一、引言
在NOC大赛的备考过程中，操作系统的调度算法是一个重要的知识点。特别是FCFS（先来先服务）、SJF（短作业优先）和HRRN（高响应比优先）这几种算法，不仅要理解它们的基本原理，还需要深入掌握在一些特殊情况下可能出现的失效案例，以及抢占与非抢占模式的差异。
二、FCFS、SJF、HRRN算法基本原理及学习方法
- FCFS算法
- 原理：按照作业到达的先后顺序进行调度。例如，有三个作业J1、J2、J3，J1最先到达，那么它将最先被处理。
- 学习方法：可以通过简单的实例模拟来加深理解。比如在纸上记录不同作业的到达时间和执行时间，按照顺序依次计算每个作业的完成时间和平均等待时间等指标。
- SJF算法
- 原理：选择预计执行时间最短的作业优先执行。假设存在作业J1（执行时间5分钟）、J2（执行时间3分钟）、J3（执行时间4分钟），那么J2会最先被调度。
- 学习方法：构建不同执行时间的作业队列，手动计算并比较按照SJF算法和其他算法的执行顺序差异，同时注意其对平均周转时间的影响。
- HRRN算法
- 原理：响应比 =（等待时间+执行时间）/执行时间。每次选择响应比最高的作业执行。例如，作业J1等待时间为2分钟，执行时间为3分钟，响应比为(2 + 3)/3≈1.67；J2等待时间为1分钟，执行时间为2分钟，响应比为(1+2)/2 = 1.5，那么J1会被优先调度。
- 学习方法：多做一些不同等待时间和执行时间组合的计算练习，并且与FCFS和SJF算法在不同场景下的性能进行对比分析。
三、失效案例及应对
- 长作业饥饿问题
- 在SJF算法中，如果持续有短作业到达，长作业可能会长时间得不到执行。例如，不断有执行时间为1分钟的短作业到来，而一个执行时间为10分钟的长作业在队列后面就需要等待很长时间。
- 应对方法：可以考虑采用HRRN算法或者在SJF算法基础上增加一些机制，如设置最长等待时间，超过该时间的作业优先级提升。
- 响应时间波动问题
- 在某些情况下，FCFS算法可能会导致响应时间波动较大。比如一个长时间运行的作业后面跟着几个短时间作业，短时间作业的响应时间就会很长。
- 应对方法：采用HRRN算法可以根据当前的等待情况动态调整作业的执行顺序，从而减小响应时间的波动。
四、抢占与非抢占模式差异
- 非抢占模式
- 特点：一旦作业开始执行，就会一直执行到完成或者主动请求I/O等操作才会停止。例如，在FCFS的非抢占模式下，作业按照到达顺序依次完整执行。
- 影响：可能会导致长作业长时间占用处理器资源，影响系统的整体效率。
- 抢占模式
- 特点：当有更高优先级的作业到达或者满足一定条件时，正在执行的作业可以被暂停，让更高优先级的作业执行。比如在抢占式SJF算法中，如果有新的更短的作业到达，正在执行的较长作业可能会被暂停。
- 影响：可以提高系统的响应速度和资源利用率，但也增加了系统的复杂性和开销。
五、总结
在NOC大赛备考操作系统调度算法这部分内容时，要全面掌握FCFS、SJF、HRRN算法的基本原理、失效案例以及抢占与非抢占模式的差异。通过大量的实例分析、计算练习来加深理解，并且能够根据不同的需求选择合适的算法或者对算法进行改进，这样才能在考试中应对自如。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
