/Teaching/System Level Programming/Assignments/A3

Task: Thread Synchronization

You will find a multi-threaded program in the upstream repository without any synchronization. Your task is to add correct and proper synchronization to make the program run flawlessly.
If you don’t know where and how to start, look at the help section below. While implementing, make sure to read the comments found in the assignment code, and if anything is unclear, come back to this Wiki.

Main Idea

This time, we provide a framework for A day of work at an airport check-in. The central roles in this scenario are:

  • Passengers – choose between the staffed check-in lane and a self-check-in machine.
  • Employees – check in passengers waiting in the staffed lane.
  • SelfCheckIns – guide one passenger at a time through identification and ticket printing.
  • Maintainers – repair self-check-in machines that are out of service.

The passenger decides whether to use the staffed lane or a self-check-in machine. The workflow then branches as follows:

Staffed Check-in

  • No passenger should enter the waiting queue before the first employee opens the lane (check_in_line_opened).
  • Employees should be notified as soon as passengers arrive. An employee should work only when there is a waiting passenger, or finish when there are no more passengers.
  • Each passenger waits until the employee has completed their check-in before proceeding to the gate.

Self-check-in

  • A passenger selects an available machine in the READY state. Two passengers must never select the same machine, and an out-of-service machine must not be used.
  • The passenger starts the interaction (START) and waits for the machine to request an ID scan (ID_SCAN).
  • After scanning the ID, the passenger signals PASSENGER_IDENTIFIED. The machine prints the ticket and signals PRINT_TICKET. The passenger must receive this result before the machine is made available again.
  • Some passengers then drop off baggage at the express line. Keep access to the baggage counters safe while allowing different free counters to be used concurrently.
  • Machines may go OUT_OF_SERVICE. Maintainers periodically check for such machines at their own pace, repair them, and return them to the available machines. No dedicated notification mechanism is expected for maintainers; they take a coffee break when there is nothing to do.
  • At shutdown, employees must be able to finish, maintainers must be cancelled safely, and self-check-in machines must terminate when switched OFF.

Ensure that the provided comments and hints in the code are followed, and achieve the described workflow using only synchronization primitives.

Task

  • Identify all actors and resources in the programs.
  • You need to ensure that the resources are acquired safely.
  • 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!
  • The individual tasks are built to encourage the usage of at least one mutex, one semaphore, and one condition variable. Strongly think about which locking principles make the most sense in which situations.
  • Notice the marked TODO fields and which files are not to be modified.
  • Make sure to read the code as well as the function headers carefully.

Test your programs multiple times and with numerous parameters to find possible threading errors. Threading errors tend to crash programs/produce incorrect output very irregularly and are sometimes hard to reproduce.
Follow the “divide and conquer” principle and take a modular approach to the implementation. Start by implementing the staffed check-in part first, then move on to self-check-in without maintenance or baggage drop-off. Once this works, gradually add these options.

If you take a look at the header file testing_defines.h, you will be able to activate, deactivate and randomize self-check-in, maintenance and baggage drop-off for local testing. Set the number of threads through the command-line arguments!

Building

Out-of-source building:

cd A3/
cmake -S . -B build
cmake --build build

Notice that an executable titled airport has been created in the build folder.
You can now start the program by executing:

./build/airport num_passengers num_employees num_selfcheckins

Do not push the build directory or its contents.

Common Problems

  • This task is about locking. Do not wrap your head around different edge cases. Only make sure every shared resource is correctly locked.
  • Avoid potential deadlocks! Locks have to be locked in the same order.
  • Do not unlock a mutex multiple times, do not destroy a locked mutex, and especially do not unlock a mutex from a thread not owning it. Consider scenarios that lead to undefined behavior! (check out the man page)
  • You don’t have to change the cancellation state and/or type of any thread!
  • Use assert statements to check the return values of the pthread_* and sem_* functions to catch wrong usage!

General Notes

  • You are responsible only for locking. Do not change the program logic (except an if/while loop directly related to a synchronization primitive)!
    ==> Do not observe the codebase as an optimization or improvement opportunity. Instead, consider it a runway where you must make everything work correctly using only the learned synchronization primitives.
    No new non-synchronization variables, code modifications, or reorganizations are allowed.
  • Timeout is a good sign for deadlock, lost signals, or overlocking. Make sure you don’t introduce any of these problems in your program.
  • You have a free choice of synchronization primitives. We don’t restrict you anywise, but only encourage you to use all those mentioned in the lecture as the goal of this task is to get familiar with them.
  • Ideally do not push any custom debug messages!
  • Make sure printf messages indicating an illogical program flow do not get printed! (e.g. “[OOPS] Passenger %zd appears to be early for their check-in! The lane hasn’t opened yet!!”).
  • Ensure that the final “THAT’S ALL FOLKS” and “BON VOYAGE” messages appear only after all threads have finished!

Help

The spirit of this course is that you should learn to look up technical concepts and implement practical tasks by yourself. However, here is some help in case you get lost:

Most important resource:
Manual pages for the pthreads (POSIX threads) functions

man pthreads
man pthread_mutex_lock
man pthread_cond_wait
man <...>

If you need a rough overview of the pthread library and how to lock correctly, make sure to check out the pthread tutorial (PDF) by Peter C. Chapin. It contains a lot of information you might need for the first and second assignments.

Note: If you get an error while trying to open the manual pages for pthread_mutex_lock, you can install the glibc-doc (sudo apt-get install glibc-doc) package to fix the issue.

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.

  • A fixed amount of threads can enter.
  • It puts the calling thread to sleep when it wants to decrease the value and has reached 0 or less.
  • Sleeping threads are woken up when another thread increases the value.
  • Datatype: sem_t
  • Popular functions: sem_init, sem_destroy, sem_wait, sem_post
  • See also: https://linux.die.net/man/7/sem_overview

Mutex

Primitive that can be used to make sure only one thread accesses critical sections of code simultaneously.

  • Only one thread can enter.
  • It 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.
  • A mutex applies the same concept as a semaphore with the values 0 or 1.
  • Datatype: pthread_mutex_t
  • Popular functions: pthread_mutex_init, pthread_mutex_destroy, pthread_mutex_lock, pthread_mutex_unlock
  • See also: https://hpc-tutorials.llnl.gov/posix/

Condition Variable

Primitive that can be used to put threads to sleep and wake them up from other threads.

  • A CV is ideal for many cases where one thread needs to wait for the result of some processing in another thread.
  • They are always protected by an accompanying mutex.
  • Datatype: pthread_cond_t
  • Popular functions: pthread_cond_init, pthread_cond_destroy, pthread_cond_wait, pthread_cond_signal, pthread_cond_broadcast
  • See also: https://hpc-tutorials.llnl.gov/posix/

Submission

Modify airport.c and add synchronization primitives as needed in resources.h. Keep changes to the testing configuration local. You can find this assignment’s files in the A3 directory.

Tag the submission with A3 and push it to the server. You may remove and re-push the A3 tag at any time throughout the semester.

Support

If you have any questions regarding this assignment, go to Discord and read through the SLP channels. The probability that your question was already answered or some discussions will lead you in the right direction is quite high. If not so, just create a new thread with the A3 flair applied.