操作系统并发

Terms

  • Critical section: piece of code that accesses a shared resource.
  • Race condition: 多个线程同时进去 critical section。
  • Indeterminate:指程序在多线程情况下,程序结果不唯一。
  • Mutual exclusion:排他。

Locks

Evaluating Locks

  • Mutual exclusion
  • Fairness 当大量线程同时访问时,是否存在某些 thread starve 的可能。
  • Performance

Controlling Interrupts

就是 lock 的时候直接关闭系统中断,但是这样很危险,而且不靠谱。因为一旦关闭中断,操作系统也无法获得操作权利。

而且不支持多核处理器。

image-20210511122124949

所以这种方法只有在某些地方用用了。

Simple Spin Lock

image-20210511132750354

这种 lock 方式由两个问题:

correctness:不正确

image-20210511132953632

performance:spin wait 的方式会消耗大量的 CPU 时间片。

Spin Lock with Test-And-Set

硬件层面提供了如下原子操作:

image-20210511133309929
image-20210511134948170

Spin Lock With Compare-And-Swap

image-20210511135433031
image-20210511141310262

和 Test-And-Set 差不多,Java 里面的 CAS 就是 Compare-And-Swap。

Fetch-And-Add

有些硬件提供这种 premitive。

image-20210511141603678

可以基于这个,开发一个 ticket lock。ticket lock 的好处就是维持了 fairness,保证每个 thread 一定能够被执行到,不会被 starve。

image-20210511141656163

解决 spin lock 性能低下

解决办法很简单,就是要开始自旋的时候,放弃 CPU,进入 sleep 状态。然后把 thread id 放一个队列里面。当别的 thread 执行完成后,唤醒队列中的一个 thread。

image-20210511145454675

除此之外,spin lock 还有一个缺点:priority inversion 。假设两个 thread,分别为 T1 和 T2。T2 的 priority 大于 T1。然后一开始,T2先运行,因为它优先级高。然后因为某种 IO 操作,blocked。此时操作系统让 T1 开始运行,然后 T1 hold 一个 T2 将来要用的 lock。然后 T2 IO 操作完毕,开始执行,操作系统将 T1 sleep 了,然而此时 T1 的 lock 并没有释放,结果使得 T2 卡在那里,等着 T1 的 lock,然而 T1 已经 sleep,永远不会释放 lock。

Two-Phase Locks

spin lock 也不是一无是处,因为如果你知道某些锁很快就会被释放,推荐就使用 spin lock,这样性能更高,

Two-phase lock 就是一开始先自旋一会,然后如果还是得不到 lock,就会采用 second plan,睡觉。

Condition Variables

wait() thread 希望 sleep。signal() 通知唤醒。

image-20210512214802381

说明几点:

  • 为什么要用变量 done:当假设没有 done 变量时,child 线程直接开始执行(在 thr_join() 之前),并且执行了 thr_exit() ,当他尝试 signal 线程时,因为没有线程 sleep,所以直接跳过。而此时 thr_join() 开始执行,然后睡着了,然而永远不会有线程去 signal 它了。
  • 为什么要用 mutex 锁:假设没有了 mutex,此时先执行了 thr_join(),到 20 行,还没有开始 wait。此时 OS 调度子线程,直接执行完成了 thr_exit()。然后切换回 parent thread 执行后面的 wait,与上面一样,永远不会被唤醒了。

下面是基于 Java 的生产者消费者模型。

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Study {

    private static Lock lock = new ReentrantLock();
    static Condition empty = lock.newCondition();
    static Condition fill = lock.newCondition();

    private static int count = 0;
    private static int buf = 0;

    public static void main(String[] args) {
        Thread p = new Thread(new Producer());
        p.start();
        for (int i=0; i<10; i++) {
            new Thread(new Consumer()).start();
        }

        try {
            Thread.sleep(5000);
        } catch (InterruptedException e) {}
    }

    private static class Consumer implements Runnable {
        @Override
        public void run() {
            for (int i=0; i<10; i++) {
                lock.lock();
                while (count == 0) {
                    try {
                        empty.await();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.println(Thread.currentThread().getName() + ":" + buf);
                count = 0;
                fill.signal();
                lock.unlock();
            }
        }
    }

    private static class Producer implements Runnable {
        @Override
        public void run() {
            for (int i=0; i<100; i++) {
                lock.lock();
                while (count == 1) {
                    try {
                        fill.await();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                buf = i;
                System.out.println("produce: " + buf);
                count = 1;
                empty.signal();
                lock.unlock();
            }
        }
    }
}

在上面的代码中我们要注意,一定要使用 while 循环来判断 count==0count ==1 这两个条件。比如 consumer 中,如果使用 if,count==0 进入后,睡眠了,然后被唤醒,就直接执行后面的语句了,而没有循环再次检查一遍 count 的值(因为有可能在你唤醒的过程中,这个 count 的值被其他线程消费了)。

在条件变量这块,用 while 肯定不会出错,用 if 反而有可能出错。

Semaphore

image-20210513120734444

信号量使用 condition variable 和 mutex 实现

image-20210513121524798

Event-based Concurrency

select, poll

原创文章,作者:Smith,如若转载,请注明出处:https://www.inlighting.org/archives/os-concurrency

打赏 微信扫一扫 微信扫一扫
SmithSmith
上一篇 2021年4月25日
下一篇 2020年11月29日

相关推荐

  • CPU Scheduling Policies 调度算法

    本文只写给自己,所以比较粗糙。 调度衡量指标 Turnaround time Turnaround time = 任务完成时间-任务到达时间$$T_{turnaround} = T…

    2021年4月25日
    1.8K0
  • Fast File System

    Fast File System(FFS)一个具有里程碑意义的文件系统。它没有修改上层调用的 API,例如( open(), read(), write() 等等),而修改了内部实…

    2020年11月29日
    1.8K0
  • Log-Structured File System

    Introduction Log-Structured File System (LFS)发明的背景就是建立在 CPU 高速发展,磁盘读取写入速度极速发展,单位内存越来越便宜,而磁…

    2020年12月2日
    1.4K0

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注