CSE3221 (Winter 2008) Project

 

You have to work individually. You are not allowed to view or exchange documents with your peers. We treat all sorts of cheating very seriously. Do not copy code from anywhere, even as a `template''. No late submission will be accepted. You are required to program in your PRISM account. Your work will be graded based on: i) correctness of programming logic; ii) clarity of your code and your coding style; iii) whether your code follows the specification. It is your responsibility to explain clearly every detail you do in the code with appropriate comments to avoid any possible confusion in marking.

 

Due date is 12:00 noon, March 3rd  10th  (Monday), 2008.

 

CPU Scheduling Simulation

 

A CPU Scheduler is a core component of any multiprogramming operating system kernel. It is very important to understand all details about the CPU scheduler if you want to know dynamic behaviors of the operating system. In this assignment, you are asked to write some ansi-C programs to simulate the following CPU scheduling algorithms for a single CPU machine:

 

1)      FCFS (first-coming-first-serving) scheduling.

 

2)      RR (round robin) scheduling with time quantum q=20 milliseconds, q= 200 milliseconds, q=2000 milliseconds, respectively.

 

3)      Three-level feedback-queue (FBQ) preemptive scheduling with q1=50 milliseconds and q2=200 milliseconds, as shown in Figure 5.7 in the textbook. Read the corresponding text for the details about this scheduling algorithm.

 

Based on a given static CPU workload (download from the course Web), your program must calculate and answer all the following questions for each of the above CPU schedulers:

 

1.      What is the average waiting time?

2.      What is the average turnaround time?

3.      When does the CPU finish all these processes? What is CPU utilization by this time point?

4.      How many context switches occur in total during the execution? (How to count context switch: you should count as context switch only for those cases where a process is preempted during its CPU bursts, not for those cases where a process terminates or just finishes its current CPU bursts and goes to I/O.)

5.      Which process is the last one to finish?

 

After you have your CPU scheduler programs, you need to do some experiments to investigate scheduling performance or scheduling behavior based on the given CPU workload for various control parameters. For RR scheduler, try to find an optimal value for quantum q which you think gives the optimal performance. For FBQ scheduler, try to find the optimal values for q1 and q2 which you think give the optimal performance. The performance should be measured according to average waiting time and total number of context switch. If you can’t improve both at the same time, try to find a good tradeoff between them and justify your choice.

 

Data Format

 

The CPU workload data file can be downloaded from the course Web, which is an ASCII file made in Unix system. Each line represents one process with the following format: (all numbers are in unit of millisecond)

 

pid  arrival_time 1st_CPU_burst (1st_IO_burst) 2nd_CPU_burst (2nd_IO_burst) ...

e.g.

0  0  4 (100) 12 (67) 2 ...

1  13 7 (210) 20 (23) 67 ...

 

where each I/O burst includes both the time waiting in the device queue and the time spent in actual I/O operations. When you implement each scheduler, if two or more processes are identical in terms of scheduling criterion, you should give priority to the process which has lowest pid number. 

 

What to submit?

 

First of all, you must submit three C programs for each of the CPU schedulers. For FCFS scheduler, your program is called "fcfs.c". For RR scheduler, your program is called "rr.c". For FBQ scheduler, your program is called “fbq.c”. When the programs run, they should print out the answers for all of the above questions to the standard output. If the programs do not compile in the PRISM lab or do not print out the answers, you get zero mark for this project.

 

Run the following commands to submit:

 

submit 3221 project fcfs.c

submit 3221 project rr.c

submit 3221 project fbq.c

 

Secondly, you need to submit a hardcopy report to the assignment box near the main office before the deadline.  The report can not be too long (maximum 6 pages).  In this report, you should first explain how to compile and run your codes for each of the above CPU scheduler and specify how to input parameters for each scheduler. Then, briefly summarize all experiments you have done with your schedulers on the given CPU workload. Finally, report the optimal parameters you have found for RR and FBQ schedulers and give your reasons to justify these optimal parameters. Do NOT include your source codes in the report.

 

In each of your C file and the report, include the following information (please complete) at the beginning:

# Family Name:

# Given Name:

# Section:

# Student Number:

# CS Login: