CSE 451
Winter, 1999
Assignment Handed Out: 1/22/99 (Friday)
Assignment Due Date:
-
Part 1 and Part 2: 2/2/99 (Tuesday) at midnight (at or before 11:59
PM)
-
Part 3 : 2/8/99 (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). Instructions for submission will be supplied
by the time you need them.
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. These groups are listed on the group page; your group will be given a
directory in which you both (and only you) have permissions, to aid in
shared development. These should be available on Monday, depending on
how long it takes support to set it up. You should not wait until you
have met with your partner or until your directory is ready 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.