【优选】操作系统概念复习资料【-章】PPT文档.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第1-2章 导论和操作系统结构,明确操作系统的作用。,明确操作系统包括哪些功能,明确用户模式和内核模式的概念及作用。,了解操作系统提供的服务有哪些,明确系统调用的工作机制。,明确操作系统的结构有哪些，各自优缺点。,了解虚拟机及优点,第,1-2,章 导论和操作系统结构,1.,操作系统的作用,答：操作系统提供了程序执行的环境。它的职能是管理和控制计算机系统中的所有软硬件资源，合理的组织计算机工作流程，并为用户提供一个良好的工作环境与友好的接口。,Allocation,答：线程池的思想是在进程开始时创建一定数量的线程并将它们置入一个池（pool）中，线程在这个池中等待工作。,答：进程和程序是既有联系又有区别的两个概念，它们的主要区别如下：,Finish1=true,(2)优先级调度算法。,下列哪一个不是操作系统的主要特征?,显然，5个进程的周转时间为：T1=30min、T2=22min、T3=6min、T4=16min、T5=28min。,B它的优先权变为最大,安全序列=,它包含了一个线程 ID、一个程序计数器、一个寄存器组和一个堆栈。,其次，虚拟机允许在不干扰正常的系统操作的情况下进行系统开发。,设系统中仅有一个资源类，其中共有3个资源实例，使用此类资源的进程共有3个，每个进程至少请求一个资源，它们所需资源最大量的总和为X，则发生死锁的必要条件是（X的取值）：（？）,(3)如果系统采用时间片轮转（RR）算法，令时间片为2分钟，5个任务轮流执行的情况为：,X=a+b+c 6,（2）南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。,初始状态检测流程(2),第,1-2,章 导论和操作系统结构,2.,操作系统包括哪些功能,答：,存储器管理功能，主要包括：内存分配、地址映射、内存保护和内存扩充。,处理机管理功能，其功能包括：作业和进程调度，进程控制和进程通信。,设备管理功能，主要包括：缓冲区管理、设备分配、设备驱动和设备无关性（设备处理）。,文件管理功能，其功能包括：文件存储空间的管理、文件操作的一般管理、目录管理、文件的读写管理，存取控制和保护。,用户接口：命令接口、程序接口、图形接口,第,1-2,章 导论和操作系统结构,3.,核心模式和用户模式,答：核心模式一般指操作系统管理程序运行的状态，具有较高的特权级别。,用户模式一般指用户程序运行时的状态，具有较低的特权级别。,当处理器处于管态时全部指令（包括特权指令）可以执行，可使用所有资源，并具有改变处理器状态的能力。当处理器处于用户模式时，就只能执行非特权指令。特权级别不同，可运行指令集合也不同。特权级别越高，可以运行指令集合越大。高特权级别对应的可运行指令集合包含低特权级的。核心模式到用户模式的唯一途径是通过中断。,第,1-2,章 导论和操作系统结构,4.,操作系统提供的服务有哪些,答：程序执行、,I/O,操作、文件系统处理、通信、错误检测、资源分配、户管理、保护,第,1-2,章 导论和操作系统结构,5.,系统调用的工作机制,用户在需要执行特权指令时，调用系统调用，陷入内核（不同的任务，所对应调用的系统调用号也不同，在调用系统调用陷入内核时，会同时向,OS,内核传入一个系统调用号,i,）,进入内核后，根据,i,查找系统调用表，找到调用号为,i,的系统调用的处理代码,内核执行完系统调用处理代码后，从核心态返回用户态,第,1-2,章 导论和操作系统结构,6,操作系统的结构有哪些，各自优缺点,答：,1.,简单结构,2.,层次化设计,3.,微内核,要求：能用简单的语言说明不同结构操作系统的特点,7,虚拟机的优点,答：虚拟机技术主要有两个优点。,首先，通过完全的保护系统资源，虚拟机提供了一个健壮的安全保护层。,其次，虚拟机允许在不干扰正常的系统操作的情况下进行系统开发。,第,1-2,章 导论和操作系统结构,选择题：,1.,以下有关操作系统的叙述中，哪一个是不正确的？,A.,操作系统管理系统中的各种资源,B.,操作系统为用户提供的良好的界面,C.,操作系统就是资源的管理者和仲裁者,D.,操作系统是计算机系统中的一个应用软件,D,2.,分时操作系统的主要特点是,。,A.,个人独占机器资源,B.,自动控制作业运行,C.,高可靠性和安全性,D.,多个用户共享计算机资源,D,3.,操作系统具有进程管理,存储管理,文件管理和设备管理的功能,下列有关描述中,哪一项是不正确的,?,A.,进程管理主要是对程序进行管理,B.,存储管理主要管理内存资源,C.,文件管理可以有效的支持对文件的操作，解决文件共享、保密和保护问题,D.,设备管理是指计算机系统中除了,CPU,和内存以外的所有输入输出设备的管理,A,4.,下列哪一个不是操作系统的主要特征,?,A.,并发性,B.,共享性,C.,灵活性,D.,随机性,C,5.,用户与操作系统打交道的手段称为,。,A,命令输入,B,广义指令,C,通信,D,用户接口,D,6,从用户的观点看，操作系统是,。,A,用户与计算机之间的接口,B,控制和管理计算机资源的软件,C,合理地组织计算机工作流程的软件,D,由若干层次的程序按一定的结构组成的有机体,A,7.,操作系统提供给程序员的接口是,。,A,进程,B,系统调用,C,库函数,D,B,和,C,B,8.,计算机的操作系统是一种,。,A.,应用软件,B.,系统软件,C.,工具软件,D.,字表处理软件,B,第3章 进程,明确进程的概念及组成。,明确进程的基本状态及转换条件,明确进程控制块的作用,明确进程调度的类型（长，中，短）及调度的过程（上下文切换）,了解进程的操作有哪些。,明确进程间通信的机制有哪些。,第,3,章 进程,1,进程的概念及组成。,概念：进程是指在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个能独立运行的活动实体。多个进程间可以并发执行和交换信息。一个进程在运行时需要一定的资源，如,CPU,、存储空间及,I/O,设备等。,组成：,（,1,）进程标识符：它是惟一的标志对应进程的一个标志符或数字；,（,2,）处理机状态：包括是处理机的各种寄存器内容信息；,（,3,）进程调度信息：表明该进程的执行状态；调度优先权：表示进程获取,CPU,的优先级别；进程之间通信信息：反映该进程与哪些进程有什么样的通信关系；,（,4,）进程控制信息：被保护的信息有：程序计数器程序状态字，各工作寄存器的内容等；资源需求、分配和控制方面的信息；进程实体信息：指出该进程的程序和数据的存储情况，在内存或外存的地址、大小等；族系关系：反映父子进程的隶属关系；其它信息：如文件信息、工作单位等。,第,3,章 进程,2,进程的基本状态及转换条件,状态：,创建：进程正被创建。,运行：（进程的）指令正被执行。,等待：进程正在等待发生一些事件（如,I/O,完成或接收一个信号）。,就绪：进程正等待分配处理器。,终止：进程结束运行,第,3,章 进程,转换：,(1),就绪运行：进程具备运行条件，当进程调度程序选择了进程后，便将其转入运行状态。,(2),运行阻塞：进程需要等待某种事件的发生，如执行了输入输出指令，或者请求资源得不到满足时，进程转阻塞状态。,(3),阻塞就绪：进程等待的,I/O,已完成，或者请求的资源得到满足，进程转为就绪状态。,(4),创建就绪：进程尚不具备运行条件，所需的资源尚未得到满足。当进程创建完成后，进程可转入就绪状态。,(5),运行延迟：进程运行过程中，因某种原因需要延迟运算，则设定好延迟时间后被转入延迟状态。,(6),运行完成：进程运行时遇到结束指令后，被转入完成状态。,第,3,章 进程,3,进程控制块（,PCB,）的作用,答：进程控制块是进程组成中最关键的部分。每个进程有惟一的进程控制块。操作系统根据,PCB,对进程实施控制和管理。进程的动态、并发等特征是利用,PCB,表现出来的。,PCB,是进程存在的惟一标志。,第,3,章 进程,4,进程调度的类型（长，中，短）及调度的过程（上下文切换）,（,1,）高级调度（,high Level Scheduling,）：又称为作业调度或者长程调度（,longTerm Scheduling,）,其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，也就是说，它调度对象是作业。,P84,（,2,）低级调度（,low Level Scheduling,）称为进程调度或短程调度（,shortTerm Scheduling,）,它所调度的对象是进程（或内核级线程。）进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的,OS,中，都必须配置这级调度。,P86,（,3,）中级调度（,Intermediate Level Scheduling,）又称中程调度（,Medium-Term Scheduling,）,.,引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。,第,3,章 进程,5,进程的操作有哪些。,答：包括进程的创建和进程的终止,6,进程间通信的机制有哪些。,答：消息传递系统、命名（包括直接通信和间接通信）、同步、缓冲,问答题：,1.,试比较进程和程序的区别,答：进程和程序是既有联系又有区别的两个概念，它们的主要区别如下：,（,1,）进程是程序在处理机上的一次执行过程，是一个动态概念；而程序是代码的有序集合，其本身没有任何运行的含义，是一个静态的概念。,（,2,）进程是一个状态变化的过程，是有生命期的，表现在它因创建而产生，因调度,而执行，因得不到资源而暂停，因撤销而消亡；而程序是永久的，可以长久保存。,（,3,）进程和程序的组成不同。进程由程序、数据和进程控制块组成，而程序仅是代,码的有序集合。,（,4,）进程与程序之间不是一一对于的。通过多次运行，同一个程序可以对应多个进程过调用关系，一个进程可以包含多个程序。,2.,并行与并发的概念,并发（,Concurrent,）：多个事件在同一时间段内发生。操作系统是一个并发系统，各进程间的并发，系统与应用间的并发。操作系统要完成这些并发过程的管理。,并行,(parallel),是指在同一时刻发生。,选择题：,1.当前运行的进程（），将引发系统进行进程调度。,A.执行了一条转移指令,B.要求增加主存空间，经系统调用 家算法进行测算认为是安全的,C.执行了一条I/O指令,D.执行程序期间发生了I/O完成中断,C,2.,下面所述步骤中，,不是创建进程所必需的。,A,由调度程序为进程分配,CPU B,建立一个进程控制块,C,为进程分配内存,D,将进程控制块链入就绪队列,A,3.,分配到必要的资源并获得处理机机时的进程状态是,。,A,就绪状态,B,执行状态,C,阻塞状态,D,撤销状态,B,4.,下面对进程的描述中，错误的是,。,A,进程是动态的概念,B,进程执行需要处理机,C,进程是有生命期的,D,进程是指令的集合,D,5.,操作系统中，若进程从执行状态转换为就绪状态，则表示,。,A,时间片到,B,进程被调度程序选中,C,等待某一事件,D,等待的事件发生,A,6.,一个进程被唤醒意味着,。,A,该进程重新占有了,CPU,B,它的优先权变为最大,C,其,PCB,移至等待队列队首,D,进程变为就绪状态,D,第4章 线程,明确线程的基本概念及组成,明确引入线程的好处。,明确用户级线程和内核级线程的区别,明确多线程模型有哪些，各自优缺点,了解线程池的思想。,1,线程的基本概念及组成,答：线程，有时也被称为轻量级进程（,LWP,），是一个基本的,CPU,执行单元；它包含了一个线程,ID,、一个程序计数器、一个寄存器组和一个堆栈。它与属于同一个进程的其它的线程共享代码段、数据段，以及其它的操作系统资源。,2,引入线程的好处。,答：提高了响应速度，资源共享，经济实惠，提高了多处理机体系结构的利用率，使,OS,具有更好的并发性,1抢占式和非抢占式区别,死锁预防和死锁避免：采用某种协议预防或避免死锁，确保系统不会进入死锁状态。,Finish1=true,第2个request降临,B它的优先权变为最大,了解多处理器调度要处理的问题,问题中的这个事件是指 signal操作的执行。,A进程 B系统调用 C库函数 DB和C,（3）进程和程序的组成不同。,A时间片到 B进程被调度程序选中 C等待某一事件 D等待的事件发生,答：线程池的思想是在进程开始时创建一定数量的线程并将它们置入一个池（pool）中，线程在这个池中等待工作。,每个进程有惟一的进程控制块。,如果池中没有可用的线程，那么服务器就等待，直到某个线程被释放。,当服务器接收到一个请求时，它就从池中唤醒一个线程（如果有可用的线程），由它来处理请求。,(2)运行阻塞：进程需要等待某种事件的发生，如执行了输入输出指令，或者请求资源得不到满足时，进程转阻塞状态。,答：对用户线程的支持通常处于内核之上，通过一个用户级线程库（thread library）实现。,族系关系：反映父子进程的隶属关系；,P(loadNS);,3,用户级线程和内核级线程的区别,答：对用户线程的支持通常处于内核之上，通过一个用户级线程库（,thread library,）实现。线程库提供了对线程的创建、调度和管理的支持，这无需来自内核的支持。用户级线程的创建和管理通常很快；,内核线程由操作系统直接支持：内核在内核空间内实现了线程的创建、调度和管理。因为线程管理由操作系统完成，所以内核线程的创建和管理要比用户线程慢。,4,多线程模型有哪些，各自优缺点,多对一模型,:,优点：效率比较高。缺点：如果一个线程调用了导致阻塞的系统调用的话，那么将阻塞整个进程。在多处理机环境中多个线程不能够并发执行。用户级线程库在那些采用了多对一模型不支持。,一对一模型,:,优点：更好的并发性；允许多个线程在多处理机环境中并行执行。缺点：在于创建一个用户线程就需要创建一个相应的内核线程。,多对多模型,:,优点：允许开发者随心所欲的创建用户线程。允许更大的并行性。缺点：开发者能够创建所需的用户线程，而且相应的内核线程能够在多处理机环境中并行运行。而且当一个线程执行导致阻塞的系统调用时，内核能够调度其它的线程执行。,5,线程池的思想。,答：线程池的思想是在进程开始时创建一定数量的线程并将它们置入一个池（,pool,）中，线程在这个池中等待工作。当服务器接收到一个请求时，它就从池中唤醒一个线程（如果有可用的线程），由它来处理请求。一旦线程服务完毕，它就返回线程池等待后面的工作。如果池中没有可用的线程，那么服务器就等待，直到某个线程被释放。,问答题：,1.,什么是线程？描述线程和进程的区别？,答：线程是在进程内用于调度和占有处理机的基本单位，它由线程控制表、存储线程上下文的用 户栈以及核心栈组成。,调度：传统操作系统中，拥有资源的基本单位和独立调度分派的基本单位都是进程；而引入线程的操作系统中，线程是调度和分派的基本单位，进程则是资源分配的基本单位。,并发性：在引入线程的,OS,中，进程之间可以并发执行，同一进程的多个线程之间也可以并发执行，从而使得,OS,具有更好的并发性。,拥有资源：在,OS,中，进程是拥有资源的一个独立单位，它拥有自己的资源，而线程一般不拥有系统资源，但是它可以访问其隶属进程的资源。,系统开销：创建和撤销进程涉及资源的分配或回收，需要比线程创建和撤销大得多的系统开销，同样的，进程切换的开销也远远大于线程切换的开销。,第5章 CPU调度,明确抢占式和非抢占式区别,了解分派程序的功能,明确调度的准则有哪些,明确各种调度算法的准则,了解多处理器调度要处理的问题,1,抢占式和非抢占式区别,抢占式的：当进程从运行状态转换到就绪状态时或者当进程从等待状态转换到就绪状态时。,非抢占式的：当进程从运行状态转换到等待状态时或者当进程终止时。,在非抢占式调度下，一旦把,CPU,分配给一个进程，那么该进程就会保持,CPU,直到终止或转换到等待状态。,抢占式调度要付出一定的代价,2,调度的准则有哪些,答：,先来先服务（,FCFS,）调度算法,短作业优先（,SJF,）或最短剩余时间优先调度算法,优先调度算法。,轮转（,RR,）调度算法,级队列调度算法,多级反馈队列调度算法,要求：各种调度算法的准则,选择题：,1.,分时系统中进程调度算法通常采用,。,A.,响应比高者优先,B.,时间片轮转法,C.,先来先服务,D.,短作业优先,B,2.,下列进程调度算法中，（,）可能会出现进程长期得不到调度的情况。,A.,非抢占式静态优先权法,B.,抢占式静态优先权法,C.,时间片轮转调度算法,D.,非抢占式动态优先权法,B,3,为了照顾紧迫型作业，应采用（,）。,A.,先来服务调度算法,B.,短作业优先调度算法,C.,时间片轮转调度算法,D.,优先权调度算法,D,4,作业从后备作业到被调度程序选中的时间称为（,）。,A.,周转时间,B.,响应时间,C.,等待调度时间,D.,运行时间,A,4,在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（,）相同。,A.,先来先服务调度算法,B.,短作业优先调度算法,C.,时间片轮转调度算法,D.,长作业优先调度算法,C,问答题：,1,什么是常用调度算法的评价指标？,答：,CPU,利用率，吞吐量，周转时间，就绪等待时间，响应时间。,吞吐量表示单位时间,CPU,完成作业量，周转时间指的是从作业提交到作业完结的时间间隔，就绪等待时间是每个作业在就绪队列所花的时间，响应时间是提交第一个请求到产生第一个响应的时间。,综合分析题：,有,5,个任务,A,，,B,，,C,，,D,，,E,，它们几乎同时到达，预计它们的运行时间为,10,，,6,，,2,，,4,，,8min,。其优先级分别为,3,，,5,，,2,，,1,和,4,，这里,5,为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。,(1),先来先服务（按,A,，,B,，,C,，,D,，,E,）算法。,(2),优先级调度算法。,(3),时间片轮转算法。,(1),采用先来先服务（,FCFS,）调度算法时，,5,个任务在系统中的执行顺序、完成时间及周转时间如下表所示,根据表中的计算结果，,5,个进程的平均周转时间,T,为：,T=,（,10+16+18+22+30,）,执行次序,运行时间,优先数,等待时间,周转时间,A,10,3,0,10,B,6,5,10,16,C,2,2,16,18,D,4,1,18,22,E,8,4,22,30,(2),采用最高优先级调度（,HPF,）算法时，,5,个任务在系统中的执行顺序、完成时间及周转时间如下表所示：,它们的平均周转时间为：,T=,（,6+14+24+26+27,）,执行次序,运行时间,优先数,等待时间,周转时间,B,6,5,0,6,E,8,4,6,14,A,10,3,14,24,C,2,2,24,26,D,1,1,26,27,(3),如果系统采用时间片轮转（,RR,）算法，令时间片为,2,分钟，,5,个任务轮流执行的情况为：,第,1,轮：（,A,，,B,，,C,，,D,，,E,）,第,2,轮：（,A,，,B,，,D,，,E,）,第,3,轮：（,A,，,B,，,E,）,第,4,轮：（,A,，,E,）,第,5,轮：（,A,）,显然，,5,个进程的周转时间为：,T1=30min,、,T2=22min,、,T3=6min,、,T4=16min,、,T5=28min,。它们的平均周转时间,T,为：,T=,（,30+22+6+16+28,）,第6章 进程同步,明确临界区。,明确解决临界区必须要满足的三项要求。,明确信号量的定义。,熟练学会使用信号量解决进程间的同步和互斥问题。,1,临界区。,答：考虑由,n,个进程,P0,P1,.,Pn-l,构成的系统。每个进程有一个代码段，被称作临界区（,critical section,），进程在临界区内可能会修改公有变量、更新一个表、写一个文件等等。该系统的一个重要的特征是当一个进程在其临界区内执行时就不允许其它进程在它的临界区内执行。这样，进程对临界区的执行在时间上是互斥的。,临界区是指不允许多个并发进程交叉执行，一次最多允许一个进程进入的一段程序代码。临界区是由于不同并发进程的程序段共享公 用数据或公用数据变量而引起的。这些需要互斥访问的资源称为,临界区资源,。,2,解决临界区必须要满足的三项要求。,互斥（,Mutual Exclusion,）：如果进程,Pi,正在其临界区中执行，那么就不允许有其它进程在临界区中执行。,有空让进（,Progress,）：如果没有进程处于临界区而此时有进程希望进入临界区，那么只可以从这些不在剩余区执行的进程中挑选出下一个进入临界区的进程，而且这个选择不可以长时间的延缓。,有限等待（,Bounded Waiting,）：在一个进程请求进入临界区之后和获准之前，允许其它进程在有限的时间内进入临界区。,3,信号量的定义。,答：信号量是一种同步工具。信号量,S,是一个整形数，除初始化以外，对它的访问只能通过两个标准原子操作：,wait,和,signal,。最初，这被称为,P,操作,(for wait;from the Dutch proberen,to test),和,V,操作,(for signal;from verhogen,to increment),。,死锁的定义,答：具备一个等待队列的信号量实现可能会导致这样的一个情况：两个或多个进程无休止的等待发生一个事件，而这个事件只能由等待中的某个进程引发。问题中的这个事件是指,signal,操作的执行。当达到这样的一个状态时，我们称这些进程被死锁（,deadlock,）,议题1：同步问题,过桥问题：,一座小桥横跨南北两岸,（,1,）桥最多只能承重两个人，所以规定任意时刻同一方向只允许一人过桥,（,2,）南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。,试用信号量和,PV,操作写出南、北两岸过桥的同步算法。,桥的形状,N_thin=1,S_thin=1,loadNS=1,loadSN=1,P,N,:,P(loadNS);,P(N_thin);,走过北边狭窄通道,V(N_thin);,走过宽敞的通道；,P(S_thin);,走南边狭窄通道；,V(S_thin);,V(loadNS);,P,S,:,P(loadSN);,P(S_thin);,走过南边狭窄通道,V(S_thin);,走过宽敞的通道；,P(N_thin);,走北边狭窄通道；,V(N_thin);,V(loadSN);,第7章 死锁,明确死锁产生的四个必要条件,明确死锁的处理方法,明确死锁预防的处理方法,明确死锁避免的处理方法（包括安全状态、死锁状态关系等）,1,死锁产生的四个必要条件,互斥条件：必须至少有一个资源以非共享的方式被进程持有；更确切的说，同时只有一个进程可以使用该资源。如果另一个进程请求这个资源，那么该进程必须等待这个资源被释放。,持有并等待条件：进程必须持有至少一个资源且等待获取另外的当前被其它进程持有的资源。,不可抢占条件：不可以抢占资源；也就是说，资源的释放只可以是由持有它的进程完成工作后自动释放。,循环等待条件：对一组等待进程,P0,P1,Pn,来说，必须：,P0,等待,P1,持有的资源，,P1,等待,P2,持有的资源，,，,Pn-1,等待,Pn,持有的资源，而,Pn,等待,P0,持有的资源。,2,死锁的处理方法,主要有三种方法可以处理死锁：,死锁预防和死锁避免：采用某种协议预防或避免死锁，确保系统不会进入死锁状态。,死锁恢复：允许系统进入死锁状态，然后检测并恢复。,完全忽视死锁并假设系统中不会发生死锁。包括,UNIX,在内的大多数操作系统采用了这种方法。,死锁习题1,产生死锁的基本原因是（）和（）。,答案：系统资源不足、进程推进顺序不当,备注：死锁的,4,大必要条件是出现死锁时候的状况，,这里讨论的是产生死锁的根本缘由。,死锁习题2,某系统中只有,11,台打印机，,N,个进程共享打印机，每个进程要求,3,台，当,N,取值不超过（）时，系统不会发生死锁？,最坏情况下，,N,个进程每个都得到,2,台打印机，都去申请第,3,台，为了保证不死锁，此时打印机的剩余数目至少为,1,台，则：,11-2N=1,N=5,死锁习题3,设系统中仅有一个资源类，其中共有,3,个资源实例，使用此类资源的进程共有,3,个，每个进程至少请求一个资源，它们所需资源最大量的总和为,X,，则发生死锁的必要条件是（,X,的取值）,：（？）,假设,3,个进程所需该类资源数分别是,a,b,c,个，因此有：,a+b+c=X,假设发生了死锁，也即当每个进程都申请了部分资源，还需最后一个资源，而此时系统中已经没有了剩余资源，即：,(a-1)+(b-1)+(c-1)3,X=a+b+c 6,因此，如果发生死锁，则必须满足的必要条件是（,X 6,）,议题2：家算法,家算法的运作的整个流程,如果单纯的流程还不够具体的话，来个实际一点的例子,最简单的死锁实例(初始状态):,Max,A B,p1:,p2:,1 1,1 1,Allocation,A B,0 0,0 0,Need,A B,1 1,1 1,Available,A B,1 1,如何检验,初始状态的安全性,呢,？,初始状态检测流程(1),最简单的死锁实例(检查初始状态是否安全):,Max,A B,p1:,p2:,1 1,1 1,Allocation,A B,0 0,0 0,Need,A B,1 1,1 1,Available,A B,1 1,Work,A B,1 1,Step1:,Work:=Availabe,目标：检验初始状态安全性！,初始状态检测流程(2),最简单的死锁实例(检查初始状态是否安全):,Max,A B,p1:,p2:,1 1,1 1,Allocation,A B,0 0,0 0,Need,A B,1 1,1 1,Available,A B,1 1,Work,A B,1 1,Step2:,寻找那个进程可以在现有,Work,资源集的基础上顺利执行完成,P1,P2,都可以作为备选，我们选,P1,P1,安全序列：,判断依据：,Need=Work,初始状态检测流程(3),最简单的死锁实例(检查初始状态是否安全):,Max,A B,P1:,p2:,1 1,1 1,Allocation,A B,0 0,0 0,Need,A B,1 1,1 1,Available,A B,1 1,Work,A B,1 1,P1,安全序列：,Step 2:,Finish1=true,Work=work+allocation1,Finish,true,初始状态检测流程(4),最简单的死锁实例(检查初始状态是否安全):,Max,A B,P1:,p2:,1 1,1 1,Allocation,A B,0 0,0 0,Need,A B,1 1,1 1,Available,A B,1 1,Work,A B,1 1,P1,P2,安全序列：,Step 3:,从尚未结束的进程中再挑下一个能够保证全部资源就绪的进程,Finish,true,这时只有,P2,可以选，并且,p2,满足要求,判断依据：,Need=Work,安检结果：初始状态安全,Max,A B,p1:,p2:,1 1,1 1,Allocation,A B,0 0,0 0,Need,A B,1 1,1 1,Available,A B,1 1,接着，进程,p1,发出请求,request=1,0,例子：,R=A,B,申请,a,b;,释放,a,b,p1:a b a b;,p2:b b a a,第一次预分配,Max,A B,p1:,p2:,1 1,1 1,Allocation,A B,1,0,0 0,Need,A B,0,1,1 1,Available,A B,0,1,预分配结果：,很容易判定安全,安全序列,=,第2个request降临,Max,A B,p1:,p2:,1 1,1 1,Allocation,A B,1,0,0 0,Need,A B,0,1,1 1,Available,A B,0,1,分配后：,Request2=(0,1),不安全，不分配，（分配不导致死锁）,例子：,R=A,B,申请,a,b;,释放,a,b,p1:a b a b;,p2:b b b a a b,家算法,的保守性,谢谢观看,