三章进程管理1

1、第三章 进 程 管 理 2021-11-241第三章第三章 进程管理进程管理-1 -1 3.1 3.1 进程的基本概念进程的基本概念 3.2 3.2 进程的基本状态进程的基本状态 3.3 3.3 进程的描述与管理进程的描述与管理 3.4 3.4 进程控制进程控制重点重点: :本章为本书的重点本章为本书的重点, ,难点难点 第三章 进 程 管 理 2021-11-2423.1 进程的基本概念进程的基本概念 3.1.1 进程概念的引入进程概念的引入c编译程序cc程序程序a程序程序b时间片用完中断可再入程序第三章 进 程 管 理 2021-11-243进程：一段功能完整的程序在处理机上的执行过程。进

2、程：一段功能完整的程序在处理机上的执行过程。3.1.2 进程与程序的区别进程与程序的区别 进程是动态的，程序是静态的进程是动态的，程序是静态的 进程是暂时的概念，程序是永久的概念进程是暂时的概念，程序是永久的概念 进程有自己的数据结构进程有自己的数据结构pcb 进程和程序不是一一对应的。进程和程序不是一一对应的。第三章 进 程 管 理 2021-11-2443.1.3 进程的定义进程的定义进程进程: :是一个具有独立功能的程序对某个数据集在处理是一个具有独立功能的程序对某个数据集在处理 机上的执行过程和分配资源的基本单位机上的执行过程和分配资源的基本单位. . 程序程序: :指一组操作序列指一

3、组操作序列. .数据集数据集: :接受程序规定操作的一组存储单元的内容接受程序规定操作的一组存储单元的内容. . 进程的特征进程的特征动态性动态性并行性并行性独立性独立性异步性异步性第三章 进 程 管 理 2021-11-245进程的结构特征进程的结构特征:pcb,程序代码段程序代码段,数据段数据段程序数据pcb进程的结构特征进程的结构特征第三章 进 程 管 理 2021-11-246进程程序动态静态暂时永久并行串行(顺序)pcb多个一个一个多个进程与程序的区别与联系进程与程序的区别与联系第三章 进 程 管 理 2021-11-2473.2 进程的基本状态进程的基本状态 为了描述和控制进程的运

4、行为了描述和控制进程的运行,系统为每个进程定义了一个数据系统为每个进程定义了一个数据结构结构,即进程控制块即进程控制块pcb (process control block),系统根据系统根据pcb,感知该进程的存在感知该进程的存在,故亦称故亦称pcb是进程存在的标志是进程存在的标志. pcb的作用的作用:u感知进程的存在u记录进程的状态或有关信息通常在一个实际系统中通常在一个实际系统中,pcb的总数是固定的的总数是固定的,该数目规定了系该数目规定了系统所允许拥有的进程数目统所允许拥有的进程数目,同时将所有的同时将所有的pcb形成一个结构数形成一个结构数组组(或称或称pcb表表),存放在系统的数

5、据区中存放在系统的数据区中.一个进程的一个进程的pcb机构全部或部分常驻内存机构全部或部分常驻内存.第三章 进 程 管 理 2021-11-2483.2.1 进程的基本状态进程的基本状态1. 进程状态进程状态就绪态就绪态:等待系统分配处理机以便执行时 所处的状态. 即获得了除处理机之外的所以资源,一旦由调度 程序选中得到处理机就可以立即执行的状态.运行态运行态:正在处理机上执行时所处的状态. 在单cpu情况下,处于该状态的进程数只有一个.等待态等待态:等待某个事件的完成时进程所处的状态.除了 cpu之外其他的资源也没有得到满足 第三章 进 程 管 理 2021-11-249运行就绪等待进程调度

6、策略进程调度策略时时间间片片用用完完等待某一事件发生等待某一事件发生等待事件结束等待事件结束剥剥夺夺处处理理机机创建创建撤销撤销进程的三种基本状态及其转换进程的三种基本状态及其转换 第三章 进 程 管 理 2021-11-2410 进程控制块3.3 进程的描述与管理进程的描述与管理1.os1.os感知进程存在的唯一标识感知进程存在的唯一标识-pcb-pcb2.2.记录了记录了osos所需的用于描述进程及控制进程全部信息所需的用于描述进程及控制进程全部信息. . 在在pcbpcb中主要包括下面信息中主要包括下面信息: : 1) 1) 进程描述信息进程描述信息 2) 2) 进程控制信息进程控制信息

7、 3) 3) 资源信息资源信息 4) 4) 现场保护信息现场保护信息 1) 1) 进程描述信息进程描述信息: :进程名或进程标识符进程名或进程标识符. . 家族关系家族关系. . 第三章 进 程 管 理 2021-11-24112) 2) 进程控制信息进程控制信息1. 1.进程的当前信息进程的当前信息: :指明进程的当前状态指明进程的当前状态, ,作为进程调度作为进程调度和对换的依据和对换的依据. .2.2.进程优先级进程优先级: :调度依据调度依据, ,是进程占有处理机的重要依据是进程占有处理机的重要依据. .3.3.程序开始地址程序开始地址: :便于执行这段程序便于执行这段程序. .4.4

8、.各种计时信息各种计时信息: :记录资源占用的信息记录资源占用的信息. .5.5.通信信息通信信息: :保证进程之间相应的联系保证进程之间相应的联系. .3) 3) 资源管理信息资源管理信息1. 1.占用内存大小及其管理用数据结构指针占用内存大小及其管理用数据结构指针. .2.2.对换或覆盖用的有关信息对换或覆盖用的有关信息. .3.3.共享程序的大小及起始地址共享程序的大小及起始地址. .4.4.i/oi/o设备号设备号, ,传送的数据长度传送的数据长度, ,缓冲区地址缓冲区地址, ,缓冲区长度缓冲区长度及所有设备的有关数据结构指针及所有设备的有关数据结构指针. .5.5.指向文件系统的指针

9、及有关标识符指向文件系统的指针及有关标识符. .第三章 进 程 管 理 2021-11-24124) cpu4) cpu现场保护信息现场保护信息( (进程上下文进程上下文) )1. 1.通用寄存器的用户通用寄存器的用户2.2.pcpc3.3.psw :psw :含状态信息（条件码的执行方式含状态信息（条件码的执行方式, ,中断屏蔽标识中断屏蔽标识) )。4.4.用户栈指针：为每个用户进程有一个或若干隔与之相关用户栈指针：为每个用户进程有一个或若干隔与之相关的系统栈，用于存放过程和系统调用参数和调用地址。的系统栈，用于存放过程和系统调用参数和调用地址。 当处理机被中断时当处理机被中断时, ,各种

10、寄存器的内容都必须保存在各种寄存器的内容都必须保存在被中断进程的被中断进程的pcbpcb中中, ,以便在该进程重新执行时以便在该进程重新执行时, ,能从能从断点继续执行断点继续执行. . 由于由于pcbpcb中包含较多的信息（占几百几千中包含较多的信息（占几百几千byte),byte),在有的系在有的系统中只含统中只含pcbpcb中最常用部分（中最常用部分（cpucpu现场保护部分，进程描述现场保护部分，进程描述信息，控制信息）常驻内存，其他部分则放在外存中，待该信息，控制信息）常驻内存，其他部分则放在外存中，待该进程将要执行时与其他数据一起装入内存。进程将要执行时与其他数据一起装入内存。第三

11、章 进 程 管 理 2021-11-2413* *进程上下文进程上下文 是对进程动态活动的静态描述是对进程动态活动的静态描述 进程的上下文是其相应的程序地址空间的内容，硬件进程的上下文是其相应的程序地址空间的内容，硬件寄存器的内容以及与该进程有关的核心数据结构寄存器的内容以及与该进程有关的核心数据结构（系统堆栈，用户堆栈）构成的。（系统堆栈，用户堆栈）构成的。 包括：计算机系统中与执行该进程有关的各种寄存器包括：计算机系统中与执行该进程有关的各种寄存器值；程序段经过编译连接后形成的机器指令代码段值；程序段经过编译连接后形成的机器指令代码段（text);text);数据段以及各种堆栈的值和数据段

12、以及各种堆栈的值和pcbpcb块）。块）。 例：例：unixunix进程上下文进程上下文用户级上下文用户级上下文 系统级上下文系统级上下文寄存器上下文寄存器上下文* *进程上下文进程上下文第三章 进 程 管 理 2021-11-2414* *进程进程的组成的组成 进程进程pcbpcb程序（代码和数据）程序（代码和数据） 进程的表记进程的表记pcb程序pcb程序代码第三章 进 程 管 理 2021-11-2415* *pcbpcb的组成方式的组成方式 在一个系统中，通常可以拥有数十个以及若干个在一个系统中，通常可以拥有数十个以及若干个pcb,pcb,为了能对他们进行有效的管理，应当用适当的方式将

13、为了能对他们进行有效的管理，应当用适当的方式将他们组织起来。他们组织起来。pcbpcb目前常用的组织方式：链接方式；索引方式目前常用的组织方式：链接方式；索引方式 系统中进程队列分类：就绪队列，等待队列，运行队列。系统中进程队列分类：就绪队列，等待队列，运行队列。 就绪队列：整个系统一个就绪队列：整个系统一个 等待队列：每一个等待事件一个。等待队列：每一个等待事件一个。 运行队列：单机系统中整个系统一个。运行队列：单机系统中整个系统一个。第三章 进 程 管 理 2021-11-2416pcb14pcb2pcb3pcb4pcb5pcb6pcb7pcb8pcb93087901执行指针就绪队列指针阻

14、塞队列指针空闲队列指针1. 1.链接方式链接方式pcb链接队列示意图 把具有相同状态的把具有相同状态的pcb,pcb,用其中的链接字链接成一个队列用其中的链接字链接成一个队列. .线性表线性表第三章 进 程 管 理 2021-11-2417按索引方式组织pcb 执行指针就绪索引表pcb1pcb2pcb3pcb4pcb5pcb6pcb7阻塞索引表就绪表指针阻塞表指针2. 2. 索引方式索引方式系统根据所有进程的状态系统根据所有进程的状态, ,建立几张索引表建立几张索引表, ,如就绪索引表如就绪索引表, ,阻塞索引阻塞索引表表, ,并把各索引表在内存的首地址记录于内存中的一些专用库文件中并把各索引

15、表在内存的首地址记录于内存中的一些专用库文件中. .第三章 进 程 管 理 2021-11-24183.4 进程控制进程控制为了防止为了防止osos及关键数据如及关键数据如pcbpcb等等, ,受到用户程序有意或无意的破坏受到用户程序有意或无意的破坏, ,通通常将处理机的执行状态分为常将处理机的执行状态分为: :系统态和用户态系统态和用户态. .1. 1.系统态系统态( (核心态核心态): ):具有较高的特权具有较高的特权, ,能执行一切指令能执行一切指令, ,访问访问所有的寄存器和存储区所有的寄存器和存储区. .2.2.用户态用户态: :具有较低特权的执行状态具有较低特权的执行状态, ,只能

16、执行规定的指令只能执行规定的指令, ,访问指定的寄存器和存储区访问指定的寄存器和存储区. .进程控制进程控制: : 就是系统使用一些具有特定功能的程序段来创建、撤销进程以及就是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程状态间的转换，从而达到多进程高效率并发执行和协调完成进程状态间的转换，从而达到多进程高效率并发执行和协调实现资源共享的目的。实现资源共享的目的。原语（原语（atomic operation):atomic operation): 系统态下执行的某些具有特定功能的程序段。系统态下执行的某些具有特定功能的程序段。第三章 进 程 管 理 2021-11-2419. .

17、 创建原语创建原语为此进程分配进程控制块为此进程分配进程控制块为此进程分配资源为此进程分配资源把此进程插入到就绪队列中把此进程插入到就绪队列中, ,等待等待cpucpu的调度的调度. . 引起创建进程的事件引起创建进程的事件 用户登陆用户登陆作业调度作业调度提供服务提供服务应用请求应用请求3.4.1. 进程的创建进程的创建第三章 进 程 管 理 2021-11-2420 1. 1. 引起进程终止的事件引起进程终止的事件 正常结束正常结束异常结束异常结束外界干预外界干预3.4.2 . 进程的终止进程的终止 procedure destroy(n procedure destroy(n) ) be

18、gin begin sched sched=false;=false; i= i=获取获取n n进程内部名进程内部名 kill(ikill(i); ); if (sched) schedure if (sched) schedure else continue( else continue(当前正在执行的进程当前正在执行的进程); ); end end第三章 进 程 管 理 2021-11-2421.进程创建原语的描述形式进程创建原语的描述形式create(n,so,po,mo,ro,acc)begin i=get internal name(n);/* 获得内部名获得内部名*/ i.id=n

19、; /* 填外部名填外部名 */ i.priority=po; /* 设优先级设优先级 */ i.cpustate=so; /* 填填cpu初始状态初始状态 */ i.mainstore=mo; /* 填写主存区域填写主存区域 */ i.resource=ro; /* 填写资源清单填写资源清单 */ i.status=readys; /* 填写进程状态填写进程状态 */ j=ep; /* 获取调用者内部标识获取调用者内部标识 */ i.parent=j; /* 填写填写i进程的父进程进程的父进程j */ gency=; /* 置置i的家族指针为空的家族指针为空 */ gen

20、cy=i; /* 把把i填入其父进程填入其父进程pcb的家族指针处的家族指针处 */ i.state=rq; /* 置置i所在状态队列首指针所在状态队列首指针 */ insert(rq,i); /* 把把i进程插入到进程插入到rq对尾对尾 */endpcbi第三章 进 程 管 理 2021-11-2422l procedure kill(i)l beginl if i-status=“running” l begin l stop(i);l sched=true;l endl remove(i-state,i);将被撤销进程i从i.state所指示的队列中去掉.l for all s(i.pr

21、ogency) do kill(s);l for all r(i.mainstoreui.resoure) do l if owner (r) insert(r.semaphore,r.data); l 归还属于父进程资源且插入父资源清单归还属于父进程资源且插入父资源清单.l for all rcreated resoure(i) do remove descriptor(r) ;l 撤销自己的资源清单并归还系统撤销自己的资源清单并归还系统l remove process control block(i);l end 第三章 进 程 管 理 2021-11-24231.根据被终止进程的标识符，

22、从根据被终止进程的标识符，从pcb链表中检索出该进程的链表中检索出该进程的pcb，从中读，从中读出该进程的状态。出该进程的状态。2.若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。志为真，用于指示该进程被终止后应重新进行调度。3.若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。为不可控的进程。4.将被终止进程所拥有的全部资源，或者归还给其父进程，将被终止进程所拥有的全部资源，或者归还

23、给其父进程， 或者归还给或者归还给系统。系统。5.将被终止进程将被终止进程(它的它的pcb)从所在队列从所在队列(或链表或链表)中移出，中移出， 等待其他程序来等待其他程序来搜集信息。搜集信息。 2 2. .进程的终止过程进程的终止过程第三章 进 程 管 理 2021-11-24243.4.3 进程的挂起和激活进程的挂起和激活挂起挂起: :让进程暂时不参与资源的竞争让进程暂时不参与资源的竞争1. 1. 挂起原语的方式挂起原语的方式 把挂起原语调用者本身挂起把挂起原语调用者本身挂起,即自己挂起自己即自己挂起自己挂起某个标识符的进程挂起某个标识符的进程将某个指定标识符的进程及其全部或部分子孙挂起将

24、某个指定标识符的进程及其全部或部分子孙挂起. 挂起用以保存挂起用以保存n进程的进程的pcb副本的内存区副本的内存区,以备参考以备参考.l procedure suspend(n,a)l beginl i=get internal name(n);l s=i.status; l if i.status=“running” stop(i);l a=copy pcb(i); /* 相应的相应的pcb保留起来以便查看是属于哪一种挂起保留起来以便查看是属于哪一种挂起.l if s=blocka i.status=blocks else i.status=readys;l if s=running sch

25、edule else continue;l end 第三章 进 程 管 理 2021-11-2425 当出现了引起进程挂起的事件时，比如，用户进程请求将自己当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，挂起，或父进程请求将自己的某个子进程挂起， 系统将利用挂起原系统将利用挂起原语语suspend( )将指定进程或处于阻塞状态的进程挂起。挂起原语的将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进

26、程，则将之改为静止便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。阻塞。 为了方便用户或父进程考查该进程的运行情况而把该进程的为了方便用户或父进程考查该进程的运行情况而把该进程的pcb复制到某指定的内存区域。最后，若被挂起的进程正在执行，复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。则转向调度程序重新调度。 2. 2. 进程进程的挂起的挂起第三章 进 程 管 理 2021-11-2426. . 激活原语的激活方式激活原语的激活方式 激活指定标识符的进程激活指定标识符的进程激活某进程及其子孙激活某进程及其子孙l procedure active(n

27、)l beginl i=get internal name(n);l if i.status=“readys” l i.status=readyal elsel i.status=blocka; l if i.status=“readya” l scheduler;l else l continue;l endl 第三章 进 程 管 理 2021-11-2427 当发生激活进程的事件时，例如，父进程或用户进程请求激活指定当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存进程，若该进程驻留在外存而内存中已有足够的空间时，则可将

28、在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active( )将指定进程激活。将指定进程激活。 激活原语先将进程从外存调入内存，检查该激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进入就绪队列时，应检查是否要进行重新调度，

29、即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。活的进程。 . . 进程的激活进程的激活第三章 进 程 管 理 2021-11-2428.挂起引起的原因挂起引起的原因协调负载过重协调负载过重某些设备故障某些设备故障 调试程序调试程序活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求i/o具有挂起状态的进程状态图 第三章 进 程 管 理 2021-1

30、1-24291. 1. 引起阻塞和唤醒的事件引起阻塞和唤醒的事件请求系统服务请求系统服务启动某种操作启动某种操作新数据尚未到达新数据尚未到达无新工作可作无新工作可作.3.4.4 进程的阻塞与唤醒进程的阻塞与唤醒l procedure block(n)l beginl i=ep; 从执行进程的指针从执行进程的指针ep获得调用者内部标识符获得调用者内部标识符l stop(i);l i.status=blocka; 修改该进程的状态修改该进程的状态l i.state=wq(r); 找到相应的插入队列找到相应的插入队列l insert(wq(r),i); 把把i插入到插入到wq队尾队尾l schedu

31、ler; 转调度程序转调度程序l endl . . 阻塞原语阻塞原语第三章 进 程 管 理 2021-11-2430 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由所以应先立即停止执行，把进程控制块中的现行状态由“执行执行”改

32、为阻塞，改为阻塞，并将并将pcb插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待等待)队列。队列。 最后，转调最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态保留被阻塞进程的处理机状态(在在pcb中中)，再按新进程的，再按新进程的pcb中的处理机中的处理机状态设置状态设置cpu的环境。的环境。 2. 2. 进程阻塞的过程进程

33、阻塞的过程第三章 进 程 管 理 2021-11-2431唤醒原语唤醒原语: :由于资源的释放才能利用此资源把某些因等待由于资源的释放才能利用此资源把某些因等待 此资源而被阻塞的进程唤醒此资源而被阻塞的进程唤醒l procedure wakeup(n)l beginl i=get internal name(n);找到相应的给定资源进程找到相应的给定资源进程n并获取并获取n进程的内部名进程的内部名l remove(wq(r),i); 把把i进程从等待队列进程从等待队列r中去除中去除.l i.status=readys; 置置i进程为就绪状态进程为就绪状态l i.state=rq; 把把i进程插

34、入到就绪队列进程插入到就绪队列l insert(rq,i); 把把i插入到插入到rq队尾队尾l continue;l end 第三章 进 程 管 理 2021-11-2432 当被阻塞进程所期待的事件出现时，如当被阻塞进程所期待的事件出现时，如i/o完成或其所期待的数据已完成或其所期待的数据已经到达，则由有关进程经到达，则由有关进程(比如，用完并释放了该比如，用完并释放了该i/o设备的进程设备的进程)调用唤醒调用唤醒原语原语wakeup( )，将等待该事件的进程唤醒。唤醒原语执行的过程是：首，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其先把

35、被阻塞的进程从等待该事件的阻塞队列中移出，将其pcb中的现行中的现行状态由阻塞改为就绪，然后再将该状态由阻塞改为就绪，然后再将该pcb插入到就绪队列中。插入到就绪队列中。 3. 3. 进程唤醒过程进程唤醒过程第三章 进 程 管 理 2021-11-2433相交进程相交进程:多个并发进程在逻辑上存在着相互关系多个并发进程在逻辑上存在着相互关系无关进程无关进程( (不相交进程不相交进程):):在逻辑上无任何联系的进程在逻辑上无任何联系的进程. 进程间的作用进程间的作用直接作用直接作用:进程间的相互联系是有意识的安排的进程间的相互联系是有意识的安排的.间接作用间接作用: :进程间要通过某种中介发生联

36、系进程间要通过某种中介发生联系, ,是无意识的是无意识的. .3.5 进程间的相互作用进程间的相互作用. 进程间的联系进程间的联系相交进程相交进程:多个并发进程在逻辑上存在着相互关系多个并发进程在逻辑上存在着相互关系无关进程无关进程( (不相交进程不相交进程):):在逻辑上无任何联系的进程在逻辑上无任何联系的进程进程间的联系进程间的联系进程的同步机制进程的同步机制-信号量及信号量及p.vp.v操作操作( (解决进程同步互斥问题解决进程同步互斥问题) )第三章 进 程 管 理 2021-11-2434相互感知程序交互关系一个进程对其他进程的影响相互不感知(完全不了解其他进程的存在)竞争一个进程的

37、存在对其他进程的结果无影响间接感知(双方都与第三方交互,如共享资源)通过共享进行协作一个进程的结果依赖于从其他进程获得的信息直接感知(双方互相交互,如通信)通过通信进行协作一个进程的结果依赖于从其他进程获得的信息进程间的相互联系进程间的相互联系第三章 进 程 管 理 2021-11-24353.5.1 进程的互斥进程的互斥 由于各进程要求共享资源由于各进程要求共享资源, ,而有些资源需要互斥使用而有些资源需要互斥使用, ,因此各进程间因此各进程间竞争使用这些资源竞争使用这些资源, ,进程的这种关系未进程的互斥进程的这种关系未进程的互斥. .反映在资源的使用本反映在资源的使用本身时排它的身时排它

38、的, ,从而引起进程间资源的竞争从而引起进程间资源的竞争. . 临界资源临界资源(critical resource)(critical resource):一次只允许一个进程使用的资源一次只允许一个进程使用的资源( (或者排它性使用的资源或者排它性使用的资源) )第三章 进 程 管 理 2021-11-2436与时间有关的错误与时间有关的错误. 顺序程序特征顺序程序特征 . 程序的顺序执行程序的顺序执行 一条指令执行结束之后,下一条指令才开始.或者说一条指令的执行应该在它前一条指令的执行结果的基础之上才能进行。 顺序性顺序性允许环境的封闭性允许环境的封闭性运行结果的确定性运行结果的确定性运行

39、结果的可再现运行结果的可再现第三章 进 程 管 理 2021-11-2437例例:同学甲同学甲同学乙同学乙if 有空椅子 then 坐下if 有空椅子 then 搬走造成的结果造成的结果1.运行结果的不确定性2.不能保证运行环境的封闭性3.不能保证顺序性4.运行结果的不可再现性第三章 进 程 管 理 2021-11-2438.并行程序的特征并行程序的特征1.共享性2.并发性3.随机性主机abcd时间片到a进程进程b进程进程if (x0 ) x=x-1;.if (x0 ) x=x-1;.例例1:民航售票民航售票第三章 进 程 管 理 2021-11-2439. .临界区临界区( (互斥区互斥区)

40、:):critical sectioncritical section 把程序当中具有共享资源并且对共享资源进行操作的把程序当中具有共享资源并且对共享资源进行操作的这段程序这段程序, ,或者说在进程中涉及到临界资源的程序段叫或者说在进程中涉及到临界资源的程序段叫做临界区做临界区. .a=a+1a=a+1print(aprint(a) )a=a-1a=a-1print(aprint(a) )p1p1p2p2p3p3if a0 if a0 a=a+1; a=a+1;else else a=a-1; a=a-1;第三章 进 程 管 理 2021-11-2440程序段程序段1 1程序段程序段2 2程序

41、段程序段3 3共享变量共享变量第三章 进 程 管 理 2021-11-2441使用临界区的原则有空让进有空让进: :当临界区中无进程时当临界区中无进程时, ,任何有权使用临界区的进程可进入任何有权使用临界区的进程可进入无空等待:不允许两个以上的进程同时进入临界区不允许两个以上的进程同时进入临界区. .多中选一:当没有进程在临界区当没有进程在临界区, ,而同时有多个进程要求进入临界区而同时有多个进程要求进入临界区, , 只能让其中一个进入临界区只能让其中一个进入临界区, ,其他进程必须等待其他进程必须等待. .有限等待:任何进入临界区的进程要求在有限的时间内得到满足任何进入临界区的进程要求在有限

42、的时间内得到满足. .让权等待:处于等待状态的进程应该放弃占用处于等待状态的进程应该放弃占用cpu,cpu,以便使得其他进程以便使得其他进程 有机会得到有机会得到cpucpu的使用权的使用权. .第三章 进 程 管 理 2021-11-24423.5.2 进程互斥的两种解决方法进程互斥的两种解决方法. .由竞争各方平等协商由竞争各方平等协商.引人一进程管理者引人一进程管理者, ,由管理者来协调竞争各方对互斥资源的使用由管理者来协调竞争各方对互斥资源的使用. .具体办法: 硬件(当一个进程进入临界区,就屏蔽所有中断) 软件(用编程解决,但常常忙等待)第三章 进 程 管 理 2021-11-244

43、3进程互斥的软件方法进程互斥的软件方法l 通过平等协商方式实现进程互斥的最初方法是软件方法通过平等协商方式实现进程互斥的最初方法是软件方法.l 软件方法软件方法1: while(freewhile(free) ) free=true; free=true;free=false;free=false;临界区临界区free:free:表示临界区标志表示临界区标志 true:true:有进程在临界区有进程在临界区 false:false:无进程在临界区无进程在临界区( (初值初值) )l 其基本思路：是在进入临界区检查和设置一些标志，如果已有进程在临界其基本思路：是在进入临界区检查和设置一些标志，如

44、果已有进程在临界 区，则在进入区通过循环检查进行等待；在退出区修改标志。区，则在进入区通过循环检查进行等待；在退出区修改标志。l 问题：设置什么标志和如何检查标志。问题：设置什么标志和如何检查标志。第三章 进 程 管 理 2021-11-2444l 软件方法软件方法2: while( not turn);while( not turn);turn=falseturn=false临界区turn:turn: true true表示表示p p进入临界区进入临界区 falsefalse表示表示q q进程临界区进程临界区p:while( turn);while( turn);turn=trueturn=

45、true临界区q:第三章 进 程 管 理 2021-11-2445l 软件方法软件方法3: pturnpturn=true;=true;while( qturnwhile( qturn););pturnpturn=false=false临界区pturn,qturnpturn,qturn: :初值为初值为falsefalse p p进入临界区的条件进入临界区的条件:pturn not qturn:pturn not qturn q q进入临界区的条件进入临界区的条件:not pturn qturn:not pturn qturnp:qturnqturn=true;=true;while (ptu

46、rnwhile (pturn) )qturnqturn=false=false临界区q:第三章 进 程 管 理 2021-11-2446例例: :进行修改进行修改 . . while (flag1); while (flag1); flag0=true; flag0=true; 临界区临界区; ; flag0=false; flag0=false;进程进程1 1. while (flag0); while (flag0); flag1=true; flag1=true; 临界区临界区; ; flag1=false; flag1=false;falg0falg0flag1flag1 . . wh

47、ile (flag1); while (flag1); 临界区临界区; ; flag0=false; flag0=false;. while (flag0); while (flag0); 临界区临界区; ; flag1=false; flag1=false;再进行修改再进行修改flag1=true;flag1=true;flag0=true;flag0=true;第三章 进 程 管 理 2021-11-2447 . . flag0=true;flag0=true; while (flag1) while (flag1) beginbegin flag0=false; flag0=false;

48、 wait(5); wait(5); flag0=true; flag0=true; end end 临界区临界区; ; flag0=false; flag0=false;. flag1=true;flag1=true; while (flag0)while (flag0) beginbegin flag1=false; flag1=false; wait(5); wait(5); flag1=true; flag1=true; end end 临界区临界区; ; flag1=false; flag1=false;第三章 进 程 管 理 2021-11-2448l 软件方法软件方法4:dekk

49、er算法算法 pturn,qturnpturn,qturn: :初值为初值为falsefalse p p进入临界区的条件进入临界区的条件:pturn not qturn:pturn not qturn q q进入临界区的条件进入临界区的条件:not pturn qturn:not pturn qturnturn:turn:枚举类型枚举类型, ,初值任意初值任意第三章 进 程 管 理 2021-11-2449while (true)while (true) pturn pturn=true;=true; while( qturn while( qturn) ) if (turn=2) if (t

50、urn=2) pturn pturn=false;=false; while(turn while(turn=2);=2); pturn pturn=true;=true; turn=2; turn=2; pturn pturn=false;=false; 临界区p:while (true)while (true) qturn qturn=true;=true; while( pturn while( pturn) ) if (turn=2) if (turn=2) qturn qturn=false;=false; while(turn while(turn=1);=1); qturn qt

51、urn=true;=true; turn=1; turn=1; qturn qturn=false;=false; 临界区q:第三章 进 程 管 理 2021-11-2450软件解决的缺点:l 忙等待l 实现过于复杂,需要高的编程技巧.l peterson算法算法 pturnpturn=true;=true;turn=2;turn=2;while( qturn&turnwhile( qturn&turn=2);=2);pturnpturn=false=false临界区p:qturnqturn=true;=true;turn=1;turn=1;while (pturn&t

52、urnwhile (pturn&turn=1);=1);qturnqturn=false=false临界区q:第三章 进 程 管 理 2021-11-2451硬件办法硬件办法1l boolean ts(boolean *lock) boolean old; old=*lock; *lock=true; return(old); while ts (while ts (* *lock);lock);临界区lock=false;lock=false;“测试并设置测试并设置”指令指令第三章 进 程 管 理 2021-11-2452硬件办法硬件办法2void swap(int *a,int *

53、b) int temp temp=*a; *a=*b; *b=temp; key=true;key=true;do do swap( swap(* *lock,keylock,key);); while(keywhile(key););临界区lock=false;lock=false;“交换交换”指令指令第三章 进 程 管 理 2021-11-2453硬件办法硬件办法3“开关中断开关中断”指令指令进入临界区前执行：执行进入临界区前执行：执行“关中断关中断”指令指令离开临界区后执行：执行离开临界区后执行：执行“开中断开中断”指令指令第三章 进 程 管 理 2021-11-24543.5.3 进程

54、的同步机制进程的同步机制-信号量及信号量及p.v操作操作同步机制同步机制信号量及信号量及p.v操作操作管程管程条件临界域条件临界域路径表达式等路径表达式等(用于集中式系统中用于集中式系统中)同步机制应满足的基本要求同步机制应满足的基本要求1.1.描述能力描述能力必须能够详细描述出进程间这种相互配合以及相互矛盾必须能够详细描述出进程间这种相互配合以及相互矛盾的关系的关系. .2.2.可以实现可以实现实现起来方便实现起来方便, ,这种机制在一定的机制或一定的语言上这种机制在一定的机制或一定的语言上要能够实施要能够实施. .3.3.效率高效率高不然的话不然的话, ,它会降低系统的并行能力和并行程度它

55、会降低系统的并行能力和并行程度. .4.4.使用方便使用方便第三章 进 程 管 理 2021-11-2455信号量信号量(semaphore) 是一个数据结构;严格说来它是一个整型变量,能够刻画一定程序的状态.信号量信号量(semaphore)的定义的定义strucstruc semaphore semaphore int int value; value; pointer_pcb pointer_pcb queue; queue; .信号量说明信号量说明semaphore s;第三章 进 程 管 理 2021-11-2456信号量信号量互斥的信号量互斥的信号量:p.v:p.v操作一定在同一个

56、进程中操作一定在同一个进程中同步的信号量同步的信号量:p.v:p.v操作在不同的进程当中操作在不同的进程当中信号量的物理意义信号量的物理意义s0:ss0:s表示可用资源的个数表示可用资源的个数. .s=0:ss=0:s表示无资源使用表示无资源使用, ,也无等待进程也无等待进程. .s0: s0: 表示等待队列中进程的个数表示等待队列中进程的个数s问题问题:信号量的初值不能为负信号量的初值不能为负,为什么为什么?第三章 进 程 管 理 2021-11-2457原语原语:primitive or acomic actionl 是由若干机器指令构成的完成某种特定功能的一段程序是由若干机器指令构成的完

57、成某种特定功能的一段程序,具有不可具有不可 分割性分割性.即原语的执行必须是连续的即原语的执行必须是连续的,在执行过程中不允许被中断在执行过程中不允许被中断.原语实现原语实现:开关中断开关中断1.1.必须置一次且只能设一次初值必须置一次且只能设一次初值2.2.初值不能为负数初值不能为负数3.3.修改信号量的值只能由修改信号量的值只能由p.vp.v进行操作进行操作. .信号量的使用原则信号量的使用原则:第三章 进 程 管 理 2021-11-2458p.v操作操作/ *原语原语l p(s) l s.value=s.value-1;l if (s.value0)l 该进程状态置为等待态该进程状态置

58、为等待态l 将该进程的将该进程的pcb插入相应的等待队列未尾插入相应的等待队列未尾s.queue;l l l v(s) l s.value=s.value+1;l if (s.value0:ss0:s表示可用资源的个数表示可用资源的个数. .s=0:ss=0:s表示无资源使用表示无资源使用, ,也无等待进程也无等待进程. .s0: s0: 表示等待队列中进程的个数表示等待队列中进程的个数sp.vp.v操作总结操作总结: :1. 1. 信号量的物理意义信号量的物理意义p(s):p(s):表示申请或使用一个资源表示申请或使用一个资源. .因此因此s=s-1;s=s-1;v(s):v(s):表示释放

59、一个资源表示释放一个资源. .因此因此s=s+1;s=s+1;信号量的初值应该大于等于信号量的初值应该大于等于0 0说明说明: :2. p.v2. p.v操作必须成对出现操作必须成对出现, ,有一个有一个p p操作就一定有一个操作就一定有一个v v操作操作当为互斥操作时当为互斥操作时, ,它们处于同一进程它们处于同一进程. .当为同步操作时当为同步操作时, ,则不在同一进程则不在同一进程. .如果如果p(s1)p(s1)和和p(s2)p(s2)两个操作在一起两个操作在一起, ,那么那么p p操作的顺序至关重要操作的顺序至关重要, ,一个同步一个同步p p操作与一个互斥操作与一个互斥p p操作在一起时操作在一起时, ,同步同步p p操作在互斥操作在互斥p p操作前操作前, ,而两个而两个v v操作无操作无关紧要关紧要. .第三章 进 程 管 理 2021-11-24763. p.v3. p.v操作的优缺点操作的优缺点优点优点: :简单简单, ,而且表达能力强而且表达能力强( (用用p.vp.v操作可以解决任何同步互斥问题操作可以解决任何同步互斥问题) )不够安全不够安全. .p.vp.v操作使用不当会出现死锁操作使用不当会出现死锁. .遇到复杂同步互斥问题时实现复杂遇到复杂同步互斥问题时实现复杂缺点缺点: :第三章 进 程 管 理 2021-1