第二进程管理2

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

2、去封闭性 不可再现性不可再现性p1p2ti/ocpu两个程序并发执行示意图观察者beginrepeat wait for a car through n=n+1untilend报告者beginrepeat delay print n n=0untilend初始n=n时不同执行序列，结果各不相同执行序列 123程序n=n+1print nn=0print nn=0n=n+1print nn=n+1n=0结果例子：观察者与报告者打印n+1,n=0打印n, n=1打印n, n=02) 进程（process）的定义与特征描述：描述：本质上来说一个进程就是一个执行的程序，是一个具有独立功能的程序在一个数

3、据集合上的一次动态执行过程，是计算机资源的使用主体，拥有独立的地址空间。定义：进程实体的定义：进程实体的运行过程，是运行过程，是os进行资源分配和调度进行资源分配和调度的基本单位。的基本单位。特征特征 结构特征结构特征- 进程实体=程序段+数据段+进程控制块(pcb) 动态性动态性- 进程是进程实体的一次执行过程，进程要经历“发生，发 展和消亡”的动态变化过程。 并发性并发性- 在一个时间间隔内多个进程同时运行。 独立性独立性- 独立运行，独立分配资源和独立接受调度。 异步性异步性- 按各自独立的不可预知的速度向前推进 程序与进程之区别程序与进程之区别程序程序静态永久由程序段组成通过多次执行一

4、个程 序可对应多个进程进程进程动态有生命周期进程实体通过调用一个进程可包含多个程序3) 进程的状态及其转换 三种基本状态及其转换：l 就绪状态就绪状态-已经获得所需资源，只等待cpu，所有处在就绪状态的进程排在就绪队列上。l 执行状态执行状态-正在运行中。l 阻塞状态阻塞状态-进程等待某个事件，如等待i/o完成，等待某个资源，处于暂停状态。所有处在阻塞状态的进程排在队列上(一个或多个队列)。此外还可以有新建态和终止态。v进程状态的转换新建终止就绪阻塞运行创建完毕时间片用完结束执行选中等待事件等待结束 具有挂起状态的状态图执行执行活动活动就绪就绪静止静止就绪就绪挂起挂起挂起挂起激活激活静止静止阻

5、塞阻塞活动活动阻塞阻塞激活激活挂起挂起唤醒唤醒唤醒唤醒阻塞阻塞引起挂起状态的原因： 终端用户的需要终端用户的需要-暂停执行，查清问题。 父进程的需求父进程的需求-考查和修改子进程，或要协调各子进程间的活动。 操作系统的需要操作系统的需要-检查运行中资源的使用情 况及进行记帐，以便改善系统运行的性能。 负荷调节的需要负荷调节的需要-当实时系统中工作负荷较重影响对实时任务的控制时，系统把一些不重要的进程挂起，以保证系统正常运行。4) 进程控制块（pcb）process control block pcb：由系统维护用于记录进程基本情况信息，以对进程实施控制与管理的辅助数据结构（表）， pcbpcb

6、是是进程存在进程存在与否的与否的唯一标志唯一标志. .作用是使多道程序环境中不能独立运行的程序成为一个能独立运行的基本单位 pcb包含的内容包含的内容pcb中一般包括进程描述信息、处理器状态信息、进程调度信息和进程控制信息4部分。 具体内容见下页：进程标识符信息处理机状态信息进程调度信息进程控制信息内部标识符外部标识符通用寄存器指令计数器程序状态字用户栈指针进程状态进程优先级事件其它信息程序和数据的地址进程同步和通信机制资源清单pcb 将处于同一状态的进程组织在一起将处于同一状态的进程组织在一起 同一状态的进程其pcb成一链表，多个状态对应多个不同的链表pcb14pcb2pcb3pcb4pcb

7、5pcb6pcb7pcb8pcb93087901执行指针就绪队列指针阻塞队列指针空闲队列指针l 索引方式 同一状态的进程归入一个index表（由index指向pcb）， 多个状态对应多个不同的index表执行指针就绪索引表pcb1pcb2pcb3pcb4pcb5pcb6pcb7阻塞索引表就绪表指针阻塞表指针2.2 进程控制 进程控制进程控制：进程的创建、撤消，进程状态转换的控 制。进程控制由进程控制原语和系统调用等在os内核中实现，是os进程管理的最基本功能。p 进程创建p 进程终止p 进程的阻塞与唤醒p 进程的挂起与激活 注：注：内核：os的核心层部分，包括中断处理、时钟管理 原语：os内核

8、中能完成某特定功能的小程序，其在执行期间不允许被分割aa22a21a11a2a1n 进程创建进程创建进程图：描述进程之间的创建关系的有向树 子进程可以继承父进程拥有的资源，撤销父进程时同时撤销其所有子进程子进程可以继承父进程拥有的资源，撤销父进程时同时撤销其所有子进程, 父子进程并发执行，父进程等待子进程执行结束父子进程并发执行，父进程等待子进程执行结束 引起进程创建的相关事件（因素）v用户登陆（在分时系统中）v作业调度（在批处理系统中）v提供服务（用户提出请求）v应用请求（用户程序引发） 进程创建步骤及算法流程（创建原语调用create() ）a)为新进程分配空白pcb表b)初始化pcb，分

9、配资源，填入相关数据c)置pcb状态为就绪d)pcb插入就绪队列，插入进程家族树n 进程终止进程终止引起进程终止的因素v进程正常运行结束v出错或异常结束v外界干预，强行终止进程终止的步骤及过程（终止原语）a)若被终止进程正在执行，则释放cpub)终止（撤消）该进程的所有子进程c)释放资源，归还给父进程或系统d)将其pcb从相关队列中摘除，释放pcbn 进程阻塞与唤醒进程阻塞与唤醒引起进程阻塞（唤醒）的因素引起进程阻塞（唤醒）的因素v请求系统服务 （请求得到满足）v启动某种操作 （操作完成）v等待新数据到达 （新数据已送达 ）v进程完成任务，暂无事可做 （又有新任务）进程阻塞的步骤及过程（阻塞或

10、睡眠原语）进程阻塞的步骤及过程（阻塞或睡眠原语）a)暂停执行，释放cpub)置再（重新）调度标志c)保存cpu现场信息d)置pcb状态为阻塞，pcb插入对应阻塞队列进程唤醒的步骤及过程（唤醒原语）进程唤醒的步骤及过程（唤醒原语）a)将被唤醒进程pcb从阻塞队列中摘除b)置pcb状态为就绪c)将pcb插入就绪队列注：阻塞为自行操作，唤醒为他人行为。注：阻塞为自行操作，唤醒为他人行为。2.3 进程同步1)进程同步和互斥的相关概念n进程同步：多个进程中发生的事件存在某种时序关系，必须协同工作、相互配合，以共同完成一项任务。n进程互斥：由于共享资源所要求的排他性，进程间要相互竞争，以获得这些资源的使用

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

12、案：进程间存在直接制约和间接制约两种制约关系，其中直接制约（同步）是由于进程间的相互合作引起的；间接制约（互斥）是由于进程间共享临界资源引起的。 是间接制约，其中书是临界资源 是间接制约，其中篮球是临界资源 是直接制约，因为各道工序需要相互合作 是直接制约，因为两者也需要合作：商品生产出来后才能被消费；消费后才需要再生产v临界资源与临界区临界资源与临界区（ critical sectioncritical section ） 进程的互斥进程的互斥（间接作用）（间接作用）由于现在操作系统中的进程是并发执行的，各进程以自己的速度向前推进，所以，运行的顺序可能是： p1：r1 = count； p2

13、：r2 = count； p1：r1 = r1 + 1； p1：count = r1； p2：r2 = r2 +1； p2：count = r2；错误：错误：p1,p2 p1,p2 执行的结果执行的结果countcount只加了只加了1 1临界区临界区剩余部分剩余部分进入代码进入代码退出代码退出代码dijkstradijkstra在在19651965年提出了三条准则：年提出了三条准则：（1 1）每次至多一个进程处于临界区）每次至多一个进程处于临界区（2 2）若有多个进程同时要求进入它们的临界区，应该在有）若有多个进程同时要求进入它们的临界区，应该在有限的时间内让其中一个进入而不应该相互阻塞限的

14、时间内让其中一个进入而不应该相互阻塞（3 3）进程在临界区中逗留有限时间）进程在临界区中逗留有限时间 临界区的访问临界区的访问n进程同步及其应遵守的规则 同步机制是指为实现对临界资源互斥访问的机制。所有的同步机制都应遵循四条准则： 空闲让进空闲让进 忙则等待忙则等待 有限等待有限等待 让权等待让权等待（有效利用资源）（有效利用资源） （对资源互斥访问）（对资源互斥访问） （避免陷入（避免陷入“死等死等”状态）状态） （避免陷入（避免陷入“忙等忙等”状态）状态） 2) 信号量机制信号量机制v整型信号量v记录型信号量vand型信号量v信号量集整形信号量 dijkitra把整型信号量定义为一个整型量

15、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，将等待同一临界资源的进程链成链表信号量信号量ss.v 信号量的值信号量的值s.l 信号量对应资源等待队列指针信号量对应资源等待队列指针p p（s

16、s）（）（waitwait（s s） s.v-s.v0 表示某类可用资源的数量 =0 其绝对值表示因请求该资源而被阻塞的进程数 s.v的初值为1时，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量；实现进程间的同步时，s.v初始值通常设为0或n。 利用信号量s和上述p,v操作实现进程互斥时s.v的初值置为1的过程如下： p1p（s）临界区临界区1v（s）p2p（s）临界区临界区2v（s）and型信号量 将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进程使用完后在一起释放。对若干个临界资源的分配，采取原子操作方式，要么全部分配到进程，要么一个也不分配。信号量

17、集 基于p,v只能对信号量施以增1或减1的操作，当需要n个资源时要执行n次很低效。于是每次分配之前测试该资源的数量是否大于申请的资源数，通过对and信号量机制进行两方面扩充，形成一般化的“信号量集”机制。用用p p、v v操作解决进程间同步问题操作解决进程间同步问题v用用p，v操作实现进程同步的模型操作实现进程同步的模型p1.v(s)p2p(s).12pp p1是p2的前趋，p2是p1的后继v利用信号量与利用信号量与p.vp.v操作实现生产者操作实现生产者- -消费者进程同步消费者进程同步问题问题生产者消费者一次只能放或取一个产品放产品取产品解答解答：单缓冲区、一个生产者和一个消费者：设置私

18、用信号量为s1，s2，初值为1，0生产者进程pwhile(true)生产一件产品;p(s1);/*申请一个空缓冲区*/放入一件产品；v(s2); /*释放缓冲区*/消费者进程qwhile(true)p(s2); /*申请一个满缓冲区*/拿出一件产品;v(s1);消费产品;v用用p，v操作实现司机售票员同步操作实现司机售票员同步 解答：设置信号量s车，s门，初值均为0司机进程while(true)正常行驶；到站停车；v(s门);p(s车);离站开车；售票员进程while(true)售票；p(s门); 开车门；关车门；v(s车);注：司机到站-想继续开车阻塞附：附：p p，v v操作所实现的司机售

19、票员同步过程操作所实现的司机售票员同步过程司机售票员同步过程（续）司机售票员同步过程（续）：注：司机到站-想继续开车阻塞-售票员开车门注：司机到站-想继续开车阻塞-售票员开车 门-想继续开车门阻塞司机售票员同步过程（续）司机售票员同步过程（续）：注：司机到站-想继续开车阻塞-售票员开车 门-想继续开车门阻塞-司机继续行车司机售票员同步过程（续）司机售票员同步过程（续）：用用p p、v v操作解决进程间互斥问题操作解决进程间互斥问题p(s)v(s)p1p2p3互斥区互斥区p(s)p(s)v(s)v(s) （设信号量（设信号量:s=1:s=1） 申请进入申请进入临界区临界区退出退出临临界区界区v用

20、用p，v操作实现进程互斥的模型操作实现进程互斥的模型v 用用p，v操作解决共享操作解决共享count变量的问题变量的问题执行序列：执行序列：p2p2执行序列：执行序列：p2p2（就绪）（就绪）-p1-p1（阻塞）（阻塞）- - 用用p，v操作解决共享操作解决共享count变量的问题（续）变量的问题（续）执行序列：执行序列：p2p2（就绪）（就绪）-p1-p1（阻塞）（阻塞）- - p3（阻塞）（阻塞） 用用p，v操作解决共享操作解决共享count变量的问题（续）变量的问题（续）执行序列：执行序列：p2p2（就绪）（就绪）-p1-p1（阻塞）（阻塞）- - p3（阻塞）（阻塞）- p2用用p，v

21、操作解决共享操作解决共享count变量的问题（续）变量的问题（续）执行序列：执行序列：p2p2（就绪）（就绪）-p1-p1（阻塞）（阻塞）- - p3（阻塞）（阻塞）- p2-p1用用p，v操作解决共享操作解决共享count变量的问题（续）变量的问题（续）执行序列：执行序列：p2p2（就绪）（就绪）-p1-p1（阻塞）（阻塞）- - p3（阻塞）（阻塞）- p2-p1-p3信号量变化范围：信号量变化范围：, , , , 即（即（-n-n）用用p，v操作解决共享操作解决共享count变量的问题（续）变量的问题（续）2.4 经典的进程同步问题经典的进程同步问题l 生产者生产者-消费者问题消费者问题

22、共享缓冲区生产指针消费指针producer 1producer 2.producer mconsumer 1consumer 2.consumer n满空指针移动方向解析解析：n个缓冲区、k个生产者和m个消费者：增加互斥信号量mutex，初值为1，并设s1，s2，初值分别为n和0。生产者进程pwhile(true)生产一件产品;p(s1);/*申请一个空缓冲区*/p(mutex);放入一件产品；v(mutex);v(s2); /*释放缓冲区*/消费者进程qwhile(true)p(s2); /*申请一个满缓冲区*/p(mutex);拿出一件产品;v(mutex);v(s1);消费产品;两个p操

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

24、e是写信号量，初值为1。读者进程beginp(mutex);readnum=readnum+1;if (readnum=1) p(write);v(mutex);read file;p(mutex);readnum=readnum1;if (readnum=0) v(write);v(mutex);end写者进程beginp(write);write file;v(write);end第一个读者来执行p操作最后一个读者来执行v操作小结：信号量及小结：信号量及p.vp.v操作操作v信号量信号量（semaphoresemaphore）: :表示资源的实体，是一个与队表示资源的实体，是一个与队列有关

25、的整型变量，其值仅能由列有关的整型变量，其值仅能由p p、v v操作改变。操作改变。v信号量类型信号量类型：互斥互斥/ /公用信号量和同步公用信号量和同步/ /私用信号量私用信号量互斥信号量互斥信号量: :用于实现进程间的互斥。初值通常设用于实现进程间的互斥。初值通常设为为1 1，它所联系的一组并行进程均可对它实施，它所联系的一组并行进程均可对它实施p p、v v操作。操作。同步信号量：同步信号量：用于实现进程间的同步，初始值通常用于实现进程间的同步，初始值通常设为设为0 0或或n n，允许拥有它的进程对其实施，允许拥有它的进程对其实施p p操作。操作。v 对对p p，v v操作的使用应注意：

26、操作的使用应注意：p p原语相当于原语相当于进入区进入区操作，操作，v v相当于相当于退出区退出区操作；遗操作；遗忘忘p p不能保证互斥访问，遗忘不能保证互斥访问，遗忘v v不能在使用后将资源不能在使用后将资源释放给其他等待的进程；释放给其他等待的进程； p p，v v操作都是操作都是成对出现成对出现的：的：互斥操作时，它们在同一进程中；同步操作时，它互斥操作时，它们在同一进程中；同步操作时，它们处于不同的进程。们处于不同的进程。在进程中，在进程中，p p操作的位置和次序至关重要。一般情况操作的位置和次序至关重要。一般情况下，对下，对互斥互斥信号量的信号量的p p操作操作在后在后。而。而v v

27、操作没有特别操作没有特别的限制。的限制。练习题1.设有一个作业有三个进程组成，这三个进程必须按如下所示的次序运行，试用p,v操作表达三个进程的同步关系。 t1t2t32. 用p,v操作实现下述问题的解。桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子里，而母亲总是放香蕉到盘子里，但一次只能有一个人成功放入水果，若放入的是香蕉则允许儿子吃，女儿必须等待；若放入盘子的是苹果则允许女儿吃，儿子必须等待。 2.5 进程通信 低级通信低级通信：只传送少量数据，且对用户不透明高级通信高级通信：可传送大量信息、数据，由o.s提供通信手段 并实施，对用户来说透明1) 高级进程通信类型高级进程通信类型p

28、共享存储器系统共享存储器系统p消息传递系统消息传递系统p管道通信系统管道通信系统n 共享存储器系统通过共享某些数据结构或共享存储区，进行通信。可分为：通过共享某些数据结构或共享存储区，进行通信。可分为： 基于共享数据结构的通信方式基于共享数据结构的通信方式 例如：生产者-消费者问题。属低级通信 基于共享存储区的通信方式基于共享存储区的通信方式 共享非格式化的存储区，公用的地址空间。属高级通信方式。n 消息传递系统进程间的数据交换以进程间的数据交换以格式化格式化的的消息消息(measege)为单位，通过为单位，通过利用利用os提供的通信原语进行通信，可分为：提供的通信原语进行通信，可分为： 直接

29、通信方式直接通信方式-信息直接传递给接收方。 间接通信方式间接通信方式-发送进程将消息发送到某种中间实体 中，接收进程从中取得消息。 n 管道通信 工作原理：利用工作原理：利用管道管道进行数据传送进行数据传送发送进程发送进程pipe文件文件字符流型数据字符流型数据接收进程接收进程注：类似生产者注：类似生产者消费者问题，要注意同步互斥的控制消费者问题，要注意同步互斥的控制2) 消息通信的实现方法消息通信的实现方法n消息缓冲通信（直接通信方式）工作原理：进程进程a进程进程bpcb（b）send（b，a）receive（b）sender：asize：5text：hello发发送送区区amqsende

30、r：asize：5text：hellonext：0sender：asize：5text：hello接接收收区区b第一消息缓冲区第一消息缓冲区abmutexsm相关数据结构消息结构消息结构：消息缓冲队列消息缓冲队列：pcb中用于消息通信的相关数据项中用于消息通信的相关数据项消息头消息头消息消息正文正文发送进程标识符、消息长度、类型、发送进程标识符、消息长度、类型、消息队列链接指针消息队列链接指针欲发送的信息数据存区欲发送的信息数据存区mqmutexsmpcb消息队列队首指针消息队列队首指针mq消 息 队 列 互 斥 信 号 量消 息 队 列 互 斥 信 号 量mutex消息队列资源信号量消息队列资源信号量sm（即队列消息个数计数）（即队列消息个数计数）消息缓冲区链成的队列，每个进程都有一个，其队首指针存放在对应进程的pcb中消息发送原语和接收原语发送原语发送原语 send（接收进程名，发送区首地址）（接收进程名，发送区首地址）接收原语接收原语 receive（接收区地址）（接收区地址）注：缓冲队列的插入、删除操作必须采取互斥措施注：缓冲队列的插入、删除操作必须采取互斥措施 发送原语算法流程发送原语算法流程 接收原语算法流程接收原语算法流程申请分配一个空白缓冲区申请分配一个空白缓冲区将数据从发送区拷贝到缓冲正文区将数据从发送区拷贝到缓冲正文区获取接收进程获取接收进