In the readers-writers problem, readers can enter the critical section concurrently but writers require exclusive access. The implementation described here is not concerned with fairness.

File Organization

The readers-writers problem is in the subdirectory problems/readers-writers. It contains the following files:

main.cpp: Driver program
sections.h: Classic mutual exclusion model interface
sections.c: Classic mutual exclusion model skeleton
sections-soln.c: Implementation (solution) of readers-writers using mutual exclusion section template
checker.cpp / checker.h: Checker implementation
Makefile: Used to build the program (assumes that the MDAT library and suds are built)
Makefile-soln: Used to build the solution - uses sections-soln.c instead of sections.c
run-mdat.py: Script used to run the implementation multiple times so different randomly generated schedules can be run
func_list.txt: List of functions that require instrumentation (file is used by suds)

The functionality is divided across the files such that the students only have to add their code in sections.c. It includes the following five functions:

void sectionInitGlobals();
void sectionEntrySection(int isWriter);
void sectionCriticalSection(int isWriter);
void sectionExitSection(int isWriter);
void sectionRemainderSection(int isWriter);

Students only have to implement sectionInitGlobals, sectionEntrySection, and sectionExitSection. The function sectionInitGlobals is called at the beginning of the program before any threads are created. This function is used to initialize any global variables, especially locks and semaphores. This function is empty in the skeleton provided to students.

The other four functions refer to the different sections of classical mutual exclusion model. The functions sectionEntrySection and sectionExitSection are empty except for a single call to mdat_enter_section. This call must remain at the beginning of each function in order for the checker to work properly. The other two functions sectionCriticalSection and sectionRemainderSection do not need further modification. The function sectionCriticalSection has some dummy code so threads stay in the section longer. We found this increases the probability of finding certain mutual exclusion violations when using random schedules.

The file sections-soln.c shows a possible solution to the readers-writers problem.

Note: The file sections.c is written in C because suds, the instrumentation program, only operates on C code. The file main.cpp is written in C++ because students coming to this class have C++ experience (and no experience with C) and I wanted students to be able to read and understand the code in main.cpp. Obviously, the code students have to write is C code but the necessary code does not require any of the C++ object-oriented features. In the two classes that used MDAT, this did not lead to any confusion (in fact, I did not receive a single question on the topic).

The file main.cpp is a driver program that processes command line arguments (many which are passed to the MDAT library via mdat_init), creates the requested number of threads, and cycles through each of the sections in a loop:

for (int i = 0; i < numRounds; i++) {
  sectionEntrySection(isWriter);            // Entry section
  sectionCriticalSection(isWriter);         // Critical section
  sectionExitSection(isWriter);             // Exit section
  sectionRemainderSection(isWriter);        // Remainder section
}

Each thread is automatically assigned to be a reader or a writer (the operations are split evenly among the threads).

This file is provided and students are not allowed to modify the file. You may wish to alter the organization such that students are creating the threads instead of providing this to the students. In my class, students had an earlier assignment where they got experience creating their own multithreaded program using the pthreads library.

Building the Program

Simply use the provided Makefile to build the program: make

This will build the program using the incomplete skeleton. Since there are no restrictions in the skeleton, the executable that is produced will almost certainly trigger a mutual exclusion violation where a writer does not have exclusive access.

To build an executable that uses the solution instead of the skeletion, use Makefile-soln instead: make -f Makefile-soln

Running the Program

When the program is compiled, it creates an executable called mdat. There are five command line flags, two are required and three are optional:

Required?	Flag	Long name	Description
required	`-t` number-of-threads	`--threads`	Number of threads
required	`-r` number-of-rounds	`--rounds`	Number of rounds
optional	`-i`	`--interactive`	Run in interactive mode
optional	`-o` trace-file-name	`--output`	Create output trace in specified file
optional	`-s` number	`--seed`	Sets the random number generator seed

Example:

./mdat –t 16 –r 10 –o trace.txt

Runs mdat with 16 threads for 10 rounds. The debugging trace is placed in the file trace.txt.

Using the Instrumentation Tool

The instrumentation tool suds will automatically add calls to mdat_invoke_scheduler after every statement. There is no need to do this manually. The instrumentation tool is automatically called within the provided Makefile. If you wish to use suds manually or modify the Makefile, follow these steps:

Run the code through the preprocessor: gcc –E sections.c > sections.i -I. –I<mdat.h-location>
- Replace <mdat.h-location> with a path to the directory where mdat.h is located.
Invoke suds: suds –suffix mdat –use_func_list func_list.txt sections.i
- This command line assumes suds is in the path.
- This will create the file sections.mdat.c where mdat comes from the –suffix command line argument. The default suffix is suds if –suffix is not present.
- Specifying -use-func-list func_list.txt directs suds to only instrument the functions listed in func_list.txt. If –use-func-list is not present, suds will instrument all of the files. This can be problematic in that mdat_invoke_scheduler should not be called until mdat_init is called.

Checker

The checker for the readers-writers problem works by tracking the number of readers and writers in the critical section.

Each time a reader enters the critical section, the number of readers is incremented. Each time a reader enters the exit section (which marks the end of the critical section), the number of readers is decremented.
Similarly, each time a writer enters the critical section, the number of writers is incremented. Each time a writer enters the exit section, the number of writers is decremented.
If there is one writer and at least one reader, the checker will report an error indicating that a reader and a writer are both in the critical section at the same time.
If there are two or more writers, the checker will report an error indicating that there are two writers in the critical section at the same time.
To ensure there solution is not too restrictive and only allows one reader or writer (which can be easily implemented using a single lock), the checker will set a flag any time two or more readers are in the critical section at the same time. This flag is initially false. If the end of the program is reached and this flag is not set, it means there was never a case where two readers were in the critical section concurrently, and a warning is reported.
- This check is subject to false alarms, especially with small thread counts, in that it is possible not to have two concurrent readers due to the randomly generated schedule not because the solution is too restrictive.
- If you test the solution a large number of times (100 or more) with 20 or more threads and this error is reported every time, it is extremely likely that the solution is too restrictive.
- This particular check has not been student-tested and has the potential of confusing the student instead of helping them. It has only been used as an aid in evaluating student submissions. You may wish to disable this particular check.

For precise implementation details, please consult the checker.cpp source code file. It is only 58 lines long!

Automation Script

The script run-mdat.py allows the program to be run a user-specified number of times. In order to fully achieve the power of MDAT, it is necessary to run a program multiple times so it can be tested with several randomly-generated schedules. This script facilitates the automation of this process.

The command line parameters for run-mdat.py:

Required?	Flag	Long name	Description
required	`-R` number-of-runs	`--runs`	Number of runs
required	`-t` number-of-threads	`--threads`	Number of threads
required	`-r` number-of-rounds	`--rounds`	Number of rounds
optional	`-c`	`--continue`	Continue past an error

Example:

./run-mdat.py -R 100 –t 16 –r 10

Runs mdat 100 times - each with a different random schedule. Each MDAT instance consists of 16 threads running for 10 rounds.

Additional notes:

Unless the -c flag is specified, the script will stop if a run with an error occurs. The debugging trace is placed in the file trace.mdat.
If the -c flag is specified, the script will execute all runs even if an error occurs. The number of passing and failing runs will be displayed once all runs have been completed. Traces of failing runs are not saved in this mode.
The default behavior of stopping on an error is the intended way for students to use the script. Once they get an error, the program stops, the debugging trace is saved. Using the trace, students can debug their solutions. The –c switch is intended more for instructors during grading to see how frequently an error occurs. If an error occurs in every single run, the student is likely aware that their solution is buggy and were unable to fix the problem.