操作系统知识点总结及总复习题库[1].doc - 下载本文

19. 共汽车上,司机和售票员各有各的职责范围。但两者的工作又需要相互配合、协调。问如何通过P/V操作实现司机和售票员的同步操作? 参答:

司机进程: wait(s1) 售票员进程:关车门

↓ ↓ 启动车辆 signal(s1) ↓ ↓ 运行 售票 ↓ ↓ 到站停车 ↓ signal(s2) ↓

wait(s2) ↓ 开车门

↓ 第三章 处理机调度与死锁

知识点:

1. 调度类型:高级调度(又称作业调度,其主要功能是按照某种原则从磁盘某

些盘区的作业队列中选取作业进入主存,并为作业做好运行前的准备工作和作业完成后的善后工作)、低级调度(又称进程调度,其主要功能是按照某种原则将处理机分配给就绪进程)、中级调度(它决定哪些进程被允许参与竞争处理机资源)。

2. 调度算法:先来先服务(FCFS)、短作业优先(SJF)、优先权、高响应比优先

(优先权=1+等待服务时间/要求服务时间)、时间片轮转(T=N/q ; T是系统响应时间,N是进程数,q是时间片)、多级反馈队列。

3. 进程周转时间:从进程进入就绪队列开始,到进程完成为止的时间间隔 4. 平均周转时间:系统中多个进程的周转时间的平均值

5. 死锁的定义:两个或两个以上并发进程,如果每个进程持有某种资源,而又

等待着别的进程释放它或它们现在保持着的资源,否则就不能向前推进。此时,每个进程都占用了一定的资源,但又都不能向前推进。此现象称为死锁。 6. 产生死锁的必要条件:互斥条件、请求和保持条件、不剥夺条件、环路等待

条件。

7. 预防死锁:破坏保持和请求条件、破坏不剥夺条件、破坏环路等待条件。 8. 银行家算法:P书(97)。★ 联系:

1. 请分析响应比高者优先调度算法为何既有利于短作业(进程),又能兼顾长作业(进程)。

(第三章) 参答:

(1)高响应比优先调度算法是一种高优先权优先算法,由于其中的优先权,即响应比的计算为:

响应时间等待时间+要求服务时间tw响应比===1+

要求服务时间要求服务时间ts(2)如果作业(进程)的等待时间相同,则要求服务时间最短的作业(进程)的优先权最

高,因此它有利于短作业(进程)。

(3)如果作业(进程)较长,它的优先权将随着等待时间的增长而提高,从而使长作业(进程)不会长期得不到服务。

2. 设有一组作业若采用短作业优先调度算法,作业的执行顺序是( )。

作业号 1 2 3 4 提交时间 9:00 9:40 9:50 10:10 运行时间 70 30 10 5 3. 有3个作业,分别采用先来先服务和短作业优先调度算法。试问它们的周转时间和平均

周转时间各是多少。 作业号 1 2 提交时间 0 0.4 运行时间 8 4 开始时间 完成时间 周转时间 3 1 1 平均周转时间 4. 某系统有3个作业,系统确定它们在全部到达后,再开始采用响应比高者优先的调度算

法,问它们的调度顺序是什么?各自的周转时间是什么? 作业号 1 2 3 提交时间 8.8 9.0 9.5 运行时间 1.5 0.4 1.0 开始时间 完成时间 周转时间 调度顺序 平均周转时间:

5. 银行家算法(6分)

假定有如下资源分配状态,现可用资源向量为(2,3,0) P0 P1 P2 P3 P4 最大需求资源 已分配资源 A 7 3 9 2 4 B 5 2 0 2 3 C 3 2 2 2 3 A 0 3 3 2 0 B 1 0 0 1 0 C 0 2 2 1 2 Need A B C Work+allo. A B C 问:(1)、该状态是安全状态吗?,若是安全的,请写出它的一个安全序列。

(2)、如果此时P4提出资源请求向量为(1,2,0),系统能否把资源分配给它?为什么?

6. 有五个作业,它们的提交、运行时间如下表所示。

若采用短作业优先调度算法,试填写下试填写答题纸表格的空白处,并计算平均周转时间。列表格的空白处,并计算平均周转时间。

作业号 1 2 3 4 5 提交时间 8.0 8.5 8.8 9.0 9.2 运行时间 1.2 0.7 0.2 2.2 0.4 7. 有五个作业,它们的提交、运行时间如下表所示。若采用响应比高者优先调度算法,试

填写答题纸表格的空白处,并计算平均周转时间。 作业号 1 2 3 4 5

提交时间 8.0 8.5 8.8 9.0 9.2 运行时间 1.2 0.7 0.2 2.2 0.4

第四章 存储器管理

1.

库内存编译程序产生的目标模块装入模块第一步?第二步

2. 页式存储管理的基本思想

分块,把内存存储空间划分成大小一定的块,称为物理块(页框、实页);分页,把用户程序的逻辑地址空间划分成大小一定的块,称为页面(逻辑页、虚页); 对某特定机器,其地址结构是一定的。若给定一个逻辑地址空间中的地址为A,页面的大小为L,则页号P和页内地址d可按下式求得:

?A? P?INT???L?

d?[A]MODL

例:系统地址结构为16位二进制,该地址空间为64K( 216 ,0~65535)。如页面长度为1K(1024)。

现有一相对地址为3000,它的二进制表示如下图,其二元组形式经过计算得到(2,952)

3. 页式存储管理的地址转换

当进程访问某逻辑地址3081时,地址变换过程: (逻辑地址3081 ? 物理地址) ?

逻辑地址3081 ?(页号,页内地址) (3,9) [页面长度1K] ?

比较:页号> 页表长度(页表寄存器中)? 越界中断 n?

表项在页表中位置 = 页表始址+页号×页表项长度 ?

从表项中取得对应该页的物理块号,装入物理地址寄存器

? (第3页面对应块号是11) 逻辑地址寄存器的页内地址?物理地址寄存器的块内地址 ?

物理块号11+ 块内地址9 ? 物理地址[11*1024+9=11273]

链接程序装入程序第三步 4. 虚拟页式存储管理

页号、驻留位、内存块号、外存地址、访问位、修改位 驻留位(中断位):表示该页是在内存还是在外存

访问位:根据访问位来决定淘汰哪页(由不同的算法决定) 修改位:查看此页是否在内存中被修改过

5. 页面淘汰算法

1. 先进先出页面淘汰算法(FIFO):选择在内存中驻留时间最长的页并淘汰之 2. 理想淘汰算法—最佳页面算法(OPT):淘汰以后不再需要的或最远的将来

才会用到的页面

3. 最近最少使用页面淘汰算法(LRU):选择最后一次访问时间距离当前时间

最长的一页并淘汰之,即淘汰没有使用的时间最长的页

练习:

1. 一实现分页式存储管理的系统,内存块大小为2K/块,现有一用户作业,逻

辑地址空间为0~5129字节,若将其装入内存,系统分配给它的存储容量为多少字节?有无碎片,大小为多少?

2. 设一个逻辑地址空间有8个页面,每个页面大小为1024字节,映射到32块

物理块的内存上,问:

(1)逻辑地址要用多少位表示? (2)物理地址要用多少位表示?

3. 已知内存容量为64KB,某一作业A的逻辑地址空间共有4K,分为4个页面,

页面0、1、2、3分别被分配到内存空间的2、4、6、7四个物理块中,在逻辑地址为200处有一条取数指令“LOAD 1,3500”, (1)画出作业A的页表;

(2)当指令“LOAD 1,3500”执行时,产生的物理地址应是什么?

4. 计算缺页次数

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

5,4,3,2,1,5(分别用FIFO、OPT、LRU)

2) 某程序在内存中分配m页初始为空,页面走向为1,2,3,4,1,2,5,1,

2,3,4,5。当m=3,m=4时缺页中断分别为多少?用FIFO算法

3) 已知内存管理采用页式存储管理。某一作业A的地址空间共4K字节,分为

4个页面0、1、2、3,它们被分配到内存的2、3、4、8四个存储块中,在逻辑地址为200中有一条取数指令LOAD 1,3200(十进制),页和块同样大小。完成以下要求: