Assignment 3

Based on Problem 2.39 from Tanenbaum and Woodhull.

Note: You may work with one other student on this assignment if you wish. The assignment is due 2:40pm, Friday, October 12. You will submit a written report for this assignment.

Objectives

To implement an adaptive scheduling technique.
To become more familiar with the Minix kernel source code.
To practice system analysis.

Problem

Your job is to modify Minix to support an alternative process-scheduling scheme that gives priority to user processes that block frequently. This is preferable because a user is more likely to be actively waiting for these processes, and because such a process is helped along tremendously with a small share of the CPU.

The scheduling algorithm is as follows. Time is divided into five-second intervals, and the clock interrupt handler tracks how much time each process has taken within the current interval.

When it is time to select a process, the OS will still prefer to take the first task or server process, as before. But when the OS is to choose a user process, instead of choosing the first user process in the queue, it chooses the ready user process that has used the least time within the current five-second interval.

Minix source code

Before you begin, first run setup_cs350 again, log out, and log in again. This modifies your setup as needed.

To get the Minix source code for modification, type getcs 350 3. This copies the source code for the kernel into your CS350/Project3 directory.

To compile the Minix source code, go into the src/tools directory and type make image. This generates a new image file containing your kernel's binary. From this directory, you should be able to run minix to test your kernel version.

Important: As you modify kernel code in src/kernel, take careful note of the modifications you make to the kernel. In your written report, you will detail only the modifications you make.

Hints

My solution to this assignment added 18 lines (not counting comments) to the Minix kernel code. The modifications I made were as follows.

In clock.c: added a global variable to represent when the current five-second segment began.
In proc.h: added two fields to the proc structure. One represented the five-second segment when the process last ran, and one represented the amount of time consumed thus far by the process in that five-second segment.
In system.c: modified the do_fork() function so that these fields were initialized to 0 when a new process is created.
In clock.c: modified it to track the current five-second segment and to update the added process fields based on the clock ticks.
In proc.c: modified it so that the scheduler chooses according to the new algorithm.

At any time while you are running Minix, you can type control-backslash, which immediately executes the p_dmp() function in dmp.c. This dumps much information about all the processes. If you want this to display more information about the current processes you can add additional debugging code to p_dmp().

Testing

When you run minix in the src/tools directory, you should be able to log in as student. You will find in that user account two executable files.

primes: A highly computational process. When you run primes, the process immediately forks, with the parent process returning you to the shell. In the background, the child process loops infinitely in lots of computation (testing primes displaying the number found after each block of 20,000).
scanfiles: A highly I/O-bound process. It runs od on several binaries and throws away the result.

Say you're running several (5, maybe) versions of primes in the background. If you've made good modifications, you should find that your modified kernel runs scanfiles much more quickly than the original kernel.

To test this, you can use the Unix time command. For example:

$ time scanfiles
real        4.00
user        2.20
sys         6.30

Ignore the ``user'' and ``sys'' lines. What's important here is the ``real'' line, which says that scanfiles took 4 seconds to complete.

When you do your timings, you should average over a series of trials, as the timings will fluctuate slightly. (There's no need to reboot Minix or log in again - just run the trials in quick succession.)

Written report

Unlike your previous assignments, for this assignment you should submit a typed paper report. This report will have two sections, one section detailing the modifications you made to the Minix kernel and one section detailing your analysis of its effects.

The first section should describe exactly your modifications to the code, referring to the textbook's line numbers to show precisely where you have added or modified code. This will likely be short - my solution has only 18 lines, after all. Do not give me large segments of the Minix source code; just detail your own changes.

For the second section, complete the following.

Make a chart of the amount of time scanfiles takes on standard Minix for various numbers of instances of primes running in the background. Start with 0 instances, and go up to 5 instances.
Make a similar chart for your modified version of Minix.
Name any important details of the above tests. How many trials were you averaging over? Was there a large variance in the trials' results?
What do you conclude from the above observations? (This is the most important element of this section, which I will grade subjectively on the quality of your reasoning and analysis.)

Grading criteria

In grading your assignment, I will assign points as follows.

20	correct accounting of time process spends
20	correct selection of algorithm
10	presentation of modifications
10	presentation of results (charts and details)
20	analysis and conclusions

In grading your analysis, I will be looking for valid assertions, that summarize the data and are well-justified. Assertions should be accompanies by an analysis of the possible cause. It's certainly possible to complete a top-scoring analysis within half a page, but there's no required length. (I will deduct points for what looks like padding to me.)