2.1 前趋图和程序执行
2.1.1 前趋图
- 前趋图是指一个有向无循环图，用于描述进程之间执行的先后顺序
- 图中的每一个结点可用来表示一个进程或者程序段
- 结点间的有向边则表示两个结点之间存在的前趋关系
2.1.2 程序顺序执行
- 程序的顺序执行：程序在执行时都需要按照某种先后次序顺序执行
- 程序顺序执行时的特征：顺序性、封闭性、可再现性
2.1.3 程序并发执行
- 在系统中引入多道程序技术，使程序或程序段间能并发执行
- 只有在不存在前趋关系的程序之间才能进行并发执行
- 程序并发执行时的特征：间断性、失去封闭性、不可再现性
2.2 进程的描述
2.2.1 进程的定义和特征
- 为了使参与并发执行的每个程序（含数据）都能独立地运行，在操作系统中必须为之分配一个专门的数据结构，称为进程控制块（Process Control Block）
- 利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程
- 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
- 进程的特征包括以下：
- 动态性：最基本的特征，进程实体有一定的生命期限
- 并发性：多个进程实体同时存在于内存中，且能在一段时间内同时运行
- 独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位
- 异步性：进程按照异步方式进行
2.2.2 进程的基本状态及转换
- 进程的三种基本状态：进程在运行规程中呈现间断性的运行规律
- 就绪状态（ready）进程处于准备好的状态，已分配到除了CPU以外的所有资源，如果系统中有许多处于就绪状态的进程，通常将它们排成一个就绪队列
- 执行状态（running）指进程已经获得CPU，其程序正在执行的状态。对任意一个时刻，对于单处理机系统中，只有一个进程处于执行状态。
- 阻塞状态（block）指正在执行的进程由于发生某事件暂时无法继续执行时的状态。此时引起进程调度，OS把处理机分配给另一个就绪进程，而让受阻进程处于暂停状态。
- 状态创建和终止状态
- 创建状态
- 首先由进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息
- 然后为该进程分配运行时所必需的资源
- 最后把该进程转入就绪状态并插入到就绪队列之中
- 终止状态
- 首先是等待操作系统进行善后处理
- 最后将其PCB清零，并将PCB空间返还系统
2.2.3 挂起状态和进程状态的转换
- 为了用户和系统观察和分析进程需要，引入了挂起操作
- 当该操作作用于某个进程时，该进程将被挂起，意味着此时该进程处于静止状态。如果进程正在执行，它将暂停执行。若原本处于就绪状态，则该进程此时暂不接受调度
2.2.4 进程管理中的数据结构
- 进程控制块PCB的作用
- 作为独立运行基本单位的标志：当一个程序配置了PCB之后，就表示它已经是一个能在多道程序环境下独立运行、合法的基本单位。
- 能实现间断性运行方式：当进程因阻塞而暂停运行时，必须保留自己运行时的CPU现场信息，再次被调度运行时，需要恢复现场信息，这些记录在PCB中
- 提供进程管理所需要的信息
- 提供进程调度所需要的信息
2.3 进程控制
2.3.2 进程的创建
- 进程控制是进程管理中最基本的功能
- 引起创建进程的事件
- 进程的创建过程
- 申请空白PCB
- 为新进程分配其运行所需的资源
- 初始化进程控制块
- 如果进程就绪队列接纳新进程，便将新进程插入到就绪队列
2.3.3 进程的终止
2.4 进程同步
- 临界区
- 人们把每个进程中访问临界资源的那一段代码称为临界区，进程互斥地进入自己的临界区，就可以实现进程对临界资源的互斥访问
- 在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区
- 在临界区的后面也要加上一段称为退出区的代码
- 其他的部分称为剩余区
- 同步机制应该遵循的规则
- 空闲让进：当无进程处于临界区时，应该允许一个请求进入临界区的进程进入临界区
- 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
- 有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区
- 让权等待：单进程不能进入自己的临界区时，应立即释放处理机
2.4.3 信号量机制
- 整形信号量
- 整形信号量定义为一个用于表示资源数目的整型量S
- 除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问
- 记录型信号量
- 增加了“让权等待"的策略
- 当一个进程获取不到所需要的资源，就会被放入阻塞队列中
- AND型信号量
- 解决当一个进程需要同时获得多个资源时的情况
- 思想：将进程在整个运行过程中所需要的所有资源，一次性全部的分配给进程，待进程使用完成后再一次释放。只要尚有一个资源未能分配给进程，其他所有可能位置分配的资源也不分配给它
2.4.4 信号量的应用
2.5 经典进程的同步问题
2.5.1 生产者-消费者问题
- 假定在生产者和消费者之间的公共缓冲区具有n个缓冲区，可以使用互斥信号量mutex
int in=0,out=0;
item buffer[n];
semaphore mutex = 1, empty = n,
full = 0;
void producer(){
do{
// produde a nextp
wait(empty);
wait(mutex);
buffer[in] = nextp;
in = (in+1) % n;
signal(mutex);
signal(full);
}while(TRUE);
}
void consumer(){
do{
wait(full);
wait(mutex);
nextc = buffer[out];
out = (out+1) % n;
signal(mutex);
signal(empty);
// consumer a nextc
}while(TRUE);
}
2.5.2 哲学家进餐问题
- 可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组chopstick[5]
// 使用记录型信号量
do{
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
//eat
signal(chopstick[i]);
signal(chopstick[(i+1) % 5];
//think
}while(TRUE);
//使用AND信号量
do{
//think
Swait(chopstiock[(i+1) % 5],
chopstick[i]);
//eat
Signal(chopstiock[(i+1) % 5],
chopstick[i]);
}while(TRUE);
2.5.3 读者-写者问题
- 允许多个读者同时读数据，不允许多个写者同时写数据，读者和写者不能同时操作
// 利用记录型信号量
semaphore rmutex = 1, wmutex = 1;
int readcount = 0;
void reader(){
do {
wait(rmutex);
if(readcount == 0) wait(wmutex);
readcount++;
signal(rmutex);
// perform
wait(rmutex)
radcount--;
if(readcount == 0) signal(wmutex);
signal(rmutex);
}while(TRUE);
}
2.7 线程（Threads）的基本概念
2.7.1 线程的引入
- 引入线程是为了减少程序在并发执行时所付出的时空开销
- 进程的两个基本属性
- 进程是一个可拥有资源的独立单位
- 进程同时又是一个可独立调度和分派的基本单位
2.7.2 线程与进程的比较
- 调度的基本单位
- 在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一进程中的线程时，必然就会引起进程的切换
- 并发性
- 不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可以并发执行
- 拥有资源
- 进程可以拥有资源，并作为系统中拥有资源的一个基本单位
- 线程本身不拥有系统资源，而是仅有一点必不可少的，能保证独立运行的资源
2.7.3 线程的状态和线程控制块
- 线程运行的三个状态：执行状态、就绪状态、阻塞状态
- 线程控制块称为TCB
