Job Scheduling Simulation

Overview

This programming assignment is designed primarily to improve your understanding of a typical process scheduling algorithm. It also incorporates skills and knowledge that you have earned in previous (lower-level) classes, in particular,

CIS163 Introduction and Computer Science 2
CIS263 Data Structures and Algorithms.

Using a simulation, you will study the behavior of the Round Robin Scheduling on a single-CPU system. One parameter that affects the performance of Round Robin policy is the time quantum. Using the simulation program you are about to develop, this effect can be easily observed by specifying different quantum each time the simulation is run.

Recall that the execution of a process/job follows an alternating cycle of its CPU bursts and I/O bursts. In a system with a round-robin scheduler, the CPU bursts may be shorter or longer than the scheduler's time quantum

Discrete-Event Simulation

The kind of simulation that you will implement in this project is known as Discrete-Event Simulation (DES) where important events in the simulated system are generated and processed by the simulator.

DES Example: Traffic Light

For instance, the three important (discrete) events in a single traffic-light simulation are:

Green light on (also Red light off)
Yellow light on (also Green light off)
Red light on (also Yellow light off)

Assuming the red light stays on for 30 seconds, green light for 25 seconds, and yellow light for 5 seconds and the red light just turned on at current (simulation) time of 100, the series of events are:

Time	Event
100	Red light on
130	Green light on
155	Yellow light on
160	Red light on
190	Green light on
215	Yellow light on
220	Read light on
and	so on ...

TIP

Associating each event with its time of occurrence is important in DES.
You will also need a (priority) queue to store all these events in ascending order of their time

Traffic Light and Cars

If, in addition to the traffic light, we also want to simulate car arrival at a fixed interval of 7 seconds, the list of events become:

Time	Event
100	==> Red light on
107	Car #1 arrival
114	Car #2 arrival
121	Car #3 arrival
128	Car #4 arrival
130	==> Green light on
135	Car #5 arrival
142	Car #6 arrival
149	Car #7 arrival
155	==> Yellow light on
156	Car #8 arrival
160	==> Red light on
163	Car #9 arrival
170	Car #10 arrival

TIP

Besides the (priority) queue of events, you will also need a queue of cars when they are waiting at the traffic light.

What about Car Departure events? Unfortunately, the car departure events can't be precomputed, their exact time depends on Green Light on event. Hence, these events must be generated (later) when the simulation is processing the "Green Light On" event.

Also, if cars are arriving at random interval (between 10-30 seconds), only the first car arrival can be precomputed and the subsequent car arrival events must be computed on the fly.

General Design of DES Simulation Loop

In general, any event in the discrete-event simulation (DES) will cause the state of the system changes at discrete time. These state transitions take place in simulated time (instead of real time).

The general design of a DES program will follow this loop:

// Generate InitialEvent(s)
startWithRed = createEvent(RED_LIGHT_ON, 100)
EventQueue.push(startWithRed)
firstCar = createEvent(CAR_ARRIVAL, 107)
EventQueue.push(firstCar)

while (EventQueue is not empty) {
    ev  = EventQueue.pop()
    now = ev.time   // advance the simulation time
    switch (ev.type) {
        RED_LIGHT_ON:
            greenEvent = createEvent(GREEN_LIGHT_ON, now + 30)
            EventQueue.push(greenEvent)
            // do other bookkeeping 
        GREEN_LIGHT_ON:
            yellowEvent = createEvent(YELLOW_LIGHT_ON, now + 25)
            EventQueue.push(yellowEvent)
            // do other bookkeeping
            // create next CAR_DEPARTURE events?
        YELLOW_LIGHT_ON:
            redEvent = createEvent(RED_LIGHT_ON, now + 5)
            EventQueue.push(redEvent)
            // do other bookkeeping
        CAR_ARRIVAL:
            nextCarTime = now + RandomNumber()
            nextCarArrival = createEvent(CAR_ARRIVAL, nextCarTime)
            EventQueue.push(nextCarArrival)
            // do more work
        CAR_DEPARTURE:
            // do more work
    }
}

Each cycle of the while-loop follows the same recipe:

Handle the current event
Advance the simulation time to the time of the current event
Generate new future events as necessary
Perform other bookkeeping tasks as needed

Job Scheduling Simulation

For job scheduling simulation, the important events are:

Arrival of a new job
Preemption of the current job from the CPU
Blocking of a job due to its I/O request
Completion of a job's I/O operation
Termination of a job

Essentially each event corresponds to one red or black arrow in the diagram used in class:

List of (Discrete) Events

The simulation loop of your program is driven by the list of (future) events in the system being simulated. In order to process all these events in a chronological order, they must be maintained in ascending order of their time of occurrence.

A heap or a priority queue is perhaps the best data structure for this list.
The simulation loop then removes one event at a time (starting from the earliest), changes the state of the system accordingly, and performs all the updates that must take place during the current simulation time.

Assignment Specifications

This is an individual project, and you may implement the simulation program in any language of your choice
The program that you are about to write is not a system program, it is just a typical user application that requires no spawning of processes, no timer interrupt handling, no I/O interrupt handling, etc.
The description of each simulated process will be provided in a text file, one line per process (See sample input file below)
Time quantum (integer) used in the Round Robin simulation is given as the second command-line parameter.
The simulator shall print an appropriate message when a simulated process changes its state. Use the 5-state model (New, Ready, Running, Blocked, Exit). For instance, it shall print a message when it performs one of the following actions:
- Starts a new process
- Schedules a process to run
- Moves a process to the I/O Waiting (Blocked) State
- Preempts a process from the Running State
- Moves a process back into the Ready State (due to I/O completion)
- Starts servicing a process' I/O request
Each message shall be prefixed with the current simulation time.
When a simulated process is interrupted (because its current CPU burst is longer than the quantum) the process is preempted and re-enter the ready queue
When a simulated process completes its current CPU burst, it will then use its I/O burst, the simulator change the process' state to Blocked. At this point, the CPU becomes idle and the dispatcher may select another process from the ready queues.
The simulated system has only one CPU but infinitely many I/O device. This implies that I/O requests can be served immediately without waiting for a device to become available.
Upon completion of its I/O burst, a process will change from Blocked state to Ready and join the Ready Queue again.
A process entering the ready queue can be one of the following:
- a new process,
- a process returning from Blocked state, or
- a process preempted from the CPU
When these three events happen at the same time, the new process will enter the Ready Q first, followed by process returning from Blocked state, and finally by the preempted process.
When a simulated process terminates, the simulator then outputs a statement of the form:
```
Job %d terminated: Turn-Around-Time = %d, Wait time = %d
```
1
At the end of simulation, the simulator shall display the percentage of CPU utilization, average TAT, average wait time.

Sample Input File

Suppose an input file used by your simulation contains the following lines

3  3  2  5  8  7  4
5  1  4
6  4  8  2  10 2  7  5  6

On each line:

The first number is process arrival time (A)
The second number is the number of CPU bursts (N)
The next 2N-1 numbers are an alternating seqeunce of CPU time and I/O time (CPU-IO-CPU-...-CPU)

This file represents three processes with the following execution behavior (pay attention to the order of CPU bursts and I/O bursts in the above input and the table below).

Job	Arrival Time	CPU bursts	I/O bursts
1	3	2,8,4	5, 7
2	5	4	-
3	6	8, 10, 7, 6	2, 2, 5

TIP

Each process always starts and ends with a CPU time
The jobs in the input file are sorted in ascending order by their arrival time

Generating Future Events

How are future events determined? Let's look at the case when a process is dispatched to use the CPU. There are three possible future events that may take place with respect to the process: PREEMPTION, IO_REQUEST, or TERMINATION. However, only one of these future events will take place depending on the scheduler quantum time, the process current CPU burst, and whether this process has an I/O burst following the current CPU burst.

As an example, let's use Job 1 in the sample input above. Assume that the system quantum time is 3 units.

When Job1 is dispatched at time T to run its first CPU burst, the next (future) event for Job1 must be IO_REQUEST that will take place at time T+2, i.e. the current time + the remaining CPU burst. At this point a new IO_REQUEST event must be inserted into the event list. Job1 itself, however, will not be blocked at the current simulation time. Later at time T+2, when the simulation loop handles the IO_REQUEST event, Job1 will be moved from the CPU to the I/O device.
When later Job1 is dispatched at time U to run its second CPU time (8 units), the next (future) event for Job1 must be PREEMPTION that will take place at time U+3, i.e. the current time + the system quantum. Likewise, a new PREEMPTION event will be inserted into the event list and the actual preemption will take place later when the simulation loop is at time U+3 handling the PREEMPTION event.
Other future events will be generated using a similar technique.

Event Structure

If you implement the simulation program in C, an "Event" is perhaps a structure that may look like the following:

typedef struct {
   int time;           /* when the event will occur */
   int type;           /* type of event */
   int process_id;     /* to whom this event applies */
} Event;

Extra Credits

Simulate a multi-processor system
Use graphs to plot system performance parameter(s) on a vertical axis vs. time on the horizontal axis: CPU utilization vs. time, Average Wait vs. time, ...... Refresh this graph as the simulation time progresses.
Allow your simulator to use additional scheduling algorithms
Implement a multithreading solution
Show a visualization of the simulated system

Grading Rubrics

Grading Item	Points
Parsing input file	3
Management of Event queue	3
Management of Ready queue	3
Correct Generation and handling of events	5x4
Correct calculation of job statistics	3
Correct calculation of simulation statistics	2
Informational messages for important job state changes	3

Deliverables

Submit a printed hard copy of all the source files, and other files needed to compile your program.
Upload all those files to Bb
Be ready to demo in the EOS lab

Overview ​

Discrete-Event Simulation ​

DES Example: Traffic Light ​

Traffic Light and Cars ​

General Design of DES Simulation Loop ​

Job Scheduling Simulation ​

List of (Discrete) Events ​

Assignment Specifications ​

Sample Input File ​

Generating Future Events ​

Event Structure ​

Extra Credits ​

Grading Rubrics ​

Deliverables ​

Overview

Discrete-Event Simulation

DES Example: Traffic Light

Traffic Light and Cars

General Design of DES Simulation Loop

Job Scheduling Simulation

List of (Discrete) Events

Assignment Specifications

Sample Input File

Generating Future Events

Event Structure

Extra Credits

Grading Rubrics

Deliverables