Concorrenza e Scheduling nei Sistemi Operativi: Ottimizzazione e Soluzioni

Concorrenza nei Sistemi Operativi

Definizione di Applicazione Concorrente

Un'applicazione concorrente è un'applicazione strutturata in modo tale che diverse parti del codice possano essere eseguite contemporaneamente. Un esempio è un sistema di elaborazione transazionale in cui più richieste vengono elaborate in parallelo.

Mutua Esclusione

La mutua esclusione è un meccanismo che impedisce a due o più processi di accedere contemporaneamente alla stessa risorsa condivisa. Viene implementata per garantire l'integrità dei dati e prevenire condizioni di competizione.

Disabilitazione degli Interrupt e Mutua Esclusione

Disabilitare gli interrupt è una soluzione semplice per implementare la mutua esclusione, ma presenta delle limitazioni significative. La multiprogrammazione può essere seriamente compromessa, in quanto la concorrenza tra i processi si basa sull'uso degli interrupt. Inoltre, questa soluzione non è adatta a sistemi multiprocessore.

Busy Waiting (Attesa Attiva)

Il busy waiting (attesa attiva) si verifica quando un processo, non potendo entrare nella sua sezione critica perché un altro processo sta accedendo alla risorsa, rimane in un ciclo continuo a testare una condizione, fino a quando non gli viene consentito l'accesso. Il problema principale è lo spreco di cicli CPU.

Semafori

Un semaforo è una variabile intera non negativa che può essere manipolata solo da due operazioni atomiche: wait (o down) e signal (o up). I semafori possono essere utilizzati per implementare sia la mutua esclusione (semafori binari) che la sincronizzazione condizionale (semafori contatori).

• Esempio di Mutua Esclusione: Un semaforo binario inizializzato a 1 può essere utilizzato per proteggere l'accesso a una risorsa condivisa.
• Esempio di Sincronizzazione Condizionale: Un semaforo contatore inizializzato a 0 può essere utilizzato per sincronizzare un produttore e un consumatore, dove il consumatore attende che il produttore produca un elemento.

Monitor

I monitor sono meccanismi di sincronizzazione di alto livello che semplificano lo sviluppo di applicazioni concorrenti. Offrono una struttura più organizzata rispetto ai semafori, incapsulando le variabili condivise e le procedure di accesso all'interno di un'unica unità. Come i semafori, possono essere utilizzati sia per la mutua esclusione che per la sincronizzazione condizionale.

• Esempio Mutua Esclusione: Un monitor può contenere una variabile condivisa e metodi per accedervi in mutua esclusione.
• Esempio Sincronizzazione Condizionale: Un monitor può utilizzare variabili condizione per gestire la sincronizzazione tra processi.

Comunicazione Asincrona tra Processi

Il vantaggio della comunicazione asincrona è l'aumento dell'efficienza delle applicazioni concorrenti, in quanto i processi non devono bloccarsi in attesa che il messaggio venga ricevuto. Per implementare questa soluzione, è necessario un buffer per memorizzare i messaggi e meccanismi di sincronizzazione per identificare se un messaggio è stato inviato o ricevuto.

Deadlock (Stallo)

Il deadlock è una situazione in cui un insieme di processi è bloccato perché ogni processo detiene una risorsa e attende una risorsa detenuta da un altro processo nello stesso insieme. Le quattro condizioni necessarie per il deadlock sono:

1. Mutua esclusione: Ogni risorsa può essere assegnata a un solo processo alla volta.
2. Hold and wait (Azione di attesa): Un processo, oltre alle risorse già allocate, può essere in attesa di altre risorse.
3. Non-preemption: Una risorsa non può essere rilasciata forzatamente da un processo.
4. Attesa circolare: Esiste una catena circolare di processi in cui ogni processo attende una risorsa detenuta dal processo successivo nella catena.

Per evitare il deadlock, è necessario impedire che almeno una di queste quattro condizioni si verifichi.

Scheduling nei Sistemi Operativi

Politica di Scheduling

Una politica di scheduling definisce i criteri per determinare quale processo, tra quelli nello stato "pronto", debba essere scelto per utilizzare il processore.

Funzioni dello Scheduler e del Dispatcher

Lo scheduler è una routine del sistema operativo che implementa la politica di scheduling. Il dispatcher è responsabile del cambio di contesto dei processi, assegnando effettivamente il processore al processo selezionato dallo scheduler.

Criteri Principali di una Politica di Scheduling

I criteri principali includono:

• Utilizzo del processore
• Throughput (velocità)
• Tempo di CPU
• Tempo di attesa
• Tempo di turnaround
• Tempo di risposta

Differenze tra Tempi

• Tempo di CPU (o tempo di elaborazione): Il tempo che un processo trascorre nello stato di esecuzione.
• Tempo di attesa: Il tempo totale che un processo trascorre nella coda dei processi pronti.
• Tempo di turnaround: Il tempo totale che intercorre tra l'arrivo di un processo e il suo completamento (include tempi di attesa, tempo di CPU e tempo di I/O).
• Tempo di risposta: Il tempo che intercorre tra una richiesta al sistema e il momento in cui viene visualizzata la prima risposta.

Scheduling Preemptive e Non-Preemptive

Nello scheduling preemptive, il sistema operativo può interrompere un processo in esecuzione e spostarlo nello stato "pronto" per assegnare il processore a un altro processo. Nello scheduling non-preemptive, un processo in esecuzione mantiene il processore fino a quando non termina o passa volontariamente allo stato di attesa.

Differenza tra FIFO e Round Robin

FIFO (First-In, First-Out) è un algoritmo di scheduling non-preemptive in cui i processi vengono eseguiti nell'ordine in cui arrivano. Round Robin è un algoritmo di scheduling preemptive progettato per sistemi time-sharing. A ogni processo viene assegnato un quanto di tempo (time slice) per l'esecuzione. Se il processo non termina entro il suo quanto di tempo, viene interrotto e rimesso in coda.

Preemption per Tempo e per Priorità

La preemption per tempo si verifica quando il sistema operativo interrompe un processo in esecuzione a causa della scadenza del suo quanto di tempo. La preemption per priorità si verifica quando un processo con priorità più alta entra nello stato "pronto", interrompendo il processo in esecuzione corrente (se ha priorità inferiore).

Code Multiple con Feedback

Lo scheduling a code multiple con feedback favorisce i processi I/O-bound. I processi I/O-bound tendono a rimanere nelle code a priorità più alta perché utilizzano la CPU per brevi periodi, mentre i processi CPU-bound tendono a scendere nelle code a priorità più bassa.