Requisito previo: Programación de CPU en sistemas operativos
Diferentes algoritmos de programación:
- Programación de CPU por orden de llegada:
el algoritmo de programación más simple que programa de acuerdo con los tiempos de llegada de los procesos. El algoritmo de programación por orden de llegada establece que el proceso que solicita la CPU primero recibe la CPU primero. Se implementa utilizando la cola FIFO. Cuando un proceso ingresa a la cola de procesos listos, su PCB se vincula al final de la cola. Cuando la CPU está libre, se asigna al proceso que está al principio de la cola. A continuación, el proceso en ejecución se elimina de la cola. FCFS es un algoritmo de programación no preventivo. - El trabajo más corto primero (apropiativo):
en la programación prioritaria del trabajo más corto primero, los trabajos se colocan en la cola de listos a medida que llegan, pero cuando llega un proceso con un tiempo de ráfaga corto, el proceso existente se adelanta o se elimina de la ejecución, y el trabajo más corto se ejecutado primero. - El trabajo más corto primero (no preventivo):
en el trabajo más corto primero no preventivo, un proceso que tiene el tiempo de ráfaga más corto se programa primero. Si dos procesos tienen el mismo tiempo de interrupción, se usa FCFS para desempatar. - El trabajo más largo primero (preventivo):
es similar a un algoritmo de programación SJF. Pero, en este algoritmo de programación, damos prioridad al proceso al que le queda el mayor tiempo de ráfaga. - El trabajo más largo primero (no preventivo):
es similar a un algoritmo de programación SJF. Pero, en este algoritmo de programación, damos prioridad al proceso que tiene el tiempo de ráfaga más largo. Esto es de naturaleza no preventiva, es decir, cuando cualquier proceso comienza a ejecutarse, no puede interrumpirse antes de completar la ejecución. - Programación de turnos rotativos:
Para implementar la programación Round Robin, mantenemos la cola lista como una cola FIFO de procesos. Los nuevos procesos se agregan al final de la cola de listos. El programador de la CPU selecciona el primer proceso de la cola de procesos listos, configura un temporizador para que interrumpa después de un cuanto de 1 vez y envía el proceso. Entonces sucederá una de dos cosas. El proceso puede tener una ráfaga de CPU de menos de 1 vez de cuanto. En este caso, el propio proceso liberará la CPU voluntariamente. El planificador procederá entonces al siguiente proceso en la cola de espera. De lo contrario, si la ráfaga de CPU del proceso que se está ejecutando actualmente es mayor que 1 vez, el temporizador se apagará y provocará una interrupción en el sistema operativo. Se ejecutará un cambio de contexto y el proceso se colocará al final de la cola de procesos listos. El programador de la CPU luego seleccionará el siguiente proceso en la cola lista. - Programación (prioritaria) basada en prioridad:
en la programación prioritaria preventiva, en el momento de la llegada de un proceso a la cola de procesos listos, su prioridad se compara con la prioridad de los otros procesos presentes en la cola de procesos listos, así como con el que está siendo procesado. ejecutado por la CPU en ese momento. El que tenga la prioridad más alta entre todos los procesos disponibles recibirá la CPU a continuación. En este programa, tenemos ambas opciones, si considerar el número más alto como prioridad más alta o el número más bajo como prioridad más alta. - Programación Prioritaria (No Preferente):
En la programación Prioritaria No Preferente, los Procesos se programan de acuerdo con el número de prioridad que se les asigna. Una vez que el proceso se programa, se ejecutará hasta su finalización. En general, cuanto menor sea el número de prioridad, mayor será la prioridad del proceso. Las personas pueden confundirse con los números de prioridad, por lo tanto, en el GATE, se menciona claramente cuál es la prioridad más alta y cuál es la más baja. En este programa, tenemos ambas opciones, si considerar el número más alto como prioridad más alta o el número más bajo como prioridad más alta. - Programación de la relación de respuesta más alta siguiente (HRRN):
la relación de respuesta más alta siguiente (HRRN) es uno de los algoritmos de programación más óptimos. Este es un algoritmo no preventivo en el que la programación se realiza sobre la base de un parámetro adicional llamado Relación de respuesta. Se calcula un índice de respuesta para cada uno de los trabajos disponibles y se da prioridad al trabajo con el índice de respuesta más alto sobre los demás.
Considere la siguiente tabla:
A continuación se muestra la implementación de los algoritmos anteriores utilizando una cola de prioridad :
FCFS
// C++ implementation of the FCFS algorithm
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
// Function to set starting Arrival Time
// Because arrival time gets updated
// when you push process in ready queue again
// in preemptive algorithms
void P_set()
{
start_AT = AT;
BT_left = BT;
}
// Function to set Response Time
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
// Function to implement FCFS algorithm
priority_queue<process> FCFS_run(priority_queue<process> ready_queue,
queue<process>* gantt)
{
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
// Till ready queue is not empty
while (!ready_queue.empty()) {
// While clock is less than
// Arrival Time
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = ready_queue.top();
ready_queue.pop();
p.set_RT(clock);
while (p.BT_left > 0) {
p.temp_BT++;
p.BT_left--;
clock++;
}
p.set_CT(clock);
// Update the Gantt Chart
(*gantt).push(p);
p.temp_BT = 0;
// Update the completion time to
// the queue
completion_queue.push(p);
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
// Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display Completion Queue and
// all the time
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1
<< endl;
cout << "Average completion time :- " << temp1 / size
<< endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1
<< endl;
cout << "Average turnaround time :- " << temp1 / size
<< endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1
<< endl;
cout << "Average waiting time :- " << temp1 / size
<< endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1
<< endl;
cout << "Average response time :- " << temp1 / size
<< endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
// For 1st row of gantt chart
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length()
+ (spaces.front().p_no != -1)
+ 2 * spaces.front().temp_BT,
'-')
<< "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
// For process no. in 2nd row
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << (string(to_string(spaces.front().p_no).length()
+ (spaces.front().p_no != -1)
+ 2 * spaces.front().temp_BT,
'-'))
<< "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
//For 3rd row of gantt chart
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << (string(to_string(spaces.front().p_no).length()
+ (spaces.front().p_no != -1)
+ 2 * spaces.front().temp_BT - temp / 2 - prev,
' '))
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialise Ready and Completion Queue
priority_queue<process> ready_queue;
priority_queue<process> completion_queue;
// queue for Gantt Chart
queue<process> gantt;
ready_queue = set_sample_data();
// Function call for completion data
completion_queue = FCFS_run(ready_queue, &gantt);
// Display Completion Queue
disp(completion_queue, false);
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
SJF-P
// C++ implementation of the SJF preemptive algorithm
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
void P_set()
{
start_AT = AT;
BT_left = BT;
}
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
process pop_index(priority_queue<process>* main_queue, int index)
{
priority_queue<process> rm_index;
int i;
process p;
switch (index) {
case 0:
p = (*main_queue).top();
(*main_queue).pop();
break;
default:
for (i = 0; i < index; i++) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
p = (*main_queue).top();
(*main_queue).pop();
while (!(*main_queue).empty()) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
(*main_queue) = rm_index;
break;
}
return p;
}
time_t min_BT(priority_queue<process> main_queue, time_t clock)
{
time_t min = 0;
while (!main_queue.empty() && main_queue.top().AT <= clock) {
if (min == 0 || min > main_queue.top().BT_left)
min = main_queue.top().BT_left;
main_queue.pop();
}
return min;
}
int min_BT_index(priority_queue<process> main_queue, time_t limit)
{
int index, i = 0;
time_t min = 0;
while (!main_queue.empty() && main_queue.top().AT <= limit) {
if (min == 0 || main_queue.top().BT_left < min) {
min = main_queue.top().BT_left;
index = i;
}
main_queue.pop();
i++;
}
return index;
}
// Function to implement SJF preemptive algorithm
priority_queue<process> SJF_P_run(priority_queue<process> ready_queue,
queue<process>* gantt)
{
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = pop_index(&ready_queue, min_BT_index(ready_queue, clock));
if (p.AT == p.start_AT)
p.set_RT(clock);
while (p.BT_left > 0 && (ready_queue.empty()
|| clock < ready_queue.top().AT
|| p.BT_left <= min_BT(ready_queue, clock))) {
p.BT_left--;
p.temp_BT++;
clock++;
}
if (p.BT_left == 0) {
p.AT = p.start_AT;
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
else {
p.AT = clock;
p.CT = clock;
(*gantt).push(p);
p.temp_BT = 0;
ready_queue.push(p);
}
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
// Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display Completion Queue
// and all the time
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1 << endl;
cout << "Average completion time :- " << temp1 / size << endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1 << endl;
cout << "Average turnaround time :- " << temp1 / size << endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1 << endl;
cout << "Average waiting time :- " << temp1 / size << endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1 << endl;
cout << "Average response time :- " << temp1 / size << endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-')
<< "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT
- temp / 2 - prev,
' ')
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialize Ready and Completion Queue
priority_queue<process> ready_queue, completion_queue;
// queue for Gantt Chart
queue<process> gantt;
ready_queue = set_sample_data();
// Function call for completion data
completion_queue = SJF_P_run(ready_queue, &gantt);
// Display Completion Queue
disp(completion_queue, false);
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
SJF-NP
// C++ implementation of the SJF(Non-preemptive) algorithm
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
void P_set()
{
start_AT = AT;
BT_left = BT;
}
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
// Function to implementation pop_index()
process pop_index(priority_queue<process>* main_queue, int index)
{
priority_queue<process> rm_index;
int i;
process p;
switch (index) {
case 0:
p = (*main_queue).top();
(*main_queue).pop();
break;
default:
for (i = 0; i < index; i++) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
p = (*main_queue).top();
(*main_queue).pop();
while (!(*main_queue).empty()) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
(*main_queue) = rm_index;
break;
}
return p;
}
// Function to find index of process
//with minimum BT
int min_BT_index(priority_queue<process> main_queue, time_t limit)
{
int index, i = 0;
time_t min = 0;
while (!main_queue.empty() && main_queue.top().AT <= limit) {
if (min == 0 || main_queue.top().BT_left < min) {
min = main_queue.top().BT_left;
index = i;
}
main_queue.pop();
i++;
}
return index;
}
// Function to implement SJF(Non-preemptive)
priority_queue<process> SJF_NP_run(priority_queue<process> ready_queue,
queue<process>* gantt)
{
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = pop_index(&ready_queue,
min_BT_index(ready_queue, clock));
p.set_RT(clock);
while (p.BT_left > 0) {
p.temp_BT++;
p.BT_left--;
clock++;
}
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
//Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display the queue
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1 << endl;
cout << "Average completion time :- " << temp1 / size << endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1 << endl;
cout << "Average turnaround time :- " << temp1 / size << endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1 << endl;
cout << "Average waiting time :- " << temp1 / size << endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1 << endl;
cout << "Average response time :- " << temp1 / size << endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-')
<< "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT
- temp / 2 - prev,
' ')
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialise Ready and Completion Queue
priority_queue<process> ready_queue, completion_queue;
// queue for Gantt Chart
queue<process> gantt;
ready_queue = set_sample_data();
// Function call to find completion data
completion_queue = SJF_NP_run(ready_queue, &gantt);
// Display Completion Queue
disp(completion_queue, false);
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
LJF-P
// C++ implementation of the LJF(Preemptive) algorithm
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
void P_set()
{
start_AT = AT;
BT_left = BT;
}
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
// Function to implementation pop_index()
process pop_index(priority_queue<process>* main_queue, int index)
{
priority_queue<process> rm_index;
int i;
process p;
switch (index) {
case 0:
p = (*main_queue).top();
(*main_queue).pop();
break;
default:
for (i = 0; i < index; i++) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
p = (*main_queue).top();
(*main_queue).pop();
while (!(*main_queue).empty()) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
(*main_queue) = rm_index;
break;
}
return p;
}
// Function to implement maximum Burst Time
time_t max_BT(priority_queue<process> main_queue, time_t limit)
{
time_t max = 0;
while (!main_queue.empty() && main_queue.top().AT <= limit) {
if (main_queue.top().BT_left > max)
max = main_queue.top().BT_left;
main_queue.pop();
}
return max;
}
// Function to implement maximum BT index w.r.t given clock limit
int max_BT_index(priority_queue<process> main_queue, time_t limit)
{
int index, i = 0;
time_t max = 0;
while (!main_queue.empty() && main_queue.top().AT <= limit) {
if (main_queue.top().BT_left > max) {
max = main_queue.top().BT_left;
index = i;
}
main_queue.pop();
i++;
}
return index;
}
// Function to implement LJF(Preemptive) algorithm
priority_queue<process> LJF_P_run(priority_queue<process> ready_queue,
queue<process>* gantt)
{
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = pop_index(&ready_queue, max_BT_index(ready_queue, clock));
if (p.AT == p.start_AT)
p.set_RT(clock);
while (p.BT_left > 0 && (ready_queue.empty()
|| clock < ready_queue.top().AT
|| p.BT_left >= max_BT(ready_queue, clock))) {
p.temp_BT++;
p.BT_left--;
clock++;
}
if (p.BT_left == 0) {
p.AT = p.start_AT;
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
else {
p.AT = clock;
p.CT = clock;
(*gantt).push(p);
p.temp_BT = 0;
ready_queue.push(p);
}
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
// Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display Completion Queue
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1 << endl;
cout << "Average completion time :- " << temp1 / size << endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1 << endl;
cout << "Average turnaround time :- " << temp1 / size << endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1 << endl;
cout << "Average waiting time :- " << temp1 / size << endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1 << endl;
cout << "Average response time :- " << temp1 / size << endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT - temp / 2 - prev, ' ')
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialise Ready and Completion Queue
priority_queue<process> ready_queue, completion_queue;
// queue for Gantt Chart
queue<process> gantt;
ready_queue = set_sample_data();
// Function call to find completion data
completion_queue = LJF_P_run(ready_queue, &gantt);
// Display Completion Queue
disp(completion_queue, false);
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
LJF-NP
// C++ implementation of the LJF(Non-Preemptive) algorithm
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
void P_set()
{
start_AT = AT;
BT_left = BT;
}
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
// Function to implement pop_index()
process pop_index(priority_queue<process>* main_queue, int index)
{
priority_queue<process> rm_index;
int i;
process p;
switch (index) {
case 0:
p = (*main_queue).top();
(*main_queue).pop();
break;
default:
for (i = 0; i < index; i++) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
p = (*main_queue).top();
(*main_queue).pop();
while (!(*main_queue).empty()) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
(*main_queue) = rm_index;
break;
}
return p;
}
// Function to find maximum Burst Time Index w.r.t clock limit
int max_BT_index(priority_queue<process> main_queue, time_t limit)
{
int index, i = 0;
time_t max = 0;
while (!main_queue.empty() && main_queue.top().AT <= limit) {
if (main_queue.top().BT_left > max) {
max = main_queue.top().BT_left;
index = i;
}
main_queue.pop();
i++;
}
return index;
}
// Function to implement LJF(Non-Preemptive) Algorithm
priority_queue<process> LJF_NP_run(priority_queue<process> ready_queue,
queue<process>* gantt)
{
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.set_CT(clock);
(*gantt).push(p);
}
p = pop_index(&ready_queue, max_BT_index(ready_queue, clock));
p.set_RT(clock);
while (p.BT_left > 0) {
p.temp_BT++;
p.BT_left--;
clock++;
}
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
// Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display Completion queue
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1 << endl;
cout << "Average completion time :- " << temp1 / size << endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1 << endl;
cout << "Average turnaround time :- " << temp1 / size << endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1 << endl;
cout << "Average waiting time :- " << temp1 / size << endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1 << endl;
cout << "Average response time :- " << temp1 / size << endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-')
<< "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT
- temp / 2 - prev,
' ')
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialise Ready and Completion Queue
priority_queue<process> ready_queue, completion_queue;
// queue for Gantt Chart
queue<process> gantt;
ready_queue = set_sample_data();
// Function call to find completion data
completion_queue = LJF_NP_run(ready_queue, &gantt);
// Display Completion Queue
disp(completion_queue, false);
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
RR
// C++ implementation of the Round Robin algorithm
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
void P_set()
{
start_AT = AT;
BT_left = BT;
}
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
// Function to implement Round Robin algorithm
priority_queue<process> RR_run(priority_queue<process> ready_queue,
time_t Time_Slice,
queue<process>* gantt)
{
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = ready_queue.top();
ready_queue.pop();
if (p.AT == p.start_AT)
p.set_RT(clock);
while (p.BT_left > 0 && (p.temp_BT < Time_Slice
|| ready_queue.empty()
|| clock < ready_queue.top().AT)) {
p.temp_BT++;
p.BT_left--;
clock++;
}
if (p.BT_left == 0) {
p.AT = p.start_AT;
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
else {
p.AT = clock;
p.CT = clock;
(*gantt).push(p);
p.temp_BT = 0;
ready_queue.push(p);
}
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
// Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display Completion queue
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1 << endl;
cout << "Average completion time :- " << temp1 / size << endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1 << endl;
cout << "Average turnaround time :- " << temp1 / size << endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1 << endl;
cout << "Average waiting time :- " << temp1 / size << endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1 << endl;
cout << "Average response time :- " << temp1 / size << endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT - temp / 2 - prev, ' ')
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialise Ready and Completion Queue
priority_queue<process> ready_queue, completion_queue;
// queue for Gantt Chart
queue<process> gantt;
// Time quantum for round robin
int tq = 2;
ready_queue = set_sample_data();
// Function call to find completion data
completion_queue = RR_run(ready_queue, tq, &gantt);
// Display Completion Queue
disp(completion_queue, false);
cout << "\nTime Quantum for round robin :- " << tq << endl;
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
PB-P
// C++ implementation of the Priority Based(Preemptive) algorithm
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
void P_set()
{
start_AT = AT;
BT_left = BT;
}
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
// Function to implement pop_index()
process pop_index(priority_queue<process>* main_queue,
int index)
{
priority_queue<process> rm_index;
int i;
process p;
switch (index) {
case 0:
p = (*main_queue).top();
(*main_queue).pop();
break;
default:
for (i = 0; i < index; i++) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
p = (*main_queue).top();
(*main_queue).pop();
while (!(*main_queue).empty()) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
(*main_queue) = rm_index;
break;
}
return p;
}
// Function to implement maximum priority w.r.t
//priority and also 2nd argument has boolean
//variable because we need to specify
// True=highest number as highest priority
// False=lowest number as highest priority
int max_priority(priority_queue<process> main_priority_queue,
int limit, bool high)
{
int max = -1;
if (high == 1) {
while (!main_priority_queue.empty()
&& main_priority_queue.top().AT <= limit) {
if (main_priority_queue.top().priority > max)
max = main_priority_queue.top().priority;
main_priority_queue.pop();
}
}
else {
while (!main_priority_queue.empty()
&& main_priority_queue.top().AT <= limit) {
if (max == -1 || main_priority_queue.top().priority < max)
max = main_priority_queue.top().priority;
main_priority_queue.pop();
}
}
return max;
}
// Function to implement maximum priority index
int max_priority_index(priority_queue<process> main_queue, int limit, bool high)
{
int max = -1, i = 0, index = 0;
if (high == 1) {
while (!main_queue.empty() && main_queue.top().AT <= limit) {
if (main_queue.top().priority > max) {
max = main_queue.top().priority;
index = i;
}
main_queue.pop();
i++;
}
}
else {
while (!main_queue.empty()
&& main_queue.top().AT <= limit) {
if (max == -1 || main_queue.top().priority < max) {
max = main_queue.top().priority;
index = i;
}
main_queue.pop();
i++;
}
}
return index;
}
// Function to implement priority based Preemptive scheduling
priority_queue<process> Priority_P_run(priority_queue<process> ready_queue, queue<process>* gantt, bool high)
{
int temp;
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
if (high == 1) {
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = pop_index(&ready_queue,
max_priority_index(ready_queue, clock, high));
if (p.AT == p.start_AT)
p.set_RT(clock);
while (p.BT_left > 0
&& (ready_queue.empty()
|| clock < ready_queue.top().AT
|| p.priority >= max_priority(ready_queue, clock, high))) {
p.temp_BT++;
p.BT_left--;
clock++;
}
if (p.BT_left == 0) {
p.AT = p.start_AT;
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
else {
p.AT = clock;
p.CT = clock;
(*gantt).push(p);
p.temp_BT = 0;
ready_queue.push(p);
}
}
}
else {
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = pop_index(&ready_queue,
max_priority_index(ready_queue,
clock, high));
if (p.AT == p.start_AT)
p.set_RT(clock);
temp = max_priority(ready_queue, clock, high);
while (p.BT_left > 0 && (ready_queue.empty()
|| clock < ready_queue.top().AT
|| p.priority <= max_priority(ready_queue, clock, high))) {
p.temp_BT++;
p.BT_left--;
clock++;
}
if (p.BT_left == 0) {
p.AT = p.start_AT;
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
else {
p.AT = clock;
p.CT = clock;
(*gantt).push(p);
p.temp_BT = 0;
ready_queue.push(p);
}
}
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
// Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display main queue
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1 << endl;
cout << "Average completion time :- " << temp1 / size << endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1 << endl;
cout << "Average turnaround time :- " << temp1 / size << endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1 << endl;
cout << "Average waiting time :- " << temp1 / size << endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1 << endl;
cout << "Average response time :- " << temp1 / size << endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-')
<< "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT - temp / 2 - prev, ' ')
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialise Ready and Completion Queue
priority_queue<process> ready_queue, completion_queue;
// queue for Gantt Chart
queue<process> gantt;
ready_queue = set_sample_data();
// Function call to find completion data
//3rd argument has true passed becuase we have set
//highest number = highest priority
completion_queue = Priority_P_run(ready_queue, &gantt, true);
// Display Completion Queue as true in
//2nd argument to display priority
disp(completion_queue, true);
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
PB-NP
// C++ implementation of the Priority Based(Non-Preemptive) algorithm
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
void P_set()
{
start_AT = AT;
BT_left = BT;
}
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
// Function to implement pop_index()
process pop_index(priority_queue<process>* main_queue,
int index)
{
priority_queue<process> rm_index;
int i;
process p;
switch (index) {
case 0:
p = (*main_queue).top();
(*main_queue).pop();
break;
default:
for (i = 0; i < index; i++) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
p = (*main_queue).top();
(*main_queue).pop();
while (!(*main_queue).empty()) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
(*main_queue) = rm_index;
break;
}
return p;
}
//Function to implement maximum priority w.r.t clock limit
// and 3rd parameter as bool because we need true = highest
//number as highest and false as lowest number as highest priority
int max_priority(priority_queue<process> main_priority_queue,
int limit, bool high)
{
int max = -1;
if (high == 1) {
while (!main_priority_queue.empty()
&& main_priority_queue.top().AT <= limit) {
if (main_priority_queue.top().priority > max)
max = main_priority_queue.top().priority;
main_priority_queue.pop();
}
}
else {
while (!main_priority_queue.empty()
&& main_priority_queue.top().AT <= limit) {
if (max == -1 || main_priority_queue.top().priority < max)
max = main_priority_queue.top().priority;
main_priority_queue.pop();
}
}
return max;
}
// Function to implement maximum priority index
int max_priority_index(priority_queue<process> main_queue, int limit, bool high)
{
int max = -1, i = 0, index = 0;
if (high == 1) {
while (!main_queue.empty() && main_queue.top().AT <= limit) {
if (main_queue.top().priority > max) {
max = main_queue.top().priority;
index = i;
}
main_queue.pop();
i++;
}
}
else {
while (!main_queue.empty()
&& main_queue.top().AT <= limit) {
if (max == -1 || main_queue.top().priority < max) {
max = main_queue.top().priority;
index = i;
}
main_queue.pop();
i++;
}
}
return index;
}
// Function to implement priority based Preemptive scheduling
priority_queue<process> Priority_NP_run(priority_queue<process> ready_queue,
queue<process>* gantt, bool high)
{
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
if (high == 1) {
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = pop_index(&ready_queue,
max_priority_index(ready_queue,
clock, high));
p.set_RT(clock);
while (p.BT_left > 0) {
p.temp_BT++;
p.BT_left--;
clock++;
}
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
}
else {
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = pop_index(&ready_queue,
max_priority_index(ready_queue,
clock, high));
p.set_RT(clock);
while (p.BT_left > 0) {
p.temp_BT++;
p.BT_left--;
clock++;
}
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
// Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display main queue
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1 << endl;
cout << "Average completion time :- " << temp1 / size << endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1 << endl;
cout << "Average turnaround time :- " << temp1 / size << endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1 << endl;
cout << "Average waiting time :- " << temp1 / size << endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1 << endl;
cout << "Average response time :- " << temp1 / size << endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-')
<< "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT - temp / 2 - prev, ' ')
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialise Ready and Completion Queue
priority_queue<process> ready_queue, completion_queue;
// queue for Gantt Chart
queue<process> gantt;
ready_queue = set_sample_data();
// Function call to find completion data
//and true is passed as 3rd argument because we
//are considering highest number as highest priority
completion_queue = Priority_NP_run(ready_queue, &gantt, true);
// Display Completion Queue
disp(completion_queue, true);
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
HRRN
// C++ implementation of the HRRN Scheduling
#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;
class process {
public:
pid_t p_no = 0;
time_t start_AT = 0, AT = 0,
BT_left = 0, BT = 0, temp_BT = 0,
CT = 0, TAT = 0, WT = 0, RT = 0;
int priority = 0;
// Function for completion time
void set_CT(time_t time)
{
CT = time;
set_TAT();
set_WT();
}
// Function for Turn Around Time
void set_TAT()
{
TAT = CT - start_AT;
}
// Function for Waiting Time
void set_WT()
{
WT = TAT - BT;
}
void P_set()
{
start_AT = AT;
BT_left = BT;
}
void set_RT(time_t time)
{
RT = time - start_AT;
}
// Overload operator '<' w.r.t arrival
// time because arrival time is the
// first priority even greater than
// priority of process and priority_queue
// pops out the greatest value first
// so we need to replace '<' with '>' inorder
// to pop out smallest value
friend bool operator<(const process& a, const process& b)
{
return a.AT > b.AT;
}
};
// Function to implement pop_index()
process pop_index(priority_queue<process>* main_queue,
int index)
{
priority_queue<process> rm_index;
int i;
process p;
switch (index) {
case 0:
p = (*main_queue).top();
(*main_queue).pop();
break;
default:
for (i = 0; i < index; i++) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
p = (*main_queue).top();
(*main_queue).pop();
while (!(*main_queue).empty()) {
rm_index.push((*main_queue).top());
(*main_queue).pop();
}
(*main_queue) = rm_index;
break;
}
return p;
}
// Function to implement maximum Response Ratio
// index w.r.t clock limit for arrival time
int max_response_ratio_index(priority_queue<process> ready_queue,
time_t limit)
{
int index, i = 0;
double response_ratio = 0, max = 0;
while (!ready_queue.empty()
&& ready_queue.top().AT <= limit) {
response_ratio = ((double)(limit - ready_queue.top().AT) + ready_queue.top().BT_left) / ready_queue.top().BT_left;
if (response_ratio > max) {
max = response_ratio;
index = i;
}
i++;
ready_queue.pop();
}
return index;
}
// Function to implement HRRN Scheduling
priority_queue<process> HRRN_run(priority_queue<process> ready_queue,
queue<process>* gantt)
{
priority_queue<process> completion_queue;
process p;
time_t clock = 0;
while (!ready_queue.empty()) {
while (clock < ready_queue.top().AT) {
p.temp_BT++;
clock++;
}
if (p.temp_BT > 0) {
p.p_no = -1;
p.CT = clock;
(*gantt).push(p);
}
p = pop_index(&ready_queue,
max_response_ratio_index(ready_queue,
clock));
p.set_RT(clock);
while (p.BT_left > 0) {
p.temp_BT++;
p.BT_left--;
clock++;
}
p.set_CT(clock);
(*gantt).push(p);
p.temp_BT = 0;
completion_queue.push(p);
}
return completion_queue;
}
// Set data on the basis of given table
priority_queue<process> set_sample_data()
{
priority_queue<process> ready_queue;
process temp;
temp.AT = 0;
temp.BT = 4;
temp.priority = 2;
temp.p_no = 1;
temp.P_set();
ready_queue.push(temp);
temp.AT = 1;
temp.BT = 2;
temp.priority = 4;
temp.p_no = 2;
temp.P_set();
ready_queue.push(temp);
temp.AT = 2;
temp.BT = 3;
temp.priority = 6;
temp.p_no = 3;
temp.P_set();
ready_queue.push(temp);
temp.AT = 3;
temp.BT = 5;
temp.priority = 10;
temp.p_no = 4;
temp.P_set();
ready_queue.push(temp);
temp.AT = 4;
temp.BT = 1;
temp.priority = 8;
temp.p_no = 5;
temp.P_set();
ready_queue.push(temp);
temp.AT = 5;
temp.BT = 4;
temp.priority = 12;
temp.p_no = 6;
temp.P_set();
ready_queue.push(temp);
temp.AT = 6;
temp.BT = 6;
temp.priority = 9;
temp.p_no = 7;
temp.P_set();
ready_queue.push(temp);
return ready_queue;
}
// Function to get total Waiting Time
double get_total_WT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().WT;
processes.pop();
}
return total;
}
// Function to get total Turn Around Time
double get_total_TAT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().TAT;
processes.pop();
}
return total;
}
// Function to get total Completion Time
double get_total_CT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().CT;
processes.pop();
}
return total;
}
// Function to get total Response Time
double get_total_RT(priority_queue<process> processes)
{
double total = 0;
while (!processes.empty()) {
total += processes.top().RT;
processes.pop();
}
return total;
}
// Function to display main queue
void disp(priority_queue<process> main_queue, bool high)
{
int i = 0, temp, size = main_queue.size();
priority_queue<process> tempq = main_queue;
double temp1;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
cout << "| Process No. | Arrival Time ";
cout << "| Burst Time | Completion Time ";
cout << "| Turnaround Time | Waiting Time | Response Time |";
if (high == true)
cout << " Priority |" << endl;
else
cout << endl;
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+" << endl;
else
cout << endl;
while (!main_queue.empty()) {
temp = to_string(main_queue.top().p_no).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().p_no << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().start_AT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().start_AT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().BT).length();
cout << '|' << string(6 - temp / 2 - temp % 2, ' ')
<< main_queue.top().BT << string(6 - temp / 2, ' ');
temp = to_string(main_queue.top().CT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().CT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().TAT).length();
cout << '|' << string(8 - temp / 2 - temp % 2, ' ')
<< main_queue.top().TAT << string(9 - temp / 2, ' ');
temp = to_string(main_queue.top().WT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().WT << string(7 - temp / 2, ' ');
temp = to_string(main_queue.top().RT).length();
cout << '|' << string(7 - temp / 2 - temp % 2, ' ')
<< main_queue.top().RT << string(8 - temp / 2, ' ');
if (high == true) {
temp = to_string(main_queue.top().priority).length();
cout << '|' << string(5 - temp / 2 - temp % 2, ' ')
<< main_queue.top().priority << string(5 - temp / 2, ' ');
}
cout << "|\n";
main_queue.pop();
}
cout << "+-------------+--------------";
cout << "+------------+-----------------";
cout << "+-----------------+--------------+---------------+";
if (high == true)
cout << "----------+";
cout << endl;
temp1 = get_total_CT(tempq);
cout << "\nTotal completion time :- " << temp1 << endl;
cout << "Average completion time :- " << temp1 / size << endl;
temp1 = get_total_TAT(tempq);
cout << "\nTotal turnaround time :- " << temp1 << endl;
cout << "Average turnaround time :- " << temp1 / size << endl;
temp1 = get_total_WT(tempq);
cout << "\nTotal waiting time :- " << temp1 << endl;
cout << "Average waiting time :- " << temp1 / size << endl;
temp1 = get_total_RT(tempq);
cout << "\nTotal response time :- " << temp1 << endl;
cout << "Average response time :- " << temp1 / size << endl;
}
// Function to display Gantt Chart
void disp_gantt_chart(queue<process> gantt)
{
int temp, prev = 0;
queue<process> spaces = gantt;
cout << "\n\nGantt Chart (IS indicates ideal state) :- \n\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-') << "+";
spaces.pop();
}
cout << "\n|";
spaces = gantt;
while (!spaces.empty()) {
cout << string(spaces.front().temp_BT, ' ');
if (spaces.front().p_no == -1)
cout << "IS" << string(spaces.front().temp_BT, ' ') << '|';
else
cout << "P" << spaces.front().p_no
<< string(spaces.front().temp_BT, ' ') << '|';
spaces.pop();
}
spaces = gantt;
cout << "\n+";
while (!spaces.empty()) {
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT, '-')
<< "+";
spaces.pop();
}
spaces = gantt;
cout << "\n0";
while (!spaces.empty()) {
temp = to_string(spaces.front().CT).length();
cout << string(to_string(spaces.front().p_no).length() + (spaces.front().p_no != -1) + 2 * spaces.front().temp_BT - temp / 2 - prev, ' ')
<< spaces.front().CT;
prev = temp / 2 - temp % 2 == 0;
spaces.pop();
}
cout << "\n\n";
}
// Driver Code
int main()
{
// Initialise Ready and Completion Queue
priority_queue<process> ready_queue, completion_queue;
// queue for Gantt Chart
queue<process> gantt;
ready_queue = set_sample_data();
// Function call to find completion data
completion_queue = HRRN_run(ready_queue, &gantt);
// Display Completion Queue
disp(completion_queue, false);
// Display Gantt Chart
disp_gantt_chart(gantt);
return 0;
}
Publicación traducida automáticamente
Artículo escrito por jaspreetsinghpal18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA