为vx6进程实现用户级线程( User Level Thread
)，并根据不同的策略，在进程内做出调度策略。
Brief Description
In this assignment, you will implement user-level threads (also called self-
threads) for xv6 processes and make scheduling decisions inside the process
based on different policies.
An xv6 process starts with only one kernel-supported thread. Within the
process, we will divide this thread into several user-level threads. We will
maintain one of these user-level threads as a user-level scheduler thread.
This thread will make decisions regarding which user-level thread should
execute at a certain time, based on different scheduling algorithms that we
will choose.
Important note
- If your assignment does not compile or your upload is corrupted, you will get a zero. Always double-check your submission.
- Submit a zip file titled by your ASU username. For instance, if your username is adil, your file should be adil.zip.
User-Level Threading Library (ULTLib)
This library will create user-level threads for a process, schedule the
threads to be executed, yield the CPU from a certain thread after a period of
time, and destroy user-level threads when their task is completed. You must
write the code for this library in the files: ulthread.c, ulthread_swtch.S,
and ulthread.h.
Please follow the steps below to complete this task:
Library initialization
Important housekeeping must be done whenever a library is initialized. For
this task, you must create a data structure (similar to proc kept by the
kernel) to keep track of each user-level thread. You must decide on the
contents of this data structure based on the information provided in this
document. During initialization, also assign the first kernel-provided thread
to be the user-level scheduler thread. Write the code for this part in the
ulthread_init() function.
Thread creation
To create a thread, we need the following: (a) the starting function address
where the thread begins execution, (b) initial arguments for the starting
function, (c) the location of a stack that the thread will use during its
execution, (d) the thread’s priority, and (e) a context save location
(context) where the registers of the thread will be saved and restored on
context switches. (a)-(d) will be provided by the user process when it calls
the function ulthread_create(). However, the context save location must be
created and maintained by the ULTLib. Hint: check how the xv6 kernel maintains
context save locations for kernel self-threads. Once the thread is created,
ULTLib should also track that the thread is now RUNNABLE for scheduling
decisions.
Thread switch
The user-level scheduler thread must be called to schedule threads after
creation and each time a user-level thread yields its CPU to a different
thread. At these times, the user-level scheduler thread must (a) save its
registers in it’s context and (b) restore registers from the next scheduled
thread’s context. The thread whose registers are restored is chosen based on
the scheduling policy.
Write an assembly function (ulthread_context_switch() in ulthread.S) that
takes two pointersprevious context and next contextas arguments. The function
must save the current thread’s registers at the location of previous context,
then load the registers from the next context’s location. It must also set-up
registers in such a way that function arguments are provided correctly when a
thread starts.
Suggested reading(s)
RISC-V Function Argument Calling Conventions.
Thread yield and destroy
A user-level thread can give up its execution (using ulthread_yield()) and ask
the user-level scheduler thread to schedule a different thread. Additionally,
at the end of it’s execution, a thread will explicitly call ulthread_destroy()
to signal that it has completed its task. At these points, ULTLib should track
that the thread’s state has changed either to YIELD or FREE. Then, it should
perform housekeeping tasks to maintain data structures, and finally switch
back to the execution of the scheduler.
A user-level thread will decide when to yield based on clock timing
information that it receives from the xv6 OS. To achieve this, you must write
a new xv6 system call (ctime) that traps to the xv6 OS and returns the time
from the RISC-V register r_time.
Thread scheduling decisions
The user-level scheduler thread decides which thread to schedule based on
three algorithms: (a) round-robin, (b) first-come-first-serve, and (c)
priority scheduling. The specific algorithm to use is provided during library
initialization. Your goal is to write a scheduler that is aware of all these
algorithms and decides the correct thread to execute whenever it is called
based on the policy.
Testcases
You are only provided a single testcase for this assignment (namely test1).
Please rigorously test your code using your own testcases for corner
situations.
Miscellaneous
GIT Diff of Changes Required
Provided below is a sample of how many changes would be required to complete
this assignment. Note that this would vary based on code styles
- kernel/syscall.c
- kernel/syscall.h
- kernel/sysproc.c
- user/ulthread.c
- user/ulthread.h
- user/ulthread_swtch.S
- user/usys.pl
Submitting your Assignment
Please zip the entire provided code directory and submit it to the Canvas
under “Assignment 3: CODE”.
