CPSC/ECE 3220代做、代写C/C++编程、代写C/C++语言程序、代做C/C++设计

日期：2018-10-08 09:51

CPSC/ECE 3220: Operating Systems Fall 2018

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

CPSC/ECE 3220: Operating Systems Fall 2018

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

CPSC/ECE 3220: Operating Systems Fall 2018

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

CPSC/ECE 3220: Operating Systems Fall 2018

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

CPSC/ECE 3220: Operating Systems Fall 2018

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

CPSC/ECE 3220: Operating Systems Fall 2018

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

CPSC/ECE 3220: Operating Systems Fall 2018

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

CPSC/ECE 3220: Operating Systems Fall 2018

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.

9

CPSC/ECE 3220: Operating Systems Fall 2018

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.

7 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.