Week 10 Laboratory Exercises

dcc compile_c_files.c -o compile_c_files
ls -1
compile_c_files
compile_c_files.c
file_modes.c
file_sizes.c
./compile_c_files file_sizes.c file_modes.c
running the command: "/usr/local/bin/dcc file_modes.c -o file_modes"
running the command: "/usr/local/bin/dcc file_sizes.c -o file_sizes"
ls -1
compile_c_files
compile_c_files.c
file_modes
file_modes.c
file_sizes
file_sizes.c
file file_modes
file_modes: ELF 64-bit LSB executable # ...

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest compile_c_files 

When you are finished working on this exercise, you must submit your work by running give:

give cs1521 lab10_compile_c_files compile_c_files.c

You must run give before Monday 05 August 12:00 (midday) (2024-08-05 12:00:00) to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Provided for you is a file, fix_race.c that contains a global variable: global_counter, and a function perform_increment:

int global_counter = 0;

void perform_increment(void) {
   global_counter = global_counter + 1;
}

Unfortunately, perform_increment is currently not safe to call from multiple threads simultaneously! As it stands, this causes a data race, resulting in our program not printing the desired output:

make fix_race
dcc -pthread fix_race.c test_fix_race.c -o fix_race

should output "Global counter result: 500000000"
./fix_race 50 1000000
Global counter result: 49851959
./fix_race 50 1000000
Global counter result: 49787244
./fix_race 50 1000000
Global counter result: 50000000
./fix_race 50 1000000
Global counter result: 49285021
./fix_race 50 1000000
Global counter result: 49659783

The ./fix_race 50 1000000 specifies that 50 threads will each call perform_increment 1000000 times.

Your task is to fix the program by making the perform_increment function thread-safe to call (i.e. it can be called by multiple threads simultaneously and maintain correct program behaviour).

There are two predominant approaches to solving this exercise that we have explored in this course. Firstly, you could use a mutex (pthread_mutex_t) to guard access to the global_counter. Secondly, you could modify the global_counter to be an atomic variable, and ensure you increment it atomically.

Both of these approaches are perfectly valid -- and in-fact, we strongly suggest that you solve this exercise twice, trying each approach. Note that there is only a single submission for this exercise, so in that case you will have to choose which approach to submit.

An example of using a mutex can be found in the bank_account_mutex.c lecture code.

An example of using atomics can be found in the bank_account_atomic.c lecture code.

When your program is working, it should behave as follows:

make fix_race
dcc -pthread fix_race.c test_fix_race.c -o fix_race
./fix_race 50 1000000
Global counter result: 50000000
./fix_race 50 1000000
Global counter result: 50000000
./fix_race 50 1000000
Global counter result: 50000000
./fix_race 50 1000000
Global counter result: 50000000
./fix_race 50 1000000
Global counter result: 50000000
./fix_race 50 1000000
Global counter result: 50000000

Use make(1) to build your code:

make    # or 'make fix_race'

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest fix_race 

When you are finished working on this exercise, you must submit your work by running give:

give cs1521 lab10_fix_race fix_race.c

You must run give before Monday 05 August 12:00 (midday) (2024-08-05 12:00:00) to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Provided for you is a file, fix_deadlock.c that contains 6 functions executed as threads:

• alice_withdraw
• bob_withdraw
• alice_deposit
• bob_deposit
• alice_send_bob
• bob_send_alice

Each of these threads modifies 2 of 3 global variables, each protected by their own mutex. These global variables (and their accompanying mutexes) are:

• int bank_account (guarded by: pthread_mutex_t bank_account_mutex)
• int alice_wallet (guarded by: pthread_mutex_t alice_wallet_mutex)
• int bob_wallet (guarded by: pthread_mutex_t bob_wallet_mutex)

However, this program has a problem: it (almost always) deadlocks! Although there are many different avenues for this program to deadlock currently, we can examine a single example of how it may be possible.

Consider the case where alice_withdraw and alice_deposit are executing in parallel. Let's say alice_withdraw manages to lock the bank_account_mutex right at the same time as alice_deposit manages to lock the alice_wallet_mutex (these are lines 29 and 65 respectively). Following onto the next line of code for each thread, we see that alice_withdraw then tries to lock the alice_wallet_mutex, which it will not be able to since we just established that the alice_deposit function just locked that mutex. However, alice_deposit's next line of code will attempt to lock the bank_account_mutex, which alice_withdraw is currently holding!

In this scenario, both threads are stuck waiting for each other's mutexes, but because they're both stuck (and cannot progress), each will never be able to unlock their own mutexes in order to allow the other thread to lock it and make further progress! This is a classic deadlock scenario!

Your task is to fix the program by establishing a global ordering of lock acquisition! Curiously enough, we have already worked through the process of fixing a (slightly simpler) deadlock scenario during lectures

An example of using a mutex incorrectly can be found in the bank_account_broken.c lecture code.

An example of using a mutex correctly can be found in the bank_account_mutex.c lecture code.

You should not solve this exercise by attempting to modify the behaviours of threads, or by making some threads do nothing, or by changing the types of any global variables, or by removing or introducing any new ones.

You should simply swap the ordering of some mutex lock and unlocks such that a global ordering is established, which will free your program from deadlock. Once this is achieved, (assuming you didn't violate any of the above conditions), your task is complete!

When your program is working, it should behave as follows:

make fix_deadlock
dcc -pthread fix_deadlock.c test_fix_deadlock.c -o fix_deadlock
./fix_deadlock
bank account balance: $10000.00
alice wallet balance: $200.00
bob   wallet balance: $200.00

Use make(1) to build your code:

make    # or 'make fix_deadlock'

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest fix_deadlock 

When you are finished working on this exercise, you must submit your work by running give:

give cs1521 lab10_fix_deadlock fix_deadlock.c

You must run give before Monday 05 August 12:00 (midday) (2024-08-05 12:00:00) to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Provided for you is a file, thread_chain.c that spawns a new thread: my_thread, which calls a provided function thread_hello() before terminating.

#include <pthread.h>
#include "thread_chain.h"

void *my_thread(void *data) {
    thread_hello();
    
    return NULL;
}

void my_main(void) {
    pthread_t thread_handle;
    pthread_create(&thread_handle, NULL, my_thread, NULL);

    pthread_join(thread_handle, NULL);
}

When we run the program, we are greeted with the following output:

make thread_chain
dcc -pthread thread_chain.c test_thread_chain.c -o thread_chain -Wl,--wrap=pthread_create
./thread_chain
Hello from thread 01!
ERROR: thread_hello was called less than 50 times!
help: it was only called 1 time(s)
the program will now exit

Your task is to make this program generate a chain of 50 threads that each say hello! Your my_main should continue to simply create one thread, however the thread it creates (my_thread) should modify its behaviour as follows:

It should continue to first call the thread_hello function. thread_hello will print the Hello from thread N! message for you as required -- do not try to manually print this message yourself as you will lose marks. It should then create another thread which continues this same process.

Similiarly to how we wrote recursive functions in the first week of COMP1521, you should make the thread create another thread that uses the same my_thread function as its entry point. Finally, it should call pthread_join on the newly created thread, in order to make sure our current thread waits for the new thread to finish!

This however, would cause an endless chain of threads spawning threads spawning threads, ad infinitum! In this exercise, you are required to make the chain have exactly length 50.

The following is a diagram to help illustrate what this chain conceptually looks like:

When your program is working, it should behave as follows:

make thread_chain
dcc -pthread thread_chain.c test_thread_chain.c -o thread_chain -Wl,--wrap=pthread_create
./thread_chain
Hello from thread 01!
Hello from thread 02!
Hello from thread 03!
Hello from thread 04!
[ ... output redacted ... ]
Hello from thread 47!
Hello from thread 48!
Hello from thread 49!
Hello from thread 50!

Use make(1) to build your code:

make    # or 'make thread_chain'

When you think your program is working, you can use autotest to run some simple automated tests:

1521 autotest thread_chain 

When you are finished working on this exercise, you must submit your work by running give:

give cs1521 lab10_thread_chain thread_chain.c

You must run give before Monday 05 August 12:00 (midday) (2024-08-05 12:00:00) to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.