Operating Systems
Thread Synchronization in UNIX
Section 1. Exercises in Lab 3
There are three exercises in this lab. The purpose of this lab is to learn about thread synchronization in Unix-based OS. Due to the difficulty of debugging concurrent programs, the complexity of this lab has been adjusted accordingly. Hence, you should find the required amount of coding "minimal".
General outline of the exercises:
Exercise 1: Basic readers-writers problem
Exercise 2: A more fair readers-writers problem
Exercise 3: Synchronization in a roundabout
Section 2. Readers-Writers Lock
For exercises 1 & 2, it is sufficient to use pthread_mutex imported with the
pthread library.
2.1 Exercise 1
In exercise 1, we will implement the readers-writers lock (RW-Lock) needed to fulfil the basic requirements of the readers-writers problem. Recall that in this problem, there are two kinds of threads – reader threads and writer threads. Each thread is trying to read from or write to a shared resource respectively. The requirements of this problem are:
A writer cannot write to the shared resource when anyone else (reader or writer) is using the
Readers cannot read from the shared resource when a writer is writing to it. However, multiple readers can read the shared resource
Exercise 1 Template
ex1_runner.c is the main driving file for this exercise. In it, you will find the following global variables:
– The “shared resource” to be written and read from
reader_count – The number of readers accessing the shared resource. You should be using this to track the number of
writer_count – The number of writers accessing the shared resource. You should be using this to track the number of
max_concurrent_readers – The maximum number of concurrent readers reached in your
max_mutex – The mutex to update the max_concurrent_readers.
You will also find the following functions:
main |
This is the main driving function for the program. In this function, the following would happen: 1. initialise(read_write_lock), which creates and initializes your lock, so it is ready for use as a RW-lock. 2. WRITERS writer threads are created and initialized, each running the writer function. 3. READERS writer threads are created and initialized, each running the reader function. 4. The created threads are all joined and the result of the program is printed. 5. cleanup(read_write_lock) is then run to perform required resource cleanup. |
writer |
This is the main function call for each writer thread created. It runs WRITE_COUNT loops, each loop performing the following: 1. writer_acquire(read_write_lock) 2. Checks if the conditions are valid for writing. If not, an error will be registered for this thread. 3. Writes its threadid to the shared resource. 4. writer_release(read_write_lock) |
reader |
This is the main function call for each reader thread created. It runs READ_COUNT loops, each loop performing the following: 1. reader_acquire(read_write_lock) 2. Checks if the conditions are valid for reading. If not, an error will be registered for this thread. 3. Checks for number of other readers accessing the shared resource and updates the maximum. 4. Reads the shared resource. 5. reader_release(read_write_lock) |
ex1.c contains implementations of the functions for rw_lock. You have to change the code found in this file.
rw_lock.h and rw_lock_struct.h are header files defining the function declarations and struct declarations for rw_lock, respectively. These header files allow the compiler to know the functions are to be “imported” and used by ex1.c to ex1_runner.c.
Your task is to amend ex1.c and rw_lock_struct.h to solve the readers-writers problem. rw_lock should fulfill the following requirements:
Correctness: The program is ensured to run correctly, according to the rules of the readers-writers problem as mentioned
Concurrency: The highest possible number?)
Your program should be able to run correctly
(What is the Only changes you made in ex1.c and rw_lock_struct.h will be used for grading. You may change the other files provided (rw_lock.h, ex1_runner.c) during your own testing, but note that they will be replaced with the original files when we test your assignments.
2.2. Exercise 2
A problem with the basic solution:
Consider the following sequence of events that can occur:
even if we ensure the basic conditions are met, notice that writers can be starved when such a sequence of actions occur. This can happen as long as one reader is accessing the shared resource before another reader requests access.
Exercise 2 Template
Exercise 2 main program ex2_runner.c is almost identical to ex1_runner.c. The only difference is that the
You can copile and run ex2.c similarly to ex1.c. Likewise, there are also rw_lock.h
and rw_lock_struct.h header files for exercise 2.
Your task for Exercise 2:
For this exercise, you can start from your solution in exercise 1. You may realize that using the same solution from exercise 1 would result in the following output:
This is because in the new program, readers would access the shared resource and “hog” them before any writers can do anything.
Your task is to amend the same files (ex2.c, rw_lock_struct.h), so that:
All requirements from Exercise 1 are still (Correctness and
concurrency)
Less Writer Starvation: Each writer gets to write before all the readers (Is there a way to guarantee no starvation? Under what circumstances can a writer still be starved?)
Only changes you made in ex2.c and rw_lock_struct.h will be used for grading. You may change the other files provided (rw_lock.h, ex1_runner.c) during your own testing, but they will be replaced with the original files when we test your assignments.
If the program terminates correctly and without writer starvation, the following output is expecte
Or, you would see this if less writer starvation is not fulfilled:
Additional resources for synchronization problems
For a detailed and extended view on many synchronization problems check the following book: http://greenteapress.com/semaphores/LittleBookOfSemaphores.pdf Specifically, for readers-writers problem you can check section 4.2.
Section 3. Synchronization in a roundabout using semaphores.
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of