如果S＜0，则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止）。 V(S)：顺序执行下述两个动作： ①S值加1，即S=S+1；
②如果S＞0，则该进程继续运行；
如果S≤0，则释放信号量队列上的第一个PCB（即信号量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续运行。
（8） 计算机系统中产生死锁的根本原因是什么？
计算机系统中产生死锁的根本原因是：资源有限且操作不当。此外，进程推进顺序不合适也可以引发的死锁。
（9） 发生死锁的四个必要条件是什么？
发生死锁的四个必要条件是：互斥条件，不可抢占条件，占有且申请条件，循环等待条件。
（10） 一般解决死锁的方法有哪三种？
一般解决死锁的方法有：死锁的预防、死锁的避免、死锁的检测与恢复。
3． 思考题
（1） 是否所有的共享资源都是临界资源？为什么？
不是所有的共享资源都是临界资源。因为临界资源是一次仅允许一个进程使用的资源，而系统中有很多资源可以让多个进程同时使用，例如硬盘、正文段等。
（2） 系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P、V操作写出这些进程使用打印机的算法。
因为打印机是一种临界资源，所以这三个进程只能互斥使用这台打印机，即一个用户的计算结果打印完之后，另一个用户再打印。 设三个进程分别为A、B和C。
设一个互斥信号量mutex，其初值为1。
进程A 进程B 进程C
P(mutex) P(mutex) P(mutex) 使用打印机 使用打印机 使用打印机 V(mutex) V(mutex) V(mutex)
（3） 判断下列同步问题的算法是否正确？若有错，请指出错误原因并予以改正。 ① 设A，B两个进程共用一个缓冲区Q，A向Q写入信息，B从Q读出信息，算法框图如图3-24所示。
② 设A，B为两个并发进程，它们共享一个临界资源。其运行临界区的算法框图如
图3-25所示。
图3-24 进程A, B的算法框图 图3-25 两个并发进程临界区的算法框图
① 这个算法不对。因为A、B两个进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从Q中读出完整的信息。
改正：
A、B两进程要同步使用缓冲区Q。为此，设立两个信号量： empty表示缓冲区Q为空，初值为1； full表示缓冲区Q为满，初值为0。
算法框图如图1所示。
② 这个算法不对。因为A、B两个进程是并发的，它们共享一个临界资源，所以二者应互斥地使用该临界资源，在进入临界区时不存在先A后B的时序关系，而是哪个进程先到一步就先进入自己的临界区。
改正： A、B两个进程应互斥地进入临界区。为此，设立一个信号量：互斥信号量mutex，其初值为1。
算法框图如图2所示。
A进程 B进程 A进程 B进程
P(empty) P(full) P(mutex) P(mutex) 向Q写入信息 从Q中读出信息 临界区代码CSa 临界区代码CSb V(full) V(empty) V(mutex) V(mutex)
图1 图 2
（4） 设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后再搬到缓冲区B2中，并在打印机上打印结果。问：
① 系统要设几个进程来完成这个任务？各自的工作是什么？
② 这些进程间有什么样的相互制约关系？ ③ 用P、V操作写出这些进程的同步算法。
①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入
到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。
②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后，C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。
③信号量含义及初值：
B1full—— 缓冲区B1满，初值为0； B1empty——缓冲区B1空，初值为0； B2full—— 缓冲区B2满，初值为0； B2empty——缓冲区B2空，初值为0； R进程 C进程 P进程
输入信息写入缓冲区B1 P(B1full) P(B2full)
V(B1full) 从B1中取出信息 从B2中取出信息进行打印 P(B1empty) 加工信息 V(B2empty) 结果送入B2 V(B1empty) V(B2full)
P(B2empty)
（5） 设有无穷多个信息，输入进程把信息逐个写入缓冲区，输出进程逐个从缓冲区中取出信息。针对下述两种情况：
① 缓冲区是环形的，最多可容纳n个信息； ② 缓冲区是无穷大的。 试分别回答下列问题：
① 输入、输出两组进程读/写缓冲区需要什么条件？
② 用P、V操作写出输入、输出两组进程的同步算法，并给出信号量含义及初值。
① 针对容量为n的环形缓冲区，输入、输出两组进程读/写缓冲区需要的条件为：
? 输入进程和输出进程需同步执行，即输入进程写缓冲区后，输出进程才可以读； ? 由于缓冲区容量有限，因此任一时刻所有输入进程存放信息的单元数不能超过
缓冲区的总容量（n）；
? 同理，所有输出进程取出信息的总量不能超过所有输入进程当前写入信息的总
数。
设缓冲区的编号为0～n-1，in和out分别是输入进程和输出进程使用的指针，指向下面可用的缓冲区，初值都是0。
为使两类进程实行同步操作，应设置三个信号量：两个计数信号量full和empty，一个互斥信号量mutex。
full：表示放有信息的缓冲区数，其初值为0。
empty：表示可供使用的缓冲区数，其初值为n。
mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。
下面是解决这个问题的算法描述。
输入进程Input： while (TRUE) { P(empty);
P(mutex);
信息送往buffer(in);
in=(in+1)mod N; /*以N为模*/ V(mutex); V(full); }
输出进程Output：
while (TRUE){ P(full);
P(mutex);
从buffer(out)中取出信息;
out=(out+1)mod N; /*以N为模*/
V(mutex); V(empty); }
② 当缓冲区是无穷大时，输入进程存放信息的单元数不再受缓冲区总容量的限制，因
此，可以不设信号量empty。另外，算法中的in=(in+1)mod N; 和out=(out+1)mod N;
修改为in=in+1；和out=out+1；即可，其余的算法不变。 输入进程Input： while (TRUE) {
P(mutex);
信息送往buffer(in); in=in+1; V(mutex); V(full); }
输出进程Output： while (TRUE){
P(full);
P(mutex);
从buffer(out)中取出信息;
out=out+1; V(mutex); }
第3章 处理机调度
“练习与思考”解答
4． 基本概念和术语
调度、作业调度、进程调度、吞吐量、周转时间、带权周转时间、中断
调度就是选出待分派的作业或进程。
作业调度就是根据一定的算法，从输入的一批作业中选出若干个作业，分配必要的资源，如内存、外设等，为它建立相应的用户作业进程和为其服务的系统进程（如输入、输出进程），最后把它们的程序和数据调入内存，等待进程调度程序对其执行调度，并在作业完成后作善后处理工作。
进程调度就是根据一定的算法将CPU分派给就绪队列中的一个进程。
吞吐量：单位时间内CPU完成作业的数量。
周转时间：从作业提交到作业完成的时间间隔。
带权周转时间：定义为作业的周转时间除以其实际运行时间。
中断是指CPU对系统发生的某个事件做出的一种反应，它使CPU暂停正在执行的程序，保留现场后自动执行相应的处理程序，处理该事件后，如被中断进程的优先级最高，则返回断点继续执行被“打断”的程序。
5． 基本原理和技术
（1） 处理机调度的主要目的是什么？ 处理机调度的主要目的就是为了分配处理机。
（2） 高级调度与低级调度的主要功能是什么？为什么要引入中级调度？
高级调度的主要功能是根据一定的算法，从输入的一批作业中选出若干个作业，分配必要的资源，如内存、外设等，为它建立相应的用户作业进程和为其服务的系统进程（如输入、输出进程），最后把它们的程序和数据调入内存，等待进程调度程序对其执行调度，并在作业完成后作善后处理工作。
低级调度的主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。 为了使内存中同时存放的进程数目不至于太多，有时就需要把某些进程从内存中移到外存上，以减少多道程序的数目，为此设立了中级调度。
（3） 作业在其存在过程中分为哪四种状态？
作业在其存在过程中分为提交、后备、执行和完成四种状态。
（4） 在操作系统中，引起进程调度的主要因素有哪些？
在操作系统中，引起进程调度的主要因素有：正在运行的进程完成任务，或等待资源，或运行到时；核心处理完中断或陷入事件后，发现系统中“重新调度”标志被置上。