转载声明：文章来源https://blog.csdn.net/2401_85464956/article/details/144252361

前言

操作系统有多种调度算法，本篇博客主要介绍了短作业优先调度算法（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);
}