Exercice 1

Chacun des programmes en cours d’exécution d’un système multitâche est associé à une lettre majuscule de l’alphabet. Les temps d’exécution prévus sont donnés par les suites de lettres "AAAAAAAAA", "BBBB", "CCC" ; ainsi, par exemple, l’exécution complète du programme "B" nécessite quatre unités de temps.

La série de lettres "ABAAAABAACABCACB" indique l’utilisation des unités de temps du processeur.

Dans cet exemple, le programme "A" démarre en premier puis le programme "B" est activé; ensuite, le programme "A" poursuit son exécution pendant quatre unités de temps, etc. Chaque programme démarre au moment de la première apparition de sa lettre et attend tant qu’il n’est pas terminé et qu’un autre programme est actif.

Dans l’exemple précédent, combien de temps les trois programmes ont-ils attendu au total (unités de temps) – en justifiant votre approche de calcul ?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 15 16 AttenteA

B

C

Exercice 2 Soit TS le temps de service d'un travail (job), c'est à dire le temps écoulé entre la soumission du travail et sa fin. On considère un système de traitement séquentiel (batch) dans lequel quatre travaux arrivent dans l'ordre suivant :

N° du JOB     Instant d'arrivée         Durée           1                 0                                  8           2                 1                                  4           3                 2                                  9           4                3                                 5      a- Donner le TS moyen dans le cas où l'on adopte la politique

PAPS (Premier Arrivé, Premier Servi, ou encore FCFS, Fist Come Fisrt Served)

b- Donner le TS moyen dans le cas où l'on adopte la politique préemptive : PCA (le plus court d'abord, ou encore SJF, Shortest Job First)

Exercice   3   (Quantum de temps) Dans le cas de la stratégie d'allocation du processeur avec recyclage (algorithme du tourniquet, ou encore algorithme du quantum de temps), indiquer quels sont les effets des choix suivants pour le quantum q, sachant que s est le temps de changement de contexte et que t est le temps moyen d'utilisation du processeur entre deux événements bloquants (t >> s  et [epsilon] << s) :

1. q = [infini]2. q = [epsilon]3. q = s4. q = t5. s < q <t6. q > t

Pour chaque question, étudier les cas où s compris dans le quantum ou non.

Exercice 4Un processeur a une vitesse de traitement de 0,5 Mips. Sa politique d'ordonnancement est RR avec un quantum q. q est très inférieur au temps de service S (q<<S). On a un débit d'entrée de 1,5 programme/s et chaque programme correspond en moyenne à 100000 instructions.

1. Combien y a t-il, en moyenne, de programmes dans le système (en attente et en exécution)?

2. Quel est le temps de passage d'un programme

Un petit problème

Calculer les temps d'attente moyen ainsi que le temps de rotation moyen pour chaque scénario.

Réponse de l’exercice 3 :1.      Le processus garde le processeur tant qu'il en a besoin (comme FCFS,Fist Come Fisrt Served ),2.      Le processus ne fait presque rien entre chaque changement de contexte, progression très lente.

Si s est compté dans q, aucun processus n'est exécuté.3.      Si s est compris dans q, il ne se passe rien, sinon exécution pendant au plus s,4.      Le quantum a tendance à favoriser les processus orientés entrées-sorties,5.      Le quantum est quelconque,6.      Le quantum favorise les processus qui ne font que du calcul.

Rappels sur les algorithmes d’ordonnancement

FCFS (First Come First Serve), premier arrivé premier servi.

Dans un système à ordonnancement non préemptif ou sans réquisition, le système d'exploitation choisit le prochain processus à exécuter, en général, le Premier Arrivé est le Premier Servi PAPS (ou FCFS First-Come First-Served) ou le plus court d'abord ( SJF Short Job First). Il lui alloue le processeur jusqu'à ce qu'il se termine ou il se bloque (en attente d'un événement). Il n'y a pas de réquisition.

SJF (Short Job First), plus court d'abord

Si l'ordonnanceur fonctionne selon la stratégie SJF, il choisit parmi le lot de processus à exécuter, le plus court d'abord (plus petit temps d'exécution). Cette stratégie est bien adaptée au traitement par lots de processus dont les temps maximaux d'exécution sont connus ou fixés par les utilisateurs car elle offre un meilleur temps moyen de séjour. Le temps de séjour d'un processus (temps de rotation ou de virement) est l'intervalle de temps entre la soumission du processus et son achèvement.

SRT (Shortest Remaining Time), plus petit temps de séjour

L'ordonnancement du plus petit temps de séjour ou Shortest Remaining Time est la version préemptive de l'algorithme SJF. Un processus arrive dans la file de processus, l'ordonnanceur compare la valeur espérée pour ce processus contre la valeur du processus actuellement en exécution. Si le temps du nouveau processus est plus petit, il rentre en exécution immédiatement.

RR (Round Robin), algorithme circulaire

L'algorithme du tourniquet, circulaire ou round robin est un algorithme ancien, simple, fiable et très utilisé. Il mémorise dans une file du type FIFO (First In First Out) la liste des processus prêts, c'est à dire, en attente d'exécution. Il alloue le processeur au processus en tête de file, pendant un quantum de temps. Si le processus se bloque ou se termine avant la fin de son quantum, le processeur est immédiatement alloué à un autre processus (celui en tête de file). Si le processus ne se termine pas au bout de son quantum, son exécution est suspendue. Le processeur est alloué à un autre processus (celui en tête de file). Le processus suspendu est inséré en queue de file. Les processus qui arrivent ou qui passent de l'état bloqué à l'état prêt sont insérés en queue de file.

PRI (Priorités, sans évolution)

L'ordonnanceur à priorité attribue à chaque processus une priorité. Le choix du processus à élire dépend des priorités des processus prêts. Les processus de même priorité sont regroupés dans une file du type FIFO. Il y a autant de files qu'il y a de niveaux de priorité. L'ordonnanceur choisit le

processus le plus prioritaire qui se trouve en tête de file. En général, les processus de même priorité sont ordonnancés selon l algorithme du tourniquet.