5.3 - Scheduling Algorithms (p.198)

NB. Ik raad je aan om deze bladzijden in het boek te bekijken, het was erg lastig om dit onderwerp te samenvatten zonder al te veel tijd te besteden aan voorbeelden.

First Come First Serve (FCFS)

• Het process dat als eerste de CPU nodig heeft, krijgt deze ook als eerste.
• Maakt gebruik van een FIFO queue.
• Gemiddelde waiting time is lang.
• Is non-preemptive.
• Convoy effect = De kleine processen moeten wachten totdat het grote process van de CPU af is. Dit beinvloed de wachttijd enorm.

Shortest Job First Scheduling (SJF)

• Het process dat het kortste CPU burst time heeft, gaat als eerste.
• Wanneer er meerdere processen hetzelfde CPU burst time hebben, dan gaat het process die als eerste was voor.
• Gemiddelde waiting time is korter.
• Kan zowel preemptive als non-preemtive zijn.
  • Bij preemptive wordt een process onderbroken wanneer er een "korter" process in de queue is. (shortest remaining time first)
  • Bij non-preemptive wordt het process afgemaakt, en daarna het volgende kortste process in de queue in de CPU geladen.
    • Heeft een iets hoger gemiddelde wachttijd. (afhankelijk van de lengte van de processen natuurlijk)
• Voorspellen van CPU burst tijden wordt gedaan op basis van vorige tijden en een expodentieel gemiddelde van vorige processen.
  • EST[n] = a*MBL[n-1] + (1-a)*EST[n-1] (OS Les 4, sheet 14)
  • EST = Estimated Length, MBL = Measured Burst Length, n = huidig process, n-1 = vorig process, a = exponentiele verwachtings gemiddelde
  • a & 1-a zijn altijd < 1, dus elk opvolgend process heeft een lagere tijd dan zijn voorganger.

Priority Scheduling

• Het process met het hoogste prioriteit gaat voor.
  • LET OP: Sommige systemen vinden 0 het hoogste, en andere systemen vinden 0 het laagste prioriteitsniveau.
• Kan zowek preemptive als non-preemtive zijn.
  • Bij preemptive wordt een process onderbroken wanneer een een belangrijker process in de queue komt.
  • Bij non-preemptive wordt het process afgemaakt, en daarna het volgende belangrijkste process gekozen.
• Starvation/indefinite blocking is mogelijk als er altijd hoge prioriteit processen zijn die voor de lage prioriteit processen gaan.
  • Oplossing kan zijn aging, waarbij de lage prioriteit processen langzaam een hogere prioriteit krijgen.

Round Robin Scheduling (RR)

• Processen worden in FIFO omgewisseld na een bepaalde tijd.
• Time Quantum (time slice) = Een definitie van de hoeveelheid tijd die een process krijgt op de CPU. Over het algemeen tussen 10-100 ms.
• De Round Robin Scheduling creert de illusie dat elk proces zijn eigen processor heeft draaiend op 1/n snelheid van de echte processor.
• Elk process hoeft niet langer te wachten dan (n - 1) * q ms tot zijn volgende time quantum.
  • n = aantal processen in queue, q = time quantum
• De effectieviteit van dit algoritme hangt grotendeels af van de groote van het Time Quantum.
• Voor grote effectiviteit moet 80% van de CPU bursts kleiner zijn dan de time quantum.
• Hoe kleiner de time quantum, des te meer context switches zijn nodig. Welke ook een bepaalde tijd innemen op de CPU.

Multilevel Queue Scheduling

• Scheduling algoritme gecreeerd voor situaties waarbij processen makkelijk onder te verdelen zijn in groepen.
  • Ex. Voorgrond (interactieve) en Achtergrond (batch) processen.
  • Verschillende scheduling eisen (response tijd oa)
• Multilevel queue scheduling algorithm = Opdelen van de ready queue in kleinere queues (overeenkomend met de groepen), met een eigen prioriteit in het systeem.

Multilevel Feedback Queue Scheuduling

• Zelfde principe als hierboven, alleen mogen processen wisselen tussen (sub)queues.
  • Ex. Als een process teveel CPU tijd gebruikt wordt deze in een lagere prioriteit queue geplaatst.
  • Ex. Een process dat al lang wacht in een lagere prioriteit queue, kan naar een hogere prioriteit queue worden verzet. (een andere implementatie van aging)
• Elke subqueue kan verschillende time quantums hebben. (of zelfs een ander scheduling algorithm)
  • Als een process niet klaar is in de time quantum van zijn queue, kan deze worden verplaatst naar een queue met een hogere time quantum.
    • Natuurlijk wordt de voortgang van een process bewaart tussen het wisselen van queues.