CS 241: System Programming

Machine Problem 2
Signals, Timers, and Scheduling

Deadline: Monday, 27 February, 4:00pm
(electronic submission)

Solution: Makefile, sched_policy.c, sched_policy.h, thread.c, thread.h, scheduler.h, scheduler.c, (mp2_defines.h, pqueue.h, pqueue.c, main.c)
Entire solution: mp2.tar.gz,

Description	Note: Check out the clarifications at the bottom regularly This MP consists of three parts. Read through the whole document before beginning, especially since we are supplying some code files for your benefit. The goal is to help you understand (1) basic thread/process scheduling policies, (2) how to simulate scheduling using timers and signals, and (3) how to evaluate the performance of your program. You will first implement basic thread scheduling policies. Then, using these policies, you will write a program to perform thread scheduling. Lastly, you will evaluate the overall performance of your program by keeping track of how long each thread is idle, running, etc. Note: this MP may seem large at first, but each of these functions is relatively small. Additionally, we highly recommend good use of your R&R texbook since many of these functions and methods are trivialized (implemented for you) by the code provided in this book. Throughout the MP, pay attention to the suggested readings. Part 1: Round-Robin & Priority Scheduling Policies First, you are to design two scheduling policies: Round-robin Scheduling & Priority Scheduling, as described in Tanenbaum 3rd edition, starting on page 103. Each function described below should perform according to the currently set scheduling policy. To accomplish this, you will write two files: `sched_policy.c` & `sched_policy.h` For maintaining and coordinating the scheduling policy, use the `SchedPolicy` enumeration defined in the provided `mp2_defines.h` Your scheduler should consist of the following functions: `void InitializeSchedPolicy(enum SchedPolicy policy)` This function should initialize/create an empty queue and set the current scheduling policy. Appropriate parameter values are: `SCHED_ROUNDROBIN` and `SCHED_PRIORITY` `threadT* GetNextThread()` This function implements the actual scheduling algorithm as far as the scheduler is concerned. This function returns the appropriately scheduled next thread. This function should return a pointer to a `struct Thread` corresponding to the next thread to run. The resulting thread depends on the current scheduling policy. NOTE: `threadT` is a `struct` defined in `thread.h` `int ShouldISwitch(threadT* currentThread, threadT* newThread)` This function should only be called when a new thread is created (under priority scheduling) to see if it should preempt. This function decides whether the current thread should be preempted by the new thread. Return `0` if they should not switch (meaning either it's not priority scheduling or the new thread has a lower priority than the current thread). Return `1` if they should switch. Note: Higher priority is a lower number. `void SetThreadReady(threadT* threadID)` This function adds the specified thread to the ready list. For simplicity, we recommend that the list remains sorted so that the thread at the front of the list is the next one to run. NOTE: You should put a mutex around any operation that modifies the `pqueue` You should store a pointer to your queue and store the current scheduling policy in this file (See clarification #4). We are providing a slightly modified version of the MP0 solution, which you are welcome to use for your queue maintenance. It may also be useful to add a print function allowing you to print out your queue for debugging purposes. Remember the `pqueue` already implements a print function. The primary purpose of these two files is to provide the mechanism for maintaining and updating the thread queue - corresponding to the desired scheduling policy. Part 2: Scheduler Now, you are to implement the scheduler. To accomplish this, you will write two files: `scheduler.c` & `scheduler.h` These files contain the functions the main program will use for initializing the scheduler and starting thread processing. Be sure to read R&R section 13.5, starting on page 473, for information and examples of thread signaling. Understand how to use the `pthread_kill` function. Note the examples in Programs 13.14 and 13.15. NOTE: We have now supplied a file, `mp2_defines.h`, to make the assignment more uniform and easier to grade. Use the constants that are defined there. For this part, you will implement the following functions: `void InitializeScheduler(enum SchedPolicy currentPolicy, int timerQuantum)` This function should initialize the scheduling policy, store the timer interval quantum, and setup a signal interrupt for the timer. `timerQuantum` should correspond to the number of seconds each thread will be allowed to run under Round-Robin scheduling. (Under priority scheduling, the higher priority thread should run until finished - unless preempted by a higher-priority thread). You will need the timer to keep checking the bursttime for completion under the priority scheduling condition as well. For simplicity, you can wait until this timer goes off before checking for preemption (delayed preemption, but this is only an MP). Therefore, you can use the same timer quantums for both scheduling policies, but you do not necessarily switch threads for the priority scheduling. `void* RunThreads(void* args)` The main program should create a thread using this function. The arguments to this thread should be a `struct` pointer containing two integers. The first integer specifies the initial number of threads (INITIALTHREADNUM(5)) to start running before starting the scheduler. The second integer specifies the total number of threads to run (TOTALTHREADNUM (20)). Then, this thread should initialize and handle the timing and scheduling for the system (i.e. it must be setup to handle the `SIGNAL_TIMER(SIGALRM)` events that come from the timer. Next this function should set the appropriate signal masks for blocking the appropriate signals as described in the signal handler sections. Then, this function should create initial threads using the `Fork()` defined in `thread.c` (`INITIALTHREADNUM` separate calls to `Fork()`). The `Fork()` function takes, as parameters, the choice of thread function, the thread priority, and the burst time for the thread. `Fork()` is simply a wrapper for creating the thread functions we have provided. Generate the bursttimes and priorities randomly, where the bursttime should be between `BURSTMIN` and `BURSTMAX`, and the priorities should be between `PRIORITYMAX` and `PRIORITYMIN`. (You can use: `random() % (BURSTMAX-BURSTMIN) + BURSTMIN` for the new burst time and `random() % (PRIORITYMIN-PRIORITYMAX) + PRIORITYMAX` for new priority). Once the initial threads are started, this function should call `timer_settime` to start the timer. Finally, this thread should sleep for a random period of time (`random() % (BURSTMAX-BURSTMIN) + BURSTMIN`), and when it wakes up, it should create and schedule a new thread - again with the random attributes specified above. Keep doing this until the specified total number of threads is reached (TOTALTHREADNUM). NOTE: You must use `nanosleep()` instead of `sleep()` to avoid conflicts with the `SIGALRM` signals. Timing: You will also need to implement functions for initializing a timer and for handling interrupts from the timer. The timer should send a `SIGNAL_TIMER(SIGALRM)` signal in intervals corresponding to the initialized timer interval value. For the timer, you should use a POSIX:TMR interval timer. See Programs 9.11 & 9.12 in R&R (page 328-329) for examples on how to setup these types of timers and the corresponding interrupt described below. You will need to create a function handler using `sigaction()` that waits for the SIGALRM signal. SIGALRM's will by default go off when the timer you create has expired. Create the timer with `timer_create()` using `CLOCK_REALTIME`, and then set its time with `timer_settime()`. This timer should go off repeatedly, corresponding to the timer quantum specified when initializing the scheduler. When the timer goes off, if the policy is Round-Robin, the scheduler should suspend the currently running thread, update its remaining burst time, and tell the next thread to resume its operation using signals. For priority scheduling, you should check the remaining burst time and update it. If it is finished, you should resume the next thread in the queue. If this thread should be preempted, you should start the appropriate thread. For this signaling, you are welcome to use any appropriate interruptable signals. Use `SIGNAL_SUSPEND(SIGUSR1)` & `SIGNAL_RESUME(SIGUSR2)` for the corresponding signals. You should use `pthread_kill` to send the appropriate signals to the corresponding threads. Additionally, when the thread has used up its burst time, the scheduler should send it a signal to exit. Use the `SIGNAL_CANCEL(SIGTERM)` signal for this. You will want to 'handle' this signal in your threads as well. For simplicity, if a thread will use up its burst time within the timer interval, just let it run until the timer signals again (or it's preempted). NOTE: You are welcome to implement any helper functions you wish. Modify the given thread code: To finish your scheduler, you need to modify `thread.c` (and `thread.h` if desired). You will need to modify each of the thread functions in `thread.c` (`thread_func0` through `thread_func3`) so that these functions immediately suspend the thread, waiting for a resume signal from the scheduler. Look at Section 13.5.2 on page 474 in R&R for use of `pthread_sigmask()` and Section 8.5.3, on page 282, for help on `sigwait()`. You will need to use `sigwait()` to force the thread to suspend itself and `pthread_sigmask()` to ensure that the desired thread blocks or unblocks signals as appropriate. You will need to modify `Fork()` to correctly fill the newly created thread `struct` with the appropriate values, including getting the current time for setting the `arrivalTime` of the struct. Also, initialize any signal handling pertaining to all threads. You will also need to add a signal handler to `thread.c` to catch and handle suspend signals and exit from the scheduler. Remember that suspended threads must wait for a resume signal from the scheduler, so remember `sigwait()`. You will want to write a handler for the exit signal (`SIGNAL_CANCEL`) to allow you to perform additional measurements and terminate the thread - which would otherwise run indefinitely. (eg after a `sigaction` for `SIGNAL_CANCEL` and `SIGNAL_SUSPEND`, make sure to unblock that signal; before a `sigwait` for `SIGNAL_RESUME`, make sure to block that signal.) In order to monitor what is happening, you should print messages each time a thread is running, suspended, or resumed (include at least the thread ID). Additionally, print something at the beginning of every scheduler call stating when it enqueue or dequeues a thread from the queue (again along with any corresponding information about the thread). Last, print a message when the scheduling timer goes off. We will try to provide some sample output to help, but the exact output formatting is not important. Note: If you use clock timing functions, you may need to include the `-lrt` linking option. Part 3: Evaluation You will include the evaluation results in your README file. Look at examples such as Example 9.2 on page 309 in R&R. This demonstrates how to measure function times using `clock_gettime()`. Using `clock_gettime()`, record the times immediately before suspending and immediately after resuming. Use this information to compute the following information: Average wait time, total wait time, average compute time, and total compute time. (Total compute time should be equal to the bursttime unless the thread was allowed to run over - corresponding with the scheduler timer). Generate these calculations across 3-5 runnings of the program with the same settings passed in to the functions from main(). Using this information, compute the average system wait time and average system compute time (averaged over all threads). Then, compute the average turn-around time for all threads (as presented in discussion section slides for week 5 (Discussion section 4)). Finally, create a simple table demonstrating the correlation between thread priority and wait times. For this evaluation part, also use the `clock_gettime()` function as described on page 309 of R&R, and see Example 9.2.
Given Code	`pqueue.h, pqueue.c`: These files contain a slightly modified version of the MP0 priority queue. Each node in the queue stores a `struct Thread` as declared in `thread.h`. Feel free to use this for your queue or to write your own data structure. Note: if the priorities are all the same, the `SortedInsert` function inserts new nodes after previously inserted nodes. `thread.h, thread.c`: These files contain the `struct Thread`, which can be stored within the supplied priority queue. Additionally, these files contain the implementation of several thread functions, which you are to use. You will modify these files to support scheduling as described above. NOTE: We have modified the `thread.c` code slightly since the initial release - to provide more interesting thread functions. As posted on the newsgroup, if you had added code previously, just copy and paste them into the new code. `main.c`: Simply initializes and starts the scheduler. Modify this code to try different experiments and to change the scheduling policy. NOTE: Make sure you have a recent version of this file as well. `mp2_defines.h`: Definitions you can use for your code. This way, we can keep the signals more uniform and provide more uniform random functions as well. Download the given code here: Given Code
Deliverable	This assignment is designed to be completed via pair programming. You are encouraged to form a group of 2, although you may elect to work alone. Newsgroup communication about general issues and any given code is allowed. Please post any questions about the given code on the newsgroup. You can use the CSIL Linux machines to do the assignment. You are strictly required to use C. For the first part, create `sched_policy.h` and `sched_policy.c`. For the second part, create `scheduler.h` and `scheduler.c`. Also, modify `thread.c` and `thread.h`. Finally, create a makefile which builds 1 executable named `main`. Your makefile should also have labels for compiling each `.o` file as well (`sched_policy.o, scheduler.o, thread.o, main.o, pqueue.o`) Create a README file as well, detailing any problems encountered during program design or execution. Include in the README the following information MP number and title Your names and netids How you split the work for the entire MP Results from the Part 3 evaluation
Handin	Use Compass to electronically handin those 8 files (`makefile, sched_policy.h, sched_policy.c, scheduler.c, scheduler.h, thread.c, thread.h, README`) under the "MP2 Handin" assignment. This must be done before 4pm on Monday, 27 Feb. Every hour late is minus 2% credit. No submissions accepted after 4pm on Tuesday, 28 Feb.
Grading Criteria	Scheduling policies (sched_policy.h & sched_policy.c) – 25% Scheduler (scheduler.c & scheduler.h) – 45% Evaluation & README – 25% Makefile & submitting – 5%
Clarifications	Exit everything at any time that there are no processes left to schedule (IsEmpty(queue) == 1) You may need to add a InsertAtTheEnd() function for pqueue, if you change pqueue.c/h, submit it Since nanosleep is in the same thread as the scheduler, pay attention to the remaining time value (2nd parameter). Restart nanosleep with the time left value if nanosleep returned a value other than 0. Place the queue pointer and current scheduling policy variables in sched_policy. Scheduler yielding between suspend-resume provides better results You can modify the thread struct as desired (to store any extra information) Sample output: Round-robin, Priority Part 3: You can get the times in scheduler.c instead of the thread handler functions to allow access to the thread pointer. This MP attempts to create a user space scheduler. As a result there are certain conditions which need not be met as tightly compared to a kernel space scheduler. Immediate suspension of a worker thread is not required, but the thread should stop as quickly as it can (ie the next loop iteration). This is only an acceptable solution if the student goes a step further to ensure that no two worker threads will ever be executing at the same time. This will require more use of sychronization primitives. Great point loss will occur when there is any evidence of worker thread overlap (ie '++++-+-+----' in output).