第二进程管理2.ppt

《第二进程管理2.ppt》由会员分享，可在线阅读，更多相关《第二进程管理2.ppt（66页珍藏版）》请在三一文库上搜索。

1、第二章 进程管理,第二章 进程管理,2.1进程的基本概念,2.2 进程控制,2.3 进程同步,2.7 线程的基本概念,2.4经典进程同步问题,2.5管程机制,2.6进程通信,2.1 进程的基本概念,1) 程序的顺序执行与并发执行 前驱图 程序的顺序执行 特征：顺序性-操作按程序规定顺序执行 封闭性-独占全机资源，不受外界影响 可再现性-只要执行环境相同，初始条件相 同，程序反复执行时结果相同,Pi是Pj的前趋，Pj是Pi的后继,程序的并发执行,并发执行的特征： 间断性 失去封闭性 不可再现性,观察者 begin repeat wait for a car through N=N+1 until

2、 end,报告者 begin repeat delay print N N=0 until end,初始N=n时不同执行序列，结果各不相同,例子：观察者与报告者,打印n+1,N=0,打印n, N=1,打印n, N=0,2) 进程（process）的定义与特征 描述：本质上来说一个进程就是一个执行的程序，是一个具有独立功能的程序在一个数据集合上的一次动态执行过程，是计算机资源的使用主体，拥有独立的地址空间。 定义：进程实体的运行过程，是OS进行资源分配和调度 的基本单位。 特征 结构特征- 进程实体=程序段+数据段+进程控制块(PCB) 动态性- 进程是进程实体的一次执行过程，进程要经历 “发生

3、，发 展和消亡”的动态变化过程。 并发性- 在一个时间间隔内多个进程同时运行。 独立性- 独立运行，独立分配资源和独立接受调度。 异步性- 按各自独立的不可预知的速度向前推进, 程序与进程之区别,3) 进程的状态及其转换 三种基本状态及其转换： 就绪状态-已经获得所需资源，只等待CPU，所有处在就绪状态的进程排在就绪队列上。 执行状态-正在运行中。 阻塞状态-进程等待某个事件，如等待I/O完成，等待某个资源，处于暂停状态。所有处在阻塞状态的进程排在队列上(一个或多个队列)。 此外还可以有新建态和终止态。,进程状态的转换,新建,终止,就绪,阻塞,运行,创建完毕,时间片用完,结束执行,选中,等待事

4、件,等待结束,具有挂起状态的状态图,引起挂起状态的原因： 终端用户的需要-暂停执行，查清问题。 父进程的需求-考查和修改子进程，或要协调各子进程间的活动。 操作系统的需要-检查运行中资源的使用情 况及进行记帐，以便改善系统运行的性能。 负荷调节的需要-当实时系统中工作负荷较重影响对实时任务的控制时，系统把一些不重要的进程挂起，以保证系统正常运行。,4) 进程控制块（PCB）Process Control Block,PCB：由系统维护用于记录进程基本情况信息，以对进程实施控制与管理的辅助数据结构（表）， PCB是进程存在与否的唯一标志.作用是使多道程序环境中不能独立运行的程序成为一个能独立运行

5、的基本单位 PCB包含的内容,PCB中一般包括进程描述信息、处理器状态信 息、进程调度信息和进程控制信息4部分。 具体 内容见下页：,进程标识符信息,处理机状态信息,进程调度信息,进程控制信息,内部标识符,外部标识符,通用寄存器指令计数器程序状态字用户栈指针,进程状态,进程优先级,事件,其它信息,程序和数据的地址,进程同步和通信机制,资源清单,PCB,PCB的组织方式(逻辑结构） 将处于同一状态的进程组织在一起 链接方式 同一状态的进程其PCB成一链表，多个状态对应多个不同的链表,索引方式 同一状态的进程归入一个index表（由index指向PCB）， 多个状态对应多个不同的index表,2.

6、2 进程控制,进程控制：进程的创建、撤消，进程状态转换的控 制。进程控制由进程控制原语和系统调用等在OS内核中实现，是OS进程管理的最基本功能。 进程创建 进程终止 进程的阻塞与唤醒 进程的挂起与激活 注：内核：OS的核心层部分，包括中断处理、时钟管理 原语：OS内核中能完成某特定功能的小程序，其在执行期间不 允许被分割,进程创建 进程图：描述进程之间的创建关系的有向树 子进程可以继承父进程拥有的资源，撤销父进程时同时撤销其所有子进程, 父子进程并发执行，父进程等待子进程执行结束,引起进程创建的相关事件（因素） 用户登陆（在分时系统中） 作业调度（在批处理系统中） 提供服务（用户提出请求） 应

7、用请求（用户程序引发） 进程创建步骤及算法流程（创建原语调用Create() ） 为新进程分配空白PCB表 初始化PCB，分配资源，填入相关数据 置PCB状态为就绪 PCB插入就绪队列，插入进程家族树,进程终止 引起进程终止的因素 进程正常运行结束 出错或异常结束 外界干预，强行终止 进程终止的步骤及过程（终止原语） 若被终止进程正在执行，则释放CPU 终止（撤消）该进程的所有子进程 释放资源，归还给父进程或系统 将其PCB从相关队列中摘除，释放PCB,进程阻塞与唤醒 引起进程阻塞（唤醒）的因素 请求系统服务 （请求得到满足） 启动某种操作 （操作完成） 等待新数据到达 （新数据已送达 ） 进

8、程完成任务，暂无事可做 （又有新任务） 进程阻塞的步骤及过程（阻塞或睡眠原语） 暂停执行，释放CPU 置再（重新）调度标志 保存CPU现场信息 置PCB状态为阻塞，PCB插入对应阻塞队列 进程唤醒的步骤及过程（唤醒原语） 将被唤醒进程PCB从阻塞队列中摘除 置PCB状态为就绪 将PCB插入就绪队列 注：阻塞为自行操作，唤醒为他人行为。,2.3 进程同步,进程同步和互斥的相关概念 进程同步：多个进程中发生的事件存在某种时序关系，必须协同工作、相互配合，以共同完成一项任务。 进程互斥：由于共享资源所要求的排他性，进程间要相互竞争，以获得这些资源的使用权。 临界资源（独占资源）：指在一段时间内只允许

9、一个进程访问的资源。其中访问临界资源所对应的程序段叫临界区。 注：有些共享资源可以同时访问则不是临界资源，如只读数据。,进程间的同步 司机和售票员的同步,正常行驶,开车,到站停车,关车门,开车门,售票员,售票,司机,进程的互斥 互斥使用资源,进程A,（阻塞）,请求资源R,进程B,请求资源R,R,练习：进程之间存在哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？ 若干同学去图书馆借书； 两队举行篮球比赛； 流水线生产的各道工序； 商业生产和社会消费。,答案：进程间存在直接制约和间接制约两种制约关系，其中直接制约（同步）是由于进程间的相互合作引起的；间接制约（互斥）是由于进程间共

10、享临界资源引起的。 是间接制约，其中书是临界资源 是间接制约，其中篮球是临界资源 是直接制约，因为各道工序需要相互合作 是直接制约，因为两者也需要合作：商品生产出来后才能被消费；消费后才需要再生产,临界资源与临界区（ critical section ）,进程的互斥 （间接作用）,由于现在操作系统中的进程是并发执行的，各进程以自己的速度向前推进，所以，运行的顺序可能是： P1：R1 = count； P2：R2 = count； P1：R1 = R1 + 1； P1：count = R1； P2：R2 = R2 +1； P2：count = R2；,错误：P1,P2 执行的结果count只加了

11、1,临界区,剩余部分,进入代码,退出代码,Dijkstra在1965年提出了三条准则： （1）每次至多一个进程处于临界区 （2）若有多个进程同时要求进入它们的临界区，应该在有限的时间内让其中一个进入而不应该相互阻塞 （3）进程在临界区中逗留有限时间,临界区的访问,进程同步及其应遵守的规则 同步机制是指为实现对临界资源互斥访问的机制。所有的同步机制都应遵循四条准则： 空闲让进 忙则等待 有限等待 让权等待,（有效利用资源）,（对资源互斥访问）,（避免陷入“死等”状态）,（避免陷入“忙等”状态）,2) 信号量机制,整型信号量 记录型信号量 AND型信号量 信号量集,整形信号量 Dijkitra把整

12、型信号量定义为一个整型量s。除初始化外，仅 能通过两个标准的原子操作即P操作wait(s)和V操作signal(s) 来访问。 wait和signal操作可描述为： wait(s)： while s0 do no-op s:s一1； signal(s)： s:s十1； 注意： S表示空闲资源数，P操作申请一个资源,V操作释放一个资源。 缺点: “忙等”，只要s0就不断测试，未遵循“让权等待” 。 P.V操作必须为原子操作 P.V操作必须成对出现。,记录型信号量机制 增加一个进程链表L，将等待同一临界资源的进程链成链表,注意： S.V 0 表示某类可用资源的数量 =0 其绝对值表示因请求该资源而

13、被阻塞的进程数 S.V的初值为1时，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量；实现进程间的同步时，S.V初始值通常设为0或n。 利用信号量S和上述P,V操作实现进程互斥时S.V的初值置为1的过程如下：,AND型信号量 将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进程使用完后在一起释放。对若干个临界资源的分配，采取原子操作方式，要么全部分配到进程，要么一个也不分配。 信号量集 基于P,V只能对信号量施以增1或减1的操作，当需要N个资源时要执行N次很低效。于是每次分配之前测试该资源的数量是否大于申请的资源数，通过对AND信号量机制进行两方面扩充，形成

14、一般化的“信号量集”机制。,用P、V操作解决进程间同步问题,用P，V操作实现进程同步的模型,P1是P2的前趋，P2是P1的后继,利用信号量与P.V操作实现生产者-消费者进程同步问题,解答：单缓冲区、一个生产者和一个消费者：设置私 用信号量为S1，S2，初值为1，0,生产者进程P while(true) 生产一件产品; P(S1);/*申请一个空缓冲区*/ 放入一件产品； V(S2); /*释放缓冲区*/ ,消费者进程Q while(true) P(S2); /*申请一个满缓冲区*/ 拿出一件产品; V(S1); 消费产品; ,用P，V操作实现司机售票员同步 解答：设置信号量S车，S门，初值均为

15、0,司机进程 while(true) 正常行驶； 到站停车； V(S门); P(S车); 离站开车； ,售票员进程 while(true) 售票； P(S门); 开车门； 关车门； V(S车); ,注：司机到站-想继续开车阻塞,附：P，V操作所实现的司机售票员同步过程,司机售票员同步过程（续）：,注：司机到站-想继续开车阻塞-售票员开车门,注：司机到站-想继续开车阻塞-售票员开车 门-想继续开车门阻塞,司机售票员同步过程（续）：,注：司机到站-想继续开车阻塞-售票员开车 门-想继续开车门阻塞-司机继续行车,司机售票员同步过程（续）：,用P、V操作解决进程间互斥问题,（设信号量:s=1）,申请进

16、入临界区,退出临界区,用P，V操作实现进程互斥的模型,用P，V操作解决共享count变量的问题,执行序列：P2,执行序列：P2（就绪）-P1（阻塞）-,用P，V操作解决共享count变量的问题（续）,执行序列：P2（就绪）-P1（阻塞）- P3（阻塞）,用P，V操作解决共享count变量的问题（续）,执行序列：P2（就绪）-P1（阻塞）- P3（阻塞）- P2,用P，V操作解决共享count变量的问题（续）,执行序列：P2（就绪）-P1（阻塞）- P3（阻塞）- P2-P1,用P，V操作解决共享count变量的问题（续）,执行序列：P2（就绪）-P1（阻塞）- P3（阻塞）- P2-P1-P3

17、,信号量变化范围：, 即（-n）,用P，V操作解决共享count变量的问题（续）,2.4 经典的进程同步问题,生产者-消费者问题,解析：n个缓冲区、k个生产者和m个消费者：增加互斥信号量mutex，初值为1，并设S1，S2，初值分别为n和0。,生产者进程P while(true) 生产一件产品; P(S1);/*申请一个空缓冲区*/ P(mutex); 放入一件产品； V(mutex); V(S2); /*释放缓冲区*/ ,消费者进程Q while(true) P(S2); /*申请一个满缓冲区*/ P(mutex); 拿出一件产品; V(mutex); V(S1); 消费产品; ,两个P操作

18、交换？,读者-写者问题 对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读写”互斥，“写写”互斥，“读读”允许 分 析：写进程之间互斥，访问时必须独占资源。需设置一个全局变量对读进程进行计数，当第一个读进程开始进行访问时执行P操作，当最后一个读进程结束访问时执行V操作。,解析：现假设读者优先。使用readnum对读者计数，初值为0；mutex是对readnum进行互斥操作的信号量，初值为1；write是写信号量，初值为1。,读者进程 begin P(mutex); readnum=readnum+1; if (readnum=1) P(write); V(mutex

19、); read file; P(mutex); readnum=readnum1; if (readnum=0) V(write); V(mutex); end,写者进程 begin P(write); write file; V(write); end,第一个读者来执行P操作,最后一个读者来执行V操作,小结：信号量及P.V操作,信号量（Semaphore）:表示资源的实体，是一个与队列有关的整型变量，其值仅能由P、V操作改变。 信号量类型：互斥/公用信号量和同步/私用信号量 互斥信号量:用于实现进程间的互斥。初值通常设为1，它所联系的一组并行进程均可对它实施P、V操作。 同步信号量：用于实现

20、进程间的同步，初始值通常设为0或n，允许拥有它的进程对其实施P操作。,对P，V操作的使用应注意： P原语相当于进入区操作，V相当于退出区操作；遗忘P不能保证互斥访问，遗忘V不能在使用后将资源释放给其他等待的进程； P，V操作都是成对出现的：互斥操作时，它们在同一进程中；同步操作时，它们处于不同的进程。 在进程中，P操作的位置和次序至关重要。一般情况下，对互斥信号量的P操作在后。而V操作没有特别的限制。,练习题,1.设有一个作业有三个进程组成，这三个进程必须按如下所示的次序运行，试用P,V操作表达三个进程的同步关系。,2. 用P,V操作实现下述问题的解。桌子上有一个盘子，可以存放一个水果。父亲总

21、是放苹果到盘子里，而母亲总是放香蕉到盘子里，但一次只能有一个人成功放入水果，若放入的是香蕉则允许儿子吃，女儿必须等待；若放入盘子的是苹果则允许女儿吃，儿子必须等待。,2.5 进程通信 低级通信：只传送少量数据，且对用户不透明 高级通信：可传送大量信息、数据，由O.S提供通信手段 并实施，对用户来说透明 1) 高级进程通信类型 共享存储器系统 消息传递系统 管道通信系统,共享存储器系统 通过共享某些数据结构或共享存储区，进行通信。可分为： 基于共享数据结构的通信方式 例如：生产者-消费者问题。属低级通信 基于共享存储区的通信方式 共享非格式化的存储区，公用的地址空间。属高级通信方式。 消息传递系

22、统 进程间的数据交换以格式化的消息(measege)为单位，通过 利用OS提供的通信原语进行通信，可分为： 直接通信方式-信息直接传递给接收方。 间接通信方式-发送进程将消息发送到某种中间实体 中，接收进程从中取得消息。,管道通信 工作原理：利用管道进行数据传送,注：类似生产者消费者问题，要注意同步互斥的控制,2) 消息通信的实现方法 消息缓冲通信（直接通信方式） 工作原理：,相关数据结构 消息结构： 消息缓冲队列： PCB中用于消息通信的相关数据项,消息缓冲区链成的队列，每个进程都有 一个，其队首指针存放在对应进程的PCB中,消息发送原语和接收原语 发送原语 send（接收进程名，发送区首地

23、址） 接收原语 receive（接收区地址） 注：缓冲队列的插入、删除操作必须采取互斥措施, 发送原语算法流程, 接收原语算法流程,信箱通信（间接通信方式） 工作原理 信箱头：信箱描述部分 信箱体：数据（消息）存放部分 信箱类型：私用信箱 共享信箱 公用信箱,2.6 线程,进程特征回顾 进程：可独立运行并拥有资源的基本单位，进程是可由O.S调度和分派的基本单位，同时也是可拥有系统资源的独立单位。 线程 定义：由进程创建，是进程中可以独立执行的子任务，是O.S调度和运行的基本单位 引入目的：是减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。,3) 线程的状态与控制 类同于进程；并可

24、实施进程间的同步与通信 4）线程和进程比较 调度方面： 并发性方面： 拥有资源方面： 系统开销方面： 5）线程的实现方式及其实现（了解）,线程是调度分派和独立运行的基本单位， 这时进程不再是一个可执行的实体；,进程之间可以并发执行，一个进程的多个线程之间也可并发执行；,进程作为拥有资源的基本单位，线程 除少量必不可少的资源外基本不拥有资源，但它可以访问其隶属的进程资源；,进程间切换涉及进程环境的改变开销大； 线程之间切换只要保存和设置少量内容 开销小。,本章小结 1）基本概念 程序并发执行的概念（与顺序执行的区别） 进程的概念（进程的引入、定义、特征或特性） 线程的概念（线程的引入，与进程之区别） 2）进程状态与进程控制块（PCB） 状态：就绪、执行、阻塞（状态间的转换原因） PCB：数据结构，包含进程基本情况信息、控制信息等 3）进程的同步与通信 互斥与同步的概念、定义、实施方法 高级通信的概念、通信类型（方式） 相关术语：临界资源、临界区、信号量 4）有关算法 进程控制原语：创建、终止、阻塞、唤醒 P.V操作原语：可实现进程的互斥与同步 进程通信原语：发送、接收,本章要点,掌握程序顺序执行与并发执行的特点 掌握进程的定义和特征，线程的定义，掌握程序与进程，进程与线程之间的区别 深入领会进程状态及引起状态变化的典型原因 掌握进程同步与互斥 能够灵活运用信号量描述同步问题,