操作系统并发

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

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇