Design of an user level thread package
- Read from the OS books the sections that deal with: CPU scheduling,
threads, FIFO, FCFS, critical sections. Read Stevens for IPC.
- demo.c. Try it. This C code gives an example
of context switching (user-level) and round-robin scheduling
of two processes. Read the necessary man pages and figure out
how it works.
Build your own scheduler and threads package
In addition, implement the following two functions:
- Implement a round-robin pre-emptive scheduler and context
switching. You may use the hack of demo.c.
Design data structures for thread entities.
Implement the following functions:
- int CreateThread(void (*f)(void)) - this function creates a
new thread with f() being its entry point. The function
returns the created thread id (>= 0) or (-1) to
indicate failure. It is assumed that f() never returns.
A thread can create other threads! The created thread is
appended to the end of the ready list (state = READY). Thread ids are
consecutive and unique, starting with 0.
- void Go() - This function is called by the main process to start
the scheduling of threads. It is assumed that at least one thread is
created before Go() is called. This function is called exactly
once and it never returns.
- int GetMyId() - This function is called within a running
function returns the thread id of the calling thread.
- int DeleteThread(int thread_id) - deletes a thread. The function
returns 0 if successful and -1 otherwise. A thread can delete itself,
in which case the function doesn't return.
- void Dispatch(int sig) - the thread scheduler. This function
by the interval clock interrupt and it schedules threads using
FIFO order. It is assumed that at least one thread exists all the
time - therefore there is a stack in any time. It is not assumed
that the thread is in ready state.
- void YieldCPU() - this function is called by the running thread.
The function transfers control to the next thread. The next thread
will have a complete time quantum to run.
- int SuspendThread(int thread_id) - this function suspends a thread
until the thread is resumed. The calling thread can suspend itself, in
which case the thread will YieldCPU as well. The function returns
id on success and -1 otherwise. Suspending a suspended thread has
no effect and is not considered an error. Suspend time is not
considered waiting time.
- int ResumeThread(int thread_id) resumes a suspended process. The
process is resumed by appending it to the end of the ready list.
Returns id on success and -1 on failure. Resuming a ready
process has no effect and is not considered an error.
- int GetStatus(int thread_id, status *stat) - this call fills the
status structure with thread data. Returns id on
success and -1 on failure.
- void SleepThread(int sec) - the calling process will sleep until
(current-time + sec). The sleeping time is not considered wait
- void CleanUp() - shuts down scheduling, prints the
following statistics, deletes all threads and exits the program.
- int CreateThreadWithArgs(void *(*f)(void *), void *arg)
f is a ptr to a function which takes (void *) and
returns (void *). Unlike the threads so far, this thread takes
arguments, and instead of uselessly looping forever, returns a
value in a (void *). This function returns the id of the thread
- void *GetThreadResult(int tid)
waits till a thread created with the above function returns, and
returns the return value of that thread. tid is the id of
thread. This function, obviously, waits until that thread is done with.
- The C calling convention says that params are pushed on the stack. So,
to pass an argument to the function, put the argument (the void ptr)
at the top 4 bytes of the stack (make sure it's in little endian
order!), and then decrement the stack ptr.
- Where does a function (thread) return to? To the return address.
Where is the return address? On the stack (surprise!). It
comes after the params. So after pushing the param, push the
return address, and again decrement the stack ptr by 4.
- But where to return to? To a procedure which does some wrapping up,
like setting the state of the thread to FINISHED,
so that the dispatcher doesn't try to schedule it again, and storing
the return value somewhere.
- Finally, where is the return value. On Intel machines, at least,
it's returned in the eax register. That's part of the C
calling convention : return values are in eax. So all you have to
do is get the contents of eax. There are two ways to do that:
- inline assembly
- Write a three line assembly routine, and call it like any normal
function from your program:
------ geteax.asm -----
geteax : ret
------ end of geteax.asm ----
To call this, declare a prototype in your C program :
extern void * geteax();
and then link in geteax.o like any other normal program.
- GetThreadResult will have to wait till the thread is over. Use semaphores.
- Total number of thread that were created.
- Total number of thread that were deleted.
- Number of threads at shutdown time (Do not use (1) - (2) !! why?)
- Elapsed time between Go() and CleanUp() in msec.
- For each of the still exiisting threads:
- thread id.
- state (running, ready, sleeping, suspended).
- number of bursts (none if the thread never ran).
- total execution time in msec(N/A if thread never ran).
- total requested sleeping time in msec (N/A if thread never slept).
- average execution time quantum in msec (N/A if thread never ran).
- average waiting time (status = READY) (N/A if thread never ran).
Constant test values:
MAX_NO_OF THREADS 100 /* in any state */
Subhashis Banerjee / Dept. Computer Science and Engineering / IIT Delhi /
Hauz Khas/ New Delhi 110016 / firstname.lastname@example.org