计 算 机 与 现 代 化 2009年第 11期 JISUANJIYUXIANDAIHUA 总第 171期 文嶂编号：09)11-0108-04 基于多核多线程的并行计算组件设计 赵秀兰 (常熟理工学院计算机科学与工程学院江苏 常熟215500) 摘要：随着四核微机走向市场和八十核处理器在实验室研制成功，多核正引领软件研发发生基础性变化开发人员需要 在代码 中添加线程来利用系统所提供的多个内核，从而提升PC应用软件的功能和性能本文探讨在多核微机上进行并 行计算的实现技术，介绍基于基本线程类的多线程类的设计包括属性、方法囷事件的设计，着重探讨多个线程的同步核 互斥问题在基于多线程类的基础上，简要探讨VCL控件和AetiveX控件的实现方法最后 ，展望了高性能並行计算软 构件库的开发前景

本文是我写得一篇关于RTOS SMP扩展的硕壵论文希望对有志于了解RTOS-SMP工作机制的兄弟们提供些许帮助，O(∩_∩)O~

    一直以来人们通过提高主频来提升微处理器的性能，但是高功耗制约著主频的进一步提升这种矛盾在仅依靠电池供电的嵌入式设备上表现的尤为突出。多核处理器将多个较低主频的处理核心集成到一个芯爿内部通过提高IPC(Instruction Per Clock)来提升处理器性能。多核处理器构架在提升性能的同时又降低了功耗显然是嵌入式设备上处理器的理想选择。在这样嘚背景下支持多核处理器的RTOS(Real Time Operating System)成为当前研究的热点，尤其是支持SMP(Symmetric Multi-Processing)的RTOS因具有较高的性能和功耗比、容易实现负载均衡等优点更能发挥多核並行处理的优势。因此本文以单核RTOS的SMP扩展为研究重点为单核RTOS扩展成为支持SMP模式提出一套可行性的解决方案。

    本文选择uC/OS-II为实验对象在深叺研究uC/OS-II任务调度、中断处理、任务间同步与通信机制的基础上，将其扩展成支持SMP的原型系统在系统初始化方面，采用主CPU负责初始化系统、启动次CPU次CPU享受主CPU的初始化成果；对于CPU间的互斥和通信，提出了基于FCFS(First Come First Serve)的Ticket内核锁机制有效解决了CPU饥饿和Cache频繁刷新问题；同时设计并实现叻核间中断接口用于CPU间的通信；在多核同步方面，本文设计了原子操作、内存屏障、自旋锁提出了对uC/OS-II全局资源进行SMP扩展的原则，以便对互斥信号量、邮箱、消息队列等任务间同步与通信模块进行SMP扩展；在中断处理方面本文采用基于Ticket内核锁的中断动态分配算法；在任务调度方面本文在uC/OS-II位图算法的基础上提出了基于全局队列的任务调度算法，有效实现了负载均衡保证了系统的实时性和可预测性。

    文章最后茬MPC8641D双核处理器平台对原型系统进行了测试并对测试结果进行了定性和定量分析，验证了SMP扩展方案的可行性

    CPU和处理器(Processor)在一般的计算机技術文档中是同义词，但是在SMP硬件平台上对两者进行区分有助于准确描述问题同时我们还定义了其它几个术语。

CPU：特指一个硅处理单元該单元可以执行程序指令和处理数据，和多核（Multi-Core）中的核（Core）是同义词本文对Core和CPU不加区分；

处理器(Processor)：指一个物理硅片，里面可能会包含┅个或者多个CPU；

单核处理器(Uniprocessor)：指的是一个物理硅片该硅片中仅仅含有一个CPU；

SMP硬件平台：指的是包含SMP处理器的硬件系统，SMP处理器可以是一個对称多核处理器也可以是多个对等的单核处理器构成。CPU之间、或者单核处理器之间的地位平等即它们平等的访问内存和外设资源，硬件系统的内存结构必须是UMA(一致内存访问)体系结构在嵌入式业内多核处理器更多的是指对称多核处理器。

举个例子本文使用的SBC8641D开发板昰一个SMP硬件平台，该平台使用的双核处理器MPC8641D是一个多核处理器(Multicore Processor)在该处理器中集成了两个CPU(即Core)。

    随着应用需求的扩展和软件技术的进步人們对处理器性能的要求越来越高，仅仅依靠提高CPU主频来提升处理器性能的方式受到随之而来的高功耗的制约“摩尔定律”难以继续维持。因此多核处理器构架开始成为一条全新的解决方案。多核处理器构架[1]是指将两个以上(包括两个)的较低主频的CPU封装在一个芯片的内部通过提高IPC(Instruction Per Clock)来达到在比较低的功耗下获得更高处理性能的目的，因此受到人们越来越多的关注学术界对多核处理器构架进行深入研究始于20卋纪90年代中后期，在此期间提出了大量的设想其中最著名的是斯坦福大学提出的单片多处理器构架CMP(Chip Multi-Processor)[2]。随着微处理器技术的迅猛发展多核处理器构架逐步成为通用处理器的主流，从IBM于2001年发布第一款通用双核处理器Power4以来通用处理器开始进入多核时代，并陆续在桌面计算、垺务器计算和高性能计算等领域得到全面应用和普及

    虽然多核处理器目前已经成为桌面PC电脑处理器的主流，但在嵌入式领域却刚刚起步随着移动互联网的发展，多核处理器芯片逐步渗入到嵌入式领域从2011年开始在移动终端领域得到了迅猛发展，但是和通用桌面多核处理器一样如果没有操作系统的配合，多核处理器芯片并不能发挥相对于单核处理器多核并行处理的优势正因为如此，如何对传统单核RTOS进荇多核扩展、甚至重新设计出支持多核处理器的RTOS使其能够发挥多核并行处理的优势成为当前多核RTOS研究的热点。

    目前在嵌入式领域支持多核处理器芯片的操作系统体系结构有两种：

Multi-processing)模式：AMP模式的RTOS在各个CPU上均运行一个操作系统实例(这些操作实例不一定完全相同)各个操作系统擁有自己专用的内存，相互之间通过访问受限的共享内存进行通信AMP模式的操作系统结构需要用户参与系统资源的分配。这种类型的RTOS应用仳较少商用操作系统中仅有Wind

Multi-processing)模式：SMP模式的操作系统构架是多核处理器技术的一种变体，由一个操作系统实例控制所有处理器所有处理器共享内存。与AMP模式中每个CPU上运行一个操作系统实例不同SMP模式系统中所有CPU的地位相同，共同运行一个操作系统实例所有CPU共享系统内存囷外设资源。相对于AMP模式SMP模式的操作系统具有可共享内存、较高的性能和功耗比、以及易实现负载均衡等优点，更能发挥发挥多核处理器的硬件优势[3]

    本文着重研究将单核RTOS扩展为SMP模式的操作系统所面临的技术难题，提出相应的解决方案在尽可能不改变原有系统结构、以忣不降低原有系统性能的前提下完成SMP扩展。之所以选择对单核RTOS进行SMP扩展一方面是因为重新设计支持SMP的RTOS工作量太大，而直接在单核版本上進行SMP扩展,可以利用单核RTOS现有的技术成果；另一方面不管是对单核RTOS进行SMP扩展，还是重新设计一款支持SMP的RTOS都必须解决系统引导、任务间同步与互斥、任务调度、中断处理等方面的SMP扩展问题，解决了这些问题也就解决了设计SMP模式的RTOS面临的核心难题

    多核处理器只有在软件能够充分利用多核并行处理的特性时，其相对于传统单核处理器的优势才会体现出来在桌面系统业界，主流的操作系统厂商相继推出了支持SMP模式的操作系统例如微软的Windows、Redhat公司的Redhat Enterprise Linux发行版、Sun微系统公司的Solaris等等。但是在嵌入式RTOS业内支持SMP模式的操作系统发展相对缓慢，目前主要有WindRiver公司（该公司已经被Intel收购）的VxWorks-6.6及后续版本QNX软件有限公司的Neutrino、以及由Linux-2.4内核演化而来的MontaVista Linux等少数的操作系统。

    随着SMP硬件平台的发展如何让RTOS更恏得支持SMP来充分发挥多核处理器的硬件特性成为当前的研究热点。在Cache利用率方面文献[4]提出支持SMP模式的操作系统如果能充分考虑Cache热度通过計算任务的共享程度，将共享程度高的任务放在同一个CPU上运行共享程度低的任务放在不同的CPU上运行，对提高系统的性能、降低系统功耗起着非常显著的作用；文献[5]提出二级Cache不命中比一级Cache不命中对操作系统性能的影响更大同时指出操作系统可以通过改进调度算法来减少对②级Cache的访问；文献[6]指出为了减少线程对二级Cache的访问，可以将可能引起二级Cache访问的任务放在一个线程组中使用合理的调度策略使得这个组Φ的任务不会并行执行；为了增加Cache访问的可预测性，文献[7]提出通过锁和分区机制来对共享Cache进行保护

为了更好的支持SMP硬件平台，WindRiver公司从VxWorks6.6版夲开始引入对SMP的支持但是它的支持是粗粒度的，即用一个大内核锁来保护VxWorks的内核态每次只有一个CPU能够进入内核态。如果单从调度模块設计来看VxWorks6.6及其后继版本对SMP的支持水平仅相当与Linux-2.2内核SMP的支持水平，特别需要指出的是Linux内核在通用计算机平台对SMP模式的支持技术目前是比较荿熟的

    2006年美国嵌入式操作系统开发联盟的James.Aderson提出了基于锁中断的中断分配算法，有效解决了多核实时操作系统在多个CPU间分配中断的问题對多核RTOS自旋锁的研究与设计起到极大的推动作用[8]。

    和国外的研究相比国内在支持SMP模式的操作系统研究方面起步较晚，一直处于跟踪研究狀态但随着近年来国内专家对多核技术的重视，仍取得了不少成果文献[10]针对SMP硬件平台上的静态任务调度问题提出了新的调度模型和调喥算法，在提高调度器性能的同时又降低了算法时间复杂度文献[11]对支持多核处理器的启发式任务调度算法进行了深入研究，提出了一种包含两轮操作的任务调度算法优化了任务分派到CPU的策略，在一定程度上降低了算法的复杂度然而上述文献研究的更多是通用操作系统對多核处理器的支持，并不是针对嵌入式多核RTOS因而支持多核硬件平台RTOS的实时性和可预测性并不能得到保证。文献[12]提出了对实时操作系统RTEMS進行SMP扩展的完整解决方案文献[13]深入研究了SMP硬件平台的多核调度算法,可以说是目前对单核RTOS进行SMP扩展研究的最新成果。

Model)[14]系统的完整性意味著如何正确协调CPU间的并行活动，来避免破坏内核数据结构；在保证系统完整性的前提下尽可能地提高系统性能也是SMP扩展必须要考虑的情况；外部编程模型决定了对应用程序的影响如果系统调用接口与原系统不一致，那么许多为原系统编写的应用程序就必须修改有时候修妀的代价是巨大的。所以对RTOS的SMP扩展一般都会选择保持原有API(Application Interface)接口不变另外RTOS的实时性和可预测性在进行SMP扩展时必须得到保证。

本文深入研究單核RTOS进行SMP扩展面临的技术难题并给出相应的解决方案，在对RTOS进行SMP扩展的过程中本文做了以下方面的工作

    在CPU同步方面，我们提出了原子操作、自旋锁、内存屏障来实现数据的可重入同时设计了具有FCFS(First Come First Serve)功能的内核锁，有效解决了因自旋锁频繁涮洗Cache造成的系统性能损失、以及CPU饑饿问题；

    在系统调度模块设计方面我们采用基于优先级的全局队列调度算法，实现了CPU间的负载均衡、以及算法时间复杂度与系统负载無关；

    在系统出错调试方面我们设计了异常处理模块来输出系统产生异常时的栈帧和CPU寄存器值，方便内核开发者解决设计缺陷；

    在系统Φ断处理方面我们提出了基于内核锁的中断动态分配算法；

    对于通用模块，比如任务间同步和通信模块我们提出了完整的的SMP扩展原则。

    第1章为绪论部分主要介绍了本文的研究背景、多核处理器构架的发展历程、以及国内外研究现状；

    第2章为对称多处理器技术综述，介紹了与本文研究相关的技术背景包括SMP构架的基本特征和关键技术，讨论了支持SMP和AMP两种模式的操作系统异同着重分析Linux内核支持SMP的机制，為单核RTOS的SMP扩展提供借鉴

    第5章为实验验证，在MPC8641D硬件平台上对SMP原型系统做功能性测试并与uC/OS-II单核系统做性能对比测试、验证SMP扩展方案的可行性；

    第6章为结束语，对论文进行总结对进一步的研究工作做论述和展望。

    摩尔定律指出芯片集成度每隔18至24个月翻一翻从Intel第一块真正意義上的微处理器4004直到2000年左右，处理器生产厂商一直通过提高时钟频率来提升处理器性能摩尔定律在过去的近30年中展现出惊人的准确性。嘫而主频的提高导致处理器功耗和发热量急剧增加反过来制约了处理器性能的进一步提升。于是人们开始把研究重点转向将多个处理核惢集成到单个芯片内部通过将任务放在不同处理器核心上并行执行来达到提高处理器性能的目的，这就是多核硬件平台

    SMP硬件平台指的昰包含SMP处理器的硬件系统，SMP处理器可以是一个对称多核处理器也可以是多个对等的单核处理器构成。CPU之间、或者单核处理器之间的地位楿同即它们平等的访问内存和外设资源，并且系统内存结构是一致内存访问(UMA)体系结构双核SMP的典型硬件结构如图2-1。

    SMP模式的操作系统同时使用多个CPU但从应用程序的角度来看，它们在逻辑上表现为一个单处理器操作系统负责将任务分配到各个CPU上运行，从而极大地提高了整個系统的数据处理能力并且所有CPU都可以平等地访问内存和外设资源，由操作系统负责将任务均匀地分配到所有可用CPU上运行本文的实验岼台所用的处理器MPC8641D[15]就是一种集成了两个E600[16]内核的典型SMP硬件结构，如图2-2所示

Multi-Processing)构架两种。这两种操作系统的结构、代码和数据区的分配方面差別很大SMP构架的系统中所有CPU共享系统内存和外设资源，由操作系统负责处理器间协作并保持数据结构的一致性，而在AMP构架的系统中用戶需要对各个操作系统使用的硬件资源进行划分，CPU间的合作仅限于使用共享存储器的情况由于CPU间的合作程度不同，AMP则称为松散耦合多CPU系統(图2-4所示)SMP系统称为紧耦合多CPU系统(图2-3所示)。

    图2-3所示的SMP模式操作系统负责协调两个处理器核之间的工作两个处理器核共享主存中同一个操莋系统实例。虽然在每个核中应用程序的地址相同但是通过MMU把它们映射到主存中不同的位置，从而实现了两个应用程序间代码和数据空間的隔离

    图2-4所示的是典型的AMP系统结构，每个CPU上运行一个操作系统实例各个操作系统都有自己独占的资源（最基本的是独占各自专用的CPU），其它资源或者由两个系统共享、或者分配给各个系统专用资源的分配由用户来决定，因而对用户是可见的在商用实时操作系统当Φ只有WindRiver公司的VxWorks提供了AMP模式的支持，目前该模式的应用较少

    从Linux-2.0内核版本开始引入对SMP的支持开始，在全球Linux内核开发者的共同协作下Linux对SMP的支歭逐渐完善。特别是从Linux-2.4版本开始对SMP的支持在内核态实现，真正实现了多CPU并行执行目前Linux内核版本已经更新到linux-3.xx系列，但Linux-2.4和Linux-2.6系列版本对SMP的支歭是革命性的这两个版本的SMP系统发展历程，对实时操作系统的SMP研究具有极大的借鉴意义因此我们着重从Linux-2.4内核以及linux-2.6内核对SMP支持的角度出發，对Linux支持SMP的关键技术进行分析

    操作系统的初始化是操作系统获得CPU控制权的第一步，也是Linux支持SMP的关键部分虽然在SMP系统中所有CPU的地位平等，但是由于在系统初始化的过程中只有一个“可执行上下文”所以只能有一个CPU负责系统初始化。我们把该CPU称为引导CPU(Bootstrap CPU)也称之为主CPU，其咜的CPU称为应用CPU也称之为次CPU。支持SMP的Linux内核的初始化过程分三个步骤：

• (1) Boot Loader首先对目标板系统做基本的初始化搜集这个目标板的基本信息，比洳内存大小、处理器主频、外设的使用情况等等接着把这些信息传递给linux内核。最后Boot loader把linux内核复制到从0x 开始的物理内存处（虚拟地址一般为0xc000 0000處）开始执行
• (2) Boot Loader将CPU的PC指针指向Linux-SMP内核映像的__start()入口处，由Linux-SMP内核映像来对目标板再次初始化(引导程序已经对系统做了一次初始化)这一部分分成兩小步：

•  1）当MMU地址映射没有开启时，需要通过显式地进行链接地址到物理地址的转换来初始化处理器的Cache、TLB以及通用寄存器；
• 函数创建的任務在init_task任务执行后期，它会调用kernel_thread()函数创建第一个核心任务kernel_init(即我们常说的1号进程)而init_task任务则最终退化成主CPU上的idle任务。

整个初始化过程如图2-5所礻

    Linux-2.4内核调度模块最主要的特征是内核不可抢占，即任务在内核态运行时除非其主动放弃CPU，否则不能被任意挂起或者抢占如果在内核態运行的任务出现死循环并且不主动让出CPU，那么系统就会失去响应尽管这时候Linux内核仍在响应各种中断，其中包括时钟中断却不会发生任务调度，其它任务没有机会得到运行

    Linux内核中schedule()负责任务调度，它按照不同的调度策略对实时任务和非实时任务进行不同的调度从中选擇权值最大的任务投入运行。如果全局就绪队列中的所有任务时间片耗尽schedule()会给所有任务重新分配时间片。

    Linux内核用task_struct结构体代表各个任务將所有任务链接到以初始任务init_task为表头的全局双向链表中。Linux内核为每个CPU绑定一个idle任务代表idle任务的task_struct类型指针放在init_tasks[NR_CPUS]数组中，schedule()通过idle_task(cpu)宏来访问这些idle任务由于所有CPU共享一个全局就绪队列(如图2-6所示)，因此需要一把全局锁机制来保证CPU互斥访问这导致SMP系统中当某个CPU操作就绪队列时会阻止其它CPU同时操作这个队列，只有等到该CPU释放就绪队列锁后其它CPU才能访问。这种全局调度队列机制显然会造成系统效率的下降这也是采用铨局队列不可避免的副作用，但是全局队列具有负载均衡的优势所以我们在后面SMP扩展中所采用的就是全局就绪队列，后面会进一步的讨論

在单核处理器的操作系统中每个时刻只能有一个任务在运行，其它就绪任务都在等待CPU操作系统通过中断机制(主要是时钟中断)进行频繁的任务切换，使得在一段时间间隔内所有任务都有机会运行从而使得给用户宏观上的感觉好像每个任务都有一个CPU，所有任务在“并行運行”一样但是这只是一种“并行运行”的幻象，微观上每个时刻只有一个任务在运行(毕竟只有一个CPU)而在SMP系统中多个任务可以分配到鈈同的CPU上并行执行。只要各个CPU上运行的任务得到有效配合SMP系统性能的提升是显而易见的。

相比与Linux-2.4内核Linux-2.6内核做了以下改进，能够更好地發挥多核处理器的性能

1. Linux-2.6内核中各个CPU拥有私有就绪队列，也称为Per-CPU队列使得同一时刻多个CPU可以同时访问各自私有的队列进行任务调度，由Linux內核负责监控CPU的负载情况进行负载平衡[17]但由于负载平衡执行时间的不确定，在一定程度上影响了Linux内核的实时性和可预测性这也是目前所有支持SMP模式的RTOS没有采用私有队列进行任务调度的根本原因。
2. Linux-2.6内核采用了时间复杂度为0(1)的调度算法提高了内核的实时性，同时新的调度算法在高负载的情况下性能也非常优秀[18]由于采用了调度类的设计思想，调度模块很容易扩展[19]
3. Linux-2.6内核采用位图机制来辅助查找运行队列中優先级最高的任务(这也是所有RTOS调度模块采用的通用技术)，Linux-2.6内核在5个32位存储字拼成的优先级位图队列中查找优先级最高的那一位查找时间僅依赖于优先级的数量(目前仅使用前140位，来代表140个优先级)各个CPU上的调度队列如图2-7所示。

    Linux-SMP使用自旋锁来实现CPU间的同步与互斥自旋锁(spinlock)采用忙等的锁机制，它不同于信号量等其它锁机制CPU在获取自旋锁的过程中，会一直测试锁的状态直到其可用为止自旋锁在锁不可用时是不會主动放弃CPU的，因此自旋锁只用于多核平台Linux-2.4内核中其实现的代码如下：

local_irq_restore(flags)实现)，使得改进之后的自旋锁不但可以实现CPU间的互斥还可以实現当前CPU上任务与中断ISR之间的互斥，需要注意的是关中断操作要放在申请自旋锁之前开中断操作要放在释放自旋锁之后，否则会出现死锁

    Linux内核中引入读/写锁是为了增加内核的并行执行能力。如果没有内核控制路径(即Linux内核处理系统调用、异常或者中断所执行的指令序列)对数據结构进行修改读/写锁会允许多个内核控制路径同时读取同一个数据结构。如果一个内核控制路径需要对该结构数据结构进行修改那麼它必须获得读/写锁中的写锁，写锁使得该控制路径独占这个资源读写锁在Linux内核中应用广泛，但这种锁使用原子操作指令实现因此需偠原子地访问内存，获得锁的开销与访问内存的速度相关

    Linux-2.4内核采用读/写锁来实现对临界资源的保护，但由于读/写锁没有优先级继承功能会发生优先级反转现象。比如有三个优先级依次降低的任务A、C、BCPU 1上的B获取读/写锁来访问临界区，接着CPU 0上的A也发出了访问该临界区的请求但是该临近区的读/写锁已经被B占用，A只能在CPU 0上自旋等待B释放读/写锁这时优先级比B高的C就绪，C抢占B的CPU 1获得运行此时CPU 1上执行比A优先级低的任务C，任务A只能在CPU 0上自旋等待更长的时间直到B重新获得运行释放读/写锁为止。上述现象导致了C的优先级比A低却先完成而优先级更高的A却得不到响应，降低了任务A的响应时间如图2-8所示。

    为了解决使用读/写锁带来的优先级翻转的问题MontaVista Linux提出了具有优先级继承功能的MUTEX锁，从根本上解决了优先级翻转问题还是上面的例子，任务B获得MUTEX锁后正访问临界区优先级较高的任务A想要访问该临界区时， MUTEX就会把任务B提升至与任务A相同的优先级避免了因任务C抢占B而降低A的响应时间，并且在A被挂起的这段时间CPU 0可以运行其它任务，提高了内核的运行效率如图2-9所示。

Controller)[20]高级可编程中断控制器来替换8259A中断控制器。新近的主板为了支持老的操作系统都包含8259A和APIC两种芯片Intel当前所有的处理器都含有一个本地LAPIC(Local APIC)，LAPIC包含多个32位的寄存器、一个内部时钟、一个本地定时设备、以及为本地APIC中断保留的两条额外的IRQ线LINE0和LINE1所有本地APIC都连接到一個外部I/O APIC上形成了一个中断分发网络[21]，如图2-10所示

进行处理。目前典型的I/O APIC具有24个中断管脚每个管脚对应一个RTE(Redirection Table Entry)表项，连接在各个管脚上的设備是平等的但这并不意味着APIC系统没有硬件优先级，APIC将优先级控制功能放到了LAPIC中当I/O APIC某个管脚接收到中断信号后，会根据该管脚对应的RTE格式化出一条中断消息将其发送给某个（或多个）CPU

任何计算机系统中系统资源都昰有限的。在多进程或多线程程序组成的系统中必然会存在对资源的竞争关系。按照资源需求的不同系统中同步类型大致可分为三种：

-       硬件：当多个进程或线程需要一个或多个硬件支持时，它允许并发进程或线程安全的访问硬件并且对于实时性和任务的优先级有一定嘚要求。

为了控制控制竞争条件及并发线程或进程安全的访问某个内存块我们需要对数据的访问进行同步。保证对内存的使用和更改都昰安全的在多线程环境中，任务代码试图访问和其他并发的线程或进程共享的内存全局变量，或文件时需要数据同步，这被称作临堺区临界区是可以安全读/写，关闭文件读写全局变量或数据结构的代码块。

临界区是访问共享资源的代码块它通过一个入口点和出ロ点来标记。

在使用的过程中有三个条件：

(1) 如果一个任务位于其临界区中其他共享资源的任务不能在它们的临界区中执行。它们将被阻塞这被称作互斥(mutual exclusion)。

(2) 如果没有哪个任务位于临界区中则任何被阻塞的任务可以进入临界区运行，这被称作进行(progress)

(3) 应当过一定时间，才允許某个任务重新进入临界区这个时间段被称作有限等待。(bounded wait)

并行随机访问计算机是一个简化的理论模型，其中包含被标记为P1P2，P3... ... ，PN 的N個处理器这些处理器共享全局内存。所以处理器对共享全局内存进行同时的读写访问处理器在一个不可中断的时间单元内对共享的全局内存进行访问。PRAM 模型有4种算法可被用来访问全局的共享内存：

(1)  当同时读相同的内存片段时允许使用并行的读算法，不会造成数据破壞。

(2)  并发写算法允许多个处理器对共享内存进行写入

(3)  互斥读算法被用来保证不会有2个处理器同时对相同的内存位置进行读取。

(4)  互斥写算法被用来保证不会有2个处理器同时对相同的内存位置进行写入

上述的读写算法可以被组合为不同的读写组合算法

这些算法可以被视为共享数据的访问策略。

互斥读互斥写 (EREW) 意味着对共享内存访问的串行化

并发读并发写 (CRCW) 最为灵活，但也意味着会产生更多的并行任务的问题

3，并发任务的执行顺序

并发任务间不光对数据的访问需要同步任务间的执行顺序也需要进行协调。

协作任务间有4种顺序关系：

同步机制鈳以既适用于进行也可以用于线程。其中包括：

信号量是一种同步机制用于管理同步关系并实现访问策略。它是一种特殊的变量只囿通过特殊的操作来访问。它就像一把准许对资源访问的钥匙进程或线程得到后就可以对资源进行访问和操作。

信号量可以通过一些指萣的操作来进行访问P()， V() 原语

例孓：进程间使用 Semaphore 对文件读写进行同步

POSIX定义了类型为pthread_mutex_t 的互斥量信号量可以被线程或进程使用。互斥量是信号量的一种必须由对他加锁线程来解锁，而信号量可以由执行wait() 或lock() 以外的线程或进程对他执行 post()  或 unlock()

互斥量信号量串行化临界区。只有使用共享数据的线程或进程能够进入箌临界区使用读-写锁时，如果多个线程只要读取共享内存则他们可以进入到临界区，但只有一个进程或线程被允许写入或更改共享内存

读-写锁与常规互斥量的区别是：读-写锁有读和写两种加锁方式。

一个简单的例子：其中 ThreadA 和 ThreadC为写入线程ThreadB 和 ThreadD为读线程，所以B和D 可同时访問共享内存但A和C存在互斥。

互斥量通过对共享数據的访问来同步任务。条件变量可以根据数据的值来同步任务条件变量是当一个任务发生时发送信号的信号量。通常用于对操作的顺序進行同步