Featured image of post Unix系统分析——锁

Unix系统分析——锁

Unix系统分析——锁

总结Unix系统中锁的相关知识

Linux各种锁的实现

原子操作

原子操作是最小的执行单位,保证在执行完毕前不会被其他任何事物或事件打断,也就是说不能有比它更小的执行单位,命名也借用了物理学中物质稳定存在的最小单位——原子。

原子操作于硬件架构相关,由汇编语言实现,一般用于实现计数等操作

信号量

信号量,Semaphore,Linux内核信号量以一个初始值创建,用来表示同时可以有几个任务可以访问由信号量保护的共享资源。初始值为1的信号量就是互斥锁,即在同一时间只能有一个任务可以访问信号量保护的共享资源

实现原理

当一个任务要访问一个由信号量保护的共享资源时,通过信号量提供的操作将信号量的值做减1操作,若此时值变为负数,表示当前资源不可得,该任务必须挂起进入等待队列直到该信号量可用;若值为非负数,表示成功获得信号量,可以访问共享资源。

在任务访问完毕后,需要释放获得的信号量,即通过对应操作将信号量的值加1实现,同时判断当前的值正负。若为非正数,表示当前在等待队列中有其他任务正在挂起等待,因此需要主动唤醒等待中的任务。

读写信号量

读写信号量将信号量按访问目的做了分类——读者和写者。读者对于共享资源只能做读操作,不能修改。而写着可以同时对共享资源进行读写。因为两者对共享变量做的操作不同,因此可以用以下访问规则:

  • 一个读写信号量可以同时拥有多个读者,即多个读者可以同时访问同一个共享资源

  • 读者获得读写信号量的前提是:

    • 当前没有被写者拥有

    • 没有写者在等待信号量释放

      否则,读者需挂起等待写者释放信号量

  • 写者获得读写信号量的前提是:

    • 当前没有被其他读者或写者拥有

    • 没有其他写者在等待信号量释放

      否则,写者需挂起等待直到没有任何访问

总而言之,写者是独占访问资源的,具有排他性,同一时间只能有一个写者访问但对于多个读者可以同时访问。同时,为了保证写者不被饿死,只要有写者在等待,读者就不能进入访问,即使当前是其他读者在访问。

在Linux中,提供了将写者降级为读者的方法

1
void downgrade_write(struct rw_semaphore *sem);

函数用于把写者降级为读者。写者保持读写信号量期间,任何读者或写者都将无法访问该读写信号量保护的共享资源,对于那些当前条件下不需要写访问的写者,降级为读者将使得等待访问的读者能够立刻访问,从而增加了并发性,提高了效率。因此,读写信号量适用于读多写少的情况

自旋锁

spinlock,自旋锁与互斥锁最大的区别就是任务在调用自旋锁时不会入睡,若该自旋锁已经被占用,则调用者会一直循环等待锁的释放,也就是保持“自旋”。自旋锁适用于保持锁的时间非常短的情况,因此为了提高效率,选择自旋而不是入睡。

对比信号量来说,自旋锁可以在进程上下文和中断处理上下文中使用,而信号量只能在进程上下文中使用

在保持自旋锁的期间,进程是不放弃CPU的,而信号量在保持期间是可以放弃CPU的。对于可剥夺的Linux内核,单CPU的情况下,自旋锁只做了关闭中断和开启中断的操作。

读写锁

读写锁就是对自旋锁按访问目的划分为读者,写者,提高系统的并发度。

规则如下:

  • 如果读写锁当前没有读者,也没有写者,那么写者可以立刻获得读写锁,否则它必须自旋在那里,直到没有任何写者或读者
  • 如果读写锁没有写者,那么读者可以立即获得该读写锁,否则读者必须自旋在那里,直到写者释放该读写锁

RCU

RCU(Read-Copy Update),对于被RCU保护的共享数据结构,读者不需要获得任何锁就可以访问它,但写者在访问它时首先拷贝一个副本,然后对副本进行修改,最后使用一个回调(callback)机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的操作

顺序锁

对读写锁的优化,读者不会被写者阻塞,意味着写者在进行写操作时读者仍然可以读取,读写是可以同时发生的,但写者之间依然互斥。

既然读写可以并行,为了保证数据的正确性依然有许多限制:

  • 被保护的资源不能有指针,否则当写者修改指针后,读者读取时可能失效
  • 若读者读取时发生了写操作,读者需要重新读取数据

舒徐所适用于读写同时进行的概率较小的场景,允许读写同时进行,性能和并发度都有提高

生产者消费者问题

问题概述

生产者消费者问题,即共享固定大小缓冲区的两个进程——生产者进程和消费者进程。生产者的主要作用是生成一定量的数据放到缓冲区中,于此同时消费者也在缓冲区中消耗这些数据,然后重复这个过程。主要需要解决的问题是:

  • 保证生产者不会在缓冲区满是加入数据
  • 消费者也不会在缓冲区空时消耗数据

为保证以上两点,就必须让生产者在缓冲区满时休眠或干脆就放弃数据,等到下次消费者消耗缓冲区中的数据的时候,生产者才能被唤醒,开始往缓冲区添加数据。同样,也可以让消费者在缓冲区空时进入休眠,等到生产者往缓冲区添加数据之后,再唤醒消费者。

通常采用进程间通信的方法解决该问题,常用的方法有信号灯法等。必须要注意的是防止出现死锁的情况。出现死锁时,两个线程都会陷入休眠,等待对方唤醒自己。

该问题也能被推广到多个生产者和消费者。

基本实现

使用信号量保证对锁的操作是原子的,防止死锁

在只有一对生产者和消费者的情况下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
semaphore fillCount = 0; // 已生产项目数
semaphore emptyCount = BUFFER_SIZE; // 剩余项目数

procedure producer() {
    while (true) {
        item = produceItem();
        down(emptyCount);
            putItemIntoBuffer(item);
        up(fillCount);
    }
}

procedure consumer() {
    while (true) {
        down(fillCount);
            item = removeItemFromBuffer();
        up(emptyCount);
        consumeItem(item);
    }
}

在多个生产者和消费者的情况下,还需要一个互斥锁保证一次只有一个进程被执行

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
semaphore mutex = 1;	// 互斥锁
semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;

procedure producer() {
    while (true) {
        item = produceItem();
        down(emptyCount);
            down(mutex);	// 保证一次只有一个进程在操作缓冲区
                putItemIntoBuffer(item);
            up(mutex);
        up(fillCount);
    }
}
procedure consumer() {
    while (true) {
        down(fillCount);
            down(mutex);
                item = removeItemFromBuffer();
            up(mutex);
        up(emptyCount);
        consumeItem(item);
    }
}

CAS锁

基本概念

乐观锁与悲观锁

首先区分一下乐观锁和悲观锁的概念

乐观锁

总是假设最好的情况,每次去拿数据的时候都认为别人不会修改,所以不会上锁,但是在更新的时候会判断一下在此期间别人有没有去更新这个数据,可以使用版本号机制和CAS算法实现。乐观锁适用于多读的情况,这样可以提高吞吐量

悲观锁

总是假设最坏的情况,每次去拿数据的时候都认为别人会修改,所以每次在拿数据的时候都会上锁,这样别人想拿这个数据就会阻塞直到它拿到锁。共享资源每次只给一个线程使用,其它线程阻塞,用完后再把资源转让给其它线程,适合多写的情况

什么是CAS

  • CAS即(Compare And Swap),意为比较并替换
  • CAS是CPU的一个指令,因此是原子操作,保证并发安全
  • CAS是非阻塞的、轻量级的乐观锁

实现原理

CAS作为一条CPU指令级别的操作,做的操作为:如果要修改的变量为我期待的值,则将其修改为一个新值,否则这次操作失败。因此,当有多个线程尝试使用CAS更新同一个变量时,只有一个线程能成功更新变量的值,其他都失败,但失败的线程不会入睡,而是再次尝试,直到修改成功。

每个线程做的事情如下

1
2
3
4
do{   
     备份旧数据;  
     基于旧数据构造新数据;  
}while(!CAS( 内存地址,备份的旧数据,新数据))

可以看到,若CAS操作不成功,则重复循环尝试,成功后跳出循环

用CAS锁改造有界缓冲区为无锁队列

用CAS实现一个无锁队列的基本操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
typedef struct Node
{
    int data;
    struct Node *next;
} Node;

Node *head, *tail;	// 共享变量指向队列的头尾

bool is_empty()
{
    if (head->next == NULL)
    {
        return true;
    }
    return false;
}

void push_back(void* data)
 {
    Node* old;
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = NULL;
    
    do 
    {
        // 获取旧尾结点指针
		old = tail;
    // 使用CAS判断此次写入是否成功,只有值为NULL才可写入新结点
    }while (!cas(&(old->next), NULL, newNode));
    
    tail = newNode;
 }

int pop_front(int *e)
{
    Node *old;

    do {
    	if(is_empty())
        	return 0;
        // 获取旧的头结点
        old = head->next;
    // 使用CAS判断当前head指针是否还指向old取到的头节点,是,则从队列中取出该节点,否则失败
    } (!cas(&(head->next), old, old->next));
    
    *e = old->data;
    delete old;
    return 1;
}

之后可将这个无锁队列替换到之前读者写者问题中的有界缓冲区,大大提高系统的并发度

comments powered by Disqus
Let's code the fantastic world!!!
Built with Hugo
主题 StackJimmy 设计