📄 9_2_2 用户层垃圾回收算法的实现 - 《多任务下的数据结构与算法》 - 免费试读 - book_csdn_net.htm
字号:
&operator*() { return *m_pAddr</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">}</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> T
*operator->() { return m_pAddr</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">}</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> T *operator=(T
*t) { m_pAddr = t</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">}</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> GCPtr &
operator=(GCPtr &r) { m_pAddr = r.m_pAddr</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">}</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="MARGIN-BOTTOM: 8pt; LINE-HEIGHT: 14pt"><SPAN
lang=EN-US style="FONT-SIZE: 9pt">}</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal><SPAN style="FONT-FAMILY: 华康简宋">在通过如下方式定义一个对象</SPAN><SPAN
lang=EN-US>p</SPAN><SPAN style="FONT-FAMILY: 华康简宋">时</SPAN><SPAN
style="FONT-FAMILY: 宋体">：</SPAN></P>
<P class=MsoNormal style="MARGIN: 8pt 0cm; LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">GCPtr<int> p</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal><SPAN style="FONT-FAMILY: 华康简宋">可以将对象</SPAN><SPAN
lang=EN-US>p</SPAN><SPAN style="FONT-FAMILY: 华康简宋">如</SPAN><SPAN
lang=EN-US>int</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">类型指针一样来使用，实际的操作都是通过重载运算符来操作</SPAN><SPAN
lang=EN-US>GCPtr</SPAN><SPAN style="FONT-FAMILY: 华康简宋">类里面的</SPAN><SPAN
lang=EN-US>pAddr</SPAN><SPAN style="FONT-FAMILY: 华康简宋">成员实现的。</SPAN></P>
<P class=MsoNormal><SPAN style="FONT-FAMILY: 华康简宋">有了模拟指针，就可以通过类</SPAN><SPAN
lang=EN-US>GCPtr</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">来定义任意类型的指针。只要在</SPAN><SPAN
lang=EN-US>GCPtr</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">的构造函数和析构函数里进行引用计数的增减，就可以实现引用计数方法的垃圾回收了。</SPAN></P>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 华康简宋">也许有些读者认为可以直接在析构函数里将指针指向的内存释放，但这个想法是在只有这一个指针指向释放的内存的情况下才可行，如果有其他指针指向同一块内存，并且其他指针的生存期更长，就会出现程序运行异常，下面可以看一段简单的程序。</SPAN></P>
<P class=4><SPAN lang=EN-US>GCPtr<int> p</SPAN><SPAN
style="FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">p = new int</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> { </SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> GCPtr
q</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> q =
p</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> }</SPAN></P>
<P class=MsoNormal style="MARGIN-BOTTOM: 8pt; LINE-HEIGHT: 14pt"><SPAN
lang=EN-US style="FONT-SIZE: 9pt">*p = 100</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">以上这段程序中</SPAN><SPAN lang=EN-US>p</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">和</SPAN><SPAN lang=EN-US>q</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">指向的是同一块内存，如果在析构函数中直接将内存释放，那么“</SPAN><SPAN
lang=EN-US>*p=100</SPAN><SPAN style="FONT-FAMILY: 宋体">；</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">”这条语句将出现异常，所以不能简单地将一块内存释放掉，必须确认没有指针指向它时才可以释放。因此必须给内存加上引用计数，有多少个指针指向它，计数就为多少，如果引用计数为</SPAN><SPAN
lang=EN-US>0</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">就表示没有指针指向它，这时才可以将内存释放掉。</SPAN></P>
<H4 style="MARGIN-LEFT: 0cm; LINE-HEIGHT: 16.3pt"><SPAN lang=EN-US>3.
</SPAN><SPAN style="FONT-FAMILY: 黑体">引用计数的实现</SPAN></H4>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">上面实现了一个模拟指针的功能，要将模拟指针变成一个具有引用计数功能的模拟指针，首要问题就是要为每块分配的内存找一个保存引用计数的地方。</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">可不可以在</SPAN><SPAN lang=EN-US>GCPtr</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">类里面直接定义一个变量来保存引用计数呢？答案是否定的。因为指针和内存并不是一一对应的关系，而是可能有多个指针指向同一块内存。引用计数必须和分配的内存一一对应，如果</SPAN><SPAN
lang=EN-US>GCPtr</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">类里面直接定义一个变量来保存引用计数的话，当另外一个</SPAN><SPAN
lang=EN-US>GCPtr</SPAN><SPAN style="FONT-FAMILY: 华康简宋">对象指向一个已有</SPAN><SPAN
lang=EN-US>GCPtr</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">对象指向的内存时，如何去增加引用计数？这显然是无法实现的，所以必须设计一个和分配内存一一对应的保存引用计数的地方。</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">首先想到的就是设计一张表来保存分配的内存地址及对应的引用计数，重点是考虑在操作引用计数时，如何快速通过分配的内存地址定位到对应的引用计数变量。</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">这时也许有人会想到用一个哈希表之类的能够快速查找的数据结构来保存内存地址和引用计数，还有没有更快的方法呢？</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">更快的方法就是通过内存地址直接就可以访问引用计数，这就要求引用计数保存在和分配的内存连续的空间上。但问题又来了，系统提供的内存管理算法并没有留下可以保留引用计数的位置，要实现这样的功能就必须写一个自己的内存管理算法。</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">由于是在应用程序层，写一个内存管理算法实际上还是需要先向操作系统申请一大块内存，然后使用自己的内存管理算法来管理这块内存，问题是如何知道需要向操作系统申请多少内存呢？也许目前需要</SPAN><SPAN
lang=EN-US>1</SPAN><SPAN style="FONT-FAMILY: 华康简宋">兆内存，但下个版本也许又需要</SPAN><SPAN
lang=EN-US>2</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">兆内存，总之内存的需求是变化无常的，使用自己的内存管理算法在实际应用中必然存在浪费的情况，所以这种方法实现起来不能令人满意。</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">难道又退回到用哈希表吗？用哈希表在每次指针赋值时，增加引用计数需要进行哈希表的查找，对一个赋值语句来说，开销实在太大了，自己写内存管理算法也行不通，所以还是想想有没有别的方法吧。那么，可不可以继承系统的内存管理算法呢？</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 16.3pt"><SPAN
style="FONT-FAMILY: 华康简宋">由于系统的内存管理没有在管理上给分配的内存预留引用计数位置，但可以在分配给用户使用的内存上自己预留引用计数的空间。比如在</SPAN><SPAN
lang=EN-US>32</SPAN><SPAN style="FONT-FAMILY: 华康简宋">位系统上，要想分配一个</SPAN><SPAN
lang=EN-US style="LETTER-SPACING: 0pt">128 B</SPAN><SPAN
style="FONT-FAMILY: 华康简宋; LETTER-SPACING: 0pt">的内存块，那就应该分配一个</SPAN><SPAN
lang=EN-US style="LETTER-SPACING: 0pt">132 B</SPAN><SPAN
style="FONT-FAMILY: 华康简宋; LETTER-SPACING: 0pt">的内存块，将内存块前面</SPAN><SPAN
lang=EN-US style="LETTER-SPACING: 0pt">4</SPAN><SPAN
style="FONT-FAMILY: 华康简宋; LETTER-SPACING: 0pt">个字节留作引用计数，将第</SPAN><SPAN
lang=EN-US style="LETTER-SPACING: 0pt">4</SPAN><SPAN
style="FONT-FAMILY: 华康简宋; LETTER-SPACING: 0pt">个字节后的空间返回给程序使用。这样当需要通过内存地址来操作引</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">用计数时，直接就可以将指针地址向后移</SPAN><SPAN
lang=EN-US>4</SPAN><SPAN style="FONT-FAMILY: 华康简宋">个字节，然后在这</SPAN><SPAN
lang=EN-US>4</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">个字节上写引用计数就可以了，这样就可以设计一个用户的内存管理函数如下。</SPAN></P>
<P class=4><SPAN lang=EN-US>#define INT_LEN 4</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><STRONG><SPAN lang=EN-US
style="FONT-SIZE: 9pt">void *GC_Malloc(size_t size)</SPAN></STRONG></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">{</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> void *p =
malloc( size + INT_LEN )</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> if ( p != NULL
)</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">{</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
return (void *)((char *)p+INT_LEN)</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> }</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> return
NULL</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="MARGIN-BOTTOM: 8pt; LINE-HEIGHT: 14pt"><SPAN
lang=EN-US style="FONT-SIZE: 9pt">}</SPAN></P>
<P class=MsoNormal><SPAN style="FONT-FAMILY: 华康简宋">当然还要设计一个对应的释放函数如下。</SPAN></P>
<P class=4><STRONG><SPAN lang=EN-US>void GC_Free(void *p)</SPAN></STRONG></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">{</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">void *pFree = (void *)((char *)p – INT_LEN)</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 14pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">free(pFree)</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="MARGIN-BOTTOM: 8pt; LINE-HEIGHT: 14pt"><SPAN
lang=EN-US style="FONT-SIZE: 9pt">}</SPAN></P>
<P class=MsoNormal><SPAN style="FONT-FAMILY: 华康简宋">使用了垃圾回收算法后，</SPAN><SPAN
lang=EN-US>GC_Free( )</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">一般只由垃圾回收算法来调用，用户就不需要调用</SPAN><SPAN lang=EN-US>GC_Free(
)</SPAN><SPAN style="FONT-FAMILY: 华康简宋">了，也不需要花费时间去关心内存释放的问题了。</SPAN></P>
<P class=MsoNormal><SPAN style="FONT-FAMILY: 华康简宋">下面给出使用</SPAN><SPAN
lang=EN-US>GCPtr</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">类管理引用计数的一个初步编码实现。</SPAN></P>
<P class=4 style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US>/* </SPAN><SPAN
style="FONT-FAMILY: 华康简宋">支持垃圾内存回收的</SPAN><SPAN lang=EN-US>GCPtr</SPAN><SPAN
style="FONT-FAMILY: 华康简宋">类，使用模板实现</SPAN><SPAN lang=EN-US> */</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">template <class T> class</SPAN><STRONG><SPAN
lang=EN-US style="FONT-SIZE: 9pt"> GCPtr {</SPAN></STRONG></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">public</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">：</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt"> T
*m_pAddr</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN><SPAN
lang=EN-US style="FONT-SIZE: 9pt"> /* </SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">用来记住定义的指针地址便于析构函数使用</SPAN><SPAN
lang=EN-US style="FONT-SIZE: 9pt"> */</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">public</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">：</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
</SPAN><STRONG><SPAN lang=EN-US style="FONT-SIZE: 9pt">GCPtr(T *t = NULL)
</SPAN></STRONG></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><STRONG><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
</SPAN></STRONG><SPAN lang=EN-US style="FONT-SIZE: 9pt">{</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
m_pAddr = t</SPAN><SPAN style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US
style="FONT-SIZE: 9pt">
INT *p = (INT *)m_pAddr</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 华康简宋">－</SPAN><SPAN lang=EN-US
style="FONT-SIZE: 9pt">1</SPAN><SPAN
style="FONT-SIZE: 9pt; FONT-FAMILY: 宋体">；</SPAN></P>
<P class=MsoNormal style="LINE-HEIGHT: 13.8pt"><SPAN lang=EN-US
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -