Sistema Operativo Architettura degli elaboratori 1 - A. Memo 283 6 Sistema Operativo 6Generalità...

Sistema Operativo Architettura degli elaboratori 1 - A. Memo

1

6 Sistema Operativo6 Sistema Operativo

6 Generalità6.1 Classificazioni e definizioni6.2 Struttura generale6.3 La gestione dei processi6.4 La gestione della memoria6.5 La gestione dell’I/O6.6 File system e protezione6.7 Unix - Windows


2

6. Generalità6. Generalitàle macchine astratte 1le macchine astratte 1

livello 4 : Macchina programmatorelivello 5 : Macchina utente

livello 0 : Macchina digitalelivello 1 : Macchina microprogramma

Offre un insieme diistruzioni più strut-turate che agevolanol’accesso e l’uso dellerisorse dei livelli 0 e 1.Spesso nasconde cosac’è sotto o come fun-ziona. Il linguaggio utilizzato è quello del-le chiamate di sistema.E’ prettamente soft-ware e indispensabile.

livello 2 : Macchina hardware

livello 3 : Macchina Sistema Operativo


3

6. Generalità6. Generalitàle macchine astratte 2le macchine astratte 2

Obiettivi del Sistema Operativo (OS): rendere il calcolatore più semplice da utilizzare ottimizzare l’utilizzo delle risorse

– il SO deve gestire la CPU, la memoria principale e quella secondaria, le periferiche di I/O in maniera efficiente, assicurandone l’accesso ai richiedenti e regolandone la condivisione

gestire l’esecuzione dei programmi utente


4

6.1 Classificazioni e definizioni6.1 Classificazioni e definizioni storia 1storia 1

i programmi venivano inseriti tramite interruttori binari frontali, o lettori di schede perforate

i dati venivano letti tramite led binari, testo stampato o schede perforate

I SO nascono negli anni ‘50, con i primi calcolatori elettronici a programma memo-rizzato


5

6.1 Classificazioni e definizioni6.1 Classificazioni e definizioni storia 2storia 2

negli anni ‘60 si sviluppa il software, nascono compilatori per nuovi linguaggi e tool di sviluppo

il costo elevato e la lentezza delle periferiche (es. caricare un nuovo compilatore) inducono il lavoro a lotti (batch) gestito dall’operatore: un solo programma alla volta, dati compresi


6

6.1 Classificazioni e definizioni6.1 Classificazioni e definizioni storia 3 (batch)storia 3 (batch)

dai batch gestiti dall’operatore si passa al monitor residente (RM) [S.O.batch]– schedulatore sequenziale dei vari job control-

lato da schede perforate le operazioni di I/O sono troppo lente (100-

1000 volte) [S.O. I/O off-line]– direzionare l’I/O verso memorie a nastro

mediante sistemi intelligenti dedicati , e sovrap-posizione tra esecuzione e gestione I/O


7

6.1 Classificazioni e definizioni6.1 Classificazioni e definizioni storia 4 (multiprogramming)storia 4 (multiprogramming)

utilizzo del disco rigido come buffer di I/O molto capiente [S.O. spooling]– Simultaneus Peripheral Operation On-Line, è

più veloce e ad accesso diretto rispetto al nastro utilizzo del disco anche per i programmi

[S.O. multi-programming]– precarico nel disco un insieme di programmi,

appena il primo termina mando in esecuzione il secondo, e così via.


8

6.1 Classificazioni e definizioni6.1 Classificazioni e definizioni storia 5 (time sharing)storia 5 (time sharing)

multi-programming (segue)– se un programma richiede I/O, posso assegnarlo

ad un esecutore meno importante, e continuare con un altro programma

inizialmente c’era grande interattività e poca efficienza, ora alta efficienza ma scarsa interattività: [SO time-sharing]– un quanto di tempo per utente, se lo scambio è

frequente, l’utente potrebbe non accorgersene


9

6.1 Classificazioni e definizioni6.1 Classificazioni e definizioni storia 6 (paralleli)storia 6 (paralleli)

time-sharing (segue)– esecuzione concorrente di più programmi– condivisione della memoria– schemi di protezione e controllo delle risorse

più CPU nello stesso sistema [SO paralleli]– generalmente condividono memoria e I/O– simmetrici, tutte le CPU hanno il medesimo SO – asimmetrici, solo una CPU ha il SO


10

6.1 Classificazioni e definizioni6.1 Classificazioni e definizioni storia 7 (distribuiti e di rete)storia 7 (distribuiti e di rete)

più sistemi utilizzano il medesimo SO [SO distribuiti]– di solito operano su memorie ed I/O distinti– ciascuno ha un’immagine coincidente del SO

più sistemi interconnessi [SO di rete]– finalizzati alla condivisione delle risorse ed alla

comunicazione


11

6.1 Classificazioni e definizioni6.1 Classificazioni e definizioni storia 8 (real time e PC)storia 8 (real time e PC)

gestione prioritaria degli eventi esterni rispetto alla loro elaborazione [SO real-time]– impiegati nei controlli di processo e nei

calcolatori dedicati– nuclei spesso ridotti

SO per personal computer– in corrispondenza alla diminuzione dei costi– via via inglobano le prestazioni degli altri SO


12

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni definizione di SOdefinizione di SO

Definizione di SO:

un Sistema Operativo è un insieme di programmi che assolvono al duplice compito di far vedere all’utente una macchina virtuale semplificata e di gestire in maniera ottimiz-zata le risorse del calcolatore


13

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni componenti di un SOcomponenti di un SO

interfaccia utente

gestore processi

gestore risorse– processore/i– memoria principale– memoria secondaria– dispositivi di I/O

file system

sicurezza e protezione


14

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni definizioni di processodefinizioni di processo

un processo è l’insieme ordinato degli stati che il sistema assume durante l’esecuzione di un particolare programma o parte di esso, a partire da uno specifico stato iniziale

oppure un processo è l’insieme ordinato delle azioni

(operazioni) che il sistema esegue durante lo svolgimento di un particolare programma o insieme di istruzioni


15

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni caratteristiche dei processicaratteristiche dei processi

un programma può determinare più processi in un sistema coesistono processi utente e

processi di sistema i processi vengono creati, sospesi o terminati i processi devono poter comunicare tra loro

e sincronizzarsi i processi avanzano concorrentemente


16

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni gestore dei processigestore dei processi

è il cuore del SO, viene detto anche kernel– deve cambiare di stato i processi, scegliendo

quello o quelli da mandare in esecuzione (scheduling) e ponendo in attesa quelli che richiedono una risorsa occupata

– deve assicurare a tutti i processi la possibilità di avanzare, senza privilegiarne o penalizzarne alcuno

– assicurare un meccanismo di sincronizzazione tra i vari processi


17

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni definizioni di risorsadefinizioni di risorsa

una risorsa è qualsiasi elemento di natura hardware o software condiviso dai processi, necessario alla loro creazione o al loro avanzamento

le risorse possono essere:– riutilizzabili o consumabili– pre-rilasciabili e non– a molteplicità unaria o multipla


18

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni la risorsa processorela risorsa processore

è l’unica risorsa (hardware o software) indispensabile per l’avanzamento di tutti i processi

a livello hardware può essere associato alla CPU

a livello software in un sistema mono-processore il SO può virtualizzarne molti


19

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni la risorsa memoria principalela risorsa memoria principale

è una risorsa riutilizzabile, pre-rilasciabile a molteplicità unitaria se in scrittura, multipla se in lettura

il SO la condivide tra i vari processi, di volta in volta attribuendola e liberandola

la gestione della memoria principale risulta più veloce se viene effettuata a livello hardware


20

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni la risorsa memoria secondariala risorsa memoria secondaria

è una risorsa riutilizzabile, pre-rilasciabile a molteplicità unitaria se in scrittura, multipla se in lettura

il SO ne regola le richieste di accesso, e la può attribuire o recuperare parzialmente ai vari processi


21

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni le risorse gestione dell’I/Ole risorse gestione dell’I/O

sono generalmente risorse riutilizzabili, a molteplicità unaria e non pre-rilasciabili

il SO ne virtualizza l’impiego nasconden-one le caratteristiche hardware e omoge-neizzandone il trattamento

il SO ne regola e condivide l’accesso, richiamando le relative routine proprietarie


22

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni file systemfile system

il file system è la componente del SO che gestisce i file e le directory

il SO garantisce una visione logica della struttura fisica della memoria secondaria

il SO gestisce la creazione, la cancellazione e la modifica delle proprietà dei file


23

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni l’interfaccia utentel’interfaccia utente

è l’insieme delle modalità con cui l’utente può accedere ai servizi offerti dal SO

l’accesso per l’operatore è basato su un interprete dei comandi, che li acquisisce, li decodifica e li esegue

l’accesso per i programmi utente avviene tramite chiamate standard (system call e/o API)


24

6.1 Classificazioni e definizioni 6.1 Classificazioni e definizioni sicurezza e protezionesicurezza e protezione

la sicurezza di un SO è la capacità di svolgere correttamente le sue funzioni anche in presenza di guasti (tolleranza ai guasti) o tentativi di effrazione (protezione e controllo degli accessi)


25

6.2 Struttura generale 6.2 Struttura generale possibili architetturepossibili architetture

S.O. monolitici S.O. a livelli S.O. a macchine virtuali S.O. client server


26

6.2 Struttura generale 6.2 Struttura generale sistemi operativi monoliticisistemi operativi monolitici

insieme paritetico di tutte le componenti che possono richiamarsi li-beramente

paragonabile alla pro-grammazione spaghetti

esempi: MS-DOS ed il primo UNIX

Periferica 1 Periferica 1

prog. 1 prog. 2

MS DOS BIOS


27

6.2 Struttura generale 6.2 Struttura generale sistemi operativi a livelli 1sistemi operativi a livelli 1

suddivisione delle funzionalità del SO in livelli, in modo che ogni componente di un livello possa utilizzare solo le funzioni offerte dal livello sottostante

assicurano modularità e facilità di controllo non sempre la suddivisione a livelli è facile

o definibile


28

6.2 Struttura generale 6.2 Struttura generale sistemi operativi a livelli 2sistemi operativi a livelli 2

nucleo

risorse

superisore

kernel

API

applications

device drivers

OS/2generale

La tendenza attuale è di avere un numero contenuto dilivelli e spostare più funzioni possibile verso l’alto.


29

6.2 Struttura generale 6.2 Struttura generale sistemi operativi a macchine virtuali 1sistemi operativi a macchine virtuali 1

sviluppato in IBM nel ‘79, distingue tra multi-programmazione e interfacciamento alle risorse

sopra al livello hardware opera il Virtual Machine Monitor, che offre al livello superiore più macchine virtuali complete, ciascuna dotata del proprio livello hardware (virtuale) indipendente


30

6.2 Struttura generale 6.2 Struttura generale sistemi operativi a macchine virtuali 2sistemi operativi a macchine virtuali 2

VM/370 Virtual Machine Monitor

ConversationalMonitorSystem

IBM/370virtuale

livello hardware reale

VM/370 IBM


IBM/370virtuale


IBM/370virtuale system

call

I/Oinstr.


31

6.2 Struttura generale 6.2 Struttura generale sistemi operativi client-serversistemi operativi client-server

la tendenza odierna è di avere un kernel minimo e di implementare tutte le altre funzioni nei processi utente

nel client-server il kernel trasferisce solo i messaggi tra i vari processi

kernel

processoclient

processoserver

fileserver

processoclient


32

6.2 Struttura generale 6.2 Struttura generale caricamento del SO 1caricamento del SO 1

Il SO può risiedere permanentemente su ROM

– controllori industriali e sistemi dedicati su disco ed essere caricato all’accensione

(bootstrap)– adatto a sistemi complessi o gestiti da più

sistemi operativi


33

6.2 Struttura generale 6.2 Struttura generale caricamento del SO 2caricamento del SO 2

all’accensione viene eseguito un piccolo programma presente in ROM (Initial Program Loader) che legge la routine di caricamento (OS Loader) presente in una zona predefinita del disco.

questa routine carica il modulo Real Time Executive del SO, che fornisce i principali servizi offerti dal SO


34

6.2 Struttura generale 6.2 Struttura generale sistema operativo elementare 1sistema operativo elementare 1

analizziamo brevemente il nucleo di un SO uniprocessor multiprogramming con time sharing, organizzato a livelli:– supervisor, con funzione di verifica dei diritti e

attribuzione delle risorse– gestione delle risorse, escluso il processore– nucleo o kernel, per la gestione dei processi


35

PRONTO ESECUZIONE

BLOCCATO

crea() termina()

dispatcher()

time_out()

signal() wait()

livellosupervisor

livellokernel

ATTIVATO TERMINATO


36


ATTIVATOil supervisore lo attiva, e richiama la system call (sc) per creare il nuovo PCB

PRONTOil processo è pronto ad andare in esecuzione e rimane in attesa del suo turno

ESECUZIONEal processo selezionato è stato attribuito il processore, e sta avanzando


37


BLOCCATOil processo è sospeso in attesa di una risorsa attualmente non disponibile

TERMINATOil processo ha concluso regolarmente le sue operazioni e si predispone ad “uscire” dal SO


38


crea()immette un nuovo processo nel kernel, aggior-nando la ready-list, o lista dei processi pronti

dispatcher()manda in esecuzione il primo processo della ready-list

time_out()il processo in esecuzione esaurisce il quanto di tempo a sua disposizione e ritorna nella ready-list


39


wait()il processo richiede l’uso di una risorsa, e se questa è occupata il processo viene sospeso

signal()il processo corrente ha liberato la risorsa attesa dal processo bloccato, che passa nella ready-list

termina()il processo in esecuzione termina regolarmente il suo lavoro e rilascia il PCB


40


I compiti del livello kernel sono quindi:– gestire la transizione da PRONTO ad

ESECUZIONE– gestire le interruzioni esterne causate da eventi

di I/O o da situazioni critiche rilevate da altri processi o componenti del SO

– fornire ai livelli superiori le primitive per la gestione dei processi (creazione, terminazione e sincronizzazione)


41

6.3 La gestione dei processi 6.3 La gestione dei processi definizione (vista in precedenza) stati di un processo (visti in precedenza) descrittore dei processi schedulazione dei processi operazioni sui processi i thread (LWP) Inter Process Comunications deadlock


42

6.3 La gestione dei processi 6.3 La gestione dei processi PCBPCB

ogni processo è caratterizzato da un descrittore di processo (Process Control Block) composto da:– identificatore del processo– contesto interno della CPU (registri)– stato di avanzamento– priorità iniziale ed attuale– diritti di accesso alle risorse– processo padre ed eventali processi figli– puntatore alla lista delle risorse assegnate– puntatore alla coda messaggi in arrivo


43

6.3 La gestione dei processi 6.3 La gestione dei processi passaggio tra processipassaggio tra processi

se in un sistema possono avanzare concorrentemente più processi, occorre un metodo per decidere quando passare da uno all’altro– scambio cooperativo (co-operative o non pre-emptive

switching), in cui è il processo in esecuzione che decide quando passare il controllo al processo successivo [Win 3.1]

– scambio a pre-rilascio in cui il processo in esecuzione viene scalzato o da un processo in attesa a priorità maggiore (priority pre-emptive switching) o quando ha esaurito il tempo a sua disposizione (time-sharing pre-emptive switching) [UNIX e Win NT]


44

6.3 La gestione dei processi 6.3 La gestione dei processi schedulazione dei processischedulazione dei processi

I processi possono essere schedulati dalla ready list per mandarli in esecuzione ,

dispatcher, (short-term scheduler) dalla job list, lista dei processi in attesa di

attivazione (long-term scheduler) dalle liste in coda alle risorse di I/O (gestore

delle risorse)


45

6.3 La gestione dei processi 6.3 La gestione dei processi dispatcher 1dispatcher 1

il dispatcher è lo schedulatore più critico in quanto viene richiamato ad ogni scambio

il dispatcher deve cambiare il contesto e ritornare il controllo all’utente

i criteri di valutazione di un dispatcher sono– percentuale di utilizzazione della CPU– numero di processi completati nell’unità di tempo– durata dell’attesa nella ready list


46


la tecnica più semplice di gestione della ready list è la FCFS– il primo processo ad arrivare nella coda sarà il

primo ad essere estratto per mandarlo in esecuzione, e vi rimarrà fino a che non chiede una risorsa o termina

– ottimizza i tempi di scelta ed è facilmente implementabile, ma si blocca se un processo si blocca, non minimizza i tempi di attesa e attribuisce implicitamente priorità maggiore ad un tipo di processi


47


Dati tre processi A, B e C con tempi di esecuzione rispettivamente 2, 5 e 10 mS, i tempi di attesa medi dipendono dall’ordine di esecuzione:A B C t = 9/3 = 3 mS B C A t = 20/3 6,6 mSB A C t = 12/3 4 mS C A B t = 22/3 7,3 mSA C B t = 14/3 4,6 mS C B A t = 25/3 8,3 mS

l’attesa media minore si ha eseguendo prima quelli con tempi di esecuzione minori (SJF, short job first), o in pre-emption SRTF, shortest remaining-time first


48


un processo è generalmente costituito da una sequenza di attività_CPU intervallate da attività_I/O

i processi si possono classificare in– CPU_bound se richiedono poche attività_CPU di

durata molto lunga– I/O_bound se richiedono molte attività_CPU di breve

durata intervallate da attività_I/O molto lunghe la tecnica FCFS penalizza i processi I/O_bound


49


le politiche SJF ed SRTF sono complesse ed onerose da implementare

si possono attribuire priorità diverse ai vari processi (SJF si può considerare a priorità in base al tempo di esecuzione)– i criteri di priorità influiscono le prestazioni– si possono minimizzare i tempi di attesa medi, ma

penalizzare fortemente qualche processo (con il pre-emption si può arrivare anche al blocco)


50


introducendo il concetto di time-sharing, dalla politica FCFS si deriva la tecnica round-robin

Dati tre processi A, B e C con tempi di esecuzione di 2, 5 e 10 mS ed un quanto di tempo di 2 mS:

A

B1

C1

B2

C2

B3

C3 C4 C5

il tempo medio di attesa vale (0+6+7)/3 4,3 mS + (9/3 =) 3 cambi di contesto (che devono essere rapidi)


51


attribuendo ad ogni processo una propria priorità si ottiene la tecnica Multi-level Queue Scheduling– i processi vengono posti in code distinte, uno

per ogni livello di priorità– ogni coda viene gestita con la propria politica– c’è una politica di scheduling tra le varie code– una semplice implementazione è la round-robin

a due livelli: quelli CPU_bound ed I/O_bound


52

6.3 La gestione dei processi 6.3 La gestione dei processi creazione di un processo 1creazione di un processo 1

il programmatore UNIX, per creare un pro-cesso, utilizza la funzione fork() delle APIval fork() attiva un nuovo processo figlio simile

al padre, ma con un proprio PID

val = -1 operazione fork non riuscita

= 0 identifica il processo figlio

> 0 identifica il padre, e gli restituisce il

PID del figlio generato


53

6.3 La gestione dei processi 6.3 La gestione dei processi creazione di un processo 2creazione di un processo 2

#include <stdio.h>#include <sys/types.h>int main(void) { pid_t pid; pid = fork(); if (pid == -1) { fprintf(stderr, "fork() non riuscita\n"); exit(1); } if (pid == 0) { printf("Sono il figlio\n"); exit(0); } if (pid > 0) { printf("Sono il padre del figlio n.%d\n", pid); exit(0); }} /* si noti l’ordine casuale dei messaggi */


54

6.3 La gestione dei processi 6.3 La gestione dei processi processi e threadprocessi e thread

modello a processi• ogni processo ha il pro-

prio spazio di indirizza-bilità

• schemi di sicurezza e protezione semplificati

• scambio di contesto onerosoheavy-weight process

modello a thread• il thread ha una parte di

stato proprio contenuto ed una parte condivisa con tutti i thread dello stesso programma, risorsa o altro

• la creazione e lo scambio di contesto sono più snelle

light-weight process


55

6.3 La gestione dei processi 6.3 La gestione dei processi thread 1thread 1

un thread può essere pensato come una sequenza di istruzioni finalizzate ad un compito elementare specifico

un processo generalmente è scomponibile in più thread

il passaggio da programma a processo/i viene effettuato dal SO

la scomposizione del programma in thread è compito del programmatore


56


lo stato interno di un processo è contraddistinto dai valori assunti dai registri della CPU e dalle informazioni presenti nell’area di stack del processo

un thread (o light process) è spesso visto come un processo il cui stato interno è contraddistinto da un numero inferiore di valori, al minimo il solo IP e lo stack contenente l’indirizzo di ritorno


class Azione implements Nucleo { Object oggetto; Azione(Object a) { oggetto = a; } public void esegui() { // esegue qualcosa su oggetto }}class Programma { static public void main(String args[]) { Object ogg_1 = new Object(); Nucleo Azione_1 = new Azione(ogg_1); Thread t1 = new Thread(Azione_1); Nucleo Azione_2 = new Azione(ogg_1); Thread t2 = new Thread(Azione_2); t1.esegui(); t2.esegui(); // e così via ... }}


58


un thread in Java è caratterizzato dai valori di tutti i registri della CPU e dalle variabili locali della procedura thread, e non dagli oggetti, che vengono assimilati a variabili globali

nei SO multi-threading lo scambio tra i vari thread avviene solo per termine o rilascio spontaneo del thread in esecuzione


59

6.3 La gestione dei processi 6.3 La gestione dei processi avanzamento dei processi 1avanzamento dei processi 1

I processi possono avanzare in maniera sequenziale, nei sistemi uni-processore con un

solo contatore di programma; tipico nei SO monolitici

parallela, nei sistemi multi-processore, per ottenere il massimo delle prestazioni ma con scarsa efficenza

alternata, nei sistemi uni-processore con più contatori di programma, SO a massima efficenza


60


A B C sequenziale

A

B

C

parallela

A1

B

C1

A2

C2

A3

alternata


61


l’avanzamento parallelo e quello alternato comportano l’esecuzione concorrente (reale o simulata) dei processi

in tal modo si possono condividere le risorse, aumentare la velocità di esecuzione globale e implementare il software secondo tecniche modulari


62


L’avanzamento concorrente di più processi può portare a risultati indeterminati. Esempio:

il processo P1 è composto da 2 azioni sequenziali, A e B: (supponiamo A: x=0 e B: y= x+2)il processo P2 è composto da 2 azioni sequenziali, C e D (supponiamo C: x=10 e D: y= x-1)Le possibili sequenze di un avanzamento concorrente sono: A B C D (x=10, y=9) C A B D (x=0, y=-1) A C D B (x=10, y=12) C A D B (x=0, y=2) A C B D (x=10, y=9) C D A B (x=0, y=2)


63

6.3 La gestione dei processi 6.3 La gestione dei processi sincronizzazione dei processi 1sincronizzazione dei processi 1

se due processi non condividono lo stesso stato possono operare concorrentemente

se non soddisfano le condizione di Bernstein non possono operare concorrentemente

conviene limitare la non-concorrenza solo in quei punti in cui effettivamente viene condiviso lo stato, mediante utilizzo di segnali o primitive di sincronizzazione


64


supponiamo che A e B siano due processi che hanno in comune la variabile X, e che inizialmente X valga 10

il processo A deve incrementarla di 2 unità il processo B deve decrementarla di 4 unità entrambi accedono contemporaneamente ad X,

vedono che vale 10: il processo A scrive in X il suo risultato (12), mentre B scrive il suo (6)

alla fine X vale o 12 o 6, in base a chi termina prima, ma il risultato corretto (8) non lo scriverà nessuno


65


per evitare questo problema dobbiamo far si che i due processi accedano in maniera mu-tuamente esclusiva alla variabile condivisa

il metodo più semplice sembra essere quello di utilizzare una variabile lucchetto (flag) che indichi quando la variabile condivisa (X) è in uso ad un altro processo (è detta anche mutex, da mutual exclusion)


66


- il processo A avanza- // deve accedere ad X- test (flag == 0) ? - se SI // X è in uso ritorno al test //aspetto - altrimenti // X è libera flag = 0 // occupo X- uso la variabile X- flag = 1 // libero X

- il processo B avanza- // deve accedere ad X- test (flag == 0) ? - se SI // X è in uso ritorno al test //aspetto - altrimenti // X è libera flag = 0 // occupo X- uso la variabile X- flag = 1 // libero X

altro esempio: lock file di UNIX


67


Questa soluzione ha due problemi: in time sharing non funziona perché il

processo può essere interrotto dopo aver controllato la variabile flag, ma prima di averla modificata (sezione critica)

il processo in attesa consuma risorsa CPU (attesa attiva)


68


per assicurare la mutua esclusione in sezione critica si possono adottare due tecniche:

– disabilitare gli interrupt all’ingresso in sezione critica e riabilitarli in uscita: in tal modo nessuno potrà sospendere le attività del processo; è pericoloso perché si possono perdere interrupt importanti, non va bene nei sistemi multi-processor, è troppo generalizzato e penalizzante

– ricorrere ad una sola istruzione in linguaggio macchina (atomicità del comando) che acquisisca il valore di una variabile e ne forzi successi-vamente il valore ad 1 (istruzione test-and-set) (o con analoga xchg)


69


ancora: TSL reg,flag CMP reg,0 JNZ ancora// sezione critica MOV flag,0

flag a 0 indica risorsa disponibile, ad 1 indica risorsa già in uso.

MOV reg,1ancora: XCHG reg,flag CMP reg,0 JNZ ancora// sezione critica MOV flag,0

TSL reg,flag legge il valore di flag, lo pone nel registro reg, e poi porta flag a 1XCHG reg,flag scambia i valori di flag con reg


70


per evitare di dover programmare in LM, si utilizzano due primitive e la variabile semaforo:– il semaforo utilizza una variabile globale intera S

che non può essere utilizzata direttamente, ma solo tramite due primitive pubbliche atomiche wait() e signal(); per S>0 la risorsa è accessibile, inizial-mente S=1 void wait (int S) {

while (S<=0)do; S --;}

void signal (int S) { S ++;}


71


Se un processo vuole accedere alla risorsa R comune, regolata dalla variabile semaforo sem:

processo{ // avanzamento wait(sem); // usa risorsa R signal(sem); // avanzamento}

wait(s) viene usata per richiedere l’accesso al-la risorsa, e signal(s) per rilasciare la risorsa


72


Se il processo A vuole sincronizzarsi con B, ed essere sicuro di avanzare solo quando B ha già raggiunto un certo punto (all’inizio sem=0) :

processo A{ // avanzamento wait(sem); // avanzamento}

processo B{ // avanzamento signal(sem); // avanzamento}


73


Per evitare di avere attesa attiva, la funzione wait() può bloccare il processo che trova il semaforo occupato, e la funzione signal() può recuperare da una lista FIFO i processi in attesa (se ce ne sono)

Per assicurare l’atomicità di wait() e signal(), si devono disabilitare le interruzioni durante l’esecuzione delle due funzioni

Se il semaforo può assumere solo due valori numerici (0 ed 1) lo si chiama semaforo binario, altrimenti è un semaforo a contatore


74


void wait(struct sem){ sem.valore -- ; if (sem.valore < 0){ add (sem.lista, coda); sleep(chiamante); }}void signal(struct sem){ sem.valore ++ ; if (sem.valore < 0) wakeup(estrai(coda));}

ora il semaforo èuna struttura com-posta da un campointero valore e daun campo lista con tutti i processiin attesa su quelsemaforo


75


per offrire strumenti di sincronizzazione ac-cessibili a linguaggi più astratti, sono stati introdotti i monitors– contengono sia la struttura dati, non accessibile

dall’esterno, che le funzioni per gestirla (analoghi agli oggetti)

– includono anche la coda dei processi in attesa– assicurano la mutua esclusione


76

6.3 La gestione dei processi 6.3 La gestione dei processi InterProcess Communication 1InterProcess Communication 1

adesso che abbiamo stabilito come possiamo condividere l’accesso ad una risorsa, e quindi anche alla memoria, vediamo quali strumenti possono utilizzare i processi per comunicare tra loro:

pipe (condotto) stream (flusso)

socket (porta) signal (messaggio)


77


il pipe è come un canale (buffer) uni-direzionale tra due processi: al suo ingresso un processo può scrivere informazioni ed alla sua uscita un altro processo le può leggere– un pipe può essere non identificabile, se

condiviso tra processo padre e figlio– un pipe è identificabile se ha un ID che lo

contraddistingue, e viene utilizzato da processi tra loro indipendenti, solo tramite il suo ID


78


uno stream è analogo al pipe, ma trasferisce informazioni strutturate

un socket rappresenta una porta di comuni-cazione tra due processi

il messaggio è il sistema più diretto per far interagire due processi, ed è l’unico che opera correttamente in ambienti a memoria non condivisa


79


Il modello a messaggi utilizza due primitive

send (destinazione, messaggio)

receive (mittente, messaggio)

ed una struttura di interconnessione costituita da

canali simmetrici (1 a 1)

canali asimmetrici (1 a N) o (N a 1)

mailbox (N a M)


80

6.3 La gestione dei processi 6.3 La gestione dei processi produttore - consumatore 1produttore - consumatore 1

un processo produce dati ed un’altro li legge per elaborarli, entrambi con tempi variabili

si utilizzano tre semafori ed un buffer– int buffer, contenente N slot di dati (liberi)– sem vuoto, contenente il numero di slot vuoti nel

buffer, inizializzato ad N– sem pieno, contenente il numero di slot con dati

del buffer, inizializzato a 0– sem mutex, per impedire l’accesso simultaneo al

buffer


81


void produttore(){ // produrre dato wait(vuoto); wait(mutex); // invia dato // in buffer signal(mutex); signal(pieno);}

void consumatore(){ wait(pieno); wait(mutex); // leggi dato // dal buffer signal(mutex); signal(vuoto); // consumare dato}


82


si può risolvere anche con il modello a messaggivoid produttore(){ int dato, mess do { // produrre dato receive(consID,mess); mess=dato; send(consID,mess); } while (!finito);}

void consumatore(){ int dato, mess init_buffer(); do { receive(prodID,mess); dato=mess; // consumare dato send(prodID,NULL); } while (!finito);}N NN


83

6.3 La gestione dei processi 6.3 La gestione dei processi stallo 1stallo 1

i processi A e B hanno entrambi bisogno delle due risorse R e Q

A chiede l’accesso alla risorsa R e poiché è libera ne ottiene l’utilizzo esclusivo

B chiede l’accesso alla risorsa Q e poiché è libera ne ottiene l’utilizzo esclusivo

A chiede l’accesso alla risorsa Q, ma poiché è occupata si pone in attesa

B chiede l’accesso alla risorsa R, ma poiché è occupata si pone in attesa(altro esempio: incrocio stradale e precedenza)


84


Conzioni di stallo (o deadlock) necessarie e sufficienti:

– accesso esclusivo alla risorsa

– presenza dello stato di blocco nel SO

– non ricorso alla tecnica del pre-rilascio

– lista circolare chiusa tra processi e risorse


85


Ci sono almeno tre modi per affrontare lo stallo: prevenirlo, cercando che almeno una delle

condizioni precedenti non si verifichi mai ripristinarlo, ammettendo che si possa verificare

lo stallo ma essere in gardo di riconoscerlo ed avere a disposizione una procedura di recupero

ignorarlo, sapendo che la probabilità di stallo è molto bassa, non prendere alcuna cautela contro di esso; se succede, pazienza.


86


Prevenzione sulle cause– accesso esclusivo alla risorsa

per alcune risorse non ci sono alternative

– stato di blocco impossibile da eliminare

– no pre-emption per alcune risorse non è possibile

– attesa circolare difficile ed onerosa da valutare


87


Prevenzione sulla richiesta di accesso– ad ogni richiesta di accesso, verificare se questa

porta allo stallo– in caso affermativo però non si sa bene cosa fare– è oneroso valutare la possibilità di stallo ad ogni

richiesta– un’altra possibilità è di richiedere all’inizio a

tutti i processi quali risorse richiederanno e schedularne l’attività in maniera controllata


88


Riconoscimento– riconoscere lo stallo è molto oneroso: con una

certa frequenza (ogni secondo?) si deve bloccare l’avanzamento del sistema, analizzare lo stato di tutti i processi attivi e verificare se quelli in attesa costituiscono una lista circolare chiusa

– il ripristino da uno stato di blocco può essere effettuato solo terminando uno dei processi


89


Il problema dei cinque filosofi affamati

Cinque filosofi sono seduti ad un tavolo circolare, e ciascuno ha davanti un piatto di spaghetti ed una forchetta alla sua destra. Per mangiare gli spaghetti hanno bisogno di due forchette. I filosofi alternano momenti di meditazione a momenti di alimentazione.


90


soluzione con stallo

1

23

4

5 1

23

4

5 void filosofo_i_esimo(){ while (1) { // medita forchetta_on(i); forchetta_on((i++)%5); // mangia forchetta_off(i); forchetta_off((i++)%5); }}

Sistema Operativo Architettura degli elaboratori 1 - A. Memo 283 6 Sistema Operativo 6Generalità...

Documents

Transcript of Sistema Operativo Architettura degli elaboratori 1 - A. Memo 283 6 Sistema Operativo 6Generalità...