操作系统试题整理 - 图文 下载本文

信号量值的变化范围是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页