1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6当分配的内存块数量为4时,画出LRU,FIFO这两种置换算法的页面置换图,并计算它们的缺页率
时间: 2023-10-08 16:13:13 浏览: 30
假设物理内存有4个页面框,初始情况下,页面框中无任何页面,页面访问序列为1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6。
### FIFO页面置换算法
|访问页面|页面框状态|缺页次数|
|---|---|---|
|1|[1,-,-,-]|1|
|2|[1,2,-,-]|2|
|3|[1,2,3,-]|3|
|4|[1,2,3,4]|4|
|2|[2,3,4,2]|5|
|1|[3,4,2,1]|6|
|5|[4,2,1,5]|7|
|6|[2,1,5,6]|8|
|2|[1,5,6,2]|9|
|1|[5,6,2,1]|10|
|2|[6,2,1,2]|11|
|3|[2,1,3,7]|12|
|7|[1,3,7,6]|13|
|6|[3,7,6,2]|14|
|3|[7,6,2,3]|15|
|2|[6,2,3,1]|16|
|1|[2,3,1,1]|17|
|2|[3,1,2,2]|18|
|3|[1,2,3,6]|19|
|6|[2,3,6,1]|20|
FIFO置换算法的缺页次数为20,缺页率为$\frac{20}{20}=1$。
### LRU页面置换算法
|访问页面|页面框状态|缺页次数|
|---|---|---|
|1|[1,-,-,-]|1|
|2|[1,2,-,-]|2|
|3|[1,2,3,-]|3|
|4|[1,2,3,4]|4|
|2|[2,3,4,1]|5|
|1|[1,3,4,2]|6|
|5|[3,4,2,5]|7|
|6|[4,2,5,6]|8|
|2|[2,5,6,4]|8|
|1|[5,6,4,1]|9|
|2|[6,4,1,2]|10|
|3|[4,1,2,3]|11|
|7|[1,2,3,7]|12|
|6|[2,3,7,6]|13|
|3|[3,7,6,2]|14|
|2|[7,6,2,1]|15|
|1|[6,2,1,5]|16|
|2|[2,1,5,3]|17|
|3|[1,5,3,6]|18|
|6|[5,3,6,2]|19|
LRU置换算法的缺页次数为19,缺页率为$\frac{19}{20}=0.95$。