The purpose of this programming project is to gain some experience involving the design of a few OS components by simulation. These components include CPU management and scheduling, process management, system queues, system statistics gathering and reporting.

System Description:

The User Processes:
All processes created in this system fall under any one of the following types:
Type-1: Consists of:
10 CPU bursts of the following lengths: (1,2,1,1,1,3,1,2,2,1) Time Units,
9 I/O bursts of the following lengths: (6,4,10,3,5,3,2,10,6) Time Units.
Type-2: Consists of:
15 CPU bursts of 50 Time Units each, and
14 I/O bursts of 150 Time Units each.
Type-3: Consists of:
12 CPU bursts of 1000 Time Units each, and
11 I/O bursts of 5 Time Units each.
Type-4: Consists of:
A repeated pattern of (CPU, I/O1, Think, I/O2), where:
Each CPU burst takes 3 Time Units,
Each I/O1 burst takes 3 Time Units,
Each I/O2 burst takes 10 Time Units,
Think time takes 60 Time Units.
Any one of the types above can be created at any time. Type-4 has a maximum of N instances. No new processes of this type can be created after this limit. Processes of Type-1 to Type-3 terminate after executing their last CPU burst, while processes of Type-4 never terminate, they cycle through their pattern forever. Assume that a process in its think period stays out of the Ready Queue, say in a special list.

The Operating System Components:
The OS supports multi-programming and priority-based, pre-emptive CPU-scheduling. Each of the following OS components shall be written by the students participating in this project, according to the specifications given for each component below:

a) A modularly designed generic CPU Scheduler that supports a number of short-term scheduling algorithms including, FCFS, SJF, RR, MLFQ (Multi-Level Feedback Queue of n-levels) and -- for extra credit -- lottery (more about this is given below). Assume that the particular scheduling algorithm to be used in any simulation run is given as an input parameter on the command-line.

Other parameters that are required for a particular scheduler, depends on your design, such as the number-levels of MLFQ, time-quanta, … etc. These are part of your design decisions and they shall be saved in a suitable data-structure for fast access during execution. In particular, designing RR, MLFQ and lottery, you would choose the parameters and data structures to satisfy your goals which must be to achieve the best system performance possible.

b) A Supervisor, its job is to control all system operations, including the timer functions, interrupt handling, preemption decisions, …etc.

c) A Dispatcher, its job is to do the context switching and assign the CPU to the process selected by the CPU scheduler.

d) A Creator, is responsible for creating new processes of a given type. This is done by creating their PCBs and putting them in the ready queue.
e) A Terminator, is responsible for terminating finished processes by removing their PCBs.
f) An I/O Monitor, it is responsible for monitoring the processes completing their I/O. It generates an I/O Completion interrupt to the CPU each time a process finishes its I/O burst. For simplicity of simulation, it also takes the process's PCB to the ready queue.
g) The Job Generator, its purpose is to generate new jobs and select their types randomly, then, calls the creator to create their PCBs and enter them into the system. Job types are selected using an integer random number generator in the range [1,4] that has a uniform distribution over that range. The Java rand() function can be used.
Jobs are assumed to arrive randomly according to Poisson distribution with an expected value, v, in the range [0,1] provided to the program at run time. Use the following Poisson generator at each time step to get the number of new jobs to be created at that time step, then use the random number generator, rand() to get its type.
h) The Poisson Generator: Given an expected value, v, it generates a random integer to be used in the simulation, such that the expected value and Poisson distribution are satisfied. It is assumed that you already seeded the random number generator.
int Poisson (double v) {
double x, em;
int n;
em = Math.exp(-v);
x = rand(); // returns 0 < x < 1
n = 0;
while (x > em) {
n++;
x *= rand();
}
return n;
}

A Statistics-Collecting Module, used to keep record of important information about the system and report the following statistics about the simulation run:
1- The total number of time-units used.
2- The total number of jobs created.
3- The total number of each job-type created.
4- The total number of each job-type terminated.
5- The Maximum, and Average queue-lengths for each of the queues in the system.
6- The Minimum, Maximum, and Average response-times for jobs of Type-4 only.
7- The Minimum, Maximum, and Average turnaround-times for each job type other than Type-4.
8- The Minimum, Maximum, and Average turnaround-times for all jobs other than those of Type-4.
9- The total system throughput for jobs of Type-1 to Type-3.
10- The Minimum, Maximum, and Average of CPU-overhead-time.
11- The Percentage of CPU-idle-time.
12- The Percentage of CPU-utilization.

Assumptions
a) The CPU context-switching time takes 0.1 Time Units. i.e. each 10 take 1 time uint.
b) The SVC-start-I/O-interrupt takes 2 Time Units.
c) I/O-completion-interrupt takes 3 Time Units.
d) Job-scheduling overhead takes 1 Time Unit.
e) All other supervisor activities take 1 Time Unit per call.
f) The time-quantum of RR is left for each group to decide.
g) The MLFQ design parameters as given in class are left for each group to decide.
h) When the MLFQ is used, all processes are initially entered into the first level queue.
i) The response-time is defined for Type-4 jobs only, as the total time period spent from the end of I/O2 operation to the start of I/O1 operation. This includes the CPU-burst time, CPU-overhead and all queue delays during this period.

What to do
Write a Java program to simulate the above system. The input to the program should be through command-line parameters as follows:
1. The total number of time steps for the run, S, integer > 100; default = 100.
2. The ready queue type, integer, 1:FCFS, 2:SJF, 3:RR, 4:MLFQ, 5:lottery; default = 1.
3. The minimum quantum size, Q, to use as a basis of RR and MLFQ, integer > 0; default = 1.
4. The maximum number of Type-4 jobs, N, integer [0 .. 100]; default = 5.
5. The expected number of new jobs arriving per time unit, v, double [0 .. 1]; default = 0.5.
6. If implemented, the minimum number of tickets, t, integer > 0; default = 5.
7. If implemented, the maximum number of tickets, T, integer > t; default = 100.
8. If implemented, the speed of giving/taking tickets, c , multiple of Q, integer > 0; default = 0.
Choose an appropriate value for Q and v, Let N=20 and S=100,000 and run your program 5 times using the same values of Q, v, N, and S but each time with a different Queue type. Also, if implemented, choose suitable values for lottery parameters, t, T and c. Show the contents of all system queues, only for the first 20 time steps. After each run, your output should also show all your input values, the queue type used, and all the statistics reported by the statistics-collecting module.