L6: Habemus Regem!#

After the death of King Michał Korybut Wiśniowiecki in 1673, there was a time to choose a new King of the Polish-Lithuanian Commonwealth. Tens of thousands of magnates and other Polish nobles arrived in Koło, a village near Warsaw, all ready to see the candidates, debate and vote. The only problem was accommodation for the people from around the country for the time of the election sejm. Therefore, the citizens of Warsaw were ordered to lodge some of the nobles.

The council of a wealthy, but small city (Warsaw only consisted of the Old City then) sees a real problem accommodating all the visitors. Both the nobles and the citizens should be (relatively) comfortable while living together. One of the council members came up with an idea of creating a booking system for nobles. Interrex Kazimierz Florian Czartoryski found this idea excellent and decided to help — he donated a POSIX-compliant calculating machine and a few peasants to make the machine work. The only thing missing is a program. Help Semper Invicta and implement the system!

Stages:#

Stage 1 (6 pts)#

The program accepts two positional arguments: \(1 \leq n \leq 15\) — the number of townhouses in Old Warsaw — and \(5 \leq m \leq 20\) — the number of nobles to accommodate. Create an anonymous block of shared memory containing \(n\) shared mutexes. Then create \(m\) processes representing nobles. Each noble is lazy and tries to take the house closest to the city gate — iterate over the mutexes and lock the first available one (Hint: you can use the pthread_mutex_trylock function). After locking the mutex, the process-noble prints [<PID>] Such a comfortable house no. <i>!, where \(i\) represents the index of the mutex, sleeps 300 ms, unlocks the mutex, and exits. When no mutex is available, print [<PID>] Cui bono have I arrived here? and exit.

The parent process waits for all the children and exits.

In all stages, each process must release all used resources before exiting correctly.

In the next stages, every synchronization object and shared variables must be placed in the created anonymous memory block, unless explicitly stated (changing the size may be needed).

Stage 2 (5 pts)#

Due to the large number of upset nobles who couldn’t find accommodation, the city council wants you to implement a waiting room. Create a shared conditional variable associated with a shared free houses counter (protected by a mutex). After acquiring a house mutex, decrement the counter. When a process-noble doesn’t find accommodation, instead of exiting, it waits on the conditional variable until another process leaves a house and increments the counter. The process-noble which leaves the house notifies one of the waiting processes. After being notified, the process-noble prints [<PID>] Let's try again and repeats the loop over the houses until some mutex is free or, if not, goes again to the waiting room. Every noble should find a house.

Hint: Initialization of a shared conditional variable is analogous to initialization of a shared mutex (use pthread_condattr_t instead of pthread_mutexattr_t).

Stage 3 (3 pts)#

The huge crowd of nobles is about to break the city gate. Help toughen the walls with a semaphore. Each noble, before iterating over the houses, opens the named semaphore /gate (if the semaphore doesn’t exist, creates it with an initial value of 10) and waits on the semaphore. After sleeping inside a house (and before exiting), they increment the value of the semaphore by 1.

In the main process, remove the semaphore both at the beginning of the program (only if it exists) and at the end of the program.

Stage 4 (5 pts)#

Some Polish nobles are known for their fierce nature. They can easily become violent and damage the furniture, smash the windows, or even break through the walls.¹ The city council wants to know which houses have been damaged to effectively plan repairs after the sejm.

In the main process, remove (if it exists) and then create and map a named shared memory object /houses of the size of \(n\) integers and fill it with zeros. Close the memory object and unmap the memory before creating child processes.

Processes-nobles, after being created, open and map the memory object. The process which locked the \(i\)-th house mutex has a 10% chance to damage the house. In this case, print one (random) of the following messages:

• [<PID>] Time to break a wall in house <i>!
• [<PID>] There is so much mead in house <i>, I'll drink it all!
• [<PID>] What? No bathroom in house <i>? I'll dig the bath myself!

and change the \(i\)-th value in the created memory to \(1\) before unlocking the mutex.

In the main process, after waiting for all child processes, open the memory object, print its contents, and remove it.

Stage 5 (5 pts)#

The process-noble which encounters a damaged house dies from anger immediately. Before sleeping, check the appropriate value. If it’s nonzero, print [<PID>] House <i> is the last thing I see in my life, release the semaphore, and call abort() while holding the mutex. When another process tries to enter the room with a dead body, it prints [<PID>] Cannot be! I'll clean the house <i> up! and sets the checked value back to 0.

If you run your solution a few times with a higher damage chance (e.g. 50%), your program may hang (why?). To avoid the deadlock, detect in the main process if a child terminated abnormally (Hint: you can utilize Status Information and the WIFEXITED macro) and then, with a loud scream from the underworld, notify every process in the waiting room.

Starting code#

• Makefile
• ops-booking.c

Download as zip