CPU Scheduling nei sistemi operativi: concetti e algoritmi principali

Sistemi Operativi e Laboratorio

A. Formisano Dipartimento di Scienze Matematiche, Informatiche e Fisiche Anno Accademico 2024-25 Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 1

Contenuti

1. Scheduling dei Processi
2. Algoritmi di Scheduling dei Processi
3. Scheduling dei Thread
4. Scheduling per Sistemi Multiprocessore
5. Scheduling Real-time (cenni)
6. Scheduling in UNIX e Linux (cenni)

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 2

Scheduling dei Processi

Problema di Scheduling

Problema di scheduling In generale, risolvere un problema di scheduling consiste nel mappare un certo numero di compiti su un (diverso) numero di esecutori, in modo da realizzare gli obiettivi globali del sistema rispettando un prefissato insieme di vincoli Lo scheduling è un aspetto cruciale nei moderni sistemi di calcolo e, in forme più o meno sofisticate, viene applicato a tutte le risorse del sistema (CPU, device, dischi, ... ) In quanto segue ci occuperemo inizialmente dello scheduling della CPU (o short-term scheduling) in sistemi con una sola CPU Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 4

Scheduling dei Processi

Attivazione dello Scheduler della CPU

I principali eventi che possono causare uno switch di contesto (e che quindi fanno entrare in gioco lo scheduler):

• interruzione dovuta a timer (termine del quanto di tempo)
• interruzioni dovute ai dispositivi di I/O
• invocazione di system call (l'esempio più semplice è la exit ())
• gestione di segnali . . . .

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 5

Scheduling dei Processi

Compiti del Dispatcher

Lo scheduler sceglie quale processo eseguire. Successivamente il dispatcher:

1. effettua il context switch
2. inizializza il program counter alla prossima istruzione del programma da (continuare a) eseguire
3. effettua il passaggio alla modalità utente

Il tempo impiegato per fare ciò è detto latenza di dispatch Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 6

Scheduling dei Processi

Parametri Generali dello Scheduler

Molti parametri possono essere rilevanti nel progetto di uno scheduler:

• il numero di processori (uno o più), omogeneità/disomogeneità dei processori (in tipo, velocità, ISA, ... )
• staticità/dinamicità dell'insieme dei task
• on-line o off-line scheduling
• tempi di esecuzione noti a priori o sconosciuti
• presenza o meno di preemption (prelazione)
• presenza o meno di precedenze tra i task
• presenza o meno di priorità
• imposizione o meno di scadenze (deadline) su inizio/terminazione dei task
• presenza o meno di un obiettivo da ottimizzare (tempo di risposta, di completamento, produttività, ... )

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 7

Scheduling dei Processi

Obiettivi di Ottimizzazione

Diversi, spesso antitetici, sono gli obiettivi che si potrebbe voler ottimizzare:

• lunghezza dello schedule
• massimo tempo di risposta
• tempo medio di completamento
• tempo medio di risposta
• tempo di attesa
• minimo numero di CPU utilizzate
• produttività (throughput=num.task/tempo)
• utilizzo della CPU
• massimo ritardo rispetto a eventuali deadline

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 8

Scheduling dei Processi

Criteri per lo Scheduling della CPU

Dal punto di vista dell'utente:

• minimizzare il tempo di risposta
• minimizzare il tempo di completamento
• rispettare le deadline

Dal punto di vista del sistema:

• massimizzare l'utilizzo della CPU
• garantire la fairness (problema della starvation)
• massimizzare il throughput
• riflettere le priorità

Si noti che sia lo scheduler che il dispatcher rappresentano dei bottleneck del S.O. Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 9

Scheduling dei Processi

CPU-burst e I/O-burst

Il comportamento tipico di un processo consiste nell'alternare sequenze di operazioni d'elaborazione (CPU-burst) a sequenze di operazioni di I/O (I/O-burst), terminando con un CPU-burst Sistemi Operativi e Lab. 24/25 . . . 1 load store add store read from file CPU burst wait for I/O I/O burst store increment index write to file CPU burst wait for I/O I/O burst load store add store read from file CPU burst wait for I/O I/O burst . . . A. Formisano, DMIF 10

Scheduling dei Processi

CPU-bound e I/O-bound

Processi CPU-bound avranno pochi CPU-burst lunghi (P1), mentre processi I/O-bound avranno molti CPU-burst brevi (P2): P1 1 Attesa completamento I/O CPU-burst lungo CPU-burst breve P2 tempo Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 11

Scheduling dei Processi

Frequenze e Durate dei CPU-burst

Many short CPU bursts frequency 160 140 120 100 80 60 40 20 burst duration (ms) 8 16 24 32 40 Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 12

Scheduling dei Processi

Scheduling Preemptive e Non-Preemptive

Lo schema di scheduling può essere con o senza diritto di prelazione

• Nonpreemptive scheduling: (cooperativo, o senza diritto di prelazione) il processo running continua a detenere la CPU fino a quando termina o cede la CPU (per es. perchè richiede I/O)
• Preemptive scheduling: (con diritto di prelazione) il processo running può essere interrotto (e portato in stato ready) a seguito di un evento "ad esso esterno": scade il quanto di tempo, un altro processo diventa ready, ...

Il nonpreemptive scheduling è tipico dei sistemi batch. Il preemptive scheduling evita che i processi "meno" importanti ostacolino quelli critici, ma comporta un overhead di gestione. Un problema da affrontare riguarda la preemption attuata in modalità kernel: potrebbe portare a uno stato inconsistente del kernel Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 13

Algoritmi di Scheduling dei Processi

Un Caso di Studio

Nel descrivere le diverse politiche di scheduling faremo uso di un esempio. Supponiamo di schedulare i seguenti processi. Per semplicità consideriamo un singolo CPU-burst per processo e supponiamo siano note le durate e gli istanti di inizio:

Processo (1 CPU-burst) Tempo di arrivo del burst Durata del burst A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 15

Algoritmi di Scheduling dei Processi

First Come First Served (FCFS)

Selezione: Si seleziona il processo che è in nella ready-queue da più tempo. Ovvero: i processi vengono serviti nell'ordine in cui sono entrati nella ready-queue Decisione: nonpreemptive

0 5 10 15 20 P T D A 0 3 A B 2 6 B C 4 4 D 6 5 E 8 2 E Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 16 C D

Algoritmi di Scheduling dei Processi

Vantaggi di FCFS

• semplice da implementare e non comporta overhead di gestione
• non ci può essere starvation in quanto tutti i processi ready, prima o poi, ottengono l'uso della CPU

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 17

Algoritmi di Scheduling dei Processi

Svantaggi di FCFS

Questa politica privilegia i processi CPU-bound

• il tempo di attesa medio è molto legato all'ordine di arrivo dei burst
• il tempo di risposta di un processo può essere molto alto, anche per processi di breve durata
• un processo CPU-bound (o che addirittura non usa I/O) tende a monopolizzare il processore a scapito dei processi I/O-bound:
• (1) i processi I/O-bound terminano il burst di I/O e si accodano in ready (devices sottoutilizzati). (2) il CPU-bound rilascia la CPU per fare I/O. (3) tutti gli I/O-bound terminano il burst di CPU per fare I/O (CPU sottoutilizzata). (4) il CPU-bound termina l'I/O e torna ready ("prima" degli I/O-bound), e tutto si ripete. Quindi si tende a sottoutilizzare sia i device che la CPU (convoy effect) OSS .: se gli I/O-bound avessero assegnata "in qualche modo" una priorità superiore, avremmo un miglior uso dei device di I/O

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 18

Algoritmi di Scheduling dei Processi

Shortest Job First (SJF)

Questo algoritmo (come il successivo) cerca di ovviare ai difetti di FCFS Selezione: Si seleziona il processo che avrà il prossimo CPU-burst più breve. Decisione: nonpreemptive (È anche detto SPN o scheduling per brevità)

0 5 10 15 20 P T D A 0 3 A B 2 6 B C 4 4 C D 6 5 D E 8 2 E Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 19

Algoritmi di Scheduling dei Processi

Shortest Remaining Time First (SRTF)

Selezione: È la variante con preemption di SJF:

• si seleziona il processo che avrà il prossimo CPU-burst più breve, ma
• se P1 è running e in ready-queue giunge P2 con durata inferiore al tempo restante di P1, allora P2 sottrae la CPU a P1

Decisione: preemptive

0 5 10 15 20 P T D A 0 3 B 2 6 C 4 4 B D 6 5 C E 8 2 D E - - Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 20 1 1 A

Algoritmi di Scheduling dei Processi

Caratteristiche di SJF e SRTF

• i processi con il CPU-burst più breve sopravanzano gli altri
• SJF rappresenta lo scheduling ottimale: realizza il tempo di attesa medio migliore
• ci può essere starvation: i processi con CPU-burst lunghi tendono a restare molto tempo in ready-queue, non è garantito che ottengano l'uso della CPU entro un tempo limitato
• richiedono di prevedere la durata dei CPU-burst. Non è sempre possibile determinare queste durate

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 21

Algoritmi di Scheduling dei Processi

Stima delle Durate dei CPU-burst

La previsione/stima della durata del prossimo CPU-burst di un processo può essere compiuta basandosi sui suoi CPU-burst del passato. Si utilizza la media esponenziale: Tn+1 = atn + (1 - a)Tn dove tn è la durata dell'n-esimo CPU-burst cioè la storia recente, mentre Tn rappresenta il contributo della storia remota Sviluppando il termine n-esimo si ottiene: Tn+1= atn + (1 - a)atn-1+ (1 - a)2atn-2+ ... + (1 - a)"+ T0 con To e 0 < a ≤ 1 costanti predefinite. In particolare & permette di modulare il peso della storia recente/remota. Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 22

Algoritmi di Scheduling dei Processi

Highest Response Ratio First (HRRF)

Selezione: si seleziona il processo che ha il Response Ratio R maggiore, dove R = ta +ts ts con ta il tempo che il processo ha speso in attesa di ottenere la CPU, e ts la durata prevista del CPU-burst del processo Decisione: nonpreemptive

0 5 10 15 20 P T D A 0 3 A B 2 6 B C 4 4 D 6 5 C E 8 2 D E - - Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 23

Algoritmi di Scheduling dei Processi

Considerazioni su HRRF

Alcune considerazioni:

• processi con CPU-burst brevi sono favoriti (ts al denominatore), ma si tiene conto dell'età del processo (ta al numeratore), quindi processi con tempo di servizio ts lungo guadagnano priorità man mano che invecchiano (per un processo nuovo R = 1)
• è un meccanismo di aging: evita la starvation
• come SJF e SRTF richiede stime sul tempo di servizio richiesto dai processi

Sistemi Operativi e Lab. 24/25 A. Formisano, DMIF 24