进程同步概念简介 多线程上篇（四）

最终A，B都被阻塞，如果没有外力作用下，两者都能够从堵塞状况释放上去，这就是死锁

相关概念

对于一个水井，你在打水，另外的人还要等一等，这是人类头脑意识做起来的很基本的反应（人眼识别，大脑解析并且作出反应）

但是计算机程序并没有这么智能，你应该对他进行个别处理，以限制别的线程的访问，比如你可以将“安全黄线”变成一个安全门，比如厕所，进去了以后把门关上。。。

这种概念就是锁，锁就是对资源施加控制，锁指的是一种控制权

当处于临界区时，我们称之为获取锁，获得锁以后就可以访问临界资源；

其他线程想要开启临界区，也应该先拿到锁，显然，他们获得不到，因为此时，锁被当前正在执行的线程持有

当前线程结束后，将会释放锁，别得线程就可以获得这个资源的锁，然后....

锁表示一种控制权，对临界资源的访问权限，如果临界资源不止一个，就可能发生这种状况：

需要先后访问两种临界资源A和B，thread1获得了A线程的锁之后，等待获取B的锁，但是thread2获得了资源B的锁，在期待A资源的锁，这就出现了互相等待的状况

比如一条窄桥，同一时刻仅仅允许一辆车通过，如果一旦发生两辆车都走到桥的一半处，而且互不相让，怎么办？这就是死锁

AND型信号量机制就是用于缓解这种多共享资源下的同步问题的

AND 同步模式的基本观念：

将进程在整个运行过程中应该的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。

只要尚有一个资源无法分配给进程，其它所有可能为之分配的资源也不分配给它。

也就是对若干个临界资源的分配，采取原子操作方法：要么把它所请求的资源全部分配到进程，要么一个也不分配。

这种认知就是通过对“若干个临界资源“的原子分配，逻辑上就相当于一份共享资源，要么受到，也么得不到，所以就不会出现宕机

在 wait 操作中，增加了一个“AND”条件，所以被称为AND 同步，也被称为同时wait操作，即Swait(Simultaneous wait)，相应的signal被称为Ssignal(Simultaneous signal)

Swait(S) 和 Ssignal(S)可以描述为：

Swait(S1，S2，…，Sn)
        if(Si>=1 and …  and Sn>=1){
          for( i=1 to n){
          Si=Si-1;
          }
        }else{
        将进程插入到第一个资源<1 的对应的S的队列中，并且程序计数器设置到Swait的开始(比如S1 S2 都大于等于1，但是 S3<1，那么就插入到S3.L中；从头再来就是为了整体分配)
        }
  Ssignal(S1，S2，…，Sn)
          for(i=1 to n){
          Si=Si+1;
          将与Si关联的所有进程从等待队列中删除，移入到就绪队列中
          }

AND型信号量机制借助于对于多个资源的“批量处理”的原子操作方法，将多资源的同步问题，转换为一个“同一批资源”的同步问题

记录型信号量机制中，只是对信号量加1（S+1 或者S.value+1） 或者 减1（S-1 或者S.value-1）操作，也就是只能拿到或者释放一个单位的临界资源

如果想要一次申请N个呢？

如果进行N次的资源申请怎么办，一种方式是可以使用多次Wait(S)操作，但是肯定效率较低；

另外有时候当资源总量超过某一下限值时，就不进行分配怎么办？需要在每次分配资源前检查资源的总量。

为了缓解这两个问题，对AND信号量机制进一步扩充，形成了一般化的“信号量集”机制。

Swait操作可表述如下

其中S为信号量，d为需求值，而 t为上限值。

Swait(S1，t1，d1，…，Sn，tn，dn)
  if( Si>=t1 and …  and Sn>=tn){
          for(i=1 to n){
                  Si=Si-di;
          }
  }else{
          将进程插入到第一个资源Si<ti 的对应的S的队列中，并且程序计数器设置到Swait的开始(比如S1 S2 都大于等于t1,t2，但是 S3<t3，那么就插入到S3.L中；从头再来就是为了整体分配)    
  }
Ssignal(S1，d1，…，Sn，dn)
         for(i=1 to n){
                  Si=Si+di;
                将与Si关联的所有进程从等待队列中删除，移入到就绪队列中
          }

信号量集就是AND型信号量机制将资源限制扩展到Ti

上面的格式为（s，t，d）也就是第一个为信号量，第二个为限制，第三个为需求量

所以Swait(S，1，0)可以用做开关，只要S>=1，>=1时可分配，每次分配0个，所以只要S>=1，永远都进的来，一旦S<1，也就是0往后，那么就不满足条件，就一个都进不去

临界区机制通过算法控制进程串行进入临界区peterson算法忙等待，而信号量机制则是借助于原语操作（原子性）对临界资源进行访问控制

按照诸多信号量机制对应的规则以及相应的语义操作，就可以做到对资源的共享同步访问，而不会出现难题

信号量机制总共有四种

整型信号量机制可以处理同一共享资源中，资源数量不止一个的状况

记录型信号量对整型信号量机制的“忙等”进行了改进，通过block以及weakup原语进行阻塞和通知

AND型信号量机制解决了针对多个共享资源的同步

信号量集是对AND的再一次优化，既无法处理多个共享资源同步的难题，还能够设定资源申请的上限，是一种更加通用的处理方法

为使多个进程能互斥地访问某临界资源，只须为该资源修改一互斥信号量 mutex，并设其初始值为1

然后将各进程访问该资源的临界区 CS置于 wait(mutex)和 signal(mutex)操作之间即可。

这样，每个欲访问该临界资源的进程在开启临界区之前，都要先对 mutex 执行wait操作，若该资源此刻未被访问，本次wait操作必然失败，进程便可开启自己的临界区，否则进程将要阻塞。

wait(mutex)；

signal(mutex)；

剩余区

前驱关系就是指执行次序，比如规定语句S1执行结束以后能够执行语句S2

在进程P1中：

signal(S)；

在进程P2中

wait(S)；

显然，初始时将资源S设置为0，S2需要获得到资源才能执行，而S1执行后才会释放资源

对于一个更加复杂的前驱关系图，如何实现？

从图中可以看得出来，有S2和S3依赖S1

S4 和 S5依赖S2，而S6依赖S3、S4、S5

所以，S1应该提供两个信号量，提供给S2和S3 使用

S2 应该等待S1的信号量，并且提供两个信号量给S4 和 S5

S3 应该等待S1的信号量，并且提供一个信号量给S6

S4应该等待S2的信号量，并且提供一个给S6

S5应该等待S2的信号量，并且提供一个给S6

S6应该期待S3、S4、S5

所以总共应该2+2+1+1+1 6个信号量，我们取名为a，b，c，d，e，f，g

那么过程如下：

Var a,b,c,d,e,f,g：semaphore: =0,0,0,0,0,0,0;
P1{
        S1;
        signal(a);
        signal(b);
}
P2{
        wait(a);
        S2;
        signal(c);
        signal(d);
}
P3{
        wait(b);
        S3;
        signal(e);
}
P4{
        wait(c);
        S4;
        signal(f);
}
P5{
        wait(d);
        S5; 
        signal(g);
}
P6{
        wait(e);
        wait(f); 
        wait(g);
        S6;
}

有人可能会疑惑，这里的wait和signal又是什么？他就是信号量机制中的 wait 和 signal，他的内容是相当于下面的很多

虽然信号量机制是一种既便于、又有效的进程同步模式，但每个要访问临界资源的进程都需要自备同步操作 wait(S)和 signal(S)，这就使大量的同步操作分散在各个进程中。

这不仅给平台的管理带来了麻烦，而且还能因同步操作的使用不当而造成平台死锁。

在缓解上述难题的过程中，便形成了一种新的进程同步工具——管程(Monitors)。

所以管程也可以这么理解：它还能保证临界资源的同步访问，并且还不用将长期的同步操作分散到各个进程中。

系统中的诸多硬件资源和工具资源，均可用数据结构抽象地叙述其资源特点

比如一个IO设备，有状况（空闲还是忙时？），以及可以对他采取的操作（读取还是写入？）以及等待该资源的进程队列来表述，所以就可以从这三个维度抽象表述一个IO设备，而不关注人们的内部细节

又包括，一个集合，可以使用集合大小，类型，以及一组可执行操作来表述，比如Java中的ArrayList，有属性，还有方法

可以把对该共享数据构架实施的操作定义为一组过程

比如资源的请求和传递过程定义为request 和 release

进程对共享资源的申请、释放和其它操作，都是通过这组过程对共享数据构架的操作来推动的

类比到JavaBean的话，这些操作就正如setter和getter方式，所有针对选定对象的操作访问都应该借助getter和setter方式 ，类似，所有对共享数据构架实施的操作，都应该借助于这一组过程。

这组过程还可以依据资源的状况peterson算法忙等待，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管控对共享资源的所有访问，实现进程互斥

还是类比到JavaBean，就是相当于又提高了几个方法，这些方式提供了更多的逻辑判定控制

代表共享资源的数据结构，以及由对该共享数据构架实施操作的一组过程所组成的资源管控程序，共同构成了一个操作系统的资源管控模块，我们称之为管程。

Dijkstra于1971年提出：

把所有进程对某一种临界资源的同步操作都集中起来，构成一个所谓的秘书进程。

凡要访问该临界资源的进程，都需先报告秘书，由秘书来推动诸进程对同一临界资源的互斥使用。

管程的概念经由Dijkstra提出的概念进化而来，由Hoare和Hanson于1973年提出。

一组相关的数据结构和过程一并称为管程。

Hansan的定义：一个管程定义了一个数据结构和能为并发进程在该数据结构上所执行的一组操作，这组操作能同步进程和改变管程中的数据。

所以管程的核心部分是对共享数据抽象表述的数据结构以及可以对该数据结构实施操作的一组过程。

使用数据结构对共享资源进行具象描述，那么必然要初始化数据，比如一个队列Queue，有属性size，这是一个抽象的数据结构，那么一个具体的队列到底有很大？你应该修改size 的值，所以针对管程还包含初始化

一个基本的管程定义如下：

Minitor{
  管程内部的变量结构以及说明;
  函数1(){
  }
  ......
  函数N(){
  }
  init(){
       对管程中的局部变量进行初始化;
  }
}

管程就是管理进程，管程的概念就是设计理念中“依赖倒置原则”，依赖倒置原则是软件设计的一个理念，IOC的概念就是依赖倒置原则的一个具体的设计

管程将对共享资源的同步处理封闭在管程内，需要办理和传递资源的进程读取管程，这些进程不再需要自主维护同步。有了管程这个大管家（门面模式？）进程的同步任务将要变得更加简单。

管程是墙，过程是门，想要访问共享资源，必须借助管程的控制（通过城墙上的门，也就是经过管程的过程）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-120618-1.html