Exercices type bac : processus

Exercice 1 — Métropole 2021 (4 points)

Cet exercice porte sur les systèmes d’exploitation : gestion des processus et des ressources.

Les parties A et B peuvent être traitées indépendamment.

Partie A

Dans un bureau d’architectes, on dispose de certaines ressources qui ne peuvent être utilisées simultanément par plus d’un processus, comme l’imprimante, la table traçante, le modem.

Chaque programme, lorsqu’il s’exécute, demande l’allocation des ressources qui lui sont nécessaires. Lorsqu’il a fini de s’exécuter, il libère ses ressources.

Programme 1 :

demander (table traçante)
demander (modem)
exécution
libérer (modem)
libérer (table traçante)

Programme 2 :

demander (modem)
demander (imprimante)
exécution
libérer (imprimante)
libérer (modem)

Programme 3 :

demander (imprimante)
demander (table traçante)
exécution
libérer (table traçante)
libérer (imprimante)

On appelle p1, p2 et p3 les processus associés respectivement aux programmes 1, 2 et 3.

1. Les processus s’exécutent de manière concurrente. Justifier qu’une situation d’interblocage peut se produire.
2. Modifier l’ordre des instructions du programme 3 pour qu’une telle situation ne puisse pas se produire. Aucune justification n’est attendue.
3. Supposons que le processus p1 demande la table traçante alors qu’elle est en cours d’utilisation par le processus p3. Parmi les états suivants, quel sera l’état du processus p1 tant que la table traçante n’est pas disponible :
   • a) élu ;
   • b) bloqué ;
   • c) prêt ;
   • d) terminé.

Partie B

Avec une ligne de commande dans un terminal sous Linux, on obtient l’affichage suivant :

UID    PID  PPID C STIME TTY   TIME     CMD
...
pi    6211   831 8 09:07 ?  00:01:16 /usr/lib/chromium-browser/chromium-browser-v7 ...
pi    6252  6211 0 09:07 ?  00:00:00 /usr/lib/chromium-browser/chromium-browser-v7 --type=zygote ...
pi    6254  6252 0 09:07 ?  00:00:00 /usr/lib/chromium-browser/chromium-browser-v7 --type=zygote ...
pi    6294  6211 4 09:07 ?  00:00:40 /usr/lib/chromium-browser/chromium-browser-v7 --type=gpu-process ...
pi    6300  6211 1 09:07 ?  00:00:16 /usr/lib/chromium-browser/chromium-browser-v7 --type=utility ...
pi    6467  6254 1 09:07 ?  00:00:11 /usr/lib/chromium-browser/chromium-browser-v7 --type=renderer ...
pi   12835   836 0 09:13 ?  00:00:00 /usr/lib/libreoffice/program/oosplash ...
pi   12073 12835 2 09:13 ?  00:00:15 /usr/lib/libreoffice/program/soffice.bin ...
pi   12253   831 1 09:13 ?  00:00:07 /usr/bin/python3 /usr/bin/sense_emu_gui
pi   20029  6254 56 09:21 ?  00:00:28 /usr/lib/chromium-browser/chromium-browser-v7 --type=renderer ...
pi   20519   676 0 09:22 pts/0  00:00:00 ps -ef

La documentation Linux donne la signification des différents champs :

• UID : identifiant utilisateur effectif ;
• PID : identifiant de processus ;
• PPID : PID du processus parent ;
• C : partie entière du pourcentage d’utilisation du processeur ;
• STIME : l’heure de lancement du processus ;
• TTY : terminal de contrôle ;
• TIME : temps d’exécution ;
• CMD : nom de la commande du processus.

1. Parmi les quatre commandes suivantes, laquelle a permis cet affichage ?

   • a) ls -l
   • b) ps -ef
   • c) cd ..
   • d) chmod 741 processus.txt

2. Quel est l’identifiant du processus parent à l’origine de tous les processus concernant le navigateur Web (chromium-browser) ?

3. Quel est l’identifiant du processus dont le temps d’exécution est le plus long ?

demander (table traçante)
demander (imprimante)
exécution
libérer (imprimante)
libérer (table traçante)

Exercice 2 — Amérique du Nord 2022 (4 points)

Cet exercice porte sur les systèmes d’exploitation et la gestion des processus par un système d’exploitation.

Cet exercice pourra utiliser des commandes de systèmes d’exploitation de type UNIX telles que cd, ls, mkdir, rm, rmdir, mv, cat.

1. Dans un système d’exploitation de type UNIX, on considère l’arborescence suivante (les noms de dossiers sont en italique et ceux des fichiers sont en gras) :

/
├── bin
├── etc
├── home
│   └── morgane
│       ├── lycee
│       │   ├── francais
│       │   └── NSI
│       │       ├── info.txt
│       │       └── image1.jpg
│       └── perso
└── tmp

On suppose qu’on se trouve actuellement à l’emplacement /home/morgane.

a) Parmi les quatre propositions suivantes, donner celle correspondant à l’affichage obtenu lors de l’utilisation de la commande ls :

• Proposition 1 : lycee francais NSI info.txt image1.jpg perso
• Proposition 2 : lycee perso
• Proposition 3 : morgane
• Proposition 4 : bin etc home tmp

b) Écrire la commande qui permet, à partir de cet emplacement, d’atteindre le répertoire lycee.

On suppose maintenant qu’on se trouve dans le répertoire /home/morgane/lycee/NSI.

c) Écrire la commande qui permet de créer à cet emplacement un répertoire nommé algorithmique.

d) Écrire la commande qui permet, à partir de cet emplacement, de supprimer le fichier image1.jpg.

2. On rappelle qu’un processus est une instance d’application. On a exécuté la commande ps (avec quelques options). Un extrait du résultat est présenté ci-dessous :

UID   PID  PPID  C STIME TTY   TIME     CMD
test   900   739  0 10:51 ?  00:00:00 /usr/lib/gvfs/gvfs-udisks2-vol
test   907   838  0 10:51 ?  00:00:00 /usr/lib/gvfs/gvfsd-trash --sp
test   913   739  0 10:51 ?  00:00:00 /usr/lib/gvfs/gvfsd-metadata
test   923     1  0 10:51 ?  00:00:02 xfce4-terminal
test   927   923  0 10:51 pts/0  00:00:00 bash
test  1036     1  0 11:18 ?  00:00:02 mousepad /home/test/Documents/
test  1058   923  0 11:22 pts/1  00:00:00 bash
test  1153   927  0 11:44 pts/0  00:00:00 vi
test  1154   927  0 11:44 pts/0  00:00:00 python3 prog.py
test  1155  1058  0 11:44 pts/1  00:00:00 ps -aef

On rappelle que :

• l’UID est l’identifiant de l’utilisateur propriétaire du processus ;
• le PID est l’identifiant du processus ;
• le PPID est l’identifiant du processus parent ;
• C indique l’utilisation processeur ;
• STIME est l’heure de démarrage du processus ;
• TTY est le nom du terminal de commande auquel le processus est attaché ;
• TIME est la durée d’utilisation du processeur par le processus ;
• CMD le nom de la commande utilisée pour démarrer le processus.

a) Donner le PID du parent du processus démarré par la commande vi.

b) Donner le PID d’un processus enfant du processus démarré par la commande xfce4-terminal.

c) Citer le PID de deux processus qui ont le même parent.

d) Parmi tous les processus affichés, citer le PID des deux qui ont consommé le plus de temps du processeur.

3. On considère les trois processus P1, P2 et P3, tous soumis à l’instant 0 dans l’ordre 1, 2, 3 :

a) On considère que les processus sont exécutés de manière concurrente selon la politique du tourniquet (Round Robin) : le temps est découpé en quantums de temps. Le quantum correspond à une unité de temps. Reproduire le tableau ci-dessous et indiquer dans chacune des cases le processus exécuté par le processeur entre deux unités de temps.

b) On considère que les processus sont exécutés en appliquant la politique du « plus court d’abord » (SJF) : les processus sont exécutés complètement dans l’ordre croissant de leurs temps d’exécution, le plus court étant exécuté en premier. Reproduire et compléter le même tableau.

4. On considère trois ressources R1, R2 et R3 et trois processus P1, P2 et P3 dont les files d’exécution des instructions élémentaires sont indiquées ci-dessous :

a) Rappeler les différents états d’un processus et expliquer pourquoi il y a ici risque d’interblocage, en proposant un ordre d’exécution des instructions élémentaires le provoquant.

b) Proposer un ordre d’exécution des instructions élémentaires sans interblocage.

Exercice 3 — Amérique du Sud 2022 (4 points)

Cet exercice porte sur la gestion des processus et des ressources par un système d’exploitation.

Les parties A et B peuvent être traitées indépendamment.

A. Ordonnancement des processus

Dans le laboratoire d’analyse médicale d’un hôpital, plusieurs processus peuvent demander l’allocation du processeur simultanément.

Le tableau ci-dessous donne les demandes d’exécution de quatre processus et indique :

• le temps d’exécution du processus (en unité de temps) ;
• l’instant d’arrivée du processus sur le processeur (en unité de temps) ;
• le numéro de priorité du processus (classé de 1 à 10).

Plus la priorité est grande plus le numéro de priorité est petit. Ainsi le processus P3 est plus prioritaire que P1.

L’ordonnancement est de type préemptif : à chaque unité de temps, le processeur choisit d’exécuter le processus ayant le plus petit numéro de priorité (un seul processus à la fois). Ceci peut provoquer la suspension d’un autre processus qui reprendra lorsqu’il deviendra le plus prioritaire dans la file d’attente.

1. Reproduire le diagramme ci-dessous et indiquer dans chacune des cases le processus exécuté par le processeur entre deux unités de temps (il peut y avoir des cases vides).

2. Recopier et compléter les temps de séjour ainsi que les temps d’attente de chacun des processus (toujours en unités de temps).

Rappel :

• Temps de séjour = instant de terminaison − instant d’arrivée
• Temps d’attente = temps de séjour − temps d’exécution

3. À quelles conditions le temps d’attente d’un processus peut-il être nul ?

B. Processus et ressources

Dans ce laboratoire d’analyse médicale de l’hôpital, le laborantin en charge du traitement des différents prélèvements (sanguins, urinaires et biopsiques) utilise simultanément quatre logiciels :

• Logiciel d’analyse d’échantillons (connecté à l’analyseur) ;
• Logiciel d’accès à la base de données des patients (SGBD) ;
• Traitement de texte ;
• Tableur.

Le tableau ci-dessous donne l’état à un instant donné des différents processus (instances des programmes) qui peuvent soit mobiliser (M) des données (D1, D2, D3, D4 et D5), soit être en attente (A) des données ou ne pas les solliciter (-).

Une donnée ne peut être mobilisée que par un seul processus à la fois. Si un autre processus demande une donnée déjà mobilisée, il passe en attente.

Exemple : le SGBD mobilise la donnée D4 et est en attente de la donnée D5.

1. À partir du tableau ci-dessus, démontrer que, à cet instant, les processus s’attendent mutuellement.

2. Comment s’appelle cette situation ?

3. On suppose que l’analyseur d’échantillon libère la ressource D1. Donner un ordre possible d’exécution des processus.

Exercice 4 — Polynésie 2023 (4 points)

Cet exercice porte sur la gestion des processus et la programmation orientée objet.

On rappelle qu’un processus est l’instance d’un programme en cours d’exécution. Il est identifié par un numéro unique appelé PID. L’ordonnanceur est la composante du système d’exploitation qui gère l’allocation du processeur entre les différents processus.

Nous allons nous intéresser à l’algorithme d’ordonnancement du tourniquet dont le fonctionnement est résumé ci-dessous :

• les processus prêts à être exécutés sont placés dans une file d’attente selon leur ordre d’arrivée ;
• l’ordonnanceur alloue le processeur à chaque processus de la file d’attente un même nombre de cycles CPU, appelé quantum ;
• si le processus n’est pas terminé au bout de ce temps, son exécution est suspendue et il est mis à la fin de la file d’attente ;
• si le processus est terminé, il sort définitivement de la file d’attente.

1. On considère trois processus soumis à l’ordonnanceur au même instant pour lesquels on donne les informations ci-dessous :

a) Si le quantum du tourniquet est d’un cycle CPU, recopier et compléter la suite des PID des processus dans l’ordre de leur exécution : 11, 20, 32, 11, ...

b) Donner la composition de la suite des PID lorsque le quantum du tourniquet est de deux cycles CPU.

2. L’objectif de la suite de l’exercice est d’implémenter en langage Python l’algorithme du tourniquet. Nous allons utiliser une liste pour simuler la file d’attente des processus et la classe Processus dont le constructeur est donné ci-dessous :

class Processus:
    def __init__(self, pid, duree):
        self.pid = pid
        self.duree = duree
        # Le nombre de cycles qui restent à faire :
        self.reste_a_faire = duree
        self.etat = "Prêt"

Les états possibles d’un processus sont : « Prêt », « En cours d’exécution », « Suspendu » et « Terminé ».

a) Recopier et compléter l’instruction Python suivante permettant de créer la liste d’attente initiale des processus donnés dans le tableau précédent :

liste_attente = [Processus(..., ...), ..., ...]

b) Recopier et compléter les trois méthodes suivantes de la classe Processus :

def execute_un_cycle(self):
    ...

def change_etat(self, nouvel_etat):
    ...

def est_termine(self):
    ...

c) La fonction tourniquet ci-dessous implémente l’algorithme. Recopier et compléter le code manquant :

def tourniquet(liste_attente, quantum):
    ordre_execution = []
    while liste_attente != []:
        processus = liste_attente.pop(0)
        processus.change_etat("En cours d'exécution")
        compteur_tourniquet = 0
        while .................. and ..................:
            ordre_execution.append(...........)
            processus.execute_un_cycle()
            compteur_tourniquet = compteur_tourniquet + 1
        if .....................:
            processus.change_etat("Suspendu")
            liste_attente.append(processus)
        else:
            processus.change_etat(...........)
    return ordre_execution

liste_attente = [Processus(11, 4), Processus(20, 2), Processus(32, 3)]

def execute_un_cycle(self):
    self.reste_a_faire = self.reste_a_faire - 1

def change_etat(self, nouvel_etat):
    self.etat = nouvel_etat

def est_termine(self):
    return self.reste_a_faire == 0

def tourniquet(liste_attente, quantum):
    ordre_execution = []
    while liste_attente != []:
        processus = liste_attente.pop(0)
        processus.change_etat("En cours d'exécution")
        compteur_tourniquet = 0
        while compteur_tourniquet < quantum and not processus.est_termine():
            ordre_execution.append(processus.pid)
            processus.execute_un_cycle()
            compteur_tourniquet = compteur_tourniquet + 1
        if not processus.est_termine():
            processus.change_etat("Suspendu")
            liste_attente.append(processus)
        else:
            processus.change_etat("Terminé")
    return ordre_execution