[Operating System Concepts] Chapter6 Synchronization Tools (Part.2)

갓룡과 짱익스트라 교수님 (https://ko.wikipedia.org/wiki/%EC%97%90%EC%B8%A0%ED%97%88%EB%A5%B4_%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC) 

 

1. Why mutex, semaphore, monitor?
2. Mutex Lock
3. Semaphore
4. Monitor - Example Situations
5. Liveness

---

Why mutex, semaphore, monitor?

 

상호배제 알고리즘과 세마포어 그리고 모니터를 통해 Race Condition를 쉽게 방지할 수 있다.

• Higher level software tools for Critical Section Problem (Mutex Locks) :
  동기화 조건을 만족시키는데 있어서 가장 쉬운 방법중 하나이다. (락킹하고 열쇠를 받고 사용한다음 반납하기)
• Mutex Locks Limitation: 동기화 이슈 (2개의 프로세스 밖에 제어못한다.)
• Semaphore : 제일 보편적인 락킹 (N개를 제어할 수 있다.)
• Monitor : Java에서 사용하는 wait modify 툴이다.
• Liveness : 데드락을 방지하기 위한 progress를 만들기위한 프로세스이다.

 

Mutex Lock (mutual exclusion)

기본적인 race condition을 보호하고 제어한다. (must acquire the lock before entering critical section)

하나의 프로세스(스레드)만이 락킹을 제어할 수 있다.

 

Mutex Basic Structure

  acquire lock // entry code
     do critical section 
  release lock  // exit code
     do remainder section

  acquire()
  {
     while (!available) 
        ; (busy wait)
     available = false;
  } 
  release()
  {
     available = true;
  }

• Peterson Algorithm에서는 번거롭게 flag를 제어했어야 했는데, mutex에서는 권한만 받으면 쉽게 주고받을 수 있다.
• mutex사용하려 할 때 락킹이 현재 점유되고 있다면 현재 스레드를 큐에 넣는다. 이후 락킹이 회수되고 큐에 하나이상의 스레드가 대기중이라면 하나를 깨워서 락킹을 획득하는 방식이다.
• 어떻게 atomic하게 만들것인가 ? → CPU 레벨에서 지원하는 test_and_set 알고리즘을 사용해서 atomic을 보장해준다.
• 결론적으로, mutex도 어떻게 보면 스핀락의 종류이지만 락킹을 가질 수 있을 때 까지 휴식할 수 있기 때문에 자원낭비가 심하지 않다.

#Problem: Busy waiting

• 이렇게 쉽게 구현하면 좋을 것 같지만, 'Busy Waiting(spinlock)' 문제가 생긴다.
  (루프를 무한히 돌리면서 자원을 점유하기에 다른 프로세스가 사용할 수 없다.)
• 그러나, 스핀락이 유용할 때가 있다. → 여러개의 코어를 가지고 있을 때 busy waiting 상태에서 바로 진입할 수 있다
  (context switching time이 줄어든다. / 프로세스 실행시간(임계영역의 시간)이 context switching보다 작으면 spinlock 구현이 mutex락 구현보다 유리하다.)

void *counter(void *param) 
{
	int k;
    
    for(k = 0; k <10000; k++){
    	/* entry section */
        pthread_mutex_lock(&mutex);
        
        /* critical section */
        pthread_mutex_unlock(&mutex);

        /* remainder section */
    }
    pthread_exit(0);
}

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

int sum = 0; // shared variable
pthread_mutex_t mutex;

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

• 열쇠를 획득하고 → critical section → 반납 을 통한 방법으로 Mutex 사용가능
• starvation과 deadlock은 여전히 해결할 순 없지만 상호배제 문제는 충분히 해결가능하다.

 

Semaphore

Semaphore = 신호

• semaphore 은 정수형 변수로 되어있다. → 두개의 원자성을 갖는 동작으로 구현되어 있음(two standard atomic operation) 
  wait() and signal() 또는 P() [Proberen(to test)] V() [Verhogen(to increment)] 으로 나타낼 수 있다.

 

Semaphore Basic Structure

typedef struct
{
  int value ;
  struct process *Q ;
} semaphore ;


void wait(semaphore *S)
{
  S->value--;
  if (S->value < 0)
  {
    add this process to S->Q;
    sleep() ;
  }
}

void signal(semaphore *S)
{
  S->value++;
  if (S->value <= 0)
  {
    remove a process P from S->Q;
    wakeup(P);
  }
}

• mutex와는 다르게 열쇠가 하나가 아니라 여러개를 가지고 있음 → 받은 열쇠를 가지고 반납하고 다시 가져오고를 반복한다.
• semaphore는 task간 순서를 정해줄 때 사용된다. (wait을 통해 열쇠 회수를 대기하고 있다가 signal으로 회수받은 열쇠가 생긴다면 wait을 끝내고 다음 task를 실행시키는 방식으로 구현 가능하다.)
• 같은 프로세스나 같은 세마포어 또는 같은 스레드 내부에서 실행될 필요가 없다.

#Binary and Counting Semaphores

• Binary Semaphore : 0 또는 1 이기 때문에 mutex lock 과 진배없음 그러나, 뮤텍스락과 동일하지 않다. 
  • 뮤텍스 락은 락킹을 가진 자만 락킹을 해제할 수 있지만, 세마포어는 그렇지 않다.(주체가 서로 다를 수 있다.)
  • 뮤텍스는 priority inheritance(우선순위 스케쥴링)속성을 가지지만, 세마포어는 그런 속성이 없다.
    → 의존성을 가지고 있는 우선순위가 낮은 프로세스 스케쥴링의 우선순위를 높여서 임계영역을 빠르게 나가게 하는 방법
• Counting Semaphore : 제한되지 않은 유한된 숫자의 instance 값을 제어할 수 있다.
  • 리소스가 얼마나 유효한지 체크하고 (가용 가능한 키가 있는지) Semaphore 값을 초기화 시켜준다.
  • wait on semaphore : 리소스 감소
    signal on semaphore : 리소스 증가

#Handling Synchronization Problem

• synchronization problem : 초기화를 0으로 하고 signal을 받아야 S1, S2가 작동한다.
• busy waiting에 대한 문제가 생길 수 밖에 없다.
  → 커널레벨에서 waiting queue(sleep)에 보낸 후에 ready queue(wakeup)으로 보내면 된다.

Semaphore w/ sleep, wakeup

void *counter(void *param) 
{
	int k;
    
    for(k = 0; k <10000; k++){
    	/* entry section */
        sem_wait(&sem);
        
        /* critical section */
        sem_post(&sem);

        /* remainder section */
    }
    pthread_exit(0);
}

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

int sum = 0; // shared variable
sem_t sem;

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

• sem_init이 세마포어 구현의 핵심이다. (0으로 대부분 초기화 하고, n개의 자원의 개수를 넣는다.)
• sem_wait → sem_post(signal, modify) 의 과정은 언어에 따라 다르지만 비슷한 일을 한다.
• N개의 자원을 할당했을 때 race condition이 그대로 발생하게 되어 상호배제가 제대로 되지 않는 상황이 발생한다.

 

Monitors

세마포어를 사용하면서 생기는 문제를 보완하기 위해 'monitor' 방법을 사용한다. mutex와 condition variables로 구성되어 있다.

• The difficulty of using semaphores : 타이밍 에러, 프로그래밍 에러가 생김
• 찾기도 어렵고 항상 일어나지도 않는다. → 버그찾기 어렵다
• wait(mutex) signal(mutex)의 순서가 지켜진다면 문제 없겠지만, 그렇지 않다면 오류가 생긴다.

 

#Situation.1 (순서가 뒤바뀔 때)

→ wait하고 signal 해야하는데 signal하고 wait하게되는 경우가 발생했을 때

 

#Situation2 & 3 (signal 과 wait를 착각 혹은, wait를 위치를 까먹을때 (개발자 실수))

→ low level 언어를 사용한다면 오류생길 가능성이 있다. higher level 언어를 쓰게된다면 실수가 적어짐

Schematic view of a Monitor / Monitor with Conditional Variable

• monitor type은 변수(클래스)선언하고 변수 안에있는 동기화 함수를 사용한다.
• 모니터에 define된 자료구조를 사용하는 경우가 entry queue가 형성이 된다.
• condition variable 을 사용하게 된다면, 각각의 변수에 따라 초기화 되고 동기화 되어간다.

#condition variable 주요 동작

• wait: thread가 자기 자신을 condition variable의 waiting queue에 넣고 대기 상태로 전환하는 것
• signal: waiting queue에서 대기중인 스레드 중 하나를 깨운다.
• broadcast: waiting queue에서 대기중인 스레드 전부 깨운다.

#monitor에는 두개의 큐가 존재한다.

• entry queue: 임계영역에 진입을 기다리는 큐를 의미한다.
• waiting queue: 조건이 충족되기를 기다리는 큐가 대기상태로 기다리는 것을 의미한다.

acquire(m); 					//모니터의 락 취득

while (!p) { 					// 조건 확인

	wait(m, cv); 				// 조건 충족을 만족하지 못하면 waiting
    
}

/* Do something */

signal(cv2); or broadcast(cv2); 	// cv2와 cv가 같을 수 있음

release(m);							// 모니터의 락 반환

• acquire : 뮤텍스가 관리하고 있던 entry queue에서 대기하고 있는 스레드를 깨워서 락킹을 취득
• wait(m, cv) :  조건이 충족 안되면 cv(conditional variable)에서 관리하는 waiting queue에 대기시키고 뮤텍스를 반환한다.
• 그리고 실행된 결과에 따라 조건이 만족될 수도 있기 때문에 condition variable을 깨우기 위해 signal 또는 broadcast로 스레드를 깨워준다.

#Java에서의 모니터

• Java에서 모든 객체는 내부적으로 모니터를 가진다.
• 모니터의 mutex 기능은 'synchronized' 키워드로 사용한다.
• Java의 모니터는 condition variable를 하나만 가진다.
  • Java 모니터의 세가지 동작 : wait, notify, notifyAll (= wait, signal, broadcast)
• Java 모니터를 사용할 때 두가지 이상의 conditional variable이 필요하다면 따로 구현이 필요하다.
• Java.util.concurrent에는 동기화 기능이 탑재된 여러 클래스가 있으니 참고하면 됨

Liveness

mutual exclusion만 제공하지 deadlock 또는 starvation을 해결해주지 않는다.

 

#Deadlock

• 두개 이상의 프로세스가 영원히 기다려야 하는 것을 이야기 한다. (waiting process)
• critical section에 진입해야하는 경우가 2개이다. → 만약 꼬이게 된다면? 서로 서로 릴리즈할때 까지 기다려야함
• 영원히 만날수 없는 교착상태에 빠져버리는 경우이다.

#Priority Inversion

• 우선순위가 높은데에도 불구하고 쫓아낼 수 없는 문제점이 있다.
• (H) > (M) > (L) 로 되어있을 때 중간의 우선순위에 밀려서 높은 우선순위가 대기해야한다.
• 높은 우선순위로 만들어버려서 권한을 가지고 있는 낮은 우선순위를 쫓아내버리면된다.