Linux教程

操作系统概念 第6章 进程同步

本文主要是介绍操作系统概念 第6章 进程同步,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

概述

多进程并发访问操作同一数据,且执行结果与访问顺序有关,这种现象称为竞争条件。为避免竞争条件,需要进行进程同步。

临界区问题中,没有两个进程可以同时在临界区内执行,代码可以分为进入区、临界区、退出区、剩余区。三个基本的要求是:互斥访问,空闲让进,有限等待。假设每个进程的执行速度非零,但相对速度没有任何假设。

非抢占内核中,处于内核态的进程会一直运行到退出内核态、阻塞或者主动放弃 CPU,这种模式下不会有竞争条件,但抢占内核更适合实时程序,响应更快。

解决临界区问题

临界区问题可以用较为繁复的软件方法解决,而一些简单的尝试可能不能同时满足三个要求。证伪一个要求的方式是构造恰当的执行顺序,很多时候一人一步或一人一直走等极端情况会很有效。

软件方法

单标志法中,我们维护 turn 表示接下来该由谁来访问,进入区只需要 turn=j; while(turn!=i);,即先谦让,等被让回自己时再走。这样不满足空闲让进。

双标志先检查法中,我们维护 flag[] 表示某个进程是否有访问的意愿。所谓先检查,就是先检查是否有他人有意愿,再提出自己意愿。这样不满足互斥访问。同理,双标志后检查法不满足空闲让进。

Peterson 算法是双标志后检查和单标志法的融合,“我有想法但下次归你,如果你有想法并且下次归你我就等。”三个要求同时得到满足。

Bakery 算法维护 choosing[] 表示某个进程是否在选号,选到的号存进 number[] 中,前项为摇号机摇到的号(为当前 number[] 中最大值 +1),后项为自身进程号。进程先标记 choosing[i] 然后计算一个 number,取消 choosing[i] 后扫描一遍,如果有人在选就等他选好,如果有人的编号比我小就等着。扫描完后即可进入邻接区,退出时别忘了清楚编号。注意 choosing[] 是必须的,不妨设想进程 1 已经计算出号 (1,1) 还未保存,切到进程 2 计算出号 (1,2),但以为自己最小而进入临界区,此时切回进程 1 又进入临界区,未被互斥访问。

硬件方法

下面我们考虑如何构建一个互斥锁。用单标志 flag 显然是不行的,我们考虑一些硬件支持。

关中断是有效的,但它权限太高,不适用于多处理器,可能会丢失中断,也不够高效。

借助 Test-and-Set 指令,我们用 while(TAS(flag,1)==1); 就可以实现加锁,解锁只需 flag=0;,这样不满足有限等待,但一个标记数组和循环扫描也许会有所帮助,即解锁时按顺序考虑唤醒一个等待者。

借助 Compare-and-Swap 指令,我们用 while(CAS(flag,0,1)==1); 就可以实现加锁,类似地,它同样不满足有限等待。

条件变量

条件变量是一种显式队列,线程可以通过条件变量来等待一个条件变为真。执行条件不满足时,线程可以把自己加入队列。另一个线程改变了状态时可以通过发信号来唤醒等待线程。

wait(condition, mutex) 调用时 mutex 必须已是上锁状态,wait 会释放 mutex 并使调用线程休眠。线程被唤醒时必须重新获取 mutex 再返回调用者。signal(condition) 用于唤醒某个条件变量上的睡眠线程。

用条件变量可以实现线程的 joinexit,设条件变量 c 配套有互斥锁 m 和标记 done,则 join() 实现为 lock(m); while(!done) wait(c,m); unlock(m);exit() 实现为 lock(m); done=1; signal(c); unlock(m);。如果去掉互斥锁 m 或者标记 done 都可能会导致先 signalwait,因此通常条件变量会和互斥锁与标记配套使用。

信号量

信号量是一个整数变量,通过 wait()signal() 原语来操作。最简单的信号量是个自旋锁,为了克服忙等待我们稍加修改。若 wait() 时发现信号量值不为正则必须阻塞自己,而 signal() 后若信号量值不为正则从对应的等待队列头部唤醒一个阻塞的进程。具体地,wait() 相当于 value--; if(value<0) push(this), block(this);signal() 相当于 value++; if(value<=0) wakeup(pop());。另外,对 SMP 系统,还需要其它加锁机制来保证 waitsignal 的原子性。

多个进程无限等待只能由它们自己产生的事件,则它们称为死锁。进程在信号量内无限期等待称为饥饿。

经典同步问题

生产者-消费者问题

定义三个信号量,empty 表示空缓冲区数,full 表示满缓冲区数,mutex 用于保护缓冲区。

对于生产者,只需要 wait(empty); wait(mutex);,然后干活并释放即可。

注意 wait 的顺序不能颠倒,否则会出现死锁。

读者-写者问题

第一类读者-写者问题要求读者优先。实现时需要 readcnt 表示当前读者数量,readcnt_m 保护 readcntrw_m 表示当前是否有人在读或者有人在写。实现如下:

Write()
{
    wait(rw_m);
    write();
    signal(rw_m);
}
Read()
{
    wait(readcnt_m);
    readcnt++;
    if(readcnt==1) wait(rw_m);
    signal(readcnt_m);
    
    read();
    
    wait(readcnt_m);
    readcnt--;
    if(readcnt==0) signal(rw_m);
    signal(readcnt_m);
}

第二类读者-写者问题要求写者优先,即一旦有写者要写,下次就不得让读者进入。实现时需要 readcount 表示当前读者数量,writecount 表示当前写者数量,read_m 表示当前是否可读,write_m 表示当前是否可写。此外还需要保护数据一致性的 readcount_mwritecount_m

哲学家进餐问题

在哲学家进餐问题中,可以通过限制进餐者总数,或者让部分人反手,来解决死锁。

这篇关于操作系统概念 第6章 进程同步的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!