Operating Systems Concepts Tutorial exercises

Simple Kernel Processor Scheduling

This exercise sheet is available on-line at http://www.doc.ic.ac.uk/~wjk/OperatingSystemsConcepts

This exercise is intended to: 

1. Give you more practical experience of the Simple Kernel and a Linux development environment.
2. Let you experiment with various processor scheduling algorithms in the context of the Simple Kernel.

What you should do:

1. Find a PC running Linux, or reboot a lab machine that is running Windows NT and select Linux from the boot menu. If Linux doesn’t boot properly, try using Exceed from NT to log into a Linux machine.
   
   
2. Log in and click on the "shell" icon at the bottom of your screen to bring up a Linux command line console.
   
3. At the Linux command line type:  

cd
cp –rd ~wjk/SimpleKernelExercise2 .

(N.B. there is a dot on the end of the line above! ‘.’ stands for the current directory and is the destination of the copy)

This should give you a copy of all the files you need for this exercise in a folder called SimpleKernelExercise2 (you can check everything went according to plan by doing an ls –l to check that the folder SimpleKernelExercise2 now exists).

4. At the Linux command line type:

cd SimpleKernelExercise2
cd ICOS
cd system
ls –l 

You should recognise the Simple Kernel source files from the last exercise.

5. Have a look at the contents of the file user.cpp (e.g. using cat, vi, emacs or nedit). How many user processes are created? What do they do? What are their priorities? Can you guess what the output will be when the kernel is started?
   
6. Now type: 

cd ..
./simulate 

to run the PC simulator to see if your intuition was correct. If the PC simulator doesn’t run properly, have a look in the BochsSimulatorFiles directory, remove any files that begin with ckpt (the delete command in Linux is rm) and try again.

7. Now try to modify the Simple Kernel’s scheduler so that it implements the fairer dynamic priority assignment scheduling algorithm given in your notes. Processes should be started in the highest priority queue with a time-slice of 2 clock ticks. If the time-slice expires and the process has not suspended itself (i.e. with a P() or delay() system call), the process should be moved into the medium priority queue which has a time-slice of 4 clock ticks. Similarly, processes in the medium priority queue should be moved to the low priority queue (time-slice 8 clock ticks) when their time-slice has expired. Unblocked processes should rejoin in the highest priority queue.

You might like to try implement this on your own or you might like to follow these steps:

i. Look at the definition of struct PCB in the file include/icos/procP.h. Add an "age" field to the PCB.

ii. In proc.c go to the create() function and set the age of newly created processes to 0.

iii. In proc.c write a function void unblock(process pcb)which assigns a process to the highest priority queue and resets its age to 0 (provided the process is not the idle process).

4. Add a function prototype for unblock(…) to include/icos/procP.h.
5. Inspect time.c and sem.c and see if you can work out where you need to call unblock(…).
6. In time.c, adjust the tick() function so that it does not simply do a setready(running) and a dispatch() at the end of every clock tick, but instead:

o Increments the age of the currently running process.

o Compares the age of the process with the time-slice for the queue that the process is running in. If the time-slice has expired, the process needs to be moved down to the next queue (if it’s not already in the lowest priority queue), its age needs to be reset, it needs to be added to the ready queue and a new process should be dispatched onto the CPU.

7. In proc.c, inspect the dispatch() function. Does anything need to be changed here?
8. Check that your new code compiles by typing make. When you have fixed the errors, rerun the PC simulator and see if the output is what you expect.