进程同步、进程互斥

什么是进程同步
什么是进程互斥

什么是进程同步

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

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据->读数据”的顺序来执行的。如何解决这种异步问题，就是“进程同步”所讨论的内容。

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

什么是进程互斥

进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的I/O设备)

两种资源共享方式
- 互斥共享方式
  - 系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。
- 同时共享方式
  - 系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问。

我们把一个时间段内允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区都属于临界资源。

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

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

do{
  entry section;  //进入区，负责检查是否可进入临界区，若可进入则应设置正在访问临界资源的标志(可理解为“上锁”)，以阻止其他进程同时进入临界区
  critical section; //临界区，访问临界资源的那段代码
  exit section; //退出区，负责解除正在访问临界资源的标志(可理解为“解锁”)
  remainder section;  //剩余区,做其他处理
}while(true)

注意：
- 临界区是进程中访问临界资源的的代码段。
- 进入区和退出区是负责实现互斥的代码段
- 临界区也可称为“临界区”。
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：
1. 空闲让忙。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2. 忙则等待。当已有进程进入临界区，其他试图进入临界区的进程必须等待
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)
4. 让权等待。当进程不能进入临界区，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法

单标志法
双标志先检查
双标志后检查
Peterson算法
学习提示：
1. 理解各个算法的思想、原理
2. 结合“实现互斥的四个逻辑部分”，重点理解各算法在进入区、退出区都做了什么
3. 分析各算法存在的缺陷(结合“实现互斥要遵循的四个原则”进行分析)

单标志法

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

双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0] = true意味着0号进程P0现在想进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

双标志先检查法的主要问题是：违反“忙则等待”原则。

原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

双标志后检查法

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各程序都长期无法访问临界资源而产生“饥饿”现象。

两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

Peterson算法

算法思想：如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。

其实是多设了一个标志位turn，P0时设turn=1，条件turn=0时进入临界区。P1时设turn=0，条件turn=1时进入临界区。当P1时间片用完后切回P0时，将会满足P0条件，从而进入临界区。

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是仍然未遵循让权等待的原则，

Peterson算法相较于之前三种软件解决方案来说，是最好的，但仍然不够好。

进程互斥的硬件实现方法

中断屏蔽方法
TestAndSet(TS指令/TSL指令)
Swap指令(XCHG指令)
学习提示
1. 理解各方法的原理
2. 了解各方法的优缺点

中断屏蔽方法

利用“开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

...
关中断;
临界区;
开中断;

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

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原来的值
}

while(TestAndSet(&lock));//“上锁”并“检查”
临界区代码段;
lock = false; //解锁
剩余代码段;

若刚开始lock是false，则TSL返回的old值为false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适合用于多处理机环境。
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用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;
剩余区代码段;

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在old变量上)，再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

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

信号量机制

整型信号量
记录型信号量

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

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、V操作。因此，做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)

整型信号量

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

与普通整数变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作

int S = 1;  //初始化整型信号量s，表示当前系统中可用的打印机资源数

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

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

...
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); //如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量S的等待队列(即阻塞队列)中
  }
}

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

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

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

用信号量机制实现进程互斥、同步，前驱关系

实现进程互斥
实现进程同步
实现进程的前驱关系

信号量机制实现进程互斥

分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就应放在临界区)
设置互斥信号量mutex，初值为1
在临界区之前执行P(mutex)
在临界区之后执行V(mutex)

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

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

//信号量机制实现互斥
semaphore mutex = 1;//初始化信号量

P1(){
  ...
  P(mutex); //使用临界资源的需要加锁
  临界区代码段...
  V(mutex); //使用临界资源后需要解锁
  ...
}

P2(){
  ...
  P(mutex);
  临界区代码段...
  V(mutex);
  ...
}

信号量机制实现进程同步

进程同步：要求各并发进程要求有序地推进。

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

semaphore S=0;

P1(){
  代码1;
  代码2;
  V(S);
  代码3;
}

P2(){
  P(S);
  代码4;
  代码5;
  代码6;
}

信号量机制实现前驱关系

其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)，因此：

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

互斥问题，信号量初值为1
同步问题，信号量初值为0
前驱关系问题，本质上就是更复杂的同步问题
除了互斥，同步问题外，还会考察有多个资源的问题，有多少资源就把信号量初值设为多少。申请资源时进行P操作，释放资源时进行V操作即可。

生产者消费者问题

问题描述

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

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

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

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

缓冲区是临界资源，各进程必须互斥地访问。

如何用信号量机制(P、V操作)实现生产者、消费者进程的这些功能呢？
- 信号量机制可实现互斥、同步、对一类系统资源的申请和释放。
- 互斥：设置初值为1的互斥信号量
- 同步：设置初值为0的同步信号量(实现“一前一后”)
- 对一类系统资源的申请和释放：设置一个信号量，初始值即为资源的数量(本质上也属于“同步问题”，若无空闲资源，则申请资源的进程需要等待别的进程释放资源后才能继续往下执行)
PV操作题目分析步骤：
1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
- 生产者每次要消耗(P)一个空闲缓冲区，并生产(V)一个产品。
- 消费者每次要消耗(P)一个产品，并释放一个空闲缓冲区(V)。
- 往缓冲区放入/取走产品需要互斥。
1. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

如何实现

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

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

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

缓冲区是临界资源，各进程必须互斥地访问。

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

producer(){
  while(1){
    生产一个产品;
    P(empty); //消耗一个空闲缓冲区
    P(mutex); //互斥
    把产品放入缓冲区;
    V(mutex);
    V(full);  //增加一个产品
  }
}

consumer(){
  while(1){
    P(full);  //消耗一个产品(非空缓冲区)
    P(mutex);
    从缓冲区取出一个产品;
    V(mutex); //增加一个空闲缓冲区
    V(empty);
    使用产品;
  }
}

实现互斥的P操作一定要再实现同步的P操作之后，否则可能会造成死锁！

多生产者—多消费者问题

问题描述

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

盘子看作大小为1，初始均空的缓冲区。

问题分析

分析高压包旭。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
整理思路。根据各晋城的操作流程确定P、V操作的大致顺序。
设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

互斥关系：
1. 对缓冲区(盘子)的访问要互斥地进行。
同步关系(一前一后)：
1. 父亲将苹果放入盘子后，女儿才能取苹果
2. 母亲将橘子放入盘子后，儿子才能取橘子
3. 只有盘子为空时，父亲或母亲才能放入水果

知识回顾与重要考点

总结：再生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

建议：在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。

PV操作题目的解题思路：
1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2. 整理思路。根据各进程的操作确定P、V操作的大致顺序。
3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

吸烟者问题

问题描述

假设一个系统有三个吸烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽调它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料在桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)

如何实现

semaphore offer1 = 0; //桌上组合一的数量
semaphore offer2 = 0; //桌上组合二的数量
semaphore offer3 = 0; //桌上组合三的数量
semaphore finish = 0; //抽烟是否完成
int i = 0;  //用于实现“三个抽烟者轮流抽烟”

provider(){
  while(1){
    if(i==0){
      将组合一放桌上;
      V(offer1);
    }else if(i==1){
      将组合二放桌上;
      V(offer2);
    }else if(i==2){
      将组合三放桌上;
      V(offer3);
    }
    i = (i+1)%3;
    P(finish);
  }
}

smoker1(){
  while(1){
    P(offer1);
    从桌上拿走组合一;
    卷烟;
    抽烟;
    V(finish);
  }
}

smoker2(){
  while(1){
    P(offer2);
    从桌上拿走组合二;
    卷烟;
    抽烟;
    V(finish);
  }
}

smoker3(){
  while(1){
    P(offer3);
    从桌上拿走组合三;
    卷烟;
    抽烟;
    V(finish);
  }
}

读者-写者问题

问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。

因此要求：
1. 允许多个读者可以同时对文件执行读操作
2. 只允许一个写者往文件中写信息
3. 任一写者在完成写操作之前不允许其他读者或写者工作
4. 写者执行写操作钱，应让已有的读者和写者全部退出

如何实现

semaphore rw = 1; //用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;    //记录当前有几个进程在访问文件
semaphore mutex = 1;  //用于保证对count变量的互斥访问

writer(){
  while(1){
    P(rw);  //写之前“加锁”
    写文件;
    V(rw);  //写之后“解锁”
  }
}

reader(){
  while(1){
    P(mutex); //各读进程互斥访问count
    if(count==0);
      P(rw);  //第一个读进程负责(加锁)
    count++;  //访问文件的读进程数+1
    V(mutex);
    读文件;
    P(mutex); //各读进程互斥访问count
    count--;
    if(count==0)
      V(rw);  //最后一个读进程负责“解锁”
    V(mutex);
  }
}

思考：若两个读进程并发执行，则两个读进程有可能先后执行P(rw)，从而使第二个读进程阻塞的情况。

如何解决：出现上述问题的原因在于对count变量的检查和复制无法一气呵成，因此可以设置另一个互斥信号量来保证各读进程对count的访问是互斥的。

semaphore rw = 1; //用于实现对文件的互斥访问
int count = 0;    //记录当前有几个读进程在访问文件
semaphore mutex = 1;  //用于保证对count变量的互斥访问
semaphore w = 1;  //用于实现“写优先”

writer(){
  while(1){
    P(w);
    P(rw);
    写文件;
    V(rw);
    V(w);
  }
}

reader(){
  while(1){
    P(w);
    P(mutex);
    if(count == 0)
      P(rw);
    count++;
    V(mutex);
    V(w);
    读文件;
    P(mutex);
    count--;
    if(count == 0)
      V(rw);
    V(mutex);
  }
}

哲学家进餐问题

问题描述

一张圆桌上坐着5名哲学家，没两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析

semaphore chopstick[5]={1,1,1,1,1};

Pi(){ //i号哲学家的进程
  P(chopstick[i]);  //拿左
  P(chopstick[(i+1)%5]);  //拿右
  吃饭;
  V(chopstick[i]);  //放左
  V(chopstick[(i+1)%5]);  //放右
  思考;
} //但是如果所有哲学家同时拿起筷子，就会循环等待其他人放下

如何预防死锁的发生呢？
1. 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
3. 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1;  //互斥地取筷子

Pi(){
  while(1){
    P(mutex);
    P(chopstick[i]);  //拿左
    P(chopstick[(i+1)%5]);  //拿右
    V(mutex);
    吃饭;
    V(chopstick[i]);  //放左
    V(chopstick[(i+1)%5]);  //放右
    思考;
  }
}

//各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一般时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

管程

为什么要引入管程
管程的定义和基本特征
拓展1：用管程解决生产者消费问题
拓展2：Java中类似于管程的机制

为什么要引入管程

信号量机制存在的问题：编写程序困难，易出错。

因此设计一种机制，让程序员写程序时不需要再灌注复杂的PV操作，让写代码更轻松。

管程的定义和基本特征

管程时一种特殊的软件模块，有这些组成部分：
1. 局部于管程的共享数据结构说明
2. 对该数据结构进行操作的一组过程
3. 对局部于管程的共享数据设置初始值的语句
4. 管程有一个名字

跨考Tips:“过程”其实就是“函数”

管程的基本特征：
1. 局部于管程的数据只能被局部于管程的过程所访问
2. 一个进程只通过管程内的过程才能进入管程访问共享数据
3. 每次仅允许一个进程在管程内执行某个内部过程

拓展1：用管程解决生产者消费者问题

monitor ProducerConsumer
  condition full,empty; //条件变量用来实现同步(排队)
  int count=0;//缓冲区中的产品数
  void insert(Item item){ //把产品item放入缓冲区
    if(count == N)
      wait(full);
    count++;
    insert_item(item);
    if(count == 1)
      signal(empty);
  }
  Item remove(){  //从缓冲区取出一个产品
    if(count == 0)
      wait(empty);
    count--;
    if(count == N-1)
      signal(full);
    return remove_item();
  }
end monitor;

//生产者进程
producer(){
  while(1){
    item = 生产一个产品;
    ProdecerConsumer.insert(item);
  }
}

consumer(){
  while(1){
    item = ProdecerConsumer.remove();
    消费产品item;
  }
}

由编译器负责实现进程互斥地进入管程中的过程。
管程中设置条件变量和等待唤醒操作，以解决同步问题。
引入管程的目的无非就是要更方便地实现进程互斥和同步
1. 需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2. 需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数(如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
3. 只有通过这些特定的“入口”才能访问共享数据
4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心)
5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时，该进程应先释放管程的使用权，也就是让出“入口”)；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

拓展2：Java中类似于管程的机制

Java中，如果用关键字synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用

static class monitor{
  private Item buffer[]=new Item[N];
  private int count = 0;

  public synchronized void insert(Item item){
    ...
  }
}

每次只能有一个进程进入insert函数，如果多个线程同时调用insert函数，则后来者需要排队等待

为什么要引入管程
- 解决信号量机制编程麻烦、易出错问题
组成
- 共享数据结构
- 对数据结构初始化的语句
- 一组用来访问数据结构的过程(函数)
基本特征
- 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程
补充
- 各进程必须互斥地访问管程的特性是由编译器实现的
- 可在管程中设置条件变量及等待/唤醒操作以解决同步问题

进程同步、进程互斥

什么是进程同步

什么是进程互斥

进程互斥的软件实现方法

单标志法

双标志先检查法

双标志后检查法

Peterson算法

进程互斥的硬件实现方法

中断屏蔽方法

TestAndSet指令

Swap指令

信号量机制

整型信号量

记录型信号量

用信号量机制实现 进程互斥、同步，前驱关系

信号量机制实现进程互斥

信号量机制实现进程同步

信号量机制实现前驱关系

生产者消费者问题

问题描述

如何实现

多生产者—多消费者问题

问题描述

问题分析

知识回顾与重要考点

吸烟者问题

问题描述

如何实现

读者-写者问题

问题描述

如何实现

哲学家进餐问题

问题描述

问题分析

管程

为什么要引入管程

管程的定义和基本特征

拓展1：用管程解决生产者消费者问题

拓展2：Java中类似于管程的机制

用信号量机制实现进程互斥、同步，前驱关系