第二章-进程和线程

第2章进程管理本章内容提要 什么是进程 进程的状态和组成 进程间的同步与互斥 进程通信 对进程的管理 线程和管程概念 死锁概念2.1进程概念2.1.1程序顺序执行的特征■顺序程序设计■顺序程序活动特点●顺序性●封闭性●可再现性2.1.2程序并发执行及其特征■程序并发执行概念---在操作系统中，是指一个时间段中有几个程序都处在已启动运行到运行完毕之间。▲非多道技术下作业执行过程▲多道技术下作业执行过程●作业吞吐量是指在给定时间间隔内所完成作业的数量■程序并发执行的特征①失去封闭性②程序与计算不再一一对应③并发程序在执行期间相互制约2.1.3进程概念的引入和定义■引入进程概念多道程序并发执行所引发的一系列新情况，必须引入新的概念来描述程序动态执行过程的性质。■进程概念定义 定义：程序在并发环境中的执行过程●进程最根本的属性是动态性和并发性“进程”是操作系统的最基本、最重要的概念之一。这是对正在运行程序的一个抽象。但还没有形成统一的定义。★生活中事例——按菜谱做菜●进程和程序的区别动态性并发性非对应性异步性■进程特征（1）动态性（2）并发性（3）调度性（4）异步性（5）结构性2.2进程状态描述及组织方式2.2.1进程的状态及其转换■进程的状态三种基本状态●运行状态（Running）●就绪状态（Ready）●阻塞状态（Blocked）进程的5种状态及其转换■进程状态的转换（1）就绪→运行（2）运行→阻塞（3）阻塞→就绪（4）运行→就绪2.2.2进程的组成1．进程映像进程映像通常就由程序、数据集合、栈和PCB等4部分组成进程映像模型进程描述2．进程控制块的组成 进程控制块（PCB）也称进程描述块（ProcessDescriptor），它是进程组成中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，是系统对进程施行识别和控制的依据。★进程控制块一般应包括如下内容：进程名特征信息进程状态信息调度优先权通信信息现场保护区资源需求、分配和控制方面的信息进程实体信息族系关系其它信息3．进程控制块的作用 每个进程有惟一的进程控制块 操作系统根据PCB对进程实施控制和管理 进程的动态、并发等特征是利用PCB现出来的 PCB是进程存在的唯一标识2.2.3进程组织方式1．线性方式PCB线性队列示意图进程队列2．链接方式PCB链接队列示意图PCB索引结构示意图3．索引方式进程队列2.3进程管理和有关命令2.3.1进程图和进程管理■进程图（ProcessGraph）是描述进程族系关系的有向树进程创建的层次关系■进程创建引发创建进程的事件：▲调度新作业▲用户登录▲操作系统提供特定服务▲派生新进程●创建新进程时要执行创建进程的系统调用（如UNIX/Linux系统中的fork）●其主要操作过程有如下四步：（1）申请一个空闲的PCB（2）为新进程分配资源（3）将新进程的PCB初始化（4）将新进程加到就绪队列中#include<unistd.h>#include<sys/types.h>#include<stdio.h>intmain(intargc,char*argv[]){ intpid;pid=fork();/*forkanotherprocess*/if(pid<0){/*erroroccurred*/fprintf(stderr,"ForkFailed");exit(-1);}elseif(pid==0){/*childprocess*/execlp("/bin/ls","ls",NULL);}else{/*parentprocess*/wait(NULL);/*parentwillwaitforthechildtocomplete*/printf("ChildComplete");exit(0);}}■进程终止●导致进程终止的三种情况：正常终止异常终止外部干扰●终止进程的主要操作过程如下： 找到指定进程的PCB，终止该进程的运行 回收该进程所占用的全部资源 终止其所有子孙进程，回收它们所占用的全部资源。 将被终止进程的PCB从原来队列中摘走■进程阻塞进程阻塞的过程如下： 立即停止当前进程的执行 现行进程的CPU现场保存 现行状态由“运行”改为“阻塞” 转到进程调度程序■进程唤醒唤醒原语执行过程如下： 把阻塞进程从相应的阻塞队列中摘下 将现行状态改为就绪状态，然后把该进程插入就绪队列中 如果被唤醒的进程比当前运行进程的优先级更高，则设置重新调度标志■进程映像的更换改变进程映像的工作很复杂，其主要过程是： 释放子进程原来的程序和数据所占用的内存空间； 从磁盘上找出子进程所要执行的程序和数据（通常以可执行文件的形式存放）； 分配内存空间，装入新的程序和数据； 为子进程建立初始的运行环境——主要是对各个寄存器初始化，返回到用户态，运行该进程的程序。2.3.2Linux进程管理■Linux进程状态Linux进程状态的变化■进程的模式和类型用户进程的两种运行模式进程划分为两大类：一类是系统进程，只运行在内核模式，执行操作系统代码；另一类是用户进程。■Linux进程结构●task_struct结构Linux系统中的每个进程都有一个名为task_struct的数据结构，它相当于“进程控制块”。task_struct结构包含下列信息：进程状态调度信息标识符内部进程通信链接信息时间和计时器文件系统虚拟内存处理器信息●进程系统堆栈2.3.3有关进程操作的命令1．ps命令查看进程状态ps命令的一般是：ps[选项]$psPIDTTYTIMECMD1788pts/100:00:00bashpts/100:00:00ps2．kill命令终止一个进程的运行kill命令的一般格式是： kill[-s信号|-p][-a]进程号… kill-l[信号]$kill16513．sleep命令使进程暂停执行一段时间。一般使用格式是：sleep时间值$sleep100;who|grep'mengqc'2.3.4有关进程管理的系统调用■系统调用的使用方式在UNIX/Linux系统中，系统调用和库函数都是以C函数的形式提供给用户的，它有类型、名称、参数，并且要标明相应的文件包含。open系统调用可以打开一个指定文件，其函数原型说明如下：#include<sys/types.h>#include<sys/stat.h>#include<fcntl.h>intopen(constchar*path,intoflags);例如：intfd;…fd=open("/home/mengqc/myfile1",O_RDWR);…■有关系统调用的格式和功能常用的有关进程管理的系统调用有：fork，exec，wait，exit，getpid，sleep，nice等■应用示例/*proc1.c演示有关进程操作*/#include<unistd.h>#include<sys/types.h>#include<stdio.h>#include<errno.h>intmain(intargc,char**argv){pid_tpid,old_ppid,new_ppid;pid_tchild,parent;parent=getpid(); /*获得本进程的PID*/if((child=fork())<0){fprintf(stderr,"%s:forkofchildfailed:%s\n",argv[0],strerror(errno));exit(1);}elseif(child==0){ /*此时是子进程被调度运行*/old_ppid=getppid();sleep(2);new_ppid=getppid();}else{sleep(1);exit(0); /*父进程退出*/}/*下面仅子进程运行*/printf("Originalparent:%d\n",parent);printf("Child:%d\n",getpid());printf("Child'soldppid:%d\n",old_ppid);printf("Child'snewppid:%d\n",new_ppid);exit(0);}程序运行的结果如下：$./proc1Originalparent:2009Child:2010Child'soldppid:2009Child'snewppid:12.4线程概念2.4.1什么是线程■线程概念现代操作系统中，进程只作为资源拥有者，而调度和运行的属性赋予新的实体——线程。★线程（Thread）是进程中执行运算的最小单位，亦即执行处理机调度的基本单位。▲引入线程概念的理由主要有：①使并行实体获得共享同一地址空间和所有可用数据的能力。②易于切换，代价低。③可以改善系统的性能。■线程的组成每个线程有一个thread结构，即线程控制块，用于保存自己私有的信息，主要由以下4个基本部分组成： 一个唯一的线程标识符 一组寄存器 两个栈指针 一个私有存储区thread结构示意图线程的组成 线程必须在某个进程内执行 一个进程可以包含一个线程或多个线程单线程和多线程的进程模型■线程的状态 运行状态 就绪状态 阻塞状态 终止状态■线程和进程的关系①一个进程可以有多个线程，但至少要有一个线程；而一个线程只能在一个进程的地址空间内活动。②资源分配给进程，同一进程的所有线程共享该进程的所有资源。③处理机分配给线程，即真正在处理机上运行的是线程。④线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。2.4.2线程的实现方式■用户级线程在用户空间实现优点：切换速度快；调度算法可专用；可运行在任何操作系统上缺点：阻塞问题；多处理器利用问题在用户空间和核心空间实现线程■核心级线程优点：真正实现并行操作克服阻塞问题本身也可以是多线程的缺点：控制转移开销大调度算法由核心确定，应用进程无法影响线程的切换▲组合方式2.5进程间的同步与互斥进程间的相互关系主要分为如下三种形式：①互斥——竞争同一资源而发生相互制约②同步——协同完成一项任务③通信——交换信息2.5.1进程间的关系1．同步▲日常事例：接力跑工业生产流水作业★SPOOLing系统同步进程通过共享资源来协调活动，在执行时间的次序上有一定约束。虽然彼此不直接知道对方的名字，但知道对方的存在和作用。在协调动作的情况下，多个进程可以共同完成一项任务。2．互斥▲日常事例★进程争用某些资源 在逻辑上这两个进程本来完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。 它们的运行不具有时间次序的特征▲互斥示例假定进程Pa负责为用户作业分配打印机，进程Pb负责释放打印机。系统中设立一个打印机分配表，由各个进程共用。●Pa进程分配打印机的过程是：①逐项检查分配标志，找出标志为0的打印机号码；②把该打印机的分配标志置1；③把用户名和设备名填入分配表中相应的位置。★Pb进程释放打印机的过程是：①逐项检查分配表的各项信息，找出标志为1且用户名和设备名与被释放的名字相同的打印机编号；②该打印机的标志清0；③清除该打印机的用户名和设备名。打印机分配表（初始情况）打印机分配表（出错情况）可见，Pa和Pb对分配表的使用必须互斥执行2.5.2竞争条件和临界区■竞争条件（RaceCondition）两个或多个进程同时访问和操纵相同的数据时，最后的执行结果取决于进程运行的精确时序。■临界资源（CriticalResource）一次仅允许一个进程使用的共享资源■临界区（CriticalSection），简称CS区在每个进程中访问临界资源的那段程序▲典型进程进入临界区的一般结构■临界区进入准则①独占临界区②前进速度不确定③区内进程不受干扰④有期等待进程A和进程B互斥使用临界区的过程2.5.3进程同步机制实现互斥方式⑴利用硬件解决进程互斥问题▲禁止中断进入临界区之后立即关闭所有的中断▲专用机器指令TSL（TestandSetLock，即测试并上锁）的指令：TSLRX，LOCK汇编代码示例enter_region:TSLREGISTER,LOCKCMPREGISTER,#0JNEenter_regionRETleave_region:MOVELOCK,#0RET⑵原语操作 原语（primitive）是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomicaction），即一个操作中的所有动作要么全做，要么全不做。 执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。⑶利用软件方法解决进程互斥问题▲可为每类临界区设置一把锁，该锁有打开和关闭两种状态。▲进程执行临界区程序的操作按下列步骤进行：关锁执行临界区程序开锁▲软件锁实现 关锁原语lock(W):while(W==1);W=1; 开锁原语unlock(W):w=0;进程A……lock(W);打印信息S;}CS区unlock(W);……进程B……lock(W);打印信息S;}CS区unlock(W);……用锁实现进程互斥设系统中有一台打印机，有两个进程A和B都要使用它，以变量W表示锁，预先把它的值置为0。2．信号量及P、V操作原语 结构型信号量又称计数信号量，简称信号量 一般是由两个成员组成的数据结构。其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。typedefstruct{intvalue;structPCB*list;}semaphore;结构型信号量●信号量的值与相应资源的使用情况有关●信号量的一般结构及PCB队列对信号量的操作有如下严格限制： 信号量可以赋初值，且初值为非负数。 在使用过程中，信号量的值可以修改，但只能由P和V操作来访问，不允许通过其他方式来查看或操纵信号量。 设信号量为S，对S的P操作记为P(S)，对S的V操作记为V(S)。结构型信号量●P(S):顺序执行下述两个动作：　　①信号量的值减1，即S=S-1；　　②如果S≥0，则该进程继续执行；　　　如果S＜0，则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止）。●V(S):顺序执行下述两个动作：　　①S值加1，即S=S+1；　　②如果S＞0，则该进程继续运行；　　如果S≤0，则释放信号量队列上的第一个PCB（即信号量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续运行。★Ｐ、Ｖ操作都应作为一个整体实施，不允许分割或相互穿插执行。2.5.4信号量的一般应用1.用信号量实现进程互斥打印机分配表的互斥使用Pa:Pb:……P(mutex)P(mutex)分配打印机释放打印机（读写分配表）（读写分配表）V(mutex)V(mutex)……用信号量实现进程互斥利用信号量实现互斥的一般模型是：进程P1进程P2…进程Pn………P(mutex);P(mutex);P(mutex);临界区临界区临界区V(mutex);V(mutex);V(mutex);………用信号量实现进程互斥●注意点：①在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区；后做V，退出临界区。②互斥信号量mutex的初值一般为1。2．用信号量实现进程简单同步对缓冲区的同步使用问题简单供者和用者对缓冲区的使用关系 供者和用者间要交换两个消息：缓冲区空缓冲区满 设置两个信号量S1表示缓冲区是否空（0表示不空，1表示空）。S2表示缓冲区是否满（0表示不满，1表示满）。规定S1和S2的初值分别为1和0供者进程用者进程L1:P(S1)L2:…启动读卡机P(S2);…从缓冲区取出信息收到输入结束中断V(S1);V(S2);加工并且存盘gotoL1;gotoL2;用P和V操作实现同步时应注意如下三点：①进程间的制约关系，确定信号量种类。②信号量的初值与相应资源的数量有关，也与P,V操作在程序代码中出现的位置有关。③同一信号量的P,V操作要“成对”出现，但是，它们分别出现在不同的进程代码中。3.生产者—消费者问题 生产者:能产生并释放资源的进程 消费者:单纯使用（消耗）资源的进程 问题表述一组生产者进程和一组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等统称为产品）送入缓冲区，消费者进程从中取出产品。假定缓冲区共有N个，不妨把它们设想成一个环形缓冲池。生产者-消费者问题环形缓冲池它们应满足如下同步条件：①任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量（N）。②所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。生产者-消费者问题●设缓冲区的编号为0～N-1，in和out分别是生产者进程和消费者进程使用的指针，指向下面可用的缓冲区，初值都是0。●设置三个信号量： full：表示放有产品的缓冲区数，其初值为0。 empty：表示可供使用的缓冲区数，其初值为N。 mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。生产者-消费者问题生产者进程Producer：消费者进程Consumer：while(TRUE){ while(TRUE){P(empty); P(full);P(mutex); P(mutex);产品送往buffer(in); 从buffer(out)中取出产品；in=(in+1)modN;out=(out+1)modN;/*以N为模*//*以N为模*/V(mutex); V(mutex);V(full); V(empty);} }●应注意：①在每个程序中必须先做P(mutex)，后做V(mutex)，二者要成对出现。②对同步信号量full和empty的P,V操作同样必须成对出现，但它们分别位于不同的程序中。③无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。2.6进程通信★进程通信——进程间的信息交换 低级进程通信——互斥和同步机构 高级进程通信▲共享存储器方式：在内存中分配一片空间作为共享存储区▲管道文件方式：写者向管道文件中写入数据；读者从该文件中读出数据▲消息传递方式：以消息（Message）为单位在进程间进行数据交换●直接通信方式●间接通信方式■消息缓冲通信▲消息通信方法的设计思想▲接收消息进程的PCB和它的消息缓冲链的关系name：发送消息的进程名或标志号size：消息长度text：消息正文next：下个缓冲区的地址mutex：消息队列操作互斥信号灯Sm：表示接收消息计数和同步的信号灯Pm：指向该进程的消息队列中第一个缓冲区的指针两个进程进行消息传送的过程■信箱通信▲信箱是一种数据结构，在逻辑上可分为两个部分：信箱头——包括信箱名字、信箱属性（公用、私用或者共享）、信箱格状态等；信箱体——用来存放消息的多个信箱格。▲信箱可以动态创建和撤消▲发送和接收消息的原语形式send(mailbox,message)receive(mailbox,message)mailbox为信箱，message是要发送的消息▲信箱可分为三类：公用信箱共享信箱私有信箱2.7管程■管程：一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据。■由管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句四部分组成。管程的结构管程管程具有以下三个特性：①管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问。②进程要想进入管程，必须调用管程内的某个过程。③一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。管程▲实现互斥是由编译程序完成▲为解决同步问题，引入两个条件变量x和y：conditionx,y; 操作原语wait(x)：挂起等待条件x的调用进程，释放相应的管程，以便供其他进程使用。 操作原语signal(x)：恢复执行先前因在条件x上执行wait而挂起的那个进程。 管程的职责与信号量的职责不同。带条件变量的管程结构2.8经典进程同步问题1．读者-写者问题读者-写者问题也是一个著名的进程互斥访问有限资源的同步问题。例如，一个航班预订系统有一个大型数据库，很多竞争进程要对它进行读、写。允许多个进程同时读该数据库，但是在任何时候如果有一个进程写（即修改）数据库，那么就不允许其他进程访问它——既不允许写，也不允许读。读者-写者问题●信号量设置：▲读互斥信号量rmutex初值为1▲写互斥信号量wmutex初值为1rmutex：读者互斥地访问readcountwmutex：保证一个写者与其他读者/写者互斥地访问共享资源★读计数器readcount，整型变量，初值为0。读者-写者问题读者Readerswhile(TRUE){P(rmutex);readcount=readcount+1;if(readcount==1)P(wmutex);V(rmutex);执行读操作P(rmutex);readcount=readcount-1;if(readcount==0)V(wmutex);V(rmutex);使用读取的数据}写者Writerswhile(TRUE){P(wmutex);执行写操作V(wmutex);}▲这个算法隐含读者的优先级高于写者2．哲学家进餐问题五位哲学家围坐在一张圆桌旁进餐，每人面前有一只碗，各碗之间分别有一根筷子。每位哲学家在用两根筷子夹面条吃饭前独自进行思考，感到饥饿时便试图占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能强行从邻座手中拿过筷子，而且必须用两根筷子进餐；餐毕，要把筷子放回原处并继续思考问题。哲学家进餐问题哲学家进餐问题的一种算法===========================================#defineN5#defineLEFT(i-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2typedefstruct{/*定义结构型信号量*/intvalue;structPCB*list;}semaphore;intstate[N];semaphoremutex=1;/*互斥进入临界区*/semaphores[N]; /*每位哲学家一个信号量*/哲学家进餐问题voidphilosopher(inti){while(TRUE){think(); /*哲学家在思考问题*/take_chopstick(i);/*拿到两根筷子或者等待*/eat(); /*进餐*/put_chopstick(i);/*把筷子放回原处*/}}voidtake_chopstick(inti){P(mutex);state[i]=HUNGRY;test(i);/*试图拿两根筷子*/V(mutex);P(s[i]);}哲学家进餐问题voidput_chopstick(inti){P(mutex);state[i]=THINKING;test(LEFT); /*查看左邻，现在能否进餐*/test(RIGHT); /*查看右邻，现在能否进餐*/V(mutex);}voidtest(inti){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;V(s[i]);}}===============================================打瞌睡的理发师3．打瞌睡的理发师问题理发店有一名理发师，一把理发椅和几把座椅，等待理发者可坐在上面。如果没有顾客到来，理发师就坐在理发椅上打盹。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在理发，该顾客就坐在椅子上排队；如果满座了，他就离开这个理发店，到别处去理发。打瞌睡的理发师问题理发师和每位顾客都分别是一个进程===============================#defineCHAIRS5typedefstruct{intvalue;structPCB*list;}semaphore;semaphorecustomers=0;semaphorebarbers=0;semaphoremutex=1;intwaiting=0;打瞌睡的理发师问题voidbarber(void){while(TRUE){P(customers);/*如果没有顾客，则理发师打瞌睡*/P(mutex);/*互斥进入临界区*/waiting--;V(barbers);/*一个理发师准备理发*/V(mutex);/*退出临界区*/cut_hair();/*理发（在临界区之外）*/}}打瞌睡的理发师问题voidcustomer(void){P(mutex); /*互斥进入临界区*/if(waiting﹤CHAIRS){waiting++;V(customers); /*若有必要，唤醒理发师*/V(mutex);/*退出临界区*/P(barbers); /*如果理发师正忙着，则顾客打瞌睡*/get_haircut();}elseV(mutex); /*店里人满了，不等了*/}2.9死锁2.9.1死锁概述若干进程竞争有限资源、又加上推进顺序不当，从而构成无限期循环等待的局面。1.死锁示例▲硬件资源死锁▲软件资源死锁★可抢占资源当该资源被某进程拥有后，其它进程仍可以把它抢占过去为己所用，并且不会产生任何不良影响。例如，内存就是可抢占资源。★不可抢占资源该资源一旦被某进程占有，则其它进程不能强行抢占，必须由拥有者自动释放，否则会引起相关计算的失效。如光盘刻录机。◎死锁和不可抢占资源有关2．死锁定义 死锁是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。▲资源死锁 计算机系统产生死锁的根本原因就是资源有限且操作不当 死锁的危害系统瘫痪资源浪费……3.产生死锁的原因▲一般进程使用资源的顺序：申请使用释放▲进程推进顺序对引发死锁的影响有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。进程A进程B…………申请并占用R申请并占用S申请并占用S申请并占用R…………释放R释放S释放S释放R…………什么是死锁进程推进顺序对引发死锁的影响4.产生死锁的必要条件●产生死锁的4个必要条件1．互斥条件2．占有且等待条件3．不可抢占条件4．循环等待条件▲只要有一个必要条件不满足，则死锁就可以排除。5．资源分配图⑴资源分配图的构成▲由结对组成：G=(V,E)V是顶点的集合，E是边的集合。顶点集合可分为两部分：P={p1,p2,…,pn}由系统中所有活动进程组成R={r1,r2,…,rm}由系统中全部资源类型组成▲有向边pi→rj称为申请边有向边rj→pi称为赋给边▲在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。★资源分配图示例（1）集合P,R和E如下：P={p1,p2,p3}R={r1,r2,r3,r4}E={p1→r1,p2→r3,r1→p2,r2→p2,r2→p1,r3→p3}（2）资源数量分别为1，2，1，3（3）进程状态该图不含环路，没有死锁资源分配图示例⑵环路与死锁▲如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。环路与死锁有死锁的资源分配图有环路但无死锁的资源分配图▲如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。●资源分配图中存在环路是死锁产生的必要条件，但不是充分条件。6.对待死锁的策略☆忽略死锁问题☆死锁预防（静态策略）☆死锁避免（动态策略）☆死锁的检测与恢复2.9.2死锁的预防1.破坏互斥条件2.破坏占有且等待条件●预分资源策略——静态分配●“空手”申请资源策略——不占有资源时才可以申请资源▲这两种方法存在以下4个主要缺点◎不可预测◎利用率低◎降低并发性◎“饥饿”现象破坏非抢占条件▲处于等待状态进程当前所占有的全部资源可被抢占4．破坏环路等待条件①资源有序分配策略●资源编号设R={r1,r2,…,rm}，表示一组资源定义一对一的函数F：R→N，N是一组自然数。如：F（磁带机）=1，F（磁盘机）=5，F（打印机）=12●依序分配约定：所有进程对资源的申请严格按照序号递增的次序进行。②先弃大，再取小一个进程申请资源rj，它应释放所有满足F(ri)≥F(rj)关系的资源ri▲这两种办法都是可行的，都可排除环路等待条件优点：资源利用率和系统吞吐量都有很大提高缺点：▼资源请求受限，合理编号困难，增加系统开销。▼暂不使用的资源也需提前申请，增加资源占用时间。2.9.3死锁的避免●排除死锁的动态策略。关键是确定资源分配的安全性1.安全状态 在当前分配状态下，进程的安全序列{P1,P2,…,Pn}是：若对于每一个进程Pi（1≤i≤n），它需要的附加资源可被系统中当前可用资源与所有进程Pj（j＜i）当前占有资源之和所满足，则{P1,P2,…,Pn}为一个安全序列。这时系统处于安全状态。●存在安全序列时一定不会有死锁发生死锁是不安全状态中的特例安全状态 安全状态示意设系统中共有10台磁带机，有三个进程p1,p2和p3，分别拥有3台、2台和2台磁带机，而它们各自的最大需求分别是9台、4台和7台磁带机。此时，系统已分配了7台磁带机，还有3台空闲。下表给出三个进程在不同时刻占有资源及向前推进的情况。 时刻 已占有台数 最大需求台数 当前可用台数 进程P1 进程P2 进程P3 进程P1 进程P2 进程P3 T0 3 2 2 9 4 7 3 T1 3 4 2 9 4 7 1 T2 3 0 2 9 — 7 5 T3 3 0 7 9 — 7 0 T4 3 0 0 9 — — 7 T5 9 0 0 — — — 1 T6 0 0 0 — — — 10不安全状态示意 若不按照安全序列分配资源，则系统可能会由安全状态转换为不安全状态 时刻 已占有台数 最大需求台数 当前可用台数 进程P1 进程P2 进程P3 进程P1 进程P2 进程P3 T0′ 3 2 2 9 4 7 3 T1′ 4 2 2 9 4 7 2 T2′ 4 4 2 9 4 7 0 T3′ 4 0 2 9 — 7 4死锁的避免①死锁状态是不安全状态。②如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。③如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。2.银行家算法“银行家算法”（Banker’sAlgorithm）——针对多体资源类 设计思想：当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。银行家算法数据结构令n表示系统中进程的数目，m表示资源分类数。①Available是一个长度为m的向量，它表示每类资源可用的数量。Available[j]=k，表示rj类资源可用的数量是k。②Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max[i,j]=k，表示进程pi至多可申请k个rj类资源单位。③Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation[i,j]=k，表示进程pi当前分到k个rj类资源。④Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Need[i,j]=k，表示进程pi尚需k个rj类资源才能完成其任务。▲记号：令X和Y表示长度为n的向量可以把矩阵Allocation和Need中的每一行当做一个向量，并分别写成Allocationi和Needi。Allocationi表示当前分给进程pi的资源。⑴资源分配算法 令Requesti表示进程pi的申请向量。Requesti[j]=k，表示进程pi需要申请k个rj类资源。当进程pi申请资源时，就执行下列动作：①若Requesti＞Needi，表示出错，②如果Requesti＞Available，则pi等待。③假设系统把申请的资源分给进程pi，则应对有关数据结构进行修改：Available：=Available–RequestiAllocationi：=Allocationi+RequestiNeedi：=Needi–Requesti④系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程pi的此次申请；否则，若新状态是不安全的，则pi等待，对所申请资源暂不予分配，并且把资源分配状态恢复成③之前的情况。⑵安全性算法①令Work和Finish分别表示长度为m和n的向量，最初，置Work：=Available，Finish[i]：=false，i=1,2,…,n。②搜寻满足下列条件的i值：Finish[i]=false，且Needi≤Work。若没有找到，则转向④。③修改数据值：Work：=Work+Allocationi（pi释放所占的全部资源）Finish[i]=true转向②。④若Finish[i]=true对所有i都成立（任一进程都可能是pi），则系统处于安全状态；否则，系统处于不安全状态。⑶算法应用示例假定系统中有4个进程{A,B,C,D}和三类资源R1,R2和R3，各自的数量分别为9,3和6个单位。T0时刻资源分配表（安全）资源情况 进程 Allocation Max Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 A 1 0 0 3 2 2 2 2 2 1 1 2 B 5 1 1 6 1 3 1 0 2 C 2 1 1 3 1 4 1 0 3 D 0 0 2 4 2 2 4 2 0●T0时刻是安全的存在一个安全序列{B,A,C,D}进程T0时刻的安全序列●进程A请求资源进程A发出请求Request（1,0,1）,系统按银行家算法进行检查系统进入不安全的状态不能为进程A分配所申请的资源为进程A分配资源后的有关数据银行家算法 优点：限制条件少资源利用程度提高 缺点：①难以保证进程数固定不变②未考虑实时进程快速响应③增加了系统开销2.9.4死锁的检测和恢复■死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来。1.对单体资源类的死锁检测■等待图——资源分配图的变形从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的资源分配图和对应的等待图2．对多体资源类的死锁检测■采用若干随时间变化的数据结构，与银行家算法相似①Available是一个长度为m的向量②Allocation是一个n×m的矩阵③Request是一个n×m的矩阵，Request[i,j]=k，表示进程pi正申请k个rj类资源仍把矩阵Allocation和Request的行作为向量对待，并分别表示为Allocationi和Requesti对多体资源类的死锁检测■检测算法简单地调查尚待完成的各个进程所有可能的分配序列①令Work和Finish分别表示长度为m和n的向量，初始化Work：=Available；对于i=1,2,…,n如果Allocationi≠0，则Finish[i]：=false；否则Finish[i]：=true。②寻找一个下标i，它应满足条件：Finish[i]=false且Requesti≤Work若找不到这样的i，则转到④。③修改数据值：Work：=Work+AllocationiFinish[i]=true转向②。④若存在某些i（1≤i≤n），Finish[i]=false，则系统处于死锁状态。此外，若Finish[i]=false，则进程pi处于死锁环中。■何时调用检测算法取决于两个因素：①死锁出现的频繁程度；②有多少个进程受到死锁的影响。3．从死锁中恢复⑴通过抢占资源实现恢复临时性地把资源从当前占有它的进程那里拿过来，分给另外某些进程，直至死锁环路被打破。⑵通过回退执行实现恢复 由系统管理员做出安排，定期对系统中各个进程进行检查，并将检查点的有关信息（如进程状态、资源状态等）写入文件。 当检测到死锁时，就让某个占有必要资源的进程回退到它取得另外某个资源之前的一个检查点。回退过程所释放的资源分配给一个死锁进程，然后重新启动运行。 系统中应保存一系列检查点的文件。 要确定这个进程后退多远。 还有一种“全体”回退方式⑶通过杀掉进程实现恢复 终止所有的死锁进程。 一次终止一个进程，直至消除死锁环路。 如何确定哪个进程将被终止，一般要考虑以下6种因素：①进程的优先级。②进程已计算了多长时间，该进程在完成预定任务之前还要计算多长时间。③该进程使用了多少和什么类型的资源（例如，这些资源可简单地抢占吗？）。④为完成任务，它还需要多少资源？⑤有多少个进程被终止？⑥这个进程是交互式进程，还是批处理进程？2.9.5活锁和饥饿活锁如果进程A先运行并且得到资源R，接着进程B运行并得到资源S，……好像发生死锁了，但是它们都没有被阻塞，都可以活动。这种现象就是活锁（Livelock）。2.饥饿 在某些策略下，系统会出现这样一种情况：在可以预计的时间内，某个或某些进程永远得不到完成工作的机会，因为它们所需的资源总是被别的进程占有或抢占。这种状况称做“饥饿”或者“饿死”（Starvation）。 例如，考虑打印机的分配问题。 饥饿不同于死锁Bye!下一章(NEXT)：第3章-处理机调度==