[学习笔记] - 操作系统

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

四个特征

并发：两个或者多个事件在同一时间间隔内发送，这些事件宏观上是同时发生的，但是微观上是交替发生的
- 并行：指两个或多个事件在同一时刻同时发生
- 并发性：计算机系统中同时存在着多个运行着的程序
共享：指系统中的资源可供内存中多个并发执行的进程共同使用
- 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但是一个时间段内只允许一个进程访问该资源
- 同时共享方式：系统中某些资源，允许一个时间段内由多个进程同时对它们进行访问
- 共享性：系统中的资源可供内存中多个并发执行的进程共同使用
虚拟：把物理上的实体变为若干个逻辑上的对应物
- 空分复用技术
- 时分复用技术
异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进

并发和共享互为存在条件的
没有并发性就谈不上虚拟性
只有系统拥有了并发性，才有可能导致异步性

所谓的同时，往往是宏观上的，在微观上，这些进程可能是交替对资源进行访问的

发展和分类

手工操作阶段
批处理阶段
- 引入脱机输出/输出技术，并监督程序负责控制作业的输入输出
分时操作系统
实时操作系统
- 硬实时操作：必须在绝对严格的规定事件内完成处理
- 软实时系统：能接受偶尔违反事件规定
网络操作系统
分布式操作系统
个人计算机操作系统

运行机制和体系架构

特权指令：不允许普通用户程序使用
非特权指令

两种处理器状态

用户态
- 只能执行用户执行
核心态
- 都可有执行

通过程序状态字寄存器（PSW）中的某标志位标识当前处理器处于什么状态

两种程序

内核程序
- 运行核心态
应用程序
- 运行在用户态

操作系统内核

内核时计算机上配置的底层软件，是操作系统的最基本，最核心的部分

操作系统内核
- 时钟管理
  - 实现计时功能
- 中断处理
  - 负责实现中断机制
- 原语
  - 是一种特殊的程序
  - 储于操作系统最底层，最接近硬件的部分
  - 这种程序的运行具有原子性
  - 运行事件较短，调用频繁
- 对系统资源进行管理的功能
  - 进程管理
  - 存储器管理
  - 设备管理

操作系统的体系结构：大内核和微内核

大内核
- 将操作系统的主要功能模块都作为系统内核
- 高性能
- 内核代码复杂
微内核
- 只把最基本的功能保留在内核
- 内核功能少，结构清晰，方便维护
- 需要频繁切换运行态，性能低

中断和异常

为了让程序并发运行，引入了中断机制，实现了多道程序并发执行本质：发生中断就意味着需要操作系统接入，开展管理工作

当中断发生时，CPU立刻进入核心态
当中断发生后，当前运行的进程暂停运行，并由操作系统内核对中断进行处理
对于不同的中断信号，会进行不同的处理

发生了中断，就意味着操作系统的接入，开展管理工作，由于操作系统的管理工作需要使用特权指令，因此要从用户态转换为核心态，中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权，有了中断，才能实现多道程序并发执行

用户态 -> 核心态：使通过中断实现的，并且中断是唯一途径

中断的分类

内中断（也称为异常，例外，陷入）
- 自愿中断：自愿中断-指令中断
  - 系统调用
- 强迫中断
  - 硬件故障
    - 缺页
  - 软件中断
    - 整数除零
外中断
- 外设请求
  - IO中断请求
- 人工干预
  - 用户强行终止一个进程

中断的处理过程

执行完每个指令之后，CPU都要检查当前是否有外部中断信号
如果检查到外部中断信号，则需要保护被中断进程的CPU环境
根据中断信号类型转入相应的中断处理程序
恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

系统调用

操作系统作为用户和硬件的接口，需要向上提供一些简单易用的服务，主要包括命令接口和程序接口，其中，程序接口由一组系统调用组成

命令接口（允许用户直接使用）
- 联机用户接口：说一句做一句
- 脱机命令接口：说一堆做一堆
程序接口（允许用户间接使用）
- 由一组程序调用组成

系统调用时操作系统提供给应用程序使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务
应用程序通过系统调用请求操作系统的服务，系统中的各种共享资源都由操作系统统一管理，凡是域资源相关的操作，都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成，这样可以保证系统的稳定性和安全性，防止非法操作

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

进程

程序：就是一个指令序列
- 系统为每个运行的程序配置一个数据结构，称为进程控制块（PCB）用来描述进程的各种信息
进程：程序段，数据段，PCB三部分组成了进程实体，一般情况下，我们把进程实体就简称为进程
- PCB是进程存在的唯一标识
- 进程强调动态性，进程实体是静态的
- 程序段
  - 程序代码
- PCB
  - 进程描述信息
    - 进程标识符PID
    - 用户标识符UID
  - 进程控制和管理信息
    - 进程当前状态
    - 进程优先级
  - 资源分配清单
    - 程序段指针
    - 数据段指针
    - 键盘
    - 鼠标
  - 处理机相关信息
    - 各种寄存器值

进程的组织

链接方式
- 按照进程状态将PCB分为多个序列
- 操作系统持有指向各个队列的指针
  - 执行指针：指向当前处于运行状态的进程
  - 就绪队列指针：会把优先级高的放在前面
  - 阻塞队列指针
索引方式
- 根据进程状态不同，建立几张索引表
- 操作系统持有指向各个索引表的指针
  - 把链接换为索引表

进程的特征

动态性
- 进程是程序的一次执行的过程
并发性
- 内存中有多个进程实体，各进程可并发执行
独立性
- 进程是能独立运行，独立获得自由，独立接受调度的基本单位
异步性
- 各进程按自傅里，不可预知的速度向前前进
结构性
- 每个进程都会配置一个PCB，由程序段，数据段，PCB组成

进程的状态和转换

运行态
- 占有CPU
就绪态
- 已经具备运行条件，但是没有空闲CPU
阻塞态
- 因等待某一事件而暂时不能运行
创建态
- 正在初始化进程的状态
终止态
- 正在回收的状态

            stateDiagram
            [*] --> 创建态
创建态 --> 就绪态: 系统完成创建工作
就绪态 --> 运行态: 进程被调度
运行态 --> 就绪态: 时间片到或者处理机被抢占
运行态 --> 阻塞态: 使用系统调用请求资源
阻塞态 --> 就绪态: 申请的资源被分配
运行态 --> 终止态: 运行结束或出错
终止态 --> [*]

进程控制

进程控制的主要功能是堆系统中的所有进程实施有效的管理，它具有创建新进程，撤销已有进程，实现进程状态转换等功能

进程控制就是要实现进程状态转换

使用原语实现进程控制，原语的特点是执行期间不允许中断，只能一气呵成（原子操作）

更新PCB中的信息
1. 所有进程控制原语一定都会修改进程状态标志
2. 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
3. 某进程开始运行前必然要恢复其运行环境
将PCB插入合适的队列
分配/回收资源

进程的创建

创建原语
- 申请空白PCB
- 为新进程分配所需资源
- 初始化PCB
- 将PCB插入就绪队列
引起进程创建的事件
- 用户登录
- 作业调度
- 提供服务
- 应用请求

进程的终止

撤销原语
- 从PCB集合中找到终止进程的PCB
- 若进程正在运行，立刻剥夺CPU，将CPU分配给其他进程
- 终止其所有子进程
- 将该进程拥有的所有资源归还给父进程或操作系统
- 删除PCB
引起进程终止的事件
- 正常结束
- 异常结束
- 外界干预

进程的阻塞和唤醒

进程的阻塞
- 阻塞原语
  - 找到要阻塞的进程对应的PCB
  - 保护进程运行现场，将PCB状态信息设置为阻塞态，暂时停止进程运行
  - 将PCB插入相应的事件等待队列
- 引起进程阻塞的事件
  - 需要等待系统分配某种资源
  - 需要等待相互合作的其他进程完成工作
进程的唤醒
- 唤醒原语
  - 在事件等待队列中找到PCB
  - 将PCB从等待队列移除，设置进程为就绪态
  - 将PCB插入就绪队列，等待被调度
- 引起进程唤醒的事件
  - 等待的事件发生

阻塞和唤醒要成对的出现

进程的切换

切换原语
- 将运行环境信息存入PCB
- PCB移入相应队列
- 选择另一个进程执行，并更新其PCB
- 根据PCB恢复新进程所需的运行环境
引起进程切换的事件
- 当前进程时间片到
- 有更高优先级的进程到达
- 当前进程主动阻塞
- 当前进程终止

进程通讯

进程通信就是进程之间的信息交换，各进程拥有自己的内存地址空间相互独立
为了保证安全，一个进程不允许访问另外一个进程的地址空间

共享储存

两个进程对共享空间的访问必须是互斥的，操作系统只负责提供共享空间和同步互斥工具

基于数据结构的共享
- 限制了数据类型
基于储存区的共享
- 只提供了空间，其他由进程自己决定

管道通信

            graph LR
            进程1--写数据-->管道--读数据-->进程2

管道只能采取半双工通信，某一时间段内只能实现单向的传输，如果要实现双向同时通信，则需要设置2个管道
各进程要互斥的访问管道
数据以字符流的形式写入管道，当管道写满时，写进程的系统调用将被阻塞，等待读进程将数据取走，当读进程将数据全部取走后，管道变空，此时读进程的系统调用将被阻塞
如果没写满，就不允许读，如果过没读空，就不允许写
管道中的数据一旦被读出，就会被抛弃，因此读进程最多只有一个

消息传递

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

消息头
- 发送进程ID
- 接受进程ID
- 消息类型
- 消息长度
- …
消息体

传递方式

直接通信方式
- 消息直接挂到接受进程的信息缓冲队列上
间接通信方式
- 消息要先发送到中间实体（信箱）中

线程

有的进程需要同时处理很多事情，引入线程，来增加并发度

线程是一个基本的CPU执行单元，也是程序执行流的最小单位

资源分配、调度
- 传统进程禁止中，进程是资源分配，调度的基本单位
- 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
并发性
- 传统进程机制中，只能进程间并放
- 引入线程后，各线程间也能并发，提升了并发度
系统开销
- 传统的进程间并放，需要切换进程的运行环境，系统开销大
- 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
- 引入线程后，并发所带来的系统开销减小

线程的属性

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

线程的实现方式

            graph TD
            用户级线程1 --- 线程库
用户级线程2 --- 线程库
用户级线程3 --- 线程库
线程库 --- 进程

用户级线程由应用程序通过程序库实现，所有的线程管理工作都由应用程序负责，线程切换可以在用户态下完全，无需操作系统干预。多个用户级线程映射到一个内核级线程，每个用户进程只对应一个内核级线程

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高

            graph TD
            用户级线程1 --- 内核级线程1
用户级线程2 --- 内核级线程2
用户级线程3 --- 内核级线程3
内核级线程1 --- 进程
内核级线程2 --- 进程
内核级线程3 --- 进程

内核级线程的管理工作由操作系统内核完成，线程调度，切换等工作都由内核负责，因此，内核级线程的切换必然需要在核心态下才能完成。一个用户级线程映射到一个内核级线程，每个用户进程有与用户级线程同数量的内核级线程

优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强，多线程可以在多核处理器上并行执行
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，开销大

            graph TD
            用户级线程1 --- 线程库
用户级线程2 --- 线程库
用户级线程3 --- 线程库
线程库 --- 内核级线程1
线程库 --- 内核级线程2
内核级线程1 --- 进程
内核级线程2 --- 进程

n用户级线程映射到m各内核级线程上

克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销大的缺点

操作系统只看得见内核级线程，因此只有内核级线程才是处理机分配的单位

内核线程依然叫 “线程 (thread)”，用户线程叫 “协程 (co-routine)”.
协程跟线程是有区别的，线程由CPU调度是抢占式的，协程由用户态调度是协作式的，一个协程让出CPU后，才执行下一个协程。

处理机调度

当有一堆任务要处理，但由于资源有限，有些事情没办法同时处理，就需要确定某种规则来决定这些任务的顺序
在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程，处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行

	调度发生	频率	对进程影响
高级调度	外存->内存	最低	无->创建态->就绪态
中级调度	外存->内存	中等	挂起态->就绪态
低级调度	内存->CPU	最高	就绪态->运行态

高级调度

按一定的原则从外存上处于后备序列的作业中挑选一个或多个，给他们分配内存等必要资源，并建立相应的进程（PCB），以使他们获得竞争处理机的权力

高级调度是外存与内存之间的调度，每个作业只调入一次，调出一次，作业调入时会建立相应的PCB，作业调出时才撤销PCB，高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出

中级调入

引入了虚拟存储技术，可将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又有空闲时，再重新调入内存

提高内存利用率
系统吞吐量

这样的进程的状态为挂起状态，PCB不会一起被调到外存，而是会常驻内存，PCB中会记录进程数据在外存中的存放未知，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控，管理，被挂起的进程PCB会被放到挂起队列中

决定将那个处于挂起状态的进程重新调入内存

            stateDiagram
            [*] --> 创建态
创建态 --> 就绪态: 系统完成创建工作
创建态 --> 就绪挂起: 挂起
就绪态 --> 运行态: 进程被调度
就绪态 --> 就绪挂起: 挂起
就绪挂起 --> 就绪态: 激活
运行态 --> 就绪态: 时间片到或者处理机被抢占
运行态 --> 阻塞态: 使用系统调用请求资源
运行态 --> 就绪挂起: 挂起
阻塞态 --> 就绪态: 申请的资源被分配
阻塞态 --> 阻塞挂起: 挂起
阻塞挂起 --> 阻塞态: 激活
阻塞挂起 --> 就绪挂起: 事件出现
运行态 --> 终止态: 运行结束或出错
终止态 --> [*]

低级调度

其主要任务时按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它，进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度

调度时机

当前运行的进程主动放弃处理机
- 进程正常终止
- 发生异常而终止
- 进程主动请求阻塞
当前运行进程被动放弃处理机
- 分给进程的时间片用完
- 有更紧急的事情需要处理
- 有更高优先级的进程进入就绪队列

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

在处理中断的过程中，中断处理过程负责，切与硬件密切相关，很难做到在中断处理过程中进行进程切换
进程在操作系统内核程序临界区
在原子操作的过程中

临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源
临界区：访问临界资源的那段代码

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列
普通临界区：打印机

调度方式

非剥夺调度方式
- 只允许进程主动放弃处理机，在运行过程中即便有更紧急的任务达到，当前进程依然会继续使用处理机
剥夺调度方式
- 如果有一个更紧急的任务，则立刻暂停正在执行的进程

狭义的进程调度：从就绪队列中选中一个要运行的进程
进程切换：一个进程让出处理机，由另一个进程占用处理机
广义的进程调度：包含了选择一个进程和进程切换两个步骤

完成了

对原来进程的各种数据的保存
对新的进程各种数据的恢复

进程的切换是有代价的

评价调度算法

CPU利用率：指CPU忙碌的时间占总时间的比例
系统吞吐量：单位时间内完成作业数量
周转时间：从作业被提交给系统开始，到作业完成为止这段时间间隔
- 作业在外存后备队列上等待作业调度的时间
- 作业在就绪队列上调度调度的时间
- 进程在CPU上执行的时间
- 进程等待IO操作完成的时间
带权周转时间：作业周转时间/作业实际运行时间 >= 1
等待时间：指进程/作业处于等待处理机状态时间之和（等待IO不算）
响应时间：指从用户提交请求到首次产生响应所用的时间

调度算法

先来先服务（FCFS）

算法思想
- 从公平的角度开了
算法规则
- 按照进程到达的先后顺序进行服务
用于作业/进程调度
- 用于作业调度时：考虑的是哪个作业先达到后备队列
- 用于进程调度时：考虑的是哪个进程先到达就绪队列
是否可抢占
- 非抢占式算法
优点
- 公平，实现简单
缺点
- 排在长作业后面的短作业的带权周转时间非常大
- 对长作业有利，对短作业不利
是否会导致饥饿
- 不会

短作业有限（SJF）

算法思想
- 追求最短的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
算法规则
- 最短的作业/进程有限得到服务
用于作业/进程调度
- 用于进程调度时：短进程有限算法
是否可抢占
- 非抢占式算法，也有抢占式：最短剩余时间优先
优点
- “最短的”平均等待时间，平均周转时间
缺点
- 不公平
- 对短作业有利，对长作业不利
是否会导致饥饿
- 可能产生饥饿现象

高响应比有限（HRRN）

算法思想
- 要综合考虑作业/进程的等待时间和要求服务的时间
算法规则
- 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
用于作业/进程调度
- 用于作业调度时：考虑的是哪个作业先达到后备队列
- 用于进程调度时：短进程有限算法
是否可抢占
- 非抢占式算法
优点
- 综合考虑了等待时间和运行时间
是否会导致饥饿
- 不会

时间片轮调度算法（RR）

算法思想
- 公平地，轮流地位各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则
- 按照各进程达到就绪队列的顺序，轮流让各个进程执行一个时间片
- 若进程未在一个时间片内执行完则剥夺处理机
- 将进程重新放到就绪队列队尾重新排队
用于作业/进程调度
- 用于进程调度时：只有作业放入内存建立相应的进程后，才能被分配处理机时间片
是否可抢占
- 若进程未能在时间片内运行完，将被强行剥夺处理机使用权
- 由时钟装置发出时钟中断来通知CPU时间片已到
优点
- 公平。响应快，适用与分时操作系统
缺点
- 用于进程切换会有开销，不区分任务紧急程度
是否会导致饥饿
- 不会

如果时间片太大，使得每个进程都可有在一个时间片内完成，则时间片轮调度算法就会退化为先来先服务调度算法
一般来说，设计时间片式要让切换进程的开销占比不超过1%

优先级调度算法

算法思想
- 随着计算机的发展，特别是实时操作系统的出现，需要根据任务紧急程度来决定处理顺序
算法规则
- 每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
用于作业/进程调度
- 可用于作业调度，进程调度，甚至IO调度
是否可抢占
- 可抢占/非抢占式
优点
- 用优先级区分紧急程序，可灵活调整作业/进程的偏好程度
缺点
- 源源不断高优先级可能导致饥饿
是否会导致饥饿
- 会

可分为静态优先级和动态优先级

系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好IO型进程

多级反馈队列调度算法

算法思想
- 对其他调度算法的折中权衡
算法规则
- 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
- 新进程到达时进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾，如果此时已经在最下级的队列，则重新放回该队列的队尾
- 只有第k级队列为空时，才会位k+1级对头的进程分配时间片
用于作业/进程调度
- 可用于进程调度
是否可抢占
- 可抢占
- 若更上级的队列中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾
优点
- 对各类型进程相对公平（FCFS）
- 每个新到达的进程都可有很快得到响应（RR）
- 短进程只用较少的时间就可以完成（SPF）
- 不必实现估计进程的运行时间（避免作假）
- 可灵活的调整对各类型进程的偏好程度
  - CPU密集型进程
  - IO密集型进程
是否会导致饥饿
- 会

线程同步

进程具有异步性特征，要让一些进程按照先后顺序执行，就需要线程同步
同步亦称直接制约关系，它是指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生制约关系，进程间的直接制约关系就是源于它们之间的相互合作

线程互斥

各个并发执行的进程不可避免的需要共享一些系统资源

互斥共享方式
同时共享方式

临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源
临界区：访问临界资源的那段代码

进入区
- 检查是狗可以访问
临界区
- 访问临界资源的代码
退出区
- 解除访问临界资源
剩余区
- 善后处理

空闲让进：临界区空闲时允许立刻进入
忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待：对请求访问的进程，应保证在有限时间内进入临界区
让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

进程互斥实现方法

单标志法

两个进程在访问完临界区后，会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另外一个进程赋予

int turn = 0;

// --- P2

while (turn != 0) {} // 进入区
critical section;   // 临界区
turn = 1;           // 退出区
remainder section;  // 剩余区

// --- P1

while (turn != 1) {}
critical section;
turn = 0;
remainder section;

一定是轮流访问的，违背了空闲让进。也就是如果别人没用，自己也不能重新使用

双标志先检查法

设置一个布尔型整数flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0] = true意味着0号进程现在想要进入临界区，每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区

bool flag[2];
flag[0] = false;
flag[1] = false;

// --- P2

while (flag[0]) {}
flag[1] = true;
critical section;  // 临界区
flag[1] = false;
remainder section; // 剩余区

// --- P1

while (flag[1]) {}
flag[0] = true;
critical section;
flag[0] = false;
remainder section;

违背了忙则等待，flag[]线程不安全

双标志后检查法

双标志先检查法改进版，先上锁，后检查

bool flag[2];
flag[0] = false;
flag[1] = false;

// --- P2

flag[1] = true;
while (flag[0]) {}
critical section;  // 临界区
flag[1] = false;
remainder section; // 剩余区

// --- P1

flag[0] = true;
while (flag[1]) {}
critical section;
flag[0] = false;
remainder section;

违背了空闲让进，有限等待，产生死锁

Peterson算法

双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区，于是，如果双方都争着想进入临界区的话，可以让进程尝试“孔融让梨”，主动让对方使用临界区

bool flag[2];
int turn = 0; // 让谁优先进入

// --- P1
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);
critical section;
flag[0] = false;
remainder section;

// --- P2
flag[1] = true;
turn = 0; // 可以优先让对方进入临界区
while (flag[0] && turn == 0);
critical section;
flag[1] = false;
remainder section;

但是依然没有准寻让权等待

信号量机制

用户进程可以通过操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥，进程同步

信号量其实就是一个变量，可以是一个整数，也可以是更复杂的记录型变量，可以用一个信号量来标识系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数，检查为PV操作，P=wait，V=signal

整数信号量

用一个整数型的变量作为信号量，用来表示系统中的某种资源的数量

int S = 1; // 剩余资源数

void wait(int S) {
  while (S <= 0);
  S -= 1;
}

void signal(int S){
  S += 1;
}

// ---

wait(S);
// use
signal(S);

会产生忙等，违背让权等待

记录型信号量

整形信号量存在忙等问题，用记录型数据结构表示数据量

typedef struct {
  int value;         // 剩余资源数
  struct process *L; // 等待队列
} semaphore;

void wait(semaphore S) {
  S.value -= 1;
  while (S.value < 0) {
    block(S.L);
  }
}

void signal(semaphore S){
  s.value += 1;
  if (S.value <= 0) {
    wakeup(S.L);
  }
}

// ---

wait(S);
// use
signal(S)

对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value -= 1表示资源数减1，当S.value < 0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞，主动放弃处理机，并插入该类资源的等待队列S.L，实现了让权等待，不会忙等

对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value += 1表示资源数加1，若S.value <= 0时表示仍然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程

信号量机制实现进程互斥

分析并发进程的关键活动，划定临界区
设置互斥信号量mutex，初值为1
在临界区前执行P(mutex)
在临界区后执行V(mutex)

对不同资源需要不同的信号量（锁）

信号量机制实现进程同步

分析什么地方需要实现同步关系
设置同步信号量S，初始为0
在前操作之后执行V(mutex)
在后操作之前执行P(mutex)

semaphore S = 0;

// code2 run before code4
P1() {
  code1();
  code2();
  V(S);
  code3();
}

P2() {
  P(S); // 阻塞
  code4();
  code5();
  code6();
}

信号量机制实现前驱关系

            stateDiagram
            S1 --> S2
S2 --> S4
S4 --> S6
S2 --> S5
S5 --> S6  
S1 --> S3
S3 --> S6

要为每一对前驱关系个设置一个同步变量
在前操作之后执行V(mutex)
在后操作之前执行P(mutex)

            stateDiagram
            S1 --> S2: V(a) a=0 P(a)
S2 --> S4: V(c) c=0 P(c)
S4 --> S6: V(e) e=0 P(e)
S2 --> S5: V(d) d=0 P(d)
S5 --> S6: V(f) f=0 P(f)
S1 --> S3: V(b) a=0 P(b)
S3 --> S6: V(g) g=0 P(g)

P1() {
  S1;
  V(a);
  V(b);
}

P2() {
  P(a);
  S1;
  V(c);
  V(d);
}

P3() {
  P(b);
  SS;
  V(g);
}

P4() {
  P(c);
  S4;
  V(e);
}

P5() {
  P(d);
  S5;
  V(f);
}

P6() {
  P(e);
  P(f);
  P(g);
  S6;
}

生产消费者模型

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用，它们共享一个初始为空，大小为n的缓冲区

只有缓冲区美满，生产者才能把产品放入缓冲区，否则阻塞
只有缓冲区不空，消费者才能从中取出产品，否则阻塞
缓冲区时临界资源，各进程必须互斥地访问

semaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = 1; // 同步信号量，表示空闲缓冲区的数量
semaphore full = 1;  // 同步信号量，表示产品的数量

producer () {
  while(true) {
    produce();
    P(empty)
    P(mutex);
    put();
    V(mutex)
    V(full)
  }
}

consumer () {
  while(true) {
    P(full);
    P(mutex);
    get();
    V(mutex)
    V(empty);
  }
}

多生产消费者模型

多不同类别的数据类型

semaphore mutex = 1;   // 互斥信号量，实现对缓冲区的互斥访问
semaphore apple = 1;   // 盘子中苹果数量
semaphore orange = 1;  // 盘子中橘子数量
semaphore plate = 1;   // 盘子剩余容量

producer1 () {
  while(true) {
    produce();
    P(plate)
    P(mutex);
    put();
    V(mutex)
    V(full)
  }
}

producer2 () {
  while(true) {
    produce();
    P(plate)
    P(mutex);
    put();
    V(mutex)
    V(full)
  }
}

consumer () {
  while(true) {
    P(apple);
    P(mutex);
    get();
    V(mutex)
    V(plate);
  }
}

consumer () {
  while(true) {
    P(orange);
    P(mutex);
    get();
    V(mutex)
    V(plate);
  }
}

管程

管程是一种特殊的软件模块，有这些部分组成

局部于管程的共享数据结构定义
对该数据结构进行操作的一组过程（函数）
对局部于管程的共享数据设置初始值的语句
管程有一个名字

特征

局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次允许一个进程在管程内执行某个内部操作

monitor ProducerConsumer
  condition full, empty
  int count = 1;
  void insert(Item item) {
  if (count == N)
    wait(full);
  count++;
  insert_item(item);
  if (count == 1)
    signal(empty);
 }
 Item remove() {
   if (count == 0)
    wait(empty);
  count--;
  if (count == N - 1)
    signal(full);
  return remove_item();
 }

类似Queue，把具体操作封装起来

死锁

互斥条件：对必须互斥使用的资源的争抢
不剥夺条件：进程所获得的资源在未使用完之前，不能被剥夺
请求和保持条件：进程已经保持了至少一个资源，又提出了新的请求
循环等待条件：存在一种进程资源的循环等待链

对不可剥夺资源的不合理分配，可能导致死锁

安全序列

指如果系统按照这种序列分配资源，每个进程都能顺利完成，只要能找出一个安全序列，系统就是安全状态。
系统处于安全状态，就一定不会发生死锁，如果系统进入了不安全状态，就可能发生了死锁

银行家算法：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态
满足后的资源会返还，然后循环计算即可

Max矩阵 - Allocation矩阵 = Need矩阵

内存

内存空间的分配与回收
从逻辑上对内存空间进行扩充
把逻辑地址转化为物理地址
- 绝对装入：编译时产生绝对地址
- 可重定位装入：装入时将逻辑地址转为物理地址
- 动态运行时装入：运行时将逻辑地址转为物理地址，需设置重定位寄存器
提供内存保护功能，互不干扰
- 存放地址上下限，由CPU检测是否越界
- 采用重定位寄存器和界地址寄存器进行越界检测
  - 重定位寄存器：存放进程起始物理地址
  - 界地址寄存器：最大逻辑地址

内存扩充

覆盖技术

将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存

固定区
- 调入后就不再调出
覆盖区
- 需要用到时才调入

必须由程序员声明覆盖结构

交换技术

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

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区
- 文件区主要用于存放文件，主要追求储存空间利用率，因此对文件区空间的管理采用离散分配方式
- 对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。追求换入换出速度，采用连续分配方式
交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停
可有限换出阻塞进程，可换出优先级低的进程

内存空间的分配与回收

连续分配

系统为用户分配的必须是一个连续的内存空间

单一连续分配

内存分为

系统区
- 位于内存的低地址部分，用于存放操作系统
用户区
- 存放用户进程相关进程
- 内存中只能由一道用户程序，用户程序独占整个用户区间

优点：实现简单，无外部碎片，不一定需要采取内存保护
缺点：只能用于单用户，单任务操作系统，由内部碎片

固定分区分配

将用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业

分区大小相等
- 缺乏灵活性
- 适用于控制多个相同对象
分区大小不等
- 增加了灵活性

每个分区说明表

大小
起始地址
状态

无外部碎片，但是会产生内部碎片

动态分区分配

不会预先划分内存分区，根据进程大小动态建立分区，使分区的销大正好适合进程的需要

空闲分区表
- 分区号
- 分区大小
- 分区起始地址
空闲分区链
- 每个分区的起始部分和末尾部分分布设置指向前后分区的指针

分区回收就是数据结构的操作，相邻的空分区要合并

没有内部碎片，但是有外部碎片，可以采用紧凑技术处理外部碎片

动态分区分配算法

首次适应算法：每次从低地址开始查找，找到第一个能满足大小的空闲分区
- 空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链
最佳适应算法：尽可能留下大片连续的空闲区
- 空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链
- 每次都选最小的分区进行分配，会留下越来越多的更小的碎片
- 算法开销大
最坏适应算法：每次分配有限利用最大的连续空闲区
- 空闲分区按容量递减次序链接，每次分配内存时顺序查找空闲分区链
- 可能导致后面大进程没有分区可用
- 算法开销大
邻近适应算法：每次从上次查找结束的位置开始检索
- 空闲分区按容量递增次序链接，每次分配内存时从上次结束位置开始查找，找到第一个满足的
- 低地址，高地址都是相同概率被使用，导致无大分区可用

首次适应算法的效果反而更好

非连续分配

系统为用户分配的可以是一些分散的内存空间
将内存空间分为一个个大小相等的区分，每个分区就是一个页框，或称页帧，内存块，每个页框都有一个编号，即页框号，从0开始
将用户进程的地址空间也分为与页框大小相等的一个个区域，称为页或者页面，每个页面也有一个编号，即页号，从0开始

页式管理中地址是一维的

操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中，进程的页面与内存的页框有一一对应的关系，每个页面不必连续存放，也不必按先后顺序

利用地址的偏移量+起始地址即可找到真正的地址

物理地址 = 页面始址 + 页面内偏移量

页号：逻辑地址/页面长度
页面偏移量：逻辑地址 % 页面长度
页面在内存中起始位置：操作系统记录

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表

一个进程对应一张页表
进程的每一页对应一个页表项
每个页表项由"页号"+"块号"组成
页表记录进程页面和实际存放的内存块之间的对应关系

基本分页存储管理

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址，通常会在系统中设置一个页表寄存器，存放页表在内存中起始地址F和页表长度M，进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中

逻辑地址：页号P-页面偏移量W
页表寄存器：页表始址F-页表长度M

根据逻辑地址计算出页号，页内偏移量
判断越界中断（if P>=M）
查询页表，找到页号
计算物理地址
进行访问

具有快表的地址变换机构

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很可能再次执行，如果某个数据被访问过，不久之后该数据很可能再次被访问
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问

快表：又称联想寄存器（TLB）是一种访问速度比内存快很多的告诉缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程，内存中的页表常称为慢表

就像Redis和MySQL的关系，多加了一级缓存

CPU给出逻辑地址，由某个硬件算的页号，页内偏移量，将页号与快表中的所有页号进行比较
如果找到匹配页号，则直接使用
如果没有，就查询内存页表，按照一定算法对旧页面进行替换

两级页表

某计算机按字节寻址，支持32为逻辑地址，采用分页管理，页面大小4KB，页表项长度为4B

1
2
3

4KB = 2^12B
20页号 + 12页内地址 -> 最多20页
2^20 = 1M = 1048576个页表项，页表需要2^20 * 4 = 2^22B，需要2^10个页框储存这个表

进程在一段时间内只需要访问某几个页面就可以正常运行，没必要让整个页表都常驻内存
把页表再次进行拆封，每一块刚好放进一个页面大小，也就是1024个
- 0# … 1023# 页表
为了记录这个页表（二级页表），我们需要一个页目录表，总共3个表
- 页目录表 -> 二级页表 -> 真正页表
32位 = 10（页目录表） + 10（二级页表）+ 12（页面偏移量）

各级页表的大小不能超过一个页面大小

第一次访存：访问内存中的页目录表
第二次访存：访问内存中的二级页表
第三次访存：访问目标内存单元

基本分段存储管理

进程的地址空间：按照程序自身的逻辑关系划分为若干各段，每个段都有一个段名，每段从0开始编址
内存分配规则：以段位单位进行分配，每个段在内存中占连续空间，但各段之间可以不相邻

分段的逻辑地址：段号 + 段内偏移量
段号占：16位，因此有2^16 = 64K个段
段内地址占16位，段最大长度是：2^16 = 64KB

1
2
3

// 写程序时[D], [X]会被翻译为对应段号，<A>, <B>会被翻译为段内地址
LOAD 1, [D] | <A>;  // 将分段D中A单位内的值读入寄存器1
STORE 1, [X] | <B>; // 将寄存器1的内容存入X分段的B单位中

同理，要找到真实的物理地址，需要为每个进程建立一张段映射表，简称段表

段号
段长
基址

段表寄存器：段表始址F+段表长度M
逻辑地址：段号S+段内地址W
是否M > S
是否段长 > W

查询段表 = F + S * 段表项长度
物理地址 = 段基址 + 段内地址

页是信息的物理单位，分页的主要目的是为了实现离散分配，提高内存利用率，分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的
- 分页的用户进程是1维的，程序员只需给出一个记忆符即可表示一个地址
段时信息的逻辑单位，分段的主要目的是更好地满足用户需求，一个段通常包含着一组属于一个逻辑模块的信息，分段对用户时可见的，用户编程时需要显式地给出段名
- 分段的用户进程地址是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址

分段比分页更容易实现信息的共享和保护

虚拟地址

多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
对换性：在作业运行时无需一直常驻内存，而是运行在作业运行过程中，将作业换入换出
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量

访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存
若内存空间不足，操作系统负责将内存中暂时用不到的信息换出到外存

请求分页储存管理

在基本分页上进行扩展

内存块号
- 状态位
  - 是否调入内存
- 访问字段
  - 可记录最近被访问过几次或记录上次访问的时间
- 修改位
  - 页面调入内存后是否被修改过
- 外存地址
  - 页面在外存中存放的位置

每当访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断
此时缺页的进程阻塞，放入阻塞列表，调页完成后再将其唤醒，放回就绪队列

如果内存中有空闲块，则为进程分配一个空闲块，并修改页表中相应的页表项
如果内存中没有休闲块，则由页面置换算法选择一个页面淘汰
- 如果该页面被修改过，需要写回外存

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断（处理仍需要保存CPU现成）
如果换入/换出太频繁，会有很大的开销

页面置换算法

用于选择哪些用不到的信息置换到外存，因为换入，换出需要磁盘IO，一个好的算法追寻更少的缺页率

最佳置换算法（OPT）

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率

执行的前提是要知道之后访问的页面有哪些，所以这是个理想化的算法，不可能实现

先进先出置换算法（FIFO）

每次选择淘汰的页面是最早进入内存的页面
把调入内存的页面根据先后顺序排成一个队列，需要换出页面时选择队头页面即可，队列的最大长度取决于系统为进程分配了多少个内存块

Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增
只有FIFO算法会产生Belady异常异常，另外FIFO虽然实现简单，但是和进程实际运行时规律不适应，性能差

最近最久未使用置换算法（LRU）

每次淘汰的页面是最近最久未使用的页面
赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面

算法性能好，还是实现困难，开销大

时钟置换算法（NRU）

是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法

简单的CLOCK算法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列
- 当某页被访问时，其访问位置为1
- 当需要淘汰一个页面时，只需检查页的访问位
  - 如果是0，就选择退出
  - 如果是1，就将它置为0
- 若第一轮扫描中所有的页面都是1，则将这些页面全部置为0
- 再进行第二轮扫描
- 淘汰一个页面最多经过两轮扫描

改进型的时钟置换算法

只有被淘汰的页面被修改过，才需要写回外存，再其他条件都相同时，应优先淘汰没有修改过的页面，避免IO操作。
增加修改位

修改位：0，没有被修改过
修改位：1，被修改过

用（访问位，修改位）表示

将所有可能被置换的页面排成一个循环队列
第一轮
- 从当前位置开始扫描到第一个（0，0）的帧用于替换，本轮扫描不修改任何标志位
第二轮
- 若第一轮扫描失败，则重新扫描，查找第一个（0，1）帧用于替换，本轮将所有扫描过的帧访问位设为0
第三轮
- 若第二轮扫描失败，则重新扫描，查找第一个（0，0）帧用于替换，本轮扫描不修改任何标志位
第四轮
- 若第三轮扫描失败，则重新扫描，查找第一个（0，1）帧用于替换

页面分配

驻留集：请求分页储存管理中给进程分配的物理块集合
- 太小：缺页频繁
- 太大：资源利用率低
固定分配
可变分配

局部置换：发生缺页时只能选进自己的物理块进行置换
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页的进程

固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变，若进程在运行中发生缺页，则只能从该进程在内存中选出一页换出，然后再调入需要的页面
- 缺点：个别爸爸再刚开始判断分配多少内存
可变分配全局置换：刚开始为每个进程分配一定数量的内存块，操作系统会保持一个空闲物理块队列，当某进程发送缺页时，从空闲物理块中取出一块分配给该进程，若无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。
- 缺点：被选中的进程拥有物理块会减少，缺页率会增加
- 只要缺页就会分配物理块
可变分配局部置换：刚开始会为每个进程分配一定数量的物理块，当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存，如果进程再运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度，反之，如果进程在运行中缺页率特别低，则可适当减少分配的物理块
根据频率分配物理块

调页策略

预调页策略：根据局部性原理，一次调入若干个相邻的页面，可能比一次调入一个页面更高效，但若没有被使用，则又是抵消的，因此可以预测，但是目前只有50%的成功率，主要用于首次调入，由程序员指出
请求调页策略：在运行期间发现缺页才将所缺页面调入内存，但是每次只调入1页，IO开销很大

从对换区进行调入，否则

不需要修改的数据从文件区直接调入
需要修改的先调入对换区，再调入

UNIX先从文件区调入，换出到对换区，下次从对换区调入

颠簸现象

刚刚换出的页面，马上又要换入内存，刚刚换入的页面马上又要换出外存，称为抖动，产生原因为进程频繁访问的页面数高于物理块数（那就加内存吧）

驻留集：请求分页储存管理中给进程分配的物理块集合
工作集：指再某段时间间隔内，进程实际访问的页面集合

系统可以检测工作集的状态来决定至少分配多少内存块，驻留集 > 工作集

文件系统

文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件
标识符：一个系统内的各文件标识符唯一，对用户无可读性，只是操作系统用于区分的内部名称
类型：指明文件的类型
位置：文件存放的路径，在外存中的地址
创建事件
上次修改事件
文件所有者信息
保护信息：对文件进行保护的访问控制信息

文件逻辑结构

无结构文件
- 二进制或字符流
有结构文件：有一组相似的记录组成，又称记录式文件，每条记录由若干个数据项组成
- 定长记录
  - 数据项
- 可变长记录

目录也是一种特殊的有结构文件

顺序文件

文件中的记录一个接一个地顺序排列，记录可以是定长的或可变长的，各个记录在物理上可以顺序存储或链式存储

顺序存储：逻辑上相邻的记录物理上也相邻
链式储存：逻辑上相邻的记录物理上不一定相邻

顺序文件
- 串结构：记录之间的顺序与关键字无关
- 顺序结构：记录之间的顺序按关键字顺序排列

只有物理顺序存储（定长记录）非串结构才可以随机存储，若保持顺序结构，则可实现快速检索，但是要增加或减少记录会比较麻烦

索引文件

建立一张索引表加快文件检索速度，每条记录对应一个索引项，索引表本身是定长记录的顺序文件，索引按顺序排序还可以折半查找，用于对信息处理的及时性要求比较高的场合
每个记录对应一个索引表项的话，索引表本身可能会更大，所以引入索引顺序文件：是索引文件和顺序文件思想的结合，用一组记录对应一个索引表项
为了进一步提高检索效率，可以为顺序文件建立多级索引表

文件目录

FCB：有序集合，文件目录项
- 文件名
- 物理地址
- 逻辑结构
- 物理结构
- 可读/可写
- 权限
- 建立事件
- 修改时间

操作

搜索
创建文件
删除文件
显示目录
修改目录

单机目录结构
- 整个系统只建立一张目录表，每个文件占一个目录项
- 不允许重名
两级目录结构
- 主文件目录
- 用户文件目录
多级目录结构

文件一般会在树状结构的叶节点，所以我们可以有一个当前目录，从当前目录出发的相对路径进行查找

树形结构不便于实现文件的共享

无环图目录结构
- 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，可以方便的实现文件共享（类似linux硬连接）
- 需要为每个共享结点设置一个共享计数器，用户删除文件，只删除FCB，并减1共享计数器，当为0时才删除结点

索引结点：搜索文件时只需要关注文件名，所以对文件目录项瘦身
文件越小，占用盘块越小，启动磁盘的次数就越少（每次IO读入一快）

磁盘索引结点
内存索引结点
- 内存索引结点会增加一些信息
- 文件是否修改…

文件的物理结构

文件的数据如何存放在外存中

文件块：文件的逻辑地址被分为一个个的文件块
- 逻辑地址（逻辑块号，块内地址）
磁盘块：操作系统按照块分配储存空间

文件连续分配

要求每个文件在磁盘上占有一组连续的块

逻辑块号，块内地址 -> 物理地址，块内地址

优点
- 支持：顺序访问+直接访问
- 移动磁头的距离也变短，连续分配的文件在顺序读写时速度最快
缺点
- 文件难以扩展
- 物理上采用连续分配，存储空间利用率低，会产生磁盘碎片

文件链接分配

采取离散分配的方式，可以为文件分配离散的磁盘块

隐式链接
- 目录中记录了文件的起始块号和结束块号
- 每个磁盘块中保存指向下一个磁盘的指针
- 只支持顺序访问，不支持随机访问
- 查找效率低，需要耗费空间储存指针
- 很方便扩展文件，不会产生磁盘碎片
显式链接
- 把用于连接文件的各物理块的指针显式地放在一张表中，文件分配表（FAT）
- 一个磁盘仅设置一张FAT，开机时读入并常驻内存
- 支持顺序访问和随机访问，且不需要访问磁盘进行转换
- 不会产生磁盘碎片，且方便扩展

文件索引分配

允许文件离散地分散在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块

索引块：索引表存放的磁盘块
数据块：文件数据存放的磁盘块

索引表是一个文件对应一个

优点
- 支持随机访问，拓展容易实现
缺点
- 索引表会占用空间

若文件索引表太大

链接方案
- 将索引表拆分，并链接索引块
- 找到最后的索引块效率非常低
多层索引
- 使第一层索引指向第二层索引块，以此类推
- 但是每次读取都需要进入树状结构，小文件也一样
混合索引
- 多种索引分配方式的结合
- 包含直接地址索引，又包含一级间接索引
- 还包含二级间接索引
- 对于小文件，只需要较少的读取

文件存储空间管理

空闲表法

用表管理空闲盘块数，为一个文件分配连续的存储空间，同样可采取首次适应，最佳适应，最坏适应

第一个空闲盘块号	空闲盘块数
0	2
5	1

回收区的前后都没有相邻的空闲区
回收区的前后都是空闲区
回收区的前面是空闲区
回收区的后面是空闲区

回收时要注意表项合并问题

空闲链表法

空闲盘块链
- 以盘块为单位组成一条空闲链
- 记录：链头+链尾
- 适用于离散分配的物理结构
空闲盘区链
- 以盘区为单位组成一条空闲链
- 盘区：连续的空闲盘块
- 记录这个盘的长度，下一个盘区
- 可以采取算法进行分配，或者多个分配
- 回收同样注意合并问题

位示图法

每个二进制位对应一个盘块，用矩阵进行储存

需要注意2维对1维的转换

成组链接法

空闲表法，空闲链表法不适用于大型文件系统，在文件卷的目录区中，专门用一个磁盘块作为超级块，当系统启动时将超级快读入内存，并且保存外存同步

超级块
- 下一组空闲盘块数
- 空闲块号组
  - 下一组空闲盘块数
  - 空闲块号组
    - 下一组空闲盘块数
    - 空闲块号组

在分配时，如果存有下一组空闲盘数的信息，需要先复制到超级块中
在回收的时候，如果满了，就建新一个分组，然后重新指向（类似链表）

文件的基本操作

创建文件
- 在外存中找到文件所需的空间
- 创建该文件对应的目录项
删除文件
- 找到对应的目录项
- 回收文件占用的磁盘块
- 删除文件的目录项
读文件
- 在打开文件时，已经有编号，提供读的文件编号（文件描述符），读多少，读到哪
写文件
- 在打开文件时，已经有编号，提供写的文件编号（文件描述符），写多少，从哪写
打开文件
- 找到对应的目录项，检测权限
- 将目录项复制到内存的打开文件表中
- 使用打开文件表的编号来操作文件
- 系统打开文件表：整个系统一张（有打开计数器）
- 用户进程打开文件表->对应系统打开文件表
关闭文件
- 将进程的打开文件表对应项删除
- 回收分配给文件的内存空间
- 系统打开计数器减1，若0则删除项

文件共享

共享只有一份文件，更改会同步

基于索引结点的共享（硬链接）
- 在索引表中创建指向索引结点的项，索引结点中设置一个链接计数变量，来记录目录有几个用户链接到该结点上
基于符号链的共享方式（软连接）
- 类似快捷方式，记录文件的位置

文件保护

口令保密
- 开销小
- 不够安全，口令储存在系统里
加密保护
- 提供密码才能解密
- 保密性强
- 需要时间加密解密
访问控制列表
- 精简访问列表：用户组
- 读
- 写
- 执行
- 添加
- 删除
- 列表清单

文件系统层次结构

            graph TD
            用户接口-->文件目录系统
文件目录系统-->用户接口
文件目录系统-->存取控制模块
存取控制模块-->文件目录系统
存取控制模块-->逻辑文件系统与文件信息缓冲区
逻辑文件系统与文件信息缓冲区-->存取控制模块
逻辑文件系统与文件信息缓冲区-->物理文件系统
物理文件系统-->逻辑文件系统与文件信息缓冲区
物理文件系统-->设备管理模块
设备管理模块-->物理文件系统
设备管理模块-->设备
设备-->设备管理模块
物理文件系统-->辅助分配模块
辅助分配模块-->物理文件系统

用户接口：向上提供接口
文件目录系统：找到FCB或索引结点，管理打开文件目录表
存取控制模块：文件保护
逻辑文件系统与文件信息缓冲区：文件记录号 -> 逻辑地址
物理文件系统：逻辑地址 -> 物理地址
辅助分配模块：负责分配回收空间
设备管理模块：和设备直接进行交互

磁盘

磁盘：一个盘
磁道：磁盘盘面的环
扇区：环继续划分的块

最内侧是扇区储存密度最大

(柱面号，盘面号，扇区号)确定一个扇区

磁盘调度算法

寻找时间
- 将磁头移动到指定磁道
  - 启动磁头臂s
  - 移动磁头：跨越n个磁道，每个耗时m
延迟时间
- 旋转磁盘，定位到目标扇区
- 转速r：平均时间1/(2r)
传输时间
- 从磁盘读出或写入数据的时间
- 转速r，字节数b，磁道上字节数N
  - (1/r)*(b/N) = b/(rN)

先来先服务
- 按照请求访问磁盘的先后顺序进行调度
- 公平，若请求集中，性能还行
最短寻找时机优先
- 贪心算法寻找当前最近的磁道
- 性能较好，平均寻道时间短
- 缺点：可能产生饥饿
扫描算法
- 就是来回扫描，但是必须移动到头才会转向
- 公平，不会饥饿，
- 有多余移动，响应不平均
LOOK算法
- 如果在这个方向上没有请求了，可以立刻改变方向
循环扫描算法
- 只有磁头朝某个特定的方向移动时才处理磁道访问请求，而快速返回的起始端过程不处理
- 还是要撞墙才能改变方向
C-LOOK算法
- 循环扫描算法进一步改进，没请求就可以返回起始端
- 同时返回也可以只返回到有请求的磁道上

减少磁盘延迟

如果扇区相邻，读完第一个不能连续读取第二个，因为要进行处理，所以需要再次旋转

交替编号：采用交替编号，将逻辑上相邻的扇区，在物理上交替相连，

磁盘地址结构设计

把数据放在多个盘同一个磁道上，就可以不移动磁头臂

盘面对应的扇区的编号错位

错位命名：可以让不同盘错开不能读取的那段时期

同一个时间只能有一个磁头臂在读写，且读取后一小段时间不能读写

磁盘管理

磁盘初始化
- 进行低级格式化（物理格式化）：将磁盘的各个磁道划分扇区，一个扇区分头，数据区域，尾
- 头尾用于奇偶校验，CRC循环冗余效验码
每个分区由若干柱面组成
逻辑格式化，创建文件系统，文件系统根目录，管理文件的数据结构

引导块

读取ROM的程序完成初始化
ROW只存放很小的bootstarp程序
完整的bootstarp程序存放在磁盘启动块

参见GPT，grub等

坏块：标注坏块，后续不需要使用

磁盘控制器维护一个坏块链表，可以保留扇区进行备用

IO设备

IO设备：将数据输入到计算机，或者可以接受计算机输出数据的外部设备
UNIX系统将外部设备抽象位一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作

人机交互类外部设备
储存设备
网络通信设备

信息交换单位

块设备
字符设备

IO控制器

CPU无法直接控制IO设备的机械部件，因此IO设备还要有一个电子部件作为CPU和IO设备机械部件之间的中介

接受和识别CPU发出的命令
- 控制寄存器来存放命令和参数
向CPU报告设备的状态
- 状态寄存器用于记录IO设备当前的状态
数据交换
- 数据寄存器，用来作为缓存
地址识别
- 给CPU提供寄存器的地址

IO控制器
- CPU与控制器的接口，完成通信
- IO逻辑
  - 负责接受和识别CPU的命令，并向设备发送命令
- 控制器与设备接口
  - 控制器与设备的接口，完成通信

CPU通过数据总线控制IO控制器，通过控制线+地址线与IO逻辑链接
IO控制器可能控制多个IO设备，所以需要区分

内存映像IO
- 在内存地址之后编址，与内存同一
寄存器独立编址
- 从0开始编址，需要指明控制器+寄存器编号

IO控制方式

程序直接控制方式
- 读写
  - CPU向控制器发出读，设置状态为忙碌
  - CPU轮询检查寄存器读状态
  - 设备传输数据
  - 控制器把数据放进寄存器，并把状态改为就绪
  - CPU读取到寄存器，然后转到内存
- CPU干预很频繁
- 每次读写一个字
- IO<->CPU<->内存
- 优点：实现简单
- 缺点：CPU利用率低，效率低
中断驱动方式（系统中断）
- CPU会在每个周期的末尾检查中断是否达到
- 中断处理需要保存环境，每次发送中断，只能读一个字
- CPU和IO设备可以并行运行，利用率提升
- IO<->CPU<->内存
DMA方式
- 直接存储器存取
- 传输单位由字变为块
- 直接传输数据到内存，不经过CPU
- 仅在传输开始和接受才需要CPU干预
- DMA控制器
  - DR：数据寄存器，缓存数据
  - MAR：存放内存地址，数据放哪
  - DC：剩余要读写的数据多少
  - CR：记录CPU发来的IO命令，状态信息
- 总线直接连接内存和DMA控制器
- 读数据还是一个字一个字读取
- 块必须连接，在内存也必须连续
- IO<->内存
通道控制方式
- 一种硬件，可以识别并执行一系列的通道指令
- CPU向通道发出IO指令，表明通道程序的内存位置，哪个IO设备
- 通道执行内存中的通道程序
- 完成任务后，向CPU发出信号
- 每次读写一组数据块
- IO<->内存
- 需要硬件支持，效率特别高

IO软件层次

            graph TD
            用户层软件-->设备独立性软件
设备独立性软件-->用户层软件
设备独立性软件-->设备驱动程序
设备驱动程序-->设备独立性软件
设备驱动程序-->中断处理程序
中断处理程序-->设备驱动程序
中断处理程序-->硬件
硬件-->中断处理程序

用户层软件：提供与用户交互的接口（库函数）
- 翻译为IO请求，通过系统调用请求操作系统内核服务
设备独立性软件：以设备硬件无关的功能在这里实现
- 向上提供接口
- 提供对设备的保护
- 差错处理
- 设备的分配与回收
- 数据缓冲区管理
- 建立逻辑设备到物理设备名的映射关系，选择相应的驱动程序
  - 逻辑设备表（LUT）
    - 逻辑设备名
    - 物理设备名
    - 驱动程序入口地址
设备驱动程序
- 主要负责对硬件的具体控制，翻译命令
中断处理程序
- 读出设备的状态，判断是否正常结束
  - 从设备中读入一个字的数据放到内存缓冲区
  - 或处理异常

IO核心子系统

用户层
- 假脱机技术（SPOOLing技术）

IO核心子系统（IO系统）
- 设备独立性软件
- 设备驱动程序
- 中断处理程序
IO调度
- 用某种确定的算法确定一个好的顺序来处理各个IO请求
- 如：磁盘调度
设备保护
- 把设备看作文件进行权限管理

假脱机技术

脱机：脱离主机的控制进行输入/输出
引入脱机技术，缓解了CPU与慢速IO设备的速度矛盾，现在用软件模拟脱机数据

            graph LR
            输入设备--输入进程-->输入缓冲区-->输入井
输出井--输出进程-->输出缓冲区-->输出设备

设备的分配与回收

设备固有属性
- 独占设备
- 共享设备
- 虚拟设备

安全分配方式：为进程分配一个设备后就将进程阻塞，本次IO完成后才将进程唤醒
- 优点：不会死锁
- 缺点：不能并行工作
不安全分配方式：发出IO请求后，还可以继续执行，直到IO请求得不到满足才阻塞
- 优点：可以并行处理，一个进程可以使用多个设备
- 缺点：可能发生死锁

静态分配：进程运行前为其分配所有资源，结束后归还资源，不会发生死锁
动态分配：动态的分配资源

设备控制表（DCT）

设备类型
设备标识符
设备状态
指向控制器表的指针：找到控制器信息
重复执行次数或时间：记录失败次数
设备队列的队首指针：指向正在等待设备的进程队列

控制器控制表：每个控制器对应一张COCT

控制器标识符
控制器状态
指向通道表的指针
控制器队列的队首指针
控制器队列的队尾指针

通道控制表：每个通道对应一张CHCT

通道标识符
通道状态
与通道连接的控制器表首址
通道队列的队首指针
通道队列的队尾指针

系统设备表（SDT）：记录了系统中全部设备的情况

表面1
表目1
- 设备类型
- 设备标识符
- 设备控制表
- 驱动程序入口

根据设备请求查找系统设备表
根据系统设备表找到设备控制表
1. 设备忙则等待队列
2. 不忙则分配给进程
根据设备控制表找到控制器控制表
1. 控制器忙则等待队列
2. 不忙则分配给进程
根据控制器控制表找到通道控制表
1. 控制器忙则等待队列
2. 不忙则分配给进程

只有设备，控制器，通道3者都分配成功时，本次设备分配才算成功，才能数据传输

用户编程需要提供物理设备名->建立逻辑设备名与物理设备名的转换

缓冲区管理

缓冲区就是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区，使用硬件作为缓冲区的成本很高，容量也不大，一般情况下，是利用内存作为缓冲区，设备独立性软件的缓冲区管理就是要组织管理好这些缓冲区

缓和CPU与IO设备之间的速度不匹配的矛盾
减少对CPU的中断频率，放宽对CPU中断响应时间的限制
解决数据粒度不匹配
提高CPU与IO设备之间的并行性

单缓冲

操作系统会在主存中为其分配一块缓冲区，缓冲区每次都要用干净才能读或者写
所以会耗时Max(C, T) + M

双缓冲

操作系统会在主存中为其分配两块缓冲区，缓冲区每次都要用干净才能读或者写
难以找到一个周期，平均耗时Max(T, C+M)

缓冲池

由系统中公用的缓冲区组成，这些缓冲区按使用状态可以分为

空缓冲队列
装满输入数据的缓冲队列
装满输出数据的缓冲队列

根据功能不同

用于收容输入数据的工作缓冲区
用于提取输入数据的工作缓冲区
用于收容输出数据的工作缓冲区
用于提取输出数据的工作缓冲区

就像爬虫池，选可用的用就行了

参考

2019 王道考研操作系统