当前位置：文档之家 › 操作系统复习考试第4章 调度与死锁 复习题

操作系统复习考试第4章 调度与死锁 复习题

  • 格式：ppt
  • 大小：353.00 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

操作系统原理第四章 处理机调度习题

操作系统原理第四章 处理机调度习题

第四章处理机调度4.3 习题4.3.1 选择最合适的答案1．某系统采用了银行家算法，则下列叙述正确的是（）。

A.系统处于不安全状态时一定会发生死锁B.系统处于不安全状态时可能会发生死锁C.系统处于安全状态时可能会发生死锁D.系统处于安全状态时一定会发生死锁2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。

A.Max[i,j]=Allocation[i,j]+Need[i,j]B.Need[i,j]= Allocation[i,j]+ Max[i,j]C.Max[i,j]= Available[i,j]+Need[i,j]D.Need[i,j]= Available[i,j]+ Max[i,j]3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。

A.非抢占式静态优先权法B.抢占式静态优先权法C.时间片轮转调度算法D.非抢占式动态优先权法4．在下列选项中，属于预防死锁的方法是（）。

A.剥夺资源法B.资源分配图简化法C.资源随意分配D.银行家算法5．在下列选项中，属于检测死锁的方法是（）。

A.银行家算法B.消进程法C.资源静态分配法D.资源分配图简化法6．在下列选项中，属于解除死锁的方法是（）。

A．剥夺资源法 B.资源分配图简化法C．银行家算法 D.资源静态分配法7．为了照顾紧迫型作业，应采用（）。

A.先来服务调度算法B.短作业优先调度算法C.时间片轮转调度算法D.优先权调度算法8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同。

A.先来先服务调度算法B.短作业优先调度算法C.时间片轮转调度算法D.长作业优先调度算法9．作业从后备作业到被调度程序选中的时间称为（）。

A.周转时间B.响应时间C.等待调度时间D.运行时间10．资源静态分配法可以预防死锁的发生，它们使死锁四个条件中的（）不成立。

(完整word版)操作系统第四章

(完整word版)操作系统第四章

第四章一、问答题1、什么叫临界资源？什么叫临界区？对临界区的使用应切合哪些规则？（同步体制应依据的准则是什么？）2、死锁产生的 4 个必需条件是什么？它们是相互独立的吗？3、何谓死锁？为何将全部资源按种类给予不一样的序号，并规定全部进度按资源序号递加的次序申请资源后，系统便不会产存亡锁？4、什么是安全状态？怎么判断系统能否处于安全状态？5、简述死锁定理和排除死锁的方法。

二、计算和证明1、目前系统中出现下述资源分派状况：Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2P1 1 0 0 0 1 7 5 0P2 1 3 5 4 2 3 5 6P3 0 3 3 2 0 6 5 2P4 0 0 1 4 0 6 5 6利用银专家算法，试问假如进度P2 提出资源恳求Request（1，2，2，2）后，系统可否将资源分派给它？2、若系统有某类资源m×n+1 个，同意进度履行过程中动向申请该类资源，但在该系统上运转的每一个进度对该资源的据有量任何时辰都不会超出m+1 个。

当进度申请资源时只需有资源还没有分派完则知足它的申请，但用限制系统中可同时履行的进度数来防备发存亡锁，你以为进度调动同意同时履行的最大进度数应该是多少？并说明原由。

3、n 个进度共享某种资源R，该资源共有 m个，每个进度一次一个地申请或开释资源。

假定每个进度对该资源的最大需求量均小于m，且各进度最大需求量之和小于 m＋n，试证明在这个系统中不行能发存亡锁。

4、目前某系统有同类资源7 个，进度 P，Q 所需资源总数分别为5， 4。

它们向系统申请资源的序次和数目如表所示。

回答：序次进度申请量1 Q 22 P 13 Q 14 P 35 P 26 Q 1问：采纳死锁防止的方法进行资源分派，请你写出系统达成第 3 次分派后各进度据有资源量，在此后各次的申请中，哪次的申请要求可先获取知足?5、一个计算机系统有 6 个磁带驱动器 4 个进度。

计算机操作系统第4章-调度与死锁精品PPT课件

计算机操作系统第4章-调度与死锁精品PPT课件

2021/1/31
11
4.1 调度的类型和模型
从不同的角度进行分类，常用分类方法是按调 度的层次，把调度分为高级、中级和低级调度； 另一种分类是按OS的类型分类，调度分为批处理 调度、分时调度和实时调度及多处理机调度。
4.1.1 调度类型
作业从进入系统并驻留在外存的后备队列上开 始，直至作业运行完毕，要经历下述三级调度。
一个作业的各个作业步之间是有联系的，上一个作 业步的输出是下一下作业步的输入。
2、作业控制块
创建一个进程时，要开辟一个进程控制块PCB，随时 记录进程的信息。把一个作业提交给系统时，也要开 辟一个作业控制块JCB，随时记录作业的信息。
2021/1/31
5
作业控制块的内容
用户名
作业名
作业类别
作业现行状态
(2)后备状态(收容状态)：系统收到其全部信 息，为其建立JCB，形成后备作业队列， 系统能感知到它的存在。
2021/1/31
8
(3)运行状态：由作业调度进入了进程调度 阶段。
(4)完成状态：作业运行结束后的一个状态， 是一个暂时性状态。
2021/1/31
9
Windows 2000/XP中的作业是共享一组配额限 度和安全性限制的进程集合；进程是内存资源 分配和打开文件个数的基本单位；线程是操作 系统调度处理器的执行单位。
作业调度发生在一个作业运行完毕，退出系 统时又要重新调入一个作业进入内存时，调度的 周期长，其调度算法花费较多的时间。
是指任何时间，不管进程处于用户 态还是核心态，都可以随时被更高优先 级的进程抢用CPU。
2021/1/31
19
(1)完全不可抢先或用户态不可抢先：当前进程不 论在用户态或核心态时，都不可以被抢用CPU， 这种操作系统称为不可抢先式的操作系统。如： windows 98和windows 95

第四章 调度与死锁

第四章 调度与死锁

25
4.2.5 高响应比优先调度算法


优先权的变化规律可描述为：优先权=(等待时间Twait+要求服务时 间Trun)/要求服务时间Trun 由于等待时间与服务时间之和，就是系统对该作业的响应时间， 故该优先权又相当于响应比RP。据此，又可表示为： RP=(Twait+Trun)/Trun=响应时间/Trun 由上述表达式可以看出：
4
1、高级调度（作业调度）

在每次执行作业调度时，都须做出以下 两个决定：


1)接纳多少个作业：取决于多道程序度 2)接纳哪些作业：取决于调度算法
5
2、低级调度（进程/短程调度）

决定就绪队列的哪个进程将获得处理机 1)非抢占方式(Non-preemptive Mode) 2)抢占方式(Preemptive Mode)
6
1)非抢占方式

在采用非抢占调度方式时，可能引起进程调度 的因素可归结为这样几个：



①正在执行的进程执行完毕， 或因发生某事件而不 能再继续执行； ②执行中的进程因提出I/O请求而暂停执行； ③ 进程通信或同步过程中执行了某种原语操作，如 P操作(wait操作)、Block原语、Wakeup原语等。
短作业(进程)优先调度算法SJ(P)F的基本思想：

短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估 计运行时间最短的作业，将它们调入内存运行。 而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时 间最短的进程，将处理机分配给它，使它立即执行并一直执行到完 成，或发生某事件而被阻塞放弃处理机时，再重新调度。

这种调度方式的优点是实现简单、系统开销小， 适用于大多数的批处理系统环境。但它难以满 足紧急任务的要求——立即执行，因而可能造 成难以预料的后果。显然，在要求比较严格的 实时系统中，不宜采用这种调度方式。 7

操作系统第4章 调度和死锁new

操作系统第4章 调度和死锁new

响应时间是从用户通过键盘提交一个请求开始，直至系统首次 产生响应为止的时间，或说直到在屛幕上显示出结果为止的一段时 间间隔。它包括：


从键盘输入的请求信息传送到处理机的时间； 处理机对请求信息进行处理的时间； 将所形成的响应回送到终端显示器的时间。 请求 键入请求 CPU处理请求 响应时间 响轮转调度算法
时间片轮转Round-Robin（RR）调度算法将系统中所有的 就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片 。时间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。调度程序据此暂停 当前进程的执行，将其送到就绪队列的末尾，等待分配下一时 间片再执行。 然后把处理机分配给就绪队列中新的队首进程，同时也让 它执行一个时间片。这样就可以保证就绪队列中的所有进程， 在一给定的时间内，均能获得一时间片处理机执行时间。 在RR算法中，时间片的大小对系统性能有很大的影响。
在分时系统中通常仅设置了进程调度。此时系统有一个 就绪队列，每个进程运行一个时间片，进程运行一个时间片后 如未完成，则被放在就绪队列末尾。如进程运行中因等待某事 件（例如申请I/O而等待I/O完成），则需排入阻塞队列，系统 因阻塞的原因不同可设几个阻塞队列。
时间片完 交互用户 事 件 出 现 就绪队列 进程调度 CPU
4.2.2
短作业（进程）优先调度算法
4.2.2
优点：

短作业（进程）优先调度算法
比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等 待时间； 提高系统的吞吐量；

缺点：

对长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响调度性能。

操作系统复习题加答案

操作系统复习题加答案

操作系统复习题加答案1. 什么是操作系统？请简述其主要功能。

操作系统是计算机系统中的一个系统软件，负责管理计算机硬件与软件资源，提供用户与计算机之间的交互界面，并控制其他程序的执行。

其主要功能包括进程管理、内存管理、文件管理、输入/输出设备管理和用户接口。

2. 进程和线程有什么区别？进程是操作系统进行资源分配和调度的一个独立单位，拥有独立的内存空间。

线程是进程中的一个实体，是CPU调度和执行的单位，比进程更小的能独立运行的基本单位，同一进程中的线程共享进程的资源。

3. 什么是死锁？请列举至少两种避免死锁的策略。

死锁是指两个或多个进程在执行过程中，因争夺资源而造成的一种僵局，若无外力作用，它们都将无法继续向前推进。

避免死锁的策略包括：资源分配图法和银行家算法。

4. 简述虚拟内存的概念及其作用。

虚拟内存是一种内存管理技术，它允许程序使用的内存超过物理内存的大小。

通过将部分内存内容存储在磁盘上，操作系统可以为程序提供比物理内存更大的地址空间，从而允许程序运行更大的程序或同时运行更多的程序。

5. 操作系统中的调度算法有哪些？请至少列举三种。

操作系统中的调度算法包括：先来先服务（FCFS）、短作业优先（SJF）和轮转调度（RR）。

6. 文件系统的作用是什么？请简述其基本组成部分。

文件系统的作用是管理存储设备上的数据存储、检索和更新。

其基本组成部分包括文件、目录结构、文件控制块和文件分配表。

7. 什么是分页和分段？它们之间有什么区别？分页是将物理内存划分为固定大小的页，而将逻辑地址空间划分为同样大小的页帧，通过页表实现逻辑地址到物理地址的映射。

分段则是将程序的地址空间划分为若干个段，每个段定义了一组逻辑信息。

分页注重于内存的物理和逻辑划分，而分段注重于程序的逻辑结构。

8. 什么是中断？中断处理过程包括哪些步骤？中断是指计算机在执行程序过程中，由于出现某些紧急事件需要处理而暂时中断当前程序的运行，转而去处理这些紧急事件的过程。

操作系统第四章习题

操作系统第四章习题 第四章习题 1．时间片轮转调度算法是为了（） A、多个终端能够得到系统的及时响应 B、是系统变得高效 C、优先级较高的进程得到及时响应 D、将需要CPU时间最少的进程最先做完 2．设4个作业从8：00开始，每小时到达一个（即8:00、9:00、10:00、11:00依次到达一个作业），每个作业的执行时间均为2小时，系统采用先来先服务和不抢占的调度策略，他们在一台处理器上按照单道运行，则10:00到达的那个作业的响应比为（），整个系统的平均周转时间为（）小时 A、2，1 B、2，3.5 C、3，2.5 D、3，5 3．针对以下的每种情况，选择调度算法。为了照顾紧急作业用户，应采用（）,为了能实现多终端人机交互，应采用（），为了能使短作业、长作业和交互用户都满意，应采用（） a、剥夺式优先级调度算法 b．时间片轮转调度算法 c．多级反馈队列调度算法 d．先到先服务调度算法 A、a，b，c B、d，b，c C、a,b,d D、a，d，c 4．进程调度算法采用固定时间片轮转调度算法，当时间片过大时，会使时间片轮转算法变为（）调度算法 A、高响应比优先 B、先来先服务 C、短进程优先 D、以上都不对 5．有5个批处理作业几乎同时到达，其预计运行时间分别为10、6、2、4、8，其优先级（由外部设定）分别为3、5、2、1、4，这里5为最高优先级。以下各种调度算法中，平均周转时间为14的是（）调度算法（同一时刻只有一个作业运行）。 A、时间片轮转（时间片大小为2） B、优先级调度 C、先来先服务（按照顺序10、6、2、4、8） D、短作业优先 6．作业在系统存在与否的唯一标志是（）。 A、源程序B·作业说明书C·作业控制块D·目的程序 7．下列作业调度算法中，最短的作业平均周转时间是（）。 A·先来先服务法B·短作业优先法 C·优先数法D·时间片轮转法 8．在操作系统中，作业处于（）时，已处于进程的管理之下。 A·后备B·阻塞C·执行D·完成 9．处于后备状态的作业存放在（）中。 A·外存B·内存C·A和B D·扩展内存 10．用户在一次计算过程中，或者一次事物处理中，要求计算机完成所做的工作的集合，这是指（）。 A·进程B·程序C·作业D·系统调用 11．作业调度又称为[1]，它决定将那些在外存储器上的处于[2]状态的作业调入主机内存。系统经作业调度程序选中一个或多个作业后，就为它们分配必要的内存、设备及软资源。然后控制权就交给了[3]，由[3]将它们变为一个或一组[4]，并[5]。 供选择的答案： [1] A·高级调度B·低级调度C·中级调度D·进程调度 [2] A·就绪B·阻塞C·提交D·后备 [3] A·存储管理B·处理机管理C·文件管理模块D·设备管理模块 [4] A·指令B·子程序C·进程D·程序段 [5] A·把它们挂到就绪队列上B·为它们分配处理机 C·把它们挂到后备队列上D·为它们分配设备 12·作业从进入系统到最后完成，可能要经历三级调度：———、———和———。13·作业的状态分为四种：———、———、———和完成。 14·进程调度完成进程状态从———态到———态的转化。 15·利用优先级调度算法进行进程调度时，即从就绪队列中选择优先级高的进程，有两种不同的处理方式：———和———。 16·设有三个批作业JOB1、JOB2、JOB3，其到达时间、处理时间及完成时间如下：

第4章 操作系统调度与死锁

Chapter Four 调度与死锁
一. 调度类型与准则
1. 什么是调度？
操作系统创建、销毁进程的动作 操作系统调度 CPU分时运行各进程中的指令的动作 操作系统阻塞、挂起进程的动作
2. 调度的类型
长程调度：创建或销毁进程。（作业调度） 中程调度：挂起和调入进程。（进程调度） 短程调度：调度进程，交给 CPU运行。（进程调度）
进程12 进程27
3. 时间片轮转Round Robin （可剥夺方式 preemptive Mode)
多个任务被创建为进程后，分时运行各个进程。 （一个进程运行指定的时间，操作系统暂停其运行，调度 CPU运行下一
个进程）
4. 优先权Priority调度算法 （可剥夺方式 preemptive Mode)
内存：（4G）
Operating System
PCB1 PCB2
PCB3 PCBn
进程12 进程27 进程15 进程6 进程32 进程27 进程 n
一. 调度类型与准则
内存：（4G）
Operating System
PCB1
3. 调度的性能准则（p105）
PCB2 PCB3
1）响应时间 Tresponse：用户提交一个任务请求，到用户感受到了机器系
PCB1 PCB2
PCB3 PCBn
占用 临界资源 1 占用 临界资源 2
占用 临界资源 3
（阻塞） 进程12 进程27 进程15 进程6 进程32 进程27 进程 n
三. 死锁问题
1. 什么是死锁问题
多个进程各自占有部分资源，无法得到所需 的全部资源，以完成任务并释放资源，形成 了资源争用互锁状态。
二. 调度算法
内存：（4G）

操作系统第四章

操作系统第四章第四章⼀、问答题1、什么叫临界资源？什么叫临界区？对临界区的使⽤应符合哪些规则？（同步机制应遵循的准则是什么？）2、死锁产⽣的4个必要条件是什么？它们是彼此独⽴的吗？3、何谓死锁？为什么将所有资源按类型赋予不同的序号，并规定所有进程按资源序号递增的顺序申请资源后，系统便不会产⽣死锁？

4、什么是安全状态？怎么判断系统是否处于安全状态？5、简述死锁定理和解除死锁的⽅法。⼆、计算和证明1、当前系统中出现下述资源分配情况：

利⽤银⾏家算法，试问如果进程P2提出资源请求Request（1，2，2，2）后，系统能否将资源分配给它？2、若系统有某类资源m×n+1个，允许进程执⾏过程中动态申请该类资源，但在该系统上运⾏的每⼀个进程对该资源的占有量任何时刻都不会超过m+1个。当进程申请资源时只要有资源尚未分配完则满⾜它的申请，但⽤限制系统中可同时执⾏的进程数来防⽌发⽣死锁，你认为进程调度允许同时执⾏的最⼤进程数应该是多少？并说明原因。

3、n个进程共享某种资源R，该资源共有m个，每个进程⼀次⼀个地申请或释放资源。假设每个进程对该资源的最⼤需求量均⼩于m，且各进程最⼤需求量之和⼩于m＋n，试证明在这个系统中不可能发⽣死锁。

4、当前某系统有同类资源7个，进程P，Q所需资源总数分别为5，4。它们向系统申请资源的次序和数量如表所⽰。回答：

问：采⽤死锁避免的⽅法进⾏资源分配，请你写出系统完成第3次分配后各进程占有资源量，在以后各次的申请中，哪次的申请要求可先得到满⾜?

5、⼀个计算机系统有6个磁带驱动器4个进程。每个进程最多需要n个磁带驱动器。问当n为什么值时，系统不会发⽣死锁？并说明理由

6、n个进程共享某种资源R，该资源共有m个可分配单位，每个进程⼀次⼀个地申请或释放资源单位。假设每个进程对该资源的最⼤需求量均⼩于m，问各进程最⼤需求量之和⾄少⼩于多少，系统不会发⽣死锁，并证明。

7. 考虑某⼀系统，它有4类资源R1，R2，R3，R4，有5个并发进程P0，P1，P2，P3，P4。请按照银⾏家算法回答下列问题；

精选第4章调度与死锁资料


● 进程调度中使用优先权调度算法时又可把算法 分成两种方式：可剥夺方式和不可剥夺方式
可剥夺方式：系统吧处理机分配给优先权最
高的进程，使之运行。一旦系统中出现另一
个优先级更高的进程，调度程序将停止正在
运行的进程，把处理机分配给新出现的优先
权更高的进程。
24
优先权调度算法
● 进程调度中使用优先权调度算法时又可把算法 分成两种方式：可剥夺方式和不可剥夺方式
31
● 4.3 死锁的基本概念
● 死锁是发生 在一组相互合作或竞争的线程或进程 中的一个问题。在同步问题中很容易死锁。
● 通常情况下，死锁发生在两个或多个不同程序对 应的进程或线程同时执行时，相同程序对应的多 个进程或线程由于一些复杂资源的使用也会发生 死锁。
32
● 4.3 死锁的基本概念
一组竞争系统资源或相互通信的进程相互的“永久” 阻塞。若无外力作用，这组进程将永远不能继续执行。
27
优先权调度算法 ●优先权确定的方式
动态优先权
当一个进程占有处理机的时间不断增长 是，其优先权会以某种速率降低。目的 是使持续执行的进程在运行一段时间后 将处理机让给其他进程，以防止一个进 程长期垄断占有处理机。
28
多级反馈队列调度算法
●算法思想 ●根据作业的性质和类型不同，将就绪队列再分为 若干个子队列，每个进程分属于一个队列。 ●在多级队列的基础上，不但设多个队列，且为每 个队列赋予不同的优先权，第一个队列的优先 权最高，第二个队列次之，其余队列的优先权 逐个降低。 ●各个队列中的进程执行时间片大小逐渐增大。 ●新进程投入第一个队列。 ●调度从第一个队列进行，仅当第一个队列为空时， 才调度第二个队列中的进程。
第4章 调度与死锁
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
A. 银行家算法 C. 死锁检测法 答：B B. 资源有序分配法 D. 资源分配图化简法
11、某系统有3个并发进程，都需要同 类资源4个，试问该系统不会发生死锁的 最少资源数是多少？ 答：最少要10个。 由于各进程最大需求量之和要小于“进 程数+资源数” 3+x>12 X>9 所以最少要10个资源。
18（续）
A ll oc at i on 0 01 2 1 42 0 1 35 4 0 63 2 0 01 4 M ax 0 01 2 1 75 0 2 35 6 0 65 2 0 65 6 N ee d 0 00 0 0 33 0 1 00 2 0 02 0 0 64 2 A va il ab l e 1 10 0
16、
在一个实际的计算机系统中，资源可以更新和增减，进 程可以创建和撤销。如果系统用banker算法处理死锁，那么， 在什么情况下，下列改变可以安全地进行而不会引起死锁发 生? (1)增加Available(增添新资源)； (2)减少Available(资源永久性地从系统中删除)： (3)增大Max(对一进程而言，它可能希望更多的资源)； (4)减少Max(一进程决定不需要那么多资源)； (5)增加进程数； (6)减少进程数。
解：在本题中，当两个进程都执行完第一步后，即进 程P1和P2都申请到一个R1资源以后，系统进入不安 全状态。随着两个进程的向前推进，无论哪个进程 执行完第2步，系统都将进入死锁状态。可能到达的 死锁点是：进程P1占有一个单位的R1类资源及一个 单位的R2类资源，P2占有一个单位的R1类资源，此 时系统已经没有空闲资源，而两个进程都在保持已 占有的资源不释放的情况下继续申请资源，从而造 成死锁。或者是进程P2占有一个单位的R1类资源及 一个单位的R2类资源，P1占有一个单位的R1类资源， 此时系统已经没有空闲资源，而两个进程都在保持 已占有的资源不释放的情况下继续申请资源，从而 造成死锁。 假定进程P1成功执行了第二步，则死锁点的资源 分配图如下所示：
如果这个系统中发生了死锁，那么一方面m个资源应该 全部分配出去，即
15（续）
alloc(1)+ alloc(2)+..+ alloc(n) = m
另一方面所有进程将陷入无限等待状态。上述两式得知
need(1)+need(2)+...+need(n)< n
上式表示死锁发生后，n个进程还需要的资源量之和小 于n，这意味着此刻至少存在一个进程， need(i)=0， 即它已经获得全部的资源。既然进程已经获得了它所 需要的全部资源，那么它就能执行完成并释放占有的 全部资源，这与前面的假设矛盾，所以系统不会出现 死锁。
7、处理死锁有哪几种基本方法？
答：用于处理死锁的方法主要有： 1．预防死锁：静态方法。在进程执行前采取的措施，
通过设置某些限制条件，去破坏产生死锁的四个必要条件 之一，防止发生死锁。
2．避免死锁：动态的方法：事先不采取任何限制措施
来破坏产生死锁的必要条件，而是在进程执行过程中采取 的措施，在进程申请资源时用某种方法去防止系统进入不 安全状态，从而避免发生死锁。 （如银行家算法）。
P1
R1
R2
P2
死锁点资源分配图
21、生产者-消费者问题中，如果对调生产者进程中的两个
P操作和两个V操作，则可能发生什么情况？
解：生产者-消费者的同步问题中，如果对调生产者进程中的两个P操作 和两个V操作，那么生产者和消费者的进程分别描述如下：
producer() consumer() { while(生产未完成) { while(还要继续消费) { { 生产一个产品； P(mutex); P(full); p(empty); p(mutex); 送一个产品到有界缓冲区； 从有界缓冲区中取产品； V(full); V(mutex); V(mutex); V(empty); } } } }



由于V操作是释放资源，所以对调V操作的次序无关紧要。而对 调P操作的次序可能导致死锁。 因为对调P操作的次序后，有可能出现这样一种特殊情况：在 某一时刻缓冲区中已经装满了产品，且缓冲区中无进程工作 （这时信号量full=n,empty=0,mutex=1），若系统此时调度 生产者进程运行，生产者生产了一个产品，它执行P(mutex)并 顺利进入临界区（进入临界区后，mutex=0），随后它执行 P(empty)时因没有空缓冲单元而受阻等待，等待消费者进程进 入缓冲区取走产品后释放出缓冲单元；而消费者进程执行P(full) 后再执行P(mutex)的时候，因缓冲区被生产者进程占据而无法 进入。 这样，就形成生产者在占有临界资源的情况下，等待消费者进 程取走产品，而消费者进程又无法进入临界区取走产品的僵局， 此时两进程陷入死锁。
22
22、假设就绪队列中有10个进程，系统将时 间片设为200ms，CPU进行进程切换要花费 10ms，试问系统开销所占的比率约为多少？
答：因就绪队列中有10个进程，它们将以时间片轮转 的方式使用CPU，时间片长度为200ms。当一个时 间片用完时，调度进程将当前运行进程设置为就绪 状态并放入就绪队列尾，再从就绪队列队首选择进 程投入运行，这一过程（进程切换）要花费时间 10ms。因此系统开销所占比率为： 10/（200+10）=4.8%
15、
假设系统中有m个同类资源，并被n个进程所 共享，进程每次只申请或释放一个资源，如果 (1)每个进程至少需要一个资源，且最多不超过 m个资源，即对i=1，2，…，n，有0<Need<=m。 (2)所有最大需求量之和小于m+n。 证明该系统不会发生死锁。
证： 依题意 max(1)+max(2)+...+max(n)< m+n (由条件(2)知)
第四章 调度与死锁
复习思考题
1、分时操作系统中，进程调度 通常采用什么算法？
答：分时操作系统通常采用时间片轮转 法的调度算法。
2、一个作业从提交开始直到完成，
往往要经历哪几级调度？
答：要经历下述三级调度：高级调度、 低级调度、中级调度。
3、说出四种常用的调度算法
答：常用的调度算法有： （1）先来先服务调度算法 （2）（进程）优先级调度算法 （3）时间片轮转调度算法 （4）多级反馈队列调度算法
17、 考虑下图所示的交通死锁情况。
（1）说明图中导致死锁的四个必要条件成立。 （2）提出一个避免死锁的规则。
交通死锁图
17（续）
解 (1)此例中导致死锁的四个条件成立： ①互斥。每条道路只能被一辆车占用。 ②占用并等待．每辆车都占用了一段道路，并等待其 前方的道路被释放。 ③非抢占。资源不可抢占。单行线，汽车不能抢路超 车。 ④循环等待。每辆车都等待着前方的汽车把路让出来， 且形成了一个环路。 (2)在每个十字路口设置红绿灯，当南北方向的路通车 时，东西方向的路上汽车等待．反之亦然。
18、
考虑下表所示的系统瞬时状态，利用banker算法回答下面的问 题： (1)数组Need的内容是什么? (2)该系统处于安全态吗?若是，给出一安全序列。 (3)若进程P1的请求(0420)到达，该请求是否能立即满足?
P0 P1 P2 P3 P4 0012 1000 1354 0632 0014 0012 1750 2356 0652 0656 1520 进程 Allocation Max Available
14、
假设三个进程共享相同类型的四个资源，每个进 程一次只能申请或释放一个资源，每个进程至多 需要两个资源，证明该系统不会发生死锁。 证： 假定该系统死锁，那么就说明其中的每一进程已 占有一资源并正等待另一资源。由于该系统只有 三个进程且有四个资源，因此，必有一进程能获 得两个资源，不必等待。于是该进程不再申请资 源，而且当它执行完后将归还它占有的资时候都不会引起死锁发生： (2)仅当每一进程的Max请求数不超过可用资源的总数时， 系统才保持在安全态： (3)仅当每一进程的Max请求数不超过可用资源的总数时， 系统才保持在安全态；
(4)任何时候都不会引起死锁发生；
(5)任何时候都不会引起死锁发生： (6)任何时候都不会引起死锁发生。
答：同时具备下列四个必要条件时，就会产生死锁
1、互斥（ Mutual exclusion ）条件：一个资源一次只能 被一个进程所使用，即是排它性使用。 2、不剥夺（ No preemption ）条件：进程已经获得的资 源，在未使用完以前，不能被别的进程剥夺，只能在使用 完以后，由自己释放。 3、请求和保持（ Hold-and-wait ）条件：进程已经保持 了至少一个资源，但又提出了新的资源要求，而该资源又 已被其它进程占有，此时请求进程阻塞，但又对已经获得 的其它资源保持不放。 4、环路等待（ Circular wait ）条件：存在一种进程资源 的循环等待链，链中的每一个进程已经获得资源的同时被 链中的下一个进程所请求。
10.53 9.53
解： (1) FCFS (8+12-0.4+13-1.0)/3=10.53 (2) SJF (8+9-1.0+13-0.4)/3=9.53
20、
假定某计算机系统有R1和R2两类可再使用资源（其中 R1有两个单位，R2有一个单位），它们被进程P1和 P2共享，且已知两个进程均以下列顺序使用两类资源： →申请R1 →申请R2 →申请R1 →释放R1 →释放R2 →释 放R1 试求出系统运行过程中可能到达的死锁点，并划出死 锁点的资源分配图。
12、你如何理解资源分配图简化法中 “找出—个既不阻塞又非独立的进程 结点Pi ”这句话。
答：
—个既不阻塞又非独立的进程结点Pi ，也就是从进程 集合中找到一个有边与它相连，且资源申请数量小于系统 中已有空闲资源数量的进程Pi 。如下图： P1
R1
R2
P2