1、基本概念

1.1两种形式的制约关系

1.2临界资源

1.3临界区

1.4同步机制应遵循的规则

2、硬件同步机制

3、信号量机制(重要)

3.1整型信号量

3.2记录型信号量

3.3AND型信号量

3.4信号量集

4、信号量的应用

4.1利用信号量实现进程互斥

4.2利用信号量实现前趋关系

5、经典进程的同步问题

1.生产者-消费者问题

2.哲学家就餐问题

1、基本概念

进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则(或时序)共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。

1.1两种形式的制约关系

（1）间接相互制约关系

表现为进程互斥

可以发生在任何进程之间

互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系！

（2）直接相互制约关系

表现为进程同步

进程同步是合作完成任务的关系！

为完成同一个任务的诸进程间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。这种制约主要源于进程间的合作。

1.2临界资源

一次仅允许一个进程使用的资源

生产者与消费者问题案例:

//生产者进程和消费者进程共享的变量：
int  n;
typedef struct {……} item;
item  buffer[n];
int in, out;
int counter;//生产者
Producer(){ while(1){…produce an item in nextp;  …while(counter==n) do no-op;buffer[in]=nextp;in=in+1 mod n;counter++;}}//消费者
Consumer(){while(1){while(counter==0) do no-op;nextc=buffer[out];out=out+1 mod n;counter--;consume the itemin nextc;}
}

1.3临界区

每个进程中访问临界资源的那段程序
保证诸进程必须互斥进入相关临界区，便可实现诸进程对临界资源的互斥访问

一个访问临界资源的循环进程描述如下:

while(true)
{进入区临界区退出区剩余区
}

进入区:对欲访问的临界资源进行检查，若此刻未被访问，设正在访问的标志
临界区:访问临界资源
退出区:将正在访问的标志恢复为未被访问的标志
剩余区:其余部分

1.4同步机制应遵循的规则

空闲让进
忙则等待
有限等待
让权等待

2、硬件同步机制

软件实现方法就是在进入区设置和检查一些标志来判断是否有进程在临界区，如果已有进程在临界区，则等待；
进程离开临界区后则在退出区修改标志。
关键问题是设置什么标志和如何检查标志。
设有两进程Pi和Pj共享一个临界资源R；
用软件方法使进程Pi和Pj互斥访问资源R。

3、信号量机制(重要)

概念:信号量是一个仅能由原语对其进行操作的整型变量或记录型变量。之所以称其为信号量，来源于交通管理中的信号灯的概念。

Wait、Signal操作是原语

Wait操作：申请一个单位的资源，又称P操作
Signal操作：释放一个单位的资源，又称V操作

3.1整型信号量

最初把整形信号量定义为一个用于表示资源数目的整型量S

Wait操作  wait(S):	 while(S<=0) /*do no-op*/S=S-1;
Signal操作  signal(S):	  S=S+1;

Wait、Signal操作是原子操作,不可中断。

3.2记录型信号量

未遵循“让权等待”，会使进程出现“忙等”的状态

记录型信号量

一般是由两个成员组成的数据结构，其中一个成员是整型变量，表示该信号量的值，另一个是指向PCB的指针

struct semaphore
{int value;PCB *L;     //进程队列指针
}void  Wait(struct semaphore s)
{s.value--;//申请一个单位的资源if(s.value<0)block(s.L)//若信号量计数值小于0，//表示无资源，则阻塞等待,//重新调度；否则调用进程继续。
}void  Signal(struct semaphore s)
{s.value++;//释放一个单位的资源if(s.value<=0)wakeup(s.L)//若信号量计数值小于等于0// 表示有进程在等待该资源，//唤醒一个等待者。
}

每个信号量s除一个整数值s.value（计数）外，还有一个进程等待队列s.L，登记阻塞在该信号量的各个进程的标识;
信号量只能通过初始化和两个标准的原语来访问；
初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”）,
若为非负值表示当前的空闲资源数，
若为负值其绝对值表示当前等待临界区的进程数。

3.3AND型信号量

基本思想:将进程在整个运行过程中所需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。

SWait(S1, S2, …, Sn)if (S1 >=1 && … && Sn>=1)for( i=1;i<=n;i++)Si= Si -1 ;elsePlace the process in the waiting queue associated with the first Si found with Si <1,and set the program counter of this process to the beginning of Swait operationSSignal(S1, S2, …, Sn)for (i=1;i<=n;i++)Si= Si +1 ;Remove all the process waiting in the queue associated with  Si into the ready queue

3.4信号量集

对信号量集S的测试值不再是1，而是该资源的分配下限值t，要求S>=t，否则不予分配。

一旦分配，进程对该组员的需求值为di，即资源占有量，进行Si=Si-di的操作，而不是简单的Si-1。

SWait(S1, t1, d1, …, Sn, tn, dn)if (S1>= t1 && … && Sn>= tn )for (i=1;i<=n;i++)Si= Si - di ;elsePlace the executing process in the waiting queue of the first Si with Si < ti and set its program counter to the beginning of the Swait OperationSSignal(S1, d1, …, Sn, dn)for( i=1;i<=n;i++)Si= Si +di ;Remove all the process waiting in the queue associated with  Si into the ready queue

4、信号量的应用

4.1利用信号量实现进程互斥

为使多个进程能互斥的访问某临界资源，只需为该资源设置一互斥信号量(mutex)，初值设为1.

//进程一
Wait(mutex);临界区
Signal(mutex);剩余区
//进程二
Wait(mutex);临界区
Signal(mutex);剩余区

注意:

为临界资源设置一个互斥信号量mutex，其初值为1
在每个进程中将临界区代码置于Wait(mutex)和Signal(mutex)原语之间
必须成对使用Wait和Signal原语：遗漏Wait原语则不能保证互斥访问，遗漏Signal原语则不能在使用临界资源之后将其释放（给其他等待的进程）
Wait、Signal原语不能次序错误、重复或遗漏

4.2利用信号量实现前趋关系

设有两个并发执行的进程P1和P2，P1中有语句S1，P2中有语句S2，希望在S1执行后再执行S2。
需要为进程P2设置一个信号量S，表示前趋是否完成，并赋予其初值为0，将signal(S)操作放在语句S1后面，而在S2语句前面插入wait(S)操作。

5、经典进程的同步问题

1.生产者-消费者问题

问题描述:假设在生产者和消费者之间的公用缓冲池中具有n个缓冲区，利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty与full分别表示缓冲池中空缓冲池和满缓冲池的数量。

semaphore mutex=1,empty=n,full=0
#生产者
void producer()
{wait(empty);//申请空缓冲区wait(mutex);//申请缓冲池...signal(mutex);signal(full)
}#消费者
void consumer()
{wait(full);wait(mutex);...signal(mutex);signal(empty);
}

2.哲学家就餐问题

问题描述:

五位哲学家围桌而坐,哲学家在思考问题时不需要任何资源，思考完问题后进入进餐态。
每人必须获得左右两支筷子才能进餐,进餐完毕后，放下筷子继续思考。

1.利用记录型信号量解决

semaphore  chopstick[5]={1,1,1,1,1}while(true){wait(chopstick[ i ]);wait(chopstick[ ( i +1) %5] );...eat;...signal(chopstick[ i ]);signal(chopstick[ ( i +1) % 5] );...think;
}

2.利用AND型信号量解决

semaphore chopstick[5] ={1, 1, 1, 1, 1};
Process i(){   while(true){think;Swait(chopstick[ ( i +1) % 5] , chopstick[ i ] );eat;Ssignal(chopstick[ ( i +1) % 5] , chopstick[ i ] );     }
}