Pull from upstream before solving this task.
Task: Thread Synchronization
In the upstream repository, you will find a multi-threaded program without any synchronization. Now your task is to add correct and useful synchronization and make the program run flawlessly.
If you don’t know where and how to start, have a look at section help below.
This time, we provide a framework for a COVID-Testing-Site Simulator.
In the morning a lot of residents are waiting for the test-area/test-street to open.
First, they must go to the receptionist’s desk to fill out their registration form. There is only a limited number of receptionist desks – so you need to make sure that only one resident registers at one receptionist desk at a time.
After the resident has filled out their registration form, they can move to the waiting room to wait for their test. As soon as a test personal is available, they will take care of the resident.
As soon as the test personal has tested the resident, they will let the resident know that they can go home. (Make sure that the resident is notified as soon as this test results are available).
- Identify all actors and resources in the programs.
- Implement the missing parts of the programs, fulfilling the above requirements.
- You need to ensure that the resources are acquired in a safe way.
- Think about potential data races and deadlock scenarios.
- Use synchronization primitives correctly to make access to all shared resources thread-safe.
- All shared resources must be accessed by only one thread at a time!
- As with all other assignments, you can still lose points during the interviews, if you cannot explain your solution in a satisfactory way or any cheating is detected.
- use at least one semaphore or condition variable – You can also use both of them, think where which one fits best.
Test your programs multiple times and with multiple different parameters to find possible threading errors. Threading errors tend to crash programs/produce incorrect output very irregularly and are sometimes hard to reproduce. Think about your locking structure and check that all shared variables are locked. Also, check if all the locks are acquired and released in the correct order.
This assignment uses
CMake as a build system. You should research the
CMake build process online and get familiar with it (
CMake is also used in the operating systems course). However, the essential build steps are as follows:
cd A2/ cmake . make
cd A2/ mkdir build && cd build cmake .. make
The executables are then located in
First of all, the idea of this course is that you should learn to look up technical concepts and implement practical tasks by yourselves. However, here is some help in case you get lost:
Most important resource:
Manual pages for the
man pthreads man pthread_mutex_lock man pthread_cond_wait man < ... >
Some important concepts
Always look up the function you use in their man pages. They will tell you how each function behaves in much more detail.
- Semaphore Holds an integer value that can be increased and decreased by threads.
- Puts the calling thread to sleep when it wants to decrease the value and it has reached a value of 0 or less.
- Sleeping threads are woken up when the value is increased by another thread.
- See also http://www.csc.villanova.edu/~mdamian/threads/posixsem.html
- Mutex Primitive that can be used to make sure only one thread accesses critical sections of code at a time.
- Can be locked and unlocked.
- If a thread tries to lock an already locked mutex, it is put to sleep until the mutex is unlocked by the thread that currently has it locked.
- The same concept as a semaphore that can only have values 0 or 1.
- See also https://computing.llnl.gov/tutorials/pthreads/#Mutexes
- Condition Variable Primitive that can be used to put threads to sleep and wake them up from other threads.
- Ideal for many cases where one thread needs to wait for the result of some processing in another thread.
- See also https://computing.llnl.gov/tutorials/pthreads/#ConditionVariables