Vai al contenuto
Home » Notes » Appunti di Sistemi Operativi: CPU Scheduling

Appunti di Sistemi Operativi: CPU Scheduling

copertina appunti sistemi operativi cpu scheduling

Raccolta di Riassunti e Appunti di Sistemi Operativi, sotto forma di domande e risposte sugli argomenti di CPU Scheduling (scheduling del processore), algoritmi di scheduling.
Fonti: il mio libro di Sistemi Operativi Operating System Concepts with Java, di Silberschatz, Galvin e Gagne.

Appunti Riassunto Sistemi Operativi

Capitolo CPU Scheduling (Scheduling del processore)

Cos’è un algoritmo di CPU scheduling? Cosa deve cercare di ottimizzare?

Un algoritmo di CPU scheduling è un algoritmo per decidere in che ordine eseguire o allocare alla CPU i processi che sono in ready-queue (in coda d’attesa). L’obiettivo principale di un algoritmo di CPU scheduling è ottimizzare il tempo medio di attesa dei processi, anche average waiting time, massimizzando l’utilizzo della CPU per migliorare la produttività di sistema e assicurare all’utente le migliori performance del calcolatore, con una esperienza d’uso più fluida e reattiva.

Come funziona l’algoritmo di Shortest Job First (SJF)?

L’algoritmo SJF è un algoritmo di scheduling che associa ad ogni processo un valore di CPU burst time che riguarda la lunghezza della successiva sequenza di operazioni della CPU. Quando la CPU è disponibile, viene allocato il processo con il CPU burst time minore. Si può dimostrare che l’algoritmo SJF sia un algoritmo ottimale, ovvero in grado di produrre il tempo medio di attesa minore (average waiting time per processo).

Che svantaggi ha l’algoritmo SJF (Shortest Job First) e come si può approssimare?

Lo svantaggio principale dell’algoritmo SJF è che non è possibile realizzarlo concretamente a livello dello scheduling della CPU, perché non esiste alcun modo per conoscere la lunghezza della successiva sequenza di operazioni della CPU.
Possiamo predire questo valore sapendo che dovrebbe essere simile alle CPU bursts precedenti (media esponenziale). Con questa approssimazione è possibile usare un algoritmo SJF a burst time approssimati. L’algoritmo SJF può essere con prelazione: in questo caso l’algoritmo sostituisce il processo in esecuzione con uno appena arrivato se il CPU burst time è minore (shortest remaining time first) ,oppure senza prelazione: in quest’altro caso il processo attualmente in esecuzione termina indipendentemente dall’arrivo di altri processi con CPU bursts più brevi.

Per il CPU scheduling, supponiamo che un certo insieme di processi debba essere trattato con la politica Shortest Job First (SJF) non preemptive. Esiste un assegnamento di priorità ai processi in modo che la loro esecuzione con la politica a priorità produca esattamente la stessa sequenza di esecuzione? Se sì, come?

Un assegnamento di priorità possibile è quello di assegnare ad ogni processo la priorità come inverso del suo CPU burst. In questo modo, i processi con il minor CPU burst hanno priorità più alta, e i processi con il maggior CPU burst hanno la priorità più bassa: così facendo, l’algoritmo andrà ad eseguirli in accordo con la politica a priorità e la sequenza di esecuzione sarà esattamente uguale al SJF.

Cos’è algoritmo di Round Robin e come funziona? Quali sono i vantaggi principali della politica di scheduling Round Robin (RR)?

L’algoritmo di Round Robin, abbreviato RR, è un algoritmo di CPU scheduling che tratta la ready queue come una coda circolare.
Ad ogni quanto (quantum) di tempo prestabilito, l’algoritmo sospende il processo in esecuzione in quel momento sul processore, lo inserisce alla fine della ready queue e alloca la CPU al processo successivo. Al termine del quanto di tempo successivo, ripete l’operazione. Se un processo ha CPU burst time inferiore al quanto di tempo, allora rilascerà volontariamente la CPU e lo scheduler passerà al processo successivo. I nuovi processi che sopraggiungono vengono ovviamente inseriti a loro volta in coda della ready queue. I vantaggi di questo algoritmo sono la reattività generale del sistema e l’impossibilità di starvation.

Cosa è il principio di località dei programmi? Date 2 esempi in cui durante il corso questo principio è stato evocato per giustificare certe scelte in ambito di Sistemi Operativi o di hardware sottostante

[Il principio di località è un principio secondo cui è altamente probabile che i dati che serviranno a un processo nel breve futuro si trovino in indirizzi vicini a quelli che si stanno usando in questo momento.]

Il principio di località è un principio secondo cui le istruzioni e i dati che il processo utilizza in un certo periodo di tempo (working set) sono molto simili e vicini in memoria a quelli utilizzati nel periodo precedente e successivo, perché il working set cambia nel tempo, ma molto lentamente.

Il principio di località è molto importante nei Sistemi Operativi, sia a livello HW che SW.
Lista esempi applicazioni del principio di località:

1) La TLB, nei sistemi moderni, ha la capacità di offrire una hit ratio molto alta (anche >90%) perché in TLB sono caricati dati fisicamente limitrofi a quelli attualmente in uso e, per il principio di località, saranno molto probabilmente proprio quei dati a servire nelle prossime istruzioni dei programmi;

2) Nel page replacement è un esempio di principio di località l’algoritmo che rimuove la pagina inutilizzata da più tempo (LRU). Questo perché rimuovere una pagina utilizzata di recente potrebbe portare, per il principio di località, al fatto di aver di nuovo necessità di quella stessa pagina nel breve futuro e quindi alla generazione di un altro page fault se la si rimuovesse;

3) Quando si esegue un programma si carica in cache la prima istruzione e quelle limitrofe proprio perché, per il principio di località, dovrebbero essere proprio quei dati a servirti durante l’esecuzione del processo stesso. Ha senso quindi spendere un po’ di tempo per portare dati e istruzioni del working set in una memoria di livello più veloce perché questo tempo sarà compensato dalla maggior velocità di accesso della cache. In particolare, quando quei dati mi serviranno impiegherò meno tempo a recuperarli dalla cache rispetto a raggiungere ogni volta una memoria più lenta.

4) L’algoritmo ottimale di scheduling della CPU è SJF, che non possiamo implementare in quanto solo teorico. Una buona approssimazione è data però grazie al principio di località che ci permette di stimare come il CPU burst dei prossimi processi in arrivo sia più o meno simile a quello del processo attualmente in esecuzione.

Cosa indica la “starvation” di un processo?  Può esserci con RR? SJF? Priorità?

Per starvation indichiamo il fenomeno in cui un processo in una ready queue non ha mai la possibilità di essere allocato al processore ed essere eseguito, rimanendo quindi in un’attesa indefinita.

Non può esserci con RoundRobin: l’algoritmo di RR tratta la ready queue come una coda circolare e ad ogni quanto di tempo prestabilito l’algoritmo sospende il processo di esecuzione e alloca la CPU al processo successivo (qualora disponibile). In questo modo si evita starvation perché nessun processo rischia di essere posticipato indefinitivamente.

Nell’algoritmo di SJF può invece esserci starvation: lo SJF alloca la CPU al processo che ha il CPU burst time minore e procede in ordine crescente. Qualora un processo A avesse un grande CPU burst time, e continuassero a sopraggiungere processi con burst time minore, il processo A sarà posticipato per un tempo indefinito.
Anche nell’algoritmo di Priority Scheduling (priorità) può esserci rischio di starvation. L’algoritmo alloca la CPU ai processi con priorità maggiore e, qualora continuassero a sopraggiungere processi ad alta priorità, qualche processo a bassa priorità potrebbe rimanere in sospeso e non essere eseguito per un tempo indefinito. In questo caso possiamo risolvere il problema del rischio di starvation con una tecnica detta aging, che consiste nell’aumentare la priorità di un processo a mano a mano che trascorre tempo in coda.

L’algoritmo SJF pre emptive garantisce che un processo che arriva in coda di ready prima o poi riesca ad usare la CPU?

L’algoritmo SJF, sia preemptive che non preemptive, soffre del rischio di starvation. Un processo con burst time grande potrebbe vedere la sua esecuzione posticipata indefinitivamente dall’arrivo di processi con burst time più piccoli e a quelli, quindi, viene allocata per prima la CPU. Il risultato è una attesa di tempo indefinito del processo con burst time grande.

In una politica di CPU scheduling a priorità, qual è il problema principale? Perché nei SO moderni la politica di RR è quella più diffusa per gestire processi utente?

Il problema principale di una politica di CPU scheduling a priorità è il rischio di starvation. Un processo con una priorità bassa potrebbe essere sempre posticipato favorendo processi a priorità più alta, e attendere un tempo indefinito senza entrare mai in esecuzione.

L’algoritmo di Round Robin è il più diffuso per gestire i processi utente nei sistemi odierni perché il meccanismo del quanto di tempo permette all’algoritmo di rendere il sistema molto più reattivo di altri algoritmi. In parole povere il fatto di alternare sempre i processi ogni quanto di tempo ti dà più l’impressione che molte cose stiano avvenendo contemporaneamente nel pc.

Cosa sono e perché si usano le multilevel queue?

Con multilevel queue si intende una suddivisione dei processi in ready-queue in diverse code di attesa, differenziate in base al tipo del processo. L’obiettivo è quello di separare i processi di sistema, dai processi utente interattivi, dai processi in background perché questi processi hanno diversi tempi di risposta accettabili.

Qual è la differenza tra un algoritmo di tipo preemptive e uno non-preemptive (cioè con o senza prelazione)?

La differenza fondamentale è che in un algoritmo di tipo non preemptive, una volta che la CPU è stata allocata a un processo, quel processo mantiene la CPU finchè non finisce o non va in stato waiting. Un algoritmo di tipo preemptive, invece, permette di sospendere l’esecuzione di un processo anche se non è terminata effettuando un context switch e allocando la CPU ad un altro processo

Cos’è il waiting time medio?

Il Waiting Time medio, detto anche average waiting time, è il tempo medio di attesa di una sequenza di processi che devono entrare in esecuzione sulla CPU, dato un algoritmo di scheduling.

Qual è il principale pregio di SJF? E il principale difetto?

SJF è un algoritmo che alloca la CPU ai processi che in ready queue hanno il CPU burst time minore. Il principale vantaggio dell’algoritmo di SJF è che è matematicamente dimostrato come l’algoritmo ottimale, ovvero quello in grado di offrire sempre il minor waiting time ai processi in coda. Lo svantaggio principale è che l’implementazione di SJF richiede di conoscere il cpu burst time di tutti i processi, che si può sapere con precisione solo conoscendo il futuro, quindi è di difficile implementazione. Esistono, però, approssimazioni di questo algoritmo basate sul principio che il CPU burst time del processo successivo è simile a quello del processo precedente.

All’interno di un SO, un certo processo P è correntemente in stato di “Ready” e si sa che, una volta acquisita la CPU, non dovrà più rilasciarla volontariamente prima di aver terminato la propria esecuzione (cioè non dovrà più eseguire operazioni I/O, di sincronizzazione o di comunicazione con altri processi). Quali tra gli algoritmi di scheduling FCFS, SJF pre-emptive e non pre-emptive, RR garantiscono che il processo P riuscirà a portare a termine la propria computazione?

SJF nelle sue due varianti preemptive e non preemptive non garantisce contro il rischio di starvation, quindi non è detto che P riuscirà a portare a termine la sua esecuzione.

FCFS è un algoritmo estremamente banale, che può causare cali di reattività del sistema ma che garantisce che i processi siano eseguiti nell’ordine in cui arrivano nella ready queue, qualunque sia il loro eventuale burst time o la loro priorità, quindi sicuramente garantisce che il processo P porti a termine la computazione.

Round Robin allo stesso modo garantisce che il processo P arrivi a termine, in quanto gestisce la coda allocando la CPU al processo successivo ogni quanto di tempo. È chiaro, quindi, che prima o poi arriverà il turno del processo P.

Cos’è l’algoritmo di CPU schedulling FIFO, FCFS o First Come First Served?

L’algoritmo FCFS è uno degli algoritmi più semplici di CPU scheduling, consiste nell’eseguire il primo processo che giunge in ready queue, poi, al suo termine, caricare il processo che successivamente si è presentato in ready queue e così via.

Altri capitoli:
Struttura e architettura del Sistema operativo
Processi e Thread

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *