【文档说明】计算机操作系统原理课件.ppt，共(312)页，4.216 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76783.html

以下为本文档部分文字说明：

操作系统原理OperatingSystem第1章操作系统绪论•操作系统的概念•操作系统的历史•操作系统的特性•操作系统的基本类型•操作系统的功能•计算机硬件简介•算法的描述•研究操作系统的观点1.1操作系统概念•操作系统的地位•引入操作系统的目的•操作

系统定义Whatisoperatingsystem?1.1.1操作系统地位•硬件抽象层（HAL）之上•所有其它软件层之下硬件（HAL）OS其它系统软件层（如编译软件）应用软件层1.1.2引入操作系统的目的•从用户的观点：为用户（

应用程序）提供良好的服务界面。API、GUI•从系统管理员的观点：为管理和分配系统资源，提高系统工作效率。•从发展的观点：为系统提供功能扩展平台。1.1.3操作系统定义操作系统是位于硬件层(HAL)之上，所有其它软件层之下的一个系统软件，是管理和控制系统中各种软硬件资源，方便用户使用计算机系

统的程序集合。Operatingsupervisormonitoringprogram1.2操作系统的历史•操作系统的产生–手工操作阶段–成批处理阶段–执行系统阶段•操作系统的完善–多道批处理系统–分时系统–实时处理系统–通用操作系统•操作系统的发展–网络操作系统–分布式操作系统–多处理机操

作系统–单用户操作系统–面向对象操作系统–嵌入式操作系统–智能卡操作系统1.3操作系统特性•程序并发性–多个程序在宏观上同时向前推进、微观上串行推进–并发(concurrent)vs.并行(parallel)•资源共享性–多个程序

共用系统中的各种软硬件资源–在操作系统的协调和控制下•虚拟性–物理上的一台设备变成逻辑上的多台设备•不确定性1.4操作系统的基本类型•多道批处理操作系统(batchprocessingsystem)•分时操作系统(tim

e-sharingsystem)•实时操作系统(realtimesystem)•通用操作系统(multi-purposesystem)•单用户操作系统(singleusersystem)•网络操作系统(network

operatingsystem)•分布式操作系统(distributedoperatingsystem)•多处理机操作系统(multi-processorsystem)1.4.1多道批处理系统（Off-line）1.4.1多道

批处理系统•特点–多道：系统中同时容纳多个作业–成批：作业分批进入系统–宏观上并行，微观上串行多道批处理系统是以脱机为标志的操作系统，适用于处理运行时间比较长的程序。•主机中作业合理搭配–目标1：提高资源利用率–目标2：

提高吞吐量(throughput)界面1：交互式命令语言(eg.shell,command)界面2：图形用户界面(GUI)1.4.2分时操作系统（On-line）TimeSharingOSHAL终端终端终端…...

1.4.2分时操作系统•特点：–多路性：一个主机与多个终端相连；–交互性：以对话的方式为用户服务；–独占性：每个终端用户仿佛拥有一台虚拟机。分时操作系统是以联机为标志的操作系统，特别适用于程序的动态调试与修改。

1.4.3实时操作系统•实时控制–工业控制，军事控制，医疗控制，…….•实时信息处理–航班定票，联机情报检索，…….实时控制HALRealTimeOS被控对象A/DD/At1t2t2-t1:responsetime实时信息处理HALRealTimeOS….终端终端终端通常为远程终端特点：

（1）响应及时（promptresponse）（2）可靠性高（highreliability）1.4.4通用操作系统(multi-purposeOS)•同时具有：分时、实时、批处理功能。•目标：–提高处理能力;–扩展应用领域。•常见模式:–分时(前台)+批处理(后

台)–实时(前台)+批处理(后台)Foreground/BackgroundSystem1.4.5单用户操作系统•同一时刻仅有一个用户使用的系统•应用领域：–台式机，笔记本，…….•特点：–单用户，多进程，多线程不同的程序，不同的进程；相同的程序,

不同的线程1.4.6网络操作系统DOS3host3NOS2host2Printer建立在宿主操作系统之上，提供网络通讯、网络资源共享、网络服务的软件包。NOS1host1网络操作系统的目标•相互通讯•资源共享（信息，设备

）•提供网络服务–databaseserver–ftpserver–e-mailserver–telnetserver–etc.NoTransparentview1.4.7分布式操作系统•紧耦合：(tig

htlycoupled)–由多机系统发展而来（多CPU）–有公共内存–多处理机操作系统CPU内存CPUCPU…1.4.7分布式操作系统•松散耦合：(looselycoupled)–由计算机网络发展而来（多Host)–无公共内存，无公共时钟DOShost3DO

Shost2DOShost11.4.7分布式操作系统•分布式操作系统特征:–统一的操作系统–资源的进一步共享–可靠性–透明性1.4.8多处理机操作系统•多处理机系统–具有公共内存的多CPU系统•对称多处理机系统(SMP)–没有主从关系的多处理机系统•多处理机操作系统

–有效管理和使用多个CPU的操作系统–复杂性：多个主动体（CPUs)•例子：–UNIX,Linux,Windows1.5操作系统的功能•处理机管理•存储管理•设备管理•信息管理（文件系统管理）•用户接口1.6计算机硬件简介1.6.1计算机的基本硬件元素构成计算机基本硬件元

素包含以下4种：处理器、存储器、输入输出控制与总线、外部设备。计算机的基本硬件元素1.6.2与操作系统相关的几种主要寄存器1.数据寄存器2.地址寄存器3.条件码寄存器4.程序计数器PC5.指令寄存器IR6.程序状态字PSW7.中断现场保护寄存器8.过程调用用堆栈1.6.3存储

器的访问速度存储介质的访问速度一般来说，速度高的存储介质，成本高，容量小；容量大的存储介质，速度慢，成本低。1.6.4指令的执行与中断指令的执行周期中断执行过程f1.6.4指令的执行与中断中断处理时的指令执行周期1.7算法

的描述算法描述的方式：自然语言流程图方式类Pascal语言本书：beginRepeatWhile条件If条件end操作dothen……操作……操作Untilodelse操作1.8研究操作系统的几种观点•操作系统是计算机资源的管理者•用户界面的观点•进程管理的观点第2章操

作系统用户界面•用户界面简介•一般用户的输入输出界面•命令控制界面•Linux与Windows的命令控制界面•系统调用2.1用户界面简介•用户界面的功能用户界面负责用户与操作系统之间的交互。•用户分类使用和管理计算机的应用程序的用户程序开发人员•用户界面分类

命令控制界面系统调用2.2一般用户的输入输出界面2.2.1作业的定义2.2.2作业组织2.2.3一般用户的输入输出方式2.2.1作业的定义在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作称为一个作业。作业

由不同的顺序相连的作业步组成。图2.1一般编程过程2.2.2作业组织图2.2作业说明书的主要内容2.2.3一般用户的输入输出方式•1.联机输入输出方式外围设备直接和主机相连，速度慢。•2.脱机输入输出

方式外围机进行联机输入输出处理，通过外围机的后援存储来实现和主机的连接。速度快。•3.直接耦合方式主机和外围机通过一个公共外存直接连接。速度快，人工不用干预2.2.3一般用户的输入输出方式图2.3直接耦合方式

•4.SPOOLING系统•5.网络联机方式2.2.3一般用户的输入输出方式外围设备通过通道或DMA器件与主机和外存相连。2.3命令控制界面用户使用命令控制界面的方式：1、脱机方式填写作业说明书，用户不能干预作业执行。2、

联机方式不用填写作业说明书，用户能够干预作业执行。2.4Linux与Windows的命令控制界面RedhatLinux9.0的窗口界面2.4.1Linux的命令控制界面2.4.1Linux的命令控制界面Linux的命令一般包含9类：1系统维护与管理

命令2文件操作与管理命令3进程管理命令4磁盘及设备管理命令5用户管理命令6文档操作命令7网络通信命令8程序开发命令9XWindows管理命令2.4.2Windows的命令控制界面Windows的命令控制界面分为两

个部分：窗口交互：通过键盘和鼠标在图形上操作。命令解释器：通过cmd.exe为用户服务。2.4.2Windows的命令控制界面图2.6相互调用批处理示例2.5系统调用系统调用分为6类：1设备管理2文件管理3进程控制4进程通

信5存储管理6线程管理2.5系统调用系统调用的处理过程第3章进程管理•进程的概念•进程的描述•进程状态及其转换•进程控制•进程互斥•进程同步•进程的通信•死锁问题•线程的概念、分类与执行3.1进程的概念•3.1.1程序的并发执行•3.1.2进程的定义3.1.1程序的并

发执行1.程序(program)用来描述计算机所要完成的独立功能，并在时间上严格地按前后次序相继地进行计算机操作序列集合，是一个静态的概念。2.程序的顺序执行（sequence)※程序顺序执行的概念一个具有独

立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。※程序顺序执行的特征﹡顺序性﹡封闭性﹡可再现性3.1.1程序的并发执行•3.程序的并发(concurrent)执行※程序的并发执行：宏观上同

时向前推进，微观上同一时刻只有一个程序运行。※程序并发执行分为两种：一种是程序间的并发。另一种是同一程序内部多条指令的并发。※程序并发执行的特性：交叉性、非封闭性、不可再现性3.1.1程序的并发执行•4.程序的顺序性与并发性举例：–顺序性•内部顺序性：P1:a1,

a2,a3;P2:b1,b2,b3•外部顺序性：a1,a2,a3,b1,b2,b3;b1,b2,b3,a1,a2,a3–并发性•内部并发性：P1:a1,a2,a3;P2:b1,b2,b3•外部并发性：a1,b1,b

2,a2,a3,b3;b1,b2,a1,b3,a2,a33.1.2进程的定义•定义：并发执行的程序在执行过程中分配和管理资源的基本单位。•定义强调两个方面：–动态：执行中的程序;–并发：可与其他进程同时执行。并发vs.并行•并

发：concurrent–宏观同时，“交替执行”，不要求多个CPU•并行：parallel–微观同时，要求多个CPU–“并行算法”3.1.2进程的定义•进程与程序的区别与联系：★进程是一个动态概念，程序是一个静态概念。★进程具有并发特征，而程序没有。★进程是竞争计算机系统资源的基本单位。★不同的进

程可以包含同一程序，只要该程序所对应的数据集不同。3.2进程的描述•进程控制块•进程组成与进程上下文•进程上下文的切换•进程空间与大小•进程的类型•进程的相互联系与相互作用3.2.1进程控制块PCB•定义：标志进程存在的数据结构，其中保存系统管理进程所需的全部信息。•PC

B的内容：(不同系统不尽相同)–1.描述信息–2.控制信息–3.资源管理信息–4.CPU现场保护结构ProcessControlBlock3.2.2进程的组成与上下文•进程的组成–进程控制块(proce

sscontrolblock)•建立进程建立PCB•撤销PCB撤销进程–程序•代码(code)•数据(data)•堆栈(stack+heap)3.2.2进程的组成与上下文•进程的表记PCB程序PCB代码数据+堆栈表记1表记2系统空间用户空间3.2.2进程的组成与

上下文进程上下文（processcontext)–进程的物理实体与支持进程运行的物理环境统称为进程上下文。PCB+程序系统环境：地址空间，系统栈，打开文件表，…3.2.2进程的组成与上下文进程上下文结构3.2.3进程上下文

切换•上下文切换（contextswitch)–由一个进程的上下文转到另外一个进程的上下文•系统开销（systemoverhead)–运行操作系统程序完成系统管理工作所花费的时间和空间3.2.3进程上下文切换进程上下文的切换过程3.2.4进程空间与大小进程在内存中自己拥有的一个地址空间称为

进程空间。进程空间的大小只与处理机的位数有关。一般，进程空间可以分为：用户空间与系统空间。用户程序在用户空间中运行。操作系统内核程序在系统空间中运行。3.2.5进程的类型•进程类型–系统进程•运行操作系

统程序，完成系统管理(服务)功能.–用户进程•运行用户(应用)程序，为用户服务。3.2.6进程间相互联系与相互作用•相互联系–相关进程•同一家族的进程•可以共享文件，需要相互通讯，协调推进速度…•父进程可以监视子进程，子进程

完成父进程交给的任务。–无关进程•没有逻辑关系、同时执行的进程。•有资源竞争关系，互斥、死锁、饿死。3.2.6进程间相互联系与相互作用•相互作用1.直接相互作用：发生在相关进程之间2.间接相互作用：发生在任何进程之间RP2P1syncsendr

eceiveP1:P2:holdwait3.3进程状态及其转换•进程的状态•进程状态的转换•进程队列3.3.1进程状态•进程状态：初始态（Initial）：进程刚被创建，其他进程正占据处理器而得不到执行。运行态（Run）：占有CPU正在向前推进

。就绪态（Ready）：可以运行，但未得到CPU。等待态（Wait）：等待某一事件发生。终止态（Stop）：进程执行结束，将退出执行而被终止。3.3.2进程状态转换•状态转换–就绪运行：获得处理机–运行就绪：剥夺处理机

–运行等待：申请资源未得到，启动IO–等待就绪：得到资源，IO中断就绪等待运行获得处理机剥夺处理机等待事件事件发生3.3.2进程状态转换图3.3.2进程状态转换图就绪等待运行获得处理机剥夺处理机等待事件事件发生初创终止创建结束3.3.3进程队列PCBPCBPCB……head1.就绪队列：

系统一个或若干个（根据调度算法确定）2.等待队列：每个等待事件一个3.运行队列：每个处理机一个PCB构成的队列：（不一定FIFO)3.4进程控制进程控制：系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进

程高效率并发执行和协调、实现资源共享的目的。原语：系统态下执行的某些具有特定功能的程序段。原语的分类：机器指令级：不许中断功能级：不许并发3.4.1进程创建与撤销进程创建方式：系统创建父进程创建3.4.1进程创建与撤销进程撤销的方式：正常终止非正常终

止祖先进程撤销3.4.2进程的阻塞与唤醒阻塞原语图阻塞原语实现了进程由执行状态到等待状态的转变。阻塞原语是由进程自己调用的。3.4.2进程的阻塞与唤醒唤醒原语唤醒原语实现了进程由等待状态到就绪状态的转变。唤醒的方式:系统进程唤醒事件发生进程唤醒3.5进程互斥•与时间有关的错误•共享变量

与临界区域•进程互斥•进程互斥的实现•信号灯与P，V原语3.5.1与时间有关的错误例：图书借阅系统（x:某种书册数，设当前x=1.）终端1：终端2：CYCLECYCLE等待借书者；等待借书者；IFx>=1The

nIFx>=1ThenBeginBeginx:=x-1;x:=x-1;借书借书EndEndElse无书Else无书EndEnd3.5.1与时间有关的错误错误原因之1：进程执行交叉(interleave);错误原因之2：涉及公共变量(x)。注意:某些交叉结果不正确;必须去掉导致

不正确结果的交叉。3.5.2共享变量与临界区域•共享变量（sharedvariable）–多个进程都需要访问的变量。•临界区域（criticalregion）–访问共享变量的程序段。一组公共变量CR1CR2CRn…….临界区的表示共享变量:shared<一组变量>临界区域:region<一组变

量>do<语句＞例子：sharedB:array[0,..,n-1]ofinteger;regionBdoregionBdobeginbegin……(访问B）…..（访问B）.end;end;3.5.3进程互斥定义：多个进程不能同时进入关于同一组共享变量的临界区域，否

则可能发生与时间有关的错误，这种现象称为进程互斥。二层涵义：（1）任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域；（2）任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域。注意:互斥是相对于公共变量而言的。•

并发进程互斥执行必须满足4条准则：＊不能假设并发进程的相对执行速度。＊某进程不在临界区，不能阻止其他进程进入临界区。＊若干进程申请进入临界区，只能允许一个进程进入。＊某进程申请进入临界区，应该在有限的时间内得以进入临界区。3.5.3进程互斥3.5.4进程互斥的实现进程互斥的实现有

两种方法：◆软件方法实现：完全用程序实现，不需特殊硬件指令支持。可用于单CPU和多CPU环境中。有忙式等待问题Busywaiting“运行”或“就绪”3.5.4进程互斥的实现◆硬件方法实现：＊硬件提供“测试并建立”指令、“交换”指令＊硬件提供“关中断”和“开中断”指令关中断{Criti

calRegion}开中断Remarks:(1)开关中断只在单CPU系统中效;(why?)(2)影响并发性。3.5.4进程互斥的实现例：对临界区加锁实现互斥:当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。lock(

key[s])〈临界区〉unlock(key[s])3.5.5信号灯与P，V原语E.W.Dijkstra,1965.信号灯与PV操作的定义TYPEsemaphore=RECORDvalue:integer;queue:

PCBpointer;END;VARs:semaphore;备注:(1)semaphore是一个提前定义好的数据类型.(2)s是一个信号灯变量,使用前必须先声明.例如:vars1,s2:semaphore;信号灯变量S.valueS.queueS.valueS.queuePCBPCBPCBVa

rS:semaphore;FIFOP操作原语P操作原语：ProcedureP(vars:semaphore)s.value:=s.value-1;Ifs.value<0Thenasleep(s.queue)Endasleep(s.queue):(1)执行此操作进程

的PCB入s.queue尾（状态改为等待）；(2)转处理机调度程序。Primitive:apieceofcodeun-interruptibleV操作原语V操作原语：ProcedureV(vars:semaphore)s.value:=s

.value+1;Ifs.value<=0Thenwakeup(s.queue)Endwakeup(s.queue)s.queue链头PCB出等待队列，进入就绪队列（状态改为就绪）。Primitive:apieceofcodeun-interrupti

ble规定和结论•对于信号灯变量的规定：–必须置一次初值，只能置一次初值，初值>=0;–只能执行P操作和V操作，所有其它操作非法。•几个有用的结论：–当s.value>=0时，s.queue为空；–当s.value<0时，|s.value|为队列s.queue的长度；–当s.value初=

1时，可以实现进程互斥；–当s.value初=0时，可以实现进程同步。用信号灯实现进程互斥Varmutex:semaphore;(初值=1）sharedx,y,z:integer;CR1CR2CRn用信号灯实现进程互斥Varmutex:semaphore;(初值=1）sharedx,y,z

:integer;P(mutex)P(mutex)P(mutex)CR1CR2CRnV(mutex)V(mutex)V(mutex)互斥例子：借书系统(revisited)•Varmutex:semapho

re;(initialvalueis1)•终端1：终端2：•CYCLECYCLE•等待借书者；等待借书者；•P(mutex)P(mutex)•IFx>=1ThenIFx>=1Then•BeginBegin•x:=x-1;x:=x-1;•

V(mutex)V(mutex)•借书借书•EndEnd•ElseV(mutex);无书;ElseV(mutex);无书;•EndEnd3.6进程同步3.6.1进程同步的概念例：司机-乘客问题司机活动：(P1)乘客活动：(

P2)do{do{启动车辆上车正常行驶投币到站停车下车while(1)while(1)3.6.1进程同步的概念定义：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。

P1:P2:synchronize后先3.6.2进程同步机制•定义：用于实现进程同步的工具称为同步机制（synchronizationmechanism）•同步机制要求：–描述能力够用;–可实现;–高效;–使用方便.3.6.3用信号灯实现进程同步General

Case:VARS:semaphore;(initialvalue0)P(S)后动作先动作V(S)P1:P2:用信号灯实现进程同步例子：司机-乘客问题：VARs1,s2:semaphore;(initialva

lue0)司机活动：售票员活动：RepeatRepeatP(S1)上车启动车辆V(S1)正常行驶投币到站停车P(S2)V(S2)下车UntilfalseUntilfalse典型的进程同步问题生产者——消费者问题生产者/消费者问题预备知识：组合资源：若干相对独立的资源构成的资源集合，其中

每个相对独立的资源称为子资源。同种组合资源：相同类型子资源构成的组合资源。管理：VarS:semaphore;(初值=子资源个数）例子：2台打印机VarS:semaphore;S.value=2;申请：P（S）；释放：V（S）；22自动机描述…10-1-2P(S)P(S)P(S)P(S

)P(S)V(S)V(S)V(S)V(S)V(S)S.value=空闲资源数S.queue=空|S.value|=等待进程数空闲资源数=0...生产者/消费者问题01……k-1箱子，容量kB:Array[0..k-1]Ofitem生产者消费者生产物品放入B中从B中取物品消费之环形缓冲区10K-1

in(in+1)modkout(out+1)modk问题分析生产者活动：消费者活动：do{do加工一件物品箱中取一物品物品放入箱中消耗这件物品while(1)while(1)资源：箱子（同种组合）资源：物品（同种组合）VarS1:semaphore;VarS2:sema

phore;S1.value=k;S2.value=0;放前：P（S1）取前：P（S2）放后：V（S2）取后：V（S1）同步生产者活动：消费者活动：RepeatRepeat加工一件物品P(S2)P(S1)箱中取一物品物品放入箱中V(S1)V(S2)消耗这件物品UntilfalseUnt

ilfalse对B和in,out的互斥：Varmutex:semaphore;(mutex.value=1)互斥生产者活动：消费者活动：RepeatRepeat加工一件物品P(S2)P(S1)P(mutex)P(mutex)箱中取一物品物品放入箱中V(mutex)V(mutex)V(S1)

V(S2)消耗这件物品UntilfalseUntilfalse程序Programproducers_consumers;VarB:Array[0,…,k-1]Ofitem;S1,S2,mutex:semaphore;in,out:0..k-1;Procedureproducer

cycleproduceaproductP(S1);P(mutex);B[in]:=product;in:=(in+1)modk;V(mutex);V(S2)endProcedureconsumercycleP(s2);P(mutex);x:=B[

out];out:=(out+1)modk;V(mutex);V(S1);consumex;end;程序BeginS1.value:=k;S2.value:=0;mutex.value:=1;in:=0;out:=0;CobeginP1:p

roducer;……,Pm:producer;C1:consumer;……,Cn:consumer;Coend;End.并发性提高策略生产者和消费者：不操作B的相同分量生产者的共享变量：B[in]，in消费者的共享变量：B[out]，outin=out:满或空,Var

mutex1,mutex2:semaphore;(init1)并发性提高策略生产者活动：消费者活动：RepeatRepeat加工一件物品P(S2)P(S1)P(mutex2)P(mutex1)箱中取一物品物品放入箱中V(mutex2)V(mutex1)V(S1)V(S2

)消耗这件物品UntilfalseUntilfalse3.7进程通信•进程通信：进程之间的数据传送。•低级通讯（简单信号）–进程互斥–进程同步•高级通讯（大宗信息）3.7.1进程通信的概念3.7进程通信单机系统中进程通信可以分为4种形式：1、主从式2、会话式3、消息或邮箱机制4、共享存储方式3.8

死锁问题•死锁的概念•死锁类型•死锁的条件•死锁的处理•资源分配图•死锁预防•死锁避免•死锁的检测•死锁的恢复3.8.1死锁的概念例子：r1和r2为可再用资源;P1:applyforr1;...applyforr2;...returnr2;...retur

nr1;P2:applyforr2;...applyforr1;...returnr1;...returnr2;12死锁概念有并发进程P1,P2,……Pn，它们共享资源R1,R2,……Rm(n＞0，m＞0，n＞＝m）。其中，每个Pi（1≤i≤n）拥有资源Rj(1≤j≤m)，直

到不再有剩余资源。同时，各Pi又在不释放Rj的前提下要求得到Rk（k≠j，1≤k≤m），从而造成资源的互相占有和互相等待。在没有外力驱动的情况下，该组并发进程停止住往前推进，陷入永久等待状态。把这种现象称为死锁。由概念得到的结论•几个有用的结论：–参与

死琐的进程至少有二个；–每个参与死锁的进程均等待资源；–参与死锁的进程中至少有两个进程占有资源；–死锁进程是系统中当前进程集合的一个子集。3.8.2死锁类型1.竞争资源引起的死锁（1）不同种资源（2）同种资源4台打印机，申请:a,释放aP1:aaaaaaaaP2:aaaaDBACW:

直行E：左转S：左转3.8.2死锁类型2.进程通讯引起的死锁P1：receive(P2,M1);P2:receive(P3,M2);P3:receive(P1,M3);3.其它原因引起的死锁1.Afteryou/afteryou3.8.3死锁的条件•Coffman条件

（必要条件）–资源独占（mutualexclusion）–不可抢占（nonpreemption）–保持申请（hold-while-applying）–循环等待（circularwait）•当每类资源只有一个实例时，充要条件。•破坏上述任意一个条件可以消除死锁。3.8.4死锁的处理•死锁预防（de

adlockprevention）--静态•死锁避免（deadlockavoidance）--动态•死锁检测（deadlockdetection）•死锁恢复（deadlockrecovery）3.8.5资源分配图定义:G=(V,E),V=P∪R,P={p1,p2,…,pn},R={r1,r2,…

,rm},E={(pi,rj)}∪{(rj,pi)},piP,rjR.申请边(pi,rj):pi申请rj；分配边(rj,pi):rj分配pi;图示：进程：资源：申请边：由进程到资源类；分配边：由资源实例到进程。3.8.5资源分配图申请：pi申请

rj中的一个资源实例，由pi向rj画一申请边，如可满足，改为分配边。释放：去掉分配边。例子（无环路，无死锁）例1.P={p1,p2,p3},R={r1(1),r2(2),r3(1),r4(3)}E={(p1,r1),(p2,r3),(

r1,p2),(r2,p1),(r2,p2),(r3,p3)}p1p2p3r1r3r2r4例子（有环路，有死锁）p1p2p3r1r3r2r4增加边（p3,r2)例子（有环路，无死锁）p1p2p3p4r1r23.8.6死锁预防•对进程有关资源的活动加限制，

所有进程遵循这种限制，即可保证没有死锁发生。–优点：简单，系统不需要做什么。–缺点：对进程的约束，违反约束仍可能死锁。•预防方法：–预先分配法；–有序分配法。3.8.6.1预先分配法•进程：运行前申请所需全部资源；•系统：–能够满足，全部分配，–否则，一

个也不分配。•破坏“hold-and-wait”条件•缺点：–资源利用效率低；–一次提出申请困难。3.8.6.2有序分配法资源集：R={r1,r2,…,rn}函数：F：RN例如：R={scanner,tap

e,printer}F(scanner)=1;F(tape)=2;F(printer)=3;进程pi可以申请资源rj中的实例rl,pi占有rl,F(rl)F(rj)r1r2rkrm......申请次序3.8.6.2有序分配法证明无死锁（deadlockfre

e)：反证，假定死锁时刻t1:p1无限等待rk1中的资源实例，被p2占有；时刻t2:p2无限等待rk2中的资源实例，被p3占有；…时刻tn:pn无限等待rkn中的资源实例，被p1占有;根据有序申请假设：F(rk1)<F(rk2)<…<F(r

kn)<F(rk1)矛盾。3.8.7死锁避免检测可满足请求分配不分配安全不安全系统处于安全状态：存在安全进程序列<p1,p2,…,pn>进程序列<p1,p2,…,pn>安全，p1,p2,…,pn可依次进行完。安全不安全死锁银行家算法(Cont.)Ban

ker’salgorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性检查。P={p1,p2,…,pn};R={r1,r2,…,rm};银行家算法(Con

t.)数据结构：Available:array[1..m]ofinteger;//系统可用资源Claim:array[1..n,1..m]ofinteger;//进程最大需求Allocation:ar

ray[1..n,1..m]ofinteger;//当前分配Need:array[1..n,1..m]ofinteger;//尚需资源Request:array[1..n,1..m]ofinteger;//当前请求临时变量：Wo

rk:array[1..m]ofinteger;Finish:array[1..n]ofboolean;银行家算法(Cont.)设X,Y为下标1..l的一维数组：XYj(1jl),X[j]Y[j]X:=Yj(1jl),X[j]:=Y[j

]X:=cj(1jl),X[j]:=cX±Yj(1jl),X[j]±Y[j]资源分配Pi请求资源Request[I]Need[I]请求超量，错返Request[I]Available不满足，等待Available:=Available-Request[I]

Allocation[I]:=Allocation[I]+Request[I]Need[I]:=Need[I]-Request[I]安全确认，pi继续Available:=Available+Request[I]Allocation[I]:=Allocation[I]-Request[I]Ne

ed[I]:=Need[I]+Request[I]pi等待FTFTTF安全性检测算法FWork:=Available;Finish:=false;有满足条件的j:Finish[j]=falseNeed[j]WorkFinish[j]=true;Work:=Work+Allocat

ion[j]Tj,finish[j]=trueTF安全不安全银行家算法例子R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}ClaimAllocationNeedAvailabl

eWorkFinishABCABCABCABCABC753010743332322200122902302600222211011433002431P0:p1:p2:p3:p4:安全进程序列：<p1,p3,p4,p2,p0>p1

请求：Request[1]=(1,0,2)银行家算法例子ClaimAllocationNeedAvailableWorkFinishABCABCABCABCABC7530107432303223020209023

02600222211011433002431P0:p1:p2:p3:p4:假定分配：安全进程序列：<p1,p3,p4,p0,p2>p4请求：Request[4]=(3,3,0),不能满足，等待；p0请求：Request[0]=(0,2,0),不安全，等待。

3.8.8死锁的检测数据结构：Available:array[1..m]ofinteger;Allocation:array[1..n,1..m]ofinteger;Request:array[1..n,1..

m]ofinteger;临时变量：Work:array[1..m]ofinteger;Finish:array[1..n]ofboolean;3.8.8.1死锁检测算法Work:=Available;Finish:=false;有满足条件的i:Finish

[i]=falseRequest[i]WorkFinish[i]=true;Work:=Work+Allocation[i]Ti,finish[i]=trueTFF无死锁死锁Finish[I]=trueforallocation[I]=0Remarks1.上述算法可以检测

到参与死锁的全部进程，包括占有资源和不占有资源的进程。2.如果希望只检测占有资源的进程，初始化时：Finish[i]=true,forAllocation[I]=0死锁例子例子：R={A(7),B(2),C(6)};P={p

0,p1,p2,p3,p4}AllocationRequestAvailableWorkFinishABCABCABCABCp0:010000000p1:200202p2:303000p3:211100p4:002002未死锁。此时，Re

quest[2]=(0,0,1),死锁，参与死锁进程{p1,p2,p3,p4}3.8.8.2死锁检测时刻考虑因素：死锁发生频度；死锁影响进程。1.等待时检测：发现早，恢复代价小，开销大（overhead)。2.定时检测：3.资源（eg.CPU）利用率下降时检测。3.8.9死

锁的恢复1.重新启动简单，代价大，涉及未参与死锁的进程。2.终止进程(processtermination)环路上占有资源的进程。(1)一次性全部终止；(2)逐步终止（优先级，代价函数）3.剥夺资源(resourcepreemption)+进程回退(rollback)(1)sele

ctavictim；(2)rollback.问题:(1)保存snapshot代价大；(2)消除影响困难;(3)starvation.3.9线程的概念•3.9.1线程的引入•3.9.2线程的概念•3.9.3线程的结构•3.9.4线程的实现Threa

dandProcess3.9.1线程的引入•进程切换–上下文涉及内容多，开销大，“笨重”–相关进程之间耦合关系差•解决方案–Multi-threading–同一进程中包含多个线程–上下文只涉及寄存器和用

户栈，切换速度快–相关线程之间通讯方便、快捷3.9.2线程的概念•进程中一个相对独立的执行流。•进程vs.线程–进程是资源分配单位–线程是执行单位•多线程优点–切换速度快（地址空间不变）(lightweighted)

–系统开销小–通讯容易（共享数据空间）线程控制块•TCB（Threadcontrolblock)–标志线程存在的数据结构，其中包含对线程管理需要的全部信息．•内容–线程标识–线程状态–调度参数–现场(通用寄存器,PC,SP)•存放位置–用户级线程

：目态空间（运行系统）–核心级线程：系统空间3.9.3线程结构寄存器静态数据程序代码栈寄存器进程2动态堆内存多进程结构（用户视图）静态数据程序代码栈进程1动态堆内存寄存器3.9.3线程结构静态数据程序代码栈栈寄存器寄存器线程1：线程2：进程动态堆内存多线程结构（用户视图）3.9.3

线程结构（另一种表示）textsegmentdatasegmentProgramcounterTask:3.9.4线程的实现•3.9.4.1用户级别线程–User-levelthread•3.9.4.2核心级别线程–

Kernel-levelthread3.9.4.1用户级别线程•实现方法：–基于library函数，系统不可见–线程创建、撤销、状态转换在目态完成–TCB在用户空间，每个进程一个系统栈•优点：–不依赖于操作系统，调度

灵活–切换速度快•缺点：–同一进程中多个线程不能真正并行–一个线程进入系统受阻，进程中其它线程不能执行3.9.4.1用户级别线程运行系统TCB进程线程核心栈进程表用户空间系统空间3.9.4.2核心级线程•实现方法：–基于系统调用–创建、撤销、状态转换由操作系统完成•优点：–同一进程内多线程

可以并行执行–一线程进入核心等待，其它线程仍可执行•缺点：–系统开销大，同一进程内多线程切换速度慢–调度算法不能灵活控制3.9.4.2核心级线程进程线程核心栈进程表用户空间系统空间TCB第4章处理机调度处

理机调度是指处理机在可运行实体上的分配进程、线程不同类型的操作系统采用不同的处理机的调度策略批处理系统、分时系统、实时系统第4章处理机调度分级调度作业调度进程调度调度算法实时调度算法4.1分级调度4.1.1作业的状态及其转换一个作业从用户提交开始到占有处理机被执行，要由系统经过多级调度

才能实现。通常指批处理系统一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成等四个状态。4.1.1作业的状态及其转换作业的状态及其转换4.1.1作业的状态及其转换作业的提交

状态：从输入设备进入外部存储设备的过程。作业的后备状态：作业的全部信息输入至输入井。作业的执行状态：被作业调度程序选中的作业所处的状态。作业的完成状态：作业运行完毕，所占用的资源尚未全部被系统回收。4.1.2调度的层次只有参与竞争处理机

所必需的资源都已经得到满足的进程才能有资格竞争处理机。这些必需的资源包括内存、外设及有关数据结构等。4.1.2调度的层次处理机调度分为4级：作业调度（高级调度）交换调度（中级调度）进程调度（进程调度）线程调度对输入井的作业进行选择，为其分配内存、设备；创建根进程；回收系统资源根据系统并发度

，完成进程在内外存的换入和换出。选取一个处于就绪状态的进程占用处理机4.1.3作业与进程的关系作业是用户向计算机提交任务的任务实体进程是为了完成用户任务实体二设置的执行实体。一个作业由一个以上的进程组成。作业进

程4.2作业调度4.2.1作业调度功能1）记录系统中各作业的状况。2）从后备队列中挑选出一部分作业投入执行。3）为被选中作业做好执行前的准备工作。4）在作业执行结束时善后处理工作。主要完成作业从后备状态到执行状态的转变，以及从执行状态到完

成状态的转变。4.2作业调度4.2作业调度4.2.2作业调度目标与性能衡量作业调度目标：1）对所有作业应该是公平合理的2）应使设备有高的利用率3）每天执行尽可能多的作业4）有快的响应时间性能衡量指标：周转时间带权周转时间4.3进程调度4.3.1进程调度的功能1.记录系统中所有进程的执行

情况2.选择占有处理机的进程3.进行进程上下文切换4.3进程调度4.3.2进程调度的时机剥夺式调度与非剥夺式调度•剥夺式(preemptive)–就绪进程可以从运行进程手中抢占CPU。•非剥夺式(non-preemptive)–就绪进程不可从运行进程手中抢占CPU。4.3进程调度

4.3.2进程调度的时机进程调度的原因：1）运行的进程执行结束2）运行的进程调用阻塞原语（主动等待）3）运行的进程调用了P、V原语4）运行的进程提出I/O请求5）分时系统中时间片已经用完6）系统进程执行完毕时7）就绪队列中的某个进程的优先级别高于当前执行进程的优先级

。进程等待4.3进程调度4.3.2进程调度性能评价进程调度性能的衡量是操作系统设计的一个重要指标。进程调度性能的衡量方法可分为定性和定量两种：定性衡量方面：可靠性和简洁性定量衡量方面：CPU的利用率评价、就绪进程

的等待时机与执行时间之比等。4.4调度算法1先到先服务FCFS算法–按作业和进程的提交顺序或申请CPU（就绪）的次序。–Gantt图（到达次序：P1，P2，P3）processBursttimeP127P23P35P1P2P30273035–平均等待时间：（0+27+30）/3=19

（ms)–Gantt图（到达次序：P2，P3，P1）–平均等待时间•（0+3+8）/3=3.67P1P2P3038354.4调度算法1先到先服务FCFS算法1先到先服务算法•优缺点：–“公平”；–短作业等待时间长。作业的执行时间短2短作业优先•SJF（Sho

rtestJobFirst)–按作业的执行时间长度–Gantchart:ProcessBursttimeP112P25P37P43P1P3P2P403815272短作业优先(SJF)–平均等待时间：•（0+3+8+15）/4=6.5（ms)–特点：•

假定所有任务同时到达，平均等待时间最短。•长作业可能被饿死。3最高优先数算法(HPF)•静态优先数(static)–优先数在进程创建时分配，生存期内不变。–响应速度慢，开销小，系统效率低。–适合批处理进程•动态优

先数(dynamic)–进程创建时继承优先数，生存期内可以修改。–响应速度快，开销大。作业或进程执行之前就确定作业进程执行的过程中确定3最高优先数算法•非剥夺式静态优先数–获得处理机的进程运行，直至•终止•等待•剥夺式动(静)态优先数–获得处理机的进程运行，直至•

终止•等待•出现高优先级的进程•作业调度中静态优先数的确定原则：1）用户确定2）根据作业类型指定3）根据资源情况指定2）和3）都是由系统和操作员确定的•进程调度中静态优先数的确定原则：1）进程类型2）继承作业的优先数3最高优先数算法(Cont.)3最高优先

数算法进程的动态优先数的确定原则：1）根据进程占有CPU时间的长短。2）根据就绪进程等待CPU的时间长短。4循环轮转算法(RR)基本思路：让每个进程在等待队列中的等待时间与享受服务的时间成比例。4循环轮转算法(RR)•RoundRobin(RR)•基

本轮转–时间片(quantum,timeslice)长度固定，不变；–所有进程等速向前推进。•改进轮转–时间片长度不定，可变。4循环轮转算法•时间片长度：几十毫秒几百毫秒(eg.50ms)–过长：响应速度慢；–过短：

系统开销(overhead)大。•适应系统：–分时系统主机把时间片轮流分配给各个终端5多级队列算法(MLQ)•多级队列–多个就绪队列，进程所属的队列固定。•例如：通用系统中：–队列1：实时进程就绪队列（HPF）–队列2：分时进程就绪队列（RR）–队列3：批处理

进程就绪队列（HPF）6反馈排队算法(FB)•Feed-Back:–多个就绪队列，进程所属队列可变。Q1（RR，HPF）Q2（RR，HPF）Qn（RR，HPF）运行s1时间片运行s2时间片….创建唤醒优先级时间片运行sn时

间片6反馈排队算法•调度效果：–资源利用率高•被唤醒的进程尽早投入运行；–响应速度快•交互式进程反应及时；–系统开销小•计算量大的进程落入底层队列。4.5实时系统调度方法4.5.1实时系统的特点1）有限等待时间2

）有限响应时间3）用户控制4）可靠性高5）系统出错处理能力强实时操作系统的能力：1.很快的进程或线程切换速度2.快速的外部中断响应能力3.基于优先级的随时抢先式调度策略4.5实时调度(real-timescheduling)实

时任务：–具有明确时间约束的计算任务。–Eg.•某时刻前必须开始处理•某时刻前必须处理完毕实时调度：–合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。实时任务分类•硬实时与软实时–硬实时:必须满足任务截止期

要求.–软实时:期望满足截止期要求.•周期性与随机性–周期性:每隔固定时间发生一次–随机性:由随机事件触发，其发生时刻不确定?术语解释•Readytime:就绪时间•Startingdeadline:开始截止期•Proc

essingtime:处理时间•Completiondeadline:完成截止期•Occurringfrequency:发生频率4.5实时调度(real-timescheduling)4.5.2实时调度算法的分类1.静态表格驱动类2.静态优先级驱动抢先式调度算法类3.动态计划调度算法

类4.尽力而为调度算法类4.5实时调度(real-timescheduling)4.5.3时限调度算法与频率单调调度算法周期性实时事务令Ci为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,…,Pm可调度的必要条件为：11miiTiC周期性实时事务例：–P1

=100,P2=200,P3=500(ms)–C1=50,C2=30,C3=100(ms)–C1/P1+C2/P2+C3/P3=0.5+0.15+0.2=0.85<1–Schedulable周期性实时事务进程就绪时间处理时间完成截止期发生周期A0102020B025505010/20+25

/50=1,可调度(不考虑开销)例子ProcessArrivaltimeExecutiontimecompletiondeadlineA(1)A(2)A(3)A(4)A(5)…...B(1)B(2)020406080

…...0501010101010……252520406080100…...50100最早截止期(时限)调度•EDF（EarliestDeadlineFirst)–优先选择完成截止期最早的实时任务–可抢先式•可以证明：对EDF来说，可调度充分条件是：•在不可调度的条件下，可使错过

截止期任务最小化11miiiPC例子：Earliestdeadlinescheduling0102030405060708090100TimeB1B2A1A2A4A3A5A1dlA2dlA3dlA4dlB1dlB2dlA5dlA1B1A2B1A3B2A5B2A

4A1A2B1A3A4A5B2速率（频率）单调调度•RMS（RateMonotonicScheduling）–提出于1973年•面向周期性实时事务，非剥夺式•优先调度发生周期最短（频度最高）的实时任务–可调度

条件：)12(11niniinTCRMS的上限值)12(/1nnn123456┇1.00.8280.7790.7560.7430.734┇ln20.693RMSvs.EDF1)RMS可调度条件强于EDF2)RMS调度较EDF实现简单RMS例子：进程Ｔi

CiA10020B15040C350100779.0)12(3753.0286.0267.02.033221131TCTCTC可调度，具体调度结果：A1B1C1A2B2A3A4B3C202060160180220240300320360460第5章存储管理存储管理的功能分区

存储管理覆盖与交换技术页式管理段式与段页式管理5.1存储管理的功能5.1.1虚拟存储器实际上，进程是一部分放在内存，另一部分放在外存。系统为进程安排地址的方法有两种：一种是按照物理存储器中的位置赋予实

际物理地址；另一种是编译链接程序把用户源程序编译后链接到一个以0为始地址的线性或多维虚拟地址空间。5.1.1虚拟存储器♪虚拟空间：每个进程都拥有一个由存储管理方式来决定的空间。♪物理地址（内存地址）：物理存储器的实际地址。♪物理地址空间（内存空间）：内存地址的集合。♪虚拟地址：虚拟空间中

的地址。♪地址转换：虚拟地址到物理地址的转变。♪虚拟存储器：将进程中的目标代码、数据等虚拟地址组成的虚拟空间。5.1.2地址转换地址映射：建立虚拟地址与内存地址的映射关系。实现地址重定位的方法有两种：静态重定位动态重定位1、静态地址重定位定义：静态地址重定位是在虚拟空间程序执行

之前由装配程序完成地址映射工作。优点：不需要硬件支持缺点：无法实现虚拟存储器、必须占用连续的内存空间。5.1.2地址转换2、动态地址重定位定义：动态地址重定位是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。

优点：可以对内存进行非连续分配；实现虚拟存储器；有利于程序段的共享。5.1.3内外存数据传输的控制内外存数据传输的控制方法：一、用户程序自己控制二、操作系统控制1、交换方式2、请求调入方式和预调入方式覆盖很少部分交换，未实现真正意义上的虚拟存储进行部分交换，实

现不受内存容量限制的虚拟存储5.1.4内存的分配与回收一个作业进入内存时操作系统需将其变为进程，并为进程分配存储空间。进程运行结束时，操作系统应将其所占有的存储空间回收。分配去配对象--内存、外存(相同方法)分配去配时刻--进程创建、撤销、交换、长度变化5.1.5内存信息的共享与保

护►内存信息的共享：目的：节省内存、提高内存利用率、相互通讯内容：代码、数据►内存信息的保护：保护方法：硬件法软件法硬软件结合法上下界保护法保护键法界限寄存器与CPU的工作状态相结合两个以上进程共用内存中

相同的区域，即物理空间有相交部分5.2分区存储管理◣分区管理基本原理◣分区的分配与回收◣有关问题讨论5.2.1分区管理基本原理1分区管理的基本原理：给每一个内存中的进程划分一块适当大小的存储区，以连续存储各个进程的程序和数据，使进程得以并发执行。5.2.1分区管理基本原

理2分区管理的方法固定分区法（静态）：在作业或进程执行之前就把内存区域固定地划分为若干个大小不等的区域。分区说明表总分区个数和分区长度不变5.2.1分区管理基本原理动态分区法：在作业或进程执行过程中把内存划分为大小不等的区域。空间大小可变，提高资源利用率

5.2.1分区管理基本原理可用表请求表5.2.2分区的分配与回收1固定分区时的分配与回收基本思路：分配：当用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大小。存储管理程序根据请求表查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者。回

收：进程执行完毕时，管理程序将对应的分区状态置为未使用。特点：简单5.2.2分区的分配与回收5.2.2分区的分配与回收2动态分区时的分配与回收动态分区时的分配方法：♦最先适应法♦最佳适应法♦最坏适应法5.2.2分区的分配与回收最先适应算法（F

irstFit）空闲区首址空闲区长度128641024256322560......空闲区：首址递增排列；申请：取第一个可满足区域；优点：尽量使用低地址空间，高区保持大空闲区域。缺点：可能分割大空闲区。Eg.申请32将分割第一个区域。5.2.2分区的分

配与回收最佳适应算法（BestFit）空闲区：空闲区域按照由小到大顺序；申请：取最小可满足区域；优点：尽量使用小空闲区，保持大空闲区。缺点：可能形成碎片Eg.申请30将留下长度为2的空闲区。空闲区首址空闲区长度256321024256641280..

....5.2.2分区的分配与回收最坏适应算法（WorstFit）空闲区：空闲区域由大到小顺序；申请：取最大可满足区域；优点：防止形成碎片。缺点：分割大空闲区域。空闲区首址空闲区长度25625632641280......10245.2.

2分区的分配与回收3动态分区时的回收与拼接当用户作业或进程执行结束时，存储管理程序要收回已使用完毕的空闲区，并将其插入空闲区可用表或自由链。这时，会碰到空闲区拼接问题，解决的问题办法就是空闲区集中（碎片处理）。空闲区首址空闲区长度............250015

00占用占用占用Head:5.2.2分区的分配与回收（a）和上下一起合并（c）和下一起合并（b）和上一起合并（d）自己成为一个新区5.2.3有关分区管理其他问题的讨论☻关于虚存的实现☻关于内存扩充☻关于地址变换和内存保护☻分区存储管理的主要优缺点5.3覆盖与交换技术♦覆盖技术♦交

换技术早期操作系统中使用现代操作系统仍然使用5.4页式管理页式管理的基本原理静态页面管理动态页式管理存储保护页式管理的优缺点5.4.1页式管理的基本原理♦进程的虚拟空间被划分成若干个长度相等的页♦内存空间也按页的大小划分为片或页面♦页式管理实现了内外存存储器的

统一管理♦分页管理的重点在于页划分后的地址变换以及页面的调入调出技术页内地址连续，页面可以不连续5.4.2静态页面管理静态页面管理方式：在作业或进程开始执行之前，把该作业或进程的程序段和数据全部装入内存的

各个页面中，并通过页表和硬件地址交换机构实现虚拟地址到内存物理地址的地址映射。1内存页面分配与回收（1）页表页表由页号与页面号组成页表在内存中占有一块固定的存储区页表的大小由作业或进程的大小决定5.4.2静态页面管理（2）请求表整个系

统一张，内容包括：进程号、请求页面数、页表开始地址、页表的长度和状态。5.4.2静态页面管理（3）存储页面表整个系统一张，指出内存各页面是否已被分配出去，以及未分配页面的总数。5.4.2静态页面管理2分配算法5.4.2静态页面管

理3地址变换（1）系统从请求表中取出所调度执行的进程页表开始地址和页表长度放入控制寄存器中。（2）由控制寄存器得到页表开始地址，根据虚拟地址得到物理地址。5.4.3动态页面管理动态页面管理方式：在作业或进程开始执行之前，不是把作业或进程一次性地全部装入内存，而只装入一部分，其他部分则在执行过程中动

态装入。请求页式管理和预调入页式管理请求页式管理预调入页式管理请求方式上的区别5.4.3动态页面管理为了配合动态页面管理，需要加入中断处理后的页表；加入改变位后的页表。5.4.4页式管理的优缺点◢优点--不用连续存放，解决了碎片问题--实现了内外存的统一管理◢缺

点--要求硬件支持--增加系统开销--请求调页的算法如不当选择，可能抖动--最后一页有浪费。5.5段式与段页式管理5.5.1段式存储管理1.内存空间划分：动态异长，每区一段。段首址+段内地址物理地址=b’：l’b’+d2.

进程空间划分：若干段，每段一个程序单位。调用x段ef:访问d段ae:调用y段fmain(段号0)X(段号1)Y(段号2)D(段号3)a:0…80k-10...40k-10…20k-10…60k-1逻辑地址=段号段内地址(二维地址)mainxyd3.对

应关系40k60k80k20k............进程空间内存空间100k:200k:300k:320k:4.所需表目(1)段表：每进程一个段首址段长度100k40k80k60k段号0:1:2:3:20k200k320k300k(2)空闲表：系统一个arrayof

(addr,size)5.所需寄存器(1)段表首址寄存器：bl(2)段表长度寄存器：系统一个系统一个(3)快表：系统一组：段号段首址段长度............l’s...b’...6.地址映射:(s,d)(b’

+d){}逻辑地址(s,d)物理地址(b’+d)(1)由程序确定逻辑地址(s,d);(2)由s查快表得b’和l’如查不到：(a)由s与l比较判断是否越界不满足：0sl-1，越界；(b)由s和

b查段表，得b’和l’(s,b’,l’)快表,如快表满淘汰一个；(c)转(2)(3)由d与l’比较，判断是否越界不满足：0dl’-1，越界；(4)由b’d得物理地址。段号段长段首址...…...…......l’b’slbbl......PCB段长段首址段号…..

.l’b’...s...b’+dsd+cpsl’b’物理地址逻辑地址…...cp+b:7段的共享段长段首址…...b’l’......段号…si...P1段表：段长段首址…...b’l’......段号…sj...P2段表：共享段......

b’:l’内存空间如何实现？共享段表段名共享记数段长段首址其它…………...vi335k125k??…………...共享段表：进程段表(n)共享段表(1)共享段(1)8段的保护(1)段表的改进：段长段首址……......l’b’101段号…s...访问权

限RWE……......段号段长段首址………......sl’b’101访问权限RWE(2)快表的改进：………......5.5段式与段页式管理5.5.2段页式存储管理♦段式优于页式便于共享和保护♦页式优于段式消除“碎片”问题♦段页式：结合二者优点每个

进程包含若干段每个段包含若干页5.2.2.1基本原理1.内存空间划分：(同页式)静态等长，2i,称为一页。物理地址=(页架号,页内地址)=(f,d)2.进程空间划分：一个进程若干个段一个段若干个页逻辑地址=(段号,

逻辑页号,页内地址)=(s,p,d)5.5.2段页式存储管理3.对应关系：0页1页2页0页1页第1段：0页1页2页第0段：第2段：25页26页27页28页29页30页31页32页33页......内存空间进程空间4.所需表目(1)段表：每个进程一个页表首址页

表长度…...b’l’…...段号0...s...l-1(2)页表：每个段一个逻辑页号0…p…l’-1页架号...f...(3)总页表：系统一个5.所需寄存器(1)段表基址寄存器：保存正运行程度段表首址；(2)段表限长寄存器：保存正运行程序段表

长度。(3)快表：一组联想寄存器(快段表+快页表)段号逻辑页号页架号……...spf……...bl6.地址映射(P.141):(s,p,d)(f,d){}逻辑地址(s,p,d)物理地址(f,d)(1)

由程序确定逻辑地址；(2)由(s,p)查快表得f；如找不到：(a)由s与l比较判断是否越界：不满足：0sl-1,越界(b)由s和b查段表得页表(b’,l’)(c)由p与l’比较判断是否越界：不满足：0pl’-1,越界(d)由b

’与p查页表得f(s,p,f)快表，若快表已满，淘汰一个(e)转(2)(3)由f与d合并得物理地址(f,d)第8章文件系统文件系统的概念文件的逻辑结构与存取方法文件的物理结构与存储设备文件存

储空间管理文件目录管理8.1文件系统的概念文件：一组赋名的相关联字符流的集合，或相关联记录的集合。信息项信息项…信息项…信息项读(写)指针文件系统：操作系统中与管理文件有关的软件与数据。它负责用户建立、撤销、读写、修改和复制文件，复制按名存取和存取控制。1文件与文件系统的概念8.1文件

系统的概念2文件的分类按文件的性质和用途分类系统文件—系统调用来使用；不可读写和修改库文件—可读写，执行；不可修改用户文件—授权使用按组织形式分类普通文件—一般格式的文件目录文件—文件的目录信息构成的特殊文

件特殊文件8.2文件的逻辑结构与存取方法8.2.1文件的逻辑结构文件的组织称为文件的结构。文件的逻辑结构是指外部组织形式，亦是用户所看到的组织形式。可分为两类：字符流式的无结构文件记录式的有结构文件访问以字节为

基本单位。查找基本单位困难，文件管理简单访问以记录为单位，记录可按不同的方式排列8.2.1文件的逻辑结构记录组成例8.2.1文件的逻辑结构1.连续结构：记录按生成的先后顺序连续排列2.多重结构：记录按关键字和记录名排列成行列式文件的记录名和关键字构成的行列式文件的多重结构8.2

.1文件的逻辑结构3.转置结构：记录按关键字和记录指针锁定4.顺序结构：记录按关键字的先后顺序排列文件的转置结构8.2文件的逻辑结构与存取方法8.2.2文件的存取方法文件的存取是指文件的访问方式，就是要找到文件内容所在的逻辑地

址。即用户使用文件时按何种次序存取文件的各个信息项。一般文件的访问方法如下：顺序存取随机存取按关键字存取按文件的逻辑地址顺序存取文件各个信息项按记录编号存取，或按存取指令把读写指针移到欲读写处常用于DBMS中，按照关键字和记录名存取8.3文件的物理结构与存储设备8.3.1文件的物理结

构文件的物理结构是指文件的内部组织形式，是指文件在物理存储设备上的组织形式。常用的文件物理结构：连续文件串联文件索引文件逻辑上连续的文件依次放入连续的物理块中逻辑上连续的文件放入不连续的物理块中增加索引表，说明逻辑块与

物理块的对应，文件说明信息项给出索引表的物理地址。8.3.1文件的物理结构连续结构串联结构索引结构8.3.2文件存储设备1.顺序存取设备2.直接存取设备磁盘的结构磁带的结构8.4文件存储空间管理文件存储设备是分成若干个大小相等的物理块，并以块为单位来交换信息的，因此，文件存储空间

的管理实质是一个空闲块的组织和管理问题，它包括空闲块的组织，空闲块的分配与回收等问题。8.4文件存储空间管理空闲块管理的方法有3种：1空闲文件目录空闲文件目录空闲块号空闲块个数空闲块号第一个空闲块号8.4

文件存储空间管理2.空闲块链把文件存储设备上的所有空闲块链接在一起。空闲区大小顺序链接；空闲区释放先后顺序链接；成组链接。8.4文件存储空间管理3.位示图100…1...10第0块第2块第1块第k块第n块......每个文件存储设备建立一张位示图。用一个bit代表一个块的状态，0表空闲，1

表占用。（多单元）8.5文件目录管理8.5.1文件的组成文件名和对该文件实施控制管理的控制管理信息称为该文件的文件说明，并把一个文件说明按一定的逻辑结构存放到物理存储块的一个表目中。文件体文件说明文件本身的信息也称为FCB。它包括文件名、文件内部标识、文件存储信息在文件存储设备上的第一个

物理块的地址。8.5.2文件目录文件控制块与目录项–文件控制块(FCB)文件存在的标志，保存系统管理文件需要的全部信息–目录项目录文件中的一项，内容为FCB文件目录与目录文件–文件目录用于检索文件的目录–目录文件内容为目录项的文件8.5.2文件目录FCB（FileCo

ntrolBlock）文件名文件号文件主文件类型文件属性共享说明文件长度文件地址建立日期最后修改日期最后访问日期口令其它FCB创建：建立文件时FCB撤消：删除文件时8.5.2文件目录单级目录(Single-LevelDirec

tory)Asingledirectoryforallusers.缺点:1.命名冲突问题2.搜索效率问题8.5.2文件目录8.5.2文件目录两级目录(Two-LevelDirectory)Separatedirectoryforeachuser.特点:1.路

径问题2.实现了文件重名和共享问题3.搜索效率高8.5.2文件目录rootbinusrlibdevetcunixlpccviusersLiWangd1d2consolebinyaccs多级目录(Multi-LevelDirectoryasinUNIX)8.5.3便于共享的文件目录1绕道

法2链接法8.5.3便于共享的文件目录3基本文件目录表BFD8.5.4目录管理方法：把当前正在使用的那些文件的目录表目复制到内存中。系统提供有关的目录文件复制到内存的指定区；以及当用户不再访问有关信息文件时

删去有关目录文件的内存副本。第9章设备管理设备管理的概述数据传送控制方式中断技术缓冲技术设备分配除CPU和内存之外的设备。包括输入输出设备、外存设备、终端设备和脱机设备。9.1设备管理的概述1设备的分类按设备的从属关系分类1)系统设备：在操作系统生成时已登记于系统中的各种标准设备。（如终

端、打印机、磁盘机等）1)用户设备：由用户提供设备及其处理程序，并通过适当的手段把它们纳入系统，由系统实施管理。（如A/D，D/A转换器，CAD所用专用设备）9.1设备管理的概述按设备的数据组织方式分类1)块设备：以数据块为单位来组织和传送数据的设备，如磁盘、磁带等。2

)字符设备：以单个字符为单位来传送信息的设备，如终端、打印机等。可以按照设备的性能分类9.1设备管理的概述图9.1按使用特性对外部设备的分类9.1设备管理的概述操作系统设备管理的目标1)提高外围设备的使用效率2)为用户提供方便、统一的界面设备管理的功能

1)设备分配2)缓冲区管理3)实现物理I/O操作4)提供进程管理系统的接口2设备管理的目标与功能9.2数据传输控制方式外围设备与内存或CPU之间的常用数据传送控制方式：1程序直接控制方式2中断控制方式3DMA方式4通道方式9.2

数据传输控制方式1程序直接控制方式用户程序优缺点：优点：控制简单、硬件支持少缺点：串行、无法发现错误、只能和一台外围设备交换。适用于CPU速度慢、外围设备少的系统9.2数据传输控制方式2中断方式中断请求线、中断允许位

优缺点：优点：CPU利用率高、实现并行操作缺点：消耗CPU的处理时间数据丢失9.2数据传输控制方式3DMA方式直接的数据交换通路优缺点：优点：克服了中断方式存在的问题缺点：CPU对外围设备的管理趋向复杂、不是很经济。9.2数据传输控制方式4通道方式独立于CPU的

负责输入输出控制的处理机，控制设备与内存直接进行数据交换。9.3中断技术•9.3.1中断的概念•9.3.2中断装置•9.3.3中断处理程序9.3.1中断的概念•处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序

，这一过程称为中断。•中断系统：–中断装置(硬件)–中断处理程序(软件)9.3.2中断装置•发现并响应中断的硬件机构–识别中断源，当有多个中断源时，按紧迫程度排队；–保存现场；–引出中断处理程序。中断响应和处理的过程正运行程序16处理

程序4PSW’，PC’PC’:PSW,PC系统桟psw,pc……...253HALOS9.3.2.1中断源与中断字•中断源–引起中断的事件。•中断寄存器–保存与中断事件相关信息的寄存器。•中断字–中断寄存器的内容。•例：IO中断：设备状态寄存器。9.3.2.

2中断类型与中断向量•强迫性中断–运行程序不期望的•时钟中断•IO中断•控制台中断•硬件故障中断–powerfailure–内存校验错•程序性中断–越界，越权，缺页–溢出，除0–非法指令•自愿性中断–运行程序期望的•系统调用•访管指令–系统调用•fd=open(fname,

mode)–访管指令•准备参数•svcn•取返回值9.3.2.2中断类型与中断向量中断装置中断处理程序运行程序访管指令运行程序中断装置中断处理程序clockIOconsolepowerfailuremalfunction强迫中断：自愿中断：SVCntra

pn9.3.2.2中断类型与中断向量•中断向量：中断处理程序的运行环境与入口地址（PSW，PC）–每类中断事件有一个中断向量,–中断向量的存放位置是由硬件规定的,–中断向量的内容是OS在系统初始化时设置好的。中断向量mode应为系统态9.3.2.2中断类型与中断向量P

SW1,PC1时钟中断向量PSW2,PC2I/O中断向量PSW3,PC3console中断向量PSW4,PC4硬件故障PSW5,PC5程序错误……PSWn,PCn访管中断向量00000008001600240030…0090时钟中断处理程序PC1:I/O中断处

理程序PC2:访管中断处理程序PCn:…系统空间9.3.2.3中断嵌套与系统栈•一般原则：–高优先级别中断可以嵌入低优先级中断•实现方法：–中断响应后立即屏蔽不高于当前中断优先级的中断源。9.3.2.3中断嵌套与系统栈进入中断后一

般需要进一步保存现场关中断（屏蔽所有中断）进一步保存现场（地址寄存器，通用寄存器等）开中断（或开放高优先级中断）…...中断处理…...恢复现场中断返回9.3.2.3中断嵌套与系统栈中断嵌套:……目态PSW1:PC1……管态PSW2:PC2……管态P

SWn:PCn………9.3.2.3中断嵌套与系统栈……PSWn-1PCn-1……PSW2PC2PSW1PC1栈顶指针:系统栈:9.3.2.4中断优先级与中断屏蔽•中断优先级：–硬件规定的中断响应次序，依据:•紧迫程度；•处理时间。•中断屏蔽：–

高优先级中断事件处理不受低优先级中断打扰；–程序调整中断响应次序。9.3.3中断处理程序强迫性中断：自愿性中断：转中断处理程序是否嵌套中断由系统栈恢复现场需要切换进程返回上层中断由系统栈恢复现场转CPU分派返回目态程序（dispatcher）保存现场信息取中

断字分析中断原因保存现场信息取访管号分析调用功能TFFT9.3.3.1IO中断处理•正常结束–继续传输；–唤醒相关进程。•传输错误–复执（eg.3次)；–报告系统操作员。9.3.3.2时钟中断处理•Housek

eeping–进程管理•重新计算进程调度参数(eg.动态优先数)–实现软时钟，启动定时程序•硬时钟5ms发生一次中断，软时钟50ms–考虑进程切换9.3.3.3控制台中断处理•一个控制按钮，一个中断向量，一个中断处理程序。9.3.3.4硬件故障处理•电

源故障处理–掉电：•内存，寄存器外存•停止设备•停止处理机–恢复：•启动处理机•启动设备•外存内存，寄存器UseUPSforcriticalapplications9.3.3.4硬件故障处理•内存故障处理–海明校验，奇偶校验错误•下雨检查

•划出系统•报告操作员9.3.3.5程序性中断的处理•只能由操作系统处理的中断–影响系统或其它进程•越界，非法指令，（处理：终止进程、调试）–需要系统管理或协助•页故障，缺段，（处理：动态调入）•可以由用户自己处理的中断–不影响系统和其它进程•除

0，溢出，（处理：用户处理，或OS处理）应用程序自己处理中断调试语句：on<中断条件><中断续元入口>例如：on<divide_zero>gotoLA;除0中断时转LA处理除0中断时转LB处理on<divide_zero>gotoLB除0中断续元除0中断续元LA:LB:相同中断发生在不

同位置可采用不同处理方法应用程序自行处理中断编译时：生成中断续元表：中断续元入口0中断续元入口1……中断续元入口n中断事件0:中断事件1:中断事件n:…...运行时：执行调试语句，填写中断续元表。中断时：根据中断原因查中断续元表，为0，用户未规定中断续元，由OS标准处理；非0，用户

已规定中断续元，由用户处理。初始时均为0•步骤：–（1）发生溢出中断–（2）保存旧PSW和PC–（3）取中断向量–（4）转到中断处理程序–（5）访问中断续元表（假定非0）–（6）系统栈中现场转移到用户栈–（7）中断续元入口送寄存器（OS中断处理完成）–（8）执行中断续元–（9）用户栈PSW和PC

送寄存器–（10）返回中断断点9.3.3.6自愿性中断的处理访管指令（SuperVisorCall)形式：准备参数SVCn取返回值系统调用（systemcall)形式：返回值=系统调用名称（实参1,…,实参n

)参数和返回值的存放位置是由OS规定的。9.3.3.6自愿性中断的处理系统调用驱动表：(tabledriven)服务程序入口addr1…………addrn访管号：0……...mEg.UNIX