CS 450 Update Log

Archive for 17th June 2009

CPU Scheduling (and other) Simulators

June 17, 2009, 4:47 pm

The CPU Scheduling simulator you need for some of the problems in assignment 1 can be found at the UTSA CS Simulators website — look for the “Process (CPU) Scheduling” simulator download. Detailed documentation for the simulator can also be found on the website.

If you like, you can also obtain the simulator via the git version control system by cloning the CS 450 course repository — do this with the following command:

git clone git://github.com/michaelee/cs450.git

Look under the sim/ps directory of the cloned repository.

For those interested in some extracurricular hacking, you can also find a PDP-11 simulator under the sim/simhv directory (courtesy of the Computer History Simulation Project). Compile it with make, and you’ll find the simulator binary at ./bin/pdp11.

Running v6 is then a matter of downloading the software kit, unpacking it, and attaching to it in the simulator and booting up: (I moved the pdp11 binary into the unpacked v6 package directory before starting, below)

foxtrot:uv6swre$ ./pdp11

PDP-11 simulator V3.7-3
sim> set cpu u18
sim> att rk0 unix0_v6_rk.dsk
sim> att rk1 unix1_v6_rk.dsk
sim> att rk2 unix2_v6_rk.dsk
sim> att rk3 unix3_v6_rk.dsk
sim> boot rk0
@unix

login: root
# ls -l
total 182
drwxr-xr-x  2 bin      1040 Jan  1  1970 bin
drwxr-xr-x  2 bin       352 Jan  1  1970 dev
drwxr-xr-x  2 bin       304 Aug 20 12:18 etc
drwxr-xr-x  2 bin       336 Jan  1  1970 lib
drwxr-xr-x 17 bin       272 Jan  1  1970 mnt
drwxr-xr-x  2 bin        32 Jan  1  1970 mnt2
-rw-rw-rw-  1 root    28472 Aug 20 12:01 rkunix
-rwxr-xr-x  1 bin     28636 Aug 20 11:38 rkunix.40
drwxrwxrwx  2 bin       144 Aug 20 12:14 tmp
-rwxr-xr-x  1 bin     28472 Aug 20 12:01 unix
drwxr-xr-x 13 bin       224 Aug 20 12:22 usr
drwxr-xr-x  2 bin        32 Jan  1  1970 usr2

You can find more instructions on the PDP-11 simulator here, and on using the v6 software package here.

Category: Misc | Comment

Assignment 1: CPU Scheduling

June 17, 2009, 12:01 am

In this assignment you’ll try your hand at (manually) simulating a number of scheduling algorithms discussed in lecture. Please type up your submissions and show all your work for full credit — handwritten work will not be accepted! (Diagrams may be neatly hand drawn with a ruler, if you’re not comfortable doing those on a computer).

Submissions are due 6/24/09 at the beginning of lecture. Internet/TV students please have your work submitted via the blackboard digital dropbox by then.

Exercise 1

Consider the following set of processes with the given CPU-burst lengths and arrival times:

Process	CPU Burst	Arrival Time
P0	2	0
P1	10	1
P2	6	5
P3	3	7

Draw four Gantt charts illustrating the execution of these processes using the FCFS, non-preemptive SJF, preemptive SJF, and RR (quantum=2) scheduling algorithms.
What is the average turnaround time for each of the scheduling algorithms in part (1)? Show how you compute your answer.
What is the average waiting time for each of the scheduling algorithms in part (1)? Show how you compute your answer.
Which of the scheduling algorithms results in the minimum average waiting time in part (1)?

The Process Scheduling Simulator

Consider the following run setup for the scheduling simulator:

seed 5000
numprocs 10
firstarrival 0.0
interarrival constant 0.0
duration constant 50
cpuburst exponential 5
ioburst exponential 10

The following experiment configures the above run with the SJF, preemptive-SJF, and SJFA 0.5 (CPU burst duration predicted using an EMA with a configured alpha of 0.5) algorithms:

run alpharun algorithm SJF key "SJF"
run alpharun algorithm PSJF key "PSJF"
run alpharun algorithm SJFA 0.5 key "SJFA"

Create the necessary configuration files — you may need to add some of your own lines — and run the simulator with the given settings. Refer to the output for exercise 2. Exercises 3 and 4 asks you to make some modifications to the run settings.

Exercise 2

Which of the scheduling algorithms completes all 10 processes in the least amount of time (and consequently achieves the best CPU utilization)? Referring to the Gantt charts for the three algorithms, explain in general terms why this happens. It may help in particular to examine how processes 2 and 10 are scheduled.

Exercise 3

For our setup we specified an exponential distribution for CPU burst durations. You can read about exponential distributions at Wikipedia — they are particularly useful when modeling/simulating the inter-arrival times or durations (as in our case) of events in certain systems where the mean inter-arrival time or duration is known.

First, change the duration of the processes in the simulated run to 1000 (so that the simulation is somewhat lengthier). Via either prediction or experimentation, can you determine an optimal value (to one decimal place) for alpha for the SJFA algorithm? Explain your reasoning for why it is optimal.

Exercise 4

Modify the (original) run above by adding context switch times to the experiment. You can do this by inserting the following lines in the run file after the seed setting:

cstin 0.5
cstout 0.5

Run the experiment again. Are there any changes in the overall (and relative) performance of the algorithms? Explain your observed changes.