Lab 5: Scheduling Algorithms

Background:

The scheduling of processes within a computer depends upon three main factors:

1. whether a process is allowed to run to completion once it is started (i.e., whether scheduling is preemptive or nonpreemptive);
2. the specific algorithm used to determine the next job to be scheduled; 
3. the time slice given to a process, if preemptive scheduling is used.

Goals:

In this lab, you will 

1. Gain first-hand experience implementing several scheduling algorithms.
2. Apply the event-driven simulationapproach to the problem of modeling the behavior of a system over time.
3. Obtain comparative data on throughput and average waiting time for different scheduling algorithms and varying scheduler overhead.
4. Get more experience with list structures in C.

Reading: 

• Lab 7.1 (Nutt, p. 283-289) provides background on event-driven simulation.
• scheduler_fcfs.c, which implements the First-Come First-Served scheduling algorithm.
• scheduler_simulation.c, which implements a framework for simulating scheduling algorithms.

Collaboration: You will complete this lab in teams of 1 to 3 of your choice.  You may, as always, consult with your classmates on issues of design and debugging.

Overview of Starter Code

scheduler_fcfs.c

~davisjan/csc/213/2006F/examples/scheduler_fcfs.c includes the structures, variables, and functions specific to job scheduling.

• int jobQueueIsEmpty( void ) returns true or false, according to whether any jobs are waiting in the ready state.
• void initializeJobQueue( void ) initializes the job queue with no jobs currently pending.
• void insertJob( struct Event* job ) adds the specified job to the job queue.
• struct Event* selectJob( void ) selects the next job to run from the job queue, removes the job from the queue, and returns it.

In scheduler_fcfs.c, these functions implement the FCFS scheduling algorithm.  You will use scheduler_fcfs.c as a template for implementing the Shortest Job Next (SJN) and Priority scheduling algorithms.  Only the internals of these four functions will need to be changed.

scheduler_simulation.c

~davisjan/csc/213/2006F/examples/scheduler_simulation.c incorporates scheduler_fcfs.c into an event-based simulation.

• Events are stored in the eventList structure.  Events are ordered by their start time.
• The program handles three types of events:
• When a job enters the system, it creates a registerJob event that enters the job into the system's data structure for ready processes.
• A scheduler event triggers the scheduler. if jobs are pending, the scheduler event retrieves the next job using the selectJob procedure and runs the job.  If no jobs are pending, time is advanced until the next event will occur.  
• When a process is scheduled, a processEvent event is triggered. This adds any required scheduler overhead to the clock.  If processes run without preemption, then the process is run to completion. If preemption is allowed, the process runs for its time slice or until it is completed, whichever is sooner.  When the process stops, a new scheduler event is triggered.
• To generate registerJob events, the program reads a sequence of jobs from a file for use in the simulation.  Each job arrival generates an event, which is placed in the eventList.
• Each event is given in the file as 
• arrival_time processing_time priority
  
• Jobs are listed in the file named by the constant JOB_FILE_NAME.  (Initially defined as "/home/davisjan/csc/213/examples/scheduler_job_data.txt".)
• The constant TIME_QUANTUM is 0 for non-preemptive scheduling or the size of the time slice for preemptive scheduling.  (Defaults to 0.)
• The constant SCHEDULER_OVERHEAD specifies the amount of simulation time consumed by the scheduler each time it is called.  (Defaults to 0.35.)
• After initialization, the main loop removes an event from the eventList and executes it.  The scheduler is treated as an event that is executed at the beginning of the simulation and after each job or time slice ends.
• Statistics on jobs started and waiting times are updated whenever a process starts.
• Statistics on jobs completed and processing times are updated whenever a process finishes.

The program contains three debugging flags that can provide on-going information as the simulation runs:

• Flag input causes the job specifications to be printed as they are read from JOB_FILE_NAME.
• Flag eventlist causes the event list to be printed each time through the main event loop.
• Flag printstats causes the accumulated job statistics to be printed each time through the main event loop.

Any combination of these flags can be specified at compile time.  For example, the following line invokes the input and printstats flags:

	gcc -o scheduler_simulation -Dinput -Dprintstats scheduler_simulation.c ; ./scheduler_simulation

Similarly, you can override the values of SCHEDULER_OVERHEAD and TIME_QUANTUM at compile time.  For example, the following line sets SCHEDULER_OVERHEAD to 0.01 and sets TIME_QUANTUM to 0.05:

	gcc -o scheduler_simulation -DSCHEDULER_OVERHEAD=0.01 -DTIME_QUANTUM=0.05 scheduler_simulation.c ; 
	./scheduler_simulation

Steps for this lab

Part A: Non-preemptive scheduling algorithms

1. Run the existing program to get average waiting times and throughputs for the FCFS scheduling algorithm, using values of 0.0, 0.01, 0.02, 0.03, and 0.04 for the SCHEDULER_OVERHEAD.  (You may wish to record your measurements in a text file or a spreadsheet.)
2. Make a copy of scheduler_fcfs.c and use it as a template for implementing the SJN scheduling algorithm.
3. Change the included file in scheduler_simulation.c from scheduler_fcfs.c to your new file. 
4. Run the simulation with SJN for the same cases as in step 1.
5. Compare the average waiting times and throughputs for FCFS and SJN.  Does this information suggest any conclusions regarding the relative effectiveness of FCFS and SJN?

Part B: Preemptive scheduling algorithms

1. A simple Round-Robin (RR) scheduling algorithm can be obtained by using the FCFS scheduler you are given, but changing the processJob event handler in scheduler_simulation.c as indicated by /* YOUR CODE HERE */. If the constant TIME_QUANTUM is positive, then a job is allowed to run continuously only for that time slice.  If the job will not finish within the time slice, then the time remaining for the job is reduced by the time slice, and the scheduler is invoked again.
2. Run the RR scheduling simulation for the same values of SCHEDULER_OVERHEAD you did in step A.1, with the time quanta being 0.05, 0.1, 0.15, and 0.2.  (You may wish to record your measurements in a text file or a spreadsheet.)
3. Change the include file from scheduler_fcfs.c to a new file that implements a multi-queue priority algorithm.  Assume priorities are from 1 (most important) through 10 (not very important).  Vary the time slice allocated to a job according to its priority:
• time_quantum = TIME_QUANTUM / 2^(priority-1)
4. Again, run the resulting priority algorithm for the same values of SCHEDULER_OVERHEAD given in step A.1 and the same time quanta specified in step B.2.
5. Compare the average waiting times and throughputs for the non-preemptive and preemptive algorithms you obtained in your simulations.  Can you draw any conclusions regarding the relative effectiveness of these algorithms?

Work to be Turned In

• Part A, due Friday 29 September:
• A program from step A.2 implementing the SJN algorithm.
• The statistics you measured for steps A.1 and A.4. 
• Your answer to the question in step A.5.
• Part B, due Monday 2 October:
• Your modified version of scheduler_simulation.c from step B.1 implementing the RR algorithm.
• A program from step B.3 implementing the multi-queue priority algorithm.
• The statistics you measured for steps B.2 and B.4.
• Your answer the the question in step B.5.

For the programs in steps A.2, B.1, and B.3, please follow the instructions for submitting programs.

If you prefer, you may turn in the entire program (parts A and B) on Friday 29 September, in which case you need not turn in anything further on Monday 2 October.

Janet Davis (davisjan@cs.grinnell.edu)