考题
-
单项选择题：
- 习题集中的选择部分
-
简答题：
-
进程与线程的关系与区别
-
线程与进程的关系
- 一个进程可以有多个线程，但至少有一个线程；而一个线程只能在一个进程的地址空间内活动。
- 资源分配给进程，同一个进程的所有线程共享该进程所有资源。
- CPU 分配给线程，即真正在处理器运行的是线程。
- 线程在执行过程中需要协作同步，不同进程的线程间要利用消息通信的办法实现同步。
-
进程和线程的比较
- 调度性：在传统的操作系统中，拥有资源的基本单位和独立调动、分派的基本单位都是进程，在引入线程的 OS 中，则把线程作为调度和分派的基本单位，而把进程作为资源拥有（分配）的基本单位
- 并发性：在引入线程的 OS 中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可并发执行，因而使 OS 具有更好的并发性
- 拥有资源：无论是传统的操作系统还是引入线程的操作系统，进程始终是拥有资源的一个基本单位，而线程除了拥有一点在运行时必不可少的资源外，本身基本不拥有系统资源，但它可以访问其隶属进程的资源。
- 系统开销：由于创建、撤销和切换进程时所付出的开销将显著地大于线程。
-
-
分页式管理、页表项的组成和含义
- 页表由页表项组成，页表项由多个域组成，如下图：
各域含义与作用：
- 高速缓存禁止位：通过此位设置，可以禁止将页面缓冲到 CACHE
- 访问位：系统在该页面被访问时设置该位，它的值被用来帮助 OS 在发生缺页中断时选择要被淘汰的页面。
- 修改位：在写入一页时由硬件自动设置。该为在 OS 重新分配页框（内存块）时有用，如果一个页面被修改过，则必须写回磁盘。
- 保护位：该位作用是指出对该页的读、写、执行权限
- 在/不在位：这一位是 1 时表示该页表项是有效的，可以使用。如果是 0，则表示该表项对应的虚拟页面不在内存中，访问该页面会引起缺页中断。
- 页框号：物理内存页的编号。
页表的作用是实现从页号到物理块号的地址映射。
- 页表由页表项组成，页表项由多个域组成，如下图：
-
虚拟存储器原理与应用
- 定义：所谓虚拟存储器， 是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。
- 特征：离散性、多次性、对换性、虚拟性
- 虚拟存储器基于程序局部性原理
- 程序局部性原理，是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。局部性原理又表现为：时间局部性和空间局部性。
- CACHE（高速缓冲存储器）、页面工作集置换算法、虚拟存储器管理都是程序局部性原理的具体应用例子。
-
进程的特征
- 动态性：进程是程序的一次运行过程，有生命周期。
- 并发性
- 独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位
- 异步性：进程按各自独立的
-
-
计算与分析题
-
调度算法
-
先来先服务 FCFS —— 根据进程请求访问磁盘的先后次序进行调度。
-
最短寻道时间优先 SSTF —— 选择有距当前磁头所在磁道最近的访问磁道的进程。
-
LOOK 算法 —— 电梯调度算法 —— 选择与当前磁头移动方向一致且距离最近的进程。
-
循环扫描 (CSCAN) 算法 —— 规定磁头单向移动，如果只是从里向外移动，当磁头移到最外的磁道并访问时，磁头立即返回到最里的欲访问磁道，即将最小磁道号紧接着最大磁道号循环，进行循环扫描。
-
习题集第四部分
-
选择题 26、27、28
-
假设磁头当前位于第 105 道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为 35、45、12、68、 110、180、170、195。采用 SCAN 调度(电梯调度)算法得到的磁道访问序列是( A)。
A. 110、170、180、195、68、45、35、12 B. 110、68、45、35、12、170、180、195
C. 110、170、180、195、12、35、45、68 D. 12、35、45、68、110、170、180、195 -
设磁盘的 I/O 请求队列中的柱面号为 19、376、205、134、18、56、193、396、29、3、19、40，磁头的起始位 置为 100，若采用 SCAN(电梯调度)算法(磁头的运行方向是向内的(本注:柱面号减少方向)，则磁头移动 ( C )个磁道。
A. 205 B. 480 C. 490 D. 512
解：
// 寻道顺序为:100、56、40、29、19、18、3、134、193、205、376、396，移动 磁道次数分别为 44、16、11、10、1、15、131、59、12、171、20，总数为 490。
// 另解: 100→3→396，移动: (100-3)+(396-3)=490 -
设磁盘的 I/O 请求队列中的柱面号为 55、58、39、18、90、160、150、38、184，磁头的起始位置为 100，若 采用 SSTF(最短寻道时间优先)算法，则磁头移动( D )个磁道。
A. 55 B. 184 C. 200 D. 248
解：
//寻道顺序为:100、90、58、55、39、38、18、150、160、184，移动磁道次数分 别为 10、32、3、16、1、20、132、10、24，总数为 248。
//另解:100→18→184，移动:(100-18)+(184-18)=248
-
-
综合应用题 9
-
若磁头的当前位置为 100 磁道，磁头正向磁道号增加方向移动。现有一个磁盘读写请求队列:23、376、205、132、19、61、190、398、29、4、18、40。若采用先来先服务、最短寻道时间优先和扫描算法，试计算出平均寻道长度各为多少?
- 先来先服务算法:移动磁道数总数为 1596，平均寻道长度为 133
- 最短寻道时间优先:移动磁道总数为 700，平均寻道长度为 58.3
- 扫描算法:移动磁道总数为 692，平均寻道长度为 57.7
-
-
-
-
-
缓冲技术
-
习题集第五部分
-
引入缓冲技术的目的
- 缓和 CPU 与 I/O 设备间速度不匹配的矛盾
- 减少对 CPU 的中断频率，放宽对中断响应时间的限制
- 提高 CPU 与 I/O 设备之间的并行性
-
缓冲池(理解为更大的缓冲区)
- 组成
- 空白缓冲队列（emq）
- 由空缓冲区链接而成 F(emq)，L(emq)分别指向该队列首尾缓冲区
- 输入队列（inq）
- 由装满输入数据的缓冲区链接而成 F(inq)，L(inq)分别指向该队列首尾缓冲区
- 输出队列（outq）
- 由装满输出数据的缓冲区链接而成 F(outq)， L(outq)分别指向该队列首尾缓冲
- 空白缓冲队列（emq）
- Getbuf 和 Putbuf 过程
- 收容：缓冲池接收外界数据
- 提取：外界从缓冲池获得数据
- 缓冲区工作方式（从缓冲区的角度来看）
- 收容输入
- 提取输入
- 收容输出
- 提取输出
- 组成
-
单缓冲区 —— 即在 CPU 计算的时候，将数据数据输入到缓冲区(大小取决与 T 和 C 的大小)
-
双缓冲区 —— 即允许 CPU 连续工作（T 不断）
-
环形缓冲区（专为生产者和消费者打造）
- 组成
- 多个缓冲区
- 多个指针
- 使用
- Getbuf 过程
- Releasebuf 过程
- 同步问题
- 组成
-
选择题 16、17、18
-
设从磁盘将一块数据传送到缓冲区所用时间为 80us，将缓冲区中数据传送到用户区所用时间为 40us，CPU 处 理一块数据所用时间为 30us。如果有多块数据需要处理，并采用单缓冲区传送某磁盘数据，则处理一块数据 所用总时间为( A )。
A. 120us B. 110us C. 150us D. 70us
解：
// 并行:设备到缓冲区与 CPU 处理数据(用户程序读数据进行计算)。所以系统处 理一块数据所用的 -
某操作系统采用双缓冲区传送磁盘上的数据。设从磁盘将数据传送到缓冲区所用的时间为T1，将缓冲区中数据传送到用户区所用时间为 T2(假设 T2 远小于 T1)，CPU 处理数据所用时间为 T3，则处理该数据，系统所用总 时间为( D )。
A. T1+T2+T3 B. MAX(T2,T3)+T1 C. MAX(T1,T3)+T2 D. MAX(T1,T3)
解：
// 如果 T3>T1，CPU 处理数据速度(T3)慢于传输速度(T1+T2);
// 如果 T3<T1，设备到缓冲区速度(T1)慢于缓冲区到用户区及 CPU 处理速度(T2+T3)
// 本注:
// 当 T1>T3 时，第 1 块结束->第 2 块结束用时:T1
// 当 T1<T3 时，第 1 块结束->第 2 块结束用时:T3
-
某文件 10 个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送到用户区进行分析。假设一个缓冲区与 一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为 100us，将缓冲区的数据传送到用户区的时间是 50us， CPU 对一块数据进行分析的时间为 50us。若在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是 ( B )。
A. 1500us、1000us B. 1550us、1100us C. 1500us、1550us D. 2000us、2000us
解：
单缓冲区:总时间=n*(100+50)+50=1550us，n=10
双缓冲区:总时间=n*100+50+50=1100us，n=10
-
综合应用题 3
-
在某系统中，从磁盘将一块数据输入到缓冲区需要花费的时间为 T，CPU 对一块数据进行处理的时间为 C，将缓冲区的数据传送到用户区所花时间为 M，那么在单缓冲和双缓冲情况下，系统处理大量数据时，一块数据的处理时间为多少?
解：
单缓冲:MAX(C,T)+M;
双缓冲:MAX(C+M,T)，通常 M 较小而忽略，也可写成 MAX(C,T)
-
-
-
-
-
死锁
- 经典哲学家问题
- 5 个哲学家围绕一张圆桌而坐，桌子上放着 5 支筷子， 每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左 边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子。
- 请写出预防哲学家问题的方法
- ⾄多只允许四位哲学家同时去拿左筷⼦，最终能保证⾄少有⼀位哲学家能进餐，并在⽤完后释放两只筷⼦供他⼈使⽤。
- 仅当哲学家的左右⼿筷⼦都拿起时才允许进餐。 原理：多个临界资源，要么全部分配，要么⼀个都不分配，因此不会出现死锁的情形。
- 预防——打破死锁的四个必要条件
- 破坏"请求和保存"条件
- 第一种协议
- 所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源
- 优点:简单，易行，安全
- 缺点
- 资源被严重浪费，严重地恶化了资源的利用率
- 使进程经常会发生饥饿现象
- 第二种协议
- 它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的，且已用毕的全部资源，然后再请求新的所需资源
- 第一种协议
- 破坏"不可抢占"条件
- 当一个已经保存了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请
- 破坏"循环等待"条件
- 对系统所以资源类型进行线性排序，并赋予不同的序号
- 例如令输入机的序号为 1，打印机序号为 2，磁盘机序号为 3 等。所有进程对资源的请求必须严格按资源序号递增的次序提出。
- 破坏"请求和保存"条件
- 经典哲学家问题
-
文件分配
-
连续分配
- 原理：连续分配就是在磁盘上分配一组连续的块来存储一个文件，磁盘每个块都有一个地址，且按照线性排列。
- 优点
- 顺序访问容易
- 顺序访问速度快
- 缺点
- 要求有连续的存储空间
- 必须事先知道文件的长度
-
链接分配
- 原理：一个文件的信息存放在若干个不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。
- 优点
- 提高磁盘的空间利用率，不存在外部碎片问题。
- 有利于文件的插入和删除。
- 有利于文件的动态扩充。
-
索引分配
-
原理：每个文件在 FAT 中有一个一级索引，索引包含分配给文件的每个分区的入口。
-
无索引
-
混合索引
-
二级索引
-
习题集第四部分
-
选择题 19
-
设文件索引节点中有 7 个地址项，其中 4 个地址项为直接地址索引，2 个地址项是一级间接地址索引，1 个地 址项是二级间接地址索引，每个地址项大小为 4 字节，若磁盘索引块和磁盘数据块大小均为 256 字节，则可表 示的单个文件的最大长度是( C )。
A. 33KB B. 519KB C. 1057KB D. 16613KB
解：
//本注:
-
用的是称做“混合索引”的方式。
-
思路很简单，只是要用些专用概念
-
三类地址项:
- 直接地址项，每个地址直接管理一个“文件块”，而每个“块”是 256 字节。共 4 个这种地址，所以管理:
- 一级间接地址项，每个地址项管理一个“索引块”，而索引块的大小也是 256 字节， 其中可放置: 个地址项，而每个地址项管理 256 字节文件。所以，2 个一级间址 可管理文件大小:
- 二级间接地址项，地址项 → 索引块 → 索引块 → 文件数据块。所以可管理文件数据: .
-
综合上面可管理的文件大小为:
-
-
-
-
-
-
多道程序运行
-
习题集第二部分（进程与线程）
-
选择题 20
-
假定我们有 3 个程序，每个程序花费 80%的时间进行 I/O，20%的时间使用 CPU，每个程序启动时间和其需要使 用进行计算的分钟数如下，不考虑进程切换时间:
程序编号 启动时间 需要 CPU 时间(分钟) 1 00:00 3.5 2 00:10 2 3 00:15 1.5 请问，在多线程/进程环境下，系统的总响应时间为( B )。
A. 22.5 B. 23.5 C. 24.5 D. 25.5
解：
-
0:00 至 0:10，在这 10 分钟里系统属单道(仅程序“1”运行)
，程序“1”的
-
0:10 至 0:15，在这 5 分钟里系统属 2 道(程序“1”和“2”运行)
，。现假定这两个程序完全平等(下同)，则
-
0:15 之后，系统属 3 道(程序“1”、程序“2”和程序“3”运行)
。开始时，
程序“1”尚需
程序“2”尚需
程序“3”尚需
所以，首先结束的是程序“1”
假定程序“1”结束需要时间 x，则，
-
0:18.69 之后，系统属 2 道(程序“2”和“3”运行)
，开始时，
程序“2”尚需
程序“3”尚需
所以，首先结束的是程序“2”
假定程序“2”结束需要时间 x，则，
-
0:21.47 后，系统属单道(仅程序“3”运行)
，程序“3”尚需，则程序“3”结束尚需时间 x，
-
-
-
进程的安全序列
-
进程安全执行完的顺序
-
习题集第二部分（死锁）
-
选择题 18
-
某时刻进程的资源使用情况如下表所示，此时的安全序列是( D )。
A. P1,P2,P3,P4 B. P1,P3,P2,P4 C. P1,P4,P3,P2 D. 不存在
解：
//本注:P2 和 P3 无法满足资源需要，都需资源 R2 三个。
-
-
综合应用题 5、10
-
一台计算机有 8 台磁带机。它们由 N 个进程竞争使用，每个进程可能需要 3 台磁带机。请问 N 为多少时，系统 没有死锁危险，并说明原因。
解：
1 个进程，不会死锁
2 个进程，，而有 8 台磁带机，不会死锁
3 个进程，，而有 8 台磁带机，不会死锁
4 个进程，，而有 8 台磁带机，可能死锁
所以， 时，不会死锁。 -
设系统中有 3 种类型的资源(A、B 和 C)和 5 个进程 P1、P2、P3、P4、P5，A 资源的数量为 17，B 资源的数量为 5，C 资源的数量为 20。在 T0 时刻系统状态如表所示。系统采用银行家算法实施死锁避免策略。
- T0 时刻是否为安全状态?若是，请给出安全序列。
- 若在 T0 时刻进程 P2 请求资源(0，3，4)，是否能实施资源分配?为什么?
- 在(2)的基础上，若进程 P4 请求资源(2，0，1)，是否能实施资源分配?为什么?
- 在(3)的基础上，若进程 P1 请求资源(0，2，0)，是否能实施资源分配?为什么?
解：由题目所给出的最大资源需求量和已分配资源数量，可计算出 T0 时刻各进程的资源需求量 Need，Need=最大资源需求量-已分配资源数量。
-
T0 时刻的安全性检测表，存在安全序列{P5，P4，P3，P2，P1}，故状态是安全的。
-
P2 请求资源(0，3，4)大于剩余资源(2，3，3)，所以不能分配。
-
状态是安全的。可以立即分配 P4 所申请的资源。
-
进入不安全状态，系统不能将资源分配给 P4。
-
-
-
-
程序分析题：12 分
-
程序填空、程序改错、分析程序结果
-
进程同步与通讯
-
系统调用、进程创建
-
fork
-
习题集第二部分（进程与线程）
-
选择题 22
-
题目:请问下面的程序一共输出 ( C ) 个 “-” ？
1
2
3
4
5
6
7
8
9
10
11
int main (void) {
int i;
for(i=0; i<2; i++){
fork();
printf("-\n");
}
return 0;
}A. 2 B. 4 C. 6 D. 8
解：
// fork 复制进程。原进程创建两个子进程，第 1 个子进程再创建一个孙子进程，共四个进程并发执行。输出 6 个“-”。
-
-
-
-
进程的同步与互斥
-
忙等待（实验三）
-
自旋锁
-
turn 变量初始为 0，进程 0 进入临界区，进程 1 忙等待，直到进程 0 离开临界区，并将 turn 设为 1，然后进程 1 进入临界区，当进程 1 也离开临界区时，又把 turn 设为 0，接着进程 0 再次进入临界区，以此类推。由于这种方法需要两者交替进行，如果进程 0 退出临界区时，turn 设为 1，但是进程 1 一直在处理非临界区的工作，进程 0 只有一直忙等待，直到进程 1 将 turn 设为 0。这说明，在一个进程比另一个进程慢很多的情况下（会导致一个进程长久进入不了临界区，违反有限等待原则），轮流进入临界区不是好方法。
-
turn 值
1
2
3
4
5
6
7
8
9
10
11
12
13while(true){
while(turn != 0);
critical_region();
turn = 1;
noncritical_region();
}
while(true){
while(turn != 1);
critical_region();
turn = 0;
noncritical_region();
}
-
-
Peterson（彼得森）
-
设计一个变量 turn 表示哪个进程可以进入临界区。如果 turn==i 即 Pi 允许进入临界区，设计一个数组 flag 表示哪个进程想进入临界区。开始时临界区中无进程，假设进程 0 想进入临界区，进程 1 不想进入临界区，则进程 0 调用请求并直接进入临界区，现在进程 1 想进入临界区，它要在此处挂起并等到进程 0 离开临界区后才能进入临界区。如果两个进程同时想进入临界区，都把自己的进程号存入 turn，则后存入的进程号会覆盖前写入的 turn，变量 turn 的最终值会决定哪个进程允许进入临界区。后进入的进程忙等待直到前一个进程退出临界区。
-
flag、 turn 值
1
2
3
4
5
6
7
8do (
flag(i] = true;
turn = j;
while (flag[j] && turn j);
critical section
flag[i] = false;
remainder section
} while (true);
-
-
-
生产者与消费者问题（实验四）
- 互斥量 —— mutex
- 信号量 —— semaphore
- P (wait)、V (signal) 操作
-
-
线程创建 —— Linux 线程创建（实验二）
-
-
-
综合应用题: 16 分
-
进程调度算法
-
先来先服务（FCFS）调度算法
按照作业（进程）进入后备队列（就绪队列）的先后次序来挑选作业（进程），先进入先被挑选
算法容易实现，效率不高，只顾及作业（进程）等候时间，没考虑作业（进程）要求服务时间的长短。
有利于长作业（进程），不利于短作业（进程）。有利于 CPU 繁忙型作业，不利于 I/O 繁忙型作业 -
短作业优先（SJF）调度算法
从后备队列中选择估计运行时间最短的作业，调入内存运行
优点：
- 降低作业的平均等待时间，提高系统吞吐量。
缺点：
- 对长作业不利，有可能长期不被调度。
- 完全没考虑作业的紧迫程度（某些特殊的）。
- 用户做出的估计时间带有很大的主观性。
-
高响应比优先（HRRN）调度算法
优先权=（等待时间+要求服务时间）/要求服务时间
响应比=（等待时间 + 要求服务时间）/ 要求服务时间 = 响应时间 / 要求服务时间
每当要进行调度时，系统计算每个作业的响应比，选择其中 R 最大者投入执行。
既照顾了短作业，又考虑了作业到达的先后顺序，还不会使长作业长期得不到服务。
该调度算法改进了 FCFS 和 SJF 算法的缺点。 -
时间片轮转法（RR）
用于分时系统中的进程调度。每次调度时，总是选择就绪队列的队首进程，让其在 CPU 上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程，返回到绪队列末尾重新排队，等待下一次调度。
-
基本概念
周转时间 = 作业完成时刻 — 作业到达时刻
带权周转时间 = 周转时间 / 服务时间
平均周转时间 = 作业周转总时间 / 作业个数
平均带权周转时间 = 带权周转总时间 / 作业个数
-
习题集第二部分（调度）
-
综合应用题 1、2
-
设有 4 个作业，它们的到达时刻、所需运行时间如表所示，若采用先来先服务、短作业优先和静态优先级的非抢占式调度算法，则平均周转时间分别是多少?其中优先数越小越先运行。
作业号 到达时刻 所需运行时间 优先数 1 0 2 4 2 1 5 9 3 2 8 1 4 3 3 8 解：
-
先来先服务非抢占式调度算法
作业号 到达时刻 所需运行时间 优先数 开始时刻 结束时刻 周转时刻 1 0 2 4 0 2 2 2 1 5 9 2 7 6 3 2 8 1 7 15 13 4 3 3 8 15 18 15 -
短作业优先调度算法。
作业号 到达时刻 所需运行时间 优先数 开始时刻 结束时刻 周转时刻 1 0 2 4 0 2 2 2 1 5 9 2 7 6 3 2 8 1 10 18 16 4 3 3 8 7 10 7 -
静态优先级调度算法
作业号 到达时刻 所需运行时间 优先数 开始时刻 结束时刻 周转时刻 1 0 2 4 0 2 2 2 1 5 9 13 18 17 3 2 8 1 2 10 8 4 3 3 8 10 13 10
-
-
系统有 5 个进程，其就绪时刻(指在该时刻已经在就绪队列中就绪)、服务时间如表所示。若采用先来先服务、 短作业优先、高响应比优先、时间片轮转调度算法(时间片=1)，计算相关的平均周转时间和平均带权周转时间。(本注:带权周转时间=(周转时间)/(服务时间))
进程 就绪时刻 服务时间 P1 0 3 P2 2 6 P3 4 4 P4 6 5 P5 8 2 解：
-
先来先服务调度算法
-
短作业优先调度算法
-
高响应比优先
时刻 9:
P3:响应比 (9-4)/4=5/4
P4:响应比 (9-6)/5=3/5
P5:响应比 (9-8)/2=1/2
选择:P3
时刻 13:
P4:响应比 (13-6)/5=7/5
P5:响应比 (13-8)/2=5/2
选择:P5
-
时间片轮转(时间片=1)调度算法
-
-
-
-
-
分页与分段
-
习题集第三部分（分页分段）
-
选择题 6、10
-
在一个分页存储管理系统中，页表内容如表所示。若页的大小为 4K，则地址转换机构将逻辑地址 0 转换成物理地址为 ( A )。
页号 块号 0 2 1 1 2 6 3 3 4 7 A. 8192 B. 4096 C. 2048 D. 1024
解：
// 页号=逻辑地址\块大小=0，页内偏移=逻辑地址%块大小=0
// 物理块号=2(依据页表中页号对应块号)，
// 则物理地址=块号 * 块大小 + 页内偏移 = 2 * 4096 + 0 = 8192 -
一个分段存储管理系统中，地址长度为 32 位，其中段号占 8 位，则最大段长是 ( )。
A. 28 字节 B. 216 字节 C. 224 字节 D. 232 字节
-
-
综合应用题 1、2、3
-
-
习题集第三部分（虚拟内存管理）
-
综合应用题 7
-
某请求分页存储管理系统，允许用户空间为 32 个页面(每页 1KB)，主存为 16KB，如一个用户程序有 10 页长， 且在某时刻该用户进程的页表如下所示。
页号 物理块号 是否在 TLB 中 0 8 是 1 7 是 2 4 否 3 10 否 4 5 否 5 3 是 6 2 是 其他 无效 - 如果程序执行时遇到以下两个虚地址:0AC5(H)，1AC5(H)，试计算它们对应的物理地址。
- 页表存放在主存中，对主存的一次存取需要 1.5μs，对 TLB 表(快表)的查找时间忽略为 0，试问这两次访问共耗费多少时间?
解：
-
页大小 ，则后 10 位“页内偏移量”，前面为“页号”。
0AC5(H)=(0000 1010 1100 0101)=(0000 10)(10 1100 0101) 页号:(10)(B)=2; 页内偏移量:(10 1100 0101)
依据页表，页号 2 对应物理块号(帧号)4(二进制 100).
则，0AC5(H)的物理地址(100)(10 1100 0101)=(1 0010 1100 0101)=12C5(H)1AC5(H)=(0001 1010 1100 0101)=(0001 10)(10 1100 0101)
页号:(1 10)(B)=6;页内偏移量:(10 1100 0101)
依据页表，页号 6 对应物理块号(帧号)2(二进制 10) 则，1AC5(H)的物理地址(10)(10 1100 0101)=(1010 1100 0101)=0AC5(H) -
0AC5(H)放在物理块 4 在 TLB 中，则需要两次内存访问(增加一次访问页表)，而物 理块 2 在 TLB 中，只须访问一次内存。故两次访问耗费时间=1.5*3=4.5us。
-
-
-
页面置换算法
-
抖动的概念
- 即刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出
-
最佳置换算法(需要预知后面进程，所以不能实现)
-
最佳淘汰算法 (OPT)
-
从主存中移出永远不再需要的页面;如无这样的页面存在，
-
则选择最长时间不需要访问的页面。 - 于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。即被淘汰页 面是以后永不使用或最长时间内不再访问的页面。
-
-
先进先出页面置换算法（FIFO）
- 选择在内存中驻留时间最久的页面予以淘汰
-
最近最久未使用置换算法（LRU）Recently
- 替换，页面走向中，左边离要替换的页面最远的一项
- 寄存器支持
- 特殊的栈结构
-
最少使用置换算法（LFU）Frequently
- 替换，页面走向中，右边离要替换的页面最远的一项
-
clock 置换算法（对访问位 A 的判断）
- 改进型——增加对修改位 M 思维判断
-
页面缓冲算法（PBA,page buffering algorithm）
-
空闲页面链表
-
修改页面链表
-
-
习题集第三部分（虚拟内存管理）
-
综合应用题 8、9、10、11
-
考虑下述页面走向:1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6 当内存块数量分别为 3 时，试问 FIFO、LRU、OPT 这三种置换算法的缺页次数各是多少?
解：所有内存块最初都是空的，所以第一次使用到的页面都产生一次缺页，共发生 20 次页面调用。
-
FIFO 置换算法
缺页次数=16，缺页中断率=16/20
-
LRU 置换算法
缺页次数=15，缺页中断率=15/20
-
OPT 置换算法
缺页次数=11，缺页中断率=11/20
// 当有多个选择时，采用“先进先出”置换算法，如最后一个页面 6 按照 OPT 算法可转换{3、2、1}中的任意一个，此时选择最先进入的页面 3 置换。
-
-
已知页面走向为 1、2、1、3、1、2、4、2、1、3、4，且开始执行时内存中没有页面。若只给该作业分配 2 个 物理块，当采用 FIFO 页面淘汰算法时缺页率为多少?假定现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，其缺页率又是多少?
解：
- FIFO 页面替换算法的缺页情况
缺页次数:9;缺页率:9/11
- 替换刚使用页面算法的缺页情况
缺页次数:8; 缺页率:8/11
-
在一请求分页系统中，一个进程已分配到 4 个页框(PageFrame)，如下表所示(所有数字都为十进制数，且以 0 开始)。操作系统采用固定分配局部置换策略为此进程分配 4 个页框。当进程访问第 4 页时，产生缺页中断， 请分别用 FIFO、LRU 算法，决定缺页中断服务程序选择换出的页面。
页号 页框号 装入时间 最近访问时间 访问位 修改位 2 0 60 161 0 1 1 1 130 160 0 0 0 2 26 162 1 0 3 3 20 163 1 1 解：
由于采用固定分配局部置换策略，所以该进程只能占用 4 个页框。
-
从“装入时间”可得出，装入顺序:3、0、2、1，则被 4 替换的是 3，因为 3 的修改位为 1，在换出主存后需要回写，重新保存。
-
从“最近访问时间”可得出，最后访问顺序:1、2、0、3，则被 4 替换的是 1，因为 1 修改位为 0，在换出主存后不需要回写。
-
-
在一请求分页系统中，某程序在一个时间段内有如下的存储器引用:12、351、190、90、430、30、550(以上 数字为虚存的逻辑地址)。假定内存中每块的大小为 100B，系统分配给该作业的内存块数为 3 块。回答如下问 题:
-
对于以上的存储器引用序列，给出其页面走向。
-
设程序开始运行时，已装入第 0 页。在先进先出页面置换算法和最久未使用页面置换算法(LRU 算法)下， 分别画出每次访问时刻程序的内存页面情况;并计算出缺页中断次数和缺页率。
解：
-
页面大小与每块的大小相等，即 100B，所以 12、351、190、90、430、30、550 逻辑地址对应的页号走向序列为 0、3、1、0、4、0、5。
-
采用先进先出页面置换算法:
缺页中断次数:6 缺页率:6/7=85.7%
采用 LRU 页面置换算法:
缺页中断次数:5 缺页率:5/7=71.4%
-
-
-
-
-
-