全套课件-《操作系统教程》-彭德林

操作系统教程

主要内容：

明确计算机操作系统的基本概念、操作系统在计算机系统中的地位和特点，叙述操作系统的功能和分类，简要介绍几种典型的操作系统。学习任务：1.1初识操作系统的概念及发展1.2了解操作系统的分类1.3掌握操作系统的特性和功能1.4认知几种典型的操作系统

第1章操作系统概述1.1初识操作系统的概念及发展1.1.1操作系统的基本概念

计算机系统的组成

完整的计算机系统是由计算机硬件系统和软件系统组成的（如图1.1所示）1.硬件系统的组成

计算机硬件系统是由运算器、控制器、存储器、输入设备和输出设备组成。2.软件系统的组成

计算机软件系统主要由系统软件和应用软件组成。系统软件主要用来管理计算机本身的操作；应用软件则是计算机提供给用户用来解决具体问题的工具图1.1计算机系统组成

操作系统的定义

可见，操作系统是计算机系统中的一个系统软件，是一些程序和模块的集合，它们以最有效合理的方式组织和管理计算机的软硬件资源，合理地组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使用户能够灵活、方便、有效地使用计算机，使整个计算机系统能高效地运行，从而在计算机与用户之间起到接口的作用。1.1.2操作系统的发展

无操作系统阶段自1946年第一台数字电子计算机的诞生到上个世纪五十年代中期的计算机，都是电子管计算机，此时还没有操作系统，属于操作系统发展的第一阶段。这一时期操作计算机的主要方式有以下二种：1.人工操作方式:

这种人工操作的特点是：（1）程序设计直接编制二进制目标程序。（2）输入输出设备主要是纸带和卡片(如图1.4所示)。（3）CPU要等待人工操作，程序员亲手上机操作，程序运行和结果输出都是以手工方式进行。（4）单用户方式，用户独占CPU和系统资源。2.脱机输入输出方式

采用脱机输入输出的方式与人工操作方式相比，有如下优点：（1）减少了CPU空闲时间。（2）提高了输入输出速度。

单道批处理系统阶段

从上个世纪五十年代中期至六十年代中期,这一阶段是计算机硬件发展的晶体管时代，此时出现了单道批处理系统。1.单道批处理系统由于系统对作业的处理是成批进行，并且在内存中只保持一道作业，所以也称为单道批处理系统。

2.单道批处理系统的特征自动性：作业是被自动处理。顺序性：作业是一个一个被处理的。单道性：内存中始终是保持一道作业。

多道程序设计阶段二十世纪六十年代中期至八十年代，是计算机硬件体系结构发展的集成电路时代，而此时计算机操作系统的发展，则进入了以多道程序设计技术为主的阶段。

现代操作系统的形成操作系统到20世纪80年代已趋于成熟。批处理操作系统、分时操作系统、实时操作系统是操作系统的三个基本类型。随着计算机硬件技术和软件技术的发展，又出现了多处理机操作系统、微机操作系统、网络操作系统、分布式操作系统以及嵌入式操作系统等多种类型的现代操作系统。1.2操作系统的分类1.2.1批处理操作系统批处理操作系统是随着计算机硬件的发展而出现的，是为了提高计算机的工作效率，除去人对计算机系统运行的干预，解决人机矛盾而提出的一种计算机成批处理的操作过程。依据系统的复杂程度和出现时间的先后，可以把批处理操作系统分类为单道批处理系统和多道批处理系统两种。

单道批处理系统1.单道批处理系统（SimpleBatchProcessingSystem）的处理过程（如图所示）把作业的源程序转换为目标程序源程序有错吗？否装配目标程序是否停止运行目标程序是开始还有作业吗？单道批处理系统的处理流程2.单道批处理系统的特征（1）自动性。（2）顺序性。（3）单道性。（4）存储器保护。单道批处理系统的缺点：一次仅能运行一个作业，这对于价格昂贵的计算机系统来说，只有一个部件工作，其余部件均处于闲置状态，资源利用率很低。

多道批处理系统在批处理系统中引入多道程序设计后，具有以下特征：（1）多道性。（2）并行性。（3）串行性。（4）无序性。（5）调度性。（6）系统开销小。多道批处理系统的缺点是：用户没有交互能力，用户一旦把作提交给系统后就失去了对自己作业的控制，系统将根据作业说明书来控制作业的执行，这对程序的修改和调试是非常不便的。作业的平均周转时间长，由于作业要排队，依次进行处理，因而周转时间较长。特别对于排在队尾作业其运行请求会被长期推迟响应。1.2.2分时操作系统

分时系统的提出分时操作系统是在批处理系统的基础上，采用分时技术提出的一种新类型的操作系统。

分时的实现

配置了分时操作系统的计算机采用主从式多终端的计算机体系结构，一台主机连接着多个带有显示器、键盘及控制器的本地或远程终端，每个用户可以通过终端以交互方式向系统发出命令，共享系统资源，请求完成某项工作，系统则分析从终端设备发来的命令，完成用户提出的需求，之后，用户又根据系统提供的运行结果，向系统提出下一步请求，就这样重复上述交互会话过程，直到用户完成预计的全部工作为止。

分时系统的特征1.交互性2.及时性3.独占性4.同时性（多路性）1.2.3实时操作系统

实时操作系统是指系统能够及时（规定时间内）对外部输入的信息（一般为一些随机事件）进行响应，并以足够快的速度完成对信息处理的一类操作系统。

实时系统按其使用方式不同可以分为两类：实时控制系统和实时信息处理系统。

实时控制系统实时控制指微型计算机在实时过程控制和提供环境监督中的应用。过程控制系统是从传感器获得输入的数字或模拟信息进行分析处理后，激发一个活动信号，从而改变可控过程，以达到控制的目的。

实时信息处理系统其主要特点是：1.实时响应2.整体性3.高可靠性和安全性1.2.4网络操作系统网络操作系统（NOS）可以看作是在网络环境下工作的操作系统软件，可简单地定义为管理整个网络资源和方便网络用户的软件集合。网络操作系统是计算机网络的心脏和灵魂，是向网络计算机提供服务的特殊的操作系统。它在计算机操作系统下工作，使计算机操作系统增加了网络操作所需要的能力。

网络操作系统的功能网络操作系统具有网络通信、资源管理、网络服务、网络管理、和相互操作能力等功能。

网络操作系统的工作模式网络操作系统运行在称为服务器的计算机上，并由联网的计算机用户（这类用户称为客户）共享，这就是网络操作系统的客户机/服务器（C/S）模式，该模式具有分布处理和集中控制的特征。网络操作系统的另一种工作模式是具有分布处理特征的对等模式，其中各个客户机可以看作是访问其他站点（服务器）的客户，也可看作是向其他站点（客户）提供服务的服务器。即网络服务和控制功能分布于各个站点上，各个站点（客户）是对等关系。

1.3操作系统的特性和功能1.3.1操作系统的特征不同操作系统有不同的特征，一个操作系统可能包含了多种特征，但大多数操作系统都具有以下几种重要特征。1.并发性（concurrence）2.共享性（sharing）3.虚拟性（virtual）4.异步性（asynchronism）1.3.2操作系统的功能

操作系统具有存储器管理功能、处理机管理功能、设备管理功能和文件管理功能。

存储器管理的功能

1.内存分配主要任务是为每道程序分配内存空间，但要以存储器利用率最高、减少不可用的内存空间为准则，同时允许正在运行的程序申请附加的内存空间，以适应程序和数据动态增长的需要。操作系统在实施内存分配时可以采用静态分配方式和动态分配方式。

2.内存保护主要任务是确保每道用户程序在自己的内存空间中运行，互不干扰，也就是说绝不允许用户程序访问操作系统以及其他用户中的程序和数据。3.地址映射在多道程序设计环境下，地址空间中的逻辑地址和内存空间中的物理地址是不可能一致的，因此，存储器管理必须提供正确的地址映射功能。

4.内存扩充

由于物理内存的容量有限，有时难以满足用户的需要，存储器管理的任务之一就是在不增加物理内存的条件下，借助于虚拟内存技术从逻辑上去扩充内存容量，使用户所感觉到的内存容量比实际内存容量大得多。

处理机管理的功能

处理机管理的主要任务是对处理机进行分配，并对其运行进行有效的控制和管理。在多道程序环境下，处理机的分配和运行都是以进程为单位的，所以对处理机的管理可理解为对进程的管理。进程管理包括以下主要内容。进程控制包括进程的创建、进程的撤消、控制进程在不同的状态间转换。进程控制的实现是通过若干条操作系统提供的进程控制原语和系统功能调用来实现的。对各个进程的运行进行协调有两种方式。（1）进程互斥方式。（2）进程同步方式。

设备管理的功能

操作系统设备管理的主要任务是完成用户提出的I/O请求，为用户分配I/O设备；提高CPU和I/O设备的利用率；方便用户使用I/O设备。设备管理应具有以下功能。

1.缓冲管理

2.设备分配

3.设备处理

4.共享设备的分配与虚拟设备的分配。

文件管理的功能

文件管理的主要任务是对用户文件和系统文件进行管理，方便用户使用，并保证文件的安全性。文件系统应具有对文件存储空间的管理、目录管理、文件的读写管理、文件的共享与保护等功能。

1.文件存储空间的管理

其主要任务是为每个文件分配必要的外存空间，并依据一定的格式建立文件各逻辑块与物理块之间的对应关系，即构建文件的物理结构，为用户顺序或随机存取文件做好准备，从而尽量提高外存的利用率，提高对文件的存取速度。

2.目录管理

目录管理的主要任务是为每个文件建立其目录项，并对众多的目录项加以有效的组织，以实现按名存取。另外，目录管理还应以链接方式实现文件的共享。

3.文件的操作

文件的读写管理、文件的共享与保护等功能。

除了上述功能之外，操作系统还要具备中断处理、错误处理等功能。操作系统的各功能之间并非是完全独立的，它们之间存在着相互依赖的关系。

1.4典型操作系统的简介

在个人计算机发展过程中，出现过许多不同的操作系统，其中目前使用较多较典型的操作系统有Windows、UNIX、Linux等，下面分别予以简述。1.4.1Windows操作系统

发展过程为满足用户对操作更方便、直接和灵活的要求，微软公司推出了一种采用图形用户界面（GraphicsUserInterface，GUI）的新颖的操作系统，Windows操作系统。在近20年的发展过程中，微软主要推出的版本有Windows3.X，Windows9X，WindowsNT，Windows2000，WindowsMe，WindowsXP和Windows2003。Windows操作系统以其灵活、快速、便宜等优点，逐渐占据了PC微型计算机上的主导地位。

主要特点

1.具有丰富多彩的图形用户界面，以全新的图标、菜单和对话框的方式支持用户操作，使计算机的操作使用更加方便、容易。2.支持多任务运行，多任务之间可方便的切换和交换信息。3.充分利用了硬件的潜在功能，突破了DOS中640KB的用户可用内存限制，提供了虚拟存储功能等内存管理能力。4.提供了方便可靠的用户操作管理，如资源管理器、文件管理器、打印管理器、控制面板等操作，可完成文件、任务和设备的并行管理。

5.操作系统本身也提供了功能强大的、方便实用的工具软件和应用软件，如字处理软件、绘图软件、通信软件、办公室用化软件等。1.4.2Unix操作系统简介

发展过程

Unix系统于1969年问世，是一个多用户、多任务的分时操作系统。最初由贝尔实验室开发在PDP-7上实现的。贝尔实验室和其他一些部门在Unix上的开发工作，导致一系列Unix版本的产生。后来，又凭借其性能的完善和良好的可移植性，经历不断的发展、演变，并广泛的应用于小型计算机、超级小型计算机乃至大型计算机上。

系统特点由于PC机硬件性能的提高，Unix操作系统又被移植到微型计算机上。可以说，Unix是在微型计算机上使用的，功能最完善、安全性能最好的操作系统。它具有以下的一些主要特点。

1.先进完善的系统管理功能

2.系统内核短小精悍，便于维护和扩充

3.采用具有典型的树形结构的文件系统

4.良好的系统可移植性

1.4.3Linux操作系统

发展过程

Linux是一套免费使用和自由传播的类Unix操作系统，Linux系统是由全世界各地的成千上万的程序员设计和实现的。Linux的出现，最早开始于一位名叫LinusTorvalds的计算机业余爱好者，当时他是芬兰赫尔辛基大学的学生。他的目的是想设计一个代替Minix的操作系统，这个操作系统具有Unix操作系统的全部功能，因而开始了Linux雏形的设计。发展至今Linux有很多发行版本，较流行的有：RedHatLinux、DebianLinux、RedFlagLinux等。

Linux的构成

Linux由内核、Shell、文件结构和实用工具四个主要部组成。1.Linux内核内核是系统的心脏，是运行程序和管理像磁盘和打印机等硬件设备的核心程序。它从用户那里接受命令并把命令送给内核去执行。2.LinuxShell

Shell是系统的用户界面，提供了用户与内核进行交互操作的一种接口。它接收用户输入的命令并把它送入内核去执行。

3.Linux文件结构

文件结构是文件存放在磁盘等存储设备上的组织方法。主要体现在对文件和目录的组织上。Linux目录采用多级树形结构。用户可以浏览整个系统，可以进入任何一个已授权进入的目录，访问那里的文件。4.Linux实用工具

标准的Linux系统都有一套叫做实用工具的程序,它们是专门的程序实用工具可分三类:

编辑器：用于编辑文件。过滤器：用于接收数据并过滤数据。交互程序：允许用户发送信息或接收来自其他用户的信息。Linux优点与优势

1.Linux的优点Linux是免费的软件，你可以自由安装及任意修改软件的源代码。它拥有数量庞大的经世界各地Linux高手所开发的应用软件的支持。Linux系统与SystemV及BSDUnix兼容，并符合POSIX1.0规格。具备现代一切功能完善的Unix系统所具备的全部特征，其中包括真正的多任务、虚拟存储、共享库函数、即时负载、优越的存储管理和TCP/IP网络支持等。支持Intelx86、680x0、Sparc、Alpha及MIPS等平台，并广泛支持各种周边设备。系统内核紧凑高效，对硬件要求低，即使在4MB内存的386PC机上，也有非常卓越的表现。2.Linux的优势

Linux之所以受到广大计算机爱好者的喜爱，主要原因有两个，一是它属于自由软件，用户不用支付任何费用就可以获得它和它的源代码，并且可以根据自己的需要对它进行必要的修改，无偿对它使用，无约束地继续传播。另一个原因是，它具有Unix的全部功能，任何使用Unix操作系统或想要学习Unix操作系统的人都可以从Linux中获益。本章小结

本章介绍了计算机操作系统的概念及其发展，从不同角度叙述了计算机操作系统的分类，详细阐述了操作系统的特性和功能，最后简要介绍了几种流行的操作系统的发展过程及特点。实训一

1.熟练WindowsServer2003的使用，熟悉Windows操作系统的特点。2.下载、安装和简单使用Linux操作系统，初步了解该操作系统的优点。

2.1进程的基本概念2.2进程控制2.4进程调度2.3进程互斥、同步和通信2.5死锁2.6线程2.7WindowsServer2003进程管理

第2章进程管理

2.1进程的基本概念

程序的执行与特征进程的概念与特征进程的状态及状态转换进程控制块2.1.1程序的执行与特征程序顺序执行程序顺序执行：一个较大的程序通常都由若干个程序段组成。程序在执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。程序顺序执行时的特征顺序性可再现性封闭性在早期的单道程序系统中，程序执行时独占系统资源，数据输入、数据处理、结果输出这三个程序段只能严格按程序规定的顺序一个接一个地顺序执行。图2.1所示为程序的顺序执行，其中，I代表数据输入操作，C代表计算操作，P为打印操作。

I1C1P1I2C2P2作业1作业2图2.1程序的顺序执行程序并发执行程序并发执行：是指各程序在执行时间上是可重叠的。我们把执行时间上有重叠的几个程序称为并发程序。程序并发执行时的特征间断性失去封闭性不可再现性如图2.2所示，对一个作业而言，其输入程序、计算程序和打印程序这三个操作必须顺序执行；但对一批作业而言，许多程序之间就有可能并发执行。例如，输入程序在输入第一个程序后，在计算程序对该程序进行计算的同时，可由输入程序再输入第二个程序，从而使第一个程序的计算操作与第二个程序的输入操作并发执行。一般说，输入程序在输入第I+1个程序时，计算程序可能正在对第I个程序进行计算，而打印程序正在打印第I-1个程序的计算结果。I1I2I3I4C1C2C3C4P1P2P3P4图2.2程序并发执行图2.2表示出了输入、计算、打印三个程序对一批作业进行处理的情况。2.1.2进程的概念与特性进程的概念与特征进程的概念:可并发执行的程序在一个数据集合上的运行过程进程和程序是两个既有联系又有区别的概念，它们的区别和联系可简述如下：进程是一个动态概念，而程序则是一个静态概念。程序是指令的有序集合，没有任何执行的含义；而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。进程具有并行特征，而程序没有。由进程的定义可知，进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。显然，由于程序不反映执行过程，所以不具有并行特征进程是竞争计算机系统资源的基本单位，从而其并行性受到系统自己的制约。这里，制约就是对进程独立性和异步性的限制。不同的进程可以包含同一程序，只要该程序所对应的数据集不同。2.1.3进程的状态及状态转换

进程的状态在进程的生命期内，一个进程至少具有三种基本状态，它们是：执行状态、等待状态和就绪状态。进程的状态转换进程的状态反映进程执行过程的变化。这些状态随着进程的执行和外界条件发生变化和转换。那么，是什么样的条件使得进程各状态发生转换呢？图2.3给出了三个基本状态，即就绪状态、执行状态与等待状态之间的转换关系。图2.3进程状态转换2.1.4进程控制块PCB

从处理机的活动角度来看，如何识别、描述进程呢？显然，系统中需要有描述进程存在和能够反映其变化的物理实体，即进程的静态描述。进程的静态描述由三部分组成：进程控制块PCB，有关程序段和该程序段对其进行操作的数据结构集。进程控制块包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映。系统根据PCB感知进程的存在和通过PCB中所包含的各项变量的变化，掌握进程所处的状态以达到控制进程活动的目的。由于进程的PCB是系统感知进程的唯一实体，因此，在几乎所有的多道操作系统中，一个进程的PCB结构都是全部或部分常驻内存的。一般来说，根据操作系统的要求不同，进程的PCB所包含的内容会多少有所不同,但是下面所示基本内容是必需的：(1)描述信息①进程名或进程标识号②用户名或用户标识号③家族关系(2)控制信息①进程当前状态进程在活动期间可分为就绪态、执行态和等待状态。②进程优先级进程优先级是选取进程占有处理机的重要依据。与进程优先级有关的PCB表项有：a.占有CPU时间；b.进程优先级偏移；c.占据内存时间等。③程序开始地址④各种计时信息给出进程占有和利用资源的有关情况。⑤通信信息通信信息用来说明该进程在执行过程中与别的进程所发生的信息交换情况。(3)资源管理信息PCB中包含最多的是资源管理信息，包括有关存储器的信息、使用输入输出设备的信息、有关文件系统的信息等，这些信息有：①占用内存大小及其管理用数据结构指针，例如，后述内存管理中所用到的进程页表指针等。②在某些复杂系统中，还有对换或覆盖用的有关信息，如对换程序段长度，对换外存地址等，这些信息在进程申请、释放内存中使用。③共享程序段大小及起始地址。④输入输出设备的设备号，所要传送的数据长度、缓冲区地址、缓冲区长度及所用设备的有关数据结构指针等。这些信息在进程申请，释放设备进行数据传输中使用。⑤指向文件系统的指针及有关标识等。进程可使用这些信息对文件系统进行操作。(4)CPU现场保护结构总之，进程控制块PCB是系统感知进程存在的唯一实体。

2.2进程控制操作系统内核简介建立进程进程的撤消进程的阻塞进程的唤醒进程的挂起和激活2.2.1操作系统内核简介进程从产生到消亡的整个过程都是由操作系统来控制的，为了实现对进程的有效控制，操作系统必须设置一套控制机制，它应具有创建一个新进程，撤消一个已经运行结束的进程，以及具有改变进程状态、实现进程间通信的能力。这样的机构属于操作系统的内核。内核中所包含的原语主要有进程控制原语、进程通信原语、资源管理原语以及其他方面的原语。

2.2.2建立进程

在多道程序环境中，只有（作为）进程（时）才能在系统中运行。因此，为使程序能运行就必须为它创建进程。导致一个进程去创建另一进程的典型事件，可有以下四类：用户登录作业调度提供服务应用请求一旦操作系统发现了要求创建进程的事件后，便调用进程创建原语，按下述步骤创建进程：(1)由系统程序模块统一创建，例如，在批处理系统中，由操作系统的作业调度程序为用户作业创建相应的进程以完成用户作业所要求的功能。(2)由父进程创建，例如，在层次结构的系统中，父进程创建子进程以完成并行工作。

2.2.3进程的撤消

以下几种情况导致进程被撤消：该进程已完成所要求的功能而正常终止。由于某种错误导致非正常终止。祖先进程要求撤消某个子进程。无论哪一种情况导致进程被撤消，进程都必须释放它所占用的各种资源和PCB结构本身，以利于资源的有效利用。另外，当一个祖先进程撤消某个子进程时，还需审查该子进程是否还有自己的子孙进程，若有的话，还需撤消其子孙进程的PCB结构和释放它们所占有的资源。

2.2.4进程的阻塞阻塞原语在一个进程期待某一事件发生，但发生条件尚不具备时，被该进程自己调用来阻塞自己。阻塞原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断处理机和保存该进程的CPU现场。然后将被阻塞进程置“阻塞”状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。这里，转进程调度程序是很重要的，否则，处理机将会出现空转而浪费资源。图2.6阻塞原语图2.2.5进程的唤醒

当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都将被唤醒。唤醒一个进程有两种方法：一种是由系统进程唤醒。另一种是由事件发生进程唤醒。当由系统进程唤醒等待进程时，系统进程统一控制事件的发生并将“事件发生”这一消息通知等待进程。从而使得该进程因等待事件已发生而进入就绪队列。由事件发生进程唤醒时，事件发生进程和被唤醒进程之间是合作关系。因此，唤醒原语既可被系统进程调用，也可被事件发生进程调用。称调用唤醒原语的进程为唤醒进程。唤醒原语首先将被唤醒进程从相应的等待队列中摘下，将被唤醒进程置为就绪状态之后，送入就绪队列。当把被唤醒进程送入就绪队列之后，唤醒原语既可以返回原调用程序，也可以转向进程调度，以便让调度程序有机会选择一个合适的进程执行。图2.7唤醒原语2.2.6进程的挂起和激活

进程挂起:当出现了引起进程挂起的事件时，系统将利用挂起原语将处于阻塞状态的进程挂起。挂起原语的执行过程是，检查被挂起进程的状态，若正处于活动就绪状态，便将其改为静止就绪，对于活动阻塞状态的进程，则将其改为静止阻塞。为了方便用户或父进程考查该进程的运行情况，而把该进程的PCB复制到某指定的内存区域。最后，如被挂起的进程正在执行，则转调试程序重新调度。

进程的激活过程:当发生激活进程的事件时，若进程驻留在外存而内存已有足够的空间，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语将指定进程激活。激活原主先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪便将其改为活动就绪，若为静止阻塞便将其改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度，否则立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。2.3进程互斥、同步和通信

进程的同步进程的互斥信号量和P、V操作进程通信2.3.1进程的同步把异步环境下的一组并发进程，因直接制约而互相发送消息进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。具有同步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件。

2.3.2进程的互斥资源共享所引起的制约临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的，临界区不可能用增加硬件的方法来解决。因此，临界区也可以被称为访问公用数据的那段程序。间接制约:把这种由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约，简称间接制约。互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。一组并发进程互斥执行时必须满足如下准则：(1)不能假设各并发进程的相对执行速度。即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区(2)并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区。(3)并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。(4)并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区。互斥的加锁实现当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区。

2.3.3信号量和P、V操作

信号是铁路交通管理中的一种常用设备，交通管理人员利用信号颜色的变化来实现交通管理。在操作系统中，信号量sem是一整数。在sem大于等于零时代表可供并发进程使用的资源实体数，但sem小于零时则表示正在等待使用临界区的进程数。显然，用于互斥的信号量sem的初值应该大于零，而建立一个信号量必须经过说明所建信号量所代表的意义，和赋初值以及建立相应的数据结构以便指向那些等待使用该临界区的进程。

信号量的数值仅能由Ｐ，Ｖ原语操作改变.采用Ｐ，Ｖ原语，可以把类名为Ｓ的临界区描述为WhenＳdoＰ(sem)临界区Ｖ(sem)od。Ｐ原语操作的主要动作是：sem减1；若sem减1后仍大于或等于零，则进程继续执行；若sem减1后小于零，则该进程被阻塞在与该信号相对应的队列中，然后转进程调度。Ｖ原语的操作主要动作是：sem加1；若相加结果大于零，进程继续执行；若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。私用信号量:一般来说，也可以把各进程之间发送的消息作为信号量看待。与进程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关。因此，称该信号量为私用信号量用Ｐ，Ｖ原语操作实现同步有了私用信号量的概念，可以使用Ｐ，Ｖ原语操作实现进程间的同步。利用Ｐ，Ｖ原语实现进程同步的方法与利用wait和signal过程时相同，也是分为三步。首先为各并发进程设置私用信号量，然后为私用信号量赋初值，最后利用Ｐ，Ｖ原语和私用信号量规定各进程的执行顺序。

用Ｐ，Ｖ原语实现进程互斥设信号量sem是用于互斥的信号量，且其初值为1表示没有并发进程使用该临界区。显然，由上面几节的讨论可知，只要把临界区置于Ｐ(sem)和Ｖ(sem)之间，即可实现进程间的互斥。当一个进程想要进入临界区时，它必须先执行Ｐ原语操作以将信号量sem减1。在一个进程完成对临界区的操作之后，它必须执行Ｖ原语操作以释放它所占用的临界区。2.3.4进程通信

在单机系统中，进程间通信可分为4种形式：主从式会话式消息或邮箱机制共享存储区方式消息缓冲机制发送进程和接收进程采用消息缓冲机制进行数据传送时，发送进程在发送消息前，先在自己的内存空间设置一个发送区，把欲发送的消息填入其中，然后再用发送过程将其发送出去。接收进程则在接收消息之前，在自己的内存空间内设置相应的接收区，然后用接收过程接收消息。由于消息缓冲机制中所使用的缓冲区为公用缓冲区，使用消息缓冲机制传送数据时，两通信进程必须满足如下条件：在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其他进程对该缓冲区消息队列的访问。否则，将引起消息队列的混乱。同理，当接收进程正从消息队列中取消息缓冲时，也应禁止其他进程对该队列的访问。当缓冲区中无消息存在时，接收进程不能接收到任何消息。至于发送进程是否可以发送消息，则由发送进程是否申请到缓冲区决定。邮箱通信就是由发送进程申请建立一与接收进程链接的邮箱。发送进程把消息送往邮箱，接收进程从邮箱中取出消息，从而完成进程间信息交换。设置邮箱的最大好处就是发送进程和接收进程之间没有处理时间上的限制。一个邮箱可考虑成发送进程与接收进程之间的大小固定的私有数据结构，它不像缓冲区那样被系统内所有进程共享。邮箱由邮箱头和邮箱体组成。其中邮箱头描述邮箱名称、邮箱大小、邮箱方向以及拥有该邮箱的进程名等。邮箱体主要用来存放消息，如图2.14所示。

图2.14邮箱通信结构2.4进程调度

进程调度的基本概念进程调度的类型进程调度的算法进程高度的基本概念在进程状态的变化中，从就绪到运行的转变是由一个专门的程序来完成的，该程序称为进程调度程序。进程调度程序的具体功能如下：记录系统中所有进程的状态、优先数和资源需求情况确定调度算法和调度方式分配处理器给某进程，完成处理器的切换进程调度的类型进程调度亦可称为处理机调度，它协调和控制各进程对CPU的使用。一般来说，处理机调度可以分为4级：作业调度：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，还负责回收系统资源。交换调度：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。交换调度主要涉及到内存管理与扩充。进程调度：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。线程调度。图2.17作业的状态及其转换进程调度算法

先来先服务（FCFS）调度算法轮转法（roundrobin）多级反馈轮转法优先级法最短作业优先法（shortestjobfirst）最高响应比优先法（highestresponserationext）2.5死锁死锁的概述死锁的处理2.5.1死锁的概述死锁的定义:是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。

图2.21死锁的概念死锁的起因死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。但是，可以采用适当的资源分配算法，以达到消除死锁的目的。为此，先看看产生死锁的必要条件。产生死锁的必要条件互斥条件。并发进程所要求和占有的资源是不能同时被两个以上进程使用或操作的，进程对它所需要的资源进行排他性控制。不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放。部分分配。进程每次申请它所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源。环路条件。存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。显然，只要使上述4个必要条件中的某一个不满足，则死锁就可以排除。

2.5.2死锁的处理

死锁预防一种方法是打破资源的互斥和不可剥夺这两个条件，这种方法不能解决访问那些不允许被同时访问的资源时所带来的死锁问题。另一种方法则是打破资源的部分分配这个死锁产生的必要条件。即预先分配各并发进程所需要的全部资源。死锁避免的一种基本模式是把进程分为多个步，其中每个步所使用的资源是固定的，且在一个步内，进程所保持的资源数不变。即进程的资源请求、使用与释放要依靠不同的步完成。死锁的检测和恢复当进程进行资源请求时死锁检测算法检查并发进程组是否构成资源的请求和保持环路。有限状态转移图和petriNet等技术都可用来有效地判断死锁发生。死锁的恢复办法较多。最简单的办法是终止各锁住进程，或按一定的顺序中止进程序列，直至已释放到有足够的资源来完成剩下的进程时为止。另外，也可以从被锁住进程强迫剥夺资源以解除死锁。2.6线程线程的概念线程与进程的比较引入线程的优点线程的概念:线程是进程中的一个实体，是被系统独立调度和分派的基本单位。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器、一组寄存器和栈），但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程；同一进程中的多个线程之间可以并发执行。线程与进程的比较:进程是资源分配的基本单位。进程也是抢占处理机的调度单位，它拥有一个完整的虚拟地址空间。与进程相对应，线程与资源分配无关，它属于某一个进程，并与进程内的其他线程一起共享进程的资源。再者，当进程发生调度时，不同的进程拥有不同的虚拟地址空间，而同一进程内的不同线程共享同一地址空间。线程的适用范围并不是在所有的计算机系统中线程都是适用的。事实上在那些很少做进程调度和切换的实时系统、个人数字助理系统中，由于任务的单一性，设置线程相反会占用更多的内存空间和寄存器。使用线程的最大好处是在有多个任务需要处理机处理时，减少处理机的切换时间,而且线程的创建和结束所需要的系统开销也比进程的创建和结束要小得多。由此，可以推出最适合使用线程的系统是多处理机系统。在多处理机系统中，同一用户程序可以根据不同的功能划分为不同的线程，放在不同的处理机上执行。线程的执行特性线程在执行时也有它的相关特性。线程的状态和同步用来反映线程的这些特性。线程有3个基本状态，即执行、就绪和阻塞。但是线程没有进程中的挂起状态。也就是说，线程是一个只与内存和寄存器相关的概念，它的内容不会因交换而进入外存。线程的另一个执行特性是同步。由于同一进程中的所有线程共享该进程的所有资源和地址空间，任何线程对资源的操作都会对其他相关线程带来影响。因此，系统必须为线程的执行提供同步控制机制，以防止因线程的执行而破坏其他的数据结构和给其他线程带来不利的影响。线程中所使用的同步控制机制与进程中所使用的同步控制机制相同。因此，这里不再进一步讲述有关线程的同步问题线程的两个基本类型是：用户级线程和系统级线程(核心级线型)。用户级线程的管理过程全部由用户程序完成，操作系统内核只对进程进行管理核心级线程由操作系统内核进行管理。2.7WindowsServer2003进程管理

WindowsServer2003的结构WindowsServer2003是基于NT技术开发的32位操作系统，采用32位内核进行系统调度和内存管理，其结构是一种模块化的层次系统结构，主要层次包括：硬件抽象层、内核、执行体和子系统集。它提供了四个主要功能：线程调度、陷阱调度处理和异常处理、多处理机同步、为执行体提供内核对象。windowsserver2003中的进程windowsserver2003中的每个Win32进程都由一个执行体进程块表示。执行体进程块描述进程的基本信息，并指向其他与进程控制相关的数据结构。执行体进程块中的主要内容包括：线程块列表：描述属于该进程的所有线程的相关信息，以便线程调度程序进行处理器资源的分配和回收虚拟地址空间描述表：描述进程地址空间各部分属性，用于虚拟存储管理。对象句柄列表：当进程创建或打开一个对象时，就会得到一个代表该对象的句柄，用于对象访问，对象句柄列表维护该项进程正在访问的所有对象列表。

windowsserver2003中的线程在windowsserver2003中，系统的处理器调度对象为线程。windowsserver2003把线程状态分为以下七种。就绪状态：线程已获得除处理器外的所需资源，正等待CPU的处理。备用状态：已选择好线程的执行处理器，正等待描述表切换，以进入运行状态。系统中每个处理器上只能有一个处于备用状态的线程。运行状态：已完成描述表切换，线程进入运行状态。线程会一直处于运行，直到被剥夺CPU、时间片用完、线程终止或进入等待状态。等待状态：线程正等待某对象，以同步线程的执行。当等待的事件出现时，结束等待，并进入就绪状态。转换状态：转换状态与就绪状态类似，但线程的内核堆栈位于外存。当线程等待事件出现，而它的内核堆栈处于外存时，线程进入转换状态，当线程内核堆栈被调回内存时，线程进入就绪状态。终止状态：线程执行完就进入终止状态。初始化状态：线程处于创建过程时的状态。WindowsServer2003的线程调度windowsserver2003中，处理器调度的调度对象是线程，并且所采用的调度策略是优先级和时间片算法结合。基本思想是基于动态优先级的抢占式调度，当一个线程被调度而进入运行状态时，可运行一个被称为时间配额的时间片。时间配额是windowsserver2003中允许一个线程连续运行的最大时间长度，时间片的时间到，中断该线程的执行，系统会判断是否需要降低该线程的优先级，并查找有否其他高优先级或同等优先级的就绪线程。由于系统采用了抢占式调度方式，所以有可能在一个线程时间配额没有用完时，被进入就绪状态的更高优先级别的线程抢占CPU。

主要内容：存储器是计算机系统的重要资源之一。本章主要从基本原理、地址转换、分配与回收等几方面介绍三种常用存储管理方式的使用，以及虚拟存储器的意义。并且涉及到了覆盖、交换、拼接等常用技术。

学习任务：3.1存储管理概述3.2连续分配存储管理3.3离散分配存储管理3.4虚拟存储管理3.5WindowsServer2003存储管理

第3章存储管理

3.1存储管理概述

3.1.1存储管理的任务和功能

存储管理的任务

存储管理是操作系统的重要组成部分，它负责计算机系统内存空间的管理。其目的是充分利用内存空间为多道程序并发执行提供存储基础，并尽可能地方便用户使用。

存储管理的功能

存储管理应实现如下功能：1.存储分配的功能：2.地址变换的功能：3.“扩充”主存容量的功能：4.存储保护的功能：3.1.2存储管理的方式

由于存储管理主要是对内存进行管理，所以根据管理的方式不同可分为：

1.连续分配存储管理

(1)单一连续分配存储管理

(2)固定分区存储管理

(3)可变分区存储管理

2.离散分配存储管理

(1)页式存储管理

(2)段式存储管理

(3)段页式存储管理

3.虚拟存储管理

(1)请求分页存储管理

(2)请求分段存储管理3.1.3地址重定位

程序的装入

程序的运行必须先创建一个进程，创建进程的首要任务是将其所对应的程序和数据装入内存。将一个用户的源程序变为可在内存中执行的程序需要经过：编译、链接、装入等几步。

1.编译：编译程序可将用户的源文件编译成若干个目标模块。

2.链接：由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成完整的装入模块。

3.装入：由装入程序将需要装入的模块装入内存中。

存储空间

1.逻辑地址（相对地址）：．由于用户在编程时无法预知程序会在内存中的位置，所以无法直接使用内存地址，于是用户以0为起点来安排程序指令和数据。每条程序指令要访问的数据都有一个对应的地址，这个地址称为逻辑地址。由于它是相对于0的地址，又称相对地址、虚地址。2.逻辑地址空间（相对地址空间）：每一个完整的用户作业都存在着一定的逻辑地址，这些地址形成一个范围，用户程序、数据、工作区都包含在该范围之内，这就是逻辑地址空间。也就是说逻辑地址空间就是逻辑地址的集合。用户可以直接对逻辑地址和逻辑地址空间进行访问和操作。逻辑地址空间又称为相对地址空间、用户空间或作业空间。其大小位于0到逻辑地址最大值之间。3.物理地址（绝对地址）：程序（模块）在内存中的实际地址称为物理地址，又称绝对地址、实地址。物理地址从0开始，最大值取决于内存的大小和内存地址寄存器的最大值，二者中较小的那个值为其最大值。4.物理地址空间（绝对地址空间）：当作业进入主存时，其占有的内存空间就是物理地址空间，也就是说：当逻辑地址空间被映射到内存时所对应的物理地址的集合就是物理地址空间，也称绝对地址空间。只有当逻辑地址空间存在时，才会有物理地址空间。其最大只能达到内存的大小。当然，还要考虑地址空间寄存器的大小。

地址重定位

一个作业在装入时分配到的存储空间和它的地址空间是不一致的。因此，作业在运行时其CPU所要访问的指令、数据的实际地址和地址空间中的地址是不同的。显然，如果在作业执行时不对有关的地址进行对应的修改，将导致错误的结果。这是由于一个作业装入到与其地址空间不一致的存储空间所引起的，关于地址改变的过程称为地址重定位。这是一个变换过程，我们把作业地址空间中使用的逻辑地址变换成主存中物理地址的过程称为地址映射。重定位方法：绝对地址=基址+相对地址注：基址是指令在内存中的起始地址，也叫始址。其通常存于基址寄存器中。根据地址变换进行的时间及采用技术手段的不同，可以把重定位分为静态重定位和动态重定位。1.静态重定位(1)定义：静态重定位是在程序装入内存后运行前将程序中的所有逻辑地址转换为物理地址，在程序运行过程中不再修改。如图3.2所示逻辑地址空间重定位MOV[nn]MOV[nn+n]0nn+MM物理地址空间图3.2静态重定位(2)主要优点：容易实现，无需增加硬件地址变换机构，只要求为每个程序分配一个连续的存储区，由于程序在执行期间不能移动，所以不能共享程序和数据，因而可在一般计算机上实现。(3)主要缺点：①由于要给每个作业分配连续的存储空间，且在作业的整个执行期间不能再移动，因而也就不能实现重新分配主存。不利于主存空间的充分利用。②用户必须事先确定所需的存储量，若所需的存储量超过可用存储空间，用户必须考虑覆盖结构。③用户之间难以共享主存中的同一程序副本。2.动态重定位(1)定义：动态重定位是在程序的运行过程中，当指令需要执行时对将要访问的地址进行修改。修改过程见图3.3（举实例说明）。(2)主要优点：①用户作业不要求分配连续的存储空间。②用户作业在执行过程中，可以动态申请存储空间和在主存中移动。③有利于程序段的共享。(3)主要缺点：①需要附加硬件支持。②实现存储管理的软件算法比较复杂。

与静态重定位相比较，动态重定位的优点是非常明显的，且现在的计算机在不同程度上都提供有动态重定位所需的硬件支持，因此动态重定位方法得到了普遍应用。

1000逻辑地址空oadB500123500LoadB5001231000+基址寄存器逻辑地址物理地址空间图3.3动态重定位3.1.4虚拟存储器

虚拟存储器是一种存储管理技术，能够完成用小的内存实现在大的虚拟空间中程序的运行工作。内存在计算机中的作用很大，计算机中所有运行的程序都需要经过内存进行存储，如果存储的程序太大或太多，就会导致内存消耗殆尽。为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用，当内存占用完时，电脑就会自动调用硬盘空间来充当内存，以缓解内存的紧张。即一个大作业在执行时,其一部分地址空间在主存,另一部分在辅存。因此,从效果来看,这样的系统好像提供了存储容量比实际主存大得多的存储器,人们称这样的存储器为虚拟存储器。一个虚拟存储器的最大容量是由计算机的地址结构确定的。若CPU给出的有效地址长度为18位,可以寻址范围为:0—256K。

3.1.5覆盖与交换

内存管理要求用户作业一次性装入内存，如果作业的存储需求远远大于系统提供的整个用户区，该作业就无法投入运行，所以内存管理要解决小内存运行大作业的问题。覆盖与交换是在多道环境下用来扩充内存的两种方法。

覆盖覆盖技术是一种解决小内存运行大作业的方法。在单道系统中，每一时刻只能执行一条指令，而事实上一个作业中若干程序段和数据段可以不同时使用。因此，可以把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。一般情况下，这些程序段都被保存在外存中，当一部分程序段执行结束后，再把另一程序段调入内存覆盖前面的程序段。这就使得用户看来好像内存扩大了，从而达到了扩充内存的目的。覆盖技术是一种早期的主存扩充的方式，不能实现虚拟存储器。

交换多道程序环境下可同时执行几个作业，但是，这些同时存在于内存中的作业，有的处于执行状态，有的则处于等待状态，一般来说，等待时间会比较长。让这些等待中的进程继续驻留内存，将会造成存储空间的浪费。因此，应该把它们换出内存。交换技术就是把暂时不用的某个程序及数据部分（或全部）从内存移到外存中去，以便腾出必要的内存空间；或把指定的程序或数据从外存读到相应的内存中，并将控制权转给它，让其在系统上运行的一种内存扩充技术。交换进程由换出和换入两个过程组成，换出是把内存中的数据和程序换到外存的交换区，而换入则是把外存交换区的数据和程序换到内存中。

3.1.6分区的存储保护存储保护是为了防止一个作业破坏操作系统或其他作业。常用的存储保护方法有界限寄存器（包括上、下界寄存器保护法和基址、限长寄存器保护法）和存储保护键方法。1.上、下界寄存器保护法：上界寄存器≤物理地址≤下界寄存器，如超出这个范围便产生保护性中断。2.基址、限长寄存器保护法：

基址寄存器≤物理地址≤基址寄存器+限长寄存器，如果超过了限长，则发出越界中断信号，并停止作业的运行。3.存储保护键方法：

系统为每个分区设一个保护键，在程序状态字中也设同样的保护键字段，访问内存时检查键的配对情况，如果不匹配则产生保护性中断。3.2连续分配存储管理

3.2.1单一连续分配存储管理

单一连续分配存储管理基本原理单一连续分配存储管理是一种最简单的存储管理方式，它只能用于单用户、单任务的操作系统，如在8位和16位微机上CP/M和MS-DOS操作系统。它将内存分为两个区：

①系统区：仅供操作系统使用的主存区，通常设置在内存的低地址部分；②用户区：指除系统区以外的全部内存空间，提供给用户使用。

存储空间的分配与释放内存中只有一个用户可用区域，当一个作业申请内存空间时，分配程序将作业的大小与内存中用户可用区域进行比较，如果作业申请的区域小于用户可用区，则进行正常分配，否则提示用户内存不够无法分配。而作业一旦进入内存，就要等到它执行结束后才能释放内存。因此这种分配方式不支持虚拟存储器的实现。

地址变换采用静态重定位的方式。即作业在装入时就一次性对所有指令将要访问的地址进行修改。

存储保护采用界地址寄存器保护法。其中，基址寄存器的内容是作业进入内存后的首地址，长度寄存器的内容是用户可用区的长度。

单一连续分配的主要特点单一连续分配方式管理简单，只需要很少的软件和硬件支持，且便于用户了解和使用。采用这种存储分配方式，由于内存中只装入一道作业运行，从而使各类资源的利用率都不高，容易造成系统资源的浪费。

3.2.2固定分区（静态分区）存储管理

固定分区存储管理基本原理固定式分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。这种分区方式一般将内存的用户区划分成大小不等的区域，以适应不同大小的作业需要。

内存分配表用于固定分区管理的内存分配表是一张分区分配表，按顺序每个分区在分区分配表中对应一个表目。表目内容包括分区号、分区大小、分区起始地址以及使用状态。一个程序在运行时，先要根据其对内存的需求量，按一定的分配策略在分区分配表中查找空闲分区。若找到需要的分区，就将该分区分配给程序，并将该分区分配表中对应的分区状态重新置为空闲状态（通常用0表示）。见图3.5区号大小始址状态120K40K已分240K60K已分380K100K未分4160K180K已分5320K340K未分图3.5分区分配表

存储空间的分配与释放由于内存中存在着不止一个空闲区，因此在给作业分配内存时应有所选择，可以采用分配算法来分配。常用的分配算法有最佳适应算法、首次适应算法、循环首次适应算法、最坏适应算法。

地址变换由于作业被分配进入内存后位置不再发生变化，因此，地址转换可以采用静态重定位方法。对每一个作业进行重定位时要修正基址寄存器的值。

存储保护存储保护可以采用界地址寄存器保护方式。

固定分区存储的特点

(1)优点：固定分区实现技术简单，适用于作业的大小事先清楚的系统中。

(2)缺点：内存的利用率不高，当程序大小小于分区的大小将会产生一部分非常小的空闲区，这部分空闲区不可再利用，所以说“零头”空间不能充分利用。3.2.3可变分区(动态分区)存储管理

可变分区存储管理基本原理可变分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。这种存储管理技术是固定分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。

可变分区采用的数据结构

(1)已使用分区表：描述已被分配的区域

(2)空闲分区表：描述内存中的空闲区域，分区表中的空闲分区记录以地址递增的顺序排列。

可变分区的分配和回收分配时首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收作业所使用的分区时，要检查回收的分区是否与前后空闲的分区相邻接，若是则加以合并，使之成为一个连续的大空间。

1.常用分配算法(1)最佳适应算法：空闲分区表中的空闲分区要按分区大小从小到大的进行排序，自表头开始查找到第一个满足要求的空闲分区，然后进行分配。(2)首次适应算法：空闲分区表中的空闲分区要按地址由低到高进行排序。(3)循环首次适应算法：

(4)最坏适应法：空闲分区按大小由大到小排序，每次查找从表头开始。

2.可变分区的回收修改情况分以下四种：

(1)要回收区上、下都没有相邻的空闲分区在空闲分区表中追加一个空闲分区，其始址和大小即为回收区的始址和大小。原空闲区的个数加1。

(2)要回收区上方有相邻的空闲区在空闲分区表中找到这个空闲区，修改其始址和大小，始址为仍为原空闲区的始址，大小为空闲区与回收区的大小之和。原空闲区的个数不变。

(3)要回收区下方有相邻的空闲区在空闲分区表中找到这个空闲区，修改其始址和大小，始址为回收区的始址，大小为回收区的大小与空闲区的大小之和。原空闲区的个数不变。

(4)要回收区上、下都有相邻的空闲分区在空闲分区表中找到这两个空闲区，修改上面相邻的空闲区大小，其始址不变。大小改为相邻两个空闲区和回收区的大小总和。然后从空闲分区表中删除后一个相邻空闲区的记录。同时，原空闲区的个数减1

地址转换可变分区采用动态重定位方式来实现地址映射，这样即使作业的首地址发生变化也不会影响其执行。当作业被选择运行时，其物理空间起始地址被装入基址寄存器中，CPU每执行一条指令之前重定位硬件对指令要访问的地址进行修改。

存储保护

存储保护采用界地址寄存器保护法，即基址、限长寄存器保护法。系统调用作业时先查找内存分配表，找到所分配的分区始址，计算出其物理地址所对应的绝对地址，执行一条有关地址的指令，由硬件检查是否越界，决定继续访问或产生越界中断处理。具体过程见图3.8

可变分区的特点可变分区使多道程序得以提高，从而提高了内存的利用率，但作业的大小仍然受内存容量的限制，会使内存产生一些不可再利用的空间。

分区的始址分区的终址CPU基址寄存器限长寄存器内存+＞否是越界中断逻辑地址物理地址图3.8可变分区存储管理的地址转换3.2.4碎片与拼接技术

碎片（零头）在分区分配方式中经过不断地分配和释放后，内存中空闲分区会变得越来越多和越来越小，产生了许多碎片。所谓碎片是指内存中出现的一些零散的小空闲区域。由于碎片都很小，故无法再利用。如果内存中碎片很多，将会造成严重的存储资源浪费。

拼接（紧凑/紧缩/移动）技术碎片产生后应及时解决。解决碎片的方法是移动所有的占用区域，使所有的空闲区合并成一片连续区域，这一技术称为移动技术（拼接）。移动技术可解决碎片问题，从而提高内存的利用率移动技术可以集中分散的空闲区，便于作业动态扩充内存3.3离散分配存储管理

根据前面的介绍，连续分配方式会形成许多“碎片”，即使通过“紧凑”方法将碎片拼接成可用的大块空间，但须为此付出很大开销。如果将一个进程直接分散到若干个不相邻的分区中，就可以不再进行“紧凑”，于是基于这个思想就产生了离散分配存储管理方式。根据离散分配时所用基本单位的不同，又可把离散分配方式分以下三种：1.页式存储管理2.段式存储管理3.段页式存储管理

3.3.1页式存储管理分区存储管理方法最大的问题是要求必须把作业放在一个连续的存储区域中，这样就会产生“碎片”问题。尽管通过某种方法可以解决这一问题，可将会产生很大代价。而页式存储管理可以很好地解决这个问题。

页式存储管理的实现思想

1.将用户作业的地址空间划分成若干大小相等的区域，称为页或页面；

2.将主存空间划分为与“页”大小相同的若干区域，称为块或物理块；

3.操作系统为某作业分配内存空间时，总是以块为单位来分配，可以将作业中的任何一页放到主存中的任意一块中；

4.在调度作业运行时，必须将它的所有页面一次性调入内存中；若内存中无足够的物理块，则其必须等待。

页式存储的数据结构1.页面和页框在分页存储管理方式中，每一个进程的逻辑地址空间被分成若干个大小相等的片，这些片成为页面或页。相应的，主存空间也被分成和页同样大小的若干个存储块，称为物理块或页框（Frame），如图3.9所示，在为进程分配内存时，以块为单位给每页分配一个物理块，将进程中的若干页分别装入若干个不相邻的块中，由于页的大小与块的大小相同，这样可以有效地消除零头。在某些特殊情况下，进程的最后一页常常装不满一块，而形成不可利用的碎片，称为“页内碎片”。2.页表(PageTable)

系统为每个作业（进程）建立一张页表，页表放在内存中。作业地址空间的每一页与页表中的一个表项对应，其中记录了相应页在内存中对应的物理块号。在页表的表项中增加一个存取控制字段，当存取字段只有一位时，规定其内容是允许读/写、还是只读；当存取字段为二位时，则可以规定为读/写、只读或只执行。如果程序的操作与存取字段中的内容不相符，则引起操作系统的一次中断，从而实现保护。0123456789…第0页第1页第2页……第n页用户作业02427…………页表页号块号内存物理块图3.9页表作用示意图块号3.逻辑地址结构逻辑地址由页号P和页内地址W两部分组成，图3.10页式存储管理中的逻辑地址结构3112110

页号P页内位移W

图中，两部分的地址长度共为32位，其中0-11位为页内地址，即每页的大小为4KB；12--31位为页号，地址空间最多允许有1MB页。对于某特定的机器，其地址结构是一定的，若给定地