《操作系统原理PPT》由会员分享，可在线阅读，更多相关《操作系统原理PPT（232页珍藏版）》请在金锄头文库上搜索。
1、操操 作作 系系 统统 原原 理理武汉大学计算机多媒体课程武汉大学计算机多媒体课程1、操作系统原理操作系统原理教材教材2、操作系统原理实验大纲操作系统原理实验大纲指导教指导教材材3、操作系统课件操作系统课件多媒体教案多媒体教案 课程使用的媒体课程使用的媒体一、一、操作系统的有关概念操作系统的有关概念二、进程管理二、进程管理三、存储器管理三、存储器管理l计算机发展简史计算机发展简史l操作系统的发展过程操作系统的发展过程计算机发展简史 按硬件发展划分为四代。按硬件发展划分为四代。对对计算规律的模拟计算规律的模拟存储程序式计算机存储程序式计算机存储程序式计算机模型存储程序式计算机模型l存存储储程程序
2、序式式计计算算机机模模型型的的基基本本方方案案是是，如如要要使使计计算算机机能能够够自自动动地地计计算算，必必须须有有一一个个存存储储器器用用来来存存储储程程序序和和数数据据；同同时时要要有有一一个个运运算算器器，用用以以执执行行指指定定的的操操作作；有有一一个个控控制制器器，以以便便实实现现自自动动操操作作；另另外外，辅辅以以输输入入/输输出出部部件件，以以便便输输入入原原始始数数据据和和输输出出计计算算结结果果。于于是是形形成成了了现现代代计计算算机机的的基基本本组组成成形形式式。如图如图1.1所示。所示。图图1.1 存储程序计算机的组成存储程序计算机的组成 操作系统的发展过程 按按技技术
3、术发发展展与与分分支支划划分类别分类别操作系统的类型 早期批处理早期批处理执行系统执行系统多道成批系统多道成批系统 分时、实时系统、个人机系统分时、实时系统、个人机系统 多处理机、分布式系统多处理机、分布式系统无操作系统的计算机无操作系统的计算机l从第一代计算机诞生到从第一代计算机诞生到20世纪世纪50年代中期还未出现年代中期还未出现操作系统，这时的计算机采用人工操作方式。其过操作系统，这时的计算机采用人工操作方式。其过程是：程是： 图图1.2 手工操作计算机手工操作计算机单道批处理系统与多道批处理单道批处理系统与多道批处理系统及执行系统系统及执行系统l所所谓谓批批处处理理系系统统是是指指加加
4、载载在在计计算算机机上上的的一一个个系系统统软软件件，在在它它的的控控制制下下，计计算算机机能能够够自自动动地地成成批批地地处处理理一个或多个用户的作业。一个或多个用户的作业。l首先出现的是联机批处理系统。如下图所示。首先出现的是联机批处理系统。如下图所示。脱离主机控制的输入脱离主机控制的输入/输出批处输出批处理系统理系统 l在在外外设设处处理理数数据据时时，主主机机处处理理“忙忙等等”状状态态，这这样样高高速速的的主主机机与与慢慢速速的的外外设设矛矛盾盾就就显显现现出出来来。为为了了克克服服与与缓缓解解主主机机与与外外设设的的矛矛盾盾。我我们们引引入入脱脱机机批批处处理理系系统统，即即脱脱离
5、离主主机机控控制制的的输输入入/输输出出批批处处理理系系统统。如图如图1.4所示。所示。图图1.4 脱机批处理系统脱机批处理系统l在单道批处理系统中，内存中仅有一道作业，中断和通道在单道批处理系统中，内存中仅有一道作业，中断和通道技术出现以后，虽然可以实现输入技术出现以后，虽然可以实现输入/输出设备与中央处理机输出设备与中央处理机并行操作，但由于属于同一道作业的可并发执行的进程不并行操作，但由于属于同一道作业的可并发执行的进程不多，大多数进程是有同步关系的，这使系统中仍有较多的多，大多数进程是有同步关系的，这使系统中仍有较多的空闲资源，致使系统的性能较差。为了进一步提高资源的空闲资源，致使系统
6、的性能较差。为了进一步提高资源的利用率和系统对作业的吞吐量，在利用率和系统对作业的吞吐量，在60年代中期，引入了多年代中期，引入了多道程序设计技术，由此而形成了多道批处理系统。单道程道程序设计技术，由此而形成了多道批处理系统。单道程序与多道程序的执行过程如图序与多道程序的执行过程如图1.5和图和图1.6所示。所示。 在操作系统中引入多道程序设计技在操作系统中引入多道程序设计技术以后，会使系统具有以下特征。术以后，会使系统具有以下特征。l（1）多道性）多道性 l（2）无序性）无序性 l（3）宏观上并行、微观上串行）宏观上并行、微观上串行 l（4）调度性）调度性 分时系统分时系统l分分时时技技术术
7、是是把把处处理理机机的的时时间间分分成成很很短短的的时时间间片片，这这些些时时间间片片轮轮流流地地分分配配给给各各个个联联机机的的各各作作业业使使用用。如如果果某某作作业业在在分分配配给给它它的的时时间间片片用用完完时时仍仍未未完完成成，则则该该作作业业就就暂暂时时中中断断，等等待待下下一一轮轮运运行行，并并把把处处理理机机的的控控制制权权让让给给另另一一个个作作业业使使用用。这这样样在在一一个个相相对对较较短短的的时时间间间间隔隔内内，每每个个用用户户作作业业都都能能得得到到快快速速响响应应，以实现人机交互。以实现人机交互。l分分时时系系统统与与多多道道批批处处理理系系统统相相比比，具具有有
8、完完全全不不同同的的特特征征，由由上上所所述述可可以以归归纳纳成成以以下下几点：几点：（1）多路性）多路性 （2）独立性）独立性 （3）及时性）及时性 （4）交互性）交互性 l什么是操作系统什么是操作系统l操作系统的性质操作系统的性质 操作系统操作系统是控制和管理计是控制和管理计算机系统内各种硬件和软件资算机系统内各种硬件和软件资源、有效地组织多道程序运行源、有效地组织多道程序运行的的系统软件系统软件( (或或程序集合程序集合),),是用是用户与计算机之间的接口。户与计算机之间的接口。以下软件哪些是操作系统以下软件哪些是操作系统? ? UNIX Word DOS VB Office FoxPr
9、o Windows 98 Windows NT Linux PowerPoint以下软件是操作系统：以下软件是操作系统： UNIX DOS Linux Windows 98 Windows NT 设置设置OS的目的的目的l扩充机器功能，方便用户使用。扩充机器功能，方便用户使用。l提高系统效率。提高系统效率。操作系统的共同性质操作系统的共同性质1、从功能上看、从功能上看 具具有有五五大大功功能能-存存储储器器管管理理、处处理理机机管管理理、设设备备管管理理、文文件件管管理理、用用户接口户接口2、从层次、从层次上看上看 是是裸裸机机之之上上的的第第一一层层软软件件, ,为为其其他他软软件件的的建建
10、立立和和运行提供基础。运行提供基础。 裸机裸机操作系统操作系统其他软件其他软件. . .用户用户1。4节节3、从服务、从服务上看上看 提提供供众众多多基基础础服服务务, ,方方便便用用户户使使用用, ,构构成成软软件平台。件平台。4、从内部特征上看、从内部特征上看-支持并发性支持并发性 -实现资源共享实现资源共享-完成进程的异步前进完成进程的异步前进以多道成批系统以多道成批系统为例为例l并发并发l共享共享l不确定性不确定性1.3 OS的服务功能的服务功能l程序执行程序执行lI/O操作操作l文件系统管理文件系统管理l出错检测出错检测l资源分配资源分配l统计统计l保护保护一一 系统调用系统调用l是
11、是应用程序应用程序与与OS的接口的接口l进程或作业控制：实现进程或作业的所有活动进程或作业控制：实现进程或作业的所有活动l文件管理和设备管理文件管理和设备管理l信息维护：用户与系统交互信息信息维护：用户与系统交互信息二二 系统程序系统程序l文件管理文件管理l状态信息状态信息l文件修改文件修改l程序设计语言支持程序设计语言支持l程序装入与执行程序装入与执行l工具性软件工具性软件l命令解释程序的实现方法命令解释程序的实现方法1.5操作系统逻辑结构设计 分分层层实实现现的的软软件件设设计计方法方法1.5操作系统逻辑结构设计l单块单块结构结构l层次结构层次结构:分层实现的软件设计方法分层实现的软件设计
12、方法.l虚拟机虚拟机l客户客户/服务器模型服务器模型:再用户进程方式下实现系统的多再用户进程方式下实现系统的多数功能数功能; 核心只负责客户与服务器的通信核心只负责客户与服务器的通信; 适用于适用于分布式系统分布式系统; 注意对关键基础服务的处理注意对关键基础服务的处理.1。8 UNIX系统的特点和结构系统的特点和结构lUNIX的主要特点的主要特点lUNIX系统结构系统结构lUNIX系统核心结构系统核心结构一、操作系统的有关概念一、操作系统的有关概念二、二、进程管理进程管理三、存储器管理三、存储器管理进程概念进程概念程序的顺序执行程序的顺序执行与并发执行与并发执行程序的顺序执行程序的顺序执行概
13、念概念一一个个程程序序由由若若干干个个程程序序段段组组成成，而而这这些些程程序序段段的的执执行行必必须是顺序的，这种程序执行的方式就称为程序的顺序执行。须是顺序的，这种程序执行的方式就称为程序的顺序执行。例如：例如： 程序顺序执行的特点程序顺序执行的特点1 1 顺序性顺序性处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2 2 封闭性封闭性程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。 程序顺序执行的特点（续）程序顺序执行的特点（续）3 3 可再现性可再现性程序执行的结果与初始条件有关，而
14、与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。 O=f(I), f是与时间无关的函数程序的并发执行程序的并发执行例：例：在在系系统统中中有有n n个个作作业业，每每个个作作业业都都有有三三个个处处理理步步骤骤，输输入入数数据据、处处理理、输输出出，即即I Ii i,C,Ci i,P,Pi i (i=1,2,3,.,n) (i=1,2,3,.,n)。 这这些些作作业业系系统统中中执执行行时时是是对对时时间间的的偏偏序序，有有些些操操作作必必须须在在其其它它操操作作之之前前执执行行，这这是是有有序的，但有些操作是可以同时执行的。序的，
15、但有些操作是可以同时执行的。程序的并发执行程序的并发执行例如：例如： P1P1与与I2I2，C1C1与与I2,I3I2,I3与与P1P1是可以同时执是可以同时执行的。行的。I1I1、C1C1、P1P1的执行必的执行必须严格按照须严格按照I1I1，C1C1，P1P1的的顺序。顺序。I1I1、 I2I2、 I3I3、 I4I4轮流使用同一输入设备。轮流使用同一输入设备。时时间间资源资源程序的并发执行定义程序的并发执行定义若若干干个个程程序序段段同同时时在在系系统统中中运运行行，这这些些程程序序的的执执行行在在时时间间上上是是重重迭迭的的，一一个个程程序序段段的的执执行行尚尚未未结结束束，另另一一个
16、个程程序序段段的的执执行行已已经经开开始始，即即使使这这种种重重迭迭是很小的，也称这几个程序段是并发执行的。是很小的，也称这几个程序段是并发执行的。程序的并发执行分析程序的并发执行分析优点：优点：程序的并发执行程序的并发执行提高了资源的利用率提高了资源的利用率。 注意有限制规则：注意有限制规则：同同一一作作业业的的处处理理步步骤骤的的执执行行必必须须严严格格按按照照规规定定的的顺序顺序；同同一一独独占占资资源源上上的的不不同同作作业业的的处处理理步步骤骤不不能能同时同时执行。执行。程序的顺序执行与并发执行程序的顺序执行与并发执行假假设设有有一一个个程程序序 由由 S0S0 Sn+1Sn+1个个
17、语语句句，先先顺顺序序执执行行S0S0，然然后后并并发发执执行行 S1S1SnSn语语句句，最最 后后 顺顺 序序 执执 行行Sn+1 Sn+1 。程序并发执行的特点程序并发执行的特点一一、失失去去了了程程序序的的封闭性封闭性程序程序A程序程序Bn:=0;打印打印nn:=n+1;K1K2S如果程序执行如果程序执行的结果是一个与时的结果是一个与时间无关的函数，即间无关的函数，即具有具有封闭性封闭性。程序程序B打印打印0程序程序B打印打印1程序并发执行的特点程序并发执行的特点二、程序与计算不再一一对应二、程序与计算不再一一对应在在程程序序顺顺序序执执行行时时，一一个个程程序序总总是是对对应应一一个
18、个具具体体的的计计算算，但但在在程程序序的的并并发发执执行行时时，可可能能有有多多用用户户共共享享使使用用同同一一个个程程序序，但但处处理理（计计算算）的的对对象象却却是是不不同同的的，例例如如，在在多多用用户户环环境境下下，可可能能同同时时有有多多个个用用户户调调用用C C语语言言的的编编译译程程序序，这这就就是是典典型型的的一一个个程程序序对对应应多多个用户源程序的情况。个用户源程序的情况。程序并发执行的特点程序并发执行的特点程序与计算不再一一对应示例程序与计算不再一一对应示例程序程序A程序程序BCall CCall C程序程序C程序程序A和和B在执行过程中都调用了程序在执行过程中都调用了
19、程序C 程序并发执行的特点程序并发执行的特点三、程序并发执行可以相互制约三、程序并发执行可以相互制约在在多多道道程程序序设设计计的的环环境境下下，程程序序是是并并发发执执行行的的。即即系系统统中中有有多多道道程程序序在在“同同时时”执执行行，这这些些程程序序之之间间要要共共享享系系统统的的资资源源，程程序序之之间间有有合合作作（通通信信）的的关关系系。合合作作与与竞竞争争产产生生一一系系列列的的矛矛盾盾，这这些些矛矛盾盾实实际际上上是是一一种种相相互互制制约，有直接的，也有间接。约，有直接的，也有间接。注注意意区区别别不不能能同同时时与与有有先先后后次次序序两两种种制制约约。 程序并发执行的特
20、点程序并发执行的特点程序并发执行的相互制约示例程序并发执行的相互制约示例并发活动并发活动进程的引人进程的引人l操操作作系系统统的的特特性性之之一一是是并并发发与与共共享享，即即在在系系统统中中（内内存存）同同时时存存在在几几个个相相互互独独立立的的程程序序，这这些些程程序序在在系系统统中中既既交交叉叉地地运运行行，又又要要共共享享系系统统中中的的资资源源，这这就就会会引引起起一一系系列列的的问问题题，包包括括：对对资资源源的的竞竞争争、运行程序之间的通信、程序之间的合作与协同等符。运行程序之间的通信、程序之间的合作与协同等符。l要要解解决决这这些些问问题题，用用程程序序的的概概念念已已经经不不
21、能能描描述述程程序序在内存中运行的状态，必须引人新的概念进程在内存中运行的状态，必须引人新的概念进程。进程的定义进程的定义l行行为为的的一一个个规规则则叫叫做做程程序序，程程序序在在处处理理机机上上执执行行时时所发生的活动称为进程所发生的活动称为进程（DijkstraDijkstra) )。l进进程程是是这这样样的的计计算算部部分分，它它是是可可以以和和其其它它计计算算并并行行的一个计算。的一个计算。(Donovan)(Donovan)l进进程程（有有时时称称为为任任务务）是是一一个个程程序序与与其其数数据据一一道道通通过处理机的执行所发生的活动。（过处理机的执行所发生的活动。（Alan.C.
22、 Shaw)Alan.C. Shaw)l进进程程是是执执行行中中的的程程序序。（Ken Ken Thompson Thompson and and Dennis Ritchie )Dennis Ritchie )l进程，即是程序在并发环境中的执行过程进程，即是程序在并发环境中的执行过程 。进程与程序的区别（进程与程序的区别（1 1）l l进程是动态概念；程序是静态概念进程是动态概念；程序是静态概念l l进程具有并发性，宏观上同时运行；程序本进程具有并发性，宏观上同时运行；程序本身具有顺序性，程序的并发执行是通过进程身具有顺序性，程序的并发执行是通过进程实现的实现的l l进程具有独立性，是一个能
23、独立运行的单位，进程具有独立性，是一个能独立运行的单位，是系统资源分配的基本单位，是运行调度的是系统资源分配的基本单位，是运行调度的基本单位；程序本身没有此特性基本单位；程序本身没有此特性进程与程序的区别（进程与程序的区别（2 2）l l进程和程序无一一对应关系，一个进程可顺序进程和程序无一一对应关系，一个进程可顺序执行多个程序；一个程序可由多个进程共用执行多个程序；一个程序可由多个进程共用l l进程异步前进，会相互制约；程序不具备此特进程异步前进，会相互制约；程序不具备此特性性l l进程实体具有一定结构，组成进程映象；程序进程实体具有一定结构，组成进程映象；程序没有这种结构没有这种结构进程与
24、程序的区别示例进程与程序的区别示例例子：例子： 光盘（CD、VCD、DVD）光盘（程序）-放光盘的活动（进程）理解进程概念理解进程概念l进程的运行状态及其变迁进程的运行状态及其变迁l进程的组成进程的组成l进程映像进程映像l进程环境进程环境进程的运行状态及其变迁进程的运行状态及其变迁l进程在系统中的活动规律是：进程在系统中的活动规律是： 执行执行- -暂停暂停- -执行执行l进程的运行状态反映进程的动态性。进程的运行状态反映进程的动态性。l进程的三种基本状态：进程的三种基本状态：l 运行状态运行状态l 就绪状态就绪状态l 封锁状态（又称不可运行、挂起）封锁状态（又称不可运行、挂起）进程的三种基本
25、状态进程的三种基本状态l运行状态运行状态 ：进程得到进程得到CPUCPU控制权，它的程序控制权，它的程序正在运行。（在系统中，总只有一个进程处正在运行。（在系统中，总只有一个进程处于此状态于此状态）l就绪状态就绪状态：已经准备就绪，一旦得到已经准备就绪，一旦得到CPUCPU，就立即可以运行。（有多个进程处于此状态）就立即可以运行。（有多个进程处于此状态）l封锁状态封锁状态：正在等待某个事件的发生（如等正在等待某个事件的发生（如等待待I/OI/O的完成），而暂停执行，这时，即使给的完成），而暂停执行，这时，即使给它它CPUCPU时间，它也无法执行。时间，它也无法执行。进程的状态变化进程的状态变化
26、就绪就绪运行运行挂起挂起？PCB程序程序数据集合数据集合进程的组成进程的组成基本内容的确定基本内容的确定?进程与进程与PCB的关系的关系l每个进程有唯一每个进程有唯一的的PCB l系系统统中中所所有有进进程程都都有有自自己己的的PCBl操作系统依据操作系统依据PCB管理进程管理进程进程进程与与PCB的关系的关系l操操作作系系统统利利用用PCB实实现现进进程程的动态和并发的动态和并发 lPCB是进程存在的唯一标志是进程存在的唯一标志Pcb表组织表组织ab-1pcb1N个个pcb2pcbiPcb-addr?空间大小空间大小?UNIX的进程映像的进程映像l进程状态进程状态l变迁关系变迁关系l进程映像
27、：进程映像：PCB的实现、核心栈与的实现、核心栈与用户栈（图用户栈（图2-10 UNIX进程映像结进程映像结构构）进程环境进程环境l用户级环境用户级环境l寄存器环境寄存器环境l系统级环境系统级环境1、进程与程序的区别、进程与程序的区别2、进程的组成、进程的组成3、进程的同步与互斥、进程的同步与互斥进程控制进程控制原语原语lFork()lWait(stat_addr)lExitlexec进程在活动中会相互制约进程在活动中会相互制约l所有进程都是相互独立所有进程都是相互独立的的 l进程以异步方式并发执行进程以异步方式并发执行同步同步 同同步步是是进进程程间间共共同同完完成成一一项项任任务务时时直直
28、接接发发生生相相互互作用的关系作用的关系 同步进程间具有合作关系同步进程间具有合作关系 在在执执行行时时间间上上必必须须按按一一定定的顺序协调进行的顺序协调进行互斥互斥 互互斥斥是是并并发发执执行行的的多多个个进进程程由由于于竞竞争争同同一一资资源源而产生的相互排斥的关系而产生的相互排斥的关系 互互斥斥进进程程彼彼此此在在逻逻辑辑上上是完全无关的是完全无关的 它它们们的的运运行行不不具具有有时时间间次序的特征次序的特征临界资源和临界区临界资源和临界区信号量信号量P、V操作操作临界资源临界资源 一一次次仅仅允允许许一一个个进进程程使使用用的的共享资源共享资源 如如：打打印印机机、内内存存单单元元
29、、表表格格临界临界区区在在每每个个进进程程中中访访问问临临界界资资源源的那段程序的那段程序l 有限进入原则有限进入原则l唯一原则唯一原则l有限离开原则有限离开原则进程间的通信进程间的通信临界资源和临界区临界资源和临界区信号量信号量P、V操作操作信号信号量量l 信号量是一种数据结构信号量是一种数据结构l 一般由两个成员组成：一般由两个成员组成：数值数值指针指针?信号信号量量l 一一般般说说来来，信信号号量量的的值值与与相相应应资源的使用情况有关资源的使用情况有关l 信号量的值仅信号量的值仅由由P、V操作改变操作改变进程间的通信进程间的通信临界资源和临界区临界资源和临界区信号量信号量P、V操作操作
30、P、V操作都是原语操作都是原语P：申请一个单位资源（申请一个单位资源（P47）V：释放一个单位资源（释放一个单位资源（P47）P操作操作P(s):若若S=0，继续继续取取s值减值减1V操作操作V(s):若若S0，继续继续取取s值加值加1用用P、V原语实现互斥原语实现互斥例：打印机分配例：打印机分配互斥信号量互斥信号量mutex（初值为初值为1）Pa为分配进程为分配进程Pb为释放进程为释放进程Pa：.P（mutex）分配打印机分配打印机（读写分配表）（读写分配表）V（mutex）.Pb：.P（mutex）释放打印机释放打印机（读写分配表）（读写分配表）V（mutex）.用用P、V原语实现简单同步
31、原语实现简单同步例：供者和用者对单缓冲区的同步例：供者和用者对单缓冲区的同步信号量：信号量：S1缓冲区空否（初值为缓冲区空否（初值为1）S2缓冲区满否（初值为缓冲区满否（初值为0） 供者进程供者进程L1：P（S1） 启动读卡机启动读卡机 收到输入结束中断收到输入结束中断 V（S2） goto L1 用者进程用者进程L2： P（S2） 从缓冲区取出信息从缓冲区取出信息 V（S1） goto L2用用P、V原语实现同步原语实现同步设上例中缓冲区容量为设上例中缓冲区容量为n，分析信分析信号灯的设置与状态变化范围（生产号灯的设置与状态变化范围（生产者者-消费者问题消费者问题P49） 其它进程通信方式其
32、它进程通信方式l信号量集方式信号量集方式l管程管程l消息缓冲通信消息缓冲通信UNIX中的进程通信中的进程通信lSleep 和和wakeupl进程跟踪进程跟踪lS_5的的ipc:消息机制，共享内存，信号量。消息机制，共享内存，信号量。处理机管理l目标：提高CPU的有效运行时间l如何实现？根据CPU的特点和进程管理的需要来设计管理方法CPU资源的特点资源的特点l是一种时间资源是一种时间资源l具有唯一性与独占性具有唯一性与独占性l影响系统效率的关键因素影响系统效率的关键因素l进程运行的必备资源进程运行的必备资源CPU效率的影响因素效率的影响因素l并发并发总有请求总有请求CPU的进程的进程lCPU时间
33、分片时间分片在效率与交互性上权衡在效率与交互性上权衡l现场交换代价现场交换代价只做必须做的工作只做必须做的工作处理机的二级调度处理机的二级调度宏观作业调度：算法复杂、间隔长、宏观环境宏观作业调度：算法复杂、间隔长、宏观环境微观进程调度：算法简单、调度频繁、微观状态微观进程调度：算法简单、调度频繁、微观状态作业调度作业调度作业调度的主要任务是完成作业从后备状态到执行状作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。态和从执行状态到完成状态的转变。作业调度功能：作业调度功能：l记记录录已已进进入入系系统统的的各各作作业业的的情情况况（JCBJCB，Job Job Co
34、ntrol BlockControl Block）；）；l按按一一定定的的调调度度算算法法，从从后后备备作作业业中中选选择择一一个个或几个作业进入系统内存；或几个作业进入系统内存；l为为被被选选中中的的作作业业创创建建进进程程，并并且且为为其其申申请请系系统资源；统资源；l作业加束后作善后处理工作。作业加束后作善后处理工作。作业控制块（JCB）每个作业进入系统时由系统为其建立一个每个作业进入系统时由系统为其建立一个作业作业控制块控制块JCBJCB（Job Control Block)Job Control Block)，它是存放作业控制和它是存放作业控制和管理信息的数据结构，主要信息见下图。管
35、理信息的数据结构，主要信息见下图。调度性能的衡量调度性能的衡量 作作业业调调度度算算法法规规定定了了从从后后备备作作业业中中选选择择作作业业进进入入系系统统内内存存的的原原则则，这这些些原原则则的的性性能能如如何何，就就是是本节所讨论的问题。本节所讨论的问题。确定调度算法时应考虑的因素l应与系统的整体设计目标一致l考虑系统中各种资源的负载均匀l保证作业的执行l对一些专用资源的使用特性的考虑调度性能的衡量调度性能的衡量调度性能的衡量调度性能的衡量通常采用平均周转时间和带权平均周转时间作业的周转时间作业的周转时间：ti = tci-tsiti:作业周转时间tci：作业完成时间tsi: 作业提交时间
36、调度性能的衡量调度性能的衡量先来先服务调度先来先服务调度算法和短作业优先调度算法算法和短作业优先调度算法进程调度进程调度l调度与进程控制和进程通信的功能有密切的联系，当一个进程阻塞时，这种进程将进入相应的等待队列中，并让出CPU，调用进程分派程序选择一个就绪进程占用CPU；当一进程被唤醒时，这种进程将插入到就绪进程队列中。l在一般的操作系统教材中把上述功能称为进程调度。调度调度/ /分派结构分派结构l处理机分配由调度和分派两个功能组成。处理机分配由调度和分派两个功能组成。l调度：组织和维护就绪进程队列。包括确定调度：组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程调度算法
37、、按调度算法组织和维护就绪进程队列。队列。l分派：是指当处理机空闲时，从就绪队列队分派：是指当处理机空闲时，从就绪队列队首中移一个首中移一个PCBPCB，并将该进程投入运行。并将该进程投入运行。调度调度/分派结构分派结构pcb1schedulersuspwakeupreceivepcb2pcb3pcb4dispatchercpuReady-qpcb5调度调度/分派结构分派结构pcb2schedulersuspwakeupreceivepcb5pcb3pcb4dispatchercpu分开分开Ready-qpcb1进程调度功能进程调度功能l保护现场保护现场l入就绪队列算法实现入就绪队列算法实现l
38、处理机分派处理机分派l恢复现场恢复现场进程调度的功能进程调度的功能记记录录和和保保持持系系统统中中所所有有进进程程的的有有关关情情况况和和状状态态特征特征 有关进程调度的信息是记录在PCB中的，在进程调度中用到的主要是进程的状态、调度优先级（优先数）、就绪进程队列等。进程调度的功能进程调度的功能决定分配（处理机）策略决定分配（处理机）策略确定进程调度的策略，例如，先来先服务、优先数调度策略，调度策略的不同，组织就绪进程队列的方式也不同。先来先服务调度策略，就绪队列要按等待时间大到小的顺序排队；优先数调度，则就绪进程队列要按优先数的升疗（或降序）的方式排队。等等。进程调度的功能进程调度的功能实施
39、处理机的分配实施处理机的分配总而言之，进程调度包括：l调度算法的选择（调度算法）l调度时机的选择（调度时机）l实施进程调度（调度程序）进程调度的功能进程调度的功能调度时机（调度时机（UNIXUNIX系统中）：系统中）：（1）进程自动放弃处理机：l当进程进入高低优先级睡眠状态时 （在sleep()程序中）；l在进程进入暂停状态时（在stop()程序中）；l进程进入僵死状态时 （在exit()程序中）；进程调度的功能进程调度的功能在中断自陷总控程序中，当先前态是用户态，且runrun标志大于0，则进行强迫调度，强行剥夺现运行进程的处理机，转进程调度程序。runrun标志大于0是说明系统中处于就绪状
40、态的进程的优先级高于现运行进程的优先级，这时要进行强迫调度，出现这种情况有两种可能：高低优先级睡眠进程被唤醒后其优先级高于现运行进程；当一个进程占用一段时间的CPU后，它的优先级要降低，造成现运行进程的优先级低于系统中的其它就绪进程（时间片到是其中的一种情况）。（2 2）强迫调度）强迫调度调度方式优先数高者进程是否抢占正在运行进程资源优先数高者进程是否抢占正在运行进程资源l l非非剥夺方式剥夺方式l l剥夺方式剥夺方式l l选择可抢占策略：优先数选择可抢占策略：优先数+抢占标志（抢占标志（u,v）进程调度的功能进程调度的功能实施进程调度的程序称为进程调度程序（或称调度程序），在通常的操作系统原
41、理中，该程序属于系统进程的执行程序，有的操作系统是把进程调度程序作一个特别的处理，如早期的操作系统中把进程调度程序称为交通控制程序，不属于系统中的任何进程。在UNIX系统中，进程调度程序swtch( )分属个不同的进程，即调用swtch( )的进程、让出处理机的进程、0进程、被调度到的进程。调度性能的衡量l 选择策略时考虑因素选择策略时考虑因素整整体体目目标标、负负载载均均衡衡、资资源源特特性性、用用户户满满意意l调度性能指标调度性能指标平均周转时间，平均带权周转时间平均周转时间，平均带权周转时间CPUCPU利用率利用率吞吐量吞吐量就绪等待时间就绪等待时间响应时间响应时间调度策略l l 先来先
42、服务调度先来先服务调度l l短作业优先调度短作业优先调度l l响应比高者优先调度响应比高者优先调度l l优先数调度优先数调度l l均衡调度均衡调度l l多级队列法多级队列法l l多级反馈队列法多级反馈队列法进程优先数调度算法进程优先数调度算法优先数调度算法是目前操作系统广泛采用的一种进程调度算法，这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。采用这种调度算法的关键是如何确定进程的优先数、一个进程的优先数确定之后是固定的，还是随着该进程运行
43、的情况的变化而变化。进程优先数调度算法进程优先数调度算法静态：进程的优先数在进程创建时确定后就不再变化确定进程优先数：系统确定：（运行时间、使用资源，进程的类型）用户确定：（紧迫程度，计费与进程优先数有关） 系统与用户结合（用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数）进程优先数调度算法进程优先数调度算法动态进程优先数：动态进程优先数： 系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先数，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标。循环轮转调度算法循环轮转调度算法l时间片完，入队列
44、末端时间片完，入队列末端；q=t/n简单循环轮转调度简单循环轮转调度可变时间片轮转调度可变时间片轮转调度多重时间片循环调度多重时间片循环调度循环轮转调度循环轮转调度 循循环环轮轮转转调调度度实实际际上上是是一一种种先先来来先先服服务务算算法法的的调调度度算算法法，它它把把系系统统的的响响应应时时间间分分成成大大小小相相等等（或或不不相相等等）的的时时间间单单位位，称称为为时时间间片片。每每个个进进程程被被调调度度到到后后，占占用用一一个个时时间间片片，片片用用完完后后，该该进进程程让让出出CPUCPU，由由运运行行状状态态转转换换成成就就绪绪状状态态，排排在在就就绪绪队列的队尾。多个进程循环轮
45、转。队列的队尾。多个进程循环轮转。循环轮转调度循环轮转调度循环轮转调度循环轮转调度 系统按进程转换成就绪状态的时间的降序排队，调度程序每次调度，总是从队首移出一程的PCB，然后，将此进程投入运行（由就绪状态转换成运行状态）。一个运行时间片到的进程从运行状态转换成就绪状态后，排在就绪队列的队尾。评价：l优点是实现简单、系统开销小l缺点是不灵活，当系统中进程较少时，系统开销变大。为什么？l由于该算法简单易于实现，且系统开销较小，早期的分时操作系统和目前一些应用系统中广泛采用了这种调度算法。循环轮转调度循环轮转调度可变时间片轮转调度可变时间片轮转调度 为了克服前种调度算法的缺点，人们设计出一种可变时
46、间片的调度算法，其思想是：时间片的大小是可变的，系统可根据系统中当前的进程数来确定时间片的大小。 这种算法从理论上克服了系统中进程数很少时系统开销大的缺点，但修改时间片的大小，统计系统进程的数量也需要消耗系统时间，还有一个调整时间片大小的周期，太大，等于是固定时间片，太小，系统开销很大，得不尝失。调度用的进程状态变迁图调度用的进程状态变迁图 在在这这个个图图中中新新创创建建的的进进程程进进入入低低优优就就绪绪状状态态，一一个个运运行行进进程程因因时时间间片片到到（实实际际上上是是计计算算量量大大的的进进程程）而而转转换换成成低低优优就就绪绪；进进程程因因等等待待I/OI/O完完成成而而转转换高
47、优就绪换高优就绪. .调度用的进程状态变迁图调度用的进程状态变迁图l调度程序首先看高优就绪进程队列是否为空，若不为空，则从高优就绪进程中选择一个进程占用CPU，否则，从低优就绪队列中选择。 这种调度效果能充分地利用系统资源。为什么？lUNIX系统的进程调度状态变迁图，与前一种调度变迁图有着异曲同功的效果。调度用进程状态变迁图中就绪中就绪运行运行等待等待1低就绪低就绪高就绪高就绪等待等待2UNIX中的进程调度中的进程调度l进程调度：调度时机，调度算法进程调度：调度时机，调度算法lShell工作原理工作原理l系统初启系统初启UNIXUNIX系统的进程调度系统的进程调度UNIXUNIX调度算法调度算
48、法l我我们们从从调调度度算算法法、调调度度时时机机、调调度度程程序序三三个个方方面面来来分析分析UNIXUNIX系统的进程调度。系统的进程调度。调度算法l UNIX系统采用优先数调度算法，每个进程有一个进程优先数，p_pri是proc结构中的一个变量，其取值范围是127127，其值越小，进程的优先级越高（即，调度程序总是从就绪状态的进程中选择一个优先数最小的进程占用CPU）。UNIXUNIX调度算法调度算法优先数的确定：优先数的确定：系统设置在进程进入睡眠状态时，在SLEEP（）中设置将要进入睡眠状态进程的优先数，当该进程被唤醒后，就以系统给它设置的优先数去参与处理机的竟争。UNIXUNIX调
49、度算法调度算法l进程进入高优先级睡眠的原因：进程进入高优先级睡眠的原因：（1）0进程（100优先数）；（2）因资源请求得不到满足的进程，磁盘（80），打印机 （20），；（3）等待块设备I/O完成的进程，（50）。l进程进入低优先级睡眠的原因：进程进入低优先级睡眠的原因：(1）因等待字符设备I/O完成的进程，（020的优先数）；(2) 所有处于用户态运行进程，优先数一般情况下为大于100。l这样做的目的是为什么？这样做的目的是为什么？为使系统资源得到充分的利用，换句话说，是为了提高系统资源的使用效率。UNIXUNIX调度算法调度算法l优先数的计算优先数的计算计算公式： p_pri = 127,
50、 (p_cpu/16+p_nice+PUSER)其中： p_cpu 进程占用CPU的程度 p_nice 用户通过系统调用nice(priority)设置 的进程优先数。 PUSER 常数，其值为100UNIXUNIX调度算法调度算法UNIXUNIX调度算法调度算法 UNIXUNIX系系统统的的设设计计者者采采用用了了一一个个巧巧妙妙的的方方法法，既既避避免免了了繁繁杂杂的的统统计计工工作作，也也不不需需做做浮浮点点运运行行算算。（这这就就是是我我们们要要学学习习的的工工程程能能力力，或或称称分分析析问问题题和和解解决决问问题题的的能能力力，学学会会和和记记往往一一两两个个科科学学的的定定理理和
51、和公公式式并并不不难难，难难的的是是怎怎样样将将这这些些普普遍遍的的理理论论用用于于实实际际的的工工程程之之中中，UNIXUNIX系系统统中中有有很很多多值值得得我我们们学学习习的的地地方方，对对p_cpup_cpu的的处处理理就就是是其其中中之之一一，这这里里并并不不要要求求把把UNIXUNIX中中的的p_cpup_cpu的的处处理理完完全全记记住住，而而是是要要通通过过对它的了解，学会处理实际工程问题的方法。）对它的了解，学会处理实际工程问题的方法。）UNIXUNIX调度算法调度算法UINXUINX系统中对系统中对p_cpup_cpu的处理：的处理： 每个时钟中断：p_cpu+; 每秒钟（
52、时钟中断）： if(p_cpu-SCHMAG PUSER现运行进程在自陷处理程序trap( )末尾重新计算本进程的优先数. 目的:调用nice() 设置的本进程的优先数p_nice的改变反映到p_pri中去；现运行进程在执行时钟中断处理程序时，若发现中断前为用户态，则每隔1秒钟重新计算本进程的优先数。 因为现运行进程已经占用了一些CPU的时间，要反映到p_pri中去。UNIXUNIX调度算法调度算法l这这三三种种重重新新计计算算（调调整整）进进程程优优先先数数都都没没有有修修改改由由系系统统设设置置的的进进程程优优先先数数，从从而而保保证证了了处处于于核核心心态态的的进进程程能能尽尽快快地地得
53、得到到CPUCPU，使使得得系系统统资资源源（设设备备）能能得得到到充充分分地地利利用用，提提高高了了系系统统资资源源的的使使用用效效率率，而而计计算算进进程程的的优优先先数数又又使使得得系系统统中中所所有有处处于于用用户户态态的的进进程程能能较较均均衡衡地地占占用用CPUCPU，保保证证了了各各用用户户终终端端的的响响应时间，实现了分时操作系统的特性。应时间，实现了分时操作系统的特性。UNIXUNIX调度时机调度时机调度时机（调度时机（UNIXUNIX系统中）：系统中）：1）进程自动放弃处理机l在进程进入高低优先级睡眠状态时（在sleep()程序中）；l在进程进入暂停状态时（在stop()程
54、序中）；l进程进入僵死状态时（在exit()程序中）；2）强迫调度l在中断自陷总控程序中，当先前态是用户态，且runrun标志大于0，则进行强迫调度，强行剥夺现运行进程的处理机，转进程调度程序。UNIXUNIX调度调度时机时机Runrun标志大于0是说明系统中处于就绪状态的进程的优先级高于现运行进程的优先级，这时要进行强迫调度，出现这种情况有两种可能：高低优先级睡眠进程被唤醒后其优先级高于现运行进程；当一个进程占用一段时间的CPU后，它的优先级要降低，造成现运行进程的优先级低于系统中的其它就绪进程（时间片到是其中的一种情况）。UNIXUNIX系统调度程序系统调度程序UNIXUNIX系统中的进程
55、调度程序是系统中的进程调度程序是swtchswtch，所以，所以，在绝大多数关于在绝大多数关于UNIXUNIX系统的文献中称为进程系统的文献中称为进程切换程序。切换程序。UNIXUNIX调度程序调度程序UNIXUNIX调度程序调度程序lUNIXUNIX系统的进程调度程序有以下特点：系统的进程调度程序有以下特点：1.swtch()程序分属三个不同的进程：l调用它的程序（即将让出处理机的进程）l0号进程l被选中的进程2. 调度程序中属于0号进程的那段程序是在0号进程处于睡眠状态下执行的，这一点非常特别，在操作系统中，仅此一例。 资源分配与调度资源分配与调度l资源管理概述资源管理概述l资源分配机构资
56、源分配机构l资源分配策略资源分配策略l死锁问题死锁问题资源管理概述简便、有效的使用资源简便、有效的使用资源l 资源管理任务资源管理任务l资源分类资源分类l统统一一的的实实现现机机制制机机构构和和策策略略资源分类l物理资源与程序资源物理资源与程序资源l单入口资源与多入口资源单入口资源与多入口资源l等同资源等同资源l虚拟资源虚拟资源资源分配机构资源分配机构l资源描述器资源描述器rd（P103）l资源信息块资源信息块等待队列头指针等待队列头指针可利用资源队列头指针可利用资源队列头指针资源分配程序入口地址资源分配程序入口地址ribpcb1rd1所有所有rd在同一队列？在同一队列？资源信息块资源分配策略
57、l触发时机触发时机l分配策略实质分配策略实质排对站管理等同资源选取一、先请求先服务按请求发生的先后次序排队按请求发生的先后次序排队l 总能调度总能调度l简单迅速简单迅速l短作业响应比问题短作业响应比问题二、优先调度按优先数的大小次序排队按优先数的大小次序排队l 灵活设计灵活设计l多排队站多排队站l优先数设计问题优先数设计问题三、适应调度按工作集的大小次序排队按工作集的大小次序排队l 主存与主存与CPU合作效率最大合作效率最大l工作集的动态计算问题工作集的动态计算问题l实现的复杂度实现的复杂度四、均衡调度按按系系统统资资源源空空闲闲的的大大小小次次序序动态调度动态调度l 系统效率最大系统效率最大
58、l负载均衡负载均衡l不适合细化处理不适合细化处理五、针对设备特性的调度按设备特性次序排队（按设备特性次序排队（P107）l 服务时间最短服务时间最短l旋转排序旋转排序死锁问题l 概念概念l起因分析起因分析l解决方法解决方法l预防预防死锁概念l 并发与竞争并发与竞争l部分满足部分满足l死锁（死锁（P109）死锁起因分析l资源稀缺、鼓励竞争资源稀缺、鼓励竞争l联合推进路线（联合推进路线（P110）l进程进程-资源有向图（资源有向图（P111）l死锁起因死锁起因l死锁必要条件死锁必要条件死锁起因l资源不足资源不足l进程推进顺序非法进程推进顺序非法死锁必要条件死锁必要条件 l资源互斥使用资源互斥使用l
59、不剥夺条件不剥夺条件l部分分配部分分配l环路条件环路条件死锁解决方法l 假脱机技术假脱机技术l可抢占的进程调度策略可抢占的进程调度策略l静态分配资源静态分配资源l动态有控分配动态有控分配l检测并修复检测并修复死锁预防l 有序资源分配法（有序资源分配法（P118题）题）l银行算法（银行算法（P115）l预先分配资源预先分配资源一、操作系统的有关概念一、操作系统的有关概念二、进程管理二、进程管理三、三、存储器管理存储器管理 lCpu与主存与主存 独占独占微观独占，宏观共享微观独占，宏观共享l概念概念存储器lstorage, memoryl能接收数据和保存数据、而且能根据命令提供这些数据的装置。概念
60、概念l存储器分成两类：存储器分成两类：内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。存储器的层次结构存储器的层次结构存储系统设计三个问题： 容量、速度和成本容量：需求无止境速度：能匹配处理器的速度成本问题：成本和其它部件相比应在合适范围之内容量、速度和成本三个目标不可能同时达到最优，要作权衡存取速度快，每比特价格高容量大，每比特价格越低，同时存取速度也越慢解决方案：采用层次化的存储体系结构当沿着层次下降时每比特的价格将下降，容量将增大速度将变慢，处理器的访问频率也将下降层次化的存储体系结构层
61、次化的存储体系结构存储访问局部性原理存储访问局部性原理提高存储系统效能关键点：程序存储访问局部性原理程序执行时，有很多的循环和子程序调用，一旦进入这样的程序段，就会重复存取相同的指令集合对数据存取也有局部性，在较短的时间内，稳定地保持在一个存储器的局部区域处理器主要和存储器的局部打交道,在经过一段时间以后，使用的代码和数据集合会改变概念概念l程序的逻辑结构程序的逻辑结构程序地址：用户编程序时所用的地址（或称逻辑地址 、虚地址 ），基本单位可与内存的基本单位相同，也可以不相同。程序地址空间（逻辑地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空
62、间，也可以是多维空间。程序的逻辑组织内存组织方式：一维线性程序组织方式：程序组织方式：l l一维线性l l二维段式（模块化、分级保护、动态连接）codedataheapstack程序2虚地址空间data2stack1code1heap1code2stack2data1heap2OS codeOS dataOS heap& stacks程序 1虚地址空间codedataheapstack内存内存地址转换地址转换 l重定位重定位 把逻辑地址转变为内存的把逻辑地址转变为内存的物理地址的过程物理地址的过程 l物理主存与逻辑主存物理主存与逻辑主存用户程序默认主存地址用户程序默认主存地址0-k-1,实际对
63、应实际对应n-n+k-1 l相对地址（或逻辑地址）相对地址（或逻辑地址） 用户程序经编译之后的每用户程序经编译之后的每个目标模块都以个目标模块都以0为基地址顺序为基地址顺序编址，这种地址称为相对地址编址，这种地址称为相对地址LOAD 1, 500LOAD 1, 5001234512345LOAD 1, 500LOAD 1, 5001234512345 01005007005000510055005700程序程序A的地址空间的地址空间程序程序A的内存空间的内存空间. . . . . . . . . . . . . l绝对地址（或物理地址）绝对地址（或物理地址） 内存中各物理存储单元的内存中各物理
64、存储单元的地址是从统一的基地址顺序编地址是从统一的基地址顺序编址，这种地址称为绝对地址址，这种地址称为绝对地址主存映射方式建立虚建立虚-实地址间的对应关系实地址间的对应关系l 编编程程或或编编译译时时确确定定地地址址映映射射关关系（不能浮动）系（不能浮动）l静态地址映射（一次浮动）静态地址映射（一次浮动）l动态地址映射动态地址映射静态地址映射l 静态地址映射是在程序装入内存时完成从逻辑地址到物理地址的转换的。l 在一些早期的系统中都有一个装入程序（加载程序），它负责将用户程序装入系统，并将用户程序中使用的访问内存的逻辑地址转换成物理地址。如左图所示。评价: l优点是实现简单，不要硬件的支持。l
65、缺点是程序一旦装入内存，移动就比较困难。有时间上的浪费。在程序装入内存时要将所有访问内存的地址转换成物理地址。静态地址映射静态地址映射 动态地址映射动态地址映射l 动态地址映射是由硬件地执行时完成的，程序动态地址映射是由硬件地执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省中不执行的程序就不做地址映射的工作，这样节省了了CPUCPU的时间的时间 。 重定位寄存器的内容由操作系统用特权指令来设置，比较灵活。 实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址映射技术。动态地址映射动态地址映射动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物
66、理地址的转换的。l 系统中设置了重定位寄存器。存储管理的功能存储管理的功能（1）内存分配内存分配为每个进程分为每个进程分配一定的内存空间配一定的内存空间（2）地址映射地址映射把程序中所用把程序中所用的相对地址转换成内存的物理地址的相对地址转换成内存的物理地址存储管理的功能存储管理的功能（3）内存保护内存保护检查地址的合检查地址的合法性，防止越界访问法性，防止越界访问（4）内存扩充内存扩充解决解决“求大于求大于供供”的问题，采用虚拟存储技术的问题，采用虚拟存储技术主存共享方式l 按区分配按区分配按逻辑按逻辑l 分页分配分页分配按物理按物理内存分配内存分配l 在多道程序设计的环境中，内存分配的功能
67、包括：制定在多道程序设计的环境中，内存分配的功能包括：制定分配策略、构造分配用的数据结构、响应系统的内存分配分配策略、构造分配用的数据结构、响应系统的内存分配的请求和回收系统释放的内存区。内存管理策略有三种：的请求和回收系统释放的内存区。内存管理策略有三种：放置策略 决定内存中放置信息的区域（或位置），即如何在若干个空闲区中选择一个或几个空闲区的原则；调入策略 决定信息装入内存的时机，有两种：在用户请求时调入，称为请调；根据某种算法，确定系统将要使用的信息，并在执行前预先调入内存，称为预调 ；淘汰策略 当内存不足时，决定将某些信息调出内存的策略 。分区存贮管理分区存贮管理l 固定分区分配固定分
68、区分配l 动态分区分配动态分区分配(p96)分区分配放置策略分区分配放置策略合适的概念合适的概念l首次适应算法首次适应算法l最佳适应算法最佳适应算法l最坏适应算法最坏适应算法 碎片问题（紧缩）存储保护方法存储保护方法l 上下界防护上下界防护l基址、限长寄存器保护基址、限长寄存器保护存储保护存储保护l两种存储保护技术的区别两种存储保护技术的区别1、寄存器的设置不同；2、判别式中用的判别条件不同上下界寄存器保护法用的是物理地址基址、限长寄存器保护法用的是程序的逻辑地址对于合法的访问地址这两者的效率是相同的，对不合法的访问地址来说，上下界存储保护浪费的CPU时间相对来说要多些。多道程序对换技术多道程
69、序对换技术l以以用户为单位独占内存用户为单位独占内存l如何减少对换信息量？如何减少对换信息量？l部分换出与恢复部分换出与恢复提供虚存提供虚存l问题的提出问题的提出物理存储器的结构是个一维的线性空间，容量是有限的。用户程序结构：l一维空间 一个用户程序就是一个程序，并且程序和数据是不分离的；l二维空间 程序由主程序和若干个子程序（或函数）组成，并且程序与数据是分离的； ln维空间 即一个大型程序，由一个主模块和多个子模块组成，其中，各子模块又由主程序和子程序（或函数）组成。用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。提供虚存提供虚存l如何将与物理内存结构不同，且大于物理
70、内存容量如何将与物理内存结构不同，且大于物理内存容量的用户程序装入运行？这就是提出研究虚拟存储器的用户程序装入运行？这就是提出研究虚拟存储器的原因，或称为虚拟存储技术发展的原动力。的原因，或称为虚拟存储技术发展的原动力。提供虚存提供虚存虚拟存储器l 为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储器，或称虚拟存储技术。l 它是用户编程时所使用的一种用户思维中的存储器，它可以是任何结构（一维线性空间、二维空间、乃至n维空间），并没有容量的限制。l 现代计算机操作系统都采用了这种技术，使得用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。l 虚拟存储器需要大容量的外
71、存储器的支持，或称物资基础。虚拟存储器的基本特征虚拟存储器的基本特征（1）虚拟扩充虚拟扩充不是物理上，而是不是物理上，而是逻辑上扩充了内存容量逻辑上扩充了内存容量（2）部分装入部分装入每个作业（进程）每个作业（进程）不是全部一次性地装入内存，而是只不是全部一次性地装入内存，而是只装入其一装入其一 部分部分虚拟存储器的基本特征虚拟存储器的基本特征（3）离散分配离散分配每个作业（进程）每个作业（进程）装入内存的那部分不必占用连续的内装入内存的那部分不必占用连续的内存空间，而是存空间，而是“见缝插针见缝插针”虚拟存储器的基本特征虚拟存储器的基本特征（4）多次对换多次对换在一个进程运行在一个进程运行期
72、间，它所需的全部程序和数据要分期间，它所需的全部程序和数据要分成多次调入内存成多次调入内存虚拟主存的优点l 透明使用主存透明使用主存l方便存储保护方便存储保护l程序可浮动程序可浮动l充分利用主存充分利用主存分页存贮管理分页存贮管理l 页式系统页式系统l 页式地址变换页式地址变换l请调策略请调策略l淘汰策略淘汰策略页式存储管理页式存储管理l页式系统应解决的问题页式系统应解决的问题分区存储管理的主要问题是碎片问题。l在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。l造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问
73、题，提出了分页存储管理技术。分页的概念分页的概念l程序地址空间分成大小相等的页面，同时把内存也程序地址空间分成大小相等的页面，同时把内存也分成与页面大小相等的块，当一个用户程序装入内分成与页面大小相等的块，当一个用户程序装入内存时，以页面为单位进行分配。页面的大小是存时，以页面为单位进行分配。页面的大小是为为2 2n n , ,通常为通常为1KB1KB，2KB2KB，nKBnKB等。等。页式地址变换l页表：虚页页表：虚页-物理块对照物理块对照表表l虚地址结构虚地址结构：页号：页号+偏移偏移l页式地址变换页式地址变换 分地址-查页表-合地址页式地址变换页式地址变换l虚地址结构虚地址结构( (程序
74、字程序字) ) 虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。 区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。 假定页面大小1024字节，虚地址共占用2个字节(16位) 页号 页内地址（位移量） P W 15 10 9 0页式地址变换页式地址变换- -虚地址结构虚地址结构页式地址变换页式地址变换页式地址变换页式地址变换l页式地址映射页式地址映射虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出l将虚地址转换成二进制的数；l按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；l根据题意产生页表；l将位移量直接
75、复制到内存地址寄存器的低位部分；l以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。页式地址变换页式地址变换l页式地址映射页式地址映射虚地址以十进制数给出l 页号虚地址页大小l 位移量虚地址 mod 页大小l 根据题意产生页表；l 以页号查页表，得到对应页装入内存的块号l 内存地址块号页大小位移量请调策略请调策略l问题的提出问题的提出在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求
76、分页存储管理技术。请调策略请调策略l请求分页概念请求分页概念 请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。请求分页的基本思想请求分页的基本思想（1）请求分页请求分页=分页分页+请求请求 逻辑空间分页逻辑空间分页 物理空间分块物理空间分块 页与块同样大页与块同样大 页连续块离散页连续块离散 用页号查页表用页号查页表 硬件做重定位硬件做重定位分分 页页请求分页的基本思想请求分页的基本思想（
77、2）作业部分装入内存）作业部分装入内存（3）作业所占的内存块不连续）作业所占的内存块不连续（4）硬件通过页表生成访问内存的）硬件通过页表生成访问内存的地址地址 请求分页的基本思想请求分页的基本思想（5）若发生缺页，则进行缺页中断）若发生缺页，则进行缺页中断处理，将该页调入内存处理，将该页调入内存（6）利用快表可以加速地址转换）利用快表可以加速地址转换 缺页中断处理：请调缺页中断处理：请调为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。l中断位：0 表示该页在内存，1示该页不在内存l引用位：0 表示最近没有进程访问，1示最近有进程访问l修改位：
78、0 该页调入内存后没有修改 ，1页调入内存后修改过缺页中断处理的硬件支持缺页中断处理的硬件支持l采用相应技术加快页表的查询速度采用相应技术加快页表的查询速度 在页式存储技术中，我们可看到每访问一次内存，就要做两次访问内存的工作，即，查页表时要作一次访问内存的工作，然后是访问程序要求访问的内存，这样，存取速度降低一倍，将会影响整个系统的使用效率。在早期的计算机系统中有的采用联想存储器的技术来加快查表的速度，有的采用寄存器做页表。缺页中断处理的硬件支持缺页中断处理的硬件支持l采用联想存储器加快页表的查询速度采用联想存储器加快页表的查询速度快表。使用快表的并行查找过程。程序局部化与命中率问题。缺页中
79、断处理过程缺页中断处理过程l分地址分地址l取页号取页号l查页表查页表l缺页中断缺页中断l找空闲块找空闲块l淘汰块淘汰块l读入页面读入页面l中断返回中断返回硬件硬件软件软件请求分页的性能分析请求分页的性能分析l有效存取时间有效存取时间l缺页中断处理时间缺页中断处理时间l有效存取时间正比于缺页的比率有效存取时间正比于缺页的比率l为使速度下降控制在为使速度下降控制在10%以内，缺页率不得超过以内，缺页率不得超过0.00001淘汰策略淘汰策略物理页分配算法置换算法l当要索取一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法。颠簸、抖动几种置换算法几种置换
80、算法l先进先出算法先进先出算法先进入内存的页，先退出内存。实质上是淘汰在内存驻留时间最长的页。其理由是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。这种算法简单，实现容易。几种置换算法几种置换算法l最佳算法最佳算法假定程序p共有n页，而系统分配给它的内存只有m块（1mn），并且以作业在执行的过程中页面置换的频率的高低来衡量算法的优劣。访问的页在内存，称访问成功，否则为失败。 a=s+f a:访问的总次数 s：访问成功的次数 f：访问失败的次数几种置换算法几种置换算法缺页中断率f = f/a 则有： f f(r,m,p）最佳算法是指对于任何m和p，r:调度算法 有ff(r,m,p）最
81、小。最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。几种置换算法几种置换算法l最久未使用淘汰算法最久未使用淘汰算法（lRUlRU算法）算法）当需要淘汰一页时，选择最长时间未使用的页。如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。算法的实现（软件）：设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。淘汰一页时，总是从栈底抽出一个页号，它就是最久未使用的。算法的实现（硬件）：计数器近似LRU算法：NUR物理页分配算法物
82、理页分配算法l最少块数最少块数指令系统设计决定最少块数指令系统设计决定最少块数l全局分配与局部分配全局分配与局部分配l等分法与比例分配等分法与比例分配法法工作集模型工作集模型l时间局部化与空间局部化时间局部化与空间局部化l工作集工作集lDM，将，将出现抖动出现抖动l工作集模型的实现工作集模型的实现页式系统的存储保护页式系统的存储保护页式系统的存储保护的方法类似于基址限长存储保护，当地址映射机构分离出页号和页内位移后。若0页号用户程序的总页数，则访问合法，否则访问越界。页式系统的存储保护还包括存取控制。在页表中增加存取控制位，表示该页的存取控制权限，如r表示可读，w表示可读可写，e表示可执行。当
83、有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制。UNIX S_5的存储管理的存储管理l采用请求分页存储管理和对换技术采用请求分页存储管理和对换技术l对换对换：map表表l每次对换尽可能多的数据，不使用缓冲。每次对换尽可能多的数据，不使用缓冲。l请求分页数据结构请求分页数据结构l淘汰进程淘汰进程l缺页处理缺页处理段式系统段式系统l 一个用户程序往往由几个程序段（主程序、子一个用户程序往往由几个程序段（主程序、子程序和函数）所组成，当一个程序装入内存时，按段程序和函数）所组成，当一个程序装入内存时，按段进行分配，每个段的大小是不相等的。进行分配，每个段的大小是不相等的。程序地址的组成
84、：S：W例:lS1：XXXXlS2：XXXXlS3；XXXX段式系统段式系统段式系统段式系统l 以分区方式使用内存空间以分区方式使用内存空间l支持虚拟存储：分段调入支持虚拟存储：分段调入l快表的使用快表的使用l动态连接技术动态连接技术l缺段中断与连接中断缺段中断与连接中断 l段式保护与共享段式保护与共享l段式虚拟存储的优点和缺点段式虚拟存储的优点和缺点 段页式系统段页式系统在段式系统中，若段内分页，称为段页式系统。在段式系统中，若段内分页，称为段页式系统。段页式地址：段页式地址：s p ds p d段页式地址转换：查段表段页式地址转换：查段表 查页表查页表 合地址合地址快表的使用快表的使用段页
85、式系统是目前最好的内存管理方法段页式系统是目前最好的内存管理方法试分析段页式系统的优点与缺点试分析段页式系统的优点与缺点段页式系统段页式系统目目前前流流行行的的UNIXUNIX系系统统采采用用这这种种存存储储管管理理的的方方式式，一一个个进进程程的的图图象象分分为为U U区区、共共享享正正文文区区、用用户户栈栈区区和和数数据据区区，各各进进程程的的各各个个区区的的大大小小是是不不相相等等的的，只只有有U U区区的的大大小小是是相相等等的的。这这里里的的区区类类似似于于段段。每每个个段段又又分分成成大大小小相相等等的的页页，内内存存的的分分配配是是以以页页为为单单位位的的。因因 此此 ， 在在 UNIXUNIX系系 统统 中中 存存 储储 管管 理理 （ 上上 下下 文文 ，contextcontext）机构包括区表和页表。机构包括区表和页表。
