青岛理工大学操作系统第4章练习题

操作系统常见题解析及模拟题内容

【例2】对一个将页表存放在内存中的分页系统:

（1）如访问内存需要0．2μs，有效访问时间为多少?

（2）如果加一快表，且假定在快表中找到页表项的机率高达90％，则有效访问时间又是多少(假定查快表需花的时间为0)? 答：（1）有效访问时间为：2×0．2=0．4μs （2）有效访问时间为：0．9×0．2+(1—0．9)×2×0．2＝0．22 ps。

【例3】某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M。 （1）写出逻辑地址的格式。

（2）若不考虑访问权限等，进程的页表有多少项?每项至少有多少位? （3）如果物理空间减少一半，页表结构应相应作怎样的改变? 答：（1）该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位来描述：而每页为 2K，因此，页内地址必须用11位来描述，这样可得到它的逻辑地址格式如下： 15 11 10 0 页号 页内地址 (2)每个进程最多有32个页面，因此，进程的页表项最多为32项；若不考虑访问权限等，则页表项中只需给出页所对应的物理块块号，1M的物理空间可分成29个内存块，故每个页表项至少有9位

(3)如果物理空间减少一半，则页表中页表项数仍不变，但每项的长度可减少1位。 【例4】已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、l、2、3页分别被分配到主存的2、4、6、7块中。

(1)将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。 (2)以十进制的逻辑地址1023为例画出地址变换过程图。

答：(1)对上述逻辑地址，可先计算出它们的页号和页内地址(逻辑地址除以页面大小，得到的商为页号，余数为页内地址)，然后通过页表转换成对应的物理地址。

①逻辑地址1023：1023／1K，得到页号为0，页内地址为1023，查页表找到对应的物理块号为2，故物理地址为2×1K+1023=3071。

②逻辑地址2500：2500／1K，得到页号为2，页内地址为452，查页表找到对应的物理块号为6，故物理地址为6×IK+452=6596。

③逻辑地址3500：3500／IK，得到页号为3，页内地址为428，查页表找到对应的物理块号为7，故物理地址为7×1K+428=7596。 ④逻辑地址4500：4500／1K，得到页号为4，页内地址为404，因页号不小于页表长度，故产生越界中断。

(2)逻辑地址1023的地址变换过程如下图所示，其中的页表项中没考虑每页的访问 权限。

1

操作系统常见题解析及模拟题内容

【例5】已知某系统页面长4KB，页表项4字节，采用多层分页策略映射64位虚拟地址空间。若限定最高层页表占1页，问它可以采用几层分页策略。（浙江大学2000年考题） 答：由题意，64位虚拟地址的虚拟空间大小为264.页面长为4KB,页表项4字节，所以一个页面可存放1K个表项。由于最高层页表占1页，也就是说其页表项个数最多为1K个，每一项对应一页，每页又可存放1K个页表项，依次类推可知，采用的分页层数为：6层。 【例6】对于下表所示的段表，请将逻辑地址(0，137)，(1，4000)，(2，3600)，(5，230)转换成物理地址。 段号 O l 2 3 4 内存始址 50K 60K 70K 120K 150K 段长 10K 3K 5K 8K 4K 段表

答：(1)段号0小于段表长5，故段号合法；由段表的第0项可获得段的内存始址为 50K，段长为10K；由于段内地址137，小于段长10K，故段内地址也是合法的，因此可得 出对应的物理地址为50K+137=5l337。 (2)段号l小于段表长，故段号合法；由段表的第l项可获得段的内存始址为60K，段长为3K：经检查，段内地址4000超过段长3K，因此产生越界中断。

(3)段号2小于段表长，故段号合法；由段表的第2项可获得段的内存始址为70K，段长为5K；故段内地址3600也合法。因此，可得出对应的物理地址为70K+3600=75280。 (4)段号5等于段表长，故段号不合法，产生越界中断。

【例7】在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M为3时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时访问过程中所发生的缺页次数和缺页率。 答：(1)使用FIFO算法时，访问过程中发生缺页的情况为：当物理块数目M为3时，缺页次数为9，缺页率为9／12(如下表所示)。

2

操作系统常见题解析及模拟题内容

4 √ 4 3 √ 4 3 2 √ 4 3 2 1 √ 1 3 2 4 √ 1 4 2 3 √ 1 4 3 5 √ 5 4 3 4 5 4 3 3 5 4 3 2 √ 5 2 3 1 √ 5 2 1 5 5 2 1 (2)使用OPT算法时，访问过程中发生缺页的情况为：当物理块数目M为3时，缺页次数为7，缺页率为7／12(如下表所示)。 4 √ 4 3 √ 4 3 2 √ 4 3 2 1 √ 4 3 1 4 4 3 1 3 4 3 1 5 √ 4 3 5 4 4 3 5 3 4 3 5 2 √ 4 2 5 1 √ 4 1 5 5 4 1 5 （3）使用LRU算法时，访问过程中发生缺页的情况为：当物理块数目M为3时，缺页次数为lO，缺页率为10／12(如下表所示)。 4 √ 4 3 √ 4 3 2 √ 4 3 2 1 √ 1 3 2 4 √ 1 4 2 3 √ 1 4 3 5 √ 5 4 3 4 5 4 3 3 5 4 3 2 √ 2 4 3 1 √ 2 1 3 5 √ 2 1 5 【例8】某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3635，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制数，而内存中尚未装入任何页。给出使用LRU算法时的缺页次数，并与FIFO时的情况进行比较。

答：根据题意，分配给作业的内存块数为3，而页面的引用次序为：3、3、1、3、2、3、O、2、l、2、3、O、l、1。因此，可以计算出，采用LRU算法时，缺页次数为8，采用FIFO算法时，缺页次数为6。LRU算法用最近的过去来作为预测最近的将来的依据，一般认为其有较好的性能，但实现时，要记录最近在内存的每个页面的使用情况，比FIFO困难，其开销也大。有时，因页面的过去和未来的走向之间并无必然的联系，如上面，LRU算法的性能就没有想象中的那么好。

【例9】某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。

答：由题目所给条件可知，该系统的逻辑地址有15位，其中高5位为页号，低10位为页内 地址；物理地址有14位，其中高4位为页帧号，低10位为页帧内地址。另外，由于题目中给出的逻辑地址是十六进制数，故可先将其转换成二进制数以直接获得页号和页内地址，再完成地址的转换

如右图所示，逻辑地址(0A5C)16的页号为(00010)2，即2，故页号合法；从页表中找到对应的内存块号为4，即(0100)2与页内地址 (10 0101 1100)2拼接形成物理地址(010010 0101 1100)2即(125C)16。

(2)逻辑地址(103C)16的页号为4，页号合法，但该页未装入内存，故产生缺页中断。

3

操作系统常见题解析及模拟题内容

(3)逻辑地址(1A5C)16的页号为6，为非法页号，故产生越界中断。

【例10】现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要8 ms；若被替换的页已被修改过，则处理一个缺页中断需要20 ms。内存存取时间为lμs，访问页表的时间可忽略不计。假定70％被替换的页被修改过，为保证有效存取时间不超过2μs，可接受的最大缺页率 …… 此处隐藏：3860字，全部文档内容请下载后查看。喜欢就下载吧 ……