In my current SRTF scheduling simulation, I'm encountering an issue regarding how CPU idle time is calculated.
When the last process begins its final I/O burst, the CPU becomes idle, and the idle_time counter continues to increase. However, since the final CPU burst of the last process has already been completed, I don't want this remaining time (during its I/O) to be counted as CPU idle time — because there's no more CPU work pending for any process at that point.
Is there a clean way to avoid increasing the CPU idle time after the final CPU burst of the last process is finished?
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Process {
int id;
int arrival;
vector<int> bursts;
int burst_index = 0;
int remaining_time = 0;
int end_time = 0;
int next_ready_time = 0;
bool completed = false;
bool is_cpu_burst() const {
return burst_index % 2 == 0;
}
};
struct Compare {
bool operator()(Process* a, Process* b) const {
if (a->remaining_time != b->remaining_time)
return a->remaining_time > b->remaining_time;
if (a->next_ready_time != b->next_ready_time)
return a->next_ready_time > b->next_ready_time;
return a->id > b->id;
}
};
int main() {
FILE* fin = fopen("srtf.inp", "r");
FILE* fout = fopen("srtf.out", "w");
int n;
fscanf(fin, "%d", &n);
vector<Process> processes(n);
for (int i = 0; i < n; ++i) {
int x;
fscanf(fin, "%d", &x);
processes[i].id = i;
processes[i].arrival = x;
processes[i].next_ready_time = x;
while (fscanf(fin, "%d", &x) && x != -1) {
processes[i].bursts.push_back(x);
}
processes[i].remaining_time = processes[i].bursts[0];
}
int time = 0;
int idle_time = 0;
int completed_count = 0;
priority_queue<Process*, vector<Process*>, Compare> ready_queue;
vector<Process*> io_waiting;
Process* current = nullptr;
while (completed_count < n) {
// Handle I/O completion
for (int i = 0; i < (int)io_waiting.size();) {
Process* p = io_waiting[i];
if (p->next_ready_time <= time) {
if (p->burst_index < (int)p->bursts.size()) {
p->remaining_time = p->bursts[p->burst_index];
ready_queue.push(p);
}
else {
p->end_time = time;
p->completed = true;
completed_count++;
}
io_waiting.erase(io_waiting.begin() + i);
}
else {
++i;
}
}
// Add newly arrived processes to the ready queue
for (int i = 0; i < n; ++i) {
Process& p = processes[i];
if (p.arrival == time && p.burst_index == 0) {
p.remaining_time = p.bursts[0];
ready_queue.push(&p);
}
}
// Handle CPU burst completion
if (current && current->remaining_time == 0) {
if (current->burst_index + 1 >= (int)current->bursts.size()) {
current->end_time = time;
current->completed = true;
completed_count++;
}
else {
current->burst_index++;
if (current->is_cpu_burst()) {
current->remaining_time = current->bursts[current->burst_index];
}
else {
current->next_ready_time = time + current->bursts[current->burst_index];
io_waiting.push_back(current);
current->burst_index++;
}
}
current = nullptr;
}
// Preemption or assign a new process
if (!ready_queue.empty()) {
if (!current || ready_queue.top()->remaining_time < current->remaining_time) {
if (current)
ready_queue.push(current);
current = ready_queue.top();
ready_queue.pop();
printf("Time=%d selectedProcess=%d idleTime=%d\n", time, current->id, idle_time);
}
}
// Execute or idle
if (current) {
current->remaining_time--;
}
else {
idle_time++;
}
time++;
printf("Final idle_time = %d\n", idle_time); // Optional debug output
}
// Output results
if (fout != nullptr) {
fprintf(fout, "%d\n", idle_time); // ✅ Total idle time
for (int i = 0; i < n; ++i) {
fprintf(fout, "%d\n", processes[i].end_time);
}
fclose(fout);
}
else {
fprintf(stderr, "Failed to open output file.\n");
}
return 0;
}
srtf.inp
20
3 1 24 2 2 10 35 6 5 6 25 7 31 2 3 19 10 4 6 3 46 2 43 3 -1
5 10 33 4 11 5 37 3 23 6 44 12 5 2 25 7 15 16 4 3 9 5 -1
9 16 16 1 40 6 16 1 35 14 43 3 3 1 -1
16 1 15 7 7 10 15 3 21 4 6 8 39 4 10 15 -1
26 10 41 7 15 8 42 3 40 2 22 8 34 3 9 7 22 5 34 1 19 6 37 4 46 19 35 10 12 2 -1
33 7 47 8 49 8 18 3 37 5 38 10 36 6 1 6 13 8 35 2 -1
50 7 24 8 37 2 41 2 40 3 25 3 24 6 12 1 3 4 24 3 38 10 30 14 8 10 23 21 16 9 -1
60 10 4 1 14 5 22 5 27 5 5 6 6 8 34 3 5 19 4 7 44 9 -1
67 9 15 8 40 7 22 7 11 6 47 9 6 9 24 15 47 15 -1
1054 5 12 8 11 6 25 7 11 9 14 5 40 -1
1070 3 7 5 19 10 13 9 37 4 45 5 18 9 46 6 11 5 37 -1
1084 4 6 3 17 8 3 8 13 3 15 8 43 18 26 5 35 10 39 -1
1100 6 6 2 40 21 21 6 14 1 41 1 41 1 39 3 3 -1
1113 7 21 4 38 -1
1137 1 42 2 47 20 8 6 16 5 7 6 19 10 46 9 9 5 36 9 43 8 14 8 3 22 45 -1
1178 6 50 22 20 3 5 2 8 6 27 5 22 9 5 14 10 5 25 3 40 5 11 6 14 10 8 -1
1215 8 37 8 6 5 21 5 21 4 48 3 13 1 44 7 45 7 40 3 17 2 31 5 -1
1264 6 39 1 24 -1
1286 7 30 9 4 2 25 1 23 5 4 2 5 -1
1336 7 33 8 20 -1
533
657
531
470
479
663
412
666
624
585
1232
1420
1495
1397
1193
1654
1724
1617
1335
1410
1411
This is the correct output that I expect from the simulation.
I implemented a simulation of SRTF (Shortest Remaining Time First) scheduling using a priority queue. The simulation tracks CPU bursts and I/O bursts for each process, including the total idle time when no process is available for execution.
I expected that once the final CPU burst of the last process is completed, the CPU would not accumulate any more idle time, even if that process still has an I/O burst remaining — since there's no more CPU work to be done.
However, in my implementation, the simulation continues increasing the idle_time even after all CPU bursts are completed, just because the last process is still doing I/O.
You need to stop incrementing the idle time as soon as all the CPU bursts are complete on all the processes.
struct Process
{
int id;
int arrival;
std::vector<int> bursts;
int burst_index = 0;
int remaining_time = 0;
int end_time = 0;
int next_ready_time = 0;
bool completed = false;
bool fLastBurstCompleted = false; // true if every CPU burst complete
};
bool fAllCPUBurstsCompleted = false; // true if every CPU burst in all processes has completed
/// @brief set fAllCPUBurstsCompleted true if last CPU burst completed for every process
bool isLastBurstCompleted()
{
for (auto &p : processes)
if (!p.fLastBurstCompleted)
return false;
fAllCPUBurstsCompleted = true;
return true;
}
// Handle CPU burst completion
if (current && current->remaining_time == 0)
{
// check for last burst in current process
if ( current->burst_index == current->bursts.size()-2 ) {
// set process flag
current->fLastBurstCompleted = true;
// set global flag if all bursts done
isLastBurstCompleted();
}
// Execute or idle
if (current)
{
current->remaining_time--;
}
else
{
/* There is no current process
Increase idle time, unless all CPU bursts have been completed
*/
if ( ! fAllCPUBurstsCompleted )
idle_time++;
}
With this code, the output becomes
Total Idle Time: 541
Process 0 end time: 657
Process 1 end time: 531
Process 2 end time: 470
Process 3 end time: 479
Process 4 end time: 663
Process 5 end time: 412
Process 6 end time: 666
Process 7 end time: 624
Process 8 end time: 585
Process 9 end time: 1232
Process 10 end time: 1420
Process 11 end time: 1495
Process 12 end time: 1397
Process 13 end time: 1193
Process 14 end time: 1654
Process 15 end time: 1724
Process 16 end time: 1617
Process 17 end time: 1335
Process 18 end time: 1410
Process 19 end time: 1411
You can find the complete application code at https://codeberg.org/JamesBremner/SRTF_Shortest_Remaining_Time_First/src/branch/main/src/main.cpp
Notes on code:
is_cpu_burst()
and related dead codeIf you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With