X/ENS Informatique B MP-PC-PSI 2021

ECOLE POLYTECHNIQUE - ESPCI
ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMI SSION 2021

JEUDI 15 AVRIL 2021
16h30 - 18h30

FILIERES MP-PC-PSI
Epreuve n° 8
INFORMATIQUE B (XELCR)

Durée : 2 heures

L'utilisation des calculatrices n'est pas
autorisée pour cette épreuve

Gestion d'un allocateur dynamique de mémoire

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. Le 
langage de
programmation sera obligatoirement Python.

Complexité. La complexité, ou le temps d'exécution, d'une fonction P est le 
nombre d'opé-
rations élémentaires (addition, multiplication, affectation, test, etc...) 
nécessaires à l'exécution
de P. Lorsqu'il est demandé de donner la complexité d'un programme, le candidat 
devra justifier
cette dernière si elle ne se déduit pas directement de la lecture du code.

Rappels concernant le langage Python. L'utilisation de toute fonction Python 
sur les listes
autre que celles mentionnées dans ce paragraphe est interdite.

Si a désigne une liste en Python :

e len(a) renvoie la longueur de cette liste, c'est-à-dire le nombre d'éléments 
qu'elle contient ;
la complexité de Len est en O(1).

e ali] désigne le i-ème élément de la liste, où l'indice i est compris entre 0 
et len(a) - 1:
la complexité de cette opération est en O(1).

On pourra aussi utiliser la fonction range pour constuire une liste d'entiers 
et réaliser des
itérations.

Introduction. Dans ce sujet, on s'intéresse à un environnement de programmation 
qui à une
mémoire limitée, et où l'on veut limiter au maximum la création de nouvelles 
structures (comme
les listes Python) en mémoire. Pour cela, nous souhaitons fournir au 
programmeur un environne-
ment de gestion dynamique de la mémoire dans lequel il pourra réserver des 
portions de mémoire
pour y lire et écrire des données, puis libérer certaines portions quand il 
n'en a plus besoin. Pour
simplifier, nous ne permettons au programmeur de lire et écrire dans ces 
portions de mémoire que
des valeurs de type caractère, c'est-à-dire des chaînes de caractères de 
longueur 1. Une portion
qui n'est pas (ou n'est plus) réservée est dite libre. Chaque portion agit 
comme un tableau de
caractères : elle a une taille, et on peut lire et écrire les caractères aux 
positions comprises entre
DOett--]1,sit est la taille demandée pour la portion considérée lors de sa 
réservation.

Ce service est réduit aux cinq fonctions suivantes :

e p -- reserver(n, c) qui renvoie une nouvelle portion p réservée qui était 
libre précédem-
ment. La portion est de taille n et toutes ses n cases contiennent le même 
caractère c. La
fonction renvoie None si la mémoire est trop pleine pour permettre cette 
réservation.
liberer(p) qui libère une portion p qui était réservée précédemment.

e c = lire(p, i) renvoie le caractère c stocké à la case en position i dans la 
portion p.

ecrire(p, i, c) qui met à jour la case en position i dans la portion p avec le 
caractère c.

demarrage() qui est appelée une seule fois pour initialiser correctement la 
mémoire, avant
tout appel aux quatre fonctions précédentes.

Dans ce sujet, on considère que le programmeur fera un usage licite de ces 
fonctions en
respectant les préconditions suivantes :

e il ne lira et n'écrira qu'en utilisant les fonctions lire et ecrire, dans les 
portions actuel-
lement réservées et à des positions comprises entre 0 et EUR -- I, si { est la 
taille demandée
pour la portion considérée lors de sa réservation ;

e il n'utilisera les fonctions libere, lire et ecrire qu'avec des portions p 
obtenues par un
appel à reserver et qui n'auront pas été explicitement libérées depuis cet 
appel;

e il n'utilisera p = reserver(n, c) que lorsque l'entier n est strictement 
positif ;

e il n'utilisera les fonctions libere, lire, ecrire et reserver que sur une 
mémoire correc-
tement initialisée avec un appel à demarrage).

Ces propriétés sont appellées hypothèses de bon usage.

Pour implémenter ces services, nous créons initialement une liste Python mem de 
taille
TAILLE_MEM (intialisée avec des 0). Les variables mem et TAILLE_MEM sont des 
variables globales.
Aucune autre liste Python ne doit être manipulée dans ce sujet, exception faite 
des listes
créées avec la fonction range pour réaliser des itérations.

mem = [O] *x TAILLE _MEM

On suppose que mem vient juste d'être initialisée de cette façon au moment de 
l'appel de
demarrage(). Cette liste va contenir les différents contenus des portions qui 
seront réservées
et libérées. Chaque case contiendra soit un caractère placé par le programmeur, 
soit un entier
que nous placerons pour organiser notre structure de données. Grâce aux 
hypothèses de bon
usage, le programmeur n'accédera jamais à des cases contenant des entiers.

Dans tout le sujet, les services de lecture et écriture sont donnés par les 
fonctions suivantes :

def lire(p, i):

return memlp+il
def ecrire(p, i, c):
memlp+i]l = c

Par conséquent, nous désignerons par une portion un indice valide p de mem, tel 
que
mem[p]l ... memlp+tn-1] sont les cases réservées par le programmeur lors de 
l'appel à
p = reserver(n,c). Nous confondons donc la portion p avec la première position, 
accessible
au programmeur, des cases ainsi réservées.

Ce sujet est conçu pour être traité linéairement. Les différentes hypothèses et 
spécifications
listées dans cette introduction sont valables et importantes pour les quatre 
parties du sujet.
Chaque partie propose une stratégie différente des fonctions demarrage, 
reserver et liberer de
gestion dynamique de la mémoire. Seule la fonction initialiser décrite plus bas 
est la même
dans chaque partie.

Partie Ï : Implémentation naïve

Dans cette partie, nous organisons notre mémoire mem comme une suite contigué 
de portions
entre les indices 1 et TAILLE _MEM-1. La case mem[0] joue un rôle spécifique : 
elle contient un
entier prochain tel que les portions réservées jusqu'à présent se trouvent 
parmi les cases mem[1]
..mem[prochain-1]. Lors de la prochaine réservation, la nouvelle portion sera 
placée à partir de
l'indice prochain. Ici, une portion p de taille n est constituée de n cases 
mem[p],...,mem[p+n-1].
Mais dans cette stratégie naïve d'implémentation, la libération de portion n'a 
pas d'effet sur mem,
ce qui est correct mais peu efficace en termes de consommation mémoire : aucun 
recyclage de
mémoire n'est possible. La fonction de libération est donc simplement ! :

def liberer (p):
pass

La FIGURE 1 présente le contenu du début de mem après l'appel des services 
suivants par le
programmeur :

pi = reserver(6, 'a?)
p2 = reserver (9, ?'b')
p3 = reserver(3, ?'c')

ecrire(pi, O0, ?A?)

ug[a a alalalalb bb b bbb bible c c|o o 0 0 0 0 0 0 0 0 0
D T1 2 3 À 5 6 7 E O0 10 11 12 13 14 15 16 17 189 19 20 21 22 23 24 25 26 27 28 
29

FIGURE 1 -- Exemple de contenu de la mémoire - Stratégie naïve.

Question 1. Ecrire une fonction initialiser(p, n, c) qui initialise une portion 
de taille n à
l'indice p en remplissant chaque case avec le caractère c.

Question 2. Écrire la fonction demarrage() pour cette stratégie.

Question 3. Écrire la fonction reserver(n, c) pour cette stratégie. Préciser la 
complexité de
reserver(n, c) en fonction de n et TAILLE _MEM.

1. En Python, pass est l'instruction qui ne fait rien.
À partir de maintenant, les seules fonctions manipulant directement la liste 
mem seront fournies
par l'énoncé. Vos solutions doivent donc s'appuyer sur les fonctions 
auxiliaires qui vous seront
fournies et ne pas contenir de lecture (de la forme a=-mem[p]) ou écriture (de 
la forme mem[p]=a)
directes à mem.

Partie II : Réservations de blocs de tailles fixes

Nous cherchons maintenant à permettre la réutilisation de la mémoire libérée. 
Nous pro-
posons pour cela une nouvelle stratégie d'implémentation. Nous fixons une 
constante globale
TAILLE_BLOC et nous placerons les portions à l'intérieur de blocs de taille 
fixe de TAILLE_BLOC
cases contiguës dans la liste mem. Une portion p reservée avec la taille n (où 
n+1 < TAILLE_BLOC) occupe n + 1 cases au début d'un tel bloc. La première case memlp-1] contient un en-tête qui vaut 1 si la portion est encore réservée, ou 0 si elle a été libérée. Les cases suivantes sont utilisées pour stocker les caractères écrits par le programmeur. Comme précédemment, la case mem[0] est réservée pour pointer sur la prochaine portion libre pour créer un bloc (si aucun recyclage de bloc libéré n'était possible). La FIGURE 2 présente le contenu du début de mem après l'appel des services suivants par le programmeur : pi = reserver(6, 'a?) p2 p3 liberer (p2) reserver (4, 'b?) reserver (3, °c?) ecrire(pi, O0, ?A?) portion pl portion p2 portion p3 réservée libre réservée | | | 23 Mu 4 a a a a ab bb bo oMlc clic oo ol0o 0 0 0 0 00e 0e D 1 2 3 4 5 6 7 8 9 10 11 12 12 14 15 16 17 18 10 20 21 22 23 24 25 26 27 28 20 dd D D D Là. LL. bloc de TAILLE BLOC bloc de TAILLE BLOC bloc de TAILLE BLOC FIGURE 2 --- Exemple de contenu de la mémoire avec TATILLE_BLOC=7 - Partie IT. Pour manipuler les cases d'en-tête des portions et la prochaine portion libre, nous vous fournissons les fonctions suivantes : def lire _prochaïin): def ecrire _prochain(p): return meml[0] mem[O] = p def est_reservee(p): def est_libre(p): Il Il + return memlp-1] return meml[p-1] == 0 def marque_reservee(pj): def marque_libre(p): memlp-1] = 1 memlp-1] = © Question 4. Écrire la fonction demarrage() pour cette stratégie d'implémentation. Pour réserver une nouvelle portion, on cherche en priorité à réutiliser un bloc laissé libre par une précédente libération. La portion libre pointée par lire_prochain() n'est utilisée que si un tel bloc n'existe pas. Question 5. Écrire la fonction reserver(n, c) pour cette stratégie d'implémentation. Ren- voyer None si la taille n est trop grande vis-à-vis de TAILLE _ BLOC. Préciser la complexité de reserver(n, c) en fonction de n et TAILLE _MEM. Question 6. Écrire la fonction liberer(p) pour cette stratégie d'implémentation. Partie III : Portions avec en-tête et pied de page Nous abordons maintenant une autre stratégie d'implémentation qui permettra de ne pas limiter autant la taille de chaque portion. Nous munissons pour cela chaque portion d'un en-tête mais aussi d'un pied de page. Pour chaque portion, ces deux cases additionnelles contiennent la même valeur : un entier encodant deux informations sur la portion courante. La première information indique si la portion est réservée ou pas. La deuxième indique la taille réservée à cette portion. Nous imposons que cette taille soit toujours un entier pair. Si un programmeur demande à réserver une portion de taille n impaire, nous attribuerons une taille n + 1 à cette portion, mais le programmeur n'est pas autorisé à consulter cet espace supplémentaire, en vertu des hypothèses de bon usage dictées en début de sujet. Nous vous fournissons toutes les fonctions nécessitant un accès direct à mem : def est_reservee(p): def est_libre(p): return memlp-1] #% 2 == 1 return memlp-1] % 2 == © def marque _reservee(p, taille): def marque_libre(p, taille): mot = taille + 1 mot = taille memlp-1] = mot memlp-1] = mot memlpttaillel = mot memlp+ttaillel = mot def lire _taille(p): def lire_taille_precedent (p): return 2 *x (memlp-1] // 2) return 2 *x (memlp-2] // 2) def precedent _est_libre(p): def precedent _est_reserve(pj): return memlp-2] % 2 == © return memlp-2] % 2 == 1 Question 7. Expliquer en quelques lignes le fonctionnement des fonctions est_reservee, marque_reservee, lire_taille et precedent _est_libre. Nous utiliserons deux portions spéciales, une portion prologue et une portion épilogue. Ces deux portions spéciales sont de taille nulle et toujours marquées réservées. Nous les placçons en début et en fin de la zone de réservation. La portion prologue se situe à une position fixe donnée par la variable globale suivante : PROLOGUE = 2 La case mem[0] indique la position courante de l'épilogue. L'épilogue est contigu au prologue au démarrage, puis est déplacé vers des indices plus élevés quand la zone des portions réser- vées doit être agrandie. Nous vous fournissons les fonctions permettant de lire et modifier les informations concernant cette portion spéciale : def lire_position_epilogue): def ecrire_position_epilogue(p): return meml[0] mem[O] = p La FIGURE 3 présente ? le contenu du début de mem après l'appel des services suivants par le programmeur : pi = reserver(6, 'a?) p2 p3 reserver (1, ?'c?) liberer (p2) ecrire(pi, O0, ?A?) reserver (7, ?'b') portion portion prologue épilogue portion p1 portion p2 portion p3 réservée libre réservée en-tête | pied 1 page | | 26/01 of À a a à a a 6180 b b b b b b b 0 sof24 c Q  2+110+1 0+11 Q  Q o | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 FIGURE 3 -- Exemple de contenu de la mémoire - Partie III. Question 8. Écrire la fonction demarrage() pour cette stratégie. À part les deux portions spéciales épilogue et prologue, toutes les portions ont une taille strictement positive. Lors de la réservation d'une nouvelle portion, on réserve en priorité dans la zone de mémoire comprise entre le prologue et l'épilogue, et en dernier recours on déplace l'épilogue. Si une portion libre est suffisamment grande, une réservation dans cette zone la sépare en une portion réservée et une portion libre. 2. Dans les en-têtes et pieds de page de ces figures, la notation t + b désigne l'encodage d'une paire formée d'une taille t et d'un bit d'état de réservation b EUR {0,1}. La FIGURE 4 illustre ce mécanisme en présentant le contenu de la mémoire de la FIGURE 3, après l'appel à p4 = reserver(2,'d°?). portion portion prologue épilogue portion p1 portion p4 portion portion p3 réservée réservée libre réservée ent | pied ' page | | | 26 [0-1 o+1 |6+1 À a a a a a 6+1 |2+1 d dl 241 [410 b b  b  ©Q 410 | 2+1 c  Q 2+1/0+1 om1| 0 Q o | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 FIGURE 4 -- Exemple de contenu de la mémoire après nouvelle réservation - Partie IIT. Question 9. Écrire la fonction reserver(n, c) pour cette stratégie. Préciser la complexité de reserver(n, c) en fonction de n et TAILLE _MEM. Lors de la libération d'une portion, on étudie les portions adjacentes libres et on réalise si possible une fusion afin qu'il n'y ait jamais deux portions adjacentes libres après un appel à la fonction liberer. La FIGURE 5 illustre ce mécanisme en présentant le contenu de la mémoire de la FIGURE 4. après l'appel à liberer (p3). portion portion prologue épilogue portion p1 portion p4 portion réservée réservée libre en-tête | pied de page | | 26 [01 0+1 [6:11 À à a a a a Gui [241 d d 241 | 840 b bb @ @Q @ cc  @ \8+0|0+1 0+11 © Q 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 FIGURE 5 -- Exemple de contenu de la mémoire après nouvelle libération - Partie IIT. Question 10. Écrire la fonction liberer(p) pour cette stratégie. Justifier la correction et la complexité de liberer(p) en fonction de TAILLE_MEM, en précisant le nombre maximal de fusions effectuées à chaque appel, et en expliquant l'interêt des portions prologues et épilogues. Partie IV : Chaînage explicite des portions libres Nous souhaitons maintenant améliorer l'implémentation de la partie précédente pour accélérer la recherche de portions libérées. Nous allons pour cela maintenir une chaîne des portions libres. Il s'agit d'une séquence de portions libres organisée de la façon suivante : e dans chaque portion libre p dans la chaîne, on stocke une information dans les cases mem [pl] et memlp+1] : -- la case mem[p]l contient la position de la portion libre prédécesseur dans la chaîne ; -- la memfp+1] contient la position de la portion libre successeur dans la chaîne ; e la position de l'entrée de la chaîne est stockée dans la case mem[1]. Elle vaut 0 si et seulement si la chaîne est vide. e si la chaîne n'est pas vide, son entrée est une portion dont le prédécesseur vaut 0: e si la chaîne n'est pas vide, elle contient une portion de fin (éventuellement égale à celle d'entrée) dont le successeur vaut 0 ; e toutes les autres portions de la chaîne ont des prédécesseurs et successeurs non nuls. Pour manipuler cette structure, nous vous fournissons les fonctions suivantes : def lire _entree_chaine): def ecrire _entree_chaine(p): return memli] memli]l = p def lire_predecesseur (p): def lire _successeur (p): return lire(p, 0) return lire(p, 1) def ecrire _predecesseur(p, predecesseur ): ecrire(p, 0, predecesseur) def ecrire _successeur(p, successeur): ecrire(p, 1, successeur) def chaine est _vide): return lire _entree_chaine()== Par ailleurs, on redéfinit la portion prologue comme suit : PROLOGUE = 3 La FIGURE 6 présente le contenu du début de mem après l'appel des services suivants par le programmeur : pi = reserver (2, ?'a?) p2 = reserver (2, ?'b') p3 = reserver (2, ?'c') p4 = reserver (2, ?'d'?) p5 = reserver(1, ?e?) p6 = reserver (1, ?'f?) liberer (pl) liberer(p5) liberer (p3) La FIGURE 7 présente la chaîne associée, qui commence par la portion p3=13 , suivi de p5=21 et enfin de p1=5. portion portion prologue épilogue entrée de portion p1 portion p2 portion p3 portion p4 portion p5 portion p6 la chaîne libre réservée libre réservée libre réservée 29 13 |0+1 0+112+0 21 @ 2+0 [21 b  b 2+1 [2-0 Q 21 2+0 | 24) dd 2" | 2+0 13 5 2+0[2+1 f  Q 2+1 [o-1 Q+1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 FIGURE 6 -- Exemple de contenu de la mémoire - Partie IV. ___entrée (es) successeur (es) successeur (a) successeur Q prédécesseur prédécesseur prédécesseur FIGURE 7 -- Chaîne associée à la mémoire de la FIGURE 6. Question 11. Écrire la fonction ajoute_en_entree_de_chaine(p) qui ajoute la portion libre p en tête de la chaîne et en fait son entrée. La portion p n'appartient pas à la chaîne au moment de l'appel. Question 12. Écrire la fonction supprime_dans_chaine(p) qui supprime la portion p de la chaîne. La portion p est libre et appartient à la chaîne. Question 13. Écrire la fonction demarrage() pour cette stratégie. Question 14. Écrire la fonction reserver(n, c) pour cette stratégie. Préciser la complexité de reserver(n, c) en fonction de n, TAILLE_MEM, et tout autre quantité que vous jugerez utile pour mettre en valeur le gain en efficacité de cette stratégie d'implémentation. Comme cette fonction est très similaire à la fonction reserver(n, c) écrite pour la partie précédente, vous pouvez indiquer seulement les différences entre cette version et la précédente (en numérotant les lignes de la fonction précédente). La FIGURE 8 présente le résultat de l'opération liberer (p6) sur la mémoire de la FIGURE 6. portion portion prologue épilogue entrée de portion p1 portion p2 portion p3 portion p4 portion p5 la chaîne libre réservée libre réservée libre | | | | | | 29/21 Q+1 @+112+0 13 @ 2+012+1 bb  bDb 2+112+0 21 5 2+012+1 d  d 2+116+0 Q 13 Q@  Q  f  @ 6+0|10+1 o+1 0 1 2.3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 FIGURE 8 --- Exemple de contenu de la mémoire après libération de p6 - Partie IV. Pour libérer une portion, on réalise comme dans la partie précédente une fusion avec les éventuelles portions libres adjacentes en mémoire, mais en les supprimant au préalable de la chaîne, puis en ajoutant en entrée de chaîne la portion libre créée par la fusion. Question 15. Écrire la fonction liberer(p) pour cette stratégie. Préciser la complexité de liberer(p) en fonction de TAILLE_MEM. Là encore, il vous suffit de préciser les différences avec la fonction liberer(p) de la partie précédente. 10