CS408/Operate-System/1-process-management-ex.md

进程管理习题

进程与线程

进程

进程概念

例题 进程与程序的根本区别是()。

$A.$静态和动态特点

$B.$是不是被调入内存

$C.$是不是具有就绪、运行和等待三种状态

$D.$是不是占有处理器

解：$A$。动态性是进程最重要的特性，以此来区分文件形式的静态程序。操作系统引入进程的概念，是为了从变化的角度动态地分析和研究程序的执行。

例题 同一程序经过多次创建，运行在不同的数据集上，形成了()的进程。

$A.$不同

$B.$相同

$C.$同步

$D.$互斥

解：$A$。一个进程是程序在一个数据集上的一次运行过程。运行于不同的数据集，将会形成不同的进程。

进程结构

例题 若一个进程实体由$PCB$、共享正文段、数据堆段和数据栈段组成，请指出下列$C$语言程序中的内容及相关数据结构各位于哪一段中。

Ⅰ.全局赋值变量

Ⅱ.未赋值的局部变量

Ⅲ.函数调用实参传递值

Ⅳ.用malloc()要求动态分配的存储区

Ⅴ.常量值（如1995、"string"）

Ⅵ.进程的优先级

A.PCB

$B.$正文段

$C.$堆段

$D.$栈段

解：$B$、$D$、$D$、$C$、$B$、$A$。$C$语言编写的程序在使用内存时一般分为三个段，它们一般是正文段（即代码和赋值数据段）、数据堆段和数据栈段。二进制代码和常量存放在正文段，动态分配的存储区在数据堆段，临时使用的变量在数据栈段。由此，我们可以确定全局赋值变量在正文段赋值数据段，未赋值的局部变量和实参传递在栈段，动态内存分配在堆段，常量在正文段，进程的优先级与进程直接相关，放在$PCB$内。

进程状态

例题 下面的叙述中，正确的是()。

$A.$进程获得处理器运行是通过调度得到的

$B.$优先级是进程调度的重要依据，一旦确定不能改动

$C.$在单处理器系统中，任何时刻都只有一个进程处于运行态

$D.$进程申请处理器而得不到满足时，其状态变为阻塞态

解：$A$。选项$B$错在优先级分静态和动态两种，动态优先级是根据运行情况而随时调整的。选项$C$错在至多只存在一个运行态，系统发生死锁时有可能进程全部都处于阻塞态，或无进程任务，$CPU$空闲。选项$D$错在进程申请处理器得不到满足时就处于就绪态，等待处理器的调度。

进程优先级

例题 下列选项中，降低进程优先级的合理时机是()。

$A.$进程时间片用完

$B.$进程刚完成$I/O$操作，进入就绪队列

$C.$进程长期处于就绪队列

$D.$进程从就绪态转为运行态

解：$A$。$A$中进程时间片用完，可降低其优先级以让其他进程被调度进入执行状态避免不断占用处理机，使得其他进程产生饥饿。$B$中进程刚完成$I/O$，进入就绪队列等待被处理机调度，为了让其尽快处理$I/O$结果，因此应提高优先级。$C$中进程长期处于就绪队列，为不至于产生饥饿现象，也应适当提高优先级。$D$中进程的优先级不应该在此时降低，如果此时降低了可能会被抢占，导致进程反复切换，降低处理效率，而应在时间片用完后再降低。

父子进程

例题 下列关于父进程与子进程的叙述中，错误的是()。

$A.$父进程与子进程可以并发执行

$B.$父进程与子进程共享虚拟地址空间

$C.$父进程与子进程有不同的进程控制块

$D.$父进程与子进程不能同时使用同一临界资源

解：$B$。父进程与子进程当然可以并发执行，$A$正确。父进程可与子进程共享一部分资源，但不能共享虚拟地址空间，在创建子进程时，会为子进程分配资源，如虚拟地址空间等，$B$错误。临界资源一次只能为一个进程所用，$D$正确。进程控制块$PCB$是进程存在的唯一标志，每个进程都有自己的$PCB$，$C$正确。

进程通信

例题 下列关于管道（$Pipe$）通信的叙述中，正确的是()。

$A.$一个管道可实现双向数据传输

$B.$管道的容量仅受磁盘容量大小限制

$C.$进程对管道进行读操作和写操作都可能被阻塞

$D.$一个管道只能有一个读进程或一个写进程对其操作

解：$C$。管道类似于通信中半双工信道的进程通信机制，一个管道可以实现双向的数据传输，但是同一时刻只能最多有一个方向的传输，不能两个方向同时进行，所以必须使用两个管道才能实现双向数据传输（特指同时），$A$错误。管道的容量大小通常为内存上的一页，它的大小并不受磁盘容量大小的限制，$B$错误。当管道满时，进程在写管道会被阻塞，而当管道空时，进程在读管道会被阻塞，因此选$C$。一个管道可以被多个读进程或写进程操作，但是同一时间只能有一个读进程或一个写进程对其操作，$D$没有限制是同时所以错误。

线程

线程概念

例题 系统动态$DLL$库中的系统线程，被不同的进程所调用，它们是()的线程。

$A.$不同

$B.$相同

$C.$可能不同，也可能相同

$D.$不能被调用

解：$B$。进程是暂时的，程序是永久的；进程是动态的，程序是静态的；进程至少由代码、数据和$PCB$组成，程序仅需代码和数据即可；程序代码经过多次创建可对应不同的进程，而同一个系统的进程（或线程）可以由系统调用的方法被不同的进程（或线程）多次使用。

线程实现

例题 下面关于用户级线程和内核级线程的描述中，错误的是()。

$A.$采用轮转调度算法，进程中设置内核级线程和用户级线程的效果完全不同

$B.$跨进程的用户级线程调度也不需要内核参与，控制简单

$C.$用户级线程可以在任何操作系统中运行

$D.$若系统中只有用户级线程，则处理机的调度对象是进程

解：$B$。对于$A$，如果是同一个进程中的线程进行切换，用户级线程不需要内核参与，而相反内核级线程则需要，所以使用轮转调度算法进行切换时实现方式是完全不同的。对于$B$，只有相同进程的用户级线程切换可以直接在用户态完成，如果要跨进程用户级线程就需要进行进程调度，从而需要内核参与。对于$C$，用户级线程的维护由应用进程完成，不需要操作系统内核了解用户级线程的存在，因此可在任何操作系统中运行。对于$D$，如果系统只有用户态线程，则线程对操作系统是不可见的，操作系统只能调度进程；如果系统中有内核态线程，则操作系统可以按线程进行调度。

多线程系统

例题 在以下描述中，()并不是多线程系统的特长。

$A.$利用线程并行地执行矩阵乘法运算

$B.Web$服务器利用线程响应$HTTP$请求

$C.$键盘驱动程序为每个正在运行的应用配备一个线程，用以响应该应用的键盘输入

$D.$基于$GUI$的调试程序用不同的线程分别处理用户输入、计算和跟踪等操作

解：$C$。对于题目所提的不算多线程系统的特长，即找出下面情形可以用一个线程就可以完成的情况。多线程适用于复杂并发的操作，而整个系统只有一个键盘，而且键盘输入是人的操作，速度比较慢，完全可以使用一个线程来处理整个系统的键盘输入。

处理机调度

调度算法

先来先服务

例题 各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

解：

根据先来先服务的思想，根据到达的顺序，得到调度顺序为：$P1$、$P2$、$P3$、$P4$。

所以$P1$在$0$到达，$0+7=7$完成。$P2$在$2$到达，而$7$时$P1$完成。所以$P2$要等待$7-2=5$，所以$P2$从$7$开始，在$7+4=11$完成。$P3$在$4$到达，所以需要等待$11-4=7$，从$11$开始，在$11+1=12$结束。$P4$在$5$到达，需要等待$12-5-7$，从$12$开始，在$12+4=16$结束。

进程	到达时间	运行时间	等待时间	开始时间	完成时间
P1	0	7	0	0	7
P2	2	4	5	7	11
P3	4	1	7	11	12
P4	5	4	7	12	16

因为周转时间=完成时间-到达时间。所以$P1=7-0=7$，$P2=11-2=9$，$P3=12-4=8$，$P4=16-5=11$。

带权周转时间=周转时间÷运行时间。所以$P1=7\div7=1$，$P2=9\div4=2.25$，$P3=8\div1=8$，$P4=11\div4=2.75$。

等待时间=周转时间-运行时间。根据表格可得。

所以平均周转时间$=(7+9+8+11)\div4=8.75$。平均带权周转时间$=(1+2.25+8+2.75)\div4=3.5$。平均等待时间$=(0+5+7+7)\div4=4.75$。

短作业优先

例题 各进程到达就绪队列的时间、需要的运行时间如下表所示。使用非抢占式短进程优先调度算法和抢占式短进程优先调度算法，分别计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

解：

如果使用非抢占式的，因为每次选择当前已经到达且运行时间最短的作业/进程，因为$P1$第一个到达，所以第一个开始，$P1$完成时是$7$，$P2$、$P3$、$P4$都到达了，所以依次选最短运行时间的开始。$7$时$P3$开始，$7+1=8$时结束，$P2$开始（用了$FCFS$思想），$8+4=12$时结束，$P4$开始，$12+4=16$结束。所以调度顺序为$P1$、$P3$、$P2$、$P4$。

所以$P1$、$P3$、$P2$、$P4$周转时间为$7-0=7$、$8-4=4$、$12-2=10$、$16-5=11$。带权周转时间为$7\div7=1$、$4\div1=4$、$10\div4=2.5$、$11\div4=2.75$。等待时间为$0-0=0$、$7-4=3$、$8-2=6$、$12-5=7$。平均周转时间为$(4+7+10+11)\div4=32\div4=8$。平均带权周转时间为$(1+4+2.5+2.75)\div4=10.25\div4=2.5625$。平均等待时间为$(0+3+6+7)\div4=16\div4=4$。

如果使用抢占式的，若新到达进程剩余时间要比当前运行的进程剩余时间更短，则由新进程抢占处理机。

$0$时$P1$到达，$P1$剩余时间为$7$，所以$P1$开始运行。$2$时$P2$到达，此时$P1$剩余时间为$7-2=5$，而$P2$剩余时间为$4-0=4$，$4<5$，所以$P2$抢占$P1$处理机。$4$时$P3$到达，此时$P2$剩余时间为$4-2=2$，而$P3$剩余时间为$1-0=1$，所以$P3$又抢占$P2$处理机。到$5$时$P4$到达，此时$P3$正好运行完，所以要考虑$P1$、$P2$、$P4$三个的剩余时间，分别为$5$、$2$、$4$，所以$P2$抢占处理机运行。$5+2=7$时$P2$运行完，$P4$剩余时间更少抢占处理机。$7+4=11$时$P4$运行完，$P1$抢占处理机。最后$11+5=16$时$P1$运行完，作业全部结束。

所以$P1$、$P2$、$P3$、$P4$周转时间为$16-0=16$、$7-2=5$、$5-4=1$、$11-5=6$。带权周转时间为$16\div7=2.28$、$5\div4=1.25$、$1\div1=1$、$6\div4=1.5$。等待时间分别为$0-0+11-2=9$、$2-2+5-4=1$、$4-4=0$、$7-5=2$。平均周转时间为$(16+5+1+6)\div4=28\div4=7$。平均带权周转时间为$(2.28+1.25+1+1.5)\div4=1.5$。平均等待时间为$(9+1+0+2)\div4=12\div4=3$。

高响应比优先

例题 各进程到达就绪队列的时间、需要的运行时间如下表所示。使用高响应比优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

解：

需要利用公式计算响应比，最重要的是等待时间和运行时间。当$0$时$P1$到达，$P1$运行。$7$时$P1$完成，此时$P2$、$P3$、$P4$全部到达了，而响应比分别为$(7-2+4)\div4=9\div4=2.25$、$(7-4+1)\div1=4\div1=4$、$(7-5+4)\div4=6\div4=1.5$，所以选择$P3$上处理机运行。$7+1=8$时，$P3$完成，此时响应比分别为$P2:(8-2+4)\div4=10\div4=2.5$、$P4:(8-5+4)\div4=7\div4=1.75$，$P2$运行。$8+4=12$时$P2$完成，$P4$运行，最后$12+4=16$时全部完成。

所以$P1$、$P2$、$P3$、$P4$等待时间为$0-0=0$、$8-2=6$、$7-4=3$、$12-5=7$，平均等待时间为$(0+6+3+7)\div4=16\div4=4$。周转时间为$7-0=7$、$12-2=10$、$8-4=4$、$16-5=11$，平均周转时间为$(7+10+4+11)\div4=32\div4=8$。带权周转时间为$7\div7=1$、$10\div4=2.5$、$4\div1=4$、$11\div4=2.75$，平均带权周转时间为$(1+2.5+4+2.75)\div4=2.5625$。

时间片轮转

例题 各进程到达就绪队列的时间、需要的运行时间如下表所示。使用时间片轮转调度算法，分析时间片大小为$2$时的进程运行状态。

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

注意：当同一时刻既有时间片用完也有新进程到达时，默认新到达进程先进入队列，时间片用完的进程后进入。

解：

若时间片为$2$：

当$0$时，因为只有$P1$到达就绪队列，所以$P1$运行一个时间片。

当$2$时，$P1$时间片运行完，余下$7-2=5$个时间。正好$P2$到达就绪队列，所以$P1$处理机被剥夺，重新放到就绪队列尾，让$P2$运行一个时间片。

当$4$时，$P2$时间片运行完，余下$4-2=2$个时间。正好$P3$到达就绪队列加入队尾，此时$P1$到达队头，所以$P2$处理机被剥夺，重新放到就绪队列尾，让$P1$运行一个时间片。

当$5$时，$P4$到达加入就绪队列。此时就绪队列上有$P3$、$P2$、$P4$。

当$6$时，$P1$时间片运行完，余下$5-2=3$个时间。此时$P3$到达队头，所以$P1$处理机被剥夺，重新放到就绪队尾，让$P3$运行。此时就绪队列上有$P2$、$P4$、$P1$。

当$7$时，虽然$P3$时间片没有用完，但是由于$P3$只需一个单位的时间，所以主动放弃处理机，发生调度，让$P2$运行一个时间片。

当$9$时，$P2$正好运行完也用完时间片，$P4$上处理机。此时就绪队列上有$P1$。

当$11$时，$P4$时间片用完，余下$4-2=2$个时间，此时$P1$到达队头，所以$P4$处理机被剥夺，重新放到就绪队尾，让$P1$运行。

当$13$时，$P1$时间片用完，余下$3-2=1$个时间，此时$P4$到达队头，所以$P1$处理机被剥夺，重新放到就绪队尾，让$P4$运行。

当$15$时，$P4$正好运行完也用完时间片，$P1$上处理机。

当$16$时，$P1$运行完，主动放弃处理机。

优先级

例题 某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为$1\mu s$。在$T$时刻就绪队列中有$3$个进程$P_1$、$P_2$和$P_3$，其在就绪队列中的等待时间、需要的$CPU$时间和优先权如下表所示。

进程	等待时间	需要CPU时间	优先权
P1	30	12	10
P2	15	24	30
P3	18	36	20

若优先权值大的进程优先获得$CPU$，从$T$时进刻起系统开始进程调度，则系统的平均周转时间为()。

A.72\mu s

B.73\mu s

C.74\mu s

D.75\mu s

解：$D$。执行顺序：$P_2\rightarrow P_3\rightarrow P_1$，基本上计算没什么问题，但是要注意添加上调度时间要依次加一二三次，$P_2=1+15+24=40$、$P_3=18+1+24+1+36=80$、$P_1=30+1+24+1+36+1+12=105$，所以平均$75$。

例题 各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用非抢占式与抢占式优先级调度算法，分析进程运行状态。（优先数越大，优先级越高）

进程	到达时间	运行时间	优先数
P1	0	7	1
P2	2	4	2
P3	4	1	3
P4	5	4	2

解：

非抢占式：$0$时只有$P1$到达，所以$P1$开始处理。$2$时$P2$到达，$4$时$P3$到达，$5$时$P4$到达。$7$时$P1$运行完，因为$P3$优先级更高，所以运行$P3$。$8$时$P3$运行完，$P2$、$P4$优先级相同，但是由于$P2$先到，所以$P2$上处理机。$12$时$P2$运行完，$P4$上处理机。$16$时$P4$运行完。

抢占式：$0$时$P1$到达，$P1$上处理机。$2$时$P2$到达，且$P2$优先级$2$大于$P1$优先级$1$，所以$P2$上处理机，$P1$余下$7-2=5$。$4$时$P3$到达，且$P3$优先级$3$大于$P2$优先级$2$，所以$P3$上处理机，$P2$余下$4-2=2$。$4+1=5$时$P3$运行结束，且$P4$到达，插入就绪队列队尾，$P4$与$P2$优先数都是$2$，而$P2$进入队列时间更早，所以$P2$上处理机。$5+2=7$时$P2$运行结束，且$P4$优先级$4$大于$P1$优先级$1$，所以$P4$上处理机。$7+4=11$时$P4$运行结束，$P1$上处理机。$11+5=16$时$P1$运行结束。

多级反馈队列

例题 各进程到达就绪队列的时间、需要的运行时间如下表所示。使用多级反馈队列调度算法，就绪队列使用时间片轮转调度算法，分析进程运行状态。

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

解：

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。

新进程到达时先进入第$1$级队列，按$FCFS$原则排队等待被分配时间片。

若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。

只有第$k$级队列为空时，才会为$k+1$级队头的进程分配时间片。

被抢占处理机的进程重新放回原队列队尾。

定义多级就绪队列如下（优先级与优先数成正比）：

队列序号	优先级	时间片大小
1	3	1
2	2	2
3	1	4

$0$时首先$P1$进入第一级队列，此时$P1$优先级为$3$，时间片为$1$，所以$P1$会运行$1$个时间片。

$1$时$P1$余下$6$，没有运行完，进入第二级队列的队尾继续运行一个时间片。

$2$时$P2$进入第一级队列，优先级更高，所以$P1$被剥夺处理机，此时$P1$还余下$5$，回退第二级队列，$P2$开始运行。

$3$时$P2$运行一个时间片后余下$3$，加入第二级队列队尾。此时第二级队列头部为$P1$，所以$P1$开始运行。

$4$时$P3$进入第一级队列，优先级更高，所以$P1$被剥夺处理机，此时$P1$还余下$4$，回退第二级队列，有$P2$、$P1$。

$5$时$P4$进入第一级队列，此时$P3$也正好运行完，处理机交给$P4$。

$6$时$P4$运行一个时间片后余下$3$，加入到第二级队列尾部。第二级队列此时顺序为$P2$（余$3$）、$P1$（余$4$）、$P4$（余$3$），所以$P2$开始运行。

$8$时$P2$运行一个时间片后余下$1$，加入到第三级队列中。$P1$开始占有处理机。

$10$时$P1$运行一个时间后余下$2$，加入到第三级队列中。$P4$开始占有处理机。

$12$时$P4$运行一个时间后余下$1$，加入到第三级队列中。第二级队列为空，开始运行第三级队列，$P2$开始占有处理机。

$13$时$P2$处理完，$P1$占有处理机。

$15$时$P1$处理完，$P4$占有处理机。

$16$时$P4$处理完，全部结束。

例题 系统采用二级反馈队列调度算法进行进程调度。就绪队列$Q_1$采用时间片轮转调度算法，时间片为$10ms$；就绪队列$Q_2$采用短进程优先调度算法；系统优先调度$Q_1$队列中的进程，当$Q_1$为空时系统才会调度$Q_2$中的进程；新创建的进程首先进入$Q_1$；$Q_1$中的进程执行一个时间片后，若未结束，则转入$Q_2$。若当前$Q_1$，$Q_2$为空，系统依次创建进程$P_1$，$P_2$后即开始进程调度，$P_1$，$P_2$需要的$CPU$时间分别为$30ms$和20ms,则进程$P_1$，$P_2$在系统中的平均等待时间为()。

A.25ms

B.20ms

C.15ms

D.10ms

解：$C$。$0ms$时刻$P1$开始运行。$10ms$时刻$P1$停止，余下$20ms$进入$Q2$，$P2$进入$Q1$运行。$20ms$时刻$P2$停止，余下$10ms$，进入$Q2$，而$Q1$空，开始运行$Q2$中的进程，而$P2$余下$10ms$小于$P1$余下的$20ms$，短进程优先，所以$P2$继续开始运行。$30ms$时刻$P2$完成，$P1$运行。$50ms$时刻$P1$运行完成。

所以综上$P1$等待$30-10=20ms$，而$P2$等待$10-0=10ms$。平均等待时间为$(20+10)\div2=15ms$。

多道批处理系统

一般都是单道处理系统，所以作业调度和进程调度都是一样的。而对于多道批处理系统会采用不同的作业调度和进程调度算法。但是基本上运算方法一致。

作业调度是调度作业进内存，有多少道就有多少个内存作业位置，但是有位置不一定能运行，因为需要进行进程调度占用处理机（$CPU$）。

例题 有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用抢占式优先级调度算法。作业的运行情况见下表，其中作业的优先数即进程的优先数，优先数越小，优先级越高。

作业名	到达时间	运行时间	优先数
1	8:00	40分钟	5
2	8:20	30分钟	3
3	8:30	50分钟	4
4	8:50	20分钟	6

1）列出所有作业进入内存的时间及结束的时间（以分为单位)。

2）计算平均周转时间。

解：

1）具有两道作业的批处理系统，内存只存放两道作业，它们采用抢占式优先级调度算法竞争$CPU$，而将作业调入内存采用的是短作业优先调度。$8:00$，作业$1$到来，此时内存和处理机空闲，作业$1$进入内存并占用处理机；$8:20$，作业$2$到来，内存仍有一个位置空闲，因此将作业$2$调入内存，又由于作业$2$的优先数高，相应的进程抢占处理机，在此期间$8:30$作业$3$到来，但内存此时已无空闲，因此等待。直至$8:50$，作业$2$执行完毕，此时作业$3$、$4$竞争空出的一道内存空间，作业$4$的运行时间短，因此先调入，但它的优先数低于作业$1$，因此作业$1$先执行。到$9:10$时，作业$1$执行完毕，再将作业$3$调入内存，且由于作业$3$的优先数高而占用$CPU$，作业$3$完成后$4$开始占用$CPU$处理。所有作业进入内存的时间及结束的时间见下表。

作业	到达时间	运行时间	优先数	进入内存时间	结束时间	周转时间
1	8:00	40min	5	8:00	9:10	70min
2	8:20	30min	3	8:20	8:50	30min
3	8:30	50min	4	9:10	10:00	90min
4	8:50	20min	6	8:50	10:20	90min

2）平均周转时间$为(70+30+90+90)\div4=70min$。

进程同步与互斥

进程同步与互斥的基本概念

进程关系

例题 进程$A$和进程$B$通过共享缓冲区协作完成数据处理，进程$A$负责产生数据并放入缓冲区，进程$B$从缓冲区读数据并输出。进程$A$和进程$B$之间的制约关系是()。

$A.$互斥关系

$B.$同步关系

$C.$互斥和同步关系

$D.$无制约关系

解：$C$。并发进程因为共享资源而产生相互之间的制约关系，可以分为两类：①互斥关系，指进程之间因相互竞争使用独占型资源（互斥资源）所产生的制约关系；②同步关系，指进程之间为协同工作需要交换信息、相互等待而产生的制约关系。本题中两个进程之间的制约关系是同步关系，进程$B$必须在进程$A$将数据放入缓冲区后才能从缓冲区中读出数据。此外，共享的缓冲区一定是互斥访问的，所以它们也具有互斥关系。

临界资源

例题 以下()属于临界资源。

$A.$磁盘存储介质

$B.$公用队列

$C.$私用数据

$D.$可重入的程序代码

解：$B$。临界资源与共享资源的区别在于，在一段时间内能否允许被多个进程访问（并发使用)，显然磁盘属于共享设备。在域环境中，公用队列是$Active,Directory$中发布的队列，因此通过整个$Windows,Server,2003$家族林进行复制。公用队列可供多个进程使用，但一次只可供一个进程使用，试想若多个进程同时使用公用队列，势必造成队列中的数据混乱而无法使用。私用数据仅供一个进程使用，不存在临界区问题，可重入的程序代码一次可供多个进程使用。

信号量

PV操作

例题 下列关于$PV$操作的说法中，正确的是()。

Ⅰ.$PV$操作是一种系统调用命令 Ⅱ.$PV$操作是一种低级进程通信原语 Ⅲ.$PV$操作是由一个不可被中断的过程组成 Ⅳ.$PV$操作是由两个不可被中断的过程组成

$A.$Ⅰ、Ⅲ

$B.$Ⅱ、Ⅳ

$C.$Ⅰ、Ⅱ、Ⅳ

$D.$Ⅰ、Ⅳ

解：$B$。$PV$操作是一种低级的进程通信原语，不是系统调用，因此Ⅱ正确；$Р$操作和$V$操作都属于原子操作，所以$PV$操作由两个不可被中断的过程组成，因此Ⅳ正确。

信号量含义

例题 设与某资源关联的信号量初值为$3$，当前值为$1$。若$M$表示该资源的可用个数，$N$表示等待该资源的进程数，则$M$，$N$分别是()。

A.0,1

B.1,0

C.1,2

D.2,0

解：$D$。信号量是一个特殊的整型变量，只有初始化和$PV$操作才能改变其值。通常，信号量分为互斥量和资源量，互斥量的初值一般为$1$，表示临界区只允许一个进程进入，从而实现互斥。当互斥量等于$0$时，表示临界区已有一个进程进入，临界区外尚无进程等待；当互斥量小于$0$时，表示临界区中有一个进程，互斥量的绝对值表示在临界区外等待进入的进程数。同理，资源信号量的初值可以是任意整数，表示可用的资源数，当资源量小于$0$时，表示所有资源已全部用完，而且还有进程正在等待使用该资源，等待的进程数就是资源量的绝对值。

例题 一个进程因在互斥信号量mutex上执行V(mutex)操作而导致唤醒另一个进程时，执行$V$操作后mutex的值为()。

$A.$大于0

$B.$小于0

$C.$大于等于0

$D.$小于等于0

解：$D$。由题意可知，$V$操作导致唤醒另一个进程，所以系统原来就存在等待进入临界区的进程，mutex小于等于$-1$，因此在执行V(mutex)操作后，mutex的值小于等于$0$。

信号量初值

例题 用$PV$操作实现进程同步，信号量的初值为()。

A.-1

B.0

C.1

$D.$由用户确定

解：$D$。与互斥信号量初值一般为$1$时不同，用$PV$操作实现进程同步，信号量的初值应根据具体情况来确定。若期望的消息尚未产生，则对应的初值应为$0$，若期望的消息已存在，则信号量的初值应设为一个非$0$的正整数。（一般看之前的同步互斥应用一般设置为$0$是因为还没有产生消息）

例题 在$9$个生产者、$6$个消费者共享容量为$8$的缓冲器的生产者-消费者问题中，互斥使用缓冲器的信号量初始值为()。

A.1

B.6

C.8

D.9

解：$A$。所谓互斥使用某临界资源，是指在同一时间段只允许一个进程使用此资源，所以互斥信号量的初值都为$1$。

信号量值范围

例题 有三个进程共享同一程序段，而每次只允许两个进程进入该程序段，若用$PV$操作同步机制，则信号量$S$的取值范围是()。

A.2,1,0,-1

B.3,2,1,0

C.2,1,0,-1,-2

D.1,0,-1,-2

解：$A$。因为每次允许两个进程进入该程序段，即资源（这里指可进入的空间）的最大容量为$2$，所以信号量最大值取$2$。至多有三个进程申请，则信号量最小为$-1$，即最多只存在一个进程在等待，所以信号量可以取$2,1,0,—1$。

进程同步与互斥应用

进程互斥

例题 进程$P_1$和$P_2$均包含并发执行的线程，部分伪代码描述如下所示。

// 进程P1
int x=0;
Thread1(){
    int a;
    a=1;
    x+=1;
}
Thread2(){
    int a;
    a=2;
    x+=2;
}

// 进程P2
int x=0;
Thread3(){
    int a;
    a=x;
    x+=3;
}
Thread4(){
    int b;
    b=x;
    x+=4;
}

下列选项中，需要互斥执行的操作是()。

$A.a=1$与a=2

$B.a=x$与b=x

$C.x+=1$与x+=2

$D.x+=1$与x+=3

解：$C$。只有对共享变量的赋值可能需要互斥操作。$P$中对$a$进行赋值，并不影响最终的结果，因此$a=1$与$a=2$不需要互斥执行，所以$A$不是。$a=x$与$b=x$执行先后不影响$a$与$b$的结果，无须互斥执行，$B$不是。在同一个进程中，$x+=1$与$x+=2$执行先后会影响$x$的结果，需要互斥执行，$C$需要。$P_1$中的x和$P_2$中的$x$虽然是共享变量，但是不同范围中的$x$，互不影响，不需要互斥执行，$D$不需要。所以其实$x+=3$和$x+=4$也要互斥运行。

管程

例题 以下关于管程的叙述中，错误的是()。

$A.$管程是进程同步工具，解决信号量机制大量同步操作分散的问题

$B.$管程每次只允许一个进程进入管程

$C.$管程中$signal$操作的作用和信号量机制中的$V$操作相同

$D.$管程是被进程调用的，管程是语法范围，无法创建和撤销

解：$C$。管程的$signal$操作与信号量机制中的$V$操作不同，信号量机制中的$V$操作一定会改变信号量的值$S=S+1$。而管程中的$signal$操作是针对某个条件变量的，若不存在因该条件而阻塞的进程，则$signal$不会产生任何影响。

例题 若$x$是管程内的条件变量，则当进程执行x.wait()时所做的工作是()。

$A.$实现对变量$x$的互斥访问

$B.$唤醒一个在$x$上阻塞的进程

$C.$根据$x$的值判断该进程是否进入阻塞态

$D.$阻塞该进程，并将之插入$x$的阻塞队列中

解：$D$。这是基本的概念，且由于进程已经执行x.wait()，证明判断条件为真应该阻塞，所以$C$不对。“条件变量”是管程内部说明和使用的一种特殊变量，其作用类似于信号量机制中的“信号量”，都用于实现进程同步。需要注意的是，在同一时刻，管程中只能有一个进程在执行。若进程$A$执行了x.wait()操作，则该进程会阻塞，并挂到条件变量x对应的阻塞队列上。这样，管程的使用权被释放，就可以有另一个进程进入管程。若进程$B$执行了x.signal()操作，则会唤醒x对应的阻塞队列的队首进程。在$Pascal$语言的管程中，规定只有一个进程要离开管程时才能调用signal()操作。

死锁

死锁的概念

例题 死锁的四个必要条件中，无法破坏的是()。

$A.$环路等待资源

$B.$互斥使用资源

$C.$占有且等待资源

$D.$非抢夺式分配

解：$B$。所谓破坏互斥使用资源，是指允许多个进程同时访问资源，但有些资源根本不能同时访问，如打印机只能互斥使用。因此，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。其他三个条件都可以实现。

例题 某个系统采用下列资源分配策略。若一-个进程提出资源请求得不到满足，而此时没有由于等待资源而被阻塞的进程，则自己就被阻塞。而当此时已有等待资源而被阻塞的进程，则检查所有由于等待资源而被阻塞的进程。若它们有申请进程所需要的资源，则将这些资源取出并分配给申请进程。这种分配策略会导致()。

$A.$死锁

$B.$颠簸

$C.$回退

$D.$饥饿

解：$D$。首先根据题目的资源分分配策略可以分析得到：如果只有一个进程等待资源就堵塞，如果有多个就争夺其他堵塞进程的资源。某个进程主动释放资源不会导致死锁，因为破坏了请求并保持条件，选项$A$错。颠簸也就是抖动，这是请求分页系统中页面调度不当而导致的现象，指内容反复调入调出内存，所以没有关系，$B$是错的。回退是指从此时此刻的状态退回到一分钟之前的状态，假如一分钟之前拥有资源$X$，它有可能释放了资源$X$，那就不称回到一分钟之前的状态，也就不是回退，选项$C$错。由于进程过于“慷慨”，不断把自己已得到的资源送给别人，导致自己长期无法完成，所以是饥饿，选项$D$对。

例题 若系统$S_1$采用死锁避免方法，$S_2$采用死锁检测方法。下列叙述中，正确的是()。

Ⅰ.$S_1$会限制用户申请资源的顺序，而$S_2$不会

Ⅱ.$S_1$需要进程运行所需的资源总量信息，而$S_2$不需要

Ⅲ.$S_1$不会给可能导致死锁的进程分配资源，而$S_2$会

$A.$仅Ⅰ、Ⅱ

$B.$仅Ⅱ、Ⅲ

$C.$仅Ⅰ、Ⅲ

$D.$Ⅰ、Ⅱ、Ⅲ

解：$B$。死锁预防采用破坏产生死锁的$4$个必要条件中的一个或几个来防止发生死锁。其中之一的“破坏循环等待条件”，一般采用顺序资源分配法，首先给系统的资源编号，规定每个进程必须按编号递增的顺序请求资源，即限制了用户申请资源的顺序，因此Ⅰ的前半句属于死锁预防的范畴。

银行家算法是最著名的死锁避免算法，其中的最大需求矩阵$Max$定义了每个进程对$m$类资源的最大需求量，系统在执行安全性算法中都会检查此次资源试分配后，系统是否处于安全状态,若不安全则将本次的试探分配作废。在死锁的检测和解除中，系统为进程分配资源时不采取任何措施，但提供死锁的检测和解除手段，因此Ⅱ、Ⅲ正确。

死锁进程数

例题 系统中有$3$个不同的临界资源$R_1$，$R_2$和$R_3$，被$4$个进程$P_1$，$P_2$，$P_3$，$P_4$共享。各进程对资源的需求为: $P_1$申请$R_1$和$R_2$，$P_2$申请$R_2$和$R_3$，$P_3$申请$R_1$和$R_3$，$P_4$申请$R_2$。若系统出现死锁，则处于死锁状态的进程数至少是()。

A.1

B.2

C.3

D.4

解：$C$。对于本题，先满足一个进程的资源需求，再看其他进程是否出现死锁状态。因为$P_4$只申请一个资源，当将$R_2$分配给$P_4$后，$P_4$执行完后将$R_2$释放，这时使得系统满足死锁的条件是$R_1$分配给$_1$，$R_2$分配给$P_2$，$R_3$分配给$P_4$，（或者$R_2$分配给$P_1$，$R_3$分配给$P_2$，$R_1$分配给$P_3$）。穷举其他情况，各种情况需要使得处于死锁状态的进程数至少为$3$。（即至多只能满足一个进程）

银行家算法

例题 系统中有$5$个进程$P_0$到$P_4$，$3$种资源$R_0$到$R_2$，初始数量为$(10,5,7)$，某一时刻的情况可表示如下:

进程	最大需求	已分配
P0	(7,5,3)	(0,1,0)
P1	(3,2,2)	(2,0,0)
P2	(9,0,2)	(3,0,2)
P3	(2,2,2)	(2,1,1)
P4	(4,3,3)	(0,0,2)

解：将已分配的部分全部加起来得到$(7,2,5)$，还剩余资源数$Available=(3,3,2)$。

将每个进程的最大需求减去已分配，会得到最多还需要的资源数量，三列分别为$Max$、$Allocation$、$Need$：

进程	最大需求	已分配	最多还需要
P0	(7,5,3)	(0,1,0)	(7,4,3)
P1	(3,2,2)	(2,0,0)	(1,2,2)
P2	(9,0,2)	(3,0,2)	(6,0,0)
P3	(2,2,2)	(2,1,1)	(0,1,1)
P4	(4,3,3)	(0,0,2)	(4,3,1)

将剩余资源数$Work=(3,3,2)$与各个进程的最多还需要值$Need$对比，如果剩余资源数每个资源值都大于该进程的最多还需要的资源值，就代表这个进程可以分配资源。

对比得到$P_1$和$P_3$可以分配。

其中若先$P_1$分配完归还资源后可用资源为$(3,3,2)+(1,2,2)=(5,3,2)$，然后使用该可用资源序列进行下一轮的分配，直到五次循环检查后五个进程都加入了安全序列中${P_1,P_3,P_4,P_2,P_0}$，就得到了一个最终的序列。该算法称为安全性算法。

例题 某系统有$R_1$，$R_2$和$R_3$共三种资源，在$T_0$时刻$P_1$，$P_2$，$P_3$，和$P_4$。这四个进程对资源的占用和需求情况见下表，此时系统的可用资源向量为$(2,1,2)$。试问：

1）用向量或矩阵表示系统中各种资源的总数和此刻各进程对各资源的需求数目。

2）若此时进程$P_1$和进程$P_2$均发出资源请求向量$Request(1,0,1)$，为了保证系统的安全性，应如何分配资源给这两个进程？说明所采用策略的原因。

3）若2）中两个请求立刻得到满足，系统此时是否处于死锁状态？

资源情况	最大资源需求量			已分配资源数量
进程	R1	R2	R3	R1	R2	R3
P1	3	2	2	1	0	0
P2	6	1	3	4	1	1
P3	3	1	4	2	1	1
P4	4	2	2	0	0	2

解：

1）资源总量为$(9,3,6)$，$Need=\left[\begin{array}{ccc} 2 & 2 & 2 \ 2 & 0 & 2 \ 1 & 0 & 3 \ 4 & 2 & 0 \end{array}\right]$。

2）若此时$P_1$发出资源请求$Request_1(1,0,1)$，则按银行家算法进行检查：

$Request_1(1,0,1)\leqslant Need_1(2,2,2)$，$Request_1(1,0,1)\leqslant Available(2,1,2)$，$Available(1,1,1)$。

资源情况	Allocation			Need
P1	1	0	0	2	2	2
P2	4	1	1	2	0	2
P3	2	1	1	1	0	3
P4	0	0	2	4	2	0

再利用安全性算法检查系统是否安全，可用资源$Available(1,1,1)$已不能满足任何进程，系统进入不安全状态，此时系统不能将资源分配给进程$P_1$。

若此时进程$P_2$发出资源请求$Requestz(1,0,1)$，则按银行家算法进行检查：

$Requestz(1,0,1)\leqslant Needz(2,0,2)$，$Requestz(1,0,1)\leqslant Available(2,1,2)$，$Available(1,1,1)$。

试分配并修改相应数据结构，由此形成的进程$P_2$请求资源后的资源分配情况下表：

资源情况	Allocation			Need
P1	1	0	0	2	2	2
P2	5	1	2	1	0	1
P3	2	1	1	1	0	3
P4	0	0	2	4	2	0

再利用安全性算法检查系统是否安全，可得到如下表中所示的安全性检测情况。$Work$指当前可用资源，注意表中各个进程对应的$Work+Allocation$向量表示在该进程释放资源之后更新的$Work$向量。

资源情况	Need			Allocation			Work			Work	+	Allocation
P2	1	0	1	5	1	2	1	1	1	6	2	3
P3	1	0	3	2	1	1	6	2	3	8	3	4
P4	4	2	0	0	0	2	8	3	4	8	3	6
P1	2	2	2	1	0	0	8	3	6	9	3	6

从上表中可以看出，此时存在一个安全序列${P_2,P_3,P_4,P_1}$，因此该状态是安全的，可以立即将进程$P_2$所申请的资源分配给它。

3）若2）中的两个请求立即得到满足，则此刻系统并未立即进入死锁状态，因为这时所有的进程未提出新的资源申请，全部进程均未因资源请求没有得到满足而进入阻塞态。只有当进程提出资源申请且全部进程都进入阻塞态时，系统才处于死锁状态。

进程与死锁

例题 下面是一个并发进程的程序代码，正确的是()。

semaphore xl=x2=y=1;
int c1=c2=0;

P1(){
    while(1){
        P(x1);
        if(++c1==1) P(y);
        V(x1);
        computer(A);
        P(x1);
        if(--c1=0) V(y);
        V(x1);
    }
}

P2(){
    while(1){
        P(x2);
        if(++c2==1) P(y);
        V(x2);
        computer(B);
        P(x2);
        if(--c2=0) V(y);
        V(x2);
    }
}

$A.$进程不会死锁，也不会“饥饿”

$B.$进程不会死锁，但是会“饥饿”

$C.$进程会死锁，但是不会“饥饿”

$D.$进程会死锁，也会“饥饿”

解：$B$。首先$P1$分别对x1、c1、y操作，$P2$对x2、c2、y操作，其中只存在一个公用y，也没有不占有所以不存在抢夺变量的。而代码过程中存在$PV$操作，对$y$进行$P$不断的操作可能导致对方进程饥饿。如$P1$进程更快，$P2$进程稍慢，不断$P1$进入，$P2$被堵塞，而$c1$变成$2$不断被$P1$占用，所以导致饥饿。

例题 有两个并发进程，对于如下这段程序的运行，正确的说法是()。

int x,y,z,t, u;
P1(){
    while(1){
        x=1;
        y=0;
        if x>=1 then y=y+1;
        z=y;
    }
}

P2(){
    while(1){
        x=0;
        t=0;
        if x<=1 then t=t+2;
        u=t;
    }
}

$A.$程序能正确运行，结果唯一

$B.$程序不能正确运行，可能有两种结果

$C.$程序不能正确运行，结果不确定

$D.$程序不能正确运行，可能会死锁

解：$C$。公用变量为$x$，所以可能会导致不同的结果，$A$错误。不存在资源占有等待其他资源，所以不会死锁，$D$错误。最重要的是结果到底有哪几种。通过不同顺序可以得到$(y,z,t,u,x)$为$(1,1,2,2,0)$、$(0,0,2,2,0)$、$(1,1,2,2,1)$三种。

资源分配图

例题 假定某计算机系统有$R_1$和$R_2$两类可使用资源（其中$R_1$有两个单位，$R_2$有一个单位），它们被进程$P_1$和$P_2$所共享，且已知两个进程均以下列顺序使用两类资源：申请$R_1$→申请$R_2$→申请$R_1$→释放$R_1$→释放$R_2$→释放$R_1$。试求出系统运行过程中可能到达的死锁点，并画出死锁点的资源分配图（或称进程资源图）。

解：在本题中，当两个进程都执行完第一步后，即进程$P_1$和进程$P_2$都申请到了一个$R_1$类资源时，系统进入不安全状态。随着两个进程向前推进，无论哪个进程执行完第二步，系统都将进入死锁状态。可能达到的死锁点是：一个进程占有$P_1$和$P_2$，另一个进程占有一个$P_1$，此时系统内已无空闲资源，而两个进程都在保持已占有资源不释放的条件下造成死锁。

假如$P1$占有了两个资源：