操作系统题目与答案

某车站售票厅任何时刻最多可容纳20名购票者进入，当售票厅少于20待。若把一个购票者看作一个进程，请回答下列问题：名购票者时，则厅外的购票者可以立即进入，否则需要在外面等

（1）用P，V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。

（2）根据所定义的信号量，把应该执行的P，V操作填入下述程序中，以保证进程能够正确地并发执行。

（3）若欲购票者最多为N个大，写出信号量可能的变化范围（最大值和最小值）

1）定义信号量S，初值为20。

S>0，S的值表示可继续进入售票厅的人数； S=0，表示售票厅已有20名购票者； S<0，|S|的值为等待进入售票厅的人数。 2、COBEGIN PROCESS PI（I=1，2，…） Begin

进入售票厅； 购票；

退出； End COEND

例题：某工厂有一个可以存放设备的仓库，总共可以存放8台设备。生产部门生产的每一台设备都必须入库。销售部门可以从仓库提出设备供应客户。设备的入库和出库都必须借助运输工具。现只有一套运输工具，每次只能运输一台设备。请设计一个能协调工作的调度管理系统。

（1）定义信号量，说明各信号量的含义并赋初值： mutex，full，empty：semaphore;

mutex：=1;运输工具是否空闲，初值为1

empty：=8;仓库中尚可存放多少设备，初值为8 full：＝0;仓库中的设备数，初值为0 （2）PV操作实现如下 begin

mutex，full，empty：semaphore; mutex：=1;empty：=8;full：＝0; cobegin．

processor producerprocessor consumer beginbegin

生产设备； P（full）;

P（empty）; P（mutex）; P（mutex）;将设备从仓库取出； 将设备送入仓库； V（mutex）; V（mutex）; V（empty）; V（full）;把设备销售给用户； end;end; coend; end．

例题：设在公共汽车上，司机和售票员的活动分别是：司机：启动车辆，正常行车，到站停车。售票员：上乘客，关车门，售票，开车门，下乘客。用PV操作对其控制。

解答：由于司机与售票员之间要互通消息，司机进程设置一个私有信号量run，用于判断司机能否进行工作，初值为0。售票员进程设置一个私有信号量stop，用于判断是否停车，售票员是否能够开车门，初值为0。 driver: begin L1: P(run); 启动车辆； 正常行车； 到站停车； V(stop); goto L1; end;

conductor:begin

L2:上乘客；关车门； V(run); 售票； P(stop);

开车门；下乘客； goto L2; end;

证明题:在后备队列中等待运行的同时有3个作业1,2,3，已知它们各自的运行时间为a,b,c且满足关系a

证明：不失一般性，假设调度的顺序为2，1，3，则此时的平均周转时间：

T1=[b+(b+a)+(b+a+c)]/3=(2a+3b+c)/3

若采用SJF，则此时的调度的顺序为1，2，3，平均周转时间： T2=[a+(a+b)+(a+b+c)]/3=(3a+2b+c)/3 T2-T1=(a-b)/3,

因为a

作业调度与进程调度的联系和区别

对处理机的分配在逻辑上是分两级进行的，第一级是宏观调度，又称作业调度，第二级是微观调度，又称进程调度；作业调度是从后备作业选取一道或几道作业进入主存，分配必要的资源，变为执行状态，作业被调度时，系统为它创建一个进程，初始为就绪状态；进程调度的任务是在进入内存的所有进程中，确定哪个进程在什么时候获得处理机，使用多长时间等。

处理机调度分的三个层次及其功能

高级调度即作业调度：选中一个作业且把它装入主存储器，为该作业创建一个用户进程并分配必要资源，将其排入就绪队列。这些进程将在进程调度的控制下占有处理器运行。

进程调度功能是按照某种原则决定就绪队列中的哪个进程能获得处理器, 并将处理机出让给它进行工作。

中级调度决定那些进程被允许参与竞争处理器资源。

例题：有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3。 （1）若对资源分配不加限制，会发生什么情况？为什么？

（2）为保证进程正确工作，应采用怎样的资源分配策略？为什么？

（1）可能会发生死锁，例如：进程P1、P2和P3分别获得资源S3、S1和S2后再继续申请资源时都要等待，这是循环等待（进程在等待新源时均不释放已占资源）；

（2）可有几种答案：A、采用静态分配，由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象（或不会出现循环等待资源现象）；或B、采用按序分配，不会出现循环等待资源现象；或C、采用银行家算法，因为在分配时，保证了系统处于安全状态。

死锁防止与死锁避免的区别

死锁防止是系统预先确定一些资源分配策略，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁发生

死锁避免是当进程提出资源申请时系统测试资源分配，仅当能确保系统安全时才把资源分配给进程，使系统一直处于安全状态之中，从而避免死锁

设一个逻辑空间有16个页面，每页大小为2048B，逻辑地址需要多少位表示？ 解答：由题义：页面数为16，故需要4位二进制数表示；每页有2048B，故页内地址需要11位二进制数表示；逻辑地址由页号和页内地址组成，所以需要4+11=15位二进制数表示。

某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。

实现Spooling系统必须设计哪些程序？它们的功能是什么？

Spooling系统由三部分程序组成，即预输入程序、实现输入井读和输出井写的井管理程序、缓输出程序。在作业执行前，操作系统已将作业信息通过独占设备预先输入到辅助存储器上存放，称为预输入，此后，作业执行使用数据时不必再启动独占设备输入，而只要从辅助存储器上输入。另一方面，作业执行中也不必直接启动独占设备输出数据，而只要将输出数据写入辅助存储器。由操作系统来组织信息的输出，称为缓输出。

例题：已知某磁盘的进程访问磁道的序列为55、58、39、18、90、160、150、38、184；当前磁头的位置在100号磁道，由48磁道而来；求SSTF算法和SCAN算法的平均寻道长度。

SSTF算法：存取臂移动顺序为90,58,55,39,38,18,150,160,184 平均寻道长度：（10+32+3+16+1+20+132+10+24）/9=248/9=27.6道； SCAN算法：存取臂移动顺序为150,164,184,90,58,55,39,38,18 平均寻道长度：（50+14+20+94+32+3+16+1+2）/9=250/9=27.8道。

SPOOLing系统及其组成

1）联机情况下实现的同时外围操作称为SPOOLing(SimultaneausPeriphernal Operating On-Line)，或称为假脱机操作（2分）。为了缓和CPU的高速性与I/O设备低速性间的矛盾而引入了脱机输入、脱机输出技术。

2）Spooling系统由三部分程序组成，即预输入程序、井管理程序、缓输出程序。（3分

例题：画出以下目录结构：根目录下有三个目录A、B、C；A目录下有目录D，目录D下有文件E和文件F，B目录下有目录H，目录H下有文件G和文件I；（2）现目录D要共享文件I应如何实现？ （1）目录结构如下图所示。

（2）绕道法：经目录A、根目录、目录B、目录H、文件Ｉ。 链接法：在目录D下面建立一个链接文件直接指向文件I。

常用的目录结构形式及各自的优点

1）单级目录结构：单级目录的优点是简单且能实现目录管理的基本功能——按名存取；

2）两级目录结构：提高了检索目录的速度、在不同的用户目录中可以使用相同的文件名、不同用户还可使用不同的文件名来访问系统中的同一个共享文件；

3）多级目录结构：查询速度更快，同时层次结构更加清晰，能够更加有效地进行文件的管理和保护。

文件的保护和文件的保密的区别

文件的保护：为了防止在使用文件时破坏文件以及限制对文件的访问，可对每个文件（目录）规定使用权限；为了防止系统故障、意外事故对文件造成的破坏，最可靠的方法是定期备份; 文件的保密：为了防止他人窃取文件（内容），一种方法是为文件设置访问口令，另一种方法是对文件的内容进行加密，以密文的形式保存，使用时再解密。

用户可以对文件施加的基本操作 1）创建文件 2）删除文件 3）读/写文件

4）设置文件的读/写位置 5）撤销文件