【文档说明】高教类课件：操作系统原理与实训教程(第2版).ppt，共(340)页，5.414 MB，由小橙橙上传

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

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

操作系统课程任务和要求任务通过本课程的学习,掌握操作系统的基本概念、设计原理及实施技术,具有初步分析操作系统和设计、实现、开发实际操作系统的能。基本要求通过理论学习和上机操作,使学生能掌握操作系统的基本概念、

基本原理、及基本功能.了解UNIX操作系统、WINDOWSNT操作系统的基本轮廓,具有初步分析实际操作系统、设计、构造和开发现代操作系统的基本能力。操作系统课程的特点：•实践性强•涉及面广（并行程序，性能问题，结构问

题，程序方法论，软件工程，等等）•错综复杂如何学好操作系统？•理论抽象多看（课本和参考书）、多练（习题和上机）、多想（包括预习、听课和复习），当然还要端正态度。第1章引言OS的地位OS的作用：用户应用软件其他系统软件裸机操作系统1.1OS(OperatingSystem)

的概念计算机系统的层次结构：•人机接口•系统资源管理者•虚拟机器1.1OS的概念（续）OS的设计目标：方便性、有效性、可扩充性、开放性。OS主要功能：四大类系统资源的管理和与用户的接口。另有中断处理、时钟管理和出错处理等。在批处理系统中还有作业管理功能。OS

定义(P5)：OS是合理组织计算机的工作流程，有效控制和管理计算机系统的各类资源，并方便用户使用计算机的一组程序的集合。它是最基本、最重要的系统软件。从无到有雏形批处理分时实时PC网络分布式OS1945~1955真空管和插件板，无OS时代1955~1965晶体管

和批处理系统，OS诞生、成长时期1965~1970~1980IC芯片和多道程序，OS成熟1980~VLSIC，PC网络分布式OS以上各阶段用户的用机方式：全人工脱机I/O联机I/O1.2OS发展过程上个世纪60年代末至70年代初杨芙清院士主持我国第一台百万次集成电路计算机（1

50）操作系统，支持多道程序运行，在石油勘探领域成功应用。上个世纪70年代中后期杨芙清院士主持我国第一个全部用高级语言书写的DJS240机操作系统，DJS200/XT2层次管程结构模型，PCM设计方法，活跃管程结构模式。国内操作系统

的研制状况国内操作系统的研制状况（续）GX73多机实时操作系统（1978年）国防科技大学，1980年装在“远望”-I号航天测量船上，完成了向太平洋发射运载火箭、潜水艇水下发射的测控任务；完成了我国第一颗同步地球

卫星的测控、定轨、控制任务。“银河”-1YHOS巨型操作系统（1983年）国防科技大学，用于YH-1、YH-2超级计算机，用于我国的石油勘探、天气预报和核物理研究。COSIXv1.X/2.0国产UNIX类

操作系统（国家八五、九五重点科技攻关成果，以中软为首，联合国内18个单位共同完成）微内核结构，安全级别超过B1，中文界面。嵌入式操作系统Hopen（女娲计划）。Linux类操作系统。•可从多角度进

行多种分类：比如，按机器硬件结构、规模可分为：大、中、小型机OS，PCOS，网络OS和嵌入式OS等；而按系统处理任务的方式可分为：三种基本类型的OS（即批处理系统、分时系统和实时系统）和分布式OS。若按系

统能同时响应的用户及任务数则可分为以下三种类型：单用户单任务OS（如DOS）、单用户多任务OS（如1.3OS分类早期的批处理系统示意图脱机输入/输出过程：–(a)程序员将卡片拿到1401机处–(b)1401机将批处理作业读到磁带上–(c)操作员将输入磁带

送入7094机–(d)7094机进行计算–(e)操作员将输出磁带送到1401机–(f)1401机打印输出分时系统示意图•分时系统基于主从式多终端的计算机体系结构：一台主机连接着多个带有显示器、键盘及控制器的本

地或远程终端，多用户在自己的终端上以交互方式使用主机，共享系统资源主机(分时OS）终端终端终端……多道操作系统的基本特性:1.4OS的特征P13图1-3•并发性•共享性(两含义)•虚拟性•异步性一、命令界面1、脱机命令

界面(如JCL语言)2、联机命令界面(如键盘命令)二、程序界面（用户只能在其程序中使用的一组操作系统函数，如MSDOS的INT函数、UNIX的Systemcall函数、Windows的API函数等）三、图形用户界面(GUI)1.5OS的用户界面OS

的结构设计不同时期的软件开发方法使OS结构从整体式无结构系统模块化结构层次式结构C/S模式的微内核结构。同时系统本身具有不同的结构。一、整体式结构二、层次式结构三、虚拟机系统四、客户-服务器系统1.6OS的结构OS结构示意图(1)整体式

（单块）系统的简单结构模型OS结构示意图(2)StructureoftheTHE（1968）operatingsystemMS-DOSLAYEREDSTRUCTUREUser(L3)CommandProcessor(L2)DOSKernel(L1)BIOSHardwar

eOS结构示意图(3)StructureofVM/370（1979）withCMS（ConversationalMonitorSystem)OS结构示意图(4)Theclient-servermodelOS结构示意图(5)Theclient-servermodelinadistribu

tedsystemMICROKERNELRitcheandThompson1973,UNIX;1983,TuringAwardBillGates&PaulAllen1975MSCo.，1981DOS1.0,1990W

indows3.1,1995Windows95；1993WindowsNT,2000Windows2000,2003Windowsserver2003对OS贡献大的人：AndrewS.Tanenbaum1987,MI

NIXLinusTorvalds1991,LinuxSteveJobs，SteveWozniak1977AppleComputer,Inc.,AppleDOS;1984MacintoshOS;1991,1997MacOS

;2001MacOSx当前几个著名的开源OS：•MINIX•Linux•FreeBSD(UNIX)•Solaris10(SUN’sOpenSolarisProject,descendantofBSDandSyst

emV)•OS定义（P5）•处理机两种执行状态（核心态=管态，用户态=目态）•Kernel（OS运行于核心态的代码）•系统从用户态进入核心态执行的途径:中断(含系统调用和陷阱)•分时(TimeSharing)1959,MIT提出,19

61实现。时间片大小？•特权指令(启动I/O等影响系统安全的指令,只能OS执行)•并行与并发(P12)•OS与用户的接口小结：本章几个重要概念P19-21综合练习题一补充题1：当没有用户程序要运行时，CPU做什么？补充题2：下述指令中哪些应是特权指令？1）修改内存管理寄

存器2）写程序计数器3）读时钟的时间值4）置时钟的时间值5）改变进程的优先级6）置运行模式为核心态7）重启动8）关中断9）读程序状态字作业第2章处理机管理(重难点之一)2.1多道程序设计程序并发执行时的特征：间断性程序在并发执行时，由于共享资源，或

者需要相互合作，致使相互间产生了制约关系，呈“走走停停”的间断执行特征。失去封闭性程序并发执行时的系统环境（主要指各程序所共享的系统资源的状态）是由多个程序来改变的，因而失去了封闭性。不可再现性程序在并发执行时的结果与其执行速度等有关，从而

不可再现。I1I2I3I4C1C2C4C3P1P2P3P4程序并发执行的条件(Bernstein,1966)定理：如果两个程序P1和P2满足下述条件，它们便能并发执行，否则不能R(P1)∩W(P2)∪R(P2)

∩W(P1)∪W(P1)∩W(P2)={}即当两个程序的读集与写集的交集以及写集与写集的交集都为空集时，它们可以并发执行，否则不行。该定理也称Bernstein条件。操作系统中许多任务不满足Bernstein条件，它们不能并发执行吗？怎么办？这涉及后面重点讲的

进程同步问题。2.2进程的描述2.1进程的基本概念1.进程（P26）及进程实体（P27）的概念进程是对正在运行的程序的抽象，是OS最核心的概念。计算机上所有可运行的软件，包括OS，被组织成若干顺序进程，简称进程。进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行资

源分配和调度的一个独立单位。生活例子：一人按菜谱做菜。进程实体由程序段、相关数据段和进程控制块构成。进程的其他定义“进程”这一术语，在60年代初期，首先在美国MIT的MULTICS系统和IBM公司的CTS

S/360系统中引入。其中能反映进程实质的定义有：•（1）进程是程序的一次执行。•（2）进程是可以和其他计算并发执行的计算。•（3）进程是一个程序及其数据在处理机上顺序执行时发生的活动。•（4）进程是程序

在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。•（5）进程是进程实体的一次活动。程序任意并发执行具有一些新的特征（间断性、无封闭性、不可再现性），旧的程序的概念已不足以刻画这种并发执行的程序及其执行所产生的新特征。为使程序能并发执行，且为了能对并发执行的程序加以描

述和控制而引入进程。简言之，为了实现程序的并发执行。前趋图（P23）在此是一种可用于描述进程间执行的时序关系（前趋后继关系）的DAG。DAG在编译原理、数据结构和人工智能等课程/学科中都有用。2.进程的引入（P26）进程的特性：•动

态性：指进程是程序或进程实体的一次执行过程，生命周期短暂。•并发性：指多个进程实体同存于内存中，且能在一段时间内同时运行。•独立性：指进程是系统分配资源和调度运行的一个基本单位。•异步性：指进程的推进速度是各自独立、不可预知的。•结构特性：从结

构上看，进程由程序段、相关数据段和进程控制块三部分组成。此即进程实体。3.进程的特性及其与程序的区别（P26~P27）提示：可从二者的定义上、进程的特征上（结构特征单列）和二者对应数目关系上等几方面分析。另外，进程可真实地描述并发，而程序不能。注意：在OS中，作业、进程、程序

和线程是几个相似但又不同的概念！进程与程序的区别与联系从定义上看，进程是程序处理数据的过程，而程序是一组指令的有序集合；进程具有动态性、并发性、独立性和异步性等，而程序不具有这些特性；从进程结构特性上看，它包含程序（以及数据和PCB）；进程和程序并非

一一对应。执行态阻塞态就绪态调度I/O请求时间片完I/O完成为了更好地描述进程的动态存在，设计者常常给进程定义三种基本状态：就绪态(Ready)、执行态(Running)和阻塞(Blocked)状态。其转换方向和常见的转换原因如下图所示：4.进

程的三种基本状态及其转换图说明：1)在引入挂起功能的系统中，进程状态可至5个。2)在实际的OS中，进程的状态会更多。比如UNIXSV中有9种，Linux中有6种，Windows2000中有7种。另外，系统引入挂起功能的原因要了解（P29，为满足系统和用

户两方面的需求，如：换入换出、调整负荷、解救死锁、父进程请求等）。5.PCB（ProcessControlBlock）及其组织方式•PCB：系统中用于存放进程的描述和控制信息的数据结构。它是进程存在于系

统的唯一标志。•PCB作用(P29)：（1）标识进程的存在；（2）为系统提供可并发执行的独立单位；（3）为系统控制和管理进程提供所需的一切信息。•PCB中的主要内容(见P30)：进程的标识信息、处理机的状

态信息、进程调度信息、进程的控制信息等。。•PCB的组织方式：一般线性表、链接表(多队列)、索引表。空闲PCB队列头指针阻塞进程队列头指针就绪进程队列头指针执行进程指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9430879015….PCB链接队列示意图：进程控

制的主要任务是对进程生命周期进程控制，即要负责进程的创建、撤消以及实现进程的状态转换和进程通信等功能。这是系统的基本功能，由内核中相应的原语完成。要求了解各个进程控制原语的算法思想和引起这些控制原语执行的常见原因。原语(primitiveora

tomicaction)：是OS内核中由若干多机器指令构成的完成某种特定功能的一段程序，其执行具有不可分割性，即原子特征。亦即原语的执行必须是连续的，不能是并发或被中断的。单机系统中的实现方式之一：屏蔽中断。2.3进

程控制1.进程创建原语Creat()•引起创建进程的事件：•用户登录•作业调度•提供服务•应用请求•进程创建的主要步骤：•申请空白PCB•为新进程分配资源•初始化PCB的内容•将新进程插入就绪队列2.进程阻塞原语Block()•引起进程阻塞的事件：•请求系统服务•启动某种操作•新

数据尚未到达•无新工作可作•进程阻塞的过程：•发现阻塞事件，调用阻塞原语把自己阻塞，停止进程的执行，修改PCB的状态信息，将其插入到相应的阻塞队列。最后转调度程序，将处理机分配给另一个就绪进程。注意：进程的阻塞是进程自身

的一种主动行为2.4进程的互斥——你需要，我也需要•多道程序设计带来的问题：并发执行的多个进程可能产生互斥或同步的相互制约关系，不采取措施，可能导致结果的不可再现性。影响系统效率，而且还可以导致系统崩溃。为此，现代操作系统都在内核中设有进程的互斥同步机制，即同

步机构（硬件指令/信号量机制/管程机制等），使并发执行的诸进程之间能有效地共享资源和相互合作，并使程序的执行具有可再现性。一、互斥的定义•所谓进程互斥，指的是对某个系统资源，一个进程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用。即排他性地

用。•进程互斥是多道程序系统中进程间存在的一种源于资源共享的制约关系，也称间接制约关系，主要是由被共享资源的使用性质所决定的。•限定进程只能互斥地访问它的资源叫临界资源（指一次仅允许一个进程使用的资源）。•临界资源也是不可剥夺性资源。例：打印机、共

享变量或表格等。类似生活中的试衣室、电话间等。计算机系统中可剥夺性使用的资源主要有CPU、内存和磁盘等。类似生活中的点歌簿、电话本等。临界区：进程中访问临界资源的那段程序代码称为临界区或临界段。使用同一临界资源的不同进程中的临界

区称为同类临界区或相关临界区。临界区的使用原则，即“空则让进，忙则等待，等则有限，等则让权”。二、上锁和开锁原语•现代操作系统用来实现进程的互斥、同步的工具有多种，如上锁与开锁原语、信号灯机制、管程机制等。•上锁与开锁是一种最简单的进程互斥方法，它

使用一个锁变量W来表示某种临界资源的状态，W=0表示资源空闲可用•W=1表示资源正被使用1．上锁原语：LOCK（W）•L1：如果W=1那么转向L1;•否则W=1•返回•voidlock(锁变量w){te

st:if(w为1)gototestelsew=1;/*上锁*/•}/*lock(w)*/1.考察锁位的值；2.如果原来的值为0，将锁位置1；3.如果为1，则返回第一步再次考察2．开锁原语：UNLOCK（W）•W=0;•返回•voidunlock(锁变量w){•w=0;/*开锁*/•

}/*unlock(w)*/当进程使用完资源后，它必须将锁位置成“0”，称为开锁操作。三、用开关锁原语实现进程互斥•任何欲进入临界区的进程，必须先执行上锁原语。若上锁原语顺利通过，则进程可进入临界区；当完成对临界区

资源的访问后再执行开锁原语，以释放该临界资源。•即在相关进程的程序里由上锁和开锁原语紧夹着临界区，就能保证这些进程互斥地进入各自的临界区。例如，甲、乙两进程要访问同一类临界资源•甲进程：其他代码；LOCK（W）；甲进程的临界区；UNLOC

K（W）；其他代码；•乙进程：其他代码；LOCK（W）；乙进程的临界区；UNLOCK（W）；其他代码；用上锁用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理机效率不高，因为上锁原语中的条件测试操作可能引起CPU“忙等”。2.5信号量机制荷兰著名科学家，1972年计

算机图灵奖获得者，E.W.Dijkstra于1965年利用火车控制系统中信号灯的概念，提出了用作进程同步工具的信号量（semaphore）机制，它最初由一个表示资源可用数目或状态的整型量（信号量）和唯一能改变这个信号量值的P、V原子操作组成，是一种简单成效的进程互斥同步工具，

已广泛用于现代计算机系统中。信号量机制的基本原理是：两个或多个进程可以利用彼此间收发的简单的信号来实现“正确的”并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。经典的整型信号量＝》记录型信号量＝》信号量

集机制CPU忙等无忙等，若使用不当，可能造成死锁不易死锁，可能导致资源利用率低一、记录型信号量的概念记录型信号量是个复合类型的量，其一个分量是个整型分量S，另一个分量是个进程的等待队列指针Q。Pascal的记录相当于C的结构体。记录型信号量机制无进程的“忙等”现象，其整型分量相当于

最早的整型信号量，其值只能由P、V操作改变。记录型信号量的整型分量S的值的物理含义当S≥0时，表示某类可用资源的数目，或者说表示可以执行P操作而不会被阻塞的进程的数目；当S＜0时，其绝对值表示信号量S的阻塞队列L中

的进程数，即系统中因请求该类资源而被阻塞的进程的数目，亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。记录型信号量机制的另一构件P、V操作的定义如下：二、P、V操作原语P代表荷兰语的prober

en，意为“测试”；V代表荷兰语的verhogen，意为“增加”。国外文献现在流行使用wait操作和signal操作(或down操作和up操作)代替P操作和V操作。P(S)、V(S)原语操作的算法描述：P(S):（1）S.S减1；（2）若S.S

<0，则Block(S.Q)。V(S):（1）S.S加1；（2）若S.S0，则Wakeup(S.Q)。P（S）和V（S）操作的物理含义：P（S）操作表示“等信号”，即测试一个要等的信号是否到达；V（S）

操作表示“发信号”。这个信号在实现同步时就是“合作者的伙伴进程已完成前趋任务”，在实现互斥时就是“临界资源可用”。另外，在互斥问题中，每执行一次P（S）操作的含义，也可理解为进程请求一个单位的S类资源；每执行一次V（

S）操作的含义，也可理解为进程释放一个单位的S类资源。三、用P、V操作原语实现进程的互斥用P、V操作原语实现进程的互斥也一样简单，只需在相关进程的临界区的前后分别施以P操作和V操作即可，即在相关进程的程序里由P操作和V操作原语紧

夹着临界区，就能保证这些进程互斥地进入各自的临界区。这里所用信号量的初值一般为1，表示临界资源未被占用，且其可用数目为1。用P、V操作原语实现进程互斥的效率更高一些，因为P操作中引入了阻塞机制，所以消除了CPU忙等现象。P(S)V(S)P(S)V(S)P(S)V(S)P1P2P3互斥区一个

简化的异地售票程序，假设几乎同时两地有两个乘客要购买同一班次的车票各一张•两个终端售票程序都要访问存放该次车票的数据单元Pk•假设它们都要对Pk做如下的访问操作•“若Pk≥1，则将Pk的值减1，卖出一张票，返回•

否则打印‘无票’信息，返回”•如果不加任何限制让这两个程序并发执行的话，结果可能会导致错误，甚至两地各卖出一张重票的现象例2.1试用P、V操作实现火车联网订票系统中北京、天津两地的两个终端售票进程发售同一班次车票的过程。主要步骤是：（1）分析清楚题目涉及的进程间的制

约关系。（2）设置信号量（包括信号量的个数和初值，对于同步问题还要写出信号量的物理含义）。（3）给出进程相应程序的算法描述或流程控制，并把P、V操作加到程序的适当处。北京售票终端进程：•①根据顾客订票要求找到公共数据单元PK；•②P（S）；•③把PK的值读到工作寄存器R1中；•④根据顾客订

票数修改R1；•⑤将R1的值回写到PK中；•⑥V（S）；•⑦售出顾客所订的票，返回；天津售票终端进程：•①根据顾客订票要求找到公共数据单元PK；•②P（S）；•③把PK的值读到工作寄存器R2中；•④根据顾客订票数修改R2；•⑤将R1的值回写到PK中；•⑥V（S）；•⑦售出顾客所订的票，返回；关于此

算法的2个问题：•①如何解决“票已售完”？•②用类Pascal语言怎样描述？——留作课后思考练习！2.6进程的同步——你等我，我也等你•相关的并发进程间可能有互斥制约关系，也可能有同步制约关系•所谓进程同步，指的是合作完成同

一个任务的两个或多个进程，在执行速度或某些时序点上必须相互协调，以同步推进的合作关系。这是一种源于相互合作的直接制约关系。即一个进程的执行依赖于另一个进程的消息，当它到达某一确定点而没有得到合作者发来的“已完成前驱操作”的消息时必须等待。–生活中对弈双方、医生与化验员之间都有同步关系–系统

中父子进程之间通常属于合作（同步）关系–注意：互斥也可以看成是一种特殊的同步关系。用记录型信号量机制实现进程同步•一般的解题步骤（同进程互斥的实现）：–(1)分析题设中各进程间的制约关系；–(2)按(1)的结果设置相应信号量（包括信号量的名字、个数和初值及其物理含义（

仅限同步问题））注意：对于互斥问题，一般只设1个信号量，且置初值1；而对于同步问题，合作进程间需要收发几条消息相应就设置几个信号量，且同步信号量的初值一般为0，表示消息尚未产生。–(3)把P、V操作加到

进程代码的适当处，用类Pascal或C语言给出算法描述；注意P(S)、V(S)操作出现的形式特点一般地，P(S)、V(S)操作总是同时/配对出现的，但具体描述进程互斥时，P(S)、V(S)操作出现在同一进程中(且分别

紧挨在临界区前后)；而具体描述进程同步时，P(S)、V(S)操作常出现在不同的进程中，且一个进程发送消息时用V(S)，而它的合作者进程接收此消息时用P(S)。例2.2用信号量机制解决生产者-消费者问题（P43，经典IPC问题之一，也叫有界缓冲区问题）•问题描述：一组消费者进程一

组生产者进程如何编程？具有n个单元的环型缓冲池•生产者-消费者问题是对相互合作的进程之间同步问题的一种抽象，例如，在输入和计算进程间，计算进程是消费者；而在计算和打印进程间，计算进程是生产者。问题分析：•①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费

者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。•②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。

问题解答：①所用信号量设置如下：Ⅰ）同步信号量empty，初值为n，表示消费者已把缓冲池中全部产品取走，有n个空缓冲区可用。Ⅱ）同步信号量full，初值为0，表示生产者尚未把产品放入缓冲池，有0个满缓冲区可用。Ⅲ）互斥信号量mutex，初值为1，以保证同时

只有一个进程能够进入临界区，访问缓冲池。②用信号量机制解决生产者—消费者问题的算法描述如下(类Pascal语言描述见后)：生产者i生产出一产品；P（empty）；P（mutex）；将该产品放入缓冲区；V（m

utex）；V（full）；消费者jP（full）；P（mutex）；从缓冲区取出一产品；V（mutex）；V（empty）；消费该产品；Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofi

tem;in,out:integer:=0,0;beginparbeginproducer:beginrepeatproduceanitemnextp;P(empty);P(mutex);buffer(in):=

nextp;in:=(in+1)modn;V(mutex);V(full);untilfalse;endconsumer:beginrepeatP(full);P(mutex);nextc:=buffer(out);out:=(out+1)modn;V(m

utex);V(empty);consumetheiteminnextc;untilfalse;endparendend问题思考：•如果某进程中的P操作顺序颠倒了，会怎么样？•如果某程序员漏写了一个V操作，会怎么样？例2.3用信号量机

制解决读者-写者问题（P44,经典IPC问题之一,Courtois,1971）•问题描述：一组读者与一组写者循环访问共享的同一个数据对象。规定：多个读者可以同时读这个数据对象，但决不允许多个写者同时对它进行写操作，也不允许读者、写者同时访问它。如

何对读者、写者编程？哲学家进餐问题对多进程互斥访问有限资源这一类问题的建模很有用。另一著名问题就是读者-写者问题，它为数据库访问建立了一个模型，是对进程间一类互斥问题的抽象。问题分析•①读者—写者之间的互斥关系：由于共享的数据对象是临界资源，故可设

一个公用的初值为1的互斥信号量RW_mutex，以保证同时只有1个读者或者写者进程进入临界区访问该数据对象。但是，这样做不仅实现了写者与写者的互斥、写者与读者的互斥，而且也实现了读者与读者的互斥。其实

，只有第1个到来的读者和最后1个离开的读者需要与写者进行互斥通信。为此，引入一个读者计数器变量RC。•②读者—读者之间新增的互斥关系：读者需互斥地访问RC，故需再设一个初值为1的互斥信号量R_mutex。问题解答

：•①所用信号量和其他变量设置如下：Ⅰ）互斥信号量RW_mutex，初值为1，用于实现写者与其他写者或读者互斥地访问共享的数据对象。Ⅱ）互斥信号量R_mutex，初值为1，用于实现诸读者互斥地访问读者计数器

变量RC。Ⅲ）整型变量RC，初值为0，用于对读者进行记数。②算法描述(类Pascal语言描述见下)：读者：P（R_mutex）；若RC=0则P（RW_mutex）；RC加1；V（R_mutex）；读数据对象；P（R_mutex）；RC减1；若RC=0则V（RW_m

utex）；V（R_mutex）；写者：P（RW_mutex）；对数据对象进程写操作；V（RW_mutex）；用信号量机制实现的读写问题的类Pascal描述：VarRW_mutex,R_mutex:semaphore:

=1,1;RC:integer:=0;beginparbeginReaderi:beginrepeatP(R_mutex);ifRC=0thenP(RW_mutex);RC:=RC+1;V(R_mutex);performreadoperation;P(R_mutex);RC:=RC-1;if

RC=0thenV(RW_mutex);V(R_mutex);untilfalse;endparendendWriterj:beginrepeatP(RW_mutex);performwriteoperation;V(RW_mutex);untilfa

lse;end例2.4试用用信号量机制描述两人下象棋的过程•两人下象棋的过程可以概括为：一开始只能是“红先黑后”，以后两人要循环轮流走子，直至某一方获胜或双方和棋为止。•这是个只有一个生产者和一个消费者的生产者——消费者问题，是个典型的“你

等我，我也等你”的问题。红方是总的前趋任务——生产者进程，黑方是总的后继任务——消费者进程，但由于下棋过程必须轮流走子，所以红黑双方的生产者消费者身份会轮流改变。棋盘则是生产者与消费者共享的缓冲。解答：①所用信号量设置如下：•Ⅰ）同步信号量hei，初值为1，表示黑方已走子,开始时可使红方先行

不受阻。•Ⅱ）同步信号量hong，初值为0，表示红方尚未走子，开始时可使黑方先行受阻。②红黑双方下象棋过程如下：红方：•P（hei）；•若被黑方将死，则投子认负，结束；•若同意与黑方作和，则结束；•否则，根据棋局思考后走一子；•V（h

ong）；黑方：P（hong）；若被红方将死，则投子认负，结束；若同意与红方作和，则结束；否则，根据棋局思考后走一子；V（hei）；此例的类Pascal语言描述留作课后练习还有其他解法吗？例2.5用信号量机制描述进程的前趋后继关系(补充例

1)说明：这是一种类型的同步问题，解法也较固定：•初始结点对应的操作可直接执行，然后用V操作给其各个后继结点分别发送一条“已完成前趋操作”的消息；•终止结点对应的操作则必须在该结点分别用P操作收到其各个前趋结点“已完成前趋操作”的消息后才能执行；•各个中间结点

对应的操作，执行前需用P操作接受其前趋结点“已完成前趋操作”的消息，执行后还需用V操作给其各个后继结点分别发送一条“已完成前趋操作”的消息。上述前趋图中各结点对应的操作的并发执行情况描述如下：Vars12,s13,s24,s25,s36,s46,s56:sema

phore:=0,0,0,0,0,0,0;beginparbeginprocess1:beginS1;V(s12);V(s13)end;process2:beginP(s12);S2;V(s24);V(s25)end;process3:beginP(s13);S3;V(s3

6)end;process4:beginP(s24);S4;V(s46)end;process5:beginP(s25);S5;V(s56)end;process6:beginP(s36);P(s46);P(s56);S6end;parendends1s2

s3s4s5s6例2.6用信号量机制解决睡眠的理发师问题（补充例2，经典IPC问题之一）•问题描述：理发店里有1位理发师、1把理发椅和n把顾客椅。若无顾客，理发师便在理发椅上睡觉；当1顾客到来时，他必须先叫醒理发师；若理发师正在理发时又有顾客到来，则如果有空椅子，他们就坐下来等，否则就离开。如

何对理发师和顾客编程来描述他们的行为，要求不能带竞争条件？这主要是个同步问题，理发师是循环进程，顾客不是。问题分析：•①顾客—理发师之间的同步关系表现为：若无顾客，理发师便在理发椅上睡眠，等待。顾客到来时，先看等候的顾客数是否少于顾客椅子数，不是则离开

，否则就留下来，声称要理发，并且等理发师醒来或闲下来，再理发。•②顾客—理发师之间还有互斥关系：由于等候的顾客数变量是临界资源，所以顾客进屋后对该变量进行的加1操作以及理发师起身准备给顾客理发时对该变量进行的减1操作必须互斥。As

olutiontothesleepingbarberproblembyTanenbaumsemaphorecustomers,barbers,mutex=0,0,1;intwaiting=0;/*i.e.customersarewaiting*/voidbarber(v

oid){while(TRUE){P(customers);P(mutex);waiting=waiting-1;V(barbers);V(mutex);cuthair();}}voidcustomer(void){P(mutex);if(waiting<CHAIRS){waiting=w

aiting+1;V(customers);V(mutex);P(barbers);gethaircut();}else{V(mutex);}}该解法中，理发师早晨工作时先执行过程barber，阻塞在信号量customers上，于是在理

发椅中睡觉，直至有顾客到来。理发师问题解法（二）——byJ.A.Harris&何炎详semaphorecutHair,waiting,mutex=0,0,1;intcount=0;/*i.e.customersthatar

einthebarber*/voidbarber(){while(TRUE){P(cutHair);Givehaircut();}}voidcustomer(){P(mutex);if(count==n+1){V(mutex);exit();}count=count+1;if(count>1)

{//takeachairV(mutex);P(waiting);}elseV(mutex);V(cutHair);ReceiveHaircut();P(mutex);count=count-1;if(count>0)V(waiting);V(mutex

);}}该解法中，理发师与顾客，顾客与顾客之间都有同步关系，而只有顾客访问顾客计数器变量时需互斥。理发师问题解法（三）——by谢青松semaphorecustomers,barber_chair,chairs=0,0,n+1;voidbarber

(){while(TRUE){P(customers);V(barber_chair);Givehaircut();}}voidcustomer(){P(chairs);//comein//takeachairV(customers);P(barber_chair)

;ReceiveHaircut();V(chairs);//goout;}该解法中，把顾客进入理发店、理发、出理发店的过程看做顾客进程的临界区，相应互斥信号量chairs初值为n+1,表示最多允许n+1个顾客同时进店。顾客与理发师之间有同步关系。以上解法有什么差

异？该问题解法（四）更复杂，见汤子瀛、梁红兵《OS学习指导与题解》P44例2.7(P46选讲)某小型超级市场，可容纳50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过

）。试用信号量和P、V操作写出购物者的同步算法。分析：这是个典型的进程互斥问题，超市内部及其出入口是临界资源，为此，若出入口为同一个，则需要设两个互斥信号量，否则需要设3个。解答:①所用信号量设置如下：•Ⅰ）互斥信号量S，初值为50，用以保证最多可以有50个购物者同时进入超市。•Ⅱ）互斥信号量mu

tex，初值为1，用以保证同时只能有一个购物者进程进入出入口拿起篮子或者结帐后放下篮子。②用信号量机制给出的每个购物者购物过程的算法描述如下：购物者i进程（解法一）：•P（S）；P（S）；•P（mutex）；P（mutex1）；•从入口处进超市，并取一只篮子；同左；•V（mutex）；V（mu

tex1）；•进超市内选购商品；同左；•P（mutex）；P（mutex2）；•到出口结帐，并归还篮子；同左；•V（mutex）；V（mutex2）；•从出口离开超市；同左；•V（S）；V（S）；购物者i进程（解法二）：例2.8(P48选讲)桌上有个只能盛得下一个水果的空盘

子。爸爸不断向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量和P、V操作实现爸爸、儿子和女儿这三个循环进程之间的同步。分析：本题属于生产者/

消费者问题的变形，相当于一个能生产两种产品的生产者（爸爸）向两个消费者（儿子和女儿）提供产品的同步问题。因此，可参考生产者与消费者问题的解法。注意，这里未把盘子看作临界资源。而南京大学2000年的一道考研题则是此例的变形，其答案把盘子看作了临界资源，变形部分是：盘子能盛2

水果，爸爸放苹果，妈妈放桔子，要求实现4个进程的同步互斥关系。解答：①所用信号量设置如下：Ⅰ）同步信号量empty，初值为1，表示盘子是空的，即儿子或女儿已把盘中的水果取走。Ⅱ）同步信号量orange，初

值为0，表示爸爸尚未把桔子放入盘中。Ⅲ）同步信号量apple，初值为0，表示爸爸尚未把苹果放入盘中。②用信号量描述的3个进程的同步过程：爸爸进程：儿子进程：女儿进程：P（empty）；P（orange）；P（apple）；

将水果放入盘中；从盘中取出桔子；从盘中取出苹果；若放入的是桔子，V（empty）；V（empty）；则V（orange）；吃桔子；吃苹果；否则，V（apple）；此例的类Pascal语言描述留作课后练习设A、B两点之间是一段东西向的单行车道，现在要设计一个AB路段自动管理系统，管理规则如下：当A

B间有车辆在行驶时，同方向的车可以同时驶入AB段，但另一方向的车必须在AB段外等待；当AB段之间无车辆行驶时，到达AB段的任一方向的车都可进入AB段，但不能从两个方向同时驶入，即只能有一个方向的车驶入；当某方向在AB段行驶的车辆驶出了AB段且暂无车辆进入AB段时

，应让另一方向等待的车辆进入AB段行驶。试用信号量和P、V操作管理AB路段车辆的行驶。BA例2.9(P48选讲)分析：本题属于读者写者问题的变形，相当于两组读者（即两个方向的车辆）使用同一个共享文件（即AB路段）的互斥问题。

因此，可参考读者写者问题的解法。一个方向的车辆中只有第1辆驶入AB路段的和最后1辆驶出AB路段的需要与另一方向的车竞争和释放对AB路段的互斥使用权，为此需引入两个计数器变量，分别用来对驶入AB路段的两个方向的车辆进行计数，以确定哪辆车是第1辆驶入的，

哪辆是该方向最后1辆驶出的。故共需3个互斥信号量。解答：①所用信号量和其他变量设置如下：•Ⅰ）整型变量Car_A，初值为0，用于对从A点（东）驶入AB段的车辆进行记数。•Ⅱ）整型变量Car_B，初值为0，用于对从B点（西）驶入AB段的车辆进行记数。•Ⅲ）互斥信号量mutex，初值为1，用于实

现不同方向的第一辆车互斥驶入AB路段。•Ⅳ）互斥信号量ma，初值为1，用于实现东西向的车互斥地访问计数器变量Car_A。•Ⅴ）互斥信号量mb，初值为1，用于实现西东向的车互斥地访问计数器变量Car_B。P（mb）；Car_B加1；若Car_B=1则P（mutex）；V（mb）；车辆从B点通

过AB路段到达A点；P（mb）；Car_B减1；Car_B=0则V（mutex）；V（mb）；P（ma）；Car_A加1；若Car_A=1则P（mutex）；V（ma）；车辆从A点通过AB路段到达B点；P（ma）；Car_A减1；若Car_A=0则V（mutex）；V（ma）；东西向(即A

B向)行驶的车辆i西东向(即BA向)行驶的车辆j此例的类Pascal语言描述留作课后练习2.7进程通信•进程之间的信息交换称为进程通信。包括高、低级两种通信方式，本节介绍后者。•合作进程间所交换的信息量，少则是一个状态或数据，多则

成千上万字节的。两种进程通信方式/机制低级通信：只适于在进程间交换少量信息的通信方式/机制。该通信方式（如进程的同步和互斥工具）一般只传送一个和几个字节的信息，可方便有效地用于控制进程的执行速度，但它要作

为可传输大量信息的通信工具则不够理想（效率低通信对用户不透明）。高级通信：用户可以直接利用操作系统所提供的一组通信命令（如send和receive），高效地传送大量数据的一种通信方式。它具有传输效率高，用户使用方便等优点，具体又可分为3大类：高级通信方式分类•共享存

储器系统。指共享内存区通信方式。•消息传递系统。包括基于消息缓冲的本地直接通信方式——消息缓冲通信和可用于异地通信的间接通信方式——信箱通信两种通信方式。•管道通信方式。这是UNIX首创的基于共享文件的通信方式。大家记得DOS或UNIX中的管道线命令吗？消息缓冲区和

信箱typebox=recordsize:integer:=N;s1,s2:semaphore;mutex:semaphore;letter:array[1..N]ofmessage;in,out:integer;endtypemessage

-buffer=recordsender;size;text;next;EndPCB中相关数据项：mq;mutex;sm;消息缓冲队列通信机制示意图：进程APCB(B)进程B……Send(B,a)Sender:ASize:6Text:He

llo!Receive(b)Sender:ASize:6Text:Hello!Sender:ASize:6Text:Hello!Next:2Sender:?Size:?Text:xxxxNext:0……首指针：mq互斥：mutex队列资源：sm……A的发送区aB的接收区bBuffer1Buff

ern消息缓冲通信机制中的发送与接收原语Proceduresend(receiver,a)Begingetbuf(a.size，i);i.senter:=a.senter;i.size:=a.size;i.text:=a.text;i

.next:=0;getid(PCBset，receiver，j);P(j.mutex);insert(j.mq，i);V(j.mutex);V(j.sm);endProcedurereceive(b)Beginj:=internalname;P(j.sm);P

(j.mutex);remove(j.mq，i);V(j.mutex);b.sender:=i.sender;b.size:=i.size;b.text:=i.text;putbuf(i);end信箱通信机制中的发送与接收原语Proceduresend(varB:b

ox,M:message)beginP(B.s1);P(B.mutex);B.letter[B.in]:=M;B.in:=(B.in+1)modN;{B.size}V(B.mutex);V(B.s2);endProcedurereceive(varB:

box,N:message)beginP(B.s2);P(B.mutex);N:=B.letter[B.out];B.out:=(B.out+1)modN;{B.size}V(B.mutex);V(B.s1);end2.8死锁问题•死锁的概念•产

生死锁的原因•产生死锁的必要条件•解决死锁问题的基本方法1死锁的定义——“你不让，我也不让”•死锁概念的提出–1965年，Dijkstra研究银行家算法时提出，以后又由Havender、Lyach等人研究并发展。•死锁（Deadlock，

P55）：–是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。称此时系统处于死锁状态或系统产生了死锁，称这些永远在互相等待的进程为死锁进程。–我们在生产者消费者问题解法中若颠倒消费

者中P操作顺序会导致死锁；“堵车”可看作生活中的死锁例子；下面的经典IPC问题——哲学家进餐问题的一个错误解法也会导致死锁。例2.7(3.0)用信号量机制解决哲学家进餐问题（P55，经典IPC问题之一，Dijkstra,1965）•问题描述：5位哲学家围在餐桌旁，要么思考，要么饿了时拿起

左右两把叉子吃通心粉(足够用的)。要求为每位哲学家写一段程序来描述其行为，但不能出现饿死现象（死锁或饥饿）。问题分析：相邻哲学家之间因竞争一把叉子而存在互斥关系。故需5个互斥信号量。一个关于第i号哲学家进餐过程的不正确的算法：哲学家i进程（i＝0，1，2，3，4）思考；P(

S[i]);拿起左边的叉子；P(S[(i＋1)mod5])；拿起右边的叉子；吃通心粉；放下左边的叉子；V(S[i]);放下右边的叉子；V(S[(i＋1)mod5])；对应类Pascal语言描述为（P48）:varchopsti

ck:array[0,…,4]ofsemaphore:=1,1,1,1,1;Philosopheri(i=0,1,2,3,4):repeatthinking;P(chopstick[i]);P(chopstick[(i+1)mod5);……eating;……V(chopstick[i]);V

(chopstick[(i+1)mod5);……untilfalse;遗留问题：——挑战同步原语的设计者•五位哲学家可能同时拿起左边的叉子，则他们都拿不到右边的叉子，于是发生死锁，他们将饿死。•解决的办法如下（第1种解法留作课后练习）：

1.至多只允许四位哲学家同时去拿左边的叉子；2.仅当哲学家左右两边的叉子均可用时才允许他拿起叉子；(这更适于用AND型信号量集求解)3.规定奇数号哲学家先拿起他左边的叉子，而偶数号哲学家先拿起他右边的叉子。•（1）竞争临界资源（即系统资源不足）当系统中供多个进程共享的临界资源（如打印

机、公用队列等）的数目不能满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。这个原因在多道程序系统中是无法解除的。•（2）进程推进顺序不当进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁的产生。这个原因在多道程序系统中是可以解除的。2产生死锁的原因（P57）思考题：（北大95研）

•一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？•答：不可能。因为死锁产生的

原因有两点：系统资源不足或进程推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。3产生死锁的必要条件——Coffman,1971(P57)•互斥条件(mutualexclusion)–指进程排他性地

使用所获资源，即一个资源一次只能被一个进程使用。•占有并请求条件(Holdandwait)–指进程保留已经得到的资源，还要求其它的资源。•不可剥夺条件(Nopreemption)–指进程已获得的资源，在未使用完之前，不能被其它进程强行抢占，只能在使用完时由自己

释放。•循环等待条件(Circularwait)–指发生死锁时，资源分配图(resourceallocationgraph)中存在有向封闭环路。如下图所示。S1P1S2P3S3P2资源结点进程结点分配边请求边某时刻系统的

资源分配图死锁必要条件的逆否命题预防死锁的方法。即只要死锁发生的四个必要条件之一不成立，则死锁一定不会发生。产生死锁的四个必要条件中，“互斥条件”由资源的固有特性所决定的，不仅不能改变，相反还应加以保证。实际上，“不剥夺条件”也很难破坏，故具体的预防死锁办法主要是通过破坏“占有并请求条

件”和“循环等待条件”来实现的。死锁的必要条件的理论意义4处理死锁的基本方法①预防死锁②避免死锁（银行家算法）③检测与解除死锁④置之不理（鸵鸟算法）①预防死锁•预防死锁：通过在资源分配中设置某些限定条件，破坏产生死锁的四个必要条件之一来实现。•但“互斥条件”和“不可剥夺

条件”往往由资源的性质决定，很难破坏。所以，具体的预防死锁的方法主要有两种，分别是通过破坏“占有并保持”条件以及“循环等待”条件实现的。⑴静态资源分配法（摒弃“请求和保持条件”）系统规定每一个进程在开始运行前，都必须一次性地申请其在整个运行过程所需的全部资源。此

时，若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。这样，进程在运行过程中就不会再提出资源请求，从而破坏了请求和保持条件。静态资源分配法的优缺点：优点：简单、安全、易实现。(Simpleisbeautiful)（DBMS

中进程更新记录前用的两阶段上锁法似此）缺点：（1）资源被严重浪费（因为一个进程一次获得其所需的全部资源并且独占，其中有可能有些资源很少使用，严重恶化了资源利用率）。（2）进程延迟运行。（当且仅当进程获得其所需的全部资源后，才能开始运行，但有可能有些资源长期被其他进程占用，致使需要该资源的进程

迟迟不能运行）⑵有序资源使用法（摒弃“环路等待条件”）系统中的所有资源按类都被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。即对同一个进程而言，它一旦申请了一个编号为i的资源，就不允许再申请编号比i小的资源了，因此，破坏了环路等待条件。优点：安全且资源利用率比静态资源分配法有所提高，

因为它实际是一种半动态的资源分配法。缺点：实现较困难，不实用。因为很难给出合适的资源编号，不便于系统增添新设备，不便于用户编程，且仍有一定的资源浪费现象。②死锁的避免•死锁的避免是这样一种对付死锁的办法：系统在运行过程中采取动态的资源分配策略，保证系统不进入可能导致系统陷入死锁状态的所

谓不安全状态，以避免死锁发生。•常用的避免死锁的算法是“银行家算法”，系统采用此法给进程分配资源时，需先判断“如果分配，系统状态是否安全”，这很像银行家放贷前的思考过程。(1)安全状态与安全序列•1)安全状态若在某一时刻，系统能按某种进程顺序，如<P1

,P2,…,Pn>，来为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列<P1,P2,…,Pn>为安全序列。•2)不安全状态若在某时刻，系统无

法找到一个安全序列，则称系统处于不安全状态。•安全序列的实质是：序列中的每一个进程Pi（i=1,2,…,n）到以后运行完成尚需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。安全状态的例子：例2.8假定系统中三个进程P1、P2和P3

共享12台磁带机。P1总共要求10台，P2要4台，P3要9台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配(如下图所示)。问T0时刻安全吗？解：经分析可知，T0时刻系统是安全的，因为这时存在一个安全序列<P2，P1，P3>。注意：

若把题中的12改为11，则T0时刻系统是不安全的，因为这时系统中虽有2台可用设备，但不存在安全序列。当然，若不按照安全序列分配资源，安全状态可能变为不安全状态，如本题中若下一时刻P3获得1台磁带机的情况。进程最大需求

已分配可用P11053P2P34229注意：（1）系统在某一时刻的安全序列可能不唯一，但这不影响对系统安全性的判断。（2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定

可以避免死锁，而系统处于不安全状态则仅仅有可能进入死锁状态。安全状态不安全状态死锁状态(2)银行家算法•银行家算法是最有代表性的避免死锁算法，是Dijkstra(1965)提出的。其模型基于一个小城镇的银行家的放贷行为。该银行家准备向N个客户贷款，他拥有的资金足以满足任一客户的最大资金

需求，但不能同时满足所有客户的最大需求。他要求每个客贷款前必须说明自己所要的最大资金量，并且每次提出部分或全部（但不能同时提出全部）资金量申请。他只给有信誉和能力并承诺到期还本付息的客户贷款。•该算法已扩充为多

资源的银行家算法。•在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是动态地对每个客户进程每次的资源请求进行检查，看一下如果满足它是否会引起不安全状态。假如是，则不满足该请求；否则就满足它。1)可用资源向量Available[1×m]记录系统中各类资源的当前

可用数目。2)最大需求矩阵Max[n×m]记录每个进程对各类资源的最大需求量。3)分配矩阵Allocation[n×m]记录系统给每个进程分配的各类资源数目。4)需求矩阵Need[n×m]记录每个进程尚需要的各类资源数目。显然，Need=Max－Allocation。5)请求向

量Request[1×m]记录某个进程当前对各类资源的申请量，它是银行家算法的入口参数。银行家算法所用的主要数据结构当Pi发出资源请求Requesti后，系统按下述步骤进行检查：step1.如果Reque

sti>Needi,则出错。step2.如果Requesti>Available,则Pi阻塞；step3.系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablei=Availablei-Re

questi;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti;step4.系统执行安全性检测子算法，检查如果实施此次资源分配后，系统是否会处于安全状态。若安全，则完成此次试分配，成功返回

；否则，将撤消此次试分配，恢复step3中改过的数据，让进程Pi等待。银行家算法描述(P60)安全性检测子算法描述(P60)——此法与死锁检测算法很相似，可对照理解(1)初始化：work=available；

/*work是available的影子变量*/finish=false；/*finish是进程可完成标志向量*/(2)若按进程编号顺序找到了一个可加入安全序列的进程，即：满足条件finishi=false且needi≤work的进程Pi，则①假设该进程不久将完成任务归还资

源，于是置work=work+allocationi；finishi=true；②重复执行这一步，直至找不到一个这样的进程为止；(3)若所有进程的可完成标志finish为真，则返回逻辑真值（表示系统将处于安全状态）；否则，返回逻辑假值（表示不安全）。从理论上讲，银行家算法能有效地避免死锁，而

且还不需要死锁预防法中加上的种种限制，如重新运行进程或有序申请资源。但实际上，它缺乏实用价值。因为银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并且假设系统拥有的资源总量和支持的进程个数是固定的

，而且进程之间是“无关”的。但很少有进程在运行前就知道其所需资源的最大量，而且进程数也不是固定的，而是不断变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。另外，

不少进程间有同步要求。总之，死锁预防法过于严格，而死锁避免法更不实用。(3)银行家算法性能评价(4)银行家算法之例•例2.9假定系统中有五个进程{P1、P2、P3、P4、P5}和三类资源{A，B，C}，资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图

所示:进程资源情况431002433P4011211222P3600302902P2122200322P1332743010753P0ABCABCABCABCAvailableNeedAllocation

Max1.T0时刻是否安全?2.Request1(1,0,2)能否响应?3.Request4(3,3,0)能否响应?4.Request0(0,2,0)能否响应?进程资源情况431002433P4011211222P3600302902P212220

0322P1332743010753P0ABCABCABCABCAvailableNeedAllocationMax资源情况进程ABCABCABCABCFinishWork'AllocationNeedWorkP1332122200532trueP3532011211743trueP474343

1002745trueP0745743010755trueP27556003021057true解：1.由安检子算法知T0时刻存在安全序列：{P1,P3,P4,P0,P2}，故系统是安全的。P1发出资源请求r

equest1（1,0,2），系统按银行家算法进行检查：①request1（1,0,2）≤need1（1,2,2）；②request1（1,0,2）≤available（3,3,2）；③系统先假定可为P1分

配资源，并修改available、allocation1和need1向量，结果资源试分配情况如下表所示：2.进程资源情况431002433P4011211222P3600302902P2020302322

P1230743010753P0ABCABCABCABCAvailableNeedAllocationMax④再利用安全性检测子算法检查此时系统是否安全，如下表所示：资源情况进程ABCABCABCABCFinishWork'AllocationNeedWorkP12300

20302532trueP3532011211743trueP4743431002745trueP0745743010755trueP27556003021057true可知此时存在安全序列：{P1,P3,P4,P0,P2}，故系

统是安全的，可立即将P1所申请的资源分配给它。当然{P1,P3,P4,P2,P0}也是一个安全序列。3.P4发出资源请求request4（3,3,0），系统按银行家算法进行检查：①request4（3,3,0）≤need4（4,3,1）；②request4（3,3,0）≤ava

ilable（2,3,0）；故P4等待。P0发出资源请求request0（0,2,0），系统按银行家算法进行检查：①request0（0,2,0）≤need0（7,4,3）；②request0（0,2,0）≤available（2,3,0）；③系统先假定可为P0分配资源，并修改

available、allocation0和need0向量，结果资源试分配情况如下表所示：4.进程资源情况431002433P4011211222P3600302902P2020302322P1210723030753P0ABCABCABCABC

AvailableNeedAllocationMax④系统进行安全性检测，找不到一个安全序列，故系统将进入不安全状态。由此决定不给P0分配资源。若request0=(0,1,0)呢？银行家算法之例二（P

60）•假定系统中有四个进程{P1、P2、P3、P4}和三种类型的资源{R1，R2，R3}，资源的数量分别为9、3、6，在T0时刻的资源分配情况如图:资源情况进程MaxR1R2R3AllocationR1R2R3NeedR1R2R3Avai

lableR1R2R3P1322100222112P2613511102P3314211103P4422002420㈠T0时刻是否安全？资源情况进程MaxR1R2R3AllocationR1R2R3NeedR1R2R3Ava

ilableR1R2R3P1322100222112P2613511102P3314211103P4422002420资源情况进程WorkR1R2R3NeedR1R2R3AllocaR1R2R3Work’R1R2R3P21

12102511623P1623222100723P3723103211934P4934420002936FinishTrueTrueTrueTrue㈡P2发出请求向量request2（1,0,1），系统按银行家算法进行检查：①request2（1,0,1）≤need

2（1,0,2）；②request2（1,0,1）≤available（1,1,2）；③系统先假定可为P2分配资源，并修改available、allocation2和need2向量，如下表所示：资源情况进程MaxR1R2R3AllocationR1R2

R3NeedR1R2R3AvailableR1R2R3P1322100222011P2613612001P3314211103P4422002420为P2试分配资源后的有关资源数据④再利用安全性检测子算法检查系统的安全性。

如下表所示。资源进程WorkR1R2R3NeedR1R2R3AllocaR1R2R3Work’R1R2R3P2011001612623P1623222100723P3723103211934P4934420002936FinishTrueTrueTrueTrue因为存在安全序列{p1,p1

,p3,p4}，故系统安全，系统可将资源分配给进程p2。同理可知此后的㈢P1发出的资源请求request1(1,0,1)系统不响应(因为>available),P1阻塞；㈣P3发出资源请求request3(

0,0,1)系统也不响应(试分配后不安全),P3阻塞。③死锁的检测与解除死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。(1)死锁的检测检查死锁的办法是由软件定时检查

系统的资源分配图中是否存在无法化简的有向环路。若是，则此时发生了死锁，且环路中的进程是死锁进程；否则不存在死锁。其理论依据是死锁定理(即死锁的充分条件)。死锁检测算法与银行家安全检测子算法很相似，可对照理解。由于

死锁是系统中的恶性小概率事件，死锁检测程序的多次执行往往都不会调用一次死锁解除程序，而这却增加了系统开销，因此在设计操作系统时需要权衡检测效果与系统的开销。一个死锁检测算法的描述:booleandeadlocked(int[]request){int[

]save=copy(available);boolean[]done=newboolean[numberOfProcesses];for(inti=0;i<done.length;i++)done[i]=false;for(inti=0;i<numberO

fProcesses;i++)//Findaprocessthatcanfinish.{intp;for(p=0;p<numberOfProcesses;p++){if(!done[p]&&lessOrEqual

(request[p],available))break;}if(p==numberOfProcesses)//Noprocesscancontinue.Thereisadeadlock{available=save;retur

ntrue;}incr(available,Allocation[p]);done[p]=true;}//Assumeprocesspfinishesavailable=save;returnfalse;}(2)死锁的解除常见的死锁解除方法有以下两种：•1）撤消进程法撤消全部死锁进程：

简单，但代价太大。该做法很少用。最小代价撤消法：首先计算死锁进程的撤消代价，然后依次选择撤消代价最小的进程，逐个地撤消死锁进程，回收资源给其他进程，直至死锁不复存在。进程的撤消代价往往与进程的优先级、占用

处理机的时间等成正比。此法用得较广。•2）挂起进程法（剥夺资源）使用挂起/激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活它们。目前该法较受重视。④置之不理死锁的检测与解除办法不对系统的资源分配加任何限制，因此是对付死锁的诸办法中

导致资源利用率最高的一种，在对安全性要求高的大型系统中常用。但它的实现代价也是最大的。对付死锁最简单的办法，就是像鸵鸟遇到危险时把头埋进沙子里一样对死锁视而不见。有人美其名曰“鸵鸟算法”。这是对方便性与正确性折中的做法，数学家不愿意

，工程师愿意，因为死锁发生的概率实际上很小，而系统解除死锁的代价相对太大了。例如，假设UNIX系统的进程表有100项，有10个进程在执行，每个都要创建12个子进程。在各创建9个子进程后，进程表项被全部用完。则这10个进程将陷入无休止的循环等待，

即使让它们隔一段时间后再执行FORK，也会再次失败，这实际上是死锁。它发生的概率很小，但的确存在。我们难道会为了消除这种状况就放弃进程、FORK这些概念和方法吗？UNIX采用鸵鸟算法对付死锁，实际上它把解除死锁的工作交给用户

去做了，为此它提供ps、kill等系统调用。例2.10某系统有同类互斥资源m个，供n个进程共享使用。如果每个进程最多申请x个资源（1≤x≤m），试证明：当n(x-1)+1≤m时，系统不会发生死锁。•证明：因为每个进程最多申请x个资源，所以最坏情况是每个进程都得

到了（x-1）个资源，并且现在均需申请最后一个资源。此时，系统剩余资源数为m-n(x-1)，于是只要系统中至少还有一个资源可供使用，就可以使这n个进程中某个进程得到其所需要的全部资源，并能够继续执行到完成，归还资源可供其他进程使用。因而不会发生死锁。即只要m-n(x-1

)≥1时，系统就一定不会发生死锁。亦即当n(x-1)+1≤m时，系统不会发生死锁。2.9处理机调度•处理机调度的基本概念——类型、时机与过程（P67）、CPU使用方式•调度算法1处理机调度的基本概念•三级

调度的概念(加上I/Oscheduling有四级调度)处理机调度常分高级调度、中级调度、低级调度（或者叫长程调度、中程调度、短程调度）三种，高级调度又叫作业调度，中级调度又叫内存调度(它实际上就是支持虚拟存储技术的系统中的对换功能(或者叫挂起与解

除挂起功能))，低级调度又叫进程调度，只有低级调度涉及处理机分派程序的调用，今天的分时系统通常只含有后两种调度，而早期的批处理系统支持三级调度，如下图所示。•设计调度算法的若干准则（有矛盾，需权衡）面向用户考虑：T周转、

T响应、T截止、公平响应、优先级等；面向系统考虑：吞吐量、CPU利用率、均衡使用资源等；批处理系统中的三级调度2调度算法（重在思想）——Simpleisbeautiful•先来先服务(First-ComeFirst-Served)•短作业（进程）优

先(ShortJobFirst)•优先级高者优先(HighestPriorityFirst)•时间片轮转(RoundRobin)•多级反馈队列(MultilevelFeedbackQueues)①先来先服务调度算法FCFS——自然排队法•算法思想：调度程序

每次总是按照进程进入就绪队列的先后顺序，选择最先进入该队列的进程，把处理机分配给它，使之投入运行。如下图所示：DCBACPU完成进程标识到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B1100110110

01C21101102100100D31001022021991.99例如，采用先来先服务调度法的某单道批处理系统有四道作业先后到来，则其周转时间和带权周转时间如下：FCFS算法有利于CPU繁忙型的作业

，不利于I/O繁忙型的作业。•这是一种不可抢占方式的调度算法，优点是实现简单，缺点是后来的进程等待CPU的时间较长。即有利于长作业（进程），不利于短作业（进程）。•在单机系统中，先来先服务调度法已很少用作主调度算法，而是常作为辅助算法嵌套在其它调度模式中。例

如，许多调度模式根据优先级将处理机分配给进程，但对于具有相同优先级的进程则按先来先服务法进行分配。②优先级调度算法(HPF)•总是选择具有最高优先级的进程首先使用处理机，优先级相同按FCFS。根据进程的优先数是否可变以及处理机的两种使用方式，该算法具体

主要分为以下两类：•基于静态优先权的不可抢占方式调度：进程的优先权在创建时确定，且在运行期间保持不变。（简单易行，系统开销小，但不够精确，很可能出现优先权低的作业（进程）长期不被调度的情况（称饥饿现象）。所以，只在要求不太高的系统中，才使用静态优先数（权））基于动态优先权的可抢占方式调度：在

创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能，但实现稍复杂。今天有很多系统都用此法。例2.11有5个进程P1、P2、P3、P4、P5，它们同时依次进入就绪队列，它们的优先数和需

要的处理机时间如下：进程处理机时间优先数P1103P211P323P414P552忽略进程调度所花的时间，要求：（1）分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序；（2）分别计算各进程在就绪队列中的等待时间和平均等待时间。FCFS等待时间静态优先级法等待时间0110181

1111301413解:(1)采用FCFS调度算法时各进程的执行次序为：P1→P2→P3→P4→P5。采用静态优先级调度算法时各进程的执行次序为：P4→P1→P3→P5→P2（假设优先数与优先权成正比）。(2)FCFS中，平均等待时间＝（0+10+11+1

3+14）/5＝9.6；静态优先级法中，平均等待时间＝（1+18+11+0+13）/5＝8.6③时间片轮转调度算法(RR)•基本思想：系统把所有的就绪进程按FCFS原则排成一个队列，且规定一个时间片作为进程每次使用处理机的最长时间单位，按时间片把处理机轮流分配给当前位

于就绪队列队首的进程使用，当该进程的时间片用完以后，系统产生时钟中断，剥夺该进程的执行，将它送到就绪队列队尾，等待下一轮次的调度。同时处理机调度程序又去调度当前就绪队列的队首进程，也让它运行给定的时间片，如此循环往复，如下图所示

：….FCBACPU完成时间片轮转调度算法示例(时间片=20ms)进程使用CPU时间P153P217P368P424•时间片轮转法调度的Ganttchart(Gantt图)表示如下:•与SJF法性能相比,平均周转时间更长，但响应时间更短。P1P2P3P4P1P3P4P1P3P302

037577797117121134154162④多级反馈队列调度算法(MFQ)•以上介绍的算法，都存在一定的局限性。•现在主流的操作系统，如UNIX、Linux、WindowsNT等，都使用一种综合性的调度算法——多级

反馈队列调度算法。该算法综合了上述三种算法以及多队列调度算法的思想和优点，总体调度性能优越，适于各种类型的作业，但其实现也比较复杂。•系统按进程优先级设置了多级（比如n级，n≥2）就绪进程队列，并为各队列赋予不同长度的时间片；从第1级到第n级队列，优

先级越来越低，进程的时间片越来越大。•新创建的进程插入到第一级就绪队列的队尾，然后按FCFS原则排队等待调度。当轮到其执行时，它如果能在相应的时间片内完成，便撤离系统；否则，系统便根据该反馈信息把它插入到第二级队列的末尾；第n级队列中的进程运行一个时间片后若未完成，仍回到该队队尾。•仅当

第一级队列空闲(常用位图表示)时，调度程序才调度第二级队列中的进程运行，依次类推……；新进程可抢占低优先级进程的处理机，被抢占者一般仍回原队尾。如下图所示：多级反馈队列调度算法的思想：……CPUtimeoutschedulerdonetimeouttimeout被唤醒的进程将进入哪

一级队列？Readyqueue1Readyqueue2Readyqueue3Readyqueuentimeout就绪队列1有最高的优先级和最小的时间片,而对列n正相反。多级反馈队列调度算法示意图admit•多级反馈队列调度算法的性能–有

较好的调度性能，能较好地满足各种类型用户（进程）的需要。无论终端（交互）型作业用户、短批处理作业用户，还是长批处理作业用户都较满意。–但实现开销较大–UNIXSVR4、Linux和Windows2000/XP中的

低级调度都采用此法。2.10线程(Thread)的概念•线程的引入自20世纪60年代提出进程概念后，在操作系统中一直以进程作为能独立运行的基本单位。直到20世纪80年代中期，人们为了进一步减少程序在并发执行时所付出的时空开销(主要指进程的创建、切换和通信开销)，提高进程内的并发程度，进而

提高系统的并发性，和吞吐量，提出了比进程更小的能独立运行的基本单位——线程。线程的定义定义：线程是进程中的一个实体，是系统独立调度和分配的基本单位，故又称为轻量级进程(LightWeightProcess)，它由线程控制表

、存储线程上下文的用户栈以及核心栈组成。传统的进程称为重量级进程(HeavyWeightProcess)。也有人这样描述线程：线程是进程中一个可以独立执行的子任务线程是进程中一个可以调度的实体线程是进程

中一个可执行单元线程是进程中一个控制线索线程是进程中一段指令流一个进程中至少有一个线程。线程继承所属进程的一切资源，它自己只拥有运行所需的很少的一点资源，如几个寄存器和一个堆栈等。因此，一个进程内的几个线程之间的切换的开销比进程间切换的开销小得多，这是系统引入线程可以

提高效率和并发性的主要原因。线程与进程的比较（1）•1．拥有资源进程是拥有资源的一个独立单位，而线程几乎不拥有系统资源,但它可以访问其隶属进程的资源•2．调度以进程为单位进行处理机切换和调度时，处理机切换时间长，资源利用率降低。而进程内线程

的切换时间较短，从而处理机效率较高。•3．并发性均可并发执行，但线程的并发粒度小，并发程度高，从而能更有效地利用系统资源，提高系统的吞吐量。线程与进程的比较（2）•4．系统开销系统创建、撤消和切换进程的开销远大于线程的。另外，同一进程内的多个线程具有相同的

地址空间，故它们的同步实现也较容易。•5．进程是系统可感知的进程的调度、同步等大多由OS内核完成，而线程的控制既可以由OS内核进行（指内核级线程），也可以由用户控制（指用户级线程）。[目前，Solaris10只支持内核级线程。]线程的适

用范围线程特别适合于共享存储的多处理机系统和C/S模型，成功例子很多，如文件服务器，WWW浏览器等，以下是几种典型的应用：1.服务器中的文件管理和进程通信控制；2.前后台处理；3.异步处理；4.数据的批处理；5.网络系统中信息发送和接受……引入线程后带来的问题线程是新生

事物，有生命力，但也带来许多影响编程模型的新问题，导致现在把线程放在内核进行管理（如内核级线程）和把线程放在用户空间进行管理（如用户级线程）的两种系统都在被使用。因此，线程的引入也有争议。几类新问题如下：•对fork系统调用

的影响•多线程共享数据结构的问题•关于系统的出错报告•关于信号的使用•对堆栈管理的影响这些问题并非无法克服，但它们说明引入线程后系统得重新设计，起码系统调用的语义要重新定义，库例程也要重写，而且所有改变都得向后兼容，以保证只有一个线程的进程的可用性。来看一道填空题：在操作系统中引入“进程”概

念的主要目的是（）。•A．改善用户编程环境•B.描述程序动态执行过程的性质•C.使程序与计算过程一一对应•D.提高程序的运行速度再看2道选择填空题：•1.在进程状态转换时，下列哪一种状态转换是不可能发生的？A)就绪态→运行态B)运行态→就

绪态C)运行态→等待态D)阻塞态→运行态•2．某进程在运行过程中需要等待从磁盘上读入数据，此时该进程的状态将（）。A.从就绪变为运行B.从运行变为就绪C.从运行变为阻塞D.从阻塞变为就绪P69~P73综合练习题二作

业：第3章存储器管理–3.1内存管理概述（次重点）–3.2分区存储管理（次重点）–3.3页式存储管理（重点）–3.4段式存储管理（非重点）–3.5段页式存储管理（自学）本章需掌握的知识要点•内存管理任务•三种内存管理方式•两类算法（内存分配、页面置换）•三组区别

可重定位动态分区基本分页请求分页实存与虚存分页与分段连续与离散3.1内存管理概述1.存储体系三级存储器内存(主存)：RAM、ROM外存(辅存)：磁盘、磁带、光盘等高速缓冲存储器(cache)另有寄存器级OS负责协调各存储器的使用，OS本身的程序和数据与其他程序一起共享主存，为安全起见，多道程序系

统常由OS把内存初始化为系统区和用户区两大部分：内存系统区（存放OS程序和数据）用户区（存放用户程序、数据）2.存储管理的目的•充分利用内存，为多道程序并发执行提供存储基础•尽可能方便用户使用自动装入用户程序用户程序中不必考虑硬件细节•能够解决小内存运行大程序的问

题•支持程序在执行时可以动态伸缩•保证内存存取速度快•实现存储保护与安全•实现共享与通信•了解有关资源的使用状况•权衡实现的性能和代价3.存储管理的任务或功能（1）内存空间的管理、分配与回收–记录内存的使用情况——设置相应的内存分块表（内存分配回收的

依据）–内存空间划分问题？——静态或动态，等长或不等长–确定分配算法——考虑连续性与离散性，驻留性与交换性，一次性与多次性，静态方式与动态方式–内存碎片问题及解决办法–确定回收策略（2）地址转换（又称地址重定位、地址映射）–指为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑

地址（相对地址，虚地址）转换为运行时由机器直接寻址的物理地址（绝对地址，实地址）的过程3.存储管理的任务（续）–根据实施转换的主体和转换时机的不同，重定位具体分为两种：静态重定位和动态重定位。后者更常用–系统采用动态重

定位后，程序在内存可浮动（3）内存的共享与保护–进程共用相同内存区可节省空间，便于通信，所共享的代码应为纯代码（或者叫可重入的代码）–内存保护限定程序只能访问自己所在的内存区，保护了OS和其他程序——

常用界限寄存器对法和存取控制字来实现（4）内存的扩充–常用覆盖、交换和虚拟存储技术等实现对内存的逻辑扩充，以使小内存能够运行大程序装入Load1,20034561200物理地址空间Load1,data1data13456源程序Load1,20034560100200编译连接逻辑地址空间B

A=10001100系统采用动态重定位，程序装入内存时的示例（内外存副本一致）：10003456LOAD1,2000100200300LOAD1,2003456逻辑地址空间110012001300物理地址空间200VR+1000BR••••••••••••••••••动态重

定位示例：覆盖示意图主程序(30k)子程序A(8k)子程序B(10k)子程序M(20k)子程序N(25k)子程序X(15k)主程序（30k)覆盖区1(25k)覆盖区0(10k)内存区用户的结构化程序区程序的装入和链接•源程序从编辑到运行要经

历以下阶段：编辑编译链接装入运行•静态链接、动态链接•绝对地址装入、静态重定位装入、动态重定位装入存储管理策略分类•存储管理策略：–实存管理•连续区分配（包括固定分区、可变分区和伙伴系统）•分页（Paging）•分段（Segmentation

）–虚存管理•请求分页(Demandpaging)--主流技术•请求分段(Demandsegmentation)•段页式（segmentationwithpaging）离散分配3.2分区式存储管理——早期的一类实存管理技术系统给每个

作业或进程分配一个连续的内存分区。•单一连续区分配（静态分区技术）•固定分区分配（静态分区技术）•可变分区分配（动态分区技术）•可重定位可变分区分配（动态分区技术）•伙伴系统（动态分区技术）1.单一连续区存储管理系统静态地将内存划分为两个区域，一个供操作系统使用，一个供用户使用，且每次只能装入一

个作业或进程，主要用于早期单道程序系统和后来的PC操作系统。特点是实现简单，但内存利用率低，作业大小受限。操作系统用户程序0xFFF...0区号起始地址长度(KB)状态1aS102bS213cS30系统预先把可分配的内存空间分

割成若干个连续区域，每一区域称为分区，每个分区的大小可以相同也可以不同，分区的个数与大小固定不变，每个分区每次只能装一个作业。OS0abcd空job2空内存分块表(MBT)内存特点：实现简单，可用于多道程序系统，但内存利用率低，作业大小受限。2.固定分区存储管理——单一连续区

在多道程序系统中的直接应用3.可变分区存储管理•基本思想内存划分是在作业或进程进入时动态进行的，分区的个数与大小都不是固定的作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配若有足够的空间，则把分配算法选中的那个分区直

接分配给该作业，或者从那个选中的分区中割下与该作业申请量等大小的一部分连续空间分给该作业；否则令其等待。•特点克服了固定分区管理的“内碎片”问题，但产生了“外碎片”。怎样解决碎片问题呢？•改进内存释放算法•在内存中移动程序•变连续分配为离散分配4.可重定位

可变分区存储管理•基本思想相当于引入了动态重定位和内存紧凑（紧缩、拼接、紧致、浮动、搬家）（compaction）技术的可变分区存储管理•问题实现紧凑所花的代价与换来的提高了内存空间利用率的好处相比是否值？内存紧凑的开销、频率、条件、时机？一经紧凑，外

碎片是否彻底消失？•特点消除了内碎片，提高了内存利用率，便于动态申请内存，便于共享内存，便于动态链接，但会产生外碎片，而紧凑内存需要花费处理机大量时间，另外，还需要硬件重定位机构支持，作业大小也受内存可用空间的限制。可重定位可变分区存储管理（续1）•内

存管理用主要数据结构空闲分区链（或空闲分区表）•内存分配算法（顺序查找分配，可能触发紧凑程序）最先适应（FirstFit）下次适应（NextFit）最佳适应（BestFit）最坏适应（WorstFit）•内存释放/回收算法（考虑及时合并相邻空闲区）先在空闲分区链中

找到插入点，再考虑能否合并相邻空闲区数据结构怎样组织更有效？例3.1分区存储管理算法题•采用可变分区方式管理内存时，若内存中按地址顺序依次有五个大小依次为15k、28k、10k、226k和110k的空闲区。现有五个作业Ja、Jb、Jc、J

d和Je，它们各需要内存10k、15k、102k、26k和180k。问：⑴如果采用最先适应分配算法，能将这五个作业按Ja~Je的次序全部装入内存吗？⑵用什么分配算法装入这5个作业可使内存的利用率最高？解答：⑴按最先适应分配

算法，不能将这五个作业按Ja~Je的次序全部装入内存。因为内存中前两个原先的空闲分区能依次装入Ja(10k)和Jb(15k)，第3个10KB的空闲区和刚刚划分出来的两个大小分别为5KB和13KB的空闲区均无法分配，第4个空闲区可以分2次装入作业Jc(102k)和Jd(26k)，则作业Je(1

80k)无法装入内存。⑵用最佳适应分配算法装入这5个作业，可使内存的利用率最高。此时，原先的5个空闲区依次装入了5个作业，它们是：Jb(15k)，Jd(26k)，Ja(10k)，Je(180k)和Jc(102k)。15k28k10k226k110k5.伙伴系统（

buddysystem）——介于固定分区与可变分区之间的动态分区技术•伙伴系统可看作固定分区分配和可变分区分配的一种折中方案。采用伙伴系统时，内存是以2的幂次个字节大小的空闲块为分配单位的。系统初启时，只有1个最大的2的幂

次的空闲块，它就是整个可用的内存空间。当1个进程申请内存时，系统就分给它1个大于或等于进程所申请尺寸的最小的2的幂次的空闲块。例如，某进程提出的50KB的内存请求，将首先被系统向上取整，转化为对1个64KB的空闲块的请求。•伙伴

系统的内存分配过程在一开始不能找到合适的空闲块时将把一个最小的比该空闲块大的空闲块对分成2个“伙伴”单位，该对分过程可能会继续，直到获得合适的空闲块为止。•伙伴系统的内存释放过程首先考虑将被释放块与其伙伴单位合并成1个大

的空闲块，然后继续合并下去，直到不能合并为止。伙伴系统（续1）为了实现伙伴系统，系统要为每一种可能的空闲块维护1个空闲块链表。设系统管理的可用内存空间共为2N个字节，则1个伙伴系统最多需要维护N个空闲块链表。由于每种尺寸的空闲块都有一个空闲块队列，因此内存的

分配与释放可以有效地进行。Linux维护6个链表。伙伴系统的最大缺陷是不能有效地利用内存，特别是内碎片严重。例如，1个257KB的进程需要占用1个512KB的分配单位，其中将产生255KB的内碎片。另外，每次释放内存时都尽可能地合并伙伴单位的做

法也会降低系统性能，因为刚合并好的块可能马上又要对分。一种改进的做法是延迟合并的时机。伙伴系统（续2）伙伴系统示意图ActionMemoryStart1MA请求150kbA256k512kB请求100kbAB128k512kC请求

50kbABC64k512k释放BAC64k512kD请求200kbAC64kD256kE请求60kbACED256k释放CA64kED256k释放A256k64kED256k释放E512kD256k释放D1M3.3页式存储管理——不用“紧凑”也

能消除碎片的一种离散分配技术•实分页式存储管理（基本分页）•虚拟页式存储管理（请求分页）3.3.1实分页存储管理——似当今磁盘空间的管理，我认为在PC上很有发展前途！1.基本思想（≈特殊的固定分区+离散分配）•系统自动地等分进程地址空间和内存空间，每一等分单位分别叫页（p

age）和块（frame，也叫页帧、页框、页架），页与块等大小，且都从0开始连续编号。进程运行时，全部页面必须装入内存，但逻辑上连续的各个页所对应的内存块可以不连续。2.相关概念•逻辑地址、页面、页内碎片分页对用

户是透明的。页面是内存的划分使用单位，似磁盘的扇区或簇，也似CPU的时间片。一般，一页的大小为2的整数次幂（k/2~4K~16KB），也是个实验统计值，不能太大，也不能太小，为什么？进程的地址空间是一维连续的，用一个记号即可表示一个逻辑地址，但为重定位方便，系统常视逻辑地址为两部分组成的，即把地

址的高位部分视为页号，低位部分视为页内偏移。进程最后一页中空闲的部分称为页内碎片。0111231页号P页内位移量W编号0~1048575相对地址0~4095该地址结构限定的最大地址空间是多少？最大页表呢？3.管理•页表（pagemaptable）：系统为每个进程建立

一个页表，页表给出逻辑页号和具体内存块号相应的关系(虚分页系统中页表表目的内容更多)。页表放在内存，属于进程的现场信息。页表源于一组动态重定位寄存器，今天的用途主要有两处：①记录进程的内存分配情况②实现进程运行时的动态重定位。为了解决要求连续

内存空间存放页表的问题，可用对页表分页并将其各页面离散存放的办法来实现。这就形成了多级页表，目前最常用的是2级页表，如Windows2000和Linux中。这时，原来的页号部分，又被看成是两部分：页目录偏移、页表偏移。另

外，在IBMAS/400和MacOS中，使用更省内存的反置页表,页表表目为：Pid、page、valid、point。下面是一个页表示意图。...01234560123456进程的地址空间页框（物理块）页号页表主存中页框

（物理块）.......页表示意图：0310/10/10/10/10/1017……空闲块数……空块管理——位示图(用于外存分配时常叫盘图)使用时需进行字位号到块号的转换：(i,j)b，b=i*w+j。另外，找n个连续的块较慢。3.管理（续1）3.管理（续2）•内存的分配与回收计算

一个作业所需要的总块数N查位示图，看看是否还有N个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图4.硬件支持•系统设置一对寄

存器：页表始址寄存器（用于重定位时查页表）页表长度寄存器（用于重定位时内存保护校验，页表目还常有控制位）•联想存储器（associativememory）——快表（cache结构，为提高地址变换速度而引入，在IBM系统中称TLB（

Translationlookasidebuffers））用途：保存正在运行进程的部分页表项，以快速重定位快表表目内容：页号、内存块号、标识位、淘汰位快表的特点：可按内容并行查找快表命中率：已经证明，16个表目可达90%以上。I

ntel80x86/Pentium有32项，SGIMIPSR4000有48项。下面是快表在地址转换过程中应用的示意图。分页地址映射过程示意图地址越界p´页表l比较P>=1pp´.快表b+页号p页内地址dP´d页表地址寄存器页表长度寄存器逻辑地址

..物理地址页目录地址目录位移页表位移页位移虚拟地址页表地址...页目录（每进程一个）块号...页表代码或数据...物理页++二级页表结构及地址映射过程（未画出快表）5.实分页存储管理方式小结•优点：内存利用率高，解决了碎片问题；便于管理。•缺点：不易实现共享（见P93）；不便于页面

动态增长；进程仍受内存可用空间大小的限制；所需硬件支持较多。3.3.2虚拟页式存储管理1.基本思想≈实分页+对换和请求装入功能系统等分进程地址空间和内存空间，每一等分单位分别叫页和块，页与块等大小，且都从0开始连续编号。进程运行时，只需部分页面在内存，且

逻辑上连续的页所对应的内存块可以不连续。当进程访问的页不在内存时将产生缺页中断，由服务程序把所缺页装入内存，此时若内存空间已满，则又需要对换进程根据页面调度算法淘汰某个内存页面，再装入所缺页面。2.虚拟存储器的概念•实存管理方式的特征：一次性；驻留性；连续性。•虚拟存储器是为了逻辑扩充

内存，以解决小内存无法运行大程序的问题而引入的，是一种以CPU时间和外存空间换取内存空间的技术（是OS中的资源转换技术），也是迄今为止逻辑扩充内存程度最彻底的技术（远强于覆盖和交换技术）。•虚拟存储器是在1961年由英国曼彻斯特大学的Fotheringham提出，并在该校的atlas机器上实现

的一种存储技术。从1970年后被广泛应用，今天的OS普遍采用这一技术管理内存，但我们仍应辨证地看待它。•虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，OS把程序当前使用的部分保留在内存，而把其它部分保

存在磁盘上，并在需要时在内存和磁盘之间动态交换。•虚拟存储器支持多道程序设计技术。虚存管理方式的特征：多次性；对换性；虚拟性；离散性2.虚拟存储器的概念（续1）1968年美国MIT的Denning提出程序局部性原理是对虚拟存储器有力的理论支持。•程序局部性原理程序在执行时呈现出高

度的局部性特征，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。程序执行的局部性表现在时间与空间两个方面：时间局部性一条指令被执行了，则在不久的将来它可能再被执行空间局部性若某一存储

单元被访问，则在不久之后，与该存储单元相邻的单元也可能被访问2.虚拟存储器的概念（续2）•虚拟存储器定义（至今没有统一定义，我认为以下前3种比较重要）–虚假的存储器；–进程能够访问的虚拟地址空间；–具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器

系统。–把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存•虚拟存储器是把内存与外存这两级存储器并用做一级存储器的结果，是逻辑扩充内存的最佳手段•虚拟存储器的容量取决于内存与外存的容量之和，但实际最大尺寸取决于系统的地址结构2.虚拟存储器的概念（续3）

虚拟存储器是建立在离散分配的内存管理技术基础上的，它主要有以下3种实现方法：•请求分页系统——虚拟分页系统–基本分页系统+请求分页功能+页面置换功能–硬/软件支持：请求分页的页表机制、缺页中断机构、动态地址变换机构、对换机制、大容量外存。•请求分

段系统——虚拟分段系统–基本分段系统+请求分段功能+分段置换功能；–硬/软件支持：请求分段的段表机制、缺段中断机构、动态地址变换机构、对换机制、大容量外存。•请求段页式系统——虚拟段页式系统–请求分页系统+请求分段系统–硬/软件支持：页表机制

、缺页中断机构、段表机制、缺段中断机构、动态地址变换机构、对换机制、大容量外存。2.虚拟存储器的概念（续4）——要辨证地看待虚拟存储器管理•问题1：windows98为何常提示“内存不足”？•问题2：当今OS几乎都用虚拟内存技术，有必要吗

？•虚拟存储器管理的主要优点扩充了内存，解决了小内存无法运行大程序的问题，提高了内存的利用率和多道程度•虚拟存储器管理的主要缺点实现开销大，程序运行比实模式下慢3.虚分页所需的硬件支持•页表机制（似实分页的，只是扩充了页表

目内容）–用于地址转换；–扩充页表项：页号、页架号、状态位、访问字段/位、修改位、外存地址•缺页中断（PageFault）机构–在地址映射过程中，所访问的页不在内存时，便产生一缺页中断；OS接到此中断信号后，就调出缺页中断处理程序，根据页表中

给出的外存地址，将该页调入内存，更新页表，完成重定位，使进程继续运行下去。这期间可能调用置换程序。–与常规中断的不同之处：•在指令执行期间产生和处理中断信号；•一条指令在执行期间，可能产生多次缺页中断。3.虚分页所需的硬件支持（

续1）•地址变换机构（似实分页的，但重定位过程中可能触发缺页中断）–首先检索快表，若找到，修改页表项中的访问位，然后利用页表项中给出的页架号和页内地址，形成物理地址。–如果在快表中未找到相应的页表项，则检索内存中的页表，察看页表项中的状态位，若该页已

经调入内存，则形成物理地址，并更新快表，当快表满时，应淘汰一个页表项；若该页尚未调入内存，则产生缺页中断，请求OS把该页调入内存，然后再完成重定位。4.内存分配策略和分配算法•最小物理块（页架）数的确定–保证进程正常运行所需的最少页架数；–与指令的格

式、功能和寻址方式有关。•页架的分配策略–固定分配局部置换：进程占据的内存页架数不变；置换时在该进程所占页架中选则换出对象。系统给各进程分配固定数目的页架时，可考虑按比例分、平均分、结合工作集、结合优先权分配等策

略。–可变分配全局置换：初始时先给进程分配一定数目的页架，当进程缺页率较高或较低时，能由OS对其占据的页架数加以调整，置换时在整个内存用户区的页架中选则换出对象。–可变分配局部置换：可变分配同上，置换时在运行进程所占页架中选则换出对象。4.内存分配策略和分

配算法（续1）•工作集（WorkingSet）模型Denning在1968年研究缺页率与页架数的关系时提出工作集的概念，旨在降低进程的缺页率。–一个进程当前使用的页的集合叫它的工作集。更形式化的定义是：对于给定的页面访问序列选取定长的区间，称为工作

集窗口，落在工作集窗口中的页面集合称为工作集。例如，某访问序列为：26157775162341234443434441327||t1||t2则ws(t1)={1,2,5,6,7}，ws(t2)={3,4}–尽量保持进程的工作集在内存可以降低进程的缺页率，这种方法叫工作集模型。依据是局部性原理。

借助该模型，可实现可变分配、改进时钟置换算法等。–Windows2000在系统初始化时，计算进程的最小和最大工作集值，当物理内存大于32MB（server大于64MB）时，进程缺省最小工作集为50页，最大工作集为345

页。4.内存分配策略和分配算法（续2）•内存分配算法–同基本分页，管理物理页帧/空闲内存块的数据结构也是位示图5.调页策略•请求调页策略（demandpaging）–进程运行过程中靠缺页中断程序装入所需访问的不在内存的页面。实

现简单，用得广，但费时。•预调页策略（prepaging）–进程运行之前预先装入一些页面。主要用于进程的首次调入时，并且多涉及工作集模型的实现。5.调页策略（续1）•问题–从何处调入页面？外存文件区、外存对换区、内存区（共享页面或Buffer中页面的及时再利用）–页面的调入过程？先由中断服务程序调

内存分配程序（可能触发对换程序）获得一内存块，再查页表，把所缺页从外存调入内存，并修改页表。这是在重定位过程中实现的，对用户透明。6.页面置换（淘汰/调度）算法——PageReplacementAlgorithms•颠簸（抖动）在虚存中，页面在

内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。例如，一个每隔几条指令就发生一次页面故障的进程称为在颠簸（因为一条指令的执行只需几纳秒，而每从磁盘上读入一个页面则常需几十毫秒）。•系统

发生颠簸的原因页面置换算法不合理分配给进程的物理页面数太少6.页面置换算法（续1）•最佳（OPTimal）置换算法淘汰以后不再需要的或最远的将来才会用到的页面。1966年Belady提出的理想算法，但无法实现，主

要用于评价其他置换算法。•先进先出（FIFO）置换算法选择在内存中驻留时间最长的页并淘汰之。它实现简单：只需把进程在内存的页面按先后次序链成1个队列，并设置1个替换指针，使它总是指向内存中最老的页面。缺点：效率不高，因为

它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。另外，它还有Belady异常现象（考虑页面访问序列为1~4，1~2，5，1~5的进程分别获得3块内存和4块内存请求装入执行时的缺页情况）。6.页面

置换算法（续2）•最近最少使用（LRU,LeastRecentlyUsed）置换算法选择最后一次访问时间距离当前时间最长的一页并淘汰之。该算法理论上性能好，但实现代价高（需硬件支持，如：为进程每个内存页面设一计时器或寄存器，或为进程所有内存页面设一栈/链表，P98）。

LRU的软件解决方案（LRU的近似算法）：二次机会(SC,SecondChance）置换算法时钟(Clock)置换算法最近未使用（NRU,NotRecentlyUsed）置换算法6.页面置换算法（续

3）•二次机会(SC,SecondChance）置换算法——FIFO法的一种改进实现实现：页表目中增设访问位R，初值为0，页面访问时置1。发生缺页中断需置换时，OS按照先进先出置换算法选择某一页面，检查其

访问位，如果为0，则淘汰该页，如果为1，则将该位置0，把该页放到内存页面链表的尾端，给它第二次驻留机会，再检查内存页面链上的下一个页面。如果查到链尾还未找到置换对象，则再从链首开始，进行第2趟扫描检查。优点：实现简单，且性能比FIFO好很多；缺点

：运行效率低，时间开销大。6.页面置换算法（续4）•时钟(Clock)置换算法——SC的一种改进实现SC算法因为常需把给予二次驻留机会的页面移到链尾而降低效率，若把其所用的内存页面单向链表改为循环链表，则就不必在链中移动页面了。这种改进的SC法就是Clock法。显然，Cloc

k算法的页面调度性能与SC法一样，但其自身的运行效率比SC法高，因而比SC法更常用。其实，Clock法从某种角度也可看作一种LRU近似算法。6.页面置换算法（续5）•最近未使用（NRU,NotRecentlyUsed）置换算法选择在最近一段时间内未使用过的一页并淘汰

之。实现：页表目中增设访问位R，修改位M。启动进程时，R、M置0，随后R被定期清零。根据R、M的值，进程在内存的页面分为4类：00类、01类、10类、11类。发生缺页中断需置换时，OS从编号最小的非空类中随机选择一页淘汰。特点：易实现，性能上

也够用。其他置换算法（仅作一般了解）•最少使用频率（LFU,LeastFrequentlyUsed）置换算法选择在最近时期使用频率最少的页面淘汰。•页面缓冲置换算法=FIFO+page-buffer+write-delay该算法用在VAX/VMS中，利用了

延迟写技术，调度性能也不错，但延迟写都存在安全隐患。Windows2000采用可变分配局部置换策略，也用类似的置换算法。6.页面置换算法（续6）例3.2设某请求分页系统采用固定分配局部置换策略，一进程的页面

走向为4、3、2、1、4、3、5、4、3、2、1、5，该进程分得3个页架，初始为空，试计算分别采用FIFO、LRU、OPT置换算法时该进程访问过程中所发生的缺页次数和依次被换出的页面。解：⑴FIFO432143543

215444111555555333444442222223333311是否命中xxxxxxxxx所以该进程运行时共发生缺页中断9次，被换出的页面依次是4、3、2、1、4、3。6.页面置换算法（续7）链首oldest：链尾newe

st：页架1页架2页架3⑵LRU432143543215栈：432143543215432143543214321435432是否命中xxxxxxxxxx所以该进程运行时共发生缺页中断10次，被换出的页面依次是4、3、2、1、

5、4、3。6.页面置换算法（续8）⑶OPT432143543215页架1444444444222页架233333333311页架32111555555是否命中xxxxxxx所以该进程运行时共发生缺页中断7次，被换出的页面依次是2、1、4、3。6.页面置换

算法（续9）例3.3设某请求分页系统采用固定分配局部置换策略，置换算法为FIFO。一进程在内存中分得m块，初始为空，其页面走向为1，2，3，4，1，2，5，1，2，3，4，5。问：当m=3，m=4时各发生缺页几次？

解：m=3时，缺页中断9次；m=4时，缺页中断10次。注：•FIFO页面置换算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数不降反增。其实，上例也是。•其他置换算法没

有此异常。6.页面置换算法（续10）•分配给进程的物理页面数•页面本身的大小•程序的编制方法•页面淘汰算法例子3.4设某请求分页系统采用固定分配局部置换策略，置换算法为LRU。进程分得3页架，初始时全空，以下代码占1页，页面大小为128个整数；矩阵A128X128在逻辑地址空间中按行存放

。程序编制方法1：Forj:=1to128Fori:=1to128A[i,j]:=0;程序编制方法2：Fori:=1to128Forj:=1to128A[i,j]:=0;则该进程在两种编程方法下的缺页次数分别为：16385和129。影响缺页率的

主要因素3.4段式存储管理——需用“紧凑”才能消除碎片的一种离散分配技术，但便于代码共享与增长•实分段式存储管理（基本分段）•虚拟段式存储管理（请求分段）3.4.1实分段式存储管理(基本分段技术)——为方便用户编程和克服基本分页存储管理的缺点而引入1.基本思想（≈可重定位可变

分区+离散分配）•进程地址空间划分按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。(分段是由用户或编译器负责的）•逻辑地址（注意：分段地址空间是真正二维的）段号段内地址0116N...0S工作区

段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]数组[A]12345...进程地址空间分段示

意图：1.基本思想（续）•内存空间划分内存空间以段为单位被动态地划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定，相当于可变分区管理中的一个分区。•内存分配以段为单位分配内存，每

一个段在内存中占据一个连续区域，但同一进程的各段对应的物理段可以不连续。•进程运行时，其各段必须全部装入内存2.管理•段表记录了进程的每个逻辑段及其物理段的对应关系。每个进程设置一个段表，放在内存，属于其现场信息

。•空闲块管理空闲块链/表（似可变分区中的）•内存分配算法（似可变分区中的）段号012物理段首址段长度58K20K100K110K260K140K段表示意图：B0SA0NY0LX0PM0K逻辑段号01234进程1的地址空间1000

3200500060008000PKSLN内存K3200P1500L6000N8000S5000段长段始址01234操作系统.....段表3.硬件支持系统设置一对寄存器和一个联想存储器：•段表始址寄存器

：用于保存正在运行进程的段表的始址•段表长度寄存器：用于保存正在运行进程的段表的长度（例如上图的段表长度为5，它与段长及扩充段表目中的存取控制字一起用于分段管理中的存取保护）•联想存储器，即快表用途：保存正在运行进

程的段表的子集（部分表项）特点：按内容并行查找快表表目内容：段号、段始址、段长、标识（状态）位；访问位快表置换问题？ClCb+段号S段内地址d比较b+d段表S>=Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb...Slb地址越界d>=1分段地址映射及存储保护机制地址越界比较+4.实

分段式存储管理小结优点：便于动态申请内存便于共享(P103)便于动态链接管理和使用统一化缺点：似可重定位可变分区，如产生碎片，内存利用率低；紧凑开销大，需硬件支持多，进程受内存可用空间限制等。思考：1)分段与可重定位可变分区的异同？2)分段与分页的主要不同？

（PP104~105）自学：分段与分页的结合——段页式存储管理(P109)1.段表内容比实分段新增：•特征位（在/不在内存，是否可共享）•存取权限位（读，写，执行允许位）•标志位（是否修改过，能否移动）•扩充位（固定长/可扩充）3.4.2虚拟段式存储管

理≈实分段+对换和请求装入功能进程在执行过程中，有时需要扩大分段，如数据段。由于要访问的地址超出原有的段长，所以发越界中断。操作系统处理中断时，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理2.越界中断处理检查内存中是否有足够的空闲空间①若有，则装入该段，修改有关

数据结构，中断返回②若没有，检查内存中空闲区的总和是否满足要求，是则应采用紧缩技术，转①；否则，淘汰一（些）段，转①3.缺段中断处理大型程序包含：若干程序段，若干数据段一些熟知的事实：进程的某些程序段在进程运行期间可能根本不用互斥执行的程序段没有必要同时驻留内存

有些程序段执行一次后不再用到4.段的动态链接•静态链接：为了程序正确执行，必须由连接装配程序把它们连接成一个可运行的目标程序，并在程序运行前都装入内存。问题：花费时间，浪费空间•动态链接：在程序开始运行时，只将主程序段装配好并调入内存，其它各段的装配是在主程序段的运行过程中逐步

完成。每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接实现：需编译器配合支持。4.段的动态链接（续1）4.段的动态链接（续2）•机器指令的两种寻址方式：直接寻址，间接寻址LOAD100600直接寻址100数据600LOAD100800

间接寻址100间接字数据800链接间接字和链接中断采用间接寻址时，间接地址指示的单元的内容称为间接字，在链接间接字中，包含了直接地址和附加的状态位。格式为：L直接地址L：链接标志位（L=0：该段已经建立了链接；L=1：该段尚未链接）CPU执行

间接指令时，硬件能对链接字中链接标志位进行判断。当L=1时，硬件发出链接中断，并停止执行该条指令，转去执行中断处理程序。处理完后（L已被处理程序改为0），再重新执行该间接指令；若L=0，则根据间接字中的直接地址去

取数据。LOAD1,[A]|<Y>编译前LOAD*1,3|100......10067813...6787“[A]|<Y>”...编译后链接前编译器的准备工作（把对外段的符号访问译成了对本段链接间接字的间接访问）：4.段的动态链接（续3）3段LOAD*1,3|1001006787“

[A]|<Y>12004链接后：4段,即A段120<Y>：123454.段的动态链接（续4）链接中断处理•根据链接间接字找出要访问段的符号名和段内地址•分配段号，检查该段是否在内存，若不在，则从外存调入，并登记段表，修改内存分配表•修改间接字：修改连接标志

位为0，修改直接地址•重新启动被中断的指令执行由于只有“纯段”才可被共享，因此链接间接字应该放在杂段中。请求分段的其他存储管理任务的实现似基本分段和请求分页。4.段的动态链接（续5）PP109~112：综合练习题三补充题1（似七.4）某分页系统中，

经快表完成的一次内存访问需100ns，经页表完成的一次内存访问需180ns，要使一次有效的内存访问时间达到120ns，则访问快表的命中率必须是多少？补充题2某分页系统中，当进程所访问的页面在内存时，完成一次内存访问需200ns。当所访问的页面不在内存时，则如果内存有空闲页架或者被换出页面未

改写过，那么完成一次内存访问需7ms；否则需要15ms。如果页面故障率为5%，要换出的页面中有60%改写过，系统只运行单一进程，CPU在页面交换时是闲置的，那么有效的访问时间是多少？本章作业I/O设备是计算机系统的重要资源，用户

无权直接使用。设备管理的一个重要任务：便是按照一定的算法在各进程间调度和分配设备。另外，设备管理还要按照用户要求启动具体设备，完成数据传输操作，并且处理设备的中断。还有如何利用虚拟技术使独享设备“变为”共享设备，使一台物理设备“变为”多台

逻辑设备。4.1设备管理概述一、设备管理的分类1.按从属关系分类（1）系统设备：指在操作系统生成时已经登记在系统中的标准设备。如键盘、显示器、打印机等。（2）用户设备：指操作系统生成时未登记入系统的非标准设备。如鼠标、绘图仪、扫描仪等。2.按传输速率分类（1）低速设备：指传输速率为每秒钟

几个字符至数百个字节设备，如键盘、鼠标、语音输入等。（2）中速设备：指传输速率为每秒钟数千个字节至数万个字节的设备，如针式打印机、激光打印机等。（3）高速设备：指传输速率为数兆字节的设备，如磁带机

、磁盘机、光盘机等。3.按使用特性分类（1）存储设备：是计算机用来保存各种信息的设备，如磁盘、磁带等。（2）I/O设备：是向CPU传输信息或输出CPU加工处理信息的设备。例如：键盘，CRT（1）独占设备：指在一段时间内只允许一个用户（进程）访问的设备，大多数低速的I/O设备。如用户终

端、打印机等属于这类设备。因为独占设备属于临界资源，所以多个并发进程必须互斥地访问独占设备。4.按设备共享属性分类（2）共享设备：指在一段时间内允许多个进程同时访问的设备。显然，共享设备必须是可寻址的和可随机访问的设备，典型的共享设备是磁盘。（3）虚拟设

备：指通过虚拟技术将一台独占设备变换为若干台供多个用户（进程）共享的逻辑设备。一般可以利用假脱机（SPOOLing）技术实现虚拟设备。（1）字符设备：是指处理信息的基本单位是字符的设备，如键盘、打印机、显示器是字符设备。（2）块设备：是指处理信息的基本单位是字符块的设备，一般块的大小

为512B~4KB，如磁盘、磁带等都是块设备。5.按信息交换单位分类二、设备管理的目标•（1）提高设备的利用率。•应尽量提高CPU与I/O设备之间的并行操作程度，主要利用的技术有：中断技术、DMA技术、通道技术和缓冲技术。•（2）为用户提供方便、统一

的界面。•所谓方便，是指用户能独立于具体设备的复杂物理特性之外而方便使用设备。所谓统一，是指对不同的设备尽量使用统一的操作方式，例如各种字符设备用一种I/O操作方式。这就要求用户操作的是简便的逻辑设备，而具体的I/O物理设备有操作系统去实现，这种性能常常被

称为设备的独立性。三、设备管理的功能（1）设备分配。按照设备类型和相应的分配算法决定将I/O设备分配给哪一要求使用该设备的进程。凡未分配到所需设备的进程被放入一个等待队列。（2）设备处理。设备处理程序实现CPU和设

备控制器之间的通信。即当CPU向设备控制器发出I/O指令时，设备处理程序应启动设备进行I/O操作，并能对设备发来的中断请求作出及时的响应和处理。（3）实现其他功能。包括对缓冲区的管理功能及实现设备独立性。四、设备管理结构：•1.逻辑I/O：抽象命令、网络协议栈、文件逻辑结构控制•2.设备I

/O：用户命令到设备操作序列转换，I/O缓冲•3.调度和控制：•并发I/O访问调度•设备驱动•设备中断处理用户进程硬件4.2I/O控制方式•程序轮询I/O控制方式•中断I/O控制方式•DMAI/O控制方式•通道I/O控制方式4.3中断技术

1.中断的基本概念：中断是指计算机在执行期间，系统内发生了某一急需处理的事件，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完毕后又返回到刚才暂停程序的被中断处继续执行的过程。中断是操作系统实现并发性的基础之一。以下是需要

打断处理器正常工作的典型事件：•请求系统服务•实现并行工作•处理突发事件•满足实时要求2.中断的分类与优先级中断的分类角度很多，比如，IBM中大型机操作系统，便按照中断事件的性质和激活的手段，将中断分成以下两类：•强迫性中断事件这

不是正在运行的程序所期待的，而是由于某种事故或外部请求信息所引起的，具体分为：机器故障中断事件，程序性中断事件，外部中断事件，输入输出中断事件。•自愿性中断事件这是正在运行的程序所期待的事件。比如，其对操作系统有某种

需求，一旦机器执行到一条访管指令时，便自愿停止现行程序的执行而转入访管中断处理程序处理。而Windows2000/XP则按照中断信号的来源，把中断分为外中断和内中断两类：•外中断(又称中断)指来自处理器和主存之外的中断。包括：电源故障中断、时钟中断、控制台中断、它机中断和I/O中断等

。不同的中断具有不同的中断优先级，处理高一级中断时，往往会屏蔽部分或全部低级中断。•内中断(又称异常)指来自处理器和主存内部的中断。包括：通路校验错、主存奇偶错、非法操作码、地址越界、页面失效、调试指令、

访管中断、算术操作溢出等各种程序性中断。内中断是不能被屏蔽的，一旦出现应立即响应并加以处理。3.中断处理过程（由中断装置和中断服务程序共同完成）：•保护被中断进程的运行现场。即未被硬件保护的一些必需的处理状态，如PSW、PC（或IP）等。•识别各个中断源，分析产生中断的原因。•处理发生

的中断事件。•恢复被中断进程的现场，即恢复正常操作。4.4缓冲技术1.缓冲技术的基本实现思想：在CPU和外设之间设立缓冲区，用以暂存CPU与外设之间交换的数据，从而缓和CPU与外设速度不匹配所产生的矛盾。其实，

凡是数据到达和离去速度不匹配的地方均可采用缓冲技术。例如，CPU与内存之间也需要设置缓冲，只不过设在cache里。2.引入缓冲的目的•(1)改善CPU与I/O设备之间速度不匹配的矛盾•(2)减少对CPU的中断频率，放宽对中断响应时间的限制•(3)提高CPU与I/O设

备之间的并行性3.缓冲的分类及使用•缓冲有硬件缓冲（设备寄存器）和软件缓冲（内存区）之分。后者容量大，使用灵活，又可从不同角度划分成多类。比如，有专用和通用之分，还可根据系统设置的缓冲区个数，将缓冲技术分为：•单缓冲、双缓冲、环形缓冲和缓冲池。•缓冲操作主要由getbuffer

()和putbuffer()过程实现，它们之间有同步约束。4.5设备分配及设备处理程序•设备独立性•设备分配•设备处理1.设备独立性•设备独立性是指用户程序所用设备与物理设备无关的特性，也称设备无关性。为此要求用户程序对I/O设备的

请求不指定特定的设备，而采用逻辑设备名，程序执行时由系统完成逻辑设备到物理设备的映射，这很象程序对逻辑地址的使用。•设备独立性带来的好处1)便于用户使用物理外围设备2)便于系统增减或变更外围设备3)便于实现I/O重定向；易于对付外设故障4)提高了设备分配的灵活性和利用率•设备独立性的实现系统为每个

进程设置一张“逻辑设备表LUT”，记录该进程所用逻辑设备对应的物理设备名和驱动程序入口地址。这是设备分配的一种结果记录，另外，设备分配还要修改全局性的“系统设备表”和“设备控制表”等数据结构。2.设备分配•设备按共享属性可以分成独占

设备、共享设备和虚拟设备三类•相应的管理和分配外围设备的技术可分成：独占方式、共享方式和虚拟方式。•设备分配思想当某进程向系统提出I/O请求时，设备分配程序按一定策略分配设备、控制器和通道，形成一条数据

传输通路，以供主机和设备间信息交换。主要用于多通路系统，有静态分配和动态分配两种策略，而独占设备的分配还要考虑是否采用安全策略，共享设备分配要考虑调度性能。•常用的I/O设备分配算法◆先来先服务◆优先级高者优先•设备请求队列当多进程对同一设备提出I/O请求时，系统响应后，为它们分别建立I/O

请求包，按先来先服务或者优先级高者优先的原则组织成设备请求队列。设备分配程序总是把设备首先分配给队首进程。具体分配是从设备类表或者系统设备表开始顺序查找相应的数据结构进行的，在单通路系统中多采用最先适应法，而在多通路系统中，则采用回溯策略。设备分配采用的数据结构：设备类表和设备表•系统中拥有

一张设备类表，每类设备对应于表中一栏，包括内容有：设备类、总台数、空闲台数、设备驱动程序入口和设备表起始地址等。•每一类设备都有各自的设备表，用来登记这类设备中每一台设备的状态，包含的内容有：物理设备名、逻辑设备名、占有设备

的进程号、已分配/未分配、好/坏等。采用通道结构的系统中设备分配采用的数据结构：系统设备表、通道控制表、控制器控制表和设备控制表•系统建立一张系统设备表，记录配置在系统中的所有物理设备的情况。•每个通道、控制器、设备各设置一张表，记录各自的地址(标识

符)、状态(忙/闲)、等待获得此部件的进程队列指针、及一次分配后相互勾链的指针，以备分配和执行I/O时使用。具体内容如下：•设备控制块DCB（设备控制表DCT）。每个设备一张表，记录本设备的使用情况，表目内容：设备类型、设备标识符、设备状态、与此设备相连的COCT、重复执

行的次数或时间、等待队列的队首和队尾指针•控制器控制块COCB（控制器控制表COCT）•通道控制块CHCB（通道控制表CHCT）•系统设备表SDT。整个系统一张表，记录系统中所有I/O设备的信息，表目包括：设备类型、

设备标识符、设备驱动程序入口、DCT表指针等，是分配程序首先查找的数据结构。3.设备处理——即设备驱动(i)设备驱动程序•系统为每类设备编制设备驱动程序以控制I/O传输•任务：主要负责接收和分析从设备分配转来的信息，把用户I/O请求转换为具体要求后，发送给设备控制器，启动设备执行。•设备

驱动程序的处理过程：(1)将抽象I/O请求转为具体要求(2)检查I/O请求的合法性(3)读出和检查设备的状态(4)传送必要的参数，预置设备的初始状态(5)设置设备的工作方式（在有通道系统中，构造通道程序）(6)启动设备进行I/O操作(7)响应来自设备的中断(ii)I/O中断处理程序•处理来自设备或

通道的正常或异常完成中断准备工作4.6SPOOLing系统•定义：spooling系统是OS中采用的一项可以把独享设备转变成具有共享特征的虚拟设备的技术，也叫假脱机I/O技术，或虚拟设备技术。•SPOOLing全称是SimultaneousPeripheralOperationOnLi

ne,即外围设备同时联机操作。这种早期批处理系统的产物一直沿用至今。读卡机外围机1401磁带磁带磁带外围机主机7094磁带打印机上世纪50年代末批处理系统中，程序和数据的I/O是在外围机的控制下完成的，即在脱离主机的情况下进行，故称为脱机I/O方式。特点是：

手工干预多，时间长。上世纪60年代中期，当进程取代外围机（即不再需要IBM1401，不必再搬动磁带，而且磁盘取代了磁带）后即有了假脱机I/O方式。脱机I/O示意图SPOOLing系统的组成示意图预输入程序作业1信

息…作业n信息输入井作业1结果…作业n结果输出井缓输出程序井管理程序运行作业输入设备输出设备作业调度程序磁盘SPOOLing系统的组成说明•（1）输入井和输出井：•这是在磁盘上开辟出来的两个专用的存储区域。•输入井和输出井分别用于收容从输入设备输入的数据和

用户程序的输出数据。•“井”是用作缓冲的存储区域，采用井的技术能调节供求之间的矛盾，消除人工干预带来的损失。这时的输入井和输出井可分别看作是对读卡机和打印机的虚拟或者模拟。•（2）输入缓冲区和输出缓冲区：•这是供信息在I/O设备和磁盘I/O井之间传送时用的内存缓冲区。•（3）预输入进程

和缓输出进程：•预输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井。当CPU需要输入数据时，直接从输入井读入内存。•缓输出进程模拟脱机输出时的外围控制机，把用户要求输出的数据

，先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备上。假若进程打开了打印机特殊文件后几小时内无所事事，则其他进程什么都打印不了！解决方案：•创建值班进程（daemon）、SPOOLing打印目录•进程首先生

成要打印的文件，放入SPOOLing目录•值班进程：唯一获准使用打印机特殊文件的进程，负责在打印机空闲时打印SPOOLing目录里的文件。•通过禁止用户对特殊文件的直接使用，解决了上述打印机空占问题，提高了其使用效率。SPO

OLing应用举例(1)——打印机的SPOOLing值班（即守护或精灵）进程（daemon）SPOOLing应用举例(2)——网络的SPOOLing值班进程SPOOLing技术今天仍被广泛使用•网络文件传送先把文件送到网络spooling目

录，然后网络值班进程把它取出并传递到目标地址•Internet电子邮件系统在因特网上发Email时，电子邮件发送程序send先将待发信件存入spooling电子邮件目录下，供以后传输。•注意：SPOOLing只提高设备利用率，缩短用户程序执行时间，并不提高CP

U利用率。采用SPOOLing技术的好处•提高了I/O的速度，加快了作业的运行。•将独占设备改造为共享设备，提高了I/O设备的利用率。系统不给进程分配独占设备，只分配输入/输出井和建立I/O请求表。•实现了虚拟设备功能。SPOOLi

ng系统实现了将一台独占设备变换为若干台逻辑设备的功能。4.7磁盘驱动调度•一、磁盘结构硬盘一般分为固定头磁盘和移动头磁盘两大类：固定头磁盘：指盘面上每条磁道都有一个读/写头的磁盘。固定头磁盘各磁头可并行读写，但成本较高，主要用在大型机中。移动头磁盘：指每个盘

面只有一个读/写磁头的磁盘。每次读写须先移动磁头到目标磁道上，这称为寻找（seek）操作。目前，个人计算机中的硬盘（Winchester盘）和软盘都是移动头磁盘。软盘由单盘片组成，硬盘则是个盘片组（因为单一盘片的容量越来越大，故硬盘所含的盘片数

有逐渐减少的趋势）。盘片安装在一个高速旋转的枢轴上。读写头安装在移动臂上，移动臂可沿磁盘半径方向移动。枢轴盘片磁臂磁头磁臂移动方向移动头硬盘结构示意图移动头硬盘驱动器结构及盘片编址示意图柱面扇区磁头磁臂磁道盘面初期IBMPC软盘和当今WesternDigi

tal的WD18300硬盘的磁盘参数磁盘块的物理地址描述——采用三个参数•要在磁盘上访问一个扇区，必须给出其柱面号、磁头号和扇区号，这称为扇区的物理地址，即物理扇区号。由物理扇区号表示的扇区称为绝对扇区。为了方便，操作系统通常

将其转变为连续的逻辑扇区号加以管理。•编址方式为：对整个磁盘从柱面0到最后一个柱面增加，在柱面上按磁道号增加，在磁道上按扇区号增加。•设一块为一扇，则磁盘块号及其物理三地址之间可按以下式子转换:(1)已知块号，则磁盘驱动用的三

地址：柱面号＝[块号/（磁头数×扇区数）]磁头号＝[(块号mod(磁头数×扇区数))/扇区数]扇区号＝(块号mod(磁头数×扇区数))mod扇区数(2)已知磁盘块物理地址，则磁盘块号：块号＝柱面号×(磁头数×扇区数)＋磁头号×扇区数＋扇区号结合文件读写的例子，

上述情况(1)下，磁盘块号是哪里来的？•例4.1设磁盘组共有n个柱面，编号顺序为0、1、2、…、n-1；共有m个磁头，编号顺序为0、1、2、…、m-1；每个磁道内的k个信息块从1开始编号，依次为1、2、…、k。现用x表示逻辑磁盘块号，用a，b，c分别表示任一逻辑磁盘块的柱面号、磁头号、磁道

内块号，则x与a，b，c可通过如下公式进行转换：•x=k*m*a+k*b+c•a=(x-1)DIV(k*m)•b=((x-1)MOD(k*m))DIVk•c=((x-1)MOD(k*m))MODk+1•磁盘访问时

间（=T寻道+T旋转+T传输[平均值=Ts+1/(2r)+b/(rN)]，其中T寻道约占70%）–寻道时间Tseek•把磁臂（磁头）径向移动到指定磁道或柱面上所经历的时间，包含启动磁臂和磁头移动n条磁道或柱面所花费的时间。–旋转延迟时间Tlatency•指定扇区旋转移动

到磁头下面所经历的时间。与盘面的旋转速度有关。•5400rpm平均旋转延迟5.55ms；7200转:4.16ms–传输时间Ttransfer•把数据从磁盘读出或向磁盘写入数据所经历的时间。与旋转速度和一次读写的数据量有关。二、磁盘访问时间•FCFS(FirstComeFirstSer

ved)简单、低效•SSTF(ShortestSeekTimeFirst)有效，但有“饥饿现象”•Scan或Look(即Lift或Elevator)有效，没有“饥饿现象”，但有“磁臂粘着现象”•CScan或C-Look(CircularScan）对Sc

an的变形，磁头“固定周期”单向移动•N-Step-Scan和Fscan可消除“磁臂粘着现象”三、磁盘调度算法ShortestSeekFirst(SSF)diskschedulingalgorithmTheelevatoralgorithmforschedulingdiskre

quests第5章文件管理•文件系统概述•文件的结构和存取方式•文件的使用•文件目录•文件存储空间的管理•文件共享与保护•文件系统的性能问题5.1.1文件的概念1.文件外存中具有符号名的一组有逻辑意义的信息项的集合。2.文件系统指OS中管理文件的那一部分软件。它负责管

理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并为用户提供一整套方便有效的文件使用和操作方法。它在OS接口中占比例最大，是I/O系统的上层软件。文件系统面向用户的主要任务是实现文件的“按名存取”。5.1

.2文件分类•分类角度多。比如，可按文件的用途、文件中数据的形式、存取控制属性、文件信息的保存期限、文件的逻辑结构、文件的物理结构等进行分类。•UNIX系统将文件分为三类:普通文件(包括用户的ASCII或二进制文件)；目录文件；特殊文件（设备文件，管道，套接字，符号链等）

5.1.3~5.1.5文件结构与存取方法文件的结构指文件中信息的配置和构造方式，有逻辑结构和物理结构之分。1.文件的逻辑结构•用户眼中文件信息的组织形式叫文件的逻辑结构。它包括记录式文件和流式文件两种，每种文件信

息的逻辑单位分别是记录和字符。•UNIX系统视所有文件的逻辑结构为无结构的流式文件•早期有结构的记录式文件又分定长和不定长两种，流式文件可看作特殊的定长记录式文件•文件的逻辑结构与文件的存储介质无关2.文件的物理结构•系统眼中文件信息的组织

形式叫文件的物理结构。它包括顺序文件、链接文件、索引文件三种（实为连续文件与不连续文件两大类）•文件的物理结构也叫文件的存储结构，指文件在外存上的存储组织形式，它与存储介质的性能和外存的分配方式有关•顺序文件：文件的信息存放在若干连续的物理块中。特点:实现简单，顺序存取

速度快，但分配慢，外存碎片多（似内存的可重定位可变分区分配）012345678910111213141516171819202122232425262728293031文件名始址块数count02tr143mail1

96list284f62文件目录countftrmaillist磁盘空间连续分配产生顺序文件：磁盘空间•链接文件：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接。特点：提高了磁盘空间利用率,不存在外部碎片问题，有

利于文件长度动态变化，但存取速度慢（不适合随机存取，寻道时间长），可靠性差，指针占空间。•链接文件按链接指针的不同实现又分为隐式链接文件和显式链接文件，MSDOS、Windows中采用的是后者，其FAT和簇的概念是传统链接结构的变形文件名始址末址jeep925文件目

录01234567891011121314151617181920212223242526272829303111016-125磁盘空间链接式分配产生链接文件：磁盘空间•索引文件：一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一

个索引表，并将这些物理块号存放在其中•一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块•索引表组织:单级索引、多级索引、Hash索引。UNIX文件系统采用多级索引结构•特点：既能顺序存取，又能随机存取，支持文件长度动态变化，外存利用率高，但索引表需占额外空间。01234

5678910111213141516171819202122232425262728293031文件名索引表地址文件目录Jeep1991711025-1-1-119磁盘空间索引式分配产生索引文件：文件jeep的单级索引表UNI

XSystemV采用多级混合索引方式索引结点中的13个地址项十个直接地址项三次间接地址块一次间接地址块二次间接块一次间接块一次间接块二次间接块物理块物理块物理块设每个盘块4kB，每个盘块号4B，则采用3次间址可表示的文件最大长度为：4T+4G+4M+40K(B)3.文件的存取方式

当今OS支持的文件存取方式主要有顺序存取和随机存取两种。•顺序存取对文件中的信息按逻辑顺序进行读/写的存取方式称顺序存取•随机存取对文件中的信息按任意顺序进行读/写的存取方式称随机存取•早期系统中记录式文件所对

应的第三种存取方式——按键存取现在多见于DBMS中4.文件的存储介质磁带，磁盘，光盘，优盘，……•以块为单位进行信息的存储、传输、分配•磁带：顺序存取设备，前面的物理块被存取访问之后，才能存取后续的物理块的内容。存取速度较慢，现在主要用于后备存储。•磁盘：可编址的随机存取设备，存取磁盘上任一物理块

的时间不依赖于该物理块所处的位置。•光盘、优盘：可移动磁盘的改进、变形物。文件的存取方式不仅与文件的结构有关，还与文件所在存储介质的性能有关，如下表所示：5.文件结构、文件存取方式与文件存储介质的关系

存储介质物理结构存取方式磁带顺序结构顺序存取磁盘顺序链接索引顺序顺序顺序随机随机问题1：上表内容完全正确吗？问题2：磁盘上的不定长记录式顺序文件适合随机存取吗？5.1.6文件操作•为方便用户使用文件，文件系统提供对文件的各种操作，形式分别

为：系统调用或命令①提供设置和修改用户文件的存取权限的服务②提供建立、修改、改变、删除目录的服务③提供文件共享，设置访问路径的服务④提供创建、打开、读、写、关闭、撤消文件等服务⑤文件系统维护⑥文件系统的转储和恢复⑦……其中，最基本的操作是：打开、关闭、读、写文件等(

1)打开文件操作简介•任何一个文件使用前都要先打开，即把FCB送到内存，以建立用户和文件的联系，使今后频繁的查目录操作在内存中完成。如fd=open(文件路径名,打开方式)•打开文件操作的主要执行步骤如下：①根据文件路径名查目录，找到FCB主部；②根据打开方式、共享说明和用户身份检查访

问合法性；③根据文件号查系统打开文件表，看文件是否已被打开；若是→共享计数加1,否则→将外存中的FCB主部等信息填入系统打开文件表空表项，共享计数置为1；④在用户打开文件表中取一空表项，填写打开方式等

，并指向系统打开文件表对应表项返回信息：fd：文件描述符，是一个非负整数，用于以后读写文件5.2文件目录1.基本概念•文件控制块（FCB）：是OS为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（文件属性），也叫文件目录项•文件控制块是文件

存在的标志•文件控制块的内容：基本信息：文件的名字、地址、大小、结构、类型存取控制信息：文件属主、存取权限或属性或口令使用信息：共享计数，文件的建立、修改日期等•文件目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合•目录项：构成文件目录的项目，即F

CB•目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件•目录主要是为了系统快速实现“按名存取”而引入的，查目录是文件系统最频繁的操作，因此目录的合理组织很重要2.目录结构(1)单级目录结构系统为所有文件建立一个目录文件（线性表）优点：简

单，易实现缺点：•限制了用户对文件的命名（存在“命名冲突”问题）•顺序检索文件时平均检索时间长•限制了对文件的共享•不适于多用户系统(2)二级目录结构•为克服单级目录结构存在的命名冲突问题，并提高对目录文件的检索速度而引入•目录分为两级：一级称为主文件目录

，给出用户名，用户子目录所在的物理位置；二级称为用户文件目录（又称用户子目录），给出该用户所有文件的FCB•优点：解决了文件的重名问题和文件共享问题;可用于多用户系统;顺序查找时间降低。•缺点：增加了系统开销二级目录结构示意图FCB1F

CB2FCB1FCB2(3)多级目录结构（树型目录）•对二级目录简单扩充可得三级或三级以上的多级目录结构，即允许每一级目录中的FCB要么指向文件，要么指向下一级子目录即可。这是当今主流OS普遍采用的目录结构•优点：①解决了命名冲突问题②提高了文件检索

速度③易于实现文件的共享和保护④层次结构清晰，便于对文件分类管理•缺点：查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度UNIX多级树形目录结构示意图tty00／devbinlibetcusrtty01shdateccwhopasswdUNIXfei1myfil

e.cgettyincludefei2testfile.c(4)文件目录改进为加快目录检索可采用目录项分解法，把FCB分成两部分：•符号目录项（次部）文件名，文件号（即基本目录项编号，以实现主次部的链接）•基本目录项（主部）FCB中除文件名外的所有项目•UNIX采用此法，它把符号目

录项称为目录项，而把基本目录项称为I节点（Indexnode，索引节点），这样，目录项中的文件号就是索引节点号(FCB)采用基本文件目录和符号文件目录的多级目录结构示意图(1)基本文件目录变小了的符号文件目录根目录采用

基本文件目录和符号文件目录的多级目录结构示意图(2)基本文件目录(ID1)ID其它属性地址1234567891011文件名IDZhang_San3Li_Si8根目录(ID2)Software4Tools6Products7Rooms5Zhang_San的目录

(ID3)文件名IDZhangSanTools子目录(ID6)SA210Mygame11Li_Si的目录(ID8)Tools5Mygame10Classmate9文件名IDID4ID5ID7ID9ID10ID11例5.1设物理块大小512字节，一个FCB有48个字节，符号目录项占8字节，

文件名6字节，文件号2字节，基本目录项占48-6=42字节。若把含有128个目录项的某单级目录文件改造成符号文件目录和基本文件目录的结构，试说明改造后查找一个文件的平均访盘次数，谈一下自己的认识。解：分解前：1块含512/48=10个FCB分解后：1块含512/8=64个符号目录项，或者，

1块含512/42=12个基本目录项该目录文件含有128个目录项，分解前占13块，分解后其符号文件占2块，基本文件占11块。故分解前查找一个文件的平均访盘次数：(1+13)/2=7次，分解后：(1+2)/2+

1=2.5次由此可见：改造后减少了访问硬盘的次数，提高了检索速度。(5)目录的其他实现方法：•Hash表算法：目录文件按目录项键的Hash值的顺序组织。创建或搜索时根据文件名计算Hash值，得到一个指向目录表中相应表目的指针•其他算法：如B+树,这

是一种将大的单级索引目录文件组织成有序的树型多级索引目录文件的方法，是索引顺序文件中实际采用的基本索引结构，支持随机访问和顺序访问，多见于DBMS中。NTFS文件系统就采用了B+树文件的“按名存取”是通过查目录实现的，系统按照文件的

路径名检索。目录查询技术主要有两种：•线性检索法•Hash方法为加快目录检索，许多系统引入当前目录（工作目录，值班目录）、相对路径名、cd命令等。3.目录查询技术1.分配方式当今OS几乎都采用离散分配方式（似内存分页），以节省外存空间。采用链接分配法导致链接文件，如MSDOS；采用索引

分配法将形成索引文件，如UNIX。UNIX仅对其对换区采用连续分配方式，以加快对换过程。2.分配算法似首次适应法的扩充（即顺序查找分配法）3.分配算法用的主要数据结构（即描述外存空间使用情况的几类不同的数据结构）5.3文件系统的实现一、文件存储空间的管理

(5.3.4)(1)空闲区表/链•将所有空闲区记录在一个表/链中。适合连续分配。如今少用(2)空闲块链•把所有空闲块链成一个链。适合离散分配，今DOS、Windows等用之•扩展：①不断地适度地增加块尺寸。从最

早的512B1KB2KB4KB8KB16KB32KB64KB。FAT16支持的最大簇为32KB，FAT32支持的最大簇为16KB，NTFS支持的最大簇为64KB（请思考FAT12、FAT16与FAT32之间的区别）②成组链接法，链上每个节点记录1组空闲块。适合大型文件系统，分配、释

放快，链本身短，占空间少（除首组外均隐藏在空闲块中）。UNIX用之成组链接法分组原理图——逆序分组，顺序分配成组链接法初始化链的例子：超级块中空闲块号栈50号空块150号空块250号空块395049…12100150149…51

100250249…1511000349…251S.free0138←空闲块数←空闲块号251号空闲块磁盘专用块←→内存专用块(superblock)分配算法（分配1个空块）回收算法（回收1个空块）IF栈已上锁THEN

阻塞ELSE对栈上锁IF栈已上锁THEN阻塞ELSE对栈上锁IF空闲块数＞1THEN{IF空闲块数＜100THEN{空闲块数减1；开锁；将释放块压入S.free(空闲块数)单元;返回S.free(空闲块数)单元的空块；}空闲块数加1；开锁；返回；}IF空

闲块数=1且S.free(0)=0THEN{ELSE{把空闲块栈内容写到释放块中；开锁；失败返回；}ELSE{置空闲块数为1；将S.free(空闲块数-1)单元的空块存入T；将释放块号压入S.free(0)单元；将T号块内容读入专用块；开锁；返回；}开锁；返回T号空块；}采用成组链接

法的外存分配、回收算法：(3)位示图用一串二进制位反映磁盘空间中分配使用情况,每个物理块对应一位,分配物理块为1，否则为0申请物理块时，可以在位示图中查找为0的位，返回对应物理块号；归还时；将对应位转置0描

述能力强，适合各种物理结构（对连续文件稍差），本身占空间少，可常驻内存，而字位号到块号的转换也不难。今Linux等用之（甚至对内存分页方式也用它）二、文件共享的实现(5.3.3)1.文件共享的定义一个文件被多个用户或程序使用共享形式：被多个用户不同时使用，由存取权限控制被多个程序同时使用，但各

用自己的读写指针被多个程序同时使用，但共享读写指针2.文件共享的目的节省时间和存储空间，减少了用户工作量；进程间通过文件交换信息。3.文件共享的实现方法（3种）按“路径名”访问共享文件，即基于系统目录的共享法。实现简

单，但路径名可能长，检索较慢。用连接命令实现基于i-node的共享(硬链接方式)通过“连接（Link）”命令，在用户自己的目录项中对要共享的文件建立起相应的表目，新建目录项中的索引节点号即被共享文件的。解除连接需执行Unlink命令。UNIX提供此法。它是方法1的发展。使用文件别名，检索较

快，也叫静态共享。问题：删除文件时应怎样考虑？用符号链（Symboliclinking）访问共享文件系统建立一个新文件，类型为LINK，放在要连接的目录下。该文件只包含被链接文件的路径名问题：系统时

空开销大优势：适于异地系统间（特别是计算机网络环境下）的文件共享，也没有直接删除文件的副作用。符号链在Windows中叫快捷方式UNIX实例——用户B用连接方式共享用户A的文件FLink(A/F,B/C)（Linux命令为lnA/FB/C）在B目录中建立一个新表目，并在文件F所对应的目

录表目中的“连接数”项加1文件名内部标识号CA/F的内部标识号为支持用户的3种共享形式，UNIX在用户打开文件表和内存索引节点间还引入了系统打开文件表，以解决文件读写指针的存放位置问题，如下图所示。UNIX系统文件共享示例三、

文件系统的一致性(5.3.5)•事务、检查点、并发控制，见DBMS•磁盘块号的一致性检查UNIX一致性检查工作过程：设两张表，每块对应一个表中的计数器，初值为0表一：记录了每块在文件中出现的次数表二：记录了每块在空闲块表中出现的次数对任一块的检查结果01、

10为一致，00为块丢失，02为空块重复，……，检查程序要给予解决6.1安全性概述(1)系统安全性涉及系统保护与保密两个方面，旨在保障系统中数据的完整性、可用性和机密性。但实现起来难度较大，涉及到技术、管理、法律、道德、教育和政治等问题。(2)目前系统安全的分级管理机

制•系统级管理（注册、登录、口令机制）•用户级管理（分类授权）•目录、文件级管理（设权限、属性等）第6章操作系统安全性•人为破坏因素–有意、无意的非法操作–病毒破坏–黑客入侵•自然破坏因素–火灾、水灾、震灾、战争–存储介质等硬、软件损坏6.2影响系统安全性

的因素系统对策授权机制防毒机制+法制教育防黑机制备份、转储、恢复机制硬、软件冗余机制1.授权机制的实现方法一：文件的二级存取控制(UNIX采用)第一级：对访问者的识别对用户分类：–文件主（owner）–文件主的同组用户（group）–其它用户（

other）6.3实现系统安全性的基本技术——几种目前最有效的安全机制简介第二级：对操作权限的识别对操作分类：读操作（r）写操作（w）执行操作（x）不能执行任何操作（-）这样UNIX索引节点中可用9个二进制位rwxrwxrwx对各类用户设访问权限。

文件主人可改之，如chmod755file2方法二:存取控制矩阵（早期OS用）文件用户ABCUser1rwrwUser2e2.具体的备份、转储与恢复机制通过转储操作，可形成文件或文件系统的多个副本–备份有本地、异地、热、冷备份之分–转储有全量转储、增量转储两种–恢复

有全量恢复、增量恢复两种3.文件保密机制（主动做法）•口令机制（常结合DES等加密法使用）•隐藏法•加密解密机制–RSA体制（1978，MIT，Rivest、Shamir和Adleman创建，2002TuringAward），已被ISO推荐为公开密钥数据加

密标准。它是建立在数论中的大整数分解质因子的基础上的–数字签名（RSA的应用）著名的单向hash算法——fordatasignature(数字签名)MD5（Message-DigestAlgorith

m5消息-摘要算法，1991,MITLaboratoryforComputerScienceandRSADataSecurityInc’RonaldL.Rivest.Itcantransformalongs

tringofmessageintoa128-bitdigest.SHA-1（SafeHashalgorithm安全散列算法.Itoutputsa20-bytestring.NIST(美国国家标准技术研究院）,1994Wangxiaoyun，王小云,山

东大学数学与系统科学学院密码技术与信息安全实验室主任、清华大学“长江学者奖励计划”特聘教授–2004.8crackedMD5,foundoutthehashcollisions–2005.2crackedSHA-1theoretically–碰撞＝漏洞＝别人可以伪造和冒用数字签名职

业道德与法制建设随着互连网的发展，病毒与黑客对系统和用户的攻击日益猖獗，现有系统的安全对策显得很脆弱，因此，加强计算机从业人员的职业道德教育和防范计算机犯罪的法律建设成了当务之急！！