Operating systems

Portail informatique

CF2 -- TP noté 2018-2019

Modalités

Durée : 3 heures

Tous documents autorisés.

Les exercices 2, 3 et 4 sont indépendants les uns des autres. Aussi, n'hésitez pas à lire tout le sujet avant de commencer pour déterminer l'ordre dans lequel vous souhaitez traiter les questions.

Le barème est donné à titre indicatif des poids entre les différents exercices.

Préparation

cd votreRepertoireDeTravailPourCSC4508 wget http://www-inf.telecom-sudparis.eu/COURS/CSC4508/Supports/CF/2018-2019/cf2/TPNote2019.tgz tar xvfz TPNote2019.tgz mv TPNote2019 ${USER}_TPNote2019 cd ${USER}_TPNote2019

Livraison

La « livraison » de votre travail en fin de TP noté se fera par remontée sous Moodle (rubrique « TP noté de 3 heures ») du fichier d'extension tgz constitué de la manière suivante :

cd votreRepertoireDeTravailPourCSC4508 tar cvfz ${USER}.tgz ${USER}_TPNote2019

Liste chainée (7 points)

Vous avez chargé un étudiant de développer un programme remplissant une liste de valeurs aléatoire. Le programme doit ensuite trier la liste, l'afficher, puis libérer la mémoire allouée. Malheureusement, l'étudiant a décidé d'arrêter le travail pour se consacrer à d'autres occupations plus à son goût. Vous vous retrouvez donc avec le programme inachevé exercice2/linked_list.c.

1 point

Bien que le programme compile sans warning, le programme génère une erreur de segmentation à l'exécution.

Dans le répertoire exercice2/Q1, corrigez le programme pour qu'il s'exécute sans erreur.

Si vous êtes bloqué sur cette question, appelez le professeur qui vous donnera la solution. Dans ce cas vous n'aurez bien sûr pas les points de cette question, mais vous pourrez continuer la suite de l'exercice.

3 points

Les blocs mémoire alloués dans la fonction list_add ne sont jamais libérés. Cela peut poser problème car vous envisagez d'utiliser ce programme pour manipuler de nombreuses listes.

Implémentez la fonction free_list dans le fichier exercice2/Q2/linked_list.c. Cette fonction doit libérer les blocs mémoire d'une liste etremettre à NULL le pointeur list déclaré dans la fonction main.

La dernière partie manquante dans le programme est la fonction sort_list. Cette fonction trie la liste suivant la valeur du champs value des noeuds.

Implémentez la fonction sort_list dans le fichier exercice2/Q3/linked_list.c.

Jobs (8 points)

Le programme exercice3/jobs.c crée NJOBS jobs qui doivent être traités par la fonction process_job(). Le résultat de chaque job est écrit dans le fichier results.dat de façon à ce que le fichier contienne, à la fin de l'exécution du programme :

AAAABBBBCCCCDDDDEEEE...XXXX

AAAA est le résultat (écrit en binaire) du job 0, BBBB le résultat du job 1, etc.

La liste des jobs à traiter est dans la liste chaînée jobs qui pointe vers le premier élément de la liste (ou NULL si la liste ne contient aucun élément). Chaque élément pointe vers l'élément suivant à traiter (sauf le dernier, qui pointe sur NULL).

À la fin du programme, la fonction check_result vérifie que le contenu du fichier est correct.

3 points

Dans le répertoire exercice3/Q1, complétez le programme de manière à ce que les résultats des jobs soient écrits dans le fichier "results.dat". Il vous est demandé ici de compléter les fonctions suivantes:

  • init_workers(): ajouter le code permettant d'ouvrir le fichier
  • finalize_workers() : ajouter le code permettant de fermer le fichier
  • save_result(): ajouter le code permettant d'écrire le résultat d'un job (j->res) dans le fichier La fonction check_result, appelée à la fin du programme vérifie que chaque job a écrit le résultat au bon endroit du fichier.

5 points

On souhaite maintenant paralléliser le traitement des jobs afin d'exploiter les processeurs multi-coeurs des machines.

Recopiez les fichiers que vous avez modifiés lors de la question 1 dans le répertoire exercice3/Q2. Complétez ensuite ce code afin que:

  • La fonction init_workers crée MAX_PARALLEL_JOBS threads.
  • Les threads attendent que des jobs soient soumis pour les traiter
  • La fonction finalize_workers signifie aux threads qu'il n'y a plus de job à soumettre (par exemple, en soumettant un job avec un 'identifiant particulier, ou en utilisant une primitive de synchronisation) , et qu'elle attende que tous les threads aient fini de traiter les jobs soumis.
  • Tous les accès concurrents à des structures de données ou ressources partagées soient protégés correctement.

XV6 - Mémoire partagée (7 points)

Commencez par donner le code de xv6 que vous avez réalisé lors du sprint #2 (implémentation d'une mémoire partagée). Pour cela, exécutez les commandes suivantes en les adaptant :

cd repertoireXV6 make clean cd votreRepertoireDeTravailPourCSC4508 cp -r repertoire_xv6 exercice3/xv6_code_etudiant

Si vous n'avez pas fait le sprint #2 ou que le code produit n'est pas utilisable, vous pouvez vous baser sur le corrigé en exécutant les commandes suivantes à la place:

git clone https://gitlab.inf.telecom-sudparis.eu/csc4508/xv6-tsp.git git remote add shm-soluce https://gitlab.inf.telecom-sudparis.eu/csc4508/xv6-soluces/xv6-soluce-shm.git git fetch --all git checkout -b shm-soluce -t shm-soluce/master

3 points

Dans xv6, ajoutez l'appel système int get_nused(void* addr) qui retourne le champ nused du segment de mémoire contenant l'adresse addr.

Si addr n'est dans aucun segment de mémoire partagée, l'appel système retourne -1.

2 point

Dans xv6, ajoutez le programme utilisateur test_get_nused.c qui crée une zone de mémoire partagée, la mappe en mémoire, puis utilise l'appel système get_nused.

2 points

Dans le fichier exercice4/reponses.txt, présentez l'implémentation de la fonction sys_shm_create en vous appuyant sur le code que vous avez rendu à la question 4.a. Cette présentation doit expliquer l'algorithme principal implémenté ainsi que les mécanismes évitant les problèmes (détection d'erreur, verrouillage, etc.)

La fonction shm_create crée une zone de mémoire partagée d'une taille donnée. La fonctionne commence par récupérer le paramètre (la taille de la zone mémoire), puis calcule le nombre de pages mémoires correspondant. Ensuite, le verrou shms.lock est pris afin de s'assurer que la table shm n'est pas modifiée par un autre processus. La fonction recherche ensuite un segment de mémoire partagée libre (dont le nombre de pages vaut 0). Puis, la fonction alloue des pages mémoire (avec kalloc), et les initialise à 0 (avec memset). Enfin, le numéro de segment est retourné à l'application.