面试问题之高并发内存池项目

项目部分
1.这个项目是什么?
高并发内存池的原型是谷歌一个开源项目，tcmalloc，而这个项目，就是tcmalloc中最核心的框架和部分拿出来进行模拟。他的作用就是在去代替原型的内存分配函数malloc和free。这个项目涉及的技术有，c++，数据结构(双向链表，哈希桶)，操作系统内存管理，多线程，互斥锁，单例模式等方面的技术。

2.这个项目是怎么组成的?
由threadcache，centralcache，和pagecache三部分组成，什么意思呢，当用户使用我们这个项目去申请内存时，进入这个函数后，先去threadcache申请内存，如果不够，再去向第二层centracahhe去申请内存，要是还是不行，就去第三层申请内存，最后把申请到的内存返回给用户。这就是，tcmalloc的大概实现，当然了，很多细节还没展开说。

3.这个项目实现后，效果怎么样?
在项目完成后，拿我们实现的tcmalloc去和原先的malloc对比。
申请固定内存大小时，我创建了4个线程，分别执行10轮操作，每轮n申请释放1万次，也就是一共进行了40万次的申请释放，结果是malloc用了31ms左右，而tcmlloc只用了11ms左右，就是快了3倍。
当我尝试申请不同内存时，同样的，4个线程，执行10轮，1轮1万次，共40万次申请释放操作，这次，malloc的时间用了1023ms，而tcmalloc只用了113ms，倍数来到了10倍，也就是说，理想状况下，在未来的多线程开发环境下申请不同的内存，使用malloc函数如果要用10s才能完成内存的申请和释放,我只要用1s。

4.你在这个项目收获了什么?
调试方面:
一，加深了条件断点理解和使用，还可以设置具体断点条件让它停下来
二:学会了使用查看函数栈帧，当在断点处停下，当前函数没问题，就可以调用函数堆栈去看看调用这个函数的函数有没有问题。(蛮实用的)
三:疑似死循环的处理
当我们设置了断点，但它迟迟没有到达断点处，程序也没有崩溃，就可能进入死循环了，这时候全部中断，程序就会停在死循环的部分。

对操作系统内存管理的理解:
以前认为申请内存就是简单从内存里哇一块过来就行，实现了这个项目后，才发现，申请内存的时候可能有多层内存池，这个没有空间，再逐步往后申请，再比如，申请不同内存块，再造成的内存碎片问题啊等等

对c++语法和数据结构更加熟悉，项目是c++，虽然代码不是很多，但都是精华，涉及了很多语法的使用，比如智能指针，强制转换，类的使用啊，还有数据结构啊，对链表的操作，插入删除，哈希桶的操作，对齐映射等等，加强了我对代码的掌控力

5.你在这个项目遇到的最大困难是什么?
可能就是调试的时候吧，因为我是写完一个功能然后调试一下，确保每个功能没有问题，然后到了最后，我感觉没啥大问题了，然后十多个文件，一运行，得得得得，一排排错误，把我整懵了，就开始调试了，除了一些语法，其中比较难调试的，是申请内存的一套龙过程，经常调试过程中要么就是因为空指针，要么就是走到不该走的地方去了，后面加了应有的条件判断，还是函数功能的完善，问题就越来越少，当时看蛮兴奋的。
还有一个比较大的问题，当时比较tcmalloc和malloc的效率，发现tcmalloc还比malloc申请释放内存要慢一点，然后我就上网查为什么，怎么解决，后面发现可以用vs自带的性能分析，设置成debug模式，然后进入调试的性能诊断，后面发现自己的有个函数占了时间的近一半(mapobjecttospan函数–地址和页号的映射关系)，然后发现这个函数加了锁，恰恰这个函数又经常被调用，就造成了效率低下，然后我就查资料，csnd，说用基数树不用加锁，又能完成原先的函数功能，我就把基数树套上去，后就发现果然快了很多

6.为什么基数树不要加锁?
因为不可能存在多个线程对同一个页进行读取映射和建立映射的操作，读取映射的时候是在span中use_count不为0时，而建立映射是在usecount为0的时候，一个页中的usecount没有两种状态，所以不可能出现多个线程对一个页进行读取映射和建立映射的操作。

7.那一个线程读取映射，一个线程建立映射，怎么办呢?
如果是红黑素哈希表的话那就会有影响，哈希和红黑树的插入，删除都会影响到整个数的一个情况。，所以必须要加锁，但如果是基数树的话，因为它的空间一旦开好，就是固定的，所以不用担心建立其他页的映射会影响本页的读取，就和一个固定大小的数组一样，不需要加锁

8.那说说你在这个项目对锁的使用吧?
这个项目三部分可能会涉及线程安全，第一部threadcache，我的解决方案是，使用线程局部储存，使得每一个线程都有自己的专属内存，在这个线程内部是全局可见的，但在其他线程那是不可访问的，所以通过这种方法就不必再加锁了，因为他本身就解决了线程安全问题了
第二部分有线程安全问题的cencatalacache，当多个线程向哈希桶拿内存的时候会有问题，所以我给它加了个哈希桶锁，不用把整个哈希桶都锁起来，这样一来，只有线程访问相同一个桶的时候，才有加锁解锁的消耗，这也是他效率高的原因一部分
第三步有线程安全的是，当多个线程访问pagecache的哈希桶时会有线程安全，因为在这里一个线程操作会影响多个地方的桶，加锁解锁太频繁了，所以在这里，我选择直接加把大锁，一次只能一个线程访问pagecache的哈希桶。

9.那说说用户在申请一块内存要经过哪些流程吧?小伙子！
好的，面试官！
假设用户要申请一个7字节的内存，然后调用tcmalloc这个函数，进入这个函数后，我们先把7字节对齐成8，这样做是为了避免内存碎片，对齐的字节方便后续我们对内存碎片的处理。对齐后，线程第一次申请内存，通过线程局部存储获得自己专属的threadcache，然后通过threadcache去申请内存，对齐的字节数是8，那我们就找到threadcache的哈希桶的0下标去获取一个8字节的内存块，然后发现没有，这时候就找二哥，centralcache，因为哈希桶的对齐映射关系是一致的，线程也去centalcache的哈希桶0号去获取一个非空span，接着计算thread要多少个8字节内存块，这一块我使用的是慢反馈算法，第一次给一个，第二次给两个，第三次给三个，越就是你调用的越多，以后我就返回越多个内存块给你，但最多返回512个，这次是第一次，就返回一个8字节内存块就行，那就哈希桶里找啊，找之前加锁，发现一个非空的span都没有，就去找大哥，找之前解锁，然后加上大哥的锁，找大哥要多少呢，三弟刚刚要一个然后乘以他要的字节，也就是8个字节，不满一页按一页申请，大哥就去自己的第一个哈希桶找有没有1页的内存卡，发现没有，就往后找，发现还是没有，就向系统申请一个128页的内存块，然后继续找，把128拆成一个一页的和一个127页的，返回一页给二弟，二弟把这个一页切成512的8字节挂在自己的0号哈希桶，返回一个给三弟用。至此，整个申请内存流程大致完成。

10.说的不错，那你说说你释放的流程吧?
厚礼谢，感谢！
这个项目的释放内存函数叫tcfree。
当用户通过tcfree释放内存块时，线程会把这个内存卡先挂在三弟的对应的哈希桶后面，如果这个哈希桶后的链表数量超过了我们设定的值，就把这段链表，取出来，挂着二哥对应的哈希桶后面，同时查找映射表看看，不同的内存块挂着不同的span后面，确保每个span后跟着的内存块都是span这个范围里的。同样的，当二哥后面挂的链表过长，满足一页大小之后，就把他取下来，然后挂着大哥对应的哈希桶后面，同时，从这页开始，尝试向前合并页数，向后合并页数，这里返回的是一页就尝试向后看看有没有2页的，有就合成三页，然后把1/2页的span删除，继续向后合并，直至遇到空桶。至此，这个项目大概释放内存流程就走完了

11.给定100亿个整数，设计算法找到只出现一次的整数

C++语法部分

1.1.谈谈智能指针吧?
智能指针就是利用对象的生命周期来控制程序资源，当对象出了作用域，就自动调用对象的析构函数，就能解决内存泄露问题了

2.智能指针有哪几种呢?讲讲他们的区别?
根据解决智能指针拷贝问题方法的不同，把智能指针大概分以下几种
第一种autoptr，他是通过转移资源所有权来解决拷贝问题，也就是假如有一个智能指针a指向一块资源，这时候用a拷贝出一个b智能指针，此时，b就接管了资源的所有权，a就废了。
第二种，是uniqueptr，他的解决方法是通过把类的拷贝构造函数和拷贝赋值函数私有化，直接不让进行智能指针的拷贝
第三种，sharedptr,他是通过引用计数来解决智能拷贝问题，每一块资源都对应着一个引用计数，当增加了一个智能指针指向这块资源，引用计数就加加，如果有指针不指向这块资源了，智能指针不必直接调用析构函数去释放这块内存，而是将引用计数减一，如果此时为0，则进行调用析构。
ps，这个引用计数变量是在堆区，这块资源的所有智能指针对象共享这一个变量，不能放栈区，那每个个智能指针都有一个计数了，也不能变为全局或者变为静态变量，那么就是所有资源的所有对象都共享这个计数，也不对。
第四种，是为了解决，sharedptr的循环引用的问题(当智能指针管理的是节点是，并且节点一指向节点二，节点二指向节点一，那么此时，双方的引用计数都是2，当节点一，节点二出了作用域，引用计数减为一，但此时会进入死胡同，节点一的资源释放取决于，节点二中的prev变量，节点二资源的释放取决于节点一中的next变量的释放，而节点一中的next的释放又取决于节点一，节点二中的prev释放取决于节点二的资源释放，就进入死循环了)是weakptr，他把节点中的prev和next指针换成了weakptr指针，构造出来的weakptr指针和sharedptr一块管理资源，但不会增加引用计数，就解决其的循环引用问题了

3.c有强制转换为什么还要，增加其他的类型转换。
一，把所以情况混在一起，可读性低
二，有时会减少精度

4.c++有哪些类型转换?
staticcast用于两个类型相近的转换，比如int和double的转换
reinterpretcast用于两个类型不同的转换
constcast用于去除const属性，使用后就可以对const变量进行修改了
PS，const变量认为其不会变，就变值放在寄存器中，但我们修改的是内存中的值，所以打印出来还是原来的值，因为此时OS是从寄存器中拿的值。这是我们可以用volatie关键词对const进行修饰，这样就不会做多余的优化，而且去内存中拿值了
最后一种类型转换是dynamic，是一种向下转换，将父类的指针或引用转化成子类的指针或引用，但如果父类的指针原先是指向父类的，转换成子类的指针，它可能会调用子类的资源，那么就是不安全的，此时调用dynamiccast就会失败并返回一个空指针

5.谈谈进程通信中的管道传输吧?
管道通信是父子进程的一种通信方式，父进程先创建管道，然后再创造子进程，然后父子进程关掉相应的读写文件符，确定谁向谁输入。管道通信自带互斥和同步，
要不就是父进程在操作管道，要么就是子进程在操作，当写满了，写端进程就被挂起，待管道有空间了，再唤醒写端。管道通信是半双工通信，要实现双方同时通信，需要两个管道，此为匿名管道，pipe函数创建匿名管道，参数是一个输出型数组，返回两个指向管道的读写文件描述符。

6.再谈谈命名管道吧?
两个无亲缘关系的进程，可通过命名管道的文件名打开同一份管道文件进行通信，mkpipo函数，第一个参数是表示要创建命名管道名字，是以路径还是文件名(默认当前路径创建)，第二个参数是以什么权限打开，创建一个命名管道，服务端以读的方式，客户端以写的方式打开，就可以通信了。

7.二者区别？
匿名管道和命名管道的区别在于，创建方式(函数)和打开方式(匿名默认都打开，命名要自己去选择)

8.共享内存通信?
在物理空间申请一块共享空间，然后将不同进程的页表和这块空间建立映射，同时在其各自的虚拟空间中开辟空间，把虚拟空间也和其页表建立映射，那么虚拟空间就和物理空间映射起来了，这些进程就看见了同一份内存，这一份内存就叫共享内存。创建共享内存用得是shmget函数第一个参数是key，标识这块共享内存在系统的唯一性，第二个参数是这块内存的大小，第三个参数是创建共享内存的方式。

9.共享内存和管道比较的优缺点?
优点，只需要拷贝两次，而管道要拷贝四次，所以最快。
缺点，管道自带互斥和同步，而共享内存啥也没有。

10.谈谈消息队列吧?
消息队列让不同进程看到同一份资源的方法是，创建一个队列，队列里都是数据块，进程a和进程b要写入信息都在队列的尾部，读取都在队列的头读取，创建函数是msgget函数,第一个参数是key值，是系统中的唯一标识，第二个参数是打开方式。

全靠龙哥博客活着，
各位看官，要是想搞明白八股文去看2021dragon（龙是这样打的吧），超经典！