精华内容
下载资源
问答
  • 浅析Linux内核同步机制(转)
    千次阅读
    2018-07-30 23:50:19

    原文地址:https://blog.csdn.net/fzubbsc/article/details/37736683?utm_source=tuicool&utm_medium=referral

     很早之前就接触过同步这个概念了,但是一直都很模糊,没有深入地学习了解过,近期有时间了,就花时间研习了一下《linux内核标准教程》和《深入linux设备驱动程序内核机制》这两本书的相关章节。趁刚看完,就把相关的内容总结一下。为了弄清楚什么事同步机制,必须要弄明白以下三个问题:

     

    • 什么是互斥与同步?
    • 为什么需要同步机制?
    •  Linux内核提供哪些方法用于实现互斥与同步的机制?

     

    1、什么是互斥与同步?(通俗理解)

     

    • 互斥与同步机制是计算机系统中,用于控制进程对某些特定资源的访问的机制。
    • 同步是指用于实现控制多个进程按照一定的规则或顺序访问某些系统资源的机制。
    • 互斥是指用于实现控制某些系统资源在任意时刻只能允许一个进程访问的机制。互斥是同步机制中的一种特殊情况。
    • 同步机制是linux操作系统可以高效稳定运行的重要机制。

     

    2、Linux为什么需要同步机制?

            在操作系统引入了进程概念,进程成为调度实体后,系统就具备了并发执行多个进程的能力,但也导致了系统中各个进程之间的资源竞争和共享。另外,由于中断、异常机制的引入,以及内核态抢占都导致了这些内核执行路径(进程)以交错的方式运行。对于这些交错路径执行的内核路径,如不采取必要的同步措施,将会对一些关键数据结构进行交错访问和修改,从而导致这些数据结构状态的不一致,进而导致系统崩溃。因此,为了确保系统高效稳定有序地运行,linux必须要采用同步机制。

    3、Linux内核提供了哪些同步机制?

            在学习linux内核同步机制之前,先要了解以下预备知识:(临界资源与并发源)
            在linux系统中,我们把对共享的资源进行访问的代码片段称为临界区。把导致出现多个进程对同一共享资源进行访问的原因称为并发源。

            Linux系统下并发的主要来源有:

     

    • 中断处理:例如,当进程在访问某个临界资源的时候发生了中断,随后进入中断处理程序,如果在中断处理程序中,也访问了该临界资源。虽然不是严格意义上的并发,但是也会造成了对该资源的竞态。
    • 内核态抢占:例如,当进程在访问某个临界资源的时候发生内核态抢占,随后进入了高优先级的进程,如果该进程也访问了同一临界资源,那么就会造成进程与进程之间的并发。
    • 多处理器的并发:多处理器系统上的进程与进程之间是严格意义上的并发,每个处理器都可以独自调度运行一个进程,在同一时刻有多个进程在同时运行 。

     

    如前所述可知:采用同步机制的目的就是避免多个进程并发并发访问同一临界资源。 

    Linux内核同步机制:

    (1)禁用中断 (单处理器不可抢占系统)

            由前面可以知道,对于单处理器不可抢占系统来说,系统并发源主要是中断处理。因此在进行临界资源访问时,进行禁用/使能中断即可以达到消除异步并发源的目的。Linux系统中提供了两个宏local_irq_enable与 local_irq_disable来使能和禁用中断。在linux系统中,使用这两个宏来开关中断的方式进行保护时,要确保处于两者之间的代码执行时间不能太长,否则将影响到系统的性能。(不能及时响应外部中断)

    (2)自旋锁

    应用背景:自旋锁的最初设计目的是在多处理器系统中提供对共享数据的保护。

    自旋锁的设计思想:在多处理器之间设置一个全局变量V,表示锁。并定义当V=1时为锁定状态,V=0时为解锁状态。自旋锁同步机制是针对多处理器设计的,属于忙等机制。自旋锁机制只允许唯一的一个执行路径持有自旋锁。如果处理器A上的代码要进入临界区,就先读取V的值。如果V!=0说明是锁定状态,表明有其他处理器的代码正在对共享数据进行访问,那么此时处理器A进入忙等状态(自旋);如果V=0,表明当前没有其他处理器上的代码进入临界区,此时处理器A可以访问该临界资源。然后把V设置为1,再进入临界区,访问完毕后离开临界区时将V设置为0。

    注意:必须要确保处理器A“读取V,半段V的值与更新V”这一操作是一个原子操作。所谓的原子操作是指,一旦开始执行,就不可中断直至执行结束。

    自旋锁的分类:

    2.1、普通自旋锁

    普通自旋锁由数据结构spinlock_t来表示,该数据结构在文件src/include/linux/spinlock_types.h中定义。定义如下:

    typedef struct { raw_spinklock_t   raw_lock;
    
           #ifdefined(CONFIG_PREEMPT)  &&  defined(CONFIG_SMP)
    
                   unsigned int break_lock;
    
           #endif
    
    } spinlock_t;

    成员raw_lock:该成员变量是自旋锁数据类型的核心,它展开后实质上是一个Volatileunsigned类型的变量。具体的锁定过程与它密切相关,该变量依赖于内核选项CONFIG_SMP。(是否支持多对称处理器)

    成员break_lock:同时依赖于内核选项CONFIG_SMP和CONFIG_PREEMPT(是否支持内核态抢占),该成员变量用于指示当前自旋锁是否被多个内核执行路径同时竞争、访问。

    在单处理器系统下:CONFIG_SMP没有选中时,变量类型raw_spinlock_t退化为一个空结构体。相应的接口函数也发生了退化。相应的加锁函数spin_lock()和解锁函数spin_unlock()退化为只完成禁止内核态抢占、使能内核态抢占。

    在多处理器系统下:选中CONFIG_SMP时,核心变量raw_lock的数据类型raw_lock_t在文件中src/include/asm-i386/spinlock_types.h中定义如下:

    typedef struct {  volatileunsigned int slock;} raw_spinklock_t;

           从定义中可以看出该数据结构定义了一个内核变量,用于计数工作。当结构中成员变量slock的数值为1时,表示自旋锁处于非锁定状态,可以使用。否则,表示处于锁定状态,不可以使用。

    普通自旋锁的接口函数:

    spin_lock_init(lock)        //声明自旋锁是,初始化为锁定状态
    
    spin_lock(lock)             //锁定自旋锁,成功则返回,否则循环等待自旋锁变为空闲
    
    spin_unlock(lock)           //释放自旋锁,重新设置为未锁定状态
    
    spin_is_locked(lock)        //判断当前锁是否处于锁定状态。若是,返回1.
    
    spin_trylock(lock)          //尝试锁定自旋锁lock,不成功则返回0,否则返回1
    
    spin_unlock_wait(lock)      //循环等待,直到自旋锁lock变为可用状态。
    
    spin_can_lock(lock)         //判断该自旋锁是否处于空闲状态。 

    普通自旋锁总结:自旋锁设计用于多处理器系统。当系统是单处理器系统时,自旋锁的加锁、解锁过程分为别退化为禁止内核态抢占、使能内核态抢占。在多处理器系统中,当锁定一个自旋锁时,需要首先禁止内核态抢占,然后尝试锁定自旋锁,在锁定失败时执行一个死循环等待自旋锁被释放;当解锁一个自旋锁时,首先释放当前自旋锁,然后使能内核态抢占。

     

    2.2、自旋锁的变种

            在前面讨论spin_lock很好的解决了多处理器之间的并发问题。但是如果考虑如下一个应用场景:处理器上的当前进程A要对某一全局性链表g_list进行操作,所以在操作前调用了spin_lock获取锁,然后再进入临界区。如果在临界区代码当中,进程A所在的处理器上发生了一个外部硬件中断,那么这个时候系统必须暂停当前进程A的执行转入到中断处理程序当中。假如中断处理程序当中也要操作g_list,由于它是共享资源,在操作前必须要获取到锁才能进行访问。因此当中断处理程序试图调用spin_lock获取锁时,由于该锁已经被进程A持有,中断处理程序将会进入忙等状态(自旋)。从而就会出现大问题了:中断程序由于无法获得锁,处于忙等(自旋)状态无法返回;由于中断处理程序无法返回,进程A也处于没有执行完的状态,不会释放锁。因此这样导致了系统的死锁。即spin_lock对存在中断源的情况是存在缺陷的,因此引入了它的变种。

    spin_lock_irq(lock) 
    
    spin_unlock_irq(lock)

    相比于前面的普通自旋锁,它在上锁前增加了禁用中断的功能,在解锁后,使能了中断。

    2.3、读写自旋锁rwlock

    应用背景:前面说的普通自旋锁spin_lock类的函数在进入临界区时,对临界区中的操作行为不细分。只要是访问共享资源,就执行加锁操作。但是有时候,比如某些临界区的代码只是去读这些共享的数据,并不会改写,如果采用spin_lock()函数,就意味着,任意时刻只能有一个进程可以读取这些共享数据。如果系统中有大量对这些共享资源的读操作,很明显spin_lock将会降低系统的性能。因此提出了读写自旋锁rwlock的概念。对照普通自旋锁,读写自旋锁允许多个读者进程同时进入临界区,交错访问同一个临界资源,提高了系统的并发能力,提升了系统的吞吐量。

    读写自旋锁有数据结构rwlock_t来表示。定义在…/spinlock_types.h中

    读写自旋锁的接口函数:

    DEFINE_RWLOCK(lock)     //声明读写自旋锁lock,并初始化为未锁定状态
    
    write_lock(lock)        //以写方式锁定,若成功则返回,否则循环等待
    
    write_unlock(lock)      //解除写方式的锁定,重设为未锁定状态
    
    read_lock(lock)         //以读方式锁定,若成功则返回,否则循环等待
    
    read_unlock(lock)       //解除读方式的锁定,重设为未锁定状态

    读写自旋锁的工作原理:

             对于读写自旋锁rwlock,它允许任意数量的读取者同时进入临界区,但写入者必须进行互斥访问。一个进程要进行读,必须要先检查是否有进程正在写入,如果有,则自旋(忙等),否则获得锁。一个进程要进程写,必须要先检查是否有进程正在读取或者写入,如果有,则自旋(忙等)否则获得锁。即读写自旋锁的应用规则如下:

    (1)如果当前有进程正在写,那么其他进程就不能读也不能写。

    (2)如果当前有进程正在读,那么其他程序可以读,但是不能写。

    2.4、顺序自旋锁seqlock

    应用背景:顺序自旋锁主要用于解决自旋锁同步机制中,在拥有大量读者进程时,写进程由于长时间无法持有锁而被饿死的情况,其主要思想是:为写进程提高更高的优先级,在写锁定请求出现时,立即满足写锁定的请求,无论此时是否有读进程正在访问临界资源。但是新的写锁定请求不会,也不能抢占已有写进程的写锁定。

    顺序锁的设计思想:对某一共享数据读取时不加锁,写的时候加锁。为了保证读取的过程中不会因为写入者的出现导致该共享数据的更新,需要在读取者和写入者之间引入一个整形变量,称为顺序值sequence。读取者在开始读取前读取该sequence,在读取后再重新读取该值,如果与之前读取到的值不一致,则说明本次读取操作过程中发生了数据更新,读取操作无效。因此要求写入者在开始写入的时候更新。

    顺序自旋锁由数据结构seqlock_t表示,定义在src/include/linux/seqlcok.h

    顺序自旋锁访问接口函数:

    seqlock_init(seqlock)               //初始化为未锁定状态
    
    read_seqbgin()、read_seqretry()     //保证数据的一致性
    
    write_seqlock(lock)                 //尝试以写锁定方式锁定顺序锁
    
    write_sequnlock(lock)               //解除对顺序锁的写方式锁定,重设为未锁定状态。

    顺序自旋锁的工作原理:写进程不会被读进程阻塞,也就是,写进程对被顺序自旋锁保护的临界资源进行访问时,立即锁定并完成更新工作,而不必等待读进程完成读访问。但是写进程与写进程之间仍是互斥的,如果有写进程在进行写操作,其他写进程必须循环等待,直到前一个写进程释放了自旋锁。顺序自旋锁要求被保护的共享资源不包含有指针,因为写进程可能使得指针失效,如果读进程正要访问该指针,将会出错。同时,如果读者在读操作期间,写进程已经发生了写操作,那么读者必须重新读取数据,以便确保得到的数据是完整的。

     

    (3)信号量机制(semaphore)

    应用背景:前面介绍的自旋锁同步机制是一种“忙等”机制,在临界资源被锁定的时间很短的情况下很有效。但是在临界资源被持有时间很长或者不确定的情况下,忙等机制则会浪费很多宝贵的处理器时间。针对这种情况,linux内核中提供了信号量机制,此类型的同步机制在进程无法获取到临界资源的情况下,立即释放处理器的使用权,并睡眠在所访问的临界资源上对应的等待队列上;在临界资源被释放时,再唤醒阻塞在该临界资源上的进程。另外,信号量机制不会禁用内核态抢占,所以持有信号量的进程一样可以被抢占,这意味着信号量机制不会给系统的响应能力,实时能力带来负面的影响。

    信号量设计思想:除了初始化之外,信号量只能通过两个原子操作P()和V()访问,也称为down()和up()。down()原子操作通过对信号量的计数器减1,来请求获得一个信号量。如果操作后结果是0或者大于0,获得信号量锁,任务就可以进入临界区。如果操作后结果是负数,任务会放入等待队列,处理器执行其他任务;对临界资源访问完毕后,可以调用原子操作up()来释放信号量,该操作会增加信号量的计数器。如果该信号量上的等待队列不为空,则唤醒阻塞在该信号量上的进程。

    信号量的分类:

    3.1、普通信号量

    普通信号量由数据结构struct semaphore来表示,定义在src/inlcude/ asm-i386/semaphore.h中.

    信号量(semaphore)定义如下:

    <include/linux/semaphore.h>
    
    struct semaphore{
    
           spinlock_t       lock; //自旋锁,用于实现对count的原子操作
    
           unsigned int    count; //表示通过该信号量允许进入临界区的执行路径的个数
    
           struct list_head      wait_list; //用于管理睡眠在该信号量上的进程
    
    };

    普通信号量的接口函数:

    sema_init(sem,val)      //初始化信号量计数器的值为val
    
    int_MUTEX(sem)          //初始化信号量为一个互斥信号量
    
    down(sem)               //锁定信号量,若不成功,则睡眠在等待队列上
    
    up(sem)                 //释放信号量,并唤醒等待队列上的进程

    DOWN操作:linux内核中,对信号量的DOWN操作有如下几种:

    void down(struct semaphore *sem); //不可中断
    
    int down_interruptible(struct semaphore *sem);//可中断
    
    int down_killable(struct semaphore *sem);//睡眠的进程可以因为受到致命信号而被唤醒,中断获取信号量的操作。
    
    int down_trylock(struct semaphore *sem);//试图获取信号量,若无法获得则直接返回1而不睡眠。返回0则 表示获取到了信号量
    
    int down_timeout(struct semaphore *sem,long jiffies);//表示睡眠时间是有限制的,如果在jiffies指明的时间到期时仍然无法获得信号量,则将返回错误码。

    在以上四种函数中,驱动程序使用的最频繁的就是down_interruptible函数

    UP操作:LINUX内核只提供了一个up函数

    void up(struct semaphore *sem)

    加锁处理过程:加锁过程由函数down()完成,该函数负责测试信号量的状态,在信号量可用的情况下,获取该信号量的使用权,否则将当前进程插入到当前信号量对应的等待队列中。函数调用关系如下:down()->__down_failed()->__down.函数说明如下:

    down()功能介绍:该函数用于对信号量sem进行加锁,在加锁成功即获得信号的使用权是,直接退出,否则,调用函数__down_failed()睡眠到信号量sem的等待队列上。__down()功能介绍:该函数在加锁失败时被调用,负责将进程插入到信号量 sem的等待队列中,然后调用调度器,释放处理器的使用权。

    解锁处理过程:普通信号量的解锁过程由函数up()完成,该函数负责将信号计数器count的值增加1,表示信号量被释放,在有进程阻塞在该信号量的情况下,唤醒等待队列中的睡眠进程。 

    3.2读写信号量(rwsem)

    应用背景:为了提高内核并发执行能力,内核提供了读入者信号量和写入者信号量。它们的概念和实现机制类似于读写自旋锁。

    工作原理:该信号量机制使得所有的读进程可以同时访问信号量保护的临界资源。当进程尝试锁定读写信号量不成功时,则这些进程被插入到一个先进先出的队列中;当一个进程访问完临界资源,释放对应的读写信号量是,该进程负责将该队列中的进程按一定的规则唤醒。

    唤醒规则:唤醒排在该先进先出队列中队首的进程,在被唤醒进程为写进程的情况下,不再唤醒其他进程;在唤醒进程为读进程的情况下,唤醒其他的读进程,直到遇到一个写进程(该写进程不被唤醒)

    读写信号量的定义如下:

    <include/linux/rwsem-spinlock.h>
    
    sturct rw_semaphore{
    
           __s32      activity; //用于表示读者或写者的数量
    
           spinlock_t      wait_lock;
    
           struct list_head      wait_list;
    
    };

    读写信号量相应的接口函数

    读者up、down操作函数:

    void up_read(Sturct rw_semaphore *sem);
    
    void __sched down_read(Sturct rw_semaphore *sem);
    
    Int down_read_trylock(Sturct rw_semaphore *sem);

    写入者up、down操作函数:

    void up_write(Sturct rw_semaphore *sem);
    
    void __sched down_write(Sturct rw_semaphore *sem);
    
    int down_write_trylock(Sturct rw_semaphore *sem);

    3.3、互斥信号量

    在linux系统中,信号量的一个常见的用途是实现互斥机制,这种情况下,信号量的count值为1,也就是任意时刻只允许一个进程进入临界区。为此,linux内核源码提供了一个宏DECLARE_MUTEX,专门用于这种用途的信号量定义和初始化

    <include/linux/semaphore.h>
    
    #define DECLARE_MUTEX(name)  \
    
                  structsemaphore name=__SEMAPHORE_INITIALIZER(name,1)

    (4)互斥锁mutex

    Linux内核针对count=1的信号量重新定义了一个新的数据结构struct mutex,一般都称为互斥锁。内核根据使用场景的不同,把用于信号量的down和up操作在struct mutex上做了优化与扩展,专门用于这种新的数据类型。

    (5)RCU

    RCU概念:RCU全称是Read-Copy-Update(读/写-复制-更新),是linux内核中提供的一种免锁的同步机制。RCU与前面讨论过的读写自旋锁rwlock,读写信号量rwsem,顺序锁一样,它也适用于读取者、写入者共存的系统。但是不同的是,RCU中的读取和写入操作无须考虑两者之间的互斥问题。但是写入者之间的互斥还是要考虑的。

    RCU原理:简单地说,是将读取者和写入者要访问的共享数据放在一个指针p中,读取者通过p来访问其中的数据,而读取者则通过修改p来更新数据。要实现免锁,读写双方必须要遵守一定的规则。

    读取者的操作(RCU临界区)

    对于读取者来说,如果要访问共享数据。首先要调用rcu_read_lock和rcu_read_unlock函数构建读者侧的临界区(read-side critical section),然后再临界区中获得指向共享数据区的指针,实际的读取操作就是对该指针的引用。

    读取者要遵守的规则是:(1)对指针的引用必须要在临界区中完成,离开临界区之后不应该出现任何形式的对该指针的引用。(2)在临界区内的代码不应该导致任何形式的进程切换(一般要关掉内核抢占,中断可以不关)。

    写入者的操作

    对于写入者来说,要写入数据,首先要重新分配一个新的内存空间做作为共享数据区。然后将老数据区内的数据复制到新数据区,并根据需要修改新数据区,最后用新数据区指针替换掉老数据区的指针。写入者在替换掉共享区的指针后,老指针指向的共享数据区所在的空间还不能马上释放(原因后面再说明)。写入者需要和内核共同协作,在确定所有对老指针的引用都结束后才可以释放老指针指向的内存空间。为此,写入者要做的操作是调用call_rcu函数向内核注册一个回调函数,内核在确定所有对老指针的引用都结束时会调用该回调函数,回调函数的功能主要是释放老指针指向的内存空间。Call_rcu函数的原型如下:

    Void call_rcu(struct rcu_head *head,void (*func)(struct rcu_head *rcu));

    内核确定没有读取者对老指针的引用是基于以下条件的:系统中所有处理器上都至少发生了一次进程切换。因为所有可能对共享数据区指针的不一致引用一定是发生在读取者的RCU临界区,而且临界区一定不能发生进程切换。所以如果在CPU上发生了一次进程切换切换,那么所有对老指针的引用都会结束,之后读取者再进入RCU临界区看到的都将是新指针。

    老指针不能马上释放的原因:这是因为系统中爱可能存在对老指针的引用,者主要发生在以下两种情况:(1)一是在单处理器范围看,假设读取者在进入RCU临界区后,刚获得共享区的指针之后发生了一个中断,如果写入者恰好是中断处理函数中的行为,那么当中断返回后,被中断进程RCU临界区中继续执行时,将会继续引用老指针。(2)另一个可能是在多处理器系统,当处理器A上的一个读取者进入RCU临界区并获得共享数据区中的指针后,在其还没来得及引用该指针时,处理器B上的一个写入者更新了指向共享数据区的指针,这样处理器A上的读取者也饿将引用到老指针。

    RCU特点:由前面的讨论可以知道,RCU实质上是对读取者与写入者自旋锁rwlock的一种优化。RCU的可以让多个读取者和写入者同时工作。但是RCU的写入者操作开销就比较大。在驱动程序中一般比较少用。

    为了在代码中使用RCU,所有RCU相关的操作都应该使用内核提供的RCU API函数,以确保RCU机制的正确使用,这些API主要集中在指针和链表的操作。

    下面是一个RCU的典型用法范例:

    假设struct shared_data是一个在读取者和写入者之间共享的受保护数据
     
    Struct shared_data{
     
    Int a;
     
    Int b;
     
    Struct rcu_head rcu;
     
    };
     
     
     
    //读取者侧的代码
     
    Static void demo_reader(struct shared_data *ptr)
     
    {
     
           Struct shared_data *p=NULL;
     
           Rcu_read_lock();
     
           P=rcu_dereference(ptr);
     
           If(p)
     
                  Do_something_withp(p);
     
           Rcu_read_unlock();
     
    }
     
     
     
    //写入者侧的代码
     
     
     
    Static void demo_del_oldptr(struct rcu_head *rh) //回调函数
     
    {
     
           Struct shared_data *p=container_of(rh,struct shared_data,rcu);
     
           Kfree(p);
     
    }
     
    Static void demo_writer(struct shared_data *ptr)
     
    {
     
           Struct shared_data *new_ptr=kmalloc(…);
     
           …
     
           New_ptr->a=10;
     
           New_ptr->b=20;
     
           Rcu_assign_pointer(ptr,new_ptr);//用新指针更新老指针
     
           Call_rcu(ptr->rcu,demo_del_oldptr); 向内核注册回调函数,用于删除老指针指向的内存空间
     
    }
    
    
    (6)完成接口completion
    

    Linux内核还提供了一个被称为“完成接口completion”的同步机制,该机制被用来在多个执行路径间作同步使用,也即协调多个执行路径的执行顺序。在此就不展开了。

     

    更多相关内容
  • Linux内核的同步机制

    2020-11-10 07:29:16
    一、引言 在现代操作系统里,同一时间可能有多个内核执行流在执行,因此内核其实象多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上,更需要一些同步机制来同步...
  • 同步机制及应用编程实现与比较.zip
  • 相对于单机游戏,网络游戏涉及到更多的技术问题,比如网络底层通讯模型,游戏逻辑的同步策略、服务器群集技术等,其中游戏同步机制在网络游戏中有着至关重要的作用。 网络中的延迟是不可避免的,延迟的存在引发了...
  • 腾讯游戏早期的网络同步机制解决方案,移动端保证网游不同客户端的强同步机制。文章主要介绍基础原理及实现方案,部分异常情况的处理,仅供参考。
  • 主要介绍了详解C语言进程同步机制的的相关资料,文中代码非常详细,帮助大家更好的理解和学习,感兴趣的朋友可以了解下
  • 提出混合式数据同步机制,有机融合集中式和ad hoc架构,设置自组织域(SOD,self-organization domain),减少了同步数据通信量和数据同步服务器负载;提出基于节点能力值的数据分发策略,根据移动终端综合处理能力值来...
  • 主要给大家介绍了关于MySQL主从同步机制与同步延时问题追查的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
  • 在多线程编程中我们会遇到很多需要使用线程同步机制去解决的并发问题,这些同步机制是如何实现的呢?下面和小编来一起学习吧
  • 主要介绍了java 中ThreadLocal本地线程和同步机制的比较的相关资料,需要的朋友可以参考下
  • Linux操作系统内核同步机制分析.PDF
  • 同步机制

    千次阅读 2018-12-25 11:50:08
    同步机制 同步机制的原则 1、空闲让进: 当无进程处于临界区时,表明临界资源处于空闲状态,应允许一个请求进入临界区的进程立即进入自己的临界区,以有效利用临界资源 2、忙则等待 当已有进程进入临界区时...

    同步机制

    • 同步机制的原则
      1、空闲让进:
      当无进程处于临界区时,表明临界资源处于空闲状态,应允许一个请求进入临界区的进程立即进入自己的临界区,以有效利用临界资源
      2、忙则等待
      当已有进程进入临界区时,表明临界资源正在被占用,因而其他试图进入临界区的进程必须等待,以保证对临界资源的互斥使用
      3、有限等待
      对要求访问临界资源的进程,应保证在有限时间内能进入到自己的临界区,以免陷入死等的状态
      4、让权等待
      当进程不能进入自己的临界区时,应立即释放处理机,以避免进程陷入忙等状态

    • 硬件同步机制
      1、关中断:在进入锁测试之前关闭中断,直到完成锁测试并上锁之后才能打开中断。这样在临界区执行时就不会响应中断,引发调度。
      2、Test-and-Set指令实现互斥(原语)
      利用硬件指令TS

    该指令的一般性描述

    boolean TS(boolean *lock){
    boolean old;
    old=*lock;
    *lock=TRUE;//true表示资源正在被占用,false表示空闲
    return old;
    }
    //该指令是原语,不可被分割
    

    进程在进入临界区之前,首先用TS指令测试lock,如果为FALSE则表示可进入,并将TRUE值赋值给lock;

    3、利用Swap指令实现进程互斥
    该指令称为对换指令,描述如下:

    void swap(boolean *a,boolean *b)
    {
    	boolean temp;
    	temp=*a;
    	*a=*b;
    	*b=temp
    }
    

    利用Swap指令实现进程互斥但是循环进程可描述如下

    do{
    	key=TRUE;
    	do{
    		swap(&lock,&key);
    	}while(key!=FALSE);
    	临界区操作;
    	lock=FALSE;
    	......
    }while(TRUE);
    
    

    利用上述硬件指令能有效的实现进程的互斥,但当临界资源忙碌时,其他访问进程必须不断地进行测试,处于一种忙等状态,不符合让权等待的原则,同时很难将它们用于解决复杂难度的进程同步问题

    • 信号量机制(P、V操作)
      信号量(Semaphores)机制(Dijkstra提出)是一种卓有成效的进程同步工具。信号量机制已被广泛应用于单处理机和多处理机系统以及计算机网络中。
      • 整型信号量
        把整型信号量定义为一个用于表示资源数目的整型量S。
        它与一般整型量不同,除初始化外,仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。一般被称为P、V操作。
    void wait(S)
    {     
          while(S<=0);         //当S<=0时,会不断测试。未处理好
           S--;  
    } 
    
    
    void signal(S)
    {     
           S++;  
    } 
    
    

    缺陷:若信号量S<=0,就会不断地进行测试。因此,该机制并未遵循让权等待的原则。会使进程处于忙等的状态。

    • 记录型信号量
      在记录型型号量中,采用了一种新的数据结构,信号S就是这种新的数据结构类型
    struct semaphore{
    	int value;                   //表示资源数目的整型变量
    	struct semaphore *list;        //进程链表指针
    }
    

    相应的,wait(S)和signal(S)操作可描述如下:

    wait(semaphore *S)
    {
    	S->value--;
    	if(S->value<0)
    		block(S->list);
    }
    
    signal(semaphore *S)
    {
    	S->value++;
    	if(S->value<=0)
    		wakeup(S->list);
    }
    

    在记录型信号量机制中,S->value的初值表示系统中某类资源的数目,因而称为资源信号量,对他的每次wait操作,意味着进程请求一个单位的该类资源,使系统中可供分配的该类资源减少一个。因此描述为S->value–;当S->value<0时,表示该类资源分配完毕,因此进程调用一个block原语进行自我阻塞,放弃处理机并插入到信号量链表S->list中。
    对信号量的每次signal操作,都释放一个单位资源,故S->value++表示资源数目加1;若加1后S->value<=0,表示该信号量链表中仍有等待该资源的进程被阻塞,故调用wakeup原语,将S->list 链表中第一个等待进程唤醒。

    S.value的绝对值(S.value为负值)表示在该信号量链表中已阻塞进程的数目。
    如果S.value的初值为1,表示只允许一个进程访问,此时信号量转化为互斥信号量。

    信号量的应用:用信号量实现前趋图。
    在这里插入图片描述

    //设s1s2之间信号量为a,s1s3之间为b,s2s4之间为c,s2s5之间为d,s4s6之间为e
    //s5s6之间是f,s3s6之间是g;
    //函数p1~p6分别表示为s1~s6的运行函数
    
     p1(){s1;signal(a);signal(b);}
     p2(){wait(a);s2;signal(c);signal(d);}
     p3(){wait(b);s3;signal(g);}
     p4(){wait(c);s4;signal(e);}
     p5(){wait(d);s5;signal(f);}
     p6(){wait(g);wait(e);wait(f);s6;}
    
     main(){
    	semaphore a,b,c,d,e,f,g;
    	a.value=b.value=c.value=0;
    	d.value=e.value=f.value=0;
    	g.value=0;
    	/*将信号量值初始化为0,当s2抢在s1之前运行时,就会被阻塞,进入到阻塞队列。
    	**只有等到s1执行之后,wait()函数将a.value释放出来,使得a.value=1,
    	**此时p2才能成功运行。
    	*/
    	cobegin
    	p1();p2();p3();p4();p5();p6();
    	coend
    	
    }
    
    • 经典同步问题
      • 生产者-消费者问题

    (1)一个生产者,一个消费者,一个buffer
    在本题中,生产者在生产时要先判断buffer是否为空,当已有一个产品存在的时候,必须要消费者先拿走一个才能继续生产,否则生产者阻塞,故需要一个信号量empty,来帮助生产者判断buffer的情况;同理,消费者也需要生产者先生产一个产品,才能进行取用,故需要一个信号量full来判断buffer中是否有产品。

    semaphore empty,full;
    
    empty.value=1;	//初始化为1,表示当前buffer大小为1
    full.value=0;		//初始化为0,防止消费者在生产者未生产之前运行
    
    cobegin
    	process Producer(){
    		produce an item in nextp;
    		wait(empty);
    		buffer=nextp;		//此时buffer满
    		signal(full); 		//表示消费者可以取了
    	}
    process Consumer(){
    	wait(full);
    	nextc=buffer;			//此步骤将buffer清空
    	signal(empty);		    //生产者可以生产
    	consumer the item in nextc;
    }
    
    

    (2)一个生产者,一个消费者,n个buffer
    当为n个buffer时,为了控制存取的位置,需要设置存指针in和取指针out,由于只有一个生产者和消费者,所以in和out不是共享的临界资源。

    semaphore empty,full;
    int in=0;out=0;			//存和取都是从第1个buffer区开始
    empty.value=n;
    full.value=0;
    cobegin
    	process Producer(){
    		...
    		prodece an item in nextp;
    		wait(empty);		//测试只要buffer不满N个,就可以继续存
    		buffer[in]=nextp;
    		in=(in+1)%n;		//n为buffer的大小
    		signal(full);
    	}
    	process Consumer(){
    		wait(full);
    		nextc=buffer[out];
    		out=(out+1)%n;
    		signal(empty);
    		consumer the item in nextc;
    	}
    coend
    

    (3)K个生产者,M个消费者,N个buffer
    在这里插入图片描述
    empty和full只能保证buffer被生产者和消费者有序使用,但是多个消费者之间或者多个生产者之间也会产生冲突,必须设置新的信号量来控制生产者或消费者对buffer的访问,即保证每次只有一个生产者或则消费者进入。

    用互斥信号量mutex 实现对缓冲区(共享变量in和out)的互斥使用,互斥信号量mutex初值为1;

    semaphore empty,full,mutex;
    int in=0,out=0;
    empty.value=n;
    full.value=0;
    item buffer[n];
    mutex.value=1;		//同时只能有一个消费者或生产者使用in或out指针
    
    
    	void Producer(){
    		item nextp;
    		while(true){
    			...
    			prodece an item in nextp;
    			...
    			wait(empty);
    			wait(mutex);			//对于多个wait的顺序不能颠倒,否则会造成死锁
    			buffer[in]=nextp;
    			in=(in+1)%n;
    			signal(mutex);
    			signal(full);
    			}
    	}
    	void Consumer(){
    		item nextc;
    		while(true){
    			wait(full);
    			wait(mutex);
    			nextc=buffer[out];
    			out=(out+1)%n;
    			signal(mutex);
    			signal(empty);
    			consumer the item in nextc;
    			...
    		}
    	}
    
      	void main(){
    		cobegin
    			Producer();
    			Consumer();
    		coend
    	}
    

    在每个进程中的多个wait操作顺序不能颠倒,应先执行对资源信号量(也称私有信号量)的wait操作,然后执行对互斥信号量(公有信号量)的wait操作,否则可能引起进程死锁。(Why?)

    设想生产者进程已经将缓冲区放满,消费者进程并没有取产品,即empty = 0。
    当下次仍然是生产者进程运行时,它先执行Wait(mutex)封锁信号量(此时mutex=0),再执行Wait(empty)时将被阻塞,希望消费者取出产品后将其唤醒。
    轮到消费者进程运行时,它先执行Wait(mutex),然而由于生产者进程已经封锁mutex信号量,消费者进程也会被阻塞,这样一来生产者、消费者进程都将阻塞,都指望对方唤醒自己,陷入了无休止的等待。

    展开全文
  • java的线程同步机制synchronized关键字的理解_.docx
  • 比较深入的介绍了CAN网的定时和同步机制,可以更深刻的认识CAN网。
  • 小实验一:编写一个没有线程同步机制的程序,调试程序,观察在执行程序的过程中,出现的问题并解答原因 小实验二:使用Windows互斥信号量操作函数解决上述线程并发问题,并分析、尝试和讨论线程执行体中有关信号量...
  • 进程同步机制一、进程同步的几个重要概念二、软件同步机制2.1 双标志位法三、硬件同步机制3.1 关中断3.2 测试并建立(Test-and-Set,TS)指令3.3 对换指令四、信号量机制4.1 整型信号量4.2 记录型信号量4.3 AND型...


    进程的同步机制包含软件同步机制、硬件同步机制、信号量机制等,也就是这些机制,可以保证程序并发执行时的可再现性,在介绍之前,我们先来看下几个概念:

    一、进程同步的几个重要概念

    进程同步机制的主要任务,是对多个相关的进程在执行次序上进行协调,使并发执行的诸多进程之间能够按照一定的规则共享系统资源,并能很好的相互合作,从而使程序之间的执行具有可再现性。

    • 1. 进程间的两种制约关系:

      • 间接相互制约(互斥):因为进程在并发执行的时候共享临界资源而形成的相互制约的关系,需要对临界资源互斥地访问;
      • 直接制约关系(同步):多个进程之间为完成同一任务而相互合作而形成的制约关系。
    • 2. 临界资源:
      指同一时刻只允许一个进程可以该问的资源称之为临界资源,诸进程之间采取互斥方式,实现对临界资源的共享。

    • 3. 临界区
      进程中访问临界资源的那段代码。
      每个进程在进入临界区之前,应先对欲访问的临界资源的“大门”状态进行检测,如果“大门”敞开,进程便可进入临界区,并将临界区的“大门”关上;否则就表示有进程在临界区内,当前进程无法进入临界区。

    • 4. 指令
      指令就是机器语言的一个语句,它是一组有意义的二进制代码,因为是机器语言的一条指令,所以指令就可以等价于是原子性的,只有在执行完一条指令后才会去响应中断。

    • 5. 原语
      由若干条指令组成的,用户完成一定功能的一个过程。原语操作的一个特点就是“原子操作”,
      因此原语在执行的过程中不允许被中断。原子操作在系统态下执行,常驻内存。

    • 同步机制应遵循的规则

      • 1. 空闲让进:当临界区的“大门”敞开时,应当允许一个请求的进入临界区的进程立即进入临界区。
      • 2. 忙则等待:当临界区的“大门”关闭时,因而其他试图进入临界区的进程必须等待,以保证对临界资源的互斥访问。
      • 3. 有限等待:对要求进入临界区的进程,应保证有限的时间能进入自已的临界区,以免陷入“死等” 状态。
      • 4. 让权等待:当进程不能进入自已的临界区时,应立即释放处理机,以免进程陷入“忙等”状态。

    忙等死等 都是没能进入临界区,它们的区别如下:

    • 死等: 对行死等的进程来说,这个进程可能是处于阻塞状态,等着别的进程将其唤醒(signal 原语),但是如果唤醒原语一直无法执行,对于阻塞的进程来说,就是一直处于死等的状态,是无法获得处理机的。
    • 忙等:忙等状态比较容易理解,处于忙等状态的进程是一直占有处理机去不断的判断临界区是否可以进入,在此期间,进程一直在运行,这就是忙等状态。有一点需要注意的是,忙等是非常可怕的,因为处于忙等的进程会一直霸占处理机的,相当于陷入死循环了。 忙等的状态在单CPU 系统中是无法被打破的,只能系统重启解决。

    不管是“忙等”还是“死等”,都是对OS 有害的,都应该努力避免。


    二、软件同步机制

    其实说到使用软件来实现同步机制,大家想到最多的应该就是 Java 多线程,Java 通过锁,synchronized,信号量等机制实现了线程的同步,但是线程间是共享父进程中的所有资源的。
    但是当线程之间,如果需要共享系统资源时,进程之间很难直接通过软件来进行交流,对系统资源的互斥共享就很麻烦,需要借助硬件资源来完成同步,需要在内存中单独使用一块区域来保存进程是否在临界区内的标志。

    2.1 双标志位法

    先来看一段代码:

    // inside1, inside2, 是进程p1 和 p2 在内存中保存的标志,表示进程是否在临界区
    inside1 = false;
    inside2 = false;
    
    // 进程p1
    process p1
    begin
    	while(inside2);	// 循环测试,当 inside2=false 时往下走
    	
    	inside1 := true;
    	临界区
    	inside1 := false;
    end;
    
    
    // 进程p1
    process p2
    begin
    	while(inside1);	// 循环测试,当 inside1=false 时往下走
    	
    	inside2 := true;
    	临界区
    	inside2 := false;
    end;
    

    代码逻辑很清晰,就是进程p1 或 p2 想进入临界区之前,先去判断对方是否在临界区内,如果在的话,就一直循环等待,束则就进入临界区,然后挂锁。
    第一眼看起来没啥问题,但是如果进程在执行期间,比如p1 中的while 判断完比后,进入,在inside1 = true 之前发生了中断,p1 进入了临界区,但锁没来得及挂上;因此如果此时 进程p2 运行时,也可以进入临界区,这种情况下两个进程同时进入了临界区,进程的执行就会出现错误。

    虽然前面的是小概率事件,但也是可能存在的。


    针对这个问题,你可能会想,我在判断之前挂上锁呢,我们把代码的须序调整一下:

    // inside1, inside2, 是进程p1 和 p2 在内存中保存的标志,表示进程是否在临界区
    inside1 = false;
    inside2 = false;
    
    // 进程p1
    process p1
    begin
    	inside1 := true;
    	while(inside2);	// 循环测试,当 inside2=false 时往下走
    	临界区
    	inside1 := false;
    end;
    
    
    // 进程p1
    process p2
    begin
    	inside2 := true;
    	while(inside1);	// 循环测试,当 inside1=false 时往下走
    	临界区
    	inside2 := false;
    end;
    

    这样的话,进程 p1 和 p2 在并发执行的时候就没有问题了。
    我们来看这样一种情况,p1 先执行,挂锁成功,假设在成功之后,p1 发生了中断,进程p2 开始执行,此时p2 同样也可以挂锁,但是在判断是否可以进入临界区时,无法成功,会一直循环中断判断,当p1 恢复再次执行时,尴尬的事情发生了,p1 也无法进入临界区了,因为 p2 同样把锁给锁上了。


    双标志位法先检查可能会让两个进程同时进入临界区,双标志位法后检查可能会让两个进程都无法进入临界区,形成死锁问题。



    三、硬件同步机制

    前面我们在软件同步机制里,都是在落锁和判断之间发生中断,乃至导致无法实现互斥进入临界区,
    那么我们是不是可以在这个期间不允许发生中断呢?

    这就需要用到硬件了。

    3.1 关中断

    这个方法简单有效,进程在落锁和判断之间不是有可能发生中断么,那我们在测试之前关闭中断(OS 内核不响应中断信号),到测试并上锁后在打开中断。
    这样可以保证两个操作之间的连续性,保证临界资源的互斥访问。

    3.2 测试并建立(Test-and-Set,TS)指令

    我们使用关中断来解决落锁与判断之间不允许响应中断,但是我们如果把这两个执行变成一条指令呢?
    这样是不是就可以保证中断不会在落锁和判断之间被响应?

    我们可以借助一条硬件指令 — “测试并建立” 指令TS(Test-and-Set)来实现临界资源的互斥访问。

    TS 指令一般描述如下:

    // TS 指令
    boolean TS(boolean * lock){
    	if(*lock == false){
    		*lock = true;
    		return true;
    	}else{
    		return false;
    	}
    }
    
    boolean lock;
    lock = false; // 临界区可以进入
    
    // 进程 p1, p2, p3,..., pn
    process pi{
    	// ...
    	while( !TS(&lock) ); //循环请求锁
    	临界区;
    	lock = false; // 解锁,归还临界次源
    }
    

    我们可以把TS 指令看成上面的TS 函数的执行过程,其执行过程是一可分割的,即是一条原语。
    当 lock 值为 false 时,表示临界资源空闲,当lock 的值为true 时,表示该资源正在被使用。

    使用TS 指令管理临界区时,需要为每个临界资源设置一个布尔变量lock。 当有进程需要进入临界区时,需要先用TS 指令尝试临界区对应的那把锁。
    如果返回true,临界区空闲,可以进入,并落锁 ,阻止别的进程再进入临界区;
    如果返回fase,则必须要循环请求,直到TS 返回的值变为 true。

    3.3 对换指令

    该指令也称为 swap 指令,用于交换两个字的内容,其处理过程描述如下:

    void swap(boolean * a, boolean * b)
    {
    	boolean tmp;
    	tmp = *a;
    	*a = * b;
    	*b = tmp;
    }
    
    boolean lock;
    lock = false;  // 临界区可以进入
    
    // 进程 p1, p2 ,p3 ,p4
    process pi{
    	do{
    		swap(&lock, & key);
    	}while(key != false)		// 循环请求锁
    }
    临界区
    lock = false;
    

    swap 指令 和 TS 指令 类似,也需要为每个临界资源设置一个布尔变量lock,不同的进程中使用一个局部变量key 字段去替换出lock中的值 ,通过key 的值就可以判断出临界资源是否空闲。

    有一点需要注意的,因为原语是将多个指令合并成一个指令,在原语的执行过程中也是不响应中断的,使之成为原子操作,
    这个期间,等于是屏蔽中断,也就等价于我们讲的第一种硬件方式----- 关中断,
    因此原语操作的指令长序应该是短小精悍的,这样才能保证系统的效率。



    四、信号量机制

    信号量机制是1965年迪杰斯特拉(Edsger Wybe Dijkstra)提出的一种卓有成效的进程同步工具。
    信号量机制在长期的应用中得到了很大的发展,从整型信号量经记录型信号量,进而发展为“信号量集”机制,在目前来讲,信号量。

    需要着重说明的一点是:
    信号量除了初始化外,仅能被通过两个标准的原子操作wait(S)signal(S)来访问,这两个操作也被称为P、V操作,这几个操作都是原语操作。


    4.1 整型信号量

    整型信号量是最开始由迪杰斯特拉定义的,整型信号量也很简单,里面只有一个表示资源的数量的整形量,
    一般使用S符号来表示,整型信号量下的wait和signal操作可描述如下:

    int S;   // 整型信号量定义
    
    // P 操作
    wait(S){
    	while(S <= 0);
    	S--;
    }
    
    //V 操作
    signal(S){
    	S++;
    }
    

    因为wait和signal操作是原子的,因此他们在执行的过程中是不可被中断的。
    也就是说当一个进程在修改某个信号量时,没有其他的进程可以同时对该信号量进行修改。

    需要注意的是,整型信号量的wait操作,只要是信号量S<=0,就会不断的测试,让进程处于一种“忙等”的状态,没有遵循让权等待的原则。

    还有就是,把信号量的初值置为1,表示只允许一个进程访问临界资源,此时的信号量就可以转换为互斥信号量,用于完成进程的互斥(对所有的信号量机制都是一样)。


    4.2 记录型信号量

    ​为了解决整型信号量存在的忙等问题,应当采取让权等待原则。
    但是又会出现一个新的问题,如果多个进程并发请求访问临界资源,除了第一个抢到了信号量外,其余的进程都应该释放处理机,但是这些等待的进程要如何保存呢?

    为此,除了wait操作需要遵循让权等待原则,还需在信号量中增加一个进程的链表指针list,用与链接上面描述的多个等待访问临界资源的进程。
    也因为记录了等待的进程,这种信号量集之被称为记录型信号量。

    记录型信号量具体的描述以及对应的wait和signal操作如下所示:

    //记录型信号量
    typedef struct{
    	int value;
    	struct process_control_block * list;
    }semaphore;
    
    // P操作
    wait(semaphore *S)
    {
    	S->value --;
    	if(S->Value < 0){
    		block( S->list );
    	}
    ]
    signal(semaphore *S){
    	S->value++;
    	if(S->value <= 0){
    		wakeup(S->list);
    	}
    }
    

    ​ 在记录型型号量中,S->value的初值表示系统中某类资源的数目;对它每次wait操作,意味进程请求一个单位的该类资源,使得系统中可分配的该类资源数减少一个,因此描述为S->value–;
    当S.value<0时,表示在执行此次分配之前,系统中的该类资源已经全部分配完了,因此该访问进程应调用block原语进行自我阻塞,放弃处理机并插入到等待进程的队列S->list中。

    我们再来分析下signal操作,首先释放一个单位资源(S->value++),然后判断是否有进程在等待申请信号量,如果有的话,就应该调用wakeup原语从等待队列(list所链接的进程队列)中唤醒一个进程。

    通过上面的描述,我们来说一下在记录型型号量中,value值所代表的意义:

    1. value>0,此时表示系统中还剩余的该类资源的数量;
    2. value=0,此时恰好处于一个平衡状态,系统中的资源分配完了,同样也没有进程在等待资源,即list队列中是没有等待进程的;
    3. value<0,此时,value的绝对值表示有多少个进程在等待申请信号量,也即是list队列的长度。并且P、V操作必须成对的出现,有一个P操作就必定有一个与之配对的V操作(当为互斥操作时,它们同处于同一进程当为同步操作时,则不在同一进程中出现)。

    4.3 AND型信号量

    AND信号量正如其名,其基本思想是:
    将进程在整个运行过程中需要所有资源,一次性的全部分配给进程,待进程使用完后再一起释放。

    AND 信号量可以满足某些进程需要申请多个资源后才可以执行任务的场景,并且AND 信号量可以解决死锁问题,
    比始哲学家进餐问题中,一次给哲学家分配左右两支筷子,那么就不会有哲学家会因为吃不到而饿死了。

    AND 信号量使用的还是记录型信号量的数据结构,下面是 Swait 操作和 Ssignal 操作:

    //记录型信号量定义
    typedef struct{
    	int value;
    	struct process_control_block * list;
    }semaphore;
    
    //P操作
    SWait(S1, S2, ..., Sn){
    	while(true){
    		if(S1 >= 1 && ... && Sn>=1){
    			for(i = 1; i<n; i++)
    				Si--;
    			break;
    		}
    	}else{
    		// 将进程插入到第一个无法满足条件(即 Si<1)的信号量对应的等待队列中,
    		//并且将程序计数器放置到 Swait操作的开始处
    	}
    }
    // V 操作
    Ssignal(S1, S2, ..., Sn){
    	while(true){
    		for(i = 1; i<n ; i++){
    			Si++;
    			将Si 中等待队列中的所有进程全部移除,插入到就绪队列中
    		}
    		break;
    	}
    }
    
    

    需要注意的就是,因为一次申请多个资源,所以在申请的过程中,如果因为哪一类资源不足而阻塞(请求N多个资源时第一个发现不满足的资源,即资源数<1),就要将进程插入到对应信号量的list中;
    与之对应的唤醒操作也有所不同,不再是唤醒阻塞队列中的某一个进程,而是将等待队列中的所有进程全部移除,插入到就绪队列中,让这些进程再次执行一次资源请求操作(这里因为是一次请求多个资源,后面可能依旧有资源无法满足进程的需求)。


    4.4 信号量集

    在前面讲的信号量机制中,wait、signal操作仅能对信号量施以加1或者减1操作,当一次需要N个单位的资源时,便要执行N次的wait(S)操作,这显然是低效的,并且会增大发生死锁的概率(需要执行N次,在这N次执行的过程中可能会发生中断,资源也可能会被别的进程抢占)。

    此外,在某些情况下,为了确保系统的安全性,当所申请的资源数量低于某一个下限时,就不予分配(保证地主家里有余粮)。

    为了满足上述的两个需求,信号量机制又升级了,在AND型信号量的基础上进行扩充,对进程所申请的所有资源,在一次P、V操作中完成申请或释放。并且进程对每类信号量的测试值也不在是1,而是该资源的分配下限ti,也就是要求Si≥ti,否则不予分配。因此这里就不在给出具体的Swait和Ssignal的代码了,而是给出函数声明:

    Swait(S1, t1, d1, ... , Sn, tn, dn);
    Ssignal(S1, d1, ... , Sn, dn);
    

    这里与记录性型号量稍有不同的地方就是判断每类资源是否满足需求时,
    判断的条件由Si>=1变为Si>=ti,并且分配资源由Si–变为Si=Si-ti;
    与之对应的Ssignal操作,不同的一点就是,一次可以归还多个资源,相对应的资源释放代码由Si++变为Si=Si+ti。

    需要注意的是,因为AND型信号量和信号量集一次申请进程执行所需的全部资源,这样的优点就是简单、易行且安全,但是缺点也很明显:

    1. 资源被严重浪费,严重的恶化了资源的利用率;
    2. 使进程经常会发生饥饿现象(因为个别资源被占用的概率很大,会导致进程因为申请不到所有资源迟迟得不到执行)。

    五、管程机制

    虽然信号量机制是一种既方便、又有效的进程同步机制,但是每个访问临界资源的进程都需要自备同步操作wait(S)和signal(S)操作,这就使大量的同步操作分散在各个进程中,不利于大家去集中的思考、抽象,使得程序设计的时候难度非常大,容易产生各种各样的程序设计错误。

    在这样的情况下,便产生了一种新的进程同步工具----管程(Monitors)。值得一提的是,管程也是迪杰斯特拉提出的。


    ​ hansen对管程的定义如下:
    一个管程定义了一个数据结构和能力为并发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据

    由上述的定义可知,管程有四部分组成:

    1. 管程的名称;
    2. 共享数据结构说明;
    3. 对数据结构进行操作的一组过程;
    4. 初始化语句。

    下面我们来看下管程的语法描述:

    //管程的描述
    Monitor monitor_name {//管程名
      share variable declarations;   //共享变量说明
      cond cond_declarationas;       //条件变量说明
      public:						 //能被进程调用的过程
      void P1(...){					 //对数据结构操作过程
        ...
      }
      void P2(...){
        ...
      }
      ...
      void(...){
        ...
      }
      ...
      {
        initilization code;         //初始化代码
      }
    }
    
    

    通过上面的代码描述,你是不是觉得很熟悉!
    实际上,管程中包含了面向对象的思想,它将共享资源、对共享资源的操作抽象成变量和方法,并与同步机制一同封装在一个对象内部,隐藏了实现细节。

    但是你所不知道的是,在管程出现的时候,还没有面向对象程序设计,是不是很意外。

    封装于管程内部的数据结构仅能被管程内部的过程访问(类似于Java中的私有变量),如果想在管程外部访问管程内部的数据结构,就必须使用内部过程(管程内部的public修饰的方法,Java 类中的公共方法)。

    所有的进程想要访问临界资源,都只能通过管程间接的访问,并且管程每次只允许一个进程进入管程,从而实现了进程互斥。

    有一点需要说明的是,管程为了实现更加复杂的进程同步方式,增加了一个条件变量。
    通常会根据进程被阻塞或者挂起的原因,设置不同的条件变量,
    每个条件变量保存一个链表指针,用与链接所有因为该条件变量而阻塞或挂起的所有进程,
    同时提供两个P、V操作也可以表示为x.wait和x.signal,

    这两个操作的含义如下:

    1. x.wait:正在调用管程的进程因x条件需要被阻塞或挂起,则调用x.wait将自己插入到x条件的等待队列中,并释放管程,直至x条件发生变化。
    2. x.signal:正在调用管程的进程因为x条件发生了变化(资源使用完,归还),则调用x.signal,重新启动一个因x条件而阻塞或挂起的进程,如果存在多个,则选择其中的一个,如果没有,继续执行原进程,不产生任何唤醒操作。

    对于上面的操作,其实是有些问题的,我们设想一下,如果进程P1因x条件处于阻塞状态,那么当进程P2执行了x.signal操作唤醒P1后,进程P1和P2此时同时处于管程中了,这是不被允许的,那么如何确定哪个执行哪个等待?这个问题也很简单,可采用下面的两种方式之一进行处理:

    1. P2等待,直至P1离开管程或者等待另一个条件;
    2. P1等待,直至P2离开管程或者等待另一个条件。

    采用哪种处理方式,也存在很多争论。Hoare采用了第一种处理方式,而Hansen采用了两者的折中,它规定管程中的所有过程执行的signal操作是过程体的最后一个操作,于是,进程P2执行完signal操作后立即退出管程,因此进程P1马上被恢复执行。

    但是hansen的这种折中的办法,规定死了释放的时机,增加了程序设计的难度。因此现在的管程普遍采用Hoare的方式,也被称为霍尔管程。霍尔管程相比于管程、汉森管程,他的一个更大的优势是可以基于PV操作原语来实现,换一句话说就是,wait和signal可以是程序过程而不需要是原语实现(可以使用语言机制实现霍尔管程)。这个就很厉害了,霍尔管程可以基于操作系统的程序库或者是高级程序设计语言,在基础的P、V操作原语上实现wait和signal操作,而不用扩展操作系统的内核。

    管程的示意图如下,从图中我们可以看到,每个条件变量都有一个对应的等待队列,除了等待调用管程的进程队列外,还有一个紧急队列(优先级高,由进程调用signal操作后插入),对于具体的操作,我们可以结合霍尔管程中条件变量中的wait、signal操作来讲。
    在这里插入图片描述

    下面是霍尔管程的条件变量上的wait操作和signal操作的描述:

    //霍尔管程使用的信号量定义
    //semaphore为本文之前定义的记录型信号量
    typedef struct{
      semaphore mutex;    //用与管程调用的互斥信号量
      semaphore next;			//发出signal的进程挂起自己的信号量,信号量中记录着等待调用管程的进程
      int next_count;			//在next上等待的进程数
    }interf;
    
    //霍尔管程中的条件变量
    typedef struct{
      semaphore x_sem;    //与资源相关的信号量
      int x_count;        //在x_sem上等待的进程数
    }cond;
    
    //条件变量对应的wait操作
    wait(cond declar, interf IM){
      declar->x_count++;         //在条件变量declar上等待的进程数量加1
      if(IM->next_count > 0){   //判断是否有进程在高优先级队列中
        V(IM->next);						//唤醒因调用signal操作的进程
      } else {
        V(IM->mutex);						//没有的话,唤醒一个等待进入管程的进程
      }
      P(declar->x_sem);         //释放资源后,立即把自己挂起
      declar->xcount--;         //恢复执行后,重新开始执行,退出管程,条件变量declar等待的进程数量减1
    }
    
    //条件变量对应的signal操作
    signal(cond declar, interf IM){
      if(declar->x_count > 0){  //判断是否有等待条件变量的进程
        IM->next_count++;       //挂起自己后,因为调用signal挂起自己的进程数量加1
        V(declar->x_sem);       //唤醒一个等待条件变量的进程
        P(IM->next);            //释放资源后,立即把自己挂起,进入高优先级队列
        IM->next_count--;       //恢复执行后,等待调用的管程的进程数量减1
      }
    }
    
    

    我们看上面的代码,此时的wait操作和signal操作与P、V原语是有区别的,wait和signal是在P、V的基础上实现的。首先我们来看下wait操作,唤醒进程(高优先级队列或者是等待调用管程的队列)后,立即将自己挂起,并将自己插入到对应的条件变量的等待队列中(上图中左上方的队列),当被唤醒再次执行时,将对应的等待数量减1。我们在来看下signal操作,首先判断是否有等待条件变量的进程,如果没有的话,就可以什么都不用执行;如果有进程在条件变量的等待队列中,则从队列中唤醒一个,并挂起自己,插入到紧急队列中。

    ​ 霍尔管程中的wait、signal操作比较抽象,可以结合图片查看,可以帮助理解。




    学自《操作系统武功修炼心法

    展开全文
  • 本文档系操作系统课程线程同步机制的实验报告,实验内容包括:无同步机制、调用Mutex互斥变量、使用peterson软件法实现线程同步。完整的cpp源代码见文档附录。
  • 操作系统实验-简单进程同步机制模拟
  • 实现Nachos的同步机制:锁和条件变量,并利用这些同步机制实现几个基础工具类
  • Kafka副本同步机制

    千次阅读 2020-09-29 15:34:01
    一、Kafka副本同步机制 Kafka中topic的每个partition有一个预写式日志文件,每个partition都由一系列有序的、不可变的消息组成,这些消息被连续的追加到partition中,partition中的每个消息都有一个连续的序列号叫做...

    一、Kafka副本同步机制

    Kafka中topic的每个partition有一个预写式日志文件,每个partition都由一系列有序的、不可变的消息组成,这些消息被连续的追加到partition中,partition中的每个消息都有一个连续的序列号叫做offset,确定他在partition中的唯一位置。
    在这里插入图片描述
    kafka每个topic的partition有N个副本,其中N是topic的复制因子,Kafka通过多副本机制实现故障自动转移,当Kafka集群中一个Broker失效情况下,仍可保证服务可用。在Kafka中发生复制时确保partition的预写式日志有序地写到其他节点上。N个replicas中,其中一个replica为leader,其他都为follower,leader处理partition的所有读写请求,与此同时,follower会被动定期地区复制Leader上的数据。

    如下图,Kafka集群中有4个broker,某topic有3个partition,且复制因子即副本个数也为3:
    在这里插入图片描述
    Kafka提供了数据复制算法,如果leader发生故障或挂掉,一个新leader被选举并被接受客户端的消息成功写入。Kafka确保从同步副本列表中选举一个副本为leader,或者说follower追赶leader数据。leader负责维护和根据ISR(In-Sync Replicas的缩写,表示副本同步队列)中所有消息,follower之后的桩体。当producer发送一条消息到broker后,leader写入消息,并复制到所有follower。消息提交之后才被成功复制到所有的同步副本。消息复制延迟受最慢的follower限制,重要的是快速检测慢副本,如果follower“落后”太多或者失败,leader将会把他从ISR中删除。

    二、副本同步队列ISR

    所谓同步,必须满足两个条件:

    • 副本节点必须能与zookeeper保持会话(心跳机制)
    • 副本能复制leader上的所有写操作,并且不能落后太多(卡主或滞后的副本控制由replica.lag.time.max.ms配置)

    默认情况下,Kafka topic的replica数量为1,即每个partition都有一个唯一的leader,为了确保消息的可靠性,通常应用中将其值(由broker的参数offsets.topic.replication.factor指定)大小设定为1。所有的副本(replicas)统称为AR (Assigned Replicas)。ISR是AR的一个子集,由leader维护ISR列表,follower从Leader同步数据有一些延迟,任意一个超过阈值都会把follower踢出ISR,存入OSR(Outof-Sync Replicas)列表,新加入的follower也会先存放到OSR中。AR = ISR + OSR

    HW(HighWatermark)俗称高水位,取一个partition对应的ISR中最小的LEO作为HW,consumer最多只能消费到HW所在的位置。另外每个replica都有HW,leader和follower各自负责更新自己的HW的状态。对于leader新写入的消息,consumer不能立即消费,leader会等待该消息被所有ISR中的replicas都同步后,才更新HW,此时消息才能被consumer消费,这样就保证了如果Leader所在的broker失效,该消息仍可从新选举的leader中获取。对于来自内部的broker的读取请求,没有HW的限制。

    下图详细说明了当producer生产消息到broker后,ISR及HW和LEO(log end offset)的流转过程:
    在这里插入图片描述
    由此可见,Kafka的复制机制既不是完全的同步复制,也不是单纯的异步复制。事实上,同步机制要求所有能工作的follower都复制完,这条消息才会被commit,这种复制方式极大的影响了吞吐率。而异步复制方式下,follower异步的从leader复制数据,数据只要被Leader写入log就被任务已经commit,这种情况下如果follower没有全复制完,落后与Leader,突然leader宕机,则会丢数据。而Kafka这种使用ISR的方式则很好的均衡了确保数据不丢失以及吞吐率。

    Kafka的ISR管理最终都会反馈到Zookeeper节点上,具体位置为:
    /brokers/topics/[topic]/partitions/[partition]/state。目前有两个地方会对这个Zookeeper节点进行维护:
    1)Controller维护:Kafka集群中的其中一个Broker会被选举为Controller,主要负责Partition管理和副本状态管理,也会执行类似于重分配partition之类的管理任务。在符合某些特定条件下,Controller下的LeaderSelector会选举新的leader, ISR和新的leader_epoch及controller_epoch写入Zookeeper的相关节点中。同时发起LeaderAndIsrRequest通知所有的replicas。

    2)leader来维护:leader有单独的线程定期检查ISR中follower是否脱离ISR,如果发现ISR变化,则会将新的ISR的信息返回到Zookeeper的相关节点中。

    副本不同的异常情况:
    1)慢副本:在一定周期时间内,follower不能追赶上leader。最常见的原因之一是IO瓶颈导致follower追加复制消息速度鳗鱼从leader拉取速度
    2)卡住副本:在一定周期时间内,follower停止从leader拉取请求。follower replica卡住了是由于GC暂停或follower失效或死亡。
    3)新启动副本:当用户给topic增加副本因子时,新的follower不再同步副本列表中,直到他们完全追赶上leader日志。

    展开全文
  • Redis 数据同步机制

    千次阅读 2020-08-12 09:05:45
    Redis的主从同步机制可以确保redis的master和slave之间的数据同步。Redis在2.8及以上版本使用psync命令完成主从数据同步。同步方式包括:全量复制和增量复制 1. 同步机制 全量复制 全量复制 slave第一次...
  • 一般eureka server在部署的时候,都会选择集群部署,否则只用一个eureka server的话,万一出现了单点故障的话,那岂不是整个系统直接GG 同时eureka server的...将eureka的集群机制和zookeeper对比一下,zookeeper的集
  • 针对手机和无线网络的限制条件,设计了一套可行的应用在手机多人在线角色扮演类游戏上的网络游戏同步机制。分析了同步技术中的延时问题及其对游戏交互性和公平性的影响以及影响服务器伸缩性的若干因素等。设计的同步...
  • Zookeeper集群选举机制以及数据同步机制 每天多学一点点~ 话不多说,这就开始吧…进击的爆裂无球~ 文章目录Zookeeper集群选举机制以及数据同步机制1.前文2.Zookeeper的选举机制3.Zookeeper的数据同步机制4.关于...
  • 线程同步机制

    千次阅读 2019-02-14 17:52:46
    从广义上说,Java平台提供的线程同步机制包括锁、volatile关键字、final关键字、static关键字和一些相关的API,如Object.wait( )/.notify( )等   1、锁的概述和概念: a 线程安全问题的产生: 多个线程并发访问...
  • WebRTC音视频同步机制

    千次阅读 2022-01-30 14:56:34
    WebRTC音视频同步机制实现分析 - 简书音视频同步事关多媒体产品的最直观用户体验,是音视频媒体数据传输和渲染播放的最基本质量保证。音视频如果不同步,有可能造成延迟、卡顿等非常影响用户体验的现象。因此,它...
  • Redis数据同步机制

    千次阅读 2019-06-02 10:12:00
    Redis数据同步机制01. 同步机制1.1 全量拷贝1.2 增量拷贝02. 同步故障处理2.1 拷贝超时2.2 积压缓冲区拷贝溢出2.3 slave全量同步的响应问题03. 节点名词阐述3.1 节点运行ID3.2 偏移量拷贝3.2 积压缓冲区拷贝 Redis...
  • Linux内核中的同步机制

    千次阅读 2018-08-26 15:54:06
    本文介绍Linux内核中的一些同步机制,通过本文,希望读者能够明白以下几点: 什么是同步 为什么要同步 同步的几种手段 1.什么是同步? 与其解释什么是同步,倒不如告诉读者同步的由来。在Linux内核中,同步技术...
  • 进程同步机制

    千次阅读 2018-12-20 22:26:15
    同步机制中,常用一个变量来代表临界资源的状态,称之为锁。通常用“0”代表资源可用,相当于锁打开,用“1”代表资源已被占用,相当于锁闭合。 对锁的操作有两种:一种是关锁操作,一种是开锁操作 //...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 796,940
精华内容 318,776
关键字:

同步机制

友情链接: GameFramework.zip