CSE 511: User Level
Threads
Uthread
Package
(due in class on Oct 26)
Description
In this programming assignment, you will learn about the
workings of a threads package, and how a 2-level threads mechanism (such as the
one provided by Solaris which is taught in class) is implemented. The basic
idea behind this project is to implement a user-level threads package (similar
to what is provided by the pthreads interface) using just the kernel-aware
activities (LWPs).
The interface exported by your uthreads package should be as follows:
int uthread_init(int argc,char *argv[]);
void uthread_create(void * (*start_func)(void *),void *arg,caddr_t stack_base,
size_t stack_size,int priority, unsigned int flags,tid_t *tid);
unsigned int uthread_self();
void uthread_yield();
void uthread_mutex_init(uthread_mutex_t *)
void uthread_mutex_lock(uthread_mutex_t *)
void uthread_mutex_unlock(uthread_mutex_t *)
void uthread_cond_init(uthread_cond_t *)
void uthread_cond_wait(uthread_cond_t *, uthread_mutex_t *)
void uthread_cond_signal(uthread_cond_t *)
int is_empty(uthread_cond_t *)
void uthread_exit(void *)
All
these functions should be provided in a file called uthread.c.
**Note
that you are NOT allowed to use any of the pthread/solaris/user-level
thread interface functions and should only use the LWP mechanisms directly.
Rather you are required to implement/provide most of the pthread functionality
(we will call this the uthread package!). Failure to adhere to this
functionality will incur serious penalty.
You
are provided with a library/object file
implementing the following LWP functions. You can
click on the functions to view their man pages.
void LWP_exit();
int LWP_cond_init(LWP_cond_t *);
int LWP_cond_signal(LWP_cond_t *);
int LWP_cond_wait(LWP_cond_t *, LWP_mute
x_t *);
int LWP_cond_destroy(LWP_cond_t *
);
int LWP_sem_init(LWP_sem_t* , int );
int LWP_sem_post(LWP_sem_t* );
int LWP_sem_wait(LWP_sem_t* );
int LWP_sem_destroy(LWP_sem_t* );
int LWP_create(LWPid_t* , void* (*)
(void*) , void* );
int LWP_mutex_init(LWP_mutex_t* );
int LWP_mutex_lock(LWP_mutex_t* )
;
int LWP_mutex_unlock(LWP_mutex_t*
);
int LWP_mutex_destroy(LWP_mutex_
t* );
LWPid_t LWP_self();
You
are provided with an object file and a
header file implementing the above LWP functions.
You will need to use ONLY these LWP functions to create and manage LWPs that you
will be creating in your program. The application will take a command line
argument specifying the number of LWPs to be used. The command line argument
is passed to the uthread_init() function. The user level threads that you will
be creating in your program runs on these LWPs (which will schedule the user
level threads). So LWPs are like virtual processors for the user-level threads.
You
are supposed to include the header file, LWP.h in your program. Compile and
link your program with the executable file, LWP.o like the one done here
The
uthread_create() function creates a new thread, that should start executing the
start_func with the specified argument and priority in the stack specified by
the user. If a non NULL stack base is specified then the thread should start
executing within this stack. Note that it is left to you to start executing the
new thread immediately or schedule it in due course of time. Note that these
functions require the implementation of RUNNING, READY and BLOCKED queues (that
you have learned from CPU scheduling in your undergraduate course). The
different LWPs will manipulate the thread data structures (call them TCBs for
Thread Control Blocks) between these queues.
The
scheduling scheme to be implemented is pre-emption based with multi-level
feedback queues. The READY queue should be implemented as a multi-level
priority queue with N_PRIORITIES = 4 levels. Each lower level will have a time
quantum that is twice as long as the immediately higher level. A thread could
relinquish the LWP either by expiration of a time quantum (that you would need
to implement using signal handlers), or voluntarily using uthread_yield()
calls, or when it blocks. Since multiple LWPs can be manipulating the shared
queues, it is important to guard these accesses with locks (you have to use LWP
locking mechanisms, not those for user-level threads!).
There
will be a test/application package made available to you. This will include
app.c which contains calls to your interface. We may surprise you with a
different application (test program) during the demo and your routines should
still work. It will thus be a good exercise for you to test your code with
several other programs for robustness.
Please
stay tuned constantly to the web site for the exact and latest interface
functions you need to implement, their arguments, test programs, examples,
documentation/manuals and announcements
The web page supercedes any other information that may be given to you.
The
project reports are due in class on the designated day (no extensions will be
given) and the programs should be turned in before class starts on that day
using the turn-in procedure. You need to set up an appointment to
demonstrate your implementation. You can work in teams (at most 2 per team) for
the project. You are free to choose your partner but if either of you choose to
drop out of your team for any reason at any time, each of you will be
individually responsible for implementing and demonstrating the entire project
and writing the project report by the designated deadline. If you have
difficulty finding a partner, let me know at the earliest.
Even though you will
work in pairs, each of you should be fully familiar with the entire code and be
prepared to answer a range of questions related to the entire project. It will
be a good idea to work together at least during the initial design of the code.
You should also ensure that there is a fair division of labor between the
members. Also, give a detailed description of your implementation justifying
any reasonable assumptions you may have made.