Scheduling

Scheduling round robin

e'basato sul concetto di quanto di tempo (time slice)

• un process non puo'essere in esecuzione per un tempo superiore alla durata del quanto

Implementazione (1)

• l'insieme dei processi pronti è organizzato come una coda
• due possibilità:
  • un processo può lasciare il processore volontariamente, in seguito ad un'operazione di I/O
  • un processo può esaurire il suo quanto di tempo senza completare il suo CPU burst, nel qual caso viene aggiunto in fondo alla coda dei processi pronti
• in entrambi i casi, il prossimo processo da esegure è il primo della coda dei processi pronti

La durata del quanto di tempo è un parametro critico del sistema

• se il quanto di tempo è breve, il sistema è meno efficiente perchè deve cambiare il processo attivo più spesso
• se il quanto è lungo, in presenza di numerosi processi pronti ci sono lunghi periodi di inattività di ogni singolo processo,
• in sistemi interattivi, questo può essere fastidioso per gli utenti

Implementazione (2)

• è necessario che l'hardware fornisca un timer (interval timer) che agisca come "sveglia" del processore
• il timer è un dispositivo che, attivito con un preciso valore di tempo, è in grado di fornire un interrupt allo scadere del tempo prefissato
• il timer viene interfacciato come se fosse un'unita di I/O

round robin e' troppo democratico, tutti i processi hanno la stessa priorita' (in realta'alcune task sono piu importanti di altre)

Scheduling a priorita'

Ogni processo e' associato a una specifica priorita' lo scheduler sceglie il processo pronto a priorita' piu'alta la system call per cambiare priorita' al processo si chiama nice (per abbassare la priorita')

Le priorità possono essere:

• definite dal sistema operativo
  • vengono utilizzate una o più quantità misurabili per calcolare la priorità di un processo
  • esempio: SJF è un sistema basato su priorità (priorita' piu alta a processi che finiscono prima)
• definite esternamente
  • le priorità non vengono definite dal sistema operativo, ma vengono imposte dal livello utente

Tipi di priorita:

• Priorità statica:
  • la priorità non cambia durante la vita di un processo
  • problema: processi a bassa priorità possono essere posti in starvation da processi ad alta priorità
• Priorità dinamica
  • la priorità può variare durante la vita di un processo
  • è possibile utilizzare metodologie di priorità dinamica per evitare starvation

Priorità basata su aging:

• incremento graduale della priorita dei processi in attesa
• nessun processo rimarra'in attesa per un tempo indefinito (prima o poi il proc raggiungera'la priorita' massima)

Classi di priorita'

• e' possibile creare diverse classi di processi con caratteristiche sismili e assegnare ad ogni classe specifiche priorita'
• la coda ready viene quindi scomposta in tante "sottocode", una per ogni classe di processi

Algoritmo:

• uno scheduler a classi di priorità seleziona il processo da eseguire fra quelli pronti della classe a priorità massima che contiene processi

Scheduling Multilivello

• all'interno di ogni classe di processi, è possibile utilizzare una politica specifica adatta alle caratteristiche della classe
• uno scheduler multilivello cerca prima la classe di priorità massima che ha almeno un processo ready
• sceglie poi il processo da porre in stato running coerentemente con la politica specifica della classe

Esempio: Quattro classi di processi (priorità decrescente):

• processi server (priorità statica)
• processi utente interattivi (round-robin)
• altri processi utente (FIFO)
• il processo vuoto (FIFO banale)

nell'ultimo livello c'e' il processo vuoto (serve per far aspettare a)

Scheduling Real-Time

• la correttezza dell'esecuzione non dipende solamente dal valore del risultato, ma anche dall'istante temporale nel quale il risultato viene emesso

Hard real-time

• le deadline di esecuzione dei programmi non devono essere superate in nessun caso
• sistemi di controllo nei velivoli, centrali nucleari o per la cura intensiva dei malati

Soft real-time

• errori occasionali sono tollerabili
• ricostruzione di segnali audio-video, transazioni interattive

Processi periodici

• sono periodici i processi che vengono riattivati con una cadenzaregolare (periodo)
• esempi: controllo assetto dei velivoli, basato su rilevazione periodica dei parametri di volo
• Processi aperiodici
• i processi che vengono scatenati da un evento sporadico, ad esempio l'allarme di un rilevatore di pericolo

Rate Monotonic:

• è una politica di scheduling, valida alle seguenti condizioni
• ogni processo periodico deve completare entro il suo periodo
• tutti i processi sono indipendenti
• la preemption avviene istantaneamente e senza overhead
• viene assegnata staticamente una priorità a ogni processo
• processi con frequenza più alta (i.e. periodo più corto) hanno prioritàpiù alta
• ad ogni istante, viene eseguito il processo con priorità più alta (facendo preemption se necessario)

Earliest Deadline First:

• è una politica di scheduling per processi periodici real-time
• viene scelto di volta in volta il processo che ha la deadline più prossima
• viene detto "a priorità dinamica" perchè la priorità relativa di due processi varia in momenti diversi

Modulo 4 gestore risorse e deadlock

Risorse

un sistema di elaborazione e' composto da un insieme di risorse da assegnare ai processi (es. memoria, stampanti, interfaccie di rete…)

classi di risorse

Le risorse della stessa classe sono equivalenti es. byte di mem, stampanti dello stesso tipo

Definizioni:

• le risorse di una classe vengono dette istanze della classe
• il numero di risorse in una classe viene detto molteplicità del tipo di risorsa

Nota: Un processo non può richiedere una specifica risorsa, ma solo una risorsa di una specifica classe (es. un proc puo chedere memoria ma non puo specificare quale banco di memoria vuole)

Assegnazione delle risorse

Risorse ad assegnazione statica

• avviene al momento della creazione del processo e rimane valida fino allaterminazione
• esempi: descrittori di processi, aree di memoria (in alcuni casi)

Risorse ad assegnazione dinamica

• i processi
  • richiedono le risorse durante la loro esistenza
  • le utilizzano una volta ottenute
  • le rilasciano quando non più necessarie (eventualmente alla terminazione del processo
• esempi: periferiche di I/O, aree di memoria (in alcuni casi)

Tipi di richieste

Richiesta singola:

• si riferisce a una singola risorsa di una classe definita
• è il caso normale

Richiesta multipla

• si riferisce a una o più classi, e per ogni classe, ad una o più risorse
• deve essere soddisfatta integralmente

Richiesta bloccante

• il processo richiedente si sospende se non ottiene immediatamente l'assegnazione
• la richiesta rimane pendente e viene riconsiderata dalla funzione di gestione ad ogni rilascio

Richiesta non bloccante

• la mancata assegnazione viene notificata al processo richiedente, senza provocare la sospensione

Risorse non condivisibili (seriali)

• una singola risorsa non può essere assegnata a più processi contemporaneamente

• esempi: (i processori, le sezioni critiche, le stampanti)

• Risorse condivisibili
• esempio: (file di sola lettura)

Risorse prerilasciabili ("preemptable")

una risorsa si dice prerilasciabile se la funzione di gestione può sottrarla ad un processo prima che questo l'abbia effettivamente rilasciata

Meccanismo di gestione:

• il processo che subisce il prerilascio deve sospendersi
• la risorsa prerilasciata sarà successivamente restituita al processo

Una risorsa è prerilasciabile:

• se il suo stato non si modifica durante l'utilizzo
• oppure il suo stato può essere facilmente salvato e ripristinato

Esempi:

• processore
• blocchi o partizioni di memoria (nel caso di assegnazione dinamica)

Risorse non prerilasciabili

• la funzione di gestione non può sottrarle al processo al quale sono assegnate
• sono non prerilasciabili le risorse il cui stato non può essere salvato e ripristinato

Esempi

• stampanti
• classi di sezioni critiche
• partizioni di memoria (nel caso di gestione statica)

Deadlock

• i deadlock impediscono ai processi di terminare correttamente
• le risorse bloccate in deadlock non possono essere utilizzati da altri processi

Condizioni per avere un deadlock

Mutua esclusione / non condivisibili

• le risorse coinvolte devono essere non condivisibili (seriali)

Assenza di prerilascio

• le risorse coinvolte non possono essere prerilasciate, ovvero devono essere rilasciate volontariamente dai processi che le controllano

Richieste bloccanti (detta anche "hold and wait")

• le richieste devono essere bloccanti, e un processo che ha già ottenuto risorse può chiederne ancora

Attesa circolare

• esiste una sequenza di processi P0,P1, …, Pn, tali per cui P0 attende una risorsa controllata da P1, P1 attende una risorsa controllata da P2, …, e Pn attende una risorsa controllata da P0

L'insieme di queste condizioni è necessario e sufficiente (devono valere tutte contemporaneamente affinché un deadlock si presenti nel sistema)

Grafo di Holt

Caratteristiche:

• è un grafo diretto
  • gli archi hanno una direzione
• è un grafo bipartito
  • i nodi sono suddivisi in due sottoinsiemi e non esistono archi che collegano nodi dello stesso sottoinsieme
  • i sottoinsiemi sono risorse e processi
• gli archi risorsa → processo indicano che la risorsa è assegnata al processo
• gli archi processo → risorsa indicano che il processo ha richiesto la risorsa

Esempio:

Nel caso di classi contenenti più istanze di una risorsa l'insieme delle risorse è partizionato in classi e gli archi di richiesta sono diretti alla classe e non alla singola risorsa

Rappresentazione:

• i processi sono rappresentati da cerchi
• le classi sono rappresentati come contenitori rettangolari
• le risorse come punti all'interno delle classi

Nota:

• non si rappresentano grafi di Holt con archi relativi a richieste che possono essere soddisfatte
• se esiste almeno un'istanza libera della risorsa richiesta, la risorsa viene assegnata

Esempio

Nell’implementazione il grafo di Holt viene memorizzato come grafo pesato (con pesi ai nodi risorsa e pesi sugli archi)

sugli archi:

• la molteplicità della richiesta (archi processo → classe)
• la molteplicità dell'assegnazione(archi classe → processo)

all'interno delle classi

• il numero di risorse non ancora assegnate

Metodi di gestione dei deadlock

Deadlock detection and recovery:

• permettere al sistema di entrare in stati di deadlock; utilizzare un algoritmo per rilevare questo stato ed eventualmente eseguire un'azione di recovery

Deadlock prevention / avoidance:

• impedire al sistema di entrare in uno stato di deadlock

Deadlock detection

Descrizione

• mantenere aggiornato il grafo di Holt, registrando su di esso tutte le assegnazioni e le richieste di risorse
• utilizzare il grafo di Holt al fine di riconoscere gli stati di deadlock

Problema: come riconoscere uno stato di deadlock?

Caso 1 - Una sola risorsa per classe

Teorema

• se le risorse sono a richiesta bloccante, non condivisibili e non prerilasciabili
• lo stato è di deadlock se e solo se il grafo di Holt contiene un ciclo

Dimostrazione

• si utilizza una variante del grafo di Holt, detto grafo Wait-For
• si ottiene un grafo wait-for eliminando i nodi di tipo risorsa e collassando gli archi appropriati
• il grafo di Holt contiene un ciclo se e solo se il grafo Wait-for contiene un ciclo
• se il grafo Wait-for contiene un ciclo, abbiamo attesa circolare

Attenzione: La presenza di un ciclo nel caso di Holt non è condizione sufficiente per avere deadlock No deadlock perche' quando r finisce la sua risorsa puo essere data a p o q per permettergli di finire l'esecuzione

Riducibilità di un grafo di Holt

Definizione

• un grafo di Holt si dice riducibile se esiste almeno un nodo processo con solo archi entranti

Riduzione

• consiste nell'eliminare tutti gli archi di tale nodo e riassegnare le risorse ad altri processi

Qual è la logica? - eventualmente, un nodo che utilizza una risorsa prima o poi la rilascerà; a quel punto, la risorsa può essere riassegnata

Deadlock detection con grafo di Holt

Teorema

• se le risorse sono a richiesta bloccante, non condivisibili e non prerilasciabili
• lo stato non è di deadlock se e solo se il grafo di Holt è completamente riducibile, i.e. esiste una sequenza di passi di riduzione che elimina tutti gl archi del grafo

Deadlock detection - Knot

Definizione

• dato un nodo n, l'insieme dei nodi raggiungibili da n viene detto insieme di raggiungibilità di n (scritto R(n))
• un knot del grafo G è il sottoinsieme (non banale) di nodi M tale che per ogni n in M, R(n)=M
• in altre parole: partendo da un qualunque nodo di M, si possono raggiungere tutti i nodi di M e nessun nodo all'infuori di esso.

Teorema

• dato un grafo di Holt con una sola richiesta sospesa per processo
• se le risorse sono a richiesta bloccante, non condivisibili e non prerilasciabili,
• allora il grafo rappresenta uno stato di deadlock se e solo se esiste un knot

Deadlock recovery

Dopo aver rilevato un deadlock bisogna sistemarlo La soluzione può essere:

• manuale
  • l'operatore viene informato e eseguirà alcune azioni che permettano al sistema di proseguire
• automatica
  • il sistema operativo è dotato di meccanismi che permettono di risolvere in modo automatico la situazione, in base ad alcune politiche

Meccanismi per il deadlock recovery

Terminazione totale

• tutti i processi coinvolti vengono terminati

Terminazione parziale

• viene eliminato un processo alla volta, fino a quando il deadlock non scompare

Checkpoint/rollback

• lo stato dei processi viene periodicamente salvato su disco (checkpoint)
• in caso di deadlock, si ripristina (rollback) uno o più processi ad uno stato precedente, fino a quando il deadlock non scompare

Quindi terminare processi puo essere costoso e puo' lasciare le risorse in uno stato incoerente (es se un proc viene terminato nel mezzo di una sezione critica)

Deadlock prevention / avoidance

Prevention:

• per evitare il deadlock si elimina una delle quattro condizioni del deadlock  il deadlock viene eliminato strutturalmente

Avoidance

• prima di assegnare una risorsa ad un processo, si controlla se l'operazione può portare al pericolo di deadlock
• in quest'ultimo caso, l'operazione viene ritardata

Attaccare la condizione di "Mutua esclusione"

• permettere la condivisione di risorse
• e.g. spool di stampa, tutti i processi "pensano" di usare contemporaneamente la stampante

Problemi dello spooling:

• non sempre è applicabile (ad esempio, descrittori di processi)

Attaccare la condizione di "Richiesta bloccante"

• Allocazione totale
  • è possibile richiedere che un processo richiede tutte le risorse all'inizio della computazione
• Problemi
  • non sempre l'insieme di richieste è noto fin dall'inizio
  • si riduce il parallelismo

Attaccare la condizione di "Assenza di prerilascio"

• non sempre è possibile
• può richiedere interventi manuali

Attaccare la condizione di "Attesa Circolare"

• Allocazione gerarchica
  • alle classi di risorse vengono associati valori di priorità
  • ogni processo in ogni istante può allocare solamente risorse di priorità superiore a quelle che già possiede
  • se un processo vuole allocare una risorsa a priorità inferiore, deve prima rilasciare tutte le risorse con priorità uguale o superiore a quella desiderata

Allocazione gerarchica e allocazione totale: problemi

• prevengono il verificarsi di deadlock, ma sono altamente inefficienti

Nell'allocazione gerarchica:

• l'indisponibilità di una risorsa ad alta priorità ritarda processi che già detengono risorse ad alta priorità

Nell'allocazione totale:

• anche se un processo ha necessità di risorse per poco tempo deve allocarla per tutta la propria esistenza

L'algoritmo del banchiere

• un algoritmo per evitare lo stallo sviluppato da Dijkstra (1965)
• il nome deriva dal metodo utilizzato da un ipotetico banchiere di provincia che gestisce un gruppo di clienti a cui ha concesso del credito; non tutti i clienti avranno bisogno dello stesso credito simultaneamente

Descrizione

• un banchiere desidera condividere un capitale (fisso) con un numero (prefissato) di clienti
  • per Dijkstra l'"unità di misura" erano fiorini olandesi
• ogni cliente specifica in anticipo la sua necessità massima di denaro
  • che ovviamente non deve superare il capitale del banchiere
• i clienti fanno due tipi di transazioni
  • richieste di prestito
  • restituzioni