巨人网络游戏开发面经

巨人网络园区包住宿，对于我这个穷小伙还是很有吸引力的！对了他们两面的面试官应该一个是搞客户端，一个是服务端，而我碰到的一面估计是客户端，二面估计是服务端

巨人一面

1.设计一下内存管理器（上来第一个问题我就懵逼了，用链表把内存碎片连起来？不对链表这样一个个访问下去不是很慢。。。gg）

内存碎片的产生：

1.动态内存分配问题：

内存分配有静态分配和动态分配两种
静态分配在程序编译链接时分配的大小和使用寿命就已经确定，而应用上要求操作系统可以提供给进程运行时申请和释放任意大小内存的功能，这就是内存的动态分配。
因此动态分配将不可避免会产生内存碎片的问题，那么什么是内存碎片？内存碎片即“碎片的内存”描述一个系统中所有不可用的空闲内存，这些碎片之所以不能被使用，是因为负责动态分配内存的分配算法使得这些空闲的内存无法使用，这一问题的发生，原因在于这些空闲内存以小且不连续方式出现在不同的位置。因此这个问题的或大或小取决于内存管理算法的实现上。

为什么会产生这些小且不连续的空闲内存碎片呢？

实际上这些空闲内存碎片存在的方式有两种：a.内部碎片 b.外部碎片。
内部碎片的产生：因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。
外部碎片的产生：频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，就会产生外部碎片。假设有一块一共有100个单位的连续空闲内存空间，范围是0~99。如果你从中申请一块内存，如10个单位，那么申请出来的内存块就为0~9区间。这时候你继续申请一块内存，比如说5个单位大，第二块得到的内存块就应该为10~14区间。如果你把第一块内存块释放，然后再申请一块大于10个单位的内存块，比如说20个单位。因为刚被释放的内存块不能满足新的请求，所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是0~9空闲，10~14被占用，15~24被占用，25~99空闲。其中0~9就是一个内存碎片了。如果10~14一直被占用，而以后申请的空间都大于10个单位，那么0~9就永远用不上了，变成外部碎片。

2.系统内存回收机制问题：

内存碎片是一个系统问题，反复的malloc和 free，而free后的内存又不能马上被系统回收利用。这个与系统对内存的回收机制有关。

内存碎片带来的问题：大量的内存碎片会使系统缓慢，原因在于虚拟内存的使用会使内存与硬盘之间的数据交换称为系统缓慢的根源,最终造成内存的枯竭!

如何避免内存碎片的产生：

1>少用动态内存分配的函数(尽量使用栈空间)

2>分配内存和释放的内存尽量在同一个函数中

3>尽量一次性申请较大的内存2的指数次幂大小的内存空间，而不要反复申请小内存(少进行内存的分割)

4>使用内存池来减少使用堆内存引起的内存碎片

内存池管理：

Step1：重载new/delete运算符，接收到程序需要申请内存的大小。

Step2：编写内存池管理类，用于有针对性的管理内存分配。接收到程序需要申请内存的大小后，判断在哪个链中进行内存分配。（如果小于64字节，直接在第一个链进行内存分配；如果是65-128字节，在第二链进行内存分配）

内存池代码实现

1、内存块类
链式内存池的结点，维护了结点所需的信息和指向下一个结点的指针。

2、内存池类

一个内存池相当于一个链表，结点是内存块单元。内存池类维护了4个成员，MemoryBlock* _pHead; //内存块头部 size_t _nBlockSize; //内存块的大小 size_t _nSize; //内存块的数量 char* _pBuff; //内存池首地址
主要提供3个接口，内存分配：allocMemory(size_t nSize)、内存释放freeMem(void* pMem)、初始化内存池void initMemory()。

侯捷老师经常讲：学习C++程序设计要做到"心中自有丘壑"，其实只要明白内存池是一个类似链表的结构，当需要分配内存时，分配一个内存块；当需要回收内存时，释放一片内存区域，并管理好内存块。

需要特别注意的是：上面的图中也表达出了，内存块由头部信息+内存空间组成，申请内存的人(程序员/用户)关心的不是内存块，而是他们想要申请的内存。因此，申请内存的人操作的是内存块 - 头部信息的部分，而内存池类维护的是整个内存块的单元。比如说在分配内存函数中，void* allocMemory(size_t nSize)，返回值是return ((char*)pReturn + sizeof(MemoryBlock));，返回给用户申请的内存空间是内存块的首地址向后偏移一个头部大小的位置。