-
Notifications
You must be signed in to change notification settings - Fork 0
/
multiproc_sche.cpp
148 lines (142 loc) · 3.7 KB
/
multiproc_sche.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// FCFS Number of CPUs are assumed to be 3 but it could be modified
#include <iostream>
#include <conio.h>
using namespace std;
struct Process
{
int at;
int threads;
int ct;
}processes[10];
struct Thread
{
int pid;
int at;
int bt;
int ft;
int CPU_id;
}threads[25];
int CPU[]={0,0,0}, n,tc;
int main()
{
int findFreeCPUCount(int);
int dispatcher(int);
int NextAvailableTime();
void display();
int completed;
cout <<"Enter the no of processes:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Enter arrival time of "<<i<<"th process: ";
cin>>processes[i].at;
cout<<"Enter no of theads: ";
cin>>processes[i].threads;
for(int j=0;j<processes[i].threads;j++)
{
threads[tc].at=processes[i].at;
threads[tc].pid=i;
cout<<"Enter the service time of T"<<j<<": ";
cin>>threads[tc].bt;
tc++;
}
}
int ct=0, FreeCPUCount=3;
while(completed < tc)
{
FreeCPUCount= findFreeCPUCount(ct);
if(FreeCPUCount == 0) // If no CPU is free then update the current time with next time at which a CPU will become free
{
ct= NextAvailableTime();
}
while(FreeCPUCount > 0 && completed < tc ) // One or more CPUs are free and not all the threads are completed
{
int tid=dispatcher(ct); // Choose the next thread to schedule
if(tid != -1) // A thread is ready for execution at the current time
{
for(int i=0;i<3;i++) //Identify a CPU that is free right now
{
if(CPU[i] <= ct) // To find whether the ith CPU is currently free
{
CPU[i]=ct+threads[tid].bt; // Allocate the ith CPU to thre thread tid
threads[tid].bt=0; // Thread completed and will not be considered again for scheduling
threads[tid].ft= CPU[i]; // Finish time is calculated as current time + service time which is already calculated into CPU[i]
threads[tid].CPU_id = i; // The particular CPU on which the thread is executed is noted
FreeCPUCount--; // No of free CPU is decremented by one
completed++; // No of completed threads incremented by one
break; // Scheduling of the thread is over and so break the for loop
}
}
}
else // Increment current time and try to find ready threads
{
ct++;
}
}
ct++; // Increment current time
}
display();
getch();
}
int dispatcher(int ct)
{
for(int i=0;i<tc;i++)
{
if(threads[i].at <= ct && threads[i].bt != 0) // Find the thread that has arrived at the current time & it is not yet completed
{
return i;
}
}
return -1;
}
int findFreeCPUCount(int ct) // To count the number of CPUs that are currently free/available
{
int count=0;
for(int i=0;i<3;i++)
{
if(CPU[i]<=ct) count++;
}
return count;
}
int NextAvailableTime() // When is the nearest time that a CPU will become available
{
int tim= 1000;
for(int i=0;i<3;i++)
{
if(CPU[i]<tim)
tim= CPU[i];
}
return tim;
}
void display()
{
int FindCompletionTime(int);
cout<<"TID"<<"\t"<<"FT"<<"\t"<<"CPU Id"<<endl;
for(int i=0;i<tc;i++)
{
cout<<i<<"\t"<<threads[i].ft<<"\t"<<threads[i].CPU_id<<endl;
}
cout<<"PID"<<"\t"<<"CT"<<endl;
for(int i=0;i<n;i++)
{
int ft = FindCompletionTime(i);
cout<<i<<"\t"<<ft<<"\t"<<endl;
}
}
int FindCompletionTime(int pid) // To identify the highest finish time of a thread within process pid
{
int tid=0,ct=0;
if(pid!=0)
{
for(int j=0;j<pid;j++) // To find out the index of the first thread of process pid
{
tid+=processes[j].threads;
}
}
for(int i=0;i<processes[pid].threads;i++) // To find the thread of pid with the maximum finish time
{
if(threads[tid].ft > ct)
ct= threads[tid++].ft;
}
return ct;
}