辅导 CSIE3310、讲解 c++/Python编程
Machine Problem 1 - Thread Package
CSIE3310 - Operating Systems
National Taiwan University
Total Points: 100
Release Date: March 5
Due Date: March 19, 23:59:00
TA e-mail: ntuos@googlegroups.com
TA hours: Wed. & Thu. 10:00-12:00 before the due date, CSIE Building R428
Contents
1 Summary 1
2 Environment Setup 2
3 Part 1 (60 points) 2
3.1 Function Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.2 Sample Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4 Part 2 (40 points) 4
4.1 Function Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.2 Reminders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.3 Sample Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5 Run Public Test Cases 5
6 Submission and Grading 5
6.1 Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
6.2 Folder Structure after Unzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
6.3 Grading Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
7 Appendix 6
1 Summary
In this MP, you’ll try to implement a user-level thread package with the help of setjmp and longjmp. The
threads explicitly yield when they no longer require CPU time. When a thread yields or exits, the next thread
should run. The thread can assign additional tasks to other threads, including itself. There are two parts in
this MP. In the first part, you’ll need to implement the following functions:
• thread add runqueue
• thread yield
• dispatch
• schedule
• thread exit
• thread start threading
In the second part, you’ll need to implement the following functions:
• thread assign task
The following function has been implemented for you:
• thread create
Each thread should be represented by a struct thread that contains, at a minimum, a function pointer to the
thread’s function and a pointer of type void * as the function parameters. The function of the thread will take
the void * as its argument when executed. The struct should include a pointer to its stack and some jmp buf
to store it’s current state when thread yield is called. It should be enough to use only setjmp and longjmp
to save and restore the context of a thread.
2 Environment Setup
1. Download the MP1.zip from NTUCOOL, unzip it, and enter it.
$ unzip MP1.zip
$ cd mp1
2. Pull Docker image from Docker Hub.
$ docker pull ntuos/mp1
3. Use docker run to start the process in a container and allocate a TTY for the container process.
$ docker run -it -v $(pwd)/xv6:/home ntuos/mp1
4. Execute xv6
$ make qemu
5. You will use the skeleton of threads.h and threads.c provided in xv6/user folder. Make sure you are
familiar with the concept of stack frame and stack pointer taught in System Programming. It is also
recommended to checkout the appendix given.
3 Part 1 (60 points)
3.1 Function Description
1. struct thread *thread create(void (*f)(void *), void *arg): This function creates a new thread
and allocates the space in stack to the thread. Note, if you would like to allocate a new stack for the
thread, it is important that the address of the stack pointer should be divisible by 8. The function returns
the initialized structure. If you want to use your own template for creating thread, make sure it works
for the provided test cases.
2. void thread add runqueue(struct thread *t): This function adds an initialized struct thread to
the runqueue. To implement the scheduling functionality, you’ll need to maintain a circular linked list
of struct thread. You should implement that by maintaining the next and previous field in struct
thread which always points to the next to-be-executed thread and the previously executed thread respectively. You should also maintain the static variable struct thread *current thread that always
points to the currently executed thread. Note: Please insert the new thread at the end of the runqueue,
i.e. the newly inserted thread should be current thread->previous.
3. void thread yield(void): This function suspends the current thread by saving its context to the
jmp buf in struct thread using setjmp. The setjmp in xv6 is provided to you, therefore you only need
to add #include "user/setjmp.h" to your code. After saving the context, you should call schedule()
to determine which thread to run next and then call dispatch() to execute the new thread. If the thread
is resumed later, thread yield() should return to the calling place in the function.
4. void dispatch(void): This function executes a thread which decided by schedule(). In case the thread
has never run before, you may need to do some initialization such as moving the stack pointer sp to the
allocated stack of the thread. The stack pointer sp could be accessed and modified using setjmp and
longjmp. Please take a look at setjmp.h to understand where the sp is stored in jmp buf. If the thread
was executed before, restoring the context with longjmp is enough. In case the thread’s function just
returns, the thread needs to be removed from the runqueue and the next one has to be dispatched. The
easiest way to do this is to call thread exit().
5. void schedule(void): This function will decide which thread to run next. It is actually trivial, since you
will just run the next thread in the circular linked list of threads. You can simply change current thread
to the next field of current thread.
6. void thread exit(void): This function removes the calling thread from the runqueue, frees its stack
and the struct thread, updates current thread with the next to-be-executed thread in the runqueue
and calls dispatch().
Furthermore, think about what happens when the last thread exits (should return to the main function
by some means).
7. void thread start threading(void): This function will be called by the main function after some
thread is added to the runqueue. It should return only if all threads have exited.
3.2 Sample Output
The output of mp1-part1-0 should look like the following.
$ mp1-part1-0
mp1-part1-0
thread 1: 100
thread 2: 0
thread 3: 10000
thread 1: 101
thread 2: 1
thread 3: 10001
thread 1: 102
thread 2: 2
thread 3: 10002
thread 1: 103
thread 2: 3
thread 3: 10003
thread 1: 104
thread 2: 4
thread 3: 10004
thread 1: 105
thread 2: 5
thread 1: 106
thread 2: 6
thread 1: 107
thread 2: 7
thread 1: 108
thread 2: 8
thread 1: 109
thread 2: 9
exited
4 Part 2 (40 points)
In this part, you are required to implement an additional function thread assign task. This function enables
each thread to manage multiple tasks, with the most recently assigned task being executed first. Note that,
child threads should not inherit tasks from their parent when they are created.
4.1 Function Description
1. void thread assign task(struct thread *t, void (*f)(void *), void *arg): This function assigns a task to the thread t. The second argument, f, is a pointer to the task function, while the third
argument, arg, represents the argument of f. If t has unfinished tasks, the most recently assigned task
will be executed first when t is resumed later. The execution of the original thread function must wait
until all tasks are finished. Note that, this function only assigns tasks and does not trigger any context
switch.
In order to complete this part, you need to modify the following functions:
1. void thread yield(void): Because this function can also be called in the task function, you should save
the context in different jmp bufs according to whether the thread is executing the task function or not.
Specifically, if this function is called in the thread function, you can save the context just like in part 1.
If this function is called in the task function, you should save the context in another jmp buf to prevent
from discarding the context of the thread function.
2. void dispatch(void): If a task is assigned, this function should execute the most recently assigned task
function. If this function has never run before, you may need to do some initialization. If this function
was executed before, restoring the context with longjmp is sufficient. In case this task function just
returns, the thread should execute the next task function. The process follows the same approach as with
the previous task function. Surely, It is possible for a task to be assigned before the thread executes its
thread function.
Feel free to make more modification, such as adding properties in struct thread, designing new structure
for encapsulating task-related logic, etc. The only requirement is that all defined function should work as
described above.
4.2 Reminders
1. When creating a new thread in thread create, ensure that the new thread has no assigned tasks initially.
2. The parameter struct thread *t in thread assign task must exist and not have exited yet.
3. Tasks are executed in Last-Come-First-Serve (LCFS) order. That is, if a thread returns from a task
function and there are unfinished tasks, the most recently assigned task will be executed next.
4. While you are encouraged to add properties in struct thread, modifying the existing properties is not
allowed.
5. The task function may call thread create, thread add runqueue, thread yield, thread exit, or
thread assign task.
6. The memory space allocated to each thread by thread create is sufficient to execute task functions in
all test cases.
7. In all test cases, a thread may have at most 20 unfinished tasks at any moment.
8. If you intend to use global variables in threads.h, threads.c, or your test files, it is recommended to
add the static keyword to prevent unexpected situations.
4.3 Sample Output
The output of mp1-part2-0 should look like the following.
$ mp1-part2-0
mp1-part2-0
thread 1: 100
task 2: 101
thread 2: 0
thread 1: 101
thread 2: 1
thread 1: 102
task 2: 103
thread 1: 103
thread 2: 2
thread 1: 104
task 2: 105
thread 2: 3
thread 1: 105
thread 2: 4
exited
5 Run Public Test Cases
You can get 35 points (100 points in total) if you pass all public test cases. You can judge the code by running
the following command in the docker container (not in xv6; this should run in the same place as make qemu).
Note that you should only modify xv6/user/thread.c and xv6/user/thread.h. We do not guarantee that
you can get the public points from us if you modify other files to pass all test cases during local testing.
$ make grade
If you successfully pass all the public test cases, the output should be similar to the one below.
== Test thread package with public testcase part1-0 (10%) ==
thread package with public testcase part1-0: OK (16.8s)
== Test thread package with public testcase part1-1 (10%) ==
thread package with public testcase part1-1: OK (1.3s)
== Test thread package with public testcase part2-0 (5%) ==
thread package with public testcase part2-0: OK (0.8s)
== Test thread package with public testcase part2-1 (5%) ==
thread package with public testcase part2-1: OK (0.9s)
== Test thread package with public testcase part2-2 (5%) ==
thread package with public testcase part2-2: OK (1.0s)
Score: 35/35
If you want to know the details about the test cases, please check xv6/grade-mp1, xv6/user/mp1-part1-0.c,
xv6/user/mp1-part1-1.c, xv6/user/mp1-part2-0.c, xv6/user/mp1-part2-1.c and xv6/user/mp1-part2-2.c.
6 Submission and Grading
6.1 Source Code
Run the command below to pack your code into a zip named in your lowercase student ID, for example,
r11922088.zip. Upload the zip file to NTUCOOL.
$ make STUDENT_ID= zip # set your ID here
Please ensure that your student ID is in lowercase letters. E.g., it should be r11922088 instead of
R11922088. Besides, make sure your xv6 can be compiled by make qemu.
6.2 Folder Structure after Unzip
We will unzip your submission using unzip command. The unzipped folder structure looks like this.
|
+-- threads.c
|
+-- threads.h
6.3 Grading Policy
• There are 2 public test cases and 4 private test cases in Part 1.
– Public test cases (20%): mp1-part1-0 and mp1-part1-1. 10% each.
– Private test cases (40%): 10% each.
• There are 3 public test cases and 4 private test cases in Part 2.
– Public test cases (15%): mp1-part2-0, mp1-part2-1 and mp1-part2-2. 5% each.
– Private test cases (25%): 5%, 5%, 7.5%, 7.5%.
• You will get 0 if we cannot compile your submission.
• You will be deducted 10 points if we cannot unzip your file through the command line using the unzip
command in Linux.
• You will be deducted 10 points if the folder structure is wrong. Using uppercase in the is
also a type of wrong folder structure.
• If your submission is late for n days, your score will be max(raw score − 20 × ⌈n⌉, 0) points. Note that
you will not get any points if ⌈n⌉ >= 5.
• Our grading library has a timeout mechanism so that we can handle the submission that will run forever.
Currently, the execution time limit is set to 240 seconds. We may extend the execution time limit if we
find that such a time limit is not sufficient for programs written correctly. That is, you do not have to
worry about the time limit.
• You can submit your work as many times as you want, but only the last submission will be graded.
Previous submissions will be ignored.
• The grading will be done on a Linux server.
7 Appendix
[1] Function Pointer. https://en.wikipedia.org/wiki/Function pointer
[2] Call Stack. https://en.wikipedia.org/wiki/Call stack
[3] MP1 Slides. link