Contrôle périodique du cours INF3600

Ce contrôle périodique du cours INF3600 porte sur les systèmes d’exploitation. Il évalue les compétences en création de processus UNIX, ordonnancement des processus avec l'algorithme du tourniquet sur un système multiprocesseur, ainsi qu'en synchronisation de processus à l'aide de sémaphores dans un contexte de tampons partagés.

Question 1 : Création de processus (appels système UNIX)

Cette question aborde les avantages et inconvénients de la création de processus par duplication sous UNIX, les caractéristiques des processus légers (threads), ainsi qu'un programme d'illustration en C/C++.

1) Avantage et inconvénient de la duplication de processus sous UNIX

Avantage : La duplication facilite la création de processus exécutant le même programme, car le processus fils hérite de l’état du père.

Inconvénient : Elle complique la création de processus exécutant des programmes différents, car il faut ensuite remplacer l’image mémoire du fils (avec exec).

2) Avantages des processus légers (threads) par rapport aux processus classiques

• Meilleur partage des ressources (mémoire, fichiers ouverts, etc.) entre threads du même processus.
• Gain en temps et en espace, car la création et la commutation de threads sont plus rapides et consomment moins de ressources que celles des processus.
• Meilleure réactivité, notamment pour les applications interactives ou concurrentes.

3) Programme C/C++ pour la recherche parallèle dans le fichier COURS

Le programme crée quatre processus fils, chacun appelant la fonction Recherche sur une partie différente du fichier. Chaque fils retourne 0 en cas de succès (mot trouvé) et 1 sinon. Le père attend les fils et, dès qu’un fils réussit, il tue les autres.

int main ()
{
    int pid[4], status, x;
    for (int i=0; i<4; i++)
    {
        // création du (i+1)ième fils
        if ((pid[i] = fork()) == 0)
        {
            if (Recherche("COURS", "INF3600", i+1))
                exit(0);
            else
                exit(1);
        }
    }
    while ((x = wait(&status)) > 0)
    {
        if (status >> 8 == 0) // succès d’un fils
        {
            for (int i=0; i<4; i++)
                if (pid[i] != x)
                    kill(pid[i], SIGKILL);
            exit(0);
        }
    }
    exit(1);
}

Réponse finale : Le programme ci-dessus réalise la création des quatre fils, la recherche parallèle, la récupération des résultats via wait, et la terminaison des fils restants dès qu’un succès est détecté.

Question 2 : Ordonnancement des processus

Cette étude analyse un système multiprocesseur composé de deux CPU et d'une unité d'E/S, fonctionnant selon l'algorithme du tourniquet avec un quantum de 3 unités de temps.

1) Problèmes liés à la présence de pointeurs identiques dans la file des prêts

• La file peut contenir un pointeur vers un processus déjà terminé, ce qui est incohérent car ce processus ne doit plus être planifié.
• La file peut contenir un pointeur vers un processus bloqué, ce qui est incorrect car un processus bloqué ne doit pas se trouver dans la file des prêts.

2) Diagrammes de Gantt et évolution des files

Description des besoins en ressources des processus A, B et C :

Processus	Instant d’arrivée	Temps d’exécution
A	0	4 unités CPU, 2 unités E/S, 2 unités CPU
B	2	3 unités CPU, 4 unités E/S, 2 unités CPU
C	3.5	5 unités CPU

Règles de priorité pour la gestion des événements simultanés :

• CPU1 a priorité d’accès à la file des processus prêts sur CPU2.
• À la fin d’un quantum, le processus en cours est suspendu uniquement si la file des prêts n’est pas vide.
• Priorité d'exécution : Traitement de fin de quantum > fin d’E/S > arrivée de nouveaux processus.

Planification sur les processeurs et l'unité d'E/S :

• CPU1 : (0,A,4) puis (4,C,7) puis (7,C,9) puis (10,B,12)
• CPU2 : (2,B,5) puis (6,A,8)
• File des prêts : (3.5,C) puis (4,vide)
• Unité d’E/S : (4,A,6) puis (6,B,10)
• File d’attente E/S : (5,B) puis (6,vide)

3) Calcul du temps moyen de virement (temps moyen de séjour)

Le temps de virement (TV) correspond à la durée écoulée entre l'arrivée du processus et sa fin d'exécution :

• TV(A) = 8 - 0 = 8
• TV(B) = 12 - 2 = 10
• TV(C) = 9 - 3.5 = 5.5

Le temps moyen de virement (TVM) est obtenu par la formule :

TVM = (8 + 10 + 5.5) / 3 = 23.5 / 3 ≈ 7.83

Note : La valeur arrondie à 7.8 dans l'énoncé source correspond aux calculs de l'évaluation.

Réponse finale : Le temps moyen de virement est environ 7.83 unités de temps.

Question 3 : Synchronisation de processus

Cette section traite de la synchronisation de trois processus P0, P1 et P2 communicant via deux tampons partagés T0 et T1 de taille N. P0 traite des messages puis les place dans T0, P1 transfère de T0 à T1, et P2 lit T1 pour envoyer les messages.

1) Utilisation des sémaphores pour la gestion des tampons partagés

Afin d'assurer l’exclusion mutuelle et d'éviter les interblocages lors des accès aux tampons, la solution repose sur :

• Deux sémaphores d'exclusion mutuelle, mutex0 et mutex1 (initialisés à 1), pour sécuriser respectivement l'accès aux tampons T0 et T1.
• Quatre sémaphores de comptage pour contrôler l'état des tampons :
  • Vide0 et Vide1 (initialisés à N) pour compter le nombre de cases libres.
  • Plein0 et Plein1 (initialisés à 0) pour compter le nombre de cases occupées.

2) Pseudocodes des processus P0, P1 et P2

Semaphore
mutex1 = 1, mutex0 = 1, Vide0 = N, Vide1 = N, Plein0 = 0, Plein1 = 0;

P0
Message m, mc;
int ip = 0;
Répéter
{
    m = lire();               // Lecture d’un message clavier
    mc = Encrypter(m);       // Traitement (encryption)
    P(Vide0);                // Attente tampon T0 non plein
    P(mutex0);               // Exclusion mutuelle sur T0
    T0[ip] = mc;             // Dépôt dans T0
    V(mutex0);               // Libération mutex0
    ip = (ip + 1) mod N;     // Avancement de l’indice circulaire
    V(Plein0);               // Signal tampon T0 non vide
}

P1
int icp = 0;
Répéter
{
    P(Plein0);               // Attente tampon T0 non vide
    P(Vide1);                // Attente tampon T1 non plein
    P(mutex0);               // Exclusion mutuelle sur T0
    P(mutex1);               // Exclusion mutuelle sur T1
    T1[icp] = T0[icp];       // Transfert de T0 vers T1
    V(mutex1);               // Libération mutex1
    V(mutex0);               // Libération mutex0
    icp = (icp + 1) mod N;   // Avancement de l’indice circulaire
    V(Plein1);               // Signal tampon T1 non vide
    V(Vide0);                // Signal tampon T0 non plein
}

P2
Message mc;
int ic = 0;
Répéter
{
    P(Plein1);               // Attente tampon T1 non vide
    P(mutex1);               // Exclusion mutuelle sur T1
    mc = T1[ic];             // Lecture du message dans T1
    V(mutex1);               // Libération mutex1
    ic = (ic + 1) mod N;     // Avancement de l’indice circulaire
    V(Vide1);                // Signal tampon T1 non plein
    Envoyer(mc);             // Envoi du message
}

Réponse finale : Les pseudocodes ci-dessus mettent en œuvre la gestion synchronisée des tampons partagés en évitant les conditions de course et les risques d'interblocage.

Méthode : techniques récompensées et erreurs pénalisées

• Respect strict des conventions du sujet : Utiliser la notation, les définitions et les conventions données, notamment pour les codes de retour (exit(0) succès, exit(1) échec) et les priorités d’ordonnancement.
• Travail pas à pas : Montrer clairement les étapes de raisonnement, notamment dans le calcul des temps et la gestion des files d’attente, plutôt que de donner directement la réponse.
• Précision dans la synchronisation : Employer correctement les sémaphores pour l’exclusion mutuelle et la gestion des tampons, en respectant les sémaphores Plein et Vide.
• Attention aux détails d’implémentation : Par exemple, dans le code C, ne pas oublier les boucles, les tests de retour, et la gestion des signaux pour tuer les processus.
• Gestion des priorités et événements simultanés : Appliquer rigoureusement les règles de priorité données pour l’ordonnancement et les interruptions.
• Erreurs pénalisées : Omettre des étapes intermédiaires, confondre les sémaphores, ignorer la gestion des processus bloqués ou terminés dans la file, ou ne pas respecter les conventions de retour des fonctions.