[운영체제] 동기화

전공 수업 내용 정리 (문제 발생시 비공개합니다.)

---

프로세스 동기화(Process Synchronization)

여러 프로세스가 공유하는 자원의 일관성을 유지하는 것

여러 프로세스가 서로 협력해 공유자원을 사용하는 상황에서 경쟁조건(race condition)이 발생하면 공유자원의 신뢰성이 떨어진다. 이를 방지하기 위해 프로세스들이 공유자원을 사용할 때 특별한 규칙을 만드는 것

경쟁 상황(race condition)

• 여러 프로세스(또는 스레드)가 공유자원에 동시에 접근할 때 공유자원에 대한 접근 순서에 따라 실행 결과가 달라질 수 있는 상황
• 동시에 접근할 때 자료의 일관성을 해치는 결과가 나올 수 있다.

임계구역(critical section)

여러 프로세스 또는 스레드가 자원을 공유하는 상황에서 하나의 프로세스만 접근할 수 있도록 제한해둔 영역 -> race condition을 막을 수 있는 해결책이 될 수 있다.

한 프로세스가 자신의 임계 구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계 구역에 들어갈 수 없다. 즉 동시에 두 프로세스는 그들의 임계 구역 안에서 실행할 수 없다.

CSP(Critical Section Problem)

• enter section(entry section) : 각 프로세스가 임계구역(critical section)에 들어가기 위해 진입허가 요청을 하는 코드가 있는 부분
• critical section : 한 프로세스가 자신의 임계구역에서 작업을 수행하는 동안에는 다른 프로세스는 그들의 임계구역에 접근할수 없다
• exit section : 임계구역을 빠져나오는 코드가 있는 부분
• remainder section : 나머지 구역

CSP 문제 해결 조건

1. 상호 배제(mutual exclusion): 한 프로세스가 임계 구역에 들어가면 다른 프로세스는 임계 구역에 들어갈 수 없다.
2. progress(deadlock 회피): 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.
3. 한정 대기(bounded waiting): 어떤 프로세스도 무한정으로 대기하지 않아야 한다.
4. 임계구역 진입횟수에 한계를 두어 같은 프로세스가 계속해서 독점해서 사용하지 못하게 한다. -> 다른 프로세스들이 기아상태에 빠지지 않게 한다

peterson 솔루션

• CSP를 소프트웨어 기반으로 해결. 두 프로세스가 두개의 데이터 항목을 공유하며 해결.
  • int turn : 임계구역으로 진입할 프로세스의 순번(turn = i이면 프로세스 Pi가 임계구역에서 실행)
  • bool flag[2] : 특정 프로세스가 임계구역으로 들어갈 준비가 되었다는 것을 나타냄 (flag[i] = true면 프로세스 Pi가 임계구역으로 들어갈 준비가 되었다는 것)

mutex lock

• mutex의 원리
  • 임계구역을 보호하고, 경쟁조건을 방지하기 위해 mutext lock사용
  • 프로세스는 임계구역에 들어가기전에 lock을 획득하고 나올때는 lock을 반환해야한다(화장실 열쇠)
  • lock을 사용할 수 있다면 acquire()을 호출해 lock을 획득하고, 다른 프로세스가 접근하지 못하게 lock은 사용할 수 없게 된다
  • lock을 반환할때는 release()를 호출
• spinlock이란?
  • lock을 얻기 위해 이를 얻으려 acquire을 수행하는 과정에서 lock이 가용되어지기를 기다리며 프로세스가 계속 반복 회전하므로 이를 spinlock이라고 부른다.
  • context switching을 하지 않고 잠시 루프를 돌며 재시도하는것
  • 장점: 프로세스가 락을 기다려야 하고 문맥 교환에 상당한 시간이 소요될 때 문맥 교환이 필요하지 않다
  • 단점: busy-waiting
  • 임계구역에 들어가기 전 lock을 얻기 위해 acquire()에서 무한루프에 빠진다. → CPU 주기 낭비

semaphore

• Semaphore S
  정수 변수, 현재 이용가능한 자원단위의 개수
• 표준 연산
  • semWait operation decrements the value
  • semSignal operation increments the value
• semaphore의 원리
  • mutex가 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 하나의 Process 혹은 Thread가 접근하는 것을 막아주는 것이라면 semaphore는 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌 즉, 동기화 대상이 하나 이상
  • 리소스의 상태를 나타내는 간단한 카운터. 카운팅 세마포어와 이진 세마포어로 나뉠수 있으며 이진 세마포어는 이진수(0 또는 1)를 사용한다. 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 해야한다.
  • mutex는 상태가 0, 1 두개 뿐인 binary semaphore
  • 세마포어(S)는 프로세스가 임계구역에 들어가려할때 wait()를 호출해 값이 감소하고 임계구역 작업을 끝내고 lock을 반납할 때 signal()을 호출해 값이 증가한다.
  • 세마포어가 0이 되면 모든 자원이 프로세스들에 의해 모두 사용중이라는 것을 의미 -> busy waiting

생산자/소비자 문제 해결 예시
초기값: fill - 0, empty = max, m = 1

/* program producerconsumer */
semaphore n - 0, s = 1;
void producer() {
    while (true) {
        produce();
        semWait(s);
        append();
        semSignal(s);
        semSignal(n);
    }
}
void consumer() {
    while (true) {
        semWait(n);
        semWait(s);
        take();
        semSignal(s);
        consume();
    }
}
void main() {
    parbegin(producer, consumer);
}

/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */
semaphore n - 0, s = 1, e = sizeofbuffer;
void producer() {
    while (true) {
        produce();
        semWait(e); // 추가
        semWait(s);
        append();
        semSignal(s);
        semSignal(n);
    }
}
void consumer() {
    while (true) {
        semWait(n);
        semWait(s);
        take();
        semSignal(s);
        semSignal(e); //추가
        consume();
    }
}
void main() {
    parbegin(producer, consumer);
}

주의사항

데드락 (Deadlock)

• 두 개 이상의 프로세스가 서로 대기하며 진행하지 못하는 상태
• 세마포어 구현 시 발생 가능

리눅스의 Two-Phase 락

1. 첫 단계: 스핀락으로 대기
2. 두 번계: 슬립 상태로 전환

• 락 획득 시간이 짧을 것으로 예상될 때 효율적

---