《进程和线程》PPT课件.ppt

《《进程和线程》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《进程和线程》PPT课件.ppt（119页珍藏版）》请在三一办公上搜索。

1、第2章 进程管理,本章内容提要,什么是进程进程的状态和组成进程间的同步与互斥进程通信对进程的管理线程和管程概念死锁概念,2.1 进程概念,2.1.1 程序顺序执行的特征 顺序程序设计,顺序程序活动特点 顺序性 封闭性 可再现性,程序并发执行及其特征,程序并发执行概念 非多道技术下作业执行过程,多道技术下作业执行过程,作业吞吐量是指在给定时间间隔内所完成作业的数量,程序并发执行的特征 失去封闭性 程序与计算不再一一对应 并发程序在执行期间相互制约,2.1.3 进程概念的引入和定义,引入进程概念 多道程序并发执行所引发的一系列新情况，必须引入新的概念来描述程序动态执行过程的性质。进程概念定义 定义

2、：程序在并发环境中的执行过程 进程最根本的属性是动态性和并发性“进程”是操作系统的最基本、最重要的概念之一。这是对正在运行程序的一个抽象。但还没有形成统一的定义。,生活中事例按菜谱做菜进程和程序的区别 动态性 并发性 非对应性 异步性,进程特征（1）动态性（2）并发性（3）调度性（4）异步性（5）结构性,2.2 进程状态描述及组织方式,2.2.1 进程的状态及其转换进程的状态 三种基本状态 运行状态（Running）就绪状态（Ready）阻塞状态（Blocked）,进程的5种状态及其转换,进程状态的转换（1）就绪运行（2）运行阻塞（3）阻塞就绪（4）运行就绪,2.2.2 进程的组成,1进程映像

3、 进程映像通常就由程序、数据集合、栈和PCB等4部分组成,进程映像模型,进程描述,2进程控制块的组成进程控制块（PCB）也称进程描述块（Process Descriptor），它是进程组成中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，是系统对进程施行识别和控制的依据。进程控制块一般应包括如下内容：进程名 特征信息 进程状态信息 调度优先权 通信信息 现场保护区 资源需求、分配和控制方面的信息 进程实体信息 族系关系 其它信息,3进程控制块的作用每个进程有惟一的进程控制块操作系统根据PCB对进程实施控制和管理进程的动态、并发等特征是利用PCB表现出来的PCB是进程存

4、在的唯一标识,2.2.3 进程组织方式,1线性方式,PCB线性队列示意图,进程队列,2链接方式,PCB链接队列示意图,PCB索引结构示意图,3索引方式,进程队列,2.3 进程管理和有关命令,2.3.1 进程图和进程管理进程图（Process Graph）是描述进程族系关系的有向树,进程创建的层次关系,进程创建 引发创建进程的事件：调度新作业 用户登录 操作系统提供特定服务 派生新进程创建新进程时要执行创建进程的系统调用（如UNIX/Linux系统中的fork）其主要操作过程有如下四步：（1）申请一个空闲的PCB（2）为新进程分配资源（3）将新进程的PCB初始化（4）将新进程加到就绪队列中,#i

5、nclude#include#include int main(int argc,char*argv)int pid;pid=fork();/*fork another process*/if(pid 0)/*error occurred*/fprintf(stderr,Fork Failed);exit(-1);else if(pid=0)/*child process*/execlp(/bin/ls,ls,NULL);else/*parent process*/wait(NULL);/*parent will wait for the child to complete*/printf(C

6、hild Complete);exit(0);,进程终止 导致进程终止的三种情况：正常终止 异常终止 外部干扰 终止进程的主要操作过程如下：找到指定进程的PCB，终止该进程的运行回收该进程所占用的全部资源终止其所有子孙进程，回收它们所占用的全部资源。将被终止进程的PCB从原来队列中摘走,进程阻塞进程阻塞的过程如下：立即停止当前进程的执行现行进程的CPU现场保存现行状态由“运行”改为“阻塞”转到进程调度程序,进程唤醒唤醒原语执行过程如下：把阻塞进程从相应的阻塞队列中摘下将现行状态改为就绪状态，然后把该进程插入就绪队列中如果被唤醒的进程比当前运行进程的优先级更高，则设置重新调度标志,进程映像的更换

7、 改变进程映像的工作很复杂，其主要过程是：释放子进程原来的程序和数据所占用的内存空间；从磁盘上找出子进程所要执行的程序和数据（通常以可执行文件的形式存放）；分配内存空间，装入新的程序和数据；为子进程建立初始的运行环境主要是对各个寄存器初始化，返回到用户态，运行该进程的程序。,2.3.2 Linux进程管理,Linux进程状态,Linux进程状态的变化,进程的模式和类型,用户进程的两种运行模式,进程划分为两大类：一类是系统进程，只运行在内核模式，执行操作系统代码；另一类是用户进程。,Linux进程结构 task_struct结构 Linux系统中的每个进程都有一个名为task_struct的数据

8、结构，它相当于“进程控制块”。task_struct结构包含下列信息：进程状态 调度信息 标识符 内部进程通信 链接信息 时间和计时器 文件系统 虚拟内存 处理器信息 进程系统堆栈,2.3.3 有关进程操作的命令,1ps命令 查看进程状态 ps命令的一般格式是：ps 选项$ps PID TTY TIME CMD1788 pts/1 00:00:00 bashpts/1 00:00:00 ps2 kill命令 终止一个进程的运行 kill命令的一般格式是：kill-s 信号|-p-a 进程号kill-l 信号$kill 1651,3sleep命令 使进程暂停执行一段时间。一般使用格式是：slee

9、p 时间值$sleep 100;who|grep mengqc,2.3.4 有关进程管理的系统调用,系统调用的使用方式 在UNIX/Linux系统中，系统调用和库函数都是以C函数的形式提供给用户的，它有类型、名称、参数，并且要标明相应的文件包含。open系统调用可以打开一个指定文件，其函数原型说明如下：#include#include#include int open(const char*path,int oflags);例如：int fd;fd=open(/home/mengqc/myfile1,O_RDWR);,有关系统调用的格式和功能 常用的有关进程管理的系统调用有：fork，exec

10、，wait，exit，getpid，sleep，nice等应用示例/*proc1.c演示有关进程操作*/#include#include#include#include int main(int argc,char*argv)pid_t pid,old_ppid,new_ppid;pid_t child,parent;parent=getpid();/*获得本进程的PID*/if(child=fork()0)fprintf(stderr,%s:fork of child failed:%sn,argv0,strerror(errno);exit(1);else if(child=0)/*此时是

11、子进程被调度运行*/old_ppid=getppid();sleep(2);new_ppid=getppid();else sleep(1);exit(0);/*父进程退出*/*下面仅子进程运行*/printf(Original parent:%dn,parent);printf(Child:%dn,getpid();printf(Childs old ppid:%dn,old_ppid);printf(Childs new ppid:%dn,new_ppid);exit(0);程序运行的结果如下：$./proc1Original parent:2009Child:2010Childs old

12、 ppid:2009Childs new ppid:1,2.4 线程概念,2.4.1 什么是线程线程概念 现代操作系统中，进程只作为资源拥有者，而调度和运行的属性赋予新的实体线程。线程（Thread）是进程中执行运算的最小单位，亦即执行处理机调度的基本单位。引入线程概念的理由主要有：使并行实体获得共享同一地址空间和所有可用数据的能力。易于切换，代价低。可以改善系统的性能。,线程的组成每个线程有一个thread结构，即线程控制块，用于保存自己私有的信息，主要由以下4个基本部分组成：一个唯一的线程标识符 一组寄存器 两个栈指针 一个私有存储区,thread结构示意图,线程的组成,线程必须在某个进程

13、内执行一个进程可以包含一个线程或多个线程,单线程和多线程的进程模型,线程的状态运行状态就绪状态 阻塞状态终止状态,线程和进程的关系 一个进程可以有多个线程，但至少要有一个线程；而一个线程只能在一个进程的地址空间内活动。资源分配给进程，同一进程的所有线程共享该进程的所有资源。处理机分配给线程，即真正在处理机上运行的是线程。线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。,2.4.2 线程的实现方式,用户级线程 在用户空间实现 优点：切换速度快；调度算法可专用；可运行在任何操作系统上 缺点：阻塞问题；多处理器利用问题,在用户空间和核心空间实现线程,核心级线程 优点：真正

14、实现并行操作 克服阻塞问题 本身也可以是多线程的 缺点：控制转移开销大 调度算法由核心确定，应用进程无法影响线程的切换组合方式,2.5 进程间的同步与互斥,进程间的相互关系主要分为如下三种形式：互斥竞争同一资源而发生相互制约 同步协同完成一项任务 通信交换信息,进程间的关系,1同步 日常事例：接力跑 工业生产流水作业 SPOOLing系统 同步进程通过共享资源来协调活动，在执行时间的次序上有一定约束。虽然彼此不直接知道对方的名字，但知道对方的存在和作用。在协调动作的情况下，多个进程可以共同完成一项任务。,2互斥 日常事例 进程争用某些资源 在逻辑上这两个进程本来完全独立，毫无关系，只是由于竞争

15、同一个物理资源而相互制约。它们的运行不具有时间次序的特征,互斥示例 假定进程Pa负责为用户作业分配打印机，进程Pb负责释放打印机。系统中设立一个打印机分配表，由各个进程共用。Pa进程分配打印机的过程是：逐项检查分配标志，找出标志为0的打印机号码；把该打印机的分配标志置1；把用户名和设备名填入分配表中相应的位置。Pb进程释放打印机的过程是：逐项检查分配表的各项信息，找出标志为1且用户名和设备名与被释放的名字相同的打印机编号；该打印机的标志清0；清除该打印机的用户名和设备名。,打印机分配表（初始情况）,打印机分配表（出错情况）,可见，Pa和Pb对分配表的使用必须互斥执行,2.5.2 竞争条件和临界

16、区,竞争条件（Race Condition）两个或多个进程同时访问和操纵相同的数据时，最后的执行结果取决于进程运行的精确时序。临界资源（Critical Resource）一次仅允许一个进程使用的共享资源临界区（Critical Section），简称CS区 在每个进程中访问临界资源的那段程序,典型进程进入临界区的一般结构,临界区进入准则独占临界区前进速度不确定区内进程不受干扰 有期等待,进程A和进程B互斥使用临界区的过程,2.5.3 进程同步机制,实现互斥方式 利用硬件方法解决进程互斥问题 禁止中断 进入临界区之后立即关闭所有的中断 专用机器指令 TSL（Test and Set Lock，

17、即测试并上锁）的指令：TSL RX，LOCK 汇编代码示例 enter_region:TSL REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RET leave_region:MOVE LOCK,#0 RET,原语操作原语（primitive）是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomic action），即一个操作中的所有动作要么全做，要么全不做。执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。,利用软件方法解决进程互斥问题 可为每类临界区设置一把锁，该锁有打开和关闭两种状态。进程

18、执行临界区程序的操作按下列步骤进行：关锁 执行临界区程序 开锁 软件锁实现 关锁原语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的指针。typedef struct i

19、nt value;struct PCB*list;semaphore;,结构型信号量,信号量的值与相应资源的使用情况有关信号量的一般结构及PCB队列,对信号量的操作有如下严格限制：信号量可以赋初值，且初值为非负数。在使用过程中，信号量的值可以修改，但只能由P和V操作来访问，不允许通过其他方式来查看或操纵信号量。设信号量为S，对S的P操作记为P(S)，对S的V操作记为V(S)。,结构型信号量,P(S):顺序执行下述两个动作：信号量的值减1，即S=S-1；如果S0，则该进程继续执行；如果S0，则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S

20、上执行V操作，把它释放出来为止）。V(S):顺序执行下述两个动作：S值加1，即S=S+1；如果S0，则该进程继续运行；如果S0，则释放信号量队列上的第一个PCB（即信号量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续运行。、操作都应作为一个整体实施，不允许分割或相互穿插执行。,2.5.4 信号量的一般应用,1.用信号量实现进程互斥 打印机分配表的互斥使用 Pa:Pb:P(mutex)P(mutex)分配打印机 释放打印机（读写分配表）（读写分配表）V(mutex)V(mutex),用信号量实现进程互斥,利用信号量实现互斥的一般模型是：进程P1 进程P2 进程Pn

21、 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 供者

22、进程 用者进程 L1:P(S1)L2:启动读卡机 P(S2);从缓冲区取出信息 收到输入结束中断 V(S1);V(S2);加工并且存盘 goto L1;goto L2;,用P和V操作实现同步时应注意如下三点：分析进程间的制约关系，确定信号量种类。信号量的初值与相应资源的数量有关，也与P,V操作在程序代码中出现的位置有关。同一信号量的P,V操作要“成对”出现，但是，它们分别出现在不同的进程代码中。,3.生产者消费者问题生产者:能产生并释放资源的进程消费者:单纯使用（消耗）资源的进程问题表述 一组生产者进程和一组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等

23、统称为产品）送入缓冲区，消费者进程从中取出产品。假定缓冲区共有N个，不妨把它们设想成一个环形缓冲池。,生产者-消费者问题环形缓冲池,它们应满足如下同步条件：任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量（N）。所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。,生产者-消费者问题,设缓冲区的编号为0N-1，in和out分别是生产者进程和消费者进程使用的指针，指向下面可用的缓冲区，初值都是0。设置三个信号量：full：表示放有产品的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只

24、有一个进程使用缓冲区。,生产者-消费者问题,生产者进程Producer：消费者进程Consumer：while(TRUE)while(TRUE)P(empty);P(full);P(mutex);P(mutex);产品送往buffer(in);从buffer(out)中取出产品；in=(in+1)mod N;out=(out+1)mod N;/*以N为模*/*以N为模*/V(mutex);V(mutex);V(full);V(empty);,应注意：在每个程序中必须先做P(mutex)，后做V(mutex)，二者要成对出现。对同步信号量full和empty的P,V操作同样必须成对出现，但它们分

25、别位于不同的程序中。无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。,2.6 进程通信,进程通信进程间的信息交换低级进程通信互斥和同步机构 高级进程通信 共享存储器方式：在内存中分配一片空间作为共享存储区 管道文件方式：写者向管道文件中写入数据；读者从该文件中读出数据 消息传递方式：以消息（Message）为单位在进程间进行数据交换 直接通信方式 间接通信方式,消息缓冲通信 消息通信方法的设计思想 接收消息进程的PCB和它的消息缓冲链的关系,name：发送消息的进程名或标志号size：消息长度text：消息正文next：下个缓冲区的地址mutex：消息队列操作互斥信号灯 Sm：

26、表示接收消息计数和同步的信号灯 Pm：指向该进程的消息队列中第一个缓冲区的指针,两个进程进行消息传送的过程,信箱通信 信箱是一种数据结构，在逻辑上可分为两个部分：信箱头包括信箱名字、信箱属性（公用、私用或者共享）、信箱格状态等；信箱体用来存放消息的多个信箱格。信箱可以动态创建和撤消 发送和接收消息的原语形式 send(mailbox,message)receive(mailbox,message)mailbox为信箱，message是要发送的消息 信箱可分为三类：公用信箱 共享信箱 私有信箱,2.7 管程,管程：一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和

27、改变管程中的数据。由管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句四部分组成。,管程的结构,管 程,管程具有以下三个特性：管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问。进程要想进入管程，必须调用管程内的某个过程。一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。,管 程,实现互斥是由编译程序完成为解决同步问题，引入两个条件变量x和y：condition x,y;操作原语wait(x)：挂起等待条件x的调用进程，释放相应的管程，以便供其他进程使用。操作原语

28、signal(x)：恢复执行先前因在条件x上执行wait而挂起的那个进程。管程的职责与信号量的职责不同。,带条件变量的管程结构,2.8经典进程同步问题1读者-写者问题 读者-写者问题也是一个著名的进程互斥访问有限资源的同步问题。例如，一个航班预订系统有一个大型数据库，很多竞争进程要对它进行读、写。允许多个进程同时读该数据库，但是在任何时候如果有一个进程写（即修改）数据库，那么就不允许其他进程访问它 既不允许写，也不允许读。,读者-写者问题,信号量设置：读互斥信号量rmutex 初值为1 写互斥信号量wmutex 初值为1 rmutex：读者互斥地访问readcount wmutex：保证一个写

29、者与其他读者/写者互斥地访问共享资源,读计数器readcount，整型变量，初值为0。,读者-写者问题,读者Readers while(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);使用读取的数据,写者Writers while(TRUE)P(wmutex);执行写操作 V(wmutex);,这个算法隐含读者的优先级高于写者,2哲学家进餐问题五位哲学家围

30、坐在一张圆桌旁进餐，每人面前有一只碗，各碗之间分别有一根筷子。每位哲学家在用两根筷子夹面条吃饭前独自进行思考，感到饥饿时便试图占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能强行从邻座手中拿过筷子，而且必须用两根筷子进餐；餐毕，要把筷子放回原处并继续思考问题。,哲学家进餐问题,哲学家进餐问题的一种算法,=#define N 5#define LEFT(i-1)%N#define RIGHT(i+1)%N#define THINKING 0#define HUNGRY 1#define EATING 2 typedef struct/*定义结构型信号量*/int value;struct

31、 PCB*list;semaphore;int stateN;semaphore mutex=1;/*互斥进入临界区*/semaphore sN;/*每位哲学家一个信号量*/,哲学家进餐问题,void philosopher(int i)while(TRUE)think();/*哲学家在思考问题*/take_chopstick(i);/*拿到两根筷子或者等待*/eat();/*进餐*/put_chopstick(i);/*把筷子放回原处*/void take_chopstick(int i)P(mutex);statei=HUNGRY;test(i);/*试图拿两根筷子*/V(mutex);P

32、(si);,哲学家进餐问题,void put_chopstick(int i)P(mutex);statei=THINKING;test(LEFT);/*查看左邻，现在能否进餐*/test(RIGHT);/*查看右邻，现在能否进餐*/V(mutex);void test(int i)if(statei=HUNGRY=,打瞌睡的理发师,3打瞌睡的理发师问题理发店有一名理发师，一把理发椅和几把座椅，等待理发者可坐在上面。如果没有顾客到来，理发师就坐在理发椅上打盹。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在理发，该顾客就坐在椅子上排队；如果满座了，他就离开这个理发店，到别处去理发。,打瞌睡

33、的理发师问题,理发师和每位顾客都分别是一个进程=#define CHAIRS 5typedef struct int value;struct PCB*list;semaphore;semaphore customers=0;semaphore barbers=0;semaphore mutex=1;int waiting=0;,void barber(void)while(TRUE)P(customers);/*如果没有顾客，则理发师打瞌睡*/P(mutex);/*互斥进入临界区*/waiting-;V(barbers);/*一个理发师准备理发*/V(mutex);/*退出临界区*/cut_

34、hair();/*理发（在临界区之外）*/,打瞌睡的理发师问题,打瞌睡的理发师问题,void customer(void)P(mutex);/*互斥进入临界区*/if(waitingCHAIRS)waiting+;V(customers);/*若有必要，唤醒理发师*/V(mutex);/*退出临界区*/P(barbers);/*如果理发师正忙着，则顾客打瞌睡*/get_haircut();else V(mutex);/*店里人满了，不等了*/,2.9 死锁,2.9.1 死锁概述 若干进程竞争有限资源、又加上推进顺序不当，从而构成无限期循环等待的局面。1.死锁示例 硬件资源死锁 软件资源死锁 可

35、抢占资源 当该资源被某进程拥有后，其它进程仍可以把它抢占过去为己所用，并且不会产生任何不良影响。例如，内存就是可抢占资源。不可抢占资源 该资源一旦被某进程占有，则其它进程不能强行抢占，必须由拥有者自动释放，否则会引起相关计算的失效。如光盘刻录机。死锁和不可抢占资源有关,2死锁定义死锁 是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。资源死锁 计算机系统产生死锁的根本原因就是资源有限且操作不当死锁的危害 系统瘫痪 资源浪费,3.产生死锁的原因 一般进程使用资源的顺序：申请 使用 释放 进程推进顺序对引发死锁的影响 有两个进程A和B，竞争两个资

36、源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 称为赋给

37、边 在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。,资源分配图示例（1）集合P,R和E如下：P=p1,p2,p3 R=r1,r2,r3,r4 E=p1r1,p2r3,r1p2,r2p2,r2p1,r3p3（2）资源数量 分别为1，2，1，3（3）进程状态 该图不含环路，没有死锁,资源分配图示例,环路与死锁 如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。,环路与死锁,有死锁的资源分配图,有环路但无死锁的资源分配图,如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。,资源分配图中存在环路是死锁产生的必要条件，但不是充分条件。,6.对待死锁的策

38、略 忽略死锁问题 死锁预防（静态策略）死锁避免（动态策略）死锁的检测与恢复,2.9.2 死锁的预防,1.破坏互斥条件2.破坏占有且等待条件 预分资源策略静态分配“空手”申请资源策略不占有资源时才可以申请资源 这两种方法存在以下4个主要缺点 不可预测 利用率低 降低并发性“饥饿”现象,破坏非抢占条件 处于等待状态进程当前所占有的全部资源可被抢占 4破坏环路等待条件 资源有序分配策略 资源编号 设R=r1,r2,rm，表示一组资源 定义一对一的函数F：RN，N是一组自然数。如：F（磁带机）=1，F（磁盘机）=5，F（打印机）=12 依序分配 约定：所有进程对资源的申请严格按照序号递增的次序进行。,

39、先弃大，再取小 一个进程申请资源rj，它应释放所有满足F(ri)F(rj)关系的资源ri 这两种办法都是可行的，都可排除环路等待条件 优点：资源利用率和系统吞吐量都有很大提高 缺点：资源请求受限，合理编号困难，增加系统开销。暂不使用的资源也需提前申请，增加资源占用时间。,2.9.3 死锁的避免,排除死锁的动态策略。关键是确定资源分配的安全性 1.安全状态在当前分配状态下，进程的安全序列P1,P2,Pn是：若对于每一个进程Pi（1in），它需要的附加资源可被系统中当前可用资源与所有进程Pj（ji）当前占有资源之和所满足，则P1,P2,Pn为一个安全序列。这时系统处于安全状态。存在安全序列时一定不

40、会有死锁发生 死锁是不安全状态中的特例,安全状态,安全状态示意设系统中共有10台磁带机，有三个进程p1,p2和p3，分别拥有3台、2台和2台磁带机，而它们各自的最大需求分别是9台、4台和7台磁带机。此时，系统已分配了7台磁带机，还有3台空闲。下表给出三个进程在不同时刻占有资源及向前推进的情况。,不安全状态示意,若不按照安全序列分配资源，则系统可能会由安全状态转换为不安全状态,死锁的避免,死锁状态是不安全状态。如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。,2.银行家算

41、法“银行家算法”（Bankers Algorithm）针对多体资源类 设计思想：当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。,银行家算法数据结构令n表示系统中进程的数目，m表示资源分类数。Available是一个长度为m的向量，它表示每类资源可用的数量。Available j=k，表示rj类资源可用的数量是k。Max是一个nm矩阵，它表示每个进程对资源的最大需求。Maxi,j=k，表示进程pi至多可申请k个rj类资源单位。Allocation是一个nm矩阵，它表示当前分给每个进程的资源数目。Alloca

42、tion i,j=k，表示进程pi当前分到k个rj类资源。Need是一个nm矩阵，它表示每个进程还缺少多少资源。Need i,j=k，表示进程pi尚需k个rj类资源才能完成其任务。记号：令X和Y表示长度为n的向量 可以把矩阵Allocation和Need中的每一行当做一个向量，并分别写成Allocationi和Needi。Allocationi表示当前分给进程pi的资源。,资源分配算法令Requesti表示进程pi的申请向量。Requestij=k，表示进程pi需要申请k个rj类资源。当进程pi申请资源时，就执行下列动作：若RequestiNeedi，表示出错，如果RequestiAvaila

43、ble，则pi等待。假设系统把申请的资源分给进程pi，则应对有关数据结构进行修改：Available：=Available Requesti Allocationi：=Allocationi+Requesti Needi：=Needi Requesti 系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程pi 的此次申请；否则，若新状态是不安全的，则pi等待，对所申请资源暂不予分配，并且把资源分配状态恢复成之前的情况。,安全性算法 令Work和Finish分别表示长度为m和n的向量，最初，置Work：=Available，Finishi：=false，i=1,2

44、,n。搜寻满足下列条件的i值：Finishi=false，且NeediWork。若没有找到，则转向。修改数据值：Work：=Work+Allocationi（pi释放所占的全部资源）Finishi=true 转向。若Finishi=true对所有i都成立（任一进程都可能是pi），则系统处于安全状态；否则，系统处于不安全状态。,算法应用示例假定系统中有4个进程A,B,C,D和三类资源R1,R2和R3，各自的数量分别为9,3和6个单位。,T0时刻资源分配表（安全）,资源情况,T0时刻是安全的 存在一个安全序列B,A,C,D,进程,T0时刻的安全序列,进程A请求资源 进程A发出请求Request（1

45、,0,1）,系统按银行家算法进行检查,系统进入不安全的状态 不能为进程A分配所申请的资源,为进程A分配资源后的有关数据,银行家算法,优点：限制条件少 资源利用程度提高 缺点：难以保证进程数固定不变 未考虑实时进程快速响应 增加了系统开销,2.9.4 死锁的检测和恢复,死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来。,1.对单体资源类的死锁检测,等待图资源分配图的变形 从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的,资源分配图和对应的等待图,2 对多体资源类的死锁检测

46、,采用若干随时间变化的数据结构，与银行家算法相似 Available是一个长度为m的向量 Allocation是一个nm的矩阵 Request是一个nm的矩阵，Requesti,j=k，表示进程pi正申请k个rj类资源 仍把矩阵Allocation和Request的行作为向量对待，并分别表示为Allocationi和Requesti,对多体资源类的死锁检测,检测算法 简单地调查尚待完成的各个进程所有可能的分配序列 令Work和Finish分别表示长度为m和n的向量，初始化 Work：=Available；对于i=1,2,n 如果Allocationi0，则Finishi：=false；否则Fi

47、nishi：=true。寻找一个下标i，它应满足条件：Finishi=false且RequestiWork 若找不到这样的i，则转到。修改数据值：Work：=Work+Allocationi Finishi=true 转向。若存在某些i（1in），Finishi=false，则系统处于死锁状态。此外，若Finishi=false，则进程pi处于死锁环中。何时调用检测算法取决于两个因素：死锁出现的频繁程度；有多少个进程受到死锁的影响。,3 从死锁中恢复,通过抢占资源实现恢复 临时性地把资源从当前占有它的进程那里拿过来，分给另外某些进程，直至死锁环路被打破。通过回退执行实现恢复由系统管理员做出安排

48、，定期对系统中各个进程进行检查，并将检查点的有关信息（如进程状态、资源状态等）写入文件。当检测到死锁时，就让某个占有必要资源的进程回退到它取得另外某个资源之前的一个检查点。回退过程所释放的资源分配给一个死锁进程，然后重新启动运行。系统中应保存一系列检查点的文件。要确定这个进程后退多远。还有一种“全体”回退方式,通过杀掉进程实现恢复终止所有的死锁进程。一次终止一个进程，直至消除死锁环路。如何确定哪个进程将被终止，一般要考虑以下6种因素：进程的优先级。进程已计算了多长时间，该进程在完成预定任务之前还要计算多长时间。该进程使用了多少和什么类型的资源（例如，这些资源可简单地抢占吗？）。为完成任务，它还需要多少资源？有多少个进程被终止？这个进程是交互式进程，还是批处理进程？,2.9.5 活锁和饥饿,活锁,如果进程A先运行并且得到资源R，接着进程B运行并得到资源S，,好像发生死锁了，但是它们都没有被阻塞，都可以活动。这种现象就是活锁（Livelock）。,2.饥饿在某些策略下，系统会出现这样一种情况：在可以预计的时间内，某个或某些进程永远得不到完成工作的机会，因为它们所需的资源总是被别的进程占有或抢占。这种状况称做“饥饿”或者“饿死”（Starvation）。例如，考虑打印机的分配问题。饥饿不同于死锁,Bye!,下一章(NEXT)：,第3章-处理机调度,=,