Project #2: User Mode Thread Library Solution

This project1 will give you experience with threads and synchronization. You will produce a library that can be used by applications|much like the pthreads API|to create and manage threads in user mode. Your library will provide programmers with mutex locks and condition variables for use in synchronizing data access.

• Thread Management API

Your threading library will implement the API shown in Listing 1. This API will be de ned in a le called mythreads.h (I will put the header le in the git repository). You should use this header le, as is. Do not change it, or we may not be able to test your program. This API should look familiar as it is similar to the pthreads API that we have used in class (ours is just simpler). The expected functionality of each call is described below:

threadInit|Applications will call threadInit to initialize your library. You can safely assume that this will be the rst call into your library that any application will make. This would be a good place to initialize any data structures.

threadCreate|Applications will call threadCreate to create new threads. When an application calls this function, a new thread should be created. The new thread should have a stack of size STACK SIZE and should execute the speci ed function with the argument (void *) that was passed to threadCreate. If suc-cessful, this function should return an int that uniquely identi es the new thread, and will be used in calls to the threadJoin func-tion. The newly created thread should be run immediately after it is created (before threadCreate returns).

• This project is used with permission by Dr. Jacob Sorber

1

CPSC/ECE 3220: Operating Systems

Listing 1: mythreads.h|the API for your threading library

• define S T A C K _ S I Z E (1 6* 10 24 )

• define NU M_ LO CK S 10

• define C O N D I T I O N S _ P E R _ L O C K 10

◦ the type of function used to run your threads typedef void *(* th Fu nc Pt r ) ( void *) ;

extern void t h r e a d I n i t () ;

// thread m a n a g e m e n t fu nc ti on s

extern i n t t h r e a d C r e a t e ( th Fu nc Pt r funcPtr , void * argPtr ) ;

extern void t h r e a d Y i e l d () ;

extern void t h r e a d J o i n ( i n t thread_id , void ** result ) ; extern void t h r e a d E x i t ( void * result ) ;

// s y n c h r o n i z a t i o n fu nc ti on s

extern void t h r e a d L o c k ( i n t lockNum ) ; extern void t h r e a d U n l o c k ( i n t lockNum ) ;

extern void t h r e a d W a i t ( i n t lockNum , i n t c o n d i t i o n N u m ) ; extern void t h r e a d S i g n a l ( i n t lockNum , i n t c o n d i t i o n N u m

◦ ;

• control at om ic it y

extern i n t i n t e r r u p t s A r e D i s a b l e d ;

threadYield|Calls to threadYield cause the currently running thread to \yield" the processor to the next runnable thread. Your threading library will save the current thread’s context and select the next thread for execution. The call to threadYield will not return until the thread that called it is selected again to run. We will also call this function in order to preempt your threads during testing.

threadJoin|This function waits until the thread corresponding to id exits (either through a call to threadExit or by returning from the thread function). If the result argument is not NULL, then the thread function’s return value (or the return value passed to threadExit) is stored at the address pointed to by result. Otherwise, the thread’s return value is ignored. If the thread speci ed by id has either already exited, or does not exist, then the call should return immediately. You should store the results of all exited threads, so that you can retrieve their results. For this assignment, you do not need to ever free the results.

2

CPSC/ECE 3220: Operating Systems

threadExit|This function causes the current thread to exit. Calling this function in the main thread will cause the process to exit. The argument passed to threadExit is the thread’s return value (equivalent to returning the same value from the thread function), which should be passed to any calls to threadJoin by other threads waiting on this thread.

• Synchronization

Your library will also give programmers tools so they can synchronize their threads and protect shared data accesses. Speci cally, your li-brary will provide mutex locks and condition variables. For simplicity, the number of locks and the number of condition variables per lock provided by your library is statically de ned by the NUM LOCKS and CONDITIONS PER LOCK preprocessor macros. Each condition variable is associate with a single lock. All locks should initially be in the unlocked state. Note: these values may be di erent during testing, so you should always use the names (e.g., NUM LOCKS) instead of the value (e.g., 10) in your code.

The synchronization API functions are described below:

threadLock|This function blocks (waits) until it is able to ac-quire the speci ed lock. Your library should allow other threads to continue to execute concurrently while one or more threads are waiting for locks. Note that the parameter passed to the function indicates which lock is to be locked. This parameter is not the lock itself.

threadUnlock|This function unlocks the speci ed lock. As with threadLock, the parameter passed is not the lock, but rather indicates the number of the lock that should be unlocked. Trying to unlock an already unlocked lock should have no e ect.

threadWait|This function atomically unlocks the speci ed mu-tex lock and causes the current thread to block (wait) until the speci ed condition is signaled (by a call to threadSignal). The waiting thread unblocks only after another thread calls threadSignal with the same lock and condition variable. The mutex must be locked before calling this function, otherwise the behavior is un-de ned (your library should exit the process, if this occurs, and

3

CPSC/ECE 3220: Operating Systems

print out an error message). Before threadWait returns to the calling function, it re-acquires the lock.

threadSignal|This function unblocks a single thread waiting on the speci ed condition variable. If no threads are waiting on the condition variable, the call has no e ect.

You should not do any deadlock detection. If a thread calls threadLock()

on a lock that it already holds, it should deadlock.

• Preemption

When we test your threading library, control can pass from one thread to the next in one of two ways: 1) the current thread calls threadYield and gives up the processor willingly, or 2) the current thread is forced to yield the processor. In testing we will periodically force your threads to yield by calling threadYield when a timer res (we will use setitimer to generate interrupts). This means that, just like hardware inter-rupts, threadYield can be called at anytime (including during a call to threadYield), which requires careful handling.

You are not allowed to use pthread locks, any other pthreads function, or any other locks to provide synchronization. Instead your library can make operations atomic by temporarily disabling \interrupts" through the interruptsAreDisabled variable that is also declared in Listing 1. Setting this variable equal to 1 will disable interrupts and prevent the current running code from being interrupted. Setting this variable back to 0 will enable interrupts. Interrupts should only ever be disabled when executing in one of your library’s functions. When the user’s code is running, interrupts must be enabled. I recommend using the two functions shown in Listing 2 to enable and disable interrupts. They are simple wrappers, but the assertions will likely help provide some sanity checking, and help you debug issues.

• How to compile your library?

After the last project, you have some experience writing a library, but this time your library will be a static library (called "libmythreads.a"), meaning that programs will link to it when they are compiled, and the library will become part of the compiled program. To compile a static

4

CPSC/ECE 3220: Operating Systems

Listing 2: Methods for enabling/disabling of interrupts.

s t a t i c void i n t e r r u p t D i s a b l e () {

assert (! i n t e r r u p t s A r e D i s a b l e d ) ;

i n t e r r u p t s A r e D i s a b l e d = 1;

}

s t a t i c void i n t e r r u p t E n a b l e () {

assert ( i n t e r r u p t s A r e D i s a b l e d ) ;

i n t e r r u p t s A r e D i s a b l e d = 0;

}

library from a set of source les (say, a.c and b.c), you will do the following:

$ gcc -Wall -c a.c b.c

$ ar -cvr libmythreads.a a.o b.o

You can have more source les, and you can, of course, name them whatever you want; however, it is important that your library is named libmythreads.a. Also, keep in mind that if a libmythreads.a already exists, ar will update that le, replacing the les that you speci ed. It will not recreate the library from scratch. This has caused confusion in the past, and I recommend deleting the old library and recreating it rather than updating it, each time.

When we test your library we will link our test programs with your library. If I wanted to compile a test, implemented in threadtest1.c, then we will compile it like so:

$ gcc -o executable name threadtest1.c libmythreads.a

Your library needs to be written in C, and you will need to provide a Make le that compiles your library. The example above used gcc, but you’re welcome to use clang as well.

• How to implement threads?

Your library will implement threads using the getcontext, makecontext, and swapcontext functions. These functions allow you to get the cur-rent execution context, make new execution contexts, and swap the currently-running context with one that was stored.

So, what is a context? Hopefully, you remember when we talked about context switches|when one process (or thread) is interrupted and con-

5

CPSC/ECE 3220: Operating Systems

trol is given to another. It’s called a context switch because you are changing the current execution context (the registers, the stack, and program counter) for another. We could do this from scratch, using inline assembly, but the getcontext, makecontext, andswapcontext functions make it much simpler.

For example, when getcontext is called, it saves the current execution context in a struct of type ucontext t. The man page for getcontext describes the elements of this struct. Some of these elements are ma-chine dependent and you don’t have to worry about the majority of them. They may include the current state of CPU registers, a signal mask that de nes which signals should be responded to, and of course, the call stack. The call stack is the one element of this struct that you will need to pay some attention to.

The steps for creating a new thread is shown in Listing 3. The current context must be saved rst using getcontext (the new thread’s context is based on the saved context). Space for a new stack must be allocated, and the size recorded. Finally, makecontext modi es the saved context, so that when it is activated, it will call a speci c function, with the speci ed arguments. The newly created context is then activated with either a call to setcontext or swapcontext, as shown in Listing 4. The former (setcontext) replaces the current context with a stored context. When successful, a call to setcontext does not return (it begins running in the new context). A call to swapcontext is similar to setcontext, except that it saves the context that was running (a useful thing to do, if you want to resume the old context later). A successful call to swapcontext also does not return immediately, but it may return later, when the thread that was saved is swapped back in.

Be sure to read the man pages for these functions thoroughly. Also, note that the example shown in Listing 3 stores the new context on the stack. You probably want to store your thread contexts on the heap.

For each thread you create, your library should assign that thread to a unique identi er (the number returned by threadCreate), in addition to its context. Thread IDs must be unique during the life of each thread; however, you may reuse a thread’s ID, if you want, after that thread completes and is deallocated. Recording additional information about the thread may be helpful, but is not necessarily required. You will probably also want some sort of data structure to keep track of the threads in the system, so when threadYield is called, you can e ciently nd the next thread to activate.

One last hint: Students often wonder how they should tell when a

6

CPSC/ECE 3220: Operating Systems

Listing 3: Creating a new execution context.

u c o n t e x t _ t n e w c o n t e x t ;

g e t c o n t e x t (& n e w c o n t e x t ) ; // save the current context

// allocate and i n i t i a l i z e a new call stack

n e w c o n t e x t . uc_stack . ss_sp = malloc ( S T A C K _ S I Z E ) ; n e w c o n t e x t . uc_stack . ss_size = S T A C K _ S I Z E ; n e w c o n t e x t . uc_stack . ss_flags = 0;

// modify the context , so that when ac ti va te d

// func will be called with the 3 arguments , x, y, and

z

• in your code , func will be replaced by whatever function you want

• to run in your new thread .

m a k e c o n t e x t (& newcontext ,

( void (*) ( void ) ) func , 3 , x , y , z ) ;

thread completes. One way to handle this is by using the uc link eld in the context (see the man page for makecontext). This is the hard way, and I do not recommend it. Instead, think about how you would determine when a function in a sequential program is nished. Hint: the function you pass to makecontext doesn’t have to be the user’s thread function|and your job will be easier, if it’s not.

Other thoughts, hints, and warnings

Your program should be written in C or C++ and use good program-ming style. It should be -Wall clean2, and most importantly it should be your own. Your library will be tested against a variety of programs that create threads, join threads, and use locks and condition variables. You should write a variety of test programs to test your library.

Make sure that your code compiles, runs and has been thoroughly tested on the lab machines. Resist the urge to get fancy. Create a simple implementation that works (meaning you have tested it thoroughly), rst.

Remember that your main thread is a bit of a special case. You need to keep track of it, so that you can schedule it along with the rest of the

2\-Wall clean" = If compiled with the -Wall ag, it should not produce any warnings.

7

CPSC/ECE 3220: Operating Systems

Listing 4: Swapping two contexts.

// points to

a saved context

so me wh er e

in

memory

u c o n t e x t _ t

* s a v e d c o n t e x t ;

// points to

the place in memory

where

u c o n t e x t _ t

* w h e r e _ t o _ s a v e _ c u r r e n t l y _ r u n n i n g _ c o n t e x t ;

// save

the

running context ,

and

give

the

saved context

the

CPU

s w a p c o n t e x t ( w h e r e _ t o _ s a v e _ c u r r e n t l y _ r u n n i n g _ c o n t e x t , saved context ) ;

• note that s w a p c o n t e x t () will not return until the initial context is swapped back .

threads, however you don’t need to allocate a stack for it (it already has a stack). You just need to save its context.

Keep in mind that freeing a thread’s resources when it’s nished re-quires some care. Normally, when a thread completes, you need to deallocate (free) the nished thread’s stack and any other memory you allocated for it. The trick is that the exiting thread can’t free its own stack safely. Another thread will need to free its resources after it is nished. Also, you can’t (and shouldn’t try) to free the main thread’s resources. It’s stack is not allocated on the heap, and so trying this will not end well.

Submission Instructions

This project is due by 5:00 PM on October 12th. Absolutely no late assignments will be accepted, and deadline extensions typically require a natural disaster (more than the u, a broken-down car, a midterm exam, or a little ice and snow).

When your project is complete, archive your source materials, using the following command:

$ tar cvzf project2.tgz README Makefile <list of source files>

The Make le should build your library (by running make). It should produce a single le (libmythreads.a).

The README le should include your name, a short description of your project, and any other comments you think are relevant to

8

CPSC/ECE 3220: Operating Systems

the grading. It should have two clearly labeled sections titled with KNOWN PROBLEMS, and DESIGN. The KNOWN PROBLEMS sec-tion should include a speci c description of all known problems or pro-gram limitations. This will not hurt your grade, and may improve it. I am more sympathetic when students have thoroughly tested their code and clearly understand their shortcomings, and less so when I nd bugs that students are ignorant of or have tried to hide. The DESIGN sec-tion should include a short description of how you designed your code (especially anything you thought was interesting or clever about your solution). You should also include references to any materials that you referred to while working on the project. Please do not include special instructions for compilation. The compilation and running of the tests will be automated (see details below) and your instructions will not be followed.

Please make sure you include only the source les, not the object les. Before you submit this single le, please use the following command to check and make sure you have everything in the project2.tgz le, using the following script:

• tar xvzf project2.tgz

• make

This should put all of your source les in the current directory, and compile your library.

Submit your project2.tgz le via handin.cs.clemson.edu. You must name your archive project2.tgz, and it must compile and run. We will compile your code using your Make le, and link it with our test programs.

• Grading

Your project will be graded based on the results of functional testing and the design of your code. We will run several tests to make sure it works properly and correctly handles various error conditions. We will test your programs against a variety of test programs that we have written. Your code should not crash. Your code should not leave interrupts disabled. Your code should not starve threads. Your locks and condition variables should behave correctly. You will receive 10% credit if your code successfully compiles, and 10% for code style and readability. The rest of your score will be determined by the number of tests that your library passes.

9

CPSC/ECE 3220: Operating Systems

I will give up to 5% extra credit for any libraries that get full credit (pass all functional tests) and are faster than my implementation. Fast, but buggy libraries will be scored the same as slow, buggy libraries.

Your source materials should be readable, properly documented and use good coding practices (avoid magic numbers, use appropriately-named variables, etc). Your code should be -Wall clean (you should not have any warnings during compilation). Our testing of your code will be thorough. Be sure you test your application thoroughly.

• Collaboration

You will work independently on this project. You must not discuss the problem or the solution with classmates, and all of your code must be your own code.

You may, of course, discuss the project with me, and you may discuss conceptual issues related to the project that we have already discussed in lecture, via Canvas (do not post any code or implementation details of the algorithms to Piazza or any other web site). Collaborating with peers on this project, in any other manner will be treated as academic misconduct.