操作系统是大学里非常重要的课程，对于科班出身的同学来说，把这门课程学号是非常必要的，下面我将我的课堂笔记整理好跟大家分享，虽然这些例子都是很简单的，代码也都能在网上找到，但是我想经过自己整理的代码，才能把知识固定在脑子里，希望我的笔记对大家操作系统的学习有利，特别是非科班出身而且对计算机感兴趣的同学；
正文：
信号量的本质是一种数据操作锁，它本身不具有数据交换的功能，而是通过控制其他的通信资源（文件，外部设备）来实现进程间通信，它本身只是一种外部资源的标识。信号量在此过程中负责数据操作的互斥、同步等功能。
???当请求一个使用信号量来表示的资源时，进程需要先读取信号量的值来判断资源是否可用。大于0，资源可以请求，等于0，无资源可用，进程会进入睡眠状态直至资源可用。
信号量结构体：
struct{?unsigned?short?semval;
??????????pid_t??????????sempid;
??????????unsigned?short?semncent;
????????.....
????????};
信号量的两个操作：
<!--[if !supportLists]-->1、<!--[endif]-->阻塞操作——Wait
<!--[if !supportLists]-->2、<!--[endif]-->唤醒操作——Signal
?
信号量分类
<!--[if !supportLists]-->1、<!--[endif]-->技数信号量：
使用范围：资源数量有多个（共享资源有多个备份，他们的使用是互斥的）；
?
取值范围：大于1的整数值，
<!--[if !supportLists]-->2、<!--[endif]-->二元信号量：
取值范围：0、1
使用范围：实现互斥；
Semaphore?S;
Wait(S):
Critical?Section;
Signal(S);
二元信号量其实就是一个锁；
Wait——获取锁的钥匙
Signal——钥匙扔掉
?
二元信号量比较简单，比较复杂的计数信号量可以用二元信号量来实现：
?
Data?Structures:
Int?c;//计数信号量的取值
Binary-Semaphore??S1,S2;//对C的操作要求互斥，S1作为C的互斥锁；
//S2做为技术信号量的wait的等待;
Initialization:
S1?=?1
S2?=?0
C?=?intial?value?of?semaphore?S;
?
Wait(C)?operation
Wait(S1)l;
C--;
If(C<0){
Signal(S1);//唤醒S1
Wait(S2);
}
Signal(S1);
?
Signal(C)?operation
Wait(S1);
C++;
If(C<=0)
Signal(S2);
Else
Signal(S1);
?
同步问题的例子
解决同步问题思路步骤：
参与者与规则；
资源：具体问题所涉及的资源，而这些资源一般都是共享的，资源的数量也是有限的；
继续处理前必须获得资源——技术信号量或者变量计数；
共享变量
必须保护访问——二元信号量；
<!--[if !supportLists]-->1、<!--[endif]-->有限缓存问题（生产者消费者问题）：
问题描述：两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。
游戏参与者：生产者、消费者
活动限制：共享一个固定大小的缓冲区；
对共享数据的访问要求：互斥（生产消费操作必须互斥），缓存区满后停止生产，有产品后才消费；
怎样保证互斥：设置一个信号量，用信号量保证互斥；
缓存区满后停止生产：获得空的缓存去单元，用一个计数信号量表示空的单元数，empty；
有生产后才消费：有一个“满”的资源才能进行消费；
一个生产者，一个消费者，公用一个缓冲区
定义两个同步信号量：
empty——表示缓冲区是否为空，初值为1。
full——表示缓冲区中是否为满，初值为0。
生产者进程
while(TRUE){
生产一个产品;
?????P(empty);
?????产品送往Buffer;
?????V(full);
}
消费者进程
while(TRUE){
P(full);
???从Buffer取出一个产品;
???V(empty);
???消费该产品;
一个生产者，一个消费者，公用n个环形缓冲区
——N个缓冲区形成一个环形缓冲区要利用指针。缓冲区的指向则通过模运算得到。
empty——表示缓冲区是否为空，初值为n。
full——表示缓冲区中是否为满，初值为0。
????设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。
?
生产者进程
while(TRUE){
?????生产一个产品;
?????P(empty);
?????产品送往buffer（in）；
?????in=(in+1)mod?n；
?????V(full);
?????}
消费者进程
while(TRUE){
?P(full);
???从buffer（out）中取出产品；
???out=(out+1)mod?n；
???V(empty);
???消费该产品;
???}
?
一组生产者，一组消费者，公用n个环形缓冲区
——在这种情况中，生产者与消费者存在同步关系，而且各个生产者之间、各个消费者之间存在互斥关系,他们必须互斥地访问缓冲区。
定义四个信号量：
empty——表示缓冲区是否为空，初值为n。
full——表示缓冲区中是否为满，初值为0。
mutex1——生产者之间的互斥信号量，初值为1。
mutex2——消费者之间的互斥信号量，初值为1。
设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。
?
生产者进程
while(TRUE){
?????生产一个产品;
?????P(empty);
?????P(mutex1)；
?????产品送往buffer（in）；
?????in=(in+1)mod?n；
?????V(mutex1);
?????V(full);
?????}
消费者进程
while(TRUE){
?P(full);
???P(mutex2)；
???从buffer（out）中取出产品；
???out=(out+1)mod?n；
???V（mutex2）；
???V(empty);
?
<!--[if !supportLists]-->2、<!--[endif]-->读者\写者问题：
问题描述：读者—写者问题（Readers-Writers?problem）也是一个经典的并发程序设计问题，是经常出现的一种同步问题。计算机系统中的数据（文件、记录）常被多个进程共享，但其中某些进程可能只要求读数据（称为读者Reader）；另一些进程则要求修改数据（称为写者Writer）。就共享数据而言，Reader和Writer是两组并发进程共享一组数据区，要求：
游戏参与者：读者、写者
活动限制：读写操作是在同一个临界区；
对共享数据的访问要求：（互斥）读和写不能同时进行，允许多个读者同时执行读操作，不允许读者、写者同时操作，不允许多个写者同时操作；
许多个读者同时执行读操作，第一个读者解锁；最后一个读者加锁，使用一个计数器readcount来计算读者的数量；
Shared?data
Semaphore?mutex?保证读者对readcount访问的互斥
??Wrt：?保证读写互斥
Readcount：记录读者数量
?
<!--[if !supportLists]-->3、<!--[endif]-->哲学家问题
问题描述：在餐桌旁的哲学家有两种操作，思考，就餐，餐桌上每个哲学家的右边有一只筷子，两只筷子才能就餐；
?
?
游戏参与者：哲学家
共享资源：筷子（二元信号量）；
对共享数据的访问要求：每个筷子的使用是互斥的，每个哲学家只能使用身边的筷子；
哲学家就餐防止死锁：
当一个哲学家身边的两个筷子都可以用才可以允许它拿筷子；
给所有哲学家编号，奇数号的哲学家首先拿左边的筷子；偶数号的哲学家先拿右边的筷子；
如果哲学家总数已知，可以让控制最多让总数-1的哲学家就餐；
?
<!--[if !supportLists]-->4、<!--[endif]-->理发师问题：
问题描述：
<!--[if !supportLists]-->1、<!--[endif]-->休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；
<!--[if !supportLists]-->2、<!--[endif]-->处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；
<!--[if !supportLists]-->3、<!--[endif]-->理发时间长短由理发师决定；
<!--[if !supportLists]-->4、<!--[endif]-->在站席区等待时间最长的顾客可坐到空闲的理发上；
<!--[if !supportLists]-->5、<!--[endif]-->任何时刻最多只能有一个理发师在收银。
游戏参与者：理发师，顾客
伪代码：
semaphore?stand_capacity=5;
semaphore?sofa=4;
semaphore?barber_chair=3;
semaphore?customer_ready=0;
semaphore?mutex=3;
semaphore?mutex1=1;
semaphore?finished[3]={0,0,0};
semaphore?leave_barberchair=0;
semaphore?payment=0;
semaphore?receipt=0;
void?customer()
{
顾客：
int?barber_number;
wait(stand_capacity);?//等待进入理发店
enter_room();?//进入理发店
wait(sofa);?//等待沙发
leave_stand_section();?//离开站席区
signal(stand_capacity);
sit_on_sofa();?//坐在沙发上
wait(barber_chair);?//等待理发椅
get_up_sofa();?//离开沙发
signal(sofa);
wait(mutex1);
sit_on_barberchair();?//坐到理发椅上
signal(customer_ready);
barber_number=dequeue();?//得到理发师编号
signal(mutex1);
wait(finished[barber_number]);?//等待理发结束
pay();?//付款
signal(payment);?//付款
wait(receipt);?//等待收据
get_up_barberchair();?//离开理发椅
signal(leave_barberchair);?//发出离开理发椅信号
exit_shop();?//了离开理发店
}
对于理发师：
void?barber(int?i)
{
while(true)
{
wait(mutex1);
enqueue(i);?//将该理发师的编号加入队列
signal(mutex1);
wait(customer_ready);?//等待顾客准备好
wait(mutex);
cut_hair();?//理发
signal(mutex);
signal(finished[i]);?//理发结束
wait(leave_barberchair);?//等待顾客离开理发椅信号
signal(barber_chair);?//释放barber_chair?信号
}
}
void?cash()?//收银
{
while(true)
{
wait(payment);?//等待顾客付款
wait(mutex);?//原子操作
get_pay();?//接受付款
give_receipt();?//给顾客收据
signal(mutex);
signal(receipt);?//收银完毕，释放信号
}
}?
6、过桥问题
问题：一座小桥（最多能承重两个人）横跨南北两岸，任意时刻同一方向只允许一个人过桥；南侧的桥段和北侧的桥段较窄只能一个人通过，桥中央一处宽敞，允许两个人通过或者休息。
游戏参与者：南北过桥者；
资源：桥的承重（对多两人，相当于资源的两个份额）
信号量使用：
Load：（技术信号量）
North：（二元信号量）
South：（二元信号量）
伪代码：
int?countSN=0;
int?countNS=0;
semaphore?mutexSN=1;
semaphore?mutexNS=1;
semaphore?bridge=1;
?
?
?
6、和尚打水问题（生产消费变种）：
问题描述：某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为3个。每次入水、取水仅为一桶，且不可同时进行
信号量设置：
<!--[if !supportLists]-->1、<!--[endif]-->对于水缸——以一个水桶水为单位，empty=30、full?=?0两个计数信号量
<!--[if !supportLists]-->2、<!--[endif]-->小和尚对缸操作：mutex-jar?=?1二元信号量；
<!--[if !supportLists]-->3、<!--[endif]-->水桶个数（资源数）：bucket?=?5计数信号量
<!--[if !supportLists]-->4、<!--[endif]-->取水操作（每次入水、取水仅为一桶）：互斥mutex-well?=?1二元信号量；
伪代码：
?
?
7、一家人吃水果问题：
问题描述：桌子上有一只盘子，每次只能放一个水果，爸爸专向里面放苹果，妈妈放橘子，儿子专吃橘子，女儿专吃苹果，仅当盘子空闲时，爸爸妈妈才可以向里面放水果，仅当盘子里有自己需要的水果时，儿子女儿才可以从里面取出一只水果。
生产者消费者变种问题：
1、空间变为一个，不同的消费者需求不同；
2、信号量变化：Full——用两个信号量表示So=0、SA=0（表示橘子和苹果两种），empty=1不变；
伪代码：
int?e=1,a=o=0;
main()
{father();
?//son();
?//daughter();/*三个为并发进程*/
}
father()
{while(1)
??{?洗水果
????wait(e)
????把水果放入盘子
????if（水果是苹果）signal(a)
????else?signal(o)
???}
}?
son()
{while(1)
????{wait(o)
?????从盘子里取桔子
?????signal(e)
?????吃桔子}
}
daughter()
{while(1)
???{wait(a)
????从盘子里取苹果
????signal(e)
????吃苹果}
}
操作系统进程同步问题解析（哲学家问题、生产消费问题、小和尚打水问题等大量例子）
原文：http://448230305.iteye.com/blog/2155102