操作系统 --- 存储器管理

一、简答题

1.存储器管理的基本任务，是为多道程序的并发执行提供良好的存储器环境。请问好的存储器环境”应包含哪几个方面？

答：

2.内存保护是否可以完全由软件实现？为什么？

答：内存保护的主要任务是确保每道程序都只在自己的内存区内运行。这就要求系统能对每条指令所访问的地址进行越界检查。若发生越界,系统应能立即发现,并发出越界中断请求,以抛弃该指令。若每次检查完全由软件实现,则每执行一条指令时,都要增加若干条指令去执行越界的检查功能,这无疑将降低程序的执行速度,因此,越界检查通常由硬件实现,并使指令的执行与越界检查功能并行执行,从而不使程序的运行速度降低。当然,对发现有越界后的处理需与软件配合来完成。因此说内存保护功能是由硬件和软件协同完成的。

3.请解释什么是重定位？为什么要重定位？

答：重定位：允许作业在运行过程中在内存中移动的技术,必须获得硬件地址变换机构的支持。即在系统中增加一个重定位寄存器,用它来装入程序在内存中的起始地址。程序在执行时,真正访问的内存地址是相对地址与重定位寄存器中的地址相加而成的,这就叫做重定位。在连续分配方式中,为了利用“碎片”将作业装入,需要将内存中分散的小分区拼接成大分区,称为”拼接”或”紧凑”,但由于经过紧凑后的用户程序在内存中的位置发生了变化,若不对程序和数据的地址进行修改, 程序将无法执行,所以必须进行重定位。

4.动态重定位的实现方式有哪几种？

答：

5.可采用哪几种方式将程序装入内存？它们分别适用于何种场合？

答:

(1) 绝对装入方式,适用于单道程序系统。

(2) 可重定位装入方式,适用于分区式存储管理系统。

(3) 动态运行时装入方式,适用于分页、分段式存储管理系统。

根据信息的性质来划分。(3)分页的作业地址空间是一维的,而分段作业地址空间则是二维的。

6.何谓静态链接？静态链接时需要解决哪两个问题？

答：

静态链接的定义：程序运行之前，先将各目标及它们所需的库函数链接成一个完整的装配模块，以后不再拆开，这种事先进行链接的方式称为。

7.编写程序时，源代码必须经过编译和链接生成目标代码，请问什么是链接？链接主要解决了什么问题？简述链接的主要类型及其优缺点。

答：

             链接（Linking） 是计算机程序构建过程中的一个阶段，其主要任务是将一个或多个由编译器生成的目标文件（包括库文件）组合成一个可执行文件、共享库或者其他类型的目标代码。链接主要解决的问题包括：

          符号解析 ：编译时，函数和变量的具体地址尚未确定。这些未确定的函数和变量被称为“外部符号”。链接器的任务之一是找到这些符号的真实地址，并替换相应的引用。

         空间和地址分配：链接器为每个模块分配空间，并决定每个函数和变量在最终输出中的地址。

         库处理：程序员经常使用标准库或其他库中的函数。链接器从库中选择所需的模块并将其包含在最终的可执行文件中。

链接的主要类型包括：

静态链接 
  优点：
     - 生成的可执行文件是独立的，不依赖于外部的库文件，方便部署和分发。
     - 有时可能会有更好的性能，因为所有的代码都在一个单一的二进制文件中。
  缺点：
     - 如果多个程序使用相同的库，静态链接会导致每个程序都有库的一个副本，浪费磁盘和内存资源。
     - 如果库更新，需要重新链接和部署应用程序。

动态链接：
   -优点：
     - 节省磁盘空间和内存，因为多个运行的程序可以共享同一个库的副本。
     - 库更新时，通常不需要重新链接和部署应用程序。
   缺点：
     - 运行时需要库文件。如果库文件丢失或与应用程序版本不兼容，可能会导致程序无法运行。
     - 有时可能有额外的性能开销，因为需要解析动态符号和加载共享库。

在实际开发中，静态链接和动态链接各有应用场景，选择哪种链接方式取决于项目的具体需求和目标。

8.为什么要引入对换？对换可分为哪几种类型？

答：答:在多道环境下,一方面,在内存中的某些进程由于某事件尚未发生而被阻塞,但它却占用了大量的内存空间,甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况;另一方面,却又有着许多作业在外存上等待,因无内存而不能进入内存运行的情况。显然这对系统资源是一种严重的浪费,且使系统吞吐量下降。为了解决这一问题,在操作系统中引入了对换(也称交换)技术。 可以将整个进程换入、换出,也可以将进程的一部分(页、段)换入、换出。前者主要用于缓解目前系统中内存的不足,后者主要用于实现虚拟存储。

9.在对换技术中，对文件区管理的目标和对对换空间管理的目标有何不同？

答：

         对文件区管理的主要目标是提高文件存储空间的利用率，然后才提高对文件的访问速度，因此，对文件区空间的管理采取离散分配方式。

        对对换空间管理的主要目标是提高进程换入和换出的速度，然后才是提高文件存储空间的利用率，因此，对对换区空间的管理采取连续分配方式，较少的考虑外存中的碎片问题。

10.为什么说分段系统较分页系统更易实现信息共享与保护？

答:

        无论是分页系统、还是分段系统,都允许多个进程共享程序中的代码或公共数据。分页系统实现页共享的方法是,在共享进程中将共享页对应的页表项指向同一个内存块。由于分页系统的地址空间是一维的,页的划分由系统自动进行,因此会造成共享代码或数据与非共享代码或数据共处一页的情况,从而使信息的共享变得十分困难。而分段系统则在用户编程时,自然地进行分段的划分,每个分段中的信息具有相对完整的逻辑意义,正好与分段存储系统相适应,因此它比分页更容易实现信息的共享。 

        对信息的保护来说,也是按信息的逻辑单位进行保护,也与分段存储系统相适应,OS应保证用户进程只按允许的方式访问共享信息,而对他人的非共享信息则不允许进行任何形式的访问。分段系统比分页系统更容易实现信息的保护,我们可按各个分段的含义来对每个分段进行不同的保护,如子程序段的存取权限是只能执行,数据段的存取权限是可读可写等。

11.提高内存利用率的途径主要有哪些？

答：

(1)改连续分配方式为离散分配方式;

(2)增加对换和覆盖机制;

(3)引入动态机制;

(4)引入虚拟存储器机制;

(5)引入存储器共享机制。

二、计算题

12.假设一个分页存储系统具有快表，多数活动页表项都可以存在于其中若页表放在内存中，内存访问时间是1ns，快表的命中率是85%，快表的访问时间为0.1ns，财效存取时间为多少？

答：

        在有快表的分页存储系统中，计算有效存取时间时，需注意访问快表与访问内存的时间关系。通常系统中，先访问快表，未命中时再访问内存；但如果题中有具体的说明，计算时则应注意区别。 计算过程：[(0.1+1)×85%+(0.1+1+1)×(1-85%)]μs=1.25μs。

 理论： 

        在这个分页存储系统中，当需要访问内存时，系统首先查找快表（TLB）。如果找到了对应的页表项（即快表命中），则直接使用该信息进行内存访问；如果没有找到（即快表未命中），则需要首先从内存中查找页表项，然后再访问实际的数据。

1. 快表命中：此时的访问时间包括查找快表的时间和1次实际的内存访问时间。

2. 快表未命中：此时的访问时间包括查找快表的时间、从内存中获取页表项的时间以及1次实际的内存访问时间。

13.对一个将页表存放在内存中的分页系统：
（1）如果访问内存需要0.2μs，则有效访问时间为多少？
（2）如果加一快表，且假定在快表中找到页表项的概率高达90%，则有效访问时间又s是多少（假定查快表须花费的时间为0）？

答：

(1)不使用快表：

每次内存访问实际上需要两次真正的内存访问：一次是为了获取页表项，一次是为了获取实际数据。

所以有效访问时间 = 2 × 内存访问时间 = 2 × 0.2μs = 0.4μs

所以，有效访问时间为0.4μs。

(2)使用快表：

快表（或称为TLB：Translation Lookaside Buffer）用于缓存页表项，大大减少了页表查询的时间。

考虑两种情况：

1. 快表命中：此时只需1次内存访问即可。
2. 快表未命中：此时需要2次内存访问。

有效访问时间 = 快表命中概率 × 1次内存访问时间 + 快表未命中概率 × 2次内存访问时间 = 0.9 × 0.2μs + 0.1 × 0.4μs = 0.18μs + 0.04μs = 0.22μs

14.某系统采用分页存储管理方式，拥有逻辑空间32页，每页2KB，拥有物理空间1MB。
（1）写出逻辑地址的格式。
（2）若不考虑访问权限等，则进程的页表有多少项？每项至少有多少位？
（3）如果物理空间减少一半，则页表结构应相应地做怎样的改变？

答：

由题意：逻辑空间 = 32页        每页大小 = 2KB = (2^{11})B (因为1KB = 2^{10})B)
物理空间 = 1MB = (2^{20})B

(1) 写出逻辑地址的格式： 

逻辑地址由页号和页内地址组成。页号用于索引页表，而页内地址表示在该页中的偏移量。

- 页号（Page Number）：由于总共有32页，所以需要(log_2 32 = 5)位来表示。
  
- 页内地址（Page Offset）：由于每页大小为2KB = (2^{11})B，所以需要11位来表示。

因此，逻辑地址格式为：[5位页号 | 11位页内地址]

**(2) 若不考虑访问权限等，则进程的页表有多少项？每项至少有多少位？**

- 页表的项数与逻辑空间的页数相同，即32项。
- 每一项的大小是决定于物理地址空间的。1MB的物理空间对应的页数是：( frac{1MB}{2KB} = 512)页。因此，需要(log_2 512 = 9)位来表示物理页号。

所以，每项至少有9位。

**(3) 如果物理空间减少一半，则页表结构应相应地做怎样的改变？**

物理空间减少一半意味着新的物理空间为0.5MB = (2^{19})B。与2KB每页相除，得到新的物理空间页数为256页。因此，新的物理页号需要(log_2 256 = 8)位来表示。

因此，当物理空间减少一半时，页表中的每项从原来的9位减少到8位。

15.已知某分页系统，内存容量为64KB，页面大小为1KB，对一个4页大的作业，其)
1、2、3页分别被分配到内存的2、4、6、7块中。
（1）将十进制的逻辑地址1023、2500、3500、4500变换为物理地址。
（2）以十进制的逻辑地址1023为例，画出地址变换过程图。

答：

由题意：

        内存容量 = 64KB        页面大小 = 1KB = 210210B    一个作业的页面映射如下：1→2,2→4,3→6,4→71→2,2→4,3→6,4→7

        因为每页是1KB，所以逻辑地址的低10位（0-9位）是页内地址，而更高的位是用于表示页号。

(1) 将十进制的逻辑地址1023、2500、3500、4500变换为物理地址：

• 1023的逻辑地址：

  • 页号：1023/1024= 0（第一页）
  • 页内地址：1023 % 1024 = 1023
  • 物理页号：2
  • 物理地址 = 2 × 1024 + 1023 = 3071

• 2500的逻辑地址：

  • 页号：2500/1024 = 2（第三页）
  • 页内地址：2500 % 1024 = 452
  • 物理页号：6
  • 物理地址 = 6 × 1024 + 452 = 6596

• 3500的逻辑地址：

  • 页号：3500/1024 = 3（第四页）
  • 页内地址：3500 % 1024 = 932
  • 物理页号：7
  • 物理地址 = 7 × 1024 + 932 = 7932

• 4500的逻辑地址：

  • 页号：4500/1024​ = 4
  • 由题意，显然只有4页，所以4500这个逻辑地址是无效的，不能转换为物理地址。

（2）具体图像如下：

16.已知某系统页面长4KB，每个页表项的大小为4B，采用多层分页策略映射64位的用户地址空间。若限定最高层页表只占1页，问它可采用几层分页策略。

答：

        方法一:由题意可知,该系统的用户地址空间为2(64)B,而页的大小为4KB,故作业最多可有(2^64)/(2^12)(即2^52)个页,其页表的大小则为2^(52)*4即2^(54)B。因此,又可将页表分成2(42)个页表页,并为它建立两级页表,两级页表的大小为2(44)B。依次类推,可知道它的3、4、5、6级页表的长度分别是2(34)B、2(24)B、2(14)B、2(4)B,故必须采取6层分页策略。

         方法二:页面大小为4KB=2^(12)B,页表项4B=2^(2)B,因此一个页面可以存放2^(12)/2^(2)=2(10)个页表项,因此分层数=INT[64/10]=6层。

17.对于表5-2所示的段表，请将逻辑地址（0,137），（1,4000)，（2,3600)，（5,230)
变换成物理地址。
 

段表 5-2

段号	内存起始地址	段长
0	50K	10KB
1	60K	3KB
2	70K	5KB
3	120K	8KB
4	150K	4KB

答：

(0,137)对应的物理地址为:50K+137 = 50*1024+137 = 51337;

(1,4000)的段内偏移地址越界,是一个不合法逻辑地址;

(2,3600)对应的物理地址为:70K+3600 = 75280

(5,230)的段号越界,是一个不合法逻辑地址。

三、综合应用题

18.某系统采用动态分区分配方式管理内存，内存空间为640KB，低端40KB存放OS。系统为用户作业分配空间时，从低地址区开始。针对下列作业请求序列，画图表示使用首次适应算法进行内存分配和回收后内存的最终映像。作业请求序列如下：
作业1申请200KB，作业2申请70KB；作业3申请150KB，作业2释放70KB；作业4申请80KB，作业3释放150KB；作业5申请100KB，作业6申请60KB；作业7申请50KB，作业6释放60KB。

答：

内存分配和回收的过程：

2）

19.某OS采用分段存储管理方式，用户区内存为512KB，

空闲块链入空闲块表，分配时截取空闲块的前半部分（小地址部分）。初始时全部空闲。执行申请、释放操作序列request(300KB）、request(100KB)、release (300KB)、request (150KB)、request(5OKB)、request（90KB)后：
（1）若采用首次适应算法，则空闲块表中有哪些空闲块（指出大小及起始地址）？
（2）若采用最佳适应算法，则空闲块表中有哪些空闲块（指出大小及起始地址）？
（3）若随后又要申请80KB，则针对上述两种情况会产生什么后果？这说明了什么问题？

答：

由题意给定：用户区内存大小 = 512KB；初始时，所有内存都是空闲的，即有一个空闲块从地址0开始，大小为512KB。

执行给定的操作序列：

request(300KB)：分配300KB的内存                 request(100KB)：分配100KB的内存
release(300KB)：释放第一个申请的300KB         request(150KB)：分配150KB的内存
request(50KB)：分配50KB的内存                request(90KB)：分配90KB的内存

我们分别考虑两种算法：

(1) 首次适应算法：

1. 分配300KB后，空闲块：[300KB, 512KB-300KB = 212KB]
2. 分配100KB后，空闲块：[400KB, 112KB]
3. 释放300KB后，空闲块：[0KB, 300KB], [400KB, 112KB]
4. 分配150KB后，空闲块：[150KB, 150KB], [400KB, 112KB]
5. 分配50KB后，空闲块：[200KB, 100KB], [400KB, 112KB]
6. 分配90KB后，空闲块：[200KB, 100KB], [490KB, 22KB]

(2) 最佳适应算法：

1. 分配300KB后，空闲块：[300KB, 212KB]
2. 分配100KB后，空闲块：[400KB, 112KB]
3. 释放300KB后，空闲块：[0KB, 300KB], [400KB, 112KB]
4. 分配150KB后，空闲块：[0KB, 150KB], [400KB, 112KB]
5. 分配50KB后，空闲块：[0KB, 100KB], [450KB, 62KB]
6. 分配90KB后，空闲块：[0KB, 10KB], [450KB, 62KB]

(3) 随后申请80KB的后果：

        对于首次适应算法：可以从200KB位置开始的100KB空闲块中分配80KB。剩余的空闲块为：[280KB, 20KB], [490KB, 22KB]。
  
        对于最佳适应算法：可以从450KB位置开始的62KB空闲块中分配80KB，但这个块太小，所以这次分配请求会失败。剩余的空闲块不变，为：[0KB, 10KB], [450KB, 62KB]。

        最佳适应算法可能会导致大量的小空闲块，这使得大块的内存请求更有可能失败，即使总的可用空闲空间可能足够大。这说明了碎片化问题，特别是内部碎片问题。最佳适应策略可能会导致更多的内部碎片，而首次适应策略可能会导致内存的低效利用，但在这种情况下，它能够满足80KB的请求。

20.某系统的空闲分区如表5-3所示，采用可变分区分配策略处理作业。现有作业序列96KB、20KB、200KB，若采用首次适应算法和最佳适应算法来处理这些作业序列，则哪种算法能满足该作业序列的请求？为什么？

表5-3空闲分区表

段号	内存起始地址	段长
0	32K	100KB
1	10KB	150K
2	5KB	200K
3	218KB	220K
4	96KB	530K

答：

解:若采用最佳适应算法,在申请96K存储区时,选中的是5号分区,5号分区大小与申请空间大小一致,应从空闲分区表中删去该表项;接着申请20K时,选中1号分区,分配后1号分区还剩下12K;最后申请200K,选中4号分区,分配后剩下18K。显然采用最佳适应算法进行内存分配,可以满足该作业序列的需求。为作业序列分配了内存空间后,空闲分区表如表(a)所示。

若采用首次适应算法,在申请96K存储区时,选中的是4号分区,进行分配后4号分区还剩下122K;接着申请20K,选中1号分区,分配后剩下12K;最后申请200K,现有的五个分区都无法满足要求,该作业等待。显然采用首次适应算法进行内存分配,无法满足该作业序列的需求。这时的空闲分区表如表(b)所示。

分配后的空闲分区表

(a)

分区号	大小	起始地址
1	12K	100K
2	10K	150K
3	5K	200K
4	18K	220K

(b)

分区号	大小	起始地址
1	12K	100K
2	10K	150K
3	5K	200K
4	122K	220K
5	96K	530K