典型的调度算法--短作业优先调度算法

前言

操作系统有多种调度算法，本篇博客主要介绍了短作业优先调度算法（SJF）。本算法思想同样也适用短进程优先调度算法（SPF）,与之不同的是短进程优先调度算法可以分为抢占式和非抢占式。本篇博客主要介绍短作业优先调度算法和一些性能指标。

1.基本概念

1.1短作业优先调度算法

短作业优先（Shortest Job Next，SJN）调度算法是一种进程调度算法。其核心思想是，在所有就绪进程中，总是优先选择估计运行时间最短的进程来占用 CPU 运行。一旦一个进程开始运行，它就会一直运行直到结束，不会被其他进程抢占 CPU。

1.2算法步骤

进程到达：当有新进程到达就绪队列时，系统会计算每个进程的服务时间（即进程执行所需的时间），并将其与就绪队列中已有进程的服务时间进行比较。
选择进程：在每次需要调度进程时，调度程序会在就绪队列中寻找服务时间最短的进程，然后将 CPU 分配给这个进程。
进程执行：被选中的进程会一直执行，直到它完成所有的任务，然后释放 CPU。此时，调度程序会再次在就绪队列中寻找下一个最短进程进行调度。

1.3性能指标

一般评价某种调度算法性能有多种指标，这里介绍主要的指标

1.3.1周转时间

周转时间：作业或进程从开始到结束所经历的时间，计算公式为

周转时间=作业完成时间-作业提交时间

1.3.2带权周转时间

但凭借周转时间，并不能评价不同进程的，因为有的进程本身可能需要的服务时间长即（长进程），因此引入带权周转时间，计算公式为：

带权周转时间：作业周转时间 / 作业实际运行时间

1.3.3其他

平均周转时间，平均带权周转时间就是字面意思，求所有进程的周转时间的平均值和带权周转时间的平均值

2.代码实现

2.1进程结构体

在了解算法思想过后，实现代码前需要先确定如何定义结构体表示进程。可以根据性能指标确定部分成员，结构体定义具有一定的主观性，这里提供一种：

//表状态等待，运行，完成
enum stateList {W,R,F
};
// 定义结构体表示进程
typedef struct {char name;int burst_time;int arrival_time;int start_time;int completion_time;int turnaround_time;double weighted_turnaround_time;enum stateList state; 
} Process;

2.2初始化结构体

这里你可以根据个人需求进行改写，优化，使用scanf输入增加交互性等

    // 定义示例进程数量int n = 5;// 定义进程数组并初始化示例进程信息Process processes[5];// 初始化processes[0].name = 'A';processes[0].burst_time = 4;processes[0].arrival_time = 0;processes[0].state = W;processes[1].name = 'B';processes[1].burst_time = 3;processes[1].arrival_time = 1;processes[1].state = W;processes[2].name = 'C';processes[2].burst_time = 5;processes[2].arrival_time = 2;processes[2].state = W;processes[3].name = 'D';processes[3].burst_time = 2;processes[3].arrival_time = 3;processes[3].state = W;processes[4].name = 'E';processes[4].burst_time = 4;processes[4].arrival_time = 4;processes[4].state = W;

2.3核心算法

根据算法思想可以编写如下程序，并不是最优的，仅供参考

void staticCalculateProcessTimes(Process processes[], int n) {int current_time = 0;int completed_count = 0;int front = 0, rear = 0;Process* ready_queue[100];  // 就绪队列while (completed_count < n){for (int i = 0; i < n; i++) {if (processes[i].arrival_time <= current_time && processes[i].state==W) {ready_queue[rear++] = &processes[i];processes[i].state = R;}}if (front == rear) {current_time++;continue;}//从就绪队列中选择服务时间短的int i = front+1;while (i != rear) {if (ready_queue[front]->burst_time > ready_queue[i]->burst_time){Process* temp = ready_queue[front];ready_queue[front] = ready_queue[i];ready_queue[i] = temp;}   i++;}Process* current_process = ready_queue[front];current_process->start_time = current_time;current_time += current_process->burst_time;current_process->completion_time = current_time;current_process->turnaround_time = current_process->completion_time - current_process->arrival_time;current_process->weighted_turnaround_time = (double)current_process->turnaround_time / current_process->burst_time;completed_count++;front++;}}

2.4输出

为了更好地展示进程的信息，可以任意设计。这里提供一种：

void printInfo(Process processes[], int n) {// 统计平均周转时间和平均带权周转时间double total_turnaround_time = 0;double total_weighted_turnaround_time = 0;for (int i = 0; i < n; i++) {total_turnaround_time += processes[i].turnaround_time;total_weighted_turnaround_time += processes[i].weighted_turnaround_time;}double average_turnaround_time = (double)total_turnaround_time / n;double average_weighted_turnaround_time = total_weighted_turnaround_time / n;printf("--------------------------------------先来先服务算法------------------------------------------------\n");// 输出每个作业的信息以及平均时间printf("作业名\t提交时间\t服务时间\t开始时间\t完成时间\t周转时间\t带权周转时间\n");for (int i = 0; i < n; i++) {printf("%c\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%.2f\n", processes[i].name, processes[i].arrival_time, processes[i].burst_time,processes[i].start_time, processes[i].completion_time, processes[i].turnaround_time, processes[i].weighted_turnaround_time);}printf("平均周转时间\t\t%.2f\n", average_turnaround_time);printf("平均带权周转时间\t%.2f\n", average_weighted_turnaround_time);
}

结语

本篇博客带你了解了短作业优先调度算法，并用代码实现了该算法，你可以参考本篇博客尝试编写先来先服务调度算法、时间片轮转调度算法，优先级调度算法等，希望能够对你有所帮助！！！