Definizione di Sistema Operativo

Definizione di Sistema Operativo

Un Sistema Operativo (SO) è un software, quasi sempre molto complesso, che virtualizza una macchina reale (elaboratore elettronico) e le sue risorse, gestendone e coordinandone l'uso da parte delle applicazioni. Il SO crea un ambiente di lavoro nel quale le applicazioni vengono eseguite ed assegna (alloca) loro le risorse della macchina reale in base alle richieste e alla disponibilità. Il SO è schematizzabile come costituito da un nucleo detto Kernel (insieme di tutto ciò che può essere eseguito sulla macchina in stato supervisore, normalmente interdetto all'utilizzo da parte dell'utente, e responsabile della creazione dell'ambiente di lavoro) e da un interprete dei comandi (espressi in apposito linguaggio di comando simbolico detto JCL, Job Control Language) detto Shell (si pensi al prompt dell'MS-DOS

Per i primi sistemi di elaborazione l'unico tipo di programmazione previsto era il Linguaggio Macchina (il programmatore si occupava di tutto: algoritmo, controllo periferiche, settaggio dei bit di stato, flag del processore, e così via). I primi SO erano semplici insiemi di Drivers, programmi che fungono da interfaccia tra l'unità centrale e i dispositivi periferici. Successivamente fu ideato il primo programma Caricatore, il cui compito era caricare programmi e dati, da schede perforate o nastri magnetici, nella memoria dell'elaboratore (un programma in linguaggio simbolico poteva richiedere per la sua esecuzione più operazioni di caricamento prima l'opportuno compilatore che generava il testo in Assembly, poi l'assemblatore che produceva il codice oggetto in formato binario e che veniva infine caricato in memoria per l'esecuzione). La necessità di limitare progressivamente l'uso delle schede perforate diede impulso alla creazione di macchine dedicate al trasferimento dei "contenuti" da schede perforate a nastri magnetici e, poiché se ne occupava un operatore umano, fu presto evidente che il processo di trasferimento era tanto più efficace se applicato ad un numero considerevole di schede per volta: nacque il concetto di Batch o Lotto. Si capì che la CPU di una macchina poteva essere sfruttata per eseguire alternativamente diversi Processi attivi purchè questa Multiprogrammazione (e i problemi che comportava) fosse opportunamente gestita. Il trasferimento di contenuti dalle schede perforate venne presto indirizzato alle unità a disco (che hanno il vantaggio di essere ad accesso casuale, anziché sequenziale come i nastri magnetici) e la procedura adottata prese il nome di Spooling (Spool è acronimo di Simultaneous Peripheral Operations On-Line e si riferisce allo spostamento di immagini di lavoro, da svolgere o da inviare a dispositivi periferici, attraverso la temporanea memorizzazione in un buffer, in memoria o più frequentemente su disco rigido): in pratica i contenuti delle schede perforate e dei nastri venivano massicciamente trasferiti a lotti su unità a disco, indicizzati in una tabella, in modo da poter essere poi all'occorrenza caricati in memoria su richiesta di utenti e programmi in tempi molto rapidi grazie all'accesso casuale dei dischi; naturalmente lo Spooling valeva non solo in Input ma anche in Output, consentendo di usare il disco come buffer temporaneo per l'invio differito nel tempo di dati a dispositivi periferici (la più comune applicazione dello Spool è proprio lo spooling di stampa, un sistema che attraverso una coda FIFO è in grado di somministrare ad una stampante una grande quantità di pagine, secondo i tempi che le sono congeniali, agendo in background, in modo che, durante la stampa, i tempi morti della CPU siano sfruttati dall'utente per eseguire processi a più alta priorità); con questo meccanismo era possibile caricare su disco un grosso pool di jobs, trasferirne di volta in volta una parte in memoria ed eseguirli uno per uno fino ad esaurimento, attingendo quando necessario direttamente dal disco i dati utili, con la possibilità di swappare un processo (in attesa di un evento o sospeso) su disco a vantaggio di un altro, così da tenere sempre in attività la CPU: si parla di Multiprogrammazione di tipo Batch o Batch Multiprogrammato. Diverso approccio alla gestione di job multipli è la Multiprogrammazione di tipo Time Sharing, nel quale la potenza di calcolo della CPU viene distribuita ciclicamente, per piccole frazioni di tempo, ad N utenti attraverso N terminali (ciascun utente ha l'impressione di avere le risorse del sistema tutte per sé, il singolo processo del singolo utente diventa Running per un breve intervallo di tempo e poi resta Ready nel tempo in cui operano gli altri utenti). Nel Batch Multiprogrammato con Partizione Time Sharing i jobs degli utenti (considerati prioritari perchè conversazionali, ovvero richiedono interazione con l'utente e devono sottostare a stringenti tempi di risposta) sono gestiti tramite il Time Sharing (Scheduling a Breve Termine), e solo in assenza di jobs conversazionali vengono avviati i jobs di background in modalità Batch (Scheduling a Lungo Termine); una possibile variante del modello consiste nel non fare sì che la CPU sia monopolizzata totalmente dai processi utente e prevede che una piccola frazione di tempo utile ciclico della CPU sia comunque concessa al carico di lavoro Batch. I sistemi che forniscono risposte in tempi brevi sono classificati in Hard Real Time o Real Time (non Hard) rispettivamente se tempi di risposta estremamente rapidi sono decisivi per la correttezza del sistema oppure se tempi "medi" di risposta sono comunque accettabili. Con l'avvento dei MicroProcessori i computer divennero personal e i SO offrirono un ambiente di lavoro più user friendly: il concetto di multiprogrammazione era inizialmente assente nei primi SO (si riteneva fosse legato necessariamente ad una pluralità di utenti e comunque richiedeva potenze di calcolo proibitive per l'epoca) ma oggi è supportato da tutti i SO moderni. Negli ultimi 20 anni, infine, si è dato impulso all'aggregazione di PC per costituire Sistemi Distribuiti, comunemente detti Reti, geograficamente dislocate.

Dal punto di vista dell'utente, i SO possono essere classificati in sistemi dedicati, sistemi batch (a lotti), sistemi interattivi o conversazionali, sistemi in tempo reale e sistemi transazionali. Un sistema dedicato fornisce un interprete dei comandi, la possibilità di lanciare programmi e di gestire file, il tutto dedicato ad un unico utente, caratterizzandosi per il basso sfruttamento della CPU durante le interazioni con l'utente e l'assenza di una virtualizzazione delle risorse: viene denominato Supervisore o DOS, per evidenziare rispettivamente il controllo esercitato sull'esecuzione dei lavori o il supporto alla gestione del disco. Un sistema batch (a lotti) gestisce singolarmente l'avanzamento di lavori raggruppati in lotti memorizzati su disco, privilegiando lo sfruttamento della CPU (vantaggio) a prezzo dell'assenza di interazione con l'utente, che deve fornire il suo lavoro in via preliminare e che può attenderne il completamento anche per ore o giorni (svantaggio): le unità di I/O sono virtualizzate e ciò rende le operazioni su di esse più veloci (vantaggio). Un sistema interattivo o conversazionale assegna, agli utenti che interagiscono attraverso terminali, le risorse per "quanti di tempo", riducendo il tempo di risposta e dando loro la sensazione di operare su un sistema dedicato (vantaggio): questo meccanismo produce necessariamente un overhead (svantaggio). Un sistema transazionale consente ad utenti ed applicazioni di eseguire sequenze di operazioni elementari (tipicamente manipolazione di archivi) in forma di transazioni, rispettando le proprietà di atomicità, consistenza, isolamento e persistenza. Un sistema in tempo reale esegue programmi che, interagendo con l'ambiente esterno, garantiscono a dati di ingresso risposte in tempo utile rispetto alle constanti di tempo proprie dell'ambiente esterno stesso: la correttezza del sistema dipende in modo critico dalla velocità di esecuzione. Si noti che in campo commerciale "real time" è sinonimo di conversazionale o transazionale, tuttavia i due tipi di sistemi non coincidono.

In base all'organizzazione interna possono essere inoltre classificati in sistemi monoprogrammati, sistemi multiprogrammati, sistemi time-sharing (a partizione di tempo) e sistemi ad uso speciale. In base infine all'architettura del sistema di elaborazione su cui sono calati, i SO possono essere classificati in SO per sistemi di calcolo monolitici, per sistemi di calcolo distribuiti e per sistemi di calcolo paralleli.

Struttura a livelli del SO

Il SO offre all'utente dei servizi e questi ne ha visibilità attraverso i comandi che consentono di richiamarli: i comandi espliciti sono gestiti dalla Shell, i comandi impliciti sono invece generati da un compilatore/assemblatore. Le principali funzioni offerte dal SO e viste dall'utente possono essere raggruppate in funzioni per la gestione dei lavori (qualificarsi nei confronti del sistema, richiedere l'allocazione di risorse, richiedere l'esecuzione di una o una successione di azioni), supporti per la programmazione (programmi per il trattamento testi, per la gestione delle librerie, per il supporto al testing e al debugging del codice dei programmi), meccanismi di I/O (mascheramento delle modalità con cui le operazioni di I/O vengono eseguite, mascheramento dei conflitti nell'uso di periferiche condivise, gestione dei malfunzionamenti) e funzioni di gestione archivi (accesso tramite riferimenti logici, garanzia di sicurezza negli accessi e dell'integrità dei dati

Una tipica schematizzazione del SO a livelli consente di riconoscere 8 livelli, via via più bassi quanto più ci si avvicina alla macchina reale, via via più alti quanto più le macchine virtuali sono astratte e mettono a disposizione funzionalità evolute:

Programma Utente

Shell Interprete dei comandi

Utility Supporto allo sviluppo (editor, testing, debugging) dei programmi, fogli elettronici e altre utilità

File System Gestione (con controllo degli accessi) di blocchi di informazioni logicamente strutturati registrati su disco, ovvero i File

Periferiche Virtuali Simulazione di periferiche virtuali (implementazione primitive I/O e gestione malfunzionamenti)

Memoria Virtuale Allocazione memoria ai programmi che la richiedono usando se necessario la memoria secondaria (gestione corrispondenza indirizzi fisici / logici, caricamente / scaricamento / swapping, protezione dalle violazioni)

Nucleo Allocazione della CPU ai processi (Sheduling), primitive di gestione degli eventi asincroni e di sincronizzazione (richiamate tramite SVC)

Hardware Macchina Base o Reale

Ogni macchina virtuale di livello superiore utilizza i servizi offerti dalla macchina virtuale (eventualmente reale) di livello inferiore, che espone una apposita interfaccia; i livelli (2) e (3) sono da considerarsi paritari, ovvero non necessariamente dipendenti l'uno dall'altro; i livelli da (1) a (3) formano un macrolivello costituito da processi dedicati, mentre i restanti dal (4) al (7) costituiscono il Kernel del SO in senso esteso; al livello (8) c'è un'unica CPU, Memoria, Disco e un insieme discreto di periferiche; il livello (7) costituisce una macchina virtuale rispetto alla quale tutti i processi vedono ciascuno una propria CPU; il livello (6) costituisce una macchina virtuale rispetto alla quale tutti i processi vedono ciascuno una propria CPU e una propria memoria; il livello (5) costituisce una macchina virtuale rispetto alla quale tutti i processi vedono ciascuno una propria CPU, una propria memoria e un insieme non condiviso di periferiche ogni livello insomma astrae sempre di più la macchina reale facendola apparire progressivamente, in ogni suo componente, dedicata al singolo processo attivo.

Interrupt e Supervisor Call

Una Interrupt o Interruzione è il più facile meccanismo (comunemente adottato da tutti i sistemi programmabili e da tutti i modelli di CPU sul mercato) che consente di interrompere e modificare il normale flusso di esecuzione delle operazioni da parte della CPU al verificarsi di un evento. Una Interrupt Hardware è generata da dispositivi esterni alla CPU e serve a comunicare il verificarsi di un evento generalmente asincrono (un dispositivo I/O informa la CPU che è disponibile a fornire o ricevere dati, il clock segnala la scadenza di un quanto di tempo, ). Un Interrupt Software o Trap è generata invece da istruzioni assembly (INT x, SYSCALL) assimilabili a chiamate a sottoprogrammi con le quali un processo richiede una System Call o Supervisor Call (esecuzione di una primitiva del SO, accesso diretto a risorse controllate dal SO, ) oppure segnala una exception (tentata divisione per zero, la violazione della memoria, disconnesione dalla rete, errore di trasferimento dati, ). Le interruzioni possono inoltre essere abilitate o disabilitate con apposite istruzioni assembly (STI Set Interrupt e CLI Clear Interrupt

Una Interrupt Request o IRQ o Richiesta di Interruzione (usata spesso erroneamente come sinnimo di Interrupt) è il meccanismo con cui lo specifico evento viene segnalato alla CPU, inviando opportuni segnali ai pin fisici di collegamento della CPU stessa: a seconda dello stato in cui si trova la CPU, la IRQ può essere servita o accantonata per essere eseguita in un secondo tempo, e questo perchè gli IRQ sono organizzati in gerarchie di priorità e una IRQ di livello più basso può essere scavalcata - e l'interruzione da essa generata a sua volta interrotta - da una IRQ di livello alto, a meno che non sia associata ad una Non Maskable Interrupt o NMI, che non può essere accantonata e va eseguita immediatamente. Diversi tipi di CPU generalmente standardizzano i loro IRQ in modo che ad un certo IRQ corrisponda sempre lo stesso tipo di evento: tasto premuto sulla tastiera, comunicazione in arrivo su porta seriale, e così via.

La gestione degli Interrupt prevede che, quando la CPU riceve una IRQ, la prima esigenza sia determinare quale dispositivo l'ha generata e questo può essere fatto con due diversi sistemi, la scansione degli interrupt (o polling) e la vettorizzazione degli interrupt. Nel prima caso si effettua l'interrogazione di ciascuno dei dispositivi collegati per una eventuale conferma della richiesta di interruzione inviata. Nel secondo caso si usa invece un opportuno circuito integrato detto Programmable Interrupt Controller o PIC, che riceve in ingresso un certo numero di linee di IRQ usate appunto dai dispositivi per richiedere un'interruzione: quando il PIC riceve una IRQ, si occupa di segnalare alla CPU tale richiesta di interruzione e - se la CPU conferma la richiesta (potrebbe non confermarla se le interruzioni sono disabilitate) - deposita nel bus dati l'indice di un Vettore di Interrupt o Vettore di Interruzione, cioè l'indice che consenta di indirizzare una vera e propria tabella chiamata anche Interrupt Vector Table o Interrupt Descriptor Table, in cui siano memorizzati gli indirizzi delle diverse Interrupt Service Routine o ISR o Interrupt Handler associata alle interruzioni, ovvero funzioni di tipo callback (una funzione specializzata passata come parametro a un'altra funzione che invece è generica) che contengono le operazioni la cui esecuzione è prevista nel caso di ogni specifica interruzione. In sintesi, quando la CPU riceve una IRQ, recepisce un indice di interruzione, lo usa per indirizzare la tabella o vettore delle interruzioni e trova un puntatore ad una specifica procedura, predisposta dal programmatore o più spesso dal SO; affinchè il meccanismo di interruzione funzioni correttamente, è necessario che l'esecuzione della ISR sia trasparente al processo interrotto e qundi serve che la CPU, prima di mandare in esecuzione la ISR, faccia un salvataggio del contesto del processo in corso in un apposito stack e che poi, a seguito del ritorno dall'interruzione tramite l'istruzione RTE, lo ripristini com'era; poichè l'interruzione va gestita rapidamente non va perso tempo a salvare tutto il contesto del processo (ad esempio le sue variabili globali) ma solo quello che effettivamente verrà modificato dall'ISR, e siccome la CPU non conosce in anticipo che cosa l'ISR modificherà, quando si verifica una interruzione essa provvede ad affettuare il salvataggio almeno del Registro di Stato del processo o Program Status Word o PSW (un'area di memoria o un registro che contiene informazioni sullo stato dei programmi in esecuzione sul SO) e del Program Counter o PC.

Il compito del SO, relativamente al meccanismo di gestione degli interrupt, consiste essenzialmente nel predisporre gli opportuni sottoprogrammi di gestione degli interrupt per tutte le periferiche, così come i sottoprogrammi di gestione delle eccezioni, inserendo i loro indirizzi nella tabella degli interrupt.

Si definiscono istruzioni privilegiate di un SO quelle istruzioni riservate all'uso esclusivo da parte del SO (allo scopo di rendere impossibili le interferenze reciproche di processi concorrenti) concernenti essenzialmente la manipolazione del sistema delle interruzioni, la commutazione della CPU tra processi, le operazioni di I/O, l'accesso ai registri utlizzati dall'hardware per la protezione della memoria e l'arresto della CPU (halt). La maggioranza degli elaboratori opera in due modalità distinte, il Supervisor Mode (modo privilegiato, system mode, monitor mode) e lo User Mode (modo utente, modo non privilegiato) e le istruzioni privilegiate sono permesse solo nel Supervisor Mode; il passaggio dal modo utente al modo privilegiato ha luogo automaticamente al verificarsi di una delle 4 seguenti condizioni: un processo utente effettua un richiamo del SO (Supervisor Call o SVC o System Call) allo scopo di eseguire una funzione che richieda l'esecuzione di una istruzione privilegiata, si verifica il tentativo di eseguire una istruzione privilegiata mentre ci si trova nel modo utente, si verifica un interrupt oppure, infine, si verifica una condizione di errore interna al processo utente (exception); il ritorno al modo utente viene effettuato tramite una apposita istruzione, anch'essa privilegiata.

Con riferimento specifico alle SVC, possiamo dire che il kernel del SO astrae l'hardware mettendo a disposizione dei processi utente una serie di interfacce standard denominate system call, chiamate di sistema, con le quali è possibile interagire con il kernel richiedendogli servizi: ogni volta che un processo necessita di un servizio che agisce direttamente sulla macchina reale (e che non potrebbe eseguire direttamente a causa del mascheramento delle risorse da parte del SO allo scopo di evitare i conflitti), richiede l'intervento del SO affidandosi alle SVC o System Call; le system call sono implementate in assembly da istruzioni (INT x, SYSCALL) in cui l'operando ne specifica il tipo, mentre eventuali altri parametri vengono passati tramite registri o per indirizzo: effettuando la chiamata ad una di queste funzioni, si verifica una interruzione del processo ed il controllo viene passato al kernel, che provvede a fornire il servizio richiesto; nei linguaggi di alto livello tali istruzioni assembly sono wrappate (da wrap = incartare, imballare) cioè mascherate all'interno di routine di libreria dette di supporto a tempo di esecuzione.

Ricapitolando, le funzioni di un livello di macchina virtuale sono rese disponibili ai programmi in esecuzione attraverso primitive (procedure non interrompibili) del SO, accedute mediante SVC (quindi interruzioni software) con scambio di parametri tramite registri del processore e specifiche aree di memoria. Lo stesso meccanismo delle interruzioni consente di attivare da un livello superiore de Kernel funzioni di un livello inferiore, producendo contestualmente il salvataggio dello stato del processore nello stack di sistema e ogni ritorno da interruzione produce chiaramente il rispristino dallo stack di sistema dello stato del processore.

Processi e Multiprocessing

Un algoritmo è una sequenza di passi finalizzata alla soluzione di un problema. Un programma è la descrizione di un algoritmo in un linguaggio che ne rende possibile l'esecuzione da parte di un processore. Un processo è un sequenza di istruzioni (eventi) eseguite da un processore nell'ambito dell'esecuzione di un programma. Più specificamente per processo si intende una istanza di un programma in esecuzione in modo sequenziale, ovvero un programma di cui ne sia stata eseguita almeno una istruzione e che non sia ancora terminato. Ricorsivamente, un processo può essere definito come una attività (svolta chiaramente da un processore) controllata da un programma, e può quindi identificare non solo un programma nella sua interezza ma anche una sua parte. A titolo di esempio si consideri il programma in codice pascal-like che effettua 3 operazioni in sequenza su ciascun elemento di tipo T di un array a cardinalità N

var buffer : T;

i : 1N;

begin

for i:=1 to N do begin

Lettura(buffer);

Elaborazione(buffer);

Scrittura(buffer);

end;

end.

Se le operazioni di Lettura, Elaborazione e Scrittura vanno eseguite in stretta sequenzialità allora processo è sinonimo di intero programma, viceversa se esse possono essere eseguite ad un qualche livello anche minimo di parallelismo allora ciascuna di esse può costituire un processo distinto che collabora con gli altri fino al raggiungimento del risultato finale: il programma che ne deriva implementa un algoritmo concorrente.

Un SO che supporta il Multitasking (o Multiprocessing) consente di eseguire più processi in modo parallelo: questo significa che (a maggior ragione su una macchina monoprocessore) non è detto che ad ogni colpo di clock la CPU esegua un'istruzione di uno specifico processo fino al suo completamente, ma anzi al contrario la sua esecuzione può essere interrotta in ogni momento e successivamente ripresa, in modo da garantire l'esecuzione parallela di più processi distinti. Le strategie messe in atto del SO per l'avvicendamento tra processi (in seguito definito cambio di contesto) vengono intraprese da un componente del SO detto Scheduler, che invia le sue decisioni ad un altro modulo del SO detto Dispatcher, vero artefice del cambio di contesto: a seconda dell'algoritmo di Scheduling utilizzato, lo Scheduler ripartisce il tempo della CPU tra tutti i processi attivi. Possiamo avere il Multitasking Cooperativo o Senza Prelazione in cui ogni processo mantiene il controllo della CPU finchè non termina o la rilascia spontaneamente, e il Multitasking Non Cooperativo o Con Prelazione in cui il SO ha facoltà di sospendere il processo per cedere la CPU ad altro processo. Un SO Monotasking (come l'MS-DOS) ha chiaramente la capacità di eseguire un singolo processo per volta.

Ogni volta che nel SO viene generato un nuovo processo, viene allocata un'area dati denominata descrittore del processo o Process Control Block (PCB), in pratica un record nei cui campi vengono salvati tutti i dati strettamente necessari al controllo del processo da parte del SO: PID (Process Identifier o Process Handle, l'identificatore univoco del processo), Puntatori al processo padre e ad eventuali processi figli, PC (Program Counter o Instruction Pointer, il puntatore alla prossima istruzione del processo da eseguire nel ciclo fetch-execute) e posizione del Segmento di Codice, Identificatore della CPU su cui il processo è in esecuzione e suoi Registri di Stato, Informazioni di Accounting del processo e sua Priorità, Informazioni per il Memory Management del processo (in particolare memoria virtuale), Informazioni per lo Scheduling del processo (in particolare tempo di esecuzione e attesa accumulato), Descrittori delle Risorse in uso (file, periferiche, ) e informazioni sullo Stato di I/O del processo, valori delle variabili globali del processo, dello stack e dei registri del processore accessibili dal processo stesso. Tutto il contenuto del PCB costituisce il cosiddetto Stato Puntuale del processo, che viene salvato nel PCB ad ogni interruzione e ripristinato dal PCB ad ogni ripresa di attività del singolo processo: si parla di Context Switch, ovvero di cambiamento di contesto, nel senso che con l'avvicendamento di un processo ad un altro cambia il contesto cui le informazioni memorizzate nei registri della CPU si riferiscono

Procedure Context_Switch;

begin

Salvataggio_Stato; Scheduling_CPU; Ripristino_Stato;

end;

Il cosiddetto Stato Globale del processo, che può essere anch'esso memorizzato esplicitamente nel PCB (ma più spesso è implicito come vedremo), è rappresentato invece dallo stato di avanzamento del processo legato alla sua capacità di evolvere, che può essere uno tra cinque: un processo di cui è stato appena creato il PCB, del quale non sia stata ancora eseguita alcuna istruzione e che sia in attesa che il SO gli assegni le risorse necessarie per poter iniziare l'esecuzione, si trova nello stato New; una volta che l'assegnazione delle risorse sia avvenuta il processo passa nello stato Ready, una cosiddetta attesa passiva nella quale il processo attende che la CPU esegua le sue istruzioni (tale condizione manca se ci sono tante CPU quanti processi attivi); quando lo Scheduler ha assegnato la CPU al processo lo stato diventa Running, ovvero va in esecuzione; dallo stato Running il processo transita direttamente nello stato Ready laddove perda forzatamente l'uso della CPU (si parla di prerilascio), tipicamente per eccesso di utilizzo continuativo, oppure può transitare nello stato Waiting, a seguito di una chiamata ad una primitiva del SO: vuole sincronizzarsi con altri processi e deve attendere, ha richiesto una risorsa al SO e questa non è ancora disponibile oppure ha lanciato un'operazione di I/O e deve aspettare che questa sia completata (quando ciascuno di questi 3 possibili eventi si è verificato il processo transita dallo stato Waiting allo stato Ready); l'ultima istruzione utile eseguita da un processo è la chiamata alla primitiva del SO di terminazione, con la quale il processo entra nello stato Terminated in attesa che le risorse sotto il suo controllo siano recuperate dal SO (terminato il processo, chiaramente anche il PCB viene rimosso).

L'allocazione del PCB è rigorosamente statica all'interno del Kernel, e quindi il numero di PCB massimo che è possibile allocare è limitato (viceversa, la primitiva del Kernel che si occupa di generare il processo e il suo PCB dovrebbe richiamare una primitiva di livello inferiore che allochi la memoria questo comporta, nei fatti, che il livello 6 stia sotto il livello 7 e benchè ciò sia teoricamente possibile nella pratica non accade mai); inoltre, i PCB sono elencati in una struttura chiamata Process Table e tipicamente linkati tra loro in code costituite da liste a puntatori, secondo il criterio per cui PCB caratterizzati dallo stesso Stato Globale appartengono alla stessa coda (più code distinte possono esistere per processi parimenti Waiting a seconda dell'evento/risorsa per cui sono in attesa, e implicitamente un PCB in coda segnala che quel processo non è Running).

Primitiva Fork

Il meccanismo basilare per creare un processo è la primitiva Fork, chiamata dall'interno di un altro processo (al limite dallo Shell): un processo denominato padre crea in memoria un processo clone di sé stesso denominato figlio. Un processo figlio è quasi la copia esatta del processo padre giacchè eredita da esso il codice, i dati, lo stack, i descrittori di file aperti e la visibilità di ogni altra risorsa controllata dal padre; chiaramente essi risulteranno distinti per il PID, il PPID (ovvero il PID del processo padre) e per l'utilizzo delle risorse in run-time. In generale, in un sistema Non Multithreading, ereditare significa duplicare, per cui all'atto della creazione del nuovo processo il codice del padre viene duplicato per il figlio, un nuovo PCB indipendente viene allocato e viene creato un nuovo spazio di indirizzamento per fare sì che il figlio abbia copie indipendenti dei dati ereditati dal padre (una tecnica efficiente utilizzata da Unix, che è un SO Multitasking ma non Multithreading, è quella del copy on write, ovvero al processo figlio non sarà allocata memoria fisica fino al momento in cui uno dei due processi non effettuerà una scrittura sui dati condivisi: in pratica il figlio condividerà i segmenti di memoria del padre fin quando essi saranno di sola lettura per entrambi, altrimenti si procederà alla duplicazione effettiva). A titolo di esempio consideriamo il codice C seguente

#include <stdio.h>

#include <unistd.h>

#include <stdlib.h>

main() else if (pid > 0) printf('Padre!');

//Se la fork() restituisce un valore minore di 0 significa che il processo figlio non è stato creato

//ad esempio per un eccessivo numero di processi attualmente attivi

else

La chiamata fork( ) è detta chiamata asincrona di procedura, differente da una classica chiamata di procedura perchè il processo chiamante non viene sospeso ma questo, insieme al processo chiamato, vengono eseguiti in due contesti differenti, come processi indipendenti eseguiti in parallelo: il processo figlio partirà nello stato New o direttamente nello stato Ready, e non appena sarà Running eseguirà la prima istruzione che segue la fork; per riconoscere dall'interno di ciascuno dei due processi di quale si tratti (del padre o del figlio) occorre valutare il PID restituito dalla primitiva fork.

Supponiamo che il processo in esecuzione contenga un codice del tipo

A: fork(X);

B:

X: "prima istruzione del processo invocato da FORK"

la chiamata A : fork(X) produce un processo figlio la cui prima istruzione utile sarà quella corrispondente alla label X, quindi coerentemente con quanto già detto finora, sullo stesso codice vengono percorsi concorrentemente due flussi di controllo distinti (graficamente da un nodo A parte una biforcazione verso due nodi successivi B e X). Un possibile algoritmo pascal-like della fork può essere

Procedure fork(id);

begin

if esiste_PCB_libero then

begin

<alloca descrittore libero al processo figlio>

<alloca spazi di memoria al processo figlio (inizializzati ai dati del padre)>

<inizializza il descrittore del figlio (id determina il PC)>

<poni il processo figlio in stato ready>

else

<poni il processo padre in attesa di un descrittore libero>

Context_Switch;

end;

end;

Thread e Multithreading

Se il SO è Multithreaded, il nuovo processo figlio generato non è considerato propriamente come tale (proprio codice, proprio PCB) bensì padre e figlio vengono gestiti dal SO come due distinti Thread di uno stesso processo, cioè il processo padre. Thread è abbreviazione di thread of execution, cioè filo dell'esecuzione (si rifà visivamente al concetto di fune composta da vari fili attorcigliati: se la fune è il processo in esecuzione, allora i singoli fili che la compongono sono i thread) e va inteso come una parte del processo che viene eseguita in maniera concorrente ed indipendente internamente al processo stesso: un processo ha sempre almeno un thread (sè stesso) ma può avere più thread eseguiti in parallelo.

A livello di definizioni, un processo si può definire come l'entità del SO cui sono assegnate tutte le risorse di sistema per l'esecuzione di una applicazione tranne la CPU, il thread è invece l'entità del SO o dell'applicazione cui è assegnata la CPU per l'esecuzione, uno stato di esecuzione (Ready, Waiting, Running), un contesto (registri della CPU compreso PC) e uno stack. In termini di differenze, i processi, solitamente indipendenti tra loro, utilizzano aree di memoria diverse ed interagiscono solo mediante appositi meccanismi di comunicazione messi a disposizione dal SO, al contrario i thread di uno stesso processo condividono con esso le informazioni di stato, la memoria e le risorse allocate al processo; una differenza fondamentale è inoltre nel meccanismo di attivazione: la creazione di un nuovo processo è sempre onerosa per il sistema (devono essere allocate le risorse necessarie alla sua esecuzione) mentre il thread nasce come parte di un processo già esistente e quindi la sua attivazione avviene in tempi ridottissimi; infine ciascun thread è identificato da un TID (Thread Identifier o Thread Handle, omologo del PID) e ad esso è associato un Descrittore di Thread (contenente appunto lo stato d'esecuzione, il contesto e lo stack), mentre se il SO non gestisce i thread tali informazioni fanno parte dello stato del processo e sono indicate nel PCB.

I vantaggi del Multithreading sono dunque evidenti, in quanto si riducono gli overhead del SO legati alla creazione/terminazione dei processi, alla loro comunicazione e al cambio di contesto. Comunque, quando non prevista a livello Kernel tramite SVC, la gestione dei thread può avvenire a livello utente tramite apposite routine di libreria: nel primo caso esiste certamente un overhead a carico del SO compensato però dalla possibilità di processare simultaneamente più thread e di schedulare un altro thread di uno stesso processo laddove un thread sia bloccato; nel secondo caso non c'è alcun overhead esplicito a carico del SO, la schedulazione può avvenire secondo esigenze specifiche dell'applicazione (e non in base a criteri generali stabiliti dal SO) ed è per questo portabile, tuttavia il parallelismo solo simulato tramite libreria impedisce di sfruttare il multiprocessing così come l'esecuzione di tutti i thread è soggetta a blocco in caso di SVC.

Interazioni tra processi e primitiva Join

Le interazioni tra processi sono di 3 tipi: competizione, cooperazione (o concorrenza) e interferenza. Il SO deve prevedere meccanismi in grado di risolvere la competizione, che è una forma di interazione indesiderata ma prevedibile quando si usano risorse comuni: il SO si fa carico di gestire la sincronizzazione implicita tra processi che intendono utilizzare risorse da esso direttamente gestite e mette a disposizione meccanismi di sincronizzazione implicita dei processi che usano risorse gestite a livello applicazione (un modo banale di procedere può essere il rendere invisibile la risorsa a tutti i processi che potrebbero richiederne l'uso fuorchè ad un singolo processo dedicato, che diverrà quindi destinatario e mediatore delle richieste). Il SO deve inoltre permettere ed agevolare la cooperazione, una forma di interazione desiderata (perchè aumenta il parallelismo dell'elaborazione) e prevista quando i processi sono tra loro logicamente collegati o interdipendenti (condizione necessaria è l'esistenza almeno di un ordinamento parziale tra processi concorrenti, viceversa un ordinamento totale impone un'elaborazione strettamente sequenziale): la cooperazione richiede una sincronizzazione esplicita tra processi cooperanti, che possono scambiarsi messaggi di pura sincronizzazione o di sincronizzazione e dati, e il SO si fa carico di gestire la cooperazione tra processi utente e processi del SO e mette a disposizione meccanismi per la cooperazione tra processi utente. Il SO deve infine prevenire le interferenze quando dovute a errori di soluzione a problemi di competizione e cooperazione: il SO può prevenire solo interferenze macroscopiche (ad esempio la violazione della memoria) ma in presenza di veri e propri bug di programmazione può fare poco o nulla.

Un tipo particolare di interazione tra due processi si presenta quando uno di essi tenta di sincronizzare il proprio flusso di controllo con la terminazione dell'altro. A questo scopo esiste la primitiva Join che determina la confluenza o ricongiunzione di due o più flussi di controllo, e il cui algoritmo è schematizzabile in pascal-like in due distinte versioni:

Procedure join(count);

begin

count:=count - 1;

if count>0 then

begin

<termina il processo chiamante>

Scheduling_CPU; Ripristino_Stato;

//In pratica si effettua un Context_Switch con contemporanea

//terminazione del processo corrente

end;

end;

Procedure join(pid);

begin

if stato(pid) <> terminated then

begin

<poni il processo chiamante in attesa che il processo PID termini>

Context_Switch;

end;

end;

La primitiva Join(count) consente la confluenza di N flussi di controllo ma non consente di denotare esplicitamente i processi con cui ci si vuole sincronizzare: valutando l'esempio seguente in pascal concorrente, non è difficile convincersi che non è detto che i processi figli terminino tutti prima del processo padre e quindi non è detto che siano i flussi di controllo dei figli a confluire nel flusso di controllo del padre

begin

count:=3;

fork label_1;

fork label_2;

goto label_3;

label_1:

label_2:

label_3: join(count);

Fine:

end;

l'unica cosa di cui si può essere certi è che tra i 3 processi (al massimo) in esecuzione contemporaneamente, un solo di essi sfuggirà al suicidio previsto dalla Join e arriverà ad eseguire l'istruzione della label Fine (quale sia tra essi non lo possiamo però sapere in anticipo). La primitiva Join(pid) consente viceversa la confluenza di soli 2 flussi di controllo ma permette di indicare esplicitamente chi si sincronizza con chi: nell'esempio seguente in pascal concorrente il processo padre crea il processo figlio (il cui PID è memorizzato in P) e poi eseguendo la Join si arresta nell'attesa che il figlio termini (Join non termina forzatamente alcun processo, aspetta che esso termini spontaneamente), ovvero in pratica sospende la sua esecuzione per sincronizzarsi col completamento del processo figlio

var P:process;

procedure X;

begin

end; produce una SVC per la terminazione del processo (exit)

begin Main

P:= fork(X);

join(P);

end;

Esempio: programma di Lettura-Elaborazione-Scrittura di Array[N]

Per il programma introdotto all'inizio (nel paragrafo sui processi) è possibile costruire un grafo di precedenza dei processi di Lettura, Elaborazione e Scrittura che ha la forma di un reticolo rettangolare a 3 (larghezza) x N (altezza) nodi, in cui da ogni nodo partono (se possibile) archi orientati verso i due nodi alla destra e in basso: in pratica Lettura(i) precede logicamente Elaborazione(i) e Lettura(i+1), Elaborazione(i) precede logicamente Scrittura(i) e Elaborazione(i+1) e Scrittura(i) precede logicamente Scrittura(i+1). In pratica le letture possono avvenire in modo sequenziale senza vincoli, mentre le elaborazioni e le scritture devono verificare vincoli di precedenza (nel primo caso perchè l'elaborazione di un dato successivo può dipendere dall'elaborato di un dato precedente, nel secondo caso perchè i dati vano scritti sequenzialmente nello stesso ordine in cui sono stati letti). L'ordinamento parziale dei nodi di questo grafo consente lo sviluppo di un algoritmo concorrente, di cui il seguente è un semplice esempio realizzativo

var R : array[1..N] of T; Array di N elementi

i : 1..N; Variabile di indice

PE, PS : array[1..N] of process; Array di puntatori a processi

N puntatori a processi Elaborazione e N a processi Scrittura

procedure E(k : 1..N);

begin

if k>1 then Join( PE[k-1] ); Se non ci troviamo sulla prima riga del grafo sincronizzati

con l'elaborazione del campo precedente

Elabora( R[k] ); Elabora il campo corrente

PS[k]:=Fork( S(k) ); Genera il nodo alla destra di quello corrente

end; Exit

procedure S(k : 1..N);

begin

if k>1 then Join( PS[k-1] ); Se non ci troviamo sulla prima riga del grafo sincronizzati

con la scrittura del campo precedente

Scrivi( R[k] ); Scrivi il campo corrente

end; Exit

begin

for i:=1 to N do begin Ciclo di lettura sequenziale dei campi con "forking laterale"

Leggi( R[i] ); del grafo, per dare inizio all'elaborazione dei campi

PE[i]:=Fork( E(i) );

end;

end;

Costrutti Cobegin e Coend

Un problema degli algoritmi come quello indicato qui sopra è che, a causa della loro non linearità, può essere difficile capire intuitivamente in ogni istante quanti e quali processi siano attivi una volta che il programma sia in esecuzione. I costrutti Cobegin e Coend consentono di rappresentare in modo intuitivo e semplice diramazioni parallele di un grafo di processi. Un listato del tipo

begin

P0;

cobegin

P1;

P2;

Pn;

coend;

Pz;

end;

equivale ad un grafo il cui nodo radice è P0 e l'unico nodo foglia è Pz: i processi interni al costrutto Cobegin-Coend formano nodi allo stesso livello intermedio tra P0 e Pz e vengono eseguiti tutti in parallelo; chiaramente l'adozione dei costrutti Cobegin-Coend in modo innestato consente di sviluppare grafi più complessi, ma non consente di rappresentare tutti i possibili grafi di precedenza. Detto cammino parallelo una generica sequenza di nodi il cui primo nodo è un nodo Cobegin (ovvero da esso parte una diramazione) e il cui ultimo nodo è un nodo Coend (ovvero in esso collassano almeno due nodi), un grafo di precedenza può essere tradotto con i costrutti Cobegin-Coend solo se per ogni coppia X,Y di nodi Cobegin-Coend del grafo si verifica che tutti i cammini paralleli che originano da X collassano in Y e tutti quelli che collassano in Y originano da X, ovvero ogni sottografo deve essere di tipo One In - One Out.

Il grafo di precedenza relativo al programma di Lettura, Elaborazione e Scrittura dell'array non verifica questa condizione: dato il generico cammino parallelo L(i) - E(i) - S(i), si osserva che da L(i) origina il cammino L(i+1) - E(i+1) - S(i+1) che non collassa in S(i) e che in S(i) collassa il cammino L(i-1) - E(i-1) - S(i-1) che non origina da L(i), quindi in teoria non è possibile riprodurre quell'algoritmo usando i costrutti Cobegin-Coend. In realtà, riducendo il grado parallelismo (il che non significa necessariamente perdita di efficienza) al massimo a 3 processi, è possibile sviluppare un grafo alternativo traducibile con i nuovi costrutti: a partire dal nodo radice L1, abbiamo una serie di paralleli (Cobegin-Coend impilati) con L2 ed E1 al secondo livello, e L(i+1) - E(i) - S(i-1) ai livelli successivi ottenendo un algoritmo di facile interpretazione

var A, B, C : T; Usiamo solo 3 variabili buffer

(l'array è implicitamente acceduto dalla routine Leggi)

i : 2..N; Variabile di indice

begin

Leggi(A);

cobegin

Elabora(A);

Leggi(B);

coend;

for i:= 3 to N do begin Inizio ciclo For

C:=A;

A:=B;

cobegin

Elabora(A);

Leggi(B);

Scrivi(C);

coend;

end; Fine ciclo For

cobegin

Stampa(A);

Elabora(B);

Stampa(B);

coend;

end.

Risorse

Sulla base della sua definizione un processo è una entità attiva del sistema. Si definisce Risorsa un qualunque componente passivo - hardware o software - del sistema, di cui i processi (e i loro thread) si servono nei rispettivi flussi di controllo. Un processo è composto da istruzioni, le istruzioni sono composte da codici operativi e questi ultimi lavorano su operandi (anche in mancanza di operandi espliciti esiste almeno un operando implicito) quindi è corretto dire che le risorse di un processo sono i suoi operandi; una risorsa software è chiaramente un oggetto allocato e accessibile in memoria, ma anche con una risorsa hardware si può interagire, di fatto, attraverso una opportuna interfaccia costituita in ultima analisi da registri, ai quali un processo può accedere e di cui può modificare il contenuto; generalizzando si può affermare che una risorsa, indipendentemente dalla sua natura, dal punto di vista di un processo, è sempre una struttura dati (di un qualche tipo elementare o a sua volta strutturato) allocata in memoria, cui un processo può accedere con delle procedure opportunamente definite, dette metodi di accesso: l'oggetto risorsa si assume quindi costituito da una struttura dati e dai suoi metodi di accesso.

Allocare una risorsa ad un processo significa dargliene visibilità e quindi, salvo vincoli, dargli la facoltà di utilizzarla. Quando una risorsa viene allocata staticamente, un processo ne conserva la visibilità per tutta la sua durata, da quando viene creato fino a quando viene terminato; viceversa se allocata (e deallocata) dinamicamente durante la sua evoluzione, il processo ne ha visibilità solo in determinati intervalli di tempo. In base alla modalità di allocazione e al numero di processi coinvolti una risorsa può essere:

dedicata se è allocata (staticamente o dinamicamente) ad un solo processo

privata (o locale) se è dedicata e allocata staticamente

condivisa se è allocata (staticamente o dinamicamente) a più processi

comune (o globale) se è condivisa e allocata dinamicamente

ad uso esclusivo se è condivisa ma deve essere usata da un solo processo per volta

Un allocatore o gestore di risorse è un'entità preposta ad allocare risorse ai processi garantendo il rispetto dei vincoli imposti dal tipo stesso di risorsa gestita (dedicata, privata, condivisa, comune, ad uso esclusivo) e può essere lo stesso programmatore se si tratta di risorse logiche o un componente del SO o componente dell'elaborazione - d'obbligo se si tratta di risorse fisiche - che a sua volta può essere un processo gestore o una risorsa gestore: può allocare dinamicamente una generica risorsa ad un unico processo per volta, se la risorsa è allocata staticamente può usare qualche criterio per disciplinarne le richieste, oppure può eseguire esso stesso le operazioni per conto dei processi richiedenti. Per svolgere la sua funzione il gestore necessita di una struttura di gestione (che memorizza lo stato della risorsa gestita e gli identificatori dei processi che la usano o che sono in attesa di usarla) e di procedure che operano su di essa (che servono alla verifica della soddisfacibilità di una richiesta e del rilascio della risorsa successiva all'uso): tale struttura rappresenta una risorsa privata del proceso gestore oppure costituisce essa stessa la risorsa gestore allocata staticamente dal programmatore nella memoria comune condivisa da tutti i processi che desiderano accedere alla risorsa gestita.

Modelli di programmazione concorrente

Le macchine concorrenti seguono due modelli fondamentali: il modello a Memoria Globale (o Comune) e il modello a Scambio di Messaggi o a Memoria Locale; nel primo modello la macchina ha una o più CPU che condividono un'unica memoria, e chiaramente anche le risorse che risiedono su tale memoria saranno condivise, essendo accessibili da ogni processo; nel secondo modello la macchina ha invece più memorie locali e di conseguenza ha risorse private.