Programming Assignment Lab: Scheduler/Dispatcher

You are to implement a Scheduler in C, C++ and submit the source code, which we will compile and run. Both are to be delivered to the TA as source code through NYU Classes assignment. The submission must include a Makefile for building your code.

In this lab we explore the implementation and effects of different scheduling policies discussed in class on a set of processes/threads executing on a system. The system is to be implemented as a Discrete Event Simulation (DES) (http://en.wikipedia.org/wiki/Discrete_event_simulation). In discrete-event simulation, the operation of a system is represented as a chronological sequence of events. Each event occurs at an instant in time and marks a change of state in the system. This implies that the system progresses in time through defining and executing the events (state transitions) and by progressing time discretely between the events as opposed to incrementing time continuously (e.g. don't do sim_time++"). Time stamped events are removed from the event queue and new events might be created during the simulation.

A process is characterized by 4 parameters: 

Arrival Time (AT), Total CPU Time (TC), CPU Burst (CB) and IO Burst (IO).

Note, you are not implementing this as a multi-program or multi-threaded application. By using DES, a process is simply an object that goes through discrete state transitions; in the object you maintain the state and statistics of the process as the OS would do.

We make a few simplifications: 

(a) All time is based on integers not float, hence nothing will happen or has to be simulated between integer numbers;

(b) To enforce a uniform repeatable behavior, a file with random numbers is provided (see website) that your program must read in and use (note the first line defines the count of random numbers in the file) a random number is then created by using:

"int myrandom(int burst) { return 1 + (randvals[ofs] % burst); }"

You should increase ofs with each invocation and wrap around when you run out of numbers in the file/array. It is therefore important that you call the random function only when you have to, namely for transitions 1 and 3 (with noted exceptions) and the initial assignment of the static priority.

(c) IOs are independent from each other, i.e. they can commensurate concurrently without affecting each other's IO burst time. 

Deterministic Behavior:

There will be scenarios where events will have the same time stamp and you must follow these rules to break the ties in order to create consistent behavior:

(a) On the same process: termination takes precedence over scheduling the next IO burst over preempting the process on quantum expiration

(b) Processes with the same arrival time should be entered into the run queue in the order of their occurrence in the input file.

(c) Events with the same time stamp (e.g. IO completing at time X for process 1 and cpu burst expiring at time X for process 2) should be processed in the order they were generated, i.e. if the IO start event (process 1 blocked event) occurred before the event that made process 2 running (naturally has to be) then the IO event should be processed first. If two IO bursts expire at the same time, then first process the one that was generated earlier.

(d) You must process all events at a given time stamp before invoking the scheduler/dispatcher.

Not following these rules implies that fetching the next random number will be out of order and a different event sequence will be generated. The net is that such situations are very difficult to debug (see for relieve further down).

Attachment:- Assignment.rar