阅读 45

计算机操作系统基础(八)---存储管理之内存分配与回收

引言

本文为第八篇,存储管理之内存分配与回收,早期计算机编程并不需要过多的存储管理,随着计算机和程序越来越复杂,存储管理成为必要。本篇主要是了解内存分配的过程内存回收的过程

存储管理的意义

  • 确保计算机有足够的内存处理数据
  • 确保程序可以从可用内存中获取一部分内存使用
  • 确保程序可以归还使用后的内存以供其它程序使用

内存分配的过程

单一连续分配

  • 单一连续分配是最简单的内存分配方式
  • 只能在单用户单进程的操作系统中使用

它分配的过程就是把内存分为系统区用户区

系统区指的是系统区所有的内存都给操作系统区使用,用户区指的是用户区所有的内存都给用户区的程序使用(这种已经是过时的方法)

固定分区分配

  • 固定分区分配是支持多道程序的最简单存储分配方式
  • 内存空间被划分为若干固定大小的区域
  • 每一个分区只提供给一个程序所使用,互不干扰

将主存分为若干个分区,每一个分区提供给某一个进程所使用,这就是固定分区的分配方法

动态分区分配

  • 根据进程实际需要,动态分配内存空间
  • 涉及到相关数据结构和具体的一些算法

动态分区空闲表数据结构

假设主存中有若干个分区,有些被使用而有些未被使用,这样就需要一个数据结构去存储某一个分区它是否被使用了,此时就需要空闲表数据结构

在表中有若干个分区,每一个分区都有一个标记,0或1,0表示未被使用,1表示被使用。这就是动态分区空闲表数据结构

动态分区空闲链数据结构

这个是使用双向链表来保存动态分区中的空闲区域。将所有分散的空闲区域,通过链表进行首尾相连,组成一个空闲链表,但是,会存在像下图中空闲区2和3是连续的,因此可以将节点2和节点3给合并起来,这样就可以减少空闲链表的节点。因此,每个节点的大小不一样,所以需要在每个节点里边存储记录这个节点可存储的容量。这个就是动态分区空闲链数据结构

动态分区分配算法

  • 首次适应算法(FF算法)
  • 最佳适应算法(BF算法)
  • 快速适应算法(QF算法)

这些算法是实际进行动态内存分配所使用的算法

首次适应算法(FF算法)

每一次进行内存分配时,从开始顺序查找适合内存区(主要使用空闲链的数据结构) 若没有合适的空闲区,则该次分配失败,如果找到了,就将该空闲区划分给这个进程使用。每次都是从头部开始,使得头部地址空间不断被划分

最佳适应算法(BF算法)

  • 最佳适应算法要求空闲区链表按照容量大小排序
  • 遍历空闲区链表找到最佳空闲区

将空闲区按照大小进行排序,在需要内存的时候,从节点头部开始遍历,寻找最佳的空闲区节点。这种算法的好处就是可以避免一种大材小用的情况,因为它是从小到大遍历这个空闲链表的,所以它匹配到的第一个合适的空闲区,一定是最佳的。

快速适应算法(QF算法)

  • 快速适应算法要求有多个空闲区链表
  • 每个空闲区链表存储一种容量的空闲区

将拥有一个空闲区节点的和拥有两个空闲区节点,分成两个链表。当需要内存分配时,就可以快速的找到适合某一个进程的内存区域。

内存回收的过程

内存回收过程,可能有以下几种情况:

  • 回收区和一块空闲区相邻,且回收区在空闲区下边
  • 回收区和一块空闲区相邻,且空闲区在回收区下边
  • 回收区在两块空闲区中间
  • 单独的回收区

每种情况的回收过程

回收区在空闲区下边

使用空闲链表的数据结构来保存空闲区,不需要新建空闲链表节点、只需要将空闲区1的容量增大为空闲区即可(也就是将回收区包含进来)

回收区在空闲区上边
  • 将回收区与空闲区合并
  • 新的空闲区使用回收区的地址
回收区位于两个空闲区中间
  • 将空闲区1、空闲区2和回收区合并
  • 新的空闲区使用空闲区1的地址
单独的回收区
  • 为回收区创建新的空闲节点
  • 插入到相应的空闲区链表中去

在快速变化的技术中寻找不变,才是一个技术人的核心竞争力。知行合一,理论结合实践