死锁
死锁定义
- 操作系统中的死锁，指的是如果在一个进程集合中的每一个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁
死锁产生
死锁防止
破坏互斥条件
- 使资源可以同时访问而不是互斥访问
破坏占有和等待条件
静态分配
- 进程在执行中不再申请资源
- 实现简单，被许多操作系统使用的，但会严重的降低资源利用率
破坏不剥夺条件
采用剥夺式调度方法
- 当进程在申请资源未获得准许的情况下，如主动释放资源（一种剥夺式），然后才去等待
破坏循环等待条件
两种死锁防止方法
- 上述死锁防止的方法造成资源利用率和吞吐率低，两种实用的死锁防止方法
采用层次分配策略
- 资源被分成多个层次，当进程得到某一层的一个资源后，它只能再申请较高层次的资源
- 当进程要释放某层的一个资源时，必须先释放占有的较高层次的资源
- 当进程得到某一层的一个资源后，它想申请该层的另一个资源时，必须先释放该层中的已占资源
层次策略的变种——按序分配策略
死锁避免
银行家算法
死锁检测和解除
死锁定理
- 系统为死锁状态的充分条件是，当且仅当该状态的进程-资源分配图是不可完全简化的，该充分条件称为死锁定理
死锁的解除
- 结束所有进程的执行，重新启动操作系统
- 撤销陷于死锁的所有进程，接触死锁继续运行
- 逐个撤销陷于死锁的进程，回收其资源重新分派，直至死锁解除
- 剥夺陷于死锁的进程占用的资源，但不撤销他，直到死锁解除
- 根据系统保存的检查点，让所有进程回退，直到足以解除死锁
- 当检测到死锁时，如果存在某些未卷入死锁的进程，而随着这些进程执行到结束，又可能释放足够的资源来接触死锁
进程管理
进程通信
消息传递
- 消息传递提供了进程交互需要的同步和通信
- 典型的消息传递原语
- send发送消息的原语
- receive接收消息的原语
- 直接通信
- 对称直接寻址：发送进程和接收进程必须命名对方以便通信
- 非对称直接通信：只要发送者命名接收者，而接收者不需要命名发送者
- 间接通信
- 消息不是直接从发送者发送到接收者，而是发送到由4临时保存这些消息的队列组成的一个共享数据结构，这些队列通常称为信箱mailbox
管道和套接字
- 管道和套接字都是基于信箱的消息传递方式的一种变体
文件管理
文件系统
- 文件系统是操作系统中负责存取和管理信息的模块，它用统一的方式管理用户和系统信息的存储、检索、更新、共享和保护，并为用户提供一整套方便有效的文件使用和操作方法
- 文件的逻辑结构和物理结构
- 逻辑结构
- 对于用户来说，可以按照需要并遵循文件系统的规则定义文件信息的逻辑结构，有文件系统提供“按名存取”来实现对文件信息的存储和检索
- 对于系统来说，必须采用特定数据结构和有效算法，实现文件的逻辑结构到存储结构的映射，实现对文件存储空间和文件信息的管理，提供多种存取方法
- 逻辑结构
文件
- 文件的概念
- 文件是由文件名字表示的一组信息的集合，文件名字是字母或数字组成的字母数字串，他的格式和长度因系统而异
- 目录文件
- 目录文件是由文件目录构成的用来维护文件系统结构的系统文件，普通文件的查找依赖于目录文件
文件的存取
顺序存取
- 对固定长记录的顺序文件采用随机访问
- 对可变长记录的顺序文件，分两步
直接存取
- 文件可看作由顺序编号的物理块组成，这些物理块划成等长，作为定位和存取的最小单位
索引存取
- 基于索引文件的索引存取方法
文件目录
- Linux系统的FCB中的文件名和其他管理信息分开，其他信息单独组成一个数据结构，称为索引结点inode，此索引结点在磁盘上的位置由inode号标识
- 磁盘inode记录文件的属性和相关信息，在内存区开辟一张活动inode表，磁盘inode反映文件静态特性，活动inode反映文件动态特性
文件的存储
文件的逻辑结构
- 文件组织指文件中信息的配置和构造方式，应该从文件的逻辑结构和组织及文件的物理结构和组织两方面考虑
- 文件的逻辑结构和组织是从用户观点出发，研究用户概念中的信息组织方式，这是用户能观察到，可加以处理的数据集合
流式文件
- 流式文件指文件内的数据不再组成记录，只是一次的一串信息集合，称为字节流文件
记录式文件
- 记录式文件包含若干逻辑记录，逻辑记录式是文件中按信息在逻辑上的独立含义划分的信息单位
- 域field是基本数据单元
- 记录record是一组相关的域的集合，它可以看作是应用程序的一个单元
- 文件file是一组相似记录的集合
- 数据库database是一组相关的数据集合
- database自身是由一种或多种类型的文件组成的
记录式顺序文件
记录式索引文件
- 这种文件使用索引表，表项包含记录键和索引指针
- 提供的系统调用有getrecord()、putrecord()
成组和分解
- 成组操作
- 若干逻辑记录合并成一组
- 分解操作
- 当存储介质上的一个物理块读进系统输入缓冲区后，把逻辑记录从块中分离出来的操作
- 块因子：每块中的逻辑记录的个数
文件的物理结构
- 文件的物理结构和组织是指逻辑文件在物理存储空间中存放方法和组织关系
- 第一类计算法
- 设计映射算法，通常用线性计算法、杂凑法等，通过对记录键对计算转换成对应的物理地址，从而找到所需记录
- 直接寻址文件、计算寻址文件、顺序文件均属此类，计算法的存取效率高
- 第二类指针法
- 设置专门指针，指明相应记录的物理地址或表达各记录之间的关联
- 索引文件、索引顺序文件、连接文件均属此类
顺序文件（连接文件）
连接文件（串联文件）
直接文件（哈希文件）
设备管理
I/O控制方式
程序控制I/O（轮询方式）
- 处理器代表给I/O模块发送一个I/O命令，该进程进入忙式等待，等待操作的完成，然后才可以继续操作
中断驱动I/O
- 处理器代表进程向I/O模块发出一个I/O命令，然后继续执行后续指令，等I/O模块完成工作后，处理器被该模块中断
- 如果该进程不需要等待I/O完成，则后续指令可以仍是该进程中的指令，否则，该进程在这个中断上挂起，处理器执行其他操作
直接存储器访问DMA
- 一个DMA模块控制主存和I/O，模块之间的数据交换。为传送一块数据，处理器给DMA模块发送请求，只有当整个数据块传送结束后，处理器才被中断
通道方式
- 为获得CPU和外围设备更高的并行工作能力，引入通道
- CPU在执行主程序时遇到I/O请求，它启动指定通道上选址的外围设备，一旦启动成功，通道开始控制外围设备进行操作。CPU就可执行其他任务并与通道并行工作，直到I/O操作的完成。通道发出操作结束中断，CPU才停止当前工作，转向处理I/O操作结束事件
- CSW通道状态字
- 通道状态字是存放在内存固定单元的控制字，专门用于记录通道和设备执行操作的情况
- CAW通道地址字
- 通道地址字是存放在内存固定单元的控制字，专门用于存放通道程序首地址
虚拟设备
- 虚拟设备
- 虚拟设备是使用一类物理设备模拟另一类物理设备的技术
- 通常是使用共享型外围设备模拟独占型外围设备
SPOOLing设备
- 井是用作缓冲的存储区域
- 预输入程序
- 操作系统将一批作业从输入设备上预先输入到磁盘的输入缓冲区中暂时保存，这称为“预输入”，此后，由作业调度作业执行，作业使用数据时不必再启动输入设备，只要从磁盘的输入缓冲区中读入
- 缓输出程序
- 作业执行中不必直接启动输出设备，只要将作业的输出数据暂时保存到磁盘的输出缓冲区，当作业执行完毕后，由操作系统组织信息成批输出
- 井管理程序
I/O设备管理的实现和层次
I/O软件
- 把软件组织成一种层次结构，底层软件用来屏蔽硬件的具体细节，高层软件则主要向用户提供一个简洁、规范的界面
- 解决的问题
- 设备无关性
- 出错处理
- 同步（阻塞）——异步（中断驱动）传输
- 独占型外围设备和共享型外围设备
I/O软件的层次
用户层I/O软件
- 进行I/O调用；格式化I/O；SPOOLing
与设备无关的操作系统I/O软件
- 命名；保护；阻塞；缓冲；分配
设备驱动程序
- 建立设备寄存器；检查状态
I/O中断处理程序（底层）
- 执行I/O操作
