Sistemi Operativi - Lezione dell'11 marzo 2008

 :: Sistemi Operativi - Lezione dell'11 marzo 2008 ::

Torna alla pagina di Sistemi Operativi

Modulo 5 - Lezione 1 - Scheduling

Nota: quanto segue si applica sia ai processi che ai thread, con le dovute differenze. Ma i principi rimangono uguali.

Noi vedremo lo scheduling dei processi che sono nello stato ready to run, anche se si possono schedulare processi anche in altri stati.

L'obiettivo dello scheduling è stabilire in che ordine eseguire i processi. L'ordine di esecuzione può prefiggersi diversi scopi, a seconda che lo voglia stabilire nel breve, medio o lungo termine. Da notare che lo scheduling a lungo termine non riguarda solo i processi in memoria centrale, ma anche quelli ancora da caricare dalla memoria centrale. Si parla quindi di uno spazio di memoria astratto, tutto quello che il gestore della memoria mi può dare in pasto.

Short term scheduler (CPU scheduler)

Obiettivo: ordinare i processi già in memoria centrale, che si trovano nello stato ready-to-run, ovvero hanno tutte le risorse disponibili tranne il processore.

Questo scheduler viene eseguito molto spesso, eg ogni 100 ms. Deve quindi essere rapido, e quindi in favore della rapidità si può anche sacrificare un po' la ricerca dell'ottimo, altrimenti va a finire che passo più tempo a schedularli che nemmeno ad eseguirli, i processi, e a quel punto tanto valeva eseguirli in un ordine casuale.

Long term scheduler

Ordina i processi presenti nel sistema, sia in memoria centrale che altrove, cioè tutti quelli attivati.

L'obiettivo è sfruttare al massimo la CPU, senza cadere nel solito errore di consegnare il processore in mano ai CPU-bound che se lo terrebbero tutto per loro. Nel long term scheduler entrano quindi anche i lavori batch.

Ci sono anche sistemi che non hanno questo scheduler, eg quelli embedded, perché non ne ha affatto bisogno.

Siccome questo scheduler viene eseguito molto meno frequentemente, ci si può permettere di usare algoritmi più lenti e complessi, anche perché così in genere si ottengono migliori risultati. Poi, siccome devo caricare anche processi dai dischi, non posso certo permettermi di farlo ogni 100 ms, perché il tempo di caricamento in genere è di qualche ordine di grandezza in più.

Mid term scheduler

Questo scheduler si applica quando c'è troppa concorrenza tra i processi, quando non c'è bilanciamento tra CPU-bound e I/O-bound, se la memoria centrale si esaurisce.

Insomma, viene usato per ottimizzare le cose in situazioni un po' critiche. Modifica ciò che è già presente in memoria, a cui si è arrivati tramite le scelte degli altri due scheduler, e di fatto corregge queste scelte qualora si siano rivelate inadatte. Infatti, nessuno scheduler può prevedere il futuro.

Le operazioni che fa si chiamano swapping out e swapping in. Swapping out vuol dire rimuovere processi dalla memoria centrale e adagiarli nei dischi. Lo swapping in è il contrario.

Nota: non usare il termine swappare in presenza del professore.

Attivare le schedule

Ok, ho stabilito il mio schedule, ovvero la tabella di marcia. Quand'è che effettivamente applico la turnazione?

Ci sone due strategie, quelle preemptive e quelle non-preemptive.

Le strategie non preemptive avvengono in modo sincrono rispetto all'evoluzione dello stato della computazione del processo. I casi in cui si sospende un processo per attivare il prossimo in modo implicito esplicito sono i seguenti:

• il processo fa una richiesta I/O;
• il processo attende la terminazione di un figlio;
• il processo rilascia volontariamente il processore;
• il processo finisce.

Se avviene uno di questi casi, il SO passa il pallino al prossimo processo in lista. Quindi possiamo dire che gli effetti dello scheduling non-preemptive sono sincroni con l'evoluzione dello stato della computazione. Sempre, quando accade una di ste cose, si cambia processo.

Preemptive scheduling

Quando scade il quanto di tempo assegnato ad un processo (la sua time slice), il processo viene cambiato. È quindi un avvenimento asincrono rispetto all'evoluzione bla bla. Questo è ciò che accde nei sistemi time-sharing.

Lezione 2 - Criteri di schedulazione

Posso valutare uno scheduling in base a diversi criteri, tra cui possiamo citare:

• utilizzo del processore;
• throughput = frequenza di completamento;
• tempo di completamento;
• tempo di attesa;
• tempo di risposta.

Throughput = truput = quanti processi vengono eseguiti nell'unità di tempo, ovvero quanti utenti riesco a soddisfare in un dato intervallo di tempo.

Tempo di completamento = quanto tempo un processo passa nel processore prima di essere sostituito. Può darsi che un processo di per sé ci metta meno tempo se sta di più nel processore, ma magari ci sono altri processi che per via di esigenze particolari devono arrivare in fondo prima di altri.

Tempo di risposta = quanto tempo passa tra l'arrivo di un evento e la sua gestione da parte del SO. Se i quanti di tempo, eg, sono grandi, il tempo di risposta può essere alto.

Tempo di attesa = tempo da attendere tra la creazione di un processo e la sua attivazione.

Devo valutare un po' il carico applicativo del mio sistema, e in base a questo (e a tanta esperienza...) decidere che mix di criteri usare per schedulare bene. Può darsi infatti che se ottimizzo da una parte, peggioro dall'altra e così via. Eg, un server può aver bisogno di quanti di tempo lunghi, perché non deve essere interattivo ma avere tanto truput. Un sistema desktop invece può anche permettersi di essere meno performante alla lunga, ma deve reagire istantaneamente alle bizzarrie dell'utente.

Ho diversi metodi per valutare se i miei criteri sono stati raggiunti. Posso infatti vare valutazioni analitiche, ovvero deterministiche, oppure statistiche.

Valutazione analitica

Creo un modello matematico e deterministico del mio sistema, e gli do in pasto le mie schedulazioni. Vedo quindi rapidamente quanto il sistema renderà.

Ma 1) non è semplice da realizzare; 2) l'input dato a tali equazioni deve essere esatto, perché minime variazioni possono dare luogo a risultati ben diversi tra di loro.

Valutazione statistica

Nel modello a reti di code, visualizzo il sistema come una macchina che offre servizi diversi, eg disco, memoria, tastiera e così via. Ogni servizio ha una sua coda, e statisticamente vedo un po' quanto tempo il processo passa in una coda e in un'altra.

Un servizio ha una coda di processi che vogliono utilizzarlo. Un processo vuole una certa sequenza di servizi, magari prima la tastiera, poi il disco, poi il video e così via.

Nella sua evoluzione, un processo passa da una coda all'altra, e la statistica di Babbo Gianini ci permetterà di stabilire bene o male quanto tempo un processo passerà in una coda e quanto ne passerà invece in un'altra.

Naturalmente, parlando di statistica, vuol dire che si semplifica la realtà.

Un altro sistema statistico è quello della simulazione: realizzo un software che simula il mio sistema con un certo grado di aderenza alla realtà, e vedo in media come si comporta.

Implementazione

Un altro sistema per vedere se il mio scheduling funziona è, banalmente, quello di realizzare il sistema e vedere come si comporta nella realtà! Ovviamente il costo di realizzare sto sistema dal vero non è per niente leggero, e poi occorre che gli utenti lo sappiano e lo utilizzino etc. etc.

Infine, teniamo in conto che magari il mio sistema riceve carichi diversi a seconda del momento della giornata, e quindi potrebbe aver bisogno di scheduling diversi, e a questo punto occorre valutare se usare il trend medio oppure adattarsi ogni volta alla nuova situazione.

Lezione 3 - Politiche di scheduling

First Come, First Served

Il primo che arriva meglio alloggia. Però vediamo subito che è non preemptive, ed è piuttosto barbaro nei confronti dell'interazione!

Shortest Job First

È un buon sistema: il processo che ci mette meno tempo per finire viene eseguito per primo, e gli altri vengono eseguiti poi in sequenza.

Posso averlo sia preemptive che non preemptive, e in genere la versione preemptive rende meglio. Se è preemptive, vuol dire che non appena mi arriva un processo che ha un tempo di esecuzione più basso di quello attualmente in esecuzione, allora faccio lo swap asincrono con quello nuovo.

Questa politica però è basata sull'assunto di conoscere il tempo che ciascun processo ci metterà. Nel caso dei lavori batch, posso anche indovinarlo e saperlo con certezza, ma in generale è una conoscenza difficile da ottenere, e se faccio delle medie ricavate chissà come, e poi sbaglio, l'efficienza garantita da sto scheduler diventa nulla. Altrimenti perderei tempo a decidere lo scheduler e non a eseguire i processi, e allora tanto valeva eseguirli in un ordine casuale.

Priorità

Un processo ha una priorità che lo distingue dagli altri.

OCIO: in alcuni SO priorità alta = indice alto, in altri indice basso, quindi non facciamo assunti sull'indice numerico della priorità.

Il processo prioritario viene eseguito prima dei processi non prioritari. Anche qui, se uso la versione preemptive, un processo con bassa priorità appena arrivato può interrompere asincronicamente il processo attualmente in esecuzione.

Problema: i processi con priorità bassa potrebbero attendere mille anni prima di trovare posto tra tanti processi ad alta priorità che li precedono! Si chiama starvation, ovvero blocco indefinito.

E allora si stabilisce che dopo un po' di tempo un processo invecchia (aging), e guadagna in priorità, e ad un certo punto ovviamente potrà competere con processi che in partenza erano più prioritari e prepotenti di lui.

Round Robin

Nella sua forma originale, il round robin dà a tutti i processi lo stesso peso, e li esegue uno dopo l'altro scambiandoli quando scade il quanto di tempo.

Se il quanto è lungo, diventa in pratica un FCFS (First Come First Served), perché il primo che arriva si piglia il quantone grosso. Se il quanto è corto, perdo troppo tempo a gestire la faccenda del context switch. E allora cerco di usare un quanto abbastanza lungo così da soddisfare la maggior parte delle mie richieste medie.

Coda a più livelli (C+L)

Creo divere categorie, ognuna con la sua specificità (eg la categoria dei processi I/O bound, quella dei processi batch, quelli interattivi e così via). Ogni categoria ha la sua coda, e ogni coda il suo algo di scheduling. Poi, ogni tanto faccio il mix di queste code e ne traggo il mio scheduling. Wow!

Coda a più livelli con retroazione (C+LR)

Come quella sopra, ma permette a dei processi di migrare da una coda all'altra, sia per guadagnare in priorità, che per perderne e dare agli altri un po' di tempo processore.

Sistemi multiprocessore

Se ho più processore, i processori possono essere omogenei, ovveri tutti equipollenti, opppure eterogenei, ovvero un processore è specializzato in una cosa e l'altro in un'altra etc.

Inoltre, la memoria tra i processori può essere condivisa, oppure ognuno ha la sua e guai a chi la tocca.

Infine, anche le periferiche possono essere accessibili indistintamente a tutti i processori, oppure alcuni sì ed altri no.

Se ho processori omogenei e tutto il resto condiviso, allora mantengo una coda per tutti, e mando i processi in coda sul primo processore che si libera. Si chiama load sharing. Il problema è che il bus della memoria può subire tracolli visto che tutti i processori leggono dalla stessa memoria.

Posso fare load sharing anche con memoria locale per ogni processore. Se sposto un processo da un processore all'altro, sposto anche il suo spazio di indirizzamento da un processore all'altro. Devo però tenere in conto il costo di trasferimento dello spazio di indirizzamento, che nel caso della memoria condivisa non c'è

Se ho tutto condiviso ma le periferiche no, devo creare una coda in ogni processore, relativa alla periferica che solo quel processore ha disponibile.

Se invece ho processori omogenei e memoria e periferiche locali, devo avere una coda per ogni cosa e smazzarmi il casino di gestirne mille.

Nel caso dei processori eterogenei, c'è una coda per ogni processore, e sopra di esse una coda per ogni gruppo di processori omogenei.

Multiprocessamento vuol dire che c'è un processore che fa scheduling per tutti, in modo quindi asimmetrico. Altrimenti, se voglio seguire un sistema simmetrico, ogni processore ha il suo sistema operativo e fa la sua parte schedulando i processi a lui assegnati. E queste due suddivisioni sono trasversali alla distinzione tra processori omogenei ed eterogenei.

Lezione 4: scheduling per sistemi Real Time

Hard Real Time

Tutto quanto è in real time, ovvero un processo deve avere la garanzia di terminare entro un tempo massimo a partire dalla sua attivazione.

Il SO può usare diverse tecniche di scheduling.

Una piuttosto radicale è questa: se posso garantire al processo il tempo massimo di esecuzione, allora lo accetto. Se no, non lo accetto. Naturalmente devo poter fare stime del tempo di esecuzione, e non è semplice. E poi devo poter prenotare le risorse prima che il processo arrivi, se no addio tempi stretti. Se il processo è stato accettato, entrerà a far parte dei Sette Nani.

Posso usare il sistema dei processi periodici, in cui i miei processi hanno una scadenza d, ovvero una frequenza 1/p. Vuol dire che i processi vanno eseguiti ogni tot e metterci tat, e la cosa bella è che lo so prima. Ad esempio, lo scheduling dei processi audio può essere fatto così: so che ogni 5 millisecondi devo inviare i dati audio alla scheda audio, e tutti i processi realtime che producono o processano l'audio vengono eseguiti periodicamente entro i 5 ms.

Lo scheduling a frequenza monotòna (notare l'accento sulla terza O) è un caso specifico dei processi periodici visti qui sopra, con l'aggiunta della preemption. Stabilisco per ogni processo una priorità in base al periodo (ovvero la frequenza), oppure priorità statiche, e un processo con priorità alta ne può scalzare un altro.

La politica earliest deadline first (EDF) mi dice che i processi, periodici o anche no, che hanno il tempo di scadenza più vicino vengono eseguiti per primi. Quindi la priorità potrebbe essere vista come 1/d, dove d è la deadline, cioè la scadenza.

Soft Real Time

Non tutti i processi sono critici, e quindi quelli che hanno prerogative real time possono avere la precedenza su quelli non real time. Posso ad esempio stabilire che i processi realtime abbiano una priorità statica, mentre quelli non critici ne abbiano una dinamica.

E si può anche decidere di interrompere le chiamate di sistema: ciò vuol dire che anche il kernel può essere interrotto, e lo diciamo in aperto contrasto con l'assunzione fatta qualche tempo fa che in modalità supervisore il kernel blocca le interruzioni. Anche il kernel quindi può essere vittima di preemption.

Torna alla pagina di Sistemi Operativi