回顾
操作系统的五大功能：CPU管理、存储管理、设备管理、作业管理、文件管理
存储器管理的主要对象是内存，对外存的管理放在文件管理中
存储器管理：
存储器三个主要特性的关系：
存储器的缓存——主存层次和主存——辅存层次：
存储系统层次结构：
4.1 程序的装入和链接
程序的编译、链接、和装入：
地址：
程序：
4.1.1程序的装入
4.1.1.1绝对装入方式
逻辑地址=绝对地址
只适合单道程序
4.1.1.2可重定位装入方式
对于多道程序环境，可重定位装入更合理，可根据内存的具体情况装入适当位置。
-
静态重定位
在程序执行之前进行重定位。
程序重定位后无法在内存中移动，要求程序的存储空间是连续的。
对多道程序的逻辑地址重定位后装入内存中：
-
动态重定位 参见4.2.4.2动态重定位
在程序执行过程中进行地址重定位，即在每次访问内存单元前才进行地址变换。
要硬件——重定位寄存器的支持。 **
4.1.2程序的链接
程序编译后，得到一组目标模块，链接的功能是将目标模块装配成完整的装入模块。
4.1.2.1静态链接
事先链接，以后不再拆开
对于以上这个例子，需要解决两个问题：
(1) 对相对地址(0)进行修改。 (2) 变换外部调用（B、C）符号。
4.1.2.2装入时的动态链接
程序边装入边链接。
优点为：（1）便于修改和更新。 (2) 便于实现对目标模块的共享。
4.1.2.3运行时的动态链接
在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存
优点：省空间、速度快
4.2 内存的连续分配方式
连续分配方式：指为一个用户程序分配一个连续的内存空间。
系统分两个内存区：系统区和用户区
4.2.1单一连续分配
一个用户程序独占连续的内存用户区
只能用于单用户、单任务的操作系统中。
4.2.2固定分区分配
将内存划分为多个区域，每个内存区存放一个用户程序
可用于多用户、多任务环境
4.2.2.1两种固定分区分配方法
- 相等大小的分区
- 优点：简单
- 缺点：大程序装不下，小程序浪费严重
- 不等大小的分区
- 优点：适应性较强
- 缺点：特别大的程序可能仍装不下
4.2.2.2固定分区分配的实现
内存分区使用表
4.2.3动态分区分配*
按照用户进程实际大小，动态地分配内存空间
提高内存的使用效率
动态分区分配中三个需要明晰的问题：
1）数据结构、2）分配算法、3）回收操作
4.2.3.1数据结构
- 空闲分区表
- 空闲分区(双向)链表
4.2.3.2分配算法
(1)首次适应算法FF
将空闲分区表地址递增排序，找到首次满足的空闲分区。
按照作业大小在该分区划出需要的内存空间，剩下的留在空闲分区表。
- 优点：保留高地址部分的大空闲区
- 缺点：低地址存在很多小的、无法利用的空闲分区，且查找时间较长
(2)循环首次适应算法CF
从上次找到空闲分区的下一个分区开始，按序选择第一个满足要求的内存区
- 优点：空闲分区在内存中均匀分布,查找时间少
- 缺点：缺乏大的空闲分区
(3)最佳适应算法BF
将空闲分区链表从小到大排列，查找大小与用户程序大小最相近的空闲分区
- 优点：提高了内存使用效率，保留大的空闲区
- 缺点：存在许多很小的、无法利用的空闲分区
(4)最坏适应算法Worst Fit
将空闲分区链表从大到小排列，找到首次满足的空闲分区。
- 优点：剩下的空闲区还可以利用，同时查找效率很高。
- 缺点：乏大的空闲分区。
(5)快速适应算法Quick Fit
快速适应算法，又称为分类搜索法。
把空闲分区按容量大小进行分类，经常用到长度的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表。
- 优点：查找效率高，不需要分割，不容易产生碎片
- 缺点：分区回归主存，系统开销较大，分配时会存在内存浪费（以空间换时间）
4.2.3.3内存的分配与回收操作
-
分配内存
变量 说明 u.size 请求的分区大小 m.size 空闲的分区大小 size 规定不可再切割的分区大小 如果
m.size - u.size <= size将整个分区分配给请求者。否则从分区中按请求的大小划出一块内存空间分配出去，余下部分留在空闲链中，将分配区首址返回给调用者：
-
回收操作
更改空闲分区表（起始地址和大小）
4.2.4可重定位分区分配
动态重定位分区分配算法与动态分区分配算法基本相同，差别在于增加了紧凑的功能。
4.2.4.1动态分区分配的延展
上文提到，无论是什么分配方式长时间运行都会产生大量难以利用的小的内存空间分区（碎片），故需要进行紧凑（拼接）：
缺点：用户程序在内存中的地址发生变化，必须重定位（动态重回定位）。
4.2.4.2动态重定位
核心：重定位寄存器（存放进程首址）
程序执行时访问的内存地址是相对地址与重定位寄存器中的地址相加而成：
4.2.5对换（类比挂起）
对换是什么？
对换是指把内存中暂不能运行的进程，或暂时不用的数据，换出到外存上，以腾出内存空间。
引入对换的原因？
- 阻塞进程占据大量内存空间
- 许多作业在外存而不能进入内存运行
对换的分类
- 整体对换：以进程为单位 (挂起操作)
- 部分对换：以页或段为单位 (虚拟存储器) ，又分为页面对换与分段对换
要实现对换，系统必须具备的功能
-
对换空间的管理
将外存分为文件区和对换区，对换区是连续的外存存储区。
可以采用与连续内存分配类似的方法，实现对换空间的管理（分配和回收）
-
进程的换出
系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。
-
进程的换入
系统应定时查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将换出进程最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。
4.3 基本分页存储管理方式
离散的分配方式，分为分页存储管理方式和分段存储管理方式。
两种分页存储管理方式：
- 基本分页式存储管理(简单页式存储管理)的原理：系统若能满足一个作业所要求的全部块数，此作业才能被装入内存，否则不为它分配任何内存。
- 请求分页式存储管理的原理：运行一个作业时，并不要求把该作业的全部程序和数据都装入内存，可以只把目前要执行的几页调入内存的空闲块中，其余的仍保存在外存中，以后根据作业运行的需要再调入内存。
参考：分页存储管理的基本原理 页式地址变换——虚地址的计算方法
4.3.1页面与页表
4.3.1.1页面和内存物理块
将进程的逻辑地址空间分成若干个大小相等的片称为页面或页。
同一进程的页面按序从小到大进行编号，称为页号。
将内存空间分成与页面相同大小的若干个存储块，称为块或页框。
内存块号按序从小到大进行编号，称为块号。
在为进程分配内存时，进程的任何页面可以存放在内存任何物理块中（离散分配）：
进程的最后一页经常装不满一块而形成页内碎片。
4.3.1.2页面大小的选择
由机器的地址结构所决定的，即由硬件所决定。某一种机器只能采用一种大小的页面：
-
过小：内碎片小，内存利用率高。但页面数目多，使页表过长，占大量内存，管理开销大。
-
过大：页表短，管理开销小，内碎片大，内存利用率低。
页面大小是２的指数幂使地址映射过程非常容易，通常是512B（B-字节）~8KB
4.3.1.3地址结构
个人理解：
就是创建了一个跟用户程序内存一样的虚拟内存，把虚拟内存等比例分割成了若干个页面，然后通过硬件把每个页面（二进制）分成了页号和页内地址两部分，最后通过页表映射得到物理地址访问内存。
用户程序遭到破坏了吗？
没有。用户的程序在逻辑上是连续的，它并不知道自己被划分成了多个页。当程序需要访问内存时，它会生成一个虚拟地址，这个虚拟地址包含页号和页内地址（偏移量）。这个虚拟地址是被划分的，而不是用户的程序。
特定的机器，其地址结构是一定的。
地址结构分为逻辑地址结构和物理地址结构。
进程逻辑地址A分为两部分：页号P与页内地址（位移量）d
上例地址长度为32位:
2^32^ =2^2^ * 2^30^ = 4GB
2^2^ * 2^10^ = 4KB
2^20^ = 1MB
0~11位为位移量(页内地址)，即每页的大小为4KB
- 如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是2^K^个内存单元
12 ~31位为页号，地址空间最多允许有1M页
- 如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有2^M^个页面对于某
页号P：
$$ P =INT[\frac{A}{L} ]=取整[\frac{逻辑地址}{页大小} ] $$ **页内地址d**： $$ d =[A]MOD[L]=[逻辑地址]取余[页大小] $$ 如系统页面大小为1KB，Ａ=2170D，则P = INT[2170/1024] = 2、d = 2170mod1024 = 122
4.1.3.4页表
页表记录进程每一页在内存中存放的块号，即记录进程页面与内存物理块号之间映射关系。
页表实现了从页号到物理块号的地址映射。
页表放在内存中。
4.3.2地址变换机构
地址变换机构实现从进程逻辑地址到物理地址的转换。
- 通过页表将页号转换成内存的块号
- 因为一页大小等于一块大小，所以逻辑地址中的页内地址可以直接拿来作为物理地址中的块内地址
4.3.2.1基本地址变换机构
页表的始址和页表的长度存放在进程PCB中
在进程执行时，页表的始址和页表的长度送入页表寄存器PTR
地址变换流程：
- 页号与页表长度做比较，判断页号是否在页表里；
- 找到逻辑地址页号对应的页表页号的内存地址：页号+页表始址=页表页号内存地址；
- 把页表页号对应的块号赋值给物理地址的块号；
- 把页内地址直接赋值给物理地址的块内地址，得到完整的物理地址；
- 通过物理地址定位到要用的内存位置
怎么把用户程序调入到物理地址对应的内存位置的？
操作系统查找页表，找到与虚拟地址对应的物理地址，这个物理地址实际上是一个内存块（页框）的起始地址。
具体来说，“页面调入”的过程如下：
- 操作系统选择一个空闲的内存块（页框）来存放调入的页。如果内存已满，操作系统可能需要使用某种页面替换算法（如LRU，FIFO等）来选择一个被替换出内存的页框。
- 操作系统从外存中读取需要的页，然后将其复制到选择的页框中。
- 操作系统更新页表，将虚拟地址对应的页号映射到新的页框。
如果这个页框（物理地址定位的内存块）已经在内存中，那么操作系统就可以直接通过物理地址和页内地址访问到具体的数据。这个过程被称为“页面命中”。
如果这个页框不在内存中，那么就会发生“页面错误”。在这种情况下，操作系统需要从外存（如硬盘）中将该页框调入内存。这个过程被称为“页面调入”。
须两次访问内存。存储器利用率提高，处理器处理速度降低。
- 第一次：访问页表。找到指定页的物理块号，将块号与页内偏移量拼接形成物理地址。
- 第二次：物理地址找到程序。从第一次所得地址中获得所需数据，或向此地址中写入数据。
4.3.2.2具有快表（TLB）的分页系统的地址变换机构
快表：具有并行查寻能力的特殊高速存储器，也称为“联想存储器”。可以记录常用的页表内容，命中即可快速查询，否则再从页表中查找。
4.3.2.2例子
关于分页的地址变换计算---虚地址结构（就是虚拟内存逻辑地址结构是怎么算出来的）
例1（用进制的方法）.设页面大小为1KB，将逻辑地址3BADH划分为页号和页内偏移量两部分。用16进制表示。
L页大小，P页号，A逻辑地址
L = 1024d = 2^10^ = 0100 0000 0000b 有10位存放页内地址
A = 3BADh = 0011 1011 1010 1101b
P = 0011 10b = 0000 1110 b = 0Eh
W页内地址 = 11 1010 1101 = 3ADh
例2（用公式的方法）.设页面大小为2KB，将逻辑地址3BADH划分为页号和页内偏移量两部分。用16进制表示。
转换为10进制，套用公式即可。
例3.设页面大小为2KB，作业的页表如下图。求逻辑地址3BADH的物理地址。用16进制表示。
P + a = 页表页号，对应的块号为Bh = 1011b
2^20^ B = 1MB
例4:有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH转换成内存地址。
L = 2KB = 2^11^ B = 1000 0000 0000Bb
虚地址：0000 1010 1111 1110
P = 0001 = 1d 页号等于1，对应的块号等于9 = 1001
W = 010 1111 1110
MR逻辑地址 = 块号 W = 0100 1010 1111 1110 = 4AFEh
例5（用公式的方法）:有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址3412D 转换成内存地址。
虚地址 3412d
P = 3412 % 2048 = 1 页表页号为1，块号为9
W = 3412 mod 2048 = 1364
MR = 9*2048 + 1364 = 19796 内存地址为19796
4.3.3两级和多级页表
待学习...
4.4 基本分段存储管理方式
分段式存储管理的原理：
- 作业分为若平个段。每段分配一个连续的内存区，由于各段的长度不等，这些区域也就大小不一。作业各段间不要求连续。
与分页存储管理一样，分段存储管理也有两种方式：
-
基本分段式存储管理
在段式存储管理原理的基础上，将整个作业的全部段装入内存。
-
基本分段式存储管理
在段式存储管理原理的基础上，不要求将整个作业的全部段装入内存。只装入作业的几段即可运行，其余段根据运行需要再装入内存，
4.4.1分段存储管理方式的引入
分页从根本上克服了外零头（地址空间、物理空间都分割），内存利用率提高。
分页的缺点：无论信息内容如何，按页长分割，分割后装入内存有可能使逻辑完整的信息分到不同的页面——执行速度降低，所以考虑以逻辑单位分配内存。
思想：段间离散，段内连续。以逻辑单位分配内存，提高执行速度。
分段的优点：方便编程、信息共享、信息保护、动态增长、动态链接
4.4.2分段系统的基本原理
4.4.2.1分段逻辑地址结构和段表：
-
分段逻辑地址结构
段内地址：2^16^ B = 2^6^ * 2^10^ B = 64KB
段号：64KB
该地址结构允许一个作业最长有64K个段，每段的最大长度为64KB。
-
段表
与页表类似。段表记录进程每一段在内存中存放的(开始)地址及段的大小。
4.4.2.2地址变换机构
与分页类似，有基本地址变换机构和带有块表的地址变换机构：
- 为了访问段内数据，必须两次访问内存，故同样可以采用快表，将段表放入快表中
基本地址变换机构的执行过程：
- 越界判断
- 段号+段表起始地址，找到对应的段表段号
- 段表短号对应的基址+位移量W，找到物理地址
- 通过物理地址找到对应的内存
4.4.2.3分页与分段的主要区别
相似点：
- 采用离散分配方式，通过地址映射机构实现地址变换
不同点：
- 页是信息的物理单位，分页是为了满足系统的需要；段是信息的逻辑单位，含有意义相对完整的信息，是为了满足用户的需要。
- 页的大小固定且由系统确定，由系统把逻辑地址分为页号和页内地址，由机器硬件实现;；段的长度不固定，取决于用户程序，编译程序对源程序编译时根据信息的性质划分。
- 分页的作业地址空间是一维的；分段的作业地址空间是二维的。
4.4.3信息共享
分段系统的一个突出优点是易于实现段的共享和保护。
什么是分段共享？
允许若干个进程共享一个或多个分段。
如何避免共享的代码被某个进程修改？
可重入代码又称为纯代码，是一种允许多个进程同时访问的代码，可重入代码不允许任何进程对它进行修改。
4.4.3.1分段式共享和分页式共享：
-
分段系统的共享：
在分段系统中，实现共享十分容易，只需在每个进程的段表中为共享程序设置一个段表项。
-
分页系统的共享：
分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。
4.4.4.2editor和data
可重入代码，不允许任何进程对它进行修改，为editor区。
局部数据区，程序在执行时只对该数据区(属于该进程私有)中的内容进行修改，为data区。
为什么要分为两个区：
设同时有40个用户并发执行并使用该editor，则需要40 * (160 + 40) = 8MB空间支持。
如果代码可重入，内存只保留1份editor即可，40 * 40 + 160 = 1760KB。
4.4.4段页式存储管理方式
4.4.4.1段页式基本原理
段页式：分段和分页管理的结合。
-
先将用户作业（进程）分成若干具有一定逻辑意义的段，再将段分成大小固定的若干个页
-
段页式系统需要同时设置段表和页表，段表中存放页表始址及页表大小
4.4.4.2段页式地址结构：
4.4.4.3段页式系统的地址变换机构：
需要三次访问内存：访问段表取页表始址、访问页表取物理块号、取指令与数据
