Scheduling in Linux(Kernel 2.6)

Versioni Kernel Linux

Scheduling Kernel < 2.6

• Nelle versioni del kernel precedenti alla 2.6, lo scheduler aveva complessita’ O(n) dove n e’ il numero di task in competizione per la CPU– Per n grande scheduler inefficiente

• Nei sistemi MPU, una sola runqueue per tutti i processori:– una task poteva quindi essere eseguito in ogni processore: ok per

load balancing, ma non per gestione delle cache dei singoli processori

– un solo lock sulla runqueue: durante la scelta del processo da parte di un processore, gli altri processori rimanevano idle

Scheduling Kernel < 2.6

• Infine nello scheduler pre-2.6 non veniva applicata la preemption

– Un processo a priorita’ bassa poteva girare (fino alla scadenza del suo quanto di tempo) lasciando in attesa processi a priorita’ piu’ alta

Kernel 2.6

• Il kernel Linux utilizza usa i thread come unita’ di esecuzioneed implementa un nuovo algoritmo di scheduling rispetto alle versioni precedenti

• Lo scheduler e’ chiamato ``O(1) scheduler’’ (scritto da I. Molnar)

•A differenza dello scheduler ``O(n)’’ nelle versioni precedenti infatti opera in tempo costante O(1) indipendentemente dal numero di thread in competizione per la CPU.

• Motivazione: supportare al meglio il multithreading nella Java Virtual Machine

• Inoltre supporta in modo piu naturale sistemi multiprocessore

Scheduler Kernel 2.6

• Ogni CPU ha una runqueue chiamata active runqueu con 140 code di priorita` (liste) gestite FIFO

– Prime 100 priorita’: real time task– Ultime 40: user tarsk

• Ogni task ha a disposizione un quanto di tempo (round robin su ogni coda di priorita’)

• Inoltre ogni CPU ha una expired runqueue con la stessa struttura della active runqueue

• Quando un processo termina il suo time-slice viene rucalcolata la priorita’ e il processo viene aggiunto in coda alla lista della nuova priorita’ nella expired runqueue

• Se non ci sono task da eseguire per una certa priorita’ nella active runqueue• Si scambiano active ed expired (expired diventa la nuova active runqueue)

Scheduler

• Il compito dello scheduler e’ quindi quello di eseguire il task nella lista non vuota con maggiore priorita’

• Ad ogni priorita’ viene associata una bitmask. • Si possono utilizzare operazioni tipo bit-a-bit per

rendere l’operazione dipendente dal numero di priorita’ (bit) invece che dal numero di processi

• Questa proprieta’ rende lo scheduler 2.6 un programma con complessita’ O(1).

Active ed expired runqueue

Altre caratteristiche

• Lo scheduler 2.6 permette la preemption dei task a minor priorita’

• Il calcolo dinamico delle priorita’ (in base all’uso della CPU e di operazioni di I/O) evita starvation

• Ogni runqueue ha un lock separato lockper sfruttare al meglio un sistema multiprocessore (lo scheduler su una CPU non blocca lo scheduler sulle altre)

• Inoltre utilizza tecniche di load balancing (es. ogni 200ms controlla il carico e se necessario sposta processi dalla runqueue di un processore ad un’altra)