Youlaurea.it
Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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)

Esempio : priorità senza prelazione

Processo -> Priorità -> Tempo di burst

P1 -> 1 -> 7

P2 -> 3 -> 4

P3 -> 2 -> 1

P4 -> 1 -> 4

P = 0 -> Massima priorità

Tempo medio di attesa = (0 + 12 + 11 +7)/4 = 7.5

Tempo medio di completamento = (7 + 16 + 12 +11)/4 = 11.5

Diagramma di Gantt

Diagramma di Gantt


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

Highest Response Ratio Next scheduling

Scheduling senza prelazione a priorità variabile

  • E’ un modo per realizzare l’aging
  • La priorità è funzione di:
    • Tempo di attesa
    • Tempo di burst

P = 1 -> Minima priorità

  • T attesa: favorisce i processi che hanno già atteso molto
  • T burst: favorisce i processi corti
Definizione di priorità

Definizione di priorità


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à

Esempio HRRN vs SJF

Tempi medi di completamento:

  • SJF = (28+12)/2 = 20
  • HRRN = (25+17)/2 = 21
Comparazione dei diagrammi HRRn e SJF

Comparazione dei diagrammi HRRn e SJF


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?

Problema

La deviazione standard (o scarto quadratico medio) è una misura della dispersione di un insieme di numeri x1 , … , xn

  • σ piccolo <-> dati “vicini” tra loro
  • σ grande <-> dati “lontani” tra loro
Equazione dello scarto quadratico medio

Equazione dello scarto quadratico medio


Esempio HRRN vs SJF

La politica HRRN è più equa (i tempi di completamento sono più omogenei).

Equazioni comparative HRRN e SJF

Equazioni comparative HRRN e SJF


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

Quanto di tempo e tempo di turnaround

Empiricamente: il quanto di tempo deve essere maggiore dell’80% dei CPU burst.

Tabella quantum/average time

Tabella quantum/average time


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: Q0 – quanto di tempo di 8 millisecondi; Q1 – quanto di tempo di 16 millisecondi; Q2FCFS.

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 Q1.
  • Nella coda Q1 il job è ancora servito RR e riceve ulteriori 16 millisecondi. Se ancora non ha terminato, viene mosso nella coda Q2.

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
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion