操作系统第2章 进程管理

计算机操作系统主讲：白素琴计算机科学与技术系第2章进程管理系统中运行的是什么？程序执行的特点？现代os的特点？第2章进程管理那么现代os中，运行的究竟是什么？进程进程程序数据PCB记录：进程生命周期内与之相关的一切数据第2章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4进程通信2.5线程2.1进程的基本概念1、进程的定义：（各个操作系统中对进程的定义不统一）定义：进程是进程实体的运行过程。是进行系统资源分配、调度的最小单位2、进程的特征1）结构性：进程实体2）动态性3）并发性4）独立性5）异步性2.1进程的基本概念2.1进程的基本概念3、进程控制块（PCB）进程PPCB；Os进程P一一对应通过pcb进程标识符处理机状态进程调度信息进程控制信息2.1进程的基本概念4、进程的基本状态就绪R执行E阻塞B针对:单处理机,多道程序系统只有一个进程可以有一个进程队列可以有多个进程队列2.1进程的基本概念执行指针就绪队列指针阻塞队列1指针阻塞队列2指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67……PCB79PCB80PCB91典型的进程状态演变图2.1进程的基本概念分析：利：多道程序并行执行，改善了系统资源的利用率，提高了系统的吞吐量.弊：时空开销2.1进程的基本概念2.2进程控制怎么生成的？怎么结束的？怎么状态转变的？进程是。。。。。所有这些工作都是有os的内核中的进程控制原语实现的。？原语进程树:描述一个进程的家族关系的有向树。2.2进程控制ABCDEFGHIJKLM2.2进程控制进程控制原语：1．创建原语2．撤消原语3．阻塞原语4．唤醒原语2.2进程控制1．创建原语什么情况需要创建？如何创建？2.2进程控制2．撤销原语什么情况需要终止进程？如何终止？1、确保进程都在家族树内2、确保cpu尽量忙碌2.2进程控制3.阻塞和唤醒原语什么情况需要阻塞和唤醒进程？如何阻塞和唤醒？阻塞和唤醒的关系：1、进程在自己的执行过程中，阻塞自己。2、进程在执行过程中，可以唤醒其他进程。3、阻塞和唤醒必须是一一对应的！！Doyouhaveanyquestions?2.3进程同步1、进程之间的相互关系2、信号量机制3、信号量机制应用4、经典进程同步问题2.3进程同步1、间接制约方式这是由于竞争相同资源而引起的。2.3.1进程间的相互制约关系2.3进程同步PBt2t1t3cpu1PAPB写文件a文件aPA读文件aPA此时如果申请读文件，应该被禁止此时，PB可能结束；可能继续；也可能被其他进程抢占；此时，PA的运行受到了PB的制约t4PA例，现有两个进程PA，PB在他们的运行过程中都要访问文件a（2）直接制约方式。这是由于相互合作而引起的。2.3.1进程间的相互制约关系2.3进程同步PI：一个个地把数据输入bufPC：一个个地从buf中取出数据buf只能存放一个数据cpu1PI放第一个PC取第一个PI放第二个PC取第二个应该保证：在PC取走数之前，PI不能再放，否则，会漏掉一个数应该保证：在PI放一个数之前，PC不能再取，否则，会重复取数此时，PI和PC因为需要合作相互制约2.3.1进程间的相互制约关系2.3进程同步临界资源、临界区同步与互斥进入区退出区临界区同步机制必须遵循如下准则：空闲让进忙则等待有限等待：避免‘死等’（死锁）让权等待：退出临界区，立即释放处理机，让位给等待进程。避免‘忙等’。2.3.1进程间的相互制约关系2.3进程同步Doyouhaveanyquestions?1、整形信号量2、记录型信号量3、And型信号量4、信号量集2.3.2信号量机制2.3进程同步1965年，荷兰学者Dijkstra提出了信号量（semaphore）机制。1、整形信号量定义：Ints；初始值为资源数目。操作：2.3.2信号量机制2.3进程同步P（S）V（S）临界区WhileS=0donothing；S=S-1;S=S+1;2、记录型信号量定义：Typesemaphore=recordvalue:integer;L：listofprocess;end操作：2.3.2信号量机制2.3进程同步P（S）V（S）临界区S.value=S.value-1；IfS.value0thenBlock(S.L)S.value=S.value+1；IfS.value≤0thenBlock(S.L)VarS:semaphore3、AND型信号量2.3.2信号量机制2.3进程同步P（S1，S2，…Sn）V（S1，S2，…Sn）临界区要么全部分配一个，要么都不分配；每类资源回收一个；2.3.2信号量机制2.3进程同步4、信号量集机制P（S1,t1,d1,…,Sn,tn,dn）V（S1,t1,d1,…,Sn,tn,dn）临界区任何一个Si:如果Si》ti；则Si-diP(S,d,d)P(S,1,1)P(S,1,0)三种特殊情况：Doyouhaveanyquestions?2.3.3信号量机制的应用1。解决互斥问题2。解决前趋图问题2.3进程同步1.互斥问题一类资源公用信号量mutexN个共享该资源的进程的程序中，都要包含下列程序段。P（mutex）V（mutex）临界区2.3.3信号量机制的应用2.3进程同步举例：有1台打印机，两个并发执行进程p1、p2、p3.求采用记录型信号量机制，如何解决p1、p2、p3互斥访问打印机的问题。整形信号量机制记录型信号量机制Varmutex：Semaphore=1P（mutex）V（mutex）访问打印机的临界区2.3.3信号量机制的应用2.3进程同步2.3.3信号量机制的应用2.3进程同步p1p2p3P（mutex）V（mutex）打印机…………P（mutex）V（mutex）打印机…………P（mutex）V（mutex）打印机…………Mutex初始值=1；整形信号量机制0P3检测中P2检测中12.3.3信号量机制的应用2.3进程同步p1p2p3P（mutex）V（mutex）打印机…………P（mutex）V（mutex）打印机…………P（mutex）V（mutex）打印机…………S.Mutex初始值=1；-2P3阻塞中P2阻塞中记录型信号量机制p3p20-1S.L1P3被唤醒P2被唤醒分析：1、比较整形、记录型信号量机制2.3.3信号量机制的应用2.3进程同步让权等待分析：2、信号量取值范围及含义记录型s.value=0：表示系统当前可用的该类资源的数目0：其绝对值表示系统中因请求该类资源而被阻塞的进程数目（所以每个信号量都对应一个等待队列，即L）2.3.3信号量机制的应用2.3进程同步Doyouhaveanyquestions?2。解决前趋图问题2.3.3信号量机制的应用2.3进程同步2。解决前趋图问题2.3.3信号量机制的应用2.3进程同步S1S2S=0P1P2……S1…………S2……V(S)P(S)S=-1P2被阻塞S=0唤醒P2S1S2S3S5S4S6acedfgbVar.a,b,c,d,e,f,g：semaphore：=0，0，0，0，0，0，0BeginParbeginbeginS1；V（a）；V（b）；endbeginP（a）；S2；V（c）；V（d）；endbeginP（b）；S3；V（e）；endbeginP（c）；S4；V（f）；endbeginP（d）；S5；V（g）；endbeginP（f）；P（g）；P（e）；S1；endParendEnd2.3.3信号量机制的应用2.3进程同步2.3.4信号量机制的应用2.3进程同步分散！集中！三个组成!解决同步问题！管程机制Doyouhaveanyquestions?1．生产者与消费者问题2．哲学家就餐问题3.读者与写者问题2.3.4经典进程同步问题2.3进程同步1、生产者消与费者问题2.3.4经典进程同步问题2.3进程同步1、生产者消与费者问题问题描述N个P进程和M个CM+N个进程之间需要同步同样M+N个进程之间需要互斥访问缓冲池同步和互斥的抽象2.3.4经典进程同步问题2.3进程同步……PiCj2.3.4经典进程同步问题2.3进程同步1、生产者消与费者问题PiP（mutex）V(mutex）生产…………解决互斥关系定义互斥信号量mutex=1CjP(empty)V(full)P（mutex）V(mutex）消费…………P(full)V(empty）解决同步关系P：空闲的存储单元定义同步信号量empty=nC:装有产品的单元定义同步信号量full=0注意：1．每个程序中实现互斥的P(mutex),V(mutex)必须成对出现。2．Empty和full的P，V操作也必须成对出现，但它们处于不同的程序中。3.每个程序中的多个P操作不能颠倒顺序，否则可能引起死锁。2.3.4经典进程同步问题2.3进程同步练习1有一空盘，允许存放一只水果。爸爸可向盘中放苹果，妈妈可向盘中放桔子，儿子专等盘中的桔子吃，女儿专等盘中的苹果吃。请用P、V原语实现爸爸、妈妈、儿子、女儿四个进程的同步。2.3.4经典进程同步问题2.3进程同步问题分析2.3.4经典进程同步问题2.3进程同步1fpmpdpsp盘子空，就可放；放了后，dp就可取盘子有苹果空，就可取；取了后，fp，mp就放Empty=1Apple=0orange-=02.3.4经典进程同步问题2.3进程同步fpV(apple）放苹果…………P(empty)dpV(empty）取苹果…………P(apple)mpV(orang）放橘子…………P(empty)spV(empty）放苹果…………P(orange)Doyouhaveanyquestions?2、哲学家就餐问题2.3.4经典进程同步问题2.3进程同步该问题由dijkstra提出并解决目的：解决资源紧张问题2、哲学家就餐问题问题描述：2.3.4经典进程同步问题2.3进程同步1435212345thinkerThinkeat解决方案：将每支筷子都看作临界资源，设置互斥信号量。varchopstickarrayofsemaphore：=（1，1，1，1，1）；2.3.4经典进程同步问题2.3进程同步piV(chopstick[i])eatP(chopstick[i])V(chopstick[(i+1)mod5])P(chopstick[(i+1)mod5])thinkDoyouhaveanyquestions?解决方案中的僵局问题。方案一：使用AND型信号量2.3.4经典进程同步问题2.3进程同步pieatP(chopstick[i],chopstick[(i+1)mod5])V(chopstick[i],chopstick[(i+1)mod5])think方案二：限制同时申请就餐的哲学家的个数，不超过42.3.4经典进程同步问题2.3进程同步V(chopstick[i])eatP(chopstick[i])V(chopstick[(i+1)mod5])P(chopstick[(i+1)mod5])thinkvarchopstickarrayofsemaphore：=（1，1，1，1，1）；Varmutexofsemaphore：=4；V(mutex）P(mutex)2.3.4经典进程同步问题2.3进程同步方案三：让部分哲学家们争相同的第一只筷子。策略之一：奇数号哲学家顺时针申请，偶数号哲学家逆时针申请。piV(chopstick[i])eatP(chopstick[i])V(chopstick[(i+1)mod5])P(chopstick[(i+1)mod5])thinkIf（imod2==0)V(chopstick[i])eatP(chopstick[i])V(chopstick[(i+1)mod5])P(chopstick[(i+1)mod5])thinknoDoyouha