Torna alla pagina di Sistemi Operativi
:: Appunti caotici ::
Lezione 3
Politiche di schedulazione
Pag 1
Sommario
...
Pag 2
First-Come, First-Served: FCFS (1)
In questa politica si fa uso di una coda, ove i processi entrano ed attendono di essere eseguiti. L'ordine in cui i processi sono eseguiti (da come si può capire dal titolo) è il seguente:
"il primo che entra nella coda sarà il primo ad essere servito"
First-Come, First-Served: FCFS (2)
...
Pag 3
Shortest-Job-First: SJF (1)
...
Shortest-Job-First: SJF (2)
...
Pag 4
Shortest-Job-First: SJF (3)
In questa tecnica devo conoscere il tempo minimo richiesto al processore da parte del processore. Se non conosco tale tempo posso effettuare una stima, ma rischio di commettere errori e di non poter ottimizzare il processore. Un altro modo è di vedere nel passato quel processo quanto tempo ha tenuto occupato il processore, ma si tratta comunque di una stima e non è precisa.
Priorità (1)
La priorità è una proprietà del processo che indica quanto prima dobbiamo eseguirlo rispetto ad altri, indipendentemente dall'ordine con cui arrivano.
Si tratta in pratica di assegnare ad ogni processo un indice che indica il suo livello di priorità, sarà poi il sistema operativo a decidere come trattarlo. Va infatti detto che non è affatto automatico il collegamento "indice alto"-"priorità alta". Ad esempio nei sistemi UNIX più l'indice è basso e più è importante; in particolare i processi di sistema hanno priorità negativa (il minimo è -20) mentre quelli delle applicazioni positiva.
Infine, da notare come dare più proprietà non vuol dire necessariamente dare più tempo ad ogni processo.
Pag 5
Priorità (2)
Pre-emptive: processo che diventa pronto interrompe processo in esecuzione richiedendo schedulazione.
Quando in pratica un processo entra nello stato ready-to-run andrò a vedere se nella lista dei processi running ho solo processi di priorità minore, nel qual caso toglierò con una pre-emption quello in esecuzione e caricherò quello nuovo. Se invece in esecuzione ho un processo di priorità maggiore, ordinerò l'ultimo arrivato secondo i normali criteri di schedulazione (anche se generalmente mantengo l'ordine di arrivo, così aggiungo in coda e tebbona)
Non pre-emptive:processo che diventa pronto non interrompe rocesso in esecuzione richiedendo schedulazione.
Se il processo considerato ha priorità maggiore di quello in esecuzione, lascio finire quest'ultimo e quando sarà completato manderò in esecuzione quello nuovo
Priorità (3)
Un problema di questo tipo di politica di schedulazione è che processi a bassa priorità potrebbero rimanere ready-to-run per un tempo indefinito; basta infatti che continuino ad arrivare processi a priorità maggiori che gli soffino il posto. Questo fenomeno prende il nome di starvation, che se proprio vogliamo dirlo in italiano lo chiameremo "blocco indefinito" e non (letteralmente) affamamento, o Puree si incazza.
La soluzione è introdurre un progressivo invecchiamento delle priorità, detto aging. In pratica, se abbiamo un processo che rimane in starvation per un tempo abbastanza lungo, cominciamo ad aumentargli la priorità proporzionalmente al tempo di attesa, sperando che acquisisca (e prima o poi accadrà) abbastanza priorità da essere eseguito. Una volta ottenuto il suo turno di computazione gli riabbatto la priorità allo stato iniziale, e riprendo il ciclo di prima (starvation, invecchiamento, computazione, ecc).
Ho quindi delle priorità di tipo dinamico che aumentano con l'invecchiare del processo.
Pag 6
Round-Robin RR (1)
Si supponga che il processo P termini e passa a quello successivo, ovvero il prcesso Q. Quest'ultimo si trova nello stato di wait allora passo al processo R che è quello successivo, il quali si trova nello stato di ready to run e allora lo posso mettere nella coda. Si passa al successivo, ovvero al processo R, anch'esso è nello stato di ready to run, dunque lo sbatto nella coda. Il processo successivo (processo T) si trova nello stato di wait allora termino il ciclo. A questo punto riparto da capo per poter riscandire i processi che prima si travavano nello stato di wait.
Round-Robin RR (2)
Alcune caratteristiche:
- distribuzione uniforme del tempo di elaborazione tra i processi pronti (andando a turno a dare un quanto di tempo ai vari processi)
- velocità di esecuzione dei processi dipende dal numero di processi pronti
- turnaround (tempo di permanenza nel sistema) dipende dalla durata del quanto di tempo
Pag 7
Coda a più livelli (1)
Quando ho più utenti che usano processi diversi posso raggruppare tali processi in base al loro tipo. Ogni tipologia è assegnata ad un livello della coda il quale possiede un suo algoritmo di schedulazione.
Coda a più livelli (2)
...
Pag 8
Coda a più livelli con retroazione C+LR (1)
In questo caso ho sempre una coda con più livelli, la differenza è che i processi presenti su tali livelli possono migrare da un livello a un altro livello. La possibilità di far migrare i livelli è stata introdotta per poter tenere in considerazioe la priorità dei processi. Se ho un processo che perde priorità e ad un livello sottostante ne ho un altro che possiede priorità più alta, posso far scendere il primo processo per far salire il secondo in modo tale che possa usare il processore.
Coda a più livelli con retroazione C+LR (2)
Per poter consentire questa migrazione devo poter stabilire quale processo ha priorità più alta, quindi introduco delle politiche di promozione per far passare di grado il processo.
Pag 9
Schedulazione in sistemi multiprocessore (1)
...
Schedulazione in sistemi multiprocessore (2)
...
Pag 10
Schedulazione in sistemi multiprocessore (3)
...
Schedulazione in sistemi multiprocessore (4)
...
Torna alla pagina di Sistemi Operativi
