Chapitre 2 Processus & Threads

Rim Moussa 2005-2006

Plan du chapitre

1. 2.

Processus Threads

3.
4.

Ordonnancement
Communication interprocessus

Processus

Un processus est une activit: programme, entres, sorties, tat Systmes monoprocesseurs: pseudo-paralllisme Multiprogrammation: basculement entre processus Crer un processus? linitialisation du systme, par un processus, requte utilisateur, job de trait par lots.
UNIX: fork cration dun clone et execve modifier limage du processus Windows: CreateProcess

Processus
Dmons (daemon) ou en arrire-plan, exples: courriers lectroniques, pages web Premier-plan

Les voir?
Ctrl+alt+del sur Windows ps sur UNIX

 Processus

Fin de Processus
Volontaire: arrt normal ou arrt pour erreur (le fichier compiler nexiste pas) Involontaire: arrt pour erreur fatale (division par 0) ou arrt par un autre processus (Unix: kill, Windows: TerminateProcess)

Hirarchie de Processus
Existe sous UNIX, arborescence de parent-enfants Nexiste pas sous Windows, CreateProcess retourne un HANDLE utilis pour contrler le processus

Implmentation de Processus
Processus possde son propre espace dadressage: programme, donnes, pile. Le changement de contexte (changement de processus) Table de processus, avec une entre/ processus contenant registres, identificateur, ptr vers le segment texte, ptr vers segment de donnes, ptr vers le segment de pile, tat
4

 Etats de Processus
En cours dexcution (1) Bloqu (3) (2) Prt

(4)
Le processus est bloqu, en attente dune donne, vnement Lordonnanceur choisit un autre processus Lordonnanceur choisit ce processus La donne devient disponible

Threads

Un processus possde un espace dadressage et un thread de contrle unique.

Un thread processus lger ou leightweight process inclut:

un compteur ordinal, qui effectue le suivi des instructions excuter des registres, qui dtiennent les variables en cours. une pile, qui contient lhistorique de lexcution.

Pour plus de performances, cas de threads lis aux E/Ss, dautres de traitement Multithreading: +sieurs threads dans le mme espace dadressage.
Etats dun thread: en cours dexcution, bloqu, prt ou arrt.

Procdures de bibliothque: thread_create, thread_exit, thread_wait, thread_yield (abandon volontaire de la CPU).

Temps de cration dun processus >> Temps de cration dun thread (100 )
6

 Trait de Texte multithreaded

Absbjshd Absbjshd Absbjshd Dnddjkjdq Dnddjkjdq Dnddjkjdq Hqdjlqdjl Hqdjlqdjl Hqdjlqdjl Jddmkm Jddmkm Jddmkm Djdlqjdjdq Djdlqjdjdq Djdlqjdjdq djdqkmkd djdqkmkd djdqkmkd

clavier Disque
noyau

Thread 1: remet en forme le document Thread 2: interaction avec lutilisateur Thread 3: crit priodiquement le contenu de la RAM sur le disque

 Serveur Web multithreaded

Les pages web les + consultes sont dans le cache. Dispatcher Thread Pool de worker threads Cache de pages web

Le dispatcher lit les requtes entrantes

Le worker vrifie le cache, sinon effectue un read sur le disque, donc devient bloqu sur une E/S Worker Dispatcher while (TRUE) { get_next_request(&buf); handoff_work(&buf); }

noyau

while (TRUE) { wait_for_work(&buf); look_for_page_in_cache(&buf, &page); if (page_not_in_cache(&page)) read_page_from_disk(&buf, &page); return_page(&page); }

8

 Implmentation de Threads
Soit dans lEspace Utilisateur ou dans le Noyau
Processus Espace user Thread Systme dexcution Table des threads Table des processus

noyau

Systme dexcution (runtime system): gre la table de threads, le basculement entre threads en cas dimplem en espace user est + rapide que celui en mode noyau. Implem en espace user: le processus a son propre algo dordonnancement entre les threads
9

Ordonnancement
Ordonnanceur (scheduler): partie du SE qui slectionne les processus.

Algo dordonnancement (scheduling algorithm)

- ~ non-premptif: slectionne un processus, puis le laisse sexcuter jusqu ce quil se bloque (E/S, wait) ou se termine. - ~ premptif: slectionne un processus et le laisse sexcuter pendant un quantum, premption par linterruption horloge Comportement de Processus: - Processus de traitement - Processus dE/S
10

Objectifs de lordonnancement
Tous les systmes
quit: attribuer chaque processus un temps CPU quitable

quilibre: toutes les parties du systme sont occupes

Systmes de traitement par lots

Capacit de Trait: optimiser le #jobs/ heure

Dlai de rotation: rduire le dlai entre la soumission et lachvement

Taux dutilisation du processeur

Systmes interactifs
Temps de rponse: rponse rapide aux requtes

Systmes temps rel

Respect des dlais: viter de perdre les donnes Prvisibilit: viter la dgradation de la qualit
11

 Algo dordonnancement
1er arriv, 1er servi (first come first served) Le job le plus court en premier (shortest job first)
Dlais dexcution connus

Shortest remaining time next Tourniquet (round robin)

Quantum court: trop de changement de contexte Quantum long: dgradation temps de rponse aux requtes interactives

Par Priorits
Prvenir contre les situations de famine en diminuant la priorit du processus chaque interruption ou priorit gale linverse de la fraction dutilisation du dernier quantum...

Par Tirage au Sort

12

 Ordonnancement 3 niveaux
Job entrant

Processeur
Ordonnanceur du processeur

File dattente

Disque

Mmoire Principale
1. O. dadmission: Mlange jobs E/S et CPU, shortest job first 2. O. de mmoire: processus en mmoire ou sur disque ? Niveau de
multiprogrammation?

3. O. du processeur: Slection des processus prts en mmoire celui qui va

sexcuter
13

Communication interprocessus
1. Conditions de Concurrence 2. Sections Critiques 3. Exclusion Mutuelle 4. Sommeil & Activation 5. Smaphores 6. Mutex 7. Moniteurs 8. Echange de Messages

9. Barrires

14

Conditions de Concurrence

Conditions de concurrence (race conditions): situation o 2 processus ou plus effectuent des lectures et des critures conflictuelles. Exemple du Spouleur dimpression
Un processus qui veut imprimer un fichier, entre son nom dans un rpertoire de spoule Le processus dmon dimpression regarde priodiquement sil y a des fichiers imprimer. Il a 2 variables: in: pointe vers la prochaine entre libre. out: pointe vers le prochain fichier imprimer in = 7, out = 4 A et B deux processus qui veulent imprimer un fichier A >> lire in, next_free_slot = 7 Interruption: la CPU bascule vers le processus B B >> lire in, next_free_slot = 7, entre7 = fichierB, in = 8 A >> entre7 = fichierA, in = 8 Problme: le fichierB ne sera pas imprim
15

 Conditions de Concurrence

Comment viter les conditions de concurrence?

Solution: Interdire que plusieurs processus lisent et crivent des donnes partages simultanment.
Exclusion Mutuelle: permet dassurer que si un processus utilise une variable ou fichier partags, les autres processus seront exclus de la mme activit

16

Les Sections Critiques

les Sections Critiques, mthode dexclusion mutuelle
A entre dans sa section critique A quitte sa section critique

A
B quitte sa section critique

t1

t2

t3

t4 B entre dans sa section critique

17

B tente dentrer dans sa section critique

LExclusion Mutuelle avec Attente Active (busy waiting)

Dsactivation des interruptions

Aprs son entre dans une SC, un processus dsactive les interruptions, puis les ractive Il empche ainsi lhorloge denvoyer des interruptions et le processeur de basculer Il est imprudent de permettre des processus user de dsactiver les interruptions

Variables de verrou (lock)

Avant dentrer en SC, tester la valeur de verrou, si verrou = 0, verrou 1, entrer en SC Dfaillance: 2 processus peuvent entrer simultanment dans leurs sections critiques comme le spouler dimpression

Alternance Stricte
la variable turn porte le numro du processus dont cest le tour dentrer en SC. Chaque processus inspecte la valeur de la variable, avant dentrer en SC. Inconvnient: consomme bcp de temps CPU
18

 Exclusion Mutuelle avec Attente Active (busy waiting)

Alternance Stricte
while (TRUE) { while (TRUE) { while (turn != 0); while (turn != 1); critical_region(); critical_region(); turn = 1; turn = 0; non_critical_region(); non_critical_region(); } } Les attentes actives sont performantes dans le cas o elles sont brves. En effet, il y a risque dattente P0 quitte la CS, turn = 1 P1 termine sa CS, turn = 0 Les 2 processus sont en section non critique P0 excute sa boucle, quitte la SC et turn = 1 Les 2 processus sont en section non critique P0 quoiquil a termin, il ne peut pas entrer en SC, il est bloqu
19

 Exclusion Mutuelle avec Attente Active (busy waiting)

Solution de Peterson: combinaison de variables verrou, de variables

davertissement sans alternance stricte.
#define FALSE 0 #define TRUE 1 #define N 2 // nombre de processus int turn; // qui le tour? int interested[N]; // initialement les valeurs sont false void enter_region (int process) { int other; other = 1 process; interested[process] = TRUE; turn = process; while (turn == process && interested[other] == TRUE); } void leave_region (int process) { interested[process] = FALSE; }
20

 Exclusion Mutuelle avec Attente Active (busy waiting)

Instruction TSL
solution qui ncessite de laide du matriel.

TSL acronyme de Test and Set Lock

Elle consiste en la lecture du contenu du mot mmoire Lock du registre RX, puis stocker dune valeur diffrente de 0 ladresse mmoire lock. Ces oprations sont indivisibles: le processeur excutant TSL verrouille le bus mmoire. enter_region: TSL REGISTER, LOCK | copie lock dans le registre et la dfinit 1 CMP REGISTER, #0 | tester si lock est gale 0 JNE enter_region | si elle est diffrente de 0 boucle RET | retour lappelant, entre en SC leave_region: MOVE LOCK, #0 | stocke un 0 dans lock RET | retour lappelant
21

Problme du consommateurproducteur

Connu aussi sous le nom de tampon dlimit (bounded buffer).

2 processus partagent un tampon commun de taille fixe N.

Le producteur place des jetons dans le tampon. Le consommateur rcupre un jeton Problme 1: le producteur souhaite placer un nouveau jeton alors que le tampon est plein. Problme 2: le consommateur souhaite rcuprer un jeton alors que le tampon est vide Count dnote le nombre de jetons dans le tampon

22

Sommeil & Activation

Ne consomme pas de la CPU comme lattente active Primitives de communication:

sleep: appel systme qui provoque le blocage de lappelant wake up: appel systme qui rveille un processus.

Problme du producteurconsommateur
#define N 100 int count = 0;

void producer (void) { int item; while (TRUE) { item = produce_item(); if (count == N) sleep(); insert_item(item); count++; if (count == 1) wakeup(consumer); } } void consumer (void) { int item; while (TRUE) { if (count == 0) sleep(); item = remove_item(); count--; if (count == N-1) wakeup(producer); consume_item(item); } }
23

 Sommeil & Activation

Problme de blocage:
Le consommateur note que le tampon est vide

Interruption: arrt du consommateur sans quil parte en sommeil

Le producteur insre un jeton, incrmente le dcompte, appelle wakeup pour rveiller le consommateur Le signal wakeup est perdu, car le consommateur nest pas en sommeil Le consommateur reprend, pour lui le tampon est vide, il dort Le producteur remplit le tampon et dort

Solution: ajouter un bit dattente dveil.

Quand un wakeup est envoy un processus le bit est 1;
le consommateur teste le bit, sil est 1, il le remet 0 et reste en veil Cette solution est + difficile gnraliser en cas de + sieurs processus.
24

Smaphores

Smaphore: # de wakeup enegistrs 2 oprations:

down: si la valeur de la variable smaphore est > 0, la dcrmenter; si la valeur est nulle: sleep up: incrmenter la valeur de la smaphore et rveiller au hasard un processus dormant down et up sont implmentes en tant que appels systme, le SE dsactive les interruptions, et cest ainsi que les oprations de vrification, de mj et de sommeil sexcutent de manire atomique

Problme du producteur-consommateur
3 smaphores: full, empty et mutex full: # demplacemens occups dans le tampon empty: # demplacements vides dans le tampon mutex: pour sassurer que le consommateur et le producteur naccdent pas simultanment au tampon
25

 Smaphores
#define N 100 Typedef int semaphore; semaphore mutex = 1; semaphore empty = N; semaphore full = 0; void producer (void) { int item; message m; while (TRUE) { item = produce_item(); down(&empty); down(&mutex); insert_item(item); up(&mutex); up(&full); } } void consumer (void) { int item; while (TRUE) { down(&full); down(&mutex); item = remove_item(&m); up(&mutex); up(&empty); consume_item(item); } }

26

Mutex
Smaphore dexclusion mutuelle, o la fonction dcompte nest pas ncessaire. Une mutex a 2 tats: dverrouill: valeur 0 ou verrouill Si +sieurs threads sont bloqus sur une mutex, lun dentre eux est choisi au hasard pour prendre possession du verrou. mutex_lock et mutex_unlock

mutex_lock: TSL REGISTER, MUTEX | copie mutex dans le registre et la dfinit 1 CMP REGISTER, #0 | tester si mutex est gale 0 JSE ok | si elle est diffrente de 0 retour CALL thread_yield | relcher la CPU ok: RET | retour lappelant mutex_unlock: MOVE MUTEX, #0 | stocke un 0 dans mutex RET | retour lappelant

! Comparer au code denter_region slide 17

27

Moniteurs

Collection de procdures, de variables, de structures de donnes regroupes dans un module. Un processus ne peut appeler que les procdures du moniteur. Les moniteurs sont des constructions de langage, et cest au compilateur dimplanter lexclusion mutuelle sur les entres du moniteur. Problme du producteur-consommateur
2 variables conditionnelles (vc): full et empty Quand une procdure du moniteur dcouvre quelle ne peut plus poursuivre, elle effectue un wait sur une vc Si un signal est adress une vc attendue, un processus est ractiv.

28

 Moniteurs
monitor ProducteurConsommateur condition full, empty; integer count; procedure insert (item: integer) begin if count = N then wait(full) insert_item(item); count++; if (count = 1) then signal(empty); end; function remove: integer begin if count = 0 then wait(empty); remove = remove_item; count--; if (count = N 1) then signal(full); end; count = 0; end monitor; procedure producteur begin while true do { item = produce_item; ProducteurConsommateur.insert(item); } end; procedure consommateur begin while true do { item = ProducteurConsommateur.remove; consume_item(item); } end;

29

Echange de Messages

Convient aux systmes distribus 2 primitives appels systmes: send et receive

send (destination, &message) receive (source, &message)

Problmes
Perte de messages dans le rseau, + de fiabilit par les ACKs, la retransmission de messages et la dtection de doublons

Problme du producteur-consommateur
Les messages mis et non encore reus sont mis en mmoire par le SE Le consommateur envoie N messages vides au producteur Le producteur remplit chaque message vide reu
30

Echange de Messages
#define N 100 void producer (void) { int item; message m; while (TRUE) { item = produce_item(); receive(consumer, &m); build_message(&m, item); send(consumer, &m); } } void consumer (void) { int item, i; for(i=0; i<N;i++) send(producer, &m); while (TRUE) { receive(producer,&m); item = extract_item(&m); send(producer, &m); consume_item(item); } }

Problme, si le producer travaille + vite que le consumer le producer envoie tous les messages pleins et reste bloqu en attente dun message vide.

31

Les Barrires

Mcanisme de synchronisation destin aux groupes de processus. Cas dapplications dcomposes en phases, o aucun processus ne

peut entrer dans la phase suivante tant que tous les processus ne sont
pas prts y entrer.

Solution: placer une barrire, et quand un processus atteint la barrire il est bloqu jusqu ce que tous les processus atteignent la barrire.

Barrire

Barrire

B C

B C

Barrire

B
C

32