操作系统【视频】

第一章 计算机系统概述

一.操作系统的基本概念和发展历程

1.操作系统的概念&功能

• 操作系统的概念

  操作系统：是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配：以提供给用户和其他软件方便的接口和环境；他是计算机系统中最基本的系统软件

• 操作系统的功能和目标

  • 功能一：作为系统资源的管理者

    1. 处理机管理
    2. 存储器管理
    3. 文件管理
    4. 设备管理

  • 功能二：向上层提供方便易用的服务

    1. 给用户提供的

       GUI：图形用户界面

       命令接口：联机命令接口（交互式命令接口），脱机命令接口（批处理命令接口）

       注：也有教材把命令接口和程序接口叫做用户接口

    2. 给程序员提供的

       程序接口：由一堆系统调用组成，用户通过程序间接使用

  • 功能三：作为最接近硬件的软件

    实现了对硬件机器的拓展，通常把没有任何软件支持的计算机称为裸机，覆盖了软件的机器称为扩充机器，又叫虚拟机

2.操作系统的特征

• 并发：宏观上是同时发生的，微观上是交替发生的

  并发与共享是操作系统最基本的特征，并发和共享互为存在条件，没有并发和共享，谈不上虚拟和异步

• 共享

  • 两种资源共享方式

    1. 互斥共享方式：一个时间段只允许一个进程访问该资源
    2. 同时共享方式：一个时间段内允许多个进程“同时”访问 可能是并发

• 虚拟

  • 虚拟技术

    1. 空分复用技术：如虚拟存储器技术
    2. 时分复用技术：如虚拟处理器

• 异步

  异步：多道程序环境下，进程的执行不是一贯到底，而是走走停停，不可预知的速度前进 真心只有一个，给你她就等

3.操作系统的发展和分类

• 手工操作阶段

  用纸带编程
  缺点：用户独占全机，人机速度矛盾导致资源利用率低

• 批处理阶段-单道批处理技术

  引入脱机/输出技术
  缺点：内存仅有一到程序运行，CPU 有大量时间空闲 输入输出时间占多数，CPU 一下就运行完了

• 批处理阶段-多道批处理技术

  多道程序并发执行，共享计算机资源 流水线
  缺点：用户响应时间长*，*没有人机交互功能

• 分时操作系统

  计算机以时间片为单位为各个用户/作业服务
  缺点：不能处理一些紧急任务

• 实时操作系统

  硬实时系统：导弹控制，必须严格控制时间
  软实时系统：车票系统

• 其他操作系统

  • 网络操作系统：实现资源共享和计算机通信 如 windows nt 就是一种网络操作系统，网络服务器可使用
  • 分布式操作系统：主要特点是分布性和并行性，工作都可以分布在这些计算机上，让他们并行、协同完成任务
  • 个人计算机操作系统：如 window xp

二.操作系统运行环境

1.操作系统的运行机制

• 内核程序&应用程序

  • 内核程序构成了操作系统内核，可以使用特权指令

• 特权指令&非特权指令

  • 特权指令只能由内核程序执行
  • 应用程序只能执行非特权指令

• 内核态&用户态 ​​PSW 里面一个二进制位来实现

  • CPU 处于内核态说明正在运行内核程序，可以执行特权指令 ​ 管态
    CPU 处于用户态说明正在运行应用程序，只能执行非特权指令 目态

  • 内核态用户态的切换

    内核态\to用户态：实行一条特权指令，修改 PSW 标志位为用户态，操作系统主动让出 CPU 使用权

    用户态\to内核态：由“中断”引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺取 CPU 的使用权

2.中断和异常

• 中断的作用

  • 中断是让操作系统夺回 CPU 使用权的唯一途径

• 中断的类型

  • 内中断（也叫异常）

    1. 陷阱，陷入：由陷入指令引发，应用程序故意的
    2. 故障：错误条件引发的，可以被内核程序修复，如缺页故障
    3. 终止：致命错误，内核无法修复，不再归还 CPU 使用权，直接嘎掉应用程序 ​ 整数除以 0

    与当前执行的指令有关，中断信号来源于 CPU 内部
    例如：
    用户态下发现一条特权指令
    除法运算除数为 0
    陷入指令（trap 指令/访管指令）：一个特殊指令，不是特权指令，由用户程序执行，主动让出 CPU

  • 外中断

    1. 时钟中断
    2. I/O 中断请求

    与当前执行的指令无关，中断信号来源于 CPU 外部

    例如：
    时钟中断：比如进程的并发，时间片到了，时钟就会发来一个时钟中断
    I/O 设备的中断信号：比如打印机打完了，会发一个中断信号告诉 CPU

• 中断机制的基本原理

  CPU 检测到中断信号后，根据信号查询【中断向量表】，凭借表找到相应中断处理程序在内存中的存放位置

3.系统调用

• 什么是系统调用，有什么用？

  系统调用是应用程序请求系统服务的唯一途径
  系统调用和库函数的区别：比库函数更加底层

• 为什么系统调用是必须的？什么样的功能要用到系统调用?

  打印机例子，实现资源的互斥共享

  凡是与资源共享有关的操作，都需要通过系统调用，保证稳定性和安全性

• 系统调用的分类（按功能分类）【不重要】

  • 设备管理
  • 文件管理
  • 进程控制
  • 进程通信
  • 内存管理

• 系统调用的过程

  应用程序使用传参指令，给 CPU 的寄存器传入参数
  应用程序使用陷入指令引发内中断
  CPU 执行系统调用入口程序（中断处理程序），根据参数代用特定的处理程序
  操作系统归还 CPU 使用权，CPU 回到用户态

三.操作系统的体系结构&引导&虚拟机

1.操作系统体系结构

• 计算机系统的层次结构

  

  时钟管理：利用时钟中断实现计时功能
  原语：一种特殊的程序，具有【原子性】，运行无法被【中断】

• （各种）操作系统的体系结构

  1. 大内核与微内核

     

     大内核：将操作系统的主要功能模块都作为系统内核 大内核通常也才有模块化设计思想
     优点：高性能，内核中各模块可互相调用
     缺点：

     1. 内核代码庞大，结构混乱，难以维护
     2. 但内核某个功能模块出错，可能导致系统崩溃

     微弱内核：只把最基本的功能保留在内核 中断、原语、进程通信等
     优点：

     1. 内核功能少，结构清晰，方便维护
     2. 某个模块出错不会导致系统崩溃

     缺点：

     1. 需要频繁的在核心态和用户态之间切换 因为进程管理、存储管理、设备管理都需要内核的支持
     2. 用户态下各个功能模块不能互相调用，只能通过内核的【消息传递】机制间接通信

  2. 分层结构&模块化&外核

     

     特性与思想：内核分为多层，每层只能单向调用相邻的更低的一层的接口

     优点：

     1. 便于调试验证：只需要自底向上逐层调试验证
     2. 易扩充易维护：各层之间接口调用情况清晰 如果在里面加一层，只需实现原来层提供的接口

     缺点：

     1. 仅能调用相邻的低层，难以合理定义各层的边界 这些功能很复杂，很难分成这种多层​
     2. 效率低，不能跨层调用，系统调用执行时间长 调用只能一层一层

  3. 模块化

     

     特性与思想：内核划分为多个模块，各个模块之间协作

     1. 内核=主模块 + 可加载内核模块
     2. 主模块：负责核心功能 如进程调度、内存管理等
     3. 可加载内核模块：可以动态的加载新模块到内核，无需编译整个内核 如驱动程序

     优点：

     1. 模块间逻辑清晰易于维护，确定接口后可多模块同时开发
     2. 支持动态加载新内核模块，增强 OS 适应性
     3. 任何模块都可以直接调用其他模块，无需采用消息传递进行通信，效率高 像微内核就必须使用消息传递

     缺点：

     1. 模块间的接口定义未必合理、实用 虽然能按照功能分模块， 但是问题比较复杂，后面可能冒出很多问题
     2. 模块间相互依赖，难以调试和验证

  4. 外核

     

     特性与思想：内核负责进程调度、进程通信等功能，外核负责为用户进程分配未经抽象的硬件资源，且由外核负责保证资源使用安全

     优点：

     1. 外核可直接给用户进场分配【不虚拟 不抽象】的硬件资源，使用户进程可更灵活的使用硬件资源
     2. 减少了虚拟硬件资源的【映射层】，提升效率

     缺点：

     1. 降低了系统的一致性 有的程序是虚拟的地址空间，有的又不是
     2. 使系统变得更复杂

     图中 library 表示应用程序的库，kernel 表示内核，exokernel 表示外核，应用程序通过库可以调用内核功能，也可调用外核功能

     抽象的硬件资源：用户程序看到的连续的存储空间其实是由操作系统虚拟化的，实际上它们在内存/磁盘中的真实地址可能是连续的，采用外核，用户程序可以申请一篇连续的未抽象的实际存储空间，避免磁头来回跳跃，提高

2.操作系统的引导

• 操作系统的引导（开机过程）

  • 一个安装了操作系统的磁盘长啥样？

    

    磁盘除了分区还有一部分存了【主引导记录 MBR】包含：

    1. 磁盘引导程序

    2. 分区表：指明了各个分区以及活动分区的位置与大小 一种数据结构

       • 活动分区：操作系统装在哪个分区，哪个就是活动分区

    活动分区 C 盘除了目录还有一部分存了【引导记录 PBR】：执行其中的程序，可以找到根目录下的【启动管理器】

    开机过程

    1. 从特定的地址（ROM 引导程序）开始，硬件自检开机
    2. 将主引导记录 MBR 读入内存，执行磁盘引导程序：扫描分区表，找到活动分区
    3. 从活动分区读入引导记录，执行其中的程序：从根目录下读取启动管理器
    4. 启动管理器完成初始化工作，开机

3.虚拟机

• 虚拟机的概念

  虚拟机：使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器，每台虚拟机器都可以独立运行一个操作系统

  同义属于：虚拟机管理程序/虚拟机监控程序/VMM

• 两类虚拟机管理程序

  

• 两类虚拟机管理程序对比

  

第二章 进程与线程

一.进程与线程

1.进程的概念&组成&特征

• 进程的概念

  程序：​静态的，存放在磁盘​进程：​动态的，进程实体的运行过程，系统进行​资源分配​和​调度的一个独立单位
  **进程实体（进程映像）：**​静态的，相当于进程的某一刻快照，由****​PCB，程序段，数据段构成

• 进程的组成

  • PCB（进程存在的唯一标志）

    1. 进程描述信息
    2. 进程控制和管理信息
    3. 资源分配清单
    4. 处理机相关信息

  • 程序段

    程序的代码段

  • 数据段

    运行过程中产生的数据

• 进程的特征【不重要】

  • 动态性：进程是程序的一次动态的执行过程
  • 并发性：内存中有多个进程实体
  • 独立性：独立获得资源，接受调度的基本单位
  • 异步性：各个进程之间是异步的
  • 结构性：每个进程都有自己的 PCB,程序段,数据段

2.进程的状态与转换

• 进程的状态

  • 创建态
  • 就绪态
  • 运行态
  • 阻塞态
  • 终止态

• 进程状态的转换

  

• 进程的组织

  • 链接方式：把各个状态的进程的 PCB 分类挂在不同的队列
  • 索引方式：根据进程状态的不同，建立不同的索引表，操作系统持有指向各表的指针

3.进程控制

• 什么是进程控制？

  本质就是实现进程各个状态的转换

• 如何实现进程控制？

  需要使用原语，实现进程转换必须一气呵成，不然可能会出错

• 如何实现【原语】的【原子性】

  • 使用【关中断指令】和【开中断指令】两条特权指令实现原子性

    CPU 执行完一条指令后会例行检查中断信号
    使用【关中断指令后】CPU 便不再例行检查

• 进程控制相关原语

  • 进程的创建

    创建原语：
    申请空白 PCB
    为新进程分配所需资源
    初始化 PCB
    将 PCB 插入就绪队列

    引起进程创建的事件：
    用户登录：分时系统中，用户登录成功，系统会为其建立一个新的进程
    作业调度：多道批处理系统中，有新的作业放入内存中，会为其建立一个新的进程
    提供服务：用户向操作系统提出某些请求是，会建立一个进程处理该请求
    应用请求：有用户进程主动请求创建一个子进程

  • 进程的终止

    撤销原语：
    从 PCB 集合中找到终止进程的 PCB
    若进程正在运行，立即剥夺 CPU，将 CPU 分配给其他进程
    终止其所有子进程
    将该进程拥有的所有资源归还父进程或操作系统
    删除 PCB

    引起进程终止事件：

    ​ 正常结束：自己请求终止 exit 系统调用
    ​ 异常结束
    ​ 外界干预：用户管理器关掉

  • 进程的阻塞

    阻塞原语：
    找到要阻塞的进程对应的 PCB
    保护进程运行现场，将 PCB 状态信息设置为“阻塞态”，暂时停止进程运行
    将 PCB 插入相应事件的等待队列

    引起进程阻塞的事件：

    ​ 需要等待系统分配某种资源
    ​ 需要等待系统分配某种资源

  • 进程的唤醒

    唤醒原语：

    ​ 在等待队列中找到 PCB
    ​ 将 PCB 从等待队列中溢出，设置进程状态为就绪态
    ​ 将 PCB 插入就绪队列，等待被调度

    引起进程唤醒的事件：

    ​ 等待的事件发生【唤醒原语必须与阻塞原语成对，否则永远阻塞】

  • 进程的切换

    切换原语：
    将运行环境信息存入 PCB
    PCB 移入相应队列
    徐泽另一个进程执行，并更新其 PCB
    根据 PCB 恢复新进程所需的运行环境

    引起进程切换的事件
    当前进程时间片到
    有更高优先级的进程到达
    当前进程主动阻塞
    当前进程终止

4.进程通信

• 为什么进程通信需要操作系统支持？

  因为进程是分配资源的单位，各个进程拥有的内存地址空间相互独立，这是为安全考虑

• 进程通信的三种方式

  • 共享存储

    

    为了实现互斥的共享存储区，操作系统会提供一些操作，如 P/V 操作

    共享存储又可以划分为

    基于存储区的共享：​操作系统在内存划出一块共享存储区，这种共享方式速度很快，是一种​高级通信方式
    基于数据结构的共享：​比如共享空间里只能放一个长度为 10 的数组，这种共享方式速度慢，限制多，是​一种低级通信的方式

  • 消息传递

    进程间的数据交换以格式化的消息为单位，进程通过操作系统的【发送消息/接受消息】两个原语进行数据交换

    1. 直接通信方式

       

       P 使用发送原语，发一个格式化的消息，指明是发给 Q 的
       这个消息挂到内核区 Q 的消息对列
       Q 使用接受原语，指明要接受 Q 的消息
       操作系统吧消息给 Q

    2. 间接通信方式（信箱通信方式）

       

       P 使用系统调用申请一个邮箱，使用发送原语指明一个邮箱，发送格式化消息
       Q 使用接受原语指明接受一个邮箱的消息

       通常操作系统允许多个进程往同一个信箱发送消息，也支持多个进程从一个信箱里读消息

  • 管道通信

    

    管道和共享存储区的区别：管道是有方向的，一定是先进先出的
    管道由进程系统调用申请，本质就是一个固定大小的内存缓冲区
    管道只能支持半双工通信，若要双向同时通信，必须使用两个管道
    各个进程要互斥的访问管道（由操作系统实现）
    当管道写满时，写进程将阻塞，直到读进程取走数据，反之同理
    管道中的数据一旦读出，数据消失【故一个管道允许多个写进程，一个读进程】

5.线程的概念

• 什么是线程，为什么要引入线程？

  有的进程可能需要【同时】做很多事情，引入线程可以增加系统的并发度

• 引入线程机制后，会带来什么变化？

  线程机制带来的变化
  资源分配，调度变化	传统进程机制中，进程是资源分配，调度的基本单位 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
  并发性	传统进程机制中，只支持进程间并发 引入线程后，各线程间也能并发，提升了并发度
  系统开销	传统的进程间并发，需要切换进程的运行环境，系统开销大 线程间并发，如果属于同一进程，不需要切换进程环境，开销小

• 线程的属性

  线程是处理机调度的单位
  多 CPU 计算机中，各个线程可占用不同的 CPU
  每个线程都有一个线程 ID，线程控制块 TCB
  线程也有【就绪】【阻塞】【运行】三中基本状态
  线程几乎不拥有系统资源
  统一进程的不同线程间共享进程的资源
  由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
  同一进程中的线程切换，不会引起进程切换
  不同进程中的线程切换，会引起进程切换
  切换同进程内的线程，系统开销小
  切换进程，系统开销大

6.线程的实现方式&多线程模型

• 线程的实现方式

  • 用户级线程

    早期的操作系统，只支持进程，这种“线程”相当于一段代码逻辑，操作系统意识不到“线程”的存在，由线程库实现。
    优点：线程切换，不需要 CPU 变态，开销小
    缺点：一个线程被阻塞，整个进程所有线程都被阻塞；线程不可以在多核处理器上并行

  • 内核级线程（内核级线程才是 CPU 分配的单位，用户级不是）

    内核级线程的管理工作由操作系统内核完成
    内核级线程的切换需要在核心态下才能完成
    优点：一个线程被阻塞，别的线程还可以执行；多线程可以在多核并行
    缺点：切换线程需要变态，开销大

• 多线程模型

  • 一对一模型

    

    就相当于内核级线程

    优点：一个线程被阻塞，别的线程还可以执行；多线程可以在多核并行
    缺点：切换线程需要变态，开销大

  • 多对一模型

    

    就相当于用户级线程

    优点：线程切换，不需要 CPU 变态，开销小
    缺点：一个线程被阻塞，整个进程所有线程都被阻塞；线程不可以在多核处理器上并行，并发度不高

  • 多对多模型

    

    内核级线程数量少于用户级：这样可以减少变态的开销
    内核级的数量大于 1：这样可以防止一个阻塞，全员阻塞；提高并发度

7.线程的状态和转换

• 线程的状态与转换（基本和进程一样）

  ​​

• 线程的组织和控制

  ​​

  可以将多个 TCB 组织成一张线程表

二.处理机调度

1.处理机调度的概念&层次

• 调度的基本概念

  由于资源有限，需要使用某种规则决定任务的顺序

• 调度的三个层次

  • 高级调度（作业调度）

    按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。
    每个作业只调入一次，调出一次

  • 低级调度（进程调度/处理机调度）

    按某种策略从就绪队列中选取一个进程，将处理机分配给他
    进程调度是操作系统中最基本的一种调度，频率很高

  • 中级调度（内存调度）

    内存不足时，操作系统会吧某些进程数据暂时调入外存，使其变为【挂起状态】
    在外存中【挂起队列】重新调入内存的就是中级调度

    补充：进程的挂起状态
    进程的挂起状态又分为【就绪挂起】，【阻塞挂起】
    【挂起】和【阻塞】的区别：【挂起】的进程映像调入外存了

  • 三层调度的对比

    ​​

2.进程调度的时机&切换与过程&调度方式

• 进程调度的时机

  • 需要进行进程调度和切换的情况

    当前运行的进程主动放弃处理机
    1.进程正常终止
    2.运行过程中发生异常而终止
    3.进程主动请求阻塞

    当前运行的进程被迫放弃处理机

    ​ 1.分给进程的时间片用完
    ​ 2.运行过程中发生异常而终止
    ​ 3.有更高优先级的进程进入就绪队列

  • 不能进行进程调度与切换的情况

    1.处理中断的过程中
    2.进程在操作系统内核程序临界区中
    3.在原子操作过程中

    什么是操作系统内核程序临界区？
    **临界资源：**一个时间段只允许一个进程访问的资源，各个进程需要互斥的访问
    临界区： 访问临界资源的那段代码
    操作系统内核临济区可能访问的是就绪队列这个临界资源，为了互斥的访问，一般会将临界资源即就绪队列上锁，此时进程调度必然失败。但是如果是普通的临界资源，比如打印机，总不能让打印机霸占 CPU 把，所以这时候可以进程调度的

• 进程调度的方式

  • 非剥夺调度方式（非抢占式）

    只允许进程主动放弃处理机
    优点：实现简单，开销小，适用于早起的批处理系统
    缺点：没有办法处理紧急任务

  • 剥夺调度方式（抢占式）

    允许进程被迫放弃处理机
    优点：可以优先处理紧急进程，也可以按时间片分时（时钟中断），适用于分时操作系统，实时操作系统

• 进程的切换与过程

  1. 对原来运行进程的各种数据的保存
  2. 对新的进程的各种数据的恢复

  注意：
  狭义的进程调度：就是从就绪队列选一个要运行的进程，如果不是同一个就需要进程切换
  广义的进程调度：包含了选择和进程切换两个步骤

3.调度器&闲逛程序

• 调度器/调度程序

  

  • ②③ 由调度程序引起，调度程序决定

    1. 让谁运行：调度算法
    2. 运行多长时间：时间片大小

  • 调度的对象：内核级线程/进程

  • 什么事件会触发调度程序

    就绪队列改变：如 I/O 中断将阻塞唤醒，创建新进程

    进程退出/阻塞：CPU 空出来了

    注意：
    非抢占式调度策略：只有进程阻塞/退出才会触发调度程序
    抢占式调度策略：每个时钟中断都会触发调度程序

• 闲逛进程

  没有其他就绪进程时，就会运行闲逛进程

  特性：
  1.优先级最低
  2.可以 0 地址指令，占一个完整的指令周期（指令周期末位例行检查中断）
  3.能耗低

4.调度算法的评价指标

• CPU 利用率

  利用率=\Large\frac{忙碌的时间}{总时间}

• 系统吞吐量

  系统吞吐量=\Large\frac{总共完成了多少道作业}{总共花了多少时间}

• 周转时间

  • 概念：作业被提交给系统开始，到作业完成为止的时间
  • 周转时间=作业完成时间-作业提交时间
  • 平均周转时间=\Large \frac{各作业周转时间之和}{作业数}
  • 带权周转时间=\Large\frac{作业周转时间}{作业实际运行时间}
  • 平均带权周转时间=\Large \frac{各带权作业周转时间之和}{作业数}

• 等待时间

  • 概念：指进程/作业处于等待处理机状态【被服务】时间之和

    对于进程： 等待时间就是进程建立后等待被服务的时间之和，在等待 I/O 完成的期间其实也是被服务的，不计入等待时间
    **对于作业：**不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中的等待时间

• 响应时间

  • 用户提出请求到首次产生响应所用的时间

5.调度算法

① 适合早期批处理系统

这三种算法只关心算法的平均等待时间与平均周转时间，不关心响应时间，不区分任务紧急程度

(1)先来先服务 FCFS

(2)短作业优先 SJF

• 非抢占式 SPF

  ​​

• 抢占式 SRTN

  

  1.题目未说明，默认是非抢占式
  2.课本说 SJF 调度算法的平均等待时间，平均周转时间最少，应该加上一个条件：所有进程几乎同时到达，不加的话 SRTN 调度算法才是最短的
  3.SJF 仍比 FCFS 平均等待时间，平均周转时间少

(3)高响应比优先 HRRN

② 适合交互式系统

常用于分时操作系统，更关心响应时间，一般不计算平均等待/周转时间

(1)时间片轮转 RR

若时间片太大，时间片轮转算法退化为先来先服务，增加进程响应时间
若时间片太小，进程切换过于频繁，开销大

(2)优先级调度算法

• 补充

  • 就绪队列未必只有一个，可以吧优先级更高的进程排在靠近队头的位置

  • 根据优先级是否可以动态改变

    1. 静态优先级：创建进程时确定，之后不改变

    2. 动态优先级：创建进程有一个初始值，后续根据情况动态调整

       如果在就绪队列排了很久，可以适当提高优先级
       如果进程占用处理机很久，可以适当降低优先级
       如果一个进程频繁进行 I/O 操作，可以适当提升优先级

       注：通常情况
       1.系统进程优先级高于用户进程
       2.前台进程优先级高于后台进程
       3.操作系统更偏好 I/O 型进程（I/O 繁忙型进程）

       与 I/O 繁忙型进程相对的是计算型进程，I/O 进程可以和 CPU 并行工作，所以偏好它

• 抢占式

  

• 抢占式

  

(3)多级反馈队列调度算法

③ 多级队列调度算法

(1)多级队列调度算法

• 队列之间可采用
  • 固定优先级：只有高优先级空，低优先级进程才可能被调度【明显不合理】
  • 时间片划分：如三个队列分配时间 50%，40%，10%
• 各个级别队列可以采用不同的调度策略，如
  • 系统进程采用优先级调度
  • 交互式进程采用 RR
  • 批处理队列采用 FCFS

三. 同步与互斥

1.进程同步&互斥的概念

• 什么是进程同步？

  举个例子：一个进程杀猪，一个进程炒肉
  就必须保证杀猪在炒肉之前，但进程具有异步性，同步就是为了解决这个问题的

• 什么是进程互斥？

  举个例子：一个进程在洗澡，她会上锁，其他进程暂时不能访问厕所
  进入区：负责检查是否可进入临界区（上锁）
  临界区：访问临界资源的那段代码
  退出区：负责解除【正在访问临界资源】标志（解锁）
  剩余区：做其他处理

• 进程互斥的原则

  1. 空闲让进：临界区空闲，应该允许一个进程访问
  2. 忙则等待：临界区正在被访问，其他试图访问的进程需要等待
  3. 有限等待：要在有限时间内进入临界区，保证不会饥饿
  4. 让权等待：进不了临界区的进程，要释放处理机

2.实现互斥的基本方法

(1).进程互斥的软件实现方法

• 如果没有进程互斥？

  打印机例子

• 单标志法

  • 算法思想：两个进程在访问完临界区后会使用临界区的权限转交给另一个进程，每个进程进入临界区的权限只能被另一个进程赋予

  • 问题：违背了空闲让进，如果 A 一直不用，B 也用不了

    

• 双标志先检查法

  • 算法思想：设置一个布尔数组，标记各进程想要进入临界区的意愿，如果别人有意愿，自己就说没意愿；如果别人没意愿，自己就说有意愿

  • 问题：未被忙则等待，A 发现 B 是 false，刚准备把自己改成 true，时间片用完了；B 一看 A 是 false，把自己改成 true，时间片用完；A 继续执行上次的，改成 true；冲突

    

• 双标志后检查法

  • 针对【双标志先检查】的改进，先“上锁”，后“检查”，自己先说意愿，再问别人

  • 违背：空闲让进，A 说自己有意愿，时间片结束；B 说自己有意愿，时间片技术；A 一看 B 有意愿，时间片技术；B 一看 A 有意愿，时间片技术；双方都认为对方有意愿，就会说自己没意愿，这个过程可能一直进行

    

• Peterson 算法

  • 思想：一个表达意愿的变量，一个表示谦让的变量；不论时间片如何切换，最后一个表达谦让的人，一定让给了另一个进程

  • 违背了让权等待

    

(2).进程互斥的硬件实现方法

• 中断屏蔽方法

  • 方法

    先运行关中断
    然后访问临界区
    退出临界区后运行开中断指令

  • 优缺点

    优点：简单，高效
    缺点：不适用与多处理机（因为关中断只能关一个处理机）
    不适用于用户进程（因为关中断是特权指令）

• TestAndSet 指令（TSL 指令）

  

  TSL 指令有硬件实现，不允许被中断
  注意这个函数为什么需要 old 变量，因为我们需要先【上锁】在【判断】

  优点：适用于多处理机环境，简单
  缺点：不满足让权等待，会一直卡在 while 循环

• Swap 指令（Exchange 指令/XCHG 指令）

  

  和 TSL 指令逻辑上一样，不允许中断，只是硬件实现方式不一样，因此优缺点一样

3.互斥锁

• 实现

  使用 acquire()获得锁，release()释放锁，available=false 表示获得锁

  互斥锁的主要缺点：忙等待，临界区已上锁的情况下，循环 acquire()
  自旋锁：需要连续循环忙等的互斥锁，如 TSL,Swap，单标志法

• 特性

  1. 需要忙等待，进程时间片用完才下处理机，违反【让权等待】
  2. 优点：等待期间不用切换进程，在多处理机系统中，若上锁时间段，代价低
  3. 缺点：不适用于单处理机，不切换进程不可能解锁

4.信号量机制

(1).信号量机制的基本概念

• 信号量机制的一些概念

  用户进程通过操作系统提供的一对原语和信号量进行操作，实现同步/互斥

  信号量：一个变量，记录某种资源的数量（可以是整数，也可以是记录型变量）
  原语：wait(S),signal(S)原语，信号量 S 是参数，也写作 P(S),V(S)

• 整型信号量

  

  用整型变量作为信号量，没有办法实现【让权等待】

• 记录型信号量

  

(2).信号量机制实现进程同步/互斥/前驱关系

• 信号量机制实现进程互斥

  

• 信号量机制实现进程同步

  

• 信号量机制实现前驱关系

  

5.经典同步问题

(1).生产者/消费者问题

• 问题描述

  

  缓冲区没满：生产者才能把产品放入【同步问题】
  缓冲区没空：消费者才能取出产品【同步问题】
  生产者们不能同时往缓冲区写数据【互斥问题】

• 如何实现

  

• 死锁

  

  互斥的 P 操作必须在同步的 P 操作之后

(2).多生产者/多消费者问题

• 问题描述

  

  父亲只放苹果，母亲只放橘子，儿子只吃橘子，女儿只吃苹果，盘子只能装一个水果
  父亲放了苹果，女儿才能取苹果【同步关系】
  母亲放了橘子，儿子才能取橘子【同步关系】
  盘子为空，父亲或母亲才能放水果【同步关系】
  父亲，母亲不能同时放水果【互斥关系】

• 如何实现

  

  如果缓冲区为 1，可能不需要互斥信号量
  但如果大于 1，一定需要互斥信号量

(3).吸烟者问题

• 问题描述

  

  抽烟者卷烟需要三种材料：烟草，纸，和胶水
  每个抽烟者拥有一种材料
  供应者每次放两个材料在平台，缺少这两个材料的吸烟者拿走，完成吸烟
  供应者需要实现三个抽烟者轮流的吸烟

  桌子上有组合一【纸 + 胶水】，第一个抽烟者才会取走【同步问题】
  桌子上有组合二【烟草 + 胶水】，第二个抽烟者才会取走【同步问题】
  桌子上有组合三【烟草 + 纸】，第三个抽烟者才会取走【同步问题】
  抽烟者抽完烟，供应者才会放东西【同步问题】
  桌子需要互斥访问【互斥问题】，但缓冲区是 1，可以不设置互斥信号量

• 如何实现

  

(4).读者/写着问题

• 问题描述

  有读者，写者两组进程，共享一个文件

  要求：
  1.允许多个读者进程同时读
  2.只允许一个写者进程写
  3.任一写者在完成写操作前不允许其他读者或写者工作
  4.写者进程执行写操作前，应保证已有的读者与写者进程全部退出

• 如何实现

  

  注：w 是为了实现写优先，避免写进程饿死，过程比较复杂，最好自己运行一下

(5).哲学家进餐问题

• 问题描述

  

  哲学家要么思考，要么吃饭
  一共只有 5 根筷子，每个哲学家只能拿自己左右的筷子

• 如何实现

  • 死锁

    

    如果所有哲学家同时吃饭，并且恰好拿起一更筷子的时候进程切换，全员阻塞

    解决方案：
    1.最多允许四个哲学家同时进餐
    2.要求奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边筷子
    3.仅当一个哲学家左右筷子都可用时，才允许他拿起筷子（不准确），准确的说法应该是哲学家拿筷子的过程互斥访问

    ​ 【即：用一个新的互斥信号量实现，对两个 P 操作的互斥访问】

6.管程

• 为什么要引入管程？

  因为信号量机制不好用：编写程序困难，易出错

• 管程的定义和基本特征

  

• 拓展：管程解决生产者消费者问题

  

• 管程的特点总结

  

四.死锁

1.死锁的基本概念

• 什么是死锁？

  就是一种尴尬的局面：每个进程都在等待对方的资源，无法向前推进

• 死锁/饥饿/死循环的区别

  

• 死锁产生的必要条件

  • 互斥条件：进程之间访问资源必须互斥
  • 不剥夺条件：进程的资源没有用完前，无法被其他进程剥夺，只能主动释放
  • 请求和保持条件：进程至少保持了一个资源，但又提出了新资源的请求
  • 循环等待条件：存在一种进程资源的循环等待链**【反之不成立，除非每类资源只有一个】**

• 什么时候会发生死锁

  1. 对系统资源的竞争
  2. 进程推进顺序非法
  3. 信号量使用不当

• 死锁的处理策略

  1. 预防死锁
  2. 避免死锁（如：银行家算法）
  3. 死锁的检测和解除

2.死锁处理策略

(1).预防死锁

• 破坏互斥条件

  • 例如：使用 SPOOLing 技术奖打印机改造成共享设备

    

• 破坏不剥夺条件

  • 方案一

    当某个进程请求信的资源得不到满足时，他必须立即释放保持的所有资源，待以后再重新申请

  • 方案二

    当某个进程所需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺，这种方式需要考虑各个进程的优先级

  • 该策略的缺点

    1. 实现复杂
    2. 释放资源会造成前一阶段工作实效。因此一般适用于易保存/恢复状态的资源如 CPU
    3. 反复申请和释放资源增加系统开销，降低吞吐量
    4. 若采用方案一，很可能在放弃与申请间轮回，最终导致进程饥饿

• 破坏请求和保持条件

  • 静态分配方法

    进程在投入运行前，一次申请完他所需要的所有资源

  • 缺点

    1.进程长期霸占资源，有的资源都没咋用，资源利用率低
    2.如果一个进程需要很多资源，试问这些资源同时处于空闲的概率能多大？那么
    该进程大概率一直饥饿

• 破坏循环等待条件

  • 顺序资源分配法

    给系统中的资源编号，规定每个进程必须按编号递增顺序请求资源，同类资源（编号相同）一次申请完

  • 缺点

    1.不方便增加新的设备
    2.进程实际使用资源顺序可能和编号不一致，导致资源浪费【如：在使用扫描仪之前必须先申请打印机】
    3.必须按规定次序申请资源，用户编程玛玛法【如：换个电脑编号就变了，程序也要改变】

(2).避免死锁_银行家算法

• 什么是安全序列

  

  规则：银行家初始 100
  1.B,A,T 三个企业家，只有借到最大需求的钱，才会创业成功，然后还钱，否则不还钱
  2.银行家可以要回来的钱算银行家的资产，要不回来的，就不是银行家的资产

  图一：银行家剩余 40，如果给 B 借 30，那么所有钱都要不回来了，不安全状态
  图二：银行家剩余 40，如果给 A 借 20，还剩 20 可以借给 T，让他创业成功还钱，在借给 B，让 B 创业成功还钱，最后给 A，让 A 创业成功还钱，可以收回所有钱，这就是安全序列

  企业家其实就是进程，进程只有拿到所有资源才会释放资源
  如果系统处于安全状态，一定不会死锁；如果系统进入不安全状态，可能死锁

• 银行家算法

  • 核心思想

    进程提出资源申请时，先判断分配资源是否会导致系统计入不安全状态，如果会，就不答应，让进程阻塞等待

  • 资源的向量表示

    

    注：向量的维度表示不同类的资源，数值表示该类资源的数量
    **安全算法：**找到安全序列的算法

• 重要考点

  • 数据结构

    

    Available 表示系统还有多少可用资源
    Request 表示此次申请的资源数

  • 银行家算法步骤

    1.检查此次申请是否超过最大需求数
    2.检查系统剩余资源是否能满足此次申请
    3.试探性分配，更改数据结构
    4.用安全性算法检车此次分配是否会导致系统进入不安全状态

  • 安全性算法步骤

    1.检查当前剩余的可用资源能否满足某进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收
    2.不断重复上述过程，看最终能否让所有的进程都加入安全序列

(3).死锁的检测和解除

• 死锁的检测

  • 为了对死锁检测

    1.需要一种数据结构保存资源的请求和分配信息
    2.需要一种算法，利用数据结构检测系统是否进入死锁

  • 死锁的检测

    

    方法：
    1.依次运行图中进程结点（不阻塞的，非孤点的），然后归还资源，将进程结点的 2.边删除，进程结点变成孤点
    3.如果不能消除所有边，就发生了死锁
    4.最终还连着边的进程就是出于死锁状态的进程

    如果通过方法能够消除所有的边，称图示可完全简化的
    **死锁定理：**如果图不可完全简化，此时系统发生死锁

• 死锁的解除

  

第三章 内存管理

1.内存的知识

• 什么是内存？有何作用

  程序运行要先放到内存才能被 CPU 处理

  按字节编址：一个字节的内存单元编为一个地址
  按字编址：一个机器字（C 机器字长）编为一个地址

• 指令的工作原理

  操作码，地址码，计租里面学过，不多说了

• 指令中的逻辑地址如何转换为物理地址

  • 装入模块：程序编译后生成装入模块（.exe），运行时就装入内存

  • 装入的三种方式

    1. 绝对装入

       编译时候，如果事先知道程序将放到内存的哪个位置，编译程序就会把逻辑地址编译为绝对地址，只适用于单道程序方式

    2. 可重定位装入

       静态重定位，又称可重定位装入，编译程序不会地址转换，因此装入模块中是逻辑地址，在装入的时候重定位，转换为物理地址(地址变换是在装入的时候一次完成的)

       特点：一个作业装入内存时候，必须分配其要求的全部内存空间，否则不能装入，运行期间不能移动，适用于多道批处理系统

    3. 动态运行时装入

       动态重定位：又称动态运行时装入，装入模块中的地址都是从 0 开始的，弄一个重定位寄存器存储装入模块起始位置的存放地址，两者一加就得到真实地址了

       特点：可以只装入部分代码就能运行，可以动态分配内存

• 写程序到程序运行

  

  编译：把源代码编译成目标模块，这些模块地址不同意
  链接：把目标模块，库函数链接在一起，形成一个完成的装入模块

  链接的三种方式：
  1.静态连接：程序运行前把各个目标模块及库函数链接成装入模块，之后不再拆开
  2.装入时动态链接：目标模块装入内存时，边装入一边链接
  3.运行时动态链接：程序执行中需要改目标模块时，才对他链接，便于实现对目标模块的共享

2.内存管理的概念

• 内存空间的分配与回收

  • 连续分配管理方式
  • 非连续分配管理方式
    1. 基本分页存储管理
    2. 基本分段存储管理
    3. 段页式存储管理

• 内存空间的扩展

  • 之后介绍

• 地址转换

  • 装入模块：程序编译后生成装入模块（.exe），运行时就装入内存

  • 装入的三种方式

    1. 绝对装入

       编译时候，如果事先知道程序将放到内存的哪个位置，编译程序就会把逻辑地址编译为绝对地址，只适用于单道程序方式

    2. 可重定位装入

       静态重定位，又称可重定位装入，编译程序不会地址转换，因此装入模块中是逻辑地址，在装入的时候重定位，转换为物理地址(地址变换是在装入的时候一次完成的)

       特点：一个作业装入内存时候，必须分配其要求的全部内存空间，否则不能装入，运行期间不能移动

    3. 动态运行时装入

       动态重定位：又称动态运行时装入，装入模块中的地址都是从 0 开始的，弄一个重定位寄存器存储装入模块起始位置的存放地址，两者一加就得到真实地址了

       特点：可以只装入部分代码就能运行，可以动态分配内存，适用于多道批处理系统

• 内存保护

  • 方案一

    在 CPU 中设置一对上下限寄存器存放进程的上，下限地址，检查是否越界

  • 方案二

    采用重定位寄存器（基址寄存器）​和​界地址寄存器，重定位寄存器存放起始物理地址，界地址寄存器存放最大逻辑地址

3.覆盖与交换

• 覆盖技术

  

  • 背景

    为了解决：程序大小超过物理内存综合的问题

  • 缺点：对用户不透明，增加程序员编程负担

  • 思想

    将程序分为多个段
    内存分为“固定区”和“覆盖区”
    常用的段放在固定去，调入后不再调出
    不常用的段放在覆盖区，需要时调入，不需要时调出

• 交换技术

  • 一些问题

    

  • 思想

    内存紧张时候，系统将某些进程暂时换出内存
    把外存中某些具备运行条件的进程换入内存

    PCB 常驻内存

• 覆盖与交换的区别

  覆盖：在同一个程序和进程中进行的
  交换：不同进程/作业间进行的

4.连续分配方式

• 单一连续分配

  

• 固定分区分配

  

  操作系统需要建立一个分区说明表记录分区的大小，起始地址，状态

  优点：简单，无外部碎片
  缺点：1.程序如果很大，可能没有分区能装下 ，不得不采用覆盖技术，效率低下 2.会产生内部碎片

• 动态分区分配

  

  1. 系统使用什么数据结构记录内存的使用情况？

     空间分区表：一个表，包含分区号，分区大小，分区起始地址等信息
     空闲分区链：一个双链表

  2. 当很多空闲分区都满足要求，选哪个分配？

     依照动态分区分配算法，下一节介绍

     

  3. 如何进行分区的分配与回收操作？

     分配：
     1.如果分区大于进程，修改表项中的分区大小和起始地址即可
     2.如果分区等于进程，要删掉表项

     回收：
     1.回收区前面/后面有个相邻的空闲分区，回收后空闲表项需要合并
     2.回收取前后都没有相邻的空闲分区，需要增加表项

  • 碎片

    内部碎片：非给某个进程的内存，有些部分他没用
    外部碎片：内存中一些空闲分区太小，难以利用

    可通过【紧凑】技术解决

5.基本分页存储管理的基本概念

• 什么是分页存储

  

• 页表

  

  通俗的理解，告诉你逻辑地址

  0.先看有没有越界，越界内中断
  1.逻辑地址/一页的大小=这是第几页
  2.查页表，比如说进程的第 5 页对应主存的第 10 页
  3.再看这是进程第五页的第几行，那么主存也就是第 10 页的第几行

  那么实际地址=10 页 乘以 1 页的大小 加上第十页的行数

  注：主存的页叫做“块”，都是从第 0 页，第 0 行开始的，行就是【页内偏移量】

• 基本地址变换机构

  • 页表寄存器：存在 PCB 里

    

    注，考点：
    1.页式管理中地址是一维的
    2.访存次数：两次，第一次查页表，第二次取数据

• 快表

  • 快表

    又称联想寄存器 TLB，是一种高速缓存，存放最近访问的页表项的副本，内存中的页表叫慢表

    

    注：
    1.若快表命中，只需要一次访存
    2.若快表没命中，需要同时将慢表的表项存入快表

• 具有快表的地址变换机构

  

• 两级页表

  

  给出逻辑地址

  0.先判断有没有越界，越界内中断
  1.先看一级页号，根据一级页表，找到主存块
  2.主存块里面存了二级页表，根据二级页号，找到二级页表的页表项
  3.根据页表项和页内地址，找到实际地址

  注：
  1.若采用多级页表机制，各级页表的大小不能超过一个页面
  2.访存次数：有 n 级页表，访问 n+1 次，查表 n 次，取数据一次

6.基本分段存储

• 分段

  

  分段系统逻辑地址结构：\begin{array}{|c|c|c|}\hline段号&段内地址\\ \hline \end{array}
  段号：决定每个进程最多可以分几个段
  段内地址：决定每个段的最大长度

• 段表

  

• 地址转换

  

7.分段对比分页

8.段页式管理方式

• 分页，分段优缺点分析

  	优点	缺点
  分页管理	内存空间利用率高 没有外部碎片 只有少量内部碎片	不便按照逻辑实现信息共享和保护
  分段管理	很方便按照逻辑块实现信息共享和保护	如果段太长，连续空间分配不便 产生外部碎片

• 段页式管理

  1. 先分段分页

     

  2. 逻辑地址结构

     

     段号的位数决定每个进程最多分几段
     页号位数决定每个段最多多少页
     页内偏移量决定页面大小、内存块大小是多少

     分段对用户可见
     分页对用户不可见

  3. 段表

     

     一个进程只对一个段表，一个段表项对应一个页表，因此一个进程对应多个页表

  4. 地址转换

     

第四章 文件管理

一.文件系统基本知识

1.初识文件管理

• 一个文件有哪些属性？

  文件名：同一目录下不允许有重名文件
  **标识符：**标识符是唯一的，文件名不唯一
  **文件类型：**指明文件类型
  **文件位置：**文件存放路径【用户使用】&外存地址【用户不可见】
  文件大小：
  创建时间：
  上次修改时间：
  文件所有者信息：
  **保护信息：**对文件访问进行保护，比如只读等

• 文件内部的数据应该被怎样组织起来？（文件的逻辑结构）

  • 主要是看文件内的记录如何组织，下节课讲

  • 文件的两大类

    1. 无结构文件

       由一些二进制或字符流组成，又称【流式文件】

    2. 有结构文件

       由一组相似的记录组成，又称【记录式文件】

       记录：​一组相关​数据项的集合

       比如说 excel 表就是有结构文件

• 文件之间应该如何组织

  

• 操作系统应该向上提供哪些功能

  

• 从上往下看，文件如何存放在外存（文件的物理结构）

  

  外存也分为一个个【磁盘块】，具体怎么存，后面学

• 其他需要操作系统实现文件管理功能

  • 文件共享
  • 文件保护

2. 文件控制块

目录本身就是一文件
目录文件中每条记录就是一个文件控制块（FCB）

需要对目录进行哪些操作？
搜索：
创建文件：
删除文件：
显示目录：
修改目录：

3.目录结构

(1)单级目录文件

(2)两级目录结构

(3)多级目录结构

多级目录结构也叫树形目录结构

从根目录出发：绝对路径
从当前目录出发：相对路径

缺点：不便实现文件的共享

(4)无环图目录结构

4.索引结点

找到了文件名对应的目录项时，才需要将索引结点调入内存
存放在外存中的索引结点：磁盘索引结点
存放在内存中的索引结点：内存索引结点
区别：内存索引结点需要额外记录一些信息：如文件是否被修改，此时有几个进程在访问该文件等

二.文件结构

1.文件的逻辑结构

(1)文件分类

• **无结构文件：**没有讨论的必要
• 有结构文件
  1. 定长记录
  2. 可变长记录

(2)有结构文件的逻辑结构

① 顺序文件

注：如果没有说明，默认顺序文件指的是物理上顺序存储的文件
顺序文件的缺点：增/删困难

② 索引文件

③ 索引顺序文件

1. 索引顺序文件是什么

   

2. 索引顺序文件（检索效率分析）

   

   如果查找次数依然很多，可以建立多级索引顺序文件

2.文件的物理结构

**文件块：**文件的逻辑地址空间也分块，逻辑地址为【逻辑块号，块内地址】
**磁盘块：**磁盘也分块

用户操作逻辑地址来操作文件，操作系统负责实现逻辑地址到物理地址的映射

① 连续分配

优点：
1.顺序读/写的速度最快【因为磁头不用移动太远】
2.支持顺序访问和直接访问

缺点：
1.如果需要拓展，需要重新找一个“网吧五连坐”
2.如果没有“五连坐”，就没有办法分配，难以利用磁盘碎片

② 链接分配

1. 隐式链接

   

   优点：方便拓展，不会产生碎片，外存利用率高
   缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一块的指针耗费少量空间

   若题目没有提，默认就是隐式的

2. 显式链接

   

   文件分配表（FAT）：开机就放在主存，常驻，只有一张表

   优点：方便拓展，没有碎片，支持随机访问，顺序访问，地址转换不需要访问磁盘，效率最高
   缺点：文件分配表占用一定空间（主存）

③ 索引分配

如果索引表太大，一个磁盘块存不下，咋办？

1. 链接方案

   

2. 多层索引

   

   缺点：如果文件很小，也需要读几次磁盘

   如果是 K 级索引表：需要 K+1 次读磁盘，K 次读索引，1 次读数据

   为此又提出了混合索引

3. 混合索引

   

• 总结

  

三.文件存储空间管理

1. 存储空间的划分与初始化

2.存储空间管理

(1)空闲表法

适用于：连续分配方式

(2)空闲链表法

(3)位示图法

适用于：连续分配和离散分配

如何分配：
1.扫描位示图，找到连续 K 个 0
2.找到盘块，分配，然后把位示图改成 1

如何回收：
1.把回收的盘块号对应的位示图改为 0

(4)成组链接法

在文件卷的目录区中设置一个磁盘块作为超级块，当系统启动时，将超级块读入内存，并且保证内存与外存中超级块的数据一致

如何分配？

Eg：分配 100 个空闲块
1.检查第一个分组够不够用，够用刚好 100 个
2.分配第一个分组中的 100 个空闲块，但 300 号【第一个】中的信息需要复制到超级块
3.修改超级块中响应的信息

如何回收？

Eg：假设第一个分组有 99 个块，回收 1 块

1.检查第一个分组满了吗，没满
2.插到第一组
3.修改指向第一组的超级块的信息

Eg：假设第一个分组有 100 个块，回收 1 块

1.检查第一个分组满了吗，满了
2.新建一个分组，把超级块的信息复制到新的分组，回收一块作为这组的【第一个】
3.修改超级块的信息

四.文件的基本操作&共享&保护

1.文件基本操作

2.文件共享

• **硬链接：**基于索引结点的共享方式、
• **软链接：**基于符号链的共享方式

3.文件保护

• 如果用户过多，为了避免访问控制表过长，可以对用户分组

五.文件系统

0.文件系统结构（408 不考）

1.文件系统的布局

• 物理格式化后

  磁盘会被划分为许多，扇区，如果有坏的，会用备用扇区替代，这个替代对 OS 透明

• 逻辑格式化后

  

  i 结点区：就是索引结点

• 文件系统在内存的结构

  

2.虚拟文件系统

虚拟文件系统的特点：
1.向上层用户提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
2.VFS 要求下层文件必须实现某些规定的函数，否则，不好意思，VFS 不支持
3.每打开一个文件，VFS 就会在主存中新建一个 vnode，用统一的数据结构表示文件;vnode 中除了保存一些基本的文件信息，还有个指向具体文件系统的函数功能的指针
注：vnode 贮存在于主存，inode 既会被调入主存，也会在外存存储

3.文件系统挂载

• 概念：就是把文件系统安装/挂载到操作系统中

  

第五章 输入输出管理

1.磁盘的结构

2.磁盘调度算法

• 一次磁盘读/写的时间

  

• 磁盘调度算法

  

3.减少磁盘延迟的方法

4.磁盘管理

• 磁盘初试化

  

• 引导块

  ROM 集成在主板，只存放很小的【自举装入程序】
  完整的【自举装入程序】存放在启动块/引导块/启动分区上
  启动块位于磁盘固定位置，拥有启动块的分区叫启动磁盘/系统磁盘【C 盘】
  开机时先运行【自举装入程序】找到引导块，再运行【完整的自举程序】，完成初始化

• 坏块管理

  

5.固态硬盘

1.I/O 设备的概念和分类

• 什么是 I/O 设备

  将数据输入到计算机，或接受计算机输出数据的设备

• I/O 设备的分类

  按使用特性分类	人机交互类外部设备：鼠标，键盘，打印机，数据传输速度慢 存储设备：移动硬盘，光盘，数据传输速度快 网络通信设备：猫【调制调节器】速度介于 12 之间
  按传输速率分类	低速设备 中速设备 高速设备
  按信息交换单位	块设备：速率较高，可寻址 字符设备：速率较慢，不可寻址，一般采用中断驱动方式

2.I/O 控制器

• I/O 设备的组成
  • 机械部件
  • 电子部件/I/O 控制器/设备控制器
• I/O 控制器的功能