Appunti di Sistemi operativi

A.A. 2017/2018

Enrico Martini VR406823

Prof. Graziano Pravadelli

Servizi di un S.O.

– Esecuzione di programmi

– Operazioni di I/O

– Manipolazione del file system

– Comunicazione

– Rilevamento di errori (logici e fisici)

– Allocazione delle risorse

– Contabilizzazione delle risorse

– Protezione e sicurezza

ARCHITETTURA DI UN SISTEMA OPERATIVO

SISTEMI MONOLITICI

Sistemi embedded semplici, in cui i programmi non hanno una gerarchia e sono strettamente dipendenti

dall’hardware utilizzato. In questo caso il problemi era nella difficoltà di effettuare test e debug.

SISTEMI A STRUTTURA SEMPLICE

In questa evoluzione è stata introdotta una minima organizzazione gerarchica (anche se molto flessibile), che

mira a ridurre i costi di sviluppo e manutenzione. Ogni programmatore però poteva accedere

incondizionatamente all’hardware. Esempi di questo sistema sono stati MS-DOS e i primi Unix.

Struttura di MS-DOS:

Struttura di Unix:

SISTEMI MODERNI

Nei moderni sistemi, i servizi sono divisi per livelli gerarchici. Ogni livello può usare solamente funzioni fornite

da livelli inferiori e definisce precisamente il tipo di servizio e l’interfaccia al livello superiore nascondendone

l’implementazione. Questa modularità porta a una maggior facilità di manutenzione e miglioramento del

sistema. Questo tipo di sistema però ha anche degli svantaggi: è difficile definire appropriatamente gli strati,

oltre a una minor efficienza (ogni strato aggiunge overhead alle system call) e a una minor portabilità. Il primo

computer con architettura a strati è stato il THE (1968).

SISTEMI BASATI SU KERNEL

I sistemi basato solo su kernel sono composti solo di due livelli: un livello kernel e un livello non kernel. Questi

sistemi hanno gli stessi vantaggi dei sistemi moderni, ma senza avere troppi livelli. Un aspetto negativo

consiste nel fatto che non è generale come un sistema a livelli e un kernel troppo tende a diventare

monolitico.

SISTEMI CLIENT-SERVER

Modello utilizzato in sistemi operativi distribuiti e in alcuni servizi di tutti i sistemi operativi moderni. Tutti i

servizi del sistema operativo sono realizzati come processi utente (client). Ogni client chiama un processo

servitore (server) che dopo l’esecuzione restituisce il risultato.

PROCESSO

Un processo è un programma in esecuzione. Un processo richiede determinate risorse assegnate al momento

della sua creazione o durante l’esecuzione, quali tempo di elaborazione della CPU, memoria, file e dispositivi

I/O. In un moderno sistema multiprogrammato i processi evolvono in modo concorrente.

IMMAGINE DI MEMORIA

Nella sezione dati vengono salvate le variabili globali, lo stack invece è riservato

alle variabili locali e alle funzioni. Lo heap consiste nella memoria allocata

dinamicamente, nella sezione riservata al codice è contenuta la parte statica del

codice, le istruzioni. Infine, nella sezione Attributi è contenuto il PCB (Process

Control Block), che tiene conto:

- Stato del processo

- PC (Program Counter)

- Valore dei registri

- Informazioni sulla memoria

- Informazioni sullo stato dell’I/O

- Informazioni sull’utilizzo del sistema

- Informazioni di scheduling

STATI DI UN PROCESSO

Durante la sua esecuzione, un processo evolve attraverso diversi stati (ogni OS ha diagrammi di stato diversi).

OPERAZIONI SUI PROCESSI

Un processo può generare un figlio, che ottiene le risorse necessarie o dal padre o dal OS. In questo caso si

può verificare un’esecuzione sincrona (il padre attende la terminazione del figlio) e asincrona (evoluzione

parallela di padre e figli).

In ambiente Unix per la creazione di processi figli vengono utilizzati:

- fork() = crea un figlio duplicato esatto del padre;

- exec() = il processo padre carica sul figlio un processo diverso;

- wait() = sincronizza l’esecuzione tra padre e figlio.

Un processo può terminare quando finisce la sua esecuzione oppure viene terminato forzatamente dal padre

o dall’OS.

I processi tra loro possono essere:

- INDIPENDENTI: non condivide, non influenza e non è influenzato dagli altri;

- COOPERANTI: esecuzione non deterministica e non riproducibile. Vengono implementati per

condividere informazioni e accelerare alcuni calcoli in parallelo su multiprocessore.

THREAD

Un thread è l’unità base d’uso della CPU e comprende:

- ID (Identificatore di thread)

- Contatore del programma

- Insieme di registri

- Stack

Condivide con gli altri thread che appartengono allo stesso processo:

- Codice

- Dati

- File

Programmi tradizionali, composti da un unico thread sono chiamati anche processi pesanti.

Un processo multithread invece è in grado di volgere più istruzioni in modo concorrente. La maggior parte

delle applicazioni moderne sono multithread, perché possono eseguire diverse attività che utilizzano

intensivamente la CPU in parallelo e sui diversi core di elaborazione.

VANTAGGI

1) TEMPO DI RISPOSTA: Un programma può continuare la sua esecuzione anche se una parte di esso è

bloccata (ad esempio sta aspettando uno specifico input);

2) CONDIVISIONE DELLE RISORSE: le thread condividono di default memoria e risorse di un processo,

mentre per processi diversi non è così immediato e bisogna ricorrere a strumenti come la memoria

condivisa o lo scambio di messaggi;

3) ECONOMIA: La creazione e la gestione (contest switch) di un processo richiede in generale molte più

risorse rispetto alla creazione di una thread;

4) SCALABILITA’: le thread si possono eseguire in parallelo su CPU multiprocessore.

STATI DI UNA THREAD

Una thread ha gli stessi stati di un processo (pronta-in esecuzione-in attesa) ma lo stato di un processo può

anche non coincidere con lo stato di una thread.

IMPLEMENTAZIONE DI UNA THREAD

1) USER-LEVEL THREAD

La gestione delle thread è affidata alle applicazioni, il kernel ne ignora l’esistenza. Tutte queste

funzionalità sono disponibili tramite una libreria di programmazione. È comodo perché non è necessario

entrare in modalità kernel per utilizzare le thread, lo scheduling può variare a seconda dell’applicazione

e le applicazioni possono girare su qualunque OS senza dover modificare il kernel. D’altro canto però il

blocco di una thread bloccherà l’intero processo e soprattutto per ogni processo ci sarà una sola thread

in esecuzione.

2) KERNEL-LEVEL THREAD

Gestione affidata completamente al kernel, le applicazioni per usare le thread si servono dei contest

switch. Il blocco di una thread non blocca il processo, più thread dello stesso processo potranno essere

eseguite contemporaneamente e anche il OS potrà essere multithread. Questo approccio porta però

scarsa efficienza, in quanto ogni volta che si deve cambiare thread si deve passare per il kernel.

3) APPROCCI COMBINATI

GESTIONE DEI PROCESSI DEL SISTEMA OPERATIVO

Il OS è un programma a tutti gli effetti, e come tale si può gestire in modo che:

1) KERNEL ESEGUITO SEPARATAMENTE

Tipico approccio dei primi sistemi operativi, l’OS possiede uno spazio riservato in memoria, è sempre in

esecuzione in modo privilegiato e può prendere il controllo del sistema. Così facendo il concetto di

processo è quindi applicabile solo ai processi utente.

2) KERNEL ESEGUITO ALL’INTERNO DI UN PROCESSO UTENTE

I servizi del sistema operativo sono procedure chiamabili da programmi utente, accessibili in modalità

protetta (kernel mode). Nello spazio di memoria dedicato ad ogni processo, sono presenti anche il kernel

stack (per le chiamate a funzione) e il codice/dati del OS condiviso tra processi utente. Così facendo in

caso di interrupt/trap serve solo un mode switch (user mode - kernel mode) evitando un contest switch,

alleggerendo la procedura. Dopo il completamento del lavoro in kernel mode, l’OS potrà decidere se

riattivare lo stesso processo con un mode switch oppure cambiare processo con un contest switch.

3) KERNEL ESEGUITO COME PROCESSO

I servizi del OS sono processi individuali eseguiti in modalità protetta. Solo una minima parte del OS è al

di fuori di tutti i processi, come ovviamente lo scheduler. È molto vantaggioso per i sistemi

multiprocessore perché potranno eseguire i processi dell’OS in un processore ad hoc.

SCHEDULING

Funzione attraverso la quale si decide quale processo va mandato in esecuzione. L’obiettivo della

multiprogrammazione è avere sempre un processo in esecuzione, in modo da massimizzare l’utilizzo della

CPU. Si tengono contemporaneamente in memoria più processi e quando un processo deve attendere un

evento, il sistema operativo gli sottrae il controllo della CPU per cederlo a un altro processo.

CPU burst: sequenza di operazioni d’elaborazione eseguite dalla CPU.

I/O burst: sequenza di operazioni di input/output.

TIPI DI SCHEDULER

Esistono 2 tipi di scheduler:

- A LUNGO TERMINE (JOB SCHEDULER)

Seleziona i processi da portare dalla memoria alla ready queue. Deve essere molto veloce!

- A BREVE TERMINE (CPU SCHEDULER)

Seleziona quale processo eseguirà la CPU. Può essere un po’ più lento e deve tenere conto del grado di

multiprogrammazione e il mix dei processi (CPU-bound o I/O bound). Può essere assente.

I sistemi operativi con memoria virtuale usano uno scheduler a medio termine per la momentanea rimozione

(swapping) di un processo dalla CPU, riducendo il grado di multiprogrammazione.

DISPATCHER

Un elemento principale coinvolto nella funzione di scheduling della CPU è il dispatcher, il modulo che passa

effettivamente il controllo della CPU al processo scelto dallo scheduler a breve termine.

Questa funzione comprende:

- Contest Switch

- Passaggio a User-mode

- Salto alla posizione esatta del programma utente

Il tempo richiesto dal Dispatcher è noto come latenza di dispatch.

CPU SCHEDULER

Ogni volta che la CPU passa nello stato d’inattività, il sistema operativo sceglie per l’esecuzione uno dei

processi presenti nella ready queque. Generalmente gli elementi presenti nelle code sono i PCB (Process

Control Block) dei processi.

Vi sono 4 circostanze durante le quali lo scheduler deve effettuare una scelta:



1) Esecuzione Attesa



2) Esecuzione Pronto



3) Attesa Pronto



4) Esecuzione Terminazione

Data la frequenza di invocazione, necessita di algoritmi di Scheduling. Quando uno scheduler interviene solo

nelle situazioni 1 e 4 si dice che è senza prelazione o cooperativo (nonpreemptive/cooperative); altrimenti si

diche che lo schema di scheduling è con prelazione (preemptive).

SCHEDULING CON PRELAZIONE

Per prelazione si intende il rilascio forzato della CPU. In uno schema di scheduling con prelazione il processo

che detiene la CPU può essere forzato a rilasciarla prima del termine del burst.

METRICHE DI SCHEDULING

PRODUTTIVITA’ (throughput): numero di processi completati per unità di tempo.

TEMPO DI ATTESA (waiting time): quantità totale di tempo spesa da un processo nella coda di attesa.

TEMPO DI COMPLETAMENTO (turnaround): tempo necessario ad eseguire un particolare processo dal

momento della sottomissione al momento del completamento. È il tempo totale, somma di tutti gli altri

tempi.

TEMPO DI RISPOSTA (response time): tempo trascorso da quando una richiesta è stata sottoposta al sistema

fino alla prima risposta del sistema stesso.

Un buon algoritmo di scheduling dovrà massimizzare l’utilizzo della CPU e il throughput, minimizzando il

tempo di turnaround, il tempo di attesa e il tempo di risposta.

ALGORITMI DI SCHEDULING

1) FCFS (First-Come First-Served)

Quando la CPU è libera, la si assegna al primo elemento che si trova in testa alla coda, rimuovendolo da

essa. È un algoritmo che si basa su una coda FIFO. L’implementazione è molto semplice ma il tempo

medio di attesa è spesso abbastanza lungo e difficilmente prevedibile. Si può verificare infatti un effetto

convoglio, in cui tutti i processi attendono che un lungo processo liberi la CPU. Essendo senza prelazione,

risulta particolarmente problematico nei sistemi in time sharing.

2) SJF (Shortest Job First)

Si assegna la CPU al processo che ha la più breve lunghezza della successiva sequenza di operazioni della

CPU. Se due processi della successiva sequenza di operazioni della CPU. Se due processi hanno la stessa

lunghezza si applica lo scheduling FCFS. SJF è ottimale per quanto riguarda il tempo di attesa medio per

un dato insieme di processi. La vera difficoltà di questo algoritmo sta nella predizione della durata di un

processo perché non esiste un modo per sapere con certezza quanto durerà un determinato processo

prima di averlo eseguito. Esso si stima calcolando la media esponenziale delle lunghezze dei processi

precedenti. (1

= ∗ + − ) ∗

+1

Dove t contiene le informazioni più recenti e tau la storia passata; solitamente alpha vale ½.

L’algoritmo può essere con prelazione e senza prelazione. Se SJF è con prelazione, allora un processo

potrà essere prelazionato per fare spazio ad un nuovo processo appena subentrato, il cui CPU burst è

inferiore a quello che dovrebbe occupare il vecchio processo per terminare.

3) CON PRIORITA’

Si associa una priorità a ogni processo e si assegna la CPU al processo con priorità più alta. Le priorità

sono rappresentate da un intervallo fisso di numeri. Le priorità si possono definire internamente o

esternamente. Quelle internamente usano quantità misurabili per calcolare la priorità, come limiti di

tempo, requisiti di memoria, ecc. Quelle esternamente si definiscono ad esempio con la maggiore

importanza di un processo o dei fondi pagati per l’uso del calcolatore. È un algoritmo sia con prelazione

che senza prelazione. Il problema dell’attesa indefinita (starvation) può essere risolto con la soluzione

dell’invecchiamento (aging), una tecnica di aumento graduale della priorità con il passare del tempo.

4) HRRN (Highest Response Ratio Next)

Specifico algoritmo a priorità senza prelazione, in cui la priorità è data da:

=1+

È maggiore per valori di R più alti e dipende molto anche dal tempo di attesa. Essa va ricalcolata al termine

di un processo se nel frattempo ne sono arrivati altri oppure al termine di ogni processo. I processi favoriti

sono coloro che occupano per poco tempo la CPU e quelli che hanno atteso per molto.

5) RR (Round Robin)

L’algoritmo di scheduling circolare è stato studiato per i sistemi in time-sharing ed è simile all’algoritmo

FCFS, ma aggiunge capacità di prelazione. Ciascun processo riceve una piccola quantità fissata nel tempo

di CPU, chiamata quanto di tempo o porzione di tempo (time slice); la ready queque è trattata come una

coda circolare. Se il processo termina prima del quanto di tempo, la CPU viene passata automaticamente

al processo successivo. In caso contrario, il processo che non ha finito viene prelazionato con un contest-

switch. Il tempo di attesa medio è abbastanza lungo. In generale, le prestazioni dipendono molto dalla

dimensione del quanto di tempo. Nel caso in cui il quanto di tempo sia molto lungo, si ridurrebbe

all’algoritmo FCFS. Se è troppo breve, ci sarebbero troppi contest-switch a rallentare il tutto. Perciò il

quanto di tempo deve essere molto ampio rispetto al tempo impiegato per il contest-switch, ma non

troppo grande (l’80% dei processi deve essere più breve del quanto di tempo). È l’algoritmo più utilizzato

in assoluto nei moderni sistemi operativi.

VALUTAZIONE DEGLI ALGORITMI

- Modello deterministico

Basato su un carico di lavoro finito, definisce le prestazioni solo per quello specifico caso. È utile quasi

solo per presentare l’algoritmo.

- Modello a reti di code

Non utilizza un carico di lavoro finito, ma è basato su una distribuzione di probabilità che simula il

funzionamento del sistema operativo.

- Simulazione

Risultati abbastanza precisi a fronte di una implementazione abbastanza costosa.

- Implementazione

Unico vero modo per valutare un algoritmo di scheduling, scelta però molto costosa.

SINCRONIZZAZIONE TRA PROCESSI

Un processo cooperante è un processo che può influenzarne un altro in esecuzione nel sistema oppure essere

influenzato. L’accesso concorrente a dati condivisi può causare situazioni di incoerenza degli stessi dati.

Considerando il modello astratto del produttore-consumatore, in cui un processo carica dati e un altro

processo scarica dati dallo stesso buffer limitato.

Il problema principale di questo buffer P/C è che counter++ e counter-- sono molte istruzioni in linguaggio

assembly, e tra una microistruzione e l’altra potrebbe avvenire un interrupt!

I due processi potrebbero creare incoerenza di dati nella cosiddetta sezione critica (race condition).

SEZIONE CRITICA

La sezione critica è una porzione di codice in cui si accede ad una risorsa condivisa (come la modifica di una

variabile). Per non cadere in errori, ogni algoritmo che risolva il problema della sezione critica deve rispettare

3 criteri:

1) MUTUA ESCLUSIONE

Solo un processo alla volta può accedere alla sezione critica

2) PROGRESSO

Solo i processi che stanno per entrare nella sezione critica possono decidere chi entra e la decisione non

può essere rimandata all’infinito.

3) ATTESA LIMITATA

Deve esistere un massimo numero di volte in cui un processo può entrare di seguito.

Per risolvere questo problema esistono soluzioni software (aggiunta di codice alle applicazioni senza

supporto h