操作系统之内存管理

连续分配

一、单一连续

直接为要运行的进程分配一个内存，只适合单任务，只能用于单对象、单任务，内存被分配为系统区和用户区，系统区在低地址，用户区是一个用户独享

二、等分分区

由于分配一个内存只能执行单任务，所以出现了等分区的优化，可以多任务在不同的分区去工作，但是等分内存空间，导致进程大则无法放入，进程小则浪费空间；

三、不均匀的分配大小
提前将内存分为不同的分区大小，当进程进来的时候，分配最相近大小的内存块给他，但是这样也会产生很多外部碎片（由于进程放不进而浪费的空间）和内部碎片（进程太小了放入空间的时候有一部分空间没有使用导致浪费）

四、动态分配空间

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上
外部碎片：是指内存中的某些空闲分区由于太小而难以利用（如果有外部碎片，可以采用紧凑技术）

根据进程的大小来分配空间，但是由于操作系统是二倍数的大小，导致会产生很多的内部碎片

根据进程大小动态分配空间，容易产生碎片，当内存使用完毕之后，将使用的空闲分区使用链表或者空闲分区表记录

1、首次适应算法（First Fit)

算法思想：每次从低地址开始查找，找到第一个能满足大小的空闲分区

2、最佳适应算法(Best Fit)

算法思想：为了保证“大进程”到来时能有连续的大片区域，可以尽可能留下大片的空闲区，优先使用更小的空闲区。

空闲分区按容量递增次序链接，分配内存时顺序查找空闲分区链

缺点：会留下小碎片

3、最坏适应算法(Worst Fit)

算法思想：和最佳适应算法相反，按容量递减次序排列，每次尽可能用大的分区

4、领近适应算法(Next Fit)

算法思想：每次从上次查找结束的位置开始检索

缺点：大空间容易被用完

（四）根据静态和动态组合成伙伴系统

根据总内存一次一次的划分，当使用 完成后如果内存来自于统一块，就直接合并内存

非连续分配

由于连续分配的时候，会产生很多的碎片，后续出现了紧凑操作可以将碎片压缩在一起，但是比较消耗性能，所以出现了非连续的分配内存的方式。

一、页存储方式

分为逻辑地址和物理地址映射、允许一个进程分散地装入道许多不相邻的位置

连续分配：为用户进程分配连续的内存空间
非连续分配：为用户进程分配分散的内存空间

将内存分为大小相等的小分区“页框”，将用户的进程空间也分为大小相等的一个个区域，以页框的基本单位分配给每个进程片

分页管理：物理地址=页面的其实位置+偏移量
计算机中用2的整数倍表示页面的大小

页表：存放页号和块号的对应关系

举例：一段代码执行的时候，通过访问逻辑地址，然后通过页表去访问物理地址拿到信息，页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M，进程未执行时，页表的起始地址和页表的长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放在页表寄存器中。

二、段式储存

1、什么是分段？
进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每段有段名，每段从0开始编址

段号的位数决定了每个进程最多可以分几个段

段内地址位数决定了每个段的最大长度是多少

2、什么是段表

段表：段映射表

每个程序被分段后，用段表记录该程序在内存中存放的位置

段表：段号 段长 基址

3、如何实现地址变换

4、分段、分页管理的对比

页：信息的物理单位，实现离散分配，提高内存利用率，地址是一维的，访存两次

段：信息的逻辑单位，对系统可见，地址是二维的，访存3次

分段比分页更容易实现信息的共享和保护（不能被修改的代码称为纯代码和可重入代码，不属于临界资源）

三、段页式储存
1、分页、分段管理方式最大的优缺点

分页：利用率高，碎片少，不方便进行信息共享和保护

分段：方便信息共享和保护，如果段长大，容易产生外部碎片

2、分段+分页的结合——段页式管理方式

先分段再分页

段号+页号+页内偏移量

地址结构是二维的

3、段表、页表

虚拟内存技术

一、定义和特征

虚拟内存最大容量是计算机地址结构确定的

虚拟内存的实际容量=min(内存和外存容量之和，CPU寻址范围)

eg：某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB.

则虚拟内存的最大容量为 2^32B=4GB

虚拟内存的实际容量=min(2^32B,512MB+2GB)=2GB+512MB

多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调用内存
对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入换出
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量

在程序执行过程中，当所访问的信息不再内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

覆盖技术

是以进程为单位，发生在同一个进程内的不同执行的模块间，解决一个进程空间需求无法满足的问题，通过程序员定义的模块间的逻辑结构来进行页的覆盖

交换技术

进程的换入：系统定时的查看所有进程的状态，从中找出“就绪”状态且已换出的进程，将其换出时间最久的进程换入；
进程的换出：当某种由于创建子进程而需要更多的内存空间，但又无足够的内存空间时，则系统将某进程换出，一般选择阻塞状态且优先级最低的进程换出；

虚拟储存技术
当所需要访问的页面不在内存中的时候，就会发生缺页中断，请求系统所需的页调入内存，

页面置换算法
1、最佳置换算法（OPT）

每次选择淘汰的页面是以后永不使用或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

实际上不知道后面的序列

2、先进先出置换算法（FIFO）

每次选择淘汰的页面是最早进入内存的页面

Belady异常，当分配的内存块增大时，缺页次数反而增加

3、最近最久未使用置换算法（LRU）

每次淘汰最近最久未使用的页面

4、时钟置换算法（最近未用算法，CLOCK）

简单的：最多经历两轮扫描，初始为1，扫一下为0，再扫一下被踢

5、改进型的时钟置换算法

优先淘汰没有被修改过的，因为没有修改过的不用进行IO操作00->01（改）->00->01