操作系统第2章练习题.doc

第2章 进程管理
2.1 典型例题解析
【例1】试比较进程与程序的异同。（哈尔滨工业大学2000年研究生考题）
答：进程和程序是紧密相关而又完全不同的概念。
（1）每个进程实体中包含了程序段、数据段这两个部分，因此说进程和程序是紧密相关的。但从结构上看，进程实体中除了程序段和数据段外，还必须包含一个数据结构，即进程控制块PCB。
（2）进程是程序的一次执行过程，因此是动态的；动态性还表现在进程由创建产生、由调度而执行、由撤销而消亡，即它具有一定的生命周期。而程序则只是一组指令的有序集合，并可永久地存放在某种介质上，其本身不具有动态的含义，因此是静态的。
（3）多个进程实体可同时存放在内存中并发执行，其实这正是引入进程的目的。而程序的并发执行具有不可再现性，因此程序不能正确地并发执行。
（4）进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。而因程序不具有PCB，所以它是不可能在多道程序环境下独立运行的。
（5）进程和程序不一一对应。同一个程序的多次运行，将形成多个不同的进程；同一个程序的一次执行也可以产生多个进程；而一个进程也可以执行多个程序。

【例2】什么是进程控制块？它有什么作用？
答：进程控制块PCB是一个记录进程属性信息的数据结构，是进程实体的一部分，是操作系统中最重要的数据结构。
当操作系统要调度某进程执行时，需要从该进程的PCB中查询其现行状态和优先级调度参数；在调度到某进程后，要根据其PCB中保存的处理机状态信息去设置和恢复进程运行的现场，并根据其PCB中的程序和数据的内存地址来找到其程序和数据；进程在执行过程中，当需要与其它进程通信时，也要访问其PCB；当进程因某种原因而暂停执行时，又需要将断点的现场信息保存在其PCB中。系统在建立进程的同时就建立了该进程的PCB，在撤销一个进程时也就撤销其PCB。
由此可知，操作系统根据PCB来对并发执行的进程进行控制和管理，PCB是进程存在的惟一标志。

【例3】什么是原语？
答：原语是由若干条机器指令构成的一段程序，用以完成特定的功能。这段程序在执行期间不可分割。也就是说，原语的执行不能被中断，所以原语操作具有原子性。

【例4】进程和线程的主要区别是什么？（西北工业大学1999年研究生考题）
答：从调度、并发性、系统开销、拥有资源等方面来比较线程和进程：
⑴调度。无线程概念的操作系统中，独立调度、分派的基本单位是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程是资源的拥有者。同一进程中的线程之间切换，不会引起进程切换而不通进程的线程之间切换，会引起进程切换。
⑵并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。
⑶拥有资源。不论是无线程概念的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般地说，线程自己不拥有系统资源（也有一点必不可少的资源），但它可以访问其隶属进程的资源。
⑷系统开销。由于在创建、撤销或切换进程时，系统都要为之分配或回收资源，保存CPU现场。因此，操作系统所付出的开销将显著地大于在创建、撤销或切换线程时的开销。

【例5】a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确管理以保证行驶安全。
解析：读者－写着问题的变形。我们设置3个信号量S1、S2和Sab，分别用于从a点进入的车互斥访问共享变量ab（用于记录当前ab段上由a点进入的车辆的数量），从b点进入的车互斥访问共享变量ba（用于记录当前ab段上由b点进入的车辆的数量）和a、b点的车辆互斥进入ab段。3个信号量的初值分别为1、1和1，两个共享变量ab和ba的初值分别为0、0。
Semaphore S1=1,S2=1,Sab=1;
int ab=ba=0;
void Pab ()
{
while(1)
{
wait(S1);
if(ab==0) wait(Sab);
ab=ab+1;
signal(S1);
车辆从a点驶向b点;
wait(S1);
ab=ab-1;
if(ab==0) signal(Sab);
signal(S1);
}
}
void Pba ()
{
while(1)
{
wait(S2);
if(ba==0) wait(Sab);
ba=ba+1;
signal(S2);
车辆从b点驶向a点;
wait(S2);
ba=ba-1;
if(ba==0) signal(Sab);
signal(S2);
}
}
main()
{
cobegin{ Pab (); Pba (); }
}
【例6】桌子上有一只盘子，每次只能放一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用PV操作实现他们之间的同步机制。（复旦大学1997年/南京理工大学2004年研究生考题）
解析：由于爸爸和妈妈可以同时向盘子放水果，所以盘子是临界资源，应设置一个互斥信号量empty来实现放水果的互斥，其初值为1。此外爸爸和女儿、妈妈和儿子之间存在同步关系，即分别设置信号量apple和orange来分别实现这种同步关系，其初值均为0。
Semaphore empty=1, apple=orange=0;
void father（）
{
while1)
{
wait(empty);
放苹果；
signal(apple);
}
}
void mother()
{
while(1)
{
wait(empty);
放橘子；
signal(orange);
}
}
void daughter()
{
while(1)
{
wait(applel);
取苹果；
signal(empty)
}
}
void son()
{
while(1)
{
wait(orange);
取橘子；
signal(empty);
}
}
main()
{
cobegin{
father();
mother();
daughter();
son();
}
}
【例7】一个供应商用汽车给某超市送货，并把汽车上的货物用超市的三轮车运到仓库中。超市的工作人员也用三轮车从仓库中取货去出售。假设共有3辆三轮车，仓库中只能容纳10辆三轮车的货物，且每次从汽车上取货只能供给一辆三轮车，仓库也只能容纳一辆三轮车进入。考虑相关信号量的定义及初值，并写出用P、V操作实现向仓库中送货及从仓库中取货的同步算法。（西安交通大学2005年考研试题）
解析：题目的限制条件暗示着临界资源的存在。如本题中，仓库只能容纳一辆车进入，且最多容纳10辆车的货物，则仓库显然是需要互斥使用的缓冲区资源。共有三辆小车，则三轮车也是受限资源；汽车一次取货只能供给一辆小车，则汽车也是互斥资源。为所有的互斥资源设置信号量如下：
S=3(控制三轮车数量)
mutex1=1（控制互斥访问汽车）
mutex2=1（控制互斥访问仓库）
empty=10（仓库容量）
full=0（仓库现有库存量，供给超市）

从汽车到仓库进程：
P(empty);
P(S);
P(mutex1);
从汽车上取货；
V(mutex1);
去仓库；
P(mutex2);
入仓库装货；
V(mutex2);
V(S);
V(full);

从仓库到超市进程：
P(full);
P(S);
P(mutex2);
从仓库取货；
V(mutex2);
V(empty);
去超市；
V(S);

【例8】三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。（2009年考研题）

semahpore empty=N,even=0,odd=0,mutex=1;
P1:
while(1)
{
x=produce();
wait(empty);
wait(mutex);
put(x);
if x%2==0
signal(even);
else
signal(odd);
signal(mutex);
}

P2:
while(1)
{
wait(odd);
wait(mutex);
getodd();
countodd();
signal(mutex);
signal(empty);
}

P2:
while(1)
{
wait(even);
wait(mutex);
geteven();
counteven();
signal(mutex);
signal(empty);
}

22 练习题及答案
一、 选择题
1．进程的组成部分中（）是进程存在的惟一标志。
A、PCB B、数据集合
C、共享程序 D、非共享程序
2.进程从运行状态到阻塞状态可能是由于( )。
A、现运行进程执行了P操作 B、现运行进程时间片用完
C、现运行进程执行了V操作 D、进程调度程序的调度
3．在进程管理中，当（）时，进程从阻塞状态变为就绪状态。
A、进程被进程调度程序选中 B、等待某一事件
C、等待的事件发生 D、时间片用完
4．下列选项中，导致创进新进程的操作是（）。
I用户成功登陆 II设备分配 III启动程序执行
A：仅I和II B：仅II和III
C：仅I和III D：I，II，III
5．引入多道程序设计技术的目的在于()。
A、充分利用CPU，增加单位时间内的算题量
B、充分利用存储器
C、有利于代码共享，减少主、辅存信息交换量
D、提高每一个算题的速度
6．分配给进程占用处理器的时间到而强迫进程让出处理器，或有更高优先数的进程要运行，迫使正在运行的进程让出处理器，则进程状态变化的情况为()。
A、运行态->就绪态 B、运行态->等待态
C、就绪态->运行态 D、等待态->就绪态
7．设与某资源相关联的信号量初值为3，当前值为1，若M表示该资源的可用个数，N表示等待资源的进程数，则M,N分别是（）。
A：0，1 B：1，0 C：1，2 D：2，0
8．在一般情况下，下列进程变化状态中，（）和（）是不可能发生的。
A、运行->就绪 B、等待->运行
C、等待->就绪 D、运行->等待
E、就绪->等待
9．系统可把等待资源的进程组织成等待队列，这样的等待队列有（）。
A、0个 B、1个
C、2个 D、1个或多个
10．一次中断后可能引起若干个进程状态的变化，因此中断处理后，由（）来决定哪个进程可占用处理器。
A、进程调度 B、页面调度
C、移臂调度 D、作业调度
11．若信号量S初值为3，当前值为－2，则表示有（）等待进程。（西北工业大学2001考题）
A、2个 B、3个
C、4个 D、5个
12．多道程序环境下，操作系统分配资源以（）为基本单位。
A、程序 B、指令
C、作业 D、进程
13．在单一处理机上执行程序，多道程序的执行是在（ ）进行的。
A.同一时刻 B. 同一时间间隔内　　
C.某一固定时刻 D. 某一固定时间间隔内
14．进程和程序的本质区别是（ ）。　　
A.存储在内存和外存 B.顺序和非顺序执行机器指令
C.分时使用和独占使用计算机资源 D.动态和静态特征
15．一个进程被唤醒意味着（ ）。 　　
A.该进程重新占有了CPU B.进程状态变为就绪 　　
C.它的优先权变为最大 D.其PCB移至就绪队列的队首
16．在操作系统中同时存在多个进程，它们（ ）。 　　
A. 不能共享系统资源 　　 B. 不能调用同一段程序代码 　　
C. 可以共享允许共享的系统资源 　　D. 可以共享所有的系统资源
17．两个进程合作完成一个任务，在并发执行中，一个进程要等待其合作伙伴发来信息，或者建立某个条件后再向前执行，这种关系是进程间的（ ）关系。　　
A.同步 B. 互斥 C.竞争 D. 合作
18．在一段时间内，只允许一个进程访问的资源称为（ ）。　　
A. 共享资源 B. 临界区 C. 临界资源 D. 共享区

二、填空题
1．进程的基本特征有 、 、独立性、异步性和结构特征。
2．把一个程序在某个数据集合上的一次执行称为一个 。
3．进程主要由 、 、 三部分内容组成，其中 是进程存在的惟一标志。
4．临界资源的概念是 ，而临界区是指 。
5．进程控制块包含 、 、 、 四类信息。
6．目前常用的PCB的组织形式有 和 两种。
7．有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是 。
8．在一个单处理机系统中，若有5个用户进程，且假设当前时刻为用户态，则处于就绪状态的用户进程最多有 个，最少有 个。
9．信号量的物理意义是当前信号量的值大于零时表示 ；当信号量值小于零时，其绝对值表示 。
10．线程是进程中可 的子任务，一个进程中可以有 线程，每个线程都有一个 的标识符。
11．一个管程由三部分构成，分别是 、 和 。
12．进程间的高级通信机制可归结为3大类，分别是 、 和 。

三、判断题
1．当一个进程从等待态变成就绪态，则一定有一个进程从就绪态变成运行态。（北京航空航天大学2002年考题）
2．我们说程序的并发执行将导致最终结果失去封闭性。这句话对所有的程序都成立。
3．对临界资源应采取互斥访问的方式来实现共享。（北京理工大学2002年考题）
4．并发性是指若干事件在不同时刻发生。（北京理工大学2002年考题）

四、问答题
1．在操作系统中为什么要引入进程概念？它与程序的差别和关系是怎样的？
2．PCB的作用是什么？它是怎样描述进程的动态性质的？
3．进程的基本状态有几种？试描绘进程状态转换图。
4．PCB表的组织方式主要有那几种？分别予以简要说明。
5．什么是进程的互斥与同步？
6．什么是临界区和临界资源？一进程进入临界区的调度原则是什么？
7．简述信号量的定义和作用。P、V操作原语是如何定义的？

参考答案
一、选择题
1.A 2.A 3.C 4.C 5.A 6.A 7.B 8.BE 9.D 10.A 11.A 12.D 13．B 14．D 15.B 16.C 17.A 18.C

二、填空题
1． 动态性 并发性
2．进程
3．程序段 数据段 进程控制块（PCB） 进程控制块（PCB）
4．多个进程必须互斥访问的资源 进程中访问临界资源的那部分代码
5．进程标识符信息 处理机状态信息 进程控制信息 进程调度信息
6．链接形式 索引形式
7．1 至－(m-1)
8．4 0
9．可用资源的数目 因请求该资源而被阻塞的进程数目
10．独立执行 一个或多个 惟一
11．局部于管程的共享变量说明 对该数据结构进行操作的一组过程 对局部于管程的数据设置初始值的语句
12．共享存储器系统 消息传递系统 管道通信

三、判断题
1．错
2．错
3．正确
4．错
分析：并发性是指若干个事件的动作在时间上可以重叠，即系统中若干事件已经开始，但又没有运行结束。

四、问答题（略）