第二章进程的描述与控制

1.前趋图和程序执行

1）前趋图：

有向无循环图（关注的是前趋关系，不能有循环）

2）程序顺序执行的特征：

1.顺序性 2.封闭性 3.可再现性

3）程序的并发执行：

要符合前趋关系，并发不是随意的

特征：1.间断性 2.失去封闭性 3.不可再现性

2.进程的描述

1）进程的定义：

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

2）进程的特征：

1.结构性 2. 动态性 3.并发性 4.独立性 5.异步性

3）进程的基本状态：

1.就绪状态 2.执行状态 3.阻塞状态

4）挂起操作原因：

（1）终端用户的需要

（2）父进程请求

（3）负荷调节的需要

（4）操作系统的需要

5）进程控制块PCB

进程实体：

代码段+数据段+PCB

定义：

存放进程的管理和控制信息的数据结构

作用：

（1）作为独立运行基本单位的标志

（2）能实现间断性运行方式

（3）提供进程管理所需要的信息

（4）提供进程调度所需要的信息

（5）实现与其他进程的同步与通信

PCB中的信息：

（1）进程标识等信息

（2）处理机状态信息

（3）进程调度信息

（4）进程控制信息

PCB信息的存放：

常驻内存的PCB区

采用的数据结构：PCB结构体，PCB链表或队列

PCB的组织方式：

（1）线性方式（2）链接方式（3）索引方式

3.进程控制

1）操作系统内核：

支撑功能：

1.中断处理 2.时钟管理 3.原语操作

资源管理功能：

1.进程管理 2. 存储器管理 3. 设备管理

2）进程的创建：（原语操作，不可被打断）

（1）申请空白PCB

（2）为新进程分配其运行所需的资源

（3）初始化进程控制块

（4）将新进程插入到就绪队列

3）进程的终止：（原语操作，不可被打断）

1.正常结束 2.异常结束 3.外界干预

4）进程的阻塞

（1）向系统请求共享资源失败

（2）等待某种操作的完成

（3）新数据尚未到达

（4）等待新任务的到达

4.进程同步

使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

1）进程同步的两种形式的制约关系：

间接相互制约关系

直接相互制约关系

2）访问临界资源的循环进程：

while（true）

{

进入区

临界区

退出区

剩余区

}

3）同步机制应遵循的原则：

（1）空闲让进：资源使用最基本原则

（2）忙则等待：保证互斥

（3）有限等待：合适时被唤醒防止死等

（4）让权等待：能主动释放CPU防止死等

4）控制同步的关键？

不被打断的进行标志值的判断和修改

5）信号量机制

（1）整型信号量

1.信号量定义为一个整型量

2.根据初始情况赋相应的值

3.仅能通过两个原子操作来访问

4. P操作：

wait（s）:

while s<=0 do no-op;

s:=s-1;

V操作:

signal(s):

s:s+1;

（2)记录型信号量：

1.记录型数据结构：整型变量value 进程链表L

2.value>0,表示当前可用资源的数量

value<=0,其绝对值表示等待使用该资源的进程数，即在该信号量队列上排队的PCB的个数

3.P操作：

wait（）：

s.value()=s.value()-1；

if s.value（）<0 then block(s,L)

V操作:

signal():

s.value()=s.value()+1;

if s.value<=0 then wakeup(s,L)

（3)AND型信号量

设置互斥的信号量：Dmutex、Emutex，令它们的初值为1

（4）信号量集

（1）Swait(S,d,d）:此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配

（2）Swait（S,1,1）:此时的信号量集已蜕化为一般的记录型信号量（S>1时）或互斥信号量（S=1时）

（3）Swait（S,1,0）:这是一种很特殊且很有用的信号量操作。当S>=1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

6）信号量的应用

（1）实现有序

1.前趋关系

2.为每队前趋关系设置一个同步信号量S，并赋初值为0

p1: C1;signal(s);

p2:wait(s);C2;

3.控制同步顺序的注意点

①信号量值为0的点是限制的关键

②成对使用P、V原语（在有先后关系的两个进程中），不能次序错误，重复或遗漏。

5.经典进程的同步问题

1）生产者-消费者问题

（1）无论生产者、消费者使用缓冲池时应保证互斥使用（互斥信号量mutex ）

（2）生产者和消费者间交叉有序：

有序的控制最根源在产品数量上。

设置两个信号量：分别针对生产者、消费者设置不同的信号量，empty和full分别表示缓冲池中空缓冲池和满缓冲池（即产品）的数量。

empty、full两者有天然的数量关系，在PV控制下值不断变化，但在值等于0的点上是控制顺序的关键。

2）哲学家进餐问题

（1）记录型信号量解决就餐问题：

筷子是临界资源，在一段时间内只允许一个哲学家使用。为实现对筷子的互斥使用，用一个信号量表示一只筷子，五个信号量构成信号量数组。

Var chopstick: array [0, …, 4] of semaphore;

所有信号量均被初始化为1。.

第i 位哲学家的活动可描述为：

repeat

wait(chopstick[ i ]);//当哲学家饥饿时，总先拿起左边的筷子，再拿起右边的筷子

wait(chopstick[ ( i +1) mod 5] );

…

eat;

…

signal(chopstick[ i ]);//当哲学家饥饿时，总先拿起左边的筷子，再拿起右边的筷子

signal(chopstick[ ( i +1) mod 5] );

…

think;

until false;

(2)就餐死锁问题

解决方法：

1.数量控制：至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕后释放出他用过的两只筷子，从而使更多的哲学家能够进餐。

---限制并发执行的进程数

2.规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即5位哲学家都先竞争奇数号筷子。获得后，再去竞争偶数号筷子。最后总会有一位哲学家能获得两只筷子而进餐。

3.仅当哲学家的左右两只筷子均可用时，才允许他拿起筷子进餐。

---采用AND信号量。

3）读者-写者问题

（1）利用记录型信号量

为实现Reader与Writer进程间在读或写时的互斥而设置了两个互斥信号量wmutex和rmutex。另外，再设置一个整型变量readcount表示正在读的进程数目。

semaphore rmutex=1,wmutex=1;

int readcount=0;

void reader(){

do{

wait（rmutex）; //rmutex=0

if（readcount==0）wait(wmutex); //wmutex=0

readcount++;

signal(rmutex);

……

perform read operation；

……

wait（rmutex）;

readcount--;

if（readcount==0）signal(wmutex);