操作系统笔记-内存

现代操作系统都采用的是逻辑地址，即我们在程序中定义的地址都是逻辑上的并不是真正的物理地址，原因是因为在多道程序中是不能确定到程序运行后的物理地址的，有可能被其他程序占用，有可能会动态的改变其地址，例如物理地址在02位置，当01位置的数据变大后导致数据02的空间需要被占用，此时物理地址会发生变化。逻辑地址可以让每个进程自己的地址都是连续的即在逻辑上是连续的。

物理地址

物理地址实际上就是我们内存条上的地址。可以简单的理解为逻辑地址就是一个相对位置，而对于物理地址就是物理地址。

程序从编写到装入过程

1、程序员编写程序

2、（编译）将程序进行编译产生逻辑地址

3、（链接）链接就是将自己编写的程序和自带库或者引入的库代码进行关联

4、（装入）将链接好的程序装入到内存中。

装入程序的方式

绝对装入

将整个程序直接装入到物理地址的某个地址，绝对装入存在问题，不适合多道程序，在多道程序中无法确定装入的物理地址是否被占用。

静态重定位

将整个程序在编译的时候产生逻辑地址，然后在装入的时候直接由系统分配对应的物理地址，此时只会找到没有被占用的地址，但是此时同样也是将整个程序全部装入到内存中，占用内存较大，可能程序中某一部分地址是不会执行的，同时无法修改其程序的地址，一旦装入后就无法进行改变。

动态重定位

程序运行时可以只是先装入部分的数据，即重要的数据，然后后面根据实际情况需要进行装入，同时可以支持不连续的空间，也能够程序地址发生变化，因为此时逻辑地址和物理地址并不是一次装入进行映射的，而是多次，且可以不连续，同时能够节省内存减少其程序不必要的数据的加入。

内存保护

为了安全，当程序装入到内存后，实际上每一个进程只能访问自己对应的地址空间范围，而不能访问其他程序的地址空间，所以操作系统实现方式如下。

采用上限寄存器和下限寄存器用于记录当前进程的最小物理地址和最大物理地址，当进程进行访问的时候判断其是否在上下限寄存器空间范围内，如果不在则不允许访问。

交换技术

由于现代程序大小远大于内存大小，如果一个程序2g而运行内存只有1g，那么是否就以为着不能使用呢，实际上我们会采用交换技术，首先装入程序的时候采用动态重定位，这样每次只是载入一部分核心数据到内存，然后需要那些数据再加载到内存，而如果内存不够用，那么就将内存中的一部分进程唤出即挂起，然后将其对应的内存进行释放，此时就能够腾出内存使用，被挂起的进程的pcb依然在内存中，这是为了方便后面一旦使用到此程序的时候需要通过pcb来找到对应被唤出的进程对应的数据以及地址在哪儿。

交换技术一般可以采用lru，即把最早没有使用的进程进行唤出，然后腾出空间，一旦进程重新使用后，那么在此进行唤出。

ps：交换技术中唤出的进程的数据存放在磁盘的sawp空间，即交换空间，是磁盘中一块非数据存储的空间，且是连续的空间，其速度是快于其磁盘的文件空间的。

连续内存的分配

单一分配

只支持单道程序，直接将内存中的用户内存全部分给用户进程，会产生内部碎片，无外部碎片

固定大小分配

将内存划分为固定大小的多个块，当程序装入后根据情况选择对应的块空间即可，但是由于是固定大小的，此时会产生内部碎片，无外部碎片，支持多道程序。由于是固定大小的块其中如果一个块占用空间很小，那么对于整个块来说内存产生了浪费。

动态分配

不再是根据预先就将内存分成多个块，而是每装入一个程序根据程序大小进行划分内存，适用于动态重定位装入，不会产生内部碎片，但是会产生外部碎片，可能剩余的空间不够用了。

8、内存的回收

在动态分配的时候进行内存回收的时候，如果存在相邻的空间，那么回收后需要进行合并

内存的记录

os如何知道那些内存没有被使用呢，可以通过两种方式。

空闲分区表

采用表结构记录内存中对应区间是否空闲，其中表中字段包括大小，起始地址。当内存被回收后如果相邻合并后增加其大小。

空闲分区链

将内存中空闲的区域变成一个链表，进行连接，同样被回收和直接将多个相邻的链表节点进行合并。

非连续内存的分配

在连续内存分配中，单一分配只支持单道程序，同时会产生内部碎片，而固定大小同样会产生内部碎片，而动态分配会产生外部碎片，虽然可以使用紧凑技术，但是实现复杂同时依然性能低。

非连续分配

将物理内存划分为多个很小的块(页框)，将逻辑地址划分为多个页面，且分配的时候是运行时只是加载其核心程序，这样能够将一个很大的程序加载到内存中。

非连续分配逻辑地址和物理地址的计算拿到一个逻辑地址后，首先每一个进程都有一个页表，其中页表中的页号是连续的，然后每一个页号对应一个物理地址的页框。

根据逻辑地址/页号数量=对应的页号中的页框物理地址%页面数量 = 偏移量，此时用页框+偏移量=对应的物理地址

如何根据逻辑地址找物理页

首先PCB中存放了页表，当cpu调度此进程的时候，然后此时将PCB中的页表加入页表寄存器，同时程序计数器的数据也会加入到程序计数器中，然后拿到逻辑地址以后根据逻辑地址/页号数量，以及偏移量，如果超出了对应的物理数据范围，那么发生页越界，没有越界的话直接根据上面的计算方式进行计算得到物理页。

TLB(快表)

根据时间局部性原理和空间局部性原理，一个指令如果当前时间被访问很有可能会被继续访问例如可能循环语句，而空间局部性则是如果一个相邻的地址被访问，那么相邻的地址很有可能马上会被访问，如数组，所以一般操作系统会在cpu的内部缓存中如L1、L2、L3等中放入访问的页表，这样每次访问数据的时候步骤如下

1、检查快表中是否存在对应的页表数据，有则直接用页表中的物理地址访问内存

2、如果没有，那么从内存中访问进程的页表及页表寄存器，然后再访问内存的物理地址，此时会访问两次内存。

3、访问成功后将数据添加到快表中，方便下一次进行访问。

段表

将进程分为多个连续不同大小的块，每一段指令就是一个段，因为是按需分配的即执行到对应的段以后才会分配内存，和按页分配类似，每一个段都对应一个物理地址，然后同样根据逻辑地址/段数量=段号，然后逻辑地址%段数量=偏移量，通过段号+偏移量=具体的物理地址，按段分配会产生外部碎片，原因是一个段如果开辟的空间是4m，一旦这个段用完后，重新加入一个2m的进来，则会存在2m的碎片。此时如果想加入的段需要3m，由于分段需要连续的空间，前面有2m，后面本身如果还有1m是可以使用的，但是因为需要连续的，所以此时是不能分配的，会产生外部碎片，进程中的段表会存放到段表寄存器中。段表中存放的数据有段表号，起始地址，段表的大小

段页式管理

段页表就是将段表和页表进行结合，首先同样将进程分成多个段，然后每一个段中存放具体的页，然后访问物理内存的时候先根据逻辑地址/段数量=段号，然后逻辑地址%段数量=偏移量，通过段号+偏移量=具体的页表项，然后根据计算规则计算出页表中对应的物理地址。

ps：无论是按页分配还是按段或者段页是分配，都是非连续内存的分配方式，但是由于可能一个进程很大，如GTA5 60g那么此时运行内存只有16G实际上是不能运行的，因为连续分配和非连续分配都是采用的一次性将整个进程全部加载到内存中。

虚拟内存

由于原本的连续分配和非连续分配都存在一次性将程序全部加载到内存中，此时可能会出现如GTA5 60g那么此时运行内存只有16G实际上是不能运行的，因为连续分配和非连续分配都是采用的一次性将整个进程全部加载到内存中。

虚拟内存是每次将需要用到的关键程序才分配对应的内存，如果内存被分配完以后根据页面置换算法，将一部分内存放入到swap区即磁盘中的一块连续的区中，然后此时就会腾出空间，然后就能使用。

虚拟内存访问步骤

1、查看TLB快表中是否存在该页

2、如果存在直接通过逻辑地址对应的物理地址访问内存，如果不存在那么此时访问内存中的逻辑页

3、如果内存中的逻辑页存在，此时访问其逻辑页对应的物理地址，如果不存在，此时进行缺页中断，CPU将保存现场，同时将发生磁盘对应的数据加载到内存中，设置状态位为1表示已经调入内存，同时设置访问字段为1，可能会将此页放入到TLB快表中，后续访问的时候直接进行访问，如果再次访问那么访问字段数量会进行加1，修改数据后会将修改位变成1，这样是为了后续放入到swap区以后先将修改的数据存储到磁盘上。

页面置换算法

最佳置换算法

计算出那些页长时间没有被使用，同时以后也会长时间不会使用的页面进行淘汰，算法难以实现，同时是最佳的方案，能够极少的减少swap交换

先进先出算法

通过队列先进的先出，即最先分配的页先淘汰，算法简单，但是会导致当一个进程分配的页面增大后，缺页中断也会随之增多。同时并不会减少swap交换。

LRU算法

最近最早未被使用，当进行swap的时候，此时需要看那些是最早没有被使用的然后进行淘汰，最接近最佳置换算法，能够减少其swap交换。

时钟置换(CLOCK)算法

将对应的页表中的页面变成一个环行链表，同时由于页面中记录了是否访问位可以通过其访问位来进行判断，判断逻辑为如果遇到访问位为1的则变成0，如果找到第一个访问位为0的则选择该页。

可能会产生两次链表的遍历，如果全部访问位都是1，那么第一次则需要全部变成0，然后第二次遍历的时候取链表头。

改进的时钟置换算法(CLOCK)

在原本的CLOCK算法中，由于每个页都存在是否修改的标志位，对于置换算法来说如果置换的是一个没有被修改过的页，那么就不需要刷到磁盘的page cache上，这样能够减少其io，改进后的时钟置换算法步骤如下

1、先找到访问位为0，且修改位为0的数据，此时不再修改访问位从1变成0

2、如果第一步没有找到，那么继续找访问位为0，修改位为1的，同时将访问位为1的修改位0，这样的目的是0可以表示最近没有使用的，而优先考虑没有使用的而不是修改位为0的，因为这样很有可能会继续发生swap交换，因为新访问的页是刚刚淘汰的

3、如果第二步没有找到，那么继续找访问位为0，修改位也为0的，并且不修改访问位

4、如果第三步没有找到，那么继续找访问位为0，修改位为1的此时进行淘汰

ps：对应改进后的时钟置换算法，能够提升性能，但是可能会导致扫描链表的次数变成最多4次。