Sistemi Operativi

::cck::20::/cck::
::introtext::::/introtext::
::fulltext::

 

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.

::/fulltext::

Write comment (0 Comments)

::cck::23::/cck::
::introtext::

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.

 

::/introtext::
::fulltext::

Scheduling della CPU

 

Lo scheduler è un algoritmo che basa il suo funzionamento sul fatto che ogni processo divide la propria esistenza in cicli di utilizzo della CPU e attesa di I/O.Naturalmente, un processo inizia sempre con un’operazione sulla CPU (che prende il nome di CPU-burst) per poi proseguire con un’operazione di I/O (che prende il nome di I/O-burst), e ripete quest’alternanza di operazioni per un certo numero di volte.Alla fine però il processo termina sempre con un CPU-burst.È possibile catalogare i processi in due categorie:

  1. Quelli che hanno pochi CPU-burst brevi e molti CPU-burst lunghi, detti: CPU-bound.
  2. Quelli che hanno pochi CPU-burst lunghi e molti CPU-burst brevi, detti: I/O-bound.

Lo scheduling della CPU è gestito dallo scheduler a breve termine, che in generale interviene ogni volta che un processo smette di usare (volontariamente o no) la CPU. A questo punto lo scheduler deve selezionare uno dei processi pronti per eseguire computazioni, quindi la scelta del processo è ristretta all’insieme dei processi in stato di Ready, e assegnargli la CPU. I processi in stato di Ready, o per essere più precisi i loro PCB, sono inseriti in una coda chiamata readyQueue che è una coda di tipo FIFO, quindi lo scheduler selezionerà i processi da assegnare alla CPU semplicemente leggendo il prossimo processo restituito da tale coda.Lo scheduler può essere con o senza prelazione a seconda che il processo lasci d’autorità o volontariamente la CPU.Scheduling senza prelazione (nonpreemptive)Lo scheduling senza prelazione non interviene mai durante un CPU-burst di un processo in esecuzione, che può occupare la CPU per tutto il tempo necessario. Questo scheduling è ottimo per massimizzare l’uso della CPU ma non per dare l’illusione all’utente che tutti i suoi processi lavorino simultaneamente, perché finché la CPU è occupata da questo processo, gli altri dovranno attendere.Scheduling con prelazione (preemptive)Lo scheduling con prelazione viene usato da quei sistemi che hanno la possibilità di interrompere un processo mentre è in stato di Running (cioè è in corso il suo CPU-burst), reinserendolo nell’insieme dei processi in stato di Ready, e dando la CPU ad un altro processo.Lo scheduler può intervenire perché il nuovo processo ha una priorità più alta di quello attualmente sulla CPU, o perché esiste un limite di tempo sull’uso della CPU che il processo ha superato, quindi sarà prelazionato e potrà finire le sue computazioni solo quando verrà di nuovo estratto dalla readyQueue.Uno scheduler nonpreemptive non presenta grossi ostacoli d’implementazione, cosi come non ne presenta lo scheduler preemptive. Quest’ultimo però deve essere accompagnato da una corretta politica di gestione dei processi cooperanti (che lavorano su dati condivisi), prelazionati.Infatti, in assenza di un meccanismo di sincronizzazione o di sicurezza (lock dei dati e gestione delle sezioni critiche), può verificarsi il seguente caso:

  1. Il processo A lavora in cooperazione con il processo B, condividendo con esso un file nel quale è memorizzato un numero intero il cui valore in un dato momento e 5.
  2. Al tempo T0 A legge dal file (che si trova sul disco, quindi sta effettuando un’operazione I/O burst) il numero 5 e lo memorizza in una sua vbl, poi entra in stato di Ready (perché vuole incrementare questo valore è questa operazione la deve fare la CPU) e attende che il S.O. gli dia la CPU.
  3. Al tempo T1 B fa la stessa cosa di A, legge 5 e si accoda nella readyQueue dietro A.
  4. Al tempo T2 finalmente A passa in stato di Running, esegue 5=5+1, quindi il valore della sua vbl è 6, ma non fa in tempo a terminare il suo CPU-burst che viene prelazionato in favore del processo B, quindi A ora è di nuovo nella readyQueue e non ha ancora salvato il nuovo valore ( =6 ) della sua vbl nel file condiviso ( =5 ).
  5. Al tempo T3 quindi B che ha nella vbl il valore di 5 effettua l’incremento di 1 e nella vbl ha il nuovo valore =6, anche B viene prelazionato in favore di A e torna nella readyQueue
  6. Al tempo T4 A torna sulla CPU è fa richiesta mediante una system call di scrivere il valore della sua vbl=6 sul file, il S.O. pone A in stato di Waiting e A scrive 6 nel file.
  7. Al tempo T5 B fa lo stesso, e scrive nel file il suo valore che è sempre 6.

Il valore corretto avrebbe dovuto essere a questo punto 7, perché 5 + 1(sommato da A) +1(sommato da B)=7, sul file è invece presente 6.Questo perché un processo è stato prelazionato prima che potesse memorizzare le modifiche, in favore di un atro processo che lavorava sugli stessi dati e che non sapeva nulla del lavoro concorrente di altri processi. La soluzione a questo problema prevede l’adozione di politiche di sincronizzazione dei processi mediante l’uso di tecniche descritte più avanti.Criteri per scegliere l’algoritmo di schedulingIn fase di progettazione di un S.O. occorre stabilire a che tipo di attività è rivolto e l’algoritmo di scheduling deve essere scelto in base ai seguenti criteri:

  1. Se si vuol massimizzare l’utilizzo della CPU è opportuno scegliere un’algoritmo di scheduling che garantisca un carico della CPU che vari dal 40 al 90%, e per questo sia un algoritmo con prelazione che senza prelazione può andar bene, ma bisogna considerare che un algoritmo con prelazione spreca un po’ di tempo di CPU (il 10% è accettabile) per la gestione dei più frequenti context switch, mentre in un algoritmo senza prelazione tutto il tempo di CPU è destinato al lavoro utente.
  2. Se si vuol massimizzare il Throughput, cioè il numero di processi completati in un’unità di tempo, la scelta è l’uso di algoritmi senza prelazione, perché hanno un’incidenza minore del context-switch sul tempo totale di un processo, un solo context switch per ogni processo (altrimenti al tempo di durata del processo, va sommato il tempo di più context-switch con il risultato che nella stessa unità di tempo vengono completati meno processi).
  3. Se si vuol minimizzare il tempo di turnaround, che è dato dalla somma dei tempi che il processo passa in attesa di entrare in memoria (scheduling a lungo e medio termine), in attesa nella readyQueue, in esecuzione sulla CPU e effettuando operazioni I/O burst, l’algoritmo da scegliere è con prelazione perché almeno per quanto riguarda la CPU che è una risorsa prelazionabile, nessun processo la monopolizzerà per molto tempo a svantaggio di altri processi. Ma un disco, per esempio, non è una risorsa prelazionabile, quindi se si usa questo criterio di scelta, usando un algoritmo piuttosto che un altro le differenze che si hanno non sono sostanziali, ecco perché di solito si usa di più il seguente criterio di scelta anziché questo.
  4. minimizzare il tempo di attesa che è dato solo dalla somma dei tempi che il processo passa nella readyQueue, dove l’algoritmo di schedulig può incidere. In questo caso la scelta va su un algoritmo con prelazione, o almeno con priorità, cioè viene data la precedenza ai processi con tempi di utilizzo della CPU (CPU burst) minori.
  5. minimizzare il tempo di risposta, cioè l’intervallo che intercorre tra lo stato di New di un processo è la stampa dei suoi primi risultati, in questo caso è opportuno usare un algoritmo senza prelazione, perché un processo che si trova in Running, non viene mai interrotto dal S.O. e può produrre un output molto prima che se ritornasse come ultimo elemento nella readyQueue a seguito di una prelazione.

Scheduling first-come, first-servedQuesto scheduler è senza prelazione ed è il più semplice sia da capire che da implementare. Usa una readyQueue implementata come FIFO, e ciò che fa, è attendere che il processo attualmente sulla CPU, termini il suo CPU burst, e richieda di effettuare un  I/O burst, di uscire dal sistema oppure di attendere un determinato evento (il completamento del lavoro di un figlio).A questo punto lo scheduler FCFS interviene selezionando il prossimo processo dalla readyQueue e lo assegna alla CPU. Questo algoritmo massimizza l’uso della CPU (che viene usata sempre), ma non è adeguato per sistemi time-sharing, perché non minimizza il tempo di attesa di un processo, che dipende dall’ordine con cui entrano nella coda.Inoltre, presenta un’inconveniente noto come effetto convoglio, dove molti processi I/O bound sono costretti ad accodarsi e ad attendere un processo CPU bound.Per esempio nell’ Applet seguente è possibile simulare tale situazione creando i seguenti processi:P1 cpu-burst= 100 io-burst=100P2 cpu-burst= 10  io-burst=10P3 cpu-burst= 10  io-burst=10P4 cpu-burst= 10  io-burst=10Ciò che accade è che il processo CPU bound (P1) occupa per molto tempo la CPU e i processi I/O bound si trovano in attesa nella readyQueue. Quando il processo CPU bound (P1) lascia la CPU e effettua operazioni di I/O i processi I/O bound la usano e la liberano presto, entrando nella waitingQueue e rimanendoci per un po’ perché il dispositivo di I/O è ancora occupato da P1. Ora la CPU è inutilizzata. Per lo stesso motivo lo sarà il dispositivo d’I/O al prossimo CPU burst del processo CPU bound (P1).Lancia L’applet , ma ricordati di deselezionare la pausa prima di creare i processi.Sheduling shortest-job-firstQuesto algoritmo, riesce a ottimizzare (minimizzando) il tempo medio di attesa dei processi nella readyQueue riordinandola in base al successivo CPU burst. Processi con il CPU burst più breve vengono eseguiti per primi. Questo dato però non è noto al sistema e quindi può solo essere calcolato basandosi sui CPU burst passati, assumendo che i futuri CPU burst saranno simili ai passati.Per predire i CPU burst questo algoritmo effettua la media esponenziale delle lunghezze dei CPU burst precedenti nel seguente modo:τ n+1 = α tn + ( 1 – α ) τ ndove:α =peso relativo alla storia recente ( α tn )  e a quella passata ( ( 1 – α τ n ).Se: α=0 la storia recente non ha effetto.Se α=1 ha peso solo il CPU burst recente.Se α=1/2 storia recente e passata hanno lo stesso peso.τ n+1 =Valore previsto per il CPU burst successivo.τ n =Valore previsto, calcolato in passato.α tn =Lunghezza del CPU burst attuale.I processi in stato di ready vengono, quindi, inseriti in una coda ordinata o readyQueue con priorità o in un’altra struttura dati (come un heap) dalla quale è possibile estrarre i processi in base a una certa chiave come per esempio in base al più piccolo valore di CPU burst successivo, anziché in una semplice FIFO. Questo algoritmo può essere con prelazione o senza prelazione.Con prelazione: L’algoritmo interviene anche quando, nel mentre che, un processo è in esecuzione sulla CPU, nel sistema si presenta un processo, in stato di Ready, con CPU burst successivo inferiore al CPU burst del processo attualmente in stato i Running, quindi l’algoritmo prelaziona la CPU al processo corrente in favore di quello nuovo (valgono i discorsi sulla sincronizzazione dei processi cooperanti prelazionati fatti precedentemente).Senza prelazione: Quando l’algoritmo lascia comunque finire il CPU burst del processo corrente, anche se più lungo del CPU burst di un processo nuovo entrato.Un inconveniente di questo algoritmo è la starvation.La starvation, o attesa indefinita, si ha quando un processo non viene mai eseguito perché altri processi riescono ad ottenere per primi la CPU, per esempio perché hanno una priorità più alta. Si verifica questo caso quando, nella readyQueue ordinata in base al CPU burst più breve, un processo che ha il CPU burst più alto di tutti i nuovi processi non verrà mai selezionato come processo da eseguire, perché finirà, ad ogni ordinamento, sempre in ultima posizione.Nell’Applet seguente provate a creare i seguenti processi:P1 cpu-burst=100 io-burt=a piacereP2 cpu-burst=10  io-burt=10P3 cpu-burst=10  io-burt=10P4 cpu-burst=10  io-burt=10Ciò che accade è che P1 sarà sempre in ultima posizione nella readyQueue ordinata e non verrà mai eseguito se non dopo che tutti i processi con CPU burst brevi saranno terminati. Se nel sistema continuassero ad entrare nuovi processi I/O bound, P1 resterebbe per sempre in Ready.Lancia AppletPer superare la starvation è possibile implementare un meccanismo di aging o invecchiamento del processo. Con questa tecnica un processo aumenta gradualmente nel tempo la sua priorità, fino ad arrivare ad un certo punto ad essere il processo con priorità massima e quindi sicuramente verrà eseguito.Scheduling round-robinQuesto algoritmo è un algoritmo con prelazione ed è progettato appositamente per i sistemi time sharing, visto che dà l’illusione all’utente che tutti i suoi processi procedano nel lavoro simultaneamente. Questo risultato è ottenuto commutando la CPU tra i vari processi a intervalli regolari di tempo. Tale intervallo, che deve essere di piccola entità, è chiamato quanto di tempo o time slice. La strategia del round robin seleziona il prossimo processo dalla readyQueue che è di tipo FIFO, la stessa usata dal FCFS, e assegna la CPU a tale processo. Se il processo termina il suo CPU burst prima dello scadere del quanto di tempo, lo scheduler lo mette nella waitingQueue o lo dealloca dalla memoria a seconda del motivo per cui il processo ha rilasciato la CPU. Se, invece, allo scadere del quanto di tempo il processo ha ancora lavoro di CPU da fare, lo scheduler interviene, gli prelaziona la CPU, lo inserisce nella readyQueue e dà la CPU al prossimo processo restituito dalla readyQueue. Le prestazioni di questo algoritmo dipendono dalla lunghezza del quanto di tempo, dal quale dipende anche il comportamento che, per quanti di tempo molto lunghi (più lunghi dei CPU burst dei processi), può essere lo stesso dell’algoritmo FCFS. Mentre per quanti di tempo troppo corti, l’algoritmo potrebbe prelazionare talmente frequentemente la CPU tra i processi, che “sprecherebbe” più tempo per il dispatch che per le computazioni del processo stesso, che in questo modo avanzerebbe di una piccolissima quantità di lavoro per volta, dando l’impressione all’utente che invece di un processore potente dedicato ad un solo processo, esistano tanti processori lenti che eseguono ciascuno un processo. Per esempio:Se la maggior parte dei processi hanno CPU burst = 10 e il time slice = 12 (consideriamolo molto lungo) allora l’algoritmo si comporta come il FCFS perché si ha un context switch per processo, e precisamente quando questi lascia la CPU spontaneamente. All’utente non è data l’impressione che i suoi processi siano tutti in esecuzione perché quelli nella readyQueue attenderanno la fine dei processi che di volta in volta usano la CPU.Se, invece, il time slice è per esempio = 6, sempre con processi con CPU burst=10, allora abbiamo due context switch per processo, uno che lo prelaziona all’incirca alla metà del lavoro e un altro quando il processo termina. In questo caso più processi progrediscono con il lavoro un po’ per volta (ad una velocità accettabile) è l’obbiettivo del time slice è ottenuto.Se invece il quanto è troppo breve, per esempio = 1, allora avremo talmente tanti context switch che il sistema dedicherà alle computazioni dei processi utente meno tempo di quanto è costretto a dedicarne alla gestione dei context switch, e questa è una situazione inaccettabile.L’applet seguente simula un sistema con scheduling RR, provate a variare il time slice per vedere come può diventare simile al FCFS (dopo aver creato un po’ di processi selezionate il time slice per esempio a 1000, me non dimenticate di deselezionare la pausa).

Lancia Applet

Appare evidente che la scelta del quanto di tempo deve essere attenta.

::/fulltext::

Write comment (0 Comments)

::cck::21::/cck::
::introtext::

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.

::/introtext::
::fulltext::

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).
::/fulltext::

Write comment (0 Comments)

::cck::24::/cck::
::introtext::

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:

::/introtext::
::fulltext::
  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;

}

::/fulltext::

Write comment (0 Comments)

::cck::22::/cck::
::introtext::

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.

::/introtext::
::fulltext::

 

Il punto in cui, durante l’esecuzione dei processi, vengono modificate vbl condivise, prende il nome di sezione critica, ed è questa che deve essere protetta adottando dei protocolli di sincronizzazione.

La sezione critica

Per proteggere i dati condivisi da accessi che possono causare inconsistenza o incoerenza degli stessi occorre progettare un protocollo di sincronizzazione che tutti i processi devono usare per cooperare.

Tale protocollo deve dividere il codice in una sezione non critica, dove non c’è pericolo di accedere a dai condivisi, e una sezione critica che deve essere mutuamente esclusiva, ovvero un solo processo per volta può eseguire il codice marcato come tale.

Per garantire questo, ogni processo deve tentare di accedere alla sezione critica usando un protocollo d’entrata chiamato entry section, e comunicare di essere uscito dalla sezione critica usando un protocollo d’uscita chiamatoexit section. Come nella figura seguente.

Fig.1

Per far sì che il problema della sezione critica possa essere risolto occorre che vengano soddisfatti i seguenti requisiti:

  1. Mutua esclusione. Vedi fig.1
  2. Progresso. Un processo può progredire, o in altre parole superare l’entry section, ed entrare nella sua sezione critica solo dopo che qualcuno gli ha dato il permesso. La decisione se accordare o meno tale permesso deve essere presa solo dai processi che si trovano nella loro sezione critica, perché sono loro che sanno se i dati su cui stanno lavorando possono subire interferenze dal lavoro di un nuovo processo che esegue la sua sezione critica.
  3. Attesa limitata. Deve esistere un limite al numero di permessi non accordati ad un processo che vuole eseguire la sua sezione critica e che invece viene superato da altri processi.

Semafori

Una soluzione al problema della sezione critica può essere trovata implementando un oggetto che ponga in attesa un processo che tenta di accedere a una risorsa già occupata (da qualche altro processo), finche questa non viene rilasciata. Un oggetto del genere funziona come un semaforo che disciplina l’accesso ad un incrocio, con la differenza che non scatta a verde automaticamente, ma quando l’automobilista (il processo) ha liberato l’incrocio, mentre chi usa l’incrocio trovato libero, pone il semaforo a rosso (per i futuri utenti dell’incrocio che dovessero arrivare quando questi è ancora occupato).

L’implementazione di un semaforo quindi appare abbastanza semplice e deve fornire almeno due primitive.

  1. Semaforo.P() che viene chiamata da un processo prima della propria sezione critica. Pone il semaforo a rosso se la risorsa è libera (per garantire che nessun altro possa progredire nello stesso momento per entrare sua sezione critica), o se è occupata (quindi il semaforo era già rosso) mette in attesa il processo chiamante, magari bloccandolo in uno spinlock (un while( condizione ) ; ) oppure in modi più eleganti descritti in seguito.
  2. Semaforo.V() che viene chiamata da un processo per comunicare di aver liberato la risorsa o più genericamente di essere uscito dalla propria sezione critica, permettendo a chi era bloccato di progredire.

I semafori implementati con uno spinlock hanno pregi e difetti:

1.      Se i processi che usano tali semafori hanno una sezione critica che dura molto tempo (molto di più del time slice dello scheduler) si manifestano i seguenti difetti: sprecano prezioso tempo di CPU, perché quando assegnati alla CPU altro non fanno che eseguire l’istruzione nulla che segue il while. Inoltre vengono schedulati perché il loro stato quando eseguono il while e running e quindi allo scadere del quanto di tempo vengono messi nella ready queue con conseguente context switch.

1.      Se invece i processi hanno una sezione critica che può essere eseguita brevemente: hanno il pregio di evitare un context switch che verrebbe invece causato se il semaforo fosse implementato senza la tecnica dello spinlock ma con il meccanismo di wait e notify ( che funziona come una signal ) come descritto sotto.

Un semaforo infatti può inserire nella primitiva P, al posto dello spinlock ( ), una chiamata a system call del S.O. che sospende il processo dallo stato di running e lo inserisce in una coda d’attesa associata al semaforo, in questo caso un processo non è bloccato in uno spinlock e quindi non spreca tempo di CPU, inoltre non trovandosi più nella ready queue non sarà schedulato per tutto il tempo che il processo che sta eseguendo la sua sezione critica non eseguirà l’exit section.

Ovviamente se la durata della sezione critica è breve, conviene di più uno spinlock.

Il processo che è stato inserito nella coda d’attesa del semaforo può uscirne a seguito di una chiamata della primitiva V, che viene in questo caso, implementata con una chiamata ad una system call che sblocca il processo.

Quindi un semaforo del genere deve avere una coda di processi in attesa. Tale coda però può essere rappresentata anche da un valore intero che riporta (se <0) solo il numero dei processi in attesa, ma non fornisce, come è ovvio, informazioni sull’ordine di risveglio. Questa è l’implementazione del semaforo usato nell’esempio del buffer sincronizzato, che è stato molto facile da realizzare perché il linguaggio con cui è stato scritto ci fornisce le primitive wait e notify che verranno spiegate in dettaglio nel paragrafo dei monitor.

Problemi tipici di sincronizzazioni che possono essere risolti con l’uso di un semaforo per sincronizzare processi cooperanti sono: il buffer limitato e il problema dei filosofi.

Regioni critiche

Questi semafori sembra abbiano risolto il problema della sezione critica, ma se non usati dal programmatore in modo attento introducono un altro problema che può essere confinato in un blocco di codice chiamato regione critica.

Una regione critica è la chiamata di un metodo del semaforo, ed critica perché un programmatore potrebbe chiamare la Semaforo.P() prima di una sezione critica e non chiamare la Semaforo.V() all’uscita, causando un deadlock, o potrebbe effettuare altri tipi di combinazioni di chiamate non corrette. Quindi in queste regioni di codice è opportuno fare attenzione.

Monitor

Un monitor è un costrutto di sincronizzazione di alto livello. Ovvero fornisce metodi d’accesso pubblici (che possono essere usati dai processi concorrenti) per accedere a dati privati (locali del monitor) sui quali si applica la sincronizzazione e ai quali solo i metodi del monitor possono accedere.

Un monitor quindi è composto da del codice d’inizializzazione che setta le sue vbl private quando un oggetto di tipo monitor viene allocato, da un’insieme di metodi o funzioni che manipolano i dati o consentono agli utenti del monitor (i processi) di accedervi, dalle variabili condivise dai processi, una lista di processi che fanno richiesta di entrare nel monitor.

Di questi processi uno solo avrà il permesso di usare i metodi del monitor per accedere alle variabili condivise, questo garantisce la mutua esclusione.

Le variabili condivise, inoltre, non sono tipi primitivi, ma oggetti di tipo condition che oltre al loro valore hanno una lista d’attesa nella quale vengono inseriti i processi che vogliono accedere a tale valore, e dei metodi che garantiscono che un solo processo per volta, fra tutti quelli inseriti nella coda d’attesa della vbl condition, possa operare su di essa, usando sempre però i metodi del monitor. Uno solo di essi quindi potrà farlo in un dato istante. Graficamente si può rappresentare un monitor come nella figura seguente.

Fig. 2

Su una variabile x di tipo condition, il processo che è riuscito ad entrare nel monitor, può effettuare queste due chiamate: x.wait o x.signal. Queste chiamate sembrano simili a quelle di un semaforo, ma in realtà sono diverse nell’implementazione e quindi negli effetti.

Chi chiama la x.wait (un processo o un thread), rimane sospeso nella coda d’attesa finchè un altro processo non chiama la x.signal, che risveglia un processo tra quelli nella coda. Se però viene chiamata un x.signal quando non c’è nessun processo nella coda d’attesa, questa chiamata non ha alcun effetto ed è come se non fosse mai stata chiamata, in un semaforo invece la signal che sarebbe la Semaforo.V incrementa il valore della vbl value del semaforo.

Un vantaggio dei semafori è che sollevano il programmatore dallo stare attento ai problemi derivanti dalle regioni critiche quando si usano oggetti come i semafori.

Tuttavia anche un monitor può essere usato male dal programmatore e introdurre problemi simili a quelli delle regioni critiche.

Sincronizzazione in java

Linguaggi di programmazione ad alto livello ed O.O. come il java adottano dei meccanismi nativi di sincronizzazione, che se non identici ad un monitor, vi si ispirano fortemente.

In java, infatti, è possibile usare una sincronizzazione su un oggetto usando metodi synchronized, istruzioni synchronized, e primitive che consentono ai thread che operano concorrentemente di comunicare per sincronizzarsi, cioè la wait e la  notify.

Prima di vedere in dettaglio l’uso di questi metodi è opportuno descrivere il modello di monitor che usa java.

Ad ogni oggetto di java, sia esso fornito dal linguaggio (String, Integre, ecc) o cerato da noi, viene associato un monitor. Tale monitor non supporta la definizione di più variabili condition, ma esiste solo una variabile condition che può ricevere e rilasciare il lock usando istruzioni o metodi synchronized. Sebbene questa scelta sembri limitante, la sua forza stà sulla semplicità.

Se due o più thread vogliono condividere un variabile ma, si vuol evitare che il loro lavoro concorrente produca risultati incoerenti o inconsistenti si possono dichiarare i metodi d’accesso o di modifica della variabile condivisasynchronized.

Se un thread a questo punto invoca un metodo synchronized su un oggetto, questi viene bloccato, cioè riceve un lock. Se un altro thread invoca un metodo synchronized sullo stesso oggetto, entrerà nella coda d’attesa dell’oggetto, restando cioè bloccato, finché il lock non verrà rimosso.

Un esempio di metodo synchronized è:

synchronized void metodo( … ){

            istruzioni

}

Si può ottenere lo stesso effetto usando le istruzioni synchronized che assegnano il lock ad un oggetto senza pero chiamare un metodo synchronized, per esempio:

public void metodo( … ){

            synchronized( espressione ){

                        istruzioni

}

}

Questi meccanismi non sono però sufficienti a garantire la mutua esclusione in tutti i casi, ecco perché vanno usati in combinazione con i metodi wait e notify che tutti gli oggetti java hanno. Tali primitive, infatti, fanno parte della classe Object, dalla quale tutti gli oggetti (pure i nostri) derivano.

Questi metodi come i lock di riferiscono a determinati oggetti. Su tali oggetti si può quindi attendere (wait) finché qualcuno non ci segnala che l’evento che attendevamo su quell’oggetto si è verificato (notify). Esiste uno standard che i thread devono rispettare nell’uso di tali metodi:

Chi vuole usare un oggetto deve priva verificare che non sia già usato, es.:

synchronized void metodo1(…){

            while( non si verifica l’evento atteso cioè è falsa condizione da verificare ) wait();

}

Chi sta usando l’oggetto e vuole comunicare a chi attende, che non lo usa più deve:

synchronized void metodo2(…){

rendi vera la condizione o fa verificare l’evento che consente all’altro thread di uscire dal wile e invoca :

notify();

}

Nota che nel metodo1 se si sostituisce il while con un if non funziona più niente.

La chiamata alla notify risveglia uno dei thread in attesa sull’oggetto, ma non si può sapere esattamente quale, se si ha la necessità di risvegliare tutti i thread in attesa si può usare a notifyAll, dopo di che, il primo thread che ottiene il lock riesce a usare l’oggetto, gli altri ritornano in attesa.

::/fulltext::

Write comment (0 Comments)
© 2018 sito prototipale studio di GiuseppeGi