Operating systems

Portail informatique

Lock analyzer (part 2)

Preamble

To get started, get the base for today's lab:

  • git clone -b tp12_base https://gitlab.inf.telecom-sudparis.eu/csc4508/csc4508_facebook.git csc4508_tp12
  • or git checkout tp12_base

The goal of today's lab is to implement a tool that analyzes trace files generated by the lock analyzer tool developed during the previous lab.

The analyze_trace.c program runs a trace and collects several statistics:

  • For each thread, the number of recorded events
  • For each intercepted function, the number of events recorded and the average / minimum / maximum durations of the function calls
  • For each lock, the number of locks and their average / minimum / maximum duration, as well as a "contention score"

To test the program, you can use one of the traces that you generated. You can also generate a trace by running the command make run from the test/leveldb directory. Finally, you can use one of these traces:

Currently, the various locks detected in the trace are stored in a locks array of fixed size. This could pose problems for the traces containing a large number of locks.

Modify the program so that the array is allocated dynamically and augmented (using realloc) each time a new lock is detected.

Instead of reading the trace file one event at a time, we want to see the trace as a big table of events accessible via their index.

Modify the program to map the file in memory (using mmap).

The next step is to parallelize the analysis of the trace. For this, we set up a master/worker architecture: the main thread goes through the trace and dispatches events to worker threads which process the events. Each worker processes the events of a trace thread. So the main thread knows to which worker to assign each event.

First, let's take care of the possible problems of concurrent access to two data: the locks array, and the threads array.

The goal of this question is to make access to locks array thread-safe. Modify the update_lock_stats function in order to make it thread-safe while limiting the impact of the change in performance.

Changes applied to a lock can be made atomically. Due to the use of realloc (which can change the buffer adress), it is necessary to ensure that no thread is changing the table size while processing a lock. For this you can use a rwlock.

We now parallelize the application and manage threads array. This parallelization is based on a master/worker architecture: the main thread browse the trace and distributes the events to the worker threads responsible for processing events. Each worker is assigned the events of a thread from the trace. So the main thread knows to which worker to assign each event. Moreover, it is not necessary to protect access to the threads array since no concurrent access is made there.

Modify the application as follows:

  • in the thread_info structure, add one or more fields to implement a producer/consumer type scheme. You can for example use a pipe (see man pipe). It is also necessary to add two fields min_timestamp and max_timestamp corresponding to minimum and maximum timestamps detected for this thread.
  • in get_thread_info, when a new thread is detected in the trace, it is necessary to create a worker thread that will be responsible for processing the events of this thread.
  • each worker thread must wait for the main thread to send an int that is the index of an event in the table of events. Once the index has been received, the worker processes the event (by calling process_event) then wait for the next notification. The thread ends when it receives a negative index.
  • when it reads a new event, the main thread wakes up the worker thread in charge of this event and indicate the index of the event to be processed.
The answers to this exercise are available in the tp12_corrige branch of the git repository.