王道操作系统___第三章01

3.1_1_内存的基础知识

• 内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被CPU处理。
• 编译时产生的指令只关心相对地址，实际放入内存中时再想办法根据起始位置得到绝对地址。
• 编译：由编译程序将用户源代码编译成若干个目标模块(编译就是把高级语言翻译为机器语言)
• 链接：由连接程序将编译后形成的一组目标模块，以及所需的库函数链接在一起，形成一个完整的装入模块。
• 装入：由装入程序将装入模块装入内存中运行。(逻辑地址向物理地址发生转换)

装入模块装入内存

• 装入的三种方式：绝对装入，静态重定位，动态重定位。
• 绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块的地址，将程序和数据装入内存。
• 绝对装入只适用于单道程序环境
• 静态重定位：编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址，数据存放的地址都是相对于起始而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行重定位，将逻辑地址转换为物理地址。
• 静态重定位在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入改作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
• 动态重定位：编译、链接后的装入模块的地址都是从0开始的，装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才执行。因此装入内存后的所有地址依然是逻辑地址。这种方式需要一种重定位寄存器的支持。
• 采用动态重定位时允许程序在内存中移动。并且可以将程序分配到不连续的存储区等。

链接的三种方式

• 静态链接：在程序运行之前，先将个目标模块及它们所需要的库函数链接成一个完整的可执行文件(装入模块)，之后在不拆开。
• 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。
• 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

3.1_2_内存管理的概念

• 操作系统负责内存空间的分配与回收
• 操作系统需要提供某种技术从逻辑上对内存空间进行扩充。
• 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换。
• 操作系统需要提供内存保护功能。保证各进程在各自的存储空间内运行，互不干扰。
  • 在CPU中设置一对上下限寄存器，存放进程的上下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
  • 采用重定位寄存器和界地址寄存器进行越界检查。

3.1_3_覆盖与交换

覆盖技术

• 用来解决程序大小超过物理内存总和的问题
• 将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存。
• 常用的段放在固定区，不可能被同时访问的程序段共享同一个覆盖区。
• 固定区中程序段在运行过程中不会调入调出。
• 覆盖区中的程序段在运行过程中会根据需要调入调出。
• 必须由程序员声明覆盖结构，操作系统完成自动覆盖，现在已经成为历史。

交换技术

• 内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中已具备运行条件的进程换入内存。
• 进程在内存与磁盘间动态调度。
• 磁盘分为交换区和对换区，换出的进程放在对换区。
• 中级调度(内存调度)：就是要决定将哪个处于挂起状态的进程重新调入内存。
• PCB会常驻内存，不会被换出外存。

区别

• 覆盖是在同一个程序或进程中的
• 交换是在不同进程之间的。

3.1_4_连续分配管理方式

• 连续分配：指为用户进程分配的必须是一个连续的内存空间。

单一连续分配

• 在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据，用户区用于存放用户进程相关数据。
• 内存中只能有一道用户程序，用户程序独占整个用户区空间。
• 分配给某进程的内存区域中，如果有些部分没有用上，就是内部碎片。
• 外部碎片：指内存中某些空闲分区由于分区太小而难以利用。

固定分区分配

• 分区大小相等，分区大小不等
• 操作系统需要建立一个数据结构–分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态。
• 无外部碎片，会产生内部碎片。

动态分区分配

• 不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
• 使用空闲分区表或者空闲分区链记录内存的使用情况
• 把一个作业装入内存时，需按照一定的动态分区分配算法，从空闲分区表中选出一个分区分配给改作业。
• 在进行内存分区回收的时候，如果回收之后，发现一些空闲分区是相邻的，需要把相邻的空闲分区进行合并。
• 动态分区分配没有内部碎片，但是有外部碎片。可以通过紧凑技术来解决外部碎片。

3.1_5_动态分区分配算法

• 首次适应算法、最佳适应算法、最坏适应算法、邻近适应算法

首次适应算法

• 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
• 空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。

最佳适应算法

• 优先使用更小的空闲区。
• 空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。
• 会产生很多很多的外部碎片

最坏适应算法

• 在每次分配的时候优先使用最大的连续空闲区。
• 空闲分区按容量递减的次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。
• 会导致较大的连续空闲区被迅速用完，如果之后有大进程到达，就没有内存分区可用了。

邻近适应算法

• 每次都从上次查找结束的位置开始检索。
• 空闲分区以地址递增的顺序排列，每次分配内存时从上次查找结束的位置开始查找空闲分区链，找到大小能满足要求的第一个空闲分区。
• 会使高地址的大分区也被用完。

3.1_6_基本分页存储管理的基本概念

• 连续分配：为用户进程分配的必须是一个连续的内存空间
• 非连续分配：为用户进程分配的可以是一些分散的内存空间
• 基本分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。

分页存储管理的基本概念

• 将内存空间分为一个个大小相等的分区，每个分区就是一个页框。每个页框有一个编号，即页框号，从0开始编号
• 将用户进程的地址空间也分为与页框号大小相等的一个个区域，称为页，或页面，每个页面也有一个编号。
• 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应关系。
• 各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

地址转换的实现

• 要算出逻辑地址对应的页号：页号 = 逻辑地址 / 页面长度
• 要知道该页号对应的页面在内存中的起始地址：操作系统需要某种数据结构记录各个页面的起始位置。
• 要算出逻辑地址在页面内的偏移量 ：页内偏移量 = 逻辑地址 % 页面长度
• 物理地址=页面始址+页内偏移量。
• 如果每个页面大小为2的K次方B，用二进制表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号。

页表

• 为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。
• 一个进程对应一张页表
• 进程的每一页对应一个页表项
• 每个页表项由页号和块号组成。
• 页表记录进程的页面和实际存放的内存块之间的对应关系。
• 每个页表项的长度是相同的，页号是隐含的。

3.1_7_基本地址变换机构

• 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
• 通常会在系统中设置一个页表寄存器PTR，存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块中，当进程被调度时，操作系统内核会把他们放到页表寄存器。

转换步骤

• 根据逻辑地址计算出页号、页内偏移量。
• 判断页号是否越界
• 查询页表，找到页号对应的页表项，确定页面存放的内存块号。
• 用内存块号和页内偏移量得到物理地址。
• 访问内存单元对应的内存单元。
  
  
• 在分页存储管理中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此页式存储管理中的地址是一维的。即只要给出一个逻辑地址，系统就可以自动算出页号，页内偏移量两个部分，并不需要显示地告诉这个逻辑地址中，页内偏移量占多少位。
• 进程页表通常是装在连续的内存块中，为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整个页表项。

3.1_8_ 具有块表的地址变换机构

局部性原理

• 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很可能再次执行；如果某个数据被访问过，不久之后该数据可能再次被访问
• 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元很可能被访问。

什么是块表

• 块表，又称联想寄存器，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中存放的页表常称为慢表。
• CPU给出逻辑地址，由某个硬件算得页号，页内偏移量，将页号和块表中的所有页号就行比较。
• 如果找到了匹配的页号，说明要访问的是页表项在快表中的副本，则直接从中取出该页对应的内存快号，再将内存块号与页内偏移量拼接形成物理地址。最后，访问该物理地址对应的内存单元。因此若快表命中，则访问某个逻辑地址仅需一次访存即可。
• 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应的页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元。再找到页表项后应同时将其放入块表
• 若块表未命中，则访问某个逻辑地址需要两次访存，但若块表已满则必须按照一定的算法对旧的页表项进行替换。

3.1_9_两级页表

单级页表的问题

• 页表必要连续存放，因此当页表很大时，需要占用很多个连续的页框。
• 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。
• 可将长长的页表进行分组，使每个内存块刚好可以放入一个分组，另外要为离散分配的页表在建立一张页表，称为页目录表。
• 可以在需要访问页面时才把页面调入内存(虚拟存储技术)。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存。
• 若想访问的页面不在内存中，则产生缺页中断(内中断)，然后将目标页面从外存调入内存。

如何实现地址变换

• 按照地址结构将逻辑地址拆分成三部分，一级页号，二级页号，页内偏移量
• 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置。
• 根据二级页号查表，找到最终想要访问的内存块号。
• 结合页内偏移量得到物理地址。

需要注意的细节

• 若采用多级页表机制，则各级页表的大小不能超过一个页面。
• 两级页表的访存次数分析：n级页表访存次数应该是n+1次。(没有块表)
  • 第一次访存：访问内存中的页目录表
  • 第二次访存：访问内存中的二级页表。
  • 访问目标内存单元。

3.1_10_基本分段存储管理方式

分段

• 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编制。
• 内存分配规则：以段为单位进行分配，每个段在内存中占据连续内存空间，但各段之间可以不相邻。
• 由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高。
• 分段系统的逻辑地址结构由段号和段内地址所组成
• 段号的位数决定了每个进程最多可以分几个段。
• 段内地址位数决定了每个段的最大长度。

段表

• 程序分为多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。
• 为此，需为每个进程建立一张段映射表，简称段表。
• 每个段对应一个段表项，其中记录了该段在内存中的起始位置和段的长度。
• 各个段表项的长度是相同的，包括段长和基址，段号是隐藏的。

地址变换

• 进程切换相关的内核程序负责恢复进程的运行环境，把段表的信息放到段表寄存器中。
• 根据逻辑地址得到段号、段内地址。
• 判断短号是否越界。段表长度至少是1，段号是从0开始的。
• 查询段表，找到对应的段表项，段表项的存放地址为：段表始址+段号*段表项长度
• 检查段内地址是否超过段长，若超过，则产生越界中断，否则继续执行。
• 计算得到物理地址：段基址+段内地址。访问目标内存单元

分段、分页管理的对比

• 分页当中每个页面的长度是相同的不需要对页内偏移量进行检查，而分段当中每个段的长度是不同的，且需要对段内偏移量进行检查。
• 页是信息的物理单位，分页的主要目的是为了离散分配，提高内存的利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
• 段是信息的逻辑单位，分段的主要目的是更好的满足用户的需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显示地给出段名。
• 页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
• 分页的用户进程是一维的，程序员只需要给出一个记忆符即可表示一个地址
• 分段的用户进程地址空间是二维的，程序员在标识一个进程时，既要给出段名，也要给出段内地址。

分段、分页管理的对比

• 分段比分页更容易实现信息的共享和保护。
  • 共享：只需让各进程的段表项指向同一个段即可实现共享，可修改的代码是不可以被共享的。
  • 页面不是按逻辑模块划分的，这就很难实现共享。
• 访存：分段查询第一次访存，查内存中的段表，第二次访存，访问目标内存单元。总共两次访存。
• 也可以引入块表机构，将近期访问过的段表项放到快表中，可以少一次访存，加快地址变换速度。

3.1_11_段页式管理方式

• 分页管理
  • 优点：内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片
  • 缺点：不方便按照逻辑模块实现信息的共享和保护
• 分段管理
  • 优点：很方便按照逻辑模块实现信息的共享和保护
  • 缺点：如果段长过大，为其分配很大的连续空间会很不方便，另外段式管理会产生外部碎片。

段页式管理

• 将进程按逻辑模块分段，在将各段分页。
• 再将内存空间分为大小相同的内存块/页框/物理块
• 段页式系统的逻辑地址结构由段号、页号、页内地址组成。
• 段号的位数决定了每个进程最多可以分为几个段，页号的位数决定了每个段最大有多少页，页内偏移量决定了页面大小、内存块大小是多少。
• 分段对用户是可见的，而将各段分页对用户是不可见的，段页式管理的地址结构是二维的。

段表、页表

• 每个段对应一个段表项，每个段表项由段号，页表长度，页表存放块号(页表起始地址)组成。每个段表项长度相等，段号是隐含的。
• 每个页面对应一个页表项，每个页表项由页号，页面存放的内存块号组成。每个页表项长度相等，页号是隐藏的。

逻辑地址–>物理地址

• 根据逻辑地址得到段号、页号、页内偏移量
• 判断段号是否越界，与段表寄存器中的段表长度进行比较
• 查询段表，找到对应的段表项，段表项的存放地址为：段表始址 + 段号*段表项长度。
• 检查页号是否越界，若页号大于等于页表长度，则发生越界中断，否则继续执行。
• 根据页表存放块号、页号查询页表，找到对应页表项。
• 根据内存块号、页内偏移量得到最终的物理地址。
• 访问目标内存单元
• 三次访存：访存段表、访存页表、访存目标内存单元。
• 也可以引入块表机制，用段号和页号作为查询块表的关键字。若块表命中，则仅需一次访存。