关于操作系统:从零开始写-OS-内核-锁与多线程同步

系列目录

• 序篇
• 筹备工作
• BIOS 启动到实模式
• GDT 与保护模式
• 虚拟内存初探
• 加载并进入 kernel
• 显示与打印
• 全局描述符表 GDT
• 中断解决
• 虚拟内存欠缺
• 实现堆和 malloc
• 第一个内核线程
• 多线程运行与切换
• 锁与多线程同步
• 进入用户态
• 过程的实现
• 一个简略的文件系统
• 加载可执行程序
• 零碎调用的实现
• 键盘驱动
• 运行 shell

多线程竞争

上一篇 咱们终于运行起了多线程，并初步建设起了任务调度零碎 scheduler，使这个 kernel 终于开始显现出了一个操作系统应有的风貌。在 multi-threads 运行的根底上，接下来咱们须要进入用户态运行 threads，并且建设过程 process 的概念，加载用户可执行程序。

然而在此之前，有一个重要且危险的问题曾经随同着 multi-threads 的运行而来临，这就是线程的竞争和同步问题。置信你应该有用户态下多线程相干的编程教训，了解 threads 之间竞争同步的问题和起因，以及 lock 的概念和应用。本篇会从 kernel 的视角来扫视和探讨 lock，以及代码实现。须要阐明的是，lock 是一个宏大简单的课题，且在 kernel 和在用户态下的 lock 的应用形式和实现会有很多的不同（当然也有大部分的共通之处），本篇只是我集体浅显的了解和实现，欢送探讨和斧正。

锁 Lock

threads 之间竞争导致的数据问题，我想不用在这里多解释。通过前两篇的 thread 启动运行后，咱们应该能分明地意识到，interrupt 是随时并且在任何指令处都可能会产生的，任何非原子的操作都会导致 threads 之间的数据竞争（race）。

对于咱们当初这个 kernel，其实曾经有很多中央须要加 lock，来爱护对公共数据结构的拜访，例如:

• page fault 处理函数，调配 physical frame 的 bitmap，显然须要爱护；
• kheap，所有 threads 都在外面挖内存；
• scheduler 里的各种工作队列，如 ready_tasks；
• ……

在大多数反对多线程的编程语言里，都会有 lock 相干的概念和工具，而作为一个一穷二白的 kernel 我的项目，咱们须要本人实现之。

lock 是一门简单的课题，在平安第一的根底上，设计实现的好坏以及应用形式，会极大地影响零碎的性能。坏的 lock 设计和应用，可能会导致 threads 的不合理调度和 CPU 工夫的大量节约，升高零碎吞吐性能。

接下里咱们从 lock 的底层原理登程，探讨几种常见的 lock 的分类和实现形式，以及它们的应用场景。

原子指令操作

从逻辑上讲，lock 的实现很简略：

if (lock_hold == 0) {
  // Not locked, I get the lock!
  lock_hold = 1;
} else {// Already locked :(}

这里 lock_hold 保留了以后状态是否上锁，值为 true / false。试图拿锁的人，首先查看它是否为 0，是 0 则示意 lock 还未被其它人持有，则我能够拿到 lock，并设为 1，示意锁上，避免前面再有人失去 lock。

然而下面实现的谬误之处在于，if 条件的判断和上面的设置 lock_hold = 1 两步操作并非是原子的，两个 threads 可能都在 lock_hold 是 0 且对方还未来得及批改 lock_hold = 1 的状况下执行 if 判断并且都通过，一起拿到 lock 并进入。

这外面的外围问题是对 lock 的判断和批改这两步操作不是原子的，也就是说它们不是一条指令实现的，那么两个 threads 在这外面的穿插运行可能会导致数据 race。

所以任何 lock，最底层实现必须是一条原子指令，即应用一条指令，实现对数据的 测验 和 变更，它保障了只有一个 thread 能顺利通过该指令，而将其它挡在门外，例如：

uint32 compare_and_exchange(volatile uint32* dst,
                            uint32 src);

它必须由汇编实现：

compare_and_exchange:
  mov edx, [esp + 4]
  mov ecx, [esp + 8]
  mov eax, 0
  lock cmpxchg [edx], ecx
  ret

cmpxchg 指令是一条 compare and exchange 指令，它的作用是比拟第一个操作数和 eax 的值：

• 如果雷同，则将第二个操作数加载到第一个操作数中；
• 如果不同，则将第一个操作数的值，赋值给 eax；

（cmpxchg 后面加上 lock 前缀，使该指令在多核 CPU 上执行时保障对内存的拜访是独占（exclusive）的且能被其它 core 感知（visible）的，这里波及到了多核 CPU 的缓存一致性等问题，你能够临时跳过。对于咱们的我的项目试验用的单核 CPU 而言，lock 前缀不是必须的。）

实际上这条指令就实现了对于 查看并批改 操作的原子合并。咱们用它实现 lock 的逻辑，以操作数 dst 来标记 lock 是否曾经被锁上，将它和 eax = 0 比拟：

• 如果相等，那么就是第一种状况，0 阐明没有锁上，那么将 1 赋值给 dst，示意拿到 lock 并且上锁，返回值是 eax = 0；
• 如果不等，那么阐明 dst 曾经等于 1，lock 曾经被他人上锁，那么就是第二种状况，将 dst = 1 值赋值给 eax，返回值是 eax，它曾经被批改为 1；

int lock_hold = 0;

void acquire_lock() {if (compare_and_exchange(&lock_hold, 1) == 0) {// Get lock!} else {// NOT get lock.}
}

除了cmpxchg 指令，还有一种实现形式是 xchg 指令，我个人感觉更好了解：

atomic_exchange:
  mov ecx, [esp + 4]
  mov eax, [esp + 8]
  xchg [ecx], eax
  ret

xchg 指令，有两个操作数，它示意替换它们的值，而后 atomic_exchange 函数会返回替换后的第二个操作数的值，实际上也就是第一个参数替换前的旧值。

那如何用 atomic_exchange 来实现 lock 的性能？一样的代码：

int lock_hold = 0;

void acquire_lock() {if (atomic_exchange(&lock_hold, 1) == 0) {// Get lock!} else {// NOT get lock.}
}

试图拿锁的人，总是用 1（上锁）这个值，去和 lock_hold 替换，所以 atomic_exchange 函数，永远返回 lock_hold 的旧值，行将 lock_hold 的旧值替换进去并返回，只有当 lock_hold 旧值为 0 时，下面的判断能力通过，示意锁之前没有被人持有，继而胜利拿锁。

能够看到这里也只用了一条指令，实现了对 lock_hold 的变更和查看，乏味的是它是先变更，而后查看，但这丝毫不影响它的正确性。

自旋锁 spinlock

下面探讨了 lock 的 acquire 操作的底层实现，然而这只是 lock 相干问题的冰山一角。lock 真正的简单的中央在于 acquire 失败后的解决，这也是一种很重要的用来对 lock 的分类形式，它极大地影响 lock 的性能和应用场景。

这里首先要探讨的一种最简略的 lock 类型就是自旋锁（spinlock），它在 acquire 失败后会一直重试直到胜利：

#define LOCKED_YES  1
#define LOCKED_NO   0

void spin_lock() {while (atomic_exchange(&lock_hold , LOCKED_YES) != LOCKED_NO) {}}

这是一种 busy wait 的形式，以后 thread 持续持有 CPU 运行，不停地重试 acquire，简略粗犷；

首先须要明确一点，spinlock 不能够在单核 CPU 上应用。单核 CPU 上同一时刻只有一个 thread 被执行，如果拿不到 lock，这样的 spin 空转没有任何意义，因为持有 lock 的 thread 不可能在此期间开释 lock。

然而如果在一个多核 CPU 上，spinlock 却有用武之地。如果 acquire lock 失败，持续重试一段时间，就可能等来持有 lock 的 thread 开释 lock，因为它此时很有可能正在另一个 core 上运行，而且它必然是在 critical section 之内：

这对于 critical section 很小，lock 竞争不是很强烈的应用场景就非常适合，因为在这种状况下，spin wait 的工夫大概率不会很长。而如果以后 thread 因为拿不到 lock 而放弃了 CPU，则可能会付出更大的代价，这一点前面会具体探讨。

然而如果是 critical section 比拟大或者 lock 竞争很强烈的状况，即便在多核 CPU 上，spin lock 也是不实用的，不停地期待和 spin 空转会大量节约 CPU 工夫，这是不明智的。

yield lock

下面说了，spinlock 对于单核 CPU 是没有任何意义的，不过咱们这个 kernel 恰好是在单核 CPU 模拟器上运行，所以须要实现一种相似 spinlock 的轻量级 lock，我权且称它为 yield lock。

顾名思义，yield lock 是指在 acquire 失败后，被动让出 CPU。也就是说我临时拿不到 lock，我去劳动一会儿，让其它 threads 先运行，等它们轮转完一圈，我再回来试试看。

它的行为实质上也是一种 spin，但不同于原地空转，它没有节约任何 CPU 工夫，而是立刻将 CPU 让给了他人，这样持有 lock 的 thread 就可能失去运行，待下一轮工夫片运行完后，它就很有可能曾经开释了 lock：

void yield_lock() {while (atomic_exchange(&lock_hold , LOCKED_YES) != LOCKED_NO) {schedule_thread_yield();
  }
}

留神这里必须将 schedule_thread_yield 放在 while 循环里，因为即便持有 lock 的 thread 开释了锁，也不代表以后 thread 等会儿肯定能拿到 lock，因为可能还有别的竞争者，所以在 yield 回来后，必须再次竞争 acquire lock；

和 spinlock 相似，yield lock 也适宜于 critical section 比拟小，竞争不是很强烈的情景，否则很多 threads 一次次地空等，也是对 CPU 资源的节约。

阻塞锁

下面两种锁，都是 非阻塞锁，也就是说 thread 在 acquire 失败的状况下不会 block，而是不停重试，或者过一段时间重试，实质上都是在重试。然而在 critical section 比拟大或者 lock 的竞争比拟强烈的状况下，一直重试很可能是徒劳的，这是对 CPU 资源的节约。

为了解决这个问题就有了 阻塞锁 （blocking lock），它的外部会保护一个队列，如果 thread 拿不到锁，会将本人退出到这个队列里睡眠，让出 CPU，在睡眠期间它不会再被调度运行，即进入了 阻塞 态；等到持有 lock 的 thread 开释 lock 时，会从队列里拿出一个 thread 从新唤醒。

例如，咱们定义以下的阻塞锁，命名为 mutex：

struct mutex {
  volatile uint32 hold;
  linked_list_t waiting_task_queue;
  yieldlock_t ydlock;
};

上锁的实现：

void mutex_lock(mutex_t* mp) {yieldlock_lock(&mp->ydlock);
  while (atomic_exchange(&mp->hold, LOCKED_YES) != LOCKED_NO) {
    // Add current thread to wait queue.
    thread_node_t* thread_node = get_crt_thread_node();
    yieldlock_lock(&mp->ydlock);
    linked_list_append(&mp->waiting_task_queue, thread_node);
    
    // Mark this task status TASK_WAITING so that
    // it will not be put into ready_tasks queue
    // by scheduler.
    schedule_mark_thread_block();
    
    yieldlock_unlock(&mp->ydlock);
    schedule_thread_yield();

    // Waken up, and try acquire lock again.
    yieldlock_lock(&mp->ydlock);
  }
  yieldlock_unlock(&mp->ydlock);
}

这里上锁（lock）的实现曾经比较复杂了，这其实是规范的 conditional wait 的实现办法。所谓 conditional wait，即 条件期待，就是以阻塞的形式，期待一个冀望的条件失去满足。这里所要期待的冀望条件就是：lock 被开释，我能够去尝试取得 lock。

在尝试获取 lock 失败后，以后 thread 将本人退出到 mutex 的 waiting_task_queue，并且标记本人为 TASK_WAITING 状态，而后让出了 CPU；这里的 让出 CPU 和下面的 yield lock 里一样，都调用了 schedule_thread_yield 函数，然而它们有着本质区别：

• yield lock 里的 thread 通过 yield，依然会被放入 ready_tasks 队列，前面依然会被 scheduler 调度；
• 而这里 thread 先把本人标记为了 TASK_WAITING，这样在 schedule_thread_yield 的实现里，该 thread 不会被增加到 ready_tasks 队列里，它因此实际上进入了 阻塞 状态，不会被再次调度，直到持有 lock 的 thread 下次 unlock 时，将它从 mutex 的 waiting_task_queue 里取出唤醒，从新放到 ready_tasks 队列；

void mutex_unlock(mutex_t* mp) {yieldlock_lock(&mp->ydlock);
  mp->hold = LOCKED_NO;

  if (mp->waiting_task_queue.size > 0) {
    // Wake up a waiting thread from queue.
    thread_node_t* head = mp->waiting_task_queue.head;
    linked_list_remove(&mp->waiting_task_queue, head);
    // Put waken up thread back to ready_tasks queue.
    add_thread_node_to_schedule(head);
  }
  yieldlock_unlock(&mp->ydlock);
}

下面的 lock 和 unlock 的代码里都有个要害元素，那就是定义在 mutex 外部的一个 yieldlock。这看上去仿佛比拟奇怪，因为 mutex 的实质性能就是锁，后果这个锁的外部数据竟然还须要另一把锁去爱护它本人，这岂不是套娃？

从实现上来说，mutex 曾经是一种比较复杂的锁了，它外部保护了 waiting 队列，而这个队列显然须要被爱护起来，所以就有了下面的套娃悖论。这里关键点在于，这两层锁的类型和存在目标是有本质区别的：

• mutex 是一把重型锁，它是提供给内部应用的，它的用处和爱护对象是是不确定的，一般来说是 critical section 比拟大，竞争比拟强烈的区域；
• 外部 yield lock 是轻量级的锁，这把锁的用处和爱护对象是是确定的，它爱护的是 mutex 外部的操作，这个 critical section 能够管制得十分小，所以这把锁的引入是必须而且正当的；

外部 yield lock 的代价在于，它引入了新的竞争，使整个 mutex 上的 threads 竞争更加强烈。然而这样的额定 cost 从 mutex 的设计和应用情景上来说是不可避免的，某种意义上来说也是能够接受和疏忽的：因为通常认为 mutex 爱护的内部 critical section 是比拟大的，相比于其外部 yield lock 爱护的区域而言。

kernel 和用户态的 lock

以上探讨的是几种锁的原理和实现形式，以及它们的应用场景的不同。一个很重要的辨别准则是，critical section 的大小和竞争的强烈水平，这实质上反映的是一个 thread 每次尝试失去这把锁的容易水平（或者机率），以此为根据，咱们能够分成两类应用情景：

• critical section 很小，且竞争不强烈，那么应用 spin 类型的 lock（包含 spinlock 和 yieldlock），它们是非阻塞的；
• critical section 很大，或者竞争强烈，那么应用阻塞锁；

不过以上探讨仅仅是 kernel 态下 lock，实际上在 kernel 态下应用哪种锁的抉择远不止那么简略，还波及到应用锁的中央，例如是中断上下文还是异样上下文，以及其它的很多思考，都会带来很多限度和不同。对于这些问题，当前有工夫我会尝试独自写一篇探讨，先挖个坑。

而如果到了用户态，lock 的应用和 kernel 态又会有很大的不同，一个被探讨的最多就是对于阻塞锁和 spinlock 的抉择。下面曾经说了，阻塞锁常被用于 critical section 很大，或者竞争强烈的情景，因为它不会导致 CPU 大量空转，看似是节约了 CPU 资源，然而用户态下的线程进入阻塞睡眠须要陷入 kernel 态，这对于 CPU 的性能影响是十分大的，可能还不如原地 spin 期待来的划算（前提是多核 CPU），所以这里的考量和 kernel 态下锁的应用又会有很大不同。

总结

本篇探讨了 lock 的原理和实现，限于本身程度，只是我集体浅显的了解，心愿能对读者有所帮忙，也欢送一起探讨评述。在这个 scroll 我的项目中，性能临时并不是咱们思考的问题，为了简略平安起见，我大量应用了 yieldlock 作为 kernel 下的次要用锁。