此部分内容为笔者大二下学期的复习笔记摘过来的。

Ⅲ进程管理

一、进程与线程

进程概念的引入

两个基本概念：并发与并行

顺序执行
并发Concurrent：设有两个活动a1和a2，如果在某一指定的时刻t，无论a1和a2是在同一处理机上还是在不同的处理机上执行，只要 a1和a2都处在各自的起点和终点之间的某一处，则称a1和a2是并发执行的。
并行Parallel：如果考虑两个程序,它们在同一时间度量下同时运行在不同的处理机上，则称这两个程序是并行执行的。

并发性的确定－Bernstein条件

定义：

R(Si)：Si的读子集, 其值在Si中被引用的变量的集合
W(Si)：Si的写子集, 其值在Si中被改变的变量的集合

Bernstein条件：

两个进程S1和S2可并发，当且仅当下列条件同时成立：
- R(S1) ∩ W(S2) = Φ
- W(S1) ∩ R(S2) = Φ
- W(S1) ∩ W(S2) = Φ

判断程序并发执行结果是否可再现的充分条件。

进程的定义

进程是程序的一次执行；
进程是可以和别的计算并发执行的计算；
进程可定义为一个数据结构，及能在其上进行操作的一个程序；
进程是一个程序及其数据在处理机上顺序执行时所发生的活动；
进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

进程的特征

动态性：进程是程序的一次执行过程，因创建而产生，因调度而执行，因无资源而暂停，因撤消而消亡；而程序是静态实体。
并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。
独立性：在传统OS中，进程是独立运行的基本单位
异步性：也叫制约性，进程之间相互制约，进程以各自独立的不可预知的速度向前推进。
结构特征：程序、数据、进程控制块PCB

一个进程应该包括

程序的代码；
程序的数据；
PC中的值，用来指示下一条将运行的指令；
一组通用的寄存器的当前值，堆、栈；
一组系统资源（如打开的文件）

进程与程序的区别

进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件，静态和可以复制。
进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。
进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。
进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

进程状态与控制

进程控制

进程控制的主要任务是创建和撤消进程，以及实现进程的状态转换。由内核来实现。

进程的创建

提交一个批处理作业
用户登录
由OS创建，用以向一个用户提供服务
由已存在的一进程创建

进程撤消

用户退出登录
进程执行一个中止服务的请求
出错及失败因素
正常结束
给定时限到

原语：由若干条指令所组成的指令序列，来实现某个特定的操作功能
- 指令序列执行是连续的，不可分割
- 是操作系统核心组成部分
- 必须在管态（内核态）下执行，且常驻内存
与系统调用的区别
- 不可中断
进程图
创建原语(fork, exec)
撤消原语(kill)
- 释放资源、撤消子进程、重新调度。

进程状态及其演变

进程的三种基本状态

就绪状态：进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配CPU就可执行。
执行状态：占用处理机资源；处于此状态的进程的数目小于等于CPU的数目。在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）。
阻塞状态：正在执行的进程，由于发生某种事件而暂时无法执行，便放弃处理机处于暂停状态。

进程控制块

系统为每个进程定义了一个数据结构：进程控制块PCB（Process Control Block）。
作用：
- 进程创建、撤消；
- 进程唯一标志；
进程控制块是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。

PCB的组织方式

线性表：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。
链接方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。
索引方式：系统按照进程的状态将进程的PCB 组成队列，从而形成就绪队列、阻塞队列、运行队列等。

辨析：进程上下文切换vs 陷入内核

进程上下文切换（Process Context Switch）
- 通常由调度器执行
- 保存进程执行断点
- 切换内存映射（页表基址、flush TLB）
陷入/退出内核（也称为模态切换, Mode Switch) •
- CPU状态改变
- 由中断、异常、Trap指令（系统调用）引起
- 需要保存执行现场（寄存器、堆栈等）
系统调用涉及到进程从用户态到内核态的切换（mode switch），这个时候涉及到的切换主要是寄存器上下文的切换，和通常所说的进程上下文切换（Process Context Switch）不同，mode switch 的消耗相对要小很多。

线程概念的引入

线程（thread）的提出

进程的不足：
- 进程只能在一个时间处理一个任务，不能同时处理多个任务。
- 如果进程在执行时阻塞，整个进程都无法继续执行。例如：在等待输入时，即使进程中有些处理不依赖于输入数据，也将无法执行。
需要提出一种新的实体，满足以下特性：
- 实体之间可以并发地执行；
- 实体之间共享相同的地址空间；

进程与线程

调度

实际上，进程包含了两个概念
- 资源拥有者
- 可执行单元
现代操作系统将资源拥有者称为进程（process, task），将可执行单元称为线程（Thread）。

并发性

多进程：多个程序可以并发执行，改善资源使用率，提高系统效率
多线程：并发粒度更细（任务级并行）、并发性更好

拥有资源

线程间可以共享资源

进程的资源：虚拟地址空间、进程映像、处理机保护、文件、 I/O
线程的资源：运行状态、上下文（如：程序计数器）、执行栈。

系统开销

进程
- 创建/撤销时需要分配/回收大量资源
- 进程切换时涉及运行环境的保存与设置
- 进程间的同步需要借助消息通信机制。
线程：由于资源共享，有效减少了创建/撤销/切换/同步等所造成的开销

小结

引入线程的优势

线程很轻量：容易创建、撤销
- 有些应用要求并行实体具备共享同一个地址空间和所有可用数据的能力
- 创建一个线程比一个进程快10-100倍
- 对于存在大量计算和大量I/O处理的应用，大幅度提高性能
- 在多CPU/多核CPU系统中更有优势

进程v.s.线程

线程的实现方式

用户级线程

线程在用户空间,通过 library模拟的thread,不需要或仅需要极少的kernel支持
上下文切换比较快,因为不用更改page table等,使用起来较为轻便快速.
提供操控视窗系统的较好的解决方案.
用户级的线程库的主要功能

–创建和销毁线程

–线程之间传递消息和数据

–调度线程执行

–保存和恢复线程上下文
典型的例子

–POSIX Pthreads

–Mach C-threads

–Java Threads
优点
- 线程切换与内核无关
- 线程的调度由应用决定，容易进行优化
- 可运行在任何操作系统上，只需要线程库的支持
不足
- 很多系统调用会引起阻塞，内核会因此而阻塞所有相关的线程。
- 内核只能将处理器分配给进程，即使有多个处理器，也无法实现一个进程中的多个线程的并行执行。

内核级线程

内核级线程就是kernel有好几个分身,一个分身可以处理一件事.
这用来处理非同步事件很有用, kernel可以对每个非同步事件产生一个分身来处理.
支持内核线程的操作系统内核称作多线程内核
优点
- 内核可以在多个处理器上调度一个进程的多个线程实现同步并行执行
- 阻塞发生在线程级别
- 内核中的一些处理可以通过多线程实现
缺点
- 一个进程中的线程切换需要内核参与，线程的切换涉及到两个模式的切换（进程-进程、线程-线程）
- 降低效率

用户级线程和内核级线程的比较

内核级线程是OS内核可感知的，而用户级线程是OS内核不可感知的。
用户级线程的创建、撤消和调度不需要OS内核的支持，是在语言或用户库这一级处理的；而内核级线程的创建、撤消和调度都需OS内核提供支持，而且与进程的创建、撤消和调度大体是相同的。
用户级线程执行系统调用指令时将导致其所属进程的执行被暂停，而内核级线程执行系统调用指令时，只导致该线程被暂停。

用户级线程和内核级线程的总结

在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核级线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。
用户级线程的程序实体是运行在用户态下的程序，而内核级线程的程序实体则是可以运行在任何状态下的程序。

混合的线程实现方式

线程模型

有些系统同时支持用户线程和内核线程，由此产生了不同的多线程模型，即实现用户级线程和内核级线程的不同连接方式。
- Many-to-One：将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。此模式中，用户级线程对操作系统不可见（即透明）。
- One-to-One：将每个用户级线程映射到一个内核级线程。
- Many-to-Many：将n 个用户级线程映射到m 个内核级线程上，要求m <= n。

二、同步与互斥

同步与互斥问题

程序的并发执行

并发是OS的设计基础，也是很多关键问题（如:同步互斥）产生的主要原因。

进程的三个特征：
- 并发：体现在进程的执行是间断性的；进程的相对执行速度是不可测的。（间断性）
- 共享：体现在进程/线程之间的制约性（如共享打印机）（非封闭性）。
- 不确定性：进程执行的结果与其执行的相对速度有关，是不确定的（不可再现性）

并发执行，不可避免地产生了多个进程对同一个共享资源访问，造成了资源的争夺。

竞争：两个或多个进程对同一共享数据同时进行访问，而最后的结果是不可预测的，它取决于各个进程对共享数据访问的相对次序。这种情形叫做竞争。
竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关(Bernstein条件)。
临界资源：一次仅允许一个进程访问的资源。
临界区：每个进程中访问临界资源的那段代码称为临界区。

进程的同步与互斥

进程互斥（间接制约关系）：
- 两个或两个以上的进程，不能同时进入关于同一组共享资源的临界区，否则可能发生与时间有关的错误。
- 进程互斥是进程间发生的一种间接性作用，一般是程序不希望的。
进程同步（直接制约关系）：
- 系统中各进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性的过程称为进程同步。
- 进程同步是进程间的一种刻意安排的直接制约关系。即为完成同一个任务的各进程之间，因需要协调它们的工作而相互等待、相互交换信息所产生的制约关系。

同步与互斥的区别与联系

互斥：某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。互斥无法限制访问者对资源的访问顺序，即访问是无序访问。
同步：是指在互斥的基础上，通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有对资源的写入的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

临界区管理应满足的条件

没有进程在临界区时，想进入临界区的进程可进入。
任何两个进程都不能同时进入临界区（Mutual Exclusion）；
任何一个进程进入临界区的请求应该在有限时间内得到满足（Bounded Waiting）。
当一个进程运行在临界区外面时，不能妨碍其他的进程进入临界区（Progress）；

机制设计上应遵循的准则

空闲让进：临界资源处于空闲状态，允许进程进入临界区。临界区内仅有一个进程运行。
忙则等待：临界区有正在执行的进程，所有其他进程则不可以进入临界区。
有限等待：对要求访问临界区的进程，应保证在有限时间内进入自己的临界区，避免死等。
让权等待：当进程（长时间）不能进入自己的临界区时，应立即释放处理机，尽量避免忙等。

基于忙等待的互斥方法

软件方法

Dekker算法
Peterson算法

硬件方案

中断屏蔽：使用“开/关中断”指令。
- 执行“关中断”指令，进入临界区操作；
- 退出临界区之前，执行“开中断”指令。
使用test and set指令：
- TS（test-and-set ）是一种不可中断的基本原语（指令）。它会把“1”写到某个内存位置并传回其旧值。在多进程可同时访问内存的情况下，如果一个进程正在执行TS指令，在它执行完成前，其它的进程不可以执行TS指令。

自旋锁Spinlocks

利用test_and_set硬件原语提供互斥支持 §通过对总线的锁定实现对某个内存位置的原子读与更新

几个算法的共性问题

无论是软件解法（如Peterson）还是硬件（如 TSL或XCHG）解法都是正确的，它们都有一个共同特点：当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止。

忙等待: 浪费CPU时间
优先级反转：低优先级进程先进入临界区，高优先级进程一直忙等

基于信号量的同步方法

同步实现的基本思路

同步中，进程经常需要等待某个条件的发生，如果使用忙等待的解决方案，势必浪费大量CPU时间。
解决方法：将忙等变为阻塞，可使用两条进程间的通信原语：Sleep和Wakeup
- Sleep原语将引起调用进程的阻塞，直到另外一个进程用 Wakeup原语将其唤醒。很明显，wakeup原语的调用需要一个参数——被唤醒的进程ID。

信号量

信号量是Dijkstra1965年提出的一种方法，它使用一个整型变量来累计唤醒次数，供以后使用。在他的建议中引入了一个新的变量类型，称作信号量（ semaphore）。
Dijkstra建议设立两种操作，P(S)和V(S)操作。P、V 分别是荷兰语的test(proberen)和increment(verhogen) 。P操作也称为semWait，V操作也称为semSignal。 PV操作属于进程的低级通信。
信号量是一类特殊的变量，程序对其访问都是原子操作，且只允许对它进行P(信号变量)和V(信号变量 )操作。

信号量的定义

信号量: 一个确定的二元组(s, q)，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列. 当发出P操作时： •
- s为正，则该值等于可立即执行的进程的数量；s<=0，那么发出P操作后的进程被阻塞， │s│是被阻塞的进程数。 •
- q是一个初始状态为空的队列，当有进程被阻塞时就会进入此队列。

信号量的分类

二元信号量和一般信号量

二元信号量：取值仅为“0”或“1”，主要用作实现互斥；
一般信号量：初值为可用物理资源的总数，用于进程间的协作同步问题。

强信号量和弱信号量

强信号量：进程从被阻塞队列释放时采取FIFO–不会出现“饥饿”（某个进程长时间被阻塞）
弱信号量：没有规定进程从阻塞队列中移除顺序–可能出现“饥饿”

二元信号量机制

通常使用二元信号量的PV操作实现两个进程的互斥。
应用时应注意：
- 每个进程中用于实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。 •
- P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
- 互斥信号量的初值一般为1。

1
2
3

P(S) :while S<=0 do skip; 
	S:=S-1; 
V(S) :S:=S+1;

一般信号量的结构

信号量的数据结构，包含:
- 一个初始值为正的整数:s.count
- 一个初始为空的队列: s.queue
其上定义了三个原子操作
- 初始化s
- 发送信号s: semSignal(s)，(V, Up)
- 接收信号s: semWait(s) ，(P, Down)

信号量的操作

一个信号量可能被初始化为一个非负整数.
semWait 操作（P操作）使信号量减1。若值为负，则执行 semWait的进程被阻塞。否则进程继续执行。
semSignal操作（V操作）使信号量加1。若值小于或等于零，则被semWait操作阻塞的进程被解除阻塞。
除此之外，没有任何办法可以检查或操作信号量

“信号量集”机制

当利用信号量机制解决了单个资源的互斥访问后，我们讨论如何控制同时需要多个资源的互斥访问。信号量集是指同时需要多个资源时的信号量操作。

“AND型”信号量集
一般信号量集

P.V操作的优缺点

优点： •简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）
缺点： •不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂

管程(Monitor)

信号量及PV 操作的问题： •信号量机制具有一些缺点，比如说用信号量及 PV 操作解决问题的时候程序编写需要很高的技巧。 •如果没有合理地安排PV 操作的位置，就会导致一些出错的结果，例如：出现死锁等问题。
管程是在程序设计语言当中引入的一种高级同步机制。

管程的定义和组成

管程由四部分组成： 1.管程的名称； 2.局部于管程内部的共享数据结构（变量）说明； 3.对该数据结构进行操作的一组互斥执行的过程； 4.对局部于管程内部的共享数据设置初始值的语句。