操作系统【八】

4、对换

在多道程序环境下,一方面,在内存中的某些进程由于某事件尚未发生而被阻塞运行,但它却占用了大量的内存空间,甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况,另一方面,却有很多作业在外存上等待,因无内存而无法进入内存运行的情况,这是对系统资源的浪费,为了解决这个问题,增设了对换设施,对换是把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上,以便腾出足够的内存空间,再把已具备运行条件的进程或者进程所需要的程序和数据调入内存。对换是提高内存利用率的有效措施。如果对换的单位是进程,便称为整体对换或进程对换,为了实现进程对换,系统必须实现对换空间的管理、进程的换出、进程的换入。

对换空间的管理,在具有对换功能的OS中,通常把外存分为文件区和对换区,前者用于存放文件,后者用于存放从内存换出的进程。由于文件通常是较长久的驻留在外存上,文件区的管理主要目标是提高存储空间的利用率,采取离散分配方式,进程通常在对换区中驻留的时间较短暂,对换操作较频繁,故对对换空间管理的主要目标是提高进程换入和换出的速度,采取的是连续分配的方式,较少考虑外存中的碎片问题。

进程的换出,每当进程由于创建子进程而需要更多的内存空间,但又无足够的内存空间情况时,系统应将某进程换出,首先,系统首先选择处于阻塞状态且优先级最低的进程作为换出进程,然后启动磁盘,将该进程的程序和数据传送到磁盘的对换区上,若传送过程没有错误,则可回收该进程所占用的内存空间,并对该进程的进程控制块做相应的修改。

进程的换入,系统定时地查看所有进程的状态,从中找出就绪状态但已换出的进程,将其中换出时间最久的进程作为换入进程,将其换入,直至无换入的进程或无可换出的进程为止。

对换空间的分配与回收,与动态分区方式时的内存分配与回收雷同。

5、基本分页存储管理方式

连续分配,包括固定分区分配和动态分区分配。但前者容易产生内部碎片,后者容易产生外部碎片(虽然可以用紧凑技术解决,但是有一定的成本),都不是理想的解决方案。果允许一个进程直接分散地装入到许多不相邻接的分区中,则无须进行紧凑操作,基于这一思想产生了离散分配方式,如果离散分配的基本单位是页,则称为分页存储管理方式,若为段,则为分段存储管理方式。

通俗:

在连续分配中,一个进程不可被分割,只能整体放入一块连续的内存空间中;但在基本分页存储管理中,允许把一个进程按照固定大小 X 分割为多个部分,同时把内存也按照固定大小 X 分割为多个部分,并把前者对应地放到后者中(不要求连续存放)。通常来说,一个进程的最后一部分会小于 X,这部分若放到内存的某个 X 空间中,则仍然会产生碎片(这种碎片称为页内碎片),要让这种碎片尽可能小,X 也必须尽可能小。

(1)页面与页表

①页面、页框(块)

将用户程序的地址空间分为若干个大小固定的页,对应的内存空间分为与页面 大小相同的块(block)或页框(frame )

分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页,并为各页进行编号,从0开始。相应地,把内存空间分成与页面相同大小的若干个存储块,称为(物理)块或者页框,也同样为它们编号,如0#块,1#块等。在未进程分配内存时,以块为单位将进程的若干个页分别装入到多个可以不相邻接的物理块中,由于进程的最后一页经常装不满一块而形成不可利用的碎片,称之为页内碎片。

==进程:页面==

==内存:块、页框==

在分页系统中的页面其大小应适中,页面若太大,一方面可以是内存碎片减少,有利于提供内存利用率,但是,每一个进程占用的页面较多,导致页表过长,占用太多内存,会降低页面换进换出的效率。页面若太大,可减少页表的长度,提供页面换进换出的速度,但是,内存碎片会增大,所以,也页面大小应适中,通常为512B~8K。

分页地址中的地址结构如下

说明:前一部分为页号P,后一部分为位移量W(或称为页内地址),总共32位,其中0-11位为页内地址,每页大小4KB,12-31位为页号,地址空间最多允许1M页。

②页表

为了能够保证在内存中找到每个页面所对应的物理块,系统为每个进程建立了一张页面映射表,简称为页表。页表项纪录了相应页在内存中对应的物理块号,在配置了页表后,进程执行时,通过查找该表,即可找到每页在内存中的物理块号,页表实现了从页号到物理块号的地址映像

③地址转换

1、十进制地址

左边进程按照 50b 的大小分为 4 个页面,右边内存按照 50b 的大小分为若干个页框:

在程序执行到指令 1 的时候,需要访问地址 80,这是一个逻辑地址,需要转换成对应的物理地址。转换步骤如下:

  • 计算逻辑地址的页号
  • 根据页号找到页号对应页面在内存中的起始地址
  • 计算逻辑地址在当前页面内的偏移量
  • 物理地址 = 起始地址 + 页内偏移量

从左图可以看出,逻辑地址 80 在 1号页面内,而 1 号页面对应的是右图中的红色页框,起始地址为 450;逻辑地址 80 在 1号页面内的偏移量为 30;所以物理地址 = 450 + 30 = 480

也可以用计算的方法,在已知逻辑地址的情况下:

  • ==页号 = 逻辑地址/页面长度,即 80/50 = 1(取整数部分);==
  • ==页内偏移量 = 逻辑地址%页面长度,即 80%50 = 30;==

2、二进制地址

当然,地址实际上是用 32 位二进制数表示的。这时候计算页号和页内偏移量实际上更加简单,因为地址本身已经包含了这两者。以页面/页框大小 4kb 为例:

一个页面 4kb 大小,也即 2^12^b = 4096b 大小。那么,0 号页、1 号页、2 号页的表示就是:

这里会发现,地址的前 20 位(红色部分)表示页号:全是 0 表示 0 号页,末尾 1 表示 1 号页,末尾 10 表示 2 号页……以此类推;地址的剩余(黑色)部分表示页内偏移量。所以说地址本身其实已经包含了这两者的信息。

若页面/页框大小位 1kb,也即 2^10^b =1024b 大小,那么同样可以发现,地址的前 22 位表示页号,地址的剩余部分表示页内偏移量:

总结下来,规律就是:

如果页面/页框大小为 2^k^ b,那么前面部分表示页号,末尾 k 位表示页内偏移量。在页面/页框大小为 2 的整数幂的时候,就可以直接从地址看出页号和页内偏移量,因此建议将页面/页框大小设置为为 2 的整数幂。

(2)地址变换机构

①基本地址变换机构

为了能够将用户地址空间中的逻辑地址变换为内存空间中的物理地址,在系统中必须设置地址变换机构,该机构的基本任务是实现从逻辑地址到物理地址的转换,由于页内地址与物里块内的地址一一对应,无须再进行转换,因此,地址变换机构的任务实际上只是将逻辑地址中的页号转换为内存中的物理块号。又因为页面映射表的的作用就是用于实现从页号到物理块号的变换,因此,地址变换任务是借助页表来完成的

页表的功能可以由一组专门的寄存器来实现,一个页表项用一个寄存器,由于寄存器具有较高的访问速度,因而有利于提高地址变换的速度,但成本较高,且页表项一般会很多,都使用寄存器实现不太现实,因此,页表大多驻留在内存。在系统中只设置一个页表寄存器PTR(Page-Table Register),用于存放页表在内存的始址和页表的长度,平时,进程执行时,页表的始址和页表长度存放在本进程的PCB中,当调度程序调度到某进程时,将这两个数据装入页表寄存器,因此,在单处理机环境下,虽然系统中可以运行多个进程,但只需要一个页表寄存器。

当进程要访问某个逻辑地址中的数据时,分页地址变换机构会自动地将有效地址(相对地址)分为页号和页内地址两部分,再以页号为索引去检索页表,查找操作由硬件执行,在执行检索前,先将页号与页表长度进行比较,若页号大于或等于页表长度,则表示本次访问的地址超越了进程的地址空间,这一错误将被系统发现并产生一个地址越界中断。若未出现错误,则将页表始址加上页号与页表项长度的乘积,便得到该表项在页表中的位置,于是可从中得到该页的物理块号,将之装入物理地址寄存器,与此同时,再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中,这样,便完成了逻辑地址到物理地址的转换。

在程序未执行的时候,PCB 中存放程序对应页表的初始地址 F 以及页表长度 M(页表项个数)。程序一旦开始执行,F 和 M 会被送到页表寄存器中。在需要访问地址的时候,基本地址变换机构开始运行:

  • 首先将逻辑地址 A 拆分为页号和页内偏移量两个部分,然后将页号与页表寄存器中的页表长度作比较。页表长度即页表项个数,即页面个数,因此页号是不能大于等于(不能等于,是因为页号从 0 开始计算,类似于数组)页表长度的,否则就说明页号越界了,此时就会发生越界中断。若不越界,来到下一步
  • 由于页表中每个页表项的大小是一样的(假设为 size),且已经知道了页表初始地址(假设为 X),所以很容易知道页号 P 对应的页表项的地址,它等于 X + size*P,找到这个地址就意味着找到了页号对应的块号
  • 将块号与偏移量(注意这两个都是二进制)拼接,就得到了物理地址
  • 根据物理地址,就可以访问到目标

==在上面例子中,由于涉及到的都是二进制数,所以要计算物理地址,只需要将块号二进制数与偏移量二进制数拼接即可,这是比较方便的==,如果例子给出的是十进制数,那么可以用 块起始地址 + 页内偏移量 进行计算,计算结果可以再转化为二进制数,结果其实也是一样的。比如

若给定的是十进制:

页面大小 1kb,块号 2,偏移量 1023。

那么块起始地址等于 2*1kb = 2*1024b=2048b,又偏移量 1023,所以物理地址等于 2048+1023=3071,转化为 32 位二进制数,就是 0000000000000000000010,1111111111

若给定的是二进制:

页面大小 1kb,块号 2,偏移量 1111111111。

那么块号 2 转化为 22 位二进制数就是 0000000000000000000010,与偏移量拼接,就得到 0000000000000000000010,1111111111,可以看出与上面的结果是一样的。

1、若逻辑地址以十六进制、八进制、二进制的形式给出的,则计算方法如下:

==将逻辑地址转换成二进制的数==

==按页的大小分离出页号和位移量(低位部分是位移量,高位部分是页号)==

==根据题意查找页表==

==将位移量直接复制到内存地址寄存器的低位部分==

==以页号查页表,得到对应页装入内存的块号,并将块号转换成二进制数填入地址寄存器的高位部分,从而形成内存地址。==

2、逻辑地址以十进制数给出,则

==页号P=INT[虚地址/页面大小]==

==位移量d=虚地址 % 页面大小==

==根据页号查页表,得到对应的块号 内存地址=块号*页面大小+位移量==

②具有快表的地址变换机构

上述操作中,每次存取一个数据时,都会==访问内存两次==,第一次是访问内存中的页表,从中找到指定页的物理块号,再将块号与页内偏移量W拼接,以形成物理地址,第二次访问时,才是从第一次所得的地址中获得所需数据,因此,这种方式会使计算机的处理速度降低一半,为了提高地址变换速度,可以在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲寄存器,又称为联想寄存器或快表,用以存放当前访问的那些页表项。第二次访存肯定是不能避免的,但是第一次访存其实可以想办法避免。

若多条指令涉及到的逻辑地址的页号都相同,则每次都得经历第一次访存,找到该页号对应的块号

上面这两个问题可以通过引入快表来解决。

快表又叫做联想寄存器,它是一种访问速度比内存快很多的高速缓冲存储器,用以存放访问过的页表项的副本,从而加快地址转换的过程 —— 也就是说,引入快表后,地址转换可以不需要经历第一次访存,而是直接从快表中拿到需要的页表项。与之对应的,内存中原本的页表,叫做慢表。

==其实应用的是局部性原理==

此时,地址变换机构的运行过程和之前还是差不多的,只是多了一个快表的处理过程:

在程序未执行的时候,PCB 中存放程序对应页表的初始地址 F 以及页表长度 M(页表项个数)。程序一旦开始执行,F 和 M 会被送到页表寄存器中。在需要访问地址的时候,地址变换机构开始运行:

  • 首先将地址拆分为页号和页内偏移量两个部分,然后将页号与页表寄存器中的页表长度作比较。若越界,则发生越界中断。若不越界,来到下一步
  • 该页号被送往快表,并与其中的页表项一一比较,寻找是否有配对的页号,因为这里我们是第一次查询,所以是没有的,即未命中,此时来到下一步
  • 经历第一次访存,在内存的页表中找到页号对应的页表项的地址,找到这个地址就意味着找到了页号对应的块号
  • 将该页表项拷贝一份副本放到快表中
  • 将块号与偏移量(注意这两个都是二进制)拼接,就得到了物理地址
  • 根据物理地址,就可以访问到目标

假设又一次地,我们需要访问某个地址,并且这个地址与前次访问的地址的页号一样:

  • 首先将地址拆分为页号和页内偏移量两个部分,然后将页号与页表寄存器中的页表长度作比较。若越界,则发生越界中断。若不越界,来到下一步
  • 该页号被送往快表,并与其中的页表项一一比较,寻找是否有配对的页号,因为之前我们已经在快表中存放了一份页表项的副本,所以找到了配对的页号,即命中,此时来到下一步
  • 从快表中读出该页号对应的块号,并与偏移量拼接,就得到了物理地址
  • 根据物理地址,就可以访问到目标

这里可以注意到,由于第一次查询到页号对应的块号后,我们将页表项拷贝了一份副本放到快表中,所以以后再涉及到相同的页号时,只需要先来到快表查找即可,找到了就直接拼接得到物理地址,无需再到内存中去访问页表,寻找页号对应的块号。

当然,由于成本的关系,快表不会做得很大,但对于中小型作业来说也已经足够,只是对于大型作业来说,不太可能把全部页表项都存放到快表中。

I.访问内存的有效时间(Effective Access Time,EAT)

从进程发出指定逻辑地址的访问请求,经过地址变换到在内存中找到对应的实际物理地址单元取出数据所花费的总时间 。

分页存储管理方式

  • ==EAT=2t(t为访问一次内存所需时间)==

引入快表分页存储管理方式

  • ==EAT= a×λ+(t+λ)(1-a)+t=2t+λ-at==
    • a×λ+(t+λ)(1-a)为使用块表的平均查询时间
    • t为不可避免的访存时间
    • λ为查找快表所需时间 ,a为命中率

某系统使用基本分页存储管理,并采用了具有快表的地址变换机构。假设访问一次快表耗时 1us,访
问一次内存耗时 100us,快表的命中率为 90%。

  • 若未引入快表,则访问一个逻辑地址耗时 100 + 100 = 200us

  • 若引入快表,则访问一个逻辑地址耗时 (1+100) * 0.9 + (1+100+100) * 0.1= 111 us

  • 若引入快表,且该系统支持同时查询快表和慢表,则访问一个逻辑地址耗时 (1+100) * 0.9 + (100+100) * 0.1 = 110.9us

    显然,引入快表后,访问一个逻辑地址的速度快多了。

II.页表项的大小

假设某系统物理内存大小为 4GB,页面大小为 4KB,则每个页表项至少应该为多少字节?

4GB=2^32^ b, 4KB=2^12^b,因此 4GB 的内存总共会被分为 2^32^/2^12^ = 2^20^ 个内存块,因此内存块号的范围应该是 0~2^20^-1。因此对于单个页表项,它至少要用一个 20 位二进制数才能表示这样的一个内存块号,而一个字节 8 位,所以至少要三个字节才可以表示这样的一个内存块号。又由于实际不知道哪个页表项存放哪个内存块号,所以所有的页表项统一得用到至少三个字节。

但是一个页表项用三个字节其实会出现一些问题。类似于进程被拆分为多个页面存储在内存中一样,页表也是被拆分为多个页表项存储在内存中的。假设页面/页框大小为 4kb,也即 4096b,由于一个页表项 3b,所以一个页框至多可以放 4096/3=1365 个页表项,并且这个页框剩余 1b 的空间。由于 1b 不足以再存放一个页表项,所以第 1366 个页表项(1365 号页表项)只能放在下一个页框中了。

这就会导致,前面 1365 个页表项的地址依然可以采用 X + 3*P 的方式计算,但是第 1366 个页表项,它的地址却应该是 X + 3*P + 1,也就是说,我们无法以一个通用的式子去计算页表项的地址。

为此,建议一个页表项大小应为 4b 而不是 3b(选取 2 的整数幂)。因为如果页表项大小为 4b,那么一个页框就刚好可以放 4096/4=1024 个页表项,不会有剩余空间,而余下的页表项也可以依次放在下一个页框中。这样的话,涉及到页表项地址的计算,都可以用通用的式子 X + 4*P 来计算,就无需考虑由于页框无法得到完全利用而带来的查询麻烦的问题了。当然,为了这个式子能够通用,页表通常也应该连续地存放在内存块中,中间不出现断节。

③两级页表和多级页表
I.两级页表

现代计算机系统中,可以支持非常大的逻辑地址空间(2^32^~2^64^),这样,页表就变得非常大,要占用非常大的内存空间,如,具有32位逻辑地址空间的分页系统,规定页面大小为4KB,则在每个进程页表中的页表项可达1M(2^20^)个,又因为每个页表项占用一个字节,故每个进程仅仅页表就要占用1MB的内存空间,而且要求连续,这显然是不现实的,可以通过如下两个方法解决该问题。

  • 采用离散方式
  • 只将当前所需页表项调入内存

对于要求连续的内存空间来存放页表的问题,可利用将页表进行分页,并离散地将各个页面分别存放在不同的物理块中的办法来解决,同样的,也要为离散分配在页表再建立一张页表,称为外层页表。在每个页表项中记录了页表页面的物理块号,以32位逻辑地址空间为例进行说明。

说明:外层页号P1为10位,可以表示1024个物理块,外层页表中的外层页内地址P2为10位,可以表示1024个物理块,页内地址为12位,表示页面大小为4K。

在需要进行地址转换的时候:

  • 首先将逻辑地址分为三个部分:一级页号、二级页号、页内偏移量
  • 然后从 PCB 中读出页目录表的初始地址,结合一级页号以及每个页表项的大小,找到一级页号对应页表项的地址,即找到了对应页表项,也就找到了一级页号对应的内存块号
  • 根据内存块号到内存中找到对应的那个二级页表(原页表的某个子页表)
  • 在二级页表中,根据二级页号找到对应的块号
  • 块号与偏移量结合,得到物理地址

为了实现地址变换,在地址变换机构中需要增设一个外层页表寄存器,用于存放外层页表的始址,并利用逻辑地址中的外层页号,作为外层页表的索引,从中找到指定页表分页的始址,在利用P2作为指定页表分页的索引,找到指定的页表项,其中即含有该页在内存的物理块号,用该块号和页内地址d即可构成访问的内存物理地址。

II.多级页表

页面大小为4KB即212B,还剩52位,按物理块大小2^12位来划分页表,则剩余40位用于外层页号,此时外层页表可能有1024G个页表项,要占用的连续存储空间太大。

解决方法:采用多级页表,将外层页表再进行分页。

==注意:到现在为止,我们只是在解决连续分布问题,没有解决页表大的问题。无论你分几层,只不过是打散,并没有减少。==

④*反置页表(Inverted Page Table)

分页系统中,为每个进程配置了一张页表,进程逻辑地址空间中的每一页,在页表中都对应有一个页表项。在现代计算机系统中,通常允许一个进程的逻辑地址空间非常大,因此就需要有许多的页表项,而因此也会占用大量的内存空间。

反置页表:为每个物理块设置一个页表项,并将它们按物理块编号排序,其内容为页号及所在的进程ID.

在利用反置页表进行地址变换时,是根据进程标识符和页号去检索反置页表。如果检索到与之匹配的页表项,则该页表项(中)的序号i便是该页所在的物理块号,可用该块号与页内地址一起构成物理地址送内存地址寄存器。若检索了整个反置页表仍未找到匹配的页表项,则表明此页尚未装入内存。对于不具有请求调页功能的存储器管理系统,此时则表示地址出错。对于具有请求调页功能的存储器管理系统,此时应产生请求调页中断,系统将把此页调入内存。

当内存容量很大时,反置页表表项也会很多,如何检索?

I.内存块的管理方法:位示图法

位示图法是利用二进制的一位来表示主存中一个块的使用情况。 当其值为0时表示对应的块空闲,为1时表示已分配 。 主存上的所有盘块都有一个二进制位与之对应,这样由所有盘块所对应的位构成一个集合,称为位示图。 通常可用m*n个位数来构成位示图,并使m*n等于主存的总块数

④虚拟存储技术

上述方法用离散分配空间解决了大页表无需大片存储空间的问题,但并未减少页表所占的内存空间。解决方法是把当前需要的一批页表项调入内存,以后再根据需要陆续调入(虚存)。

在采用两级页表结构的情况下,对于正在运行的进程,必须将其外层页表调入内存,而对页表则只需要调入一页或者几页,为了表征某页的页表是否已经调入内存,还应在外层页表项中增设一个状态位S,其值若为0,表示该页表分页尚未调入内存,否则,说明已经在内存,进程运行时,地址变换机构根据逻辑地址P1,去查找外层页表,若所找到的页表项中的状态位为0,则产生一中断信号,请求OS将该页表分页调入内存。

具体的知识后面再进行讲解。

习题

最后,可以做一些题目来巩固一下。

1.若系统采用两级分页存储方式,物理内存 64mb,页面大小 1kb,页表项大小 2b,则顶级页表有多少个页表项?

这里我们可以参考之前求页表项大小的思路。物理内存 64mb,即 2^26^b,所以逻辑地址一共 26 位。这 26 位中,一部分表示一级页号,一部分表示二级页号,剩下的表示页内偏移量。

因为页面大小 1kb,也即 2^10^b,所以页内偏移量一共需要 10 位来表示。一个页面大小 2^10^b,一个页表项 2b,所以一个页面可以最多可以放 2^9^ 个页表项,又由于各级页表不能超过一个页面,所以各级页表不能超过 2^9^ 个页表项。在逻辑地址余下的 16 位中,可以用其中 9 位去表示二级页表的页号(此时该页表的页表项个数取到了最大值),剩下的 7 位表示另一个 —— 顶级页表的页号。因为顶级页表页号有 7 位,所以顶级页表可以包含 2^7^ 个页表项,即包含 128 个页表项。

2.若系统采用分页存储方式,物理内存 256mb,页面大小 1kb,页表如下:

页号 0,1,2,3,4,5,6,7,8,9,10 分别对应块号 15,16,20,28,29,30,31,32,36,38,39

则逻辑地址 1A68(16进制)对应的物理地址是多少?

为了方便计算,我们先统一用十进制计算,得到十进制的物理地址后再转换为十六进制。

1A68 按权展开转化为对应的十进制数字是 6760,对于逻辑地址 6760,可以计算它的页号和页内偏移量:

  • 页号 = 6760/1024 = 6(取整数部分)
  • 页内偏移量 = 6760%1024 = 616

根据页号 6 找到块号 31,根据块号 31 计算块初始地址为 31*1024 = 31744,偏移量和初始地址相加得到的物理地址为 31744+616 = 32360。32360 是十进制的物理地址,转化为对应的十六进制物理地址就是 7E68。

3.若系统采用分页存储方式,物理内存 1mb,共有 32 个页面,一个页面 2kb,则逻辑地址一共多少位?

因为物理内存 1mb,也即 2^20^b,所以逻辑地址 20 位。

根据上面习题的经验,我们可能会这么做,但是注意这是错误的做法。上面的习题都没有告诉我们程序具体被划分为多少个页面,所以我们认为物理地址需要多少位时(20),逻辑地址也需要多少位(20);但是这道题已经告诉了我们程序具体被划分为多少个页面(32)—— 显然,页面仅仅被划分为 32 个,是不需要 20 这么多位的逻辑地址的。

由于逻辑地址包括两部分,一个是页号,一个是页内偏移量,我们不妨分别考虑这两者所占的位数:

  • 考虑页内偏移量位数。由于一个页面 2kb,也即 2^11^b,所以页内偏移量占 11 位(注意这点是不变的);
  • 考虑页号位数。由于页面仅仅被划分为 32 个,也即 2^5^ 个,所以页号只需要 5 位

11 + 5 =16,所以逻辑地址一共 16 位。

PS:当题目明确给出分页个数的时候,按照页号位数+偏移量位数计算逻辑地址总位数。

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~