Deniffer's Blog
Deniffer's Blog

MIT6.S081之lock

Deniffer Deniffer 收录于 Operating System  MIT 6.S081
   约 3796 字  预计阅读 8 分钟   - 次阅读    - 条评论  

Lock

说起锁，大家都应该不陌生吧，在资源竞争(race condition)的时候,我们会习惯性的给资源加上锁，以达到正确访问和正确修改的目的。 本次记录主要是以问答形式

why lock？

  • 当我们的应用程序想要在multi-core的os上跑，并且想利用多核来提升性能的时候，我们就需要一些机制来保证多核访问不会对程序的正确性产生影响，也就是说这种机制应该是透明的。如何保证多核访问不会对程序的正确性产生影响呢，这里我们自然而然的想到，什么时候多核访问会导致程序的错误呢？

  • 其实说起来，你要会用锁的前提是你要知道os是怎么调度process(thread),你要知道并行到底是一个怎么样的一个概念。

    • 并行，在我看来可以分成两种，一种是进程间的并行，另外一种是线程中的并行。如果是进程中的并行，也需要一些锁来保证对共享数据结构(shared data structure)的正确访问，还有就是IPC(inter-Process communication)对缓冲区的读写问题。但是我们更关心的是单进程多线程的并行，这里就提及一下线程模型

      • 简单聊聊线程模型的问题，我们可能在书上看到过，什么一对一线程模型，一对多线程模型，多对多线程模型，可能很多人都不理解为什么只有1:1模型才能充分利用多核cpu的优势，这里我来简单聊聊。

        • 所谓一对一线程模型，就是指每一个user level thread 都有一个kernel level thread与其对应。Linux的thread实现就是一对一模型（），每一个用户线程都有一个task_struct结构(记住我们需要有task_struct结构cpu才能调度一个thread)，这个时候在内核的视野中，他是看得到多个threads，并且有能力调度该进程的不同thread在不同的cpu上，并行执行。

          （也就是说当其中一个用户thread被阻塞，或者睡眠是不影响其他thread执行的，cpu仍然可以调度其他的线程），其实在Linux内核的眼里，thread和process的概念其实是差不多的(可以说Linux里面没有thread，其实thread只是一个抽象的概念，指一个指令流)，只是Linux支持了light-wight process 共享memory(不同的task_struct共享同一个进程空间)，体现了thread的思想，所以我们习惯性地称这种抽象的封装为thread。 只有这种情况下，我们来聊一聊多线程模型，什么是多线程呢？我们先得说一下单线程模型，所谓单线程，在我眼里就是指程序的入口只有一个，程序必须串行的执行下去，而多线程模型就可以有多个入口，可以并行地执行多个执行流，这就是所谓的多线程模型。

        • 所谓多对一线程模型，就是指多个user level threads 对应一个kernel level thread，在Linux的眼里，整个用户程序就只有一个thread，所以也只有一个kernel thread去与其对应，一旦用户的某一个thread被阻塞掉，整个kernel thread也会阻塞，所以就算该进程有其他可以执行的线程也会同时被阻塞掉。(用户的thread 对于内核来说是不可见的)

        • 然后就是多对多模型 就是mix上述两个模型的，但其实应用起来会比较难，我没有太深的了解（不然的话Linux为什么不用multi->multi呢?

    • 这里聊一下不同线程模型的优缺点，

      • 1：1模型很棒！可以充分发挥多cpu的优势，就算某个thread 被阻塞掉也不影响其他thread的运行(除非thread之间有拓扑关系)，缺点就在于需要内核来进行调度，因为对内核来说调度是按照一定规则执行的，用户thread无法干涉内核的调度策略，这就导致了内核不可能知道什么时候去调度是一个perfect time ，还有就是thread切换需要陷入内核，开销会比较大。
      • 多对一模型，缺点：无法充分利用多cpu的优势，同一个时刻只有一个thread被执行，受限于单个cpu的执行效率。优点：被用于user level thread的实现，thread switch代价低，不需要陷入内核，基本上可以看成没有任何的switch的代价，其次就是可以自定义调度策略，因为user level thread是由用户指定调度策略的，所以你可以按照实际需求个性化制定调度策略 ，以满足快速响应等场景。

  • 回到刚刚的问题，什么时候多核访问会导致程序的错误运行呢，或者说用锁可以避免什么错误呢？

    1. 锁可以避免丢失更新，也就是说当一个thread更新一个shared data structure 的时候，上锁可以保证这次更新是原子性的，要么更新成功，要么更新失败。不存在说更新一半，data structure就被别的thread更新的这种情况。回想我们之前在kalloc.c中的例子，丢失更新是指我们丢失了对于某个内存page在kfree函数中的更新。如果没有锁，在出现race condition的时候，内存page不会被加到freelist中。但是加上锁之后，我们就不会丢失这里的更新。
    2. 锁可以打包多种操作，使其具有原子性，这种区域我们称之为critical section，如果往critical section加锁的话，整个critical section的操作都会是原子性的。
    3. 锁可以维护共享数据结构的不变性。共享数据结构如果不被任何进程修改的话是会保持不变的。如果某个进程acquire了锁并且做了一些更新操作，共享数据的不变性暂时会被破坏，但是在release锁之后，数据的不变性又恢复了。

When to use lock

一个保守的规则来说就是，当一个数据结构可以被多个进程访问的时候，其中有一个进程会更新数据的时候，就会可能产生race condition的情况，这时候我们就应该使用锁来避免这种情况的发生。 其实类似于printf等函数也是需要锁来执行序列化输出的过程。

When you have multi locks in One section

这里的解决方案是，如果你有多个锁，你需要对锁进行排序，所有的操作都必须以相同的顺序获取锁。所以对于一个系统设计者，你需要确定对于所有的锁对象的全局的顺序

Lock type

  1. Spinlock 自旋锁

    先来聊一下自旋锁实现原理是怎么样的，我们要知道单纯依靠软件是无法实现原子性的（依靠软件实现的原子性代价极高），因为任何一个语句都可能被拆分为多个micro instruction执行，也就是说在一条语句执行到一半的时候就可能被打断，从而导致程序无法达到预期的效果。

    1
2
3
4
5
6
7
8

    // Mutual exclusion lock.
struct spinlock {
  uint locked;       // Is the lock held?

  // For debugging:
  char *name;        // Name of lock.
  struct cpu *cpu;   // The cpu holding the lock.
};

    这是xv6里面关于spinlock锁的结构，非常的简洁，但是我们更关心的是spinlock如何实现acquire和release的操作

     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
28
29
30
31
32
33

    // Check whether this cpu is holding the lock.
// Interrupts must be off.
int
holding(struct spinlock *lk)
{
  int r;
  r = (lk->locked && lk->cpu == mycpu());
  return r;
}

void
acquire(struct spinlock *lk)
{
  push_off(); // disable interrupts to avoid deadlock.
  if(holding(lk))
    panic("acquire");

  // On RISC-V, sync_lock_test_and_set turns into an atomic swap:
  //   a5 = 1
  //   s1 = &lk->locked
  //   amoswap.w.aq a5, a5, (s1)
  while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;

  // Tell the C compiler and the processor to not move loads or stores
  // past this point, to ensure that the critical section's memory
  // references happen strictly after the lock is acquired.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();

  // Record info about lock acquisition for holding() and debugging.
  lk->cpu = mycpu();
}

    RISCV提供了硬件级别的swap原子操作指令(amoswap.w.aq)，也就是说有一个swap的原子指令，swap只需要一条指令就能完成.从而保证了while循环的原子性。 （Test And Set CAS）procedure below

    1
2
3
4
5

    1.  lock address 
2.  tmp <- *addr
3.  *addr <- r1
4.  r2<- tmp
5.  unlock address

Sleep lock

Sleep lock的实现相对来说就比较简单一点，简单来说是利用sleep&&wakeup这两个system call来完成，

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
void
sleep(void *chan, struct spinlock *lk)
{
  struct proc *p = myproc();
  
  // Must acquire p->lock in order to
  // change p->state and then call sched.
  // Once we hold p->lock, we can be
  // guaranteed that we won't miss any wakeup
  // (wakeup locks p->lock),
  // so it's okay to release lk.

  acquire(&p->lock);  //DOC: sleeplock1
  release(lk);

  // Go to sleep.
  p->chan = chan;
  p->state = SLEEPING;

  sched();

  // Tidy up.
  p->chan = 0;

  // Reacquire original lock.
  release(&p->lock);
  acquire(lk);
}

// Wake up all processes sleeping on chan.
// Must be called without any p->lock.
void
wakeup(void *chan)
{
  struct proc *p;

  for(p = proc; p < &proc[NPROC]; p++) {
    if(p != myproc()){
      acquire(&p->lock);
      if(p->state == SLEEPING && p->chan == chan) {
        p->state = RUNNABLE;
      }
      release(&p->lock);
    }
  }
}

其实你只要了解p->chan && p->state 这两个成员的属性就可以了解sleep lock是怎么实现的了， 首先要理解sleep的函数签名 sleep(void* chan,struct spinlock * lk); 首先要清楚一点的是，这里的void* chan,可以是任意一个地址！比如一个structure process实例 的地址，一个structure sleeplock的地址，为什么用的是void* 这里要明白。你可以简单理解chan为导致sleep的原因，当你理解了这个概念之后，你就可以明白sleep && wakeup的精髓。 wakeup就是遍历所有的process，如果是因为chan的原因导致的sleep，则唤醒该进程(change p->state to runnable).More interesting things,其实sleep lock的实现是有借助spinlock的

**所谓的锁，在计算机里本质上就是一块内存空间。**当这个空间被赋值为1的时候表示加锁了，被赋值为0的时候表示解锁了，仅此而已。多个线程抢一个锁，就是抢着要把这块内存赋值为1。在一个多核环境里，内存空间是共享的。每个核上各跑一个线程，那如何保证一次只有一个线程成功抢到锁呢？你或许已经猜到了，这必须要硬件的某种guarantee。具体的实现如下。

Lock problem

1.Dead lock

  1. one process acquire one lock(spinlock) twice!

  2. two processes acquire two lock .

2. Locks VS Modularity
3.Locks VS performance

​ 解决方法，先用全局锁，测试，慢慢将锁的范围变小。

Memory Ordering

​ instruction reordering is wrong in concurrent execution.__sync_synchronize(); 防止指令重排！提供了类似于barrier的区域，保证指令的顺序执行。

更新于 2021-09-09 
CC BY-NC 4.0
 Operating System, MIT 6.S081
返回 | 主页
0%