CODE: #include <stdlib.h> #include <stdio.h> struct task{//process int id;//pid
ID: 3776679 • Letter: C
Question
CODE:
#include <stdlib.h>
#include <stdio.h>
struct task{//process
int id;//pid
int bt;//burst time
int at;//arrival time
int pr;//priority
};
typedef struct task Task;
typedef Task *TaskPtr;
struct qnode{//a node in the run/ready queue
Task data;//process
struct qnode *nextPtr;
};
typedef struct qnode Qnode;
typedef Qnode *QnodePtr;
void enqueue(QnodePtr *headPtr, QnodePtr *tailPtr,Task task);
Task dequeue(QnodePtr *headPtr, QnodePtr *tailPtr);
int isEmpty(QnodePtr headPtr);
void enqueue(QnodePtr *headPtr, QnodePtr *tailPtr,Task task){
QnodePtr newNodePtr = malloc( sizeof( Qnode));
if(newNodePtr !=NULL){
newNodePtr->data = task;
newNodePtr->nextPtr = NULL;
}
QnodePtr current = *headPtr, prev = NULL;
while(current!=NULL && task.bt>=(current->data).bt){
prev = current;
current = current->nextPtr;
}
if(prev==NULL){
newNodePtr->nextPtr= *headPtr;
*headPtr=newNodePtr;
}
else{
newNodePtr->nextPtr=prev->nextPtr;
prev->nextPtr=newNodePtr;
}
if(newNodePtr->nextPtr==NULL){
*tailPtr = newNodePtr;
}
}
Task dequeue(QnodePtr *headPtr, QnodePtr *tailPtr){
Task value;
QnodePtr tempPtr;
value = (*headPtr)->data;
tempPtr = *headPtr;
*headPtr = (*headPtr)->nextPtr;
if(*headPtr == NULL){
*tailPtr = NULL;
}
free (tempPtr);
return value;
}
int isEmpty(QnodePtr headPtr){
return headPtr == NULL;
}
///////////////////////////////////////////////
struct event{//an event event
int type;//event type 0:arrival, 1: departure
int time;//event time
Task task;//the process
};
typedef struct event Event;
typedef Event *EventPtr;
struct eventQnode{//an node in the events list
Event data;//the event
struct eventQnode *nextPtr;
};
typedef struct eventQnode EventQnode;
typedef EventQnode *EventQnodePtr;
void enqueueevent(EventQnodePtr *headPtr, EventQnodePtr *tailPtr,Event e);
Event dequeueevent(EventQnodePtr *headPtr, EventQnodePtr *tailPtr);
int isEmptyEQ(EventQnodePtr headPtr);
void displayEvents(EventQnodePtr currentPtr);
void enqueueevent(EventQnodePtr *headPtr, EventQnodePtr *tailPtr,Event se){
EventQnodePtr newNodePtr = malloc( sizeof( EventQnode));
if(newNodePtr !=NULL){
newNodePtr->data = se;
newNodePtr->nextPtr = NULL;
}
EventQnodePtr current = *headPtr, prev = NULL;
while(current!=NULL && se.time>(current->data).time){//find the insert position in order of time
prev = current;
current = current->nextPtr;
}
while(current!=NULL && se.time==(current->data).time && se.type<(current->data).type){//then find the insert position in order of event's type
prev = current;
current = current->nextPtr;
}
if(prev==NULL){
newNodePtr->nextPtr= *headPtr;
*headPtr=newNodePtr;
}
else{
newNodePtr->nextPtr=prev->nextPtr;
prev->nextPtr=newNodePtr;
}
if(newNodePtr->nextPtr==NULL){
*tailPtr = newNodePtr;
}
}
Event dequeueevent(EventQnodePtr *headPtr, EventQnodePtr *tailPtr){
Event value;
EventQnodePtr tempPtr;
value = (*headPtr)->data;
tempPtr = *headPtr;
*headPtr = (*headPtr)->nextPtr;
if(*headPtr == NULL){
*tailPtr = NULL;
}
free (tempPtr);
return value;
}
int isEmptyEQ(EventQnodePtr headPtr){
return headPtr == NULL;
}
void displayEvents(EventQnodePtr currentPtr){
if(currentPtr==NULL)
printf("The event list is empty ... ");
else{
printf("The event list is: ");
Event tempevent;
while(currentPtr!=NULL){
printf(" time: %d, type : %d : task(id:%d,bt:%d) ",
(currentPtr->data).time, (currentPtr->data).type, (currentPtr->data).task.at,(currentPtr->data).task.bt);
currentPtr=currentPtr->nextPtr;
}
}
}
///////////////////////////////////////////////
const int MAXTASKS = 10;
const int MAXBURSTTIME = 70;
const int IAT = 30;
void main(){
QnodePtr rqheadPtr=NULL, rqtailPtr=NULL;//the run/ready queue
EventQnodePtr eventsQheadPtr=NULL, eventsQtailPtr=NULL;//the event queue/list
Task task;//the process structure
Event event;//the event structure
int prevat = 0, i;//set the previous arrival time to zero
for(i=0;i<MAXTASKS;i++){//generate all arrivals and insert them in the event list
//fill up the info of the process structure
task.id=i;
task.at=rand()%IAT+prevat;
prevat=task.at;
task.bt=rand()%MAXBURSTTIME+1;
//fill up the info of the event structure
event.type=0;//event type is 0:arrival
event.time=task.at;//event time
event.task=task;//note that the process is encapsulated in an event structure
enqueueevent(&eventsQheadPtr,&eventsQtailPtr,event);//insert the event in the events list
}
displayEvents(eventsQheadPtr);//Display the events list of all arrivals before starting the simulation
int clock=0;//the sim clock time is currently 0
int idle=1;//CPU is initially idle
Event currentEvent;//to hold the current event
int wt=0;//waiting time
int idletime=0;//CPU idel time
printf(" Time: %d: Simulation is started ... ",clock);
while(!isEmptyEQ(eventsQheadPtr)){
currentEvent = dequeueevent(&eventsQheadPtr,&eventsQtailPtr);//get an event from the events list
clock=currentEvent.time;//
if(currentEvent.type==1){//Departure logic
idle=1;
task = currentEvent.task;
printf(" Time: %d : Departure : task(id:%d,bt:%d) has finished. ", clock, task.id,task.bt);
}
if(currentEvent.type==0){//Arrival logic
task = currentEvent.task;
printf(" Time: %d : Arrival : task(id:%d,bt:%d). ", clock, task.id,task.bt);
enqueue(&rqheadPtr,&rqtailPtr,task);
}
if(idle==1 && !isEmpty(rqheadPtr)){//Service logic
idle = 0;
currentEvent.task=dequeue(&rqheadPtr,&rqtailPtr);
wt+=clock-currentEvent.task.at;
currentEvent.type=1;
currentEvent.time=clock+currentEvent.task.bt;
enqueueevent(&eventsQheadPtr,&eventsQtailPtr,currentEvent);
task = currentEvent.task;
printf(" Time: %d : Serving : task(id:%d,bt:%d). ", clock,task.id,task.bt);
}
}
printf(" Simulation has finished. ");
printf(" Results: ");
printf("Total tasks served = %d. ", MAXTASKS);
printf("Average wating time for all processes = %f ",(double)wt/MAXTASKS);
}
Explanation / Answer
#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);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.