# H5. Processen

---

## Inhoud

1. Van programma tot proces
2. Opbouw van een proces
3. Soorten processen
4. Beheer van processen
5. Scheduling

---

# 5.1 Van programma tot proces

---

## Compileren

Notes:

Wanneer we een programma schrijven in een programmeertaal is dat niet meteen uitvoerbaar door de hardware. De CPU verstaat geen programmeertalen zoals Java, C++, C#, ... . Elk type CPU heeft een bepaalde verzameling instructies die het begrijpt: deze verzameling heet de instructieset van dat type CPU. De instructieset wordt ook wel instruction set architecture (ISA) genoemd. Elk programma moet dus worden omgezet van broncode in een programmeertaal tot een verzameling instructies uit die instructieset. Compileren is het omzetten van de broncode naar instructies.

---

Notes:

De figuur op de slide illustreert hoe een eenvoudig programma in C omgezet wordt naar een binaire code die aan de hand van instructies uit de instructieset van de CPU het programma kan uitvoeren op de CPU.

- https://www.youtube.com/watch?v=QXjU9qTsYCc

---

## Java: write once, run everywhere

Notes:

De figuur op de slide illustreert hoe een eenvoudig programma in Java omgezet wordt naar een assembleertaal. Deze assembleertaal wordt dan omgezet naar binaire code (hier voor de eenvoud voorgesteld als hexadecimale code). Merk op dat Java geen gebruik maakt van assembler code die rechtstreeks uitgevoerd kan worden door de CPU, maar gebruik maakt van Bytecode, een soort van assembleertaal die gebruikt wordt door de virtuele CPU van de Java Virtual machine (zie ook volgende slide). Dankzij deze tussenlaag kan een gecompileerd Java programma draaien op elke hardware die een Java Virtual Machine kan draaien (write once, run everywhere). Dit in tegenstelling tot rechtstreeks gecompileerde programmeertalen zoals C, C++, Rust, ... waarbij het programma opnieuw gecompileerd moet worden voor elke instructieset van CPU's waarop het programma moet draaien.

Extra informatie hierover kan je vinden op volgende links:

- https://docs.redhat.com/en/documentation/red_hat_data_grid/7.0/html/getting_started_guide/java_virtual_machine2
- https://www.youtube.com/watch?v=cAoymPToQdg

---

## Instructieset

- Uniek per type CPU
    - Bv. x86, x86-64, ARM, MIPS, JVM, 8051, ...

Notes:

De instructieset is uniek per type CPU. Er zijn verschillende types:

- x86: De 32-bits instructieset die vroeger door Intel en AMD werd gebruikt voor gebruikers, zowel laptops als desktops, tegenwoordig is deze vervangen door een uitbreiding hiervan: de 64-bits x86-64 instructieset.
- x86-64: Dit is de instructieset die tegenwoordig door de meeste Intel en AMD processoren gebruikt wordt. Zo goed als alle gebruikers, zowel laptops als desktops, hebben dit type processor.
- ARM: Dit type processor wordt bijvoorbeeld gebruikt op de Raspberry Pi, smartphones, tablets, ... vanwege de lage kost en energieverbruik.
- MIPS: Wordt gebruikt in embedded devices zoals routers, switches, printers, smartphones, tablets, en zelfs supercomputers.
- JVM: De Java Virtual Machine (zie verder).
- 8051: Wordt soms gebruikt in embedded devices, daarnaast ook vaak gebruikt voor onderwijs.
- ... : Er zijn uiteraard nog andere CPU types in gebruik of ontwikkeling.

Een programmeur moet dus zijn programma compileren naar elk type CPU waarop het programma moet kunnen uitgevoerd worden. Je ziet bij sommige programma's dat er dus meerdere downloads worden aangeboden.

Een overzicht van de verschillende instructiesets vind je op https://en.wikipedia.org/wiki/Comparison_of_instruction_set_architectures#Instruction_sets.

In de screenshot zie je een C++ programma dat wordt omgezet naar instructies voor het type x86-64. Het programma is een heel eenvoudig programma dat de tekst "Hello World!" toont op de command line en dan afsluit. Op https://godbolt.org/z/4fe4Yn kan je in het rechtervenster verschillende types CPU aanduiden en er naar compileren. Je ziet dat de instructies voor elk type telkens verschillen.

Java is hierop een uitzondering (vandaar dat de website werkt met C++). Bij Java wordt er gecompileerd naar bytecode. Dit is een soort tussentaal met instructies uit een intructieset voor een virtuele machine, de Java Virtual Machine (JVM). De programmeur moet de java code slechts eenmaal compileren naar bytecode, en het programma werkt dan op elk type CPU waarvoor een JVM bestaat. Het is dan immers de taak van de JVM om de bytecode om te zetten naar instructies voor de hardware. Dit bespaart heel wat werk voor de programmeur.

---

## Instructiecyclus

Notes:

De computerhardware werkt steeds oneindig lang volgens hetzelfde stappenplan. Het eenmalig uitvoeren van dit stappenplan wordt ook wel een cyclus genoemd. De hardware voert dus oneindig lang cyclus na cyclus uit. In de meest eenvoudige vorm bestaat zo'n cyclus uit 2 stappen, fetch en execute:

- Fetch: Haal de volgende uit te voeren instructie op.
- Execute: Voer deze instructie uit.

Na deze 2 stappen is de cyclus afgewerkt en begint de volgende cyclus.

---

## Instructiecyclus (voorbeeld)

Notes:

In dit voorbeeld wordt een simpel programma uitgevoerd dat 2 getallen optelt en het resultaat opslaat. Dit zou bijvoorbeeld het volgende programma kunnen zijn:

```java
int a = 3;
int b = 2;
b = a + b; // b = 5
```

De instructies voor de hardware van dit systeem zijn als volgt:

- `1XXX`: Kopieer de waarde op adres XXX in het geheugen naar het `AC` register.
- `2XXX`: Sla de waarde in het `AC` register op in het geheugen op adres XXX.
- `5XXX`: Tel de waarde op adres XXX in het geheugen op bij de waarde in het `AC` register en sla het resultaat op in het `AC` register.

We zien hier de volgende CPU registers:

- `PC`: Program Counter. Dit register houdt het adres bij van de uit te voeren instructie.
- `IR`: Instruction Register. Dit register houdt de uit te voeren instructie bij. De hardware analyseert de bits in dit register om de handeling van de instructie uit te voeren.
- `AC`: ACcumulator. Een hulpregister voor tussenresultaten op te slaan van bewerkingen.

Het programma is gecompileerd naar de volgende instructies van de CPU:

- `1940`: Kopieer de waarde op adres 940 in het geheugen naar het `AC` register
- `5941`: Tel de waarde op adres 941 in het geheugen op bij de waarde in het `AC` register en sla het resultaat op in het AC register
- `2941`: Sla de waarde in het `AC` register op in het geheugen op adres 941

We zien per cyclus telkens de volgende stappen:

- Fetch: Kopieer de uit te voeren instructie op het adres volgens de `PC` van het geheugen naar het IR register. Verhoog de `PC` met 1 zodat deze klaar staat voor de juiste instructie op te halen in de volgende cyclus.
- Execute: Analyseer de instructie in het `IR` register en voer deze uit.

---

## Interrupts

Notes:

Bij computersystemen treden er soms events op: er wordt een nieuw apparaat aangesloten, de gebruiker voert iets uit, er treed ergens een fout op, er is een timer afgegaan, ... . De computer moet dan hierop kunnen reageren. Zulke onderbreking noemt men een interrupt. De fetch-execute cyclus kan uitgebreid worden om interrupts mogelijk te maken, hiervoor wordt na de execute stap een extra stap voor interrupts toegevoegd in de cyclus. Bij de interrupt stap wordt gekeken of er een interrupt is opgetreden:

- Er is geen interrupt opgetreden: Dan wordt er doorgegaan naar de volgende cyclus.
- Er is een interrupt opgetreden: De huidige uitvoering van het programma wordt onderbroken en de toestand van het programma wordt opgeslagen. Zo wordt onder meer het `PC` register opgeslagen, zodat niet vergeten wordt op welke plek het programma werd onderbroken. Daarna voert het systeem instructies uit om de interrupt af te handelen via de fetch-execute-cyclus. Deze verzameling instructies die interrupt verwerken wordt ook wel de "interrupt handler" genoemd. Het wisselen van het ene programma naar een ander programma (bv. van programma naar de interrupt handler of omgekeerd) wordt ook een "context switch" genoemd. Als de interrupt is afgehandeld, wordt de toestand van het oude programma herstelt en wordt het oude programma verder uitgevoerd.

Het gebruik van context switches komt ook aan bod in de sectie over scheduling.

---

## Binaries

Notes:

Het bestand gegenereerd door een compiler wordt ook wel een "binary" of "executable" genoemd. Op Windows worden programma's gecompileerd naar uitvoerbare bestanden in het PE-formaat (Portable Executable). Dit formaat is in de volksmond vaak bekend als het .exe-formaat, alhoewel dit formaat ook wordt gebruikt in bestanden met andere extensies. Bij Linux daarentegen worden programma's gecompileerd naar het ELF-format (Executable and Linkable Format). Op Mac wordt dan weer het Mach-O-formaat gebruikt (Mach Object). Een overzicht van dergelijke formaten vind je op https://en.wikipedia.org/wiki/Comparison_of_executable_file_formats .

Daarnaast bieden verschillende besturingssystemen verschillende functies aan programmeurs aan om bepaalde dingen te doen. Zo is het aanmaken van een venster in een GUI compleet verschillend voor Windows en Linux. Dit zorgt er voor dat een programmeur dus voor elk besturingssysteem een specifieke versie zal moeten maken en compileren. Programma's gecompileerd op het ene besturingssysteem kunnen dus niet zomaar uitgevoerd worden op een ander besturingssysteem. Het is bijvoorbeeld niet mogelijk om een .exe-bestand uit te voeren op Linux. Er bestaan wel programma's die dit proberen mogelijk te maken (zoals [WINE](https://www.winehq.org/) en [Proton](https://github.com/ValveSoftware/Proton) op Linux), maar deze zijn niet altijd bruikbaar.

In de voorbeelden hierboven zie je dat er voor veel programma's verschillende versies beschikbaar zijn voor de meest gebruikte besturingssystemen. Dit is niet bij alle programma's zo: veel games zijn bijvoorbeeld enkel uitvoerbaar op Windows.

---

## Van binary tot proces

Notes:

Eenmaal de binary is aangemaakt, is dit simpelweg een bestand dat opgeslagen is op de harde schijf of SSD. Wanneer de gebruiker het programma wil uitvoeren, worden de instructies gekopieerd naar het RAM-geheugen. Deze instantie van het programma in het RAM-geheugen wordt een "proces" genoemd. Het bestand op de schijf (het programma) is dus niet hetzelfde als het proces. Het bestand op de schijf (het programma) is iets passief: pas wanneer een instantie daarvan wordt ingeladen in het RAM-geheugen krijgen we iets actiefs, namelijk het proces.

---

# 5.2 Opbouw van een proces

---

## Proces

- Een **instantie** van een programma dat uitgevoerd wordt op het systeem.

Notes:

Processen zijn een belangrijk onderdeel van besturingssystemen. Het zijn instanties van programma's die uitgevoerd worden op het systeem. Bijvoorbeeld, stel dat ik een "Hello World!" programma heb gecompileerd naar hello.exe. Als ik dat programma nu 2x activeer door te dubbelklikken, dan draaien er op mijn systeem twee hello.exe programma's in het RAM-geheugen, ondanks dat ik slechts één hello.exe bestand heb staan op mijn harde schijf of SSD. Die 2 draaiende programma's zijn instanties van het hello.exe programma en worden elk voorgesteld binnenin het besturingssysteem door processen.

Een proces is dus een soort container die alles bevat om een programma uit te voeren. Dankzij processen kunnen besturingssystemen programma's die worden uitgevoerd beheren. Ook zorgt het gebruik van processen ervoor dat er meerdere programma's tegelijkertijd uitgevoerd kunnen worden.

Een proces in het RAM-geheugen kan enkel een bepaald deel van dat RAM-geheugen aanspreken om de inhoud van te lezen of er naar te schrijven. Dit gedeelte wordt de "address space" genoemd van dat proces. De address space bevat onder andere de uitvoerbare instructies en data van het programma.

---

## Process image

Notes:

De process image is hoe het proces er uit ziet in het RAM-geheugen. Het is een momentopname van de address space van een proces. Dit bevat in het algemeen de volgende zaken:

- Stack: tijdelijke opslag voor variabelen, functie parameters, adressen voor return uit functies, ... . Als er geen plaats meer is op deze stack, door bijvoorbeeld een te diepe of oneindige recursie, krijgt men de befaamde stackoverflow error.
- Heap: dynamisch gealloceerd geheugen. Als iets te groot is om op de stack te plaatsen, of als er iets beschikbaar moet zijn over de grenzen van functies heen, dan is de stack geen bruikbare optie. In dat geval kan er gebruik gemaakt worden van de heap om iets dynamisch te alloceren. De heap werkt niet zoals een stack: wat er wordt bewaard, blijft beschikbaar tot het door de programmeur wordt opgekuist.
- Data: globale variabelen.
- Text: de uit te voeren instructies.

De exacte vorm van een process image is sterk afhankelijk van besturingssysteem tot besturingssysteem.

Het verschil tussen heap en stack is erg belangrijk voor programmeurs. Programmeertalen die zelf de opslag van variabelen en containers behandelen (garbage-collected programmeertalen zoals Java) verstoppen een groot deel van deze complexiteit, maar C/C++/Rust/...-programmeurs moeten hier goed rekening mee houden om segmentation faults en memoryleaks te voorkomen.

Meer informatie over stack vs. heap:

- https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html
- https://www.youtube.com/watch?v=fADovR07-1M
- https://www.digitalocean.com/community/tutorials/java-heap-space-vs-stack-memory

Extra informatie over process images:

- https://tldp.org/LDP/tlk/kernel/processes.html
- https://tldp.org/LDP/LG/issue23/flower/psimage.html

---

## Process Control Block (PCB)

Notes:

Het besturingssysteem heeft een overzicht van alle processen die actief zijn op het systeem. Dit overzicht heeft de vorm van een tabel en wordt ook wel de process table genoemd. Elke element in de tabel bevat informatie over een proces. Een dergelijk element wordt ook wel een process control block (PCB) genoemd. Een PCB bevat algemeen de volgende informatie:

- Informatie om het proces uniek te identificeren.
- Informatie om de staat van het proces bij te houden bij context switches (zie ook de sectie over scheduling).
- Informatie om het proces te beheren (zie ook de sectie over scheduling).

De vorm van een PCB is sterk afhankelijk van besturingssysteem tot besturingssysteem. In de slide tonen we 2 verschillende generieke vormen van een PCB. Je merkt dat bepaalde informatie in beide gevallen terugkomt (al dan niet onder een andere noemer).

---

# 5.3 Soorten processen

---

## Soorten processen

- Interactief
- Automatisch
- Daemons

---

## Interactief proces

- Opstarten en controleren vanuit een terminal sessie
- Kunnen zowel in voorgrond (foreground) als achtergrond (background) draaien
    - **Foreground process**: blokkeert terminal zolang het loopt
    - **Background process**: blokkeert terminal enkel bij opstart van het proces, nadien kan terminal andere taken uitvoeren

---

## Automatische processen

- Ook wel "batch" processen genaamd
- Verzameling van processen die in een wachtrij worden geplaatst wachtend op uitvoering
- Bij uitvoering worden alle processen één voor één uit de wachtrij uitgevoerd. Dit volgens het **F**irst **I**n, **F**irst **O**ut (FIFO) principe
- Voorbeeld: automatisch een back-up maken (elke dag om middernacht)

---

## Daemons

- Processen die continu draaien
- Veelal gestart bij opstarten van systeem
- Wachten in de achtergrond tot ze nodig zijn
- Ook gekend als **services**
- Voorbeelden: OneDrive-synchronisatie, MySQL database...

---

# 5.4 Beheer van processen

---

## Ontstaan

Notes:

Het ontstaan van processen verschilt van besturingssysteem tot besturingssysteem. We behandelen hier het geval van Linux.

Op een Linux systeem heeft elk proces een uniek ID-nummer. Dit nummer wordt ook wel "Process Identifier" (PID) genoemd. Op een linux systeem start bij het opstarten als eerste proces het proces met PID 1. Op recentere systemen is dit systemd, op sommige oudere systemen kan men ook nog het init proces tegenkomen. Systemd is dus bij recente linux distro's de moeder van alle processen. Alle andere processen worden aangemaakt als kinderen door een ouderproces, waardoor er zich een boom van processen vormt. In het voorbeeld hierboven zien we het moederproces systemd dat de kindprocessen logind (om ervoor te zorgen dat gebruikers zich kunnen inloggen), python (om python programma's uit te voeren), en sshd (om ervoor te zorgen dat gebruikers kunnen inloggen via SSH) heeft aangemaakt. Een gebruiker heeft zich ingelogd op het toestel, waardoor logind het kindproces bash heeft aangemaakt om de gebruiker een bash shell te geven. Daarin heeft de gebruiker de commando's ps en vim ingetypt en zo bash de opdracht gegeven om de ps (toon een lijst van processen op de CLI) en vim (text editor) kindprocessen aan te maken. Daarnaast zien we ook dat iemand zich heeft ingelogd via SSH (zie het kindproces sshd van sshd) waardoor de tcsh shell (alternatief voor bash) is aangemaakt als kindproces van sshd.

---

## Ontstaan

Notes:

Het aanmaken van een proces in Linux bestaat uit het aanroepen van 2 functies: `fork()` en `exec()`.

- `fork()`: Deze functie maakt een exacte kopie van het proces in het RAM-geheugen (een kopie van diens address space dus) en vult de PID van het proces in met een nieuw ongebruikt procesnummer. Daarnaast vult de functie het PPID (Parent Process Identifier) in met het PID van het ouderproces.
- `exec()`: Het nieuw aangemaakt kindproces wordt overschreven met de nodige waarden voor het gewenste proces. Zo worden bijvoorbeeld de juiste instructies, waarden, ... ingelezen naar het procesbeeld van het kindproces.

Extra informatie: https://github.com/illinois-cs241/coursebook/wiki/Processes

---

## Afbraak

- Het proces is afgewerkt of er treedt een fout op: `exit()`
- Het proces wordt afgebroken door een ander proces: bv. `kill`
- Soms gaat er iets fout: zombie proces → orphan proces
- In de terminal kan je steeds het huidige proces op de voorgrond beëindigen met `Ctrl`+`C`

Notes:

Wanneer een proces zijn taak heeft volbracht of er een fout optreedt, wordt het afgesloten. Dit gebeurt in linux met behulp van het exit() commando. Aan dit commando kan een getal als parameter meegegeven worden om aan te duiden of het proces correct is afgewerkt (getal 0) of dat het is afgesloten door een fout (een getal verschillend van 0). Bij een fout vertelt het getal (= de foutcode) welke fout er is opgetreden.

Als het proces wordt afgesloten, wordt het procesbeeld verwijderd en alle resources (bv. bestanden, geheugen, ...) dat het proces in gebruik had, worden terug vrijgegeven. De PCB in de process table mag wel nog niet meteen vrijgegeven worden. Het bevat immers de foutcode die aangeeft waarom het proces is afgesloten. Als de PCB ook meteen verwijderd zou worden, kan het ouderproces niet achterhalen waarom zijn kindproces is afgesloten.

Een proces waarvan enkel de PCB nog bestaat, wordt ook wel een zombieproces genoemd. Normaal gezien bestaan zombieprocessen slechts kortstondig: de PCB wordt snel na het afsluiten van het kindproces gelezen door het ouderproces, waardoor het PCB verwijderd mag worden en het kindproces volledig is verdwenen. Soms gebeurt het echter dat een foutcode van zo'n zombieproces nooit wordt gelezen (bv. het ouderproces is afgesloten alvorens de foutcode te lezen). In dat geval wordt het zombieproces een orphan process (weesproces). Het besturingssysteem kan hier niet meer aan en de PCB's van zulke processen vervuilen dus de process table van het besturingssysteem.

---

## Wachten

Notes:

Om ervoor te zorgen dat zombieprocessen niet te lang resources vasthouden, is het aangeraden dat het ouderproces wacht totdat het kindprocess gestopt is. Op deze manier detecteert het ouderproces snel dat het kindproces gestopt is, leest het de exit code uit de PCB, en kan het besturingssysteem het kindproces verwijderen.

Als een ouderproces niet wacht op het kindproces en geen ander mechanisme heeft om te detecteren of het kindproces gestopt is, dan blijft het PCB van het kindproces in het besturingssysteem aanwezig en houdt het kindproces ook de resources vast. Hierdoor kan het besturingssysteem "verhongeren" (starvation). Het kindproces wordt dan ook wel een "resource leak" genoemd.

Extra informatie: https://github.com/cs341-illinois/coursebook/wiki/Processes#the-fork-exec-wait-pattern

---

```c
#include <unistd.h>

int main() {
  pid_t pid = fork();
  if (pid < 0) { // fork failure
    exit(1);
  } else if (pid > 0) { // we are the parent
    int status;
    waitpid(pid, &status, 0);
  } else { // pid == 0: we are the child
    execl("/bin/ls", "/bin/ls", NULL);
    exit(1); // for safety
  }
}
```

Notes:

De C-code is niet te kennen en puur ter illustratie.

---

## Procesmodel met 2 statussen

Notes:

Op dit moment hebben we gezien dat processen zijn eigenlijk in 2 toestanden kunnen bevinden: wordt uitgevoerd op de CPU of staat te wachten. De toestand van een process wordt ook wel state genoemd. Het 2-state scheduling model is het simpelste scheduling model dat er is en bevat dus 2 toestanden:

- Running: dit proces wordt uitgevoerd op de CPU.
- Not Running: dit proces wordt niet uitgevoerd op de CPU

We zien dat processen die staan te wachten op de CPU in een wachtrij (queue) worden geplaatst en aanschuiven voor CPU-tijd. Nieuwe processen worden aangemaakt, krijgen een PCB in de process table, en worden dan toegevoegd aan de queue. Nieuwe processen hebben dus steeds de Not Running toestand (tenzij ze meteen de CPU mogen gebruiken).

---

## Procesmodel met 5 statussen

Notes:

Uiteraard zijn de meeste besturingssystemen complexer dan het 2-state scheduling model. Zo kan het ook zijn dat processen staan te wachten op een antwoord van I/O. In dat geval draait het proces niet op de CPU en staat het ook niet in de wachtrij. We hebben dus namelijk een extra toestand nodig: Blocked. We breiden het model uit met de volgende staten:

- New: Een nieuw proces aangemaakt door het besturingssysteem. Meestal een nieuw proces waarvan de PCB al is toegevoegd aan de process table, maar dat nog niet volledig is ingeladen in het geheugen. Soms wordt er ook een limiet gezet op het aantal processen in de wachtrij: als deze vol zit mag een proces nog niet overgaan van New naar Ready tot de wachtrij vrije plaatsen heeft.
- Ready: Een proces dat wacht tot het op de CPU mag.
- Running: Het proces wordt uitgevoerd op de CPU.
- Blocked: Een proces dat staat te wachten op iets (zoals lezen/schrijven uit of naar het RAM, geheugen, harde schijf, SSD, netwerk, ...).
- Exit: Een afgewerkt proces. Let op, de exit toestand zegt niets over het feit dat het proces correct is afgewerkt of door een fout is afgesloten. De scheduler heeft daar niets mee te maken, het weet alleen dat hij met dit proces geen rekening moet houden: het is op hoe dan ook een of andere manier afgerond.

Enkele belangrijke overgangen:

- Ready → Running: Het proces dat als eerste staat in de wachtrij mag op de CPU.
- Running → Ready: Processen mogen vaak slechts een bepaalde maximum tijd op de CPU (zie bv. time sharing). Die maximum tijd wordt ook wel quantum of time slice genoemd. Wanneer de tijd verlopen is, wordt het proces van de CPU gehaald en achteraan de wachtrij geplaatst. Het onderbreken van een proces wordt ook wel preemption genoemd.
- Running → Blocked: Het proces moet wachten op iets (bv. I/O) en wordt van de CPU gehaald zodat deze gebruikt kan worden door een ander proces dat de CPU-tijd kan gebruiken.
- Blocked → Ready: het proces heeft gedaan met wachten (bv. I/O). Dit is vaak het resultaat van een gebeurtenis (event) (bv. de data is gelezen van de harde schijf). Het proces heeft opnieuw CPU-tijd nodig en wordt dus achteraan de wachtrij geplaatst.

---

## Procesmodel met 6 statussen

Notes:

Processen in het 5-state scheduling model bevinden zich allemaal in het RAM-geheugen van het systeem. Alleen kan het soms gebeuren dat dat RAM-geheugen vol geraakt. In dat geval heeft het systeem geen plaats meer om zaken op te slaan of aan te passen en loopt het vast. Om dit op te lossen kan het systeem bepaalde processen die staan de wachten uit het RAM-geheugen verplaatsen naar de harde schijf of SSD om RAM-geheugen vrij te maken. Dit wordt ook wel "swapping" genoemd. Zulke processen bevinden zich dan in de Suspend toestand. Wanneer het systeem terug voldoende ademruimte heeft in het RAM-geheugen, kan het systeem terug processen vanop de hardeschijf of SSD verplaatsen naar het RAM-geheugen. De processen krijgen dan terug de Ready toestand en mogen weer aanschuiven in de wachtrij.

---

## Procesmodel met 7 statussen

Notes:

In het laatste model maken we nog een extra onderscheid bij de status Suspend. Een proces kan in suspend toestand zitten maar wel klaar zijn om uitgevoerd te kunnen worden (Ready/Suspend) ofwel is het proces suspend maar moet zijn evenement nog gebeuren alvorens het verder uitgevoerd kan worden (Blocked/Suspend).

Merk ook op we nu ook de mogelijkheid hebben om een nieuwe aangemaakte proces of het huidige draaiend proces rechtstreeks te suspenden.

---

## Swapping (Suspend)

Notes:

Op dit systeem zie je dat het RAM-geheugen volloopt. Het systeem riskeert daardoor vast te lopen. Om dat te vermijden zal het systeem processen wegschrijven naar de harde schijf of SSD om RAM-geheugen vrij te maken om ervoor te zorgen dat het systeem niet in de problemen komt. Op Windows wordt er weggeschreven naar de pagefile.sys en swapfile.sys bestanden op de C:\ schijf (meer info over deze bestanden vind je op https://helpdeskgeek.com/help-desk/hdg-explains-swapfile-sys-hiberfil-sys-and-pagefile-sys-in-windows-8/ ). Op Linux is er daarentegen vaak een aparte swap partitie aanwezig.

Swappen is een intensief proces: de harde schijf of SSD is vele malen trager dan het RAM-geheugen (zie de tabel op een aantal slides verder). Swappen vertraagt het systeem enorm!

Er is tegenwoordig ook een debat of swap ruimte of Windows of Linux met de huidige RAM hoeveelheden nog relevant is. Het heeft zijn voor- en nadelen om wel of geen swap ruimte te voorzien. Meer info vind je op:

- https://www.windowscentral.com/what-swapfilesys-and-do-i-need-it-my-windows-10-pc
- https://www.redhat.com/en/blog/do-we-really-need-swap-modern-systems

---

# 5.5 Scheduling

---

## Multiprogramming

- CPU zo optimaal mogelijk gebruiken
    - I/O is trager dan CPU
    - Sommige processen moeten wachten op iets (zoals bv. I/O)
- Wanneer een proces moet wachten, kan een ander proces gebruik maken van de CPU

Notes:

Een besturingssysteem zal steeds trachten de hardware zo optimaal mogelijk te benutten. Aangezien CPU-tijd een schaars goed is, zal het de CPU ten volle proberen gebruiken. Het percentage tijd dat de CPU in gebruik is, wordt ook wel CPU utilization genoemd. Als een CPU staat te nietsen, zegt men dat de CPU "idle" is. Het besturingssysteem probeert de CPU utilization zo hoog mogelijk te krijgen en de CPU idle time zo laag mogelijk. Hierbij zijn wel enkele valkuilen. Zo is de snelheid van een CPU vele malen hoger dan die van andere hardware zoals RAM, harde schijven, SSD's, netwerk, ... . Elke keer een programma iets van de opslag of netwerk nodig heeft, moet het wachten. Hierdoor gaat kostbare tijd verloren. Om de CPU toch bezig te houden wordt er ondertussen een ander proces op de CPU geplaatst. Wanneer het eerste proces gedaan heeft met wachten op de I/O, vraag het terug CPU-tijd aan. Dit concept wordt "multiprogramming" genoemd en zorgt ervoor dat de CPU continu bezig blijft en er geen CPU-tijd verloren gaat.

---

## Multiprogramming

$CPU\ utilization = \frac{CPU\ usage\ time}{Total\ time}$ → Streven naar 100%

$CPU\ idle = \frac{CPU\ idle\ time}{Total\ time}$ → Streven naar 0%

Notes:

Let op: een besturingssysteem dat continu aan 100% draait is ook niet ideaal. Indien er dan een interrupt binnenkomt, is er immers geen CPU-tijd beschikbaar om deze interrupt af te werken. M.a.w. een systeem waarvan de CPU volledig aan 100% werkt, zal niet meer lijken te reageren tot de taken die de CPU opeisen afgewerkt zijn of minder CPU-tijd vragen. Er wordt dus best gestreefd naar een goed compromis tussen een zo hoog mogelijke CPU utilization en een marge voor interrupts. De ideale CPU utilization is dus eigenlijk minder dan 100%.

---

## Multiprogramming

| Computer action                           | Average latency | Normalized human time |
| ----------------------------------------- | --------------- | --------------------- |
| 3GHz CPU clock cycle                      | 0.3 ns          | 1 s                   |
| Level 1 cache access                      | 0.9 ns          | 3 s                   |
| Level 2 cache access                      | 2.8 ns          | 9 s                   |
| Level 3 cache access                      | 12.9 ns         | 43 s                  |
| RAM access                                | 70-100 ns       | 3.5-5.5 m             |
| NVMe SSD I/O                              | 7-150 μs        | 2 h - 4 days          |
| HDD I/O                                   | 1-10 ms         | 11 days - 4 months    |
| Internet (San Francisco to New York City) | 40 ms           | 1.2 years             |
| Internet (San Francisco to Australia)     | 183 ms          | 6 years               |
| physical reboot                           | 90 s            | 3000 years            |

Notes:

Je hoeft de exacte getallen op de slide niet te kennen. Je moet natuurlijk wel een idee hebben welk type I/O sneller is dan de andere.

Bron: https://formulusblack.com/blog/compute-performance-distance-of-data-as-a-measure-of-latency/

Een heel mooie illustratie van de vertraging op verschillende soorten I/O kan je zien op https://planetscale.com/blog/io-devices-and-latency. Je kan zelf uitproberen hoe lang het duurt om data te lezen van tape drives, harde schrijven, SSD's...

---

## Voorbeeld uniprogramming

$CPU\ utilization = \frac{5\ +\ 2\ +\ 8}{5\ +\ 2\ +\ 8\ +\ 3\ +\ 6\ +\ 1} = \frac{15}{25} = 60 \\%$

Notes:

Op de slide zie je een voorstelling van de uitvoering van 3 processen op een CPU. De groene vakjes wijzen op uitvoering, de gele vakjes op wachten. In dit geval is de CPU utilization 60%. Dit is niet optimaal: de CPU is 40% van de tijd idle. In dit geval is er dus nog 40% van de tijd dat de CPU niets doet. Dit is niet efficiënt. Het besturingssysteem kan de CPU beter benutten door een ander proces op de CPU te plaatsen wanneer een proces moet wachten op I/O.

Bron: https://w3.cs.jmu.edu/kirkpams/OpenCSF/Books/csf/html/Multiprogramming.html

---

## Voorbeeld multiprogramming

$CPU\ utilization = \frac{5\ +\ 2\ +\ 8}{5\ +\ 2\ +\ 8\ +\ 1} = \frac{15}{16} = 93.75 \\%$

Notes:

In dit voorbeeld zie je dat een ander proces de uitvoering over de CPU krijgt wanneer een proces moet wachten op I/O. In dit geval is de CPU utilization 93,75%. Dit is optimaal: de CPU is continu bezig en er gaat geen (of weinig) CPU-tijd verloren. Dit is het doel van multiprogramming.

Bron: https://w3.cs.jmu.edu/kirkpams/OpenCSF/Books/csf/html/Multiprogramming.html

---

## Time sharing

Notes:

Terwijl multiprogramming dient om geen CPU-tijd verloren laten gaan, gebruikt het besturingssysteem ook time sharing om de illusie te geven dat de gebruiker meerdere processen tegelijkertijd uitvoert. In de realiteit wisselt het besturingssysteem processen op de CPU elkaar kort af, waardoor het lijkt alsof de processen tegelijkertijd uitgevoerd worden omdat computers veel sneller werken dan mensen. Multiprogramming kan dus ook perfect werken op een CPU met slechts 1 core. Het besturingssysteem moet wel een goede afweging maken hoelang processen aan een stuk op de CPU mogen. Als deze tijd te kort is, dan steekt het besturingssysteem te veel tijd in het wisselen van processen en is het niet efficiënt. Is de tijd te lang, dan merkt de gebruiker dit op.

Multiprogramming en time sharing hebben dus een verschillend doel:

- Multiprogramming: de CPU ten volle benutten.
- Time sharing: de illusie van parallelle processen creeëren.

---

## Scheduler

- De scheduler bepaalt wanneer welk proces CPU-tijd krijgt
- Geen eenvoudige beslissing. Mogelijke factoren:
    - Prioriteit
    - Status
    - Volgorde in de wachtrij
- Dit kan sterk verschillen tussen processen
    - Interactieve programma's
    - Batch programma's
    - Real-time programma's

Notes:

De scheduler is het onderdeel van het besturingssysteem dat beslist wanneer een bepaald proces CPU-tijd krijgt. De simpelste scheduler is een eenvoudige wachtrij: het eerste proces in de wachtrij (queue in het Engels) mag uitgevoerd worden. Wanneer dat klaar is, is het aan het volgende proces. Nieuwe processen moeten achteraan de wachtrij aanschuiven tot het hun beurt is. Dit eenvoudig algoritme wordt "First Come First Serve" genoemd. Er zijn nog veel complexere algoritmes mogelijk waarbij er gekeken wordt naar hoeveel een proces moet wachten op I/O, hoelang een proces zal duren, welke processen prioriteit krijgen, ... .

Een scheduler heeft dus een lastige taak en is ook vaak een lastig te programmeren. Wanneer een scheduler zijn werk niet goed doet, heeft dit vaak gevolgen voor de gebruiker. We delen de mogelijke types processen op in 3 groepen:

- Batch programma's bestaan uit processen die een na een moeten worden uitgevoerd en vaak weinig tot geen interactie hebben met de gebruiker. Vaak gaat het om een lijst van opdrachten die gegeven wordt aan de computer, die deze een na een afwerkt. Bij batchprocessen is een wachtrij als basis voor een scheduler vaak voldoende.
- Interactieve programma's bestaan uit processen op command line of GUI waarmee we het meeste vertrouwt zijn. We kunnen deze uitvoeren door zaken in te typen of door op knoppen te duwen. Deze processen geven ook vaak resultaten terug weer. Als de scheduler niet goed zijn job doet, lijkt het voor de gebruiker alsof programma's blijven hangen.
- Realtime systemen zijn systemen die een hoge snelheidsrespons nodig hebben. Bv. bij streamen leiden kleine vertragingen al snel tot stotter en lag, wat erg hinderlijk is voor de gebruiker. Schedulers doen er dus goed aan om zulke processen voorrang te geven.

---

## Voorrang

- Theoretisch probleem: een nieuw proces komt toe net op het moment dat een running proces onderbroken wordt
    - Kans klein in de echte wereld
    - In onze vereenvoudigde voorbeelden komt dit echter wel vaak voor
    - **Huidig proces dat onderbroken wordt** wordt **eerst** aan de wachtrij toegevoegd
        - Daarna pas nieuw proces.

Notes:

In de echte wereld is de kans klein dat dit probleem voorkomt, want er zal meestal één proces iets vroeger zijn dan het andere proces. In onze (vereenvoudigde) voorbeelden komt dit echter wel vaak voor omdat we werken met discrete tijdseenheden. We maken volgende afspraak: in deze situatie wordt het huidige proces dat onderbroken wordt eerst toegevoegd aan de wachtrij, dan pas het nieuwe proces.

---

## Preemption

- Onderbreken huidig proces om voorrang te geven aan een ander proces
    - Nodig indien proces systeem kan monopoliseren
    - Wisselen van proces zorgt voor extra overhead
    - Huidige proces wordt terug in wachtrij gezet indien niet voltooid

---

## Starvation

- Proces krijgt geen CPU-tijd en "verhongert"
- Mogelijk scenario:
    - De scheduler geeft voorrang aan korte processen
    - Hierdoor komen steeds nieuwe korte processen in het systeem
    - Waardoor lange processen telkens worden uitgesteld

---

## Voorbeelden van scheduler-types

- Zonder preemption
    - First Come, First Served (FCFS)
    - Shortest Process Next (SPN)
- Met preemption
    - Shortest Remaining Time (SRT)
    - Round Robin (RR)

Notes:

Er bestaan verschillende algoritmen voor schedulers om CPU-tijd toe te wijzen aan processen. Deze kunnen onderverdeeld worden in 2 categorieën:

- Non-preemptive: algoritmes die geen gebruik maken van context switches en dus pas wisselen van proces wanneer een proces volledig is afgewerkt.
- Preemptive: algoritmes die gebruik maken van context switches om processen op de CPU te onderbreken en om te wisselen met een ander proces.

In de volgende slides zien we voor elk type een voorbeeld van een eenvoudig algoritme:

- FCFS (First Come First Serve): een non-preemptive algoritme waarbij er gebruik wordt gemaakt van een eenvoudige wachtrij. Elk proces op de CPU wordt volledig afgewerkt. Daarna is het de beurt aan het volgende proces uit de wachtrij, dat dan op zijn beurt ook volledig wordt afgewerkt. Er worden geen processen van de CPU gehaald als ze nog niet volledig zijn afgewerkt.
- SPN (Shortest Proces Next): een non-preemptive algoritme waarbij er gebruik wordt gemaakt van een eenvoudige wachtrij. Elk proces op de CPU wordt volledig afgewerkt. Daarna is het de beurt aan het volgende proces uit de wachtrij dat de kortste geschatte uitvoeringstijd heeft, dat dan op zijn beurt ook volledig wordt afgewerkt. Er worden geen processen van de CPU gehaald als ze nog niet volledig zijn afgewerkt. In tegenstelling tot FCFS wordt het volgende proces dus niet gekozen op basis van de volgorde van ontstaan.
- SRT (Shortest Remaining Time): een preemptive algoritme waarbij er telkens een nieuw proces ontstaat een afweging wordt gemaakt welk proces het minst tijd op de CPU zal nemen. Als het nieuw proces minder CPU-tijd nodig heeft dan het huidige proces op de CPU, wordt er van proces gewisseld. Er wordt dus gebruik gemaakt van context switches.
- RR (Round Robin): een preemptive algoritme waarbij de CPU om de $Q$ eenheden wisselt naar het volgende proces uit de wachtrij. Het huidige proces wordt dan achteraan in de wachtrij opnieuw toegevoegd indien het nog niet klaar was.

---

## Planners

- Elke type planner wordt opgesteld op basis van een tabel die het overzicht bevat van alle processen:

Notes:

- Horizontale as = tijdslijn
- Startpunt = tijdstip dat proces aangeboden wordt
- Aantal gekleurde vakjes = tijd dat proces nodig heeft om uitgevoerd te worden
- Bv. groene proces start op tijdstip 1 en heeft 4 tijdseenheden nodig om uitgevoerd te worden

---

## First Come, First Served (FCFS)

- Proces wordt volledig uitgevoerd, geen preemption
- Processen worden, indien nodig, in wachtrij geplaatst
- Volgende proces? Eerste proces uit de wachtrij

---

## First Come, First Served (FCFS)

- Voordelen:
    - Geen starvation
    - Heel eenvoudig
- Nadelen:
    - Korte processen moeten mogelijk lang wachten
    - Proces kan systeem monopoliseren

---

## FCFS (voorbeeld)

↓

---

## Shortest Process Next (SPN)

- Proces wordt volledig uitgevoerd, geen preemption
- Processen worden in wachtrij geplaatst indien nodig
- Volgende proces? Kortste proces uit de wachtrij

---

## Shortest Process Next (SPN)

- Voordeel: korte processen zijn snel uitgevoerd
- Nadelen:
    - Starvation voor lange processen
    - Proces kan systeem monopoliseren

---

## SPN (voorbeeld)

↓

---

## Shortest Remaining Time (SRT)

- Proces wordt onderbroken indien er zich een beter (= korter) proces aandient
- Processen worden in wachtrij geplaatst indien nodig
- Volgende proces? Proces met kortste overgebleven uitvoeringstijd uit de wachtrij

---

## Shortest Remaining Time (SRT)

- Voordeel: korte processen zijn snel uitgevoerd
- Nadelen:
    - Starvation voor lange processen
    - Overhead bij veel wisselen

---

## SRT (voorbeeld)

↓

---

## Round Robin (RR)

- Elk proces wordt beurtelings Q eenheden uitgevoerd
- Processen worden in wachtrij geplaatst indien nodig
- Volgende proces? Volgende proces uit wachtrij, laatst uitgevoerde wordt achteraan de wachtrij terug toegevoegd

---

## Round Robin (RR)

- Voordeel:
    - Eerlijk
    - Geen starvation
- Nadelen:
    - Waarde Q heel belangrijk
    - Korte processen moeten soms lang wachten
    - Overhead bij veel wisselen

---

## RR (voorbeeld)

↓

---

## Overzicht voorbeelden

↓

---

## Overzicht type planners

|             | FCFS                                       | SPN                                                        | SRT                                                    | Round robin                                                              |
| ----------- | ------------------------------------------ | ---------------------------------------------------------- | ------------------------------------------------------ | ------------------------------------------------------------------------ |
| Preemptive? | ❌                                        | ❌                                                        | ✅                                     | ✅                                                       |
| Voordelen   | geen starvation, makkelijk te programmeren | korte processen snel uitgevoerd                            | korte processen snel uitgevoerd                        | geen starvation, eerlijk                                                 |
| Nadelen     | korte processen moeten soms lang wachten   | starvation lange processen, monopolisatie systeem mogelijk | starvation lange processen, overhead bij veel wisselen | goede $Q$-waarde is belangrijk, korte processen moeten soms lang wachten |
| Best bij    | lange processen                            | korte processen                                            | korte processen                                        | lange processen                                                          |

---

## Extra voorbeelden/oefeningen planners

- Van klein naar groot
- Van groot naar klein
- Lange processen
- Korte processen
- Je kan <a href="./files/planners_sjabloon.xlsx">dit sjabloon</a> gebruiken bij het oplossen

---

## Van klein naar groot (Opgave)

- Gegeven:

- Gevraagd: stel op basis van bovenstaande situatie de planner op volgens
    - FCFS
    - SPN
    - SRT
    - RR met $Q = 4$, $Q = 6$ en $Q = 8$

---

## Van klein naar groot (Oplossing)

↓

---

## Van groot naar klein (Opgave)

- Gegeven:

- Gevraagd: stel op basis van bovenstaande situatie de planner op volgens
    - FCFS
    - SPN
    - SRT
    - RR met $Q = 4$, $Q = 6$ en $Q = 8$

---

## Van groot naar klein (Oplossing)

↓

---

## Lange processen (Opgave)

- Gegeven:

- Gevraagd: stel op basis van bovenstaande situatie de planner op volgens
    - FCFS
    - SPN
    - SRT
    - RR met $Q = 2$, $Q = 5$ en $Q = 7$

---

## Lange processen (Oplossing)

↓

---

## Korte processen (Opgave)

- Gegeven:

- Gevraagd: stel op basis van bovenstaande situatie de planner op volgens
    - FCFS
    - SPN
    - SRT
    - RR met $Q = 2$, $Q = 4$ en $Q = 5$

---

## Korte processen (Oplossing)

↓

---

## Bronnen

- Andrew S. Tanenbaum and Herbert Bos. 2014. Modern Operating Systems (4th. ed.). Prentice Hall Press, USA
- William Stallings. 2018. Operating Systems: Internals and Design Principles, 9/e (9th. ed.). Pearson IT Certification, Indianapolis, Indiana, USA
- Tanenbaum & Austin, 2013. Structured Computer Organization (6th. ed.). Pearson, USA

---

- Abraham Silberschatz, Peter B. Galvin, and Greg Gagne. 2018. Operating System Concepts (10th. ed.). Wiley Publishing
- Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. 2018. Operating Systems: Three Easy Pieces. Arpaci-Dusseau Books. https://pages.cs.wisc.edu/~remzi/OSTEP/#book-chapters