Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Project #2:
User Mode Thread Library
Objectives
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.
1 Thread Management API
Your threading library will implement the API shown in Listing 1. This
API will be defined in a file called mythreads.h (I will put the header
file in the git repository). You should use this header file, 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 first 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 specified function with
the argument (void *) that was passed to threadCreate. If successful,
this function should return an int that uniquely identifies
the new thread, and will be used in calls to the threadJoin function.
The newly created thread should be run immediately after
it is created (before threadCreate returns).
1This project is used with permission by Dr. Jacob Sorber
1
CPSC/ECE 3220: Operating Systems Fall 2018
Listing 1: mythreads.h—the API for your threading library
# define STACK_SIZE (16*1024)
# define NUM_LOCKS 10
# define CONDITIONS_PER_LOCK 10
// the type of function used to run your threads
typedef void *(* thFuncPtr ) (void *) ;
extern void threadInit () ;
// thread management functions
extern in t threadCreate ( thFuncPtr funcPtr , void *
argPtr ) ;
extern void threadYield () ;
extern void threadJoin ( in t thread_id , void ** result ) ;
extern void threadExit (void * result ) ;
// synchronization functions
extern void threadLock ( in t lockNum ) ;
extern void threadUnlock ( in t lockNum ) ;
extern void threadWait ( in t lockNum , in t conditionNum ) ;
extern void threadSignal ( in t lockNum , in t conditionNum
) ;
// control atomicity
extern in t interruptsAreDisabled ;
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
specified 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
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.
2 Synchronization
Your library will also give programmers tools so they can synchronize
their threads and protect shared data accesses. Specifically, your library
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 defined 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 different 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 acquire
the specified 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 specified 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 effect.
threadWait—This function atomically unlocks the specified mutex
lock and causes the current thread to block (wait) until the
specified 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 undefined
(your library should exit the process, if this occurs, and
3
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 specified condition variable. If no threads are waiting on
the condition variable, the call has no effect.
You should not do any deadlock detection. If a thread calls threadLock()
on a lock that it already holds, it should deadlock.
3 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 fires (we will use setitimer
to generate interrupts). This means that, just like hardware interrupts,
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.
4 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
Listing 2: Methods for enabling/disabling of interrupts.
s t a t i c void interruptDisable () {
assert (! interruptsAreDisabled ) ;
interruptsAreDisabled = 1;
}
s t a t i c void interruptEnable () {
assert ( interruptsAreDisabled ) ;
interruptsAreDisabled = 0;
}
library from a set of source files (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 files, 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 file, replacing the files that you specified. 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
Makefile that compiles your library. The example above used gcc, but
you’re welcome to use clang as well.
5 How to implement threads?
Your library will implement threads using the getcontext, makecontext,
and swapcontext functions. These functions allow you to get the current
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
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 machine
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 defines 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 first 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 modifies the saved context,
so that when it is activated, it will call a specific function, with the
specified 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 identifier (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
efficiently find the next thread to activate.
One last hint: Students often wonder how they should tell when a
6
Listing 3: Creating a new execution context.
ucontext_t newcontext ;
getcontext (& newcontext ) ; // save the current context
// allocate and initialize a new call stack
newcontext . uc_stack . ss_sp = malloc ( STACK_SIZE ) ;
newcontext . uc_stack . ss_size = STACK_SIZE ;
newcontext . uc_stack . ss_flags = 0;
// modify the context , so that when activated
// 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 .
makecontext (& newcontext ,
(void (*) (void) ) func , 3 , x , y , z ) ;
thread completes. One way to handle this is by using the uc link field
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 finished.
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 programming
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),
first.
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 flag, it should not produce any
warnings.
7
Listing 4: Swapping two contexts.
// points to a saved context somewhere in memory
ucontext_t * savedcontext ;
// points to the place in memory where
ucontext_t * where_to_save_currently_running_context ;
// save the running context , and give the saved context
the CPU
swapcontext ( where_to_save_currently_running_context ,
saved context ) ;
// note that swapcontext () 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 finished requires
some care. Normally, when a thread completes, you need to
deallocate (free) the finished 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
finished. 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 flu, 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 Makefile should build your library (by running make). It should
produce a single file (libmythreads.a).
The README file should include your name, a short description
of your project, and any other comments you think are relevant to
8
the grading. It should have two clearly labeled sections titled with
KNOWN PROBLEMS, and DESIGN. The KNOWN PROBLEMS section
should include a specific description of all known problems or program
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 find bugs
that students are ignorant of or have tried to hide. The DESIGN section
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 files, not the object files.
Before you submit this single file, please use the following command
to check and make sure you have everything in the project2.tgz file,
using the following script:
$ tar xvzf project2.tgz
$ make
This should put all of your source files in the current directory, and
compile your library.
Submit your project2.tgz file 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 Makefile, and link it with our
test programs.
6 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.
- 经济Economics
- 金融Finance
- 会计Accounting
- 工商管理Business Management
- 计算机computer science
- 商业分析business analysis
- 法律Law
- 管理Management
- 市场营销Marketing
- 哲学Philosophy
- 心理学Psychology
- 物理Physical
- 统计学statistics
- 电气工程electric engineering
- 化学chemistry
- 生物biology
- 数学mathematics
- 语言学linguistics
- 土木工程civil engineering
- 工程力学engineering mechanics
- 艺术art
PROFESSIONAL HELP!
在线咨询
立即下单
Wechat：THEend8_ 
Email：