一、什么是垃圾回收
在计算机程序运行过程中，我们的程序会不断地申请内存、使用内存和释放内存，但有些时候，我们无法确定什么时候释放内存，导致内存泄露问题。为了解决这一问题，垃圾回收机制应运而生。
垃圾回收机制是一种自动化管理内存的机制，其主要作用是通过监控内存的使用情况、识别不再使用的内存和释放内存，使我们的程序更加高效和可靠。
二、常见的垃圾回收算法
垃圾回收算法是垃圾回收机制的核心。常见的垃圾回收算法有三种：
1.引用计数算法
引用计数算法是一种最简单的垃圾回收算法，其原理是通过维护每个对象的引用计数，当对象引用计数为零时，就将其释放。
class Object {
public:
Object() : mRefCount(0) {}
virtual ~Object() {}
void addRef() {
mRefCount++;
}
void release() {
mRefCount--;
if (mRefCount <= 0) {
delete this;
}
}
private:
int mRefCount;
};
引用计数算法的优点是实现简单、实时回收；但其缺点是不能解决循环引用的问题，且增加引用计数和减少引用计数会增加额外的开销。
2.标记清除算法
标记清除算法是一种基于“可达性分析”（Reachability Analysis）的垃圾回收算法。其流程如下：
从根节点开始遍历所有对象，标记所有可达对象（即不能被回收的对象），未标记的对象即为可回收对象，进行清除。如果对象存在循环引用，则标记算法无法识别出可回收对象，即存在内存泄露问题。
void mark(Object* object) {
if (!object || object->mMarked) {
return;
}
object->mMarked = true;
for (auto it = object->mReferences.begin(); it != object->mReferences.end(); ++it) {
mark(*it);
}
}
void sweep() {
for (auto it = Object::sObjects.begin(); it != Object::sObjects.end(); ++it) {
if (!(*it)->mMarked) {
delete *it;
*it = nullptr;
} else {
(*it)->mMarked = false;
}
}
}
void gc() {
for (auto it = Object::sRoots.begin(); it != Object::sRoots.end(); ++it) {
mark(*it);
}
sweep();
}
3.复制算法
复制算法是一种基于“分代假设”（Generational Hypothesis）的垃圾回收算法。其流程如下：
将内存分为两个区域，一个为“From Space”，一个为“To Space”。程序在From Space分配内存，并在使用完之后，将不再使用的对象拷贝到To Space。当To Space已经存储了足够多的对象时，执行“数代推进”（generational promotion），即将To Space中的所有对象移动到From Space中。该算法能够解决循环引用的问题，效率也相对较高，但同时需要使用更多的内存。
void gc() {
Object* fromSpace = currentHeap->getFromSpace();
Object* toSpace = currentHeap->getToSpace();
Object* p = nullptr;
for (auto it = Object::sRoots.begin(); it != Object::sRoots.end(); ++it) {
copy(&p, (*it));
*it = p;
}
while (fromSpace getAllocPtr()) {
Object* object = reinterpret_cast<Object*>(fromSpace);
fromSpace += object->getSize();
copy(&p, object);
object = p;
}
std::swap(fromSpace, toSpace);
currentHeap->setAllocPtr(fromSpace);
}
三、如何选择合适的垃圾回收算法
不同的垃圾回收算法适用于不同的场景。我们需要根据自己的需求来选择合适的算法。
引用计数算法适用于单线程环境下的小对象，但不能解决循环引用的问题；标记清除算法适用于多线程环境下和连续分配内存的场景下，但容易出现内存碎片问题；复制算法适用于多线程环境下和存在大量不活跃（常驻内存中）对象的场景下，在其他场景下可能会浪费内存。
四、垃圾回收相关的实践
垃圾回收机制在现代编程语言中得到了广泛的应用。例如，Java和C#都采用了垃圾回收机制，Python、Ruby等脚本语言也采用了此类机制。下面是一个基于C++11的垃圾回收框架：
#include <iostream>
#include <list>
class Object {
public:
static std::list<Object*> sObjects;
static std::list<Object*> sRoots;
Object() {
sObjects.push_back(this);
}
virtual ~Object() {}
void* operator new(size_t size) {
void* p = malloc(size);
currentHeap->setAllocPtr(static_cast<char*>(p) + size);
return p;
}
void* operator new[](size_t size) {
void* p = malloc(size);
currentHeap->setAllocPtr(static_cast<char*>(p) + size);
return p;
}
void operator delete(void* p) {
if (!currentHeap->contains(p)) {
free(p);
}
}
void operator delete[](void* p) {
if (!currentHeap->contains(p)) {
free(p);
}
}
virtual int getSize() = 0;
static void setHeap(void* start, void* end) {
currentHeap = new Heap(start, end);
}
private:
static class Heap* currentHeap;
};
std::list<Object*> Object::sObjects;
std::list<Object*> Object::sRoots;
class Heap* Object::currentHeap = nullptr;
class Heap {
public:
Heap(void* start, void* end) : mStart(start), mEnd(end), mAllocPtr(start) {}
bool contains(void* p) {
return p >= mStart && p mEnd - highWaterMark) {
gc();
}
}
void* getAllocPtr() const {
return mAllocPtr;
}
Object* getFromSpace() {
return reinterpret_cast<Object*>(mStart);
}
Object* getToSpace() {
return reinterpret_cast<Object*>(mEnd - highWaterMark);
}
private:
void gc() {
std::cout << "Start GC...\n";
Object** oldRoots = new Object*[Object::sRoots.size()];
int pos = 0;
for (auto it = Object::sRoots.begin(); it != Object::sRoots.end(); ++it) {
oldRoots[pos++] = *it;
}
for (int i = 0; i < pos; ++i) {
mark(oldRoots[i]);
}
sweep();
currentHeap->setAllocPtr(currentHeap->getToSpace());
delete[] oldRoots;
std::cout << "End GC...\n";
}
void mark(Object* obj) {
if (!obj || obj->mMarked) {
return;
}
obj->mMarked = true;
for (auto it = obj->mReferences.begin(); it != obj->mReferences.end(); ++it) {
mark(*it);
}
}
void sweep() {
for (auto it = Object::sObjects.begin(); it != Object::sObjects.end(); ) {
if (!(*it)->mMarked) {
delete *it;
*it = nullptr;
it = Object::sObjects.erase(it);
} else {
(*it)->mMarked = false;
++it;
}
}
}
void* mStart;
void* mEnd;
void* mAllocPtr;
static const int highWaterMark = 2048;
};
class String : public Object {
public:
static String* create(const char* str) {
String* p = new String();
p->mLength = strlen(str);
p->mData = new char[p->mLength + 1];
strncpy(p->mData, str, p->mLength + 1);
return p;
}
~String() {
delete[] mData;
}
int getSize() override {
return sizeof(String) + mLength + 1;
}
void addRef() {
Object::addRef();
std::cout << "Add reference...refCount=" << mRefCount << "\n";
}
void release() {
Object::release();
std::cout << "Release reference...refCount=" << mRefCount << "\n";
}
private:
String() : mData(nullptr), mLength(0) {
Object::sRoots.push_back(this);
}
char* mData;
int mLength;
};
int main() {
Object::setHeap(malloc(1024), static_cast<char*>(malloc(1024)) + 1024);
String* str1 = String::create("hello, world!");
String* str2 = String::create("hello, AI!");
str1->addRef();
str1->addRef();
str1->release();
Object::sRoots.clear();
Object::sRoots.push_back(str2);
gc();
free(Object::sObjects.front()); // free heap allocated by `malloc`
Object::sObjects.pop_front();
free(Object::sRoots.front()); // free heap allocated by `malloc`
Object::sRoots.pop_front();
free(Object::currentHeap);
return 0;
}
该垃圾回收框架支持自动、实时、引用循环等情况下的内存回收。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/286433.html
微信扫一扫 
支付宝扫一扫 