一、什麼是垃圾回收
在計算機程序運行過程中，我們的程序會不斷地申請內存、使用內存和釋放內存，但有些時候，我們無法確定什麼時候釋放內存，導致內存泄露問題。為了解決這一問題，垃圾回收機制應運而生。
垃圾回收機制是一種自動化管理內存的機制，其主要作用是通過監控內存的使用情況、識別不再使用的內存和釋放內存，使我們的程序更加高效和可靠。
二、常見的垃圾回收算法
垃圾回收算法是垃圾回收機制的核心。常見的垃圾回收算法有三種：
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/zh-hk/n/286433.html
微信掃一掃 
支付寶掃一掃 