5.4 & 5.5 - Thread Scheduling & Multiprocessor Scheduling (p.209, 211)

Thread Scheduling

• Kernel threads worden door het OS zelf gescheduled.
• User threads worden via een kernel-level thread gescheduled.
  • Dit kan worden gedaan via een Lightweight Process (LWP)
  • In essentie is dit een scheduler van de threads in een kernel thread in het OS.
• Process Contention Scope = Competitie voor CPU tijd tussen threads van hetzelfde process.
  • Voor Many-to-One en Many-to-Many models (zie H4, Multithreading Models).
  • Meestal gaat het thread met het hoogste prioriteit voor.
  • Huidige thread gaat voor een thread met een hogere prioriteit.
  • Gebruikt door Linux/Windows XP
• System Contention Scope = Competitie voor CPU tijd tussen ALLE threads in het OS.
  • Voor One-to-One models.

Multiprocessor Scheduling

• Load Sharing = Verdelen van werk over meerdere processoren.
• Push migration = Het weggeven van een process op een drukke processor naar een rustige processor.
• Pull migration = Het aantrekken van een process op een rustige processor van een drukke processor.
• Homogeneous processors = Identieke processoren qua functionaliteit.
• Asymmetric multiprocessing = Processoren die verschillen in wat ze uitvoeren (ex. een processor voert alleen user code uit oa).
• Symmetric multiprocessing (SMP) = Elke processor voert zijn eigen scheduling uit.
  • Kan via een gedeelde ready queue, of een ready queue voor elk processor.
  • Geimplementeerd in meeste nieuwe OSen.
• Processor affinity = Hoe graag een process wil blijven in dezelfde processor.
  • Migreren tussen processoren kan een zware taak zijn voor het systeem, omdat de caches opnieuw moeten worden gebouwd ¹.
  • De main-memory architectuur van het systeem kan de processor affiniteit vermakkelijken of vermoeilijken.
    • Het kan zijn dat een processor sneller bij een gedeelte van het geheugen kan komen dan een andere processor.
• Soft affinity = Wanneer een OS in de regel probeert om de processen op dezelfde processor te houden, wanneer dat gewenst is door een process.
• Hard affinity = Wanneer een OS zorgt dat de processen op dezelfde processor worden gehouden, wanneer dat gewenst is door een process.
• Processor Sets = (solaris) Lijst van welke processen op welke processoren mogen worden uitgevoerd.
• Multicode processor = Meerdere processoren op dezelfde fysieke chip.
• Memory stall = Het wachten van de processor totdat het benodigde geheugen beschikbaar komt.
• Coarse-grained multithreading = Een thread wordt uitgevoerd tot een long-latency (lang durend) event als een memory stall voorkomt.
  • Hierdoor wisselt de processor van thread, wat heel kostbaar is omdat de processing pipeline moet worden geleegd en opnieuw geladen.
• Fine-grained multithreading (interleaved) = Betere wisseling tussen threads door te wisselen aan het einde van een instructie-cyclus.
  • Ook is er vaak logica voor deze threadwissel, wat de kosten van deze actie omlaag brengt.
• Virtualisatie deelt de processor vaak nog verder op (1 core wordt 4 cores oa) waardoor scheduling nog inefficienter wordt.

¹. Er wordt gepraat over de cache per processor of core. Bij een wissel moet er dus opnieuw allerlei cache misses worden verholpen. ↩