【操作系统】知识点总结 之 并发进程

1.并发进程

1.1顺序进程与并发进程

顺序进程

概念：略

特征：顺序性执行、封闭性，独占资源、确定性，即可再现性。

并发进程：

并发环境： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的

特征：

（1）程序结果的不可再现性并发程序执行的结果与其执行的相对速度有关，是不确定的（2）在并发环境下程序的执行是间断性的执行——停——执行
（3）资源共享   系统中资源被多个进程使用
（4）独立性和制约性 独立的相对速度、起始时间   进程之间可相互作用（相互制约） 可分为直接作用和间接作用
（5）程序和计算不再一一对应
（6）并发性

1.2与时间有关的错误

1、并发进程交替使用共享资源时可能出现的错误：例如：P1和P2是两个并发进程P1: ①R1=C; ②R1=R1+1;③C=R1;P2: ④R2=C;⑤R2=R2+1;⑥C=R2;P1全部执行完毕后再执行P2，则C增加2若P2中的④在P1中的③之前执行，则C增加1
原因是没有正确地控制对共享变量C的访问。

2、飞机订票问题

3、缓冲区读写问题：get、copy、put是3个并发进程

1.3 进程间的联系

1、间接式与直接式制约
直接式制约：一程序段等待另一程序段的执行结果
间接式制约：并发程序段竞争同一资源
2、相交进程与无关进程：
相交进程：并发进程在逻辑上有某种联系
无关进程：逻辑上无任何联系的并发进程
直接作用只发生在相交进程之间；间接作用可以发生在相交进程之间，也可发生在无关进程之间

3、进程的同步与互斥：

进程同步（直接作用）：根据一定的时序关系合作完成一项任务并发进程因直接制约而互相等待，彼此相互发送消息进行合作，使得各进程按一定的速度执行进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间。例子：司机与售票员。

进程互斥（间接作用）：各进程竞争使用临界资源（一次只允许一个进程使用的系统资源）。进程互斥是进程同步的一种特殊情况。进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间。

2.临界区管理

2.1 临界区及其使用原则

临界区：进程中涉及临近资源的程序段为临界区/互斥区，多个进程的临界区为相关临界区。

使用原则：有空让进、无空等待、多中择一、有限等待、让权等待。

解决进程互斥的两种做法：由竞争各方平等协商解决，包括硬件、软件两类方法。引入进程管理者来协调竞争各方对互斥资源的使用 。

2.2 实现临界区管理的软件方法

两个失败的尝试1：

bool inside1=false; bool inside2=false;
cobegin
process P1 process P2
while(inside2) do    while(inside1) do
begin end; begin end;
inside1:=true;   inside2 :=true;
临界区；    临界区;
inside1=false;   inside2=false;
} }
coend

两个失败的尝试2：

bool inside1:=false; bool inside2:=false;
cobegin
process P1 process P2
begin begin
inside1:=true;   inside2=true;
while(inside2) do    while(inside1) do
begin end; begin end;
临界区；    临界区;
inside1:=false;   inside2:=false;
end end
coend

成功解决方法（Dekker算法）：

详见：http://blog.csdn.net/aiwuzhiling/article/details/38824029

2.3 实现临界区管理的硬件方法

通过专门提供的硬件指令管理临界区：测试并建立指令TS、交换指令SWAP、开关中断指令

软件解法的缺点主要在于：
   1. 忙等待
   2. 实现过于复杂，需要高的编程技巧

硬件方法解决临界区的管理较为简单有效，其缺点主要在于：
会导致“忙等待”
会导致“饥饿”
中断屏蔽方法代价较高，不适应多处理器

3、信 量与P、V操作

3.1信 量的定义

提出：以上介绍的各种算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题，操作系统可从进程管理者的角度来处理互斥的问题，信 量就是操作系统提供的管理公有资源的有效手段。

定义：Struct semaphore 
         {    int value; //信 量的值
              pointer_PCB queue; //信 量队列指针
         } 

信 量说明：semaphore s信 量代表对某种公共资源的管理（如停车场的看门人），其值是一个非负整数（如停车场内的车位数）
要使用资源的进程（如要进入停车场的车）需通过信 量，有资源时顺利通过（有车位时，看门人打开车栏）；若没有资源可用（如空车位为0），则所有进程都将进入对应信 量的等待队列（如车子在看门人看守的车栏外排队等待）
当一个进程归还资源（如车开出停车场）时，此时若信 量队列有等待进程则释放一个（如让一辆车进入停车场）

特性：

（1）信 量代表对某种公共资源的管理（如停车场的看门人），其值是一个非负整数（如停车场内的车位数）。
（2）要使用资源的进程（如要进入停车场的车）需通过信 量，有资源时顺利通过（有车位时，看门人打开车栏）；若没有资源可用（如空车位为0），则所有进程都将进入对应信 量的等待队列（如车子在看门人看守的车栏外排队等待）。
（3）当一个进程归还资源（如车开出停车场）时，此时若信 量队列有等待进程则释放一个（如让一辆车进入停车场）。

3.2 P、V操作定义

P操作用于申请信 量管理的资源（如停车场一例中需要进入停车场使用车位的车就应执行P操作）

V操作用于释放资源（如停车场一例中需要开出停车场归还车位的车就应执行V操作）

P操作：

P(s)
{
  s.value = s.value－－ ; //s.value减1
  if (s.value
//该进程被阻塞，进入相应队列，然后转进程调度 
   {
     该进程状态置为等待状态;
     将该进程的PCB插入相应的等待队列s.queue的末尾;
   }
   //若s.value减1后仍大于或等于零，则进程继续执行
}

V操作：

V(s)
{
  s.value = s.value ++; //s.value加1
  if (s.value    //从队列中唤醒一等待进程，然后继续执行或转进程调度 
   {
    唤醒相应等待队列s.queue中等待的一个进程;
    改变其状态为就绪态，并将其插入就绪队列;
     } 
  //若相加结果大于零，则进程继续执行 
}

3.3 信 量的使用

（1）使用注意事项：必须置一次且只能置一次初值，且初值不能为负数；只能执行P、V操作 
用信 量及P、V操作解决进程间互斥问题 。

（2）用信 量及P、V操作解决进程间互斥问题 ：
mutex : semaphore; mutex:= 1;
cobegin 
 process Pi
           begin
               …
               P(mutex); 

临界区；

               V(mutex);
               …
           end; 
coend; 

用信 量及P、V操作解决单类机票问题：

var A : ARRAY[1..m] OF integer;
mutex : semaphore;  mutex:= 1;
cobegin 
process Pi
     var Xi:integer;
begin
     L1:
      按旅客要求找到A[j];
      P(mutex)
      Xi := A[j];

      if  Xi>=1 
           then begin Xi:=Xi-1; A[j]:=Xi; 
                V(mutex);输出一张票;  end;
           else  begin 
           V(mutex);输出票已售完; end;
     goto L1;
     end; 

Coend 

用信 量及P、V操作解决多类机票问题
var A : ARRAY[1..m] OF integer;
      s : ARRAY[1..m] OF semaphore; s[j] := 1;
cobegin 

process Pi
     var Xi:integer;
begin
     L1:
      按旅客要求找到A[j];
      P(mutex)
      Xi := A[j];

     if  Xi>=1 
     then begin Xi:=Xi-1; A[j]:=Xi; 
       V(mutex);输出一张票;  end;
     else  begin 
       V(mutex);输出票已售完; end;
     goto L1;
     end; 
Coend 

（3）用信 量及P、V操作解决进程间同步问题 

生产者-消费者问题

问题描述：生产者往缓冲区中放产品，消费者从缓冲区中取产品。

生产者P进程不能往“满”的缓冲区中放产品，设置信 量为S1，初值为1，代表缓冲区有1个空闲空间。

消费者Q进程不能从“空”的缓冲区中取产品，设置信 量S2 ，初值为0，代表缓冲区有0个产品。

用信 量及P、V操作解决进程间同并不斥问题

P //生产者进程
while  (true)  {
      生产一个产品;
      P(s1) ; //初值为1
      送产品到缓冲区;
      V(s2);
}; 

C //消费者进程
while  (true)  {
     P(s2); //初值为0
           从缓冲区取产品;
    V(s1);
             消费产品;
}; 

3.4 信 量及P、V操作讨论

信 量及P、V操作的物理含义
① S>0表示有S个资源可用
② S=0表示无资源可用
③ S ④ P(S)表示申请一个资源
⑤ V(S)表示释放一个资源 

P、V操作必须成对出现，有一个P操作就一定有一个V操作
① 当为互斥操作时，它们处于同一进程
② 当为同步操作时，则不在同一进程中出现
③ 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要，一个同步P操作与一个互斥P操作在一起时，同步P操作在互斥P操作前，而两个V操作无关紧要

信 量及P、V的优缺点
① 优点：简单且表达能力强，用P、V操作可解决任何同步、互斥问题
② 缺点：不够安全，P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂

3.5  信 量与P、V操作经典问题

（1）哲学家吃通心面问题：

问题描述：5个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。每个哲学家必须直接从自己左边和右边同时获得两把叉子才能吃面
解决思路：5位哲学家看作5个进程，需要互斥使用5把叉子，这5把叉子是共享资源，用5个信 量表示。

var fork[I]:array[0..4] of semaphore;       fork[i] := 1;
cobegin 
process Pi                    // i=0,1,2,3,4,
    begin
     L1: 思考；
     P(fork[i]);             //叉子逆时针编 ，先拿左边叉子
     P(fork[(i+1)mod 5]);         //再拿右边叉子
     吃通心面;
     V(fork[i]); //归还左边叉子
     V(fork[(i+1)mod 5]); //归还右边叉子
     goto L1;
    end; 
coend 

上述解法保证了对叉子的互斥使用，但可能出现每位哲学家均拿起左边叉子而同时又等待拿右边叉子的情况，发生死锁，可通过下列几种办法避免死锁：
至多允许4个哲学家同时吃
奇数 先取左手边的叉子，偶数 先取右手边的叉子
每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取 

（2）生产者消费者问题

问题描述：若干进程通过K个有限共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出。任何时刻只能有一个进程可对共享缓冲区进行操作。且满足条件：① 消费者想接收数据时，有界缓冲区中至少有一个单元是满的；② 生产者想发送数据时，有界缓冲区中至少有一个单元是空的 。

解决思路：设置3个信 量
full表示“满”数目，即缓冲区当前产品数，初值为0 
empty表示缓冲区“空位”数目，初值为K；full + empty == K 
mutex用于访问缓冲区时的互斥，初值是1 。

var B: array[0..k-1] of item; in, out:integer:= 0; //缓冲区读写指针
empty, full, mutex: semaphore; empty:=k; full:=0; mutex:=1; 
cobegin 
process producer_i
begin
     L1:produce a product;
     P(empty);P(mutex);//empty初始为K，表示缓冲区有K个空位，每生产一个p(empty)让空位资源-1，      B[in] := product;
     In:=(in+1) mod k;
     V(mutex);  V(full);//full表示目前缓冲区有多少个产品，缓冲区full信 量+1，加入一个产品
     Goto L1;
     end;

process consumer_j        
begin
   L2: P(full);  P(mutex);//
        Product:= B[out];//将缓冲区产品数-1
        out:=(out+1) mod k;
        V(mutex);      V(empty);//空位+1
        Consume a product;
        Goto L2;
      end;  

coend 

（3）苹果桔子问题

问题描述：桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果（apple），妈妈专向盘子中放桔于（orange）；一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果
解决思路：生产者消费者问题的变形，有两类生产者和两类消费者，仍然设置3个信 量
sp表示盘子能放的水果数目，初值为1
sg1表示盘子里有无桔子，初值为0 
Sg2表示盘子里有无苹果，初值为0 

sp, sg1, sg2: semaphore; sp := 1; sg1, := 0; sg2 := 0;
cobegin 
process father        
begin
     L1:削一个苹果；
     P(sp); 放苹果;
V(sg2);goto L1;
end; 
process mother        
begin
     L2:剥一个桔子；
     P(sp); 放桔子；
     V(sg1); goto L2;
end; 

process daughter       
begin
     L4: P(sg2);取苹果；
     V(sp); 吃苹果；
     goto L4;
end; 
process son        
begin
     L3: P(sg1); 取桔子；
     V(sp); 吃桔子；
     goto L3;
end; 
coend 

（4）读者和写者问题

问题描述：读者和写者两组并发进程共享一个文件F，要求允许多个读者同时执行读操作，任一写者在完成写操作之前不允许其他读者或写者工作，写者执行写操作前，应让已有的写者和读者全部退出 
解决思路：设置2个信 量W和R，1个控制变量rc
W控制读写进程对文件的互斥访问，初值为1
R控制各个读进程对rc的互斥访问，初值为1
rc记录正在读文件的进程数，初值为0

var rc: integer; rc:=0; W，R: semaphore; W := 1;  R := 1; 
cobegin 
procedure read;
begin
  P(R);
  rc := rc + 1;
  if rc=1 then P(W)；
  V(R);
  读文件；
  P(R);
  rc := rc – 1;
  if rc = 0 then V(W)；
  V(R);
end; 

procedure write;
begin
    P(W);
    写文件;
    V(W);
end; 
coend 

读写问题详见：http://blog.csdn.net/aiwuzhiling/article/details/38846619

（5）理发师问题

问题描述：理发店有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。没顾客时理发师在理发椅上睡觉，顾客来时必须叫醒理发师，如果其正在理发则坐下来等待，没有空椅子坐就离开
解决思路：设置1个控制变量waiting 和3个信 量
waiting记录等候理发的顾客数，初值为0
customers表等候理发的顾客数，可阻塞理发师进程，初值为0
barbers表正在等候顾客的理发师数，可阻塞顾客进程，初值为0
mutex用于互斥修改waiting，初值为1

解答详见：http://blog.csdn.net/aiwuzhiling/article/details/38848957

本节所介绍的函数和数据结构需要引用头文件semaphore.h。

只有一个持有者的信 量叫二值信 量或互斥信 量
允许有多个持有者的信 量叫计数信 量，在初始化时要说明最多允许有多少个持有者（Count值） 
当任务访问完被信 量保护的共享资源后，必须释放信 量，释放信 量通过把信 量的值加1实现，假如信 量的值为非正数，表明有任务等待当前信 量，因此它也唤醒任何等待该信 量的任务 

申请同类资源

内存资源有m个分配单位，n个进程共享，每个进程依次只能申请一个单位，满足总量才能使用，使用完后一次性释放

银行家算法思想在单种资源情况下的应用：（4个客户每个都有一个贷款额度）

一个状态被称为是安全状态

条件是存在一个状态序列能够使所有的客户均得到其所有的贷款。
图示b状态是安全的，以使Marvin运行结束，释放所有的4个单位资金。这样下去便可满足Suzanna或Barbara的请求。

一个状态被称为是不安全状态

考虑给Barbara另一个她申请的资源，则得到的状态是不安全的。
如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。 

算法描述

查找右边矩阵是否有一行，其未被满足的设备数均小于或等于向量A。如果找不到，系统将死锁，任何进程都无法运行结束

若找到这样一行，可以假设它获得所需的资源并运行结束，将该进程标记为结束，并将资源加到向量A上
重复以上两步，直到所有进程都标记为结束，则状态是安全的，否则将发生死锁 

系统有n个进程和m种不同类型的资源，相关定义如下：

各类资源总数向量——Resource=(R1,R2,…,Rm)，其中Ri表示第i类资源总数
各类资源未分配数向量——Available=(V1,V2,…,Vm) 
最大需求矩阵——Cij表示进程Pi对Rj类资源的最大需求量
分配矩阵——Aij表示进程Pi已分到Rj类资源的个数 

算法基本思想
①系统中所有进程进入进程集合；在安全状态下系统收到进程的资源请求后进行试分配（修改Available ）
②将系统剩余资源和进程集合中其他进程还需要的资源数作比较，找出能满足最大需求量的进程Pi （即(Ci1,…Cim) -(Ai1,…Aim) ≤ Available），找不到则转④ 
③把进程Pi从集合中去掉，将其占用资源归还给系统（即Available+=(Ai1,…Aim)）；集合为空转④，否则转②
④检查进程集合，若为空表明本次申请执行后系统仍处于安全状态，可实施分配；否则说明该申请将导致系统处于不安全状态，则暂不实施分配，让申请进程等待 

例：系统状态如下图所示，给出了剩余资源Available、最大需求矩阵C、分配矩阵A的情况，试处理进程P1发出的资源请求(1, 0, 0, 0)

P0符合条件，归还资源后，Available=(0, 6, 2, 2)+(0, 0, 3, 2)=(0, 6, 5, 4)

P1和P4都符合条件，选P1归还资源，Available =(0, 9, 8, 6)+(2, 0, 0, 0)=(2, 9, 8, 6)

5.4 死锁的检测及解除

基本策略
允许死锁发生
操作系统不断监视系统进展情况，判断死锁是否发生
一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行

死锁检测

检测时机：进程等待时、定时检测、资源利用率下降时
检测手段：利用进程-资源分配图 

方框表示资源类（资源的不同类型）
方框中的黑圆点表示资源实例（存在于每个资源类中）
圆圈中加进程名表示进程
资源实例指向进程的一条有向边来表示分配边
进程指向资源类的一条有向边来表示申请边

进程-资源分配图中的死锁判断
无环路，则此时系统没有发生死锁
有环路，且每个资源类中仅有一个资源，则系统中发生了死锁。此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程 
有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件

检测思路：检测“进程-资源分配图”是否可完全简化（能经过一系列简化使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的）

死锁解除：应以最小的代价恢复系统的运行

资源剥夺法：当发现死锁后，从其他进程那里剥夺足够数量的资源给死锁进程，以解除死锁状态；

撤消进程法：
撤消全部死锁进程，使系统恢复到正常状态。最简单但代价太大
按照某种顺序逐个撤消死锁进程，直到有足够的资源供其他未被撤消的进程使用，消除死锁状态为止

6、管程

信 量的大量同步操作分散在各个进程中不便于管理和控制，读写和维护都很困难，还有可能导致系统死锁 
Dijkstra于1971年提出把所有进程对某一种临界资源的同步操作都集中起来，构成一个所谓的秘书进程（即管程）
凡要访问该临界资源的进程，都需先 告秘书，由秘书来实现诸进程对同一临界资源的互斥使用

概念：

一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据 ——Hanson
管程用共享数据结构抽象地表示系统中的共享资源，而把对该共享数据结构实施的操作定义为一组过程，集中在一个模块中。操作系统或并发程序就由这样的模块构成，模块之间联系清晰，便于维护和修改，易于保证正确性 

管程的特性：

模块化：管程是一个基本程序单位，可以单独编译
抽象数据类型：管程中不仅有数据，而且有对数据的操作
信息掩蔽：管程外可以调用管程内部定义的一些函数，但函数的具体实现外部不可见 

管程的使用：

管程相当于围墙，将共享变量和对它进行操作的若干个过程围了起来
任何进程要访问临界资源时，都必须进入管程通过调用其内的某个函数进行申请
任何进程要归还资源时，也必须进入管程通过调用其内的某个函数进行归还
进程必须互斥访问管程，即同一时刻只能有一个进程在调用管程内的某个函数