MP2 – Thread library : Due February 22nd before class
Announcement
(2/15/2009) Eighteen test
cases, a brief summary of the test case (README-testcases.txt), and Makefile have
been uploaded on csil-vmserv1: /home/class/sp10/cs423/mp2
(2/12/2009) thread.h has
been changed: added another parameter (unsigned int priority) to
thread_libinit() to specify the priority of the first (main) thread.
Overview
In this
project, you will implement your own thread library that helps you understand
how threads and synchronization mechanisms are implemented to provide
concurrency in a user program.
`
Thread library interfaces
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.
int
thread_libinit(thread_startfunc_t func, void *arg, unsigned int priority = 0)
thread_libinit
initializes the thread library. A user program should call thread_libinit
exactly once (before calling any other thread functions). 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. Priority specifies
the priority of the thread (0 is the highest priority and 0xffffffff is the
lowest priority).
Note that a
successful call to thread_libinit will not return to the calling function.
Instead, control transfers to func, and the function that calls thread_libinit
will never execute again.
int
thread_set_sched_policy(int schedule_policy)
thread_scheduler
changes the thread schedule policy. The thread scheduler supports two types of
schedule policies. First, it supports FIFO schedule (THR_SCHED_FIFO) that
simply queues threads in the order that they arrive in the ready queue. Second,
it supports priority scheduling (THR_SCHED_PRIORITY) that assigns a fixed
priority rank to every thread and the scheduler arranges the threads in the
ready queue in order of their priority. See section [Scheduling order] below
for further details. The default is FIFO schedule.
int
thread_create(thread_startfunc_t func, void *arg, unsigned int priority = 0)
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.
Priority specifies the priority of this thread (0 is the highest priority and
0xffffffff is the lowest priority).
int thread_yield(void)
thread_yield
causes the current thread to yield the CPU to the next runnable thread. It has
no effect if there are no other runnable threads. thread_yield is used to test
the thread library. A normal concurrent program should not depend on thread_yield;
nor should a normal concurrent program produce incorrect answers if
thread_yield calls are inserted arbitrarily.
int
thread_lock_policy(bool dfree)
thread_lock_policy
specifies lock semantics. If dfree is true, the thread library never allows
deadlock. You should implement thread_lock and thread_unlock (see below) such
that there are no deadlocks. For example, with the deadlock free semantics,
when thread_lock() detects a possible deadlock, it should return an error, -1.
If dfree is false, there is no such restriction and a deadlock can happen. The
default is dfree=false.
int
thread_initlock(unsigned int lock)
int
thread_lock(unsigned int lock)
int thread_unlock(unsigned int lock)
thread_initlock,
thread_lock and thread_unlock implement locks in your thread library. A lock is
identified by an unsigned integer (0 - 0xffffffff), chosen by the programmer.
Programs can use arbitrary numbers for locks (and they need not be numbered
consecutively).
Each of these
functions returns -1 on failure. Each of these functions returns 0 on success,
except for thread_libinit, which does not return at all on success.
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.
-------------------------------------------------------------------------------
/*
* 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
#define
STACK_SIZE 262144 /* size of each thread's stack */
#define
THR_SCHED_FIFO 0
#define
THR_SCHED_PRIORITY 1
typedef void
(*thread_startfunc_t) (void *);
extern int
thread_libinit(thread_startfunc_t func, void *arg, unsigned int priority = 0);
extern int
thread_set_sched_policy(int sched_policy);
extern int thread_create(thread_startfunc_t func, void *arg, unsigned int
priority = 0);
extern int thread_yield(void);
extern int
thread_lock_policy(bool dfree);
extern int
thread_initlock(unsigned int lock);
extern int thread_lock(unsigned int lock);
extern int thread_unlock(unsigned int lock);
/*
* start_preemptions() can be used in
testing to configure the generation
* of interrupts (which in turn lead to
preemptions).
*
* It generate asynchronous preemptions
every 10 ms using
*
SIGALRM. These are
non-deterministic.
*
* 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.
*/
extern void
start_preemptions(void);
#endif /*
_THREAD_H */
-------------------------------------------------------------------------------
start_preemptions()
is part of the interrupt library we provide, 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().
Creating and swapping
threads
You will be
implementing your thread library on x86 PCs running the Linux operating system.
Linux 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.h>
/*
* Initialize a context structure by copying the current thread's context.
*/
getcontext(ucontext_ptr); // ucontext_ptr has type (ucontext_t *)
/*
* Direct the new thread to use a different stack. Your thread library
* should allocate STACK_SIZE bytes for each thread's stack.
*/
char *stack = new char [STACK_SIZE];
ucontext_ptr->uc_stack.ss_sp = stack;
ucontext_ptr->uc_stack.ss_size = STACK_SIZE;
ucontext_ptr->uc_stack.ss_flags = 0;
ucontext_ptr->uc_link = NULL;
/*
* Direct the new thread to start by calling start(arg1, arg2).
*/
makecontext(ucontext_ptr, (void (*)()) start, 2, arg1, arg2);
-------------------------------------------------------------------------------
Use swapcontext
to save the context of the current thread and switch to the context of another
thread. Read the Linux manual pages for more details.
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);
-------------------------------------------------------------------------------
Interrupts and 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.cc) 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.
Scheduling order
This section
describes the specific scheduling order that your thread library should follow.
Remember that a correct concurrent program must work for all thread
interleavings, so your scheduler must work independent of this scheduling
order.
All scheduling
queues should be following the scheduling policy set by thread_sched_policy.
This includes the ready queue and the queue of threads waiting for a lock.
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 necessarily 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 necessarily executed right away.
Error handling
Operating
system code should be robust. There are three sources of errors that OS code
should handle. The first and most common source of errors come from misbehaving
user programs. Your thread library must detect when a user program misuses
thread functions (e.g., calling another thread function before thread_libinit,
calling thread_libinit more than once, misusing locks (e.g., using
uninitialized ones, trying to acquire a lock that a thread already has or
release a lock it doesn't have, etc.). A second source of error comes from
resources that the OS uses, such as hardware devices. Your thread library must detect
if one of the lower-level functions it calls returns an error (e.g., C++'s new
operator throws an exception because the system is out of memory). For these
first two sources of errors, the thread function should detect the error and
return -1 to the user program (it should not print any error messages). User
programs can then detect the error and retry or exit.
A third source
of error is when the OS code itself (in this case, your thread library) has a
bug. During development (which includes this entire semester), the best
behavior in this case is for the OS to detect the bug quickly and assert (this
is called a "panic" in kernel parlance). You should use assertion
statements copiously in your thread library to check for bugs in your code.
These error checks are essential in debugging concurrent programs, because they
help flag error conditions early.
We will not
provide you with an exhaustive list of errors that you should catch. OS
programmers must have a healthy sense of paranoia to make their system robust,
so part of this assignment is thinking of and handling lots of errors.
Unfortunately, there will be some errors that are not possible to handle,
because the thread library shares the address space with the user program and
can thus be corrupted by the user program.
There are
certain behaviors that are arguably errors or not. Here is a list of
questionable behaviors that should NOT be considered errors; deadlock (however,
trying to acquire a lock by a thread that already has the lock IS an error); a
thread that exits while still holding a lock (the thread should keep the lock).
Ask on the newsgroup if you're unsure whether you should consider a certain
behavior an error.
Do not use
ucontext structs that are created by copying another ucontext struct. Instead,
create ucontext structs through getcontext/makecontext, and manage them by
passing or storing pointers to ucontext structs, or by passing/storing pointers
to structs that contain a ucontext struct (or by passing/storing pointers to
structs that contain a pointer to a ucontext struct, but this is overkill).
That way the original ucontext struct need never be copied.
Why is it a bad
idea to copy a ucontext struct? The answer is that you don't know what's in a
ucontext struct. Byte-for-byte copying (e.g., using memcpy) can lead to errors
unless you know what's in the struct you're copying. In the case of a ucontext
struct, it happens to contain a pointer to itself (viz. to one of its data
members). If you copy a ucontext using memcpy, you will copy the value of this
pointer, and the NEW copy will point to the OLD copy's data member. If you
later deallocate the old copy (e.g., if it was a local variable), then the new
copy will point to garbage. Copying structs is
also a bad idea for performance (the ucontext struct is 348 bytes on
Linux/x86).
Unfortunately,
it is rather easy to accidentally copy ucontext structs. Some of the common
ways are: passing a ucontext by value into a function copying the ucontext
struct into an STL queue declaring a local ucontext variable is almost always a
bad idea, since it practically forces you to copy it
You should
probably be using "new" to allocate ucontext structs (or the struct
containing a ucontext struct). If you use STL to allocate a ucontext struct,
make sure that STL class doesn't move its objects around in memory. E.g., using
vector to allocate ucontext structs is a bad idea, because vectors will move
memory around when they resize.
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 <iostream>
#include "thread.h"
#include <assert.h>
using namespace
std;
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;
if (thread_yield()) {
cout << "thread_yield failed\n";
exit(1);
}
}
}
void
parent(void *a)
{
int arg;
arg = (int) a;
cout <<
"parent called with arg " << arg << endl;
if (thread_create((thread_startfunc_t) loop, (void *) "child
thread")) {
cout << "thread_create failed\n";
exit(1);
}
loop( (void *)
"parent thread");
}
int
main()
{
if (thread_libinit( (thread_startfunc_t) parent, (void *) 100)) {
cout << "thread_libinit failed\n";
exit(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.
-------------------------------------------------------------------------------
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 lock library 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. Finally, implement deadlock prevention or avoidance.
An integral
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.
But to help you
implement and debug your thread library, we will provide several test cases
(will be available on Feb. 15). Each test case will be a short C++ program that
uses functions in the thread library (e.g. the example program listed above.
Each test case runs without any arguments. Test cases exit(0) when run with a
correct thread library (normally this will happen when your test case's last
runnable thread ends or blocks). Your thread library will be graded based on
the result of running similar test cases.
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.
Write your
thread library and scheduler in C++ on Linux. The public functions in thread.h
are declared "extern", but all other functions and global variables
in your thread library should be declared "static" to prevent naming
conflicts with programs that link with your thread library.
Compile an
application program (app.cc) with a thread library (thread.cc) and interrupt
library (interrupt.cc) as follows:
>>g++
-m32 thread.cc interrupt.cc app.cc
Use g++
(/usr/bin/g++) to compile your programs. You may use any functions included in
the standard C++ library, including (and especially) the STL. You should not
use any libraries other than the standard C++ library.
Your thread
library must be in a single file and must be named "thread.cc".
A copy of
thread.h, interrupt.h and interrupt.cc can be found in
/home/class/sp10/cs423/mp2 on csil-vmserv1
NOTE: You need to use -m32 in Makefile for
all files to compile.
-m32 option tells the compiler to generate 32bit code. Because this mp is
originally designed in 32 bit machines, we are using "-m32" switch
when compiling the code. If you don't use this switch, the compiler will
complain about some incompatibility. For example, void* type is 64bit (to
address 64bit address space) while int type is 32bit (I think long type is 64
bit but not sure).
Deliverables / Grading
We need the
following files:
1.
thread.cc,
C source code for implementing your thread library
2.
README,
described below
Writing a README file
Create a text
file that briefly describes how your thread library APIs are implemented. If
there are any known bugs in your implementation that you were unable to fix, or
you could not fully complete the assignment, please describe what does and
doesn't work correctly in this file as well.
This file
should include, at the very top, the names and NetIDs of all group members.
Submitting your work
1.
Copy
the files you wish to hand in to a directory named cs423-mp2-<groupid>,
replacing <groupid> by the net id of one of your group members followed
by the group size. An example <groupid> for a group with 3 members:
jinheo3. You will use this group id throughout the semester.
2.
Tar
and gzip the files (tar zcf cs423-mp2-<groupid>.tar.gz
cs423-mp2-<groupid>).
3.
Send
an email with the gzipped file to the TA. The subject line should include
"CS423 SP10 MP2"
4.
You
can resubmit your work anytime before the deadline.