操作系统试题整理.docx

操作系统试题整理.docx

《操作系统试题整理.docx》由会员分享，可在线阅读，更多相关《操作系统试题整理.docx（43页珍藏版）》请在冰点文库上搜索。

操作系统试题整理

简答1简述进程的状态及其转换的原因（图）

进程在其生存期内可能处于如下三种基本状态之一:

1）运行态（Run）:

进程占有处理机资源，正在运行。

2）就绪态（Ready）:

进程已分配到除cpu以外所有的必要资源，只要在获得cpu，便可执行3）阻塞态（Wait）:

正在执行的程序由于某事件二暂时无法继续执行便放弃处理机而出于暂停状态

（1）就绪状态→执行状态：

进程分配到CPU资源

（2）执行状态→就绪状态：

时间片用完

（3）执行状态→阻塞状态：

I/O请求

（4）阻塞状态→就绪状态：

I/O完成。

简答2分页和分段有何区别?

a.分页和分段都采用离散分配的方式，且都要通过地址映射机构来实现地址变换，这是它们的共同点；

b.对于它们的不同点有三，第一，从功能上看，页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率，即满足系统管理的需要，而不是用户的需要；而段是信息的逻辑单位，它含有一组其意义相对完整的信息，目的是为了能更好地满足用户的需要；第二页的大小固定且由系统确定，而段的长度却不固定，决定于用户所编写的程序；第三分页的作业地址空间是一维的，而分段的作业地址空间是二维的。

简单3比较静态重定位和动态重定位。

1）地址转换时刻：

静态重定位是在程序运行之前完成地址转换的；动态重定位却是将地址转换的时刻推迟到指令执行时进行。

2）谁来完成任务：

静态重定位是由软件完成地址转换工作的；动态重定位则由一套硬件提供的地址转换机构来完成。

3）完成的形式：

静态重定位是在装入时一次集中地把程序指令中所有要转换的地址全部加以转换；而动态重定位则是每执行一条指令时，对其地址加以转换。

4）完成的结果：

实行静态重定位，原来的指令地址部分被修改了；实行动态重定位，只是按照所形成的地址去执行这条指令，并不对指令本身做任何修改。

简答4什么是虚拟设备？

请说明SPOOLing系统是如何实现虚拟设备的。

虚拟设备是指通过虚拟技术，可将一台独占设备变换成若干台逻辑设备，供若干个用户（进程）同时使用。

由于多台逻辑设备实际上并不存在，而只是给用户的一种感觉，因此被称为虚拟设备。

SPOOLING系统中，作业执行前，操作系统已将作业通过独占设备预先输入到磁盘或磁鼓上一个特定的存储区域（称之为"输入井"）存放好，称为"预输入"，此后，作业执行使用数据时不用再启动独占设备读入，而把这一要求转换成从辅助存储器中读入。

另一方面，作业执行中，也不必直接启动独占设备输出数据，而只要将作业输出数据写入磁盘或磁鼓中的特定存储区域（称之为"输出井"）存放，当作业执行完毕后，由操作系统通过相应的输出设备来组织信息输出，称为"缓输出"。

这样做可以提高独占设备的利用率，缩短作业的执行时间。

这样，由于一台设备可以和辅助存储器中的若干存储区域相对应，所以在形式上就好像把一台输入设备（或输出设备）变成了许多虚拟的输入设备（或输出设备），即把一台不能共享的输入设备（或输出设备）转换成了一台可共享的缓冲输入设备（或输出设备），使用户产生一个"错觉"，好像他们各自都有一台专用的字符设备，从而实现虚拟设备。

简答5什么是死锁？

发生死锁的四个必要条件是？

死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进；

必要条件是:

互斥条件，请求和保持条件，不剥夺条件和环路等待条件。

1.分时系统的特征：

多路性独立性及时性交互性

2.进程是作为分配资源的基本单位，线程是作为独立运行和独立调度的基本单位

3.并发和共享是操作系统的两个最基本的特征。

（虚拟性、异步性）

4.处理机管理的主要功能是创建和撤销进程（线程），对诸进程（线程）的运行进行协调，实现进程（线程）间的信息交流，以及按照一定的算法把处理机分配给进程（线程）。

5.程序顺序执行特征：

顺序性、封闭性、可再现性；程序并发特征：

间断性、失去封闭性、不可再现性

6.前驱图必须不存在循环有向无循环图

7.进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。

PCB是进程存在的唯一标志

8.原子操作是指一个操作所有动作要么全做要么全不做。

是一个不可分割的基本单位，不允许中断，在管态下执行，常驻内存。

9.进程同步两种制约关系：

间接制约（共享某种资源）、直接制约（进程合作）

10.AND同步机制的基本思想：

将进程在整个运行过程中需要的所有资源，一次性全部分配给进程。

嗲进程使用完后一起释放也称wait操作

11.记录型信号量机制遵循“让权等待”原则.

1）消费者和生产者（记录型信号量）

（AND信号量）

2）哲学家进餐问题（记录型信号量）（AND信号量）

3）读者—写者问题（记录型信号量）

（AND型信号量）

4）和尚喝水

12.管道机制必须提供三方面协调能力：

互斥、同步和确定对方是否存在

13.创建进程的过程：

OS发现请求创建调用创建原语、申请空白PCB、分配资源、初始化进程控制块、插入就绪队列。

撤销进程的过程：

从PCB集中检索出PCB读出状态、终止子进程、归还资源、移除PCB

14.同步机构应遵循的基本准则是：

空闲让进、忙则等待、有限等待、让权等待原因：

为实现进程互斥进入自己的临界区。

15.

在生产者消费者问题中，如果缺少了signal（full）戒signal（empty）,对执行结果有何影响？

如果缺少signal（full），那么表明从第一个生产者进程开始就没有改变信号量full值，即使缓冲池产品已满，但full值还是0，这样消费者进程执行wait（full）时认为缓冲池是空而取不到产品，消费者进程一直处于等待状态。

如果缺少signal（empty），在生产者进程向n个缓冲区投满产品后消费者进程才开始从中取产品，这时empty=0，full=n，那么每当消费者进程取走一个产品empty值并不改变，直到缓冲池取空了，empty值也是0，即使目前缓冲池有n个空缓冲区，生产者进程要想再往缓冲池中投放产品也会因为申请不到空缓冲区被阻塞。

16.在生产消费者问题中，如果将两个wait操作即wait（full）和wait（mutex）互换位置，戒者将signal（mutex）不signal（full）互换位置，结果如何？

将wait（full）和wait（mutex）互换位臵后，可能引起死锁。

考虑系统中缓冲区全满时，若一生产者进程先执行了wait（mutex）操作并获得成功，则当再执行wait（empty）操作时，它将因失败而进入阻塞状态，它期待消费者进程执行signal（empty）来唤醒自己，在此之前，它不可能执行signal（mutex）操作，从而使试图通过执行wait（mutex）操作而进入自己的临界区的其他生产者和所有消费者进程全部进入阻塞状态，这样容易引起系统死锁。

若signal（mutex）和signal（full）互换位臵后只是影响进程对临界资源的释放次序，而不会引起系统死锁，因此可以互换位臵。

例1）有两个程序，A程序按顺序使用CPUl0s，使用设备甲5s，使用CPU5s，使用设备乙10s，最后使用CPUl0s。

B程序按顺序使用设备甲10s，他用CPU10s，使用设备乙5s，使用CPU5s，使用设备乙10s。

在顺序环境下先执行A程序再执行B程序，CPU的利用率是多少?

根据题意，A程序的运行时间为：

10+5+5+10+10＝40s，

其中cpu的运行时间为：

10+5+10=25s。

B程序的运行时间为：

10+10+5+5十10=40s，

其中cpu的运行时间为；10+5＝15s。

cpu的利用率为：

（15+25）/（40+40）=50%

2）设有n个进程共享一个程序段，对如下两种情况：

（1）如果每次只允许一个进程进入该程序段；

（2）如果每次最多允许m个进程（M＜＝n）同时进入该程序段。

试问：

所采用的信号量初值是否相同?

信号量值的变化范围如何?

所采用信号量的初值不相同。

在情况

（1）中，信号量的初值为1，

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

semaphore;

s：

=1;

cobegin

begin

P（s）;

过桥；

V（s）

end

Coend

end

5）两个并发进程的程序如下：

若PROCESSA先执行了三个循环后，PROCESSA和PROCESSB又并发执行了一个循环，写出可能出现的打印值。

请用PV操作进行管理，使它们并发执行时不出现与时间有关的错误。

若PR0CESSA先执行了三个循环后，N值变为3+5+5+5＝18；这时PROCESSA和PROCESSB并发执行了一个循环,这时可能出现的情况有以下几种：

（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）桌上有一个空的水果盘，盘中一次只能放一个水果，服务员、男顾客和女顾客共用这个盘子。

服务员向盘中放草莓和香蕉，男顾客专等吃盘中的草莓，女顾客专等吃盘中的香蕉。

规定每次当盘子空时只能放一个水果供顾客食用。

请用信号量机制实现服务员、男顾客和女顾客三个进程的同步。

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.求平均周转时间和平均带权周转时间

平均周转时间：

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：

周期时间单处理机情况下：

需满足下面的限制条件系统才是可调度的：

多处理机系统N表处理机个数

1）最早截止时间优先算法（EDF非抢占式调度方式用于非周期实时任务）

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

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

通常的优先级调度不适用于实时系统

例有两个周期性任务A和B。

A的周期时间为20ms，每个周期的处理时间为10ms。

B的周期时间为50ms，每个周期的处理时间为25ms。

2）最低松弛度优先算法（LLF）用于抢占式调度方式中

松弛度=必须完成时间－需运行时间－当前时间

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

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

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个，试问该系统不会发生死锁的最少资源数是（）

A.9B.10C.11D.12

8）在下列解决死锁的方法中，属于死锁预防策略的是：

A.银行家算法B.资源有序分配法C.死锁检测法D.资源分配图化简法

9）资源的按序分配策略可以破坏（）条件。

A.互斥使用资源B.占有且等待资源C.非抢占资源D.循环等待资源

10）进程的调度方式有两种，一种是（），另一种是（）

11）在（）调度算法中，按照进程进入就绪队列的先后次序来分配处理机。

12）死锁产生的必要条件有四个，即（）、（）、（）、（）。

13）银行家算法中，当一个进程提出的资源请求将导致系统从（）进入（）时，系统就拒绝它的资源请求。

14）对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。

典型的银行家算法是属于（），破坏环路等待条件是属于（），而剥夺资源是（）的基本方法。

15）某分时系统中的进程可能出现如下图所示的状态变化，回答下列问题：

（1）根据图示，该系统采用的是什么进程调度策略？

（2）指出图示中的每一个状态变化的原因。

16）n个进程共享某种资源Ｒ，该资源共有m个可分配单位，每个进程一次一个的申请或释放资源单位。

假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m+n，试证明在这个系统中不可能发生死锁。

设max（i）表示第i个进程的最大资源需求量，need（i）表示第i个进程还需要的资源量，alloc（i）表示第i个进程已分配的资源量。

由题中所给条件可知：

max

（1）+…+max（n）=（need

（1）+…+need（n））+（alloc

（1）+…+alloc（n））

如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，

即alloc

（1）+…+alloc（n）

另一方面所有进程将陷入无限等待状态。

由上述两式可得：

need

（1）+…+need（n）

分析

上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i，need（i）=0，即它已获得了所需要的全部资源。

既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。

17）有一个内存中只能装入两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。

有如下表所示的作业序列，表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高.列出所有作业进入内存的时刻以及结束的时刻。

计算作业的平均周转时间。

10：

00A到达，无竞争，开始运行；

10：

20B到达，进入主存，优先数为3，优于A,B开始运行

10：

30C到达，不可进入；

10：

50B结束，同时D到达，同C争夺内存，D运行时间短，被调度进入内存；A的优先数高，开始运行；

11：

10A结束，C进入内存，C的优先数高于D,开始运行；

12：

00C结束,D开始运行；

12：

20D结束。

平均周转时间=280/4=70分钟

18）在银行家算法中，若出现下述资源分配情：

试问：

⑴该状态是否安全？

⑵若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？

⑴该状态是安全的，因为存在一个安全序列。

下表为该时刻的安全序列表。

⑵若进程P2提出请求Request（1，2，2，2）后，系统不能将资源分配给它，若分配给进程P2，系统还剩的资源情况为（0，4，0，0），此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。

19）某多道程序设计系统配有一台处理器和两台外设IO1、IO2，现有3个优先级由高到低的作业J1、J2和J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是：

（南京大学1999年试题）

J1:

IO2（30ms）,CPU（10ms）,IO1（30ms）,CPU（10ms）.

J2:

IO1（20ms）,CPU（20ms）,IO2（40ms）.

J3:

CPU（30ms）,IO1（20ms）.

处理器调度采用可抢占的优先数算法，忽略其他辅助操作时间，回答下列问题：

（1）分别计算作业J1、J2和J3从开始到完成所用的时间。

（2）3个作业全部完成时CPU的利用率。

（3）3个作业全部完成时外设I01的利用率。

20）假设有4道作业，它们的提交时刻及执行时间由下表给出：

计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序

先来先服务：

1，2，3，4

平均周转时间：

（2+2.8+3.1+3.3）/4=2.8

平均带权周转时间：

（1+2.8/1+31/5+11）/4=5.25

最短作业优先：

1，4，3，2平均周转时间（2+1.8+2.4+3.6）/4=2.45

平均带权周转时间（2+9/5+12/5+18/5）/4=3.85

最高响应比算法：

1，4，3，2R=1+W/T

t1=2执行1

t2=1w2=12-10.2=1.8r2=1+1.8/1=2.8

t3=0.5w3=12-10.4=1.6r3=1+1.6/0.5=4.2

t4=0.3w4=12-10.5=1.5r4=1+1.5/0.3=6执行4

w2=1.8+0.3=2.1r2=1+2.1/1=2.1

w3=1.6+0.3=1.9r3=1+1.9/0.5=4.8执行3，2

平均周转时间同最短作业优先法。

21）设有P1、P2、P3、P4共4个进程同时依次进入就绪队列中，它们需要的处理器时间和优先级别如下所示：

忽略调度所花费的时间，请回答下列问题：

（1）写出分别采用“先来先服务”和“非抢占式的优先数”调度算法选中的进程执行的次序。

（2）在上述两种算法下，分别算出每个进程在就绪队列的等待时间和平均等待时间。

（1）用先来先服务的调度算法时，4个进程的调度次序是P1、P2、P3、P4。

用非抢占式的优先数调度算法时，4个进程的调度次序是P2、P4、P1、P3。

（2）用先来先服务调度算法，每个进程在就绪队列中的等待时间分别为：

P1：

0秒

P2：

0+20=20秒

P3：

0+20+30=50秒

P4：

0+20+30+10=60秒

平均等待时间为：

（0+20+50+60）／4=32.5秒

用非抢占式的优先数调度算法，每个进程在就绪队列中的等待时间分别为；

P1：

30+5=35秒

P2：

0秒

P3：

20+30+5=55秒

P4：

30秒

平均等待时间为：

（35+0+55+30）／4=30秒

22）在单处理器环境下，有4道作业，其进入系统的时间和所需要的执行时间如下所示试分别用“先来先服务”和“非抢占式的优先数”调度算法，求出每个作业的周转时间和平均周转时间

（1）先来先服务调度算法

平均周转时间：

（1.5+1.7+1.4+1.4）/4=1.5

（2）非抢占式的优先数调度算法

平均周转时间：

（1.5+2.3+O.7+0.7）/4=1.3

23）某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见表2.2，此刻系统的可用资源向量为（2,1,2），

①将系