In this project, you will work on two programs that help you (1) to be familiar with the concepts of threads, synchronization, and multi-threaded programming design patterns; (2) to understand how user level thread scheduling works; and (3) to gain hand-on experience on writing multi-threading programs.
Implement a Thread Pool library that can be used by a multi-threaded server program. The library shall work on a Linux machine in the School of Computing computer labs.
Today, most server programs are written as multi-threaded programs. Among these programs, thread pool is a widely used design pattern that solves two issues existed in naive programs. that creates a separate thread for each request. First, creating a threads takes time and it is a waste when the thread will be discarded once it has completed its work. Second, because the number of requests at any time point is unpredictable, if we don't place a bound on the number of concurrent threads, a large number of threads could exhaust system resources like CPU time or memory.
The general idea behind a thread pool is to create a number of threads at start-up and then place them into a pool, where they sit and wait for work. When a server receives a request, rather than creating a thread, it instead submits the request to the thread pool and resumes waiting for additional requests. If there is an available thread in the pool, it is awakened, and the request is serviced immediately. If the pool contains no available thread, the task is queued until one becomes free. Once a thread completes its service, it returns to the pool and awaits more work.
In this task, you will implement a thread pool library that can be used by some server programs. A server program submits its tasks to the thread pool and the threads in the thread pool fetch tasks and do the work. We provide an example server program called tptest
and a starter code for you to get started. The starter code uses the simple thread API developed by the authors of the OSPP textbook. However, you are free to use other thread libraries like pthread
if you are comfortable to do so.
-
You provide a thread pool library that implements a ThreadPool class which has at least three APIs:
a.
ThreadPool(unsigned int numThreads)
creates a pool of numThreads.b.
int submit(void (*somFunction)(void *), void *p)
submits a task to the pool, wheresomFunction
is a pointer to the function that a thread from he pool will execute and ps is parameter passed to the function.c.
shutdown()
that shutdown the pools. -
Invoking the command
make
shall create a executable binarytpooltest
, which can be used to test your thread pool implementation.
Your program shall generate output like the following example except that the order of the output may be different.
$ make
g++ -c -g -Wall -Werror -D_POSIX_THREAD_SEMANTICS tpooltest.cc -o tpooltest.o
g++ -c -g -Wall -Werror -D_POSIX_THREAD_SEMANTICS ThreadPool.cc -o ThreadPool.o
g++ -c -g -Wall -Werror -D_POSIX_THREAD_SEMANTICS Lock.cc -o Lock.o
g++ -c -g -Wall -Werror -D_POSIX_THREAD_SEMANTICS CV.cc -o CV.o
gcc -c -g -Wall -Werror -D_POSIX_THREAD_SEMANTICS thread.c -o thread.o
g++ -g -Wall -Werror -D_POSIX_THREAD_SEMANTICS tpooltest.o ThreadPool.o Lock.o CV.o thread.o -lpthread -o tpooltest
$ ./tpooltest 3 0 5
sum of 1 ... 1 = 1
sum of 1 ... 4 = 10
sum of 1 ... 5 = 15
sum of 1 ... 2 = 3
sum of 1 ... 3 = 6
sum of 3 ... 9 = 42
sum of 6 ... 8 = 21
sum of 9 ... 10 = 19
sum of 7 ... 12 = 57
sum of 3 ... 8 = 33
$
-
If you use the simple thread API, then you should apply the best practice of designing shared objects described in the OSPP textbook. The textbook covers all the APIs for the thread, lock, and condition variable that you will need for this task.
-
We have provide a starter code in
ThreadPool.cc
andThreadPool.h
. We also provided atpooltest.cc
for an example server program. -
In
ThreadPool.h
, you will see some unusual treatment: theThreadPool
constructor (ThreadPool.cc:9) passes an external functionexecutor()
and a pointer to itself (i.e.,this
) tothread_create_p()
and thenexecutor
calls thethread_work()
method of the ThreadPool object pointed by the pointer parameter passed into theexecutor()
inthread_create_p
. The only reason for this treatment is to bypass the constraint that ISO C++ forbids taking the address of an unqualified or parenthesized non-static member function to form a pointer to member function. We provide the code so that you can avoid this error and know how to fix it when you see similar errors in your code. -
For the task queue, you can use the
deque
template library, although you have to add proper synchronizations to make your queue thread-safe. For this task, all you need for deque is as follows:#include <deque>
include library for deque implementationstd::deque <Task> queue;
define a queue of Tasksqueue.push_back(task);
add a task to the queuetask = queue.front();
fetch a task in the front
queue.pop_front();
remove a task from the frontqueue.size()
get number of tasks in the queue
Implement thread switching in user-level thread package. The program shall run on the xv6-riscv OS in the QEMU environment
in the School of Computing computer labs.
This task will familiarize you with how state is saved and restored in context switches. You will implement switching between threads in a user-level threads package. This task involves more code reading and concept understanding. Once you truly understand the concepts of how user-level threads work, the code will be trivial.
For this task it will be important to understand a bit of RISC-V assembly. There is a file user/call.c
in
your xv6 repo. make fs.img
builds a user program call
and a readable assembly version of the program in user/call.asm
.
Read the code in call.asm
for the functions g
, f
, and main
.
The instruction manual for RISC-V is available at https://content.riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf.
Here are some questions that you should answer (store the answers in a file answers-syscall.txt
in the TaskB folder):
- Which registers contain arguments to functions? For
example, which register holds 13 in
main
's call toprintf
? - Where is the function call to
f
frommain
? Where is the call tog
? (Hint: the compiler may inline functions.) - At what address is the function
printf
located? - What value is in the register
ra
just after thejalr
toprintf
in main?
In this task you will design the context switch mechanism for a user-level threading system, and then implement it. To get you started, your xv6 has two files user/uthread.c and user/uthread_switch.S, and a rule in the Makefile to build a uthread program. uthread.c contains most of a user-level threading package, and code for three simple test threads. The threading package is missing some of the code to create a thread and to switch between threads.
Your job is to come up with a plan to create threads and save/restore registers to switch between threads, and implement that plan.
Once you've finished, you should see the following output when you run uthread on xv6 (the three threads might start in a different order): $ make qemu ... $ uthread thread_a started thread_b started thread_c started thread_c 0 thread_a 0 thread_b 0 thread_c 1 thread_a 1 thread_b 1 ... thread_c 99 thread_a 99 thread_b 99 thread_c: exit after 100 thread_a: exit after 100 thread_b: exit after 100 thread_schedule: no runnable threads $ This output comes from the three test threads, each of which has a loop that prints a line and then yields the CPU to the other threads.
At this point, however, with no context switch code, you'll see no output.
- You should complete
thread_create
to create a properly initialized thread so that when the scheduler switches to that thread for the first time,thread_switch
returns to the function passed as argumentfunc
, running on the thread's stack. You will have to decide where to save/restore registers. Several solutions are possible. You are allowed to modify struct thread. - You'll need to add a call to
thread_switch
inthread_schedule
; you can pass whatever arguments you need tothread_switch
, but the intent is to switch from threadt
to thenext_thread
. - You will need to complete
thread_switch
function in theuthread_switch.S
file.
Some hints:
thread_switch
needs to save/restore only the callee-save registers. Why?- You can add fields to
struct thread
into which to save registers. - You can see the assembly code for
uthread
inuser/uthread.asm
, which may be handy for debugging. - To test your code it might be helpful to single step through your
thread_switch
usingriscv64-linux-gnu-gdb
.
You can get started in this way:
(gdb) file user/_uthread
Reading symbols from user/_uthread...
(gdb) b thread.c:60
This sets a breakpoint at a specified line in thread.c
.
The breakpoint may (or may not) be triggered before you even run uthread
.
How could that happen?
Once your xv6 shell runs, type "uthread
", and gdb will break
at line thread_switch
. Now you can type commands like the following
to inspect the state of uthread
:
(gdb) p/x *next_thread
With "x", you can examine the content of a memory location:
(gdb) x/x next_thread->stack
You can single step assembly instructions using:
(gdb) si
On-line documentation for gdb is here.
Please following the procedure below in your submission.
- Switch to your project folder:
cd ~/path/to/your-projects-folder
- Clean up the folders
cd TaskA make clean cd ../TaskB make clean
- List files that you have added or modified:
git status
- Stage the new and modified files in your local repo:
git add files-you-created-or-modified
- Commit the changes to your local repo:
git commit -m "Finished Project #2"
- Push the changes to the remote repo (i.e. github):
git push
Orgit push origin master
. - Verify all changes have been push into the repo on github.
- You can run "git status", "git log", and "git show" to the see the changes and commits you have made
- You can also log into github to see if your changes have been actually pushed into your project repo on github.
- (Optional but recommended) For a further validation, you can check out the repo in a separate folder on your computer and then verify that it has all the files for the programs to work correctly.