1、第二章第二章 进程管理进程管理进程的概念进程的概念进程的控制进程的控制进程同步及经典同步问题进程同步及经典同步问题进程间的高级通信进程间的高级通信进程与线程的区别进程与线程的区别CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 22.1 前趋图和程序执行前趋图和程序执行前趋图的定义前趋图的定义前趋图（前趋图（Procedence Graph）是一个有向）是一个有向无循环图无循环图DAG（Directed Acyclic Graph）。）。结点：语句、程序段或进程。结点：语句、程序段或进程。初始节点初始节点终止节点终止节点边：执行顺序。边：执行顺序。重量：程序量或执行时间。重量
2、：程序量或执行时间。CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 31234567例：有例：有7个结点的前趋图。个结点的前趋图。P=P1，P2，P3，P4，P5，P6，P7 =（P1，P2），（P1，P3），（P1，P4），（P2，P5），（P3，P5），（P4，P6），（P5，P7），（P6，P7）2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 4程序的顺序执行程序的顺序执行一个复杂的程序通常可以分为若干程序一个复杂的程序通常可以分为若干程序段，并且必须按照某种先后次序来执行。段，并且必须按照某种先后次序来执行。
3、例例1：输入：输入计算计算打印打印例例2：语句执行顺序：语句执行顺序S1：a：=x+yS2：b：=a 5S3：c：=b+12.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 5顺序执行程序的特点：顺序执行程序的特点：程序的顺序性。程序的顺序性。程序在运行时独占主机资源。程序在运行时独占主机资源。程序的执行结果与其执行速度无关。程序的执行结果与其执行速度无关。程序执行时的初始条件相同，其结程序执行时的初始条件相同，其结果必相同。果必相同。2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理
4、6程序的并发执行程序的并发执行程序执行环境程序执行环境独立性，逻辑上是独立的。独立性，逻辑上是独立的。随机性：输入和执行开始时间都是随机的。随机性：输入和执行开始时间都是随机的。资源共享：资源共享导致对进程执行速度资源共享：资源共享导致对进程执行速度的制约。的制约。2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 7程序的并发执行程序的并发执行 并发执行是指两个程序执行时间上是重叠并发执行是指两个程序执行时间上是重叠的。凡是能由一组并发程序完成的任务，都的。凡是能由一组并发程序完成的任务，都能由相应的单个程序完成。能由相应的单个程序完成。
5、例例1：有一批程序，而每个程序需输入，计算，：有一批程序，而每个程序需输入，计算，打印三项操作。其程序段并发执行的前趋图打印三项操作。其程序段并发执行的前趋图:I1 I2 I3 I4 C1 C2 C3 C4 P1 P2 P3 P4 2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 8 例2Begin integer N:=0;CobeginProgram A:begin Program B:beginL1:N:=N+1;L2:Print(N);N:=0;Goto L1；Goto L2；End EndCoendEnd当当N=5时，如果时，如
6、果 N=N+1 在在 print（N）和）和 N:=0前前中间中间后后打印打印655执行后执行后N=0012.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 9例例3设有堆栈设有堆栈S，栈指针，栈指针top，栈中存放相应的数，栈中存放相应的数据块地址，程序据块地址，程序 popaddr（top）从栈中取地址，）从栈中取地址，pushaddr（blk）将地址放入栈）将地址放入栈S中。中。void popaddr(top)void pushaddr(blk)top-;*top=blk;r=*top;top+;return(r)先执行先执行 po
7、paddr 的的top-，接着执行，接着执行pushaddr的的*top=blk2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 10程序并发执行过程及条件程序并发执行过程及条件（Bernstein条件）条件）S0;CobeginS1；S2；S3；Sn;CoendSn+1;S1、S2、Sn可以由同一程序段可以由同一程序段中的不同语句组成。中的不同语句组成。2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 11 将任一语句划分为两个变量的集合将任一语句划分为两个变量的集合R（Si）和）
8、和W（Si）:读读集集R（Si）=a1，a2，am写集写集W（Si）=b1，b2，bn 如对语句如对语句S1和和S2有：有：R（S1）W（S2）=W（S1）R（S2）=W（S1）W（S2）=成立，则语句成立，则语句S1和和S2可并发执行。可并发执行。2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 12例例1 语句语句 c=a b 和和 w=c+1R（c=a b）=a,b W（c=a b）=c R（w=c+1）=c W（w=c+1）=w R（w=c+1）W（c=a b）=c 语句语句 c=a b 和和 w=c+1 不能并发执行。不能并发执
9、行。2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 13例例2 S1:a=x+y S2:b=z+1S3:c=a b S4:w=a+c+1 R（S1）=x,y W（S1）=a R（S2）=z W（S2）=b R（S3）=a,b W（S3）=c R（S4）=a,c W（S4）=w 语句语句 S1 和和 S2 能并发执行。能并发执行。语句语句 S1 和和 S3，S2 和和S3，S3 和和S4 不能并发执行。不能并发执行。S1 S3 S4 S22.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管
10、理 14资源共享资源共享资源共享是指系统中的硬件资源和资源共享是指系统中的硬件资源和软件资源不再由单个用户所独占，而软件资源不再由单个用户所独占，而为为 n 个用户共同使用。个用户共同使用。由系统进行统一分配（硬件）和由由系统进行统一分配（硬件）和由程序自行使用（数据集，变量、队列程序自行使用（数据集，变量、队列等）等）程序并发执行与资源共享之间互为程序并发执行与资源共享之间互为存在条件。存在条件。2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 15程序并发执行的特点程序并发执行的特点失去程序的封闭性和可再现性失去程序的封闭性和可再现性
11、程序与计算不再一一对应程序与计算不再一一对应程序并发执行的相互制约程序并发执行的相互制约执行执行暂停暂停执行执行2.1前趋图和程序执行前趋图和程序执行CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 162.2 进程的概念进程的概念进程的定义进程的定义进程的定义进程的定义:进程是程序在一个数据集进程是程序在一个数据集合上的运行过程，是系统进行资源分配合上的运行过程，是系统进行资源分配和调度的一个独立的基本单位。和调度的一个独立的基本单位。进程的特征进程的特征动态性动态性并发特征并发特征独立特征独立特征异步特征异步特征机构特征机构特征CUIT 叶斌叶斌2023-2-12 11:
12、50操作系统|进程管理 17进程与程序的关系进程与程序的关系进进 程程 程程 序序 概念概念 动态实体，动态实体，静态实体，静态实体，强调执行过程强调执行过程 是指令的有序集合是指令的有序集合 特征特征 并发性、独立性、并发性、独立性、无并行特征，无并行特征，异步性，异步性，是静止的是静止的 是竞争计算机系统是竞争计算机系统 资源的基本单位资源的基本单位两者联系两者联系 不同的进程可以共享同一个程序，不同的进程可以共享同一个程序，只要对应的数据集不同只要对应的数据集不同2.2 进程的概念进程的概念CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 18进程的组成（进程上下文）进
13、程的组成（进程上下文）PCB程序程序 数据数据进程控制块进程控制块PCB描述信息描述信息控制信息控制信息资源管理信息资源管理信息CPU现场保护：对现场保护：对CPU的处理的处理2.2 进程的概念进程的概念CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 19PCB的组织方式的组织方式链接方式链接方式将具有相同状态的将具有相同状态的PCB，用其中的链接，用其中的链接字，链接成一个队列。字，链接成一个队列。2.2 进程的概念进程的概念CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 20索引方式索引方式根据进程的状态，建立索引表。根据进程的状态，建立索引表。CU
14、IT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 21 2.3进程状态及其控制进程状态及其控制进程状态进程状态 一个进程的生命期可以划分为一组状一个进程的生命期可以划分为一组状态，这些状态刻画了这个进程。系统根据态，这些状态刻画了这个进程。系统根据PCB结构中的状态值控制进程。结构中的状态值控制进程。就绪状态（就绪状态（Ready）执行状态（执行状态（Running）等待状态（阻塞状态等待状态（阻塞状态Blocked）新（新（New）状态）状态终止状态（终止状态（Terminated or Exit）CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 22挂起状态
15、（挂起状态（Suspend）把一个进程挂起使之处于静止状把一个进程挂起使之处于静止状态，以便研究它的执行情况获对它进态，以便研究它的执行情况获对它进行修改。行修改。用户终端需要；用户终端需要；父进程的需要：考查、修改获协调各子父进程的需要：考查、修改获协调各子进程时；进程时；OS的需要：改善系统运行性能，调节负的需要：改善系统运行性能，调节负荷；荷；对换的需要：缓和内存紧张的情况；对换的需要：缓和内存紧张的情况；2.3进程状态及其控制进程状态及其控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 23进程状态转换进程状态转换三种基本状态：执行状态（Executing）就绪状
16、态（Ready）阻塞状态（Blocked）或等待（Wait）阻塞阻塞状态状态就绪就绪状态状态 执行执行状态状态调度调度I/O请求请求进程进程唤醒唤醒时间时间片到片到新状态新状态结束结束后备队列后备队列新状态新状态结束状态结束状态2.3进程状态及其控制进程状态及其控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 24CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 25细化的进程状态图（增加挂起）细化的进程状态图（增加挂起）活动活动阻塞阻塞执行执行状态状态活动活动就绪就绪静止静止就绪就绪静止静止阻塞阻塞调度调度唤醒唤醒I/O请求请求激活激活激活激活挂起挂起
17、挂起挂起挂起挂起唤醒唤醒2.3进程状态及其控制进程状态及其控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 26活动就绪（活动就绪（Readya）和活动阻塞（）和活动阻塞（Blockeda）静止就绪（静止就绪（Readys）和静止阻塞（）和静止阻塞（Blockeds）2.3进程状态及其控制进程状态及其控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 27一个状态转换和进程转换的例子一个状态转换和进程转换的例子进程进程AI/O驱动驱动中断处理中断处理进程进程BI/O现场保护现场保护和阻塞和阻塞A启动启动I/O调度，恢调度，恢复复B现场现场I/O中断现场
18、保护现场保护中断处理中断处理A就绪就绪调度，恢调度，恢复复A现场现场退出退出（收回（收回资源，资源，调度）调度）注：红色表示处于注：红色表示处于“管态管态”2.3进程状态及其控制进程状态及其控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 28 2.4进程控制进程控制进程间的关系进程间的关系非结构系统（非结构系统（Unstructured System）树形结构系统（树形结构系统（Tree-Structured System）:一个进程能创建另一个进程，形成一个进程能创建另一个进程，形成进程家族。进程家族。CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理
19、 29操作系统内核操作系统内核（Kernel）支撑功能支撑功能中断处理中断处理时钟管理时钟管理原语操作：完成特定功能的一段程原语操作：完成特定功能的一段程序。原语在执行期间是不可分割的。序。原语在执行期间是不可分割的。资源管理功能资源管理功能进程管理进程管理存储器管理存储器管理设备管理设备管理 2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 30进程的创建进程的创建引起进程创建的事件引起进程创建的事件用户登录用户登录作业调度作业调度提供服务提供服务应用请求应用请求(应用程序创建应用程序创建)创建过程创建过程 Create()申请空白申请空白PCB：新标
20、识和：新标识和PCB为新进程分配资源：批处理型和交互型为新进程分配资源：批处理型和交互型作业作业初始化进程控制块初始化进程控制块新进程插入就绪队列新进程插入就绪队列CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 31创建原语（创建原语（Create Primitive）Void Create(n,S0,P0,M0,R0,acc)i=getinternal name(n);id(i)=n;priority(i)=P0;cpupstate(i)=S0;main store(i)=M0;resources(i)=R0;status(i)=“readys”;set accounti
21、ng data;insert(RL,i);2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 32进程的终止进程的终止进程终止的事件进程终止的事件正常结束：正常结束：Holt指令（引发中断）指令（引发中断）异常结束：异常结束：越界错误越界错误保护错保护错非法指令错非法指令错特权指令错特权指令错运行超时运行超时等待超时等待超时算术运算错算术运算错I/O故障故障外界干预：人工或系统干预、父进程请外界干预：人工或系统干预、父进程请求、父进程终止求、父进程终止CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 33撤消原语（撤消原语（Destroy
22、 Primitive）Void destroy(n)sched=false;i=getinternal name(n);Kill(i);If sched then scheduler;2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 34Kill过程：过程：1、从、从PCB中读出进程状态；中读出进程状态；2、终止进程并设置调度标志为真；、终止进程并设置调度标志为真；3、终止所有子进程；、终止所有子进程；4、释放拥有的全部资源并归还父进、释放拥有的全部资源并归还父进程或系统；程或系统；5、将终止进程从所在队列（、将终止进程从所在队列（PCB）中移出中移出C
23、UIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 35进程阻塞进程阻塞引起进程阻塞的事件引起进程阻塞的事件1、请求系统服务、请求系统服务2、启动某种操作、启动某种操作3、数据尚未到达、数据尚未到达4、无新工作可做、无新工作可做阻塞原语的主要工作阻塞原语的主要工作停止目前工作，存停止目前工作，存CPU下场到下场到PCB中；中；将将PCB中的现行状态由中的现行状态由“执行执行”改为改为“阻塞阻塞”；将将PCB插入相应的阻塞队列中插入相应的阻塞队列中将将CPU的控制权交下一就绪状态的进程的控制权交下一就绪状态的进程 2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:5
24、0操作系统|进程管理 36阻塞原语（阻塞原语（Block Primitive）Void block(n)i=getinternal name(n);stop(i);status(i)=“blockeda”;insert(WL(r),i);scheduler;2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 37进程的唤醒进程的唤醒进程唤醒的事件进程唤醒的事件唤醒原语（唤醒原语（Wakeup Primitive）Void wakeup(n)i=getinternal name(n);remove(WL(r),i);status=“ready”;insert
25、(RL,i);scheduler;2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 38进程的挂起进程的挂起（Suspend）挂起方式挂起方式1、把发出本原语的进程自身挂起；、把发出本原语的进程自身挂起；2、挂起指定进程名（子进程）的进程；、挂起指定进程名（子进程）的进程；3、把某进程及其全部或部分子孙一起挂起。、把某进程及其全部或部分子孙一起挂起。挂起操作挂起操作检查被挂起进程的状态，根据原状态设置挂检查被挂起进程的状态，根据原状态设置挂起后的状态起后的状态把把PCB复制到特定的内存区域复制到特定的内存区域若挂起前该进程正在执行，则由调度程序进若挂起前
26、该进程正在执行，则由调度程序进行重新调度。行重新调度。2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 39方式方式2挂起原语（挂起原语（Suspend Primitive）Void suspend(n,a)i=getinternal name(n);s=status(i);if s=“executing”then stop(i);a=copy PCB(i);status(i)=if s=“blockeda”then “blockeds”;else “readys”;if s=“executing”then scheduler;2.4进程控制进程控制CU
27、IT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 40进程的激活进程的激活进程激活过程进程激活过程激活原语（激活原语（Activate Primitive）由创建原语创建的进程处于由创建原语创建的进程处于“静止静止就绪就绪“状态，后跟一个激活原语，使状态，后跟一个激活原语，使之变为活跃就绪，就能引起之变为活跃就绪，就能引起CPU的的重新调度。重新调度。2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 41Void activate(n)i=getinternal name(n);status(i)=if status=“readys”the
28、n “readya”;else “blockeda”;if status(i)=“readya”then scheduler;2.4进程控制进程控制CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 42 2.5 进程同步进程同步并发引起的操作系统的改变并发引起的操作系统的改变操作系统必须记住各种活跃的进程操作系统必须记住各种活跃的进程必须为每个进程分配和释放各种资源必须为每个进程分配和释放各种资源保护每个进程的数据和物理资源保护每个进程的数据和物理资源进程的结果必须与执行速度无关进程的结果必须与执行速度无关CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 4
29、3进程间的制约进程间的制约进程中的资源竞争（间接）进程中的资源竞争（间接）进程间通过共享的合作（直接）进程间通过共享的合作（直接）进程间通过通信的合作（直接）进程间通过通信的合作（直接）进程间的制约临界区进程间的制约临界区临界资源（临界资源（Critical Resource）：）：一次仅允许一个进程使用的资源。一次仅允许一个进程使用的资源。2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 44例例1：两个进程对同一变量：两个进程对同一变量count访问和修改，访问和修改，P1：count+=1;P2：count-=1;若若 count=5。P1：R1=
30、count;R1=R1+1;count=R1;P2：R2=count;R2=R2-1;count=R2;若顺序执行若顺序执行P1、P2，则，则count=5。2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 45P1：R1=count;P1：R1=count;P2：R2=count;R1=R1+1;P1：R1=R1+1;P2：R2=count;count=R1;R2=R2 1;P2：R2=R2 1;count=R2;count=R2;P1：count=R1;若执行顺序如上，若执行顺序如上，若执行顺序如上，若执行顺序如上，则则count=4则则count=
31、6。2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 46与时间有关的错误与时间有关的错误:理发师问题理发师问题发师床X顾客床Y理发馆理发椅顾客床有人唤醒顾客理发去发师床睡NY被唤醒理发师发师床有人唤醒发师理发去顾客床睡NY被唤醒顾客床有人离开NY顾客理发师 读Y 顾客 读Y 写X 读X 写YCUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 47 cobegin process 1;process 2：coend 2.5进程同步进程同步临界区：不允许多个并发进程交叉执行的一段程序临界区：不允许多个并发进程交叉执行的一段程序process
32、 1：begin L1：entry section CS1;exit section Remainder of rocess 1;Goto L1;endprocess 2：begin L2：entry section CS2;exit section Remainder of rocess 2;Goto L1;endCUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 48互斥互斥不允许两个以上的共享该资源的并发进程不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。同时进入临界区称为互斥。临界区调度原则临界区调度原则空闲让进空闲让进忙则等待忙则等待有限等待有限等待让权等
33、待让权等待 2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 49 互斥的软件实现互斥的软件实现 算法算法1:进程进程Pi，Pj共享临界资源共享临界资源R。Turn：进程编号。：进程编号。算法算法1：共享一个公用整型变量共享一个公用整型变量turnvoid Pi()while(true)while (turn!=i );/资源被资源被j进程用，空转进程用，空转 critical section turn=j;/把资源控制权交给把资源控制权交给j remainder section 2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作
34、系统|进程管理 50算法算法2：用数组代替算法一中的用数组代替算法一中的turnint flag n=0,0,0;void Pi()while(true)for(j=0;jn;j+)if (flagj)j=0;/资源被用，空转资源被用，空转 flagi=1;/让让i 进程获得资源进程获得资源 critical section flagi=0;/放弃资源控制权放弃资源控制权 remainder section 2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 51算法算法3：int flag n=0,0,0;void Pi()while (true)fla
35、gi=1;for(j=0;jn;j+)if (flagj)j=0;critical section flagi=0;remainder section 2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 52算法算法4：进程共享两个公用变量进程共享两个公用变量boolean flag=new boolean 2;int turn=0;public void P0()while(true)flag 0=true;turn=1;while(flag 1&turn=1)；;flag 0=false;public void P1()while(true)flag
36、1=true;turn=0;while(flag 0&turn=0);flag 1=false;；2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 53public static void main()flag 0=false;flag 1=false;parbegin(P0,P1);2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 54算法算法5：对临界区：对临界区S设置一个变量状态设置一个变量状态W，W=0表示资源可用，表示资源可用，W=1表示资源已被占用。表示资源已被占用。例：例：Begin integer
37、W=0;CogeginBeginL1：lock W;CS1;Unlock W;Remainder of process 1;Goto L1;EndBeginL2：lock W;CS2;Unlock W;Remainder of process 2;Goto L2;EndCoend End 2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 55关锁原语关锁原语lock W：if W=1 thenbeginblock(n);insert(WL,n);scheduler;endelseW=1;2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:5
38、0操作系统|进程管理 56开锁原语开锁原语unlock W：if WL NULL thenbeginremove(WL,q);status(q)=“ready”;insert(RL,q);endelseW=0;2.5进程同步进程同步CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 572.6 信号量机制及其应用信号量机制及其应用整型信号量机制整型信号量机制信号量信号量(sem)sem=0:表示可供并发进程使用的资源实体的个数表示可供并发进程使用的资源实体的个数sem0:表示正在等待使用临界区的进程数。表示正在等待使用临界区的进程数。Sem的值只能由的值只能由P、V操作改变。操
39、作改变。P：wait(s)V：signal(s)按信号量数值分为二元信号量和一般信号量。按信号量数值分为二元信号量和一般信号量。CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 58Wait（P）和）和signal（V）原语）原语Wait(s)原语原语struct semaphore int count;QueueType Queue;void wait(s)s.count-;if(s.count 0)place this process in s.queue;block this process;2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12
40、 11:50操作系统|进程管理 59signal原语原语void signal(s)s.count+;if(s.count=0)remove a process P from s.queue;place process P on ready list;2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 60利用信号量实现互斥利用信号量实现互斥public class mutualexclusion static final int n=;semaphore s=new semaphore(1);public void P(int i)w
41、hile(true)wait(s);signal(s);public static void main()parbegin(P(1),P(2),.,P(n);2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 61利用信号量描述前趋关系利用信号量描述前趋关系P1：S1P2：S2S1S2则设置信号量s=0，P1：S1；signal(s)；P2：Wait(s)；S2；2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 621234567abcdefgh例：根据前趋图写出可并发执行的程
42、序：2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 63var a,b,c,d,e,f,g,h:semaphore:=0,0,0,0,0,0,0,0;begin parbegin begin S1;signal(a);signal(b);signal(c);end begin wait(a);S2;signal(d);end begin wait(b);S3;signal(e);end begin wait(c);S4;signal(f);end begin wait(d);S5;signal(g);end begin wait(e
43、);wait(f);S6;signal(h);end begin wait(g);wait(h);S7;endparendend 2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 64信号量集机制信号量集机制AND型信号量集机制型信号量集机制问题引入问题引入 进程进程A、B访问共享数据访问共享数据D和和E 信号量信号量Dmutex=1，Emutex=1process A:wait(Dmutex);wait(Emutex);process B:wait(Emutex);wait(Dmutex);2.6信号量机制及其应用信号量机制及其应用
44、CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 65 A、B交替执行：交替执行：process A:wait(Dmutex);则则Dmutex=0process B:wait(Emutex);则则Emutex=0process A:wait(Emutex);则则Emutex=-1，阻塞，阻塞process B:wait(Dmutex);则则Dmutex=-1，阻塞，阻塞发生死锁。发生死锁。2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 66AND同步机制的思想同步机制的思想Swait(S1,S2,Sn)if (S
45、1=1&S2=1&Sn=1)for (i=1;i=n;i+)Si-;else 将进程插入第将进程插入第i（Si1）个等待队列）个等待队列;设置该进程的程序计数器到设置该进程的程序计数器到Swait操作的开操作的开始始;2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 67Ssignal(S1,S2,Sn)for (i=1;i=t1&S2=t2&Sn=tn)for (i=1;i=n;i+)Si =di;else 将执行进程插入第将执行进程插入第i（Siti）个等待队列）个等待队列;设置该进程的程序计数器到设置该进程的程序计数器到Swai
46、t操作的开始操作的开始;2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 69Ssignal(S1,d1,;Sn,dn)for (i=1;i1）或互斥信号量（或互斥信号量（S=1）；）；Swait(S,1,0)：当：当S=1，允许多个进，允许多个进程进入某临界区；当程进入某临界区；当S=0后，阻止任后，阻止任何进程进入临界区。何进程进入临界区。2.6信号量机制及其应用信号量机制及其应用CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 71 例2：打印进程与计算进程的同步问题 设：设：SA SA 打印进程的私有信号量，
47、初值为打印进程的私有信号量，初值为0 0，当当SA SA=1=1 时表示可以打印。时表示可以打印。SB SB 计算进程的私有信号量，初值为计算进程的私有信号量，初值为0 0，当当SB =0 SB =0 时时表示可以表示可以放入计算结果。放入计算结果。缓冲区计算计算打印机打印机缓冲区打印打印进程进程计算进程计算进程SASASBSB缓冲区缓冲区缓冲区缓冲区同步的概念同步的概念 2.7 经典进程同步问题经典进程同步问题CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 72 计算结果放入缓冲区计算结果放入缓冲区；T2:T2:signal(SA)signal(SA)；L1:L1:wai
48、twait（SBSB）；显然，进程显然，进程CPCP与进程与进程IOPIOP相互制约：相互制约：只有只有CPCP执行到执行到 T2T2，IOPIOP才能执行才能执行T1T1。（。（T2 T1T2 T1）只有只有IOPIOP执行到执行到L2L2，CPCP才能执行才能执行L1L1。（L2 L1L2 L1）计算进程与打印进程同步的模型计算进程与打印进程同步的模型计算进程计算进程CPCP打印进程打印进程IOPIOPT1:wait（SA）；从缓冲区取结果从缓冲区取结果；L2:signal（SB）；SA SA，SB SB 初值为初值为0 02.7 经典进程同步问题经典进程同步问题CUIT 叶斌叶斌2023
49、-2-12 11:50操作系统|进程管理 73异步环境异步环境 相互合作的一组并发进程，其中每相互合作的一组并发进程，其中每一进程都能以各自独立的，不可预知的一进程都能以各自独立的，不可预知的速度向前推进。速度向前推进。进程同步进程同步 相互合作的进程之间需要交换一定的相互合作的进程之间需要交换一定的信息，当某进程未获得其合作进程发来的信息，当某进程未获得其合作进程发来的信息之前，该进程等待，直到该信息到来信息之前，该进程等待，直到该信息到来时才被唤醒继续执行，从而保证诸进程的时才被唤醒继续执行，从而保证诸进程的协调运行。协调运行。2.7 经典进程同步问题经典进程同步问题CUIT 叶斌叶斌20
50、23-2-12 11:50操作系统|进程管理 74生产者生产者消费者问题综述消费者问题综述问题描述问题描述 通过由通过由n个环形缓冲区构成的个环形缓冲区构成的缓冲池，把生产者缓冲池，把生产者P1，P2，PM和一群消费者和一群消费者C1，C2，CK联系起来。联系起来。算法描述算法描述2.7 经典进程同步问题经典进程同步问题CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 75CUIT 叶斌叶斌2023-2-12 11:50操作系统|进程管理 76变量定义：变量定义：begin Var mutex,empty,full:semaphore:=1,n,0;buffer:array0
