电子商务型网站建设淘宝流量平台
1.设某进程页面的访问序列为4,3,2,1,4,3,5,4,3，2,1,5，当分配给该进程的内存页框数分别为3和4时，对于先进先出，最近最少使用，最佳页面置换算法，分别发生多少次缺页中断？
答：
分配的页框数为3时：
FIFO:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | |
| 内存块1 | 4 | 4 | 4 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 |
| 内存块2 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 2 | 2 | 2 | |
| 内存块3 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | ||
| 是否缺页 | × | × | × | × | × | × | × | √ | √ | × | × | √ |
共缺页9次
扩充：先进先出置换算法（FIFO):每次选择淘汰的页面是最早进入内存的页面
实现方法:把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
当到内存块为 1 4 3时，队列为4-3-5,这时候下一个访问4，因为内存块有，就不改变队列，继续下一个，3也在队列不改变，2的时候改变，于是队列变为了3-5-2，内存块为4内容的改为2.
OPT:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | |
| 内存块1 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 2 | 2 | 2 |
| 内存块2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | |
| 内存块3 | 2 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | ||
| 是否缺页 | × | × | × | × | √ | √ | × | √ | √ | × | × | √ |
共缺页7次
扩充; 最佳置换算法（OPT，Optimal):每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
注意最后从倒数第四个到倒数第三个，4 3 5 改为2 3 5，因为后期都不会有4 3的访问了，所以先改变4，从倒数第三个到倒数第二个，2 3 5 下一个时2 1 5，改变3的原因时尽管感觉3与2都可以修改，但是3的时间不妨问比2的久，因为2刚刚访问过了。
分配的页框数为4时：
FIFO:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | |
| 内存块1 | 4 | 4 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 1 | 1 |
| 内存块2 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 5 | |
| 内存块3 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | ||
| 内存块4 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | |||
| 是否缺页 | × | × | × | × | √ | √ | × | × | × | × | × | × |
共缺页10次
LRU:
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | |
| 内存块1 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 |
| 内存块2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | |
| 内存块3 | 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 1 | 1 | ||
| 内存块4 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | |||
| 是否缺页 | × | × | × | × | √ | √ | × | √ | √ | × | × | × |
共缺页8次
扩充：最近最久未使用置换算法（LRU，least recently used):每次淘汰的页面是最近最久未使用的页面。简单来说就是看有4个内存块，那么往前看4个不同的，把最后一个改变，比如，到5的时候，前面4个依次是2 1 4 3，所以从5往前看正好是不同的4个，删除最后一个2，5给换上。
倒数第3个是2，按照方法从前数发现是1 5 4 3
OPT：
| 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 | |
| 内存块1 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 1 | 1 |
| 内存块2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | |
| 内存块3 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | ||
| 内存块4 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | |||
| 是否缺页 | × | × | × | × | √ | √ | × | √ | √ | √ | × | √ |
共缺页6次
2. 某分页存储管理中，页面大小为4KB,某进程的页号0~8对应的物理块号分别为8、9、 10、15、18、20、21、22、23，计算该进程的逻辑地址05AF8H对应的物理地址（描述计算过程）
答：因为：页号为0-8，所以：前4位为页号
页面大小为4KB，4K=2^12 所以：后12位为页内地址
05AF8H的二进制为0101 1010 1111 1000
所以：页号为0101 十进制表示为5
查表得物理快号为20，即10100（B）
与页内地址拼接得10100 1010 1111 1000 十六进制为14AF8H
3. 在一个请求页式存储管理系统中，进程P共有5页，访问串为3，2，1，0，3，2，4，3，2，1，0，4时，试用LRU置换算法和FIFO置换算法，计算当分配给该进程的页面数为3时，访问过程中发生的缺页次数和缺页率。
LRU：
| 3 | 2 | 1 | 0 | 3 | 2 | 4 | 3 | 2 | 1 | 0 | 4 | |
| 内存块1 | 3 | 3 | 3 | 0 | 0 | 0 | 4 | 4 | 4 | 1 | 1 | 1 |
| 内存块2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 0 | 0 | |
| 内存块3 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 4 | ||
| 是否缺页 | × | × | × | × | × | × | × | √ | √ | × | × | × |
缺页次数：10 缺页率：10/12=5/6
FIFO：
| 3 | 2 | 1 | 0 | 3 | 2 | 4 | 3 | 2 | 1 | 0 | 4 | |
| 内存块1 | 3 | 3 | 3 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 |
| 内存块2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | |
| 内存块3 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | ||
| 是否缺页 | × | × | × | × | × | × | × | √ | √ | × | × | √ |
缺页次数：9 缺页率：9/12=3/4
方法：排成一个队列，替换最早的哪一个，遇到相同的页号不改变，如到了4-3-2，这时候队列为3-2-4，但是下一个页号为3，内存块已经有了，然后下一块2，内存块也有，都不改变队列，到了1的时候内存块没有，改变最早的那个，也就是3，所以存放3的那个内存块变成了1
4. 在某请求分页系统中，有一作业，它依次要访问的地址序列是：18、351、198、99、436、50、556，若该作业的第0号页已经装入主存，现分配给该作业的主存共3块，页的大小为100字节。请回答下列问题（需要详细过程）：
(1)按FIFO调度算法产生的缺页中断次数是多少？依次写出淘汰的页号？缺页中断率是多少？
（2）按LRU调度算法产生的缺页中断次数是多少？依次写出淘汰的页号？缺页中断率是多少
答：依次访问页号为 0 3 1 0 4 0 5
FIFO：
| 0 | 3 | 1 | 0 | 4 | 0 | 5 | |
| 内存块1 | 0 | 0 | 0 | 0 | 4 | 4 | 4 |
| 内存块2 | 3 | 3 | 3 | 3 | 0 | 0 | |
| 内存块3 | 1 | 1 | 1 | 1 | 5 | ||
| 是否缺页 | × | × | × | √ | × | × | × |
中断次数 6 淘汰的页号： 0 3 1 缺页率：6/7=85.71%
LRU：
| 0 | 3 | 1 | 0 | 4 | 0 | 5 | |
| 内存块1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 内存块2 | 3 | 3 | 3 | 4 | 4 | 4 | |
| 内存块3 | 1 | 1 | 1 | 1 | 5 | ||
| 是否缺页 | × | × | × | √ | × | √ | × |
中断次数 5 淘汰的页号（暂定）： 0 3 1 和0 4 1 缺页率：5/7=71.43%
5. 请求分页管理系统中，假设某进程的页表内容如下表所示。
页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设：
①TLB初始为空；
②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；
③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列137H 、565H、15A5H，请问：
（1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。
（2） 基于上述访问序列，虚地址258H的物理地址是多少？请说明理由。
| 页号 | 页框号 | 有效位（存在位） |
| 0 | 101H | 1 |
| 1 | -- | 0 |
| 2 | 254H | 1 |
（1）根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：
137H：P=0，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
565H：P=0，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。
15A5H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+100ns≈108ns。
（2）访问1565H时,1号页面在内存中,页框号与15A5H相同。前面当访问虚地址15A5H时，访问页表发现1号页不在内存中，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，最近访问的都是0号页的内容，0号页不应被淘汰。应淘汰2号页面，因此1号页面装入时对应的页框号为254H。由此可得1565H的物理地址为254565H。
6.段式存储管理
在某个段式存储管理系统中，进程P的段表如下表，求表中各逻辑地址对应的物理地址
| 段号 | 段内位移 |
| 0 | 430 |
| 1 | 15 |
| 2 | 500 |
| 3 | 400 |
| 4 | 112 |
答：
| 段号 | 段内位移 | 物理地址 |
| 0 | 430 | 680 |
| 1 | 15 | 2365 |
| 2 | 500 | 越界 |
| 3 | 400 | 1750 |
| 4 | 112 | 越界 |
7.页式管理
在某页式管理系统，某进程页表如下，已知页面大小为1024B，试将逻辑地址1012、2248、3010、4020、5018转化为相应的物理地址。
| 页号 | 页框号 |
| 0 | 5 |
| 2 | 8 |
| 2 | 8 |
| 3 | 1 |
| 4 | 6 |
答：
| 逻辑地址 | 页号 | 页内地址 | 页框号 | 物理地址 |
| 1012 | 0 | 1012 | 5 | 5*1024+1012=6132 |
| 2248 | 2 | 200 | 8 | 8*1024+200=8392 |
| 3010 | 2 | 962 | 8 | 8*1024+962=9154 |
| 4020 | 3 | 948 | 1 | 1*1024+948=1972 |
| 5018 | 4 | 922 | 6 | 6*1024+922=7066 |
8. 假定某页式管理系统中，主存为128KB，分成32块,块号为0,1,2,3,4……31,某作业有五块,其页号为0,1,2,3,4, 被分别装主存的3,8,4,6,9块中，有一逻辑地址为[3,70],试求出相应的物理地址(其中方括号中的第一个元素为页号,第二个元素为页内地址，按十进制计算)，并画图说明地址变换过理。
9.计算物理地址
物理地址计算3步曲!
- 求出页号
- 对照页表
- 计算地址
地址转换
绝对地址 = 块号*块长 + 块内地址
例题:
在采用页式存储管理的系统中,某进程的逻辑地址空间为4页(每页2048字节),且已知该进程的页面映像表(页表)如下:
| 页号 | 块号 |
| 0 | 2 |
| 1 | 4 |
| 2 | 6 |
| 3 | 8 |
计算有效逻辑地址4865所对应的物理地址.
解题:
读题划重点: 每页多少字节, 页表,有效逻辑地址!
3步曲解题!
页号:
页号 = 逻辑地址/每页字节数
d = 4865/2048 = 2
对照页表:
根据页号找到块号!
看页表 ,页号2对应块号6!
数地址:
绝对地址 = 块号*块长（每页字节数） + 块内地址
块内地址= 逻辑地址%每页字节数
块内地址: 4865%2048 = 769
地址:6*2048 + 769 = 13057