5.3　例题解答

例1　什么是动态重定位？它有什么特点？

答：动态重定位是指在程序执行期间，由系统硬件完成从逻辑地址到物理地址的转换。

动态重定位的特点：具有给用户程序任意分配内存区的能力；可以将程序分配到不连续的存储区中；在程序运行之前可以只装入它的部分代码即可投入运行，不执行的代码就不做地址映射的工作，这样节省了CPU的时间；可实现虚拟存储，向用户提供一个比主存的存储空间大得多的地址空间；重定位寄存器的内容由操作系统用特权指令来设置，比较灵活；实现动态重定位必须有硬件支持，并有一定的执行时间延迟，且实现存储管理的软件算法比较复杂。现代计算机系统中都采用动态地址映射技术。

例2　某页式管理系统，内存为2GB，分成了1024块，块号为0、1、2、…、1023。假设某个作业有4页，分别装入内存的12、14、100、166块。

1）试问该作业的大小是多少？

2）给出该作业的每一页在内存中的起始地址。

答：1）设该作业的大小为N，内存分为1024块，则物理块或页面的大小为：

2¹⁰MB/2¹⁰=1MB

该作业全部装入内存，需要占用4个物理块，则

3MB＜N≤4MB

2）该作业的第0号页在内存中的起始地址为：1MB×12=12MB，该作业的第1号页在内存中的起始地址为：1MB×14=14MB，该作业的第2号页在内存中的起始地址为：1MB×100=100MB，该作业的第3号页在内存中的起始地址为：1MB×166=166MB。

例3　在一个分页存储管理系统中，某作业的页表如表5-1所示。已知页面大小为1024字节，试将逻辑地址1011、2148、3000、5012转化为相应的物理地址。

答：逻辑地址转为物理地址的方法是，首先，计算该逻辑地址所在的页号和页内偏移：

页号=逻辑地址/页面大小（取整）

页内偏移=逻辑地址%页面大小（取余）

其次，在确定该逻辑地址合法的情况下，查页表，根据页号得到对应的物理块号。最后，利用以下公式得到对应的物理地址：

块号×页面大小+页内偏移

利用上述方法，可得：

逻辑地址1011相应的物理地址为：2×1024+1011=3059，逻辑地址2148相应的物理地址为：1×1024+100=1124，逻辑地址3000相应的物理地址为：1×1024+952=1976，无法求出逻辑地址5012相应的物理地址，因为该逻辑地址非法，它的页号超出页表长度。

例4　某操作系统采用分区存储管理技术。操作系统在低地址占用了100KB的空间，用户区主存从100KB处开始占用512KB。开始时，用户区全部空闲，分配时截取空闲分区的低地址部分作为已分配区。在执行申请、释放操作序列后，请求300KB、请求100KB、释放300KB、请求150KB、请求50KB、请求90KB，请回答以下问题：

1）若采用首次适应分配算法，此时主存中有哪些空闲分区？

2）若采用最佳适应分配算法，此时主存中有哪些空闲分区？

3）若随后又要请求80KB，采用以上两种方法分别会产生什么情况?

答：1）采用首次适应分配算法：

请求300KB：地址块100～399被占用；地址块400～612空闲。

请求100KB：地址块100～399、400～499被占用；地址块500～612空闲。

释放300KB：地址块400～499被占用；地址块100～399、500～612空闲。

请求150KB：地址块100～249、400～499被占用；地址块250～399、500～612空闲。

请求50KB：地址块100～249、250～299、400～499被占用；地址块300～399、500～612空闲。

请求90KB：地址块100～249、250～300、300～389、400～499被占用；地址块390～399、500～612空闲。

产生空闲块两个，块1，首地址390，块大小为10KB；块2，首地址500，块大小为112KB。

2）采用最佳适应分配算法：

请求300KB：地址100～399被占用；地址400～612空闲。

请求100KB：地址100～399、400～499被占用；地址500～612空闲。

释放300KB：地址400～499被占用；地址100～399、500～612空闲。

请求150KB：地址100～249、400～499被占用；地址250～399、500～612空闲。

请求50KB：地址100～249、400～499、500～549被占用；地址250～399、550～612空闲。

请求90KB：地址100～249、250～339、400～499、500～549被占用；地址340～399、550～612空闲。

产生空闲块两个，块1，首地址340，块大小为60KB；块2，首地址550，块大小为62KB。

3）若随后又要请求80KB，则采用首次适应分配算法可以分配，因为块2空闲空间为112KB＞80KB；采用最佳适应分配算法不可分配，因为块1和块2空闲空间均小于80KB。

例5　在虚拟存储系统中，当系统分配给一个作业的物理块数分别为3和4时，并且此作业的页面走向为1、2、3、4、1、2、5、1、2、3、4、5。

1）采用FIFO算法，分别计算程序访问过程中所发生的缺页次数和缺页率。要求给出页面置换过程。

2）计算结果说明了什么问题？

答：1）采用FIFO算法，当分配的页数为4时，页面置换过程如下：

缺页次数为9次，缺页率=9/12=75%。

采用FIFO算法，当分配的页面数为4时，页面置换过程如下：

缺页次数为10次，缺页率=10/12=83.3%。

2）计算结果说明了缺页率随着所分配的物理块数的增加而增加，即Belady现象。原因是根本没有考虑程序执行的动态特征。

例6　某进程已分配到4个物理块，如表5-2所示（所有数字都为十进制数，且以0开始）。当进程访问第4页时，产生缺页中断，请分别用FIFO、LRU、NRU算法决定缺页中断服务程序，选择换出的页面。

答：FIFO算法：根据算法规则，最先进入的页应当被选择换出，因此访问第4页时，缺页中断程序选择的是3号页。该页的修改位为1，在换出主存后应进行回写，即重新保存。

LRU算法：根据算法规则，最近的一次访问时间离当前最远的页应当被选择换出；因此缺页中断程序选择的是1号页。

NRU算法：根据算法规则，应当选择访问位为0的页换出主存，又选择修改位为0的页换出主存（省去保存操作），因此缺页中断程序选择将1号页换出。

例7　某请求分页管理系统中，如果页面在内存中，一次内存访问需要2微秒。如果页面不存在，若有空闲物理块或者被置换出内存的页没有被修改，则需要4毫秒；如果置换的页已经修改，则需要10毫秒。如果缺页率为20%，其中置换出的页有30%被修改，则有效访问时间为多少？

答：有效访问时间=80%×没有产生缺页情况下所需时间+20%×（30%×缺页时置换页被修改情况下所需时间+70%×缺页时置换页未被修改或有空闲物理块情况下所需时间）

=80%×2微秒+20%×（30%×（2微秒+10毫秒+2微秒）+70%×（2微秒+4毫秒+2微秒））

=1162.6微秒

例8　对访问串：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为3、4时，使用FIFO和LRU算法的缺页次数。结果说明了什么？

答：首先采用FIFO，当m=3时，缺页次数=9；m=4时，缺页次数=10。

采用LRU算法，当m=3时，缺页次数=10；m=4时，缺页次数=8。

结果说明：FIFO有Belady异常现象，即不满足驻留集增大，缺页次数一定减小的规律；另外，在m=3时，LRU的缺页次数比FIFO要多，所以LRU算法并不总优于FIFO，还要看当前访问串的特点。