第一章 操作系统概述

(一) 操作系统的基本概念

目的：方便性-支持高级语言，有效性-提高系统资源利用率，提高系统的吞吐量，可扩充性-适应发展与变化，开放性-遵循世界标准规范

• OS 内核本质上就是一个程序，但它是一个特殊到极致的程序：常驻内存、运行在内核态、管理所有硬件、没有“退出”概念、并且所有其他程序都跑在它提供的环境之上。
• OS 内核作为一个大型程序，物理上常驻内存，虚拟上映射到所有进程的高地址内核空间，所有进程共享同一份物理副本。内核空间内部有自己的代码段、数据段、堆、栈、页表、缓冲区等，由内核自己管理。
  作用：

1. 用于与硬件之间的接口：命令方式、系统调用、图标-窗口模式
2. 管理计算机系统资源：处理及、存储器、IO设备及文件
3. 抽象计算机资源：
   抽象层次：物理机 - IO设备管理 （read-write）命令- 文件管理软件 - 窗口软件

(二) 操作系统的发展历程

1. 目的：提高资源利用率，方便用户，器件更新换代、体系结构变更、新应用和需求
2. 历程：人工操作系统 - 脱机输入/输出（引入外存使用外围机管理IO指令和数据） - 批处理系统单道 - 批处理系统多道 - 分时系统 - 实时系统
3. 共同特征：
   1. 并发，
   2. 虚拟：通过时分复用和空分复用将物理实体变成逻辑上的对应物：
      1. 时分复用：虚拟处理机 用户感知到的处理器 虚拟设备技术 IO设备的复用 --利用处理器的空闲时间运行其他程序
      2. 空分复用：利用存储器的空闲空间存放运行多道程序，提高内存的利用率
   3. 异步：进程以不可预知的速度推进
   4. 共享：资源可供内存中多个并发执行的进程共用
      1. 互斥共享：
      2. 同时访问
4. 分时系统：
   1. 作业直接进入内存，多路卡实现分时多路复用，作业按照时间片轮转
5. 实时系统：
   1. 系统的正确性跟产生结果的时间也有关
   2. 周期性和非周期性（截止时间约束:某时间之前必须开始-某时间之前必须结束） 硬实时（HRT）和软实时（SRT）

(三) 程序运行环境

1. CPU 运行模式(内核模式、用户模式)
2. 中断和异常的处理
3. 系统调用
4. 程序的链接与装入
5. 程序运行时内存映像与地址空间

(四) 操作系统结构(分层，模块化，宏内核，微内核，外核）

1. 微内核：凡是需要直接读写硬件寄存器、触发CPU陷阱、操作MMU（内存管理单元）或中断控制器硬件的代码，必须留在内核。

(五) 操作系统引导

(六) 虚拟机

第二章 进程管理

• 前趋图：描述程序先后执行顺序，前趋节点与后继节点，节点重量：表示节点含有的程序量或程序的执行时间
• 顺序执行的程序特征：
  • 顺序性：有严格规定的程序顺序
  • 封闭性：运行时候程序独占全集资源。资源状态只有本程序能改变
  • 可再现性：相同初始条件和环境，重复执行结果相同
    并发执行
• 间断性：并发程序具有执行-暂停-执行的活动规律
• 失去封闭性：资源共享。
• 不可再现性：相同初始环境和初始条件，得到结果不相同

进程

• 进程控制块（PCB：process control block）：描述进程的基本情况和活动过程，运行必要的资源的指针/表项存储在PCB中
• 进程映像由PCB（内核中的数据结构）、程序段（存放指令序列，只读区域）、相关的数据段（存放数据，读写区域）组合而成（在内存中的静态存储布局），
• 进程是一个动态定义：进程是进程实体的运行过程，是进行资源分配和调度的单位
• 进程特征：
  • 动态性：由创建产生，调度执行，撤销消亡
  • 并发性：多个进程实体共存内存，同时间内同时运行（并发）
  • 独立性：进程实体是一个能独立运行、独立获得资源和接收调度的基本单位
  • 异步性：进程按照异步方式运行

进程状态

• 就绪状态：分配到除CPU外以外的所有资源
• 执行状态：进程占有CPU
• 阻塞状态：进程由于事件阻塞
• 创建状态：CPU执行加载器内核代码，
  • 分配内核资源（PCB与PID）：内核从PCB空闲池中分配一个结构体并分配一个PID
  • 建立虚拟地址空间：内核创建内存描述符、建立空的页表，划分虚拟地址区域 -会导致创建失败的硬性内核资源不足
  • 加载程序文件（解析映射磁盘内容）：将磁盘上的二进制文件映射到虚拟地址空间
  • 设置进程上下文（初始化栈和程序入口）：将新进程伪造成一个刚被中断返回的现场 -- 与中断响应程序的恢复现场一致
  • 将进程挂入就绪队列（调度器接管）
• 终止状态：让CPU执行内核中的do_exit()函数
  • 清理：关闭文件描述符、释放内存、释放信号量、共享内存、剥离进程关系、保存退出码
  • 僵尸体：残留空白PCB，供父进程根据退出码判断退出正常与否
  • 资源回收：退出码复制给父进程指定变量，释放子进程
• 挂起状态：挂起原语SUSpend和激活原语Active ，将内存数据换出
  资源管理的数据结构
  进程的组织形式：线性方式、链接方式（相同状态进程队列）、索引方式（相同状态进程PCB索引组成一张表）
  OS内核功能：

1. 支撑功能：提供OS其他模块工作的支撑
   1. 中断处理
   2. 时钟管理
   3. 原语操作
2. 资源管理功能
   1. 进程管理
   2. 存储器管理
   3. 设备管理
      创建进程的事件：

• 用户登录
• 作业调度
• 提供服务
• 应用请求
  原语的实现逻辑：

1. 执行失败复原（乐观锁）：设无冲突 - 暂存修改 - 最终提交
2. 硬件总线霸权（悲观锁）：TAS

硬件同步机制

1. 同步与互斥的基本概念
2. 基本的实现方法(软件方法;硬件方法)
3. 锁
   1. 关中断
   2. 利用Test-and-Set实现互斥
   3. 利用Swap指令实现进程互斥
4. 信号量
   1. 整型信号量
   2. 记录型信号量
   3. AND信号量
   4. 信号量集
5. 条件变量
6. 经典同步问题
   (生产者-消费者问题;读者-写者问题;哲学家进餐问题)

进程通信

OS提供的高级通信工具，使用方便，高效传送

1. 共享存储系统
   1. 共享数据结构
   2. 共享存储区
2. 管道（pipe）通信系统：用于连接读写进程实现通信的共享文件
   1. 互斥、同步、确认是否存在
3. 消息传递系统：维护内核中的消息队列（发送方拷贝到内核缓冲区，接收方从缓冲区拷贝到用户空间）
   1. 直接通信方式：显式指明进程ID -
      1. 对称寻址方式：发送进程和接收进程都必须显示提供对方表示符； - 不利于实现进程定义模块化
      2. 非对称寻址：发送进程命名需要接收进程，接收进程不需要命名发送进程
   2. 间接通信方式：显示指明邮箱ID，接收方可以从任意发送方给的指定邮箱中接收数据
4. 客户机-服务器系统（CS-system）
   1. 套接字（socket）
      1. 基于文件类型（同一机器通信）：套接字关联特殊文件进行读写
      2. 基于网络型（网络通信）：套接字+端口
   2. 远程过程调用和方法调用（RPC）：使用客户存根和服务器存根进行绑定
5. 进程之间的通信：完成之后进程的状态
   1. 两者均阻塞
   2. 发送不阻塞，接收进程被动唤醒
   3. 发送进程和接收进程不阻塞：当事件发生无法运行时候阻塞等待
6. 链路：
   1. 发送进程和接收进程之间显示建立，使用完成后拆除
   2. 无需明确提出，系统自动建立
      1. 单向通信：只允许一边发送一边接收
      2. 双边通信：两边同时发送与接收
7. 信箱：由信箱头和信箱体（存放消息的信箱格组成，创建信箱时候大小确定）组成 - 类似消息队列的精简数据结构
   1. 信箱操作：信箱创建和撤销：给出邮箱名字邮箱属性和共享者名字
      1. 私有邮箱：只允许其他进程发送，与拥有进程同生命周期
      2. 公有邮箱：采用双向通信链路，系统运行期间始终存在
      3. 共享邮箱：进程创建后指明可共享，拥有者和共享者有权取出信息
8. 直接通信实例：使用消息缓冲队列实现（包含发送者进程标识，长度，消息长度，指向下一个消息缓冲区的指针）PCB中存在指向消息队列队首以及队尾的指针
   1. 进程的PCB中增加消息队列首指针，用于对消息队列进行操作
   2. 发送的时候根据消息长度申请缓冲区后将消息复制到缓冲区再将缓冲区地址

线程

线程变为独立运行的基本单位，线程切换的时候仅需保存少量寄存器内容

• 性质：调度基本单位，并发性（可并发执行）、拥有资源、独立性（独立性低，线程共享进程的地址空间和资源）；每个线程独立拥有内核空间；
• 用户级线程的切换不需要内核的干预
• 用户级线程TCB存放在堆，私有栈存放在堆区动态分配;内核级线程由内核创建，用户级由用户态库函数创建
• 线程的状态：执行态，就绪态，阻塞态
  线程不需要切换资源容器（地址空间），进程切换主要损失是TLB失效导致的缓存丢失；切换的时候中断隐指令负责保存返回点，保护现场保护不影响返回后的运算

线程的实现

1. 内核支持线程 -kernel support threads - kst:内核自身华为多个独立执行的上下文，可以并行处理系统调用
2. 用户级别线程 -User level Threads - ULT:用户级线程与内核无关，系统调度仍然以进程为单位：线程切换不需要转换到内核空间，用户级线程实现与平台无关；阻塞线程同时阻塞进程；不能充分利用多CPU的优势
3. 组合方式 - ULT/KST线程，用户级线程进行时分多路复用，内核支持线程数目调整
   1. 多对一模型：多个用户线程映射到一个内核控制线程
   2. 一对一模型：一个内核一个用户级
   3. 多对多模型：多个用户级多个内核级
4. KST的实现：提前内核分配任务数据区PTDA，TCB存储到PTDA中
5. ULT的实现：
   1. 运行时系统：管理和控制线程的函数集合，组成共享库在用户态实现用户级线程
   2. 内核控制线程：在内核中构建独有数据结构，将多LWP组成线程池，用户进程任意用户线程连接LWP时才能与内核通信，线程阻塞的时候相连接的LWP也阻塞
6. 线程的创建与终止
   1. 通过系统调用或者线程创建函数进行线程创建
   2. 线程不自己终止，由终止线程调用函数进行终止
      1. 线程被终止之后不释放占有资源，只有其他线程调用分离函数之后终止线程才与资源分离：内核栈，线程控制块，用户态栈。线程局部存储
      2. 未分离资源的线程可被其他线程调用恢复运行：等待线程终止命令，待目标线程终止之前阻塞，终止之后调用者线程连接完成并执行

处理机调度与死锁

调度就是资源的分配，处理机的调度就是对处理机资源进行分配
高级调度：调度作业，处理外存与内存之间，创建进程并分配到就绪队列
低级调度：进程调度，调度就绪队列中的进程
中级调度：将不能运行的进程调至外存挂起 - 存储器管理的对换功能

• 提高资源利用率，主要是CPU的利用率
• 公平性：所有进程获得合理的CPU时间，不发生进程饥饿现象
• 平衡性：系统资源使用的平衡
• 策略强制执行：安全策略等需要的时候强制执行（可强制调度）

批处理系统评价指标：

1. 周转时间短
   • 平均周转时间：作业提交系统到作业完成时间作业外存后备队列等待时间+就绪队列上等待调度时间+进程CPU执行时间 + 进程等待IO操作完成时间
   • 平均带权周转时间：每个进程占用CPU执行时间与作业周转时间之比的平均值
2. 系统吞吐量：单位时间内系统完成的作业数量多
3. 处理及利用率高：处理机的利用率高

分时系统目标

1. 响应时间快：用户提交请求开始到屏幕显示出处理结果为止的时间：请求信息从键盘传送到处理机+处理机对请求处理 + 响应信息回送到终端显示器
2. 均衡性：系统响应时间快慢与用户请求服务复杂性相适应

实时系统目标

1. 保证截止时间：任务必须开始执行的最迟时间
2. 可预测性：要求请求可预测，通过缓冲实现连续

批处理系统作业

资源管理的数据结构 > 作业控制块 JCB
提前把程序+数据+运行要求组合成作业进行提交

• 作业：进程引入之前的数据结构，负责控制外存与内存之间的交换
• 作业步：作业的加工步骤，：经典的编译-链接装配-运行

1. 作业调度：每次作业调度时候接纳作业数量与接纳作业对象（作业已经建立JCB）
   分时系统为保障及时响应不配置作业调度机制，数据直接送入内存

作业调度算法

1. FIFS算法：按照到达顺序进行调度
2. SJF算法：系统按照用户声明的估计时间（在JCL中声明）预测进行优先排序或者根据进程的历史运行时间进行预测；
   1. 必须预知作业运行时间
   2. 对长作业非常不利
   3. FCFS算法时候，人机无法交互
   4. 未考虑作业紧迫性，高优先级作业可能没有及时处理
3. PSA(priority-scheduling-algorithm)-优先级调度算法:基于作业的紧迫程度，由外部赋予作业优先级进行调度
4. HPRN(High-Response-Ratio-Next)-高响应比优先调度算法：引入动态优先级优先权=\frac{等待时间+要求服务时间}{要求服务时间}
   1. 等待时间相同，短作业优先
   2. 同样长度作业FCFS；
   3. 长作业优先级等待时间增加提高
   4. 每次调度之前计算一次响应比，增大了系统开销

进程调度算法

进程调度需要保存现场信息，按照某种算法选取进程，将处理器分配给进程
进程调度的硬件支撑：

• 排队器：所有就绪进程由排队器插入对应队列
• 分派器（内核代码）：从队列中取出进程，然后进行从分派器到新选出进程间的上下文切换（分配器代码借用原进程内核上下文执行切换程序），将处理器分配给新选出进程
  • 模式切换：A切换进入内核态；保存A的用户态上下文到内核态
  • 进程切换：保存A的内核上下文；恢复B的内核上下文
  • 模式切换：进程B从内核态切换回用户态，B的用户上下文被恢复
  • 上下文切换器（分派器的子模块，用于恢复保存寄存器值）：负责搬运数据
• 进程调度方式
  • 非抢占式调度：处理机分配给某进程后除非主动放弃或者阻塞不放弃处理机
  • 抢占方式：调度程序按照某种原则暂停某个进程重新分配给另一进程
    • 带有优先权：只允许高优先权抢占低优先权
    • 短进程优先抢占
    • 时间片原则
• 轮转调度算法（RR：round robin，RR）：系统按照一定时间间隔中断，确保就绪队列中所有进程在确定时间段内获得一个时间片的处理机时间
  • 进程完成触发调度
  • 时间片用完触发调度
  • 时间片大小确定：大多数交互式进程在一个时间片内完成
• 优先级调度算法：处理机分配给就绪队列中优先级最高的进程
  • 非抢占式优先级调度算法：进程放弃处理机之后才能重新抢占
  • 抢占式优先级调度算法：出现更高优先级别的触发抢占
  • 静态优先级：按照0-255规定优先数
    • 进程类型：系统进程高于一般用户进程
    • 资源要求少的优先级高
    • 用户要求高进程紧迫优先
  • 动态优先级：先赋予优先级，进程推进或等待时间增加改变动态变化
• 多队列调度算法：使用多个就绪队列，每个就绪队列采用不同调度算法，
  • ***多级反馈队列（multileved feedback queue）调度算法：
    • 设置多个就绪队列，优先级高的队列时间片小，一般下级队列时间片大小翻倍
    • 每个队列内采用FCFS算法，时间耗尽未结束进程则降级到下一队列末
    • 高优先级队列抢占低优先级队列
  • 基于公平的调度算法：
    • 保证调度算法：必须跟踪进程已执行处理器时间，应获得的处理机时间，计算进程保活的时间的比率，选择比率最小的进程运行直到超过最接近它的进程比率为止（进程至少执行完一个时间片才会计算进程比率）
    • 公平分享算法：按照用户数量平分处理机时间而不是进程数量平分

实时调度

实时调度需要向调度程序提供就绪时间和开始截止时间和完成截止时间、处理时间、资源要求、优先级
实时性必须满足限制公式\sum_{i=1}^{m}\frac{C_i}{P_i} \le 1(N：n个处理机时候)

• 抢占机制：小的实时系统可以采用非抢占但是大的系统必须采用非抢占；执行完关键性程序和临界区及时自我阻塞
• 快速切换机制：对中断快速响应。快速任务分派
• 实时调度算法：
  • 非抢占式：非抢占式轮转，非抢占式优先级调度（高优先级任务到达之后直接排在队列队首）
  • 抢占式：基于时钟中断的抢占（时钟中断发生时，进行抢占）；立即抢占（当前任务非临界区域直接抢占）
• 最早截止算法-EDF（Earliest Deadline First）算法：截止时间最早的优先级最高
• 最低松弛度优先LLF（Least Laxity First）算法：松弛度 = 截止时间-本身运行时长 - 当前时间
• 优先级倒置算法(priority inversion problem)：由于临界资源的抢占导致高优先级进程因为低优先级进程阻塞
  • 使用临界资源的进程不允许抢占
  • 动态优先级继承：低优先级进程继承因它临界资源阻塞的高优先级进程

死锁

一组死锁进程中的每个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么这组进程死锁

• 死锁条件：互斥、请求并保持、不可抢占、循环等待
• 可重用性资源：只能分配给单个进程
  • 请求资源-使用资源-释放资源
  • 资源数目相对固定，进程运行期间不能增删
  • 通过系统调用实现资源请求和释放
• 消耗性资源：进程动态创建和消耗
  • 单元数目在运行期间不断变化
  • 运行期间，可创造资源单元放入缓冲区
  • 可以请求资源单元进行消耗
• 可抢占性资源：资源分配后可由系统或者其他进程抢占
• 不可抢占性资源：一旦胸痛分配不能强行收回。只能进程用完释放

1. 竞争不可抢占性资源引起死锁
2. 竞争可消耗性资源引起死锁
3. 进程推进不当引起死锁：不安全的分配方案

死锁处理

对于死锁的防范程度减弱，资源利用率提高

1. 预防死锁（事先预防）
   1. 破坏请求和保持：
      1. 协议一-禁止运行时申请资源：全资源申请，进程在开始运行之前，必须一次性申请全部资源
      2. 协议二-释放后重新申请：申请之前释放自己拥有的所有资源，然后一次性申请全部资源 --容易丢失中间计算状态；可能造成活锁或饥饿-适合管理无状态资源
         1. 协议假设：资源释放后，进程可无损重新申请并继续
   2. 破坏不可抢占：当一个进程保持了某些不可抢占的资源时候提出新的请求不能满足需要释放已经保持的资源，待以后需要时候再重新申请
   3. 破坏“循环等待”条件：对系统资源类型线性排序，为每个资源赋予唯一序号；每个进程按照序号递增请求资源；同类资源必须一起申请；申请低序号资源，先释放大于等于该序号的所有资源再一次申请
      1. 限制了新类型设备的增加
      2. 系统使用各类资源的顺序与系统规定的顺序不同，造成资源浪费
      3. 限制用户
2. 避免死锁（事先预防）：系统分为安全和不安全状态，禁止系统进入不安全状态；系统再进行资源分配时候，使系统不进入不安全状态
   1. 安全状态：系统能够按照某种进程推进顺序满足每个进程对资源的最大需求
   2. 银行家算法
3. 检测死锁：对已经发生的死锁进行检测，需要有关资源的请求和分配信息并使用算法判断是否已经进入死锁
   1. 资源分配图：尝试简化资源分配图，当前仅当资源分配图不可简化时，为死锁状态
   2. 死锁检测的数据结构类似银行家算法中的数据结构
4. 解除死锁：撤销回收进程推进其他进程
   1. 抢占资源，分配给死锁进程解除死锁状态
   2. 终止进程，终止撤销系统中一个或多个死锁进程，打破循环环路
      1. 终止所有死锁进程
      2. 按照某种顺序逐个终止进程（难以度量代价最小的顺序）
         1. 进程优先级
         2. 进程已执行时间，剩余时间
         3. 已使用资源，还需要资源
         4. 进程属于交互还是批处理
      3. 付出代价最小的死锁解除算法：按照一定标准计算终止代价最小的进程，终止后重新死锁检测计算代价，如此循环执行

第三章 存储器管理

• 存储器层次：CPU寄存器-cache缓存-主存-磁盘缓存-磁盘-可移动存储介质
• 主存及之上的存储为可执行存储器。其上的信息计算机可以直接load/store访问而不用通过IO设备访问
• 不同层次的存储介质，操作系统统一管理，操作系统存储管理负责对可执行存储器的管理，以及存储器间数据移动；设备和文件管理则提供对辅存的管理
• PFN（page frame number）物理页框号、PTE(page table entry)页表项

主存储器

• 演变：磁芯-VLSI
• 寄存器：与CPU速度相同
• 高速缓存：备份主存中常用数据，减少访问主存，进程程序和数据访问时候才存放在主存中；按照缓冲行为单位存放在缓存中
• 磁盘缓存：将主存中的部分用作磁盘数据高速缓存，

程序的装入和链接

1. 编译：操作系统读取内核中的编译文件，将目标文件从磁盘（或者磁盘缓冲区）中-编译器（用户态进程）缓冲区（用户空间），CPU执行，从CPU读取文件
2. 链接：运行内核中的链接器代码，从磁盘中读取.o文件由链接器（进程）在内存中完成链接、重定位（相对地址统一成可执行文件的逻辑地址），生成可执行文件
   1. 静态链接：事先进行链接，不再拆开
      1. 修改相对地址，修改链接各模块的起始地址，统一为以可执行文件起始地址为0得逻辑地址空间
      2. 变换外部地址调用符号：变换为相对地址
   2. 动态链接：边装入边链接，：装入程序寻找对应模块装入内存。并修改相对地址
      1. 便于修改和更新
      2. 便于实现对目标模块的共享
   3. 运行时动态链接：将对某些模块的链接推迟到程序执行时才执行。发现被调用模块尚未装入内存中再由OS找到装入链接
3. 装入：装入程序装入内存，建立页表，分配页框、设置PC入口地址，最后CPU执行
   1. 绝对装入：程序装入地址在编译或者汇编时候给出，程序必须加载到指定地址 -编译时地址换算完毕
   2. 可重定位装入：地址采用相对地址 - 装入时候地址换算完毕
   3. 动态运行时装入：装入模块保持逻辑地址直到程序真正执行时进行地址转换，使用重定位寄存器进行支持实现，运行时候物理地址 = 重定位寄存器值 + 逻辑地址

连续分配存储管理方式

1. 单一连续分配：低字节给内核系统区，高字节给用户区
2. 固定分区分配：多道程序系统引入分区式内存管理
   1. 分区划分：分区大小相等：缺乏灵活性但较为方便使用；分区大小不等：划分成大小不同、数量不同的分区组
   2. 内存分配：分区按其大小建立分区使用表：程序装入时候内存分配程序根据程序大小检索分区表分配给该程序
3. 动态分区分配（可变分区分配）：
   1. 资源管理的数据结构 > 动态分区的数据结构
   2. 动态分区分配算法
      1. 基于顺序搜索的动态分区分配算法
         1. 首次适应算法（first fit，FF）：从链首起第一个大小足够的空间
         2. 循环首次适应算法（next fit,NF）:从上次找到的空闲分区的下一个空闲分区找到的第一个大小足够空闲分区
         3. 最佳适应算法（best fit ,BF）：将所有空闲分区按照容量大小从小到大排列，匹配第一个大小足够的空闲分区
         4. 最坏适应算法(worst fit, WF):优先使用最大空闲区
      2. 基于索引搜索的动态分区算法
         1. 快速适应算法(quick fit):空闲分区按照容量大小分类，每一类单独一个空闲分区索引表；分区归还使得算法复杂，
         2. 伙伴系统(buddy system):已分配或空闲分区按照2^k组成，每次在大小最小满足的序列中取分区进行分配
            1. 只合并大小相等的伙伴分区
      3. 哈希算法：减少空闲分区分类较细引起的索引开销，可以根据所需空闲分区大小直接计算出空闲分区链表地址
4. 紧凑与动态重定位：紧凑将小的空闲分区合并成大的分区，动态重定位进行紧凑时候只需要更改重定位寄存器中的值，同时拷贝进程内容到新地址，更新PCB中保存的重定位寄存器值，清除块表
   1. 动态重定位分区分配算法：动态分区分配算法增加紧凑后：当所有空闲分区均不满足，且总空闲分区大小满足分配时候触发

对换（swapping）

将内存中暂停的进程或程序、数据换出到外存中，将已具备运行条件（挂起的进程PCB等待的条件已经满足）的程序和数据换入内存

1. 对换类型：整体对换以整个进程为单位进行对换，页面（分段）对换实现对虚拟存储系统的支持
2. 对换空间管理：磁盘空间分为文件区和对换区
   1. 文件区：长时间在外存，提高文件存储的利用率，采用离散分配方式
   2. 对换区：存放从内存换出的线程，提高换出速度，其次考虑利用率，采用连续分配方式
   3. 采用空闲分区表和空闲分区链：包含对换区的首址和大小，使用盘块号和盘块数表示；
   4. 由对换进程实现进程的换出和换入（内核进程）
3. 进程换出
   1. 选择被换出的进程：优先选择阻塞或者睡眠进程，同状态进程优先级最低的先选择
   2. 进程换出过程：只换出非共享的程序和数据段
      1. 申请空间启动磁盘，先传送到磁盘上，再回收内存空间最后修改PCB和进程控制表等
      2. 持续换出直到无阻塞进程为止
4. 进程换入 - 定时执行换入操作
   1. 查看PCB中已经就绪但现在已换出的进程，并按照在外存驻留时间申请内存，申请成功直接换入，申请失败调用换出再换入进程
   2. 终止条件为内存中无就绪且换出或者内存不够换入停止

分页存储机制

允许进程分散装入不相邻分区 - 离散分配
**分页存储管理将用户程序的地址空间的固定页，内存空间的页框（物理块）

1. 分页存储管理

1. 页面：用户的页面（0、1）与内存的物理块（1#，2#），最后一页会有页内碎片
2. 页面大小取2的幂次，大小适中（1KB-8KB）
3. 分页地址结构组成：$$地址=页号P+位移量$$
4. 页表：每个进程一张进程映像表，存放进程地址空间的所有页，进程执行时候查表查找物理块号
5. [[资源管理的数据结构#地址变换机构：]]
6. 地址变换流程
	1. 地址变换机构拆分页号与页内地址
	2. 页号与页表长度比较，失败触发越界中断
	3. 未出现越界错误则相加在页表中查询物理地址，组合成物理地址
	4. 需要两次访存，一次查页表，二次访问数据
7. 快表 - 联想寄存器 TLB（translation Look aside Buffer） -位于MMU内部的高速缓存
	1. 存放当前访问的页表项，MMU与TLB先比较，如果有匹配的页号就访问快表减少一次访存；落空就需要访问页表同时更新快表
8. 访问内存时间计算：从发出地址请求到取出数据为止
9. **两级以及多级页表**：页表项中不存逻辑地址，逻辑地址由页表项的物理地址隐含；给离散分布的页表再建立一张页表储存其地址
	1. 新增状态位表明分页是否调入内存，运行内存的外层页表调入内存，页表只需要调入几页
	2. 多级页表将页表的页表再离散分布引入新的外层页表记录其地址
10. 反置页表
	1. 全系统一张，按照物理页框号索引判断物理页框占用情况，储存在内核空间，使用哈希查找，表项数目等于物理页框总数，只管理内存中的页框
	2. 页表项组成$$逻辑地址页号 + 进程号（PID）$$
	3. 外部页表使用传统的页表记录每个页在外存的物理位置

2. 分段式存储管理

程序逻辑上是分段，段是独立逻辑单位符合用户侧需求

1. 方便编程、方便描述共享区域（共享页的集合分段），信息保护（分段，权限控制）、动态增长、动态链接
2. 分段：每段进行命名，按照逻辑信息的分组分段；
3. 段表：记录每个段在内存中的起始地址和段的长度（寻址上限）；段表一般只有一张
4. 段表寄存器：存放段表始址和段表长度TL
5. 分段管理也可采用联想存储器（TLB）减少访存
6. 易于实现共享（页式共享需要描述共享区域使用需要页表项，段共享只需要一个段表项）

3. 段页式存储管理

• 包含段表和页表，段表中存放页表始址和页表长度
• 逻辑地址组成逻辑地址 = 段号 + 页号 + 页内地址
• 段号+段表始址-该段页表始址，页表始址+页号-物理块号

虚拟存储器

逻辑上扩充内存容量：传统的作业一次性调入，运行时长期驻留内存

• 程序执行时候大部分顺序执行
• 过程调用会使程序执行轨迹转至另一区域，调用深度不超过5：调用深度有限、调用有重复、调用的代码本身区域集中
• 程序中循环结构多次执行 - 时间局部性
• 对数据操作集中在小范围

缺页中断：

访问的页尚未调入内存触发缺页中断（MMU触发）

• 虚拟存储特征：多次性，对换性，虚拟性
• 虚拟存储都采用离散分配管理内存：原有的划分添加请求调动机制和置换机制之后形成
  • 页表项中新增：存在位（虚拟存储对换触发的开关）、访问位（供换入时候决定，一般只有1位，由硬件自动维护）、脏位（供换出的时候决定是否写回）、外存地址（该页在外存地址，实际上因为页表项大小有限才有复用内存物物理字段，两者互斥；多加一个字段present字段判断指向地址是在内存中还是在磁盘中；汤书中描述为同时存在外存和物理块号）、权限位
  • 缺页中断机构：硬件部分检测到PTE无效，CR2中保存出错的虚拟地址，保存对应错误码，CPU陷入内核，软件执行缺页处理程序
  • 地址变换机构：新增判断存在位、访问位、脏位、外存地址、全局位（可选） -相对于传统的映射同时存储状态
  • 请求分段系统：类似请求分页机制
• 缺页中断机制：
  • 在指令执行期间产生和处理中断信号
  • 指令执行期间可能产生多次缺页中断（需要嵌套状态）
  • TLB命中时候只修改TLB内部的A/D副本
  • 触发请求机制时候将TLB中A/D位同步到内存，脏页写回磁盘
• 内存分配：
  • 最小物理块数：保证进程正常运行的最小物理块数（必须覆盖一条指令执行过程中同时活跃的页），数据和地址各一块（指令长度小于两个字节），寻址存储：间接寻址新增间接地址页，二次间址+1块，以此类推为最小值
  • 物理块分配策略：
    • 固定分配局部置换：每个进程分配固定，进程置换在分配区域置换
      • 难以确定最佳分配空间
    • 可变分配全局置换：每个进程先分配一定物理块数，缺页时候从空闲队列或者全体中取出
      • 仅当空闲队列物理块用完OS才触发调出
      • 可能相互干扰、抖动扩散、公平性差
    • 可变分配局部置换：先分配一定物理内存，缺页时候从该进程物理页框中选择发生对换，系统检测缺页中断频繁就再分配，低则回收
      • 隔离性好
      • 公平
  • 分配算法：
    • 平均分配：每个进程平分
    • 按比例分配：按照进程大小分配
    • 考虑优先权的分配算法：一部分按照比例分配、一部分按照优先权分配
  • 页面调入策略
    • 预调页策略：将预计被访问的预先调入内存，用于第一次将进程调入内存时，采用工作集时候进程运行时候按照工作集调入
    • 请求调页策略：缺页中断的时候调入一页
  • 调入区域：文件区和对换区
    • 对换区域足够就只从对换区调度
    • 缺少对换区空间时候从文件区调入，换出的可能被修改的部分从对换区调入
    • UNIX方式：未运行过的文件区，运行过被换出对换区。共享的页面不触发调入，增加引用计数
  • 调入过程：程序访问触发缺页中断，中断处理程序保留CPU环境之后进行缺页中断处理
    • 内存足够直接调入然后修改页表
    • 内存已满则按照置换算法进行换出：如果所选页已被修改则写回磁盘
    • 调入内存修改页表项，并写入快表
    • 访问内存数据
  • 缺页率：总访问次数与需要从外存调入次数

页面置换算法

• 抖动：刚换出的页面很快又要被访问
• 置换的时候换出页刷新TLB中的状态：TLB中该页条目已经失效

1. 最佳置换算法（Belady算法）：理想化算法，有最好的性能，实际上无法实现
   1. 先淘汰后面永不使用的，或者最长时间不再被访问的页面
2. 先进先出页面置换算法（FCFO）：优先淘汰最先进入内存的页面：选择在内存中驻留时间最久的页面淘汰；设置替换指针指向最老页面
3. 最近最久未使用算法（LRU：least Recently Used算法）：根据页面调入内存后的使用情况决策，采用最近的过去作最近的将来近似
   1. 优先淘汰最久未使用的页面
   2. 需要硬件支撑：需要较多硬件支撑，一般采用LRU的近似
      1. 寄存器类：每个内存中页面对应一个寄存器，当最近访问的时候寄存器最高位置1，定时右移，
      2. 栈类：采用特殊栈，每次访问移动到栈顶
4. 最少使用最欢算法（least Frequently Used,LFU）：对移位寄存器按位求和，取和最小的为最少使用，进行替换
   1. 因为采样频率的原因实际上只是判断了在每个时间段是否访问，而不是访问次数
   2. 与LRU复用结构
5. Clock算法（NRU：not recently Used算法）：循环检查访问位和修改位
   1. 改进型Clock算法：新增置换代码，同时检查访问位A和修改位M：
      1. 第一步淘汰A=0，M=0，寻找有无，有就进行替换，没有就不进行变化
      2. 第二步淘汰A=0，M=1；同时针对选中之前的A=1的进行清零；
      3. 可淘汰的都是A=0的，A=1的都在第二轮进入A=0的状态才可能清零
      4. 实现算法开销有所增加。扫描次数可能增加
   2. 页面缓冲算法（Page Buffering Algorithm,PBA）:页面已换出未写回， -后台回收路径使用：系统内存低于水位线唤醒、系统定期扫描不活跃页、进程被挂起
      1. 建立已修改换出页面的链表，当换出数目达到一定值时候再一起写回磁盘
      2. 读入内存：在涉及读已修改换出链表页面的时候可以直接从链表中获取
      3. 情形：当整个进程被挂起的时候为了加快换入进度，部分页暂留内存
      4. 使用空闲页面链表 - 换出的未修改页面优先挂载到队列末尾，取的时候不用进行访存‘修改页面链表 - 修改的页面放出时候挂载末尾，
6. 访存时间计算 - 带上缺页中断机制
   1. TLB中有，页本身在内存中：一次
   2. TLB中无，页本身在：两次访存（一次访问页表，一次读取数据） + 更新快表时间 + 查询快表失败的时间
   3. 被访问页不在内存中：TLB时长+查找页表时长+处理缺页中断时间 + 更新快表时间 + 访问实际物理地址时间
7. 抖动与工作集
   1. 抖动是因为分配给每个进程的物理块不能满足进程运行基本要求
   2. 老化算法：n位寄存器，每个时钟中断右移一位
   3. 工作集：由局部性原理，对于页面的访问集中且不均匀，在固定的时间间隔力，进程实际要访问的页面集合
      1. 仍然使用过去某段时间的行为作为将来的近似
      2. 不同时间t的工作集大小不同，是时间与窗口大小的二元函数，是窗口尺寸的非降函数
   4. 局部置换：进程只能在自己内存空间进行置换 限制抖动的影响范围
   5. 引入工作集算法：进程在最近的时间段内访问过的页集合（工作集W(t,Δ),从到t时刻为止Δ宽的时间段中访问页集合），实际分配大于等于工作集即稳定，小于等于就抖动
      1. 处理机利用率也采用工作集后，则调度程序新增程序之前先评估已有进程的驻留内存是否满足工作集，都已满足再考虑新增作业
   6. L=S准则（缺页之间的平均时间(触发两次缺页之间进程执行时间，即缺页的频率) = 平均缺页服务时间（从磁盘读入页的平均时间））
   7. 选择暂停程序：程序数量偏多的时候按照调度策略选择优秀级低的策略暂停进程（挂起） - 释放内存压力

请求分段存储管理

• 硬件支持：请求段表，存在访问位、修改位、存在位、外存始址（外存中的始址：起始盘块号）、存取方式（实施权限保护）、增补位（表示本段运行时候是否动态增长过）
• 缺段中断机构：类似缺页中断
• 地址变换机构：新增缺段中断的请求和处理：先处理越界再处理保护中断（内核中的段表），最后进行缺段中断处理
• 共享段表：系统中的共享段表 - 内存、位置信息等仍然记录在每个进程自己段表项中，共享段表额外记录共享计数和各进程的存取权限等管理信息
  • 表项：共享进程计数、存取控制字段、段号（不同进程段号不同）
  • 按照共享标志位，当判定当前进程为共享段的时候查共享表中计数，删除当前进程信息，清除当前进程的占用，减去共享计数
  • 调用共享的时候共享段表中新增信息，计数+1
• 分段保护：
  1. 越界检查：越界中断
  2. 控制信息检查：保护中断
  3. 环保护机构：权限分级机制，OS核心位于0环，低环高优先级
     1. 程序可以访问相同环或者外环的数据
     2. 程序可以调用相同环或者内环的服务
     3. 外环到内环必须通过调用门、中断门、陷阱门
     4. 日常一般采用0、3两个层级（内核和guest）

第四章 文件管理

文件基本属性

文件是具有相同文件名的若干元素的集合

• 数据项最基层数据结构：基本数据项用于描述对象属性（基本数据项名字+类型定义格式）的值；基本数据项组合
• 一组相关数据项集合组成记录，关键字一般为一个，也可能为几个数据项组合
• 文件组成：创建者定义、具有文件名的一组相同元素集合
  • 有结构文件：由记录组成
  • 无结构文件：字符流
  • 文件属性：
    • 文件名和扩展名：禁止特殊字符作为文件名；扩展名即是后缀名，指示文件类型
    • 文件类型：
      • 按照用途划分：系统文件（最多允许用户调用）、用户文件（用户委托系统保管）、库文件（允许调用，不允许修改）
      • 按照数据形式划分：源文件（输入的源程序和数据形成的文件）、目标文件（只有节头表，编译过后，但没有链接的文件，.obj文件）；可执行文件（补充了程序头表，编译文件链接后可直接执行的文件,.exe）
      • 按照组织形式和处理方式划分：普通文件、目录文件、特殊文件（系统中的各类IO设备，按照unix一切皆文件思想被视为文件，只是对其操作需要设备驱动程序完成）
    • 文件长度，文件物理位置，文件建立时间
  • 文件系统分层：自底向上
    1. 对象及属性层：实际存储的模式，包含文件，目录，磁盘存储空间
    2. 对对象操纵和管理的软件集合：
       1. 对文件存储空间管理
       2. 对文件目录管理
       3. 文件的逻辑地址与物理地址之间转换
       4. 对文件读写管理
       5. 对文件的共享与保护
    3. 文件系统接口：
       • 命令接口：
       • 程序接口：
  • 文件系统相关软件分层：
    • IO控制层：磁盘驱动等，负责实现磁盘文件的具体读写
    • 基本文件系统层：内存与磁盘的数据块交换
    • 基本IO管理程序：磁盘IO相关的事务，逻辑地址转换，管理空闲块，缓冲的指定
    • 逻辑文件系统：处理和记录针对文件的操作及保护

基本文件操作

• 创建文件：分配外存空间，创建目录项，
• 删除文件：删除目录项，回收文件占用存储
• 读文件：根据文件名查目录-按照目录所给位置，目录中指针对文件进行读
• 写文件：根据文件名查目录-目录项中目录项-写指针开始写操作
• 设置文件读写位置：设置目录项中读写指针位置
• 打开和关闭文件：
  • 避免多次重复检索目录；请求文件时候使用open系统将至指定文件的目录中属性拷贝到内存打开文件表中，使用打开文件表的编号（索引号）取代直接指向磁盘中的目录项
  • 关闭指令只需要删除打开文件表中的项
• 其他文件操作：
  • 更改文件属性：操作目录项中的数据，更改对应文件的
  • 操作目录：创建、修改、删除、改变切换目录
  • 实现文件共享的系统调用
  • 对文件系统进行操作的系统调用

文件逻辑结构

• 逻辑结构：文件组织，将逻辑记录组成文件
  • 有结构文件（定长与变长记录）与无结构文件（一个记录中仅有一个字节）
  • 按照属性划分：
    • 顺序文件（记录按顺序排列）：串结构（按照存入时间先后排序）与顺序结构（用户指定的关键字，所有记录按关键字排序），顺序文件可引入查找算法
      • 增加或删除数据需要挪动的记录比较多，比较困难；配置对应的运行记录文件（事务文件），将修改记录其中，每隔一段时间将该文件与原文件合并
      • 记录文件寻址：隐式寻址（访问一个指定记录，必须访问它前面的n个数据）；显式寻址（实现直接随机访问，记录整型标识，可以一次性计算指定记录的地址；或者使用关键字进行从第一个开始的比较）
    • 索引文件（每个文件一张索引表，每个记录有对应的索引：包含地址首址和记录长度）；将顺序查找文件改造成可随机查找；通过增加存储开销减少时间开销
      • 索引表本身按照关键字排序，定长；可以随机检索（使用折半查找）
      • 每当增加记录时候需要修改索引表
      • 可以根据不同的关键字配置多张不同关键字的索引表
    • 索引顺序文件（每个文件一张索引表，每组记录中的第一个记录一个索引）：顺序文件（原文件本身按照关键字排序）引入文件索引表，实现随机访问；引入溢出文件：记录新增加的、删除、修改的记录
      • 一级索引顺序：文件中的记录分组，每组对应一个索引项（记录组中第一个记录的关键字和指针）、
      • 两级索引顺序：两级划分。每级平均查询次数一致
      • 最优分组大小是\sqrt{N},查分组所有次数与分组内所有次数一致
    • 直接文件：根据给定关键字可以直接获得指定记录的物理地址，关键字本身决定了物理地址；
      • 键值转换：由关键字直接到记录物理地址
      • 哈希文件：Hash散列函数直接将关键字转为相应的地址，
        • 优化后Hash函数指向目录表中相应表目的指针
        • Hash函数是标准函数，存取系统可以随时调用
• 物理结构：如何将文件储存在外存中

文件目录

• 实现按照名字存取：
• 提高对目录检索速度
• 文件共享
• 允许文件重名
• 资源管理的数据结构 > 索引结点
  单级目录：整个文件系统只建立一张，每个文件一个目录项；不划分索引节点 ；只实现了按名存取
• 建立新文件必须检索当前目录下所有文件名，确保唯一就占用新的目录项填入并新占
• 查找速度慢，不允许重名
• 不便于实现文件共享：所有用户只能使用同一名字访问同一文件
  两级目录：
• 每个用户单独的目录（User File Directory）：每个用户单独建立一个单独的用户文件目录；由用户所有文件文件控制块组成
• 系统建立用户目录的目录（Master File Directory）:每个用户目录文件占有一个目录项，包括用户名和指向用户目录的指针
• 可以提高检索速度，将原本的O（MU）的检索空间变为O（M + U）的检索范围
• 不同的目录中，可以使用同名文件
• 不同用户使用不同的文件名访问同一个共享文件
  树形目录：
• 主目录即根目录，每个文件和每个目录都只有一个父目录。
• 数据文件为树叶
• 统一化目录项：目录文件和数据文件的FCB统一作为FCB，通过FCB中状态标识
• 路径名和当前目录
  • 路径名：每个数据文件从根目录到具体文件名的通路唯一
  • 当前目录：每个进程设置当前目录，进程对文件访问相对于当前目录进行；路径名从当前目录开始，逐级经过目录文件到达数据文件；即相对路径
    目录操作：创建目录，删除目录，不删除非空目录（递归删除）、可删除非空目录、改变目录（切换当前目录）、移动目录、链接操作、查找操作
    目录查询计数：按照文件名找到FCB或者incode节点
• 线性检索法：顺序检索法，按照用户文件名，顺序查找目录项；
  • 文件路径名按照分量划分，依次检索
• hash方法：系统利用用户提供别的文件名变换为索引值，直接按照索引值寻找
  • 含有通配符的文件名无法使用hash查找
  • 哈希冲突处理规则：
    • 利用哈希索引查找目录时候，目录表中目录项为空，则表示空；不匹配则哈希值+常数（与目录长度互质），形成新索引查找

文件共享

• 多个用户或者进程共享同一份文件，系统中只保存一份副本
• 基于有向无环图共享：允许一个文件有多个父目录，但之间不构成环
  • 文件目录中包含文件的盘号（物理块号），每个父目录单独一个文件目录
  • 新增加的盘块只会出现在执行了操作的目录中
• 索引节点法：文件目录中只设置文件名及指针
  • 采用链接计数表示共享用户数量
  • 采用索引节点统一记录文件内容的变化
  • 划分文件主与共享者：即使文件主删除文件（逻辑删除）依然不会放弃该字段；
• 符号链接（Symbolic Linking）：文件拥有一个主父目录，其他几个父目录只是符号链接共享，没有在索引中体现
  • 类似系统快捷方式，在需要共享的文件下创建link类型的新文件
  • 只有文件主拥有指向索引节点的指针，其他用户只拥有路径名
  • 其他共享用户调用相当于访问一个指定路径的文件，文件主删除后自动触发访问失败自我删除
  • 每次访问该符号链接可能都需要读盘重新获取索引节点
  • 链接本身是一个文件，本身也需要配置对应的索引节点
• 每个共享文件拥有多个文件名，储存在磁盘的时候会出现因为不同名出现多次拷贝

文件保护

• 危险：人为因素（危险操作），系统因素（系统故障丢失数据），自然因素（磁盘数据会逐渐消失（物质世界的熵增））
• 存取控制系统：控制操作权限，减少人为因素
  • 保护域与访问权概念：
    • 访问权：对系统中的对象保护，进程对某对象执行操作的权力，采用有序对表示进程对对象的权力（对象名，权集），例如（F1，R/W）
    • 保护域：对系统中的资源；是一组对象访问权限（访问权）的集合，
    • 进程和域一一对应：静态域，在整个生命周期中可用资源；动态域：一个进程多个域，每个运行阶段一个域；使用保护域切换在不同运行阶段进行不同保护域的切换；系统调用或特权指令可以变化保护域
  • 访问矩阵：使用矩阵描述的系统的访问权限控制，由资源的拥有者和管理者决定访问矩阵中的访问权，新增文件时候新增一个文件，并分配它在每个域内的权限
    • 具有域切换权的访问矩阵：
    • 将切换本身视作一种权力进行分配；描述当前的进程允许切换到域 -S
    • 修改访问矩阵-拷贝权（已有的访问权控制扩散，Copy），将某个域的访问权扩展到同一列的其他域中 - * 表示访问权，类似R^{*},表示当前域内进程可以将该权限同步给其他域
    • 所有权（访问权从无到有的新增或者删除，Owner）：所有权（O）所在域可以删除或者新增其他域针对该资源的访问权，能控制异权限修改
    • 控制权（Control，用于改变指定域中进程对不同对象的访问权）：当前域能是否能分配其他域的权力，决定域跟谁管，同样能分配异权限修改
    • 理论访问矩阵中的表项太多，处理下来是稀疏矩阵（行列都可能稀疏），因此将其按照列或者行拆分
      • 访问控制表（ACL，按列划分）：描述当前对象允许的域及对应权限集合；不保存空项，存放在文件控制表，或者文件的索引节点（文件侧）；作为文件的控制信息（PCB）
        • 域可以与用户对应也可以与进程对应
        • 可设置定义缺省的访问全集（权限初始化）
      • 访问权限表（Capabilities，按行划分）：描述当前域对每一个对象执行的操作表
        • 访问权限表安全是保护对象安全的前提，其不允许直接被用户访问，储存在系统区的专有区内
    • 第一次访问查访问控制表，有权限则在访问权限表中新增权限
      • 避免能力扩散的撤销或删除：设置认证介质存储在对应能力表或者设置有效时间（过期需要重新进行ACL校验）
• 系统容错技术：系统故障可以根据备份重启
• 建立后备系统:

文件系统

文件物理结构与外存的组织方式相关

文件物理结构与外存组织形式

• 连续组织：文件分配的盘块相邻，文件物理地址只需要记录第一个盘块号和文件长度（盘块号）
  • 可能会存在外存碎片，需要通过紧凑处理
  • 顺序访问容易，顺序访问速度快；分配文件存储时候必须事先知道文件大小（难以预估，动态分配的分配空间也麻烦），插入和删除记录麻烦；
• 链接组织：文件装在离散的盘块中，每个盘块链接指针构成链表
  • 磁盘外部碎片减少
  • 插入、删除、修改记录容易
  • 适应动态增长
  • 隐式链接：每个目录项中包含同时指向最开始和最后盘块指针；每个盘块中存储下一个盘块物理地址
    • 盘块组成簇（cluster，）：按照簇为单位进行盘块分配
  • 显式链接（文件分配表法FAT，File Allocation Table）：将每个文件组成一个物理链存储，FCB存文件首地址，FAT存储每个链的具体分配
    • 链接文件各个块的指针集中存放内存（启动之后常驻内存，本身放在外存）中的一张链接表；表序号是物理块号，每个表项中只放下一个盘块的链接指针（物理块号，同时是内存的相对地址）；每个文件的第一个文件地址作为文件地址放在FCB中；
  • FAT格式：占用较大的内存，文件块号随机分配，空间局部性不够良好
    • 安全起见FAT实行备份，分为FAT1和FAT2
    • FAT中的卷：物理磁盘集合划分的逻辑磁盘集合，每个卷能单独格式化并供文件系统使用；每个卷单独区域存放目录和FAT表，以及逻辑驱动器名称
    • FAT12：盘块地址为12位，块内地址一般为9位，存储大小为21位 =2MB*4(分区数)
      • 引入簇后，按照簇进行地址划分，一个簇可能9位，10位，11，12位，容量扩充完成
      • 2^12位编码空间中存在特殊值：000空闲；001保留；FF0-FF6保留，FF7表示坏簇，FF8-FFF文件结束，只有4096-2-16 = 4078个有效地址
      • 减少FAT表中占用存储空间，增大了簇内零头
      • FAT12只能支持短文件名，8+3格式的文件名
    • FAT16：表项长度增加到16位
      • 编码空间的特殊值：0000空闲，0001保留，FFF6保留，FFF7坏簇，FFF8-FFFF文件结束，共有 65536-2-11 = 65523个有效地址
    • FAT32：表项长度增加到32位；同时支持长文件名，节省硬盘空间；降低了运行速度，
      • 高四位保留不用
      • 有最小管理空间限制：至少需要位簇号
  • NTFS：
    • 64位磁盘地址：以簇为磁盘空间分配和回收单位；每个簇只属于一个文件；NTFS具有与磁盘物理块大小无关独立性；把卷上簇的大小称为卷因子，簇的大小在低级格式化的时候就确定（512B-64KB），1GB大小磁盘簇大小1KB，2GB磁盘对应4KB；大部分情况下可以直接取4KB
      • 逻辑簇号（LCN）和虚拟簇号（VCN）：LCN以卷为单位，每个卷中簇简单编号；VCN以文件为单位，属于某个文件簇按照顺序编号，知道开始簇地址，就将VCN映射到LCN
      • 主控文件表（master File Table,MFT）:一个文件，将一个卷中所有文件信息、目录信息以及未使用空间记录；每个文件作为一个记录占一行，包括MFT自身文件；每行大小固定为1KB；称为对应文件的元数据（metadata，文件控制字）；
      • 将文件不能容纳的属性记录到卷中其他可用簇中，将簇按照记录文件属性分类，分别链接到多个队列，储存对应队列指针到元数据中（一个属性树，每个节点分别存放一个MFT表项描述属性，具体数据在MFT中通过指针指向）
      • 元数据中尽可能多存储文件信息：当文件较小时候直接文件内容存储到元数据中，文件较大使用元数据中指向文件DATA属性的队列指针找到对应的簇；通过run_list描述每段连续的存储
      • 系统兼容性不足：NTFS文件不能被FAT等存储，之前的windows系列也不兼容NTFS系统
    • 支持长文件名，最长为255个字符，全路径名32767
    • 具有系统容错功能，差错可以自我纠正
    • 保证系统中数据一致性
• 索引组织：方便高效的直接存取，打开文件时候只需存储文件占用盘号编号（将每个文件所对应的盘块号集中存放，访问对应文件时候调用文件对应盘块号入内存）
  • 不会产生外部碎片
  • 每建立一个索引文件，该文件需要分配索引块记录所有盘块号；对于小文件索引块利用率低
  • 采用多级索引组织形式，储存索引块的索引加快了对大型文件的查找，缺点是访问一个盘块时候启动磁盘次数随着索引级数的增加而增多；
  • 增量索引：将多级索引中不必放入树底层的节点向上收缩，减少整体的访问代价
    • 小文件占用块小，将每个盘块地址直接放入文件控制块
    • 中等文件单级索引
    • 大文件才使用两级或者三级索引
  • UNIX system V组织：索引节点中有13个地址项，前十个个地址项指向直接地址，一次间接地址则在之后再加一个地址使用，二次间接地址就再增加一个地址用于二次间址，三次间址则使用最后一个地址项

文件存储空间管理

存储空间的基本分配单位是磁盘块

1. 空闲表法：为外存所有空闲区建立一张空闲表，使用空闲表项描述表项序号，空闲区起始盘号，空闲盘块数；按照起始盘块号次序排列
   1. 采用首次适应算法和最佳适应算法等进行分配：顺序检索空间表的各表项，找到第一个符合要求的空闲区进行分配；在外存中为了提高分配速度，减少IO访问频率，仍可以采用连续分配（针对较小文件以及多媒体文件 -减少寻道时间），
2. 空闲链表法：空闲盘区拉成空闲链，根据链的元素不同分为空闲盘块链和空闲盘区链
   1. 盘块链：只考虑分配数量，不考虑临近分配；分配和回收简单但是效率较低
   2. 盘区链：空闲分区成链，分配和回收复杂但效率较高
3. 位示图：二进制的01表示盘块使用情况，
   1. 分配：
      1. 顺序扫描，找出一个或者一组值为0的二进制
      2. 将二进制转为对应盘块号，
      3. 修改位示图，占用
   2. 回收：将盘块号转为行列号，按照行列号进行置零
4. 成组链表法：适用于大型系统，属于临界资源加锁进行保护
   1. 空闲盘号栈：成组的空闲盘块，存放当前可用的一组空闲盘块和栈中尚有的空闲盘块数；空闲盘块分组，每组设置最大大小
   2. 将每一组的盘块总数和该组所有的盘块号存放在栈底指向的链块中，每次到栈底的同时就将指向的块中储存的空闲盘块组和数量读入栈，之后空闲块再分配
   3. 释放块的时候如果栈满，就将栈的整个信息写入栈顶指向的块中，并将该地址写入栈底，空闲盘块大小重置为1
   4. 最后一组只有99盘块，S.free(0)中储存0作为结束标志

虚拟文件系统 - VFS

位于内核中的抽象层，用统一的超级块、innode、dentry、file抽象文件系统
dentry描写当前目录项，vfsmount描写当前文件系统实例

• 虚拟文件系统在内核启动时候进行初始化，建立核心数据结构
  • 文件系统类型列表：记录已注册的文件系统类型
  • 挂载链表：记录已挂载的文件系统实例；路径解析时候如果能查到就调用查找挂载
• 文件系统驱动加载时候向VFS注册自己的类型（文件系统注册）
  • 文件系统名
  • 调用函数（mount）
  • 卸载调用函数
  • 标志位
• 挂载文件系统：VFS根据文件系统拿到mount函数，读入磁盘超级块 - 针对VFS接口的底层实现
  • 分配vfsmount结构
  • 分配或者找到挂载点
  • 建立挂载点与新文件系统根的联系
  • 将vfsmount结构挂入挂载链表
  • 每次路径解析遇到挂载点就dentry切到子文件系统系统根，vfsmount切换到子系统的函数
• 超级块：已挂载的文件系统，描述文件系统全局信息
  • 块大小、根inode、操作表
  • 从磁盘超级块读入
• 索引节点：描述一个文件，每个文件一个，存文件的元数据（大小、权限、时间、数据位置），从磁盘中复制
• 目录项：路径名到innode的映射，由名称定位到控制信息
• 文件：描述一个打开的文件
• 文件系统挂载(mounting)：将一个文件系统接入目录树，挂载点成为新文件系统入口

提高磁盘IO速度途径

• 改进目录结构或者查询方法
• 选取好的文件存储结构
• 提高磁盘的IO速度：目前远低于对内存的访问速度，低4-6个量级
  磁盘高速缓存（Disk Cache）：在内存中为磁盘盘块设置副本，访问磁盘请求时候先查缓冲器
• 数据交付方式：数据交付，将缓存数据传到请求进程；指针交付将缓冲区指针传给请求者进程
• 置换算法：访问频率等于对IO频率；数据块访问部分可预见，数据一致性确保
  • 将缓存区看成一条LRU链，影响数据一致性的和预见使用频率不高的块往前靠；使用频率高的放尾部
  • 周期性必须会写磁盘避免长时间的数据丢失：使用修改程序定时强制写回所有已修改盘块数据（自动保存机制）
    -其他方法：
• 提前读：预知访问的盘块提前放入缓冲区（顺序访问）
• 延迟写：数据修改不立即写回磁盘
• 优化物理块分布：减少磁头移动距离
• 虚拟盘：即RAM盘，使用内存空间模拟磁盘（RAM）：允许使用磁盘操作访问对应内存；但虚拟盘容易丢失数据，一半只用于存放临时数据
  • 虚拟盘中的数据由用户完全控制，磁盘高速缓存的内容由OS控制
• 廉价磁盘冗余阵列（RAID）：复用多个相同组件大幅度提高性能，大幅提高了磁盘的IO速度和磁盘系统的可靠性。类似多处理机，多核芯片的原理
  • 磁盘阵列控制器：统一管理和控制一组磁盘控制器，组成大型磁盘系统；
  • 并行交叉存储：将每一个盘块数据分别存储到不同磁盘中的相同位置；传输数据的时候每个盘块的子盘块同时传输（每子盘存储原始1/N的数据）
  • RAID分级：条带化：连续数据分散到多盘；镜像：每块盘存完整副本；校验：奇偶校验，检验分散：避免专有校验盘瓶颈
    • RAID0级：实现数据分割， - 条带化
    • RAID1级：增加磁盘镜像功能：每个子盘镜像一份；确保可靠性，但空间利用率降低为原始的一半 - 条带化 + 镜像
    • RAID3级：只使用一台奇偶校验盘进行数据校验，其他盘作为数据盘，利用率（N-1/N） -- 条带化 + 专用校验盘
      • 主轴同步：所有盘旋转相位一致
    • RAID4级：一个逻辑块完整存储在一块盘中，固定一个校验盘；一个IO请求一般涉及一个盘，其他盘可以同时请求服务；坏盘可以通过校验盘修复
      • 每次写都需要更新专用校验盘，校验盘成为写瓶颈
    • RAID5级：将校验信息分散，不存在校验盘限制传输速率，校验数据螺旋散步所有数据盘 - 分布式奇偶校验；条带单位是逻辑块；校验块和数据分散都是逻辑块分布
    • RAID6级：双校验，可以容忍两块磁盘故障
    • RAID7级：架构升级，每块磁盘独立缓存，实时操作系统管理，异步IO
  • RAID除了0级别以外可靠性高，有容错，磁盘IO速度提高；性能/价格比高

提高磁盘可靠性方法

• 磁盘容错技术（系统容错技术SFT）：系统中设置冗余部件，增加冗余磁盘冗余磁盘控制器等方法提高磁盘系统可靠性
  • 低级磁盘容错技术：双份目录、双份文件分配表以及写后读校验
    • FAT及目录备份
    • 热修复重定向：将磁盘的一小块区域作为热修复重定向区，当磁盘有缺陷时的待写数据临时写入，并对写入数据进行登记
    • 写后读校验：每次写入一个数据块后再次读入缓冲区与仍未释放的数据进行一致性校验，不一致就写入热修复重定向区
  • 中级磁盘容错技术：防止磁盘驱动器和磁盘控制器的系统错误
    • 磁盘镜像：同一磁盘控制器下，设置备份的磁盘控制器；每次写入同时执行两个磁盘驱动器写入磁盘和备份磁盘
    • 磁盘双工：备份磁盘控制器，从磁盘控制器开始分裂；每次磁道控制器有独立通道与主存通信，可以并行写入读出数据
  • 系统容错技术：基于集群的容错功能，；对称对台处理机（SMP）实现集群系统的服务器
    • 集群：一组互连的自主计算机
    • 双机热备份系统：备有两台服务器，主处理机故障从服务器接替，修复后的服务器作为备份
    • 双机互为备份：两台服务器各自完成任务，任务同时传输两组，服务器选择完成一组，另外一组在故障时候才执行；
    • 公用磁盘模式：多台计算机连接到公共磁盘
• 后背系统：将暂时不需要但仍然有用的数据存放在后备系统（磁带机、磁盘机、光盘机）
  • 磁带机：只适合顺序文件。容量大，速度较慢
  • 硬盘：移动磁盘速度高、脱机保存方便、保存时间较长；固定硬盘启动器：将系统备份，彼此分出一块区域作为另一硬盘的拷贝区
  • 光盘驱动器：只读光盘CD-ROM和DVD-ROM只能读不能写不能做后背
    • 可读写光盘驱动器，刻录机作为后背系统（刻录CD和DVD）

数据一致性控制

• 事务：全部完成才能托付，一个失败就执行夭折（回滚、取消）；
• 事务记录：放在稳定存储器中记录事务运行时数据项修改的全部信息，即运行记录（Log）
  • 事务名
  • 数据项名
  • 旧值
  • 新值
• undo操作：设置所有值为旧值，没有托付操作的事务执行redo
• redo操作：设置所有值为新值，完成托付操作的事务执行redo操作
• 检查点：进行截断，只需要针对检查点之后的事务操作进行redo和undo操作
• 并发控制：使用互斥锁实现顺序性或者利用互斥锁和共享锁（允许并行读，不允许任何写）实现顺序性

第五章 输入输出（I/O）管理

功能模型

• 方便用户使用IO设备：
  1. 隐藏物理设备细节：不同设备有响应的设备控制器（包含命令寄存器（存指令）和类数据寄存器（存参数）），通过对设备抽象向上层进程提供少量抽象读写命令
  2. 与设备的无关性：上层程序不依赖具体物理设备（用户可以使用抽象的逻辑设备名使用设备），有个；有效提高OS的可移植性和易适应性
• 提高CPU和I/O设备利用率：
  1. 提高处理机与IO设备利用率：尽可能让处理机和I/O设备并行操作；处理机能快速响应用户的I/O请求，使IO设备尽快运转，减少IO设备运行时处理机的干扰
  2. 对IO设备进行控制（驱动程序的功能）：采用轮询；采用中断；直接存储器访问；采用通道
• 为用户共享设备时候提供方便，系统发生错误时候及时发现并修正错误
  1. 确保对设备的正确共享：独占和互斥设备
  2. 错误处理：临时性错误重试修复，持久性错误上层报告
     1. 低层能解决的就低层解决，不能再进行上报
• I/O软件层次：
  • 用户层IO软件：
  • IO系统接口
  • 设备独立性软件：
  • 设备驱动程序：具体实现系统对设备发出的操作指令，驱动IO设备工作的驱动程序
  • 中断处理程序：保存被中断进程的CPU环境，转入相应的中断处理程序，处理完毕恢复中断进程现场，返回被中断进程
  • RW/RH接口
  • 设备控制器
• IO系统接口：按照设备类型划分
  • 块设备接口：磁盘和光盘使用，数据存取和传输以数据块为单位；传输速率高、可寻址，
    • 磁盘中使用DMA方式
    • 隐藏磁盘中的二维接口：将磁盘的二维结构（磁道、扇区）转为块号
    • 将抽象命令映射为底层操作：抽象命令转为具体指令
  • 流设备接口：字符设备（数据的存取和传输以字符为单位、传输速率较低、不可寻址（不能指定数据的输入源地址和输出的目标地址））接口，用于控制字符设备的输入与输出
    • 采用中断驱动方式，采取队列进行顺序存取
    • in-control指令：通过参数配置与剧吐设备相关的功能
    • 大多数独占，互斥共享；通过打开和关闭实现互斥
  • 网络通信接口：提供相应的网络软件和网络通信，使计算机可以通过网络与其他计算机进行通信和上网浏览
• IO系统层次：自底向上
  • 中断处理程序
  • 设备驱动程序
  • 设备独立性软件

具体IO设备与设备控制器

• 执行控制IO的电子部件称为设备控制器或适配器（adapter），可以是印刷电路卡形式（控制卡、接口卡、网卡）
• 分类划分：
  • 使用特性划分：存储设备（容量大，专注存储）与IO设备（输入、输出、交互）
  • 按传输速率分类：低速、中速、高速

设备与控制器之间接口：

• 数据信号线：传输数据到缓冲器，到达一定数量后从缓冲区传输到设备控制器
• 控制信号线：设备控制器向IO设备发送具体控制信号
• 状态信号线：传送当前设备状态到计算机

设备控制器：

OS中描述的设备控制器默认指主机侧控制器，不是设备内部的控制器，设备内部控制器属于设备硬件细节
控制IO设备实现IO设备与计算机之间的数据交换，可编制（分配物理地址成为物理地址空间的一部分-MMIO区域）
- 由向上接口（与计算机）、向下接口（与设备）、IO逻辑（翻译并执行处理机发送的命令）
- 接收和识别命令：将处理器发送命令转化
- 数据交换：实现CPU与控制器、控制器之间的数据交换，通过内置数据寄存器
- 标识和报告设别状态：内置状态寄存器
- 地址识别：设备控制器能识别所控制的所有设备的地址、所有寄存器地址，地址译码器
- 数据缓冲区：
- 差错控制：通过差错控制检测码向CPU报告错误，CPU重传

• 内存映像IO：
  • 原本：利用特定IO指令：访问内存和访问IO设备的指令不一致
  • 不再区分内存和IO设备提供的物理空间地址，统一编制
• IO通道：建立独立IO操作，将CPU中的任务剥离，使CPU尽量专注数据处理，通道其实就是一种特殊的处理机（没有内存以及其指令类型单一），有自己的指令寄存器和译码器
  • 将CPU不核心的任务卸载给专用的处理机（类似GPU、TPU的思想，让CPU回归通用逻辑控制）
  • 接收指令中的任务地址和启动信号、执行通道程序
  • 字节多路通道：字节交叉方式工作，每个子通道轮流与主通道进行通信，不适于连接高速
  • 数组选择通道：只含有一个分配型子通道，以数据块为单位，选择一台设备独占传输
  • 数组多路通道：多个非分配型子通道，
  • 瓶颈问题：通道价格昂贵，多对一效率不够高，改成多对多的形式，充分利用空闲的通道、存储器
• 中断机构与中断处理程序（中断服务程序ISR）：中断与陷入按照是外部IO设备还是CPU内部事件划分
  • 中断处理序在驱动程序中，由中断向量表中指向，每个设备不同的中断请求信号对应不同的中断处理程序，中断控制器实现中断号与处理程序的映射
  • 多中断源同时发生：屏蔽中断（关中断）和嵌套中断（开中断，高优先级中断允许中断低优先级请求）
  • 中断处理程序处理过程：
    • 检测是否有未响应的中断信号 - 处理机测试
    • 保护被中断进程的CPU环境 - 硬件保存恢复到当前进程所需环境（处理机状态字、下一条指令地址）；软件保存CPu现场信息（压入中断栈中）
    • 转入相应的设备处理程序。 - 处理机发送确认信号后设备撤回请求信号，得到中断处理程序入口地址放入IR中
    • 执行中断处理程序
    • 恢复现场退出中断

设备驱动程序：

接收上层的抽象IO要求转换为具体要求发送给设备控制器启动设备执行；设备控制器发送信号传给上层；每一类设备配置一类驱动（按照逻辑设备划分）

• 接收上层控制信号，抽象要求转为设备的低指令序列：只有驱动程序同时了解抽象要求和寄存器情况
• 检查用户IO请求合法性：传递参数，设置工作方式；
• 发出IO命令：设备空闲（状态寄存器中的状态位）直接启动设备，设备忙碌支持请求块挂在设备队列等待
• 及时响应中断，调用对应中断处理程序
• 特点：不同类型的设备驱动不同，相同类型的可以驱动相同；常用中断和DMA方式，其中部分必须使用汇编编写；允许可重入
• 设备配置进程：一类设备一个进程；输入输出专门进程；不设置专有进程

对IO设备的控制：

尽量减少主机对IO控制的干预；

• 轮询：处理机向控制器发指令，设置状态寄存器中状态位为忙碌，不断循环测试是否IO操作结束（状态位修改回去），处理器就从数据寄存器中取数据，送入内存
• 中断：额外增加一条中断信号通知机制，设备主动发送信号，CPU被动响应。 - 按照字（节）为单位，每个地址触发一次中断
• DMA控制器：数据计数器（DC）进行统计传输大小（自减）；数据寄存器（DR）进行速度匹配；内存地址寄存器（MAR）存放内存始地址/源地址；CR存储命令和状态
  • 每次传输一个字后DC减一，（MAR） = （MAR）+1
• IO通道方式：一次读多个数据块并传送区域不连续；一次对一组数据块读写或者干预
• 通道程序：由一系列通道指令构成：操作码、内存地址、计数（类似DMA中数据计数器）和通道程序结束位（二进制表示是否结束）、记录结束标志（分割不同指令是否属于同一记录）

与设备无关软件：

• 实现设备独立性，在设备驱动器上设置的逻辑层软件
• 引入逻辑设备名，实现设备无关性与IO重定向（更换用于IO操作的设备）
• 实现逻辑设备名称到物理设备名称的转换：配置逻辑设备表
• IO系统最高层软件，包括了执行所有设备公有操作的软件
  • 设备驱动程序统一接口：规范化接口，方便开发；针对权限控制的门禁，防止无权限用户访问
  • 缓冲管理
  • 差错控制：暂时性错误（重传纠正，多次连续错误（10次）后认为是设备出错）；持久性错误（持久性故障引起）
  • 对独立设备的分配与回收：避免设备占用后不进行归还，因此系统统一分配（设备无关软件进行）
  • 独立于设备的逻辑控制块：不同磁盘数据块大小可能不一致，但被隐藏掉
• 资源管理的数据结构 > 设备表（DCT）
• 设备的固有属性：独占、共享、虚拟
• 设备分配算法：先来先服务，优先级高优先
• 运行时安全性的设备分配：
  • 安全分配方式：进程占用设备后执行IO，执行完成直接释放，进程阻塞直到IO完成；
  • 不安全分配方式：进程发出IO请求后又发出多个IO请求，仅当请求设备已被另外一个进程占用才进入阻塞
• 独占设备的分配程序：
  • 分配设备：先按照物理设备名查找SDT，找对应DCT，空闲则将设备进行分配，忙则插入设备等待队列
  • 分配控制器：在DCT中找到对应COCT入口，空闲分配，忙则插入控制器等待队列
  • 分配通道：COCT中找CHCT，空闲分配，忙则挂入通道等待队列上
  • 分配成功后切换到就绪态直到被调度，执行IO再次阻塞
  • 驱动程序在分配完成后才被调用启动IO和处理中断

用户层的IO软件

• 系统调用：内核提供调用入口，用户主动传递参数，是应用程序获得OS服务的唯一途径
• 中断：硬件留下状态信息，OS内核在中断周期读该信息调用中断处理程序
• 库函数：位于用户态，提供一层封装；屏蔽了不同平台之间的差异，确保一份源码多平台运行；是OS内核的扩展，可能有库函数没有与系统调用相关

假脱机系统（Spooling系统）

将一台物理CPU虚拟成多台逻辑CPU，允许多个用户共享主机

• 脱机输入输出系统：采用外围处理机将低速IO数据与高速磁盘传输，通过高速磁盘进行中转
• 多道处理程序中通过两道程序模拟外围输入输出时候外围处理机功能：外围操作与CPU对数据的处理同时进行
  • 避免多个进程因为独占设备而互相阻塞
  • 使用两个常驻内存的进程模拟输入输出
• 组成：软件技术，不需要专门设计硬件支持
  • 输入井和输出井：磁盘的两个区域，以文件形式管理，一个文件（进程私有，一般不共享）一个进程数据，所有进程文件链接队列；
    • 输入设备可以持续输入，无空闲
  • 输入缓冲区和输出缓冲区：内存中的两个区域，缓和速度问题
    • 输入数据：输入设备-输入缓冲区 - 输入井
    • 输出数据：CPU - 输出缓冲区 - 输出井
  • 输入进程和输出进程：预输入进程和缓输出进程
  • 井管理程序：控制作业和磁盘井之间信息交换，操作系统调用井管理程序
• 特点：
  • 提高IO速度：由低速IO升级为磁盘速度
  • 独占设备改为共享：
  • 实现了虚拟设备功能：宏观共享，进程层面共享
• 守护进程：守护进程允许使用该独占设备的唯一进程，其他进程通过写入文件放在假脱机目录由守护进程按照顺序依次完成请求

缓冲区管理

可以由硬件寄存器组成，实际上考虑成本使用内存作为缓冲区

• 缓和速度矛盾、减少中断频率、解决数据颗粒度不匹配问题、提高CPU和IO设备并行性
• 单缓冲区：Max(C,T)+M
• 双缓冲区：即缓冲对换，先输入第一缓冲区，然后输入第二缓冲区；计算平均耗时为Max(C+M,T)，其中数据传输M可以和设备输入C重叠（两个不同缓冲区）
  • 双机双向同时通信需要各两个缓冲区
  • 只能解决设备慢的问题，不能解决CPU慢的问题
• 环形缓冲：内核根据缓冲区中已经有数据的量提供提醒水位服务（唤醒用户），用户在数据量达到用户设定标准之后读取可用数据到用户空间
  • 将两个缓冲区扩充到多个，三类：装入数据的空缓冲区R，已装满数据的缓冲区G以及计算进程正在使用的现行工作缓冲区C；每个类别进程对应指针
  • Getbuf过程：调用下一个满数据缓冲区转为现行工作进程； - 已可用缓存转为当前使用
  • Releasebuf过程：释放空间， - 数据向用户空间传输完成；输入数据已经装满缓冲区
  • 输入进程和计算进程并行执行，指针会不断变化
  • 输入事件小于计算时间，最后缓冲区满，输入被阻塞，系统最后受计算限制
  • 输入时间大于计算时间，最后缓冲区空，计算被阻塞，系统收IO限制
• 缓冲池：设置公用缓冲池，多个缓冲区供多个进程共享；新增对应的管理数据结构和操作函数；缓冲池中的队列是临界资源
  • 缓冲首部和缓冲体：首部包括缓冲区号、设备号、设备上的数据块号（数据来源）、同步信号量（控制同步访问）以及队列链接指针；
    • 缓冲队列：空白缓冲队列：可用的空白缓冲；输入缓冲队列：装满输入数据；输出缓冲队列：装满输出数据
    • 四种工作缓冲区：接收输入数据，接收输出数据，发送输入数据，发送输出数据
    • 同步与互斥：互斥信号量MS（type）、资源信号量RS（type）

磁盘存储器

磁盘调度算法减少磁盘寻道时间

• 组成：磁盘片分存储面，存储面分为磁道（每个磁道上存储相同数据），磁道划分扇区；扇区之间有间隙（Gap）
  • 柱面：所有盘面上相同磁道集合
  • 环带：磁道中扇区数相同的相邻磁道集合构成一个环带
  • 虚拟：磁盘隐藏内部实现，仅提供一维的虚拟磁盘规格
• 磁盘低级格式化：格式化后的磁盘存储数据
  • 温切斯特磁盘：数据区大小相对固定（原始512B，现代4KB），按扇区储存对应控制信息
  • 标识符字段：SYNCH定界，利用磁道号、磁头号、扇区号标识扇区；CRC字段进行段校验，
  • 格式化之后柱面号、磁道号从0开始，扇区号从1开始
  • 间距：扇区与扇区之间，扇区的不同字段之间均设置间隙
  • 标识符号：位于间隙后，每个扇区的字段开始：
  • 数据段：SYNCH标识符，数据，CRC校验
• 分区：逻辑上每个分区是独立的逻辑磁盘；记录每个分区的起始扇区和分区大小；放在CHS编号（0，0，1）开始的主引导记录分区表中包含的分区表；标识其中一个分区为活动的
  • MBR分区：存放引导代码，分区表和结束表示；最多四个分区
  • GPT分区：
• 高级格式化：建立文件系统，设置引导块，空闲磁盘管理、根目录和一个空文件系统，分区表中标识该分区使用的文件系统
  • 引导块：分区第一个块，存放引导代码，用于从该分区启动操作系统
  • 超级块：储存文件系统的全局参数，魔数表示文件系统类型
  • 块组描述符：描述每个块的信息
  • 块位图：
  • inode位图：
  • 根目录
  • 数据块：
• 类型划分：硬盘和软盘；单片盘和多片盘，固定头磁盘和活动头磁盘
  • 固定头磁盘：每条磁道上一个磁头，磁头统一装载刚性磁臂；每个磁头独立决定是否访问该磁道（可以并行读/写），用于大容量磁盘
  • 移动头磁盘：每个盘面一个磁头，装入磁臂，磁头移动训导，移动磁头仅能串行（针对同一盘面），IO速度慢
• 磁盘访问时间计算：总时间 = 寻道时间+旋转延迟时间+ 读写数据时间寻道时间包含启动磁臂时间+移动到磁道时间；旋转延迟时间指指定扇区开始处移动到磁臂下的时间，一般为当前磁道访问一周时间的一半；传输时间才是数据真正传输的时间
  • 因此适当集中数据有利于提高传输效率
• 早期磁盘调度算法：
  • FCFS算法：按照进程请求访问磁盘的先后顺序依次访问
  • （最短寻道时间优先）SSTF算法：每次访问完磁道后访问与当前磁道最近的请求磁道
• 扫面磁盘调度算法：
  • 扫描算法（SCAN）：针对SSTF算法修改，优先考虑磁头当前移动方向，单向扫描到最高需求磁道再返回依次扫描
  • 循环扫描算法（CSCAN）：磁头单向移动的扫面算法，这样将最大延迟时间降低到扫描算法的一半
  • 磁臂黏着：有几个进程反复请求对某一磁道的IO导致按照算法调度会垄断整个磁盘设备
  • NStepSCAN算法：将对整个请求队列使用的算法截断，划分为大小为N的区间内使用调度算法
  • FSCAN算法：只划分两个区间，一个当前扫描队列，一个扫描期间新的请求

外存管理

1. 操作系统考试大纲 > 磁盘存储器
2. 固态硬盘(读写性能特性，磨损均衡)
   1. 按照块擦除，以页为单位读写：写放大：每次写都会另外找新块重新写整块，远高于实际修改的页大小
   2. 每次写的时候找一个空闲页写入新数据，将旧页标记无效
   3. 支持随机读和顺序读：但写性能低于读性能，随机写低于顺序写
   4. 读的性能很高，每次写前必须擦除
   5. 磨损均衡：防止某些块被频繁擦鞋，导致先损坏导致SSD；让所有块的擦写次数尽量均与；
      1. 动态均衡：每次写的时候优先选择擦除次数少的，不主动搬迁冷数据（长时间不调用的数据）
      2. 静态磨损均衡：定期扫描擦除次数低的块将其中的冷数据搬迁到擦除次数高的块
      3. 实际容量大于标称容量，多出部分叫做预留空间OP，用于垃圾回收，减少写放大