操作系统学习笔记

1. 操作系统概述

1.1 操作系统概念

控制和管理整个计算机系统的硬件和软件资源，合理组织调度计算机的工作和资源。
- 处理机管理、存储器管理、文件管理、设备管理
提供给用户其它软件方便的接口与环境
- 命令接口：用户直接使用
  - 联机命令接口：终端命令直接交互
  - 脱机命令接口：将所有需要执行的命令放入文件中批量执行
- 程序接口：系统调用，用户通过程序间接使用
- GUI图形用户界面
是计算机系统中最基本的系统软件

操作系统将CPU抽象为进程、磁盘抽象为文件、内存抽象为地址空间，提供给应用程序使用

操作系统层次架构：硬件之上、应用程序之下，处于中间层

操作系统主要关注Kernel内核，而非暴露在外部的Shell。

CPU管理、内存管理、文件系统管理、中断处理与IO设备驱动

1.2 操作系统特征

OS Kernel 特征：并发与共享互为存在条件、没有并发与共享则谈不上虚拟与异步

并发：两个或多个事件在同一时间间隔内发生。宏观上同时发生，微观上交替发生。
- 区分概念 -> 并行：两个或多个事件在同一时刻同时发生。
- 一个单核CPU同一时刻只能执行一个程序 -> 并发
- 尽管目前存在多核CPU，但仍然需要并发性
共享：系统中的资源可供内存中多个并发执行的进程使用
- 互斥共享：一个时间段内仅允许一个进程访问该资源
- 同时共享：一个时间段内多个进程“同时”访问该资源（宏观同时、微观交替）
虚拟：利用多道程序设计技术，让每个用户都觉得有一个计算机专门为他服务
- 空分复用
- 时分复用
异步：程序的执行不是一贯到底，而是走走停停，以不可预知的速度向前推进。但只要运行环境相同，OS需要保证最终程序运行的结果也相同。

1.3 操作系统运行机制

两种指令：

特权指令：如内存清理指令，不允许用户程序使用
非特权指令：如普通的运算指令

两种处理器状态：用程序状态寄存器PSW实现

用户态：此时CPU只能执行非特权指令
核心态：两种指令均可执行

两种程序：

内核程序：操作系统的内核程序是系统管理者，运行在核心态
应用程序：普通应用程序运行在用户态

1.4 操作系统内核

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

时钟管理：实现计算机计时功能。所有管理工作需要基于计时实现。
中断处理：负责实现中断机制
原语：是一种特殊程序，是最接近硬件的部分，这种程序的运行具有原子性。
为系统资源进行管理的功能：进程管理、存储器管理、设备管理
- 有的系统将此归于操作系统内核，有的系统则不这样做

1.5 操作系统体系结构

大内核：将操作系统的主要功能模块都作为系统内核，运行在内核态

优点：高性能
缺点：内核代码庞大、结构混乱、难以维护

微内核：只将最基本功能留在内核

优点：内核功能少、结构清晰、易于维护
缺点：需要频繁在核心态与用户态之间切换，性能低

1.6 中断和异常

中断机制：使得多道程序并发执行，避免了串行执行的低效率。

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

发生了中断则意味着需要操作系统介入开展管理工作。由于操作系统的管理工作需要使用特权指令，所以CPU需要从用户态切换为内核态，使操作系统获得计算机的控制权。

用户态 -> 核心态：中断实现（唯一途径）
核心态 -> 用户态：执行一个特权指令，通过PSW设置

中断的分类：

内中断：也称为异常、例外、陷入
- 自愿中断：即指令中断
- 强迫中断：硬件故障与软件中断
外中断：外设请求、人工干预，如IO操作完成后发出的中断信号

处理过程如下：
1. 执行完每个指令后，CPU需检查当前是否有外部中断信号
2. 如果检测到，则需要保护被中断进程的CPU环境（通过PC、PSW、各种寄存器等）
3. 根据中断信号类型转入相应的中断处理程序
4. 恢复原进程的CPU环境并退出中断，返回原进程继续向下执行

1.7 系统调用

操作系统需要向上提供一些简单易用的服务。包括命令接口与程序接口。

其中，程序接口由一组系统调用组成。

系统调用可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。
用户进程想要操纵共享资源，只能通过系统调用向操作系统发出请求，由操作系统对各个请求协调管理。这样可以保证系统的稳定性与安全性，防止用户进行非法操作。

系统调用分类：在核心态下完成

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

系统调用过程：

用户态传递系统调用参数
用户态执行陷入指令：唯一一个只能在用户态执行、不能在内核态执行的指令
- 陷入指令实在用户态执行的，执行陷入指令后立即引发一个内中断，CPU进入内核态
内核态调用相应服务程序
返回用户程序

2. 进程

2.1 进程概述

程序段、数据段、PCB三部分组成了进程实体

2.1.1 进程定义

进程是程序的一次执行过程
进程是一个程序及其数据在处理机上顺序执行时发生的活动
进程是具有独立功能的程序在数据集合上运行的过程，是系统进行资源分配与调度的一个独立单位
进程是进程实体的运行过程

2.1.2 进程组成

程序段：存放程序代码

数据段：存放程序运行时使用、产生的运算数据。如全局变量、局部变量等

PCB：操作系统通过PCB管理进程，其中存储着管理所需要的信息

进程描述信息：进程标识符PID、用户标识符UID
进程控制和管理信息：进程当前状态、进程优先级
资源分配清单：程序段指针、数据段指针、键盘、鼠标
处理机相关信息：各种寄存器值 -> 便于进程切换

2.1.3 进程组织

连接方式：
- 按照进程状态将PCB分为多个队列
- 操作系统持有指向各个队列的指针
索引方式：
- 根据进程状态的不同，建立多张索引表
- 操作系统持有指向各个索引表的指针

2.1.4 进程特征

动态性：进程是程序的一次执行过程，动态地产生、变化和消亡
并发性：内存中有多个进程实体，可并发执行
独立性：进程是能独立运行、独立获得资源、独立接收调度的基本单位
异步性：各进程按各自独立、不可预知的速度前进，OS需提供进程同步机制解决异步问题
结构性：每个进程都配置一个PCB。由程序段、数据段和PCB组成

2.1.5 进程状态与转换

三种基本状态：Running、Ready、Waiting/Blocked

Running：占有CPU，并在CPU上运行
- 单核下每一时刻只有一个进程处于运行态，多核下可以有多个
Ready：已具备运行条件，但没有空闲CPU，暂时不能运行
Waiting/Blocked：因等待某一事件暂时不能运行

另外两种状态：New、Terminated

New：进程正在被创建，操作系统为其分配资源，初始化PCB
Terminated：进程正在从系统重撤销，回收资源与撤销PCB

转换：

2.1.6 进程控制

进程控制：对系统中所有进程实施有效的管理。它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

创建进程：初始化PCB，分配系统资源
创建态 -> 就绪态：修改PCB内容，将PCB添加到就绪队列
就绪态 -> 运行态：恢复进程运行环境，修改PCB内容和相应队列
运行态 -> 阻塞态：保存进程运行环境，修改PCB内容和相应队列
阻塞态 -> 就绪态：需要修改PCB内容和相应队列。如果等待的是资源，还需要为进程分配系统资源。
运行态 -> 就绪态：保存进程运行环境，修改PCB内容和相应队列
运行态 -> 终止态：回收进程拥有的资源，撤销PCB

实现进程控制：

使用原语实现进程控制。原语的特点是在执行期间不允许中断，即原子性操作。

原语采用“关中断指令”和“开中断指令”实现

更新PCB中的信息
- 修改进程状态标志
- 将当前进程的运行环境保存到PCB
- 从PCB中恢复该进程的运行环境
将PCB插入到合适的队列
分配/回收资源

2.1.7 进程通信

进程通信：进程之间的信息交换

各进程拥有的内存地址空间相互独立，为了保证安全，一个进程不能直接访问另一个进程的地址空间。

为了保证进程间的安全通信：

共享存储：操作系统开辟一块共享空间供各个进程共享使用，但进程对共享空间的访问必须是互斥的
- 基于数据结构的共享：限定了数据格式大小，低级通信
- 基于存储区的共享：自由，高级通信
管道通信：用于连接读写进程的一个共享文件，即在内存中开辟一个固定大小的缓冲区
- 只能采用半双工通信，某一时间段内只能实现单向传输，若要实现双向同时通信，则需要设置两个管道
- 各进程需要互斥地访问管道
- 数据以字符流形式写入管道，当管道写满时，写进程的write将被阻塞，等待读进程将数据取走。当数据全部被取走后，管道为空，此时读进程的read将被阻塞
- 如果没有写满，则不允许读；如果没有读空，则不允许写
- 数据一旦被读出，就从管道中被抛弃，这意味着读进程最多只有一个
消息传递：以格式化消息为单位进行数据交换
- 直接通信：消息直接挂到接收进程的消息缓冲队列上
- 间接通信：消息需要先发到中间实体信箱中

2.1.8 线程概念和多线程模型

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

引入线程之后，不仅进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程也可以并发处理各种任务。

资源分配与调度
- 无线程时：进程是资源分配、调度的基本单位
- 引入线程后：进程是资源分配的基本单位，线程是调度的基本单位
并发性
- 无线程时：只能进程间并发
- 引入线程后：线程之间也可以并发，提升了并发度
系统开销
- 无线程时：切换进程运行环境的开销很大
- 引入线程后：同一进程内的线程切换不需要切换进程环境，系统开销很小

线程的实现方式：

用户级线程：由应用程序通过线程库实现
- 所有线程管理工作都由应用程序负责
- 用户级线程中，线程切换在用户态下即可完成，无需操作系统干预
- 在用户看来，存在多个线程，但操作系统内核并意识不到县城的存在。即：对用户不透明，对操作系统透明
内核级线程：由操作系统内核完成对线程的管理工作

多线程模型：内核级线程才是处理机CPU核分配的单位

多对一模型：多个用户级线程映射到一个内核级线程
- 优点：在用户空间即可完成线程切换，开销小，效率高
- 缺点：如果一个用户级离县城阻塞，会导致整个进程均被阻塞
一对一模型：一个用户级线程映射到一个内核级线程
- 优点：并发能力强，不会出现单个线程阻塞造成进程阻塞的问题
- 缺点：一个用户进程占用多个内核级线程，线程切换操作由操作系统内核完成，需要切换到核心态，管理成本高，开销大
多对多模型：
- 克服了并发度低的缺点、克服了一个用户进程占用过多内核级线程开销大的缺点

2.2 调度算法

2.2.1 调度概念

往往进程数量多于CPU数量。需要按照一定算法从就绪队列中选择一个进程并将CPU资源分配给它。

2.2.2 调度算法评价指标

CPU利用率：忙碌时间 / 总时间

系统吞吐量：完成作业的数量 / 总花费时间

周转时间：从作业被提交到系统开始，到作业完成为止的时间间隔

包含：
1. 作业在外存后备队列上等待作业调度的时间
2. 进程在就绪队列上等待进程调度的时间
3. 进程在CPU上执行的时间
4. 进程等待I/O操作完成的时间

带权周转时间：作业周转时间 / 作业实际运行的时间 >= 1

等待时间：进程/作业处于等待处理机状态时间之和

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

2.2.3 先来先服务FCFS

从公平角度出发，按照作业/进程到达的先后顺序进行服务

用于作业调度时，考虑哪个作业先到达后备队列
用于进程调度时，考虑哪个进程先到达就绪队列

非抢占式算法

优点：公平、算法实现简单，不会导致饥饿

缺点：有利于长作业，不利于短作业。短作业排在长作业之后需要等待较长时间。

2.2.4 短作业优先SJF

追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间

即最短的作业/进程优先得到服务，每次调度时选择当前已到达且运行时间最短的作业/进程。为非抢占式的。

优点：“最短的”平均等待时间、平均周转时间

缺点：不公平，对短作业有利，对长作业不利，可能产生饥饿现象

抢占式短作业优先版本SRTN

最短剩余时间优先算法：如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程就需要重新回到就绪队列。

2.2.5 高响应比优先算法HRRN

综合考虑作业/进程的等待时间与要求服务的时间

响应比：等待时间 + 要求服务时间 / 要求服务时间

以上算法均没有考虑响应时间，不区分任务的紧急程度，对用户而言交互性很差。

2.2.6 时间片轮转 Round-Robin

公平地轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

按照各个进程到达就绪队列的顺序，轮流让每个进程执行一个时间片。如进程未在一个时间片内执行完，则剥夺CPU，将进程重新放到就绪队列队尾重新排队。

适用于进程调度，只要作业放入内存并建立了进程后才分配时间片。

属于抢占式算法，由时钟发出中断通知CPU时间片已到。

若时间片设置过大，则时间片轮转调度算法可能退化为先来先服务调度算法，会增大进程响应时间。
若时间片设置过小，则导致进程切换过于频繁，使实际进程执行时间比例减少

优点：公平、响应快、适用于分时操作系统、无饥饿

缺点：高频切换进程带来开销、不区分任务紧急程度

2.2.7 优先级调度算法

需要根据任务的紧急程度来决定处理顺序

调度时选择优先级最高的作业/进程

优点：灵活地调整对各种作业/进程的偏好程度

缺点：可能导致饥饿

2.2.8 多级反馈队列调度算法

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
新进程到达时先进入第1级队列，按照FCFS原则排队等待分配时间片。
- 若用完时间片进程还未结束，则进程进入下一级队列的队尾
- 若此时已经在最下级队列，则重新放到该队列队尾
只有第k级队列为空时，才会为k+1级对头的进程分配时间片

是一种抢占式算法

优点：

对各类型进程相对公平
每个新到达的进程都可以很快得到响应
短进程只用较少的时间就可完成
可灵活地调整各类进程的偏好程度

2.3 进程同步与互斥

同步：两个或多个进程协调工作次序

互斥：一个时间段只允许一个进程访问该资源，互斥访问临界资源

进入区、临界区、退出区、剩余区
空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

2.3.1 进程互斥实现

单标志法：

缺点：Starvation：If P0 never enters CS, P1 starve
双标志先检查法

缺点：存在并发问题，违反忙则等待原则。原因是while循环的检查与上锁两个步骤不具有原子性，在这之间可能出现线程切换。

双标志后检查法：调换了检查与上锁步骤

缺点：存在并发问题，造成死锁，导致线程均无法进入临界区。
Perterson算法

孔融让梨思想：先表达自己的意愿，再主动请对方先使用临界区