Scheduling della CPU e dei processi

Scheduling della CPU

• Il multitasking e il time sharing mirano a massimizzare l'utilizzo della CPU.
• Per questo, il progettista del sistema operativo (SO) deve stabilire delle regole per decidere, quando un processo lascia la CPU, quale sarà il prossimo processo da eseguire.
• L'insieme di queste regole e la loro applicazione pratica è chiamato Scheduling della CPU.

Fasi di elaborazione e di I/O

• Nella vita di un processo si alternano fasi di uso della CPU (burst di CPU) e fasi di attesa per il completamento di operazioni di I/O (Burst di I/O).
• Distinzione fra:
  • Processi CPU-bound: utilizzano molto la CPU e poco i dispositivi di I/O (es. compilatore).
  • Processi I/O-bound: utilizzano poco la CPU e molto i dispositivi di I/O (es. editor di testo, browser).

Lo scheduler della CPU

• Lo scheduler è il modulo del SO che decide a quale processo assegnare la CPU quando un processo la rilascia.
• Questa operazione è detta Scheduling della CPU.

Scheduling con e senza prelazione

• 1. Il processo che sta usando la CPU passa volontariamente dallo stato di running allo stato di waiting (ad esempio per compiere una operazione di I/O).
• 2. Il processo che sta usando la CPU termina.
• In questi casi, lo scheduler deve prendere un processo dalla coda di ready e mandarlo in esecuzione per evitare che la CPU resti inattiva.
• Uno scheduler che interviene in questi casi è sufficiente per il multi-tasking.
• Se un programma contiene un ciclo infinito, il SO deve poter intervenire per evitare che blocchi permanentemente la CPU.
• 3. Il processo che usa la CPU viene costretto a passare dallo stato di running allo stato di ready. Questo passaggio non è volontario. Nei sistemi time-sharing, il SO mantiene il controllo del sistema per evitare situazioni problematiche.

Criteri di Scheduling

• Massimizzare l'utilizzo della CPU nell'unità di tempo (dipenderà dal carico).
• Massimizzare il Throughput, ovvero la produttività del sistema (numero di processi completati in un dato intervallo di tempo).
• Minimizzare il Tempo di risposta, che è il tempo che intercorre tra l'avvio di un processo e il suo effettivo inizio di esecuzione (importante per i sistemi interattivi).
• Minimizzare il Turnaround time, ovvero il tempo totale di esecuzione di un processo (dal momento in cui entra nella coda di ready fino al termine).
• Minimizzare il waiting time, ossia il tempo di attesa complessivo di ciascun processo nella coda di ready. Il processo è pronto ad eseguire il suo codice, ma la CPU è occupata da un altro processo.

Algoritmi di Scheduling

• First Come, First Served (FCFS): I processi vengono elaborati secondo l'ordine di arrivo.
• Shortest Job First (SJF): Il processo con il tempo di esecuzione più breve viene elaborato per primo. SJF può essere preemptive o non preemptive.
• Priority Scheduling: I processi vengono elaborati in base alla loro priorità. SJF è un tipo di scheduling a priorità. La durata del prossimo burst di tempo è la priorità. FCFS è anche un tipo di scheduling a priorità (in questo caso, la priorità è l'ordine di arrivo).
• Round Robin (RR): I processi vengono elaborati con un quanto di tempo (intervallo di tempo di esecuzione). Se un processo non termina nel quanto, viene spostato in fondo alla coda di ready.
• Multilevel Queue: La coda di ready è suddivisa in più code (foreground, background, batch), ciascuna con la sua politica di scheduling.
• Multilevel Feedback Queue: Simile a Multilevel Queue, ma i processi possono cambiare coda durante la loro esecuzione in base al loro comportamento.

Il Dispatcher

• Lo scheduler ha il compito di scegliere il processo a cui assegnare la CPU.
• Il dispatcher è un altro modulo del SO che effettua l'operazione di context switch.
• Eseguire il passaggio del sistema in user mode.
• Posizionare il PC della CPU nella corretta locazione del programma da far ripartire.

Scheduling a code multiple (Multi-level Queue)

• Se i processi possono essere divisi in categorie come foreground (interattivi), background (non interattivi), batch (la cui esecuzione può essere differita), si può suddividere la ready queue in più code.
• Ogni coda può avere la sua politica di scheduling appropriata per le proprietà dei processi in essa contenuti.

Scheduling a code multilivello con retroazione (MFQS)

• È uno schema di scheduling più flessibile, in cui i processi possono essere spostati da una coda all'altra in base al loro comportamento.

Scheduling per sistemi multi-core

• Le architetture multi-core sono comuni.
• Ogni core ha il suo scheduler.
• I processi ready to run possono essere inseriti in una coda unica, oppure in code separate per ciascun core.
• Un aspetto importante è la gestione del bilanciamento del carico sui diversi core.
• I SO moderni spesso usano code separate, richiedendo quindi un meccanismo di bilanciamento del carico. Ad esempio, Linux SMP attiva il suo proprio meccanismo di bilanciamento del carico ogni 200 millisecondi, svuotando la coda di un core quando è inattivo e mandando un processo dalla coda comune (unica) a quello specifico core.

Esempi di sistemi operativi (Solaris, Windows, Linux)

• Sono descritti diversi schemi di scheduling usati in sistemi operativi come Solaris, Windows e Linux, che includono il concetto di priorità, la gestione delle code, e la retroazione per regolare il comportamento del sistema operativo.

Valutazione degli algoritmi di scheduling

• Vengono descritti metodi per valutare la prestazione di diversi algoritmi di scheduling.