小谈ONLINE-GAME服务器端设计（4）
发表于2016-08-05
原文地址：http://dev.gameres.com/Program/Abstract/Thinking/online_g_4.htm
也许这样的贴代码会让大家觉得很不明白，嗯，我的代码水平确实不怎么样，那么下面我来用文字方式来叙说一下大体的概念吧。对于段页式内存管理，首先分成N个页面，这个是固定的，而对于每个页面内的段则是动态的，段的大小事先是不知道的，那么我们需要回收的不仅仅是页面的内存，还包括段的内存，那么我们就需要一个二维数组来保存是哪个页面的那块段的地址被释放了。然后对于申请内存的时候，则首先检查需要申请内存的大小，如果不够一个页面大小的话，则在垃圾回收站里面寻找可用的段空间分配，如果找不到，则申请一个新的页面空间。
这种脚本结构就类似CPU的指令的结构，一条一条指令按照顺序执行，对于脚本程序员（Script Programmer）也可以培养他们汇编能力的说。
在这一章节，我想谈谈关于服务器端的脚本的相关设计。因为在上一章节里面，谈NPC智能相关的时候已经接触到一些脚本相关的东东了。还是先来谈谈脚本的作用吧。
在基于编译的服务器端程序中，是无法在程序的运行过程中构建一些东西的，那么这个时候就需要脚本语言的支持了，由于脚本语言涉及到逻辑判断，所以光提供一些函数接口是没用的，还需要提供一些简单的语法和文法解析的功能。其实说到底，任何的事件都可以看成两个部分：第一是对自身，或者别的物件的数值的改变，另外一个就是将该事件以文字或者图形的方式广播出去。那么，这里牵扯到一个很重要的话题，就是对某一物件进行寻址。恩，谈到这，我想将本章节分为三个部分来谈，首先是服务器如何来管理动态创建出来的物件（服务器内存管理），第二是如何对某一物件进行寻址，第三则是脚本语言的组织和解释。其实之所以到第四章再来谈服务器的内存管理是因为在前几章谈这个的话，大家对其没有一个感性的认识，可能不知道服务器的内存管理究竟有什么用。
4.1、服务器内存管理
对于服务器内存管理我们将采用内存池的方法，也称为静态内存管理。其概念为在服务器初始化的时候，申请一块非常大的内存，称为内存池（Memory pool），同时也申请一小块内存空间，称为垃圾回收站（Garbage recollecting station）。其大体思路如下：当程序需要申请内存的时候，首先检查垃圾回收站是否为空，如果不为空的话，则从垃圾回收站中找一块可用的内存地址，在内存池中根据地址找到相应的空间，分配给程序用，如果垃圾回收站是空的话，则直接从内存池的当前指针位置申请一块内存；当程序释放空间的时候，给那块内存打上已经释放掉的标记，然后把那块内存的地址放入垃圾回收站。
下面具体谈谈该方法的详细设计，首先，我们将采用类似于操作系统的段页式系统来管理内存，这样的好处是可以充分的利用内存池，其缺点是管理起来比较麻烦。嗯，下面来具体看看我们怎么样来定义页和段的结构：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | typedef struct m_segment_s { struct m_segment_s *next; /* 双线链表 + 静态内存可以达到随机访问和顺序访问的目的， 真正的想怎么访问，就怎么访问。 */struct m_segment_s *pre; int flags; // 该段的一些标记。int start; // 相对于该页的首地址。int size; // 长度。struct m_page_s *my_owner; // 我是属于哪一页的。char *data; // 内容指针。}m_segment_t; typedef struct m_page_s { unsigned int flags; /* 使用标记，是否完全使用，是否还有空余 */int size; /* 该页的大小，一般都是统一的，最后一页除外 */int end; /* 使用到什么地方了 */int my_index; /* 提供随机访问的索引 */m_segment_t *segments; // 页内段的头指针。 }m_page_t; 那么内存池和垃圾回收站怎么构建呢？下面也给出一些构建相关的伪代码：static m_page_t *all_pages;// total_size是总共要申请的内存数，num_pages是总共打算创建多少个页面。void initialize_memory_pool( int total_size, int num_pages ) { int i, page_size, last_size; // 算出每个页面的大小。page_size = total_size / num_pages; // 分配足够的页面。all_pages = (m_page_t*) calloc( num_pages, sizeof(m_page_t*) ); for ( i = 0; i < num_pages; i ++ ) {// 初始化每个页面的段指针。all_pages[i].m_segment_t = (m_segment_t*) malloc( page_size );// 初始化该页面的标记。all_pages[i].flags |= NEVER_USED;// 除了最后一个页面，其他的大小都是page_size 大小。all_pages[i].size = page_size;// 初始化随机访问的索引。all_pages[i].my_index = i;// 由于没有用过，所以大小都是0all_pages[i].end = 0; }// 设置最后一个页面的大小。if ( (last_size = total_size % num_pages) != 0 ) all_pages[i].size = last_size; } 下面看看垃圾回收站怎么设计：int **garbage_station; void init_garbage_station( int num_pages, int page_size ) { int i; garbage_station = (int**) calloc( num_pages, sizeof( int* ) ); for ( i = 0; i < num_pages; i ++) {// 这里用unsigned short的高8位来储存首相对地址，低8位来储存长度。garbage_station[i] = (int*) calloc( page_size, sizeof( unsigned short )); memset( garbage_station[i], 0, sizeof( garbage_station[i] )); } } |
这样用内存池的方法来管理整个游戏世界的内存可以有效的减少内存碎片，一定程度的提高游戏运行的稳定性和效率。
4.2、游戏中物件的寻址
第一个问题，我们为什么要寻址？加入了脚本语言的概念之后，游戏中的一些逻辑物件，比如说NPC，某个ITEM之类的都是由脚本语言在游戏运行的过程中动态生成的，那么我们通过什么样的方法来对这些物件进行索引呢？说得简单一点，就是如何找到他们呢？有个很简单的方法，全部遍历一次。当然，这是个简单而有效的方法，但是效率上的消耗是任何一台服务器都吃不消的，特别是在游戏的规模比较大之后。
那么，我们怎么来在游戏世界中很快的寻找这些物件呢？我想在谈这个之前，说一下Hash Table这个数据结构，它叫哈希表，也有人叫它散列表，其工作原理是不是顺序访问，也不是随机访问，而是通过一个散列函数对其key进行计算，算出在内存中这个key对应的value的地址，而对其进行访问。好处是不管面对多大的数据，只需要一次计算就能找到其地址，非常的快捷，那么弊端是什么呢？当两个key通过散列函数计算出来的地址是同一个地址的时候，麻烦就来了，会产生碰撞，其的解决方法非常的麻烦，这里就不详细谈其解决方法了，否则估计再写个四，五章也未必谈得清楚，不过如果大家对其感兴趣的话，欢迎讨论。
嗯，我们将用散列表来对游戏中的物件进行索引，具体怎么做呢？首先，在内存池中申请一块两倍大于游戏中物件总数的内存，为什么是两倍大呢？防止散列表碰撞。然后我们选用物件的名称作为散列表的索引key，然后就可以开始设计散列函数了。下面来看个例子：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | static int T[] = { 1, 87, 49, 12, 176, 178, 102, 166, 121, 193, 6, 84, 249, 230, 44, 163, 14, 197, 213, 181, 161, 85, 218, 80, 64, 239, 24, 226, 236, 142, 38, 200, 110, 177, 104, 103, 141, 253, 255, 50, 77, 101, 81, 18, 45, 96, 31, 222, 25, 107, 190, 70, 86, 237, 240, 34, 72, 242, 20, 214, 244, 227, 149, 235, 97, 234, 57, 22, 60, 250, 82, 175, 208, 5, 127, 199, 111, 62, 135, 248, 174, 169, 211, 58, 66, 154, 106, 195, 245, 171, 17, 187, 182, 179, 0, 243, 132, 56, 148, 75, 128, 133, 158, 100, 130, 126, 91, 13, 153, 246, 216, 219, 119, 68, 223, 78, 83, 88, 201, 99, 122, 11, 92, 32, 136, 114, 52, 10, 138, 30, 48, 183, 156, 35, 61, 26, 143, 74, 251, 94, 129, 162, 63, 152, 170, 7, 115, 167, 241, 206, 3, 150, 55, 59, 151, 220, 90, 53, 23, 131, 125, 173, 15, 238, 79, 95, 89, 16, 105, 137, 225, 224, 217, 160, 37, 123, 118, 73, 2, 157, 46, 116, 9, 145, 134, 228, 207, 212, 202, 215, 69, 229, 27, 188, 67, 124, 168, 252, 42, 4, 29, 108, 21, 247, 19, 205, 39, 203, 233, 40, 186, 147, 198, 192, 155, 33, 164, 191, 98, 204, 165, 180, 117, 76, 140, 36, 210, 172, 41, 54, 159, 8, 185, 232, 113, 196, 231, 47, 146, 120, 51, 65, 28, 144, 254, 221, 93, 189, 194, 139, 112, 43, 71, 109, 184, 209, }; |
// s是需要进行索引的字符串指针，maxn是字符串可能的最大长度，返回值是相对地址。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | inline int whashstr(char *s, int maxn) { register unsigned char oh, h; register unsigned char *p; register int i; if (!*s) return 0; p = (unsigned char *) s; oh = T[*p]; h = (*(p++) + 1) & 0xff; for (i = maxn - 1; *p && --i >= 0; ) { oh = T[oh ^ *p]; h = T[h ^ *(p++)]; } return (oh << 8) + h; } |
具体的算法就不说了，上面的那一大段东西不要问我为什么，这个算法的出处是CACM 33-6中的一个叫Peter K.Pearson的鬼子写的论文中介绍的算法，据说速度非常的快。有了这个散列函数，我们就可以通过它来对世界里面的任意物件进行非常快的寻址了。
其中name是在散列表中这个物件的索引号，prog则是脚本解释器需要解释的程序内容。下面我们就以NPC为例来设计一个结构：
4.3、脚本语言解释
在设计脚本语言之前，我们首先需要明白，我们的脚本语言要实现什么样的功能？否则随心所欲的做下去写出个C的解释器之类的也说不定。我们要实现的功能只是简单的逻辑判断和循环，其他所有的功能都可以由事先提供好的函数来完成。嗯，这样我们就可以列出一张工作量的表单：设计物件在底层的保存结构，提供脚本和底层间的访问接口，设计支持逻辑判断和循环的解释器。
下面先来谈谈物件在底层的保存结构。具体到每种不同属性的物件，需要采用不同的结构，当然，如果你愿意的话，你可以所有的物件都采同同样的结构，然后在结构里面设计一个散列表来保存各种不同的属性。但这并不是一个好方法，过分的依赖散列表会让你的游戏的逻辑变得繁杂不清。所以，尽量的区分每种不同的物件采用不同的结构来设计。但是有一点值得注意的是，不管是什么结构，有一些东西是统一的，就是我们所说的物件头，那么我们怎么来设计这样一个物件头呢？
1 2 3 4 5 | typedef struct object_head_s { char* name; char* prog; }object_head_t; |
1 2 3 4 5 6 7 | { object_head_t header; // 物件头int hp; // NPC的hp值。int level; // NPC的等级。struct position_s position; // 当前的位置信息。unsigned int personality; // NPC的个性，一个unsigned int可以保存24种个性。}npc_t; |
OK，结构设计完成，那么我们怎么来设计脚本解释器呢？这里有两种法，一种是用虚拟机的模式来解析脚本语言，另外一中则是用类似汇编语言的那种结构来设计，设置一些条件跳转和循环就可以实现逻辑判断和循环了，比如：
1 2 3 4 5 6 | set name, "路人甲"; CHOOSE: random_choose_personality; // 随机选择NPC的个性compare hp, 100; // 比较气血，比较出的值可以放在一个固定的变量里面ifless LESS; // hp < 100的话，则返回。jump CHOOSE; // 否则继续选择，只到选到一个hp < 100的。 LESS: return success; |
那么怎么来模仿这种结构呢？我们拿CPU的指令做参照，首先得设置一些寄存器，CPU的寄存器的大小和数量是受硬件影响的，但我们是用内存来模拟寄存器，所以想要多大，就可以有多大。然后提供一些指令，包括四则运算，寻址，判断，循环等等。接下来针对不同的脚本用不同的解析方法，比如说对NPC就用NPC固定的脚本，对ITEM就用ITEM固定的脚本，解析完以后就把结果生成底层该物件的结构用于使用。
而如果要用虚拟机来实现脚本语言的话呢，则会将工程变得无比之巨大，强烈不推荐使用，不过如果你想做一个通用的网络游戏底层的话，则可以考虑设计一个虚拟机。虚拟机大体的解释过程就是进行两次编译，第一次对关键字进行编译，第二次生成汇编语言，然后虚拟机在根据编译生成的汇编语言进行逐行解释，如果大家对这个感兴趣的话，可以去www.mudos.org上下载一份MudOS的原码来研究研究。 大体的思路讲到这里已经差不多了，下面将用unreal（虚幻）为实例，谈一谈网络游戏服务器的设计。
|