OSTEP [并发] Chapt. 26-28 - 并发与锁

分类:Operating System, 发布于:2019-04-14 22:45:57, 更新于:2019-04-19 00:09:40。 评论

注意:本文基本是OSTEP的摘要,充满大量渣翻,建议看原著。

26 Concurrency: An Introduction

多线程的两大原因:

  • Parallelism(并发?)
  • 防止由IO操作引起的阻塞

存在的问题:未经控制的调度 + 共享数据 = 混乱的结果。需要原子性来解决。

原子性的理念:all or nothing。要么全部发生,要么一个都没发生。有时将多个操作打包为一个原子性操作的行为叫做transcation。

另一个存在的问题:相互等待。例如两个线程相互交互,共享一个变量。一个线程进行原子性操作时,另一个必须等待直到行为结束。

并发相关的关键词:

  • 临界区(critical section):访问共享资源的代码段。
  • 竞争现象(race condition, or data race):多个线程几乎同时进入临界区,尝试更新共有的数据,造成意外结果。
  • 不确定(indeterminate)的程序包含一个或多个竞争情况,运行的结果不确定。
  • 互斥(mutual exclusion):只有一个线程能够进入临界区。

27 Interlude: Thread API

头文件:<pthreads.h>。编译时需要-pthread flag。

线程创建:pthread_create函数。

线程等待:pthread_join函数。

锁:pthread_mutex_lockpthread_mutex_unlock

条件变量:pthread_cond_waitpthread_cond_signal。当一个线程希望在继续执行下去前由另一个线程执行一些操作时使用。

线程API编程指导性原则:
  • 保持简单(KISS)。
  • 最小化线程间互相的交互。
  • 初始化锁和条件变量。
  • 检查返回值。(书中原话:不检查会导致无法理解程序的行为,导致(a)尖叫、(b)扯头发或者(c)两者都发生。)
  • 小心地在线程之间传递参数、返回值。如果要引用一个分配在栈上的指针,那基本就已经f**ked up了。
  • 每个线程有自己的帧栈。线程分配的变量是private的,其他线程无法访问。要让其他线程也可访问,必须分配在堆区或者全局可见。
  • 总是使用信号变量来在线程之间传递信号。不要使用简单的变量flag来当信号。
  • 使用man pages,仔细读。

28 Locks

锁的定义

一把锁只是一个变量,因此要使用锁必须要声明一个某种类型的“锁变量”(lock variable)。这种类型的变量无论何时都保存着锁的状态。

锁只有两种状态:可用(available, unlocked, free)和被占用(acquired, locked, held)。因此,唯一拥有锁的线程很可能位于临界区中(原文:the exactly one thread holds the lock and presumably)处于临界区中。

可以在锁类型中存储更多的信息,包括持有者、等待拥有锁的队列等,但这些信息应该对锁的使用者来说不可见。

上锁和解锁

  • 调用lock()来获得锁。如果没有别的线程拥有锁,当前线程就可以拿到锁并进入临界区。有时这个线程就叫做锁的持有者(owner)。如果其他线程此时调用lock()企图获得同一把锁,那么直到持有者释放这把锁之前此次调用都不会返回。这样就可以阻止其他线程进入临界区。
  • 当持有者调用unlock()时,锁就再次可用。如果没有其他线程在等锁,那么锁就被标记为可用(free)。否则,等待的线程中会(最终)有一个注意到锁的状态发生变化,获得它并进入临界区。

锁提供给程序员最小的流程控制。通过上锁,程序员可以保证至多一个线程能够同时执行某段代码。因此锁能够改善传统OS调度导致的混乱,使得系统更加有序。

Pthread Locks

POSIX标准库提供的锁叫做mutex(互斥锁),提供线程之间的互斥。如果一个线程处于临界区,它(线程)就能阻止其他线程进入临界区,直到它(线程)完成了临界区的任务并退出。

部分POSIX版本允许上锁时传入一个锁变量,这样就可以使用不同的锁来保护不同的变量。这样做的好处是可以增加并发性:不需要一把大锁锁住所有的临界区(coarse-grained strategy),多把锁可以让更多的线程同时处于上锁的区间(fine-grained approach)。

评估一把锁

评估一把锁的基本准则:

  1. 锁能够完成基本任务:提供互斥性质。
  2. 锁的分配是公平的:不会有线程想要上锁却永远得不到它。
  3. 锁的性能是高效的:无等待时开销如何?多线程同时等待时性能又如何?多CPU情况下,每个核心中的线程都要上锁时性能又如何?

中断控制

定义:上锁=关中断,解锁=开中断。

在单处理器系统中,通过关闭中断,我们可以处于临界区中的代码不被干扰,因此它的执行是原子的。

这种做法的最大好处是简单。一个线程可以保证在执行过程中不会受到其他代码的干扰。

但这种做法的坏处有:

  • 关闭、打开中断要求允许线程进行特权操作,OS必须要信任这个应用。
  • 在多处理器中无效。
  • CPU无法处理中断可能会导致严重的系统问题(例如硬件发送了读请求,CPU无法处理)。
  • 效率低下。

因此,关闭中断仅在有限的环境下,例如原始的互斥条件下使用。在OS中这样的用法是可行的,因为OS肯定会信任自己并允许自己进行特权操作。

使用Loads/Stores:失败的尝试

只是用一个变量并使用Loads/Stores指令是不够的。

如果另一个线程在临界区时,当前线程调用了lock(),此时,它就会自旋等待(spin-wait)前一个线程解除对锁的占用。之后当前线程就会结束循环,将flag设为1(持有锁)并进入临界区。

但以上方法存在正确性与性能上的问题。

  • 如果中断时机巧妙,两个线程可以同时将flag设为1并进入临界区。
  • 如果线程想要获得一把已经被上的锁,他就会永远循环检查flag的值,造成CPU的资源浪费甚至死循环。

Test-And-Set

Test-and-set操作又被称为原子交换(atomic exchange)。

int TestAndSet (int *old_ptr, int new) {
  int old = *old_ptr;
  *old_ptr = new;
  return old;
}

此操作返回ptr处的旧数据,并同时更新其值为new。这个操作序列必须被原子性地执行。此操作用来构建自旋锁已经足够。

void lock(lock_t *lock) {
  while (TestAndSet(&lock->flag, 1) == 1)
    ; // spin-wait
}

void unlock(lock_t *lock) {
  lock->flag = 0;
}

为了让自旋锁在单CPU系统上正确工作,需要一个抢占式的调度处理器(preemptive scheduler)来根据占用时间打断、切换线程。

Test-And-Set自旋锁的评估:

  • 正确性:正确,只允许一个线程进入临界区。
  • 公平性:没有公平性。
  • 性能:单CPU中自旋开销太大;而在多CPU系统中可以认为临界区很短,因此锁很快即可回复可用并被其他线程获得,自旋不会带来太多的开销。

Compare-And-Swap

int CompareAndSwap(int *ptr, int expected, int new) {
  int actual = *ptr;
  if (actual == expected)
    *ptr = new;
  return actual;
}

以上函数会返回内存中的实际值,由此调用者即可知道其执行是否成功。使用此方法构造的自旋锁如下:

void lock(lock_t *lock) {
  while (CompareAndSwap(&lock->flag, 0, 1) == 1)
    ; // spin-wait
}

此款锁的行为与上一款锁完全一致,但对于无锁同步(lock-free synchronization)有神秘好处(书里此处没说)。

Load-Linked and Store-conditional

int LoadLinked(int *ptr) {
  return *ptr;
}

int StoreConditional(int *ptr, int value) {
  if (/* no one has updated *ptr since the LoadLinked to this address */) {
    *ptr = value;
    return 1; // success
  } else {
    return 0; // failed to update
  }
}

由此实现的锁如下:

void lock(lock_t *lock) {
  while (1) {
    while (LoadLinked(&lock->flag) == 1)
      ; // spin until it's zero
    if (StoreConditional(&lock->flag, 1) == 1)
      return; // if set to 1: success
  }
}

Fetch-And-Add

int FetchAndAdd(int *ptr) {
  int old = *ptr;
  *ptr = old + 1;
  return *ptr;
}

由此实现的门票锁(ticket lock)如下:

typedef struct __lock_t {
  int ticket;
  int turn;
} lock_t;

void lock(lock_t *lock) {
  int myTurn = FetchAndAdd(&lock->ticket);
  while (lock->turn != myTurn)
    ; // spin-wait
}

void unlock(lock_t *lock) {
  lock->turn = lock->turn + 1;
}

这款锁和之前的所有锁之间的差别是:它保证了每个线程都有机会获得锁。一旦一个线程被分配了一个ticket value,它就被安排在未来的某个时刻能够获得锁。

处理自旋循环:yield

每当自旋过程中没有获得锁时,线程执行yield()来主动放弃CPU,让下一个线程执行。

这样可以解决性能问题,但无法解决公平性(有线程无法获得锁,starvation problem)的问题。

使用队列:睡眠而不是自旋

Solaris采用的解决方案是使用两个调用:

  • park():让调用者进入睡眠状态;
  • unpark(threadID):唤醒指定的线程。
typedef struct __lock_t {
  int flag;
  int guard;
  queue_t *q;
} lock_t;

void lock(lock_t *m) {
  while (TestAndSet(&m->guard, 1) == 1)
    ; // acquire guard lock by spinning
  if (m->flag == 0) {
    m->flag = 1; // lock is acqured
    m->guard = 0;
  } else {
    queue_add(m->q, gettid());
    m->guard = 0;
    park(); // BOOOOOOOOOOOOM!
  }
}

void unlock(lock_t *m) {
  while (TestAndSet(&m->guard, 1) == 1)
    ; // acquire guard lock by spinning
  if (queue_empty(m->q))
    m->flag = 0;
  else
    unpark(queue_remove(m->q)); // hold lock
  m->guard = 0;
}

当一个进程被唤醒时,将会从park()返回;否则,他就不会持有guard锁,更不能将锁的flag设为1。因此,我们只需要将锁直接传递给下一个需要它的进程,而不能把flag清除。

但以上实现可能会出现竞争状况:一个线程即将进入睡眠,直到锁的状态被解除,但此时另一个线程刚刚好将其“唤醒”(从队列中删除),那么前者就永远无法被唤醒。这个问题也被叫做唤醒/等待竞争(wakeup/waiting race)。

Solaris的解决方案是增加第三个系统调用:setpark(),告知OS该线程即将进入睡眠状态。如果此时发生中断,另一个线程唤醒当前线程,那么下一步调用的park()就会直接返回,不会进入睡眠状态。

此外,Linux系统还提供了futex锁(Chapt. 28 P 19),略。

评论