operating system
WiSe 2023/2024

• kann zur Prüfung von Zeitinvarianten verwendet werden
• es gibt schreibend nur ein Reset auf 0
• sonst monoton linear steigend

Clocks are global variables that are incremented in each transition. They can be reset to 0 in each transition. They can be compared to constants and other clocks. They can be used to model time.

Channels are used to model communication between processes.

pass

pass

Es gibt keinen Pfad auf dem ein Prozess verhungert, obwohl er in die Critical-Section möchte. A[] (P(1).WAIT --> P(1).CS) bei dem --> Operator is es äquivalent das A[] wegzulassen P(1).WAIT --> P(1).CS

• keinen Kontextwechsel zwischen User- und Kernel-Mode

Active-wait protocols are more efficient than semaphores, because they do not require a context switch. They are also easier to implement.

Active-wait protocols are not preemptive, so they can lead to starvation. Also, they are not deadlock free, because they do not provide mutual exclusion.

• bei active-wait auf einem singe-core-sytem kann es dazu kommen

Ein hochpriorisierter Prozess will auf eine Critical-Section zugreifen, die aber noch von einem niederpriorisierten Prozess blockiert wird. Nun würde der hochp. Prozess gescheduled und bremst sich damit selber aus, um in die Critical-Section zu kommen.

Priority inversion is a problem that can occur when using semaphores. A high priority process is waiting for a low priority process to release a semaphore.

Peterson's algorithm is an active-wait protocol that provides mutual exclusion. It uses two flags to indicate that a process is interested in entering the critical section. It also uses a turn variable to indicate which process is allowed to enter the critical section.

(mutual exclusion):

• only one process can be in the critical section at a time
• if process 0 is in the critical section, then process 1 is not in the critical section

int turn = 0;
int interested[2] = {0, 0};

// Oo enter a ciritical section, call the following function.
// (pid is in range 0..1)
void enterCritical(int pid) {
    // int other = 1 - pid;

    interested[pid] = 1;
    turn = pid;

    while (turn == pid && interested[1 - pid] == 1) {
	// busy wait
    }
}

// To leave a critical section, call the following function.
void leaveCritical(int pid) {
    interested[pid] = 0;
}

If the assignments are swapped, then the algorithm does not provide mutual exclusion anymore. This is because the turn variable is set before the interested flag is set.

// WRONG: this does not provide mutual exclusion

void enterCritical(int pid) {
    int other = 1 - pid;

    // WRONG: turn is set before interested[pid] is set
    turn = pid;
    interested[pid] = 1;

    while (turn == pid && interested[other] == 1) {
	// busy wait
    }
}

Fischer's protocol is an active-wait protocol that provides mutual exclusion. It uses a flag to indicate that a process is interested in entering the critical section. It also uses a turn variable to indicate which process is allowed to enter the critical section.

Can be implemented and used in practice for applications with arbitrary many processes.

Most famous protocol using timers for synchronization.

It works as follows:

• A process that wants to enter the critical section sets its flag to true.
• It then waits until the flag of all other processes is false.
• It then sets its flag to false and enters the critical section.
• When it leaves the critical section, it sets its flag to false.

The processes must be synchronized. This means that they must start at the same time. Also, they must have synchronized clocks.

Strict alternation is an active-wait protocol that provides mutual exclusion. It uses a flag to indicate that a process is interested in entering the critical section. It also uses a turn variable to indicate which process is allowed to enter the critical section.

It works as follows:

• A process that wants to enter the critical section sets its flag to true.
• It then waits until the flag of the other process is false.
• It then sets its flag to false and enters the critical section.
• When it leaves the critical section, it sets its flag to false.

Userspace-Scheduling erlaubt es Anwendungsspezifische Scheduling-Entscheidungen zu treffen. Außerdem muss nicht in den Kernel-Mode, für erstellen oder wechseln von User-Threads, gewechselt werden. Dadurch weniger Overhead. Weil das Scheduling im Userspace gemacht wird, ist es unabhängig vom Betriebssystem-Scheduler und somit leichter zu portieren.

Die einzelnen User-Threads laufen alle im selben Prozess. Der Scheduler vom Kernel betrachtet den Prozess nur als ganzes. Dadurch können die User-Threads nicht echt-parallel laufen (auch auf Multithreaded CPUs) und sie laufen alle auf der selben CPU. Das Scheduling muss im Userspace gemacht werden. Weil das Scheduling im gleichen Prozess gemacht wird kann keine Preemption für aktuell laufende User-Threads gemacht werden. Die User-Threads müssen also kooperativ schedulen und sollten nicht blockieren.

Eine Anwendung mit mehreren Reitern. Bei dem Wechsel zwischen den Reitern werden die entsprechenden User-Threads gewechselt. Dadurch kann der Zustand (State) der vorher besuchten Reiter leicht behalten und später wieder aufgerufen werden. (TODO: besseres Beispiel?)

`getcontext(*ucp)` und `setcontext(*ucp)` wobei hier `*ucp` jeweils ein `user context pointer` vom Typ `ucontext<sub>t</sub>` ist. Zunächst kann man mit [`getcontext`](https://man7.org/linux/man-pages/man3/getcontext.3.html) den aktuellen Kontext bekommen. Mit `setcontext` kann man einen Kontext wieder herstellen und somit in einen anderen Kontext (User-Thread) innerhalb des selben Prozesses wechseln. Alternativ kann man auch mit [`swapcontext`](https://man7.org/linux/man-pages/man3/swapcontext.3.html) wechseln.

Ein Implementierungsdetail. Zum Beispiel mehrere Policies in einer Klasse. Zum Beispiel Realtime-Klasse und Other-Klasse. Innerhalb dieser Klasse werden Prozesse gleichbehandelt, egal welcher Policy sie angehören und entsprechend geschedult.

Der Linux-Kernel hat 6 Scheduling-Policies (in den Klassen OTHER und REALTIME). SCHED\_OTHER, SCHED\_IDLE, SCHED\_BATCH, SCHED\_FIFO, SCHED\_RR und SCHED\_DEADLINE

Prozesse, die nach einer Realtime Scheduling Policy (SCHED\_FIFO, SCHED\_RR) geschedult werden, haben auch eine sched\_priority mit Werten typischerweise in [1..99]. (POSIX.1 verlangt mindestens nur 32 Prioriäten, also [1..32]) Der Scheduler hat eine Liste von Listen. Für jede sched\_priority gibt es eine Liste von lauffähigen Prozessen. Nun muss in der Liste von (sched\_priority) Listen die höchst-priorisierteste nicht-leere Liste gefunden werden. Der Kopf dieser Liste ist der Prozess der nun geschedult wird.

Überhaupt nicht, da SCHED\_FIFO eine Realtime-Policy ist und somit eine höhere (statische) Priorität als SCHED\_OTHER hat. Solange es lauffähige Realtime-Prozesse gibt (hier permanent der Fall), werden diese ausgeführt/geschedult. Prozesse mit der SCHED\_OTHER können nur eine statische Priorität von 0 haben, welche mit der SCHED\_FIFO jedoch in [1..99] (immer > 0).

Beides sind Realtime-Scheduling-Policies, daher ist hier vorallem die Priorität wichtig und für SCHED\_RR auch sogenanntes "time quantum" (Zeit Menge). Die Prozesse der SCHED\_RR Policy haben eine Priorität von 12 und werden damit vor denen der SCHED\_FIFO mit Priorität 5 geschedult. Bei dem Round-Robin-Scheduling können Prozesse nur eine maximale Zeit (bestimmt durch das "time quantum") aktiv sein, bevor sie preempted werden und wieder ans Ende der Scheduling-Liste gestellt werden. Solange es nun lauffähige Prozesse der SCHED\_RR mit Priorität 12 gibt (höher als 5) werden diese geschedult und entsprechend ihres Zeit-Budgets "rotiert". Die SCHED\_FIFO Prozesse mit Priorität 5 würden währenddessen jedoch nicht geschedult werden.

Präemptives Scheduling bedeutet, dass die Ausführung eines Prozesses unterbrochen wird, obwohl er noch lauffähig währe. Dies erlaubt es zwischendurch andere Prozesse zu schedulen. Insgesamt sollte dadurch die Interaktivität (responsiveness) des Systems verbessert werden.

(Aus den Folien) "A schedule is weakly fair, if and only if every process that is always runnable is scheduled infinitely often. A violation of weak fairness occurs if there exists a permanently runnable process which gets the CPU only a finite number of times (or not at all)." > Ein Prozess der immer lauffähig ist, wird "unendlich" oft wieder geschedult und bekommt entsprechend auch "unendlich" oft die CPU. Also z.B. ein permanent lauffähiger Prozess.

• while True
• mit nicht-blockierenden Instruktionen

(Aus den Folien) "A schedule is strongly fair, if and only if every process that is runnable infinitely often is scheduled infinitely often. A violation of strong fairness occurs if there exists a process which is runnable infinitely often, but gets the CPU only a finite number of times (or not at all)." > Ein Prozess der "unendlich" mal lauffähig ist, wird "unendlich" oft geschedult und bekommt auch entsprechend "unendlich" oft die CPU. Also z.B. ein immer wieder lauffähiger Prozess

• wird Berechnungen immer wieder beenden
• und dann erneut lauffähig werden

Ein universell fairer Scheduler muss "strongly fair" sein. Ein Scheduling von einem fairen Scheduler muss auch von einem universell fairen Scheduler erzeugt werden können.

Ein `Dockerfile` könnte z.B. folgenden Inhalt haben: ``` FROM ubuntu:latest COPY project/binary/foo /usr/bin/foo RUN chmod +x /usr/bin/foo ENTRYPOINT ["/usr/bin/foo"] ``` Um mit einem `Dockerfile` ein neues Container-Image zu bauen `docker build -t CONTAINER<sub>NAME</sub>:TAG ./Dockerfile`. Es wird mit `FROM` ein Container-Image als Basis ausgewählt, dass angepasst werden soll. Mit dem `COPY` wird aus dem relativen Pfad `./project/binary/foo` eine Datei in den Container an den Pfad `/usr/bin/foo` kopiert. Mit `RUN` können Befehle im Container ausgeführt werden, die Änderungen dabei werden im entstehenden neuen Container-Image gespeichert (hier, dass `/usr/bin/foo` das executable-Bit gesetzt bekommt). Mit `ENTRYPOINT` wird der Befehl angegeben, der beim Start eines Containers (der das neue Container-Image verwendet) ausgeführt wird.

``` — apiVersion: batch/v1 kind: Job metadata: name: hello-world namespace: bs2024 spec: template: spec: containers:

• name: hello-world image: ubuntu:latest imagePullPolicy: IfNotPresent command: ["echo", "Hello World - version 1!"]

restartPolicy: Never backoffLimit: 4 ``` Es wird eine Resource vom Typ `Job` definiert, mit dem Namen `hello-world` und in dem Namespace `bs2024`. Der Job wird entsprechend dem `spec` spezifiziert. Es soll ein Container mit dem Namen `hello-world` gestartet werden und dafür das Container-Image `ubuntu` mit dem `latest` Tag geholt werden. In diesem Container wird der Befehl `echo "Hello World - version 1!"` ausgeführt. Falls der Container "sterben" sollte, soll er nicht neugestartet werden (`restartPolicy: Never`). Das `backoffLimit` gibt eine Grenze an, wie oft versucht werden soll den Container neuzustarten, bevor aufgegeben wird. Um einen eigenen Container zu starten würde man `image`, `command` und die `name` entsprechend anpassen.

Ein Deployment ist ein POD, welcher von Kubernetes neugestartet werden kann und von dem eine bestimmte Anzahl an Replicas vorhanden sein sollen.

Unterhalb der Container-Spezifikation können Environment-Variablen gesetzt werden: ``` spec: template: spec: containers:

• name: example-container image: docker.io/example/container env:
  • name: VARIABLE<sub>NAME</sub> value: example<sub>value</sub>

```

Ein PVC ist ein Claim/Anspruch an einen persistenten Speicher der von einem Pod gestellt wird. Zu jedem PVC gehört ein PV. Wo die Daten letzendlich gesichert/persistiert wird vom Cluster System Management entschieden.

Es gibt drei verschiedene Typen von Claims: `ReadWriteOnce`, `ReadOnlyMany`, `ReadWriteMany`

Entweder über eine DNS-Query, oder über Environment-Variablen. Angenommen es gibt einen Service `mysql-example` im Namespace `bs2024`. Dann ist die Environment-Variable `MYSQL<sub>EXAMPLESERVICEHOST</sub>` entsprechend der IP gesetzt (Pod muss gestartet worden sein, nachdem der Service existierte!). Besser ist es über DNS-Queries, z.B. mit `dig +short mysql-example.bs2024`.

Man benötigt 2 yaml-Files, eines für das replizierte Backend und eines für einen LoadBalancer welcher die Anfragen auf die Backends verteilt. ```backend.yml apiVersion: apps/v1 kind: Deployment metadata: name: backend spec: replicas: 3 template: spec: containers:

• name: example image: "docker.io/example/container:latest" ports:
  • name: http containerPort: 80

``` ```loadbalancer.yml apiVersion: v1 kind: Service metadata: name: frontend spec: selector: app: backend ports:

• protocol: "TCP" port: 80 targetPort: 80

type: LoadBalancer ```

Mehrere Container die innerhalb eines PODS laufen, können über `localhost` miteinander kommunizieren. TODO Multicast-Adresse (ggf. auch über PODS hinweg?)