# Algoritmi di Scheduling ## FCFS (First-Come-First-Served) ### Introduzione **FCFS (First-Come-First-Served)**, noto anche come "Primo Arrivato, Primo Servito", è uno degli algoritmi di scheduling della CPU più **semplici** e **intuitivi**. I processi vengono eseguiti in base all'ordine di arrivo nella coda dei processi pronti. Il primo processo a entrare nella coda è il primo a essere servito. ### Caratteristiche Principali - **Non-Preemptive:** - FCFS è un algoritmo non preemptive, il che significa che un processo in esecuzione non può essere interrotto finché non completa il suo CPU burst o si blocca volontariamente (ad esempio, per operazioni di I/O). - **Facile da Implementare:** - Richiede solo una coda FIFO (First-In-First-Out) per gestire l'ordine di arrivo dei processi pronti. - **Equo:** - Il processo che arriva per primo viene eseguito per primo. Tuttavia, questa equità può portare a problemi di efficienza. - **Effetto Convoglio:** - Uno dei principali svantaggi di FCFS. I processi con CPU burst lunghi (processi CPU bound) bloccano quelli successivi, anche se più brevi, aumentando i tempi di attesa. ### Casi di Utilizzo L'algoritmo FCFS è adatto per: - Ambienti **non interattivi**, come sistemi batch. - Carichi di lavoro **moderati**. - Applicazioni **non critiche**. <im> L'effetto convoglio e i tempi di attesa elevati lo rendono meno adatto a sistemi complessi e interattivi. </im> ### Esercizio di Esempio <ex> Immaginiamo tre processi $P_1$, $P_2$ e $P_3$ che arrivano simultaneamente nella coda dei processi pronti. I rispettivi tempi di esecuzione (CPU burst) sono: | Processo | Tempo di Arrivo | CPU Burst | |----------|-----------------|-----------| | $P_1$ | 0 | 10 | | $P_2$ | 0 | 5 | | $P_3$ | 0 | 20 | La coda iniziale contiene: **[$P_1$, $P_2$, $P_3$]**. #### Applicazione di FCFS 1. **Tempo 0:** - Esecuzione di $P_1$. - Tempo di attesa di $P_1$: **0**. - Coda: **[$P_2$, $P_3$]**. 2. **Tempo 10:** - Esecuzione di $P_2$. - Tempo di attesa di $P_2$: **10**. - Coda: **[$P_3$]**. 3. **Tempo 15:** - Esecuzione di $P_3$. - Tempo di attesa di $P_3$: **15**. - Coda: **[ ]**. #### Risultato Finale | Processo | Tempo di Attesa | |----------|-----------------| | $P_1$ | 0 | | $P_2$ | 10 | | $P_3$ | 15 | **Tempo di attesa medio:** $ \text{Media} = \frac{0 + 10 + 15}{3} = 8,33 \text{ unità di tempo} $ </ex> --- ## SJF (Shortest Job First) ### Introduzione **SJF (Shortest Job First)**, noto anche come "Primo il Lavoro più Breve", è un algoritmo di scheduling che prioritizza i processi in base alla loro durata prevista o al loro prossimo CPU burst. Il processo con il minor tempo di esecuzione stimato viene eseguito per primo. ### Caratteristiche Principali - **Riduzione del Tempo di Attesa:** - SJF riduce il tempo di attesa medio dando priorità ai processi più brevi. - **Difficoltà di Implementazione:** - Richiede la conoscenza o la stima anticipata dei tempi di esecuzione dei processi, rendendolo più complesso rispetto a FCFS. - **Rischio di Starvation:** - I processi più lunghi possono rimanere bloccati se ci sono continuamente processi più brevi in arrivo. ### Casi di Utilizzo SJF è ideale per: - Ambienti dove il tempo di risposta è critico. - Scenari con stime accurate dei tempi di esecuzione. <im> Non è adatto a sistemi con molti processi lunghi, a causa del rischio di starvation. </im> ### Esercizio di Esempio <ex> Immaginiamo tre processi $P_1$, $P_2$ e $P_3$ che arrivano simultaneamente nella coda dei processi pronti. I rispettivi tempi di esecuzione (CPU burst) sono: | Processo | Tempo di Arrivo | CPU Burst | |----------|-----------------|-----------| | $P_1$ | 0 | 10 | | $P_2$ | 0 | 5 | | $P_3$ | 0 | 20 | La coda iniziale contiene: **[$P_1$, $P_2$, $P_3$]**. #### Applicazione di SJF 1. **Tempo 0:** - Esecuzione di $P_2$. - Tempo di attesa di $P_2$: **0**. - Coda: **[$P_1$, $P_3$]**. 2. **Tempo 5:** - Esecuzione di $P_1$. - Tempo di attesa di $P_1$: **5**. - Coda: **[$P_3$]**. 3. **Tempo 15:** - Esecuzione di $P_3$. - Tempo di attesa di $P_3$: **15**. - Coda: **[ ]**. #### Risultato Finale | Processo | Tempo di Attesa | |----------|-----------------| | $P_1$ | 5 | | $P_2$ | 0 | | $P_3$ | 15 | **Tempo di attesa medio:** $ \text{Media} = \frac{5 + 0 + 15}{3} = 6,66 \text{ unità di tempo} $ </ex> --- ## SJF con Prelazione (Shortest Remaining Time First - SRTF) ### Introduzione **SJF con Prelazione**, noto anche come **SRTF (Shortest Remaining Time First)**, è una variante preemptive di SJF che permette di interrompere un processo in esecuzione se arriva un nuovo processo con un tempo di esecuzione stimato più breve. ### Caratteristiche Principali - **Preemptive:** - Consente di interrompere un processo in corso se un nuovo processo con un tempo di esecuzione stimato più breve arriva nella coda dei pronti. Il processo interrotto riprenderà l'esecuzione una volta completati i processi più brevi. - **Minimizzazione del Tempo di Attesa:** - Riduce ulteriormente il tempo di attesa medio rispetto a SJF non-preemptive. - **Maggiore Complessità di Implementazione:** - Richiede una gestione più complessa della coda dei processi pronti e un controllo continuo dei tempi di esecuzione. - **Risposta Rapida:** - Favorisce i processi più brevi, migliorando i tempi di risposta per questi processi. - **Rischio di Starvation:** - Come in SJF, i processi con tempi di esecuzione lunghi possono essere penalizzati se arrivano continuamente processi più brevi. <im> Come per SJF, anche SRTS Non è adatto a sistemi con molti processi lunghi, a causa del rischio ancora maggiore di starvation. </im> ### Esercizio di Esempio <ex> Consideriamo tre processi, $P_1$, $P_2$ e $P_3$, che arrivano in momenti diversi con i seguenti tempi di esecuzione: | Processo | Tempo di Arrivo | CPU Burst | |----------|-----------------|-----------| | $P_1$ | 0 | 10 | | $P_2$ | 2 | 5 | | $P_3$ | 4 | 2 | #### Applicazione di SRTF 1. **Tempo 0-2:** - Esecuzione di $P_1$. - Tempo di attesa di $P_1$: **0**. 2. **Tempo 2-4:** - Esecuzione di $P_1$ continua (8 unità rimanenti). - Arriva $P_2$, ma $P_1$ ha ancora il tempo di esecuzione più breve. - Tempo di attesa di $P_2$: **2**. 3. **Tempo 4-6:** - Arriva $P_3$ con un tempo di esecuzione più breve. Interrompe $P_1$ e inizia l'esecuzione. - Tempo di attesa di $P_3$: **0**. 4. **Tempo 6-11:** - Completato $P_3$, $P_2$ diventa il processo più breve e inizia l'esecuzione. - Tempo di attesa di $P_2$: **4**. 5. **Tempo 11-17:** - Completato $P_2$, $P_1$ riprende e termina l'esecuzione. - Tempo di attesa di $P_1$: **11**. #### Risultato Finale | Processo | Tempo di Attesa | |----------|-----------------| | $P_1$ | 11 | | $P_2$ | 4 | | $P_3$ | 0 | **Tempo di attesa medio:** $ \text{Media} = \frac{11 + 4 + 0}{3} = 5 \text{ unità di tempo} $ </ex> --- ## Round Robin (RR) ### Introduzione **Round Robin (RR)** è un algoritmo di scheduling della CPU che assegna a ogni processo un intervallo di tempo fisso, chiamato **time slice** o **quantum**. Dopo che un processo ha utilizzato il suo time slice, viene sospeso e rimesso in coda, permettendo al prossimo processo di eseguire. Questo approccio garantisce una gestione equa dei processi. ### Caratteristiche Principali - **Preemptive:** - Se un processo non termina entro il suo quantum, viene interrotto e rimesso in coda. - **Time Slice Fisso:** - Ogni processo riceve lo stesso tempo di esecuzione per ciclo. La scelta del valore del time slice è cruciale: - **Quantum troppo breve:** Aumenta l'overhead dovuto ai frequenti cambi di contesto. - **Quantum troppo lungo:** Riduce l'efficienza del sistema e si comporta come FCFS. - **Equità:** - Ogni processo riceve la stessa opportunità di accedere alla CPU, rendendo l'algoritmo adatto a sistemi interattivi. - **Semplice da Implementare:** - L'algoritmo utilizza una coda circolare per gestire i processi. ### Casi di Utilizzo - **Sistemi Interattivi:** - Ideale per sistemi in cui i processi richiedono tempi di risposta rapidi, come nei sistemi operativi multitasking. - **Molti Processi Brevi:** - Adatto ad ambienti con numerosi processi che richiedono un utilizzo limitato della CPU. <im> RR non è sempre ottimale in termini di throughput o tempo di attesa medio, specialmente se il quantum non è ben calibrato. </im> ### Esercizio di Esempio <ex> Immaginiamo quattro processi che arrivano in momenti diversi e con diversi tempi di esecuzione: | Processo | Tempo di Arrivo | CPU Burst | |----------|-----------------|-----------| | $P_1$ | 0 | 5 | | $P_2$ | 2 | 10 | | $P_3$ | 4 | 13 | | $P_4$ | 6 | 20 | **Quantum assegnato:** 5 unità di tempo. **Tempo per cambio di contesto:** 1 unità di tempo. ### Applicazione dell'Algoritmo 1. **Tempo 0-5:** - **$P_1$** esegue per 5 unità di tempo e completa la sua esecuzione. - Nessun cambio di contesto necessario poiché non ci sono altri processi pronti. 2. **Tempo 5-6:** - Cambio di contesto per passare a $P_2$. 3. **Tempo 6-11:** - **$P_2$** esegue per 5 unità di tempo. - Rimane con 5 unità di tempo non completate e viene rimesso in coda. 4. **Tempo 11-12:** - Cambio di contesto per passare a $P_3$. 5. **Tempo 12-17:** - **$P_3$** esegue per 5 unità di tempo. - Rimane con 8 unità di tempo non completate e viene rimesso in coda. 6. **Tempo 17-18:** - Cambio di contesto per passare a $P_4$. 7. **Tempo 18-23:** - **$P_4$** esegue per 5 unità di tempo. - Rimane con 15 unità di tempo non completate e viene rimesso in coda. 8. **Tempo 23-24:** - Cambio di contesto per tornare a $P_2$. 9. **Tempo 24-29:** - **$P_2$** esegue per le sue ultime 5 unità di tempo e completa l'esecuzione. 10. **Tempo 29-30:** - Cambio di contesto per tornare a $P_3$. 11. **Tempo 30-35:** - **$P_3$** esegue per 5 unità di tempo. - Rimane con 3 unità di tempo non completate e viene rimesso in coda. 12. **Tempo 35-36:** - Cambio di contesto per tornare a $P_4$. 13. **Tempo 36-41:** - **$P_4$** esegue per 5 unità di tempo. - Rimane con 10 unità di tempo non completate e viene rimesso in coda. 14. **Tempo 42-43:** - Cambio di contesto per tornare a $P_3$. 15. **Tempo 43-46:** - **$P_3$** esegue per le sue ultime 3 unità di tempo e completa l'esecuzione. 16. **Tempo 46-47:** - Cambio di contesto per tornare a $P_4$. 17. **Tempo 47-57:** - **$P_4$** esegue per le sue ultime 10 unità di tempo e completa l'esecuzione. --- ### Risultato Finale | Processo | Tempo di Attesa | Tempo di Completamento | |----------|-----------------|------------------------| | $P_1$ | 0 | 5 | | $P_2$ | 17 | 29 | | $P_3$ | 26 | 46 | | $P_4$ | 36 | 57 | **Tempo di attesa medio:** $ \text{Media} = \frac{0 + 17 + 26 + 36}{4} = 19,75 \text{ unità di tempo} $ </ex>