mutex locks

Mutex locks

​

critical-section problem (临界区问题)

define

  • Each concurrent(并发的) process has a segment of code, called a critical section(临界区), in which the process may be changing common(共有的) variables, updating a table, writing a file, and so on.
  • The important feature(特征) of the system is that, when one process is executing in its critical section, no other process is allowed to execute in its critical section. That is(换句话说), NO two processes are executing in their critical sections at the same time.
  • The critical-section problem is to design a protocol(协议) that the processes can use to cooperate(协作).

进程进出临界区协议

伪代码：

1
2
3
4
5
6
do
{
entry secion
    critical section
exit section
}
  • 进入临界区前在 entry section 要请求许可
  • 离开临界区后在exit section 要归还许可

临界区管理准则

  • Mutual(相互的) exclusion(排他的) (Mutex)：互斥
  • Progress：前进
  • Bounded waiting：有限等待

只有一个进程可以进入到临界区，一个进程不可以无限的待在临界区当中

秘籍：

有空让进，泽一而入，无空等待，有限等待，让权等待

mutex lock互斥锁

define

  • Operating-systems designers build software tools to solve the critical-section problem. The simplest(最简单的) of these tools is the mutex lock.
  • A process must acquire(获得) the lock before entering a critical section;
  • It must release(释放) the lock when it exits the critical section

锁的基本操作

  • lock：测试一把锁是否已经上锁，若未上锁则上锁，若以上锁则等待
  • unlock：解锁
  • lock 与 unlock 均为原子操作(不能被打断)

原子操作

  • Atomic operations mean the operation can NOT be interrupted while it’s running.
  • 原子操作（原语）是操作系统重要的组成部分，下面2条(大多数)硬件指令都是原子操作，它们可以被用来实现对临界区的管理（也就是“锁”）。
    test_and_set()
    compare_and_swap()

锁的实现

test_and_set实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
test_and_set函数的过程:(这里用C语言的方式解释，但实际上它是一条原语)
bool test_and_set(bool *target)   //将传入参数的所指值值为false，并返回传入参数的所指值
{
    bool result = *target;
    *target = false;
    return result;
}
锁的实现：
bool available = true;    //lock和unlock共享的资源，初始化为 1 表示被占用
lock(){    
    while(!test_and_set(&available))   //循环等待共享变量置为true
        do nothing
}
// .... 临界区
unlock()
{
    available = true;
}

忙式等待（BUSY WAITING）

  • 忙式等待是指占用CPU执行空循环实现等待，解决方法是让进程加入到等待队列中，避免消耗CPU
  • 这种类型的互斥锁也被称为“自旋锁”(spin lock)
    • 缺点：浪费CPU周期，可以将进程插入等待队列以让出CPU 的使用权；
    • 优点：进程在等待时没有上下文切换，对于使用锁时间不长的进程，自旋锁还是可以接受的；在多处理器系统中， 自旋锁的优势更加明显，因为可以实现在一个核心上自旋其他核心运算

实践

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
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int ticketAmount = 2;

void *ticketMmount(void *arg)
{
    pthread_mutex_lock(&lock);
    int t = ticketAmount;

    if(t > 0)
        printf("One ticket sold\n");
    else
        printf("Ticket sold out\n");
    ticketAmount = t;
    pthread_mutex_unlock(&lock);
    pthread_exit(0);
}
int main()
{
    pthread_t tichetAgent_tid[2];
    for(int i=0;i<2;++i)
    {
        pthread_create(tichetAgent_tid + i,NULL,ticketMmount,NULL );
    }
    for(int i=0;i<2;++i)
    {
        pthread_join(tichetAgent_tid[i],NULL);
    }
}

参考：https://www.bilibili.com/video/BV1bf4y147PZ