最短剩余时间优先算法 c++

最短剩余时间优先算法（Shortest Remaining Time First, SRTF）是一种进程调度算法，在就绪队列中选择剩余执行时间最短的进程来执行。算法的思想是，每当一个进程执行完一个时间单元后，就暂停该进程，然后检查是否有新的进程到达，如果有进程比暂停的进程的剩余时间更短，则抢占CPU继续执行该进程，直到所有的进程都执行完毕。

在该算法中，每个进程都有自己的PID（进程ID）、到达时间、已执行时间和剩余时间。通过使用一个私有容器V_S来存储所有的进程，以及一个临时容器temp来存储已经到达的进程。在程序的编写过程中，可能遇到一些问题，比如如何确定时间片的大小，以及在每次传递一个已到达的进程后忘记清空temp数组，这些问题都需要注意。

相关问题

b编写c或c++程序实现最短剩余时间优先算法

以下是一个使用 C++ 实现最短剩余时间优先算法的示例程序：

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

using namespace std;

struct Process {
    int pid; // 进程 ID
    int arrival_time; // 到达时间
    int burst_time; // 运行时间
    int remaining_time; // 剩余时间

    Process(int pid, int arrival_time, int burst_time) {
        this->pid = pid;
        this->arrival_time = arrival_time;
        this->burst_time = burst_time;
        this->remaining_time = burst_time;
    }
};

bool operator<(const Process &a, const Process &b) {
    return a.remaining_time > b.remaining_time;
}

void shortestRemainingTimeFirst(vector<Process> &process_list) {
    int n = process_list.size();
    priority_queue<Process> pq;
    int current_time = 0;
    int total_waiting_time = 0;
    int total_turnaround_time = 0;

    // 按到达时间排序
    sort(process_list.begin(), process_list.end(), [](const Process &a, const Process &b) {
        return a.arrival_time < b.arrival_time;
    });

    // 开始调度
    int i = 0;
    while (i < n || !pq.empty()) {
        // 将到达时间小于等于当前时间的进程加入队列
        while (i < n && process_list[i].arrival_time <= current_time) {
            pq.push(process_list[i]);
            i++;
        }
        if (pq.empty()) {
            // 队列为空，当前时间跳到下一个进程到达时间
            current_time = process_list[i].arrival_time;
        } else {
            // 执行队首进程
            Process p = pq.top();
            pq.pop();
            total_waiting_time += current_time - p.arrival_time;
            current_time += p.remaining_time;
            total_turnaround_time += current_time - p.arrival_time - p.burst_time;
            // 更新剩余时间
            p.remaining_time = 0;
            // 处理后续到达的进程
            while (i < n && process_list[i].arrival_time <= current_time) {
                if (process_list[i].remaining_time < p.remaining_time) {
                    // 抢占当前进程
                    p.remaining_time -= current_time - process_list[i].arrival_time;
                    pq.push(p);
                    p = process_list[i];
                } else {
                    // 加入队列
                    pq.push(process_list[i]);
                }
                i++;
            }
            if (p.remaining_time > 0) {
                // 将剩余时间不为 0 的进程加入队列
                pq.push(p);
            }
        }
    }

    // 输出结果
    int total_time = current_time - process_list[0].arrival_time;
    int num_processes = process_list.size();
    double avg_waiting_time = (double) total_waiting_time / num_processes;
    double avg_turnaround_time = (double) total_turnaround_time / num_processes;
    printf("Total time: %d\n", total_time);
    printf("Average waiting time: %.2f\n", avg_waiting_time);
    printf("Average turnaround time: %.2f\n", avg_turnaround_time);
}

int main() {
    vector<Process> process_list = {
        Process(1, 0, 5),
        Process(2, 2, 3),
        Process(3, 3, 2),
        Process(4, 5, 4),
        Process(5, 6, 2)
    };
    shortestRemainingTimeFirst(process_list);
    return 0;
}

该程序实现了 SRTF 算法，并对一个进程列表进行调度，输出了总时间、平均等待时间和平均周转时间。需要注意的是，在实际使用中，进程到达时间和运行时间需要从外部读入，而不是在程序中硬编码。

C++实现最短剩余时间优先SRT调度算法

以下是使用C语言实现最短剩余时间优先（SRT）调度算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 进程控制块
typedef struct Process {
    int pid;  // 进程ID
    int arrival_time;  // 到达时间
    int burst_time;  // 执行时间
    int remaining_time;  // 剩余执行时间
    int completion_time;  // 完成时间
    int waiting_time;  // 等待时间
    int turnaround_time;  // 周转时间
} Process;

// 初始化进程控制块
void init_process(Process *p, int pid, int arrival_time, int burst_time) {
    p->pid = pid;
    p->arrival_time = arrival_time;
    p->burst_time = burst_time;
    p->remaining_time = burst_time;
    p->completion_time = 0;
    p->waiting_time = 0;
    p->turnaround_time = 0;
}

// 计算平均等待时间和平均周转时间
void calc_average_time(Process *p, int n, float *avg_waiting_time, float *avg_turnaround_time) {
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    for (int i = 0; i < n; i++) {
        total_waiting_time += p[i].waiting_time;
        total_turnaround_time += p[i].turnaround_time;
    }
    *avg_waiting_time = (float)total_waiting_time / n;
    *avg_turnaround_time = (float)total_turnaround_time / n;
}

// 最短剩余时间优先调度算法
void srt_schedule(Process *p, int n) {
    int current_time = 0;
    int completed = 0;
    int prev_pid = -1;

    while (completed != n) {
        int shortest_index = -1;
        int shortest_time = 999999;

        // 找到剩余时间最短的进程
        for (int i = 0; i < n; i++) {
            if (p[i].arrival_time <= current_time && p[i].remaining_time < shortest_time && p[i].remaining_time > 0) {
                shortest_index = i;
                shortest_time = p[i].remaining_time;
            }
        }

        if (shortest_index == -1) {
            // 如果当前没有进程可执行，增加时间片
            current_time++;
        } else {
            // 执行剩余时间最短的进程
            if (prev_pid != p[shortest_index].pid) {
                p[shortest_index].waiting_time += current_time - p[shortest_index].completion_time;
            }
            p[shortest_index].remaining_time--;
            current_time++;
            prev_pid = p[shortest_index].pid;

            if (p[shortest_index].remaining_time == 0) {
                // 进程执行完毕
                p[shortest_index].completion_time = current_time;
                p[shortest_index].turnaround_time = p[shortest_index].completion_time - p[shortest_index].arrival_time;
                completed++;
            }
        }
    }
}

int main() {
    int n;
    printf("请输入进程数：");
    scanf("%d", &n);

    Process *p = (Process*)malloc(n * sizeof(Process));
    for (int i = 0; i < n; i++) {
        int pid, arrival_time, burst_time;
        printf("请输入第%d个进程的到达时间和执行时间：", i + 1);
        scanf("%d%d", &arrival_time, &burst_time);
        init_process(&p[i], i + 1, arrival_time, burst_time);
    }

    srt_schedule(p, n);

    float avg_waiting_time, avg_turnaround_time;
    calc_average_time(p, n, &avg_waiting_time, &avg_turnaround_time);

    printf("进程ID\t到达时间\t执行时间\t完成时间\t等待时间\t周转时间\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n", p[i].pid, p[i].arrival_time, p[i].burst_time, p[i].completion_time, p[i].waiting_time, p[i].turnaround_time);
    }
    printf("平均等待时间：%f\n", avg_waiting_time);
    printf("平均周转时间：%f\n", avg_turnaround_time);

    free(p);
    return 0;
}

示例输出：

请输入进程数：5
请输入第1个进程的到达时间和执行时间：0 8
请输入第2个进程的到达时间和执行时间：1 4
请输入第3个进程的到达时间和执行时间：2 9
请输入第4个进程的到达时间和执行时间：3 5
请输入第5个进程的到达时间和执行时间：4 2
进程ID	到达时间	执行时间	完成时间	等待时间	周转时间
1	0		8		8		0		8
2	1		4		5		3		4
3	2		9		17		6		15
4	3		5		12		4		9
5	4		2		6		0		2
平均等待时间：2.600000
平均周转时间：7.600000