Multilevel Queue Scheduling
A multilevel queue scheduling is a scheduling algorithm where there are multiple queues for each type of process. The selection of level is done through priority based scheduling while each level queue scheduling are dependent entirely on the type of process. Round robin for upper layers and First come first served for lower layers.
Source Code
/**
* @author Purbayan Chowdhury
* @brief Multilevel Feedback Queue Scheduling Algorithm
*/
#include <bits/stdc++.h>
class process
{
public:
int _id, _atime, _wtime, _ttime, _btime, _priority, _percent;
process(int id = 0, int atime = 0, int btime = 0, int priority = 0) : _id(id), _atime(atime), _btime(btime), _priority(priority), _percent(btime) {}
};
/**
* Q3 = Batch Process having Low Priority with FCFS Algorithm
* Q2 = Interactive Process having Medium Priority with Priority Scheduling
* Q1 = System Process having High Priority with Round Robin Algorithm
*/
std::vector<process *> sortArrivalTime(std::vector<process *> p)
{
int i, j;
process *k;
for (i = 0; i < p.size() - 1; i++)
{
for (j = p.size() - 1; j >= i + 1; j--)
{
if (p[j]->_atime < p[j - 1]->_atime)
{
k = p[j - 1];
p[j - 1] = p[j];
p[j] = k;
}
}
}
return p;
}
int FCFS(std::vector<process *> p, int stime, int etime)
{
int i, c = etime - stime;
if (c <= 0)
return etime;
for (i = 0; i < p.size(); i++)
{
if (p[i]->_percent > c)
{
p[i]->_percent -= c;
return etime;
}
else
{
c = c - p[i]->_percent;
p[i]->_ttime = stime + p[i]->_percent;
stime += p[i]->_percent;
p[i]->_percent = 0;
}
}
return etime - c;
}
std::vector<process *> sortPriority(std::vector<process *> p)
{
int i, j;
process *k;
for (i = 0; i < p.size() - 1; i++)
{
for (j = p.size() - 1; j >= i + 1; j--)
{
if (p[j]->_atime < p[j - 1]->_atime && (p[j]->_atime < p[j - 1]->_atime && p[j]->_priority < p[j - 1]->_priority))
{
k = p[j - 1];
p[j - 1] = p[j];
p[j] = k;
}
}
}
return p;
}
int PR(std::vector<process *> p, int stime, int etime)
{
p = sortPriority(p);
int i, c = etime - stime;
if (c <= 0)
return etime;
for (i = 0; i < p.size(); i++)
{
if (p[i]->_percent > c)
{
p[i]->_percent -= c;
return etime;
}
else
{
c = c - p[i]->_percent;
p[i]->_ttime = stime + p[i]->_percent;
stime += p[i]->_percent;
p[i]->_percent = 0;
}
}
return etime - c;
}
int RR(std::vector<process *> p, int stime, int etime)
{
int i = 0, j, c = etime - stime, ct = p.size();
int quantum = 4;
while (ct != 0 && c != 0)
{
if (c < quantum)
{
if (p[i]->_percent > c)
{
p[i]->_percent -= c;
return etime;
}
else
{
c = c - p[i]->_percent;
p[i]->_ttime = stime + p[i]->_percent;
stime += p[i]->_percent;
p[i]->_percent = 0;
ct--;
}
i++;
if (i == p.size())
break;
}
else
{
if (p[i]->_percent != 0)
{
if (p[i]->_percent > quantum)
{
stime += quantum;
p[i]->_percent -= quantum;
c -= quantum;
}
else
{
stime += p[i]->_percent;
p[i]->_ttime = stime;
c -= p[i]->_percent;
p[i]->_percent = 0;
ct--;
}
}
i++;
i = i % p.size();
}
}
return etime - c;
}
std::vector<int> calculateTime(std::vector<process *> p)
{
std::vector<int> t(2);
t[0] = t[1] = 0;
int i;
for (i = 0; i < p.size(); i++)
{
p[i]->_ttime -= p[i]->_atime;
t[0] += p[i]->_ttime;
p[i]->_wtime = p[i]->_ttime - p[i]->_btime;
t[1] += p[i]->_wtime;
}
return t;
}
void displayTime(std::vector<process *> p)
{
std::cout << std::setfill(' ') << std::setw(10) << "Id"
<< std::setfill(' ') << std::setw(10) << "Priority"
<< std::setfill(' ') << std::setw(10) << "A_Time"
<< std::setfill(' ') << std::setw(10) << "B_Time"
<< std::setfill(' ') << std::setw(10) << "T_Time"
<< std::setfill(' ') << std::setw(10) << "W_Time"
<< std::endl;
for (int i = 0; i < p.size(); i++)
std::cout << std::setfill(' ') << std::setw(10) << p[i]->_id
<< std::setfill(' ') << std::setw(10) << p[i]->_priority
<< std::setfill(' ') << std::setw(10) << p[i]->_atime
<< std::setfill(' ') << std::setw(10) << p[i]->_btime
<< std::setfill(' ') << std::setw(10) << p[i]->_ttime
<< std::setfill(' ') << std::setw(10) << p[i]->_wtime
<< std::endl;
}
void displayPercent(std::vector<process *> p)
{
int i;
for (i = 0; i < p.size(); i++)
printf("%d\t", p[i]->_percent);
printf("\n");
}
int main(int argc, char const **argv)
{
std::vector<process *> q[3];
int n = 10, i, j, c = 10;
std::vector<process *> p(n);
std::vector<process> cp(n); // 10 Processes
cp[0] = process(1, 7, 5, 1);
cp[1] = process(2, 4, 2, 0);
cp[2] = process(3, 5, 7, 1);
cp[3] = process(4, 0, 6, 0);
cp[4] = process(5, 3, 24, 0);
cp[5] = process(6, 7, 4, 2);
cp[6] = process(7, 0, 7, 1);
cp[7] = process(8, 3, 12, 2);
cp[8] = process(9, 2, 7, 1);
cp[9] = process(10, 4, 8, 2);
for (i = 0; i < n; i++)
p[i] = &cp[i];
p = sortArrivalTime(p);
int pburst = 0, pend = 0;
int co = 0;
// displayPercent(p);
while (c != 0)
{
c = 10;
for (i = 0; i < n; i++)
{
if (p[i]->_percent != 0)
{
if (p[i]->_atime <= pburst)
{
q[p[i]->_priority].push_back(p[i]);
}
else
{
pend = p[i]->_atime;
break;
}
}
}
if (pend == pburst)
pend = 999;
for (j = 0; j < 3; j++)
{
switch (j)
{
case 0:
if (!(q[j].empty()))
pburst = RR(q[j], pburst, pend);
break;
case 1:
if (!(q[j].empty()))
pburst = PR(q[j], pburst, pend);
break;
case 2:
if (!(q[j].empty()))
pburst = FCFS(q[j], pburst, pend);
break;
}
if (pburst == pend)
break;
}
for (i = 0; i < n; i++)
if (p[i]->_percent == 0)
c--;
q[0].clear();
q[1].clear();
q[2].clear();
}
std::vector<int> t = calculateTime(p);
displayTime(p);
printf("Average Turnaround Time: %d\nAverage Waiting Time: %d\n", t[0], t[1]);
return 0;
}
0 comments:
Post a Comment