[OS] Synchronization Tools

critical-section problem(CSP)과 그 해결법을 공부했다. Peterson's Solution은 가장 완전한 해결법이지만, 소프트웨어적 접근이기 때문에 결국 기계어에서 발생하는 문제들을 완전히 해결할 수 없었다. 따라서 atomic instruction과 atomic variable와 같은 하드웨어적 지원이 필요했다.

mutex, semaphore, monitor, liveness 이 4가지는 Peterson's Solution과 atomic instruction & variable을 이용하여 만든 CSP를 해결하기 위한 higher-level software tool이다. 

 

[ Mutex Locks ]

• mutex: mutual exclusion, 즉 상호배제를 구현한 것이다.
• 프로세스/스레드는 critical section에 들어가기 전에 'lock'을 획득해야 하며, 나올 때 'lock'을 반납한다. 만약 이미 하나의 프로세스/스레드가 critical section에 있을 경우 'lock' 상태이므로 다른 프로세스/스레드는 진입하지 못한다. 즉 '상호배제'를 구현하여 동기화하였다.
• critical section에 하나의 프로세스/스레드만 들어갈 수 있다.
• boolean 변수 available, acquire(), release()를 이용하며, 이때 acquire()과 release()는 atomically하게 실행되어야 한다.

bool available // indicates if the lock is available of not (can enter of not)

acquire() {    // wait until the thread can enter critical section, and get lock 
	while (!available) ;
	available = false;
}

release() {    // after executing critical section, release lock
	available = true;
}

• Busy Waiting
  acquire()에서 critical section에 들어갈 수 있을 때까지 계속 루프를 돌게 된다. 이는 다른 생산적인 곳에 쓸 수 있는 CPU를 비효율적으로 낭비하는 것이기 때문에 실제 멀티프로그래밍 시스템에서는 문제가 된다.
• Spinlock
  : busy waiting을 이용한 mutex lock을 spinlock이라고 한다. 
  context switching 할 필요가 없다. busy waiting을 안하고 wait queue에서 대기하게 되면, available해졌을 때 ready queue로 이동한 후 context switch를 하는 과정을 거친다. 이 과정에서 dispatch latency 등 시간이 소요된다. 하지만 busy waiting을 하면 계속 CPU를 점유하고 있기 때문에 이런 시간이 소요되지 않는다.
  위와 같은 장점으로 멀티코어 시스템에서는 spinlock이 좋은 선택일 수 있다. 다른 코어에서 busy waiting을 하고 있다가 available해지면 바로 실행할 수 있기 때문이다.
• 상호배제는 충족하지만 데드락과 기아문제는 해결할 수 없다.

ex)

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

#define COUNT_MAX 10000

pthread_mutex_t mutex;

/* shared data */
int sum = 0;

void *counter(void *param) {
	for (int i=0; i<COUNT_MAX; i++) {
		/* entry */
		pthread_mutex_lock(&mutex);

		/* critical */
		sum++;
        
		/* exit */
		pthread_mutex_unlock(&mutex);
	}
	pthread_exit(0);
}

int main() {
	pthread_t tid1, tid2;
	pthread_mutex_init(&mutex, NULL);
	pthread_create(&tid1, NULL, counter, NULL);
	pthread_create(&tid2, NULL, counter, NULL);
	pthread_join(tid1, NULL);
	pthread_join(tid2, NULL);
	printf("sum = %d\n", sum);
}

 

---

[ Semaphores ]

• semaphore: 신호장치, 신호기 (기차역이나 번잡한 교차로에서 정지/이동 신호를 보내는...)
• 여러 개의 프로세스/스레드가 critical section에 진입할 수 있는 locking 매커니즘이다.
• critical section에 들어갈 수 있는 스레드/프로세스 수에 따라 binary semaphore와 counting semaphore로 나뉜다.
  만약 접근할 수 있는 resource가 n개라면 n개의 스레드/프로세스가 동시에 critical section에 들어갈 수 있으며, 이를 counting semaphore라고 한다. 만약 resource가 1개라면 mutex lock과 유사하며, 이를 binary semaphore라고 한다.
• 사용 가능한 lock의 개수를 나타내는 정수 변수 (보통 sync..)와 두 개의 atomic operation wait()과 signal()을 이용한다

int sync = the number of resources available ( > 0 )

wait(sync) {  // wait until the thread can enter critical section and sync decreases
	while (sync<=0) ; // not enough lock, busy waiting
    sync--;
}

signal(sync) { // send signal that means the thread exit the cirtical section and sync increases
	sync++;
}

• rather than busy waiting, the thread suspends itself and goes to the waiting queue
  and when signal() is called the thread is placed into ready queue
• sync는 반드시 사용가능한 자원의 개수여야 한다. 예를 들어 공유 데이터는 정수 변수 하나인데 5개의 스레드가 동시 접근을 하게 되면 상호 배제가 되지 않아 race condition이 발생하게 된다.
• semaphore 역시 데드락과 기아 문제가 발생할 수 있다.

ex) counter

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

#define COUNT_MAX 10000

sem_t sem;

/* shared data */
int sum = 0;

void *counter(void *param) {
	for (int i=0; i<COUNT_MAX; i++) {
		/* entry */
		sem_wait(&sem);

		/* critical */
		sum++;
        
		/* exit */
		sem_post(&sem);
	}
	pthread_exit(0);
}

// binary semaphore
int main() {
	pthread_t tid1, tid2;
	sem_init(&sem, 0, 1);
	pthread_create(&tid1, NULL, counter, NULL);
	pthread_create(&tid2, NULL, counter, NULL);
	pthread_join(tid1, NULL);
	pthread_join(tid2, NULL);
	printf("sum = %d\n", sum);
}