OS_内存管理@非连续方式@段式和段页式

OS_内存管理@非连续方式@段式和段页式

内存管理方式的发展

• 当OS由单道向多道发展时，存储管理方式便由单一连续 分配发展为固定分区分配。
• 为了能更好地适应不同大小的用户程序要求,存储管理方式又从固定分区分配，发展到动态分区分配。
• 为了能更好地提高内存的利用率，进而又从连续分配方式发展到离散分配方式:分页存储管理方式
• 管理分页管理方式是从计算机的角度考虑设计的，目的是提高内存的利用率

基本分段存储

• Memory segmentation

  • it is an operating system memory management technique of division of a computer’s primary memory into segments or sections.
  • In a computer system using segmentation, a reference to a memory location includes a value that identifies a segment and an offset (memory location) within that segment.
  • Segments or sections are also used in object files of compiled programs when they are linked together into a program image and when the image is loaded into memory.

• 引入分段存储管理方式的目的，则主要是为了满足用户(程序员)在编程和使用上多方面的要求，其中有些要求是其它几种存储管理方式所难以满足的。

• 因此，这种存储管理方式已成为当今所有存储管理方式的基础，许多高级语言和C语言的编译程序也都支持分段存储管理方式。

• 分页通过硬件机制实现，对用户完全透明。

优点

• 段式虚拟存储器的优点是，段的分界与程序的自然分界相对应，因而具有逻辑独立性，使得它易于编译、管理、修改和保护，也便于多道程序的共享;
• 分段管理方式的提出则考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。
  • 分段段式管理方式按照用户进程中的自然段划分逻辑空间。
  • 例如
    • 某个用户进程由以下几个段组成
      • 主程序段、
      • 两个子程序段、
      • 栈段
      • 数据段
    • 每段从0开始编址，并分配一段连续的地址空间
    • 段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的

缺点

• 因为段长度不固定,空间分配不便,容易在段间留下碎片,造成空间浪费

逻辑结构图

• 

• 

逻辑地址结构划分

• 由段号S与段内偏移量W两部分组成

• 段号S	段内偏移量W

• 两者都必须由用户显式提供,(或者编译器来完成)

段表

• 记为ST:segment table🎈

• 类似于页表的作用,记录了逻辑空间与内存地址的映射关系

  • 从逻辑段到物理内存区的映射

• 每个段表项对应进程的一段

• 段表项记录该段(段号S)在内存中的长度M和始址b

  • 段长C	本段在主存中的始址(基址)

    • 字段间的顺序不是重点

  • 具体版:

    • 组成原理中,把段表结构描述的更加具体

    • 段号S(index)	段长C	装入位	本段在主存中的始址(基址)$b_s$

    • 段表行(段表项)的装入位判断该段是否已调入主存

      • 装入位为“1”，表示该段已调入主存：

      • 装入位为“0”，表示该段不在主存中

    • 已调入主存时，从段表读出该段在主存中的起始地址$b_s$，与段内地址（偏移量W）相加得到对应的主存实地址

  • 记段表ST中,段号S对应的那一条段表项(记录)为$ST.S$

    • ST,ST.S都视为可调用对象
    • $ST.S.b$则表示段S在主存中的物理地址

地址变换机构

• 为了实现进程的逻辑地址到物理地址的变换功能,系统中设置了段表寄存器(Segment Register)
• 

段表寄存器内容结构

• Segment Register

• 段表始址F	段表长度M

• 段表始址F🎈

• 段表长度M🎈

  • M=L(ST)
  • 即段表中包含的段表项数量

段和段表项的记号

• 段表项长度:$L(I)$🎈
  • 表示每个段表项占用的内存空间
• 段长C=L(S)🎈
  • 表示进程的某个段占用的内存空间

变换过程

• 从逻辑地址A中取出前s位为段号S,后w位为段内偏移量W
  • 两个字段分两次使用
  • $地址长度为n,则s+w=n$
• 检查段表寄存器SR,比较段号S和段表长度M
  • 若$S⩾M$,则产生越界中断
  • 若$S<M$继续执行
• 计检查段表ST,算段号S对应的段表项(地址):$ST.S=F+S\times L(I)$
  • 取出该段表项的前c位得到段长C
  • 若$W⩾C$,则产生越界中断
  • 若$W<C$,继续执行
• 取出段表项中该段始址$b=ST.S.b$,计算A对应的具体存储单元的物理地址$E=b+W$
  • 用得到的物理地址E去访问内存(可以取得具体的内存单元(存储字)内容)。

段的共享与保护

• 在分段系统中，段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。
• 当一个作业正从共享段中读取数据时，必须防止另一个作业修改此共享段中的数据。
• 不能修改的代码称为纯代码或可重入代码（它不属于临界资源），
  • 这样的代码和不能修改的数据可以共享，
  • 而可修改的代码和数据不能共享。
• 分段管理的保护方法主要有两种：
  • 一种是存取控制保护，另一种是地址越界保护。
  • 地址越界保护将段表寄存器中的段表长度与逻辑地址中的段号比较，
    • 若段号大于段表长度，则产生越界中断：
      • 再将段表项中的段长C和逻辑地址中的段内偏移w进行比较，
      • 若段内偏移大于段长，也会产生越界中断。
• 分页管理只需要判断页号是否越界，页内偏移是不可能越界的。
  • 与页式管理不同，段式管理不能通过给出一个整数便确定对应的物理地址，
  • 因为每段的长度是不固定的，无法通过整数除法得出段号，无法通过求余得出段内偏移，
  • 所以段号和段内偏移一定要显式给出(段号，段内偏移)，因此分段管理的地址空间是二维的

段页式存储🎈

• 分页存储管理能有效地提高内存利用率
• 分段存储管理能反映程序的逻辑结构并有利于段的共享和保护。
• 将这两种存储管理方法结合起来，便形成了段页式存储管理方式。
• 把程序按逻辑结构分段，每段再划分为固定大小的页，
• 主存空间也划分为大小相等的页,程序对主存的调入、调出仍以页为基本传送单位，这样的虚拟存储器称为段页式虚拟存储器。
  • 在段页式系统中，
    • 作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，
    • 然后将每段分成若干大小固定的页。
      • 对内存空间的管理仍然和分页存储管理一样， 將其分成若干和页面大小相同的存储块，
      • 对内存的分配以存储块为单位
  • 在段页式虚拟存储器中
    • 每个程序对应一一个段表，
    • 每段对应一个页表，
  • 段的长度必须是页长的整数倍，段的起点必须是某一页的起点

优点

• 段页式虚拟存储器的优点是，兼具页式和段式虚拟存储器的优点，可以按段实现共享和保护。

缺点

• 在地址变换过程中需要两次查表，系统开销较大。

逻辑地址结构

• 段号S
• (段内)页号P
• 页内地址(页内偏移)W

实现思路:段表和页表的变体🎈

逻辑结构图

• 为了实现地址变换,系统给每个进程建立(1:1)
  • 一张段表,
  • 每个分段都有一张页表
    • 后面地址变换机构图会表达这一点
• 为了适应段页式方式,以sp前缀适应于段页式存储的段表和页表

sp-段表

• sp-SegmentTable
• 段表对象用ST表示
• 段表项中至少包括
  • 段号S
  • (段内)页表长度L(PT)
    • Length(PageTable)
  • (段内)页表始址$F_p$=PT
    • PTA:Page Table Address
• Note:逻辑地址字段段号P对应的段表项表达式记为ST[S]

sp-页表

• sp-PageTable
• 页表对象用PT表示
• 页表项至少包含:
  • 页号P
    • 可以理解为sp-段内的偏移,可以确定页表
    • 和单纯的段偏移(记为pure-段内偏移)有所不同(pure-段内偏移是为了确定具体的存储单元)
  • 块号b
• Note:逻辑地址字段页号P对应的页表项表达式记为:PT[P]
  • 其中$PT=ST[S].PT$,简记为$F_P$

sp段表寄存器

• 系统中还包含的段表寄存器,用于越界判断和提供段表始址,指出
  • 段表始址$F_s$
  • 段表长度$M_s$=L(ST)

相关寄存器的作用🎈

• 声明:

  • 表始址有时就代指表本身

  • 表项地址有时代表表项本身

  • 类比于数组的首地址和数组名,有时它们作用相同

• 页表寄存器和段表寄存器的作用:

  • 寻址
    • 表始址
      • 找到页表项/段表项之前,需要先确定页表/段表的始址
      • 然后基于表的始址做一定的偏移得到表项(地址)
    • 表项
      • 读取表项中指示的 页/段的物理页号/段号$b_p或b_s$
      • 基于页/段的物理地址(物理页/段号),用逻辑地址的页/段内偏移字段W,就可以得出具体的内存单元地址
    • 根据段号或者页号,计算出逻辑地址被映射到的段表或页表
      • 一个程序对应的段表只有一个
        • 一个段表可以记录多个段(注意区分)
      • 但是可能对应多个页表
      • 如果没有越界,会返回一个有效的段表/页表起始地址值
      • 根据具体的段表/页表地址,可以计算出相应的表项(段表项/页表项)
      • 根据表项中指示的物理块地址,结合段/页内偏移,计算出具体内存单元的物理地址
  • 越界判断
    • 如果进程要映射的逻辑地址越界(非法/错误),会引发中断

• 同一个逻辑地址,采用不同的内存管理方式(段式/页式/段页式/…),仅在划分字段的时候有所不同,

  • 因为,不同的内存管理方式的地址变换机构有所不同

地址变换机构

• 

变换过程🎈

• 将逻辑地址分为三个字段:
  • 段号S
  • 页号P
  • 页内偏移(地址)W
• 取用逻辑地址的字段S查询sp-段表(段表寄存器),确定段表始址(段表对象)$F_s=ST$
  • 此处使用的表达式类比像程序设计语言C语言
  • 计算段表项地址:
    • 基于段表始址$F_s$做偏移S(偏移量就是段号S)
      • 得到段表项(地址)$ST[S]=F_s+S\times L(SegItem)$
      • 具体说,是进程对应段的段表项地址
    • 根据段表项(地址),读取段表项中的页表始址字段$PT=ST[S].PT$
• 再取用逻辑地址的页号字段P,基于页表对象(始址)$PT$做偏移P,
  • 确定页内的页表项对象$PT[P]=PT+P\times L(PageItem)$
    • 也就是页表项地址
  • 页表项对象的字段$b=PT[P].b$就是物理块号(块地址)
• 最后取用逻辑地址的字段W拼接到$b$,确定页内字地址
• CPU根据虚地址访存时，首先根据段号得到段表地址;
  • 然后从段表中取出该段的页表起始地址，与虚地址段内页号合成，得到页表地址;
  • 最后从页表中取出实页号，与页内地址拼接形成主存实地址。
• 在进行地址变换时，首先通过段表查到页表始址，然后通过页表找到页帧号，最后形成物理地址。
• 进行一次访问实际需要三次访问主存
  • 这里同样可以使用快表来加快查找速度，
    • 关键字由段号、页号组成，
    • 值是对应的页帧号和保护码

小结

• 主要问题

• 想要查段表，需要先知道段表在哪里，所以要先计算段表的地址（首地址）

• 知道了段表首地址，怎么计算具体的段表项，从而读取段表项内容字段:页表首地址

  • 可根据地址划分出的段号和段表始址,计算段表项的位置，进而知到页表首地址

• 再根据地址划分的页号以及页表首地址，计算具体的页表项地址

• 读出页表项的物理块号字段内容，

• 结合地址划分的块内偏移，拼接出具体的字地址