现代操作系统 - 第 5 章 同步互斥机制 (I)
最编程
2024-04-03 09:07:13
...
- 同步与互斥产生的背景:由于进程的三个特征导致的可能的时序错误,会引起程序执行错误
- 并发:进程的执行是间断性的,多个进程在执行的过程中不断切换
- 共享:多个进程间存在共享资源,并且多个进程间断性地执行,可能导致一个进程对数据的操作过程被另一个使用该数据的进程损坏,因此需要对使用共享资源的进程制定制约机制
- 随机:进程的执行具有随机性,因此进程的执行结果是不确定的,无法确定性的知道各进程的执行顺序和执行结果,因此也就无法得知共享资源具体被做了哪些修改,当产生错误时也不知道到底经历了什么样的出错过程
- 竞争条件:两个或多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序,由此引起的两个进程间的资源竞争
- 进程互斥——竞争关系
- 概念:由于各进程要求使用共享资源(变量、文件等),而这些资源需要排他性使用,各进程之间竞争使用这些资源——这一关系称为进程互斥
- 临界资源:系统中有某些资源一次只允许一个进程使用,称这样的资源为临界资源或互斥资源或共享变量
- 临界区:各个进程中对某个临界资源进行操作的程序片段
- 临界区的使用原则:
- 没有进程在临界区时,想进入临界区的进程可以进入
- 不允许两个进程同时处于临界区中
- 临界区外运行的进程不得阻塞其他进程进入临界区
- 不得使进程无限期地等待进入临界区
- 实现进程互斥的方案:
- 软件方案:Dekker解法、Peterson解法
- 硬件方案:屏蔽中断(简单高效;代价高,限制CPU的并发能力;不适用于多处理器;适用于操作系统本身而不适用于用户进程)、TLS指令(Test and Set Lock)、XCHG指令(EXCHANGE)
- 忙等待:进程在得到临界区访问权之前,持续测试而不做其他事情。自旋锁做的就是忙等待,常用与多处理(多核)的条件下。
- 进程同步——协作关系
- 概念:指系统中多个进程中发生的事件存在时序关系,需要相互合作,共同完成一项任务。具体地说,一个进程运行到某一时间点时,要求另一伙伴进程为他提供消息,在未获得消息前,该进程进入阻塞态,获得消息后被环形进入就绪态。常见的进程间同步问题为:生产者消费者问题
- 信号量及PV操作——经典进程同步机制
- 信号量:是一个特殊的变量,是用于进程间传递消息的一个整数值,定义如下。对信号量可以实施的操作只有三种:初始化、P(test)、V(increase)
struct semphore
{
int count;
queueType queue;
} - P、V操作的定义:信号量S>=0时,S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源,因此S的值减1;当S<0时,表示已经没有可用资源,且S的绝对值表示正在等待资源的进程数,请求者必须等待别的进程释放该类资源,它才能运行下去。而执行一个V操作意味着释放一个单位资源,因此S的值加1;若S<0,表示有某些进程正在等待该资源,因此要唤醒一个等待状态的进程,使之运行下去。
procedure P(var s:samephore); { s.value=s.value-1; if (s.value<0) asleep(s.queue); } procedure V(var s:samephore); { s.value=s.value+1; if (s.value<=0) wakeup(s.queue); }
- 用信号量实现互斥:
- 设置信号量mutex初值为1
- 在临界区之前实施P(mutex)
- 在临界区之后实施V(mutex)
- 生产者-消费者问题:其中信号量empty和full用于生产者-消费者之间的同步,mutex是为了解决写与读不可同时进行而后引入的互斥信号量。从这段程序可以看出:使用PV操作实现进程同步时,同一信号量的P、V操作要成对出现,但它们分别在不同的进程(相互协作的进程)代码中;而使用PV操作实现进程互斥时,实现互斥的P、V操作必须成对出现,且在同一进程中,先做P操作,进临界区,后做V操作,出临界区。
void producer(void)
{
int item;
while( true )
{
item = produce_item();
P( &empty );
P( &mutex );
insert_item( item );
V( &mutex );
V( &full );
}
}void consumer(void)
{
int item;
while( true )
{
P( &full );
P( &mutex );
item = remove_item();
V( &mutex );
V( &empty );
consume_item( item );
}
} - 对于信号量及PV操作,可以参考:https://www.xuebuyuan.com/3230387.html
- 信号量:是一个特殊的变量,是用于进程间传递消息的一个整数值,定义如下。对信号量可以实施的操作只有三种:初始化、P(test)、V(increase)
-
Linux中的同步方法
-
内核中的同步方法——主要是自旋锁和信号量,并且关注二者的区别和使用场景
- 原子操作:包括对整数的原子操作和对位的原子操作,应用对象比较单一,不做过多介绍
-
自旋锁:
- 特性:自旋锁可以防止多个执行线程同时进入同一临界区,一个被争用的自旋锁使得请求它的线程在等待锁重新可用时自旋(忙等),因此自旋锁不应该被长时间持有。自旋锁的机制类似于如下场景:寝室卫生间的争用——当有人在厕所里时,想上厕所的人在门口等,直到里面的人出来。
- Linux内核中的自旋锁:自旋锁能够保证一个时刻只有一个线程在临界区内,为多处理机器提供了防止并发访问所需的保护机制。但是在单处理器机器上,编译时不会加入自旋锁,而是被当做内核抢占机制是否开启的开关,通过防止并发的产生而保护临界区,同时防止可能产生的死锁(在单处理器机器上,如果允许内核抢占机制,当持有锁的进程被另一个争用锁的进程抢占,进而可能还会被另外的进程抢占,如此一来即使不死锁也会导致严重的问题)
-
自旋锁的使用:
- 自旋锁可以使用在中断处理程序中,因为自旋锁不会导致睡眠(不像信号量)
- 在中断处理程序中使用自旋锁时,一定要在获取锁之前禁止本地中断,否则,其他的中断处理程序可能会打断当前正持有锁的内核代码,并且可能会试图争用该锁,从而导致其自旋,但是持有锁的内核代码(中断处理程序)必须等待抢占它的中断处理程序返回,才能释放锁,于是便产生了双重死锁。
- 注意,只需要禁止当前处理器的中断,而不用禁止其他处理器的中断。如果中断发生在不同的处理器上,并且中断处理程序试图争用锁,那么即使导致其自旋,也不会影响锁的持有者释放锁,因此这是真正的并行,而不像单处理器的并发那样。
- 另外,还要注意:如果有下半部和进程上下文共享数据,由于下半部会抢占进程上下文,则在进程上下文中加锁的同时还要禁止下半部;同理,如果有中断处理程序和下半部共享数据,由于中断处理程序会抢占下半部的执行,因此在下半部中加锁的同时还要禁止中断。
-
自旋锁方法:
- spin_lock() - spin_unlock() 获取/释放指定的自旋锁
- spin_lock_irqsave() - spin_unlock_irqrestore() 保存本地中断的当前状态,禁止本地中断,并获取指定的自旋锁/释放指定的锁,并让本地中断恢复到以前的状态
- spin_lock_irq() - spin_unlock_irq() 禁止/激活本地中断,并获取/释放指定的自旋锁。由于难以搞清楚当前的中断状态,因此不提倡使用
- spin_lock_init() 动态初始化自旋锁
- spin_lock_trylock() 试图获取指定的自旋锁,即使无法获取也不会自旋
- spin_is_locked() 判断指定的锁是否被占用
-
信号量:
- 特性:Linux中的信号量是一种睡眠锁,当一个进程试图获取一个不可用(已被占用)的信号量时,信号量会将其加入等待队列,然后让其睡眠。当信号量被释放时,处于等待队列的中的进程会被唤醒,并获得该信号量。信号量适用于锁会被较长时间占用的情况。使用信号量时,大多都是用的是互斥信号量(二值信号量)。
- 由于执行线程在试图获取信号量时会睡眠,所以只能在进程上下文中获取信号量,因为中断上下文中是不能进行调度的(也就是说无法满足进程的睡眠要求并调度新的任务)。
- 在持有自旋锁时,不能试图获取信号量,持有自旋锁时不允许睡眠。
-
信号量方法:
- sema_init() 以指定值初始化信号量
- init_MUTEX() 以数值1初始化信号量
- down() 相当于信号量P操作
- up() 相当于信号量V操作
-
自旋锁和信号量的选择:
- 自旋锁适用于占有锁的时间较短的情况,而信号量则适用于占有锁的时间较长的情况。二者相比,信号量提供了更好的CPU利用率,没有把时间花在忙等待上,但是信号量却有更大的任务切换开销。“生活总是一分为二的”。
- 另外,自旋锁可以用在中断处理程序中,而信号量不能用在中断处理程序中。
- Linxu中,自旋锁和信号量分别有读写自旋锁、读写信号量,二者都偏向读操作,是对二者的优化。
-
线程同步方法——pthread API
- 互斥量——用于互斥:功能基本和互斥信号量相同(推测其实现方式为互斥信号量)。读写锁是在互斥量的基础上进行优化后的锁。
- 条件变量——用于同步:条件变量给多线程提供了一个会合的场所。条件变量与互斥量一起使用时,允许线程以无竞争的方式等待特定条件的发生。条件本身由互斥量保护,线程在改变条件状态时必须首先锁住互斥量。pthread的条件变量是MESA模式的,具体用法见同步互斥机制(二)。
- 自旋锁:通常作为底层原语实现其他的锁。自旋锁在用户层并不是非常有用。
- 屏障:屏障是用户协调多线程并行工作的同步机制,它允许任意数量的线程等待,直到所有的线程完成处理工作,而线程不需要退出,所有线程到达屏障后可以接着工作。
-
内核中的同步方法——主要是自旋锁和信号量,并且关注二者的区别和使用场景
推荐阅读
-
现代操作系统 - 第 5 章 同步互斥机制 (I)
-
操作系统 第 2 章 进程描述与控制_进程同步与互斥的区别
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)