X/ENS Informatique B MP-PC-PSI 2021

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                

Rapport du jury

(télécharger le PDF)
                 

Énoncé obtenu par reconnaissance optique des caractères


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

Extrait du corrigé obtenu par reconnaissance optique des caractères



X/ENS Informatique B MP-PC-PSI 2021 --
Corrigé
Ce corrigé est proposé par Virgile Andreani (ENS Ulm) ; il a été relu par 
William
Aufort (professeur en CPGE) et Benjamin Monmege (enseignant-chercheur à 
l'université).

Ce sujet présente le problème de l'allocation dynamique de mémoire, qui est
fondamental dans le fonctionnement des systèmes d'exploitation et de la plupart 
des
langages de programmation. C'est un important domaine de recherche et 
d'ingénierie :
des algorithmes utilisant des idées semblables à celles présentées ici sont 
utilisés en
permanence par les OS modernes et par les applications. Le sujet est de 
difficulté
croissante et à aborder dans l'ordre puisque chaque partie repose sur la 
précédente.
· En guise d'introduction, la partie I pose trois questions faciles pour 
réaliser une
première implémentation naïve.
· La partie II introduit la notion d'en-têtes à chaque portion de mémoire. Ces 
métadonnées permettent de recycler la mémoire qui n'est plus utilisée.
· Dans la partie III, les métadonnées sont complexifiées et dupliquées afin de
permettre la fusion de portions libres consécutives. L'une des questions 
d'implémentation de cette partie est particulièrement difficile.
· Enfin, la partie IV introduit une amélioration du système précédent qui 
consiste
à maintenir une chaîne des portions libres permettant de parcourir rapidement
ces dernières.
Le sujet ne comporte que 15 questions ; c'est peu, mais les enjeux sont autant 
la
rapidité que la justesse. En effet, l'implémentation des fonctions reserver et 
liberer
des deux dernières parties est complexe, et propice à de nombreuses erreurs de 
logique ou de décalage d'indices, surtout sur papier. Néanmoins, le sujet est 
très guidé
et bien posé. Plusieurs pages ne comportent pas de question mais sont à lire 
attentivement puisqu'elles présentent les principes des algorithmes étudiés ou 
les fonctions
à utiliser pour les implémentations. On pourra d'ailleurs noter que cette 
pratique
d'encapsulation du code derrière des interfaces que l'on peut utiliser sans 
connaître
leur fonctionnement interne est un pilier de la programmation orientée objet, 
un paradigme de programmation utilisé par exemple dans les langages Python, 
Java, C++,
etc. C'est un très bon sujet d'entraînement, que l'on peut aborder dès la 
première
année pour tester sa capacité à écrire du code sans faute.

Indications
Partie I
3 Ne pas oublier de gérer le cas où la mémoire est trop pleine pour effectuer 
l'allocation.
Partie II
5 Pour parcourir la mémoire, les blocs étant de taille fixe, il est approprié 
d'utiliser
une boucle for avec un incrément adapté. Utiliser la fonction initialiser de
la question 1. Prendre soin de bien gérer les cas particuliers (taille demandée
supérieure à la taille d'un bloc ou allocation à la fin impossible par manque
de place).
Partie III
7 On pourra imaginer la représentation binaire de l'entier dans l'en-tête et le 
pied
de page.
8 Utiliser, entre autres, la fonction marque_reservee fournie par l'énoncé.
9 Commencer par un parcours des portions successives pour en chercher une libre 
et
de taille suffisante. Le cas échéant, on effectue l'allocation, on crée 
éventuellement
une section libre avec le reliquat et on retourne immédiatement. Si on arrive à
l'épilogue sans avoir trouvé de portion adaptée, on alloue sur place en décalant
l'épilogue après avoir vérifié que la place disponible est suffisante.
10 Si la portion suivante est libre, on peut augmenter la taille de la portion 
libérée.
Si la portion précédente est libre, on en augmente la taille et on déplace 
également
le pointeur qui en marque le début.
Partie IV
11 Commencer par le cas où la chaîne est initialement vide. Faire un schéma pour
voir quelles relations (successeur ou prédécesseur) sont réécrites, et où. 
Faire de
même pour le cas général.
12 Observer que pour supprimer une portion de la chaîne, il suffit de raccorder 
son
prédécesseur et son successeur. Vérifier les cas limites lorsque la portion est 
en
entrée ou à la fin de la chaîne.
13 Ne pas oublier que la variable globale PROLOGUE a été modifiée.
14 Les lignes de l'implémentation précédente à modifier sont celles qui 
effectuent le
parcours des portions à la recherche d'une portion recyclable. Il faut également
ajouter des appels à supprime_dans_chaine et ajoute_en_entree_de_chaine
pour maintenir la chaîne à jour.
15 Ajouter trois lignes à la fonction liberer de la question 10 : deux appels à
supprime_dans_chaine et un à ajoute_en_entree_de_chaine.

I. Implémentation naïve
1 La fonction initialiser remplit avec le caractère c les cases de mémoire 
situées
entre les indices p inclus et p+n exclu.
def initialiser(p, n, c):
for i in range(n):
mem[p+i] = c
La fonction initialiser n'est pas une des cinq faisant partie de l'interface
du service. C'est donc une fonction auxiliaire, à usage interne (appelée par
reserver). Il convient ici, comme d'habitude, de lire les questions un peu en
avance afin de ne pas déjà implémenter dans initialiser ce qui doit l'être
dans reserver.
2 La fonction demarrage doit placer la mémoire dans un état prêt à recevoir des
demandes d'allocation. Initialement, la mémoire est vide et la seule case qui 
sera lue
avant d'être écrite est mem[0]. On doit donc s'assurer que sa valeur est 
correcte pour
la première utilisation de la mémoire. Cette case indiquant le début de la 
prochaine
portion libre, sa valeur initiale doit être 1.
def demarrage():
mem[0] = 1
3 Dans la fonction reserver, on commence par s'assurer que la mémoire disponible
est suffisante pour effectuer l'allocation. Si ce n'est pas le cas, on retourne 
directement
None, comme demandé. Si tout va bien, on initialise la portion demandée à 
l'aide de
la fonction écrite à la question 1 et on change la valeur de la première case, 
sans
oublier de retourner l'indice de la portion allouée.
def reserver(n, c):
p = mem[0]
if p + n > TAILLE_MEM:
return None
initialiser(p, n, c)
mem[0] += n
return p
Pour vérifier si le test sur la mémoire disponible doit être implémenté à
l'aide d'une inégalité large ou stricte, on peut compter les cases du schéma
donné dans l'énoncé. Pour TAILLE_MEM = 30 et mem[0] = 19, on peut allouer
au maximum 11 cases, une douxième case serait de trop. Comme 19+11 = 30
et 19 + 12 = 31, on doit utiliser une inégalité stricte à la troisième ligne.
On aurait pu exploiter le fait que les fonctions Python retournent 
implicitement None lorsque l'exécution arrive à leur fin pour écrire :
def reserver(n, c):
p = mem[0]
if p + n <= TAILLE_MEM: initialiser(p, n, c) mem[0] += n return p C'est une bonne pratique de signaler les erreurs de manière explicite et le plus tôt possible, ce qui permet également de réduire le niveau d'indentation moyen du code et de le rendre plus compréhensible. Pour calculer la complexité de la fonction, il faut compter le nombre d'opérations élémentaires effectuées par celle-ci. La fonction reserver est sans boucle ni récursion, et la seule fonction qu'elle appelle est initialiser, qui effectue un nombre d'opérations proportionnel à n. Par conséquent, la complexité de la fonction est en O(n) et ne dépend pas de la taille totale de la mémoire. II. Réservations de blocs de tailles fixes 4 Pour l'initialisation de la mémoire, il s'agit de s'assurer, comme à la question 2, que la première case pointe au bon endroit. Il est inutile d'initialiser les en-têtes, puisque l'allocation de mémoire à partir de mem[0] réserve des blocs neufs, jamais encore réservés, et donc ne lit pas leurs en-têtes. Puisque mem[0] ne pointe pas vers l'en-tête d'un bloc, mais vers le début d'une portion de données, sa valeur initiale est ici 2 et non plus 1 comme à la question 2. def demarrage(): ecrire_prochain(2) 5 On peut commencer par vérifier que la taille de mémoire demandée ne dépasse pas d'un bloc. Puis, s'il existe un bloc libre à recycler, on doit l'utiliser. On en recherche donc un, en itérant sur les emplacements des portions, de la première, incluse, à celle désignée par mem[0], exclue, au moyen de la fonction range dont le troisième argument indique l'incrément. Si la recherche échoue, après avoir vérifié que la mémoire disponible est suffisante, on effectue l'allocation d'un bloc sur la portion pointée par mem[0] et on met à jour la prochaine portion libre si besoin. def reserver(n, c): if n + 1 > TAILLE_BLOC:
return None
# Recherche d'un bloc libre à recycler
for p in range(2, lire_prochain(), TAILLE_BLOC):
if est_libre(p):
marque_reservee(p)
initialiser(p, n, c)
return p
# Pas de bloc libre trouvé : allocation à la fin si possible
p = lire_prochain()
if p + TAILLE_BLOC - 1 > TAILLE_MEM:
return None
ecrire_prochain(p + TAILLE_BLOC)
marque_reservee(p)
initialiser(p, n, c)
return p
Ici encore, ne pas hésiter à compter les cases à la main et à jouer avec les
dimensions pour vérifier que les tests sont corrects.
Dans le pire des cas, on recherche en vain un bloc libre dans une mémoire 
quasiment pleine. Dans ce cas, la boucle de la fonction a effectué un nombre 
d'itérations