最短剩余时间优先算法C语言
时间: 2023-06-02 19:02:50 浏览: 55
#include <stdio.h>
#include <stdlib.h>
// 进程结构体
typedef struct Process {
int pid; // 进程ID
int arrivalTime; // 到达时间
int burstTime; // 执行时间
int remainingTime; // 剩余执行时间
} Process;
// 创建进程
Process* createProcess(int pid, int arrivalTime, int burstTime) {
Process* process = (Process*) malloc(sizeof(Process));
process->pid = pid;
process->arrivalTime = arrivalTime;
process->burstTime = burstTime;
process->remainingTime = burstTime;
return process;
}
// 交换两个进程的位置
void swap(Process** a, Process** b) {
Process* temp = *a;
*a = *b;
*b = temp;
}
// 最短剩余时间优先算法
void SRTF(Process** processes, int n) {
int currentTime = 0; // 当前时间
int completed = 0; // 已完成的进程数
int i, shortest;
// 循环直到所有进程都完成
while (completed != n) {
shortest = -1;
// 找到剩余时间最短的进程
for (i = 0; i < n; i++) {
if (processes[i]->arrivalTime <= currentTime && processes[i]->remainingTime > 0) {
if (shortest == -1 || processes[i]->remainingTime < processes[shortest]->remainingTime) {
shortest = i;
}
}
}
// 如果没有找到进程,则时间加一
if (shortest == -1) {
currentTime++;
} else {
// 执行该进程
processes[shortest]->remainingTime--;
currentTime++;
// 如果该进程已经完成,更新完成时间和等待时间
if (processes[shortest]->remainingTime == 0) {
processes[shortest]->completionTime = currentTime;
processes[shortest]->waitingTime = currentTime - processes[shortest]->arrivalTime - processes[shortest]->burstTime;
completed++;
}
}
}
}
// 计算平均等待时间和平均周转时间
void calculateAverageTimes(Process** processes, int n, float* avgWaitingTime, float* avgTurnaroundTime) {
int i;
*avgWaitingTime = 0;
*avgTurnaroundTime = 0;
for (i = 0; i < n; i++) {
*avgWaitingTime += processes[i]->waitingTime;
*avgTurnaroundTime += processes[i]->completionTime - processes[i]->arrivalTime;
}
*avgWaitingTime /= n;
*avgTurnaroundTime /= n;
}
int main() {
int n, i, pid, arrivalTime, burstTime;
float avgWaitingTime, avgTurnaroundTime;
// 读入进程数
printf("Enter the number of processes: ");
scanf("%d", &n);
// 创建进程数组
Process** processes = (Process**) malloc(n * sizeof(Process*));
// 读入每个进程的信息
for (i = 0; i < n; i++) {
printf("Enter the arrival time and burst time of process %d: ", i + 1);
scanf("%d %d", &arrivalTime, &burstTime);
processes[i] = createProcess(i + 1, arrivalTime, burstTime);
}
// 对进程按照到达时间排序
for (i = 0; i < n - 1; i++) {
int j;
for (j = 0; j < n - i - 1; j++) {
if (processes[j]->arrivalTime > processes[j + 1]->arrivalTime) {
swap(&processes[j], &processes[j + 1]);
}
}
}
// 执行最短剩余时间优先算法
SRTF(processes, n);
// 计算平均等待时间和平均周转时间
calculateAverageTimes(processes, n, &avgWaitingTime, &avgTurnaroundTime);
// 输出结果
printf("Process\tArrival Time\tBurst Time\tCompletion Time\tWaiting Time\tTurnaround Time\n");
for (i = 0; i < n; i++) {
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n", processes[i]->pid, processes[i]->arrivalTime, processes[i]->burstTime, processes[i]->completionTime, processes[i]->waitingTime, processes[i]->completionTime - processes[i]->arrivalTime);
}
printf("Average waiting time: %.2f\n", avgWaitingTime);
printf("Average turnaround time: %.2f\n", avgTurnaroundTime);
return 0;
}