类库大魔王
类库大魔王 懒惰,傲慢,以及无耐心

MAME的CPU调度(译)

  有好些地方看不懂,晕,凑合吧,以后如果明白了,再来改吧!更让我郁闷的是,自己的英语水平真是不敢恭维啊!其实Aaron Giles已经写得很简单了,几乎没有长句!唉!

MAME的CPU调度
by Aaron Giles

第1部分
  MAME中多CPU游戏是以循环的方式进行调度的。循环执行的顺便在机器驱动中根据CPU的顺便严格定义。没有办法改变这个顺序,然而,你可以通过挂起CPU或调整调度粒度来影响调度。那部分内容会在第2部分讨论。
  调度器依靠定时器系统工作,定时器系统知道什么时候下一个定时器被调度。所有调度都是在定时器被触发时发生。类似的,当CPU运行时,定时器从来不被触发。这点很重要。
  调度器查询定时器系统,找出什么时候下一个定时器被触发。然后它轮循每个CPU,计算CPU需要多少个时钟周期才会到达那个时刻,再运行CPU那么多个时钟周期。当CPU执行完后,CPU核心会返回实际上执行了多少个时钟周期。这些信息被累计,并转换为“本地CPU时间”,这是为了统计是否多用了CPU核心时间,或者过早退出CPU核心。
  例如我们说CPU #0是14MHz,CPU #1是2MHz。我们还说我们从0时刻(对两个CPU来说都是本地时间为0)开始,有个定时器在150ms后触发(time=0.000150)。
  循环逻辑会启动CPU #0,计算它需要多少时钟周期才能达到0.000150时刻。我们从0时刻开始,我们至少需要运行150µs。0.000150 × 14,000,000 = 2100时钟周期。它就调用CPU运行函数执行2100个时钟周期;当函数返回,它知道多少个时钟周期实际被执行了。我们假设它返回它实际运行了2112个时钟周期。(CPU核心一般会过量使用,因为很多指令会占用多于1个时钟周期。)2112个时钟周期转换为CPU #0的本地CPU时间是0.000150857(2112/14,000,000)。
  现在轮到CPU #1运行。0.000150 × 2,000,000 = 300时钟周期。所以我们调用执行(300个时钟周期)并返回300个时钟周期。CPU #1的本地时间现在是0.000150。
  现在,两个CPU都已经执行过了,它们的本地时间都大于或等于目标时间0.000150。所以调度器调用定时器系统让它处理定时器。完成后,它再次查询什么时候下一个定时器会触发。假设它很精确地在150µs后触发,time=0.000300。
  再回到调度器,我们再次启动循环。CPU #0需要运行(0.000300 – 0.000150857) × 14,000,000 = 2088时钟周期到达本地时间0.300。注意我们统计了上次执行过的所有时钟周期数。所以我们调用执行(2088),然后返回,是2091。这时本地时间就是0.000150857 + 0.000149357 = 0.000300214。
  轮到CPU #1。还是(0.000300 – 0.000150) × 2,000,000 = 300时钟周期。调用执行(300),返回302个时钟周期。记录CPU #1的本地时间是0.000150 + 0.000151 = 0.000301.
  再一次,两个CPU都已执行了,它们的本地时间都大于或等于0.000300,所以我们联系定时器系统让它运行它的定时器。这个过程贯穿了整个系统的执行。
  这里有些事要注意。第一次循环后,CPU #0的本地时间稍微比CPU #1的本地时间提前一点。经过第二次循环后,刚好相反。因此你不能保证在任何时候一个CPU会比其它的是要提前点还是延后点。
  而且,需要记住的是每个CPU有它各自的本地时间。定时器系统也会有一个“全局时间”。全局时间一般是所有CPU本地时间中最小的那个。当调用定时器系统时使用哪个时间,取决于当前哪个CPU上下文是活动状态的。如果某CPU上下文是活动的(一般只有当CPU在运行时才是;例如在读/写回调函数),然后所有定时器操作都把这个“当前时间”作为CPU本地时间,统计当前时间片内CPU执行的所有时钟周期数。如果某CPU上下文不是活动状态(所有其它时刻;例如,在定时器回调中),这时“当前时间”就是全局时间。
  全局时间在每个时间片结束,调度器调用定时器系统处理定时器前被更新,而且全局时间可用来分派定时器。
  有很多内容这篇文章没提到的,包括提前退出,挂起CPU,自旋(spinning)和让步(yielding)。下一篇文章会讲到所有相关的这些细节如果适用到定时系统中。

第2部分
  文章的第1部分讲到了MAME在运行多CPU时使用的循环调度算法的基础知识。可以总结为:
  1. 决定什么时候下一个定时器被触发
  2. 轮循每个CPU:
    1) 计算这个时间和CPU本地时间的差值
    2) 执行(消耗)这段时间
    3) 统计被执行的时钟周期,并计算CPU本地时间
  3. 返回第1步
  现在你应该能预感到接下来的事情——注意第1步要求你做的。实际上MAME中的很多事件都是周期性的可预知的,所以这个工作应该是个很好的开始。
  然而有件很常用的事件是不可预知的,就是2个CPU间的通信。实际上,这是我把定时器系统添加到MAME中的第一个地方的一个主要原因。让我们看一个例子,如果没有同步,CPU间通信就会出错。
  回到前面那个例子,有CPU #0是14MHz,CPU #1是2MHz。我们知道有个定时器每150µs被触发一次,或者说是在时刻0.000150。所以我们开始执行CPU #0共2100个时钟周期。这时,在CPU #0上运行的代码决定发送个中断信号给CPU #1在第1500个时钟周期的时候(时间点=1500/14,000,000=0.000107143)。因为没有同步机制,中断信号发送过去(一般是设置一些CPU #1的上下文状态,来指示有中断)后,CPU #0继续执行直到时间片用完。当它完成后,像前面一样,它执行了2112个时钟周期,本地时间是0.000150857。
  现在是CPU #1第一次运行。因为它注意到它有个中断,所以它应该处理中断,并继续执行剩下的时间片。
那问题是什么呢?呃,CPU #0发送中断信号在本地时间0.000107143,但CPU #1在本地时间0(就是时间片刚开始)时处理中断。假定CPU #1是个声音处理CPU;结果就是可能音乐开始得早了点。更糟糕点的,假定CPU #1正忙于处理其它事情,那时就没有机会处理中断了。可能你已经改掉了代码,或改了状态,用一种比较糟糕的方式。
  可能不太容易注意到的是,定时器系统在创建了定时器后,大部分情况下会立马触发定时器。如果你曾经在MAME中看过timer_set(TIME_NOW,…),你就已经看到了对一个定时器的请求。因为定时器是同步的障碍。整个调度算法是基于执行所有CPU直到下一个定时器触发。创建一个定时器,就是在请求调度器和定时器系统协同工作,让CPU运行到当前预定的时间直到调用你提供给它的函数。(译注:这句没看懂…)
  这又如何对上面提到的中断信号问题有所帮助呢?假定当CPU #0决定发送中断信号给CPU #1,它并不立即发送信号。它建立了一个定时器让它触发。从当前时间0.000107143才发送中断,就是定时器被触发时。但是定时器并不会触发,直到循环序列结束,而只有当所有CPU都到达那个时间才会。所以如果我们在循环结束时,它仍不会触发,因为CPU #1还在时刻0。
  这里我们有另外一个主题。CPU #0创建了个定时器,在0.000107143时刻触发,但它仍有600个时钟周期需要在时间片内执行完。我们可以让它运行完,在0.000150857时刻。但是当需要执行CPU #1,我们只有在定时器被触发时(0.000150857时刻)才会执行,这时2个CPU就完全不同步了。比起让这样的事情发生,还不如每当在某时间片内创建一个新的定时器,在时间片被用完前它就被调度触发,定时器系统和调度器协同工作中止那个CPU的执行。一般,这意味着CPU会在当前指令执行完后停止执行,并把控制权返回给调度器。
  在这种情况下,从CPU #0在该时间片内创建定时器起,从该定时器在该时间片内被调度触发起,CPU #0被中止执行,但仍有600个时钟周期剩下。调度器知道CPU #0只执行了它要求的2100个时钟周期中的1500个,并更新CPU #0的本地时间为1500 / 14,000,000 = 0.000107143。
  现在CPU #1有机会执行了。0.000107143 × 2,000,000 = 215时钟周期,所以我们执行CPU #1那么久。完成后,可能它实际执行了217个时钟周期,所以它的本地时间是0.0001085。
  全局时间被更新为所有CPU时间中最小的那个值,这里是0.000107143,并且定时器系统被要求处理定时器。这时,我们设置的该定时器的回调函数被调用,在这个回调函数中我们发送中断信号给CPU #1。
  返回到调度器,我们看一下之后仍有一个定时器被设定在0.000150时刻触发,所以计算一下CPU #0(600)的时钟周期并执行。CPU #0执行完后,我们切换到CPU #1开始执行。CPU #1现在有一个待处理的中断,但它已经在正确(或接近的,在0.0001085时刻)的本地时间接收到了中断信号,这样2个CPU间的同步就实现了。
  当CPU #1试图回访CPU #0时又发生了什么呢?请看第3部分,讲到了这个复杂主题的细节。

第3部分
  文章第2部分讨论了调度器和定时器间的协作使得事件在多CPU间进行同步。简单说来,当一个CPU需要发送事件给另一个CPU,它创建一个定时器,使得所有CPU一直执行到那个时刻。然后,定时器回调函数就被触发,事件就能安全地精确地发送过去。
  这个方案中的一个大问题是,它只有到目标CPU有个小于当前时间的本地时间时才会正常工作。我们上面看到的例子中,CPU #0发送中断信号给CPU #1。循环顺序中使得CPU #0先被执行,我们就已经保证了当CPU #0想发送信号时,它的本地时间会大于CPU #1的本地时间了。
  但是,当CPU #1想发回信号给CPU #0时,又发生了什么呢?
  采用这个天真的方案,回到我们前面那个例子,假设我们有CPU #0是14MHz,CPU #1是2MHz。有个被调度的定时器是设定在150µs后被触发,即0.000150时刻。所以我们开始执行CPU #0共2100个时钟周期,它用完时间片后,返回2112个时钟周期,意味着它的本地时间为0.000150857。
  现在我们执行CPU #1的时间片,根据第1部分中的例子,运行300个时钟周期。然而,这次在运行到第50个时钟周期时,CPU #1决定发送信号给CPU #0。所以,不是立即发送信号,而是创建个定时器,设定在50 / 2,000,000 = 0.000025时刻触发。这也有个副作用,就是中止CPU #1的执行,结束当前循环。
  这时,调度器通知定时器系统,指示全局时间需要更新为所有CPU本地时间中最小值,即0.000025。定时器系统知道后,就有个定时器被调度设定在0.000025时被触发;在回调函数中,我们就发送信号给CPU #0。
  但是等一下,CPU #0的本地时间不是已经在0.000150857时用完了么?对!这就是说,这个信号比它应该到达的时间(0.000150857 – 0.000025 = 0.000125857秒, 或1762 CPU时钟周期,太晚了)来得太迟了,我们又失去了同步。
  那我们怎么解决这个问题呢?我们需要交换执行顺序,使得调度器先执行CPU #1。但为了那样做,我们需要再一次进行预测。如果2个CPU间的通信细节已经充分理解了,并遵守这些严格的规则,应该是可以使这类调度工作正常的。到现在为止,仍然没有一个好的方案使得像这样不按顺序地运行。所以循环顺序是固定的。
  传统的在MAME中(实际上,在我写定时器系统和调度器前)这种CPU间的通信问题已经解决了,用来增加CPU间的插入因子。插入因子是一个数字,用于指示MAME中配置的为了重同步CPU间每一个视频帧需要的运行时间的频率。(这是在视频帧中指定的,因为所有在MAME中的定时都是根据已有的定时器相关的视频帧来完成的)。(译注:这段没懂…)
  插入因子在MAME的机器驱动结构中指定为全局的值。它通过计算每秒需要多少次同步(例如,某60Hz运行的游戏,插入因子为100,则暗示着每秒需要6000次同步),并简单地创建一个定时器,带一个NULL回调函数,以那个速率触发,来隐含地实现。不需要回调函数是因为不需要做任何动作;因为起码每次这个定时器的触发会使得所有CPU就在那样的速率下被同步。
  回到我们的例子,假定我们的游戏以60Hz的帧速率运行,我们使插入因子为500。那就需要确保每秒500 × 60 = 30,000次同步,或者说每0.000033333秒一次同步。这就意味着需要一个定时器设定为每0.000033333秒被触发。让我们重新评估一下发生了什么,而且为什么插入因子使一些事件得到了改善。
  记住,定时器系统指出什么时候第一个定时器被触发。前面,我们第一个定时器设定在0.000150时触发,但现在我们有了这个插入因子定时器,能更早地在0.000033333时被触发,所以决定了哪个会是第一个时间片。0.000033333 × 14,000,000 = 467时钟周期,所以我们执行CPU #0共467个时钟周期。假定它返回执行了470个时钟周期。就把本地时间更新为0.000033571。
  现在我们执行CPU #1的时间片,用新的定时器执行67个时钟周期。再一次,执行了50了时钟周期后,CPU #1决定发送个信号给CPU #0。我们创建一个定时器让它马上触发,在0.000025时刻。像以前那样,这会结束循环,并通知定时器系统。
  然而,这个时候CPU #0在0.000033571时刻收到信号,只迟了0.000008571秒或120个CPU时钟周期。相比1762个时钟周期,这是个大改进,但它仍然不够完美。通过提高插入因子,只要我们愿意,我们可以使得它做得更好。实际上,插入因子确定了从一个CPU发送信号到另一个CPU的最差情况的延迟。
  我们可以做得更好一点么?嗯,实际上,可以。如果我们创建一个定时器,以每秒2,000,000次(第2快的CPU的时钟速率)的频率运行,我们可以得到尽可能接近完美的插入因子。CPU #0从来不会执行时间长于CPU #1上的一个时钟周期,所以当CPU #1发送一个信号,它会在这个运行于CPU #1上的特定的时钟周期结束的同时触发CPU #0。
  设置高的插入因子,如在游戏的机器驱动中设置插入因子为33333。这样试一下,东东变得很慢很慢。这是因为在2个CPU间切换上下文是有代价的,当你试图创建一个定时器运行得那么频繁,你会花掉你所有的时间用于上下文切换,只有一占时间用于实际执行其它的代码。
  完美的解决方案是检测什么时候看起来CPU #1需要发送信号给CPU #0,并临时那样提高插入因子,至少那么一会儿,就可以保证同步了。这是cpu_boost_interleave函数调用的目的。它接受2个参数。第1个参数是定时器触发的频率——注意它并不在视频帧里指定,不是个绝对值。你可以传个0过去,这样系统会自动使用第2快的CPU的时钟速率,就能实现完美的同步。第2个参数指定你需要保留这个级别的插入因子多久(以秒计)。一般你不会需要它太久。
  大多数情况,MAME的游戏创建并使主CPU最先运行,并且在循环顺序中,通信是从先运行的CPU到后运行的CPU。插入因子的使用是因为从CPU需要发送回一些信息,而主CPU正好在那里等待响应。
  记住,没有一个系统是完美的,但它们已经成功地在几千种不同的平台上使用了。在第4部分,我会把这些内容连同一点关于自旋、让步和触发器一起穿起来。

第4部分
  第3部分讨论了如何解决从一个稍迟运行(在一个循环顺序中被稍迟调度)的CPU发送信号到稍早运行的CPU时调度通信问题。因为MAME不支持在循环中改变CPU运行顺序,所以唯一的改善时延的办法是提高插入因子,全局地或临时地。
  在CPU执行过程中改变调度,有2种方法。cpu_yield() 和cpu_spin()调用。过去,这2个方法都经常被滥用,因为缺少对它们实际如何工作的理解,现在是时候使这成为历史了。
  cpu_yield()做的是使当前CPU时间片提前结束。它不影响系统中的其它CPU。我们来看一个例子。
  我们再次假定有CPU #0是14MHz,CPU #1是2MHz。有个被调度的定时器设定在0.000150时刻。我们开始执行CPU #0共2100个时钟周期,但这次,在它时间片一半时(如,在第1250个时钟周期时),有个它的读/写处理函数调用了cpu_yield()。这会中止当前时间片,把CPU #0的本地时间设置为0.000089286。
  轮到CPU #1执行。一般它会执行整个时间片直到0.000150时刻;然而,因为前面的CPU过早地停止了,所以调度器只调度到前一个CPU停止执行的时刻。就是0.000089286 × 2,000,000 = 179时钟周期。假定它执行了180个时钟周期,本地时间就是0.00009。
  这时,我们告诉定时器系统全局时间是0.000089286,但是在0.000150时刻前,没有定时器会被触发,所以什么也不会发生,循环继续。
  到目前为止,所有的事都很好,但这里有个不是很明显的副作用:当cpu_yield()后,CPU会不再被调度,直到下次插入因子定时器被触发。(回忆一下上一部分,插入因子值决定了定时器以一个要求的插入因子速率被调度)就是说以后的调度周期中,CPU #0就不再配合了,直到插入因子定时器被触发,并再次允许它进行调度。
  实际上,cpu_yield()属于一组同步调用:cpu_yielduntil_trigger(), cpu_yielduntil_int(), cpu_yielduntil_time()。所有这些函数都跟cpu_yield()有相同的基本操作——它们停止当前CPU的执行,把它从调度中移除——但每一个都指定了一个不同的事件能使得CPU重要被调度。这个不被调度的CPU有一些有趣的结果。
  再看一下前面的例子,结果这些知识。为了让事情变得易于解释,我们改变情况,不调用cpu_yield(),而是调用cpu_yielduntil_time(0.00005)。这会告诉调度器不要放弃时间片,但在50ms后从调度体中移除。所以:
  CPU #0像以前那样执行,调用cpu_yielduntil_time(0.00005)后在0.000089286时刻结束时间片。中止了时间片,内部会创建一个定时器在当前本地时间(0.000089286)加0.00005秒时触发,或者说在0.000139286时刻。
  然后CPU #1执行,直到前一个CPU停止执行的时刻,即0.000089286时刻。同样,是179个时钟周期,所以我们运行CPU,它返回180个时钟周期,它的本地时间就是0.00009。
  调用定时器系统,但没有任何可以触发的,所以循环结束了。这次当我们询问定时器系统下一个定时器什么时候触发,它返回0.000139286,因为定时器由cpu_yielduntil_time()创建了。
  循环再次开始,由于CPU #0彻底从调度中移除,我们跳到CPU #1。计算时钟周期((0.000139286 –0.00009)×2,000,000)=99时钟周期。我们运行CPU #1这么多个时钟周期,返回得到101个时钟周期,把它的本地时间改为0.0001405,循环结束。
  这时,cpu_yielduntil_time()创建的定时器被触发,它使得CPU #0在下次循环中可以被调度。然后,注意2个CPU已经失去同步了。CPU #0仍然在本地时间0.000089286,CPU #1已经是0.0001405。而有个定时器设定在0.000150时触发,所以会在下次循环中使用。
  对于CPU #0,下次会执行0.000150 - 0.000089286 = 0.000060714秒,即850个时钟周期,这远远长于正常所需,因为它要一直多执行很多个时钟周期,直到那个目标时间为止。另一方面CPU #1几乎已经是在目标时间了,只需要执行19个时钟周期就到目标时间了。
  这么大的这种方式使用cpu_yielduntil_time()的副作用是你使得让步(yield)CPU在调度处理的后面了。重复使用让步调用会使得CPU越来越延后,直到导致一些奇怪的行为。例如因为CPU #0在CPU #1后的很大一段时间后才开始执行,如果它设置了一个定时器,这个定时器对于CPU #1可能就已经是在过去时了。
  类同的cpu_yield()调用是cpu_spin()调用。这些调用精确地像它们的搭档一样操作,除了自旋CPU的本地时间在每个时间片结束时是自动逼近当前全局时间的。就是说,CPU不会延后;它实际上以某种方法“烧”掉了所有剩下的时钟周期,并且自旋CPU永远不会再需要它们。
  让人迷惑的是:让步是一种同步的形式。自旋是一种hack。虽然它们看起来有点相似,但它们是用于2种不同的目的。
  有2个正统的理由来使用自旋,这是为了给那些正做着无用功的等待某些事件的游戏添加自旋循环优化。如果事件在以后一些已知的时刻会发生,就使用cpu_spinuntil_time()。如果事件是中断,就使用cpu_spinuntil_int()。如果事件是一些其它的外部驱动因子,使用cpu_spinuntil_trigger(),并在事件发生时调用cpu_trigger()。
  如果你发现你使用cpu_spin()调用来进行同步,你正屏蔽了一些其它的模拟器系统的问题。
  最后,关于触发器的一句话。触发䍛是一种简单的信号机制,用于指示一个指定的事件已经发生了。一个触发器由一个整数标记,这个整数是一个随机值,由创建/使用触发器的人选定。触发器标识没有冲突检测或分配手段(尽管可能它们需要)。为了通知触发器,你可以简单地调用cpu_trigger()带一个触发器标识。触发器大多数时候跟让步和自旋调用一起使用,让步和自旋阻塞了CPU的执行,触发器为CPU解除阻塞。没有更多的东西了。
  这里总结了我对MAME中CPU调度的讨论。如果有什么问题,我可以在稍后的第5部分回答。感谢一直读到这里——我知道,这里很多内容很难得继续跟下来。

感觉本文不错,不妨小额鼓励我一下!
支付宝扫一扫

支付宝扫一扫

微信扫一扫

微信扫一扫

如果你看不到评论框,说明Disqus被墙了。