多核多线程技术

1、多核程序设计,参考资料： 1. 多核系列教材编写组.多核程序设计.清华大学出版社(第7版),2007.9 2. David B.Kirk,Wen-mei W.Hwu著.陈曙晖,熊淑华译.大规模并行处理器编程实践.清华大学出版社,2010.9 3. Maurice Herlihy,Nir Shavit著.金海,胡侃译.多处理器编程的艺术.机械工业出版社,2009.8 4. Richard Gerber, Aart J.C.Bik, Kevin B.Smith等著, 王涛,单久龙,孙广中译.软件优化技术IA-32平台的高性能手册(第2版) .电子工业出版社,2007.4,多核程序设计,电子书及资料

2、下载：,多核程序设计,第一章 多核技术导论,微处理器发展史,1945年，世界上第一台全自动电子数字计算机ENIAC 计算机的发展按照硬件工艺可以分为 第一代（19461958）：电子管数字计算机。 第二代（19581964）：晶体管数字计算机。 第三代（19641971）：集成电路数字计算机。 第四代(1971年以后）：大规模集成电路数字计算机。 微处理器 第一代微处理器(4位)：英特尔4004,8008 第二代微处理器(8位)：采用NMOS工艺,采用汇编语言、BASIC、Fortran编程，使用单用户操作系统。如英特尔8080,8085。 第三代微处理器(16位)：以1978年英特尔的808

3、6出现为起点。 第四代微处理器(32位)：运算模式包括实模式、保护模式和“虚拟86”。英特尔80386 DX, 80486, Pentium 4,并行计算机,由一组处理单元组成，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。 出现背景: 60年代初期，晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。出现规模不大的共享存储多处理器系统，即大型主机（典型代表：IBM360）。 60 年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了，在处理器内部的应用大大提高了并行计算机系统的性能。 两个最主要的组成部分 计算节点

4、节点间的通信与协作机制,并行计算机的弗林分类,Flynn根据指令流和数据流的不同组织方式，把计算机系统的结构分为以下四类： 单指令流单数据流（Single Instruction stream Single Data stream, SISD） 单指令流多数据流（Single Instruction stream Multiple Data stream, SIMD） 多指令流单数据流（Multiple Instruction stream Single Data stream, MISD） 多指令流多数据流（Multiple Instruction stream Multiple Data

5、stream, MISD）,并行计算机从系统结构角度分类,分布式存储器的SIMD处理机 含有多个同样结构的处理单元（PE），通过寻径网络以一定方式互相连接。每个PE有各自的本地存储器（LM）。 向量超级计算机（共享式存储器SIMD） 集中设置存储器，共享的多个并行存储器通过对准网络与各处理单元PE相连。在处理单元数目不太大的情况下很理想。 对称多处理器（SMP） 一个计算机上汇集了一组处理器，各处理器之间共享内存子系统以及总线结构。 并行向量处理机（PVP） 使用定制的高带宽网络将向量处理器连向共享存储器模块 使用大量的向量寄存器和指令缓冲器 集群计算机 由许多连在一起的独立计算机组成，像一个

6、单独集成的计算机资源一样协同工作，用来解决大型计算问题。,片上多核处理器架构,片上多核处理器（Chip Multi-Processor，CMP）就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。 按计算内核的对等与否，CMP可分为同构多核和异构多核 CPU核心数据共享与同步的通信机制： 总线共享Cache结构：每个CPU内核拥有共享的二级或三级Cache，用于保存比较常用的数据，并通过连接核心的总线进行通信。 基于片上互连的结构：每个CPU核心具有独立的处理单元和Cache，各个CPU核心通过交叉开关或片上网络等方式连接在一起。 给程序开发者带来的挑战,典型多核芯片架构,芯片组对多核

7、的支持固件,固件是一种嵌入到硬件设备中的软件。它通常烧写在flash等介质中，可以被当作一个二进制映像文件由用户从硬件设备中调用。 固件是在集成电路只读存储器中的计算机程序，是可擦写可编程芯片，其上的程序可以通过专门的外部硬件进行修改，但是不能被一般的应用程序改动。,芯片组对多核的支持固件(续),BIOS（Basic Input/Output System） 作为系统硬件和操作系统之间的抽象层，主要用来初始化和配置系统的硬件，启动操作系统以及提供对系统设备底层的通讯。 BIOS是连接CPU、芯片组和操作系统的固件，是IBM兼容计算机中启动时调用的固件代码。 由两部分组成:上电自举即POST（P

8、ower On Self Test）和在线的中断服务（主要由legacy 操作系统使用）。 计算机加电时BIOS从flash、PROM或是EPROM中启动并完成初始化，进行加电自检，对硬盘，内存，显卡，主板等硬件进行扫描检查，然后它将自己从BIOS内存空间中解压到系统的内存空间中，并开始从那里运行。 正在被以EFI（Extensible Firmware Interface，可扩展固件接口）为代表的新一代技术所取代。,芯片组对多核的支持固件(续2),EFI（可扩展固件接口） 在操作系统与平台固件之间的软件接口。 EFI规范定义的接口包括包含平台信息的数据表和启动时及启动后的服务。 EFI启动管

9、理器被用来选择装载操作系统，不再需要专门的启动装载器机制辅助。 Framework是一种固件的架构，它是EFI固件接口的一种实现，用来完全替代传统的BIOS。,EFI对多核支持,在Framework中定义了两类处理器 BSP（boot strap processor），执行EFI的初始化代码，设置APIC环境，建立系统范围的数据结构，开始并初始化AP。 AP （application processor），在系统上电或重启之后，AP会自己进行一个简单的设置，然后就等待BSP发出Startup信号。 Framework在多核计算机中初始化过程如下： SEC：从实模式切换到保护模式，处理不同的重启

10、事件、对每个处理器进行缓存设置。 PEI：做尽量少的硬件初始化，而把更多的留给DXE。 DXE：对所有可用的硬件设备进行初始化，为建立控制台和启动操作系统提供必要的服务。 BDS：建立所需的控制台设备，在输出控制台上显示用户界面。 当系统最后选择启动到操作系统时，EFI需要提交包括处理器在内的有关信息。,操作系统对多核处理器的支持方法,调度与中断 对任务的分配进行优化。使同一应用程序的任务尽量在一个核上执行。 对任务的共享数据优化。由于CMP体系结构共享二级缓存，可以考虑改变任务在内存中的数据分布，使任务在执行时尽量增加二级缓存的命中率。 对任务的负载均衡优化。当任务在调度时，出现了负载不均衡

11、，考虑将较忙处理器中与其他任务最不相关的任务迁移，以达到数据的冲突量小。 输入输出系统 多核体系处理器中，必须将中断处理分发给一组核处理。 存储管理与文件系统 库函数做成非阻塞调用方式（需要保证数据同步的机制） 使用多线程内存分配,操作系统对多核处理器的支持方法,多核程序设计,第二章 并行计算基础,并行计算机体系结构,组成并行计算机的各个部分： 节点（node） 互联网络（interconnect network） 内存 （memory）,内存模块与节点分离,内存模块位于节点内部,多级存储体系结构,为了解决内存墙（memory wall）性能瓶颈问题。 在节点内部的cache称为二级cache

12、（L2 cache）。 在处理器内部更小的cache成为一级cache（L1 cache）。 L1 cache连接CPU寄存器和L2 cache，负责缓存L2 cache中的数据到寄存器中。,多级存储体系结构,并行计算机的多级存储结构主要包括两个问题： Cache的映射策略，即cache如何从内存中取得数据进行存储； 节点内部或者节点之间内存的访问模式 。 cache原理 cache以cache线为基本单位，每条cache包含L个字，每个字8个字节。例如，L=4，则表示cache线包含4*8=32个字节。内存空间分割成块（block），每个块大小与cache线长度一致，数据在内存和cache之

13、间的移动以cache线为基本单位 。 For i =1 to M Ai = Ai + 2 * Bi 如果操作数存在cache中，称该次访问是命中的，否则，该次操作是“扑空”的 。,无Cache，访问内存2M次；有cache，访问内存2M/L次,多级存储体系结构,cache的映射策略指的是内存块和cache线之间如何建立相互映射关系。 直接映射策略（direct mapping strategy） 每个内存块只能被唯一的映射到一条cache线中 K路组关联映射策略 （K-way set association mapping strategy） Cache被分解为V个组，每个组由K条cache线

14、组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一条cache线。 全关联映射策略 （full association mapping strategy） 内存块可以被映射到cache中的任意一条cache线。,并行计算机访存模型,UMA（Uniform Memory Access）模型 物理存储器被所有节点共享； 所有节点访问任意存储单元的时间相同； 发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等； 各节点的CPU可带有局部私有高速缓存； 外围I/O设备也可以共享，且每个节点有平等的访问权利。 NUMA（Non-Uniform Memory Acces

15、s）模型 物理存储器被所有节点共享，任意节点可以直接访问任意内存模块； 节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的3倍以上； 发生访存竞争时，仲裁策略对节点可能是不等价的； 各节点的CPU可带有局部私有高速缓存 （cache）； 外围I/O设备也可以共享，但对各节点是不等价的。,并行计算机访存模型,COMA（Cache-Only Memory Access）模型 各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间 利用分布的高速缓存目录D进行远程高速缓存的访问 COMA中的高速缓存容量一般都大于2级高速缓存容量 使用COMA时，数据开始时可以任意

16、分配，因为在运行时它最终会被迁移到要用到它的地方 NORMA（No-Remote Memory Access）模型 所有存储器都是私有的； 绝大多数NORMA都不支持远程存储器的访问； 在DSM中，NORMA就消失了。,并行计算机访存模型,并行计算机系统的不同访存模型分类,并行计算模型,SIMD同步并行计算模型 共享存储的SIMD模型（PRAM模型） PRAM，Parallel Random Access Machine 分布存储的SIMD模型（SIMD互联网络模型） MIMD异步并行计算模型 异步PRAM模型 BSP模型 LogP模型 C3模型,SIMD同步并行计算模型,SIMD共享存储模型

17、（PRAM模型） PRAM-EREW （Exclusive-Read and Exclusive-Write），不允许同时读和同时写 PRAM-CREW （Concurrent-Read and Exclusive-Write） ，允许同时读但不允许同时写 PRAM-CRCW （Concurrent-Read and Concurrent-Write） ，允许同时读和同时写 优点： 适合于并行算法的表达、分析和比较； 使用简单，很多诸如处理器间通信、存储管理和进程同步等并行计算机的低级细节均隐含于模型中； 易于设计算法和稍加修改便可运行在不同的并行计算机上； 有可能加入一些诸如同步和通信等需要

18、考虑的方面。,SIMD分布存储模型,采用一维线性连接的SIMD模型，简记为SIMD-LC 采用网孔连接的SIMD模型，简记为SIMD-MC 采用树形连接的SIMD模型，简记为SIMD-TC 采用树网连接的SIMD模型，简记为SIMD-MT 采用立方连接的SIMD模型，简记为SIMD-CC 采用立方环连接的SIMD模型，简记为SIMD-CCC 采用洗牌交换连接的SIMD模型，简记为SIMD-SE 采用蝶形连接的SIMD模型，简介为SIMD-BF 采用多级互联网络连接的SIMD模型，简记为SIMD-MIN,MIMD异步计算模型APRAM模型,APRAM特点: 每个处理器都有其本地存储器、局部时钟和

19、局部程序 处理器间的通信经过共享全局存储器 无全局时钟，各处理器异步地独立执行各自的指令 处理器任何时间依赖关系需明确地在各处理器的程序中加入同步（路）障（Synchronization Barrier） 一条指令可在非确定但有限的时间内完成。 APRAM模型中有四类指令: 全局读，将全局存储单元中的内容读入本地存储器单元中 局部操作，对本地存储器中的数执行操作，其结果存入本地存储器中 全局写，将本地存储器单元中的内容写入全本地存储器单元中 同步，同步是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序,MIMD异步计算模型BSP模型,大同步并行BSP (Bulk

20、 Synchronous Parallel) 模型作为计算机语言和体系结构之间的桥梁，由以下述三个参数描述分布存储的并行计算机模型： 处理器/存储器模块（下文简称处理器） 处理器模块之间点到点信息传递的路由器 执行以时间间隔L为周期的路障同步器 特点： 将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅施行点到点的消息传递，不提供组合、复制或广播等功能，这样做既掩盖了具体的互联网络拓扑，又简化了通信协议 采用路障方式的以硬件实现的全局同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员并无过分的负担 在分析BSP模型的性能时，假定局部操作可在一个时间步内

21、完成，而在每一超级步中，一个处理器至多发送或接受h条消息（h-relation）,MIMD异步计算模型LogP,C3模型,LogP模型是一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来描述，但它并不涉及到具体的网络结构，也不假定算法一定要用显式的消息传递操作进行描述。 L:Latency, 表示消息从源到目的在网络上的延迟 o:overhead, 表示处理器发送或接收一条消息消耗在网络协议栈中的开销 g:gap,表示处理器可连续进行消息发送或接收的最小时间间隔 P:Processor, 表示处理器/存储模块数 1/g 对应于处理器带宽,MIMD异步计算模型LogP,C3模型,

22、C3（Computation, Communication, Congestion）模型是一个与体系结构无关的粗粒度的并行计算模型，旨在能反映计算复杂度，通信模式和通信期间潜在的拥挤等因素对粗粒度网络算法的影响。 C3模型强调用共用的通信操作来开发粗粒度的并行算法 BSP、LogP模型采用点到点的消息传递来进行通信，复杂的通信操作由编程实现,并行编程环境,比较流行的并行编程环境主要有3类：消息传递、共享存储和数据并行： 共享存储并行编程基于线程级细粒度并行，可移植性不如消息传递并行编程，但是，由于他们支持数据的共享存储，所以并行编程的难度较小，但一般情况下，当处理机个数较多时，其并行性能明显不

23、如消息传递编程 ； 消息传递并行编程基于大粒度的进程级并行，具有最好的可扩展性，几乎被所有当前流行的各类并行计算机所支持，其具有较好的可扩展性，但是，消息传递并行编程只能支持进程间的分布式存储模式，即各个进程只能支持访问其局部内存空间，而对其他进程的局部内存空间的访问只能通过消息传递来实现，因此，学习和使用消息传递并行编程的难度均大于共享存储和数据并行这两种编程模式。,并行编程环境,比较流行的并行编程环境主要有3类：消息传递、共享存储和数据并行,编程语言与编译器,在科学计算领域对并行编程支持已经取得相当成功的三项技术： 自动并行化 数据并行语言HPF 共享存储并行编程接口OpenMP,编程语言

24、与编译器,自动并行 始于20世纪70年代的自动向量化。 20世纪80年代中期，基于依赖分析的向量化工具成熟，成为向量机的标准。 自动化并行本身不足以解决并行程序设计问题。 此领域的研究重点逐步转向基于语言的策略研究，即从用户那里获得更多的信息，同时利用自动并行化技术来减轻程序设计的负担。,编程语言与编译器,数据并行编程：HPF 高性能Fortran(HPF)的思想是使数据管理的多数细节自动并行化 HPF提供了一个指令集，通过注释形式的指令来扩展变量类型的说明，能够对数组的数据布局进行相当详细的控制。 对显式并行机制的说明相当有限，通过系统而非程序员把任务分配给处理机。,编程语言与编译器,共享存

25、储并行编程：OpenMP 由Silicon Graphics领导的工业协会推出了OpenMP 是一个与Fortran77和C语言绑定的并行编程接口 OpenMP指令在单机编译器上被当作注释而忽略 通过parallel section 指令获得任务并行 #pragma omp parallel for 提供了锁变量用于线程间细粒度同步 是适合于具有一致性访存的共享存储计算机的编程接口,并行计算性能评测,并行程序执行时间 从并行程序开始执行到所有进程执行完毕，墙上时钟走过的时间，也称为墙上时间 （wall clock time）。 加速比性能定律 Amdahl定律 Gustafson定律 Sun和

26、Ni定律 并行程序性能评价方法 浮点峰值性能与实际浮点性能 峰值性能等于CPU内部浮点乘加指令流水线条数、每条流水线每个时钟周期完成的浮点运算次数、处理器主频三者的乘积 实际浮点性能等于并行程序的总的浮点运算次数和并行程序执行时间的比值 数值效率和并行效率,并行计算性能评测,并行程序执行时间 对各个进程，墙上时间可进一步分解为计算CPU时间、通信CPU时间、同步开销时间、同步导致的进程空闲时间 计算CPU时间：进程指令执行所花费的CPU时间，包括程序本身的指令执行占用的时间和系统指令花费的时间； 通信CPU时间：进程通信花费的CPU时间； 同步开销时间：进程同步花费的时间； 进程空闲时间：进程

27、空闲时间是指并行程序执行过程中，进程所有空闲时间总和（如进程阻塞式等待其他进程的消息时。此时CPU通常是空闲的，或者处于等待状态）,并行计算性能评测,加速比性能定律Amdahl定律 能够计算并行程序相对于最优串行算法在性能提升上的理论最大值他将程序划分为可加速与不可加速两大部分，程序总的加速比是一个关于程序中这两部分所占比例以及可加速部分性能加速程度的函数 Amdahl定律: f 表示执行程序中串行部分的比例，p表示处理器核的数量。假设最优串行算法的执行时间为一个单位时间（也就是分子为1）。 处理器核在数量上能够无限制的增加，但是无限的处理器核却并不能带来性能上的无限增长，无论如何，程序性能上

28、的总是有个上限，这个要受限于串行部分所占的比例。,程序性能优化,串行程序性能优化 是并行程序性能优化的基础，一个好的并行程序首先应该拥有良好的单机性能，影响程序单机性能的主要因素是程序的计算流程和处理器的体系结构 调用高性能库，比如优化的BLAS，FFTW等 选择适当的编译器优化选项 合理定义数组维数 注意嵌套循环的顺序，尽量改善数据访问的局部性 通用的原则就是尽量使最内层循环的数据访问连续进行 循环展开,DO I=1, N D=D+A(I) ENDDO,DO I=1, MOD(N, 4) D=D+A(I) ENDDO DO I=MOD(N, 4)+1, N, 4 D=D+A(I) +A(I+

29、1) +A(I+2) +A(I+3) ENDDO,程序性能优化,并行程序性能优化 最主要的是选择好的并行算法和通信模式 减少通信量、提高通信粒度 提高通信粒度的有效方法就是减少通信次数，尽可能将可以一次传递的数据合并起来一起传递 全局通信尽量利用高效集合通信算法 对于标准的集合通信，如广播、规约、数据散发与收集等，尽量调用MPI标准库函数 挖掘算法的并行度，减少CPU空闲等待 具有数据相关性的计算过程会导致并行运行的部分进程空闲等待.在这种情况下，可以考虑改变算法来消除数据相关性,程序性能优化,并行程序性能优化 负载平衡 动态调整负载时要考虑负载调整的开销及由于负载不平衡而引起的空闲等待对性能

30、的影响，寻找最优负载调整方案 通信、计算的重叠 让通信和计算重叠进行，利用计算时间来屏蔽通信时间。实现方法一般基于非阻塞通信，先发出非阻塞的消息接受或发送命令，然后处理与收发数据无关的计算任务，完成计算后再等待消息收发的完成。 通过引入重复计算来减少通信，即以计算换通信 由于当前大部分并行计算机的计算速度远远大于通信速度，并且在一些情况下，当一个进程计算时，别的进程往往处于空闲等待状态，因而适当引入重复计算可以提高程序的总体性能,并行编译器,并行编译器大致由三部分组成： 流分析 确定源代码中数据和控制的相关性 程序优化 将代码变换成与之等效的的更好形式，以挖掘硬件潜力 代码生成 将代码从一种描

31、述转换成另一种中间形式的描述,并行编译器,并行编译过程,并行编译器,流分析 要使程序并行地执行，首先要进行相关性分析（Dependency Analysis） 四种相关形式： 流相关：从SiSj存在执行通路，且Si至少有一个输出被用作Sj的输入 反相关：Sj紧接Si，且Sj的输出被作为Si的输入 输出相关：两条语句往相同的变量里写 控制相关：语句Sj的执行与否依赖于语句Si,并行编译器,代码优化 代码向量化（Code Vectorization）: 把标量程序中的由一种可向量化循环完成的操作变换成向量操作。 代码并行化（Code Parallelization）:并行代码的优化是将一个程序展开

32、成多线程以同时供多台处理机并行执行，其目的是要减少总的执行时间。 代码生成 并行代码生成（Code Generation）涉及到将优化后的中间形式的代码转换程可执行的具体的机器目标代码。包括执行次序、指令选择、寄存器分配、负载平衡、并行粒度、代码调度以及后优化（Postoptimization）等问题。,多核程序设计,第三章 线程的基本概念,进程,定义：进程是具有一定独立功能的程序关于一个数据集合的一次运行活动。可表示成四元组（P, C, D, S），其中P是程序代码，C是进程的控制状态，D是进程的数据，S是进程的执行状态。 状态： 运行态(Run): 进程占有处理机资源, 正在运行; 就绪态

33、(Ready): 进程本身具备运行条件, 但由于处理机的个数少于可运行进程的个数, 暂未投入运行; 等待态(Wait): 进程本身不具备运行条件，即使分给它处理机也不能运行. 进程正等待某一个事件的发生, 如等待某一资源被释放，等待与该进程相关的I/O传输的完成信号等。,进程,状态间转换 当一个就绪进程获得处理机时, 其状态由就绪变为运行； 当一个运行进程被剥夺处理机时, 其状态由运行变为就绪； 当一个运行进程因某事件受阻时, 如所申请资源被占用, 启动I/O传输未完成, 其状态由运行变为等待； 当所等待事件发生时, 如得到申请资源, I/O传输完成, 其状态由等待变为就绪。,进程,进程控制块

34、(Process Control Block，PCB):标志进程存在的数据结构，其中包含系统对进程管理需要的全部信息。,进程标识 用户标识 进程状态 调度参数 现场信息 家族联系 程序地址 当前打开文件 消息队列指针 资源使用情况 进程队列指针,进程,进程的组成 进程控制块：由于进程控制块中包含程序的地址信息，通过它可以找到程序在内存或外存的存放地址，也就找到了整个进程. PCB存于系统空间，只有操作系统能够对其存取，用户程序不能访问. 实际上用户甚至感觉不到PCB的存在； 程序：进程的“躯体”，其中包括代码和数据两个部分. 现代操作系统都支持程序共享的功能，这就要求代码是“纯”的，即在运行期

35、间不修改自身。数据一般包括静态变量、动态堆和动态栈。,进程,进程的表示,PCB,程序,PCB,代码,数据 + 堆栈,系统空间,用户空间,（a）,（b）,进程,进程的队列 为实现对进程的管理，系统需要按照某种策略将进程排成若干队列，由于PCB是进程的代表，因而进程队列实际上是由进程PCB构成的队列. 因为该队列通常由链的形式实现的，所以也称PCB链 。系统中的进程队列分为如下三类：就绪队列 、等待队列、运行队列。,进程,进程的队列 就绪队列 整个系统一个. 所有处于就绪状态的进程按照某种组织方式排在这一队列中. 等待队列 每个等待事件一个，当进程等待某一事件时，进入与该事件相关的等待队列中；当某

36、事件发生时，与该事件相关的一个或多个进程离开相应的等待队列，进入就绪队列. 运行队列 在单CPU系统中只有一个，在多CPU系统中每个CPU各有一个，每个队列中只有一个进程，指向运行队列头部的指针被称作运行指示字.,进程,进程的类型 系统进程 运行操作系统程序，完成操作系统的某些功能； 用户进程运行用户程序，直接为用户服务。 进程的特性 并发性：与其它进程一道在宏观上同时向前推进 ； 动态性：进程是执行中的程序. 此外进程的动态性还体现在如下两个方面：首先，进程是动态产生、动态消亡的；其次，在进程的生存期内，其状态处于经常性的动态变化之中 ； 独立性：进程是调度的基本单位，它可以获得处理机并参与

37、并发执行 ； 交往性：进程在运行过程中可能会与其它进程发生直接或间接的相互作用 ； 异步性：每个进程都以其相对独立、不可预知的速度向前推进 ； 结构性：每个进程有一个控制块PCB 。,进程,两个特征 资源特征，包括程序执行所必需的计算资源，例如程序代码、内存地址空间、文件系统、I/O设备、程序计数器、寄存器、栈空间等 执行特征，包括在进程执行过程中动态改变的特征，例如指令路径（即进程执行的指令序列）、进程的控制与执行状态等。,进程间通信,现代操作系统提供基本的系统调用函数，允许位于同一台处理机或不同处理机的多个进程之间相互交流信息 三种表现形式： 通信：进程间的数据传递称为进程间通信。 两个进

38、程间传递的数据称为消息；这种操作称为消息传递 同步：同步是使位于相同或不同处理机中的多个进程之间相互等待的操作，它要求进程的所有操作均必须等待到达某个控制状态之后才进行。 聚集（或规约）：聚集将位于相同或不同处理机中的多个进程的局部结果综合起来，通过某种操作，产生一个新的结果，存储在某个指定的或者所有的进程的变量中。 具体实现： 在共享存储环境中，通过读/写操作系统通过的共享数据缓存区来实现 在分布式存储网络环境中，通过网络通信来实现,进程的创建与撤销,进程创建 建立一个PCB，并对其内容进行初始化； 为该进程分配必要的存储空间，并加载所要执行的程序(在UNIX系统中需要通过另外一个系统调用e

39、xecl实现)； 将PCB送入就绪队列。 进程撤销 完成使命的进程需要终止自己并告知操作系统，系统将对进程进行善后处理(收集进程状态信息、通知其父进程等)，之后将收回进程所占有的所有资源(打开文件、内存等)，最后撤销其PCB 。，非正常终止也将进入操作系统进行善后处理 。,线程的概念,进程不适合细粒度的共享存储并行程序设计。 线程（thread）是进程上下文（context）中执行的代码序列，又被称为轻量级进程（light weight process），是进程内的一个相对独立的执行流。 进程可由单个线程来执行，即通常所说的串行执行；或者由多个线程来并行执行，此时，多个线程将共享该进程的所有资

40、源特征，并可以使用不同的CPU，对不同的数据进行处理，从而达到提高进程执行速度的目的。,线程的概念,在支持多线程的系统中： 进程成为资源分配和保护的实体 线程是被调度执行的基本单元。 进程的资源 包括进程的地址空间，打开的文件和I/O等 属于同一个进程的线程 共享该进程的代码段和数据段，打开的文件，信号等 还包含各自的线程ID，线程执行状态，CPU寄存器状态和栈,线程的概念,进程和线程的区别 进程是指程序在一个数据集合上运行的过程，是系统进行资源分配和调度运行的一个独立单位，有时也称为活动、路径或任务。 操作系统中引入进程的目的，是为了使多个程序并发执行，以改善资源利用率及提高系统的吞吐量。

41、操作系统中再引入线程则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。进程是资源的分配单位 。 线程是进程中的一个实体，是被系统调度和分配的基本单元。每个程序至少包含一个线程，那就是主线程。 线程自己只拥有很少的系统资源（如程序计数器、一组寄存器和栈），但它可与同属一个进程的其他线程共享所属进程所拥有的全部资源。 同一进程中的多个线程之间可以并发执行，从而更好地改善了系统资源的利用率。 线程是CPU的调度单位 。,线程是“进程中的一条执行路径或线索”或“进程中的一个可调度实体”,线程的概念,单线程与多线程处理器模型,线程的概念,线程的概念,线程的优点 上下文切换速度快：由

42、同一进程中的一个线程切换到另一个线程只需改变寄存器和栈，包括程序和数据在内的地址空间不变； 系统开销小：创建线程比创建进程所需完成的工作少，因而对于客户请求，服务器动态创建线程比动态创建进程具有更高的响应速度； 通讯容易：由于同一进程中的多个线程地址空间共享，一个线程写到数据空间的信息可以直接被该进程中的另一线程读取，方便快捷 ； 终止一个线程比终止一个进程的代价要小。,线程的概念,调度 在传统的操作系统中，CPU调度和分派的基本单位是进程。而在引入线程的操作系统中，则把线程作为CPU调度和分派的基本单位，进程则作为资源拥有的基本单位，从而使传统进程的两个属性分开，线程便能轻装运行，从而显著地

43、提高系统的并发性。 同一进程中线程的切换不会引起进程切换，从而避免了昂贵的系统调用。但是在由一个进程中的线程切换到另一进程中的线程时，依然会引起进程切换。,线程的概念,并发性 在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统的吞吐量。 例：在一个未引入线程的单CPU操作系统中，若仅设置一个文件服务进程，当它由于某种原因被封锁时，便没有其他的文件服务进程来提供服务。在引入了线程的操作系统中，可以在一个文件服务进程中设置多个服务线程。当第一个线程等待时，文件服务进程中的第二个线程可以

44、继续运行；当第二个线程封锁时，第三个线程可以继续执行，从而显著地提高了文件服务的质量以及系统的吞吐量。,线程的概念,系统开销 不论是引入了线程的操作系统，还是传统的操作系统，进程都是拥有系统资源的一个独立单位，它可以拥有自己的资源。 一般地说，线程自己不拥有系统资源（也有一点必不可少的资源）， 但它可以访问其隶属进程的资源。亦即一个进程的代码段、数据段以及系统资源（如已打开的文件、I/O设备等），可供同一进程的其他所有线程共享。,线程的概念,拥有资源 由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。

45、在进行进程切换时，涉及到整个当前进程CPU环境的保存环境的设置以及新被调度运行的进程的CPU环境的设置。 线程切换只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。因此进程切换的开销远大于线程切换的开销。 由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现也变得比较容易。,线程的概念,线程的结构,线程的概念,线程控制块(Thread Control Block，TCB) ：线程控制块是标志线程存在的数据结构，其中包含系统对于线程进行管理所需要的全部信息,线程的实现方式 用户级线程(User Level Thread) 在用户层通过线程库来实现 核心级线程(K

46、ernel Level Thread) 由操作系统直接支持 硬件线程(Hardware Thread)。 硬件线程就是线程在硬件执行资源上的表现形式。,用户级线程和内核级线程,用户级线程和内核级线程,用户级线程库 是用于用户级线程管理的例程包，支持线程的创建、终止，以及调度线程的执行并保存和恢复线程的上下文，这些操作都在用户空间进行，无需内核的支持。 内核级线程 所有管理操作都是由操作系统内核完成的。内核保存线程的状态和上下文信息，当一个线程执行了引起阻塞的系统调用时，内核可以调度该进程的其他线程执行。在多处理器系统上，内核可以分派属于同一进程的多个线程在多个处理器上运行，提高进程执行的并行度

47、。 组合模式 有的操作系统提供了组合的线程模式，在Solaris中，用户创建的多个用户级线程被映射到一些内核线程上，内核线程的数目可能少于用户级线程的数目。,用户级线程,用户级线程和内核级线程,用户级别线程优点： 线程不依赖于操作系统，可以采用与问题相关的调度策略，灵活性好； 同一进程中的线程切换不需进入操作系统，因而实现效率较高； 有关线程的所有管理工作都由在用户级实现的线程库来支持。 用户级别线程缺点： 同一进程中的多个线程不能真正并行； 由于线程对操作系统不可见，调度在进程级别，某进程中的一个线程通过系统调用进入操作系统受阻，该进程的其它线程也不能运行 。 用户级别线程特征： 户级线程的

48、创建和管理等操作无须内核参与，操作更快 并行性不高，一个线程被系统阻塞后，整个进程被阻塞,用户级线程和内核级线程,核心级线程通过系统调用由操作系统创建，线程的控制结构TCB保存于操作系统空间，线程状态转换由操作系统完成，线程是CPU调度的基本单位。,用户级线程和内核级线程,核心级别线程的优点是并发性好，在多CPU环境中同一进程中的多个线程可以真正并行执行 核心级别线程的缺点是线程控制和状态转换需要进入操作系统完成，系统开销比较大. 特点 并行性高， 多个线程可被同时调度 充分利用多处理器 创建和管理代价高,用户级线程和内核级线程,多线程的映射模型,对于实现了用户级线程和内核级线程的操作系统，用

49、户级线程和内核级线程之间的可以有不同的映射方式。 多对一模型 一对一模型 多对多模型,多线程的映射模型,多对一模型 多对一模型把多个用户级线程映射到一个内核级线程。 线程的管理在用户空间实现，所以效率高。 当一个线程因调用系统调用被阻塞时，整个进程被阻塞。 用户级线程不能在多处理器上并发执行，不支持内核级线程的操作系统使用多对一模型。,一对一模型 一对一模型把每个用户级线程影射到一个内核级线程。 当一个线程阻塞时，其他线程仍然可以运行。 实例： Windows 95/98/NT/2000 OS/2,多线程的映射模型,多对多模型 多对多模型将m个用户级线程影射到n个内核级线程，mn。 用户可以创

50、建所需要的用户级线程，通过分配适当数目的内核级线程获得并发执行的优势并节省系统资源。 Examples Solaris 2,多线程的映射模型,线程生命周期,线程的标识 通常用一个整数来标识一个线程 线程的创建 自动创建从main函数开始的主线程 调用函数库接口创建一个新的线程（pthread_create） 线程的终止 执行完毕，或者调用了pthread_exit 主线程退出导致整个进程会终止,线程状态的转换,线程的状态 就绪（ready）：线程等待可用的处理器。 运行（running）：线程正在被执行。 阻塞（blocked）：线程正在等待某个事件的发生（比如I/O的完成，试图加锁一个被上锁

51、的互斥量）。 终止（terminated）：线程从起始函数中返回或者调用pthread_exit。,线程的应用,许多任务在逻辑上涉及多个控制流，控制流具有内在的并发性，当其中一些控制流被阻塞时，另外一些控制流仍可继续。 在没有线程支持的条件下，只能采用单进程或多进程模式，单进程不能表达多控制流，多进程开销大而且在无共享存储空间的条件下进程间交往困难。 采用多线程一方面可以提高应用程序的并行性，另一方面也使程序设计简洁明晰。 例如：Word文字编辑工具、Web服务器等。,多线程程序设计,为什么要多线程程序设计 某些应用具有内在的多个控制流结构，这些控制流具有合作性质，需要共享内存，采用多线程易于

52、对问题建模，从而得到最自然的解决算法； 在需要多控制流的应用中，多线程比多进程在速度上具有绝对优势，统计测试表明，线程的建立速度比进程的建立速度快100倍，进程内线程间的切换速度与进程间切换速度也有数量级之差； 采用多线程可以提高处理机与设备之间的并行性. 在单控制流情形下，启动设备的进程进入核心后将被阻塞，此时该进程的其它代码也不能执行. 若此时无其它可运行程序，处理机将被闲置. 多线程结构在一个线程等待时，其它线程可以继续执行，从而使设备和处理机并行工作； 在多核环境下，多线程可以并行执行，既可提高资源利用效率，又可提高进程推进速度。,多线程机制,多核处理器的基本结构是共享存储的，多线程程

53、序设计技术被认为是能够充分挖掘共享存储系统性能潜力的最有效的技术。 多线程机制的优点： 创建一个线程比创建一个进程代价要小 ； 线程之间的切换比进程间的切换代价小 ； 充分利用多处理器 ； 数据共享 ； 快速响应特性 ； 多线程编程可以使程序更加更加模块化，简化程序逻辑 。,多线程机制,在多处理器系统上，如果一个应用具有如下特征，就可以利用多线程技术达到目标： 前台后台操作； 异步处理； 需要加速执行； 模块化程序结构。,多线程环境下的进程控制语义,单线程环境下的进程控制接口在多线程环境下语义可能会发生变化，包括进程创建、进程终止、进程执行、信号处理等操作。 进程创建 创建进程的系统调用完成后

54、，被创建的新进程复制调用进程的内容，当进程的一个线程中创建一个子进程，新的进程可以复制整个进程（包括所有线程）也可以只复制调用线程的内容； 执行新的程序 在进程中执行新的程序，函数的语义在多线程环境下没有发生大的变化。Exec将会终止所有的线程，用新的程序覆盖进程的地址空间，并开始执行新的程序；,多线程环境下的进程控制语义,进程结束 在任何一个线程中调用exit将会结束整个进程，另外从主线程返回也等同于调用exit而导致进程结束。如果要从线程中退出则调用专用的线程退出函数。 信号处理 信号是unix中系统通知进程的重要机制。信号可能是同步的也可能是异步的。发送给进程的信号在多线程环境下有多种选

55、择： 发送给引发信号的线程； 发送给所有的线程； 发送个特定的线程； 指定一个线程处理所有的信号。,多线程带来的问题,由于线程共享同一进程的内存空间，多个线程可能需要同时访问同一个数据。 对共享数据的并发访问可能导致数据的不一致性. 如果没有正确的保护措施，对共享数据的访问会造成数据的不一致和错误。 竞争条件 若干进程并发地访问并且操纵共享数据的情况; 共享数据的值取决于哪个进程最后完成; 防止竞争条件，并发进程必须被同步.,线程的同步,例：如果一个进程有一个共享变量counter，两个线程producer和consumer，线程producer执行counter+，线程consumer执行c

56、ounter-，这两个操作都需要多个机器指令来完成，Counter=5 counter+ counter- register1=counter register2=counter register1=register1+1 register2=register2-1 counter=register1 counter= register2 可能的序列： Producer: register1=counter (register1=5) Producer: register1=register1+1 (register1=6) Consumer: register2=counter (regis

57、ter2=5) Consumer: register2= register2-1 (register2=6) Producer: counter= register1 (counter=6) Consumer: counter= register2 (counter=4),顺序程序 程序的顺序性包括内部顺序性和外部顺序性。 内部顺序性：对于一个进程来说, 它的所有指令是按序执行的； 外部顺序性, 对于多个进程来说, 所有进程是依次执行的。 P1活动: a1 a2 a3 a4，P2活动: b1 b2 b3 b4 顺序执行时, 有如下两种情形: 情形1: a1 a2 a3 a4 b1 b2 b3

58、b4 情形2: b1 b2 b3 b4 a1 a2 a3 a4,线程的同步,顺序程序的特性 顺序性：处理机严格按照指令次序依次执行，即仅当一条指令执行完后才开始执行下一条指令； 封闭性：程序在执行过程中独占系统中的全部资源，该程序的运行环境只与其自身动作有关，不受其它程序及外界因素影响； 可再现性：程序的执行结果与执行速度无关，而只与初始条件有关，给定相同的初始条件，程序的任意多次执行一定得到相同的执行结果.,线程的同步,并发程序 程序的并发性含义： 内部并发性, 对于一个进程来说, 它的所有指令可能按序执行，也可能不按次序执行; 外部并发性: 对于多个进程来说, 所有进程是交叉(interl

59、eave)执行的. 例如, 对于上面P1和P2两个进程来说, 只考虑外部并发性，具有许多情形 ： 情形1: a1 b1 b2 a2 a3 b3 a4 b4 情形2: b1 b2 a1 a2 a3 b3 b4 a4 并发进程在其执行过程中, 出现哪种交叉情形是不可预知的, 这就是并发程序带来的不确定性,线程的同步,并发程序特性 交叉性：程序并发执行对应某一种交叉，不同的交叉可能导致不同的计算结果，操作系统应当保证只产生导致正确结果的交叉，去除那些可能导致不正确结果的交叉； 非封闭性：一个进程的运行环境可能被其它进程所改变，从而相互影响； 不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运行的结果,线程的同步,例：一个图书馆管理系统, 连有两个终端, 用户可通过终端借书. 为简化问题, 假设所有用户借阅的图书是相同的. 设x代表图书的剩余数量, 为两个终端用户服务的程序,线程的同步,线程的同步,常用的同步机制 临界区（critical section） 信号量（simphore） 互斥量（mutex） 管程（monitor） 锁的粒度 死锁,进程互斥,定义：两个或两个以上的进程，不能同时进入关