Primi Concetti Di Un Sistema Operativo

Titolo: "Primi Concetti Di Un Sistema Operativo" Autore: Dir31 Rbt-4 Crew Mail: [email protected]

Ringraziamenti: Anche se potrà risultare un Paper semplice e molto riduttivo, quello che andrete a leggere è il risultato di qualche settimana di lavoro e ricerca. Vorrei ringraziare tutti i miei amici e colleghi che come sempre non fanno mancare il loro appoggio e aiuto, tutta la comunity di rbt-4 che ai miei occhi è sempre più unita e in crescita, la comunity di hacking inside, gli autori del libro da cui ho preso spunto “Operative System Concept”: Abraham Silberschatz e Peter Baer Galvin e il Web, che mi permette di avere a disposizione ogni momento materiale illimitato.

DEFINIZIONI: PROCESSO Un processo è semplicemente l' espressione di un programma in esecuzione. Se noi lanciamo un programma più volte vengono infatti prodotti più processi.

MULTITASKING I sistemi Multitasking, gestiscono l' esecuzione di più processi simultaneamente. Il cambiamento che ha portato questi ultimi a non rimanere monoprogrammati è dovuto dal fatto che lo spreco di lavoro è enorme. Un esempio potrebbe essere quello di un programma che gestisce I/O... Utilizzando un sistema monoprogrammato è facile immaginare lo spreco di cpu che si andrebbe a creare, poichè nel tempo che trascorre nell' esecuzione di un input da parte dell' utente il sistema rimane in attesa solo per quella applicazione, invece di utilizzare quel momento di attesa per altre attività. La soluzione a questo problema

è stato proprio lo sviluppo di sistemi multiprogrammati; che consentono appunto di eseguire più processi simultaneamente. Ora, il nostro compito sarà quello di capire come questi processi vengano messi a disposizione della cpu.

TIME SHARING I sistemi time sharing, prevedono più o meno lo stesso lavoro dei multitasking, con la differenza che avranno diversi algoritmi di sheduling (come vedremo fra poco), che basano la loro attività sul tempo. Difatti letteralmente la parola Time Sharing si traduce in condivisione di tempo. Per fare un esempio, il nostro amato (xD) Windows è time sharing.

I PROCESSI DI SISTEMA Analizziamo i diversi stati in cui ogni processo può trovarsi: -Running: quando occupa la cpu per la sua attività -Ready: se è in attesa della cpu, occupata da un altro processo -Waiting: se è in attesa di un dispositivo I/O -Parking: se è momentaneamente inattivo ed è stato caricato su memoria di massa Un solo processo può trovarsi in running, mentre tutti gli altri si trovano in ready. In questo stato questi ultimi hanno tutte le risorse necessarie per essere eseguiti, tranne la cpu, ed è il kernel che decide quale processo caricare. Lo sheduling definisce proprio quale processo e per quanto tempo deve passare da ready a running. Se un processo rimane inattivo per tanto tempo, viene liberata la sua porzione di memora nella ram e viene parcheggiato su memoria di massa (definizione: swapping). Vediamo ora come un SO identifica un processo: essenzialmente non ci sono passaggi,ma tutte le informazioni vengono registrate in un record chiamato PCB (process control block).

I campi di un PCB sono: -Nome (ID) -Priorità -stato -Un puntatore per poterlo connettere ad altri PCB -Counter (per conoscere l' indirizzo della prossima istruzione da eseguire)

PARTE STATICA E DINAMICA Un processo si compone di una parte statica, quali nome, codice e dati, e una parte dinamica come stato, priorità e diritti di accesso ad altre informazioni, che variano a seconda della situazione.

PROCESS TREE Alla base di ogni programma o sistema operativo che debba sfruttare il multitasking c'è la gestione dei processi. Su questi sistemi è la funzione fork() addetta alla creazione e alla gestione dei processi. La sintassi è questa: #include <sys/types.h> #include pid_t fork(void) /* Creazione del processo*/

Una volta che il processo è stato creato, si ha un processo figlio che è la copia del padre e ne esegue lo stesso codice. Il processo padre può: 1 -Continuare il suo lavoro contemporaneamente al suo processo figlio; 2 -Aspettare fino a che il lavoro del processo figlio sia finito;

Il processo figio inoltre ha un indirizzo di memoria che punta al processo padre, affinchè i 2 possano cominicare velocemente.

IPC (INTERPROCESS COMUNICATION) Una delle tante vie, anzi il miglior servizio, che permette ad ogni processo di comunicare con un altro è l' IPC ovvero l' interprocess comunication. L' IPC è un meccanismo che permette ai processi di comunicare e sincronizzare il loro lavoro. La funzione principale che rende l' IPC un ottimo mezzo di comunicazione è che consente a 2 processi di scambiare messaggi senza che questi ultimi abbiano bisogno di condividere o resettare le loro variabili. I Messaggi da inviare possono avere una dimensione sia fissa sia variabile. Comunque sia, due processi per comunicare devono pur sempre avere un collegamento di comunicazione fra loro, questo può avvenire diversi modi: 1) Comunicazione diretta o indiretta; 2) Comunicazione simmetrica o asimmetrica; O può essere implementato attraverso: -buffering automatico o esplicito; -l' invio di copie o riferimenti del messaggio;

I processi che vogliono comunicare fra loro attraverso un riferimento (che sia il nome, o un tipo di porta) utilizzeranno il primo punto. Nel caso di un collegamento diretto i due processi si scambieranno messaggi utilizzando il proprio nome. send(P,text) Invia text al processo P.

receive(Q,text) Riceve text inviato dal processo Q. In questo tipo di collegamento possiamo anche inserire le comunicazioni simmetriche e asimmetriche. Nel primo caso sia il processo che invia, sia quello che riceve vengono identificati fra loro (come nelle 2 funzioni in alto); Nel secondo caso solo il processo che invia conosce il nome del destinatario, mentre quest ultimo è abilitato a ricevere messaggi da qualsiasi processo generico. send(P,text) invia text al processo P receive(n,text) riceve text da qualsiasi prcesso, dove n prende il nome del processo con cui si è in comunicazione.

Nel caso di un collegamento indiretto, i messaggi vengono inviati e ricevuti tramite una mail box (o detta anche porta). Con questo metodo i processi possono comunicare fra loro in questo modo: send(A,text) Viene inviato un file ad A (dove A è il nome della mailbox) receive(A,text) Viene caricato un file da A (dove A è la mailbox) Con questo meccanismo possono comunicare fra loro più processi poiche la mailbox funge da contenitore e qualunque processo che ne ha bisogno può prelevare o inviare messaggi collegandosi ad essa. Ci sarebbe da dire altro su questo tipo di collegamento, come per esempio parlare della differenza tra una mailbox di proprietà del

processo e una di proprietà del sistema, ma per non dilungare troppo mi fermo a queste informazioni essenziali (come per tutto il paper d' altronde). Per quanto riguarda il buffering, dobbiamo parlare di code. Un collegamento ha alcune capacità di determinare il numero dei messaggi che possano risiedere temporaneamente in esso. Questa proprietà può essere vista come una coda e ci sono tre modi di implementazione: 1)CAPACITA' ZERO: questo vuol dire che la coda ha una lunghezza massima nulla. Quindi le azioni dovranno essere svolte una alla volta (il processo che invia un messaggio dovrà aspettare la ricezione prima di compiere una nuova attività). 2)CAPACITA' VINCOLATA: qui la coda ha una capacita finita, questo vuol dire che finchè ci sarà spazio una volta inviato un messaggio, non ci sarà nessuna attesa. Al contrario una volta che la coda si sarà riempita si dovrà eliminare il processo che invia fino a che non ci sarà spazio sufficente. 3)CAPACITA' SVINCOLATA: la coda ha potenzialmente spazio infinito.

SHEDULING DI SISTEMA Lo sheduling della cpu è una delle parti fondamentali di un sistema operativo. Il concetto base è molto semplice: cercare di sfruttare al massimo il processore, rendendo il tempo produttivo; quindi ogni qual volta un processo in esecuzione non richiede più cpu, verrà sostituito con un altro in attesa. Quello che andremo a vedere è come avviene questo sistema e con quali metodi. Esistono diversi algoritmi di sheduling e ognuno ha delle caratteristiche proprie che possono favorire un gruppo di processi piuttosto che altri. Per capire quali algoritmi utilizzare bisogna analizzare le varie proprietà. In questa fase di analisi vengono presi in considerazione dei criteri che serviranno per determinare il miglior

algoritmo in base alle nostre esigenze. I criteri sopra citati sono i seguenti: -Utilizzo della cpu: vogliamo che la cpu sia utilizzata il più possibile; -Troughput: Misura del lavoro della cpu che si basa sul numero di processi che hanno completato la loro esecuzione in un range di tempo (chiamato appunto throughput); -Turnaround time: Ovvero il tempo di completamento dell' esecuzione di un processo (ovvero la somma del tempo speso aspettando che un processo venga caricato in memoria,attenda nella coda di ready, venga sottoposto all' utilizzo della cpu e svolga funzioni di I/O); -Waiting time: il tempo di attesa di un processo nella coda di ready; -Response time: questo criterio è un po più efficente del turnaround time, viene preso in considerazione nei sistemi con alto livello di interattività, dove l' output viene prodotto velocemente. Il Response Time è il tempo che varia dalla presentazione di una richiesta alla prima risposta prodotta (senza tener conto del tempo dell' invio all' output).

ALGORITMI DI SCHEDULING FCFS (first come first served) Il compito di questo algoritmo è eseguire i processi in base all' ordine della richiesta, cioè chi chiede per primo l' utilizzo della cpu viene servito. Il problema è che se un processo richiede un lungo utilizzo di cpu, altri processi che invece potrebbero essere serviti in meno tempo dovranno attendere inutilmente. Consideriamo tre processi: P1, P2, P3 P1= 100 ms (millisecondi); P2=5 ms; P3=5ms; E' evidente subito come il processo P1 servito per prima presenti un

tempo di esecuzione piuttosto lungo in confronto ai processi P2 e P3. Il risultato quindi non è ottimale. Questo tipo di algoritmo è particolarmente fastidioso per gli OS basati su time-sharing, dove ogni processo riceve un porzione di CPU ad intervalli regolari.

SJF (Shortest job first) Questo algoritmo serve per primo il processo che richiede meno tempo di utilizzo di cpu, quindi prevede un continuo ordinamento della coda di ready. Il PCB quindi ordinerà qsti ultimi attraverso un insertion sort che li catalogherà in base ad una stima di tempo di utilizzo. Anche qui però lo svantaggio sarà che i processi con un termine più lungo dovranno aspettare che ogni processo che utilizzerà meno termine sarà eseguito. Consideriamo sempre il caso di tre processi, inserendo tra le parentesi tonde il tempo di utilizzo in millisecondi: P1(10ms), P2(2ms), P3(20ms). Il processo P1 che si trova nella coda di ready in una prima fase da solo, viene eseguito. All' arrivo nella coda del processo P2, con un tempo di attesa largamente inferiore di P1, viene controllato il tempo che rimane a P1 per concludere il lavoro. Se questo risulterà ancora maggiore del tempo di P2 verrà effettutato uno scambio fra i 2 processi e P2 verrà eseguito.Per quanto riguarda P3, al suo arrivo la coda di ready non dovrà essere ordinata, poichè il suo tempo di utilizzo è il maggiore fra tutti. Una volta capito il concetto potrebbe sorgere spontanea una domanda: Come fa a capire l' OS il tempo di utilizzo che richiede un processo? Bhe è qui che si riscontra un altro problema di questo algoritmo. Questa porzione di tempo viene calcolata approssimatamente dai sistemisti in base a diversi criteri. Il risultato anche se preciso, non sarà mai perfetto e si potrebbe incappare in qualche errore (dopo

tutto errare è umano), con risultati non molto gradevoli. Appunto: Quando due processi hanno lo stesso troughput, si prendera in considerazione la soluzione FCFS.

PRIORITY SHEDULING I' algoritmo SJF è un caso speciale del più generale algoritmo a priorità. Ad ogni processo viene associata una proprità e lo sheduling propone alla cpu quello con priorità maggiore. Nel caso ci siano processi con la stessa priorità si utilizzerà l' algoritmo FCFS. Considerando come processi più importanti quelli con valore di priorità più bassa, definiamo P1(priorità 4), P2 (priorità 3), P3 (priorità 1) posizionati nella coda di ready. P1 viene eseguito, ma all' arrivo di P2 viene controllatà la priorità. Verificato che P2 ha una priorità maggiore viene passato alla CPU. Stessa situazione si creerà con l' arrivo di P1 che verrà scambiato a sua volta con P2. La priorità di un processo può essere fornita a quest ultimo internamente o esternamente. Nel primo caso è l' OS che ne controlla le varie caratteristiche prendendo in considerazione valori come tempo limite, memoria occupata, numero di file aperti o quantità di cpu richiesta e fornendo quindi al processo una priorità. Nel secondo caso questo lavoro viene fatto dall' esterno da parte, per esempio, di un sistemista che prenderà in considerazione altre variabili come importanza, tipo o anche fattori politici. Il principale problema di questo algoritmo è che i processi con una bassa priorità avranno un indefinito tempo di attesa nella coda di ready e potrebbero mai essere eseguiti, causando errori irreversibili. Una soluzione ai problemi c'è sempre, ed in questo caso la soluzione è l' AGING (affinamento) che consiste nell' incrementare la priorità di un processo ad ogni intervallo di tempo prestabilito. ROUND ROBIN SHEDULING Questo tipo di algoritmo è disegnato specialmente per sistemi a timesharing. La struttura è molto semplice: viene definita un' unità di tempo (time quantum), generalmente compreso fra 10 e 100 millisecondi, e lo sheduling avviene come un FCFS, fornendo però ai

processi la CPU necessaria solo in quel frangente di tempo, per poi passare al processo successivo alla coda di ready. Bisogna immaginarlo come un sistema circolare dove la CPU viene fornita a tempi prestabiliti. Esaminiamo il seguente esempio, creiamo tre processi presenti nell' ordine nella coda di ready, inserendo tra parentesi la quantità di tempo che servirebbe loro per essere eseguiti (in millisecondi): P1(37 ms), P2(15 ms), P3(8 ms). Se consideriamo il time quntum di 10 ms, notiamo subito che per i primi due processi servirà più di un ciclo per essere eseguiti, mentre l' ultimo processo verrà eseguito nell' arco di tempo prestabilito. Le prestazioni di questo algoritmo comunque dipendono dal timequantum, tutto gira su questa frazione di tempo: se il time-quantum sarà molto grande l' algoritmo assomiglierà molto ad un FCFS, mentre se sarà molto piccolo verrà chiamato Processor Sharing, e apparirà all' utente come se ogni processo avesse un proprio processore, poichè si creeranno rapidi cicli di esecuzione. MULTILEVEL FEEDBACK QUEUE SHEDULING In un Multilevel Queue sheduling normalmente ad ogni processo viene assegnata in modo permanente una coda di ready. Ciò lascia intendere che in questo algoritmo esistono diverse code e i processi inseriti in queste ultime non possono spostarsi da una all' altra. Nel caso però del Multilevel Feedback Queue Sheduling viene permesso ai processi questo spostamento. Anche qui il concetto è molto semplice: vengono create diverse code, ordinate, per esempio, in base al time quantum che i processi devono supportare al loro interno (Come verrà detto fra poche righe,però, ogni coda può avere il suo algoritmo di sheduling). La coda di ready che avrà il time quantum più breve verrà eseguita per prima. Una volta che tutti i singoli processi verranno eseguiti dalla CPU, si passerà alla coda successiva. Per quanto riguarda lo spostamento, i processi arrivano in modo automatico alla coda con maggiore priorità (in questo esempio quella con il time quantum più breve) e da qui vengono controllati e smistati.

Ecco l' esempio: CPU P1(13 ms) --------------------------------------> Coda1 (time quantum: 8ms) Coda2 (time quantum: 16ms) Coda3(time quantum: 24ms)

Il processo P1 arriverà alla Coda1 e verrà eseguito, ma avendo un time quantum maggiore dello standard passerà a quella successiva. E così sarà per tutte gli altri processi e le altre code. Generalmente un Multilevel Feedback Queue Sheduler è definito in base a questi parametri: 1) Il numero di code; 2)L' algoritmo di sheduling per ogni coda; 3)Il metodo usato per determinare come un processo possa essere spostato in una coda a maggiore priorità; 4)Il metodo usato per determinare come un processo possa essere spostato in una coda con priorità minore; 5)Il metodo per determinare la coda nella quale un processo entrerà quando avrà bisogno di CPU; In conclusione possiamo definirlo come il più generale tra gli algoritmi, poichè permette di definire molte caratteristiche e sfumature. Proprio per questo però, è anche il più complesso, perchè necessita di moltissime variabili che hanno bisogno di essere gestite per renderlo il più efficente.

ANNOTAZIONE SULLO SHEDULING Fin' ora abbiamo parlato di sheduling su sitemi con un solo processore, ma nel caso ci fossero più CPU, la situazione si

complica un po, sinceramente per non dilungarmi troppo ho preferito lasciare questo argomento alla vostra pura curiosità.

SINCRONIZZAZIONE DEI PROCESSI Quando due processi si trovano a condividere la stessa risorsa (un dato), si potrebbero generare degli errori nell' utilizzo di quest' ultima. Quindi bisogna cercare delle soluzioni che rendano questa condivisione possibile. Prima di tutto bisogna spiegare cos'è la "Sezione Critica". Semplicemente è quella sezione dove il processo è in fase di scrittura, e quindi di modifica. In questa fase nessun altro processo può accedere alla risorsa poichè si genererebbero diversi errori, insieme a dati completamente sballati. Lo scopo di questo piccolo riferimento alla sincronizzazione, sarà quello di capire quali siano i metodi per ovviare al problema della Sezione Critica. L' argomento è immenso, ma causa le mie scarse conoscenze e la lunghezza del paper mi fermerò solo a queste basilari informazioni. Solitamente per evitare errori nella sezione critica vengono dati dei permessi ai vari processi che consentono di accedervi. Gli algoritmi che gestiscono tutto ciò devono soddisfare tre criteri fondamentali: 1)Mutua Esclusione, cioè se un processo è nella sezione critica, nessun altro può accedervi; 2)Solo i processi che sono nella sezione critica, ovvero nella "remainder section" (sezione restante), possono decidere quale sarà il prossimo processo a potervi accedere; 3)Attesa limitata. Un processo può essere bloccato e sostituito con un altro processo nella sezione critica solo per un certo numero di volte. Soluzioni per l' Accesso alla Sezione Critica :

1) Viene creato un array di boleani che funge da indice dei processi e un intero che sceglie a quale processo permettere l' accesso. Questo metodo garantisce che solo un processo alla volta abbia i permessi per entrare nella sezione critica. Una volta che il processo finisce il suo lavoro la sua flag viene impostata su false, così da permettere all' indice di aggiornarsi e all' intero di selezionare un nuovo processo. Nel caso voglia continuare il suo lavoro la sua flag verrà impostata su true, ma per garantire l' attesa limitata verrà registrato che il processo che sarebbe dovuto entrare è stato bloccato.

2) Viene creato un lucchetto hardware che la CPU assegna al processo che deve usufruire della sezione critica, cosicchè nessun altro processo abbia la possibilità di accedervi. 3)I Semafori: Un semaforo contiene all' interno due funzioni wait() e signal() Il numero contenuto nel semaforo rappresenta il numero di risorse disponibili ad un processo (task), qll più utilizzato è il semaforo binario, che può avere due valori: 1 e 0. Il suo lavoro può essere modificato tramite le due chiamate a sistema (accennate prima) wait() e signal(). Le fasi di lavoro sono però tre: -Inizializzazione: il semaforo riceve un valore, quindi si dichiarano quante unità di un tipo di risorsa sono disponibili. -Operazione wait(): Il semaforo qui viene decrementato. Se il suo valore diventa negativo, il processo viene sospeso e messo in coda. -Operazione Signal(): Il semaforo viene incrementato. Se c’è un task in coda, viene preso e inserito nella coda di ready pronto per accedere alla sezione critica. PROBLEMA RIGUARDANTE LA SINCRONIZZAZIONE: LE DEADLOCK Le Deadlock sono situazioni in cui due task si bloccano a vicenda

aspettando che uno esegua una certa azione. Per evitare questa situazione di stallo, un sistema dovrebbe esser stato programmato in modo ottimale (ovvero sicuro), allocando i processi in modo tale che fornendo ad ognuno tutte le risorse che questo possa richiedere, gli si permetta di terminare la propria esecuzione. In parole più semplici, ad ogni richiesta l’ OS dovrebbe controllare lo stato della risorsa in questione e se risulta sicura viene fornita. Il problema è che non è sempre possibile sapere le risorse che un task andrà a chiedere e quindi non si è mai al riparo da una deadlock. In questo caso (ovvero quando non è possibile evitare questo problema) si ricorre a degli algoritmi che riconoscano e risolvino le deadlock (Es. l’ algoritmo del banchiere).

Conclusioni: Queste penso siano le basi per capire com'è strutturato un Sistema Operativo, chissà se non mi cimenterò in una seconda parte. Per adesso va bene così. Per critiche o insulti non esitate a contattarmi :D. Saluti Dir31.