进程同步与互斥

进程同步与互斥

1.概念

1.进程异步性

进程具有异步性，各并发执行的进程以各自独立的、不可预知的速度向前推进

2.进程同步

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

3.进程互斥

1.临界资源

我们把一个时间段内只允许一个进程使用的资源称为临界资源。

如：摄像机、打印机、变量、数据缓冲区等等

2.对临界资源的访问，必须互斥的进行。

3.互斥

亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源

4.对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

1）进入去（上锁）

2）临界区（用于访问临界区的那段代码）

3）退出去（解锁）

4）剩余区

5.为了实现互斥访问，需遵循一下原则

2.进程互斥实现

1.单标执法

1.算法思想

两个进程在访问完临界区后，会把使用临界区的权限转交给另一个进程。也就是临界区只能有一个进程

2.代码

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

//P0进程
while(turn != 0);   //进入去；进程号不等于0，一直等待
critical section;   //临界区
turn = 1;                        //退出去
remainder section;    //剩余区

//p1进程
while(turn != 1);        //进程号不等于1，一直等待
critical section;
turn = 1;
remainder section;

分析：初始值turn = 0；所以p0进入临界区，p1一直等待，直到p0在退出去将turn 改为1时，p1才会进入临界区

缺点：即使临界区是空闲的，若p0不进入临界区，则p1一直等待，违背了空闲让进原则

2.双标志先检查法

1.算法思想

设置一个bool类型的数据flag[]，数组中各个元素用来标记各进程想进入临界区的意愿；

比如flag[0] = true，表示P0想进入临界区。

每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身的对应表示flag[i] = true;之后开始访问。

2.代码

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

//p0进程
while(flag[1]);              //如果此时P1想进入，则p0等待   检查
flag[0] = true;                //标记为 p0想进入临界区        上锁
critical section;            //访问临界区
flag[0] = false;            //访问完，将标记修改为不想使用临界区
remainder section;

//p1进程
while(flag[0]);              //如果此时P0想进入，则p1等待
flag[1] = true;                //标记为 p1想进入临界区    
critical section;            //访问临界区
flag[1] = false;            //访问完，将标记修改为不想使用临界区
remainder section;

3.缺点

1）进程异步执行，如果在循环的部分，发生了进程切换，则会导致p0和p1的falg均为true，所以导致两个进程同时访问临界区；违背了忙则等待的原则

2）产生原因是，进入去的检查和上锁两个操作不是一气呵成的，所以可能导致检查后，上锁前发生进程切换，导致同时访问临界区

3.双志后检查

1.算法思想

对双标志先检查法的改进，先上锁，后检查

2.代码

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

//p0进程
flag[0] = true;                //标记为 p0想进入临界区        上锁
while(flag[1]);              //如果此时P1想进入，则p0等待   检查
critical section;            //访问临界区
flag[0] = false;            //访问完，将标记修改为不想使用临界区
remainder section;

//p1进程
flag[1] = true;                //标记为 p1想进入临界区    
while(flag[0]);              //如果此时P0想进入，则p1等待
critical section;            //访问临界区
flag[1] = false;            //访问完，将标记修改为不想使用临界区
remainder section;

3.分析

进程是并发执行的，如果在检查前，先上锁，则有可能发生，两个进程都想进入临界区，将标记为设为true，从而导致两个进程都进入不了临界区的情况出现，违背了空闲让进，有限等待原则

会出现饥饿的现象

4.Peterson算法

1.算法思想

双标志后检查法，两个进程都想进入临界区，谁也不让谁，最后谁都进入不了。Peterson算法中，主动让对方先使用临界区

2.代码

bool flag[2];                //表示进入临界区意愿的数组，初始化值false
int turn = 0;                //表示优先让那个进程进入临界区

//p0进程
flag[0] = true;                                //进入区    p0想进入
turn = 1;                                            //进入区 让p1先进
while(flag[1] && trun == 1);    //进入区 如果p1想进，则p0等待
critical section;            //访问临界区
flag[0] = false;            //访问完，将标记修改为不想使用临界区
remainder section;

//p1进程
flag[1] = true;                                //进入区    p1想进入
turn = 0;                                            //进入区 让p0先进
while(flag[0] && trun == 1);    //进入区 如果p0想进，则p1等待
critical section;            //访问临界区
flag[0] = false;            //访问完，将标记修改为不想使用临界区
remainder section;

3.分析

如果两个进程都想进入临界区，则flag均为true，刚开始都谦让对方，所以两个进程都会循环等待，直到时间片用完，因为p1随后执行的过程中说愿意让给p0执行，则p0重新进入处理机运行时，发现turn = 0，所以不会等待，直接进入临界区。p0执行完毕后p1即可正常执行。

谦让过程只会执行一次：

p0：我想用临界区

P1：我想用临界区

p0：你先吧

P1：你先吧

P0：好，我先

4.缺点

遵循了空闲让进、忙则等待、有限等待三个原则，但是没有遵循让权等待原则

3.进程互斥的硬件实现方法

1.中断屏蔽方法

1、利用”开/关中断指令"实现

2、与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况。

3、优点：简单高效

4.缺点：不适用多处理剂；（关中断只能使得一个cpu不能进程切换，别的进程同样可以，如果别的cpu也要进入临界区，则会出错）

只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态）

2.TestAndSet指令

简称TS指令，或TSL指令

1、TSL使用硬件实现，执行的过程不允许被中断，只能一气呵成。

2、伪代码描述如下：硬件实现可以使得检查和上锁一气呵成。适用于多处理机。

//bool型lock表示当前临界区是否被加锁
//true表示已加锁false未加锁
bool TestAndSet(bool *lock){
  bool old;
  old = *lock;        //old用来存放原来的lock值
  *lock = true;        //无论之前是否加锁，都将lock设置为true
  return old;
}

bool lock = false;
//使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock));       //上锁并检查
临界区代码……
lock = false;       //解锁
剩余代码段……

3、优点：实现简单、适用于多处理机

4、缺点：不满足让权等待原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致”忙等“

3.Swap指令

1、有的地方称为Exchange指令或简称XCHG指令

2、Swap通过硬件实现，执行的过程不能被中断，只能一气呵成

3、伪代码描述如下：

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

//以下是使用Swap实现互斥的算法逻辑
//lock  表示当前临界区是否被加锁
bool lock = false;
//old保存lock的值，为false表示之前没有别的进程对临界区上锁
//old初始值为true，需要检查lock的值，而后加锁，lock = true
bool old = true;
while(old == true){
  Swap(&lock, &old);
}
临界区代码……
lock = false;       //解锁
剩余代码段……

4、优点：实现简单、适用于多处理机

5、缺点：不满足让权等待原则，暂时无法进入临界区的进程会占用CPU并循环执行Swap指令，从而导致”忙等“

4.信号量机制

用户可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

1.概念

1、信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量。

2、可以通过操作系统提供的一对原语对信号量进行操作。wait（s)原语和signal（S）原语。通常简称为PV操作。

2.整形信号量

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

int S = 1; //初始化整形信号量为1，表示当前系统中打印机的数量

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

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

//eg：

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


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

2.分析

1）检查和上锁一气呵成，避免了并发、异步导致的问题

2）存在的问题：不满足”让权等待“的原则，会发生忙等

3.记录型信号量

1.用记录型数据结构表示的信号量

2.代码

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

/*某进程需要使用资源时，通过wait原语申请*/
void wait(semaphore S){
  S.value--;
  if(S.value < 0){
    block(S.L);     //如果剩余资源不够，使用block原语将进程从运行态进入阻塞态，并把它挂到信号量S的等待队列中
  }
}

/*进程使用完资源后，通过signal原语释放*/
void signal(semaphore S){
  s.value++;
  if(S.value <= 0){
    wakeup(S.L);     //如果释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态
  }
}

3.例子

4.分析

1）对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value --，表示资源数减一；当S.value < 0 时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞（当前运行的进程从运行态进入就绪态），主动放弃处理机，并插入该类资源的等待队列S.L中。可见，该机制遵循了”让权等待"的原则，不会出现"忙等"的现象。

2）对信号量的一次V操作意味着进程需要释放一个单位的该类资源，因此需要执行S.value++，表示资源数+1，若加1后仍然是S.value <= 0,表示已让有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程（被唤醒的进程从阻塞态到就绪态)

5.通过信号量实现进程同步与互斥

1.信号量机制实现进程互斥

1.分析并发进程的关键活动，划分临界区

2.设置互斥信号量mutex，初值为1

3.在临界区之前执行P（mutex）

4.在临界区之后执行V（mutex）

5.注意：

1）对不同的临界资源需要设置不同的互斥信号量

2）P、V操作必须成对出现。缺少P就不能保证临界资源的会吃访问。缺少V会导致资源永久不被释放，等待进程永远不会被唤醒

2.信号量机制实现进程同步

1.程序执行的异步性，导致程序的运行顺序不确定。但在特定的场景下，我们必须保证程序的顺序执行；例如，P2进程执行需要P1的输出，因此，必须保证P1先于P2执行

2.分析什么地方需要实现“同步关系”，即保证“一前一后”执行的两个操作

3.设置同步信号量S，初始值为0

4.在“前操作”之后执行V操作

5.在“后操作”之前执行P操作

3.信号量机制实现前驱关系

1.如下图

6.生产者消费者问题

1.问题

1、系统中有一组生产者和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。

2、生产者、消费者共享一个初始为空、大小为n的缓冲区

3、只用缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待

4、只有缓冲区不空时，消费者才能从中取出产品，否则必须等待

2.分析

1、缓冲区是临界资源、各进程必须互斥的访问

2、生产者和消费者有同步关系

1）生产者生产后才能消费（缓冲区未空）

2）消费者消费了之后才能生产（缓冲区未满）

3、为每对关系设置信号量

semaphore mutex = 1;    //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;    //同步信号量，表示空闲缓冲区的数量
semaphore full = 0;        //同步信号量，表示产品的数量，非空缓冲区的数量

3.代码

semaphore mutex = 1;    //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;    //同步信号量，表示空闲缓冲区的数量
semaphore full = 0;        //同步信号量，表示产品的数量，非空缓冲区的数量

//生产者
producer(){
  生产一个产品……
  P(empty);   
  P(mutex);
  把产品放入缓冲区……
  V(mutex);
  V(full);
}

//消费者
consumer(){
  消费一个产品……
  P(full);
  P(mutex);
  从缓冲区取出一个产品
  V(mutex);
  V(empty);
  使用产品……
}

注意：

1）实现互斥的P操作一定要放在实现同步的P操作之后。否则会发生死锁现象

2）V操作不会导致进程阻塞，因此两个V操作顺序可以交换

3）生产产品、使用产品的相关操作，如果放到PV里面，则会导致程序的并发度降低，所以，灭必要将无关代码放到PV里面

4.总结

7.多生产者-多消费者问题

1.问题

2.分析

1、互斥关系：对缓冲区（盘子）的访问需要互斥的进行

2、同步关系（一前一后）：

1）父亲将苹果放到盘子后，女儿才能取到苹果

2）母亲将橘子放到盘子后，儿子才能取到橘子

3）只有盘子为空时，父亲或母亲才能放入水果

3、关系下图

3.如何实现

1.四个信号量实现方式

2.三个信号量实现方式

1）不使用互斥信号量

2）注意：

本题可以不使用互斥信号量的原因：本题中缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1，因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。

如果盘子（缓冲区）的容量为2，则必须设置一个互斥信号量来保证缓冲区的互斥访问，以避免数据覆盖的情况出现

3.总结

8.吸烟者问题

1.问题

2.分析

1.桌子可以抽象为容量为1的缓冲区，要互斥的访问（将两种材料看成一种组合）

2.如下图

3.如何实现

9.读写者问题

1.问题

1、读共享，写互斥；

2.分析

3.如何实现（默认读优先）

4.如何实现（写优先）

5.总结

10.哲学家进餐问题

1.问题描述

2.分析

同时持有两个临界资源才能正常执行

只有互斥关系，没有同步关系

3.如何实现,避免死锁的发生

1.两种方案：

2.方案三：仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子

3.总结

11.管程

1.为什么要引入管程

1、信号量机制存在的问题：辨析程序困难、易出错

2、设计一种机制，让程序员写程序的时候不需要再关注复杂的PV操作，让写代码更加轻松，从而引出了管程机制；管程是一种高级的同步机制。

2.管程的定义

管程是一种特殊的软件模块，有以下组成部分：

1、局部于管程的共享数据结构说明；

2、对该数据结构进行操作的一组过程；

3、对局部与管程的共享数据设置初始值的语句；

4、管程有一个名字

3.管程的基本特征

1、局部与管程的数据只能被局部与管程的过程所访问

2、一个进程只有通过调用管程内的过程才能进入管程访问共享数据；

3.每次仅允许一个进程在管程内执行某个内部过程。

注意：管程的定义和特征类似于类

4.使用管程实现生产者消费者问题

类似于将同步过程封装成类，由编译器负责实现各进程互斥地进入管程中的过程。

如下图所示

5.Java中类似管程的机制

Java中，关键字synchronized描述的函数，同一时间段只能被一个进程或线程访问