[OS] Process Synchronization

1. Introduction

Multi-processing, multi-core, multi-threading과 같이 다수의 주체가 공유하고 있는 자원을 접근 할 때 synchronization을 하지 않으면 우리가 의도하지 않는 동작이 system에서 발생할 수 있다.

1.1 Critical section

Critical section은 오직 하나의 process만이 수행되고자 하는 code segment를 말한다. Critical section에는 shared variable이 존재하는데, consistency를 유지하기 위해선 process synchronization이 필요하다.

위 그림을 보면 서로 다른 process가 key라는 variable을 가지고 critical section에 진입하려고 하는 모습이다.

1.2 Race condition

Race condition은 하나 이상의 process가 동일한 memory access를 할 때, 각 process의 access 순서에 따라서 수행 결과가 달라질 수 있는 상황을 말한다. 이런 문제를 해결하기 위해선 atomic instruction 사용, lock / atomic variable 활용 등의 synchronization scheme을 통해 예방 할 수 있다.

2. Solution

2.1 Mutex (Locks)

Mutex는 locking mechanism으로 lock을 가지고 있는 경우에만 shared resource에 접근 가능하도록 하는 방식이다. 만약 아래와 같은 프로그램이 있다고 가정하자.

이런 경우에 Th1과 Th2가 모두 X와 Y resource를 점유할 경우 deadlock이 발생한다.

만약 lock의 순서가 두 thread가 동일하다면 deadlock은 발생하지 않을 것이다. 이 때도 중요한 부분은 lock (X)를 잡는 것을 반드시 한 thread만 잡을 수 있도록 atomic operation (mutex)을 보장해야 한다.

Example

#include <pthread.h>
#include <stdio.h>

#define  MAX_THREAD   2
int sum = 0;
void *thread_routine( void * arg ) {
    int local,i;
    for(i=0; i<10000000/MAX_THREAD; i++ ) {
        local = sum;
        local = local+1;
        sum = local;
    }
    return arg;
}
int main( int argc, char **argv ) {
    pthread_t thread_id[MAX_THREAD];
    void *thread_result;
    int status, i;

    for(i=0; i<MAX_THREAD ; i++)
        status = pthread_create( &thread_id[i],0,thread_routine,0);

    for(i=0; i<MAX_THREAD ; i++)
        status = pthread_join( thread_id[i], &thread_result);

    printf("sum=%d\n", sum);
    return 0;  
}

위 코드는 두 thread가 공유하는 변수의 값을 계속 accumulation 하는 프로그램이다. 이 때 따로 lock이 없이 수행하기 때문에 비 정상적 동작을 한다. 따라서 해결하기 위해선 critical section (공유 변수에 접근하는 부분)에 대해서 exclusive access를 보장해야 한다.

#include <pthread.h>
#include <stdio.h>

#define  MAX_THREAD   2
int sum = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
void *thread_routine( void * arg )
{
    int local,i;
    for(i=0; i<100000000/MAX_THREAD; i++ )
    {
        pthread_mutex_lock(&lock);
        local = sum;
        local = local+1;
        sum = local;
        pthread_mutex_unlock(&lock);
    }
    return arg;
}

int main( int argc, char **argv )
{
    pthread_t thread_id[MAX_THREAD];
    void *thread_result;
    int status, i;

    for(i=0; i<MAX_THREAD ; i++ )
        status = pthread_create( &thread_id[i],0,thread_routine,0);

    for(i=0; i<MAX_THREAD ; i++ )
        status = pthread_join( thread_id[i], &thread_result );

    printf("sum=%d\n", sum);
    return 0;  
}

2.2 Semaphores

Semaphore는 Mutex와 다르게 signaling mechanism으로, 만약 shared resource에 접근 가능한 경우 resource를 free하는 process가 signaling 하면서 interrupt를 건다. 그리고 shared resource에 접근 가능한 process의 개수가 2개 이상인 경우에 semaphore를 사용한다. 이 때 반드시 resource 수는 접근 가능한 process 수보다 커야한다.

2.3 Monitors

Monitor는 abstract data type으로 semaphore와 마찬가지로 2개 이상의 shared resource에 대해서 다수의 process의 접근을 제어한다. Monitor는 shared resource와 procedure set을 함께 지원하기 때문에 사용하기 쉽다.

Reference

https://www.geeksforgeeks.org/mutex-vs-semaphore/?ref=lbp
https://www.geeksforgeeks.org/monitor-vs-semaphore/?ref=rp