Sistemi Operativi: Fork() ed Exec(), Algoritmi di scheduling dei processi, Semafori

ROUND-ROBIN

Simile allo scheduling FCFS ma con l'aggiunta del timesharing, ossia ad ogni processo viene assegnato un quanto di tempo della CPU (time slice, es 10-100 ms), ogni processo ha uguale priorità di esecuzione. Il scheduler della CPU scorre la ready queue (la quale è con diritto di prelazione, ossia preemtive), la quale viene trattata come una coda circolare, assegnando la CPU a ciascun processo per un intervallo di tempo della durata massima di un quanto di tempo.

Due situazioni:

1. Il processo ha una sequenza di istruzioni più breve del time slice e quindi rilascia spontaneamente la CPU consentendo al processo in testa alla coda di impadronirsi della CPU.
2. La durata della sequenza di istruzioni è maggiore del quanto di tempo che il processo ha a disposizione e quindi al termine del time slice il timer scade e invia un segnale di interrupt al SO (la CPU viene sottratta al processo che viene reinserito in fondo alla ready queue).

L'efficienza

dell'algoritmo è chiaramente legata alla durata del time slice. Un time slice troppo corto implica un elevato numero di context switch, mentre un time slice lungo rischia di far degenerare l'algoritmo in un FCFS. In generale basta che il time slice sia ampio rispetto al tempo richiesto per effettuare il context switch (negli algoritmi precedenti era trascurabile, qui non più). PRIORITÀ: Ogni processo viene dotato di una certa priorità, dunque i processi a priorità maggiore avranno la precedenza nell'utilizzo della CPU rispetto a quelli a priorità inferiore. A parità di priorità, i processi vengono ordinati secondo l'algoritmo FCFS. Per evitare che processi con una priorità alta vengano eseguiti indefinitamente, durante la loro esecuzione, a ogni interrupt del clock, la loro priorità viene decrementata. Avviene un context switch quando la priorità del processo in esecuzione diventa più bassa di

quella del processo con più alta priorità nella ready queue.

CODE MULTILIVELLO: I processi vengono suddivisi in code distinte (adesempio i processi in background {batch }verranno separati da quelli inforeground {interattivi}) con diversi livelli di priorità, e ciascuna sarà gestitacon un proprio algoritmo di scheduling.

Lo scheduling tra le code è invece solitamente uno scheduling a priorità fissacon prelazione, dove ogni coda ha una sua percentuale di utilizzo della CPU,che viene poi a sua volta suddivisa tra i processi di ogni coda. I processi siassegnano in modo permanente a una coda.

CODE MULTILIVELLO CON RETROAZIONE: in questa situazione, la classe dipriorità alla quale un processo viene assegnato non è permanente, ma puòvariare.All’ingresso nella ready queue i processi che vengono assegnati alla prima codaottengono un quanto di tempo, mentre quelli assegnati alla seconda neottengono due, quelli assegnati alla

terza ne ottengono quattro, e così via. I processi che non terminano la propria sequenza di istruzioni entro il time slice che gli è stato concesso vengono spostati alla fine della coda di livello inferiore. Con questo metodo i processi lunghi scendono nelle code a priorità bassa per dare la precedenza all'esecuzione di processi interattivi brevi. GARANTITO: la promessa è che se ci sono n utenti connessi, ogni utente riceverà 1/n della potenza di CPU. Per poter mantenere la promessa, il sistema calcola la priorità in base al rapporto tra il tempo di CPU effettivamente usato da un utente ed il tempo che gli sarebbe spettato. L'algoritmo privilegia l'esecuzione di quei processi che rischiano maggiormente di non rispettare le scadenze. A LOTTERIA: Ad ogni processo vengono assegnati dei biglietti della lotteria (che rappresentano del tempo di CPU) e il processo a cui viene assegnata la