Programming Assignment 3 - User-Level Thread Library

# Programming Assignment 3 - User-Level Thread Library :::info **:date: Deadline: 2024/12/12 23:59:00 (UTC+8)** [Github Classroom Link](https://classroom.github.com/a/qiC0SpnL) **Late Penalty:** 1. If you push your submission between 12/12 23:59:01 ~ 12/14 23:59:00, your grade will be multiplied by 0.85. 2. If you push your submission between 12/14 23:59:01 ~ 12/17 23:59:00, your grade will be multiplied by 0.7. 3. If you push your submission between 12/17 23:59:01 ~ 12/19 23:59:00, your grade will be multiplied by 0.5. 4. Any submission after 12/19 23:59:00 will not be graded and considered as **0 score**. ::: :::danger :warning: Warning: We will base our evaluation solely on your last commit. Regardless of any earlier commits you may have pushed, if your last commit is submitted after the deadline, only that commit will be considered for grading, and a corresponding late submission penalty will be applied. ::: ## Clarifications and Corrections ### 12/5 **Corrections:** - The order of arguments `q_p` and `q_s` in the command line is incorrect. The correct order is `q_p q_s`, which is consistent with `main.c`. This correction is applied to the [Compilation and Execution section](#Compilation-and-Execution), and the [Sample Input and Output section](#Sample-Input-and-Output). ### 12/1 **Clarifications:** - In the original specification, the details regarding the operation of the alarm were intentionally omitted, as we expected students to determine the implementation independently. However, we have found that this approach introduces ambiguity, particularly given the extensive operations described in the scheduler workflow. Therefore, we have now explicitly added the required alarm operations at the beginning of the [scheduler workflow](#Scheduler-Workflow) for clarity. - The progress of the idle thread shall be done in a loop. That is, the thread repeatedly do the progress. The clarification is added into the [section](#Special-Routine:-Idle-Thread). ### 11/30 **Corrections:** - When a signal is caught, the signal handler should print `caught [signal name]` to `stdout` instead of the orignal format, `caught signal [signal name]`, which is a typo. For example, if `SIGTSTP` is caught, you should print `caught SIGTSTP` to `stdout`, as demonstrated in the [Sample I/O section](#Sample-Input-and-Output). This correction is applied to the [assignment specification](#Signal-Handling). ### 11/29 Part2 **Corrections:** - For `thread_setup`, originally, it is said that you should return the control back to `init_threads` after a thread is setting up, which should be corrected to `spawn_thread`. This correction is also applied to the [assignment specification](#Macros-to-Implement-and-Thread-Lifecycle). ### 11/29 Part1 **Clarifications:** - In judging, we will modify the definition of `struct tcb`, so that: - The members needed by thread routines provided by TAs will be added. - The members needed by your implementations of the thread routines will be kept. - The clarification is also updated in the [assignment specification](#Data-Structures). **Corrections:** - The definition of `sleeping_set` in `main.c` is misplaced. There shall not be that definition in `main.c`. Please remove it. A new requirement is also added to the [assignment specification](#Data-Structures). ## Typos This section is dedicated to listing minor corrections or clarifications that do not significantly affect the understanding of the assignment. ### 12/11 **Don't worry, this is just a typo.** In testcase3, [Sample I/O section](#Sample-Input-and-Output), the explanation of thread 4 should be `fibonacci` with $n = 2$ instead of $n=5$. ### 12/6 In testcase3, [Sample I/O section](#Sample-Input-and-Output), we forgot to write a comment `# send SIGTSTP here` to indicate the `TSTP` signal coming before the third `caught SIGTSTP`. It is now updated. ### 12/2 In testcase2, [Sample I/O section](#Sample-Input-and-Output), the output `thread 0: idle` ends with an extra blank (`" "`), which is not expected. It is now updated. ### 12/1 In the description of `main.c`, we found that the explanation of `start_threading()` function is not fully correct. For the corrected description, please refer to [assignment specification](#Pre-defined-Functions-in-mainc). ### 11/30 In routine `enroll`, we asked you to print ```text thread [id]: enroll in [class name] ``` in **Step 4**, which is inconsistent with the [Sample I/O section](#Sample-Input-and-Output). This is a typo and should be corrected to: ```text thread [id]: acquire write lock, enroll in [class name] ``` to maintain the consistency. The corresponding [assignment specification](#Routine-Descriptions) is updated. ## Assignment Overview ### Objective This assignment focuses on implementing a user-level thread library in C. It involves aspects of thread management, including creating, scheduling, and synchronizing threads. ### Requirements Your program must match the specified behavior precisely, as the judging environment will strictly compare the output to verify correctness. ### What You Will Do - Implement thread scheduling, including preemption and context switching. - Manage thread synchronization using read-write locks. - Implement a sleeping and waking mechanism for threads. - Handle thread states, including running, ready, waiting, and sleeping. ### Scope In this assignment, you will be provided with several partially implemented files. Your task is to complete the implementation of a user-level thread library and some thread routines. Specific focus areas include: - Completing the macros for thread lifecycle operations in `thread_tool.h`. - Implementing a signal handler and a scheduler in `scheduler.c`. - Writing routines that demonstrate thread usage in `routine.c`. ## Environment Specification :::danger :warning: Warning: This assignment only runs on the specified environment. Compatibility with other architectures/OSes is not guaranteed. ::: OS: x86_64 Linux 6.6 C standard: `-std=gnu17` The required Linux kernel is indeed the current version of CSIE workstations, so you don't need to worry about it if you do your assignment on CSIE workstations. Please note that modification of `gcc` compilation flags is prohibited. That is, your changes to the `Makefile` will not be adopted. Basically, including any header files other than the provided ones is not allowed. However, if there is a need to include some header files, please ask the TAs, telling them the reason, and they will consider it. :::info C17 with GNU extensions is actually the default C standard of `gcc` today, so you may not feel anything different than usual. ::: ## Some Information and Tips - Before asking questions, please read the assignment specification carefully. If you still have questions, it is preferred to ask them in the discussion space. - In this specification, we use the term `longjmp()` to refer to both `longjmp()` and `siglongjmp()`, `setjmp()` to refer to both `setjmp()` and `sigsetjmp()`. It **is** part of the assignment to decide which one to use. - There are actually 8 sections of the manual pages in Linux, and some entries are in multiple sections. For example, `sigaction()` is in both section 2 and section 3P, which are System Calls Manual and POSIX Programmer's Manual, respectively. In general, section 2 may be more related to system calls, also to your assignment. You may want to check the [manual page of `man-pages`](https://man7.org/linux/man-pages/man7/man-pages.7.html) itself for more information. - Modifications to the provided C files are allowed, except for those which are explicitly mentioned in the assignment specification. However, you must strictly follow the requirements of the behavior of your program. You can ask the TAs if you are not sure whether your modifications are allowed. ## File Structure :::danger :warning: **Warning:** The default version of `main.c` and `routine.h` will be used for judging. Your modifications to these files will be discarded. ::: The source code files is put in the `src` directory. The following files are provided: 1. **main.c** Contains some functions for initializing the thread library and creating the thread routines. Also, it initializes the data structures and starts the scheduler. 1. **thread_tool.h** Provides necessary macros and data structures for thread handling. Partially complete; some macros must be completed as specified. 1. **scheduler.c** Is blank and requires you to complete a signal handling and a thread scheduling function in this file. 1. **routine.c** Contains thread routines. You’ll need to implement parts of this file based on the assignment specifications. 1. **routine.h** Provides function prototypes for routine functions. You should not modify this file. ## Pre-defined Functions in `main.c` This file is complete and will be used as-is during grading. You are not required to understand its implementation, but it is encouraged to read through it to understand the overall program flow. 1. `int main(int argc, char *argv[])` The main function that initializes the thread library, creates threads, and starts the scheduler. The parameters will be described in the following sections. 1. `void unbuffered_io()` Turns stdin, stdout, and stderr into unbuffered I/O. 1. `void init_signal()` This function blocks `SIGTSTP` and `SIGALRM`, and then set `sighandler()` as the signal handler for these two signals. 1. `void spawn_thread(int argc, char *argv[])` Creates the user-level threads with the given arguments. You may check why we need the `padding` variable in the Extra Notes section. 1. `void start_threading()` ~~Sets up the alarm, then~~ Calls the scheduler, which will then setup the alarm. ## User-Level Thread Library Implementation ### Data Structures 1. **Thread Control Block (TCB)** - Defined in `thread_tool.h` as `struct tcb` - Contains fields for: - `int id`: Unique identifier for each thread. - `int *args`: Arguments to be passed to the thread function. - `waiting_for`: Indicator of which resource the thread is waiting for (e.g., read or write lock). - `sleeping_time`: Duration for which the thread should sleep. - `env`: Execution context used for saving and restoring thread state (`longjmp` usage for context switching). - `n`, `i`: Variables to retain values between context switches, allowing the thread to resume computations seamlessly. You can add more fields if needed. - Do **not** delete existing members of the structure. Routines implemented by TAs will be used for judging, and they may rely on these members. - Members defined by you will be kept in the judging process. Additional members needed by TAs' thread routines will be added by TAs. 1. **Queues** - `ready_queue` and `waiting_queue` (both `struct tcb_queue`): Circular arrays used for managing thread states. - `ready_queue`: Holds threads that are ready to run. - `waiting_queue`: Holds threads waiting for a resource to become available. 1. **Locks** - `rwlock` (`struct rwlock`): A read-write lock structure for synchronizing threads. - `read_count`: Tracks the number of threads holding a read lock. - `write_count`: Tracks whether a write lock is held (only one thread can hold a write lock). 1. **Thread Sleeping Set** - A data structure that must be implemented to manage sleeping threads. - Stores threads that are currently sleeping, along with information on how long they should sleep. - When a thread's sleep duration expires, the scheduler shall move it back to the `ready_queue`. - When a `thread_awake()` call is made, the awaken thread shall be moved from the sleeping set to the `ready_queue` despite its remaining sleeping time. - Even though named `sleeping_set`, it can be implemented as an array or any other data structure. A priority queue is recommended for simulating the real-world implementation. - The definition of the sleeping set in `main.c` is misplaced. Please remove it. Please define your own `sleeping_set` in `scheduler.c`, and declare it as `extern` in `thread_tool.h` simultaneously. ### Pre-Defined Global Variables The following global variables are defined in `main.c`, and declared as `extern` in `thread_tool.h` for use in other files. You can use these variables wherever `thread_tool.h` is included. Do **not** "define" global variables in a header files, instead, "declare" them with `extern` keyword and actually "define" them in a source file. - `struct tcb *current_thread`: Points to the currently running thread. - `struct tcb *idle_thread`: Points to the idle thread, which runs when no other threads are ready to. More details will be discussed later. - `struct tcb_queue ready_queue`: Circular array for storing threads that are ready to run. - `struct tcb_queue waiting_queue`: Circular array for storing threads that are waiting for a resource. - `struct rwlock rwlock`: Read-write lock structure for synchronizing threads. ### Macros to Implement and Thread Lifecycle - You have to implement the following macros which are essential for managing thread lifecycle and synchronization. Each macro has a specific purpose in the thread lifecycle. - All the behaviors associated with the scheduler will be discussed later. 1. **Creation** - `thread_create(func, t_id, t_args)`: Creates a new thread with `t_id`, running the specified function with the given arguments. - Just simply call `func` with `t_id` and `t_args` as arguments. 2. **Execution Setup** - `thread_setup(t_id, t_args)`: Initializes the TCB, registers the thread in the ready queue (if it is not the idle thread), and prepares it to be scheduled. After that, the control should be returned back to `spawn_thread()`. - Shall be called at the start of every thread routine to set up the thread. - The following messages should be printed to the **standard output**: ```text thread [id]: set up routine [routine name] ``` - The name of the routine can be accessed by the `__func__` variable (This is a C99 feature! Refer to [this link](https://gcc.gnu.org/onlinedocs/gcc/Function-Names.html)). - Sets up the initial context for the thread using `setjmp()`, which will allow the scheduler to switch to this thread later. - If the thread is the idle thread, the `idle_thread` variable should be set here. - If not, registers the thread in the `ready_queue` by pushing it into the queue - To give the control back to `spawn_thread()`, you should `return` in this macro, which means `return` in `func()` in fact. 3. **Yielding Control** - `thread_yield()`: Relinquishes control to the scheduler after each computational iteration or step. - Saves the current thread's context using `setjmp()`, allowing it to resume later. - **Sequentially** unblock and block `SIGTSTP` and `SIGALRM` signals. - That is, do like this: - Unblock `SIGTSTP` - Block `SIGTSTP` - Unblock `SIGALRM` - Block `SIGALRM` - `setjmp()` may be called before unblocking signals, so the thread can safely be preempted by the scheduler. 4. **Synchronization (Locks)** All the following macros are associated with the read-write lock `rwlock` declared in `thread_tool.h`. Moreover, you can assume that the `rwlock` is used only to protect exactly one resource in the judging process. - `read_lock()`: Acquires a read lock of the resource. - If a write lock is held, yields control to the scheduler, which will then push the current thread to the `waiting_queue`. - You may want to use `setjmp()` to save the context of the thread. - After switching back to the thread, check if the resource is available again. If so, acquire the read lock; otherwise, yield control to the scheduler again. - In the view of threads, the macro is a blocking call, and they get the lock after returning from the macro. - `write_lock()`: Acquires a write lock of the resource. - If any read or write lock is held, yields control to the scheduler, which will then push the current thread to the `waiting_queue`. - You may want to use `setjmp()` to save the context of the thread. - Similar to `read_lock`, the macro is a blocking call, and the thread shall get the write lock after returning from the `write_lock` macro. - `read_unlock()`: Releases a read lock. It is guaranteed that **only** one of the owners of the read lock will call the macro in correct implementations based on assignment's [requirements](#third-routine-enrollment-for-sp-course). - `write_unlock()`: Releases a write lock, allowing other threads to acquire the lock. It is also guaranteed that **only** the owner of the write lock will the macro in correct implementations based on assignment's requirements. 5. **Sleeping and Waking** - `thread_sleep(sec)`: Puts a thread to sleep for a specified time (`sec`) and moves it to the `sleeping_set`. - The duration `sec` is a positive integer between 1 and 10. - The scheduler will move the thread back to the `ready_queue` once the sleep duration has elapsed. - We simulate the sleeping time by the **number of `SIGTSTP` and `SIGALRM` caught** times the **time slice**, not the real-world time. - That is, every time a `SIGTSTP` or `SIGALRM` signal is caught, the sleeping time of the thread will be decreased by `time_slice`. More details will be discussed later. - It simulates that all threads use exactly `time_slice` seconds in each step. - The real-world time approach will introduce more complexity in the judging process. - The thread shall be put to the sleeping set here but not in the scheduler, as the scheduler will not know the sleep duration. - `thread_awake(t_id)`: Transitions the thread with `t_id` from the `sleeping_set` to the `ready_queue`. - This macro is used by the thread routines to wake up a sleeping thread. - If the thread with `t_id` is not in the sleeping set, nothing happens. - It is guaranteed that there will not be any invalid `t_id` passed to this macro in a correct implementation of the thread routines. 6. **Termination** - `thread_exit()`: Ends a thread by calling `longjmp()` to switch to the scheduler, allowing another thread to run. - The following messages should be printed to the **standard output**: ```text thread [id]: exit ``` - Note that the thread's resources shall be freed by the scheduler, so just call `longjmp()` to switch to the scheduler. ## Scheduler Design in `scheduler.c` The scheduler is responsible for managing the execution of threads, handling context switching, and ensuring that all threads proceed according to their assigned states (ready, waiting, or sleeping). ### Components of the Scheduler 1. **Signal Handlers** - The prototype of the handler shall be `void sighandler(int signum)`. The function is registered as signal handler in `init_signal()`. - The scheduler uses two signals for thread management: - `SIGTSTP`: Used for manual context switching, triggered by pressing `Ctrl+Z` on terminal or the judge. - `SIGALRM`: Used for automatic context switching, triggered by the `alarm()` system call to enforce time slices. - Signal handlers switches to the scheduler. 1. **Scheduler Function** - The main function of the scheduler is to manage thread states, select the next thread to execute, and perform context switching. - **Thread State Management**: The scheduler moves threads between different states—`ready`, `waiting`, and `sleeping`—based on their conditions and requirements. - **Context Switching**: The scheduler performs context switching using `setjmp()` and `longjmp()`, saving the current thread's environment and jumping to the next thread's saved environment. 1. **Thread Queues** - The scheduler maintains multiple queues to track the state of threads: - **Ready Queue**: Holds threads that are ready to run and waiting for their turn. - **Waiting Queue**: Holds threads that are waiting for a resource, such as a read or write lock. - **Sleeping Set**: Tracks threads that are sleeping and waiting for their sleep duration to expire. 1. **Idle thread** - The idle thread is a special thread that runs when no other threads are ready to execute. - The scheduler will schedule the idle thread when there are no threads in the ready queue or waiting queue, but there are still threads in the sleeping set. - For example, consider a scenario where there is only one thread want to sleep for 10 seconds. The time slice is 1 second. The idle thread will be scheduled for 10 times. - To implement the idle thread, a thread with ID `0` shall be created. - The idle thread will be created by the scheduler right after the first time the scheduler called. - The thread routine for the idle thread is `idle()`, which will be discussed later. ### Signal Handling When a `SIGALRM` or `SIGTSTP` signal is received, the signal handler is invoked. - When a signal is received, the handler shall print the following message to the **standard output**: ```text caught [signal name] ``` - [11/30 Correction here](#Clarifications-and-Corrections) - The handler proceeds to call `longjmp()` to switch to the scheduler context. ### Scheduler Initialization On the first call to the scheduler, the following steps are performed: 1. Create the idle thread with ID `0` and the routine `idle()`. 1. Call `setjmp()` to save the scheduler's context in `schebuf`. ### Scheduler Workflow Including the first call, the scheduler shall perform the following steps: 1. **Reset the Alarm** - The scheduler resets the alarm to enforce the time slice for each thread. - Cancel the previous alarm, and set a new alarm for the time slice. 1. **Clearing the Pending Signals** - The scheduler shall clear any pending `SIGTSTP` and `SIGALRM` signals before proceeding. - This may be done by changing the signal handler of `SIGTSTP` and `SIGALRM` to `SIG_IGN`, then restoring the original handler. Refer to Extra Notes if you are interested in the reason. 1. **Managing Sleeping Threads** - The scheduler checks the `sleeping_set` to see if any thread's sleep duration has expired. - The sleep duration is decremented by `time_slice` if we jump to the scheduler from the signal handler. - Your implementation of the sleeping set should be able to handle this. - If a thread's sleep time is over, it is moved from the `sleeping_set` to the `ready_queue`, making it eligible for execution. - The order of threads moved from the sleeping set to the ready queue shall be the same as the order of threads' index. For example, if thread 1 and thread 2 are in the sleeping set, and them wake up at the same time, thread 1 shall be put to the ready queue before thread 2. 1. **Handling Waiting Threads** - The scheduler monitors the availability of resources and moves threads from the `waiting_queue` to the `ready_queue` when the resource becomes available. - If the head of the `waiting_queue` can acquire the resource, it is moved to the `ready_queue`. Repeat this process until no more threads can be moved. 1. **Handling Previously Running Threads** You may use the return value of `setjmp()` to distinguish where the jump comes from. - If the previous running thread comes from the signal handler, which must be triggered in `thread_yield()`, then the thread is not waiting for anything and shall be directly pushed to the ready queue. - Note that the idle thread, as a special thread, shall not be pushed to the ready queue. - If the previous running thread comes from a `read_lock()` or `write_lock()` call, then the thread is waiting for the resource and shall be pushed to the waiting queue. - If the previous running thread comes from a `thread_sleep()` call, then nothing to do, the thread is already in the sleeping set. - If the previous running thread comes from a `thread_exit()` call, then simply free the resources of the thread, including the TCB and the array of arguments, and do not push it back to any queue. 1. **Selecting the Next Thread** - The scheduler selects the next thread to run from the head of the `ready_queue`. The thread shall be popped from the queue. - If the `ready_queue` is empty, it checks if there are any threads in the `sleeping_set`. - If so, the scheduler schedules the idle thread. - If not, `scheduler()` shall free the resource of the TCB of the idle thread, then "returns". It actually returns to `start_threading()`, which will then return back to `main()`. 1. **Context Switching** - The scheduler performs context switching using the saved environment (`env`) of each thread. - The next thread's context is restored using `longjmp()`, which effectively transfers control to that thread. ## Routine Functions in `routine.c` The `routine.c` file contains the implementation of various thread routines that are executed by the user-level threads. The prototype of each routine is defined in `routine.h`. All of them will be in form like: ```c void routine_name(int id, int *args); ``` The routines will parse the arguments in their own way. There is no need to check the validity of the arguments, as the arguments will be guaranteed to be valid. `args` of each routine shall be freed in `scheduler()`, as mentioned before. ### Important Note on Judging To ensure that your program runs as expected during the judging process, please include a `sleep(1)` call before the ending `thread_yield()` or `thread_exit()` of each step or iteration in your routines. This will help synchronize the output and make it easier to verify the correctness of your implementation. ### Initialization Each routine shall start by calling `thread_setup(id, args)` at the beginning. ### Routine Descriptions Here are the routines that you need to implement in `routine.c`. #### Special Routine: Idle Thread The idle thread is a special thread that runs when no other threads are ready to execute. The idle thread is created with ID `0` and runs the `idle()` routine. No arguments are passed to the idle thread. Thus, you may pass `NULL` as `args`. The routine shall do the following: 1. Print the following message to the **standard output**: ```text thread [id]: idle ``` 1. Call `sleep(1)`. 1. Call `thread_yield()`. The thread shall repeatedly do the process forever. The thread routine do not call `thread_exit()` at the end, as the resources of the idle thread will be freed by the scheduler. #### First Routine: Fibonacci Number A positive integer $n$ is passed in as the argument, i.e., $n$ can be obtained from `args[0]`. Your program has to calculate the $n$-th Fibonacci number $F_n$. Specifically, we define $$ F_n = \begin{cases} 1, & \text{if } n \le 2 \\ F_{n - 1} + F_{n - 2}, & \text{otherwise} \end{cases} $$ - Compute the answer in exactly $n$ iterations. - Overflow is not a concern in this assignment under the given environment. For the $i$-th iteration, the routine shall do the following: 1. Calculate the $i$-th Fibonacci number. 1. Print out the following message to the **standard output**: ```text thread [id]: F_[i] = [F_i] ``` 1. Call `sleep(1)`. 1. Call `thread_yield()` or `thread_exit()`, depending on whether the calculation is finished. #### Second Routine: Plus and Minus A positive integer $n$ is passed in as the argument, i.e., $n$ can be obtained from `args[0]`. Your program has to calculate $\operatorname{pm}(n)$. Specifically, we define $$ \operatorname{pm}(n) = \begin{cases} 1, & \text{if } n = 1\\ (-1)^{n-1} \cdot n + \operatorname{pm}(n-1), &\text{otherwise} \end{cases} $$ - Compute the answer in exactly $n$ iterations. - Overflow is not a concern in this assignment under the given environment. For the $i$-th iteration, the routine shall do the following: 1. Calculate $\operatorname{pm}(i)$. 1. Print out the following message to the **standard output**: ```text thread [id]: pm([i]) = [pm(i)] ``` 1. Call `sleep(1)`. 1. Call `thread_yield()` or `thread_exit()`, depending on whether the calculation is finished. #### Third Routine: Enrollment for SP Course In this routine, you will simulate students attempting to enroll in the 2025 Fall SP course using threads. There are two classes, `pj_class` and `sw_class`, both held at the same time. Each student decides which class to enroll in based on: - Their level of desire to enroll in the class, and - The remaining spots (quotas) available in the class. There are four arguments passed to the routine: $d_p$, $d_s$, $s$ and $b$. The arguments are as follows: - $d_p$ and $d_s$ represent the student's desire to enroll in `pj_class` and `sw_class`, respectively. - $s$ represents the number of seconds a student will "sleep" at the beginning to simulate students who are oversleeping. - $b$ represents your best friend's ID, who you will try to awaken after you wake up. They can be obtained from `args[0]`, `args[1]`, `args[2]` and `args[3]`, respectively. The remaining spots in each class are represented by $q_p$ for `pj_class` and $q_s$ for `sw_class`. The corresponding variables, `q_p` and `q_w`, are defined in `main.c`, and declared as `extern` in `thread_tool.h`. They are protected by the read-write lock, `rwlock`. --- ##### Step 1 Print the following message to the **standard output**: ```text thread [id]: sleep [s] ``` Then, Call `thread_sleep(s)` to simulate oversleeping. ##### Step 2 Wake up your best friend with ID $b$ by calling `thread_awake()`. Acquire the read lock. Then, record the current values of $q_p$ and $q_s$ (remaining spots for both classes). Print the following message to the **standard output**: ```text thread [id]: acquire read lock ``` Call `sleep(1)`. Finally, yield. ##### Step 3 Release the read lock. Then, compute priority values $p_p = d_p \times q_p$ and $p_s = d_s \times q_s$ to decide which class the student will prioritize for enrollment. Print the following message to the **standard output**: ```text thread [id]: release read lock, p_p = [p_p], p_s = [p_s] ``` Call `sleep(1)`. Finally, yield. ##### Step 4 Acquire the write lock. Attempt to enroll in the class with the higher $p$ value. Break ties by enrolling in the class with the higher $d$ value. If the preferred class is already full at this time, enroll in the other class. Then, print the following message to the **standard output**: ```text thread [id]: acquire write lock, enroll in [class name] ``` - [11/30 Typo here](#Typos). The class name should be `pj_class` or `sw_class`. Decrease the remaining quota $q$ for the enrolled class by one. Call `sleep(1)`. Yield. - It is guaranteed that the $d$ values will not be equal. - It is guaranteed that the total number of threads executing this routine will not exceed the sum of $q_p$ and $q_s$ at any time. ##### Step 5 Release the write lock, then print the following message to the **standard output**: ```text thread [id]: release write lock ``` Call `sleep(1)`. Finally, exit. ## Compilation and Execution ### Compilation To compile the program, run the following command: ```bash make ``` This command will compile the source files and generate an executable named `hw3`. Object files files will be stored in the `obj` directory. To clean up the compiled files, run: ```bash make clean ``` This command will remove the `hw3` executable and the object file directory. ### Execution To run the compiled program, use the following command: ```bash ./hw3 time_slice q_p q_s \ routine_type routine_arg_1 [routine_arg_remaining ...] \ [routine_type routine_arg_1 [routine_arg_remaining ...]] ... ``` - Note that the order of the arguments is corrected. - `time_slice` specifies the number of seconds a thread can execute before context switching. - `routine_type routine_arg_1 [routine_arg_remaining...]` specifies the thread routines to be executed. Each routine is defined by its type and arguments. - `routine_type` is an integer from 1 to 3, corresponding to Fibonacci, Plus and Minus, and Enrollment for SP Course routines, respectively. - The number of `routine_arg`s depends on the routine type. - The number of threads will be determined by the number of argument group provided. It is guaranteed that the number of threads will not exceed `THREAD_MAX`. ## Constraints - $1 \leq \mathrm{the \ number \ of \ threads} \leq 100$. - Except for the idle thread. - $1 \leq q_s,\, q_p \leq 100$. - $\mathrm{The \ number \ of \ threads \ with \ routine \ 3} \leq q_s + q_p$. - $1 \leq \mathrm{time \ slice} \leq 10$. - For every thread routines `fibonacci` and `pm`: - $1 \leq n \leq 100$. - For every thread routines `enroll`: - $1 \leq d_p,\, d_s \leq 100$, where $d_p \neq d_s$. - $1 \leq s \leq 10$. - $b$ is a valid thread ID. ## Sample Input and Output ### Test Case 1 The time slice is 3 seconds, with `q_s` and `q_p` both set to 1. The thread routines are as follows: - Thread 1: `fibonacci` with `n` set to 3. - Thread 2: `pm` with `n` set to 3. - Thread 3: `fibonacci` with `n` set to 4. - Thread 4: `pm` with `n` set to 4. ```sh $ ./hw3 3 1 1 1 3 2 3 1 4 2 4 thread 1: set up routine fibonacci thread 2: set up routine pm thread 3: set up routine fibonacci thread 4: set up routine pm # Here, the scheduler will set up the idle thread. thread 0: set up routine idle thread 1: F_1 = 1 # send SIGTSTP here caught SIGTSTP thread 2: pm(1) = 1 thread 2: pm(2) = -1 # send SIGTSTP here caught SIGTSTP thread 3: F_1 = 1 thread 3: F_2 = 1 thread 3: F_3 = 2 # send SIGTSTP here caught SIGTSTP thread 4: pm(1) = 1 thread 4: pm(2) = -1 thread 4: pm(3) = 2 caught SIGALRM thread 1: F_2 = 1 thread 1: F_3 = 2 thread 1: exit thread 2: pm(3) = 2 thread 2: exit thread 3: F_4 = 3 thread 3: exit thread 4: pm(4) = -2 thread 4: exit ``` ### Testcase 2 The time slice is 3 seconds, with `q_s` set to ~~5~~ 6 and `q_p` set to ~~6~~ 5. The thread routines are as follows: - Thread 1: `enroll` with $d_p = 3$, $d_s = 2$, $s = 8$, and $b = 2$. - Thread 2: `enroll` with $d_p = 2$, $d_s = 3$, $s = 2$, and $b = 1$. ```sh $ ./hw3 3 5 6 3 3 2 8 2 3 2 3 2 1 thread 1: set up routine enroll thread 2: set up routine enroll thread 0: set up routine idle thread 1: sleep 8 thread 2: sleep 2 # Since no active thread now, the scheduler will schedule the idle thread. thread 0: idle # send SIGTSTP here caught SIGTSTP # Here, the scheduler will manage the sleeping set, deprecating the time # period of each thread in the sleeping set by `3`. # Hence, thread 2 wakes up and is put to the ready queue by the scheduler. # In this case, thread 2 is the only thread in the ready queue and # will be scheduled. # When thread 2 resumes its routine, it will awake its best friend thread `1`. thread 2: acquire read lock thread 2: release read lock, p_p = 10, p_s = 18 thread 2: acquire write lock, enroll in sw_class caught SIGALRM thread 2: release write lock thread 2: exit thread 1: acquire read lock thread 1: release read lock, p_p = 15, p_s = 10 thread 1: acquire write lock, enroll in pj_class caught SIGALRM thread 1: release write lock thread 1: exit ``` - [12/2 Typo here](#Typos). ### Testcase 3 The time slice is 2 seconds, with `q_s` set to ~~1~~ 2 and `q_p` set to ~~2~~ 1. The thread routines are as follows: - Thread 1: `enroll` with $d_p = 3$, $d_s = 2$, $s = 8$, and $b = 2$. - Thread 2: `enroll` with $d_p = 2$, $d_s = 3$, $s = 2$, and $b = 1$. - Thread 3: `pm` with $n = 5$. - Thread 4: `fibonacci` with n = ~~5~~ 2. - Thread 5: `enroll` with $d_p = 1$, $d_s = 2$, $s = 3$, and $b = 1$. ```sh $ ./hw3 2 1 2 3 3 2 8 2 3 2 3 2 1 2 5 1 2 3 1 2 3 1 thread 1: set up routine enroll thread 2: set up routine enroll thread 3: set up routine pm thread 4: set up routine fibonacci thread 5: set up routine enroll thread 0: set up routine idle thread 1: sleep 8 thread 2: sleep 2 thread 3: pm(1) = 1 # send SIGTSTP here caught SIGTSTP thread 4: F_1 = 1 thread 4: F_2 = 1 thread 4: exit thread 5: sleep 3 thread 2: acquire read lock thread 2: release read lock, p_p = 2, p_s = 6 caught SIGALRM thread 3: pm(2) = -1 # send SIGTSTP here caught SIGTSTP thread 1: acquire read lock # send SIGTSTP here caught SIGTSTP thread 5: acquire read lock thread 5: release read lock, p_p = 1, p_s = 4 # send SIGTSTP here caught SIGTSTP thread 3: pm(3) = 2 thread 3: pm(4) = -2 caught SIGALRM thread 1: release read lock, p_p = 3, p_s = 4 thread 1: acquire write lock, enroll in sw_class caught SIGALRM thread 3: pm(5) = 3 thread 3: exit thread 1: release write lock thread 1: exit thread 2: acquire write lock, enroll in sw_class thread 2: release write lock thread 2: exit thread 5: acquire write lock, enroll in pj_class thread 5: release write lock thread 5: exit ``` - [12/6, 12/11 Typo here](#Typos). These three sample testcases are the same as those in `sample_execution.sh`. ## Evaluation :::danger :warning: **Warning:** - Please strictly follow the implementation guidelines, or TAs' programs may not work successfully with yours and you will lose points. - If your submission includes unnecessary files, your grade will be capped at 6. - Please make sure your submission compiles and runs on CSIE workstations successfully. - Please strictly follow the output format, or you may not get the full credits. - Please use `ps -u $USER` or `htop -u $USER` to check for dangling processes. `kill` or `pkill` may be used to clean up your processes on a workstation. ::: ### Important Note on Output The output of the routines will be strictly compared to the expected output during the judging process. Please ensure that the output format matches the expected format exactly. Every messages should be printed to the **standard output**, with a newline at the end. ### Grading Policy - (2pt) Your `routine.c` is correctly implemented. - Your `routine.c` will be compiled with the provided other files. - (2pt) Your program with routine 1 and routine 2 can correctly output the expected results. - (2pt) Your program with routine 1, routine 2 and routine 3 can correctly output the expected results. - (2pt) Your program can correctly output the expected results with some additional routines. - Your program will be compiled with some routines provided by TAs. - The routines provided by TAs will use the thread library calls implemented by you. ## Extra Notes The following knowledge is not required for this assignment but is provided for interested students. - The reason why the design of our scheduler is not truly preemptive is that we cannot guarantee how our process will be scheduled by the OS. "The OS may decide to suspend our process and allocate CPU time to another process at any moment, which is beyond our control. Consider the following case: - We want to simulate that each step of a thread routine takes 1 second. We also set the time slice to 1 second. - We want the thread to be preempted after 1 second by the `SIGALRM` signal. Note that for the sake of authenticity, we don’t block the signal (more realistic preemptive scheduling). Therefore, we set the alarm to 1 second and sleep for 10 seconds. - There are two critical points here: - The OS may preempt our process at any time, so we don't know if the thread will finish its computation after 1 second. When the signal arrives, the thread may not be ready to be preempted. - The `SIGALRM` signal may not arrive exactly after 1 second. Even after 10 seconds, the signal may not arrive, although this is extremely unlikely. So the thread keeps doing its computation. - In the two cases above, the output of the program may not be as expected. - The ```c #define FUNCTION_LIKE_MACRO(arg) \ ({ \ int x = arg; \ \\ doing something... \ }) ``` syntax is a GCC extension called [Statement Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html). It allows you to use a block of code as an expression, which is useful for writing macros that return a value. A more common and older way to write this is to use a function-like macro with a `do { ... } while (0)` loop. - The `extern` keyword means that the decorated variable is actually declared elsewhere before, and this variable we declare here wants to point, or 'link', to that variable. You may want to check the [community wiki](https://en.cppreference.com/w/c/language/extern) for more information, especially the 'One Definition Rule' part. - Why don't we store local variables on the stack, just like usual functions? Or, let's say, what happens to the stack when we switch to another thread? Does `setjmp()` actually save the stack? You may want to check the [man page of `setjmp()`](https://man7.org/linux/man-pages/man3/setjmp.3.html) for more information. - Our usage of `setjmp()` and `longjmp()` is actually pretty bad. `longjmp()` to a function that has already returned is [undefined behavior](https://en.cppreference.com/w/c/program/longjmp), and [unpredictable and disastrous things are likely to happen](https://www.gnu.org/software/libc/manual/html_node/Non_002dLocal-Details.html). They should only be used for long-jumping **up** the call stack. - A very weird `char padding[64]` variable is defined in the `spawn_thread()` function in the provided `main.c`. This is to prevent the stack from being corrupted by the `setjmp()` and `longjmp()` functions. Consider the following scenario: - We call `thread_create()` directly in the `main()` function. - The stack frames of each thread are all allocated right after the `main()` function's stack frame. - The size of the stack frames of `main()` increases during the runtime of the program. - Even though the compiler fixes the stack frame size of `main()` at compile time in most cases, it is not guaranteed but just a common optimization. - The stack frames of a thread created earlier may overlap with the stack frames of `main()`. - When we `longjmp()` back to the thread, the stack frames of `main()` may be corrupted. - It is very likely that after return to `main()`, somethings unexpected will happen, and the program may crash. - Why is the `padding` variable solved this problem? Hint: we warp the `padding` variable and all `thread_create()` calls in a function. - The corrupted stack is also the reason why we implement most of our thread library as macros. What do you think will happen if you define them as functions instead? How about inline functions? - The behavior of setting `SIG_IGN` to a blocked signal is defined in [The Single Unix Specification](https://pubs.opengroup.org/onlinepubs/7908799/xsh/sigaction.html) > Setting a signal action to SIG_IGN for a signal that is pending will cause the pending signal to be discarded, whether or not it is blocked. , but not actually in the manual pages of `sigaction` and `signal`, sections 2, 3 and 7 (at least TAs cannot find it QQ). However, it is mentioned in the [GNU C Library manual](https://www.gnu.org/software/libc/manual/html_node/Basic-Signal-Handling.html#index-SIG_005fIGN) (TAs spent a lot of time on finding this). You may also want to check the function `sigqueue_free_ignored()` in the Linux kernel [source code](https://github.com/torvalds/linux/blob/master/kernel/signal.c). ## FAQ - **Q: Can I modify the provided Makefile?** A: Yes, you can modify the Makefile to add more rules or add GCC debugging flags for your convenience. However, the judging environment will use the default Makefile, so your changes will not be adopted. ### 12/4 Update - **Q: What happen if there are only two threads in the waiting queue that both want to acquire the write lock? And currently, the write lock is available.** A: The scheduler will add these two threads to the ready queue in sequence, regardless of whether a thread can acquire the lock in the future when it is scheduled. In our setup, the scheduler only knows whether the lock is currently available, without considering the future action of threads. Each thread will attempt to acquire the lock when it returns to the `lock()` function. If the lock is unfortunately not available then, the thread should return to the waiting queue again. The same logic applies to `read_lock`. ### 12/1 Update - **Q: What happen if two `SIGTSTP` signals are sent to the program, while no `thread_yield()` is called between them?** A: `SIGTSTP` signal simulates that you have not run out of your time slice, but someone else wants you to yield as soon as possible. Therefore, even though two `SIGTSTP` signals are sent, the program shall behave as if only one `SIGTSTP` signal is sent. (Moreover, for POSIX reliable signals, only one signal instance is delivered after the signal is unblocked even if the signal is sent multiple times.) - **Q: Is there any requirement for the order of operations in the scheduler?** A: The order of operations in the scheduler is strictly defined. For all the operations listed in the spec, you should follow the order of operations as described. - **Q: If no any `SIGTSTP` caught when `idle thread` is scheduled, will it completely print `thread [id]: idle` for `time_slice` times even though there are threads which sleeping duration is less than `time_slice`?** A: Yes. In the [assignment specification](#Routine-Descriptions), we asked you to print `thread [id]: idle`, `sleep(1)` and `thread_yield`, which do not contain any operation about the check to sleeping set. Imagining that the `time_slice=3` and there is thread with sleeping duration 1, the `idle thread` will still print the idle message three times if no any `SIGTSTP` is caught.