操作系统习题三
每次做题都触及到了我的知识盲区，所以谨以此来记录自己的不足。欢迎大家评论指正，谢谢。
知识点
死锁：在一个进程集合中，所有的进程都在等待只能由该进程集合中的其它进程才能引发的事件，这就是死锁。
理解：由于进程集合中的所有进程都在等待集合中的其它进程引发唤醒该进程的事件，所以所有进程都会阻塞而无法向前推进。就是我想要的在你那里，你想要的在我这，我在等你，你也在等我，结果就是都在等。
资源死锁的四大必须条件
<1>互斥条件:
每个资源要么已经分配给了一个进程，要么是可用的。即就是资源非共享
<2>占有和等待条件:
已经得到资源的进程还能继续请求新的资源
<3>不可抢占条件:
当一个资源分配给了一个进程后，其它需要该资源的进程不能强制性获得该资源，除非该资源的当前占有者显示地释放该资源
<4>环路等待：
死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，环路上的每个进程都在等待下一个进程所占有的资源
死锁预防
防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。
(1) 破坏互斥条件
如果允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。
(2) 破坏不剥夺条件
当一个已保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺了，或从而破坏了不可剥夺条件。
该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。
(3) 破坏请求和保持条件
釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，这样就可以保证系统不会发生死锁。
这种方式实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，当由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。
(4) 破坏循环等待条件
为了破坏循环等待条件，可釆用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请编号大于Ri的资源。
这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费；此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。
死锁避免
避免死锁同样是属于事先预防的策略，但并不是事先釆取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。
- 系统安全状态
避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，让进程等待。
所谓安全状态，是指系统能按某种进程推进顺序( P1, P2, …, Pn)，为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序地完成。此时称 P1, P2, …, Pn 为安全序列。如果系统无法找到一个安全序列，则称系统处于不安全状态。
下面是一个安全序列
并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可以避免进入死锁状态。
银行家算法
银行家算法是最著名的死锁避免算法。它提出的思想是：把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
死锁的检测：
前面绍的死锁预防和避免算法，都是在为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不釆取任何措施，则应该提供死锁检测和解除的手段。
死锁的解除：
一旦检测出死锁，就应立即釆取相应的措施，以解除死锁。死锁解除的主要方法有：
-
资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
-
撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
-
进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。
判断题
1-1如果系统在所有进程运行前，一次性地将其在整个运行过程中所需地全部资源分配给进程，即所谓"静态分配"，可以预防死锁发生。 （T）
预防死锁：资源静态分配法
解除死锁：剥夺资源法
1-2多个进程竞争比经常数目少的资源就可能产生死锁，而当资源数目大于进程数目时就一定不会发生死锁。 （F）
1-3在银行家算法中，对某时刻的资源分配情况进行安全分析，如果该时刻状态是安全的，则存在一个安全序列，且这个安全序列是唯一的。 （F）
1-4进程调度算法各种各样，如果选择不当，就会造成死锁。（T）
要注意概念的理解，进程调度算法使用不当会造成进程长时间等待，与死锁没有关系。造成死锁主要看产生死锁的四个必要条件。
1-5作业调度能使作业获得CPU。（F）
作业调度只能创建进程将其调入内存，进程调度才能获取CPU。
1-6短作业（进程）优先调度算法具有最短的平均周转时间。 （T)
此题有争议，之后再进行解释
我的理解：只有当所有进程同时到达时，才有最短的平均周转时间，我认为应该是错的。
SJF的特点：
(1) 优点：
1、比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
2、提高系统的吞吐量；
(2) 缺点：
1、对长作业非常不利，可能长时间得不到执行；
2、未能依据作业的紧迫程度来划分执行的优先级；
3、难以准确估计作业（进程）的执行时间，从而影响调度性能。
1-7在优先权调度算法中如何确定静态优先权？一般说，计算进程的优先权要高于磁盘I/O进程的优先权。 (T)
计算进程会占用大量的CPU时间，IO进程会占用较少的CPU时间，所以后者的优先权要高。
确定静态优先权的依据有如下三个方面：
①进程类型：通常，系统进程（如接收进程、对换进程、磁盘I/O进程）的优先权高于一般用户进程的优先权
②进程对资源的要求：如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予较高的优先权
③用户要求：这是用户进程的紧迫程度及用户所付费用的多少来确定优先权的
选择题
2-1、设有4个作业同时到达，每个作业的执行时间均为2h，它们在一台处理器上已单道 式运行，则平均周转时间为（5h）。
2-2、假设系统中所有的进程都是同时到达，则使进程平均等待时间最短的是（ ）调度算法。
A、优先级
B、时间片轮转
C、先来先服务
D、短作业优先
短进程优先调度算法具有最短的平均周转时间。平均周转时间=各进程周转时间之和/进程数。因为每个进程的执行时间都是固定的，所以变化的是等待时间，只有短进程优先算法能最小化等待时间。
2-3、下面关于选择进程调度算法的准则中不正确的是（ ）。
A、尽可能提高系统的吞吐量
B、适当增加进程在就绪队列的等待时间
C、尽快响应交互式用户的请求
D、尽量提高CPU利用率
在选择进程调度算法时应考虑以下几个准则：
①公平：确保每个进程获得合理的CPU份额；
②有效：使CPU尽可能地忙碌；
③响应时间：使交互用户的响应时间尽可能短；
④周转时间：使批处理用户等待输出的时间尽可能短；
⑤吞吐量：使单位时间处理的进程数尽可能最多；
2-4、在单处理器的多进程系统中，进程什么时候占用处理器以及决定占用时间的长短是由（）决定的。
A、进程相应的代码长度
B、进程总共需要运行的时间
C、进程特点和进程调度策略
D、进程完成什么功能
2-5、（）是指作业进入系统到作业完成所经过的时间间隔。
A、响应时间
B、周转时间
C、运行时间
D、等待时间
2-6、在多道程序的环境中，不会因竞争（）而产生死锁
A、可被抢占的资源
B、不可抢占的资源
C、消耗性资源
D、可重复使用的资源
2-7、降低进程优先级的最合理的时机是（）。
A、进程的时间片用完
B、进程刚完成I/O操作，进入就绪队列
C、进程长期处于就绪队列中
D、进程从就绪状态转为运行状态
进程的时间片用完，就被调到队尾，继续等待下一次，优先级降低了
2-8、在面向用户的调度准则中，（）是选择实时调度算法的重要准则。
A、响应时间快
B、平均周转时间短
C、截止时间的保证
D、优先权高的作业能获得优先服务
2-9、在面向用户的调度准则中，（）是选择分时系统中进程调度算法的重要准则。
A、响应时间快
B、平均周转时间短
C、截止时间的保证
D、优先权高的作业能获得优先服务
2-10、在面向用户的调度准则中，（）是批处理系统中选择作业调度算法的重要准则。
A、响应时间快
B、平均周转时间短
C、截止时间的保证
D、优先权高的作业能获得优先服务
2-11、在面向用户的调度准则中，（）准则是为了照顾紧急作业用户的要求而设置的。
A、响应时间快
B、平均周转时间短
C、截止时间的保证
D、优先权高的作业能获得优先服务
2-12、在单处理器的多进程系统中，进程什么时候占用处理器以及决定占用时间的长短是由（）决定的。
A、进程相应的代码长度
B、进程特点和进程调度策略
C、进程总共需要运行的时间
D、进程完成什么功能
2-13、（ ）有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业。
A、优先权调度算法
B、时间片轮转调度算法
C、短作业（进程）优先算法
D、先来先服务调度算法
先来先服务(FCFS)调度算法是一种最简单的调度算法，当在作业调度中采用该算法时，每次调度是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。
FCFS调度算法比较有利于长作业，而不利于短作业。所谓CPU繁忙型的作业，是指该类作业需要大量的CPU时间进行计算，而很少请求I/O操作。I/O繁忙型的作业是指CPU处理时，需频繁的请求I/O操作。所以CPU繁忙型作业更接近于长作业
2-14、时间片轮转调度算法是为了（）。
A、多个终端能够得到系统及时响应
B、需要CPU时间最少的进程最先做
C、使系统变得高效
D、优先级较高的进程得到及时响应
2-15、（）优先级是在创建进程时确定的，确定之后在整个运行期间不再改变。
A、先来先服务
B、静态
C、短作业
D、动态
2-16采用时间片轮转调度算法分配CPU时，当处于运行状态的进程用完一个时间片后，他的状态是（ ）状态。
A、消亡
B、就绪
C、运行
D、阻塞
2-17、下列调度算法中，（）调度算法是绝对可抢占的。
A、时间片轮转
B、短进程优先
C、先来先服务
D、优先级
2-18、下列选项中，降低进程优先级的合理时机是（）。
A、进程刚完成I/O操作，进入就绪队列
B、进程从就绪状态转为运行状态
C、进程时间片用完
D、进程长期处于就绪队列
2-19、系统产生死锁是指（）。
A、系统发生重大故障
B、若干进程正在等待永远不可能得到的资源
C、请求的资源数大于系统提供的资源数
D、若干进程等待被其他进程所占用而又不可能被释放的资源