第二章 进程管理

12020/1/23操作系统第二章进程管理2.1进程的基本概念(PROCESS)2.2进程状态和进程控制2.3线程(THREAD)2.4进程的互斥和同步2.5进程间通信(IPC,INTER-PROCESSCOMMUNICATION)2.6死锁问题(DEADLOCK)2.7处理机调度22020/1/23操作系统2.4进程互斥和同步2.4.1互斥算法2.4.2信号量(semaphore)2.4.3经典进程同步问题2.4.4管程(monitor)2.4.5进程互斥和同步举例32020/1/23操作系统2.4.1互斥算法2.4.1.1临界资源2.4.1.2临界区的访问过程2.4.1.3同步机制应遵循的准则2.4.1.4进程互斥算法42020/1/23操作系统进程的交互关系：可以按照相互感知的程度来分类相互感知的程度交互关系一个进程对其他进程的影响潜在的控制问题相互不感知(完全不了解其它进程的存在)竞争(competition)一个进程的操作对其他进程的结果无影响互斥，死锁（可释放的资源），饥饿间接感知(双方都与第三方交互，如共享资源)通过共享进行协作一个进程的结果依赖于从其他进程获得的信息互斥，死锁（可释放的资源），饥饿，数据一致性直接感知(双方直接交互，如通信)通过通信进行协作一个进程的结果依赖于从其他进程获得的信息死锁，饥饿互斥，指多个进程不能同时使用同一个资源；死锁，指多个进程互不相让，都得不到足够的资源；饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）进程间的相互关系52020/1/23操作系统进程间的制约关系间接制约：进行竞争－－独占分配到的部分或全部共享资源“互斥”直接制约：进行协作－－等待来自其他进程的信息“同步”62020/1/23操作系统2.4.1.1临界资源进程间资源访问冲突共享变量的修改冲突操作顺序冲突硬件或软件（如外设、共享代码段、共享数据结构），多个进程在对其进行访问时（关键是进行写入或修改），必须互斥地进行－－有些共享资源可以同时访问，如只读数据多道程序环境－进程之间存在资源共享，进程的运行时间受影响72020/1/23操作系统共享变量的修改冲突程序段1程序段2程序段n共享变量82020/1/23操作系统getcopyputfstg有3个进程：get,copy和put，它们对4个存储区域f、s、t和g进行操作。操作顺序冲突92020/1/23操作系统。fstg结果初始状态3,4,...,m22(1,2)g,c,p4,5,...,m33(1,2,3)正确g,p,c4,5,...,m33(1,2,2)错误c,g,p4,5,...,m32(1,2,2)错误c,p,g4,5,...,m32(1,2,2)错误p,c,g4,5,...,m32(1,2,2)错误p,g,c4,5,...,m33(1,2,2)错误有6种可能操作顺序，只有一种结果正确102020/1/23操作系统2.4.1.2临界区临界区(criticalsection)：进程中访问临界资源的一段代码。进入区(entrysection)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志。退出区(exitsection)：用于将正在访问临界区标志清除。剩余区(remaindersection)：代码中的其余部分。entrysectionexitsectioncriticalsectionremaindersection临界区entrysectionexitsectioncriticalsectionremaindersection临界区112020/1/23操作系统2.4.1.3同步机制应遵循的准则空闲则入：其他进程均不处于临界区；忙则等待：已有进程处于其临界区；有限等待：等待进入临界区的进程不能死等；让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）目的：避免死锁和饥饿122020/1/23操作系统2.4.1.4互斥算法解决进程互斥的方法：基于进程间平等协商的互斥方法软件方法硬件方法由操作系统协调互斥问题的方法132020/1/23操作系统进程互斥的软件方法算法1：单标志while(turn!=i);criticalsectionturn=j;remaindersection设立一个公用整型变量turn：描述允许进入临界区的进程标识在进入区循环检查是否允许本进程进入：turn为i时，进程Pi可进入；在退出区修改允许进入进程标识：进程Pi退出时，改turn为进程Pj的标识j；有两个进程Pi,Pj，其中的Pi142020/1/23操作系统单标志算法的缺点强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区；152020/1/23操作系统算法2：双标志、先检查设立一个标志数组flag[]：描述进程是否在临界区，初值均为FALSE先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；while(flag[j]);aflag[i]=TRUE;bcriticalsectionflag[i]=FALSE;remaindersection162020/1/23操作系统双标志、先检查算法的特点优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。按下面序列执行时，会同时进入：PiaPjaPibPjb即在检查对方flag之后和切换自己flag之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能连续进行。172020/1/23操作系统算法3：双标志、后检查类似于算法2，与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。flag[i]=TRUE;bwhile(flag[j]);acriticalsectionflag[i]=FALSE;remaindersection182020/1/23操作系统双标志、后检查算法的缺点缺点：Pi和Pj可能都进入不了临界区。按下面序列执行时，会都进不了临界区：PiaPjaPibPjb“即在切换自己flag之后和检查对方flag之前有一段时间，结果都切换flag，都检查不通过192020/1/23操作系统算法4：先修改、后检查、后修改者等待turn=j;描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后：检查对方flag，如果不在临界区则自己进入－－空闲则入否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入－－先到先入，后到等待flag[i]=TRUE;turn=j;while(flag[j]&&turn==j);criticalsectionflag[i]=FALSE;remaindersectionPeterson’sAlgorithm结合算法1和算法3，是正确的算法202020/1/23操作系统2.4.1.5进程互斥的硬件方法完全利用软件方法，有很大局限性（如不适于多进程），现在已很少采用可以利用某些硬件指令－－其读写操作由一条指令完成，因而保证读操作与写操作不被打断212020/1/23操作系统Test-and-Set指令该指令读出标志后设置为TRUEbooleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示资源的两种状态：TRUE表示正被占用FALSE表示空闲222020/1/23操作系统whileTS(&lock);lock=FALSE;criticalsectionremaindersection利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；互斥算法（TS指令）232020/1/23操作系统Swap指令（或Exchange指令）交换两个字（字节）的内容voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}242020/1/23操作系统互斥算法（Swap指令）利用Swap实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量keykey=TRUE;do{SWAP(&lock,&key);}while(key);lock=FALSE;criticalsectionremaindersection252020/1/23操作系统硬件方法的特点硬件方法的优点适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点等待要耗费CPU时间，不能实现让权等待可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上可能死锁262020/1/23操作系统2.4.2信号量(semaphore)2.4.2.1信号量和P、V原语2.4.2.2信号量集前面的互斥算法都存在问题，它们是平等进程间的一种协商机制。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量代表可用资源实体的数量272020/1/23操作系统2.4.2.1信号量和P、V原语1965年，荷兰学者Dijkstra提出（P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识信号量只能通过初始化和两个标准的原语来访问－－作为OS核心代码执行，不受进程调度的打断初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量）－－若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数二进制信号量(binarysemaphore)：只允许信号量取0或1值282020/1/23操作系统1.P原语P(s){--s.count;//表示申请一个资源;if(s.count0)//表示没有空闲资源;{调用进程进入等待队列s.queue;阻塞调用进程;}}292020/1/23操作系统2.V原语V(s){++s.count;//表示释放一个资源；if(s.count=0)//表示有进程处于阻塞状态；{从等待队列s.queue中取出一个进程P;进程P进入就绪队列;}}V原语通常唤醒进程等待队列中的头一个进程302020/1/23操作系统信号量的使用信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数必须置一次且只能置一次初值初值不能为负数只能执行P、V操作必须成对使用P和V原语：遗漏P原语则不能保证互斥访问遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）P、V原语不能次序错误、重复或遗漏312020/1/23操作系统3.利用信号量实现互斥为临界资源设置一个互斥信号量mutex(MUTualExclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间V(mutex);criticalsectionremaindersectionP(mutex);322020/1/23操作系统用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)332020/1/23操作系统4.利用信号量来描述前趋关系前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为