改进型Clock置换算法

问题背景

假如分页存储系统页大小为4KB,字节编址，系统给进程P分配两个固定页框，并采用改进型Clock置换算法，进程P的页表的部分内容如下：

页号	页框号	存在位（1：存在 0：不存在）	访问位（1：访问 0：为访问）	修改位 （1：修改，0：未修改）
…	…	…	…	…
2	20H	0	0	0
3	60H	1	1	0
4	80H	1	1	1

若P访问虚拟地址为02A01H的存储单位，则经地址变换为得到的物理地址是( C )。
A. 00A01H B. 20A01H C. 60A01H D. 80A01H

涉及知识

进制转换
内存管理的地址转换
页面置换算法

思路

第一步

虚拟地址（逻辑地址）
虚拟地址02A01H = 页号+页内偏移量（和内存页大小统一）。
页面大小为4KB=$2^{12}$B，对应虚拟地址为02A01H。
因为页面大小和业内偏移量相同大小,所以02H为页号。

结合背景中的图标可知，02H对应的页框（内存中的一格）号为20H。

第二步

因为题干给出要求，内存中固定分配给进程两个页框，同时页号00H，01H已经暂用内存两个页框，所以需要执行页从内存的换入换出。

页面置换算法（6种）
参照链接一

• 最佳（Optimal,OPT）置换算法
• 先进先出(FIFO)页面置换算法
• 最近最久未使用（LRU）置换算法
• 随机置换
• 时钟置换算法
• 改进时钟置换算法

时钟置换算法
参考链接二
存在位(resident bit): 对于一个页面是否有物理页与其对应，如果有就为1。
修改位(dirty bit)：判断页面 是否被修改过。
引用位(clock/reference bit)：页面是否有过对它的引用。

1. 由于20H存在位是0，60H和80H两个页框连续且存在,所以符合题目要求
2. 根据改进时钟置换算法 60H(1,0)的优先级 > 80H(1,1),所以虚拟地址02A01H转为位实际内存物理地址位60A01H。

总结

1. H=>16进制 B=>2进制 D=>10进制 O=>8进制
2. 逻辑地址和物理地址的地址转换 ，基于页表作为中间映射。
3. 基本分页存储管理的页面置换算法。
4. 时钟置换算法的处理流程。