Operating systems

Portail informatique

Exam 2022-2023


Duration : 3 h


cd someDirectory wget http://www-inf.telecom-sudparis.eu/COURS/CSC4508/Supports/CF/2022-2023/cf1/9jF2j7Ns7M/Exam2023.tgz tar xvfz Exam2023.tgz mv Exam2022 ${USER}_Exam2023 cd ${USER}_Exam2022

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:

cd someDirectory tar cvfz ${USER}.tgz ${USER}_Exam2023

Monte Carlo approximation of Pi (6 points)

The goal of this exercise is to parallelize an application that approximates the value of Pi using a Monte Carlo method. This method involves drawing a large number of points (x,y) at random. The coordinates x and y are comprised between 0 and 1. By counting the number of points in a circle, we can approximate the value of Pi.

In the exercise2 directory, the pi.c program defines function void monte_carlo_pi(). This function draws a large number (niter) of points and computes how many of them are within a 1 unit circle (the sum counter).

The program calls nepochs time the monte_carlo_pi function before printing the approximate value of Pi.

Parallelizing an application (3 points)

For now, only one thread performs all the computation. Modify the program so that the main function creates nb_threads threads, and each thread calls the monte_carlo_pi function nepochs / nb_threads times.

The main function should wait until all the thread finished their computation before printing the approximate value of Pi.

Grading scale:
  • Creating threads: 2 points
  • Waiting for the end of the threads: 1 point

Thread-safety (3 points)

By running the computation in parallel, some data structures may be modified concurrently. Make sure that the computation remains correct.

Add a comment at the beginning of pi.c to justify the synchronization method that you chose.

Grading scale:
  • Synchronization: 2 points
  • Justification: 1 point

Word count (6 points)

In the exercise3 directory, you will find the program word_count.c. The goal of this exercise is to modify this program so that it counts words in a text.

2 points

First, modify the main function so that it opens the file filename, read each line with fgets. For each line of the file, call the function void word_count(char* line).

Grading scale:
  • Open/close the file: 1 point
  • Iterate over the file content: 1 point

3 points

The word_count function splits a line into a group of words, and calls void update_word(char* w) for each word. update_word has to update the statistics (the number of time this word appears in the text) of a word. The list of know words is stored as a linked list named word_list.

Implement update_word. This function should:

  • Iterate through the list word_list and search for word w;
  • If w is found, increment the count of the world and return;
  • If w is not in the list, allocate a new struct word_stat and initialize it with w before inserting it into the word_list list.
Grading scale:
  • Browsing the list and calling strcmp: 1 point
  • Allocating a new node and initializing it: 1 point
  • Inserting the node into the list: 1 point

1 point

After processing the file, the main function calls void print_words(). This function should browse the word_list list and print each known word and its count.

Implement the print_words function.

Grading scale:
  • Browsing the list: 1 point

4 points

In this question, we modify the program to make it parallel. Before starting, copy your word_count.c to word_count_parallel.c and work on this new file. This will prevent you from destroying all your hard work from the previous questions !

Modify word_count_parallel.c to set up a worker-slave processing of the file. The main function should create a set of 4 worker threads. Then when reading the file, instead of calling word_count directly, the main thread should "send" the line to a worker thread. When a worker thread receives a new line, it processes it by calling word_count, and wait for the next line.

After sending all the lines to the worker threads, the main thread notifies them that there is no more work and it waits for the end of the worker threads. The main threads can then can print_words to display the results.

Grading scale:
  • Implementing a producer/consumer: 2 points
  • Thread-safe modification of the list: 1 point
  • Waiting for the end of the worker threads: 1 point

XV6 - memory allocation (6 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:

git clone https://gitlab.inf.telecom-sudparis.eu/csc4508/xv6-tsp.git

Then, to generate a patch in the directory where you did the other exercises, run the following commands:

$ git add -N test_alloc.c # add test_alloc.c to the git repo $ git diff origin/master > ${PATH_TO_CF}/exercise4/diff.patch # create the patch with all your code changes

Where ${PATH_TO_CF} is the path to the directory containing the code you did for the other exercises.

4 points

Add a system call int alloc_page(void* addr) in xv6 that allocates a memory page, fills it with zeros, and maps it at address addr.

The system call return 0 if successful, or -1 in case of an error.

You can implement this system call in vm.c.
Grading scale:
  • Setting the system call: 2 point
  • Allocating memory and mapping it: 1 point
  • Call to memset: 1 point

1 point

Add a system call int free_page(void*addr) that free a memory page allocated with alloc_page.

You can implement this system call in vm.c.
Grading scale:
  • Setting the system call: 0.5 point
  • Freeing the memory: 0.5 point

1 point

Create a test program test_alloc.c. This program allocates 10 memory pages, write some data in the allocated pages (for example 1), and free the memory pages.

Grading scale:
  • Test program: 0.5 point
  • Modification of the Makefile: 0.5 point