使用首次适应算法模拟内存的分配和回收_王道操作系统学习笔记（五）内存

内存基础知识

• 内存是用于存放数据的硬件，因为CPU和IO之间存在速度差，所以需要一个缓冲区
• 内存如何分布
  • 内存地址：每个地址对应一个存储单元，会根据内存大小算出存储单元数量，从而计算地址表达需要的位数（4GB，按字节编址，即需要2^32个存储单元，所以地址长32位）
  • 存储单元：存放数据的“小房间”。“按字节编址”--1B一个格子；“按字编址”--1Byte一个格子

指令基础知识

• 指令是进程运行的原理，存放在进程的程序段中
• 指令（我们写的代码）需要编译成机器码，编译生成的指令使用的是逻辑地址（相对地址）

逻辑地址与物理地址区别：

• 逻辑地址是相对的，于当前进程的起始位置的相对值
• 物理地址是绝对的，于0位置的相对值

从写程序到程序运行过程

• 编辑源代码文件
• 编译：由编译程序将用户源代码编译成若干个目标模块（高级语言翻译成机器语言）
• 链接：将目标模块以及所需库函数链接在一起，形成一个完整的装入模块
• 装入：由装入程序将装入模块装入内存运行。把逻辑地址转换到物理地址

绝对装入--程序编译时--单道程序阶段，此时还没产生操作系统（什么都要自己做）

• 编译阶段直接产生绝对地址的目标代码。装入程序按照装入模块的地址，将程序和数据装入内存。
• 绝对装入只适用于单程序环境，因为只有单进程的机子，每个程序需要在什么位置可以提前设置。

静态重定位/可重定位装入--程序装入内存时---早期的多道批处理系统

• 在装入的过程中进行地址的变换。一次完成。因此：
  • 一个作业装入内存时，必须分配其所要求的全部内存空间
  • 作业一旦进入内存，在运行期就不能再移动，也不能再申请内存空间

**动态重定位/动态运行时装入**--程序执行时---现代操作系统

• 装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。所以装入内存后所有地址依然是逻辑地址
• 它依赖于重定位寄存器（基地址寄存器）的支持
• 优点：
  • 程序可以在内存中移动，有利于解决内存碎片问题。因为执行时才转换地址
  • 可将程序分配到不连续的存储区，只要不同的存储区域模块有对应的重定位寄存器
  • 可以动态申请分配内存，实现虚拟化技术。（因为可以灵活的调入调出）

内存管理

内存管理，都叫管理就是对内存的分配和回收，谁来管理？操作系统！

灵魂拷问

• 内存很多位置都可以放，那应该放在哪里
• 操作系统要怎么记录哪些内存区域已经被分配，哪些空闲
• 当进程运行结束之后，如何将进程占用的内存空间回收

内存管理概念/定义

• 操作系统负责内存空间的分配与回收
• 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
• 操作系统提供逻辑地址到物理地址的转换功能
• 操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰。

覆盖与交换

交换技术

• 内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存。（中级调度-内存调度 就是要决定将哪个处于挂起状态的进程重新调入内存）
• 磁盘分为文件区和对换区，换出的进程放在对换区
• 在不同进程之间进行。单位是进程

连续内存管理--回收与分配方式

• 内部碎片：分配给某进程的内存区域大于其实际需要的大小
• 外部碎片：指内存中因为分配与回收的过程产生的空闲分区由于太小而无法利用。（如果是一开始划定的区域太小这种不属于。所以固定分区分配无外部碎片）

单一连续分配

内存被分为系统区和用户区，用户区只能存放一道用户程序

优点：实现简单，无外部碎片，不需要内存保护

缺点：只适用于单用户，单任务的操作系统中；有内部碎片

固定分区分配

将整个用户空间划分为若干各固定大小的分区，每个分区只装入一道作业。

• 分区大小相等：缺乏灵活性，适合用于用一台计算机控制多个相同对象的场合
• 分区大小不等：增加灵活性，可以满足不同大小的进程需求。当用户程序装入内存后，根据分区说明表从中那个找到一个能满足大小的未分配分区，将之分配。
• 优点：实现简单，无外部碎片
• 缺点：有内部碎片，内存利用率低。（比如说10M的程序，占用了12M的一个分区）

**动态分区分配/可变分区分配**(重点)

它不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程需要。因此系统分区的大小和数目时可变的

系统用要用什么数据结构记录内存的使用情况

系统根据空闲分区表进行内存的分配与回收（增加表项或者是合并表项或者是修改表项）

• 优点：无内部碎片，提高内存的利用率
• 缺点：有外部碎片（多次换入换出后，可能产生过小的空闲区），但是外部碎片可以用“紧凑技术”解决（对内存中的程序进行移动使之紧凑）。

动态分区空闲分配算法--针对动态分区算法

如果很多个空闲分区都能满足需求时，该选取哪个分区进行分配

首次适应算法（First Fit）

算法思想

每次都从低地址开始查找，找到第一个能满足的空闲分区

如何实现

空闲分区以地址递增的次序排序。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到第一个大小能满足要求的空闲分区。

最佳适应算法（Best Fit）

算法思想

为了保证“大进程”到来时能有连续的大片空间，所以尽可能留下大的空闲区，即优先使用更小的空闲区

如何实现

空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链，找到大小满足要求的第一个空闲分区

• 必须按照容量递增链接，因此发生变化后，得重新排序
• 每次都选最小的分区进行分配，会留下越来越多的，难以利用的外部碎片。

最坏适应算法（Worst Fit）

算法思想

为了解决最佳使用算法的问题，即留下太多难以利用的小碎片，所以每次分配优先使用最大的空闲区，这样分配后剩余的空闲区就不会太小。

如何实现

空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链。找到大小能满足要求的第一个空闲分区

• 虽然可以使分配后留下的空闲区更大
• 但是这种方式会导致大的连续空闲区被迅速用完。如果之后有"大进程"到达，就没有内存分区可用。

邻近适应算法（Next Fit）

算法思想

首次适应算法每次都从链头开始查找，这回导致低地址部分出现很多小的空闲分区，而每次分配查找都需要经过这些分区。每次都从上次查找结束的位置开始检索。

本质：低地址和高地址的空闲分区都有相同概率的被使用。（然而这样也会导致高地址的大分区更可能被使用，导致无大分区可用）

算法开销大是指对链表进行排序