无用单元采集 垃圾回收机制
发布时间：2022-07-10 22:19:12 所属栏目：语言 来源：互联网
导读：通过前几节对可利用空间表进行动态存储管理的介绍，运行机制可以概括为：当用户发出申请空间的请求后，系统向用户分配内存；用户运行结束释放存储空间后，系统回收内存。这两部操作都是在用户给出明确的指令后，系统对存储空间进行有效地分配和回收。 但是
|
通过前几节对可利用空间表进行动态存储管理的介绍，运行机制可以概括为：当用户发出申请空间的请求后，系统向用户分配内存；用户运行结束释放存储空间后，系统回收内存。这两部操作都是在用户给出明确的指令后，系统对存储空间进行有效地分配和回收。 但是在实际使用过程中，有时会因为用户申请了空间，但是在使用完成后没有向系统发出释放的指令，导致存储空间既没有被使用也没有被回收，变为了无用单元或者会产生悬挂访问的问题。 什么是无用单元？简单来讲，无用单元是一块用户不再使用，但是系统无法回收的存储空间。例如在C语言中，用户可以通过 malloc 和 free 两个功能函数来动态申请和释放存储空间。当用户使用 malloc 申请的空间使用完成后，没有使用 free 函数进行释放，那么该空间就会成为无用单元。 悬挂访问也很好理解：假设使用 malloc 申请了一块存储空间，有多个指针同时指向这块空间，当其中一个指针完成使命后，私自将该存储空间使用 free 释放掉，导致其他指针处于悬空状态，如果释放掉的空间被再分配后，再通过之前的指针访问，就会造成错误。数据结构中称这种访问为悬挂访问。 在含有共享子表的广义表中，也可能会产生无用单元。例如图 1 中，L1、L2 和 L3 分别为三个广义表的表头指针，L4 为 L1 和 L2 所共享，L3 是 L2 的子表，L5 为 L1、L2 和 L3 三个广义表所共享。 在图 1 的基础上，假设表 L1 不再使用，而 L2 和 L3 还在使用，若释放表 L1，L1 中的所有结点所占的存储空间都会被释放掉，L2 和 L3 中由于同样包含 L1 中的结点，两个表会被破坏，某些指针会产生悬挂访问的错误； 而如果 L1 表使用完成后不及时释放，L1 中独自占用的结点由于未被释放，系统也不会回收，就会成为无用单元。 解决存储空间可能成为无用单元或者产生悬挂访问的方法有两个： 每个申请的存储空间设置一个计数域，这个计数域记录的是指向该存储空间的指针数目，只有当计数域的值为 0 时，该存储空间才会被释放。 在程序运行时，所有的存储空间无论是处于使用还是空闲的状态，一律不回收，当系统中的可利用空间表为空时，将程序中断，对当前不在使用状态的存储空间一律回收，全部链接成一个新的可利用空间表后，程序继续执行。 第一种方法非常简单，下面主要介绍第二种方法的具体实现。 第二种方法中，在程序运行过程中很难找出此时哪些存储空间是空闲的。解决这个问题的办法是：找当前正在被占用的存储空间，只需要从当前正在工作的指针变量出发依次遍历，就可以找到当前正在被占用的存储空间，剩余的自然就是此时处于空闲状态的存储空间。 如果想使用第二种方式，可以分为两步进行： 对所有当前正在使用的存储空间加上被占用的标记（对于广义表来说，可以在每个结点结构的基础上，添加一个 mark 的标志域。在初始状态下，所有的存储空间全部标志为 0，被占用时标记为 1）； 依次遍历所有的存储空间，将所有标记为 0 的存储空间链接成一个新的可利用空间表。 对正在被占用的存储空间进行标记的方法有三种： 从当前正在工作的指针变量开始，采用递归算法依次将所有表中的存储结点中的标志域全部设置为 1； 第一种方法中使用递归算法实现的遍历。而递归底层使用的栈的存储结构，所以也可以直接使用栈的方式进行遍历； 以上两种方法都是使用栈结构来记录遍历时指针所走的路径，便于在后期可以沿原路返回。所以第三种方式就是使用其他的方法代替栈的作用。 递归和非递归方式在前面章节做过详细介绍，第三种实现方式中代替栈的方法是：添加三个指针，p 指针指向当前遍历的结点，t 指针永远指向 p 的父结点，q 指向 p 结点的表头或者表尾结点。在遍历过程遵循以下原则： 当 q 指针指向 p 的表头结点时，可能出现 3 种情况： p 结点的表头结点只是一个元素结点，没有表头或者表尾，这时只需要对该表头结点打上标记后即 q 指向 p 的表尾； p 结点的表头结点是空表或者是已经做过标记的子表，这时直接令 q 指针指向 p 结点的表尾即可； p 结点的表头是未添加标记的子表，这时就需要遍历子表，令 p 指向 q，q 指向 q 的表头结点。同时 t 指针相应地往下移动，但是在移动之前需要记录 t 指针的移动轨迹。记录的方法就是令 p 结点的 hp 域指向 t，同时设置 tag 值为 0。 当 q 指针指向 p 的表尾结点时，可能出现 2 种情况： p 指针的表尾是未加标记的子表，就需要遍历该子表，和之前的类似，令 p 指针和 t 指针做相应的移动，在移动之前记录 t 指针的移动路径，方法是：用 p 结点的 tp 域指向 t 结点，然后在 t 指向 p，p 指向 q。 p 指针的表尾如果是空表或者已经做过标记的结点，这时 p 结点和 t 结点都回退到上一个位置。 由于 t 结点的回退路径分别记录在结点的 hp 域或者 tp 域中，在回退时需要根据 tag 的值来判断：如果 tag 值为 0 ，t 结点通过指向自身 hp 域的结点进行回退；反之，t 结点通过指向其 tp 域的结点进行回退。 由于 p 指针指向的 e 结点的表尾结点为空，所以 p 指针和 t 指针都回退。由于 p 指针指向的结点 b 的 tag 值为 1，表明表尾已经遍历完成，所以 t 指针和 p 指针继续上移，最终遍历完成。 总结 无用单元的收集可以采用以上 3 中算法中任何一种。无论使用哪种算法，无用单元收集本身都是很费时间的，所以无用单元的收集不适用于实时处理的情况中使用。 （编辑：云计算网_泰州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330476号