操作系统之进程同步

一、临界区

互相协作的进程之间有共享的数据，于是这里就有一个并发情况下，如何确保有序操作这些数据、维护一致性的问题，即进程同步。为了解决合作进程之间的竞争条件，引入临界区问题模型。临界区是包含访问共享数据指令的相关代码段，也是多个进程都包含的代码段，在这段代码中可能会进行更新数据表、交换变量等操作。从数据一致性的角度来说，当一个进程进入临界区后，其他进程就不允许进入临界区，也就是不能有多个进程同时处于临界区。

临界区问题（critical-section problem）是设计一个以便进程协作的协议。每个进程必须请求允许进入其临界区。实现请求的代码段称为进入区（entry section），临界区之后可有退出区（exit section），其他代码段成为剩余区（remainder section）。

临界区问题的解答必须满足三项要求：

（1）互斥（mutual exclusion）：如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行；

（2）渐进（progress）：如果没有进程在其临界区内执行且有进程需进入临界区，那么只有那么不在剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟；

（3）有限等待（bounded waiting）：从一个进程做出进入临界区的请求，直到该请求允许为止，其他进程允许进入其临界区内的次数有上限。

二、Peterson's 算法

Peterson算法是一种经典的基于软件的临界区问题算法，解决了两进程的临界区问题，但是该算法在多进程时实现比较复杂，通常不会用在实际问题中。

下面是Peterson 算法的pi进程伪代码：

//两进程共享的数据
int turn;
boolean flag[2];

//进程Pi的Peterson算法
do{

   flag[i]=true;
   turn=j;
   while(flag[j]&&turn==j);//注意这里的while后有个分号，它是个空循环
       critical section //临界区
   flag[i]=FALSE;
       remainder section //剩余区
}while(TRUE)

变量turn表示哪个进程可以进入其临界区，即如果turn==i，那么进程Pi允许在其临界区内执行。
数组flag表示哪个进程想要进入临界区，如果flag[i]为true，即Pi想进入其临界区。
上述代码执行的过程为：pi准备好了想进入临界区，但是pi在进入临界区前先看看pj是否也想进入临界区（true=j）,如果pj也想进入临界区，则让pj先进，pi循环等待，直到pj从临界区出来将flag[j]置为false，pi跳出循环进入临界区。而如果两个进程几乎同时执行的话，能够决定让哪个进程进入临界区的是true的值，由于true是两进程共享的变量，所以即使两进程都对true进行了操作，后一个也会覆盖前一个，最终只有一个进程能够进入临界区。
三、互斥锁（Mutex Locks）

do{
  acquire lock//获得锁
    critical section   //临界区
  release lock//释放锁
    remainder section
}while(TRUE)

获取锁与释放锁的定义

acquire(){
  while(!available)
     ;
  available = false;
}
release(){
  available = true;
}

在这种方法中，进程想进入临界区必须先拿到锁，只有当临界区中没有进程时才能够拿到锁，否则必须等待。这种方法的一个缺点是会产生忙等待（busy waiting），优点是不用切换上下文环境。因此当每个进程进入临界区的时间比较短时这种方法还是很有用的。当然这里直接这样操作是不行的，在acquire的while循环那里，如果一个进程判断完available是true跳出循环但是还没有来得及改变变量的值时另一进程抢占了CPU开始执行，这是available还是true，所以他也可以获得锁，这样就会有两个进程进入临界区。上面的方法只是抽象出来的，实际执行中会在硬件上采用原子操作，避免上述情况的发生，具体细节不再详述。即你可以简单的将获得锁和释放锁看成是一个整体的、不可被打断的操作。
四、信号量
信号量S是个整数变量，除了初始化外，它只能通过两个标准原子操作：wait()和signal()来访问。即P和V。
wait()就是等待资源的过程，定义可表示为：

wait(S)
{
  while(S<=0)
    ;//busy wait
  S--;
}

signal()就是释放资源的过程，定义可表示为：

signal(S)
{
  S++;
}

在wait()和signal()操作中，对信号量整型值的修改必须不可分地执行。即当一个进程修改信号量值时，不能有其他进程同时修改同一信号量的值。另外，对于wait(S)，对于S的整数值测试(S≤0)和对其可能的修改(S–)，也必须不被中断地执行。

信号量的基本用法如下：

do
{
  wait(mutex);
    //critical section
  signal(mutex);
    //remainder section
}while(TRUE);

可以看到互斥锁其实就是信号量的一种特殊形式（当信号量为二进制信号量时），而从互斥锁中可以知道其具有忙等待的缺点，可以通过阻塞自己来解决这一缺点。
将信号量定义为结构体，如下：

typedef struct
{
    int value;                  //记录了这个信号量的值   
    struct process *list;       //储存正在等待这个信号量的进程（PCB链表指针）
}semaphore;

wait实现：

wait(semaphore *S)//消耗资源
        {
  S->value--;
  if(S->value<0)                  //没有资源
  {
  add this process to S->list;      //进入等待队列  
  block();                          //堵塞
  }
}

signal实现：

signal(semaphore *S)//释放资源
{
    S->value++;
    if(S->value<=0)
    {                  //上面++后，S仍然还<=0，说明资源供不应求，等待者还有很多，于是唤醒等待队列中的一个
        remove a process P from S->list;
        wakeup(P);                        //唤醒进程p  
    }
}

在具有忙等的信号量经典定义下，信号量的值不会为负数，但是本实现可能造成信号量为负值。如果信号量为负值，那么其绝对值就是等待该信号量的进程的个数。信号量的关键之处是它们原子的执行。必须确保没有两个进程能同时对一个信号量进行操作，在单处理器情况下，可以在执行wait()和signal()的时候简单的关闭中断，保证只有当前进程进行。

具有等待队列的信号量的实现可能会导致死锁，关于死锁请参阅：http://blog.csdn.net/weiyongle1996/article/details/71511956

五、经典同步问题

1.有限缓冲区问题（生产者消费者问题）

问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。

假设缓冲池有 n 个缓冲项，每个缓冲项能存在一个数据项。信号量 mutex 提供了对缓冲池访问的互斥要求，并初始化为 1 。信号量 empty 和 full 分别用来表示空缓冲项和满缓冲项的个数，信号量empty初始化为 n ；而信号 empty初始化为 0 。

生产者进程结构：

do
{
  …
  //produce an item in next p 生产
…
wait(empty);//只要有一个空的缓冲项就可以添加
wait(mutex);//保证消费者生产者不能同时进入缓冲区
…
//add next p to buffer 加入到缓冲区
…
signal(mutex);
signal(full);
}while(TRUE);

消费者进程结构：

do
{
wait(full);//只要有一个满的缓冲项就可以移除
wait(mutex);
…
//remove an item from buffer to next c 从缓冲区移除
…
signal(mutex);
signal(empty);
…
//consume the item in next c 消费
…
}while(TRUE);

2.读者写者问题

读者写者问题描述：有一个写者很多读者，多个读者可以同时读文件，但写者在写文件时不允许有读者在读文件，同样有读者在读文件时写者也不去能写文件。

即要满足下面的条件：

第一．写者要等到没有读者时才能去写文件。

第二．所有读者要等待写者完成写文件后才能去读文件。

读者写者共享的数据，其中信号量mutex和wrt初始化为1，readcount初始化为0，信号量wrt为读者和写者进程所共有。信号量mutex用于确保在更新变量readcount时的互斥。变量readcount用来跟踪有多少进程正在读对象。信号量wrt供写者作为互斥信号量，它为第一个进入临界区和最后一个离开临界区的读者所使用，而不被其他读者所使用（这样就可以保证只要有读者就不会有写者过来写数据）：

semaphore mutex, wrt;
int readcount;

读者结构：

do
{
    wait(mutex);//保证修改readcount时互斥
    readcount++;
    if(readcount==1)
    wait(wrt);//第一个读者来时获得wrt信号量
    signal(mutex);
    …;
    //reading is performed
    …;
    wait(mutex);
    readcount--;
    if(readcount==0)
        signal(wrt);//最后一个写者离开时释放信号量wrt
    signal(mutex);
}while(TRUE);

写者结构：

do
{
  wait(wrt);//保证写数据时没有读者和其他写者
  …;
  //writing is performed
  …;
  signal(wrt);
}while(TRUE);

上述解法是读者优先的解法，即只要有读者在读数据，后续的读者都可以进入，而等待的写者却不可以进入，直到读者全部从临界区出来后，写者才可以进入。这种方法比较适用于一下情况：

一是，当可以区分哪些进程只需要读共享数据，哪些进程只需要写共享数据；

二是，当读者进程数比写进程多时。

还有另一种写者优先的解法，即只要是写者就绪，就优先让写者进入，读者等待。具体方法不再详述。

3.哲学家就餐问题

哲学家问题描述：假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只筷子。因为用一只筷子很难吃到意大利面，所以假设哲学家必须用两只筷子吃东西。他们只能使用自己左右手边的那两只筷子。哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的筷子，永远都在等右边的筷子（或者相反）。

semaphore chopstick[5];//共享的数据

do
{
  wait(chopstick[i]);
  wait(chopstick[(i+1)%5]);
  …;
  //eat
  …;
  signal(chopstick[i]);
  signal(chopstick[(i+1)%5]);
  …;
  //think
  …;
}while(TRUE);

这是一种简单的解法，每只筷子都用一个信号量来表示。一个哲学家通过执行wait()操作试图获取相应的筷子，他会通过执行signal()操作以释放相应的筷子。但正如上面所说，如果所有的哲学家同时饥饿，拿起一只筷子，就会产生死锁。

可能的解决方案有：

1.最多只允许4个哲学家同时坐在桌子上；

semaphore chopstick[5]={1，1，1，1，1}; 
semaphore room=4; 
void philosopher(int i) 
{ 
while(true) 
{ 
think(); 
wait(room); //请求进入房间进餐 
wait(chopstick[i]); //请求左手边的筷子 
wait(chopstick[(i+1)%5]); //请求右手边的筷子 
eat(); 
signal(chopstick[(i+1)%5]); //释放右手边的筷子 
signal(chopstick[i]); //释放左手边的筷子 
signal(room); //退出房间释放信号量room 
} 
}

2.只有两只筷子都可用时才允许一个哲学家拿起它们（他必须在临界区内拿起两只筷子）；

semaphore chopstick[5]={1，1，1，1，1}; 
void philosopher(int I) 
{ 
while(true) 
{ 
think(); 
Swait(chopstick[(I+1)]%5,chopstick[I]); 
eat(); 
Ssignal(chopstick[(I+1)]%5,chopstick[I]); 
} 
}

3.使用非对称解决方法，即技术哲学家先拿起左边的筷子，接着拿起右边的筷子，而偶数哲学家先拿起右边的筷子，接着拿起左边的筷子。

semaphore chopstick[5]={1，1，1，1，1}; 
void philosopher(int i) 
{ 
while(true) 
{ 
think(); 
if(i%2 == 0) //偶数哲学家，先右后左。 
{ 
wait (chopstick[ i + 1 ] mod 5) ; 
wait (chopstick[ i]) ; 
eat(); 
signal (chopstick[ i + 1 ] mod 5) ; 
signal (chopstick[ i]) ; 
} 
else //奇数哲学家，先左后右。 
{ 
wait (chopstick[ i]) ; 
wait (chopstick[ i + 1 ] mod 5) ; 
eat(); 
signal (chopstick[ i]) ; 
signal (chopstick[ i + 1 ] mod 5) ; 
} 
}

秒客网

操作系统之进程同步

相关文章