/Teaching/System Level Programming/Assignments/A2


Pull from upstream before solving this task.


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 and run the program 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 Hero Organization Simulator.

Initially, hero threads look up the villain “database” to select a villain to fight. Multiple heroes can look through the database simultaneously, but only one hero can check out one specific enemy at a time.

Once a hero has acquired a target villain, the fight will begin, but be aware! Every villain needs a certain amount of heroes present at once to be defeated. Individual heroes attacking by themselves lead to defeat. Make sure to gather enough heroes before unleashing them upon the enemy.

After a hero has endured some glorious battles, a trip to the hospital is necessary. Make sure every injured hero gets a hospital spot. Only a certain amount of heroes are allowed to look through the hospital concurrently, and checking out a room may only be done by one hero at a time.

Finally, when all enemies are defeated, heroes start fighting the Big Boss. This foe is more demanding than the average villain and has shields as protection. Make sure to only attack when the shields are down, which requires heroes to wait for the right moment. Once this moment comes around, heroes can damage the boss. It might be that a certain amount of heroes deal damage to the boss, and the rest of them needs to wait for another opportunity when the shields are down.

After dealing damage to the boss, heroes wait for the boss to be defeated before going off duty to celebrate the day.

Task

  • 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 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!
  • As with all other assignments, you can still lose points during the interviews if you cannot explain your solution satisfactorily or any cheating is detected.
  • 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. Think about your locking structure and check that all shared variables are locked. Also, check if all the locks are acquired and released correctly.

To test all enemy and hospital-related functions or boss fight-related functions individually, one can en- and disable USE_ENEMIES and USE_BOSS in defines.h.

It is recommended to solve the assignment from the top-down, meaning it is advisable to start with the searchVillainDatabase and fight functions, then the useHospital function, and finally the fightBoss and beMalevolent functions.

Building

This assignment uses CMake as a build system. The essential build steps are as follows:

in-source building:

cd A2/
cmake .
make

out-of-source building:

cd A2/
mkdir build && cd build
cmake ..
make

Notice that an executable titled heroes has been created in the folder you called make in. You can now start the program by executing the command ./heroes num_heroes num_enemies, e.g. ./heroes 1 1.

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 (POSIXthreads) 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 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/

Bonus Task

Due to popular demand, we added a second locking example for you to practice locking further as preparation for Operating Systems. Implementing the given bonus task can yield up to 3 bonus points. The test system is optimized to provide a somewhat detailed explanation of what is being tested and what went wrong. Read the TODOs of the assignment code and implement locking mechanisms according to them. The bonus task assignment was designed by Florian Hirner.

Assignment Tutor

If you have any questions regarding this assignment, try discord first and slp@iaik.tugraz.at second. If you have a more direct question regarding your specific solution, you can also ask the tutor who organizes this assignment:

Michael Kammerer, michael.kammerer@student.tugraz.at