#include<bits/stdc++.h>
using namespace std;
int function_for_time_quantum(queue<int> ready_queue)
{
int tot_size=ready_queue.size();
vector<int> v_for_sort,v_for_save;
while(!ready_queue.empty()){
int process_burst=ready_queue.front();
ready_queue.pop();
v_for_save.push_back(process_burst);
v_for_sort.push_back(process_burst);
}
sort(v_for_sort.begin(),v_for_sort.end());
int median;
if(tot_size%2==0){
median=( v_for_sort[tot_size/2] + v_for_sort[(tot_size/2)-1] )/2.0;
}
else median=v_for_sort[tot_size/2];
int diff=0;
for(int i=1;i<v_for_sort.size();i++){
diff+=(v_for_sort[i]-v_for_sort[i-1]);
}
double average_of_diff;
if(tot_size==1) average_of_diff=diff;
else average_of_diff=(double)diff/(tot_size-1);
int factor=floor(average_of_diff);
for(auto it:v_for_save){
ready_queue.push(it);
}
int t=median+factor;
return t;
}
int main()
{
int arrival_time[105],burst_time[105],finish_time[105],response_time[105],visited[105],waiting_time[105],turn_time[105];
int tq;
vector<pair<int,pair<int,int>> > v;
cout<<"Number of process, n:";
int n;cin>>n;
for(int i=1;i<=n;i++){
response_time[i]=-1;
visited[i]=0;
}
for(int i=1;i<=n;i++){
cout<<"Enter the arrival time of P"<<i<<": ";
cin>>arrival_time[i];
cout<<"Enter the burst time of P"<<i<<": ";
cin>>burst_time[i];
cout<<endl;
v.push_back({arrival_time[i],{burst_time[i],i}});
}
sort(v.begin(),v.end());
queue<int> ready_queue;
int current_time=0;
int tot_idle_time=0;
queue<pair<int,int> > q;
q.push({v[0].second.first,v[0].second.second}); /// burst time , id
ready_queue.push(v[0].second.first);
visited[0]=1;
current_time=v[0].first;
cout<<"Gantt Chart: :";
cout<<0<<" ";
if(current_time!=0){
cout<<"Idle "<<current_time<<" ";
tot_idle_time+=current_time;
}
///int ct=0;
int total_completed=0;
while(!q.empty()){
auto x=q.front();
int burst=x.first;
int process_id=x.second;
q.pop();
///ct++;
if(response_time[process_id]==-1) response_time[process_id]=current_time;
tq=function_for_time_quantum(ready_queue);
ready_queue.pop();
int remaining_burst_time;
if(tq<burst){
current_time+=tq;
remaining_burst_time=burst-tq;
}
else{
current_time+=burst;
remaining_burst_time=0;
finish_time[process_id]=current_time;
total_completed++;
}
cout<<"P"<<process_id<<" "<<current_time<<" ";
for(int i=0;i<n;i++){
if(v[i].first<=current_time){
if(visited[i]==0)
{
visited[i]=1;
q.push({v[i].second.first,v[i].second.second});
ready_queue.push(v[i].second.first);
}
}
}
/// cout<<"ID2 "<<id<<" bur "<<rem<<endl;https://pastebin.pl/view/346f6894
if(remaining_burst_time!=0){
q.push({remaining_burst_time,process_id});
ready_queue.push(remaining_burst_time);
}
if(q.empty()){
if(total_completed!=n){
for(int i=0;i<n;i++){
if(visited[i]==0)
{
visited[i]=1;
int arrival=v[i].first;
q.push({v[i].second.first,v[i].second.second});
ready_queue.push(v[i].second.first);
cout<<"Idle "<<arrival<<" ";
tot_idle_time+=(arrival-current_time);
current_time=v[i].first;
break;
}
}
}
}
}
cout<<endl;
///ct=ct-1;
double total_turn_time=0.0,total_waiting_time=0.0;
for(int i=1;i<=n;i++){
turn_time[i]=finish_time[i]-arrival_time[i];
total_turn_time+=(double)finish_time[i]-arrival_time[i];
waiting_time[i]=turn_time[i]-burst_time[i];
total_waiting_time+=(double)turn_time[i]-burst_time[i];
}
for(int i=1;i<=n;i++){
response_time[i]=response_time[i]-arrival_time[i];
}
for(int i=1;i<=n;i++){
cout<<"Process: P"<<i<<" End time: "<<finish_time[i]<< " Waiting time:"<<waiting_time[i]<<" "<<"Turnaround time:"<<turn_time[i];
cout<<" Response time "<<response_time[i];
cout<<endl;
}
cout<<endl;
cout<<"Average waiting time:"<<total_waiting_time/n<<endl;
cout<<"Average turnaround time:"<<total_turn_time/n<<endl;
cout<<"IDLE "<<tot_idle_time<<endl;
///cout<<"CONTEXT "<<ct<<endl;
}
/*
4
3
6
9
5
9
4
9
3
5
3
4
7
1
10
5
11
5
9
2
5
3
6
7
5
12
2
10
7
9
6
3
0
5
0
6
0
22
*/