osNote

第一章 绪论

操作系统的定义和特性

• 桌面常见的四大操作系统
  • Windows系统
  • Linux系统
    • RedHat小红帽
  • Mac系统
  • Unix系统
• 没有安装操作系统的计算机能干什么
  • 无法继续启动
  • 没有安装操作系统的计算机开机进入DOS界面，需要输入指令来进行操作，无法使用鼠标、键盘等，裸机启动过程分为三步（也就是会进入BIOS）：
    1. 裸机上电后，会启动自检程序，自检程序会对硬件进行检测，判断计算机情况是否正常，若有问题则提示；
    2. 初始化操作，对一些外部设备进行初始化和检测；
    3. 引导程序，引导DOS
• 操作系统的基本功能
  • 提供操作界面
  • 控制程序运行
  • 管理系统资源
  • 配置系统参数
  • 监控系统状态
  • 工具软件集合
• 操作系统的定义
  • 操作系统是一个大型系统程序，它负责计算机系统软、硬件资源的分配；控制和协调并发活动；提供用户接口，使用户获得良好的工作环境
  • 简而言之，管理并调度资源，为用户提供接口
• 不同角度理解操作系统
  • 终端用户
    • 界面和命令
  • 应用程序员
    • 编程接口API
  • 系统程序员
    • 管理和调度硬件资源
    • 提供接口
• 操作系统的地位
  • 
• 操作系统的特性（重点）
  • 并发性
    • 同时处理多个任务的能力
  • 共享性
    • 为多个并发任务提供资源共享
  • 不确定性
    • 具有处理随机事件的能力
      • 中断处理的能力
      • 自动化能力

操作系统的功能（重点）

• 进程管理功能、存储管理功能、设备管理功能、文件管理功能
• 进程管理
  • 处理机分配
  • CPU管理
  • 处理机管理
  • 多个程序如何共享CPU
  • 具体功能：
    • 进程控制：创建，暂停，唤醒，撤销
    • 进程调度：调度策略，优先级
    • 进程通信：进程间通信
• 存储管理
  • 为应用程序运行高效提供内存空间
  • 支持多道程序设计
  • 作用：
    • 内存分配
    • 内存共享
    • 内存保护
    • 虚拟内存
• 设备管理
  • 提供统一的设备使用接口，管理设备分配和使用
    • 设备无关性
    • 设备的传输控制
    • 设备的驱动
• 文件管理
  • 文件和目录的管理
  • 提供简便统一的信息存取和管理方法，解决信息共享、数据的存取控制等问题
    • 存储空间管理
    • 文件的操作
    • 目录的操作
    • 文件和目录的存取权限管理

操作系统的性能

• 吞吐率
  • 在单位时间内处理信息的能力
• 响应能力
  • 从接收数据到输出结果的时间间隔
• 资源利用率
  • 设备使用的频度
• 可移植性
  • 改变硬件环境仍能正常工作的能力：代码修改量
• 可靠性
  • 发现、诊断和恢复系统故障的能力

操作系统的发展历史

• 计算机硬件发展的四个典型阶段

  • 电子管时代
  • 晶体管时代
  • 集成电路时代
  • 大规模集成电路时代

• 操作系统发展的四个典型阶段

  1. 手工操作
  2. 单道批处理系统
  3. 多道批处理系统
  4. 分时操作系统

• 手工操作

  • 使用特点
    • 上机：编程（打孔），预约，操作机器（开关/接线）
    • 程序启动与结束：手工处理
  • 缺点
    • 效率低：CPU运行时间少，例：100分钟 = 50分钟(装) + 10(CPU运行) + 40(拆)
    • 用户独占
    • 缺少交互

• 单道批处理系统

  • 工作过程
    • 管理员将多个作业输入到磁盘形成作业队列
    • 监控程序依次自动处理磁盘中的每个作业
      • 装入—运行—撤出—装入—运行—撤出—……
    • 运行完毕，通知用户取出结果
  • 工作特点
    • 一批：作业队列
    • 自动：识别作业
    • 单道：串行
  • 单道批处理的两种实现方式
    • 联机批处理
      • 
      • 特点：主机控制输入/输出
      • 缺点：系统效率低
    • 脱机批处理
      • 
      • 特点：卫星机控制输入/输出
      • 优点：系统效率高
      • 缺点：调度不灵活；保护问题
  • 单道批处理系统中CPU的使用情况
    • 
    • 现象：外设工作时CPU空闲，CPU工作时外设空闲
    • 结论：CPU和外设效率低
  • 单道批处理系统程序的改进
    • 
    • 程序设计合理
      • 使得IO发生时，程序可以继续做一些其他的工作，例如上图中的WhileReading()函数
    • 系统必须提供工具
      • 程序可以启动设备和测试设备

• 多道批处理系统（重点）

  • 多道程序设计技术
    • 在内存中存放多道程序，当某道程序因为某种原因（例如请求IO时）不能继续运行，监控程序便调度另一程序投入运行，这样可以使CPU尽量处于忙绿状态，提高系统效率
  • 多道批处理系统
    • 采用多道程序设计技术实现的处理系统称为多道批处理系统
  • 多道批处理系统的设计目的
    • 提高系统的利用率（或吞吐量）
      • CPU和外设并行
      • 外设之间也并行
  • 多道程序相互穿插的运行过程
    • 
    • A、B两道程序相互穿插的运行，使CPU和外设都尽量忙碌
  • 多道程序设计思想
    • 多个程序同时在计算机/虚拟机上运行
    • 物理资源的共享
      • 时分：分成多个时段，不同进程错开使用不同时段
      • 空分：分成多个单元，不同进程同时使用不同单元
      • 
  • 多道批处理系统的特点
    • 多道：内存同时存放多道程序
    • 并行：宏观上
    • 串行：微观上
  • 意义：多道技术出现——操作系统形成
  • 多道批处理系统的缺点
    • 作业处理时间长
    • 运行过程不确定
    • 交互能力差
    • 
  • 60年代硬件的两个重大进展
    • 中断技术
      • 当CPU收到外部信号（中断信号）后，停止当前的工作，转去处理该外部事件，处理完毕后回到原来工作的中断处（断点）继续原来的工作
    • 通道技术
      • 专门处理外设和内存之间的数据传输的处理机

• 分时技术与多道批批处理系统都能完成多个程序的切换，这两种切换有何差别

  • 分时技术采用的方法是，主机以很短的时间片为单位把CPU轮流分配给每个终端使用，直到作业被全部运行完，让终端认为自己独占CPU
  • 多道批操作系统是内存中存放了多个程序，程序相互穿插运行，当某道程序没有使用CPU时，系统调度另一程序投入执行；多道批处理本质在微观上还是相当于单道批，但是分时技术可以把多个程序真正地“同时”（差别时间不大）运行

• 分时操作系统

  • 背景

    • 中断技术
    • 大规模集成电路
    • 事务性任务和程序的涌现
      • 交互性高
      • 响应快速
    • 要求：多任务多用户

  • 多终端计算机

    • 主机采用分时技术轮流为每个终端服务，每个终端都感觉到是“独占”主机

  • 分时技术（重点）

    • 概念

      • 主机以很短的“时间片”为单位，把CPU循环的轮流分配给每个作业（终端/用户）使用，直到全部作业被运行完

    • 特点

      • 时间片：较短时间间隔

      • 响应及时：独占主机

  • 分时系统的特点

    • 多路调制性
      • 多用户联机使用同一台计算机
    • 独占性
      • 用户感觉独占一台计算机
    • 交互性
      • 及时响应用户的请求

• UNIX

  • 第一个实用化的分时操作系统
  • 革新和创造
    • 实现了操作系统的可移植性
    • “特殊文件”：外设看作文件

• 操作系统的进一步发展

  • 实时操作系统/嵌入式操作系统
  • 微机操作系统
  • 多处理机操作系统
  • 网络操作系统
  • 分布式操作系统
  • 嵌入式操纵系统

第二章 操作系统结构与硬件支持

操作系统虚拟机（重点）

• 面对用户，裸机配置操作系统后称为操作系统虚拟机
  • 用户界面
  • 屏蔽硬件细节
  • 扩展硬件功能
  • 系统更安全
  • 系统更可靠
  • 效率更高

操作系统的逻辑结构

• 逻辑结构

  • OS的设计和实现思路

• 逻辑结构的种类

  • 整体式结构（单体式结构、宏内核结构）
  • 微内核结构
  • 层次式结构

• 整体式结构

  • 以模块为基本单位构建
    • 每个模块具有特定的功能
  • 定义
    • 模块化结构/单体内核结构/宏内核结构
    • 操作系统由大量的过程构成，每个过程都有明确参数列表、返回值类型，大多数过程是可以相互间调用的
    • 
  • 优点
    • 模块的设计、编码和调试独立
    • 模块之间可以相互调用
  • 缺点
    • 错误容易扩散
    • 开发和维护困难
    • 可伸缩性差
  • 实例os——UNIX
    • 采用单一内核模块（单体结构）实现
    • 对外提供一组系统调用
    • 设备驱动与内核其他部分分开
  • 实例os——Linux
    • 宏内核，单体内核
    • 支持动态可安装模块
    • 模块可以在操作系统中动态安装或去除
    • 模块可以在内核运行时编译或安装

• 层次式结构

  • 层次结构的软件例子——TCP/IP协议栈

  • 定义

    • 功能模块按调用次序排成若干层，各层单向依赖或单向调用
    • 

  • 分层原则

    • 硬件相关——最底层
    • 外部特性——最外层
    • 中间层——调用次序或消息传递顺序
    • 共性服务——较低层
    • 活跃功能——较低层
    1. 硬件相关的放在最底层
    2. 与用户策略或用户交互相关的功能放在最顶层
    3. 中间层各层按调用次序或消息传递次序安排
    4. 共性的和活跃的服务放在较低的层次

  • 层次结构的优点

    • 结构清晰，避免循环调用
    • 整体结构局部化，系统的正确性容易保证
    • 有利于操作系统的维护、扩充和移植

• 微内核结构（客户/服务器结构）

  • 客户——应用程序
  • 服务器——操作系统
    • 微内核
      • 足够小，提供OS最基本的核心功能和服务
      • 足够与硬件紧密相关的处理
      • 实现一些较基本的功能
      • 负责客户与服务器之间的通信
    • 核外服务器
      • 完成OS的绝大多数功能，等待用户提供请求
      • 由若干服务器或进程共同构成
        • 例如：进程/线程服务器，虚存服务器，设备管理服务器等，以进程形式运行在用户态
    • 

• 微内核和单体内核（宏内核）的比较

  • 

操作系统依赖的基本硬件环境

处理机的态（重点）

• 支持操作系统的最基本的硬件结构

  • CPU、内存、中断、时钟

• 操作系统考虑的安全问题

  • 共享/安全
    • 防止进程的信息被非法访问
    • 防止进程随意存取系统资源
    • 防止进程修改系统安全机制
    • 
  • 解决策略
    1. 软件被设置为可信软件和不可信软件两类
       • 保护机制能区分可信软件和不可信软件
       • 可信软件权限高
         • 可以修改安全保护机制
         • 可以存取系统资源
       • 不可信软件
         • 功能受限
       • CPU能区分当前软件的类型并设置不同的工作模式
    2. 设置访问屏障
       • CPU根据当前的工作模式，限制可使用的指令集
       • 设置可信软件和不可信软件之间的访问屏障

• CPU

  • CPU态（Mode）
    • CPU的工作状态
    • 对资源和指令使用权限的描述
  • 硬件描述
    • 在处理器中包含有一个模式位，表明当前的权限状态
    • 指令执行前增加“权限状态是否满足”的条件判断
    • Intel CPU
      • PE位，PG位
      • 地址映射机制
      • 权限核验
  • 特权指令
    • 类别
      1. 涉及外部设备的输入/输出指令
      2. 修改特殊寄存器的指令
      3. 改变机器状态的指令
  • CPU态的分类
    • 核态
      • 能够访问所有资源和执行所有指令
      • 管理程序/OS内核
    • 用户态
      • 仅能访问部分资源，其他资源受限
      • 用户进程
    • 管态
      • 介于核态和用户态之间
  • 硬件和OS对CPU的观察
    • 硬件按“态”来区分CPU的状态
    • OS按“进程”来区分CPU的状态
    • 
  • 用户态和核态之间的转换
    • 用户态向核态转换
      • 用户请求OS提供服务
      • 发生中断
      • 用户进程产生错误（内部中断）
      • 用户态企图执行特权指令
    • 核态向用户态转换的情形
      • 一般是中断返回：IRET

• 内存

  • 存储器：存储程序和数据的部件
  • 存储器分类
    • 按与CPU的联系
      • 主存：直接与CPU交换信息
      • 辅存：不能直接和CPU交换信息
    • 按存储器（半导体存储器）读写工作方式
      • RAM
      • ROM
  • 理想体系
    • 理想存储体系：速度快、容量大、成本低
    • 实际存储体系
      • 寄存器
      • 高速缓存
      • 主存
      • 磁盘
  • 分级存储系统的工作原理
    • CPU读取指令或数据时的访问顺序
      1. 访问缓存
      2. 访问内存
      3. 访问辅存
    • 

• 时钟

  • 以固定时间间隔产生时钟信号，提供计算机所需的节拍
  • 时钟的作用：
    • 时间片
    • 提供绝对时间
    • 提供预定的时间间隔
  • 时钟的类型
    • 绝对时钟
    • 相对时钟

中断机制（重点）

• 中断

  • 中断定义

    • 只CPU对突发的外部事件的反应过程或机制
    • CPU收到外部信号后，停止当前工作，转去处理该外部事件，处理完毕后回到原来工作的地方继续原来的工作

  • 引入中断的目的

    • 实现并发活动
    • 实现实时处理
    • 故障自动处理

  • 

  • 中断的一些概念

    • 中断源

      • 引起系统中断的事件称为中断源

    • 中断类型

      • 强迫中断和自愿中断

        • 强迫中断：程序没有预期，例如：IO、外部中断
        • 自愿中断：程序有预期，例如：执行访管指令

      • 外中断（中断）和内中断（俘获）

        • 外中断：由CPU外部事件引起，例如：IO、外部事件
        • 内中断：由CPU内部事件引起，例如：访管指令、程序中断

      • 外中断：不可屏蔽中断和可屏蔽中断

        • 不可屏蔽中断：中断的原因很紧要，CPU必须响应
        • 可屏蔽中断：中断的原因不很紧要，CPU可以不响应

    • 断点

      • 程序中断的地方，将要执行的下一条指令的地址
      • CS：IP

    • 现场

      • 程序正确运行所依赖的信息集合
      • PSW程序状态字，PC，相关寄存器

    • 进入中断服务程序：破坏主程序的现场

    • 现场的两个处理过程

      • 现场的保护：进入中断服务程序之前，入栈
      • 现场的恢复：退出中断服务程序之后，出栈

  • 中断响应过程

    1. 识别中断源
    2. 保护断点和现场
    3. 装入中断服务程序
    4. 进入中断服务程序
    5. 恢复现场和断点
    6. 中断返回：IRET
    7. 

  • 

  • 中断响应的实质

    • 交换指令执行地址
    • 交换CPU的态
    • 工作
      • 现场保护和恢复
      • 参数传递（通信）

第三章 用户界面

用户环境和构造

• 用户环境
  • 用户工作的软件环境
    • 桌面环境
    • 命令行环境
• 用户环境构造
  • 按照用户要求和硬件特性按照和配置操作系统
    • 提供操作命令和界面
    • 提供系统用户手册

操作系统的启动

• 相关背景知识

  • 实模式和保护模式
  • BIOS(Basic I/O System)
  • POST(Power On Self Test)
  • CMOS

• 启动过程

• 操作系统的安装

  • MBR（主引导程序）
  • 安装过程
  • 多操作系统安装和启动

• 实模式（实地址模式）

  • 程序按照8086寻址方式访问0-FFFFFh（1MB）空间
  • 寻址方式：物理地址（20位）
  • CPU单任务运行
  • 实模式存取的1M空间
    • 前面640K：基本内存
    • 中间128K：显卡显存
    • 末尾256K：BIOS

• MBR

  • 和os启动相关的数据和代码
  • 存放在主启动扇区
  • MBR读取分区表，查找并确认唯一活动分区，MBR读取活动分区PBR，并加载到内存
  • PBR控制后续引导进程

• BIOS

  • 基本输入输出系统
  • 功能：
    • CMOS设置
    • 基本IO设备中断服务
    • POST上电自检
    • 系统自举/加载OS

• POST

  • 加电自检
  • 初始化基本硬件
    • CPU、内存、显卡

• 系统自举/加载OS

  • 开机时将OS载入内存并运行，为用户建立用户环境

• 操作系统的启动

  • 从加电到用户工作环境准备好的过程
  1. 初始引导
  2. 核心初始化
  3. 系统初始化

1. 初始引导
   • 目的：把OS内核装入内存并使之开始工作，接管计算机系统
   • 过程：
     • 加电，jump POST
     • 跳入BIOS的启动程序
       • 读取第0面0道1扇区的内容
       • MBR：主启动记录，引导程序
     • 运行引导程序
       • 根据相关参数，读取硬盘指定位置的OS内核到内存
       • 初始化基本参数
     • OS内核：逐步加载OS剩余部分，直到最后完全控制计算机
2. 核心初始化
   • 目的：OS内核初始化系统的核心数据
3. 系统初始化
   • 目的：为用户使用系统做准备，使系统处于待命状态

用户界面

• 用户界面的定义

  • OS提供给用户控制计算机的机制，又称用户接口
  • 

• 用户界面的类型

  • 操作界面

  • 系统调用

操作界面

• 图形用户接口
• 键盘命令
  • 普通命令：ls、cd、ps等
  • 批处理程序：普通命令的集合，批执行
  • shell：操作系统和用户交互的界面
    • shell表现为通过控制台执行用户命令的方式
    • shell本身不执行命令，仅仅是组织和管理命令

系统调用（重点）

• 系统调用
  • 操作系统内核为应用程序提供的一系列服务/函数
• 特点
  • 一般涉及核心资源或硬件的操作
  • 系统调用运行于核态
  • 每个系统调用有唯一的编号：ID
  • 系统调用过程会产生中断：自愿中断
• 具体OS中系统调用的实现
  • DOS：int 21h
  • Linux：int 80h
• 访管指令
  • 用于实现在用户态下运行的进程调用操作系统内核程序
  • 执行过程
    1. 设置模式位
    2. 转入内核某固定位置（自陷中断处理）
    3. 跳转到相应的OS服务例程，执行
    4. 返回用户空间

第四章 进程管理

进程概念

• 进程定义
  • 进程是程序在某个数据集合上的一次运行活动
    • 数据集合：软硬件环境，多个进程共存/共享的环境
• 进程的特征
  • 动态性：进程是程序的一次执行过程，动态产生/消亡
  • 并发性：进程可以同其他进程一起向前推进
  • 异步性：进程按各自的速度向前推进
  • 独立性：进程是系统分配资源和调度CPU的单位
• 进程和程序的区别
  • 动态和静态
    • 进程是动态的：程序的一次执行过程
    • 程序是静态的：一组指令的有序集合
  • 暂存和长存
    • 进程是暂存的：在内存上驻留
    • 程序是长存的：在介质上长期保存
  • 一个程序可能有多个进程
• 进程的类型
  • 按使用资源的权限
    • 系统进程：指系统内核相关的进程
    • 用户进程：运行于用户态的进程
  • 按对CPU的依赖性
    • 偏CPU进程：计算型进程
    • 偏IO进程：侧重于IO的进程

进程的状态

• 进程的状态
  • 运行状态：进程已经占有CPU，在CPU上运行
  • 就绪状态：具有运行条件但由于无CPU，暂时不能运行
  • 阻塞状态：因为等待某项服务完成或信号到来而不能运行的状态，例如：系统调用，IO操作，合作进程的信号或服务
  • 进程状态的变迁：
    • 
    • 
• 支持挂起和解挂操作的进程状态
  • 

进程控制块（PCB）

• 进程的描述——进程控制块
  • 描述进程的状态、资源、和相关进程的关系的一种数据结构
  • PCB是进程的标志
  • 创建进程时创建PCB，进程撤销后PCB同时撤销
• 和进程标识相关的成员变量
  • PID：进程ID
  • PPID：父进程ID
  • PGID：进程组ID

线程概念

• 线程的概念
  • 线程是进程内的一个执行路径
  • 一个进程可以包含多个线程
  • 线程之间共享CPU可以实现并发运行
  • 创建线程比创建进程开销要小
  • 线程间通信十分方便
• 适用场景
  • 程序的多个功能需要并发运行
  • 提高窗口的交互性
  • 改善程序的结构
  • 多核CPU上的应用，充分发挥多核性能

进程控制

• 进程控制的概念

  • 在进程的生存全期间，对其全部行为的控制
  • 四个典型的进程控制
    • 创建进程：创建一个具有指定标识ID的进程
      • 参数：进程标识、优先级、进程起始地址、CPU初始状态、资源清单等
    • 撤销进程：撤销一个指定的进程
      • 收回进程所占有的资源，撤销该进程的PCB
      • 撤销的时机：正常结束、异常结束、外界干预
      • 参数：被撤销的进程名ID
    • 阻塞进程：停止进程执行，变为阻塞
      • 阻塞的时机：请求系统服务、启动某种操作、新数据未到、无新工作
      • 参数：阻塞原因，不同原因有不同的阻塞队列
    • 唤醒进程：唤醒处于阻塞队列中的某个进程
      • 唤醒的时机：系统服务满足，IO完成、新数据到达、进程提出新要求
      • 参数：被唤醒进程的标识

• 创建进程的过程

  • 创建一个空白的PCB
  • 赋予进程标识符ID
  • 为进程分配空间
  • 初始化PCB：默认值
  • 插入相应的进程队列：新进程插入就绪队列

• 进程撤销的实现

  • 在PCB队列中检索出该PCB
  • 获取该进程的状态
  • 若该进程处在运行态，立即终止该进程
    • （递归）先撤销子进程
    • 子进程挂到init进程下
  • 释放进程占有的资源
  • 将进程从PCB队列中移除

• 进程阻塞的实现

  • 停止运行
  • 将PCB运行态改为阻塞态
  • 插入对应的阻塞队列
  • 转调度程序

• 原语

  • 由若干指令构成的具有特定功能的函数
  • 具有原子性，其操作不可分割
  • 创建原语、撤销原语、阻塞原语、唤醒原语

• windows进程控制

  • CreateProcess函数

• Linux进程控制——fork

  • fork创建进程
    • 子进程是父进程的复制
    • 父进程和子进程并发运行（在fork函数之后）
    • fork的返回值：子进程返回0，父进程返回子进程ID，出错返回-1
  • 进程执行特定的功能
    • exec函数族，功能：装入一个指定的可执行程序运行，使子进程具有和父进程完全不同的新功能
  • fork常规用法
    • 

• linux进程控制——wait(int &status)

  • 进程调用wait来阻塞自己
    • 检测子进程是否结束
      • 未结束：等待子进程结束，继续阻塞
      • 已结束：wait收集该子进程信息并彻底销毁它后返回
    • Status接收子进程退出时的退出代码
      • 若忽略子进程的退出信息：wait(NULL)

• linux进程控制——exit(int status)

  • 调用exit终结进程
  • 进程终结时要释放资源并向父进程报告
    • 利用status向父进程传递退出代码
    • 变为僵尸进程，保留部分PCB信息供wait收集
    • 调用schedule函数，选择新进程运行

• Linux进程控制——sleep(int nSecond)

  • 进程暂停执行nSecond秒

同步与互斥

• 进程的互斥关系
  • 多个进程由于共享具有独占性的资源，必须协调各进程对资源的存取顺序：确保没有任何两个或以上的进程同时进行资源的存取
  • 临界资源：一次只允许一个进程独占访问的资源，例如：共享变量i
  • 临界区：进程中访问临界资源的程序段
  • 临界资源和临界区的共享特点
    • 临界资源的访问具有排他性
    • 并发进程不能同时进入“临界区”
  • 访问临界区的方法
    • 锁机制
    • 信号量
• 进程的同步关系
  • 若干合作进程为了共同完成一个任务，需要相互协调运行步伐，一个进程A开始某个操作之前要求另一个进程B必须已经完成另一个操作，否则进程A只能等待
  • 互斥关系属于特殊的同步关系

同步机制

• 锁机制
  • 基本原理
    • 设置一个标识S：表明临界资源是否可用
    • 在进入临界区之前先检查标志是否可用
    • 进入临界区后，将标志修改为不可用——上锁
    • 退出临界区，将标志修改为可用——解锁
  • 上锁原语和解锁原语
• 设置临界区的四个原则
  • 忙则等待
  • 空闲让进
  • 有限等待
  • 让权等待：等待进程放弃CPU（锁机制不满足）

信号量和PV操作

• 信号灯机制

  • 信号灯数据结构

    • 信号灯定义为一个二元矢量(S, q)
    • S信号量：整数，初值非负
    • q队列：进程PCB集合

  • 两个操作

    • P、V操作

  • P操作

    • 

  • V操作

    • 

  • 信号灯与PV操作的应用

    • 实现进程互斥

      • 实质是实现对临界区的互斥访问

        1个临界资源：允许最多一个进程处于临界区

        M个临界资源：允许最多M个程序同时处于临界区

      • 应用过程

        进入临界区之前先执行P操作

        离开临界区之后再执行V操作

        S的初值设置要合理（S初值为临界资源的数量）

      • 例子：

    • 实现进程的同步

      • 同步机制实质

        运行条件不满足时，能让进程暂停

        运行条件满足时，能让进程立即继续

      • PV操作应用于进程同步的基本思路

        暂停当前进程：在关键操作之前执行P操作

        继续进程：在关键操作之后执行V操作

        定义有意义的信号量S，并设置合适的初值（不合理的初值会引发死锁）

经典同步问题

• 生产者、消费者问题
• 读者、编者问题

进程通信

• 进程通信方式
  • 低级通信原语
    • 交换信息量较少
  • 高级通信原语
    • 交换信息较多
• linux软中断通信机制
  • kill(pid,sig)：传递软中断信号
  • signal(sig,func)：注册软中断信号
  • wait()：用于父子进程间的同步
  • sleep()：使当前进程睡眠
• 管道通信
  • 父进程创建管道fd[0]读句柄、fd[1]写句柄
  • 父进程fork、createprocess创建子进程
  • 单向通信（双向通信创建两个管道）
  • 特点
    • 只允许有血缘关系的进程间通信
    • 面向字节流
    • 跟随进程

第五章 资源分配与调度

死锁的概念

• 死锁的定义
  • 两个或多个进程无限期地等待永远不会发生的条件的一种系统状态

产生死锁的原因和必要条件

• 死锁的原因
  • 系统资源有限
    • 资源数目不足以满足所有进程的需要，引起进程对资源的竞争而产生死锁
  • 并发进程的推进顺序不当
    • 进程在运行过程中，请求和释放资源的顺序不当，导致进程产生死锁
• 关于死锁的一些结论
  • 陷入死锁的进程至少是2个
  • 参与死锁的进程至少有两个已经占用资源
  • 参与死锁的所有进程都在等待资源
  • 参与死锁的进程是当前系统中所有进程的子集
  • 死锁会浪费大量的系统资源，甚至导致系统崩溃
• 死锁的必要条件
  • 互斥条件
    • 资源具有独占性，进程互斥的使用资源
  • 不剥夺条件
    • 进程在释放资源前不能被其他程序剥夺
  • 部分分配条件
    • 进程所需要的资源逐步分配，需要时申请和分配
  • 环路条件
    • 多个进程构成环路：环中每个进程已经占用的资源被前一进程申请，而自己所需要的新资源又被环中后一进程所占用

解决死锁问题的策略

• 预防死锁
  • 通过设置某些限制条件，破坏死锁四个必要条件中的一个或多个，来防止死锁
    • 破坏互斥条件——难
    • 破坏不剥夺条件——代价大
    • 破坏部分分配条件——预先静态分配
    • 破坏环路条件——有序资源分配
  • 由于限制太严格，导致资源利用率和吞吐率降低
• 避免死锁——银行家算法
• 检测和恢复死锁
  • 允许死锁发生，但可通过检测机制及时检测出死锁状态，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统从已发生的死锁中清除，将程序从死锁状态解脱出来

第六章 处理机调度（进程调度）

进程调度概念

• 调度定义
  • 在一个队列中，按某种策略选择一个最合适的个体
• 调度分类
  • 长程调度/宏观调度/作业调度
  • 中程调度/交换调度
  • 短程调度/进程调度
  • IO调度/设备调度
  • 
• 进程调度的目标
  • 响应速度尽可能快
  • 进程处理时间尽可能短
  • 系统吞吐量尽可能大
  • 资源利用率尽可能高
  • 对所有进程要公平
  • 避免饥饿
  • 避免死锁
• 进程调度的量化指标
  • 周转时间/平均周转时间
  • 带权周转时间/平均带权周转时间
• 周转时间
  • 进程提交给计算机到完成所花费的时间t = tc - ts
    • ts——进程的提交时间
    • tc——进程的完成时间
  • 意义：说明进程在系统中停留的时间长短
• 平均周转时间
  • t = (t1 + t2 + ...... +tn)/n
  • 平均周转时间越短，意味着这些进程在系统中停留的时间越短，因而系统吞吐量也越大，资源利用率越高
• 带权周转时间
  • w = t/tr
    • t——进程的周转时间
    • tr——进程的运行时间
  • 意义：进程在系统中的相对停留时间
• 平均带权周转时间
  • w = (w1 + w2 + ...... +wn)/n

进程调度算法

• 先来先服务调度
  • 晚来但是很短的作业可能需要等待很长时间，不利于短作业
• 短作业优先调度
  • 忽视了等待时间，一个早来但是很长的作业将会得不到调度
• 响应比高者优先调度
  • 响应比 = 加权周转时间
• 优先数调度
  • 优先数 = 静态优先数 + 动态优先数
  • 静态优先数：在进程创建时确定，在整个进程运行期间不再改变
  • 动态优先数：动态优先数在进程期间可以改变
• 循环轮转调度
  • 把所有就绪进程按先进先出的原则排成队列，进程以时间片为单位轮流使用CPU
    • 时间片太大则会退化成先来先服务算法
    • 时间片太小则会引起进程切换频繁，系统开销增大
• 可变时间片轮转调度
• 多重时间片循环调度
• 调度方式
  • 定义
    • 当一进程正在CPU上运行时，若有更高优先级的进程需要运行，系统如何分配CPU
  • 非剥夺方式
    • 让正在运行的进程继续执行，直到该进程完成或发生某事件而进入完成或阻塞的状态，才把CPU分配给新来的更高优先级的进程
  • 剥夺方式
    • 当更高优先级的进程来到时，便暂停正在运行的进程，立即把CPU分配给新来的优先级更高的进程

Linux进程调度

• 基本特点
  • 基于优先级调度
  • 支持普通进程，也支持实时进程
  • 实时进程优先于普通进程
  • 普通进程公平使用CPU时间

第七章 主存管理

内存管理的功能

• 实际存储体系
  • 三级存储体系
  • Cache+内存+辅存
  • 基本原理
    • 当内存太小不够时，用辅存来支援内存
    • 暂时不运行的模块换出到辅存上，必要时再换入内存
• 存储管理的功能
  1. 地址映射
  2. 虚拟存储（存储扩充）
  3. 内存分配
  4. 存储保护
• 地址映射
  • 定义
    • 把程序中的地址（虚拟地址/虚地址/逻辑地址）变换为真实的内存地址（实地址/物理地址）的过程
  • 方式
    • 固定地址映射
    • 静态地址映射
    • 动态地址映射
  • 固态地址映射
    • 定义：编程或编译时确定逻辑地址和物理地址间的映射关系
    • 特点
      • 程序加载时必须放到指定的内存区域
      • 容易产生地址冲突，运行失败
      • 不能适应多道环境
  • 静态地址映射
    • 定义：程序装入时由操作系统完成逻辑地址到物理地址的映射
      • 保证在运行之前将所有地址都绑定到主存
    • MA = BA + VA
      • MA——物理地址
      • BA——装入基址，基址寄存器
      • VA——逻辑地址
    • 特点
      • 程序运行之前确定映射关系
      • 程序装入后不能移动
      • 程序占用连续的内存空间
  • 动态地址映射
    • 定义：在程序执行过程中把逻辑地址转换为物理地址
      • 例如：MOV AX, [500]，访问500单元时执行地址转换
    • MA = BA + VA
      • MA——物理地址
      • BA——装入基址，基址寄存器
      • VA——逻辑地址
    • 特点
      • 程序占用的内存空间可动态变化
        • 若程序移动及时更新基址BA
      • 程序不要求占用连续的内存空间
        • 需要记录每段放置的基址BA
      • 便于多个进程共享代码
        • 共享代码作为独立的一段存放
• 虚拟存储（存储扩充）
  • 解决的问题
    • 程序过大或过多时，内存不够，不能运行
    • 多个程序并发时地址冲突，不能运行
  • 虚拟存储的基本原理
    • 借助辅存在逻辑上扩充主存，解决内存不足
    • 过程
      • 迁入：将要运行的部分装入内存，把辅存存放的部分临时按需调入内存
      • 迁出：把当前不运行的部分暂时存放在辅存，尽量腾出足够的内存供进程正常运行
    • 前提：短时间内进程不运行的部分往往占大部分
    • 用户体验了足够大的线性内存——虚拟内存
  • 程序局部性原理
    • 时间局部性
      • 一条指令或数据，会在较短的时间内被重复访问
      • 例如：循环语句
    • 空间局部性
      • 任一内存单元及其临近单元会在短时间内被集中访问
      • 短时间内，CPU对内存的访问往往会集中在一个较小区域内
      • 例如：表，数组的操作
    • 结论
      • 程序在一个有限的时间段内访问的代码和数据往往集中在有限的地址范围内，因此，一般情况下，把程序的一部分装入内存在较大概率上也足够让其运行一段时间
  • 实现虚拟存储的前提
    • 足够的辅存
    • 适量容量的内存
    • 地址变换结构
  • 虚拟存储的应用
    • 页式虚拟存储
    • 段式虚拟存储
• 内存分配
  • 为程序运行分配足够的内存空间
  • 需要解决的问题
    • 放置策略
      • 程序调入内存时将其放在哪个位置
      • 全部分配或部分分配
    • 调入策略
      • 何时把要运行的代码或访问的数据调入内存
    • 淘汰策略
      • 迁出哪些代码和数据以腾出内存空间
• 存储保护
  • 保证内存中的多道程序只能在给定的存储区域活动并互不干扰
  • 保护方法
    • 界址寄存器
      • 在CPU中设置一对下限寄存器和上限寄存器，存放程序在内存中的下限地址和上限地址
      • 基址寄存器和限长寄存器
      • 适用于连续物理分区中的情形
    • 存储键保护
      • 适用于不连续物理分块的情形，也可用于共享中的权限

物理内存管理

• 物理内存管理方法
  • 单一区存储管理（不分区存储管理）
  • 分区存储管理
  • 内存覆盖技术
  • 内存交换技术
• 单一区存储管理
  • 内存的用户区不分区，完全被一个程序所占用

分区存储管理

• 定义：把用户区内存划分成若干大小不等的分区，供不同程序使用

• 分类

  • 固定分区
  • 动态分区

• 固定分区

  • 把内存固定的划分为若干个大小不等的分区供各个程序使用，每个分区的大小和位置都固定，系统运行期间不再重新划分
  • 分区表：记录分区的位置、大小和使用标志
  • 例子：
  • 使用特点
    • 在程序装入之前，内存已被分区，不再改变
    • 每个分区大小不同，适应于不同大小的程序
    • 系统需要维护分区表
  • 固定分区缺点
    • 浪费内存：程序比所在分区小
    • 大的程序可能无法运行：程序比最大分区大，无法装入
  • 应用建议
    • 程序大小、个数、装入顺序都是固定的情形
    • 根据分区表安排程序装入顺序

• 动态分区

  • 在程序装入时创建分区，使分区的大小刚好与程序的大小相等

  • 例子：

    

  • 特点

    • 分区动态建立
    • 分区的个数和大小均可变
    • 存在内存碎片

  • 动态分区需要解决的问题

    • 分区的选择
    • 分区的分配
    • 分区的回收
    • 解决内存的碎片问题

  • 分区的选择（放置策略）

    • 程序装入空闲区时，尽量往高地址靠拢

    • 空闲区表：描述内存空闲区的位置和大小的数据结构

    • 分区选择：

      • 从空闲区表中选择一个空闲区给用户使用
      • 选择策略/放置策略

    • 放置策略

      • 从排序好的空闲区表中选择第一个大小够大的分区
      • 选择分区与空闲区表排序方式有关

    • 空闲区表的排序原则

      • 首次适应算法：按空闲区位置递增排序
        • 尽可能先利用低地址空间
      • 最佳适应法：按空闲区大小递增排序
        • 尽量选择满足要求的最小空闲区
      • 最坏适应法：按空闲区大小递减排序
        • 尽量使用最大的空闲区
        • 仅作一次查找就可以找到所要分区

  • 分区的分配

    • 从用户选中的分区中分配/分割所需大小给用户
    • 剩余部分依然作为空闲区登记在空闲区表中
    • 注意：分割空闲区时，一般把底部分割给用户（因此，空闲区表只需修改大小即可）

  • 分区的回收

    • 回收程序占用的分区（释放区），将其适当处理后登记到空闲区表中，以便再分配
    • 若释放区与现有空闲区相邻则合并

  • 碎片问题

    • 动态分区的缺点
      • 容易产生内存碎片：内存反复分配和分割
      • 首次适应法，最佳适应法，最坏适应法
    • 解决碎片的方法
      • 规定门限值：分割空闲区时，若剩余部分小于门限值，则此空闲区不进行分割，而是全部分配给用户
      • 内存拼接技术：将所有空闲区集中一起构成一个大的空闲区
      • 把程序分拆成几个部分装入不同分区，充分利用碎片

覆盖技术

• 目的：在较小的内存空间中运行较大的程序
• 内存分区
  • 常驻区：被某段单独使用且固定的占用的分区，可划分多个
  • 覆盖区：能被多段共用（覆盖）的区域，可划分多个
• 工作原理
  • 程序划分成若干代码段或数据段
  • 将程序常用的段装入常驻区
  • 将程序不常用的段装入覆盖区
    • 正在运行的段处于覆盖区
    • 暂时不运行的段放在硬盘中（覆盖文件）
    • 即将运行的段装入覆盖区（覆盖旧内容）
  • 意义：减少程序对内存的需求
  • 例子：

对换技术

• 原理
  • 当内存不够时把进程写到磁盘，当进程要运行时重新写回内存
• 优点
  • 增加进程并发数
  • 不考虑程序结构
• 缺点
  • 换入和换出增加CPU开销
  • 对换单位太大

虚拟内存管理

• 物理内存（即实内存）管理
  • 
• 改善物理内存管理的相关技术
  • 内存拼接
  • 对换技术
  • 覆盖技术
• 虚拟内存的概念
  • 虚拟内存是面向用户的虚拟封闭存储空间
  • 线性地址空间
  • 容量4G
  • 封闭空间（进程空间）
  • 和物理地址分离（地址无冲突）
  • 程序员编程时使用线性虚拟地址
• 虚拟内存管理
  • 目标
    • 使得大的程序能在较小的内存中运行
    • 使得多个程序能在较小的内存中运行
    • 使得多个程序并发运行时地址不冲突
    • 使得内存利用效率高
  • 虚拟内存管理的实现思路
    • 把程序一小部分装入内存在较大概率上也足够让其运行一小段时间
    • 程序的局部性
      • 程序在一个有限的时间段内访问的代码和数据往往集中在有限的地址范围内
  • 典型虚拟内存管理方式
    • 页式虚拟内存管理
    • 段式虚拟内存管理
    • 段页式虚拟内存管理

页式存储管理

• 页式虚拟内存管理
  • 概念
    • 把进程空间（虚拟）和内存空间都划分成等大小的小片
      • 进程的小片——页
      • 内存的小片——页框
      • 小片的典型大小：1K、2K、4K
  • 程序装入和使用内存的原则
    • 内存以页框为单位分配使用
    • 进程以页为单位装入内存
      • 只把程序部分页装入内存便可运行
      • 页在内存中占用的页框不必相邻
      • 需要新页时，按需从硬盘调入内存
      • 不在运行的页及时删除，腾出空间
  • 页式系统中的地址
    • 虚拟地址VA是线性的，从0开始
    • VA分成页号P和页内偏移W
      • 所处页编号P = VA/页大小
      • 所处页偏移W = VA%页大小
  • 地址映射过程
    • 页面映射表：记录页与页框之间的对应关系，也叫页表
    • 例子：
    • 过程：
      1. 从VA中分离页号P和页内偏移W
      2. 查找页表，以P为索引查找页框号P'
      3. 计算物理地址MA = P' * 页大小 + W
    • 快表：页表部分存放在Cache中称为快表
      • 地址映射时优先访问快表
      • 合理的页面调度策略能使快表具有较高的命中率
    • 页面的共享
      • 在页表中填上共享的页框号，从而实现页面共享
      • 共享页面在内存中只有一份真实存储，节省内存
  • 页表的建立
    • 操作系统为每个进程创建一个页表
      • 页表长度和首地址存放在进程控制块中
    • 当前运行进程的页表驻留在内存
      • 页表长度和首地址由页表长度寄存器和页表首址寄存器指示
  • 页表扩充
    • 扩充有中断位I和辅存地址的页表
    • 中断位I——标识该页是否在内存中，为1标识不在内存，为0标识在内存
    • 辅存地址——该页在辅存上的位置
    • 扩充有访问位（引用位）和修改位的页表
    • 访问位——标识该页是否最近被访问
    • 修改位——标识该页的数据是否已被修改
  • 缺页中断
    • 在地址映射的过程中，当要访问的目的页不在内存时，则系统产生异常中断——缺页中断
    • 缺页中断处理程序
      • 中断处理程序把所缺的页从页表指出的辅存地址调入内存的某个页框中，并更新页表中该页对应的页框号以及修改中断位I为0
      • 
    • 缺页率：f = 缺页次数/访问页面总次数
    • 缺页中断和普通中断
      • 相同点：保护现场、中断处理、恢复现场
      • 不同点：响应时机：普通中断在指令完成后响应，缺页中断在指令执行时响应
  • 二级页表
    • 页表实现时的问题
      • 页表全部装入过度消耗内存（4M）
      • 难以找到连续的1k个页框存放页表
    • 解决办法
      • 仅将页表的部分内容调入内存
      • 将4M的超大页表分拆存储到离散的1k个页框中
    • 
    • 
    • 
  • 淘汰策略
    • 选择淘汰哪一页的规则称为淘汰策略
    • 页面抖动：页面在内存和辅存之间频繁交换的现象
    • 好的淘汰策略
      • 较低的缺页率
      • 页面抖动较少
    • 常用的淘汰算法
      • 最佳算法
      • 先进先出算法
      • 最久未使用算法
      • 最不经常使用算法
  • 最佳算法
    • 淘汰不再需要或最远的将来才会使用的页面
  • 先进先出淘汰算法
    • 淘汰在内存中停留时间最长的页面
  • 最久未使用淘汰算法
    • 淘汰最长时间未使用的页面
  • 最不经常使用淘汰算法
    • 选择到当前时间为止被访问次数最少的页面
    • 每页设置访问计数器，每当页面被访问时，该页面的访问计数器加一
    • 发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零
  • 页面大小选择
    • 页面过大：浪费内存，极限是分区存储
    • 页面过小：页面增多，页表长度增加，浪费内存，换页频繁，系统效率低
  • 影响缺页次数的因素
    • 淘汰算法
    • 分配给进程的页框数
    • 页本身的大小：页面越小越容易缺页
    • 程序的编制方法
      • 局部性越好，越不容易缺页
      • 跳转或分支越多越容易缺页
  • 页式系统的不足
    • 页面划分无逻辑含义
    • 页的共享不灵活
    • 页内碎片

段式存储管理

• 进程分段
  • 把进程按逻辑意义划分成多个段，每段有段名，长度不定，进程由多段组成
  • 例如：一个具有代码段、数据段、堆栈段的进程
• 段式内存管理系统的内存分配
  • 以段为单位装入，每段分配相邻的内存
  • 但是段与段之间不要求相邻
• 段式系统的虚拟地址
  • 段式虚拟地址VA包含段号S和段内偏移W
• 段表
  • 记录每段在内存中映射的位置
  • 段号|段长|基地址
  • 段表的字段
    • 段号S——段的唯一编号
    • 段长L——该段的长度
    • 基地址B——该段在内存中的首地址
• 段式地址的映射机制
  • 过程
    1. 由逻辑地址VA分离出(S,W)
    2. 查询段表：检索段号S，查询该段基地址B和长度L
    3. 物理地址MA = B + W
• 段表的扩充
  • 基本字段：段号，长度，基址
  • 扩展字段：中断位，访问位，修改位，R/W/X
• 段的共享
  • 共享段在内存中只有一份存储
  • 共享段被进程映射到自己的空间（写入段表）
  • 所有共享的模块都可以设置为单独的段
• 段式系统的缺点
  • 段需要连续的存储空间
  • 段的最大尺寸收到内存大小的限制
  • 在辅存中管理可变尺寸的段比较困难
• 段式系统与页式系统
  • 地址空间的区别
    • 页式系统：一位地址空间
    • 段式系统：二维地址空间
  • 段与页的区别
    • 段长可变——页面固定大小
    • 段的划分有意义——页面划分无意义
    • 段方便共享——页面不方便共享
    • 段用户可见——页面用户不可见
    • 段偏移有溢出——页偏移无溢出
    • 段式系统不会产生碎片问题——页式系统会产生碎片

段页式存储管理

• 在段式存储管理中结合页式存储管理技术
• 在段中划分页面
• 段页式系统的地址构成：段号|页号|页内偏移
  • 逻辑地址：段号S，页号P，页内偏移W
  • 内存按页划分，按页装入
• 段页式地址的映射结构
  • 同时采用段表和页表实现地址映射
    • 系统为每个进程建立一个段表
    • 系统为每个段建立一个页表
    • 段表给出每段的页表基地址和页表长度（段长）
    • 页表给出每页对应的框
  • 

Linux存储管理

• /proc文件系统
  • 特点
    • 内存文件系统
    • 为用户访问内核信息提供接口
      • 例：CPU信息
      • 例：内核信息（进程信息）

第八章 设备管理（输入/输出管理）

设备管理概述

• 设备管理功能
  • 状态跟踪
    • 生成设备管理器的数据结构，动态的记录各种设备的状态
  • 设备分配
    • 设备分配功能是设备管理的基本任务
  • 设备映射
    • 设备的两种名字：设备逻辑名、设备物理名
    • 从应用软件的角度看，逻辑设备是一类物理设备的抽象
    • 从设备管理程序的角度看，物理设备是逻辑设备的实例
    • 设备独立性
      • 逻辑设备对用户透明
      • 用户使用统一规范的方式使用设备
  • 设备控制和设备驱动
    • 对物理设备进行控制，实现IO操作
    • 把来自应用的服务请求（例如：读写命令）转换为一系列IO指令，控制设备完成相关操作
    • 向用户提供统一的设备使用接口：read、write
    • 设备驱动程序的特点
      • 设备驱动程序与硬件密切相关
      • 每类设备都要配置特定的驱动程序
  • 缓冲区管理
    • 组织IO缓冲区

缓存技术

• 缓冲作用
  1. 连接有着不同数据传输速度的设备
  2. 协调数据记录大小的不一致
  3. 正确执行应用程序的语义拷贝
     • write(Data,Len)向磁盘写入Data
     • 方法：
       • 内核写完再返回（实时性差）
       • 内核设置缓冲区，完成内核复制即返回，之后由内核把缓冲区写到磁盘（实时性好）
• 提前读和延后写
  • 存储设备
  • 提高数据传输效率
  • 减少进程访问目标设备的次数
• 提前读
  • 进程处理一个输入数据时，直接从IO缓冲区读入，正确的数据已被提前读入到IO缓冲区中
    • 结论：内核提前从输入设备把数据读到IO缓冲区中
    • 但不一定是正确数据
    • 注意同步问题
• 延后写
  • 进程输出数据时，仅把数据写入IO缓冲区，此后，待输出设备空闲时，内核把IO缓冲区的数据写入输出设备
    • 结论：用户处理数据的同时内核输出（有延后）前一数据
• 常用的缓冲技术——环形缓冲
  • 若干缓冲单元首尾链接成一个环：环形缓存区
  • 
  • 

设备分配

• 设备分配方法
  • 独享分配
  • 共享分配
  • 虚拟分配
• 独占设备
  • 每次只能供一个进程单独使用的设备
    • 打印机、键盘、鼠标等
• 共享设备
  • 允许多个进程同时使用的设备
    • 块设备、硬盘等
• 虚拟设备
  • 借助虚拟技术，在共享设备上模逆独占型设备
    • 一般是辅存上模逆独占型设备
• 设备分配
  • 独享分配
    • 申请成功——开始使用——用完释放
  • 共享分配
    • 即时申请即时分配，不阻塞
  • 虚拟分配
    • 申请独占设备，实际分配虚拟设备
• 虚拟技术
  • 在一类物理设备上模逆另一类物理设备的技术
    • 通常借助辅存的一部分区域模拟独占设备，将独占设备转为共享设备
  • 虚拟设备
    • 用来模拟独占设备的部分辅存称为虚拟设备，虚拟独占设备
    • 输入井：模拟输入设备的辅存区域
    • 输出井：模逆输出设备的辅存区域
• 虚拟分配
  • 申请独占设备，实际分配虚拟设备
  • SPOOLING系统是虚拟技术和虚拟分配的实现
    • 
• SPOOLing系统构成
  • 输入井和输出井
    • 磁盘上开辟的两个存储区域
  • 输入缓冲区和输出缓冲区
    • 内存中开辟的存储区域，暂存输入输出数据，以后在传送到输入井和输出井
  • 预输入程序：控制信息从独占设备输入到缓存
  • 预输入表：从哪台设备输入，存放在输入井的位置
  • 缓输出程序：控制信息从缓存输出到独占设备
  • 缓输出表：输出信息在输出井的位置，从那台设备输出
  • 井管理程序：控制用户程序与辅存之间的信息交换
• SPOOLing系统原理小结
  • 任务执行前：预先将程序和数据输入到输入井中
  • 任务运行时：使用数据时，从输入井中取出
  • 任务运行时：输出数据时，把数据写入输出井
  • 任务运行完：外设空闲时输出全部数据和信息
• SPOOLing优点
  • 提高了IO速度
  • 将独占设备改造为“共享设备”
    • 实现了虚拟设备功能

设备驱动程序

• Linux模块

  • LKM
  • 一种未经链接的可执行代码
  • 可以动态的加载或卸载模块
  • 经过连接称为内核的一部分

• Linux设备驱动（LDD）

  • 

• Linux设备分类

  • 字符设备
    • 以字节为单位逐个进行IO操作
    • 字符设备中的缓存是可有可无的
    • 不支持随机访问
    • 如串口设备
  • 块设备
    • 块设备的存取是通过buffer、cache来进行
    • 可以进行随机访问
    • 例如：IDE硬盘设备
    • 支持可安装文件系统
  • 网络设备
    • 通过BSD套接口访问

• 设备文件

  • 将设备作为文件看待
  • 使用文件接口打开、关闭、读写和IO控制设备
    • 字符设备和块设备通过设备文件访问
    • Linux
  • 主设备号和次设备号
    • 主设备号
      • 标识该设备种类，标识驱动程序
      • 主设备号范围：1-255
      • Linux内核支持动态分配主设备号
    • 次设备号
      • 标识同一设备驱动程序的不同硬件设备
      • 次设备号只在驱动程序内部使用

• 驱动程序的基本接口

  • 面向用户程序的接口

  • 面向IO管理器的接口

    1. 注册函数
    2. 注销函数
    3. 数据结构
    4. 请求队列

  • 面向设备的接口

    • 把用户请求转化为端口操作IN/OUT
    1. 无条件传送
    2. 查询传送
    3. 中断传送
    4. DMA传送

第九章 文件系统

文件和文件系统的概念

• 文件的定义

  • 文件是系统中信息存放的一种组织形式
    • 文件是若干信息项的构成
      • 信息项可以是字节，可以是结构化数据
    • 用户通过读写指针来存取文件的信息项
    • 文件具有文件名，用户通过文件名存取文件

• 文件分类

  • 按文件的用途

  • 系统文件

    • 包括操作系统的可执行程序和数据文件，这种文件不对用户开发，仅供系统使用

  • 库文件

    • 系统为用户提供的各种标准函数库和实用程序等，用户只能使用这些文件，而无权进行修改

  • 用户文件

    • 用户创建的文件，如用户可执行文件，源程序，数据文件等

    ---

  • 按文件的操作权限

  • 只读文件

  • 读写文件

  • 不保护文件

    ---

  • 按文件的性质

  • 普通文件

    • 指一般的用户文件或系统文件

  • 目录文件

    • 由目录项组成的文件
    • 目录项：文件名，文件属性，文件存放地址

  • 设备文件

    • 把设备作为文件管理和使用

文件的逻辑结构

• 文件的结构
  • 逻辑结构
    • 为用户提供逻辑结构清晰、使用方便的文件
    • 强调文件信息项的构成方式和用户的存取方式
  • 物理结构
    • 文件在存储设备上的存储结构
    • 强调合理利用存储空间，缩短IO存取时间
• 文件的逻辑结构
  • 流式文件
    • 信息项是字节，文件长度就是字节的数量
    • 优点
      • 文件无需额外的说明信息或控制信息
      • 节省存储空间
  • 记录式文件
    • 信息项由记录组成，一个记录包含若干成员
      • 学生记录：姓名，学号，性别，成绩
      • 学生花名册文件：包含若干个学生记录
    • 特点
      • 文件中需保存记录长度和数量等说明信息
      • 浪费存储空间
  • 现代OS中文件是流式文件
• 文件的存取方法
  • 顺序存取
    • 按文件信息单位排列的顺序依次存取
    • 读写指针
  • 随机存取
    • 直接存取
    • 每次存取操作时先确定存取位置

文件的物理结构

• 文件的物理结构
  • 文件的物理结构是指文件在存储设备上的存储方式，强调合理利用存储空间，缩短IO存取时间
• 物理结构的类型
  • 连续文件
    • 文件按照逻辑顺序存放在存储设备的连续物理块中
  • 串联文件
    • 文件信息存放在不连续的存储块中
    • 每个存储块有一个指针，指向文件的下一个逻辑块所在的存储块
  • 索引文件
    • 文件存放在不连续的物理块中，系统建立索引表记录文件的逻辑块和存储块的对应关系

文件存储空间管理

• 概念
  • 记录当前磁盘的使用情况，创建文件时分配存储空间，删除文件时收回存储空间
• 记录磁盘空闲块的方法
  • 空闲文件目录
  • 空闲块链
  • 位示图
• 空闲文件目录
  • 一片连续的空闲区当作一个特殊文件：空闲文件，该文件由多个连续的空闲存储块组成
  • 所有的空闲文件代表存储设备的空闲空间
  • 空闲文件目录
    • 记录所有空闲文件的目录，每个表项对应一个空闲文件
• 空闲块链
  • 把存储设备上的所有空闲块链接在一起，当申请者需要空闲块时，分配程序从链头开始摘取所需要的空闲块，然后调整链首指针，反之当回首空闲块时，把释放的空闲块逐个加载链尾上
• 位示图
  • 从内存中划出若干个字节，每位对应一个存储块
    • 该位为1：对应存储块空闲
    • 该位为0：对应存储块已分配

文件目录

• 文件目录
  • 文件名址录，记录文件名和存放地址的目录表
  • 为了对大量文件进行分门别类的管理，提高文件检索的效率，现代操作系统往往将文件的一些属性也记录在目录中
• 目录文件
  • 文件目录以文件形式存于外存，这个文件叫目录文件
• 文件目录的功能：将文件名转换为外存物理地址的功能
• 文件的全名：包括从根目录开始到文件为止的通路上所有子目录路径
• 每个文件有唯一的路径名
• 两种路径名形式
  • 绝对路径名
  • 相对路径名

补充

• 多道批处理系统为什么工作效率比单道的高
  • 因为多道批操作系统在内存中存放了多道程序，当某程序因某种原因不能运行放弃CPU时，操作系统调度另一程序投入运行，让CPU尽量忙碌，提高系统效率，而单道批处理系统只能让CPU空闲等待
• 常见的虚拟机软件能不能理解为操作系统
  • 不能，虚拟机只是允许在当前操作系统上运行其他的操作系统，是运行在当前操作系统之上的，是一个应用程序
• 临界区设计太小或太大有何缺点
  • 在保证功能的条件下应该设计的小一些
  • 临界区太大，会使得其他想要访问临界区的进程等待时间过长，致使并发性变差
  • 临界区太小，可能导致临界资源不在临界区内，程序并发执行产生混乱
• 临界区访问机制为什么要实现让权等待原则，锁机制为什么没有满足该原则
  • 让权等待原则是指让等待的进程放弃CPU资源，把资源让给其他进程，避免了CPU资源的浪费，提高CPU的利用率
  • 锁机制的等待程序在未被允许进入临界区之前，一直处于死循环状态，一直占用CPU
• 如何理解参与死锁的进程至少有2个已经占有资源
  • 如果参与死锁的进程只有一个占用资源，那么这个占有资源的进程可以继续获取需要的资源，并在有限时间内执行完成，释放占有的资源供其他需要程序的进程使用，这种情况下此进程为发生死锁，产生矛盾；因此参与死锁的进程至少有两个占用资源。
• 如何证明“按有序资源分配法分配资源并发运行进程不会死锁”
  • 有序资源分配法破坏了死锁的环路条件：即A资源使用者等待B资源，B资源使用者等待A资源，形成死锁
  • 有序资源分配法对资源进行编号，规定进程必须按照编号顺序申请资源，即必须先申请A资源才能申请B资源，那么就不会出现B资源被获取而在等待A资源的情况，所以不会产生死锁
• 如何理解参与死锁的进程都在等待资源
  • 如果某个参与死锁的进程不在等待资源，那么它就会在有限时间内执行完成，并释放占用的资源，即此进程未参与死锁
• 试述缺页中断的概念和缺页中断响应的过程
  • 在地址映射过程中，当所要访问的目的页不在内存中，则系统产生缺页中断
  • 中断处理程序把所缺的页从页表指定的辅助存储器地址调入内存的某个页框中，并更新页表对应项，修改中断位为0