操作系统页面置换算法习题

好的，这里有一些操作系统页面置换算法的习题。

1. 有一个主存大小为4KB的计算机系统，分配给一个作业的物理块数为2，该作业的逻辑地址空间大小为64KB，每个页的大小为2KB。请问该系统的页表大小是多少？

答案：由于每个页的大小为2KB，因此逻辑地址空间大小为64KB，则该作业的页数为64KB/2KB = 32页。由于系统只分配了2个物理块，因此只能将2个页放入主存中。因此，该作业的页表大小为32 * 2 = 64B。

2. 在一个主存大小为8KB的计算机系统中，有一个作业需要访问的逻辑页号为1、2、3、4、5、6、7、8、9、10，分配给该作业的物理块数为3。采用FIFO页面置换算法，当作业访问逻辑页号为1、2、3、4、5、6、7、8、9、10时，发生的页面置换情况是什么？

答案：初始状态下，物理块中没有页面，因此作业首先访问逻辑页号为1，将页面1装入物理块1；然后作业访问逻辑页号为2，将页面2装入物理块2；接着作业访问逻辑页号为3，将页面3装入物理块3；此时，物理块中已经没有空闲的块，因此需要进行页面置换，采用FIFO算法，因此置换出现在物理块1中的页面1，将新访问的页面4放入物理块1；接下来依次顺序访问页面5、6、7、8、9、10，当访问页面5时，会发现物理块中已经没有页面2了，因此需要将页面2置换出去，以此类推，最终的页面置换情况为：1→2→3→4→5→2→6→3→7→4→8→5→9→2→10。

3. 在一个主存大小为16KB的计算机系统中，有一个作业需要访问的逻辑页号为1、2、3、4、5、6、7、8、9、10，分配给该作业的物理块数为4。采用LRU页面置换算法，当作业访问逻辑页号为1、2、3、4、5、6、7、8、9、10时，发生的页面置换情况是什么？

答案：初始状态下，物理块中没有页面，因此作业首先访问逻辑页号为1，将页面1装入物理块1；然后作业访问逻辑页号为2，将页面2装入物理块2；接着作业访问逻辑页号为3，将页面3装入物理块3；此时，物理块中已经没有空闲的块，因此需要进行页面置换，采用LRU算法，因此需要将最近最少使用的页面置换出去，根据访问情况，最近最少使用的页面为页面1，因此置换出现在物理块1中的页面1，将新访问的页面4放入物理块1；接下来，访问逻辑页号为5时，发现页面5不在物理块中，因此需要将最近最少使用的页面2置换出去，以此类推，最终的页面置换情况为：1→2→3→1→4→5→2→6→3→7→1→8→4→9→2→10。