2021操作系统

#Chapter 2：进程的描述与控制

#程序执行

程序顺序执行时的特征
- 顺序性
- 封闭性
- 可再现性
并发和并行
- 并发：一组逻辑上互相独立的程序在执行时间上客观重叠，即一个还未结束，另一个已经开始。
- 并行：一组程序在同一物理时刻同时执行
并发执行的特征
- 间断性
- 失去封闭性
- 不可再现性

#进程

进程的特征
- 动态性
- 独立性
- 并发性
- 异步性
- 结构化

进程 = 程序 + 数据 + PCB
- PCB：由操作系统维护的用来记录进程相关信息和管理进程的数据结构
  - 进程标识符
  - 调度信息
  - 处理机状态
  - 进程控制信息
- PCB的组织形式
  - 链表
  - 索引表

OS是根据PCB来对并发执行的进程进行控制和管理的。

进程和程序的区别
- 进程是动态的，程序是静态的
- 进程是暂时的，程序是永久的
- 进程和程序组成不同（进程三要素）
- 进程和程序的对应关系
  - 通过多次执行，一个程序可对应多个进程
  - 通过调用关系，一个进程可包括多个程序（？）
- 进程具有并行性，程序没有
- 进程是竞争计算机资源的基本单位
  
  #进程状态及其转换
双挂起模型
挂起进程的目的
- 提高处理机效率：就绪进程表为空时，OS将阻塞进程从内存中“挂起”到磁盘的“挂起队列”，再从该队列选另一进程进入内存，或接受一个新进程的请求。
- 为运行进程提供足够内存：资源紧张时，暂停某些进程，如：CPU繁忙（或实时任务执行），内存紧张
- 用于调试：在调试时，挂起被调试进程（从而对其地址空间进行读写）
挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况
- 阻塞到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以纳入新进程或运行就绪进程；
- 就绪到就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程；
- 运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态
激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况
- 就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进行这种转换
- 阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转为阻塞状态；较少出现。

#进程控制的功能

原语：由若干条指令构成的“原子操作(atomic operation)”过程
- 进程创建
- 进程撤销
- 进程阻塞
  - 进程自身的主动行为
- 进程唤醒
  - 由系统进程唤醒
  - 由事件发生进程唤醒
- 进程挂起
- 进程激活

#Chapter 3-5：进程同步

#进程同步与互斥

进程互斥
- 资源共享关系（间接互相制约关系）
- 进程本身之间不存在直接联系
进程同步
- 相互合作关系（直接互相制约关系）
- 进程本身之间存在着相互制约的关系

#临界资源

一段时间内只允许一个进程访问的资源，诸进程应采取互斥方式实现资源共享、

#临界区

#定义

临界区：每个进程中访问临界资源的代码
进入区：临界区前的一段用于进行临界资源检查的代码
退出区：将临界区正被访问的标志恢复为未被访问的标志

#使用临界区遵循的原则

空闲则入
忙则等待
有限等待
让权等待

#进程同步机制

解决诸进程互斥进入临界区的方法

硬件同步机制
软件同步机制

#硬件同步机制

#关中断

最简单的方法之一，缺点

滥用关中断权力导致严重后果
影响新系统效率，限制cpu交叉执行程序
不适用于多cpu系统

#Test and Set

借助硬件指令TS

#利用swap指令

如80x96的xchg

#进程互斥的软件方法

#一堆不完善的算法

算法1 单标志
- 强制轮流进入临界区
算法2 双标志先检查
- 检查和修改不是原子操作
- 可能同时进临界区
算法3 双标志后检查
- 可能都进不了临界区

#利用信号量机制

整型信号量
- 仅能通过 wait(S) 和 signal(S) 访问
- wait 时不放弃处理机
记录型信号量
- wait 时小于0则自我阻塞
- signal 时小于等于0则从阻塞队列取出一个进程放入就绪队列
AND型信号量
- Swait 多个资源信号量同时满足才执行，否则阻塞
- Ssignal 对占用的每个资源信号量都释放，然后检查每种资源的等待队列，取出的进程也要多个资源信号量同时满足

#经典进程同步问题

判断同步或互斥

同步：两个进程合作时，一个进程的执行必须依赖另一个进程
互斥：两个进程不能同时使用同一个资源

生产者消费者

NoneBashCSSCC#GoHTMLJavaJavaScriptJSONPerlPHPPowershellPythonRubySQLTypeScriptYAML

//Producer
P(empty);
P(mutex);
one unit -> buffer;
V(mutex);
V(full);

//Consumer
P(full);
P(mutex);
one unit <- buffer;
V(mutex);
V(empty);

读者写者

NoneBashCSSCC#GoHTMLJavaJavaScriptJSONPerlPHPPowershellPythonRubySQLTypeScriptYAML

//Writer
P(Wmutex);
write;
V(Wmutex);

//Reader
P(Rmutex);
if (Rcount == 0)
  P(Wmutex);
++Rcount;
V(Rmutex);
read;
P(Rmutex);
--Rcount;
if (Rcount == 0)
  V(Wmutex);
V(Rmutex);

#管程（Monitor）

#基本思想

把信号量及其操作原语封装在一个对象内部

#定义

管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块

#主要特性

模块化：一个管程是一个基本程序单位，可以单独编译
抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码
信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的

#实现要素

管程中的共享变量在管程外部是不可见的，只能通过调用外部过程间接访问
管程互斥进入
管程中设有进程等待队列及相应的等待及唤醒操作

#管程中的多个进程进入

当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权
当一个进入管程的进程执行唤醒操作时（如Ｐ唤醒Ｑ），管程中便存在两个同时处于活动状态的进程
唤醒切换方法（可采用下列两种之一，通常为第一种）
- P等待，Q继续，直到Q等待或退出
- Q等待，P继续，直到P等待或退出
- 规定唤醒为管程中最后一个可执行的操作
入口等待队列

试图进入一个已被占用的管程的进程在管程入口处等待的队列
紧急等待队列

管程内部由于执行唤醒操作，可能出现多个等待进程，进入紧急等待队列，优先级高于入口队列

#条件变量

表示一种等待原因，并不取具体数值。

形式为 Var x, y:condition，相应的操作为X.wait和X.signal。

X.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。

#管程的格式

NoneBashCSSCC#GoHTMLJavaJavaScriptJSONPerlPHPPowershellPythonRubySQLTypeScriptYAML

TYPE monitor_name = MONITOR;
共享变量说明
define 本管程内所定义、本管程外可调用的过程（函数）名字表
use    本管程外所定义、本管程内将调用的过程（函数）名字表
PROCEDURE 过程名（形参表）；
		过程局部变量说明；
		BEGIN
			语句序列；
		END;

......

FUNCTION 函数名（形参表）：值类型；
	函数局部变量说明；
		BEGIN
			语句序列；
		END;

......

BEGIN
	共享变量初始化语句序列；
END;

#管程的组成

名称：一个管程对应一个共享资源
数据结构说明：局部控制变量
操作原语：访问管程的唯一途径，本身互斥
初始化代码

#管程和进程的异同

设计目的不同
需要OS维护的数据结构不同
- PCB
- 等待队列
管程被进程调用
管程是操作系统的固有成分，无创建和撤销

#Chapter 6：进程通信及线程

#进程通信

一个进程直接或通过某一机构发一条消息给另一进程，且据此来控制其它进程，我们将进程之间的这种信息交流称为进程通信。

#进程通信类型

#低级通信机制

传送字节数较少，起到控制进程的作用
例子：PV操作
优点：速度快
缺点：信息量小，效率低，编程复杂

#高级通信机制

传送任意数量数据，解决了一个进程将大批量数据传递给另一个进程的问题‘

共享存储系统
- 基于共享数结构
- 基于共享存储区
- 原理：在内存中开辟一个共享区域
- 特点：效率高, 一个进程可以分配多个共享存储区，最大值由系统决定
消息传递系统

进程间通信以消息为单位进行
1. 直接通信
2. 间接通信：利用中间体
- 原理
  - 消息通信机构管理一组空闲缓冲区消息
  - A进程向B进程发送消息，申请一个缓冲区，填写有关信息后，发送信号给B进程
  - B进程读取数据并释放消息缓冲区
管道通信
- 管道：pipe文件
- 管道通信：发送进程（写进程）以字符流形式将大量数据送入管道，接收进程（读进程）从管道接收数据。
- 特征
  - FIFO
  - 传送任意量数据
  - 写满/读空则阻塞
- 三方协调能力
  - 双方都存在
  - 互斥
  - 同步
客户端-服务器系统
1. 套接字
2. 远程过程调用
3. 远程方法调用

#消息传递通信的实现方式

#直接消息传递系统

对称寻址方式

Send(receiver, message)

Receive(sender, message)
非对称寻址方式

Send(p, message)

Receive(id, message)

#间接通信方式——邮箱通信

邮箱定义为一种数据结构
- 邮箱头
- 邮箱体
条件和特点
- 为空才能发，不为空才能接收
- 系统提供邮箱创建、撤销，信息发送、接收的相关原语
- 收发进程无直接关系
- 收发进程间存在邮箱
邮箱通信原语

Send(mailbox, message)

Receive(mailbox, message)
邮箱类型
1. 私有：用户进程创建，属于该进程一部分，其他进程可以发，该进程读
2. 公用：操作系统创建

#线程

#引入

线程：作为CPU调度单位，而引入线程后进程只作为其他资源分配单位
- 只拥有必不可少的资源，如：线程状态、寄存器上下文、栈
- 同样具有三基本状态
优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度
- 同进程内线程共享内存和文件资源

#线程的状态

执行，就绪，阻塞。

#TCB

记录了用于控制和管理线程的信息。

#属性

轻型实体。（线程是进程中的一个实体）
独立调度和分派的基本单位。在多线程OS中,线程是能独立运行的基本单位,因而也是独立调度和分派的基本单位。而把进程作为资源拥有的单位。由于线程很“轻’’,故线程的切换非常迅速且开销小
可并发执行
共享进程资源

#线程等级

kernel-level thread

依赖于OS kernel
- 内核维护进程和线程的上下文信息
- 线程切换由内核完成
- 一个线程发起系统调用而阻塞，不会影响其他线程的运行。
- 时间片分配给线程，所以多线程的进程获得更多CPU时间。
user-level thread

不依赖于OS kernel
- 时间片分配给线程
- 用户线程的维护由应用进程完成
- 内核不了解用户线程的存在
- 用户线程切换不需要内核特权
- 用户线程调度算法可针对应用优化

#线程和进程的关系

线程是进程的一个组成部分。每个进程在创建时通常只有一个线程，需要时这个线程可以创建其它线程。
进程的多线程都在进程的地址空间活动。某进程内的线程在其他进程不可见。
资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源配额中扣除并分配给它。
处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。
线程在执行过程中，需要同步。

#Chapter 7-9 处理机调度与死锁

#作业和处理机调度

#作业的基本概念

用户角度定义
- 编程过程
- 在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所作的有关该次业务处理的全部工作称为一个作业。
- 作业步：在一个作业的处理过程中，计算机所作的相对独立的工作。
系统角度定义

作业 = 程序 + 数据（作业体）+ 作业说明书（作业控制语言）
作业组织
- 作业 = 程序 + 数据 + 作业说明书
- 作业说明书
  - 体现用户的控制意图
  - 组成
    - 作业基本情况
    - 作业控制描述
    - 作业资源要求描述
  - 由作业控制语言编写

作业控制语言

用户用于描述批处理作业处理过程控制意图的一种特殊程序

作业的建立
- 建立过程：一个作业的全部程序和数据输入到外存且在系统中建立了相应的作业控制块（job control block——JCB）
- 包括作业的输入和控制块的建立
- 作业的输入：将作业的程序、数据和作业说明书从输入设备输入到外存，并形成有关初始信息
- 必须有外部启动信号通知系统调用相应的作业输入管理程序——决定了作业的输入方式

#处理机调度（高级，中级和低级调度）

一个批处理型作业，通常需要经过高级调度(作业调度)、低级调度(进程调度)、中级调度，方能获得处理机。

高级调度（作业调度、长程调度）
- 功能：用于决定把外存上处于后备队列中的哪些作业调入内存
- 具体操作
  - 创建进程
  - 分配资源
  - 排在就绪队列尾端
低级调度（进程调度、短程调度）
- 功能
  - 保存现场
  - 按某种算法选取进程
  - 把处理机分配给所选进程（装入PCB恢复该进程断点）
- 进程调度机制
  - 排队器
  - 分派器
  - 上下文切换器
- 进程调度方式
  - 非抢占式
    - 正在执行的进程执行完毕，选一新进程
    - 执行中的进程因提出I/O请求而暂停执行
    - 进程调用了P、V操作
    - 分时系统中时间片用完
  - 抢占式
    - 优先权原则
    - 短作业（进程）有限原则
    - 时间片原则

中级调度
- 目的：提高内存利用率和系统吞吐量
- 功能
  - 挂起进程
  - 激活被挂起的进程

#调度队列模型

仅有进程调度的调度队列模型

具有高级和低级调度的调度队列模型
同时具有三级调度的调度队列模型

#选择调度方式和算法的准则

面向用户
1. 周转时间短（评价批处理系统）
  
  所谓周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)
2. 响应时间快（评价分时系统）
  
  响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或说直到在屏幕上显示出结果为止的一段时间间隔
3. 截止时间的保证（评价实时系统）
  
  所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。
4. 优先权准则
面向系统
1. 系统吞吐量高
2. 处理机利用率好
3. 各类资源的平衡利用

#调度算法

先来先服务算法（FCFS）

每次调度从就绪队列中选择最先进入的进程，一直执行到完成或发生阻塞为止
短进程优先算法（SJ(P)F）

从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度

缺点：不利于长作业
高优先权优先算法（FPF）
- 非抢占式
  
  系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程
- 抢占式
  
  在执行期间，只要出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。
- 优先权的类型
  - 静态优先权：在创建进程时确定，在进程的整个运行期间保持不变
    - 进程类型
    - 进程对资源的需求
    - 用户要求
  - 动态优先权：在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能

高响应比优先算法

优先权又相当于响应比RP。
- 等待时间相同，则要求服务的时间愈短，其优先权愈高
- 当要求服务的时间相同时，等待时间愈长，其优先权愈高
- 对于长作业，优先级随等待时间增加而提高

基于时间片的轮转算法（RR）

就绪进程按先来先服务的原则，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，将它送往就绪队列的末尾；依次执行下个进程

假设某时间片执行完毕时刻，有新进程到来，则先将新进程插入就绪队列尾部，然后才将刚刚时间片结束未执行完毕的进程插入就绪队列的尾部

优点：保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间

多级反馈队列调度算法
- 原则
  1. 设置多个就绪队列
  2. 各个队列优先级不同
  3. 各个队列进程执行时间片大小不同，优先级越高，时间片越小
- 实施过程
  - 新进程放入第1队列（优先级最高）的末尾，按FCFS调度
  - 在规定时间片内能完成，便正常结束；否则降级到下一队列
  - 降到第n队列（优先级最低）后，在其中按RR调度
    - 仅当更高优先级队列均为空闲，才调度第i队列中进程运行
  - 高优先级进程采用抢占原则，被抢占者放回本队列末尾

#实时调度

#特点（基本条件）

更详细的调度信息
抢先式调度
快速中断响应
快速上下文切换

#分类

非抢占式
- 非抢占式轮转
- 非抢占式优先
抢占式
- 基于时钟中断的抢占式
- 立即抢占

#常用的几种实时调度算法

都是基于任务的优先权，并根据确定优先级方法的不同而形成以下几种算法。

最早截止时间优先(EDF Earliest Deadline First)算法
最低松弛度优先(LLF)算法

松弛度 = 完成截止时间 - 服务时间

松弛度越小表示该任务越紧迫，优先级别越高。

算法要求实现一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行

#多处理机调度

#与单处理机调度的区别

注重整体运行效率
更多样的调度算法
多处理机访问OS数据解雇时的互斥
调度单位广泛采用线程

#对称式多处理系统

不用看。

#死锁

#概念

指两个或两个以上的进程都无限止的等待永不出现的资源而发生的一种状态。

#产生原因

竞争资源
- 可剥夺性资源
- 非剥夺性资源
- 临时性资源
- 永久性资源
进程间推进顺序非法

#必要条件

互斥使用
不可抢占
请求和保持
循环等待

#死锁处理方法概述

死锁预防
死锁避免
死锁检测+恢复
死锁忽略

死锁预防的方法例子
- 在进程执行前，一次性申请所有需要的资源
- 对资源类型进行排序，资源申请必须按序进行

死锁避免

安全状态：如果系统中的所有进程存在一个可完成的执行序列，则称系统处于安全状态

银行家算法

检测当前状态是否安全的流程

NoneBashCSSCC#GoHTMLJavaJavaScriptJSONPerlPHPPowershellPythonRubySQLTypeScriptYAML

int Available[1..m]; //每种资源剩余数量
int Allocation[1..n,1..m]; //已分配资源数量
int Need[1..n,1..m];//进程还需的各种资源数量
int Work[1..m]; //工作向量
bool Finish [1..n]; //进程是否结束

Work = Available; Finish[1..n] = false; 
while(true) { 
   for(i = 1; i <= n; i++) {
     if(Finish[i] == false && Need[i] <= Work) {
        Work = Work + Allocation[i];
        Finish[i] = true; break;
     }
     else goto end;
   }
}
end:
for(i=1;i<=n;i++) 
   if(Finish[i]==false) return “deadlock”;

完整算法流程：

对某个客户提出的贷款请求，先假设批准其请求，进入系统状态T
用上面的算法检测状态T是否安全
如果安全，则批准该请求；否则不批准该请求

死锁的检测和恢复
- 死锁检测
  - 发现问题再处理
  - 定时检测或发现资源利用率低时检测
- 死锁接触
  - 剥夺资源
  - 撤销进程

死锁忽略：没讲

休息一会

#Chapter 10-13 存储器管理

#存储器的层次结构

#存储组织

最佳状态：各层次的存储器都处于均衡的繁忙状态

#存储管理的功能

主存分配和回收
地址变换
存储共享和保护
主存地址扩充

#程序的装入和链接

#程序的装入（重定位方法）

重定位：将程序中的虚拟地址转换为主存中的物理地址的转化过程

可重定位装入（静态重定位）

程序运行前，由链接装入程序进行的一次重定位，完成地址转换，装入后不能移动、改变空间或被换出主存。
- 优点：不许硬件变换机构支持
- 缺点：需要占用连续空间，运行期间不能移动，不能共享
动态运行时装入（动态重定位）

在程序装入时保持逻辑地址不变，装入内存后仍是相对地址。

在程序执行的过程中，每当访问指令或数据时，才将要访问的指令或数据的逻辑地址转换成物理地址。

#分区存储管理

#分配方式

固定分区

把内存划分为若干个固定大小的连续分区。
1. 划分分区的方法
  - 分区大小相等
  - 分区大小不等
2. 内存分配
  
  使用分区说明表
3. 固定分区的进程队列
  
  多队列适用于大小不等的固定分区；单队列适用于大小相同的固定分区，也可用于大小不等
动态分区

在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。
- 优点：没有内碎片
- 缺点：有外碎片，如果大小不是任意的，也可能出现内碎片
- 将空闲分区合并，需要移动多个段(复制内容)：内存紧缩

#分区分配中的数据结构

空闲分区表
空闲分区链

#分区分配算法

首次适应算法（first fit）
- 空闲分区链以地址递增的次序链接，从链首开始顺序查找，直到找到能满足要求的空闲分区
- 优先分配低地址部分
循环首次适应算法
- 每次分配从上次找到的空闲分区的下一个空闲分区开始查找，直到找到
- 采用循环查找方式
最佳适应算法
- 将所有空闲分区按大小递增排序形成链表
- 从链首开始查找，第一个找到的必然最优
- 容易产生碎片

#分区分配操作

malloc
free
- 与相邻的空闲分区合并

#可重定位分区分配

内存紧缩

将各个占用分区向内存一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合并成为一个空闲分区
- 需要动态重定位
- 紧缩时机：每个分区释放后，或内存分配找不到满足条件的空闲分区时
动态重定位的实现
- 当紧缩时，不需修改程序，只要修改原本的基址
- 增加重定位寄存器存放基址

动态重定位分区算法

#对换

定义

把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。

对换是提高内存利用率的有效措施。
- 整体对换：以进程为单位
- 部分对换：以页或段为单位
对换空间的管理

数据结构：可以用空闲分区表或空闲分区链
- 外存空间分类
  - 文件区：离散分配
  - 对换区：连续分配

进程的换出和换入
1. 换出
  
  系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。
2. 换入
  
  系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。

#基本分页存储管理方式

#页面和页表

页面

一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页

相应地，也把内存空间分成与页面相同大小的若干存储块，称为（物理）块或页框

分配时，物理块可以不连续，而页内逻辑地址是连续的。

分页存储器的逻辑地址由两部分组成：页号和页内地址。

最后一页页内装不满形成的碎片叫做页内碎片
地址结构
页表

实现页号到物理块号的映射。

#地址变换机构——页表

地址变换机构的任务是实现逻辑地址到物理地址的转换，这一任务是借助页表完成的。

#简单页式

地址转换的公式为：绝对地址＝块号X块长+页内地址

引入TLB

一组相联快速存储，是寄存器，作为页表的缓存。

利用局部性原理

#两级和多级页表

两级页表

将页表也进行分页，离散地放在不同的物理块中，为离散分配的页表再建立一张页表，称为外层页表。

多级页表

#基本分段存储管理方式

#分段存储管理方式的引入

方便编程
信息共享：段是信息的逻辑单位
信息保护
动态增长
动态链接

#分段系统的基本原理

分段
- 基本原理：将程序的地址空间划分为若干段，程序加载时，分配其所需的所有段，这些段不必连续；物理内存的管理采用动态分区。需要CPU的硬件支持。
- 不同段可以分别编写和编译，可以采取不同保护，可以按段共享
- 优点：没有内碎片；便于改变进程占用空间大小
- 每个段都从0开始编址，并采用一段连续存储空间
- 段的长度并不相等
- 整个进程的地址空间是二维的

段表

段表实现从逻辑段到物理内存区的映射。

简单段式管理的数据结构
- 进程段表
- 系统段表
- 空闲段表

地址变换机构

#简单段式

地址变换举例
分页和分段的主要异同
- 相同
  - 都采用离散分配方式
  - 都通过地址映射机构实现地址变换
- 不同
  - 分页是出于系统管理的需要，分段是出于用户应用的需要
    - 一条指令或操作数可能会跨越两页，但不会跨越两段
  - 页的大小是系统固定的，段的大小通常不固定
  - 逻辑地址表示
    - 分页是一维的，所有页组成一个地址空间
    - 分段是二维的，每个段组成一个地址空间
  - 通常段比页大，因而段表比页表短，可以提高查找速度

#信息共享

#段页式存储管理

分页系统能有效地提高内存利用率，分段系统能很好地满足用户需要。结合二者优点，称为段页式系统。

基本原理

先把用户程序分成若干段，再把每个段分成若干页

地址变化过程
- 三次访存
  - 访问段表
  - 访问页表
  - 从地址中取数据

前面所介绍的各种存储器管理方式，它们都要求将一个作业全部装入内存方能运行。

#虚拟存储器基本概念

#定义

所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

其逻辑容量受限于计算机的地址结构和可用磁盘容量，其运行速度接近于内存速度。

#实现方法

分页请求系统

在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统
- 硬件支持
  - 请求分页的页表机制
  - 缺页中断机构
  - 地址变换机构
- 实现请求分页的软件
分段请求系统

它是在分段系统的基础上，增加了请求调段功能、分段置换功能所形成的段式虚拟存储系统
- 硬件支持
  - 请求分段的段表机制
  - 缺段中断机构
  - 地址转换机构

#虚拟存储器的特征

多次性（最重要的特征）

一个作业被分成多次地调入内存运行，亦即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可，以后运行到那一部分时再将它调入。
对换性

允许在作业的运行过程中换入、换出。
虚拟性（表现出来的最重要的特征）（ppt上就这么写的😅）

能够从逻辑上扩充内存容量

#请求分页存储管理方式

换进换出的基本单位是固定长的页面。

#硬件支持

页表机制

要在基础分页管理方式的页表上增加若干位
缺页中断

缺页中断在指令执行期间产生和进行处理，所缺页面被调入后，重新执行被中断的指令。

一条指令的执行可能产生多次缺页中断。
地址变换机构

#虚拟存储的调入策略、分配策略和清除策略

调入策略（确定调页时机）
- 请求调页
- 预调页
分配策略
- 如何对物理内存进行分配（最先适应、最佳适应等）
- 在虚拟段式、段页式管理中不用考虑
清除策略
- 请求清除
  
  该页被置换时才调出
- 预清除
  
  该页被置换前就调出，因而可以成批调出多个页面

#内存分配策略和分配算法

涉及三个问题

最小物理块数的确定

指保证进程正常运行所需的最小物理块数。

与硬件结构有关，取决于指令的格式、功能和寻址方式。
物理块的分配策略
1. 固定分配局部置换
  
  为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变。（固定分配）
  
  运行时缺页，则从分配给该进程的n个页面中选出一页换出，然后再调入一页，保证该进程的内存空间不变。（局部置换）
2. 可变分配全局置换
3. 可变分配局部置换
物理块的分配算法

#调页策略

何时调入页面
- 预调页
- 请求调页
从何处调入页面

请求分页系统的外存分为文件区和对换区。对换区采用连续存储，速度更快

有三种情况
1. 系统拥有足够的对换区空间
  
  可以全部从对换区调入页面，前提是在进程运行前将所需文件从文件区拷贝到对换区。
2. 系统缺少足够的对换区空间
  
  凡是不会被修改的文件，都直接从文件区调入，因而被置换时也不必换出。
  
  可能被修改的文件，在被换出时放入对换区。
3. UNIX方式
页面调入过程

每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。

如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。

#页面置换算法

选择页面换出的算法

抖动：刚被换出的页很快又重新被调用

#最佳置换算法和先进先出置换算法

最佳置换算法（OPT）

理论算法，被淘汰的页面在将来最长时间内不再被访问。
先进先出置换算法（FIFO）

总是淘汰最先进入内存的页面。

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

选择最近最久未使用的页面淘汰

#Clock置换算法（LRU的近似）

LRU对硬件支持要求较高

简单的Clock置换算法
- 为每页设置一位访问位，将所有页面链成循环链表。
- 当某页被访问时，访问位置1
- 在寻找一页淘汰时，按FIFO顺序遍历链表
  - 若为0，就淘汰该页，遍历指针停在下一位
  - 若为1，则将其置0
改进型Clock算法

设置访问位A和修改位M，组合成四种情况
- A = 0, M = 0：最佳淘汰页
- A = 0, M = 1：最近未被访问但已被修改，不是很好
- A = 1, M = 0：最近已被访问，未被修改，可能再次被访问
- A = 1, M = 1：最近已被访问且被修改
执行流程如下
1. 从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A。
2. 如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
3. 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

#轮转算法

上面简单clock算法的非链表版本，按地址先后检查各页

#最不常用算法（LFU）

选择到当前为止被访问次数最少的页面
每页设置访问计数器，每当页面被访问，计数器+1
要淘汰页面时，淘汰计数器最小的页面，并将所有计数清零

Belady现象：增加分配给作业的内存块数，反而增加了缺页次数，提高缺页率

#请求分段存储管理方式

在请求分段系统中，程序运行之前只需先调入若干个分段（不必调入所有的分段），便可启动运行。当所访问的段不在内存时，可请求OS将所缺的段调入内存。

#硬件支持

段表机制

在简单分段的基础上增加若干项。

缺页中断机构
地址变换机构

#分段的共享和保护

共享段表

在系统中配置一张共享段表，所有共享段都在其中有一表项

不同进程用可用不同段号共享同一段，并有各自的读写权限。

共享段的分配和回收
1. 分配
  
  共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1。
  
  当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count = count + 1操作，以表明有两个进程共享该段
2. 回收
  
  当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count = count - 1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录
分段保护
1. 越界检查
2. 存取控制检查（rwx）
3. 环保护机构（ring）
  - 低编号的环具有高优先权，OS核心处于0环内；某些重要的实用程序和操作系统服务，占居中间环；而一般的应用程序，则被安排在外环上
  - 一个程序可以访问驻留在相同环或较低特权环中的数据
  - 一个程序可以调用驻留在相同环或较高特权环中的服务

#Chapter 14-15：设备管理

管理的对象：I/O设备或I/O通道
基本任务：提高利用率，提高速度
主要功能：缓冲区分配，设备分配，设备处理，虚拟设备，实现设备独立性
特点：外设种类多，差异大
目的：外设资源的控制，外设资源的共享，提高外设资源的利用率

#I/O系统

#I/O设备

I/O设备的类型
1. 按传输速率分类
  - 低速设备
  - 中速设备
  - 高速设备
2. 按信息交换的单位分类
  - 块设备
    - 传输速率高
    - 可寻址，即支持随机读写
    - 常采用DMA方式
  - 字符设备
    - 传输速率低，常采用中断驱动方式
3. 按设备共享属性分类
  - 独占设备：即临界资源
  - 共享设备
  - 虚拟设备：通过虚拟技术将一台独占设备变换为若干台逻辑设备
设备与控制器之间的接口（联动华栋）

#设备控制器

基本功能
- 接收和识别命令
- 数据交换
- 标识和报告设备状态
- 地址识别
- 数据缓冲
- 差错控制
组成

#I/O通道

引入

一种特殊的处理机，具有执行I/O指令的能力，并通过执行通道（I/O）程序来控制I/O操作

与一般处理机不同
- 指令类型单一
- 没有自己的内存（与CPU共享内存）
通道类型
1. 字节多路通道（以字节为传送单位）
2. 数组选择通道（以数组为传送单位）
  
  只含有一个分配型子通道，可以连接多台高速设备，在一段时间内只能执行一道通道程序。
  
  当某台设备占用了该通道后，便一直由它独占，即使是它无数据传送，通道被闲置。
  
  速率高但利用率很低。
3. 数组多路通道
  
  将数组选择通道传输速率高和字节多路通道能使各子通道(设备)分时并行操作的优点相结合而形成的一种新通道。它含有多个非分配型子通道。

“瓶颈”问题

单通路I/O系统

多通路I/O系统总线型I/O系统

#I/O控制方式

#程序I/O方式

I/O操作由程序发起，并等待操作完成，数据每次读写经过CPU。

缺点：等待

#中断驱动I/O方式

I/O操作由程序发起，在操作完成时（如数据可读或已经写入）由外设向CPU发出中断，通知该程序。数据的每次读写通过CPU。

优点：不等待

缺点：CPU每次处理的数据量少

#DMD I/O 方式

由程序设置DMA控制器中的若干寄存器值（如内存始址，传送字节数），然后发起I/O操作，而后者完成内存与外设的成批数据交换，在操作完成时由DMA控制器向CPU发出中断。

优点：CPU只需干预I/O操作的开始和结束，而其中的一批数据读写无需CPU控制，适于高速设备。

特点：

数据传输基本单位是数据块
数据直接在设备和内存间传输
仅在一次传送开始和结束时需要CPU干涉，整块数据传送由控制器控制

工作过程

#I/O通道控制方式

DMA方式的发展，进一步减少CPU的干预，即把对一个数据块的读(或写)为单位的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。

又可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

通道程序

通道通过执行通道程序，并与设备控制器共同实现对I/O设备的控制。

由一系列的通道指令(或称为通道命令)所构成。

每条指令包含下列信息
- 操作码
- 内存地址
- 计数
- 通道程序结束位
- 记录结束标志

#缓冲管理

#缓冲的引入

缓和CPU与I/O设备间数据不匹配的矛盾
减少对CPU的中断频率，放宽对CPU中断响应时间的限制
提高CPU和I/O设备间并行性

#单缓冲和双缓冲

单缓冲

对一块数据处理时间为 max(T, C) + M
双缓冲

对一块数据处理时间为max(T, C + M)

#循环缓冲

循环缓冲的组成（多个缓冲区，三个指针）

Nexti：空缓冲区

Nextg：进程下个可用缓冲区

current：进程当前正在使用缓冲区

#缓冲池（多进程能有效的同时处理输入输出）

缓冲池的组成

至少含有空闲缓冲区、装满输入数据缓冲区、装满输出数据缓冲区，对应三个队列
- 空缓冲队列
- 输入队列
- 输出队列
还需四种工作缓冲区
- 收容输入数据
- 提取输入数据
- 收容输出数据
- 提取输出数据
Getbuf和Putbuf
缓冲区的工作方式

#设备分配

设备分配是对进程使用外设过程的管理。

#设备分配数据结构

设备控制表（DCT）

每个设备一张，描述设备特性和状态

系统设备表：系统内一张，反应系统中设备资源的状态
控制器控制表：每个控制器一张，描述I/O控制器的配置和状态

#设备分配原则

原则：合理使用外设（公平和避免死锁），提高设备利用率

静态分配：进程创建时分配，退出时释放
- 不出现死锁
- 利用率不高
动态分配
- 需要考虑死锁
- 提高设备利用率
- 针对特定设备采用特定分配策略
  - FCFS
  - 基于优先级

#设备独立性

概念

也称设备无关性
- 应用程序独立于具体使用的物理设备
- 引入逻辑设备和物理设备两个概念
- 应用程序中使用逻辑设备名称请求某类设备；系统实际执行时，使用物理设备名称
设备独立性软件
1. 执行所有设备的公有操作
  - 对独立设备的分配与回收
  - 将逻辑设备名映射为物理设备名，进一步可以找到相应物理设备的驱动程序
  - 对设备进行保护，禁止用户直接访问设备
  - 缓冲管理，即对字符设备和块设备的缓冲区进行有效的管理，以提高I/O的效率
  - 差错控制。由于在I/O操作中的绝大多数错误都与设备无关，故主要由设备驱动程序处理，而设备独立性软件只处理那些设备驱动程序无法处理的错误
2. 向用户层（或文件层）软件提供统一接口

#SPOOLing技术

利用假脱机技术，可以把独享设备转变成具有共享特征的虚拟设备，从而提高设备利用率。

引入

在多道批处理系统中，专门利用一道程序（SPOOLing程序）来完成对设备的I/O操作。无需使用外围I/O处理机。

原理：
- SPOOLing程序和外设进行数据交换，可以称为“实际I/O”。
  - 一方面，SPOOLing程序预先从外设输入数据并加以缓冲，在以后需要的时候输入到应用程序；
  - 另一方面，SPOOLing程序接受应用程序的输出数据并加以缓冲，在以后适当的时候输出到外设。
- 在SPOOLing程序中，需要管理两级缓冲区：内存缓冲区和快速外存上的缓冲池，后者可以暂存多批I/O操作的较多数据。
- 应用程序进行I/O操作时，只是和SPOOLing程序交换数据，可以称为“虚拟I/O”。
  
  这时虚拟I/O实际上是从SPOOLing程序的缓冲池中读出数据或把数据送入缓冲池，而不是跟实际的外设进行I/O操作。
SPOOLing系统的组成
1. 输入井和输出井
  
  在磁盘上开辟的两个大存储空间。
  
  输入井是模拟脱机输入时的磁盘，用于收容I／O设备输入的数据
  
  输出井是模拟脱机输出时的磁盘，用于收容用户程序的输出数据
2. 输入缓冲区和输出缓冲区
  
  在内存中开辟两个缓冲区。
  
  输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井
  
  输出缓冲区用于暂存从输出井送来的数据，以后再传送给输出设备
3. 输入进程SPi和输出进程SPo
  
  SPi进程模拟脱机输入时的外围控制机，将用户要求的数据从输入设备，通过输入缓冲区再送到输入井。当CPU需要输入数据时，直接从输入井读入内存。
  
  SPo进程模拟脱机输出时的外围控制机，把用户要求输出的数据，先从内存送到输出井，待输出设备空闲时，再将输出井中的数据，经过输出缓冲区送到输出设备上

系统组成

工作原理

共享打印机

当用户进程请求打印输出时， SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程，而只为它做两件事
- 由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中
- 输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求打印队列上

SPOOLing系统的特点
- 提高了I/O速度
- 将独占设备改造为共享设备
- 实现了虚拟设备功能

什么是虚拟设备？实现虚拟设备的关键技术是什么？虚拟设备是通过某种虚拟技术，将一台物理设备变换成若干台逻辑设备，从而实现多个用户对该物理设备的同时共享。由于多台逻辑设备事实上不存在，而只是给用户的一种感觉，因此被称作虚拟设备。常通过在可共享的、高速的磁盘上开辟两个大的存储空间(即输入井和输出井)以及预输入、缓冲输出技术来实现。预输入和缓输出可通过脱机和假脱机技术实现，假脱机是目前使用最广泛的虚拟设备技术。

#设备控制

#设备的控制过程

转换
合法性检查
可用性检查
参数设置
启动I/O
中断处理

#设备控制过程的实现方式

作为应用进程的一部分执行：与程序控制I/O相对应，难以对外设发出的中断作实时响应
作为系统进程执行：每类设备一个进程，或整个系统一个进程处理各类设备
不设进程，作为OS核心中的设备驱动程序

#设备驱动程序

I/O处理功能的低级系统例程。

特征：

中转数据和控制
与硬件特性密切相关
向上屏蔽设备细节

处理过程（主要任务是启动设备）：

将抽象要求转换为具体要求
检查I/O请求的合法性
读出和检查设备的状态
传送必要的参数
工作方式的设置
启动I/O设备

#磁盘设备管理

#磁盘I/O访问时间的组成

柱面定位时间：磁头移动到指定柱面时间
旋转延迟时间：磁头旋转到指定扇区时间，与磁盘转速相关
数据传送时间

由于柱面定位时间在访问时间中占主要部分，合理组成磁盘数据的存储位置可提高磁盘I/O性能。

#磁盘I/O调度策略

先来先服务（FCFS）
最短寻道时间优先（SSTF）

磁臂粘着：有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。
SCAN算法（电梯算法）

先按一个方向找最近，到尽头再换方向
循环扫描算法（CSCAN）

只按一个方向，到尽头就循环从头开始
NStepSCAN算法
1. N步SCAN是将磁盘请求队列分成若干长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。
2. 每个子队列按SCAN算法处理完后，才处理其它子队列
3. 新请求放入其它队列；避免粘着
4. 但是当N取值很大时，算法类似于SCAN；N=1时，算法退化为FCFS
FSCAN算法（N步SCAN算法的简化）

将磁盘请求队列分为两个子队列
- 一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。
- 另一个是在扫描期间，将新出现的所有请求磁盘I/O的进程放入等待处理的请求队列。
- 所有新请求被推迟到下一次扫描时处理。

#Chapter 16：文件管理

#文件，抽象的磁盘块集合

#文件，磁盘，数据项

文件是数据的一种组织形式，指具有文件名的若干相关元素的集合。
文件管理系统：是指文件和对文件进行操纵和管理的软件集合
文件系统中数据的分类：数据项、记录和文件三级。

#文件系统，抽象整个磁盘

#文件系统模型

对象及其属性
1. 文件
2. 目录
3. 磁盘存储空间
文件系统

对对象操纵和管理的文件集合
- 对文件存储空间的管理
- 对文件目录的管理
- 用于将文件的逻辑地址转换为物理地址的机制
- 对文件读和写的管理
- 对文件的共享与保护等功能
文件系统的接口
- 命令接口：用户与文件系统交互
- 程序接口：用户程序与文件系统交互

#文件系统的功能

实现从逻辑文件到物理文件的转换
有效的分配文件的存储空间
建立文件目录
提供合理的存取方法适应不同的环境
提供文件的共享、保护和保密
提供一组文件操作

#文件的逻辑结构

#文件逻辑结构的类型

有结构文件（记录文件）
- 定长记录
- 变长记录
- 顺序文件
- 索引文件
- 索引顺序文件
无结构文件（流式文件）

#顺序文件

逻辑记录的排序
只有顺序文件才能存储在磁带上
缺点
- 需要逐个查找记录
- 难以增删

#索引文件

#索引顺序文件

顺序文件分为若干组，每组第一个记录放入索引表

#直接文件和哈希文件

根据给定的记录键值直接获得指定记录的物理地址

哈希文件是最常见的直接文件。

#外存分配方式（物理结构）

#连续分配

优点
- 顺序访问容易
- 顺序访问速度快
缺点
- 要求有连续的存储空间
- 必须事先知道文件长度

#链接分配

隐式链接

显式链接

#索引分配

单级索引分配

多级索引分配

多级索引

混合索引

#目录管理

#文件控制块FCB和索引节点

文件控制块
1. 基本信息类
  - 文件名
  - 文件物理位置
  - 文件逻辑结构
  - 文件物理结构
2. 存取控制信息类
3. 使用信息类

#目录结构

单级目录结构
- 查找速度慢
- 不允许重名
- 不便于实现文件共享
两级目录
多级目录结构

#Extension：翻转课堂PPT😅

自己看

#Chapter 2：进程的描述与控制

#程序执行

#进程

#进程状态及其转换

#进程控制的功能

#Chapter 3-5：进程同步

#进程同步与互斥

#临界资源

#临界区

#定义

#使用临界区遵循的原则

#进程同步机制

#硬件同步机制

#关中断

#Test and Set

#利用swap指令

#进程互斥的软件方法

#一堆不完善的算法

#利用信号量机制

#经典进程同步问题

#管程（Monitor）

#基本思想

#定义

#主要特性

#实现要素

#管程中的多个进程进入

#条件变量

#管程的格式

#管程的组成

#管程和进程的异同

#Chapter 6：进程通信及线程

#进程通信

#进程通信类型

#低级通信机制

#高级通信机制

#消息传递通信的实现方式

#直接消息传递系统

#间接通信方式——邮箱通信

#线程

#引入

#线程的状态

#TCB

#属性

#线程等级

#线程和进程的关系

#Chapter 7-9 处理机调度与死锁

#作业和处理机调度

#作业的基本概念

#处理机调度（高级，中级和低级调度）

#调度队列模型

#选择调度方式和算法的准则

#调度算法

#实时调度

#特点（基本条件）

#分类

#常用的几种实时调度算法

#多处理机调度

#与单处理机调度的区别

#对称式多处理系统

#死锁

#概念

#产生原因

#必要条件

#死锁处理方法概述

#Chapter 10-13 存储器管理

#存储器的层次结构

#存储组织

#存储管理的功能

#程序的装入和链接

#程序的装入（重定位方法）

#分区存储管理

#分配方式

#分区分配中的数据结构

#分区分配算法

#分区分配操作

#可重定位分区分配

#对换

#基本分页存储管理方式

#页面和页表

#地址变换机构——页表