Condition Variables Basics

Posted on January 16, 2023 · 22 minute read

Condition Variables Basics

In this assignment, we will have a quick practice with condition variables and mutexes. There are three problems that you must solve using condition variables.

Learning Objectives

At the end of this assignment, you should be able to:

  • Implement multi-threaded code using the pthreads library.
  • Solve basic concurrency problems using condition variables.

Getting the Source Code

We will do this lab in the main branch of your labs repository. To make sure you are on the right branch, check it out using:

  $ git branch

The branch you are currently on will be highlighted for you (with a * next to its name).

If you are working on the main or master branch, then follow these instructions:

  $ git fetch upstream
  $ git pull upstream main

At this stage, you should have the latest copy of the code, and you are good to get started. The starter code is contained under the threads_basics/ directory.

If you are currently on a different branch (say you are still on clab_solution from a previous lab), then we need to switch to main or master (depending on your default’s name).

First, add, commit, and push your changes to the clab_solution to make sure you do not lose any progress you did on the last lab. To check the status of your current branch, you can use:

  $ git status

This will show you all the files you have modified and have not yet committed and pushed. Make sure you add those files, then commit your changes, and push them.

If git push complains about not knowing where to push, you’d want to push the current branch you are on. So for example, if I am working on clab_solution, then I’d want to do git push origin clab_solution.

Now, you are ready to swap back into main (or master).

$ git checkout main

Then, grab the latest changes using:

$ git fetch upstream
$ git pull upstream main

At this stage, you should have the latest copy of the code, and you are good to get started. The starter code is contained under the condvar_basics/ directory.

In-order (30 points)

This problem refers to the file inorder.c. In this system, there are threads numbered 1 through 4 and there is a critical section that the threads are trying to enter. The threads are required to enter the critical section in order (e.g., 1 enters the critical section first, 2 following that, then 3, and finally 4).

If a thread n finishes and thread n+1 is waiting, then thread n+1 immediately executes. However, if thread n+1 is not waiting, no threads should be allowed into the critical section until the correct thread arrives in order. For example, if thread 1 finishes and thread 2 is not yet waiting to enter the critical section, then no other thread should be allowed in until thread 2 comes in and finishes.

Max (30 points)

This problem refers to the file max.c. In this system, there is a special critical section in which 3 threads are allowed to be in at once. Once 3 threads are in the critical section, any further threads must wait until one of the threads leaves the critical section.

Rooms (30 points)

In this setup, there are two rooms where customers can go in and receive service. Customers have to go through the two rooms in order, i.e., they go into room 1 first and then go into room 2.

The first room has a capacity of 5, i.e., at most 5 customers can go in to the room at one time. Each customer will spend FIRST_ROOM_SERVICE_RATE time units in the first room before leaving. The first room has an infinite waiting room, i.e., there is no limit on the number of customers that are waiting to go into the first room.

On the other hand, the second room is a bottleneck. It has a small capacity of 2 and a slower service rate (SECOND_ROOM_SERVICE_RATE of 2 time units). In other words, there can be at most 2 customers in the second room, and each customer gets to spend 2 time units in the room. However, unlike the first room, the second room has a much smaller waiting room capacity of 2, i.e., there can be at most 2 customers waiting to enter the second room. So in total, the second room can only support at most 4 customers, 2 in service and 2 waiting.

When a customer arrives, they will first try to enter the first room. If that room is full, they will wait until someone clears out of the room. Alternatively, if the room has a spot for them to get service, then they will go in to the room and receive service.

After finishing up from the first room, the customer will attempt to enter the second room. Three cases might arise in this scenario:

  1. The second room has a spot for the customer to receive service, then they will directly go in and receive service.
  2. The second room is full (i.e., there is already two threads in there) but the waiting room has a spot for them, then they will join the waiting room.
  3. Both the second room and the waiting room are full, in that case, the customer will become unhappy and decide to leave the system completely. I am keeping track of the number of unhappy customers using the num_left_customers global variables.

Use condition variables and mutex locks to implement the concurrency requirements listed above. You only need to modify the customer thread function and add global variables and concurrency means. Note that when a spot opens in either rooms, it does not matter which customer gets to go into that room, i.e., waiting rooms are not necessarily first in first out.

You can compile your code using make rooms and then run it using ./rooms. Here is a sample output from my solution:

$ ./rooms
[Customer 1] Just arrived at first room...
[Customer 1] Entered first room...
[Customer 2] Just arrived at first room...
[Customer 2] Entered first room...
[Customer 3] Just arrived at first room...
[Customer 3] Entered first room...
[Customer 1] Left first room...
[Customer 1] Entered second room...
[Customer 2] Left first room...
[Customer 2] Entered second room...
[Customer 4] Just arrived at first room...
[Customer 4] Entered first room...
[Customer 3] Left first room...
[Customer 5] Just arrived at first room...
[Customer 3] Joined the waiting room for second room...
[Customer 5] Entered first room...
[Customer 7] Just arrived at first room...
[Customer 7] Entered first room...
[Customer 6] Just arrived at first room...
[Customer 6] Entered first room...
[Customer 8] Just arrived at first room...
[Customer 9] Just arrived at first room...
[Customer 8] Entered first room...
[Customer 10] Just arrived at first room...
[Customer 4] Left first room...
[Customer 4] Joined the waiting room for second room...
[Customer 9] Entered first room...
[Customer 5] Left first room...
[Customer 7] Left first room...
[Customer 6] Left first room...
[Customer 5] Left unahppy because waiting room is full...
[Customer 7] Left unahppy because waiting room is full...
[Customer 6] Left unahppy because waiting room is full...
[Customer 8] Left first room...
[Customer 8] Left unahppy because waiting room is full...
[Customer 10] Entered first room...
[Customer 1] Left second room...
[Customer 2] Left second room...
[Customer 3] Entered second room...
[Customer 4] Entered second room...
[Customer 9] Left first room...
[Customer 9] Joined the waiting room for second room...
[Customer 10] Left first room...
[Customer 10] Joined the waiting room for second room...
[Customer 3] Left second room...
[Customer 4] Left second room...
[Customer 9] Entered second room...
[Customer 10] Entered second room...
[Customer 9] Left second room...
[Customer 10] Left second room...
Everything finished: 4 customers left unhappy...

As always, your output will look different depending on the order of execution. Here are the requirements for your output:

  1. There can be no more than 5 customers entering the first room. In other words, there can be no more than 5 Entered first room... statements before a Left first room... statement.
  2. A customer cannot go into the second room without going through the first room.
  3. There can be no more than 2 customers entering the second room. Use the same approach as requirement (1) above to check for that.
  4. There can be no more than 2 customers entering the waiting room for the second room.
  5. Customer attempting to go into the second room while there are 2 customers waiting for it will leave unhappy.
  6. All customers must eventually leave, happily or unhappily.

Tunnel (10 points)

In this scenario, we have a tunnel with cars going in from two opposite directions, east-west and west-east. However, the tunnel is unfairly designed. There is only 1 west-eat lane while there are 3 east-west lanes. In other words, there can be at most 3 east-west cars in the tunnel while there can only be at most 1 west-east car in the tunnel.

If an east-west car arrives at the tunnel and there are less than 3 east-west cars in the tunnel, then that car can enter the tunnel. If an east-west car arrives at the tunnel and there are 3 east-west cars already in the tunnel, then that car must wait until one of the cars in the tunnel leaves. There is no limit on the number of cars waiting in that direction.

If a west-east car arrives at the tunnel and the west-east lane is empty, then that car can enter the tunnel. If a west-east car arrives at the tunnel and there is already a car in the west-east tunnel, then that car must wait until the car in the tunnel leaves. Again, there is no limit on the number of cars waiting in that direction.

Therefore, at any point in time, there can be at most 4 cars in the tunnel. 3 in the east-west lanes and 1 in the west-east lane. An east-west car cannot use the west-east lane. Similarly, a west-east car cannot use the east-west lane.

Step 1: Simple Concurrency

First, let’s focus on implementing the above semantics. They should be pretty much straight forward. Modify the ewcar and wecar thread functions to implement the above requirements. You may use as many condition variables as you need, but I recommend only using a single lock.

To test your implementation, make sure to first set the number of ambulances (coming up soon) to 0. To do so, edit the code at line 9 and change the constant NUM_AMBULANCE to 0 instead of the 7 that is in there.

Now, you can compile your code using make tunnel and run it using $ ./tunnel. My output looks something like the following:

$ ./tunnel
Car (1) entered tunnel in EW direction...
Car (2) entered tunnel in EW direction...
Car (3) entered tunnel in EW direction...
Car (16) entered tunnel in WE direction...
Car (16) exited tunnel in WE direction...
Car (17) entered tunnel in WE direction...
Car (1) exited tunnel in EW direction...
Car (3) exited tunnel in EW direction...
Car (2) exited tunnel in EW direction...
Car (6) entered tunnel in EW direction...
Car (7) entered tunnel in EW direction...
Car (4) entered tunnel in EW direction...
Car (17) exited tunnel in WE direction...
Car (18) entered tunnel in WE direction...
Car (6) exited tunnel in EW direction...
Car (7) exited tunnel in EW direction...
Car (4) exited tunnel in EW direction...
Car (5) entered tunnel in EW direction...
Car (8) entered tunnel in EW direction...
Car (9) entered tunnel in EW direction...
Car (18) exited tunnel in WE direction...
Car (19) entered tunnel in WE direction...
Car (19) exited tunnel in WE direction...
Car (20) entered tunnel in WE direction...
Car (5) exited tunnel in EW direction...
Car (8) exited tunnel in EW direction...
Car (9) exited tunnel in EW direction...
Car (10) entered tunnel in EW direction...
Car (11) entered tunnel in EW direction...
Car (12) entered tunnel in EW direction...
Car (20) exited tunnel in WE direction...
Car (21) entered tunnel in WE direction...
Car (10) exited tunnel in EW direction...
Car (12) exited tunnel in EW direction...
Car (13) entered tunnel in EW direction...
Car (11) exited tunnel in EW direction...
Car (15) entered tunnel in EW direction...
Car (14) entered tunnel in EW direction...
Car (21) exited tunnel in WE direction...
Car (22) entered tunnel in WE direction...
Car (22) exited tunnel in WE direction...
Car (23) entered tunnel in WE direction...
Car (13) exited tunnel in EW direction...
Car (15) exited tunnel in EW direction...
Car (14) exited tunnel in EW direction...
Car (23) exited tunnel in WE direction...
Car (24) entered tunnel in WE direction...
Car (24) exited tunnel in WE direction...
Car (25) entered tunnel in WE direction...
Car (25) exited tunnel in WE direction...
Car (26) entered tunnel in WE direction...
Car (26) exited tunnel in WE direction...
Car (27) entered tunnel in WE direction...
Car (27) exited tunnel in WE direction...
Car (28) entered tunnel in WE direction...
Car (28) exited tunnel in WE direction...
Car (29) entered tunnel in WE direction...
Car (29) exited tunnel in WE direction...
Car (30) entered tunnel in WE direction...
Car (30) exited tunnel in WE direction...
Everyting finished...

As usual, your output will look different, but here are the requirements:

  1. At most three EW cars can enter the tunnel.
  2. At most one WE car can enter the tunnel.
  3. All cars must enter the tunnel and complete execution.

This part should be easy to implement, we have done this many times in class.

Step 2: A Single Ambulance

Before your forget, change the number of ambulances to 1.

Now, we will add ambulances to the cars possibly arriving at the tunnel. For simplicity, we will only assume that ambulances arrive from the east-west direction and not from the west-east direction. However, the ambulances have priority over ALL cars, regardless of the direction they are coming from. In addition, ambulances can use any of the four lanes, i.e., they can use the west-east lane even though they are coming in from the east-west direction. For this step, we will limit our attention to a single ambulance.

Once an ambulance arrives, no new car can enter the tunnel from either direction. However, cars already in the tunnel are allowed to leave. You should be careful here. This requirement is a strong one. Once an ambulance arrives at the tunnel, cars can no longer enter the tunnel, even if there is room for them and the ambulance. For example, let’s say that the tunnel has 1 east-west car and 0 west-east cars. Let’s say an ambulance arrives and can use one of the empty east-west lanes. At that point, as long as the ambulance is in the tunnel, no new car, regardless of its direction, can enter the tunnel, even though there are two more empty lanes. So the ambulance blocks everyone, regardless of the state of the tunnel.

If an ambulance arrives and the tunnel is full (i.e., there are 3 east-west cars and 1 west-east car in the tunnel), then it must wait for the first lane that clears up, regardless of its direction (recall that ambulances can use either directions).

Once the ambulance leaves the tunnel, blocked cars can now approach the tunnel. Also, since the ambulance was using one of the lanes, then we know for sure that if there are cars waiting, then one car can directly enter the tunnel (the trick is determining from which direction is that car coming from).

Update your implementation to satisfy the above concurrency requirements. Feel free to use as many condition variables as you deem fit, though I wouldn’t recommend using more than a single mutex lock.

You can compile your solution using make tunnel and run it using ./tunnel. Here is my sample output:

$ ./tunnel
Car (1) entered tunnel in EW direction...
Car (2) entered tunnel in EW direction...
Car (3) entered tunnel in EW direction...
Car (16) entered tunnel in WE direction...
Car (16) exited tunnel in WE direction...
Ambulance 31 entered the tunnel in WE direction
Car (1) exited tunnel in EW direction...
Car (2) exited tunnel in EW direction...
Car (3) exited tunnel in EW direction...
Ambulance 31 exited the tunnel in WE direction
Car (4) entered tunnel in EW direction...
Car (17) entered tunnel in WE direction...
Car (17) exited tunnel in WE direction...
Car (18) entered tunnel in WE direction...
Car (4) exited tunnel in EW direction...
Car (5) entered tunnel in EW direction...
Car (18) exited tunnel in WE direction...
Car (19) entered tunnel in WE direction...
Car (5) exited tunnel in EW direction...
Car (6) entered tunnel in EW direction...
Car (19) exited tunnel in WE direction...
Car (20) entered tunnel in WE direction...
Car (20) exited tunnel in WE direction...
Car (21) entered tunnel in WE direction...
Car (6) exited tunnel in EW direction...
Car (8) entered tunnel in EW direction...
Car (21) exited tunnel in WE direction...
Car (22) entered tunnel in WE direction...
Car (8) exited tunnel in EW direction...
Car (7) entered tunnel in EW direction...
Car (22) exited tunnel in WE direction...
Car (23) entered tunnel in WE direction...
Car (23) exited tunnel in WE direction...
Car (24) entered tunnel in WE direction...
Car (7) exited tunnel in EW direction...
Car (9) entered tunnel in EW direction...
Car (24) exited tunnel in WE direction...
Car (25) entered tunnel in WE direction...
Car (9) exited tunnel in EW direction...
Car (10) entered tunnel in EW direction...
Car (25) exited tunnel in WE direction...
Car (26) entered tunnel in WE direction...
Car (26) exited tunnel in WE direction...
Car (27) entered tunnel in WE direction...
Car (10) exited tunnel in EW direction...
Car (11) entered tunnel in EW direction...
Car (27) exited tunnel in WE direction...
Car (28) entered tunnel in WE direction...
Car (11) exited tunnel in EW direction...
Car (12) entered tunnel in EW direction...
Car (28) exited tunnel in WE direction...
Car (29) entered tunnel in WE direction...
Car (29) exited tunnel in WE direction...
Car (30) entered tunnel in WE direction...
Car (12) exited tunnel in EW direction...
Car (13) entered tunnel in EW direction...
Car (30) exited tunnel in WE direction...
Car (13) exited tunnel in EW direction...
Car (14) entered tunnel in EW direction...
Car (14) exited tunnel in EW direction...
Car (15) entered tunnel in EW direction...
Car (15) exited tunnel in EW direction...
Everyting finished...

Let’s zoom in on what happened here. Here is the relevant part of the output:

Car (1) entered tunnel in EW direction...
Car (2) entered tunnel in EW direction...
Car (3) entered tunnel in EW direction...
Car (16) entered tunnel in WE direction...
Car (16) exited tunnel in WE direction...
Ambulance 31 entered the tunnel in WE direction
Car (1) exited tunnel in EW direction...
Car (2) exited tunnel in EW direction...
Car (3) exited tunnel in EW direction...
Ambulance 31 exited the tunnel in WE direction
Car (4) entered tunnel in EW direction...

Notice the following:

  • There are 3 east-west cars in the tunnel.
  • One west-east car arrived at the tunnel, entered, and then left.
  • When the ambulance arrived, only the west-east lane was open, then the ambulance took that lane even though it arrived from the east-west direction.
  • While the ambulance was in the tunnel (i.e., before the Ambulance 31 extied the tunnel in WE direction line), cars only left the tunnel, but no new cars entered, even though car (4) could have entered when car (1) exited.
  • Once the ambulance exited the tunnel, then new cars can go depending on the state of the tunnel.

Step 3: More Ambulances

For this step, change the number of ambulances back to 7.

Now, we must consider what happens when we allow more than one ambulance to arrive. If those ambulances arrive at different times, then there’s really nothing to worry about. However, if ambulances arrive concurrently, then we have a few issues.

Here are the requirements for multiple ambulances:

  • If an ambulance arrives and there is an open lane, then the ambulance can enter the tunnel, even if there was another ambulance already in the tunnel. This means that at most, we can have 4 ambulances in the tunnel at the same time.
  • If an ambulance arrives and the tunnel is full (all lanes are occupied, either by cars or other ambulances or a combination of the two), then that ambulance must wait for the first open lane.
  • If an ambulance is waiting, then that ambulance has priority over all waiting cars. In other words, if a car that was in the tunnel exits, then we should definitely allow the ambulance to go in and use that lane, even if there are other waiting cars. More concretely, a waiting ambulance has priority over any waiting car, so any lane that opens must directly go to a waiting ambulance.
  • If an ambulance leaves the tunnel and there are still other ambulances (either waiting or in the tunnel), then all cars must remain blocked. It is only when all ambulances have left the tunnel that cars can start going in.

This is a little bit of doozy and requires some very careful waiting and signaling combinations. I ended up using 5 condition variables and a single mutex, but that is definitely not the only way to solve the problem. Use as many condition variables as you need, though I do recommend sticking to a single mutex.

Update your implementation to satisfy the above concurrency requirements. You can compile your code using make tunnel and then run it using ./tunnel. Here is the sample output I had in my solution:

$ ./tunnel
Car (1) entered tunnel in EW direction...
Car (2) entered tunnel in EW direction...
Car (3) entered tunnel in EW direction...
Car (16) entered tunnel in WE direction...
Car (16) exited tunnel in WE direction...
Ambulance 31 entered the tunnel in WE direction
Car (2) exited tunnel in EW direction...
Car (1) exited tunnel in EW direction...
Car (3) exited tunnel in EW direction...
Ambulance 31 exited the tunnel in WE direction
Car (4) entered tunnel in EW direction...
Car (17) entered tunnel in WE direction...
Car (17) exited tunnel in WE direction...
Car (18) entered tunnel in WE direction...
Car (4) exited tunnel in EW direction...
Car (6) entered tunnel in EW direction...
Ambulance 32 entered the tunnel in EW direction
Car (18) exited tunnel in WE direction...
Ambulance 33 entered the tunnel in EW direction
Ambulance 34 entered the tunnel in WE direction
Ambulance 32 exited the tunnel in EW direction
Ambulance 33 exited the tunnel in EW direction
Ambulance 34 exited the tunnel in WE direction
Car (5) entered tunnel in EW direction...
Car (20) entered tunnel in WE direction...
Car (6) exited tunnel in EW direction...
Car (7) entered tunnel in EW direction...
Car (20) exited tunnel in WE direction...
Car (21) entered tunnel in WE direction...
Car (5) exited tunnel in EW direction...
Car (8) entered tunnel in EW direction...
Car (7) exited tunnel in EW direction...
Car (9) entered tunnel in EW direction...
Ambulance 35 entered the tunnel in EW direction
Car (21) exited tunnel in WE direction...
Ambulance 36 entered the tunnel in WE direction
Ambulance 35 exited the tunnel in EW direction
Ambulance 37 entered the tunnel in EW direction
Ambulance 36 exited the tunnel in WE direction
Ambulance 37 exited the tunnel in EW direction
Car (10) entered tunnel in EW direction...
Car (19) entered tunnel in WE direction...
Car (8) exited tunnel in EW direction...
Car (11) entered tunnel in EW direction...
Car (9) exited tunnel in EW direction...
Car (12) entered tunnel in EW direction...
Car (19) exited tunnel in WE direction...
Car (22) entered tunnel in WE direction...
Car (10) exited tunnel in EW direction...
Car (13) entered tunnel in EW direction...
Car (11) exited tunnel in EW direction...
Car (14) entered tunnel in EW direction...
Car (12) exited tunnel in EW direction...
Car (15) entered tunnel in EW direction...
Car (22) exited tunnel in WE direction...
Car (23) entered tunnel in WE direction...
Car (13) exited tunnel in EW direction...
Car (14) exited tunnel in EW direction...
Car (23) exited tunnel in WE direction...
Car (24) entered tunnel in WE direction...
Car (15) exited tunnel in EW direction...
Car (24) exited tunnel in WE direction...
Car (25) entered tunnel in WE direction...
Car (25) exited tunnel in WE direction...
Car (26) entered tunnel in WE direction...
Car (26) exited tunnel in WE direction...
Car (27) entered tunnel in WE direction...
Car (27) exited tunnel in WE direction...
Car (28) entered tunnel in WE direction...
Car (28) exited tunnel in WE direction...
Car (29) entered tunnel in WE direction...
Car (29) exited tunnel in WE direction...
Car (30) entered tunnel in WE direction...
Car (30) exited tunnel in WE direction...
Everyting finished...

Again, your output will be different, but here are a couple of observations (in addition to the ones above):

  • No more than 4 ambulances can be in the tunnel as the same time.
  • No new cars can enter the tunnel between an ambulance entering and ambulance exiting pair of statement.
  • If more than one ambulance entered the tunnel, then no new cars can enter the tunnel until all ambulances leave.

To simplify things a bit, it does not matter the order in which the ambulances enter the tunnel, nor which lane they end up taking, i.e., if an ambulance enters the tunnel and both an east-west and a west-east lanes are open, then it doesn’t matter which one that ambulance takes.

Submission

Submit all of your .c files to Gradescope as usual. There are no special submission requirements.

Guidance on how we grade:

Some guidance on how we grade:

  • You can get 25% of points if your solution reliably produces correct output with the given data (and small modifications). 0 points if doing this requires weird sleeps or other hacky non-general purpose code.
  • You can get 50% points you did above and your solution is plausible and does not do something obviously bad. It’s impossible to enumerate every obviously bad thing but here’s a big one : having multiple concurrent threads modify a global variable. Basically this is for solutions that basically are OK but miss some edge cases.
  • You can get 50% points if you have a fully working solution but you utilize non-standard functions (i.e. stuff other than pthread_cond_signal/wait, pthread_mutex_lock/unlock)
  • A fully correct solution, even if it’s not the one we envisioned, is worth 100%