User-level Threads

The goal of this exercise is to design and implement an user-level thread package. Threads created by this package are not visible to the underlying OS, so the scheduler itself must run within the user process.

API

The user-level thread package must implement, at least, the following interface:

int init(void)
Initializes the user-level thread manager, registering the calling process as the first thread. This function must be called before any other in the package and returns "0" in case of success and "-1" in case of failure.
int create(void (* entry)(int), int arg)
Creates a thread with entry point set to entry, which is a pointer to a plain function taking an integer as argument. The function returns an identifier for the created thread in case of success and "-1" in case of failure.
int join(int tid, int * status)
Waits for the thread identified by tid to exit, returning it's return value in status. In case of success, this function returns "0", otherwise, "-1".
void exit(int status)
Immediately terminates the execution of the calling thread, allowing for a return value to be eventually handed over to join.
void yield(void)
Causes the calling thread to release the CPU, thus activating the scheduler.
int getid(void)
Returns the identifier of the calling thread.

API usage example

Scheduler

The user-level thread package must feature a thread scheduler implementing a police of choice plus a back-end mechanism enforcing a round-robin police with a quantum of 100 milliseconds. For example, if static priorities are chosen as the main police, then the thread creation primitive must be extended to feature a priority and threads are scheduled based on that value. Nevertheless, after a quantum, the scheduler must be activated to validate the current selection, thus enforcing round-robin for same-priority threads.

Implementation based on POSIX

In theory, any POSIX.1 compliant system should deliver the basic functionality needed to implement the proposed thread package at user-level. The key issues, i.e., context switching and timing can be implemented based on LIBC functions setjmp and longjmp and on the system calls setitimer and signal.

Context Switch

setjmp saves the stack context/environment. longjmp can restore the stack context/environment later. In this way, longjmp "returns" to the state of the program when setjmp was called. The return value from setjmp indicates whether control reached that point normally (returns 0) or from a call to longjmp (returns a value other than 0).

Example:


	if(setjmp(old_context) == 0) 
		longjmp(new_context, 1); 

	else 
		return;

The setjmp and longjmp are very usefull when the context you want to save is already in execution (i.e. all context structures pre-exists), and therefore implementations of exception and events handling usually rely on such constructs. However, when a new context must be created, several structures must be initialized and manipulated inside the context buffer (e.g. set stack pointer to the new stack of the new thread). Setjmp and longjmp functions doesn't provide a good interface for such manipulation, since you have to adjust the bytes in context hand, breaking the portability of your code, since every architeture will organize the data inside context differently.

For that reason, new functions for context manipulation was defined by POSIX1.2001 (e.g. setcontext, getcontext, makecontext and swapcontext). These functions are available on recent versions of the Standard C library. Remeber, man command is your friend.

More information about those functions could be found in http://en.wikipedia.org/wiki/Setcontext.

You can also download and look on example of using these functions here.

Scheduler Timed Activation

It is necessary to activate the scheduler in specific times (QUANTUM). In this case, setitimer sets value of an interval timer (QUANTUM) which the SIGALRM signal will be generated. In addition, it is possible to install a new signal handler ("scheduler") for the signal SIGALRM through of the function signal.

Example:


	struct itimerval time; 



	time.it_interval.tv_sec =  0; 

	time.it_interval.tv_usec = 100000; 

	time.it_value.tv_sec =  0; 

	time.it_value.tv_usec = 100000; 



	signal(SIGVTALRM, scheduler); 
 


	setitimer(ITIMER_VIRTUAL, &time, NULL);

Download source code

More informations on UNIX man pages.