/Teaching/System Level Programming/Assignments/A2

Task: Multithreading

This assignment aims to learn and understand the mechanisms of multithreading and concurrency programming. You will use the functionality of the POSIX standard for that and learn how POSIX manages the creation, handling, and termination of threads.

Please read the full description of this assignment carefully beforehand. You will need all the information, which will save you a lot of time.

Main Idea

We decided to show you the aspects of multithreading via a simple ASCII game. You can see if you have done something right by observing that the game is getting more playable. Initially, the game will not draw anything. Start by doing your first TODOs to see more and more of the game!

Your player collects pals, while trying to stay alive as long as possible.

The game consists of 4 different entities:

  • Rocks: Rocks (represented by an ‘R’) are stationary 2×2 squares on the game map. The player must avoid them.
  • Enemies: Enemies (represented by an ‘E’) occupy a single field and move left, right, up or down. Each enemy moves independently of the other entities.
  • Player: The player (represented by a ‘P’ on a blue background) changes direction via the W, A, S and D keys. Moving into an enemy, a rock or the edge of the playing area ends the game. The game shall also quit when ‘q’ is pressed. (Lifepoints get set to 0)
  • Pals: Pals (represented by a ‘P’ on a magenta background) can be collected for points. There should be only one pal on the map at a time. Once it is collected, it should disappear immediately, its thread must terminate, and a new pal should spawn at a random location.

Setup

You’ll have to install ncurses as well as the C build tools on your system. In Debian/Ubuntu the following line will do the job:

sudo apt-get install build-essential libncurses-dev

In some circumstances, your system may require explicit ncurse versions:
sudo apt-get install libncurses6-dev libncursesw6-dev

If none of the packages above work on your system, you can use ncurses5. This package is deprecated, and you should only use it as a last resort after asking for support on Discord!

Do NOT make any other changes to the Makefile!

Implementation details

When you open the folder of this task, you will notice five files:

  • Makefile: Use this file to compile and run the program or clean up the folder. You MUST NOT commit any changes to this file!
  • main.c: This file exists to mount our test cases more easily. You MUST NOT commit any changes to this file!
  • palclone.h: This file contains relevant includes, typedefs, and predefined values. You MUST NOT commit any changes to this file!
  • helpers.c: This file contains helper functions to make the game playable. You MUST NOT commit any changes to this file!
  • palclone.c: This is the only file that will be checked and used by the test system. Please follow the TODOs and ONLY change and add code between TODO BEGIN and TODO END!

To summarize, you can modify all files but can only commit changes to palclone.c. This ensures that you are using the same files as the test system and that everything should work locally as it would on the test system.

You must not create ANY global variables, delete existing code outside of the TODOs (comments can be changed and added, of course), or rearrange existing code! Be careful, do not delete any needed functions declared in the header file.

Furthermore, you should keep the lifetime of variables in mind and not leak any memory you allocate. You don’t need to test this with Valgrind since libncurses leaks memory, and therefore, Valgrind would produce wrong results. Furthermore, valgrind is known to have bugs with this type of game and some of our TODOs.

What to do before you start?

  • Pull from upstream!
  • Carefully look at the TODOs in the palclone.c file.
    • The TODOs are enumerated in the suggested way you should solve the assignment
  • Look at the Manpage, what those parameters of the needed functions are for, and how they are used. (pthread_create( ... ), pthread_cancel( ... ), pthread_join( ... ), etc [https://man7.org/linux/man-pages/man7/pthreads.7.html])
  • Only begin if you understand the basic concept, what a thread is, and what it does. Bruteforcing will lead to a severe amount of wasted time.
    • Try to understand the different functions of the palclone.c file and their connections.
    • Hint: Make sure that you reuse as many variables as possible.
I prepared some data structures to save some time. You can find them in the header file. There is a predefined structure for the parameters you have to pass, and a linked list of enemy_info entries for the enemy types, IDs, thread IDs and return values. Initialize this list and implement getEnemyInfo() as described in the TODOs. USE the provided structures!
If you take a closer look into the usage of the game map array, you may recognize that several race conditions could occur with the usage of this array. You do not have to worry about them. For the readability of the given code and to just focus on the first learning goals of this course, proper synchronization is left out. Occurring race conditions should not crash the program, and for test runs on the test system, they are solved. How race conditions are preventable will be discussed in the Thread Synchronization assignment. If you want some further information, take a look at this page: https://en.wikipedia.org/wiki/Race_Condition.
However, you might encounter other race conditions with your implementation that are not caused by using the game map array. If you notice such buggy behavior, you cannot use mutexes, semaphores, etc. Also, using functions like sleep() is not the way here! Therefore additional calls to sleep functions and the usage of synchronization primitives are forbidden! This also includes functions (combinations) such as getch!

Helpful resources

You find all the needed information on the manual pages. You can access them by either typing man into the terminal or by reading them on various websites. For example, the manual regarding pthread_create( ... ) may be accessed by the command man pthread_create . For this exercise, you might find the following links helpful.

Debugging:

In this course, it’s very important to find errors yourself and notice issues in your own usage of syscalls or other functions. Therefore, we recommend getting comfortable with a debugger, especially since most of you will take OS in the next semesters!

Debugging with VSCode

Manpages:

In case you prefer a German source:

If you need a rough overview of the pthread library, check out the pthread tutorial by Peter C. Chapin. It contains a lot of information for the first and second assignments.

Submission

Modify palclone.c in your git repository. You can find this file in the directory A2. Tag the submission as A2 and push it to the server. Do not add any additional files to the folder!

Support

If you have 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 ask in the corresponding channel.