CS-3013 Operating Systems                                                                      WPI, A-term 2008
Hugh C. Lauer                                                                                        Project 3 (20 points)
Assigned: Tuesday, September 16, 2008        Due: Thursday, September 25, 2008, 6:00 PM

Introduction & Problem statement

This project is intended to introduce you to working with threads and synchronization primitives with a process. You will implement a simple shared data structure that supports access and updating by multiple threads, and you will implement a multi-threaded test program to exercise that data structure and convince yourself that your design for synchronizing access to it is sufficient.

This project is also intended to prepare you for Project 4, in which you will implement a mailbox facility with a similar interface but inside the Linux kernel, so that threads can send messages to different processes.

You should implement this project in the C language.

Shared data structure

The shared data structure will be a doubly-linked list such as the one described in class in the lecture on Monitors (see .ppt,, html, slides 27-29). A sample header file is project3.h.

Each item in the list should be defined by the following structure:–

struct Item {
   struct Item *next,*prev;
   pthread_t creating_thread;
   struct timespec time_added;
};

The list itself is defined by the following two variables implemented in your program:–

extern struct Item *head, *tail;

The maximum number of items in your list is defined by the following:–

#define MAX_ITEMS 128

You must implement two functions:–

int AddItem(int block)

int RemoveItem(pthread_t *threadID, timespec *time_added,
int block)
#define BLOCK 1
#define NO_BLOCK 0

The function AddItem simply creates a new Item using malloc(), fills in the creating_thread field of with the ID of the invoking thread and the time_added field with the current time in seconds and nanoseconds from the clock_gettime() function. It then appends the Item to the end of the doubly-linked list. AddItem returns zero if it successfully creates and adds the new Item to the list, and it returns an error code if not. In particular, if the list is full (i.e., if it has as many as MAX_ITEMS items in its list) and if block = BLOCK, AddItem blocks until at least one item has been removed, so that the number of items never exceeds MAX_ITEMS. However, if block = NO_BLOCK and the list is full, AddItem returns immediately with an error code and no new item is added to the list.

The function RemoveItem is the opposite of AddItem. It removes the first Item from the linked list, frees the memory using free(), and returns the thread ID of the thread that inserted the item and the time that the item was inserted into the list. RemoveItem returns zero if it successfully removed an item and an error code if not. If the list is empty and block = BLOCK, RemoveItem blocks and waits until something has been added to the list. If, however, block = NO_BLOCK and the list is empty, RemoveItem returns immediately with an error code and does no valid values in *threadID and *time_added.

Two error codes have been defined for this assignment, namely

#define LIST_FULL 1001
#define LIST_EMPTY 1002

If you discover that other codes are needed, you must invent them and document them in your write-up.

Implementation

You should implement your list and the functions AddItem and RemoveItem, in a C program called Project3.c. Your Makefile should compile this to Project3.o. You may add definitions and declarations to Project3.h specified as part of this assignment, but you should not change any existing definitions or declarations.

To implement Project3.c, you will need to use the various synchronization functions available to Linux user-space programs. For example, if you choose to implement the management and synchronization of the list and functions as a monitor, then

· pthread_mutex_lock() and pthread_mutex_unlock() can be used to simulate the monitor lock, and

· pthread_cond_wait() and pthread_cond_signal() can be used to simulate condition variables.

Alternatively, if you chose to implement the linked list as in a Producer-Consumer model, then

· sem_wait() and sem_post() can be used to for the semaphores, but updating the links of the list will still have to be protected by a pthread_mutex.

These primitives and functions are described in the Linux man pages and documentation.

Test Program

In a separate C program called Project3-Test.c, implement a multi-threaded test program to test your list facility. This test program will obviously include Project3.h and will be linked with Project3.o by your Makefile.

The main function of Project3-Test.c should be a master or control that parses the command line, creates other “worker” threads using pthread_create(), lets them run for a while, then tells them to stop, and collects their results. When all threads have finished, the master prints a summary and exits. The worker threads come in two flavors – those that add items to the list and those that remove items from the list. The numbers of each kind of worker thread is determined by the master from arguments on the command line. The duration (in seconds) of the run should also be an argument on the command line.

The command line for the test program would therefore be

Project3-Test #adding_threads #removing_threads duration

Each worker thread operates in a loop in which it waits a random number of milliseconds (not longer than one second), checks to see whether it needs to stop, and, if not, executes its operation with block set to BLOCK. It then repeats this loop until the master tells it to stop. At this point, an “adding” thread merely exits as described below. On the other hand, a “removing” thread should continue looping (without waiting) and execute RemoveItem with block set to NO_BLOCK. This way, it can clear out the items still on the list when the master initiated the stop.

Your master will also have to address the situation of ordering stop when some “removing” threads are still blocked. For example, it could add some dummy items to the list to cause the “removing” threads to unblock. You should also convince yourself that blocked “adding” threads will eventually unblock themselves as the “removing” threads clear out the list.

When any worker thread completes its loop, it should exit by calling pthread_exit() with a status indicating the number of items that it has added or removed. After telling threads to stop, the master should wait for each thread to exit by calling pthread_join(), which returns the status of the exited thread. The master accumulates this status information and generates a summary message showing the how many adds or deletes were performed by each thread.

If your implementation of Project3.c is correct, the test program should be able to run for many minutes or hours with a large number of worker threads (i.e., tens or hundreds). If your synchronization is incorrect, however, you will typically find that the program locks up very quickly and that you will have to kill the process. To help debugging, it is suggested that the master and worker threads use printf() to print progress on the standard output.

Note that if the number of “adding” threads exceeds the number of “removing” threads, “adding” threads will tend to block until the “removing” threads catch up. Likewise, if the number of “removing” threads exceeds the number of “adding” threads, the “removing” threads will tend to block until the “adding” threads catch up.

Write-up

This project requires a more comprehensive write-up than most projects of this course or of other courses. In your write-up, you must document and explain the programming invariants that you use to manage the linked list and its updating. That is, you must explain in clear, logical English (with or without mathematical notation) what assertions are true about the linked list and the variables head and tail whenever AddItem or RemoveItem are not executing and also how AddItem and RemoveItem preserve those invariants. Finally, you must prove or provide a convincing argument that items are removed from the list in the order that they were inserted.

For reference, you can consult the slides pertaining to Monitors and Producer-Consumer synchronization here (.ppt, html). In addition, a copy of the Monitor example from class is reproduced at the end of the document.

Individual Project and Execution Environment

This is an individual project. You may carry out the development on any modern Linux system, but it will be graded on the environment of your virtual machine. Any differences in compiler warnings or execution between another environment and that of your virtual machine will be decided in favor of the virtual machine.

You may discuss the problem assignment with your classmates, TAs, and other people, and you may work out a joint solution on the whiteboard. Once you have arrived at a joint solution, however, you must code it in your own coding style and write the document in your own words. Copying from other students or from previous assignments of this project is a violation of the WPI Academic Honesty Policy.

Grading

This project represents twenty points. Grading will be allocated approximately as follows: –

· Makefile correctly compiles Project3.c and Project3-Test.c without warnings — 1 point.

· Correctly executes your test case with a variety of arguments with no memory leaks — 5 points.

· Correctly links with and executes the grader’s test case with no memory leaks — 5 points.

· Satisfactory code review by grader — 4 points.

· Satisfactory write-up describing your programming invariants and implementation — 5 points

Appendix – Monitor example from class