Programming, data structures & operating systems

# Programming, data structures & operating systems ## Objectifs et prérequis Ce chapitre vise à consolider les connaissances fondamentales en programmation C, structures de données, systèmes d'exploitation et logiciels système, tout en développant des compétences pratiques à travers deux projets concrets. À l'issue de ce chapitre, l'étudiant sera capable de : - Implémenter et manipuler des structures de données linéaires et non linéaires en C (listes, piles, files, arbres binaires de recherche). - Comprendre le rôle du système d'exploitation dans la gestion des processus, de la mémoire et des périphériques. - Développer un module d'indexation et de recherche de données en C utilisant des structures de données appropriées. - Concevoir un simulateur de allocation CPU et mémoire basé sur des algorithmes de planification et de gestion de mémoire réels. - Appliquer les bonnes pratiques de programmation système : gestion de la mémoire dynamique, pointeurs, fichiers, et modularité. **Prérequis** : - Maîtrise des bases du langage C (variables, types, opérateurs, structures de contrôle, fonctions). - Notions d'algorithmique de base (complexité en O(n), recherche linéaire/dichotomique). - Familiarité avec l'environnement de développement (compilateur GCC, éditeur de texte, ligne de commande sous Linux ou équivalent). - Compréhension des concepts de mémoire (stack vs heap) et de compilation (préprocessing, compilation, assemblage, édition de liens). --- ## I. Data Structures & C Programming Foundations ### 1.1. Structures de données linéaires : listes simplement chaînées Une **liste simplement chaînée** est une structure de données dynamique où chaque élément (nœud) contient une donnée et un pointeur vers le nœud suivant. Elle permet une insertion/suppression efficace en O(1) à la tête, mais une recherche en O(n). > **Définition** : Une liste simplement chaînée est définie par un pointeur `head` vers le premier nœud. Chaque nœud est une structure : > ```c > typedef struct Node { > int data; > struct Node* next; > } Node; > ``` **Propriétés** : - Allocation dynamique : chaque nœud est créé avec `malloc()`. - Pas d'accès aléatoire : il faut parcourir la liste depuis la tête. - Insertion en tête : O(1). - Suppression d'un nœud donné : O(n) si on ne connaît pas son prédécesseur. - Utilisation courante : implémentation de piles, files, gestion de listes de tâches. **Exemple résolu** : Insertion en tête et affichage d'une liste. ```c #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; void push(Node** head_ref, int new_data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node* node) { while (node != NULL) { printf("%d -> ", node->data); node = node->next; } printf("NULL\n"); } int main() { Node* head = NULL; push(&head, 3); push(&head, 2); push(&head, 1); printList(head); // Output: 1 -> 2 -> 3 -> NULL return 0; } ``` **Exercice 1** : Écrire une fonction `deleteNode(Node** head_ref, int key)` qui supprime la première occurrence d'un nœud contenant `key`. **Corrigé** : ```c void deleteNode(Node** head_ref, int key) { Node* temp = *head_ref; Node* prev = NULL; if (temp != NULL && temp->data == key) { *head_ref = temp->next; free(temp); return; } while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; prev->next = temp->next; free(temp); } ``` ### 1.2. Piles et files Une **pile** (stack) est une structure LIFO (Last In, First Out). Une **file** (queue) est une structure FIFO (First In, First Out). > **Définition (pile)** : Les opérations principales sont `push` (empiler) et `pop` (dépiler), toutes deux en O(1). > **Définition (file)** : Les opérations sont `enqueue` (ajouter à la fin) et `dequeue` (retirer du début), en O(1) si implémentée avec une liste chaînée ou un tableau circulaire. **Implémentation en C (pile avec liste chaînée)** : ```c typedef struct Stack { Node* top; } Stack; void stackPush(Stack* s, int value) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = value; new_node->next = s->top; s->top = new_node; } int stackPop(Stack* s) { if (s->top == NULL) { fprintf(stderr, "Erreur : pile vide\n"); exit(EXIT_FAILURE); } Node* temp = s->top; int value = temp->data; s->top = s->top->next; free(temp); return value; } ``` **Implémentation en C (file avec liste chaînée)** : ```c typedef struct Queue { Node* front; Node* rear; } Queue; void enqueue(Queue* q, int value) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = value; new_node->next = NULL; if (q->rear == NULL) { q->front = q->rear = new_node; return; } q->rear->next = new_node; q->rear = new_node; } int dequeue(Queue* q) { if (q->front == NULL) { fprintf(stderr, "Erreur : file vide\n"); exit(EXIT_FAILURE); } Node* temp = q->front; int value = temp->data; q->front = q->front->next; if (q->front == NULL) q->rear = NULL; free(temp); return value; } ``` **Exercice 2** : Implémenter une fonction `isPalindrome(Node* head)` qui vérifie si une liste d'entiers forme un palindrome en utilisant une pile. **Corrigé** : 1. Parcourir la liste et empiler chaque élément. 2. Parcourir à nouveau la liste, dépiler et comparer chaque élément. 3. Si tous correspondent → palindrome. Complexité : O(n) en temps, O(n) en espace. ### 1.3. Arbres binaires de recherche (BST) Un **arbre binaire de recherche** est un arbre où pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud, et toutes celles du sous-arbre droit sont supérieures. > **Définition** : > ```c > typedef struct BSTNode { > int data; > struct BSTNode* left; > struct BSTNode* right; > } BSTNode; > ``` **Propriétés** : - Recherche, insertion, suppression : O(h), où h est la hauteur de l'arbre. - Dans le pire cas (arbre dégénéré) : O(n). - Dans le meilleur cas (arbre équilibré) : O(log n). - Parcours : in-order (trié), pre-order, post-order. **Exemple résolu** : Insertion et recherche dans un BST. ```c BSTNode* insert(BSTNode* root, int value) { if (root == NULL) { BSTNode* new_node = (BSTNode*)malloc(sizeof(BSTNode)); new_node->data = value; new_node->left = new_node->right = NULL; return new_node; } if (value < root->data) root->left = insert(root->left, value); else if (value > root->data) root->right = insert(root->right, value); return root; } BSTNode* search(BSTNode* root, int value) { if (root == NULL || root->data == value) return root; if (value < root->data) return search(root->left, value); return search(root->right, value); } ``` **Exercice 3** : Écrire une fonction `inorderTraversal(BSTNode* root)` qui affiche les éléments du BST dans l'ordre croissant. **Corrigé** : ```c void inorderTraversal(BSTNode* root) { if (root != NULL) { inorderTraversal(root->left); printf("%d ", root->data); inorderTraversal(root->right); } } ``` **Exercice 4** : Écrire une fonction `minValueNode(BSTNode* node)` qui retourne le nœud avec la valeur minimale dans un BST. **Corrigé** : ```c BSTNode* minValueNode(BSTNode* node) { BSTNode* current = node; while (current && current->left != NULL) current = current->left; return current; } ``` --- ## II. Operating Systems & System Software ### 2.1. Rôle et fonctions du système d'exploitation Un **système d'exploitation (SE)** est un logiciel système qui gère les ressources matérielles d'un ordinateur et fournit des services communs aux programmes informatiques. > **Définition** : Le SE agit comme une interface entre le matériel et les logiciels applicatifs, assurant l'abstraction, la protection, et la gestion efficace des ressources. **Fonctions principales** : - **Gestion des processus** : création, planification, synchronisation, communication inter-processus (IPC). - **Gestion de la mémoire** : allocation, protection, échange (swapping), mémoire virtuelle. - **Gestion des fichiers** : création, lecture, écriture, organisation des systèmes de fichiers (ex: ext4, NTFS). - **Gestion des périphériques** : pilotes, interruptions, accès aux entrées/sorties (I/O). - **Protection et sécurité** : contrôle d'accès, authentification, isolation des processus. - **Interface utilisateur** : ligne de commande (CLI) ou interface graphique (GUI). **Logiciels système** : - **Noyau (kernel)** : cœur du SE, s'exécute en mode privilégié. - **Bibliothèques système** : fournissent des API pour accéder aux services du noyau (ex: libc, POSIX). - **Utilitaires** : commandes de base (ls, cp, grep, etc.). - **Shell** : interpréteur de commandes (ex: bash, sh). ### 2.2. Gestion des processus Un **processus** est un programme en cours d'exécution, comprenant son code, ses données, sa pile, ses registres, et son état. > **Définition** : Le SE maintient un **bloc de contrôle de processus (PCB)** pour chaque processus, contenant : > - État du processus (nouveau, prêt, exécutant, bloqué, terminé) > - Compteur d'instruction (PC) > - Registres CPU > - Informations de gestion de mémoire > - Informations de comptabilité > - État des E/S **Transitions d'état** : - **Nouveau → Prêt** : lors de la création. - **Prêt → Exécutant** : lorsque le planificateur choisit le processus. - **Exécutant → Bloqué** : lors d'une attente d'E/S ou d'un verrou. - **Bloqué → Prêt** : lorsque l'événement attendu se produit. - **Exécutant → Terminé** : après fin d'exécution ou appel à `exit()`. **Planification (scheduling)** : - **Objectif** : maximiser l'utilisation du CPU, minimiser le temps de réponse, assurer l'équité. - **Algorithmes courants** : - **FCFS (First Come, First Served)** : non préemptif, simple mais peut entraîner l'effet de convoi. - **SJF (Shortest Job First)** : préemptif ou non, optimal pour le temps moyen d'attente mais nécessite connaissance du temps d'exécution. - **Round Robin (RR)** : préemptif, chaque processus reçoit un quantum de temps fixe. - **Priorité** : attribue une priorité à chaque processus ; peut entraîner la famine. - **Multilevel Feedback Queue** : combine plusieurs files avec des quantums et priorités différents. **Exemple résolu** : Calcul du temps moyen d'attente avec FCFS pour 3 processus : P1: arrivée à 0, durée 6 P2: arrivée à 1, durée 3 P3: arrivée à 2, durée 4 Ordre d'exécution : P1 (0-6), P2 (6-9), P3 (9-13) Temps d'attente : P1: 0 - 0 = 0 P2: 6 - 1 = 5 P3: 9 - 2 = 7 Moyenne = (0+5+7)/3 = 4 **Exercice 5** : Calculer le temps moyen d'attente avec SJF non préemptif pour les mêmes processus. **Corrigé** : À t=0 : seul P1 disponible → exécuter P1 (0-6) À t=6 : P2 (durée 3) et P3 (durée 4) disponibles → choisir P2 (6-9) À t=9 : exécuter P3 (9-13) Temps d'attente : P1: 0 P2: 6-1=5 P3: 9-2=7 Moyenne = 4 (identique à FCFS ici car P1 est le plus court au départ) ### 2.3. Gestion de la mémoire La **gestion de la mémoire** vise à allouer de la mémoire aux processus de manière efficace et sécurisée. > **Définition** : La **mémoire virtuelle** permet à chaque processus de disposer d'un espace d'adressage logique indépendant, plus grand que la mémoire physique disponible, grâce à la pagination et à l'échange sur disque. **Mécanismes** : - **Pagination** : division de la mémoire en blocs de taille fixe appelés **pages** (généralement 4 Ko). - **Table des pages** : associe chaque numéro de page logique à un numéro de cadre physique (ou indique qu'elle est sur disque). - **TLB (Translation Lookaside Buffer)** : cache matériel pour accélérer la traduction d'adresses. - **Échange (swapping)** : déplacement d'une page entière entre mémoire vive et disque lorsqu'elle n'est pas utilisée récemment. - **Algorithmes de remplacement de page** : - **FIFO (First In, First Out)** : remplace la page la plus ancienne. - **LRU (Least Recently Used)** : remplace la page la moins récemment utilisée (optimal en pratique). - **Optimal** : remplace la page qui ne sera pas utilisée le plus longtemps dans le futur (inutile en pratique car nécessite connaissance du futur). - **Clock** : approximation de LRU avec un bit d'utilisation. **Exemple résolu** : Simulation de FIFO avec 3 cadres et séquence de références : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Étapes : - Réf 1 : défaut → charger 1 → [1] - Réf 2 : défaut → charger 2 → [1,2] - Réf 3 : défaut → charger 3 → [1,2,3] - Réf 4 : défaut → remplacer 1 (FIFO) → [4,2,3] - Réf 1 : défaut → remplacer 2 → [4,1,3] - Réf 2 : défaut → remplacer 3 → [4,1,2] - Réf 5 : défaut → remplacer 4 → [5,1,2] - Réf 1 : hit - Réf 2 : hit - Réf 3 : défaut → remplacer 1 → [5,3,2] - Réf 4 : défaut → remplacer 5 → [4,3,2] - Réf 5 : défaut → remplacer 3 → [4,5,2] Total défauts : 9 **Exercice 6** : Répéter l'exercice avec l'algorithme LRU. **Corrigé** : - Réf 1 : défaut → [1] - Réf 2 : défaut → [1,2] - Réf 3 : défaut → [1,2,3] - Réf 4 : défaut → remplacer 1 (LRU) → [2,3,4] - Réf 1 : défaut → remplacer 2 → [3,4,1] - Réf 2 : défaut → remplacer 3 → [4,1,2] - Réf 5 : défaut → remplacer 4 → [1,2,5] - Réf 1 : hit → [2,5,1] (mettre à jour l'usage) - Réf 2 : hit → [5,1,2] - Réf 3 : défaut → remplacer 5 → [1,2,3] - Réf 4 : défaut → remplacer 1 → [2,3,4] - Réf 5 : défaut → remplacer 2 → [3,4,5] Total défauts : 9 (dans ce cas, même résultat que FIFO) ### 2.4. Logiciels système et appels système Les **appels système (system calls)** sont l'interface par laquelle un programme utilisateur demande un service au noyau du SE. > **Définition** : Un appel système provoque une interruption logicielle qui bascule le processeur du mode utilisateur au mode noyau, permettant l'exécution sécurisée de privilégiés. **Exemples courants (POSIX/Linux)** : - `fork()` : crée un nouveau processus (copie du processus appelant). - `exec()` : remplace l'image mémoire du processus par un nouveau programme. - `wait()` : attend la fin d'un processus fils. - `open()`, `read()`, `write()`, `close()` : opérations sur les fichiers. - `malloc()` : bien que souvent perçu comme une fonction de bibliothèque, il utilise finalement `brk()` ou `mmap()` (appels système) pour obtenir de la mémoire du noyau. - `signal()` : gère les signaux (ex: SIGINT, SIGTERM). **Différence entre appel système et fonction de bibliothèque** : - Une **fonction de bibliothèque** (ex: `printf()`) peut exécuter du code en mode utilisateur avant d'effectuer un appel système. - Un **appel système** est toujours une transition vers le noyau et implique un coût de contexte plus élevé. **Exemple résolu** : Utilisation de `fork()` et `exec()` pour exécuter une commande externe. ```c #include <stdio.h> #include <unistd.h> #include <sys/wait.h> int main() { pid_t pid = fork(); if (pid == 0) { // Processus fils execlp("ls", "ls", "-l", NULL); perror("execlp failed"); // Seulement si execlp échoue exit(EXIT_FAILURE); } else if (pid > 0) { // Processus père wait(NULL); // Attend la fin du fils printf("Child process completed.\n"); } else { perror("fork failed"); exit(EXIT_FAILURE); } return 0; } ``` **Exercice 7** : Modifier l'exemple ci-dessus pour exécuter `ls -la /tmp` au lieu de `ls -l`. **Corrigé** : Remplacer `execlp("ls", "ls", "-l", NULL);` par `execlp("ls", "ls", "-la", "/tmp", NULL);` --- ## III. Hands-on C Project: Data Indexing & Search Module ### Objectif du projet Développer un module en C permettant d'indexer un ensemble de documents texte (fichiers .txt) et d'effectuer des recherches rapides par mot-clé, en utilisant une table de hachage (hash table) associée à des listes simplement chaînées pour gérer les collisions. ### Spécifications - Lire tous les fichiers .txt d'un répertoire spécifié. - Pour chaque mot (séparé par des espaces, ponctuation, retour ligne), enregistrer : - Le mot lui-même (en minuscules). - Le nom du fichier où il apparaît. - Le numéro de ligne dans le fichier. - Construire un index : table de hachage où chaque entrée pointe vers une liste chaînée d'occurrences. - Permettre à l'utilisateur de saisir un mot-clé et afficher toutes les occurrences (fichier + ligne). - Gérer la mémoire dynamiquement : libérer toutes les allocations à la fin. - Ignorer les mots vides (stop words) courants : "the", "and", "or", "but", "in", "on", "at", "to", "a", "an". ### Structure de données proposée ```c #define TABLE_SIZE 101 typedef struct Occurrence { char* filename; int line_number; struct Occurrence* next; } Occurrence; typedef struct HashNode { char* word; Occurrence* occurrences; struct HashNode* next; // pour gérer les collisions dans la table de hachage } HashNode; typedef struct { HashNode* table[TABLE_SIZE]; } HashTable; ``` ### Fonctions clés 1. **`unsigned int hash(const char* str)`** : fonction de hachage simple (ex: somme des codes ASCII modulo TABLE_SIZE). 2. **`void toLowerCase(char* str)`** : convertit une chaîne en minuscules. 3. **`int isStopWord(const char* word)`** : vérifie si le mot est dans la liste des mots vides. 4. **`void insertWord(HashTable* ht, const char* word, const char* filename, int line_num)`** : - Calcule l'index de hachage. - Recherche si le mot existe déjà dans la chaîne à cet index. - Si oui : ajoute une nouvelle occurrence à la liste des occurrences du mot. - Si non : crée un nouveau nœud HashNode, l'insère en tête de la chaîne, puis ajoute l'occurrence. 5. **`void searchWord(HashTable* ht, const char* word)`** : - Calcule l'index de hachage. - Parcourt la chaîne à cet index pour trouver le mot. - Si trouvé : affiche toutes les occurrences (fichier, ligne). - Sinon : affiche "Mot non trouvé". 6. **`void freeHashTable(HashTable* ht)`** : libère récursivement toute la mémoire allouée (mots, occurrences, nœuds). ### Étapes d'implémentation 1. Parcourir le répertoire avec `opendir()`, `readdir()`, `closedir()`. 2. Pour chaque fichier .txt : - L'ouvrir avec `fopen()`. - Lire ligne par ligne avec `fgets()`. - Pour chaque ligne : - Extraire les mots (en utilisant `strtok()` ou parsing manuel). - Pour chaque mot : - Appliquer `toLowerCase()`. - Vérifier `isStopWord()`. - Si valide : appeler `insertWord()`. 3. Après l'indexation : - Boucle de recherche : demander un mot à l'utilisateur, appeler `searchWord()`, répéter jusqu'à saisie de "exit". 4. Libérer la table de hachage avec `freeHashTable()`. ### Exemple résolu (extrait) Fichier `doc1.txt` : ``` Hello world This is a test ``` Après traitement : - "hello" → fichier: doc1.txt, ligne: 1 - "world" → fichier: doc1.txt, ligne: 1 - "this" → fichier: doc1.txt, ligne: 2 - "is" → stop word → ignoré - "a" → stop word → ignoré - "test" → fichier: doc1.txt, ligne: 2 Recherche de "world" : ``` Found in: doc1.txt (line 1) ``` ### Exercice 8** : Écrire la fonction `toLowerCase(char* str)` en C. **Corrigé** : ```c void toLowerCase(char* str) { for (int i = 0; str[i]; i++) { if (str[i] >= 'A' && str[i] <= 'Z') str[i] = str[i] + ('a' - 'A'); } } ``` ### Exercice 9** : Écrire la fonction `isStopWord(const char* word)` en utilisant un tableau statique de mots vides. **Corrigé** : ```c int isStopWord(const char* word) { const char* stop_words[] = {"the", "and", "or", "but", "in", "on", "at", "to", "a", "an"}; int n = sizeof(stop_words) / sizeof(stop_words[0]); for (int i = 0; i < n; i++) { if (strcmp(word, stop_words[i]) == 0) return 1; } return 0; } ``` ### Exercice 10** : Écrire la fonction `insertWord()` en détail. **Corrigé** : ```c void insertWord(HashTable* ht, const char* word, const char* filename, int line_num) { unsigned int index = hash(word) % TABLE_SIZE; HashNode* current = ht->table[index]; // Rechercher si le mot existe déjà while (current != NULL) { if (strcmp(current->word, word) == 0) { // Mot trouvé : ajouter une occurrence Occurrence* new_occ = (Occurrence*)malloc(sizeof(Occurrence)); new_occ->filename = strdup(filename); new_occ->line_number = line_num; new_occ->next = current->occurrences; current->occurrences = new_occ; return; } current = current->next; } // Mot non trouvé : créer un nouveau nœud HashNode* new_node = (HashNode*)malloc(sizeof(HashNode)); new_node->word = strdup(word); new_node->occurrences = NULL; new_node->next = ht->table[index]; ht->table[index] = new_node; // Ajouter la première occurrence Occurrence* new_occ = (Occurrence*)malloc(sizeof(Occurrence)); new_occ->filename = strdup(filename); new_occ->line_number = line_num; new_occ->next = NULL; new_node->occurrences = new_occ; } ``` --- ## IV. Hands-on OS Project: CPU & Memory Allocation Simulator ### Objectif du projet Simuler les comportements d'un noyau de système d'exploitation concernant : 1. La **planification du CPU** avec l'algorithme Round Robin (RR). 2. La **gestion de la mémoire** avec l'algorithme de remplacement de page LRU (Least Recently Used). Le simulateur lit une séquence d'instructions provenant d'un fichier d'entrée et affiche l'état du système à chaque étape. ### Spécifications d'entrée Fichier d'entrée (`input.txt`) contenant des lignes de la forme : `<timestamp> <process_id> <instruction_type> <address>` - `timestamp` : entier, temps auquel l'instruction est émise (non nécessairement séquentiel). - `process_id` : entier identifiant le processus (0, 1, 2, ...). - `instruction_type` : soit `CPU` (instruction de calcul), soit `MEM` (accès mémoire à `address`). - `address` : adresse logique entière (pour les instructions MEM uniquement). ### Comportement attendu - À chaque unité de temps (à partir de t=0), le simulateur : 1. Active tous les processus dont le `timestamp` <= temps courant et qui ne sont pas encore terminés. 2. Applique le planificateur RR avec un quantum fixe (ex: q=2 unités de temps). 3. Pour le processus sélectionné : - Si l'instruction suivante est `CPU` : l'exécuter pendant 1 unité de temps (décrémenter son compteur d'instructions CPU restantes). - Si l'instruction suivante est `MEM` : - Traduire l'adresse logique en adresse physique via la table des pages (simulée). - Vérifier si la page est en mémoire (hit) ou sur disque (fault). - En cas de fault : charger la page depuis le disque, appliquer LRU pour choisir une page à évincer si la mémoire est pleine. - Mettre à jour l'historique d'utilisation (pour LRU). 4. Afficher l'état : temps courant, processus en cours d'exécution, file prête, état de la mémoire (cadres occupés, pages présentes), nombre de faults. 5. Passer au temps suivant. ### Structures de données ```c #define MAX_PROCESSES 10 #define MEMORY_FRAMES 3 #define PAGE_SIZE 1024 // taille logique d'une page (ex: adresses 0-1023 = page 0) typedef struct { int pid; int remaining_cpu_time; // temps CPU restant pour l'instruction courante int next_instruction_index; // index dans la liste d'instructions du processus int is_complete; } Process; typedef struct { int page_number; // numéro de page logique int frame_number; // numéro de cadre physique (-1 si pas en mémoire) int last_used; // timestamp d'utilisation récente (pour LRU) } PageTableEntry; typedef struct { int frame_number; int page_number; // page logique actuellement chargée dans ce cadre int last_used; // pour LRU } MemoryFrame; ``` ### Algorithmes - **Planification RR** : - File prête (FIFO) des processus actifs. - Chaque processus sélectionné s'exécute pendant min(quantum, temps CPU restant de l'instruction courante). - Après expiration du quantum ou fin de l'instruction, il est remis à la fin de la file s'il n'est pas terminé. - **Remplacement de page LRU** : - Chaque accès à une page met à jour son champ `last_used` au timestamp courant. - En cas de fault et mémoire pleine : remplacer la page avec la plus petite valeur de `last_used` (la moins récemment utilisée). ### Étapes d'implémentation 1. Lire le fichier d'entrée et construire pour chaque processus une liste d'instructions (type, adresse si MEM). 2. Initialiser : - Tous les processus à l'état non actif. - Table des pages vide pour chaque processus (toutes les entrées pointent vers -1). - Mémoire physique : tous les cadres libres. - Temps courant = 0. 3. Boucle principale jusqu'à ce que tous les processus soient terminés : - Activer les nouveaux processus (timestamp <= temps courant). - Si la file prête est vide : avancer le temps au prochain timestamp d'arrivée. - Sinon : - Défilez le premier processus de la file prête. - Déterminez le temps d'exécution : `time_slice = min(quantum, remaining_cpu_time)` si CPU, ou 1 unité si MEM (on suppose qu'une accès mémoire prend 1 unité). - Exécuter l'instruction : - Si CPU : décrémenter `remaining_cpu_time` de `time_slice`. - Si MEM : - Calculer numéro de page : `page = address / PAGE_SIZE`. - Vérifier la table des pages du processus pour cette page. - Si `frame_number == -1` : fault → - Si un cadre libre existe : le prendre. - Sinon : choisir le cadre avec le plus petit `last_used` (LRU), sauvegarder sa page si nécessaire (on ignore l'écriture ici), charger la nouvelle page. - Mettre à jour `last_used` de la page et du cadre au timestamp courant. - Mettre à jour la table des pages. - Après exécution : - Si l'instruction courante est terminée (remaining_cpu_time == 0 pour CPU, ou après 1 unité pour MEM) : - Passer à l'instruction suivante du processus. - Si aucune instruction restante : marquer le processus comme terminé. - Sinon : remettre le processus en file prête avec son temps restant. - Afficher l'état. - Incrémenter le temps courant de 1 (ou de `time_slice` si on veut optimiser, mais pour simplifier on fait pas à pas). ### Exemple résolu (extrait) Fichier `input.txt` : ``` 0 0 CPU 0 0 0 MEM 500 1 1 CPU 0 1 1 MEM 2000 2 0 CPU 0 ``` PAGE_SIZE = 1024 → pages : - 500 → page 0 - 2000 → page 1 (puisque 2000/1024 = 1) Supposons quantum = 2, MEMORY_FRAMES = 2. **Temps t=0** : - Activer P0 (timestamp 0). - File prête : [P0] - P0 sélectionné : instruction CPU (temps restant CPU = on suppose 1 unité par instruction CPU pour simplifier → disons que chaque ligne "CPU" = 1 unité CPU). - Exécuter 1 unité de CPU (quantum=2, mais on ne prend que ce qui est nécessaire). - Après : P0 a encore une instruction MEM à faire. - Remettre P0 en file prête. - État : temps=0, P0 en cours, file prête=[P0], mémoire vide, faults=0. **Temps t=1** : - Aucun nouveau processus (timestamp suivant à 1 pour P1). - Activer P1 (timestamp 1 <= 1). - File prête : [P0, P1] - Sélectionner P0 : prochaine instruction MEM 500 → page 0. - Page 0 non en mémoire → fault. - Charger page 0 dans cadre 0 (libre). - Mettre à jour last_used de cadre 0 et page 0 de P0 à t=1. - faults=1. - Après exécution : P0 terminé (plus d'instructions). - État : temps=1, P0 terminé, file prête=[P1], mémoire: cadre0=page0(P0), faults=1. **Temps t=2** : - Activer P2? Non, pas de P2. - File prête : [P1] - Sélectionner P1 : instruction CPU → exécuter 1 unité. - Après : P1 a encore instruction MEM. - Remettre P1 en file prête. - État : temps=2, P1 en cours, file prête=[P1], mémoire inchangée, faults=1. **Temps t=3** : - File prête : [P1] - Sélectionner P1 : instruction MEM 2000 → page 1. - Page 1 non en mémoire → fault. - Charger page 1 dans cadre 1 (libre). - Mettre à jour last_used de cadre 1 et page 1 de P1 à t=3. - faults=2. - Après : P1 terminé. - État : temps=3, P1 terminé, file prête=[], mémoire: cadre0=page0(P0), cadre1=page1(P1), faults=2. **Temps t=4+** : aucun processus actif → fin. ### Exercice 11** : Écrire la fonction qui calcule le numéro de page à partir d'une adresse logique. **Corrigé** : ```c int getPageNumber(int address, int page_size) { return address / page_size; } ``` ### Exercice 12** : Écrire la fonction qui sélectionne le cadre à remplacer en utilisant LRU (le cadre avec la plus petite valeur de `last_used`). **Corrigé** : ```c int selectLRUFrame(MemoryFrame frames[], int num_frames) { int lru_index = 0; for (int i = 1; i < num_frames; i++) { if (frames[i].last_used < frames[lru_index].last_used) { lru_index = i; } } return lru_index; } ``` ### Exercice 13** : Dans le simulateur, après un accès mémoire réussi (hit), que faut-il mettre à jour pour maintenir la propriété LRU ? **Corrigé** : Il faut mettre à jour le champ `last_used` de la page accédée (dans la table des pages) et du cadre mémoire où elle réside, en le définissant égal au timestamp courant. ### Exercice 14** : Pourquoi utilise-t-on un timestamp global dans le simulateur plutôt que le temps d'exécution réel de chaque processus ? **Corrigé** : Le timestamp global permet de synchroniser l'état de tous les processus et de la mémoire selon un temps logique commun, essentiel pour déterminer lequel des processus est arrivé (timestamp <= temps courant) et pour appliquer de manière cohérente l'algorithme LRU basé sur la récence d'accès. ---