CS353 Project 2: Building a deterministic scheduler (due September 29)

Algorithm

Enter a thread	LOCK(GL)

Leave a thread	UNLOCK(GL)

• Lock the global lock before entering a new thread. This should be done for the main thread too. One way to lock the global lock in the main thread is that lock at the first instance of pthread_create. You can reuse pthread library for the global lock.

pthread_mutex_lock	if (L is held by other threads) UNLOCK(GL); /* select next available thread to execute */ /* wait till L is not held by any other threads */ LOCK(GL); LOCK(L); else LOCK(L);

• The algorithm uses the existing LOCK functionality to suspend the current thread until the lock L is available. However with the existing pthread library we can't know if a thread is waiting for a lock or is ready to execute. Therefore we cannot simply use the pthread lock and unlock primitives to realize the polling lock state and LOCK(L) in the semantics of pthread_mutex_lock, we have to re-implement LOCK semenatics. With your LOCK implementation, you should be able to know 2 things: whether this lock is held by other thread or not, and whether this thread is waiting for a lock or not. In order to map the pthread_mutex_t object and your mutex object, you can use hash table.

pthread_join	UNLOCK(GL); /* select next available thread to execute */ /* wait till joinee terminates */ LOCK(GL);

• Similar to the LOCK, you should maintain status(whether a thread is running or terminated) for each thread. You can use hash table to map the pthread_t object and your own thread object.

sched_yield	UNLOCK(GL); /* select next available thread to execute */ LOCK(GL);

• If there's no other available thread, the calling thread should be executed. If there is another available thread, the other thread should be executed.

You will implement these primitives by using the provided template. The implementation will be compiled to a dynamic library in place of the standard pthread library. When it is linked and executed with a concurrent program, deterministic execution can be achieved. Note that you should not need to change anything in the test programs.

Template

You can use the following template for the basic part of the tool. The template has a basic implementation to wrap pthread functions. Your code should be compiled in the unix or linux machine.

chess.tar.gz

Build

Use the makefile included in the package. Type 'make' in the directory with makefile and source code and chess.so will be built.

Run

Use run.sh in the package. Type './run.sh ./sample' in the directory with chess.so and run.sh will execute program sample in the current directory with the tool.

Sample test program: sample1.c

This program will print out numbers with two threads and the order of numbers will change as schedules. The deterministic scheduler should produce same input at every execution.

You can build sample1.c by typing 'gcc -o sample1 -lpthread -lrt sample1.c' on the shell.