Domenico Cotroneo » 9.Gestione dei processi nei sistemi operativi Unix/Linux e Windows

Sommario

• Gestione dei processi nei S.O. Unix/Linux
• Gestione dei processi e dei thread nei S.O. Windows

I processi Unix

Unix è un sistema operativo multiprogrammato a divisione di tempo.

Caratteristiche del processo Unix:

• processo pesante con codice rientrante:
  • dati non condivisi;
  • più processi possono condividere lo stesso codice;
• funzionamento dual mode:
  • processi di utente (modo user);
  • processi di sistema (modo kernel).

Stati di un processo Unix

Lo stato Zombie

Stato in cui un processo ha terminato, ma non può essere ancora eliminato perché la sua immagine è ancora necessaria.

Esempio tipico: il processo figlio termina prima del padre. Il processo è zombie finchè il padre non rileva lo stato di terminazione del figlio.

Stati di un processo Unix:Un modello più completo

Da user a kernel mode: esempio della system call read()

Un processo, in modo “user running“, esegue la system call read(). Una richiesta viene inoltrata al kernel per leggere i dati da un file.

• L’esecuzione della system call read() pone il processo nello stato “kernel running“, in quanto esso sta richiedendo l’accesso ad una risorsa controllata (disk drive). Uno degli argomenti della system call read() è l’indirizzo di un buffer, dove saranno memorizzate le informazioni lette dal file al termine dell’esecuzione della system call.
• Il kernel, all’atto della ricezione della system call read() (evento sincrono), dovrà eseguire delle routine interne, al fine di trovare la locazione dei files contenenti i dati da leggere e per attivare il corrispondente device per la lettura.
• Il tempo necessario al device per eseguire le opportune operazioni hardware è relativamente lungo. Il tempo medio di accesso ad un disco, per esempio, è dell’ordine dei 15ms. Per tale motivo, il kernel sospenderà il processo in attesa del device, ponendolo in stato “asleep“, a favore di qualche altro processo che abbia lavoro utile da far compiere alla CPU.

Da user a kernel mode: esempio della system call read()

Il device, una volta completata l’operazione di lettura, notificherà mediante un interrupt al kernel il completamento del task.

La routine di interrupt (ISR) verrà eseguita con una priorità molto elevata in modo da poter prelazionare qualsiasi altro task a priorità inferiore. Lo scopo fondamentale della ISR consiste nel far transitare il processo dallo stato asleep a quello di user running.

A tal punto il kernel “sveglierà” il processo dallo stato asleep in modo tale che possa continuare la sua esecuzione. Nel caso particolare considerato in precedenza, in cui la richiesta è stata effettuata da una system call read(), i dati letti verranno copiati nello spazio utente all’indirizzo dato come parametro d’ingresso alla system call stessa.

Process Structure e U-Area

Immagine di un processo Unix

Scheduling in Unix

Obiettivo: privilegiare i processi interattivi.

• Scheduling feedback multilivello;
• ad ogni processo è associato un livello di priorità: più grande è il valore, più bassa è la priorità;
• Ad ogni livello è associata una coda, gestita con Round Robin;
• se un processo running non si blocca o termina in un secondo, viene revocato (preemption);
• priorità dinamiche, ricalcolate ogni secondo.

Calcolo della Priorità

E' basato sul tipo di processo e sulla storia di esecuzione

Linux Scheduler

Un utente può visualizzare/impostare solo il valore di nice.

Internamente, il kernel Linux distingue tra priorità statica e priorità dinamica dei task.

Priorità statica: determina la durata di un quanto di tempo assegnato ad un task.

Priorità dinamica: determina l’ordine di schedulazione (un task non esegue se altri task eseguibili hanno maggiore priorità statica).

Linux Scheduler

La priorità dinamica è fatta variare automaticamente dal kernel durante l’esecuzione.

La priorità dinamica è ottenuta aggiungendo o sottraendo un valore (bonus) alla priorità statica, calcolata in base al tempo medio di sleep del task:

• maggiore il tempo di sleep, maggiore il bonus.

Grazie alla priorità dinamica, il kernel può privilegiare i task I/O bound, e penalizzare quelli CPU bound.

Processi (task) e Thread in Linux

Il kernel di Linux non distingue tra thread e processo.

Un thread è un particolare tipo di processo che condivide delle strutture con altri processi (ad esempio, più processi con stessa tabella delle pagine).

Un flusso di esecuzione (task) è l’unità fondamentale di schedulazione per il kernel.

Ciascun task è identificato da un Process ID (PID).

Un gruppo di task correlati (un “processo” multithreaded nel senso classico) è identificato da un Thread Group ID (TGID).

Tipi di scheduling in Linux

Diversa schedulazione per task real-time e convenzionali.

Un task viene eseguito solo quando non ci sono altri task eseguibili con priorità maggiore.

• Ad esempio, finchè c’è almeno un task real-time eseguibile, i task convenzionali non sono mai schedulati.

I processi convenzionali sono gestiti con un’unica politica di schedulazione time-sharing (SCHED_NORMAL).

Scheduling real-time

Ciascun task può essere configurato per essere schedulato secondo una tra 2 politiche disponibili:

1. SCHED_FIFO: il task esegue finchè è eseguibile o rilascia volontariamente la CPU;

• può essere prelazionato soltanto da un task a maggiore priorità;

2. SCHED_RR: il task viene alternato periodicamente con altri task (round robin).

Tale scheduling non è hard real-time (nessuna garanzia è fornita sui tempi di schedulazione).

SCHED_FIFO e SCHED_RR

La funzione schedule()

Effettua la schedulazione del task (attivo) a maggiore priorità.
Se vi è un task a priorità maggiore di quello attuale, effettua il context switch.
Può essere invocata in diverse occasioni:

• quando scade il quanto di tempo di un task;
• quando viene attivato un task a priorità più alta;
• quando una system call termina;
• esplicitamente in apposite parti del kernel.

Effettua anche altri compiti di servizio (e.g., aggiornare la priorità, load balancing tra CPU)

Scheduler O(1) (kernel 2.6)

Obiettivi
Ottenere uno scheduling con overhead costante al variare del numero dei processi presenti nel sistema.

Utilizzare efficientemente le architetture SMP:

• ogni processore ha una propria coda di esecuzione;
• concetto di affinità SMP: processi affini vengono raggruppati su un singolo processore (group scheduling). La migrazione dei processi è prevista solo per motivi di bilanciamento del carico.

Scheduler O(1)

Il tempo impiegato per scegliere quale processo schedulare è costante, indipendentemente da quanti task ci sono nel sistema.

Il tempo per la scelta è lo stesso sia se ci sono 10 task sia se ci sono 1000 task in esecuzione.

Sviluppato per ottenere un buon grado di interattività ed equità allo stesso tempo.

Elevata scalabilità su sistemi SMP.

Priority array

A ciascun processore è associata una runqueue, ossia una lista di processi in attesa di essere eseguiti su quel processore.

Ogni runqueue ha 2 “priority array”, expired ed active.

Un elemento dell’array è una lista di processi a stessa priorità (140 liste in totale):

• Active: insieme dei task che non hanno ancora esaurito il quanto di tempo a loro assegnato;
• Expired: insieme dei task che hanno eseguito per un intero quanto di tempo.

Runqueues

L’algoritmo O(1)

Il sistema mantiene una matrice (map) di 140 (MAX_PRIO) bit, ognuno dei quali indica se esiste un processo in esecuzione con tale priorità.

Trovare la coda che contiene il processo a priorità più alta è davvero semplice: basta trovare il primo bit alto della matrice!

Una volta trovata la coda si seleziona il primo processo (FIFO).

Scheduler O(1)

Scheduler O(1)

Ogni volta che un task diviene eseguibile, il suo descrittore è collocato in coda alla relativa lista (in base alla priorità dinamica) dell’array active.

Quando un task deve essere schedulato, viene letto il descrittore in cima alla lista non vuota a maggior priorità.

Quando un task si blocca, esce dalla runqueue.

Queste operazioni non dipendono dal numero di task nel sistema.

Scheduler O(1)

Quando un task a maggior priorità diviene attivo, esso è inserito nella relativa lista ed il task corrente viene prelazionato
Quando un task esaurisce il quanto di tempo:

• il suo nuovo quanto di tempo viene precalcolato;
• Il descrittore è collocato in coda alla relativa lista (in base alla priorità dinamica) dell’array expired.

Quando tutti i task hanno esaurito il loro quanto di tempo, i puntatori ai 2 priority array vengono scambiati tra loro (expired <-> active).

Queste operazioni non dipendono dal numero di task nel sistema.

Load balancing in sistemi SMP

In Linux qualunque processore può eseguire qualunque task.

CPU affinity: se un task ha appena eseguito su un certo processore (cache-hot), è svantaggioso spostarlo su un altro processore.

Per ottenere un throughput elevato in un sistema SMP, è necessario che il numero di task in esecuzione sia equilibrato tra i vari processori.

I processi Windows 2000 (W2K)

W2K è un S.O. multithread, time-sharing.

Caratteristiche dei processi e thread W2K:

• i processi/thread W2K sono implementati secondo il paradigma object oriented:
  • ogni processo è un oggetto (kernel object) che offre stato e funzionalità agli utenti attraverso dei riferimenti (handle);
  • un processo contiene uno o più thread, che a loro volta sono dei kernel object.

La concorrenza è realizzata dai thread, per cui un processo W2K deve contenere almeno un thread per eseguire.

Risorse di un processo W2K

Stati dei Thread in W2K

Oggetti Process e Thread

Scheduling dei Thread in W2K

Politica di scheduling dei thread: intermedia tra la politica prioritaria e quella “round-robin”.
Ad ogni thread viene associata una priorità assoluta che varia tra 0 e 31.
Viene calcolata come somma di due componenti:

• una classe di priorità associata al processo a cui il thread appartiene;
• una priorità relativa del thread.

Ad ogni classe viene assegnato un valore numerico nominale.

Priorità

Classi di priorità di un processo (in ordine decrescente):

• Real-time (24): precedenza su ogni thread, da usare con cautela;
• High (13): precedenza sui thread delle classi inferiori, per applicazioni critiche (ad es. Task Manager);
• Above Normal (10): per i thread leggermente più prioritari del normale;
• Normal (8): maggiormente usato;
• Below Normal (6): per i thread leggermente meno prioritari del normale;
• Idle (4): i thread eseguono quando il sistema non ha altro da fare.

Priorità relative di un thread (in ordine decrescente):

• Time Critical: priorità uguale a 15 (31 se la classe è Real-time);
• Highest: +2 rispetto alla nominale (valore della classe);
• Above Normal: +1 rispetto alla nominale;
• Normal: si usa la priorità nominale;
• Below Normal: -1 rispetto alla nominale;
• Lowest: -2 rispetto alla nominale;
• Idle: priorità uguale a 1 (16 se la classe è Real-time).

Scheduling dei Thread in W2K

Per ogni livello di priorità, lo scheduler mantiene una coda gestita con Round Robin, con quanto 10 ms.

Lo scheduler esegue il primo thread della coda a priorità più alta che contiene almeno un thread pronto.

Il thread può eseguire fino a quando:

• il quanto temporale termina;
• il thread si sospende in attesa di un evento esterno;
• un thread a priorità più alta viene attivato.

In tutti e tre i casi, lo scheduler viene invocato nuovamente per scegliere il successivo thread.

Meccanismo del dynamic priority boost

Permette di ridurre il tempo di risposta dei thread interattivi.

All’attivazione di un thread sospeso:

• la sua priorità base viene aumentata di 2 punti;
• ad ogni quanto temporale, la sua priorità viene decrementata di un punto;
• in ogni caso la priorità del thread non può essere inferiore alla sua priorità base.

Supporto ai sistemi SMP

I thread di ogni processo, inclusi quelli dell’executive, possono eseguire su qualsiasi processore.

• Il microkernel assegna un thread ready al primo processore disponibile.

Il microkernel usa una policy nota come soft affinity:

• lo scheduler prova ad assegnare un thread ready allo stesso processore utilizzato in precedenza
• … al fine di riutilizzare le strutture dati del thread eventualmente ancora residenti nella cache del processore.