阅读 144

操作系统系列(一)同步

协作进程能与系统内的其他执行进程相互影响。协作进程或能直接共享逻辑地址空间(即代码和数据)--可通过线程来实现,或能通过文件或消息来共享数据。共享数据的并发访问可能导致数据的不一致性。本文讨论多种机制,以便确保共享数据的协作进程有序执行,从而维护数据的一致性。
首先,先了解几个概念:

  1. 竞态条件(race condition),所谓的竞争条件是指多个进程并发访问和操作同一数据,并且执行结果与特定访问顺序有关。
  2. 抢占式内核:处于内核模式的进程被强占。响应更快、适用于实时编程;
  3. 非抢占式内核:不允许处于内核模式的进程被强占。基本不会导致竞争条件;

本文将从如下两个方面进行讨论:
1)临界区问题,以及解决方案(软件或硬件解决方案);
2)进程同步问题,以及解决方案(同步工具);

临界区问题

do {
	进入区
		临界区
	退出区
		剩余区

} while(true);
复制代码

临界区问题的解决方案的要求:
1)互斥:如果进程P在其临界区内执行,那么其他进程都不能在其临界区内执行;
2)进步:如果没有进程在其临界区内执行,并且有进程需要进入临界区,那么只有那些不在剩余区内执行的进程可以参加选择,以便确定谁能下次进入临界区,而且这种选择不能无限推迟;
3)有限等待:从一个进程做出进入临界区的请求直到这个请求允许为止,其他进程允许进入其临界区的次数具有上限;

软件解决方案 --Peterson

在现代计算机体系结构上并不能保证正确工作。

进程Pi的结构

do {
	flag[i] = true;	 	// 先设置当前进程Pi希望进入临界区
	turn = j;			// 将turn设置为j,如果最终turn成功设置为j,进程j设置flag[j]成功,则下面进程j将进入忙等待
	while(flag[j] && turn == j) ;	//  进程j设置flag[j]成功,则下面进程j将进入忙等待
	
	临界区
	
	flag[i] = false;
	
	剩余区
} while(true);
复制代码

硬件解决方案 --基于“锁”实现

硬件功能能够简化编程工作而且提高系统效率。

  1. 单处理器环境:禁止中断可以解决;
  2. 多处理器环境:特殊硬件指令(由test_and_set、compare_and_swap对其进行抽象),原子地执行

test_and_set

基于test_and_set指令(对特殊硬件指令的封装)的实现,还是通过“忙等待”来解决临界区问题。

boolean test_and_set(boolean *target) {
	boolean rv = *target;
	*target = true;
	return rv;
}

// 不满足有限等待条件
do {
	// 如果&lock为false,表示锁尚未被使用,test_and_set将设置&lock为true,并返回false,退出死循环,执行临界区。
	while(test_and_set(&lock) ;
	
	临界区
	
	lock = false;	// 将lock设置为false,表示解锁
	
	剩余区
} while(true);

// 有限等待:
do {
	waiting[i] = true;
	key = true;
	
	// 判断锁是否可用,如果可用,则进程i不等待,进入临界区执行
	while(waiting[i] && key) {
		key = test_and_set(&lock);
	}
	waiting[i] = false;
	
	临界区
	
	// 获取下一个进程索引
	j = (i+1)%n;
	// 通过循环的方式,获取在等待执行的下一个进程索引,可以实现有限等待
	while(j != i && !waiting[j]) {
		j = (j+1)%n;
	}
		
	if(j == i) {	// 如果 j == i 表示同一个进程,可以解锁
		lock = false;
	} else {		// 如果 j != i 表示不同进程,则取消等待j,准备进入临界区
		waiting[j] = false;
	}
		
	剩余区
} while(true);
复制代码

compare_and_swap

基于compare_and_swap指令(对特殊硬件指令的封装)的实现,还是通过“忙等待”来解决临界区问题。

int compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
	if(*value == expected) {
		*value = new_value;
	}
	return temp;	// 返回原先值
}

// 不满足有限等待条件
do {
	// 初始情况下,lock=0,调用compare_and_swap后,lock为1并返回原先值为0,跳出循环执行临界区
	while(compare_and_swap(&lock, 0, 1) != 0) ;
	
	临界区
	
	lock = 0;	// 释放锁
	
	剩余区

} while(true);
复制代码

同步问题

经典的同步问题

有界缓冲区问题

读者-作者问题

哲学家问题

同步工具

互斥锁(mutex)

每个互斥锁有一个布尔变量available,它的值表示锁是否可用。如果锁可用时,那么调用acquire()会成功,并且锁不再可用。当一个进程试图获取不可用的锁时,那么调用acquire()会阻塞,直到锁被释放。
当有一个进程在临界区中,任何其他进程在进入临界区时必须连续循环地调用acquire()。其实,这种类型的互斥锁也被称为自旋锁,因为进程不停地旋转,以等待锁变得可用。忙等待会浪费CPU周期,而这原本可以有效用于其他进程。

acquire() {
	while(!available) ;		// 忙等待
	available = false;
}

release() {
	available = true;
}
复制代码

注意:

  1. 对acquire()或者release()的调用必须原子地执行。
  2. 自旋锁通常用于多处理器系统、锁时间比较短。

信号量(semaphone)

一个信号量S是个整型变量,它除了初始化外只能通过两个标准原子操作:wait()和signal()来访问。

计数信号量 --可用资源数
二进制信号量 --类似于互斥锁

wait()称为P

wait() {
	while(S <= 0) ;
	S--;
}
复制代码

signal()称为V

signal() {
	S++;
}
复制代码

上述实现还是具有忙等待,我们可以通过下面的修改,实现非忙等待!

注意:在wait()和signal()操作中,信号量S整数值的修改应原子地执行。

信号量的实现:当一个进程执行操作wait()并且发现信号量不为正时,它必须等待。然而,该进程不是忙等待而是阻塞自己。阻塞操作将一个进程放到与信号量相关的等待队列中,并且将该进程状态切换成等待状态。然后,控制转到CPU调度程序,以便选择执行另一个进程。 等待信号量S而阻塞的进程,在其他进程执行操作signal()后,应被重新执行。进程的重新执行是通过操作wakeup()来进行的,它将进程从等待状态改为就绪状态。然后,进程被添加到就绪队列中准备由CPU来调度执行。

typeof struct {
	int value;				// 信号量
	struct process *list;	// PCB链表
}semaphone;


wait(semaphone *S) {
	S->value--;
	if(S->value < 0) {
		将该进程添加到S->list中;
		block(); 
	}
}

signal(semaphone *S) {
	S->value++;
	if(S->value <= 0) {
		从S->list队列中删除一个进程P;
		wakeup(P);
	}
}
复制代码

注意:

  1. block()和wakeup(P)都是由操作系统作为基本系统调用来提供的;
  2. 如果信号量为负数,那么它的绝对值就是等待它的进程数。
  3. S->list是PCB链表;
  4. 信号量操作(wait和signal方法)应原子地执行;

同步案例

Windows同步

单处理器系统:禁用中断;
多处理器系统:自旋锁,处于效率原因,内核确保决不强占拥有自旋锁的线程。

内核外的线程同步,Windows提供调度对象。采用调度对象,有多种不同的线程同步机制,包括互斥锁、信号量、事件和定时器等。
调度对象可以处于触发状态(表示对象可用,线程在获取它时不会阻塞)或非触发状态(表示对象不可用,线程在试图获取它时会阻塞)。 当一个线程阻塞在非触发对象上时,它的状态从就绪变为等待,而且它会添加到那个对象的等待队列。当调度对象状态变为触发时,内核检查是否有线程正在等待这个对象。如果有,那么内核改变一个或多个线程的状态,即从等待状态切换到就绪状态以便重新执行。内核从等待队列中选择的线程数量取决于等待的调度对象类型。对于互斥锁,内核从等待队列中只选择一个线程,因为一个互斥对象只能为单个线程拥有。对于事件对象,内核选择所有等待事件的线程。

Linux同步

Linux提供互斥锁,用于保护内核中的临界区;
Linux还提供自旋锁和信号量,用于内核的加锁;

单处理器 多处理器
禁用内核抢占 获得自旋锁
启用内核抢占 释放自旋锁

preempt_disable()与preempt_enable()用于禁用和启用内核抢占。

Pthreads同步

Pthreads API只能被用户级别的程序员使用,而不能用于任何特定内核。Pthreads API为线程同步提供互斥锁、条件变量和读写锁。
互斥锁代表Pthreads使用的基本同步技术。互斥锁用于保护代码的临界区;也就是说,线程在进入临界区之前获取锁,在退出临界区之后释放它。
Pthreads互斥锁采用数据类型pthread_mutex_t,通过pthread_mutex_init()创建互斥锁;通过pthread_mutex_lock()或者pthread_mutex_unlock()获取或者释放互斥锁。

pthread_mutex_lock(&mutex);

临界区

pthread_mutex_unlock(&mutex);
复制代码