Operation-System-Chap.6

Operating System
Study Notes
发布日期:   2024-11-18
更新日期:   2024-11-22
文章字数:   3.3k

操作系统 Chap.6 同步机制

1. 竞争条件(Race Condition)

1.1 啥时候出现?

竞争条件(Race Condition) 指的是当多个线程 / 进程针对某个共享变量几乎同时进行操作时, 会出现的问题.

很显然, 某个进程在执行时, 可能会由于某种原因被暂停, 从而并未完成整个任务. 当涉及到某个共享变量时, 如果缺少对应的同步机制, 就会出现数据冲突 / 不一致的问题.

考虑一个具体的例子:

假设有个共享变量c, 现在又两个进程都对其进行++c的操作;
在系统中, 这一步指令分三步:

  • movl c, %eax // 把c的值放入eax寄存器
  • addl $1, %eax // eax寄存器增加1
  • movl %eax, c // 把eax寄存器的值再复制回c

我们假设, 进程1执行++c, 执行完第二步后被强行移除了运行队列(由于时间片到期等原因), 随后进程2重新执行++c; 最后进程1再回来把第三步做完.

发生了啥?
我们执行了两遍++c, 但c最终只自增了1.

显然这已经够麻烦了, 但更麻烦的是, 每次运行这两个进程的时候, 我们不知道其被中断运行时卡在了哪一步, 因此结果是 不确定 的(比如某一次运行时CPU频率比较高, 进程1被中断之前就把第三步干完了…)

类似上文这种问题, 被我们称为 race condition bug(竞争条件错误) .

1.2 临界区(Critical Section)

为了解决上文提出的问题, 人们提出了 临界区(Critical Section) 这一概念:
A Critical section is a program region that has to access shared data in a synchronized way (say, a mutual exclusion way); otherwise, race condition may occur
临界区是程序中的一个特定的区域, 程序需要以特定的同步方式来访问其中的共享数据.

这意味着, 如果要访问共享数据, 每个进程必须首先 申请进入临界区 , 当其获取到该许可后, 任何其它的进程均不允许访问该数据. 该进程结束对共享数据的处理后, 需要 告知退出临界区 , 随后继续完成其余的指令.

Critical Section

因此, 我们几乎已经能明确临界区的设计原则了:

  • 互斥原则(Mutual Exclusion): 即某个进程在其临界区内部运行时, 其余的进程均无法再进入临界区.
  • 有限等待(Bounded Waiting): 在某个进程请求进入其临界区后且该请求被批准之前，其他进程可以进入它们临界区的次数必须有一个上限.(事实上, 这是为了保证任何进程不会被无限期的隔离在临界区之外)
  • 空则让进(Progress): 如果没有任何进程正在其临界区中执行，并且存在一些进程希望进入它们的临界区，那么选择下一个进入临界区的进程的操作不能被无限期推迟。
  • 让权等待(Preemptive): 取决于内核设定, 若内核允许, 则进程可以在处于内核态时让出临界区的控制权, 反之则必须等到退出内核态后才能释放临界区.

1.3 互斥机制

一个好的互斥机制的实现应当满足:

  • 互斥
  • 无需对处理器速度或数目进行任何假设
  • 不会出现外部阻塞问题
  • 不会出现无限等待问题

2. 基于软件的互斥机制(Software-based Solutions)

2.1 First Solutions: Dekker’s algorithm

// flag[] is boolean array; and turn is an integer
flag[0] = false
flag[1] = true
turn = 0 // or 1

P0:
    flag[0] = true; // indicate intension
    while (flag[1] == true){
        if (turn <> 0){ // if it is not my turn
            flag[0] = false; // back off
            while(turn <> 0){
                // busy wait
            }   // finally, it is my turn
            flag[0] = true; // re-indicate intension
        }
    }
    // critical section
    ...
    turn = 1;
    flag[0] = false;
    // remainder section

P1:
    flag[1] = true; // indicate intension
    while (flag[0] == true){
        if (turn <> 1){ // if it is not my turn
            flag[1] = false; // back off
            while(turn <> 1){
                // busy wait
            }   // finally, it is my turn
            flag[1] = true; // re-indicate intension
        }
    }
    // critical section
    ...
    turn = 0;
    flag[1] = false;
    // remainder section
  • 通过flag数组来表示某一进程 是否有进入临界区的意愿
  • 通过turn保证 不会有任何一方陷入无限等待的状态

2.2 Peterson’s algorithm – simplify Dekker’s

后续基于Dekker的算法设计, Peterson对该算法进行了封装, 简化:

Peterson's algorithm

对于某个进程:

do { 
    enter_region(i); 
        critical section...
    leave_region(i); 
        remainder section...
} while (true);

事实上, 互斥机制还能够基于硬件进行实现.

但实话实说, 基于硬件进行实现比上述这种编程方式还要复杂一些, 笔者实在不是很想在这里展开长篇大论 , 如果读者感兴趣可前往互联网自行搜索.

3. 互斥锁(Mutex Locks)

我们确实能看出, 此前这种基于编程实现的方法比较复杂, 需要简化, 尤为重要的是, 它无法被应用程序的代码员很方便的利用起来.

因此, 不同操作系统的设计者都会搭建对应的系统工具用于解决这种线程间的 临界区同步 问题, 最典型的, 也是最简单的就是 互斥锁(Mutex Lock) .

3.1 实现逻辑

互斥锁的实现逻辑比较简单:

在进入临界区之前, 进程应当先 获取锁(acquire lock) , 随后进行需要执行的操作; 操作完毕后, 进程还应当 释放锁(release lock) , 使得其余线程能够访问临界区.

额外的, 如果当前进程在获取锁时, 锁正在被其他进程占有 , 则当前进程将进入 忙等状态 , 直到 锁被其他进程释放为止 .

通常, 互斥锁是通过一个 布尔变量(bollean) 进行控制的, 用布尔变量的真假标识当前临界区是否能够被访问.

acquire(){
    while(!available){
        /*busy wait*/
    }
    available = false;
}

release(){
    available = true;
}

//Process
do{
    acquire lock;
        critical section
    release lock;
        remainder section
}while(true)

看似这种互斥锁已经能够较好的完成该问题的解决, 但仍然存在不完美之处, 该方案是基于忙等的 .

但其实当前操作系统提供的一些更为高级的互斥锁(pthread_mutex_lock), 已经转而利用了操作系统的阻塞机制, 而不是忙等. (该点了解即可)

4. 信号量(Semaphore)

信号量有两种:

  • 二元信号量(Binary Semaphore): 作用类似于互斥锁, 其计数值只能是0 / 1
  • 计数信号量(Counting Semaphore): 相比于二元信号量, 其计数值可以 >1 , 通常用于限制对资源的并发访问.

4.1 如何解决此前的问题?(Critical Section Problem)

二元信号量提供了两种方法:

signal();

wait();

//考虑两个进程P1, P2; P1中的操作S1需要在P2中某个操作S2前完成
P1:
    S1;
    signal(synch);
P2:
    wait(synch);
    S2;

4.2 如何去除忙等机制?(without busy-waiting?)

当前的信号量机制不仅仅有这么一个数字, 每个信号量还伴随着一个 等待队列(waiting queue)

队列中的每个条目一般包含这样两个条目:

  • value(or Integer): 可能用于标识该条目在队列中的状态(如优先级等)
  • pointer to the next record: 即指向下一个条目的指针, 这使得这个等待队列能够形成一个链表

通常, 当某个进程发现该信号量当前不可用时, 会被放入等待队列中并进入 阻塞状态(Block) ;

当信号量再度可用时, 根据链表队列中的优先级, 删除某个队列项并将其对应的线程转为 就绪状态(Ready) ;

typedef struct{ 
    int value; 
    struct process *list; 
} semaphore; 

wait(semaphore *S) { // also called P operation				// Atomic operation
    S->value--; 
    if (S->value < 0) {
        add this process to S->list ; 
        block();
    } 
}
signal(semaphore *S) { // also called V operation			// Atomic operation
    S->value++; 
    if (S->value <= 0) {
        remove a process P from S->list;  
        wakeup(P);
    } 
}

4.3 死锁(Deadlock) / 优先级翻转(Priority Inversion)

信号量已经比较完善了, 我们解决了关键区域的问题, 并摆脱了忙等的限制.

但还有一种比较尴尬的情况, 我们称之为 死锁(Deadlock) , 这代表着有两个或更多线程在等待队列里无限期的等待下去, 并无法正常被调用. 这通常是由于不同的信号量使用不当导致的问题, 看如下的例子:

P0: //Process 0
wait(S);
wait(Q);
...
signal(S);
signal(Q);

P1: //Process 1
wait(Q);
wait(S);
...
signal(Q);
signal(S);

除开死锁, 还有 优先级翻转(Priority Inversion) 问题, 比如低优先级的进程占用了高优先级进程的资源, 导致高优先级进程无法及试运行.

对于这两种问题, 还请读者注意一下, 后续会有进一步讨论它们的文章.

4.4 Busy-waiting VS Context Switch

我们在此前的文章中(Operating System Chap.3)提到过, 进程的阻塞 / 恢复是需要代价的, 操作系统需要将 进程控制块(PCB) 中的内容恢复到内存中, 并继续运行剩余的代码. 这种代价我们一般称之为 上下文切换(Context Switch)

考虑如果忙等需要执行的代码量小于上下文切换的代码量, 这种时候忙等的效率其实要高于进程切换.
因此最新的操作系统一般会采用两种方式并用的策略来解决关键区域问题.

4.5 Linux中的互斥锁(pthread_mutex)

pthread_mutex func

5. 监视器(Monitor)

监视器(Monitor) 是一种高层的并发编程结构, 它提供了多种受控访问共享数据的方法.

5.1 组成

之所以介绍它, 是因为它实际上是对上述机制的一种系统封装:

  • 共享数据(Shared Data)
  • 操作共享数据的过程(Procedures that operate on the shared data)
  • 同步机制(Synchronization): 确保同一时刻只能有一个线程执行监视器中的方法.

5.2 运作

说到这, 其实其运作原理已经比较好猜了.

一个监视器里面有一个 互斥锁(Mutex lock) 以及一个 队列(Queue) .

一个进程必须先获得监视器中的互斥锁, 才能运行对监视器中共享数据区域的操作.
当这个互斥锁已经被其他进程占有, 则其它想要获得该互斥锁的进程被放入队列中.

Monitor

这玩意显然更加容易使用了, 它封装了大部分的方法, 并且基本上不会发生什么意料之外的情况

但显然, 这玩意也没有信号量那么灵活就是了.

Java中提供了内置的简单监视器实现: Synchronized

6. 条件变量(Condition Variable / CV)

为啥又冒出来个这呢?

考虑一种情况, 当某个线程得到了锁, 运行了一段时间了, 但它由于某些 别的条件不满足 , 导致它自身无法继续运行下去了.

这时候该咋办捏? 这个线程放弃锁, 并放弃它已经运行的所有步骤, 等到别的条件满足了之后重新来吗? 这显然不可接受.

条件变量应运而出了.

6.1 三种操作

CV其实本质上设计思路跟信号量有点像的. 它也有一个单独的等待队列.

它就三种操作:

  • wait(c, lock)
    • 把调用此方法的进程放入CV自己的等待队列(CV’s queue)中
    • 释放锁(方便其他进程)获取锁继续操作
  • signal(c)
    • 如果这个CV的等待队列中有进程, 从其中拿出一个, 放到监视器的等待队列中 (CV’s queue -> Monitor’s queue)
  • broadcase(c)
    • 将CV等待队列中的所有进程都放入监视器的等待队列中

请务必明确, 条件变量的等待队列跟监视器的等待队列是俩概念!

前者是为了等待某个条件满足, 让当前进程能够继续运行的.
后者是为了等待当前进程获得锁, 使自己能够运行的.

Condition Variable

6.2 实例

//一个简单的存钱 / 取钱例子
Strange_withdraw(x) {
    ...
    pthread_mutex_lock(&m);
    while(account < x) // “if” will not work
        pthread_cond_wait(&c, &m);
    account -= x;
    pthread_mutex_unlock(&m);
}

Deposit(y){
    pthread_mutex_lock(&m); //s1
    account += y;
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m); //s2
}

明确:

  • 在操作某个条件时, 请务必拿到锁.(s1, s2操作是必须的)
  • 请务必将条件变量放在一个循环里面
  • 别的线程调用了signal, 并不代表原先的条件一定满足了, 只不过是原先的条件发生了变化, 可以重新判断而已

至此, 各种同步机制就差不离了.

Synchronization methods

这篇博文就到这里~

文章作者: MUG-chen
文章链接: http://mug-chen.github.io/posts/50395.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 MUG-chen !
Operating System
  目录