Algoritmo

Algoritmi

Presentazione

Start

Algoritmo

Gli algoritmi di scheduling sono meccanismi utilizzati nei sistemi operativi per decidere l'ordine con cui i processi ottengono l'accesso alla CPU. L'obiettivo principale è ottimizzare l'uso delle risorse, garantendo equità tra i processi, riducendo i tempi di attesa e migliorando la reattività. Gli algoritmi si dividono in due categorie principali: preemptive, dove un processo in esecuzione può essere interrotto per dare priorità ad altri, e non-preemptive, dove un processo mantiene la CPU fino al completamento. Ogni algoritmo è progettato per bilanciare criteri come throughput (numero di processi completati), tempo di attesa, tempo di risposta e utilizzo della CPU, adattandosi a diverse esigenze: dai sistemi interattivi ai sistemi batch e real-time.

Confronto tra algoritmi

FCFS (First-Come, First-Served)

L’algoritmo Shortest Job First assegna la CPU al processo con il tempo di esecuzione più breve. Questo approccio, che può essere sia preemptive che non-preemptive, è considerato ottimale per ridurre il tempo medio di attesa dei processi. Tuttavia, richiede una stima accurata del tempo di esecuzione dei processi, il che non sempre è possibile nei sistemi reali. Sebbene efficace nel migliorare l’efficienza complessiva, questo algoritmo può causare il problema di starvation, dove i processi con tempi di esecuzione lunghi vengono continuamente posticipati a favore di processi più brevi. È ideale per ambienti in cui si conoscono i tempi di esecuzione, ma meno pratico per sistemi interattivi o in tempo reale.

'Your content is liked, but engages much more if it is interactive' -Genially

Priority Scheduling

Il Priority Scheduling assegna la CPU ai processi in base a una priorità predefinita, che può essere determinata da fattori come l’urgenza del processo o i requisiti di sistema. L’algoritmo può essere preemptive, interrompendo l’esecuzione di un processo quando ne arriva uno con priorità più alta, oppure non-preemptive, dove un processo in esecuzione termina prima di lasciare spazio ad altri. Questo approccio è utile per gestire processi critici, ma presenta il rischio di starvation per i processi con priorità bassa. Una soluzione a questo problema è l’aging, che aumenta gradualmente la priorità dei processi più vecchi per garantire che vengano eseguiti. È adatto a scenari dove alcune operazioni hanno bisogno di essere completate prima di altre, come nei sistemi real-time.

'Your content is liked, but engages much more if it is interactive' -Genially

Round Robin(First-Come, First-Served)

Il Round Robin è un algoritmo preemptive che assegna un tempo fisso, chiamato quantum, a ogni processo in esecuzione. I processi vengono gestiti in una coda circolare, ricevendo ciascuno un turno per utilizzare la CPU. Questo approccio garantisce equità tra i processi e una buona reattività, rendendolo ideale per i sistemi interattivi. Tuttavia, le prestazioni dipendono fortemente dalla scelta del quantum: se troppo breve, aumenta l’overhead del context switch; se troppo lungo, il comportamento tende a quello di FCFS. È un algoritmo equilibrato, che bilancia efficienza e reattività, ma può richiedere ottimizzazioni per sistemi con carichi particolarmente variabili.

'Your content is liked, but engages much more if it is interactive' -Genially

MLFQ (Multi-Level Feedback Queue)

L’algoritmo Multi-Level Feedback Queue utilizza più code con priorità diverse per gestire i processi. I processi interattivi o con I/O frequenti ricevono priorità più alta e vengono eseguiti rapidamente, mentre i processi CPU-bound vengono spostati progressivamente in code a priorità più bassa. Questo meccanismo permette di adattarsi dinamicamente al comportamento dei processi, offrendo una combinazione di efficienza per quelli brevi e equità per quelli lunghi. Nonostante i numerosi vantaggi, come la flessibilità e la capacità di bilanciare diversi tipi di carico, l’algoritmo è complesso da implementare e richiede una configurazione attenta per evitare squilibri nelle prestazioni.

'Your content is liked, but engages much more if it is interactive' -Genially

Classificazione degli Algoritmi di Scheduling

Perché Esistono Diversi Algoritmi?

Ogni algoritmo è progettato per soddisfare esigenze diverse: Sistemi Batch (es. server): Massimizzare throughput e utilizzo della CPU. Sistemi Interattivi (es. PC, smartphone): Garantire risposte rapide. Sistemi Real-Time: Rispettare scadenze rigide (es. controllo di volo).

Per confrontare le prestazioni degli algoritmi, utilizziamo alcune metriche chiave: Tempo di attesa: Somma dei tempi in cui un processo resta nella coda ready prima di ottenere la CPU. Tempo di turnaround: Tempo totale tra l'arrivo del processo e il suo completamento. Tempo di risposta: Tempo che intercorre tra l'arrivo del processo e la prima volta in cui inizia a essere eseguito. Throughput: Numero di processi completati nell'unità di tempo.

Gli algoritmi di scheduling possono essere classificati in base a due fattori principali: Preemptive vs Non-Preemptive Preemptive: Un processo in esecuzione può essere interrotto per assegnare la CPU a un altro processo (es. Round Robin, Priority Preemptive, SJF Preemptive). Non-Preemptive: Un processo mantiene la CPU fino a quando non termina o entra in stato di attesa (es. FCFS, SJF Non-Preemptive, Priority Non-Preemptive). Basati su Priorità o Durata Alcuni algoritmi decidono l'ordine dei processi basandosi su priorità (Priority Scheduling) o durata prevista (SJF). Altri utilizzano approcci equi, come Round Robin, che considera tutti i processi uguali.

Metriche di Valutazione

Conclusione

Gli algoritmi di scheduling sono il cuore della gestione dei processi nei sistemi operativi, influenzando direttamente le prestazioni, l’efficienza e l’esperienza utente. Ogni algoritmo ha punti di forza e limitazioni, ed è progettato per rispondere a esigenze specifiche, dai sistemi batch ai sistemi interattivi e real-time. La scelta dell’algoritmo più adatto dipende dal contesto operativo: per sistemi interattivi si preferiscono soluzioni come Round Robin o MLFQ, mentre per ambienti dove conta l’ottimizzazione del tempo di attesa algoritmi come SJF o Priority possono essere più appropriati. Comprendere il funzionamento e le implicazioni di ogni approccio è essenziale per progettare sistemi operativi bilanciati e performanti, in grado di soddisfare le necessità sia degli utenti che delle applicazioni.