Algoritmi di pianificazione del sistema operativo
Un Process Scheduler pianifica diversi processi da assegnare alla CPU in base a particolari algoritmi di pianificazione. Ci sono sei popolari algoritmi di pianificazione dei processi di cui parleremo in questo capitolo:
- Pianificazione FCFS (First-Come, First-Served)
- Pianificazione Shortest-Job-Next (SJN)
- Pianificazione prioritaria
- Tempo rimanente più breve
- Programmazione Round Robin (RR)
- Pianificazione delle code a più livelli
Questi algoritmi sono entrambi non-preemptive or preemptive. Gli algoritmi non preventivi sono progettati in modo che una volta che un processo entra nello stato di esecuzione, non può essere anticipato fino a quando non completa il tempo assegnato, mentre la pianificazione preventiva è basata sulla priorità in cui uno scheduler può anticipare un processo in esecuzione a bassa priorità in qualsiasi momento quando una priorità alta il processo entra in uno stato pronto.
Primo arrivato, primo servito (FCFS)
- I lavori vengono eseguiti in base all'ordine di arrivo.
- È un algoritmo di pianificazione non preventivo e preventivo.
- Facile da capire e implementare.
- La sua implementazione è basata sulla coda FIFO.
- Scarse prestazioni poiché il tempo di attesa medio è elevato.
Wait time di ogni processo è il seguente:
| Processi | Tempo di attesa: Orario di servizio - Orario di arrivo |
|---|---|
| P0 | 0 - 0 = 0 |
| P1 | 5-1 = 4 |
| P2 | 8-2 = 6 |
| P3 | 16-3 = 13 |
Tempo di attesa medio: (0 + 4 + 6 + 13) / 4 = 5,75
Lavoro più breve successivo (SJN)
Questo è anche noto come shortest job firsto SJF
Questo è un algoritmo di pianificazione preventivo e non preventivo.
Il miglior approccio per ridurre al minimo i tempi di attesa.
Facile da implementare nei sistemi batch dove il tempo di CPU richiesto è noto in anticipo.
Impossibile implementare in sistemi interattivi in cui il tempo di CPU richiesto non è noto.
L'elaboratore dovrebbe sapere in anticipo quanto tempo richiederà il processo.
Dati: tabella dei processi e ora di arrivo, ora di esecuzione
| Processi | Orario di arrivo | Tempo di esecuzione | Tempo di servizio |
|---|---|---|---|
| P0 | 0 | 5 | 0 |
| P1 | 1 | 3 | 5 |
| P2 | 2 | 8 | 14 |
| P3 | 3 | 6 | 8 |
Waiting time di ogni processo è il seguente:
| Processi | Tempo di attesa |
|---|---|
| P0 | 0 - 0 = 0 |
| P1 | 5-1 = 4 |
| P2 | 14 - 2 = 12 |
| P3 | 8-3 = 5 |
Tempo di attesa medio: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25
Pianificazione basata su priorità
La pianificazione prioritaria è un algoritmo non preventivo e uno degli algoritmi di pianificazione più comuni nei sistemi batch.
Ad ogni processo viene assegnata una priorità. Il processo con la priorità più alta deve essere eseguito per primo e così via.
I processi con la stessa priorità vengono eseguiti in base all'ordine di arrivo.
La priorità può essere decisa in base ai requisiti di memoria, ai requisiti di tempo o a qualsiasi altro requisito di risorse.
Dato: tabella dei processi e loro ora di arrivo, ora di esecuzione e priorità. Qui stiamo considerando che 1 è la priorità più bassa.
| Processi | Orario di arrivo | Tempo di esecuzione | Priorità | Tempo di servizio |
|---|---|---|---|---|
| P0 | 0 | 5 | 1 | 0 |
| P1 | 1 | 3 | 2 | 11 |
| P2 | 2 | 8 | 1 | 14 |
| P3 | 3 | 6 | 3 | 5 |
Waiting time di ogni processo è il seguente:
| Processi | Tempo di attesa |
|---|---|
| P0 | 0 - 0 = 0 |
| P1 | 11 - 1 = 10 |
| P2 | 14 - 2 = 12 |
| P3 | 5-3 = 2 |
Tempo di attesa medio: (0 + 10 + 12 + 2) / 4 = 24/4 = 6
Tempo rimanente più breve
Il tempo rimanente più breve (SRT) è la versione preventiva dell'algoritmo SJN.
Il processore viene assegnato al lavoro più vicino al completamento, ma può essere preceduto da un lavoro pronto più recente con tempi più brevi per il completamento.
Impossibile implementare in sistemi interattivi in cui il tempo di CPU richiesto non è noto.
Viene spesso utilizzato in ambienti batch in cui è necessario dare la preferenza a lavori brevi.
Round Robin Scheduling
Round Robin è l'algoritmo di pianificazione preventiva del processo.
A ogni processo viene fornito un tempo di correzione per l'esecuzione, è chiamato a quantum.
Una volta che un processo viene eseguito per un determinato periodo di tempo, viene interrotto e altri processi vengono eseguiti per un determinato periodo di tempo.
Il cambio di contesto viene utilizzato per salvare gli stati dei processi anticipati.
Wait time di ogni processo è il seguente:
| Processi | Tempo di attesa: Orario di servizio - Orario di arrivo |
|---|---|
| P0 | (0-0) + (12-3) = 9 |
| P1 | (3 - 1) = 2 |
| P2 | (6 - 2) + (14 - 9) + (20 - 17) = 12 |
| P3 | (9 - 3) + (17 - 12) = 11 |
Tempo medio di attesa: (9 + 2 + 12 + 11) / 4 = 8.5
Pianificazione delle code a più livelli
Le code a più livelli non sono un algoritmo di pianificazione indipendente. Fanno uso di altri algoritmi esistenti per raggruppare e programmare lavori con caratteristiche comuni.
- Vengono mantenute più code per processi con caratteristiche comuni.
- Ogni coda può avere i propri algoritmi di pianificazione.
- Le priorità vengono assegnate a ciascuna coda.
Ad esempio, i lavori associati alla CPU possono essere pianificati in una coda e tutti i lavori associati a I / O in un'altra coda. Il Process Scheduler seleziona quindi alternativamente i lavori da ciascuna coda e li assegna alla CPU in base all'algoritmo assegnato alla coda.