Marco Lapegna » 8.Algoritmi di scheduling

Sistemi operativi

Algoritmi di scheduling

Scheduling a priorità

• Un valore di priorità (intero) è associato a ciascun processo.
• La CPU viene allocata al processo con la priorità più alta
  • preemptive
  • non–preemptive

ESEMPIO

SJF è uno scheduling a priorità dove la priorità è rappresentata dall’inverso del burst di CPU.

Priorità

La priorità è un numero intero in un intervallo fissato

Es:

0 ≤ p ≤ 20

0 ≤ p ≤ 4096

Ogni sistema ha il proprio modo di misurare la priorità:

• p = 0 priorità alta

oppure

• p = 0 priorità bassa (es. Windows e Linux)

Problemi:

Possibilità di starvation (posticipazione indefinita)

SJF:

• Forte disparità tra processi corti e processi lunghi

Priorità:

• I processi a bassa priorità potrebbero non venir mai eseguiti

Soluzione:

Aging (invecchiamento):

• aumento graduale della priorità dei processi che si trovano in attesa nel sistema da lungo tempo

Esempio HRRN vs SJF

Processo -> Tempo attesa -> Tempo di burst

P1 -> 20 -> 5

P2 -> 9 -> 3

Processo -> Priorità HRRN

P1 -> (20+5)/5 = 5

P2 -> (9+3)/3 = 4

• SJF prima P2 e poi P1
• HRRN prima P1 e poi P2

P = 1 -> Minima priorità

Problema

HRRN è stato introdotto per superare l’eccessiva disparità di trattamento tra processi corti e processi lunghi operata da SJF.

Come misurare questa qualita’ di HRRN?

Scheduling Round Robin (RR)

• Scheduling con prelazione progettato appositamente per sistemi time sharing
• A ciascun processo viene allocata una piccola unità di tempo di CPU (quanto di tempo o timeslice), generalmente 10–100 millisecondi. Trascorso il quanto di tempo, il processo è forzato a rilasciare la CPU e accodato alla ready queue.

Scheduling Round Robin (RR)

• Se ci sono n processi nella ready queue ed il quanto di tempo è q, ciascun processo occupa 1/n del tempo di CPU in frazioni di, al più, q unità di tempo.
• Nessun processo attende per più di (n -1) x q unità di tempo.

Scheduling RR con quanto = 20

In genere si ha un tempo medio di attesa maggiore rispetto a SJF, tuttavia si ha un miglior tempo di completamento per i processi lunghi.

Quanto di tempo

La grandezza del quanto di tempo determina il tempo di risposta delle richieste interattive:

• Quanto di tempo grande
  • Processi in esecuzione per molto tempo
  • Di fatto diventa FCFS
• Quanto di tempo piccolo
  • Il sistema impiega più tempo nel cambio di contesto che nell’esecuzione dei programmi

Scheduling con code multiple

• La ready queue è suddivisa in code separate:
  • foreground (interattiva)
  • background (batch)
• Ciascuna coda ha il suo proprio algoritmo di scheduling. ESEMPIO:
  • foreground – RR
  • background – FCFS

Scheduling con code multiple

È necessario uno scheduling tra code.

• Scheduling a priorità fissa: es. serve tutti i processi in foreground poi in background. Rischio di starvation.
• Time slice : ciascuna coda occupa un certo tempo di CPU che suddivide fra i propri processi. Ad esempio:
  • 80% per foreground in RR
  • 20% per background in FCFS

Code multiple con feedback

Un processo può spostarsi fra le varie code; l’aging può essere implementato in questo modo.

Lo scheduler con code multiple con feedback è definito dai seguenti parametri:

• Numero di code
• Algoritmi di scheduling per ciascuna coda
• Algoritmi di scheduling tra le code
• Metodo impiegato per determinare quando spostare un processo in una coda a priorità maggiore

Esempio

Tre code: Q₀ – quanto di tempo di 8 millisecondi; Q₁ – quanto di tempo di 16 millisecondi; Q₂ – FCFS.

Scheduling:

• Un nuovo job viene immeso nella coda Q0 che è servita RR. Quando prende possesso della CPU il job riceve 8 millisecondi. Se non termina, viene spostato nella coda Q₁.
• Nella coda Q₁ il job è ancora servito RR e riceve ulteriori 16 millisecondi. Se ancora non ha terminato, viene mosso nella coda Q₂.

Cenni al real-time

• I s.o. real time hanno algoritmi di scheduling differenti dai sistemi interattivi / time-sharing
• Obiettivo primario: assicurare che un dato processo finisca entro i termini previsti (deadline)

Cenni al real-time

In generale i s.o. real time gestiscono mansioni specifiche di durata fissata:

• Processi periodici (ad es. raccogliere informazioni sul traffico aereo ogni secondo)
• Processi asincroni (ad es. in risposta ad un dato evento)
  • facile prevedere la durata dell’esecuzione
  • possibile usare algoritmi di scheduling a priorità

Earliest deadline first (EDF)

• Algoritmo con prelazione che dà precedenza ai processi con deadline più vicina
• Obiettivo: soddisfare la deadline del maggior numero di processi
• Si può dimostrare che tale algoritmo minimizza l’eventuale ritardo del processo “più ritardatario”
• A volte non utilizzabile per la mancanza di supporto hardware (timer necessario per la prelazione)

Minimum laxity first (MLF)

Il rilassabilità (laxity) è una misura della non urgenza di un processo:

Ad es. se per un dato processo:

• T = tempo corrente = 5
• D = deadline = 9
• C = tempo di esecuzione rimanente = 3

L = (D-T) – C = 1

E’ il tempo che tale processo può attendere prima di essere mandato in esecuzione e rispettare la deadline

• Precedenza ai processi con la rilassabilità minore.

Prossima lezione

La sincronizzazione dei processi

• Background
• Il problema della sezione critica
• Soluzioni software
• Soluzioni hardware