操作系统-串讲讲义北工大版课件

操作系统原理操作系统原理1

第一章操作系统概论第二章进程管理第三章内存管理第四章设备管理第五章文件管理和作业管理操作系统原理

2第一节操作系统的概念一、什么是操作系统计算机硬件操作系统实用程序应用程序操作系统设计着程序员终端用户定义：

操作系统是一个系统软件，它管理计算机系统中的软件和硬件资源，在计算机硬件和用户之间起到一个接口作用。.程序图标显示、双击鼠标动作，命令行.文件复制、磁盘内容察看、建立文件.INT中断语句进行系统调用.通过IE下载文件的同时可编辑另一个文本文件？第一节操作系统的概念一、什么是操作系统计算机硬件操作系统3第二节操作系统的功能一、进程管理

进程管理主要是对处理机进行管理。CPU是计算机中最宝贵的硬件资源。为了提高CPU的利用率，操作系统采用了多道程序技术。当一个程序因等待某一条件而不能运行下去时，就把处理机占用权转交给另外一个可运行程序。或者，当出现了一个比当前运行的程序更重要的可运行程序时，后者应能抢占CPU。为了描述多道程序的并发执行，就引入了进程的概念。通过进程管理协调多道程序之间的关系，解决处理机实施分配策略，使CPU资源得到最充分的利用。正是由于操作系统对处理机分配策略的不同，从而呈现在用户面前的就是具有不同性质的操作系统，例如批处理方式、分时处理方式和实时处理方式等。二、内存管理

存储器管理主要管理内存资源。它包括以下几点：

1）内存分配：在内存中除了OS、其他系统软件外，还有一个或多个用户程序，OS要解决分配问题，使其互不冲突。第二节操作系统的功能一、进程管理进程管理主要是4

2）存储保护：由于系统中有多个程序，要保证他们之间互部干扰，保证用

户程序不破坏系统程序。

设备管理是指对计算机系统中的所有输入输出设备的管理。它不仅涵盖进行实际I/O操作的设备，还涵盖了控制器、通道等I/O支持设备。

存容量时，就要把内存和外存结合起来，为用户提供一个比

实际内存大的多的虚拟存储器。

三、设备管理

3）内存扩充：当用户作业所需要的内存量超过计算机系统所提供的实际内四、文件管理

系统中的信息资源（程序和数据）是以文件的形式存放在外存储器上

的，需要时再将其装入。文件管理的任务就是有效支持文件存储、检索修改，解决文件共享、保密和保护，以方便用户安全、方便地访问文件。五、用户接口

1）程序级：提供一组广义指令供用户程序调用。

2）作业级：提供一组控制操作命令供用户去组织、控制自己的作业执行。第一节作业的基本概念2）存储保护：由于系统中有多个程序，要保证他们之间5如同任何其他事物一样，操作系统也有它的诞生、成长和发展过程。为了更清楚地把握操作系统的实质，了解操作系统的发展是很有必要的，因为操作系统的许多概念都是在操作系统的发展过程中出现并逐步得到发展和成熟的。一、手工操作在第一代计算机时期，构成计算机的主要器件是电子管，计算机运行速度慢，没有操作系统。用户直接用机器语言编制程序，并在上机时独占全部计算机资源，用户既是程序员，又是操作员。穿孔->纸带（卡片）装上输入机->程序和数据送入计算机->控制台开关启动程序运行->计算->输出结果->取走指带。操作过程第三节操作系统的发展历史如同任何其他事物一样，操作系统也有它的诞生、成长和6二、批处理

20世纪50年代晶体管计算机出现，开始出现各种高级语言，操作人员、程序人员和维护人员开始有了明确分工。程序员穿孔操作员计算机室卡片盒

许多机时被操作员在机房里走来走去的过程浪费了。二、批处理程序员穿孔操作员计算机室卡片盒许多机7

由于处理器速度的提高，造成手工操作的输入输出与计算机处理速度的不匹配现象。因此，人们设计了监督程序（或称为管理程序）来实现作业的自动转换处理。程序员将数据、程序以及用作业语言书写的作业说明书作为作业信息提交给操作员，操作员将这些作业信息“成批”地输入到计算机中，有监督程序识别每一个作业进行处理。这种自动定序的处理方式称为“批处理”监督程序标准输入程序编译程序装配程序标准输出和处理程序输入用户作业程序编译后的用户作业程序装配好的用户作业程序执行、输出结果调用子程序转到下一个作业由于处理器速度的提高，造成手工操作的输入输出与计8三、多道程序系统第二代计算机后期，特别是计算机进入第三代以后，系统软件和硬件都有了很大发展，特别是主存容量的增大以及大容量辅助存储器的出现，这一切都使得计算机体系结构发生了很大变化。由以中央处理器为中心的结构改变为以主存为中心，而通道使得输入输出操作与CPU操作的并行处理成为可能。所谓多道是指允许多个程序同时存在于主存中，由中央处理器以切换方式为之服务，使得多个程序可以同时执行，计算机资源不再被某一个用户所独占。待处理程序存入外存形成程序队列作业调度几个程序进入内存有作业完成再调度三、多道程序系统第二代计算机后期，特别是计算机进9

多道程序的引入，使得不同用户的多道程序可以同时在系统内存并行运行，同时它们共享计算机的资源，并行和共享思想的引入大大增加了系统的复杂性。如，如何分配和管理内存、处理机如何调度以及外部设备如何分配等等。这些问题都需要一个复杂的管理机构合理有效地进行管理。它就是操作系统。

随着计算机的发展，硬件价格越来越低,人们开始关注计算机使用的方便性，也就是说如何提高和增加计算机的人-机对话功能，因此很快就出现了分时系统。这种系统是在一台计算机上挂若干台联机终端，用户通过自己的终端与计算机对话来控制、调试、干预他的程序。而系统则是将处理机的时间划分为小的时间间隔（又称时间片），轮流地为每个终端上的作业服务，使每个用户都感觉好象自己在使用计算机。

多道和分时系统的出现，标志着操作系统的正式形成。四、操作系统的形成多道程序的引入，使得不同用户的多道程序可以同时在10五、操作系统的分类根据操作系统在用户界面的使用环境和功能特征的不同，操作系统一般可分为三种基本类型，即批处理系统、分时系统和实时系统。随着计算机体系结构的发展，又出现了个人操作系统、网络操作系统和分布式操作系统。1、批处理操作系统（BatchProcessing)

批处理操作系统的工作方式是：用户将作业交给系统操作员，系统操作员将许多用户作业组成一批作业，输入到计算机中，在系统中形成一个自动转接的连续的作业流，然后启动操作系统，系统自动、依次执行每个作业。最后由操作员将作业结果交给用户。优点：作业流自动化；效率高；吞吐率高。缺点：无交互手段；调试程序困难。五、操作系统的分类根据操作系统在用户界面的使用环境112、分时操作系统（TimeSharing)

分时操作系统的工作方式是：一台主机连接了若干终端，每个终端有一个用户在使用。用户交互地向系统提出命令请求，系统采用时间片轮转法方式处理服务请求，并通过交互方式在终端上向用户显示结果。

分时系统具有多路性、交互性、“独占”性和及时性的特征：

多路性：宏观上看多人同时使用一个CPU;

交互性：用户根据系统响应结果进一步提出新请求；

“独占”性：用户感觉不到计算机为其他用户服务;

及时性：系统对用户提出的请求及时响应。3、实时操作系统（RealTimeOperationSystem)

实时操作系统是指计算机能及时响应外部事件的请求，在规定的严格时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致地工作的操作系统。2、分时操作系统（TimeSharing)124、个人计算机操作系统（PersonOperationSystem)

个人计算机系统是一种单用户多任务的操作系统。它主要供个人使用，功能强、价格便宜。其特点是采用图形界面人机交互的工作方式；使用方便。Dos是单用户单任务操作系统，早期Windows是单用户多任务操作系统。5、网络操作系统（NetworkOperationSystem)

网络操作系统是基于计算机网络的一种操作系统，是在各种计算机操作系统之上按网络体系结构协议标准开发的软件，包括网络管理、通讯、安全、资源共享和各种网络应用。其主要目标是计算机之间的相互通讯和资源共享。因为现代操作系统的主要特征之一就是网络功能，因此，除了20世纪90年代初期时，Novell公司的Netware系统被称为网络操作系统之外，人们一般不再特指某个操作系统为网络操作系统4、个人计算机操作系统（PersonOperation136、分布式操作系统（DistributedOperationSystem)大量的计算机通过网络被连接在一起，可以获得极高的运算能力和广泛的数据共享。这种系统被称为分布式操作系统。

分布式操作系统具有：统一性、共享性、“透明性和自治性的特征：

统一性：它是一个统一的操作系统;

共享性：所有的分布式系统中的资源是共享的；

透明性：用户并不知道某一操作具体运行在哪一台计算机。

自治性：分布式系统中的多个主机都处于平等地位。

网络操作系统和分布式操作系统在概念上的区别是：网络操作系统可以构架于不同的操作系统之上，通过网络协议实现网络资源的统一配置，需要显式地指明资源位置与类型，对本地资源和异地资源的访问要区别对待。分布式强调单一性，它是一种操作系统构架的。所有资源用同一方式管理和访问，不必关心资源在哪，怎样存储。6、分布式操作系统（DistributedOperatio14第二章进程管理•进程是什么•进程的状态如何•进程的互斥与同步•进程的通讯方式•操作系统如何解决进程死锁问题第二章进程管理•进程是什么15第一节进程的基本概念通常，操作系统的重要任务之一是使用户充分、有效地利用系统中的资源，那么采用一个什么样的概念来描述用户程序的执行过程和作为资源分配的基本单位才能充分反映操作系统的并发执行、资源共享呢？这个概念就是进程。第一节进程的基本概念通常，操作系统的重要任务16一、进程的定义

进程：是一个具有独立功能的程序段对某个数据集在处理机上的执行过程和分配资源的基本单位。进程的概念是60年代初期首先在IBM的TTS/360系统中引用，人们对进程下过许多各式各样的定义：（1）进程是可以并行执行的计算部分；（2）进程是一个独立的可以调度的活动；（3）进程是一实体，当它执行某个任务时，将要分配和释放各种资源。以上定义尽管各有侧重，但在本质上是相同的，即主要注重进程是一个动态的执行过程，因此我们给出进程的一般性定义。一、进程的定义进程：是一个具有独立功能的程序段对某个数据17进程、程序的区别和关系：

b.进程具有并行特征，而程序则没有。因为程序不反映执行过程c.进程是竞争计算机系统资源的基本单位，从而其并行性受到系统的制约。d.不同的进程可以属于同一程序，只要该程序所对应的数据集不同。a.进程反映的是一个动态概念，而程序是一个静态概念；程序是指令的有序集合，没有任何执行的含义，而进程则强调的是执行过程，它动态被创建、执行和消亡。如程序是菜谱，则进程就是按照菜谱炒菜的过程。进程、程序的区别和关系：c.进程是竞争计算机18第二节进程的描述一个进程是一个程序对某一个数据集的执行过程，是分配资源的基本单位。那么，从处理机的活动角度来看，又如何识别和描述程序执行活动的进程呢？很显然，系统中需要有描述进程存在和能够反映其变化的物理实体，即进程的静态描述。进程控制块PCB包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映。系统根据PCB感知进程的存在和通过PCB中所包含的各项变量的变化，掌握进程所处的状态以达到控制进程活动的目的。由于进程的PCB是系统感知进程的唯一实体，所以进程的PCB结构几乎是常驻内存的。

进程的静态描述由三部分组成：进程控制块PCB(ProcessControlBlock)，有关程序段和该程序段对其进行操作的数据结构集。第二节进程的描述一个进程是一个程序对某一个数19进程的程序部分是描述进程所要完成的功能；数据结构集是程序在执行时必不可少的工作区和操作对象。这两部分是进程完成所需功能的物质基础，通常它们放在外存，直到进程执行时再调入内存。进程描述进程控制块PCB有关程序段数据结构集进程的程序部分是描述进程所要完成的功能；进程描述20一、进程控制块PCB一般来说，不同的操作系统，PCB表所包含的内容多少有所不同，但总的来说还是大致相同的。1、描述信息

进程的描述信息包括：进程名、用户名、家族关系。进程名就是进程标识号，每个进程都有一个唯一的名称。用户名就是指出该进程是隶属于哪个用户的。家族关系是指该进程的父进程是谁，即谁创建了该进程。

PCB块集中反映一个进程的动态特征。在进程并发执行时，由于资源共享，带来各进程之间的相互制约。很显然，为了反映这些制约关系和资源共享关系，在创建一个进程时，应首先创建它的PCB，然后才能根据PCB中的信息对进程实施有效的管理和控制。也就是说，PCB随着进程的创建而创建，随着进程的撤消而消亡。一、进程控制块PCB一般来说，不同的操作系统，P212、控制信息

控制信息包括：进程当前状态、进程优先级、程序开始地址、各种计时信息、通讯信息。进程当前状态说明进程当前处于何种状态。进程在活动期间可分为就绪态、执行态和等待状态。就绪态该进程准备占有处理机；执行态表示该进程正在占有处理机；而等待状态则表示进程因某种原因不能占有处理机。进程优先级是选取进程占有处理机的重要依据。程序开始地址规定该进程对应的程序段以此地址开始运行。各种计时信息给出进程占有和利用资源的有关情况。通讯信息用来说明该进程在执行过程中与别的进程所发生的信息交换情况。2、控制信息控制信息包括：进程当前状态、进程优先级、程223、资源管理信息资源管理信息包括：

（1）占用内存大小、指针；（页表指针）；（2）对换或覆盖用有关信息（对换程序段长度、外存地址），这些信息在申请、释放内存中使用；（3）共享程序段的大小及起始地址；（4）输入输出设备的设备号，所要传送的数据长度、缓冲区地址、及所用设备的有关数据结构指针等，这些信息在进程申请、释放设备以及数据传送中使用；（5）指向文件系统的指针及有关标识等，以便对文件系统操作。3、资源管理信息资源管理信息包括：（2）对换或覆盖用有关信息23第三节进程的状态转换及控制一、进程的状态及转换任何一个事物都有他的生命期，进程也不例外。一个进程的生命期可以划分为一组状态，这些状态刻画了进程的整个生存过程。操作系统根据PCB中的状态值控制进程。

进程在其生命期内被划分为三种基本状态：就绪状态、执行状态、等待状态。就绪状态(Ready)：刚被创建；或者等待事件发生被唤醒；执行状态(Running)：获得处理机的使用权；阻塞状态(Blocked)：等待某个事件的发生（I/O完成）这只是进程的三种基本状态，有的系统可能划分得更细，但都是围绕着三个基本状态划分的。第三节进程的状态转换及控制一、进程的状态及转换24提交调度时间片到等待某个事件（内存、设备等）等待事件发生就绪执行阻塞提交调度时间片到等待某个事件等待事件发生就绪执行阻塞25

除此之外，在有的系统中，将进程的状态进一步细分为五个状态，除了上述三个状态之外，增加了创建和退出两个状态。创建状态（New)：进程还在创建过程中，还不能运行。这时，操作系统要建立PCB、建立资源表、分配资源、建立地址空间表。退出状态（Exit)：进程运行结束，系统回收所占用资源。创建创建提交就绪调度执行释放退出等待事件阻塞事件出现超时除此之外，在有的系统中，将进程的状态进一步细分26二、进程的控制所谓进程控制，就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态之间的转换，从而达到高效率并发执行和实现资源共享的目的。用于进程控制的程序段有什么要求呢？我们引入原语的概念。

原语：在系统状态下执行的具有特定功能的程序段称为原语，且它们在执行期间不允许被中断、不允许并发执行。1）创建原语：就是系统为进程创建一个进程控制块PCB,并填写PCB中相应信息项的过程。二、进程的控制所谓进程控制，就是系统使用一些具272）撤消原语：就是系统释放进程所占有的各种资源和PCB结构本身。导致进程撤消的原因有多种：

a.该进程已完成所要求的功能而正常终止；

b.该进程由于某种错误导致非正常终止；

c.祖先进程要求撤消某个子进程；2）撤消原语：就是系统释放进程所占有的各种资源和PCB结构本283）阻塞原语：在一个进程期待某一事件发生，但发生条件尚不具备时，进程调用该原语阻塞自己。

入口保存当前进程CPU现场置进程状态为“阻塞”被阻塞进程入等待队列转进程调度

进程阻塞时，正处于执行状态，故先要保存CPU现场(PCB中）；另外最后转进程调度程序是很重要的，否则，处理机将会出现空转现象。3）阻塞原语：在一个进程期待某一事件发生，但发生条件入口保存294）唤醒原语：当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都将被唤醒。但进程本身不能自己唤醒自己，有两种方法：

a.系统唤醒：系统统一管理和控制事件的发生，并将“发生”这一消息通知所有等待进程，而使他们进入就绪队列。b.事件发生进程唤醒唤醒：等待进程有事件发生进程唤醒，这时，事件发生进程和被唤醒进程之间是合作关系。入口从等待队列中摘下被唤醒进程将被唤醒进程置为就绪状态将被唤醒进程送入就绪队列转进程调度4）唤醒原语：当等待队列中的进程所等待的事件发生时，a.系30第四节进程互斥前面我们已讲过，进程在执行时，各进程具有独立性和异步性等并行特征。但是，在计算机系统中，由于资源的有限必然导致进程之间对资源既有共享、又有竞争。因此并发进程的执行不仅仅是用户程序开始时间的随机性和资源利用率的问题，同时也造成了进程之间的相互制约。一、资源共享引起的进程制约从例题中可以看出，系统中进程相互影响的原因有二：

a.系统内的进程共享资源（Diskreq队列，Insert程序段）；

b.为完成同一任务的进程之间要进行协作（PHF和IOS)；

因此，我们给出两个定义：临界资源和临界区。第四节进程互斥前面我们已讲过，进程在执行时，311、临界资源和临界区临界资源：是指一次仅允许一个进程使用的资源。（CriticalResource)（Diskreq队列)临界区：最多只允许一个进程访问的程序段。（CriticalSection)（Insert程序段)2、进程互斥

定义：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即，不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。1、临界资源和临界区临界资源：是指一次仅允许一个进程使用的资323、并发进程互斥执行准则：1）有空即进。并发进程中的某个进程不在临界区时，它不阻止其它进程进入临界区。2）择一而入。并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。3）限时进入。并发进程中的某个进程申请进入临界区开始，应在有限时间内得以进入临界区。3、并发进程互斥执行准则：1）有空即进。并发进程中的某个进程33二、互斥方法进程互斥的解决方法有两种：一是由竞争各方平等协商；二是引入进程管理者，由管理者协调竞争各方对临界资源的使用。

为了保证临界资源的正确使用，我们可把临界资源的访问过程分成四部分：进入区退出区a.进入区：检查可否进入临界区；可进入，设置响应的标志，阻止其他进程。b.临界区：进程中访问临界资源的一段代码。c.退出区：将访问标志清除。d.退出区：代码中的其余部分。

临界区

剩余区二、互斥方法进程互斥的解决方法有两种：一是由竞争34信号量和P、V原语前面的互斥算法都是平等进程间的协商机制，它们存在的问题是平等协商无法解决时，需要引入一个管理者来解决公有资源的使用问题。信号量（Semaphore)就是由操作系统提供的管理公有资源的有效手段。1）信号量信号量是一个整数，代表系统中可用资源实体的数量。信号量Sem>=0表示可用临界资源的实体数；<0表示等待使用该临界资源的进程数信号量和P、V原语前面的互斥算法都是平等进程间的协352）P、V原语

P、V是对信号量操作的两个原语操作，其中P原语操作使信号量减1，V原语操作使信号量加1。

假设系统中有一共有资源为S,并在系统中设有表示其实体数量的计数器Count和进程等待队列Queue,P、V原语操作描述如下：P(S){--S.Count;if(S.Count<0){阻塞调用进程；进程进入等待队列S.Queue;}}

入口--S.CountS.Count>=0置进程为“阻塞”进入等待队列转进程调度返回YN2）P、V原语P、V是对信号量操作的两个原语操作36入口++S.CountS.Count<0唤醒等待队列中的一个进程转进程调度返回NYV(S){++S.Count;if(S.Count<0){从等待队列S.Queue

中取出一个进程；将该进程入就绪队列；}}入口++S.CountS.Count<0唤醒等待队列中的一个373）用P、V原语实现进程互斥通过我们对临界区访问过程的分析，信号量机制中P原语相当于进入区操作，V原语相当于退出区操作。用P、V原语实现进程互斥就是将临界区置于P和V两个原语操作之间，进入时执行P操作，使信号量Sem减1，如果Sem>=0,则进入临界区，否则不可进入。进程退出临界区时，执行V操作，使信号量Sem+1，表示释放临界资源。设置互斥信号量Sem，并赋初值为1

Sem=1,资源未被占用；

Sem=0,资源被占用；

Sem<0,资源被占用，且有等待进程。b.描述：P(Sem);临界区V(Sem)剩余区3）用P、V原语实现进程互斥通过我们对临界区访问384）进程互斥举例例1：设有三个进程A、B、C需共享一个临界资源，用P、V操作写出其算法。SemaphoreSem=1;VoidP(){while(true){P(Sem);

使用临界区；

V(Sem);}}VoidMain{ParbeginPa,Pb,Pc}SemPaPbPc1P(Sem)0P(Sem)-1P(Sem)-2V(Sem)-1V(Sem)0V(Sem)14）进程互斥举例例1：设有三个进程A、B、C需共享一个临界资39例3、读者-写者问题（Reader-WriterProblem)在计算机系统中当若干个并发进程都要访问某个共享文件时应区分是读还是写。显然可允许多个进程同时读文件，不允许在进程读文件时让另外一进程去写文件，或者有进程在写文件时让另外一个进程去读该文件，更不允许多个外进程同时写同一文件。因此读-写进程之间关系为：“读-写”互斥、“写-写”互斥和“读-读”允许。另外，因为允许多个进程同时读，系统应记录读进程的个数，而每个读进程去读文件或读文件结束后都要修改读者个数，因此，读者个数又是若干读进程的共享变量，即软件临界资源，它们也必须互斥地修改这个变量。

综上所述，我们定义两个互斥信号量和一个公共变量：Wmutex用于“读-写”和“写-写”互斥；Rmutex用于若干读进程对读者个数修改的互斥；公共变量RCount用于记录当前正在读文件的读者数目。例3、读者-写者问题（Reader-WriterProbl40过程描述：BeginWmutex,Rmutex:semaphore;Rcount:integer;Wmutex=Rmutex=1;Rcount=0;

ProcessReader(I)Begin++Rcount;

ifRcount=0

thenV(Rmutex);ReadFile;P(Rmutex);--Rcount;IfRcount=0ThenV(Rmutex);End;ProcessWriter(I)BeginP(Wmutex);WriteFile;V(Wmutex);End;End;P(Rmutex);P(Wmutex);V(Wmutex);过程描述：BeginWmutex,Rmutex:sema41第五节进程同步一、同步的概念上一节我们介绍了并发进程对系统公有资源的竞争，从而引出了进程互斥的概念以及解决的办法，并发进程之间是否还存在其他制约关系呢？这就是同步问题。

例：设有计算和打印两个进程Pc和Pp,共同使用同一缓冲区Buffer，Pc向Buffer中存放计算结果，Pp从Buffer取计算结果送打印机输出。PcPpBuffer

这两个进程的执行是相互制约的。即Pc的执行结果是Pp的执行条件；而Pp的执行结果也是Pc的执行条件，它们是相互制约的。

我们把一组在异步环境中由于以各自的执行结果而限制其它进程的执行速度的现象称为并发进程的直接制约，解决这种直接制约的方法称为同步。（假设互斥已解决）第五节进程同步一、同步的概念上一节我们介绍了并42二、私有信号量前面讲到进程互斥引入了信号量的概念，它是与所有并发进程都相关的，因此我们称其为公有信号量。那么在进程同步中，我们同样也引入信号量的概念，但它只是与制约进程和被制约进程有关，并不涉及所有的并发进程，因此我们称其为私有信号量。上面计算进程和打印进程是相互制约的，让双方互相发送条件已经具备的信号，以协调两进程的运行，描述如下：PcA:Wait(Bufferempty)计算；计算结果送缓冲区；Bufferfull=true;Signal(Bufferfull);GotoA;PpB:Wait(Bufferfull);

打印缓冲区中的数据；Bufferempty=true;

Signal(Bufferempty);

GotoB;二、私有信号量前面讲到进程互斥引入了信号量的概念，43三、用P、V原语实现进程同步

a.为并发进程设置私有信号量；

b.为私有信号量赋初值；

c.用P、V原语和私有信号量实现同步。上面例子中，我们假设缓冲区大小为n,同步过程如下：a.设Bufferempty为Pc进程的私有信号量，

Bufferfull为Pp进程的私有信号量，b.赋初值；Bufferempty=n,Bufferfull=0;c.实现：Pc:Deposit(data)

beginP(Bufferempty)DataBuffer[I];V(Bufferfull);end;Pp:Remove(data)

beginP(Bufferfull);Buffer[I]Data;V(Bufferempty);end;三、用P、V原语实现进程同步a.为并发进程设置私有信号量44四、进程互斥、同步的应用1.生产-消费者问题（Producer-ConsumerProblem)如果把并发进程的互斥和同步问题一般化，我们可以得出一个抽象化的一般模型，即生产-消费者问题。在计算机系统中，每个进程都可以申请和释放各种不同类型的资源。通常把系统中申请资源的进程称为消费者，而释放资源的进程称为生产者。众多并发进程共同存在于系统之中，必然要解决它们之间的互斥和同步问题。如果我们把前面讲述的计算进程Pc和打印进程Pp互斥和同步同时考虑，就是我们要讨论的生产-消费者问题。

a.设置公有信号量mutex，以实现互斥；

b.设置私有信号量empty和full，以实现同步；

c.赋初值：empty=n,full=0,mutex=1;

d.实现deposit和remove.四、进程互斥、同步的应用1.生产-消费者问题（Produce45Deposit(data)BeginP(empty);P(mutex);dataBufferunit[I];V(mutex);V(full);End;Remove(data)BeginP(full);P(mutex);V(mutex);V(empty);End;（生产）Bufferunit[I]data;（消费）注意：P、V顺序。

Deposit(data)BeginP(empty);P(m46第六节进程通讯一、进程通信方式

进程之间的通讯也就是进程之间进行信息、数据的交换。这种信息、数据的交换一般有两种：控制信息和大批量信息或数据。我们把进程之间控制信息的交换称为低级通讯；而把大批量信息、数据的交换称为高级通讯。前面我们所接触到的为了实现进程之间的同步，进程之间需要传递私有信号量，它是属于为了控制进程的执行速度而进行的低级通讯。下面我们介绍进程高级通讯的两种方式：消息缓冲机制和信箱机制。a.消息缓冲方式；

b.信箱方式。

第六节进程通讯一、进程通信方式进程之间的通讯47一、消息缓冲机制

它的基本思想是由系统统一管理一组缓冲存储区，其中每一个缓冲区存放一个消息。当发送进程要发送消息时，先想系统申请一缓冲区，然后把消息写进去，接着再把该缓冲区送到接收进程的一个消息队列中。接收进程则在适当时机从消息队列中去走所需消息，然后释放缓冲区。由于消息缓冲机制所使用的缓冲区为公用缓冲区，两个通讯进程必须满足如下条件：

a.发送进程只有申请到空缓冲区，才能发送消息。

b.消息队列无消息时，接收进程不能接收到任何信息。

c.各进程对消息队列操作时，必须互斥。发送与发送，发送与接收，接收与接收。一、消息缓冲机制它的基本思想是由系统统一管理一组缓冲481、消息缓冲区的结构发送进程名消息长度消息正文指针消息缓冲区发送消息的进程名或标示符消息的长度消息的正文指向下一个消息缓冲区的指针2、进程PCB增加内容PCB增加内容Pm:指向进程接收到的消息队列队首的指针Mutex:用于消息队列操作的互斥信号量。消息队列属于临界资源，进程需互斥进行操作。Sem:用于接收进程和发送进程之间实现同步。其值表示接收进程消息队列中的消息个数。接收消息的进程名或标示符接收进程名1、消息缓冲区的结构发送进程名消息长度消息正文指针消息缓冲区493、Send和Receive原语发送进程A接收进程B的PCB接收进程B………..Send(B,消息)………..接收进程名B消息长度Size消息正文Text缓冲区指针………..………..……………队首指针PmMutex,Sem…………………………Next接收进程名B消息长度Size消息正文TextNil………..Receive(A,消息)………..接收进程名B消息长度Size消息正文Text缓冲区指针………..………..………..发送进程名A发送进程名A发送进程名A3、Send和Receive原语发送进程A接收进程B的PCB50Send(Receiver,信件）向系统申请消息缓冲区；将所要发送消息复制到消息缓冲区；查找Receiver进程的PCB表；

P(Mutex);将消息缓冲区链接到Receiver的PCB链上；

V(Mutex);

V(Sem);返回;Receiver(Sender,信件）P(Sem)；

P(Mutex)；取消息链上Receiver进程发出的消息；将此消息复制到接收进程的接收区内;释放缓冲区；

V(Mutex);返回;Send(Receiver,信件）向系统申请消息缓冲区；将51二、信箱方式消息缓冲方式是系统统一管理空缓冲区，为系统中所有进程共享。而信箱方式是指在发送进程和接收进程之间建立一个邮箱实现信息通信的一种方式，也就是说邮箱是发送进程和接收进程的私有数据结构。

信箱信箱头：信箱名称、大小、传输方向、拥有该信箱的进程名等信箱体：存放信件。分成若干块，一块存放一个信件。（信箱数据结构定义及发送（SEND）、接收（RECEIVE）原语见书51）。二、信箱方式消息缓冲方式是系统统一管理空缓冲区，为系52第七节死锁一、死锁的产生前面我们介绍了多道程序环境下并发程序的执行带来的众多问题，这一节继续讨论另外一个问题—死锁。12341234例1：交通死锁第七节死锁一、死锁的产生前面我们介绍了多道程序环53二、死锁的定义在多道程序系统中，由于程序的并发执行，虽然提高了系统资源的利用率和系统的处理能力，但也带来了一些新的问题，如我们前面讲的互斥、同步等问题，除此之外，也可能会出现一种更危险的情况：当某一进程提出资源的使用请求后，使得系统中的一些进程处于无休止的阻塞状态，在无外力的作用下，这些进程永远都不能前进。因此我们给出死锁的定义。

死锁：是指并发进程彼此互相等待对方占有的资源，而这些进程在得到对方占有的资源之前又不会释放自己占有资源，从而造成进程永远无法执行的状态，死锁不仅会给系统造成资源的浪费，甚至导致整个系统崩溃，因此我们分析一下造成死锁的因素。二、死锁的定义在多道程序系统中，由于程序的并发执54二、造成死锁的因素1)具有多个进程。多道程序环境的特点。2)多个资源。同类型资源多个单位；不同类型资源多个种类，如果只有一个资源，只要互斥使用即可。3)部分分配。对各进程所需资源只分配一部分，否则无死锁。4)申请与释放资源的动态性、分散性和独立性。动态性是指进程申请、释放资源的随机性；分散性是指进程获取资源后自己释放，系统无权干涉；独立性是指资源分配与使用的分离，进程得到资源后并不一定一直使用，也可能闲置，但其他进程却无法使用。

以上因素反映了多道程序环境下并发进程与有限资源多种矛盾，因此必须解决这些矛盾，使系统有条不紊地运行。二、造成死锁的因素1)具有多个进程。多道程序环境的特点。255三、死锁产生的条件

死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。但是可以采用适当的算法，达到消除死锁的目的。1)互斥。任何资源在任何时刻只能被一个进程使用。3)占有且等待。进程在等待申请资源的过程中，原占有资源保持不变。4)循环等待。发生死锁时，系统中必存在一进程循环等待链即前一进程占有着后一进程所要求的资源。2)非剥夺。进程占有的资源，该进程以外的进程不得抢占，只能由占有者释放。三、死锁产生的条件死锁的起因是并发进程的资源竞争56四、死锁的解决方法

上面四条是死锁产生的必要条件，若同时满足了这四个条件死锁便产生了。解决死锁的方法一般可分为预防、避免、检测和恢复等三种。1、死锁的预防

死锁的预防就是预先防止死锁的发生，那么只要破坏死锁产生的四个必要条件中任何一条就可以预防死锁的产生。

a.破坏互斥。就是说允许一个资源可由多个进程同时使用，

但系统中多数资源必须互斥使用，此法不宜使用。

b.破坏非剥夺。当某进程申请某一互斥资源时，如被拒绝，则在进程进入阻塞状态前由操作系统剥夺或自行释放已占有的所有资源，待以后系统再行分配。但为了保护进程资源现场和以后的再次恢复，系统需付出高昂代价。四、死锁的解决方法上面四条是死锁产生的必要条件57

c.破坏占有且等待或循环等待。为达到此目的，可以采用资源静态分配和层次（顺序）分配两种方式：*静态分配方式

静态分配是指一个进程在被创建时就赋予它全部所需的资源，只有在该进程所需的资源都得到满足的条件下，进程才开始执行。

此策略可以破坏占有且等待条件，可以预防死锁。但这种策略严重地降低了资源的利用率。因为这些被占有资源有的到进程执行的后半期才被使用，甚至只有例外的情况下才被用到，而其它进程又申请不到这些被占有资源。因此这种方式是低效的，原因有三：

•进程因等待所需要的资源阻塞时间过长，一部分即可；

•部分资源可能在相当长的时间内变得不可用；

•进程一次性知道所需全部资源不太可能。c.破坏占有且等待或循环等待。为达到此目的，可以采用资58*层次（顺序）分配方式

层次分配方式的基本思想是将系统中的资源分成若干个层次，每个层次中包含有若干个资源。

•某进程得到某一层的一个资源后，它只能再申请本层次或比本层次更高一层的资源；

•释放资源时，先释放较高层次的资源，后释放较低层次的资源；

•一个进程得到某一层的资源后，若想再申请该层中的另一资源时，必须先释放该层中已占有的所有其它资源。

此种策略可防止循环等待情况的发生。此策略的一种特例就是将系统资源排成一个序列：RS1,RS2,…..RSn,某进程申请了RSi(1<=I<=n)后不得再申请RSj(j<i)。如系统中：#1:卡片读入机，#2:打印机，#3:绘图仪，#4:磁带输入机。申请：卡片读入机，绘图仪，磁带输入机予以分配。申请：打印机，卡片读入机，绘图仪不予分配。*层次（顺序）分配方式层次分配方式的基592、死锁的检测和解除上面讲述的各种方法虽然能很好地对死锁进行预防和避免，但它存在的问题就是资源的利用率不高，况且各种算法会增加系统的开销。因此解决死锁的另一种途径就是对死锁进行检测。基本思想是系统对资源的分配不加任何限制，系统定时判断死锁是否已经出现，若检查出现了死锁，则采取一定措施解除死锁。a.死锁的检测方法

操作系统设置两张表格，一张表记录被阻塞进程等待资源的情况，另一张表记录已占有资源的情况，即哪些进程占有什么资源，我们不妨称其为Table1和Table2。

如果进程申请某一资源时，若该资源空闲，则进行分配，同时将该资源填资源占有情况表，即Table2;否则，阻塞该进程填写进程等待资源表，即Table1。

操作系统定期检查Table1和Table2，如果进程Pi等待Rk资源，而Rk又被Pj进程占用，则认为Pi和Pj因该资源具有等2、死锁的检测和解除上面讲述的各种方法虽然能很好地60待关系，并记为W(Pi,Pj)。系统记下所有等待关系，如果出现如下序列：W(Pi,Pj),W(Pj,Pk),………W(Ps,Pm),W(Pm,Pi)，则操作系统就认为系统中存在一组循环等待资源的进程：Pi,Pj,……Ps,Pm,因而认为出现了死锁。b.死锁的解除方法如果检测到死锁，系统就必须采用某种恢复技术解除死锁：

•结束所有进程，并重新启动操作系统；

•结束所有卷入死锁的进程；

•一次结束卷入死锁的一个进程，然后再次检测直到死锁消失为止；

•从一个或多个卷入死锁的进程中抢占资源，把这些资源分配给卷入死锁的其它进程之一，然后恢复执行；待关系，并记为W(Pi,Pj)。系统记下所有等待关系，如果出61在实际操作系统中，一般都是采用多种方法的组合，而并非采用单一的方法来解决死锁问题，如对资源进行分类，对外设类使用死锁避免的方法，而对存储系统使用预防的方法。总之，解决死锁问题要综合考虑。在实际操作系统中，一般都是采用多种方法的组合，62第八节处理器调度

处理器是计算机系统中的重要资源，处理器调度算法不仅对处理器的利用效率和用户进程的执行有影响，同时还与内存等其他资源的使用密切相关，对整个计算机系统的综合性能指标也有重要影响。一、处理器调度类型

从处理器调度的对象、时间、功能等角度出发，将处理器调度分为宏观调度、中级调度和微观调度三个层次。（1）宏观调度。从用户工作流程的角度，一个作业提交几个流程，其中每个程序按照流程进行调度执行；（2）中级调度。涉及进程在内外存之间的交换。（3）微观调度。也称低级调度，从处理器资源分配的角度来看，处理器需要经常选择就绪进程进入运行状态，因此微观调度的尺度是毫秒级的，宏观调度的尺度是分钟、小时或天，中级调度则是秒级的。第八节处理器调度处理器是计63就绪挂起挂起就绪调度执行释放退出等待事件阻塞事件出现超时阻塞挂起激活事件出现激活挂起提交提交创建宏观调度中级调度微观调度就绪挂起挂起就绪调度执行释放退出等待事件阻塞事件出现超时阻塞64

三、进程调度(处理机调度)算法的功能（1）记录系统中所有进程的执行情况。

a.各进程的执行情况和状态特征记录在各进程的PCB表中；

b.根据各进程的状态特征和资源需求，将各进程的PCB排成相应队列并进行动态队列转换；

c.根据PCB掌握各进程的执行情况和状态特征。三、进程调度(处理机调度)算法的功能（1）记录65（2）选择占有处理机的进程。

按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。（3）进行进程的上下文转换。

进程的执行是在进程的上下文中执行，当正在执行的进程由于某种原因让出处理机时，系统要在该进程的PCB中保留足够的信息，以便该进程的恢复执行，然后调度程序重新选择一个新的处于就绪状态的进程，并装配该进程的上下外文，使CPU控制权转换到被选中进程。四、进程调度的时机(1)正在执行的进程执行完毕；(2)执行中的进程自己调用阻塞原语而进入等待状态；(3)执行中进程调用P原语因资源不足而被阻塞；或调用V原语激活等待资源的等待进程；（2）选择占有处理机的进程。（3）进行进程的上下文转换。四、66(4)在分时系统中时间片用完；(5)在可剥夺方式下，如果就绪队列中的某进程的优先级高于当前执行进程的优先级时，也引发进程调度。五、调度算法

下面讨论几种调度算法，由于算法设计的出发点不同，他们各自适应的场合也不同。有的适合于宏观调度，有的算法则适合于微观调度，而有的则适合于多种场合。1、先来先服务（FirstComeFirstService)顾名思义，其基本思想是按进程的到达先后顺序进行调度。(1)、按照作业提交或进程变为就绪状态的先后次序分派CPU;(2)、当前作业或进程占用CPU，直到执行完或阻塞才让出CPU;(3)、当作业或进程被唤醒，并不立即恢复执行，入就绪队列等待;(4)在分时系统中时间片用完；(5)在可剥夺方式672、优先数法为每个进程设置一个优先数，进程调度程序每次选择就绪队列中优先数最大者占有处理机。确定进程优先数的考虑因素：

a.使用外设频繁着优先数大，提高外设CPU的并行性。b.重要程序优先数大，有利于用户。。

c.进入计算机时间长的优先数大，有利于缩短作业完成时间。

d.交互用户的进程优先数大，有利于终端用户的响应时间。（1）静态优先数法：在创建进程时，操作系统根据优先数的确定原则确定该进程的优先数，而且在进程的生命期内该优先数不再改变，称为静态优先数。确定原则：

a.根据进程的类型确定。系统进程>用户进程；用户进程I/O相关的>其他类型的用户进程；分时系统前台进程>后台进程2、优先数法为每个进程设置一个优先数，进程调度程序68

b.根据进程使用资源的状态确定。根据进程对系统资源的要求，如CPU占用时间、内存大小、I/O设备的使用情况等来确定进程的优先数大小。这种情况有利于短作业或进程。

c.用户自己确定进程的优先数。这种情况适用于同一用户的不同进程，而不同用户的进程还是有操作系统来确定。（2）动态优先数法：

动态优先数方式是指在进程创建时赋予给进程一个优先数，而在进程的运行过程中可以自动改变，以便获得更好的调度性能。影响动态优先数的因素包括进程等待时间和占用处理机时间等。当一个进程在就绪队列中等待时间越长，它的优先数越高；其目的就是使优先数较低的进程在等待一定时间后，逐步提高其优先数，进而被调度执行。（论年头）

当一个进程占用处理机的执行时间越长，其优先数逐步降低，目的是让持续执行的进程在降低优先数后让出处理机。b.根据进程使用资源的状态确定。根据进程对系统资源的要693轮转法：

在分时系统中，如果仍采用上述算法就不合适了。因为优先数低的进程可能会在长时间内的不到CPU的服务，这在分时系统中是绝对不允许的。因为分时系统要求对用户的响应要及时、快速。其基本思想是：系统确定一个适当大小的时间片，所有进程排成一个就绪队列按时间片轮流使用CPU。确定时间片应考虑的因素：

a.系统的响应时间；进程数一定，时间片与响应时间成正比；

b.就绪队列中进程数；系统响应时间一定时，时间片与进程就绪队列中的数目成反比，用户越多，时间片应越小，反之越大；

c.进程的切换时间；设计时确定一个标准，如1/10；

d.CPU的执行速度；如果CPU速度快，时间片长，反之则短；3轮转法：在分时系统中，如果仍采用上述算法就不70时间片计算公式：Q=T/N;其中Q为时间片大小，T为响应时间，N为就绪队列中进程的个数。

这种固定时间片法简单有效，但有时为提高CPU效率、减少进程切换次数降低系统开销，又可采用可变时间片轮转法。它的基本思想是：每当一轮调度开始时，系统便根据就绪队列中现有进程的数目计算一次时间片，作为新一轮调度的时间片。这样对减少系统开销和提高响应时间都是有利的。4多级队列法：

多级队列法就是引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标。如将系统进程、用户进程、批处理进程分别入不同的就绪队列，不同队列的优先级、时间片、调度策略不同。时间片计算公式：Q=T/N;这种固71（5）多级反馈队列法：多级反馈队列算法是时间片算法和优先数算法的一种综合使用。与多队列法的不同之处是它是按进程使用CPU时间的长短这一特征来划分队列的。..队列1（Q=8)队列2(Q=16)队列n2n(先来先服务）时间片增加优先级变小（5）多级反馈队列法：多级反馈队列算法是时间片算72

多级反馈队列算法可兼顾多方面的系统目标。如提高系统的吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。因此这种调度算法是最通用的CPU调度算法，但它也是最复杂的策略。一个作业或进程刚进入就绪队列时，先放到队列1，如果在该队列所属时间片内没有完成，则自动沉入队列2，依次类推。各队列的运行顺序是：调度程序先运行队列1中的叫做业或进程，只有队列1空时，才调度执行队列2中的作业或进程；而且当低级队列中的进程正在执行时，如果高级队列中有进程到来，则有可能抢占正在运行进程的CPU.多级反馈队列算法可兼顾多方面的系统目标。如提高系统73第三章存储器管理•计算机存储层次•分区式管理•页式管理•段式与段页式管理

第三章存储器管理•计算机存储层次74第一节内存管理概述一、计算机存储层次寄存器内存外存容量速度成本存取速度小大高高低低高低当前CPU正在执行的指令及被处理的数据当前CPU正在运行的程序代码及数据所有信息第一节内存管理概述一、计算机存储层次寄存器内存外存容量75二、内存硬件使用特性:微观角度(指令级)和宏观角度(程序级)

1、微观角度（1）程序对内存的使用体现为程序向内存发出的一次次读写请求。

MOVEAX,[1000H](2)、内存接受的读写请求可能来自CPU或DMA2、宏观角度从宏观角度看程序对内存的使用,主要是意识到内存空间和程序空间的存在.二、内存硬件使用特性:微观角度(指令级)和宏观角度(程序级)76三、用户对内存的使用要求

1、在使用内存时不希望涉及内存物理细节.

2、用户程序执行前的装入工作,是与应用无关的,不应由用户程序来承担.3、对内存容量和利用率.要满足用户大程序和多任务的要求;避免内存有足够的空闲空间,而用户程序却无法装入运行;对超过内存容量的大程序装入束手无策.4、对内存存取速度的要求.5、存储保护与安全.6、用户程序运行期间的动态伸缩要求.7、用户程序的信息共享(程序、数据).三、用户对内存的使用要求77四、内存管理的任务和功能1、如何才能使用户不涉及内存物理细节.

这是由操作系统和编译程序、硬件共同完成的.首先是高级语言或汇编语言使源程序与可执行目标程序分化,是源程序得以使用独立于物理细节的地址和高级语言;其次是可执行目标程序对内存物理细节的独立性.源程序编译、链接库函数目标文件（逻辑地址空间）运行时（物理地址空间）地址变换四、内存管理的任务和功能源程序编译、链接库函数目标文件（逻辑78由于用户的逻辑地址空间都是从0开始的，而当该程序装如内存运行时又不是从0开始，因此就需要将逻辑地址转换成实际的内存地址。0：.1:.10:loadA,[500]..500:12345逻辑地址100：.101:.110:loadA,[500].500：（其他数据）600:12345内存地址由于用户的逻辑地址空间都是从0开始的，而当该程序装791)、静态重定位

在目标程序装入内存时（程序开始执行之前），由操作系统装配程序一次性完成的重定位过程。它由专门设计的程序来完成，无需硬件支持。为了使程序能够正确执行，需要将程序中出现的逻辑地址全部映射成内存物理地址，这一映射过程称为重定位。重定位：由逻辑地址空间到内存物理地址空间的映射过程。缺点：a.程序经地址重定位后就不能再移动了，因而不能重新分配内存，不利于内存的有效利用；b.程序在存储空间中只能连续分配，不能分布在内存的不同区域；1)、静态重定位为了使程序能够正确执行，需要将程序802)、动态重定位

在程序执行过程中，在CPU访问内存之前，完成重定位过程。它需要硬件支持。

a.基址寄存器BR：存放用户程序分配到的内存块的首地址；

b.程序虚地址寄存器VR：存放程序中涉及到的内存的虚地址。

MA=(BR)+(VR)LOADA,500010012345500LOADA,50010012345BR100VR5006002)、动态重定位a.基址寄存器BR：存放用户程序分配到的812、如何提高内存利用率和弥补用户对内存容量要求与实际内存容量之间的差距.

内存管理的大部分内容都是以提高内存的利用率为目的的,详见具体管理方法.当用户对内存要求超过实际内存容量时:

a.程序多、空间小,装不下:采用交换、虚拟等技术;

b.程序大、空间小,装不下:采用虚拟、覆盖动态装入等技术.

所有技术的理论根据是局部性原理.3、如何解决内存速度与CPU速度不匹配问题.

a.高速缓存Cache.若存在Cache命中率98%.

b.尽量减少各种提高内存利用率技术所带来的副作用.2、如何提高内存利用率和弥补用户对内存容量要求与实际内存容量824、如何满足系统和用户的安全要求.

出于安全方面的考虑,内存保护通常由操作系统和硬件共同完成.

在多道程序设计环境下，有许多程序段和数据是可供多个用户共享的，而且，每一个用户的进程又只能在自己的内存区运行，不能破坏和干扰其它用户进程的运行，更不能破坏系统程序100上界寄存器200下界寄存器100200被保护程序100<=访问地址<=2004、如何满足系统和用户的安全要求.在多道程序设计835、如何满足用户程序的动态伸缩要求.

具体实现方法是依不同的内存管理模式而异.5、如何满足用户程序的动态伸缩要求.84第二节分区存储管理

分区管理就是把内存划分成若干个大小不等的区域，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共享，它是满足多道程序设计的一种最简单的存储管理方法。我们结合分区原理来讨论分区存储管理时地址变换、内存的分配与释放等问题。一、固定式分区法

1、分区方法：

把内存固定地划分为若干个大小不等的区域。如可划分成长作业区和短作业区。分区一旦划分结束，每个分区的长度和总分区数将保持不便。

系统对内存的管理和控制通过数据结构分区说明表进行，它包括分区号、分区大小、起始地址、分区状态等信息。分区的分配、释放、存储保护以及地址变换都通过该表进行。第二节分区存储管理分区管理就是把内存划分成85区号长度起始地址状态1238K32K64K20K28K60K1114132K124K0020K28K60K124K操作系统进程A(6K)进程B(25K)进程C(36K)256K分区1分区2分区3分区4(a)分区说明表(B)内存相应状态2、分配回收算法

操作系统为作业或进程分配内存时有两种方法，一种是绝对地址转换的分配法，即将作业或进程分成多个队列，但内存浪费大（见书）；另一种是可重定位的分配法，将所有作业和进程排成一个队列，它们可在任何满足要求的区中运行。区号长度起始地址状态1238K32K64K20K28K60K86要求x大小分区取分区表第一项表结束？空闲？长度>=x？修改状态位返回分区号取下一项无法分配YNYNYN

分配：

当用户程序要装入内存执行时，存储管理程序根据用户程序要求查询内存分区表，从中找出一个满足要求的空闲分区，将其分配给申请者。算法如右图。

释放：用户进程执行完毕，存储管理程序将分区表中相应的分区标志置为“空闲”即可。要求x大小分区取分区表第一项表结束？空闲？长度>=x？修改状87二、动态分区法

1、分区方法：

动态分区法在作业或进程执行前并不建立分区，分区的建立是在作业或进程的执行过程中进行的。在系统初期时，除了操作系统常住内存部分之外，只有一个空闲分区，随后，分配程序将该区划分给调度选中的作业和进程。如下图所示：OSOSOSOS进程A进程A进程A进程A12进程B3进程B进程C4进程B进程C进程D进程A8K进程B16K进程C64K进程D124K二、动态分区法1、分区方法：OSOSOSOS进程A进88

随着进程的执行，会出现一系列的分配和释放，假设如下：C进程结束-E进程申请50K-F进程申请16K-B进程释放-D进程释放。内存变化过程如下：操作系统A(8K)B(16K)C(64K)D(124K)24K空闲操作系统A(8K)B(16K)64K空闲D(124K)24K空闲操作系统A(8K)B(16K)E(50K)14K空闲D(124K)24K空闲操作系统A(8K)B(16K)E(50K)14K空闲D(124K)F(16K)8K空闲操作系统A(8K)B(16K)E(50K)合并138K空闲F(16K)8K空闲操作系统A(8K)16K空闲E(50K)14K空闲D(124K)F(16K)8K空闲进程C完成进程E申请50K进程F申请16K进程B释放16K进程D释放124K与14K合并随着进程的执行，会出现一系列的分配和释放，假设如下89

与固定分区法相同，动态分区法也可采用分区说明表对内存空闲分区进行管理，也可采用可用分区表或自由链方式管理内存。

自由链就是利用每一个空闲分区的前几个单元存放本空闲分区的大小和下一个空闲分区的起始地址，从而把所有的空闲分区连接起来。然后，系统设置一个自由链首指针指向第一个空闲分区。40K16K78K40K78K24K100K空闲空闲AB

可用表的每个表目记录一个空闲区，主要参数包括区号、长度和起始地址。区号分区长度起始地址1316K24K40K78K100K59K100K与固定分区法相同，动态分区法也可采用分区说明表对90

2、动态分区的分配：

动态分区的分配主要解决三个问题：a.

对于用户作业或进程的内存要求，从可用表或自由链中寻找合适的空闲区进行分配：b.

分配空闲区之后，更新可用表或自由链：