多线程面试题|多线程游戏服务器技术开发

2008-07-27 手机技术 阅读:

 这些东西是平时遇到的, 觉得有一定的价值, 所以记录下来, 以后遇到类似的问题可以查阅, 同时分享出来也能方便需要的人

写在前面的
存在即合理, 不管什么事, 都是有原因有理由有前提的, 所以在谈论之前我们先要明确一些东西
1. 服务器端使用多线程的必要条件是多核, 且物理核的计算能力总和>>服务器程序的计算量. 如果不满足上述条件, 应该先考虑硬件配置问题.
2. 为什么要用多线程? 是为了充分利用多核增加计算量, 增大计算量的目的是什么? 支持更为复杂的玩法. 这里有很重要的信息, 那就是"支持更为复杂的玩法"是目的, 而"增加计算量"是达到目的的手段; 前者是策划域问题, 而后者是程序域问题. 一个需求和实现的结合点.
3. 当计算量达到时, 其他短板开始起作用, 也就是说不要去追求所谓最好利用计算量之方法, 转而追求计算量不要成为最短板即可.
这片文章是在有"支持更为复杂的玩法"这样的需求, 且当前存在"计算量目前是最短板", 且"由于没有充分利用多线程发挥机器多核计算量即计算量有较多剩余"的情况下的一些探讨和心得.
申明: 本文并不想得出任何"我这个就对!"的方案, 只是将我在实践中遇到的问题, 和解决问题或是看到的一些思路写出来, 期望能引发大家的探讨:) 相比之下文中提高的方案只不过是一个example罢了

一个地图一个线程的方案
关于在游戏服务器中使用多线程, 有一个常常被提到的方案是: 一个地图一个线程, 这个方案的一个推广就是平行子系统中每个子系统对应一个线程. 个人认为这个方案还是值得商榷的. 下面来说明一下我的看法.
根据一些讲解系统的名著中的定义: 在问题域的世界中, 交互联系格外紧密的一群实体之间形成了一个系统. 一个子系统之所以被划分成为一个子系统, 是因为在子系统中的成员的交互和联系频率要远远大于和系统外实体的交互和联系, 这是一个很重要的结论. 我们可以从这里得到一个推论: 划分良好的子系统内部交互非常紧密, 和外部实体交互相对较弱. 很巧的是我们在设计中往往会把这里的子系统划分为程序中的一个功能模块, 模块也有这样的性质, 模块中的交互要远远大于模块间的交互.
有了上述理论的支持, 再来看看为什么说"一个地图一个线程"这样的方案不可取? 一个地图是一个子系统, 地图间的交互是非常小的, 的确是这样, 可能就是在不同地图中移动时等不频繁事件. 这里可以分析一下"地图绑定线程"这个想法的依据:
1. 增大计算量. 在系统中引入多线程, 利用多核, 加大服务器端的计算能力(提供更多的游戏逻辑处理), 这样就可以在一个服务器上容纳更多的玩家.
2. 防止犯错. 避开多线程的锁的问题, 把交互性强的部分分在同一个线程中, 这样的话在大部分情况下避免锁, 只有在很少的跨地图交互时才使用同步方法来保证[避免锁可以防止锁的竞争, 更重要的是在实际编程中解放程序员, 因为时刻考虑多线程问题太痛苦了, 犯错不可避免]. 放在这里就可以发现按地图划分是一个很好的划分线程的方法.
该方法的问题在于首先它不一定很发挥出多核的效果, 因为游戏中人不太会是均匀的分布在多个地图上. 这样就会产生有的线程都忙不过来了[地图人很多], 有的线程很闲[地图人很少], 问题的本质是这种使用线程的方法限制了每个地图的可使用计算量[无形中的一个假设是: 单个核的计算量是足够的, 一旦现实情况不符, 服务器端就会掉帧], 也就是说对每个地图来说, 还是单线程的, 并没有达到想要的"增大计算量"的目地. 其次, 系统的稳定性差, 因为只要有一个线程core掉, 后果可想而知. 再次, 暂时不谈前两个问题, 那么在计算量得到充分满足的条件下, 根据"短板效应", 你的系统的能力又会开始受到内存, 网络等其他因素的影响, 这时你可能会想要在其他机器上横向扩展系统, 你必须单独设计这一部分, 多线程体系本来就有"我能发挥机器的计算能力, 计算量从此不是问题"这样的倾向, 但是它的一个不可回避的问题就是, 多线程的执行流共享程序进程空间, 它必须在同一台主机上. 分布式的横向扩展对多线程来说是另一个课题, 它从来没想过这个, 你得自己去实现.
其实根据设计的特点, 这里还不如只用多进程来代替多线程, 因为:
1. 多进程同样发挥多核的计算能力, 至少在"地图绑定线程"这个问题上不弱于多线程, 但也不会强, 因为也受到单线程地图的影响.
2. 多进程稳定性好, 一个地图进程core了, 其他地图不受影响.
3. 使用socket进行地图[进程]间通信手段, 天然支持分布式部署, 在系统需要横向扩展时, 不用做任何的额外工作.
总的来说, 这种平行子系统中一个子系统对应一个线程的方法看似使用的多线程, 但是本质上还是单线程的设计思路, 所以不是一种很好的方案, 但是这个方法有它的可行性和合理性, 因为它的确是分摊了计算量, 而且不用过度考虑锁的问题, 所以它还是有很重要的参考价值.

去现实世界中寻找答案
另一个想法是, 游戏世界中的每一个active obj都有一个线程+一个消息对列. 这个想法看起来不现实, 但是它是出于对现实世界中可响应的实体的最好模拟. 我记得刚工作的时候, 带我的人最后也是my friend的--徐晓刚同学就告诉我, 游戏中的实体一定要和现实生活中的类似实体有对应, 现实实体是怎么样的, 你游戏中的实体就做成什么样, 当时我听了觉得不对啊, 不是要抽象么什么什么的, 典型的书看多了, 但是现在看来确实是这样的, 游戏中的实体都是源于生活的, 要想做一个好的模拟, 还是得观察和研究现实中的实体才行.
比如现实生活中确实就是这样, 可以有反应的实体都是时刻在接受着外界的信息(消息), 然后它的反应其实就是在处理这个信息[在它自己的线程里处理这个消息]. 比如说, 你丢一个骨头给一个小狗, 就相当于给它发了个消息[你有吃的了], 小狗就会处理这个消息[啃骨头]. 再比如说, 妈妈告诉小孩, 去把垃圾倒了, 小孩听到这个消息, 就会去倒垃圾. 可以看出来, 这都是 可执行体+消息 的结构. 当然, 妈妈也可以告诉小孩, 你去把垃圾倒了, 然后再去商店买一点盐. 小孩收到这两个消息的时候, 就会记下来, 先去到垃圾, 然后去买盐, 这个其实相当于小孩有一个记录消息的队列, 他会依次处理队列中的消息.
所以这里我个人得出的结论是在多线程系统中:
1. 系统本身是内聚封闭的, 它不能直接去查看不是自己内部的数据, 方法等, 别人也不能直接来查看它的相关信息, 系统只负责维护自己的状态.
2. 如果需要交互, 系统间应该显式的走消息机制.
在现实生活中找到有反应的实体并观察它们的行为后, 就可以寻找它们的共同点, 这个过程就是抽象, 抽象并不是打开编辑器, 想着自己要写代码来抽象这个问题呀, 而是在现实中找到对应并归纳共性的过程. 这里看到, 可以独立的反应的实体具有两个性质:
1. 可以独立行为---也就是说他们是active的. 一个npc是一个系统, 一个player也是一个系统.
2. 有一个消息队列---他们可以处理队列中的消息.
映射到程序中, 可以独立行为就单独给它分一根线程呗, 消息队列不是问题, 每个线程的唯一任务就是处理消息队列中的消息. 但是如果能这么简单就不叫"源于生活高于生活了". 这样的弊端一看就看出来了, 游戏中每个有反应的实体一个线程不现实, 就拿我知道的来说, 5000个npc和2000个玩家吧, 都是有反应的实体, 一共启动5000+2000=7000根线程, 显然不现实, 开销上受不了.
但是这个抽象的确很不错, 很符合现实, 所以我不想放弃它. 那么还是要从现实世界中学习如何"降低开销", 类比一下, 比如一个食堂的老板, 他雇佣了一个洗白菜工, 一个洗芹菜工, 一个切白菜工, 一个切芹菜工, 一个炒白菜工, 一个炒芹菜工, 这样的配置不能说错, 没问题可以工作, 不过过了几天老板就发现了, 开销太大了, 每个月挣的不如花的多, 而且还有人员有大把空闲时间. 于是他让洗菜的不管白菜芹菜一起洗, 切菜和炒菜的人也一样. 这样就剩下3个人了, 过了几天后老板又开掉了洗菜的人, 让切菜的人兼上洗菜的活, 这样就只剩下两个人的人力开销.
类比到计算机中, 我们创建的线程就是雇佣工人, 工人不是免费的, 是有人力成本的, 线程也一样, 它不是免费的, 是有开销的. 所以你创建不了太多的线程, 就和你请不起太多的员工是一个道理. 在现实生活中通过让一个员工干更多的活, 来达到降低成本的方法, 在这里也是适用的.
首先讲一个不易区分的地方, 就是"能动"和"动"的区别. 英文active和actor, 一个是形容词, 一个是动词. 这个很重要, 因为我们的系统中, active object很多, 但是actor是需要控制的, 不可能太多. actor其实直接对应于一个线程, 而active object对应于诸多的可反应的实体. 比如npc, player等等.我们需要用actor来驱动active object, 没有被驱动的active object是静止的, 只有用actor才能赋予它活力. 所以我们可以写下如下的代码.

可反应的实体的定义
class activeobj {
msgqueue mq;
void Active() {
processMsg(mq.PopFront());
}
void RecvWork(msg) {
mq.push(msg);
}
}

创建多个实体
activeobj objs[34];

actor驱动实体
void actor() {
while (true) {
foreach(obj in objs) {
obj.Active()
}
}
}
这里, 每个activeobj都有自己的消息队列, 你可以使用RecvWork向activeobj发送消息, 而这个activeobj被actor激活的时候就会去处理自己消息队列中的消息, 这样整个世界中的obj都具有活力了, 下面代码表示在多线程世界中上述代码的形式, 也就是说, 存在多个actor

可反应的实体的定义
class activeobj {
msgqueue mq;
lock mc;
void Active() {
mc.Lock();
msg m = mq.PopFront();
mc.Unlock();
processMsg(m);
}
void RecvWork(msg) {
mc.Lock();
mq.push(msg);
mc.Unlock();
}
}

创建多个实体
activeobj objs[100];

actor驱动实体
void actor(int i) {
while (true) {
for (j = i * 25; j < (i + 1) * 25; ++j) {
objs[j].Active()
}
}
}

创建actor
createActor(actor, 0)
createActor(actor, 1)
createActor(actor, 2)
createActor(actor, 3)
上面演示的策略是创建4个actor, 每个actor负责驱动固定的25个obj, 每个activeobj有自己的消息队列锁, 这样就可以保证消息队列的线程安全. 这样的好处是比较简单, 但是这个做法的问题也有很多:

1. 消息的时序不对, 比如, 我先给obj[3]发了一个消息, 然后给obj[1]发了一个消息, 那么根据上面的逻辑, obj[1]的消息很可能会先于obj[3]被处理. 如果这两个消息之间先后没有关系还好, 但是一旦有逻辑上的先后关系, 这样处理就是错误的了. 问题的根源是: 处理消息总是按照obj的排列顺序, 而不是按照收到消息的前后顺序.
2. 这种方法还是落入了不能平分负载的问题中, 因为可能actor1管理的obj群不活跃, 而actor2管理的obj群异常的活跃. 就会出现一个线程特别忙, 另一个线程闲置的状态, 在往下说, 就是有可能发生一个CPU 100%了, 另一个CPU20%, 但是游戏掉帧, 就是因为没有均摊计算量. 这也可能成为一个优点, 因为不会出现两个线程中同时处理一个obj的情况, 也就是说对obj自身来说是在单线程环境中的. 具有单线程的安全性.

改进方案
所以我们必须继续思考这个问题, 上面的第二点好解决, 可以这样

创建多个实体 …
lock oc;
activeobj GetObj() {
oc.Lock();
foreach(obj in objs) {
if (!obj.mq.empty()) {
objs.Remove(obj);
oc.Unlock();
return obj;
}
}
oc.Unlock();
return nullobj;
}

void actor() {
while (true) {
obj = GetObject();
if (obj != nullobj) {
obj.Active();
} else {
yield();
}
}
}
经过上述改动以后, 可以看到, 只要有一个线程空闲下来, 它就会去查询是否有obj存在msg等待被处理. 如果没有, 线程就短暂的休息一下. 这样的话, 计算量基本上可以实现均摊到多个线程上. 但是这种方案有明显的一个锁竞争的hot point, 就是GetObj函数中. 这里不适合用重量级的锁, 而且这里的竞争会随actor的数量上升而变得更激烈.
上面的方案算是一个解决计算分摊的办法, 但是没有解决消息的时序问题. 话说基于消息的系统成堆成堆的, 比如说日常中用到的windows系统就是基于消息驱动的, 可以从它身上学到一些东西. Windows的控件可以看做是active object, 因为它可以对你的操作进行反应, 比如你点击它, 拖动它等等, 这些都是发消息来实现的. 这里就是关键, 消息到底发给谁了
1. 从表象上来看, 因为是控件对消息产生了反应, 我们从感觉上就认为消息是发给控件的, 控件上可能有一个消息队列, 同时我们知道, 其实控件只是active obj, 它是由actor ui线程来驱动的.
2. 但是我们从资料上可以轻松找到其实控件都没有消息队列, 消息队列是和ui线程绑定在一起的:) 也就是说一个actor一个队列, 而不是说一个active obj一个队列.
我认为这windows这个消息模型是很有借鉴价值的, 应用到我们的设计中就是

可反应的实体的定义
class activeobj {
void Active(msg m) {
processMsg(m);
}
}

actor的定义
class actor {
msgqueue mq;
void Loop() {
msg m = mq.popfront();
obj = FindObj(m.t) else goto yield();
obj.Active(m);
}
}
上述机制看上去又再一次的落入任务和线程绑定的模式中, 我们还是要再次研究, 一个游戏世界中, 只有一个时间轴, 如果说每个消息都有一个时间戳的话, 那么它们应该是"先来后到"的关系, 因为我们要保证消息有序. 所以, 我们不能使用一个actor一个队列的方式, 消息队列必须是全局的, 然后又几个actor监视这个队列, 一旦有消息进入的话, 就有一个actor会取到它并去处理. 为了验证我们的想法, 我在现实中找到了这样实现的模型, 就是目前windows下最高效的IO模型完成端口, 完成端口的完成队列就相当于这里的消息队列, 而actor就是线程池, 每个actor都企图从完成队列中取一个任务来执行. 这和我们的想法是非常类似的. 所以再次修改代码:

可反应的实体的定义
class activeobj {
void Active(msg m) {
processMsg(m);
}
}

定义一个全局的消息队列
msgqueue mq;
mqlocal ml;

actor的定义
class actor {
void Loop() {
ml.lock();
msg m = mq.poptop() else goto yield();
ml.unlock();
obj = FIndObj(m);
obj->Active(m);
}
}
上面就是一个可选的方案, 首先它分摊了计算量, 计算量在msgqueue中存着, 真正的处理逻辑是在activeobj中, 而actor驱动activeobj来执行msgqueue中的消息的处理. 从设计的角度来说, 做到了职责分离. 而前面的设计中, msgqueue不是和activeobj绑定在一起, 就是和actor绑定在一起, 所以总是有一些问题, 看来还是大牛们说的对, 每个概念都单独表示, 然后通过组合把它们联系起来.
上面的这个方案好么? 首先, 我们的游戏中, 时序是非常重要的, 我们总是期望先到的消息能够先处理[因为它先产生], 所以必须有一个消息排队的地方, 所以有一个全局队列是很重要的.其次就是, 我们不期望发生一个线程很忙, 另一个很闲的情况, 使用全局msg队列就可以达到收集任务, 管理任务, 分配任务的效果, 上面这种模式就可以在大部分情况下平均分摊计算量.

总结
上面简单介绍了一个多线程方案, 我并不是直接的给出了答案, 而是记录了我在思考这个问题的过程中遇到的各种问题, 和如何解决这些问题的思路(只能说是思路:), 我认为其中最重要的部分就是:
1. 抽象应该是源于生活的, 不是空想的.
2. 对系统的看法: 一个系统之所以被划分成为一个系统, 是因为在系统中的成员的交互和联系频率要远远大于和系统外实体的交互和联系.
3. 各个系统不直接交互, 如果必须交互, 请一定走MSG
4. MSG应该维持时序性, 我这里使用的是全局MSG队列来保证时序性.
在文中讨论到最后的方案中, 任然存在着一些问题, 比如说在这种方案下, 全局的MSG队列就是唯一一个全局且高竞争数据, 这里锁的互斥是高发的, 所以在选择锁的时候需要斟酌等等, 希望能有所帮助, 欢迎大家提出更好的解决方案, 建设性的交流总是有益的:)

多线程面试题|多线程游戏服务器技术开发

http://m.quanqiunao.cn/yingjianxiangguan/4975/

推荐访问:多线程编程 多线程并发 多线程有几种实现方法 多线程和多进程的区别 多线程的实现方式 多线程的应用场景 多线程面试 多线程爬虫

手机技术推荐文章

推荐内容

上一篇:[腾讯投资了哪些公司]腾讯投资1500万元与清华大学建清华-腾讯联合实验室 下一篇:[亚马逊kindle阅读器怎么用]亚马逊Kindle阅读器 是由以色列人开发的