操作系统（五）锁、信号量与管程

竞态条件/Race condition：系统缺陷——结果依赖于并发执行或事件的顺序，时间（不确定性，不可重现）

原子操作/Atomic Operation：一次不存在任何中断或失败的执行

要么执行成功，要么根本没有执行，并且不应该发现任何部分执行的状态

临界区/Critical Section：值进程中的一段代码区域，这段区域需要访问共享资源，并且当另一个进程处于相应代码区域时便不会执行

互斥/Mutual Exclusive：当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并访问任何相同的资源

死锁/Dead Lock：两个或以上的进程，在互相等待完成特点的任务，而最终没法将自身任务进行下去

饥饿/Starvation：一个可执行的进程，被调度器持续忽略

锁/Lock：

lock.acquire()：在锁释放前一直等待，直到获得锁
lock.release()：解锁并唤醒任何等待中的进程

在临界区执行的属性：

互斥：同一临界区最多存在一个线程
progress：若一个线程想进入临界区，那么它最终会成功
有限等待：若一个线程处于入口区，在其请求被接受之前，其他线程进入临界区的时间是有限的
无忙等待(可选)：若一个进程在等待进入临界区，那它可以在进入前被挂起

1.实现锁的方法

方法一：禁用硬件中断

仅限单处理器
没有中断，没有上下文切换，因此并发不存在
进入临界区：禁用中断
离开临界区：开启中断

缺点：

一旦禁用中断，线程就无法停止，整个系统都要为它停下来。可能会导致其他进程处于饥饿状态
无法限制响应中断所需时间（临界区任意长？）

方法二：基于软件

Peterson算法

使用两个共享项

int turn; //指示该谁进入临界区
bool flag[]; //进程是否准备好进入临界区

进程[latex]P_i[/latex]的算法：

do
{
	flag[i] = true;
	turn = i;
	while (flag[i] && trun == i)
		CRITICAL SECTION;
	flag[i] = false;
	REMINDER SECTION;
} while (true);

Bakery算法——N个进程的临界区

进入临界区，进程接收一个数字
得到数字最小的进入临界区
若进程[latex]P_i[/latex]和[latex]P_j[/latex]得到的数字相同，则比较i和j的大小，小的进入临界区
编号方案总是按照枚举的增加顺序生成数字

方案三：更高级的抽象

特殊的原子操作指令，通过特殊内存访问电路

原子指令：Test-and-set/测试与置位

从内存中读取值
测试该值是否为一（返回真假）
内存值置为1

bool TestAndSet(bool *target)
{
	bool rv = *target;
	*target = true;
	return(rv);
}

忙等待

class Lock {int value = 0;};

Lock::Acquire()
{
    while(TestAndSet(value)
};

Lock::Release()
{
    value = 0;
}

无忙等待

class Lock {int value = 0; waitQueue q;};

Lock::Acquire()
{
    while(TestAndSet(value)
    {
        add this TCB to waitQueue q;
        schedule();
    }
};

Lock::Release()
{
    value = 0;
    remove a thread t from q;
    wakeup(t);
}

原子指令：Exchange/交换

交换内存中的两个值

void exchange(bool* a, bool* b)
{
	bool temp = *a;
	*a = *b;
	*b = temp;
}

共享数据：int lock = 0;

int key;

do
{
	key = 1;

	while (key == 1)
		Exchange(lock, key);
	CRITICAL SECTION;

	lock = 0;
	REMINDER SECTION;
}

基于原子操作的机器指令

优点：

适用于单处理器或则共享多处理器的多处理的任意数量的进程
简单，并易证明
可以用于支持多临界区

缺点：

忙等待消耗处理器时间
当进程离开临界区并且多个进程在等待，可能会导致饥饿
死锁（实时系统中），例如：一个低优先级的进程拥有临界区并且一个高优先级进程也需求，那么高优先级的进程会获得处理器并等待临界区

Pages: 1 2 3 4 5

操作系统（五）锁、信号量与管程

Comments | NOTHING

取消回复