操作系统-例题选讲

1、操作系统操作系统 - - 例题选讲例题选讲1计计 算算 机机 操操 作作 系系 统统例题选讲例题选讲 第二章第二章 进程管理进程管理 第三章第三章 处理机调度与死锁处理机调度与死锁 第四章第四章 存储器管理存储器管理 第五章第五章 设设 备备 管管 理理 第六章第六章 文件管理文件管理 操作系统操作系统 - - 例题选讲例题选讲2 A、B两个火车站之间是单轨连接的，现有许多列车两个火车站之间是单轨连接的，现有许多列车同时到同时到A站，须经站，须经A再到达再到达B站，列车出站，列车出B站后又可分路行站后又可分路行驶。为保证行车安全，请你当调度时，你将如何调度列驶。为保证行车安全，请你当调度时，你

2、将如何调度列车？请你用车？请你用PV操作为工具设计一个能实现你的调度方案操作为工具设计一个能实现你的调度方案的自动调度系统。的自动调度系统。 AB例例1：操作系统操作系统 - - 例题选讲例题选讲3 当当A、B两站之间无列车停驶时，可让到达两站之间无列车停驶时，可让到达A站的一列车进站的一列车进人人A、B站之间行驶。站之间行驶。 当当AB站之间有列车在行驶时，则到达站之间有列车在行驶时，则到达A站者必须在站外等站者必须在站外等待。待。 当有列车到达当有列车到达B站后，让等在站后，让等在A站外的一列车进入。站外的一列车进入。答：答： 因此因此，可用一个信号量，可用一个信号量S来控制到达来控制到达

3、A站的列车能否进入站的列车能否进入单轨道行驶，单轨道行驶，S的初始值为的初始值为1。 列车到达列车到达A站后，先执行站后，先执行P（S），），若无列车在若无列车在A、B站之站之间行驶，则执行间行驶，则执行P（S）后立即进人单轨道行驶，到达）后立即进人单轨道行驶，到达B站后，站后，执行执行V（S），），可释放一个等待进入的列车进入行驶。可释放一个等待进入的列车进入行驶。 若若A、B站之间已有列车在行驶，则执行站之间已有列车在行驶，则执行P（S）后就等待，后就等待，直到行驶者到了直到行驶者到了B站执行站执行V（S）后释放一个欲进入者。后释放一个欲进入者。 操作系统操作系统 - - 例题选讲例题选讲

4、4例例2： 假设有一个成品仓库，总共能存放假设有一个成品仓库，总共能存放8台成品，生产者台成品，生产者进程生产产品放入仓库，消费者进程从仓库中取出成品消进程生产产品放入仓库，消费者进程从仓库中取出成品消费。为了防止积压，仓库满时就停止生产。由于仓库搬运费。为了防止积压，仓库满时就停止生产。由于仓库搬运设备只有一套，故成品的存入和取出只能分别执行，使用设备只有一套，故成品的存入和取出只能分别执行，使用PV操作来实现该方案。操作来实现该方案。 答：答：Var mutex,full,empty:semaphore;mutex:=1;empty:=8;full:=0;操作系统操作系统 - - 例题选讲

5、例题选讲5答：答：processor producerbegin生产一个成品；生产一个成品；P(empty）;P(mutex);将产品存入仓库；将产品存入仓库；V（mutex）;V(full);End; Processor consumerBeginP(full);P(mutex);将产品从仓库取出；将产品从仓库取出；V(mutex);V(empty);消费成品；消费成品；endVar mutex,full,empty:semaphore;mutex:=1;empty:=8;full:=0;操作系统操作系统 - - 例题选讲例题选讲6 有三个进程有三个进程R、M、P，它们共享一个缓冲区。，它们

6、共享一个缓冲区。R负责从输负责从输入设备读信息，每次读出一个记录并把它存放在缓冲区中；入设备读信息，每次读出一个记录并把它存放在缓冲区中；M在缓冲区加工读入的记录；在缓冲区加工读入的记录；P把加工后的记录打印输出。输入的把加工后的记录打印输出。输入的记录经加工输出后，缓冲区中又可存放下一个记录。请用记录经加工输出后，缓冲区中又可存放下一个记录。请用P、V操作为同步机构写出他们并发执行时能正确工作的程序。操作为同步机构写出他们并发执行时能正确工作的程序。例例3：答：答： 三个进程共用一个缓冲区，他们必须同步工作，可定义三个进程共用一个缓冲区，他们必须同步工作，可定义三个信号量：三个信号量：S1：

7、表示是否可把读人的记录放到缓冲区，初始值为：表示是否可把读人的记录放到缓冲区，初始值为1. S2：表示是否可对缓冲区中的记录加工，初始值为：表示是否可对缓冲区中的记录加工，初始值为0.S3：表示记录是否加工好，可以输出，初始值也为：表示记录是否加工好，可以输出，初始值也为0. 三个进程可如下设计：三个进程可如下设计： 操作系统操作系统 - - 例题选讲例题选讲7答：答：beginS1，S2，S3：semaphore；S1：l；S2：S3：0；cobeginprocess RbeginL1：读记录；：读记录；P（S1）；）；记录存入缓冲区；记录存入缓冲区；V（S2）；goto L1；end；pr

8、ocess Mbegin L2： P（S2）；加工记录；加工记录；V（S3）；goto L2；end；process Pbegin L3： P（S3）；输出加工后的记录；输出加工后的记录；V（S1）；goto L3；end；coend；end.操作系统操作系统 - - 例题选讲例题选讲8 有有4个进程个进程R1，R2，W1，W2，它们共享可以存放一个，它们共享可以存放一个数的缓冲器数的缓冲器B. 进程进程R1每次把从键盘上投入的一个数存放到缓冲器每次把从键盘上投入的一个数存放到缓冲器B中，中，供进程供进程W1打印输出；打印输出； 进程进程R2每次从磁盘上读一个数放到缓冲器每次从磁盘上读一个数放

9、到缓冲器B中，供进程中，供进程W2打印输出。打印输出。 当一个进程把数据存放到缓冲器后，在该数还没有被打当一个进程把数据存放到缓冲器后，在该数还没有被打印输出之前不准任何进程再向缓冲器中存数。印输出之前不准任何进程再向缓冲器中存数。 在缓冲器中还没有存入一个新的数之前不允许任何进程在缓冲器中还没有存入一个新的数之前不允许任何进程从缓冲区中取出打印。从缓冲区中取出打印。 问：怎样才能使这四个进程在并发执行是协调的工作？问：怎样才能使这四个进程在并发执行是协调的工作？ 例例4：操作系统操作系统 - - 例题选讲例题选讲9答：答： 四个进程实际上是两个生产者四个进程实际上是两个生产者 R1，R2和两

10、个消费和两个消费者者 W1，W2，各自生成不同的产品让各自的消费对象，各自生成不同的产品让各自的消费对象去消费，且共享一个的缓冲器。去消费，且共享一个的缓冲器。 由于缓冲器只能存放一个数，所以，由于缓冲器只能存放一个数，所以，R1和和R2在存在存放数时必须互斥。而放数时必须互斥。而R1和和W1、R2和和W2之间存在同步。之间存在同步。 为了协调它们的工作可定义三个信号量：为了协调它们的工作可定义三个信号量：S：表示能否把数存人缓冲器：表示能否把数存人缓冲器B，初始值为，初始值为1.S1：表示：表示R1是否已向缓冲器存入从键盘上读入的是否已向缓冲器存入从键盘上读入的一个数，初始值为一个数，初始值

11、为0.S2：表示：表示R2是否已向缓冲器存入从磁盘上读入的是否已向缓冲器存入从磁盘上读入的一个数，初始值为一个数，初始值为0.操作系统操作系统 - - 例题选讲例题选讲10答：答：beginS，S1，S2：semaphore；S：1；S1：S2：0；cobeginprocess R1xl ：integerbeginL1：从键盘读一个数；：从键盘读一个数；x1：=读入的数；读入的数；P（S）；B：xl；V（S1）；goto L1；end；process R2x2：integer；beginL2：从磁盘读一数；：从磁盘读一数；x2：=读入的数；读入的数；P（S）；B：x2；V（S2）；goto L

12、2；end；process W2z：integerbeginL4：P（S2）；z：=B；V（S）；打印打印z中的数；中的数；goto L4；end；coend；cess W1y：integer；beginL3：P（S1）；y：=B；V（S）；打印打印y中的数；中的数；goto L3；end；操作系统操作系统 - - 例题选讲例题选讲11 a、b 两点间是一段东西向的单行车道，现要设计两点间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：一个自动管理系统，管理规则如下： 当当ab间有车辆在行驶时同方向的车可以同时驶入间有车辆在行驶时同方向的车可以同时驶入ab段，但另

13、一方向的车必须在段，但另一方向的车必须在ab段外等待；段外等待； 当当ab之间无车时，到达之间无车时，到达a（或（或b）的车辆可以进入）的车辆可以进入ab段，但不能从段，但不能从a，b点同时驶入；点同时驶入； 当某方向在当某方向在ab段行驶的车辆使出了段行驶的车辆使出了ab段且无车辆进段且无车辆进入入ab段时，应让另一方向等待的车辆进入段时，应让另一方向等待的车辆进入ab段行驶。段行驶。 请用请用wait、signal工具对工具对ab段实现正确管理。段实现正确管理。 例例5：操作系统操作系统 - - 例题选讲例题选讲12Semaphore s, mutexab,mutexbaPab：Wait(

14、mutexab)Countab+If countab=1 then wait(s);Signal(mutexab)enter; .wait(mutexab)countab- -;if countab=0 then signal(s)signal(mutexab);答：答：操作系统操作系统 - - 例题选讲例题选讲13Pba:wait(mutexba)countba+;If countba=1 then wait(s)signal(mutexba)enter;wait(mutexba)countba-;if countba=0 then signal(s)signal(mutexba);操作系统

15、操作系统 - - 例题选讲例题选讲14例例1： 假定要在一台处理机上执行下列作业：假定要在一台处理机上执行下列作业：且假定，这些作业在时刻且假定，这些作业在时刻0以以1、2、3、4、5的顺序的顺序到达，试完成：到达，试完成： 1）给出分别使用）给出分别使用FCFS、RR（设（设T=1）、）、SJF，以及非抢占优先调度算法时，这些作业的执行顺序。以及非抢占优先调度算法时，这些作业的执行顺序。 2）给出上述各算法的平均周转时间和平均带权周）给出上述各算法的平均周转时间和平均带权周转时间转时间。操作系统操作系统 - - 例题选讲例题选讲15例例2： 假设某计算机系统有假设某计算机系统有R1和和R2两

16、类可再使用资源两类可再使用资源（其中（其中R1两个单位，两个单位，R2一个单位），它们被进程一个单位），它们被进程P1和和P2所共享，且已知两进程均以如下方式使用资源。所共享，且已知两进程均以如下方式使用资源。申请申请R1申请申请R2申请申请R1释放释放R1释放释放R2释放释放R1 试给出系统运行过程中可能到达的死锁点，并画试给出系统运行过程中可能到达的死锁点，并画出死锁状态的资源分配图出死锁状态的资源分配图。操作系统操作系统 - - 例题选讲例题选讲16例例3： 试化简下列资源分配图试化简下列资源分配图，并利用死锁定理给出相，并利用死锁定理给出相应结论应结论。操作系统操作系统 - - 例题选

17、讲例题选讲17例例4： 某系统有某系统有R1、R2、R3公三种资源，在公三种资源，在To时刻时刻P1、P2、P3、P4着着4个进程对资源的占个进程对资源的占用和需求情况如表，用和需求情况如表，此时系统可用资源向此时系统可用资源向量为（量为（2，1，2）。）。 * * 将系统各资源总数和此刻进程对资源的需求数目用向将系统各资源总数和此刻进程对资源的需求数目用向量表示出来。量表示出来。 * * 如此刻如此刻P1P1、P2P2均发出资源请求均发出资源请求Request(1Request(1，0 0，1 1），），为确保系统安全，应如何分配资源。为确保系统安全，应如何分配资源。 * * 如此刻上述请求

18、得到满足后，系统此刻是否处于死锁如此刻上述请求得到满足后，系统此刻是否处于死锁状态状态。操作系统操作系统 - - 例题选讲例题选讲18例例1 某操作系统采用固定分某操作系统采用固定分区管理方法，内存分区（以区管理方法，内存分区（以字节为单位）如图。现有大字节为单位）如图。现有大小分别为小分别为1K1K、9K9K、33K33K、121K121K的多个作业要求进入内存，的多个作业要求进入内存，试画出它们进入内存后的空试画出它们进入内存后的空间分配使用情况。间分配使用情况。操作系统操作系统 - - 例题选讲例题选讲19例例2 某操作系统采用可变分区管理方法，用户区为某操作系统采用可变分区管理方法，用

19、户区为512K512K，且始址为，且始址为0 0，用空闲分区表管理空闲分区。若，用空闲分区表管理空闲分区。若分配初始时，用户区空闲，且从低地址端开始分配，分配初始时，用户区空闲，且从低地址端开始分配，则对于下述请求序列：则对于下述请求序列：申请申请300K300K申请申请100K100K释放释放300K300K申请申请150K150K申请申请30K30K申请申请40K40K申请申请60K60K释放释放30K30K 1 1）分别画出采用首次适应算法、最佳适应算法分配）分别画出采用首次适应算法、最佳适应算法分配后，存储空间的使用状况。后，存储空间的使用状况。 2 2）针对上述两种分配结果，如再申请

20、）针对上述两种分配结果，如再申请100K100K，各会出，各会出现什么结果？系统应如何解决？现什么结果？系统应如何解决？操作系统操作系统 - - 例题选讲例题选讲20例例3 3： 在一分页存储管理系统中，逻辑地址长度为在一分页存储管理系统中，逻辑地址长度为1616位，页面大小为位，页面大小为40964096字节，现有一逻辑地址为字节，现有一逻辑地址为2F6AH2F6AH，且第，且第0 0、1 1、2 2页依次存放在物理块页依次存放在物理块5 5、1010、1111中。问该逻辑地址的物理地址是多少？中。问该逻辑地址的物理地址是多少？操作系统操作系统 - - 例题选讲例题选讲21例例4： 在一个请

21、求分页存储管理系统中，一个作业的页面在一个请求分页存储管理系统中，一个作业的页面走向为：走向为：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

22、= 3Belady现象现象操作系统操作系统 - - 例题选讲例题选讲22操作系统操作系统 - - 例题选讲例题选讲23例例5： 从下列关于存储器管理功能的论述中，选出两条从下列关于存储器管理功能的论述中，选出两条正确的论述。正确的论述。 1）即使在多道程序设计环境下，用户也能设计）即使在多道程序设计环境下，用户也能设计用内存物理地址直接访问内存的程序用内存物理地址直接访问内存的程序。 2）内存分配最基本的任务是为每道程序分配内存）内存分配最基本的任务是为每道程序分配内存空间，其所追求的主要目标是提高存储空间的利用率。空间，其所追求的主要目标是提高存储空间的利用率。 3）为了提高内存保护的灵活性

23、，内存保护通常由）为了提高内存保护的灵活性，内存保护通常由软件实现软件实现。 4）交换技术已不是现代操作系统中常用的一种技）交换技术已不是现代操作系统中常用的一种技术术。 5）地址映射是指将程序空间中的逻辑地址转变）地址映射是指将程序空间中的逻辑地址转变为内存空间的物理地址。为内存空间的物理地址。 6）虚拟存储器是物理上扩充内存容量）虚拟存储器是物理上扩充内存容量。 操作系统操作系统 - - 例题选讲例题选讲24例例8： 某系统有同类互斥资源某系统有同类互斥资源m个，供个，供n个进程共享使用，个进程共享使用，如果每个进程最多申请如果每个进程最多申请x个资源（其中个资源（其中1xm）。）。 （1

24、）证明：当）证明：当n(x-1)+1m时，系统不会发生死锁；时，系统不会发生死锁；（2）设各进程的最大资源需求量之和为）设各进程的最大资源需求量之和为s，证明：当，证明：当sm+n时，系统不会发生死锁。时，系统不会发生死锁。操作系统操作系统 - - 例题选讲例题选讲25解解：（1）因为每个进程最多申请使用）因为每个进程最多申请使用x个资源；个资源； 所以最坏情况下是每个进程都得到了（所以最坏情况下是每个进程都得到了（x-1）个资）个资源，并且现在均申请其所需最后一个资源：源，并且现在均申请其所需最后一个资源： 即，系统剩余资源数为即，系统剩余资源数为m-n(x-1)。 此时，只要系统至少还有一

25、个资源可以使用，就可此时，只要系统至少还有一个资源可以使用，就可以使这以使这n个进程中某个进程得到其所需要的全部资源，个进程中某个进程得到其所需要的全部资源，继续执行到完成；当它执行完成后释放其所占有的资源，继续执行到完成；当它执行完成后释放其所占有的资源，供其它进程使用，因而当供其它进程使用，因而当m-n(x-1)1时，系统不可能发时，系统不可能发生死锁。生死锁。 即，即，m-n(x-1)1 n(x-1)+1m 操作系统操作系统 - - 例题选讲例题选讲26解解：（2）由（）由（1）可知当）可知当n(x-1)+1m系统不会发生死锁。系统不会发生死锁。 那么就有那么就有nxm+n，其中，其中n

26、x是所有进程的最大资源是所有进程的最大资源需求量之和，即需求量之和，即S，那么就有当，那么就有当sm+n时系统不会发生时系统不会发生死锁。死锁。操作系统操作系统 - - 例题选讲例题选讲27 若磁头的当前位置为若磁头的当前位置为100磁道，磁头正向磁道号递增磁道，磁头正向磁道号递增方向移动。现有一磁盘读写请求队列：方向移动。现有一磁盘读写请求队列：23 376 205 132 19 61 190 389 29 4 18 40若采用若采用FCFS、SSTF、SCAN 进行调度，试计算出寻道进行调度，试计算出寻道总跨度及平均跨度各为多少？总跨度及平均跨度各为多少？解答解答：1）先来先服务）先来先服

27、务FCFS：1596133例例1操作系统操作系统 - - 例题选讲例题选讲28 若磁头的当前位置为若磁头的当前位置为100磁道，磁头正向磁道号递增磁道，磁头正向磁道号递增方向移动。现有一磁盘读写请求队列：方向移动。现有一磁盘读写请求队列：23 376 205 132 19 61 190 389 29 4 18 40若采用若采用FCFS、SSTF、SCAN 进行调度，试计算出寻道进行调度，试计算出寻道总跨度及平均跨度各为多少？总跨度及平均跨度各为多少？解答解答：1596133例例12）最短寻道时间优先）最短寻道时间优先SSFT：70058.3操作系统操作系统 - - 例题选讲例题选讲29 若磁头的当前位置为若磁头的当前位置为100磁道，磁头正向磁道号递增磁道，磁头正向磁道号递增方向移动。现有一磁盘读写请求队列：方向移动。现有一磁盘读写请求队列：23 376 205 132 19 61 190 389 29 4 18 40若采用若采用FCFS、SSTF、SCAN 进行调度，试计算出寻道进行调度，试计算出寻道总跨度及平均跨度各为多少？总跨度及平均跨度各为多少？解答解答：1596133例例170058.33）扫描算法）扫描算法SCAN：69257.7操作系统操作系统 - - 例题选讲例题选讲30例例2 假定一个磁盘有假定一个磁盘有200个柱面，编号为个柱面，编号为0199，在完