计算机操作系统

计算机操作系统 操作系统概述 处理机管理 存储管理 文件管理 设备管理 作业管理 进程管理 操作系统设计

操作系统试验 安装windows 2000(课后完成） Windows2000任务管理器的进程管理

基本要求 掌握基本原理 熟悉常用主要功能特点 了解操作系统设计思想与结构

学习方法 知识：需要记忆、积累 联想、对比 抓重点 技能：需要训练、经验 方法、技巧 抓特点 思路：逻辑思维 形象思维

操作系统知识体系结构 知识结构： 知识面： 至少记住以下两句话： 知识点： 操作系统是计算机技术与管理技术的结合 知识面： 至少记住以下两句话： .操作系统是方便用户，管理和控制整个计算机软硬件资源的程序系统（系统软件） .操作系统有“五大类型”和“五大功能” （批处理，分时，实时，网络，分布； 作业，文件，存储，设备和进程管理） 知识点： “五大类型”和“五大功能” 的基本知识和应用技能

计算机操作系统是计算机技术和管理技术的结合。 管理技术：1. 分门别类 2. 详细记录 3. 调度策略

数据结构 (堆)栈 Stack 队(列) Queue 表(格) Table 树(型) Tree 图(论) Graphic、Chart、Map、Picture、Drawing 场(论) Field

第一章 操作系统引论 操作系统的概念 操作系统的生成和五大类型 操作系统的五大功能 表征操作系统的属性

操作系统的概念(1) 操作系统的英文名是Operating System，缩写成OS 操作系统是一种软件，属于系统软件 从用户角度看，操作系统可以看成是计算机的硬件扩充 人机交互方式来看，操作系统是用户与机器的接口 用管理者角度看，操作系统也是管理资源的程序扩充

操作系统的概念(2) 从计算机的系统结构看，操作系统是一种层次、模块结构的程序集合，属于有序分层法，是无序模块的有序层次调用。 操作系统是计算机技术和管理技术的结合 操作系统相当于计算机系统的“管理机构”。操作系统是为计算机用户服务，它的主人就是用户。 OS是方便用户管理和控制计算机软硬件资源的系统软件或程序集合

操作系统的生成和类型 生成：产生最适合自己工作环境的os内核（kernel）。为了方便用户，又使系统开销尽量小 生成，配置过程： UNIX中 newconfig 命令 DOS中 config.sys 文件 维护：系统管理员 我们 有则后 知道愤怒

操作系统形成的历史(1) 1946年—50年代末 50年代后期 当时计算机处于电子管时代，根本没有操作系统。人们把这个时期称为“手工操作阶段”。顾名思义人们当时使用的计算机大量需要人工控制，还没有“管家”来为他们服务。 50年代后期 计算机的运行速度有了很大的提高，从每秒几千次、几万次发展到每秒几十万次、上百万次。

操作系统形成的历史（2） 50年代末—60年代中期 联机批处理系统 脱机批处理系统 执行系统 此时计算机进入了第二代——晶体管时代。为了解决人机矛盾，提高自动化程度，

操作系统形成的历史（3） 60年代中期——70年代中期 人们研制了监督程序，由该程序自动依次处理一系列任务 计算机进入第三代——集成电路时代。在这一时期操作系统初步形成并完善。 出现了三种最基本的操作系统类型：多道批处理操作系统、分时操作系统和实时操作系统。

操作系统形成的历史(4) 80年代至今 第四代计算机，大规模集成电路工艺技术飞速发展。操作系统也有了进一步发展：出现了个人计算机上的操作系统、网络操作系统和分布式操作系统。

操作系统的类型 五大类型： （单道批处理系统 、多道程序设计技术、 多道批处理操作系统） 批处理操作系统 分时操作系统 实时操作系统 （单道批处理系统 、多道程序设计技术、 多道批处理操作系统） 分时操作系统 实时操作系统 网络操作系统 分布式操作系统

多通道批处理操作系统 单道运行：每次只调一个用户程序进入内存让它运行 多道程序设计：即在系统内（内存）同时存放并运行几道相互独立的程序。 多道程序设计的基础：是将运行过程进一步细化成几个小的步骤，从而实现宏观上的并行。但从微观上看，内存中的多道程序轮流地或分时地占用处理机，交替执行。

多道程序系统 ≠ 多重处理系统 ≠ 多用户 ≠ 多终端 多道是指内存中驻留多个程序或一个程序的多个程序段，因此，多用户系统一定是采用多道技术。而多道系统不一定是多用户系统。多重处理系统一般指多CPU系统。当然，一个CPU的系统采用分时技术可以为多用户服务。多用户的关键技术是在用户之间要有保密保安措施。终端指用户使用的硬件设备，即使一个终端也可为多用户用，例如，银行的自动取款机(ATM)。 纯码 = 可重入代码

分时 实时 分时技术：把CPU的时间分成很短的时间片（例如，几十至几百毫秒）工作 分时 实时 分时技术：把CPU的时间分成很短的时间片（例如，几十至几百毫秒）工作 随着时间片的时间减少，对换时间所占的比例随之增大。随着用户数目的不断增加，这种矛盾会越来越突出 特点是计算机规定特点是人（用户） 实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内作出快速反应 交互作用能力较差 特点是人（用户）规定计算机

操作系统的五大功能(1) 作业管理 文件管理 存储管理 包括任务管理、 界面管理、人机交互、形界面、语音控制和虚拟现实等 又称为信息管理 实质是对存储“空间”的管理，主要指对内存的管理

操作系统的五大功能(2) 设备管理 进程管理 实质是对硬件设备的管理，其中包括对输入输出设备的分配、启动、完成和回收 又称外理机管理，实质上是对处理机执行“时间”的管理，即如何将CPU真正合理地分配给每个任务

表征操作系统的属性(1) 响应比，响应系数：Rp = 作业响应时间/运行时间（估计值） 影响因素:CPU速度，内外存对换，I/O调度，用户数，时间片，事件优先权等

表征操作系统的属性(2) 并发性也叫“共行性”（concurrent）, 表现在： 信息的共享、保密与保护,常见方法有： 多个作业并发执行或一个用户作业的多个程序段间并发执行 多个输入输出设备间并发工作 信息的共享、保密与保护,常见方法有： 给用户设置登录口令 给文件加权限 给文件加密

表征操作系统的属性(3) 可扩充性、可移植性、可读性、可“生成”性 安全可靠性 “行业评测性能比较”法 “可扩充性”表示该操作系统可灵活地按照用户的需要增加功能 “可读性”和“可移植性”均表现操作系统的适应性 安全可靠性 “行业评测性能比较”法

表征操作系统的属性(4) 可测试性 测试程序（Benchmark）有： 中央处理单元（CPU）：每秒百万条指令MIPS 事件（Event）：每秒处理事务数TPS MIPS是指CPU速度，对于数学运算的应用项目有重要意义。但对于一般的数据处理，涉及输入输出的动作较多，TPS测试更为切合实际。

第三章 处理机管理 第一节 多道程序设计 第二节 进程的定义和特征 第三节 中断与中断系统 第四节 处理机调度

多道程序 通过增加资源使用者的数量，提高系统资源利用率 单道程序 设备、内存、处理机资源利用率低 资源竞争

多道程序设计的问题 处理机资源 分配与调度 内存资源 内存空间划分，重定位，存储保护 设备资源 分配与去配

为什么要引入“进程”的概念 关键是“共享资源”引起的 如何描述多道系统中程序的执行

顺序执行与并发执行的区别 顺序执行: 并发执行： 程序具有封闭性 程序失去封闭性 独享资源 共享资源(互为存在条件) 顺序执行: 并发执行： 程序具有封闭性 程序失去封闭性 独享资源 共享资源(互为存在条件) 可再现性 程序与“计算”不再一一对应 有相互制约

进程的定义及特征 进程:进程是程序在数据集合上的一次运行过程，是OS 动态系统进行资源分配和调度的基本单元（构件）。 程序和进程的区别 进程的基本特征

程序和进程的区别 程序 进程 多个进程 一个程序在工作 ●静态的指令序列 ●动态的程序执行过程 ●一程序可对应 ●一个进程对应至少有 程序 进程 ●静态的指令序列 ●动态的程序执行过程 ●一程序可对应 ●一个进程对应至少有 多个进程 一个程序在工作 ●永久性软件资源 ●暂存资源,动态生之过程

进程的基本特征 动态性：进程是程序在并发系统内的一次执行，一个进程有一个从产生到消失的生命期； 并发性：正是为了描述程序在并发系统内执行的动态特性才引入了进程，没有并发就没有进程； 独立性：每个进程的程序都是相对独立的顺序程序，可以按照自己的方向和速度独立地向前推进； 制约性：进程之间的相互制约，主要表现在互斥地使用资源和相关进程之间必要的同步和通讯； 结构性：进程 = PCB + 程序 + 数据集合。 异步性：每个进程按其各自独立的不可预知的速度向前推进。

进程的组成 进程对应的程序:进程的算法描述 数据集合:数据部分,工作区 进程控制表（PCB）:是操作系统对CPU进行控制的依据 Pid,进程状态，调度参数，进程位置和大小，家族联系，队列指针等

进程的三个基本状态及转换 等待 得到资源 资源不足 就绪 完成 提交进入 执行 时间片到 调度选中进入

等待 静止 阻塞 活动 阻塞 得到资源 资源不足 准备 完成 提交进入 时间片到 执行 活动 就绪 静止 就绪 调度选中进入

进程的状态及转换 执行 完成 页面阻塞 I/O阻塞 盘带阻塞 得到资源 资源不足 时间片到 提交进入 调度选中进入 队列：高优先级队列：中优先级队列：低优先级 时间片到 完成 提交进入 执行 调度选中进入

处理机调度算法 先来先服务(FCFS) 优先数法(Priority) 时间片轮转,轮转循环调度(Round Robin)分时系统 方法：静态优先数，动态优先数 不可抢占CPUCPU，可抢占cpu 时间片轮转,轮转循环调度(Round Robin)分时系统 分类排队法Multi Level Queues 反馈排队法Feed Back

处理机状态及其转换 管态 目态 目态到管态 中断 管态到目态 修改程序状态字

中断 在程序的运行 过程中，出现了某种紧急事件，使得CPU必须中止正在运行的程序，转去处理此事件，然后再恢复原来运行的程序，这一过程称为中断。

相关概念 中断系统 中断装置 识别中断源，保护现场，引出中断程序 中断处理程序 中断源 中断寄存器，中断字 中断向量

中断类型（按中断源分） I/O中断 系统请求中断/访管中断 报警中断 程序中断 时钟中断 机器故障中断 内部中断 外部中断

中断向量 为处理上的方便，对不同的中断源编制不同的中断处理程序，这些处理程序的入口地址(PC)放在特定的单元。此外，不同中断处理程序有不同的处理机状态字PSW，它放在与中断处理程序入口指针相邻的单元中。有了这两个单元的内容，便可转入相应的中断处理相应的cpu状态字）称为中断向量，把存放中断向量的单元称为中断向量单元。

中断优先级与中断嵌套 根据引起中断事件事件的重要性和紧迫程度，硬件将中断源分为若干级别，称作中断优先级。 如果系统在处理一个中断的过程中又响应了新的中断，则称发生了中断嵌套。 中断嵌套的实际层次一般不会超过中断优先级别的个数。

中断处理过程图3-13 进入中断：响应中断时，CPU撤回对总线的控制权，暂停对现行程序的运行 保护现场信息（PSW,PC等 ） 判断中断源 系统堆栈 判断中断源 中断处理 恢复现场

中断程序处理方案 输入输出中断的处理 时钟中断：一类特殊的I/o中断，不一定与具体的I/o相连，每一次中断意味着一个固时间已到。 控制台中断：相当于一个操作命令 硬件故障中断：保护现场，报告故障信息 程序中断：由程序异常引起，如除数为0，浮点运算溢出，存储器使用无效，地址越界，目态下使用特权指令，错误格式化等

中断程序处理方案 访管中断（自愿性中断）：由访管指令产生的向操作系统提出服务请求的中断，该中断由系统调用命令引出，如trap, SVC或INT等访管指令产生的中断。该中断将命令传给操作系统，操作系统对请求做出分析并提供所需服务。

第四章 存储管理 第一节 存储管理的功能 第二节 内存资源管理 第三节 存储管理方式 第四节 外存管理技术 第五节 虚拟存储系统

第五章 文件管理 文件与文件系统 文件的访问形式 文件的组织 文件目录 文件的共享 文件系统的保护、保密与安全 文件系统的实现 文件系统的界面

引言 在早期计算机系统中，人们直接用物理地址存放信息。存放信息时，要求用户指出并记住信息存放在哪个设备的哪些磁道、哪些扇区上。 在多用户的环境中这几乎是不可能的，更是不能忍受的。

实际上对用户来说，关心的不是信息的具体存放位置，而是存取方法的方便、可靠。不是信息的物理结构而是信息的逻辑结构。 因此，引入文件和文件系统的概念，它是操作系统的重要组成部分。

1、文件的定义 文件是计算机系统中信息存放的一种组织形式，目前尚无严格的定义，下面给出两种有代表性的解释: 文件是赋名的信息 (数据)项的集合。 文件是赋名有关联的信息单位 (记录)的集合。 信息项 ……... 编号：0 1 …… i …… n-1 读写指针

这两种解释定义了两种文件形式： 前者说明文件是由字节组成，这是一种无结构的文件，或称流式文件。目前UNIX操作系统，MS-DOS系统均采用这种文件形式。 后者说明文件是由记录组成。而记录则是由一组相关信息项组成。例如每个学生的登记表可视为一个记录，它包括学生姓名，出生年月，性别，籍贯等信息项。所有学生登记表组成一个学生文件。

文件分类 按文件所有者分类 按保存期限分类 按访问方式分类 按设备类型分类(UNIX或Linux操作系统) 按用途分类 按文件的内容分类 按逻辑结构分类 按物理结构分类

按所有者分类 系统文件: 指用操作系统的执行程序和数据组成的文件，这种文件不对用户开放，仅供系统使用。 库文件：是指系统为用户提供的各种标准函数，标准过程和实用程序等。用户只能使用这些文件，而无权对其进行修改。 用户文件: 由用户的信息组成的文件，如源程序文件，数据文件等。这种文件的使用和修改权均属于用户。

按保存期限分类 临时文件：用于系统在工作过程中产生的中间文件，一般有暂存的目录，正常工作情况下，工作完毕会自动删除，一旦有异常情况往往会残留不少临时文件 永久文件: 指一般受系统管理的各种系统和用户文件，经过安装或编辑、编译生成的文件，存放在软盘、硬盘或光盘等外存上

按访问方式分类 只读文件：只允许文件主及被核准的用户去读文件，而不允许写文件。 只写文件：只允许文件主及被核准的用户去写文件，而不允许其他操作。 可读可写文件：允许文件主及被核准的用户去读和写文件。 可执行文件：允许文件主及被核准的用户去调用执行该文件而不允许读和写文件

（3）按文件的性质分类 普通文件: 指一般的用户文件和系统文件。 目录文件: 指由文件目录项组成的文件。 特别文件: 有的系统把设备作为文件统一管理和使用，并为区别起见，把设备称为特别文件。 UNIX操作系统把文件分成普通文件、目录文件和特别文件。

按设备类型分类 磁盘文件 磁带文件 磁鼓文件

按用途分类 普通文件(常规文件) 目录文件 特殊文件（设备驱动程序） 是指系统中最一般组织格式的文件，一般是字符流组成的无结构文件 是由文件的目录信息构成的特殊文件，操作系统将目录也做成文件，便于统一管理 特殊文件（设备驱动程序） 将输入输出外部设备被看作特殊文件便于统一管理

按文件内容分类 程序文件 源文件 目标文件 可执行文件 头文件 库文件 数据文件

按存取的物理结构分类(1) 顺序（连续）文件 链接文件 文件中的纪录，顺序地存储到连续的物理盘块中，顺序文件中所记录的次序，与它们存储在物理介质上存放的次序是一致的 链接文件 文件中的纪录可存储在并不相邻接的各个物理块中，通过物理块中的链接指针组成一个链表管理，形成一个完整的文件,又称指针串连文件或直接存取文件

按存取的物理结构分类(2) 索引文件 文件中的纪录可存储在并不相邻接的各个物理块中，纪录和物理块之间通过索引表项按关键字存取文件，通过物理块中的索引表管理，形成一个完整的文件

按文件的逻辑存储结构分类 流式/无结构文件 记录式/有结构文件 这是直接由字符序列所构成的文件，故又祢为流式文件 由若干个记录所构成的文件，故又称为记录式文件

文件 文件是软件机构，软件资源的管理方式 具有符号名的一组相关元素的有序序列，是一段程序或数据的集合 一组赋名的相关联字符流的集合，或者是相关联记录。而记录是有意义的信息集合

文件系统 文件系统负责文件的创立、撤消、读写、修改、复制和存取控制等，并管理存放文件的各种资源。 文件系统包含文件管理程序（文件与目录的集合）和所管理的全部文件 是用户与外存的接口 系统软件为用户提供统一方法（以数据记录的逻辑单位），访问存储在物理介质上的信息 文件系统=文件管理程序（文件和目录的集合）+它所管理的全部文件 文件系统负责文件的创立、撤消、读写、修改、复制和存取控制等，并管理存放文件的各种资源。

文件系统特点 使用方便，灵活，用户按名存取 安全可靠， 保护系统和用户 提供保密与共享

文件的访问方式 顺序访问 文件存取最简单的方法是顺序存取，即严格按文件信息单位排列的顺序依次存取。 当打开文件时，文件的存取指针指向第一个信息单位，如第一个字节或第一个记录，每存取一个信息单位存取指针加1指向下一个信息单位，如此类推。

随机访问 也称直接存取，每次存取操作时必须先确定存取的位置。 对流式文件或定长记录的文件比较容易确定存取位置。 对不定长的记录式文件比较麻烦。当然可从第一个记录开始顺序查询，直到找到要存取的记录为止，显然这样做是低效的。 解决的方法是建立索引。文件的索引可以作为文件的一部分，也可以单独建立索引文件。

文件的访问方式 顺序访问方式 由文件头部开始顺序访问 由文件中间开始顺序访问 随机访问方式 按信息项编号随机访问 按键随机访问

文件的组织 文件的逻辑组织 流式文件 记录式文件 文件的物理组织 顺序结构 链接结构 索引结构 Hash结构 倒排结构

文件的逻辑结构 1、文件的逻辑结构 流式文件：基本信息单位是字节或字，其长度是所含字节的数量。 这种文件的优点是节省存储空间。 在这种文件中无需额外的说明和控制信息。

记录式文件：记录式文件是一种结构文件。由若干个记录组成，文件中的记录可按顺序编号为记录1，记录2，……，记录n。 如果文件中所有记录的长度相等，则称为定长记录文件，文件的长度为记录个数与记录长度的积。 若文件中的记录长度不相等，则称为变长记录文件。文件长度为所有记录长度之和。

相对流式文件而言，记录式文件的使用不很方便，尤其是变长记录文件。另外在文件中还要有说明记录长度的信息，这就浪费了一部分存储空间。 因此许多现代计算机操作系统如UNIX操作系统等都取消了记录式文件。

流式文件 记录式文件 流式文件是记录式文件的特例 非结构式的 具有符号名的字节序列 Os对外部结构无解释 结构式的 具有符号名的记录序列 流式文件 记录式文件 非结构式的 具有符号名的字节序列 Os对外部结构无解释 结构式的 具有符号名的记录序列 Os对外部结构有解释 流式文件是记录式文件的特例

文件的物理结构 文件的物理结构是指文件在物理存储介质上的结构。 1、连续结构 2、链接结构 3、索引结构 4、HASH结构 5、倒排结构

1、顺序结构 一个文件的全部信息存放在外存的一片连续编号的物理块中，这种结构称为连续结构，或称连续文件。 存放在磁带上的文件一般采用连续结构，即序号为I+1的物理块一定在i物理块之后。而存放在磁盘上的文件则可采用连续结构，也可采用别的结构。 建立连续文件时要求用户给出文件的最大长度，以便系统为文件分配足够的存储空间，并在相应表格中登记文件的起始位置和长度。

优点 简单 支持顺序存取和随机存取 顺序存取速度快 所需的磁盘寻道次数和寻道时间最少

缺点 文件不易动态增长 预留空间:浪费 重新分配和移动 不利于文件插入和删除 存储压缩技术

2、链接结构 这是一种非连续的结构，存放文件信息的每一物理块中有一个指针，指向下一个物理块，这个指针的长度由物理设备的容量决定，通常放在该物理块的开头或结尾。

链接结构的文件适用于顺序存取。因为要获得某一块的块号，必须读取上一物理块，因此要随机地存取信息就较为困难。

优缺点 优点： 提高了磁盘空间利用率,不存在外部碎片问题 有利于文件插入和删除 有利于文件动态扩充 缺点： 存取速度慢，不适于随机存取 链接指针占用一定的空间 可靠性问题，如指针出错

3、索引结构 一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在索引表中。 一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块

直接索引 一次间接 二次间接 三次间接 … 9 10 11 12 255

优点 缺点 保持了链接结构的优点，又解决了其缺点： 即能顺序存取，又能随机存取 满足了文件动态增长、插入删除的要求 能充分利用外存空间 索引表本身带来了系统开销 如：内外存空间，存取时间

思考题 设一个文件由100个物理块构成，对于顺序，链接和索引存储方式，分别计算执行下列操作时所应启动的I/o次数。（链接方式使用的是单向指针，但没有头、尾指针） 1.将一块加在文件的开头 2. 将一块加在文件的中间 3. 将一块加在文件的末尾 4 .从文件的开头去掉一块 5 .从文件的中间去掉一块 。6 .从文件的末尾去掉一块

文件目录 文件目录是文件系统中主要数据结构之一,文件存储后用户通过用户文件逻辑结构的索引链接找到对应的物理结构 文件目录由目录项构成，目录项又称为文件控制块FCB 文件控制块FCB是文件存在的标志，记录着系统对文件进行管理所需要的全部信息。

文件目录分类 单级目录 一个磁盘一个目录，一个文件一个说明表目 优点是简单，缺点是无法防止重名或被刪，安全保密性差，目前已淘汰

二级目录结构 二级文件目录结构把目录分成系统目录和用户目录两级。 系统目录由用户名和用户文件目录首地址组成，用户文件目录中登记相应的用户文件的目录项。

在二级目录结构中，区别不同的文件除文件名外还有文件的用户名，因此不同的用户可以使用相同的文件名。 例如用户A中使用文件名LISH，用户B也可使用文件名LISH，因为标识这两个文件时还要加上用户名，A：LISH和B：LISH，不致于造成混淆。  

优缺点 优点：二级目录结构较为简单，也比较好地解决了重名的问题。 缺点：缺乏灵活性，特别是不能反映现实世界中多层次的关系。   为此人们提出了多级目录结构，其中MULTICS及UNIX系统均采用了多级目录结构，它们是当前文件系统的典型而完美的代表。

多级目录结构 多级目录结构由根目录和各级目录组成，为管理上的方便，除根目录外，其它各级目录均以文件的形式组成目录文件。 根目录中的每个目录项可以对应一个目录文件，也可以对应一个数据文件，同样目录文件中的每个目录项可以对应一个目录文件。也可以对应一个数据文件。如此类推，就形成多级目录结构。 也称树形目录结构

在这种结构中把根目录称为根结点，把各级目录文件称中间结点，用方框表示。数据文件称为叶结点，用圆圈表示。

路径名 在多级目录结构中一个文件的唯一标识不再是文件名，而是从根结点开始，经过一个或多个中间结点，到达某个叶结点的一条路径。称这条路径为文件的路径名，它是文件的唯一标识。 路径名由根目录和所经过的目录名和文件名以及分隔符组成，通常使用分隔符 /。例如/d1/f1， /d2/d5/f3， /f7  

工作目录 在多级目录结构中，文件路径名一般较长，而用户总是局部地使用文件，为了方便起见，可把经常使用的文件所在的目录指定为工作目录(或称当前目录)。 查询时，若路径名以/开头；则从根目录开始查找，否则从当前目录开始查找。

文件目录改进 为加快目录检索把FCB分成两部分： 符号目录项 (次部） 文件名，文件号 基本目录项(主部） 除文件名外的所有项目

文件的共享 所谓文件共享指系统允许多个用户或进程共享同一份文件。 在系统中只需要保存共享文件的一个副本。 如果系统不能提供文件共享功能，就意味着凡是需要该文件的用户都要自备此文件的副本。

文件共享的目的 节省存储空间 进程间通过文件交换信息

链接技术实现文件共享 从一个目录项直接用一个指针（或编号）指向另一个目录项达到共享文件的目的。 这里需要扩充目录项，增加：用户计数。用于记录共享数量。 硬链接

利用符号链实现文件共享 用户A为了共享用户B的Bboot目录下的一个文件f1.c，可以创建一个LINK类型的新文件x，新文件x中仅包含被链接文件f1.c的路径名。A用户对新文件x的访问被系统重定位去访问B的文件f1.c。 软链接

优势：计算机网络环境下可用 问题：系统开销大

文件的保护、保密与安全 文件的保护 存取控制矩阵，访问权限说明，分级目录 文件的保密 口令，密码 文件的安全 备份

用访问控制矩阵实现文件保护 一维代表所有用户，一维代表系统中的所有文件。 优点：一目了然 缺点：矩阵往往过大。

对访问权限分类 对文件的访问系统首先要检查访问权限，只允许合法的用户访问。文件的存取权限一般有以下几种: 仅允许读 (R)。 仅允许写 (W) 仅允许执行 (E)。 仅允许对文件进行修改（M） 允许删除文件（D） 这几种权限可进行适当的组合。

访问权限说明 对用户进行分类 按用户对文件访问权力的差别把用户分成几类，然后对每个文件规定各类用户的存取权限。通常将用户分成三类: 文件主 文件主的同组用户或合作用户 其它用户

存取控制表实现文件保护

用户权限表实现文件保护

分级目录 在多级目录系统中，可规定不同用户对于统一子目录的访问权限。

文件的保密 口令 密码

用口令实现文件保护 用户为自己的每个文件规定一个口令，有口令者才能访问文件。 优点：简便 缺点： 保护级别少（可访问和不可访问） 保密性差。   优点：简便 缺点： 保护级别少（可访问和不可访问） 保密性差。 不易改变存取控制权限。

使用口令 使用口令优点是占存储空间少、方便，缺点是保护能力弱 口令应选择包含有大小写字母，甚至包含控制字符 口令至少有八位字长 不要使用陈旧的口令，而且口令应经常变化

使用密码 存储时用“密钥” （“密码钥匙”）对文件进行编码，取时译码 优点是保密性强

文件的安全 文件的安全性是指抵抗和预防各种物理性破坏及认为性破坏的能力。 备份 海量转储 增量转储

文件系统的实现 系统打开文件表 2 Fd mode p* 入口 …… 用户打开文件表（p1) …… Fd mode p* 入口 …… FCB主部 文件号 共享计数 修改标志 2 …… 系统打开文件表 Fd mode p* 入口 用户打开文件表（p2) ……

外存空间的管理 空闲块表 空闲块链 字位映像图 首空闲块号和空闲块数 字位映像图需要永久地保存于外存空间 使用时将其调入内存 修改后内存写回内存

文件系统的界面 建立文件 打开文件 关闭文件 指针定位 create (path-name,FCB-args) Fd=open（path-name,mode） 关闭文件 Close(fd) 指针定位 Seek(fd,offset)

读文件 写文件 建立链接 断开链接 Read(fd,nrcd,buf) Write(fd,nrcd,buf) Link(old-name,new-name) 断开链接 Unlink(path-name)

存储管理的目的及功能（1） 目的：方便用户，使用户减少甚至摆脱对存储器使用的管理；提高内存资源的利用率，关键是实现内存共享 功能： 内存分配：通过建表、查表、改表和回收登录内存使用情况，按选定分配算法确定分区等

存储管理的目的及功能（2） 功能： 存储共享：节省内存空间，实现进程通信 内存保护技术：防止地址越界，防止操作越权 内存的扩充技术：使用虛存或自动复盖技朮提供比实际内存更大的空间 地址映射

逻辑地址与物理地址 在具有地址变換机构的计算机中，允许程序中编排的地址和信息实际存放在内存中的地址有所不同。前者叫逻辑（相对）地址，后者叫物理（绝对）地址。 地址映射：将程序所产生的逻辑地址转换为存储空间的物理地址。

内存资源管理 内存分区 内存分配 碎片处理

内存资源管理 静态不等长分区 静态等长分区 动态异长分区

静态不等长分区 分区：系统运行前，将逐村划分成大小不等的若干区域，每个分区的大小可以预先确定，但系统开启后就不能再改变了。 管理：每个注册的作业必须规定其最大存储量，不得超过最大分区的大小。 分配：系统设置一张分区表，标明每块分区的大小位置 和使用状态，分区表按照分区从小到大顺序排列。分配时， 从说明的第一项开始依次查看每个分区的转台状态及大小， 当状态可用，且其大小超过作业大小时，便可分配。

静态等长分配（分页） 存储空间被静态地划分为若干个长度相等的区域，每个区域称为一页。 字位影像图 空闲页面表/空闲页面链

动态异长分区 存储空间被动态地划分为若干个长度不等的区域 分配算法 最先适应算法FF(First Fit) 最佳适应算法BF(Best Fit) 最坏适应算法WF(Worst Fit)

碎片处理 碎片 紧凑 紧凑的开销 修改被移动进程的地址信息 复制进程空间 实验：开始/程序/附件/系统工具/磁盘碎片整理

内存资源管理实例1 有一个系统，其内存容量为1024KB，有8个作业同时到达，各作业的内存量及运行时间如下表所示，假定系统初启时，将内存1024KB按作业的编号顺序分给各道作业，并假定是多CPU下，分配到内存的作业都可以立即运行，问： 1S后，内存空白区按FF和Bf算法的方式将如何链接? 2S后，内存空白区按上述两种算法的方式又将如何链接? 这时（ 2S后），有作业9要求进入内存，它需要12KB内存量，按上述方法，系统将哪一块空白区分给它？

作业编号 需要内存量（KB） 运行时间（s） 1 140 3 2 80 100 4 60 5 50 6 30 7 15 8 20

内存资源管理实例2 某计算机系统的内存容量为128KB，对存储器采用可变分区管理办法，现有3个作业J1,J2,J3在内存，其存储区间的分配如图所示： 现有一个需要25KB存储空间的作业J4请求装入内存， (1)若采用FF分配算法，请给出装入J4后的内存分配表；(2)若采用BF分配算法，请给出装入J4后的内存分配表；(3)在只有J1,J2,J3三个作业的情况下,J2运行结束后撤离，请给出J2撤离后的内存分配表

操作系统 J1 空闲区 J2 空闲区 J3 空闲区 0K 5K 20K 40K 50K 90K 100K 128K

内存“扩充”技术 交换（swap)：由操作系统做，用户不知道。 复盖（overlay)：由用户控制，操作系统提供覆盖机制。

存储管理方式 界地址存储管理 页式存储管理 段式存储管理 段页式存储管理

界地址存储管理 内存空间：动态地划分为若干个长度不同的区域 进程空间：由一个连续的区间构成，0~L-1 地址映射：设内存中的起始地址为b 内存分配表/空闲区域表 首址寄存器/限长寄存器 物理地址=逻辑地址+首址寄存器内容

双对界 交换技术swapping Roll-in,Roll-out

页式存储管理实现原理 基于程序在运行时不需要一开始都装入内存，更不应该把最近较长一段时间内不用的程序装入内存。 内存空间：静态地划分为若干等长的页面 物理地址=物理页首址+页内地址 进程空间：静态地划分为若干等长的逻辑页 逻辑地址=逻辑页首址+页内地址 页表/进程表/总页表 页表首址寄存器/页表长度寄存器/快表 地址映射p66,图4-15

分页式管理应用实例1 一个由4个页号（页号0~3），每页由1024个字节组成的程序，把它装入一个由8个物理块（块号为0~7）组成的存储器中，装入情况如下表所示，已知下面的逻辑地址[0，100]，[1，179]，[2，785]，[3，1010]（第一个元素为页号，第二个元素为页内地址），请按页表求出对应的物理地址

逻辑页号 内存块号 3 1 5 2 6

页式存储管理的优点 虛存量大，适合多道程序运行，用户不必担心内存不够的调度操作。 内存利用率高，不常用的页面尽量不留在内存； 不要求作业连续存放，有效地解决了“碎片”问题。与分区式比，不需移动作业；与多重分区比，无零星碎片产生.

页式存储管理的缺点 要处理页面中断、缺页中断处理等，系统开销较大； 有可能产生“抖动”; 地址变換机构复杂，为提高速度采用硬件实现，增加了机器成本

分段式存储管理 内存空间：动态地划分为若干不等长的物理段 进程空间：静态地划分为若干不等长的逻辑段 段表/进程表/空闲表 物理地址=段首址+段内地址 进程空间：静态地划分为若干不等长的逻辑段 逻辑地址=段号+段内地址 段表/进程表/空闲表 段表首址寄存器/段表长度寄存器/快表 地址映射p70,图4-26

段,页式存储管理的对比表 段式 页式 由用户设计，有逻辑意义 分页用户不可见，由OS划分 段面是信息的逻辑单位 页面是信息的物理单位 段式 页式 由用户设计，有逻辑意义 分页用户不可见，由OS划分 段面是信息的逻辑单位 页面是信息的物理单位 便于段的共享和动态链接 页一般不能共享 段长不等，可动态增长 页面大小相同，不能增长 段具有二维地址空间 页具有一维地址空间 管理形式相似，但概念不同

段页式存储管理 内存空间：静态地划分为若干等长的物理页 进程空间：静态地划分为若干不等长的逻辑段，每段又静态地划分为若干等长的逻辑页 物理地址=物理页首址+页内地址 进程空间：静态地划分为若干不等长的逻辑段，每段又静态地划分为若干等长的逻辑页 逻辑地址=段号+逻辑页号+页内地址 段表/页表/进程表/空闲表 段表首址寄存器/段表长度寄存器/快表 地址映射p74,图4-37

分段式管理应用实例 给定下面段表，已知下列逻辑地址[0，430]，[3，400]，[1，10]，[2，500]，[4，42]，[1，11]（第一个元素为段号，第二个元素为段内地址），分别求其对应的物理地址

段号 段长 段首址 600 219 1 14 2300 2 100 90 3 580 1327 4 96 1954

段式存储管理 段,页式存储管理的对比表 段式存储管理的优越性:段的共享与动态分配，一般由硬件设备的多种支持，特别是近代的优化编译巳进入CPU内部设计。段共享的先决条件是程序段可重入，即前面一段没有退出前，在不影响工作前提下，后面一段又可重新装入。而可重入程序的特点是执行程序中指令不变称纯代码（纯码）,而工作区和数据区由调用者自带。

段页式存储管理特点 每一段分若干页，再按页式管理，页间不要求连续； 用分段方法分配管理作业，用分页方法分配管理内存； 兼有段式和页式管理的优点,系统复杂性和开销增大，一般在大型机器上才使用.

外存管理技术 外存区间划分：基本单位为块 外存空间分配：外存分配的基本单位是块，而内存的分配单位是单元 界地址存储管理外存空间分配 页式存储管理外存空间分配 段式存储管理外存空间分配 段页存储管理外存空间分配

虚拟存储管理 虚存是由操作系统调度，采用内外存的交换技术，各道程序在必需使用时调入内存，不用的调出内存，这样好象内存容量不受限制。

虚拟存储系统 虚拟存储是一种借助于外存 空间，从而允许一个进程在其运行过程中部分地装入内存的技术 虚拟 页式存储系统 虚拟段式存储系统 虚拟段页式存储系统

虚存的特点 虚存容量不是无限的，极端情况受内存和外存可利用的总容量限制 虚存容量还受计算机总线地址结构限制 速度和容量的“时空”矛盾，虛存量的“扩大”是以牺牲CPU工作时间以及内外存交換时间为代价的，以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术

概述 程序局部性原理 时间局部性 一条指令被执行了，则在不久的将来它可能再被执行 空间局部性 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用

虚拟页式存储管理 基本思想 在进程开始运行之前，不是装入全部页面，而是装入几个或零个页面，之后根据进程运行的需要，动态装入其它页面； 当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面

} 虚页 X 7 5 3 4 6 1 2 虚地址空间 物理地址空间 页框 60K-64K 56K-60K 52K-56K 48K-52K 6 1 2 60K-64K 56K-60K 52K-56K 48K-52K 44K-48K 40K-44K 36K-40K 32K-36K 28K-32K 24K-28K 20K-24K 16K-20K 12K-16K 8K-12K 4K-8K 0K-4K 虚地址空间 物理地址空间 } 虚页 页框

页表表项 页号、内存块号、外存块号 、访问位、内外标志、、修改标志 内外标志：表示该页是在内存还是在外存 修改位：查看此页是否在内存中被修改过 页号 中断位 内存块号 外存地址 访问位 修改位

页表设计 页表内容举例 淘汰位/修改位/保护位/中断位/引用位/缺用位等 快表:因页面较多，页表在内存，取一次数要访问内存两次。

内存页面分配策略 平均分配 按进程长度比例分配 按进程优先级比例分配 按进程长度和优先级比例分配 将内存中所有物理页等份分给进入系统的进程。 Ai=si/S*m 按进程优先级比例分配 按进程长度和优先级比例分配

外存块分配策略 静态分配 动态分配 一个进程在运行前，将其所有页面全部装入外存，当某外存页被调入内存时，所占用的外存 页面并不释放 一个进程在运行前，仅将未装入内存的那部分页面装入外存，当某外存页被调入内存时，释放所占用的外存 页面

缺页中断（Page Fault）处理 在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，准备将该页调入内存 此时应将缺页的进程挂起（调页完成唤醒）

如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应页表项目的驻留位及相应的内存块号 若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）

思考 缺页中断同一般中断的区别？

缺页中断同一般中断都是中断，相同点是： 保护现场 中断处理 恢复现场 不同点： 一般中断是一条指令完成后中断，缺页中断是一条指令执行时中断 一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中。

页面调入方法 请调 页故障发生/缺页时，进行页面调度 预调 页故障发生/缺页前，进行页面调度

页面淘汰算法（1） 最优淘汰算法（OPT）（Optimal Replacement Algorithm） 先进先出算法(FIFO） 淘汰以后不再需要的或最远的将来才会用到的页面 先进先出算法(FIFO） （First Input First Output）,又称轮转法（RR） 选择在内存中驻留时间最长的页并淘汰之 最近最少使用页面先淘汰（LRU） （Least Recently Used） 选择最后一次访问时间距离当前时间最长的一页并淘汰之 即淘汰没有使用的时间最长的页

页面淘汰算法（2） 最近没有使用页面先淘汰（NUR） 最不经常使用的页面先淘汰（LFU）（Least Frequent Used） 最经常使用的页面先淘汰（MFU）（Most Frequent Used）

LRU的硬件解法： 系统为每页设置一个寄存器R，每当访问这一页时，将该页对应的寄存器R置1，以后每个时间间隔将所有的R左移一位，当淘汰一页时就选择R值最大的页。也就是说R值越大，对应的页未被使用的时间越长。所以淘汰的是最久未使用的页。显然，R的位数越多越精确。但系统硬件成本也就越高。

LRU软件解法： 设置一个页号栈，当一个页面被访问时，就立即将它的页号压入页号栈，并检查页号栈中是否有与刚压入栈顶的相同的页号，若有，则从页号栈中抽出，以保证页号栈中无相同的页号。当系统要淘汰一节时，总是从页号栈底取出一个页号淘汰，即淘汰的页是最久未使用的。

LRU近似算法： 在页表中增加一访问位，每当访问一页时，将该页的访问位由硬件置1，软件周期（T）性地将所有访问位置0。在时间T内，访问过的页其访问位为1，反之为0，淘汰为0 的页。 缺点：T难定。太小，访问位为0的页相当多，所选的不一定是最久未用的。太大，所有页的引用位可能都为1，找不到合适的淘汰页。

最不经常使用（LFU） 选择访问次数最少的页面淘汰之 与LRU的硬件解法类似。

例1 某程序在内存中分配三个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、 LRU、OPT算法分别计算缺页次数 假设开始时所有页均不在内存

FIFO FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 5 5 2 1 1 页2 4 3 2 1 4 3 3 3 5 2 2 页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x   x x  共缺页中断9次

LRU LRU 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 4 3 2 1 5 页2 4 3 2 1 4 3 5 4 3 2 1 页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x   x x x 共缺页中断10次

OPT OPT 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 5 5 2 1 1 页2 4 3 3 3 3 3 3 3 5 5 5 页3 4 4 4 4 4 4 4 4 4 4 x x x x   x   x x  共缺页中断7次

练习 某程序在内存中分配四个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分别计算缺页次数 假设开始时所有页均不在内存

LRU 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 4 3 2 1 5 页2 4 3 2 1 4 3 5 4 3 2 1 页3 4 3 2 1 4 3 5 4 3 2 页4 4 3 2 1 1 1 5 4 3 x x x x   x   x x x 共缺页中断8次

OPT 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 5 5 5 1 1 页2 4 3 2 2 2 2 2 2 2 5 5 页3 4 3 3 3 3 3 3 3 3 3 页4 4 4 4 4 4 4 4 4 4 x x x x   x    x  共缺页中断6次

例2 有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配3块。进程执行时使用页号的顺序为 4 3 2 1 4 3 5 4 3 2 1 5 (1) 该进程运行时总共出现几次缺页。 (2) 若每个进程在内存有4块，又将产生几次缺页。 (3) 如何解释所出现的现象。

m=3 FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 4 3 5 5 5 2 1 1 页2 4 3 2 1 4 3 3 3 5 2 2 页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x   x x  共缺页中断9次

m=4 FIFO 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 4 3 2 1 5 页2 4 3 2 2 2 1 5 4 3 2 1 页3 4 3 3 3 2 1 5 4 3 2 页4 4 4 4 3 2 1 5 4 3 x x x x   x x x x x x 共缺页中断10次

m=3时，缺页中断9次 m=4时，缺页中断10次 FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加

影响缺页次数的因素 (1) 分配给进程的物理块数 (2) 页本身的大小 (3) 程序的编制方法 (4) 页淘汰算法

颠簸（抖动） 在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动 原因： 分配给进程的物理页面数太少 页面淘汰算法不合理

工作集模型 工作集是进程活跃地访问页面的集合 工作集随时间而变化 工作集大小与窗口大小密切相关 工作集模型实现的难点在于 动态记录各个进程的工作集

页故障率反馈模型 系统可以利用页故障率的反馈信息来动态地调整页面的分配。 规定页故障率的上限和下限。

虚拟段式存储管理 1、段表内容 增加： 特征位（在/不在内存，是否可共享） 存取权限位（读，写，执行） 标志位（是否修改过，能否移动） 扩充位（固定长/可扩充 ）

缺段中断处理 检查内存中是否有足够的空闲空间 ①若有，则装入该段，修改有关数据结构，中断返回 ②若没有，检查内存中空闲区的总和是否满足要求，是则应采用紧缩技术，转① ；否则，淘汰一（些）段，转①

段的动态链接 ………… 125743 [x]段 <y> ………… Load *1,[x]|<y> [w]段

[w]段 [段号=2 ] …… … 段首址 段表 段号 1 2 1 … 2 160 Load *1,2|100 …… “7[x]|<y>” 60 100 160 Y 200 …… “125734” 200 …… … 2 [W] 1 [A] [MAIN] 段首址 段名 段名-段号对照表 *

[w]段 [段号=2 ] …… … 段首址 段表 段号 1 2 3 0 … 3 200 Load *1,2|100 …… “7[x]|<y>” 60 100 160 Y 200 …… “125734” 200 [X]段 …… … 2 [W] 1 [A] [MAIN] 段首址 段名 段名-段号对照表 [X] 3 *

课堂练习 1、某程序在内存中分配3块内存，初始为空，访问页的走向为2，3，2，1，5，2，4，5，3，2，5，2，用FIFO和LRU算法分别计算缺页次数

FIFO 2 3 2 1 5 2 4 5 3 2 5 2 页1 2 3 3 1 5 2 4 4 3 3 5 2 页2 2 2 3 1 5 2 2 4 4 3 5 页3 2 3 1 5 5 2 2 4 3 x x  x x x x  x  x x 共缺页中断9次

LRU 2 3 2 1 5 2 4 5 3 2 5 2 页1 2 3 2 1 5 2 4 5 3 2 5 2 页2 2 3 2 1 5 2 4 5 3 2 5 页3 3 2 1 5 2 4 5 3 3 x x  x x  x  x x   共缺页中断7次

2、 有一页式系统，其页表存放在主存中。 (1) 如果对主存的一次存取要3us，问实现一次页面访问要多长时间。 (2) 如系统有快表，平均命中率为97%，假设访问快表的时间忽略为0，问此时一次页面访问要多长时间。

1、2*3=6us 2、0.97*3+0.03*6=3.09us

3、在分页存储管理系统中，有一作业大小为4页，页长为2K，页表如下： 试借助地址变换图（即要求画出地址变换图）求出逻辑地址4635所对应的物理地址。 页号 块号 5 1 3 2 7 6

3 1 6 7 2 5 块号 页号 01000011011 00010 00111 页表首址 + 10 物理地址为：14875

作业

第六章 设备管理 6.1 设备分类 6.2 设备的物理特性 6.3 通道技术 6.4 设备的分配与去配 6.5 设 备 驱动 6.6 缓冲技术 6.7 虚拟设备

设备管理的目标 1、设备独立性 所谓设备独立性：用户在编制程序时，使用逻辑设备名，由系统实现从逻辑设备到物理设备（实际设备）的转换。用户能独立于具体物理设备而方便的使用设备。

两种类型的设备独立性 独立于同一类设备中的某台具体设备。如果一个系统中有若干台相同的设备，用户编程时不指定使用哪一个具体的设备，而仅说明要使用哪一类设备，系统根据当前这一类设备的具体状况给用户分配一台具体的设备。用户不用关心他所使用的到底是哪一台设备。

独立于不同类型的设备。 例如有一程序要求输入信息，可以从各种不同类型的输入设备上给程序输入数据，则称该程序是独立于不同类型的输入设备的。 又如在MS-DOS系统中，程序的I/O操作不必指出在哪台设备上进行，一般情况下是从键盘上输入数据，而在显示器上输出数据。但用户可以做一次联机操作命令Ctrl+P，则输出数据可以在打印机上打印出来。

2、提高设备利用率 提高设备的使用效率是操作系统设备管理的重要目标。 为达到此目标除了要合理分配和使用外部设备外，还应努力提高设备同CPU的并行程度。与此有关的技术有：通道技术和缓冲技术。

设备管理的功能 1、 监视系统中所有设备的状态 一个计算机系统中存在着许多设备，在系统运行期间这些设备都在处理各自所承担的工作，并处于各种不同的状态，系统要有效地管理和使用这些设备就必须监视它们的工作状态。

设备的分类 1.按用途分 输入输出型设备 输入设备 输出设备 存储型设备 磁带机 磁盘机 磁鼓机

2、按信息交换的单位分类 字符设备：I/O传输的单位是字节，如打印机、modem等。特征：速率较低、中断驱动。 块设备 ： I/O传输的单位是块，如磁盘、磁带。特征：速率高（几兆）、可随机访问任一块、DMA方式驱动。

3. 按资源管理方式分类 独占型设备：在任一段时间内最多有一个进程占用它，字符设备及磁带机属独占型设备。即临界资源。 共享型设备：多个进程对它的访问可以交叉进行，除磁带机外的块设备属共享设备 虚拟设备：在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚拟设备

4、按传输速率分 低速设备：每秒几个到数百字节。如Modem 中速设备：每秒数千到数万字节。如打印机 高速设备：每秒数百K到数兆。如磁盘、磁带

设备的物理特性 输入输出型设备 以字符为I/O传输的基本单位 通道技术 存储型设备 I/O传输一完整的块为基本单位

磁带 磁头 带头标　信息块　间隙 信息块 间隙 …… 尾标 成组技术

假定磁带的记录密度为每英寸800字符,每个逻辑记录长为160字符,块间间隙为0.6英寸，现有1000个逻辑记录需要存储.问: 1.计算不成组操作时,磁带的利用率是多少? 2.若以5个逻辑记录为一组操作时,磁带的利用率又是多少? 3.物理记录(块)至少为多大时,才不至于浪费超过50%的利用率?

磁盘物理结构 扇区 磁道 磁道（cylinders）0磁道中存有文件分配表（FAT）信息 扇区（Sectors,512字节） 磁盘结构及磁道扇区划分

磁盘容量 容量 = 2  80  18  512（字节）  1024 = 1474560（字节B） = 1440（KB） 容量=磁盘面数磁道数/面扇区数/磁道字节数/扇区 容量 = 2  80  18  512（字节）  1024 = 1474560（字节B） = 1440（KB）

硬磁盘的结构 磁道 柱面 扇区 柱面、磁头、扇区 唯一确切的扇区： 0柱面、1磁头、12扇区

三维地址: 柱面号:0…i…L-1 盘面号:0…j…m-1 扇区号:0…k…n-1 一维地址: 块号b i=b÷(m×n) j=b mod (m×n) ÷n k=b mod (m×n) mod n b=i × m×n +j ×n +K

假设某磁盘组 共有100个柱面,8个磁头,每个盘面被分为4个扇区,若逻辑记录的大小与扇区大小相等,柱面,盘面和扇区的编号从“0”开始, 现用字长为16位的200个字(第0字到第199字)组成字位映像图来指示磁盘空间的使用情况，请问： 文件系统发现字位映像图中的第15个字第7位为0,而准备分配给某一记录时,该记录会存放到磁盘的哪一块上,此块的物理位置如何?(柱面号,盘面号和扇区号如何?) 删除文件时,要归还存储空间,当第56柱面第6盘面第3扇区的块变成了空白块时,字位映像图中的第几位应该由1改为0?

通道技术 1、 I/O系统结构 在大型计算机系统中较为典型的I/O系统结构是主机、通道、控制器和外部设备。

外部设备通常由机械的和电子的两部分组成，电子部分构成控制器，也叫适配器。 一个控制器可交替地控制几台同类设备，例如一个磁盘控制器可以控制两台磁盘驱动器。 在没有通道的计算机系统中，中央处理机是通过控制器控制I/O操作的。

在采用了中断技术以后，中央处理机和外部设备已能在一定程度上并行工作，但每传一个信息单位（一个字节或一个字符块），就要插入一次中断处理，每次中断处理CPU少则要执行几十条指令，多则要执行上千条指令，当一个系统配置的设备较多时，I/O操作较为频繁的情况下，CPU可能完全陷入I/O处理，这样会大大地降低计算机系统的效率，解决的方法就是用到通道技术。

2、通道概念 为使中央处理机从繁忙的I/O处理中摆脱出来，现代大、中型计算机系统中设置了专门的处理I/O操作的处理机，并把这种处理机称为通道。通道在CPU的控制下独立地执行通道程序，对外部设备的I/O操作进行控制，以实现内存与外设之间成批的数据交换。 通道=I/O处理机

当完成CPU交给的任务后，向CPU发出中断信号，请求CPU的处理。这样就使得CPU基本上摆脱了I/O操作的处理工作，提高了CPU与设备之间的并行程序，从而提高了整个计算机系统的效率。 通道程序是由通道指令组成，一个通道可以分时的方式执行几道程序。每道程序控制一台外部设备。

3、 通道指令和通道程序 通道有它自己的指令系统，用这些指令编写的程序叫通道程序，通道只能执行通道程序，不可能执行用户进程。 通道有它自己的指令系统，用这些指令编写的程序叫通道程序，通道只能执行通道程序，不可能执行用户进程。  通道程序保存在内存中

通道指令 操作码 传输字节数 特征位 地址信息 通道控制部件 通道地址字CAW 通道命令字CCW 通道状态字CSW 通道数据字CDW

4、通道的工作过程 某进程在运行过程中，若提出了I/O请求，则通过系统调用进入操作系统，系统首先为I/O操作分配通道和外设，然后按I/O请求生成通道程序并存入内存，把起始地址送入通道的首地址寄存器（CAW），接着CPU发出启动通道的指令。

中央处理机启动通道后，通道的工作过程为： 根据CAW，从内存取出通道指令，送入通道控制字寄存器（CCW），并修改CAW，使其指向下一条通道指令。 执行CCW中的通道指令，进行实际的I/O操作，执行完毕后，如果还有下一条指令，则返回前一步，否则转下一步。 发出中断信号通知CPU通道程序已执行完成。 P115 图6-4

设备的分配与去配 在多用户或多进程的环境中，每个用户在完成各自的任务时总是要使用外设，为用户或进程分配设备是设备管理的主要功能之一。 设备分配包括：设备分配策略、分配的方式、分配技术和选择用户的算法。

设备管理数据结构 设备控制块(UCB/DCB) DCB是设备管理的重要数据结构，在这个结构中较全面地反映了每台设备的特性、连接和使用的状态等信息。当一台设备进入系统时必须创立相应的DCB

DCB的内容 设备标识符：系统有许多设备，为区别起见为每台设备取个名，这个名叫设备标识符。 设备属性：反映设备的相应特性和类型 设备I/O总线地址：设备和CPU是通过I/O总线连接起来的，它在总线上有个地址。 设备状态：指设备当时所处的状态。 等待队列指针：等待使用该设备的进程组成等待队列，这里存放等待队列的队首指针。

图示

设备分配技术 根据设备的特性把设备分成独占设备、共享设备和虚拟设备三种。 针对这三种设备采用三种分配技术: 独享分配 共享分配 虚拟分配

独占分配 独占型设备有行打印机，键盘，显示器。磁带机可作为独占设备，也可作为共享设备。 若对这些设备不采用独享分配就会造成混乱。因此对独占设备一般采用独享分配，即当进程申请独占设备时，系统把设备分配给这个进程，直到进程释放设备。 申请时执行P操作，释放时执行V操作

共享分配 共享设备包括磁盘，磁带和磁鼓。 对这类设备的分配是采用动态分配的方式进行的，当一个进程要请求某个设备时，系统按照某种算法立即分配相应的设备给请求者，请求者使用完后立即释放。

磁盘设备调度 先到先服务FCFS(first come first serve) 最短查找时间优先SSTF(shortest seek time first) 优先为距磁头当前所在位置最近柱面的请求服务 扫描算法scan 磁头引臂按照方向扫描 N步扫描N-scan

假设一个可移动磁头的磁盘具有200个磁道,其编号为0-199，系统刚结束对125道的处理，现正在处理143道的服务请求，假设系统当前I/O请求序列顺序排列如下：86，147，91，177，94，150，102，175，130。试问对以下几种磁盘I/O请求算法而言，满足以上请求序列时，磁头将如何移动，移动的距离各是多少？（以磁道数计） 1.先来先服务算法FCFS 2.最短查找时间优先调度算法SSTF 3.扫描算法SCAN FCFS:143,86,147,91,177,94,150,102,175,130 S=57+61+56+86+83+56+48+73+45=565 SSTF:143,147,150,130,102,94,91,86,175,177 S=4+3+20+28+8+3+5+89+2=162 SCAN:143,147,150,175,177,199,130,102,94,91,86 S=4+3+25+2+22+69+28+8+3+5=169

缓冲技术 引言 硬缓冲与软缓冲 缓冲池 缓冲技术的实现

缓冲技术的引入 缓冲技术的目的是为了提高中央处理机与外设的并行程度。 计算机系统中的各种设备(包括中央处理机)的运行速度差异甚大，CPU的运行速度是以微秒甚至以纳秒计，而设备的运行速度则是以毫秒甚至以秒计；（速度的差异）

另一方面系统的负荷也不均匀，有时处理机进行大量的计算工作，没有I/O操作，有时又会进行大量的I/O操作，这两个极端都会造成系统中的一些设备过于繁忙，一部分设备过于空闲，严重地影响CPU与外设的并行工作。

为此人们提出用缓冲技术来匹配CPU与设备的速度的差异和负荷的不均匀，从而提高处理机与外设的并行程度。 凡是数据到达和离去速度不匹配的地方均可采用缓冲技术。

缓冲技术可以用硬件缓冲器来实现，在设备控制器中有硬件缓冲器，通常容量较小，一般为1个字节。 软件缓冲技术是应用广泛的一种缓冲技术，它由缓冲区和对缓冲区的管理两部分组成。

缓冲池 为了提高缓冲区的利用率，目前广泛流行公用缓冲池，池中的缓冲区可供多个进程共享。   缓冲池由内存中一组大小相等的缓冲区组成，池中各缓冲区的大小与用于I/O的设备的基本信息单位相似，缓冲池属于系统资源，由系统进行管理。 缓冲池中各缓冲区可用于输出信息，也可用于输入信息，并可根据需要组成各种缓冲区队列。

缓冲技术的实现 缓冲区 输入设备 进程空间 缓冲区 进程空间 输出设备 缓冲区 进程空间 输入/输出设备 操作系统 通道程序 通道程序

虚拟设备 利用共享设备实现数量 较多,速度较快的独占型设备。 某一区域 共享型设备 独占型设备 进程 内存 间断传输 连续传输

虚拟分配 系统中独占设备的数量总是有限的，这些独占设备一旦分配给某个进程往往只有很少时间在工作，许多时间一直处于空闲状态。而别的进程又因得不到相应的设备而不能运行，因此严重地影响到整个计算机系统的效率。 从另一个角度来说，独占设备一般是低速的，若采用联机操作，也会增加进程的运行时间，影响计算机系统的效率。 为提高计算机系统的效率，提出了在高速共享设备上模拟低速设备功能的技术，称为虚拟设备技术。

虚拟分配是针对虚拟设备而言的。 其实现的过程是: 当用户(或进程)申请独占设备时。系统给它分配共享设备的一部分存储空间。当程序要与设备交换信息时，系统就把要交换的信息存放在这部分存储空间。在适当的时候再将存储空间的信息传输到相应的设备上去处理。

如系统打印信息时，就把要打印的信息送到某个存储空间中去，然后由系统在适当时机把存储空间上的信息送到打印机上打印出来。这个时机可能是打印机空闲或打印机完成了一用户的信息输出之后。 通常人们把共享设备中代替独占设备的那部分存储空间和相应的控制结构称为虚拟设备，并把对这类设备的分配称作虚拟分配。

SPOOLing系统 Simultaneaus Periphernal Operations On-Line(外部设备同时联机操作）。 在单道批处理时期，用脱机I/O可以提高CPU利用率。多道出现后可以利用一道程序来模拟脱机I/O中的卫星机，这样可实现在主机控制下的脱机I/O功能。 我们把这种在联机情况下实现的同时外围操作称为SPOOLing，也称为假脱机操作。

SPOOLing系统的组成 1、输入井和输出井 2、输入缓冲区和输出缓冲区 3、输入进程和输出进程

SPOOLing系统工作原理 作业执行前预先将程序和数据输入到输入井中 作业运行后，使用数据时，从输入井中取出 作业执行不必直接启动外设输出数据，只需将这些数据写入输出井中 作业全部运行完毕，再由外设输出全部数据和信息 好处： 实现了对作业输入、组织调度和输出的统一管理 使外设在CPU直接控制下，与CPU并行工作（假脱机）

图示 输入装置 通 道 输出装置 通 道 主机系统 输入管 输出管 理模块 理模块 外 存 输入井 输出井 SPOOLing系统

SPOOLing系统的特点 1、提高了I/O速度 2、将独占设备改造为共享设备 3、实现了虚拟设备功能

其它技术(*) 总线技术 USB技术 SCSI接口技术 即插即用技术 网络I/O设备

总线技术 1、总线的基本概念： 新一代计算机出现，带来了总线技术的更新 在计算机系统内各种子系统，如CPU、内存、I/O设备等之间，构建公用的信号或数据传输通道 这种可共享的传输通道称为总线

2、总线的分类 CPU-内存总线 （非本课程范围） 总线的分类 数据总线 I/O总线 地址总线 控制总线

微型计算机 总线的种类和发展 PC／XT总线 ISA总线 MCA总线 EISA总线 VESA总线 PCI总线 USB总线 SCSI总线 …... (过时) 微型计算机 总线的种类和发展 SCSI总线 1394总线

ISA（工业标准结构） ISA基于PC／AT总线，是由IEEE（美国电气电子工程师协会）1987年正式确立的标准。 ISA工作频率定在8.33MHz，数据传输率为8.33MB／s。 随着系统工作频率的迅速提高，其配用的扩展卡也逐渐被淘汰，现在最新的主板已开始取消ISA槽。

PCI （外围部件互连） 1993年Intel发表PCI2.0版，PCI开始走进主板。 PCI槽的时钟频率为33.3MHz，32位PCI的数据传输率为133MB／s，大大高于ISA。所以PCI问世后迅速成了扩展总线的主流，流行的扩展卡也都转移到PCI上，如显示卡、声卡、网卡、MODEM卡等等。

AGP（加速图形端口） 1996年Intel公司在PCI的基础上专为显示卡接口提出AGP标准。 AGP使用32位数据总线，工作频率为66.6MHz AGP 1x的数据传输率可达266MB/s，AGP 2x在一个时钟周期的上升沿和下降沿各传输一次资料，其数据传输率可达到533MB／s，而AGP 4x的理论传输率为1.066GB／s。

IEEE1394 IEEE1394是1995年由IEEE将APPLE公司高速串行总线“FIRE WIRE”标准化而成，目前还在发展中。

IEEE1394的特点 标准数据传输率分三种：100Mbps、200Mbps和400Mbps, IEEE1394商业联盟计划将它提高到800Mbps、1Gbps和1.6Gbps； 支持同步模式传输,可实现“准实时”的多媒体数据传输； 连接方便，易于扩展，不必设定标识号和连接终端负载，可采用菊花链或树形方式连接，所有连接的设备是平等关系，不用个人计算机介入也可形成系统，支持热插拔；

单根线缆最长为4.5米，最大可进行15级级联，连接最大距离为72米； 采用6股铜芯线缆，两股用于供电，另外四股分为两对双绞线，接头小巧耐用。

USB技术 USB（Universal Serial Bus）通用串行总线 一种连接I/O串行设备的技术标准 USB是以Intel为主并有Compaq、MicroSoft、IBM、DEC、NEC、Northern Telecom7家公司共同制定的串行接口规格。 USB接口适用于低、中速的外围设备如键盘、鼠标、打印机、数码相机、调制解调器、扫描仪等。

USB设备的分类 USB设备分为两类： （1）USB集线器：本身可再接其他USB外围设备 （2）USB设备：连接在计算机上用来完成特定功能并符合USB规范的I/O设备单元，如鼠标、键盘等

USB的传输方式 4种不同的数据传输方式： （1）等时传输方式 （2）中断传输方式 该方式传送的数据量很小，但这些数据需要及时处理，以达到实时效果，此方式主要用在键盘、鼠标以及游戏手柄等外部设备上

（3）控制传输方式 处理器与USB设备的数据传输，包括设备控制指令、设备状态查询及确认命令。当USB设备收到这些数据和命令后将按照先进先出的原则按队列方式处理到达的数据 （4）批传输方式 用来传输要求正确无误的数据。通常打印机、扫描仪和数码相机以这种方式与主机连接 除等时传输方式外，其他3种方式在数据传输发生错误时，都会试图重新发送数据以保证其准确性

USB 的特点 数据传输具有1.5Mbps和12Mbps两种方式； 连接方便，易于扩展，可使用集线器进行树形连接，连接的设备最多可达6层127个，支持热插拔； 连接的设备之间不是平等关系而是亲子关系，上下游的关系明确，对上和对下的电缆插头不一样，而且必须用个人计算机作为主设备，各个分设备只能同主设备进行通信并受主设备的控制；

单根线缆最长为5米； 采用4股铜芯线缆，两股用于供电，直接由主板提供＋5V电源，另外二股为信号线。 USB 2.0规范将最高速率提高到480 Mbps

SCSI接口技术 小型计算机系统接口 （Small Computer System Interface） 最早研制于1979年，原是为小型机的研制出的一种接口技术，但随着电脑技术的发展，现在它被完全移植到了普通微机上。

在计算机外部设备，尤其是存储设备的接口方面SCSI接口和IDE接口一直是飞速发展的两大阵营。 IDE接口价格低廉，兼容性好，主板的BIOS能够支持，使用方便，长期以来的不断改进，使其性能也有了长足的进步，传输速率现已达到66MB/S。 SCSI接口从技术和性能上说，其始终拥有着顶级设备的特征。

IDE接口在PC机上拥有绝大多数的市场份额 SCSI接口却以其优异的性能成为高端电脑市场的绝佳选择。 二者的区别主要在于： IDE的工作方式需要CPU的全程参与 SCSI接口则完全通过独立的高速的SCSI卡来控制数据的读写操作

优缺点 SCSI接口优点： 1. 适应面广，在一块SCSI控制卡上就可以同时挂接15个设备 2. 高性能（具有很多任务、宽带宽及少CPU占用率等特点） 3. 具有外置和内置两种 SCSI接口缺点： 价格昂贵、安装复杂

即插即用技术 Plug and Play 计算机系统I/O设备与部件配置的应用技术 顾名思义： 插入就可用，不需要进行任何设置操作

PnP技术的产生 由于一个系统可以配置多种外部设备，设备也经常变动和更换，它们都要占有一定的系统资源，彼此间在硬件和软件上可能会产生冲突。因此在系统中要正确地对它们进行配置和资源匹配；当设备撤除、添置和进行系统升级时，配置过程往往是一个困难的过程

PnP技术的特点 （1）支持I/O设备及部件的自动配置，使用户能够简单方便地使用系统扩充设备

（3）在主机板和附加卡上保存系统资源的配置参数和分配状态，有利于系统对整个I/O资源的分配和控制 （4）支持和兼容各种操作系统平台，具有很强的扩展性和可移植性。 （5）在一定程度上具有“热插入”、“热拼接”技术

网络I/O设备 典型网络I/O设备——网络打印 以往的打印模式 打印机连接到网上PC上，或连到文件服务器上，提供网络打印服务 新的网络打印 采用网络打印服务器技术，打印机直接上网 任何数据直接送到网络打印机输出

打印服务器还能实现多种网络自动切换：不同网络环境中的用户都可以直接向同一台打印机发送打印作业，打印服务器会自动识别 较强的打印管理功能：可以管理网络打印驱动，而且容易安装和管理；可以实现远程登录访问，进行远程打印机管理 提高工作效率 分布式的环境设置：可以安装在网络的任何地方，这种打印服务方式，就显得更加灵活和满足需要

第七章 作业管理 7.1 作业及其分类 7.2 批处理作业管理 7.3 交互式作业管理

处理机调度概述 处理机调度（CPU调度）要解决的问题： WHAT：按什么原则分配CPU —调度算法 WHEN：何时分配CPU —调度的时机 HOW： 如何分配CPU —CPU调度过程（进程的上下文切换）

处理机调度的三个层次 处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度

高级调度 也称为作业调度或宏观调度，一般在批处理系统中有作业调度。

中级调度 涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间。

低级调度 也称微观调度、进程调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态。由于低级调度算法的频繁使用，要求在实现时做到高效

作业调度 作业的基本概念 （1）作业 要求计算机系统按照指定步骤对初始数据进行处理并得到结果的一系列的工作集合。 作业更强调完整的工作过程。 （2）作业步 一个作业可划分成若干部分，称为一个作业步 典型的作业控制过程： “编译”、“连接装配”、“运行”

（3）典型的作业步

批处理作业 以脱机操作为主要特征 交互式作业 以联机操作为主要特征，在分时系统以及实时系统中所处理的作业属于此类。

批处理作业控制语言与作业说明书 1、作业控制语言 作业说明书:用户用于描述批处理作业处理过程 书写作业说明书的语言称为作业控制语言（JCL）

2、作业说明书 表达用户对作业的控制意图 内容： 作业的基本描述 作业控制描述 资源要求描述

$ SNUMB JOB1,40 $ INDET 123,USER1 $ OPTION FORTRAN77 $ FORTRAN77 ………………….. $ EXECUTE $ LIMITS 20,64K,1000 $ ENDJOB

批处理作业的状态及其转换 提交 后备 执行 完成 退出 假脱机输入 作业调度（1） 作业调度（2） 假脱机输出

作业控制块与作业表 1、作业控制块（JCB：Job Control Block） 作业控制块是批处理作业存在的标志 保存有系统对于作业进行管理所需要的全部信息 位于磁盘区域中

2、作业控制块的内容 作业控制块中所包含的信息数量及内容因系统而异

作业控制块JCB 作业标知 用户名称 用户帐号 调度信息 资源需求 作业状态 作业类别 输入井地址 输出井地址 进入系统时间 开始处理时间 作业完成时间 作业退出时间 资源使用情况 作业控制块JCB

3、作业控制块的建立 当作业开始由输入设备向磁盘的输入井传输时，系统输入程序为其建立一个作业控制块，并进行初始化 初始化的大部分信息取自作业说明书

4、作业控制块的使用 需要访问作业控制块的程序： 系统输入程序 作业调度程序 作业控制程序 系统输出程序等

5、作业控制块的撤消 作业完成后，其作业控制块由系统输出程序撤消 作业控制块被撤消后其作业也不复存在

系统输入程序、作业调度程序、系统输出程序都需要访问作业表，因而存在互斥问题 6、作业表 每个作业有个作业控制块 所有作业JCB构成一个作业表 作业表存放在外存固定区域中，长度是固定 限制了系统所能同时容纳的作业数量 系统输入程序、作业调度程序、系统输出程序都需要访问作业表，因而存在互斥问题 JCB1 JCB2 …… JCBi …… JCBn 作业表

作业的建立 经历两个过程 1、作业的输入 2、JCB的建立 作业控制块JCB和作业：一一对应关系

1、作业的输入 作业输入方式 将作业程序、数据和作业说明书从输入设备（例如键盘）输入到外存，并形成初始信息 联机输入方式 脱机输入方式 SPOOLing系统

脱机输入方式 为了解决单台设备联机输入时的CPU浪费问题 联机输入方式 用户和系统通过交互会话来输入作业 外围设备直接和主机连接 脱机输入方式 为了解决单台设备联机输入时的CPU浪费问题

2、JCB的建立 在系统把作业信息输入到输入井之后，根据作业说明书和有关作业信息在外存的位置等，建立作业控制表JCB 外存输入井的大小有限 只有在获得JCB表项和足够输入井空间后 作业才可能创建成功

批处理作业的调度 主要功能： 审查系统能否满足用户作业的资源要求 按照一定的算法从输入井中的后备作业中选取作业 调度的关键在选择恰当的算法

1、调度算法评价 调度实质上是一个策略问题 设定的目标往往是相互冲突的 目标： 单位时间内运行尽可能多的作业 使处理机尽可能保持“忙碌” 使各种I/O设备得以充分利用 对所有的作业都是公平合理的

要设计一个理想的调度算法是一件十分困难的事 在实际系统中，调度算法往往折衷考虑 设计调度算法时应考虑的因素： 调度算法应与系统设计目标保持一致 注意系统资源均衡使用 保证提交的作业在截止时间内完成 设法缩短作业平均周转时间 大多数操作系统都采用比较简单的调度算法

2、调度算法性能的衡量 作业平均周转时间 假定某一作业进入“输入井”的时间为Si， 它被选中执行，运行结束时的时间为Ei 周转时间为Ti ＝Ei – Si 则作业平均周转时间为： T＝（ ）× n为作业数

平均带权周转时间 W＝（ ）× ri 为某作业i的实际执行时间

3、系统进行作业调度的决策因素 作业到达时间 预先为作业确定的优先级 作业所需的CPU时间C 存储要求M 打印输出的行数L 其他的资源要求

4、常见的批处理作业调度算法 先来先服务算法（FCFS：First Come First Serve） 最短作业优先算法（SJF：Shortest Job First）

最高响应比优先算法（HRN：Highest Response Ratio Next） 响应比R = 作业周转时间 / 作业处理时间 =（作业处理时间+作业等待时间）/ 作业处理时间 = 1 +（作业等待时间 / 作业处理时间）

基于优先数调度算法（HPF：Highest Priority First） （a）由用户规定优先数（外部优先数） 用户提交作业时，根据急迫程度规定适当的优先数，作业调度程序根据JCB优先数决定进入内存的次序 （b）由系统计算优先数（内部优先数） 例：可按如下公式计算作业的优先数： 优先数 = 用户规定优先数 – 作业处理时间 + 作业等待时间 – 输出量

均衡调度算法(分类排队算法) 基本思想： 根据系统运行情况和作业属性将作业分类 轮流从不同的作业类中挑选作业 目标： 力求均衡地利用各种系统资源，发挥资源使用效率 力求使用户满意

均衡调度算法例1： 将待处理作业分成如下队列： 队列1：计算量大的作业 队列2：I/O量大的作业 队列3：计算量与I/O量均衡的作业 调度时，在三个队列中各取一些作业，在内存中的作业有的使用处理机，有的使用外部设备 使得系统的各种资源能得到充分利用

均衡调度算法例2： 将待处理作业分成如下三个队列： 队列1：长作业 队列2：中等长度作业 队列3：短作业 调度时 取队列1一道作业，队列2一道作业，队列3一道作业 长作业用户和短作业用户均比较满意

5、作业调度算法应用例子1 假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间, 应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间

先来先服务调度算法计算结果

最短作业优先作业算法计算结果

最高响应比优先作业算法计算结果

作业调度与进程调度 作业能否占用处理器？什么时间能够占用处理器？ 由进程调度来决定 进程的初始状态为就绪状态 进程调度选择当前可占用 CPU处理进程，当它让出处理器时，进程调度就再选另一作业的进程 作业调度与进程调度相互配合，实现作业的并发执行

作业退出 把输出结果送到输出设备上（启动缓输出进程完成） 回收各种资源

交互式作业的管理 终端命令语言 命令解释程序 终端用户的创建与清除 终端用户的注册与注销 用户名，帐号，口令，历次登录使用时间，资源使用情况，其他 终端用户的注册与注销 Login/logon Logout/logoff

第八章 进程管理 8.1 并发进程 8.2 进程互斥 8.3 进程同步 8.4 进程通信 8.5 进程死锁

程序的顺序执行 程序的顺序执行如图 在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。一道程序执行完后另一道才能开始。

程序顺序执行的特点 顺序性：一个程序开始执行必须要等到前一个程序已执行完成 封闭性：程序一旦开始执行，其计算结果不受外界因素影响 可再现性：程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果。

程序的并发执行 所谓程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。 并发与并行概念的区别？ Concurrency，parallel

程序并发执行的特点 间断性 失去程序的封闭性 不可再现性 任何并发执行都是不可再现的吗？

进程互斥 共享变量与临界区域 临界区域与进程互斥 进程互斥的实现 利用软件方法解决进程互斥问题 利用硬件方法解决进程互斥问题 用上锁开锁原语实现进程互斥

基本概念 与时间有关的错误: 一飞机订票系统，两个终端，运行T1、T2进程 T1 : T2: ... ... ... ... Read(x); Read(x); if x>=1 then if x>=1 then x:=x-1; x:=x-1; write(x); write(x);

c p g 并发环境下程序间的制约关系

同步：对于进程操作的时间顺序所加的某种限制，如操作Ａ应在Ｂ之前执行。 互斥：同步的特例，多个操作决不能同时执行， 如：操作Ａ和操作Ｂ不能在同时执行。 （注意：理解不能同时执行的准确含义）

临界资源(critical resource)：一次仅允许一个进程访问的资源。 如：进程ＡＢ共享一台打印机，若让它们交替使用则得到的结果肯定不是我们希望的。 临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。 并发进程对临界资源的访问必须作某种限制，否则就可能出与时间有关的错误，如：联网售票。

临界区(critical section)：临界段，在每个程序中，访问临界资源的那段程序。 注意：临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。 如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。

解决互斥的准则 为了禁止两个进程同时进入临界区内,可以采用软件办法或系统提供的同步机构来协调它们的关系。但是，不论用什么办法都要遵循下述准则: 1、当有若干进程欲进入它的临界区时,应在有限时间内使进程进入临界区。换言之，它们不应相互阻塞而致使彼此都不能进入临界区 2、每次至多有一个进程处于临界区。 3、进程在临界区内仅逗留有限的时间。

对临界区的管理原则 有闲让进 忙则等待 多中选一 有限等待 让权等待

软件方法解决进程互斥 现在很少用软件方法解决互斥，但通过学习软件解法能使读者了解到，在早期进程互斥问题的解决并不是一件很简单的事。 假如有两个进程Pi和Pj，它们共享一个临界资源R。如何用软件方法使进程Pi和Pj能互斥地访问R。 下面介绍四个算法。

算法1 设整型变量turn，用于指示被允许进入临界区的进程的编号，即若turn=0，表示进程Pi可进入。turn =1表示进程Pj可进入。 

进程Pi : Repeat While turn<>i do no_op; Critical section turn:=j; Other code Until false;

算法1的问题 该算法可确保每次只允许一个进程进入临界区。但它强制两个进程轮流进入。如当Pi退出时将turn置为1，以便 Pj能进入，但Pj暂不需要进入，而这时Pi又需要进入时，它无法进入。这不能保证准则1。

算法2 设var flag:array[0..1] of boolean，若flag[i]=true，表示进程Pi正在临界区内。flag[i]=false表示进程Pi不在临界区内。若flag[j]=true，表示进程Pj正在临界区内。flag[j]=false表示进程Pj不在临界区内。

Pi进程： Repeat While flag[ j ] do no_op; flag[i]:=true; Critical section flag[i]:=false; Other code Until false;

算法2的问题 该算法可确保准则1。但又出现新问题。当pi和pj都未进入时，它们各自的访问标志都为false。如果pi和pj几乎同时要求进入，它们都发现对方的标志为false，于是都进入了。 这不能保证准则2。

算法3 算法2 的问题在于：当进程Pi观察到进程Pj的标志为false后，便将自己的标志由false改为true，而正是在这两步之间，可能发生进程切换。当Pj运行时，它会观察到Pi的标志为false，从而可以将自己的标志设为true，并进入临界区。若在临界区的执行过程中发生了进程切换，Pi可能获得处理机而进入临界区。

在算法3 中，设var Flag:array[0 在算法3 中，设var Flag:array[0..1] of boolean，若flag[i]=true，表示进程Pi希望进入临界区内。若flag[j]=true，表示进程Pj希望进入临界区。

Pi进程： Repeat flag[i]:=true; While flag[j] do no_op; Critical section flag[I]:=false; Other code Until false;

算法3的问题 该算法可确保准则2。但又出现新问题。它可能造成谁也不能进入。如，当pi和pj几乎同时都要进入，分别把自己的标志置为true，都立即检查对方的标志，发现对方为true. 最终谁也不能进入。 这不能保证准则1。

算法4（正确算法） 组合算法1、3，为每一进程设标志位flag[i]，当flag[i]=true时，表示进程pi要求进入，或正在临界区中执行。此外再设一个变量turn，用于指示允许进入的进程编号。

进程为了进入先置flag[i]=true，并置turn为j，表示应轮到pj进入。接着再判断flag[ j ] and turn=j的条件是否满足。若不满足则可进入。或者说，当flag[ j ]=false或者turn=i时，进程可以进入。前者表示pj未要求进入，后者表示仅允许pi进入。

算法4（正确算法） Repeat flag[i]:=true; turn:=j; While (flag[ j] and turn=j) do no_op; Critical section flag[i]:=false; Other code Until false

软件解法的缺点 1. 忙等待 2. 实现过于复杂，需要较高的编程技巧

硬件方法解决进程互斥 用软件解决很难，现代计算机大多提供一些硬件指令。 利用Test-and-Set指令实现互斥 利用swap指令实现进程互斥

Test-and-Set指令实现互斥 1、Test-and-Set指令 Function TS(var lock:boolean):boolean; Begin TS:=lock; Lock:=true; End; 其中，有lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。

2、利用TS指令实现进程互斥 为每个临界资源设置一个全局布尔变量lock，并赋初值false，表示资源空闲。 repeat while TS(lock) do skip; critical section lock:=false; Other code Until false;

swap指令实现进程互斥 1、swap指令 又称交换指令，X86中称为XCHG指令。 Procedure swap(var a,b:boolean); Var temp:boolean; Begin Temp:=a;　 A:=b;　 B:=temp; End;  

2、利用swap实现进程互斥 为每一临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中有局部布尔变量key。 Repeat key:=true; Repeat　　Swap(lock,key);　 Until key=false; Critical section lock:=false; Other code Until false;

用原语实现进程互斥 锁即操作系统中的一标志位，０表示资源可用，１表示资源已 被占用。用户程序不能对锁直接操作，必须通过操作系统提供的上锁和开锁原语来操作。 通常锁用w表示，上锁开锁原语分别用lock(w)、unlock(w)来表示。

上锁和开锁原语 上锁原语lock(w)可描述为： L：if(w==1) goto L else w=1； 　开锁原语unlock(w)可描述为： w=0；

用原语实现进程互斥

改进的上锁原语 上述上锁原语中存在忙等待。

改进的开锁原语

信号量及P、V操作 1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test (proberen) 和increment (verhogen) ） 一种卓有成效的进程同步机制 最初提出的是二元信号量（互斥） 推广到一般信号量（多值）（同步） P、V操作是原语

信号量：semaphore 是一个数据结构 定义如下： struct semaphore { int value; pointer_PCB queue; } 信号量说明： semaphore s;

P操作 P(s) { s.value = s.value -1 ; if (s.value < 0) 该进程状态置为等待状态 } 将该进程的PCB插入相应的等待队列末尾s.queue; }

V操作 V(s) { s.value = s.value +1; if (s.value < = 0) 唤醒相应等待队列s.queue中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列 }

信号量的使用 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作

用P、V操作解决进程间互斥问题 P(mutex) V(mutex) P1 P2 P3 互斥区

信号量及P、V操作讨论 对于两个并发进程，互斥信号量的值仅取1、0和-1三个值 若ＭＵＴＥＸ＝1表示没有进程进入临界区 若ＭＵＴＥＸ＝0表示有一个进程进入临界区 若ＭＵＴＥＸ＝-1表示一个进程进入临界区，另一个进程等待进入。

信号量及P、V操作讨论（续1） 1) 信号量的物理含义： S>0表示有S个资源可用 S=0表示无资源可用 P(S)：表示申请一个资源 V(S)：表示释放一个资源。 信号量的初值应该大于等于0

信号量及P、V操作讨论（续2） 2) P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。 一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前 而两个V操作无关紧要

信号量及P、V操作讨论（续3） 3）P、V操作的优缺点 优点： 简单，而且表达能力强（用P、V操作可解决任何同步互斥问题） 缺点： 遇到复杂同步互斥问题时实现复杂

信号量集——AND型信号量集 AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集P原语为Swait AND型信号量集V原语为Ssignal

进程同步 同步问题可分为两类： 保证一组合作进程按确定的次序执行 保证共享缓冲区的合作进程的同步。

合作进程的执行次序 若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来表示进程集合的执行次序。如图

例 如图，试用信号量实现这三个进程的同步。 设有两个信号量SB、SC，初值均为０ Pa： Pb： Pc： … P(SB); P(SC)   设有两个信号量SB、SC，初值均为０ Pa： Pb： Pc： … P(SB); P(SC) V(SB); …　　　 … 　　 V(SC);

解 设有两个信号量S1、S2，初值均为０ P1： P2： P3： … … P(S1) V(S1); V(S2); 　 P(S2) 　　 … 　　

解 设有5个信号量S2、S3、S4、S5、S6，初值均为０ P1： P2： P3： … P(S2); P(S3) P4： P5： P6： V(S2); …　　　 … 　　 V(S3)； V(S4); V(S6); V(S5) P4： P5： P6： P(S4); P(S5); P(S6); … P(S5); P(S6); …　　　 … 　　 V(S5)； V(S6);

用P.V操作解决司机与售票员的问题 司机进程： while(1) { 启动车辆 正常驾驶 到站停车 }… 售票员进程： 关门 售票 开门

解 设有两个信号量S1，S2，初值均为0。 司机进程： while(1) { P(S1) 启动车辆 正常驾驶 到站停车 V(S2) }… 售票员进程： 关门 V(S1) 售票 P(S2) 开门

共享缓冲区的进程的同步 设某计算进程ＣＰ和打印进程ＩＯＰ共用一个单缓冲区，ＣＰ进程负责不断地计算数据并送入缓冲区Ｔ中，ＩＯＰ进程负责不断地从缓冲区Ｔ中取出数据去打印。

分析 通过分析可知，ＣＰ、ＩＯＰ必须遵守以下同步规则： 当ＣＰ进程把计算结果送入缓冲区时，IOP进程才 能从缓冲区中取出结果去打印;

为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。 两个进程的同步可以描述如下：

【思考题】 1.用P.V操作解决下图之同步问题 提示：分别考虑对缓冲区S和T的同步，再合并考虑 get copy put s t

解 copy： while（1） { P(Sout）; P(Tin）; 将数从S取出放入T; V(Tout); V(Sin); } get： P(Sin）; 将数放入S; V(Sout); } 设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0； put： while（1） { P(Tout）; 将数从T取走; V(Tin); }

【思考题】 桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。 试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。 提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。

解 设置三个信号量S,So,Sa ，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。

Father() { while(1) { p(S); 将水果放入盘中; if(是桔子)v(So); else v(Sa); } Son() { while(1) { p(So) 取桔子 v(S); 吃桔子; Daughter() { p(Sa) 取苹果 吃苹果;

经典的进程同步问题 生产者/消费者问题 读者/写者问题 哲学家进餐问题

生产者/消费者问题 生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。 当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。

问题描述 通过一个有界缓冲区可以把一群生产者p1,p2…,pm，和一群消费者Q1,Q2,…,Qn联系起来。如图 只要缓冲区未满，生产者就可以把产品送入缓冲区; 只要缓冲区未空，消费者就可以从缓冲区中取走物品。

图

问题分析 为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2表示，初值为０。 由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为１。

问题的解 Q： P： i = 0; while (1) j = 0; while (1) { P(S2); P(mutex); 从Buffer[j]取产品; j = (j+1) % n; V(mutex); V(S1); 消费产品; }; P： i = 0; while (1) { 生产产品; P(S1); P(mutex); 往Buffer [i]放产品; i = (i+1) % n; V(mutex); V(S2); };

采用AND信号量集解决生产者-消费者问题 P： i = 0; while (1) { 生产产品; Swait(s1, mutex); 往Buffer [i]放产品; i = (i+1) % n; Ssignal(s2, mutex); }; Q： j = 0; while (1) { Swait(s2, mutex); 从Buffer[j]取产品; j = (j+1) % n; Ssignal(s1, mutex); 消费产品; };

【思考题】 如果生产者消费者问题中的缓冲区是无界的，又该如何解呢？

解 设信号量S1, mutex 初值均为0 P： i = 0; while (1) Q： j = 0; while (1) { { 生产产品; P(mutex); 往Buffer [i]放产品; i = (i+1) % n; V(mutex); V(S1); }; Q： j = 0; while (1) { P(S1); P(mutex); 从Buffer[j]取产品; j = (j+1) % n; V(mutex); 消费产品; };

【思考题】 有一个仓库，可以存放A和B两种产品，但要求： （1） 每次只能存入一种产品（A或B） （2） －N＜A产品数量－B产品数量＜M。 其中，N和M是正整数。试用P、V操作描述产品A与B的入库过程。 提示：设两个信号量Sa、Sb Sa表示允许A产品比B产品多入库的数量 Sb表示允许B产品比A产品多入库的数量

解 设两个信号量Sa、Sb，初值分别为M-1，N-1 Sa表示允许A产品比B产品多入库的数量 Sb表示允许B产品比A产品多入库的数量 设互斥信号量mutex，初值为1。

A产品入库进程： i = 0; while (1) { 生产产品; P(Sa); P(mutex); A产品入库 V(mutex); V(Sb); }; B产品入库进程： j = 0; while (1) { P(Sb); P(mutex); B产品入库 V(mutex); V(Sa); 消费产品; };

读者/写者问题 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作

第一类：读者优先 如果读者来： 如果写者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待

第一类读者写者问题的解法 设有两个信号量w=1，mutex=1 另设一个全局变量readcount =0

写者： while (1) { P(w); 写 V(w); }; 读者： while (1) { P(mutex); readcount ++; if (readcount==1) P (w); V(mutex); 读 readcount --; if (readcount==0) V(w); };

第一类读者写者问题的解法（一般信号量集） 读者： while(1) { Swait(rcount,1,1; wmutex,1,0); 读； Ssignal(rcount,1); } 写者： while(1) { Swait(wmutex,1,1; rcount,R,0); 写； Ssignal(wmutex,1); } 增加一个限制条件：同时读的“读者”最多R个 wmutex表示“允许写”，初值是1 rcount表示“允许读者数目”，初值为R

【思考题】写优先 修改以上读者写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。 提示，增加一个信号量，用于在写者到达后封锁后续的读者

解 增加一个信号量s，初值为1 读者： while (1) { P(s); P(mutex); readcount ++; if (readcount==1) P (w); V(mutex); V(s); 读 readcount --; if (readcount==0) V(w); }; 写者： while (1) { P(s); P(w); 写 V(w); V(s); };

哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子

解 设fork[5]为5 个信号量，初值为均1 Philosopheri： while (1) { 思考； P(fork[i]); 进食； V(fork[i]); V(fork[(i+1) % 5])； }

分析 以上解法会出现死锁 为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之

采用AND信号量集解决哲学家就餐问题 设fork[5]为5 个信号量，初值为均1 Philosopheri： while (1) { 思考； Swait( fork[i], fork[(i+1) % 5] )； 进食； Ssignal( fork[i], fork[(i+1) % 5] )； }

进程通信 概念 进程通信模式 直接方式 间接方式

概念 所谓进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。 P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息。如果要在进程间传递大量信息则要用Send / Receive原语（高级通讯原语）

进程通信类型 1、共享存储器系统 2、消息传递系统 3、管道通信 (共享文件方式)

1、共享存储器系统 基于共享数据结构的通信方式 诸进程公用某些数据结构，进程通过它们交换信息。如生产者-消费者问题中的有界缓冲区。

基于共享存储区的通信方式 高级通信，在存储器中划出一块共享存储区，进程在通信前，向系统申请共享存储区中的一个分区，并指定该分区的关键字，若系统已经给其它进程分配了这样的分区，则将该分区的描述符返回给申请者。接着，申请者把获得的共享存储分区连接到本进程上，此后可读写该分区。 以上两种方式的同步互斥都要由进程自己负责。

2、消息传递系统 进程间的数据交换以消息为单位，程序员利用系统的通信原语实现通信。操作系统隐藏了通信的实现细节，简化了通信程序编制的复杂性。因而得到广泛应用。

消息传递系统可分为： 直接通信：发送进程直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。 也称为消息缓冲通信

间接通信：发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消息。 也称信箱通信。在网络中称为电子邮件系统。

思考 两种方式的主要区别？ 前者需要两进程都存在，后者不需要。

3、管道通信 字符流方式写入读出 先进先出顺序 所谓管道，是指用于连接一个读进程和一个写进程的文件，称pipe文件。向管道提供输入的进程（称写进程），以字符流的形式将大量数据送入管道，而接受管道输出的进程（读进程）可从管道中接收数据。该方式首创于UNIX，它能传送大量数据，被广泛采用。 发送进程 接收进程 字符流方式写入读出 先进先出顺序

消息缓冲通信的实现 在操作系统空间设置一组缓冲区。 当发送进程需要发送消息时，执行send系统调用，产生访管中断，进入操作系统。 操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。 发送进程返回到用户态继续执行。

在以后某个时刻，当接收进程执行到receive接收原语时，也产生访管中断进入操作系统。 由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行

图示 PCB M: N: 接收进程 R 发送进程 S 消息 消息链指针 ...... Receive(N) Send(R, M) SIZE:消息长度 TEXT:消息正文 消息链指针 Receive(N) M: N: 接收进程 R 发送进程 S 消息

消息缓冲区结构 type messageBuffer=record sender ;//发送者ID size ;//消息长度 text ;//消息正文 next ;//消息队列指针 end

PCB中有关通信的数据项 type PCB=record … mq ; //消息队列首指针 mutex; //消息队列互斥信号量 sm ; //消息队列资源信号量 end

用P、V操作来实现Send原语 send（R,M） begin 在OS中分配M.size大小的缓冲区t; 将M中的内容复制到t; 得到进程R的PCB的指针q； P(q.mutex); 将t挂到队列q.mq队尾； V(q.mutex); V（q.sm); end

用P、V操作来实现Receive原语 Receive(N） begin 得到本进程PCB的指针q； P(q.sm); P(q.mutex); 从q.mq队首取下一个缓冲区t； V(q.mutex); 将t的内容复制到N，并释放t end

信箱通信的实现 信箱使用规则 若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被唤醒 若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被唤醒

Send实现 send（MailBox，M）：把信件M送到指定的信箱MailBox中 步骤： 查找指定信箱MailBox ； 若信箱已满置发送信件进程为“等信箱”状态；

Receive实现 receive（ MailBox ，X）：从指定信箱MailBox中取出一封信，存放到指定的地址X中 步骤： 若信箱中无信件则置接收信件进程“等信件”状态；

无死锁哲学家就餐问题 解1 设fork[5]为5 个信号量，初值均为1 设信号量Mutex、W ，初值为1 设有全局变量Count 初值为0 Mutex用于对临界资源Count 的访问

Philosopheri： while (1) { 思考； P(Mutex) Count++; if(Count>=4)P(W) V(Mutex) P(fork[i]); P(fork[(i+1) % 5])； 进食； V(fork[i]); V(fork[(i+1) % 5])； P(Mutex) Count--; if(Count==3)V(W) V(Mutex) }

无死锁哲学家就餐问题 解2 设fork[5]为5 个信号量，初值为均1 设信号量S ，初值为4 S用于封锁第5个哲学家

Philosopheri： while (1) { 思考； P(S) P(fork[i]); P(fork[(i+1) % 5])； 进食； V(fork[i]); V(fork[(i+1) % 5])； V(S) }

无死锁哲学家就餐问题 解3 设fork[5]为5 个信号量，初值为均1

Philosopher1： while (1) { 思考； P(fork[1]); P(fork[2])； 进食； V(fork[2]); V(fork[1])； } Philosopher2： while (1) { 思考； P(fork[3]); P(fork[2])； 进食； V(fork[2]); V(fork[3)； }

习题 进程A1、A2，。。。An1通过m个缓冲区向进程B1、B2、。。。Bn2不断发送消息。发送和接收工作遵循下列规则： （1） 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度 （2） 对每个消息，B1，B2，Bn2都须各接收一次，读入各自的数据区内 （3） m个缓冲区都满时，发送进程等待，没有可读消息时，接收进程等待。 试用P、V操作组织正确的发送和接收工作。

提示：每个缓冲区只要写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2个缓冲区，而每个接收者只要读它自己的缓冲区。 Sin[n2]=m Sout[n2]=0;

解 先将问题简化： 设缓冲区的大小为1 有一个发送进程A1 有二个接收进程B1、B2 设有信号量Sin[1] 、Sin[2] 初值为1 设有信号量Sout[1] 、Sout[2] 初值为0

A1: while (1) { P(Sin[1]); P(Sin[2]); 将数据放入缓冲区 V(Sout[1]); V(Sout[2]); } Bi： while (1) { P(Sout[i]); 从缓冲区取数 V(Sin[i]); }

向目标前进一步 设缓冲区的大小为m 有一个发送进程A1 有二个接收进程B1、B2 设有信号量Sin[1] 、Sin[2] 初值为m 设有信号量Sout[1] 、Sout[2] 初值为0

A1: while (1) { P(Sin[1]); P(Sin[2]); P(mutex); 将数据放入缓冲区 V(mutex); V(Sout[1]); V(Sout[2]); } Bi： while (1) { P(Sout[i]); P(mutex); 从缓冲区取数 V(mutex); V(Sin[i]); };

到达目标 设缓冲区的大小为m 有n1个发送进程A1….An1 有n2个接收进程B1…Bn2 设有n2个信号量Sin[n2] 初值均为m 设有n2个信号量Sout[n2] 初值均为0

Aj: while (1) { for(i=1;i<=n2;i++) P(Sin[i]); P(mutex); 将数据放入缓冲区 V(mutex); for(i=1;i<=n2;i++) V(Sout[2]); } Bi： while (1) { P(Sout[i]); P(mutex); 从缓冲区取数 V(mutex); V(Sin[i]); };

死锁的概念 死锁举例 产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法

死锁举例 例1： 两个小孩在一起玩耍，一个在玩皮球，另一个玩自动步枪，如果这两个小孩都要对方手中的玩具，而又不肯先放掉自己拿着的玩具，这时就发生了僵持局面。

例2： 设系统有一台打印机和一台扫描仪，进程P1、P2并发执行，在某时刻T，进程P1和P2分别占用了打印机和扫描仪。在时刻T1（T1>T），P1又要申请扫描仪，但由于扫描仪被P2占用，P1只有等待。在时刻T2（T2>T），P2又申请打印机，但由于打印机被P1占用，P2只有等待。如此两进程均不能执行完成。称这种现象为死锁。

在生产者-消费者问题中将生产者进程的两个P操作颠倒时会发生死锁。 例3： 在生产者-消费者问题中将生产者进程的两个P操作颠倒时会发生死锁。 将消费者进程的两个P操作颠倒时也会发生死锁。

死锁的定义 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到该资源，这种现象称为进程死锁，这一组进程就称为死锁进程 死锁（Deadlock） 饥饿（Starvation）

判断 1 参与死锁的所有进程都占有资源 2 参与死锁的所有进程均正在等待资源 3 参与死锁的所有进程中至少有两个进程占有资源 2 参与死锁的所有进程均正在等待资源 3 参与死锁的所有进程中至少有两个进程占有资源 4 参与死锁的进程至少有两个

关于死锁的一些结论 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃 参与死锁的进程最少是两个 （两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃

产生死锁的必要条件 四个必要条件： 互斥条件：涉及的资源是非共享的。 不剥夺条件：不能强行剥夺进程拥有的资源。 部分分配条件：进程在等待一新资源时继续占有已分配的资源。 环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。

处理死锁的基本方法 1、预防死锁： 通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。 较易实现，广泛使用，但由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。

2、避免死锁： 不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。 实现较难，只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。

3、检测死锁： 事先并不采取任何限制，也不检查系统是否进入不安全区，允许死锁发生，但可通过检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发生的死锁清除掉

4、解除死锁： 与检测死锁相配套，用于将进程从死锁状态解脱出来。 常用的方法是撤消或挂起一些进程。以回收一些资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态。 实现难度大，但可获得较好的资源利用率和系统吞吐量。

死锁的预防和避免 死锁的预防 系统的安全状态 利用银行家算法避免死锁

死锁的预防 在系统设计时确定资源分配算法，保证不发生死锁 具体的做法是破坏产生死锁的四个必要条件之一

破坏部分分配条件 系统要求所有进程要一次性地申请在整个运行过程中所需的全部资源。若系统有足够资源则完全分配。

优点：简单、易于实现且安全。 缺点： 一个用户在作业运行之前可能提不出他的作业将要使用的全部设备。 用户作业必须等待，直到所有资源满足才能运行。实际上某些资源可能要到运行后期才会用到。 一个作业运行期间，对某些设备的使用时间很短，甚至不会用到。如：当用户作业出错时才需要打印机输出错误信息，但采用静态分配法必须把打印机分配给该作业，并长期占用。采用该方法对系统来说是非常浪费的。

破坏不可剥夺条件 一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源。以后需要时再重新申请。 实现复杂、要付出很大的代价。

破坏环路条件 系统中的所有资源都有一个确定的唯一号码，所有分配请求必须以序号上升的次序进行。 例如：系统中有下列设备：输入机（1），打印机（2），穿孔机（3），磁带机（4），磁盘（5）。有一进程要先后使用输入机、磁盘、打印机，则它申请设备时要按输入机、打印机、磁盘的顺序申请。

优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。 缺点：进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费。

系统的安全状态 死锁避免定义 在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配

安全状态 如果系统能按某种顺序（如P4，P1，…,Pn, 称为安全序列）为每个进程分配其所需的资源，直至所有进程都能运行完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。

安全状态举例 有三个进程p1,p2,p3，有12台磁带机。P1共要求10台，P2共要求4台，P3共要求9台。在T0时刻，p1,p2,p3分别获得5、2、2台，尚有3台空闲。

图 经分析，在T0时刻，系统是安全的。 因为存在一个安全序列p2、p1、p3。见下图。 进程 最大需求 已分配 还需 可用 p1 10 5 4 2 p3 9 7

由安全状态向不安全状态的转换 如果不按安全序列分配资源，则系统可能会由安全状态进入不安全状态。如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台）。将导致死锁。可见当P3申请资源时，尽管系统中有资源也不能分给它。

系统进入不安全状态 进程 最大需求 已分配 还需 可用 p1 10 5 2 p2 4 p3 9 3 6

利用银行家算法避免死锁 最有代表性的避免死锁算法，由Dijkstra提出。 1、银行家算法中的数据结构 可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。 如： A B C 5 2 3

最大需求矩阵Max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。 B C P1 5 6 2 P2 3 1 P3 4 P4

分配矩阵Allocation 。n*m矩阵，表示每个进程分配的资源数。 B C P1 2 1 P2 P3 P4 3

需求矩阵Need 。n*m矩阵，表示每个进程还需要各类资源数。 A B C P1 3 5 2 P2 1 P3 P4

例 设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图

银行家算法描述 当进程pi提出资源申请时，系统执行下列步骤： （1）若Request[i]≤Need[i],转（2）； 否则错误返回 （2）若Request[i]≤Available, 转（3）；否则进程等待

（4）执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待 (3）假设系统分配了资源，则有： Available:=Available-Request[i]; Allocation[i]:=Allocation[i]+Request[i]; Need[i]:=Need[i]-Request[i] （4）执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待

安全性算法 为进行安全性检查，定义数据结构： Work:ARRAY[0..m-1] of integer; Finish:ARRAY[0..n-1] of Boolean; m代表资源的数量，n代表进程的数量

安全性算法步骤 (1) Work:=Available; Finish:=false; (2) 寻找满足下列条件的i： a). Finish[i]=false; b). Need[i]≤Work; 如果不存在，则转(4)

(3) Work:=Work+Allocation[i]; Finish[i]:=true; 转(2) (4) 若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态

T0时刻的安全性检查 T0时刻可以找到一个安全序列{p1,p3,p4,p2,p0}. 系统是安全的。

P1发出请求Request(1,0,2)，执行银行家算法 例1：T0时刻P1请求资源

可以找到一个安全序列{p1,p3,p4,p0,p2}. 系统是安全的，可以将P1的请求分配给它。 执行安全性算法

例2：P4请求资源 P4发出请求Request(3,3,0), 执行银行家算法 Available=2 3 0 不能通过算法第2步（ Request[i]≤Available ），所以P4等待。

例3：P0请求资源 Request（0，2，0），执行银行家算法

进行安全性检查 Available{2,1,0}已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配

练习：有三类资源A(17)、B(5)、C(20)。有5个进程P1—P5。T0时刻系统状态如下： (2)、T0时刻，P2: Request(0,3,4)，能否分配，为什么？ (3)、在(2)的基础上P4：Request(2,0,1)，能否分配，为什么？ (4)、 在(3)的基础上P1：Request(0,2,0)，能否分配，为什么？ 最大需求 已分配 P1 5 5 9 2 1 2 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4

解：(1) T0时刻的出安全系列 先求出Need和Work Work=2 3 3 最大需求 已分配 Need P1 5 5 9 2 1 2 5 5 9 2 1 2 3 4 7 P2 5 3 6 4 0 2 1 3 4 P3 4 0 11 4 0 5 0 0 6 P4 4 2 5 2 0 4 2 2 1 P5 4 2 4 3 1 4 1 1 0 A(17)、B(5)、C(20) Work=2 3 3

Work=2 3 3 Work Allocation Need W+A Finish P5 2 3 3 3 1 4 1 1 0 5 4 7 2 3 3 3 1 4 1 1 0 5 4 7 T P4 2 0 4 2 2 1 7 4 11 P3 7 4 11 4 0 5 0 0 6 11 4 16 P2 4 0 2 1 3 4 15 4 18 P1 15 4 18 2 1 2 3 4 7 17 5 20

(2) P2: Request(0,3,4) 因（ Available =2 3 3）< Request(0,3,4) 所以不能分配

(3) P4：Request(2,0,1) Available =2 3 3 Allocation Need Available P1 2 1 2 3 4 7 0 3 2 P2 4 0 2 1 3 4 P3 4 0 5 0 0 6 P4 0 2 0 P5 3 1 4 1 1 0 有安全序列P4 P5 P3 P2 P1 可以分配 Work Allocation Need W+A Finish P4 0 3 2 4 0 5 0 2 0 4 3 7 T P5 3 1 4 1 1 0 7 4 11 P3 0 0 6 11 4 16 P2 11 4 16 4 0 2 1 3 4 15 4 18 P1 15 4 18 2 1 2 3 4 7 17 5 20

(4) P1：Request(0,2,0) Allocation Need Available P1 2 3 2 3 2 7 0 1 2 2 3 2 3 2 7 0 1 2 P2 4 0 2 1 3 4 P3 4 0 5 0 0 6 P4 0 2 0 P5 3 1 4 1 1 0 0 1 2 已不能满足任何进程的需要，不能分配

死锁的检测和解除 死锁检测： 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行

检测时机： 当进程等待时检测死锁 （其缺点是系统的开销大） 定时检测 系统资源利用率下降时检测死锁

死锁的解除 重要的是以最小的代价恢复系统的运行。方法如下： 1）重新启动 2）撤消进程 3）剥夺资源 4）进程回退

资源分配图 用有向图描述进程的死锁 准确、形象 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例

二元组G=（V，E） V：结点集，分为P，R两部分 P={p1,p2,…,pn} R={r1,r2,…,rm} E：边的集合，其元素为有序二元组 (pi,rj)或(rj,pi)

表示法 资源类（资源的不同类型） 用方框表示 资源实例（存在于每个资源中） 用方框中的黑圆点（圈）表示 进程 用圆圈中加进程名表示

分配边： 资源实例进程的一条有向边 申请边： 进程资源类的一条有向边

例

死锁定理 如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件

资源分配图化简 1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点 2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边 3）重复以上步骤，若所有进程成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简化的。 死锁状态的充分条件是：当且仅当资源分配图是不可完全简化的。

有环有死锁

有环无死锁

教材P132第17题解答 P0请求：Reqest(0,1,0) Allocation Need Available P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1

试探分配后 2 2 0 P1 5 2 2 P2 7 3 3 P4 7 3 5 P0 7 5 5 10 5 7 Allocation Need 2 2 0 P1 5 2 2 P2 7 3 3 P4 7 3 5 P0 7 5 5 10 5 7 Allocation Need Available P0 0 2 0 7 3 3 2 2 0 P1 3 0 2 P2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1

有安全系列如下 Work Allocation Need W+A Finish P1 2 2 0 3 0 2 0 2 0 5 2 2 T 2 2 0 3 0 2 0 2 0 5 2 2 T P3 2 1 1 0 1 1 7 3 3 P4 0 0 2 4 3 1 7 3 5 P0 7 5 5 P2 6 0 0 10 5 7

习题1 已分配的资源 最大需求量 A B C A B C P1 0 1 0 7 5 3 P2 2 0 0 3 2 2 已分配的资源 最大需求量 A B C A B C P1 0 1 0 7 5 3 P2 2 0 0 3 2 2 P3 3 0 2 9 0 2 P4 2 1 1 2 2 2 P5 0 0 2 4 3 3 剩余资源 A B C 3 3 2

问题:此状态是否为安全状态，如果 是, 则找出安全序列 在此基础上 P2 申请（1，0，2）能否分配？为什么？ P5 申请（3，3，0）能否分配？为什么？ P1 申请（0，2，0）能否分配？为什么？

习题2 1、 一台计算机共8台磁带机，由N个进程共享，每个进程最多要3台，问N为多少时不会有死锁，为什么？ 2、有R1(2)、R2(1)两类资源和两个进程P1、P2，两个进程均以 申请R1申请R2申请R1释放R1释放R2释放R1 顺序使用资源，求可能达到的死锁点，并画出此时的资源分配图。

解 当两个进程都执行完第1步后，无论哪个进程执行完第2步，以后，这两个进程再申请资源时就会死锁。 P1 P2 R1 R2