Spring 2003 CS 3733 Operating Systems Assignment 2

CS 3733 Operating Systems, Spring 2003 Assignment 2

Part 0 Due Tuesday, February 18, 2003
Parts 1 and 2 Due Thursday, February 27, 2003

In this assignment you will explore the topic of CPU scheduling by using the scheduling simulator described in class. You can find out more about the simulator at the web site: /nsf/ps/index.html.
A copy of the simulator user's guide can be found at /nsf/ps/ps_doc/psdoc.html.
These links are also available from the course simulator web page.

You might want to read about the experiences students had with the simulator in a previous semester in a paper available at /nsf/pubs/process.html.

Part 0

If you have not already done so, create a web page for yourself.
The address of your web page should be http://www.cs.utsa.edu/~username. Create a course web page with web address http://www.cs.utsa.edu/~username/cs3733/index.html. This should be globally accessible. Your course web page should be very simple without much graphics so that it will load quickly over a phone line.

Make an assign2p0, directory under your public_html/cs3733 directory. The permissions of the public_html, cs3733, and assign2p0 directories should be drwxr-xr-x.

Make a directory somewhere in your account for this assignment called assign2. Do not put this under public_html. The permissions of this directory should be set so that only you have access to it. Make a subdirectory called part0. Put the contents of this tar file in your part0 directory. Edit the psconfig file and change my name to yours. Make sure that your path includes /usr/local/courses/java/bin. Execute:
java -version
You should get output that looks like this:
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.0-rc-b91) Java HotSpot(TM) Client VM (build 1.4.0-rc-b91, mixed mode) Run the simulator using runps which is a script in this directory.

Click Open Log button and this should change it to Close Log. You have opened a log file.
Click on Run Experiment and then Log All Table Data.
Click on Draw Graph and then the Log button on the graph. It may take a few seconds while the graph is converted into a GIF.
Click on Draw Gantt Chart and choose the first one. Adjust the size so that the entire chart is shown. You can use the Controls to change the height of the bars.
Click on the Log button on the Gantt chart.
Do the same for the second Gantt chart.
Close the log file.
Open a browser and load the file called logfile.html.

Copy the .html and .gif files into your public_html/cs3733/assign2p0 directory. Set the permissions so that the files are all world readable. Put a link to the log file in your course web page. Make sure you (and others) can access this log file through your link.

Part 1

Start by copying your files from your assign2/part0 directory into a assign2/part1 directory. Modify the files in this part1 directory for this part of the assignment. Consider 20 processes all arriving at almost the same time. The first 10 processes to arrive have duration 100 and CPU bursts uniformly distributed between 10 and 20. All I/O bursts are 200. The next 10 processes all have duration 40, cpubursts of 2, and I/O bursts of 25.

Run an experiment on the simulator that compares first come/first served and round robin with a quantum of 3. Run the experiment and determine which has a shorter average waiting time.

Create an HTML log containing tables of statistics, graphs, and Gantt charts to show the results of the two runs. Also include other data as indicated below.

Estimate the load average for each of the runs. The load average is defined as the average number of processes in the ready queue. This information is not directly available from the simulation statistics, but can be calculated using Little's Law which implies that the load average is the total waiting time divided by the time for the experiment. The total waiting time is the total for all of the processes. You can find it by using the average waiting time given in the simulator tables. The time for the experiment is the time the last process finishes and is given in the table.
RR often causes more context switches than FCFS. The simulator does not take into account context switch time. Estimate the context switch time that would give RR in this example the same average waiting time as FCFS.

Take into account the context switch time as follows. Each time a context switch occurs, the context switch time must be added to the waiting time of each process in the ready queue. Above, you calculated the average number of processes in the ready queue. Find out the number of context switches for each algorithm. You can do this by pushing the All Data button. This puts some data for each run in the yellow window. Include the contents of this window in your log file. The value "Times CPU Entered" is the number of times a process enters the running state and is the number of context switches done. This, together with the context switch time and the average number of processes in the ready queue tells you how much needs to be added to the total waiting time. Do this calculation and show how you got your results. Note that there are no units for the times given by the simulator. Express the answer to b) above in units of the round robin quantum.

Part 2

Start by copying your files from your assign2/part1 directory into a assign2/part2 directory. Modify the files in this part2 directory for this part of the assignment.

Think about the conditions under which preemptive shortest job first (PSJF) will perform better than shortest job first without preemption (SJF). The measure of performance we will use is average waiting time. Write a statement describing these conditions in some detail.
Now design an experiment which will support your statement. The experiment must use at least 20 processes, and the average waiting time for PSJF should be at most half that of SJF. Choose parameters so that the load average is at least 1.0 and the CPU utilization is at least 50%.
Use the method described in Part 1 to take into account the context switch time. One disadvantage of PSJF is that it may require additional context switches. If your experiment requires more context switches for PSJF, calculate the context switch time that would cancel out the advantage that PSJF has in your experiment. Express the answer in the time units of the simulator.
Another disadvantage of PSJF is that there is additional overhead each time a process enters the ready queue while a process is running. The algorithm needs to decide whether or not to preempt the running process. Estimate the number of times this needs to be done in your PSJF experiment. Then calculate the time one of these extra calculations would need to take in order to cancel out the advantage of PSJF over SJF. Ignore the context switch time in this calculation. Show how you got your answer.

The number of times a process enters the ready queue should be the same as the number of times a context switch occurs. The probability that a process is running when a process enters the ready queue is the same as the CPU utilization. Notice that in part c), only the difference in the number of context switches in the two runs is used (since both algorithms do context switches) but in part d) the total number of context switches for PSJF is used (since SJF never does the preemption calculation).

Hand in the log file containing tables and graphs that show your results. Explain why this experiment supports your statement about when PSJF is better.

Handing in the assignment

You do not need to hand in Part 0.
Make sure you have a link to your log file on your course web page by the due date for Part 0.
For Part 1:
1. Create a log file containing tables, waiting time graphs, and Gantt charts.
2. Make sure this log file is labeled as Part 1.
  You can label it by hand.
3. After this log file, put your answers to part 1a and 1b.
4. Make sure these answers are right after the log file so I can easily find them.
Put your results for Part 2 after those for Part 1.
1. Start with your answer to Part 2a.
2. Next include the printout of your log file for the experiment for Part 2b.
3. Next include a short (1 paragraph) discussion of what your experiment shows and how it supports your statement in Part 2a.
4. Next include your answers to parts 2c and 2d.
5. It is important (to me) that everything is in the right order and easy to find. If not, I will not be able to give you the grade you deserve.