术语
- 进度图 进度图是将 n 个并发进程的执行模型化为一条 n 维笛卡尔空间中的轨迹线，每条轴 k 对应于线程 k 的进度，每个进度对应一条指令。
- 临界区 某个线程操作共享变量 cnt 内容的一串指令
- 不安全区 两个临界区的交集形成的状态空间区域称为不安全区
- 安全轨迹区 绕开不安全区的轨迹线
-
信号量 是一个具有非负整数值的全局变量，只能由两种特殊的操作 P(s)（测试减一） 和 V(s)（增加加一） 来处理，这两个操作都是原子的，不可分割的
临界区与安全轨迹线
为了保证线程化程序的正确执行（实际上是任何共享全局数据结构的冰法程序的正确执行）我们必须以某种方式同步线程，使它们总是有一条安全轨迹线，一个经典的方法是基于信号量的思想。
使用信号量来实现互斥
基本思想是将每个共享变量与一个信号量 s(初始化为一个整数 n) 联系起来，然后用 P(s) 和 V(s) 操作将相应的临界区包围起来。
s 的初始值决定了这个资源可以同时被 n 个进程使用
n=1 时的信号量成为互斥锁(mutex)，P(s) 和 V(s)相应的成为加锁和解锁，信号量操作确保了对临界区的互斥访问。
使用信号量实现互斥
使用信号量来调度共享资源
除了提供互斥之外，信号量的另外一个重要作用是用来调度对共享资源的访问，即一个线程用信号量来通知另一个线程，线程状态中的某个条件已经为真了。
生产者-消费者问题
生产者消费者问题也称为有限缓冲问题，是一个多线程同步问题的经典案例。该问题描述了共享固定大小缓冲区的两个线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。
要解决该问题，就必须让生产者在缓冲区满时休眠（要么干脆就放弃数据），等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后。
经典进程同步问题1：生产者-消费者问题
semaphore mutex=1; //临界区互斥信号量
semaphore empty=n; //空闲缓冲区
semaphore full=0; //缓冲区初始化为空
producer () { //生产者进程
while(1){
produce an item in nextp; //生产数据
P(empty); //获取空缓冲区单元
P(mutex); //进入临界区.
add nextp to buffer; //将数据放入缓冲区
V(mutex); //离开临界区,释放互斥信号量
V(full); //满缓冲区数加1
}
}
consumer () { //消费者进程
while(1){
P(full); //获取满缓冲区单元
P(mutex); // 进入临界区
remove an item from buffer; //从缓冲区中取出数据
V (mutex); //离开临界区，释放互斥信号量
V (empty) ; //空缓冲区数加1
consume the item; //消费数据
}
}
读者写者问题
有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。
经典进程同步问题2：读者-写者问题
int count = 0; //用于记录当前的读者数量
semaphore mutex = 1; //用于保护更新count变量时的互斥
semaphore rw=1; //用于保证读者和写者互斥地访问文件
semaphore w=1; //用于实现“写优先”
writer(){
while(1){
P(w); //在无写进程请求时进入
P(rw); //互斥访问共享文件
writing; //写入
V(rw); // 释放共享文件
V(w) ; //恢复对共享支件的访问
}
}
reader () { //读者进程
while (1){
P (w) ; // 在无写进程请求时进入
P (mutex); // 互斥访问count变量
if (count==0) //当第一个读进程读共享文件时
P(rw); //阻止写进程写
count++; //读者计数器加1
V (mutex) ; //释放互斥变量count
V(w); //恢复对共享文件的访问
reading; //读取
P (mutex) ; //互斥访问count变量
count--; //读者计数器减1
if (count==0) //当最后一个读进程读完共享文件
V(rw); //允许写进程写
V (mutex); //释放互斥变量count
}
}
