操作系统原理——内存

内存管理的目标

1. 实现内存分配、内存回收等操作
2. 提高内存的利用率和内存的访问速度
   即充分利用现有的内存资源，为应用程序提供方便的内存使用方式和一个快速、安全且充分大的存储器

程序的链接和装入

链接要解决的问题是将编译后的目标模块装配成一个可执行的程序，分为静态链接和动态链接

1. 程序链接

静态链接：在程序运行之前，用链接程序将目标模块连接成一个完整的转入模块，任务：一是对逻辑地址进行修改，二是转换外部调用符号
优点：运行速度快 缺点：可执行文件较大，占用空间大，系统开销大，程序开发不够灵活，修改一个模块会导致整个程序重新连接

动态链接
可将某些目标模块的链接推迟到这些模块中的函数要被调用时再进行。
优点：节省内存和外存空间，方便程序开发
缺点：增加了运行时的开销，是程序运行时速度变慢

2.程序的装入

装入方式：绝对装入方式、可重定位装入（静态装入方式）和动态运行时装入方式

绝对装入方式：编译程序已知程序在内存中的位置，编译时产生物理地址的目标代码，转入程序按照装入模块的物理地址将程序和数据装入内存
可重定位装入方式：编译时不知道程序在内存中的位置，那么编译时就必须生成可重定位的代码，其中的地址都是逻辑地址，在程序转入内存时，再把逻辑地址映射为物理地址。程序装入时对目标称重的指令和数据地址修改的过程称之为重定位转入

静态装入方式的特点：1)编译程序使目标模块的地址从0开始
2) 程序装入时，装入程序根据内存的使用情况将装入模块的装入内存的某个位置，并对模块进行重定位。物理地址=有效的逻辑地址+程序在内存中的其实位置

动态运行时装入：当一个进程在被换出之前的内存地址与后来被从外存调入时的位置不同，这是地址映射延迟到进程执行时再进行。

3.连续分配的存储管理方式

1. 单一连续去分配方式
   适合于单用户单任务系统，内存分为系统区和用户区
2. 固定分区分配
   将用户内存空间分配成若干固定大小的区域，每个区域运行一道用户程序；分区的数量固定的，大小也是固定的
   每个分区大小相等的分配方式缺点是：内存利用率低，主要用于一个计算机去控制多个相同对象的场合，如冶炼炉
   在一些实时系统中，固定分区的分配方式还是简单而有效的
3. 动态分区分配方式
   用户分区的数量和大小都是动态变化的
   分配原理：系统初始只有一个大的空闲分区，当进程请求内存资源时，系统根据请求资源的大小分配一片空闲区域给进程，当运行一段时间后，空闲分区可能散布在不连续的区域，这时候系统会维护一个记录当前空闲分区的数据接口，当进程请求内存时，系统从所有空闲分区中找到一个合适大小的空间给进程。
   数据结构：空闲分区表和空闲分区链
   空闲分区链可以动态为每个分区建立一个节点，每个节点包括分区大小、分区起始地址、指向前一个空闲分区节点的指针、指向后一个空闲分区节点的指针。每一个节点占用的内存动态分配、动态回收。

动态分区分配算法

1. 首次适应算法FF
   要求空闲分区链以地址递增的顺序进行连接，每次从链首开始查找，低地址空间可能会被反复划分 缺点：造成空间浪费，内存碎片
2. 循环首次适应算法NF
   不在每次从链首开始查找，而是从上一次查找的空闲分区的下一个分区开始查找，每次应设置一个起始查找指针，指示下一次查找的分区
3. 最佳适应算法BF
   为了方便查找，把所有空闲区，按照空闲大小递增的顺序进行排列，总是把大小和进程请求的内存空间大小接近的空间分配给进程。
   优点：避免了大材小用，提高了内存的利用率
   缺点：容易留下难以使用的小空闲区

4. 基于分页存储的管理方式

把进程的存储在内存中的物理地址不连续的区域，这种内存管理方式称为离散内存管理方式。
离散内存管理分配内存空间的管理方式有：分页存储管理，分段存储管理、段也式存储管理

页：将一个进程的逻辑地址空间分为若干个大小相等的片，，称之为页
页框：将物理内存地址分成与页大小相同的若干个存储块，称之为页框

业内碎片：进程的最后一页一般装不满一个叶框，而形成了不可利用的碎片称为页内碎片。

页表：实现页号到页框的映射，在基本的分页制度中，每个进程有一个页表，进程的每一页在页表中有一个对应的页表项，页表在内存中连续存放。

分页管理方式的地址结构
页的存储结构：
页号P 页内偏移量W
若用m位标识逻辑地址，页大小为2的n次方，则用低n位表示页内偏移量w,用高位m-n位表示P

分页地址变换：实现逻辑地址到物理地址的转换
公式:物理地址=页框号x页框大小 + 页内偏移量

为了减少cpu在有效访问内存时间上的开销，提高内存的速度，引入了快表机制
快表:也称转换后的缓冲是为了提高访问内存速度而采用的专用缓存，存放最近访问过的页表项。

4. 基于两级页表和多级页表的管理方式

页表再分页，就形成了两级或者多级页表
两级页表：将页表再分页，使得每个页表分页的大小与内存页框的大小相同
页目录号实际是一个索引值，根据p1从也木勒表项中找到页表所在的页框号，页号p2是页表中的偏移量，根据p2可以知道应该从也飙中的第p2项找到进程页所在的页框号。

5. 基于分页虚拟存储的系统

虚拟存储技术实现的基本思想是：只把进程的一部分装入内存，在进程执行的过程中，cpu访问内存如果发现所访问的内容不再内存中，则通过异常处理将所需的内容从外存调入内存。
虚拟存储技术的好处：

1. 提高内存的利用率
2. 提高多道程序度
3. 把逻辑地址空间和物理地址空间分开，程序员不用关心物理内存的容量对编程的限制。

虚拟存储技术的特征

1. 离散性
2. 多次性
3. 对换性

6. 页的分配策略

最少页框数：是指保证进程正常运行所需的最少页框数。操作系统为进程分配的页应该大于或者等于最少页框数

页分配策略：固定分配策略和可变分配策略
页置换策略：局部置换和全局置换。1)局部置换发生置换时，只从请求置换的进程本身的内存页中选择淘汰页，腾出内存空间 2)全局置换是指发生置换时，从所有进程的内存页中选择淘汰的页。
也有局部置换和全局置换组合的策略：1)固定分配局部置换 2可变分配局部置换 3)可变分配全局置换

分配算法

1. 平均分配算法n进程m页框，则分配INT[m/n]个页框，余数放入缓冲
2. 按比例分配算法，为进程分配的页框数=进程页数/所有进程页数总和 * 总页框数
3. 优先权的分配算法

7.页调入策略

1. 系统可以在进程需要时将页调入内存，有利于内存的使用率，但是对系统的时间性能不利
2. 采用预先调入页的策略，将预计不久后会被访问的页预先调入内存

8.页置换算法

1. 最佳置换算法ORA:该算法选择以后永远不会被访问的页或者长时间不会被访问的页作为换出页
2. 先进先出置换算法FIFO：最简单。当选择换出页时，选择进入内存时间最早的页（用指针指示当前调入新页时，应当淘汰的那个也在队列中的位置，换出后，指针指向下一个应该淘汰的页）
3. 最久未使用的LRU置换算法：性能较好的算法，该算法是选择最久未使用的页换出。
4. 其他置换算法：附件引用位算法、简单clock算法、改进型clock算法、最少使用置换算法、页缓冲算法

9.分段存储管理

引入分段机制的优点是方便编程、分段共享、分段保护、动态链接以及存储空间的动态增长