운영체제 : Synchronization

Background

---

동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황 이라고 한다.

→ 실행 순서를 결정하는 것은 OS의 스케줄링

임계영역(Critical Section) 문제

---

• 코드 상에서 경쟁 조건이 발생할 수 있는 특정 부분을 임계영역이라고 한다.

이 코드는 전역 변수 counter에 1을 더하는 과정이다. 우선 메모리에 있는 전역 변수를 가지고 와서 레지스터에 넣는다. 레지스터 값을 1 증가시키고 증가시킨 값을 다시 메모리에 로드한다. (메모리에 있는 값을 바로 증가하는 것이 아님!)

스레드1이 전역변수의 값을 레지스터로 옮기고 값을 1 증가시킨 순간 interrupt가 수행되고 제어 흐름이 스레드 2로 전환되었다.

따라서 전역변수 counter에 저장된 값은 여전히 50이고 스레드2의 레지스터에는 50이라는 값이 로드되어 1 증가하는 연산을 수행하게 된다. 그런 후에 counter에 51이라는 값을 로드한다.

다시 인터럽트가 발생하여 스레드1이 작업을 하게 되는데, 이때 레지스터에 저장되어있던 51이 다시 전역변수 counter에 덮어쓰게 된다.

따라서 counter에 1이 증가된 것처럼 보이게 된다

atomic operation 이 아니기 때문에 문제가 발생!

해결 방법 : 공유 자원에 접근할 때 경쟁조건이 유발되는 코드부분을 수행할 때에는 interrupt를 방지한다.

• thread_lock 함수를 사용!

임계 영역이 발생하는 이유

• 경쟁 조건
• 실행마다 바뀌는 스케줄링

임계영역 문제를 해결하기 위해서는 3가지 요구조건이 만족되어야 한다.

1. Do all or nothing (atomicity)
2. 임계영역 (critical section)
3. 상호 배제 (Mutual Exclusion) - 한 스레드만 임계영역에 들어갈 수 있다.

→ thread lock이나 세마포를 이용하여 해결할 수 있다.

임계영역 문제를 해결하기 위해서

1. 상호 배제
2. Progress - 어느정도 기다리면 반드시 내 차례가 되어야 함
3. Bounded Waiting - 기아상태에 빠지면 안된다

• 임계영역에 들어갈 때 인터럽트를 방지하는 것은 비효율적임
  • 임계영역이 너무 길면 너무 오래걸린다. → 기아 상태 유발
  • 다른 코어도 인터럽트 금지 시켜야 해서 효율이 ㄷ떨어진다.

동기화를 위한 하드웨어

• Test-and-Set
  • true → true, false→false값 반환 target=true
  1. lock = false면 false를 리턴하여 임계영역에 진입한다. lock = true
  2. 두번째 스레드 진입 시 lock = true이므로 무한 루프 타다가 time out
  3. 첫 스레드 임계영역 벗어나면 lock = False로 바뀐다.

문제점 : while() 락을 확인하면서 unlock이 될 때 까지 busy waiting → CPU 자원 낭비

• Compare-and-Swap

Mutex Locks

---

임계영역을 해결하기 위한 해결책.

프로세스는 임계영역에 들어가기 전에 반드시 lock을 획득해야 하고, 임계영역을 빠져나올 때 lock을 반환해야 한다.

1. acquire() : 락 획득함수
2. release() : 락 반환 함수
3. available : 락 가용 여부를 표시하는 함수

acquire 과 release는 원자성을 가진다.

→ 이 솔루션은 busy waiting을 요구한다.

해결방법 : sleep 시키면 된다!!! → semaphore

Semaphores

---

세마포 S는 정수 변수로서 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait() (P())와 signal() (V()) 로만 접근할 수 있다. 

S의 초계치는 양수 1이어야 한다. S가 양수면 임계영역에 접근이 가능하다는 의미이다.

 

wait(S) {

while (S <= 0) ;

// busy wait

S--;

}

 

signal(S) {

S++;

}

1. counting semaphore : 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있다.
2. binary semaphore 0,1

→ 세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타낸다.

 

• 임계영역의 구간이 짧으면 busy waiting 방식을 사용해도 된다.
• 임계영역 구간이 길면.. busy waiting 하지 않도록 한다.
  • queue 도입
  • block과 wakeup - 세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal연산을 실행하면 재시작되어야한다.

typedef struct {int value;

    struct process *list;}semaphore;

wait() 연산의 정의는 다음과 같다.

wait(semaphore *S) {

    S->value--;

    if (S->value < 0) {

        add this process to S -> list;

        sleep();

    }

}

signal() 연산의 정의는 다음과 같다.

 

signal(semaphore *S) {

    S->value ++;

    if (S->value <= 0) {

        remove a process P from S -> list;

        wakeup(P);    

    }

}

Liveness

---

두 프로세스가 리소스를 점유하고 놓아주지 않거나 어떠한 프로세스도 리소스를 점유하지 못하는 상태가 되어 프로그램이 멈추는 현상을 Deadlock(교착상태)이라고 한다.