Lab 3: CPU Scheduling Simulator

Assigned: Thursday, March 27
Due: Thursday, April 3, 17, 29

Purpose

To have a deep understanding of heap structure and priority queue.
To be familiar with different algorithm techniques used in CPU Scheduling policies.
To learn how to develop an event-based simulator
To practice the empirical evaluation of the algorithms

Description

In this project, you will implement a discrete event simulator in Java with several different scheduling algorithms. The simulator selects a task to run from ready queue based on the scheduling algorithm. However, it does not require any actual process creation or execution. When a task is scheduled, the simulator will simply print out what task is selected to run at a time.

(Due: April 3) Part 1: implement your own priority queue. Priority queue is a basic data structure used in many algorithms, including CPU scheduling. When a task arrives, it will enter the ready queue. At a scheduling point (such as the previous task finishes, or a new task with high priority arrives), the scheduler will select a task with the highest priority from the ready queue, and execute it. Different scheduling algorithms have different priority criteria. However, they all have the basic enqueue and dequeue operation for a priority queue. Priority queue is not only used in scheduling algorithm, it is also used in the event-based simulation. A core component of the Discrete Event Simulator (DES) is the event queue, which is ordered based on the event's time. When a new event is generated, it needs to insert into the event queue. The main operation of a simulator is repeatedly get the earliest event from the queue and handle the event until the event queue is empty. A priority queue can be used to implement event queue, where the event with the earliest start time has the higher priority. In the first part of this project, you will implement your own priority queue in two different way:
- MyArrayPriorityQueue: use an unordered array of key values for all potential elements. An enqueue(insertion) operation is fast (O(1)), but the dequeue(deletion) operation requires a linear-time scan of the list.
- MyHeapPrioirtyQueue: because of the frequent dequeue operation, a faster implementation is to use heap data structure. Both an enqueue(insertion) and dequeue(deletion) operation take O(log_2 n) time with a binary heap structure.
- Your priority queue should be able to support any comparable type of elements.
- Your submission should include the source code for two priority queue class, and a driving class to test your priority queue, with both string and integer elements.
- You are not allowed to use priority queue data structure provided by Java library directly. However, you can use array, arraylist, vector, list to implement your priority queue.
- An explanation of priority queue implementation can be found here
- Find here a sample java code: TestQueue.java, MyArrayPriorityQueue.java, Name.java, CompareName.java

(Due: April 10) Part 2: implement a discrete event simulator for CPU scheduling with two simple scheduling algorithms: FCFS(first come first serve) and SJF(Shortest Job First).
- Assumptions of our simulator. In this project, the simulator is only required to support UP(uniprocessor) mode. This simple CPU scheduling simulator is not required to simulate the I/O operation, I/O waiting state, or interrupts. Admission control is not needed either. We assume time is represnted as the number of basic time unit in integer starting at 0.
- Discrete Event Simulator(DES). In DES, 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. In this project, you need implement CPU scheduling simulator as a DES. Comparing with time-driven simulator, DES is usually more efficient. In this CPU scheduling simulator, there are mainly two events: process arrival (new job event) and process departual (job terminate). Event event is associate with a process which may results a stat change among ready, running, and exit. Each event has at last three attributes: time, event type, and associated process. The events are ordered in the event list based on their time. The simulation is basically a main loop of handling each event in the event list in order until all events are handled.
- Object-Oriented Design: We will use object-oriented design to implement this project in Java (or C++ if you want). The classes invovled in the projects are: Project (has only one main method), CPUSchedSimulator, Scheduler, Event, Process etc. The relationship between classes will be described in the lab in detail. Basically, CPUSchedSimulator contains Scheduler, and Event Queue. Scheduler contains Process queue. In the main method in Project class, simulator object is created and the run simulator function will be called to handle all the events in the event list.
- Inheritance and Polymorphsim: This simulator intends to build a generate framework to support different scheduling policy. Inheritance and polymorphsim concepts will be implemented in this project to enable the extensibility of the simulator. For example, Scheduler class will provide a general interface for all different scheduler. Each scheduling algorithm can be implemented as a subclass of Scheduler. Since FCFS algorithm only need use FIFO queue which has O(1) time complexity for enqueue and dequeue operation. A seperate MyFifoQeueu class should be define. Both MyFifoQueue and MyPrioirtyQueue should implement a general interface MyQueue which can be used in class Scheduler. Different comparator should be provided in different scheduling policy to enable the prirority queue in different order.
- The handling of simultaneous events. In DES, several events may occur at the same time. For example, there might be several processes arrived at the same time. A process's arrival might be at the same time as another process's departure. Such cases need careful consideration.
- In part 2, your simulator should output the performance of each scheduling algorithm in terms of each process's turnaround time and waiting time, total(average) turnaround time and waiting time. It should also output the sequence of event handling to show how the scheduling algorithm is executed. A simple configuration file of the process is provided as the input of your simulator(processInfo). A thorough test of your simulator is to use a randomly generated process set as workload.
- Some incompleted source code of the simulator is provided here(lab3_part2.tar). You can use it directly as part of your simulator, or you can just use it as a reference for your simulator. Besides completing the provided code, you also need define several other classes: FcfsScheduler, SjfScheduler, which should be subclass of Scheduler. MyFifoQueue and MyPrioirityQueue should implement MyQueue interface.
- Here is a sample output using FCFS scheduling algorithm:
```
Time 0: new job event process pid: 1 arrival: 0 serviceTime :6 periods 1 interval 0 next event true
Time 0: new job event process pid: 2 arrival: 0 serviceTime :4 periods 1 interval 0 next event false
Time 0 : run process pid: 1 arrival: 0 serviceTime :6 periods 1 interval 0
Time 2: new job event process pid: 4 arrival: 2 serviceTime :1 periods 1 interval 0 next event false
Time 3: new job event process pid: 3 arrival: 3 serviceTime :2 periods 1 interval 0 next event false
Time 6: terminate job event processpid: 1 arrival: 0 serviceTime :6 periods 1 interval 0 next event false
Time 6 : run process pid: 2 arrival: 0 serviceTime :4 periods 1 interval 0
Time 10: terminate job event processpid: 2 arrival: 0 serviceTime :4 periods 1 interval 0 next event false
Time 10 : run process pid: 4 arrival: 2 serviceTime :1 periods 1 interval 0
Time 11: terminate job event processpid: 4 arrival: 2 serviceTime :1 periods 1 interval 0 next event false
Time 11 : run process pid: 3 arrival: 3 serviceTime :2 periods 1 interval 0
Time 13: terminate job event processpid: 3 arrival: 3 serviceTime :2 periods 1 interval 0 next event false

Process 1 turnaround time: 6 waiting time: 0
Process 2 turnaround time: 10 waiting time: 6
Process 3 turnaround time: 10 waiting time: 8
Process 4 turnaround time: 9 waiting time: 8
total turnaround time: 35
total waiting time: 22
```

(Due: April 29) Part 4: Implement another preemptive scheduling algorithm, SRT (Shortest Remaining Time), and Empirically evaluate the performance of different scheduling algorithms, including waiting time/turnaround time and time overhead-
- Implement the preemptive scheduling algorithm SRT.
  - Need to check if the preemption is needed, when a new process arrives.
  - If the preemption is needed, scheduler is called to find a new process to run, at the same time, reinsert current running process in the ready queue.
  - Delete the termination event of the previous running process in the event queue.
- Empirically evaluate the scheduling algorithms
  - For each experiment, randomly generate 100 processes with different arrival time and execution time. The arrival interval and execution time follow an exponential distribution with mean as 10 and 9 respectively (Thus the average utilization of the system is 90%). Run each scheduling algorithms on the same process set. Run 100 experiments and get the average value of all metrics (100 different process set).
  - There are two types of performance metrics to evaluate different scheduling algorithms: waiting time/turnaround time, time overhead in terms of basic operation numbers and real time. Beside, two different implementation, array priority queue, and heap priority queue are used for process ready queue and the time overhead of these two different implementation should also be compared.
```
import java.util.Random;
  import java.lang.Math;

   int expRandom(int mean)
   {
       int exp = 0;
       double unif = 0;
       Random generator = new Random();
       while (exp == 0) {
          // generate a random real number uniformly distributed between 0 and 1
          unif = generator.nextDouble();
          //Convert to a random number that exponential distributed with certain mean
          exp = (int)(-1.0 * Math.log (unif) * (double) mean);
        }
        return exp;
    }
```

Submission

A hard copy of the source code and output of all your programs. You should use command ``a2ps'' or ``enscript -2rG'' to print them in two columns.
A hard copy of your lab report written in Latex. It should include the following contents:
- Section 1 Introduction: a brief description of the problem and the purpose of the lab.
- Section 2 Implementation: a brief description of how to implement the algorithms to calculate Fibonacci numbers, and how to measure the time overhead.
- Section 4 Analysis: a brief description of the theoretical analysis of the algorithm.
- Section 3 Empirical Evaluation: a detailed description of your experiment setup, performance metrics, sample input, and analysis of experiment result.
- Section 5 Conclusion

Link to this Page

Lab Handouts & Assignments last edited on 11 April 2008 at 8:44 am by aldenv29.allegheny.edu