第二章 进程管理2

第二章进程管理第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.7线程的基本概念2.4经典进程同步问题2.5管程机制2.6进程通信2.1进程的基本概念1)程序的顺序执行与并发执行☆前驱图①程序的顺序执行特征：顺序性---操作按程序规定顺序执行封闭性---独占全机资源，不受外界影响可再现性---只要执行环境相同，初始条件相同，程序反复执行时结果相同1I1C1P2I2C2PPjPiPi是Pj的前趋，Pj是Pi的后继②程序的并发执行并发执行的特征：间断性失去封闭性不可再现性P1P2tI/OCPU两个程序并发执行示意图观察者beginrepeatwaitforacarthroughN=N+1untilend报告者beginrepeatdelayprintNN=0untilend初始N=n时不同执行序列，结果各不相同执行序列123程序N=N+1printNN=0printNN=0N=N+1printNN=N+1N=0结果例子：观察者与报告者打印n+1,N=0打印n,N=1打印n,N=02)进程（process）的定义与特征①描述：本质上来说一个进程就是一个执行的程序，是一个具有独立功能的程序在一个数据集合上的一次动态执行过程，是计算机资源的使用主体，拥有独立的地址空间。②定义：进程实体的运行过程，是OS进行资源分配和调度的基本单位。③特征结构特征---进程实体=程序段+数据段+进程控制块(PCB)动态性---进程是进程实体的一次执行过程，进程要经历“发生，发展和消亡”的动态变化过程。并发性---在一个时间间隔内多个进程同时运行。独立性---独立运行，独立分配资源和独立接受调度。异步性---按各自独立的不可预知的速度向前推进程序与进程之区别程序进程静态动态永久有生命周期由程序段组成通过多次执行一个程序可对应多个进程进程实体通过调用一个进程可包含多个程序3)进程的状态及其转换①三种基本状态及其转换：就绪状态---已经获得所需资源，只等待CPU，所有处在就绪状态的进程排在就绪队列上。执行状态---正在运行中。阻塞状态---进程等待某个事件，如等待I/O完成，等待某个资源，处于暂停状态。所有处在阻塞状态的进程排在队列上(一个或多个队列)。此外还可以有新建态和终止态。进程状态的转换新建终止就绪阻塞运行创建完毕时间片用完结束执行选中等待事件等待结束②具有挂起状态的状态图执行活动就绪静止就绪挂起挂起激活静止阻塞活动阻塞激活挂起唤醒唤醒阻塞引起挂起状态的原因：终端用户的需要---暂停执行，查清问题。父进程的需求---考查和修改子进程，或要协调各子进程间的活动。操作系统的需要---检查运行中资源的使用情况及进行记帐，以便改善系统运行的性能。负荷调节的需要---当实时系统中工作负荷较重影响对实时任务的控制时，系统把一些不重要的进程挂起，以保证系统正常运行。4)进程控制块（PCB）ProcessControlBlock①PCB：由系统维护用于记录进程基本情况信息，以对进程实施控制与管理的辅助数据结构（表），PCB是进程存在与否的唯一标志，每个进程在系统中都有相应的PCB，内容随进程的运行而动态改变，而且PCB处于系统核心，通常不能由应用程序直接访问。作用是使多道程序环境中不能独立运行的程序成为一个能独立运行的基本单位②PCB包含的内容PCB中一般包括进程描述信息、处理器状态信息、进程调度信息和进程控制信息4部分。具体内容见下页：①进程标识符信息②处理机状态信息③进程调度信息④进程控制信息内部标识符外部标识符通用寄存器指令计数器程序状态字用户栈指针进程状态进程优先级事件其它信息程序和数据的地址进程同步和通信机制资源清单PCB③PCB的组织方式(逻辑结构）将处于同一状态的进程组织在一起链接方式同一状态的进程其PCB成一链表，多个状态对应多个不同的链表PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针…索引方式同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针2.2进程控制进程控制：进程的创建、撤消，进程状态转换的控制。进程控制由进程控制原语和系统调用等在OS内核中实现，是OS进程管理的最基本功能。进程创建进程终止进程的阻塞与唤醒进程的挂起与激活注：内核：OS的核心层部分，包括中断处理、时钟管理……原语：OS内核中能完成某特定功能的小程序，其在执行期间不允许被分割AA22A21A11A2A1进程创建①进程图：描述进程之间的创建关系的有向树子进程可以继承父进程拥有的资源，撤销父进程时同时撤销其所有子进程,父子进程并发执行，父进程等待子进程执行结束②引起进程创建的相关事件（因素）用户登陆（在分时系统中）作业调度（在批处理系统中）提供服务（用户提出请求）应用请求（用户程序引发）③进程创建步骤及算法流程（创建原语调用Create()）a)为新进程分配空白PCB表b)初始化PCB，分配资源，填入相关数据c)置PCB状态为就绪d)PCB插入就绪队列，插入进程家族树进程终止①引起进程终止的因素进程正常运行结束出错或异常结束外界干预，强行终止②进程终止的步骤及过程（终止原语）a)若被终止进程正在执行，则释放CPUb)终止（撤消）该进程的所有子进程c)释放资源，归还给父进程或系统d)将其PCB从相关队列中摘除，释放PCB进程阻塞与唤醒①引起进程阻塞（唤醒）的因素请求系统服务（请求得到满足）启动某种操作（操作完成）等待新数据到达（新数据已送达）进程完成任务，暂无事可做（又有新任务）②进程阻塞的步骤及过程（阻塞或睡眠原语）a)暂停执行，释放CPUb)置再（重新）调度标志c)保存CPU现场信息d)置PCB状态为阻塞，PCB插入对应阻塞队列③进程唤醒的步骤及过程（唤醒原语）a)将被唤醒进程PCB从阻塞队列中摘除b)置PCB状态为就绪c)将PCB插入就绪队列注：阻塞为自行操作，唤醒为他人行为。2.3进程同步1)进程同步和互斥的相关概念进程同步：多个进程中发生的事件存在某种时序关系，必须协同工作、相互配合，以共同完成一项任务。进程互斥：由于共享资源所要求的排他性，进程间要相互竞争，以获得这些资源的使用权。临界资源（独占资源）：指在一段时间内只允许一个进程访问的资源。其中访问临界资源所对应的程序段叫临界区。注：有些共享资源可以同时访问则不是临界资源，如只读数据。进程间的同步司机和售票员的同步正常行驶开车到站停车关车门开车门售票员售票司机进程的互斥互斥使用资源进程A（阻塞）请求资源R进程B释放资源R请求资源R（使用R）释放资源RR分配拒绝唤醒练习：进程之间存在哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？①若干同学去图书馆借书；②两队举行篮球比赛；③流水线生产的各道工序；④商业生产和社会消费。答案：进程间存在直接制约和间接制约两种制约关系，其中直接制约（同步）是由于进程间的相互合作引起的；间接制约（互斥）是由于进程间共享临界资源引起的。①是间接制约，其中书是临界资源②是间接制约，其中篮球是临界资源③是直接制约，因为各道工序需要相互合作④是直接制约，因为两者也需要合作：商品生产出来后才能被消费；消费后才需要再生产临界资源与临界区（criticalsection）进程的互斥（间接作用）由于现在操作系统中的进程是并发执行的，各进程以自己的速度向前推进，所以，运行的顺序可能是：…P1：R1=count；P2：R2=count；P1：R1=R1+1；P1：count=R1；P2：R2=R2+1；P2：count=R2；错误：P1,P2执行的结果count只加了1临界区剩余部分进入代码退出代码Dijkstra在1965年提出了三条准则：（1）每次至多一个进程处于临界区（2）若有多个进程同时要求进入它们的临界区，应该在有限的时间内让其中一个进入而不应该相互阻塞（3）进程在临界区中逗留有限时间临界区的访问进程同步及其应遵守的规则同步机制是指为实现对临界资源互斥访问的机制。所有的同步机制都应遵循四条准则：空闲让进忙则等待有限等待让权等待（有效利用资源）（对资源互斥访问）（避免陷入“死等”状态）（避免陷入“忙等”状态）2)信号量机制整型信号量记录型信号量AND型信号量信号量集①整形信号量Dijkitra把整型信号量定义为一个整型量s。除初始化外，仅能通过两个标准的原子操作即P操作wait(s)和V操作signal(s)来访问。wait和signal操作可描述为：wait(s)：whiles≤0dono-ops:＝s一1；signal(s)：s:＝s十1；注意：S表示空闲资源数，P操作申请一个资源,V操作释放一个资源。缺点:“忙等”，只要s≤0就不断测试，未遵循“让权等待”。P.V操作必须为原子操作P.V操作必须成对出现。②记录型信号量机制增加一个进程链表L，将等待同一临界资源的进程链成链表信号量SS.V信号量的值S.L信号量对应资源等待队列指针P（S）（wait（S））S.V--S.V0？YN阻塞调用进程插入S.L队列V（S）（signal（S））S.V++S.V0？YN唤醒S.L队列上进程注意：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型信号量将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进程使用完后在一起释放。对若干个临界资源的分配，采取原子操作方式，要么全部分配到进程，要么一个也不分配。④信号量集基于P,V只能对信号量施以增1或减1的操作，当需要N个资源时要执行N次很低效。于是每次分配之前测试该资源的数量是否大于申请的资源数，通过对AND信号量机制进行两方面扩充，形成一般化的“信号量集”机制。用P、V操作解决进程间同步问题用P，V操作实现进程同步的模型P1...v(s)P2p(s)...12PPP1是P2的前趋，P2是P1的后继利用信号量与P.V操作实现生产者-消费者进程同步问题生产者消费者一次只能放或取一个产品放产品取产品解答：单缓冲区、一个生产者和一个消费者：设置私用信号量为S1，S2，初值为1，0生产者进程Pwhile(true){生产一件产品;P(S1);/*申请一个空缓冲区*/放入一件产品；V(S2);/*释放缓冲区*/}消费者进程Qwhile(true){P(S2);/*申请一个满缓冲区*/拿出一件产品;V(S1);消费产品;}用P，V操作实现司机－售票员同步解答：设置信号量S车，S门，初值均为0司机进程while(true){正常行驶；到站停车；V(S门);P(S车);离站开车；}售票员进程while(true){售票；P(S门);开车门；关车门；V(S车);}司机进程while(true){正正正正正正正正正正V(S正);P(S正);正正正正正}售票员进程while(true){正正正P(S正);正正正正正正正正V(S正);}S正=1S正=-1，B注：司机到站-想继续开车阻塞附：P，V操作所实现的司机－售票员同步过程司机－售票员同步过程（续）：注：司机到站-想继续开车阻塞-售票员开车门司机进程while(true){正正正正正正正正正正V(S正);P(S正);正正正正正}售票员进程while(true){正正正P(S正);正正正正正正正正V(S正);}S正=0，继续S正=0,唤醒司机注：司机到站-想继续开车阻塞-售票员开车门-想继续开车门阻塞司机进程whil