Contents

1. 背景
2. 临界区
1. 2.1. 临界区的三个原则：
2. 2.2. 实现临界区互斥的解决办法

背景

对共享数据的并发访问可能导致数据的不一致性，要保持数据的一致性，就需要一种保证并发进程的正确执行顺序的机制————同步机制来保证多个进程对共享数据的互斥访问.

进程间的制约关系
间接制约：有些资源需要互斥使用，因此各进程竞争使用这些资源－－独占分配到的部分或全部共享资源，进程的这种关系为进程的互斥;
直接制约：系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。即一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态.进程的这种关系为进程的同步

临界区

进程中访问临界资源的一段代码。
临界区的执行在时间上是互斥的,进程必须请求进入临界区
进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志。
退出区(exit section)：用于将”正在访问临界区”标志清除
剩余区(remainder section)：代码中的其余部分。

临界区的三个原则：

互斥。假定进程Pi在其临界区内执行，其他任何进程将被排斥在自己的临界区之外
有空让进。当没有进程在临界区中执行时，需要进入临界区的进程，应能够很快进入
有限等待。在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区的次数必须是有限的

实现临界区互斥的解决办法

进程互斥的解决有两种做法:
由竞争各方平等协商
引入进程管理者，由管理者来协调竞争各方对互斥资源的使用
具体方法：硬件；软件

软件的办法：

算法1:单标志
算法2：双标志、后检查
算法3(Peterson’s Algorithm)：先修改、后检查；后修改者等待

单标志法

该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号，即若turn=i，则允许Pi进程进入临界区。该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，如果某个进程不再进入临界区了，那么另一个进程也将进入临界区（违背“空闲让进”）这样很容易造成资源利用的不充分。

// P0进程  
while(turn!=i);  
critical section;  
turn=j;  
remainder section;

// P1进程  
while(turn!=j);  // 进入区  
critical section;  // 临界区  
turn = i;  // 退出区  
remainder section;  // 剩余区

双标志法先检查

该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。为此，设置了一个数据flag[i]，如第i个元素值为FALSE，表示Pi进程未进入临界区，值为TRUE，表示Pi进程进入临界区。(初始值？初值均为FALSE,先修改后检查)

// Pi 进程  
while(flag[j]);  // ①      
flag[i]=TRUE;  // ③    
critical section;     
flag[i] = FALSE;   
remainder section;

// Pj 进程  
while(flag[i]);  // ② 进入区  
flag[j] =TRUE;  // ④ 进入区  
critical section;  // 临界区  
flag[j] = FALSE;  // 退出区  
remainder section;  // 剩余区

优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。按序列①②③④ 执行时，会同时进入临界区（违背“忙则等待”)。即在检查对方flag之后和切换自己flag 之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。

双标志法后检查

算法二是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。为此，算法三釆用先设置自己标志为TRUE后,再检测对方状态标志，若对方标志为TURE，则进程等待；否则进入临界区。

// Pi进程  
flag[i] =TRUE;  
while(flag[j]);  
critical section;  
flag[i] =FLASE;  
remainder section;

// Pj进程  
flag[j] =TRUE;  // 进入区  
while(flag[i]);  // 进入区  
critical section;  // 临界区  
flag [j] =FLASE;   // 退出区  
remainder section;  // 剩余区

当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。

Peterson’s Algorithm。

为了防止两个进程为进入临界区而无限期等待，又设置变量turn，指示不允许进入临界区的进程编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入。这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区，只允许一个进程进入临界区。

// Pi进程  
flag[i]=TURE; turn=j;  
while(flag[j]&&turn==j);   
critical section;  
flag[i]=FLASE;  
remainder section;

// Pj进程  
flag[j] =TRUE;turn=i;  // 进入区  
while(flag[i]&&turn==i);   // 进入区  
critical section;  // 临界区  
flag[j]=FLASE;  // 退出区  
remainder section;  // 剩余区

本算法的基本思想是算法一和算法三的结合。利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象

硬件方法

计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。通过硬件支持实现临界段问题的低级方法或称为元方法。

1) 中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。其典型模式为：…关中断;临界区;开中断;…这种方法限制了处理机交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。

2) 硬件指令方法
原子地执行，因而保证读写操作不被中断:
Test-and-Set (TS)指令
SWAP指令

信号量

信号量是OS提供的管理公有资源的有效手段
1965年，信号量由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。

整型信号量

信号量S – 整型变量：信号量代表可用资源实体的数量。
除了初始化之外，仅能通过两个不可分割的[原子]操作访问：

1
2
3

P(S):  while S 0 do no-op;
        S--;
V(S):   S++;

存在忙等——自旋锁:进程在等待锁时自旋

记录型信号量

是一个数据结构,􀂄定义如下：
Struc semaphore
{
int value;
pointer_PCB queue;
}

P（S）: S=S-1
如果S≥0，则该进程继续执行；
S＜0，进程暂停执行，放入信号量的等待队列

V（S）: S=S+1
如果S＞0，则该进程继续执行；
S≤0，唤醒等待队列中的一个进程

信号量和PV原语

S是与临界区内所使用的公用资源有关的信号量
S≥0 可供并发进程使用的资源数
S<0 正在等待进入临界区的进程数
信号量只能通过初始化和两个标准的原语来访问－－作为OS核心代码执行，不受进程调度的打断
初始化指定一个非负整数值，表示空闲资源总数。
信号量实现互斥

信号量实现前趋

前趋图：
若图中存在结点S1指向结点S2的有向边，表示程序段S1应该先执行，而程序段S2后执行。
设置一个信号量s,初值为0，将V(s)放在S1后面，而在S2前面先执行P(s)。

Struct 
smaphore a,b,c,d,e,f,g,h,I,j=0,0,0,0,0,0,0,0,0,0
cobegin 
    {S1;V(a);V(b);V(c);}
    {P(a);S2;V(d);}
    {P(b);S3;V(e);V(f);}
    {P(c);S4;V(g);}
    {P(d);P(e);S5;V(h);}
    {P(f);P(g);S6;V(i)}
    {P(h);P(i);S7;V(j);}
    {P(j);S8;}
coend

And型信号量集

用于同时需要多种资源且每种占用一个进程的信号量操作；
一个进程需要同时获取两个或多个临界资源――可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，”各不相让”
基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait (Simultaneous Wait)。在Swait时，各个信号量的次序并不重要(会影响进程归入哪个阻塞队列)

Swait(S1, S2, …, Sn)   //P原语；
{
while (TRUE)
{
     if (S1 >=1 && S2 >= 1 && … && Sn >= 1)
 {     //满足资源要求时的处理；
       for (i = 1; i <= n; ++i)  --Si; 
          //注：与wait的处理不同，这里是在确信可满足
          //全部资源要求时，才进行减1操作；
       break;
     }
 else
 {    //某些资源不够时的处理；
       进程进入第一个小于1信号量的等待队列Sj.queue;
       阻塞调用进程;
     }
}

Ssignal(S1, S2, …, Sn)
{
  for (i = 1; i <= n; ++i)
  {
    ++Si;      //释放占用的资源；
    for (each process P waiting in Si.queue)
          //检查每种资源的等待队列；
    {
      从等待队列Si.queue中取出进程P;
      if (判断进程P是否通过Swait中的测试)
           //注：与signal不同，这里要进行重新判断；
          {    //通过检查（资源够用）时的处理；
   进程P进入就绪队列;
          }
      else
          {    //未通过检查（资源不够用）时的处理；
   进程P进入某等待队列；
          }
    }
  }
}

一般信号量集

一次需要N个某类临界资源时，就要进行N次wait操作－－低效又可能死锁
一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理；
基本思想：进程对信号量Si的测试值为ti（用于信号量的判断，即Si < ti，表示资源数量低于ti时，便不予分配），占用值为di（用于信号量的增减，即Si = Si - di和Si = Si + di）
Swait(S1, t1, d1; …; Sn, tn, dn);
Ssignal(S1, d1; …; Sn, dn);

生产消费者问题

采用信号量机制：
full是”满”数目，初值为0，empty是”空”数目，初值为N。
实际上，full + empty == N
mutex用于访问缓冲区时的互斥，初值是1
每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥――否则可能死锁
采用AND信号量集：Swait(empty, mutex), Ssignal(full, mutex),

PV操作讨论

P.V操作必须成对出现，有一个P操作就一定有一个V操作
当为互斥操作时，它们处于同一进程
当为同步操作时，则不在同一进程中出现
对于前后相连的两个P(S1)和P(S2) ，顺序是至关重要的:同步P操作应该放在互斥P操作前,而两个V操作顺序则无关紧要

信号量同步的缺点

同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）
易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；
不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；
正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误

SamanthaChen's Blog

计算机操作系统--进程同步-笔记

背景

临界区