408-os

35’

C1 计算机系统概述

1.1 操作系统的基本概念

• 操作系统管理各种计算机硬件并为应用程序提供基础，充当计算机硬件与用户之间的中介

• 操作系统管理和控制整个计算机系统的硬件和软件，合理组织调度计算机工作和资源分配，为用户和软件提供方便接口和环境的程序集合

• 特征：

  • 并发：两个或多个事件同一时间间隔内发生（并行是同一时刻），通过分时实现
  • 共享：互斥共享（临界资源）、同时访问（宏观同时，可能分时共享），可重入同时访问
  • 虚拟：一个物理CPU虚拟成多个逻辑CPU（时分复用），虚拟存储器（空分复用）
  • 异步 ：不可预知推进

• 操作系统的功能：

  • 处理机管理（可归纳为对进程、线程的管理）：进程控制、进程同步、进程通信、死锁处理、处理机调度
  • 存储器管理：内存分配回收、地址映射、内存保护、内存共享、内存扩充
  • 设备管理：缓冲管理、设备分配、虚拟设备等
  • 文件管理：文件存储空间的管理、目录管理、文件读写管理和保护

• OS为用户和计算机硬件之间的接口（也是用户使用计算机的方法）

  • 命令接口
    • 联机命令接口（交互式命令接口 Shell）
    • 脱机命令接口（批处理命令接口 .bat）
  • 程序接口
    • 一组系统调用（用户通过程序中使用这些系统调用来请求OS为其服务）

• 课后习题：

  • OS管理计算机资源
  • OS给编程人员的接口是系统调用（对应程序接口）
  • 系统调用的目的是为了请求系统服务
  • OS通过系统调用为用户程序提供服务、文件I/O需要在内核态
  • OS被加载到内存中的系统区 RAM
  • 系统中的缓存全部由操作系统管理，对用户透明，不提供管理系统缓存的接口
  • 引入多道程序后，程序执行失去封闭顺序，因为资源共享产生竞争，顺序性是单道程序的基本特征
  • 库函数属于用户程序而非系统调用，在系统调用上层（库函数是高级语言中提供的与系统调用对应的函数，运行在用户空间中）
  • 使用系统调用需要上下文的切换以及用户态、核心态的转换

1.2 操作系统的发展历程

• 手工操作阶段（无OS）

  • 用户独占全机
  • CPU等手工，利用不充分

• 批处理阶段（OS出现，批处理解决了CPU与I/O速度不匹配的问题）

  • 单道批处理系统
    • 内存中始终保存一道作业
    • 自动性、顺序性、单道性
    • 发出输入输出请求便一直等待IO完成
  • 多道批处理系统（脱机）
    • 多个程序同时进入内存，允许在CPU中交替运行
    • 宏观并行、微观串行
    • 用户响应时间较长
    • 不能人机交互，不能控制计算机

• 分时操作系统

  • 处理器的运行时间分成很短的时间片，轮流分配联机作业，用户感觉自己独占计算机
  • 多个用户通过终端同时共享一台主机
  • 同时性、交互性、独立（独占）性、及时性
  • 虽然及时，但是有时候需要更加短的时间内做出反应

• 实时操作系统

  • 硬、软实时（必须在规定时刻发生）
  • 及时性、可靠性

• 网络操作系统和分布式计算机系统

  • 各台计算机有机结合，实现网络各种资源的共享以及各台计算机之间的通信
  • 若干操作系统协同完成同一个任务

• 个人计算机操作系统

  • Windows Linux Macintosh

• 课后习题：

  • 批处理系统不允许用户与计算机直接交互
  • 中断技术使得多到批处理系统的I/O设备可与CPU并行工作
  • 多道批处理I/O可以和CPu并行运行
  • 计算CPU利用率
    • 单道：CPU使用时间/总共程序时间
    • 多道：甘特图/横道图
      • 横坐标时间间隔，纵坐标程序名，不同线区分不同资源的占用，注意临界资源

1.3 操作系统运行环境

• CPU运行两种不同性质的程序

  • OS内核程序
    • 可执行特权指令：IO 、中断等
    • 核心态
  • 用户自编程序
    • 可执行非特权指令：访问用户的地址空间
    • 用户态

• 内核：

  • 时钟管理
  • 中断机制：只有一小部分属于内核
  • 原语：最底层最接近硬件，一气呵成，时间短，调用频繁
  • 系统控制的数据结构及处理：PCB、各类缓冲区、空闲区登记表等等

• 中断和异常（由OS处理完成）

  • 发生中断和异常时，用户态CPU会立刻进入核心态，硬件实现
  • 中断：外中断、设备发出I/O中断
    • 内部异常
      • 故障、自陷（软件）
      • 终止（硬件）
    • 外部中断（硬件）
      • NTR 可屏蔽中断，实现多重中断
      • NMI 不可屏蔽中断，电源掉电
  • 异常：内中断、越界等、不能被屏蔽

• 系统调用

  • 用户在程序中调用OS子功能，可视为公共的子程序
  • 可分为
    • 设备管理
    • 文件管理
    • 进程控制/通信
    • 内存管理
  • 运行在核心态
  • 用户程序可以通过执行陷入指令（trap指令、访管指令）来发起系统调用
  • 相当于把CPU的使用权交给操作系统内核程序
  • 使用完后CPU使用权还给用户程序
  • 用户不能执行对系统影响很大的操作，需要请求OS内核代为执行
  • 系统通过中断机制（异常处理）进入核心态来完成操作
  • 进入核心态不仅状态切换，堆栈可能也要切换，系统堆栈其实也是属于该进程但只能由OS管控

• 课后习题：

  • 运行程序需要确定起始地址，从这个地址开始运行
  • I/O必须核心态
  • 通道是硬件技术
  • 用户态使用特权指令为访管中断
  • 中断处理流程前三个步骤硬件实现，地址映射需要基地址寄存器，时钟管理需要硬件计数器，进程调度是算法问题
  • 进入中断处理程序的一定是OS程序，中断本身可能是应用程序
  • 广义指令就是系统调用，会使用户态转向内核态，硬件完成转换
  • 中断处理程序会保存而子程序调用不需要保存的是PC程序计数器
  • 用户态不可能关中断，关中断为特权指令
  • 外部中断PC会被中断隐指令自动保存，通用寄存器内容由OS保存
  • 访问存储器缺页属于异常（内部中断）
  • 执行系统调用流程：先传递系统调用参数，再由陷入指令转态，最后返回地址压栈备用，执行内核态服务程序最后返回用户态
  • 时钟中断需要处理和时钟有关的信息
  • OS要完成和中断相关的操作：初始化中断向量表，提供中断服务，保存中断屏蔽字
  • 常见特权：有关I/O设备操作指令，有关访问程序状态的指令，存取特殊寄存器的指令
  • 多道程序并发指有的程序在CPU执行，另一些在I/O传输
  • 综合题2：通道是一种控制多台外部设备的硬件机构，独立于CPU运行
  • 通道和中断技术结合起来可以实现CPU和I/O设备并行工作，即CPU启动通道传输数据后便去执行其他程序的计算工作，通道I/O，通道结束通过终端机构向CPU发出中断请求，这时候CPU停下工作处理中断请求。

1.4 操作系统结构

• 分层法

• 模块化

  • 做到高内聚低耦合
  • 正确性可维护性可理解性
  • 可适应性和高速开发过程

• 宏内核

  • 将系统的主要功能模块都作为一个紧密联系的整体运行在内核态
  • 从而为应用程序提供高性能服务
  • Windows Linux macOS

• 微内核

  • 内核中基本的功能保留在内核，不需要在核心态执行的功能转移用户态
  • 将OS划分称为两大部分：微内核和多个服务器
  • 绝大部分功能都放在微内核外的一组服务器（进程）实现，各种服务器都是通过进程实现的
  • 内核仅仅包含与硬件紧密相关的部分，基本的功能
    • 进程/线程管理
    • 低级存储器管理
    • 中断和陷入处理
  • 微内核的特点
    • 扩展性和灵活性
    • 可靠性和安全性
    • 可移植性
    • 分布式计算

1.5 操作系统引导

• 激活CPU
• 硬件自检
• 加载带有OS的硬盘
• 加载主引导记录MBR
• 扫描硬盘分区表
• 加载分区引导记录
• 加载启动管理器
• 加载操作系统

1.6 虚拟机

• 一台逻辑计算机，利用虚拟化技术通过隐藏计算平台的实际物理特性，为用户提供抽象计算环境
• 第一类虚拟机管理程序
  • 虚拟机作为用户态的一个进程执行
  • 虚拟机管理系统向上提供多台虚拟机
• 第二类虚拟机
  • VMware Parallel 套娃
• 课后习题：
  • 分层设计的OS结构清晰便与调试，效率低，单向依赖，不灵活
  • 微内核性能没有宏内核好，策略与机制分离，需要频繁切换，宏内核切换快
  • 微内核适合分布式系统环境
  • 常驻内存的只是操作系统内核
  • 硬件软件互相实现

C2 进程与线程

2.1 进程与线程

• 多道程序环境允许多个程序并发执行，失去封闭，间断，不可再现

• 进程实体由程序段，相关数据段，PCB构成（PCB是进程存在唯一标志）

• 进程实体是静态的，进程是动态的

• 进程的状态（前三种基本状态）

  • 运行态
    • 获得处理机资源
  • 就绪态
    • 等处理机器
    • 时间片用完
    • 进程等待的事件到来了
    • 更高优先级的进程出现了
  • 阻塞态
    • 等其他资源（除了处理机）
    • 等I/O 通过系统调用请求OS的服务
  • 创建态
    • 等内存
  • 结束态
    • 先设为结束再处理资源释放回收

• 运行到阻塞主动，阻塞到就绪时被动

• 对进程来说 PCB是核心，是进程存在的唯一标志，其常驻内存

• 运行时通过PCB了解状态，结束时回收PCB，OS想调度程序的时候就从PCB查出他的状态和优先级，调度到他后通过PCB的信息恢复现场，系统总通过PCB来对进程进行控制

• PCB

  • 进程描述信息 PID UID：标志进程
  • 进程控制和管理信息：当前状态，优先级等
  • 资源分配清单：内存空间以及虚拟地址空间状况
  • 处理机相关信息：处理机上下文，寄存器的值

• 一个OS中很多PCB

  • 链接方式组织，不同的链式队列
  • 索引方式组织，不同的索引表

• 进程控制（着重记住PCB的位置以及进程的状态）

  • 进程控制用的程序段是执行期间不可以被中断的原语
  • 进程的创建（创建原语）
    • 为进程分配PID，申请空白PCB（PCB有限）
    • 为进程分配所需资源，若没有资源分配就处于创建态
    • 初始化PCB
    • 进程就绪队列可以接纳新进程就将新进程插入就绪队列，等待被调度
  • 进程的终止（终止原语）
    • 根据PID检索PCB
    • 立即终止，资源回收再分配
    • 子孙也终止
    • PCB删除
  • 进程的阻塞和唤醒
    • 新数据未到达或者请求系统资源失败，通过自己调用阻塞原语从运行变成阻塞
    • 阻塞原语：找到PID对应的PCB，改成阻塞态，插入等待队列（Block）
    • 唤醒原语：从等待队列找到PCB，改成就绪态，PCB插入就绪队列（Wakeup）

• 进程通信

  • 共享存储
    • 通过同步互斥工具（如PV）
    • 低级共享：共享数据结构
    • 高级共享：共享存储区
    • 共享空间需要特殊的系统调用
  • 消息传递（微内核和服务器就用了这个捏）
    • 直接通信（通过系统提供的消息发送和接受消息原语）
    • 间接通信，信箱
  • 管道通信（进化的共享存储）
    • 连接一个读进程一个写进程的一个共享文件 pipe文件
    • 管道是一个固定大小缓冲区
    • 半双工
    • 有数据就能读，不管在不在写

• 线程与多线程模型

  • 引入进程为了更好并发，引入线程为了提高并发性能
  • 线程可以理解成轻量级进程
  • 线程是被系统独立调度的基本单位（进程是资源分配基本单位）
  • 线程只有必不可少的资源，统一进程中的多个线程可以并发
  • 线程也有基本三种状态

• 进程线程比较

  • 线程是被系统独立调度的基本单位（进程是资源分配i基本单位）
  • 进程可并发，统一进程多个线程也可以并发
  • 同一进程中线程切换不会引起进程切换，不同进程间的线程切换回引起进程切换
  • 同一进程的多个线程会共享进程的地址空间，同步和通信方便，无需OS甚至
  • 支持多机

• 线程的属性

  • 每个线程又一个线程控制块TCB，记录了寄存器和栈等现场状态

    • TID 寄存器 优先级 运行状态 专有存储区 堆栈指针 返回地址
    • 创建新线程是通过线程创建函数（进程是创建原语）

  • 不同的线程可以执行相同的程序

  • 同一进程中的哥哥线程共享该进程拥有的资源

• 线程的实现方式

  • 用户级线程
    • 线程切换不需要转换到内核空间 节省切换开销
    • 调度算法可控
    • 对线程管理的代码与OS无关（比如Goroutine）
    • 进程的一个线程被阻塞，进程直接G
    • 不能发挥多处理机优势
  • 内核级线程
    • 进程切换快但是同一进程的线程之间切换也需要从用户态转核心态
  • 组合方式
    • 一些内核级线程对应多个用户级线程
    • 线程库可以是OS提供，也可以是用户空间的本地库

• 多线程模型

  • 多（用户级线程）对一（内核级线程）：线程管理用户空间进行，一个阻塞全部G
  • 一对一：一个用户线程一个内核线程，开销大，并发强
  • 多对多：都好，老好人了

• 课后习题

  • 线程也可以独立执行程序，没有自己独立的地址空间，共享进程的
  • 进程最大数目受到内存大小制约
  • 创建后进入就绪队列
  • 阻塞态到就绪态的转换是由协作进程决定
  • 同一进程或不同进程内的线程都可以并发执行
  • 线程是进程内一个相对独立的执行单元，但不能脱离进程单独运行
  • 文件系统也可以交换数据
  • 一个进程从运行态变成就绪态必定进程切换
  • 一个内核级线程阻塞，CPU将会调度同一进程中其他内核级线程
  • 多处理机系统，核心可以同时调度同一个进程的多个线程并行运行
  • 降低进程优先级的合理时间：时间片结束
  • 进程中的线程共享进程内的全部资源，但是某线程的指针对另一个线程不透明
  • 进程申请临界资源，访问磁盘会阻塞（等磁盘读文件）
  • 内核级线程的的调度OS完成
  • 每个线程都有一个TCB
  • 父子进程不共享虚拟地址空间
  • 在多线程模型中，用户级线程和内核级线程的连接方式分为多对一、一对一和多对多，操作系统为每个用户级线程建立一个线程控制块是属于一对一模型，其他两个模型没有为用户级线程建立一个线程控制块，即B选项错误；

2.2 处理机调度

• 任务很多但资源游戏，处理机调度需要对处理机分配，即从就绪队列中按照一定算法选择一个进程并分配处理机，以实现进程的并发执行

• 调度的层次

  • 高级调度（作业调度）
    • 内存和辅存之间的调度，每个作业只调入一次调出一次
  • 中级调度（内存调度）（提高内存利用率）
    • 将不能运行的程序调到外存等待，挂起态，挂起队列（存储器管理中的对换）
  • 低级调度（进程调度）
    • 从就绪队列中选一个进程分配处理机，频率非常高

• 三级调度的关系

  • 作业调度为进程活动做准备
  • 中级调度将不能运行的进程挂起
  • 频率越来越多
  • 进程调度不可或缺

• 调度的目标

  • CPU利用率：有效工作/等待➕有效
  • 吞吐量
  • 周转时间：完成时间-提交时间
  • 等待时间：等处理机的时间之河
  • 响应时间：提交到首次产生响应

• 调度的实现

  • 调度程序（调度器）
    • 排队器
    • 分派器
    • 上下文切换器
  • 调度的时机、切换与过程
    • 不能调度的情况
      • 中断处理中
      • 内核临界区
      • 原子操作
    • 应该调度的情况
      • 发生调度条件且当前进程无法进行
      • 中断结束或者自陷结束后（系统调用结束）

• 进程调度方式

  • 抢占
  • 非抢占

• 闲逛进程

  • 没有就绪进程
  • 最低优先级
  • 有进程就绪就让出处理机

• 两种线程调度

  • 用户级线程调度
    • 内核不知道用户及线程的存在，选一个进程并给予时间，进程中自己的调度程序选择线程运行
  • 内核级线程调度
    • 内核选一个特定线程，赋予时间片，过时间就挂起
  • 用户级只需要少量机器指令，内核级需要完整上下文切换，导致延迟

• 经典调度算法！！！（处理机调度）⭐️

  • 先来先服务 FCFS
    • 从就绪队列中选择最先进入该队列的进程，分配处理机
    • 利于CPU繁忙型作业，不利于I/O繁忙
    • 算法简单、效率低、长作业有利、短作业不利
  • 短作业优先 SJF
    • 长作业不利
    • 完全没考虑作业紧迫程度
    • 作业长短是用户所提供的估计时间而定
  • 优先级调度算法
    • 抢占非抢占
    • 动态静态优先级
    • 系统进程优先级大于用户进程优先级
    • 交互性大于非交互
    • I/O大于计算
  • 高响应比优先调度算法
    • 计算响应比=（等待时间+要求服务时间）/要求服务时间
  • 时间片轮转调度算法
    • 分时系统
    • 时间片太大会退化成fcfs
  • 多级队列调度算法
    • 多个就绪队列，按照不同类型或者性质分
  • 多级反馈队列调度算法（融合前几种算法优点）
    • 设置多个就绪队列
    • 赋予各个队列的进程运行时间片大小各不相同
    • 每个队列fcfs
    • 按队列优先级调度
    • 每一级队列时间片变长，新加入到1级，一个时间片完成撤离，完成不了就放到第二级末尾，n级中采用时间片轮转
  • 总结P70图
  • 除了多级反馈队列和时间片轮转默认抢占，其他默认非

• 进程切换

  • 上下文切换
    • 挂起一个进程 保存CPU上下文 更新PCB
    • PCB移动到相应队列
    • 选择另一个进程运行 更新其PCB
    • 跳转到新进程PCB中PC指向位置
    • 恢复处理机上下文
  • 上下文切换的消耗
    • 改变寄存器组的指针
  • 上下文切换与模式切换

• 处理机的调度提高率系统资源的利用率，合理的处理计算机软/硬件资源

• 课后习题：

  • 平均周转时间最短的是短作业优先算法
  • 高响应比优先也算短作业优先
  • 在不影响临界区使用规则的情况下，不影响处理机调度
  • 访问打印机时就不能调度的话，系统性能可不是很差吗
  • 一定要区别好作业调度和进程调度
  • 看清题中是几道程序的批处理系统

2.3 同步与互斥

• 同步与互斥的基本概念

  • 临界资源：一次只允许一个进程使用
    • 进入区、临界区、退出区、剩余区

  • 同步：先后关系
  • 互斥：制约关系
  • 准则
    • 空闲让进
    • 忙则等待
    • 优先等待
    • 让权等待

• 实现临界区互斥的方法

  • 软件实现方法
    • 单标志法
      • 用turn变量指明谁能进，但必须交替
      • a出去了，b不进，a不能再进
      • 导致谁也进不去
    • 双标志法先检查
      • 先检查是否另一个进程想用
      • 不想则把自己的flag设置成想用（1）
      • 不用交替进入
      • 可能导致同时访问临界资源
      • 因为检查对方flag与改变自己的flag并不是一气呵成
    • 双标志法后检查
      • 都先把自己的flag设置成想用（1）
      • 饥饿，谁都进不去
    • Peterson‘s Algorithm
      • 防止无限等待
      • 都很客气，先说自己想用后把自己进入临界区的trun改成对方
      • 判断时Pi：while( flag[ j ] && turn == j )
      • 想访问但对方想访问且turn是对方就一直while
      • 退出时改变自己的 flag，破坏对方while条件
  • 硬件实现方法
    • 中断屏蔽方法
      • 执行效率低，不适合多机，关中断是特权指令
    • 硬件指令方法（不让权等待）
      • TestAndSet指令：检查lock 无人用临界则false 置为true 让任何人进不去临界区
      • Swap指令： 交换key与lock值

• 互斥锁

  • acquire()获得锁 release()释放锁
  • 问题：忙等待
  • 适合多处理机系统

• 信号量

  • P (wait)：申请
  • V (signal) ：释放
  • 整型信号量
    • 不让权等待，忙等（while ( s<=0 ) )
  • 记录型信号量
    • 资源变量value
    • 进程链表L 解决忙等
    • P操作依旧会使value-1 ，如果资源不足会添加进链表，并阻塞自己
    • V操作会唤醒L链表中的首个，实现让权等待
  • 利用信号量实现同步
    • 先V后P，即后面一个想要走必须需要资源value
    • 开始把资源设为0，后面的只能等前一个V了以后才能P
    • 同时可以实现前驱关系
  • 利用信号量实现互斥
    • mutex
    • p后进入 访问结束后V

• 管程

  • 信号量机制容易因操作不当导致死锁
  • 管程的特性保证了进程互斥，无需程序员自己实现互斥（编译器实现）
  • 提供了条件变量，可以让程序员灵活的实现同步
  • 管程的构成
    • 名字
    • 内部共享数据结构说明
    • 对数据操作的一组过程（或者函数）
    • 对局部于管程内部的共享数据设置初始值的语句
  • 管程把对共享资源的操作封装起来
  • 每次仅仅允许一个进程进入管程

• 经典同步问题

  • 生产者消费者问题
    • 务必先 P 空闲缓冲区 再P 临界区
    • 否则会导致你占用了临界区 但是没有空闲缓冲区
    • 释放的先后无所谓
    • 父母必须P盘子V水果 孩子P水果V盘子
  • 读者-写者问题
    • 允许多读 只允许一个写 写前让别人走 写完成之前不允许读
    • 注意避免写者饿死问题（没人读才V写者）
    • 添加写优先，让写者也能竞争到一个额外的临界资源，如此在看的人都看完了写者就能写，不会让写者饿死，写完也会及时释放资源
  • 哲学家进餐问题
    • 俩筷子才能吃饭问题
    • 都拿左边直接G，都别吃了饿死算了
    • 最多限制4个哲学家吃可以解决
    • 当左右都能拿起来才能吃也能解决（拿左右这俩操作都在临界区 临界区为1）
  • 王源-丁真问题
    • 把信号量设置成xxx与xxx的组合

• 课后习题：

  • 访问临界资源的代码叫临界区
  • 并发执行不需要信号量，互斥，同步，前后驱动需要
  • 信号量-几代表链表里几个在等
  • 等待I/O被中断时，可以让出处理机，但是别人不能进入该进程临界区
  • 临界区是共享变量段的代码程序
  • 临界资源是互斥共享资源
  • 原语是不可分割的指令序列
  • PV操作是第几进程通信原语
  • 公用队列属于临界资源
  • TSL（Test and Set Lock）退出临界区置lock为FALSE，唤醒就绪态的程序，不让权
  • PV操作常常会出综合大题
  • 2011 PV 不错
    • 理清流程，顾客需要有空位才能才能取号 空位empty
    • 取号互斥所以mutex
    • 取号后相当于可以被叫，因此 等被叫的人+1 full+1
    • 服务过程对于顾客与顾客是互斥的，对于功能作人员和人是同步的
    • 营业员则没有顾客就休息
    • 有顾客就服务一个 同时释放一个座位，叫号服务。
  • 2021考的描述与理解居多

2.4 死锁

• 死锁的概念

  • 由于多程序并发执行而导致进程因为竞争资源而相互等待
  • 无外力无法推进
  • A占打印机要BB机 C占BB机要打印机

• 死锁产生原因

  • 系统资源竞争：只有对不可剥夺的资源竞争才可能死锁
  • 推进非法
  • 死锁产生必要条件
    • 互斥条件：进程排他使用
    • 不剥夺条件：未使用完不能被强行夺走，只能自己释放
    • 请求并保持条件：进程已经保持了至少一个资源，提出了新的资源要求，但资源被其他人占有，请求被阻塞，但对自己保持的资源不放
    • 循环等待条件：循环等待链

• 死锁的处理策略

  • 死锁预防
    • 破坏互斥条件：允许共享使用，但互斥性需要保持，一般破坏不了
    • 破坏不剥夺条件：得不到满足就放弃资源
    • 破坏请求并保持条件：静态分配，一次申请完所有的资源，不满足不工作
    • 破坏循环等待条件：顺序资源分配法，资源编号，同类资源申请完，申请大编号
  • 死锁避免
    • 系统安全状态
    • 银行家算法
      • Max
      • Allocation
      • Available
      • Need
  • 死锁的检测与解除
    • 资源分配图
      • 请求边
      • 分配边
    • 死锁定理
      • 找到申请数量小于等于系统中的空闲资源数量，有的话释放
      • 完全简化就不死锁，否则死锁
    • 死锁解除
      • 资源剥夺法：先别做
      • 撤销进程法：别做了
      • 进程回退法：回溯吧，时光倒流！

• 课后习题

  • 死锁出现是因为若干进程因竞争资源而无限等待别的进程释放资源
  • 死锁避免是防止系统进入不安全状态
  • 资源有序分配可以限制循环等待
  • 引入多道程序的基础是要系统支持中断功能性
  • 死锁预防通过破坏四个必要条件之一来防止发生死锁
  • 一般不出大题，小题还是常考的，不能失分
  • 希望今年大题考个银行家算法，不难，基本不会失分，主要就是找安全序列

• 重难点

  • 进程是动态概念，离开程序的进程没有意义
    • 进程和程序的组成不同
    • 一个程序可以多个进程
    • 动态创建消亡
  • 死锁与饥饿
    • 死锁是两个或者多个进程在无限的等待一个事件，而这些事件只能是由这些正在等待的进程实现
    • 饥饿时进程长时间的等待导致对进程推进产生了明显影响，最后可能会被饿死。打印机，短文件优先
    • 死锁阻塞，饥饿就绪
  • 银行家算法避免系统进入不安全序列
  • 并发会相互制约
    • 互斥访问
    • 同步协同

C3 内存管理

• 操作系统的核心就是内存管理和进程管理
• 程序放入内存才能被CPU处理，缓和CPU和硬盘之间的速度矛盾

3.1 内存管理概念

• 基本原理和要求

  • 虚拟技术从逻辑上拓宽内存
  • 主要功能：
    • 内存空间的分配与回收
    • 地址转换（重定位）：逻辑到无力
    • 内存空间的扩充（虚拟）
    • 内存共享
    • 存储保护
  • 程序的连接与装入 ⭐️
    • 创建进程首先要将程序和数据装入内存，将源程序编程可在内存中执行的程序
    • 步骤：
      • 编译：由编译程序将用户源代码编译成若干目标模块
      • 链接：由链接程序将编译后形成的一组目标模块以及需要的库函数链接，形成装入模块
        • 静态链接：直接链接成完整装配模块，不再拆开
          • 需要修改相对地址，变换外部调用符号
        • 装入时动态链接：边装入边链接，便于修改更新，便于实现目标模块共享
        • 运行时动态链接 ：加快装入过程
      • 装入：由装入程序将装入模块装入内存运行
        • 绝对装入（低灵活，单道）
          • 单道程序环境，直到程序将驻留在内存的位置，编译产生绝对地址
          • 逻辑地址=实际内存地址
        • 可重定位装入（早起多道批处理系统）（静态重定位）
          • 程序其他地址都是相对于起始地址
          • 装入时对目标程序中指令和数据地址的修改过程称为重定位
          • 地址变换在装入时一次完成
        • 动态运行时装入（动态重定位）
          • 装入后的所有地址都是相对地址
          • 需要重定位寄存器支持
          • 根据需要动态申请分配内存，便于共享，可以不分配连续存储区
  • 逻辑地址与物理地址
    • 逻辑地址转换成物理地址的过程叫地址重定位
    • OS通过内存管理单元（MMU）将进程使用的逻辑地址转换成物理地址
    • 进程使用虚拟内存空间中的地址，在OS和硬件支持下转换成物理地址
    • 逻辑地址通过页表映射到物理内存，页表由OS维护并被处理器引用
  • 进程的内存映像
    • 一个程序调入内存运行时，就构成了进程的内存映像
    • 代码段：二进制代码，可被共享
    • 数据段：全局、静态
    • PCB：放在内存的系统区，OS通过PCB来控制管理进程
    • 堆：存放动态分配变量，通过malloc函数向高地址分配
    • 栈：函数调用，高地址向低地址
  • 内存保护
    • 设置上下限寄存器、CPU要访问地址就把值和两个寄存器比看看越界情况
    • 用重定位寄存器（基地址寄存器）和界地址寄存器（限长寄存器）
    • 加载重定位寄存器和界地址寄存器需要特权指令，只有内核才能加载这两个寄存器
    • 用程序不能修改
  • 内存共享
    • 只读部分才能共享，可重入代码：允许多个进程同时访问但不允许被任何进程修改
    • 段的共享非常简单，容易
    • 铺垫：内存映射文件
  • 内存分配与回收
    • 从固定分区发展到动态分配
    • 为了更好提高内存里用力，从连续分配到离散分配（页式存储管理）
    • 分段就是为了编程和使用方面的要求

• 覆盖与交换

  • 早期主存小，放一个用户程序也可能放不下，用户空间分成一个固定区和若干覆盖区
  • 活跃放在固定区，即将要访问的段放在覆盖区，需要的时候再调入覆盖区，替换原有段
  • 对程序员用户不透明
  • 对换就是把处于等待状态（被剥夺运行权利）的程序从内存移动到辅存，腾出内存空间
  • 中级调度采用的就是交换技术
  • 交换需要备份存储，通常是磁盘
  • 若换出必定是空闲的
  • 交换空间独立于文件系统，很快
  • 对换通常在进程多，内存空间吃紧就开始启动，负荷低就暂停
  • 交换技术在现代操作系统依然重要

• 连续分配管理方式 ⭐️

  • 单一连续分配
    • 内存分为系统区和用户区
    • 系统区OS用，低地址
    • 用户区仅一个用户程序，独占
    • 简单，无外部碎片，无需内存保护
    • 但有内部碎片，存储器利用率低
  • 固定分区分配
    • 用户内存空间分为若干固定大小区域
    • 每个区域一道作业
    • 有空闲分区就从后备作业队列中选一个大小合适的装进去
      • 分区大小相等：浪费，太大装不进去，灵活差
      • 分区大小不等：多个小，适量中，少量大
      • 分区说明表：未找到合适分区拒绝分配
    • 程序小于固定分区时，内部空间浪费，有内部碎片
    • 无外部碎片，利用率低
  • 动态分区分配
    • 无内部碎片，外部碎片可以通过紧凑技术来解决（磁盘碎片整理）
    • 算法：
      • 首次适应（FIrst Fit）算法
        • 空闲分区地址递增
        • 分配时从链首顺序，找到第一个空闲分配给作业
        • 最好最快
        • 低地址很多空闲分区，每次都要再走一遍
      • 邻近适应（Next Fit）算法（循环首次适应算法）
        • 从上次查找结束位置开始查找
        • 导致尾部小碎片，比FF差
      • 最佳适应（Best Fit）算法
        • 空闲分区容量递增
        • 找到第一个满足要求且最小的空闲分区分配给作业
        • 避免大材小用
        • 性能非常差
        • 留下很多小的难以利用的内存块
      • 最坏适应（Worst Fit）算法
        • 容量递减，找到第一个满足要求的
        • 分割一部分空间给作业
        • 性能也非常差
        • 没有很大的内存块

• 基本分页存储管理 ⭐️

  • 每个进程平均半个块内部碎片（页内碎片）
  • 进程中的块称为页or页面
  • 内存中的块称为页框or页帧
  • 外存也这样划分叫块or盘块
  • 进程执行的时候需要申请主存空间，为每个页面分配主存中页框
  • 产生了页和页框之间的一一对应
  • 分页存储逻辑结构：页号+页内偏移量
  • 页号的位数决定了页数的最大值
  • 页内偏移量决定了页的大小
  • 从内存中找出页表查
  • 地址变换机构
  • 逻辑地址变换物理地址的过程P174
  • 可以带快表（TLB）
  • 多级页表（一级页号 二级页号 页内偏移量）
  • 一维（页号不必显示给出，可以求，因为每页长度一样）

• 基本分段存储管理 ⭐️

  • 分段结构：段号+段内偏移量
  • 段表：段号+段长+本段在主存的起始地址
  • 可重入代码不算临界资源
  • 不能修改的代码叫纯代码 也叫可重入代码
  • 二维（段号和段内偏移一定要显式给出）

• 段页式管理 ⭐️

  • 结构：段号+页号+页内偏移量
  • 段表查出页表的长度和起始地址
  • 页号从页表中读出块号
  • 块号加偏移量就是物理地址啦

• 课后习题

  • 虚拟内存管理需要硬件支持（地址变换机构吧）
  • I/O时不能换出
  • 一个进程一个段表，每个段一张页表
  • 内存保护需要OS和硬件机构合作完成
  • 固定分区可以静态重定位
  • 分段没有内部碎片 分页 固定 段页都有内部碎片
  • 系统给用户提供的物理地址空间是总空间-页表or段表
  • 整个系统只有一个重定位寄存器
  • 一台计算机配备一个重定位寄存器即可，一方面是因为寄存器本身很昂贵，不可能拿出来很多给地址转换来使用，另一方面是因为同一时刻只有一个进程在CPU上运行，所以只有一个重定位寄存器能用到，在进程切换时派遣程序会修改重定位寄存器的内容，从而实现基地址的转换，所以一个重定位完全可以解决问题。
  • 实现分区代价最小
  • 有虚拟存储器，运行时，运行前都不用全部在内存
  • 段方便编程、方便共享、保护、动态链接、增长
  • 存储管理为了方便用户和提高内存利用率
  • 如何分段是在用户编程时决定的
  • 进程的页表一直在内存（即使换出了）
  • 段页：分段管理用户，分页管理物理
  • 形成逻辑地址，链接时
  • 最容易产生内部碎片最佳适应算法
  • 二级页表基址寄存器放的是一级页表的起始物理地址

• 综合题：⭐️（伏笔 就做了前6题 吃透了 ）

  • 固定有内无外 动态有外无内
  • 不同的算法 不同的结果 不同的最后空闲分区
  • 无符号右移动 >>>
  • 0x3FF 0000000000,11 1111 1111
  • 按位与
  • （LA >>> 22）& 0x3FF
  • 页表长度也记录在页表基址寄存器
  • 要区别好段和页
  • 段越界：非法地址
  • 要点提炼
  • 一般页表的初始物理地址会给出，要根据这是第几页来算出页表项的物理地址
  • 页表项的物理地址指向了页框号，页框号反映了再内存中这是第几页
  • 比如一页4KB，字节编址
  • 00900H为页框号，对应的页的物理地址就是00900000H
  • 加上偏移量就是具体的地址
  • 也要看一下是否连续存放，很多时候连续存放就提示了很多

3.2 虚拟内存管理

• 虚拟内存的基本概念

  • 传统存储管理方法的特征
    • 一次性、驻留性、浪费宝贵内存资源
  • 局部性原理：时空
  • 虚拟存储器
    - 多次性：无需一次性装入内存，分成多次调入内存运行
    - 对换性：作业运行时无需一直常驻内存
    - 虚拟性：逻辑扩大内存容量
    • 实现方式：
      • 请求分页存储管理
      • 请求分段存储管理
      • 请求段页式存储管理
    • 需要的支持
      • 一定容量内外存
      • 页表or段表基址作为主要数据结构
      • 中断机构
      • 地址变换机构

• 请求分页管理方式（区别于基本分页存储管理）

  • 增加了请求调页功能和页面置换功能
  • 页表机制
    • 请求页表项内字段
      • 页号 物理块号？ 状态位 访问字段A 修改位M 外存地址
      • 状态位P 是否调入内存
      • 访问字段A 一段时间内被访问次数
      • 修改位M 调入内存后是否被修改过
      • 外存地址 该页在外存上的地址，通常物理块号
  • 缺页中断机构
    • 执行指令期间产生or处理中断信号，内部异常
    • 执行期间可能多次缺页中断
  • 地址变换机构
    • 先检索快表 找到访问的页就修改访问位置
    • 利用物理块号和页内地址形成物理地址
    • 未找到就到内存查页表，对比状态位看是否调入
    • 调入则写入快表 快表慢了就要替换

• 页框分配

  • 驻留集大小
    • 对于分页式虚拟内存，不需要进程所有页读入
      • 分配给一个进程的页框越少，内存中进程多，CPU利用率高
      • 若页框过少，尽管局部性原理，缺页率较高
      • 若页框过多，因为局部性原理，缺页率影响不大
  • 内存分配策略
    • 固定分配局部置换
      • 为每个进程一定数目物理块，运行期间不改变
      • 局部置换：缺页就分配给他的一面换出
    • 可变分配全局置换
      • 运行期间根据情况适当增加减少
      • 可从空闲物理块队列分配给他
      • 更灵活、动态增加物理块
      • 但容易盲目分配，并发能力下降
    • 可变分配局部置换
      • 如果频繁中断才给更多的物理块，直到缺页率适当
      • 保持并发能力，不会分配过多过少
      • 需要复杂实现，但对比频繁换入换出的资源，值得
    • 没有固定分配全局置换，不然不是低能吗
      • 全局置换：缺页就从空闲物理块队列分一块给进程
  • 物理块调入算法
    • 平均分配算法
    • 按比例分配算法（进程大小）
    • 优先权分配算法
  • 调入页面的时机
    • 预调页策略
      • 将预计不久之后会被访问的页面先调入主存，概率50%
    • 请求调页策略
      • 不在就提出请求，简单容易实现，一次调入一页，I/O开销大
    • 预调页是运行前、请求调页是运行期间

• 页面置换算法 ⭐️

  • 访问的页面不在内存中就要调入，没空闲需要换出
  • OPT 最佳页面置换算法：无法实现
  • FIFO 先进先出页面置换算法：队列
    • **Belady现象（物理块数增多，问题不减反增） **
  • LRU 最近最久未使用置换算法
  • CLOCK 时钟置换算法
    • 简单的（NRU）
      • 刚进来置1
      • 被访问置1
      • 找人换出时找到1置0 找到0换出
    • 改进的
      • 访问位A 修改位M
      • 00 未被访问 未被修改
      • 01 未被访问 已经被修改 不好淘汰
      • 10 已被访问 未被修改
      • 11 已被访问 已被修改
      • 第一轮找00
      • 第二轮找01 并把所有找的第一位都变成0
      • 重复

• 抖动与工作集

  • 抖动
    • 刚换出又要换入

  • 工作集
    • 某段时间内进程要访问的页面

• 内存映射文件

  • 内存映射文件和虚拟内存有点相似，将磁盘文件的部分or全部与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，而不必执行I/O操作。P210图
  • 允许多个进程并发内存映射同一个文件
  • 共享内存就是通过内存映射实现（填之前共享内存的坑）

• 虚拟存储器性能影响因素

  • 缺页率是影响虚拟存储器性能的重要因素，缺页率又受到页面大小，物理块数（内存中的页），页面置换算法，程序编制方法影响

• 地址翻译⭐️🌟✨ COP看到组相连+cache再来看

  • 字节编址、页面大小64B、页内偏移6位
  • 虚拟地址14位、则虚拟页号有8位（14=8+6）、页内偏移6位
  • 物理地址12位、则物理页号有6位（12=6+6）、页内偏移6位

• 课后习题

  • 缺页次数必定大于总页数（得被调入才会存在换出，调入必缺）
  • 虚拟存储器的最大容量是由计算机的地址结构决定的，与主存容量和外存容量没有必然连续
  • 页表中的合法位信息显示本页面是否在内存中，也决定了是否会发生页面故障
  • 使用多级页表 最高级页表项不能超出一页大小
  • 加快虚实地址转换：增大TLB、页表常驻内存、增加交换区没啥用
  • 缺页可能置换页面或者分配内存（可变分配）
  • 00 01 10 11 顺序淘汰
  • 不能固定分配 全局置换
  • 创建新进程是系统调用

• 综合大题（只做了年份题）

  • 覆盖技术的程序段最大长度收到内存容量大小限制
  • 虚存技术不受内存容量限制，受地址结构限制
  • 缺页后会调入页表和快表，然后访问快表
  • 页面置换的实质，就是把页框分配给进程缺的那个页，页框号不变，变的是页号，也是页号与页框的对应
  • 进程切换需要修改页目录起始地址、TLB、cache等，开销大
  • 大题精彩，需要细心且了解细节

C4 文件管理

4.1 文件系统基础

• 区分文件的逻辑结构和物理结构，深入理解

• 文件是以硬盘为载体的存储在计算机上的信息集合

• 运行时计算机以进程为基本单位进行资源调度分配

• 用户输入输出以稳健为基本单位

• 大多数应用程序的输入都是文件实现，输出也保存在文件

• 需要一个文件管理系统实现对文件的维护管理

• 文件的结构

  • 数据项
    • 基本数据项：一个对象某种属性的一个值
    • 组合数据项： 多个基本数据项构成
  • 记录：一组相关数据项的集合
  • 文件
    • 有结构文件：若干相似记录组成，一个班级的学生记录
    • 无结构文件：字符流、二进制文件或字符文件

• 文件控制块和索引节点 ⭐️

  • 文件控制块
    • 基本信息：文件名、物理位置、逻辑结构、物理结构
    • 存取控制信息：存取全县、核准用户的权限和一般权限
    • 使用信息：建立时间、上次修改时间
    • 其实是目录文件中的一条记录，一条记录就是一个FCB
    • 一个文件目录也被视作一个文件，称为目录文件
  • 索引节点
    • 文件目录通常放在磁盘上，文件很多时文件目录会占用大量盘快
    • 查找目录时要把存放目录文件的第一个盘快调入内存，用给定的文件名比较
    • 没有就下一块，再比较
    • 检索目录只用文件名
    • UNIX利用文件名和文件描述信息分开的方式
    • 文件目录中的每个目录项由文件名和指向该文件的指针构成
    • FCB很大，64B，一个盘快1KB只能放16个
    • 使用文件名加索引节点的组合可以实现16B就够了，然后通过索引结点找FCB
  • 磁盘索引节点
    • 存放在磁盘上的索引节点，每个文件有一个唯一的磁盘索引结点
      • 主文件标识符、文件类型、存取权限、物理地址、文件长度
      • 文件链接计数、文件存取时间
  • 内存索引节点
    • 文件被打开时，要将磁盘索引节点复制到内存的索引结点中，方便后续使用
      • 索引节点编号、状态（修改与否）、访问针数
      • 逻辑设备号（文件所属文件系统的逻辑设备号）
      • 链接指针：指向空闲链表和散列队列的指针

• 文件的操作：⭐️

  • 创建文件：为新文件分配必要的外存空间，创建一个目录项，记录了文件名、外存地址等
    • （系统调用）
  • 写文件：为文件维护一个写位置的指针（系统调用）
  • 读文件：为文件维护一个读位置的指针（系统调用）
  • 重新定位文件：文件定位，搜索目录找到适当的条目，将当前文件位置指针重定位
    • （不涉及读写）
  • 删除文件：释放存储空间，删除目录条目
  • 截断文件：文件所有属性不变，删除文件内容，长度设为0
  • 基本操作组合可以实现很多操作

• 文件的打开与关闭

  • 每次文件操作都需要检索目录
  • OS维护一个“打开文件表”
  • OS调用open根据文件名搜索目录
    • 将文件的属性（外存位置等）复制到文件的打开文件表的一个表目
    • 并将索引返回给用户
  • 用户再次文件操作，可以通过检索打开文件表查找文件信息，节省搜索目录开销
  • close关闭，对应删除打开文件表的条目
  • 多个不同进程可以同时打开文件的OS中，使用二级表
    • 进程打开文件表和系统打开文件表
    • A进程打开了文件，系统打开文件表增加条目，A进程的打开文件表表项指向系统表相应条目 ⭐️
  • 系统打开文件表为每个文件关联一个打开计数器Open和Count
  • 记录多少进程打开了这个文件，每次close，count递减，计数器为0时不再使用
  • P241 图很形象
    • 用户空间，read 索引到进程打开文件表，索引到系统打开表，索引到PCB和物理外存
  • 文件名不是打开文件表的一部分，完成磁盘定位，文件名就不用了
  • **于访问打开文件表的索引，UNIX称之为文件描述符，WIndows称为文件句柄 **
  • 打开文件表的信息：
    • 文件指针
    • 文件打开计数
    • 磁盘位置
    • 访问权限

• 文件保护（也是高层功能可以通过系统程序调用低层系统调用来实现）

  • 口令保护：口令在系统内部，不安全
  • 加密保护：需要密钥，编码译码需要时间
    • 这两种都没有控制访问类型
  • 访问控制
    • 访问控制列表，规定用户名以及所允许的访问类型
    • 拥有者：创建文件的
    • 组：一组需要共享文件且具有类似访问的用户
    • 其他：其他用户
    • 同一个用户组，同权限，否则其它权限
  • 等

• 文件逻辑结构（内部、数据逻辑如何组织）⭐️

  • 无结构文件（流式文件）：源程序文件，代码文件，字节为单位
  • 有结构文件（记录式文件）：
    • 顺序文件：磁带等、效率高，但在查找修改增加删除式性能差
    • 索引文件：定长记录可以计算、变长记录必须顺序查找
      • 可以建立索引表加快检索速度
    • 索引顺序文件：顺序文件和索引文件的集合，只用了简单的一级索引
      • 因为配置索引表增加了存储空间
      • 同一组的关键字无序、组之间关键字有序
    • 直接文件或散列文件：没有顺序特性，键值决定物理地址

• 文件物理结构（外部、文件分配方式：对磁盘非空闲块的管理、存储空间管理：空闲块）⭐️

  • 常用分配：连续分配、链接分配、索引分配
  • 连续分配
    • start length 要求每个文件在磁盘上有一组连续的块
    • 使作业访问磁盘时所需要的寻道数量和时间最小
    • 缺点很多，文件长度不能动态增加，删除插入很麻烦，外部碎片（因为增加删除文件），难以确定需要空间
  • 链接分配
    • 离散分配，消除外部碎片，提高磁盘可利用率
    • 无需知道文件大小，插入删除修改方便
      • 隐式链接：每个文件对应着一个磁盘块的链表，每个盘块有指向下一个的指针
        • 只适合顺序访问，稳定性容易出问题
        • 解决方案：几个盘块成一个簇，按簇分配，代价是内部碎片
      • 显式链接 ⭐️
        • 用于链接文件各物理块的指针从物理块末尾提取
        • 显式存放内存的链接表中，磁盘中也仅仅一张，叫文件分配表FAT
        • 盘快号 下一块
        • 文件目录中放起始块号
        • -1 就是表示结尾，-2 -3等就表示空闲
        • FAT在系统启动时就会被读入内存，因此查找记录在内存进行
        • 查找在内存完成，不仅提高检索速度，减少了访问磁盘次数
  • 索引分配
    • 解决了外部碎片和文件大小管理问题：不能有效支持访问（FAT除外）
    • FAT需要占用大量内存空间
    • 索引分配将文件所有盘快号放在一起构成索引块
    • 每个文件都有索引块，直接访问，没外部碎片
    • 索引块太小没法支持大文件索引
      • 链接：多个索引块链接
      • 多层索引：一级二级
      • 混合索引：高频考点
  • 混合索引分配
    • 先要从FCB中找到文件的索引表
    • 多级索引
    • 10个4KB 直接地址（为了提高文件检索速度）
    • 一个一次间接地址 1个4MB
    • 一个二次间接地址 1个4GB
    • 一个三次间接地址 1个4TB
  • 索引节点是FCB的改进
    • 目录表瘦身，只放文件名和指向索引节点（inode）的指针
    • 目录表的一条就是一个FCB 也相当于给FCB瘦身，但是FCB所包含的内容不变，多的内容靠指向的inode给出
    • 这样文件目录表中找到inode，inode找到其他所有的信息以及数据在外存的位置

• 不同目录下的文件名可以相同，最多创建文件数量只需要考虑索引节点数量上限

• 课后习题；

  • UNIX 设备文件视为特殊文件
  • 一个文件对应FCB，文件目录项就是一个FCB
  • 打开文件：指定文件的目录放到内存指定区域
  • 目录文件存放：目录中所有的子目录文件以及数据文件的目录
  • FAT文件目录项不包括 FCB的物理位置
    • 目录文件是FCB的集合
  • 相对于加密 访问控制机制安全性较差，灵活度高
  • 加密系统不是系统实现的，如果系统实现，就没法扩展了
  • 进入系统要注册，这一个安全管理是系统级的
  • 文件逻辑结构的范畴：见上方
  • FAT 文件分配表 包含：文件基本信息、存取控制信息和实用信息
    • 基本信息包含文件物理位置
  • 逻辑：流 / 记录（非结构 结构）：为了用户
  • 物理：连续 链接 索引：为了OS
  • 索引文件由逻辑文件和索引表组成
  • 逻辑索引为了加快数据定位：为了用户
  • 物理索引为了管理不连续的物理块：为了OS
  • 对索引文件存取 必须通过索引表，建立索引会增加额外存储，为的是快速定位
  • 顺序索引文件最好是根号分
  • 链式不能随机存取
  • 顺序文件：外部碎片
  • 启动磁盘次数要注意是否需要写回！！！！
  • 一个文件一张索引表
  • 读顺序文件：从FCB读出文件的第一个盘快号
  • 读索引文件：从FCB读出索引块的起始地址
  • 索引表只有相应记录的关键字和逻辑地址！！！！
    • 注意是逻辑地址
  • 一定要看清题目中的逻辑和物理两个字
  • read 文件不在内存 缺页中断 阻塞 需要切换核心
    • 不需要文件名 只需要fd文件描述符 buf缓冲区首地址 字节数
  • CD连续结构最优
  • 文件 会先FCB调入内存，进程希望获得文件内容才读入文件内容

• 大题没做没做没做没做没做

4.2 目录

• 实现按名存取、提高对目录检索速度、方便共享、方便用习惯命名

• FCB的有序集合称为文件目录

• 一个FCB就是一个文件目录项

• 目录管理通过树形结构来解决和实现（不同用户相同名字）

• 目录结构

  • 单级目录结构
    • 一个文件系统就一张目录表，一个文件就是一个目录项
    • 按名存取，慢，补充名，不便共享

  • 两级目录结构
    • 克服单级
    • 主文件目录和用户文件目录
    • 用户文件目录项记录了该用户的FCB，主文件目录记录User
    • 不灵活不能文件分类
  • 树形目录结构
    • /
      - dev home bin usr
      - 方便文件分类，结构清晰，方便保护
      - 查找文件需要按路径名逐级访问中间节点，增加磁盘访问次数
      - 影响查询速度，UNIX Linux Windows 都是树形文件目录
    • 无环图目录结构
    • 共享计数器：方便共享，管理复杂

• 目录的操作

  • 搜索
  • 创建文件：目录中增加一个目录项
  • 删除文件：删除目录项
  • 创建目录（包括子目录）
  • 删除目录
    • 不删非空白目录，除非文件都被删了，要递归删除子目录
    • 可删除非空白目录
  • 移动目录：文件的路径名也会随之改变
  • 显示目录
  • 修改目录

• 目录实现不考

• 文件共享

  • 为了多个用户共享同一个文件，只保留一个副本
  • 硬链接：基于索引节点的共享方式
    • 不同用户同一个文件，文件目录的索引节点指针指向 同一个索引节点
    • 索引节点中有count，用于表示链接到本索引节点的用户目录项的数目
    • count=0才删除
  • 软连接：用符号链实现文件共享
    • 为了B能共享A的一个文件F，创建一个LINK类型文件也叫F
    • 并将该文件写入用户B的目录中，实现用户B的目录和文件F的链接
    • 新文件只包含被链接文件的路径名，这就叫符号链接
    • 只有文件主才拥有指向索引节点的指针
    • 主文件删除了，其他用户通过符号访问就G了
    • 多次读盘，耗费磁盘空间
  • 都是静态共享方法，两个进程同一个文件操作叫动态共享
  • 硬比软快

• 课后习题：

  • 目录顺序检索，第一个分量没找到就说明不存在，不需要继续检索
  • 目录查询通常Hash 和 顺序检索 常用顺序
  • 属性目录可以从当前目录开始查找（因为设置了当前目录）
  • 找到的是逻辑地址
  • 相对路径当前目录 绝对路径跟目录
  • 多级目录为了解决命名冲突
  • 文件重名不能单级目录
  • 当前工作目录为了加快文件检索速度
  • 文件在磁带上连续存放，硬盘不连续，内存随机存放 所以同一个系统不同介质不同物理存储
  • 对文件的访问控制由用户访问权限和文件属性限制
  • 防止文件受损，用备份
  • 存取控制矩阵的方式用于多用户之间的存取权限保护
  • 符号链接直接复制引用计数，硬连接就+1，删除时对符号链接不可见
  • 目录：文件名+索引节点指针，指针指向索引节点，再通过索引节点找到文件
  • 软连接：目录中：文件名加索引节点指针，指针指向索引节点，通过索引节点找到LINK文件
    • LINK文件中存放原来的路径 实现共享索引节点
    • 硬+1 不一定会影响所有的软链接
  • 各进程可以同时读 同时写一个文件：读写指针可能不一样
    • 不同用户打开文件表内容不同

4.3 文件系统

• 文件系统结构

  • 应用程序
  • 逻辑文件系统
    • 管理元数据信息，包括文件系统所有结构不包含数据或文件内容
    • 管理目录结构，通过文件控制快来维护文件结构，文件保护
  • 文件组织模块
    • 组织文件及其逻辑块和物理块
    • 包括空闲空间管理器
  • 基本文件系统
    • 向设备驱动发送命令，以读取和写入磁盘的物理块
  • I/O控制
    • 设备驱动程序和中断处理程序，在内存和磁盘系统之间传递消息
    • 设备驱动程序将输入命令翻译成硬件指令，硬件控制器利用其交互
    • 设备驱动程序告诉I/O采取什么动作
  • 设备

• 文件系统布局

  • 一个磁盘划分成多个or一个区，每个分区一个独立文件系统
  • 一个文件系统
    • 主引导记录MBR：磁盘0号扇区，引导计算机
      • 启动时 BIOS读如并执行MBR
      • 确定活动分区，读入引导块（第一块）
    • 引导块：MBR执行引导块中程序后该程序负责启动该分区中的OS
    • 超级块：包含文件系统中所有关键信息，计算机启动时会被载入内存
      • 分区的块的数量，块的大小，空闲FCB数量，和FCB指针
    • 文件系统中空闲块的信息：

    • 文件系统在内存中的结构
      - 内存中的信息用于管理文件系统并通过缓存提高性能
      - 操作期间更新，卸载时被丢弃
      - 内存的安装表：包含每个已安装的文件系统分区的有关信息
      - 整个系统的打开文件表：打开文件的FCB副本及其他信息
      - 每个进程的打开文件表： 指向系统的打开文件表的适当条目指针

• 外存空闲空间管理

  • 空闲表法：第一个空闲盘快号，空闲盘快数
  • 空闲链表法：
    • 空闲盘块链：所有空闲空间以盘块为单位拉成一条链
    • 空闲盘区链：空闲盘区拉成一条链（一个盘区可以报刊若干盘块）
      • （首次适应 最佳适应等策略）
  • 位视图法：二维数组01
  • 成组链接法（需要补笔记）
    • 分配：根据第一个成组链接块的指针将对应盘块分配用户，指针下移
    • 回收：指针上移
    • 视频理解 估计不容易考 因为很难描述 记得学会复制到新的块就好了
  • 表示空闲空的向量or第一个成组链块都要放在磁盘中的卷头，超级块

• 虚拟文件系统VFS

  • 为用户程序提供了文件系统操作的统一接口
  • 屏蔽了不同文件系统的差异和操作细节
  • 内核空间
  • 面向对象思想
  • 每个VFS对象都存放在一个适合的数据结构，包括对象 ⭐️
    • 超级块对象：对应特定扇区文件系统的超级块
    • 索引节点对象：对文件为宜
    • 目录项对象：VFS经常执行切换到某个目录，为了提高效率就引入了目录项
    • 文件对象：进程打开的一个文件
    • P280 图非常清晰（进程和VFS对象之间的交互）
  • 提高系统性能
    • 加速文件路径名到最后一个路径分量的索引节点的转换过程
  • VFS 系统启动时建立，关闭时消亡
  • 只存在于内存中
  • 抽象出了一个通用的文件系统模型，定义了通用文件系统都支持的接口
  • 文件系统只要支持并实现了接口就可以安装使用。
  • 用户空间 到 VFS 到 文件系统 到 物理介质1

• 分区和安装

  • 文件系统在进程使用之前必须安装，也叫挂载 mount 卸载文件系统umount
  • Linux启动后，先载入MBR，随后MBR识别活动分区，加载引导程序
  • UNIX本身是一个固定的目录树，只要安装就有
  • 要给根目录分配空间才能操作这棵树

• 课后习题：

  • OS：文件系统负责对文件存储空间进行组织分配管理保护检索
  • 用户：按名存取
  • 超级块用来描述文件系统
  • 位图 位示图 很重要
    • 位示图还能管理内存 还能管理磁盘
  • FAT 兼职磁盘空闲管理
    • 成组链接
    • 空闲盘区
    • 空闲盘块
    • 位视图
    • 空闲表法

C5 I/O管理

5.1 I/O管理概述

• 操作系统对主机外部的设备进行管理

• 数据输入到计算机或者接受计算机输出数据的外部设备

• UNIX把外部设备抽象成一种特殊的文件，用户可以使用与文件操作相同的方式来对外部设备操作

• 设备分类

  • 使用特性
    • 人机交互型外设
    • 存储设备
    • 网络通信设备
  • 速率
    • 低速 鼠标键盘
    • 中速 激光打印机
    • 高速 磁盘等
  • 信息交换的单位
    • 块设备：数据交换的基本单位是块：移动硬盘
    • 字符设备：数据交换的基本单位是字符or字节：鼠标键盘
      • 中断驱动

• 需要一个电子部件作为CPU和I/O设备的中介，实现控制，I/O控制器

  • 接受和识别CPU发出的命令：控制寄存器：存放命令和参数
  • 向CPU报告设备的状态：状态寄存器：记录I/O设备当前状态
  • 数据交换：数据寄存器：暂存CPU发过来的数据
  • 地址识别：为了区别控制器中的各个寄存器，要给每个寄存器一个特定地址
    • 需要通过CPU给出的地址来判断读写哪个寄存器 （I/O逻辑）

• 为了实现CPU与I/O端口进行通信，可以

  • 独立编址（内存印象I/O）
    • 只有操作系统特殊指令才能访问端口
  • 统一编址
    • 端口被分配唯一内存地址

• I/O控制方式⭐️

  • （注意一次读写操作流程、注意CPU干预的频率、注意数据传送的单位、数据流向、主要缺点和主要优点）
  • 程序直接控制方式
    • 轮询
    • CPU频繁干预，I/O开始结束都要CPU介入
    • 等待I/O的完成过程中需要不断的轮询检查
    • 简单，但是CPU需要一直轮询检查，长期忙碌状态
    • 读数据，数据输入：I/O设备 CPU 内存
    • 写数据，数据输出：反一反
  • 中断驱动方式
    • 引入中断机构，发出读命令后CPU可以做其他事情
    • I/O完成后，会向CPU发出中断信号
    • CPU监测到中断信号就执行中断处理程序处理该中断
    • 处理完毕后恢复原来的运行环境
    • CPU会在每个指令周期末尾检查中断
    • 中断处理过程中需要保存、回复进程的运行换进
    • 过程需要一定的开销，因此中断频率过高就会降低系统性能
    • 每次读写一个字
    • 读数据，数据输入：I/O设备 CPU 内存
    • 写数据，数据输出：反一反
  • DMA方式（直接存储器存取）
    • 数据单位是块（只能读写连续的块、读入内存在内存中也要连续）
    • 数据流向不用经过CPU，而是直接放到内存里或者直接内存放设备
    • 传送一个数据块的开始或者结束CPU才需要干预
    • DMA控制器代为完成
    • CPU告诉DMA要多少，放什么位置，全部结束才中断CPU
    • DMA控制器也是一种I/O控制器
  • 通道控制方式
    • 通道是一种硬件
    • 很弱的CPU，CPU内存通道系统总线连接
    • CPU向通道发出I/O，指明通道程序在内存中的位置
    • 指明要操作哪个I/O设备，之后CPU就切换走了
    • 通道执行内存中的通道程序（指明需要读写多少数据，数据在哪，任务清单）
    • 通道可以识别一系列通道指令，任务清单是CPU写的，通道指令构成
    • 读写完成后才中断，一次一组数据块
    • 知识点回顾和重要考点在5_1_3结尾

• I/O软件层次结构（封装思想）⭐️

  • 软件层次
    • 用户层软件（用户通过库函数操作用户层软件）
      • 字符设备接口
        • get读
        • put写
      • 块设备接口
        • read
        • write
        • 需要提供地址参数
      • 网络设备接口
        • socket
        • read
        • write
        • connect 连接远程主机

    • 操作系统内核层次（用户层软件通过锡荣调用往下走）
      • 设备独立性软件
        • 需要提供调用接口 read write等
        • 需要提供设备保护 不同用户不同
        • 差错处理
        • 设备分配回收
        • 数据缓冲区管理
        • 建立逻辑设备名道物理设备名的映射关系
        • 根据设备类型调用相应的驱动程序
          • 调用时需要指明逻辑设备名
          • 映射关系 逻辑设备表
      • 设备驱动程序
      • 中断处理程序
    • 新考点，OS规定好设备驱动程序的接口标准，厂商必须按要求开发设备驱动
  • 硬件层次
    • 硬件
  • 涉及硬件具体细节、且与终端无关的操作肯定是设备驱动程序完成的
  • 没有涉及硬件，对各种设备的管理通过设备独立性软件层

• 阻塞/非阻塞I/O

  • 阻塞 sacnf
  • 非阻塞 往磁盘写数据write

• 用户层软件

  • 假脱机技术（SPOOLing技术） （408归为I/O核心子系统实现的）
    • 脱机技术
      • 一开始输入输出很慢 纸带
      • 批处理阶段引入脱机技术：磁带、已经快很多
    • 假脱机就是用软件方式模拟脱机技术（输入进程输出进程）
      • 需要和用户程序并发，需要多道程序处理
      • 输入设备输出设备
      • 内存中、输入缓冲区输出缓冲区 中转站
      • 磁盘中、输入井输出井
    • 共享打印机
      • 多用户提出打印机
      • 系统都打印但不直接打印
      • 同意了以后再内存开辟缓冲区
      • 打印请求表（说明用户打印数据的位置）挂在假脱机文件队列

• I/O核心子系统

  • 设备独立性软件
    • I/O调度
      • 磁盘调度 ⭐️

    • 设备保护
      • 设备看成文件，建立FCB

    • 设备分配与回收
    • 缓冲区管理

  • 设备驱动程序

  • 中断处理程序

  • 这三个属于OS内核部分，也叫I/O核心子系统
  • 就是实现这三个

• OS可以采用两种方式管理逻辑设备表LUT

  • 整个系统一张LUT，只适合单用户OS
  • 每个用户一个LUT，不用用户可以同样逻辑设备名
    • 用户登录时建立用户管理进程，LUT存放在用户管理进程的PCB中
  • LUT中包含逻辑设备名 物理设备名 驱动程序入口地址

• 设备分配时应该考虑的因素

  • 设备的固有属性
    • 独占设备
    • 共享设备
    • 虚拟设备（SPOOLing独占改造成虚拟的共享）
  • 设备分配算法
    • 各种算法
  • 设备分配中的安全性
    • 安全分配算法
    • 不安全分配算法（死锁、需要避免、检测、解除）
    • 动态分配 静态分配

• 需要的数据结构

  • 通道控制多个控制器，控制器控制多个设备
  • 设备控制表DCT：一个设备一个DCT
    • 设备类型
    • 设备标识符：物理设备名 唯一
    • 设备状态：空闲忙碌
    • 指向控制器表的指针：一个设备一个控制器控制，找到相应控制器的信息
    • 重复执行的时间次数
    • 设备队列的队首指针 ：等待队列
  • 控制器控制表COCT：一个设备控制器对应一张COCT
    • 控制器标识符
    • 控制器状态
    • 从属通道
    • 控制器队列的队首指针
    • 队尾指针
  • 通道控制表CHCT：一个通道对应一张CHCT
    • 通道标识符
    • 通道状态
    • 与通道连接的控制器表的起始地址：找到所有控制器
    • 通道队列首尾指针
  • 系统设备表 SDT：记录了全部设备的情况，一个设备一个表目
    • 表目12345
    • 一个表目
      • 设备类型
      • 设备标识符
      • DCT（上面）
      • 驱动程序入口

• 设备分配的步骤

  • 根据进程请求的物理设备名查找SDT，SDT中一个表项中存放DCT
  • 找到DCT判断设备是否空闲，不忙碌就把设备分配给进程
  • 根据DCT找到COCT，控制器忙碌就将该进程PCB挂到控制器等待队列中，不忙碌分配控制器给进程
  • 根据COCT找到CHCT，通道忙碌挂在PCB通道等待队列，不忙碌就分配通道
  • 设备、控制器、通道都成功才成功，之后可以启动I/O
  • 缺点：
    • 用户必须使用物理设备名，不方便变成
    • 换一个物理设备就不能运行
    • 即使同类型设备，也必须阻塞
  • 改进：建立逻辑设备名到物理设备名的映射
    • 用户给逻辑设备名就是设备类型
    • 查找SDT，找到制定类型空闲设备，并分配
    • LUT新建一个表项（逻辑设备名、物理设备名、驱动程序入口地址）
    • 第一次需要新建表项
    • 后面不需要每一次访问都新建一个表项
    • LUT表的张数决定了各个用户逻辑设备名是否允许重复

• 缓冲区管理：

  • 可以硬件组成也可以利用内存
  • 快表
  • 内存作为缓冲区：
    • 缓和CPU和I/O设备速度不匹配的问题
    • 减少对CPU中断频率，放宽中断时间的限制
    • 解决颗粒度不匹配
    • 提高CPU与I/O设备之间的并行性

• 单缓冲（看TC 平均一个max（C，T）+M）

  • 单缓冲策略，OS在主存分配一个缓冲区（没说明就是一个块）
  • 非空不能冲，只能出
  • 为空不能传，只能冲
  • 计算处理数据的平均时间：假定一个初始状态，下次到这块的时间
    • （工作区满，缓冲区空）

• 双缓冲（T和C+M比较） 取大的

• 循环缓冲队列

• 缓冲池：

  • 很多缓冲区的池
  • 空缓冲队列
  • 输入队列
  • 输出队列
  • 几个东西
  • 用于收容输入数据的工作缓冲区的hin
  • 用于提取输入数据的工作缓冲区sin
  • 用于收容输出数据 hout
  • 用于提出输出数据 sout

5.x 磁盘与固态硬盘