1.Intro
为了实现多道程序环境，操作系统设计引入了进程Process的概念。 为了协调进程间的相互制约，则又引入了进程同步进程互斥的概念。
为了更直观地处理进程相互制约的问题，我们把一次仅允许一个进程使用的资源称为临界资源。把进程访问这个资源的那段代码称为临界区。
do {
entry section; //进入区
critical section; //临界区
exit section; //退出区
remainder section; //剩余区
} while (true)
2.什么是进程同步？什么是进程互斥？
同步是指为了完成某种任务而建立的多个进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。通俗地讲，多个存在合作关系的进程之间使用进程同步技术来协调。
互斥是指一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后另一个进程才能访问该资源。
3.实现临界区进程互斥的技术
3.1软件方法，即Peterson算法
// Px进程
flag[x]=1; turn=y;
while(!flag[x] && turn!=x);
critical section;
flag[x]=0;
remainder section
//Py进程
flag[y]=1; turn=x;
while(!flag[y] && turn!=y);
critical section;
flag[x]=0;
remainder section;
3.2硬件方法，即硬件指令方法
TestAndSet指令：一个原子操作。功能是读出指定标志后把该标志设置为1.
bool TestAndSet(bool *lock)
{
bool old;
old = *lock;
*lock = 1;
return old;
}
为每个临界资源设置一个共享bool型变量lock，为1表示被占用。
while TestAndSet (& 1 ock);
// 进程的临界区代码段;
lock=false;
// 进程的其他代码
Swap指令：该指令的功能是交换两个字节的内容。其功能描述如下。
Swap(boolean *a, boolean *b){
boolean temp;
Temp=*a;
*a = *b;
*b = temp;
}
4信号量机制
4.1信号量是什么
我们设计一个变量，用来描述某一资源的当前状态。如整型信号量s用来描述当前某一空闲资源的数量。
- 整型信号量
在设计操作系统的时候，我们会保留出两个原子语句操作：P(S)和V(S)，也可以称为wait(s)和signal(s)。wait(s)表示请求占用资源s，signal(s)表示回收资源s。这里使用s来表示某一空闲资源数量。
seaphore wait(s)
{
while(s<1);
s--;
}
seaphore signal()
{
s++;
}
- 记录型信号量
typedef struct {
int value; //资源数目
struct process *L; //整型变量
} semaphore;
void wait(semaphore S)
{
S.value--;
if(S.value>0)
{
add a process P to S.L;
S.value--;
}
}
void signal(semaphore S)
{
S.value++;
if(S.value<=0)
{
remove a process P from S.L;
wakeup(P);
}
}
4.2利用信号量实现进程互斥
利用信号量解决临界区进程互斥问题，设S为两个进程之间的互斥信号量，初值为1。
semaphore S = 1;
// 进程A
P(S)
critical section
V(S)
// 进程B
P(S)
critical section
V(S)
4.3利用信号量实现进程同步
假如进程B的语句y需要进程A中语句x的运行结果，所以只有在x语句运行后y语句才能运行。我们设S为进程A和B之间的同步信号量，初值为0。
semaphore S = 0;
// 进程A
// …
x; //语句x
V(S);
// 进程B
// …
P(S);
y; //语句Y
5经典进程同步问题：生产者消费者问题
问题陈述
一组生产者进程和一组消费者进程共享一段大小为n，初值为0的Buffer，只有Buffer没满时生产者才能放入消息，否则必须等待，只有Buffer不为空时消费者才能取消息，否则必须等待。另外由于Buffer是临界区，在任何时刻都只允许1个进程对其操作。
问题解决
semaphore vmutex = 1;
semaphore empty = n;
semaphore full = 0;
producer() {
P(empty);
P(vmutex);
critical section;
V(vmutex);
V(full);
}
customer() {
P(full);
P(vmutex);
critical section;
V(vmutex);
V(empty);
}
实例
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈就可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。
6经典进程同步问题：读者写者问题
问题陈述
有读者和写者两组并发进程，共享一个文件。允许多个读者可以同时对文件执行读操作；只允许一个写者往文件中写信息；任一写者在完成写操作之前不允许其他读者或写者工作；写者执行写操作前，应让已有的读者和写者全部退出。
问题解决
int cnt = 0;
semaphore mutex = 1;
semaphore rw = 1;
writer() {
while (TRUE){
P(rw);
Writing;
V(rw) ;
}
}
reader() {
while(TRUE){
P (mutex) ;
if (count==0)
P(rw);
cnt++;
V (mutex) ;
reading;
P (mutex) ;
cnt--;
if (count==0)
V(rw) ;
V (mutex) ;
}
}
7经典进程同步问题：哲学家进餐问题
问题陈述
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是食物。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、 右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
问题解决
#define N 5
semaphore mutex;
semaphore chopsticks[N];
memset(chopsticks,1,sizeof(chopsticks));
Pi() {
while(TRUE)
{
P(mutex);
P(chopsticks[i]);
P(chopsticks[(i+1)%N]);
eat;
V(mutex);
V(chopsticks[i]);
V(chopsticks[(i+1)%N]);
think;
}
}