In this lab you will implement different process scheduling policies in Xinu that will avoid starvation of processes and improve CPU load balancing among I/O- and CPU-bound processes. At the end of this lab you will be able to explain the advantages and disadvantages of the scheduling policies implemented in Xinu.

Starvation occurs in Xinu when we have two or more processes eligible for execution that have different priorities. The scheduling invariant in Xinu assumes that at any time, the highest priority process eligible for CPU service is executing, with round-robin scheduling for processes of equal priority. Under this scheduling policy, the processes with the highest priority will always be executing. As a result, all the processes with lower priority will never get CPU time. You may test this condition by running test1.c and test2.c. For ease of discussion we call the set of processes in the ready list and the current process as the eligible processes.

In the following, we will assume that scheduling policies are process-specific. That is, each process may have its own policy that determines how its priority should be set when resched() is invoked.

1. Aging Scheduler 

The first scheduling policy is an aging scheduler. On each rescheduling operation, the scheduler increases the priority of all ready processes in the AGINGSCHED scheduling class by a constant number. This avoids starvation as a ready process in the AGINGSCHED class can be passed over only a finite number of times before it achieves maximum priority.

Implementation (hints):

Each AGINGSCHED scheduling class process has an initial priority that is assigned to it at process creation and is changed via the call to chprio(). Every time the scheduler is called it takes the following steps.

• The priority of the current process, if it is a AGINGSCHED scheduling class process, is set to the initial priority assigned to it.
• The priorities of all ready processes in the AGINGSCHED class are incremented by 1.

2. Proportional Share Scheduler 

The second scheduler implements a proportional sharing policy. First the policy will be explained and then we will give pointers as to how to adapt this to XINU.

Every process in the PROPORTIONALSHARE scheduling class has a scheduling parameter called rate. In the following, we will assume that all the processes in question belong to the PROPORTIONALSHARE scheduling class. For a process i let us denote the rate as Ri. Every process i has a priority value Pi. Initially, all the processes start with a priority value 0 (Pi = 0). Whenever a rescheduling occurs, the priority value Pi of the currently running process is updated as follows,

where t is the CPU ticks consumed by the process since it was last scheduled. Ri is a percentage value and takes values between 0 and 100.

Now the scheduler schedules an eligible process with the smallest Pi. Whenever a process is scheduled the first time or is scheduled after blocking, its Pi value is updated  as follows,

where T is the number of CPU ticks that have elapsed since the start of the system.

Intuitively, you can think of this policy as one that gives the processes some guarantees about their CPU share. If a process has a rate Ri, then it is guaranteed at least Ri percent of CPU time, provided the sum of all Ri values is less than 100. As the CPU usage of a process increases, its Pi value also increases depending on its Ri. If you have a large Ri, then your Pi increases more slowly and hence giving you a larger share of the CPU. Thus, Ri can be considered as a share of the CPU for the process i.

The second formula can be intuitively understood from the following example: Consider two processes A, B  starting at time 0 and running continuously with rate 50 and 40 respectively. Let us say that another process C is created after 100,000  ticks with rate 10. C will start executing with a  priority value  of 0 (if the second formula were not to be applied) and hence will hog the CPU for a very long time and processes A, B have to wait for long to get the CPU back and would not enjoy their share of the CPU till all the Pi values level off. On the other hand, if the process C starts with a priority value 100,000 instead of 0, then it will run only for a short amount of time before yielding the CPU back to A and B.

Implementation (hints):

According to this policy, the processes are scheduled in increasing order of their priority, i.e., the process with the lowest priority value Pi will be scheduled first. But, Xinu works in exactly the opposite way, i.e., the process with the highest priority is scheduled. In order to overcome this mismatch, we can maintain an internal variable Pi for every process which will contain the priority value. Let us denote the Xinu process priority of a process i to be PRIOi. Then PRIOi can be calculated as PRIOi = MAXINT - Pi. As Pi increases, PRIOi decreases and the process will get lesser share of CPU.  

To summarize, at every reschedule operation the proportional share scheduler does the following:

• The Pi value of the current process is modified and its PRIOi value updated.
• The scheduler chooses for execution the process with the highest priority, choosing from the processes in the ready list and the current process.

3. TS Scheduler 

A TS (timeshare) scheduler attempts to classify processes into CPU-bound and I/O-bound categories such that I/O-bound processes can be assigned higher priority for increased responsiveness without sacrificing fairness (i.e., starving CPU-bound processes). This is so since I/O-bound processes tend to voluntarily relinquish the CPU by issuing blocking system calls before their time quanta has expired.

Implementation (hints):

Implementing a TS scheduler entails two aspects: first, identification as I/O- or CPU-bound, and second, adapting process priorities. For the first step, we will use a simple (but also efficient) criterion, namely, whether the current process (if it belongs to the TSSCHED class), at the moment resched() is called, voluntarily relinquished the CPU or was forcibly interrupted by a clock interrupt handler because its time quantum expired. This may be determined inside resched() by checking the global variable preempt which counts down from the symbolic constant QUANTUM each time the clock interrupt handler is called (the internal details of the clock interrupt handler does not concern us here). A TSSCHED class process that, by this criterion, is considered I/O-bound (note that this only takes into account the most recent history) has its priority increased by 1. Of course, the maximum allowed priority (confer the range of the pprio field in the pentry structure) must not be exceeded. Design your own time quantum adaptation method (include a description of the method in the write-up) which is implemented along with priority adaptation.

4. Co-existence of Multiple Scheduling Policies

4.1 Changes to create()

Since scheduling policies are specified on a per-process basis, whenever a process is created in Xinu, a scheduling policy must be indicated. This can be implemented by adding an additional parameter to the create() system call. The new prototype of the create system call will be

    SYSCALL create ( int *procaddr, int ssize, int priority, int spolicy, char *name, int nargs, long args );

The parameter spolicy can be either AGINGSCHED, PROPORTIONALSHARE, or TSSCHED. Otherwise, SYSERR should be returned. A new field of the same name must be added to the process table definition. In the case of AGINGSCHED, the parameter priority would indicate the Xinu process' initial priority value. The same goes for TS. But in the case of proportional share it would indicate the 'rate' of the process. The internal priority value P should be made zero and hence the Xinu process priority value should be made MAXINT (MAXINT - 0).

The following must be defined in proc.h

#define AGINGSCHED                         1
#define PROPORTIONALSHARE       2
#define TSSCHED                                 3

4.2 Changes to resched()

To support process-specific scheduling policies, modify resched() such that process-specific switches implement priority changes inside resched(). Note that priority changes need not be limited to the current process. The Xinu scheduling invariant that at the end of the day a process with the highest priority is scheduled remains unchanged.

4.3 Chprio()

4.4 Getprio(), Getintprio()

Getprio() is expected to return the same priority that was set with chprio()

Getintprio() should be added as a new system call, to return the priority effectively used for the scheduling. In other words, getintprio() should return the priority that is used when inserting the process in the ready queue. You can use getprio() as an example.

 5. Miscellaneous Details

For checking the proportional share policy the following programs will help: test5.c, test6.c. The directions to run the programs are given in the files themselves. These test cases are by no means exhaustive. You have to write your own test cases to check your code. 

For this lab, you have to download a fresh copy of xinu as specified in lab0 (the Xinu Setup file) and follow the instructions.

6. Written Assignment (90 + 30 pts)

You must turn in a writeup along with the code for this lab. The writeup can be a text, pdf, or postscript file. Name the file "lab1answers.ps", "lab1answers.pdf", or "lab1answers.txt" and put it at the top level of your Xinu directory. In your write-up you should include a description (data-structures/algorithm) of your implementation, and answers to the following questions:

1. What are the advantages and disadvantages of the different scheduling policies including Xinu's default scheduler? For each scheduling class, use the same benchmark with multiple processes to demonstrate their performance. When evaluating the relative merits of the four scheduling classes, focus on their performance with respect to fairness. To evaluate fairness, first propose a method for measuring fairness of a population of processes (include the criterion and methodology in your write-up) which is implemented in Xinu. Do not use printing of characters as a solution. That is, the kernel must measure (related to accounting) to quantify fairness which is transparent to processes running in the system. You may insert sleep10() system calls to emulate I/O blocking for I/O-bound processes. Create a population of 10 processes with varying characteristics (i.e., I/O-bound, CPU-bound, or in-between) that are used as the benchmark suite.
2. Create a benchmark consisting of a mixture of AGINGSCHED, PROPORTIONALSHARE, and TSSCHED processes, two per scheduling class. What is the observed CPU sharing behavior across the three different service classes? Despite the general difficulty of predicting inter-class scheduling interactions, can you give an explanation of the sharing behavior that you have observed?

7. Turnin Instructions

Include your write-up as a text or postscript file in your xinu (xinu-fall2009) directory as the file Lab1Answers.txt, Lab1Answers.ps, or Lab1Answers.pdf (depending on the format used).

Turnin instructions for Lab1 code (electronic):

1. Make sure to turn off debugging output
2. Make sure that most of the code changes/addition you make are in the files resched.c, create.c, chprio.c. If you need to declare new variables, functions etc., declare them in a file lab1.h inside the xinu-fall2009/h/ directory.
3. goto xinu-fall2009/compile directory and do "make clean".
4. go to the directory of which your xinu-fall2009 directory is a subdirectory. (eg) if /homes/park/xinu-fall2009 is your directory structure, goto /homes/park
5. type in the following command:
   turnin -c cs503 -p lab1 xinu-fall2009

    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.

8. FAQ (from past years)

How to compile test1.c, test2.c ..... in Xinu???

        In Xinu, all the user processes will be written inside a file called main.c. This file  will be found in the "sys" directory. Initially, just after un-tarring Xinu, you will find that the main.c contains code to print "Hello world, Xinu lives" or something like that.

        So, if you want to run say test1.c. and let us assume that test1.c is in /u/u3/503/labs/09fall/lab1/ directory. You do the following.

        *First go to the sys directory (ie) your current directory is the "sys" subdirectory inside the 503 directory.
        *Now execute the following commands

                 *   cp  /u/u3/503/labs/06fall/lab1/test1.c    ./main.c
                 *   cd ../compile
                 *   make
                 *   cs-console
                        now proceed normally.

            What we have done is to copy the contents of the file test1.c into main.c and recompiling Xinu itself. Now, the recompiled xinu will execute whatever was inside test1.c whenever it is booted.

            Similarly for test2.c test3.c test4.c ....
 

What are test1.c test2.c test3.c test4.c etc?

    test1.c - explains the working of the Xinu scheduler when processes with equal priority are there.
    test2.c - explains starvation in the case of ordinary Xinu scheduling.
    test3.c - explains XINU scheduling invariant and shows starvation.
    test4.c - explains XINU scheduling invariant.
    test5.c and test6.c - contain test cases to test your proportional share scheduler.

More about Aging Scheduler

How often do we increase the priority?
    Each time rescheduling occurs.

Do we increase the priority of all the processes?
   The priority of all the ready processes (in the AGINGSCHED class).

More about Proportional share

How often do we increase the priority?
    Each time rescheduling occurs.

Do we update the priority of all the processes?
   The priority of current processes.

What is t in Pi   : =  Pi + ( t * 100 / Ri ) ?
   The CPU ticks since the most recent scheduling of the process.

What is T in Pi= max ( Pi, T ). ?
   T is the CPU ticks since the start of the system.

NOTE: In prop share, process with low priority value (Pi) is scheduled first. In XINU, process with high priority is schedule first. You MUST consider these policies. Please read the handout carefully for more information.

What do we mean by number of ticks or number of quanta in Xinu?

Hint: In Xinu there is a global variable to keep track of time. It stores time since the start of the system with an accuracy of 1/1000th of a second. Find out what it is and use it as the number of Ticks.