CSE 451
Spring, 1998
Assignment Handed Out: 4/24/98 (Wednesday)
Assignment Due Date:
-
Part 1 and Part 2: 5/5/98 (Tuesday) at midnight (at or before 11:59
PM)
-
Part 3 : 5/11/98 (Monday) at Midnight (at or before 11:59 PM)
This assignment has three parts and they are due on the dates given
above. Since the assignment contains some Alpha-specific assembly code,
you can only work on the assignment on Alpha systems running DIGITAL Unix
(ie, orcas or sanjuan); 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
more than two weeks to do the assignment, which should give you plenty
of time, but we recommend that you start right away.
As mentioned in lecture, you will be working with a partner for this
assignment. If you haven't already, one of you should send mail to the
TA listing the name of your
partner; or send me mail saying you have no preferences and the TA can
assign you to a group randomly. This will allow us to set up work directories
and groups. You should not wait until you have met with your partners to
start reviewing the code and instructions for this assignment.
This assignment is broken down into three parts, the second and third
of which rely on the first.
-
First, you will implement your own thread management system called minithreads
in which you will be able to explore what we've been discussing in class
about how non-preemptive thread systems work.
-
In the second part of the assignment, you will write two test applications
that demonstrate some classical problems in concurrent programming, as
well as stress your thread system.
-
In the third part of the assignment, you will add preemption to your threads
package.
The Threads Package
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 OS provide a similar service. Here's
(conceptually) how minithreads will work:
-
UNIX gives each process a single thread in a single address space. We want
to treat that single UNIX thread as a VIRTUAL PROCESSOR, with which we
can schedule multiple threads from the same address space. Each thread
represents an independent execution context (private registers, stack,
some private scheduling state). The single thread provided by the UNIX
operating system is time-multiplexed (by you) across the many minithreads
within one address space.
-
In other words, you deal with the VIRTUAL PROCESSOR given to you by UNIX
as UNIX treats the PHYSICAL PROCESSOR on which it runs.
In some ways, what we're building in this assignment 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:
-
Debuggability. It's a lot easier to develop and debug programs in
user space than it is in the kernel; if you make a mistake, you can fall
into the debugger and figure out what happened. (Ask yourselves, fundamentally,
why is it easier to develop user-level code than kernel code).
-
Cost. If everyone was working on their own kernel, then everyone
would need their own computer, and we would need 40+ computers for this
class.
-
Simplicity. An operating system such as UNIX already provides many
auxiliary services that you need for an assignment like this. These services
include memory management, a file system, etc. In this assignment, we will
be relying on these UNIX services. As the quarter progresses, though, we
will be writing our own versions of some of these services.
Getting Started...
Everything you need to start in in minithreads.tar
Download the file and use the following command to extract the files.
tar xvf minithreads.tar
This will extract all the files into the directory minithreads
in the current directory. You could extract the files into the group
work directory. (or personal directory if you want your own copy or want
to start working while we get the group directories up).
You could also download the individual files from the minithreads directory.
Part 1: Non-Preemptive Threads
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.
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.
Part 2: Applications
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.
Bounded Buffer
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.
The Cigarette-Smoker's Problem
(From OSC 5th 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.
Part 3: Preemption
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.
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. Also, I am planning
to maintain an assignment
FAQ with answers to questions you ask by email.
What you should turn in
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 assignment in the
src directory:
-
README
-
A file that describes what is here, who was in your group, their e-mail
addresses, and anything special we need to know.
-
minithread.c
-
Implementation of the minithread.h interface.
-
synch.c
-
Implementation of the synch.h interface.
-
my_malloc.c
-
Implementation of the my_malloc.h interface.
-
boundbuf.c
-
Your solution to the bounded buffer problem. The resulting executable should
be called boundbuf.
-
cigarette.c
-
Your solution to the cigarette smoker's problem. The resulting executable
should be called cigarette.
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 minithreads
directory, use:
turnin -c cse451 -p minithreads 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.