[OS] 동기화 문제와 세마포어

프로세스 동기화??

컴퓨터 시스템에서는 데이터를 가지고 연산할때, 데이터가 저장된 곳에서 불러오고 그걸 연산하는 구조를 띄고있음,
예를들면, CPU가 메모리에서 데이터를 읽어 연산, 저장을 한다던가, 프로세스가 각자의 주소공간에서 데이터를 읽어 값을 변경, 저장 한다던가의 형식
여기서 CPU가 여러 프로세스를 멀티 테스킹할때 등의 상황에서 동기화 문제가 발생할 수 있음

Process Synchronization(동기화) 문제

• 공유 데이터의 동시 접근은 데이터의 불일치 문제를 야기할 수 있음

• 데이터의 일관성을 유지하기 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요하게됨

• Race condition

  • 여러 프로세스, 프로세서가 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스나 프로세서에 의해 달라지게됨
  • race condition을 막기위해서는 concurrent process 동기화 되어야함

Race Condition

• Race Condition : 대표적인 동기화문제로, 여러 프로세스가 같은 데이터를 활용하려 할때, 의도치않은 결과가 나오는것

• OS에서의 race condition

  1. 커널에서 인터럽트가 발생할때
  2. 프로세스가 시스템콜을해서 커널 모드로 수행 중인데, 문맥 교환이 일어나서 다른 프로세스가 선점하는 경우
  3. 멀티프로세서에서 공유 메모리내의 커널 데이터값을 각 cpu가 동시에 건드리려할때

• 1번의 경우

커널 모드에서 실행 중에 인터럽트가 발생해서 인터럽트 처리루틴이 수행되는 경우를 그림으로 나타낸것.
양쪽 다 커널 코드이므로, 커널 주소 공간을 공유하게됨, 위 예에서는 count값을 로드하고 난 후 인터럽트가 발생해서 count값을 1빼는 코드가 적용이 안되고
1증가하는 커널의 2번 부분만 적용됨. 해결책으로는 주소 공간의 값을 가져와서 처리하는 코드에 진입할 경우 인터럽트를 disable시키고 종료 되면 enable시켜서
중간에 인터럽트 핸들러가 실행되지 않게 하면됨

• 2번의 경우

A가 커널모드에서 실행 중일떄, 문맥 교환이 일어나서 B가 실행되는 상태를 나타낸 그림
A와 B 모두 count값을 1씩 증가시키는데, B의 경우는 반영이 안돼서 1만 증가됨
해결책으로는 커널 모드에서 수행 중일떄는 다른 프로세스가 CPU를 선점하지 않도록 하면됨, 즉 사용자 모드에서만 문맥 교환이 일어나도록

• 3번의 경우

CPU 여러개가 count값을 변경하는 경우, 어떤 CPU가 마지막으로 count값을 store했는지에 따라 값이 달라짐
해결책으로는 한 CPU가 count값을 접근할떄 락을 걸어서 다른 cpu가 접근을 못하게 막은 다음 count값 store작업이 끝난 후 락을 푸는 방법

Critical Section

• Critical Section 문제

  • n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
  • 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드의 critical section이 존재함
  • 하나의 프로세스가 critical section에 있을 때, 다른 프로세스는 critical section에 들어가지 못하게해야함

• 해결의 충족 조건

  • Mutual Exclusion(상호 배제) : 프로세스 A가 critical section 부분을 수행 중이면 다른 모든 프로세스는 자신의 critical section에 들어가면 안됨
  • Progress : 아무도 critical section에 있지 않은 상태에서 어떤 프로세스가 critical section에 들어가고자 한다면 들어가게 해줘야됨
  • Bounded Waiting : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될때 까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야됨

• Peterson's 알고리즘

  Process i
  do{
      flag[i] = true; //i가 크리티컬섹션에 들어간다는 flag를 true로 변경
      turn = j; // 턴을 프로세스 j에게 넘김
      while(flag[j] && turn==j); // 프로세스 j의 차례이고 j가 크리티컬 섹션에 있을때 while문 돌면서 기다림
      critical section part 
      flag[i] = false; // 크리티컬섹션 종료 후 flag를 false로 바꿔서 상대방이 크리티컬섹션에 들어가도록 해줌
      remainder section
     }while(1);

  중간에 아무 지점에서나 CPU를 선점당해도 위의 충족 조건들을 만족하면서, 정상적으로 동작함
  하지만 Busy Waiting(=spin lock)문제가 발생함 계속 CPU와 메모리를 쓰면서 기다림(while문 부분)
  (반대로, 멀티프로세서에서는 스핀락이 선호되는 경우가 있음, 스핀락중에 락이 풀리면 바로 크리티컬섹션으로 돌입이 가능하기때문에 문맥교환 비용을 아낄 수 있음)
  

• 하드웨어적으로 Test & set를 atomic하게 수행할 수 있도록 지원하는 경우 Busy Waiting문제가 해결됨

process i
do {
    while(Test_set(lock));
    critical section
    lock = false;
    remainder section
    }while(1);

lock이 0이면 test_set이 0을 반환해서 while문 탈출, 1이면 test_set이 1을 반환해서 wait상태

Semaphores(세마포어)

• 앞의 알고리즘을 추상화 시킨것
• Semaphore S
  • int타입 정수값(자원의 변수값)
  • 아래 두가지 atomic 연산에 의해서만 접근이 가능함
    
  • P연산은 세마포어 변수값을 흭득하는과정(=락을 거는 과정)
  • V연산은 다 사용하고 반납하는 과정(=락을 푸는 과정)
• Counting semaphore
  • 도메인이 0 이상인 임의의 정수값(여러개의 자원이 있음)
  • 주로 resource counting에 사용
• Binary semaphore(=mutex)
  • 0 또는 1 값만 가질 수 있는 세마포어
  • 주로 mutual exclusuon(lock/unlock)에 사용됨

Block / Wake up 방식의 세마포어 구현

세마포어를 사용해도 결국은 하드웨어의 도움이 없으면 스핀락이 생김 이 스핀락을 해결하기 위한 구현방식
아이디어는 프로세스가 IO작업 중에 블락 상태가 되고, IO작업이 끝나면 ready큐에 들어가는 것 처럼 다른 스레드나 프로세스가 공유 데이터를 사용하고 있으면, 블락상태가 되면서 스핀락이 되지 않고 공유 데이터의 락이 풀리면 그때 Wake up하여 CPU를 점유하는것

• 구현 방식

• 세마포어를 다음과같이 정의

  typedef struct
  {
    int value; //세마포어
    struct process *L; // wait 큐 프로세스
  }semaphore;

• block과 wake up 상태를 다음과 같이 가정
  • Block : 커널은 block을 호출한 프로세스를 suspend시킴, 이 프로세스의 PCB를 세마포어에 대한 wait queue에 넣음
  • wake up(p) : block된 프로세스 p를 wake up시킴 이 프로세스의 pcb를 ready queue에 넣음
• 세마포어의 연산 구현
  • P연산

    P(S): 
    S.value--; // 자원 흭득
    if(S.value < 0) //만약 세마포어의 값이 음수이면 이미 다른 프로세스가 자원을 다가져간 상황 즉 여분의 자원이없음
    {
       block() //여분의 자원이없으므로 block상태
    }

  • V연산

    V(S):
    S.value++; //자원 반납
    if(S.value <= 0) //자원이 0이하라면, 이 자원을 가지고 block된 프로세스나 스레드가 있음을 의미함
    {
       wakeup(P); //이 자원을 기다리며 block상태인 프로세스를 wakeup해줌
    }

세마포어 구현방식의 장단점

• Busy wait VS Block/Wakeup
• Block/wake up의 오버헤드 vs 크리티컬섹션의 길이
  • 크리티컬섹션의 길이가 길면, block/wakeup이 효율적일 수 있음
  • 크리티컬섹션의 길이 짧으면, block/wakeup의 오버헤드가 busy-wait의 오버헤드보다 커질 수 있음
  • 일반적으로 block/wakeup방식이 더 좋음

Reference
주니온 교수님 유튜브 채널
반효경 교수님 KOCW 운영체제
운영체제 아주 쉬운 세 가지 이야기(OSTEP 번역서)