多核并行编程的背景
在摩尔定律失效之前,提升处理器性能通过主频提升、硬件超线程等技术就能满足应用需要。随着主频提升慢慢接近撞上光速这道墙,摩尔定律开始逐渐失效,多核集成为处理器性能提升的主流手段。现在市面上已经很难看到单核的处理器,就是这一发展趋势的佐证。要充分发挥多核丰富的计算资源优势,多核下的并行编程就不可避免,Linux kernel就是一典型的多核并行编程场景。但多核下的并行编程却挑战多多。
多核并行编程的挑战
目前主流的计算机都是冯诺依曼架构,即共享内存的计算模型,这种过程计算模型对并行计算并不友好。下图是一种典型的计算机硬件体系架构。
这种架构中,有如下设计特点:
外设DMA支持直接访问主存,改善CPU使用效率;
这些硬件体系设计特点也引入很多问题,***的问题就是cache一致性问题和乱序执行问题。
cache一致性问题由cache一致性协议MESI解决,MESI由硬件保证,对软件来说是透明的。MESI协议保证所有CPU对单个cache line中单个变量修改的顺序保持一致,但不保证不同变量的修改在所有CPU上看到的是相同顺序。这就造成了乱序。不仅如此,乱序的原因还有很多:
这种情况造成,就连简单的++运算操作的原子性都无法保证。这些问题必须采用多核并行编程新的技术手段来解决。
多核并行编程关键技术
锁技术
Linux kernel提供了多种锁机制,如自旋锁、信号量、互斥量、读写锁、顺序锁等。各种锁的简单比较如下,具体实现和使用细节这里就不展开了,可以参考《Linux内核设计与实现》等书的相关章节。
锁技术虽然能有效地提供并行执行下的竞态保护,但锁的并行可扩展性很差,无法充分发挥多核的性能优势。锁的粒度太粗会限制扩展性,粒度太细会导致巨大的系统开销,而且设计难度大,容易造成死锁。除了并发可扩展性差和死锁外,锁还会引入很多其他问题,如锁惊群、活锁、饥饿、不公平锁、优先级反转等。不过也有一些技术手段或指导原则能解决或减轻这些问题的风险。
原子技术
原子技术主要是解决cache不一致性和乱序执行对原子访问的破坏问题。主要的原子原语有:
ACCESS_ONECE():只限制编译器对内存访问的优化;
barrier():只限制编译器的乱序优化;
smb_wmb():写内存屏障,刷新store buffer,同时限制编译器和CPU的乱序优化;
smb_rmb():读内存屏障,刷新invalidate queue,同时限制编译器和CPU的乱序优化;
smb_mb():读写内存屏障,同时刷新store buffer和invalidate queue,同时限制编译器和CPU的乱序优化;
atomic_inc()/atomic_read()等:整型原子操作;
多提一句的是,atomic_inc()原语为了保证原子性,需要对cache进行刷新,而缓存行在多核体系下传播相当耗时,其多核下的并行可扩展性差。
无锁技术
上一小节中所提到的原子技术,是无锁技术中的一种,除此之外,无锁技术还包括RCU、Hazard pointer等。值得一提的是,这些无锁技术都基于内存屏障实现的。
Hazard pointer主要用于对象的生命周期管理,类似引用计数,但比引用计数有更好的并行可扩展性;
RCU适用的场景很多,其可以替代:读写锁、引用计数、垃圾回收器、等待事物结束等,而且有更好的并行扩展性。但RCU也有一些不适用的场景,如写侧重;临界区长;临界区内休眠等场景。
不过,所有的无锁原语也只能解决读端的并行可扩展性问题,写端的并行可扩展性只能通过数据分割技术来解决。
数据分割技术
分割数据结构,减少共享数据,是解决并行可扩展性的根本办法。对分割友好(即并行友好)的数据结构有:
使用这些便于分割的数据结构,有利于我们通过数据分割来改善并行可扩展性。
除了使用合适的数据结构外,合理的分割指导规则也很重要:
4种分割规则中,所有权分割是分割最彻底的。
以上这些多核并行编程内容基本上涵盖了Linux kernel中所有的并发编程关键技术。当然并行编程还有很多其他技术没有应用到Linux kernel中的,如无副作用的并行函数式编程技术(Erlang/Go等)、消息传递、MapReduce等等。
11月16日,由51CTO旗下CTO训练营品牌精心打造的LeaTech全球CTO领导力峰会在北京...
机器学习作为近几年的一项热门技术,不仅凭借众多人工智能产品而为人所熟知,更...
使用3389香港服务器搭网站或多或少都会遇到一些问题,而其实很多用户对于这方面...
打热水一个APP、发学分一个APP、跑步一个APP、连无线网络一个APP、刷网课一个APP...
许多人会碰到vps和云服务器如何挑选的难题,那麼网编今日就剖析一下这二者的差别...
1.我QQ列表里人不多,能留下的都是我珍惜的。 2.是不是刘海遮住了眉毛,所以你...
【51CTO.com原创稿件】物联网技术的飞速发展让我们提前进入了万物互联的时代,给...
如今,创建和使用非结构化数据(如视频、文档、日志甚至社交媒体情绪)的应用程序...
业务中会有两种衡量标准:一种是业绩评估,另一种是情报提供。聪明的首席信息官...
如今,人工智能产业风发泉涌,随着机器学习带来算法训练的大规模应用,快速安全...