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; and
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 simulation approach 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.
• Example scheduling algorithm and simulation program:
  • scheduler.h, defines the interface and data structures for a generic scheduling algorithm.
  • scheduler_fcfs.c , which implements the First-Come First-Served scheduling algorithm, according to the scheduler.h interface above.
  • scheduler_simulation.h / scheduler_simulation.c , which implements a framework for simulating scheduling algorithms. It can be linked with any object file that implements the methods in schedule.h
  • Makefile, which gives an example of how to compile and link the simulator, with optional #defined parameters specified.

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.h

This header declares some structure types 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.
• struct jobQueue contains pointers to two struct jobQueueNodes for a linked list that can form a jobQueue for any scheduling algorithm.

scheduler_fcfs.c

scheduler_simulation.c

• Events are stored in the eventList structure, 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/weinman/public_html/courses/CSC213/examples/scheduler/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.

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

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. (Record your measurements in a text file or a spreadsheet.)
2. Implement the SJN scheduling algorithm, using the scheduler.h interface described above.
3. Compile your own SJN scheduler and link it with scheduler_simulation.c.
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. (Record your measurements in a text file or a spreadsheet.)
3. Implement a multi-queue priority algorithm, using the scheduler.h interface described above. 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

• 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.
• 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 to the question in step B.5.

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

Note that the exam is Friday 10/3. While the lab has been "partitioned," it is not due in its entirety until Tuesday 10/7 so that you have ample time to study. According to syllabus, the exam carries three times more weight than any given lab.

Jerod Weinman