第二章 进程的描述与控制
2.1.1 进程的基本概念
1. 前趋图
前趋图是一个有向无循环图，可用来描述程序段或进程之间执行的先后依次关系。有直接前趋，直接后继，称没有前趋的节点为初始节点，没有后继的节点为终止节点。
2. 程序的顺序执行特征
3. 程序的并发执行特征
程序的并发执行极大的提高了资源利用效率和系统吞吐量，同时也产生了不同于顺序执行的新特征。
4. 进程的定义与特征
为了使程序能够正确的并发执行，并且可以对并发执行的程序加以描述和控制，操作系统中引入了进程的概念，用进程来表示一个并发执行的程序。
为了使参与并发执行的每个程序（含数据）都能独立的运行，在操作系统中必须为之配备一个专门的数据结构，称为进程控制块（即 PCB，Process Contorl Block）。 PCB、程序段和相关的数据段三个部分构成一个进程实体（又称为进程映像），简称进程。
5. 进程的状态
- 进程的基本状态
对于整个系统而言，每个时刻允许同时有多个进程处于就绪状态，而通常它们将组织成一个或多个就绪队列；也允许同时又多个进程处于阻塞状态，并将它们组织成一个或多个阻塞队列；但对于执行状态的进程，每个处理机最多只允许有一个。 - 进程的挂起状态
6. 进程控制块（包含信息）
为了描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块，即 PCB。PCB 是进程实体的一个组成部分，在 PCB 上记录了 OS 所需的、用于描述进程的当前情况以及控制进程的全部信息。PCB 的作用是将程序变为可并发执行的进程。系统根据进程的 PCB 感知到进程的存在，并通过 PCB 对进程进行控制。因此，PCB 是进程存在的唯一标志。由于 PCB 要被系统频繁访问，因此，PCB 中的信息必须全部或部分常驻内存。
一个系统中通常有许多 PCB，构成 PCB 集合。为了便于管理，系统通常用先行方式或链接方式或索引方式将这些 PCB 组织起来。
2.1.2 进程控制
进程控制是进程管理的最基的功能，主要包括创建和终止进程以及负责进程运行过程中的状态转换等功能。进程控制是操作系统的内核通过原语来实现的。
原语是指由若干条指令组成、用来实现某个特定操作的一个过程。原语的执行具有原子性，即原语在执行过程中不允许被中断。原语常驻内存，而且在系统态下执行。
1. 操作系统内核
现代操作系统中一般将 OS 划分成若干层次，再将 OS 的不同功能，分别设置再不同的层次中。通常将一些与硬件紧密相关的模块（如中断处理器等）、各种常用设备的驱动程序以及运行频率较高的模块（如时钟管理、进程调度和许多模块所公用的一些基本操作），安排在紧靠硬件的软件层次中，将他们常驻内存，这部分通常被称为 OS 内核。
为了使操作系统内核代码和数据不会遭受到用户程序的破坏，通常将处理机的执行状态 分为两种。
2. 进程的创建
导致一个进程去创建另一个进程的典型事件有分时系统中的用户登录和批处理系统中的作业调度。另外，程序本身也可以根据需要去创建新的进程。
创建新的进程是通过创建原语完成的，被创建的进程被称作子进程，而创建子进程的进程则称作父进程。子进程又可以创建自己的子进程，从而形成一棵有向的进程树，即进程图。
进程创建原语的主要任务是创建进程控制块 PCB。具体操作过程是：先从 PCB 集合中申请一个空闲的 PCB，再为新进程分配内存等资源，并根据父进程提供的参数和分配到的资源情况来对 PCB 进行初始化，最后将新进程插入就绪队列。
3. 进程的终止
当进程完成任务或遇到异常情况和外界干预需要结束时，应通过进程终止原语来终止进程。终止进程的实质是收回 PCB。具体操作过程是：找到要终止进程的 PCB；若该进程正在执行，则终止它的执行，并设设置重新调度标志；终止属于该进程的所有子进程；释放终止进程所拥有的全部资源；将终止进程移出它所在的队列并回收 PCB。
4. 进程的阻塞和唤醒
当正在执行的进程需要等待某种事件的完成或本身无新工作可做时，应调用阻塞原语与将自己从执行状态转换成阻塞状态。具体的操作过程是：停止进程的执行，将其状态改为阻塞状态，并把他的 PCB 插入响应的阻塞队列，转调度程序重新调度。当阻塞进程所等待的事情完成时，应调用唤醒原语将该进程的状态从阻塞状态转换成就绪状态，并将它插入就绪队列。
5. 进程的挂起与激活
系统可利用挂起原语将一指定的进程挂起。具体的操作流程是：若进程处于活动阻塞状态，则将它的状态转换成精致阻塞状态；否则，将它转换成静止就绪状态；将 PCB 复制到指定的内存区域供用户或父进程考察；若挂起前进程正在执行，则转换调度程序重新进行进程调度。如果挂起是为了对换，则在挂起进程时还必须将它换出到外存中。
系统可利用激活原语激活一指定进程。具体的操作过程是：若进程处于静止阻塞状态，则将它转换成活动阻塞状态，否则将它转换为活动就绪状态；若进程转换成活动就绪状态，而系统又采用抢占调动策略，则应检查该进程是否有权抢占 CPU，若有则应进行进程调度。同样，如果挂起是为了对换，则在激活被挂起的进程时还必须将它调入进程。
2.1.3 进程同步
进程同步是指对多个相关进程在执行次序上进行协调，它的目的是使系统中诸进程之间能按照一定的规则（或时序），共享资源和相互合作，从而使程序的执行具有可再现性。用来实现同步的机制被称作同步机制。
1. 进程同步的基本概念
2. 信号量机制
- 整形信号量
一个整形信号量通常对应与一类临界资源，它是一个非负的共享整数，用来表示该类资源的数目，除了初始化外，它只能通过两个标准的原子操作 wait（也称作 P）和 signal（也称作 v）来访问。
wait(S){
while（S<=0);
S--;
}
signal(S){
S++;
}
整形信号量的 wait 操作表示申请一个资源，signal 表示释放一个资源。整形信号量的主要问题是：只要 S<=0，wait 操作就会不断的测试，因而，整形信号量没有遵守“让权等待”的规则。
- 记录型信号量
记录型信号量中除了需要一个用于代表资源数目的整形变量 value 外，还增加了一个进程链表指针 list，用于链接所有等待该资源的进程。
typedef struct{
int value;
struct process_control_block *list;
}semaphore;
相应的，wait 和 signal 操作可描述为：
wait(semaphore *S)
S->value--;
if(S->value<0)block(S->list);
}
signal(semaphore *S){
S->value++;
if(S->value<=0)wakeup(S->list);
}
在记录型信号量中，S->value 的初值表示系统中某类资源的数目，因而又称为资源信号量。每次对它进行 wait 操作意味着申请一个单位的该类资源，signal 操作意味着归还一个单位的该类资源。当 S->value>0 时，它的值表示系统中该列资源当前可用的数目；S->value<=0 时，表示该类资源以分配完毕，其绝对值表示系统中因申请该类资源而阻塞在 S->list 队列上的进程数目。
记录型信号量的 wait 操作中，当 S.value 减 1 后， 结果小于 0 时，表示系统中已无资源可供分配，因此进程调用 block 原语自我阻塞，其 PCB 被插入信号量的等待队列 list 中。可见，记录型的信号量遵循了“让权等待”规则。
3. 信号量的应用
- 利用信号量实现前趋关系
信号量可以用来描述程序或语句之间的前趋关系。若 I 是 J 的直接前趋，即 I -> J，则可设置一个初值为 0 的公共信号量 S，并将 signal(S) 操作放在 I 之后，而在 J 前面插入 wait(S) 操作，以保证 J 在 I 完成之后才开始在执行。
- 利用信号量实现互斥
为使多个进程能够互斥的访问某个临界资源，只需为该资源设置一互斥信号量 mutex，并将其初值赋为 1，然后将访问该资源的临界区置于 wait(mutex) 和 signal(mutex) 之间。下面的算法
#######################
2.1.4 进程同步的问题
2.1.5 管程机制
使用信号量来处理同步问题时，同步操作wait(s)和signal(s)分散在各个进程中，并遍布整个程序，这不仅给系统的管理和程序的修改和维护带来了麻烦，而且还会因同步操作的使用不当造成死锁。为了解决上述问题，又产生了一种新的进程同步工具——管程。
1. 管程的定义
管程利用共享数据结构抽象地表示系统中的共享资源，并且将对该共享数据结构实施的特定操作定义为一组进程。换句话说，管程是由一组局部的共享变量、对局部变量进行操作的一组过程以及对局部变量进行初始化的语句序列构成的一个软件模块，取名为monitor_name的管程，其语法描述如下：
管程具有以下特点：
- 管程内的局部变量只能被局部于管程内的过程所访问，反之亦然，即
局部与管程内的过程只能访问管程内的变量和形式参数。- 任何进程只能通过调用管程所提供的过程入口进入管程。
- 任一时刻，最多只能有一个进程在管程中执行。
保证进程互斥的进入管程是由编译器负责的，也就是说，管程是一种编译语言的构件，他的实现需要得到编译器的支持。
2. 条件变量
在任何时刻，最多只有一个进程在管程中执行，因此用管程很容易实现互斥，只要将需要互斥访问的资源用数据结构来描述，并将该数据结构放入管程中便可。若要用管程来实现同步，则在相应条件下不满足时（如临界资源得不到时）必须能够将在管程内执行的进程阻塞。由于阻塞的原因不同，为了将它们区分开，引入了局部于管程的条件变量。条件变量的定义格式为：condition x,y：对条件变量只能执行以下两种操作。
(1) wait操作。如x.wait()用来将执行进程挂到与条件变量x象印的等待队列上。
(2) signal操作。如x.signal()用来唤醒与x条件变量相应的等待队列上的一个进程。值得注意的是，若没有等待进程，则x.signal不起任何作用。
3. 利用管程解决生产者——消费者问题
利用管程来解决生产者——消费者问题，首先必须为它们建立一个管程，具体算法描述如下：
上述管程PC中包括两个局部过程：put和get。过程put负责将产品投放到缓冲池中，过程get负责将缓冲池中取出产品。另外，整形变量count表示缓冲池中已存放的产品数目，条件变量notfull、notempty分别对应于缓冲池不全满、缓冲池不全空两个条件。
相应的生产者和消费者的算法可描述为：
2.1.6 进程通信
进程通信是指进程之间的信息交换。进程之间的互斥和同步，可以在进程交换一定的信息，也可看作是一种进程通信，但由于其交换的信息量少、通信的效率低以及实现方式对用户不透明而被归结为低级通信。
- 进程通信的类型
- 消息缓冲队列通信机制
2.1.7 线程
- 线程的基本概念
他的引入目的是为了减少程序在并发执行时所付出的时空开销。
在多线程
