操作系统笔记------进程同步（1）

发表于 | 更新于 | 分类于

产生原因

在多道程序环境下进程的并发进行，常常伴随着对系统资源的共享与竞争，有些资源之间可以共享，有些则是以独占的方式供进程使用，因此会产生进程之间的相互制约关系。

  1. 间接的相互制约：共享某种系统资源（互斥）
  2. 直接的相互制约：主要源于进程间的合作（同步）

这里的共享资源是指对资源的独占式访问，而进程间的合作是指程序的运行依赖于其他程序的运行结果。这里共享的系统资源往往成为临界资源。

临界资源

一次仅能为一个进程所使用的资源称为临界资源。例如内存变量，数组，指针等都可以成为临界资源。

临界区

在程序中的体现为在进程中访问临界资源的代码段称为临界区。
临界资源之间的访问互斥具体到对临界区访问互斥。

访问控制模型

大致分为4部分即：进入区，操作区，退出区，后续操作。

  1. 进入区是对临界资源进行访问请求，在这一区域进行占用判断，保证进程对资源的独占式访问。
  2. 操作区这里就已经获得了对资源的访问许可，直接进行相关的逻辑操作就可以了。
  3. 退出区就是释放对临界资源的占用以供其他的进程使用。
  4. 后续的操作就是继续进行进程中的其他操作，这些操作无需对临界资源进行访问（需要临界资源的都在操作区完成了）。

同步机制原则

  1. 空闲让进：当无进程处于临界区时，请求进入临界区的进程可立即进入。
  2. 忙则等待：当已有进程进入临界区时，其他试图进入临界区进程须等待
  3. 有限等待：对要求访问临界资源进程，保证能在有限时间内进入临界区
  4. 让权等待：当进程不用进入临界区时，应释放对临界区的占用。

锁（Lock）

锁，门之键也，古谓之键，今谓之锁。
锁一般是私有的象征，这里的门也就是对临界资源的访问，每个进程的访问都是“私有的”，也是互斥的，这样才能保证数据操作的同步。在系统中也使用了锁的设计，操作系统中有锁，JVM中也有，很多的编程语言中有也，Lock几乎成为了数据同步的象征。

原子性

在cpu处理并发时往往是以时间片的方式来分配使用权来让不同的进程运行相应代码，这导致了一个代码块往往只执行了一部分就用完了时间片的时间，就跳到了另一个进程中运行了，而且由于时间片与程序运行的不确定性，这种跳转是难以预测与控制的。而原子性保证的就是程序的操作中不会产生间断跳转，也就是说，所有的操作一旦开始就必须执行完成，不会被其他的进程干扰。

原语

实现了原子性的程序（函数或程序段）称为原语。具有不可分割性与执行连续性，执行过程中不会被中断。

软件同步

进程一内部操作

1
2
3
4
5
6
7
while(true)
{
	enter_region(0); 
	sectionWithResource();
	leave_region(0); 
	sectionWithOutResource();
}

进程二内部操作

1
2
3
4
5
6
7
while(true)
{
	enter_region(1); 
	sectionWithResource();
	leave_region(1); 
	sectionWithOutResource();
}

Dekker算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define FALSE 0
#define TRUE 1
#define N 2 // 进程的个数
int turn; // 轮到哪个进程
int interested[N]; // 初始值均为FALSE,标志有那些进程已提出了请求
//请求临界资源
void enter_region (int process)// process = 0 或 1
{
	int other = 1 - process;// 另外一个进程的进程号
	interested[process] = TRUE;// 表明本进程提出请求
	while(interested[other])
	{
		if(turn != process)//检查是否排上了队
		{
			interested[process] = FALSE;//没排上就撤销请求
			while(turn == other);//继续排队
			interested[process] = TRUE;//排上就继续请求
		}
	}
}
//释放临界资源
void leave_region ( int process)
{
	int other = 1 - process;
	turn = other;//转让访问权
	interested[process] = FALSE; // 本进程已离开临界区，撤销请求
}

这里在理解时注意，在以上函数的各个语句之间，cpu都可能导致其发生进程跳转，在此基础上使用了一个标志数组interested与一个状态变量turn，完成了进程同步。

Peterson算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define FALSE 0
#define TRUE 1
#define N 2 // 进程的个数
int turn; // 轮到哪个进程
int interested[N]; // 初始值均为FALSE,标志有那些进程已提出了请求
//请求临界资源
void enter_region (int process)// process = 0 或 1
{
	int other; // 另外一个进程的进程号
	other = 1 - process;
	interested[process] = TRUE;// 表明本进程提出请求
	turn = process; // 设置标志位
	while( turn == process && interested[other] == TRUE);//如果轮到该进程但是之前已有进程提出请求就死循环等待。
}
//释放临界资源
void leave_region ( int process)
{
	interested[process] = FALSE; // 本进程已离开临界区
}

Peterson算法在实现上更加简单，两者实现的思想几乎是类似的，使用的数据结构也相同，只是在逻辑处理上少有不同。

硬件同步

基于SWAP指令

SWAP指令用于交换俩个变量（寄存器）的值，该指令自身保证了操作的原子性，是同步实现的基础。
SWAP的C语言描述。

1
2
3
4
5
6
7
void SWAP(boolean *lock, boolean *key) 
{ 
	boolean tmp;
	tmp=*lock;
	*lock=*key;
	*key=tmp;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean lock=false;//lock为全局变量，初始为false
void enter_region(boolean lock) 
{
	boolean key= true; //局部变量 
	while(key!=false)//在没有进程使用时lock为false，交换后跳出循环获取访问权限。
	{
		SWAP(&lock,&key);
	}
}

void leave_region(boolean lock) 
{
	lock= false;//使用结束释放锁
}