Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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