Scheduling in Windows 2000
Un thread entra in modalità kernel e chiama lo scheduler quando:
• Si blocca su un oggetto di sincronizzazione (semaforo, mutex, ecc..)
• Fa una segnalazione ad un oggetto (rilascia un semaforo)
• Termina il suo quanto di tempo.
Lo scheduler gestisce un array con 32 entry (liste di thread, una per ogni
priorità dei thread)
1
Scheduling in Windows 2000
Windows 2000 fornisce 32 priorità diverse per i thread
2
Scheduling in Windows 2000
• Win32 permette all’utente di specificare :
– priorità di un processo (6 livelli diversi)
– priorità di un thread all’interno di un processo (7 livelli diversi)
Attraverso le API SetPriorityClass e SetThreadPriority
• Windows 2000 mappa le 42 combinazioni possibili su 32
livelli di priorità
3
Scheduling in Windows 2000
Corrispondenza fra le priorità di Win32 e quelle di Windows 2000
4
Scheduling in Windows 2000
Algoritmo di scheduling :
• Si esegue il primo thread della prima coda non vuota
per massimo 1 quanto (20ms--120ms)
• Scheduling round robin fra thread con la stessa priorità
• Come variano le priorità nel tempo :
– i thread tipicamente entrano a priorità 8
– la priorità viene elevata se:
• viene completata una operazione di I/O (+1 disco, +2
linea seriale, +6 tastiera, +8 scheda audio …)
• termina l’attesa su un semaforo, mutex
• l’input nella finestra di dialogo associata al thread è
pronto
5
Scheduling in Windows 2000
Algoritmo di scheduling :
• Come variano le priorità nel tempo
– la priorità viene abbassata se:
• un thread usa tutto il suo quanto (-1)
– se un thread non ha girato per un tempo maggiore di una
soglia fissata, allora passa per 2 quanti a priorità 15 (serve a
gestire potenziali inversioni di priorità)
6
Lo scheduler di Linux
• Vengono schedulati i thread, non i processi
• Tre classi di thread : real-time FIFO, real-time Round
Robin, Timesharing
• Ogni thread ha
– una priorità nell’intervallo [0, +40], generalmente all’inizio la
priorità di default è 20 (può essere variata con la system call
nice(valore) : nuova_priorità = 20 – valore)
– un quanto (misurato in jiffy o tick = 10ms)
• Lo scheduler calcola la goodness (gdn) di ogni thread
come
if (class == real-time) gdn = 1000 + priority
if (class == timeshar && quantum > 0) gdn = quantum + priority
if (class == timeshar && quantum == 0) gdn = 0
7
Lo scheduler di Linux
Algoritmo di scheduling :
• Ogni volta viene selezionato il thread con goodness
maggiore
• Ogni volta che arriva un tick (segnale del clock) il
quanto del processo in esecuzione viene decrementato
• Un thread viene de-schedulato se si verifica una delle
seguenti condizioni
– il quanto diventa 0
– il thread si blocca su semafori, mutex, ecc..
– diventa ready un thread con una goodness maggiore
8
Lo scheduler di Linux
Algoritmo di scheduling:
• Quando tutti i quanti dei processi ready sono andati a 0 , lo
scheduler ricalcola il quanto di ogni processo (anche se blocked)
come segue :
quantum = quantum / 2 + priority
Perche i processi bloccati avranno del quantum
rimanente.
9
LINUX: struttura generale
User
Interface
The layers of a UNIX system.
10
Processi in LINUX
• Ogni processo nasce con un solo thread
• Un processo gira in modalità utente; quando effettua
una system call passa in modalità kernel e può
operare sulle risorse del sistema.
• Il kernel possiede due strutture per ogni processo:
– process table e user structure
11
Gestione dei Processi
Process table : risiede sempre in RAM
Contiene:
•
•
•
•
•
•
parametri per lo scheduling (priorità, tempo consumato, ecc.)
immagine di memoria (punatori alle aree di memoria e al disco).
informazioni sui segnali (quali segnali gestire, ignorare, ecc.)
Stato del processo
PID, PID del padre
user e group id.
12
Gestione dei Processi
• User structure risiede su disco se il processo è swapped
Contiene informazioni non necessarie quando il processo non è in
esecuzione:
– Registri macchina
– tabella dei descrittori di file aperti
– stato della system call corrente (parametri)
– kernel stack
– informazioni di accounting (tempo CPU, limiti, ecc.)
13
Creazione di Processi
int pid = fork()
– crea una copia esatta del processo invocante
– restituisce 0 al figlio ed il PID del figlio al padre
– duplica i dati e lo stack del padre nel figlio in
un’area di memoria differente
– i file aperti dal padre sono condivisi al figlio
– Il figlio eseguirà lo stesso codice del padre
14
Creazione di Processi
execl (nome_con_path, nome, argv)
– Fa eseguire a un processo un codice diverso, con diversi
parametri
– Nome_con_path = nome dell’eseguibile compreso di path
– nome = nome dell’eseguibile
– Argv = lista di parametri del’eseguibile separati da virgola,
terminati da NULL
Esempio di processo che lancia ls -l
execv (“/bin/ls”, “ls”, “-l”, NULL);
Esistono altre chiamate con differenti argomenti: execv, execve,
execle, ecc..
15
Terminazione di processi
• wait(&status)
– attende la terminazione di un processo figlio
– dopo l’esecuzione di wait, status contiene l’esito
della computazione del processo figlio (il codice di
uscita del figlio e altre informazioni)
• exit(status)
– termina il processo e restituisce il valore di status al
padre (nella variabile status restituita da wait)
16
Terminazione di processi
• Processi zombie
– processi terminati il cui padre non ha (ancora)
eseguito la wait()
– attendono di restituire il codice di terminazione
e svanire, altrimenti rimangono zombie e sono
eliminati da uno speciale processo detto init
17
Comunicazione fra processi
• Pipe : file speciali utilizzati per connettere due processi
con un canale unidirezionale di comunicazione
• Se B cerca di leggere da una pipe vuota si blocca
• Se A scrive su una pipe piena, viene bloccato fino
a che non viene letto qualcosa
• L’ampiezza della pipe dipende dal sistema
18
Comunicazione fra processi
Una pipe si crea con l’istruzione:
int pd[2];
pipe(pd);
Si legge da pd[0] e si scrive su pd[1]
Per leggere:
read (pd[0], buffer, lung);
Per scrivere:
write (pd[1], buffer, lung);
Dove buffer è un’array di caratteri e lung è la lunghezza del
messaggio.
19
Comunicazione fra processi
• Segnali (interruzioni software)
– comunicano al processo il verificarsi di una certo
evento
– possono essere inviati solo ai membri del proprio
gruppo (antenati, discendenti)
– generalmente possono essere ignorati, catturati o
possono terminare il processo (default per molti
segnali)
– per i segnali catturabili si può specificare un signal
handler che viene mandato in esecuzione appena il
segnale viene rilevato
20
Comunicazione fra processi
• Segnali (cont.)
– particolari combinazioni di tasti inviano dei segnali al
processo in foregroud
• Control-C corrisponde a SIGINT
• Control-Z corresponde a SIGTSTP
– i segnali servono anche al SO per a comunicare al
processo il verificarsi di particolari eventi (es.
SIGFPE, errore floating-point)
21
I segnali previsti da POSIX
22
Chiamate di sistema relative ai processi
s è un codice di errore
pid è il codice di identificazione di un processo
23