2.3 同步与互斥

2.3 进程的同步与互斥

1. 进程同步、进程互斥

1.1 什么是进程同步?

• 进程具有异步性的特征
  • 异步性: 各并发执行的进程以各自独立的、不可预知的速度向前推进
• 如何解决这种异步问题，就是“进程同步”所讨论的内容
  • 同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作

1.2 什么是进程互斥?

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

• 我们把一个时间段内只允许一个进程使用(互斥共享方式)的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有很多变量、数据、内存缓冲区等都属于临界资源，对临界资源的访问，必须互斥地进行

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

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

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

• 注意:

  • 临界区是进程中访问临界资源的代码段
  • 进入区和退出区是负责实现互斥的代码段
  • 临界区也可称为"临界段"

• 为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:

  • 空闲让进: 临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
  • 忙则等待: 当已有进程进入临界区时，其他试图进入临界区的进程必须等待
  • 有限等待: 对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)
  • 让权等待: 当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

2. 进程互斥的软件实现方法

2.1 学习提示:

1. 理解各个算法的思想、原理

2. 结合上小节学习的“实现互斥的四个逻辑部分”，重点理解各算法在进入区、退出区都做了什么

3. 分析各算法存在的缺陷(结合"实现互斥要遵循的四个原则"进行分析)

2.2 单标志法

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

int turn = 0; // turn 表示当前允许进入临界区的进程号
// P0进程:                            //P1进程:
while (turn != 0);  ①                while (turn != 1); ⑤   // 进入区
critical section;   ②                critical section;  ⑥   // 临界区
turn = 1;           ③                turn = 0;          ⑦   // 退出区
remainder section;  ④                remainder section; ⑧   // 剩余区

• turn的初值为0，即刚开始只允许0号进程进入临界区
• 若P1先上处理机运行，则会一直卡在⑤，直到P1的时间片用完，发生调度，切换P0上处理机运行。若代码①不会卡住P0，P0可以正常访问临界区，则P0访问临界区期间即使切换回P1，P1依然会卡在⑤
  • 因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”
• 只能按P0 → P1 → P0 → P1 → ...... 这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问
  • 因此，单标志法存在的主要问题是: 违背“空闲让进”原则

2.3 双标志先检查

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

bool flag[2]; 		// 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = 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;

• 若按照①⑤②⑥③⑦......的顺序执行，P0和P1将会同时访问临界区

• 因此，双标志先检查法的主要问题是: 违反“忙则等待”原则

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

2.4 双标志后检查

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

bool flag[2];   // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = 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;  

• 若按照①⑤②⑥......的顺序执行，P0和P1将都无法进入临界区
• 因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区

2.5 Peterson算法

• 算法思想：结合双标志法、单标志法的思想，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”(谦让)，做一个有礼貌的进程

bool flag[2]; // 表示进入临界区意愿的数组, 初始值都是false

int turn = 0; // turn 表示优先让哪个进程进入临界区

// P0进程:					//P1进程:
flag[0] = true; 	①		flag[1] = true; ⑥ // 进入区, 表示自己想进入临界区
turn = 1;			②		turn = 0;⑦ // 进入区, 可以优先让对方进入临界区

while (flag[1] &&			while (flag[0] &&
       turn == 1);	③	 	turn == 0); ⑧ //进入区，对方想进, 且最后一次是自己"让梨", 那自己就循环等待

critical section;	④ 		critical section; ⑨ // 访问临界区
flag[0] = false;	⑤		flag[1] = false; ⑩ // 访问完临界区，表示自己已经不想访问临界区了
remainder section;			remainder section;

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

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

3.1 中断屏蔽方法

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

关中断; // 关中断后即不允许当前进程被中断，也必然不会发生进程切换
临界区;
开中断; // 直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区

• 优点: 简单、高效

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

  • 因为关中断只针对单个处理机，其他处理机上的进程还是能够访问临界区

3.2 TestAndSet指令

• 简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令

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

• 以下是用C语言描述的逻辑:

// 布尔型共享变量 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;				// "解锁"
剩余区代码段...

• 原理:

  • 若刚开始 lock 是 false，则 TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区
  • 若刚开始 lock 是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”
  • 相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作

• 优点: 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

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

3.3 Swap指令

• 有的地方也叫 Exchange 指令，或简称 XCHG 指令

• Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成

• 以下是用C语言描述的逻辑:

// 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指令，从而导致“忙等”。

4. 互斥锁

• 解决临界区最简单的工具就是互斥锁(mutex lock)。
  • 一个进程在进入临界区时应获得锁;在退出临界区时释放锁。
  • 函数acquire()获得锁，而函数release()释放锁。
• 每个互斥锁有一个布尔变量available,表示锁是否可用。如果锁是可用的，调用acqiure()会 成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

acquire(){
	while(!available)
        ;				//忙等待
	available false;	//获得锁
}
release(){
	available true; 	//释放锁
}

• acquire(或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

• 互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须 连续循环调用acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常 用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

• 需要连续循环忙等的互斥锁，都可称为自旋锁(spin lock),如TSL指令、swap指令、单标志法

• 特性：

  • 需忙等，进程时间片用完才下处理机，违反“让权等待”
  • 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
  • 不太适用于单处理机系统，忙等的过程中不可能解锁

5. 信号量机制

5.1 之前学习的这些进程互斥的解决方案分别存在哪些问题?

• 进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法）

• 进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）

  • 在双标志先检查法中，进入区的“检查”、“上锁” 操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题
  • 所有的解决方案都无法实现“让权等待”

• 1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法 -- 信号量机制

5.2 信号量机制

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

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

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

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

• wait、signal 原语常简称为 P、V操作（来自荷兰语 proberen 和 verhogen）。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)

5.3 整型信号量

• 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量
  • 与普通整数变量的区别：对信号量的操作只有三种，即 初始化、P操作、V操作
• 检查”和“上锁”一气呵成，避免了并发、异步导致的问题
• 存在的问题：不满足“让权等待”原则，会发生“忙等”
• Eg ：某计算机系统中有一台打印机:

int S=1；//初始化整型信号量s,表示当前系统中可用的打印机资源数
void wait(int S){	//wait原语，相当于"进入区"
    while (S < 0);  //如果资源数不够，就一直循环等待
    S = S-1;    	//如果资源数够，则占用一个资源
}

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

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

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

5.4 记录型信号量

• 整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

• 在考研题目中 wait(S)、signal(S) 也可以记为 P(S)、V(S)，这对原语可用于实现系统资源的“申请”和“释放”

• S.value 的初值表示系统中某种资源的数目

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

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

6. 用信号量实现进程互斥、同步、前驱关系

6.1 Tips:

• 不要一头钻到代码里，要注意理解信号量背后的含义，一个信号量对应一种资源

• 信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）

• P( S ) -- 申请一个资源S，如果资源不够就阻塞等待

• V( S ) -- 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程

6.2 信号量机制实现进程互斥

• 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区)
• 设置互斥信号量mutex,.初值为1
  • 在进入区P(mutex)一一申请资源
  • 在退出区V(mutex)一一释放资源
• 注意：对不同的临界资源需要设置不同的互斥信号量。
• P、V操作必须成对出现。
  • 缺少P(nutex)就不能保证临界资源的互斥访问。
  • 缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

6.3 信号量机制实现进程同步

• 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码)
• 设置同步信号量S,初始为0
• 在“前操作”之后执行V(S)
• 在“后操作”之前执行P(S)
  • 技巧口诀：前V后P

6.4 信号量机制实现前驱关系

• 其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作）因此，
  • 要为每一对前驱关系各设置一个同步信号量
  • 在“前操作”之后对相应的同步信号量执行V操作
  • 在“后操作”之前对相应的同步信号量执行P操作

7. 生产者-消费者问题

7.1 问题描述:

• 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用（注：这里的“产品”理解为某种数据）

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

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

  • 缓冲区没满→生产者生产，缓冲区满时，生产者必须等待

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

  • 缓冲区没空→消费者消费，缓冲区空时，消费者必须等待

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

  • 互斥关系

7.2 PV操作题目分析步骤:

• 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系
• 整理思路。根据各进程的操作流程确定P、V操作的大致顺序
• 设置信号量。并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初

始值要看对应资源的初始值是多少）

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); // 增加一个空闲缓冲区
        使用产品;
    }
}

• ②③④: 实现互斥是在同一进程中进行一对PV操作

• ⑤⑥: 实现两进程的同步关系，是在其中一个进程中执行P，另一进程中执行V

• 实现互斥的P操作一定要在实现同步的P操作之后

  • 若将该题中producer和consumer内的两个P操作交换，刚开始时若按⑦→⑥(此时由于full==0，消费者进程阻塞)→②(此时由于消费者消费了mutex，mutex==0，生产者进程阻塞)，导致死锁的发生

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

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

8.1 问题描述:

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

• 互斥关系（mutex = 1）:

  • 对缓冲区（盘子）的访问要互斥地进行

• 同步关系（一前一后）:

  • 父亲将苹果放入盘子后，女儿才能取苹果
  • 母亲将橘子放入盘子后，儿子才能取橘子
  • 只有盘子为空时，父亲或母亲才能放入水果
    • “盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果

• 此题中可以删去mutex，即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象，原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。因此在任何时刻， 最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…

• 总结:

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

• 建议:

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

9. 吸烟者问题

问题描述:

• 假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）
  • 组合一：纸+胶水
  • 组合二：烟草+胶水
  • 组合三：烟草+纸
• 互斥关系:
  • 桌子可以抽象为容量为1的缓冲区，要互斥访问
• 同步关系（从事件的角度来分析）:
  • 桌上有组合一 → 第一个抽烟者取走东西
  • 桌上有组合二 → 第二个抽烟者取走东西
  • 桌上有组合三 → 第三个抽烟者取走东西
  • 发出完成信号 → 供应者将下一个组合放到桌上

注：将finish改为1， P(finish) 放在 provider 中 while(1){ 下一行也是可行的

10. 读者写者问题

问题描述:

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

• 因此要求:

  • 允许多个读者可以同时对文件执行读操作；
  • 只允许一个写者往文件中写信息；
  • 任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出

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);		// 各读进程互斥访问count
        if(count==0) 	// 由第一个读进程负责
        	P(rw);		// 读之前“加锁”
        count++;		// 访问文件的读进程数+1
        V(mutex);
        V(w);
        读文件…
        P(mutex);		// 各读进程互斥访问count
        count--;		// 访问文件的读进程数-1        
        
        if(count==0)  	// 由最后一个读进程负责
        	V(rw);		// 读完了“解锁”
        V(mutex);
    }
}

• 如果不加P(w)也可以完成功能，但当读进程源源不断进入时将会导致写进程“饥饿”

• P(mutex)保证各读进程对count 的访问是互斥的，对count 变量的检查和赋值能够一气呵成

• 总结:

  • 读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路
  • 其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数
  • 我们可以用count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理
  • 另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量
  • 最后，还要认真体会我们是如何解决“写进程饥饿”问题的

11. 哲学家进餐问题

问题描述:

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

分析:

• 关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系

• 整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的事，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓

• 信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1} 用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为 (i+1)%5

解:

误解:

// 如果5个哲学家并发地拿起了自己左手边的筷子, 每位哲学家循环等待右边的人放下筷子（阻塞）, 会发生“死锁”
semaphore chopstick[5]={1,1,1,1,1};
Pi (){ // i号哲学家的进程
    while(1){
        P(chopstick[i]); // 拿左
        P(chopstick[(i+1)%5]); // 拿右
        吃饭…
        V(chopstick[i]); // 放左
        V(chopstick[(i+1)%5]); // 放右
        思考…
    }
}

如何防止死锁的发生呢?

• 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

• 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况

• 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子更准确的说法应该是: 各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1; // 互斥地取筷子
// 这种方法并不能保证只有两边的筷子都可用时，才允许哲学家拿起筷子
Pi (){ // i号哲学家的进程
    while(1){
        P(mutex);
        P(chopstick[i]); // 拿左
        P(chopstick[(i+1)%5]); // 拿右
        V(mutex);
        吃饭…
        V(chopstick[i]); // 放左
        V(chopstick[(i+1)%5]); // 放右
        思考…
    }
}

总结:

• 哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患

12. 管程

12.1 为什么要引入管程?

• 信号量机制存在的问题: 编写程序困难、易出错

• 能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢?

• 1973年，Brinch Hansen 首次在程序设计语言 (Pascal)中引入了“管程”成分 -- 一种高级同步机制

12.2 管程的组成和基本特征

• 管程是一种特殊的软件模块，有这些部分组成:
  • 局部于管程的共享数据结构说明
  • 该数据结构进行操作的一组过程
    • 跨考Tips: “过程”其实就是“函数”
  • 对局部于管程的共享数据设置初始值的语句
  • 管程有一个名字
• 管程的基本特征:
  • 局部于管程的数据只能被局部于管程的过程所访问
  • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  • 每次仅允许一个进程在管程内执行某个内部过程
    • 由编译器负责实现各进程互斥地进入管程中的过程
    • 管程中设置条件变量和等待/唤醒操作，以解决同步问题
• 如何理解?
  • 可以把管程比作Java中的类，管程中的共享数据结构为类中的属性，管程中的一组过程是类中的一组方法
  • 管程中的方法可以看作是静态同步(static synchronized)方法，所以每次仅允许一个进程在管程内执行某个内部过程
  • 进程只能通过方法对属性进行操作，体现了类的封装思想

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