现代操作系统采用多道程序设计机制，多个进程可以并发执行，CPU在进程之间来回切换，共享某些资源，提高了资源的利用率，但这也使得处理并发执行的多个进程之间的冲突和相互制约关系成为了一道难题。如果对并发进程的调度不当，则可能会出现运行结果与切换时间有关的情况，令结果不可再现，影响系统的效率和正确性，严重时还会使系统直接崩溃。就比如你只有一台打印机，有两个进程都需要打印文件，如果直接让他们简单地并发访问打印机，那么你很可能什么都打印不出来或者打印的文件是…anyway，我们需要增加一些机制来控制并发进程间的这种相互制约关系。
进程间通信的很多问题的根本原因是我们不知道进程何时切换。
概念
首先我们了解一下临界资源与临界区的概念：临界资源就是一次只允许一个进程访问的资源，一个进程在使用临界资源的时候，另一个进程是无法访问的，操作系统也不能够中途剥夺正在使用者的使用权利，正所谓“泼出去的女儿嫁出去的水”是也。即临界资源是不可剥夺性资源。那么临界区呢谓临界区就是进程中范文临界资源的那段程序代码，注意，是程序代码，不是内存资源了，这就是临界资源与临界区的区别。我们规定临界区的使用原则(也即同步机制应遵循的准则)十六字诀：“空闲让进，忙则等待，有限等待，让权等待”–strling。让我们分别来解释一下：
(1)空闲让进：临界资源空闲时一定要让进程进入，不发生“互斥礼让”行为。
(2)忙则等待：临界资源正在使用时外面的进程等待。
(3)有限等待：进程等待进入临界区的时间是有限的，不会发生“饿死”的情况。
(4)让权等待：进程等待进入临界区是应该放弃CPU的使用。
好了，我们进入下一部分。
那么先来讨论如何实现进程的互斥控制。有下列几种方法：严格轮换(每个进程每次都从头执行到尾，效率不高，可能等待很久)，屏蔽中断(刚刚进入临界区时就屏蔽中断，刚要出临界区就打开中断)，专用机器指令test_and_set,test_and_clear，加锁，软件方法，信 量机制。讲一下加锁和软件方法，加锁方法如下：设置一个锁标志K表示临界资源的状态，K=1表示临界资源正在被使用，K=0表示没有进程在访问临界资源。如果一个进程需要访问临界资源，那么先检查锁标志K：
if K == 1, 循环检测，直到K = 0
else if K == 0，设置锁标志为1，进入临界区
离开临界区时设置锁标志K为0. 软件方法类似，如爱斯基摩人的小屋协议，爱斯基摩人的小屋很小，每次只能容纳一个人进入，小屋内有一个黑板，上面标志这能够进入临界区的进程。若进程申请进入临界区，则先进入小屋检查黑板标志，如果是自己，那么离开小屋进入临界区，执行完后进入小屋修改黑板标志为其他进程，离开小屋。如果小屋黑板标志不是自己，那么反复进入小屋考察黑板标志是不是自己。这两种方法都实现了互斥访问，但是都违反了四条原则之一：让权等待，都需要不断的循环重复检测标志，霸占了CPU资源，不是很好的方法。
到后来，荷兰计算机科学家Dijkstra于1965年提出了解决进程同步与互斥问题的信 量机制，收到了很好的效果，被一直沿用至今，广泛应用与单处理机和多处理机系统以及计算机 络中。信 量机制就是说两个或者多个进程通过他们都可以利用的一个或多个信 来实现准确无误不冲突的并发执行。如果临界资源不够，就会有一个信 表示出来，如果进程此时想访问，那么就会阻塞到一个队列中，等待调度。当临界资源使用完毕，一个进程改变信 ，并及时唤醒阻塞的进程，这就实现了进程间的同步和互斥问题。
信 量分为整型信 量，记录型信 量，AND信 量以及信 量集。最初的信 量就是整型信 量，定义信 量为一个整型变量，仅能通过两个原子操作P,V来访问，所谓原子操作就是指一组相联的操作要么不间断地执行，要么不执行。这两个操作又称为wait和signal操作或者down和up操作。之所以叫P,V操作是因为Dijkstra是荷兰人，P指的是荷兰语中的“proberen”，意为“测试”，而V指的是荷兰语中的“verhogen”，意为“增加”。最初P,V操作被描述为：
P(S): while (S≤0) {donothing};
S=S-1;
V(S): S=S+1;
但是这样明显违反了“让权等待的原则”，后来发展为记录型信 量，记录型信 量的数据结构是一个两元组，包含信 量的值value和关于此信 量的阻塞队列Q，value具有非负初值，一般反映了资源的数量，只能由P,V操作改变其值。(还有另一种定义，信 量由value和P组成，value为信 量的值，P为指向PCB队列的指针)。
记录型信 量的P,V操作原语为：
P(S): S.value = S.value-1;if(S.value
block(S,Q);
V(S): S.value= S.value + 1;if(S.value
wakeup(S,Q);
我们来详细解释一下这两个操作的含义：
首先，P操作，首先将S.value减1，表示该进程需要一个临界资源，如果S.value 0时不唤醒进程呢，很简单，因为阻塞队列中没有进程了。
我们将信 量初值设置为1时通常可实现互斥，因为信 量表示资源可用数目，互斥信 量保证只有一个进程访问临界资源，相当于只有一个访问权可用。设置为0或者N时可以用来实现同步。我们后面将会在生产者-消费者问题中看到这点。用P,V操作实现互斥类似于加锁的实现，在临界区之前加P操作，在临界区之后加V操作，即可互斥控制进程进入临界区，访问临界资源。记录型信 量由于引入了阻塞机制，消除了不让权等待的情况，提高了实现的效率。
经典问题
下面通过一些实例详细讲解如何使用信 量机制解决进程同步与互斥问题。先说明一条规律，即：同步与互斥实现的P,V操作虽然都是成对出现，但是互斥的P,V操作出现在同一个进程的程序里，而同步的P,V操作出现在不同进程的程序中。
问题1：生产者-消费者问题
经典的同步互斥问题，也称作“有界缓冲区问题”。具体表现为：
1.两个进程对同一个内存资源进行操作，一个是生产者，一个是消费者。
2.生产者往共享内存资源填充数据，如果区域满，则等待消费者消费数据。
3.消费者从共享内存资源取数据，如果区域空，则等待生产者填充数据。
4.生产者的填充数据行为和消费者的消费数据行为不可在同一时间发生。
还有一种解法是让奇数 与偶数 的哲学家拿筷子的先后顺序不同，以破坏环路等待条件。还可以只允许4个哲学家同时进餐(4个人都拿起一只筷子的时候，第5个人不能再拿筷子，这样就会空出一只筷子)
例题分析
至此，我们已经可以总结出一点用信 量解决同步互斥问题的基本规律和一般步骤：
(1)分析各进程间的制约关系，从而得出同步与互斥关系
(2)根据(1)中的分析，设置信 量
(3)编写伪代码，实施P,V操作
同步：多个进程在执行次序上的协调，相互等待消息
互斥：对临界资源的使用
要注意的是，虽然P,V操作在每一个进程中都是成对出现的，但不一定是针对一个信 量。互斥信 量的P,V操作总是出现在一个进程中的临界区的前后，而同步信 量的P,V操作总是出现在具有同步关系的两个进程中，需要等待消息的一方执行P操作，发出消息的一方执行V操作。
下面通过诸多例题来熟悉，掌握及训练用信 量解决同步与互斥问题的一般方法。
问题4：放水果问题
桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果，妈妈可向盘中放一个桔子。
儿子专等吃盘中的桔子，女儿专等吃苹果。
试用P、V操作实现爸爸、妈妈、儿子、女儿四个并发进程的同步。
分析：临界资源是盘子，放的时候不能取，取的时候不能放，取的时候不能再取。同步关系：爸爸、妈妈与盘子为空，儿子与盘中有桔，女儿与盘中有苹果。
所以设置一个mutex互斥信 量来控制对盘子的访问，用empty，orange，apple分别代表以上同步关系。程序如下：
Semaphore mutex = 1;
Semaphore empty= 1, orange = apple = 0;
mother:while(1) {
P(empty);
P(mutex);//放入桔子
V(mutex)
V(orange);
}
father:while(1) {
P(empty);
P(mutex);//放入苹果
V(mutex)
V(apple);
}
son:while(1) {
P(orange)
P(mutex)//取桔子
V(mutex);
V(empty);
}
daughter:while(1) {
P(apple)
P(mutex)//取苹果
V(mutex);
V(empty);
}
View Code
问题5：读文件问题
四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件，现用P、V操作进行管理。
分析：互斥关系：A和C读文件时互斥，B和D读文件时互斥，没有同步关系。
所以设置两个互斥信 量：AC_mutex,BD_mutex即可。伪代码如下：
Semaphore AC_mutex = BD_mutex = 1;
A:while(1) {
P(AC_mutex);//read F
V(AC_mutex);
}
B:while(1) {
P(BD_mutex);//read F
V(BD_mutex);
}
C:while(1) {
P(AC_mutex);//read F
V(AC_mutex);
}
D:while(1) {
P(BD_mutex);//read F
V(BD_mutex);
}
View Code
问题6：阅览室问题 / 图书馆问题
有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座 和读者姓名。读者离开时要消掉登记信
，阅览室中共有100个座位。用PV操作控制这个过程。
分析：
由于每个读者都会进行一样的操作：登记->进入->阅读->撤销登记->离开，所以建立一个读者模型即可。
临界资源有：座位，登记表
读者间有座位和登记表的互斥关系，所以设信 量empty表示空座位的数量，初始为100，mutex表示对登记表的互斥访问，初始为1。
P,V操作如下：
Semaphore mutex = 1, empty = 100;
Reader()：
While(true) {
P(empty)//申请空座位
P(mutex) //申请登记表//登记
V(mutex) //释放登记表//进入阅读
P(mutex) //申请登记表//撤销登记
V(mutex) //释放登记表
V(empty) //释放座位
}
View Code
问题7：单行道问题
一段双向行驶的公路，由于山体滑坡，一小段路的一般车道被阻隔，该段每次只能容纳一辆车通过，一个方向的多个车辆可以紧接着通过，试用P,V操作控制此过程。
从其中可以看出，车辆正常交替顺序通过该路段。数字重复出现是因为线程被重复地调度执行。
问题8：理发师问题
理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子 如果没有顾客，理发师便在理发椅上睡觉。 一个顾客到来时，它必
须叫醒理发师
如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。用PV操作管理该过程。
分析：
法1：首先设置一个count表示等待的人数(包括理发椅上的那个人)，初值为0，以供后来者判断是否应该离开。同时对count的访问要保证互斥，所以设置mutex信 量来保证互斥，初值为1。
临界资源：凳子，理发椅。 分别设置waitchair,barchair信 量，初值分别为n和1，表示临界资源数量。
同步关系：顾客和理发师之间有同步关系，用ready和done信 量来表示，初值均为0，ready表示顾客有没有准备好，done表示理发师是否完成一次理发。
注意：并非每一个进程都需要while(1)无限循环，比如此例，顾客剪完一次头发就走了，不可能马上再来剪，而以前的生产者-消费者不同，他们都是可以不断生产消费的。
写出P,V操作如下：
Semaphore waitchair =n;
Semaphore barchair= 1;
Semaphore ready= done = 0;int count = 0;
Semaphore mutex= 1;
barber:while(1) {
P(ready);
理发
V(done);
}
consumer:
P(mutex);if(count
count= count + 1;
V(mutex);
}else{
V(mutex);
离开
}
P(waitchair);
P(barchair);
V(waitchair);//离开等待椅去理发椅需要释放等待椅!
V(ready); //准备好了
P(done); //等待理发完成
V(barchair);
P(mutex);
count= count – 1;
V(mutex);
离开
View Code
法2：将凳子和理发椅看做同一种资源，因为只要理发椅空就一定会有人凑上去，所以相当于每个位置都是理发椅，理发师只需要去每个有人的座位理发即可。
还是设置count表示正在理发店中的人数，以便决定后来者是否离开。
同步关系仍用ready和done来表示。
算法：
Semaphore ready = done = 0;int count = 0;
Semaphore mutex= 1;
barber:while(1) {
P(ready);
理发
V(done);
}
consumer:
P(mutex);if(count
count= count + 1;
V(mutex);
}else{
V(mutex);
离开
}
V(ready);//准备好了
P(done); //等待理发完成
P(mutex); //也可由理发师来做count-1的操作
count = count – 1;
V(mutex);
离开
View Code
好了，先说这么多，例题会持续更新增加，感兴趣的朋友可以关注下。
鄙人学力有限，有不足或错误之处敬请指出，不胜感激。
参考文献：
1.《现代操作系统》 –Andrew S. Tanenbaum
2.《操作系统设计与实现》 –Andrew S. Tanenbaum
3.《操作系统精髓与设计原理》 –Strling
4.《2015操作系统高分笔记》 –刘泱主编
相关资源：Cwtype摩尔斯电码学习软件,发 软件,汉化版本_电脑模拟CW-电信…
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！