计算机操纵系统——进程同步、互斥及信号量机制

进程同步，互斥及信号量机制

进程同步

• 同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。进程之间的相互制约关系就是源于它们之间的相互合作。

进程互斥

• 一段时间内只允许一个程序使用的资源成为临界资源
• 对临界资源的访问，必须互斥的进行，互斥亦称间接制约关系。
• 进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

  do{
      enter section;      //进入区：复制检查是否可以进去临界区，若可进入，设置正在访问临界资源的标志，以阻止其他进程进入
      critical section;   //临界区：访问临界资源的那段代码
      exit section;       //退出区：负责解除正在访问临界资源的标志
      remainder section;  //剩余区
  }
  

  • 注：临界区是进程中访问临界资源的代码段。
    进入区和退出区是负责实现互斥的代码段。
    临界区也可称为“临界段”
• 遵循原则

进程互斥的软件实现方法

单标志法

• 算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予

int turn = 0    //trun表示当前允许进入临界区的进程号

p0进程：                            p1进程：
while(trun != 0);                   while(trun != 1);   //进入区
critical section;                   critical section;   //临界区
trun = 1;                           trun = 0;           //退出区
remainder section;                  remainder section;  //剩余区

• 该算法可以实现“同一时刻最多只允许一个进程访问临界区”
• 问题：违背“空闲让进”原则

双标志先检查法

• 算法思想：设置一个布尔型数组flag[]，数组中各元素用来标记各进程想进入临界区的意愿

bool flag[2];       //表示进入临界区意愿的数组
flag[1] = false;
flag[2] = false;    //刚开始设置两个进程都不想进入临界区

p0进程：                            p1进程：
while(flag[1]);                     while(flag[0]);   //如果此时p0想进入临界区，p1就一直匈奴换等待
flag[0] = true;                     flag[1] = true;     //标记为p1进程想要进入了临界区
critical section;                   critical section;   //访问临界区
flag[0] = false;                    flag[1] = false;    //访问完临界区，修改标记为p1不想使用临界区
remainder section;                  remainder section;  //剩余区

• 问题：违反了“忙则等待”原则，原因是，进入区的“检查”和“上锁”两个处理不是一气呵成的，“检查后”，“上锁”前可能发生进程切换。

双标志后检查法

bool flag[2];       //表示进入临界区意愿的数组
flag[1] = false;
flag[2] = false;    //刚开始设置两个进程都不想进入临界区

p0进程：                            p1进程：
flag[0] = true;                     flag[1] = true;     //标记为p1进程想要进入了临界区
while(flag[1]);                     while(flag[0]);   //如果此时p0想进入临界区，p1就一直匈奴换等待
critical section;                   critical section;   //访问临界区
flag[0] = false;                    flag[1] = false;    //访问完临界区，修改标记为p1不想使用临界区
remainder section;                  remainder section;  //剩余区

• 解决了“忙则等待”的问题，但有违背了“空闲让进”和“有限等待”原则。会因各进程都长期无法访问临界资源而产生“饥饿”现象。

Peterson算法

• 算法思想：如果双方都想进入临界区，可以主动让对方想使用临界区

bool flag[2];
int turn = 0;   //表示优先让哪个进程进入临界区

p0进程：
flag[0] = true;
turn = 1;
while(flag[1] && turn==1);
critical section;
flag[0] = false;
remainder section;

p1进程：
flag[1] = true;             //表示自己想进入临界区
turn = 0;                   //可以优先让对方进入临界区
while(flag[0] && turn==0);  //对方想进，且最后一次是自己让，那就自己循环等待
critical section;
flag[1] = false;            //访问完临界区，表示自己已经不想访问临界区了
remainder section;

• 进入区：
  • 主动争取
  • 主动谦让
  • 检查对方是否也想使用，且最后一次是不是自己说了“客气话”
• Peterson算法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但未遵循让权等待原则

进程互斥的硬件实现方法

中断屏蔽方法

• 利用“开/关中断指令”实现

关中断； //指不允许当前进程被中断，也必然不会发生进程切换
临界区；
开中断；

• 优点：简单、高效
• 缺点：不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果让用户随意使用会很危险）

TestAndSet指令

• 简称TS指令，有的也称TestAndSetLock指令，或TSL指令
• TSL指令是用硬件实现的，执行过程不允许被中断，只能一气呵成

//布尔值共享变量lock表示当前临界区是否被加锁
//true表示已加锁，false表示未加锁
bool TestAndSet (bool *lock){
    bool old;
    old = *lock;    //old存放lock以前的值
    *lock = true;   //无论之前是否加锁，都将lock设为true
    return old;     //返回lock原来的值
}

//以下是使用TSL实现互斥的算法逻辑
while(TestAndSet (&lock));  //"上锁"并“检查”
临界区代码段。。。
lock = false;               //解锁
剩余区代码段。。。

• 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境
• 缺点：不满足“让权等待”原则，暂时无法进入临界区的程序会占用CPU并循环执行TSL指令，从而导致“忙等”

Swap指令

• 有的地方也叫Exchange指令，或XCHG指令
• Swap指令是用硬件实现的，执行过程不允许被中断，只能一气呵成

//Swap指令的作用是交换两个变量的值
Swap(bool *a,bool *b){
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//以下是用Swap指令实现互斥指令的算法逻辑
//lock表示当前临界区是否被加锁
bool old = true;
while(old == true)
    Swap(&lock,&old);
临界区代码段。。。
lock = false;
剩余区代码段

• 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境
• 缺点：不满足“让权等待”原则，暂时无法进入临界区的程序会占用CPU并循环执行TSL指令，从而导致“忙等”

信号量机制

概念

• 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作。从而很方便的实现了进程互斥、进程同步
• 信号量其实就是一个变量（可以是整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量
• 一对原语：wait(S)原语和signal(S)原语，简称为P(S),V(S)

整型信号量

• 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

某计算机系统中有一台打印机
int S = 1;

void wait(S){       //相当于进入区
    while(S <= 0);  //如果资源不够，就一直循环等待
    S=S-1;          //如果资源数够，就占用一个资源
}

void signal(S){     //相当于退出区  
    S=S+1;          //使用完资源后，在退出区释放资源
}

进程p0
wait(S)                 //进入区，申请资源
使用打印机资源。。。    //临界区，访问资源
signal(S)               //退出区，释放资源

• 问题：不满足“让权等待”原则，会发生“忙等”

记录型信号量

/*记录型信号量的定义*/
typedef struct{
    int value;          //剩余资源数
    struct process *L;  //等待队列
    
}semaphore;

/*某进程需要使用资源时，通过wait原语申请*/
void wait(semaphore S){
    S.value--;
    if(S.value < 0){
        block(S.L);
    }
}

/*进程使用完资源后，通过signal原语释放 */
void signal(semaphore S){
    s.value++;
    if(S.value <=0){
        wakeup(S.L);
    }
}

• P操作若执行block，则进程从运行态->阻塞态
• v操作若执行wakeup，进程从阻塞态->就绪态

信号量机制实现进程互斥

1. 分析并发过程的关键活动，划定临界区
2. 设置互斥信号量mutex，初值为1
3. 在临界区之前执行P(mutex)
4. 在临界区之后执行V(mutex)

• 注：对不同的临界资源需要设置不同的互斥信号量
• P、V操作必须成对出现

信号量机制实现进程同步

1. 分析什么地方需要实现“进程同步”，即必须保证“一前一后”执行的两个操作
2. 设置同步信号量S,初值为0
3. 在“前操作”之后执行V(S)
4. 在“后操作”之前执行P(S)

信号量机制实现前驱关系

1. 要为每一对前驱关系各设置一个同步变量
2. 在“前操作”之后相对于的同步变量执行V操作
3. 在“后操作”之后相对于的同步变量执行P操作