In Lab2 you will enhance the simple, static process scheduler of Xinu so that it implements scheduling policies employed by modern operating systems aimed at achieving "fair" share of CPU cycles for a population of I/O- and CPU-intensive processes. This approach is also referred to as time-share scheduling. The scheduling invariant -- when invoked, the scheduler chooses a highest priority ready process to run (and round robin among equal priority processes) -- remains intact, however, the scheduler dynamically (i.e., changing over time) adjusts the priority values and time slices of processes to achieve a desired objective (such as fairness).

You will evaluate correctness and performance of your enhanced process scheduler by creating test workloads -- mixed populations of CPU- and I/O-intensive processes -- that will serve as a benchmark for assessing the "goodness" of your scheduler implementation. The TAs will use additional benchmark workloads to further gauge the performance of your kernel modification.

1. Kernel Monitoring and Classification of Processes

As discussed in class, a dominant paradigm of "fair" scheduling in operating systems such as UNIX and Windows (and until recently Linux) has been the concept of classifying processes -- based on their run-time behavior -- into CPU- and I/O-intensive processes which is then used to adjust their priorities and time slices dynamically. For example, a CPU-intensive process tends to hog the CPU, not relinquishing it voluntarily (through blocking system calls), which requires preemption of the process by the scheduler so that the shared CPU is not monopolized by a CPU-intensive process. Preemption is effected by the clock interrupt handler (see clkint.S) which keeps track of the time slice consumed by a process (part of the clock interrupt handler's bookkeeping activity) and calls the scheduler (see resched.c) when the time budget (global variable preempt) is depleted (i.e., reaches zero).

In contrast, an I/O-intensive process tends to make system calls to engage a kernel's I/O services. In the case of a read related system call (e.g., reading from an I/O device), if data from an I/O device (e.g., web server waiting on client request packets on a gigabit-per-second Ethernet card) is not available, the default agreement between a process making the read related system call and the kernel is that the process in question is put in a blocking state (recall that only ready processes are eligible to be context-switched in and use the CPU) and context-switched out so that a ready process may utilize the CPU. When the event (e.g., packet arrival) that the process is blocking on eventually occurs, the kernel will unblock the process and put it in the ready state so that the scheduler, when invoked next in the future, will consider the unblocked process when deciding which process to run next.

Since I/O-intensive processes often relinquish the CPU voluntarily through blocking system calls whereas CPU-intensive processes hog the CPU and must be "forcefully" preempted, it makes intuitive sense to assign I/O-intensive processes higher priorities relative to CPU-intensive processes. That is, when a blocked I/O-intensive process becomes unblocked (recall that such unblocking events are processes by the kernel's interrupt service routines), it is desirable that the kernel's scheduler is invoked which then preempts a CPU-intensive process that is currently occupying the CPU -- by virtue of the "highest priority process first rule" -- and context-switches in the unblocked I/O-intensive process, which, hopefully, will promote fairness between CPU- and I/O-intensive processes.

As to differentiated assignment of time slices to CPU- and I/O-intensive processes, giving larger time slice budgets to CPU-intensive processes has been a preferred strategy although the Linux scheduler, until recently, followed the opposite approach. We will follow the "large quantum to CPU-intensive and low quantum to I/O-intensive process" assignment policy.

Implementing UNIX Solaris process classification and time-share (TS) scheduling in Xinu

Classification of processes based on their observed run-time behavior must be done by the kernel efficiently so that the scheduler's footprint is kept low. A very simple strategy, for example, used by UNIX Solaris, is to classify a process based on its most recent scheduling related activity: (a) if a process consumed all of its time slice and needed to be preempted by the clock interrupt handler then the process is viewed as CPU-intensive; or (b) a process voluntarily relinquishes the CPU by making a blocking system call (e.g., I/O or sleep) in which case the process is viewed as I/O-intensive. In both instances, the scheduler will change the process's priority value. In the case of (a), the process is demoted by reducing its priority. In (b), the process's priority is bumped up.

After this change in priorities, the scheduler picks a highest priority process from ready processes to run (round-robin if there are 2 or more highest priority processes). As to the time slice, in the case of (a), the quantum is increased to reflect the CPU-intensive behavior of the process. In (b), the opposite occurs.

As to the exact quantitative change in priority and quantum values, use those employed by Solaris, a production grade UNIX kernel:

• Solaris UNIX dispatch table: TS

struct ts_ent {
  int ts_tqexp;         // new priority: CPU-intensive (time quantum expired)
  int ts_slpret;        // new priority: I/O-intensive (sleep return)
  int ts_quantum;       // new time slice
};
extern struct ts_ent tstab[];

struct ts_ent tstab[60];

2. Xinu Kernel Modification: Relevant Modules

As discussed in class, a kernel is broadly divided into two major parts called halves: an upper half that deals with top-down system calls and a bottom half that deals with bottom-up interrupts. Xinu's scheduler resched() is invoked bottom-up by the clock interrupt service routine clkint in clkint.S when a process's quantum is depleted. We noted that Xinu's scheduler resched() expects the caller to set proctab[currpid].prstate to the desired future state of the process before it is called.

For example, when preempted by clkint, the current process was in the midst of using the CPU, hence its intended future state is PR_CURR. On the other hand, if resched() is called from sleepms() then its desired next state is PR_SLEEP. Since we haven't studied inter-process communication and device I/O yet, for the purposes of Lab2 a process being "I/O-intensive" will mean that it calls sleepms a lot. That is, what's important is that a process relinquishes the CPU voluntarily.

Due to Xinu's calling convention of resched(), to implement Solaris's TS scheduling policy in Xinu there is no need to modify the callers clkint.S and sleepms(). That is, the essential scheduling code modification (e.g., TS table initialization is done in initialize.c) can be done in resched(). Carry out this kernel modification so that Solaris's TS scheduling policy is supported by Xinu.

Important: Before performing any kernel modification, please back up the files (even intermediate files to guard against accidental deletions) so that you can go back to a previous code base and recover more easily from human errors in the development process.

3. Benchmark Evaluation of TS Scheduling Performance (1, 2 and 3: 200 pts)

To evaluate how well the TS scheduling implementation in Xinu achieves fairness, we will consider the following three test case scenarios.

• All processes are CPU-intensive. In the first test case, create 6 processes that run the same program cpuintensive(). Put the code of cpuintensive() in a separate file cpuintensive.c. Assign the same initial priority 20 when calling create() from main(), and set QUANTUM in kernel.h to the corresponding value in Solaris's TS table. The code structure of cpuintensive() should follow:

  for (i=0; i<LOOP1; i++) {
    for (j=0; j<LOOP2; j++) {
      // insert code that performs memory copy (slow) and/or
      // ALU operations (fast)
      // note: this loop consumes significant CPU cycles
    }
    // using kprintf print the pid followed the outer loop count i,
    // the process's priority and remaining time slice (preempt)
  }
  

  Note, although 6 instances of the same program are executed, the different process IDs of the 6 processes allows observing their individual progress toward completion -- which requires CPU allocation -- from the output. Printing dynamically changing priority and time slice values -- accessible from app process cpuintensive() in Xinu since isolation/protection is not implemented -- allows monitoring how resched() (and clkint.S for preempt) adapts the scheduling variables of the 6 processes over time.
  
  To prevent priority demotion to decrease a process's priority down to 0 which lumps it together with the Xinu's null process (default priority 0) -- recall the null process should only run when there are no other ready processes in the system -- create your own solution that ensures the null process does not steal CPU cycles from ready processes and describe it in a separate write-up, Lab2Answers.pdf. In the write-up, discuss the output that you observe and whether the output values indicate fair sharing of CPU cycles by the 6 processes. You will need to experiment with different values of LOOP1 and LOOP2 to induce CPU sharing (via context switching) and resultant output that can be easily interpreted for gauging your implementation of TS scheduling performance.


• All processes are I/O-intensive. Follow the same steps as above but replace cpuintensive() by iointensive() (in iointensive.c) which has the same code structure as cpuintensive() except that the code in the inner loop (for ALU and memory copy) is replaced by a single call to sleepms(). By varying the argument of sleepms() you can vary the degree to which iointensive() is prone to blocking and voluntarily relinquishing the CPU. In Lab2Answers.pdf, include a discussion of the results observed and your assessment of fairness by the TS scheduler.


• Half-and-half. Create 6 processes where half execute cpuintensive() and the other half execute iointensive(). In the first part of the evaluation, under this mixed workload of CPU- and I/O-intensive processes, determine if the 3 CPU-intensive processes -- among themselves -- achieve equal sharing of CPU cycles as indicated by the output. Do the same for the 3 I/O-intensive processes. The less straightforward question is whether there is "fair" sharing of CPU cycles between CPU- and I/O-intensive processes. This question is inherently open-ended. TS scheduling assigns higher priorities to I/O-intensive processes over CPU-intensive processes, allowing them to preempt CPU-intensive processes whenever they become unblocked (in our case, wake up from sleeping). Since iointensive() processes sleep, over time, they will consume less CPU than cpuintensive() processes, but by choice (they want to sleep). Thus one meaningful way to determine whether TS scheduling is doing its job properly is to check whether iointensive() processes, upon becoming unblocked, immediately preempt cpuintensive() processes.
  
  Waking up sleeping processes -- changing process state from PR_SLEEP to PR_READY and moving a process from sleep queue to ready queue -- is another task carried out by the clock interrupt routine clkint.S. If implemented correctly then for larger sleep times, say 500 msec, the three iointensive() processes should wake up at approximately similar times, print their output, sleep for another 500 msec, then wake up close together and print, then repeat this cycle until the outer loop completes. For example, if the outer loop is 10 (there is no inner loop in iointensive()), then after approximately 5 seconds the three I/O-intensive (i.e., sleep-intensive) processes should complete. Experiment with the benchmark parameters and discuss your findings in Lab2Answers.pdf.

4. Starvation Issues (120 pts)

Although the TS scheduler implemented in Xinu is a real-world scheduler (Solaris and other variants of UNIX and Windows), the benchmark workload is highly simplified since processes are assumed to be of two extremes: CPU-intensive or I/O-intensive. In real-world workloads, we are faced with processes that are at times CPU-intensive and at other times I/O-intensive during the course of their execution. The efficient but simplistic mechanism employed by Solaris to dynamically adjust priorities based on the most recent scheduling related behavior of processes (i.e., making blocking system calls or using up their time slice) can lead to undesirable consequences, the most important of which is starvation. Starvation is the phenomenon where a ready process does not receive CPU cycles for a prolonged period of time. When this is intentional -- e.g., the null process is not supposed to receive cycles if there are ready processes to run -- then there is no problem. However, in some instances, processes can starve when this was not intended by the scheduler of the kernel.

For example, consider a process that executes code that is sometimes CPU-intensive, at other times I/O-intensive. Suppose such a program, call it hybridprocess() (in hybridprocess.c), has the characteristic that it consumes CPU cycles but just before depleting its quantum, makes a very brief sleepms() system call (since the sleep resolution is in milliseconds, say, with argument 1 msec). The kernel will treat this process as I/O-intensive at that moment since it voluntarily relinquished the CPU (however briefly) before clkint.S had a chance to preempt it, which bumps up its priority. When hybridprocess() becomes ready after a brief sleep period, it finds itself in an advantageous position compared to a cpuintensive() process due to its increased priority. The question is: when we have 3 processes of type hybridprocess() and 3 of type cpuintensive(), is it possible for the hybrid processes to garner a lion's share of the shared CPU cycles so that the 3 CPU-intensive processes are nearly starved (or are getting a much smaller share)?

Engineer an instance of hybridprocess() such that three of them running concurrently with three instances of cpuintensive() processes will receive a significantly larger share of the CPU under your implementation of TS scheduling. Discuss your results in Lab2Answers.pdf.

Propose and implement a solution (but different from that used by Solaris) that attempts to mitigate the starvation problem. Your aim is to come up with an improved method that is more accurate than the simple classification carried out by Solaris (Section 1) but remains lightweight (i.e., has small overhead). For example, incorporating CPU consumption behavior of processes over a time window of the recent past when performing classification and dynamic priority assignment may help improve accuracy (and ultimately fairness). Describe your solution in Lab2Answers.pdf. Using the same 3+3 benchmark as above, show that your solution significantly improves fairness of TS scheduling. Discuss your results and findings in Lab2Answers.pdf.

5. Support for Real-time Scheduling (80 pts)

Most operating systems today (e.g., UNIX/Linux and Windows) support real-time processes by allowing users with root account privilege to run an app as a real-time (RT) process. Inside a kernel, a RT process is one that is assigned a priority range higher than all the TS processes. In our extension of Xinu, let the RT priority range be 60, 61, 62, ..., 75. That is, 16 priority levels above TS are supported by the kernel for RT processes. The create() system call need not be modified since specifying a priority in the 60-75 range in the argument is tantamout to requesting that the Xinu kernel treat the created process as being of type RT. However, Xinu's modified scheduler that implements TS scheduling needs to be changed so that processes with priorities 60-75 are not treated as TS processes. That is, RT process priorities remain fixed.

Note, since all processes, TS and RT, obey the "highest priority process first rule," if an RT process is created that never blocks (e.g., sleeps or waits for I/O), the process ends up monopolizing the CPU and all TS processes starve. This is the reason why in today's operating systems root account privilege is required to execute RT processes.

Make code changes to the Xinu kernel such that in addition to TS, Xinu supports RT processes. The code base before implementing the RT support can be the Solaris TS implementation or the one that implements an improved method in Problem 4. Test the RT kernel support by running a program rtprocessnoslp() with priority 65, along with a 3+3 mixed workload of CPU- and I/O-intensive processes in Problem 3. Create/resume these 6 processes before the RT process rtprocessnoslp() which follows the same structure as cpuintensive() (you can use the same code). Repeat the experiment with an RT process, rtprocessyesslp(), that follows the structure of iointensive() (same code may be used).

What happens if, in addition to the 3+3 mixed workload, you attempt to run concurrently rtprocessyesslp() and rtprocessnoslp() where rtprocessyesslp() is created with priority 70 and rtprocessnoslp() is created with priority 65? (Note that all processes are created by the main() process in our benchmark tests.) What happens in the test when the order of creation of rtprocessnoslp() and rtprocessyesslp() is reversed? Discuss your results and findings in Lab2Answers.pdf.

Important: Please comment your code changes in Xinu such that (a) where changes are made is highlighted, and (b) what changes are made is conveyed.

Turn-in Instructions

Electronic turn-in instructions:

        i) Go to the xinu-spring2013-x86/compile directory and do "make clean".

        ii) Go to the directory of which your xinu-spring2013-x86 directory is a subdirectory. (NOTE: please do not rename xinu-spring2013-x86, or any of its subdirectories.)

                e.g., if /homes/jsr/xinu-spring2013-x86 is your directory structure, go to /homes/jsr

        iii) Type the following command

                turnin -c cs354 -p lab2 xinu-spring2013-x86

Important: You can write code in main.c to test your procedures, but please note that when we test your programs we will replace the main.c file! Therefore, do not put any functionality in the main.c file. ALL debugging output should be turned off before you submit your code. Please put Lab2Answers.pdf in the system/ directory.