4.在页式虚存管理系统中，系统有m个物理块供调度，初始时全空，页面引用串长度为p，包含了n个不同的页号，无论用什么页面置换算法，有： 1）缺页次数的下限是多少？ 2）缺页次数的上限是多少？

1. 缺页次数的下限是0，因为初始时所有物理块都是空的，不可能有缺页。

2. 缺页次数的上限是p/m，即页号引用串长度除以物理块数。这是因为，如果物理块数小于页号数，必然会出现缺页情况，缺页次数最多为页号数除以物理块数。而如果物理块数大于等于页号数，所有页都可以在物理块中找到，不会出现缺页情况。因此，缺页次数的上限为p/m。

相关问题

在一个页式虚存管理系统中，假定系统分配给一个进程的物理块数为3，并且此进程的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，且开始执行时内存中没有页面，分别用FIFO、OPT、LRU算法，分别计算出缺页中断次数和缺页中断率。

好的，我知道了。这是一个操作系统的问题，需要一定的计算和分析。我可以帮你解答。

首先，我们需要了解三种页面置换算法：FIFO、OPT、LRU。

- FIFO：先进先出，即最先进入内存的页面将被最先淘汰。
- OPT：最优置换算法，选择最长时间内不被访问的页面进行置换。
- LRU：最近最少使用算法，选择最长时间未被访问的页面进行置换。

接下来，我们来计算缺页中断次数和缺页中断率。

使用FIFO算法：

| 页号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1 | F | F | F | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | | F | F | F | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | | | F | F | F | F | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 4 | | | | F | F | F | F | F | F | 5 | 5 | 4 | 4 |
| 缺页 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

缺页中断次数为13，缺页中断率为13/12=1.08。

使用OPT算法：

| 页号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1 | F | F | F | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | | F | F | F | F | F | F | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | | | F | F | F | F | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 4 | | | | F | F | F | F | F | F | 5 | 5 | 5 | 4 |
| 缺页 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 9 | 10 | 11 | 12 |

缺页中断次数为12，缺页中断率为12/12=1。

使用LRU算法：

| 页号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1 | F | F | F | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | | F | F | F | F | F | F | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | | | F | F | F | F | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 4 | | | | F | F | F | F | F | F | 5 | 5 | 5 | 5 |
| 缺页 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 9 | 10 | 11 | 11 |

缺页中断次数为11，缺页中断率为11/12=0.92。

综上所述，FIFO算法的缺页中断率最高，OPT算法的缺页中断率最低，LRU算法位于两者之间。

页面置换算法，在一个支持虚拟分页并采用请求页式调度的存储管理系统中，有一用户程序，它访问其地址空间的字地址序列是：70、74、135、276、400、300、700、266、148、560、284、172（以上数字为虚存的逻辑地址）。问： (1). 若分配给该作业的内存大小为384字，初始为空，页大小为128字，对于以上的存储器引用序列，给出其页面走向。 (2). 试按FIFO、LRU页面淘汰算法，分别计算页面访问的缺页次数和缺页率？

好的，我来回答您的问题：

(1) 若分配给该作业的内存大小为384字，初始为空，页大小为128字，对于以上的存储器引用序列，给出其页面走向。

首先，根据页大小可知，一个页面可存放128字，所以该程序需要的页面数为：

(70+127)/128 + (74+127)/128 + (135+127)/128 + (276+127)/128 + (400+127)/128 + (300+127)/128 + (700+127)/128 + (266+127)/128 + (148+127)/128 + (560+127)/128 + (284+127)/128 + (172+127)/128 = 11

因此，该程序需要11个页面才能存放完所有数据。由于分配给该作业的内存大小为384字，初始为空，因此只能分配3个页面，即384字/128字/页面=3个页面。页面走向如下：

| 访问地址 | 页号 | 页面内容 |
|----------|------|----------|
| 70 | 0 | 70 |
| 74 | 0 | 70、74 |
| 135 | 1 | 135 |
| 276 | 2 | 276 |
| 400 | 3 | 400 |
| 300 | 2 | 276、300 |
| 700 | 5 | 700 |
| 266 | 2 | 300、266 |
| 148 | 1 | 135、148 |
| 560 | 4 | 560 |
| 284 | 2 | 266、284 |
| 172 | 1 | 148、172 |

(2) 试按FIFO、LRU页面淘汰算法，分别计算页面访问的缺页次数和缺页率。

FIFO页面淘汰算法：

| 访问地址 | 页号 | 页面内容 | 缺页次数 | 缺页率 |
|----------|------|----------|---------|--------|
| 70 | 0 | 70 | 1 | 33.33%|
| 74 | 0 | 70、74 | 1 | 33.33%|
| 135 | 1 | 70、74、135 | 2 | 66.67%|
| 276 | 2 | 74、135、276 | 3 | 100.00%|
| 400 | 3 | 135、276、400 | 4 | 133.33%|
| 300 | 2 | 276、400、300 | 5 | 166.67%|
| 700 | 5 | 400、300、700 | 6 | 200.00%|
| 266 | 2 | 300、700、266 | 7 | 233.33%|
| 148 | 1 | 700、266、148 | 8 | 266.67%|
| 560 | 4 | 266、148、560 | 9 | 300.00%|
| 284 | 2 | 148、560、284 | 10 | 333.33%|
| 172 | 1 | 560、284、172 | 11 | 366.67%|

LRU页面淘汰算法：

| 访问地址 | 页号 | 页面内容 | 缺页次数 | 缺页率 |
|----------|------|----------|---------|--------|
| 70 | 0 | 70 | 1 | 33.33%|
| 74 | 0 | 70、74 | 1 | 33.33%|
| 135 | 1 | 70、135、74 | 2 | 66.67%|
| 276 | 2 | 135、74、276 | 3 | 100.00%|
| 400 | 3 | 74、276、400 | 4 | 133.33%|
| 300 | 2 | 276、400、300 | 5 | 166.67%|
| 700 | 5 | 400、300、700 | 6 | 200.00%|
| 266 | 2 | 400、700、266 | 7 | 233.33%|
| 148 | 1 | 700、266、148 | 8 | 266.67%|
| 560 | 4 | 266、148、560 | 9 | 300.00%|
| 284 | 2 | 148、560、284 | 10 | 333.33%|
| 172 | 1 | 560、284、172 | 11 | 366.67%|

其中，缺页次数是指程序运行过程中，需要从虚拟内存中读取的页面数量，缺页率是指缺页次数占所有页面访问次数的比例。可以看出，在FIFO和LRU页面淘汰算法下，缺页次数和缺页率都是相同的，因为页面淘汰算法不会影响整个程序的页面走向。