操作系统之同步与互斥详解

2021年3月5日 651点热度 1人点赞 1条评论

同步与互斥

相关概念

  • 临界资源:一段时间内仅允许一个进程使用的资源称为临界资源。
  • 竞争条件:两个或多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序,类似这样的情况称为竞争条件。
  • 临界区:进程中访问临界资源的那段代码称为临界区。
  • 同类临界区:所有与同一临界资源相关联的临界区。
  • 同步(Synchronization):多个相互合作的进程在一些关键点上可能需要互相等待或互相交换信息,这种相互制约关系称为进程同步。
  • 互斥:当一个进程正在使用某资源时,其他希望使用该资源的进程必须等待,当该进程用完资源并释放后,才允许其他进程去访问此资源,我们称进程之间的这种相互制约关系为互斥。

临界区

共享资源会造成竞争条件,那么我们该如何避免呢?禁止两个或多个进程在同一时刻对共享资源(包括共享内存,共享文件等)进行操作。也就是说,我们需要达到互斥的状态,即如果一个进程在某种条件下正在对共享资源进行操作,那么除该进程之外的其他进程就应该禁止对该共享资源进行操作。

如何实现互斥操作,我们将在后面进行探讨。

避免竞争条件的问题我们也可以换一种方式去描述。一个进程的一部分时间做内部计算或另外一些不会引发竞争条件的操作。在某些时候进程可能需要访问共享内存或共享文件,或执行另外一些会导致竞争的操作。我们把对共享内存进行访问的程序片段称作临界区。如果我们能够合理地安排,使得两个进程不可能同时处于临界区中,就能够避免竞争条件。

上述要求虽然可以避免竞争条件,但是还不能保证使用共享数据的并发进程能够正确和高效地进行协作。

一个良好的解决方案,应该包含下面四种条件:

  1. 任何时候两个进程不能同时处于临界区
  2. 不应该对CPU的速度和数量做任何假设
  3. 位于临界区外的进程不得阻塞其他进程
  4. 不能使任何进程无限等待进入临界区

为此,我们可以总结出访问临界资源应该遵循的四大原则:

  • 空闲让进:若无进程处于临界区时,应允许一个进程进入临界区。
  • 忙则等待:当已有进程进入临界区,其他进程必须等待。
  • 有限等待:应保证要求进入临界区的进程在有限时间内进入临界区。
  • 让权等待:当进程不能进入自己的临界区时,应释放处理机。

同步与互斥的实现

屏蔽中断

在单处理器系统上,最简单的解决方案是让每个进程在进入临界区后立即屏蔽所有中断,并在离开临界区之前重新启动它们。屏蔽中断后,时钟中断也会被屏蔽。CPU只有发生时钟中断或其他中断时才会进行进程切换。这样,在屏蔽中断后CPU不会切换到其他进程。所以,一旦某个进程屏蔽中断之后,它就可以检查和修改共享内存,而不用担心其他进程介入访问共享数据。

但是这并不是一个好的方案,因为把屏蔽中断的权力交给用户进程是不明智的。设想一下,若一个进程屏蔽中断后不再打开中断,结果会怎么样呢?整个系统可能会因此终止。当然,如果系统是多处理器,则屏蔽中断仅仅对执行disable指令的那个CPU有效。其他CPU仍将继续运行,并且可以访问共享内存。

另一方面,对于内核来说,当它在执行更新变量或列表的几条指令期间将中断屏蔽是很方便的。

总结来说,屏蔽中断对于操作系统本身来说是一项很有用的技术,但是把屏蔽中断的权力交给用户进程会导致灾难性后果。

软件方法实现互斥——互斥算法

假设有两个进程P0和P1互斥地共享某个临界资源。

  1. 算法一

    int turn=0;
    P0:{ 
           do {
                    while (turn!=0);
                    进程P0的临界区代码CS0 ;
                    turn=1 ;
                    进程P0的其他代码;
               } while (true)
         }
    P1:{ 
         do {
                  while (turn!=1);
                  进程P1的临界区代码CS1 ;
                  turn=0 ;
                  进程P1的其他代码;
            } while (true)
        }
    

此算法可以保证互斥访问临界资源,但两个进程必须以交替次序进入临界区。

此算法不能保证实现空闲让进准则。

  1. 算法二

    enum  boolean {false,true};
    boolean  flag[2]={false,false};
    P0:{
          do  {
                   while  (flag[1]);
                   flag[0]=true;
                   进程P0的临界区代码CS0 ;
                   flag[0]=false ;
                   进程P0的其他代码;}
          while(true)    }
    P1:{
          do  {
                   while ( flag[0]);
                   flag[1]=true;
                   进程P1的临界区代码CS1 ;
                   flag[1]=false ;
                   进程P1的其他代码;}
          while(true)    }

此算法解决了空闲让进的问题,但有可能两个进程同时进入临界区。

当两个进程都未进入临界区时,它们各自的访问标志值都为false,若此时刚好两个进程同时都想进入临界区,并且都发现对方标志值为false,于是两个进程同时进入了各自的临界区,这就违背了临界区的访问原则忙则等待。

  1. 算法三

    enum  boolean {false,true};
    boolean  flag[2]={false,false};
    P0:{
          do {             
                  flag[0]=true;
                  while  (flag[1]);
                  进程P0的临界区代码CS0 ;
                  flag[0]=false;
                  进程P0的其他代码;}
           while(true)   }
    P1:{
          do {             
                  flag[1]=true;
                  while  (flag[0]);
                  进程P1的临界区代码CS1 ;
                  flag[1]=false;
                  进程P1的其他代码;}
           while(true)   }
    

该算法可以有效地防止两个进程同时进入临界区,但存在两个进程都进不了临界区的问题。

当两个进程同时想进入临界区时,它们分别将自己的标志位设置为true,并且同时去检查对方的状态,发现对方也要进入临界区,于是双方互相谦让,结果谁也进不了临界区。

  1. 算法四

    enum  boolean {false,true};
    boolean  flag[2] ={false,false};   int turn;
    P0:{ 
         do  {                 
                  flag[0]=true;        turn=1;
                  while  (flag[1] && turn = = 1);
                  进程P0的临界区代码CS0 ;
                  flag[0]=false ;
                  进程P0的其他代码;}
          while (true)     }
    P1:{ 
         do  {                 
                  flag[1]=true;        turn=0;
                  while  (flag[0] && turn = = 0);
                  进程P1的临界区代码CS1 ;
                  flag[1]=false ;
                  进程P1的其他代码;}
          while (true)     }
    

TSL指令

一些计算机,特别是那些设计为多处理器的计算机,都会有下面这条指令:
TSL RX,LOCK
称为测试并加锁,它将一个内存字lock读到寄存器RX中,然后在该内存地址上存储一个非零值。读写指令能保证是一体的,不可分割的,一同执行的。在这个指令结束之前其他处理器均不允许访问内存。执行TSL指令的CPU会锁住内存总线,用来禁止其他CPU在这个指令结束之前访问内存。

很重要的一点就是锁住内存总线和屏蔽中断是不一样的。屏蔽中断并不能保证一个处理器在读写操作期间另一个处理器对内存的读写。而锁住内存总线可以做到屏蔽另一个处理器的影响。

为了使用TSL指令,要使用一个共享变量lock来协调对共享内存的访问。当lock为0时,任何进程都可以使用TSL指令将其设置为1,并读写共享内存。当操作结束时,内存使用move指令将lock的值重新设置为0。

使用TSL指令防止两个进程同时进入临界区的方案如下:

enter_region:
    TSL REGISTER,LOCK       |复制锁到寄存器并将锁设为1
    CMP REGISTER,#0         |锁是0吗?
    JNE enter_region        |若不是0,说明锁已被设置,所以循环
    RET                     |返回调用者,进入了临界区

leave_region:
    MOVE LOCK,#0            |在锁中存入0
    RET                     |返回调用者

还有一个可以替换TSL的指令是XCHG,它原子性的交换了两个位置的内容。代码如下:

enter_region:
    MOVE REGISTER,#1        |在寄存器中放一个1
    XCHG REGISTER,LOCK      |交换寄存器与锁变量的内容
    CMP REGISTER,#0         |锁是0吗?
    JNE enter_region        |若不是0,说明锁已被设置,所以循环
    RET                     |返回调用者,进入了临界区

leave_region:
    MOVE LOCK,#0            |在锁中存入0
    RET                     |返回调用者

锁机制

锁是一个代表资源状态的变量,通常用0表示资源可用(开锁),用1表示资源已被占用(关锁)。

在使用临界资源前需先考察锁变量的值,如果值为0则将锁设置为1(关锁),如果值为1则回到第一步重新考察锁变量的值。当进程使用完资源后,应将锁设置为0(开锁)。

上锁原语

lock(w)
 {
    while(w==1);
    w = 1;
 }

开锁原语

unlock(w)
 { 
     w = 0;
 }

用锁机制实现互斥

进程P1             进程P2
   ┆                ┆
 lock(w);         lock(w);
 临界区;           临界区;
 unlock(w);       unlock(w);
   ┆                ┆

信号量

信号量由两个成员(s,q)组成,其中s是一个具有非负初值的整型变量,q是一个初始状态为空的队列。又称信号灯。

信号量中的整型变量S表示系统中某类资源的数目。

  • 当其值大于0时,表示系统中当前可用资源的数目;
  • 当其值小于0时,其绝对值表示系统中因请求该类资源而被阻塞的进程数目。

改变信号量的值的方式有两种原子操作:

  • 一个是P 操作,这个操作会把信号量减去 -1,相减后如果信号量 < 0,则表明资源已被占用,进程需阻塞等待;相减后如果信号量 >= 0,则表明还有资源可使用,进程可正常继续执行。
  • 另一个是V 操作,这个操作会把信号量加上 1,相加后如果信号量 <= 0,则表明当前有阻塞中的进程,于是会将该进程唤醒运行;相加后如果信号量 > 0,则表明当前没有阻塞中的进程;

P操作

设S为一个信号量,P(S)执行时主要完成下述动作:
 S=S-1;
 if(S< 0) {设置进程状态为等待;
             将进程放入信号量等待队列;
             转调度程序;}

V操作:

V(S)执行时主要完成下述动作:
S=S+1;
if(S≤0){将信号量等待队列中的第一个进程移出;
         设置其状态为就绪状态并插入就绪队列;
         然后再返回原进程继续执行;}

P 操作是用在进入共享资源之前,V 操作是用在离开共享资源之后,这两个操作是必须成对出现的。

生产者-消费者问题为例,用信号量解决同步与互斥的方案如下:

#define N 100                  //缓冲区中的槽数目
typedef int semaphone;         //信号量是一种特殊的整形数据
semaphone mutex=1;             //控制对临界区的访问
semaphone empty=N;             //计数缓冲区的空槽数目
semaphone full=0;              //技术缓冲区的满槽数目

void producer(void)
{
    int item;

    while(true)
    {
        item=produce_item();    //产生放在缓冲区的一些数据
        down(&empty);           //将空槽数目减1
        down(&mutex);           //进入临界区
        insert_item(item);      //将新数据放入缓冲区中
        up(&mutex);             //离开临界区
        up(&full);              //将满槽的数目加1
    }
}

void consumer(void)
{
    int item;

    while(true)
    {
        down(&full);            //将满槽数目减1
        down(&mutex);           //进入临界区
        item=remove_item();     //从缓存区中取出数据项
        up(&mutex);             //离开临界区
        up(&empty);             //将空槽数目加1
        consume_item(item);     //处理数据项
    }
}

管程

信号量的同步操作分散在各进程中不便于管理,还可能导致系统死锁。如:生产者消费者问题中将P颠倒可能死锁。

为此Dijkstra于1971年提出:把所有进程对某一种临界资源的同步操作都集中起来,构成一个所谓的秘书进程。凡要访问该临界资源的进程,都需先报告秘书,由秘书来实现诸进程对同一临界资源的互斥使用。因而诞生了管程的概念。

Hansan为管程所下的定义是:管程定义了一个数据结构和能为并发进程所执行的一组操作,这组操作能同步进程和改变管程中的数据。

管程由以下部分构成:
  • 局部于管程的共享数据结构
  • 对共享数据结构进行操作的一组函数
  • 对局部于管程的数据设置初始值的语句
管程的基本语法为:
Monitor  monitor _name;/*管程名*/
variable  declarations;     /*共享变量说明*/
 P1(...)           /*对数据结构操作的函数*/
   { … }
 P2(...)
   { … }
         ┆
 Pn(...)
    { … }
{
     initialization code;     /*设初值语句*/
}
管程的基本特性:
  • 局部于管程的数据只能被局部于管程内的函数所访问。
  • 一个进程只有通过调用管程内的函数才能进入管程访问共享数据。
  • 每次仅允许一个进程在管程内执行某个函数。
  • 由于管程是一个语言成分,所以管程的互斥访问完全由编译程序在编译时自动添加上,无需程序员关心,而且保证正确。
条件变量

利用管程实现同步时,还应设置条件变量和在条件变量上进行操作的两个同步原语。

条件变量用于区别各种不同的等待原因。其说明形式为: condition x,y;

同步原语Cwait和Csignal。Cwait使调用进程等待,并将它排在相应的等待队列上;Csignal唤醒等待队列的队首进程。

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

  • 乐乐

    乐乐和向日葵占领头条 :eek:

    2021年3月6日