操作系统-第四章作业

一、问答题

1. 简述存储管理的功能

• 内存空间的分配与回收：负责为进程分配所需内存空间，进程结束后回收其占用内存，如分区式存储管理中，根据作业大小分配固定或动态分区，进程结束时将分区状态置为未分配。

• 地址转换（地址映射）：将用户程序中的逻辑地址转换为内存物理地址，使程序能正确访问内存单元。例如静态重定位在程序装入时完成转换，动态重定位在程序执行过程中转换。

• 内存信息的共享与保护：实现内存中程序和数据的共享，同时防止进程间相互破坏。通过设置访问权限等措施，确保各进程在合法范围内访问内存资源。

• 内存扩充：利用虚拟存储技术等手段，从逻辑上扩充内存容量。如分页式、分段式存储管理方式为虚拟存储技术提供支持，使系统能运行更大程序。

1. 简述存储管理方式及其优缺点

• 分区式存储管理

    - 优点：允许多个作业共享主存空间，实现多道程序设计，提高资源利用率；所需硬件支持少，管理算法简单，易于实现。

    - 缺点：内存利用率仍不高，存在碎小空闲区（碎片）问题；作业大小受分区大小限制；难以实现分区间信息共享。

• 分页式存储管理

    - 优点：有效解决内存碎片问题，提高内存利用率；通过页表实现逻辑地址到物理地址的转换，便于内存管理。

    - 缺点：页的划分可能破坏程序逻辑完整性；程序和数据共享复杂；地址转换需访问页表，可能影响系统性能，虽可通过快表优化，但仍需额外硬件支持。

• 分段式存储管理

    - 优点：保留程序逻辑结构，便于程序和数据的共享与保护；段可动态增长，适应程序需求。

    - 缺点：段大小不一可能产生内存碎片；内存管理和地址转换复杂，需较多硬件支持。

• 段页式存储管理

    - 优点：结合分页和分段优点，提高内存利用率，利于程序和数据共享与保护。

    - 缺点：管理数据结构复杂，增加系统开销；地址转换需多次查表，效率相对较低。

1. 简述分区存储管理中碎片产生的原因

• 固定分区法：分区大小固定，作业大小若小于分区，剩余空间无法利用形成内部碎片；分区划分后不变，作业大小受分区限制，易造成空间浪费。

• 动态分区法：作业装入和释放动态进行，释放后的空间不连续，形成外部碎片；最先适应法等分配算法优先利用低地址空闲区，导致低地址端留下小空闲分区。

1. 简述3种常用的页面置换算法

• 先进先出算法（FIFO）：置换时选择在内存中驻留时间最长的页淘汰。如为进程分配一定物理块，按页面访问顺序，新页面调入且内存满时，淘汰最先进入内存的页面。该算法内存利用率不高，因CPU访问地址空间不一定线性，如循环语句执行时可能频繁访问近期使用过的页面。

• 最近最久未使用页面置换算法（LRU）：选择最近一段时间内最久未使用的页淘汰。其基于若页被访问，可能很快再被访问；反之，长时间未访问，近期也不太可能访问的思想。实现开销大，实际常用近似算法。

• 最佳适应算法（Best Fit）：按空闲区大小从小到大排序组成空闲区表。申请空闲区时，从表头找满足要求的最小空闲区。该算法优先利用与程序需求大小最接近的空闲区，但会剩下较多小空闲区。

1. 何谓虚拟存储技术

• 虚拟存储技术是一种仅将作业部分装入内存即可运行作业的存储系统，具有请求调入和置换功能，能从逻辑上扩充内存容量。它利用外存（磁盘）模拟无限大虚拟存储空间，基于程序局部性原理，包括时间局限性（指令执行后不久可能再次执行）和空间局限性（访问存储单元后不久可能访问附近单元）。虚拟存储器最大容量为主存与辅存容量之和，实际容量受计算机寻址位数限制，如32位CPU，虚存容量为4G。

1. 为什么要进行地址转换

• 用户程序经编译后的逻辑地址不能直接用于访问内存物理单元，需通过地址转换将逻辑地址映射为物理地址，才能准确定位程序和数据在内存中的实际存储位置，确保程序正确执行。

1. 什么是物理地址？什么是逻辑地址

• 物理地址：内存中物理存储单元从统一基地址顺序编址的地址，又称绝对地址，是数据在内存中的实际存储地址，其集合构成物理地址空间（主存地址空间），是一维线性空间。

• 逻辑地址：用户程序编译后，目标模块以0为基地址顺序编址的地址，又称相对地址，其集合构成逻辑地址空间，编址从0开始，可为一维线性或多维空间。

1. 什么是内碎片、外碎片

• 内碎片：在分页式存储管理中，进程最后一页未填满形成内碎片；固定分区法中，分区大于作业大小的剩余空间也属于内碎片。

• 外碎片：动态分区法中，作业释放空间不连续形成的小空闲区分布在已分配分区之间，称为外碎片。

1. 动态分页存储管理方式中为什么要扩充页表

• 为实现请求分页技术，需记录页面相关控制管理信息。中断位用于判断页在内存还是外存，便于处理缺页中断；修改位查看页在内存中是否被修改，决定淘汰时是否回写外存；访问位根据不同算法决定淘汰哪页。这些信息有助于有效管理内存页面，提高内存利用率和系统性能。

1. 什么是页的“抖动”

• 页的“抖动”指刚被淘汰的页不久又被访问，需再次调入，调入后又很快被淘汰，如此反复，使系统大量时间花费在页面调进调出上，严重降低系统性能。

1. 如何理解局部性原理

• 局部性原理指程序执行时，在一段时间内，CPU集中访问程序某部分。包括时间局限性（某指令执行后不久再次执行）和空间局限性（访问某存储单元后不久访问附近单元）。程序执行多为顺序执行，过程调用深度有限，循环语句重复执行，数据结构操作范围小，这些体现了局部性原理。它是虚拟存储技术的理论基础，使程序运行时仅需部分页面在内存，利用外存扩充内存容量成为可能。

1. 什么是静态地址重定位？什么是动态地址重定位？二者有何优缺点

• 静态地址重定位

    - 定义：在程序装入内存前完成逻辑地址到物理地址的转换。

    - 优点：无需硬件支持。

    - 缺点：程序执行前需全部装入内存且不能移动，无法实现虚拟存储技术；占用连续存储空间，难以实现程序和数据共享。

• 动态地址重定位

    - 定义：在程序执行过程中进行重定位，由系统硬件完成逻辑地址到物理地址的转换，装入时不转换，每次访问内存前转换。

    - 优点：内存可非连续分配，为虚拟存储技术实现提供基础，利于程序段共享。

    - 缺点：需要硬件支持，增加系统成本和复杂性。

1. 为什么要扩充存储空间

• 随着计算机应用发展，程序和数据量不断增大，内存容量有限，无法容纳全部程序和数据，导致一些作业因内存不足无法运行。扩充存储空间可利用外存模拟更大内存空间，使更多作业同时运行，提高系统资源利用率和多道程序设计能力，满足用户需求。

1. 如何理解分页的逻辑地址结构是一维的，而分段式是二维的

• 分页的逻辑地址结构：分页管理中，页号从0开始线性递增，程序地址是一维线性结构。逻辑地址分为页号和页内地址两部分，通过页表将页号映射为内存页面号，结合页内地址形成物理地址，整个转换基于一维页号顺序。

• 分段式的逻辑地址结构：分段管理中，操作系统将进程虚拟地址空间分为二维结构，包括段号S和段内位移W。段与段无顺序关系，是二维平面结构，各段长度不等，首地址为0，段内为连续一维线性地址空间且段长可动态增长。地址转换需通过段表找到段起始地址，加上段内位移得到物理地址，涉及段号和段内地址两个维度的映射。

1. 什么是分页存储管理？其主要的数据结构是什么

• 分页存储管理：将程序和数据划分为固定大小的页，内存也分成同样大小的页面（帧、片或页框）。进程的逻辑页可分散存于内存不同页面，通过页表记录逻辑页与物理页面的对应关系，实现非连续内存分配，提高内存利用率。

• 主要数据结构：页表，包含页号和页面号等信息，用于实现逻辑地址到物理地址的转换。

1. 什么是分段存储管理？其主要的数据结构是什么

• 分段存储管理：保留程序逻辑完整性，将程序分段，由多个逻辑段组成，系统按段分配内存，各段大小不等且可动态增长。每段在内存中占据连续空间，但段间可不连续存放，通过段表记录段的相关信息，便于实现程序和数据共享与保护。

• 主要数据结构：段表，记录段号、段长、段地址等信息，用于实现逻辑地址到物理地址的转换及内存管理。

1. 什么是段页式存储管理？其主要的数据结构是什么

• 段页式存储管理：结合分页和分段优点，将作业地址空间分为逻辑段，每段再分若干固定页；主存空间管理同页式，分若干与页面大小相同存储块。地址结构包含段号、页号和页内位移，通过段表和页表配合实现地址转换和内存管理，提高内存利用率，利于程序和数据共享与保护。

• 主要数据结构：段表（管理内存分配与释放、缺段处理、存储保护和地址变换等）和页表（将段内虚页变换成内存中的实际页面）。

二、计算题

1. 在页式虚拟存储管理的计算机系统中，运行一个共有8页的作业，且作业在主存中分配到4块主存空间，作业执行时访问页面顺序为7，0，1，2，3，0，4，3，2，3，6，7，3，1，5，7，6，2，6，7。请问用FIFO和LRU调度算法时，它们的缺页中断率分别是多少?

• 已知作业共8页，主存分配4块空间，页面访问顺序为7，0，1，2，3，0，4，3，2，3，6，7，3，1，5，7，6，2，6，7。

• FIFO算法

    - 采用先进先出置换策略，内存块初始为空，按页面访问顺序依次调入。当内存已满且有新页面访问时，淘汰最先进入内存的页面。

    - 例如，开始时依次调入7、0、1、2，此时内存已满。当访问3时，淘汰7，调入3；访问0时，0已在内存；访问4时，淘汰0，调入4；以此类推。

    - 计算缺页次数，可得缺页10次。总访问页面数为20次，所以缺页中断率 = 10 / 20 = 50%。

• LRU算法

    - 选择最近最久未使用的页面淘汰。每次访问页面后，更新页面的使用时间记录。

    - 初始调入7、0、1、2，访问3时，2最久未使用，淘汰2，调入3；访问0时，0刚被使用，不淘汰；访问4时，1最久未使用，淘汰1，调入4；依此类推。

    - 经计算，缺页8次，缺页中断率 = 8 / 20 = 40%。

1. 某动态分页系统中有一个具有5个页的进程在内存中分别存放在9、4、10、20、13块中，系统页大小为1K，试问当该进程调用2022单元的内容时，将访问内存哪个单元？

• 已知进程有5个页，分别存放在9、4、10、20、13块中，系统页大小为1K，要访问2022单元。

• 首先计算页号：2022 / 1024 = 1（整除），即页号为1。

• 页内偏移量为：2022 % 1024 = 998。

• 根据页表，页号1对应的内存块号为4。

• 所以访问的内存单元地址为：4 * 1024 + 998 = 5094。

1. 某系统采用动态地址重定位，现有一个7页大小的进程在时刻T0其前三页内容已经调入内存，系统以2K作为页大小，试问当进程访问6300单元内容时，会有什么情况发生？

• 已知进程有7页，页大小为2K，时刻T0前三页已调入内存，要访问6300单元。

• 计算页号：6300 / 2048 = 3（整除），页内偏移量为：6300 % 2048 = 184。

• 由于进程前三页已调入内存，页号3对应的页在内存中，不会产生缺页中断。

• 系统根据动态地址重定位机制，将逻辑地址（页号3和页内偏移量184）转换为物理地址，可正常访问内存单元。

1. 某分页存储管理系统，每页可存放200个整型数，现有一程序(C语言)按方法A执行，或按方法B执行时，计算两种方法的缺页率。假设，该进程对应的代码已经调入内存。

• 已知每页可存放200个整型数，进程代码已调入内存。

• 对于方法A（按先行后列次序存储），例如有一个100×100的矩阵，当按行访问时，每页存放200个整数，访问第0行时，需调入第1页，之后第1行到第49行数据均在已调入的第1页中，共发生1次缺页中断；访问第50行时，需调入第

1. 在可变分区管理中下，按地址排列的内存空闲区为：10KB，4KB，20KB，18KB，7KB，9KB，12KB，15KB。对于下列的连续存储区的请求：12KB，10KB，9KB，问：使用首次适应算法、最佳适应算法、最坏适应算法，以上连续存储区的各使用哪个空闲区？
   • 已知内存空闲区按地址排列为：10KB，4KB，20KB，18KB，7KB，9KB，12KB，15KB，连续存储区请求为：12KB，10KB，9KB。
   • 首次适应算法
     • 从内存低地址开始查找，找到第一个能满足请求大小的空闲区。对于12KB请求，分配10KB空闲区，剩余2KB碎片；对于10KB请求，分配18KB空闲区，剩余8KB碎片；对于9KB请求，分配12KB空闲区，剩余3KB碎片。
   • 最佳适应算法
     • 按空闲区大小从小到大排序。对于12KB请求，分配12KB空闲区；对于10KB请求，分配10KB空闲区；对于9KB请求，分配9KB空闲区，均无碎片产生。
   • 最坏适应算法
     • 按空闲区大小从大到小排序。对于12KB请求，分配20KB空闲区，剩余8KB；对于10KB请求，分配15KB空闲区，剩余5KB；对于9KB请求，分配10KB空闲区（已分配部分后的剩余空间），剩余1KB。
2. 某作业J的逻辑空间为4页，分别放在内存2、4、6、8号页面，每页大小2048B，试计算逻辑地址为0A65H的物理地址。
   • 已知作业逻辑空间为4页，分别放在内存2、4、6、8号页面，每页大小2048B，逻辑地址为0A65H。
   • 先将逻辑地址转换为二进制：0A65H = 0000 1010 0110 0101B。
   • 计算页号：0000 10（高6位） = 2（十进制），即页号为2。
   • 页内偏移量：010 0110 0101（低10位） = 1109（十进制）。
   • 根据页表，页号2对应的内存页面号为6。
   • 物理地址 = 6 * 2048 + 1109 = 13397（十进制） = 3425H。

3. 某段式存储管理中某程序段表如表4-7所示，请简述分段式逻辑地址的转换为物理地址的过程；分别计算逻辑地址：[0,430]、[1,10]、[2,500]、[3,400]、[4,20]、[5,100]的物理地址(每一个逻辑地址方括号中的第一个元素为段号，第二个元素是段内地址)；在分段式存储管理下，存取主存中的某一条指令或数据至少需要访问内存几次？

   

   • 逻辑地址转换为物理地址的过程
     • 首先根据逻辑地址中的段号，在段表中查找对应的段表项，获取该段的起始地址。然后将段起始地址与逻辑地址中的段内地址相加，得到物理地址。若段内地址大于段长，则产生越界中断。
   • 计算各逻辑地址的物理地址
     • 对于逻辑地址[0,430]：根据段表，段号0的段长为600，段内地址430未越界。段起始地址为2000，物理地址 = 2000 + 430 = 2430。
     • 对于逻辑地址[1,10]：段号1的段长为500，段内地址10未越界。段起始地址为3000，物理地址 = 3000 + 10 = 3010。
     • 对于逻辑地址[2,500]：段号2的段长为400，段内地址500越界，产生越界中断。
     • 对于逻辑地址[3,400]：段号3的段长为300，段内地址400越界，产生越界中断。
     • 对于逻辑地址[4,20]：段号4的段长为200，段内地址20未越界。段起始地址为5000，物理地址 = 5000 + 20 = 5020。
     • 对于逻辑地址[5,100]：段号5的段长为100，段内地址100越界，产生越界中断。
   • 存取主存中的指令或数据至少需要访问内存次数
     • 至少需要访问内存2次。第一次访问段表，获取段的起始地址；第二次根据起始地址和段内地址访问物理内存单元。