Out: Wednesday, 15 October
Due: Friday, October 31 at midnight (at or before 11:59 PM)
The project is due at midnight on the indicated due date. Since the project contains some Alpha-specific assembly code, you can only work on the project on Alpha systems running DIGITAL Unix; you must submit your work on orcas or sanjuan using the turnin program.
This is a difficult assignment. You should read through all of the source files and get a general idea as to what the structure of the system is like and what is expected of you before you start writing code. You have two weeks to do this assignment, which should give you plenty of time, but we don't recommend waiting until the last week to start it.
As mentioned in lecture, you will be working with two partners for this project. If you haven't already, one of you should send mail to the TA listing the name of your partners; the partners should be CC'ed on the message. This will allow us to set up project work directories and groups. You should not wait until you have met with your partners to start reviewing the code and instructions for this project.
This assignment is broken down into three parts, the second and third of which rely on the first.
The first part of this assignment is to write a non-preemptive thread management package called minithreads. You will be building a USER-LEVEL threads package on top of a kernel-level process. Many operating systems, such as Mach, DEC OSF/1 and some versions of SUN OSprovide a similar service. Here's (conceptually) how minithreads will work:
In some ways, what we're building in project 2 is a simulation of an operating system kernel scheduler, except we're doing it in user space. There are several reasons to do it this way, rather than to build a system on a bare machine:
Everything you need to start is in /cse/courses/cse451/97au/projects/project2/. Use cp -r to copy the entire project2 tree to your project directory (or personal directory if you want your own copy or want to start working while we get the group directories up).
You must implement the interfaces defined in include/minithread.h and include/synch.h, placing your implementations in src/minithread.c and src/synch.c. You are only allowed to change files in the src subdirectory (and in fact this is the only subdirectory you will turnin).
We are providing you with some low level machine dependent functions for stack allocation and deallocation, and context switching. These are defined in include/minithread_public.h, src/minithread_public.c, include/minithread_md.h and src/sys.S. Skeleton code for src/minithread.c and src/synch.c is provided in src/minithread_skel.c and src/synch_skel.c. You can use this code as a starting place to complete the assignment.
In addition, a skeleton test program, src/runtester.c, is provided. You can use the routine tester() in this file to implement test programs for your minithreads package. We will provide our own implementation of tester() so that we can test you code when you hand it in, so please leave the references to runtester.c in the Makefile. Because this version of minithreads will be non-preemptive, you will have to include calls to minithread_yield() at arbitrary points in your test program to ensure that interleaved executions work correctly.
You may implement any scheduling policy that you like, although if you implement something other than FIFO, you should explain your motivations which led you to do so. If you do implement FIFO, you can use your implementation of queues from project 1. A copy of the header file from project 1 is in the include directory.
There will undoubtedly be functions and data structures that you will want to use that are not reflected in the versions of the header files that we have provided. If those functions and data structures need to be made public, then you should declare them in other header files. For turnin convenience, place your own header files in the src directory (normally, you would place them in the include directory, but turning in two directories is kind of annoying, so just leave them in src). If you add new files don't forget to edit your Makefile and/or run make depend to update dependencies.
Using your implementation of minithreads, write programs that demonstrate solutions to the following two problems. You should use the semaphores that you implemented above for synchronization. You should stress-test your solution by yielding the processor at arbitrary points within the code.
Write a solution for the bounded buffer problem. You have one producer thread and one consumer thread. The producer produces random null-terminated character strings and puts them in a buffer pool which can contain at most 10 strings. The consumer takes strings out of the pool and prints them to the screen.
Place your solution to this problem in a file named src/boundbuf.c. The makefile src/Makefile should arrange for the resulting executable to be called boundbuf.
(From OSC 4th Edition, Exercise 6.8) Consider a system with three smoker processes and one agent process. Each smoker continuously rolls a cigarette and smokes it. But to roll and smoke a cigarette, a smoker needs three ingredients: tobacco, paper, and matches. One of the smoker processes has an infinite supply of paper, another has an infinite supply of tobacco, and the third has an infinite supply of matches (don't ask me why). The agent has an infinite supply of all three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then rolls and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a program to synchronize the agent and the three smokers.
Place your solution to this problem in a file named src/cigarette.c. The makefile src/Makefile should arrange for the resulting executable to be called cigarette.
For the final part of this assignment, you will need to make your thread scheduler preemptive. You will need to use the clock interface provided in include/clock.h. This clock interface allows you to request a clock interrupt every so-many milliseconds. The clock interrupt is delivered to an interrupt handler that you specify. Before the interrupt handler is called, the currently running thread's context is stored on its stack, and the interrupt handler runs using the stack of the interrupted thread. From the standpoint of the interrupt handler, it appears as though the currently running thread simply called it synchronously. (The interrupt handling machinery active behind the scenes creates this illusion).
In order to protect critical regions of your scheduler from unwanted interrupts, you will need to explicitly enable and disable interrupts at certain points in your scheduler code. However, disabling interrupts too often is not good, and should be avoided. Note that your application programs should not directly request enablement or disablement of interrupts. They should use appropriate blocking synchronization primitives such as semaphores.
Recall that your threads will be running in a single address space. Therefore, you must also use synchronization constructs around any calls to the memory allocator, i.e., malloc and free (why is this so?). The file include/my_malloc.h prototypes wrapper routines called my_malloc and my_free. You should implement these routines in src/my_malloc.c and add them to your minithreads package. Replace all your calls to malloc and free with my_malloc and my_free (don't forget about your queue package!). If you are not religious about this, any code that (de)allocates memory will crash at random points, so be careful...
You should test your preemptive implementation initially with a simple program that has several threads in it each of which is counting upwards; ensure that the execution of these threads is interleaved.
You should then rerun the applications from part 2 of the assignment, making sure that you continue to get correct answers with your thread system (note that with preemption, execution ordering can be non-deterministic, so you may not get the same results).
You will ultimately turn in only the preemptive version of your system. Some tips on dealing with the interrupts will be posted to the section web.
Note: Since you are working with partners, only one of you should turn in the final version.
You should have created the following files for this project in the src directory:
You may add additional .h and .c files to the src directory, but do not change any files outside of the src directory! Also, please include a Makefile named src/Makefile that will enable us to build and test your code. We've included a Makefile, but you will need to modify it.
Use turnin to turn in that directory. From the project2 directory, use:
turnin -c cse451 -p project2=AA src
Where AA is your group section which will be assigned when your group directory is set up. You should make sure that we can compile and link all your programs by typing make in the src subdirectory with the original include and lib subdirectories.