一、程序的链接与装入
编译
由编译程序将用户源代码编译成若干目标模块
链接
由链接程序将编译后形成的一组目标模块及它们所需的库函数链接在一起，形成一个完整的装入模块。
逻辑地址形成的阶段
1、静态链接
在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。
2、装入时动态链接
将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。其优点是便于修改和更新，便于实现对目标模块的共享。
3、运行时动态链接
对某些目标模块的链接，是在程序执行中需要该目标模块时才进行的。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。其优点是能加快程序的装入过程，还可节省大量的内存空间。
装入
由装入程序将装入模块装入内存运行。
1、绝对装入
绝对装入方式只适用于单道程序环境。在编译时，若知道程序将驻留在内存的某个位置，则编译程序将产生绝对地址的目标代码。
2、可重定位装入
在多道程序环境下，多个目标模块的起始地址通常都从0开始，程序中的其他地址都是相对于起始地址的，此时应采用可重定位装入方式。根据内存的当前情况，将装入模块装入内存的适当位置。在装入时对目标程序中指令和数据地址的修改过程称为重定位，又因为地址变换通常是在进程装入时一次完成的，故称为静态重定位
(3)动态运行时装入
也称动态重定位。程序在内存中若发生移动，则需要采用动态的装入方式。装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器的支持
逻辑地址与物理地址
1.形成逻辑地址的阶段：链接
2.形成物理地址的阶段：装⼊或程序运⾏时
二、覆盖与交换(*)
覆盖
简言之: 把用户空间分为固定区和覆盖区，把活跃的进程部分放入固定区
一般只在早期单一连续存储管理中使用
交换
把处于等待状态的进程放入主存，把准备好竞争的进程调入主存
三、内部碎片与外部碎片
内部碎片
为一个进程分配了 500MB内存空间，而进程只使用了100MB，剩下的400MB内存就被浪费了，属于内部碎片
外部碎片
如图，小的白色框代表的内存就是外部碎片，它由于太小而难以被利用，而又由于太多而浪费内存空间，可以采用紧凑技术来整理外部碎片
四、动态分区分配算法
这些都是单一连续分配算法
⾸次适应算法
按地址递增的次序
最简单，效果最好，速度最快
邻近适应算法
从上次查找结束的位置开始
⽐⾸次适应算法差
最佳适应算法
按容量递增的次序，找最小的
性能很差，会产⽣最多的外部碎⽚
最坏适应算法
按容量递减的次序，找最大的
可能导致没有可⽤的⼤内存块，性能差
五、分页
分页不会产生外部碎片，并且内部碎片产生也很小，只会在每个进程的最后一个不完整的块里产生
⻚表的起始地址放在⻚表基址寄存器PTBR中
每个进程都有⼀张⻚表...
在多个进程并发执行时，所有进程的页表大多数驻留在内存中，在系统中只设置一个页表寄存器(PTR),它存放页表在内存中的始址和长度。
平时，进程未执行时，页表的始址和页表长度存放在本进程的PCB中，当调度到某进程时，才将这两个数据装入页表寄存器中。每个进程都有一个单独的逻辑地址，有一张属于自己的页表。
页表常驻内存，但不是所有页表都常驻内存
地址转换工作确实是由硬件完成的，对用户透明
页表由操作系统维护并被处理器引用
六、分段
分段会产生外部碎片
对用户可见
段号和段内偏移一定要显式给出
有利于程序动态链接
七、段页式
段页式无外部碎片，有内部碎片
先分段后分页，因为段已经被页化了，所以不会有外部碎片，相当于我们先把程序分成一个一个段，然后把它切成一个一个页，然后放在内存里，注意这与分页有区别，是因为一个段的页是连续存在的，每个段都可以连续分配，因为这个段已经被切割成页的粒度，而页式是每个页都离散分布的。
八、错题3.1
采用段式存储管理时，一个程序如何分段是在用户编程时决定的。
分段有利于程序动态链接
某个操作系统对内存的管理采用页式存储管理方法，所划分的页面大小必须相同以方便系统管理
T34
对主存储器的访问，(B)。
A.以块（即页）或段为单位
B.以字节或字为单位
C.随存储器的管理方案不同而异
D.以用户的逻辑记录为单位
这里是指主存的访问，不是主存的分配。对主存的访问是以字节或字为单位的。例如，在页式管理中，不仅要知道块号，而且要知道页内偏移
把作业空间中使用的逻辑地址变为内存中的物理地址称为 地址重定位。
p162有原话
T43
在采用二级页表的分页系统中，CPU页表基址寄存器中的内容是当前进程的一级页表的起始物理地址
页表是存放在物理内存中的，所以PTR必须存放的是物理地址才能找到一级页表的位置
进程中的块称为页或页面，内存中的块成为页框或页帧
p182-T12(3)图中的页框号指的是他所指内存的页框号
段页式访存次数
在段页式系统中，为了获得一条指令或数据，须三次访问内存。 第一次访问是访问内存中的段表，从中取得页表始址；第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。
九、虚拟存储器
特征
1、多次性
是指无须在作业运行时一次性地全部装入内存，而允许被分成多次调入内存运行
即只需将当前要运行的那部分程序和数据装入内存即可开始运行。
2、对换性
是指无须在作业运行时一直常驻内存，在进程运行期间，允许将那些暂不使用的程序和数据从内存调至外存的对换区（换出），待以后需要时再将它们从外存调至内存
3、是指从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际的内存容量。这是虚拟存储器所表现出的最重要特征，也是实现虚拟存储器的最重要目标。
驻留集
指请求分页存储管理中给进程分配的物理块集合
使⽤覆盖，交换⽅法可以实现虚拟存储
虚拟存储技术只能基于⾮连续分配技术
内存分配策略---固定分配局部置换
为每个进程分配一定数目的物理块，在进程运行期间都不改变。所谓局部置换，是指如果进程在运行中发生缺页，则只能从分配给该进程在内存的页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。实现这种策略时，难以确定应为每个进程分配的物理块数目：太少会频繁出现缺页中断，太多又会降低CPU和其他资源的利用率。
内存分配策略---可变分配全局置换
先为每个进程分配一定数目的物理块，在进程运行期间可根据情况适当地增加或减少。所谓全局置换，是指如果进程在运行中发生缺页，系统从空闲物理块队列中取出一块分配给该程，并将所缺页调入。这种方法比固定分配局部置换更加灵活，可以动态增加进程的物理块，但也存在弊端，如它会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降。
内存分配策略---可变分配局部置换
为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，因此不会影响其他进程的运行。若进程在运行中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直至该进程的缺页率趋于适当程度：反之，若进程在运行中的缺页率特别低，则可适当减少分配给该进程的物理块，但不能引起其缺页率的明显增加。这种方法在保证进程不会过多地调页的同时，也保持了系统的多道程序并发能力。当然它需要更复杂的实现，也需要更大的开销，但对比频繁地换入/换出所浪费的计算机资源，这种牺牲是值得的。
物理块调入算法
采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述几种算法。
1)平均分配算法，将系统中所有可供分配的物理块平均分配给各个进程。
2)按比例分配算法，根据进程的大小按比例分配物理块。
3)优先权分配算法，为重要和紧迫的进程分配较多的物理块。通常采取的方法是把所有可分配的物理块分成两部分：一部分按比例分配给各个进程：一部分则根据优先权分配。
调入页面时机
从何处调入
因为考的少，所以这部分内容掌握的一点都不牢固，还得多复习
十、页面置换算法
OPT最佳置换算法
基于队列，Utopia 式的算法,无法实现，只能⽤于评价其他算法
FIFO先进先出算法
淘汰在内存中驻留时间最久的⻚⾯
会出现 Belady 异常(分配的物理块数增⼤但⻚故障数不减反增
LRU最近最久未使用算法
淘汰最近最⻓时间未访问过的⻚⾯
性能好，但实现复杂，需要寄存器和栈道硬件⽀持，堆栈类算法
耗费⾼因为要对所有⻚排序
最接近OPT
时钟置换算法CLOCK 或者叫 最近未使用算法(NRU)
淘汰最近未使⽤的⻚⾯
FIFO和LRU的结合
由于LRU实现起来消耗很大，因此提出CLOCK算法来代替LRU
算法实现如下(很容易遗忘，多看多记)
改进型CLOCK置换算法
考虑到了替换修改过的页面需要写回磁盘这个问题，由于写回磁盘开销很大，因此这个算法在CLOCK算法的基础上又增加了修改位
在选择页面换出时，优先考虑既未使用过又未修改过的页面.
考前记一记，喝前摇一摇
十一、其他零散的知识点
抖动
刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动或颠簸。
所有⻚⾯置换策略都有可能造成抖动
系统发生抖动的根本原因
系统中同时运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页，必须请求系统将所缺页面调入内存。
这会使得在系统中排队等待页面调入/调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，进而导致发生处理机的利用率急剧下降并趋于零的情况。
工作集
由于抖动，所以引入了工具集的概念
落在工作集内的页面需要调入驻留集中，而落在工作集外的页面可从驻留集中换出。
实际应用中，工作集窗口会设置得很大，即对于局部性好的程序，工作集大小一般会比工作集窗口小很多。工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合
分配给进程的物理块数（即驻留集大小）要大于工作集大小
内存映射文件
与虚拟内存有些相似，将磁盘⽂件的全部或部分内容与进程虚拟地址空间的某区域建⽴映射关系
可以直接访问被映射的⽂件，⽽不必执⾏⽂件I/O操作，也⽆需对⽂件内容进⾏缓存处理
适合⽤来管理⼤尺⼨⽂件
一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时，就能立刻看到上一个进程写操作的结果。
虚拟存储器性能影响因素
-
⻚⾯较⼤—>缺⻚率较低—>可以减少⻚表⻓度，但使得⻚内碎⽚增⼤
-
⻚⾯较⼩—>缺⻚率较⾼
—>可以减少内存碎⽚，提⾼内存利⽤率
—>使得⻚表过⻓，占⽤⼤量内存 -
分配给进程的物理块数越多，缺⻚率就越低
-
分配给进程的物理块数超过某个值时，对缺⻚率的改善并不明显
-
好的⻚⾯置换算法可以使进程在运⾏过程中具有较低的缺⻚率
-
LRU，CLOCK将未来可能要⽤到的进程保存在内存中，可以提⾼⻚⾯的访问速度
-
编写程序的局部化程度越⾼，执⾏时的缺⻚率越低
-
存储和访问尽量使⽤系统的访问⽅式（如都按⾏存储就按⾏访问）
注意区分几级页表
这是二级页表
这是四级页表
磁盘块和物理页框号的大小不一定一致
做题的时候，题目照顾考生，一般会设置一致，但实际上是不一致的！！！
十二、错题3.2
导致LU算法实现起来耗费高的原因是: 需要对所有的页进行排序 (p206-T13)
LRU算法需要对所有页最近一次被访问的时间进行记录，查找时间最久的进行替换，这涉及排序，对置换算法而言，开销太大。为此需要在页表项中增加LRU位
T15.在虚拟存储器系统的页表项中，决定是否会发生页故障的是(A)。
A.合法位
B.修改位
C.页类型
D.保护码
页表项中的合法位信息显示本页面是否在内存中，即决定了是否会发生页面故障。
页面调入是从磁盘调入
做选择题的时候要拿捏住是变快了还是变大了
页、页表、页框大小的问题又记混了，整理一下(p213-T18(1))
页: 进程中的块（进程被分成许多大小相同的块）
页框:内存中的块（内存被分成许多大小相同的块）
页表: 页表记录进程页面和实际存放的内存块之间的对应关系，每个进程都有一个页表
由此可见，页表是一个更大的概念
行优先存放、列优先存放、按行存储、按列存储 p(215-T21(3))
概念记混了
注意，按行优先存放的意思是优先存放一行，而不是优先存放每列的第某行
按行优先存放 <=> 按行存储 这就是目前计算机主流的存放方式
按列优先存放 <=> 按列存储
int arr[10][10];
按行优先的arr[9][2]的位置等于 按列优先的arr[2][9]的位置
同一进程的线程切换时，PDBR寄存器不会变化的原因
(自己的回答总是不够标准)
同一进程中的线程共享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，因此PDBR的内容也不变。