Ordonnanceur avec liste d'attente⚓︎

D'après 2022, Polynésie, J1, Ex. 2

Un système est composé de 4 périphériques, numérotés de 0 à 3, et d'une mémoire, reliés entre eux par un bus auquel est également connecté un dispositif ordonnanceur. À l'aide d'un signal spécifique envoyé sur le bus, l'ordonnanceur sollicite à tour de rôle les périphériques pour qu'ils indiquent le type d'opération (lecture ou écriture) qu'ils souhaitent effectuer, et l'adresse mémoire concernée.

Un tour a lieu quand les 4 périphériques ont été sollicités. Au début d'un nouveau tour, on considère que toutes les adresses sont disponibles en lecture et écriture.

Si un périphérique demande l'écriture à une adresse mémoire à laquelle on n'a pas encore accédé pendant le tour, l'ordonnanceur répond "OK" et l'écriture a lieu. Si on a déjà demandé la lecture ou l'écriture à cette adresse, l'ordonnanceur répond "ATT" et l'opération n'a pas lieu.

Si un périphérique demande la lecture à une adresse à laquelle on n'a pas encore accédé en écriture pendant le tour, l'ordonnanceur répond "OK" et la lecture a lieu. Plusieurs lectures peuvent avoir donc lieu pendant le même tour à la même adresse.

Si un périphérique demande la lecture à une adresse à laquelle on a déjà accédé en écriture, l'ordonnanceur répond "ATT" et la lecture n'a pas lieu.

Ainsi, pendant un tour, une adresse peut être utilisée soit une seule fois en écriture, soit autant de fois qu'on veut en lecture, soit pas utilisée.

Si un périphérique ne peut pas effectuer une opération à une adresse, il demande la même opération à la même adresse au tour suivant.

1. Le tableau donné en annexe 1 indique, sur chaque ligne, le périphérique sélectionné, l'adresse à laquelle il souhaite accéder et l'opération à effectuer sur cette adresse. Compléter dans la dernière colonne de cette annexe, à rendre avec la copie, la réponse donnée par l'ordonnanceur pour chaque opération.

Annexe 1

N° périphérique	Adresse	Opération	Réponse de l'ordonnanceur
0	`10`	écriture	`"OK"`
1	`11`	lecture	`"OK"`
2	`10`	lecture	`"ATT"`
3	`10`	écriture	`"ATT"`
0	`12`	lecture
1	`10`	lecture
2	`10`	lecture
3	`10`	écriture

Réponse

N° périphérique	Adresse	Opération	Réponse de l'ordonnanceur
0	`10`	écriture	`"OK"`
1	`11`	lecture	`"OK"`
2	`10`	lecture	`"ATT"`
3	`10`	écriture	`"ATT"`
0	`12`	lecture	`"OK"`
1	`10`	lecture	`"OK"`
2	`10`	lecture	`"OK"`
3	`10`	écriture	`"ATT"`

Il s'agit d'un nouveau tour, les lectures sont possibles, la première écriture ne l'est pas, on a déjà accédé en lecture pendant le tour à l'adresse demandée.

On suppose dans toute la suite que :

le périphérique 0 écrit systématiquement à l'adresse 10 ;
le périphérique 1 lit systématiquement à l'adresse 10 ;
le périphérique 2 écrit alternativement aux adresses 11 et 12 ;
le périphérique 3 lit alternativement aux adresses 11 et 12 ;

Pour les périphériques 2 et 3, le changement d'adresse n'est effectif que lorsque l'opération est réalisée.

2. On suppose que les périphériques sont sélectionnés à chaque tour dans l'ordre 0 ; 1 ; 2 ; 3. Expliquer ce qu'il se passe pour le périphérique 1.

Réponse

À chaque début de tour, le périphérique 0 demande à écrire à l'adresse 10 ; c'est accepté.
Juste après, le périphérique 1 demande à lire à l'adresse 10 ; c'est refusé.

Le périphérique 1 ne pourra jamais lire l'adresse 10.

Les périphériques sont sollicités de la manière suivante lors de quatre tours successifs :

au premier tour, ils sont sollicités dans l'ordre 0 ; 1 ; 2 ; 3 ;
au deuxième tour, dans l'ordre 1 ; 2 ; 3 ; 0 ;
au troisième tour, 2 ; 3 ; 0 ; 1 ;
puis 3 ; 0 ; 1 ; 2 au dernier tour.
Et on recommence...

3.a. Préciser pour chacun de ces tours si le périphérique 0 peut écrire et si le périphérique 1 peut lire.

Réponse

Tour 1 : 0 ; 1 ; 2 ; 3
- 0 peut écrire, puis
- 1 ne peut pas lire
Tour 2 : 1 ; 2 ; 3 ; 0
- 1 peut lire, puis
- 0 ne peut pas écrire
Tour 3 : 2 ; 3 ; 0 ; 1
- 0 peut écrire, puis
- 1 ne peut pas lire
Tour 4 : 3 ; 0 ; 1 ; 2
- 0 peut écrire, puis
- 1 ne peut pas lire

3.b. En déduire la proportion des valeurs écrites par le périphérique 0 qui sont effectivement lues par le périphérique 1.

Réponse

Au tour 1, la valeur écrite par le périphérique 0 sera lue par le périphérique 1 au tour suivant.
Au tour 2, rien n'est écrit par le périphérique 0.
Au tour 3, la valeur écrite par le périphérique 0 ne sera jamais lue par le périphérique 1 ; en effet, une autre écriture intervient avant la prochaine lecture.
Au tour 4, la valeur écrite par le périphérique 0 ne sera jamais lue par le périphérique 1 ; en effet, une autre écriture intervient avant la prochaine lecture.

Ainsi, une seule valeur sur trois sera effectivement lue. La proportion est \(\frac13\).

On change la méthode d'ordonnancement : on détermine l'ordre des périphériques au cours d'un tour à l'aide de deux listes d'attente ATT_L et ATT_E établies au tour précédent.

Au cours d'un tour, on place dans la liste ATT_L toutes les opérations de lecture mises en attente, et dans la liste d'attente ATT_E toutes les opérations d'écriture mises en attente.

Au début du tour suivant, on établit l'ordre d'interrogation des périphériques en procédant ainsi :

on interroge ceux présents dans la liste ATT_L, par ordre croissant d'adresse,
on interroge ensuite ceux présents dans la liste ATT_E, par ordre croissant d'adresse,
puis on interroge les périphériques restants, par ordre croissant d'adresse.

4. Compléter et rendre avec la copie le tableau fourni en annexe 2, en utilisant l'ordonnancement décrit ci-dessus, sur 3 tours.

Annexe 2

Tour	N° périphérique	Adresse	Opération	Réponse ordonnanceur	`ATT_L`	`ATT_E`
1	0	`10`	écriture	`"OK"`	vide	vide
1	1	`10`	lecture	`"ATT"`	`(1, 10)`	vide
1	2	`11`	écriture
1	3	`11`	lecture
2	1	`10`	lecture			vide
2
2
2
3	0	`10`	écriture		vide	vide
3	1	`10`	lecture			vide
3	2	`11`	écriture	`"OK"`	`(1, 10)`	vide
3	3	`12`	lecture

Réponse

Tour	N° périphérique	Adresse	Opération	Réponse ordonnanceur	`ATT_L`	`ATT_E`
1	0	`10`	écriture	`"OK"`	vide	vide
1	1	`10`	lecture	`"ATT"`	`(1, 10)`	vide
1	2	`11`	écriture	`"OK"`	`(1, 10)`	vide
1	3	`11`	lecture	`"ATT"`	`(1, 10), (3, 11)`	vide
2	1	`10`	lecture	`"OK"`	`(3, 11)`	vide
2	3	`11`	lecture	`"OK"`	vide	vide
2	0	`10`	écriture	`"ATT"`	vide	`(0, 10)`
2	2	`12`	écriture	`"OK"`	vide	`(0, 10)`
3	0	`10`	écriture	`"OK"`	vide	vide
3	1	`10`	lecture	`"ATT"`	`(1, 10)`	vide
3	2	`11`	écriture	`"OK"`	`(1, 10)`	vide
3	3	`12`	lecture	`"OK"`	`(1, 10)`	vide

Les colonnes e0 et e1 du tableau suivant recensent les deux chiffres de l'écriture binaire de l'entier n de la première colonne.

nombre n	écriture binaire de n sur deux bits	e1	e0
0	00	0	0
1	01	0	1
2	10	1	0
3	11	1	1

L'ordonnanceur attribue à deux signaux sur le bus de données les valeurs de e0 et e1 associées au numéro du circuit qu'il veut sélectionner. On souhaite construire à l'aide des portes ET, OU et NON un circuit pour chaque périphérique.
Chacun des quatre circuits à construire prend en entrée deux signaux e0 et e1, le signal de sortie s valant 1 uniquement lorsque les niveaux de e0 et e1 correspondent aux bits de l'écriture en binaire du numéro du périphérique correspondant.

Par exemple, le circuit ci-dessous réalise la sélection du périphérique 3. En effet, le signal s vaut 1 si et seulement si e0 et e1 valent tous les deux 1.

flowchart LR
    e0---ET(ET)
    e1---ET
    ET---s
    style e0 stroke-width:0px,opacity:0
    style e1 stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

5.a. Recopier sur la copie et indiquer dans le circuit ci-dessous les entrées e0 et e1 de façon que ce circuit sélectionne le périphérique 1.

flowchart LR
    ea( )---NON(NON)---ET(ET)
    eb( )----ET
    ET---s
    style ea stroke-width:0px,opacity:0
    style eb stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

Réponse

flowchart LR
    ea(e1)---NON(NON)---ET(ET)
    eb(e0)----ET
    ET---s
    style ea stroke-width:0px,opacity:0
    style eb stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

5.b. Dessiner un circuit constitué d'une porte ET et d'une porte NON, qui sélectionne le périphérique 2.

Réponse

flowchart LR
    ea(e1)----ET(ET)
    eb(e0)---NON(NON)---ET
    ET---s
    style ea stroke-width:0px,opacity:0
    style eb stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

5.c. Dessiner un circuit permettant de sélectionner le périphérique 0.

Réponse

flowchart LR
    ea(e0)---NON1(NON)---ET(ET)
    eb(e1)---NON2(NON)---ET
    ET---s
    style ea stroke-width:0px,opacity:0
    style eb stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0