eMiage, Licence 3e anne, 2014-2015B208 - Systmes dExploitation

Devoir N.2Interblocage, Synchronisation et

OrdonnancementA rendre au plus tard le 10 mai 2015

Gilles Dequen

1 Synchronisation (7 points)Trois moines Shaolin mangent du riz pour prendre des forces avant de sen-

traner. Lorsquils ne mangent pas et quils nont pas faim, ils sentranent. Ilsont chacun leur bol de riz et une baguette. Cependant pour manger leur riz, ilsont besoin de deux baguettes.

En utilisant les smaphores, crire les programmes (pseudo-algorithmes) desprocessus symbolisants chacun des moines

2 Interblocages (Tanenbaum) (7 points)Dans un systme de transfert de fonds, il existe des centaines de processus

identiques qui fonctionnent de la manire suivante. Chaque processus lit uneligne de donnes qui indique une somme dargent, un compte crditer (c1pour lexemple) et un compte dbiter (c2 pour lexemple). Aprs cette lecture,il verrouille c1 puis c2, transfre largent puis finalement libre les verrous. Lenombre de processus en parallle tant important, il peut reproduire la situationsuivante.

Aprs avoir verrouill le compte c1, on peut ne pas pouvoir verrouiller c2 caril aura t verrouill par un autre processus qui lui mme est en attente de c1.Imaginez une mthode qui vite les interblocages.

Vous ne devez pas envisager la solution consistant relcher c1 immdiate-ment si c2 nest pas disponible. En dautres termes, un verrou doit tre relchuniquement si la transaction est complte.

1

3 Ordonnancement (7 points)5 processus, p1, p2, p3, p4 et p5 sont dans une file dattente dans cet ordre

(p1 est le premier, p5 est le dernier). Leur excution demande un temps total deservice exprim en units arbitraires

Table 1 lexemple

Processus temps de servicep1 4p2 1p3 2p4 5p5 1

Dcrire lexcution des processus dans le cadre des politiques dordon-nancement FIFO, SJF, RR (avec un quantum de 1).

Quelle est, de ces trois politiques, celle qui correspond un temps minimaldattente moyen par processus ?

2