进程的同步机制

一.基本概念

1.进程同步机制的概念

多个进程（线程）在执行次序上的协调关系的机制称为进程同步机制。

2.为何要引入进程同步机制

由于操作系统中的进程是并发的，因此当协同进程对共享数据进行访问时，可能会造成数据的不一致性问题。为了保证数据的一致性，那么我们就需要一种有效地机制，这就是被我们称之为的进程同步机制。

3.临界资源

临界资源是指一次仅允许一个进程（线程）使用的资源，比如某个变量i（逻辑资源），打印机（物理资源）等等。

4.临界区

临界区是指并发执行的进程中，访问临界资源必须互斥执行的程序段。

二.进程同步与互斥关系

1.同步

多个并发进程（线程）协同完成一项任务时，由于数据交换需要而在进程（线程）执行次序上的约束关系，交同步关系。比如“司机和售票员”问题描述的就是同步关系。

2.互斥

并发进程（线程）间为竞争统一资源而间接发生的相互制约关系，叫互斥关系。比如两个进程同时需要完成打印任务，描述的就是互斥关系。

三.进程同步机制的四个基本原则

1.空闲让进

当没有进程在临界区时，它处于空闲状态，任何请求临界资源的进程都可以进入临界区。

2.忙则等待

当已有进程正在访问临近区时，其他任何进程都必须等待，以保证互斥地访问临界资源。

3.有限等待

进程必须在有限的时间内进入临界区，避免长时间处在“饥饿”状态。

4.让权等待

当进程不能进入自己的临界区时，应立即释放CPU资源，以免进程陷入忙等状态。

四.软件和硬件同步方法

1.软件方法

这种方法虽然会对临界资源是否正在被访问进行判断，但是两个进程有可能同时进入临界区。

2.硬件方法

五.信号量机制

概述

1965年，荷兰学者Dijkstra提出的信号量（Semaphores）机制是一种卓有成效的进程同步工具。 在长期且广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量经记录型信号量，进而发展为“信号量集”机制。 现在，信号量机制已经被广泛地应用于单处理机和多处理机系统以及计算机网络中。 --源自百度百科

总结来说信号量机制就是一种进程同步的工具。

1.整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S，它只能被两个标准的原语wait(S)和signal(S)来访问，分别被称为为“P”操作和“V“操作，它们中的操作都是原子操作。它的伪代码如下：

void wait(S) {
     while (S<=0);	//此时如果S<=0，申请资源的进程就会在此处一直处于忙等状态
     S=S-1;
}

void signal(S) {
     S=S+1;
}

2.记录型信号量

它的伪代码如下：

void wait(semaphore S) { //这里的S是一个结构体
    --S.value;	//value为记录资源数目的变量
    if(S.value < 0)	//注意这里的判断条件是<0
    	block(S.L);	//将申请资源的进程阻塞并添加到等待队列中，程序计数器定位到wait操作后
}

void signal(semaphore S) {
    ++S.value;
    if(S.value <= 0) //注意这里的判断条件是<=0
    	wake(S.L);	//唤醒队首等待的进程，唤醒后执行wait后的代码
}

typedef struct{  
    int value; 			//大于0时表示资源数量，小于0时它的绝对值表示已阻塞的进程数目  
    struct process *L;  //进程阻塞队列
} semaphore;

3.AND型信号量

当一个进程需要同时获取多个资源时，就需要用到AND型信号量了

void Swait(S1, S2, ... , Sn) {
     if (S1>=1 && S2>=1 && ... && Sn>=1)  //进程需要访问的资源是否全都可用
         for (int i=1; i<n; i++)
             Si = Si - 1;
     else 
         //自我阻塞，将当前进程放置阻塞队列中
}
 
void Ssignal(S1, S2, ... , Sn) {
     for (int i=1; i<n; i++)
         Si = Si + 1;	//同时唤醒等待队列中的所有进程
}

4.信号量集

当一次需要n中资源且资源Si申请di个资源，该类资源的可用数低于某个下限值ti时不予分配，这样就需要对AND型信号量机制加以扩充，形成信号量集机制：

Swait(S1, d1, t1, ... , Sn, dn, tn){
     if (S1>=t1 && ... && Sn>=tn )
         for (int i=1; i<=n; i++)
             Si = Si - di;
     else 
         //自我阻塞，插到第一个Si<ti的队列Si.L，并将程序计数定位到Swait操作的起点
}

Ssignal(S1, d1, ... , Sn, dn,){
     for (int i=1; i<=n; i++)
         Si = Si + dn;	//唤醒Si.L的所有进程
}

六.Linux中的信号量

Linux中的信号量使用时需要导入semaphore.h头文件

1.定义信号量

sem_t i;

2.信号量的初始化

int sem_init(sem_t *sem, int pshared, unsigned int value)

3.wait，signal操作

sem_wait(sem_t *sem);

sem_post(sem_t *sem);

4.销毁信号量

sem_destroy(sem_t *sem);