This assignment will provide you with greater familiarity with the scheduling of
ID: 3855382 • Letter: T
Question
This assignment will provide you with greater familiarity with the scheduling of processes by an
operating system. You will also get a little experience with the implementation of a simulation program that deals only with discrete events (that is, events that occur at well-defined times). In particular, you are to implement a single program that implements a simulation of processes executing with the scheduling policy described below.
In a discrete event simulation, a system is modeled as a sequence of individual events. Each such event occurs at a specified time, but that time is often dependent on other (previous) events in the system. In our simulation the events with which we’re concerned are those that affect the scheduling of processes – events that affect the movement of a process from one state to another. In a real system activities take place between these process state changes – a process performs some computation, or an input/output device does work on behalf of a process. But in this simulation we’re not interested in modeling those acitivites, but only the process scheduling state changes.
Each process in a simulation will exist in one of five states: not-yet-submitted, ready, running, blocked, and completed. Although not-yet-submitted and completed are not normally considered process states, including them here will make it easier to understand the scheduling algorithm. All processes begin in the not-yet-submitted state.
Each process moves from the not-yet-submitted state to the ready state at the time specified (in the input data, described later) for its submission. At some point the scheduler will select a process for execution and move it to the running state. Each process is described by six integer input parameters: the unique process identification (pid), the process priority (prio), the time when the process is submitted (submit), the total CPU time required for the computation (totcpu), the length of time a process computes (that is, actively uses the CPU) before requesting some input/output (cpu), and the length of time required for each input/output operation (io).
Once submitted, a process will alternate between doing some computation (for the time specified by cpu) and doing I/O (for the time specified by io) until it has accumulated the total CPU time required (as specified by totcpu). Of course, we don’t really care about the details of the computation or I/O done by each process; we’re only concerned about the time required to complete these activities, and making certain the CPU resources are appropriately assigned to the processes.
For example, suppose there is only a single process in the system, and it was submitted at time 0. It has a total CPU time requirement of 20 time units (TUs, which are arbitrary units of time), a compute time of
5 TU, and an I/O time of 50 TU. After computing for 5 TU, it will become blocked for 50 TU (for I/O), then compute again for 5 TU, then become blocked again for 50 TU (for more I/O), and so forth. The process will complete execution at time 170, after being blocked for a total of 150 TU. Remember that this example has only a single process.
Of course there may be more than one process, more than one CPU, and a quantum size less than infinite. In the previous example (with only one process), it makes no difference if we have additional CPUs, or if the quantum size is less than 5 TU; note that we’re also assuming a context switch is free – it takes no time! Suppose, however, we have two identical processes, each submitted at time 0, a quantum size of 4 TU, and a single CPU. The first process, after running for 4 TU, will experience quantum runout (or expiration), and will be preempted – it will be moved back to the ready state. Note that this process still needs one TU’s worth of CPU time before it can begin doing I/O. Also at time 4 the second process will be allowed to run, for 4 TU, of course, since the CPU became available for use as the result of preempting the first process. At time 8 the second process will experience quantum runout, and be moved back to the ready state; it also still needs one TU of CPU time before it can begin doing I/O. Also at time 8 the first process will again be allowed to use the CPU. This time it only needs one TU before it begins doing I/O. So, at time 9, (a) the first process is moved to the blocked state (where it will remain until time 59 while its I/O operation is performed), and (b) the second process will move to the running state. You should convince yourself that the first process will complete execution at time 186, with the second process finishing at time 187.
The following set of steps provides a reasonably concise, well-defined behavior for the scheduling and processing of processes in this system. The only undefined behavior is associated with, for example, two processes with the same priority both being ready for execution at the same time (for example, they were both submitted at the same time). Note that the ordering of processes in the queues is usually well- defined by the following steps. If any ambiguity ever arises, however, your simulation should always first select the process with the smallest process ID. For example, if processes 10 and 15 have the same priority and are both submitted at time 0, process 10 will be selected to run first.
Simulation Procedure
Your simulation will be controlled by a simulation time, T, and the set of events that occur at the current
simulated time. This is not a real time, so do not attempt to synchronize your simulation with any system timing features. One of the primary positive features of simulation is that it can usually be done much faster than doing the “real” activity, and that is certainly true for this simulation. Also note that it is inappropriate to use multiple processes or threads for this simulation; the processes with which your program is dealing are simulated – not real!
The initial time for the simulation is, of course, 0. But since nothing happens until the first process is submitted, the simulation time will “jump” to the time of that submission (see step 2). At that time, the simulation processes all events that occur at that time. The various events that are possible in this simulation are as follows:
A “new” process is submitted (moved from the not-yet-submitted state to the ready state)
A running process completes all of its input/output and computation, and moves from the
running state to the completed state
A running process uses all of its current execution quantum (and still has more execution to do before it starts doing input/output), so it moves from the running state to the ready state
A running process finishes with its current computation effort and begins doing input/output, and is moved from the running state to the blocked state)
A blocked process finishes its input/output and moves from the blocked state to the ready
state
A CPU becomes available, and if there is an available ready process, it is selected for execution, moving from the ready state to the running state
A process with a priority higher than that of the running process is moved to the ready state (either from the blocked state, or from the not-yet-submitted state); it should preempt the currently running process.
Here are the steps you should follow in simulating the scheduling of the processes in each simulation.
1. Read the data describing the system (number of CPUs, number of processes, and quantum size), and the parameters describing each of the processes in the next simulation, placing the processes in the not-yet-submitted state. Set the ready, running, blocked, and completed process sets to empty. [Although the word sets is used here, you will likely want to represent these sets as queues in your solution.]
2. Set the simulation time (T) to the earliest time of any process in the not-yet-submitted state. (Recall that all processes are initially in the not-yet-submitted state, so this is really the smallest/earliest submission time of any process.)
3. If a running process completes execution at time T, then move it from the running state to the completed state. If all processes have now completed execution, the simulation terminates after displaying all desired statistical information.
4. If any blocked process completes its input/output at time T, then move it from the blocked state to the ready state; logically it is placed at the end of the queue associated with its priority.
5. If any not-yet-submitted process is to be submitted at time T, add it to the set of ready processes
(again, logically at the end of the queue associated with its priority).
6. If a running process completes its current computation cycle (before doing I/O) at time T, then move it from the running state to the blocked state.
7. If the quantum for a running process expires at time T, then move the process to the ready state
(at the end of the queue associated with its priority).
8. For each idle CPU, move a process from the ready state to the running state. The process that is moved first is logically that which is at the head of the highest priority non-empty ready queue. Of course, it is possible that there may be too few ready processes to assign one to each idle CPU. In that case, the idle CPU remains idle.
9. Check for the possibility that one (or more) of the running processes currently assigned to a CPU should be preempted because there is a higher-priority ready process. The details of this are described below in Preemption.
10. Advance the simulation time to the time of the next event (those associated with steps 3 through
7), update data for the running and blocked processes, and repeat from step 3.
Preemption
Deciding which process (or processes) to preempt (if any) must be done carefully. Here is the procedure
you should follow:
1. If there are no ready processes, then there will obviously be no (further) preemptions.
2. If there are no running processes, then there will obviously be no (further) preemptions, either!
3. Select a running process that might be preempted. This is the running process with the smallest/lowest priority, with the least running time in this quantum, on the lowest-numbered CPU. [This uniquely identifies a process that might be preempted. Even if there were two processes with the same (lowest) priority, each of which had accumulated the same amount of running time in the current quantum, only one of them will uniquely be on the lowest-numbered CPU.]
4. If the process selected in step 3 has a priority smaller than that of the ready process with the highest priority, then do the preemption (as described below). Otherwise, there will be no (further) preemptions.
a. Move the process being preempted (the one selected in step 3) back to the ready state
(logically at the end of the appropriate queue for its priority).
b. Move the highest-priority ready process to the running state where it will used the just- vacated CPU.
5. Repeat from step 1.
Input Data
The input, which is to be read from the standard input, contains descriptions of one or more simulations;
the simulations are numbered sequentially starting with 1.
The input for each simulation begins with a line containing three integers. In order, they are:
- the nubmer of CPUs in the system, ncpu (1 ncpu 4)
- the number of preocesses, np(1 np 25), and
- the quantum size, quant (quant >= 1)
Following the first line there will appear one line for each of the np processes. Each line contains siz integers. In order, they are:
- the unique process identification, pid (1 pid 999)
- the process priority, prio (1 prio 10)
- the time of submission, submit (submit >= 0)
-the total CPU time required for the process to complete, totcpu (1 totcpu 1000)
- the compute time required before the next input/output operation is needed, cpu (1 cpu 100)
- the input/output time rquired for a single I/O operation, io (1 io 1000)
The end of the input data is indicated by the end of file immediately after the input for the last simulation.
Output Format
For each simulation, first display the simulation number (1, 2, …) and the input data in a reasonable
format (an acceptable format is shown below). When a simulation is complete, display the following statistical information:
1. For each process, in ascending process identification (pid) order, display its completion time and its turnaround time (that is, the difference between the time of submission and the completion time).
2. Display the average idle time for the set of CPUs. For each individual CPU, the idle time is the time it was not actively executing any process prior to time of completion of the last process
(regardless of the CPU on which the last process was executing). The average idle time over all
CPUs is just the sum of the idle time for each CPU divided by the number of CPUs.
3. Display the average percentage of the time the CPUs were idle. This is just the average idle time
(as computed for output item 2) divided by the time of completion of the last process, times 100.
4. Display the average turnaround time for all processes.
Sample Input
1 1 10
1 1 0 20 5 50
Expected Output
Simulation # 1
-------------- Input:
1 CPU, 1 process, quantum size = 10
PID 1, prio = 1, submit = 0, totCPU = 20, CPU = 5, I/O = 50
Output:
PID 1 completed execution at 170, turnaround time = 170
Average CPU idle time = 150 (88%) Average process turnaround time = 170
Notes and Restrictions
You are not restricted to using only system calls for input/output in this assignment. In fact, it is strongly recommended that you use the I/O facilities provided by the standard library for the programming
language you use for your solution.
Do, however, remember that the input is to be read from the standard input. When your solution is tested, the standard input will likely be redirected to an input data file from the command line (for example, “./prog2 <prog2.input”, but your solution is not to do any input or output to files other than the standard input and standard output.
The limits specified in the input data section are guaranteed. For example, you do not need to verify that the number of processes is in the range 1 to 25.
Ensure that your program can handle multiple simulations in a single execution. The test data used to evaluate your solution will consist of multiple simulation descriptions in a single file. This will require that you guarantee appropriate initialization of data at the beginning of each simulation.
Also ensure that your program can handle redirection of the standard input to a data file. The test data used to evaluation your solution will be provided to your program by running it with its standard input redirected to the data file.
Explanation / Answer
#include<stdio.h>
struct process
{
char name;
int at,bt,wt,tt,rt;
int completed;
float ntt;
}p[10];
int n;
int q[100]; //queue
int front=-1,rear=-1;
void enqueue(int i)
{
if(rear==100)
{
printf("overflow");
return 0;
}rear++;
q[rear]=i;
if(front==-1)
front=0;
}
int dequeue()
{
if(front==-1)
{
printf("underflow");
return 0;
} int temp=q[front];
if(front==rear)
front=rear=-1;
else
front++;
return temp;
}
int isInQueue(int i)
{int k;
for(k=front;k<=rear;k++)
{
if(q[k]==i)
return 1;
}
return 0;
}void sortByArrival()
{
struct process temp;
int i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(p[i].at>p[j].at)
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
}
void main()
{
int i,j,time=0,sum_bt=0,tq;
char c;
float avgwt=0;
printf("Enter no of processes:");
scanf("%d",&n);
for(i=0,c='A';i<n;i++,c++)
{
p[i].name=c;
printf(" Enter the arrival time and burst time of process %c: ",p[i].name);
scanf("%d%d",&p[i].at,&p[i].bt);
p[i].rt=p[i].bt;
p[i].completed=0;
sum_bt+=p[i].bt;
}
printf(" Enter the time quantum:");
scanf("%d",&tq);
sortByArrival();
enqueue(0); // enqueue the first process
printf("Process execution order: ");
for(time=p[0].at;time<sum_bt;) // run until the total burst time reached
{ i=dequeue();
if(p[i].rt<=tq)
{ // for processes having remaining time with less than or equal time quantum
time+=p[i].rt;
p[i].rt=0;
p[i].completed=1;
printf(" %c ",p[i].name);
p[i].wt=time-p[i].at-p[i].bt;
p[i].tt=time-p[i].at;
p[i].ntt=((float)p[i].tt/p[i].bt);
for(j=0;j<n;j++) // enqueue the processes which have come while scheduling
{
if(p[j].at<=time && p[j].completed!=1&& isInQueue(j)!=1)
{
enqueue(j);
}
}
}
else // more than time quantum
{
time+=tq;
p[i].rt-=tq;
printf(" %c ",p[i].name);
for(j=0;j<n;j++) //enqueue the processes which have come scheduling first
{
if(p[j].at<=time && p[j].completed!=1&&i!=j&& isInQueue(j)!=1)
{
enqueue(j);
}
}
enqueue(i); // then enqueue the uncompleted process
}
}
printf(" Name Arrival Time Burst Time Waiting Time TurnAround Time Normalized TT");
for(i=0;i<n;i++)
{avgwt+=p[i].wt;
printf(" %c %d %d %d %d %f",p[i].name,p[i].at,p[i].bt,p[i].wt,p[i].tt,p[i].ntt);
}
printf(" Average waiting time:%f ",avgwt/n);
}
OR
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
class cpuschedule
{
int n,bu[20];
float twt,awt,wt[20],tat[20];
public:
void Getdata();
void fcfs();
void sjf();
void roundrobin();
};
//Getting no of processes and Burst time
void cpuschedule::Getdata()
{
int i;
cout<<“Enter the no of processes:”;
cin>>n;
for(i=1;i<=n;i++)
{
cout<<“ Enter The BurstTime for Process p”<<i<<“=”;
cin>>bu[i];
}
}
//First come First served Algorithm
void cpuschedule::fcfs()
{
int i,b[10];
float sum=0.0;
twt=0.0;
for(i=1;i<=n;i++)
{
b[i]=bu[i];
cout<<“ Burst time for process p”<<i<<“=”;
cout<<b[i];
}
wt[1]=0;
for(i=2;i<=n;i++)
{
wt[i]=b[i-1]+wt[i-1];
}
for(i=1;i<=n;i++)
{
twt=twt+wt[i];
tat[i]=b[i]+wt[i];
sum+=tat[i];
}
awt=twt/n;
sum=sum/n;
cout<<“ Total Waiting Time=”<<twt;
cout<<“ Average Waiting Time=”<<awt;
cout<<“ Average Turnaround time=”<<sum;
}
//Shortest job First Algorithm
void cpuschedule::sjf()
{
int i,j,temp,b[10];
float sum=0.0;
twt=0.0;
for(i=1;i<=n;i++)
{
b[i]=bu[i];
cout<<“ Burst time for process p”<<i<<“=”;
cout<<b[i];
}
for(i=n;i>=1;i–)
{
for(j=2;j<=n;j++)
{
if(b[j-1]>b[j])
{
temp=b[j-1];
b[j-1]=b[j];
b[j]=temp;
}
}
}
wt[1]=0;
for(i=2;i<=n;i++)
{
wt[i]=b[i-1]+wt[i-1];
}
for(i=1;i<=n;i++)
{
twt=twt+wt[i];
tat[i]=b[i]+wt[i];
sum+=tat[i];
}
awt=twt/n;
sum=sum/n;
cout<<“ Total Waiting Time=”<<twt;
cout<<“ Average Waiting Time=”<<awt;
cout<<“ Average turnaround time=”<<sum;
}
//Round Robin Algorithm
void cpuschedule::roundrobin()
{
int i,j,tq,k,b[10],Rrobin[10][10],count[10];
int max=0;
int m;
float sum=0.0;
twt=0.0;
for(i=1;i<=n;i++)
{
b[i]=bu[i];
cout<<“ Burst time for process p”<<i<<“=”;
cout<<b[i];
if(max<b[i])
max=b[i];
wt[i]=0;
}
cout<<“ Enter the Time Quantum=”;
cin>>tq;
//TO find the dimension of the Round robin array
m=max/tq+1;
//initializing Round robin array
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
Rrobin[i][j]=0;
}
}
//placing value in the Rrobin array
i=1;
while(i<=n)
{
j=1;
while(b[i]>0)
{
if(b[i]>=tq)
{
b[i]=b[i]-tq;
Rrobin[i][j]=tq;
j++;
}
else
{
Rrobin[i][j]=b[i];
b[i]=0;
j++;
}
}
count[i]=j-1;
i++;
}
cout<<“Display”;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cout<<“ Rr[“<<i<<“,”<<j<<“]=”<<Rrobin[i][j];
cout<<” “;
}
cout<<“ count=”<<count[i];
}
for(j=1;j<=n;j++)
{
for(i=1;i<=count[j];i++)
{
if(i==count[j])
{
for(k=1;k<j;k++)
{
if(k!=j)
wt[j]+=Rrobin[k][i];
}
}
else
for(k=1;k<=n;k++)
{
if(k!=j)
wt[j]+=Rrobin[k][i];
}
}
}
for(i=1;i<=n;i++)
cout<<“ Waiting Time for process P”<<i<<“=”<<wt[i];
//calculating Average Weighting Time
for(i=1;i<=n;i++)
{
twt=twt+wt[i];
tat[i]=b[i]+wt[i];
sum+=tat[i];
}
awt=twt/n;
sum=sum/n;
cout<<“ Total Waiting Time=”<<twt;
cout<<“ Average Waiting Time=”<<awt;
cout<<“ Average turnaround time=”<<sum;
}
void main()
{
int ch=0,cho;
cpuschedule c;
clrscr();
do
{
switch(ch)
{
case 0:
cout<<“ 0.MENU”;
cout<<“ 1.Getting BurstTime”;
cout<<“ 2.FirstComeFirstServed”;
cout<<“ 3.ShortestJobFirst”;
cout<<“ 4.RoundRobin”;
cout<<“ 5.EXIT”;
break;
case 1:
c.Getdata();
break;
case 2:
cout<<“FIRST COME FIRST SERVED SCHEDULING”;
c.fcfs();
break;
case 3:
cout<<“SHORTEST JOB FIRST SCHEDULING”;
c.sjf();
break;
case 4:
cout<<“ROUND ROBIN SCHEDULING”;
c.roundrobin();
break;
case 5:
break;
}
cout<<“ Enter your choice:”;
cin>>ch;
getch();
}while(ch<5);
}