Lezione 6 Sistemi operativi

SCHEDULING PER MULTIPROCESSORI:

Lo scheduling nei sistemi multiprocessore è più

complesso, basti solo pensare alla differenza tra la

gestione di un solo processore che gestisce tutti i

processi, e la geestione di (n) processori che gestiscono

tutti i processi, si evince facilmente che la situazione sia

notevolmente più complessa (bisogna tenere conto di

tutti le CPU di tenerle sempre occupate e allo stesso

tempo cercare di bilanciare il carico di lavoro).

processori omogenei

Si possono avere (tutti uguali) e

processori disomogenei (processori diversi). Ovviamente

nei sistemi multiprocessori vi è forte esigenza del

bilanciamento del carico (load balancing) compito svolto

da degli algoritmi appositamente implementati.

multiprocessing Asimmetrico

Un esempio è il ovvero solo

un processore (master) accede alle strutture del sistema,

e quindi effettua lo scheduling, gli altri (slave) eseguono

programmi utente.

SCHEDULING REAL-TIME:

- Sistemi hard real-time sono dei sistemi in cui ci

sono dei forti vincoli temporali, che vanno

necessariamente rispettati. I processi devono

completare l’esecuzione entro un tempo fissato.

Questo spesso avviene tramite una funzione

implementata chiamata Prenotazione delle risorse,

ovvero un processo che ha questo tipo di vincolo

prenota la CPU. Dopo questo tipo di prenotazione lo

scheduler può accettare o rifiutare. La maggior parte

delle volte lo scheduler NON può rifiutarsi di dare la

CPU, ma se vi fossero i presupposti per rifiutare di

cedere la CPU il processo in questione sicuramente non

verrà mai eseguito.

Questo tipo di sistemi sono sempre di tipo

preemptive.

- Sistemi soft real-time:

Sono processi che hanno vincoli temporali leggeri, ad

esempio i videogiochi.

In questo tipo di sistemi si usano algoritmi di gestione

con priorità.

La priorità dei processi non è decrescente, ovvero un

processo può incrementare la sua priorità ma non può

perderla.

Si usa la prelazione delle system call. A volte ci sono

dei processi che hanno prelazione sulle system call,

ovvero la system call viene bloccata per favorire

l’esecuzione del processo in questione.

Questa è una cosa che non avviene mai in un sistema

operativo poiché non eseguire una system call

equivale a dire bloccare l’esecuzione del sistema

operativo. A fronte di gestione di questo tipo di

chiamate a volte vengono implementate le system call

‘punti di prelazione’

prevedendo dei ovvero le stesse

system call prevedono queste situazioni e nel

momento in cui queste si presentano allora la system

call può essere interrotta solo dopo aver passato

questo punto di prelazione, per assicurarsi che la

system call abbia effettuato almeno una parte della

sua chiamata.

I nostri sistemi operativi possono gestire i sistemi soft real-

time ma non i sistemi hard real-time (quindi gli algoritmi di

gestione di un missile o di una centrale nucleare hanno

sicuramente un sistema operativo ad oc, oppure un

sistema operativo usuale ma modificato);

VALUTAZIONE DI ALGORITMI DI SCHEDULING:

Un algoritmo di gestione (scheduling) prima di essere

messo in commercio va appositamente valutato.

Per fare questo anzitutto bisogna decidere cosa si vuole

ottimizzare, e come poter valutare l’algoritmo. Esistono

approcci teorici atte a questi fini.

Esempio:

- Modellazione Deterministica: Fissati i diversi carichi

di lavoro definisce le prestazioni dei diversi algoritmi

per ognuno dei carichi analizzati;

- Modelli di code: Il sistema viene modellato come un

insieme di server con le code associate; date le

distribuzioni degli arrivi delle richieste si calcola la

lunghezza media delle code, il tempo medio di attesa

ecc.

Quindi in pratica simulo una sequenza dei processi e di

thread e vedo come si comporta l’algoritmo.

CLASSI DI SCHEDULING DI SOLARIS:

Solaris è un sistema operativo utilizzato per macchine-

server, insieme a Linux risulta essere una variante di Unix.

ready

Solaris utilizza un sistema a code multiple, la cui

queque è formata da:

- La coda Real-Time (RT);

- La coda dei processi di sistema (SYS);

- Processi a priorità fissa (FP);

- La coda dei processi a ripartizione equa (FSS);

- La coda Time-Sharing (TS);

- La coda dei processi interattivi (IA);

La coda dei pronti è divisa in sei code, ogni coda è gestita

da un algoritmo di scheduling diverso. Solaris è

completamente basato sui thread (quindi schedula thread,

thread based),

chiamato andiamo ad analizzare come sono

gestiti in base alla priorità:

- PRIORITA’ 0-59:

1)Thread interattivo (IA), essendo dei thread che parla

con l’utente ed essendo l’utente l’elemento lento del

sistema questi sono i thread che hanno priorità più

bassa;

2)Thread a ripartizione del tempo (TS);

3)Thread a priorità fissa (FX);

4)Thread a ripartizione equa (FSS);

- PRIORITA’ 60-99:

1)Thread di sistema (SYS);

- PRIORTA’ 100-159:

1)Thread Real-Time (RT), se io scrivo un programma

soft real-time il sistema Solaris da al programma

priorità più alta rispetto ai thread di sistema;

- PRIORITA’ 160-169:

1)Thread per le interruzioni;

Questo elenco ci dice inoltre che la priorità può cambiare

però entro certi intervalli. La gestione della priorità è

combinata con la gestione del quanto di tempo, più la

priorità è bassa più il quanto di tempo sarà alto. Questa

starvation;

gestione è così implementata per evitare

WINDOWS:

Windows utilizza sei classi di priorità (quindi scheduling a

code multiple) con feedback:

- Real-Time;

- High;

- Above Normal;

- Normal;

- Below Normal;

- Idle priority;

Il feedback deve gestire la prelazione ed il quanto di tempo.

Oltre alle classi di priorità, lo scheduling è computato anche

ai livelli di priorità :

- Time-critical;

- Highest;

- Above Normal;

- Normal;

- Below Normal;

- Lowest;

- Idle; ready queque

Un processo appena arrivato nella entra con

priorità normal (asse y), successivamente, a seconda delle

esigenze, può aumentare o diminuire. Interessante d notare

è che i processi real-time, possono variare da priorità 16-

31, invece tutti gli altri variano da 0-15, questo ci dice che i

processi real-time vengono eseguiti sempre per primi in

windows. Altra caratteristica interessante è la variazione al

cambiare dei livelli di priorità in base alla classe di

appartenenza, quindi il gioco di priorità, si svolge non sugli

intervalli di priorità come Solaris, ma sulla variazione di

questa in base al livello di priorità;

LINUX:

Linux è organizzato con un algoritmo di scheduling con

prelazione basato su priorità con due intervalli (a valori più

bassi corrispondono priorità più alte).

Gli intervalli in questione sono:

- Real-Time: priorità tra 0 e 99;

- Nice: priorità tra 100 e 140,

Come in Solaris i quanti di tempo associati ai processi

variano in base alla priorità che questi possiedono, a

differenza di questo però il quanto di tempo aumenta

all’aumentare della priorità.

starvation,

Per evitare Linux utilizza un principio per il quale

quando un task (processo) utilizza il suo quanto di tempo

deve attendere che tutti gli altri task abbiano consumato il

loro, prima di essere eseguito.

Questo principio può essere attuato grazie alla presenza di

attivo scaduto.

due array, chiamati e

Per spiegare bene:

Nel sistema Linux, c’è una struttura dati chiamata array

delle priorità, che contiene gli indirizzi delle liste dei task

con la stessa priorità.

Come già detto di questi array ne esistono due:

- Attivo

- Scaduto;

L’array attivo contiene i task che hanno ancora a

disosizione di tempo per quel ‘giro’.

L’array scaduto contiene i task che hanno esaurito il

tempo a disposizione per quel ‘giro’.

Una volta finito il giro tutti i processi saranno nell’array

scaduto, a quel punto si scambiano gli array.

Ogni lista è gestita con algoritmo Round-Robin;

SINCRONIZZAZIONE DEI PROCESSI:

Primo aspetto riguardante la sincronizzazione di processi è

l’accesso concorrente da parte di più processi a dati

condivisi. Quando più processi accedono ad informazioni

condivise può verificarsi un fenomeno chiamato

inconsistenza dei dati. Questo fenomeno riguarda

l’evenienza in cui più processi vadano a sovrascrivere uno

stesso dato condiviso in modo che non si sappia più quale

sia il reale valore di quel dato.

Per garantire la consistenza dei dati sono necessari

meccanismi che assicurino l’esecuzione ordinata dei

processi concorrenti.

Poniamo di avere 2 processi che accedono ad una variabile

counter e la cambino. Poniamo che un processo voglia

aumentarla e l’altro voglia diminuirla. Nel caso in cui i due

processi volessero aggiornare la variabile

contemporaneamente, le istruzioni nel linguaggio macchina

(interleaved)

potrebbero risultare interfogliate .

L’interleaving dipende da come i due processi sono

schedulati. Dato che ogni interleaving è possibile, ma

l’ordine interno di ogni istruzione di alto livello deve essere

conservato.

Tornando al nostro esempio abbiamo quindi in 2 processi

diversi, le istruzioni counter++; e counter--;. Che tradotte

in linguaggio Assembly:

- Counter++:

register_1 = counter;

register_1 = register_1 + 1;

counter = register_1

- Counter--:

register_2 = counter;

register_2 = register_2 – 1;

counter = register_2;

Diamo per ipotesi che le due istruzioni avvengano

contemporaneamente, ed assumiamo che counter valga 5.

Le istruzioni avverranno in quest’ordine:

1)register_1 = counter; (register_1 = 5)

2)register_1 = register_1 + 1; (register_1 = 6)

3)register_2 = counter; (register_2 = 5)

4)register_2 = register_2 – 1; (register_2 = 4)

5)counter = register_1; (counter = 6)

6)counter = register_2 (counter = 4)

Come si può notare il valore finale non è corretto poiché la

variabilee counter ha subito un incremento ed un

decremento, perciò il suo valore finale deve essere cinque,

invece risulta essere quattro. Anche nel caso l’ultima

istruzione fosse del processo counter ++ il risultato

sarebbe sbagliato poiché il risultato sarebbe sei.

Questa situazione di