IMA4 2017/2018 EC5

Présentation du projet

Contexte

L'élève continue son semestre S8 à l'école.

Objectif

Il vous est demandé d'écrire un programme C permettant de simuler l'ordonnancement de processus avec gestion de ressources communes suivant les algorithmes tourniquet et priorité avec préemption.

Description du projet

Vous commencerez par créer les structures de données pour pouvoir décrire, dans le code C, les processus que votre ordonnanceur va devoir gérer.

Les caractéristiques des processus à prendre en compte sont :

• un numéro permettant d'identifier les processus ;
• une date de départ du processus par rapport à une horloge globale ;
• les divers événements du processus par rapport à son horloge interne correspondant au temps passé en exécution :
  • réclamation d'une ressource commune ;
  • libération d'une ressource commune ;
  • terminaison du processus.

Un exemple de description de processus est donné ci-après.

int nb_procs=4;
struct event p1_events[]={ {30,OP_CLAIM,R1}, {70,OP_RELEASE,R1}, {100,OP_STOP} };
struct event p2_events[]={ {80,OP_CLAIM,R1}, {180,OP_RELEASE,R1}, {200,OP_STOP} };
struct event p3_events[]={ {40,OP_CLAIM,R1}, {160,OP_RELEASE,R1}, {300,OP_STOP} };
struct event p4_events[]={ {400,OP_STOP} };
struct process procs[]={
 {.number=1,.start=150,.priority=1,.events=p1_events},
 {.number=2,.start=100,.priority=2,.events=p2_events},
 {.number=3,.start=50,.priority=3,.events=p3_events},
 {.number=4,.start=0,.priority=4,.events=p4_events}
 };

Les caractéristiques des ressources à prendre en compte sont :

• un numéro permettant d'identifier les ressources ;
• le nombre d'occurrences de la ressource disponibles.

Pour simuler les deux algorithmes d'ordonnancement, vous utiliserez un algorithme "intelligent" :

• faites partir le temps de zéro puis rentrez dans une boucle infinie où le temps saute directement à l'événement suivant (arrivé d'un processus, événement pour le processus courant, fin du quantum de temps, etc) ;
• voyez si un nouvel événement se traduit par un changement d'état du processus courant et l'activation d'un autre processus ;
• si tous les processus sont terminés, sortez de la boucle.

A chaque événement imprimez un code permettant de suivre l'exécution :

• pour la réclamation ou la libération d'une ressource affichez le temps global, le caractére R comme ressource, son numéro et + ou - suivant qu'il s'agit d'une réclamation ou d'une libération ;
• pour le changement d'état d'un processus, affichez le temps global, le caractére P comme processus, son numéro et [ ou ] suivant qu'il s'agit de l'activation ou de la mise en sommeil du processus.

Pour chaque simulation lancez les deux algorithmes d'ordonnancement. Vérifiez votre programme avec les différents exercices d'ordonnancement des DS de système des années passées.

Une fois le programme fonctionnel étudiez les différentes variantes possibles pour les deux algorithmes. Par exemple pour le tourniquet, le quantum de temps est-il ou non prioritaire sur une opération sur une ressource qui est programmée au même instant ? Par exemple pour la priorité avec préemption, comment choisir entre des processus avec la même priorité ?

Travail effectué

Le début de travail à été de créer les différentes structures afin de pouvoir construire l'ordonnancement.

On a pu différencier 3 structures différentes : Celle de la ressource, celle du processus et celle d'un événement.

Les structures sont les suivantes :

struct ressource
{
   int num_ressource;
   int nb_occurence;
};
typedef struct ressource Ressource;

struct event
{
   int demande;
   int action;
   Ressource R;
};
typedef struct event Event;

struct process
{
   int number;
   int start;
   int priority;
   int nbEvent;
   Event* event;
};
typedef struct process Process;

Une fois celle ci définit, il a donc fallu créer un ordonnancement par tourniquet dans un premier temps, puis dans un second temps par priorité avec préemption.

Afin de réaliser ces ordonnancement, j'ai repris les événements et les processus du Ds du 6 janvier 2017.

Une fois cette étapes de retranscription finie il a fallu créer les fonctions utile au déroulement de l'ordonnancement : afin que celui ci se rapproche au plus près de la réalité, j'ai établie les règles suivantes :

• Un temps de switch era mis en place afin qu'il existe un temps de battement entre les changements de processus.
• Si deux processus démarre en même temps, c'est le premier arrivé dans le programme qui s'exécutera.
• Un temps de switch et de quantum sera demandé au début du programme.

Pour le second, si un processus en cours, demande de prendre la main alors qu'il a une priorité égale, la demande sera rejetée.

Réponse aux questions : Le quantum de temps est-il ou non prioritaire sur une opération sur une ressource qui est programmée au même instant ? Dans mon programme, avant de commencer une opération qui demandera une ressource quelconque il est observé si le quantum de temps se termine. En effet si l'inverse était fait, un processus pourrait prendre un ressource sans l'utiliser. Si celle est demandé dans le future elle ne pourra pas être utilisé. Je pense donc que la priorité doit être donné au quantum et non à l'opération.

Pour la priorité avec préemption, comment choisir entre des processus avec la même priorité ?

Pour choisir entre deux processus ayant la même priorité, il existe plusieurs solution : soit le premier arrivé reste tant qu'il n'est pas fini, soit on compare le temps restant pour chacun d'entre eux et l'on prend celui dont le temps restant est le plus court afin de libérer au plus vite les ressources.

Sources

Les principales sources ont été celles données au début du rattrapage ainsi que le cours de système et de temps réel du semestre 7.

Documents

Fichier:Rattrapage système.zip