当前位置：首页 > news >正文

操作系统——（处理机调度与死锁）

news 来源：原创 2025/8/6 14:28:02

一、处理机调度

（1）层次

（2）进程调度

（3）调度算法

1.先来先服务算法（FCFS）

2.短作业优先算法（SJF）

3.高优先权算法（HPF）

4.多级反馈队列调度算法（HRRN）

二、实时调度

1.实现实时调度的基本条件

2.实时调度算法的分类

3.常用的两种实时调度算法

三、处理机死锁

1.什么叫死锁？

2.产生死锁的原因

3.产生死锁的必要条件

4.处理死锁的基本方法

一、处理机调度

处理机调度是对处理机进行分配。

（1）层次

高级调度（长程调度或作业调度），中级调度（内存调度），低级调度（短程调度或进程调度）

（2）进程调度

进程调度要解决问题：进程调度的时机，CPU调度过程（保存与分配）。

调度算法准则：

（1）面向系统的准则：系统吞吐量高，处理机利用效率好，各类资源的平衡利用，公平。

（2）面向用户的准则：用户时间短（周转时间T1=运行结束时间E1 - 提交时间S1，如果是平均周转时间就再处以n；带权周转时间W=T1周转时间/T2服务时间——（周转时间=服务时间+等待时间）），响应时间快，截至时间的保证，优先权准则。

（3）调度算法

1.先来先服务算法（FCFS）

按顺序完成进程。

优缺点：利于长作业，不利于短作业。利于CPU繁忙性作业，不利于I/O繁忙性作业。

2.短作业优先算法（SJF）

第一个进程运行后，后面的进程按照服务时间越短优先进行。

优缺点：能有效降低平均等待时间，提高吞吐量，而对长作业不利，为考虑作业的紧迫程度。

3.高优先权算法（HPF）

第一个进程运行后，后面的进程按照响应比越大优先进行。

优缺点：时间处于FCFS和SJF中间，短作业和长作业可以可以灵活运行。

4.多级反馈队列调度算法（HRRN）

前面的算法都有一些局限性，如果未指明长度时，短作业优先等算法都将无法使用。而多级反馈队列调度算法事先不需要知道各进程的执行时间，还可以较好地满足各种进程需要。

多级反馈队列算法会设置多个就绪队列，，每个队列都采用FCFS算法，第一个队列优先级最高，其他依次降低，优先级越高的队列时间片越小。第一个队列执行完毕，就执行第二个队列，如果第二行队列任务时间片结束时还没完成，就放入第三个队列。

注意：优先级高的先执行，第一队列空闲才会执行第二队列。

二、实时调度

1.实现实时调度的基本条件

（1）提供必要的信息：时间，资源要求，优先级。

（2）系统处理能力强：单处理机的处理时间/周期时间要小于等于1，多处理机的处理时间/周期时间要小于等于N。

（3）采用抢占式调度机制。

（4）具有快速切换机制：有对中断的快速响应能力和快速的任务分配能力。

2.实时调度算法的分类

根据实时任务性质不同可以分为硬实时调度和软实时调度。

根据调度方式不同可以分为非抢占调度和抢占调度算法。

根据调度的时间可以分为静态和动态调度算法。

现在着重讲解非抢占式和抢占式算法：

3.常用的两种实时调度算法

（1）最早截至时间优先算法EDF：根据任务开始截止时间来确定任务优先级，截至时间越早越优先。

（2）最低松弛度优先算法LLF：根据任务的松弛度来确定优先级。

（松弛度=必须完成的时间 - 还需运行的时间 - 当前时间）

注意：有些题目的完成时间在下一个周期到来之前。

A必须完成时间为20s，B必须完成时间为50s。此时A1用了10s完成，A2的松弛度小于B1松弛度，按理应该执行A2，但是A的周期式20s，此时为10s，A2还未到，只能运行B1.

三、处理机死锁

1.什么叫死锁？

一组进程分别拥有对方所想要的资源，但自身又不释放，双方处于僵持状态，此结果叫死锁。

2.产生死锁的原因

结论：

参与死锁的进程最少是两个(两个以上进程才会出现死锁)。

参与死锁的进程至少有两个已经占有资源。

参与死锁的所有进程都在等待资源。

参与死锁的进程是当前系统中所有进程的子集。

3.产生死锁的必要条件

（1）互斥条件：涉及的资源是非共享的。

（2）不剥夺条件：不能剥夺进程拥有资源。

（3）请求保持条件：进程在等待一新资源时继续占用已分配的资源。

（4）环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。

4.处理死锁的基本方法

四种：预防，避免，检测，解除。

图中的一些概念：

破坏请求和保持：系统要求所有进程要一次性地申请在整个运行过程中所需的全部资源。若系统有足够资源则完全分配。（即在执行时不会再提出资源请求在等待时未占有任何资源）

破坏不剥夺：一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源。以后需要时再重新申请。（实现复杂、要付出很大的代价（如以前工作的失效（本来已经99%，却因申请资源失败而变成0%）或执行的推迟)。

破坏环路：系统将所有资源按类型进行线性排序，并赋予不同的序号，所有进程对资源的请求必须严格按照资源序号递增的次序提出。

银行家算法中的数据结构：可利用资源available，最大需求矩阵max，分配矩阵allocation，需求矩阵need，系统可提供资源数目work，是否有足够进程（是否能运行）finish。有时还会又请求request（）。

死锁可以用分配图表示：（死锁状态的充分条件是：当且仅当资源分配图是不可完全简化的）

化简方法：

1）找一个只有分配边的进程，将分配边消去，使其成为孤立结点
2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边
3）重复以上步骤，若所有进程成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简化的。

一、处理机调度

（1）层次

（2）进程调度

（3）调度算法

1.先来先服务算法（FCFS）

2.短作业优先算法（SJF）

3.高优先权算法（HPF）

4.多级反馈队列调度算法（HRRN）

二、实时调度

1.实现实时调度的基本条件

2.实时调度算法的分类

3.常用的两种实时调度算法

三、处理机死锁

1.什么叫死锁？

2.产生死锁的原因

3.产生死锁的必要条件

4.处理死锁的基本方法

相关文章：