计算机软件技术基础_操作系统.ppt

1、吴正平,第五章操作系统5.1概论5.2处理机管理(进程管理)5.3存储管理5.4设备管理5.5文件管理5.6作业管理与用户界面5.7常见的操作系统,吴正平,5.1概论计算机系统:由硬件和软件两部分组成。硬件部分：指计算机物理装置本身(裸机)，即各种处理机、存储器、输入/输出设备和通讯装置。软件部分：各种程序。计算机系统中的软件一般分为系统软件和应用软件。系统软件：用于计算机的管理、维护、控制和运行，其中最重要的是操作系统。应用软件：是指用户为了解决某一特定问题而编制的程序。操作系统是对硬件的首次扩充。操作系统已成为现代计算机系统中必不可少的系统关键组成部分。,吴正平,5.1.1操作系统的基本概

2、念CPU是计算机硬件的核心和基础-心脏。操作系统是软件的核心和基础-大脑。操作系统控制和管理计算机所有的系统硬件和软件。计算机系统通常分为四个层次:,操作系统是加在裸机上的第一层软件。它是对裸机功能的首次扩充。从结构看，操作系统是用户程序及系统软件与物理计算机之间的接口。,吴正平,对操作系统的描述一般有以下二种观点：一是虚拟机的观点:把硬件全部隐藏起来，给用户提供一个友好的、易于操作的界面。操作系统的虚拟扩展功能体现在二个方面:一是系统功能的扩展：操作系统提供了系统调用，扩展了裸机的基本指令系统，组成了虚拟机的高级指令系统。二是数量上的扩展：使多个用户可以同时使用一台机器.二是资源管理的观点:

3、操作系统管理计算机资源，并提供一个有序的和可控的分配，使各种资源得到充分的使用和方便用户。总之，操作系统是一种系统软件，由它来统一管理系统的资源和控制程序的执行，是所有其它软件运行的基础，是用户使用计算机的接口。,吴正平,5.1.2操作系统的特征和功能由于多道程序系统出现，使处理机与输入/输出以及其它资源得到充分利用，但也由此带来不少新的复杂问题。因此，一般支持多道程序的操作系统具有并发执行、共享、虚拟技术等一些明显的特征。1.操作系统的特征(1)迸发性所谓并发，指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内，宏观上有多个程序在同时运行，但在单CPU系统中，每一

4、时刻却仅能有一道程序执行，故微观上这些程序只能分时地交替执行。并发和并行是两个不同的概念，并行是一种物理的或微观的同时性概念，而并发是一种逻辑的或宏观上的同时性概念。,吴正平,(2）共享性即多个用户、多道程序同时使用某个有限的系统资源。共享性是多道程序计算机系统的一个最大特点，是操作系统所追求的主要目标之一。“并发”和“共享”是操作系统的两个最基本特征，它们互为存在条件，即资源共享是以程序的并发执行为存在条件，没有并发执行，就不可能有共享；反之，若不能很好地实现共享，则程序的并发执行必将受到影响。,吴正平,(3）虚拟技术虚拟技术的目的在于向用户提供一个方便、高效、易于使用的操作系统。所谓“虚拟

5、”，就是把物理实体映射为一个或者多个逻辑实体。物理实体是实际存在的，而逻辑实体则是“虚拟”的，只是用户的一种看法和感觉。例如，在多道分时系统中，虽然只有一个CPU，但每一个终端用户却都认为是有一个CPU专门为他服务。SPOOLing(外围设备同时联机操作)也采用了虚拟技术,它把一个物理上的输入输出(I/O)设备映射成多个逻辑上的输入输出(I/O)设备。典型的例子是共享打印机。,吴正平,2.操作系统的功能要点操作系统的功能要点：系统资源的管理。操作系统的主要功能是使各种系统资源得到充分的、合理的使用，及提供良好的用户界面。为了解决用户作业因争夺资源而产生的矛盾和使多道程序有条不紊地运行，操作系统

6、应具有以下五个功能：(1)处理机管理：主要解决在多道程序并发执行时如何合理分配处理机(2)存储器管理：使有限的内存尽可能装入多的作业。(3)设备管理：进行设备分配和具体的输入、输出。(4)文件管理：外存空间管理及文件按名存取。(5)作业管理：提供良好的用户接口。,吴正平,5.1.3操作系统的发展计算机初创时：这一阶段没有操作系统,采用人工操作方式。50年代中期：用监控程序来管理用户所提交的程序，这种自动定序的处理方式称为“批处理”方式，而且是串行执行作业，因此称为单道批处理。60年代中后期：允许多个程序同时存在于内存中，由处理机以切换的方式使多个程序可以同时运行。这时，管理程序已经迅速地发展成

7、为一个重要的软件分支-操作系统。80年代中期：通过通信系统，把地理上分散的计算机群和工作站设备联结起来，达到数据通信和资源共享的目的，发展成了网络操作系统。操作系统进一步发展：随着计算机硬件技术的飞速发展、微处理机的出现和发展，出现了分布式操作系统，分布式操作系统是由多个相互连接的处理资源组成的计算机系统，它们在整个系统的控制下可合作执行一个共同任务，最少依赖于集中的程序、数据或硬件。这些资源可以是物理上相邻的，也可以是在地理上分散的。21世纪将是分布式系统的时代。,吴正平,5.1.4操作系统的分类,从操作系统工作的角度简介几种主要的操作系统。1.批处理操作系统批处理:是指用户作业的成批输入并

8、处理;即系统将作业成批地输入系统并暂存在外存中，组成一个后备作业队列，每次按一定的调度原则从后备作业中挑选一个或多个装入主机处理，作业完成后退出主机和后备作业装入主机运行均由系统自动实现。批处理操作系统的目的：是减少人工操作、减少作业建立和结束过程的时间浪费。优点：是系统的吞吐量大，资源利用率高，系统开销较小。缺点：用户在其作业运行期间不能控制其作业的运行过程。同时在作业输入和输出过程中，CPU处于等待状态。主要配置在大型计算机操作系统上，希望有作业的大呑吐量，以便充分利用系统资源。,吴正平,多道程序技术的目的：是在于充分利用处理机，减少处理机等待时间。采用的方法:将内存分成多个分区,每个分区

9、放一道作业,当一个作业处于等待I/O资源时,其他作业则使用CPU。多道程序技术给操作系统带来了如下复杂性：(1)多用户作业共享CPU和输入/输出设备，操作系统要解决各道程序之间的同步、互斥和死锁问题；(2)要有较大容量的存储器，以便尽可能多的装入用户作业，又必须防止各道程序之间的交叉和冲突，及有意无意地破坏；(3)必须有高效、可靠和方便的文件系统，能有效地管理文件。(4)无交互能力,出现故障无法及时排除。,吴正平,2分时操作系统所谓“分时”：就是多个用户对系统资源进行时间上的分享。分时系统中主机是一台功能强大的计算机，连接多个终端，主机采用时间分片的方式轮流地为各终端上的用户服务。对每个用户而

10、言，都仿佛“独占”了整个计算机系统。分时系统的基本特征是：(1)多路性：系统按时间分片的原则为每个终端服务。宏观上，多个用户通过终端同时工作，共享资源；微观上，各终端作业轮流在时间片内进行处理。(2)独立性：每个用户的感觉自已好象独占着计算机系统。(3)及时性：系统对每一用户的输入请求能作出及时的响应。(4)交互性：用户通过终端采用人-机会话的方式直接控制程序运行。最早的分时系统是美国麻省理工学院在1963年研制的CTSS,用于IBM7904机。IBM公司于1968年推出的TSS/360也是一个成功的分时系统。目前最流行的分时操作系统为UNIX。,吴正平,3实时操作系统所谓“实时”是表示“及时

11、”的意思。实时系统又分为实时控制系统和实时信息系统(航空定票系统、情报检索系统、信息查询系统等。)二种。实时系统的特征是：（1）简单的交互能力（2）实时响应（3）高可靠性。实时系统与分时系统之间的主要区别在于：实时系统一般是专用的，其交互能力比较差，只允许用户访问数量有限的专用程序，但系统响应时间要求极高。分时系统具有很强的通用性，有很强的交互功能，但响应时间可以稍长，以不超过用户的忍受范围为限。批处理系统、分时系统和实时系统是操作系统的三个基本类型。而一个实用的操作系统可以是分别独立的一种系统，也可以是两两结合的或是三者兼而有之的通用操作系统。,吴正平,4网络操作系统计算机网络是地域位置不同

12、，具有独立功能的多台计算机系统，通过通信线路与设备彼此互连，在网络系统软件的支持下，实现更广泛的硬件资源、软件资源及信息资源的共享。网络操作系统除了具有基本类型操作系统中所应具备的管理功能和服务功能外，还具有网络管理和服务功能，这主要包括：（1）网络资源共享（2）网络通信（3）作业迁移。5分布式操作系统分布式操作系统也是通过通信网络将物理上分布的具有自治功能的数据处理系统或计算机系统互连起来，实现信息交换和资源共享、协作完成任务。分布式系统要求一个统一的操作系统，实现系统操作的统一性。分布式操作系统管理分布式系统中的所有资源，负责全系统的资源分配和调度、任务划分、信息传输、控制协调等，并为用户

13、提供一个统一的界面。分布式操作系统是当今操作系统发展的一个重要方向。,吴正平,6嵌入式操作系统和智能卡操作系统嵌入式操作系统是一种小型操作系统,主要用于掌上电脑或PDA设备,例如PalmOS和WindowCE等。,吴正平,5.2处理机管理（进程管理）在操作系统中处理机的管理被归结为进程管理。进程是操作系统分配资源及运行调度的基本单位。进程管理的任务是：协调各进程之间的运行活动；为各进程合理分配资源；为进程提供各种系统服务；使所有的进程都能够正确而有效地运行。5.2.1进程与线程进程(process)的引入：在单道程序系统中，一个复杂的程序可以分为若干个程序段，它们必须依某种次序逐次执行，且运行

14、时独占整个计算机资源。它的缺点是系统的资源利用率很低。,吴正平,例:有三道程序在一个系统中运行，该系统有输入设备，输出设备各一台。三道程序构成如下:A:输入32秒，计算8秒，输出5秒。共计45秒。B:输入21秒，计算14秒，输出35秒。共计70秒。C:输入12秒，计算32秒，输出15秒。共计59秒。若程序按A-B-C的次序顺序执行，则系统运行时间为45+70+59=174秒。若使各设备并发执行，也按A-B-C顺序执行，则执行情况为：,总计执行时间:32+21+14+35+15=114秒,吴正平,并发执行提高了系统吞吐量，但也产生了下述一些新问题:由于并发性和共享性，并发程序之间常常相互依赖，彼

15、此制约。这时程序已不能很好地描述并发性问题，引进了进程。1.进程为了能对并发程序的执行加以描述而引入了进程的概念。进程可以定义为：一个可并发执行的程序在其数据集上的一次运行活动。,吴正平,进程的基本特征,动态性：进程实质上是程序的一次执行过程。并发性：多个进程能在一段时间内同时运行。独立性：进程是一个能独立运行、独立分配资源和独立调度的基本单位。异步性：每个进程按各自独立的,不可预知的速度向前推进。操作系统必须提供某种机制来协调进程。,吴正平,2.进程的实质（进程的实体）进程的实体由程序、数据集合、进程控制块PCB(ProcessControlBlock)及相应表格组成。3.线程线程是处理机调

16、度的独立单位.更好描述多机上进程的并发处理.线程是进程中可独立执行的子程序，一个进程中可以有多个线程，每个线程用唯一的标识符进行标识。线程可以并发执行，它们之间的切换比进程之间的切换快得多，所以线程又称为“轻型进程”。线程和进程的根本区别在于进程是系统作为资源分配的单位，而线程是处理机进行调度和执行的单位。每个进程都有自已的内存空间，同一进程的各线程可共享该进程的内存空间，并且该进程中所有线程对进程的整个内存空间都有存取权限。目前，Mach、WindowsNT、Windows2000等操作系统都已有管理线程的机制。,吴正平,5.2.2进程的状态与转换,进程状态是指进程的当前行为。由于进程运行的

17、间断性,决定了进程至少具有三种状态。最基本的代表进程生命周期的状态有:就绪、运行、阻塞。,(1)就绪状态(ready)当进程已经获得除CPU之外的所有运行必要资源。(2)执行状态(runing)指进程已经获得处理机,其程序正在执行。(3)阻塞状态(block)进程因发生某事件(如请求I/O。申请缓冲空间等)而暂停执行的状态,吴正平,就绪、执行、阻塞是进程的三种基本状态。执行态进程是物理运行，就诸态和阻塞状进程是逻辑运行，宏观上，它们都是活动的（即都处在运行之中）。进程在某个时刻总是处于某种状态，随着其自身的推进和外界条件的变化，进程的状态也随之而变。状态之间的转换为进程控制。就绪状态-执行状态

18、:进程调度程序为之分配了处理机.执行状态-就绪状态:因时间片已用完而被暂停执行时.执行状态-阻塞状态:等待某事件发生而使进程的执行受阻.阻塞状态-就绪状态:等待事件发生了.说明:1.就绪进程有多个，形成就绪队列。2.进程调度是从就绪队列中挑选进程分配CPU。3.进程在阻塞结束后回到就绪队列。除此基本状态外还有其它状态，在这里就不再一一介绍了。,吴正平,5.2.3进程的控制和调度,1.进程控制进程控制，就是对进程在整个生命周期中各种状态之间的转换进行有效的控制。进程控制的基本功能就是为作业创建进程、撤消进程，以及控制进程在运行过程中的状态转换。这些操作对应于一组程序，亦称为特殊的系统调用。这些特

19、殊的系统调用也称为原语。原语（Primitive）是机器指令的延伸，一条原语由若干机器指令所组成，有时也称之为“软指令”，用以完成特定功能的一段程序。为保证操作的正确性和完整性，大多数原语的在执行必须是连续的，即一条原语在执行中不允许被中断，大部分原语通过系统调用方式使用。,吴正平,2.进程调度,进程调序决定就绪队列中哪个进程先获得处理机,然后再由分派程序执行将处理机分配给进程的操作。进程调度要解决二个问题：(1)从就绪队列中选择哪个进程？(2)选中进程之后，进程能占用CPU多久?,吴正平,进程调度的二种方式:,剥夺式调度:(抡占式调度)进程在运行时,系统可根据某种原则,剥夺已分配给它的处理机

20、,并分配给其它进程的一种调度方式。剥夺的原则有:优先权原则:优先权高的进程可以剥夺优先权低的进程而运行。短进程优先原则:短进程到达后可以剥夺长进程的运行。时间片原则:运行一个CPU时间片后重新调度。非剥夺方式:以这种调度方式运行时,调度程序一旦把处理机分配给某进程后，除非它自愿放弃，否则它就一直运行下去。,吴正平,几种进程调度算法,(1)先进先出(FirstInFirstOut)(2)短执行进程优先(SCBF)(3)优先级调度(FPF)(4)时间片轮转法（RR）(5)多级反馈队列,吴正平,5.2.4进程的协调和通信,由于进程合作与资源共享,使进程之间产生两种形式的制约关系:(1)间接相互制约：

21、系统的重要的资源，如处理机、内存空间、设备、文件等由系统协调资源共享。进程的间接相互制约又称为互斥。互斥实质是对进程的异步运行在时间上施加的某些限制。(2)直接制约关系：一个进程在没有获得合作进程提供的必要信息之前不能超越某一执行点或无法继续工作。进程的直接制约关系称为同步，由进程间自行协调，可见,就绪进程在并发执行时,必须按照一定的次序执行。互斥与同步实质上都是在执行时序上的某种限制。因此，它们是广义同步概念。故在广义上，互斥是一种特殊的同步。,吴正平,1临界区和临界资源一次只允许一个进程使用的资源称为临界资源。程序中使用临界资源的那段程序称为临界区。对临界区调用的原则归纳为：有空则进、无空

22、等待、有限等待。2.同步机构1）锁机制锁机制提供一个锁变量S。S变量只能由上锁或开锁原语改变，若S=0表示锁开可使用，若S=1表示已加锁。加锁原语为:测试S是否为0？若S=0，让S=1。若S=1，继续测试。开锁原语则为:使S为0。锁机制解决互斥是安全可靠的。锁机制不能解决进程的同步问题。,吴正平,2）信号量和P、V操作荷兰的著名计算机科学家Dijkstra把互斥的关键含义抽象成信号量（semaphore）概念，并引入在信号量上的P、V操作作为同步原语。信号量是个被保护的量，只有P、V操作和信号量初始化操作才能访问和改变它的值。Dijkstra把信号量为S定义为一个非负整型量。在信号量S上的P操

23、作和V操作定义如下：P(S)：（1）S:=S-1；（2）若S=0，当前进程继续运行。V(S)：（1）S:=S+1；（2）若S0，当前进程继续运行。,吴正平,例：多个进程共享打印机问题，问信号量S应该等于多少？,吴正平,P，V操作从资源观点上看，S值表示可用资源数，0表示无可用资源，负数表示还欠缺的资源数。而P(s)表示请求分配一个资源，V(s)表示归还一个单位资源。P，V操作既可以用于进程互斥，也可以用于进程同步。一个简单的同步关系的问题:信号量Sa初值为1,信号量Sb初值为0,其中n为临界资源，进程A和进程B必须互斥使用。这二个进程不管分别以什么速度向前推进，但打印的结果肯定是从1开始的连续

24、数值。,吴正平,生产者与消费者问题是最著名的进程同步问题，生产者与消费者共享一个有界缓冲池，生产者向池中投入消息，消费者从中取得消息。生产者消费者问题实际上是相互合作进程关系的一种抽象，常用于检验进程同步机制。假定缓冲池中具有n个缓冲区，每个缓冲区存放一个产品，可利用互斥信号量mutex使进程对缓冲区实现互斥访问；利用资源信号量empty和full分别表示缓冲池中空缓冲区及满缓冲区的数量。只要缓冲区未满，生产者便可将产品送入缓冲区；只要缓冲池未空，消费者便可从缓冲池取走一个产品消费。信号量的初值：互斥信号量mutex=1，空缓冲区empty=n，满缓冲区full=0。,吴正平,在生产者消费者问

25、题中应当注意：1）在每个程序中用于实现互斥的P(mutex）和V(mutex)必须成对出现。2）对资源信号量empty和full的P、V操作同样需要成对出现，但它们分别处于不同的程序中。3）在每个程序中的P操作顺序不能颠倒，否则可能引起进程死锁。V操作的次序无关紧要。,吴正平,3进程的通信,进程以各自独立的速度向前推进。它们之间经常需要交换一定数据的信息，以便协调一致共同完成指定的任务。所交换的信息量，少则一个状态或数值，多则成百上千个字节。进程间信息交换方式有：低级通信:交换少量数据。这种交换的方法常用变量，数组等。前面介绍的P，V操作也可以交换少量信息。高级通信：进程间交换大量数据信息，也

26、称为消息通信。常用有消息缓冲方式、信箱通信、管道通信等方式，以较高的效率传输大批数据。,吴正平,实现进程高级通信的机制有:(1)消息缓冲：也称作直接通信方式，即一个进程直接发送一个消息给接收进程。这种通信方式必须知道对方存在。靠原语send(发送)和receive(接收)来实现。(2)信箱通信：称作间接通信方式，指进程之间的通信需要通过某种中间实体，通常把这种中间实体称为信箱。利用信箱可实现非实时通信。(3)管道通信：建立在文件系统的基础上,它利用共享文件来连接两个相互通信的进程，此共享文件称为管道(pipe)，因而这种通信方式也称为管道通信。管道通信的实质是利用外存来进行数据通信，故具有传送

27、数据量大的优点。,吴正平,5.3存储管理,5.3.1存储管理的概念及功能1系统存储器的配置系统的存储器由内、外存储器组成。程序的指令和数据只有存放在CPU能直接访问的内存中，这个程序或这个程序的部分才能够被执行。系统使用的存储器由二部分组成：物理内存和逻辑内存。物理内存由系统实际提供，由字节组成，容量受实际存储单元的限制。逻辑内存也称虚拟内存，它把内存和外存统一进行管理，它的容量受计算机地址的位数和辅存容量限制。内存的使用分为二部分，一部分为系统区，即系统程序使用的区域，主要存放操作系统、一些标准子程序、例行程序和系统数据等。另一部分为用户区。由操作系统存储管理系统管理。,吴正平,2.存储空间

28、的地址高级语言编制的源程序，存在于由程序员建立的符号名字空间(名空间)内，与存储器地址无任何直接关系，仅是符号名的集合，称作名空间。源程序经编译后所形成的目标程序，其地址总是从零开始，因此称目标程序中的地址为虚拟地址空间(地址空间)。目标地址经过链接再装入内存时，其分配到的物理地址与编译后的相对地址是不同的。称为物理地址空间，即绝对的地址集合(存储空间)。,吴正平,3.地址重定位用户在各自的逻辑空间内编程。一个作业在装入时分配到的存储空间和它的编程地址空间是不一致的。即程序在运行时需要把逻辑地址转换为物理地址。地址重定位:一个作业的逻辑地址向物理地址的转换。重定位分为静态重定位和动态重定位。静

29、态重定位:是在目标程序装入指定内存区的时候由装配程序在程序执行之前一次完成逻辑地址至物理地址的转换，以后地址不再改变。动态重定位:是在目标程序执行中，每当形成一个访问内存的有效地址时，就动态进行地址变换。由于每形成一条指令都需变换，所以需要硬件支持，如基地址寄存器和限长寄存器等，以加快地址变换。,吴正平,4.存储器管理的功能存储器管理有两个基本目的：一是方便用户；二是充分发挥内存的利用率。存储器管理具有以下几个功能:(1)内存分配(2)地址映射(3)存储扩充(4)存储共享和保护,吴正平,5.内存扩充技术内存的扩充的二种方法：一是物理上的扩充，为系统配置更多的存储器芯片。二是逻辑上的扩充，借用软

30、件技术实现主存容量的扩充目的。逻辑扩充技术有覆盖技术和交换技术二种。覆盖技术:是指同一内存区可以被不同的程序段重复使用,（a）作业的调用结构（b）覆盖结构及内存分配若把作业P全部进入内存需要190K，而使用覆盖技术后只占用110K内存。通常覆盖技术主要用于系统程序的内存管理上。,吴正平,交换技术:是指在内外存之间交换程序和数据。在内存中只驻留一部分甚至只是少数几个用户进程，其余用户进程驻在外存，当用到时进入内存。交换技术使用户可以得到大容量的存储器和内存的运行速度。但从存储管理的角度，交换并不是一种独立的存储管理方案。它与分区技术结合，形成交换式分区管理；也可以与分页或分段技术结合，形成交换式

31、分页或分段管理。交换技术实质上是系统把内存和外存统一进行管理，形成一个存储容量比实际内存大的存储器，这个存储器就是虚拟存储器。它的最大容量受二个因素决定，一是由计算机的地址结构而定，二是内外存容量之和所确定。,吴正平,5.3.2分区式管理,基本思想：将内存划分成若干连续区域(分区)，每个分区中装入一个运行作业。1.固定式分区(静态分区):系统初始化时，内存分为若干区，每个区的大小可以不同，但每一个区中只能存放一个作业。一旦分好，则每个分区的大小和分区总数均不再变化。分区分配表区号分区大小起始地址使用状态18k16k1216k24k0332k40k1464k72k05120k136k0存储区的分

32、配策略是顺序查找分区分配表，将满足作业请求容量的、且未使用的第一个分区分配给该作业（将其使用状态置为“1”）。回收时将分区表中的使用状态改为“0”即可,吴正平,2.可变分区(动态分区),存储区的分配:预先不划分分区的大小，在装入作业时使分配的分区大小正好适应作业的需要量，且分区的个数也不固定。系统初启时，除操作系统占据一块内存外，其余为一个完整的大空闲区。有作业要求装入时，则分配作业要求大小的空闲区，余下的为空闲区。如某时刻内存的状态为:,吴正平,可变分区中对内存状态的记录和管理使用有如下几种方法：(1)表格法(双表法):使用两个表格(占用区表P和空闲区表F)管理内存。这二个表的内容均为存储区

33、的大小和起始地址。这二个表的长度均可变。(2)位图法:将内存按分配单元划分，单元可以是若干字节或几个KB。每个分配单元对应于位图中的一位。如:01234567位1100000000000000.其中：0-空闲，1-已分配。(3)链表法:用链表记录内存的占用或空闲情况。链表的每项的内容有:分配状态分区起始地址分区大小链接指针链接指针可以是单向指针或双向指针。链接表也可以分别设置为已分配链表和未分配链表。,吴正平,(4)分配策略链表记录通常有如下三种分配策方法:A.首次适配法(FF)把内存中的空闲区按起始地址递增顺序排列。分配内存时，从链表首端开始查找，选择第一个满足要求的空闲块分配，而不管它究竟

34、有多大。剩余的空间仍留在空闲链中。B.最佳适配法(BF)把内存中的空闲区按分区大小递增次序排列。分配内存时，按链表顺序查找适合用户需求的空闲块，必定是最接近用户申请的块大小。然后按用户申请量进行分配，残余部分留在链中，并重新排列。C.最坏适配法(WF)把空闲块按其大小递减的顺序组成链表，大块在先，小块在后。分配时先挑选大的进行分配，使剩余空间不致太小。需要指出的是，最佳适应算法不一定是最佳的，最坏适应算法也不一定最坏。,吴正平,假设内存中现有两个空闲区：F1为110K，F2为60K。现依次有A、B、C三个作业请求装入运行，它们的内存需求分别是20K、80K和50K。若采用WF算法，作业A可获得

35、F1中的20K，作业B获得F1中的80K，作业C获得F2中的50K，三个作业的需求都得到了满足。若采用BF算法，作业A获得F2中的20K，作业B获得F1中的80K，而作业C的需求却不能满足。若采用FF算法，如果F1的地址低于F2，可得到与WF算法同样的结果，否则，则得到与BF算法同样的结果。这里，最坏适应算法倒是“最佳”的。分区管理实现了多道程序共享内存，提高了CPU的利用率，管理算法简单，容易实现。但它导致内存碎片多，拼接又化费时间，降低了内存利用率。,吴正平,5.3.3分页式管理,分页式管理的出发点是为了消除碎片而打破存储分配的连续性，使得一个作业的地址空间可以分布在若干离散的内存块上，从

36、而充分利用内存空间，提高内存利用率。页：用户作业的空间划分为若干个大小相等的块。不足一块的补齐为一页，页面大小通常为512字节至4K大小。所有的页从0开始依次编号每个页内部相对于0连续编址。页帧：系统将内存空间中也划分与页大小相等的若干块。于是作业地址空间构成一个二维地址空间，其中的任一逻辑地址都可表示成（p,d）,其中p是页号，d是页内位移量即相对地址。系统装入作业时，以页为单位给作业分配页帧。因此，作业可以按页为单位，离散地放在内存中不连续的页帧中。,吴正平,1.简单页式管理（静态分页管理）基本思想：如果内存当前可用页帧数不小于作业要求的页数，系统就实施分配，否则不于分配。简单页式用页表(

37、PMT)来进行管理。每个作业有一张相应的页表，如某作业有4页，内存中以1K为一帧进行分配，则可能的页表及对应的页帧关系。,吴正平,2.请求页式管理(动态分页管理)实现原理：开始时把整个作业的一部分装入内存，其它部分则在运行过程中动态装入。系统对页表进行扩充，扩充后的页表组成如:页表结构页帧号存取控制存在位访问位修改位1RWE1112RWE1103RE000其中存在位为0表示该页不在内存，存在位为1时表示在内存。系统在运行时动态检查页表，当存在位为0时，系统就把所需的页调入内存。但当内存中没有空闲页帧时，则先淘汰内存中的页，若淘汰的页已被修改过（修改位为1），则回写磁盘，否则直接淘汰。,吴正平,

38、系统淘汰页面时有常见的策略有：(1)先进先出法(FIFO)算法适合于程序按顺序访问地址空间。不适合于程序中有循环的情况。(2)最近最少使用法(LRU)过去一段时间内未被访问过的页，近期也可能不会被访问。该算法较为复杂。实际中常使用近似的LRU算法，如最不经常使用的页面淘汰算法LFU及最近没有使用页面淘汰算法NUR等。“颠簸”:对于刚被淘汰出去的页，进程可能马上又要访问它，故又需将它调入，因无空闲内存页帧又要淘汰另一页，而后者很可能是即将被访问的页。于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重时将导致系统的瘫痪。请求页式管理能有效地消除内存碎片，且作业地

39、址空间不受内存容量大小的限制，提高内存利用率。但由于建立和管理页表及动态地址，增大了系统时间和空间开销，如算法选择不当可能引起系统“颠簸”，致使系统性能下降。,吴正平,5.3.4段式管理,分页并不是依据作业内存的逻辑关系，而是对连续的地址空间一种固定长度的连续划分。实际上，一个作业通常是由若干逻辑程序段和数据段所组成，从用户角度希望作业能按照自已的逻辑关系分成若干自然段，每段都有自己的名子，且都从0开始编址的一维地址空间，这样有利于程序设计，又可方便地按段名进行访问。段式管理就是为了解决这个问题而提出的。段式管理也分有二种形式：简单段式管理和段页结合式管理。,吴正平,1.简单段式管理一个段定义

40、为一组逻辑信息。一个作业由若干个具有逻辑意义的段(如主程序、子程序、数据、工作区等)组成。每个段有段名，且都从0开始编址的连续空间。段的长度不固定，仅由相应逻辑信息组的大小所决定，一个作业由(s，d)组成，其中s是二维地址空间中的段号，d是段内相对地址。整个作业地址空间是二维的。简单段式管理以段为单元进行内存分配，一段分配在一个连续的内存区，各段的长度可以不同，段与段之间可不连续。一个作业的连续地址空间可以对应若干个不连续的内存分区。系统为每一个运行的作业建立一个段表(SMT)。段表：段长内存起始地址状态标志段的替换算法与释放算法类同页式管理。,吴正平,段是逻辑意义的如：cos(x)，sin(

41、x)等。所以段式管理易实现共享同一内存块里的程序或数据。不同的段表调用一个共享段时，共享段可以具有不同的段号。也可以设置共享段表来实现段的共享。为了保证各作业之间相互不干扰，系统设置段保护。一般的段保护措施如下:l建立存取控制：段表中有“存取方式”项，存取方式有三种：写、读和执行，用R、W、E表示。l段地址越界保护措施：段表中每段的表目中有段长值，以指明该段的长度，使每个作业被限制在自己的地址空间中运行。页式、段式管理提供了内外存统一管理的虚拟存储器的概念，为用户提供了一个非常大的运行空间。段式管理中允许段长动态增长，便于段的共享和保护，便于程序动态链接。但是段式管理需要更多硬件支持，同时段长

42、受内存限制，给系统增加了复杂性，也有可能产生“颠簸”。,吴正平,2.段页式结合管理基本思想：是利用分段向用户提供二维的编程空间，以方便用户编程，利用分页来管理内存空间，以提高内存利用率。在段页式系统中，作业的地址仍按逻辑意义分段，是用户定义的二维逻辑地址（s，d），其中s是段号，d是段内位移量，d又可以被系统变换为，（p，w）p是页号，w为页内位移量。这样形成三维地址映射。段页式管理:系统为每个作业建立一个段表和若干个页表，页表的个数等于段表的表目数。访问主存的物理地址就要访问段表，页表和实际地址，所以访问主存中的一条指令或一个数据，至少要访问内存三次。,吴正平,段式管理与页式管理有如下不同之

43、处：,l段是信息的逻辑单位，分段是出于作业逻辑上的要求，对用户来说，分段是可见的，分页是不可见的；页是信息物理单位，段是信息的逻辑单位；分页并不是用户作业的要求，而仅仅是为了系统管理内存的需要。也就是说，段是面向使用，页是面向管理。l分段地址空间是二维的，分页地址空间是一维的。l段的长度不固定，由用户决定；页的长度是等长的，由系统决定。段页式管理实现了分段、分页管理的优势互补，方便了用户，提高了内存利用率。但也增加了硬件成本和系统开销。,吴正平,5.4设备管理5.4.1设备的有关概念,1设备系统的设备是指进行实际I/O操作的物理设备，及控制这些设备并进行I/O操作的支持部件。从数据组织的角度，

44、设备可以分为:l块设备：以块为单位组织和传送数据。l字符设备：以字符为单位组织和传送数据。从资源分配的角度，设备可以分为:l独享设备：在作业整个运行期间为此作业独占。l共享设备：允许若干用户同时共同使用的设备。l虚拟设备：通过假脱机技术，把原来的独享设备改造成共享设备。,吴正平,2设备管理的任务(1)设备分配(2)启动设备完成实际的输入/输出操作(3)设备无关性(4)提高设备的利用率3.中断的概念中断是指计算机在执行期间，系统内发生急需处理事件，使得CPU暂时中断当前正在执行的程序而转去执行相应的事件处理程序，待处理完毕后又返回原来被中断处继续执行或调度新的进程执行的过程。中断源:引起中断发生

45、的事件。中断请求:中断源向CPU发出的请求中断处理信号.中断响应:而CPU收到中断请求后转相应的事件处理程序。根据中断源产生的条件，可把中断分为硬件中断和软件中断。,吴正平,4通道的概念程序中断I/O方式中每处理一个字，要进行一次中断处理，当有大批数据需要传递时，中断次数就很多。通道的出现建立了I/O的独立管理机构，这时只要CPU发一条I/O指令给通道，告诉通道要执行的I/O操作要访问的设备，通道便向内存索取通道程序以完成I/O控制管理。5.缓冲技术目的：为解决高速的CPU与低速的外设之间的速度不匹配。缓冲技术实质上是在内存中开辟一个具有n个单元的区域作为缓冲区。缓冲区的大小可以按实际应用需要

46、来确定。其结构形式可以有多种形式，有循环队列形式、单缓冲区及多缓冲区形式、缓冲池结构等。,吴正平,5.4.2设备管理程序,1.逻辑设备与物理设备设备的无关性:用户可不必指定特定的设备，而代之指定逻辑设备。使得用户程序与实际使用的物理设备无关，可以脱离具体的物理设备来使用设备。逻辑设备:为了方便用户使用设备，通常用符号名代替设备的类型名。如LPT表示打印机。为了实现与设备的无关性，系统中必须有一张联系逻辑设备和物理设备名称的映象表。2.设备分配程序设备分配程序应按照一定的算法，决定把某一台设备分配给那一个要求该设备的进程。设备分配时的算法有先请求先服务、优先数法等。3设备驱动程序设备驱动程序实现

47、I/O操作。,吴正平,5.4.3虚拟设备-假脱机系统,虚拟设备技术(Spooling技术):利用高速的直接存储设备（一般使用硬盘）来模拟低速的独占设备，使独占设备转化成共享设备。,吴正平,5.5文件管理5.5.1文件及文件系统,1.文件文件是逻辑上具有完整意义的数据或字符序列的集合。2文件系统文件系统是负责存取和管理文件的机构。3.5.2文件结构及存取方式1.文件的逻辑结构(1)流式文件：流式文件是由一串连续的字符序列组成。(2)记录式文件：记录式文件由若干个记录组成。2.文件的物理结构文件的物理结构是指文件在外存储器上的组织形式。文件的物理结构一般有三种类型：连续结构、链结构和索引结构。,吴

48、正平,连续结构：把逻辑上连续的文件存放在一个连续的物理介质上。,吴正平,链接结构：文件可以分别存放在物理介质的不同块中，块与块之间通过指针取得联系。,索引结构：文件的全部记录分别存放在物理介质的不同块中，系统为每一个文件建立一张索引表.,吴正平,3.文件的存取方式,一般有顺序存取、随机存取两种方式。顺序存取:对文件的每次存取是在上次存取的基础上进行。对于记录式文件，它总是在上次存取的基础上顺序存取下一个记录。而对流式文件，则在读/写指针的当前位置顺序存取文件的下一串字符。随机存取(直接存取):以任意次序直接存取文件中某一个记录，对于流式文件，需要把读/写指针调整到要访问的位置。同时，直接存取技

49、术的具体实现还与存取文件的物理介质结构有关。,吴正平,5.5.3文件存储空间管理,也称为外存管理，它和内存管理有许多相似之处，最大区别是内存管理以字节为单位，而外存管理以字符块为单位。根据文件的物理结构不同，文件在外存储器中存放的方式有连续和不连续两种。文件存储空间管理常用的技术有以下几种:1.空白文件目录:把一个连续的未分配的外存储区称为“空白文件”，系统为所有的“空白文件”建立一个目录，表目的内容为空白块地址和空白块数目。序号第一个空白块号空白块个数表示的物理块号1242，3，4，52939，10，11315515，16，17，18，194.,吴正平,2.空闲块索引表空闲块索引表的每个表目

50、登记一个空闲块号，相邻表目中的块号不一定相邻。分配时，从索引表的一个非空表目中取出一个空闲块号，分配后将该块号从相应表目中删去，回收一个物理块时，将其块号填索引表的一个空表目中。这种方法对物理块的分配和回收处理都比较容易，但索引表需要占用较大的存储空间。3.位示图利用一个二进制位来表示一个物理块的分配状态，系统为文件的存储空间建立一张位示图，参见前面的图3-3-5所示。其中每一位对应一个外存物理块，图中“1”表示对应块已分配，“0”表示对应块为“空闲”。位示图方法既可用于非连续文件，也可用于连续文件和分配，当进行连续文件分配时，需要在位示图中找到足够多的连续为0的二进位。,吴正平,5.5.4文

51、件目录,文件目录组织方式有：1一级目录结构整个系统只设置一个目录表，目录表就是文件控制块。2二级目录结构文件的目录被分成二部分，第一级是主目录表，第二级是用户目录表。3目录树结构是一棵倒置的有根的树。树型结构目录可以更确切地反映系统内部文件的分支系统，用户可将部分文件构成子树与其它部分分开以便处理。系统或用户还可以规定不同层次或子树文件有不同的存取权限，以便更好地对文件加以保护。,吴正平,5.5.5文件的共享与安全性,文件的共享和安全是一个问题的二个方面。1.文件的共享(1)由系统来实现文件的共享当要共享系统文件或其它已知用户的文件，且已知道文件的路径，则可以通过从根目录出发的路径来共享文件。

52、(2)采用基本文件目录和符号文件目录把文件目录分成二部分：一部分为基本文件目录，包括文件的结构信息,物理地址,存取控制及其它管理信息说明，并用系统赋予的标识符来标识。另一部分包括符号名和与之相应的标识符组成，称为符号文件目录。对欲共享的文件进行联接，即在用户自己的符号文件目录中对欲共享的文件建立起相应的表目，称为联接。,吴正平,2.文件的存取控制(1)存取控制矩阵用一个二维矩阵，行坐标表示系统中全部用户，列坐标表示系统中全部文件，矩阵元素aij的值为“1”时，表示用户i允许访问j文件。反之，当aij为“0”时，表示用户i不允许访问j文件。(2)按用户分类存取控制系统中的用户往往分类为:a.文件

53、主b.同组用户c.一般用户。在UNIX系统中，每个文件的存取权力说明用一个9位二进制数表示，每类用户占3位，每一位代表读、写和执行三种访问权力。(3)口令用户为自己的每一个文件规定一个口令，附在文件目录中，凡请求访问该文件的用户，必须先提供口令。,吴正平,5.5.6文件的主要操作,最基本的命令有：建立文件、打开文件、读文件、写文件、关闭文件和撤消文件等。,吴正平,3.6作业管理与用户界面作业管理的主要对用户作业进行合理调度，以提高系统的吞吐量和缩短作业的周转时间，并提供用户与操作系统的接口。在实际操作中，用户通过输入设备，如键盘、鼠标器、触摸屏等将用户要求“告诉”计算机，计算机收到这些请求后再

54、为用户服务。1.用户是通过命令或者程序向计算机发出请求，多个用户的请求以用户作业的方式在后备存储设备中等待。2.计算机收到用户请求后，利用操作系统提供的命令解释和系统调用，以及相应的处理程序，有序有效地使用系统提供的各种资源，完成用户作业的处理。,吴正平,5.6.1作业管理,作业管理主要包括作业的组织、作业的控制以及作业的调度等内容。1.作业管理的概念作业(job)是指用户在一次计算过程中，或者一次事物处理过程中，要求计算机系统所作的工作的集合。通常，一个作业又可分为若干个顺序处理的作业步，作业步的集合完成了一个作业。2.作业的类型从控制的角度可把作业分成脱机作业和联机作业。脱机作业:是在整个

55、作业运行过程中，根据作业说明书中的说明对作业进行控制.联机作业:通常是用键盘命令直接控制作业的运行。,吴正平,3作业的状态（1）进入状态提交的作业通过某种输入方式将作业输入到外存上时，称此作业处于进入状态。（2）后备状态由作业建立程序为之建立了作业控制块(PCB)，并插入到后备作业队列中等待调度运行为止。（3）运行状态作业调度程序从处于后备状态的作业队列中选出一个作业调入内存，并为之建立相应的进程后，由于此时的作业已具有独立运行的资格，如果处理机空闲，便可立即开始执行，故称此时的作业是进入了运行状态。（4）终止状态当作业（进程）的运行正常或异常结束时，进程便自我终止，或被迫终止，此时作业便进入终止状态。,吴正平,图