MDAT is a multithreaded testing and debugging infrastructure designed for students learning to program with multiple threads. MDAT automatically generates random schedules to allow students to more thoroughly test their programs. The design of MDAT takes full control over the scheduling allowing a failing run to be reproduced. To assist debugging, MDAT includes an output trace that shows the status of all threads, locks, and semaphores in the program and has an interactive mode that allows students to try out their own schedules.

Starting out with MDAT

MDAT consists of four directories:

doc: documentation
mdat: MDAT library
problems: three different synchronization problems that use MDAT
suds: SUDS instrumentation tool

To compile the MDAT library, switch to the mdat directory and type: make

To compile the SUDS instrumentation tool, switch to the suds directory and type: make

To compile any of the three synchronization problems, switch to the subdirectory under problems and type: make (Note: The synchronization problems require that the MDAT library and suds are already built.)

MDAT Interface

This section describes the interface for the MDAT library. The interface is defined in mdat.h so all programs using the interface need to include this file. MDAT can be used for C and C++ problems but suds, the provided instrumentation tool only supports C programs.

From a synchronization perspective, MDAT supports both locks and semaphores. Only the basic synchronization operations are used as shown in the following table:

MDAT function	POSIX function
mdat_mutex_init	`pthread_mutex_init`
mdat_mutex_lock	`pthread_mutex_lock`
mdat_mutex_unlock	`pthread_mutex_unlock`
mdat_sem_init	`sem_init`
mdat_sem_wait	`sem_wait`
mdat_sem_post	`sem_post`

Some implementation notes regarding these functions:

The argument lists for the MDAT and POSIX calls are identical except that mdat_mutex_init and mdat_sem_init both have an additional parameter for the name. The name is used in the debugging trace.
The functionality of the locks and semaphores is handled internally by the MDAT library – the states of the locks and semaphores are unchanged. Therefore, if a lock or semaphore is used by an MDAT function, then it should not be used in a POSIX function, and vice versa.

In addition to these synchronization functions, the MDAT interface consists of five additional functions:

MDAT Implementation

This section describes relevant details of the MDAT implementation.

Error Handling

For better or for worse, all errors detected by MDAT cause the program to abort. Errors are handled by the trace facility and the error message will appear both in the trace and on the console. Errors are split up into two categories: internal errors and external errors. Internal errors are due to the result of failed sanity checks within MDAT. They refer to bugs within the MDAT library itself. If you encounter an internal error, please send an email to elars.nosp@m.on@s.nosp@m.eattl.nosp@m.eu.e.nosp@m.du with a description of the problem.

External errors either refer to synchronization bugs in the code (such as deadlock) or cases where MDAT was not used properly (such as initializing MDAT with an invalid scheduler mode).

Scheduling

Scheduling decisions are made at the following times:

When mdat_invoke_scheduler is called.
At the end of mdat_mutex_lock.
At the end of mdat_mutex_unlock.
At the end of mdat_sem_wait.
At the end of mdat_sem_post.
When a thread finishes by calling mdat_thread_finish (except for the last thread).

The next thread to execute (including the very first thread) is determined by the scheduling mode:

Random: The next thread is selected randomly.
Interactive: The user is prompted for the next thread.

If multiple threads are waiting to acquire a lock or semaphore, a similar approach is used to select which thread to wake-up:

Random: The thread to wake-up is selected randomly.
Interactive: The user is prompted to select which thread to wake-up.

Additional notes:

Unless the thread is waiting or finishes, the thread that was just executing before the scheduler was invoked could be dispatched again immediately.
The selection of the thread to wake-up is independent and done before the next scheduling decision. For instance, just because thread 3 is selected to wake up does not necessarily mean that thread 3 will be selected by the scheduler to execute next.
In interactive mode, the user is not permitted to select a thread that is waiting or has already completed.
In interactive mode, the program will exit if the user selects ‘Q’ at any prompt.
If at any point there are no threads to be scheduled, MDAT will abort indicating that deadlock has occurred.

Interfacing with a Checker

Since each problem or program has their own unique synchronization requirements, the checker is external to MDAT. MDAT provides an interface for interacting with a checker via a callback function. Please consult the CheckerWrapper documentation for further details.

Synchronization Problems

MDAT has been used with three synchronization problems:

All problems are described in the Book of Semaphores. To use MDAT with different problems, we expect that most people would start with an existing problem and modify the code appropriately. Since readers-writers is the most familiar of the three problems, detailed documentation is provided. In addition, a solution is provided in its source code directory. The other two problems are implemented in a very similar fashion – the documentation only describes the differences with respect to the readers-writers problem. Solutions are not provided for these problems.