Exam 2021-2022
Organization
Duration : 3 h
Preparation
Returning your work
At the end of the exam, you have to post your work on moodle.
Please post a tgz file. You can generate it with:
Memory profiler (10 points)
Directory exercice2 contains a program that simulates the behavior of a memory profiler. The memory profiler counts the number of memory access to each virual address. To do that, the memory profiler intercepts the application memory access (in our case, this is simulated by the application explicitely calling get_value that logs a memory access).
The memory profiler stores the virtual addresses and their access count in a hashtable. The virtual address identifies a struct ht_entry that contains a field nb_access that is incremented each time the application accesses this address.
The hastable consists of an array of list named entrys. When searching for the addressaddr, we first compute a hash of addr, that we call index. This hash indicates that addr may be in the list entrys[index]. This list contains all the collected addresses whose hash is index, and the list is sorted according the addresses.
Parallelizing a matrix multiplication (3 points)
The memory_profiler.c program collects the memory accesses performed when multiplying matrices.
Modify the main function to create NTHREADS threads. Each thread should execute thread_function, and obtain a unique identifier thread_id comprised between 0 and NTHREADS-1. The main function should wait for the end of the threads before calling dump_stats.
- Création/destruction des threads : 2 points
- Récupération d'un identifiant unique: 1 point
3.5 points
Now that several threads run the matrix multiplication in parallel, there may be concurrent access to the hashtable when several threads call ht_insert concurrently.
Modify the hashtable structure and the hashtable functions (ht_init, alloc_entry, update_ht_entry, and ht_insert) to make this data structure thread-safe. Add a comment at the beginning of the source file to explain your implementation choices, and how they impact the program performance.
- lock initialisé: 0.5 point
- Implémentation ok: 2 points
- Justification: 1 point
3.5 points
After the execution of the application, the memory profiler should write the content of the hashtable into a file. Modify the dump_stats function so that it creates a file named filename with read and write permissions for the user (and no permission for the group, or for other users). Then, browse the hashtable and, for each entry write the address and the number of accesses.
- Ouverture du fichier avec les bonnes permissions: 1 point
- Fermeture du fichier: 0.5 point
- Parcours de la table de hash: 1 point
- Ecriture des entrées: 1 point
mmap (5 points)
In this exercise, you process the trace generated in Exercise 2. Finishing Exercise 2 is not mandatoray to start this exercise.
Directory exercise3 contains a trace generated by a correct program that implements Exercise 2, and a basic memory_analyzer.c file. The struct event structure exactly corresponds to a record in the trace test.dat.
The first argument of the program is the path to a trace file. The second argument is either read or mmap. When the program runs in read mode, it has to read the trace by using the read function. When the program runs in mmap mode, it has to read the trace by using the mmap function.
1 points
In the main function, remove the comment TODO: 3.a. Instead, initialize fd and n. fd is a file descriptor to the trace file opened in read only, and n is the number of events in the trace file.
2 points
Write the code of nb_access_read. This function is supposed to return the nb_access in the nth event of the trace by using read. If you run ./memory_analyzer test.dat read, you should find that, in average, the trace access each memory address 10 times.
2 points
In the main function, remove the comment TODO: 3.b. Instead, you have to map the whole trace file, and store the address at which the file is mapped in the events variable. Write also the code of nb_access_mmap. This function is supposed to return the nb_access in the nth event of the trace by using the events variable. If you run ./memory_analyzer test.dat mmap, you should find that, in average, the trace access each memory address 10 times.
XV6 - number of direct children (5 points)
In this exercise, you are asked for xv6 code. You don't have to attach all the sources to your archive (that would be too big for an email). Instead start by cloning xv6 outside from the directory where you did the other exercises with the following command:
Then, to generate a patch in the directory where you did the other exercises, run the command:
Where ${PATH_TO_CF} is the path to the directory containing the code you did for the other exercises.
5 points
Add a system call int nb_children() in xv6 that returns the number of children of the calling process.
- Mise en place de l'appel système: 2 points
- Prise du lock: 1 point
- Algo général: 1 point
- Vérification de l'état du processus: 1 point
