并行程序的潜在问题 (三)

在介绍 Mutex lock 与 Spinlock 後，本篇文章同样针对并行程序的 Synchronization 作探讨，以保证并行程序的执行顺序。

Semaphore

Semaphore 是一个同步物件，用於保持在 0 至指定最大值之间的一个计数值。比起之前介绍的 spinlock 和 mutex lock，semaphore 更像是一个指示号志。
当执行绪完成一次对该 semaphore 物件的等待 (wait) 时，该计数值减一；当执行绪完成一次对 semaphore 物件的释放 (release) 时，计数值加一。
semaphore 物件的计数值大於 0，为 signaled 状态；计数值等於 0，为 nonsignaled 状态.
也就是说，当计数值为 0 时，处於 nonsignald 状态的 semaphore 是无法供执行绪使用的，除非该 semaphore 再次转为 signaled 状态。

Semaphore APIs

使用 Semaphore 前须详阅公开说明书:

sem_t semaphore;
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_wait(sem_t *sem);
int sem_post(sem_t *sem);

在使用 semaphore 前，我们需要使用 sem_init() 将其初始化:

static sem_t semaphore;
sem_init(&semaphore, 0, 1);

透过 Linux manual page 查看 sem_init() 的定义，可以知道它的三个参数从左至右分别为:

• sem_t 型别变数的位址。
• 决定 semaphore 共享於同一个 Process 的 Thread，或是多个 Process。
• semaphore 的初始值。

初始化後，通常我们会在 Critical section 间放置 sem_wait() 与 sem_post() 去避免 Race condition。

sem_wait()

sem_wait() 会检查传入的 semaphore 变数值，如果大於零，则会将它减一。相反的，如果变数值为零，该执行绪就会被 Block。

sem_post()

当执行绪处理完 Critical section 便可以使用 sem_post() 释放 Semaphore 物件。这时，传入的 Semaphore 物件值会被加一。

透过范例程序学习 Semaphore!

比起 Mutex，虽然 Semaphore 同样可以用来保护 Critical section，不过它更常被用来确保并行程序的执行顺序。不像是 Mutex lock 解铃还需系铃人的特性，在 Semaphore 中，每个任务都会消耗与制造不同的号志，考虑以下程序码:

static sem_t A_B;
static sem_t B_C;
static sem_t C_A;

void *printA(void *arg)
{
	int i = 0;
	for(i = 1;i<11;i++){
		sem_wait(&C_A);
		printf("第%02d次:A",i);
		sem_post(&A_B);
	}
	return NULL;
}
void *printB(void *arg)
{
	int i = 0;
	for(i = 1;i<11;i++){
		sem_wait(&A_B);
		printf("B");
		sem_post(&B_C);
	}
	return NULL;
}
void *printC(void *arg)
{
	int i = 0;
	for(i = 1;i<11;i++){
		sem_wait(&B_C);
		printf("C");
		sem_post(&C_A);
	}
	return NULL;
}

在 main() 赋予初始值:

pthread_t thread_A;
pthread_t thread_B;
pthread_t thread_C;
sem_init(&A_B,0,0);
sem_init(&B_C,0,0);
sem_init(&C_A,0,1);
pthread_create(&thread_A,NULL,printA,NULL);
pthread_create(&thread_B,NULL,printB,NULL);
pthread_create(&thread_C,NULL,printC,NULL);
//...

透过 Semaphore，我们不止可以避免 Race condition，更可以保证三个 Task 的执行顺序。

原始码连结: Github。

与 Mutex lock 的异曲同工之妙

文章前面有提到，Semaphore 用於保持在 0 至指定最大值之间的一个计数值。
如果开发者将 Semaphore 设计成只会出现 0 和 1 两种状态，便称为 Binary semaphore。
仔细想想，Binary semaphore 同样确保一次只能有一个执行绪获得共用资源的存取权，比较不同的是 Binary semaphore 不像 Mutex lock 有 Owner ship 的概念。因此在应用上，Binary semaphore 会更具弹性。

这里的弹性是指，当一个 Thread 更改 Semaphore 的状态，程序能够允许另一个 Thread 对同一个 Semaphore 修改状态。换句话说，Binary semaphore 可以让我们造出一个能有它人解锁的 Mutex lock。
关於这个问题，网路上也有人设计相关实验作探讨，有兴趣的读者请参考该连结。

Deadlock 与 Livelock

使用锁或是 Semaphore 确实可以避免 Race condition 的发生，不过，当开发者在设计机制时没有考虑周全，就有可能让程序逻辑打结。

Deadlock

简单来说，当有两个 Process 或是 Thread 需要彼此目前占有的资源，而两者却又不愿意释放资源时，便会让彼此的进度卡住，形成死结。又好比两个人做交易，买家坚持卖家先出货，卖家则坚持买家先付款，导致交易僵持，如果在电脑中出现类似的情况，就称为 Deadlock。

Deadlock 范例

考虑以下程序码:

// Source: https://stackoverflow.com/questions/27480125/simple-deadlock-example-using-pthread/50111909
pthread_mutex_t lock1, lock2;

void *resource1(){

    pthread_mutex_lock(&lock1);

    printf("Job started in resource1..\n");
    sleep(2);

    printf("Trying to get resourc2\n");
    pthread_mutex_lock(&lock2); 
    printf("Aquired resourc2\n");
    pthread_mutex_unlock(&lock2);

    printf("Job finished in resource1..\n");

    pthread_mutex_unlock(&lock1);

    pthread_exit(NULL);

}

void *resource2(){

    pthread_mutex_lock(&lock2);

    printf("Job started in resource2..\n");
    sleep(2);

    printf("Trying to get resourc1\n");
    pthread_mutex_lock(&lock1); 
    printf("Aquired resourc1\n");
    pthread_mutex_unlock(&lock1);

    printf("Job finished in resource2..\n");

    pthread_mutex_unlock(&lock2);

    pthread_exit(NULL);

}



int main() {

    pthread_mutex_init(&lock1,NULL);
    pthread_mutex_init(&lock2,NULL);

    pthread_t t1,t2;

    pthread_create(&t1,NULL,resource1,NULL);
    pthread_create(&t2,NULL,resource2,NULL);

    pthread_join(t1,NULL);
    pthread_join(t2,NULL);

    return 0;

}

在上面的范例中，两个 Task 都会尝试 Lock 两个互斥锁，一个 Task 先上锁 lock1 再上锁 lock2，另一个则相反。当这两个 Task 尝试上获得第二道锁时，就会因为对方迟迟不交出资源而陷入 Deadlock 的状况。

Deadlock 触发条件

要让程序进入死结，必须天时地利人和:

• No preemption： 占用系统资源的一个任务无法被强制停止。
• Hold and wait： 一个行程可以在等待时持有系统资源。
• Mutual exclusion： 系统资源只能同时分配给一个行程，无法在多个行程共享。
• Circular waiting： 多个行程互相持有其他行程所需要的资源。

要达成以上条件，程序才有可能进入 Deadlock，作业系统在做排程设计时也会将其考虑进去，做出应对机制，像是: 让任务是可以被作业系统强制结束的。

Starvation

当一个 Process 迟迟无法获得所需资源，进入长期等待，这种情况就可以称为 Starvation (饥饿)。作业系统为了避免饥饿/死结发生，除了上面提到的可抢断式排程，也添加了老化的机制，也就是: 当一个 Process 久久没有执行完成，作业系统便会逐步调高它的优先权，增加该 Process 完成的速度。

对排程演算法感兴趣的话，可以参考作业系统概念学习笔记 10 CPU 排程。

Livelock

Livelock 不同於 Deadlock，Livelock 发生在彼此竞争但都愿意让步的情况，用生活上的例子就像是: 当我们走在行人道遇到对向的行人，两个人都想让路给对方却又很刚好的站到同一边，在电脑中，这样看似有在执行却毫无进展的情况就是 Livelock。

Reference

• semaphore, mutex, spin lock
• Linux manual page
• Mutex, Semaphore, the difference, and Linux kernel
• 三、Queue 的应用(3) - Semaphore、Mutex的同步
• deadlock跟starvation教会我的人生哲学