728x90
Background

Background

  • Data consistency
    • 멀티프로세싱/스레딩 시에 다수 작업이 동시에 시행
    • 인터럽트 발생 시 이전에 동작하던 작업이 일시 중단되고 새로 실행
    • 여러 작업이 데이터를 공유할 경우 문제 발생
      • 데이터 업데이트 중 다른 프로세스가 읽어들이거나
      • 여러 프로세스가 동시에 쓰는 경우
    • 일정 루틴에 맞는 프로세스 실행 순서를 정의할 필요가 존재
  • Producer - Consumer Problem
    • 데이터 생산 프로세스(Producer)는 큐가 차있지 않은 동안 데이터를 입력
    • 데이터를 쓰는 프로세스(Consumer)는 큐가 비어있지 않으면 데이터 사용
    • Counter 변수를 같이 접근하는 문제 존재
      • ++, --명령어 실행 시 변수값을 각 레지스터로 이동하여 처리
    • race condition : 초기값이 5일 때, 동시에 접근 시 Producer는 5 > 6, Consumer는 5 > 4로 Counter 값을 바꾸므로 결과적으로 카운터값이 6>4로 변경될 가능성 존재
    • fork()의 race condition
      • fork 실행 시 반환값은 PID
      • 두 프로세스가 동시에 fork 호출 시 같은 PID를 갖는 두 프로세스가 생성될 수 있음
/*  Producer Process  */
while (true) {
/* produce an item in next produced */
while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}

/*  Consumer Process  */
while (true) {
while (counter == 0)
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
/* consume the item in next consumed */
}

Critical-Section Problem

  • 다수의 프로세스/스레드 생성 시 한 번에 하나의 작업만 실행될 수 있는 구간
    • 공용 데이터 접근시의 충돌 방지
do
{
    /* Ask Permission to enter critical section */
        /*  Critical Section */
    /* Exit Critical Section */
    ...
}while(...);
  • Critical Section 문제의 해결 조건
    • Mutual Exclusion : 프로세스 P가 Critical Section에 접근 시 다른 프로세스는 해당 구간을 실행하면 안됨(Critical Section의 정의)
    • Progress : Critical Section에 실행 중인 프로세스가 없을 경우, 이 구간에 진입하고자 하는 프로세스를 지연 없이 진입시켜야 함
    • Bounded Waiting : 프로세스 A가 Critical Section에 있을 때, 새 프로세스가 진입하고자 할 경우 A가 끝나는 것을 대기해야 하나, 무한정 대기해서는 안됨 (Critical Section 진입 시 우선순위의 조정 필요)
  • OS의 Critical-Section Handling : Non-Preemptive
    • 인터럽트 없이 커널 설계
    • 구현이 쉽고, 오류를 신경쓸 필요성이 낮아짐
    • 공유 데이터 접근 시 우선한 작업이 처리되어야 나머지 처리가 가능하므로 시스템 반응성, 성능이 떨어지게 됨

Peterson's Solution

  • SW 기반으로 HW 영역의 문제를 해결하고자 하는 접근법
  • 2개 프로세스/스레드를 가정
    • load/store 명령어는 순서대로 실행된다고 가정(각 명령어 중에는 인터럽트가 없음)
    • 두 프로세스에는 변수가 존재 : int turn ; bool flag[2]
    • turn : critical section에 접근 가능한 프로세스
    • flag[i]가 true면 i번째 process가 Critical section에 접근하고자 함
  • Entry Section
    • 자신의 flag를 true로 만듦 : critical section에 접근할 준비
    • turn을 상대 프로세스 값으로 대입
    • while : 상대 프로세스가 준비가 되었고(flag), 실행할 순서인 경우(turn), 완료할 때까지 무한루프로 대기
      • 그렇지 않은 경우 자신의 코드 실행
    • critical section 실행 후 자신의 flag를 false로 설정
  • 위 예시의 검증
    • Mutual Section : while문 조건에서 turn이 상대방 값으로 대입되므로 critical section에 동시 접근이 불가
    • Progress : Entry section에 진입하지 않은 경우 해당 프로세스의 flag는 false이므로 다른 프로세스는 바로 critical section에 접근 가능
    • Bounded Waiting : turn이 상대 값으로 대입되었기 때문에 프로세스가 while문 재진입 시 다른 프로세스에 우선권을 넘겨주므로 무한 대기 없이 두 프로세스가 순차 실행
  • Peterson's Soultion의 문제 : 현대 컴퓨터에서 실행을 보증하지 않음
    • 프로세서나 컴파일러가 성능을 위해 독립적으로 실행되는 명령어 순서를 변경할 수 있음
    • 독립적인(서로 다른 곳에 접근하는) 명령어의 경우 순서를 바꾸어도 결과는 동일
    • 멀티코어 / 멀티프로세서 구조에서 심각한 문제가 될 수 있음
      • 원래의 알고리즘
        • (Process i) flag i = true, turn = j
        • (Process j) flag j = true, turn = i
        • (Process j가 먼저 접근한 경우) j는 critical section 처리, i는 while 대기
        • flag j = false : Process i가 critical section 처리
      • 현대 아키텍처의 경우
        • (Process i) turn = j : flag를 나중에 대입
        • (Process j) turn = i, flag j = true
        • turn i=false이므로 Process j가 Critical section 처리
        • (Process i) flag i = true
        • turn이 i이므로 Process i도 Critical Section에 접근 가능 : Mutual Section 위반

HW Support for Synchronization

  • Critical Section Code를 위한 별도 명령어 제공
    • Memory Barrier
    • HW Instruction
    • Atomic Variable
  • Memory Barrier
    • 명령어의 실행 순서를 명시
    • Strongly Ordered : 각 프로세서가 구현 명령어대로 접근
    • Weakly Ordered : 명령어 접근 순서가 바뀔 수 있음
    • Memory barrier : 배리어 전후로는 명령어 순서 변경이 불가
  • HW Instruction
    • Test-and-Set

      boolean test_and_set (boolean *target) {
      boolean rv = *target;
      *target = true;
      return rv:
      }

      • 다른 명령어와 독립적으로 실행(execute atomically)
      • target값을 읽어들인 후, target에 새 값 대입
      • 읽어들인 값 rv 반환
    • Compare-and-Swap

      int compare_and_swap(int *value, int expected, int new_value) {
      int temp = *value;
      if (*value == expected)
      *value = new_value;
      return temp;
      }

      • 이전값(value)가 예측값(expected)와 동일하면 새 값(new_value)로 치환
// criticals section with test_and_set
do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
  • test_and_set이 처음에는 false
    • 먼저 접근한 프로세스가 lock을 true로 바꿈
    • 나머지 프로세스들은 test_and_set이 true를 반환하게 되므로 mutual section이 성립
//critical section with comp_and_swap
while (true){
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
  • 초기값 lock이 0이면 해당 프로세스는 Critical section 진입하면서 lock을 1로 바꿈
    • 나머지 프로세스는 lock이 1이므로 while 대기
    • 이때 value와 expect가 다르므로(1, 0) swap이 되지 않게 됨
while (true) {
    waiting[i] = true;
    key = 1;
    while (waiting[i] && key == 1)
        key = compare_and_swap(&lock,0,1);
    waiting[i] = false;
    /* critical section */
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == i)
        lock = 0;
    else
        waiting[j] = false;
/* remainder section */
}
  • Bounded waiting and Mutual section
    • i번째 프로세스가 실행된 경우
    • i+1부터 순회하면서 대기중인 프로세스 탐색
    • 대기중인 프로세스가 있을 경우 해당 프로세스의 waiting 상태를 풀어줌
    • 특정 프로세스가 계속해서 점유하는 것을 방지
  • Atomic Variable
    • 변수 하나만을 보호해야 할 경우
    • 동시 접근 시 데이터의 일관성 보장

Mutex Locks

  • acquire/release 명령어로 atomic variable 선언
    • busy wait : Critical Section에 접근하지 못한 나머지 변수들은 while loop를 돌면서 대기
    • spin lock : 무한루프를 돌면서 대기하는 형태(busy wait)

Semaphores

  • Mutex Lock의 경우 한 번에 하나의 프로세스만 Critical Section 진입
  • Semaphore의 경우 정수 변수 S 값의 설정에 따라 진입 가능한 프로세스 수 설정 가능
    • wait(S) : 대기 중인 프로세스 조정
    • signal(S) : 실행이 완료된 프로세스 release
  • 자원 관리에 주로 사용
  • Busy wait이 없는 Semaphore
    • 프로세스 sleep(), wakeup() 확인
    • wait : 프로세스 실행이 불가능한 경우 프로세스를 sleep queue에 추가 후 sleep
    • signal : 프로세스가 추가 실행이 불가능하면서 waiting중인 프로세스 존재 시 해당 프로세스 wakeup
    • 프로세스 리스트 접근 시 mutex section 구현 필요
wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
    //add this process to S->list;
    block();
    }
}
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
    //remove a process P from S->list;
    wakeup(P);
    }
}

Monitor

  • mutex/semaphor의 고레벨 구현
  • monitor 내에 선언한 함수는 컴파일 단계에서 wait-signal이 구현됨
  • condition variable
    • 변수에 여러 프로세스가 동시 접근 시 signal - wait 구현

Liveness

  • Progress, Bounded Waiting으로 보장
  • 프로세스가 일정 시간 내에 실행되는 것을 보장
    • 보장되지 않을 경우 알 수 없는 이유로 시스템이 멈추는 등의 문제 발생
  • Deadlock
    • 둘 이상의 프로세스가 서로의 자원을 필요로 하는 상황
    • 서로의 wait을 위해 서로의 자원을 필요로 하는 상황
      • P0의 Q wait을 위해서는 P1이 대기하는 Q가 필요
      • P1의 S wait을 위해서는 P0이 대기하는 S가 필요
  • Starvation
    • 프로세스가 공유 자원(Critical Section, Semaphore, ...)을 무한히 대기하는 현상
    • 선점한 프로세스가 무한히 자원을 점유하기 때문에 발생
  • Priority Inversion
    • P1>P2>P3의 우선순위를 갖는 프로세스(P1이 가장 우선)을 가정
    • P1, P3이 공유 자원 R1을 사용하는 상황
    • P3이 사용하는 자원을 release해야 P1을 실행 가능
    • 이때 P2가 실행되면 P2>P3이므로 P2가 우선 실행
    • P1은 R1 자원을 대기중이므로 실행되지 못함
    • 이로 인해 P2가 P1보다 우선 실행되는 우선순위 역전 현상이 발생
    • 해결책 : Priority Inheritance(우선순위 상속) - P3의 우선순위를 P1 수준으로 높여줌

Bounded-Buffer Problem

  • n개의 버퍼마다 데이터 존재
    • 버퍼에는 full, empty, mutex 변수를 갖고 있음
    • full : 버퍼 내 데이터 수
    • empty : 버퍼 내의 공백 수 (full + empty = 버퍼 크기)
    • mutex : 프로세스의 권한 할당 여부 (1 - producer / 0 - consumer)
  • Producer
    • 버퍼가 비었는지 확인(wait(empty))
    • lock acquire - release acquire(wait, signal(mutex))
    • notify consumer(signal(full))
  • Consumer
    • 버퍼가 찼는지 확인(wait(full))
    • lock acquire - relase acquire(wait, signal(mutex))
    • notify producer(signal(empty))

Readers-Writers Preoblem

  • readers : 데이터를 읽기만 하는 프로세스
  • writers : 데이터의 입/출력을 모두 하는 프로세스
  • readers의 경우 동시에 데이터 읽기가 가능하게 설정
    • rw_mutex semaphore를 설정
728x90
저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바