On considère un système monoprocesseur dans lequel les processus partagent un disque comme seule ressource (autre que le processeur). Cette ressource n'est accessible qu'en accès exclusif et non requérable, c'est-à-dire qu'une commande disque lancée pour le compte d'un processus se termine normalement avant de pouvoir en lancer une autre. Un processus peut être en exécution, en attente d'entrée-sortie ou en attente du processeur.

A- Expliquer le schéma suivant représentant les états possibles d'un processus et les transitions entre ces états. Expliquer pourquoi certaines transitions ne sont pas possibles.

B- En fait l'état bloqué se divise en deux états : attente de la ressource disque et attente de la fin d'exécution de l'opération. Les demandes d'entrées-sorties sont gérées à l'ancienneté, et l'allocation du processeur est faite selon la priorité affectée au processus, et représentée par une valeur entière. Le processus prioritaire est celui qui a la plus grande valeur et si deux processus ont même priorité, c’est le plus ancien dans la file d’attente des processus prêts.

Nous considérons les 4 processus dont le comportement est le suivant (la priorité au démarrage est indiquée entre parenthèses) :

P1	(100)	Calcul pendant 40 ms 
			Lecture disque pendant 50 ms
			Calcul pendant 30 ms
			Lecture disque pendant 40 ms
			Calcul pendant 20 ms
P2	(99)	Calcul pendant 30 ms 
			Lecture disque pendant 80 ms
			Calcul pendant 80 ms
			Lecture disque pendant 20 ms
			Calcul pendant 10 ms
P3	(98)	Calcul pendant 40 ms
			Lecture disque pendant 40 ms
			Calcul pendant 10 ms
P4	(97)	Calcul pendant 80 ms 

B.1- Les 4 processus sont lancés en même temps et gardent leur priorité initiale pendant toute leur exécution. Établir le chronogramme des 4 processus sur le diagramme suivant. Vous noircirez les cases correspondant à l'état du processus, comme cela a été fait pour le début du processus P1, à titre d'exemple.

P1

P2

P3

P4

B.2- Les 4 processus sont lancés en même temps, mais leur priorité est variable. Chaque fois qu'un processus quelconque quitte l'état bloqué, on recalcule la priorité de chaque processus selon la formule suivante :

Priorité Nouvelle = Priorité Initiale - (Temps processeur utilisé) / 10

Établir le chronogramme des 4 processus sur le diagramme suivant.

P1

P2

P3

P4

C- Donner le temps total de l’exécution de ces 4 processus dans les trois cas suivants :

C1 L'activation des 4 processus est demandée à l'instant initial et ils s'exécutent en monoprogrammation dans l'ordre P1, P2, P3 puis P4,

C2 Gestion de B.1,

C3 Gestion de B.2.

D- Comparer les temps de réponse moyens dans les trois cas C1, C2, C3

E- Donner le taux d’utilisation du processeur dans les 3 cas C1, C2 et C3

Un processus peut se trouver dans différents états, suivant qu'il dispose de tout ou partie des ressources dont il a besoin pour s'exécuter. On distingue la ressource processeur de l'ensemble des autres ressources. En effet, s'il manque une ressource autre que le processeur, celui-ci ne peut faire évoluer le processus et il est donc inutile que cette ressource chère lui soit allouée. Lorsqu'il manque à un processus une ressource autre que le processeur, il est dans l'état bloqué. Lorsqu'un processus a toutes ses ressources à l'exception du processeur, il est dans l'état prêt. Enfin lorsqu'un processus a toutes ses ressources, y compris le processeur, il est dans l'état actif. L'allocation du processeur consiste à choisir un processus dans l'état prêt, et à lui allouer le processeur, le faisant passer dans l'état actif (transition 3). Un processus actif peut perdre le processeur, et repasser dans l'état prêt lorsque le système désire allouer le processeur à un autre processus (transition 2). Lorsqu'un processus actif demande une ressource qui n'est pas disponible, il passe dans l'état bloqué, et le processeur lui est retiré (transition 1). Lorsque la ressource demandée par un processus devient disponible, elle peut lui être allouée; le processus a alors toutes ses ressources sauf la ressource processeur et passe donc dans l'état prêt (transition 4).

Le processus est dans l'état bloqué lorsqu'il n'a pas toutes ses ressources, à l'exception de la ressource processeur. Pour passer dans cet état, il faut qu'il lui manque une ressource, soit parce qu'on la lui a retiré, ce qui n'est pas prévu ici, soit parce qu'il exprime un nouveau besoin, ce qui implique qu'il dispose du processeur pour exprimer ce besoin, c'est-à-dire qu'il soit actif. En conséquence, la seule transition vers l'état bloqué ne peut venir que de l'état actif. Par ailleurs, un processus quitte l'état bloqué lorsqu'il a toutes ses ressources pour s'exécuter, à l'exception de la ressource processeur, ce qui interdit la transition directe de bloqué à actif.

Le chronogramme d'exécution des 4 processus est donné ci-après. Les 4 processus sont initialement prêts. P1 ayant la priorité la plus grande est le premier processus actif jusqu'au temps 40, où son entrée-sortie est lancée, pour une durée de 50, c'est-à-dire jusqu'en 90. P2 devient alors actif. Au temps 70, P2 est bloqué en attente du disque et P3 devient actif.

Au temps 90, la demande d'entrée-sortie de P1 se termine et celui-ci redevient prêt. La priorité de P1 étant maximale, P1 redevient donc actif. En même temps, le disque étant libre, l'entrée-sortie de P2 est lancée, pour une durée de 80, c'est-à-dire jusqu'en 170. Au temps 120, P1 se bloque en attente du disque. P3, de priorité maximale, redevient actif jusqu'au temps 140, où il se bloque en attente du disque (derrière P1). P4 étant le seul processus prêt devient actif.

P1

P2

P3

P4

Au temps 170, l'entrée-sortie de P2 se termine, permettant à ce processus de redevenir prêt, en même temps que l'entrée-sortie suivante de la file, c'est-à-dire celle de P1, est lancée, pour une durée de 40, c'est-à-dire jusqu'en 210. La priorité de P2 étant maximale, P2 devient actif.

Au temps 210, l'entrée-sortie de P1 se termine permettant à ce processus de redevenir prêt, en même temps que l'entrée-sortie de P3 est lancée, pour une durée de 20, c'est-à-dire jusqu'en 230. La priorité de P1 étant maximale, P1 redevient actif jusqu'à son achèvement au temps 230.

Au temps 230, l'entrée-sortie de P3 se termine permettant à ce processus de redevenir prêt. La priorité de P2 étant maximale, P2 redevient actif jusqu'au temps 270, où son entrée-sortie est lancée, pour une durée de 20, c'est-à-dire jusqu'en 290. P3 devient actif jusqu'à son achèvement en 280. P4 étant seul processus prêt devient actif.

Au temps 290, l'entrée-sortie de P2 se termine permettant à ce processus de redevenir prêt. La priorité de P2 étant maximale, P2 redevient actif jusqu'à son achèvement en 300. P4, seul processus restant, redevient actif jusqu'à son achèvement en 340.

Le chronogramme d'exécution des 4 processus est donné ci-après. Le début est similaire au cas précédent. Les 4 processus sont initialement prêts. P1 ayant la priorité la plus grande est le premier processus actif jusqu'au temps 40, où son entrée-sortie est lancée, pour une durée de 50, c'est-à-dire jusqu'en 90. P2 devient alors actif. Au temps 70, P2 est bloqué en attente du disque et P3 devient actif.

Au temps 90, la demande d'entrée-sortie de P1 se termine et celui-ci redevient prêt. La priorité de P1 est alors 100-4=96, celle de P3 est 98-2=96 et celle de P4 est 97. P4 devient donc actif. En même temps, le disque étant libre, l'entrée-sortie de P2 est lancée, pour une durée de 80, c'est-à-dire jusqu'en 170.

Au temps 170, d'une part P4 est achevé, d'autre part l'entrée-sortie de P2 se termine, et P2 redevient prêt. La priorité de P2 est alors 99-3=96. Les 3 processus P1, P2, P3 ont la même priorité, mais P3 est le plus ancien de la file; il devient actif, jusqu'au temps 190, où son entrée-sortie est lancée, pour une durée de 40, c'est-à-dire jusqu'en 230. Les deux processus prêts ayant même priorité (96) le plus ancien de la file, c'est-à-dire P1, devient actif. Au temps 220, P1 se bloque en attente du disque et P2, seul processus prêt, devient actif.

Au temps 230, l'entrée-sortie de P3 se termine, permettant le lancement de celle de P1, pour une durée de 40, c'est-à-dire jusqu'en 270. P3 redevient actif avec la priorité 98-4=94. La priorité de P2 à ce moment est 99-4=95. Le processus P2 reste actif.

Au temps 270, l'entrée-sortie de P1 se termine et P1 redevient actif. La priorité de P1 est alors 100-7=93, celle de P2 est 99-8=91 et celle de P3 est 98-4=94. P3 devient actif jusqu'à son achèvement en 280. P1 étant alors le plus prioritaire devient actif jusqu'à son achèvement au temps 300. P2 restant seul peut achever ses activités.

P1

P2

P3

P4

En monoprogrammation, le temps total est la somme des temps processeurs et entrées-sorties de chaque processus. Or P1 dure 180 ms, P2 dure 220 ms, P3 dure 90 ms et P4 dure 80 ms. Le temps total d'exécution dans le cas C1 est donc de 570 ms.

Dans le cas B1 où l'allocation processeur est à priorité fixe, on constate que le dernier processus à se terminer est P4, donnant une durée totale de 340 ms.

Dans le cas B2 où l'allocation processeur est à priorité variable, on constate que le dernier processus à se terminer est P2, donnant une durée totale de 360 ms.

Le temps de réponse pour un processus est le temps qui sépare le moment où le processus est fourni au système du moment de la fin de son exécution. Dans nos hypothèses, les 4 processus sont toujours fournis à l'instant 0, mais ils se terminent plus ou moins tôt.

Constatons sur ce tableau que le temps de réponse moyen est plus fort dans le cas C1 que dans les autres cas. Notons que le temps de réponse pour P4 est nettement amélioré dans la gestion à priorité variable par rapport à la gestion à priorité fixe, au détriment des temps de réponse de P1 et P2.

Le taux d'utilisation processeur est le rapport entre la durée d'utilisation effective du processeur par l'un des processus et la durée totale d'exécution. Le temps total d'utilisation du processeur étant de 340 ms, on voit donc que le cas C1 donne un taux d'occupation du processeur de 60%, le cas C2 un taux de 100% et le cas C3 un taux de 94%.

En analysant les chronogrammes, on constate que le cas C2 permet d'obtenir un taux d'occupation de 100% du processeur parce que le processus P4 qui ne fait aucune entrée-sortie a la priorité la plus faible. Il sert donc de "bouche-trou". L'inconvénient est immédiat : c'est l'allongement du temps de réponse pour ce processus.