多线程编程方法综述.ppt

第二章 多线程编程方法综述,免费午餐结束了,为了充分利用多个计算核心，提高整个程序的吞吐率，主要是利用多线程,线程的基本概念线程的同步多线程编程模型多线程编程的原则及要点,3,内容,1.线程的基本概念,进程,（早期）进程作为能独立运行的基本单位。进程是程序在计算机上的一次执行活动。程序是死的（静态的），进程是活的（动态的）。进程是系统进行资源分配和调度运行的一个独立单位（也称为任务）。引入进程的目的：为了使多个程序并发执行，来改善资源利用率及提高系统的吞吐量。引入线程的目的：为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。,线程,线程：是进程中的一个实体，是被系统调度和分配的基本单元。每个程序至少包含一个线程，主线程。线程拥有很少的系统资源：程序计数器、一组寄存器和栈同一进程所属的各线程共享进程的全部资源同一个进程中的多个线程可以并发执行，从而更好地改善了资源利用率。,1.1 线程与进程的区别,线程是轻量级的进程，是CPU调度和分配的基本单位。传统意义的进程是重量级进程。,1.1 线程与进程的区别,调度传统的操作系统，进程是CPU调度和分配的基本单位。引入线程的操作系统，线程是CPU调度和分配的基本单位，而进程是资源拥有的基本单位。进程的两个属性分开，线程轻装运行，可以显著提高系统的并发性。同一个进程的线程切换简单。,1.1 线程与进程的区别,并发性进程之间可以并发执行一个进程的多个线程之间也可以并发执行例：未引入线程的操作系统，只有一个文件服务进程，它由于某种原因被封锁，就没有其他的文件服务进程来提供服务。若引入线程，一个文件服务进程中设置多个服务线程。,1.1 线程与进程的区别,系统开销进程是拥有系统资源的一个独立单位线程不拥有系统资源（只有一点必不可少的资源），可以访问其隶属进程的资源。一个进程的代码段、数据段以及系统资源（如打开的文件、I/O设备等），可供进程的所有线程共享。,1.1 线程与进程的区别,拥有资源创建和撤销进程时，系统都要为之分配和回收资源，如内存空间、I/O设备等。操作系统所付出的开销将显著大于创建和撤销线程时的开销。进程切换涉及到当前进程CPU环境的保存和新被调度进程的CPU环境的设置。线程的切换只需保存少量寄存器的内容，不涉及存储器。,1.2 用户级线程、核心级线程和硬件线程,根据多线程实现机制：线程又被分为用户级线程和内核级线程用户级线程：在用户层通过线程库来实现。对它的创建、撤销和切换都不利用系统的调用。核心级线程：由操作系统直接支持，即无论是在用户进程中的线程，还是系统进程中的线程，它们的创建、撤销和切换都由核心实现。,1.2 用户级线程、核心级线程和硬件线程,硬件线程就是线程在硬件执行资源上的表现形式单个线程一般都包括三个层次：用户级线程映射到核心级线程，再通过硬件相应的接口作为硬件线程来执行。,用户级线程和核心级线程之间的映射方式,多对一模型：把多个用户级线程映射到一个核心级线程 一对一模型：把每个用户级线程影射到一个核心级线程 多对多模型：将m个用户级线程影射到n个核心级线程，mn,多对多映射,1.3 线程的生命周期,线程的生命周期：线程从创建到消亡的过程。,2 线程的同步,为什么需要线程同步？,线程共享同一进程的内存空间 多个线程可能需要同时访问同一个数据如果没有正确的保护措施，对共享数据的访问会造成数据的不一致和错误。,最后的结果取决于线程执行的顺序,常用的线程同步方法,互斥（Mutual exclusion）当一个线程进入某个临界区域（访问线程共享数据的代码段），此时其他想访问这个临界区域的线程就必须等待。临界区（Critical_Section）信号量（Semaphore）互斥量（Mutex）条件同步（Condition sychronization）执行线程将一直处于阻塞状态直道系统满足指定的条件。条件变量（Conditional Variable）,2.1 临界区-互斥,临界区是指包含共享数据的一段代码，这些代码可能被多个线程访问或修改。当一个线程在临界区内执行的时候，不能有其他任何线程被允许在临界区执行。临界区：进入区和退出区,进入区,退出区,临界区,2.2 信号量,信号量被定义为一个整数变量 对信号量只能通过两个原子操作P（wait等信号，减量操作）和V（signal给信号，增量操作）,signal（S）S.value；if(S.value=0)Remove a process p from S.L;Wakeup(p);,wait（S）S.value-；if（S.value 0）Add this process to S.L;Block(),锁类似于信号量，不同之处在于同一时刻只能使用一个锁。锁对应两个原子操作：Acquire（）获取操作，将锁据为己有并把状态改为已加锁，如果该锁已被其他线程占有则等待，锁状态保持未加锁状态。Release（）释放操作，将锁状态由已加锁状态改为未加锁状态。一个锁最多只能由一个线程获得。任何线程访问共享资源前要先获得锁，否则，线程将保持在该锁的等待队列，直到该锁被释放。,22,2.4 锁,互斥量是一种锁，线程对共享资源访问之前必须先获得锁；否则线程将保持等待状态，直到该锁可用。占有这个锁的过程就叫做锁定，或者叫获得互斥量。,2.4 锁,2.4 锁,Thread AVoid someMethod()print(“A Hello one”);print(“A Hello two”);,Thread BVoid someMethod()print(“B Hello one”);print(“B Hello two”);,不使用同步原语,A Hello oneB Hello oneB Hello twoA Hello two,2.4 锁,Thread AVoid someMethod()mutex.lock();print(“A Hello one”);print(“A Hello two”);mutex.unlock();,Thread BVoid someMethod()mutex.lock();print(“B Hello one”);print(“B Hello two”);mutex.unlock();,加上同步原语Mutex mutex;,2.5 条件变量,条件变量是用来通知共享数据状态信息的。当特定条件满足时，线程等待或者唤醒其他合作线程。条件变量不提供互斥，需要一个互斥量来同步对共享数据的访问。,2.5 条件变量,条件变量C使用锁L来完成对共享数据的访问，则可以对条件变量C执行的3种原子操作：Wait(L)：该操作释放自身所持有的锁并等待，其执行完毕则表示锁已被其他线程获得。Signal(L)：允许等待队列中的一个线程往下继续执行，该操作执行完毕即表示锁仍然被持有。Broadcast(L)：广播，允许所有线程往下执行，该操作执行完毕即表示锁仍然被持有。,Lock L;Bool LC=false;void producer()while(1)L-acquire();/临界区开始 while(LC=true)C-wait(L);/产生下一个数据 LC=true;C-signal(L);/临界区结束 L-release();,void consumer()while(1)L-acquire();/临界区开始 while(LC=false)C-wait(L);/消费下一个数据 LC=false;C-signal(L);/临界区结束 L-release();,3.多线程的编程模型,编程模型：以多线程编程模型为主的并行处理系统和并发式应用程序。多线程编程模型是目前计算机系统架构的最终模型多线程编程模型的目的，就是“最大限度地利用CPU资源”,三种多线程编程模型,流水线工作组客户端/服务器,3.1 流水线编程模型What Is Pipelining,Laundry（洗衣）ExampleAnn,Brian,Cathy,Dave each have one load of clothes to wash,dry,and foldWasher takes 30 minutesDryer takes 40 minutes“Folder”takes 20 minutes,What Is Pipelining,Sequential laundry takes 6 hours for 4 loadsIf they learned pipelining,how long would laundry take?,30,40,20,30,40,20,30,40,20,30,40,20,6 PM,7,8,9,10,11,Midnight,TaskOrder,Time,What Is Pipelining Start work ASAP,Pipelined laundry takes 3.5 hours for 4 loads,6 PM,7,8,9,10,11,Midnight,TaskOrder,Time,3.1 流水线编程模型,在流水线方式中，数据元素流串行地被一组线程顺序处理。每个线程反复地在数据系列集上执行同一种操作，并把操作的结果传递给下一步骤的其他线程,3.1 流水线编程模型,3.2 工作组编程模型,数据由一组线程独立地处理循环的“并行分解”就属于这种模式，通常这种模式称为SIMD并行处理。也可以在不同的数据上执行不同的操作，与MIMD并行处理的定义相似。,3.2 工作组编程模型,3.3 客户端/服务器方式,客户端请求服务器对一组数据执行某个操作。,4.多线程编程的原则及要点,负载平衡,静态负载平衡人工地将程序分割成多个可并行执行的部分，并保证分割的各个部分能均衡地分布到各个CPU上。动态负载平衡程序在运行过程中来进行任务的分配达到负载平衡的目的。如：循环的次数是由外部输入决定的动态负载平衡中对任务的调度一般是由系统来实现的。,负载平衡的难题,程序中的可并行执行块很多要靠程序员来划分，CPU核数较少时，划分并不困难。但随着核数增多，划分的粒度将变得越来越细，划分难度增加。负载划分的误差会随着CPU核数的增加而放大。负载划分的难题体现在CPU核数上。负载划分的难题体现在软件升级上。,串行化问题,加锁保护导致的串行化问题，如果任务数量固定的前提下，串行化所占的比例是随软件规模的增加而减少的，但不幸的是它会随着任务数量的增加而增加。也就是说处理器个数越多，锁竞争导致的串行化越严重。,解决措施,少用锁，甚至采用无锁编程使用原子操作代替锁，使用原子操作本质上并没有解决串行化的问题，只不过让串行化的速度大大提升，从而使得串行化所占执行时间比例大大下降。从设计和算法层面来缩小串行化所占的比例。从芯片设计方面来考虑的，在芯片层面设计一些新的并行指令,