This exercise is Difficult. Start early!
In this exercise you are required to implement a user-level thread library with a basic scheduling algorithm and some interfaces. The package should be delivered in the form of a static library. The public interface of the library is ~os/lib/uthreads.hh. Do not change or submit the header file: Your exercise should work with the header we provided. You should implement all the functions in the header, as explained below. You will probably find it necessary to implement internal functions and data structures. These are not visible outside the library, as they are the private part of your implementation. Therefore, you are not restricted in their number, signatures, or content.
At any given time during the running of the user's program, each of the threads in the program is in one of the states shown in the following state diagram. Transitions from state to state occur as a result of calling one of the library functions, or from elapsing of time, as explained below.
The scheduler in this excercise will operate according to a simple principle:
The thread that is RUNNING at any given moment is the thread that was created more recently than all other READY threads. This means that the thread id of the RUNNING thread is higher than the id's of all the READY threads.
Following is the list and description of all library functions. Calling these functions may result in a transition of states in the state diagram shown above. Library functions that accept a thread id may be used by a thread to change its own state or to change some other thread's state. You should check for legality of input parameters in all functions whenever possible. If any parameter is illegal, the function should do nothing and fail (i.e. return -1).
int thread_lib_init()
Description: This function initializes the thread library.
You may assume that this function is called before any other thread library function, and that it is called exactly once.
Return value: On success, return 0. On failure, return -1.
int thread_spawn(void (*thread_func)(void))
Description: This function creates a new thread, whose entry
point is the function thread_func with the signature void
thread_func(void). Each thread should be allocated with a stack of size
STACK_SIZE bytes.
Return value: On success, return the ID of the created thread. On failure, return -1.
int thread_terminate(int tid)
Description: This function terminates the thread with
ID tid and deletes it from all relevant control structures. All the resources allocated by the library for this thread
should be released. Terminating the main thread (tid == 0) will result
in the termination of the entire process using exit(0).
Return value: The function returns 0 if the thread was successfully terminated and -1 otherwise. If a thread terminates itself or the main thread is terminated, the function does not return.
int thread_sync(int sync_id, int num)
Description: This function is used to synchronize several
threads in the following way: A thread that calls this function
becomes SUSPENDED until a total of num threads are SUSPENDED on this
function with the same sync_id. When this condition is met, all
the threads who called this function with the relevant sync_id are
resumed and become READY. The value of
sync_id is allowed to be any integer. The value of
num must be at least 2, otherwise the library function should
fail. If a thread calls this function while there are other threads
who are SUSPENDED with the same sync_id then it must use
the same input num as the other SUSPENDED threads used, otherwise
the function should fail.
It is an error to call this function from the main thread (tid
== 0). If a thread calls thread_sync but is then terminated,
it should not be counted as one of the num threads when
deciding whether it's time to resume all the synching threads.
Return value: On success, return 0. On failure, return -1.
int thread_sleep(int tid, int num_millisecs)
Description: This function suspends the thread with id
tid for num_millisecs milliseconds. If the thread is
already suspended, then the function should fail. Only one thread in
the process is allowed to sleep at any given time, therefore if any
other thread is sleeping, the function should fail. Note that
whenever we mention time in this exercise, we mean the running time
of the process, also called the virtual time, and not the
real time that has passed in the system. The process running time is
measured by the Virtual Timer. An example of using this timer
can be found here. It is an error to call thread_sleep for the main thread (tid == 0). It is illegal to ask for num_millisecs equal to zero.
Return value: On success, return 0. On failure, return -1.
int thread_gettid()
Description: This function returns the thread ID of the calling thread.
Return value: The ID of the calling thread.
int
thread_get_time_until_wakeup(int tid)
Description: This function returns the time until the thread
with id tid wakes up. If the thread is not sleeping, the
function should return 0. If the thread is sleeping, the function
should return the number of milliseconds left until it will become
READY again. If there is a fractional number of milliseconds, this number should always be rounded up.
Return value: Number of milliseconds until wakeup.
int thread_get_num_waiting_for_sync(int
sync_id)
Description: This function returns the number of threads that
are currently SUSPENDED on the function thread_sync with id
sync_id.
Return value: The number of waiting threads. If no thread is
waiting for sync_id, return 0.
When a system call fails you should print a single line in the following format:
"system error: text\n"
Where text is a description of the error, and then exit(1).
When a function in the threads library fails, you should print a single line in the following format:
"thread library error: text\n"
where text is a description
of the error, and then return the appropriate return value.
Submit tar file named ex2.tar containing:
Make sure that the tar file can be extracted and that the extracted files do compile.
This exercise is Difficult. Start early!