Appunti di Architettura - Parte Sistemi Operativi con spiegazioni semplicissime

COME AVVIENE LO SCHEDULING IN LINUX ?

In base alle versioni di LINUX abbiamo varie modalità di gestione dello scheduling



LINUX VERSIONE < 2.5 code multiple con scheduling mediante algoritmo ROUND ROBIN , con

prelazione del processore . Non adeguato a sistemi SYMMETRIC MULTI-PROCESSING

 

LINUX VERSIONE 2.6.0 scheduling A TEMPO COSTANTE e con PRELAZIONE(a complessità O(1))

adeguato ai sistemi SYMMETRIC MULTI-PROCESSING.

Lo scheduling avviene grazie all’ausilio di 2 algoritmi:

1) algoritmo di TIME-SHARING

2) algoritmo di REAL-TIME

Come funziona l’algoritmo di TIME-SHARING in LINUX ?

 appena un TASK è pronto per essere eseguito passa nello stato “ATTIVO”. Esso avrà un SUO

QUANTO DI TEMPO a disposizione per l’esecuzione in CPU. Fino a quando il QUANTO non sarà

scaduto, rimarrà nello stato ATTIVO.

 Appena finisce il QUANTO di tempo, il TASK passa nello stato “SCADUTO”. Non verrà ripresa la sua

esecuzione fino a quando altri quanti relativi ad altri task ( gestiti con priorità ) non saranno tutti

scaduti , e verrà di nuovo il turno del Task iniziale.

COME SI TIENE TRACCIA DEI TASK e dei loro STATI ? (ATTIVO O SCADUTO?)

 

ESISTE una RUN-QUEUE di LINUX che tiene conto di questo! LA RUN-QUEUE contiene DUE

array [uno “ATTIVO” e uno “SCADUTO”] con PRIORITA’ (associata ad un numero intero) E una lista

dei task relativi a quella priorità .

 Nella RUN-QUEUE, quando l’array “ATTIVO” diventa vuoto , l’array “SCADUTO” diventa il nuovo



ARRAY ATTIVO ( si scambiano i ruoli degli array) in questa fase , tutti i task riceveranno nuove

priorità (in maniera dinamica )

 

CONCLUSIONI l’algoritmo di LINUX TIME-SHARING è EFFICIENTE , ma non per processi

INTERATTIVI! 

LINUX VERSIONE 2.6.23 viene introdotto un nuovo scheduler : COMPLETELY FAIR SCHEDULER (CFS)

Vi è l’assegnazione di una PERCENTUALE DI TEMPO DELLA CPU ( e non esistono pertanto dei QUANTI

affidati come nello scheduling delle versioni precedenti).

Esistono 2 versioni di CFS implementabili in LINUX C.V. :



CFS di DEFAULT calcolo della percentuale di tempo sulla base di VALORI di “NICE” per ciascun task



CFS di REAL-TIME è uno scheduling di tipo SOFT REAL-TIME ( che implementa uno STANDARD DI POSIX

chiamato POSIX.1b)

Lo scheduler CFS mantiene un TEMPO DI ESECUZIONE VIRTUALE per ogni task in una VARIABILE chiamata

VRUNTIME(quindi una variabile per ogni task) 

Il Tempo di ESECUZIONE VIRTUALE è associato ad un FATTORE DI DECADIMENTO un task meno

importante ha fattore di decadimento più elevato

Lo scheduler seleziona il prossimo TASK in base al VRUNTIME più piccolo trovato.

CAPITOLO 7 – I DEADLOCK

Cosa sono i DEADLOCK ?

I Deadlock sono degli “STALLI” che possono verificarsi soprattutto nei sistemi MULTIPROGRAMMATI : dei

processi devono attendere di acquisire delle risorse che devono essergli date da altri processi e viceversa.

Quindi un processo ha RISORSE , ma ne attende altre che devono essergli date da un altro processo.

Quest’ultimo magari attende anch’esso delle risorse dal primo.. e così via.

I

QUINDI PROCESSI SONO IN COMPETIZIONE PER L’ACQUISIZIONE di un NUMERO FINITO DI RISORSE.

Nei SISTEMI MULTITHREAD gli STALLI SONO PIU’ FREQUENTI ( perché più threads competono per

accaparrarsi delle risorse (numero finito))

MODELLO DEL SISTEMA DI ACCESSO ALLE RISORSE DA PARTE DEI PROCESSI:

ogni processo deve: 

1) Effettuare una RICHIESTA di RISORSA se la richiesta non può essere soddisfatta subito (perché

già è in uso da altri processi) , il processo che ha fatto la richiesta deve aspettare fino a che la

RISORSA NON SIA DISPONIBILE. [UNA RICHIESTA DI RISORSA VIENE EFFETTUATA MEDIANTE

CHIAMATE DI SISTEMA come “request”(per devices), “open” (per files) , “allocate” (per memoria)

, “wait” ( implementazione tramite semafori)

2) UTILIZZARE LA RISORSA RICHIESTA QUANDO E’ DISPONIBILE

3) RILASCIARE LA RISORSA PER SUCCESSIVI UTILIZZI DA PARTE DI ALTRI PROCESSI RICHIEDENTI [IL

RILASCIO DELLA RISORSA VIENE EFFETTUATO MEDIANTE CHIAMATE DI SISTEMA come

“release”(per devices) , “close” (per files),”free” (per memoria) , “signal”(implementazione

tramite semafori) 

QUANDO SI VERIFICA UN DEADLOCK? un Deadlock può verificarsi se e solo se avvengono

contemporaneamente queste situazioni:

 

MUTUA ESCLUSIONE nel sistema ESISTE almeno una RISORSA che può essere usata da un

PROCESSO PER VOLTA

 

POSSESSO ED ATTESA c’è un processo che possiede già risorse ma ne attende ALTRE (

possedute da altri processi nell’attesa)

 

NON E’ POSSIBILE LA PRELAZIONE una risorsa in stato di “UTILIZZO” dal processo , può essere

rilasciata SOLO ED ESCLUSIVAMENTE se il processo stesso decide di rilasciarla

 

ATTESA CIRCOLARE significa che un INSIEME DI PROCESSI sono in ATTESA CIRCOLARE di

RISORSE :

ESEMPIO : esistono una serie di processi PROCESSO1, PROCESSO2 , PROCESSO3, … , PROCESSOn

PROCESSO1 possiede risorse , ma deve attendere risorse di PROCESSO2

PROCESSO2 possiede risorse , ma deve attendere risorse di PROCESSO3

PROCESSO3 possiede risorse , ma deve attendere risorse di PROCESSO4

. . . . .

PROCESSOn-1 possiede risorse ,ma deve attendere risorse di PROCESSOn

PROCESSOn possiede risorse , ma deve attendere risorse di PROCESSO1!

Che cos’è il GRAFO DI ASSEGNAZIONE DELLE RISORSE?

E’ un grafo che ovviamente serve per assegnare le risorse ai processi. E’ formato da 2 SOTTOINSIEMI:

1) Un sottoinsieme P che contiene tutti i PROCESSI

2) Un sottoinsieme R che contiene tutte le RISORSE CHE POSSONO ESSERE RICHIESTE DAI PROCESSI

E’ composto da questi elementi:

IL PALLINO costituisce un PROCESSO n-esimo

IL QUADRATO rappresenta UNA RISORSA.

I QUADRATINI all’interno del QUADRATO RISORSA rappresentano le ISTANZE DELLA RISORSA. Questa

SINGOLA RISORSA possiede 4 ISTANZE

LA FRECCIA dal PROCESSO verso la RISORSA indica che “IL PROCESSO1 richiede un’istanza della risorsa “

LA FRECCIA da un’istanza della RISORSA verso il PROCESSO1 significa che l’istanza è POSSEDUTA dal

PROCESSO!

GRAFO SENZA DEADLOCK GRAFO CON DEADLOCK

COME ABBIAMO DETTO, affinché vi sia un QUESTA VOLTA c’è DEADLOCK! Perché ? Il

DEADLOCK ,devono verificarsi tutte e 4 le processo3 in maniera CIRCOLARE attende

situazioni precedentemente descritte. NON VI E’ RISORSE possedute dal processo1 ( ATTESA



ATTESA CIRCOLARE! Dato che il processo 3 non CIRCOLARE GARANTITA) tutte e 4 le situazioni



richiede risorse possedute dal PROCESSO1 verificate DEADLOCK SI!

COME SI PREVIENE IL DEADLOCK ? ( come si previene che il sistema entri in uno stato di DEADLOCK?)

SI POSSONO ADOTTARE VARIE STRATEGIE:

1) EVITARE che si verifichino contemporaneamente MUTUA ESCLUSIONE , POSSESSO E ATTESA ,



NON PRELAZIONE e ATTESA CIRCOLARE basta fare un USO RIDOTTO DELLE RISORSE e

RIDURRE il THROUGHTPUT! 

2) E’ concesso al sistema di entrare in uno stato di deadlock. il sistema vi entra , poi avviene un



ripristino dal deadlock Per ripristinare le funzionalità del Sistema occorre appoggiarsi a 2

algoritmi: un algoritmo di RILEVAMENTO DEI DEADLOCK + un algoritmo per il RIPRISTINO DEL



DEADLOCK QUESTO COMPORTA DEI COSTI AGGIUNTIVI per MEMORIZZARE informazioni

necessarie ai due algoritmi

 viene

ALGORITMO DI RILEVAMENTO DEI DEADLOCK utilizzato dal sistema in base alla



frequenza di accadimento dei DEADLOCK e del numero di processi influenzati da essi Può

essere usato dal sistema secondo 2 modalità: alcuni sistemi richiamano l’algoritmo in maniera

del tutto casuale, altri richiamano l’algoritmo ad intervalli regolari , o quando l’uso della CPU

scende sotto un limite percentuale ( di solito il 40%)

 

ALGORITMO DI RIPRISTINO DEL DEADLOCK viene utilizzato dal sistema per TERMINARE

tutti i processi in STATO DI DEADLOCK ( “ABORT” dei processi) in un ordine preciso che

dipende da vari fattori come : PRIORITA’ del PROCESSO, RISORSE IMPIEGATE, TIPO DI

PROCESSO ( se interattivo o processo batch) ecc…

3) Il sistema IGNORA I DEADLOCK ( Windows , LINUX e UNIX adottano questa strategia)

4) Limitare RICHIESTA e UTILIZZO delle RISORSE da parte dei PROCESSI

PREVENIRE I DEADLOCK comporta che il sistema SIA POCO PRODUTTIVO!

COME RISOLVERE? EVITARE COMPLETAMENTE I DEADLOCK!

 Ogni processo che richiede risorse e possiede risorse deve rendere esplicito il numero max di

risorse che potrà usare nel corso della sua esecuzione (fino a che il processo non terminerà)

 Esiste un apposito ALGORITMO chiamato deadlock-avoidance che controlla DINAMICAMENTE lo

STATO DI ALLOCAZIONE delle varie risorse cercando di evitare che si verifichi ATTESA CIRCOLARE.

[ LO STATO DI ALLOCAZIONE è composto da 3 variabili: numero max di risorse disponibili,

numero max di risorse allocate , numero max di richieste da processi]

STATO SICURO ( inerente all’allocazione delle risorse):

ogni volta che un processo fa richiesta di una risorsa che è DISPONIBILE ( quindi non posseduta da altri

processi) , il SISTEMA CONTROLLA che l’ALLOCAZIONE immediata di tale risorsa LASCI IL SISTEMA in uno

STATO SICURO ( lo stato sicuro è una sequenza sicura di esecuzione di processi)

Quando una sequenza di processi mantiene il sistema in uno STATO SICURO?

Una coda di processi ( PROCESSO1, PROCESSO2, PROCESSO3 … ) è in uno STATO SICURO se le RISORSE che

un PROCESSO i-esimo può richiedere possono essere allocate sfruttando : RISORSE DISPONIBILI + RISORSE

POSSEDUTE da tutti i processi precedenti.



STATO SICURO DEL SISTEMA ci si tiene alla larga dai DEADLOCK

L’algoritmo di deadlock-avoidance garantisce che il SISTEMA si mantenga sempre in uno STATO SICURO

Quali sono gli algoritmi per evitare i DEADLOCK?

 Se nel sistema abbiamo RISORSE TUTTE AD UNA SOLA ISTANZA, basta affidarsi ad una versione



LEGGERMENTE modificata del GRAFO DI ASSEGNAZIONE DELLE RISORSE vengono aggiunte

frecce tratteggiate[dette “Archi di Reclamo”] per indicare che “IL PROCESSO PUO’ RICHIEDERE LA



RISORSA IN FUTURO” la freccia tratteggiata diventa freccia continua quando il PROCESSO usa

EFFETTIVAMENTE la RISORSA (l’istanza della risorsa)

 Se nel sistema abbiamo RISORSE CON VARIO NUMERO DI ISTANZE ci si affida ad un algoritmo

chiamato “ALGORITMO DEL BANCHIERE”

ALGORITMO DEL BANCHIERE[FUNZIONAMENTO]

1) Ogni processo deve dichiarare il NUMERO MAX di RISORSE che pu&ogra