Sistemi Operativi - Gestione VM e Processi

TSL

TSL opera nel seguente modo:

- Sintassi => TSL register, flag

- Semantica => Esegue le istruzioni che seguono come se fosse una sola

o Register <= flag

o Flag <= 1

- TSL può essere usata per implementare le primitive di accesso alla sezione critica (enter_region,

leave_region)

I semafori => Sono variabili interne condivide tra più processi, possono assumere valore unico 0 o 1

(semafori binari) oppure un intero >= 0 (semafori generalizzati).

Utilizzati per:

- Mutua esclusione (inizializzati ad 1)

- Attesa di eventi (inizializzati a 0)

- Contatore risorse (inizializzati a n)

Operazioni sui semafori => Up(sem), Down(sem) e sem = valore (per l’inizializzazione)

Il sistema operativo ne garantisce

l’atomicità, come se fossero una sola

istruzione macchina.

Con i semafori binari => I processi non attendono più in busy waiting, a ciascun semaforo è associata una

cosa in cui vengono posti i processi bloccati. La cosa solitamente viene gestita in FIFO; i processi sono

risvegliati dalla cosa quando un altro processo esegue un operazione di UP sul semaforo su cui son bloccati.

Con i semafori si risolve facilmente il problema della mutua esclusione tra n processi:

- Down (sem) => Entra regione critica

- Up (sem) => Lascia regione critica

I semafori possono essere usati anche per sincronizzare due o più processi.

Con i semafori generalizzati => Le operazioni di down e up hanno la seguente semantica:

Il Deadlock

Riassumendo criticità dei sistemi con esecuzione concorrente:

- Startvation => Situazione in cui l’esecuzione di uno o più thread è posticipata indefinitamente

- Deadlock => Situazione in cui tutti i thread di applicazioni cooperanti sono bloccati in attesa di

accedere ad un risorsa condivisa appartenente ad un altro processo

- Livelock => Situazione in cui tutti i thread di applicazioni cooperanti riescono a svolgere qualche

attività senza mai progredire

Il deadlock è caratterizzato dalla presenza contemporanea di 4 condizioni necessarie per essere verificato:

- Accesso alle risorse in mutua esclusione

- Hold and Wait => Processi in possesso di risorse che possono continuare a richiederne delle nuove,

senza cedere già quelle acquistate anche se rimangono bloccati in attesa

- No Preemption

- Attesa circolare => Due o più processi sono in attesa di risorse usate da un altro processo dello

stesso gruppo

Resource Allocation Graph (RAG) => Stato di rappresentazione di allocazione delle risorse di un sistema.

Un RAG è formato da due insieme di nodi:

- P = {P1,P2.. Pn} che rappresenta i processi

- R = {R1, R2,… Rn} che rappresenta le risorse

- Un arco diretto da un processo ad una risorsa => Pi ha richiesto Ri

- Un arco diretto da una risorsa ad un processo => Ri è in uso da Pi

Ogni risorsa può avere un numero di copie maggiore di uno. Se il grafo non ha cicli non può esserci

deadlock, altrimenti se ne ha uno potrebbe esserci.

- Se il grafo rappresenta un sistema con una sola istanza per ogni risorsa allora c’è sicuramente

deadlock

- Se il grafo rappresenta un sistema con istanze multiple, allora il deadlock è possibile

Nessun ciclo, nessun deadlock Ciclo e nessun deadlock Ciclo e deadlock

Come gestire i deadlock:

- Ignorandoli: quando possibile si cerca di ignorarli

- Prevenzione: si prendono tutte le precauzioni affinchè una delle 4 condizioni necessarie non si

verifichi mai.

o Sistema di Hold and Wait => Quando un processo sta già utilizzando una risorsa non può

richiederne altre

o Circular Wait => Per prevenire l’attesa circolare ordiniamo le risorse assegnandogli un

identificativo numeri e imponiamo che i processi le richiedano rispettando l’ordine

- Rilevazione e recupero: se verifica periodicamente lo stato di allocazione delle risorse; individuata

una criticità di deadlock si killa uno o più processi e si ripristina lo stato iniziale prima che avvenisse

- Evitare(avoidance): attraverso un allocazione pensata delle risorse

Safe Sequecence => E’ una sequenza di esecuzione di processi che garantisce

che tutti i processi possano

essere eseguiti sino al loro completamento, anche assumendo che

richiedano il massimo delle risorse.

Safe State => (Stato sicuro) Stato dal quale è possibile dedurre una sequenza

sicura. E’ uno stato in cui è possibile tutte le richieste dei processi in

esecuzione e garantirne la loro terminazione.

Gestione della Memoria

Memoria => Insieme di locazioni di byte, ciascuna contraddistinta da un indirizzo. La CPU copia l’indirizzo di

una locazione di memoria presente in un’istruzione e lo trasferisce sul bus indirizzi da cui verrà recuperato il

dato presente.

L’accesso alla memoria centrale è una delle operazioni più frequenti effettuate da un processo (accesso ai

dati e al codice) quindi la sua gestione è determinate sulle prestazioni del sistema.

La presenza contemporanea di più processi in memoria e la loro esecuzione concorrente è possibile se il

Memory Manager (MM) è in grado di garantire la loro coesistenza evitando ogni tipo di interferenza non

espressamente richiesta. Scopo del MM è mappare spazi di indirizzi logici sullo spazio degli indirizzi fisici

evitando sovrapposizioni (ogni processo non può avere indirizzi fisici sovrapposti).

Un sistema => Caratterizzato da un unico spazio di indirizzi fisici, in corrispondenza di ogni indirizzo vi è una

locazione di memoria presenta nella RAM

Un processo => Caratterizzato da uno spazio di indirizzi virtuali (o logici), ad ogni indirizzo logico è associato

un dato o un’istruzione

Attività svolte dal Memory Manager:

- Rilocazione (o binding): operazione che definisce la corrispondenza tra elementi di due spazi diversi

degli indirizzi. (attività che può essere svolta anche dal compilatore).

- Protezione: Un processo non può accedere allo spazio fisico e logico di un altro processo, se non

autorizzato

- Sharing: alcuni spazi di memoria fisica possono essere condivisi tra processi

Lo spazio di un programma, prima di essere caricato in memoria, è costituito da nomi simbolici (parliamo di

sorgente del codice) => Lo spazio viene trasformato in spazio logico dal compilatore o linker del

programma, in assoluto o rilocabile.

Spazio logico assoluto => Se in fase di compilazione di è a conoscenza della memoria fisica che dovrà

contenere il processo; qualora lo spazio fisico dovrà essere modificato sarà necessario ricompilare il codice

Spazio logico rilocabile => Spazio logico del programma, associato dal compilatore al programma, che potrà

essere mappato su disco.

Tipi di Binding:

- Early binding (compilatore): Esecuzione codice efficiente, anticipa in fase di compilazione una serie

di verifiche

- Dalayed Binding (linker): Esecuzione codice efficiente, consente compilazioni separate

- Late Binding (VM, linker dinamici): Esecuzione meno efficiente, molto flessibile

Memory Managment Unit (MMU) => Dispositivo HW che mappa indirizzi logici in indirizzi fisici a run-time.

La trasformazione degli indirizzi viene effettuata ogni volta che un indirizzo viene prelevato dalla CPU

dall’istruzione e inviato sul bus indirizzi. La CPU elabora solo indirizzi logici, poi trasformati dalla MMU.

Swapping => Intendiamo procedimento di allocazione / deallocazione di un processo da memoria centrale

in memoria secondaria, per far posto ad un processo da eseguire che non trova più memoria disponibile.

Gestione Della Memoria

Vecchi sistemi:

Partizioni multiple fisse Code separate per ogni partizione, singola coda

di input.

Usati in sistemi statici (es: sistemi di tipo batch).

Problemi con l’avvento di sistemi time sharing =>

Processi di memoria maggiore rispetto a RAM e

a memoria variabile

Partizioni multiple variabili Numero, dimensione e posizione delle

partizioni cambiano con il variare dei

processi in memoria. Stato della memoria

si modifica continuamente.

Problemi riguardanti gli spazi liberi e

occupate della memoria centrale,

frammentazione esterna degli spazi liberi.

Frammentazione esterna => Frazionamento della memoria libera in piccoli pezzi inutilizzabili

Sistemi moderni (cenni):

- Segmentazione

- Paginazione

Strategie di allocazione dello spazio libero:

- First Fit: Riempita la porzione di memoria sufficientemente grande per contenere il processo

- Next Fit: Simile al first fit, con l’aggiunta che la ricerca riprende dal punto in cui si era inserito

l’ultimo processo

- Best Fit: Riempita la più piccola porzione di memoria sufficiente per contenere il processo

- Worst Fit: Riempita la più grande porzione di memoria libera che può contenere il processo

Memoria Virtuale

Introduzione VM

Con il tempo si sono sviluppate diverse esigenze:

- Applicazioni, in termine di codice, hanno aumentato sempre di più la loro dimensione

- Diffusione di sistemi time-sharing con elevati numeri di utenti

- Necessità di gestire in modo efficiente situazioni in cui le applicazioni da gestire superavano di gran

lunga la memoria fisica del sistema (swapping soluzione poco efficiente)

Risposta a queste problematiche fu la tecnica della Memoria Virtuale, che richiedeva due grossi vincoli:

- Permanenza di un processo in memoria nella sua interezza

- Permanenza di un processo in locazioni di memoria contigue

Principi di Località

Località temporale => Se un elemento x viene referenziato all’istante t, si ha con molta probabilità che

l’elemento x venga referenziato all’istante t+t’

Località spaziale => Se un elemento x di posizione s viene referenziato all’istante t, è probabile che venga

anche referenziato l’elemento x’ nello spazio s’.

Grazie a questi principi di località viene suggerito un importante concetto => Non è necessario caricare un

programma interamente in memoria per poterlo eseguire, è sufficiente caricarlo località per località

Vantaggi di Località

- Svincolo dimensione di un programma dalla dimensione della memoria centrale

- Aumento del livello di programmazione, a parità di memoria disponibile

- Maggiore velocità nelle operazioni di swapping

Metodi implementare VM

Overlay

Meccanismo molto primitivo, in cui il programmatore suddivide il programma in porzioni la cui esecuzione

non si sovrappone nel tempo e ogni porzione del programma chiamata overlay. Gli overlay vengono caricati

in memoria dal programmatore su esplicito comando. Ogni programma costituito da almeno un overlay in

memoria.

Paginazione

Eseguito un meccanismo che consente di mappare automaticamente uno spazio di indirizzamento log