MelonCholi 收录于专业课

0001-01-01 约 13636 字预计阅读 28 分钟

操作系统一

操作系统引论

操作系统概念

定义

计算机系统中的一个系统软件，是程序模块的集合

（有效、合理、方便）

目标

方便性
有效性：提高系统资源利用率、提高系统吞吐量
可扩充性
开放性：软硬件兼容

作用

作为用户与硬件之间的接口

计算机系统资源的管理者

硬件资源

软件资源

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

覆盖了一系列软件（I/O 操作命令、文件管理等）后成为虚机器

推动 OS 发展的动力

不断提高计算机资源利用率
方便用户
器件的不断更新与迭代
计算机体系结构的不断发展
不断提出新的应用需求

操作系统的发展过程

人工操作
脱机 / 假脱机（SPOOLing）方式
- 事先将装有用户程序和数据的纸带装入纸带输入机，在一台外围机的控制下，把纸带（卡片）上的数据（程序）输入到磁带上
- 当 CPU 需要这些程序和数据时，再从磁带上高速调入内存。
- 当 CPU 需要输出时，先由 CPU 把数据直接从内存高速地输送到磁带上，然后在另一台外围机的控制下，再将磁带上的结果通过相应的输出设备输出。
单道批处理
- 首先由监督程序将磁带上的第一个作业装入内存，并将运行控制权交给该作业；
- 当该作业处理完成时，又把控制权交还给监督程序，再由监督程序吧磁带上的第二个作业调入内存。
- 计算机系统就这样自动地一个作业紧接着一个作业地进行处理，直至磁带上的所有作业全部完成
- 特点
  - 自动性、顺序性、单道性（内存中仅有一道程序）

多道批处理

(并发)

利用 A 程序的 I/O 操作而暂停执行 CPU 空挡时间，调度 B 程序运行

特点

资源利用率高
系统吞吐量大
平均周转时间长（需要排队依次进行处理）
无交互能力（修改和调试程序不方便）

需要解决的问题

处理机争用问题
内存分配和保护问题
I/O 设备分配问题
文件的组织和管理问题
作业管理问题
用户与系统的接口问题

(多道、单道的比较)

分时系统

人机交互、共享主机
时间片（time slice）：一段很短的时间，用来切割 CPU

关键问题

系统首先必须能提供多个终端，同时给多个用户使用；
其次，当用户在自己的终端上键入命令时，系统应能及时接收、并及时处理该命令，再将结果返回给用户。
- 及时接收
  - 要做到及时接收多个用户键入的命令或数据，只需在系统中配置一个多路卡即可（多路卡实现分时多路复用，使主机能同时接收各用户从终端上输入的数据）
  - 此外，还须为每个终端配置一个缓冲区，用来暂存用户键入的命令（或数据）。
- 及时处理
  - 人-机交互的关键在于，用户键入命令后能对自己的作业机器运行及时地实施控制，或进行修改。因此，各个用户的作业都必须驻留在内存中，并能频繁地获得处理机运行。
    - 作业直接进入内存
    - 采用轮转运行方式

特征

多路性
该特性是指系统允许将多台终端同时连接到一台主机上，并按分时原则为每个用户服务。多路性允许多个用户共享一台计算机，显著地提高了资源利用率，降低了使用费用，从而促进了计算机更广泛的应用。
独立性
该特性是指系统提供了这样的用机环境，即每个用户在各自的终端上进行操作，彼此之间互不干扰，给用户的感觉就像是他一人独占主机进行操作。
及时性
该特性是指用户的请求能在很短时间内获得相应。这一时间间隔是根据人们所能接收的等待时间确定的，通常仅为 1~3 秒钟。
交互性
该特性是指用户可通过终端与系统进行广泛的人机对话。其广泛性表现在：用户可以请求系统提供多方面的服务。

实时系统

（Real time system）

计算机对所接收到的信号做出及时或实时的反应

实时系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

实时任务的类型

周期性实时任务和非周期性实时任务
周期性实时任务：外部设备周期性地发出激励信号给计算机，要求它按规定周期循环执行，以便周期性地控制某外部设备。
非周期性实时任务：无明显周期性，但联系着一个截止时间，或称为最终期限。它可分为：
- 开始截止时间：某任务在某时间以前必须开始执行
- 完成截止时间：某任务在某时间以前必须完成
硬实时任务和软实时任务
硬实时任务：系统必须满足任务对截止时间的要求
软实时任务：也联系着一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大。

分时系统和实时系统的比较

微机操作系统

单用户单任务操作系统

MS-DOS

单用户多任务操作系统

Windows XP

多用户多任务操作系统

UNIX，Linux

操作系统的基本特性

并发

（Concurrence）多时间在同一时间段内发生

多道程序宏观上并发，微观上交替执行

引入进程（Process）

未引入进程系统：计算和 I/O 顺序执行

引入进程系统：为计算程序和 I/O 程序分别建立一个进程，两个进程可并发进行

线程（Threads）

比进程更小的单位

共享

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

互斥共享（音频设备、打印机）
同时访问（磁盘文件、可重入代码）

虚拟

（Virtual）把一个物理实体变为若干个逻辑上的对应物

如

CPU：每个进程的虚处理机
存储器：每个进程占有的地址空间（指令+数据+堆栈）
显示设备：多窗口或虚拟终端
打印设备：将临界资源变成同时访问资源

方法

时分复用
- 虚拟处理机技术、虚拟设备技术
空分复用
- 对存储空间的管理，实际上是内存的分时复用

异步

（Asynchronism）

也称不确定性 / 随机，指进程的执行顺序和执行时间的不确定性

并发执行的程序走走停停，不可预知

操作系统的主要功能

资源管理
- 处理机管理（硬件）
- 存储器管理（硬件）
- 设备管理（硬件）
- 文件管理（软件）
用户接口
- 命令接口
- 图形接口
- 程序接口

处理机管理功能

进程控制：创建、撤销、状态迁移
进程同步：互斥访问临界资源
进程通信：进程合作
调度
- 作业调度：按照算法为作业分配资源
- 进程调度：按照算法先后执行进程

存储器管理功能

内存分配
- 为每道程序分配内存空间
- 提高存储器利用率，减少内存碎片
- 满足正在运行的程序数据动态增长的需要
- 分类
  - 静态分配
  - 动态分配
内存保护
- 每道程序在自己的内存空间内运行，彼此互不干扰
- 不允许用户访问操作系统的程序与数据
- 不允许用户转到非共享的其他用户程序
地址映射
- 能够将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址
内存扩充
- 借助虚拟存储技术，从逻辑上扩充内存容量，使用户所感觉到的内存容量比实际内存容量大得多，以便让更多的用户程序能并发运行。
- 功能
  - 请求调入
  - 置换

设备管理功能

主要任务

完成用户提出的 I/O 请求，并分配 I/O 设备
提高 I/O 利用率

主要内容

缓冲管理
- 在 I/O 设备和 CPU 中之间引入缓冲
设备分配
设备处理
虚拟设备

文件管理功能

文件存储空间的管理
- 为每个文件分配必要的外存空间，提高外存的利用率，进而提高文件系统的存取速度
目录管理
- 为每个文件建立一个目录项，目录项包括文件名、文件属性、文件在磁盘上的物理位置等，并对众多的目录项加以有效的组织，以实现方便的按名存取
文件的读 / 写管理和保护
- 文件的读 / 写管理
  根据用户请求，从外存中读取数据，或将数据写入外存。
- 文件保护
  放置未经核准的用户存取文件；放置冒名顶替存取文件；放置以不正确的方式存取文件

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

用户接口

用户可以通过该接口向作业发出命令以控制作业的运行

命令接口（联机用户接口、脱机用户接口） + 图形用户接口

程序接口

由一组==系统调用==构成，它长得蛮像个库函数（API）

程序接口是为用户程序在执行中访问系统而设置的，是用户程序取得操作系统服务的唯一途径

一些概念

系统调用

系统调用是操作系统提供给应用程序 / 编程人员的唯一接口，它使 CPU 状态从用户态陷入内核态

内核

内核是一组程序模块，作为可信软件来提供支持进程并发执行的基本功能和基本操作

它驻留内核空间，运行于和心态，具有访问硬件设备和内存的全部权限，可以执行特权指令。

它是对操作系统核心功能的抽象概念

处理过程

用户使用系统调用（此时用户程序挂起），导致操作系统功能执行（此时从用户态陷入内核态），并返回用户请求的服务，用户程序恢复现场。

用户态

（user mode）非特权状态、目态

在此状态下，执行的代码被硬件限定，不能进行某些操作

核心态

特权状态、管态

核心态是操作系统内核所运行的模式，运行在该模式的代码，可以无限制地对系统存储、外部设备进行访问。

特权指令

管理硬件和系统安全，只能在核心态执行，用户程序不得含有特权指令。

现代操作系统的新功能

blabla

操作系统结构设计

传统 OS 结构

无结构操作系统

模块化结构 OS

模块独立性
- 内聚性
  - 指模块内部各部分间联系的紧密程度。内聚性越高，模块独立性越强
- 耦合度
  - 模块间相互联系和相互影响的程度。耦合度越低，模块独立性越强

分层式结构 OS

在目标系统 A~n~ 和裸机系统 A~0~ 之间，铺设若干个层次的软件 A~1~、A~2~、A~3~、…、A~n-1~，使 A~n~ 通过 A~n-1~、A~n-2~、…、A~2~、A~1~ 层，最终能在 A~0~ 上运行。

自底向上的分层设计的基本原则是每一步设计都是建立在可靠的基础上，每一层仅能使用期底层所提供的功能和服务

客户 / 服务器模式

（Client / Server Model）

客户机、服务器、网络系统

面向对象的程序设计

微内核 OS 结构

基于客户服务器模式
应用机制与策略分离原理
- 机制是指实现某一功能的具体执行机构，通常处于系统基层，在微内核操作系统中，将机制放在 OS 的微内核中。
  策略是指在机制的基础上借助于某些参数和算法来实现该功能的优化，或达到不同的功能目标，通常处于系统高层。
采用面向对象技术

微内核

能实现现代 OS 最基本核心功能的小型内核
包含
- 与硬件处理紧密相关的部分
- 一些较基本的功能
- 客户与服务器间的通信
如
- 进程管理
- 低级存储器管理
- 中断和陷入管理

优点

正确性、灵活性、易维护性、可扩充性

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

存在的问题

效率低：系统在用户态与内核态多次切换（上下文切换频繁）

进程的描述与控制

前驱图和程序执行

前驱图

顺序执行

前驱图

特征

顺序性
封闭性：程序运行时独占全部资源
可再现性

并发执行

允许多道程序共享资源，次序不确定

前驱图

特征

间断性：程序共享系统资源，程序之间会有相互制约的关系，出现 “执行——暂停——执行” 的间断性活动规律
失去封闭性：程序共享系统资源
不可再现性：失去封闭性，导致了不可再现性

进程的描述

（Process）

进程的定义和特征

进程定义

描述性定义

计算机中的所有程序（软件），按照某种顺序运行，这种运行的过程叫做进程

（一个活动，有程序输入、输出和状态）

典型定义

==进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位==

进程是 CPU 抽象的结果

进程实体

进程在计算机系统中的映像

它包括

进程控制块：（Process Control Block，PCB）系统为了控制进程而设计的数据结构
- 进程描述信息
- 进程控制信息
- …
程序段
相关数据段
管理用户的用户堆栈和系统堆栈：可归类到数据段中

进程特征

动态性：“由创建而产生，由调度而执行，由撤销而消亡”，它有一定的生命期
并发性：多个进程实体同存于内存中，且能在一段时间内同时运行；引入进程实体的目的就是并发执行
独立性：进程实体能够独立运行、获取资源、接受调度
异步性：进程按各自独立的、不可预知的速度向前推进

进程与程序的不同

进程是动态的，程序是静态的
进程是暂时的，程序时永恒的
进程包含程序、数据和PCB
进程可以包含多个程序（调用），同一程序可以对应多个进程（多次执行）

进程的基本状态及转换

进程的三种基本状态

就绪状态（Ready）
- 进程被分配到除 CPU 以外的所有必要资源
- 按一定的策略可被排成就绪队列
执行状态（Running）
- 占用 CPU 运行
- 执行态进程数小于等于 CPU 数
阻塞状态（Block）
- 暂时无法继续执行
- 可以排成一个阻塞队列

三种基本状态的转换

创建状态和终止状态

创建状态
- 创建进程的过程
- 进程刚建立，还未进入就绪队列
终止状态
- 终止进程的过程

挂起状态和进程状态的转换

定义

挂起状态（Suspend）：进程从内存转到外存（进入静止状态，不可接受调度）

执行的进程暂停、就绪的进程不调度

引入挂起状态的原因

终端用户的请求
父进程请求
负荷调节的需要
操作系统的需要

引入挂起原语操作后的状态转换

进程管理中的数据结构 (PCB)

PCB 的作用

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

PCB 中的信息

进程标识符（编号）
处理机状态（通用寄存器，计数器，程序状态字 PSW，用户栈指针）
进程调度信息（进程状态、优先级）
进程控制信息（程序和数据的地址、进程同步和通信机制（信号量等）、资源清单、链接指针）

PCB 组织方式

线性结构 / 方式

将所有的 PCB 都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中

链接结构

把相同状态进程的 PCB 分别通过 PCB 中的链接字链接成一个队列，这样就可以形成就绪队列、若干个阻塞队列和空白队列等

索引结构

系统根据所有进程状态的不同，建立几张索引表

进程控制

操作系统内核

支撑功能
- 中断处理
- 时钟管理（时间片）
- 原语操作（由若干条指令组成，在执行过程中不允许被中断）
资源管理功能
- 进程管理
- 存储器管理
- 设备管理

进程的创建

进程的层次结构

父进程 - 子进程 - 孙进程

进程图

用于描述进程间关系的一棵有向树。图中的结点代表进程。

引起创建进程的事件

用户登录
作业调度
提供服务
应用请求

进程的创建

申请空白 PCB
为新进程分配其运行所需的资源
初始化进程控制块 PCB
将新进程插入就绪列

进程的终止

正常结束
异常结束
外界干预（父进程、操作员或操作系统的干预）

进程终止过程

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

进程的阻塞与唤醒

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

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

进程阻塞过程

进程使用阻塞原语 block 自己
停止运行并进入阻塞队列
调度程序重新调度

阻塞原语：block
阻塞是进程自身的一种主动行为。

进程唤醒过程

调用唤醒原语 wakeup，将等待该事件的进程唤醒。

将进程从阻塞队列移出，
将 PCB 改为就绪，
加入就绪队列。

进程的挂起

挂起原语：suspend

检查进程状态，
改为对应的静止状态，
复制 PCB 到指定内存区域以备查看。
指引重新调度

进程的激活

挂起原语：active

将进程从外存调入内存，检查状态，改为对应就绪/阻塞状态。
如果有抢占机制比较是否抢占。

进程同步

基本概念

进程同步机制的主要任务：对多个相关进程在执行次序中进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。

两种形式的制约关系

直接实现同步，间接实现互斥

间接相互制约关系：互斥
多个程序在并发执行时，由于共享系统资源致使这些执行程序之间形成相互制约的关系。
直接相互制约关系：同步
源于进程之间的合作关系，前趋图

临界资源

（Critical Resource）

系统中一次只允许一个进程使用的资源

诸进程间应采取互斥方式，实现对临界资源的共享。

临界区

（Critical Section）

进程中访问临界资源的代码段

1
2
3
4
5
6
7
while(TRUE)
{
	进入区
	临界区
	退出区
	剩余区
}

同步机制应遵循的问题

空闲让进：无其他进程处于临界区时，允许一个进程进入临界区
忙则等待：已有进程进入临界区时，其他进程必须等待
有限等待：在有限时间内能进入自己的临界区，以免陷入“死等”状态；保证有限时间内进入临界区
让权等待：进程不能进入临界区时应立即释放处理机（避免死等资源，即忙等待 Busy waiting）

硬件同步机制

关中断

禁止中断发生，不适用于多 CPU

在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。

Test-and-Set 指令实现互斥

疯狂测试 lock，如果开门了就锁门后访问

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
boolean TS(boolean *lock)
{
	boolean old;
	old = *lock;
	*lock = TRUE;
	return old;
}
  
do{
	…
	while TS(&lock)
	critical section;
	lock = FALSE;
	remainder section;
}while(TRUE)

利用 Swap 指令实现进程互斥

疯狂交换 key 和 lock，如果 key 变 true 了访问

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void swap(boolean *a, boolean *b)
{
	boolean temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
  
do{
	key = TRUE;
	do{
		swap(&lock,&key);
	}while(key!=FALSE)
	临界区操作;
	lock = FALSE;
	…
}while(TRUE)

信号量机制

整型信号量

信号量定义为一个整型量 S
两个原子操作 wait(S) 和 signal(S) 被分别称为 P、V 操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// 只要信号量小于等于0就不断进行测试（忙等），其实是未遵循让权等待的
wait(S){
    // 探测
	while(S<=0);
	S--;
}

signal(S){
    // 释放
	S++;
}

记录型信号量

解决忙等问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
typedef struct{
	int value;
	struct process_control_block *list;
}semaphore
  
wait(semaphore *S)
{
	S->value--;
	if(S->value<0) 
        block(S->list);
}

signal(semaphore *S)
// 释放一个单位资源
{
	S->value++;
	if(S->value<=0) wakeup(S->list);
}

value：代表资源数目的整型变量
list：一个进程链表指针，用于链接上述所有等待进程。
S->value：表示资源数量
- S->value 大于等于 0：表示系统中可用资源数
- S->value 小于 0：表示已阻塞进程数
- S->value 初始值为 1：表示互斥信号量（临界资源只有一个）
- S->list：记录阻塞进程信息

AND 型信号量

解决死锁问题

将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放，只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。

信号量集

解决多份资源问题

进程对信号量 S~i~ 是该资源的分配下限值 t~i~，要求 S~i~≥t~i~，否则不予分配。一旦允许分配，进程对该资源的需求值为 d~i~，即表示资源占用量，进行 S~i~=S~i~-d~i~ 操作。

特殊情况

Swait(S,d,d)：只有一个信号量 S，允许每次申请 d 个资源，当少于 d 时，不予分配
Swait(S,1,1)：一般的记录型信号量 (S>1) 或互斥信号量 (S=1)
Swait(S,1,0)：S≥1，允许多个进程进入某特定区；S=0，将阻止任何进程进入特定区

信号量应用

利用信号量实现进程互斥

两个信号量互斥

设 mutex 为互斥信号量，其初值为 1，取值范围为 (-1,0,1)。当 mutex=1 时，表示两个进程皆未进入需要互斥的临界区；当 mutex=0 时，表示有一个进程进入临界区运行，另外一个必须等待，挂入阻塞队列；当 mutex=-1 时，表示有一个进程正在临界区运行，另外一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒。

代码描述

1
2
3
4
5
6
7
8
9
semaphore mutex=1;
PA(){
	while(1){
		wait(mutex);
		临界区
		signal(mutex);
		剩余区
	}
}

利用信号量实现前趋关系

管程机制（自学）

面向对象的封装

代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，称之为管程。

组成

管程的名称
局部于管程的共享数据结构说明
对该数据结构进行操作的一组过程
对局部于管程的共享数据设置初始值的语句

管程和进程的不同

进程定义的是私有数据结构 PCB，管程定义的是公共数据结构
进程是由顺序程序执行有关操作，管程进行同步操作和初始化操作
进程的设置目的在于实现系统的并发性，管程的设置目的则是解决共享资源互斥使用问题
进程为主动工作方式，管程为被动工作方式
进程具有动态性，管程是操作系统中的一个资源管理模块，供进程调用

经典进程的同步问题

生产者-消费者问题

生产者-消费者问题是相互合作的进程关系的一种抽象

记录型信号量

循环队列

P 操作互换会引起死锁；V 操作互换不影响

AND 信号量

哲学家进餐问题

记录型信号量

避免死锁的方法

读者-写者问题

写者进程与所有其他读者进程互斥

写者进程互斥

记录型信号量

信号量集机制

进程通信

进程通信就是进程之间的信息交换，用于同步和互斥。

互斥实质上是一种特殊的同步

进程同步实质上就是一种进程通信

概念

低级进程通信（信号量）

效率低
通信对用户不透明
P/V 操作称为低级通信原语

高级进程通信

进程通信 IPC（Inter Process Communication）
使用方便
高效地传送大量数据

进程通信的类型

共享存储器系统（Shared-Memory System）

共享数据结构或存储区

基于共享数据的通信方式（数据结构）
基于共享存储区的通信方式（内存）

管道通信系统

所谓 “管道”，指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件

写进程 —> 管道文件 —> 读进程

以文件为传输介质
以字符流方式读写

消息传递系统（Message Passing System）

以格式化的消息（message）为单位

实现方式
- 程序员利用系统提供的一组通信命令（原语）进行通信
直接通信方式（原语操作）
间接通信方式（通过共享中间实体（信箱通））

客户-服务器系统（Client-Server System）

套接字：分基于文件型和基于网络型
远程方法调用和远程文件调用

消息传递通信的实现方式

直接消息传递系统

发送进程利用 OS 所提供的发送命令（原语），直接把消息发送给目标进程。

直接通信原语
- 对称寻址方式
  send(receiver,message);
  receive(sender,message);
- 非对称寻址方式
  send(P,message);
  receive(id,message);
消息的格式
进程的同步方式
通信链路

信箱通信

信箱的结构
- 信箱头：用于存放有关信箱的描述信息
- 信箱体：由若干个可以存放消息（或消息头）的信箱格组成，信箱格的数目已经每格的大小是在创建信箱时确定的
信箱通信原语
- 邮箱的创建和撤销
- 消息的发送和接收
信箱的类型
- 私用邮箱
- 公用邮箱
- 共享邮箱

线程的基本概念

线程的引入

引入线程是为了减少程序在并发执行时所付出的时空开销，使 OS 具有更好的并发性

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

线程：资源共享、调度独立（作为调度和分派的基本单位）

线程与进程的比较

调度的基本单位
进程是能独立运行的基本单位，在每次被调度时，都需要进行上下文切换，开销较大；
线程切换仅需保存和设置少量寄存器内容，切换代价远低于进程
并发性
都可以并发执行
拥有资源
进程可以拥有资源，并作为系统中拥有资源的一个基本单位；
线程并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源；线程仅拥有隶属进程的资源
独立性
进程间地址空间和资源互相独立；
线程间共享地址空间和资源
系统开销
进程需要切换上下文；
线程没什么资源，开销小
支持多处理机系统
进程必须在单处理机上运行；
单进程中的多线程可分配到不同处理机上执行

线程的实现

内核支持线程（KST, Kernel Supported Threads）：内核创建，能够并发，用户切换线程需要陷入
用户级线程（ULT, User Level Threads）：用户创建，切换不需要陷入，但阻塞后无法调度
组合模式：两者结合相互利用

（线程的实现、线程的创建与终止……）

处理机调度与死锁

处理机调度的层次和调度算法的目标

调度的实质是一种资源分配，处理机调度是对处理机资源进行分配

作业：作业是任务实体，进程是完成任务的执行实体

周转时间：从作业提交给用户开始，到作业完成为止的时间间隔（等待时间与运行时间之和）

系统性能：平均作业周转时间

带权周转时间：$W_i=\frac{T_i}{T{ki}}$（T~ki~ 为运行时间），大于等于 1（周转时间与运行时间之比）

响应时间：交互式进程从提交一个请求到接受到响应的时间间隔

处理机调度的层次

作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需经历不同级别的调度

高级调度（作业调度 / 长程调度）
- 启动、进入系统时
- 决定外存上后备队列的哪几个作业调入内存
- 调度对象是作业，主要用于多道批处理系统中。
中级调度（内存调度 / 平衡调度）
- 挂起 / 唤醒，做内外存的对换
- 主要目的是提高内存利用率和系统吞吐量。
低级调度（进程 / 线程调度）
- 决定就绪队列中的哪个进程获得处理机
- 调度对象是进程（内核级线程），基本调度
- 在多道批处理、分时和实时三种类型的 OS 中，都必须配置这级调度。

处理机调度算法目标

处理机调度算法的共同目标

资源利用率
- ($CPU 的利用率=\frac{CPU 有效工作时间}{CPU 有效工作时间+CPU 空闲等待时间}$)
公平性
- 诸进程都获得合理的 CPU 时间，不会发生进程饥饿现象
平衡性
- CPU 都能经常处于忙碌状态；系统资源的平衡性
策略强制执行
- 如安全策略

批处理系统的目标

平均周期时间短
周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔，包括作业在外存后备队列上等待调度的时间，进程在就绪队列上等待进程调度的时间，进程在 CPU 上执行的时间，以及进程等待 I/O 操作完成的时间。
- 平均周转时间最短，有效提高系统资源利用率，可使大部分用户满意。
平均周转时间：$ (T=\frac{1}{n}[\sum_{i=1}^{n}{T_i}])$
- 平均带权周转时间： $(W=\frac{1}{n}\sum_{i=1}^{n}{\frac{T_i}{T_s}})$
- 作业周转时间 $T$，系统为其服务时间 $T_s$
系统吞吐量高
- 吞吐量：在单位时间内系统所完成的作业数
处理机利用率高

分时系统的目标

响应时间快
响应时间：从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。
均衡性
- 均衡性：系统响应时间的快慢应与用户所请求服务的复杂性相适应。

实时系统的目标

截止时间的保证
- 截止时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间
可预测性

作业与作业调度

凡是涉及作业的调度算法均是非抢占式的

概念

进程：程序段 + 数据 + PCB

作业（Job）：包含程序、数据、作业说明书。

作业步：完成作业的每一个加工步骤。

作业控制块（JCB Job Control Block）：是作业在系统中存在的标志。

作业运行的三个阶段和三种状态

输入、后备、执行、完成

收容阶段（后备状态）：建立 JCB 进入后备队列
运行阶段（运行状态）：分配资源、进入就绪队列
完成阶段（完成状态）：完成

作业最终转化为进程，其中的低级调度不可避免

作业调度的主要任务

接纳多少个作业（允许多少个作业同时在内存中运行）
接纳哪些作业（取决于所采用的调度算法）

选择作业 -> 分配资源 -> 创建进程 -> 作业控制 -> 后续处理

先来先服务 FCFS 调度算法

（First Coming First Serverd）

作业调度 √，进程调度 √

系统按照作业到达的先后顺序来进行调度，或者说优先考虑等待时间最长的作业，而不管作业所需执行时间的长短

特点

不可抢占性、实现简单、顾及作业等候时间
有利于长作业(进程)，不利于短作业(进程)
有利于 CPU 繁忙型作业，不利于 I/O 繁忙型作业
效率不高、没有考虑优先级

短作业优先 SJF 调度算法

（Short Job First / shortest process first，有时会写作 SJN/SPN，N 表 next）

作业调度 √，进程调度 √

以作业长短来计算优先级，作业越短，优先级越高。作业的长短是以作业所要求的运行时间来衡量的。

优点

易于实现
平均周转时间比 FCFS 小

缺点：

效率还不是很高
必须预知作业的运行时间
对长作业非常不利，忽视了长作业的等待时间，出现饥饿现象
人-机无法交互
未考虑作业的紧迫程度

最短剩余时间优先 SRTF

（shortest remaining time first）

SJF 算法的抢占式

一旦有作业就绪，让其需要的 CPU 时间与当前运行作业剩余时间做判断，小者上 CPU

优先级调度 PSA 算法

（priority-scheduling algorithm）

作业调度 √，进程调度 √

基于作业的紧迫度，由外部赋予作业相应的优先级。

可以是抢占式，也可以是非抢占式的

一般为高优先权优先（HPF，highest-priority first）

使得紧迫的任务得以优先执行
静态优先级较死板，动态优先级开销大

高响应比优先调度 HRRN 算法

（highest response ratio next）

既考虑等待时间，也考虑运行时间。进程都到之后开始计算优先权。

动态优先级 ($优先权=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}=响应比 R_p$)

作业等待时间相同，服务时间越短，优先级越高，利于短作业
要求服务时间相同，等待时间越长，优先级越高，利于长作业
作业优先级可以随等待时间的增加而提高

缺点：每次调度都需进行响应比的计算

响应时间并不是周转时间，响应时间是一种不断变化的过程；周转时间是作业运行结束后得出的结果
同理，这里的等待时间表示已经等待的时间，是过程；通常意义上的等待时间则是一种结果

进程调度

进程调度的任务

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

进程调度机制

排队器
分派器
上下文切换器

进程调度方式

非抢占方式：一旦分配给某进程，就一直让它运行下去。
- 正在执行的进程运行完毕，或因发生某时间而使其无法再继续运行
- 正在执行中的进程因提出 I/O 请求而暂停执行
- 进程通信或同步过程中，执行了某种原语操作
抢占方式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程
- 优先权原则
- 短进程优先原则
- 时间片原则

轮转调度 RR 算法

（round robin）

调度契机

一个时间片尚未用完，正在允许的进程便已完成
在一个时间片用完时，计时器中断处理程序被激活，若进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。
时间片未用完时，进程因 I/O 原因造成了堵塞

特点

只能用于调度 CPU 这一类可抢占资源
作业调度一般不使用轮转，因为它资源特别多，包含有对不可抢占资源的分配
短作业存在优先权
长作业上下文切换时间开销大

时间片的选择

时间片过大 -> 退化成 FCFS

时间片过小 -> 过多的上下文切换，吞吐量小

根据系统对响应时间的要求 R和就绪队列中所允许的最大进程数 N~max~ 确定

这里也有响应时间，为用户数目 × 时间片大小

多级反馈队列调度算法 MFQ

（multileved feedback queue）

描述

设置多个就绪队列（优先级逐个降低，时间片逐个增大）
每个队列都采用 FCFS 算法，最后一个队列 RR 算法
- 若有新进程进入，加入第一队列末尾
- 若进程未在时间片内完成，则到第二队列末尾
队列按照优先级调度
- 随着队列优先级的降低，分配的时间片变长

调度算法的性能

终端型用户：交互型作业，较小，可以保证在第一队列时间片内完成即可
短批处理作业用户：稍短的，第一队列完成；稍长的，第二、三队列各执行一个时间片完成，周转时间也较短
长批处理作业用户：依次在第 1 到 n 个队列中运行，再以轮转的方式运行，不必担心作业长期得不到处理。

死锁概述

定义

计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争系统资源而造成的一种互相等待的现象

若无外力作用，这组进程将永远不能继续执行

资源类型

可重用性资源（数目相对固定）和可消耗性资源（生产创建，消费消耗）
可抢占性资源（处理机）和不可抢占性资源（打印机）

死锁产生原因

竞争不可抢占性资源
竞争可消耗性资源
进程推进顺序不当

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。

产生死锁的必要条件

互斥条件（Mutual Exclusion）
- 资源要求互斥访问
请求和保持条件（Hold and wait）
- 提出的请求得不到满足，手头的资源释放不出来
不可抢占条件（No preemption）
- 资源只能由占有者资源释放
循环等待条件（Circular wait）
- 必有一个进程-资源的环形链，环路中的进程形成等待链

处理死锁的方法

不让死锁发生
- 预防死锁：静态策略，破坏死锁产生的必要条件
- 避免死锁：动态策略，不限制必要条件，而去防止系统进入不安全状态（银行家算法）
让死锁发生
- 检测死锁：通过检测机构及时发现死锁，再采取措施（资源分配图）
- 解除死锁：当死锁发生，撤销一些进程，回收资源再分配

预防死锁

破坏四个必要条件之一

“互斥条件”是设备的固有属性，应加以保证，不能被破坏
破坏“请求和保持”条件：进程在中间不会请求新的资源，所有进程在开始前必须一次性申请所需全部资源
- 简单、安全、易于实现
- 资源浪费严重
- 进程延迟运行
破坏“不可抢占”条件：（不可抢占→可抢占）进程逐个申请资源；一旦进程申请的新资源不能得到满足时，必须放弃自己所有已有的资源。
- 实现复杂、代价高昂
- 延长了进程的周转时间，增加系统开销、降低系统吞吐量
破坏“循环等待”条件：资源按类型分配序号并排队；规定每个进程必须按序号递增的顺序请求资源（而不按自己的使用顺序）

避免死锁

实质：确保系统不进入不安全状态

避免死锁与预防死锁的区别

预防死锁对进程的资源申请命令施加限制（规定死的）

避免死锁在进程请求分配资源时进行动态检查，并根据检查结果决定分配

安全状态与安全序列

安全状态：系统能按某种进程推进顺序（$P_1,P_2,…,P_n$）为每个进程 $P_i$ 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。

此时（$P_1,P_2,…,P_n$）为安全序列。

若不存在安全序列，则称为不安全状态。

只要处于安全状态，不定不会死锁
处于不安全状态，也不一定会发生死锁
发生死锁了，就一定处于不安全状态

==银行家算法避免死锁==

四个数据结构

可利用资源向量 Available
- 一个数组，记录每类资源剩余的量，初始值为每个资源的总量
最大需求矩阵 Max
- 每一类进程所需的每一类资源总数
- 纵资源类型，横坐标进程类型
分配矩阵 Allocation
- 每一类进程的资源数已分配到的每一类资源量
需求矩阵 Need
- 每一类进程还需要的每一类资源数
Need[i,j] = Max[i,j] - Allocation[i,j]

其他

Request_i[j] = k：进程 P~i~ 申请 R~j~ 资源 k 个

银行家算法

两个判断 -> 试分配 -> 安全性检查

if Request_i[j] <= Need[i,j]，便转向步骤 2；否则认为出错。
if Request_i[j] <= Available[j]，便转向步骤 3；否则表示尚无足够资源，$P_i$ 须等待。

系统试探着把资源分配给进程 $P_i$，并修改下面数据结构中的数值：

1
2
3
4
5
Available[j] = Available[j] - Request_i[j];

Allocation[i,j]=Allocation[i,j]+Request_i[j];

Need[i,j]=Need[i,j]-Request_i[j];

系统执行安全性算法，检查此次资源分配后系统是否处于安全状态
- 若安全才正式将资源分配给进程 $P_i$
- 否则作废，恢复原来的资源分配状态

安全性算法

设置两个向量：
- 工作向量 Work，表示系统可提供给进程继续运行所需的各类资源数目，初始化 Work=Available
- Finish，表示系统是否有足够的资源分配给进程，使之运行完成。开始时 Finish[i]=false；当有足够资源分配给进程时，Finish[i]=true
从进程集合中找到一个能满足下述条件的进程
- Finish[i]=false && Need[i,j]≤Work[j]
若找到，执行步骤 3，否则执行 4
当进程 $P_i$ 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
1 2 3
Work[j] = Work[j] + Allocation[i,j]; Finish[i] = true; go to step 2
如果所有进程的 Finish[i] == true 都满足，则表示系统处于安全状态。

步骤 2 中所有类型的资源都要被判断，步骤 3 中所有类型的资源都要被释放，使用循环

不足

对资源分配保守
计算多
一些情况下缺乏实用性（进程对资源的需求动态、进程数量不确定）

死锁的检测与解除

死锁检测

资源分配图

（Resource Allocation Graph）

若不存在环路，则必然不存在死锁

死锁定理

从既不阻塞又非独立的进程结点开始简化：消去请求边和分配边
- 将请求边转换为分配边（如果可以的话）
S 为死锁状态的充分条件是：当且仅当 S 状态的资源分配图是不可完全简化的

死锁检测的数据结构

类似银行家算法的数据结构

可利用资源向量 Available
不占用资源的进程（Allocation == 0）记入 L 表
从进程集合中找到一个 Request_i <= Work 的进程
- 将其资源分配图简化
- 释放资源
- 增加工作向量 Work += Allocation
- 记入 L 表
若不能把所有进程都计入 L 表 -> 状态 S 资源分配图不能被完全简化 -> 死锁

死锁解除

抢占资源（剥夺资源）
- 从其他进程剥夺资源给死锁进程
终止（或撤销）进程
1. 撤销所有死锁进程
2. 按照某种资源逐个撤销代价最小的进程，直至资源可用

操作系统（1）

操作系统一

操作系统引论

操作系统概念

定义

目标

作用

作为用户与硬件之间的接口

计算机系统资源的管理者

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

推动 OS 发展的动力

操作系统的发展过程

多道批处理

特点

需要解决的问题

分时系统

关键问题

特征

实时系统

实时任务的类型

分时系统和实时系统的比较

微机操作系统

单用户单任务操作系统

单用户多任务操作系统

多用户多任务操作系统

操作系统的基本特性

并发

引入进程（Process）

线程（Threads）

共享

虚拟

异步

操作系统的主要功能

处理机管理功能

存储器管理功能

设备管理功能

文件管理功能

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

用户接口

程序接口

一些概念

系统调用

内核

处理过程

用户态

核心态

特权指令

现代操作系统的新功能

操作系统结构设计

传统 OS 结构

无结构操作系统

模块化结构 OS

分层式结构 OS

客户 / 服务器模式

面向对象的程序设计

微内核 OS 结构

微内核

优点

存在的问题

进程的描述与控制

前驱图和程序执行

前驱图

顺序执行

前驱图

特征

并发执行

前驱图

特征

进程的描述

进程的定义和特征

进程定义

进程特征

进程与程序的不同

进程的基本状态及转换

进程的三种基本状态

三种基本状态的转换

创建状态和终止状态

挂起状态和进程状态的转换

定义

引入挂起状态的原因