Sistemi Operativi

PROCESSI

​ ​ ​

Il processo è un’entità dinamica utilizzata del sistema operativo per rappresentare una

specifica esecuzione di un programma​ . Ad un processo corrisponde un programma, mentre

ad un programma, possono corrispondere più processi (differenti istanze dello stesso

programma). ​ ​ ​ ​

Un processo possiede alcune proprietà statiche e dinamiche che lo caratterizzano:

- programma​ : codice che il processo sta eseguendo (code region);

- program counter​ : registro della CPU contenente l’indirizzo della prossima

esecuzione;

- registri​ : contenuto dei registri della cpu;

- data region​ : sezione dati sui quali il processo sta eseguendo;

- stack region​ : sezione contenente le funzioni del programma (variabili locali);

…).

- attributi​ : insieme di informazioni per la sua gestione (PID id del processo,

​

Ogni processo evolve durante la sua esistenza: in ogni istante si trova in un determinato

stato​ . I principali stati sono:

- new​ : processo appena invocato;

- ready​ : processo pronto ad essere eseguito del sistema, aspetta una CPU libera;

- running​ : processo ottiene la CPU e va in esecuzione;

- waiting​ : processo in attesa di qualche evento (terminazioni di I/O);

- terminate​ : processo finisce la sua esecuzione.

L’assegnamento di un processo al processo

​

viene chiamato dispatching ed è eseguito

da un particolare modulo del sistema

​

operativo detto dispatcher​ .

​

Il Process Control Block è una struttura che contiene le informazioni su un processo nel

sistema operativo. Le informazioni cambiano continuamente in quanto i processi sono

dinamici, tra esse vediamo:

- pid​ : identificatore del processo (unico statico);

- stato​ : lo stato nel quale in processo si trova;

- valore program counter​ :

- contenuti dei registri della cpu​ :

- informazioni sullo scheduling​ : per gestire i processi che andranno in running;

Il PCB descrive l’​ esecuzione del contesto​ , una fotografia istantanea di come è il processo in

​

quell’istante. Ogni processo ha il suo PCB i quali rientrano tutti nella process table​ , la quale

contiene l’identificatore (pid) e un puntatore alla PCB. ​

Nel PCB vengono salvate le informazioni del processo che passa da stato di running a stato

​ ​

di ready o wait​ , in modo da far ripartire il processo da dove era stato fermato una volta

​

ridata la cpu ovvero rimesso in stato di running​ . ​

I processi competono per utilizzare le risorse, entra in gioco il concetto di code di processi​ .

​ ​

Il sistema operativo gestisce le richieste dei processi tramite: code di scheduling e politiche

​ ​

di scheduling​ . Esistono diverse code: job queue (tutti i processi), ready queue (tutti i

​

processi pronti), device queue​ (tutti i processi in attesa per un I/O).

​

Ogni coda ha un suo scheduler​ . I due principali scheduler sono:

- Long term scheduler​ : decide quali processi, mai stati in memoria, debbano essere

caricati in memoria principale (ready queue) e quali devono restare in memoria;

Inoltre bilancia il caricamento tra processi CPU-bound e I/O bound (grado di

multiprogrammazione = numero di processi caricati in memoria principale);

- Short term scheduler​ : decide a quale processo, tra quelli nella ready queue,

assegnare la CPU. ​

- Medium term scheduler​ : ha il compito di modulare il carico a cui è soggetto il

→

sistema (bilanciare CPU-bound e I/O bound un processo può essere catalogato

​ ​

CPU-bound ma poi passare ad essere I/O bound), tramite operazioni di swap-out e

swap-in​ , ovvero spostando dei processi dalla memoria principale alla memoria

secondaria o viceversa (interessano solo i processi già parzialmente eseguiti).

​ ​ ​ ​

a) Se il processo era ready​ o running diventa ready+swapped​ ;

​ ​

b) Se il processo era waiting​ diventa waiting+swapped​ .

Operazioni sui Processi:

Il sistema operativo deve implementare un insieme di operazioni sui processi:

1) Creazione di un Processo ​

Ogni processo può creare altri processi invocando una apposita system call​ . Il

​ ​

processo creatore è detto padre​ , quello creato è detto figlio​ . Il nuovo processo avrà

un nuovo PID e un nuovo PCB. Il PCB del processo padre contiene le informazioni per

​

identificare i suoi figli. Questo permette di creare delle gerarchie​ di processi.

- Come procedono?

a) padre e figlio continuano in modo concorrente; (unix)

b) padre attende la terminazione del figlio.

- Che codice esegue il figlio?

​

a) figlio duplicato​ (quasi) identico al padre; (unix)

b) figlio carica ed esegue un codice diverso dal padre.

- Quali risorse condividono?

a) figlio condivide (quasi) tutte le risorse del padre; (unix)

b) figlio deve acquisire tutte le risorse necessarie.

​

In Unix vengono attuate quasi sempre le risposte (a), il figlio eredita l'exécution

context (contenuto del PCB) del padre​ , questo non vuol dire che il figlio non possa

creare un codice diverso tramite un’altra system call (​ exec​ ).

​

2) Terminazione di un Processo​ : (+ terminazioni processi android)

Un processo termina, in condizioni normali, eseguendo l’ultima istruzione del suo

​

programma e richiedendo la sua eliminazione tramite exit​ . Il sistema operativo

disalloca le risorse concesse al processo, trasmette informazioni al padre e cancella

la PCB.

La terminazione può avvenire per altri motivi “anomali”:

- violazioni od errori: il sistema operativo uccide il processo;

- richiesta di terminazione da parte di un’altro processo;

- termina il processo padre e quindi terminano tutti i “sottoprocessi”.

Comunicazione tra Processi:

I processi in esecuzione possono influenzarsi, vengono distinti due casi:

- processi indipendenti​ : l’esecuzione di uno non influenza l’esecuzione dell’altro e

​

quindi si verifica la proprietà di riproducibilità​ (non dipende l’ordine di esecuzione);

- processi concorrenti​ : processi che si influenzano e quindi non è garantita la

riproducibilità (aumento stipendio del 10% + bonus 200 euro, è necessario garantire

un processo che avviene prima sennò cambia lo stipendio totale). I processi

concorrenti possono essere:

a) cooperanti​ : processi che cooperano per uno stesso fine (riduzione tempi,

modularità nella soluzione del problema);

b) competitori​ : processi competono per utilizzo di risorse;

I processi concorrenti, quindi, necessitano di meccanismi che supportino lo scambio

di informazioni e dati (​ Inter Process Communication IPC​ ), esistono due modelli:

- Memoria condivisa​ : ambiente globale (blocco di memoria concesso dal OS

derivato da una richiesta di un processo) accessibile da tutti i processi che

​ ​

desiderano cooperare. Questi processi devono essere regolamentarizzati del

programma.

- Scambio di Messaggi​ : utilizzato quando non c’è l’esistenza di un ambiente

globale. Avviene quindi una comunicazione tramite l’invio e la ricezione di

​ ​ ​

messaggi tramite un canale di comunicazione e due operazioni base: send e

receive​ .

- Stesso canale utilizzato da più di due processi?

- Più canali tra due processi?

- Canale monodirezionale o bidirezionale?

- Come vengono gestiti i messaggi?

Non c’è un giusto o sbagliato a queste domane, tutto dipende da cosa

dobbiamo implementare e come lo vogliamo fare. Per ogni risposta verranno

​ ​ ​ ​

realizzate le primitive send e receive in modi differenti.

Le diverse tipologie di canali (comunicazioni) dipendono da questi aspetti:

​ ​ ​ ​

- naming​ : comunicazione può essere diretta o indiretta (anonimato).

Nella comunicazione diretta si nominano esplicitamente i processi che

​

si scambiano il messaggio. Questo è uno schema simmetrico​ , ovvero

due processi stabiliscono un unico canale (identificato dai due

interlocutori). ​

Nella comunicazione indiretta vengono utilizzate le mailbox​ , ovvero

viene spedito il messaggio in uno “scatolone”. La stessa mailbox può

essere utilizzata da più coppie di processi, è necessario quindi stabilire

​

delle politiche di gestione​ ; ​ ​ ​

- sincronizzazione​ : comunicazioni con operazioni sincrone o asincrone​ .

Nell’invio sincrono il processo che spedisce si blocca in attesa che il

messaggio sia ricevuto dal destinatario o nella mailbox. Nella ricezione

​

sincrona il processo che esegue una recieve si blocca in attesa che vi

sia un messaggio disponibile.

Nell’invio asincrono il processo che spedisce non attende la ricezione.

Mentre nella ricezione asincrona non si blocca e viene avvisato nel

caso di ricezione di messaggi.

- buffering​ : tipologia di buffer (spazio nel quale viene mantenuto

temporaneamente il messaggio). I buffer sono gestite dal OS e dei

buffering si studia la capacità:

​

a) capacità nulla​ : non ci sono messaggi in attesa, la send deve

essere bloccante (non c’è buffering);

​

b) capacità limitata​ : c’è un numero massimo di messaggi in coda,

la send deve essere bloccante solo se la coda è piena;

​

c) capacità illimitata​ : la send può essere sempre non bloccante.

THREAD

​ ​

Il processo è un’unità elementare di elaborazione. Però all’interno di un processo si possono

distinguere due aspetti (nel processo queste due entità sono lo stesso oggetto):

- entità che possiede le risorse​ : assegnamento delle risorse (spazio), degli attributi del

PCB, controllo dei dispositivi I/O;

- entità che esegue​ : stato del processo, una priorità, soggetto a scheduling;

Questi aspetti possono essere considerati singolarmente come unità distinte. L’entità che

​ ​ ​ ​

possiede le risorse​ si può chiamare processo​ , mentre l’entità che esegue viene detta thread​ .

​ ​ ​

Il multithreading è una situazione nella quale il sistema operativo, in un singolo processo​ ,

riesce a supportare più thread (flussi di esecuzione). I sistemi in cui vi è un solo thread per

​

processo si dicono single-thread​ . ​

In una situazione di multithreading ogni thread, interno ad un processo, possiede un thread

control block​ (​ TCB​ ) il quale descrive:

​ ​

a) Lo stato​ del thread;

​

b) Il thread context​ (program counter);

​ ​

c) Lo stack​ (execution stack) del thread;

​

d) Una zona di memoria per variabili locali​ accessibili solo al thread. ​

Ogni thread ha accesso alla memoria e quindi tutte le risorse sono condivise​ , quindi è

delegato tutto al programmatore che deve gestire lui come avvengono gli accessi e le

operazioni dei vari thread.

Vantaggi Thread Svantaggi Thread

​ ​

maggior parallelismo (efficienza) maggior difficoltà​ e complessità di

progettazione e implementazione

​ ​

creare un thread di un processo, costa “iniziare fin dall’inizio in modo parallelo”

​

meno​ di creare un intero processo

​ ​ ​

terminazione del thread molto meno flussi di esecuzione non devono interferire

costosa​ della terminazione di un processo

​ ​ ​

switch di contesto​ è molto più veloce​ , accessi dei dati condivisi protetti

bisogna salvare solamente il TCB

​ ​

comunicazioni​ più efficienti​ , non -

coinvolgono tutto il sistema e il kernel

​ ​ ​ ​

Lo scheduling e il dispatching avvengono a livello di thread, quindi le informazioni sono

mantenute nei TCB. In alcuni casi certe operazioni devono essere gestite a livello di

​

processo, ovvero da parte del sistema operativo (​ swapping​ , terminazione del processo​ ).

​ ​ ​ ​ ​

I thread hanno anch’essi degli stati: running​ , ready e blocked (wait). Le principali operazioni

sui thread invece sono:

- spawn​ : creazione di un thread, il quale successivamente potrà creare thread fratelli;

- block​ : il thread si mette in attesa di un evento;

- unblock​ : l’evento atteso si verifica e il thread viene sbloccato e posto in ready;

- finish​ : il thread termina e il suo contesto (TCB) viene deallocato.

Dato che tutti i thread di un processo condividono lo stesso spazio di indirizzamento e tutte

​

le risorse allocate del processo bisogna impiegare meccanismi di sincronizzazione​ . Le

tecniche usate sono le stesse applicate al livello superiore di processi.

Modelli di supporto al multithreading:

Nei sistemi operativi si distinguono due differenti tipologie di thread:

​ ​

- user-level thread ( ULT​ ): thread eseguiti a livello di applicazione, il kernel ne ignora

​ ​

l’esistenza. Un’applicazione ULT utilizza opportune librerie che implementano le

primitive per la gestione dei thread. Partendo da un singolo thread vengono creati

altri thread, questo permette di allocare tutti i thread ad un singolo processo gestito

del kernel. La libreria crea le strutture dati per eseguire lo scheduling tra i thread del

​ ​ ​

processo. Quindi si ha un doppio scheduling: sul processo e sui thread​ .

Vantaggi ULT Svantaggi ULT

switch di contesto tra thread non processo utente può avere tanti thread

richiede l’intervento del kernel ma solamente uno sarà in esecuzione

scheduling specificatamente se avviene una system call bloccante

implementato per la specifica tutti i thread verranno messi in stato di

applicazione waiting (​ jacketing​ )

maggiore portabilità il kernel vedendo un solo processo non

dell’implementazione (modifica librerie) può assegnare multiprocessori

​ ​

- kernel-level thread ( KLT​ ): il kernel esegue sia l'exécution context del processo che

quello di tutti i thread. Lo scheduling avviene sui thread di tutti i processi. Inoltre il

blocco di un thread non implica il blocco dei thread fratelli.

​ ​

Il principale svantaggio è rappresentato del maggior costo dello switch di contesto

tra thread di diversi processi ma anche tra thread di uno stesso processo, in quanto

bisognerà sempre passare alla modalità kernel.

“Fare uno switch di contesto tra due thread nel ULT costa 1/10 che farlo tra due

thread nel KLT.”

E’ molto utile quindi combinare i due approcci per approfittare del vantaggio di ogni singolo

metodo. In questo modo se il sistema è multiprocessore, thread fratelli possono essere

eseguiti contemporaneamente. CPU Scheduling

​ ​ ​ ​ ​

Risolvere un problema di scheduling consiste nel mappare un certo numero di compiti su

​

un diverso numero di esecutori​ , in modo da realizzare gli obiettivi globali del sistema

​

rispettando un prefissato insieme di vincoli​ . ​ ​

Lo scheduler della CPU viene attivato quando si verificano eventi che possono causare uno

switch di contesto​ : interruzione dovuta ad un timer, interruzioni dovute ai dispositivi di I/O,

invocazione di system call (exit), gestione di segnali.

​ ​ ​

Lo scheduler quindi sceglie quale processo eseguire. Successivamente il dispatcher

​ ​

effettuerà lo switch di contesto​ , inizializzerà il program counter (per la prossima istruzione)

​ ​

ed effettuerà il passaggio alla modalità utente​ . Il tempo impiegato del dispatcher è detto

latenza di dispatch​ .

Esistono diversi parametri che possono influenzare la progettazione dello scheduler:

- numero e tipologia processori;

​ ​

- staticità o dinamicità dell’insieme dei task;

​

- online (può cambiare tutto) o offline (conosco tutto) scheduling;

- tempi di esecuzione​ noti a priori o sconosciuti;

​ ​

- presenza o meno di preemption (prelazione):

a) non preemptive scheduling​ , il processo running continua a detenere la CPU

fino a quando termina o cede la CPU (wait). Non gli viene tolta la CPU.

b) preemptive scheduling​ , il processo running può essere interrotto e portato a

stato di ready, magari per concedere la CPU ad un processo più prioritario.

​ ​

- presenza o meno di precedenza tra i task​ (un task deve​ essere eseguito dopo);

​ ​

- presenza o meno di priorità (task “trascurabili” o importanti);

​

- presenza o meno di scadenze (deadline)​ su inizio/terminazione dei task;

​

- presenza o meno di un obiettivo da ottimizzare​ :

​

a) massimo tempo di risposta (tempo che trascorre da quando il processo nasce

a quando viene reso running per la prima volta), minimizzo il massimo;

​ ​

b) tempo medio di completamento​ ;

c) tempo medio di risposta, minimizzo la media;

d) tempo di attesa​ (tempo nel quale il processo sta nello stato ready);

​

e) minimo numero di CPU utilizzate​ , devo massimizzare il numero di CPU

utilizzate contemporaneamente;

​

f) produttività (numero di task completati / tempo), da massimizzare;

g) massimo ritardo rispetto a eventuali deadline, da minimizzare.

​ ​

Lo scheduler e il dispatcher devono essere ottimizzati al massimo in quanto rappresentano,

del punto di vista dell’efficienza, l’entità fondamentali del sistema operativo.

Comportamento CPU:

Il processo alterna sequenze di operazioni di elaborazione (​ CPU-burst​ ) a operazioni di I/O

​ ​ ​ ​ ​ ​ ​

→ →​

(​ I/O-burst​ ). || (P1) usa più CPU CPU-bound​ || (P2) usa più I/O I/O-bound​ ||

Algoritmi di Scheduling dei Processi:

Esistono diverse politiche di scheduling, verranno visualizzati di seguito tramite l’utilizzo di

​

un esempio. Lo scheduling dei processi è rappresentato tramite il diagramma di gantt​ .