上一篇文章总结了一些关于进程的知识点，这章的目的也是根据《计算机操作系统》（第四版、汤子瀛）的书来总结一下进程调度和死锁的相关知识点，这一章其实和上一章紧密相连，所以如果没有基础或基础较差（对一些概念还有些模糊）的朋友们先去看上一章的简答题总结，然后再看这一章的内容会比较好接受一些。当然，这一章还包括一些所谓的与“计算”相关的知识点，能够方便大家理解相应的知识点，如银行家算法的应用。PS：阿婆主只是知识的搬运工~分享者~
目录（检索你需要知道的知识点）
第三章操作系统的基础知识点
3.1.1 引起进程调度的因素有哪些？
3.1.2 试说明低级调度的主要功能。
3.1.3 在采用优先级调度算法的系统中，请回答以下问题：
（1）没有执行进程是否一定没有就绪进程？
（2）没有执行进程，没有就绪进程，或者两者都没有，是否可能？各是什么情况？
（3）执行进程是否一定是可运行进程中优先权最高的？
3.1.4 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销时间，若分别按先来先服务（FCFS）、非抢占及抢占的短作业优先（SJF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法（FB，第i级队列的时间片=）进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。
3.1.5 高响应比优先调度算法的优点是什么？
3.1.6 为什么说多级反馈队列调度算法能较好地满足各方面用户的需要？
3.1.7 有一个内存中只能装入两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。有如下表所示的作业序列，表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高。
（1）列出所有作业进入内存的时刻以及结束的时刻。
（2）计算作业的平均周转时间。
3.2.1 对下面的5个非周期性实时任务，按最早开始截止时间优先调度算法应如何进行CPU调度？
3.2.2 若有3个周期性任务，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为10ms；任务C要求每50ms执行一次，执行时间为15ms，应如何按最低松弛度优先算法对它们进行CPU调度？
3.3.1 在哲学家就餐问题中，如果将先拿起左边的筷子的哲学家称为左撇子，而将先拿起右边的筷子的哲学家称为右撇子，请说明在同时存在左撇子和右撇子的情况下，任何就座安排都不会产生死锁。
3.3.2
（1）3个进程共享4个同种类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？
（2）n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n。说明该系统不会因竞争该类资源而死锁。
（3）在（2）中，如果没有“每个进程都需要用该类资源”的限制，情况又会如何？
3.3.3 不安全状态是否必然导致系统进入死锁状态？
3.3.4 在银行家算法中，若出现下面的资源分配情况：
（1）计算分配矩阵的值，并判断该状态是否安全？
（2）若进程P2提出请求Request(1,2,2,2)，系统能否将资源分配给它？
（3）如果系统立即满足P2的上述请求，请问系统是否立即进入死锁状态？
3.3.5 假定某计算机系统有R1设备3台，R2设备4台，它们被P1、P2、P3和P4这4个进程互斥共享，且已知这4个进程均以下面所示的顺序使用现有设备：申请R1
申请R2
申请R1
释放R1
释放R2
释放R1
请问系统运行过程中是否可能产生死锁？如果有可能的话，请举出一种情况，并画出表示该死锁状态的进程--资源图。
3.3.6 死锁检测程序的运行频率较高或较低，各有什么优缺点？
3.3.7 解除死锁，在选择撤销进程或被抢占资源的进程时，可考虑哪些因素？
第三章操作系统的基础知识点
3.1 进程调度及调度算法中的典型问题分析
3.1.1 引起进程调度的因素有哪些？
答：引起进程调度的因素有：
（1）正在执行的进程正常终止或异常终止。
（2）正在执行的进程因某种原因而阻塞。具体包括：
a、提出I/O请求后被阻塞；
b、在调用wait操作时因资源不足而阻塞；
c、因其他原因执行block原语而阻塞等。
（3）在引入时间片的系统中，时间片用完。
（4）在抢占调度方式中，就绪队列中某进程的优先权变得比当前正在执行的进程高，或者有优先权更高的进程进入就绪队列。
3.1.2 试说明低级调度的主要功能。
答：低级调度用于决定就绪队列中的哪个进程应获得处理机，并由分派程序把处理机分配给该进程。其主要功能有：
（1）保存当前进程的处理机现场信息。
（2）按某种算法选择投入执行的新进程。
（3）恢复新进程的现场，从而将处理机分配给新进程。
3.1.3 在采用优先级调度算法的系统中，请回答以下问题：
（1）没有执行进程是否一定没有就绪进程？
（2）没有执行进程，没有就绪进程，或者两者都没有，是否可能？各是什么情况？
（3）执行进程是否一定是可运行进程中优先权最高的？
答：
（1）是。如果有就绪进程，那么调度程序必定会把CPU分配给其中的一个进程，因此必定会有执行进程。
（2）有可能系统中有执行进程但无就绪进程，此时，除了执行进程外，系统中可能没有其他进程，或者有其他进程但这些进程都分别在等某个事件（如I/O操作）完成而均处于阻塞状态；前一种情况下，如果正在执行的进程终止或也因等待某个事件而进入阻塞状态，若其他进程还没被唤醒，则系统变为既没有执行进程也没有就绪进程的状态。
（3）不一定。在采用非抢占优先级调度算法时，某个进程正在执行的过程中，若有一个优先权更高的进程进入就绪状态，由于不进行CPU抢占，执行进程便不再是可运行进程中优先权最高的进程。若采用抢占策略，则执行进程一定是可运行进程中优先权最高的。
3.1.4 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销时间，若分别按先来先服务（FCFS）、非抢占及抢占的短作业优先（SJF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法（FB，第i级队列的时间片=）进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| A | 0 | 3 |
| B | 2 | 6 |
| C | 4 | 4 |
| D | 6 | 5 |
| E | 8 | 2 |
分析：进程调度的关键是理解和掌握调度所采用的算法，FCFS算法选择最早进入就绪队列的进程投入执行；SJF算法选择估计运行时间最短的进程投入执行，采用抢占方式时，若新就绪的进程运行时间比正在执行的进程的剩余运行时间短，则新进程将抢占CPU；HRRN算法选择响应比（响应比=（运行时间+等待时间）/运行时间）最高的进程投入执行；RR算法中，就绪进程按FIFO方式排队，CPU总是分配给队首的进程，并只能执行一个时间片；FB算法将就绪进程排成多个不同优先权及时间片的队列，新就绪进程总是按FIFO方式先进入优先权最高的队列，CPU也总是分配给较高优先权队列上的队首进程，若执行一个时间片仍未完成，则转入下一级队列的末尾，最后一级队列则采用时间片轮转方式进行调度。
答：对上述5个进程按各种调度算法调度的结果如下图所示，从中可以计算出各进程的完成时间、周转时间和平均周转时间如下表所示。
|
|
进程 | A | B | C | D | E | 平均 |
|---|---|---|---|---|---|---|---|
| FCFS | 完成时间 周转时间 带权周转时间 |
3 3 1.00
|
9 7 1.17 |
13 9 2.25 |
18 12 2.40 |
20 12 6.00 |
8.6 2.56 |
| SJF（非抢占） | 完成时间 周转时间 带权周转时间 |
3 3 1.00
|
9 7 1.17
|
15 11 2.75
|
20 14 2.80
|
11 3 1.50
|
7.6 1.84 |
| SJF（抢占） | 完成时间 周转时间 带权周转时间 |
3 3 1.00
|
15 13 2.16
|
8 4 1.000
|
20 14 2.80
|
10 2 1.00
|
7.2 1.59 |
| HRRN | 完成时间 周转时间 带权周转时间 |
3 3 1.00
|
9 7 1.17
|
13 9 2.25
|
20 14 2.80
|
15 7 3.50
|
8 2.14 |
| RR(q=1) | 完成时间 周转时间 带权周转时间 |
4 4 1.33
|
18 16 2.67
|
17 13 3.25
|
20 14 2.80
|
15 7 3.50
|
10.8 2.71
|
| FB(q= |
完成时间 周转时间 带权周转时间 |
3 3 1
|
17 15 2.50
|
18 14 3.50
|
20 14 2.80
|
14 6 3.00
|
10.4 2.56
|
| FB(q= (立即抢占) |
完成时间 周转时间 带权周转时间 |
4 4 1.33
|
18 16 2.67
|
15 11 2.75
|
20 14 2.80
|
16 8 4.00
|
10.6 2.87
|
3.1.5 高响应比优先调度算法的优点是什么？
答：高响应比优先调度算法是一种高优先权优先调度算法，由于其中的优先权，即响应比等于：
响应比=响应时间/要求服务时间=（等待时间+要求服务时间）/要求服务时间
因此，它具有以下的优点：
（1）如果作业（进程）的等待时间相同，则要求服务时间最短的作业（进程）的优先权最高，因此它有利于短作业（进程），从而可降低作业（进程）的平均周转时间，提高系统吞吐量。
（2）如果作业（进程）的要求服务时间相同，则其优先权将取决于作业到达（或进程进入就绪状态）的先后次序，因此体现了公平的原则。
（3）如果作业（进程）较长，它的优先权将随着等待时间的增长而提高，从而使长作业（进程）不会长期得不到服务。
3.1.6 为什么说多级反馈队列调度算法能较好地满足各方面用户的需要？
答：对终端型作业用户而言，他们提交的作业大多属于交互型作业，作业通常较小，系统只要能使这些作业在第一个队列所规定的时间片内完成，便可使他们都感到满意。对于短批处理作业用户而言，开始时他们的作业像终端型作业一样，如果仅在第一个队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间；对于稍长的作业，通常也只需在第二队列和第三队列各执行一个时间片即可完成，其周转时间仍然很短。对长批处理作业用户而言，他们的作业将依次在第1，2，......，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理；而且每往下降一个队列，其得到的时间片将随着增加，故可进一步缩短长作业的等待时间。
3.1.7 有一个内存中只能装入两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。有如下表所示的作业序列，表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高。
| 作业名 | 到达时间 | 估计运行时间 | 优先数 |
|---|---|---|---|
| A | 10:00 | 40分 | 5 |
| B | 10:20 | 30分 | 3 |
| C | 10:30 | 50分 | 4 |
| D | 10:50 | 20分 | 6 |
（1）列出所有作业进入内存的时刻以及结束的时刻。
（2）计算作业的平均周转时间。
答：根据题意，作业的调度和运行情况如下图所示，从图中可以看出。
（1）A、B、C、D各作业进入内存的时刻分别是10:00、10:20、11:10、10:50；它们完成的时刻分别是11:10、10:50、12:00、12：20。
（2）A、B、C、D的周转时间分别是70分钟、30分钟、90分钟、90分钟，故它们的平均周转时间为70分钟。
3.2 实时调度中的典型问题分析
3.2.1 对下面的5个非周期性实时任务，按最早开始截止时间优先调度算法应如何进行CPU调度？
| 进程 | 到达时间 | 执行时间 | 开始截止时间 |
| A | 10 | 20 | 110 |
| B | 20 | 20 | 20 |
| C | 40 | 20 | 50 |
| D | 50 | 20 | 90 |
| E | 60 | 20 | 70 |
答：对上面5个非周期性实时任务，按最早开始截止时间优先调度算法进行CPU调度的结果如下图所示，可见，在采用非抢占调度方式时，系统没能保证B任务对截止时间的要求。
3.2.2 若有3个周期性任务，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为10ms；任务C要求每50ms执行一次，执行时间为15ms，应如何按最低松弛度优先算法对它们进行CPU调度？
答：对上面的3个周期性任务，利用最低松弛度优先算法进行调度的情况如下图所示。
3.3 死锁中的典型问题分析
3.3.1 在哲学家就餐问题中，如果将先拿起左边的筷子的哲学家称为左撇子，而将先拿起右边的筷子的哲学家称为右撇子，请说明在同时存在左撇子和右撇子的情况下，任何就座安排都不会产生死锁。
分析：这类题目的关键是必须证明产生死锁的四个必要条件的其中一个不可能成立。在本题中，互斥条件、请求与保持条件、不剥夺条件显然是成立的，因此必须证明“循环等待”条件不成立。
答：对本题，死锁产生的必要条件“循环等待”不可能成立。如果存在所有左边的哲学家等待右边的哲学家放下筷子的循环等待链。而且，系统中也不可能存在五个以下哲学家的循环等待链，因为，不相邻的哲学家之间不竞争资源。因此，不可能产生死锁。（PS：为了更加直观，阿婆主画了下面的图画便于大家理解，无标识，仅限于举例理解）
3.3.2
（1）3个进程共享4个同种类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？
（2）n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n。说明该系统不会因竞争该类资源而死锁。
（3）在（2）中，如果没有“每个进程都需要用该类资源”的限制，情况又会如何？
答：
（1）该系统不会因为竞争该类资源而死锁。因为，必有一个进程可获得2个资源，故能顺利完成，并释放出其所占用的2个资源给其他进程使用，使他们也顺利完成。
（2）用、
和
来分别表示第i个进程对该类资源的最大需求量、还需要量和已分配到的量，根据题意它们将满足下述条件：
（对所有i）
若系统已因竞争该类资源而进入死锁状态，则意味着已有一个以上的进程因申请不到该类资源而无限阻塞，而m个资源肯定已全部分配出去，即
因此：
即：
这样，至少必须存在一个进程，其，这显然与题意不符合，所以该系统不可能因竞争该类资源而进入死锁状态。
（3）此时系统可能发生死锁，如n=4,m=3时，若P1的Max为0，而其余三个进程的Max都为2，则仍然满足最大需求量之和（即6）小于m+n（即7）的要求，但当除P1以外的其余三个进程各得到1个资源时，这三个进程便可能进入死锁状态。
3.3.3 不安全状态是否必然导致系统进入死锁状态？
答：不安全状态不一定导致系统进入死锁状态。因为，安全性检查中使用的向量Max是进程执行前提供的，而在实际运行过程中，一进程需要的最大资源量可能小于Max，如：一进程对应的程序中有一段进行错误处理的代码，其中需要n个A种资源，若该进程在运行过程中没有碰到相应错误而不需调用该段错误处理代码，则它实际上将完全不会请求这n个A种资源。
3.3.4 在银行家算法中，若出现下面的资源分配情况：
| Process | Max | Need | Available |
| P0 | 0 0 4 4 | 0 0 1 2 | 1 6 2 2 |
| P1 | 2 7 5 0 | 1 7 5 0 | |
| P2 | 3 6 10 10 | 2 3 5 6 | |
| P3 | 0 9 8 4 | 0 6 5 2 | |
| P4 | 0 6 6 10 | 0 6 5 6 |
（1）计算分配矩阵的值，并判断该状态是否安全？
（2）若进程P2提出请求Request(1,2,2,2)，系统能否将资源分配给它？
（3）如果系统立即满足P2的上述请求，请问系统是否立即进入死锁状态？
答：
（1）Allocation = Max - Need，所以该时刻Allocation的值如下：
| Process | Allocation |
| P0 | 0 0 3 2 |
| P1 | 1 0 0 0 |
| P2 | 1 3 5 4 |
| P3 | 0 3 3 2 |
| P4 | 0 0 1 4 |
利用安全性算法对上面的状态进行分析（见下表），找到了一个安全序列{P0，P3，P4，P1，P2}，故系统是安全的。
（2）P2发出请求向量Request(1,2,2,2)后，系统按银行家算法进行检查：
a、
b、
c、系统先假定可为P2分配资源，并修改Available，和
向量：
Available = (0,4,0,0)
d、进行安全性检查：此时对所有的进程，条件都不成立，即Available不能满足任何进程的请求，故系统进入不安全状态。
因此，当进程P2提出请求Request(1,2,2,2)后系统不能将资源分配给它。
（3）系统立即满足进程P2的请求(1,2,2,2)后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，导致所有没执行完的多个进程因得不到资源而阻塞并形成循环等待链时，系统才进入死锁状态。
3.3.5 假定某计算机系统有R1设备3台，R2设备4台，它们被P1、P2、P3和P4这4个进程互斥共享，且已知这4个进程均以下面所示的顺序使用现有设备：
申请R1
申请R2
申请R1
释放R1
释放R2
释放R1
请问系统运行过程中是否可能产生死锁？如果有可能的话，请举出一种情况，并画出表示该死锁状态的进程--资源图。
答：系统运行过程种有可能产生死锁。根据题意，系统中只有R1设备3台，它要被4个进程共享，且每个进程对它的最大需求均为2，那么，当P1、P2、P3进程各得到1个R1设备时，它们可以继续运行，并均可以顺利地申请到一个R2设备，但当它们第2次申请R1设备时，因系统已无空闲的R1设备，它们将全部阻塞，并进入循环等待的死锁状态。此时的进程--资源图如下图所示：
3.3.6 死锁检测程序的运行频率较高或较低，各有什么优缺点？
答：死锁的检测可非常频繁地在每次资源请求时进行，其优点是：可以尽早地检测到死锁及其所涉及的进程，并有可能找到引起系统死锁的那个（或那几个）进程。其缺点是频繁的检测会耗费相当多的CPU时间，增加系统的开销。相反，每隔较长时间或当CPU利用率下降到较低程度时进行死锁的检测，则可以降低运行死锁检测程序的开销，但在检测到死锁时可能涉及到很多进程，也难以找到引起死锁的那个进程，从而难以从死锁状态恢复过来。
3.3.7 解除死锁，在选择撤销进程或被抢占资源的进程时，可考虑哪些因素？
答：解除死锁，在选择撤销进程或被抢占资源的进程时，可考虑下列因素：
（1）优先权；
（2）进程已执行的时间；
（3）估计的剩余执行时间；
（4）已产生的输出量；
（5）已获得的资源量和资源类型；
（6）还需要的资源量；
（7）进程的类型（批处理型或交互型）；
（8）需要被撤销的进程数等。
