03第三章 多线程编程 多核编程.ppt

第三章 多线程概述 l多线程技术运用恰当，多线程技术就能使硬件资源得到更加充分的利用，提高计算性能；反之，降低计算性能，导致应用程序发生一些不可预测的行为，甚至出现难以解决的故障。只要正确理解线程的运行方式，就可以避免这些可能出现的问题，达到充分发挥多线程技术的优势、提高计算性能的目的。进程概念l定义：进程是具有一定独立功能的程序关于一个数据集合的一次运行活动。可表示成四元组（P,C,D,S），其中P是程序代码，C是进程的控制状态，D是进程的数据，S是进程的执行状态。l状态：运行态(Run):进程占有处理机资源,正在运行;就绪态(Ready):进程本身具备运行条件,但由于处理机的个数少于可运行进程的个数,暂未投入运行;等待态(Wait):进程本身不具备运行条件，即使分给它处理机也不能运行.进程正等待某一个事件的发生,如等待某一资源被释放，等待与该进程相关的I/O传输的完成信号等。进程概念l状态间转换当一个就绪进程获得处理机时,其状态由就绪变为运行;当一个运行进程被剥夺处理机时,其状态由运行变为就绪;当一个运行进程因某事件受阻时,如所申请资源被占用,启动I/O传输未完成,其状态由运行变为等待;当所等待事件发生时,如得到申请资源,I/O传输完成,其状态由等待变为就绪.进程概念l进程控制块(Process Control Block，PCB):标志进程存在的数据结构，其中包含系统对进程管理需要的全部信息。进程标识用户标识进程状态调度参数现场信息家族联系程序地址当前打开文件消息队列指针资源使用情况进程队列指针进程概念l进程的组成 进程控制块：由于进程控制块中包含程序的地址信息，通过它可以找到程序在内存或外存的存放地址，也就找到了整个进程.PCB存于系统空间，只有操作系统能够对其存取，用户程序不能访问.实际上用户甚至感觉不到PCB的存在；程序：进程的“躯体”，其中包括代码和数据两个部分.现代操作系统都支持程序共享的功能，这就要求代码是“纯”的，即在运行期间不修改自身。数据一般包括静态变量、动态堆和动态栈。进程概念l进程的表示：PCB程序PCB代码数据+堆栈系统空间用户空间（a）（b）进程概念l进程的队列：为实现对进程的管理，系统需要按照某种策略将进程排成若干队列，由于PCB是进程的代表，因而进程队列实际上是由进程PCB构成的队列.因为该队列通常由链的形式实现的，所以也称PCB链。系统中的进程队列分为如下三类：就绪队列、等待队列、运行队列。进程的队列l就绪队列整个系统一个.所有处于就绪状态的进程按照某种组织方式排在这一队列中.l等待队列每个等待事件一个，当进程等待某一事件时，进入与该事件相关的等待队列中；当某事件发生时，与该事件相关的一个或多个进程离开相应的等待队列，进入就绪队列.l运行队列在单CPU系统中只有一个，在多CPU系统中每个CPU各有一个，每个队列中只有一个进程，指向运行队列头部的指针被称作运行指示字.进程概念l进程的类型系统进程 运行操作系统程序，完成操作系统的某些功能；用户进程运行用户程序，直接为用户服务。l特性：并发性：与其它进程一道在宏观上同时向前推进；动态性：进程是执行中的程序.此外进程的动态性还体现在如下两个方面：首先，进程是动态产生、动态消亡的；其次，在进程的生存期内，其状态处于经常性的动态变化之中；独立性：进程是调度的基本单位，它可以获得处理机并参与并发执行；交往性：进程在运行过程中可能会与其它进程发生直接或间接的相互作用；异步性：每个进程都以其相对独立、不可预知的速度向前推进；结构性：每个进程有一个控制块PCB。进程间相互联系与相互作用 l多道系统中同时运行的并发进程一般有多个，在逻辑上，这些进程之间可能存在某种联系，也可能相对独立 相关进程：在逻辑上具有某种联系的进程称作相关进程;无关进程：在逻辑上没有任何联系的进程称作无关进程；l并发进程之间存在相互制约的关系，这种相互制约的关系称作进程间的相互作用.进程间相互作用的方式有两种：即直接相互作用和间接相互作用即直接相互作用和间接相互作用直接相互作用：进程之间不需要通过中间媒介而发生的相互作用，这种相互作用通常是有意识的；间接相互作用：进程之间需要通过某种中间媒介而发生的相互作用，这种相互作用通常是无意识的。进程的创建与撤销 l进程创建 建立一个PCB，并对其内容进行初始化；为该进程分配必要的存储空间，并加载所要执行的程序(在UNIX系统中需要通过另外一个系统调用execl实现)；将PCB送入就绪队列。l进程撤销完成使命的进程需要终止自己并告知操作系统，系统将对进程进行善后处理(收集进程状态信息、通知其父进程等)，之后将收回进程所占有的所有资源(打开文件、内存等)，最后撤销其PCB。，非正常终止也将进入操作系统进行善后处理。线程的概念l线程（thread）是进程上下文（context）中执行的代码序列，又被称为轻量级进程（light weight process），是进程内的一个相对独立的执行流。l在支持多线程的系统中：进程成为资源分配和保护的实体线程是被调度执行的基本单元。l进程的资源包括进程的地址空间，打开的文件和I/O等l属于同一个进程的线程共享该进程的代码段和数据段，打开的文件，信号等还包含各自的线程ID，线程执行状态，CPU寄存器状态和栈线程的概念l进程和线程的区别：进程-是指程序在一个数据集合上运行的过程，是系统进行资源分配和调度运行的一个独立单位，有时也称为活动、路径或任务。如果说在操作系统中引入进程的目的，是为了使多个程序并发执行，以改善资源利用率及提高系统的吞吐量；那么，在操作系统中再引入线程则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。进程是资源的分配单位。线程 是进程中的一个实体,是被系统调度和分配的基本单元。每个程序至少包含一个线程，那就是主线程。线程自己只拥有很少的系统资源（如程序计数器、一组寄存器和栈），但它可与同属一个进程的其他线程共享所属进程所拥有的全部资源，同一进程中的多个线程之间可以并发执行，从而更好地改善了系统资源的利用率。线程是CPU的调度单位。l线程是“进程中的一条执行路径或线索”或“进程中的一个可调度实体”lSingle Threaded and Multithreaded Process Models线程的概念l线程具有如下优点：上下文切换速度快：由同一进程中的一个线程切换到另一个线程只需改变寄存器和栈，包括程序和数据在内的地址空间不变；系统开销小：创建线程比创建进程所需完成的工作少，因而对于客户请求，服务器动态创建线程比动态创建进程具有更高的响应速度；通讯容易：由于同一进程中的多个线程地址空间共享，一个线程写到数据空间的信息可以直接被该进程中的另一线程读取，方便快捷；终止一个线程比终止一个进程的代价要小。线程的概念l线程与进程的区别：线程为轻量级进程（lightweight process,LWP），也是CPU调度和分派的基本单元；进程则被称为重量级进程（heavyweight process,HWP），它就是只拥有一个线程的进程。如果进程有多个控制线程，那么它就能同时执行多个任务。他们之间的关系可以简单的由下图表示：线程的概念l调度在传统的操作系统中，CPU调度和分派的基本单位是进程。而在引入线程的操作系统中，则把线程作为CPU调度和分派的基本单位，进程则作为资源拥有的基本单位，从而使传统进程的两个属性分开，线程便能轻装运行，这样可以显著地提高系统的并发性。同一进程中线程的切换不会引起进程切换，从而避免了昂贵的系统调用。但是在由一个进程中的线程切换到另一进程中的线程时，依然会引起进程切换。线程的概念l并发性 在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统的吞吐量。例如，在一个未引入线程的单CPU操作系统中，若仅设置一个文件服务进程，当它由于某种原因被封锁时，便没有其他的文件服务进程来提供服务。在引入了线程的操作系统中，可以在一个文件服务进程中设置多个服务线程。当第一个线程等待时，文件服务进程中的第二个线程可以继续运行；当第二个线程封锁时，第三个线程可以继续执行，从而显著地提高了文件服务的质量以及系统的吞吐量。线程的概念l系统开销 不论是引入了线程的操作系统，还是传统的操作系统，进程都是拥有系统资源的一个独立单位，它可以拥有自己的资源。一般地说，线程自己不拥有系统资源（也有一点必不可少的资源），但 它可以访问其隶属进程的资源。亦即一个进程的代码段、数据段以及系统资源（如已打开的文件、I/O设备等），可供同一进程的其他所有线程共享。线程的概念l拥有资源 由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地，在进行进程切换时，涉及到整个当前进程CPU环境的保存环境的设置以及新被调度运行的进程的CPU环境的设置。而线程切换只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。此外，由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现也变得比较容易。在有的系统中，线程的切换、同步和通信都无需操作系统内核的干预。线程的概念l线程的结构 线程的概念l线程控制块(Thread Control Block，TCB)：线程控制块是标志线程存在的数据结构，其中包含系统对于线程进行管理所需要的全部信息 线程的概念l线程有两种实现方式：用户级线程(User Level Thread)和核心级线程(Kernel Level Thread)。更深入一步来讲我们还可以划分出硬件线程(Hardware Thread)。用户级线程在用户层通过线程库来实现。对它的创建、撤销和切换都不利用系统的调用。核心级线程由操作系统直接支持，即无论是在用户进程中的线程，还是系统进程中的线程，它们的创建、撤消和切换都由核心实现。硬件线程就是线程在硬件执行资源上的表现形式。线程的概念l用户级别线程线程的概念l用户级别线程优点：线程不依赖于操作系统，可以采用与问题相关的调度策略，灵活性好；同一进程中的线程切换不需进入操作系统，因而实现效率较高；有关线程的所有管理工作都由在用户级实现的线程库来支持。l用户级别线程缺点：同一进程中的多个线程不能真正并行；由于线程对操作系统不可见，调度在进程级别，某进程中的一个线程通过系统调用进入操作系统受阻，该进程的其它线程也不能运行。l用户级别线程特征：户级线程的创建和管理等操作无须内核参与，操作更快 并行性不高，一个线程被系统阻塞后，整个进程被阻塞线程的概念l核心级别线程通过系统调用由操作系统创建，线程的控制结构TCB保存于操作系统空间，线程状态转换由操作系统完成，线程是CPU调度的基本单位。l核心级别线程的优点是并发性好，在多CPU环境中同一进程中的多个线程可以真正并行执行 l核心级别线程的缺点是线程控制和状态转换需要进入操作系统完成，系统开销比较大.l特点并行性高，多个线程可被同时调度充分利用多处理器创建和管理代价高 多线程的映射模式 l对于实现了用户级线程和内核级线程的操作系统，用户级线程和内核级线程之间的可以有不同的映射方式：l多对一模型 多对一模型把多个用户级线程映射到一个内核级线程。线程的管理在用户空间实现，所以效率高。当一个线程因调用系统调用被阻塞时，整个进程被阻塞。另外，用户级线程不能在多处理器上并发执行，不支持内核级线程的操作系统使用多对一模型。多线程的映射模式l多对一模型多线程的映射模式l一对一模型一对一模型把每个用户级线程影射到一个内核级线程。当一个线程阻塞时，其他线程仍然可以运行。lExamplesWindows 95/98/NT/2000OS/2l多对多模型多对多模型将m个用户级线程影射到n个内核级线程，mn。用户可以创建所需要的用户级线程，通过分配适当数目的内核级线程获得并发执行的优势并节省系统资源。ExamplesSolaris 2 线程生命周期l线程的标识通常用一个整数来标识一个线程 l线程的创建自动创建从main函数开始的主线程调用函数库接口创建一个新的线程（pthread_create）l线程的终止执行完毕，或者调用了pthread_exit 主线程退出导致整个进程会终止 线程状态的转换l线程的状态就绪（ready）：线程等待可用的处理器。运行（running）：线程正在被执行。阻塞（blocked）：线程正在等待某个事件的发生（比如I/O的完成，试图加锁一个被上锁的互斥量）。终止（terminated）：线程从起始函数中返回或者调用pthread_exit。线程的应用l许多任务在逻辑上涉及多个控制流，控制流具有内在的并发性，当其中一些控制流被阻塞时，另外一些控制流仍可继续.在没有线程支持的条件下，只能采用单进程或多进程模式，单进程不能表达多控制流，多进程开销大而且在无共享存储空间的条件下进程间交往困难.采用多线程一方面可以提高应用程序的并行性，另一方面也使程序设计简洁明晰。例如：Word文字编辑工具、Web服务器等。多线程程序设计l为什么要多线程程序设计某些应用具有内在的多个控制流结构，这些控制流具有合作性质，需要共享内存，采用多线程易于对问题建模，从而得到最自然的解决算法；在需要多控制流的应用中，多线程比多进程在速度上具有绝对优势，统计测试表明，线程的建立速度比进程的建立速度快100倍，进程内线程间的切换速度与进程间切换速度也有数量级之差；采用多线程可以提高处理机与设备之间的并行性.在单控制流情形下，启动设备的进程进入核心后将被阻塞，此时该进程的其它代码也不能执行.若此时无其它可运行程序，处理机将被闲置.多线程结构在一个线程等待时，其它线程可以继续执行，从而使设备和处理机并行工作；在多核环境下，多线程可以并行执行，既可提高资源利用效率，又可提高进程推进速度。多线程机制l多核处理器的基本结构是共享存储的，多线程程序设计技术被认为是能够充分挖掘共享存储系统性能潜力的最有效的技术。l多线程机制的优点包括以下几个方面：创建一个线程比创建一个进程代价要小；线程之间的切换比进程间的切换代价小；充分利用多处理器；数据共享；快速响应特性；多线程编程可以使程序更加更加模块化，简化程序逻辑。多线程机制l在多处理器系统上，如果一个应用具有如下特征，就可以利用多线程技术达到目标：前台后台操作；异步处理；需要加速执行；模块化程序结构。多线程环境下的进程控制语义l单线程环境下的进程控制接口在多线程环境下语义可能会发生变化，包括进程创建、进程终止、进程执行、信号处理等操作。进程创建创建进程的系统调用完成后，被创建的新进程复制调用进程的内容，当进程的一个线程中创建一个子进程，新的进程可以复制整个进程（包括所有线程）也可以只复制调用线程的内容；执行新的程序 在进程中执行新的程序，函数的语义在多线程环境下没有发生大的变化。Exec将会终止所有的线程，用新的程序覆盖进程的地址空间，并开始执行新的程序；多线程环境下的进程控制语义进程结束 在任何一个线程中调用exit将会结束整个进程，另外从主线程返回也等同于调用exit而导致进程结束。如果要从线程中退出则调用专用的线程退出函数。信号处理信号是unix中系统通知进程的重要机制。信号可能是同步的也可能是异步的。发送给进程的信号在多线程环境下有多种选择：发送给引发信号的线程；发送给所有的线程；发送个特定的线程；指定一个线程处理所有的信号。多线程带来的问题l由于线程共享同一进程的内存空间，多个线程可能需要同时访问同一个数据。l对共享数据的并发访问可能导致数据的不一致性.l如果没有正确的保护措施，对共享数据的访问会造成数据的不一致和错误。l竞争条件若干进程并发地访问并且操纵共享数据的情况;共享数据的值取决于哪个进程最后完成;防止竞争条件，并发进程必须被同步.线程的同步l例：如果一个进程有一个共享变量counter，两个线程producer和consumer，线程producer执行counter+，线程consumer执行counter-，这两个操作都需要多个机器指令来完成，Counter=5counter+counter-register1=counter register2=counterregister1=register1+1 register2=register2-1counter=register1 counter=register2可能的序列：可能的序列：Producer:register1=counter (register1=5)Producer:register1=register1+1 (register1=6)Consumer:register2=counter (register2=5)Consumer:register2=register2-1 (register2=6)Producer:counter=register1 (counter=6)Consumer:counter=register2 (counter=4)顺序程序l顺序程序，程序的顺序性包括内部顺序性和外部顺序性。内部顺序性：对于一个进程来说,它的所有指令是按序执行的；外部顺序性,对于多个进程来说,所有进程是依次执行的。P1活动:a1 a2 a3 a4，P2活动:b1 b2 b3 b4 顺序执行时,有如下两种情形:情形1:a1 a2 a3 a4 b1 b2 b3 b4 情形2:b1 b2 b3 b4 a1 a2 a3 a4 顺序程序l顺序程序的特性：顺序性：处理机严格按照指令次序依次执行，即仅当一条指令执行完后才开始执行下一条指令；封闭性：程序在执行过程中独占系统中的全部资源，该程序的运行环境只与其自身动作有关，不受其它程序及外界因素影响；可再现性：程序的执行结果与执行速度无关，而只与初始条件有关，给定相同的初始条件，程序的任意多次执行一定得到相同的执行结果.并发程序 l程序的并发性含义:内部并发性,对于一个进程来说,它的所有指令可能按序执行，也可能不按次序执行;外部并发性:对于多个进程来说,所有进程是交叉(interleave)执行的.例如,对于上面P1和P2两个进程来说,只考虑外部并发性，具有许多情形：情形1:a1 b1 b2 a2 a3 b3 a4 b4 情形2:b1 b2 a1 a2 a3 b3 b4 a4 并发进程在其执行过程中,出现哪种交叉情形是不可预知的,这就是并发程序带来的不确定性 并发程序l并发程序特性：交叉性：程序并发执行对应某一种交叉，不同的交叉可能导致不同的计算结果，操作系统应当保证只产生导致正确结果的交叉，去除那些可能导致不正确结果的交叉；非封闭性：一个进程的运行环境可能被其它进程所改变，从而相互影响；不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运行的结果 l例：一个图书馆管理系统,连有两个终端,用户可通过终端借书.为简化问题,假设所有用户借阅的图书是相同的.设x代表图书的剩余数量,为两个终端用户服务的程序 进程互斥 l定义：两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域,否则可能发生与时间有关的错误,这种现象被称作进程互斥.l进程互斥是进程之间所发生的一种间接性相互作用,这种相互作用是进程本身不希望的,也是运行进程感觉不到的.进程互斥可能发生在相关进程之间,也可能发生在不相关进程之间.l互斥量（Mutex）作为一种互斥设备，有两个状态，上锁和空闲。同一时刻只能有一个线程能够对互斥量加锁。对于一个已经被加锁的互斥量，当另外一个线程试图对它加锁时，该线程会被阻塞，知道该互斥量被释放。互斥量在Pthread线程库中被定义为pthread_mutex_t类型。互斥量（Mutex）lPthread线程库对一个互斥量的加锁操作是：int pthread_mutex_lock(pthread_mutex_t*mutex);int pthread_mutex_trylock(pthread_mutex_t*mutex);pthread_mutex_unlock(pthread_mutex_t*mutex);/释放lproducer对counter变量的操作要先加锁互斥量，完成对counter的操作之后释放互斥量 pthread_mutex_lock(&counter_mutex);counter+;pthread_mutex_unlock(&counter_mutex);锁l类似信号量，同一时刻使用一个锁，对应两个原子操作：Acquire()：获取操作，将锁据为己有，状态-已加锁，如果锁被占，等待之；Release()：释放操作，将锁状态-未加锁。l互斥量是一种锁，线程对共享资源进行访问之前必须先获得锁，否则，线程保持等待状态，直到锁可用，只有其他线程都不占有它时，一个线程才可以占有它。占有锁的过程叫做锁定或者获得互斥量。A Hello oneB Hello oneB Hello twoA Hello twolMutex mutex;A Hello one B Hello oneA Hello two B Hello twoB Hello one A Hello one B Hello two A Hello two 锁的粒度l锁的粒度是上锁后保护的共享数据的多少，假设多个线程需要存取一棵树，如果设定一个互斥量以保证对数的互斥访问，当一个线程加锁并访问该树期间，则其他线程无法访问。另一种方法是对树的每个节点设置一个互斥量，当访问不同的节点时，加锁不同的互斥量，除非两个线程试图访问同一个节点，多个线程可以同时访问树的不同节点，在多CPU或多核系统中可以充分地利用并行处理能力。竞争条件l竞争条件（Race Conditions）：多个线程间可能会共享一些彼此都能够读写的公用存储区，它可能在内存中，也可能是一个共享文件，当两个或多个进程试图在同一时刻访问共享内存，或读写某些共享数据，而最后的结果取决于线程之行的顺序。例：“抢椅子”游戏，三个人伴随着音乐围着两把椅子转，当音乐暂停时，便立即找空的椅子坐下。没有抢到椅子的人被淘汰，这时，三个人就对应着三个不同的线程，椅子就是他们共享的区域。最后区域的值是多少完全取决于人被淘汰的顺序。临界区域(critical region)l有些变量,两个进程或两个以上的进程均需要访问它们,这些变量被称作共享变量共享变量,也称公共变量，访问共享变量的程序段称作临界区域临界区域(critical region),也称为临界段(critical section)定义：多个进程均需要访问的变量称为公共变量(shared variable)；定义：访问共享变量的程序段称作临界区域(critical region),也称为临界段(critical section)共享变量可能属于操作系统空间，也可能属于用户进程空间.对于前者,其临界区域亦属于操作系统空间，而对于后者,其临界区域则属于用户进程空间.临界区l所有n 个进程竞争使用一些共享的数据。l每个进程有一个代码段,称为临界区,在那儿共享数据被访问。l问题保证当一个进程正在临界区执行时，没有另外的进程进入临界区执行l解决临界区问题需满足互斥：假定进程Pi在其临界区内执行，其他任何进程将被排斥在自己的临界区之外.有空让进：临界区虽没有进程执行，但有些进程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间.有限等待：在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区前的等待时间必须是有限的.假定每个进程都以非零的的速率执行.没有任何关于这n个进程相对执行速率的假定临界区与进程互斥 l两个或两个以上的进程不能同时进入关于同一组共同一组共享变量享变量的临界区域临界区域,其中有两层含意:不容许多个进程同时进入关于同一组共享变量的相同的临界区域;不容许多个进程同时进入关于同一组共享变量的不同的临界区域.如果容许,则有可能发生错误,亦有可能不发生错误,这与各个进程并发执行时的推进速度有关.l这是保证正确性的要求,但这件事的实现应当由操作系统以及并发程序的设计者在编写程序时来保证,而这需要有必要的互斥机制.l临界区域嵌套引起的问题 互斥的实现 l应当满足下面三个管理原则:正确性原则(correctness)：任意时刻至多只能有一个进程处于关于同一组共享变量的临界区域之中；公平性原则(fairness)：一个请求进入临界区的进程应当在有限等待时间内获得进入该临界区的机会；进展性原则(progress)：当临界区空闲时，竞争进入临界区的多个进程在有限时间之内确定下一个进入临界区的进程.l临界区域的管理应当满足如下调度原则:当关于某一组共享变量的所有临界区域均为空闲时,一个要求进入该组共享变量某一临界区域的进程应当能够立即进入;当关于某一组共享变量的某一临界区域被占用时,一个要求进入该组共享变量某一临界区域的进程应当等待;当一个进程离开关于某一组共享变量的某一临界区域时,应当容许某一个等待进入关于该组共享变量某一临界区域的进程进入.解释:使用临界区的原则l每次只允许一个进程处于它的临界区(CS)中l若有多个进程同时想进入CS,应在有限时间内让其中一个进程进入CS,以免阻塞l进程在CS内只能逗留有限时间l不应使要进入CS的进程无限期地等待在CS之外l在CS之外的进程不可以阻止其他进程进入CSl不要预期和假定进程进展的相对速度以及可用的处理器数目.因为这是不可预期的.同步 l同步：一组进程（线程）,为了协调其推进速度,在某些点处需要相互等待与相互唤醒,进程之间这种相互制约的关系称作进程同步，简称同步(synchronization).进程同步是进程之间直接的相互作用形式,是合作进程之间有意识的行为,这种相互作用只发生在相关的进程之间。l进程合作(cooperation)：一组进程，如果它们单独不能正常进行,但并发可以正常进行,称这种现象为进程合作，参与合作的进程称作合作进程(cooperating process)。l同步例子：要求:(1)关车门后方能启动车辆;(2)到站停车后方能开车门.进程同步机制 l同步机制：用于实现进程间同步的工具称作同步机制，亦称同步设施(synchronization mechanism)l同步机制应当满足如下几个基本要求:描述能力够用:即用此种同步机制应当能够描述操作系统及并发程序设计中所遇到的各种同步问题;可以实现;效率高;使用方便.信号量 l信号量与PV操作：包括一种称作信号灯类型的变量以及对于此种变量所能进行的两个操作：即P(wait,减量操作)操作和V（signal,增量操作）操作wait(s)signal(s)while(s=0)s+;s-;信号量使用基本要求:必需置一次且只能置一次初值,而且初值必需为非负整数;只能执行P操作和V操作,所有其它操作均是非法的。l结论:当s0时,s等待队列为空;当s0时,s为s队列中等待进程的个数;当s的初值为1时,可以用来实现进程互斥,这只需在进入临界区时执行一次P操作,在离开临界区时执行一次V操作；当s的初值为正整数时，可以用来管理同种组合资源(具有多个实例的同种类资源，如5台打印机)，申请时执行一次P操作，归还时执行一次V 操作。进程通讯 l定义：进程之间的互斥、同步及信息交换统称进程通讯(Inter-Process Communication，IPC)l低级通讯：将进程互斥与进程同步称作进程之间的低级通讯；l高级通讯：进程之间大数据量的传递称作进程之间的高级通讯。进程通讯的模式l进程通讯主要有两种模式:共享内存模式和消息模式。共享内存模式相互通讯的进程之间需要有公共内存,一组进程向该公共内存中写,另一组进程由该公共内存中读,如此便实现了进程之间的信息传递。需要解决两个问题:为相互通讯的进程之间提供公共内存；为访问公共内存提供必要的同步机制。信息传递模式（通讯通过两个基本的系统调用命令,即发送命令和接收命令）直接方式间接方式 l直接方式：是指相互通讯的进程之间在通讯时直呼其名,发送者在发送时要指定接收者的名字,接收者在接收时要指定发送者的名字两种系统调用形式：对称形式通讯形式的特点是一对一的，调用命令：send(R,M)：将消息M发给进程R；receive(S,N)：由进程S处接收消息至N。非对称形式通讯形式的特点是多对一的，调用命令：send(R,M)：将消息M发给进程R；receive(pid,N)：接受消息至N，返回pid为发送进程标识。信息传递两种途径：有缓冲途径无缓冲途径l间接方式：是指相互通讯的进程之间在通讯时不是直呼对方名字,而是指明一个中间媒体,即信箱,进程之间通过信箱来实现相互间的通讯.此时,系统所提供的高级通讯原语以信箱取代进程发送和接收原语如下：send(MB,M)：将消息M发送到信箱MB；receive(MB,N)：由信箱MB中接收消息至。死锁l如果两个线程都各自加锁了一个互斥量，然后申请加锁对方的互斥量，这样会陷入阻塞，这样的话，这两个线程永远不会从阻塞中恢复，此时，这两个线程处于死锁状态。l定义：一组进程（线程）中的每个进程（线程）均等待此组进程（线程）中某一其它进程（线程）所占有的,因而永远无法得到的资源,这种现象称作进程死锁。参与死锁的进程个数至少为二；参与死锁的所有进程均等待资源；参与死锁的进程至少有两个占有资源；参与死锁的进程是系统中当前正在运行进程之集合的一个子集。l死锁的类型 竞争资源引起的死锁由于进程争夺使用系统中有限的资源而引起；进程通讯引起的死锁其它原因引起的死锁l死锁的条件资源独占;不可剥夺;保持申请;循环等待。l预先分配策略 思想：思想：进程在运行前运行前 一次性地一次性地向系统申请它所需要的全部资源，系统能满足呢，则一次性地将所请求的全部资源分配给申请进程；若系统当前不能满足进程的全部资源请求，则就不分配资源，此进程暂不投入运行。分析：分析：由于运行前运行前已经获得所需的全部资源，因而在运行期间不会再发出新的资源请求，所以不会发生占有资源占有资源又申请资源申请资源的现象，破坏了保持申请这一死锁必要条件，故死锁不发生。缺点：缺点：资源利用率低；有些资源有可能根本就不用；有可能发生饥饿。l有序资源分配将每个资源类按一定原则编号，进程对资源的申请应严格按照资源编号由小到大的次序来进行，即，当进程不占有任何资源时，它可以申请任何资源类ri中的任意多个资源实例，但此后它可以申请另外一个资源类rj中的若干资源实例的充要条件是:f(ri)f(rj);（函数f就是给资源序号的）若进程需要同一资源类中的若干个资源实例，这些应用有可能分散在进程的各个地方，但它必须在一个申请命令中同时发出请求。使用该预防死锁的策略时，资源类的编号应当仔细考虑，为了提高资源的利用率，通常应当按照大多数大多数进程使用使用资资源源的次序来给资源类编号，即先使用的先使用的或经经常使用的常使用的排在前面，后使用的后使用的或不不经经常使用的常使用的排在后面。l死锁的避免 对于进程对资源的请求进程对资源的请求进行动态地检测动态地检测，对处于安全状态安全状态的请求分配资源分配资源，不处于安全状态的请求不予分配资源，而让该进程等待，等到分给它资源也是安全状态时再把资源分给它。安全状态安全状态(safe state)safe state)：如果系统中的所有进程所有进程能够按照某一种次序依次地进行完，我们说系统处于安全状态。安全进程序列安全进程序列：系统中所有进程构成一个进程序列，若对于每一个进程pi(1in)，它以后需要的资源量不超过系统当前剩余资源量与所有进程pj(ji)(pi和pj都是进程序列中的两个进程)当前占有资源量之和，则称此进程序列此进程序列是安全的。思考题l设计一个涉及到线程互斥的问题，并将其解决？叙述问题，提供解决方案（使用互斥量、临界区）。