操作系统应该如何在多CPU上调度工作?

2021-03-04    分类: 网站建设

本章将介绍多处理器调度(multiprocessor scheduling)的基础知识。由于本章内容相对较深,建议认真学习并发相关的内容后再读。

过去很多年,多处理器(multiprocessor)系统只存在于高端服务器中。现在,它们越来越多地出现在个人PC、笔记本电脑甚至移动设备上。多核处理器(multicore)将多个CPU核组装在一块芯片上,是这种扩散的根源。由于计算机的架构师们当时难以让单核CPU更快,同时又不增加太多功耗,所以这种多核CPU很快就变得流行。现在,我们每个人都可以得到一些CPU,这是好事,对吧?

当然,多核CPU带来了许多困难。主要困难是典型的应用程序(例如你写的很多C程序)都只使用一个CPU,增加了更多的CPU并没有让这类程序运行得更快。为了解决这个问题,不得不重写这些应用程序,使之能并行(parallel)执行,也许使用多线程(thread,本书的第2部分将用较多篇幅讨论)。多线程应用可以将工作分散到多个CPU上,因此CPU资源越多就运行越快。

补充:高级章节

需要阅读本书的更多内容才能真正理解高级章节,但这些内容在逻辑上放在一章里。例如,本章是关于多处理器调度的,如果先学习了中间部分的并发知识,会更有意思。但是,从逻辑上它属于本书中虚拟化(一般)和CPU调度(具体)的部分。因此,建议不按顺序学习这些高级章节。对于本章,建议在本书第2部分之后学习。

除了应用程序,操作系统遇到的一个新的问题是(不奇怪!)多处理器调度(multiprocessor scheduling)。到目前为止,我们讨论了许多单处理器调度的原则,那么如何将这些想法扩展到多处理器上呢?还有什么新的问题需要解决?因此,我们的问题如下。

关键问题:如何在多处理器上调度工作

操作系统应该如何在多CPU上调度工作?会遇到什么新问题?已有的技术依旧适用吗?是否需要新的思路?

空间局部性。时间局部性是指当一个数据被访问后,它很有可能会在不久的将来被再次访问,比如循环代码中的数据或指令本身。而空间局部性指的是,当程序访问地址为x

的数据时,很有可能会紧接着访问x

周围的数据,比如遍历数组或指令的顺序执行。由于这两种局部性存在于大多数的程序中,硬件系统可以很好地预测哪些数据可以放入缓存,从而运行得很好。

有趣的部分来了:如果系统有多个处理器,并共享同一个内存,如图10.2所示,会怎样呢?



图10.1 带缓存的单CPU


图10.2 两个有缓存的CPU共享内存

事实证明,多CPU的情况下缓存要复杂得多。例如,假设一个运行在CPU 1上的程序从内存地址A读取数据。由于不在CPU 1的缓存中,所以系统直接访问内存,得到值D

。程序然后修改了地址A处的值,只是将它的缓存更新为新值D'

。将数据写回内存比较慢,因此系统(通常)会稍后再做。假设这时操作系统中断了该程序的运行,并将其交给CPU 2,重新读取地址A的数据,由于CPU 2的缓存中并没有该数据,所以会直接从内存中读取,得到了旧值D

,而不是正确的值D'

。哎呀!

这一普遍的问题称为缓存一致性(cache coherence)问题,有大量的研究文献描述了解决这个问题时的微妙之处[SHW11]。这里我们会略过所有的细节,只提几个要点。选一门计算机体系结构课(或3门),你可以了解更多。

硬件提供了这个问题的基本解决方案:通过监控内存访问,硬件可以保证获得正确的数据,并保证共享内存的唯一性。在基于总线的系统中,一种方式是使用总线窥探(bus snooping)[G83]。每个缓存都通过监听链接所有缓存和内存的总线,来发现内存访问。如果CPU发现对它放在缓存中的数据的更新,会作废(invalidate)本地副本(从缓存中移除),或更新(update)它(修改为新值)。回写缓存,如上面提到的,让事情更复杂(由于对内存的写入稍后才会看到),你可以想想基本方案如何工作。


一段时间后,假设每个工作依次执行一个时间片,然后选择另一个工作,下面是每个CPU可能的调度序列:



由于每个CPU都简单地从全局共享的队列中选取下一个工作执行,因此每个工作都不断在不同CPU之间转移,这与缓存亲和的目标背道而驰。

为了解决这个问题,大多数SQMS调度程序都引入了一些亲和度机制,尽可能让进程在同一个CPU上运行。保持一些工作的亲和度的同时,可能需要牺牲其他工作的亲和度来实现负载均衡。例如,针对同样的5个工作的调度如下:



这种调度中,A、B、C、D 这4个工作都保持在同一个CPU上,只有工作E不断地来回迁移(migrating),从而尽可能多地获得缓存亲和度。为了公平起见,之后我们可以选择不同的工作来迁移。但实现这种策略可能很复杂。

我们看到,SQMS调度方式有优势也有不足。优势是能够从单CPU调度程序很简单地发展而来,根据定义,它只有一个队列。然而,它的扩展性不好(由于同步开销有限),并且不能很好地保证缓存亲和度。

10.5 多队列调度

正是由于单队列调度程序的这些问题,有些系统使用了多队列的方案,比如每个CPU一个队列。我们称之为多队列多处理器调度(Multi-Queue Multiprocessor Scheduling,MQMS)

在MQMS中,基本调度框架包含多个调度队列,每个队列可以使用不同的调度规则,比如轮转或其他任何可能的算法。当一个工作进入系统后,系统会依照一些启发性规则(如随机或选择较空的队列)将其放入某个调度队列。这样一来,每个CPU调度之间相互独立,就避免了单队列的方式中由于数据共享及同步带来的问题。

例如,假设系统中有两个CPU(CPU 0和CPU 1)。这时一些工作进入系统:A、B、C和D。由于每个CPU都有自己的调度队列,操作系统需要决定每个工作放入哪个队列。可能像下面这样做:



根据不同队列的调度策略,每个CPU从两个工作中选择,决定谁将运行。例如,利用轮转,调度结果可能如下所示:



MQMS比SQMS有明显的优势,它天生更具有可扩展性。队列的数量会随着CPU的增加而增加,因此锁和缓存争用的开销不是大问题。此外,MQMS天生具有良好的缓存亲和度。所有工作都保持在固定的CPU上,因而可以很好地利用缓存数据。

但是,如果稍加注意,你可能会发现有一个新问题(这在多队列的方法中是根本的),即负载不均(load imbalance)。假定和上面设定一样(4个工作,2个CPU),但假设一个工作(如C)这时执行完毕。现在调度队列如下:



如果对系统中每个队列都执行轮转调度策略,会获得如下调度结果:



从图中可以看出,A获得了B和D两倍的CPU时间,这不是期望的结果。更糟的是,假设A和C都执行完毕,系统中只有B和D。调度队列看起来如下:



因此CPU使用时间线看起来令人难过:



所以可怜的多队列多处理器调度程序应该怎么办呢?怎样才能克服潜伏的负载不均问题,打败邪恶的……霸天虎军团[1]

?如何才能不要问这些与这本好书几乎无关的问题?

关键问题:如何应对负载不均

多队列多处理器调度程序应该如何处理负载不均问题,从而更好地实现预期的调度目标?

最明显的答案是让工作移动,这种技术我们称为迁移(migration)。通过工作的跨CPU迁移,可以真正实现负载均衡。

来看两个例子就更清楚了。同样,有一个CPU空闲,另一个CPU有一些工作。



在这种情况下,期望的迁移很容易理解:操作系统应该将B或D迁移到CPU0。这次工作迁移导致负载均衡,皆大欢喜。

更棘手的情况是较早一些的例子,A独自留在CPU 0上,B和D在CPU 1上交替运行。



在这种情况下,单次迁移并不能解决问题。应该怎么做呢?答案是不断地迁移一个或多个工作。一种可能的解决方案是不断切换工作,如下面的时间线所示。可以看到,开始的时候A独享CPU 0,B和D在CPU 1。一些时间片后,B迁移到CPU 0与A竞争,D则独享CPU 1一段时间。这样就实现了负载均衡。



当然,还有其他不同的迁移模式。但现在是最棘手的部分:系统如何决定发起这样的迁移?

一个基本的方法是采用一种技术,名为工作窃取(work stealing)[FLR98]。通过这种方法,工作量较少的(源)队列不定期地“偷看”其他(目标)队列是不是比自己的工作多。如果目标队列比源队列(显著地)更满,就从目标队列“窃取”一个或多个工作,实现负载均衡。

当然,这种方法也有让人抓狂的地方——如果太频繁地检查其他队列,就会带来较高的开销,可扩展性不好,而这是多队列调度最初的全部目标!相反,如果检查间隔太长,又可能会带来严重的负载不均。找到合适的阈值仍然是黑魔法,这在系统策略设计中很常见。

10.7 小结

本章介绍了多处理器调度的不同方法。其中单队列的方式(SQMS)比较容易构建,负载均衡较好,但在扩展性和缓存亲和度方面有着固有的缺陷。多队列的方式(MQMS)有很好的扩展性和缓存亲和度,但实现负载均衡却很困难,也更复杂。无论采用哪种方式,都没有简单的答案:构建一个通用的调度程序仍是一项令人生畏的任务,因为即使很小的代码变动,也有可能导致巨大的行为差异。除非很清楚自己在做什么,或者有人付你很多钱,否则别干这种事。

网页题目:操作系统应该如何在多CPU上调度工作?
文章起源:https://www.cdcxhl.com/news/104103.html

成都网站建设公司_创新互联,为您提供网站排名商城网站响应式网站网站制作Google软件开发

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

成都定制网站网页设计