NCRE4 · 网络工程师《操作系统原理》概要
前言
考试方式：
上机考试，总分50分，与四级其他一门课程合计考试时间长90分钟。
题型：
单选题 10道题 30分
多选题 10道题 20分
基本要求
1.掌握操作系统的基本概念、基本结构及运行机制。
2.深入理解进程线程模型，深入理解进程同步机制，深入理解死锁概念及解决方案。
3.掌握存储管理基本概念，掌握分区存储管理方案，深入理解虚拟页式存储管理方案。
4.深入理解文件系统的设计、实现，以及提高文件系统性能的各种方法。
5.了解I/O设备管理的基本概念、I/O软件组成，掌握典型的I/O设备管理技术。
6.了解操作系统的演化过程、新的设计思想和实现技术。
第一章 操作系统概论
考试内容：
1.操作系统基本的概念、特征、分类
2.操作系统主要功能
3.操作系统发展演化进程，典型操作系统
4.操作系统结构设计，典型的操作系统结构
操作系统基本的概念：
balabala...
操作系统的特征：
1.并发性：在多道程序环境下，并发性是指两个或多个时间在同一时间间隔内发生，即宏观上有多道程序同时执行，而微观上，在单处理机系统中每一个时刻仅能执行一道程序。
2.共享性：共享指系统中的资源可供多个并发执行的进程使用。
涉及资源：中央处理器、内存储器、外存储器、外部设备
共享方式：互斥共享、同时共享
3.随机性：也称异步性，不确定性，是指多道程序环境下，允许多个进程并发执行，由于资源的限制，进程的执行不是“一气呵成”的，是“走走停停”的。
操作系统的功能：
1.进程管理
进程管理、进程同步、进程间通信、调度
2.存储管理
内存的分配与回收、存储保护、内存扩充
3.文件管理
文件存储空间的管理、目录管理、文件系统的安全性
4.设备管理
缓冲管理、设备分配、设备处理
5.用户接口
命令接口、程序接口
操作系统分类：
按照用户界面的使用环境和功能特征，分为三种：批处理系统、分时系统、实时系统
随着计算机体系结构的发展，出现的多类型操作系统：个人操作系统、网络操作系统、分布式操作系统、嵌入式操作系统
一、批处理操作系统
1.基本工作方法
用户将作业交给操作员，在受到一定数量的作业后，由操作员把这批作业输入到计算机，最后将结果交给用户
2.特点与分类
成批处理作业，
缺点：用户不直接与计算机交互，不适合调试程序
优点：自动化较高，资源利用率高，作业吞吐量大，提高整个系统效率
分类：简单批处理系统、多道批处理系统
单道批处理系统：主要特征：自动性、顺序性、单道性
多道批处理系统：引入的好处：提高CPU的利用率；可提高内存和I/O设备的利用率；增加系统吞吐量
3.设计思想
先把一个作业调入内存，等这个作业运行完毕，再调入下一个作业，如此反复，直到作业处理完毕
作业及作业的衔接都有监控程序自动控制，提高了作业运行效率
4.作业控制说明书
由作业控制语言编写的一段程序，通常放在程序前面，执行师，由程序读入作业控制说明书，按照说明书中的语句执行。
STEP1 ASM A
STEP2 FTN B
STEP3 LINK A,B,C
STEP4 RUN C
5.一般指令和特权指令
特权指令：输入输出指令、停机指令等。只要监控程序才能执行特权指令。
用户只能执行一般指令，如需执行特权指令，处理器会将控制权移交给监控程序。
6.假脱机技术（SPOOLing）
6.1假脱机的概念
假脱机技术（SPOOLing）是指在联机情况下实现的同时外围操作，也称假脱机输入输出操作，它是操作系统中的一项将独占设备改为共享设备的技术。
6.2假脱机技术的组成
假脱机技术由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程、请求打印队列组成。SPOOLing系统的组成如下图所示。
6.3假脱机技术的特点
（1）提高了输入输出速度
（2）将独占设备改造为共享设备
（3）实现了虚拟设备的功能
二、分时系统
1.基本工作方式
用户通过终端交互式地向系统提出命令，系统接受命令后，采用时间片轮转方式处理服务请求
2.设计思想
将CPU的时间划分为若干个时间段、操作系统以时间片为单位，轮流为每个终端用户服务
3.特点
多路性：多个用户在同时使用一台计算机
交互性：用户直接干预操作的每一步
独占性：用户感觉不到计算机为他人服务
及时性：系统能对用户提出的额请求即使给予响应
4.影响响应时间的因素
机器处理能力
请求服务的时间长短
系统中连接的终端数目
服务请求的分布
调度算法（时间片的选取）
三、实时系统
实时系统是指系统能及时响应外部事件的请求，在规定的时间内，完成对该事件的处理，并控制所有实时任务协调一致地运行。
分类：
第一类：实时过程控制
工业控制，军事控制，...
第二类：实时通信（信息）处理
电讯（自动交换），银行，飞机订票，故事行情
实时系统的特征：有多路性、独立性、及时性、交互性和可靠性。
四、嵌入式操作系统
在各种设备、装置或系统中，完成特定功能的软硬件系统
它们是一个大设备、装置或系统中的一部分，这个大设备、装置或系统可以不是“计算机”
通常工作在反应式或对处理时间有较严格要求环境中
由于它们被嵌入在各种设备、装置或系统中，因此称为嵌入式系统
嵌入式领域广泛使用的操作系统有：嵌入式Linux、Windows Fmbedded、VxWorks等，以及应用在智能手机和平板电脑的Android、iOS等。
特点：系统内核小、专用性强、系统精简、高实用性、多任务的操作系统
五、个人计算机操作系统
单用户多任务的操作系统，比如Windows
特点：界面友好、使用方便、用户无需具备专门的知识，也能熟练使用。
六、网络操作系统
网络操作系统用于管理网络中的各种资源，为用户提供各种资源。其主要功能有网络通信管理、网络资源管理、网络安全管理和网络服务等。
类型：客户/服务器模式（C/S），对等模式
七、分布式操作系统
分布式处理系统是指由多个分散的处理单元经互联网络的连接而形成的系统。在分布式系统上配置的操作系统成为分布式操作系统。
特点：
分布性
并行性
透明性
共享性
健壮性
八、智能卡操作系统
它一般是紧紧围绕着它所服务的智能卡的特点而开发的。由于不可避免地收到了智能卡内微处理器芯片的性能及内存容量的影响，因此，在很大程度上不同于我们通常所见到的微机上的操作系统（例如DOS、UNIX等）。
网络和分布式操作系统的区别：
1.分布具有各个计算机间相互通讯，无主从关系；网络有主从关系、
2.分布式系统资源为所有用户共享；而网络有限制地共享。
3.分布式系统中若干个计算机可相互协作共同完成一项任务。
操作系统的发展（演化）
1.手工操作系统
2.监控程序（早期批处理）
3.多道批处理
4.分时系统
5.UNIX通用操作系统
6.个人计算机操作系统
7.Android操作系统
操作系统结构
按照系统的功能和特性要求，选择合适的结构，使用相应的结构设计方法将系统逐步地分解、抽象和综合，使操作系统结构清晰、简单、可靠、易读、易修改，而且使用方便，适应性强。
整体式结构
层次式结构
微内核（客户机/服务器）结构
一、整体结构
模块接口法、无序模块法、模块组合法
特点：根据功能划分模块
优点：结构紧密，接口简单直接，模块之间转接的灵活性使系统效率高
缺点：由于模块之间可以任意相互调用，形成网络，各模块相互联系，独立性差，系统结构不清晰
结论：可适应性较差，使用与规模较小、使用环境比较稳定却要求效率较高的系统
二、层次结构
balabala...
三、微内核结构
balabala...
第二章 操作系统运行机制
考试内容：
1.内核态与用户态
2.中断与异常
3.系统调用接口
4.存储系统
5.I/O系统
6.时钟（CLock）
一、CPU的构成与基本工作方式
处理器由运算器、控制器、一系列的寄存器以及高速缓存构成
运算器实现指令中的算术和逻辑运算，是计算机计算的核心
控制器负责控制程序运行的流程，包括取指令维护CPU状态、CPU与内存的交互等等
寄存器是指令在CPU内部做处理的过程中暂存数据、地址以及指令信息的存储设备
在计算机的存储系统中它具有最快的访问速度，高速缓存处于CPU和物理内存之间
利用程序局部性原理使得高速指令处理和低速内存访问得以匹配，从而提高CPU的效率
1.处理器中的寄存器
寄存器提供了一定的存储能力
速度比驻村快得多
造价高，容量一般都很小
两类寄存器：
用户可见寄存器，高级语言编译器通过算法分析并使用之，以减少程序访问主存次数
控制和状态寄存器，用于控制处理器的操作由OS的特权代码使用，以控制其它程序的执行
用户可见寄存器：机器语言直接引用
包括数据寄存器、地址寄存器以及条件码寄存器
数据寄存器（data register）又称通用寄存器，主要用于各种算术逻辑指令和访存指令
地址寄存器（address register）用于存储数据及指令的物理地址、线性地址或者有效地址，用于某种特定方式的寻址。如index register、segment pointer、stack pointer
条件码寄存器保存CPU操作结果的各种标记位，如算术运算产生的溢出、符号等等
控制和状态寄存器
用于控制处理器的操作
大部分对于用户是不可见的
一部分可以在某种特权模式（由OS使用）下访问
常见的控制和状态寄存器：
程序计数器（PC：Program Counter），记录将要取出的指令的地址
指令寄存器（IR：Instruction Register），包含最近取出的指令
程序状态字（PSW：Program Status Word），记录处理剂的运行模式信息等等
2.指令执行的基本过程
两个步骤：
先从储存器中每次读取一条指令
然后执行这条指令
一个单条指令处理过程称为一个指令周期
程序的执行是由不断取和执行的指令周期组成
仅当关机、出错或有停机相关指令时，程序才停止
3.特权指令和非特权指令
特权指令：只能由操作系统使用的指令
使用多道程序设计技术的计算机指令系统必须要区分为特权指令和非特权指令，特权指令一般引起处理器状态的切换。
处理器通过特殊的机制将处理器状态切换到操作系统运行的特权状态（管态）
4.处理器的状态
根据运行程序对资源和机器指令的使用权限将处理器设置为不同状态
管态：操作系统管理程序运行的状态，较高特权级别，又成为特权态（特态）、系统态、核心态
目态：用户程序运行时的状态，较低的特权级别，又称为（普态）、用户态
有些系统将处理器状态分为核心状态，管理状态和用户程序状态（目标状态）三种。
管态和目态的差别：
全部指令（包括特权指令）可以执行
可使用所有资源
具有改变处理器状态的能力
目态->管态
其转换的唯一途径是通过中断
管态->目态
可用设置PSW（修改程序状态字）可实现
5.程序状态字PSW
在PSW中专门设置一位，根据运行程序使用指令的权限而设置，PSW（Program Status Word）：
CPU的工作状态码——指明管态还是目态，用来说明当前在CPU上执行的是操作系统还是一般用户，从而决定其是否可以使用特权指令或拥有其它的特殊权利
条件码——反映指令执行后的结果特征
中断屏蔽吗——指出是否允许中断
二、存储体系
支持OS运行硬件环境的一个重要方面：
作业必须把它的程序和数据存放在内存中才能运行
多道程系统中，若干程序和相关的数据要放入主存储器
操作系统要管理、保护程序和数据，使它们不至于受到破坏
操作系统本身也要存放主存储器中并运行
1.存储器的层次结构
存储系统设计三个问题：
容量、速度和成本
容量：需求无止境
速度：能匹配处理器的速度
成本问题：成本和其它部件相比应在合适范围之内
2.存储保护
对主存中的信息加以严格的保护，是操作系统及其它程序不被破坏，是其正确运行的基本条件之一
多用户、多任务操作系统：
OS给每个运行进程分配一个存储区域
为了保证软件程序只影响程序的内部
硬件可提供如下功能：
界地址寄存器（界限寄存器）
实现方法：
在CPU中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址
也可将一个寄存器作为基址寄存器，另一寄存器作为限长寄存器（指示存储区长度）
每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界
如果未越界，则按此地址访问主存，否则将产生程序中断——越界中断（存储保护中断）
存储键
三、中断与异常机制
中断对于操作系统的重要性就像机器中的驱动齿轮一样，所以有人把操作系统成为是由“中断驱动”或者“（中断）事件驱动”，它使得OS可以捕获用户程序发出的系统功能调用及时处理设备的中断请求，定时启动指定程序
中断的概念：
CPU对系统发生的某个事件作出的一种反应
CPU暂停正在执行的程序，保留现场后自动转去执行相应事件的处理程序，处理完成后返回断电，继续执行被打断的程序
特点：
1.中断是随机的
2.中断是可恢复的
3.中断是自动处理的
中断/异常概念：
中断/异常：balabala...
中断的引入：balabala...
异常的引入：balabala...
早期的中断和异常并没有区分，都把它们叫做中断。随着它们的发生原因和处理方式的差别愈发明显，才有了以后的中断和异常
中断的分类：
广义中断：
中断（外中断）：
I/O中断
时钟中断
硬件故障中断
异常（内中断）例外：
系统调用
缺页异常
断点指令
其他程序性异常（如算术溢出等）
中断（狭义）与异常的区别：
中断：与正执行指令无关，可以屏蔽
异常：与正执行指令有关，不可屏蔽
中断系统是现代计算机系统的核心机制之一。
中断系统的两大组成部分：硬件中断装置和软件中断处理程序
中断寄存器：
有的计算机中，由于可能有很多中断源请求同时发生，为了区分和不丢失中断信号，对应每个中断源分别用一固定触发器寄存中断信号。
规定值为1时，表示有中断信号，为0时表示无
这些触发器的全体称为中断寄存器
每个触发器称为一个中断位
所以中断寄存器是由若干个中断位组成
处理器如何发现中断信号？
处理器的控制部件中设一个能检测中断的机构成为中断扫描机构。
在每条指令执行周期的最后时刻扫描中断寄存器，询问是否有中断信号。
若无中断信号，继续执行下一条指令。
若有中断，中断硬件将该中断触发器内容按规定编码送入PSW的相应位，称为中断码。
典型的中断处理
I/O中断
由I/O设备的控制器或者通道发出
两类I/O中断：
I/O操作正常结束
如果要继续I/O操作，需要在准备好以后重新启动I/O
若请求I/O程序正处于等待I/O状态，则应将其唤醒
I/O异常
设备故障或特殊情况
设备故障时需要重新执行失败的I/O操作
重试次数有上限，次数过大，系统将判定硬件故障
时钟中断
系统多道能力的重要推动力量，时钟中断处理程序通常做与系统运转、管理和维护相关的工作，包括：
维护软件时钟：系统有若干个软件时钟，控制定时任务以及进程的处理器时间配额，时钟中断需要维护、定时更新这些软件时钟
处理器时间调度：维护当前进程时间片软件时钟，并在当前进程时间片到时以后运行调度程序选择下一个被调度的进程
控制系统定时任务：通过软件时钟和调度程序定时激活一些系统任务，如检测死锁、系统记账、系统审计等
硬件故障中断
硬件故障中断处理程序一般需要做的工作：
保存现场，使用一定警告手段，提供些辅助诊断信息
在高可靠系统中，中断处理程序还要评估系统可用性，尽可能恢复系统
程序性中断
程序指令出错、指令越权或者指令寻址越界而引发
两类处理方法：
1.只能由操作系统的相关扩展功能模块完成，多为程序试图做不能做的操作引起得系统保护
2.可由系统自己完成，如一些算术运算错误
四、系统调用
1.系统调用与一般过程调用的特点
1）运行在不同的系统状态
2）状态的转换
3）返回问题
4）嵌套调用
系统调用的处理步骤
balabala...
五、I/O技术
主要的I/O控制方式
通道
DMA技术
缓冲技术
通道
独立于中央处理器，专门负责数据I/O传输的处理机，它对外设实现统一管理，代替CPU对I/O操作进行控制，使CPU和外设可以并行工作
通道又称为I/O处理机
引入通道的目的：
为了使CPU从I/O事务中解脱出来
同时为了提高CPU与设备、设备与设备之间的并行度
DMA技术
中断的引入大大地提高了处理器处理I/O的效率，当处理器和I/O间传送数据时，效率任旧不高
解决方法：
直接存储器访问（DMA：Direct Memory Access）
通过系统总线中一独立控制单元——DMA控制器自动控制成块数据在内存和I/O单元间的传送，大大提高处理I/O的效能
缓冲技术
缓冲区是硬件设备之间进行数据传输时，用来暂存数据的一个存储区域
缓冲技术的三种用途：
处理器与主存储器之间
处理器和其它外部设备之间
设备和设备之间的通信
目的：解决硬件之间速度不匹配的问题
单缓冲区：
设备向缓冲区输入数据直到装满后，必须等待CPU将其取完，才能继续向其中输入数据。
为了提高设备利用率，单缓冲区不够
多缓冲区（Cache）技术：
Cache：离CPU最近，使CPU快速访问常使用的数据
如果没有，CPU到二级Cache中找
如果没有，CPU到系统内存中找
六、时钟
操作系统时钟是微机上所有软件获取时间的主要来源，其位置至关重要。
操作系统时钟的时间是硬件提供的，如果危机硬件时钟有错，就会影响到操作系统。
时钟一般分为硬件时钟和软件时钟
时钟的用途可分为绝对时钟和相对时钟
第三章 进程线程模型
考试内容：
1.并发环境与多道程序设计
2.进程的基本概念，进程控制块（PCB）
3.进程状态及状态转换
4.进程控制：创建、撤销、阻塞、唤醒、fork()的使用
5.线程基本概念，线程的实现机制
6.处理机调度
一、并发环境与多道程序设计
1.程序的顺序执行
程序：指令或语句序列，体现了某种算法，所有程序是顺序的
顺序环境：在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不收外界影响。
顺序执行的特征：
顺序性
封闭性
程序执行结果的确定性
程序结果的可再现性
2.多道程序系统
计算机能够同时处理多个具有独立功能的程序，以增强系统的处理能力和提高机器的利用率
多道程序的特点：
独立性
随机性
资源共享性
3.程序的并发执行
并发环境：
在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事前确定的。
并发的特征：
1）并发程序在执行期间具有相互制约关系
2）程序与计算不在一一对应
3）并发程序执行结果不可再现
二、进程模型
1.进程的概念
进程是正在执行的程序，从操作系统角度可分为系统进程和用户进程。
进程和程序既有联系又有区别。
2.进程的特性
并发性
动态性
独立性
交往性
异步性
3.进程的基本状态及其转换
进程的基本状态：
不同系统设置的进程状态数目不同
三状态进程模型
五状态进程模型
七状态进程模型
进程的三种基本状态
1）就绪状态
2）运行状态
3）等待状态
4）创建状态
5）结束状态
6）挂起状态
7）激活状态
进程状态间的转换
1）新状态->就绪状态
2）就绪状态->执行状态
3）执行状态->阻塞状态
4）执行状态->就绪状态
5）阻塞状态->就绪状态
6）执行状态->终止状态
4.进程控制块（PCB）的内容：
分为调度信息和现场信息两大部分。
调度信息供进程调度时使用，描述进程当前所处的状况。
现场信息刻画了进程的运行情况。
进程的组成：
程序、数据和进程控制块（PCB）
5.PCB表的组织方式
1）线性方式
2）索引方式
3）链接方式
6.进程控制
创建、撤销进程以及完成进程各状态之间的转换，由具有特定功能的原语完成。
创建原语
撤销原语
阻塞原语
唤醒原语
Unix的fork()函数
父进程通过fork()创建子进程
特点：只被执行一次，返回两次结果，一次是在调用进程中，一次是在创建的子进程中，父进程中返回的是子进程的PID，子进程中fork()返回0。
程序
int main(){
pid_t pid;
int x = 1;
pid = fork();
if(pid==0){
printf("child:x=%d\n",++x);
}
printf("parent:x=%d\n",--x);
}有两种可能的运行结果：
child:x=2;
parent:x=0
程序1
int main(){
fork();
printf("hello!\n");
}输出两个hello!
程序2
int main(){
fork();
fork();
printf("hello!\n");
}输出四个hello!
进程的创建
创建一个PCB
赋予一个统一进程标识符
为进程映像分配空间
初始化进程控制块
设置相应的链接
进程的撤销
1）引起进程撤销的事件有三类：
进程正常结束
在进程运行期间，由于出现某些错误和故障而使进程被迫中止
进程应外界的请求而终止运行
2）进程撤销的过程
balabala...
进程阻塞和进程唤醒
1）引起进程阻塞的事件
请求系统服务
启动某种操作
新数据尚未到达
无新工作可做
2）引起进程唤醒的事件
请求系统服务得到满足
启动某种操作完成
新数据已经到达
有新工作可做
7.线程的控制
进程作为系统中的一个基本单位，具有两个属性：一是资源分配和拥有的基本单位。二是一个可以地理调度和执行的基本单位。
而在进程操作过程中，因为进程是一个资源的拥有者。所以，系统要不断地进行资源的分配与回收、现场的保存、恢复等工作。系统要为此付出较大的时间与空间的开销。此外，在系统中所设置的进程数目不能过多，进程切换的频度不能过高，这就限制了系统并发程度的进一步提高。
如何能使进程更好地并发执行，同时又能尽量减少系统开销呢？
将进程的两个属性分开，由操作系统分别处理，即只作为资源分配与拥有的单位，不再是调度和执行的基本单位，使之轻装前进，而对资源分配与拥有的基本单位，不进行频繁的切换处理，以减少系统开销。正是因为这种思想，产生了一个新的概念——线程。
8.线程的概念
线程是进程中的一个实体，是被系统独立调度和执行的基本单位。
线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器、一组寄存器和栈），但是它可以与同属于一个进程的其他线程共享进程所拥有的全部资源。
一个线程可以创建和撤销另一个进程，同一进程中的多个线程之间可以并发执行。线程之间也会相互制约，使其在运行中呈现异步性。因此，线程同样具有就绪、执行、阻塞三种基本状态。
9.线程与进程的比较
1）调度
传统操作系统中，进程是作为资源分配和独立调度的基本单位。在引入线程的操作系统中，则把线程作为调度和分派的基本单位，把进程作为资源拥有的基本单位。
2）并发性
引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行。
3）拥有资源
无论哪种操作系统，进程都是拥有资源的一个独立单位，一般情况，线程自己不拥有系统资源，但线程可以访问属于进程的资源。
4）系统开销
由于进程的创建和撤销都需要分配拟或回收资源，因此操作系统所付出的开销显著大于创建和撤销进程时的开销。
同样，进程切换的开销也远大于线程切换的开销。
简而言之，一个程序至少有一个进程，一个进程至少有一个线程。
10.线程的实现机制
1）用户级线程。用户级线程是由用户控制的，对于用户级线程的创建、撤销与切换，都与系统控制无关，完全由用户自己管理。简单来说就是系统并不知道有用户级线程的存在，在系统中各种控制仍然是基于进程的。
2）内核级线程。内核级线程是依赖于内核，即无论是用户进程中的线程，还是系统进程中的线程，它们的创建、撤销与切换都是由内核实现的。在系统中保留了一张线程控制块，系统根据该线程控制块来赶回线程的存在，并对线程进行控制。
3）混合实现方式。同时实现用户级和内核级线程。
11.Pthread进程包
Pthread是一套用户级线程库，定义了线程标准，大部分的UNIX系统都支持该标准。
12.进程调度的概述
调度分层次的，可分为高级调度、中级调度、低级调度。
高级调度：它用于确定把后备队列上的哪些作业调入内存。
中级调度：核心按一定的调度算法，将内存中处于等待状态的某些进程调至外存对换区，来腾空这部分内存。
低级调度（进程调度）：指在多道程序环境下，内核按一定的调度算法，从就绪队列中选出一进程，把处理机分配给它。
进程调度的时机：
1）正在执行的进程运行完毕
2）正在执行的进程调用阻塞原语将自己阻塞，进入等待状态
3）调用激活原语激活等待资源的进程
4）时间片用完
5）就绪队列中的某个进程的优先级高于当前运行进程的优先级
13.调度算法设计原则
1）面向用户的原则。这是为满足用户的需求而遵循的一些准则。
2）面向系统的原则。这是为了满足系统要求而遵循的一些准则。
14.进程（线程调度算法）
1）先来先服务调度算法（FCFS）
先来先服务调度算法的裁决模式是非抢占式的，优先权函数=花费在系统中的实际时间，仲裁规则是随机的。这种调度算法有利于长进程，而不利于短进程。
2）最短作业优先调度算法（SPF）
短进程优先调度算法的裁决模式是非抢占式的，优先权函数=-运行时间，仲裁规则是按照时间先后顺序或随机方式。这种调度算法照顾到了系统中的短进程，有目的地降低了进程的平均等待时间，提高了系统的吞吐量。但是，这种算法对长进程不利。
3）最短剩余时间优先调度算法（SRT）
最短剩余时间优先调度算法的裁决模式是抢占式的，优先权函数是动态的，随着进程运行和完成时间的减少而增加，仲裁规则是按照时间先后顺序或随机方式。这种调度算法充分照顾到了剩余运行时间短的进程。
4）最短剩余时间优先调度算法（SRT）
时间片轮转调度算法的裁决模式是面向时间片的，所有就绪进程的优先权函数值相同，仲裁规则是轮转规则。这种调度算法适用于交互进程的调度。
5）最高优先级调度算法
优先权调度算法的裁决模式是抢占式的或非抢占式的，优先权函数是用户或系统赋予给它的优先权，仲裁规则是随机的或先进先出的。
6）多级反馈队列调度算法（MLF）
多级反馈队列调度算法的裁决模式是抢占式的或非抢占式的，优先权函数是从最大值开始每执行一次递减1，仲裁规则是轮转的或按照时间先后次序。
第四章 并发与同步
考试内容
1.进程的同步与互斥
2.信号量
3.管程
4.进程的通信
1.进程的相互作用
1.1相关进程和无关进程
1）进程互斥
2）进程同步
1.2与时间有关的错误
2.进程互斥
解决办法两种：
1）由竞争双方平等协商
2）引入进程管理者
资源共享的程度分为三个层次：互斥、死锁、饥饿
2.1临界资源的概念
临界资源的访问过程：
进入区、临界区、退出区、剩余区
2.2进程同步机制应遵循的原则
1）空闲让进
2）忙则等待
3）有限等待
4）让权等待
进程互斥的软件方法
1）单标志算法
while(turn!=i); 临界区 turn=j; 剩余区
2）双标志、先检查算法
while(flag[j]) flag[i]=true; 临界区 flag[i]=flase; 剩余区
3）双标志、后检查算法
flag[i]=true; while(flag[j]); flag[i]=false; 剩余区
4）先修改、后检查、后修改者等待算法
flag[i]=true; turn=j; while(flag[j]&&turn==j); 临界区 flag[i]=false; 剩余区
进程互斥的硬件方法
1）TS指令
每个临界区设置一个公共变量lock:true表示正被占用，false表示空闲进入区利用TS进行检查和修改表示lock。
2）Swap指令
balabala...
3）信号量
1965年，荷兰学者Dijksrea提出的信号量机制是一种很有效的进程同步工具，得到了广泛的使用。这里讲介绍最简单的经常使用的信号量——整型信号量。
信号量是一种特殊变量，它用来表示系统中资源的使用情况。而整型信号量就是一个整型变量。当其值大于“0”时，表示系统中对应可用资源的数目；当其值小于“0”时，其绝对值表示因该资源被阻塞的进程的数目；当其值等于“0”时，表示系统中对应资源已经用完，并且没有因该资源而被阻塞的进程。
对信号量的操作：
对于整型信号量，仅能通过两个标准的原语操作来访问，这两个操作被称为P操作、V操作，也合称为PV操作。其中P操作在进入临界区前执行，V操作在退出临界区后执行。
P操作，用wait(s)来描述：
wait(s)
{
--s.count; // 表示申请一个资源
if(s.count<0) // 表示没有空闲资源
{
调用进程进入等待队列s.queue;
阻塞调用进程;
}
}V操作，用signal(s)来描述：
signal(s)
{
++s.count; // 表示申请一个资源
if(s.count<0) // 表示没有空闲资源
{
从等待队列s.queue中取出头一个进程；
进程P进入就绪队列；
}
}3.经典的进程同步问题
简单生产者-消费者问题
生产者进程P：
while(true){
P(empty)
生产一个产品;
送到缓冲区;
V(full);
}
消费者进程Q：
while(true){
P(full)
从缓冲器取产品;
V(full);
消费产品;
}
利用PV操作实现进程同步的方法
1）使用PV操作的规则
1>分清哪些是互斥问题，哪些是同步问题
2>对于互斥问题要设置互斥信号量，互斥信号量的个数只与临界资源的种类有关。通常，有几类临界资源就设置几个互斥信号量，且初值为1，代表临界资源可用
2>对于同步问题要设置同步信号量，通常同步信号量个数与可参与同步的进程种类有关。同步信号量表示该资源是否可以开始或者进程是否已经结束。
4>在每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现，但是，它们分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的P操作，则其顺序不能颠倒。必须先执行对同步信号量的P操作，再执行对互斥信号的P操作。但是，V操作的顺序没有严格要求。
2）同步互斥问题的解题步骤：
1>确定进程
2>确定同步互斥关系
4.管程
4.1引入管程的原因
每个访问临界资源的进程都必须使用PV操作，是的大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，还可能因同步操作使用不当而导致系统故障，如顺序不当、读写、漏写等。为此，又产生了一种新的进程同步管理工具——管程。
4.2管程的组成
管程由四部分组成：管程名称、共享数据的说明、对该数据进行操作的一组过程、对共享数据设置初始值的语句。此外，每个管程都有唯一的名字来标示。管程类似于面向对象程序设计中的类。
4.3利用管程实现经典的同步问题
进程或者线程的阻塞和唤醒，可以通过管程的wait和signal操作来巧妙地实现，所有管程中的过程是互斥的。balabala...
1）wait原语
2）signal原语
为了区别阻塞的原因，需要设置一个条件变量。条件变量是一个整型变量，用condition说明，balabala...
管程具有的三个特征：
1）模块化
2）抽象数据类型
3）信息隐蔽
5.进程通信
进程的同步与互斥成为低级通信。
用户直接利用操作系统提供的一组通信命令，高效地传送大量数据，成为高级通信，又称管道通信。
balabala...
进程之间的通信方式：
1）共享内存
2）消息机制
3）通过共享文件
6.共享内存
在相互通信的进程之间设置一个公共的内存区，一组进程向该公共内存中写，另一组进程从内存中读，通过这种方式实现两个进程之间的信息交换。
7.消息机制
在消息机制中，进程间的数据交换是以消息为单位进行的。用户直接利用系统中提供的一组通信命令（原语）进行通信。
1）消息缓冲通信
balabala...
发送原语：Send(Receiver,message);
接收原语：Receive(Send,message);
2）信箱通信方式
balabala...
1>信箱通信的操作
2>信箱的分类
3>进程间的关系
8.管道通信系统
balabala...
第五章 存储管理方案
考试内容
1.存储管理基本概念，存储管理基本任务
2.分区存储管理方案
3.覆盖技术与交换技术
4.虚存概念与虚拟存储技术
5.虚拟页式存储管理方案
1.存储体系
2.存储器管理的主要任务
存储器由外存和内存组成
内存空间分为两部分：系统区、用户区
1）内存的分配和回收
2）存储共享
3）存储保护
4）权限保护
2.1内存的分配和回收
1）记住每个存储区域的状态
2）实施分配
3）回收
实现方法：
位示图表示法
空闲页面表
空闲块表
内存分配的方式：
1）静态分配
2）动态分配
2.2存储共享
指两个或多个进程公用内存中的相同区域，使多道程序动态地共享，提高内存利用率
共享内容：代码共享、数据共享
2.3存储共享
存储保护内容
1）地址越界保护
2）权限保护
3）存储键保护
2.4扩充内存
用户在编程的时候，不应该受内存容量限制，要采用一定的技术“扩充”内存的容量。
采用虚拟存储技术或其他交互技术。
3.地址转换
将用户程序的逻辑地址转换为运行时的物理地址的过程称为地址转换，也称为地址映射（即重定位）。
静态重定位：在程序装入时，把程序中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在程序开始执行前集中完成的，所以在程序执行过程中就无需在进行地址转换工作。
动态重定位：在程序装入时，不进行地址转换，而是直接把程序装入到分配的内存区域中。在程序执行过程中，每当执行一条指令时由硬件的地址转换机构将指令中的逻辑地址转换成物理地址。
4.固定分区
基本定理
固定分区存储管理方式是最早使用的一种可以运行多道程序的存储管理方式。它要求把作业全部装入主存，且装入一个连续的存储空间。
基本特点
1）一个作业只能装入一个分区，不能装入两个或多个相邻分区。一个分区只能装入一个作业，当分区大小不能满足作业的要求时，该作业暂时不能装入。
2）通过对“分区分配表”的改写，来实现对主存空间的分配与回收。作业在执行时，不会改变存储区域，所以采用静态地址重定位方式易于实现，且系统开销小。
3）当分区较大作业较小时，仍然浪费许多主存空间，并且分区总数固定，限制了并发执行的作业数目。
主存空间的分配
在作业分配之前，根据主存分区的划分情况，在分区分配表中填入每个分区的起始地址（简称始址）、大小，在状态栏中一律跳入“0”，表示该分区可用，当作业装入时填入作业名。
5.可变分区
可变分区存储管理方式又称为动态分区存储管理方式。它是根据用户作业的大小，在作业要求装入主存时，动态地划分分区，使分区的大小正好适应作业的要求。采用这种存储管理方式，分区的大小是不定的，分区的数目也是不定的。
可变分区存储管理方式必须解决三个问题：
一是分区分配中所用的数据结构
二是分区的分配算法
三是分区的分配和回收
移动技术
可变分区中，内存经过一段时间的分配和回收后，会存在很小的空闲快，这些小块不足以满足程序进一步分配内存的要求，但其总和却可以满足程序的分配要求，解决的办法就是“碎片整理”，这一技术成为“移动技术”。
移动技术注意的问题：
1）移动会增加系统的开销
2）移动是有条件的
5.1采用的数据结构
为了实现可变分区分配，系统必须配置相应的数据结构，用来记录主存的使用情况，包括空闲分区的情况和已分分区的情况，为作业分配主存空间提供依据。为此，设置了两张表，即已分分区表和空闲分区表。
5.2主存空间的分配
分配主存时，先分配小地址，再分配大地址。空闲分区表中记录的排列也是从小地址向大地址排列的。首次分配时，只有一个空闲区。
常用的主存分配算法
1）最先适应分配算法（FF）
它要求空闲分区表中的记录按地址递增的顺序排列。在每次分配主存时，总是从第1条开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区。一部分分配作业，另一部分仍作为空闲区。
它的特点是分配算法简单，容易差生过多的主存碎片。主存碎片是指小的不能使用的主存空间；这种算法把大的空闲区分成了小的空闲区，当有大作业要求分配时，不能满足要求，降低了系统的效率。
2）最优适应分配算法（BF）
它是从所有的空闲分区中挑选一个能满足作业要求的最小的空闲区进行分配。这样可以保证不去分割一个更大的空闲区，使装入大作业时比较容易得到满足。为了实现这种算法，把空闲区按长度递增次序登记在空闲分区表中，分配时，顺序查找。
它的优点是解决了大作业的分配问题，不足是容易产生主存碎片，降低了主存空间的利用率。另外收回主存时，要按长度递增顺序插入到空闲分区表中，增加了系统开销（操作系统所占有的系统资源和所需要的处理器的时间成为“系统开销”）。
3）最坏适应分配算法（WF）
它每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小而成为主存碎片。为了实现这种算法，把空闲区按长度递减的次序登记在空闲分区表中，分配时，顺序查找。
它的优点是不会产生过多的碎片，不足是影响大作业的分配。另外收回主存时，要按长度递减的顺序插入到空闲分区表中，增加了系统的开销。
4）下次分配算法
当接到内存申请时，查找分区说明，从上一次分配的位置开始扫描内存，选择下一个大小足够的可用块。
5.3主存空间的回收
1）回收的分区前后没有相邻的空闲分区
2）回收分区的前后有相邻的空闲区
3）回收分区的后面有相邻的空闲分区
4）回收分区的前后都有相邻的空闲分区
分区管理的优缺点：
1）分区的长度不是预先固定的，而是按作业的实际需求来划分的。分区的个数也不是预先确定的，而是由装入的作业个数决定的。
2）分区的大小由作业的大小决定，提高了主存的使用频率。
3）在主存分配过程中，会产生许多主存碎片，造成主存空间的浪费。
6.覆盖技术
覆盖技术是指一个程序的若干程序段或几个程序段的某个部分共享一个存储空间。覆盖技术的实现是把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构是那些不会同时执行的程序共享一块内存区域。未执行的程序段先保存在磁盘上，当有关程序段的前一部分执行结束后，把后续程序段写入内存，覆盖前面的程序段。
7.交换技术
交换技术是指把主存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，把已具备运行条件的进程，或进程所需要的程序或数据换入到主存的技术。
1）换出进程的选择
2）交换时机的确定
3）交换空间的分配
4）换入进程换回内存时位置的确定
8.页式存储管理
在页式存储管理方式中，将用户作业的地址空间分成若干大小相同的区域，称为页面或页，并为每个页从“0”开始编号。
相应地，主存空间也分为与页大小相同的若干存储块，成为物理块或页框，并且采用同样的方式为它们进行编号，从0开始：0块，1块，...，n-1块。
程序的逻辑地址页号和页内地址组成，页号的长度决定了分页的多少，页内地址的长度决定了页面的大小。在为作业分配主存时，以块为单位将作业中的若干页分别装入到多个不相邻的块中。作业执行时根据逻辑地址中的页号找到它所在的块号，再确定当前指令要访问的物理地址。它的地址转换属于动态重定位，由于进程的最后一页经常装不满一块，而形成不可利用的碎片，称为“页内碎片”。
8.1主存空间的分配与回收
1)采用的数据结构
为了实现页式存储管理方式，系统设置了主存分配表、位示图和页表，记录主存空间的使用情况和每个作业的分配情况。
2）主存空间的回收
当一个作业执行结束，则应收回该作业所占用的主存块。根据主存分配表中的记录，取出该作业的页表。从该作业的页表中取出每一个归还的块号，计算出该块在位示图中的位置，将占用标志位置“0”。最后，把归还的块数加入到空闲块数中，删除该作业的页表，并把分区分配表中该作业的记录删除。
9.地址转换和快表
9.1地址转换。两个与地址计算有关的方法。
一是，由逻辑地址计算出页号和页内地址的计算方法如下：
页号=逻辑地址/页长（商）
页内地址=逻辑地址 % 页长（余数）
二是，由块号计算物理地址的计算方法为：
物理地址=块号*块长+块内地址+用户区基址
页表：
1）多级页表
2）散列页表
3）反置页表
页式管理特点：
1）有效地解决了“碎片”多的问题。可以使程序和数据存放在不连续的主存空间，而不必像可变分区管理那样通过增加系统开销来解决主存碎片的问题。
2）通过位示图和页表来记录主存的使用情况和每个作业的分配情况，当主存很大，并且作业也很大时，位示图和页表都有可能占用较大的存储空间。另外，它要求有相应的硬件支持，从而增加了系统成本，也增加了系统开销。例如需要地址变换机构、快表等。
3）要求页的大小固定。
9.2快表
因页表在主存中，CPU在存取数据时，要访问主存两次。第一次是访问主存中的页表，从中找出该页的物理块号，将此块号与页内地址拼接形成物理地址，第二次是根据上一步得到的物理地址，到主存中获取数据。这样就降低了计算机的处理速度。为了提高处理速度，可以使用快表和两级页表的方法对页式存储管理进行改进。
具有快表的地址变换
具有两级页表的地址转换
10.虚拟存储管理方式
虚拟存储器的定义
虚拟存储器是指仅把作业的一部分装入主存便可以运行的存储器系统。
虚拟存储器的逻辑容量也称为最大容量，是由地址寄存器的位数决定的。如果计算机的地址寄存器是24位，地址按单字节编址，则虚拟存储器的最大（逻辑）熔炼容量是224B。
虚拟存储器的物理容量也称为实际容量。当最大容量大于等于主存与硬盘容量之和时，虚拟存储器实际容量为主存与硬盘容量之和；当最大值小于主存与硬盘容量之和时，虚拟存储器实际容量就是最大容量。虚拟存储器的运行速度接近于主存速度，而其成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛的应用于各类计算机中。
10.1页式虚拟存储管理基本原理
页式虚拟存储管理是建立在纯分页基础上的，增加了请求调页功能和页面置换功能所形成的页式虚拟存储管理系统。他把作业分成大小相等的若干页，把主存分成与页大小相等的若干块；对每个作业限定分给它的主存块数，先把作业的部分页装入主存的这些块中，在作业运行时再装入所需要的页。
10.2采用的数据结构
虚拟存储器在实现上是有一定难度的，既需要一定的硬件支持，又需要较多的软件支持，但是，请求分页式存储管理方式相对容易，因为它换进、换出的基本单位是固定长度的页面。采用的数据结构如下：位示图、页表和主存分配表。
10.3页面调度策略：
调入策略
1）请求调页
2）预调页
置页策略
置换策略
1）固定分配局部置换
2）可变分配全局置换
3）可变分配全局置换
10.4页面置换算法
1）先进先出置换算法（FIFO）
该算法淘汰最早进入主存的页面。因为，最早进入的页面，不再使用的可能性比最近调入的页面要大。先进先出置换算法实现简单，只要把各调入主存的页按其进入主存的先后顺序连成一个队列即可，总是淘汰队首的那一页。
2）最近最久未使用算法（LRU）
该算法选择在最近一段时间内最久没有使用过的页淘汰掉。它依据的是程序局部性原理。最近最久未使用算法是利用一个特殊的栈来保存当前使用的各个页的页号。每当访问某页时，考察栈内是否有于此相同的页号，若有则将该页的页号从栈中抽出，再将它压入栈顶。
3）最近最不经常使用算法（LFU）
该算法选择到当前时间为止被访问次数最少的页置换。其实现方法是为每页设置一个访问计数器，每当页面被访问时，该页面的访问计数器就加“1”；发生缺页时，淘汰计数器淘汰值最小的页，同时将所有计数器清“0”。
4）理想页面置换算法
从主存中溢出永远不需要的页。若无这样的页，则移出最长时间不需要访问的页。该算法只有理论意义。
5）最近未使用页面置换算法（NRU）
第0类：没有被访问，没有被修改
第1类：没有被访问，已被修改
第2类：已被访问，没有被修改
第3类：已被访问，已被修改
6）第二次机会页面置换算法
7）时钟页面置换算法
缺页中断率
缺页中断率=中断次数/页面访问总次数
影响缺页中断的因素：
1>分配给程序的内存块数
2>页面的大小
3>程序编制方法
4>页面置换算法
11.段式存储管理方式
基本原理
在段式存储管理方式中，作业的地址空间被划分为若干段，每段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D及栈段S等。每个段都有自己的名字。为了实现简单，通常可用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。
整个作业的逻辑地址空间，由于分成多个段，因而是二维的，即其逻辑地址由段号和段内地址所组成。
12.段页式存储管理方式
基本原理
段页式存储管理方式的基本原理是段式和页式系统工作原理的组合，即先把用户程序分成若干段，并为每个段划分成大小相等的若干页，把主存分成与页大小相同的块。每段分配与其页数相同的主存块，主存块可以连续，也可以不连续。
第六章 文件管理
考试内容
1.文件的基本概念、文件逻辑结构、文件的物理结构和存取方式
2.文件目录的基本概念，文件目录的实现
3.文件的操作，目的操作
4.磁盘空间的管理
5.文件系统的可靠性和安全性
6.文件系统的性能问题
7.Windows的文件系统FAT，UNIX的文件系统
1.什么是文件？
文件是指存放在外存上的已命名的一组相关信息的集合，通常将程序和数据组织成文件。
文件中的基本访问单位是位、字节或记录。
文件的属性包括文件类型、文件长度、文件的物理位置、文件的存取控制、文件的建立时间。
文件是一种抽象机制，它提供了一种把信息保存在存储介质上而且便于以后存取的方法，用户不用关心文件的实现细节。
2.文件系统的概念
操作系统中与文件和目录相关的子系统统称为文件系统能够，是操作系统中统一管理信息资源的一种软件。
信息的存储要求：
1）能够存储大量的信息
2）长期保存信息
3）可以共享信息
操作系统为系统管理者提供了对文件的透明存取。
研究文件系统的两种角度：
1）用户的角度
主要关心文件由上面组成，如何命名，如何保护，如何操作等
2）操作系统的角度
主要关心文件目录怎样实现，怎样管理存储空间，文件存储位置，磁盘实际运作方式等
文件的分类
1）按文件的用途分类：
系统文件：操作系统和各种应用程序和数据所组成的文件。
库函数文件：标准子程序及常用应用程序组成文件
用户文件：用户委托文件系统保存的文件
2）按文件的阻值形式分类：
普通文件：文件的组织格式为文件系统中所规定的最一般格式的文件
目录文件：由文件的目录构成的特殊文件
特殊文件：形式上与普通文件相同，也可以进行查找目录操作，但有其特殊的性质，比如，UNIX系统中，输入输出设备被看作是特殊文件。
3）按文件中的保护方式分类：只读文件、读写文件、可执行文件、无保护文件等。
4）按信息的流向分类：输入文件、输出文件和输入输出文件等
5）按文件的存放时限分类：临时文件、永久文件和档案文件等
6）按文件使用的介质类型分类：磁盘文件、磁带文件、卡片文件和打印文件等
7）按照文件的组织结构分类：
逻辑文件：流式文件和记录文件等
物理结构：顺序文件、链接文件和索引文件等
UNIX操作系统中的文件分类：
1.普通文件
2.目录文件
3.特殊文件
目的：对不同的文件进行管理，提高系统效率，同时提高文件系统的用户界面友好性
文件系统的功能
1）统一管理文件的存储空间，实施存储空间的分配和回收
2）实现文件的按名存取
3）实现文件信息的共享，并提供文件的保护和保密措施
4）向用户提供一个方便使用的接口
5）系统维护及向用户提供有关信息
6）保持文件系统的执行效率
7）提供与I/O的统一接口
3.文件的结构
1）文件逻辑结构的概念
文件的逻辑结构是用户组织文件时可见的结构，即用户所观察到的文件组织形式。文件的逻辑结构是用户的文件组织形式。文件的逻辑结构是用户可以直接处理的数据及其结构，它独立于物理特性，又称为文件组织。
选择文件的逻辑结构主要有一下原则：
1>查找快捷。根据给定的逻辑结构，应使文件系统在尽可能短的时间内找到所需要的记录或基本信息单位。
2>修改方便。便于在文件中增加、删除和修改一条或多条记录。
3>空间紧凑。应使文件的信息占据尽可能小的存储空间。
4>易于操作。
2）文件逻辑结构的形式
文件的逻辑结构从形式上分为两类：有结构的记录式文件和无结构的流式文件
流式文件：文件中的数据是一串字符，没有结构
记录文件：由若干逻辑记录组成，每条逻辑记录又由相同的数据项组成
记录式文件可分为定长记录文件和不定长记录文件。
4.文件物理结构的概念
1）文件物理结构的概念
文件的物理结构，又称为文件的存储结构，它是指文件在外存上存储时的组织结构。文件的物理结构与存储介质的物理特性及用户对文件的访问方式有关。
文件的物理结构通常划分为大小相等的物理块。这些物理块也称为物理记录，它是文件分配及传输信息的基本单位。物理记录的大小与物理设备有关，与逻辑记录的大小无关。
2）文件物理结构的形式
根据文件存储设备的特征以及用户对文件的访问方式，可以在文件存储器中使用以下三种：
1>顺序结构。顺序结构是很简单的一种物理结构。顺序结构将一个在逻辑上连续的文件信息一次存放在外存连续的物理块中，即所谓的逻辑上的连续，物理上也连续。
顺序结构的特点：
一旦知道文件在存储设备上的其实块号和文件长度，能快速进行存取
顺序结构支持顺序存取和随机存取
顺序结构的缺点：
文件不能动态增长
文件分配内存空间比较慢
容易产生存储碎片
2>链接结构。克服顺序文件缺点的办法之一是采用链接结构。链接结构将文件存放在外存的若干个物理块中，这些物理块不必连续，并且在每一个物理块中设一个指针，指向下一个物理块的位置，从而使得存放在同一个文件的物理块链接起来。
windows的FAT文件系统采用的就是链接结构。
链接结构的优点：
存储碎片问题解决
有利于文件动态扩充，有利于文件插入、删除
提高磁盘利用率
链接结构缺点：
存取速度慢
不适合随机存取文件
磁盘磁头移动多，效率比较低
存放文件的可靠性较差
链接指针需要额外的空间
3>索引结构。索引文件克服了顺序文件和链接文件的缺点。索引结构将文件存放在外存的若干个物理块中，并将
索引文件的优点：
保持了链接结构的优点，又解决了其缺点。
索引文件既适合于顺序存储，也适合于随机存储。
索引文件缺点：
会引起较多的寻道次数和寻道时间，索引表增加存储空间的开销。
索引文件结构对空间占用比较严重，索引表是定长还是不定长，解决问题如下：
1）索引表的链接模式。这种模式存取文件需要读所有的索引表，对于大文件需要读很多块。
2）多级索引
4>索引结构的实例——I节点
I节点是一种多级索引结构，最早出现在UNIX系统中。I节点在一般多级索引结构文件基础上，进行了结构的变化。
I节点的思想，是给每个文件赋予一张成为I节点的小表，这张小表列出了文件属性和文件中个这块在磁盘上的地址。
5.文件的存储介质，主要是文件的外存储设备
5.1顺序存储设备
顺序存储设备是按信息的物理位置进行定位和读/写操作的存储设备。在顺序存储设备中，只有前面的物理块被存取之后，才能存取其后的物理块。
磁带的存储特性如下：
1）磁带是一种顺序存取的存储设备，总是从磁头的当前位置开始读写
2）磁带上的块不由地址来标识，而由其在次带上的位置来识别
3）块与块之间有间隙，磁带上的物理块就是通过间隙来区分的
4）磁带的存取速度与信息密度、磁带带速和块间间隙有关。如果带速高，信息密度大，且所需块间隙小，则磁带存取速度高。
5）磁带的容量大，采用顺序存取方式时存取速度高，采用随机存取方式效率较低
5.2随机存储设备
允许文件系统直接存取对应存储介质上的任意物理块的存储设备。如磁盘就是典型的随机存储设备。
与磁盘有关的概念
1）磁道。磁盘盘片上的一系列同心圆成为磁道；为了描述磁道，对磁道由外向内进行编号，成为磁道号（编号均从0开始）。即系统通过磁道号完成对磁道的操作。
2）柱面。与盘片中心有相同距离的所有磁道组成一个柱面；当磁臂移动到某一位置时，所有的读写磁头 都在同一个柱面上，盘面上的磁道号即为柱面号；对于软盘，一个柱面仅包含两个磁道。
3）扇区。磁道沿径向又分成大小相等的若干区域，每个区域成为一个扇区，每个扇区可以存放相等字节数（一般为512字节）的信息，按照与磁盘旋转相反的方向依次给扇区编号，成为扇区号。
4）磁头号。所有的读写磁头由上至下进行编号成为磁头号。
磁盘空间的位置由三个因素决定：柱面号、磁头号、扇区号。
访问磁盘的时间由三部分组成，即寻道时间、延迟时间和传输时间。其中寻道时间是指将磁头从当前位置移动到指定磁道所经历的时间，也称为移臂时间；延迟时间是通过磁盘的旋转将所指定扇区移动到磁头下面的时间，也称为旋转时间；传输时间是指将扇区上的数据从磁盘读出或向磁盘写入数据所经历的时间。
磁盘每个物理块的位置可用柱面号、磁头号和扇区号表示：
1）已知物理块号，则磁盘地址：
柱面号=[物理块号/(磁头数*扇区数)]
磁头号=[(物理块号%(磁头数*扇区数))/扇区数]
扇区号=[(物理块号%(磁头数*扇区数))%扇区数]
2）已知磁盘地址：
物理块号=柱面号*(磁头数*扇区数)+磁头数*扇区数+扇区号
6.文件的存取方式
随机存取方式
随机（直接）存取方式
文件目录
是指存放文件有关信息的一种数据结构。它包含多条记录，每条记录为一个文件的文件控制块（FCB）的有关信息。最简单的记录包含文件名和文件的其实地址，用以建立文件名和存储地址的对应关系。较复杂的记录包含文件控制块的全部内容，此时，文件目录就是文件控制块的集合。
文件目录是文件实现按名存取的重要手段，是文件符号到文件物理地址之间的一种映射机制。
目录项：构成文件目录的项目（目录项即使FCB）
目录文件：用户新建一个文件时，与文件有关的信息在该文件的文件控制块内，多个文件的文件控制块一起组成了文件的目录。为了实现对文件目录的管理通常将文件目录以文件的形式保存在外存。
文件目录的管理形式可以分为一级目录、二级目录、多级目录三种。
一级目录，也称为单级目录，是一种最简单、最原始的目录结构。它采用的方法是为外存的全部文件建立一张目录表。表中包括全部文件的文件名、索引表的始址以及文件的其他属性，如文件长度、文件类型等。每个文件占据表中的一条记录。该目录表存放在外存的某个固定区域，需要时系统将其全部或部分导入主存。
一级目录的特点：
1）目录结构易于实现，管理简单，只需要建立一个文件目录，对文件的所有操作，都是通过该文件目录实现的。
2）易发生重名问题
3）当文件较多时，查找时间较长
4）不便于实现文件共享，适用于PC机的单用户系统
为了克服单级目录结构所存在的缺点，可以把单级目录扩充为二级目录。
在二级目录中，有主文件目录和用户文件目录。在主文件目录中，每个用户文件目录都占有一个目录项，其中包括用户名和指向该用户目录文件的指针。用户文件的文件说明组成的目录文件成为用户文件目录，不同的用户拥有不同的用户文件目录，这些文件目录具有相似的结构，由用户所有文件的文件控制块组成。
二级目录的特点：
1）提高了检索目录的速度
2）可以解决用户文件重名问题
3）可以使不同用户共享同一个文件
4）可以实现对文件的保护和保密
5）二级文件目录虽然解决了不同用户之间文件同名的问题，但是，同一用户的文件不能同名。当一个用户的文件很多时，这个矛盾就比较突出了。
为了解决用户文件同名的问题，可以把二级目录的层次关系加以推广，就形成了树型目录。
在二级目录结构中，如果进一步允许用户创建自己的子目录并相应地组织自己的文件，即可以形成三级目录结构，依次类推，还可以进一步形成多级目录。通常把三级或三级以上的目录结构成为树型目录结构。
在树型目录结构中，除了最低一级外，其他每一级存放的都是下一级目录或文件的说明信息，最高层为根目录，最底层为文件。UNIX和DOS系统中都采用了树型目录结构。
树型目录的特点：
1）层次清楚：不同性、不同用户的文件可以构成不同的子树，便于管理；不同用户的文件可以被赋予不同的权限，有利于文件的保护。
2）解决了用户文件重名问题：只要在同一目录下的文件名不发生重复，就不会由文件重名引起混乱。
3）搜索速度快：可为每类文件建立一个子目录，对于多级目录，每次只查找子目录，因此速度比一级和二级目录时快。
用户在访问文件时，需要进行目录检索，用户给出文件名，系统按名寻找目录项。
有两种根据路径检索的方法：全路径名和相对路径。
全路径名：需要从根目录开始，列出由根到用户的所有子目录，又称为“绝对路径名”。
缺点：每次都从根目录开始检索，很不方便，因为通常目录放在外存故影响访问速度，尤其当目录层次较多时，检索需要耗费很长时间。
相对路径：用于检索的路径只是从当前目录开始到所要访问文件的一段路径，即以当前目录作为路径的相对参照点。这样检索速度比较快。
文件寻址：根据FCB中文件物理地址等信息，求出文件的任意记录或字符在存取介质上的地址，称为文件寻址。
文件目录改进
为加快目录检索可采用目录项分解法：把FCB分成两部分：
符号目录项（次部）
文件名，文件号
基本目录项（主部）
除文件名外的所有项目
分解之后的查找过程：
查找一个目录项就分成两步：首先访问符号目录文件，根据文件名查找相应的文件内部号；然后访问基本目录文件，根据文件内部号，可直接计算出相应基本目录项所在基本目录文件中的相对位置和物理位置，并将它直接读入内存。
目录操作：
以UNIX为例：
1.Creat
2.Delete
3.Opendir
4.Closedir
7.存储空间的分配和回收
1）位图法
用一串二进制位反应磁盘空间中分配使用情况，每个物理块对应一位，分配物理块为1，否则为9
申请物理块时，可以在位示图中查找为0的位，返回对应物理块号
归还时，将对应位转置0
描述能力强，适合各种物理结构
计算公式：
已知字号i，位号j
块号=i*字长+j
已知块号：
字号=[块号/字长]
位号=块号%字长
2）空闲块表
将所有空闲块记录在一个表中，即空闲块表特别适合文件物理结构为顺序结构的文件系统
3）空闲块链表
把所有空闲块链成一个链
4）成组链接法
文件系统的实现
内存中多需的表目
1）系统打开文件表（整个系统一张）
放在内存。用于保存已打开文件的FCB
此外，文件号，共享计数，修改标志
2）用户打开文件表（每个进程一个）
文件描述符，打开方式，读写指针，系统打开文件进程的PCB中，记录了用户打开文件表的位置
3）用户打开文件表与系统打开文件表之间的关系
用户打开文件表指向系统打开文件表
如果多个进程共享同一个文件，则多个用户打开文件表目对用系统打开文件表的同一入口
8.记录
记录是一组相关数据项的集合，用于描述数据对象某方面的属性。它是文件中数据处理的基本单位，是组成文件的基本元素。
在一个由大量记录组成的文件中，为了能惟一地标识一条记录，可以在记录的各个数据项中，确定出一个或几个数据项，把它（或它们）成为关键字（key）。如在描述学生的数据项中，学号可以作为关键字。
记录的成组和分解
每个用户的文件是由用户按照自己的需要组织的，逻辑记录的大小是由文件的性质决定的。而存储介质上的分块是根据存储介质的特性划分的。所以，逻辑记录的大小往往与存储块的大小不一致。为了节省存储空间，提高主存的利用率，系统引入了记录的成组和分解。
记录成组
记录成组是指把若干条逻辑记录合并成一组存入一个物理块的过程。
记录分解是指从一条物理记录中把逻辑记录分离出来的过程。
记录成组存放后，当用户需要某一条记录时，必须把含有该条记录的整块信息独处，再从这一组逻辑记录中找出用户所需要的记录进行处理。记录分解也需要使用主存缓冲区。
9.文件的操作
提供设置和修改对用户文件存取权限
提供建立、修改、改变、删除目录的服务
提供文件共享，设置访问路径的服务
提供创建、打开、读、写、关闭、撤销文件等服务
文件系统维护
文件系统的转储和恢复
10.文件的保护
文件的共享
1）定义
一个文件被多个用户或程序使用
共享形式：
被多个用户使用，由存取权限控制
被多个程序使用，但各用自己的读写指针
被多个程序使用，但共享读写指针
2）目的
节省时间和存储空间，减少了用户工作量；
进程间通过文件交换信息
文件安全是指避免合法用户有意或无意的错误操作破坏文件，或非法用户访问文件。
影响文件安全性的主要因素有：
1）认为因素
2）系统因素
3）自然因素
为了确保文件系统的安全性，可以采取以下措施：
1）建立副本，通过“后备系统”来防止由自然因素所造成的不安全性
2）定时转储，通过系统容错技术来防止系统部分的故障所造成的文件不安全性
3）规定文件的存取权限，通过存取控制机制来防止由人为因素引起的文件不安全性
特点：建立副本的方法简单，但是系统开销大，且文件更新时，所有副本都必须更新。这种方法使用容量较小且极为重要的文件。定时转储的方法简单，但是较为费时，在转储过程中一般要停止文件系统的使用。这种方法适用于容量较大的文件。
文件的使用权限可以设为：只能读、可读可写、只能执行、不能删除等。对多用户共享的文件采用属性、目录结构，反得到某级目录权限的用户就可以得到该目录所属的全部目录和文件。
11.文件的存取权限
1）存取控制矩阵：系统以一个二维矩阵来实施文件的存取控制。其方法在概念上比较简单。
2）二级存取控制：两个存取级别。第一级，把用户按照某种关系分为若干组，进行对访问者的识别，第二级，进行对操作权限的识别。
UNIX中的文件存取权限：
第一级：对访问者的识别
对用户分类：
文件主（owner）
文件主的同组用户（group）
其它用户（other）
第二级：对操作权限的识别
对操作分类：
读操作（r）
写操作（w）
执行操作（x）
不能执行任何操作（-）
文件属性rwxr--xr--x用二进制表示是111101101，在UNIX中使用八进制，因此权限是755
12.文件保密
文件保密是指文件本身不得不被未授权的用户访问，防止他人窃取文件。实现文件保密采用的方法有：
1）隐藏文件目录
2）设置口令
3）使用密码
13.文件系统的优化
文件系统的物理基础是磁盘设备
常见的技术措施：
1）块高速缓存
2）合理分配磁盘空间
3）磁盘的驱动调度
4）信息的优化分布
5）RAID技术
1>块高速缓存
系统在内存中保存一些块。逻辑上它们属于磁盘
2>合理分配磁盘空间
3>磁盘的驱动调度
公平：一个I/O请求在有限时间内满足
高效：减少设备机械运动所带来的时间浪费
磁盘调度考虑的问题：
一次访盘时间=寻道时间+旋转延迟时间+传输时间
磁盘驱动调度由“移臂调度”和“旋转调度”组成
移臂调度目的是尽可能减少寻找磁道时间
旋转调度目的是尽可能减少寻找扇区时间
磁盘调度算法：
1）先来先服务（FCFS）：
按访问请求到达的先后次序服务
优点：简单，公平
缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利
2）最短寻道时间优先（SSTF）：
优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先
特点：该调度算法，虽然减少了磁臂的移动距离，但是，会经常改变磁臂的移动方向，花费时间多又影响机械部件，还会导致“饥饿”现象，即较远距离的鼓励的访问者可能很长时间不能获得访问磁盘的机会。
3）扫描算法（SCAN电梯算法）：
克服了最短寻道有限的缺点，考虑了距离和方向
4）循环扫描（C-SCAN）调度算法：
在扫描算法的基础上改进的。balabala...
4>旋转调度算法
旋转调度：根据延迟时间来决定执行次序的调度
5>信息的优化分布
记录在磁道上的排列方式也会影响磁盘的输入输出时间
6>RAID技术
磁盘时机械设备，一方面速度慢，一方面也容易出现故障。
RAID是一种把多块独立的硬盘（物理硬盘）按不同的方式组合起来形成一个硬盘组（逻辑硬盘），从而提供比单个硬盘更高的存储性能和提供数据备份技术。
Windows的FAT文件系统
FAT文件系统是各种Windows操作系统都支持的一个简单的文件系统
FAT文件系统一簇为单位进行分配
FAT有三个版本：FAT-12，FAT-16，FAT-32
FAT卷的结构包括：引导扇区、文件分配表、根目录
UNIX文件系统
UNIX目录中为每个文件保留了一项，每个目录项包含了两个域，文件名和节点号。
UNIX普通文件的物理结构是三级索引结构
第七章 I/O设备管理
考试内容
1.设备与设备分类
2.I/O硬件组成
3.I/O软件的特点及结构
4.典型技术：通道技术，缓冲技术，SPOOLing
5.I/O性能问题及解决方案
1.设备与设备的分类
按设备的使用特性分类
1）存储设备。存储设备是指用来存放信息的设备，如磁盘、磁带等。
2）I/O（输入输出）设备
按设备共享属性分类
1）独占设备。独占设备是指在一段时间内只允许一个进程访问的设备。系统一旦把这种设备分配给一个进程后，便由该进程独占，直到用完释放，其他进程才能使用。多数低速设备都属于此类设备，如打印机。
2）共享设备。共享设备是指在一段时间内允许多个进程访问的设备，如磁盘。
3）虚拟设备。虚拟设备是指通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个进程同时使用的设备，如虚拟打印机。
按设备的信息组织方式来分类
1）块设备。块设备是指处理信息的基本单位是字符块。一般块的大小为512B~4KB，如磁盘、磁带等。
2）字符设备。字符设备是指处理信息的基本单位是字符，如键盘、显示器、打印机等。
2.I/O硬件组成
2.1计算机的I/O系统结构
从硬件的角度来看，一个典型的计算机结构，中央部分是CPU和主存，通过总线与第二层的接口部分连接，第三层各种外围设备控制器，最外层是外围设备。
2.2I/O设备数据传输控制方式
程序直接控制方式
程序直接控制方式也称为“忙——等待”方式，即在一个设备的操作没有完成时，控制程序一直检测设备的状态，直到该操作完成，才能进行下一个操作。
步骤为：
1）当用户需要输入数据时，由处理器向设备控制器发出一条输入输出指令，启动设备进行输入。
2）当用户进程需要像设备输出数据时，也必须发出启动命令启动设备输出，并等待输出操作完成。
特点：工作过程简单，CPU的利用率低。直接控制方式适用于早期的无中断的计算机系统。
程序中断控制方式
中断控制是指计算机在执行期间，系统内发生任何给寻常的或非预期的急需处理事件，使得CPU暂时中止当前执行的程序而转去执行相应的时间处理程序，待处理完毕后又返回原来被中止处继续执行或调度新的进程。
特点：中断控制方式比程序直接控制方式提高了CPU的利用率。每输入一个数据都会发生中断，传输一组数据需要多次中断，浪费了CPU的时间。中断控制方式应用与现代计算机系统中。
直接存储器存取控制方式（DMA）
直接存储器存取方式是指对输入输出设备的控制由DMA控制器完成，在DMA控制器的作用下，设备和主存之间可以成批地进行数交换，而不用CPU的干涉。
特点：数据的传送方向、存放数据的主存始址及传送数据的长度等都由CPU控制，具体的数据传送由DMA控制器负责，每台设备需要配一个DMA控制器，这样输入输出传输速度快，CPU负担少。直接存储器存取控制方式适用于块设备的数据传输。
通信控制方式
I/O通信是一种特殊的处理机
具有执行I/O指令的能力
具有执行通道（I/O）程序控制I/O操作
指令类型单一，主要限于I/O操作有关的指令
没有自己的内存，通道程序放在主机内存中
特点：通道所需要的CPU干预更少，并可以实现CPU、通道和输入输出设备三者之间的并行操作，从而更有效地提高整个系统资源的利用率。通道控制方式适用于现代计算机系统中的大量数据交换。
2.3输入输出通道的分类
输入输出通道是用于控制外围设备的。根据信息交换方式的不同，把通道分成三种类型：
1）选择通道。可以连接多台高速设备，由于它只含有一个分配型子通道，在一段时间内只能执行一个通道程序，控制一台设备进行数据传送，致使当某台设备占用了该通道后，便一直由它独占，直至该设备传送完毕后释放该通道。
数据选择通道虽然有很高的传输速率，但它每次只允许一个设备传输设备，这种通道利用率很低。
2）字节多路通道。通常都含有许多非分配型子通道，其数量可以从几十到数百个，每一个子通道连接一台输入输出设备，这些子通道按时间片轮转方式共享主通道。
字节多路通道连接低速或中速设备时，不会丢失信息。
3）数组多路通道。将数据选择通道传输速率高和字节多路通道能使各子通道（设备）分时并行操作的优点相结合，而形成的一种新通道。它含有多个非分配子通道，因而这种通道既具有很高的数据传输速率，又能获得令人满意的通道利用率。
该通道被广泛地用于连接多台高、中速的外围设备，其数据传送是按数组方式进行的。
3.I/O软件的特点及结构
设计I/O最关键的目标是设备独立性。
I/O设备管理软件的结构，基本思想是分层构造，使底层与硬件相关，把硬件与较高层次的软件隔离。
I/O软件分为四层：
中断处理程序
设备驱动程序
与设备无关的系统软件
用户空间的I/O软件
设备驱动程序的功能
balabala...
设计I/O最关键的目标是设备独立性。
I/O设备管理软件的结构，基本思想是分层构造，使底层与硬件相关，把硬件与较高层次的软件隔离。
I/O软件分为四层：
中断处理程序
设备驱动程序
与设备无关的系统软件
用户空间的I/O软件
设备驱动程序的特点：
1）驱动程序主要是在请求输入输出的进程与设备控制器之间的一个通信程序。
2）驱动程序与输入输出设备的特性密切相关
3）驱动程序与输入输出控制方式紧密相关
4）驱动程序与硬件紧密相关，其部分被固化在ROM中
与设备无关的系统软件
除了一些I/O软件与设备相关外，大部分软件是与设备无关的。一般情况，所有设备都需要的I/O功能可以在于设备独立的软件中实现。
设备无关软件层实现的一些功能：
统一命名
设备保护
提供与设备无关的逻辑块
缓冲
存储设备的块分配
独占设备的分配与释放
出错处理
用户空间的I/O软件
大部分I/O软件都包含在操作系统中，但是用户程序可以和库函数连接在一起
标准的I/O库包含了许多设计I/O的过程，他们都是作为用户程序的一部分运行的
4.缓冲技术
为了提高输入输出设备的速度和利用率，在输入输出设备与处理器交换数据时引入了缓冲技术。缓冲技术是输入输出设备在与主存交换数据时使用缓冲区的技术。缓冲管理的主要功能是组织好缓冲区，并提供获得和释放缓冲区的手段。
4.1缓冲的引入
1）缓和CPU与输入输出设备间速度不匹配的矛盾
2）减少对CPU的中断频率，放款对中断响应时间的限制
3）提高CPU与输入输出设备间的并行性
4.2单缓冲
单缓冲是指在设备和处理器之间设置一个缓冲区，用于数据的传输
4.3双缓冲
双缓冲是指在设备和处理器之间设置两个缓冲区
4.4多缓冲
在设备和处理器之间设置多个缓冲区
4.5缓冲池
当系统较大时，可以利用多个进程共享的缓冲池来提高缓冲区的利用率
5.I/O性能问题及解决方案小结
I/O性能常常成为系统性能的瓶颈，因此提高I/O性能十分重要
1）通过缓冲技术，减少或缓解不同设备之间传输速度的差距
2）通过异步I/O技术，使CPU计算不必等待I/O操作结果
3）通过应用DMA和通信部件，使CPU摆脱I/O操作，与这些部件并行执行
4）通过虚拟设备技术，提高独占设备的利用率
第八章 死锁
活锁概念
数据资源释放时间不确定，导致某些事务长时间等待，得不到封锁的机会
饥饿的概念
系统没有发生死锁，但某些进程可能会长时间等待，当等待时间给进程推进和响应带来明显影响时，称进程饥饿
死锁的原因
1）竞争资源
2）进程推进顺序不合理
产生死锁的必要条件
死锁并不一定都会出现，如果一旦产生死锁，一定会满足下述4个必要条件
1）互斥条件
2）不剥夺条件
3）请求和保护条件
4）循环等待条件
解决死锁的方法分为四种
1）预防死锁。
预防死锁是在进行资源分配之前，通过设置某些资源分配的限制条件，来破坏产生死锁的四个必要条件的一个或几个。预防死锁是一种较简单的方法，容易使用，但是，由于施加了限制条件，会导致系统资源利用率和吞吐量的下降。
2）避免死锁。
避免死锁是在资源分配前不设置限制条件，在进行资源分配的过程中，用某种方法对每次资源分配进行管理，以避免某次分配使系统进入不安全状态，以致产生死锁。这种方法限制较小，可以获得较好的系统资源利用率和吞吐量。目前比较完善的系统中，通常采用此种方法。
3）检测死锁
允许系统产生死锁，但在系统中设置检测机构，一旦发生死锁，采取措施解除死锁
4）解除死锁
通过撤销或挂起一些死锁中的进程，回收相应的资源，进行资源的再次分配，从而将进程死锁状态解除。这种方法没有限制，可以获得较好的系统资源利用率
死锁的预防
通过对资源分配的原则进行限制，而使产生死锁的四个必要条件中的1个或多个条件不能成立，来预防产生死锁。
破坏“互斥条件”条件
进制进程独占资源，如果资源不被一个进程独占，你们死锁肯定不会发生
此条件实现比较困难，限制比较多
破坏“不剥夺”条件
一个已经占有某些资源的进程，当它再提出新的资源需求而不能立即得到满足时，必须释放它已经占有的所有资源，待以后需要时再重新申请。这意味着进程已经拥有的资源，在运行过程中可能会暂时被迫释放，即被系统剥夺，从而摒弃了“不剥夺条件”
这种预防死锁的方法，实现起来比较复杂，并付出较大的代价，会使前段时间的工作实效等。此外这种方法还会因为反复地申请和释放资源，延长进程的周转时间，增加系统开销，降低系统吞吐量。
破坏“请求和保持”条件
系统要求进程必须一次性地申请其在整个运行期间所需要的全部资源。若系统有足够的资源，便一次性将其所需要的所有资源分配给该进程，这样一来，该进程在整个运行过程中，便不会再提出资源请求，从而摒弃了“请求”条件。而在分配时，只要有一个资源要求不能满足，系统将不分配给该进程任何资源，此时进程没有占有任何资源，因而也摒弃了“保持”条件，所以，可以预防死锁的产生。
这种预防死锁的方法，简答方便、易于实现，但是，因为进程将一次性获得所有资源，并且独占使用，其中可能有些资源在该进程运行期间很少使用，造成资源严重浪费；同时有些进程因不能一次性获得所需要的资源，导致长时间不能投入运行。
破坏“循环等待”条件
在这种方法中规定，系统将所有的资源按照类型进行线性排序，赋予不同的资源序号。并且所有进程对资源的请求和分配必须严格的按照资源序号有小到大地进行，即只有先申请和分配到序号小的资源，才能申请和分配序号大的资源。这样在最后形成的资源分配图中，将不可能再出现环路，从而摒弃了“环路等待”条件。
这种预防死锁的方法与前两种相比，其资源利用率和系统吞吐量，都有明显的改善。但是，这种方法涉及对各类资源的排序编号，考虑到实际的使用，其排序的合理性将受到很大的挑战。
破坏“循环等待”条件
在这种方法中规定，系统将所有的资源按照类型进行线性排序，赋予不同的资源序号。并且所有进程对资源的请求和分配必须严格的按照资源序号有小到大地进行，即只有先申请和分配到序号小的资源，才能再申请和分配序号大的资源。这样在最后形成的资源分配图中，将不可能再出现环路，从而摒弃了“环路等待”条件。
死锁的避免
在死锁的避免中，所施加的限制较弱，可以获得较好的系统性能。该方法的系统状态分为安全状态和不安全状态，只要能使系统时钟处于安全状态，便可以避免死锁发生。
安全状态和不安全状态
安全状态是指系统能够按照某种顺序为每个进程分配搜需要资源，直到最大需求，使每一个进程都可以顺利完成。反之，如果系统不存在这样的一个安全序列，则称系统处于不安全状态。
当系统进入不安全状态后，很有可能进入死锁状态；反之，只要系统处于安全状态，便可避免进入死锁状态。因此，避免死锁的实质就是如何是系统不进入不安全状态。
利用银行家算法避免死锁
最具代表性的避免死锁的算法是Dijkstra和Habermann的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。
死锁的检测与接触
当系统为进程分配资源时，如果没有采取任何限制措施，系统必须提供死锁的检测与解除机制
死锁的检测
在进行死锁的检测时，系统必须能保存有关资源的请求和分配的信息，并提供一种算法，以便利用这些信息来检测系统是否进入死锁状态。
死锁的解除
当检测到系统发生死锁时，就必须立即把死锁状态解除，常用的方法是：
1）剥夺资源法。从其他进程剥夺足够数量的资源给死锁进程，使其得到足够的资源，然后继续执行，以解除死锁状态。
2）撤销进程法。系统采用强制手段将死锁进程撤销。最简单的方法是将全部死锁进程一次性撤销，但是，代价较大；另一种方法是按照一定的算法，从死锁进程中一个一个地选择进行撤销，并同时剥夺这些进程的资源，直到死锁状态解除为止。
死锁定理
1）如果资源分配图中没有环路，则系统没有死锁
2）如果资源分配图中出现了环路，则系统可能出现死锁
如果环路中每个资源的数目只有一个，则意味着死锁的存在，此时，环路是死锁的中分必要条件。
如果处于环路的每个资源数目不为1，则是死锁产生的必要而不是充分条件