SISTEMI OPERATIVI
Gestione dei processi
Domande di verifica
2007
Luca Orrù Centro Multimediale Montiferru 13/05/2007
Gestione dei processi
1. Qual è la differenza tra un programma e un processo?
Un programma descrive un algoritmo ed è una entità statica. Un processo invece è un programma in esecuzione. Un processo è quindi una entità dinamica. Possiamo pensare ad un processo come una sequenza di stati attraverso il quale evolve il sistema di elaborazione durante l’esecuzione di un programma. Ad un programma possono essere associati più processi. Infatti se si cambiano i dati in ingresso al programma, allora la sequenza delle istruzioni e di conseguenza la sequenza degli stati attraverso il quale evolve il sistema, potrà essere differente. Il flusso di esecuzione cambia ovvero il processo è diverso. Esempio:
supponiamo di avere un programma in cui vi è ad un certo punto un’istruzione if then else.
Con determinati dati in ingresso, per esempio viene eseguito il ramo then, mentre cambiando i dati in ingresso viene eseguito il ramo else. Si hanno due processi diversi. Ciascun processo associato ad un programma costituisce un’istanza del programma
2. Si disegni e si descriva il diagramma degli stati di un processo (solo per la parte CPU-RAM) per un sistema operativo multiprogrammato e time- sharing (esame 19-12-2003)
Per descrivere gli stati in cui si può trovare un processo possiamo fare riferimento ad un sistema con una sola CPU (sistema monoprocessore). In questo caso i processi entreranno in competizione per l’utilizzo della risorsa CPU. Un solo processo alla volta può usare l’unità di
elaborazione. Il processo che sta usando la CPU si trova in stato di esecuzione. Un processo che si trova in stato di esecuzione può transitare nello stato di terminato, nello stato di pronto oppure nello stato di bloccato. Il processo passa in stato di terminato se ha completato la sua attività (ha eseguito l’ultima istruzione del suo codice ) oppure se chiama un’apposita system call. Nel sistema UNIX un processo può terminare volontariamente la propria esecuzione chiamando la system call exit. In realtà in UNIX vi è uno stato intermedio tra lo stato di terminato e lo stato di esecuzione (stato zombie). Quando un processo invoca la system call exit, esso passa dallo stato di esecuzione allo stato zombie e rimane in questo stato finchè il padre non né rileva lo stato di terminazione.
Il passaggio in stato di terminato può anche essere dovuto ad una terminazione forzata. Il sistema operativo può forzare la terminazione di un processo quando il processo tenta di eseguire un accesso ad una area di memoria che non gli appartiene (superamento dei limiti imposti dai registri di frontiera, registro base e registro limite) oppure perché il processo ha tentato l’esecuzione di un’ istruzione illegale (istruzione eseguibile solo in modo kernel) oppure per effetto della ricezione di un segnale (esempio in UNIX i segnali SIGKILL e SIGSTOP).
La transizione dallo stato di esecuzione (running) allo stato di pronto (ready) può avvenire per i seguenti motivi:
• in un sistema a divisione di tempo, se il processo in esecuzione termina il suo quanto di tempo, il sistema operativo lo sostituisce con un altro processo pronto, scelto dalla coda dei processi pronti attraverso un opportuno algoritmo di scheduling,
implementato dal sistema operativo.
• In un sistema in cui la CPU viene assegnata in base alla priorità dei processi, durante la sua esecuzione un processo, che è quello a priorità più alta tra tutti i processi pronti, potrebbe svegliare un processo a priorità più alta della sua. In questo caso il sistema operativo revoca l’uso della CPU al processo in esecuzione e l’assegna al processo risvegliato.
Il passaggio dallo stato di pronto allo stato di esecuzione avviene quando al processo in esecuzione viene revocata la CPU e quindi il sistema operativo sceglie dalla coda dei processi pronti il nuovo processo da mandare in esecuzione. Un processo si dice che è in stato di pronto in quanto potrebbe essere eseguito ma deve attendere perché la CPU è in uso da un altro processo. Un altro stato possibile è lo stato nuovo.
Un processo appena creato si trova in stato nuovo e passa in stato di pronto quando il sistema operativo decide che esso può competere per l’uso della CPU e quindi può essere mandato in esecuzione.
La transizione di stato esecuzione-bloccato avviene quando un processo, per esempio, invoca una operazione di I/O. In questo caso, non potendo proseguire la sua esecuzione, il processo viene sospeso in attesa che l’operazione richiesta venga completata. Quando l’operazione richiesta è completata (si è verificato l’evento atteso ) il processo viene risvegliato ed è nuovamente pronto per l’esecuzione ma deve attendere che venga scelto dalla coda dei processi pronti. Un processo può passare in stato di bloccato anche perché attende di ricevere un segnale di sincronizzazione da un altro processo.
Per esempio, nel sistema UNIX la sincronizzazione tra padre e figlio prevede che ogni processo padre possa sospendersi (attraverso la system call wait) in attesa della terminazione del processo figlio. Il padre rimane in stato di bloccato finché il figlio non termina e gli passa il suo stato di terminazione, terminazione volontaria oppure involontaria. Il figlio può passare il suo stato di terminazione al padre mediante la system call exit.
3.
Si disegni e si descriva il diagramma degli stati completo
(CPU-memoria-memoria virtuale) di un processo. (esame 12-01-2005)
Rispetto al diagramma degli stati CPU-RAM sono presenti i due stati di swapped (pronto swapped e bloccato swapped). Questi due stati sono gli stati di pronto e bloccato su disco.
In molti sistemi è possibile trasferire un processo presente in memoria principale in memoria secondaria (disco) per liberare spazio su RAM per gli altri processi. L’operazione prende il nome di swapping. Un processo si trasporta in memoria secondaria soprattutto per motivi di efficienza. Infatti, un processo che è bloccato su RAM è in attesa di qualche evento e quindi non può usare la CPU per cui viene trasferito su disco tramite una operazione di swap-out.
Quando il processo viene riattivato, perché si è verificato l’evento che attendeva, passa in stato di pronto su disco (pronto swapped). Quando è in pronto su disco può passare in stato pronto su RAM (operazione di swap-in) e da pronto su RAM può passare in stato di pronto swapped (operazione di swap-out).
Tutti gli altri stati e le relative transizioni di stato sono identiche al caso CPU RAM:
• esecuzione: il processo sta usando la CPU.
• pronto: il processo potrebbe essere eseguito ma la CPU è occupata da un altro processo e quindi il processo attende che la CPU venga liberata.
• bloccato: il processo è in attesa del verificarsi di un evento esterno che lo risvegli.
• Terminato: il processo ha concluso la sua esecuzione
• Nuovo: il processo è stato appena creato
sospensione Revoca
CPU creazione
Swap- out
Segnale di riattivazione esecuzione
pronto bloccato
terminato
Bloccato swapped Nuovo
Pronto swapped
terminazione
Assegnazione CPU
Swap-out
Segnale di riattivazione Swap-in
4. Descrivere gli stati di un processo UNIX (esame 21-03-2003)
Il sistema operativo UNIX è un sistema operativo time-sharing vale a dire che la CPU viene assegnata ai processi solo per un time slice e poi viene revocata. Il diagramma degli stati è analogo al diagramma degli stati generale visto nella domanda 3. E’ presente però un nuovo stato: lo stato zombie. Questo è lo stato in cui si trova un processo che ha terminato la sua esecuzione ma è in attesa che il processo padre ne rilevi lo stato di terminazione. Esso uscirà dallo stato zombie, per passare in stato di terminato, quando il padre avrà raccolto il suo stato di terminazione oppure quando il padre termina la sua esecuzione.
Lo stato di esecuzione (running) è stato in questo diagramma diviso in due parti: esecuzione di un processo in modo utente ed esecuzione di un processo in modo kernel. Il passaggio running user-mode-running kernel-mode si verifica quando il processo in esecuzione genera una chiamata di sistema (system call) oppure per effetto di un interrupt che richiede l’intervento del kernel. Il passaggio inverso si ha quando viene eseguita l’istruzione IRET (interrupt return) che indica la conclusione della routine di servizio associata alla system call o all’interrupt. Un processo che si trova in stato running kernel mode, se riceve un segnale di interrupt (INT), rimane in stato kernel mode per processare l’interrupt.
Un processo può passare dallo stato running kernel-mode allo stato bloccato per effetto della chiamata di sistema wait che sospende il processo in esecuzione in attesa di un evento che lo risvegli.
Un processo che si trova in esecuzione può subire la revoca della CPU perché ha terminato il suo time slice e quindi viene portato in stato pronto.
Terminazione (system call exit)
Revoca CPU
INT
wait Allocazione
memoria
Esecuzione in user mode
pronto Esecuzione in
kernel mode
zombie
Bloccato su ram Nuovo
swapped
Sospensione (system call o interrupt)
Swap- out
Swap-out Creazione
(fork)
Swap-in
terminato IRET
signal
Il processo che viene creato con la system call fork si trova in stato nuovo e passa in stato ready (pronto) nel momento in cui il sistema decide di allocargli la memoria.
Le altre transizioni possibili sono:
bloccato su RAM- swapped: il processo viene trasferito in memoria secondaria, perché magari è da molto tempo bloccato (operazione di swap out);
pronto- swapped: il processo viene trasferito in memoria secondaria per liberare memoria per gli altri processi (operazione di swap out);
swapped-pronto: il processo viene trasferito dalla memoria secondaria in memoria principale (operazione di swap in);
bloccato su ram-pronto: il processo che è bloccato viene risvegliato tramite una signal e riportato in stato di pronto;
5. Cosa s’intende per descrittore di un processo
Un descrittore di un processo (PCB-Process Control Block) è una struttura dati che contiene varie informazioni ed è memorizzata in una area di memoria accessibile solo dal kernel del sistema operativo.
Esiste un descrittore per ogni processo e tutti i descrittori sono organizzati in una tabella chiamata tabella dei processi.
In un descrittore sono memorizzate le seguenti informazioni:
a) Nome del processo: tipicamente viene usato un indice (numero intero) che identifica la posizione del processo nella tabella dei processi. In Unix l’identificativo di un processo prende il nome di PID (Process Identifier)
b) Stato del processo: pronto, bloccato etc
c) Modalità di servizio dei processi: specifica la modalità con la quale la CPU viene assegnata ai processi pronti. Per esempio:
modalità FIFO ( chi è in attesa da più tempo viene servito per primo);
priorità: ai vari processi può essere associata una priorità statica o dinamica;
Per i sistemi a divisione di tempo viene specificato il quanto di tempo assegnato al processo e per i sistemi in tempo reale viene specificato il tempo entro cui il processo deve terminare la sua esecuzione (deadline).
d) Informazioni sulla gestione della memoria: paginazione, segmentazione, limiti area di memoria allocata al processo (è identificata dai registri base e limite).
e) Contesto del processo: ogni volta che il processo viene sospeso vengono salvati nel descrittore il contenuto del PC, il contenuto del registro di stato (PSW), il contenuto dei registri generali, accumulatore e contenuto dello stack pointer.
f) Uso delle risorse: quali sono i dispositivi di I/O assegnati al processo e i file aperti dal processo.
g) Identificativo del processo successivo: specifica quale è il processo successivo nella stessa coda di cui fa parte il processo (coda processi pronti o coda processi bloccati)
6. Cosa s’intende per contesto di un processo e quali sono i passi
fondamentali che caratterizzano un cambio di contesto tra processi?
Il contesto di un processo comprende il contenuto del Program Counter (PC) (indirizzo della istruzione successiva da eseguire), il contenuto del registro di stato (PSW-Program Status Word), il contenuto dello Stack Pointer (SP) che identifica la cima dello stack, il contenuto dell’accumulatore e dei registri di uso generale (Ri). Nel momento in cui il processo che è in esecuzione viene sospeso o per effetto di una operazione di Input/Output oppure perché è scaduto il suo quanto di tempo (sistemi multi programmati operanti in modalità time sharing) il contesto del processo deve essere salvato. In entrambe i casi il sistema operativo esegue una serie di operazioni che prendono il nome di cambio di contesto (context switch).
Quando il processo in esecuzione viene sospeso il sistema operativo salva il contesto del processo nel suo descrittore. Il descrittore del processo viene inserito nella coda dei processi pronti oppure nella coda dei processi bloccati. Il descrittore viene inserito nella coda dei processi pronti se il processo è stato sospeso perché è terminato il suo quanto di tempo e quindi passa dallo stato di esecuzione allo stato di pronto. Se invece il processo è stato
sospeso perché è in attesa del verificarsi di qualche evento (completamento di una operazione di Input/Output) allora passa dallo stato di esecuzione allo stato di bloccato e quindi il suo descrittore andrà nella coda dei processi bloccati. Ora lo scheduler a breve termine del sistema operativo sceglie un nuovo processo tra quelli presenti nella coda dei processi pronti, secondo un determinato algoritmo, per esempio FIFO (viene scelto il processo che da più tempo è in attesa) e carica nel registro del processo in esecuzione il nome di tale processo. Il registro processo in esecuzione è un registro del processore che contiene il puntatore al descrittore del processo in esecuzione. Infine il sistema operativo carica il contesto del nuovo processo nei registri del processore.
7. Si descrivano i concetti di processi concorrenti e processi cooperanti (esame del 19-04-2005)
Due o più processi si dicono concorrenti se la loro esecuzione si sovrappone nel tempo ovvero se l’esecuzione di un processo inizia prima che termini l’altro processo.
In figura è rappresentato il caso di due processi concorrenti nel caso di due unità di elaborazione (overlapping) e di una sola unità di elaborazione (interleaving)
I processi concorrenti possono dividersi in:
• processi indipendenti
• processi interagenti
Due processi sono indipendenti se l’esecuzione di un processo non influenza l’esecuzione dell’altro processo. Proprietà fondamentale di un processo indipendente è la riproducibilità ovvero l’esecuzione del processo in istanti diversi, insieme ad altri processi indipendenti, produce sempre lo stesso risultato se i dati d’ingresso rimangono gli stessi.
Due processi sono interagenti se l’esecuzione di un processo influenza l’esecuzione dell’altro processo. Due processi possono interagire attraverso scambio di messaggi (cooperazione o comunicazione) per eseguire una attività comune oppure possono
competere per la stessa risorsa (per esempio i due processi hanno una variabile in comune).
Due processi interagenti non godono della proprietà di riproducibilità in quanto il risultato dell’esecuzione di un processo dipende dalla velocità relativa dei processi ( a seconda dell’ordine con cui i processi vengono eseguiti il risultato dell’esecuzione di un processo può cambiare anche se i dati d’ingresso sono gli stessi). Nel caso di cooperazione è importante l’ordine con la quale i processi vengono eseguiti (esempio produttore
consumatore). Il corretto funzionamento del sistema produttore consumatore è garantito solo se la sequenza delle operazione è del tipo: inserimento messaggio- prelievo messaggio- inserimento messaggio- prelievo messaggio. Se la sequenza fosse invece: inserimento- inserimento-prelievo allora il secondo inserimento produce la cancellazione del primo messaggio che non verrà quindi consumato. Analogamente se la sequenza fosse:
inserimento-prelievo-prelievo lo stesso messaggio verrebbe prelevato due volte. Nel caso di competizione è invece importante che un solo processo alla volta usi la risorsa comune (mutua esclusione). In entrambe i casi si parla di sincronizzazione tra processi.
8. Si descriva l’algoritmo di schedulazione dei processi Round Robin (RR) (esame del 15-11-2004)
L’algoritmo Round Robin è uno degli algoritmi usati dallo scheduler del sistema operativo per scegliere quali tra i processi presenti nella coda dei processi pronti mandare in
esecuzione (short term scheduling). La coda dei processi pronti viene gestita in modalità FIFO e ad ogni processo viene assegnata la CPU per un quanto di tempo prefissato (tra 10 e 100ms). Se il processo richiede un tempo di esecuzione inferiore rispetto ad un quanto di tempo allora esso abbandona volontariamente la CPU e lo scheduler sceglie un nuovo processo dalla coda dei processi pronti (il primo della coda). Se invece il processo richiede più quanti di tempo allora, terminato il quanto di tempo a disposizione, il processo in esecuzione viene sospeso e inserito in fondo alla coda dei processi pronti e viene scelto il processo che è in testa alla coda. Il quanto di tempo deve essere sufficientemente grande rispetto al tempo necessario al cambio di contesto altrimenti, essendoci molti cambi di contesto, l’efficienza d’uso della CPU si riduce (aumenta l’overhead). Tipicamente nei sistemi moderni il tempo necessario per il cambio di contesto non eccede i 10µs.
Poiché con questa tecnica un processo perde la CPU forzatamente dopo un quanto di tempo allora l’algoritmo RR fa parte della categoria degli algoritmi di scheduling con diritto di prelazione (preemptive scheduling). Il processo non abbandona la cpu volontariamente (in tal caso si parla di non preemptive scheduling) ma viene forzato ad abbandonarla.
9.
Si descriva il concetto di quanto di tempo e la sua applicazione nel meccanismo di schedulazione di UNIX (esame del 19-06-2006)
Il sistema operativo UNIX è un sistema a divisione di tempo. Un processo rimane in esecuzione solo per un tempo prefissato a cui viene dato il nome di quanto di tempo o time slice. Tipicamente in UNIX il quanto di tempo è di 100ms. Un processo che è in esecuzione se non termina durante il quanto di tempo assegnato viene forzato dal S.O ad abbandonare l’uso della CPU per far posto ad un nuovo processo scelto dalla coda dei processi pronti. A tutti i processi presenti nella coda dei processi pronti viene assegnato un quanto di tempo e tutti a rotazione usano la CPU per il quanto di tempo assegnato (algoritmo Round Robin).
La scelta del nuovo processo viene fatta dalla scheduler a breve termine secondo un modalità FIFO.
Se un processo termina la sua esecuzione prima dello scadere del suo quanto di tempo abbandona volontariamente la CPU e lo scheduler sceglie un nuovo processo dalla coda dei processi pronti. In UNIX esistono diverse code di processi pronti ciascuna associata ad un diverso livello di priorità. Lo scheduler esegue l’algoritmo RR a partire dalla coda a priorità più alta e solo quando non ci sono processi nella coda a più alta priorità va a scegliere dalle altre code a priorità più bassa. Possibilità di starvation (attesa indefinita) per i processi a bassa priorità. ( si vedano anche le domande 8 e 11).
10.
Definire quali sono i livelli di scheduling e descrivere la funzione di ciascuno di essi
In un sistema operativo esistono tre livelli di scheduling:
a. short term scheduling (scheduling a breve termine);
b. long term scheduling (scheduling a lungo termine);
c. medium term scheduling (scheduling a medio termine);
Lo short term scheduling è quella funzione del sistema operativo che si occupa di scegliere quale processo, tra i processi presenti nella coda dei processi pronti residenti in memoria centrale, assegnare la CPU. Questa funzione interviene ogni volta che il processo in
esecuzione perde il controllo della CPU o perché ha terminato la propria esecuzione, oppure perché è scaduto il suo quanto di tempo, o anche perché ha richiesto una operazione di I/O.
In tutti e tre i casi lo scheduler a breve termine, chiamato anche scheduler della CPU, deve scegliere il nuovo processo da mandare in esecuzione al posto del processo che era in esecuzione.
Nel caso in cui il processo che era in esecuzione abbandona volontariamente l’uso della CPU (ha terminato la sua esecuzione oppure ha richiesto una operazione di I/O) si
parla di scheduling senza diritto di prelazione (non preemptive scheduling).
Si parla invece si scheduling con diritto di prelazione (preemptive scheduling) se il processo che era in esecuzione viene forzato ad abbandonare l’uso della CPU. Questo accade quando il processo ha terminato il suo quanto di tempo e ciò gli viene segnalato tramite un interrupt, oppure perché è stata completata una operazione di I/O (il processo in attesa viene risvegliato e se è più importante del processo in esecuzione passa immediatamente dallo stato di
bloccato allo stato di pronto e allo stato di esecuzione). Lo scheduling a breve termine si esegue molto frequentemente perché un processo rimane in esecuzione per poco tempo (in UNIX 100 msec). Lo scheduler a breve termine deve quindi scegliere molto velocemente il nuovo processo da mandare in esecuzione altrimenti verrebbe sprecato molto tempo di CPU per il solo scheduling (overhead). Se impiegasse 20ms per scegliere il nuovo processo allora si sprecherebbe, il 20/(100+20)=16,67 per cento del tempo di CPU per il solo scheduling del processo.
Il long term scheduling è quella funzione del sistema operativo che si occupa di scegliere quali processi presenti in memoria di massa caricare in memoria centrale per la successiva esecuzione. Lo scheduler a lungo termine deve scegliere un buon mix di processi da caricare in memoria centrale. Se scegliesse processi la maggior parte di tipo CPU bound, quindi che richiedono molto tempo di elaborazione e poche richieste di I/O, allora il sistema sarebbe sbilanciato nel senso che i dispositivi di I/O sarebbero sottoutilizzati. Se invece scegliesse un insieme di processi di tipo I/O bound, vale a dire processi che richiedono poca elaborazione e molte richieste di I/O allora lo scheduler a breve termine sarebbe la maggior parte del tempo inattivo in quanto la coda dei processi pronti sarebbe quasi sempre vuota perché la maggior parte dei processi si troverebbe nella coda dei processi bloccati in attesa del completamento delle operazioni di I/O. Lo scheduler a lungo termine deve anche controllare il numero di processi presenti contemporaneamente in memoria centrale (grado di multiprogrammazione).
Più sono i processi presenti in memoria centrale, minore sarà il tempo di esecuzione dedicato a ciascun processo. Lo scheduler a lungo termine può quindi limitare il grado di
multiprogrammazione in modo da fornire un servizio migliore ai vari processi.
Il medium term scheduling è quella funzione del sistema operativo che ha il compito di trasferire momentaneamente i processi dalla memoria di massa alla memoria centrale e vieceversa. Questo scheduler opera sui processi che sono già stati parzialmente eseguiti. Nel caso debba essere liberato spazio in memoria centrale, per far posto ad altri processi, allora lo scheduler a medio termine sceglie quali processi trasferire dalla memoria centrale alla
memoria di massa (operazione di swap-out). L’operazione di caricamento da memoria di massa alla memoria centrale prende invece il nome di swap-in.
11. Si descriva il meccanismo di schedulazione dei processi di UNIX (esame del 23-01-2004)
Unix è un sistema a divisione di tempo (time sharing) e quindi ogni processo usa la CPU per un quanto di tempo prefissato e poi viene forzato ad abbandonare la CPU. Lo scheduler usa quindi un algoritmo con diritto di prelazione (preemption scheduling). L’algoritmo di scheduling usato è basato sulle priorità. In particolare in UNIX lo scheduler usa più code di priorità. Tutti i processi con la stessa priorità fanno parte della stessa coda e vengono scelti secondo un algoritmo Round Robin. Lo scheduler ad ogni quanto di tempo sceglie la coda a priorità più elevata che contiene almeno un processo. Quando tutti i processi della coda a più alta priorità sono stati eseguiti (la coda è vuota) si passa ad eseguire i processi della coda successiva in ordine di priorità. La priorità dei processi è dinamica e viene ricalcolata ad ogni secondo in modo da far diminuire la priorità di quei processi che usano molto la CPU e quindi evitare fenomeni di starvation per quei processi cha hanno bassa priorità.
nuova priorità = valore iniziale +uso della CPU.
Il valore iniziale della priorità dei processi utente è maggiore di 0 mentre i processi eseguiti in modalità kernel hanno valore negativo di priorità. In Unix infatti più grande è il valore più bassa è la priorità. Un processo può volontariamente diminuire la propria priorità attraverso la system call nice.
Si descrivano le modalità di esecuzione dei processi sotto UNIX (esame del 19-04-2005)
L’esecuzione dei processi in UNIX può avvenire in modalità background (non interattiva) oppure in modalità foreground (interattiva o in primo piano).
Se un processo è in esecuzione in modalità foreground, il prompt della shell non torna finchè il processo non è terminato e quindi l’utente non può digitare nuovi comandi.
Se un processo è in esecuzione in modalità background allora la shell torna immediatamente a disposizione dell’utente subito dopo la digitazione del comando da shell. Ora l’utente può digitare nuovi comandi (eseguire nuovi programmi) e contemporaneamente il processo avviato continua la sua esecuzione in background. Per avviare un processo in modalità background occorre digitare il comando seguito dal simbolo di & (e commerciale).
Esempio: Si vuole decomprimere un grosso file di nome pippo.gz in modalità background.
Uso il comando gunzip pippo.gz &. Nel fra tempo che il processo è in esecuzione la shell torna subito a disposizione dell’utente che può eseguire nuovi comandi. Quando il processo gunzip ha terminato, viene notificata la sua terminazione.
12. Si descriva l’algoritmo di scheduling Shortest Job First; un esempio è vivamente consigliato (esame del 12-07-2006)
L’algoritmo di scheduling Shortest Job First (SJF) appartiene alla categoria degli algoritmi di short term scheduling usati dal sistema operativo per scegliere a quale tra i processi pronti assegnare la CPU. Con questo algoritmo viene scelto il processo che ha il minor tempo di esecuzione. Il problema è sapere in anticipo quanto vale il tempo di esecuzione di un processo. Questo non è praticamente possibile. Allora viene fatta una predizione basandosi sulle precedenti sequenze di esecuzioni di tale processo. L’algoritmo SJF è ottimale, nel senso che rende minimo il tempo di attesa medio per un dato insiemi di processi.
Si consideri il seguente esempio:
Siano T.E e T.A rispettivamente i tempi di esecuzione e di arrivo in coda di 4 processi P1,P2,P3,P4.
processi T.E T.A
P1 10 0
P2 20 0
P3 5 7
P4 60 15
Con l’algoritmo SJF viene prima eseguito il processo con il tempo di esecuzione più breve e cioè P1.
P1 e P2 arrivano in coda allo stesso istante e poiché P1 è più breve viene eseguito P1. Prima che P1 termini arriva in coda P3 che è più breve di P2 e quindi viene eseguito P3 e non P2, anche se P2 è arrivato prima di P3. Poi viene eseguito P2 e infine P4.
Il diagramma temporale è il seguente :
P4 P3
15
10 35 95 tempo
P1
P2
Il tempo di turnaround (tempo medio di completamento dell’insieme dei processi) vale:
Tempo di turnaround = (10+8+35+80)/4=33.25 Infatti:
P1 attende 10 prima di terminare P2 attende (15-7)=8 prima di terminare P3 attende (35-0)=35
P4 attende (95-15)=80
L’algoritmo SJF può essere sia con prelazione sia senza prelazione. Un algoritmo SJF con prelazione sostituisce il processo attualmente in esecuzione con quello che è appena arrivato in coda. La sostituzione avviene se il processo che arriva in coda ha un tempo di esecuzione inferiore al tempo che resta al processo in esecuzione. Esempio: se il processo che è in esecuzione deve ancora essere eseguito per 5 unità di tempo e arriva un processo che richiede solo 4 unità di tempo allora il processo in esecuzione viene sospeso a favore del nuovo processo e terminerà la propria esecuzione successivamente. Nel caso di SJF senza prelazione il processo in esecuzione continua ad essere eseguito anche se arriva un altro processo che richiede un tempo di esecuzione inferiore rispetto al tempo che resta al processo in esecuzione. (l’esempio fatto precedentemente è relativo ad un SJF senza prelazione).
13. Descrivere i principali algoritmi di short term scheduling
Gli algoritmi di short term scheduling sono degli algoritmi usati dal sistema operativo per scegliere quale processo, tra i processi presenti nella coda dei processi pronti, mandare in esecuzione cioè assegnargli la CPU. Questa funzione del Sistema Operativo interviene ogni volta che un processo in esecuzione abbandona forzatamente o volontariamente la CPU.
Gli algoritmi più utilizzati sono i seguenti:
FIFO(First In First Out) o FCFS (First Come First Served):
Lo scheduler sceglie, tra tutti i processi pronti, il processo che è in attesa da più tempo ossia il primo arrivato nella coda dei processi pronti. Il processo che perde l’uso della CPU viene inserito in ultima posizione nella coda dei processi bloccati (richiesta di I/O). Il processo mantiene la CPU fino al rilascio spontaneo (algoritmo senza prelazione non preemptive scheduling) che può avvenire perché il processo ha richiesto una operazione di I/O oppure perché ha terminato. I tempi medi di attesa sono alti.
SJF (Shortest Job First): Tra tutti i processi presenti nella coda dei processi pronti viene scelto il processo che ha il minor tempo di esecuzione. Problema: conoscere in anticipo la durata della successiva sequenza di operazioni di un processo. Questo è impossibile, per cui viene fatta una predizione del tempo di esecuzione basandosi sui precedenti tempi di
esecuzione del processo. Con questa tecnica i tempi di attesa sono minimi. Può essere senza prelazione oppure con prelazione come già detto in una delle risposte precedenti.
Round Robin (RR): I processi sono organizzati in una coda circolare. Ogni processo viene scelto seconda una modalità FIFO ed al processo scelto viene assegnata la CPU per un
quanto di tempo prefissato, terminato il quale la CPU gli viene revocata e il processo passa in coda alla lista. Il quanto di tempo deve essere molto più grande del tempo necessario per il cambio di contesto altrimenti l’efficienza dell’uso della CPU si riduce significativamente.
A priorità: in un sistema che usa un algoritmo a priorità, ogni processo ha una priorità e la CPU viene assegnata al processo con priorità maggiore. Se due processi hanno la stessa priorità viene scelto il processo che è arrivato per primo (FCFS). L’algoritmo può essere con prelazione oppure senza prelazione. Se adotta la prelazione allora, se arriva nella coda dei processi pronti un processo che ha una priorità più alta del processo in esecuzione, questo ultimo viene sospeso e sostituito con il processo con priorità più alta. Nel caso di scheduling senza prelazione, se arriva un processo con priorità più alta di quello in esecuzione ( e questo significa che ha anche priorità più alta dei processi presenti in coda), il processo in
esecuzione continua la sua esecuzione e il nuovo processo viene inserito in testa alla coda dei processi pronti. Il problema di questa tecnica di scheduling è lo starvation ossia l’attesa indefinita. Un processo che ha bassa priorità rischia di attendere indefinitamente prima poter avere la CPU perché ci sono sempre processi con priorità più alta della sua.
La priorità di un processo può essere statica (assegnata all’atto della creazione del processo e non più modificabile) o dinamica (può cambiare durante la vita del processo). La priorità dinamica viene usata per risolvere il problema dello starvation. Ad un processo che è da molto tempo in attesa gli viene aumentata la priorità e questo avviene periodicamente a intervalli di tempo prefissati. In questo modo anche un processo a bassa priorità può ottenere la priorità più alta. Un processo che usa molto la CPU subisce una diminuzione della priorità, mentre un processo che usa molto i dispositivi di I/O ottiene un aumento della priorità.
14. Data la seguente tabella dei processi (T.A tempo di arrivo nel sistema, T.E tempo di esecuzione) calcolare il tempo di turnaround medio con gli
algoritmi di scheduling FCFS e SJF: (esame del 09-05-2007)
Processi T.E T.A
P1 20 0
P2 5 15
P3 10 10
P4 5 20
L’algoritmo di scheduling FCFS (First Come First Served) sceglie tra tutti i processi presenti nella coda dei processi pronti quello che da più tempo è in attesa, mentre
l’algoritmo SJF (Shortest Job First) sceglie il processo con il minor tempo di esecuzione.
Nel caso FCFS abbiamo la seguente situazione:
Il primo processo ad essere eseguito è il processo P1 che arriva all’istante t=0;
Il secondo processo è il processo P3 che arriva all’istante t=10;
Il terzo processo è il processo P2 che arriva all’istante t=15;
Per ultimo viene eseguito il processo P4 che arriva all’istante t=20;
Il tempo di turnaround medio è dunque il seguente:
Tempo di turnaround=[20+(30-10)+(35-15)+(40-20)]/4=20 Infatti :
P1 attende 20 prima di terminare
P3 attende (30-10)=20 prima di terminare P2 attende (35-15)=20 prima di terminare P4 attende (40-20)=20 prima di terminare
Di seguito è rappresentato il diagramma temporale
Nel caso SJF abbiamo invece:
Il primo processo ad essere eseguito è il processo P1 perché è il primo che arriva in coda;
Il secondo processo ad essere eseguito è il processo P2 perché quando termina P1 (istante 20) P2 è in coda con P3 e P4. I tempi di esecuzione di P2 e P4 sono gli stessi ma P2 è arrivato prima, per cui viene schedulato P2;
Il terzo processo ad essere eseguito è il processo P4 perché ha un tempo di esecuzione inferiore rispetto a P3;
Infine viene schedulato P3;
P4 P3
30
20 35 40 tempo
P1 P2
Il tempo di turnaround medio è dunque il seguente:
Tempo di turnaround=[20+(25-15)+(30-20)+(40-10)]/4=17,5 (inferiore rispetto all’algoritmo FCFS)
Infatti :
P1 attende 20 prima di terminare
P2 attende (25-15)=10 prima di terminare P4 attende (30-20)=10 prima di terminare P3 attende (40-10)=30 prima di terminare
Di seguito è rappresentato il diagramma temporale
15. Data la seguente tabella di processi con i relativi tempi di esecuzione (T.E) e di arrivo nel sistema (T.A), disegnare l’andamento temporale dei processi supponendo di adottare una polita di schedulazione FCFS (FIFO) e
calcolare il tempo di turnaround medio.
Processi T.E T.A
P1 30 0
P2 25 5
P3 80 6
P4 5 20
P3 P2
25
20 30 40 tempo
P1 P4
Il tempo di turnround medio è il tempo medio di completamento dell’insieme dei processi.
Il diagramma temporale dell’esecuzione dei processi è il seguente:
Con la politica FCFS il primo processo che viene mandato in esecuzione è il processo che è arrivato per primo. Nell’esempio è il processo P1.
Dopo il processo P1 viene eseguito il processo P2 perché arriva all’istante 5, poi il processo P3 che arriva all’istante 6 e infine il processo P4.
Il processo P1 rimane in esecuzione per 30 unità di tempo e poiché viene servito subito, il suo tempo di attesa per il completamento è pari a 30 unità. P2 invece arriva in t=5 ma deve attendere che P1 sia terminato, per cui entra in esecuzione all’istante t=30. Il suo tempo di attesa per il completamento è pari a (55-5)=50 unità di tempo.
P3 deve attendere che P1 e P2 abbiano completato. Il processo P3 arriva in t=6 e prima che venga eseguito deve attendere il completamento di P1 e P2. Quindi il suo tempo di attesa è pari a (135- 6)=129. Il processo P4 arriva in t=20 e quindi attende (140-20)=120 prima di essere completato.
Il tempo medio di turnround è dunque pari a :
tempo di turnround= [30+(55-5)+(135-6)+(140-20)]/4= 82,25
