操作系统原理——进程调度与死锁

一、进程调度

进程的调度室指按照某种策略或算法从就绪进程中为当前空闲的cpu选择在其上运行的新进程

二、进程的调度算法

##1. 时间概念
周转时间是指从作业开始提交给系统开始，到作业完成为止系统的
平均周转时间T=N各种作业的周转时间之和除以n
带权周转时间=作业的周转时间/系统为它提供服务时间
响应时间=用户从提交一个请求开始至系统首次响应的时间为止的一段时间
截止时间=是指某个人物必须开始执行的最迟时间，或者必须完成的最迟时间

2. 调度算法优劣的准则

• 周转时间短
• 响应时间快
• 截止时间保证
• 系统吞吐量高
• CPU利用率好

3. 调度算法

1. 先来先服务(FCFS),从就绪队首选择最先到达就绪队列的进程
   优缺点：FCFS适合长进程，不利于短进程，适合CPU繁忙型的进程，不适合IO繁忙型的进程

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

3. 调度算法优先(SPL),分为非抢占式优先调度算法，抢占式优先权调度；优先权的调度类型：静态优先权和动态优先权

4. 时间片轮转调度算法(RR),时间片大小确认考虑的因素：

   1. 系统对响应时间的要求，响应时间越短，时间片取值应该越小。
   2. 就绪队列中的进程数
   3. 系统的处理能力

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

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

##实时系统中的调度

1. 提供必要的调度信息
2. 系统处理能力强
3. 采用抢占式调度机制
4. 具有快速切换机制

死锁

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

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

1. 互斥
2. 请求保持
3. 不剥夺
4. 环路等待

处理死锁的防范：

1. 预防死锁
2. 避免死锁，资源分配的状态分为安全和不安全状态，不安全状态不一定产生死锁，但是系统进入安全状态一定不会产生死锁，这样就可以避免死锁的产生，银行家算法就是一种系统避免系统死锁的一种检测算法，其基本思想是：一个进程提出资源请求后，系统进行资源的试分配。然后检测此次分配是否处于安全状态，若安全则按分配方案分配资源，否则不进行分配资源。
3. 检测并解除死锁
4. 忽略死锁

某系统中有3个并发进程，都需要同类资源4个，试问该系统保证不会发生死锁的最少资源数是______
如果一个进程有m个资源它就能够结束，不会使自己陷入死锁中。因此最差情况是每个进程有m-1个资源并且需要另外一个资源。如果留下有一个资源可用，那么其中某个进程就能够结束并释放它的所有资源，使其它进程也能够结束。所以避免死锁的条件是：r≥p(m-1)+1。带入上述条件公式：r≥3(4-1)+1=10*。所以答案为10个。