导图社区 第七章 设备管理
- 34
- 0
- 0
- 举报
第七章 设备管理
这是一篇关于第七章 设备管理的思维导图，主要内容包括：第一节 I/O设备管理的基本概念，第二节 I/O硬件和I/O软件的组成，第三节 I/O设备控制方式，第四节 设备分配与回收，第五节 磁盘调度策略，第六节 缓冲技术，第七节 虚拟设备技术。
编辑于2025-03-24 06:13:36- 操作系统
- 自考
- 设备管理
- 第一章 操作系统概论
这是一篇关于第一章 操作系统概论的思维导图，包含考点1至考点17，系统且全面地覆盖了操作系统概论的核心知识点。从操作系统的定义、特征、观点、功能，到不同类型的操作系统，逻辑清晰，层次分明.
- 数据人主播
这是一篇关于数据人主播的思维导图，主要内容包括：概述，数字人生成方式，语音驱动与口型同步，动作捕捉与交互，场景与直播集成。
- 《马克思主义基本原理概论》
这是一篇关于《马克思主义基本原理概论》的思维导图，主要内容包括：与时俱进是，哲学的基本问题是，空间是物质运动的，实践作为主体有意识、有目的的活动，强调的是实践具有，下列范畴揭示事物联系和发展中确定的和不确定的两种趋势的是，人类社会与自然界有本质区别。。
第七章 设备管理
社区模板帮助中心，点此进入>>
- 第一章 操作系统概论
这是一篇关于第一章 操作系统概论的思维导图，包含考点1至考点17，系统且全面地覆盖了操作系统概论的核心知识点。从操作系统的定义、特征、观点、功能，到不同类型的操作系统，逻辑清晰，层次分明.
- 数据人主播
这是一篇关于数据人主播的思维导图，主要内容包括：概述，数字人生成方式，语音驱动与口型同步，动作捕捉与交互，场景与直播集成。
- 《马克思主义基本原理概论》
这是一篇关于《马克思主义基本原理概论》的思维导图，主要内容包括：与时俱进是，哲学的基本问题是，空间是物质运动的，实践作为主体有意识、有目的的活动，强调的是实践具有，下列范畴揭示事物联系和发展中确定的和不确定的两种趋势的是，人类社会与自然界有本质区别。。
- 相似推荐
- 大纲
操作系统
第一章 操作系统概论
第二章 操作系统运行环境与运行机制
第三章 进程/线程模型
第四章 进程/线程调度
第八章 进程同步机制与死锁
第五章 存储管理
第六章 文件系统
第七章 设备管理
第一章 操作系统概论
第一节 操作系统概论
考点1 计算机系统
计算机系统包括
硬件（子）系统
硬件系统是计算机系统赖以工作的实体。
中央处理器（CPU=运算器+控制器）
内存储器（又称主存）
外存储器（磁盘、磁带等）
输入输出设备（键盘、鼠标、显示器、打印机等）
软件（子）系统
软件系统保证计算机系统按用户指定的要求协调工作（灵魂）。
软件系统 = 程序+数据
计算机系统的资源包括两大类：
硬件资源
软件资源
考点2 操作系统的定义
操作系统是计算机系统中的一个系统软件，它是这样一些程序模块的集合：
它们能有效地组织和管理计算机系统中的硬件及软件资源
合理地组织计算机工作流程
控制程序的执行
向用户提供各种服务功能，使得用户能够灵活、方便、有效地使用计算机
使整个计算机系统能高效地运行
考点3 操作系统的特征
1.并发性
含义:操作系统能够同时管理多个任务的执行。
注意“并发”与“并行”的区别：
并发
微观上任务交替执行（如单核CPU通过时间片轮转实现多任务）。
并行
真正同时执行（需多核硬件支持）。
示例
：边下载文件边编辑文档，系统在进程/线程间快速切换。
2.共享性
含义:资源被多个进程或用户共同使用，分为两种形式：
互斥共享
资源某一时刻仅允许一个进程使用（如打印机）。
同时访问
资源可被多个进程同时使用（如只读文件）。
关键问题
通过同步机制避免资源竞争（如锁、信号量）。
3.虚拟性
含义：将物理资源抽象为逻辑上的多份，使每个用户/进程仿佛独占资源。
典型应用：
虚拟内存：将磁盘空间扩展为“内存”，进程感知到连续地址空间。
CPU虚拟化：通过分时复用，每个进程感觉独占CPU。
4.异步性
含义：进程的执行顺序和完成时间不可预知（如因资源竞争或中断），但结果需保证正确性。
核心要求：系统必须处理不确定性，通过同步机制确保结果一致性。
考点4 研究操作系统的观点
1、软件的观点
操作系统是一种大型软件系统，它是多种功能程序的集合。
有软件的外在特性和内在特性。
2、资源管理的观点
在计算机系统中的硬件和软件资源可以分成以下几部分：
中央处理器（CPU）、存储器（内 存和外存）、外部设备和信息（文件）。
3、进程的观点
操作系统看作由多个可以同时独立运行的程序和一个对这些程序进行协调的核心所组成
4、虚机器的观点
是从系统功能分解的角度出发，考虑操作系统的结构。
5、服务提供者的观点
考点5 操作系统的功能
1、进程管理（处理器管理）
进程控制
进程同步
进程间通信
调度
2、存储管理
内存的分配与回收
存储保护
内存扩充
3、文件管理
文件存储空间管理
目录管理
文件系统的安全性
4、设备管理
5、用户接口
第二节 操作系统的体系结构
一、Windows操作系统的体系结构
是分层的模块系统，主要层次有硬件抽象层HAL、内核、执行体 和大量的子系统集合
内核
硬件抽象层HAL
执行体
系统进程和系统线程
二、UNIX操作系统的体系结构
三、Linux操作系统的体系结构
四、Android操作系统的体系结构
考点17 操作系统结构的体系结构
1、整体式结构
2、层次式结构
3、微内核（客户/服务器）结构
（1）运行在内核态的内核
（2）运行在用户态的并以客户/服务器方式运行的进程层
4、外核结构
第三节 操作系统的发展
考点6 不同时期的操作系统
（1946年-1950年代末）
1.手工操作
无操作系统，用户直接操作硬件，资源利用率极低。
（1950年代末-1960年代中期）
2.监控程序（早期批处理）
引入监督程序，实现作业自动过渡，但仍为单道程序。
（1960年代中期-1970年代中期）
多任务并发、资源共享，分时技术实现交互式操作。
3.多道批处理
4.分时与实时系统
（1970年代中期-1990年代）
5.UNIX通用操作系统
（2000年至今）
支持多架构、云计算、AI融合，覆盖移动端与分布式场景。
6.个人计算机操作系统
Android操作系统
7.当代操作系统两大发展方向——宏观应用与微观应用：
大型系统：分布式操作系统、机群操作系统
微型系统：嵌入式操作系统
第四节 操作系统的分类
考点7 批处理操作系统
收到一定数量的用户作业后，组成一批作业，输入到计算机，在系统中形成一个连续的、 自动转接的作业流
优点：
成批处理、系统资源利用率高、作业吞吐率高、作业流程自动化较高、作业吞吐量大
缺点：
用户不能直接与计算机交互，不适合调试程序
分类：
简单批处理系统和多道批处理系统
为了提高硬件资源的利用率，批处理系统发展为更加高级的多道批处理系统，关键技术就是多道程序运行、假脱机（SPOOLing）技术等
假脱机技术，全称是“同时的外部设备联机操作”，借助硬件通道技术，实现了输入输出操作和处理器动作的自动并行处理。
考点8 分时操作系统
分时操作系统出现在批处理操作系统之后
弥补批处理方式不能向用户提供交互式快速服务的缺点。
用户通过终端交互式地向系统提出命令请求
系统接受用户的命令之后，采用时间片轮转方式处理服务请求，并通过交互方式在终端上向用户显示结果。
用户根据系统送回的处理结果发出下一道交互命令。
将CPU的时间划分成若干个小片段，称时间片。
操作系统以时间片为单位，轮流为每个终 端用户服务
分时操作系统具有
多路性
交互性
独占性
及时性
考点9 实时操作系统
实时操作系统（RTOS：Real Time Operating System）：
在规定时间内，及时响应外部事 件请求，完成事件处理，控制实时设备和实时任务协调一致工作。
实时系统为实现硬实时或软实时的要求，需要具备以下能力：
（1）实时时钟管理
（2）过载防护
（3）高可靠性
考点10 个人计算机操作系统
个人计算机操作系统（Personal Computer Operating System）是一种单用户的操作系统
个人计算机操作系统的主要特点：
计算机在某一时间内为单个用户服务
采用图形界面人机交互的工作方式，界面友好
使用简单方便
考点11 网络操作系统
网络操作系统（Network Operating System）是基于计算机网络的、在各种计算机操作系统之上按网络体系结构协议标准设计开发的软件
考点12 分布式操作系统
分布式系统（Distributed System）将大量的计算机通过网络连结在一起，获得极高的运 算能力及广泛的数据共享
分布式操作系统（Distributed Operating System）是网络操作系统的更高级形式，分布式操作系统除了保持了网络操作系统的各种功能之外，还具备如下的特征：
（1）系统中的所有主机使用统一的操作系统
（2）资源深度共享。
（3）透明性。
（4）自治性
考点13 嵌入式操作系统
嵌入式操作系统用于工业控制、交通管理、信息家电等嵌入式系统，设计紧凑、高效，只 保留运行在其上的特定应用程序所需要的功能
嵌入式操作系统的特点：
（1）系统内核小。
（2）专业性强。
（3）系统精简。
（4）高实时性。
（5）多任务的操作系统。
考点14 其他类型操作系统
（1）大型机操作系统
（2）服务器操作系统
（3）多处理操作系统
（4）移动计算操作系统
（5）传感器节点操作系统
（6）智能卡操作系统
第五节 操作系统设计
考点15 操作系统的设计过程及目标
操作系统的设计过程可分为三个部分
功能设计
算法设计
结构设计
一个高质量的操作系统应具有
可靠性、高效性、易维护性、易移植性、安全性和简明 性等特征
考点16 操作系统结构研究的目标
（1）系统模块化
将模块看做一组数据结构以及定义在其上的一组操作
（2）模块标准化
①标准设计，模块规格划一，遵循相同模块构造准则和模块（构件）标准
②总结、提炼基本成份并定型化
（3）通信规范化
模块之间接口清晰划一，联系方式统一
第二章 操作系统的运行环境
考点1 计算机系统的层次结构
所有的子系统都可以包括在硬件（子）系统和软件（子）系统这两个层次中
第一节 处理器
一、处理器的构成与基本工作方式
CPU一般由运算器、控制器、一系列的寄存器以及高速缓存构成。
运算器
实现指令中的算术和逻辑运算，是计算机计算的核心。
控制器
负责控制程序运行的流程，包括取指令、维护处理器状态、处理器与内存的交互等。
寄存器
是一种暂时存储器件，用于处理器执行指令的过程中暂存数据、地址以及指令信息
1.处理器中的寄存器
常见的用户可见寄存器：
1）数据寄存器
2）地址寄存器
3）条件码寄存器
常见的控制和状态寄存器：
1）程序计数器
（Program Counter，PC），它记录了将要取出的指令的地址；
2）指令寄存器
（ Instruction Register，IR），包含了最近取出的指令；
3）程序状态字
（Program Status Word，PSW），它记录了处理器的运行模式信息等。
2.指令执行的基本过程
指令执行的过程
一个指令周期=取指令+执行指令。
取指令
处理器每次从存储器中读取一条指令，程序计数器+1。
执行指令
存储在处理器的指令寄存器，处理器于是解释并执行这条指令。
指令大致分成五类：
1）访问存储器指令：
它们负责处理器和存储器之间的数据传送；
2）I/O指令：
它们负责处理器和I/O模块之间的数据传送和命令发送；
3）算术逻辑指令：
有时又称为数据处理指令，用以执行有关数据的算术和逻辑操作；
4）控制转移指令：
这种指令可以指定一个新的指令的执行起点；
5）处理器控制指令 ：
这种指令用于修改处理器状态，改变处理器工作方式等。
二、特权指令和非特权指令
单用户、单任务方式下使用的微型计算机系统，可使用该计算机指令系统中的全部指令。
多用户或多任务的多道程序设计环境中，指令两部分：特权指令和非特权指令
特权指令
在指令系统中那些只能由操作系统使用的指令。
非特权指令
大家（操作系统、普通用户）都能使用的。
三、处理器的工作状态
1.管态和目态
根据程序对资源和指令的使用权限而将处理器设置为不同状态，多数系统将处理器工作状态划分为内核态和用户态
内核态：
一般指操作系统管理程序运行的状态，具有较高的特权级别，又称为管态、特权态、 系统态或核心态。
用户态
一般指用户程序运行时的状态，具有较低的特权级别，又称为目态、普通态
2.处理器工作状态的转换
（1）目态到管态的转换
用户态到内核态的转换
其转换的唯一途径是通过中断
（2）管态到目态的转换
内核态到用户态的转换
可通过设置PSW指令（修改程序状态字）实现
3.限制用户程序执行的特权指令
四、程序状态字（PSW）
第二节 计算机系统硬件部件
一、存储系统
中央处理器能直接访问的唯一的存储空间是主存储器
作业必须把它的程序和数据存放在主存储器中才能运行
1.存储器的类型
（1）类型
两类存储器
读写型的存储器
只读型的存储器
（2）存储分块
存储的最小单位称为“二进位” ，它包含的信息为0或1
最小编址单位是字节，一个字节一般包含八个二进位
1024个字节称为1KB，1024个1KB称为1MB，1024个1MB称为1G
2.存储器的层次结构
（1）容量、速度和成本的匹配
采用层次化的存储体系结构解决权衡问题：
容量、速度和成本
沿层次下降时，每比特的价格将下降，容量将增大，速度将变慢而处理器的访问频率也将下降
（2）存储访问局部性原理
3.存储器保护
对主存中的信息加以保护，使操作系统不被破坏，是其正确运行的基本条件之一 要实现存储保护，必须要有硬件的支持
界地址寄存器（界限寄存器）
存储键
二、I/O部件
1.I/O结构
考点11 I/O结构
早期的计算机系统中，外部设备的控制器通过I／O硬件结构与中央处理器连接
这种方法中，中央处理器定期轮询各个I/O设备控制器的状态
有I/O处理请求，中央处理器就处理I/O操作，直到处理完毕
2.通道
考点12 通道
通道独立于CPU，专门负责数据I/O传输工作的处理单元，又称为I/O处理机
对外部设备实行统一的管理
代替CPU对I/O操作进行控制
使CPU和外部设备可以并行工作
通道可以实现中央处理器和各种外部设备并行工作
3.DMA技术
考点13 直接存储访问技术
通过系统总线中的一个独立控制单元，自动地控制成块数据在内存和I/O单元之间的传送， 处理器需要读写一整块数据的时候，它给DMA控制单元发送一条命令，命令中包含I/O设备的编 址、开始读或写的主存编址、需要传送的数据长度等信息，发送完一条命令之后，就可以处理 其他的事情，DMA控制器将自动管理整块数据的传送，当这个传送过程完成后，它会给处理器发一个中断这样处理器只开始传送和传送结束时关注一下就可以了。
4.缓冲技术
考点14 缓冲技术
缓冲区是硬件设备之间进行数据传输时，专门用来暂存这些数据的一个存储区域 ，三种情况下采用
处理器与主存储器之间
处理器和其它外部设备之间
设备与设备之间的通信
目的：为了解决部件之间速度不匹配的问题
三、时钟部件
考点15 时钟
时钟可以为计算机完成以下工作
在多道程序运行，时钟可以发现死循环，防止机时的浪费
在分时系统中，用时钟实现时间片轮转运行
在实时系统中，按要求的时间间隔输出信号控制设备
定时唤醒外部事件
记录用户和系统所需要的绝对时间，即年、月、日
时钟分成硬件时钟和软件时钟
第三节 中断机制
一、中断与异常的概念
考点8 中断的概念
1.中断与异常
（1）中断的概念
中断是CPU对系统中或系统外发生的异步事件的响应
当发生某个异步事件后，中断处理器对当前程序的执行，而转去处理该异步事件，处理完 了之后，处理器再转回原程序的中断点继续执行
中断的作用
解决了主机和外设并行工作的问题
消除了因外设的慢速而使得主机等待的现象
为多机操作和实时处理提供了硬件基础
充分发挥处理器的使用效率
提高系统的实时能力
（2）异常
异步事件是指无一定时序关系的随机发生的事件
2.中断与异常的分类
中断的分类
强迫性中断：
程序所不期望发生的，具有随机性
程序性中断：
运行程序本身的中断时钟中断
输入输出（I/O）中断：
由I/O控制器产生
控制台中断
硬件故障中断
自愿性中断
中断系统分为两大组成部分
硬件中断装置
负责捕获中断源发出的中断请求，并响应中断源将处理器控制权移交给特定的中断处理程序
软件中断处理程序
针对中断事件的性质而执行相应的一系列操作
二、中断系统
1.中断请求的接收
2.中断响应
3.中断处理
4.几种典型中断的处理
（1）I/O中断
由I/O设备的控制器或者通道发出
I/O操作正常结束
I/O
（2）时钟中断
时钟中断处理程序通常要做较多的与系统运转、管理和维护相关的工作
（3）硬件故障中断
硬件故障中断处理程序需要做的工作，主要包括
保存现场，使用一定的手段警告管理员并提供一些辅助的诊断信息
在高可靠的系统中，中断处理程序还需要评估系统的可用性，尽可能恢复系统
（4）程序性中断
（5）系统服务请求（自愿性中断）
系统服务请求一般由处理器提供的专用指令（又称访管指令）来激发
三、中断优先级、中断屏蔽与中断嵌套
1.多级中断与中断优先级
多级中断系统表现为有多根中断请求线从不同设备连接到中断逻辑线路上
连接在不同中断请求线上的中断信号，表示它们有不同的中断级别
中断信号的级别代表了该中断信号是否具有被优先处理的特权，以及这个特权的大小
2.中断屏蔽
可以允许或者禁止中断系统对某些类别中断的响应
3.中断嵌套
如果一个中断的处理过程中又发生了中断，那么将引起多个中断处理问题。
第四节 系统调用
一、系统调用简介
1.系统调用与函数调用的区别
（1）运行在不同和系统状态
（2）状态的转换
（3）返回问题
（4）嵌套调用
2.系统调用的分类
（1）进行控制类系统调用
（2）文件操作类系统调用
（3）进程通信类系统调用
（4）设备管理类系统调用
（5）信息维护类系统调用
3.系统调用与库函数、API、内核函数的关系
二、系统调用的处理过程
第三章 进程线程模型
第一节 多道程序设计
一、程序的顺序执行
1.顺序性
2.封闭性
3.程序执行结果的确定性
4.程序执行结果的可再现性
二、程序的并发执行
1.在执行期间并发程序相互制约
2.程序与计算不现一一对应
3.并发程序的执行结果不可再现
4.程序的并行执行与程序的并发执行
三、多道程序设计
1.多道程序设计技术的引入
2.多道程序设计环境的特点
3.多道程序设计的缺陷
第二节 进程
一、进程的定义
定义
进程是具有一定独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位
分类
系统进程
执行操作系统程序
优先级通常高于一般用户进程的优先级
用户进程
运行用户程序
1.进程与程序的联系与区别
进程与程序的联系和区别
1）进程和程序的联系
• 程序是构成进程的组成部分之一
• 进程是由程序、数据和进程控制块（PCB）三部分组成的
• 一个进程的运行目标是执行它所对应的程序
2）进程和程序的区别
• 程序是静态的，而进程是动态的
• 进程是程序的一个执行过程
• 程序的存在是永久的，进程存在生命周期，一个程序可以产生多个进程
2.可再入程序
3.进程的特征
进程的特征
进程是一个可拥有资源的独立单位
进程同时又是一个可以独立调度和分派的基本单位
进程具有以下特性：
1）并发性：一个进程可以同其他进程一道向前推进
2）动态性：进程有其生命周期，且进程的状态是不断变化的
3）独立性：一个进程是一个相对完整的资源分配单位
4）交往性：一个进程在运行过程中可能会与其他进程发生直接的或间接的相互作用
5）异步性：每个进程按照各自独立的、不可预知的速度向前推进
6）结构性：一个进程由程序、数据和进程控制块三部分组成
二、进程的状态与转换
1.三状态进程模型
2.五状态进程模型
3.七状态进程模型
考点2 进程状态及状态转换
三状态进程模型
（1）运行状态（Running）
进程已获得CPU，并且在CPU上执行的状态
（2）就绪状态（Ready）
进程已经具备运行条件，但没有获得CPU的状态
（3）阻塞状态（Blocked）
进程因等待某种事件发生而暂时不能运行的状态
三状态模型的状态转换条件
（1）就绪→运行
进程调度程序把处理机分配给某个就绪进程
（2）运行→就绪
规定的运行时间片用完
（3）运行→阻塞
运行状态的进程等待其他资源
（4）阻塞→就绪
阻塞进程在其被阻塞的原因获得时解除阻塞
五状态进程模型：
（1）运行状态（Running）：
进程正在占用CPU资源
（2）就绪状态（Ready）：
进程等待分配CPU资源
（3）阻塞状态（Blocked）：
进程因等待I/O操作等条件而暂停运行
（4）创建状态（New）：
进程正在创建过程中，还不能运行
（5）结束状态（Exit）：
进程已结束运行，回收除进程控制块之外的其他资源，让其他进程从 进程控制块中收集有关信息
五状态状态转换条件
（1）创建新进程：
进入创建状态
（2）提交（Admit）：
完成一个新进程的创建过程，进入就绪状态
（3）调度运行（Dispatch）：
进入运行状态
（4）释放（Release）：
进程终止运行，进入退出状态
（5）超时（Timeout）：
用完时间片，进程暂停运行，从运行状态进入就绪状态
（6）事件等待（Event Wait）：
进程要求的事件未出现而进入阻塞状态
（7）事件出现（Event Occurs）：
进程等待的事件出现，进程从阻塞状态进入就绪状态
七状态进程模型
七状态模型引入原因：
五状态进程模型没有区分进程地址空间位于内存还是外存，低优先级进程对换至外存，这种做法可得到的好处：
（1）提高处理机效率
（2）可为运行进程提供足够内存
（3）有利于调试
七状态模型状态定义：
与五状态进程模型相比，增加了就绪挂起和阻塞挂起两个状态
（1）阻塞挂起状态（Blocked，suspend）：
进程在外存并等待某事件的出现
（2）就绪挂起状态（Ready，suspend）：
进程在外存，但只要进入内存，即可运行
七状态模型状态转换条件：
1）挂起（Suspend）：
进程从内存转到外存
阻塞到阻塞挂起
就绪到就绪挂起
运行到就绪挂起
（2）激活（Activate）：
进程从外存转到内存
就绪挂起到就绪
阻塞挂起到阻塞
（3）事件出现（Event Occurs）：
等待的事件出现
阻塞到就绪
阻塞挂起到就绪挂起
（4）提交（Admit）：
完成创建过程
进入就绪状态或就绪挂起状态
三、进程控制块
考点3 进程控制块
进程控制块（PCB：Process Control Block）：描述进程的基本情况以及进程的运行变化过程
PCB是进程存在的唯一标志
当系统创建一个进程时，为进程设置一个PCB，再利用PCB对进程进行控制和管理
撤消进程时，系统收回它的PCB，进程也随之消亡
PCB的内容
PCB的内容可以分成调度信息和现场信息两大部分，进程由程序、数据和进程控制块三部分组成 • PCB存有进程的地址信息 • 程序描述了进程要实现的功能 • 数据是程序操作的对象
PCB组织
（1）线性方式：所有PCB不分状态组织在一个线性表（称PCB表）中 （2）索引方式：相同状态的进程，分别设置PCB索引表 （3）链接方式：对于具有相同状态进程的PCB，通过PCB中的链接字构成一个队列链接字指出本 队列下一PCB在PCB表中的编号（或地址）编号为0表示队尾队首由内存固定单元中相应的队列指 针指示
进程的队列
（1）就绪队列 所有就绪状态的进程排在一个就绪队列中 （2）等待队列 对每一种等待事件组织一个队列 （3）运行队列 在单CPU系统中，整个系统有一个运行队列
1.PCB的内容
2.进程的组成
3.PCB组织
4.进程的队列
5.进程队列的组成
四、进程控制
考点4 进程控制基本概念
进程控制：
对进程在整个生命周期中各种状态之间的转换进行有效的控制，通过进程控制原语来实现。
原语：
若干条指令所组成的一个指令序列，用来实现某个特定的操作功能，连续的，具有不可分 割性，在执行时也不可间断，必须在管态下执行，并且常驻内存，用于进程控制的原语：创建 进程、撤消进程、挂起进程、激活进程、阻塞进程、唤醒进程以及改变进程优先级等
1.创建原语 2.撤消原语 3.阻塞原语 4.唤醒原语
1.进程控制原语
2.UNIX操作系统的进程创建操作fork
第三节 线程
一、线程的基本概念
考点5 线程的引入
线程是进程中的一个实体，是CPU调度和分派的基本单位，只拥有少量在运行中必不可少 的资源
同属一个进程的其他线程共享进程所拥有的全部资源线程有就绪、等待和运行三种基本 状态，有的系统中线程还有终止状态等
考点6 线程的组成
thread结构，即线程控制块，由以下四个基本部分组成：
①一个唯一的线程标识符
②描述处理器工作情况的一组寄存器的内容
③两个栈指针
④一个私有存储区
一个进程可以包含一个线程或多个线程
当一个进程包含多个线程时，这些线程除各自私有少量资源以外，共享所属进程的全部资源
1.什么是线程
2.线程的属性
3.引入线程的好处
二、进程和线程
考点7 线程与进程的关系
线程又称为轻量级进程或者进程元
传统的进程称为重量级进程
通常一个进程都有若干个线程
1.调度
传统的操作系统中拥有资源的基本单位和独立调度、分派的基本单位都是进程引入线程的 操作系统中，线程作为调度和分派的基本单位，进程作为资源拥有的基本单位
2.并发性
引入线程的操作系统中不仅进程之间可以并发执行，一个进程中的多个线程之间也可以并 发执行
3.拥有资源
不论是传统的操作系统，还有线程的操作系统
进程都是拥有资源的一个独立单位
4.系统开销
在创建或撤消进程时，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销， 进程切换的开销远大于线程切换的开销，同一进程中的多个线程具有相同的地址空间，同步和 通信的实现比较容易。
1.调度
2.并发性
3.拥有资源
4.系统开销
三、线程实现机制
考点8 线程的实现方式
用户级线程、核心级线程和混合方式
线程已在许多系统中实现，但实现的方式并不完全相同 用户级线程（User-Level Threads），不依赖于内核
例如：数据库系统中的线程
内核级线程（Kernel-Supported Threads），依赖于内核 混合方式实现线程，即同时实现了以上两种类型的线程
1.用户线程
2.内核级线程
3.混合实现方式
4.实例：Pthread线程包
第四节 进程调度
一、概述
1.进程调度的主要功能
2.进程调度的时机
二、调度算法设计原则
1.进程行为
2.系统分类
3.调度算法的设计目标
三、进程调度算法
1.先来先服务算法
2.最短进程优先算法
3.最短剩余时间优先算法
4.最高响应比优先算法
5.轮转算法
6.最高优先级算法
7.多级反馈队列算法
考点9 协程
提出原因：
当线程数量非常多的时候，系统线程会占用非常多的内存空间
过多的线程切换会占用大量的系统时间
解决方法：协程机制
协程是运行在线程之上的轻量级线程，当一个协程执行完成后，让另一个协程运行在当前 线程之上，协程并没有增加线程数量，只是在线程的基础之上通过分时复用的方式运行多个协 程，协程的切换在用户态完成切换的代价比线程从用户态到内核态的代价小很多。
考点1 进程调度的基本概念
进程调度即处理机调度。进程调度的任务是控制、协调进程对CPU的竞争，按照一定的调度算法，使某一就绪进程获得CPU的控制权，转换成运行状态。进程调度也叫低级调度
进程调度程序是操作系统的真正核心，它直接负责CPU的分配。系统中所有进程都是在CPU上运行的，进程调度程序就是它们的切换开关。
考点2 进程调度的主要功能
①保存现场
②挑选进程
③恢复现场
第五节 系统内核
考点3 进程调度的时机
①创建进程
②任务完成
③等待资源
④中断发生
⑤运行到时
考点4 进程调度的主要功能
①设计目标
②公平性
③均衡性
④统筹兼顾
⑤优先级
⑥开销
考点5 性能评价标准
①CPU利用率
②吞吐量
③周转时间
④就绪等待时间
⑤响应时间
考点6 先来先服务法
先来先服务（First-Come，First-Served，FCFS）法是最简单的一种调度算法
对于作业调度来说，每次调度从后备作业队列中选择队头的一个或几个作业，把它们调入内存，分配相应的资源，创建进程，然后把进程放入就绪队列
对于进程调度算法来说，即每次调度从就绪队列中选择一个最先进入该队列的进程，把CPU 分给它，直至完成或者由于某些原因而阻塞，当新一个进程进入就绪队列时，它的PCB就链入就 绪队列的末尾。每次进程调度时就把队头进程从该队列中摘下，分给它CPU，使它运行
考点7 时间片轮转法
时间片轮转法（Round-Robin，RR）主要用于分时系统中的进程调度。
当进程用完分给它的 时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，并把它放入就绪队列 的末尾；然后，把CPU分给就绪队列的队首进程，同样也让它运行一个时间片，如此往复
时间片的长短通常由以下四个因素来确定：
①系统的响应时间
②就绪队列进程的数目
③进程的转换时间
④CPU运行指令速度
考点8 优先级法
利用优先级调度算法进行进程调度时，是从就绪队列中选出优先级最高的进程，把CPU分给它使用如果在就绪队列中出现优先级更高的进程时，怎么办：
①非抢占式优先级法
②抢占式优先级法
内部决定优先级是利用某些可度量的量来定义一个进程的优先级
外部优先级是按操作系统以外的标准设置的
两种确定进程优先级的方式：
①静态优先级是在创建进程时就确定下来的，而且在进程的整个运行期间保持不变
②动态优先级是随着进程的推进而不断改变的
考点9 短作业优先法
从作业的后备队列中挑选那些需要运行时间最短的作业放入内存
短作业优先法能有效地降低作业的平均等待时间和提高系统的吞吐量
算法对长作业很不利，并且不能保证紧迫性作业会被及时处理
考点10 最短剩余时间优先法
最短剩余时间优先（Shortest Remaining Time First， SRTF）法是短作业优先法的变形，它采用抢占式策略
考点11 多级队列法
多级队列（Multi level Queue）调度算法是根据作业的某些特性，如占用内存大小和作业类型等，永久性地把各个作业分别链入不同的队列，每个队列都有自己的调度算法，在各个队 列之间也要进行调度，通常采用固定优先级的抢占式调度
考点12 多级反馈队列法
多级反馈队列（Multi level Feedback Queue）法是在多级队列法的基础上加进“反馈”措 施。
其实现思想是：系统中设置多个就绪队列，每个队列对应一个优先级，第一个队列的优先 级最高，第二个队列次之，以下各个队列的优先级逐个降低；各就绪队列中进程的运行时间片不同，高优先级队列的时间片小，低优先级队列的时间片大，如从高到低依次加倍；新进程进入系统后，先放入第一队列的末尾，各队列按FCFS方式排队；如某个进程在相应时间片内没有 完成工作，则把它转到下一级队列的末尾；系统先运行第一队列中的进程，第一队列为空后，才运行第二队列中的进程，依次类推。最后一个队列（最低级）中的进程采用时间片轮转的方 式进行调度。
考点13 保证调度
保证调度算法的目标是保证每个进程享用CPU的时间完全一样，即如果系统里一共有n 个进 程，则每个进程占用CPU的时间为1/n。
保障调度就是保障每个进程使用1/n的CPU时间。保障就是肯定1/n的时间运转，而不是大概1/n时间运转。那么保障调度和轮转调度是一样吗？时间片 轮转能不能达到1/n的效果？关键就是达到1/n不一定要靠轮转。轮转是能够达到1/n的，但是保 障调度不一定要轮转。每次给的时间片不一定要一样。
考点14 彩票调度
彩票调度算法是一种概率调度算法。
你买过彩票就知道，你买的越多中奖的概率越大。在 该算法里，给每个进程分发一定数量的彩票，而调度器则从所有彩票里随机抽取一张彩票，持有该彩票的进程就获得CPU。这样，如果想让某个进程获得更多的CPU时间，我们可以给该进程 多发几张彩票。彩票算法的优越性是显而易见的，通过给每个进程至少一张彩票就可以防止饥 饿，因为该进程获得CPU的概率将大于0。
考点15 进程与线程调度
在大多数传统的多处理器系统中，进程并不是被指定到一个专门的处理器。不是所有处理器只有一个队列，或者使用某种类型的优先级方案，而是有多条基于优先级的队列，并且都送 进相同的处理器池中。在任何情况下，都可以把系统看作是多服务器排队结构。
在单处理器中，线程可以用作辅助构造程序，并在处理过程中重叠执行I/O。由于在进行线 程切换时的性能损失远远小于进程切换的开销，因此可以用很少的代价实现这些优点
在多处理器系统中，线程的全部能力得到了更好的展现。在这个环境中，线程可以用于开 发应用程序中真正的并行性
考点16 实时调度算法
静态表驱动调度适用于周期性的任务
静态优先级驱动抢占调度与大多数非实时多道程序系统中的优先级驱动的抢占式调度所用 的机制相同
基于动态规划调度，在一个任务已到达但未执行时，试图创建一个包含前面被调度任务和 新到达任务的调度
如果新到达的任务可以按这种方式调度：满足它的最后期限，但是当前被调度的任务也不 会错过它的最后期限，则修订这个调度以适应新任务
为周期性任务解决多任务调度冲突的一个非常好的方法是速率单调调度RMS
优先级最高的任务是周期最短的任务，优先级次高的任务是周期次短的任务，依次类推。 当有多个任务可供执行时，周期最短的任务首先得到服务
优先级逆转（priority inversion）在任何基于优先级的可抢占的调度方案中都能发生的 一种现象，但是它与实时调度的上下文关联特别大
在任何优先级调度方案中，系统应该不停地执行具有最高优先级的任务
一个更加严重的情况被称之为无界限优先级逆转（Unbounded priority inversion），在 这种情况下，优先级逆转的持续时间不仅依赖于处理共享资源的时间，而且也依赖于其他不相 关任务的不可预测的行为
第八章 进程同步机制与死锁
第一节 进程间相互作用
一、相关进程和无关进程
多道程序系统中并发进程通常有多个。在逻辑上具有某种联系的进程称为相关进程。在逻辑上没有任何联系的进程称为无关进程。
如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则说这些并发进程的相互之间是无关的。显然，无关的并发进程一定没有共享的变量，它们分别在各自的数据集合上操作。
如果一个进程的执行依赖其他进程的进展情况，或者说，一个进程的执行可能影响其他进程的执行结果，则说这些并发进程是相关的。
例如，两个并发程序A和B共享一个公共变量n，程序A每执行一次循环都要作n：=n+1操作，程序B 则在每一次循环中打印出n的值并将n重新置0。
程序A. While（true） { n=n+1； …. }； … …
程序B. While（true） { print（n）； n=0； …. }；
二、与时间有关的错误
第二节 进程的同步与互斥
相同的程序在可能的三种情况下，分别产生了三组不同的结果。
根本原因在于：在并发程序中共享了公共变量，使得程序的计算结果与并发程序执行的速度有关。这种错误的结果又往往是与时间有关的（如上例中的三种情形，其结果时对时错，随执行速度的 不同而异），所以，把它称为“与时间有关的错误”
解决进程同步与互斥的做法有两种：一是由竞争各方平等协商；二是引入进程管理者 临界资源是指计算机系统中的需要互斥使用的硬件或软件资源，如外设、共享代码段、共享数据 结构等。多个进程在对临界资源进行写入或修改操作时，必须互斥地进行计算机系统中也有一些可以同时访问的共享资源不是临界资源，如只读数据
进程间的相互制约关系按相互感知程度分为如表8-1所列的三种类型。资源共享的程度分成三个 层次：互斥（mutual exclusion）、死锁（deadlock）和饥饿（starvation）
保证资源的互斥使用是指多个进程不同时使用同一个资源。避免死锁是指避免多个进程互不相让 而得不到足够的资源的情况出现。避免饥饿是指避免某些进程一直得不到资源
一、进程的同步
同步机制应遵循以下4条准则
1）空闲则入：任何时刻最多只有一个进程位于临界区。当有进程位于临界区时，其他进程不能进入 临界区
2）忙则等待：当已有进程处于临界区时，后到达的进程只能在进入区等待
3）有限等待：等待进入临界区的进程不能无限期地“死等”
4）让权等待：因在进入区等待而不能进入临界区的进程，应释放处理机，转换到阻塞状态
考点2 死锁 死锁现象并不是计算机操作系统环境下所独有，在日常生活乃至各个领域是屡见不鲜的。例如， 没有交通灯的十字路口出现了死锁。 死锁是指在多道程序系统中的一种现象：一组进程中的每一个进程均无限期地等待被该组进程中 的另一个进程所占有且永远不会释放的资源。系统发生这种现象称为系统处于死锁状态，简称死锁。 处于死锁状态的进程称为死锁进程。 当死锁发生后，死锁进程将一直等待下去，除非有来自死锁进程之外的某种干预。系统发生死锁 时，死锁进程的个数至少为两个。 系统发生死锁不仅浪费了大量的系统资源，甚至会导致整个系统崩溃，带来灾难性的后果。
产生死锁的原因主要有两个：一是竞争资源，系统资源在分配时出现失误，进程间对资源的相互 争夺而造成僵局；二是多道程序运行时，进程推进顺序不合理 1.资源的概念 系统中的资源有两类：永久性资源（可重用资源），如内存、外部设备、CPU等硬件资源，以及 各种数据文件、表格、共享程序代码等软件资源 临时性资源（消耗性资源），是指由某个进程所产生、只为另一个进程使用一次、或经过短暂时 间后便不再使用的资源，如I/O和时钟中断信号、同步信号、消息等 永久性资源和临时性资源都可能导致死锁发生。
2.死锁的例子 进程P1和P2在运行中都使用输入、输出设备，假定系统中只有一台输入设备，一台输出设备，则
进程P1和P2可有如下形式 P1 ①申请一台输入设备； ②申请一台输出设备； 使用各设备； 释放输入设备； 释放输出设备；
P2 Ⅰ 申请一台输出设备； Ⅱ 申请一台输入设备； 使用各设备； 释放输出设备； 释放输入设备；
当进程P1申请并获得了该输入设备后（运行完成①) , 由于进程切换或某种原因，停止前进。此时P2到达，P2进程 完成了对输出设备的申请（运行完成②) , 接下来再申请输 入设备（运行④)，由于输入设备被P1占用必将导致P2被阻 塞且进入等待队列等待 若进程P1重新获得运行机会，接下来便要申请输出设备 （运行③)，同样，也被阻塞进入等待输出设备的等待队列。 进程P1和P2彼此无限地等待对方释放资源从而唤醒自己，于是形成了僵局，如图所示
子主题
假设有一类可重用资源R，如主存（或磁盘），它包含有m个页面（或扇区），由n个进程 P1，P2，… ，Pn（2≤m≤n）共享。假定每个进程按下述顺序依次申请和释放页面（或扇区）： ①申请一个页面 … ②申请一个页面 … 释放一个页面 … 释放一个页面
对于第四章描述的生产者和消费者问题，若把生产者和消费者程序中前面两个P操作顺序颠倒， 则形成如下所示的两个序列
生产者进程： P（mutex）； P（empty）； … …
消费者进程： P（mutex）； P（full）；
当进行了n次生产后（或n个生产者，每人都送了缓冲区一个产品后），缓冲区被全部占满， 此时empty=0。若生产者执行P（mutex）后（此时mutex=0），又继续执行P（empty），此刻 empty=-1，使生产者因无可用缓冲区而在empty上等待。若又有一个消费者进程到达，并执行P ( mutex），结果使mutex=-1 因此，消费者也阻塞，并且在mutex上等待。此时，生产者、消费者都彼此等待对方来唤醒自 己，处于循环等待状态，这样便形成了死锁局面
对临时性资源的使用不加限制而引起的死锁 信件可以看作是一种临时性资源，也可能引起死锁。比如，进程P1等待进程P3的信件s3到来后再 向进程P2发送信件s1，P2又要等待P1的信件s1到来后再向P3发送信件s2，而P3也要等待P2的信件s2来 到后才能发出信件s3。在这种情况就形成了循环等待，产生死锁。
进程P1 receive（s3）； ...... send（s1）； ......
进程P2 receive（s1）； ...... send（s2）； ......
进程P3 receive（s2）； ...... send（s3）； ......
产生死锁有四个必要条件（Coffman等，1971） 1.互斥条件 资源是独占的且排他使用 2.不可剥夺条件 又称不可抢占或不可强占。进程所获得的资源在未释放前，不能被其他进程强行剥夺
3.请求和保持条件 又称部分分配或占有申请。进程在申请新的资源的同时，继续占用已分配到的资源 4.循环等待条件 又称环路等待。在发生死锁时，必然存在一个进程等待队列{P1，P2，… ，Pn}，其中P1等待P2占 有的资源，P2等待P3占有的资源，… ，Pn等待P1占有的资源，形成一个进程等待环路
1.死锁预防 死锁预防通过设置某些严格限制，破坏产生死锁的必要条件以防止死锁发生 若死锁是由于资源数量不足而造成的，可以通过增加资源数量的方法来进行预防，例如内存 临时性的资源如系统中的共享写数据，各种信号量等，不能通过增加资源数量来解决，所以这种 情况下通过破坏互斥条件来预防死锁不现实
在预防死锁的静态分配策略中，资源分配的原则是 一个进程在申请新资源的要求不能立即得到满足时，便处于等待状态。而一个处于等待状态的进 程的全部资源可以被剥夺。被剥夺的资源重新加入到资源表中。仅当该进程重新获得它原有的资源以 及得到新申请的资源时，才能重新启动执行 这种方法破坏了不可剥夺条件 具体实施方法 （1）若一个进程已占用了某些资源，又要申请一个新的资源，在申请新的资源时，不能立即得到满 足，在变为等待状态之前，该进程必须释放已占有的所有资源，即阻塞前释放资源
（2）若一个进程申请某些资源，首先系统应检查这些资源是否可用，如果可用，就分配给该进程。 否则，系统检查这些资源是否分配给另外某个等待进程。若是，则系统将剥夺所需资源，分配给这 个进程。如果资源没有被等待进程占有，那么，该进程必须等待。在其等待过程中，其资源也有可 能被剥夺 破坏不可剥夺条件以预防死锁的方法适用于这样一些资源，它们的状态是容易保存和恢复的， 例如CPU、内存等 在预防死锁的静态分配策略中，还可以采用以下方法，该方法破坏了请求和保持条件
（3）每个进程必须在开始执行前就申请它所需要的全部资源，仅当系统能满足进程的资源申请要求 且把资源一次性分配给进程后，该进程才能开始执行 采用该方法后，进程在执行过程中不再申请资源，故不可能出现占有了某些资源再等待其他资源 的情况，即“请求和保持”的条件不成立，从而预防死锁的发生 这种方法其缺点是严重浪费系统资源 静态分配资源策略还有一个问题是大部分进程在运行开始时不能确定所需要的全部资源，例如堆 栈所需的内存
（4）当进程没有占用资源时才允许它去申请资源，如果进程已经占用了某些资源而又要再申请资 源，则它应先归还所占的资源后再申请新资源 这种资源分配策略仍会使进程处于等待状态，同时也存在着资源利用率低的缺点
采用资源有序分配策略打破了循环等待的条件 其基本思想是将系统中所有资源顺序编号。进程申请资源时，必须严格按照资源编号的顺序进 行，否则系统不予分配。释放资源时，应按编号逆序进行
2.死锁避免 在资源的动态分配过程中，采取某种方法防止系统进入不安全状态，从而避免死锁的发生。可获 得较高的资源利用 死锁避免的基本思想是：系统对进程发出的每一个申请进行动态检查，并根据检查结果决定是否 分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配 死锁避免和死锁预防的区别在于，死锁预防是设法破坏产生死锁的四个必要条件之一，严格地防 止死锁的出现。而死锁避免则是在系统运行过程中注意避免死锁的最终发生
如果不存在任何一个安全序列，则系统处于不安全状态 不安全状态不一定导致死锁，但死锁状态一定是不安全状态
二、进程的互斥
1.进程互斥的软件方法
通过平等协商方式实现进程互斥的最初方法是软件方法。其基本思路是在进入区检查和设置一些 标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志
彼得松算法（Peterson’s Algorithm）是一种软件实现的临界区访问算法，其做法是：先修改 临界区标识、后检查、后修改者等待
彼得松算法的基本思想是：每个进程都在进入区先将flag修改为本进程为TRUE，而将turn设为另 一个进程，所以当另一个进程想进临界区时就可以进入。如果两个进程同时希望进入临界区，那么turn会在几乎同时被设成i和j，但是只有后一个赋值语句的结果会被保持，因此turn的最终值决定了 先到的（先赋值的）进程能进入临界区。
2.进程互斥的硬件方法
软件方法实现进程互斥不适用于数目很多的进程间的互斥
利用硬件方法的主要思路是用一条指令完成读和写两个操作，因而保证读操作与写操作不被打 断。依据所采用的指令的不同硬件方法分成TS指令和Swap指令两种
平等进程间的协商机制存在有些问题是平等协商无法解决的，需要引入一个地位高于进程的管理 者来解决公有资源的使用问题
操作系统可以从进程管理者的角度来处理互斥的问题，信号量就是由操作系统提供的管理公有资 源的有效手段
三、临界区
临界资源的正确访问过程分成如图8-2所示的四个部分：
1）进入区（entry section）：在进入区设置相应的“正在访问临界区”标志，检查可否进入临界 区；以防止其他进程同时进入临界区
2）临界区（critical section）：进程中访问临界资源的一段代码
3）退出区（exit section）：将“正在访问临界区”的标志清除
4）剩余区（remainder section）：代码中的其余部分
第三节 信号量及P、V操作
一、信号量
二、P、V操作
信号量机制中P原语相当于进入区操作，V原语相当于退出区操作。
信号量机制可实现临界资源的互斥访问。如图所示，mutex（MUTual Exclusion）为互斥信号 量，其初值为1；临界区代码置于P（mutex）和V（mutex）原语之间。在使用信号量时，必须成对 使用P和V原语。遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放 给其他等待的进程。P、V原语的使用不能次序错误、重复或遗漏
三、信号量与P、V操作的物理含义
四、用P、V操作实现进程之间的互斥
五、用P、V操作实现进程间的同步
六、信号量及P、V操作小结
第四节 经典的进程同步题
一、简单生产者——消费者问题
简单生产者-消费者问题：设有一个生产者进程P，一个消费者进程Q，它们通过一个缓冲区联系起来，如图所示。缓冲区只能容纳一个产品，生产者不断地生产产品，然后往空缓冲区送产品；而消费者则不断地从缓冲区中取出产品，并消费掉。
P进程不能往已经“满”的缓冲区中放入产品，设置信号量empty，其初值为1，用于指示空缓冲 区数量；同样，Q进程也不能从已经“空”的缓冲区中取出产品，设置信号量full，初值为0，用于指 示满缓冲区数量。
P： while（true） { P（empty）； 生产一个产品； 送产品到缓冲区； V（full）； }；
Q： while（true） { P（full）； 从缓冲区取产品； V（empty）； 消费产品； }；
二、多个生产者——消费者问题
三、读者——写者问题
四、同步与互斥机制的综合应用
信号量机制可实现临界资源的互斥访问。如图所示，mutex（MUTual Exclusion）为互斥信号 量，其初值为1；临界区代码置于P（mutex）和V（mutex）原语之间。在使用信号量时，必须成对 使用P和V原语。遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放 给其他等待的进程。P、V原语的使用不能次序错误、重复或遗漏
第五节 管程
一、管程的提出
二、管程的概念及组成
三、管程中的条件变量
四、用管程解决生产者——消费者问题
第六节 进程通信
一、共享内存
二、消息机制
1.消息缓冲通信
2.信箱通信
3.管道通信
考点3 银行家算法规定 （1）当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客 （2）顾客可以分期贷款，但贷款的总数不能超过最大需求量 （3）当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾 客在有限的时间里得到贷款 （4）当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金
假定某系统有三类资源A、B、C，A类资源共有10个资源实例，B类资源共有5个资源实例，C类资 源共有7个资源实例，现有5个进程P1、P2、P3、P4、P5，它们对各类资源的最大需求量和第一次分配 后已占有的资源量如图所示。
子主题
应用银行家算法，找到一个进程安全序列P2，P4，P5，P3，P1，可以得出结论：图8-13中的系统 状态是安全状态 在此状态下，进程P2提出新的资源申请：A类1个，B类0个，C类2个，进行试探性分 配后，系统状态如图所示
应用银行家算法，仍然可以找到一个进程安全序列P2，P4，P5，P1，P3，表明该系统状态是安全 状态，可以实施资源分配 在图所示状态下，进程P5又申请资源：A类3个，B类3个，C类0个，此时系统不能实施分配，因为 该申请超过了系统当前剩余的资源量 若进程P1提出新的资源申请：A类0个，B类2个，C类0个，也不能实施资源分配，因为根据银行家 算法，若进行了分配，则在新的系统状态下找不到进程安全序列，这将导致系统进入不安全状态
考点4 死锁的检测与解除 死锁的检测与解除是在系统运行过程中，通过在系统中设置检测机构，定时检测死锁是否真的发 生，并精确地确定与死锁有关的进程与资源，然后采取措施解除死锁。 操作系统可定时运行一个“死锁检测”程序，该程序按一定的算法去检测系统中是否存在死锁， 即是否存在“循环等待”条件。 通常，死锁检测可以在任何一次资源分配后，也可以在每次调度后，或者利用定时器定时运行检 测，或某个进程长期位于阻塞态或阻塞进程过多时，启动死锁检测程序。
考点5 死锁发生后的处理方法 解除死锁的方法 剥夺资源法解除死锁 （1）选择一个牺牲进程，即要剥夺哪个进程的哪些资源 （2）被选中的进程重新运行或回退到某一点开始继续运行 （3）保证不发生“饿死”现象 （4）“最小代价”
（2）撤销进程 撤销死锁进程，将它们占有的资源分配给另一些死锁进程，直到死锁解除为止 撤销进程的代价 ①进程优先数，即被撤销进程的优先数 ②进程类的外部代价 ③运行代价
4.忽略死锁 对于那些死锁发生的几率极低，而解决死锁的方法代价极大或暂时没有办法解决的死锁问题暂时 不予理睬
考点6 哲学家就餐问题 为了提高资源的利用率，通常应当按照大多数进程使用资源的次序对资源进行编号。先使用者编 号小，后使用者编号大。 1）这种硬性规定申请资源的方法，会给用户编程带来限制，按照编号顺序申请资源增加了资源使用 者的不便； 2）如何合理编号是一件困难的事情，特别当系统添加新设备类型时，会造成不灵活、不方便；如果 有进程违反规定，则仍可能发生死锁。资源有序分配法与资源静态分配策略相比，显然提高了资源利 用率，进程实际需要申请的资源不可能完全与系统所规定的统一资源编号一致，为遵守规定，暂不需 要的资源也要提前申请，仍然会造成资源的浪费。
第五章 存储管理
第一节 存储管理概述
一、存储体系
二、存储管理的任务
三、地址转换
第二节 分区管理方案
第三节 覆盖与交换技术
第四节 虚拟页式存储管理方案
考点1 存储体系
存储器分成两类：
内存储器（简称内存）
外存储器（简称外存）
处理器可以直接访问内存，但不能直接访问外存。
处理器要通过启动相应的输入/输出设备 后才能使外存与内存交换信息。
在操作系统中，管理内存的部分称为存储管理，是操作系统的重要部分之一。对内存管理 的好坏直接影响到计算机系统工作性能的高低。
1.若干兆字节、中等速度、中等价格、内容易变的内存RAM，通常是GB的数量级；
2.低速、价廉、内容不易变的磁盘，通常是TB的数量级；
3.少量的、非常快速、昂贵、内容易变的高速缓存Cache，通常是MB的数量级。
考点2 存储管理的任务
存储管理直接影响系统性能。
所谓内存空间，是由存储单元（字节或字）组成的一维连续的地址空间。
内存空间的任务：
用来存储当前正在运行程序的代码及数据，
是程序中指令本身地址所指的也就是程序计数器所指的存储器。
内存空间分为两部分：
1）系统区，用以存储操作系统常驻内存部分，用户不能占用这部分空间；
2）用户区，分配给用户使用，用于装入并存储用户程序和数据，这部分的信息随时都在发生变化。
内存分配和回收
1）记住每个存储区域的状态。
2）实施分配（静态和动态）。
内存分配有两种方式：
1）静态分配
2）动态分配
3）回收。
内存分配和回收采用的方法——内存分配表
①位示图表示法
②链表法
内存共享
所谓内存共享是指两个或多个进程共用内存中相同区域。
1）能使多道程序动态地共享内存，提高内存利用率；
2）能共享内存中某个区域的信息。
共享的内容包括代码共享和数据共享，特别是代码共享要求代码必须是纯代码。
考点3 地址转换
存储器以字节（每个字节为8个二进制位）为编址单位，每个字节都有一个地址与其对应。
假定存储器的容量为n个字节，其地址编号顺序为0，1，2，… ，n-1。这些地址称为内存的 “绝对地址” ，由绝对地址对应的内存空间称为“物理地址空间”。
用户程序中使用的地址称为“逻辑地址” ，由逻辑地址对应的存储空间称为“逻辑地址空间”。
地址重定位
把逻辑地址转换成绝对地址的工作称“地址重定位”或“地址转换” ，又称 “地址映射"
每个逻辑地址在内存中也没有一个固定的绝对地址与之对应。为了保证程序的正确执行， 必须根据分配给程序的内存区域对程序中指令和数据的存储地址进行重定位，即要把逻辑地址 转换成绝对地址
重定位的方式可以有
静态重定位
动态重定位
考点4 分区管理方案
分区管理是能满足多道程序运行的最简单的存储管理方案。其基本思想是把内存划分成若 干个连续区域，称为分区，每个分区装入一个运行程序。
分区的方式可以归纳为两类
固定分区
固定分区是指系统先把内存划分成若干个大小固定的分区，一旦划分好，在系统运行期间 便不再重新划分。
为了满足不同程序的存储要求，各分区的大小可以不同。程序运行时必须提供对内存资源 的最大申请量
可变分区
可变分区是指系统不预先划分固定分区，而是在装入程序时划分。
内存分区
使为程序分配的分区的大小正好等于该程序的需求量，且分区的个数是可变的
已分配区表
记录已装入的程序在内存中占用分区的起始地址和长度，用标志位指出占用 分区的程序名
空闲区表
记录内存中可供分配的空闲区的起始地址和长度，用标志位指出该分区是未分 配的空闲区。
考点7 紧缩技术
内存经过一段时间的分配回收后，会存在很多很小的空闲块，这些空闲块被称为碎片。
解决碎片问题的办法是在适当时刻进行碎片整理，通过移动内存中的程序，把所有空闲碎 片合并成一个连续的大空闲区且放在内存的一端，而把所有程序占用区放在内存的另一端，这 一技术称为“紧缩技术” ，或“压缩技术”。
考点8 空闲分区的分配策略
（1）最先适应算法
最先适应算法，又称顺序分配算法，当接到内存申请时，顺序查找分区说明表，找到第一个满 足申请长度的空闲区，将其分割并分配。
此算法简单，可以快速做出分配决定
（2）最优适应算法
最优适应算法，当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲 区，将其分割并分配。
（3）最坏适应算法
当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。
基本思想：
在大空闲区中装入信息后，分割剩下的空闲区相对也很大，还能用于装入其他程序
考点10 覆盖技术
覆盖技术是指一个程序的若干程序段，或几个程序的某些部分共享某一个存储空间。
覆盖技术不需要操作系统的特殊支持，可以完全由用户实现，即覆盖技术是用户程序自己 附加的控制。
覆盖技术可以由编译程序提供支持。覆盖可以从用户级彻底解决内存小装不下程序的问题
覆盖技术是早期采用的简单的扩充内存的技术，对用户不透明，增加了用户的负担，要求 用户清楚地了解程序的结构，并指定各程序段调入内存的先后次序，以及内存中可以覆盖掉的 程序段的位置等。而且程序段的最大长度仍受内存容量的限制。通常，覆盖技术主要用于系统 程序的内存管理上，因为系统软件设计者容易了解系统程序的覆盖结构。
考点11 交换技术
交换技术又称对换技术。
进程从内存移到磁盘，并再移回内存称为交换。
交换技术是进程在内存与外存之间的动态调度，是由操作系统控制的。 交换技术多用于分时系统，大多数现代操作系统使用交换技术。
交换技术支持多道程序设计、也是虚拟存储技术（下一节）基础。
使用交换技术需要考虑 的相关问题：
（1）换出进程的选择：时间片轮转法、基于优先数的调度算法。
（2）交换时机的确定：内存空间不够或者内存空间有不够的危险时。
（3）交换空间的分配：当进程在内存中时，不再为它分配磁盘空间。 当它被换出时，必须为它分配磁盘交换空间。
（4）换入进程换回内存时位置的确定：
绝对地址：一定要在原来的位置上。
相对地址：可再进行地址重定位，可以不在原来的位置上。
与覆盖技术相比：
1）交换技术对用户而言是透明的。
2）交换可以发生在不同的进程或程序之间，而覆盖发生在同一进程或程序内部，而且只能覆盖 那些与覆盖段无关的程序段。
因此，交换技术比覆盖技术更加广泛地用于现代操作系统。覆盖技术与交换技术的发展导 致了虚拟存储技术的出现。
考点12 虚拟页式存储管理方案
虚拟存储技术：
可以把一个逻辑地址连续的程序分散存储到几个不连续的内存区域中，并 且保证程序的正确执行，则既可充分利用内存空间，又可减少移动所花费的开销。
页式存储管理就是这样一种有效的管理方式。
虚拟存储技术的基本思想：
利用大容量的外存来扩充内存，产生一个比有限的实际内存空 间大得多的、逻辑的虚拟内存空间，简称虚存，以便能够有效地支持多道程序系统的实现和大 型程序运行的需要，从而增强系统的处理能力。
实现虚拟存储器需要以下的硬件支持：
1）系统有容量足够大的外存。
2）系统有一定容量的内存。
3）最主要的是，硬件提供实现虚-实地址映射的机制
虚拟存储器的工作原理：
当进程开始运行时，先将一部分程序装入内存，另一部分暂时留在外存；当要执行的指令不 在内存时，由系统自动完成将它们从外存调入内存的工作；当没有足够的内存空间时，系统自动 选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其他进程使用。这 样做的结果使程序的运行丝毫不受影响，使程序在运行中感觉到拥有一个不受内存容量约束的、 虚拟的、能够满足自己需求的存储器。
交换技术：
交换到外存上的对象一般都是进程，也就是说交换技术是以进程为单位进行的。
虚拟存储技术：
一般是以页为单位。
支持页式存储管理的硬件部件通常称为“存储管理部件”（MemoryManagement Unit，MMU）。
存储管理部件首先把内存分成大小相等的许多区，把每个区称为“物理页面” ，物理页面是进 行内存空间分配的物理单位。
同时，要求程序中的逻辑地址也进行分页，页的大小与物理页面的大小一致。“逻辑地址”可被称为虚拟地址。
内存分配表中具有三种标识：已分配、未分配、剩余空闲物理页面数。
简单的内存分配表可以用一张“位示图”构成。
假设内存的可分配区域被分成256个物理页面，则可用字长为32位的8个字作为“位示图” 。 位示图中的每一位与一个物理页面对应，每一位的值可以是0或1，0表示对应的物理页面为空闲， 1表示已占用。
页式存储管理的地址转换
页表控制寄存器（页表始址寄存器、页表长度寄存器）+高速缓冲 存储器的支持。
1）页表始址寄存器，用于保存正在运行进程的页表在内存的首地址；
2）页表长度寄存器，用于保存正在运行进程的页表的长度。
页表：
1）指出该程序虚拟地址中的页号与所占用的物理页面号之间的对应关系。
2）页表又是硬件进行地址转换的依据，每执行一条指令时按虚拟地址中的页号查页表。 物理地址的计算公式为：
物理地址=物理页面号×块长+页内地址
需要强调的是，物理页面号又称为页帧和页框号
页表项
在虚拟页式存储管理中，页表项的设计如下。
物理页面号：页面在内存中时所对应的物理页面号。
有效位：又称驻留位、存在位，表示该页是在内存还是在磁盘。
访问位：访问位表示该页在内存期间是否被访问过。
修改位：修改位表示该页在内存中是否被修改过。
保护位：是否能读/写。
其中访问位和修改位可以用来决定置换哪个页面，具体由页面置换算法决定。
（1）多级页表
大多数操作系统中采用二级页表，即由表页和页目录一起构成进程页表。
第一级表示页目录，保存页表页的地址；
第二级表示页表页，保存物理页面号。
（2）散列页表
当地址空间大于32位时，一种常见的方法是使用以页号为散列值的散列页表。
其中每个表项都包含一个链表，该链表中元素的散列值都指向同一个位置。 散列页表中的每个表项都包含三个字段：
（a）虚拟页号；
（b）所映射的页框号；
（c）指向链表中下一个元素的指针。
（3）反置页表
每个物理页框对应一个表项。每个表项包含与该页框相对应的虚拟页面地址，以及拥有该页 面进程的信息。
转换检测缓冲区（TLB）
按给定的虚拟地址进行读写时，必须访问两次内存。
第一次按页号读出页表中对应的块号。
第二次按计算出来的绝对地址进行读写。
两次访问内存显然延长了指令的执行周期，降低了执行速度。
缺页异常处理
若在页表中发现所要访问的页面不在内存，则产生缺页异常：
1）操作系统必须在内存中选择一个页面将其移出内存。
2）页面在内存期间已经被修改过，就必须把它写回磁盘。
3）该页没有被修改过，不需要写回，调入的页直接覆盖被淘汰的页。
页面调度策略
虚拟存储器系统通常定义三种策略来规定如何（或何时）进行页面调度：调入策略、置页策 略和置换策略。
（1）调入策略
虚拟存储器的调入策略决定了什么时候将一个页由外存调入内存之中。
①请求调页（Demand Paging）：只调入发生缺页时所需的页面。
②预调页（Prepaging）：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。
（2）置页策略
当线程产生缺页时，内存管理器还必须确定将调入的虚拟页放在物理内存的何处。用于确定 最佳位置的一组规则称为“置页策略”。
（3）置换策略
如果缺页发生时物理内存已满，“置换策略”被用于确定哪个虚页面必须从内存中移出为新 的页面腾出空位。在虚拟页式存储管理方案中，可采用两种分配策略，即固定和可变分配策略。
在进行置换时，也可以采用两种策略，即全局置换和局部置换。将它们组合起来，有如下三 种策略
①固定分配局部置换（Fixed Allocation，Local Replacement）。
②可变分配全局置换（Variable Allocation，Global Replacement）。
③可变分配局部置换（Variable Allocation，Local Replacement）。
页面置换算法
如果刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久 又被装入，如此反复，使调度非常频繁。这种现象称为“抖动”或称“颠簸”。
常用的页面置换算法：
（1）理想页面置换算法（Optimal replacement，OPT）——最佳OPT算法淘汰以后不再需要的或 者在最长时间以后才会用到的页面。这一算法一般不可能实现，但它可以作为衡量其他页面淘汰 算法优劣的一个标准。
（2）先进先出页面置换算法（First-In First-Out，FIFO）先进先出页面置换算法总是选择最先 装入内存的一页调出，或者说是把驻留在内存中时间最长的一页调出。
（3）第二次机会页面置换算法
检查进入内存时间最久页面的R位，如果是0，那么这个页面既老又没有被使用，可以立刻置 换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，修改其进入时间，然后继续搜索。
这一算法称为第二次机会（Second Chance）算法，其基本思想是寻找一个最近的时钟间隔以 来没有被访问过的页面。
（4）时钟页面置换算法（Clock）
一个更好的办法是把所有的页面都保存在一个类似时钟面的环形链表中，一个表针指向最老 的页面。当发生缺页时，算法首先检查表针指向的页面，如果它的R位是0就置换该页面，并把新 的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置， 重复这个过程直到找到了一个R位为0的页面为止。由于这个算法的工作方式，就将它称为时钟 ( clock）算法。
（5）最近最少使用页面置换算法（Least Recently Used，LRU）
在缺页发生时，首先淘汰掉最长时间未被使用过的页面。这个策略称为LRU页面置换算法。最 近最少使用页面置换算法总是选择距离现在最长时间内没有被访问过的页面先调出。这种实现方 法必须对每一页的访问情况时时刻刻地加以记录和更新，实现起来开销比较大，但LRU算法是在效 果上最接近OPT算法的算法。
缺页率
假定一个程序共有n页，系统分配给它的物理页面是m个（m、n均为正整数，且1≤m≤n）。
因此，该程序最多有m页可同时被装入内存。如果程序执行中访问页面的总次数为A，其中有F 次访问的页面尚未装入内存，故产生了F次缺页异常。
现定义：f=F/A 把f称为“缺页率”
显然，缺页率与缺页异常的次数有关。
影响缺页率的因素如下（4点）：
（1）分配给程序的物理页面多，则同时装入内存的页面数就多，故减少了缺页异常的次数，也就 降低了缺页率。反之，缺页率就高。
（2）页面的大小
虚拟页面的大小取决于物理页面的大小，物理页面大则虚拟页面也大，每个页面大了则程序 的页面数就少。装人程序时是按页存储在内存中的，因此，装入一页的信息量就大，就减少了缺 页异常的次数，降低了缺页率。反之，若页面小则缺页率就高。
（3）程序编制方法
怎样编制程序也是值得探讨的，程序编制的方法不同，对缺页异常的次数有很大影响。
（4）页面调度算法
页面调度算法对缺页率的影响也很大，调度不好就会出现“颠簸”
理想的调度算法（OPT）能使缺页率最低，采用FIFO调度算法产生的缺页率约为最佳算法的3倍。
第六章 文件系统
第一节 文件系统的基本概念
一、文件系统的任务
1.文件的定义
文件：文件可以被解释为一组带标识的、在逻辑上有完整意义的信息项的序列
2.文件系统的定义
文件系统：文件系统是操作系统中统一管理信息资源的一种软件。
文件系统的功能：
（1）统一管理文件的存储空间，实施存储空间的分配与回收
（2）实现文件从名字到外存地址空间的映射即实现文件的按名存取
（3）实现文件信息的共享，并提供文件的保护措施
（4）向用户提供一个方便使用的接口
（5）系统维护及向用户提供有关信息
（6）保持文件系统的执行效率文件系统在操作系统接口中占的比例最大
（7）提供I/O的统一接口
二、文件的存储人质及存取方式
1.外存储设备的特点
外存储设备的特点
外存储设备通常由驱动部分和存储介质两部分组成。
存储介质又常被称为卷，“卷”字来自把存储介质看作“信息容器”的比喻。
驱动器的作 用是使计算机能够实现读写（及保存、控制、测试）存储介质上的内容。
2.外存储设备的存储介质
外存储设备的存储介质
（1）磁带
磁带是最早使用的磁记录存储介质。显然，磁带是一种顺序存取设备，因为在磁带上，只 有在前面的物理块被访问之后，才能存取后续的物理块。
（2）磁盘
• 磁盘分为软盘（已淘汰）和磁盘（又称“盘片”）。
• 磁盘由于其存储容量大以及成本低而得到广泛应用。
• 磁盘是一种典型的随机存取设备。磁盘设备允许文件系统直接存取磁盘上的任意物理块。
（3）光盘
光盘是利用在激光的作用下特性发生变化的一些材料所制成的非磁记录介质。
只读式光盘具有容量大（600MB以上）、速度快（接近磁盘）、价格便宜等特点，但一般 不可写。
（4）闪存
闪存是不易丢失存储器中的一种。
3.文件在存储设备中的存取方式
三、文件的分类
为了有效、方便地管理文件，在文件系统中，常常把文件按其性质和用途的不同进行分类
1.按文件的用途分类
（1）系统文件：操作系统和各种系统应用程序和数据所组成的文件。
（2）库函数文件：标准子程序及常用应用程序组成的文件允许用户对其进行读取、执行，但 不允许对其进行修改。如C语言子程序库、FORTRAN子程序库等。
（3）用户文件：用户文件是用户委托文件系统保存的文件。
2.按文件的组织形式分类
（1）普通文件：最一般格式的文件，文件的内容是一般的数据或程序，例如由字符流组成的 文件。普通文件既包括系统文件，也包括用户文件、库函数文件和用户实用程序文件等。
（2）目录文件：目录文件是由文件的目录构成的特殊文件。
（3）特殊文件：特殊文件是以文件形式存在和访问的设备，可进行查找目录等操作，但对文 件的读写会对应于对设备的读写，并由设备驱动程序来完成具体的读写操作。
3.一些常见的文件分类方式
按文件的保护方式可划分为：只读文件、读写文件、可执行文件、无保护文件等
按信息的流向分类可划分为：输入文件、输出文件和输入输出文件等
按文件的存放时限可划分为：临时文件、永久文件和档案文件等
按文件所使用的介质类型分类可划分为：磁盘文件、磁带文件、卡片文件和打印文件等
上述种种文件系统的分类，其目的是：对不同文件进行管理，提高系统效率；同时，提高 文件系统的用户界面友好性
4.UNIX类操作系统中文件的分类
1）普通文件。这是内部无结构的一串平滑的字符所组成的文件。
2）目录文件。这是由文件目录项所构成的文件。
3）特殊文件。在UNIX类操作系统中，把I/O设备也看成是一种文件——特殊文件。
第二节 文件的逻辑结构和物理结构
一、文件的逻辑结构
文件的逻辑结构就是从用户角度看文件，研究文件的组织形式。
文件的逻辑结构就是用户所看到的文件的组织形式文件逻辑结构是一种经过抽象的结构，所 描述的是文件中信息的组织形式，与文件在物理介质上的具体存储结构不同。
文件划分成三类逻辑结构：无结构的字符流式文件、定长记录文件和不定长记录文件构成的 记录树
1.设计文件逻辑结构的原则
2.文件的逻辑结构
二、文件的物理结构
文件的物理结构，也就是文件在实际的存储空间存储时的结构。
从研究文件管理、设计文件管理系统的角度来看，必须研究如何在物理存储器上存储文件， 这是文件系统实现的物理基础
常用的文件物理结构有顺序结构、链接结构、索引结构
文件的物理结构：
1.顺序结构
（1）顺序结构原理
顺序结构又称连续结构，这是一种最简单的文件物理结构，它把逻辑上连续的文件信息依 次存放在连续编号的物理块中。在顺序结构中，一个文件的目录项中只要指出该文件占据的总 块数和起始块号即可。
2.链接结构原理
（1）链接结构原理
文件的链接结构的实质就是为每个文件构造所使用磁盘块的链表。
3.索引结构
（1）索引结构原理
索引结构的文件把每个物理盘块的指针字，集中存放在称为索引表的数据结构中的内存索 引表中。
1.顺序结构
2.链接结构
3.索引结构
三、UNIX的三级索引结构
第三节 文件目录
一、文件控制块
文件系统的一个特点是“按名存取” ，文件控制块（FCB，FileControl Block），把所有 文件的文件控制块有机地组织起来，就构成了文件控制块的一个有序集合，称为文件目录。
文件目录实际就是文件符号名到文件物理地址之间的一种映射机制。
文件控制块FCB是系统为管理文件而设置的一个数据结构。
FCB是文件存在的标志，它记录了系统管理文件所需要的全部信息
二、文件目录和当前目录
1.目录结构
文件目录是实现用户按名存取文件的一种手段。
为了能够方便用户的检索和文件的管理，根据实际的需要，一般把文件目录设计成一级（单 级）目录结构、二级目录结构和多级目录结构。
（2）二级目录结构
第一级称为主文件目录（MFD，Main File Directory），给出了用户名和用户子目录所在的 物理位置。
第二级称为用户文件目录（UFD，User File Directory，又称用户子目录），给出了该用户 所有文件的FCB。
（3）多级目录
把二级目录的层次关系加以推广，就形成了多级目录，又称树型目录结构
2.当前目录与目录检索
文件系统向用户提供了一个当前正在使用的目录，称为“当前目录” ，又称“工作目录” 如果需要，用户可随意更改当前目录
用户在访问文件时，需要进行目录检索，这时用户给出文件名，系统按名寻找目录项。有 两种根据路径名检索的方法：一种是全路径名，另一种是相对路径
1.一级目录结构
2.二级目录结构
3.多级目录
4.当前目录与目录检索
三、目录项和目录文件
1.目录项
当用户建立一个新文件时，与该文件有关的一些信息与属性记录在该文件的文件控制块内。 为了便于管理，通常将文件控制块做成定长数据结构的一个记录，存放在目录文件中而这样的每 一个记录称为目录项。
2.目录文件
多个文件的文件控制块集中在一起组成了文件的目录通常，文件目录以文件的形式保存起来， 这个文件就被称为目录文件。
即把目录项（FCB）分为两部分，符号目录项（次部）和基本目录项（主部）其中，符号目 录项包含文件名以及相应的文件号；而基本目录项包含了除文件名外文件控制块的其他全部信息。
四、目录项分解法
五、UNIX的文件目录实现
六、FAT文件系统的实现
FAT文件系统三部分：
（1）引导扇区：
引导扇区（Boot Sector）包含用于描述卷的各种信息，利用这些信息才可以访 问文件系统
（2）文件分配表：
每个文件都给出了它在卷上的起始簇号。
（3）根目录
在FAT16文件系统中，位于根目录下的每个文件和子目录在根目录区中都包含一个目录项。
第四节 文件存储空间管理
一、磁盘空间管理
外存储设备中的空间容量比较大，对文件删除之后而不再使用的空间，必须加以回收，然后 在建立文件等操作中重新利用。
对于只读的存储设备（如CD-ROM光盘），无所谓回收，也无所谓动态分配，这种存储设备在 物理上就是不可重用的。
为了进行存储空间的分配与回收，在外存储设备上设置有空闲空间登记表，该表动态跟踪该 外存储设备上所有还没有分配给任何文件的空闲块的数目和块号。
二、磁盘空间的分配回收算法
1.位示图
位示图法的基本思想是，利用一串二进制位（bit）的值来反映磁盘空间的分配使用情况。
2.空闲块表
空闲块表是专门为空闲块建立的一张表，该表记录外存储器全部空闲的物理块：每一个空闲 块的第一个空闲物理块号和该空闲块中空闲物理块的个数。适合于文件物理结构为顺序结构的文 件系统。
3.空闲块链表
将外存储器中所有的空闲物理块连成一个链表，用一个空闲块首指针指向第一个空闲块，随 后的每个空闲块中都含有指向下一个空闲块的指针，最后一块的指针为空，表示链尾，这样就构 成了一个空闲块链表。
三、空闲块成组链接法
考点11 文件及文件目录的操作
文件系统是提供给用户使用的、用户可以进行按名存取所需要的文件。在文件系统的实现中， 为用户提供使用文件的手段是文件系统的重要任务之一。
下面介绍7个常用的进行文件操作的系统调用：
1、建立文件
用户调用 “建立文件”操作，需要提供所要创建的文件的文件名及若干参数：用户名、文件 名、存取方式、存储设备类型、记录格式、记录长度等。
建立文件系统调用的一般格式为：
create（文件名，访问权限，（最大长度））。
2、打开文件
任何一个文件使用前都要先打开，即把文件控制块FCB送到内存。
打开文件系统调用的一般格式为：fd=open（文件路径名，打开方式）。
3、读文件
读文件系统调用的一般格式为：
read（文件名，（文件内位置），要读的长度，内存目的地址）。
4、写文件
写文件系统调用的一般格式为：write（文件名，记录键，内存位置）。
把内存中指定单元的数据作为指定的一个记录写入指定文件中，系统还将为其分配物理块， 以便把记录信息写到外存上。
5、关闭文件
关闭文件系统调用的一般格式为：close（文件名）。
6、删除文件
删除文件系统调用的一般格式为：delete（文件名）。系统根据用户提供的文件名或文件描 述符，检查此次删除的合法性，若合法，则收回该文件所占用的文件控制块及物理块等资源。
7、指针定位
指针定位的一般格式为：seek（fd，新指针的位置）。
第五节 实现文件系统的表目
当用户申请打开一个文件时，系统要在内存中为该用户保存一些必要的信息，这些信息以表 格栏目中内容的形式出现，被称为表目。
一、系统打开文件表
二、用户打开文件表
第六节 文件及文件目录的操作
一、典型的文件操作
1.建立文件
2.打开文件
3.读文件
4.写文件
5.关闭文件
6.删除文件
7.指针定位
二、典型的目录操作
第七节 文件系统的性能
文件系统的物理基础是磁盘设备，显然，磁盘存储器的服务效率，其速度和可靠性，就成为文 件系统性能和可靠性的关键。
设计文件系统时应尽可能减少磁盘访问次数，这样，可以适当减少磁盘存储器性能对文件系统 性能的影响。
其他采取有效的措施，提高文件系统的性能。常见的技术措施有如磁盘高速缓存、RAID技术。
一、磁盘高速缓存
磁盘高速缓存：
基本思想：系统在内存中保存一些磁盘块，这些磁盘块在逻辑上属于磁盘，内存的这一区域 被称为块高速缓存。
运行时，系统检查所有的读请求，所需文件块如在块高速缓存中则直接在内存中进行读操作； 否则先启动磁盘，将所需块读到高速缓存中，再复制到其他内存区域。如果内存中的高速缓存已 满，则需要按照一定的算法淘汰一些较少使用的磁盘块，让出块高速缓存空间。块高速缓存的内 容需要定期写回到磁盘上，以保存对磁盘块的修改。
1.记录的成组
2.记录的分解
二、RAID技术
RAID技术：
RAID技术主要是解决两个问题：
1）磁盘速度慢
2）容易出现故障
第作节 文件共享、保护和保密
一、文件共享
文件的共享是指一个文件可以允许多个用户共同使用文件共享不仅是完成共同任务所必需， 而且还带来许多好处：节省文件所占用的存储空间；免除系统复制文件的工作；减少用户大量重 复性劳动；减少实际输入输出文件的次数此外，利用文件共享可以实现进程间相互通信。
在允许文件共享的系统中，必须对共享文件进行管理从共享的时间段上看，共享文件的使用 有两种情况：
（1）文件可以同时使用
（2）文件不允许同时使用
二、文件存取控制
1.建立副本
2.定时转储
3.规定文件的存取权限
三、UNIX的文件使用权限管理方案
1.存取控制矩阵
2.二级存取控制
3.UNIX中的文件存取权限
四、文件的保密措施
1.隐蔽文件目录
2.设置口令
3.使用密码
4.病毒防范
第七章 设备管理
第一节 I/O设备管理的基本概念
一、I/O设备管理的任务
输入输出设备（I/O设备）也称为外部设备（peripheral），包括计算机系统中除CPU和内存 储器以外的所有的硬件设备和装置
广义的输入输出设备即上述定义，狭义的输入输出设备不包括外存储设备
1）解决I/O设备性能同CPU性能不匹配
2）对多种I/O设备实现统一的管理，从而方便用户使用，是I/O设备管理的另一项重要任务。
3）如何保证用户安全正确的使用I/O设备。
二、I/O设备分类
1.按制备的使用特性分类
（1）输入设备
（2）输出设备
（3）交互式设备
特点：用户命令信息通过各种输入设备进入计算机系统，系统同步地在显示器上显示用户的 命令信息以及执行命令后所得到的处理结果。
（4）存储设备等
特性：
1）可写入性
2）可读出性
3）可保存性
2.按设备的信息组织方式分类
（1）字符设备（Character Device）
键盘、终端、打印机等以字符为单位组织和处理信息的设备。
（2）块设备（Block Device）
磁盘、磁带等以字符块为单位组织和处理信息的设备被称为块设备。
3.按设备使用可共享性分类
（1）独占设备：
在一个程序（作业、用户）的整个运行期间都必须由单个程序（作业、用户）独占直至该程序 ( 作业）完成的设备。
（2）共享设备：
能够同时让许多程序（作业、用户）使用的设备。
（3）虚拟设备：
在一类设备上模拟另一类设备，被模拟的设备称为虚拟设备。
通常用共享设备模拟独占设备（如用磁盘的固定区域模拟打印机），用高速设备模拟低速设备。 引入虚拟设备的目的是为了提高设备利用率。
三、I/O设备管理与文件管理的关系
第二节 I/O硬件和I/O软件的组成
一、I/O硬件组成
从硬件的角度看，设备由物理设备和电子部件两部分组成——操作系统而言更注重的是其电 子部件的控制方式
典型的计算机系统其硬件结构：中央部分是CPU和主存，通过总线与第二层的接口（适配器） 部件相连，第三层是各种外部设备控制器，最外层是外部设备
二、I/O软件组成
设计I/O软件结构的基本思想：
较低的层处理与硬件有关的细节，并将硬件的特征与较高的层隔离；而较高的层则向用户提 供一个友好的、清晰而规整的I/O接口。
一般的I/O软件结构分为四层：
1）中断处理程序；
2）设备驱动程序；
3）设备独立的操作系统软件；
4）用户级软件。
从功能上看，设备独立层是I/O软件的主要部分；
从代码量上看，设备驱动层是I/O软件的主要部分。
中断处理程序负责控制输入输出设备和内存与CPU之间的数据传送设备独立层起到承上启下 的作用
三、设备独立性
设计I/O软件的一个最关键的目标是设备独立性（device independence），即除了直接与设 备硬件打交道的低层软件之外，其他部分的软件并不依赖于硬件。
设备需要的I/O软件功能可以在与设备独立的软件中实现，这类软件面向用户应用层并提供一 个统一的接口
设备独立层软件的功能：设备驱动程序的统一接口，设备命名，设备保护，提供一个与设备 无关的逻辑块
缓冲，存储设备的块分配，独占设备的分配和释放，错误处理。
1.设备命名
在操作系统的I/O软件中，对I/O设备借用了与文件统一命名的方法，即采用文件系统路径名 的方法来命名设备。设备独立层的软件负责把设备的符号名映射到相应的设备驱动程序上。
2.设备保护
对设备进行必要的保护，防止无授权的应用或用户的非法使用。
3.提供一个与设备无关的逻辑块
与设备无关的软件就有必要向较高层软件屏蔽各种I/O设备空间大小、处理速度和传输速率 各不相同的这一事实，而向上层提供大小统一的逻辑块尺寸。
4.缓冲
对于常见的块设备和字符设备，一般都使用缓冲区。块设备：如果用户进程只写了半块数 据，则操作系统通常将数据保存在内部缓冲区，等到用户进程写完整块数据才将缓冲区的数据 写到磁盘上。
字符设备：当用户进程把数据写到设备的速度快于系统输出数据的速度时，必须使用缓冲
5.存储设备的块分配
在创建一个文件并向其中填入数据时，通常在硬盘中要为该文件分配新的存储块。 操作系统需要为每个磁盘设置一张空闲块表或位图。
6.独占设备的分配和释放
操作系统对设备使用请求进行检查，并根据申请设备的可用状况决定是接收该请求还是拒 绝该请求。
7.错误处理
一般来说错误处理是由设备驱动程序完成的。大多数错误是与设备密切相关的，因此，只 有驱动程序知道应如何处理（比如，重试、忽略或放弃）。
第三节 I/O设备控制方式
I/O设备的控制方式取决于I/O设备硬件与处理器和内存的联结方式以及其相应的设备驱 动程序。
一、程序控制方式
程序控制方式也称为PIO（Programmed I/O，程控I/O）方式，是指由用户进程直接控制 处理器或内存和外围设备之间进行信息传送的方式，也称为“忙-等”方式、轮询方式或循环 测试方式。
这种方式的控制者是用户进程。
二、中断控制方式
中断是一种在发生了一个异常事件时，调用相应处理程序（通常称为中断服务程序）进 行服务的过程。
三、DMA控制方式
DMA是直接内存访问（Direct Memory Access）的缩写，它是一种完全由硬件执行I/O数据交换的工作方式。
DMA控制器（DMA Controller，DMAC）从CPU完全接管对总线的控制，数据交换不经过CPU， 而直接在内存和外部设备之间进行。
由DMA控制器占用系统总线并向内存发出地址和控制信号，对传送信息的个数计数，并且以 中断方式向CPU报告传送操作的结束。
DMA方式的传送结构如图所示，可分为三个阶段：传送前预处理、数据传送、传送后处理
四、通道控制方式
通道（channel）是一个特殊功能的处理器，它有自己的指令和程序，可以实现对外部设备的统 一管理和外部设备与内存之间的数据传送。
与DMA方式相比，通道方式增加了CPU与通道操作的并行能力；增加了通道之间以及同一通道内各 设备之间的并行操作能力；为用户提供了灵活增加外设的可能性。
通道具有的功能：
接受CPU的指令，按指令与外部设备进行通信，从内存读取通道指令，执行通道程序，向设备控 制器和设备发送各种命令，组织外部设备和内存之间进行数据传送，并根据需要提供数据缓存的空间
从外部设备得到设备的状态信息，形成并保存通道本身的状态信息，根据要求将这些状态信息送 到内存的指定单元，供CPU使用，将外部设备的中断请求和通道本身的中断请求按序及时报告CPU
第四节 设备分配与回收
设备分配的相关数据结构和策略：
1.数据结构
设备分配算法的实现中，常采用的数据结构主要含四张表：
• 系统设备表（SDT）：每个接入系统中的设备都占有一个表目项。
• 设备控制表（DCT）：系统中的每台设备都有一张设备控制表DCT。
• 控制器控制表（COCT）：每个控制器都有一张控制器控制表COCT，用于登录某控制器的使用分配情况及与该控制器相连的通道的情况。
• 通道控制表（CHCT）：CHCT表反映了通道的情况，系统中的每个通道一张CHCT。
2.分配原则
设备分配的总原则是：要充分发挥设备的使用效率，尽可能地让设备忙碌，但又要避免由于不 合理的分配方法造成进程死锁。
设备分配方式有两种，即静态分配和动态分配。
（1）静态分配
基本思想：在用户作业开始执行前，由系统一次分配该作业所要求的全部设备、控制器（和通 道）。一旦分配之后，这些设备、控制器（和通道）就一直为该作业所占用，直到该作业被撤销。
2）动态分配
基本思想：在进程执行过程中根据执行需要进行。当进程需要设备时，通过系统调用命令向系统提出设备请求，由系统按照事先规定的策略给进程分配所需要的设备、I/O控制器（和通道），一旦用完之后，便立即释放。
3.分配策略
考虑的因素有：I/O设备的固有属性，I/O设备的分配算法，设备分配的安全性以及设 备独立性。
与进程调度相似，设备的分配策略通常采用先来先服务（FIFS）和高优先级优先等。
对于独占设备或共享设备，会根据其特性采用不同的分配策略，以期达到合理、高效 和安全的目的。
一、独占设备的分配
1.设备的绝对号与相对号
系统为每一台设备确定一个编号，以便区分和识别，这个确定的编号称为设备的“绝对号” 。 有时用户可能要求同时使用几台同类设备，为了避免使用时的混乱，用户可以把自己要求使用的若干台类设备给出编号，由用户在程序中定义的设备编号称设备的“相对号” 。
2.设备的指定方式
指定设备的方式可以有两种：一种是指定设备的绝对号，另一种是指定设备类、相对号。
（1）指定设备的绝对号，系统应该把与绝对号对应的设备分配给作业。如指定的这台设备占用或 者故障，则作业就阻塞不能执行。
（2）用户程序中通过“设备类、相对号”提出使用设备的要求这种方式使设备分配的适应性好、 灵活性强。
3.独占型设备的分配和释放
二、共享设备的分配
第五节 磁盘调度策略
一、信息传输时间
执行一次输入输出所花的时间如下：
1）寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。
2）延迟时间——指定扇区旋转到磁头下所需的时间。
3）传送时间——由磁头进行读写完成信息传送的时间。
传送信息所花的时间，是在硬件设计就固定的。
寻找时间和延迟时间是与信息在磁盘上的位置有关。
二、移臂调度及调度算法
磁盘是一种高速旋转的存储设备。移动磁臂上的磁头在沿着直径盘片的直径方向移动，同 时对指定的磁道上的扇面中的数据进行读写操作。
根据访问者指定的柱面位置来决定执行次序的调度，称为“移臂调度” 。
移臂调度的目的是尽可能地减少操作中的寻找时间。
常用的移臂调度算法有先来先服务算法、最短寻找时间优先算法、电梯调度算法和单向扫 描算法。
1.先来先服务调度算法
最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问 的物理位置，而只是考虑访问者提出访问请求的先后次序。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来 先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。
2.最短寻找时间优先调度算法
最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而 不管访问者到来的先后次序。
采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个 柱面的距离，与先来先服务算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服 务的平均时间，也就提高了系统效率。
3.电梯调度算法
乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。
他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯 目前运行方向是向上，所以电梯的行程是先把乘客张生从8层带到15层，然后电梯换成下行方向，把 乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。
前述的同一例子来讨论采用“电梯调度”算法的情况，由于磁臂的初始方向有两个，而该算 法是与磁臂的方向有关，所以分成两种情况来讨论：
（1）磁臂由里向外移动
开始时，在50号柱面执行操作的读写磁头的磁臂方向是由里向外，趋向32号柱面的位置， 当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是32号柱面，所以应先为32号柱面的 访问者服务，然后是为15号柱面的访问者服务，由于在向外移方向已无访问等待者，故改变磁臂的方向，由外向里依次为各访问者服务，这种情况下为等待访问者服务的次序是61，99，130，148，159，199。
（2）磁臂由外向里移动
开始时，正在50号柱面执行操作的读写磁头的磁臂是由外向里（即向柱面号增大的内圈方向） 趋向61号柱面的位置当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是61号柱面，所以应 先为61号柱面服务，然后按磁臂由外向里移动的方向，依次为99，130，148，159，199柱面的访问 者服务当201号柱面的操作结束后，向里移动的方向已经无访问等待者，所以改变磁臂的前进方向， 由里向外依次为32、15柱面的访问者服务。
4.单向扫描调度算法
单向扫描调度算法的基本思想是，不考虑访问者等待的先后次序，总是从0号柱面开始向里道 扫描，按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后个一个柱面后，立即 快速返回到0号柱面，返回时不为任何的访问者等待服务。在返回到0号柱面后，再次进行扫描。
三、旋转调度优化
四、信息的优化分布
第六节 缓冲技术
1.缓冲的引入
中断、DMA和通道控制技术使得系统中各I/O设备之间、I/O设备和CPU之间可以并行工作，但 I/O设备和CPU的处理速度不匹配的问题是客观存在的，中断方式时容易造成数据丢失。
引入缓冲区的作用：
解决I/O设备与处理机速度不匹配的问题
减少中断次数
根据I/O控制方式的不同，实现缓冲区的方法有两种：
（1）采用专用的硬件设置数据缓冲区。这种方法常常应用在外部设备的I/O控制器中。打印 机、键盘。
（2）在内存划出一定容量的专用数据缓冲区，以便存储输入/输出的数据，这种设置在内存 的缓冲区又称为“软件缓冲”。
2.缓冲的种类
根据系统设置的缓冲区的个数，可把缓冲技术分为以下几种：
1）单缓冲：在I/O设备和处理器之间设置一个缓冲区。
2）双缓冲区：解决两台I/O设备或者打印机和终端之间的并行操作问题。
3）多缓冲：一种具有多个缓冲区，其中一部分缓冲区专门用于输入，另一部分缓冲区专门用于输 出的缓冲结构
4）缓冲池：把多个缓冲区连接起来统一管理，在缓冲池中的每个缓冲区既可用于输入又可用于输 出的一种缓冲结构。
缓冲区是一种临界资源，所以在使用缓冲区时都有一个申请、释放和互斥的问题需要考虑。 缓冲池由多个缓冲区组成，而一个缓冲区由两部分组成：
（1）用来标识和管理该缓冲器的缓冲首部；
（2）用于存储数据的缓冲体。
3.缓冲池管理
第七节 虚拟设备技术
一、虚拟设备的实现原理——SPOOLing系统工作原理
虚拟设备技术，又称为SPOOLing技术，是多道程序设计系统中处理独占I/O设备的一种方法， 它可以提高设备利用率并缩短单个程序的响应时间。
SPOOLing技术之所以被称为虚拟设备技术，是因为它可以使进程在所需的外部设备不存在或被 占用的情况下使用该设备。
SPOOLing系统，全称为Simultaneous Peripheral OperationsOn-Line，其含义是同时的外部 设备联机操作，也称假脱机技术。
SPOOLing系统主要包括输入程序模块、输出程序模块、作业调度程序三部分。
二、SPOOLing的组成和实现
1.SPOOLing系统的组成
2.SPOOLing系统的实现——打印机的值班进程