Project 1--EECS 482 (Winter 2003) Worth: 15 points Assigned: Tuesday, January 14th, 2003 Due: 6:00 pm, Tuesday, February 18th, 2003 1 Overview This project will give you experience writing simple multi-threaded programs using monitors and will help you understand how threads and monitors are implemented. The project has two parts. In the first part, you will write a simple concurrent program that schedules disk requests. This concurrent program will use a thread library that we provide. In the second part, you will implement your own version of this thread library. 2 Thread Library Interface This section describes the interface to the thread library for this project. You will write a multi-threaded program that uses this interface, and you will also write your own implementation of this interface. void thread_libinit(thread_startfunc_t func, void *arg, int num_locks, int num_conds_per_lock) thread_libinit is called to initialize the thread library. After initializing the thread library, thread_libinit creates and runs the first thread. This first thread is initialized to call the function pointed to by func with the single argument arg. num_locks specifies the maximum number of locks that will be used in this process. num_conds_per_lock specifies the maximum number of condition variables per lock that will be used in this process. Note that thread_libinit does not return to the calling function (the function that calls thread_libinit will never execute again). void thread_create(thread_startfunc_t func, void *arg) thread_create is used to create a new thread. When the newly created thread starts, it will call the function pointed to by func and pass it the single argument arg. void thread_yield(void) thread_yield causes the current thread to yield the CPU to the next runnable thread. void thread_lock(int lock) void thread_unlock(int lock) void thread_wait(int lock, int cond) void thread_signal(int lock, int cond) void thread_broadcast(int lock, int cond) thread_lock, thread_unlock, thread_wait, thread_signal, and thread_broadcast implement Mesa monitors in your thread library. Locks are numbered from 0 to num_locks-1. Each lock has several condition variables implicitly associated with it, numbered from 0 to num_conds_per_lock-1. Here is the file "thread.h". DO NOT MODIFY OR RENAME IT. thread.h will be included by programs that use the thread library, and should also be included by your library implementation. Solaris also has /usr/include/thread.h, so make sure you use #include "thread.h", NOT #include . ------------------------------------------------------------------------------- /* * thread.h -- public interface to thread library * * This file should be included in both the thread library and application * programs that use the thread library. */ #ifndef _THREAD_H #define _THREAD_H typedef void (*thread_startfunc_t) (void *); extern void thread_libinit(thread_startfunc_t func, void *arg, int num_locks, int num_conds_per_lock); extern void thread_create(thread_startfunc_t func, void *arg); extern void thread_yield(void); extern void thread_lock(int lock); extern void thread_unlock(int lock); extern void thread_wait(int lock, int cond); extern void thread_signal(int lock, int cond); extern void thread_broadcast(int lock, int cond); /* * start_preemptions() can be used in testing to configure the generation * of interrupts (which in turn lead to preemptions). * * The sync and async parameters allow several styles of preemptions: * * 1. async = true: generate asynchronous preemptions every 10 ms using * SIGALRM. These are non-deterministic. * * 2. sync = true: generate synchronous, pseudo-random preemptions before * interrupt_disable and after interrupt_enable. You can generate * different (but deterministic) preemption patterns by changing * random_seed. * * start_preemptions() should be called (at most once) in the application * function started by thread_libinit(). Make sure this is after the thread * system is done being initialized. * * If start_preemptions() is not called, no interrupts will be generated. * * The code for start_preemptions is in interrupt.cc, but the declaration * is in thread.h because it's part of the public thread interface. */ extern void start_preemptions(bool async, bool sync, int random_seed); #endif /* _THREAD_H */ ------------------------------------------------------------------------------- start_preemptions() is part of the interrupt library we provide (interrupt.o, see Section 4.3), but its declaration is included as part of the interface that application programs include when using the thread library. Application programs can call start_preemptions() to configure whether (and how) interrupts are generated during the program. As discussed in class, these interrupts can preempt a running thread and start the next ready thread (by calling thread_yield()). If you want to test a program in the presence of these preemptions, have the application program call start_preemptions() once in the beginning of the function started by thread_libinit(). 3 Disk Scheduler (28%) In this part, you will write a concurrent program to issue and service disk requests. We will provide a working thread library (thread.o) for you to use while testing your disk scheduler. As you write your thread library, the disk scheduler program will also help you test your thread library (and vice versa). The disk scheduler in an operating system gets and schedules disk I/Os for multiple threads. Threads issue disk requests by queueing them at the disk scheduler. The disk scheduler queue can contain at most a specified number of requests (max_disk_queue); threads must wait if the queue is full. Your program should start by creating a specified number of requester threads to issue disk requests and 1 thread to service disk requests. Each requester thread should issue a series of requests for disk tracks (specified in its input file). Each request is synchronous; a requester thread must wait until the servicing thread handles its last request before issuing its next request. A requester thread finishes after all the requests in its input file have been serviced. Requests in the disk queue are NOT serviced in FIFO order. Instead, the service thread handles disk requests in SSTF order (shortest seek time first, see page 319 in the textbook). That is, the next request it services is the request that is closest to its current track. The disk is initialized with its current track as 0. Keep the disk queue as full as possible to minimize average seek distance. That is, your service thread should only handle a request when the disk queue has the largest possible number of requests. This gives the service thread the largest number of requests to choose from. Note that the "largest number of requests" varies depending on how many request threads are still active. When at least max_disk_queue requester threads are alive, the largest possible number of requests in the queue is max_disk_queue. When fewer than max_disk_queue requester threads are alive, the largest number of requests in the queue is equal to the number of living requester threads. You will probably want to maintain the number of living requester threads as shared state. 3.1 Input Your program will be called with several command-line arguments. The first argument specifies the maximum number of requests that the disk queue can hold. The rest of the arguments specify a list of input files (one input file per requester). I.e. the input file for requester r is argv[r+2], where 0 <= r < (number of requesters). The number of threads making disk requests should be deduced from the number of input files specified. The input file for each requester contains that requester's series of requests. Each line of the input file specifies the track number of the request (0 to 999). 3.2 Output After issuing a request, a requester thread should call (note the space characters in the strings): cout << "requester " << requester << " track " << track << endl; After servicing a request, the service thread should call (note the space characters in the strings): cout << "service requester " << requester << " track " << track << endl; Your program should not generate any other output. Note that the console is shared between the different threads. Hence the couts in your program must be protected by a monitor lock to prevent interleaving output from multiple threads. 3.3 Sample Input/Output Here is an example set of input files (disk.in0 - disk.in4). disk.in0 disk.in1 disk.in2 disk.in3 disk.in4 -------- -------- -------- -------- -------- 53 914 827 302 631 785 350 567 230 11 Here is one of several possible correct outputs from running the disk scheduler with the following command: disk 3 disk.in0 disk.in1 disk.in2 disk.in3 disk.in4 (The final line of the output is produced by the thread library, not the disk scheduler.) ------------------------------------------------------------------------------- requester 0 track 53 requester 1 track 914 requester 2 track 827 service requester 0 track 53 requester 3 track 302 service requester 3 track 302 requester 4 track 631 service requester 4 track 631 requester 0 track 785 service requester 0 track 785 requester 3 track 230 service requester 2 track 827 requester 4 track 11 service requester 1 track 914 requester 2 track 567 service requester 2 track 567 requester 1 track 350 service requester 1 track 350 service requester 3 track 230 service requester 4 track 11 Thread library exiting. ------------------------------------------------------------------------------- 3.4 Tips We will provide a working thread library (thread.o) for you to use while testing your disk scheduler. You should first get your disk scheduler working without preemption, then test it with preemption enabled (Section 2 explains how to configure preemptions in your testing). 4 Thread Library (72%) In this part, you will write a library to support multiple threads within a single Solaris process. Your library will support all the thread functions described in Section 2. 4.1 Creating and Swapping Threads You will be implementing your thread library on Sun workstations running the Solaris operating system. Solaris provides some library calls (getcontext, makecontext, swapcontext) to help implement user-level thread libraries. You will need to read the manual pages for these calls. As a summary, here's how to use these calls to create a new thread: #include ucontext_t ucontext; /* * Initialize a context structure by copying the current thread's context. */ getcontext(&ucontext); /* * Direct the new thread to use a different stack. Your thread library * should allocate 256 KB for each thread's stack. */ static const int stack_size = 262144; /* size of each thread's stack */ char *stack = new char [stack_size]; ucontext.uc_stack.ss_sp = stack + stack_size - 8; ucontext.uc_stack.ss_size = stack_size - 8; ucontext.uc_stack.ss_flags = 0; ucontext.uc_link = NULL; /* * Direct the new thread to start by calling start(func, arg). */ makecontext(&ucontext, (void (*)()) start, 3, func, arg); Use swapcontext to save the context of the current thread and switch to the context of another thread. Read the Solaris manual pages for more details. 4.2 Deleting a Thread and Exiting the Program A thread finishes when it returns from the function that was specified in thread_create. Remember to de-allocate the memory used for the thread's stack space and context (do this AFTER the thread is really done using it). When there are no runnable threads in the system (e.g. all threads have finished, or all threads are deadlocked), your thread library should execute the following code: cout << "Thread library exiting.\n"; exit(0); 4.3 Ensuring Atomicity To ensure atomicity of multiple operations, your thread library will enable and disable interrupts. Since this is a user-level thread library, it can't manipulate the hardware interrupt mask. Instead, we provide a library (interrupt.o) that simulates software interrupts. Here is the file "interrupt.h", which describes the interface to the interrupt library that your thread library will use. DO NOT MODIFY IT OR RENAME IT. interrupt.h will be included by your thread library (#include "interrupt.h"), but will NOT be included in application programs that use the thread library. ------------------------------------------------------------------------------- /* * interrupt.h -- interface to manipulate simulated hardware interrupts. * * This file should be included in the thread library, but NOT in the * application program that uses the thread library. */ #ifndef _INTERRUPT_H #define _INTERRUPT_H /* * interrupt_disable() and interrupt_enable() simulate the hardware's interrupt * mask. These functions provide a way to make sections of the thread library * code atomic. * * assert_interrupts_disabled() and assert_interrupts_enabled() can be used * as error checks inside the thread library. They will assert (i.e. abort * the program and dump core) if the condition they test for is not met. * * These functions/macros should only be called in the thread library code. * They should NOT be used by the application program that uses the thread * library; application code should use locks to make sections of the code * atomic. */ extern void interrupt_disable(void); extern void interrupt_enable(void); #define assert_interrupts_disabled() \ assert_interrupts_private(__FILE__, __LINE__, true) #define assert_interrupts_enabled() \ assert_interrupts_private(__FILE__, __LINE__, false) /* * assert_interrupts_private is a private function for the interrupt library. * Your thread library should not call it directly. */ extern void assert_interrupts_private(char *, int, bool); #endif /* _INTERRUPT_H */ ------------------------------------------------------------------------------- Note that interrupts should be disabled only when executing in your thread library's code. The code outside your thread library should never execute with interrupts disabled. E.g. the body of a monitor must run with interrupts enabled and use locks to implement mutual exclusion. 4.4 Scheduling Order This section describe the specific scheduling order that your thread library should follow. Remember that a correct concurrent program must work for all thread interleavings, so your disk scheduler must work independent of this scheduling order. All scheduling queues should be FIFO. This includes the ready queue, the queue of threads waiting for a monitor lock, and the queue of threads waiting for a signal. Locks should be acquired by threads in the order in which the locks are requested (by thread_lock() or in thread_wait()). When a thread calls thread_create, the caller does not yield the CPU. The newly created thread is put on the ready queue but is not executed right away. When a thread calls thread_unlock, the caller does not yield the CPU. The woken thread is put on the ready queue but is not executed right away. When a thread calls thread_signal or thread_broadcast, the caller does not yield the CPU. Any woken threads are put on the ready queue but are not executed right away. Any woken threads request the lock when they next run. 4.5 Example Program Here is a short program that uses the above thread library, along with the output generated by the program. Make sure you understand how the CPU is switching between two threads (both in function loop). "i" is on the stack and so is private to each thread. "g" is a global variable and so is shared among the two threads. ------------------------------------------------------------------------------- #include #include "thread.h" int g=0; void loop(void *a) { char *id; int i; id = (char *) a; cout <<"loop called with id " << (char *) id << endl; for (i=0; i<5; i++, g++) { cout << id << ":\t" << i << "\t" << g << endl; thread_yield(); } } void parent(void *a) { int arg; arg = (int) a; cout << "parent called with arg " << arg << endl; thread_create((thread_startfunc_t) loop, (void *) "child thread"); loop( (void *) "parent thread"); } int main() { thread_libinit( (thread_startfunc_t) parent, (void *) 100, 1, 1); } ------------------------------------------------------------------------------- parent called with arg 100 loop called with id parent thread parent thread: 0 0 loop called with id child thread child thread: 0 0 parent thread: 1 1 child thread: 1 2 parent thread: 2 3 child thread: 2 4 parent thread: 3 5 child thread: 3 6 parent thread: 4 7 child thread: 4 8 Thread library exiting. ------------------------------------------------------------------------------- 4.6 Tips Start by implementing thread_libinit, thread_create, and thread_yield. Don't worry at first about disabling and enabling interrupts. After you get that system working, implement the monitors functions. Finally, add calls to interrupt_disable() and interrupt_enable() to ensure your library works with arbitrary yield points. A correct concurrent program must work for any instruction interleaving. In other words, we should be able to insert a call to thread_yield anywhere in your code that interrupts are enabled. Use assertion statements copiously in your thread library to check for unexpected conditions. These error checks are essential in debugging concurrent programs, because they help flag error conditions early. 4.7 Test Cases An integral (and graded) part of writing your thread library will be to write a suite of test cases to validate any thread library. This is common practice in the real world--software companies maintain a suite of test cases for their programs and use this suite to check the program's correctness after a change. Writing a comprehensive suite of test cases will deepen your understanding of how to use and implement threads, and it will help you a lot as you debug your thread library. Each test case for the thread library will be a short C++ program that uses functions in the thread library (e.g. the example program in Section 4.5). Each test case should be run without any arguments and should not use any input files. If you submit your disk scheduler as a test case, remember to specify all inputs (number of requesters, buffers, and the list of requests) statically in the program. This shouldn't be too inconvenient because the list of requests should be short to make a good test case (i.e. one that you can trace through what should happen). Your test cases should NOT call start_preemption(), because we are not evaluating how thoroughly your test suite exercises the interrupt_enable() and interrupt_disable() calls. Your test suite may contain up to 20 test cases. Each test case may generate at most 10 KB of output and must take less than 60 seconds to run. These limits are much larger than needed for full credit. You will submit your suite of test cases together with your thread library, and we will grade your test suite according to how thoroughly it exercises a thread library. See Section 6 for how your test suite will be graded. 5 Project Logistics Write your thread library and disk scheduler in C++ on Solaris. Declare all internal variables and functions "static" to prevent naming conflicts with programs that link with your thread library. Use g++ (/usr/um/bin/g++) to compile your programs. You may use any functions included in the standard C++ library, except for the STL. You should not use any libraries other than the standard C++ library. We will compile an application program "app.cc" and thread library "thread.cc" with the command "g++ thread.cc app.cc interrupt.o". The STL may not be used because (a) it is not thread-safe with respect to the threads you are building in this project and (b) it is difficult, if not impossible, to subclass any one of the STL classes and wrap its methods with monitor locks. However, the data structures in this project are extremely simple; you should have no trouble writing them on your own. Your thread library must be in a single file and must be named "thread.cc". Your disk scheduler must also be in a single file (e.g. "disk.cc"). We will place copies of thread.h, thread.o, interrupt.h, and interrupt.o in /afs/engin.umich.edu/class/perm/eecs482/proj1 6 Grading, Auto-Grading, and Formatting To help you validate your programs, your submissions will be graded automatically, and the result will be mailed back to you. You may then continue to work on the project and re-submit. The results from the auto-grader will not be very illuminating; they won't tell you where your problem is or give you the test programs. The main purpose of the auto-grader is it helps you know to keep working on your project (rather than thinking it's perfect and ending up with a 0). The best way to debug your program is to generate your own test cases, figure out the correct answers, and compare your program's output to the correct answers. This is also one of the best ways to learn the concepts in the project. The student suite of test cases will be graded according to how thoroughly they test a thread library. We will judge thoroughness of the test suite by how well it exposes potential bugs in a thread library. The auto-grader will first compile a test case with a correct thread library and generate the correct output (on stdout, i.e. the stream used by cout) for this test case. Test cases should not cause any compile or run-time errors when compiled with a correct thread library. The auto-grader will then compile the test case with a set of buggy thread libraries. A test case exposes a buggy thread library by causing it to generate output (on stdout) that differs from the correct output. The test suite is graded based on how many of the buggy thread libraries were exposed by at least one test case. This is known as "mutation testing" in the research literature on automated testing. Remember that your test cases should NOT call start_preemption(), because we are not evaluating how thoroughly your test suite exercises the interrupt_enable() and interrupt_disable() calls. The buggy thread libraries will not have problems with interrupt_disable/enable. You may submit your program as many times as you like. However, only the first submission of each day will be graded and mailed back to you. Later submissions on that day will be graded and cataloged, but the results will not be mailed back to you. See the FAQ for why we use this policy. In addition to this one-per-day policy, you will be given 3 bonus submissions that also provide feedback. These will be used automatically--any submission you make after the first one of that day will use one of your bonus submissions. After your 3 bonus submissions are used up, the system will continue to provide 1 feedback per day. Because you are writing concurrent programs, the auto-grader may return non-deterministic results. In particular, test cases 20-24 for the thread library and test case 3 and 4 for the disk scheduler use asynchronous preemption, which may cause non-deterministic results. Because your programs will be auto-graded, you must be careful to follow the exact rules in the project description: 1) (disk scheduler) Only print the two items specified in Section 3.2. 2) (disk scheduler) Your program should expect several command-line arguments, with the first being max_disk_queue and the others specifying the list of input files for the requester threads. 3) (thread library) The only output your thread library should print is the final output line "Thread library exiting.". Other than this line, the only output should be that generated by the program using your thread library. 4) (thread library) Your thread library should consist of a single file named "thread.cc". 5) Do not modify source code included in this handout (thread.h, interrupt.h). In addition to the auto-grader's evaluation of your programs' correctness, a human grader will evaluate your programs on issues such as the clarity and completeness of your documentation, coding style, the efficiency, brevity, and understandability of your code, etc.. Your final score will be the auto-grader score; feedback from the course staff is for your information only. 7 Turning in the Project Use the submit482 program to submit your files. The full name is /afs/engin.umich.edu/class/perm/eecs482/bin/submit482, but you should add /afs/engin.umich.edu/class/perm/eecs482/bin/ to your path (see the FAQ) so you don't have to keep typing in the full name. submit482 submits the set of files associated with a project part (disk scheduler, thread library), and is called as follows: submit482 ... Here are the files you should submit for each project part: 1) disk scheduler (project-part 1d) a. C++ program for your disk scheduler (name should end in ".cc") example: submit482 1d disk.cc 2) thread library (project-part 1t) a. C++ program for your thread library (name should be "thread.cc") b. suite of test cases (each test case is an C++ program in a separate file). The name of each test case should end in ".cc". c. a file named "README", which contains a description of the contributions of each group member (for the entire project, i.e. both disk scheduler and thread library). example: submit482 1t thread.cc test1.cc test2.cc README Your README file should adhere to the following format: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Project Member: ____________________________________ Contribution ___ % Project Member: ____________________________________ Contribution ___ % Project Member: ____________________________________ Contribution ___ % Add 2-3 sentences per project member describing each member's contribution. If any project member disagrees with this summary evaluation, that member should email the course staff directly at eecs482staff@umich.edu. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ The official time of submission for your project will be the time the last file is sent. If you send in anything after the due date, your project will be considered late (and will use up your late days or will receive a zero).