操作系统-并发技术


并发技术中:多任务、进程、线程、锁、协程、IO多路复用的基本概念。

【多任务】

    在上古时代,CPU 资源十分昂贵,如果让 CPU 只能运行一个程序,那么当 CPU 空闲下来(例如等待 I/O 时),CPU 就空闲下来了。为了让 CPU 得到更好的利用,人们编写了一个监控程序,如果发现某个程序暂时无须使用 CPU 时,监控程序就把另外的正在等待 CPU 资源的程序启动起来,以充分利用 CPU 资源。这种方法被称为 多道程序(Multiprogramming)。

    对于多道程序来说,最大的问题是程序之间不区分轻重缓急,对于交互式程序来说,对于 CPU 计算时间的需求并不多,但是对于响应速度却有比较高的要求。而对于计算类程序来说则正好相反,对于响应速度要求低,但是需要长时间的 CPU 计算。想象一下我们同时在用浏览器上网和听音乐,我们希望浏览器能够快速响应,同时也希望音乐不停掉。这时候多道程序就没法达到我们的要求了。于是人们改进了多道程序,使得每个程序运行一段时间之后,都主动让出 CPU 资源,这样每个程序在一段时间内都有机会运行一小段时间。这样像浏览器这样的交互式程序就能够快速地被处理,同时计算类程序也不会受到很大影响。这种程序协作方式被称为 分时系统(Time-Sharing System)。

    在分时系统的帮助下,我们可以边用浏览器边听歌了,但是如果某个程序出现了错误,导致了死循环,不仅仅是这个程序会出错,整个系统都会死机。为了避免这种情况,一个更为先进的操作系统模式被发明出来,也就是我们现在很熟悉的 多任务(Multi-tasking)系统。操作系统从最底层接管了所有硬件资源。所有的应用程序在操作系统之上以 进程(Process) 的方式运行,每个进程都有自己独立的地址空间,相互隔离。CPU 由操作系统统一进行分配。每个进程都有机会得到 CPU,同时在操作系统控制之下,如果一个进程运行超过了一定时间,就会被暂停掉,失去 CPU 资源。这样就避免了一个程序的错误导致整个系统死机。如果操作系统分配给各个进程的运行时间都很短,CPU 可以在多个进程间快速切换,就像很多进程都同时在运行的样子。几乎所有现代操作系统都是采用这样的方式支持多任务,例如 Unix,Linux,Windows 以及 macOS。


【进程】

    进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源,是一个动态的概念,是一个活动的实体。它不只是程序的代码,还包括当前的活动,通过程序计数器的值和处理寄存器的内容来表示。

    进程的概念主要有两点:第一,进程是一个实体。每一个进程都有它自己的地址空间,一般情况下,包括文本区域(text region)、数据区域(data region)和堆栈(stack region)。文本区域存储处理器执行的代码;数据区域存储变量和进程执行期间使用的动态分配的内存;堆栈区域存储着活动过程调用的指令和本地变量。第二,进程是一个“执行中的程序”。程序是一个没有生命的实体,只有处理器赋予程序生命时,它才能成为一个活动的实体,我们称其为进程。

进程的基本状态

    1、等待态:等待某个事件的完成;

    2、就绪态:等待系统分配处理器以便运行;

    3、运行态:占有处理器正在运行。

    运行态→等待态 往往是由于等待外设,等待主存等资源分配或等待人工干预而引起的。

    等待态→就绪态 则是等待的条件已满足,只需分配到处理器后就能运行。

    运行态→就绪态 不是由于自身原因,而是由外界原因使运行状态的进程让出处理器,这时候就变成就绪态。例如时间片用完,或有更高优先级的进程来抢占处理器等。

    就绪态→运行态 系统按某种策略选中就绪队列中的一个进程占用处理器,此时就变成了运行态

进程调度

    调度种类

        高级、中级和低级调度作业从提交开始直到完成,往往要经历下述三级调度:

        ·    高级调度:(High-Level Scheduling)又称为作业调度,它决定把后备作业调入内存运行;

        ·    中级调度:(Intermediate-Level Scheduling)又称为在虚拟存储器中引入,在内、外存对换区进行进程对换。

        ·    低级调度:(Low-Level Scheduling)又称为进程调度,它决定把就绪队列的某进程获得CPU;

    非抢占式调度与抢占式调度

        ·    非抢占式

                分派程序一旦把处理机分配给某进程后便让它一直运行下去,直到进程完成或发生进程调度进程调度某事件而阻塞时,才把处理机分配给另一个进程。

        ·    抢占式

                操作系统将正在运行的进程强行暂停,由调度程序将CPU分配给其他就绪进程的调度方式。

    调度策略的设计

        响应时间: 从用户输入到产生反应的时间

        周转时间: 从任务开始到任务结束的时间

        CPU任务可以分为交互式任务和批处理任务,调度最终的目标是合理的使用CPU,使得交互式任务的响应时间尽可能短,用户不至于感到延迟,同时使得批处理任务的周转时间尽可能短,减少用户等待的时间。

    调度算法

        1、FIFO或First Come, First Served (FCFS)

            调度的顺序就是任务到达就绪队列的顺序。

            公平、简单(FIFO队列)、非抢占、不适合交互式。未考虑任务特性,平均等待时间可以缩短

        2、Shortest Job First (SJF)

            最短的作业(CPU区间长度最小)最先调度。

            可以证明,SJF可以保证最小的平均等待时间。

            ·    Shortest Remaining Job First (SRJF)

                 SJF的可抢占版本,比SJF更有优势。

            SJF(SRJF): 如何知道下一CPU区间大小?根据历史进行预测: 指数平均法。

        1、优先权调度

            每个任务关联一个优先权,调度优先权最高的任务。

            注意:优先权太低的任务一直就绪,得不到运行,出现“饥饿”现象。

            FCFS是RR的特例,SJF是优先权调度的特例。这些调度算法都不适合于交互式系统。

        2、Round-Robin(RR)

            设置一个时间片,按时间片来轮转调度(“轮叫”算法)

            优点: 定时有响应,等待时间较短;缺点: 上下文切换次数较多;

            如何确定时间片?

            时间片太大,响应时间太长;吞吐量变小,周转时间变长;当时间片过长时,退化为FCFS。

        3、多级队列调度

            按照一定的规则建立多个进程队列

            不同的队列有固定的优先级(高优先级有抢占权)

            不同的队列可以给不同的时间片和采用不同的调度方法

        存在问题1:没法区分I/O bound和CPU bound;

        存在问题2:也存在一定程度的“饥饿”现象;

        4、多级反馈队列

            在多级队列的基础上,任务可以在队列之间移动,更细致的区分任务。

            可以根据“享用”CPU时间多少来移动队列,阻止“饥饿”。

            最通用的调度算法,多数OS都使用该方法或其变形,如UNIX、Windows等。

进程同步

    临界资源与临界区

        在操作系统中,进程是占有资源的最小单位(线程可以访问其所在进程内的所有资源,但线程本身并不占有资源或仅仅占有一点必须资源)。但对于某些资源来说,其在同一时间只能被一个进程所占用。这些一次只能被一个进程所占用的资源就是所谓的临界资源。典型的临界资源比如物理上的打印机,或是存在硬盘或内存中被多个进程所共享的一些变量和数据等(如果这类资源不被看成临界资源加以保护,那么很有可能造成丢数据的问题)。

        对于临界资源的访问,必须是互斥进行。也就是当临界资源被占用时,另一个申请临界资源的进程会被阻塞,直到其所申请的临界资源被释放。而进程内访问临界资源的代码被成为临界区。

        对于临界区的访问过程分为四个部分:

            1、进入区:查看临界区是否可访问,如果可以访问,则转到步骤二,否则进程会被阻塞

            2、临界区:在临界区做操作

            3、退出区:清除临界区被占用的标志

            4、剩余区:进程与临界区不相关部分的代码

        解决临界区问题可能的方法:

            1、一般软件方法

            2、关中断方法

            3、硬件原子指令方法

            4、信号量方法

    信号量

        信号量是一个确定的二元组(s,q),其中s是一个具有非负初值的整形变量,q是一个初始状态为空的队列,整形变量s表示系统中某类资源的数目:

            ·    当其值 ≥ 0 时,表示系统中当前可用资源的数目

            ·    当其值 < 0 时,其绝对值表示系统中因请求该类资源而被阻塞的进程数目

        除信号量的初值外,信号量的值仅能由P操作和V操作更改,操作系统利用它的状态对进程和资源进行管理

        P操作:

        P操作记为P(s),其中s为一信号量,它执行时主要完成以下动作:

s.value = s.value - 1;  /*可理解为占用1个资源,若原来就没有则记帐“欠”1个*/

        若s.value ≥ 0,则进程继续执行,否则(即s.value < 0),则进程被阻塞,并将该进程插入到信号量s的等待队列s.queue中

        说明:实际上,P操作可以理解为分配资源的计数器,或是使进程处于等待状态的控制指令

        V操作:

        V操作记为V(s),其中s为一信号量,它执行时,主要完成以下动作:

 s.value = s.value + 1;/*可理解为归还1个资源,若原来就没有则意义是用此资源还1个欠帐*/

        若s.value > 0,则进程继续执行,否则(即s.value ≤ 0),则从信号量s的等待队s.queue中移出第一个进程,使其变为就绪状态,然后返回原进程继续执行

        说明:实际上,V操作可以理解为归还资源的计数器,或是唤醒进程使其处于就绪状态的控制指令

        信号量方法实现:生产者 − 消费者互斥与同步控制

semaphore fullBuffers = 0; /*仓库中已填满的货架个数*/
semaphore emptyBuffers = BUFFER_SIZE;/*仓库货架空闲个数*/
semaphore mutex = 1; /*生产-消费互斥信号*/

Producer() 
{ 
    while(True)
    {  
       /*生产产品item*/
       emptyBuffers.P(); 
       mutex.P(); 
       /*item存入仓库buffer*/
       mutex.V();
       fullBuffers.V();
    }
}

Consumer() 
{
    while(True)
    {
        fullBuffers.P(); 
        mutex.P();    
        /*从仓库buffer中取产品item*/
        mutex.V();
        emptyBuffers.V();
        /*消费产品item*/
    }
}

    死锁

        死锁: 多个进程因循环等待资源而造成无法执行的现象。

        死锁会造成进程无法执行,同时会造成系统资源的极大浪费(资源无法释放)。

        死锁产生的4个必要条件:

        ·    互斥使用(Mutual exclusion)

            指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。

        ·    不可抢占(No preemption)

            指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。

        ·    请求和保持(Hold and wait)

            指进程已经保持至少一个资源,但又提出了新的资源请求,而该资源已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。

        ·    循环等待(Circular wait) 指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

        死锁避免——银行家算法

        思想: 判断此次请求是否造成死锁若会造成死锁,则拒绝该请求

进程间通信

    本地进程间通信的方式有很多,可以总结为下面四类:

    ·    消息传递(管道、FIFO、消息队列)

    ·    同步(互斥量、条件变量、读写锁、文件和写记录锁、信号量)

    ·    共享内存(匿名的和具名的)

    ·    远程过程调用(Solaris门和Sun RPC)


【线程】

    多进程解决了前面提到的多任务问题。然而很多时候不同的程序需要共享同样的资源(文件,信号量等),如果全都使用进程的话会导致切换的成本很高,造成 CPU 资源的浪费。于是就出现了线程的概念。

    线程,有时被称为轻量级进程(Lightweight Process,LWP),是程序执行流的最小单元。一个标准的线程由线程ID,当前指令指针(PC),寄存器集合和堆栈组成。

    线程具有以下属性:

        1、轻型实体 线程中的实体基本上不拥有系统资源,只是有一点必不可少的、能保证独立运行的资源。线程的实体包括程序、数据和TCB。线程是动态概念,它的动态特性由线程控制块TCB(Thread Control Block)描述。

        2、独立调度和分派的基本单位。

            在多线程OS中,线程是能独立运行的基本单位,因而也是独立调度和分派的基本单位。由于线程很“轻”,故线程的切换非常迅速且开销小(在同一进程中的)。

        3、可并发执行。 在一个进程中的多个线程之间,可以并发执行,甚至允许在一个进程中所有线程都能并发执行;同样,不同进程中的线程也能并发执行,充分利用和发挥了处理机与外围设备并行工作的能力。

        4、共享进程资源。 在同一进程中的各个线程,都可以共享该进程所拥有的资源,这首先表现在:所有线程都具有相同的地址空间(进程的地址空间),这意味着,线程可以访问该地址空间的每一个虚地址;此外,还可以访问进程所拥有的已打开文件、定时器、信号量等。由于同一个进程内的线程共享内存和文件,所以线程之间互相通信不必调用内核。 线程共享的环境包括:进程代码段、进程的公有数据(利用这些共享的数据,线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。


【锁】

    这里讨论的主要是多线程编程中需要使用的锁,网上有关于锁的文章实在是非常多而且乱套,让新手不知道从何下手。这里我们不去钻名词和概念的牛角尖,而是直接从本质上试图解释一下锁这个很常用的多线程编程工具。

    锁要解决的是线程之间争取资源的问题,这个问题大概有下面几个角度:

        ·    资源是否是独占(独占锁 - 共享锁)

        ·    抢占不到资源怎么办(互斥锁 - 自旋锁)

        ·    自己能不能重复抢(重入锁 - 不可重入锁)

        ·    竞争读的情况比较多,读可不可以不加锁(读写锁)

    上面这几个角度不是互相独立的,在实际场景中往往要它们结合起来,才能构造出一个合适的锁。

独占锁 - 共享锁

    当一个共享资源只有一份的时候,通常我们使用独占锁,常见的即各个语言当中的 Mutex。当共享资源有多份时,可以使用前面提到的 Semaphere。

互斥锁 - 自旋锁

    对于互斥锁来说,如果一个线程已经锁定了一个互斥锁,第二个线程又试图去获得这个互斥锁,则第二个线程将被挂起(即休眠,不占用 CPU 资源)。

    在计算机系统中,频繁的挂起和切换线程,也是有成本的。自旋锁就是解决这个问题的。

    自旋锁,指当一个线程在获取锁的时候,如果锁已经被其它线程获取,那么该线程将循环等待,然后不断的判断锁是否能够被成功获取,直到获取到锁才会退出循环。

    容易看出,当资源等待的时间较长,用互斥锁让线程休眠,会消耗更少的资源。当资源等待的时间较短时,使用自旋锁将减少线程的切换,获得更高的性能。

    较新版本的 Java 中的 synchornized 和 .NET 中的 lock(Monitor) 的实现,是结合了两种锁的特点。简单说,它们在发现资源被抢占之后,会先试着自旋等待一段时间,如果等待时间太长,则会进入挂起状态。通过这样的实现,可以较大程度上挖掘出锁的性能。

重入锁 - 不可重入锁

    可重入锁(ReetrantLock),也叫做递归锁,指的是在同一线程内,外层函数获得锁之后,内层递归函数仍然可以获取到该锁。换一种说法:同一个线程再次进入同步代码时,可以使用自己已获取到的锁。

    使用可重入锁时,在同一线程中多次获取锁,不会导致死锁。使用不可重入锁,则会导致死锁发生。

    Java 中的 synchornized 和 .NET 中的 lock(Monitor) 都是可重入的。

读写锁

    有些情况下,对于共享资源读竞争的情况远远多于写竞争,这种情况下,对读操作每次都进行加速,是得不偿失的。读写锁就是为了解决这个问题。

    读写锁允许同一时刻被多个读线程访问,但是在写线程访问时,所有的读线程和其他的写线程都会被阻塞。简单可以总结为,读读不互斥,读写互斥,写写互斥。

    对读写锁来说,有一个升级和降级的概念,即当前获得了读锁,想把当前的锁变成写锁,称为升级,反之称为降级。锁的升降级本身也是为了提升性能,通过改变当前锁的性质,避免重复获取锁。


【协程】

    协程,又称微线程,纤程。英文名 Coroutine。

    协程可以理解为用户级线程,协程和线程的区别是:线程是抢占式的调度,而协程是协同式的调度,协程避免了无意义的调度,由此可以提高性能,但也因此,程序员必须自己承担调度的责任,同时,协程也失去了标准线程使用多CPU的能力。


【IO多路复用】

基本概念

    IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取,它就通知该进程。IO多路复用适用如下场合:

        1、当客户处理多个描述字时(一般是交互式输入和网络套接口),必须使用I/O复用。

        2、当一个客户同时处理多个套接口时,而这种情况是可能的,但很少出现。

        3、如果一个TCP服务器既要处理监听套接口,又要处理已连接套接口,一般也要用到I/O复用。

        4、如果一个服务器即要处理TCP,又要处理UDP,一般要使用I/O复用。

        5、如果一个服务器要处理多个服务或多个协议,一般要使用I/O复用。

    与多进程和多线程技术相比,I/O多路复用技术的最大优势是系统开销小,系统不必创建进程/线程,也不必维护这些进程/线程,从而大大减小了系统的开销。

常见的IO复用实现

        ·    select(Linux/Windows/BSD)

        ·    epoll(Linux)

        ·    kqueue(BSD/Mac OS X)

上一篇 下一篇

评论

登录后可发表评论