Machines de Turing, Unité Centrale, Ordonnancement, Gestion de la Mémoire
1. Diagramme des transitions : Dessiner les états et les transitions en utilisant les règles fournies.
2. Calcul pour un mot donné : Simuler le fonctionnement de la machine étape par étape, en notant l'état, la position sur le ruban, et le contenu du ruban à chaque transition.
Voici le diagramme des transitions pour la machine de Turing définie :
États : 0, 1, 2 (2 est l'état final)
Transitions :
• 0 → 0 (lire 'b', écrire 'b', déplacer à droite)
• 0 → 1 (lire 'a', écrire 'a', déplacer à droite)
• 1 → 0 (lire 'a', écrire 'a', déplacer à droite)
• 1 → 1 (lire 'a', écrire 'a', déplacer à droite)
• 1 → 1 (lire 'b', écrire 'b', déplacer à droite)
• 1 → 2 (lire '#', écrire '#', déplacer à droite)
Ruban initial : b a a b #
État initial : 0
Position initiale : sur le premier caractère ('b')
| Étape | État | Contenu du ruban | Position | Action |
|---|---|---|---|---|
| 1 | 0 | b a a b # |
b | Lire 'b' → écrire 'b', déplacer à droite |
| 2 | 0 | b a a b # |
a | Lire 'a' → écrire 'a', passer à l'état 1, déplacer à droite |
| 3 | 1 | b a a b # |
a | Lire 'a' → écrire 'a', déplacer à droite |
| 4 | 1 | b a a b # |
b | Lire 'b' → écrire 'b', déplacer à droite |
| 5 | 1 | b a a b # |
# | Lire '#' → écrire '#', passer à l'état 2, déplacer à droite |
Résultat : Le calcul est acceptant, car la machine atteint l'état final 2.
1. Analyser le schéma : Identifier les composants (Compteur Ordinal, Accumulateur, UAL, etc.) et les bus (adresses, données).
2. Simuler l'exécution : Pour chaque instruction, décrire les micro-opérations (ex: LEC, CAD, ADD, etc.) et mettre à jour les registres et bus.
Programme : Soustraire le nombre 3H (à l'adresse F820H) du nombre 9H (à l'adresse F810H) et ranger le résultat à l'adresse F820H.
| Étape | Micro-commandes | Compteur Ordinal | Accumulateur | Registre Instruction | Bus Adresse | Bus Données | Registre Mot |
|---|---|---|---|---|---|---|---|
| Initialisation | - | 0001 | X | X | - | - | X |
| 1ère Instruction (LD A, (F810H)) | LOO, PSR, LEC, LMM, CRI, ICO | 0001 → 0002 | X | 3A F8 10 | 0001 → F810 | 3A F8 10 | 9 |
| Exécution LD | CAD, PSR, LEC, LMM, CEA, NOP, CRA | 0002 | 9 | 3A F8 10 | F810 | 9 | 9 |
| 2ème Instruction (SUB A, (F820H)) | LOO, PSR, LEC, LMM, CRI, ICO | 0002 → 0003 | 9 | D6 F8 20 | 0002 → F820 | D6 F8 20 | 3 |
| Exécution SUB | CAD, PSR, LEC, LMM, CEA, CEB, SUB, CRA | 0003 | 6 | D6 F8 20 | F820 | 3 | 3 |
| 3ème Instruction (LD (F820H), A) | LOO, PSR, LEC, LMM, CRI, ICO | 0003 → 0004 | 6 | 32 F8 20 | 0003 → F820 | 32 F8 20 | 6 |
| Exécution LD (F820H) | CAD, PSR, EDA, EMM, ECR | 0004 | 6 | 32 F8 20 | F820 | 6 | 6 |
1. Tourniquet (Round Robin) :
• Utiliser un quantum de 200 ms.
• Alterner entre les processus prêts, en respectant l'ordre d'arrivée.
• Bloquer un processus si nécessaire et le remettre en file à sa reprise.
2. Ordonnancement à 2 niveaux (Unix) :
• Quantum de 100 ms.
• Un "top" toutes les 25 ms pour chaque processus en cours.
• Réévaluer les priorités toutes les secondes : nouvelle_priorité = priorité_initiale + nb_top/2.
• Toujours exécuter le processus prêt avec la priorité la plus élevée.
| Temps | Processus en cours | File d'attente | Événement |
|---|---|---|---|
| 10h00'00" | A | B, C | Début de A (priorité 10) |
| 10h00'00,2 | A | B, C | A bloque après 0,3s (à 10h00'00,3) |
| 10h00'00,3 | B | C | A bloqué, B commence |
| 10h00'00,5 | B | C | Fin de B (durée 0,9s) |
| 10h00'01,4 | C | A, D | A et C reprennent (C commence) |
| 10h00'01,6 | C | A, D | Fin de C (durée 0,6s) |
| 10h00'01,8 | A | D | A reprend (il reste 0,9s) |
| 10h00'02,7 | A | D | Fin de A |
| 10h00'02,9 | D | - | D commence (priorité 16) |
| 10h00'04,2 | D | - | Fin de D |
Ordre de fin : B → C → A → D
| Temps | Processus en cours | Priorité | Nb tops | File d'attente | Événement |
|---|---|---|---|---|---|
| 10h00'00" | A | 10 | 0 | B, C | Début de A |
| 10h00'00,1 | A | 10 | 4 | B, C | Top toutes les 25ms |
| 10h00'00,3 | A | 10 | 12 | B, C | A bloque |
| 10h00'00,3 | B | 10 | 0 | C | B commence |
| 10h00'01,0 | B | 12 | 28 | C | Réévaluation des priorités |
| 10h00'01,4 | D | 16 | 0 | A, C | D arrive (priorité 16) |
| 10h00'02,4 | D | 16 | 40 | A, C | Réévaluation des priorités |
| 10h00'03,7 | D | 16 | 68 | A, C | Fin de D |
| 10h00'03,7 | A | 22 | 0 | C | A reprend (priorité 22) |
| 10h00'04,6 | A | 22 | 36 | C | Fin de A |
| 10h00'04,6 | C | 22 | 0 | - | C reprend (priorité 22) |
| 10h00'05,2 | C | 22 | 24 | - | Fin de C |
Ordre de fin : D → A → C → B
1. Segmentation pure :
• Adresse physique = adresse de base du segment + déplacement.
• Vérifier que le déplacement est inférieur à la taille du segment.
2. Segmentation paginée :
• Diviser le déplacement par la taille de la page (4 Ko = 4096 octets) pour obtenir le numéro de page virtuelle et l'offset.
• Utiliser la table de correspondance pour trouver le numéro de page physique.
• Adresse physique = (numéro de page physique × 4096) + offset.
3. Remplacement de pages (FIFO/LRU) :
• Simuler l'évolution de la mémoire en suivant la liste des pages référencées.
• Pour FIFO : remplacer la page la plus anciennement chargée.
• Pour LRU : remplacer la page la moins récemment utilisée.
| Adresse virtuelle | N° segment | Déplacement | Adresse de base | Adresse physique | Validation |
|---|---|---|---|---|---|
| (0, 8196) | 0 | 8196 | 8500 | 8500 + 8196 = 16696 | Valide (8196 < 16394) |
| (1, 1024) | 1 | 1024 | 10 | 10 + 1024 = 1034 | Valide (1024 < 8250) |
| (2, 30000) | 2 | 30000 | 29990 | 29990 + 30000 = 59990 | Invalide (30000 > 32768) |
| (3, 4090) | 3 | 4090 | 24900 | 24900 + 4090 = 28990 | Invalide (4090 > 4084) |
| Adresse virtuelle | N° segment | Déplacement | N° page virtuelle | Offset | N° page physique | Adresse physique | Validation |
|---|---|---|---|---|---|---|---|
| (0, 8196) | 0 | 8196 | 8196 / 4096 = 2 | 8196 % 4096 = 40 | 15 (d'après la table) | (15 × 4096) + 40 = 62440 | Valide |
| (1, 1024) | 1 | 1024 | 1024 / 4096 = 0 | 1024 % 4096 = 1024 | 5 (d'après la table) | (5 × 4096) + 1024 = 21504 | Valide |
| (2, 30000) | 2 | 30000 | 30000 / 4096 ≈ 7 | 30000 % 4096 = 1328 | 2 (d'après la table) | (2 × 4096) + 1328 = 9456 | Valide |
| (3, 4090) | 3 | 4090 | 4090 / 4096 ≈ 0 | 4090 % 4096 = 4090 | 8 (d'après la table) | (8 × 4096) + 4090 = 36826 | Invalide (4090 > 4084) |
Liste des pages : 4, 5, 6, 8, 4, 9, 6, 1, 2, 4, 6, 1, 0
| Étape | Page référencée | Mémoire | Défaillance ? | Page remplacée |
|---|---|---|---|---|
| 1 | 4 | [4, -, -, -] | Oui | - |
| 2 | 5 | [4, 5, -, -] | Oui | - |
| 3 | 6 | [4, 5, 6, -] | Oui | - |
| 4 | 8 | [4, 5, 6, 8] | Oui | - |
| 5 | 4 | [4, 5, 6, 8] | Non | - |
| 6 | 9 | [9, 5, 6, 8] | Oui | 4 |
| 7 | 6 | [9, 5, 6, 8] | Non | - |
| 8 | 1 | [9, 1, 6, 8] | Oui | 5 |
| 9 | 2 | [9, 1, 2, 8] | Oui | 6 |
| 10 | 4 | [4, 1, 2, 8] | Oui | 9 |
| 11 | 6 | [4, 6, 2, 8] | Oui | 1 |
| 12 | 1 | [1, 6, 2, 8] | Oui | 4 |
| 13 | 0 | [1, 0, 2, 8] | Oui | 6 |
| Étape | Page référencée | Mémoire | Défaillance ? | Page remplacée |
|---|---|---|---|---|
| 1 | 4 | [4, -, -, -] | Oui | - |
| 2 | 5 | [4, 5, -, -] | Oui | - |
| 3 | 6 | [4, 5, 6, -] | Oui | - |
| 4 | 8 | [4, 5, 6, 8] | Oui | - |
| 5 | 4 | [4, 5, 6, 8] | Non | - |
| 6 | 9 | [4, 9, 6, 8] | Oui | 5 |
| 7 | 6 | [4, 9, 6, 8] | Non | - |
| 8 | 1 | [1, 9, 6, 8] | Oui | 4 |
| 9 | 2 | [1, 2, 6, 8] | Oui | 9 |
| 10 | 4 | [4, 2, 6, 8] | Oui | 1 |
| 11 | 6 | [4, 2, 6, 8] | Non | - |
| 12 | 1 | [4, 1, 6, 8] | Oui | 2 |
| 13 | 0 | [0, 1, 6, 8] | Oui | 4 |