1、第三章 进程管理 v进程的定义、特征、进程控制的基本概念。进程的定义、特征、进程控制的基本概念。v进程进程PCB基本结构，作用及基本结构，作用及进程的状态及转换进程的状态及转换。v进程同步与互斥的基本概念和解决方法。进程同步与互斥的基本概念和解决方法。v几个经典的进程同步与互斥问题及算法几个经典的进程同步与互斥问题及算法。v进程通信的类型及实现方法进程通信的类型及实现方法v线程的基本概念及状态。线程的基本概念及状态。v难点难点：v进程的同步与互斥进程的同步与互斥本章重点：本章重点：v进程的基本概念进程的基本概念 v进程进程的的描述描述v进程的状态及其转换进程的状态及其转换 v进程控制进程控制
2、v进程互斥进程互斥v进程同步进程同步v进程通信进程通信 v线程线程v小结小结 3.1进程的概念 一、程序的顺序执行与特征一、程序的顺序执行与特征 1.程序：程序：完成一定功能的、按前后顺序执行的指令集完成一定功能的、按前后顺序执行的指令集合，它可以分成若干指令串。合，它可以分成若干指令串。2.程序的执行过程：程序的执行过程：S1:a=513.程序的顺序执行：程序的顺序执行：一个具有独立功能的程序独占处理机一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。直至最终结束的过程称为程序的顺序执行。Repeat IR pc Until CPU Halt 输入数据输入数据 输出结果输
3、出结果 计算计算ICPS2:b=a*5S4:d=a+b*b+c*2S3:c=a+bMpc pc+1 Execute（instruction IR）4.程序顺序执行的特征：程序顺序执行的特征：（1）顺序性：每一个操作都必须在上一个操作完成顺序性：每一个操作都必须在上一个操作完成之后开始之后开始内：语句之间、指令之间内：语句之间、指令之间外：程序之间外：程序之间（3）可再现性：可再现性：只要程序的运行环境及输入条件相只要程序的运行环境及输入条件相同，输出结果肯定相同。同，输出结果肯定相同。（2）封闭性：封闭性：资源独占，只有运行的程序能够改变资资源独占，只有运行的程序能够改变资源状态，每个程序的执
4、行不会受到外部因素的影响。源状态，每个程序的执行不会受到外部因素的影响。二、前趋图二、前趋图前趋图前趋图（Directed Acyclic Graph）：）：是一个有向非循环图，图中每个节点可以表示一条语句，是一个有向非循环图，图中每个节点可以表示一条语句，一个程序或进程，节点之间的有向边表示节点之间的前一个程序或进程，节点之间的有向边表示节点之间的前趋关系（趋关系（Precedence Relation）或半序关系（）或半序关系（Partial Order）（Pi，Pj）没有前趋的节点称为初始节点没有前趋的节点称为初始节点。=“”|Pj必须在必须在Pi完成之后开始执行完成之后开始执行 Pi称
5、为称为Pj的的直接前趋直接前趋，Pj称为称为Pi的的直接后继直接后继。如果：（如果：（Pi，Pj），则，则，Pi Pj 如果：如果：Pi Pk Pj Pi称为称为Pj的的前趋前趋，Pj称称为为Pi的的后继后继。没有后继的节点称为终止节点没有后继的节点称为终止节点。S1:a=51S2:b=a*5S4:d=b*b+c*2S3:c=a+6该图是否为前趋图？该图是否为前趋图？为什么？为什么？该图是否为前趋图？该图是否为前趋图？为什么？为什么？三、多道程序的并发执行与特征三、多道程序的并发执行与特征。1多道程序并发执行的逻辑分析多道程序并发执行的逻辑分析但对于多个程序，并不一定存在关系：但对于多个程序，
6、并不一定存在关系：Pi Ii+1可以：第一个程序的输入结束并开始计算时，第二个程序可以：第一个程序的输入结束并开始计算时，第二个程序的输入工作开始进行，从而第一个计算和第二个输入可以的输入工作开始进行，从而第一个计算和第二个输入可以并行进行。并行进行。IiCiPiI1I2C1I3C2P1I4p2P3C3Ii CiIi Ii+1Ci Ci+1Ci PiPi Pi+12多道程序并发执行的系统实现多道程序并发执行的系统实现处理器的主要功能是执行驻留在内存中的指令，为了处理器的主要功能是执行驻留在内存中的指令，为了提高效率，处理器可以同时执行多道程序。对于处理提高效率，处理器可以同时执行多道程序。对于
7、处理器而言，对全部指令的执行是按一定顺序进行的，这器而言，对全部指令的执行是按一定顺序进行的，这个顺序的改变是通过改变程序计数器（个顺序的改变是通过改变程序计数器（PC）或称为指）或称为指令指示器令指示器(IP)的值来完成的。的值来完成的。例：程序例：程序A的起始地址为的起始地址为51200，共，共12条指令；程序条指令；程序B的起始地址为的起始地址为81920，共，共4条指令，其中第条指令，其中第4条指令包条指令包括括I/O指令；程序指令；程序C的起始地址为的起始地址为194560，共，共12条指条指令；分派程序的起始地址为令；分派程序的起始地址为20480，共，共6条指令；三个条指令；三个
8、程序以及分派程序均在内存，操作系统每次执行程序以及分派程序均在内存，操作系统每次执行6条条用用户程序指令后就会自动终止当前用户程序，转去执行户程序指令后就会自动终止当前用户程序，转去执行分派程序。每条指令需要一个指令周期，则程序的执分派程序。每条指令需要一个指令周期，则程序的执行过程如下：行过程如下：7 20480 8 204819 20482102048311204841220485 13 8192014 8192115 81922 16 81923 I/O请求请求 1.512002.512013.512024.512035.512046.51205 超时超时1720480182048119
9、20482202048321204842220485231945602419456125194562261945632719456428194565超时超时29 2048030 2048131 2048232 2048333 2048434 2048535 5120636 5120737 5120838 5120939 5121040 5121141 2048042 2048143 2048244 2048345 2048446 2048547 19456648 19456649 19456750 19456851 19456952 1945703多道程序并发执行的定义多道程序并发执行的定义并
10、发执行：为了增强计算机系统的处理能力和提高资源的并发执行：为了增强计算机系统的处理能力和提高资源的利用率所采用的一种同时操作技术。利用率所采用的一种同时操作技术。使若干进程都处于已使若干进程都处于已经开始执行和尚未执行完成的状态。经开始执行和尚未执行完成的状态。多道程序的并发执行分两种情况多道程序的并发执行分两种情况:多道程序系统的程序执行环境变化引起的多道程序的并多道程序系统的程序执行环境变化引起的多道程序的并发执行发执行（多道程序系统环境下，各道程序在逻辑上独立，（多道程序系统环境下，各道程序在逻辑上独立，具备了执行的条件）。具备了执行的条件）。在某道程序的几个程序段中，包含着一部分可以同
11、时执在某道程序的几个程序段中，包含着一部分可以同时执行或顺序颠倒执行的代码。行或顺序颠倒执行的代码。4.多道程序并发执行的特征：多道程序并发执行的特征：（2）间断性：间断性：程序并发执行时，由于（程序并发执行时，由于（a）它们共享）它们共享软、硬件资源软、硬件资源(b)程序之间相互合作完成一项共同任程序之间相互合作完成一项共同任务，因而使程序之间相互制约。这种制约导致并发程务，因而使程序之间相互制约。这种制约导致并发程序具有序具有“执行执行-暂停暂停-执行执行”这种间断活动的特点。这种间断活动的特点。（1）失去了封闭性：失去了封闭性：多道程序相互影响。多道程序相互影响。（3）独立性：独立性：系
12、统把每个程序作为一个独立单位来进系统把每个程序作为一个独立单位来进行分配，并发程序在运行过程中，既然是作为一个独立行分配，并发程序在运行过程中，既然是作为一个独立的运行实体，它也必然具有作为一个单位去获得资源的的运行实体，它也必然具有作为一个单位去获得资源的独立性。独立性。（4）随机性：随机性：有可能失去可再现性，由于公用变量的存有可能失去可再现性，由于公用变量的存在，使程序由于微观上的执行顺序不同而产生不同的结在，使程序由于微观上的执行顺序不同而产生不同的结果。果。四、四、Bernstain条件条件。程序的不可再现性是绝对不允许的，为此，应采取程序的不可再现性是绝对不允许的，为此，应采取某种
13、措施使并发程序保持其可再现性。某种措施使并发程序保持其可再现性。Si、Sj:程序段或语句。程序段或语句。R（Si）：）：Si所涉及的读变量的集合。所涉及的读变量的集合。W（Si）：）：Si所涉及的写变量的集合。所涉及的写变量的集合。Si与与Sj可并发执行的条件：可并发执行的条件：R（Si）W（Sj）=R（Sj）W（Si）=W（Sj）W（Si）=同时成立同时成立 例：S1:C=X+Y+Z S2:D=C+XR(S1)=X,Y,Z R(S2)=C,X W(S1)=C W(S2)=D S1：x=x1+x2 S2：y=x1*x2 S3：z=(x+y)/2S4：w=z+5S5：m=w+1S6：m=m+1不
14、能并发！五、进程的定义五、进程的定义进程：进程：一个具有独立功能的程序对某个数据集合在处一个具有独立功能的程序对某个数据集合在处理机上的一次执行过程。理机上的一次执行过程。它是操作系统进行它是操作系统进行资源分配资源分配的基本单位。的基本单位。操作系统所应满足的主要要求都与进程有关：操作系统所应满足的主要要求都与进程有关：操作系统必须能够同时执行多个进程以最大限度地操作系统必须能够同时执行多个进程以最大限度地利用处理器，并为每个进程提供合适的响应时间。利用处理器，并为每个进程提供合适的响应时间。操作系统必须按一定的策略为进程分配资源并避免死锁。操作系统必须按一定的策略为进程分配资源并避免死锁。
15、操作系统应支持进程间的通信并能创建用户进程。操作系统应支持进程间的通信并能创建用户进程。操作系统的操作系统的主要职责就是控制进程的执行主要职责就是控制进程的执行。六、进程的特征六、进程的特征动态性：动态性：进程是程序的一次执行过程。因此，进程是程序的一次执行过程。因此，动态特动态特征是进程的最重要特征征是进程的最重要特征 并发性：并发性：只有建立了进程的程序才能并发执行，引入只有建立了进程的程序才能并发执行，引入进程的目的就是为了使它所对应的程序和其他进程并发进程的目的就是为了使它所对应的程序和其他进程并发执行，以提高系统资源的利用率。执行，以提高系统资源的利用率。独立性：独立性：每个进程都有
16、各自独立的功能。进程是一个每个进程都有各自独立的功能。进程是一个能独立运行的单位，也就是竞争计算机资源和进行处理能独立运行的单位，也就是竞争计算机资源和进行处理机调度的基本单位。机调度的基本单位。结构特征：结构特征：每个进程都配有一个每个进程都配有一个PCB，每个进程都有程，每个进程都有程序段、数据段和序段、数据段和PCB三部分组成。三部分组成。异步性（异步性（相互制约性）：由于进程之间的相互制约，使相互制约性）：由于进程之间的相互制约，使其具有执行的间断性。既：进程按各自独立的不可预知的其具有执行的间断性。既：进程按各自独立的不可预知的速度向前推进。速度向前推进。七、进程与程序的比较七、进程
17、与程序的比较状状态态存在存在方式方式所需所需资源资源包含关系包含关系并发并发 性性进程进程程序程序动动静静生命生命期短期短永久永久内存、外内存、外存、存、CPU外存外存进程包进程包含程序含程序程序不程序不包含进程包含进程有有无无3.2进程的描述PCB进程包括：程序段、数据段、进程包括：程序段、数据段、PCB二、二、PCB的内容：的内容：1.描述信息：描述信息：进程标识符（进程标识符（PID）或进程名）或进程名：用来唯一标识进程。：用来唯一标识进程。家族信息（家族信息（Family）：）：进程所属家族，即：进程的父进程所属家族，即：进程的父进程和子进程等。进程和子进程等。用户标识符（用户标识符（
18、UID）或用户名）或用户名：进程所属用户，利于：进程所属用户，利于进行资源共享和信息保护。进行资源共享和信息保护。一、作用：一、作用：PCB中包含了进程的中包含了进程的控制信息和描述信息控制信息和描述信息，是进程动态特征的集中体现。是进程动态特征的集中体现。PCB是系统感知进是系统感知进程存在的唯一标志。程存在的唯一标志。处理机状态处理机状态（CPU）：）：处理机的各种寄存器的内容，处理机的各种寄存器的内容，包括：通用寄存器（用户可视寄存器）、指令计数器、包括：通用寄存器（用户可视寄存器）、指令计数器、程序状态字、用户栈指针。程序状态字、用户栈指针。2.控制信息控制信息进程的状态（进程的状态（
19、Status）：进程所处的状态，就绪，：进程所处的状态，就绪，运行，等待。运行，等待。进程优先级（进程优先级（Priority）：处理机调度的依据，其：处理机调度的依据，其值取决于进程执行的紧迫程度以及进程占用值取决于进程执行的紧迫程度以及进程占用CPU的时间，占据内存时间、占据其他资源等情况的时间，占据内存时间、占据其他资源等情况 程序程序和数据和数据的起始地址（的起始地址（Start）：进程所对应的程：进程所对应的程序的起始地址。序的起始地址。通信信息（通信信息（Communication）：该进程在运行过：该进程在运行过程中与其他进程交换信息的情况。消息队列指针、信程中与其他进程交换信息
20、的情况。消息队列指针、信号量等号量等记时信息（记时信息（TIME）：记录进程等待：记录进程等待CPU的时间、已的时间、已占有占有CPU的时间等以及使用其他资源的时间的时间等以及使用其他资源的时间占内存大小，位置（占内存大小，位置（RAM）及其管理用数据结构。）及其管理用数据结构。外存交换区位置外存交换区位置（SWAP）共享区位置，大小共享区位置，大小（SHARE）打开文件情况打开文件情况（FILE）外设情况外设情况（DEVICE）PCB指针指针（PCBPtr）进程控制块进程控制块PCB是系统感知进程存在的唯一标志。是系统感知进程存在的唯一标志。系统对进程的各种操作通过对系统对进程的各种操作通过
21、对PCB的操作的操作实现。实现。三、三、进程进程组织：不同系统组织方式不同：组织：不同系统组织方式不同：链接、索引链接、索引四、四、存在区存在区：PCB的常用部分常驻内存系统区，其他的常用部分常驻内存系统区，其他部分放在外存。部分放在外存。执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针空闲队列指针空闲队列指针PCB1 4PCB2 3PCB3 0PCB4 8PCB5 PCB6 7PCB7 9PCB8 0PCB9 3.3进程的状态及其转换进程的状态及其转换一、进程的基本状态进程的基本状态 1.就绪状态（就绪状态（READY）：进程获得除处理机以外的所：进程获得除处理机以外的所 有
22、资源，等待处理机。有资源，等待处理机。2.运行状态（运行状态（RUNNING）：进程正在占有处理机，其对：进程正在占有处理机，其对应的程序正在处理机上运行。单处理机系统中，只能应的程序正在处理机上运行。单处理机系统中，只能有一个进程处于运行状态。有一个进程处于运行状态。3.等待状态等待状态/阻塞状态（阻塞状态（WAITING/BLOCKED）：进程：进程正在等待某件事情的发生无法继续运行下去而放弃正在等待某件事情的发生无法继续运行下去而放弃处理机。处理机。5.终止（终止（EXIT）：进程已正常或异常结束，被：进程已正常或异常结束，被OS从可运从可运行进程队列中释放出来行进程队列中释放出来 4.
23、创建创建/初始初始（NEW）：）：进程刚刚创建，还没有被处理进程刚刚创建，还没有被处理机提交到可运行进程队列中。机提交到可运行进程队列中。二、进程的状态转换：二、进程的状态转换：1三种状态的进程状态转换图三种状态的进程状态转换图 就 绪就 绪阻塞阻塞运行运行创建创建 进程调度进程调度 时间片到时间片到 I/O请求请求 I/O完成完成终止终止 2五种状态的进程状态转换图五种状态的进程状态转换图 就 绪就 绪阻塞阻塞运行运行准许准许 进程调度进程调度 时间片到时间片到 I/O请求请求 I/O完成完成 完成完成 初 始初 始终止终止3具有挂起状态的进程状态转换图具有挂起状态的进程状态转换图 活动活动
24、就绪就绪活动活动阻塞阻塞运行运行准许准许 进程调度进程调度 时间片到时间片到 等待某件事情等待某件事情 完成完成 初 始初 始终止终止静静止止就就绪绪静止静止阻塞阻塞 挂起挂起 激活激活 挂起挂起 激活激活 等待的事情发生等待的事情发生 等待的事情发生等待的事情发生 挂起挂起 3进程状态间转换关系表进程状态间转换关系表原状态原状态转换后状态转换后状态创建创建运行运行就绪就绪阻塞阻塞终止终止OS根据作业控制请求，根据作业控制请求，分时系统用户登录，分时系统用户登录，进程创建子进程进程创建子进程创建创建OS准备运行准备运行新进程新进程运行运行时间片到，时间片到，OS响应更响应更高优先级高优先级的进
25、程的进程OS服务请求，服务请求，资源请求，资源请求，事件请求。事件请求。进程完成进程完成进程夭折进程夭折就绪就绪被分派程序被分派程序选中选中被父进程终止被父进程终止阻塞阻塞事件发生事件发生被父进程终止被父进程终止说明：一般的操作系统为了管理方便，根据等待的事件设置多个说明：一般的操作系统为了管理方便，根据等待的事件设置多个阻塞队列，将等待不同事件的进程放在不同的等待队列中。阻塞队列，将等待不同事件的进程放在不同的等待队列中。3.4进程控制进程控制 进程控制：系统使用一些具有特定功能的程序来进程控制：系统使用一些具有特定功能的程序来创建创建、撤撤消消进程以及进程以及完成进程各状态间的转换完成进程
26、各状态间的转换，从而达到多进程、，从而达到多进程、高效率、并发执行和协调、实现资源共享的目的。高效率、并发执行和协调、实现资源共享的目的。实现进程控制的程序段被称作实现进程控制的程序段被称作进程控制原语进程控制原语。进程控制是通过进程控制是通过原语原语来实现。来实现。原语：用于完成某种特定功能的原语：用于完成某种特定功能的不可分割的一段程序不可分割的一段程序。原语的实现是通过原语的实现是通过关中断关中断来实现的。来实现的。一、内核：一、内核：1.什么是内核什么是内核?在设计在设计OS时把一些时把一些与硬件紧密相关的模块与硬件紧密相关的模块或或运行频率较运行频率较高的模块高的模块以及被以及被许多
27、模块所公用许多模块所公用的一些基本操作，安排在的一些基本操作，安排在靠近硬件靠近硬件的层次中，并使他们的层次中，并使他们常驻内存常驻内存，以提高，以提高OS的运的运行效能，通常把这部分叫行效能，通常把这部分叫OS的内核。的内核。2.内核的基本功能：内核的基本功能：中断处理中断处理:在在OS中，中，中断处理中断处理既是内核既是内核最基本功能最基本功能也是也是整个整个OS赖以活动的基础，在内核中对中断进赖以活动的基础，在内核中对中断进行行”有限的处理有限的处理”然后便转去相关的进程继续然后便转去相关的进程继续处理。应该说处理。应该说OS的重要活动最终都将依赖于的重要活动最终都将依赖于中断中断的的进
28、程调度、设备驱动、系统调用进程调度、设备驱动、系统调用等等。等等。进程管理进程管理:进程的建立与撤消进程的建立与撤消 进程状态的转换进程状态的转换 进程调度进程调度 控制进程的并发执行控制进程的并发执行 资源管理中的基本操作：资源管理中的基本操作：如：时钟管理、如：时钟管理、I/O管理管理文件系统的管理等（设备文件系统的管理等（设备驱动程序、例程处理程序等）驱动程序、例程处理程序等）1.创建原语创建原语创建方式有两种：创建方式有两种：（1）系统程序创建：）系统程序创建：（2）父进程创建：）父进程创建：进程的层次结构进程的层次结构096050850350250101二二、原语原语：（1）用户登录
29、）用户登录（2）作业调度）作业调度 引起引起进程进程创建的事件创建的事件 创建原语的功能：创建原语的功能：从系统中申请一第从系统中申请一第PCB表，为进程分配资源，填表，为进程分配资源，填PCB表，表，其中状态为其中状态为”就绪状态就绪状态”，把，把PCB插入到就绪队列中。插入到就绪队列中。（3）提供服务：例如，用户程序提出打印服务请求）提供服务：例如，用户程序提出打印服务请求（4）应用请求：用户程序建立键盘输入程序完成自身需）应用请求：用户程序建立键盘输入程序完成自身需要的数据输入任务。这种情况是由用户程序自己建立子进要的数据输入任务。这种情况是由用户程序自己建立子进程。程。开始开始查查PC
30、B链表链表有空有空PCB吗？吗？取一个取一个PCB，获得该，获得该PCB的的PID为进程分配资源为进程分配资源将将PID挂入其家族链挂入其家族链返回返回失败失败无无有有置置“就绪就绪”状态，入就绪队状态，入就绪队列列填入入口参数填入入口参数2.撤销原语撤销原语撤消时机：撤消时机：该进程完成了所有的任务而该进程完成了所有的任务而正常结束正常结束由于错误而导致由于错误而导致非正常结束非正常结束地址越界：访问其它进程的存储区地址越界：访问其它进程的存储区保护错：进程试图访问不允许访问的资源保护错：进程试图访问不允许访问的资源非法指令：程序试图执行一条不存在的指令非法指令：程序试图执行一条不存在的指令
31、特权指令错：用户进程试图执行特权指令错：用户进程试图执行OS指令指令运行超时：进程的执行时间超过了指定最大值。运行超时：进程的执行时间超过了指定最大值。等待超时：等待某件事时间超过了规定的最大值等待超时：等待某件事时间超过了规定的最大值算术运算错：被零除算术运算错：被零除I/O故障故障外界干预外界干预祖先进程撤消某个子进程祖先进程撤消某个子进程父进程终止父进程终止操作员或操作系统干预操作员或操作系统干预2.撤销原语撤销原语功能：将该进程的所有子进程撤消，然后撤消本进程，功能：将该进程的所有子进程撤消，然后撤消本进程，将进程占有的所有资源收回后，把将进程占有的所有资源收回后，把PCB收回，挂到空
32、收回，挂到空PCB链表上。链表上。入口查进程查进程PCB链表或进程家族链表或进程家族有此有此PCB吗？吗？释放释放PCB结构结构返回返回错误处理错误处理无无有有释放该进程所占资源释放该进程所占资源 该该PCB有有 子进程吗？子进程吗？有有无无处理子进程处理子进程3.阻塞原语阻塞原语引起阻塞的事件：引起阻塞的事件：请求系统服务：正在执行的进程请求操作系统提供服请求系统服务：正在执行的进程请求操作系统提供服务，操作系统不能立即满足进程要求。务，操作系统不能立即满足进程要求。启动某种操作：进程启动某种操作且必须等该操作完启动某种操作：进程启动某种操作且必须等该操作完成后进程才能继续运行。成后进程才能
33、继续运行。新数据尚未到达：进程运行时需要处理的数据还未送新数据尚未到达：进程运行时需要处理的数据还未送达。达。无新工作可以做：具有一定功能的进程完成某任务后，无新工作可以做：具有一定功能的进程完成某任务后，没有新任务布置下来。没有新任务布置下来。功能：中断处理机，保护现场，状态由功能：中断处理机，保护现场，状态由“执行执行”改为改为“等待等待”，将，将PCB从运行状态转到从运行状态转到WQ中。中。阻塞原语是进程等待某件事情的发生，而该事情又不具阻塞原语是进程等待某件事情的发生，而该事情又不具备发生条件时，进程备发生条件时，进程自己调用阻塞原语自己调用阻塞原语将自己阻塞起来。将自己阻塞起来。入口
34、置该进程状态为置该进程状态为“WAIT”转进程调度转进程调度被阻塞进程入等待队列被阻塞进程入等待队列保护当前进程的保护当前进程的CPU现场现场4.唤醒唤醒原语原语功能：状态由功能：状态由“等待等待”改为改为“就绪就绪”，将，将PCB从等待队从等待队列中插入列中插入RQ中。中。等待该事件的进程将被唤醒，由等待该事件的进程将被唤醒，由系统进程系统进程唤醒或由唤醒或由其他其他进程进程唤醒。唤醒。入口置该进程状态为置该进程状态为“READY”转进程调度或返回转进程调度或返回被阻塞进程入就绪队列被阻塞进程入就绪队列从等待队列中摘下被唤醒进程从等待队列中摘下被唤醒进程一、并发进程之间的基本关系一、并发进程
35、之间的基本关系 1.互斥互斥：不允许两个以上的并发进程同时使用某种资源：不允许两个以上的并发进程同时使用某种资源2.同步同步：是指对多个相关进程在执行次序上的协调。：是指对多个相关进程在执行次序上的协调。OS的的核心任务核心任务就是解决进程的就是解决进程的同步与互斥同步与互斥。用于保证这种关系的机制称为进程同步机制。用于保证这种关系的机制称为进程同步机制。例：例：互斥互斥的进程之间的进程之间无逻辑无逻辑关系，关系，同步同步的进程之间的进程之间有逻辑有逻辑关系。关系。无论同步还是互斥，进程间都有一种无论同步还是互斥，进程间都有一种制约制约关系。关系。“该走该走就走，该停就停就走，该停就停”。互斥
36、互斥的进程之间存在着的进程之间存在着间接制约间接制约关系：进程关系：进程资源资源进程进程同步同步的进程之间存在着的进程之间存在着直接制约直接制约关系。关系。iaaiii10110013.5进程互斥进程互斥3.5.1 资源共享所引起的制约资源共享所引起的制约二、临界区二、临界区CS（Critical Section）1.临界资源临界资源CR（Critical Resources）：）：一次只允许一个进程访一次只允许一个进程访问的资源问的资源，等一个进程完全用完后，另一个进程才能使用。，等一个进程完全用完后，另一个进程才能使用。如：打印机、变量、堆栈指针、队列指针如：打印机、变量、堆栈指针、队列指
37、针临界区：每个进程中访问临界资源的代码段。临界区：每个进程中访问临界资源的代码段。X=X+1000LOAD A，XADDI A，1000STORE A，XX=X-100LOAD A，XMINUS A，100STORE A，X500 x申请区申请区临界区临界区退出区退出区 空闲让进：空闲让进：当当CS为空时，必须允许要求进入为空时，必须允许要求进入CS的的进程进入进程进入CS以有效利用资源。以有效利用资源。临界区的使用规则：临界区的使用规则：忙则等待：忙则等待：当某进程处于当某进程处于CS时，其它想进入者必须时，其它想进入者必须等待，以保证互斥使用等待，以保证互斥使用CS。让权等待：让权等待：对
38、于等待进入对于等待进入CS的进程，必须释放处理的进程，必须释放处理机，避免机，避免“忙等忙等”有限等待：有限等待：对要求进入对要求进入CS的进程，应在有限时间内的进程，应在有限时间内使之进入，避免使之进入，避免“死等死等”三、两个任务的解决方案三、两个任务的解决方案01turnTurn=0?取球取球打球打球Turn=1离开离开Turn=1?取球取球打球打球Turn=0离开离开01Flag0FLAG1=T?取球取球打球打球FLAG0=F离开离开FLAG0=T?取球取球打球打球FLAG1=F离开离开Flag1FLAG0=TFLAG1=T三、两个任务的解决方案三、两个任务的解决方案有没有更好的方案？
39、有没有更好的方案？三、两个任务的解决方案三、两个任务的解决方案任务描述任务描述:(Worker Thread)public class Worker extends Thread public Worker(String n,int i,MutualExclusion s)name=n;id=i;shared=s;public void run()while(true)shared.enteringCriticalSection(id);System.out.println(name+”is in CS”);MutualExclusion.criticalSection();shared.le
40、avingCriticalSection(id);System.out.println(name+”is out of CS”);MutualExclusion.nonCriticalSection();private String name;private int id;private MutualExclusion shared;MutualExclusion abstract classpublic abstract class MutualExclusion public static void criticalSection()try Thread.sleep(int)(Math.r
41、andom()*TIME);catch(InterruptedException e)public static void nonCriticalSection()try Thread.sleep(int)(Math.random()*TIME);catch(InterruptedException e)public abstract void enteringCriticalSection(int t);public abstract void leavingCriticalSection(int t);public static final int TURN_0=0;public stat
42、ic final int TURN_1=1;public static final int TIME=3000;TestAlgorithm classpublic class TestAlgorithm public static void main(String args)MutualExclusion alg=new Algorithm_1();Worker first=new Worker(“Runner 0”,0,alg);Worker second=new Worker(“Runner 1”,1,alg);first.start();second.start();1.Algorith
43、m 1public class Algorithm_1 extends MutualExclusion public Algorithm_1()turn=TURN_0;public void enteringCriticalSection(int t)while(turn!=t)Thread.yield();public void leavingCriticalSection(int t)turn=1-t;private volatile int turn;2.Algorithm 2Algorithm 1的问题是只记录允许哪些进程进入临界区，的问题是只记录允许哪些进程进入临界区，没记录关于进程
44、目前所处状态的信息，解决办法：没记录关于进程目前所处状态的信息，解决办法：用用boolean flag=new boolean2代替变量代替变量turnFlagi=true表示进程表示进程i准备进入临界区准备进入临界区public class Algorithm_2 extends MutualExclusion public Algorithm_2()flag0=false;flag1=false；public void enteringCriticalSection(int t)int other；other=1-t；flagt=true；while(（flagother=true)Thr
45、ead.yield();public void leavingCriticalSection(int t)flagt=false;Private volatile boolean flag=new boolean2;3.Algorithm 3Algorithm 2的问题是只记录关于进程目前所处状态的的问题是只记录关于进程目前所处状态的信息，解决办法：信息，解决办法：用用boolean flag=new boolean2 和变量和变量turn一起控一起控制并发过程。制并发过程。Flagi=true表示进程表示进程i准备进入临界区准备进入临界区public class Algorithm_3 ex
46、tends MutualExclusion public Algorithm_3()flag0=false;flag1=false；turn=TURN_0;public void enteringCriticalSection(int t)int other；other=1-t；flagt=true；turn=other；while(（flagother=true)&(turn=other)Thread.yield();public void leavingCriticalSection(int t)flagt=false;Private volatile int turn;Private v
47、olatile boolean flag=new boolean23.5.2 互斥的加锁实现互斥的加锁实现1.实现原理实现原理当并发进程申请进入临界区时首先测试临界区是否是上当并发进程申请进入临界区时首先测试临界区是否是上锁的，如果锁上了，就等待；锁的，如果锁上了，就等待；否则，上锁，进入临界区。否则，上锁，进入临界区。当某个进程进入临界区之后，将临界区锁上，直到他退出当某个进程进入临界区之后，将临界区锁上，直到他退出临界区为止。临界区为止。3.实现代码：实现代码：加锁加锁TS（lock）TS locklock TRUE解锁解锁unlock（Lock）Lock FALSELock=FALSE表
48、示临界区可用，表示临界区可用，Lock=TRUE表示临界区不可用。表示临界区不可用。设控制临界区的锁变量为：设控制临界区的锁变量为：Lock，初始为，初始为FALSEPAA:While TS（Lock）DO SKIP;CSunlock（Lock）GOTO APBB:While TS（Lock）DO SKIP;CSunlock（Lock）GOTO BPCC:While TS（Lock）DO SKIP;CSunlock（Lock）GOTO C4.加锁机制存在的问题加锁机制存在的问题 循环等待造成资源浪费循环等待造成资源浪费 对于同步问题灵活性不够对于同步问题灵活性不够 可能造成不公平可能造成不公平
49、3.5.3 信号量和信号量和P、V操作操作1.信号量（信号量（Semaphore）（1）信号量是一个整型变量）信号量是一个整型变量（2）与一个资源有关）与一个资源有关（3）只能进行）只能进行P操作和操作和V操作（初始化除外）操作（初始化除外）2.P操作：申请资源操作：申请资源P(S:Semaphore)s=s 1;if(s0)w(s);/*阻塞原语阻塞原语*/3.V操作：释放资源操作：释放资源V(S:Semaphore)s=s+1;if(s=0)R(s);/*唤醒原语唤醒原语*/P、V操作本身都是原语操作操作本身都是原语操作3.5.4 信号量解决互斥关系信号量解决互斥关系 例：例：SP=1 打
50、印机打印机P1P(SP)使用打印机使用打印机 V（SP）P2P(SP)使用打印机使用打印机 V（SP）P3P(SP)使用打印机使用打印机 V（SP）临界区不是原语可以被中断。5台打印机怎么办？台打印机怎么办？信号量信号量S值的含义：值的含义：（1）S0表示可用资源数表示可用资源数（2）S0）个单元的缓冲）个单元的缓冲区，区，P1每次用每次用produce()生成一个正整数并用生成一个正整数并用put()送送入缓冲区的某一空单元中；入缓冲区的某一空单元中；P2每次用每次用getodd()从该缓从该缓冲区中取出一个奇数并用冲区中取出一个奇数并用countodd()统计奇数个数；统计奇数个数；P3每
