计算机操作系统

• 计算机操作系统
  • 概论
    • 操作系统的定义
    • 操作系统发展
    • 操作系统特征
    • 操作系统运行机制
      • 系统调用
      • 中断分类
      • 外中断处理过程
    • 操作系统体系结构
  • 进程与线程
    • 进程
      • 进程的状态
      • 进程的组织
      • 进程通信
    • 线程
      • 线程的实现方式
  • 进程互斥与同步
    • 互斥软件实现方法
    • 互斥硬件实现方法
    • 信号量机制
      • 例
      • 管程
  • 进程调度
    • 调度
      • 调度算法性能指标
      • 调度层次
      • 调度算法
    • 死锁
      • 死锁的处理
  • 内存
    • 程序装入方式
    • 连续内存分配
    • 非连续内存分配
      • 分页存储管理
      • 分段存储管理
      • 段页式存储管理
    • 虚拟内存
      • 页面置换算法
      • 页面分配策略
  • 设备
    • 设备分类
    • 设备控制器
      • 控制方式
    • 设备分配
  • 磁盘
    • 磁盘
      • 磁盘读写耗时
      • 磁盘调度算法
      • 数据交付方式
      • 减少延迟方法
      • 磁盘初始化
      • 磁盘分区
    • 磁盘容错
      • 磁盘冗余阵列
      • 磁盘容错技术
  • 文件
    • 文件存储空间管理
    • 文件逻辑结构
    • 文件目录结构
    • 文件物理结构

概论

操作系统的定义

• 操作系统是系统软件（软件分为系统软件和应用软件）；
• 操作系统是用户与计算机硬件系统之间的接口（包括用户接口和程序接口），隐藏了对硬件操作的细节；
• 操作系统是资源（处理器、存储器、IO设备、文件）的管理者，实现了对计算机资源的抽象。

操作系统发展

操作系统特征

• 并发：宏观上同时，微观上交替。
• 共享：资源贡献，共享方式——互斥共享、同时共享。
• 虚拟：物理实体变为若干逻辑对应物，实现技术——空分复用、时分复用。
• 异步：由并发性产生了异步性。

操作系统运行机制

用户态可以发生：系统调用、中断（外部中断、缺页等），但不能发生进程切换。

系统调用

系统调用需要执行一些特权指令，故需要在核心态下进行。

系统调用是操作系统与程序之间的接口。

系统调用和库函数：系统调用需要使用汇编语言调用。高级语言库函数可以是对系统调用的封装（即库函数不一定使用到系统调用）。

操作系统主要功能（系统调用功能）：处理机管理（进程控制、进程同步、进程通信、进程调度）、存储器管理/内存管理、设备管理、文件管理。

中断分类

• 内中断（异常、例外、陷入）：来自CPU内部
  • 自愿中断：指令中断（如trap）
  • 强迫中断：硬件故障（如缺页）、软件中止（如除0）
• 外中断（狭义的中断）：来自CPU外部
  • 外设请求
  • 人工干预

外中断处理过程

• 每个指令完成后，检查是否有外部中断信号；
• 若检测到中断信号，则保护被中断进程的CPU环境（关键寄存器内容）；
• 根据中断信号类型转入相应的中断处理程序；
• 恢复被中断进程进程的CPU环境，并退出中断。

操作系统体系结构

操作系统是层次且模块化的。

分类：无结构、模块化结构、分层式结构、微内核结构（小内核、C/S模式、机制与策略分离、面向对象技术）。

原语：由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断，由关中断和开中断来实现。

进程与线程

程序（Program）：是指令的有序集合（静态概念）。

进程（Process）：进程实体（PCB）的运行过程（动态概念），是系统进行资源分配和调度的独立单位。一个进程可以执行多个程序。

作业（Job）：起源于批处理系统，用户在一次计算过程中或者事务处理过程中，要求计算机所作工作的集合。一个作业可由多个进程组成。

顺序执行的程序具有：顺序性、封闭性、可再现性

并发执行的程序具有：间断性、无封闭性、不可再现性。

进程的特征：

• 动态性（最基本特征）
• 并发性
• 独立性（资源分配、调度的独立单位）
• 异步性（不可预知的速度推进，可能导致结果的不确定性）
• 结构性。

进程

进程实体：$\textnormal{\footnotesize 进程实体（进程映像）} = \{\textnormal{\footnotesize 程序段（程序代码）}, \textnormal{\footnotesize 数据段（程序运行时数据）}, PCB\}$

PCB（Process Control Block）：常驻内存，$PCB = \{\textnormal{\footnotesize 进程标识符}, \textnormal{\footnotesize 处理机状态信息}, \textnormal{\footnotesize 进程调度信息}, \textnormal{\footnotesize 进程控制信息}\}$，创建进程就是创建进程实体中的PCB。撤销进程就是撤销进程实体中的PCB。

进程的状态

• 运行态：独占CPU的一个物理内核运行。
• 就绪态：已具备运行条件（运行所需资源），排队等待CPU空闲。
• 阻塞态：等待事件触发后进入就绪态。
• 创建态：OS为进程分配资源、初始化PCB。
• 终止态：OS回收进程资源，撤销PCB。

进程的组织

进程通信

• 共享存储系统
  • 共享变量：可被多个进程访问，但不一定互斥
• 消息传递：直接通信（直接挂到接受进程的消息缓冲队列）、间接通信（先发送到信箱）。
• 管道通信：半双工通信，没有写满不能读，没有读空不能写。
• C/S系统：Socket通信。

线程

没有引入线程时，传统的进程是程序执行流的最小单位。引入线程后，进程是资源分配的基本单位；线程是调度的基本单位。同一进程的线程间并发不需要切换进程的运行环境，所以开销更小。

线程特点：轻型实体、独立调度和分配基本单位、可并发、共享进程资源。

线程的实现方式

进程互斥与同步

进程互斥：对临界资源的访问，需要互斥进行。即当一个进程进入临界区使用临界资源时，另一个进程必须等待。

访问临界资源原则：空闲让进、忙则等待、有限等待、让权等待

进程同步：保证各个进程按预期的方式推进。

互斥软件实现方法

单标致法、双标志先检查法、双标志后检查法、Peterson算法

/**
 * 【单标致法】
 * 说明：每个进程进入临界区的权限只能被另一个进程赋予。
 * 问题：不遵循空闲让进。
 */
int turn = 0;

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

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

/**
 * 【双标志先检查法】
 * 说明：先检查后上锁，标记每个进程想进入临界区的意愿。
 * 问题：不遵循忙则等待，若按①⑥②⑦③⑧顺序，则两者同时访问临界区。
 */
bool flag[2];
flag[0] = false;
flag[1] = false;

// P0
while(flag[1]) {        // ①进入区，其它进程是否想进入
    flag[0] = true;     // ②进入区，表明自己意愿
    ...;                // ③临界区
    flag[0] = false;    // ④退出区
    ...;                // ⑤剩余区
}

// P1
while(flag[0]) {        // ⑥进入区，其它进程是否想进入
    flag[1] = true;     // ⑦进入区，表明自己意愿
    ...;                // ⑧临界区
    flag[1] = false;    // ⑨退出区
    ...;                // ⑩剩余区
}

/**
 * 【双标志后检查法】
 * 说明：先上锁后检查。
 * 问题：不遵循空闲让进和有限等待，若按①⑥②⑦顺序，则两者均无法访问临界区。
 */
bool flag[2];
flag[0] = false;
flag[1] = false;

// P0
flag[0] = true;         // ①进入区，表明自己意愿
while(flag[1]) {        // ②进入区，其它进程是否想进入
    ...;                // ③临界区
    flag[0] = false;    // ④退出区
    ...;                // ⑤剩余区
}

// P1
flag[1] = true;         // ⑥进入区，表明自己意愿
while(flag[0]) {        // ⑦进入区，其它进程是否想进入
    ...;                // ⑧临界区
    flag[1] = false;    // ⑨退出区
    ...;                // ⑩剩余区
}

/**
 * 【Peterson算法】
 * 说明：主动谦让。
 * 问题：不遵循让权等待。
 */
bool flag[2];
flag[0] = false;
flag[1] = false;
int turn = 0;

// P0
flag[0] = true;                 // ①进入区，表明自己意愿
turn = 1                        // ②进入区，主动避让
while(flag[1] && 1 == turn) {   // ③进入区，其它进程是否想进入且当前礼让中
    ...;                        // ④临界区
    flag[0] = false;            // ⑤退出区
    ...;                        // ⑥剩余区
}

// P1
flag[1] = true;                 // ⑦进入区，表明自己意愿
turn = 0                        // ⑧进入区，主动避让
while(flag[0] && 0 == turn) {   // ⑨进入区，其它进程是否想进入且当前礼让中
    ...;                        // ⑩临界区
    flag[1] = false;            // ⑪退出区
    ...;                        // ⑫剩余区
}

互斥硬件实现方法

信号量机制

软件和硬件互斥方法存在问题：
1.检查和上锁操作无法一气呵成。
2.无法实现让权等待。

原语：由关中断/开中断实现，一旦开始执行，就不能被中断的若干条指令。

PV操作：一对原语，wait(S)和signal(S)简称P(S)、V(S)，是一对低级进程通信原语。

整型信号量：

int S = 1;          // 初始化整型信号量

void wait(int S) {
    while(S <= 0);  // 资源不够则等待资源
    S--;
}

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

// P0进程
wait(S);        // 申请资源S
...;            // 使用资源S
signal(S);      // 释放资源S

记录型信号量：为解决整型信号量的忙等待问题，即不满足让权等待问题。

typedef struct {
    int value;          // 可用资源数量
    struct process *L;  // 等待进程队列
} semaphore;

void wait(semaphore S) {
    S.value--;
    if(S < 0) block(S.L);           // RUNNING --> BLOCKED
}

void signal(semaphore S) {
    S.value++;
    if(S.value <= 0) wakeup(S.L)    // BLOCKED --> READY
}

// P0进程
wait(S);        // 申请资源S
...;            // 使用资源S
signal(S);      // 释放资源S

例

例1：有$p$个进程并发，每个进程需要$r$（$1≤r≤R$）个资源，问至少有多少资源不会发生死锁。

每个进程差$1$个资源可以运行，再补充一台使至少有$1$台不会无限等待则有：

$R=(r-1)p + 1$

例2：有可用资源$R$，每个进程需要使用$r$（$1≤r≤R$）个资源，问至多有几个线程$p$不会发生死锁。

$p=\dfrac{R-1}{r-1}$

例3：有$p$个程序共享同一程序段，每次最多允许$R$个进程进入该程序短，问信号量$S$取值范围

$S∈[R-p,R]$

管程

用于解决信号量机制编程复杂的问题，包含共享数据结构、数据结构初始化语句、一组用来访问数据结构的过程。

• 外部进程/线程只能通过管程提供特定入口才能访问共享数据
• 每次仅允许一个进程在管程内执行某个内部过程

进程调度

调度

挂起：暂时被淘汰出内存的进程。

调度算法准则：面向用户准则（周转时间短、响应时间快、截止时间保证、优先权准则）、面向系统准则（吞吐量高、处理机利用率高、各资源的平衡利用）

进程调度时机：主动放弃（异常、IO操作）、被动放弃（时间片耗尽、高优先进程进入就绪队列）

进程调度方式：非抢占式调度算法（非抢占式轮换调度算法、非抢占式优先调度算法）、抢占式调度算法（基于时钟中断的抢占式优先权调度算法、立即抢占的优先级调度算法）

非剥夺调度方式（只允许主动放弃）、剥夺调度方式（抢占式）

调度算法性能指标

$\textnormal{\footnotesize 周转时间} = \textnormal{\footnotesize 作业完成时间} - \textnormal{\footnotesize 作业提交时间}$

$\textnormal{\footnotesize 平均周转时间} = \dfrac{\textnormal{\footnotesize 各作业周转时间之和}}{\textnormal{\footnotesize 作业数}}$

$\textnormal{\footnotesize 带权周转时间} = \dfrac{\textnormal{\footnotesize 作业周转时间}}{\textnormal{\footnotesize 作业实际运行时间}}$

$\textnormal{\footnotesize 平均带权周转时间} = \dfrac{\textnormal{\footnotesize 各作业带权周转时间之和}}{\textnormal{\footnotesize 作业数}}$

$\textnormal{\footnotesize 等待时间} = \textnormal{\footnotesize 作业处于等待处理机状态时间之和}$

$\textnormal{\footnotesize 响应时间} = \textnormal{\footnotesize 从用户提交请求到首次产生响应所用的时间}$

调度层次

作业调度工作：检查资源要求、分配内存调入作业、进程载入就绪队列。

调度算法

死锁

产生原因：竞争资源、请求和释放资源的顺序不当

产生必要条件：互斥访问、请求和保持（等待）、不可抢占、环路等待

死锁的处理

• 预防死锁：破坏产生的必要条件
• 避免死锁：安全状态、银行家算法
• 检测和解除
  • 检测：依次消除资源分配图（进程结点、资源结点、请求边、分配边）中与不阻塞进程相连的边，直到无边可消。
  • 解除：资源剥夺法、撤销进程法、进程回退法

内存

硬件结构：寄存器、高速缓存、内存

内存保护：上下限寄存器、限长寄存器（届地址寄存器、重定位寄存器）

覆盖技术：按照逻辑，让不能同时被访问的程序段共享同一个覆盖区。

交换技术：内存紧张时，将内存中某些进程暂时换出到外存交换区（PCB则常驻内存）。

内存碎片：不能被使用的内存区域。

程序装入方式

连续内存分配

动态分区分配算法：需要能描述空闲分区和已分配分区的数据结构，常用数据结构有空闲分区表、空闲链表。若分区回收后与前后分区均为空闲分区，则应将其合并存储。

非连续内存分配

分页存储管理

基本思想：非连续分配，把进程分页，各个页面离散的放到各个内存块中。

物理层面：将内存空间分为多个大小相等（太大可能产生过大的内部碎片）的分区，每个分区就是一个页框（页帧、内存块、物理块），每个页框有一个编号即页框号（页帧号、内存块号、物理块号），页框号从0开始。

逻辑层面：用户进程的地址空间也分为与页框大小相等的一个个区域称为页（页面），每个页有一个页号，页号从0开始。

页表：存储了逻辑页与物理块的对应关系(页号, 块号)。故CPU每次读取数据都需要$2$次访存，第一次访问内存中的页表，第二次通过查询页表获得的物理地址访问内存获得所需数据。

页表长度：页表有几个页表项（多少行）。

页表项长度：页表项占存储空间大小（一行大小）。

页面长度：页面占存储空间大小。

快表：当页表项缓存于寄存器时，即为快表。此时每次读取数据仅需$1$次访存。

多级页表：各级页表大小不能超过一个页面大小，使用两级页表（(一级页号, 二级页号, 页内偏移量)、(页号, 块号)）需要$3$次访存，$N$级页表需要$N+1$次访存。

地址转换

• $\textnormal{\footnotesize 逻辑地址} = \textnormal{\footnotesize 页号} × \textnormal{\footnotesize 页面长度} + \textnormal{\footnotesize 页面偏移量}$
  • $\textnormal{\footnotesize 页号} = \left\lfloor{\dfrac{\textnormal{\footnotesize 逻辑地址}}{\textnormal{\footnotesize 页面长度}}}\right\rfloor$，并检查页号是否合法
  • $\textnormal{\footnotesize 页内偏移量} = \textnormal{\footnotesize 逻辑地址} {\rm \ mod \ } \textnormal{\footnotesize 页面长度}$
• 查询页表：$\textnormal{\footnotesize 页号} \xrightarrow[]{(\textnormal{\footnotesize 页号}, \textnormal{\footnotesize 块号})} \textnormal{\footnotesize 块号}$
• $\textnormal{\footnotesize 起始地址} = \textnormal{\footnotesize 块号} × \textnormal{\footnotesize 块大小}$
• $\textnormal{\footnotesize 物理地址} = \textnormal{\footnotesize 起始地址} + \textnormal{\footnotesize 页内偏移量}$

例：页面长度=1KB = 0x400，页表如下，问逻辑地址0A1F(H)对应的物理地址

• 0x0A1F = 2 × 0x400 + 0x21F，即页号为2（块号为3），页面偏移量为0x21F。
• 物理地址为3 × 0x400 + 0x21F = 0xE1F

分段存储管理

段表：存储了逻辑段与物理地址的对应关系(段号（隐含）, 段长, 基址)。

段页式存储管理

先将程序分为若干段，再将每段分为若干页。逻辑地址结构为用户提供(段号, 段内地址)，实际存储(段号, 页号, 页内偏移量)。段页式段表为(段号（隐含）, 页表长度, 页表存放地址)与分段存储管理中的段表不同。段页式访问一个逻辑地址需要访存$3$次（段表->页表->物理地址），若快表命中则仅需$1$次访存。

虚拟内存

从逻辑上扩充内存容量，程序不需要全部装入内存即可允许，运行时根据需要动态调入数据，内存不够时换出一部分数据。

虚拟内存的最大容量：由系统的地址结构和外存空间大小决定。

虚拟内存组成：主存、辅存、管理单元、管理软件。

调入策略：预调页策略、请求调页策略

局部性原理：

• 时间局部性（执行过的指令可能再次执行，访问过的数据可能再次被访问）
• 空间局部性（访问过的存储单元其附件的单元也可能被访问）

虚拟内存特征：

• 多次性（一个作业分成多次调入内存）
• 对换性（将暂时不使用的进程调出到外存）
• 虚拟性（逻辑上扩充内存容量）

实现技术：

• 虚拟内存实现
  • 请求分页存储管理
    • 页表有所改变为(页号, 块号, 状态位, 访问字段, 修改位, 外存地址)
    • 缺页中断为内中断中的故障，属于可以被系统修复的异常
    • 一条执行在执行过程中可能产生多次缺页中断
  • 请求分段存储管理
  • 请求段页式存储管理
• 请求调页功能：访问信息不存在时
• 页面置换功能：内存空间不够时

页面置换算法

CLOCK/NRU算法：采用循环队列构建页面队列，记录(访问位)，访问后若为1则置为0，最多2轮即可找到要淘汰的页。

改进的CLOCK/NRU算法：增加了置换代价因素，记录(访问位, 修改位)，最多进行4轮扫描即可找到要淘汰的页。

• 第1轮：扫描替换第一个(0,0)
• 第1轮：扫描替换第一个(0,1)，所有扫描过的访问位=0
• 第3轮：扫描替换第一个(0,0)
• 第4轮：扫描替换第一个(0,1)

页面分配策略

驻留集：请求分页存储管理中给进程分配的物理块的集合。

工作集：某段时间间隔内，进程实际访问的页面的集合。

固定分配/可变分配：运行期间驻留集大小是否可变。

局部替换/全局替换：缺页时，是否只能换出进程自己的页面。

抖动：刚换入的页面马上又要换出，主要原因是进程频繁访问的页面数目高于可用物理块数，即分配给进程的物理块不够。

• 固定分配局部替换
• 可变分配全局替换：发生缺页就会获得新物理块；内存耗尽时，选择一个未锁定页面调出，该页所属进程缺页率会增加。
• 可变分配局部替换：频繁缺页则适当增加物理块；反之则适当减少物理块。

设备

设备IO方式：轮询、中断、直接访存、通道控制

作业IO方式：联机、脱机、假脱机

缓冲区管理：

• 单缓冲
• 双缓冲
• 循环缓冲
• 缓冲池

层次结构：

• 用户层：库函数、假脱机技术（SPOOLing技术）
• 设备独立性软件：系统调用、IO调度、设备保护、设备分配与回收、缓冲区管理
• 设备驱动程序
• 中断处理程序
• 硬件

设备分类

按设备使用分类：存储设备、输入输出设备

按设备速率分类：低速、中速、高速

按设备交换单位分类：块设备（传输快，可寻址）、字符设备（传输慢，不可寻址，常采用中断驱动方式）

按设备共享属性分类：独占设备、共享设备、虚拟设备

设备控制器

功能：接受和识别CPU发出的命令、向CPU报告设备状态、数据交换、地址识别

组成：CPU与控制器接口、IO逻辑、控制器与设备之间的接口

寄存器编址方式：内存映射I/O、寄存器独立编址

控制方式

设备分配

相关数据结构：设备控制表（DCT）、控制器控制表（COCT）、通道控制表（CHCT）、系统涉笔表（SDT）。

分配时考虑因素：设备固有属性（独占性、共享性、可虚拟性）、设备分配算法、分配中安全性。

设备分配步骤：用户编程时使用逻辑设备名，OS通过物理设备名映射表（LUT）实现从逻辑设备名到物理设备名的映射。

SPOOLing：提高IO速度、独占设备改造为共享设备、实现了虚拟设备功能。是一种以空间换时间的技术。

磁盘

磁盘

磁盘读写耗时

• 寻道时间：启动磁臂、移动磁头
• 延迟时间：目标扇区转到磁头下面
• 传输时间：读/写数据花费的时间

磁盘调度算法

数据交付方式

• 数据交付：交付磁盘高速缓存中的数据
• 指针交付：交付磁盘高速缓存的一块区域的指针

减少延迟方法

• 提前读
• 延迟写
• 优化物理分布
  • 交替编号：编号相邻的扇区物理上不相邻
  • 错位命名：相邻盘面的扇区编号错位
  • 地址结构设计：使用(柱面号, 盘面号, 扇区号)结构以减少移动磁头次数
• 虚拟盘

磁盘初始化

• 初始化
  • 低级格式化：划分扇区
  • 磁盘分区
  • 逻辑格式化：建立文件系统
• 引导块：存放自举程序
• 坏块管理
  • 逻辑格式化时将坏块标记出来
  • 维护一个坏块链，管理备用扇区

磁盘分区

• 主分区1~4预留
• 扩展分区从5开始

磁盘容错

磁盘冗余阵列

磁盘容错技术

• STF-Ⅰ：双份目录双份文件、写后读校验
• STF-Ⅱ：磁盘镜像、磁盘双工
• STF-Ⅲ：双机热备、双机互备、公用磁盘

文件

文件系统：由文件管理有关软件、被管理文件、实施管理所需的数据结构等组成。

文件数据：

• 数据项：字母或数字等基本数据单位
• 文件属性：文件类型、长度、位置、建立时间等附加信息
• 记录 = 数据项的集合
• 文件 = 记录 + 文件属性

文件共享方式：

• 硬链接：基于有向无循环图，用户目录项指向同一个索引结点
• 软链接/符号链接：Link型文件记录共享文件所在位置

文件保护方式：

• 口令保护
• 加密保护
• 访问控制：用访问控制表ACL记录各用户/组对文件的权限

文件系统层次结构：

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

文件存储空间管理

主要解决如何为新文件分配存储空间的问题。

文件存储空间划分：逻辑卷/文件卷、目录区（文件目录、空闲表、位示图、超级块）、文件区

文件逻辑结构

有结构文件由记录组成，又称记录式文件，记录分为定长记录和可变长记录。

• 顺序文件
  • 串结构：记录间顺序与关键字无关
  • 顺序结构：纪录间顺序按关键字顺序排列
    • 定长记录：可以实现随机存取，可以快速检索
    • 可变长记录：无法实现随机存取
• 索引文件：为了实现可变长记录的快速检索
  • 建立索引表(索引号, 长度, 指针)，索引表本身是定长记录的顺序文件
  • 若索引表按关键字顺序排列则可支持快速检索
• 索引顺序文件：将记录分组，每组对应一个索引表项

文件目录结构

文件目录：一个文件对应一个FCB、一个FCB就是一个目录项，多个FCB组成文件目录。

索引结点：除文件名之外所有信息都放到索引节点中，每个文件对应一个索引结点。

目录查询方法：线性检索、Hash方法

目录结构：

• 单极：不允许文件重名
• 两级：不同用户文件可以重名，但不能对文件进行分类
• 多级（树形）：不方便文件共享，包含相对路径和绝对路径
• 无环图：共享结点设置共享计数器，计数器为0时才删除结点

文件物理结构

包括：顺序结构、链式结构、索引结构。