有多少种方法可以实现多线程同步和互斥?什么是同步和互斥,操作系统如何实现同步和互斥,进程和线程之间的关系是什么,进程比线程的开销是多少?
文章目录
- 计算机基础知识
- 进程和线程
- 计算机的资源
- 内核
- 操作系统的内核
- 用户态和内核态
- 内核线程和用户线程
- 进程的开销比线程大在了哪里?
- 线程的同步和互斥
- 什么是同步,什么是互斥?
- 操作系统实现同步的方式
- 操作系统实现互斥的方法:
在讲同步和互斥之前,需要先熟悉一些计算机相关的基础概念
计算机基础知识
进程和线程
-
进程(Process),顾名思义就是正在执行的应用程序,是软件的执行副本。而线程是轻量级的进程。
-
进程是分配资源的基础单位。而线程是程序执行的基本单位。
每一种应用,比如游戏,执行后是一个进程。但是游戏内部需要图形渲染、需要网络、需要响应用户操作,这些行为不可以互相阻塞,必须同时进行,这样就设计成线程。现代的CPU以多线程为主,如下内容也主要是说多线程,我们讲的调度更多的也是线程的调度。
计算机的资源
我们经常讲操作系统需要分配资源,最重要的 3 种资源是:计算资源(CPU)
、内存资源
和文件资源
。计算机的CPU是有限的,而需要执行的任务往往有多个,CPU无法同时执行所有的任务,只能挨个执行,这就相当于是给任务(线程)分配了计算资源,得到了计算资源的任务就可以被执行。文件资源比如计算机中存储的文件是文件资源。
归根到底不管是计算机的组成还是操作系统,都面临着资源有限,而使用资源的任务(用户)却非常多,如何合理的安排资源,使得任务都能得到更好的执行,不管是线程和进程的设计也好,还是计算机的三级存储结构也好,都是在权衡利弊以及成本的基础上,为了更好的统筹规划资源而设计出来的。
内核
操作系统的内核
用户态和内核态
内核线程和用户线程
线程设计出来后,因为只被分配了计算资源(CPU),因此被称为轻量级进程。被分配的方式,就是由操作系统调度线程。操作系统创建一个进程后,进程的入口程序被分配到了一个主线程执行,这样看上去操作系统是在调度进程,其实是调度进程中的线程。
这种被操作系统直接调度的线程,我们也成为内核级线程。另外,有的程序语言或者应用,用户(程序员)自己还实现了线程。相当于操作系统调度主线程,主线程的程序用算法实现子线程,这种情况我们称为用户级线程。Linux 的 PThread API 就是用户级线程,KThread API 则是内核级线程。
进程的开销比线程大在了哪里?
以Linux为例:Linux 中创建一个进程自然会创建一个线程,也就是主线程。创建进程需要为进程划分出一块完整的内存空间,有大量的初始化操作,比如要把内存分段(堆栈、正文区等)。创建线程则简单得多,只需要确定 PC 指针和寄存器的值,并且给线程分配一个栈用于执行程序,同一个进程的多个线程间可以复用堆栈。因此,创建进程比创建线程慢,而且进程的内存开销更大。
线程的同步和互斥
什么是同步,什么是互斥?
同步:线程同步并不是说线程同时运行,而是让线程按照一定的顺序执行,使得最后的数据能达到同步。考虑这么一个场景,教室里很多学生,每个学生都在说话,七嘴八舌的,一片混论。如果这些同学挨个起来发言,或者是是以一个组为单位来发言 ,就会显得井然有序,大家也都能听到他们在说什么。同理,多线程的情况下,如果不加以控制,多个线程一起对数据进行添加或者是修改,数据会异常混论,就像是七嘴八舌的声音一样。我们写程序的目的,无非就是为了处理数据,处理数据的输入和输出,如果最后得到的输出不受你的控制,这个程序还有什么用?
互斥:有一些资源,比如:打印机。一次只能被一个线程访问,不允许多个线程同时访问,这种资源叫做临界资源。因此一个线程在访问这种资源的时候,其它线程不能访问,这就叫做互斥。【临界区:访问临界资源的那一段代码就叫做临界区。线程只有先进入临界区的才能访问到临界资源。】
一般来说:要实现同步,就得先实现互斥。比如上面同步中所举的那个场景,我们要让学生挨个起来发言,就得先保证一个同学发言的时候,其它同学不要发言,这就是一种互斥。
操作系统实现同步的方式
-
使用互斥量(Mutex):采用互斥对象机制,只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个,所以可以保证公共资源不会被多个线程同时访问。比如Java中的synchronized关键词和各种Lock都是这种机制。
-
使用信号量(Semphares) :它允许同一时刻多个线程访问同一资源,但是需要控制同一时刻访问此资源的最大线程数量
什么是信号量呢?可以看一下如下的例子
考虑有两个函数up和down。up
将lock
增 1,down
将lock
减 1。当 lock 为 0 时,如果还在down
这个函数里,那么会自旋。
其中的cas是指CPU中的原子操作其伪代码形式可以这样表示:cas(&oldValue, expectedValue, targetValue)
。比如我们要执行a++;假设a的初值为0,则可以这么写cas(&a, 0, 1),表示什么意思呢?先去存储a的地址空间中取出a的值,如果a的值是0,我就执行更新操作,使得a的值变为1,然后再写回去,否则不更新a的值。为什么执行一个a++都要这么麻烦呢?为的就是再多线程并发的情况下防止其它线程更改a的值
up(&lock){
while(!cas(&lock, lock, lock+1)) { }
}
down(&lock){
while(!cas(&lock, lock, lock - 1) || lock == 0){}
}
考虑到多线程的情况下执行下面这个程序
int lock = 2;
down(&lock);
// 临界区
up(&lock);
如果只有一个线程在临界区,那么lock
等于 1,第 2 个线程还可以进入。 如果两个线程在临界区,第 3 个线程尝试down
的时候,会陷入自旋锁。当然我们也可以用其他方式来替代自旋锁,比如让线程休眠。
当lock
初始值为 1 的时候,这个模型就是实现互斥(mutex)。如果 lock 大于 1,那么就是同时允许多个线程进入临界区。这种方法,我们称为信号量(semaphore)。
- 使用事件(Event) : 比如Wait/Notify:通过通知操作的方式来保持多线程同步。
操作系统实现互斥的方法:
- 软件实现互斥的方法
-
单标志法:设置一个公共的整形变量:turn。比如turn = 1则表示运行1这个进程进入临界区获得临界资源,其它线程则不允许进入。
-
双标志法先检查:每个线程在进入临界区访问临界资源之前,先查看临界资源是否正在被访问,若正在被访问,该线程需要进行等待;若临界资源没有被访问,该线程则进入临界区访问临界资源。我们可以设置一个标志数组flag[],flag[i] = true,则表示i这个线程在访问临界资源,flag[i] = false则表示该线程没有访问临界资源。当i线程检测到没有其它线程在访问临界资源时,则进入临界区,并将flag[i]设置为true。
可能出现的问题:
两个线程同时进入临界区
。因为线程是先查看有没有其它线程在访问临界资源,然后在没有其它线程访问临界资源时再进入临界区访问临界资源,这两个步骤间是有一定的时间间隔的。考虑两个线程T1和T2。T1先检查有没有线程没有访问临界资源,检查结果发现,没有其它线程访问临界资源,于是准备进入临界区访问临界资源,T1正准备进入却还没有进入的时候。【发生这样原因除了是因为执行的过程中存在时间间隔,还有个原因就是可能会发生线程切换】T2也开始检查有没有线程访问临界资源,检查结果发现没有线程访问临界资源,于是T2也开始准备进入临界区访问临界资源。这下好了,T1和T2都检测到没有其它线程在访问临界资源,于是,都进入了临界区,很显然违背了互斥。 -
双标志法后检查:
双标志法先检查
是先检测临界资源的状态,然后再设置自己的标志。双标志后检查则相反:若一个线程准备访问临界资源,先将自己的标志位设置为true,然后再检查其它的线程的标志位,若检测到其它某个线程的标志位为true,则该线程等待,否则进入临界区。可能出现的问题:
导致饥饿状态,没有一个线程能进入临界区
。考虑两个线程T1和T2。T1准备访问临界资源,于是将自己的标志位设置为true。在T1还未开始检测其它线程的状态时,T2刚好也准备访问临界资源,于是T2也赶紧将自己的标志位设置为true。这下好了,这两个线程检查是否有其它线程访问临界资源的时候,都能检查到对方的标志位为true,这两个线程就这样僵持着,互相都无法访问临界资源 -
Peterson(彼得森)算法:除了用一个flag[]数组来标志线程是否在访问临界资源或者是是否正准备访问临界资源,还设置了一个公共变量turn。
伪代码如下:
考虑两个线程i和j。
首先考虑3的那种情况。首先是i线程准备访问临界资源,于是将自己的标志位设置为true。然后呢,i线程假设此刻是j线程在访问临界区,于是将true设置为j。就在此时,j线程也准备访问临界资源,于是将自己的标志位设置为true,j线程也同样做了一个假设,假设此刻是i线程在访问临界区,于是把true的值设置为了i。最终,true的值变成了i。紧接着i线程开始在while循环中判断条件了,flag[j] == true成立,但是turn的值已经被j线程设置为了i,于是turn == j不成立,因此该循环条件不满足,i线程不执行该循环,i线程成功进入到临界区,避免了双标志法后检查
产生的饥饿问题。
- 硬件实现方法
-
中断屏蔽方法
当一个线程获得了CPU的计算资源时,除非发生中断,否则,是不会发生线程切换的。我们的计算机能同时运行多个程序,并不是说这些程序同时获得了CPU的计算资源,而是CPU在不停地切换线程或者是进程,比如先执行A线程,执行了一会以后,然后对A线程发起中断请求,A线程被中断了,然后交出了运行权,接着发生线程切换。然后CPU又赶紧去执行B线程。B线程执行了一会有切换到其它线程。CPU的运算速度非常快,很短的时间内就能执行大量的代码,而线程切换的速度又非常快,所以给我们造成了一种程序在并行执行的现象。
一个线程准备访问临界资源时,先屏蔽中断,屏蔽了中断就意味着这样该线程不会被中断,某种程度上就意味着该线程是独占CPU了,其它线程不会被得到执行,只有当该线程执行完毕,再开启中断以后,其它线程才可能得到执行。
-
硬件指令方法
在计算机中,有一些指令是原子级的指令,也就是说指令在执行的过程中,不会发生线程切换而导致执行过程被中断。比如TAS(Test and Set),CAS(Compare and Swap)。回想我们用软件实现互斥的方法的时候,比如双标志检查法,不管是先检查还是后检查。都存在着被打断的问题。比如T1线程先检测,发现没有其它线程使用临界资源,正当T1准备进入还没有进入的时候,T2线程却来捣乱了,偷偷将一些标志位给发生了改变。由于T1已经检测过了,所以它以为一切正常,继续执行,殊不知有些内容已经被修改了。如果我们把T1检测是否有其它线程使用中断,如果没有,将自己的值设置为true,否则,继续轮询这些操作封装成一个原子过程,也就是T1在执行这些代码的时候,一气呵成的执行完毕,不允许其它线程插进来捣乱,就不会发生同时进入临界区或者是发生饥饿的现象了。
参考
《王道操作系统考研复习指导》
下一篇: 竞争问题:深入理解和解决方案
推荐阅读
-
有多少种方法可以实现多线程同步和互斥?什么是同步和互斥,操作系统如何实现同步和互斥,进程和线程之间的关系是什么,进程比线程的开销是多少?
-
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)