第一章 概述

定义

1. 负责管理协调硬件、软件等计算机资源的工作
2. 为上层用户、应用程序提供简单易用的服务
3. 是一种系统软件

功能和目标

1. 资源的管理者
   处理机管理、存储器管理、文件管理、设备管理
2. 向用户提供服务
   命令接口：包含联机命令接口、脱机命令接口
   程序接口：由一组系统调用组成
   GUI用户图形界面
3. 对硬件机器的扩展
   扩充机器

操作系统的特征

1. 并发
2. 共享
   互斥共享方式：如对摄像头、打印机等设备的共享使用
   同时共享方式：如对硬盘资源的共享使用
3. 虚拟
   空分复用技术：spatial，如虚拟存储技术
   时分复用技术：temporal，如虚拟处理机技术
4. 异步：所有进程都是在不同时间片内以不可预知的速度进行的。

操作系统的发展

1. 手工操作阶段
   缺点：人机速度的矛盾
2. 批处理阶段
   单道批处理系统：
   引入了脱机输入输出技术，解决了人机速度矛盾，但资源利用率依然很低
   多道批处理系统：
   操作系统开始出现，多道程序并发执行，资源里利用率高。但不提供人机交互功能。
3. 分时操作系统
   提供了多道批处理系统不具备的人机交互功能
   但不能优先处理紧急任务
4. 实时操作系统
   软实时系统：能偶尔接收违反时间规定/
   硬实时系统：必须在绝对严格的规定时间内完成处理。
   优点：能优先处理紧急任务。
5. 网络操作系统
6. 分布式操作系统
7. 个人计算机操作系统

操作系统的运行机制和体系结构

1. 运行机制
   两种指令：特权指令和非特权指令
   两种处理器状态：核心态、用户态
   两种程序：内核程序、用户程序
2. 操作系统内核
   时钟管理
   中断处理
   原语：是一种特殊的程序，其执行具有原子性。
   对系统资源进行管理的功能：进程管理、存储器管理、设备管理
3. 操作系统的体系结构
   大内核：
   优点：高性能
   缺点：内核代码量庞大，结构混乱难以维护。
   微内核：
   优点：内核功能少，结构清晰，方便维护。
   缺点：需要频繁地在和心态和用户态之间切换、性能低

中断和异常

1. 中断机制的诞生
   为了实现多道程序并发执行而引入的一种技术。
2. 概念与作用
   发生中断就意味着需要操作系统介入开展管理工作，CPU会立即进入核心态。
   中断时CPU从用户态进入核心态的唯一途径。
3. 中断的分类
   内中断：也称异常、例外、陷入
   自愿中断：指令造成的中断。
   强迫中断：由硬件谷中、软件中断造成的
   外中断：
   外设请求，人工干预
4. 内中断的另一种分类方式：
   陷阱、陷入Trap
   故障 Fault
   终止 Abort
5. 外中断的处理过程
   每条指令执行结束后CPU检查是否有外部中断信号。
   若有外部中断信号，则需要保护被中断进程的CPU环境
   根据中断信号类型转入相应的中断处理程序。
   恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

系统调用

1. 概念与作用
   系统调用是操作系统提供给应用程序的接口
   应用程序通过系统调用来请求获得操作系统的服务
   系统调用会使处理器从用户态进入核心态
   分类：设备管理、文件管理、进程控制、进程通信、内存管理
2. 系统调用和库函数的区别
   系统调用是操作系统向上层提供的接口
   有的库函数是对系统调用的进一步封装
   当今编写的应用程序大多是通过高级语言提供的库函数间接进行系统调用
3. 系统调用背后的过程
   传递系统调用参数
   执行陷入指令
   执行系统调用相应服务程序
   返回用户程序

第二章 进程管理

进程与线程

概念

1. 定义
   进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
2. 组成
   PCB：进程的描述信息、进程控制和管理信息、资源分配清单、处理机相关信息
   程序段：存放要执行的程序代码
   数据段：存放程序运行过程中处理的各种数据
3. 组织形式：
   链接方式：按进程状态将PCB分为多个队列
   索引方式：按照进程状态建立几张索引表，各表项指向一个PCB
4. 特征：
   动态性：进程的最基本特征
   并发性：
   独立性：进程是系统进行资源分配、调度的独立单位
   异步性：各进程以不可预知的速度向前推进，可能导致运行结果的不确定性。
   结构性

进程的状态与切换

1. 状态
   运行状态：CPU执行，其他所有状态就绪
   就绪状态：CPU没执行，其他所有资源就绪
   阻塞状态：CPU没执行，其他所有资源未就绪
   创建状态：操作系统为新进程分配资源，创建PCB
   终止状态：操作系统回收进程资源、撤销PCB

2. 进程状态间的转换
   就绪态-->运行态：进程被调度
   运行态-->就绪态：时间片到，或CPU被其他高优先级进程抢占
   运行态-->阻塞态：等待系统资源分配，或等待某事件发生（主动行为）
   阻塞态-->就绪态：资源分配到位，等待的事件发生（被动）
   创建态-->就绪态：系统完成创建进程相关的工作。
   运行态-->终止态：进程运行结束，或运行过程中遇到不可修复的错误。

进程控制

1. 基本概念：
   进程控制就是要实现进程状态的转换
   进程控制用原语实现：
   1> 原语用关/开中断来实现
   2> 原语是一种特殊的程序
   3> 原语的执行必须一气呵成，不可中断
2. 相关原语：
   进程的创建
   进程的终止
   进程的阻塞
   进程的唤醒（阻塞与唤醒要成对出现）
   进程的切换

进程通信

1. 共享存储
   设置一个共享空间
   要互斥地访问共享空间
   两种方式：基于数据结构（低级）、基于存储区共享（高级）

2. 管理通信
   设置一个特殊的共享文件（管道），实质是一个缓冲区
   一个管道只能实现半双工通信
   实现双向同时通信要建立两个管道
   各进程要互斥访问管道
   写满时，不能再写，读空时不能再读
   没写满，不能读；没读空，不能写

3. 消息传递
   传递结构化的消息（消息头/消息体）
   系统提供“发送/接收原语”
   两种方式：
   直接通信方式：消息直接挂到接收方的消息队列里
   间接（信箱）通信方式：消息先发到中间体（信箱）

线程、多线程模型

1. 概念
   可理解为"轻量级进程"
   可增加并发度，减少并发带来的开销

2. 引入线程机制后有什么变化
   资源分配、处理机调度
   并发性
   系统开销减少

3. 线程有哪些重要的属性
   线程是处理机调度的单位，进程是资源分配的单位
   同一进程的各线程共享进程拥有的资源
   同一进程内的线程切换不会导致进程切换

4. 线程的实现方式
   用户级线程：从用户视角看的线程
   内核级线程：从操作系统视角看的线程，内核级线程才是处理机分配的单位
   组合方式：上述两种方式的结合

5. 多线程模型
   多对一模型：
   优点：进程管理开销小效率高
   缺点：一个线程阻塞会导致整个进程都被阻塞
   一对一模型：
   优点：各个线程可分配到多核处理机并行执行，并发度高
   缺点：进程管理开销大
   多对多模型：
   集二者之长

处理机调度

概念

1. 基本 按某种算法选择一个进程，将处理机分配给它

2. 三个层次
   高级调度（作业）：按照某种规则，从后备队列中选择合适的作业将其调入内存，并为创建进程。
   中级调度（内存）：按照某种规则，从挂起队列中选择合适的进程将其数据调回内存。
   低级调度（进程）：按照某种规则，从就绪队列中选择一个进程为其分配处理机。

3. 三层调度的联系、对比
   高级调度：外存-->内存，面向作业，发生频率最低
   中级调度：外存-->内存，面向进程，发生频率中等
   低级调度：内存-->CPU，发生频率最高

4. 补充
   为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为“挂起态”
   其状态模型：再五状态模型的基础上加入“就绪挂起”和“阻塞挂起两种状态”

调度时机，切换与过程、方式

1. 时机
   什么时候需要进程调度
   主动放弃：进程正常终止，运行过程中发生异常而终止，主动阻塞（如等待IO）
   被动放弃：分给进程的时间片用完，有更紧急的事情需要处理，有更高优先级的进程进入就绪队列
   什么时候不能进行调度：
   处理中断的过程中
   进程在操作系统内核程序临界区中
   原子操作过程中（原语）

2. 切换与过程
   狭义的调度和切换的区别
   切换过程：对原来运行进程各种数据的保存；对新的进程各种数据的恢复
   重要结论：进程调度、切换是有代价的，并不是调度约频繁，并发度就越高

3. 方式
   非剥夺调度方式（非抢占式）：只能由当前运行的进程主动放弃CPU
   剥夺调度方式（抢占式）：可由操作系统剥夺当前进程的CPU使用权

调度算法的评价指标

1. CPU利用率
   利用率 = 忙碌的时间/总时间

2. 系统吞吐量
   系统吞吐量 = 总共完成作业数量/完成上述作业所花时间

3. 周转时间
   周转时间 = 作业完成时间-作业提交时间
   平均周转时间 = 各作业周转时间之和 / 作业数
   带权周转时间 = 作业周转时间 / 作业实际运行的时间
   平均带权周转时间 = 各作业带权周转时间之和 / 作业数

4. 等待时间
   进程/作业 等待被服务的时间之和
   平均等待时间即各个进程/作业等待时间的平均值

5. 响应时间
   从用户提交请求到首次产生响应所用的时间

调度算法

名词解释：
FCFS：先来先服务调度
SJF：短作业优先调度，SPF为短进程优先
HRRN：高响应比优先

多级反馈队列调度算法

算法思想：对其他调度算法的折中权衡
算法规则：

1. 设置多级就绪队列，各级队列优先级从高到底，时间片从小到大
2. 新进程到达时先进入第1级队列，按FCS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾
3. 只有第K级队列为空时，才会为k+1级队头的进程分配时间片
   用于作业/进程调度：只用于进程调度

是否可抢占？
抢占式算法，在k级队列的进程运行过程中，若更上级的队列（1~k-1）级中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
优缺点
对各类型进程相对公平（FCFS的优点）；每个新到达的进程都可以很快就得到响应（RR的优点）；短进程只用较少的时间就可以完成；不必实现估计进程的运行时间；可灵活地调整各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程。

进程同步、互斥

1. 进程同步
   并发带来了异步性，有时需要通过进程同步解决这种异步问题。有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。
2. 进程互斥
   定义：对临界资源的访问，需要互斥的访问。即同一时间段内只允许一个进程访问该资源。
   四个部分：

进入区：检查是否可进入临界区，若可进入，需要"上锁"
临界区：访问临界资源的那段代码
退出区：负责解锁
剩余区：其余代码部分。

3. 需要遵守的原则

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

4. 互斥的实现方法
   单标志法
   在进入区只做“检查”，不上锁
   在退出区把临界区的使用权转交给另一个进程（相当于在退出区既给另一进程解锁又给自己上锁）
   主要问题：不遵守“空闲让进”原则

双标志先检查：
在进入区“检查”后上锁，退出区“解锁”
主要问题：不遵循“忙则等待”原则

双标志后检查：
在进入区先“上锁”后“检查”，退出区“解锁”
主要问题：不遵循“空闲让进、有限等待”原则，可能导致“饥饿”

Peterson算法：
在进入区“主动争取--主动谦让--检查对方是否想进、己方是否谦让”
主要问题：不遵循“让权等待”原则，会发生“忙等”

以下为硬件实现方法：
中断屏蔽方法：
使用“开/关中断”指令实现
优点：简单高效
缺点：只适用于单处理机；只适用于操作系统内核进程

TestAndSet（TS/TSL指令）：

old记录是否已被上锁；
再将lock设为true；
检查临界区是否已被上锁（若已上锁，则循环重复前几步）
优点：实现简单；适用于多处理机环境
缺点：不满足“让权等待”

Swap指令（XCHG指令）：
逻辑上同TSL

信号量机制

1. 整形信号量

用一个整数型变量作为信号量，数值表示某种资源数
整形信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作
整形信号量存在的问题：不满足让权等待原则

TIP:P操作即wait操作，V操作即signal操作

2. 记录型信号量

   • S.value表示某种资源数，S.L指向等待该资源的队列
   • P操作中，一定是先S.value--，之后可能需要执行block原语
   • V操作中，一定是先S.value++，之后可能需要执行wakeup原语
   • 注意：要能够自己推断在什么条件下需要执行block和wakeup原语
   • 可以用记录型信号量实现系统资源的申请和释放
   • 可以用记录型信号量实现进程互斥、进程同步

3. 用于实现进程互斥

   • 分析问题，确定临界区
   • 设置互斥信号量，初始值为1
   • 临界区之前对信号量进行P操作
   • 临界区之后对信号量进行V操作

4. 用于实现进程同步

   • 分析问题，找出哪里需要实现“一前一后”的同步关系
   • 设置同步信号量，初始值为0
   • 在“前操作”之后执行V操作
   • 在“后操作”之前执行P操作

5. 用于实现进程的前驱关系

   • 分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
   • 为每一对前驱关系设置同步信号量，初值为0
   • 在每个“前操作”之后执行V操作
   • 在每个“后操作”之前执行P操作

进程同步，互斥的典型问题

1. 生产者-消费者问题
2. 多生产者-多消费者问题
3. 吸烟者问题
4. 读者-写者问题
5. 哲学家进餐问题

管程

1. 引入管程的原因
   解决信号量机制编程麻烦、容易出错的问题

2. 组成

   • 共享数据结构
   • 对数据结构初始化的语句
   • 一组用来访问数据结构的过程

3. 基本特征

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

4. 补充

   1. 各进程必须互斥访问管程的特性是由编译器实现的
   2. 可在管程中设置变量及等待/唤醒操作以解决同步问题

死锁

概念

1. 定义
   各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进

2. 死锁、饥饿、死循环的区别

   • 死锁：至少是两个进程一起死锁，死锁进程处于阻塞态
   • 饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
   • 死循环：可能只有一个进程发生死循环，死循环的进程可上处理机
   • 死锁和饥饿是操作系统要解决的问题，死循环是应用程序要解决的

3. 死锁产生的必要条件

   • 互斥条件：对必须互斥使用的资源的争抢才会导致死锁
   • 不剥夺条件：进程保持的资源只能主动释放，不可以强行剥夺
   • 请求和保持资源：保持着某些资源不放的同时，请求别的资源
   • 循环等待条件：存在一种进程资源的循环等待链，循环等待未必死锁，死锁一定有循环等待。

4. 什么时候发生死锁

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

5. 死锁的处理策略

预防死锁

破坏死锁产生的四个必要条件

1. 破坏互斥条件
   • 将临界资源改造为可共享使用的资源：SPOOLing 技术
   • 缺点：可行性不高，很多时候无法破坏互斥条件
2. 破坏不剥夺条件
   • 方案一：申请的资源得不到满足时，立即释放拥有的所有资源
   • 方案二：申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）
   • 缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致系统开销大；可能导致饥饿
3. 破坏请求和保持条件
   • 运行前分配好所有需要的资源，之后一直保持
   • 缺点：资源利用率低；可能导致饥饿
4. 破坏循环等待条件
   • 给资源编号，必须按编号从小到大的顺序申请资源
   • 缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦

避免死锁

数据结构：

• 长度为m的一维数组Available表示还有多少可用资源

• nxm矩阵Max表示各进程对资源的最大需求数

• nxm矩阵Allocation表示已经给各进程分配了多少资源

• Max-Allocation = Need 矩阵表示各进程最多还需要多少资源

• 用长度为m的一维数组Request表示进程此次申请的各种资源数

银行家算法步骤

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

安全性算法步骤

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

TIP：系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

死锁的检测和解除

1. 检测方法

   数据结构：资源分配图

   • 两种节点：进程节点、资源节点

   • 两种边：进程节点--->资源节点 请求边； 资源节点--->进程节点 分配边

   死锁检测算法：

   • 依次消除与不阻塞进程相连的边，直到无边可消

   • 所谓不阻塞进程是指其申请的资源数还足够的进程

   • 死锁定理：若资源分配图是不可完全简化的，说明发生了死锁

2. 解除方法

   资源剥夺法

   撤销进程法

   进程回退法