Proportional Share Scheduling (Fair Sharing)

---

🎯 Was ist Proportional Share Scheduling?

• Prozesse bekommen CPU-Zeit basierend auf einer Gewichtung.
• Lotteriescheduling: Jeder Prozess bekommt Lose, mehr Lose = höhere Wahrscheinlichkeit zu laufen.
• Stridescheduling: Prozesse haben eine Schrittweite (Stride) → Der Prozess mit dem kleinsten "Passwert" läuft zuerst.

📌 Lotteriescheduling

• Jeder Prozess erhält Lose, dann wird zufällig gezogen.
• Fair: Über lange Zeit bekommt jeder ungefähr die richtige CPU-Zeit.

🔍 Pseudo-Code

while True:
    winner = random.choice(processes)  # Zufällige Auswahl
    execute(winner)

---

📌 Stridescheduling

• Prozesse haben eine Schrittweite → Kleinerer Stride bedeutet, häufiger laufen.
• Ein Prozess mit 50% CPU-Zeit bekommt doppelt so große Schritte wie einer mit 25%.

🔍 Pseudo-Code

while True:
    process = min(queue, key=lambda p: p.pass_value)
    execute(process)
    process.pass_value += process.stride

---

🔄 Multiprozessor-Scheduling

🎯 Problemstellung

• Wie plant man Jobs auf mehreren CPUs?
• Kann ein Prozess von einer CPU zur anderen wechseln?
• Wie verhindert man Lastungleichgewicht?

📌 Single Queue Scheduling

• Eine Warteschlange für alle CPUs.
• Problem: Hoher Synchronisationsaufwand.

---

📌 Multi-Queue Multiprozessor Scheduling (MQMS)

• Jeder CPU-Kern bekommt eigene Warteschlange.
• Geringere Synchronisationskosten als Single Queue.
• Problem: Lastungleichgewicht → Eine CPU könnte überlastet sein.

🔍 Pseudo-Code

while True:
    process = local_queue.pop(0)
    execute(process)
    if queue_empty:
        steal_work()

![[multiprocessor_scheduling.svg]]

---

📌 Load Balancing (Work Stealing)

• Falls eine CPU nichts zu tun hat, klaut sie Prozesse von einer anderen CPU.

🔍 Pseudo-Code

if local_queue.empty():
    target_cpu = find_busy_cpu()
    steal_process(target_cpu)

---

📌 Linux Multiprozessor Scheduling

Linux verwendet mehrere Algorithmen für Multiprozessor-Systeme:

• O(1) Scheduler: Skalierbarer Scheduler mit mehreren Warteschlangen.
• Completely Fair Scheduler (CFS): Basiert auf virtueller Zeit → Fairer als klassische Algorithmen.
• Load Balancer: Verteilt Prozesse dynamisch zwischen CPUs.

![[linux_sched.svg]]

---

🏆 Fazit

1. Einzel-CPU-Scheduling:
   • FIFO, SJF, RR, MLFQ → Jede hat Vor- und Nachteile.
2. Fairness:
   • Proportional Share Scheduling (Lotterie, Stride).
3. Multiprozessor-Scheduling:
   • Single Queue: Einfach, aber Synchronisationsprobleme.
   • Multi-Queue: Weniger Overhead, aber schwieriger zu balancieren.
   • Work Stealing: Dynamische Lastverteilung.
4. Linux Scheduling:
   • Kombination aus prioritätsbasiertem Scheduling und Lastverteilung.