进程同步：synchronization 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体地说，一个进程运行到某一点时，要求另一伙伴进程为它提供消息，在未获得消息之前，该进程进入阻塞态，获得消息后被唤醒进入就绪态。
生产者/消费者问题
问题描述：一个或多个生产者生产某种类型的数据放置在缓冲区中，有消费者从缓冲区中取数据，每次取一项，只能有一个生产者或消费者对缓冲区进行操作。
要解决的问题：当缓冲区已满时，生产者不会继续向其中添加数据；当缓冲区为空时，消费者不会从中移走数据
避免忙等待：睡眠或唤醒原语
#define N 100
int count=0;
void producer(void)
{ int item;
while(TRUE){
item=produce_item();
if(count==N) sleep();
insert_item(item);
count=count+1;
if(count==1)
wakeup(consumer);
}
}
void consumer(void)
{
int item;
while(TRUE){
if(count==0) sleep();
item=remove_item();
count=count-1;
if(count==N-1)
wakeup(producer);
consume_item(item);
}
}
信号量及P、V操作
信号量和PV操作是一种卓有成效的进程同步机制，1965年由荷兰学者Dijkstra提出。
一个特殊变量，用于进程间传递信息的一个整数值，定义如下
struc semaphore
{
int count;
queueType queue;
}
信号量说明：semaphore s;
对信号量可以实施的操作：初始化、P和V（P、V分别是荷兰语的test（proberen）和increment（verhogen）
P、V操作定义
P(s)
{
s.count--;
if(s.count<0)
{
该进程状态置为阻塞状态；
该进程插入相应的等待队列s.queue末尾；
重新调度；
}
}
V(s)
{
s.count++;
if(s.count<=0)
{
唤醒相应等待队列s.queue中等待的一个进程；
改变其状态为就绪态，并将其插入就绪队列；
}
}
P、V操作为原语操作
在信号量上定义了三个操作：初始化（非负数）、P操作、V操作
最初提出的是二元信号量（解决互斥），之后，推广到一般信号量（多值）或计数信号量（解决同步）
用PV操作解决进程间互斥问题
- 分析并发进程的关键活动，划定临界区
- 设置信号量mutex，初值为1
- 在临界区前实施P（mutex）
- 在临界区后实施V（mutex）
用信号量解决生产者、消费者问题
读者写者问题
用信号量解决读者/写者问题
问题描述： 多个进程共享一个数据区，这些进程分为两组：
读者进程：只读数据区中的数据
写者进程：只往数据区写数据
要求满足条件：
- 允许多个读者同时执行读操作
- 不允许多个写者同时操作
- 不允许读者、写者同时操作
第一类读者写者问题：读者优先
如果读者执行：
- 无其他读者、写者。该读者可以读
- 若已有写者等，但有其他读者正在读，则该读者也可以读
- 若有写者正在写，该读者必须等
如果写者执行：
- 无其他读者、写者，该写者可以写
- 若有读者正在读，该写者等待
- 若有其他写者正在写，该写者等待
Linux提供的读写锁
应用场景：如果每个执行实体对临界区的访问或者是读或者是写共享变量，但是它们都不会既读又写时，读写锁是最好的选择
实例：Linux的IPX路由代码中使用了读写锁，用ipx_routes_lock的读写锁保护IPX路由表的并发访问
要通过查找路由表实现包转发的程序需要请求读锁；需要添加和删除路由表中入口的程序必须获取写锁（由于通过读路由表的情况比更新路由表的情况多得多，使用读写锁提高了性能）
