[운영체제] Chapter 6. Process Synchronization (2)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

Semaphores, Critical Section of n Processes, Block/Wakeup Implementation, Two types of Semaphores, Deadlock and Starvation

 

1. Semaphores, 세마포어

• 앞의 방식들을 추상화 시킴
• Semaphore S
  • 추상 자료형: object와 operation으로 구성
  • integer variable: 자원의 개수를 의미, 정수 값을 가질 수 있다.
  • 두 가지(P, V) atomic 연산에 의해서만 접근 가능하다.
    • 변수 S에 대한 P연산: 세마포어 값(= 공유 데이터 값) 획득

    P(S): 
    while (S<=0) do no-op;    //자원이 없는 상태에서는 기다림
    S--;    //누군가가 자원을 내어 놓으면 S--로 자원을 획득	
    

    • 변수 S에 대한 V연산: 반납

    V(S):
    S++;    //반납
    

• P연산과 V연산 시 세마포어의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다. 즉, 한스레드가 세마포어 값을 변경하면, 다른 어떤 스레드도 동시에 동일한 세마포어 값을 변경할 수 없다.
• P연산에서도 busy-wait(바쁜 대기)은 발생한다: 자원이 없을 때 할당 시간 동안 while문만 반복해서 프로세스가 생산적으로 사용할 수 있는 CPU 주기를 낭비한다.
• (사실은, P연산과 V연산 자체의 구현은이 원자적으로 수행이 되려면 synchronization hardware를 사용해서 구현해야 될 것이다.)

 

2. Critical Section of n Process:

semaphore mutex = 1;    
//Synchronization variable, 1개가 임계 영역에 들어갈 수 있다.

//Process Pi
do{
	P(mutex);    //lock, postive값이면 세마포어값을 1 감소 하고 진입
	critical section
	V(mutex);    //unlock, 세마포어 값 1 증가
}

• mutex(mutual exclusion) 락: critical section을 보호하고 race condition을 방지하기 위해 사용한다.
  • 프로세스는 critical section에 들어가기 전에 반드시 락을 획득해야 하고 임계구역을 빠져나올 때 락을 반환해야 한다.
  • spinlock라고 한다. 락을 사용할 수 있을 때까지 프로세스가 "회전"하기 때문: busy-wait
• critical section 문제는 자연스럽게 해결할 수 있다.
  • 추상적이기 때문에 프로그래머는 세마포어가 지원되면 P연산과 V연산만 사용하면 되고
  • P연산과 V연산의 구현은 시스템의 몫이다.
• 그렇지만 busy-wait은 효율적이지 못하다. (= spin lock)
  • Block & Wake Up 방식의 구현으로 해결할 수 있다. (= sleep lock)

 

3. Block & Wake Up

• 공유 데이터를 누가 사용하고 있으면 내어 놓기 전까지는 내 차례가 오지 않는다.
  • 그렇다면 while문을 돌 필요 없이
  • 그 프로세스 자체를 blocked 시켜서 CPU를 반납하고 잠들어 있다가
    • 공유 데이터를 반납하면 그때 깨어나서 준비 큐에서 CPU를 얻으면 공유 데이터를 얻을 수 있다.
• 세마포어 정의

  typedef struct{
  	int value;          //세마포어 변수 값
  	struct process *L;  //세마포어 때문에 잠들어 있는 변수들을 연결하기 위한 큐
  } semaphore;

• block: 세마포어를 획득하지 못한 상태
  • 커널은 block을 호출한 프로세스를 일시 중지시키고
  • 이 프로세스의 PCB를 세마포어에 대한 wait queue에 넣어 프로세스의 상태를 대기 상태로 전환
• wakeup(P): 누군가에게 세마포어를 반납하게 되면 block 된 프로세스 중 하나를 깨움
  • block 된 프로세스 P를 wakeup 시켜 프로세스의 상태를 대기상태에서 준비 완료 상태로 변경하고
  • 이 프로세스의 PCB를 ready queue로 옮김
• 세마포어 연산
  • 변수 S에 대한 P연산 - 자원 획득

    P(S):
    S.value--;    //자원의 여유가 있다면 바로 획득
    if(S.value < 0){    //자원의 여유가 없을 때
    	add this process to S.L;    //구조체 변수 S의 리스트에 추가
    	block();    
    }

    • 자원의 여유가 없을 때에도 S.value 감소
    • 세마포어의 값이 음수일 때, 그 절댓값은 세마포어를 대기하고 있는 프로세스들의 수
  • 변수 S에 대한 V연산 - 자원 반납 & 자원을 기다리면서 잠들어 있는 프로세스가 있다면 깨워주는 작업 포함

    V(S):
    S.value++;    //자원을 반납하고
    if(S.value <= 0){    //자원이 반납 되었는대도 값이 0이하 = 누군가 기다리며 잠들었다.
    	remove a process P from S.L;
    	wakeup(P);
    }

    • 자원을 반납했는대도 불구하고 S.value값이 0 이하는 누군가 자원을 기다리며 잠들었다는 뜻이다.

 

4. Busy-wait VS Block/wakeup

• 세마포어 S 변수의 의미
  • Busy-wait: 자원의 개수
  • block & wakeup: 누군가를 깨워야 할 것이 있는지 없는지를 확인해야 하는 상황
    • S가 양수면 자원에 대한 여유가 있다.
    • S가 음수면 누군가 자원을 기다리고 있다. 그 절댓값은 세마포어를 대기하고 있는 프로세스들의 수
• 일반적으로는 의미 있게 이용하는 CPU 이용률 측면(문맥 교환 오버헤드)을 고려할 때는 Blcok/wakeup 방식이 효율적이다.
• Critical section의 길이가 긴 경우 → Block/wakeup이 적당
• Critical section의 길이가 매우 짧은 경우 → Block/wakeup의 오버헤드 > busy-wait의 오버헤드
  • Critical section에 대한 경쟁이 치열하지 않은 경우 = 길이가 매우 짧은 경우 - (busy-wait)
  • Critical section에 대한 경쟁이 치열한 경우 = 길이가 긴 경우 - (block/wakeup)

 

5. 두 가지 종류의 세마포어

• Counting semaphore: 자원의 개수가 여러 개 있을 때
  • 도메인이 0 이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore(= mutex): lock을 걸 때 자원의 개수가 1개인 경우
  • 0 또는 1의 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion (lock/unlock)에 사용

 

6. Deadlock and Starvation

• 상황) 세마포어 S와 Q가 있는데, 어떤 일을 하기 위해서 이 2개의 자원을 모두 획득해야 일을 할 수 있는 구조에서 발생하는 문제
  • 예) 하드 디스크 A에서 B로 copy 하려면: 하드디스크 A와 B를 모두 보유 → A에서 읽어서 B에 쓰고 → 반환
• Deadlock(데드락): 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

  

  • 문제) 상대방이 가진 것을 기다리면서 자기 것은 내어 놓지 않고 영원히 기다려야 하는 상황
    • 일이 다 끝난 다음에만 자원을 내놓지, 그전에는 절대 자원을 내놓지 않는다: Deadlock
  • 해결) 자원을 획득하는 순서를 똑같이 맞추면 된다.
    • 그렇게 되면 둘이서 하나씩 가지고 있으면서 영원히 내놓지 않는 문제는 발생하지 않는다.
    • 프로그래머가 유의해서 작성해야 함
• Starvation: indefinite blocking
  • 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
  • 특정 프로세스드만 자원을 공유하면서 다른 프로세스는 영원히 차례가 오지 못하게 하는 문제
  • Starvation은 각각의 입장에서 자원을 받지 못하고 있는 것이라면, Deadlock은 여럿이 얽혀 어느 누구도 진행이 불가능한 상황

 

[복습]

1. 세마포어: object와 operation으로 구성, 상호 배제의 원리를 보장하는 알고리즘
   
   • integer variable: 자원의 개수
   • P연산(획득), V연산(반납)
2. Block & Wakeup: 공유데이터에 다른 프로세스가 접근하고 있으면 while문에서 대기할 필요 없이 그 프로세스 자체를 blocked 시켜 CPU를 반납하고 잠들어 있다가 다른 프로세스가 공유 데이터를 반납하면 그 때 깨어나서 준비 큐에서 CPU를 얻으면 공유 데이터를 얻을 수 있다.
   
   • block: 세마포어를 획득하지 못한 상태 - 일시 중지시키고, PCB를 세마포어에 대한 wait queue에 넣음
   • wakeup: 세마포어를 반납하고 block된 프로세스 중 하나를 깨워 그 프로세스의의 PCB를 ready queue로 옮김
3. 세마포어 S 변수의 의미
   1. busy-wait: 자원의 개수
   2. block & wakeup: 깨워야 할 것이 있는지 없는지를 확인해야 하는 상황
4. Counting semaphore: 자원의 개수가 여러개 있을 때의 세마포어
5. Binary semaphore(= mutex): lock을 걸 때 자원의 개수가 1개인 세마포어
6. Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 이벤트를 무한히 기다리는 현상
   
   • 해결: 프로세스의 자원을 획득하는 순서를 똑같이 맞추면 해결할 수 있다.
7. Starvation: indefinite blocking: 무한 대기

 

 

 

 

---

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제], [2017년 1학기 운영체제] 강의 정리입니다.

 [Operating System Concepts] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140404151340260748?vmode=f 

반효경 [운영체제] 13. Process Synchronization 2