Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to prevent idle time from increasing after the last CPU burst in SRTF scheduling?

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.

like image 767
sjg9989 Avatar asked Sep 03 '25 04:09

sjg9989


1 Answers

You need to stop incrementing the idle time as soon as all the CPU bursts are complete on all the processes.

  • Add a process flag that is true when all CPU bursts are complete
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
};
  • Add a global flag that is true when all CPU bursts in all processes are complete
bool fAllCPUBurstsCompleted = false;    // true if every CPU burst in all processes has completed
  • Add a free function to set the global flag
/// @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;
}
  • Add code to the burst completion code to set the flags
        // 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();
            } 
  • Finally, add check for all bursts done before incrementing the idle time
        // 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:

  • I have removed is_cpu_burst() and related dead code
  • I have ported the file i/o to C++
like image 142
ravenspoint Avatar answered Sep 04 '25 18:09

ravenspoint