Un sistema operativo è un programma specializzato nella gestione dell’hardware su cui risiede, e da questo punto di vista può essere definito come un intermediario tra l’utente e l’hardware, dove per utente non si intende solo una persona umana ma anche programmi o altri computer che hanno la necessità di usare il sistema. Un sistema operativo svolge talmente tanti compiti che potrebbe essere definito in altrettanti modi diversi. E’ più facile dire ciò che fa un sistema operativo che esprimere ciò che è. Se si tiene in considerazione che un sistema operativo si occupa di allocare e deallocare le risorse ai vari utenti (processi) che ne fanno richiesta allora un S.O. può essere definito un allocatore di risorse, se invece si tiene in considerazione il fatto che un S.O. controlla l’esecuzione dei vari programmi per impedire un non corretto utilizzo del computer specie per ciò che riguarda l’I/O allora il S.O. è un programma di controllo, che per altro ha la particolarità di non terminare mai (Kernel), almeno fino allo spegnimento della macchina. Ma un S.O. e soprattutto un aiuto nell’uso dell’hardware sottostante, cioè rende conveniente l’uso del computer sollevando l’utente dalla gestione diretta delle periferiche come i dischi o altre risorse, occupandosi di queste in maniera efficiente. Infatti, alcuni sistemi sono dotati d’interfacce grafiche utilizzate dagli utenti umani e interfacce software per utenti non umani.

Esistono molti tipi di sistemi operativi, alcuni sono l’evoluzione d’intuizioni e soluzioni adottate per i primi computer altri sono delle specializzazioni di sistemi già esistenti e che non aggiungono nulla di nuovo a quanto gia esiste. Quella che segue è l’evoluzione dei sistemi operativi:

q               Sistemi batch semplici  (primo S.O.)

q               Sistemi batch multiprogrammati (evoluzione)

q               Sistemi time-sharing (evoluzione)

q               Sistemi per personal computer (specializzazione di ciò che già esisteva con poche innovazioni sostanziali ma molti miglioramenti)

q               Sistemi paralleli

q               Sistemi distribuiti

q               Sistemi real-time

Sistemi batch semplici 

In principio i computer erano enormi, molto costosi e difficili da programmare. Un programmatore interagiva con questa macchina tramite una console e inseriva i programmi (da scrivere già in codice macchina) usando delle schede perforate che venivano lette tramite dei lettori di schede. L’interazione con il computer non era “dinamica” nel senso che il programmatore preparava dei job (consistenti nel programma da eseguire, dai dati da usare, e da altre informazioni (schede di controllo)), che eseguiva e ne attendeva i risultati. Tutto questo era poco produttivo e conveniente e ci si rese ben presto conto che vi erano molte procedure (come quelle che effettuavano operazioni di I/O) che il programmatore doveva riscrivere per ogni nuovo programma anche se erano poi sempre le stese. Così si pensò che tali compiti potevano essere scritti una volta per tutte ed inserite come parti software sempre presenti in un computer. Questo è il primo embrione di sistema operativo che andrà via via arricchendosi di nuove funzionalità. A questo punto però mentre i programmatori si concentravano sulla realizzazione dei programmi e il sistema batch della gestione a lotti degli stessi, una nuova figura professionale si preoccupava di fare da tramite tra il programmatore e il sistema, cioè l’operatore. Quest’ultimo, infatti, aveva il compito di raccogliere le schede dei vari programmatori, di organizzarle, di inserirle nel computer, di eseguire i job, di attendere l’output degli stessi e di restituire i risultati ai rispettivi programmatori. Nel frattempo potevano essere passate ore o giorni e se un programmatore aveva commesso un errore nel proprio programma solo dopo questo elevato lasso di tempo (detto turnaround) poteva porvi rimedio (cioè leggere la stampa dell’immagine binaria del suo programma in memoria, capirci qualcosa, correggere, ricompilare, riconsegnare all’operatore e attendere). Questo tipo di sistema aveva sì risolto il problema della ridondanza di codice uguale per ogni programma ma aveva introdotto due nuovi inconvenienti che saranno risolti solo in seguito: 1) il programmatore non interagiva più direttamente con la macchina 2) un turnaround elevato.

Inoltre nelle prime versioni dei sistemi batch semplici la CPU restava spesso inutilizzata, infatti, se un job in esecuzione doveva effettuare delle operazioni di I/O ad esempio da un lettore di schede, la velocità di quest’ultima risorsa era molto più bassa di quella della CPU che non poteva effettuare altre computazioni per tutto il tempo dell'operazione di lettura. Con l’avvento dei dischi e della tecnica denominata spooling questo problema venne in parte risolto. Lo spooling consiste nel copiare sul disco i dati letti dalle schede o da scrivere su una stampante e migliorare cosi l’uso della CPU. Quindi il disco viene usato come un grande buffer.

Sistemi batch multiprogrammati

Sebbene lo spooling migliorava le prestazioni di un sistema, non era sufficiente a garantire un uso costante o ininterrotto della CPU, infatti, per quanto veloce, un disco è sempre molto più lento della CPU. Così si pensò di sviluppare un sistema batch multiprogrammato ovvero un sistema in grado di eseguire un job finche questi usa la CPU, (ovvero finché non richiede un’operazione di I/O), e di eseguirne un altro, quando il primo effettua le sue operazioni di I/O.

In questo modo venivano usate contemporaneamente la CPU e il dispositivo di I/O, cosa che non accadeva precedentemente dove le risorse venivano usate in sequenza. Questo approccio introduce molti concetti importanti, infatti, il sistema deve decidere quali job caricare in memoria tra quelli presenti sul disco (scheduling a lungo termine dei job), e quale eseguire tra quelli presenti in memoria (scheduling a breve termine della CPU), deve poi garantire che i processi tenuti contemporaneamente in memoria restino in un certo ordine (gestione della memoria). Sebbene l’uso della CPU era pressoché costante e che le prestazioni erano ulteriormente migliorate, ci si rese conto che se si fosse aumentata l’interattività tra programmatore e computer sarebbe aumentata anche la loro produttività (a vantaggio di tutti tranne dell’operatore che diventerà non necessario nei sistemi time-sharing è sarà cancellato).

Sistemi time-sharing

Il time-sharing risolve alcune difficoltà che un utente incontrava nell’uso di un sistema batch multiprogrammato ovvero il fatto che un job dopo essere stato impostato e lanciato non poteva essere modificato durante la sua esecuzione e l’utente fino alla fine del job non aveva niente da fare. Inoltre un programma doveva essere scritto e testato staticamente, cioè non poteva essere provato sulla macchina mentre si tentavano delle modifiche. La naturale evoluzione di un simile sistema fu il sistema time-sharing (multitasking) nel quale più job vengono eseguiti dalla CPU che commuta la loro esecuzione non quando il job deve effettuare un’operazione d' I/O, ma con una frequenza tale da dare l’impressione agli utenti che tutti i processi caricati vengano eseguiti contemporaneamente, ciò consente ad ogni utente di interagire con il proprio programma durante la sua esecuzione, di modificarne i dati di input o di controllarne il funzionamento lanciando altri programmi.

Quindi con un sistema time sharing ogni programmatore aveva una sua postazione costituita da una tastiera e da un monitor e il sistema forniva un editor e un debugger e cosa più innovativa un file system on-line cioè supportava il salvataggio/lettura dei dati organizzati in file. I sistemi time-sharing presero vita negli anni 60 ma ebbero successo solo negli anni 70. Un sistema time-sharing avendo la necessità di caricare e tenere in memoria molti programmi, le cui dimensioni complessive potevano essere superiori alle dimensioni effettive della memoria introduce due concetti innovativi: 1) lo swapping 2) la memoria virtuale.

Con lo swapping un processo in memoria non attivo veniva temporaneamente scritto sul disco mentre un altro veniva spostato dal disco in memoria per essere eseguito.

Con la memoria virtuale una porzione di disco viene usata come una estensione della memoria centrale che diventa virtualmente più grande.

Sistemi per personal computer

Con la riduzione dei costi dei componenti hardware è stato possibile realizzare computer moto piccoli se paragonati ai primi computer. Queste nuove macchine vennero chiamate personal computer, perché venivano assegnate ad un singolo utente. I sistemi operativi per questa classe di macchine erano multitasking ma supportavano anche operazioni in batch, sebbene assegnate ad un singolo utente alcuni sistemi supportavano la sicurezza sui file qualora la macchina veniva collegata ad altre macchine con altri utenti, alcuni sistemi piuttosto che ottimizzare l’uso delle risorse, puntarono verso la convenienza dell’uso di queste ultime, cioè rendere più facile il proprio utilizzo anziché il più intensivo possibile.

Sistemi paralleli

Nei sistemi paralleli esistono due o più CPU che devono essere coordinate da S.O. per un corretto funzionamento.

Un sistema parallelo viene detto anche multiprocessore o sistema strettamente accoppiato perché le CPU condividono le risorse del sistema. Un sistema del genere ha un alto numero di job eseguiti in un unità di tempo per cui si dice che ha un elevato throughput. Occorre precisare però che aumentando di n volte il numero di processori non vuol dire aumentare di n volte il throughput questo perché occorre un certo tempo per gestire il corretto funzionamento delle n CPU e gestire la conflittualità delle risorse condivise, tale tempo è chiamato overhead. Un’altra caratteristica dei sistemi paralleli e l’alta affidabilità o tolleranza ai guasti, infatti, in un sistema con n processori se se ne guasta uno ne restano n-1 che possono continuare a funzionate (con prestazioni ridotte), questa caratteristica è detta degradazione controllata. Alcuni sistemi paralleli, infatti, vengono progettati appositamente per supportare l’alta affidabilità piuttosto che un incremento di prestazioni, questi sistemi, infatti, hanno un hardware duplicato (il costo è ovviamente proporzionato) nel quale a determinati lassi di tempo (checkpoint) viene copiata l’immagine binaria di tutto ciò è presente nell’hardware primario. Se si verifica un guasto, l’hardware duplicato non guastato prende il posto di quello guastato e i processi vengono riavviati a partire dallo stato in cui erano nell’ultimo checkpoint.

I sistemi paralleli si distinguono in sistemi simmetrici e sistemi asimmetrici.

Nei primi su ogni CPU risiede ed e eseguita una copia del S.O. che quando necessario comunica con gli altri processori. I programmi vengono eseguiti ripartendoli tra le varie CPU. Programmare un sistema del genere è molto complesso.

Negli asimmetrici invece il S.O. risiede su un processore detto master e che fa da coordinatore, mentre sugli altri processori detti slave vengono eseguiti solo i programmi.

Sistemi distribuiti

Nei sistemi distribuiti più CPU sono tra loro collegate tramite linee telefoniche o bus ad alta velocità, le CPU non condividono tra loro la memoria o altre risorse e per questo sono detti debolmente accoppiati.

Sistemi real-time

I sistemi real-time sono particolari sistemi sviluppati per risolvere problemi nei quali il tempo di esecuzione e determinante, es. un braccio meccanico in una fabbrica di automobili dopo aver determinato la posizione della vettura deve potersi fermare in tempo per non danneggiarla.

Sistemi Operativi

12 Dicembre 2016

Visite: 1678

Leggi tutto: Introduzione ai sistemi operativi

La multiprogrammazione ha come suo obiettivo quello di massimizzare l’uso della CPU, il time-sharing quello di dare l’illusione agli utenti del sistema che tutti i loro processi siano in esecuzione contemporaneamente. Sia l’uno che l’altro obiettivo viene raggiunto tenendo in esecuzione concorrente più processi, e commutando tra loro la CPU. La scelta su come e quando effettuare la commutazione viene presa dallo scheduler.

Sistemi Operativi

12 Dicembre 2016

Visite: 1733

Leggi tutto: Scheduling

Un processo è costituito dall’immagine binaria di un programma caricato in memoria centrale (detta sezione testo), da un program counter ad esso associato, che ne identifica la prossima istruzione da eseguire, dal contenuto dei registri del processore, dalle sue variabili locali contenute nel suo stack e dalle sue variabili globali contenute nella sua sezione dati.

Tutto questo rende un processo molto diverso dal programma (che lo “descrive”) che si trova memorizzato sul disco, quest’ ultimo, infatti, è un’entità statica che non svolge alcun lavoro. Un processo è, invece, un entità dinamica che cambia il suo stato durante la sua esecuzione e che svolge un lavoro, spesso in cooperazione con altri processi che possono essere istanze di programmi diversi (fig.1), o istanze dello stesso programma  (fig.2)(ma anche in questo caso i processi sono entità diverse perché anche se hanno tra loro in comune la sezione testo hanno program counter, stak, e sezioni dati distinte e separate).

Stati di un processo e PCB

Come accennato precedentemente, un processo è un entità dinamica che muta il suo stato durante la sua esecuzione, esecuzione che ha un inizio e una fine. Un processo può avere molti stati intermedi tra il suo caricamento in memoria e la sua deallocazione dal sistema, e il numero di questi stati viene deciso in fase di progettazione del sistema, ma in genere sono i seguenti:

1. New – Quando il processo viene caricato in memoria, cioè creato (per esempio a seguito dell’invocazione del nome del programma o della creazione di un processo figlio mediante l’uso di apposite system call che possono fare in modo che il figlio abbia una copia locale dello spazio di indirizzi del processo padre o sostituisca il suo spazio con nuovi dati completamente diversi da quelli del padre)
2. Ready – Il processo entra in questo stato tutte le volte che attende che il S.O. gli assegni la cpu. Un processo è in Ready quando è pronto per eseguire un CPU-Burst ovvero ha delle computazioni da far fare alla cpu. Può entrare in Ready nei seguenti casi: A) Dopo la sua creazione, se è andata a buon fine. B) Se viene tolto d’autorità dal S.O. dalla cpu mentre la stava ancora utilizzando (a seguito di un interrupt) e quindi vuole ancora usarla. C)Dopo aver concluso un operazione di I/O o dopo aver atteso un evento.
3. Running – Un processo si trova in questo stato quando sta usando la cpu. Entra in questo stato sempre dopo la fase di Ready a seguito di un dispatch. Un dispatcher è un modulo del S.O. che ha il compito di gestire il context switch, più il passaggio dal modo kernel al modo utente (per impedire al processo di eseguire istruzioni privilegiate), il salto alla giusta posizione della sezione testo, puntata dal program counter. In un sistema monoprocessore, un solo processo per volta può trovarsi in stato di running e anche se all’utente sembra che tutti i suoi processi stiano lavorando, uno solo di essi in un dato istante sta usando la cpu. Questa illusione dei processi che lavorano contemporaneamente viene data all’utente perché in un ambiente multiprogrammato il S.O. commuta con elevata frequenza la cpu tra i vari processi che sono in ready, facendoli avanzare tutti un po’ per volta. Tale lavoro viene gestito dal S.O., che deve per ogni commutazione: 1) salvare lo stato attuale del processo in esecuzione, 2) caricare lo stato del nuovo processo, 3) effettuare operazioni di gestione memoria. Tutto questo è tempo sottratto alle computazioni dei processi è si chiama tempo di context switch (cambio di contesto).
4. Waiting – Quando il processo attende che si verifichi un evento come il completamento di un operazione di I/O o la fine del lavoro di un suo processo figlio.
5. Terminated – Quando il processo viene deallocato perché ha finito il suo lavoro. In questo caso il processo è terminato regolarmente. Ma può anche venir eliminato dal sistema perché il processo in questione è figlio di un processo che è stato deallocato (è la politica del sistema non prevede l’esistenza di processi orfani) oppure il processo ha eseguito un operazione considerata dal sistema illecita (come accedere a locazioni di memoria che si trovano fuori dallo spazio a esso allocato).

Essendo i processi oggetti molto diversi tra loro, sia per “forma” (il lavoro che svolgono) che per “consistenza” (la loro dimensione in memoria) un sistema operativo può gestirli in maniera conveniente solo se usa un oggetto che li rappresenta e che gli consente di avere tutte le informazioni necessarie come il suo stato, il suo numero identificativo univoco, il suo program counter, i suoi registri e altre informazioni memorizzate in una struttura dati tutto sommato piccola, almeno se confrontata con il processo al quale si riferisce.

Questo oggetto viene chiamato Process Control Block o PCB.

Il PCB ha anche un puntatore ad altri oggetti del suo tipo, per poter formare con essi delle code di PCB, usate dagli scheduler che vengono descritti più avanti.

Processi cooperanti e comunicanti

Uno degli aspetti più affascinanti della programmazione di un S.O. o dei processi che in esso “vivranno” è la possibilità di realizzare processi specializzati in determinati compiti e fare in modo che essi cooperino tra loro, comunicando, per risolvere problemi più ampi e generici.

Naturalmente i processi restano tra loro concorrenti, cioè competono per usare la cpu e tutte le altre risorse, e se a questo si aggiunge che per essere cooperanti i processi devono anche condividere variabili, file o altre strutture dati, appare evidente che la complessità della programmazione aumenta.

Aumenta perché come progettisti del sistema dobbiamo fornire ai processi un ambiente che non solo consenta, ma che supporti la cooperazione, per esempio fornire meccanismi di comunicazione nativi del sistema, e come progettisti dei processi dobbiamo prevedere metodi di sincronizzazione sull’accesso ai dati condivisi, per evitare problemi di incoerenza e inconsistenza degli stessi,  usando strumenti del sistema operativo o progettandone di nostri (un esempio è quello del processo produttore che memorizza l’informazione creata in un buffer Condiviso con un’ processo consumatore che invece usa l’informazione).

Un processo è detto cooperante se influenza o può essere influenzato da altri processi, ovviamente, se un processo non condivide dati con altri processi e non può influire ne essere influenzato è detto indipendente.

IPC

Per poter cooperare, i processi devono poter comunicare. Il S.O. deve fornire dei meccanismi noti come IPC (interprocess-comunication) attraverso i quali i processi possono scambiarsi dei messaggi che di solito usano per sincronizzare il proprio lavoro (vedi esercizio degli attori e del regista che usano mailBox per comunicare). La struttura di base di un IPC deve fornire almeno le primitive send(msg) e receive(msg) ma, a seconda dell’implementazione, è possibile trovare un livello di dettaglio maggiore, come per esempio altri metodi che inviano non un messaggio ma la conferma del ricevimento di un dato messaggio, o altre primitive che possono essere considerate utili.

In generale, però, se due processi vogliono comunicare, occorre che un terzo oggetto, un canale di comunicazione, esista. Per implementare questo oggetto, occorre stabilire alcune specifiche fondamentali. Tra le più importanti scelte progettuali rientrano quelle che stabiliscono se:

1. I canali tra i processi vengono allocati dal S.O. e i processi li usano per depositare/prelevare i messaggi (in questo caso il canale esiste finché è in esecuzione il sistema), oppure un processo (server) crea i canali e uno o più processi (client) li usano (in questo caso se il server esce dal sistema anche i canali che ha creato vengono deallocati, e se c’è ancora un client che tenta di accedervi, si ha una situazione d’errore. Occorre in questo caso gestire delle condizioni  d’errore o d’eccezione).
2. Un canale può essere bidirezionale ( P1 spedisce e riceve da un canale condiviso con P2) o unidirezionale (su un canale un processo può solo spedire e l’altro solo ricevere ), associato a una sola coppia di processi (il canale tra P1 e P2 non può avere altri processi collegati) o essere condiviso tra più processi (P1 spedisce i messaggi su un canale e P2 o P3 o P4, lo leggono. Sorge il problema di stabilite se chi ha letto il messaggio è il destinatario desiderato da P1, che potrebbe, per saperlo, attendere una “ricevuta di ritorno” ovvero una conferma dal ricevente prima di inviare altri messaggi o procedere con il lavoro).
3. La comunicazione tra i processi è diretta (P1 comunica con P2 specificando il suo riferimento, P1 quindi conosce, perché lo nomina, P2) o indiretta (P1 non sa nulla di P2 e deposita i messaggi in una mail box dove P2 li preleverà).

Thread

A volte capita che un processo abbia la necessità di avere al suo interno più “oggetti capaci di svolgere del lavoro in autonomia” (tra poco verranno chiamati con il loro giusto nome) specializzati in un solo compito (come la ricerca di un record in un database), o ognuno specializzato in un compito specifico (come in un programma per guidare un robot dove all’interno di questo processo esiste un “oggetto” che si preoccupa di catturare gli eventi di un sensore di contatto mentre un altro, contemporaneamente, (cioè in esecuzione concorrente) si occupa di far muovere i motori). Tutti questi “oggetti che svolgono dei compiti in maniera concorrente e cooperante”, se venissero gestiti come processi tradizionali, sarebbero troppo pesanti per il particolare scopo che si intende raggiungere perché ognuno di essi avrebbe un proprio spazio di memoria privato e molti dati sarebbero duplicati inutilmente. Inoltre, verrebbero gestiti (quindi schedulati) dal S.O. che per farlo passerebbe dal modo utente al modo monitor con conseguente contex switch (comprensivo di operazioni di gestione della memoria visto che ogni processo ha un proprio spazio di memoria diverso).

In questi casi particolari possono essere usati i lightweight process o thread.

Un thread è definito LWP (processo leggero) perché è l’unità di base dell’utilizzo della cpu e consiste solo di un program counter, di registri e del suo stack, ma condivide con altri thread sia il segmento di memoria dei dati che quello di testo, ovvero l’ambiente di esecuzione, che altri non è che un processo tradizionale e che prende in questo caso il nome di task

Quindi un task è un processo tradizionale all’interno del quale sono in esecuzione concorrente dei thread (anche uno solo) che condividono tra loro tutto ciò che è allocato al task nel quale si trovano.

Intuitivamente appare già chiaro che il S.O., quando si preoccuperà di gestire il task, effettuerà dei context switch tradizionali, ma quando gestirà i thread in esso esistenti, si avrà un context switch molto meno costoso perché si tratterà di effettuare solo la copia dei registri del tread sulla cpu e il salto alla giusta posizione del programma del thread, ma nessuna operazione di gestione della memoria verrà eseguita che resta la stessa anche per il nuovo thread.

Si potrebbe immaginare un task come un mini sistema operativo specializzato nel gestire i thread anziché i processi, ma solo quelli, perché poi, ogni system call() dei thread o del task verrà valutata e nel caso eseguita dal S.O. sottostante (a meno che il S.O. non fornisca strumenti particolari come descritto fra breve).

Naturalmente anche e soprattutto per i thread valgono le regole di sincronizzazione dell’accesso ai dati condivisi usando i lock sugli oggetti e la politica delle sezioni critiche.

Segue un esempio che può illustrare i vantaggi dei thread in alcune situazioni particolari:

Esempio : Supponiamo di aver realizzato un’applicazione client server dove i client effettuano delle richieste al server, e quest’ultimo le soddisfa ricercando dei dati in un database.

Se il server è un processo senza thread inizia, la ricerca e i nuovi client devono attendere che la ricerca attuale termini prima di vedere soddisfatta la loro, come nella figura seguente.

Se il server è invece un task con più thread (magari allocati dinamicamente), al primo thread viene assegnato il compito di effettuare la prima ricerca, nuovi client verranno soddisfatti “contemporaneamente” perché alla loro richiesta verrà allocato un nuovo thread che ricercherà i dati in maniera concorrente agli altri thread già in esecuzione, essendo la ricerca un’operazione di sola lettura, sullo stesso database possono agire più thread contemporaneamente, come nella fig. seguente.

Ma un sistema operativo che voglia supportare i thread, deve prima di tutto stabilire come essi devono essere implementati, se a livello utente o a livello kernel.

I sistemi più recenti sono stati sviluppati per gestire i thread a livello utente, a livello kernel o entrambi.

Il supporto dei thread a livello utente viene fornito dal sistema offrendo al programmatore delle librerie o package che contengono delle system call “speciali”. Queste system call possono essere usate per realizzare dei task che si occupano dei thread senza mai passare in modalità kernel. Un task, può, in questo ambiente, schedulare personalmente i propri thread senza far intervenire il S.O. e risparmiando quindi ulteriore tempo (il  context switch “leggero”). In questo caso realmente un task può sembrare un mini sistema operativo.

Se il sistema invece gestisce i thread solo a livello Kernel, essi vengono schedulati dal S.O. che gli concede lo stesso quanto di tempo che concede ad un processo tradizionale, avendo sì un context switch leggero ma dovendo comunque passare in modalità kernel per la copia dei registri e il salto all’istruzione da eseguire riferita dal program counter.

Quello che segue è un esempio che mette in evidenza i pro e i contro delle due scelte:

Supponiamo di avere un task A che ha 1 thread al suo interno e un task B che ha 100 thread al suo interno ecco cosa accade se:

1. Il sistema gestisce i thread a livello utente: ogni task (che è un processo) ottiene dal S.O. lo stesso quanto di tempo di cpu, quindi il processo A in un quanto esegue un thread, il processo B il quanto di tempo lo deve dividere fra 100 thread, quindi il task A avrà prestazioni 100 volte superiori. (perché il suo thread avrà il 100% del quanto contro il 10% di ogni thread di B)
2. Il sistema gestisce i thread a livello Kernel: ogni thread di un task verrà schedulato dal S.O. il task B verrà schedulato 100 volte ottenendo la cpu 99 volte in più del task A.

Molti sistemi quindi supportano entrambe le modalità.

I thread nei linguaggi di programmazione

Come un S.O. supporta l’esistenza dei thread all’interno dei task, anche i linguaggi di programmazione dovrebbero fornire degli strumenti adatti alla loro progettazione. I più evoluti in questo senso sono i linguaggi orientati agli oggetti come il C++ e il Java, tanto per citare i più noti.

Tuttavia tra i due il C++ offre lo svantaggio di non fornire come tipo nativo del linguaggio un oggetto thread e per usarlo all’interno dei nostri programmi dobbiamo ricorrere a librerie di terze parti come la VCL della borland o altre di altri produttori (MS ecc.). Ovviamente queste librerie non sono tra loro compatibili e dobbiamo scegliere da che parte stare. Il java invece, fornisce un’enorme quantità di classi (oggetti) già pronti per l’uso tra cui i thread. In Java infatti realizzare un thread è semplice come dichiarare un Integer, ciò che invece occorre fare con attenzione è progettarne il comportamento, specie se i nostri thread sono cooperanti.

Esistono due modi in Java per fare di una nostra classe un thread:

1. Estendere la classe base (superclasse) Thread che java ci mette a disposizione;
2. Oppure implementare l’interfaccia Runnable che ci viene fornita dal linguaggio.

La scelta se usare il primo o il secondo modo è lasciata a noi sulla consapevolezza però che Java non consente l’ereditarietà multipla ovvero la possibilità che ha una classe di estendere contemporaneamente più di una superclasse. Quindi se la nostra classe sta già estendendo un’altra classe, non possiamo contemporaneamente derivare anche la classe Thread. Osserva la figura seguente:

1. La classe A definisce un metodo Draw() che disegna un cerchio;
2. La classe B estende A e ne eredita il metodo Draw, quindi B.draw() disegna un cerchio proprio come farebbe A
3. La classe C estende A ma sovrascrive il metodo draw() che disegna un triangolo, quindi C.draw() disegna un triangolo.
4. La classe D estende contemporaneamente sia B che C e non sovrascrive il metodo draw. Ora D.draw() realizza un cerchio (come B.draw()) o un triangolo (come C.draw()) ?

Questo schema prende il nome di configurazione a diamante (e non è scorretta anzi) è si può verificare se il linguaggio consente l’ereditarietà multipla come il C++. Molti programmi sono stati scritti in questo modo, e funzionano alla perfezione perché il C++ fornisce l’operatore :: che consente di specificare a quale delle superclassi ci si vuole riferire.

In Java invece questo operatore non esiste perché, come scelta progettuale ben precisa, l’ereditarietà multipla non è consentita. Questo perché un programmatore “distratto” potrebbe usare male sia un operatore del genere, sia le caratteristiche del “diamante”, aspettandosi cioè un certo comportamento dal suo programma e ottenendone un altro, ma stiamo parlando di un programmatore “distratto”.

Java quindi non ti fa “sbagliare” neanche se lo vuoi se lo vuoi fare apposta, ed è un bene o un male a seconda del programma che vuoi realizzare. Ma mette comunque a disposizione dei programmatori degli strumenti che fanno sì che le caratteristiche di una classe derivino da più oggetti preesistenti. Nel nostro esempio la classe D vuole estendere la classe B, lo può fare ma non può contemporaneamente estendere la classe C. Però se C venisse implementata come interfaccia allora D estenderebbe B e implementerebbe C come nella figura seguente:

Le interfacce sono classi che non possono essere istanziate, perchè non sono implementate, ovvero forniscono solo le firme dei metodi ma non la loro implementazione. Tale implementazione è lasciata alla classe che la estende. Questo garantisce che in una configurazione a diamante in java non può esservi ambiguità. Perche sé il metodo (nel esempio il metodo Draw) esiste, lo si è ereditato dalla superclasse, se non esiste nella superclasse lo si deve implementare al livello corrente di derivazione, altrimenti non si può compilare.

Quindi tornando ai thread con Java, se la mia classe non estende altre classi per implementare un thread basta estendere la superclasse Thread come nell’esempio seguente.:

public class nomeDellaMiaClasse extends Thread { ... }

Se invece la mia classe estende un’altra classe ma vuole essere anche un thread allora devo implementare l’interfaccia Runnable es.:

public class nomeDellaMiaClasse extend unAltraClasse implements Runnable { … }

Come i processi, anche i thread hanno vari stati, e nello specifico di java gli stati che un thread può assumere (nella JVM) sono:

1. New – Il thread è in questo stato subito dopo la sua inizializzazione (da non confondere con la sua dichiarazione che non alloca memoria per il thread ma per il suo riferimento, ne con la definizione che non alloca memoria ma ne definisce solo la struttura, es: public class Produttore extend Thread {…} e una definizione, mentre Produttore p; è una dichiarazione, ma Produttore p=new Produttore() e una inizializzazione e solo in questo caso p è in stato di New).
2. Runnable – Un thread è in questo stato mentre esegue il suo metodo run (che noi come programmatori dobbiamo realizzare). Il metodo run viene eseguito dopo l’invocazione del metodo start() (che possiamo se vogliamo sovrascrivere).
3. Blocked – Un thread può essere temporaneamente sospeso dalla cpu dal task o da se stesso invocando una sleep() o altri metodi della classe.
4. Dead – Un thread entra in questo stato subito dopo l’invocazione del metodo stop () o subito dopo aver terminato il metodo run (), nella JVM i thread in dead vengono de allocati quando necessario usando una tecnica di recupero dello spazio inutilizzato nota come garbage collection (questo vale per tutti gli oggetti, infatti, in java si può allocare dinamicamente la memoria definendo per un oggetto un costruttore, ma non è necessario de-allocarla definendo un distruttore, farà tutto la JVM).

Sistemi Operativi

12 Dicembre 2016

Visite: 1197

Leggi tutto: Processo

Un deadlock, o abbraccio mortale, si ha quando uno o più processi non possono proseguire nel loro lavoro perché bloccati in attesa che si verifichi un evento (il rilascio di una risorsa) che può essere generato solo da un altro processo, anch’ esso in attesa per lo stesso motivo. Attenzione però a non confondere la starvation con il deadlock. In entrambi i casi si tratta di una condizione d’attesa di un processo, ma:

1. Nella starvation l’attesa è indefinita, nel deadlock l’attesa è infinita. Ciò vuol dire che un processo che subisce starvation, prima o poi, magari dopo 10 anni, magari l’ultimo giorno di attività del sistema, ovvero quando non sono rimasti altri processi sulla macchina tranne il processo in questione riuscirà a completare il suo lavoro uscendo dall’attesa spontaneamente. Un deadlock invece coinvolge un processo, è questi non uscirà mai più da tale situazione, anzi con il passare del tempo sempre più processi del sistema verranno coinvolti, “abbracciandosi”.
2. La starvation dipende dall’attività del sistema, che magari dà la precedenza a certi processi anziché ad altri, ritardandone l’esecuzione, il deadlock invece dipende dall’attività dei processi, che come nel caso dei processi che usano i semafori (visti precedentemente) possono essere progettati male, introducendo delle regioni critiche che causano un deadlock.

Quindi appare già chiaro che un deadlock, per un progettista di sistemi, è una situazione abbastanza spiacevole da gestire, perché dipende da come sono scritti i processi, e non dalla politica del sistema. Ma analizzando le caratteristiche di un deadlock, è possibile sviluppare strategie per prevenire, evitare, ripristinare un deadlock. Prima di analizzare in dettaglio tali caratteristiche è opportuno specificare che un processo entra in deadlock quando ha bisogno di usare una risorsa che non è disponibile, e quindi attende che chi la detiene la rilasci. Ma se chi detiene la risorsa è anch’esso un processo in attesa per lo stesso motivo, resteranno entrambi bloccati per sempre. Come se non bastasse da questo momento in poi tutti i processi che vorranno usare le risorse possedute dai processi abbracciati ( bloccati ) entreranno anche loro in deadlock, portando col tempo le prestazioni del sistema a un livello inaccettabile.

Quindi le risorse sono la chiave di un deadlock. Un processo per ottenere una risorsa effettua questa sequenza di operazioni:

1. La richiede, usando delle apposite system call, al sistema operativo che, se la risorsa è libera, soddisfa immediatamente il processo altrimenti lo fa attendere.
2. La usa, se è un file ci scrive o ci legge, se è una stampane ci stampa.
3. La rilascia, usando delle system call, quando non gli serve più.

Ovviamente il primo processo che entra in deadlock non effettua il punto 3, gli altri non superano il punto 1.

Il deadlock però non è un evento molto frequente, è perché si verifichi occorre che quattro condizioni, che lo caratterizzano, siano rispettate contemporaneamente. Quindi basta negare una sola delle seguenti caratteristiche perprevenire un deadlock.

1. Mutua esclusione. Questa condizione è vera quando almeno una risorsa tra quelle contese dai processi è non condivisibile, ovvero può essere assegnata in un dato istante a un solo processo per volta, quindi chi si blocca su questa risorsa, bloccherà tutti gli altri che in futuro la vogliano usare. Negare la mutua esclusione è difficile, perché alcune risorse non possono essere condivisibili. Una stampante, infatti, se fosse condivisibile stamperebbe un po’ per un processo, un po’ per un altro sullo stesso foglio! (a meno che non si usi una tecnica di spooling).
2. Possesso attesa. Questa condizione esiste se esiste un processo che richiede risorse già possedute da altri processi mentre continua a detenere almeno una risorsa non condivisibile. Per negare questa condizione bisogna garantire che un processo che detiene una risorsa, non possa chiederne altre. Bisogna quindi progettare un protocollo di richiesta risorse che per esempio imponga al processo richiedente di rilasciare tutte le risorse possedute prima di entrare in attesa di una risorsa non disponibile, oppure che dichiari la sequenza delle richieste che effettuerà durante la sua esecuzione, in modo che il sistema l’ analizzerà per vedere se, quando combinate con la sequenza di un altro processo, possono causare un deadlock. Negare questa condizione adottando queste strategie produce uno scarso uso delle risorse, e può causare starvation per quei processi che dichiarano una sequenza di richieste che il sistema considera rischiosa.
3. Impossibilità di prelazione. Questa condizione è vera se le risorse non sono prelazionabili, cioè non possono essere tolte d’autorità ad un processo. Quindi un processo che le detiene le rilascerà spontaneamente quando avrà finito di usarle. Per negare questa condizione, bisogna progettare un protocollo che, invece di prelazionare le risorse ad un processo che sta per entrare in attesa di un’altra risorsa posseduta da un altro processo, congela tutto il processo. Il processo quindi sarà sospeso, e le risorse che aveva gli possono ora essere tolte, e gli verranno restituite solo quando la nuova risorsa che sta attendendo è disponibile. Il processo riprenderà il lavoro dal punto in cui era stato interrotto come se niente fosse accaduto, ma solo se potrà recuperare tutte le risorse che già deteneva. Infatti, se nel frattempo le risorse che aveva prima dell’interruzione sono state allocate ad altri, il processo non potrà riprendere la sua esecuzione per ora (starvation).
4. Attesa circolare. Questa condizione esiste se in un insieme di processi composto da P0 a Pn, il processo Pi è in attesa delle risorsa posseduta dal processo P(i+1)%n. Per negare questa condizione si potrebbe realizzare una funzione che, in base ad un indice numerico assegnato ad ogni risorsa, stabilisce se quella risorsa una volta concessa al processo “Pi” può portare ad un’attesa circolare, perché esiste già un processo (P(i+1)%n)) in attesa sulla stessa risorsa. Nel problema dei filosofi, l’attesa circolare è stata negata garantendo che dei 5 filosofi solo 4 per volta possono sedersi al tavolo.

Grafo di allocazione Risorse

Un sistema costituito da processi che usano o attendono risorse, può essere facilmente rappresentato da una struttura dati come un grafo orientato. Un grafo orientato è costituito da un’insieme di vertici, collegati tra loro da archi. Un arco è orientato se è diretto da un vertice ad un altro, come nella figura:

Un grafo di allocazione risorse è una specializzazione di un grafo orientato, infatti è costituito da due partizioni di vertici. In una partizione si trovano le risorse, rappresentate graficamente da vertici rettangolari, nell’altra partizione, si trovano i processi, rappresentati graficamente da cerchi.

Può esistere un arco orientato da un vertice processo Pi a un vertice risorsa Rj, scrivendo Pi->Rj, per indicare che il processo rappresentato dal vertice P è in attesa di ottenere la risorsa rappresentata dal vertice R, l‘arco in questo caso si chiama arco di richiesta.

Può esistere un arco orientato da Rj a Pi, scrivendo Rj->Pi, in questo caso si legge che la risorsa Rj è usata dal processo Pi, l’arco in questo caso si chiama arco di assegnazione.

In un sistema dinamico, rappresentato da un grafo di allocazione risorse, quando un processo vuole usare una risorsa la richiede, e nel grafo viene inserito un arco di richiesta, che si trasforma immediatamente, se la risorsa è libera, in arco d’assegnazione. Se la risorsa non è libera l’arco di richiesta permane, e indica che il processo, rappresentato dal vertice dal quale parte l’arco, è in attesa, osserva la figura.

Essendo il grafo di allocazione risorse una rappresentazione del sistema, possiamo usarlo per reperire alcune informazioni utili sul sistema, per esempio possiamo determinare se il sistema è in deadlock. Infatti se seguendo gli archi uscenti da un vertice processo, esplorando in profondità il grafo, ritorniamo più di una volta su un vertice, vuol dire che nel grafo esiste un ciclo, e in questo caso nel sistema esiste la condizione di attesa circolare, e quindi esiste un deadlock. Come nella figura seguente.

Esistono degli algoritmi, che partendo da un vertice arbitrario, verificano la presenza di un ciclo in un grafo, e possono essere usati per rilevare un deadlock, e nel caso vi sia, ripristinare la situazione. Per ripristinare la situazione si potrebbe, per esempio, selezionare un processo tra quelli coinvolti nel deadlock (informazione reperibile sempre grazie al grafo) e ucciderlo, riportando però tutti gli altri processi ad uno stato del lavoro, precedentemente salvato. Il problema dei filosofi usa, a titolo dimostrativo, un grafo per verificare il sistema. Questa strategia è un po’ costosa sia in termini di spazio (per la memorizzazione del grafo), sia in termini di tempo (per l’esplorazione periodica dello stesso), e se applicata a sistemi con più istanze per ogni tipo di risorsa, allora la complessità dell’algoritmo di rilevamento cicli, aumenta, perché in questo caso, non basta trovare un ciclo nel grafo per essere certi che nel sistema esiste un deadlock, ma occorre accertarsi che, per ogni risorsa coinvolta,  non vi siano altre istanze allocate a processi bloccati es:

Evitare i deadlock

Abbiamo visto come negando una delle condizioni necessarie si possa prevenire un deadlock, e come usando un grafo si possa ripristinare la situazione. Esiste anche una politica che evita il verificarsi di un deadlock.

Tale strategia si basa sul concetto di stato sicuro, associato al concetto di sequenza sicura.

Uno stato sicuro è uno stato in cui non esiste un deadlock, per contro uno stato non sicuro non implica necessariamente la presenza di un deadlock, ma indica che, data la configurazione attuale delle allocazioni a i processi, è possibile che una prossima richiesta di risorse, causi un deadlock. Quando il sistema viene avviato e non ha ancora caricato nessun processo è sicuramente in uno stato sicuro. Per evitare un deadlock occorre far persistere questo stato sicuro anche dopo aver assegnato risorse ad un processo. Per far in modo che il sistema resti sempre in uno stato sicuro, gli algoritmi preposti a tale scopo lavorano sul concetto di sequenza sicura. Una sequenza di richieste è sicura se è possibile allocare tutte le risorse richieste dai processi, senza passare in uno stato non sicuro, dove cioè il S.O. non potrebbe far fronte a future richieste senza mettere in attesa circolare uno o più processi. Più formalmente quindi, una sequenza di processi da P0 a Pn è sicura per lo stato di allocazione attuale se, per ogni Pi, le risorse che Pi può ancora chiedere al sistema, gli possono essere date utilizzando quelle ancora disponibili, più quelle possedute da tutti i processi Pj con j<i. Essendo Pj stato soddisfatto con lo stesso criterio, allora lui potrà finire il suo lavoro senza bloccarsi perché Pj-1 gli potrà dare le risorse che eventualmente gli servono e cosi via fino a P0.

Algoritmo del banchiere

Un sistema che voglia evitare i deadlock, può usare un algoritmo noto come algoritmo del banchiere. Questo algoritmo si divide in due parti.

1. Algoritmo di richiesta delle risorse.
2. Algoritmo di verifica della sicurezza.

Utilizza inoltre alcune strutture dati per stabilire se una generica richiesta di risorse di un certo processo, fatta in un dato istante, possa essere soddisfatta perché non porta il sistema in uno stato non sicuro.

Queste strutture dati sono delle matrici e dei vettori, che codificano la rappresentazione dei processi e delle risorse nel sistema. Esse possono facilmente essere realizzate come classi in un linguaggio O.O. come java, e devono supportare uno stile di programmazione che consenta di confrontarle, di sommarle, di sottrarle e di copiarle tra loro.

Le strutture dati sono:

1. Available. Un vettore di m elementi. Ogni elemento indica il numero di istanze disponibili per quella risorsa. Es.: Available[j]=k significa che sono disponibili k istanze della risorsa Rj.
2. Max. Una matrice n x m, che definisce la richiesta massima di risorse da parte di ciascun processo. Questa dichiarazione di richieste viene fatta da un processo appena viene lanciato.
3. Allocation. Una matrice n x m, che definisce il numero di risorse allocate ad ogni processo.
4. Need. Una matrice n x m che indica la necessità residua di risorse che ogni processo ha per terminare il suo lavoro. Need è ottenuta da Max - Allocation.

Un sistema operativo quindi deve avere un processo preposto all’esecuzione dell’algoritmo del banchiere, sempre in esecuzione. Quando un nuovo processo, o un processo già esistente “Pi” ha bisogno di usare delle risorse, invia una richiesta al S.O. che la passa all’algoritmo del banchiere sotto forma di vettore che chiamiamo Request[i]. L’algoritmo del banchiere ora deve dire al S.O. se questa richiesta porta il sistema in uno stato non sicuro, o lo lascia in stato sicuro. Per dare questa risposta l’algoritmo del banchiere esegue l’algoritmo di richiesta risorse:

void RichiestaRisorse(Vettore Request_i){

/*se le richieste attuali sono superiori alla necessità residua del processo, allora il processo sta imbrogliando, e la sua richiesta non è lecita*/

    if(Request_i>=need_i){

      "La richiesta di Pi non è lecita.";

      return;

    }

/*Se le richieste sono superiori alle risorse disponibili, Pi deve attendere*/

    if(Request_i > available){

      "Pi deve attendere, le ris. non sono disp.";

      return;

    }

/*Altrimenti posso simulare l’allocazione delle risorse a Pi, modificando le matrici, per ottenere un nuovo stato di allocazione…*/

      Available=Available-Request_i;

      Allocation_i=Allocation_i+Request_i;

Need_i=Need_i-Request_i;

/*Se questo stato risulta sicuro, risposta che mi dà l’algoritmo di verifica sicurezza, allora dico al S.O. che Pi può essere eseguito...*/

    if(AlgoritmoVerificaSicurezza()==true){

      " Pi viene eseguito";

    }else{

/*Altrimenti Pi deve attendere e io ripristino la situazione così come era prima */

Available.undo();

      Allocation_i.undo();

Need_i.undo();

    }

  }

Nell’algoritmo di richiesta risorse viene chiamato l’algoritmo di verifica sicurezza, che è il seguente:

boolean AlgoritmoVerificaSicurezza(){

//alloca due vettori come di seguito

finish=new Vettore( di lunghezza n e con tutti gli elementi a false );

work=new Vettore( di lunghezza m è = ad available );

//cerca un i che soddisfi contemporaneamente queste condizioni    

while( esiste un finish[i]==false e Need_i<= Work, (ma ripeti questa ricerca per non più di n volte) ){

//modifica i vettori e vedi se esiste un altro i

          work=work + allocation;

          finish[i]=true;

}

//… adesso cerca nel vettore finish un Pì che non può terminare, se esiste lo stato non è sicuro

for( tutti gli i di finish ){

      if(finish[i]==false){

            "Stato NON sicuro";

            return false;

      }

}

return true;

}

Sistemi Operativi

12 Dicembre 2016

Visite: 1480

Leggi tutto: Deadlock

Valutazione attuale: 5 / 5

Quando in un S.O. vi sono dei processi cooperanti (cioè che condividono dei file o dei dati), ma anche quando in un task esistono più thread (che hanno in comune il loro ambiente d’esecuzione compresa l’area dati), occorre fornire dei meccanismi di sincronizzazione sull’accesso concorrente a tali dati condivisi. Questi meccanismi di sincronizzazione devono vincolare il comportamento dei processi  in modo che il fenomeno noto come race condition non si verifichi. Con il termine di race condition si descrive il fenomeno per il quale un output prodotto dal lavoro di più processi cooperanti dipende dalla sequenza con cui i processi effettuano le loro operazioni, sequenza che può essere diversa di volta in volta e che quindi produce risultati diversi per ogni sequenza, di cui uno solo è quello esatto, cioè quello che è prodotto dalla sequenza giusta.

Sistemi Operativi

12 Dicembre 2016

Visite: 2291

Leggi tutto: Sincronizzazione dei processi