操作系统概论:第三章 进程调度与死锁

进程调度的功能是按照某种策略或算法从就绪态进程中为当前空闲的 cPU 选择在其上运行的新进程。

选择调度方式和算法的若干准则：

1 ）周转时间短

周转时间是指从作业被提交给系统开始，到作业完成为止系统的平均周转时间丁等于 N 各作业的周转时间之和除以 n T = ( tl + tZ + t3 ＋ … ＋ tn ) / n 作业的周转时间 T 与系统为它提供的服务时间 TS 之比为 W = T/TS，被称为带权周转时间，那么 n 个作业的平均带权周转时间为: T = ( t1 / ts1 + t2 /ts2+......+tn / t sn ) / n 服务时间 TS 是一个作业在 CpU 上执行的总时间 .

2 ）响应时间快响应时间是指从用户提文一个请求开始直至系统首次产生响应的时间为止的一段时间

3 ）截止时间的保证截止时间是指某个任务必须开始执行的最迟时间，或必须完成的最迟时间

4 ）系统吞吐量高

5 ）处理机利用率好．

调度算法；

1 ）先来先服务（FCFS ）从就绪列的队首选择最先到达就绪队列的进程， FCFS 适合长进程，不利于短进程，适合 CpO 萦忙性进程，不适合 10 铁忙性进程。

2 ）短进程优先调度算法（ SPF）短进程优先算法能有效降低进程的平均等待时间，提高系统的吞吐，

3 ）优先调度算法（ PSL ）类型：非抢占式优先权调度算法、抢占式优先权调度算法奋优先权的类型；静态优先权和动态优先权

4 ）时间片轮转调度算法（ RR )

时间片大小的确定考虑的因素：

1.系统对响应时间的要求，晌应时间越短，时间片取值应该越小。

2.就绪队列中进程的数目。

3.系统的处理能力

5 ）多级队列调度不同的队列优先权不同，调度算法也可能不同。

6 ）多级反馈队列调度队列优先权越高，时间片越短，时间片通常成倍增长

实时系统中的调度：

基本条件

1）提供必要的调度信息

2 ）系统处理能力强

3 ）采用抢占式调度机制

4 ）具有快速切换机制

常用的调度算法： 1 ）最早截至时间优先（EDF） 2 ）最低松弛度优先（ LLF )

多处理器调度：多处理器系统的类型：紧密耦合、松弛耦合、对称处理器系统、非对称处理器系统

进程调度方式： 1 ）自调度 2 ）成组调度 3 ）专用处理器分配

自调度：采用自调度的系统中有一个公共的就绪队列，任何一个空闲的处理器都可以从该就绪队列中选择一个进程或者一个线程运行。

在多处理器环境下， FCFS 是较好的自调度算法

自调度优点: 1）易移植 2 ）有利于提高 CpU 的利用率

自调度缺点: 1）瓶颈问题 2 ）低效性 3 ）程序切换频繁．

死锁：死锁是由多个进程竞争共享资源而引起的进程不能向前推进的臼死状态

产生死锁的原因：竞争死锁资源且分配资源的顺序不当

产生死锁的必要条件: 1）互斥 2 ）请求保持 3 ）不剥夺 4 ）环路等待

S 为死锁的充分条件是：当且仅当 S 状态的资源分配图是不可完全简化的

处理死锁的方法：预防死锁、避免死锁、检测并解除死锁和忽略死锁。

死锁的避免：资源分配的状态分为安全状态和不安全状态，不安全状态不一定产生死锁，但是系统进入安全状态以后，就可以避免死梢的产生，所以避免死锁的实质在于使系统处于安全状态。

银行家算法：

基本思想：一个进程提出资源请求后，系统进行资源的试分配。然后检测此次分配是否处于安全状态，若安全则按分配方案分配资源，否则不分配资源。

试分配过程：