AlgerFan | Blog

一、进程同步、进程互斥

什么是进程同步？

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据 →读数据”的顺序来执行的。
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

什么是进程互斥？

两种资源共享方式

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

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

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

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

总结

二、软硬件同步机制（了解）

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

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

中断屏蔽方法

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

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

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

TestAndSet 指令

简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令
TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用 C 语言描述的逻辑：

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

Swap 指令

有的地方也叫 Exchange 指令，或简称 XCHG 指令。
Swap 指令是用硬件实现的，执行的过程不允许被中断，只能- -气呵成。以下是用 C 语言描述的逻辑：

优缺点和 TestAndSet 指令一样。

总结

三、信号量机制

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

原语是一种特殊的程序段，其执行只能- -气呵成，不可被中断。原语是由关中断/开中断指令实现的。一对原语： wait(S) 原语和 signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal,括号里的信号量 S 其实就是函数调用时传入的一个参数。

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

整型信号量

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

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

Eg:某计算机系统中有一台打印机...

记录型信号量

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

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

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

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

总结

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

实现进程互斥

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

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

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

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

实现进程同步

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

/*信号量机制实现同步*/
semaphore S=0; // 初始化同步信号量，初始值为0

P1(){		P2(){
  代码1; 	  P(S);
  代码2;	  代码4;
  V(S);		  代码5;
  代码3;	  代码6;
}		}

若先执行到 V(S)操作，则 S++ 后 S=1。之后当执行到 P(S)操作时，由于 S=1，表示有可用资源，会执行 S--，S 的值变回 0,P2 进程不会执行 block 原语，而是继续往下执行代码 4。
若先执行到 P(S)操作，由于 S=0， S-- 后 S=-1，表示此时没有可用资源，因此 P 操作中会执行 block 原语，主动请求阻塞。之后当执行完代码 2，继而执行 V(S)操作，S++， 使 S 变回 0,由于此时有进程在该信号量对应的阻塞队列中，因此会在 V 操作中执行 wakeup 原语，唤醒 P2 进程。这样 P2 就可以继续执行代码 4 了。

实现前驱关系

进程 P1 中有句代码 S1，P2 中有句代码 S2..P3...P6 中有句代码 S6。这些代码要
示的顺序来执行：
其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)因此，
1.要为每一对前驱关系各设置一个同步变量
2.在“前操作”之后对相应的同步变量执行 V 操作
3.在“后操作”之前对相应的同步变量执行 P 操作

总结

五、生产者-消费者问题

问题描述：
系统中有一组生产者进程和一-组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注： 这里的“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为 n 的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
缓冲区是临界资源，各进程必须互斥地访问。

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

实现过程：

实现互斥的 P 操作一定要在实现同步的 P 操作之后。
V 操作不会导致进程阻塞，因此两个 V 操作顺序可以交换。

六、读者-写者问题

问题描述：
有读者和写者两组并发进程，共享一个文件，当两个或两个以。上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：
① 允许多个读者可以同时对文件执行读操作;
② 只允许一个写者往文件中写信息;
③ 任一写者在完成写操作之前不允许其他读者或写者工作;
④ 写者执行写操作前，应让已有的读者和写者全部退出。

两类进程：写进程、读进程
互斥关系：写进程-写进程、写进程-读进程。读进程与读进程不存在互斥问题。
写者进程和任何进程都互斥，设置一个互斥信号量 rw，在写者访问共享文件前后分别执行 P、V 操作。读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对 rw 执行 P、V 操作。

P(rw)和 V(rw)其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量 count 来记录当前有几个读进程在访问文件。

实现过程

优化后实现

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

七、 哲学家进餐问题

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

1.关系分析。系统中有 5 个哲学家进程，5 位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2.整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的事，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
3.信号量设置。定义互斥信号量数组 chopstick[5]={1,1,1,1,1}用于实现对 5 个筷子的互斥访问。并对哲学家按 0~4 编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为(i+1)%5。

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

实现过程