Exercice 1 - Ordonnancement et interblocage · Bac Numérique et Sciences Informatiques Amérique du Nord 2024 (jour 1)

EXERCICE 1 (6 points)

Cet exercice porte sur la programmation Python, la programmation orientée objet, les structures de données (file), l'ordonnancement et l'interblocage.

On s'intéresse aux processus et à leur ordonnancement au sein d'un système d'exploitation. On considère ici qu'on utilise un monoprocesseur.

On veut simuler cet ordonnancement avec des objets. Pour ce faire, on dispose déjà de la classe Processus dont voici la documentation:

Classe Processus:

p = Processus(nom: str, duree: int)

Crée un processus de nom <nom> et de durée <duree> (exprimée en cycles d'ordonnancement)

p.execute_un_cycle()

Exécute le processus donné pendant un cycle.

p.est_fini()

Renvoie True si le processus est terminé, False sinon.

Pour simplifier, on ne s'intéresse pas aux ressources qu'un processus pourrait acquérir ou libérer.

Pour mettre en place l'ordonnancement, on décide d'utiliser une file, instance de la classe File ci-dessous.

Classe File

class File:

def __init__(self):

""" Crée une file vide """

self.contenu = []

def enfile(self, element):

""" Enfile element dans la file """

self.contenu.append(element)

def defile(self):

""" Renvoie le premier élément de la file et l'enlève de la file """

return self.contenu.pop(0)

def est_vide(self):

""" Renvoie True si la file est vide, False sinon """

return self.contenu == []

1.

Citer les trois états dans lesquels un processus peut se trouver.

2.

Pour simplifier, on ne s’intéresse pas aux ressources qu’un processus pourrait acquérir ou libérer.

Citer les deux seuls états possibles pour un processus dans ce contexte.

4.

Pour décrire les processus et le moment de leur création, on utilise le code suivant, dans lequel depart_proc associe à un cycle donné le processus qui sera créé à ce moment:

p1 = Processus("p1", 4)

p2 = Processus("p2", 3)

p3 = Processus("p3", 5)

p4 = Processus("p4", 3)

depart_proc = {0: p1, 1: p3, 2: p2, 3: p4}

Il s'agit d'une modélisation de la situation précédente où un seul processus peut être créé lors d'un cycle donné.

Recopier et compléter sur votre copie le chronogramme ci-dessous pour les processus p1, p2, p3 et p4.

5.

Pour mettre en place l’ordonnancement suivant cette méthode, on écrit la classe Ordonnanceur dont voici un code incomplet (l’attribut temps correspond au cycle en cours):

Compléter le code ci-dessous.

class Ordonnanceur:

def __init__(self):

self.temps = 0

self.file = File()

def ajoute_nouveau_processus(self, proc):

'''Ajoute un nouveau processus dans la file de

l'ordonnanceur. '''

def tourniquet(self):

'''Effectue une étape d'ordonnancement et renvoie le nom

du processus élu.'''

self.temps += 1

if not self.file.est_vide():

proc =...

...

if not proc.est_fini():

...

return proc.nom

else:

return None

6.

À chaque appel de la méthode tourniquet, celle-ci renvoie soit le nom du processus qui a été élu, soit None si elle n’a pas trouvé de processus en cours.

Écrire un programme qui:

utilise les variables p1, p2, p3, p4 et depart_proc définies précédemment;

crée un ordonnanceur;

ajoute un nouveau processus à l'ordonnanceur lorsque c'est le moment;

affiche le processus choisi par l'ordonnanceur;

s'arrête lorsqu'il n'y a plus de processus à exécuter.

7.

Dans la situation donnée en exemple (voir Figure 1), il s’avère qu’en fait les processus utilisent des ressources comme:

un fichier commun aux processus;

le clavier de l'ordinateur;

le processeur graphique (GPU);

le port 25000 de la connexion Internet.

Voici le détail de ce que fait chaque processus:

Liste des processus

A

B

C

D

acquérir le GPU

acquérir le clavier

acquérir le port

acquérir le fichier

faire des calculs

acquérir le fichier

faire des calculs

faire des calculs

libérer le GPU

libérer le clavier

libérer le port

acquérir le clavier

libérer le fichier

libérer le clavier

libérer le fichier

Montrer que l’ordre d’exécution donné en exemple aboutit à une situation d’interblocage.