进程调度 非抢占短作业优先算法源代码（C语言）

### 进程调度非抢占短作业优先算法(C语言实现) #### 概述 在操作系统领域，进程调度是一项关键任务，其目标是通过合理地选择就绪队列中的进程执行顺序来提高系统的整体效率。其中，“非抢占短作业优先”(Non-Preemptive Shortest Job First, NSJF)是一种常用的进程调度算法。该算法的基本思想是：在所有已到达且尚未完成的进程中，选择执行时间最短的进程优先执行。 本文将详细介绍一个基于C语言实现的非抢占短作业优先调度算法的源代码，并对其中的关键函数进行解释。 #### 算法原理与实现 非抢占短作业优先算法的核心思想在于： 1. **按到达时间排序**：所有进程按照到达时间进行排序。 2. **选择最短作业**：在当前时刻已经到达的所有进程中选择剩余执行时间最短的那个进程运行。 3. **非抢占性**：一旦一个进程被选中执行，则它将一直运行到结束，不会被其他任何到达的更短进程所中断。 ### 代码分析 #### 数据结构定义 代码中首先定义了一个`struct pro`的数据结构，用于表示一个进程： ```c struct pro { int num; // 进程编号 int arriveTime; // 到达时间 int burst; // 执行时间 struct pro *next; // 指向下一个进程的指针 }; ``` #### 函数详解 1. **创建链表**：`struct pro* creatList()` - 功能：创建一个链表并初始化进程数据。 - 实现：通过循环获取用户输入的进程编号、到达时间和执行时间，然后调用`insert`函数将新进程插入到链表中。 2. **插入进程**：`void insert(struct pro *head, struct pro *s)` - 功能：根据进程到达时间将新进程插入到正确的位置。 - 实现：使用`searchByAT`函数找到具有最小到达时间的进程所在位置，并将新进程插入到该位置之后。 3. **查找进程**：`struct pro *searchByAT(struct pro *head, int AT)` - 功能：查找具有指定到达时间或更早到达的所有进程中的最后一个进程。 - 实现：遍历链表，直到找到第一个到达时间大于给定时间的进程为止，返回其前一个进程的地址。 4. **删除进程**：`void del(struct pro *p)` - 功能：删除由指针`p`指向的进程节点。 - 实现：修改`p`的下一个指针使其指向被删除进程的下一个进程，并释放被删除进程的内存。 5. **计算当前时间之前的进程数量**：`int getCount(struct pro *head, int time)` - 功能：计算在给定时间之前到达的所有进程的数量。 - 实现：遍历链表，统计到达时间小于等于给定时间的进程个数。 6. **选择最短进程**：`struct pro *SJF(struct pro *head, int count)` - 功能：从当前时间之前到达的进程列表中选择执行时间最短的进程。 - 实现：遍历所有在当前时间之前到达的进程，找到执行时间最短的进程，并返回其前一个进程的地址。 7. **运行进程**：`void run(struct pro *head)` - 功能：模拟进程调度过程，按NSJF算法运行进程。 - 实现：使用`getCount`函数确定当前时间到达的进程数量，然后根据数量的不同情况选择相应的处理策略：如果只有一个进程，则直接运行；如果有多个进程，则使用`SJF`函数选择最短进程运行。 ### 代码运行逻辑 1. **初始化进程**：通过`creatList`函数创建进程链表。 2. **循环调度**：使用`run`函数不断更新当前时间，并根据NSJF算法选择合适的进程运行。 3. **输出结果**：打印每个进程的编号、到达时间、启动时间、响应时间、完成时间和周转时间等信息。 通过以上分析可以看出，该C语言程序实现了非抢占短作业优先算法的基本功能，能够有效地模拟进程调度过程，并输出调度结果。这对于理解进程调度原理以及学习如何使用C语言实现具体算法具有重要意义。