一、引论

1.1、操作系统的目标

方便性：

• 通过OS命令操纵计算机，方便用户

有效性：

• 提高系统资源的利用率
• 提高系统吞吐量

可扩充性：

• OS必须具有很好的可扩充性
• 与OS的结构有紧密的联系

开放性：

• 遵循世界标准规范。特别是开放系统互连OSI

1.2、操作系统的作用

用户与计算机硬件系统之间的接口：

• 命令方式（UNIX、DOS命令）
• 系统调用方式（API）
• GUI方式（Windows、LINUX）

计算机系统资源的管理者：

• 处理机管理、存储器管理、I/O设备管理、文件管理

实现对计算机资源的抽象：

• 裸机：无软件的计算机系统
• 虚拟机：覆盖了软件的机器，向用户提供一个对软件操作的抽象模型

1.3、操作系统的发展过程

• 无操作系统的计算机系统（人工操作方式、脱机I/O方式）
• 单道批处理系统
• 多道批处理系统
• 分时系统
• 实时系统
• 微机操作系统
• 嵌入式操作系统
• 网络操作系统
• 分布式操作系统

1.4、操作系统的基本特征

并发（Concurrence）

• 并行性：两个或多个事件在同一时刻发生
• 并发性：两个或多个事件在同一时间间隔内发生
• 引入进程（任务）：动态、并发

共享（Sharing）

系统中的资源可供内存中多个并发执行的进程共同使用

• 互斥共享方式（临界资源）
• 同时访问方式

虚拟（Virtual）

• 时分复用技术：虚拟处理及、虚拟设备
• 空分复用技术：虚拟存储

异步（Asynchronism）

• 进程的异步性：进程是以人们不可预知的速度向前推进的

1.5、操作系统的运行环境

硬件支持：

• 引导程序：位于固件（定位OS内核并将其加载到内存中）
• 指令：CPU执行
• 事件：硬件中断或软件中断引起
• 执行程序：位于内存
• 程序：位于外存

操作系统内核：

常驻内存，通常与硬件紧密相关

支撑功能：

• 中断处理
• 时钟管理
• 原语操作

• 由若干条指令组成，用于完成一定任务
• 原子操作：要么不做，要么全做，不可分割

资源管理功能：

• 进程管理、存储器管理、设备管理

处理器的双重工作模式：

• 特权指令：如有误用，有可能引起系统崩溃的提示
• 内核态（管态、系统态）：执行包括特权指令在内的一切指令
• 用户态（目态）：不能执行特权指令

• 由硬件提供模式位

• 提供了区分系统正在运行用户代码或内核代码的能力
• 系统调用切换运行模式到内核态，并将调用结果返回给用户

特权指令和非特权指令

特权指令：在内核态下运行的指令

• 不仅能访问用户空间，还能访问系统空间
• 如启动外部设备、设置系统时钟、管终端、切换执行状态、I/O指令。

非特权指令：在用户态下运行的指令

• 应用程序所使用的都是非特权指令
• 防止应用程序的运行异常对系统造成破坏
• 仅能访问用户空间

中断与异常

• 操作系统是终端驱动的，OS总在等待某个事件的发生，事件总是由中断或异常引起的
• 中断（interrupt）：由硬件引起
• 异常/陷阱（trap）：由软件引起

• 出错（如出书为0或无效存储访问）
• 用户程序的特定请求（如执行OS的某个服务）

1.6、操作系统的主要功能

处理机管理功能

• 进程控制：创建进程、撤销（终止）进程、状态转换
• 进程同步：信号量机制
• 进程通信：直接通信、间接通信
• 调度：作业调度、进程调度

存储器管理功能

• 内存分配和回收：内存分配、内存回收
• 内存保护：确保每个用户程序仅在自己的内存空间进行、决不允许用户程序访问操作系统的程序和数据
• 地址映射：逻辑地址转换为物理地址
• 内存扩充（虚拟存储技术）：请求调入功能、置换功能

设备管理功能

• 缓冲管理：缓冲区机制
• 设备分配
• 设备处理：设备驱动程序

主要任务：完成I/O请求、提高CPU和I/O设备的使用率

文件管理功能

• 文件存储空间的管理
• 目录管理：按名存取
• 文件的读/写管理和保护：文件的读/写管理、文件保护

操作系统与用户之间的接口

用户接口：

• 联机用户接口：命令方式CLI
• 脱机用户接口
• 图形用户接口GUI

程序接口：

• 系统调用：能完成特定功能的子程序

现代操作系统的新功能

• 系统安全：认证、密码、访问控制、反病毒技术
• 网络功能服务：网络通信、资源管理、应用互操作
• 支持多媒体：接纳控制技术、实时调度、多媒体文件的存储

1.7、操作系统结构设计

简单结构

OS是无结构的，是为数众多的一组过程的集合，内部复杂、混乱。也称整体系统结构。如：MS-DOS，早期的UNIX。

模块化结构

将OS按功能划分成若干个模块、并规定好各模块间的接口，称为“模块-接口法”

优点：

• 提高OS设计的正确性、可理解性和易维护性
• 增强OS的可适应性
• 加速OS的开发过程

大部分现代OS采用可加载的内核模式来设计

• 内核有一组核心组件，提供核心服务
• 其他服务可在内核运行时动态实现（动态链接）
• 每个组件在需要时被加载到内核
• 例子：Linux、Mac OS X、Solaris以及Windows

分层式结构

操作系统划分为若干层，在低层上构建高层

• 高层仅依赖于邻接它的底层
• 底层（0层）为硬件；最高层（N层）为用户层

优点

• 易保证系统的准确性
• 可保证系统的易维护性和可扩展性

缺点

• 系统效率低

例子：THE、Multics

微内核OS结构

基本概念：

• 足够小的内核
• 基于C/S模式
• 应用“机制与策略分离”原理
• 采用面向对象技术

基本功能：进程管理、低级存储器管理、中断和陷入处理

实例：Mach OS、Windows 200/XP

优点：

• 提高了系统的可扩展性
• 增强了系统的可靠性
• 可移植性强
• 提供了对分布式系统的支持
• 融入了面向对象技术

存在的问题：

• 运行效率有所降低
• 主要原因：在完成一次客户对操作系统提出的服务请求时，需要利用消息实现多次交互和进行用户/内核模型与上下文的多次切换

1.8、系统调用

系统调用目的：使应用程序可以通过它间接调用OS内核中的相关过程，取得相应的服务

系统调用概念：

• 应用程序请求OS内核完成某功能时的一种过程调用
• 用户与内核的接口

与一般过程调用的区别：

• 运行在不同的系统状态
• 状态的切换
• 返回问题
• 嵌套调用

系统调用的类型：

• 进程控制类：创建和终止进程、获得和设置进程属性、等待某事件出现的系统调用
• 进程通信类：用于进程之间通信的系统调用
• 文件操纵类：打开和关闭文件、创建和删除文件、读写文件的系统调用
• 设备管理类：申请设备、释放设备、设备I/O重定向、获得和设置设备属性等系统调用
• 信息维护类：获得包括有关系统和文件的时间信息、OS版本、当前用户、空闲内存、磁盘等。

二、进程的描述与控制

2.1前趋图和程序执行

程序顺序执行

• 一个较大的程序通常都由若干个程序段组成
• 程序在执行时，必须按照某种先后次序诸葛执行，仅当前已操作完成后，才能执行后续操作
• 顺序性 ；封闭性；可再现性

前趋图

• 有向无循环图，用于描述进程之间执行的先后顺序
• 结点表示进程或程序段，有向边表示前趋关系

程序并发执行

• 采用多道程序技术，将多个程序同时装入内存，使之并发运行

特征：间断性、失去封闭性、不可再现性

间断性：

• 并发程序之间相互制约
• 执行——暂停执行——执行

失去封闭性：

• 多个程序共享全机资源
• 执行状态受外界因素影响

不可再现性：

• 程序经过多次执行后，虽然其执行时的环境和初始条件都相同，但得到的结果却各不相同

2.2进程的描述

进程的定义

• 一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
• 程序段、相关的数据段和PCB这3部分构成进程实体，一般简称为进程

进程控制块（process control block,PCB）

• 是进程的一部分，是操作系统中最重要的记录型数据结构，是进程存在的唯一标志，常驻内存

PCB的作用：

• 作为独立运行单位的标志
• 能实现间断性运行方式
• 提供进程管理所需要的信息
• 提供进程调度所需要的信息
• 实现与其他进程的同步与通信

PCB的信息：

• 进程标识符
• 处理及状态
• 进程调度信息
• 进程控制信息

PCB的组织方式：

• 线性方式
• 链接方式
• 索引方式

进程的特征

• 动态性（最基本的特征）：生命期
• 并发性：一段时间内同时运行
• 独立性：进程实体是一个能独立运行的基本单位、是系统中独立获得资源和独立调度的基本单位
• 异步性：按各自独立的、不可预知的速度向前推进

进程的状态及转换

就绪态：

• 一个较大的程序通常都由若干个程序段组成
• 程序在执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后续操作

执行状态：以获得CPU，正在执行的状态

• 单处理机：一个进程处于执行状态
• 多处理及：多个进程处于执行状态

阻塞状态：

• 正在执行的进程由于发生某事件而暂时无法继续执行的状态
• 典型事件：请求I/O、申请缓冲空间
• 根据阻塞原因，设置多个阻塞队列

2.3进程控制

介绍

• 进程管理最基本的功能
• 一般由OS内核中的原语实现
• 包括：进程创建、进程终止、进程阻塞与唤醒、进程挂起与激活

进程创建

• 进程具有层次结构
• 引起进程创建的事件：用户登录、作业调度、提供服务、应用请求
• 进程图：描述进程家族关系的有向树
• 进程创建过程：申请空白PCB、分配所需资源、初始化PCB、插入就绪队列

进程终止

引起进程终止的事件：正常结束、异常结束、外界干预

进程的终止过程：

• 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态
• 若被终止的进程正处于执行状态，应立即终止该进程的执行，并设置调度标志为真，用于指示该进程被终止后应和重新进行调度
• 若该进程还有子孙进程，应将其所有子进程终止
• 将该进程所拥有的所有资源，归还其父进程或系统
• 将被终止进程（PCB）从所在队列中移去

进程的阻塞与唤醒

引起进程阻塞与唤醒的事件：

• 向系统请求共享资源失败
• 等待某操作的完成
• 新数据尚未到达
• 等待新任务的到达

进程阻塞过程：

• 阻塞原语Block（）
• 进程的阻塞是进程自身的一种主动行为
• 具体过程：停止执行、状态由执行改为阻塞、将PCB插入阻塞队列

进程唤醒过程：

• 唤醒原语Wakeup()
• 具体过程：从阻塞队列中移除、状态由阻塞改为就绪、将PCB插入就绪队列
• 必须成对使用Block和Wakeup原语

进程的挂起与激活

Suspend（）原语与Active（）原语

2.4进程通信

概念

• 进程通信是指进程间的信息交换

低级进程通信：进程的同步与互斥

• 效率低
• 通信对用户不透明

高级进程通信

• 使用方便
• 高效地传送大量数据

共享存储器系统

• 基于共享数据结构的通信方式（效率低）
• 基于共享存储区的通信方式（高级）

管道通信

• 管道：用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件
• 管道机制的协调能力：互斥、同步、对方是否存在

消息传递系统

• 直接通信方式
• 间接通信方式（通过邮箱）

C/S模式

• 套接字（Socket）
• 远程过程调用（RPC）和远程方法调用（RMI，Java）

2.5线程的基本概念

引入进程的目的

• 使多个程序并发执行
• 提高资源利用率级系统吞吐量

进程的2个基本属性

• 进程是一个可拥有资源的独立单位
• 进程是一个可独立调度和分派的基本单位

线程是什么

在进程内部增加一类实体，满足以下特性：

• 实体之间可以并发执行
• 实体之间可以共享相同的地址空间

这种实体就是线程（Thread）

优点：

• 一个进程中可以同时存在多个线程
• 各个线程之间可以并发执行
• 各个县城直线可以共享地址空间和文件等资源

缺点：

• 一个线程崩溃，会导致其所属进程的所有线程崩溃

提出线程的目的

• 减少程序在并发执行时所付出的时空开销：创建、撤销、切换
• 使OS具有更好的并发性
• 适用于SMP结构的计算机系统

进程是拥有资源的基本单位（传统进程称为重型进程）

线程作为调度和分派的基本单位（又称为轻型进程）

线程与进程的比较

• 进程是资源分配单位，线程是CPU调度单位
• 进程拥有一个完整的资源平台，而线程只独享指令流的必要资源，如寄存器和栈

• 线程具有就绪、阻塞和运行三种基本状态和状态间的转换关系
• 线程能减少并发执行的时间和空间开销

• 创建时间短
• 终止时间短
• 切换时间短
• 同一进程个各线程间共享内存和文件资源，可不通过内核进行直接通信

线程的实现

实现方式：

• 内核支持线程KST
• 用户级线程ULT
• 组合方式

具体实现：

• 内核支持线程的实现（利用系统调用）
• 用户级现成的实现（借助中间系统）

内核支持线程KST：在内核空间实现

优点：

• 在多处理机系统中，内核可同时调度同一进程的多个线程
• 如果一个线程阻塞了，内核可调度其他线程（同一或其他进程)
• 线程的切换比较快，开销小
• 内核本身可采用多线程技术，提高执行速度和效率

缺点：对用户线程切换，开销较大

用户级线程ULT：在用户空间实现

优点：

• 线程切换不需要转换到内核空间
• 调度算法可以是进程专用的
• 线程的实现与OS平台无关

缺点：

• 系统调用的阻塞问题
• 多线程应用不能利用多处理机进行多重处理的优点

三、处理机调度与死锁

3.1处理机调度概述

处理机调度层次

• 高级调度（长程调度/作业调度）
• 低级调度（短程调度/进程调度）
• 中级调度（中程调度/内存调度）

高级调度

• 调度对象：作业
• 根据某种算法，决定将外存上处于后备队列中的作业调入内存，并为它们创建进程和分配必要资源。然后，将新创建的进程排在就绪队列上等待调度
• 主要用于多道批处理系统中

中级调度

• 将暂不运行的进程，调至外存等待
• 将处于外存上的急需运行的进程，调入内存运行
• 即“对换”功能

低级调度

• 调度对象：进程
• 根据某种调度算法，决定就绪队列中的哪个进程应获得处理机
• 应用在多道批处理、分时和实时OS

处理机调度

• 从就绪队列中挑选下一个占用CPU运行的进程
• 从多个可用CPU中挑选就绪进程可使用的CPU资源

进程调度的任务

• 保存处理及的现场信息
• 按某种算法选取进程
• 把处理器分配给进程

进程调度机制（调度程序分为3部分）

• 排队器：用于将就绪进程插入相应的就绪队列
• 分派器：用于将选定的进程移出就绪队列
• 上下文切换器：进行新旧进程之间的上下文切换

进程调度的方式

分为非抢占方式和抢占方式，现代OS广泛采用抢占方式，抢占方式有以下三个原则

• 优先权原则：允许优先权高的新到进程抢占当前进程的处理机
• 短作业优先原则：短作业可以抢占当前较长作业的处理机
• 时间片原则：各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度

处理机调度算法的目标

共同目标：资源利用率、公平性、平衡性、策略强行执行

批处理系统的目标：平均周转时间短、系统吞吐量高、处理及利用率高

分时系统的目标：响应时间快、均衡性

实时系统的目标：截至时间的保证、可预测性

评价指标

• 周转时间：从作业提交给系统开始，到作业完成为止的这段时间间隔
• 带权周转时间：权值为作业周转时间T与系统为之服务时间TS之比
• 响应时间：从用户通过键盘提交请求开始，直到系统首次显示出处理结果为止的一段时间
• 等待时间：进程在就绪队列中等待调度的所有时间之和

3.2调度算法

介绍

先来先服务（FCFS）

短作业优先调度（SJF）

优先权调度（PR）

时间片轮转调度（RR）

多级队列调度

多级反馈队列调度

基于公平原则的调度算法

先来先服务（FCFS）算法特征

既可用于作业调度，也可用于进程调度

优点：简单

缺点：

• 平均等待时间波动较大，因为段进程可能排在长进程后面
• I/O和CPU资源利用率较低，因为CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也会等待

短作业优先（SJF）调度算法

既可用于作业调度，也可用于进程调度

• 对作业：从后被队列中选择若干个评估运行时间最短的作业
• 对进程：关联到每个进程下次运行的CPU区间长度，调度最短的进程

对进程调度，SJF有两种模式

• 非抢占式SJF
• 抢占式SJF：抢占发生在有比当前进程剩余时间片更短的进程到达时，也成为最短剩余时间优先调度

SJF时最优的（对一组特定的进程而言），它给出了最短的平均等待时间

缺点：

• 需要预知运行时间
• 对长作业不利（饥饿）
• 采用SJF算法时，人机无法实现交互
• 完全未考虑作业的紧迫程度

优先级调度算法（PR）

既可用于作业调度，也可用于进程调度

基于紧迫程度，由外部赋予作业相应的优先级，调度算法根据优先级进行调度：

• 每个进程都有一个优先数，优先数为整数
• 默认：小的优先数具有高优先级
• 目前主流的操作系统调度算法

高响应比优先调度算法是一种优先级调度算法，用于作业调度

优先级调度算法的类型：

• 非抢占式
• 抢占式

优先级类型：

• 静态优先级

• 创建进程时确定优先数（整数），在进程的整个运行期间保持不变
• 简单易行，系统开销小
• 不够精确，可能会出现优先级低的进程长期没有被调度的情况

• 动态优先级

• 创建进程时先赋予其一个优先级，然后随着时间的增加而改变  

优点：

• 实现简单，考虑了进程的紧迫程度
• 灵活，可模拟其他算法

存在问题：饥饿 ；解决方法：老化

高响应比优先调度算法（PR的特例）

• 既考虑了作业的等待时间，又考虑了运行时间
• 优先级=（等待时间+要求服务时间）/要求服务时间
• 响应比=响应时间/要求服务时间
• 如等待时间相同，运行时间越短，类似于SJF
• 如运行时间相同，取决于等待时间，类似于FCFS
• 长作业可随其等待时间的增加而提高，也可得到服务
• 缺点：每次调度之前，都需要计算响应比，增加系统开销

时间片轮转算法（RR）

时间片：分配处理机资源的基本事件单元

算法思路：时间片结束时，按FCFS算法切换到下一个就绪进程

• 专门为分时系统设计，类似于FCFS，但增加了抢占
• 为每个进程分配不超过一个时间片的CPU。时间片用完后，该进程被抢占并插入就绪列表末尾，循环执行
• 假定就绪队列中有n个进程、时间片为q，则每个进程每次得到1/n的、不超过q单位的成块CPU时间，没有任何一个进程的等待时间会超过（n-1）q单位

通常，RR的平均周转时间比SJF长，但响应时间要短一些

进程切换实际：

• 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪列表中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片
• 时间片设置应考虑在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾

在当前进程A的一个时间片用完时,恰好有新进程B到达,则就绪队列的末尾的排序应该是BA。

确定时间片大小的因素：

• 系统对响应时间的要求
• 就绪队列中进程的数目
• 系统的处理能力

操作系统复习篇（中）：https://developer.aliyun.com/article/1446300