信号量值的变化范围是l，0，-1?-(n-1)。 在情况(2)中，信号量的初值为M，

信号量值的变化范围是M，m-1，m-2?(m-n)。

3）有一个售票厅只能容纳200人，当少于200人时，可以进入；否则需在外等侯。若将每一个购票者作

为一个进程，请用P、v操作描写其互斥关系。 设公有信号量mutex=200 购票者进程： cobegin p(mutex) 进入购票厅； 购票； v(mutex) coend

4）一条小河上有一座独木桥，规定每次只允许一人过桥。如果把每个过桥这看作一个进程，为保证安全，请用PV操作实现正确管理。

begin s：=1; cobegin begin

P(s); 过桥； V(s) end Coend end

s:semaphore;

5）两个并发进程的程序如下：若PROCESS A先执行了三个循环后，PROCESS A和PROCESS B 又并发执行

了一个循环，写出可能出现的打印值。请用PV操作进行管理，使它们并发执行时不出现与时间有关的错误。 若PR0CESS A先执行了三个循环后，N值变为3+5+5+5＝18；这时PROCESS A和PROCESS B并发执行了一个循环,这时可能出现的情况有以下几种： (1)print(N)；N：=0;N：＝N+5； (2)print(N)；N：＝N+5； N:=0； (3)N:=N十5；print(N); N:=0；

当出现情况(1)时，出现的打印值为18;当出现情况(2)时，出现的打印值为18;当出现情况(3)时，出现的打印值为23。为了使它们并发执行时不出现与时间有关的错误，我们采用了PV操作进行管理，其管理

的程序如上：

6）汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客，试设必要的信号灯及赋初值，写出他们的同步过程。

7）桌上有一个空的水果盘，盘中一次只能放一个水果，服务员、男顾客和女顾客共用这个盘子。服务员向盘中放草莓和香蕉，男顾客专等吃盘中的草莓，女顾客专等吃盘中的香蕉。规定每次当盘子空时只能放一个水果供顾客食用。请用信号量机制实现服务员、男顾客和女顾客三个进程的同步。

第5页 共22页

8）桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用PV操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。

9）a,b 两点间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车时，到达a（或b）的车辆可以进入ab段，但不能从a，b点同时驶入；当某方向在ab段行驶的车辆使出了ab段且无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用wait,signal工具对ab段实现正确管理。

第三章

18.高级调度又称作业调度或长程调度。主要功能是根据某种算法，把外存上处于后备队列的那些作业调入内存

19.低级调度称为进程调度或短程调度。主要功能是保存处理机的现场信息、按某种算法选取进程、把处理机分配给进程。三大基本机制：排队器、分派器、上下文切换机制。调度方式：非抢占式、抢占式（优先权原则、短作业优先原则、时间片原则）。它的运行频率最高。 20.中级调度主要是为了提高内存利用率和系统的吞吐量。 21.调度算法（p92）

1）先来先服务（FCFS）算法利于长作业。 2）短作业优先调度（SJF）

完成时间=开始执行+服务时间；周转时间=完成时间-到达时间；带全周转时间=周转时间/服务时间 开始执行时间=上次任务的完成时间 服务时间=进程实际运行时间 开始执行时间-到达时间=等待时间 例有如下三道作业：系统为它们服务的顺序是：1、2、3. 求平均周转时间和平均带权周转时间

第6页 共22页

平均周转时间：T=(2+2.9+3)/3=2.63h平均带权周转时间：W=(1+2.9+12)/3=5.3h

3）高优先权优先调度算法。静态优先权是创建进程是确定的，依据有：进程类型、进程对资源的要求、用户要求。除此之外还有动态优先权。（响应比Rp）优先权=1+等待时间/要求服务时间。 4）时间片轮转法（RR）p95

例A、B、C、D、E五个进程，到达时间分别为0、1、2、3、4；执行时间分别为4、3、5、2、4.

q=1

q=4

5)多级反馈队列调度算法（cpu开销大） FIFO原则

时间片轮转的方式

22.实时调度

提供必要的信息：就绪时间、开始时间和完成截止时间、处理时间、资源要求、优先级。

假设系统中有m个周期性的硬实时任务C:处理时间；p：周期时间 单处理机情况下：需满足下面的限制条

CiCi件系统才是可调度的： 多处理机系统 N?N表处理机个数 ?1??i?1Pii?1Pi1）最早截止时间优先 算法(EDF非抢占式调度方式用于非周期实时任务)

mm

非抢占式调度方式用于非周期实时任务

抢占式调度方式用于周期实时任务 通常的优先级调度不适用于实时系统

例有两个周期性任务A和B。A的周期时间为20ms，每个周期的处理时间为10ms。B的周期时间为50ms，每个周期的处理时间为25ms。

第7页 共22页

2）最低松弛度优先算法（LLF）用于抢占式调度方式中 松弛度=必须完成时间－需运行时间－当前时间

一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。

例假如有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。

23．死锁指多个进程在运行过程中因争夺资源而造成一种僵局。 原因：竞争资源、进程间推进顺序非法。

产生死锁的必要条件：互斥条件、请求和保持条件、不剥夺条件、环路等待条件。

处理死锁的基本方式：预防死锁（易实现）、避免死锁、检测死锁（利用率高）、解除死锁（利用率高）。 24.预防死锁

1）互斥条件：不能改变

2）摒弃“请求和保持”条件：一次性分配资源。简单但浪费资源，系统吞吐量大。 3）摒弃“不剥夺”条件::当进程资源请求不能满足，放弃所有资源。代价大，前功尽弃。 4）摒弃“环路等待：对资源预先排列，依次提出请求。

25.避免死锁的实质：系统在进行资源分配时，如何使系统不进入不安全状态。 例：三个进程共享12台磁带机

安全序列：

26.利用银行家算法避免死锁（p109）

27.死锁定理：死锁状态的充分条件，资源分配图不可完全简化

例1) 在一个有N个进程的单处理机系统中，有可能出现N个进程都被阻塞的情况( ) 系统处于不安全状态必然导致系统死锁。( )

2)当一进程运行时，系统可基于某种原则，强行将其撇下，把处理机分配给其他进程，这种调度方式是（） A.非剥夺方式 B.剥夺方式 C.中断方式 D.查询方式

3)在为多道程序所提供的可共享的系统资源不足时可能出现死锁。但是，不适当的（）也可能产生死锁。 A.进程优先权 B.资源的线性分配 C.进程推进顺序 D.分配队列优先权

4)发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏（）条件是不太实际的。A.互斥 B.不可抢占 C.部分分配 D.循环等待

5)在分时操作系统中，进程调度经常采用（）算法。A.先来先服务 B.最高优先权C.时间片轮转D.随机 6)（）优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。 A.先来先服务 B.静态 C.动态 D.短作业

7)某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是（）

第8页 共22页