Linux Scheduling Classes Quiz

Introduzione allo Scheduling

• Lo scheduling è la funzione del sistema operativo che gestisce l'allocazione delle risorse, soprattutto del tempo di esecuzione, tra i diversi processi che ne fanno richiesta contemporaneamente.
• Questa risorsa viene allocata tramite lo "scheduling" (o pianificazione).

Scopo dello Scheduling

• L'obiettivo dello scheduling è assegnare ad ogni processore i processi da eseguire a mano a mano che vengono creati e distrutti.
• Questo obiettivo si raggiunge ottimizzando aspetti come il tempo di risposta, il throughput e l'efficienza del processore.

Obiettivi dello Scheduling

• Distribuire il tempo di esecuzione in modo equo (fair) tra tutti i processi, senza favoritismi.
• Gestire le priorità dei processi quando necessario, garantendo un trattamento equo tra processi con la stessa priorità, con favoritismi solo se giustificati.
• Evitare la starvation (morte per fame) dei processi.
• Usare il processore in modo efficiente.
• Minimizzare l'overhead.

Tipi di Scheduling

• Long-term scheduling (lungo termine): decide quali programmi devono essere aggiunti al sistema per essere eseguiti. Spesso segue una politica FIFO (First-In, First-Out).
• Medium-term scheduling (medio termine): gestisce l'aggiunta di processi alla memoria principale ed il loro spostamento in memoria secondaria (swap) per gestire il grado di multiprogrammazione.
• Short-term scheduling (breve termine): chiamato anche dispatcher, decide ogni qualvolta quale processo tra quelli pronti deve essere eseguito dal un processore. È chiamato frequentemente in base a diversi eventi.
• I/O scheduling (input/output): decide quale processo deve accedere a quale dispositivo I/O.

Stati dei Processi e Scheduling

• Il sistema operativo gestisce i processi attraverso diversi stati (New, Ready, Running, Blocked, Exit).
• Il medium-term scheduler gestisce anche lo spostamento dei processi tra memoria principale e secondaria.
• Le transizioni tra gli stati dei processi sono decise dai diversi scheduler.

Criteri per lo Short-Term Scheduling

• Utente contro Sistema: i criteri per lo scheduling devono considerare sia le esigenze dell'utente (tempo di risposta, visualizzazione dell'output immediato) che le prestazioni del sistema (utilizzo efficiente del processore).
• Prestazioni: i criteri legati alle prestazioni comprendono il tempo di risposta, il throughput e l'utilizzo del processore, tutti quantitativi e misurabili.
• Non Prestazioni: i criteri legati a fattori qualitativi come la predicibilità, l'equità, e il bilanciamento delle risorse, sono più complessi da misurare.

Criteri Utente per lo Short-Term Scheduling

• Tempo di ritorno (Turnaround time): il tempo totale trascorso dalla creazione di un processo fino al suo completo completamento.
• Tempo di risposta (Response time): il tempo trascorso dalla richiesta di un processo fino all'inizio della sua risposta (utile per processi interattivi).
• Scadenza (Deadline): il tempo massimo consentito per l'esecuzione di un processo.
• Predicibilità: la capacità di prevedere i tempi di risposta dei processi.

Criteri di Sistema per lo Short-Term Scheduling

• Throughput: il volume di lavoro completato in un determinato periodo di tempo.
• Utilizzo del processore (processor utilization): la percentuale di tempo in cui il processore è utilizzato.
• Equità (Fairness): garantire un uso equo delle risorse del sistema a tutti i processi.
• Gestione delle priorità (Enforcing priorities): assegnare priorità a processi diversi e garantire che le priorità vengano rispettate.
• Bilanciamento delle risorse (Balancing resources): bilanciare l'utilizzo delle risorse a disposizione tra i processi.

Turnaround Time

• Il tempo tra la creazione (sottomissione) di un processo e il suo completo completamento.
• Include le attese dovute alle operazioni I/O e all'utilizzo del processore.
• Utile per i processi batch (non interattivi).

Response Time

• Tempo tra la richiesta di un processo e l'inizio della sua risposta.
• Considerato per i processi interattivi.
• I processi interattivi devono restituire una risposta il più velocemente possibile.

Deadline e Predicibilità

• Importanza di soddisfare le scadenze, quando possibile.
• La variabilità nei tempi di risposta è accettabile a meno che il sistema sia completamente saturo.

Throughput

• Misura del volume di lavoro completato nell'unità di tempo.
• Misura quanto lavoro viene effettuato.
• Dipende dalla durata media di un processo.

Utilizzo del Processore

• Percentuale di tempo in cui il processore è effettivamente in uso.
• Lo scheduler deve minimizzare i periodi non produttivi del processore.
• Utile in sistemi costosi dove si desidera maximizzare l'utilizzo.

Bilanciamento delle risorse

• Lo scheduler deve assicurarsi che le risorse del sistema siano usate al massimo possibile.
• Favorire processi con un minore consumo di risorse.

Fairness e Priorità

• Nessun favoritismo tra processi a meno che non siano presenti priorità definite esternamente.
• Se ci sono priorità, lo scheduler deve assegnare le priorità più alte a i processi con priorità più alte.
• Se ci sono priorità, il scheduler si serve di code differenti, una per ogni livello di priorità.

Code per la Gestione delle Priorità

• Diverse code separatamente gestite per ogni livello di priorità.
• I processi in esecuzione sono prelevati dalla coda con la priorità più alta.

Priorità e Starvation

• I processi a bassa priorità possono subire starvation
• In caso di priorità, il sistema può gestire un processo con priorità alta che può causare la starvation in processi con priorità bassa

Politiche di Scheduling

• Il capitolo riporta le varie politiche di scheduling, come FCFS, Round Robin, SPN, SRT e HRRN, con le loro caratteristiche chiave (non preemptive/preemptive, utilizzo, tempo di risposta).

Funzione di Selezione

• Sceglie effettivamente il processo da mandare in esecuzione.
• Dipende da vari parametri come il tempo trascorso in attesa, il tempo passato in esecuzione e il tempo totale richiesto.
• Definisce l'istanza temporale in cui la funzione di selezione viene invocata.

Modalità di Decisione

• Può essere preemptive o non-preemptive.
• Non preemptive: se un processo sta eseguendo, viene mantenuto fino a quando non termina o richiede un'operazione I/O, o fino a quando un'altra condizione causa un'interruzione forzata.
• Preemptive: il sistema operativo può interromperlo anche se in esecuzione.

Preemptive e Non-Preemptive

• Il sistema operativo decide se un processo può essere interrotto in esecuzione.
• Preempzione utilizzata in base a nuovi processi o interrupt, per garantire un controllo più equo sull'utilizzo delle risorse.

CPU-bound vs I/O bound

• Nel round-robin, i processi CPU-bound sono avvantaggiati perché consumano l'intero quantum di tempo. I processi I/O-bound ne usano solo una parte.
• Il round-robin virtuale migliora l'equità considerando le richieste di I/O. I processi I/O-bound hanno una priorità più alta, dopo le operazioni I/O, per garantire un'esperienza utente migliore.

Round-Robin Virtuale

• È una politica specifica per l'allocazione del processore in architettura multiprocessore.
• Con un solo processore, il sistema funziona come il round-robin base, ma con più processori, per garantire l'utilizzo della CPU in diverse zone, creando code apposite per ogni tipo di I/O.

SPN: Shortest Process Next

• Seleziona il processo con il tempo di esecuzione stimato più breve tra quelli pronti.
• Politica non preemptive.
• Problema di predicibilità su tempi di esecuzione imprecisi.

SPN: Come Stimare il Tempo di Esecuzione?

• Metodi per effettuare delle previsioni sul tempo di esecuzione dei processi, come l'uso del valore medio passato.
• Si usa l'exponential averaging per evitare la perdita di informazioni e privilegiare le informazioni più recenti.

Exponential Averaging

• Metodo efficace per prevedere il futuro con informazioni passate, dando più peso alle informazioni più recenti.

SRT: Shortest Remaining Time

• Variante preemptive di SPN, che tiene conto del tempo rimanente di esecuzione.
• Interrompe i processi in esecuzione a favore di quelli con tempo rimanente più breve.

HRRN: Highest Response Ratio Next

• Prioritizza i processi basandosi su un rapporto tra il tempo di attesa e il tempo richiesto.
• Favorisce i processi che hanno atteso a lungo.

Confronto

• Confronto tra diverse politiche di scheduling in base a vari criteri.

Scheduling in Linux

• Scheduling in Linux, che combina una versione preemptive a priorità dinamica, con le caratteristiche di altre politiche.

Scheduling in Linux: Regole Generali

• Descrizione dettagliata delle regole del scheduling in Linux, inclusi i tipi di processo (Interattivi, Batch, Real-Time).

Scopri le classi di scheduling riconosciute da Linux e il range di priorità per i processi nelle classi SCHED FIFO e SCHED RR. Questo quiz esplora anche la preemption in Linux e le condizioni in cui un processo può essere soppiantato. Testa le tue conoscenze sullo scheduling in ambiente Linux.