mc做弊端网站,抖音代运营协议书范本,山东省建筑施工企业安全生产管理,做网站一定要效果图吗项目简介
这个项目是实现了一个高效的并发内存池。它的原型的goggle的一个开源项目tcmalloc#xff0c;即thread-cache malloc#xff08;线程缓存的malloc#xff09;#xff0c;实现了高效多线程的内存管理#xff0c;可实现对系统提供的内存分配函数malloc和free的替代…项目简介
这个项目是实现了一个高效的并发内存池。它的原型的goggle的一个开源项目tcmalloc即thread-cache malloc线程缓存的malloc实现了高效多线程的内存管理可实现对系统提供的内存分配函数malloc和free的替代。
内存碎片
内存碎片分为外碎片和内碎片。 外碎片是指未被分配给进程的内存块由于其太小了无法满足进程申请的内存大小。 内碎片是指内存块已经分配给了进程但是由于各种原因比如结构体的内存对齐不会使用内存块的某一部分一直处于空闲状态直至释放。 定长内存池设计
所谓定长就是每次申请出来的内存大小都是一样的。 申请过程首先在堆上申请一大块内存按对象的大小从大块内存中截取对应的内存供进程使用。 释放过程内存池中维护一个freelist_的链表用来回收释放掉的内存采用头插的方式挂在freelist_后边。在申请内存过程中优先查看freelist_后边是否回收的内存块优先使用freelist_中的内存供进程申请用。达到重复利用的目的。 项目框架 该内存池由3部分组成 1. thread cache线程缓存是每个线程独有的用于小于256KB的内存的分配线程从这里申请内 存不需要加锁每个线程独享一个cache这也就是这个并发线程池高效的地方。 2. central cache中心缓存是所有线程所共享thread cache是按需从central cache中获取的对 象。central cache合适的时机回收thread cache中的对象避免一个线程占用了太多的内存而其他线程的内存吃紧达到内存分配在多个线程中更均衡的按需调度的目的。central cache是存在竞争的所以从这里取内存对象是需要加锁首先这里用的是桶锁其次只有thread cache的没有内存对象时才会找central cache所以这里竞争不会很激烈。 3. page cache页缓存是在central cache缓存上面的一层缓存存储的内存是以页为单位存储及分配的central cache没有内存对象时从page cache分配出一定数量的page并切割成定长大小的小块内存分配给central cache。当一个span的几个跨度页的对象都回收以后page cache 会回收central cache满足条件的span对象并且合并相邻的页组成更大的页缓解内存碎片的问题。 内存池实现逻辑
threadcache
threadcache设计称为一个hash结构申请的大小在其区间按各自的对齐数均匀划分桶。
其中hash的对其规则如下 1B bites128B对齐数8B其划分的桶就有128/816个即8、16 ······ 128 8KBbites64KB对齐数1KB其划分的桶就有(64 - 8)/156个即9、10 ······ 64 64Kbites256KB对齐数8K其互粉的桶就有(256-64)/824个即72、80 ······ 256 ps这里的排列时不同的桶下应挂的小内存的大小并不是hash桶的下标。其下标是按其排列顺序由低到高由0开始的。 关于内碎片浪费的计算 比如申请的大小为为129B就会按16B对齐实际申请128B16B144B就会多出15B的内碎片内存浪费率就是15B/144B0.104。 再比如申请的大小为1025B就会按128B对齐实际申请12041281332B多出127B的内碎片内存浪费率就是127B/1332B0.095。 对上边内存规则有了一定认识之后对下边threadcache的结构才会有更深刻的理解。 TLSThread Local Storage线程本地存储技术普通的全局变量在多线程中是贡献的一个线程对其进行了修改所有线程都能看见这个修改而线程私有的全局变量与普通全局变量不同线程私有的全局变量是线程的私有财产每个线程都有自己的一份副本某个线程对其所做的修改只会影响到自己的副本并不会修改其他线程的副本。 申请内存
1、每个线程通过TLS无锁获取自己独属的ThreadCache对象
2、如果ThreadCache中对应hash桶下边的freelist_结构不为空从中取出内存供进程使用
3、如果ThreadCache中对应hash桶下边的freelist_结构为空向CentralCache中申请内存。 ps向CentralCache中申请内存过程中使用类似TCP拥塞控制中的满开始算法。以达到申请内存的多少的合理性即并不是单个单个内存申请而是批量申请。
释放内存
1、将不用的内存通过内存大小计算出其在ThreadCache中对应桶的位置将其插入进去。
2、当ThreadCache中某个桶中挂的链表过长的时候即链表长度大于一次批量申请的内存时就将ThreadCache中对应桶中的内存回收给CentralCache.
centralcache
centralcache设计也是一个hash结构也是使用和threadcache的对齐规则。不同的是centralcache的每个hash桶挂着的是span对象是一个双向链表。每个span中又切分了多个对应其对齐数的小内存对象是一个单链表结构。 其次从整个项目框架上看多个ThreadCache内存不足或者需要释放内存的时候都需要涉及到centralcache因此centralcache最好设计称为单例模式供多个threadcache访问。
申请内存
1、ThreadCache向CentralCache申请内存首先获得从CentrlCache对应位置的hash桶中获得一个Span此时需要加桶锁在该Span中拿出ThreadCache申请的内存数尽力而为。
2、如果CentrlCache对应位置没有Span则向PageCache中申请内存。将向PageCache中刚申请的内存进行切分成freelist_。
释放内存
1、回收ThreadCache中的freelist_链表过长的内存首先得找到CentralCache中对应的hash位置
2、其次CentralCache得找到这个个回收回来得freelist_链表隶属于CentralCache对应hash位置下的哪一个span。 这里找到对应的span使用了一个哈希结构unordered_mapPAGE_ID, Span*在PageCache向CentralCache中分配内存的时候就建立好了对应的映射关系了。 关于PAGE_ID的计算是这样的(PAGE_ID)ptr PAGE_SHIFT即将内存地址右移PAGE_SHIFT位。这样每一个内存地址都能找到自己的PAGE_ID。再通过映射关系找到自己所属的Span。 3、向对应hash位置下的对应span中依次挂入回收的链表并且useCount对应减少。
4、当useCount减至0的时候标志着该span中的所有小块内存都被回收回来了。就应该向PageCache中归还该span的内存了。
pagecache
pagecache的设计也是一个hash结构采用的是直接定址法法映射。其每个hash桶下挂着的是以页为单位的对应其范围大小的span内存对象是个双向链表结构。 这里的PageCache也设计称为单例模式。
申请内存
1、首先向满足CentralCache申请对应的桶中查看时候有span。有则交付一个span。
2、满足CentralCache申请对应的桶中没有span就向后续桶中遍历查找存在内存的桶。
3、后续桶中的span必定比满足CentralCache申请对应的桶中的span大需要在后续桶中的span切分满足CentralCache申请对应的桶中的大小span剩下的内存则按剩余内存大小映射插入到对应的hash桶中。
释放内存
1、回收来自CentralCache返还的span进行合并页缓解内碎片的问题。
2、向前合并1前边没有页号了2前边的页号正在使用3合并后的页数超过128页无法管理。则不合并。
3、向后合并1前边没有页号了2前边的页号正在使用3合并后的页数超过128页无法管理。则不合并。
内存池优化逻辑
大块内存的申请和释放
我们这里内存池的单个线程能申请的最大内存就是256KB当线程申请的内存大于256KB的时候便能是为是大块内存。
我们设计PageCache的时候一页的大小定为的8K当申请256KB的时候就需要256KB/8KB32个span。因此将Page Cache的哈希桶个数多弄几个比如32*4128个即一个128页的span可以满足四个线程去申请256KB大小的内存。 当申请大块内存的时候我们直接去向PageCache中去申请。 在PageCache中当申请超过128页的大内存的时候就直接向堆申请。 释放的过程相反即可。 释放大块内存的时候直接向PageCache中归还。 在PageCache中归还超过128页的内存时直接归还给堆。 替代系统内存分配函数
我们的内存池是能替代系统提供的内存分配函数malloc、free的因此我们不能在里边继续使用系统提供的内存分配函数。定长内存池便能达到使用内存分配的效果。
使用基数树优化
基数树或称压缩前缀树是一种更节省空间的Trie前缀树。对于基数树的每个节点如果该节点是确定的子树的话就和父节点合并。基数树可用来构建关联数组。
为什么要使用基数树优化呢
在PageCache向CentralCache分配内存的时候我们需要建立PageId和Span的映射关系我们使用的是STL中unordered_map其底层是使用的哈希表。关于哈希表有如下缺点不符我们内存池的使用 1、哈希表的底层必定使用了系统内存分配相关函数 2、哈希表的底层使用数组实现的数组大小不好确定还涉及到扩容的问题扩容就分为原地扩容和一定扩容。 接下来就开始介绍基数树了
单层基数树 单层基数树就如同hash的直接定址法一样其中的模板参数表示的是存储页号的位数。在32位环境下是32-PAGE_SHIFT64位环境下是64-PAGE_SHIFT。我们的PAGE_SHIFT是2^13也就是说BITES在32位环境下的值就是2^19位。占用的内存就是2^19*42^212M。
比如页号为多少就在对应的void**的数组中找对应的位置其位置存储的就是它Span的信息。 双层基数树 上边的双层基数树的模板参数含义和单层基数树一样都代表存储页号需要多少位。
这里的双层基数树的前5位用于标识页号能通过第一层对应位置中的内容找到第二层的数据第二层的数组标识着Span的属性。32位环境下二层基数树需要的大小是2^19*42^212M。 项目反思
项目不足 可能存在内存泄漏。在ThreadCache的回收逻辑里当哈希桶下挂的freelist_过长的时候才将freelist_向CentralCache中返还。当freelist_挂的内存不长的时候呢比如说就只挂了一个小的内存对象并不满足过长的条件就不会向CentralCache里返还就造成了内存泄漏的问题。 项目优势 1、ThreadCache使用了TLS技术每个线程无锁获得自己独属的ThreadCache对象。 2、ThreadCache内存不足时向CentralCache申请时并不是需要多少申请多少而是批量申请也就是说在向CentralCache申请依次后Thread Cache就有了一批内存对象供本线程使用。即减少了ThreadCache向CentralCache申请的频次而CentralCache的访问时会加锁的这也将使CentralCache中的桶锁不会很激烈。 3、使用基数树优化既可以代替底层使用new和delete有可以利用基数树可以根据一个长整型比如一个长ID快速查找到其对应的对象指针比hash映射来的简单和节省空间。
