操作系统-例题选讲

计算机操作系统例题选讲

第二章进程管理第三章处理机调度与死锁第四章存储器管理第五章设备管理第六章文件管理1

A、B两个火车站之间是单轨连接的，现有许多列车同时到A站，须经A再到达B站，列车出B站后又可分路行驶。为保证行车安全，请你当调度时，你将如何调度列车？请你用PV操作为工具设计一个能实现你的调度方案的自动调度系统。AB例1：2当A、B两站之间无列车停驶时，可让到达A站的一列车进人A、B站之间行驶。当AB站之间有列车在行驶时，则到达A站者必须在站外等待。当有列车到达B站后，让等在A站外的一列车进入。答：

因此，可用一个信号量S来控制到达A站的列车能否进入单轨道行驶，S的初始值为1。列车到达A站后，先执行P（S），若无列车在A、B站之间行驶，则执行P（S）后立即进人单轨道行驶，到达B站后，执行V（S），可释放一个等待进入的列车进入行驶。若A、B站之间已有列车在行驶，则执行P（S）后就等待，直到行驶者到了B站执行V（S）后释放一个欲进入者。3例2：假设有一个成品仓库，总共能存放8台成品，生产者进程生产产品放入仓库，消费者进程从仓库中取出成品消费。为了防止积压，仓库满时就停止生产。由于仓库搬运设备只有一套，故成品的存入和取出只能分别执行，使用PV操作来实现该方案。答：Varmutex,full,empty:semaphore;mutex:=1;empty:=8;full:=0;4答：processorproducerbegin生产一个成品；P(empty）;P(mutex);将产品存入仓库；V（mutex）;V(full);End;ProcessorconsumerBeginP(full);P(mutex);将产品从仓库取出；V(mutex);V(empty);消费成品；endVarmutex,full,empty:semaphore;mutex:=1;empty:=8;full:=0;5有三个进程R、M、P，它们共享一个缓冲区。R负责从输入设备读信息，每次读出一个记录并把它存放在缓冲区中；M在缓冲区加工读入的记录；P把加工后的记录打印输出。输入的记录经加工输出后，缓冲区中又可存放下一个记录。请用P、V操作为同步机构写出他们并发执行时能正确工作的程序。例3：答：三个进程共用一个缓冲区，他们必须同步工作，可定义三个信号量：

S1：表示是否可把读人的记录放到缓冲区，初始值为1.

S2：表示是否可对缓冲区中的记录加工，初始值为0.

S3：表示记录是否加工好，可以输出，初始值也为0.

三个进程可如下设计：6答：begin

S1，S2，S3：semaphore；

S1：＝l；S2：＝S3：＝0；

cobegin

processR

begin

L1：读记录；

P（S1）；记录存入缓冲区；

V（S2）；

gotoL1；

end；

processM

begin

L2：P（S2）；加工记录；

V（S3）；

gotoL2；

end；

processP

begin

L3：P（S3）；输出加工后的记录；

V（S1）；

gotoL3；

end；

coend；end.7有4个进程R1，R2，W1，W2，它们共享可以存放一个数的缓冲器B.

进程R1每次把从键盘上投入的一个数存放到缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数放到缓冲器B中，供进程W2打印输出。当一个进程把数据存放到缓冲器后，在该数还没有被打印输出之前不准任何进程再向缓冲器中存数。在缓冲器中还没有存入一个新的数之前不允许任何进程从缓冲区中取出打印。问：怎样才能使这四个进程在并发执行是协调的工作？例4：8答：四个进程实际上是两个生产者R1，R2和两个消费者W1，W2，各自生成不同的产品让各自的消费对象去消费，且共享一个的缓冲器。由于缓冲器只能存放一个数，所以，R1和R2在存放数时必须互斥。而R1和W1、R2和W2之间存在同步。为了协调它们的工作可定义三个信号量：

S：表示能否把数存人缓冲器B，初始值为1.

S1：表示R1是否已向缓冲器存入从键盘上读入的一个数，初始值为0.

S2：表示R2是否已向缓冲器存入从磁盘上读入的一个数，初始值为0.9答：begin

S，S1，S2：semaphore；

S：＝1；S1：＝S2：＝0；

cobegin

processR1

xl：integer

begin

L1：从键盘读一个数；

x1：=读入的数；

P（S）；

B：＝xl；

V（S1）；

gotoL1；

end；processR2

x2：integer；

begin

L2：从磁盘读一数；

x2：=读入的数；

P（S）；

B：＝x2；

V（S2）；

gotoL2；

end；processW2

z：integer

begin

L4：P（S2）；

z：=B；

V（S）；打印z中的数；

gotoL4；

end；

coend；cessW1

y：integer；

begin

L3：P（S1）；

y：=B；

V（S）；打印y中的数；

gotoL3；

end；10

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

例5：11Semaphores,mutexab,mutexbaPab：Wait(mutexab)Countab++Ifcountab=1thenwait(s);Signal(mutexab)enter;…..wait(mutexab)countab--;ifcountab=0thensignal(s)signal(mutexab);答：12Pba:wait(mutexba)countba++;Ifcountba=1thenwait(s)signal(mutexba)enter; ……wait(mutexba)countba--;ifcountba=0thensignal(s)signal(mutexba);13例1：假定要在一台处理机上执行下列作业：且假定，这些作业在时刻0以1、2、3、4、5的顺序到达，试完成：

1）给出分别使用FCFS、RR（设T=1）、SJF，以及非抢占优先调度算法时，这些作业的执行顺序。

2）给出上述各算法的平均周转时间和平均带权周转时间。14例2：假设某计算机系统有R1和R2两类可再使用资源（其中R1两个单位，R2一个单位），它们被进程P1和P2所共享，且已知两进程均以如下方式使用资源。申请R1申请R2申请R1释放R1释放R2释放R1试给出系统运行过程中可能到达的死锁点，并画出死锁状态的资源分配图。15例3：试化简下列资源分配图，并利用死锁定理给出相应结论。16例4：某系统有R1、R2、R3公三种资源，在To时刻P1、P2、P3、P4着4个进程对资源的占用和需求情况如表，此时系统可用资源向量为（2，1，2）。

*将系统各资源总数和此刻进程对资源的需求数目用向量表示出来。

*

如此刻P1、P2均发出资源请求Request(1，0，1），为确保系统安全，应如何分配资源。

*

如此刻上述请求得到满足后，系统此刻是否处于死锁状态。17例1某操作系统采用固定分区管理方法，内存分区（以字节为单位）如图。现有大小分别为1K、9K、33K、121K的多个作业要求进入内存，试画出它们进入内存后的空间分配使用情况。18例2某操作系统采用可变分区管理方法，用户区为512K，且始址为0，用空闲分区表管理空闲分区。若分配初始时，用户区空闲，且从低地址端开始分配，则对于下述请求序列：申请300K申请100K释放300K申请150K申请30K申请40K申请60K释放30K

1）分别画出采用首次适应算法、最佳适应算法分配后，存储空间的使用状况。

2）针对上述两种分配结果，如再申请100K，各会出现什么结果？系统应如何解决？19例3：在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中。问该逻辑地址的物理地址是多少？20例4：在一个请求分页存储管理系统中，一个作业的页面走向为：4、3、2、1、4、3、5、4、3、2、1、5，当分配给作业的物理块数分别为3、4时，试计算采用下列淘汰算法时的缺页率，并比较其结果。1）最佳置换淘汰算法（OPT）2）先进先出淘汰算法（FIFO）3）最近最久未用淘汰算法（LRU）结果：8/1210/12LRU10/129/12FIFO6/127/12OPTM=4M=3Belady

现象2122例5：从下列关于存储器管理功能的论述中，选出两条正确的论述。

1）即使在多道程序设计环境下，用户也能设计用内存物理地址直接访问内存的程序。

2）内存分配最基本的任务是为每道程序分配内存空间，其所追求的主要目标是提高存储空间的利用率。

3）为了提高内存保护的灵活性，内存保护通常由软件实现。

4）交换技术已不是现代操作系统中常用的一种技术。

5）地址映射是指将程序空间中的逻辑地址转变为内存空间的物理地址。

6）虚拟存储器是物理上扩充内存容量。

23例8：某系统有同类互斥资源m个，供n个进程共享使用，如果每个进程最多申请x个资源（其中1≤x≤m）。（1）证明：当n(x-1)+1≤m时，系统不会发生死锁；（2）设各进程的最大资源需求量之和为s，证明：当s<m+n时，系统不会发生死锁。24解：（1）因为每个进程最多申请使用x个资源；所以最坏情况下是每个进程都得到了（x-1）个资源，并且现在均申请其所需最后一个资源：即，系统剩余资源数为m-n(x-1)。此时，只要系统至少还有一个资源可以使用，就可以使这n个进程中某个进程得到其所需要的全部资源，继续执行到完成；当它执行完成后释放其所占有的资源，供其它进程使用，因而当m-n(x-1)≥1时，系统不可能发生死锁。即，m-n(x-1)≥1→n(x-1)+1≤m25解：（2）由（1）可知当n(x-1)+1≤m系统不会发生死锁。那么就有nx≤m+n，其中nx是所有进程的最大资源需求量之和，即S，那么就有当s<m+n时系统不会发生死锁。26若磁头的当前位置为100磁道，磁头正向磁道号递增方向移动。现有一磁盘读写请求队列：2337620513219611903892941840若采用FCFS、SSTF、SCAN进行调度，试计算出寻道总跨度及平均跨度各为多少？解答：1）先来先服务FCFS：1596133例127若磁头的当前位置为100磁道，磁头正向磁道号递增方向移动。现有一磁盘读写请求队列：2337620513219611903892941840若采用FCFS、SSTF、SCAN进行调度，试计算出寻道总跨度及平均跨度各为多少？解答：1596133例12）最短寻道时间优先SSFT：70058.328若磁头的当前位置为100磁道，磁头正向磁道号递增方向移动。现有一磁盘读写请求队列：2337620513219611903892941840若采用FCFS、SSTF、SCAN进行调度，试计算出寻道总跨度及平均跨度各为多少？解答：1596133例170058.33）扫描算法SCAN：69257.729例2假定一个磁盘有200个柱面，编号为0－199，在完成了磁道125处的请求后，当前正在磁道143处为一个请求服务。若请求队列的先后顺序为：

86，147，91，177，94，150，102，175，130试分别用FCFS（先来先服务）算法、SSTF（最短寻道时间优先）算法、SCAN