0% found this document useful (0 votes)
24 views

CPU Scheduling Algorithms

OS

Uploaded by

vedikadhebe2712
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
24 views

CPU Scheduling Algorithms

OS

Uploaded by

vedikadhebe2712
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

ASSIGNMENT NO.

3
1. First Come First Serve:
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

typedef struct {
int process_id;
int arrival_time;
int burst_time;
int completion_time;
int waiting_time;
int turnaround_time;
} Process;

bool compareArrivalTime(Process a, Process b) {


return a.arrival_time<b.arrival_time;
}

bool compareProcessId(Process a, Process b) {


return a.process_id<b.process_id;
}

int *FCFS(queue<int> &ready_queue, Process process_table[], int n) {


int total_tat=0;
int total_wt=0;
int current_time=0;
int i=0;
cout<<endl<<endl<<"Gantt chart: \n";
while (!ready_queue.empty()) {
int pid=ready_queue.front();
if(pid==process_table[i].process_id){

if (current_time<process_table[i].arrival_time) {
current_time=process_table[i].arrival_time;
}

process_table[i].completion_time=current_time+process_table[i].burst_time;
process_table[i].turnaround_time=process_table[i].completion_time-process_table[i].arrival_time;
process_table[i].waiting_time=process_table[i].turnaround_time-process_table[i].burst_time;

current_time=process_table[i].completion_time;

total_tat+=process_table[i].turnaround_time;
total_wt+=process_table[i].waiting_time;

cout << "|\tP"<<process_table[i].process_id<<"\t|";

ready_queue.pop();
i++;
}else{
ready_queue.pop();
ready_queue.push(pid);
continue;
}
}
cout<<endl<<process_table[0].arrival_time;
for(int j = 0; j < n; j++){
cout<<"\t\t"<<process_table[j].completion_time;
}
cout<<endl<<endl;
int arr[2] = {total_tat, total_wt};
return arr;
}
void displayprocess_table(Process process_table[], int n) {
cout<<"Process ID\tArrival Time\tBurst Time\tCompletion Time\t\tWaiting Time\tTurnaround Time\n";
for (int i=0; i<n; i++) {
cout<<process_table[i].process_id+1<<"\t\t"<<process_table[i].arrival_time<<"\t\t"<<
process_table[i].burst_time<<"\t\t"<<process_table[i].completion_time<<"\t\t\t"<<process_table[i].waiting_time<<"\t\t"<<process_table[i].t
urnaround_time<<endl;
}
}

int main() {
int n;

cout<<"Enter the number of processes: ";


cin>>n;

Process process_table[n];
queue<int> ready_queue;

for (int i=0; i<n; i++) {


process_table[i].process_id=i;
process_table[i].arrival_time = i;
cout<<"Enter burst time for process "<<i+1<<": ";
cin>>process_table[i].burst_time;

ready_queue.push(i);
}

// sort(process_table, process_table+n, compareArrivalTime);

int *arr = FCFS(ready_queue, process_table, n);


double average_turnaround_time = (double)arr[0]/n;
double average_waiting_time = (double)arr[1]/n;

sort(process_table, process_table+n,compareProcessId);
displayprocess_table(process_table, n);

cout<<"Average Turn Around Time: "<< average_turnaround_time<<endl;


cout<<"Average Waiting Time: "<< average_waiting_time<<endl;

return 0;
}

Output:
Enter the number of processes: 5
Enter burst time for process 1: 8
Enter burst time for process 2: 6
Enter burst time for process 3: 3
Enter burst time for process 4: 2
Enter burst time for process 5: 4

Gantt chart:
| P0 || P1 || P2 || P3 || P4 |
0 8 14 17 19 23

Process ID Arrival Time Burst Time Completion Time Waiting Time Turnaround Time
1 0 8 8 0 8
2 1 6 14 7 13
3 2 3 17 12 15
4 3 2 19 14 16
5 4 4 23 15 19
Average Turn Around Time: 14.2
Average Waiting Time: 9.6
2. Shortest Job First (Non Pre-emptive):
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct {
int process_id;
int arrival_time;
int burst_time;
int priority;
int completion_time;
int waiting_time;
int turnaround_time;
bool is_completed;
} Process;

bool compareArrivalTime(Process a, Process b) {


return a.arrival_time < b.arrival_time;
}

bool compareProcessId(Process a, Process b) {


return a.process_id < b.process_id;
}

int *ShortestJob(queue<int>& ready_queue, Process process_table[], int n) {


int total_tat = 0;
int total_wt = 0;
int current_time = 0;
int completed_processes = 0;
vector<int> gantt_chart;

cout << "\n\nGantt Chart:\n";

while (completed_processes < n) {


for (int i = 0; i < n; i++) {
if (process_table[i].arrival_time <= current_time && !process_table[i].is_completed) {
ready_queue.push(i);
}
}

if (!ready_queue.empty()) {
int ind = -1;
int shortest_job = 10000;
int size = ready_queue.size();

for (int i = 0; i < size; i++) {


int pid = ready_queue.front();
ready_queue.pop();

if (!process_table[pid].is_completed && process_table[pid].burst_time < shortest_job) {


shortest_job = process_table[pid].burst_time;
ind = pid;
}

ready_queue.push(pid);
}

if (ind != -1) {
Process& current_process = process_table[ind];
gantt_chart.push_back(current_process.process_id);
current_time = max(current_time, current_process.arrival_time);
current_process.completion_time = current_time + current_process.burst_time;
current_process.turnaround_time = current_process.completion_time - current_process.arrival_time;
current_process.waiting_time = current_process.turnaround_time - current_process.burst_time;

total_tat += current_process.turnaround_time;
total_wt += current_process.waiting_time;

current_time = current_process.completion_time;
current_process.is_completed = true;
completed_processes++;

cout << "|\tP" << current_process.process_id << "\t|";


} else {
current_time++;
}
} else {
current_time++;
}
}

cout << "\n0";


for (int i = 0; i < gantt_chart.size(); i++) {
cout << "\t\t" << process_table[gantt_chart[i] - 1].completion_time;
}
cout << endl;

int arr[2] = {total_tat, total_wt};


return arr;
}

void displayProcessTable(Process process_table[], int n) {


cout << "\nProcess ID\tArrival Time\tBurst Time\tPriority\tCompletion Time\tWaiting Time\tTurnaround Time\n";
for (int i = 0; i < n; i++) {
cout << process_table[i].process_id << "\t\t" << process_table[i].arrival_time << "\t\t"
<< process_table[i].burst_time << "\t\t" << process_table[i].priority << "\t\t"
<< process_table[i].completion_time << "\t\t" << process_table[i].waiting_time
<< "\t\t" << process_table[i].turnaround_time << endl;
}
}

int main() {
int n;

// Input number of processes


cout << "Enter the number of processes: ";
cin >> n;

Process process_table[n];
queue<int> ready_queue;

for (int i = 0; i < n; i++) {


process_table[i].process_id = i + 1;
process_table[i].arrival_time = i;
cout << "Enter burst time for process " << i + 1 << ": ";
cin >> process_table[i].burst_time;
cout << "Enter priority for process " << i + 1 << ": ";
cin >> process_table[i].priority;
process_table[i].is_completed = false;
}
sort(process_table, process_table + n, compareArrivalTime);

int *arr = ShortestJob(ready_queue, process_table, n);


double average_turnaround_time = (double)arr[0]/n;
double average_waiting_time = (double)arr[1]/n;

sort(process_table, process_table + n, compareProcessId);


displayProcessTable(process_table, n);

cout << "\nAverage Turnaround Time: " << average_turnaround_time << endl;
cout << "Average Waiting Time: " << average_waiting_time << endl;

return 0;
}

Output:
Enter priority for process 3: 4
Enter burst time for process 4: 2
Enter priority for process 4: 3
Enter burst time for process 5: 4
Enter priority for process 5: 2

Gantt Chart:
| P1 || P4 || P3 || P5 || P2 |
0 8 10 13 17 23

Process ID Arrival Time Burst Time Priority Completion Time Waiting Time Turnaround Time
1 0 8 1 8 0 8
2 1 6 2 23 16 22
3 2 3 4 13 8 11
4 3 2 3 10 5 7
5 4 4 2 17 9 13

Average Turnaround Time: 12.2


Average Waiting Time: 7.6

3. Shortest Job First (Pre-emptive):


#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct {
int process_id;
int arrival_time;
int burst_time;
int remaining_time;
int completion_time;
int waiting_time;
int turnaround_time;
bool is_completed;
} Process;

bool compareArrivalTime(Process a, Process b) {


return a.arrival_time < b.arrival_time;
}

int *PreemptiveSJF(queue<int>& ready_queue, Process process_table[], int n) {


int total_tat = 0;
int total_wt = 0;
int current_time = 0;
int completed_processes = 0;
int shortest_job = -1;
int min_remaining_time = INT_MAX;

vector<int> gantt_chart;
bool is_any_process_running = false;

while (completed_processes < n) {


for (int i = 0; i < n; i++) {
if (process_table[i].arrival_time <= current_time && !process_table[i].is_completed) {
ready_queue.push(i);
}
}

if (!ready_queue.empty()) {
int ind = -1;
min_remaining_time = INT_MAX;

int size = ready_queue.size();


for (int i = 0; i < size; i++) {
int pid = ready_queue.front();
ready_queue.pop();

if (!process_table[pid].is_completed && process_table[pid].remaining_time < min_remaining_time) {


min_remaining_time = process_table[pid].remaining_time;
ind = pid;
}

ready_queue.push(pid);
}

if (ind != -1) {
Process& current_process = process_table[ind];
gantt_chart.push_back(current_process.process_id);
current_process.remaining_time--;
current_time++;

if (current_process.remaining_time == 0) {
current_process.completion_time = current_time;
current_process.turnaround_time = current_process.completion_time - current_process.arrival_time;
current_process.waiting_time = current_process.turnaround_time - current_process.burst_time;

total_tat += current_process.turnaround_time;
total_wt += current_process.waiting_time;

current_process.is_completed = true;
completed_processes++;

min_remaining_time = INT_MAX;
}
} else {
current_time++;
}
} else {
current_time++;
}
}

cout << "\nGantt Chart:\n0 -";


for (int i = 0; i < gantt_chart.size(); i++) {
cout << " | P" << gantt_chart[i];
}
cout << " |- " << current_time << endl;
int arr[2] = {total_tat, total_wt};
return arr;
}

void displayProcessTable(Process process_table[], int n) {


cout << "\nProcess ID\tArrival Time\tBurst Time\tCompletion Time\tWaiting Time\tTurnaround Time\n";
for (int i = 0; i < n; i++) {
cout << process_table[i].process_id << "\t\t" << process_table[i].arrival_time << "\t\t"
<< process_table[i].burst_time << "\t\t" << process_table[i].completion_time << "\t\t"
<< process_table[i].waiting_time << "\t\t" << process_table[i].turnaround_time << endl;
}
}

int main() {
int n;

cout << "Enter the number of processes: ";


cin >> n;

Process process_table[n];
queue<int> ready_queue;

for (int i = 0; i < n; i++) {


process_table[i].process_id = i + 1;
process_table[i].arrival_time = i;
cout << "Enter burst time for process " << i + 1 << ": ";
cin >> process_table[i].burst_time;
process_table[i].remaining_time = process_table[i].burst_time;
process_table[i].is_completed = false;
}

sort(process_table, process_table + n, compareArrivalTime);

int *arr = PreemptiveSJF(ready_queue, process_table, n);


double average_turnaround_time = (double)arr[0]/n;
double average_waiting_time = (double)arr[1]/n;

displayProcessTable(process_table, n);

cout << "\nAverage Turnaround Time: " << average_turnaround_time << endl;
cout << "Average Waiting Time: " << average_waiting_time << endl;

return 0;
}

Output:
Enter the number of processes: 5
Enter burst time for process 1: 8
Enter burst time for process 2: 6
Enter burst time for process 3: 3
Enter burst time for process 4: 2
Enter burst time for process 5: 4

Gantt Chart:
0 - | P1 | P2 | P3 | P3 | P3 | P4 | P4 | P5 | P5 | P5 | P5 | P2 | P2 | P2 | P2 | P2 | P1 | P1 | P1 | P1 | P1 | P1 |
P1 |- 23

Process ID Arrival Time Burst Time Completion Time Waiting Time Turnaround Time
1 0 8 23 15 23
2 1 6 16 9 15
3 2 3 5 0 3
4 3 2 7 2 4
5 4 4 11 3 7

Average Turnaround Time: 10.4


Average Waiting Time: 5.8
4. Priority (Non Pre-emptive):
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct {
int process_id;
int arrival_time;
int burst_time;
int priority;
int completion_time;
int waiting_time;
int turnaround_time;
bool is_completed;
} Process;

bool compareArrivalTime(Process a, Process b) {


return a.arrival_time < b.arrival_time;
}

bool compareProcessId(Process a, Process b) {


return a.process_id < b.process_id;
}

int *Priority(queue<int>& ready_queue, Process process_table[], int n) {


int total_tat = 0;
int total_wt = 0;
int current_time = 0;
int completed_processes = 0;
vector<int> gantt_chart;

cout << "\n\nGantt Chart:\n";

while (completed_processes < n) {


for (int i = 0; i < n; i++) {
if (process_table[i].arrival_time <= current_time && !process_table[i].is_completed) {
ready_queue.push(i);
}
}

if (!ready_queue.empty()) {
int ind = -1;
int highest_priority = 10000;
int size = ready_queue.size();

for (int i = 0; i < size; i++) {


int pid = ready_queue.front();
ready_queue.pop();

if (!process_table[pid].is_completed && process_table[pid].priority < highest_priority) {


highest_priority = process_table[pid].priority;
ind = pid;
}

ready_queue.push(pid);
}

if (ind != -1) {
Process& current_process = process_table[ind];
gantt_chart.push_back(current_process.process_id);
current_time = max(current_time, current_process.arrival_time);
current_process.completion_time = current_time + current_process.burst_time;
current_process.turnaround_time = current_process.completion_time - current_process.arrival_time;
current_process.waiting_time = current_process.turnaround_time - current_process.burst_time;

total_tat += current_process.turnaround_time;
total_wt += current_process.waiting_time;

current_time = current_process.completion_time;
current_process.is_completed = true;
completed_processes++;

cout << "|\tP" << current_process.process_id << "\t|";


} else {
current_time++;
}
} else {
current_time++;
}
}

cout << "\n0";


for (int i = 0; i < gantt_chart.size(); i++) {
cout << "\t\t" << process_table[gantt_chart[i] - 1].completion_time;
}
cout << endl;

int arr[2] = {total_tat, total_wt};


return arr;
}

void displayProcessTable(Process process_table[], int n) {


cout << "\nProcess ID\tArrival Time\tBurst Time\tPriority\tCompletion Time\tWaiting Time\tTurnaround Time\n";
for (int i = 0; i < n; i++) {
cout << process_table[i].process_id << "\t\t" << process_table[i].arrival_time << "\t\t"
<< process_table[i].burst_time << "\t\t" << process_table[i].priority << "\t\t"
<< process_table[i].completion_time << "\t\t" << process_table[i].waiting_time
<< "\t\t" << process_table[i].turnaround_time << endl;
}
}

int main() {
int n;

// Input number of processes


cout << "Enter the number of processes: ";
cin >> n;

Process process_table[n];
queue<int> ready_queue;

for (int i = 0; i < n; i++) {


process_table[i].process_id = i + 1;
process_table[i].arrival_time = i;
cout << "Enter burst time for process " << i + 1 << ": ";
cin >> process_table[i].burst_time;
cout << "Enter priority for process " << i + 1 << ": ";
cin >> process_table[i].priority;
process_table[i].is_completed = false;
}
sort(process_table, process_table + n, compareArrivalTime);

int *arr = Priority(ready_queue, process_table, n);


double average_turnaround_time = (double)arr[0]/n;
double average_waiting_time = (double)arr[1]/n;

sort(process_table, process_table + n, compareProcessId);


displayProcessTable(process_table, n);

cout << "\nAverage Turnaround Time: " << average_turnaround_time << endl;
cout << "Average Waiting Time: " << average_waiting_time << endl;

return 0;
}

Output:
Enter the number of processes: 5
Enter burst time for process 1: 8
Enter priority for process 1: 1
Enter burst time for process 2: 6
Enter priority for process 2: 2
Enter burst time for process 3: 3
Enter priority for process 3: 4
Enter burst time for process 4: 2
Enter priority for process 4: 3
Enter burst time for process 5: 4
Enter priority for process 5: 2

Gantt Chart:
| P1 || P2 || P5 || P4 || P3 |
0 8 14 18 20 23

Process ID Arrival Time Burst Time Priority Completion Time Waiting Time Turnaround Time
1 0 8 1 8 0 8
2 1 6 2 14 7 13
3 2 3 4 23 18 21
4 3 2 3 20 15 17
5 4 4 2 18 10 14

Average Turnaround Time: 14.6


Average Waiting Time: 10

--------------------------------
Process exited after 38.98 seconds with return value 0
Press any key to continue . . .

5. Round-Robin:
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct Process {
int p_id, arrival_time, burst_time, remaining_time, completion_time, turnaround_time, waiting_time;
};

void displayProcessTable(Process* processTable, int n) {


cout << "\n\nProcess Table:\n";
cout << "P_ID\tArrival Time\tBurst Time\tCompletion Time\t\tTurnaround Time\t\tWaiting Time\n";
for (int i = 0; i < n; i++) {
cout << processTable[i].p_id << "\t"
<< processTable[i].arrival_time << "\t\t"
<< processTable[i].burst_time << "\t\t"
<< processTable[i].completion_time << "\t\t\t"
<< processTable[i].turnaround_time << "\t\t\t"
<< processTable[i].waiting_time << endl;
}
}

void roundRobin(Process* processTable, int n, int quantum) {


queue<int> ready_queue; // Ready Queue
int current_time = 0;
int total_tat = 0, total_wt = 0;
int completed = 0; // Number of completed processes
int* remaining_time = new int[n]; // Array to store the remaining burst time of processes

// Initialize remaining time for all processes


for (int i = 0; i < n; i++) {
remaining_time[i] = processTable[i].burst_time;
ready_queue.push(i);
}

cout << "Gantt Chart: \n|";

while (completed < n) {


int p = ready_queue.front(); // Get the front process from the queue
ready_queue.pop(); // Remove the process from the queue

// Execute the process for 'quantum' time or its remaining time, whichever is smaller
if (remaining_time[p] > quantum) {
current_time += quantum;
remaining_time[p] -= quantum;
ready_queue.push(p); // Reinsert the process into the queue if it's not yet completed
} else {
current_time += remaining_time[p]; // Finish the process
processTable[p].completion_time = current_time;
processTable[p].turnaround_time = processTable[p].completion_time - processTable[p].arrival_time;
processTable[p].waiting_time = processTable[p].turnaround_time - processTable[p].burst_time;
total_tat += processTable[p].turnaround_time;
total_wt += processTable[p].waiting_time;
remaining_time[p] = 0;
completed++;
}

cout << " P" << processTable[p].p_id << " |"; // Print Gantt Chart
}

displayProcessTable(processTable, n); // Display the process table

// Display average waiting and turn around time


cout << "\nAverage Turnaround Time: " << (double)total_tat / n;
cout << "\nAverage Waiting Time: " << (double)total_wt / n;

int main() {
cout << "Enter the number of processes: ";
int n;
cin >> n;

cout << "Enter the time quantum: ";


int quantum;
cin >> quantum;

Process* processTable = new Process[n];


for (int i = 0; i < n; i++) {
cout << "Enter the burst time of process " << i + 1 << ": ";
cin >> processTable[i].burst_time;
processTable[i].arrival_time = i; // Assume arrival times as sequential
processTable[i].p_id = i + 1;
processTable[i].completion_time = 0; // Initialize to 0
}

roundRobin(processTable, n, quantum); // Call the round robin scheduling function

return 0;
}

Output:
Enter the number of processes: 6
Enter the time quantum: 5
Enter the burst time of process 1: 7
Enter the burst time of process 2: 4
Enter the burst time of process 3: 15
Enter the burst time of process 4: 11
Enter the burst time of process 5: 20
Enter the burst time of process 6: 9
Gantt Chart:
| P1 | P2 | P3 | P4 | P5 | P6 | P1 | P3 | P4 | P5 | P6 | P3 | P4 | P5 | P5 |

Process Table:
P_ID Arrival Time Burst Time Completion Time Turnaround Time Waiting Time
1 0 7 31 31 24
2 1 4 9 8 4
3 2 15 55 53 38
4 3 11 56 53 42
5 4 20 66 62 42
6 5 9 50 45 36

Average Turnaround Time: 42


Average Waiting Time: 31
--------------------------------
Process exited after 19.34 seconds with return value 0
Press any key to continue . . .

You might also like