当前位置： 首页 > article >正文

4_高并发内存池项目_高并发池内存释放设计_ThreadCache/CentralCache/PageCache回收并释放内存

article 2025/1/24 16:33:27

高并发池内存释放设计

对各缓存层释放内存的设计，不仅仅是从上一层回收内存，还包括对回收回来的内存怎样处理更有利于下一缓存层的回收，提高效率。

高并发内存池内存释放步骤：

线程对象释放内存

↓↓↓↓↓
ThreadCache(1.回收线程释放的内存，2.将多余内存整理归还CentralCache)

↓↓↓↓↓
CentralCache(1.回收ThreadCache释放的内存，2.将多余Span归还给PageCache)

↓↓↓↓↓
PageCache(1.回收CentralCache释放的Span，2.合并，3.并且将内存归还操作系统)

ThreadCache回收内存的标准：

  1. ThreadCache回收线程释放的内存。
    从上一层，也就是申请内存的对象释放内存时，将被释放的内存进行回收，也就是将空闲的内存块回收，挂在每个对应的哈希桶中。
  2. ThreadCache释放内存给CentralCache回收。
    当某个哈希桶中的自由链表存储的内存到达什么程度时，将其整理回收给CentralCache？
  • tcmalloc考虑了两个方向，一个是链表的长度，一个是内存的大小(比如一个ThreadCache超过2MB或者多少就回收)。
  • 我们这里只考虑链表的长度，链表的长度超过了它一次向CentralCache申请的批量对象个数时，将这个哈希桶中批量数量的内存还给CentralCache。
  • 首先，我们要比较一下链表长度（_freelists[index].Size() > _freelists[index].MaxSize()），长度超过时，我们找到要还给CentralCache的一段内存，由start，end，size（当时批量的数量），我们要将这段被释放的内存还给CentralCache。这里要调用CentralCache回收ThreadCache释放的内存的函数。

CentralCache回收释放内存：

1.从ThreadCache中回收内存，根据对应的单个内存大小，计算出对应的哈希桶，将它们放在哈希桶中对应的Span下。如何得到内存块对应的Span？

2.空闲的Span被PageCache回收，回收的标准是什么？

PageCache回收释放内存：

  1. PageCache如何处理从CentralCache中回收的Span？
  2. PageCache释放内存到操作系统。
// 封装线程释放内存
static void concurrentFree(void* obj)
{
	// 现在通过对应的指针找到对应的Span，通过Span找到对应的size也就是申请的内存大小
	Span* span = PageCache::GetInstance().MapObjectToSpan(obj);
	size_t size = span->_objSize;

	if (size > MAX_BYTES)
	{
		// 访问PageCache中的ReleaseSpanToPageCache
		PageCache::GetInstance()._pageMtx.lock();
		PageCache::GetInstance().ReleaseSpanToPageCache(span);
		PageCache::GetInstance()._pageMtx.unlock();
	}
	else
	{
		assert(pTLSThreadCache);
		// 回收内存对象释放的内存
		pTLSThreadCache->ThreadFree(obj, size);
	}
}

/* 系统申请释放内存 */
#ifdef _WIN64  
#include <Windows.h>  
#elif defined(_WIN32) && !defined(_WIN64)  
 /* 检查是否定义了 _WIN32 宏但没有定义 _WIN64 宏，
  * 这适用于32位Windows系统。
  * 如果条件满足，也包含 <Windows.h> 头文件。
  */
#include <Windows.h>  
#else  
#error "Unsupported platform"  //#else 和 #error 指令用于捕获不支持的平台，并在编译时生成错误。
#endif 

// 直接去堆上申请按页申请空间
/* 在Windows下，可以调用VirtualAlloc函数；在Linux下，可以调用brk或mmap函数
 * 使用条件编译，根据不同的平台选择不同的头文件
 * _WIN32 宏在32位和64位Windows上都定义，
 * 因此单独检查 _WIN32 而不排除 _WIN64 ，会导致在64位Windows上也执行32位分支的代码
 * 或者 不判断定义64位，将_WIN64放在_WIN32前也可以
 */
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN64
	void* ptr = VirtualAlloc(0, kpage * (1 << 13), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

#elif  _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << 13), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// 由于前面的#error，这行代码实际上不会执行  
	// 但为了保持函数完整性，这里保留了返回NULL的语句  
	return NULL;
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN64
	VirtualFree(ptr, 0, MEM_RELEASE);
#elif	_WIN32
		VirtualFree(ptr, 0, MEM_RELEASE);
#endif
}

一、ThreadCache–回收释放内存

/* ThreadCache.h */
#pragma once
#include "CommonPool.h"

class ThreadCache
{
private:
    FreeList _freeLists[NFREELISTS];// 哈希桶

public:
    // 需要提供两个接口  一个是申请对象空间，一个是释放对象空间
    // 申请内存对象
    void* ThreadAlloc(size_t size);
    
    // 释放内存对象
    void ThreadFree(void* obj, size_t size);

    // 链表过长时，回收内存回到中心缓存
    // 回收一段长度为size的链表回到中心缓存
    void ListTooLong(FreeList& list, size_t size);
    
    // 从Cental Cache中申请缓存
    void* FetchFromCentralCache(size_t index, size_t alignSize);
};

// TLS thread local storage（线程局部存储、线程本地存储）
static _declspec(thread) ThreadCache* pTLSThreadCache = nullptr;
// thread 用于声明一个线程本地变量， 
// _declspec(thread)的前缀是Microsoft添加给Visual C++编译器的一个修改符。

怎么判断什么时候把内存还给CentralCache？还多少内存？

当释放某个线程申请的对象内存时，ThreadCache将该对象插入到对应哈希桶的自由链表当中。

但随着线程不断的释放，对应自由链表的长度也会越来越长，此时我们应该将内存还给CentralCache，避免内存堆积造成的浪费。回收一部分内存对象到CentralCache

tcmalloc考虑了两个方面：一个是链表的长度，一个是内存的大小。

这里我们只考虑链表的长度。

如果ThreadCache某个桶当中自由链表的长度超过它一次向CentralCache批量申请的对象个数时，就要把该自由链表当中的这些对象还给CentralCache。

接着完善_freeList的结构，我们需要获得对应哈希桶中自由链表的长度，以及在回收这些内存时的操作函数，删除某段链表中的一部分。

关于_freeLists[index].Size()中的变量_size在哪些位置发生变化？

_freeLists[index].Size()是ThreadCache的哈希桶中申请到的链表长度，也就是向CentralCache申请释放内存块后发生变化。

class FreeList
{
public:
	// 线程申请内存就是从对应的自由链表中取出内存块（头删）
	void Push(void* obj)
	{
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}

	// 线程释放内存就是将内存块释放到对应的自由链表中（头插）
	void* Pop()
	{
		assert(_freeList);// 自由链表为空时，无法取出空闲内存块
		void* obj = _freeList;
		_freeList = NextObj(_freeList);
		--_size;
		return obj;
	}

	// 判断自由链表中是否存在内存
	bool Empty()
	{
		return _freeList == nullptr;
	}

	// 获取到_MaxSize成员变量
	size_t& MaxSize()
	{
		return _MaxSize;
	}
	size_t Size()
	{
		return _size;
	}

	// 插入一定范围的内存块
	void PushRange(void* start, void* end, size_t num)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += num;
	}

	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);

		start = _freeList;
		end = start;
		for (size_t i = 0; i < n; ++i)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

private:
	void* _freeList = nullptr;
	//在FreeList结构中增加一个叫做_MaxSize的成员变量，用于慢开始反馈调节
	size_t _MaxSize = 1;
	size_t _size = 0;
};

/* ThreadCache.cpp */

// 释放对象时，链表长度过长，回收内存到中心缓存（central cache)
void ThreadCache::ListTooLong(FreeList& list, size_t size)
{
	// 拿一个批量的，不是全部
	// _freeLists[index].Size() > _freeLists[index].MaxSize()

	void* start = nullptr;
	void* end = nullptr;

	// 还给对应的central cache 中的哈希桶
	list.PopRange(start, end, list.MaxSize());		// 输出型参数

    //调用central cache回收thread cache释放的内存的函数
    CentralCache::GetInstance().ReleaseListToSpans(start, list.MaxSize());	
}

void ThreadCache::ThreadFree(void* obj, size_t size)
{
	// 释放的内存 挂回 _freeList 链表中
	assert(obj);// 首先确保释放的对象存在
	assert(size <= MAX_BYTES);

	// 内存挂回；链表中
	size_t index = SizeClass::Index(size);
	_freeLists[index].Push(obj);

	/* 如果Thread Cache某个桶当中自由链表的长度超过
	它一次批量向central cache申请的对象个数，
	那么此时我们就要把该自由链表当中的这些对象还给central cache。 */
	if (_freeLists[index].Size() > _freeLists[index].MaxSize())
	{
		ListTooLong(_freeLists[index], size);
	}
}

二、CentralCache–回收释放内存

大体思路：

  1. CentralCache释放内存有两个大方向，一个是从ThreadCache中回收内存块，一个是回收后的内存块使得部分Span处于完全空闲状态，可以释放给PageCache，增加空间利用；
  2. 回收从ThreadCache中释放的内存：当ThreadCache中某一自由链表下悬挂的空闲内存块过多时由CentralCache进行回收RealseListToSpans()，这些内存块回收到对应哈希桶中的对应的Span中。因此在分割Span为多个内存块时就可以将内存块的页号与Span做映射关系，确保回收的内存块可以找到对应的Span。
  3. 将完全空闲的Span释放给PageCache：通过_usecount这个变量来判断Span是否是空闲的，确认空闲后，就释放给PageCache。

（一）创建页号与Span之间的额映射关系

通过对应的哈希桶和span。将对应的释放内存对象挂在对应的哈希桶下的span中。

我们可以通过内存块的起始位置获得是Span的第几页。起始地址>>13（8kb）得到_pageid，然后遍历spanlist，但是这个方法显然过于复杂。

( 注意这里 画的图只是为了好理解，直观看到联系。实质上，内存的申请不是真正的划分内存空间和移动内存位置，它的地址和位置是不会改变的，我们的还回也就是找到对应的地址，再把它们连接起来 )

我们要还到对应的span下。那么可以创建页号(_pageId)与Span的映射关系，页号(_pageId)可以计算出Span的起始地址，通过这个页号和页数，我们可以找到Span中每一页的位置，也就是可以定位到 切分的内存对象所处在哪个Span的哪个页中：

**unordered_map_pageId + i , Span>**建立起联系。

在创建Span时就通过映射关系，将页号与Span映射起来。而创建Span的过程中是在PageCache中，
这个映射关系设置为 ：

class PageCache
{
private:
	SpanList spanPageLists[NPAGES]; // 0号桶不使用，其他一一对应。
	std::unordered_map<PageID, Span*> _idSpanMap;


private:
	// 静态私有成员变量
	static PageCache _instance;

	// 私有构造函数
	PageCache(){}
	PageCache(const PageCache&) = delete;
	PageCache& operator=(const PageCache&) = delete;

public:
	// 加锁
	std::mutex _pageMtx;

	// 公有静态访问方法
	static PageCache& GetInstance()
	{
		return _instance;
	}

	// 申请一个新的Span
	Span* NewSpan(size_t k);
};

我们可以把这个映射关系设置在PageCache中，在创建一个Span时，通过它的页数，将Span中的每一页与Span创建上联系。

// 访问PageCache时记得加锁
Span* PageCache::NewSpan(size_t k)
{
	// PageCache对应哈希桶中的Span是否存在
	if (!spanPageLists[k].Empty())
	{
		Span* kSpan =  spanPageLists[k].PopFront();
		for (PageID i = 0; i < kSpan->_n; ++i)
		{
			_idSpanMap[kSpan->_pageId + i] = kSpan;
		}
		return kSpan;

	}
	else
	{
		// 往上找大页，切割
		for (size_t i = k + 1; i < NPAGES; ++i)
		{
			if(!spanPageLists[i].Empty())
			{ 
				// 不为空，切割
				Span* kSpan = new Span;
				Span* nSpan = spanPageLists[i].PopFront();

				kSpan->_pageId = nSpan->_pageId;
				kSpan->_n = k;

				nSpan->_n -= k;
				nSpan->_pageId += k;

				for (PageID i = 0; i < kSpan->_n; ++i)
				{
					_idSpanMap[kSpan->_pageId + i] = kSpan;
				}

				spanPageLists[nSpan->_n].PushFront(nSpan);
				return kSpan;
			}
		}

		// 没有大页，就向系统申请
		Span* bigSpan = new Span;
		void* ptr = SystemAlloc(NPAGES-1);

		bigSpan->_pageId =(PageID) ptr >> PAGE_SHIFT;
		bigSpan->_n = NPAGES - 1;

		spanPageLists[bigSpan->_n].PushFront(bigSpan);
		return NewSpan(k);
	}
}

此时此刻我们将CentralCache会申请到的Span与其页数创建了映射关系。

（二）通过创建的映射关系将内存块释放回对应的Span

建立_pageId与Span的映射，方便CentralCache回收小块内存时，查找对应的Span。

通过创建的页号与Span的映射关系找到对应的Span

在PageCache类中添加一个函数接口MapObjectToSpan(obj)，通过对象的地址找到该对象对应的Span了，直接将该对象的地址除以页的大小得到页号，然后在unordered_map当中找到其对应的Span，让CentralCache获取这里的映射关系。

我们有指向该对象的指针，也就是可以得到了它的地址，通过这份地址，我们可以求出该对象的页号：

 PageID id = (PageID)obj >> PAGE_SHIFT;

通过映射关系得到它属于哪个Span：

**auto ret = _idSpanMap.find(id);**

每个Span含有页号范围都是不一样的，无需担心出错。这个Span的页号范围(比如：[n~n+5])。

通过查到对象的页号，在映射关系中指向哪个Span。

因为这个对象是通过Span申请出来的，所以一定能通过页号找到对应的Span。

/* Pagecache.cpp */
// 获取从对象到span的映射
// 页号和span的映射
// std::unordered_map<PageID, Span*> _idSpanMap;
Span* PageCache::MapObjectToSpan(void* obj)
{
	// 页号和span的映射
	PageID id = (PageID)obj >> PAGE_SHIFT; // 通过对象的地址得到页号

    // 找到使用_idSpanMap.find(id);在映射表中查找该页号对应的Span对象。
    // 是一定能找到的，不然我们的代码是有问题的
	auto ret = _idSpanMap.find(id);		  

    // 如果找到了（即ret != _idSpanMap.end()），则返回该Span对象的指针。
	if (ret != _idSpanMap.end())  
	{
		return ret->second;
	}
	else
	{
		assert(false);
		return nullptr;
	}
}

搞清楚了上面的部分，现在我们要开始回收ThreadCache中过长的链表了。

（三）回收ThreadCache中过长的链表

现在我们可以得到对象属于哪个Span了。

回收内存对象，要做的就是将这块内存对象头插进入对应的Span中。

/* central cache.cpp */

// CentralCache回收ThreadCache释放的内存
void CentralCache::RealseListToSpans(void* start, size_t size)
{
	size_t index = SizeClass::Index(size);
	// 加锁
	_spanLists[index]._mtx.lock();

	// 释放的内存对象 不一定是 一个Span的
	while (start)
	{
		// 通过对象获取到它是哪个span MapObjectToSpan
		void* next = NextObj(start);
		Span* span = PageCache::GetInstance().MapObjectToSpan(start);
		NextObj(start) = span->_list;
		span->_list = start;

		start = next;
	}

	// 解锁
	_spanLists[index]._mtx.unlock();
}

（四）CentralCache释放内存

接下来我们要考虑的是如何判断CentralCache什么时候释放内存？

在框架设计以及前面的大体思路处我们都提到了一个变量：

// 这时候就有我们在创建Span时出现的 一个变量
// Span中被利用的内存块数
    size_t _usecount = 0;	  
// 切好的小块内存被使用的使用计数，==0 说明所有对象都回来了

我们可以用 _usecount来判断spanlist中的某个Span是否是空闲的、未被申请内存的，如果是，可以释放给PageCache。

我们现在看看哪些位置的操作会影响到这个变量，在代码中对这个变量进行操作比如++，–。（这个变量在ThreadCache申请和释放内存时会发生变化，因此我们需要完善这部分相关的内容）

// ThreadCache从CentralCache中获取内存块
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t  size)
{
	// 获取一个非空Span
	size_t index = ClassSize::Index(size);

	// 从现在开始访问CentralCache的哈希桶，需要开始加锁进入
	_spanLists[index]._mtx.lock();

	Span* span = CentralCache::GetOneSpan(_spanLists[index],size);
	assert(span);
	assert(span->_list);

	start = span->_list;
	end = start;

	// 设置一个变量n，和一个实际可申请对象数量的变量actualNum，以及别忘了batchNum
	size_t n = 0, actualNum = 1;
	while (n < batchNum - 1 && NextObj(end) != nullptr)
	{
		end = NextObj(end);
		++n;
		++actualNum;
	}

	// 把切割掉内存后的内存对象连接上,被切割下的内存尾端指向nullptr
	span->_list = NextObj(end);
	NextObj(end) = nullptr;
	span->_usecount += actualNum;

	_spanLists[index]._mtx.unlock();
	return actualNum;
}

// CentralCache回收ThreadCache释放的内存
void CentralCache::ReleaseListToSpans(void* start, size_t size)
{
	size_t index = SizeClass::Index(size);
	// 加锁
	_spanLists[index]._mtx.lock();

	// 释放的内存对象 不一定是 一个span的 
	while (start)
	{
		// 通过对象获取到它是哪个Span --MapObjectToSpan
		void* next = NextObj(start);
		Span* span = PageCache::GetInstance().MapObjectToSpan(start);
		NextObj(start) = span->_list;
		span->_list = start;
        span->_usecount--;

		// 从thread cache回收的内存已经回到了Span中。
    	// 判断这个Span是否空闲，如果空闲，将这个Span归还给PageCache
		// 这时候就需要用到 _usecount 这个变量，判断Span中没有被利用，被申请掉的内存
		if (span->_usecount == 0)
		{
			// 将这个要归还的span从链表中取出,删除
			// 保持链表的连续性
			_spanLists->Erase(span);
            span->list = nullptr;
			span->_next = nullptr;
			span->_prev = nullptr;

			PageCache::GetInstance().ReleaseSpanToPageCache(span);
			// 这时候，我们又是从CentralCache跳转到访问PageCache，思考是否需要加锁
            // 加锁加谁的锁？
			// 加锁加在什么位置？
		}

		start = next;
	}

	// 解锁
	_spanLists[index]._mtx.unlock();
}

PageCache::GetInstance().ReleaseSpanToPageCache(span);这段代码中我们又是从CentralCache跳转到访问PageCache，思考是否需要加锁？

加锁加在什么位置？

        _spanLists[index]._mtx.unlock();

        PageCache::GetInstance()._pagemtx.lock();
        PageCache::GetInstance().ReleaseSpanToPageCache(span);
        // 这时候，我们又是从central cache跳转到访问page cache，先解锁，在加锁，这时候防止其他线程阻塞
        PageCache::GetInstance()._pagemtx.unlock();

        _spanLists[index]._mtx.lock();

释放Span给PageCache时，需要加上PageCache的锁，也需要解去桶锁。

三、PageCache–回收释放内存

  1. PageCache回收CentralCache释放的内存，无可合并的Span，将释放回的Span挂在对应哈希桶中；
  2. PageCache中有可合并的相邻的Span，合并直到无相邻Span或最大为128页后不再合并，减少内存碎片问题。合并的条件为 _usecount=0,_isUse = false，使用 bool _isUse = false; 来判断Span是否处于PageCache的内存空间中。;
  3. PageCache释放内存给操作系统。

（一）kSpan的前后合并

从物理空间来看：

我们无法直接判断kSpan的前后页位于三层级的哪一处，这段空间并不是像我们画图那样，分给CntralCache的Span就被CentralCache拿走，不在PageCache中。实际上，这部分物理空间是始终存在，不会出现切割和移动位置的情况，也就是说这段大块的内存空间中，我们无法知晓在ThreadCache，CentralCache，PageCache是怎样占据这份物理空间的。

也就是说我们无法判断kspan的前后页是否是可以合并的部分，是否位于PageCache的空间中。

为什么不用_usecount判断？

首先看哪些存在会影响_usecount的值，在ThreadCache申请向CentralCache申请内存时，没有足够的内存，于是CentralCache向PageCache申请一个新的Span

但在申请的间隙，ThreadCache仍然可以释放内存给CentralCache，造成释放的内存足够前一步申请的内存使用。这时新申请来的空间未被利用，_usecount==0，又会被收回去合并。

而通过_isUse在CentralCache向PageCache申请一个新的Span时，它的状态就变为了true。

创建PageCache中未分配给CentralCache的Span页号与Span之间的映射关系

我们在前面为了方便回收ThreadCache中的小块内存对象，在kSpan分配给CentralCache时，就建立了各个页号与Span之间的映射关系。但实际上PageCache中还有nSpan悬挂在对应的哈希桶上，而这类nSpan并没有将自身的页号与Span做映射，因此这里我们要进一步对其操作，但是与kSpan的每一页都要和Span做映射不同，nSpan只要提供首尾页与Span做映射即可，用于合并前后页。

合并Span的要求，在前面提到过：

  1. Span在合并时，必须是前后页合并，可以通过一个Span的页号_pageId得到它前后页的页号_pageId，再通过前后页的页号_pageId映射关系找到对应的Span；
  2. 通过_isUse = false来进行判断Span在PageCache对象空间内，才可以对前后页进行合并。

我们要创建PageCache中nSpan的页数和Span的映射关系，就需要在PageCache申请内存时操作，当申请k页的Span时，如果是将n页的Span切成了一个k页的Span和一个n-k页的Span，我们除了需要建立k页span中每个页与该Span之间的映射关系（CentralCache中的span每一页都要映射）之外，还需要建立剩下的n-k页的Span与其首尾页（PageCache中的Span只需要映射首尾）之间的映射关系。

    // 后续的桶中有Span可以切分使用
    for (int i = k + 1; i < NPAGES; ++i)
    {
        if (!_spanlists[i].Empty())
        {
            Span* kspan = new Span;					// 这个是最终要返回的切分好大小的Span
            Span* nspan = _spanlists[i].PopFront(); // 这个是作为切割用的Span
    
            kspan->_pageId = nspan->_pageId;		// 页号
            kspan->_n = k;							// 页数
             
            nspan->_pageId += k;
            nspan->_n -= k;
            
            // span切好了，要记得插入进去链表中
            _spanlists[nspan->_n].PushFront(nspan);
            //存储nSpan的首尾页号与nSpan之间的映射，方便PageCache合并Span时进行前后页的查找
            _idSpanMap[nspan->_pageId] = nspan;
            _idSpanMap[nspan->_pageId + nspan->_n - 1] = nspan;
    
            for (PageID i = 0; i < kspan->_n; ++i)
            {
                _idSpanMap[kspan->_pageId + i] = kspan;
            }
    
            return kspan;	// 给CentralCache
        }
    }
    
    // 后续的桶中没有Span可以用，要向系统申请
    Span* bigSpan = new Span;
    void* ptr = SystemAlloc(NPAGES - 1); // 系统申请内存
    
    // 获取bigspan的 页号 和 页数
    bigSpan->_pageId = (PageID)ptr >> PAGE_SHIFT;
    bigSpan->_n = NPAGES - 1;
    
    // 插入
    _spanlists[bigSpan->_n].PushFront(bigSpan);
    
    // 重复切分128号桶为 k页和 128-k页
    // 重复上列切分步骤
    return NewSpan(k);
    }

（二）PageCache回收内存

PageCache回收内存后要对Span进行合并。

要想合并Span需要满足三个条件（这是从CentralCache）：

一是_usecount==0(在ThreadCache释放内存，CentralCache回收内存时，当其中的某个Span中的内存对象均空闲时，将被PageCache回收内存)；

二是_isUse=false,PageCache中的Span是未使用的；

三是合并起来最大是128页。

// 回收CentralCache中的空闲Span
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	// 合并span的前后页，解决外碎片问题

	// 1.向前合并
	while (1)
	{
		// Span的前一页 对应的Span（在PageCache中存在）
		PageID prevId = span->_pageId - 1;
		auto ret = _idSpanMap.find(prevId);
		if (ret == _idSpanMap.end())
		{
			break;	// 没有前一页，无法合并，跳出循环
		}

		// 有前一页，判断是否被使用中
		// span的页号为前一页对应span的首页号，合并页数
		 Span* prevSpan = ret->second;
		 if (prevSpan->_isUse == true)
		 {
			 break;
		 }

		 // 有前一页，没有被使用中，合并后是否大于128页
		 if (prevSpan->_n + span->_n > NPAGES - 1)
		 {
			 break;
		 }

		 // 有前一页，没有被使用，合并后小于128页-->可以合并
		 span->_pageId = prevSpan->_pageId;
		 span->_n += prevSpan->_n;

		 //将prevSpan从对应的双链表中移除
		 _spanlists[prevSpan->_n].Erase(prevSpan);

		 delete prevSpan;
	}

	//2、向后合并
	while (1)
	{
		PageID nextId = span->_pageId + span->_n;
		auto ret = _idSpanMap.find(nextId);
		// 没有后面的页号（还未向系统申请），停止向后合并
		if (ret == _idSpanMap.end())
		{
			break;
		}
		 
		// 后面的页号对应的span正在被使用，停止向后合并
		Span* nextSpan = ret->second;
		if (nextSpan->_isUse == true)
		{
			break;
		}
		// 合并出超过128页的span无法进行管理，停止向后合并
		if (nextSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		} 
		// 有后一页，没有被使用，合并后小于128页-->可以合并
		span->_n += nextSpan->_n;

		// 将nextSpan从对应的双链表中移除
		_spanlists[nextSpan->_n].Erase(nextSpan);

		delete nextSpan;
	}

	// 将合并后的span挂到对应的双链表当中
	_spanlists[span->_n].PushFront(span);

	// 建立新的映射 -> 该span与其首尾页的映射
	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span;

	// 将该span设置为未被使用的状态
	span->_isUse = false;
}

从CentralCache来的Span，满足上面一，二的条件后，可以查找PageCache中是否有其前后页。

  1. 首先找到Span前后页对应的Span是否存在，分别命名为prevSpan，nextSpan。（注意这里我们只是找到了Span的前后页，并不确定它们是否在PageCache对象空间）；
  2. 其次，要判断prevSpan，nextSpan是否在PageCache对象空间中。通过_isUse==false来判断是否被利用，如果没有被利用，那么他们在PageCache对象空间中，可与从CentralCache中回收的Span进行合并操作；
  3. PageCache中最大的页数就是128页，如果前后页合并Span相加大于128页，是不合理的，因此我们需要加上合并后是否大于128的判定条件；
  4. 最后，满足上列所有条件后，得到的就是一个合并后的Span。这时候要注意对这个新的Span进行必要的处理，比如它的映射关系，也就是注意更新span自身的信息。
  5. prevSpan或者nextSpan原来的位置还插在双向链表中，如果不删除他们，申请（或回收）时他们可能会在被重复利用（或合并），会造成错误。
  6. 新合并来的Span，我们根据（span->_n）将它插入进对应的page页中，（如果从CentralCache回收的Span为什么不做处理，那是因为它从CentralCache中切割后就做了处理）

http://www.kler.cn/a/516539.html

相关文章：

  • 【Go面试】工作经验篇 （持续整合）
  • Vue3.5 企业级管理系统实战（三）：页面布局及样式处理 （Scss UnoCSS ）
  • 基于Springboot + vue实现的美发门店管理系统
  • OpenCV相机标定与3D重建(65)对图像点进行去畸变处理函数undistortPoints()的使用
  • 【Knife4j与Swagger的区别是什么？】
  • 【面试总结】FFN（前馈神经网络）在Transformer模型中先升维再降维的原因
  • 人工智能技术在低空经济产业的应用
  • MyBatis-Plus之BaseMapper
  • 关于为什么java中nextInt()和nextLine()不能混用 | nextInt()和nextInt()之类的可以一起用
  • 设计模式Python版 简单工厂模式
  • OpenEuler学习笔记（十）：用OpenEuler搭建web服务器
  • 【MCU】DFU、IAP、OTA
  • cursor重构谷粒商城05——docker容器化技术快速入门【番外篇】
  • Mac 查看 Java SDK 和 Android SDK 的路径
  • 输入网址到网页显示，发生了什么--讲述
  • linux静态库+嵌套makefile
  • 【深度学习】 自动微分
  • python学opencv|读取图像（四十三）使用cv2.bitwise_and()函数实现图像按位与运算
  • Caesar
  • 【java】IP来源提取国家地址
  • PHP校园助手系统小程序
  • React 前端框架开发详细操作
  • 【AIGC提示词系统】赛博朋克·韵律：一个融合科技与艺术的对话系统设计
  • 如何构建一个简单的React应用？
  • 202009 青少年软件编程等级考试C/C++ 二级真题答案及解析（电子学会）
  • 使用qwen作为基座训练分类大模型