操作系统知识归纳PPT演示课件

第1章操作系统概论,1.操作系统定义地位：硬件层之上，所有其他软件层之下。作用：管理系统中软件硬件资源；为用户(应用程序)提供良好的服务(界面)。定义：操作系统是位于硬件层之上，所有其它软件层之下的一个系统软件，是管理系统中各种软硬件资源，方便用户使用计算机系统的程序集合。,1,第2章进程、线程和作业,1.多道程序设计设计目标：提高系统效率。多道程序设计的问题：处理机资源管理、存储资源管理、设备资源管理。2.进程引入进程的目的：为了多个程序并发执行，改善资源利用率和提高系统的吞吐量。进程的定义：进程是具有一定独立功能的程序关于一个数据集合的一次运行活动。进程控制块PCB进程的状态：三状态、五状态和七状态转换图及转换原因,2,3.线程线程的定义：进程内部具有独立功能的执行流。引入：切换速度快、系统开销小、通讯容易线程控制块TCB：标志线程存在的数据结构，包含线程控制的全部信息线程的状态：就绪、运行、等待线程的分类：用户级线程（库函数创建）和核心级别的线程（系统调用创建）进程与线程：进程是资源分配的最小单位，线程是处理器分配的最小单位。,3,4.作业作业：就是用户在一次计算过程中或一个事务处理中要求计算机系统所做工作的集合。作业步：要求计算机系统做的一项相对独立的工作叫做一个作业步。在逻辑上，我们可以说一个作业是由一系列有序的作业步所组成。一个作业内的作业步总是相互关联的。作业的状态：提交状态、后备状态、执行状态、完成状态、退出状态,4,作业的调度又称为高级调度或宏观调度。它根据系统的情况和作业调度策略将一些作业置于“执行状态”。由于作业调度程序选择到的作业只是有资格获得处理机，但不一定立刻就能占有它并在其上运行，一个已被作业调度程序调度到的作业（或它的相应进程）何时能够真正在物理处理机上运行，则取决于“进程调度”所遵循的调度策略。,5,第3章处理机调度,1.多级调度低级调度：进程调度中级调度：交换高级调度：作业调度2.处理机调度须解决的问题依照什么原则分配处理机，即需要确定处理机调度算法；什么时候分配处理机，即需要确定处理机调度时机；如何分配处理机，即需要给出处理机调度过程。,6,3.处理机调度算法选择的标准调度算法的选择应当与系统的设计目标相一致，同时考虑公平性与用户满意程度。具体考虑如下指标：CPU利用率：使CPU尽量处于忙碌状态；吞吐量：单位时间内所处理计算任务的数量；周转时间；从计算任务就绪到处理完毕；响应时间：从任务就绪到开始处理；系统开销：系统调度进程过程中所付出的时空代价。4.进程调度处理机的调度算法：处理机调度通常采用FCFS、短进程优先(SJF)、优先数法(HPF)、循环轮转法(RR)、分类排队法、最短剩余时间法、反馈排队法(FB)等。,7,5.处理机调度过程处理机调度过程：保存下降进程现场；选择将要运行进程；恢复上升进程现场。6.作业调度作业调度程序通常作为一个进程在系统中执行。它在系统初始化时被创建。它的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法选取作业。作业调度可以采用不同的算法。对于非多道程序系统一般有：先来先服务（FCFS）调度算法、最短作业优先（SJF）调度算法、响应比高者优先（HRN）的调度算法对于多道程序系统，常用的作业调度算法有：先来先服务的调度算法、优先级的作业调度、分时和优先级相结合的作业调度。,8,7.实时调度(real-timescheduling)（1）实时调度相关的几个概念：实时任务产生并可以开始处理的时间称为就绪时间(readytime)；实时任务最迟开始处理时间称为开始截止期(startingdeadline)；实时任务处理所需要的处理机时间称为处理时间(processingtime)；实时任务最迟完成时间称为完成截止期(completiondeadline)；周期性实时任务的发生间隔时间称为发生周期(occurringperiod)；实时任务的相对紧迫程度通常用优先级表示。,9,（2）实时调度算法：1）最早截止期优先调度优先选择完成截止期最早的实时任务，新到达的实时任务，如果其完成截止期先于正在运行任务的完成截止期，则重新分派处理机，即剥夺可以证明，对于EDF算法来说，公式：是实时任务可调度的充分条件2）速率单调调度RMS将任务的周期作为调度参数，其发生频度越高则调度级别越高。已经证明，RMS算法可调度的条件如下：,10,作业调度算法应用例子,在两道环境下有四个作业，已知它们进入系统的时间、估计运行时间。,11,第4章互斥、同步与通信,1.并发进程前驱图程序并发的基本特征：程序运行失去封闭性、运行结果不可再现性、异步性。进程并发执行的条件：Bernstein条件。假设程序P(i)所访问的共享变量的读集和写集分别为R(i)和W(i)，则任意两个程序P(j)和P(i)可以并发执行的条件有三条：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=。,S1:a=x+2;S2:b=y+4;S3:c=a+b;S4:d=c-6;S5:e=c+6;S6:f=c-e;,12,并发程序的表示cobeginS1;S2;Sncoend;parbeginS1;S2;Snparend;遇到并发（并行）语句时，同时创建n个进程（线程），分别执行S1,S2,Sn。当它们都结束时，并发（并行）语句结束。,13,2.互斥与同步临界资源：一次仅允许一个进程使用的资源。临界区：在进程中对于临界资源访问的程序段。多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。定义：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。,14,3.信号灯与PV操作在操作系统中信号量是表示资源的物理实体，是一个与队列有关的整型变量，其值仅能由P操作和V操作来改变。系统利用它的状态对进程和资源进行管理。用于信号量的P、V操作是同步原语，在执行期间不可分割。利用信号量能方便地解决临界区问题，设mutex为互斥的公用信号量，初始化为1，表示该临界资源未被占用。只需把进入临界区的操作置于P(mutex)和V(mutex)之间，即可实现进程互斥。利用信号量还可以实现进程同步，它是利用私用信号量在进程间实现同步操作。,15,（1）信号灯类型定义如下:typedefsemaphorestructintvalue;pointer_to_PCBqueue;,（3）P操作原语定义如下:voidP(semaphore*s)s-value-;if(s-valuequeue);,（2）信号灯变量说明如下:semaphores;,（4）V操作原语定义如下:voidV(semaphore*s)s-value+;if(s-valuequeue);,16,其中调用了asleep和wakeup两个标准过程,它们的定义如下:1）asleep(s-queue):执行此操作进程的PCB进入队列s-queue的尾部,其状态由运行转为等待,系统转到处理机调度程序。2）wakeup(s-queue):将队列s-queue头部的进程的PCB由该队列中取出并将其排入就绪队列,其状态由等待转为就绪。关于信号灯变量的使用有如下两个基本要求:1）必需置一次初值,只能置一次初值,而且初值必需为非负整数;2）只能执行P操作和V操作,所有其它操作均是非法的。,17,基于上述规定,我们可以得到如下几个有用的结论:(1)当s-value0时,s-queue为空；(2)当s-valuevalue为s-queue中等待进程的个数；(3)当s-value的初值为1时,可以用来实现进程互斥,这只需在进入临界区时执行一次P操作,在离开临界区时执行一次V操作。(4)当s-value的初值为正整数时，可以用来管理同种组合资源(具有多个实例的同种类资源，如5台打印机)，申请时执行一次P操作，归还时执行一次V操作。三种问题模型：时间关系模型、生产者-消费者模型、读者-写者模型,18,GeneralCase:VARS:semaphore;(initialvalue0),P(S)后动作,先动作V(S),P1:,P2:,时间关系模型,19,生产者-消费者问题模型,ProgramProducer_Consumer;VARS1:semaphore;s1.value:=n;S2:semaphore;s2.value:=0;mutex1,mutex2:semaphore;mutex1.value:=1;mutex2.value:=1;ProcedureProducerBeginRepeat加工一件物品P(S1)P(mutex1)物品放入箱中V(mutex1)V(S2)UntilfalseEnd;,ProcedureConsumerBeginRepeatP(S2)P(mutex2)箱中取一物品V(mutex2)V(S1)消耗这件物品UntilfalseEnd,Begincobeginp1:Producer;pm:Producer;c1:Consumer;cn:Consumercoendend.,20,读者-写者问题模型,Programreaders_writers;Varr_w_w:semaphore;mutex:semaphore;read_count:integer;procedurewriter;beginP(r_w_w);writeopsV(r_w_w)end;,Procedurereader;beginP(mutex);read_count:=read_count+1;Ifread_count=1ThenP(r_w_w);V(mutex);readopsP(mutex);read_count:=read_count-1;Ifread_count=0ThenV(r_w_w);V(mutex);end;,21,beginread_count:=0;r_w_w.value:=1;mutex.value:=1;cobeginr1:reader;rm:reader;w1:writer;.;wn:writercoendend.,22,4.进程通信（1）进程通信的定义进程之间的互斥、同步及信息交换统称进程通讯。(Inter-ProcessCommunication，IPC)。（2）进程通信的模式1）共享内存模式2）信息传递模式,23,第5章死锁,1.死锁的概念死锁是指在多个进程并行执行的过程中，当某进程提出资源申请后，使得若干进程在无外力作用下，永远不能再继续前进的情况。在用信号量作为同步工具时，P、V操作顺序不当也可能产生死锁。2.产生死锁的原因系统资源不足：产生死锁的根本原因在于，为多道程序所共享的系统资源不足，而且，仅当进程提出资源请求时，才会发生死锁。进程推进顺序非法：在多道程序运行时，按照一定的顺序联合推进，可使系统中所有的进程都能运行完毕，我们称这样的推进顺序是合法的。若按某种顺序联合推进，进入某个区域时将导致死锁的发生，则该顺序是非法的。,24,3.产生死锁的必要条件互斥条件：进程对它所需要的资源进行排它性控制，既在一段时间内某资源为一进程所独占。请求和保持条件：进程因请求资源而被阻塞时，对已分配给它的资源保持不放。不剥夺条件:进程所获得的资源在未使用完毕之前，不能被其它进程夺走，即只能由获得该资源的进程自己来释放。环路条件：在发生死锁时，有向图必构成一环路，即前一进程保持着后一进程所需之资源。,25,4.死锁的检测死锁定理：S为死锁状态的充分条件是，当且仅当S状态的资源分配图是不可完全约简的。资源分配图的约简方法：1）找一个非孤立且只有分配边的进程结点，若没有，则算法结束；2）去掉分配边，将其变为孤立结点；3）寻找所有申请边均可满足的进程，将该进程的申请边变为分配边；转1）.算法结束时，若所有结点均为孤立结点，此资源分配图是可完全约简的。,26,27,5.死锁的预防为了预防系统进入死锁状态，应当保证在任何时刻产生死锁的4个必要条件中，至少有一个得不到满足，由此可得到如下几种预防死锁的方法：（1）预先分配法：预分配所有共享资源，即每个作业必须一次请求并获得全部所需之资源。调度程序在该作业所需之资源未满足之前，不将它投入运行。在这种方法中，当一个进程进入运行状态后，将不需再提出其他任何资源要求。这意味着死锁的第二个必要条件不再成立，因而不会产生死锁。（2）有序分配方式：在这种方式中，系统将资源按类型进行线形排队，并赋予不同的序号。所有进程对资源的请求必须严格按照序号递增的资序进行。不难看出，在这种形式的资源分配方式下，所形成的进程资源图不可能再产生环路，因此，死锁的第4个必要条件不再成立，系统不会产生死锁。,28,（6）死锁的避免银行家算法的基本思想是，当一个新进程进入系统时,它必须申明其最大资源需求量,即每个资源类各需多少资源实例。当进程发出资源申请命令而且系统能够满足该请求时,系统将判断:如果分配资源,系统的状态是否为安全的。如是则分配资源,并让申请者继续;否则不分配资源,并让申请者等待。,29,银行家算法例子,p1请求：Request1=(1,0,2),30,ClaimAllocationNeedAvailableWorkFinishABCABCABCABCABC753010743230322302020902302600222211011433002431,P0:p1:p2:p3:p4:,假定分配：,Request1=(1,0,2),31,第6章存储管理,1基本概念（1）存储管理的目的和功能主存储器是中央处理机能直接存取指令和数据的存储器。在计算机系统中，它是一个关键性的资源，能否合理而有效地使用它，在很大程度上反映了操作系统的性能，并直接影响到整个计算机系统的性能。所以，存储管理是目前人们研究操作系统的中心问题之一。存储管理主要功能：存储分配、存储共享、存储保护、存储扩充、地址映射。（2）内存分区静态等长、动态异长（3）内存分配静态等长分区的分配：空闲页面表、空闲页面链、字位映像图动态异长分区的分配：最先适应、最佳适应、最差适应分配算法,32,2页式存储管理（1）实现原理在分页存储管理系统中，把每个作业的地址空间分成一些大小相等的片，并称之为页。同样地，把主存的存储空间也分成大小与页相同的片，这些片称之为存储块，或简称为块。在分配存储空间时，总是以块为单位来分配。一个作业的地址空间可以分配到不相连续的存储块中。分页是由系统通过页表自动完成的。,33,（2）页表的组织页表是用来完成虚地址与物理地址变换的一个重要的数据结构。从地址变换的过程来看，若页表全部放在主存中，则要取一个数据（或一条指令）至少要访问两次主存，一次是访问页表，确定所取数据（或指令）的物理地址，第二次才根据该地址取数据（或指令）。要写入一个数据时情况也是这样。为了提高查表的速度，在地址变换机构中加入了一个高速、小容量的联想存储器，构成一张快表。如果快表命中，只要访问一次主存就可以取出指令或数据。,34,（3）页内零头采用页式管理方式，其主要的优点在于无需移动信息而能够较好地解决分区与管理中产生的存储器“外零头”问题，但引入了“内零头”的问题。内零头是指由于分配给作业的页面是整数块，而一个作业的地址空间不一定是页的整数倍，因而最后一页往往是不满的。在这种情况下，最后一页中空闲的空间不能分配给别的作业，因而造成了浪费。这种浪费称之为“内零头”。内零头的多少与页面大小有关，平均来说，内零头为半页大小。,35,（4）请求页式管理（虚拟页式存储管理）请求页式管理是在分页存储管理的基础上发展起来的。对于一般的页式管理，仍要求一个作业全部装入主存后，才能开始运行。对于请求页式管理，在作业运行之前，不限定把作业的整个空间全部装入主存，而只要求把当前需要的一部分装入主存。这样，从理论上来说系统没有对作业地址空间大小的限制。因此，请求页式存储管理可以实现“扩充”主存的功能。我们称具有这种功能的存储系统为虚拟存储系统。,36,（5）页面置换算法在请求页式系统中，当主存空间业已装满而又需要调入新页时，必须把已在主存中的一些页面淘汰出去。所谓置换算法，就是用来确定应该淘汰哪些页面的一种策略。因为置换算法的优劣，直接影响到系统的效率，因此，在请求页式系统中，一个核心问题是选择合适的页面置换算法。常用的页面置换算法有：先进先出算法、LRU算法、最近不用先淘汰、二次机会算法、时钟算法等。抖动（颠簸）,37,3段式存储管理（1）实现原理：作业分为若干段，且按分段来进行存储分配。实现分段管理的关键在于，如何保证分段（二维）地址空间中一个作业，在线性（一维）的存储空间中正确运行，采用段表来完成二维地址到一维地址的转换。分段管理和分页管理的地址转换过程比较类似，但是它们在概念上完全不同。分页管理的作业地址空间是一个单一的线形地址空间，而分段管理的作业的地址空间是二维的。分页管理中“页”是信息的“物理”单位，大小固定，其分页的活动对于用户是透明的，分段管理中，“段”是信息的“逻辑”单位，既它是有意义的一组信息，其长度不定。分段是用户可见的。,38,（2）分段管理的优点便于程序模块化处理。便于处理变化的数据结构。便于动态链接。便于共享分段。（3）分段管理的缺点处理机要为地址变换花费时间，要为表格提供附加的存储空间，使操作系统复杂。会产生碎片。分段的最大尺寸受到主存可用空间的限制。,39,4段页式存储管理（1）实现原理为了获得分段在逻辑上的优点和分页在管理存储空间方面的优点，兼用分段和分页两种方法，来实现存储管理。这种技术的基本思想是用分段方法来划分进程，每段划分为若干逻辑页，而用分页方法来分配和管理主存（物理存储器）。这样，一方面可以保持分段地址空间所带来的优点，如允许分段动态扩展、可实现分段的动态链接、分段的共享、实施段保护措施等。另一方面，主存分区的拼接问题，辅助存储器的管理以及对分段大小的限制等问题，都可以得到有效的解决。,40,（2）段页式存储管理的优缺点因为段页式存储管理是分段式存储管理和页式存储管理相结合的方案，因而它具有这两者的全部优点。段页式存储管理的主要缺点是，增加了软件复杂性和管理开销，需要的硬件支持也增加了。此外，还有各种表格要占用存储空间，和在请求页式或在分段系统中一样，存在着发生系统抖动的危险，而零头问题和分页管理系统中一样存在，且更为严重。,41,第7章文件管理,1基本概念（1）文件文件是一个具有符号名的在逻辑上具有完整意义的信息项的序列。信息项是构成文件内容的基本单位，是可编址的最小信息项目。（2）文件系统文件系统是指操作系统中与文件管理有关的那部分软件和被管理的文件,以及管理所需要的一些数据结构(如各级目录、索引文件等)的总体。从系统的角度来看,文件系统是对文件存储器的存储空间进行组织、分配，负责文件的存储并对存入的文件进行保护和检索的系统。从用户的角度来看,文件系统主要是实现了“按名存取”。,42,2文件的访问方式顺序存取方式。其中的记录是按序排列的,记录的存取也是按顺序进行的。直接存取方式。用户对记录的存取是不按顺序的,即用户可以直接指定某一记录进行存取。按健存取方式。用户对文件内容的访问不是根据记录的编号或地址,而是根据记录的某项内容(键)来进行的。3文件的逻辑组织文件的逻辑组织是指从用户角度看到的文件，也就是文件的记录结构。流式文件、记录式文件。,43,4文件的物理组织文件的物理组织是指从系统角度看到的文件,也就是文件在文件存储器上的安排。文件的物理组织一般有4种形式：连续区分配(连续文件),即把一个在逻辑上连续的记录构成的文件分配到连续的物理块中。链接块方式(串联文件),即文件所分配的物理块可以是不连续的,而且也不必顺序排列。文件的物理块之间用链表连接在一起。索引式(索引文件),即为每个文件建立一个索引表,其中每一个表项指出文件记录所在的物理块号。Hash文件,即对文件的每个记录的物理地址采用Hash的方法计算出来,从而