Sistemi Operativi

Algoritmi di scheduling e tempi di attesa

P P P1 2 3

NB: Burst Time: Tempo richiesto da un processo per completare la sua esecuzione.

Tempi di attesa: P = 0, P = 24, P = 27.

Tempo di attesa medio: ( 0 + 24 + 27 ) / 3 = 27

Effetto convoglio: i processi I/O-bound si accodano dietro un processo CPU-bound.

SJF: Shortest-Job-First: Associa ad ogni processo la lunghezza del suo prossimo burst di CPU. I processi vengono schedulati in ordine di tempi crescenti. L'algoritmo SJF risulta essere quello ottimale perché fornisce il minimo tempo di attesa per un dato insieme di processi. È un algoritmo di scheduling a priorità, dove la priorità è il prossimo tempo di burst. C'è il rischio di starvation, i processi con burst-time lungo potrebbero essere rimandati all'infinito.

Problema: Non potendo conoscere il tempo per il quale il job occuperà la CPU, il sistema operativo utilizzerà i dati delle precedenti elaborazioni per fare delle stime sulla durata del prossimo burst.

Un algoritmo con prelazione, specifico dei sistemi time-sharing. Molto simile al FCFS ma con prelazione quantizzata. Ogni processo riceve una piccola unità di tempo di CPU (detto quanto: 10-100ms). Dopo questo periodo, il processo viene prelazionato e rimesso in coda ready. Se ci sono n processi in coda ready, e il quanto è q, allora ogni processo riceve 1/n del tempo di CPU in periodi di durata massima q. Si ha che nessun processo attende più di (n-1) q. Tipicamente con schedulazione round robin si ha un tempo di turnaround medio maggiore, ma minore il tempo di risposta e maggiore l'overhead dovuto ai numerosi cambi di contesto.

Esempio RR con quanto = 20

Considerazioni: con un quanto grande, degenera nell'FCFS, con un q troppo piccolo, si avrebbero troppi context switch, aumentando così l'overhead della CPU. Con algoritmo di scheduling Round Robin un eventuale processo impegnato in un'attesa attiva viene comunque prelazionato alla fine del suo quanto.

In questo modo non è possibile che monopolizzi la CPU. Se invece l'algoritmo di scheduling è basato su priorità, allora è possibile (in assenza di meccanismi di aging o trasferimento di priorità) che ciò avvenga se il processo che lo esegue ha una priorità (lo spin-lock, attesa attiva) sufficientemente alta da non venire mai prelazionato e, per esempio, se l'evento atteso può essere generato soltanto da un processo a bassa priorità (che non verrà quindi mai eseguito), causerà un deadlock.

RMS: Rate Monotic Scheduling: È un algoritmo di schedulazione con priorità tipicamente utilizzato in ambito real-time. RMS assegna a ciascun processo una priorità prefissata uguale alla frequenza con cui deve essere eseguito. Durante l'esecuzione lo scheduler esegue sempre il processo pronto a più alta priorità, prelazionando, se necessario, l'attuale processo in

esecuzione.EDF: Earliest DeadLine First: In questo algoritmo, il sistema operativo mantiene una lista dei processi eseguibili rispetto alla loro scadenza temporale (ogni processo annuncia la sua presenza allo scheduler specificando la loro scadenza temporale). L'algoritmo esegue il primo processo della lista, cioè quello con scadenza temporale più vicina. Quando un nuovo processo è pronto, il sistema controlla se la sua scadenza preceda quella del processo correntemente in esecuzione, in caso positivo quello in esecuzione viene prelazionato. A differenza di RMS è adatto a priorità dinamiche (in base a chi scade prima) ed è adatto anche per processi non periodici. Permette di raggiungere anche il 100% di utilizzo cpu.

23Andrea Mansi - UNIUD - Riassunto Teoria Sistemi Operativi

Accenni di scheduling nei sistemi operativi odierni:

Scheduling in UNIX tradizionale: A code multiple, con approccio Round Robin. Numeri più grandi indicano priorità minore.

più basse corrispondono quanti più lunghi (a differenza di Unix e Windows).Ogni CPU mantiene una coda di esecuzione con due liste di task: attivi e scaduti. Un task è attivo se non ha terminatoil suo quanto, altrimenti è scaduto. Le due liste sono ordinate secondo la priorità dei task. Quando l’array attivo sisvuota i due array si scambiano di ruolo.

Scheduling in Windows: Un thread esegue lo scheduler quando viene eseguita una chiamata bloccante, si comunicacon un oggetto e alla schadenza del quanto di thread. Inoltre lo scheduler si esegue in modo asincrono alcompletamento di un I/O e allo scadere di un timer. Lo scheduler sceglie sempre il thread a priorità maggiore, ovveroandando a guardare nella coda di priorià di maggiore priorità.

Andrea Mansi - UNIUD - Riassunto Teoria Sistemi Operativi

6. Cooperazione tra Processi

Si parla di cooperazione tra processi quando due o più processi possono modificare o essere

modificati tra di loro. In questo caso i processi vengono detti cooperanti, altrimenti, vengono chiamati indipendenti, cioè che non possono essere modificati o modificare l'esecuzione di altri processi.

I principali vantaggi della cooperazione tra processi sono:

• La condivisione delle informazioni
• L'aumento della computazione: parallelismo
• Maggiore modularità
• Praticità implementativa e di utilizzo

Perché dei processi cooperino, è necessario che essi possano comunicare. In inglese, la comunicazione tra processi viene detta inter-process communication (IPC) e si riferisce a tutte quelle tecnologie software che consentono, appunto, a diversi processi (o thread) di comunicare, scambiandosi dati e informazioni tra di loro.

Quando si parla di comunicazione tra processi è importante considerare le seguenti problematiche:

• Come può un processo comunicare con altri processi?
• Come si può evitare

• Come sequenzializzare gli accessi alle risorse?

• memoria condivisa: i processi che vogliono scambiare dei dati li (utilizzabile se i processi risiedono nello stesso sistema) scrivono e leggono in un'area di memoria allocata e destinata a questo scopo per mezzo di normali operazioni di lettura/scrittura della memoria.
• scambio di messaggi (più generale in quanto applicabile anche fra processi che risiedono su sistemi distinti, ovvero, in sistemi: permette a due o più processi di scambiare dei dati su un canale distribuito connessi da un canale di comunicazione) (realizzato solitamente mediante delle socket) attraverso due primitive, ovvero, send() e receive().

Si considerino due processi detti "produttore" e "consumatore". Il produttore produce delle informazioni che vengono utilizzate dal processo consumatore. Soluzione immediata: tra i due processi si pone un buffer di comunicazione di dimensione fissata, utilizzato per scambiare i dati, un processo scrive da un lato, e l'altro legge dall'altro.

Alcuni fenomeni e concetti legati alla cooperazione tra processi:

• Race condition (corsa critica): Le race conditions sono quel fenomeno in cui più processi accedono concorrentemente agli stessi dati, e il risultato dipende dall'ordine di interleaving dei processi. Questo fenomeno è molto frequente nei sistemi operativi multitasking, sia per dati in user che in kernel space. Il verificarsi di questa situazione risulta essere di estremo pericolo perché può portare al malfunzionamento dei processi cooperanti, o addirittura dell'intero sistema se riguardano

dati sensibili in kernel space. Sono situazioni difficili da individuare eda riprodurre perché non dipendono tanto dai dati ma da informazioni astratte quali le decisioni prese dalloscheduler, dal carico del sistema, dal numero e dallo stato dei processi, dall’utilizzo della memoria etc. etc. 25Andrea Mansi - UNIUD - Riassunto Teoria Sistemi Operativi

Problema della sezione critica: Quando sono presenti n processi checompetono per utilizzare dei dati condivisi (race condition), viene dettasezione critica quel segmento di codice in cui essi accedono a questidati. Per evitare il verificarsi di race condition, serve assicurare chequando un processo esegue la sua sezione critica, nessun altroprocesso possa entrare nella propria (ovvero mentre un processo lavorasui dati condivisi, deve essere l’unico a poterlo fare). Si noti che se loscheduling della CPU è senza prelazione, le corse critiche non si possono Dopo che il processo P passa la suaverificare in quanto

Il processo correntemente in esecuzione non può entry section, nessun altro deve poterlo.