### 调度算法知识点详解
#### 一、实验背景及目标
本次实验的主要目的是通过C语言编程的方式，实现两种常见的调度算法：先到先服务（First-Come First-Served, FCFS）和最短作业优先（Shortest Job First, SJF）。这两种调度算法在操作系统领域具有重要的地位，它们不仅能够帮助理解进程调度的基本原理，而且还能为更复杂的调度策略提供基础。
#### 二、实验环境与工具
本次实验采用的操作系统为MacOS，开发工具为Xcode。Xcode是苹果公司为MacOS提供的集成开发环境（IDE），它支持多种编程语言，包括C语言。选择MacOS作为实验环境是因为其稳定性和兼容性，而Xcode则提供了良好的开发体验和调试工具。
#### 三、实验原理
**1. 先到先服务调度算法（FCFS）**
先到先服务调度算法是一种简单的非抢占式调度算法。它的核心思想是按照进程到达的时间顺序来进行调度。当有多个进程同时竞争处理器资源时，CPU分配给最先到达的进程。该算法的特点是简单易实现，但是可能会导致某些短进程的等待时间过长。
- **流程图**：进程A到达 -> 进程B到达 -> 进程C到达 -> 处理器执行A -> 执行B -> 执行C
- **计算公式**：
- 进程等待时间 = 进程开始运行时间 - 进程提交时间
- 进程周转时间 = 进程结束时间 - 进程提交时间
**2. 最短作业优先调度算法（SJF）**
最短作业优先调度算法是一种更加高效的调度策略，它可以减少系统的平均等待时间和平均周转时间。该算法的核心思想是优先调度执行时间最短的进程。SJF算法可以分为非抢占式和抢占式两种。
- **非抢占式SJF**：一旦一个进程开始执行，就不会被其他更短的进程中断，直到当前进程完成。
- **抢占式SJF**：如果有一个新的、更短的进程到达，那么当前正在执行的进程会被暂停，CPU会分配给这个新到达的较短进程。
- **计算公式**：
- 进程等待时间 = 进程开始运行时间 - 进程提交时间
- 进程周转时间 = 进程结束时间 - 进程提交时间
#### 四、实验代码分析
下面是对部分代码段的详细解释：
```c
void input(struct attribute *p, int N) {
int i;
printf("Please input the job number, submit time and run time:\n");
for (i = 0; i < N; i++) {
scanf("%d%f%f", &p[i].jobnumber, &p[i].submittime, &p[i].runtime);
}
}
```
- **函数功能**：此函数用于输入每个任务的信息，包括任务编号、提交时间和运行时间。
- **参数解析**：
- `struct attribute *p`：指向结构体数组的指针。
- `int N`：表示任务的数量。
```c
void print(struct attribute *p, int N) {
int k;
float h = 0.0, g;
printf("Run order:");
printf("%d", p[0].jobnumber);
for (k = 1; k < N; k++) {
printf("-->%d", p[k].jobnumber);
}
printf("\nThe process's information:\n");
printf("\njobnum\tsubmit\trun\tstart\tfinal\twait\tturnaround\n");
for (k = 0; k < N; k++) {
h += p[k].turnaroundtime;
printf("%d\t%7.1f\t%7.1f\t%3.1f\t%7.1f\t%7.1f\t%7.1f\t\n",
p[k].jobnumber, p[k].submittime, p[k].runtime, p[k].starttime, p[k].finishtime, p[k].waittime, p[k].turnaroundtime);
}
g = h / N;
printf("\nThe average turnaround time is %-.2f\n", g);
}
```
- **函数功能**：此函数用于打印所有任务的执行顺序以及相关信息，并计算平均周转时间。
- **参数解析**：
- `struct attribute *p`：指向结构体数组的指针。
- `int N`：表示任务的数量。
#### 五、实验总结与思考
通过对FCFS和SJF两种调度算法的实现与分析，我们可以发现不同调度策略对系统性能的影响。FCFS算法虽然简单，但可能无法充分利用处理器资源；而SJF算法通过优化调度顺序，能够显著提高系统效率。然而，SJF算法的实现相对复杂，需要额外的工作来判断哪个任务是最短的。此外，实际应用中还需要考虑更多因素，比如优先级、抢占机制等。
通过本次实验，我们不仅加深了对基本调度算法的理解，还锻炼了编程实践能力。在未来的学习和研究中，我们可以进一步探索更多高级的调度策略及其应用场景。
