[电脑基础知识]操作系统汇总材料8份

操作系统的地位,计算机系统由硬件和软件组成操作系统在硬件基础上的第一层软件是其它软件和硬件的接口,期末复习,计算机操作系统原理,1.操作系统的目标,1有效性(1) 提高系统资源利用率：使CPU和I/O设备由于能保持忙碌状态而得到有效的利用，且可使内存和外存中存放的数据因有序而节省了存储空间。(2) 提高系统的吞吐量：操作系统还可以通过合理地组织计算机的工作流程，而进一步改善资源的利用率，加速程序的运行，缩短程序的运行周期，从而提高系统的吞吐量。2方便性:配置OS后可使计算机系统更容易使用。3可扩充性:便于方便地增加新的功能和模块，并能修改老的功能和模块。4开放性:能遵循世界标准规范，特别是遵循开放系统互连(OSI)国际标准。凡遵循国际标准所开发的硬件和软件，均能彼此兼容，可方便地实现互连。,2. 操作系统的作用,OS作为用户与计算机硬件系统之间的接口用户在OS帮助下，能够方便、快捷、安全、可靠地操纵计算机硬件和运行自己的程序。OS作为计算机系统资源的管理者:实现资源共享,提高资源利用率处理机管理，用于分配和控制处理机；存储器管理，主要负责内存的分配与回收； I/O设备管理，负责I/O设备的分配与操纵；文件管理，负责文件的存取、共享和保护OS实现了对计算机资源的抽象OS是铺设在计算机硬件上的多层系统软件，它们不仅增强了系统的功能，而且还隐藏了对硬件操作的细节，由它们实现了对计算机硬件操作的多个层次的抽象。,3. 推动操作系统发展的主要动力,不断提高计算机资源的利用率方便用户器件的不断更新换代计算机体系结构的不断发展,4. 操作系统的发展过程,无操作系统的计算机系统单道批处理系统多道批处理系统分时系统实时系统微机操作系统的发展,5.OS中引入多道程序设计技术可带来以下好处：,(1) 提高CPU的利用率。(2) 可提高内存和I/O设备利用率。(3) 增加系统吞吐量。,6.多道批处理系统的主要优缺点,(1) 资源利用率高。由于在内存中驻留了多道程序，它们共享资源，可保持资源处于忙碌状态，从而使各种资源得以充分利用。(2) 系统吞吐量大。系统吞吐量是指系统在单位时间内所完成的总工作量。能提高系统吞吐量的主要原因可归结为：第一，CPU和其它资源保持“忙碌”状态； 第二，仅当作业完成时或运行不下去时才进行切换，系统开销小。(3) 平均周转时间长。作业的周转时间是指从作业进入系统开始，直至其完成并退出系统为止所经历的时间。在批处理系统中，由于作业要排队，依次进行处理，因而作业的周转时间较长，通常需几个小时，甚至几天。(4) 无交互能力。用户一旦把作业提交给系统后，直至作业完成，用户都不能与自己的作业进行交互，一旦发现作业错误不能及时改正，这对修改和调试程序是极不方便的。所以适用于成熟的程序。,7分时系统的特征,分时系统与多道批处理系统相比，具有非常明显的不同特征，可以归纳成以下四个特点：(1) 多路性。允许在一台主机上同时联接多台联机终端，系统按分时原则为每个用户服务。宏观上，是多个用户同时工作，共享系统资源；而微观上，则是每个用户作业轮流运行一个时间片。多路性即同时性，它提高了资源利用率，降低了使用费用，从而促进了计算机更广泛的应用。 (2) 独立性。每个用户各占一个终端，彼此独立操作，互不干扰。因此，用户所感觉到的，就像是他一人独占主机。(3) 及时性。用户的请求能在很短的时间内获得响应。此时间间隔是以人们所能接受的等待时间来确定的，通常仅为13秒钟。(4) 交互性。用户可通过终端与系统进行广泛的人机对话。其广泛性表现在：用户可以请求系统提供多方面的服务，如文件编辑、数据处理和资源共享等。,8.操作系统的基本特性,并发性 共享性 虚拟技术 异步性,9.操作系统的主要功能,处理机管理功能进程控制、进程同步、进程通信、调度存储器管理功能内存分配、内存保护、地址映射、内存扩充设备管理功能缓冲管理、设备分配、设备处理文件管理功能文件存储空间的管理、目录管理、文件的读/写管理和保护操作系统与用户之间的接口 用户接口。它是提供给用户使用的接口，用户可通过该接口取得操作系统的服务；程序接口。它是提供给程序员在编程时使用的接口，是用户程序取得操作系统服务的惟一途径。,第二章进程管理,2.1进程的基本概念2.2进程控制2.3 进程同步 2.4 经典进程的同步问题2.5 进程通信 2.6 线程,1.根据语句画前驱图,对于具有下述四条语句的程序段：S1: a:=x+2S2: b:=y+4S3: c:=a+bS4: d:=c+b P81:2,图 2-4四条语句的前趋关系,2程序并发执行时的特征,程序并发执行，提高了系统吞吐量，但产生了与顺序执行不同的特征：1) 间断性：程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。相互制约将导致并发程序具有“执行暂停执行”这种间断性的活动规律。2) 失去封闭性：程序在并发执行时，是多个程序共享系统中的各种资源（软件资源和硬件资源），因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。这样，某程序在执行时，必然会受到其它程序的影响。3) 不可再现性：上述情况说明，程序在并发执行时，由于失去了封闭性，其计算结果已与并发程序的执行速度有关，从而使程序的执行失去了可再现性，亦即，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。,3.进程的特征,1.结构特征：从结构上看，进程的实体是由一个程序段和相应的数据集，以及一个PCB三部分组成。 2.动态特征：表现在，因创建而产生，由调度而执行，因得不到资源而暂停，由撤消而消亡。可见，进程有一定的生命周期。 3.并发特征：引入进程的目的就是为了能使程序并发执行，以提高资源利用率。 4.独立特征：进程是一个能独立运行的单位，也是系统进行资源分配和调度的一个独立单位 5.异步特征：进程按照各自独立的，不可预知的速度向前推进。所以要求系统为它们提供某些设施，使进程之间能协调操作和共享资源。,4. 进程的三种基本状态,进程执行时的间断性决定了进程可能具有多种状态。事实上，运行中的进程可能具有以下三种基本状态。1) 就绪(Ready)状态当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。,2) 执行状态进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态； 在多处理机系统中，则有多个进程处于执行状态。3) 阻塞状态正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。致使进程阻塞的典型事件有：请求I/O，申请缓冲空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。,5.进程状态的转换,进程的状态反映进程执行过程的变化。这些状态随着进程的自身的推进和外界条件的变化而改变。,就绪,运行,阻塞,图2-5 进程的三种基本状态及其转换,6进程控制块的作用,进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。OS是根据PCB来对并发执行的进程进行控制和管理的。,7进程的创建步骤,一旦操作系统发现了要求创建新进程的事件后，便调用进程创建原语Creat( )按下述步骤创建一个新进程。(1) 申请空白PCB。为新进程申请获得惟一的数字标识符，并从PCB集合中索取一个空白PCB。(2) 为新进程分配资源。为新进程的程序和数据以及用户栈分配必要的内存空间。显然，此时操作系统必须知道新进程所需内存的大小。对于批处理作业，其大小可在用户提出创建进程要求时提供。若是为应用进程创建子进程，也应是在该进程提出创建进程的请求中给出所需内存的大小。对于交互型作业，用户可以不给出内存要求而由系统分配一定的空间。如果新进程要共享某个已在内存的地址空间(即已装入内存的共享段)，则必须建立相应的链接。,(3) 初始化进程控制块。PCB的初始化包括： 初始化标识信息，将系统分配的标识符和父进程标识符填入新PCB中； 初始化处理机状态信息，使程序计数器指向程序的入口地址，使栈指针指向栈顶； 初始化处理机控制信息，将进程的状态设置为就绪状态或静止就绪状态，对于优先级，通常是将它设置为最低优先级，除非用户以显式方式提出高优先级要求。(4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。,8进程的终止过程,如果系统中发生了上述要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止指定的进程。(1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防它们成为不可控的进程。(4) 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5) 将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。,9同步机制应遵循的规则,为实现进程互斥地进入自已的临界区，可用软件方法，更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则：(1) 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。 (2) 忙则等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。 (3) 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。(4) 让权等待。,10. 信号量机制,1整型信号量 2记录型信号量3AND型信号量 4信号量集,procedure wait(S)var S：semaphore；beginS.value:=S.value-1；if S.value0 then block(S.L)；end,procedure signal(S)var S: semaphore；beginS.value:=S.value+1；if S.value=0 then wakeup(S.L)；end,11. 记录型信号量数据结构描述以及wait(S)和signal(S)操作描述：,type semaphore=recordvalue: integer；L: list of process；end,Var a,b,c,d,e,f,g：semaphore: =0,0,0,0,0,0,0；beginparbeginbegin S1； signal(a)； signal(b)； end；begin wait(a)； S2； signal(c)； signal(d)； end；begin wait(b)； S3； signal(e)； end；begin wait(c)； S4； signal(f)； end；begin wait(d)； S5； signal(g)； end；begin wait(e)； wait(f)； wait(g)； S6； end；parendend,12利用信号量实现前趋关系,P82:22,13管程的定义和组成,代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，我们称之为管程。由上述的定义可知，管程由四部分组成： 管程的名称； 局部于管程内部的共享数据结构说明； 对该数据结构进行操作的一组过程； 对局部于管程内部的共享数据设置初始值的语句。,14利用记录型信号量解决生产者消费者问题,假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex：实现诸进程对缓冲池的互斥使用。同步信号量empty和full：分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者消费者问题可描述如下:,var mutex,empty,full: semaphore:=1,n,0； buffer:array0,n-1 of item； in，out: integer:=0，0； begin parbegin proceducer: . consumer: .end,proceducer: beginrepeat producer an item nextp； wait(empty)； wait(mutex)； buffer(in):=nextp； in:=(in+1) mod n； signal(mutex)； signal(full)； until false；end,consumer: begin repeat wait(full)； wait(mutex)； nextc:=buffer(out)； out:=(out+1) mod n； signal(mutex)； signal(empty)； consumer the item in nextc； until false； end,思考：P82:23,24,25,28,15利用记录型信号量解决哲学家进餐问题,经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下： Var chopstick: array0，4 of semaphore；所有信号量均被初始化为1,在以上描述中，当哲学家饥饿时，总是先去拿他左边的筷子，即执行wait(chopsticki)； 成功后，再去拿他右边的筷子，即执行wait(chopstick(i+1)mod 5)；又成功后便可进餐。进餐完毕，又先放下他左边的筷子，然后再放右边的筷子。虽然，上述解法可保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0； 当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。,哲学家问题的死锁解决方法：,(1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。,16.读者-写者问题,一个数据文件或记录，可被多个进程共享。把只要求读该文件的进程称为“Reader进程”，其他进程称为“Writer进程”。允许多个进程同时读一个共享对象，但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。读者-写者问题常用来测试新同步原语。,利用记录型信号量解决读者写者问题,为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Readcount=0，表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若Wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，也应该为它设置一个互斥信号量rmutex。,Var rmutex，wmutex: semaphore:=1,1； readcount: integer:=0； begin parbeginReader: begin repeat wait(rmutex)； if readcount=0 then wait(wmutex)； readcount:=readcount+1； signal(rmutex)； perform read operation； wait(rmutex)； readcount:=readcount-1； if readcount=0 then signal(wmutex)；signal(rmutex)；until false；end,17.进程通信的类型,1共享存储器系统2消息传递系统3管道通信,18.消息传递通信的实现方法,1直接通信方式：这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)：Send(Receiver，message)； 发送一个消息给接收进程；Receive(Sender，message)； 接收Sender发来的消息；2间接通信方式：间接通信方式指进程之间的通信需要通过作为共享数据结构的实体。该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。通常把这种中间实体称为信箱。消息在信箱中可以安全地保存，只允许核准的目标用户随时读取。因此，利用信箱通信方式，既可实现实时通信，又可实现非实时通信。系统为信箱通信提供了若干条原语，分别用于信箱的创建、撤消和消息的发送、接收等。,19.信箱分类,信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。1) 私用信箱用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。当拥有该信箱的进程结束时，信箱也随之消失。2) 公用信箱它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。3）共享信箱由某进程创建，在创建时或创建后指明它是可共享的，同时须指明可共享进程的名字。信箱的拥有者和共享者都有权从信箱中取走发送给自己的消息。,20线程的引入,在操作系统中引入进程的目的，是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。但是，由于进程是一个资源的拥有者，因而在创建、撤消和切换中，系统必须为之付出较大的时空开销。正因如此，在系统中所设置的进程，其数目不宜过多，进程切换的频率也不宜过高，这也就限制了并发程度的进一步提高。在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。,21线程与进程的比较,1) 调度：在传统的操作系统中，作为拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位，把传统进程的两个属性分开，使线程基本上不拥有资源，这样线程便能轻装前进，从而可显著地提高系统的并发程度。2) 并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，使得操作系统具有更好的并发性，从而能更加有效地提高系统资源的利用率和系统的吞吐量。3) 拥有资源：不论是传统的操作系统，还是引入了线程的操作系统，进程都可以拥有资源，是系统中拥有资源的一个基本单位。一般而言，线程自己不拥有系统资源(也有一点必不可少的资源)，但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，如已打开的文件、I/O设备等，可以供该进程中的所有线程所共享。4) 系统开销：在创建或撤消进程时，系统都要为之创建和回收进程控制块，分配或回收资源，如内存空间和I/O设备等，操作系统所付出的开销明显大于线程创建或撤消时的开销。类似地，在进程切换时，涉及到当前进程CPU环境的保存及新被调度运行进程的CPU环境的设置，而线程的切换则仅需保存和设置少量寄存器内容，不涉及存储器管理方面的操作，所以就切换代价而言，进程也是远高于线程的。,第三章处理机调度与死锁,3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法3.4 实时调度 3.5 产生死锁的原因和必要条件3.6 预防死锁的方法3.7 死锁的检测与解除,1.处理机调度的层次及频率,三种调度：高级调度（作业调度）、低级调度（进程调度）、中级调度在上述三种调度中，进程调度的运行频率最高，在分时系统中通常是10100 ms便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的CPU时间，进程调度算法不宜太复杂。作业调度往往是发生在一个(批)作业运行完毕，退出系统，而需要重新调入一个(批)作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。,2一个典型的作业可分成三个作业步：, “编译”作业步，通过执行编译程序对源程序进行编译，产生若干个目标程序段； “连结装配”作业步，将“编译”作业步所产生的若干个目标程序段装配成可执行的目标程序； “运行”作业步，将可执行的目标程序读入内存并控制其运行。,3低级调度的功能,低级调度用于决定就绪队列中的哪个进程(或内核级线程，为叙述方便，以后只写进程)应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。低级调度的主要功能如下： (1) 保存处理机的现场信息。在进程调度进行调度时，首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制块(PCB)中的相应单元。(2) 按某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。 (3) 把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。,4进程调度方式,1) 非抢占方式：在采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，都一直让它运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配给它的处理机。直至该进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。2) 抢占方式：这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。,5.抢占调度方式是基于一定原则,抢占调度方式是基于一定原则的，主要有如下几条：(1) 优先权原则。通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行(当前)的进程，将处理机分配给优先权高的新到的进程，使之执行；或者说，允许优先权高的新到进程抢占当前进程的处理机。(2) 短作业(进程)优先原则。当新到达的作业(进程)比正在执行的作业(进程)明显的短时，将暂停当前长作业(进程)的执行，将处理机分配给新到的短作业(进程)，使之优先执行； 或者说，短作业(进程)可以抢占当前较长作业(进程)的处理机。(3) 时间片原则。各进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数的实时系统，以及要求较高的批处理系统。,6.选择调度方式和调度算法的若干准则,面向用户的准则：(1) 周转时间短。(2) 响应时间快。(3) 截止时间的保证。(4) 优先权准则。面向系统的准则(1) 系统吞吐量高。(2) 处理机利用率好。(3) 各类资源的平衡利用。,7.调 度 算 法,先来先服务短作业(进程)优先调度算法高优先权优先调度算法基于时间片的轮转调度算法,计算各作业（或进程）的完成时间、周转时间、带权周转时间以及平均时间。练习,FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。,图3-4FCFS和SJF调度算法的性能,8.FCFS调度算法特点,据此可知，FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业(进程)。CPU繁忙型作业是指该类作业需要大量的CPU时间进行计算，而很少请求I/O。通常的科学计算便属于CPU繁忙型作业。I/O繁忙型作业是指CPU进行处理时需频繁地请求I/O。目前的大多数事务处理都属于I/O繁忙型作业。,9.SJ(P)F调度算法也存在不容忽视的缺点：,(1) 该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,由上式可以看出：(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。,10高响应比优先调度算法中响应比及分析,11.实现实时调度的基本条件,提供必要的信息：(1) 就绪时间。这是该任务成为就绪状态的起始时间，在周期任务的情况下，它就是事先预知的一串时间序列；而在非周期任务的情况下，它也可能是预知的。(2) 开始截止时间和完成截止时间。对于典型的实时应用，只须知道开始截止时间，或者知道完成截止时间。(3) 处理时间。这是指一个任务从开始执行直至完成所需的时间。在某些情况下，该时间也是系统提供的。(4) 资源要求。这是指任务执行时所需的一组资源。(5) 优先级。系统处理能力强采用抢占式调度机制具有快速切换机制：(1) 对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。(2) 快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当地小，以减少任务切换的时间开销。,12.常用的几种实时调度算法,1最早截止时间优先即EDF(Earliest Deadline First)算法2最低松弛度优先即LLF(Least Laxity First)算法,13. 产生死锁的原因,产生死锁的原因可归结为如下两点：(1) 竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。(2) 进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。,14.产生死锁的必要条件,虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。综上所述不难看出，死锁的发生必须具备下列四个必要条件。(1) 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。(2) 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。(3) 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。(4) 环路等待条件：指在发生死锁时，必然存在一个进程资源的环形链，即进程集合P0，P1，P2，Pn中的P0正在等待一个P1占用的资源； P1正在等待P2占用的资源，Pn正在等待已被P0占用的资源。,15. 处理死锁的基本方法,(1) 预防死锁：该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。(2) 避免死锁：它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。(3) 检测死锁：这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源； 然后，采取适当措施，从系统中将已发生的死锁清除掉。 (4) 解除死锁：这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。,16安全状态,所谓安全状态，是指系统能按某种进程顺序(P1，P2，Pn)(称P1，P2，Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,安全状态之例,我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：,由安全状态向不安全状态的转换,如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为此时也无法再找到一个安全序列，,17.利用银行家算法避免死锁,假定系统中有五个进程P0，P1，P2，P3，P4和三类资源A，B，C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-16所示。,图3-16 T0时刻的资源分配表,图3-17T0时刻的安全序列,(1) T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(见图 3-17所示)可知，在T0时刻存在着一个安全序列P1，P3，P4，P2，P0，故系统是安全的。,(2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1，0，2)Need1(1，2，2) Request1(1，0，2)Available1(3，3，2) 系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，由此形成的资源变化情况如图3-16中的圆括号所示。, 再利用安全性算法检查此时系统是否安全。如图3-18所示。,图3-18P1申请资源时的安全性检查,(3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3，3，0)Need4(4，3，1)； Request4(3，3，0)Available(2，3，0)，让P4等待。(4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0，2，0)Need0(7，4，3)； Request0(0，2，0)Available(2，3，0)； 系统暂时先假定可为P0分配资源，并修改有关数据，如图3-19所示。,(5) 进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。如果在银行家算法中，把P0发出的请求向量改为Request0(0，1，0)，系统是否能将资源分配给它，请读者考虑。,图3-19为P0分配资源后的有关资源数据,P115:21,22,第四章存储器管理,4.1 存储器的层次结构 4.2程序的装入和链接 4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,1.通用计算机而言，存储层次至少应具有三级：,对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。,2. 程序的装入方式,绝对装入方式：装入模块被装入内存后，程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。可重定位装入方式（静态重定位）：根据装配模块将要装入内存的起始地址对程序中使用的指令地址和数据地址进行修改，将其转换为实际的物理地址。地址变换是在装入时一次完成的，以后不再改变。 动态运行时装入方式（动态重定位）：动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是推迟到程序真正要执行时才进行。,3. 连续分配方式,单一连续分配固定分区分配动态分区分配（重点）伙伴系统哈希算法可重定位分区分配对换,可变式分区示例,在系统初启时，内存中除了操作系统常驻部分之外，只有一个空闲分区。,随着作业的撤离和再装入，原来连续的内存空闲区变成了分散的碎片。,4分区分配算法,1) 首次适应算法2) 循环首次适应算法3) 最佳适应算法4) 最坏适应算法5) 快速适应算法,1) 首次适应算法(first fit),我们以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。该算法优点：优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。,首次适应算法的空闲分区链,2) 循环首次适应算法(next fit),该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法优点：能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，缺点：会缺乏大的空闲分区。,3) 最佳适应算法(best fit),所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。,最佳适应算法的空闲分区链,4) 最坏适应算法(worst fit),最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。但是该算法的缺点也是明显的，它会使存储器中缺乏大的空闲分区。最坏适应算法与前面所述的首次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。,最坏适应算法的空闲分区链,5.动态分区内存回收,当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：(1) 回收区与插入点的前一个F1空闲分区相邻。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。,(2) 回收分区与插入点的后一F2空闲分区相邻接。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。,(3) 回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。,(4) 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。,外碎片,相邻空闲合并,练习,采用可变分区方式管理主存空间时，若主存中按地址顺序依次有五个空闲区，空闲区的大小分别为15K，28K，10K，226K，110K，现有五个作业Ja，Jb，Jc，作业Jd和Je，它们所需的主存依次为10K、15K，l02K，2K和80K，如果采用最先适应分配算法、最佳适应、最坏适应算法分别画出对应的内存分布图?,系统现有可用空间为512K，可用空间的起始地址为25K，现有作业序列如下；1）作业1申请16K；作业2申请100K；作业3申请140K；作业4申请26K2）作业2完成；作业4完成3）作业5申请25K用可变分区的最先、最佳最坏适应算法处理上述作业序列，分别画出三个步骤对应的内存分布图。,6. 分区式分配的评价,主要优点实现了多道程序共享主存空间，更有效地利用了处理机和I/O设备，从而使系统的吞吐量和作业周转时间得到了相应的改善。并且可变式分区的主存利用率比固定式分区高，可重定位式分区则更高。相对于后面介绍的存储管理方式，为实现分区分配所使用的表格较少、占用的存储空间相对较少，算法也相对简单。实现存储保护的措施也比较简单。多重分区分配方案便于实现对子程序、 数据段的共享。,分区式分配的主要缺点,主存仍不能充分利用，除了可再定位式分区法外，都存在着严重的碎片问题。另外，即使不把存储器分碎，整个空白区也可能因容纳不下一个作业而造成浪费。 不能实现对主存的扩充。 因此， 作业的大小受到主存可用空间的限制。要求一个作业在执行之前必须全部装入主存，因此在主存中可能包含从未使用过的信息。可重定位分区分配虽然能解决碎片问题，但拼接时需移动大量信息，从而损失了处理机时间。除多重分区外，几个作业之间不能共享存入主存的信息。,7.分页存储管理的基本思想,将作业的地址空间等分成大小相等的页面；再将内存空间等分成同样大小的块。这样当页面装入内存块时，就不会出现碎片，从而提高了内存的利用率。通常，每个页长大约为14K，经过页面划分之后，进程的虚地址变为页号P与页内地址W所组成。,8分页地址中的地址结构,分页地址中的地址结构如下：,它含有两部分：前一部分为页号P，后一部分为位移量W(或称为页内地址)。图中的地址长度为32位，其中011位为页内地址，即每页的大小为4 KB；1231位为页号，地址空间最多允许有1 M页。,对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：其中，INT是整除函数，MOD是取余函数。例如，其系统的页面大小为1 KB，设A = 2170 B，则由上式可以求得P = 2，d = 122。,9.页式管理的地址变换过程,设每个页面长度为lK，指令MOV R,2500的逻辑地址为100,10具有快表的地址变换变换过程,为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表”，