퇴근 후 운영체제 시리즈 - 세마포어 & 모니터

in Studying CS Basic
퇴근 후 운영체제 시리즈 - 세마포어 & 모니터

운영체제 스터디 기록

해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다

Hits

Semaphores

💡 앞의 방식들을 추상화시킨 것 Semaphore S

Busy Wait

  • integer variable
    • Counting Semphore : 도메인이 0 이상인 임의의 정수값 / 주로 리소스 카운팅에 활용
    • Binary Semaphore(=mutex) : 0과 1만 가질 수 있음 / lock과 unlock을 나타냄
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능
    • P(S) - 자원을 획득하는 과정
        while (S<=0) do no-op; #wait
  S--;
    • V(S) - 자원을 반납하는 과정
        S++;

image

  • 바쁜 대기(Spin Lock) 은 비효율적!
  • Block & Wakeup 방식의 구현을 진행하자

Block & Wakeup

image

image

  • value를 하나를 줄이고 시작

  • 만약 더 이상 자원이 없다면(s.value < 0) 해당 프로세스를 queue에 넣어주고 block 시킴

  • 0 이하인 상황에서는 block 상태에서 ready 상태로 바꿔준다

Which is Better?

💡 Busy wait vs. Block/wakeup

  • 임계구역 경합이 많은 경우 Block / Wakeup이 적당
  • 경합이 치열하지 않은 경우 Block / Wakeup 오버헤드가 busy-wait 보다 클 수 잇음

발생하는 문제들

Deadlock

image

  • 세마포어 변수 S, Q가 있다고 하자
  • 두 개의 변수를 모두 얻어야 할 수 있는 작업이 있다고 하자 (ex. a라는 파일을 읽어서 b라는 파일에 덮어쓰는 일)
  • P0와 P1 모두 이 둘을 필요로 한다면..?
  • 서로가 서로의 자원을 원하는 일이 발생하면서 무한 대기 현상 발생

Bounded - Buffer Problem (생산자 소비자 문제)

image

  • 생산자 프로세스 vs 소비자 프로세스
  • 비어있는 공간을 생산자 프로세스 둘이 발견했다면..? ⇒ Lock 을 걸어서 처리하자
  • 소비할 자원을 소비자 프로세스 2개가 동시에 쓸려 한다면…? ⇒ Lock 걸자!

image

💡 어떤 문제가 잇는 것인가?

유한 버퍼라는 점을 인지하자.

  • 생산 프로세스 : 빈 버퍼가 있어야 데이터를 집어넣을 수 있다. 만약 꽉 차있다면 소비자 프로세스가 소비할 때까지 기다려줘야됨
  • 소비 프로세스 : 채워진 버퍼가 있어야 job 을 처리할 수 있다. 버퍼가 비어있다면 생산자가 채워줄 때까지 기다려야 된다.

⇒ 버퍼 자체가 공유되는 점에서 함부로 이를 처리할 수는 없음. 이때 요긴하게 사용되는 것이 바로 Counting Semaphore (버퍼가 몇개 차있나~)

image

  • 생산자 : empty 를 줄이고 내가 사용할 버퍼에 mutex 락을 걸고 처리
  • 소비자 : full 버퍼가 있을때 버퍼를 소비한다. 똑같이 mutex를 걸어서 처리한다.

⇒ Full / Empty : Counting Semaphore

⇒ Mutex : 해당 버퍼에 대한 락

Readers & Writers Problem

💡 한 프로세스가 DB(공유 데이터)에 write 중일 때 다른 프로세스가 접근하면 안되는 문제

Read는 다 같이 읽어도됨

Solution

  • Writer 가 DB에 접근 허가를 아직 얻지 못한 상태에서는 Reader들을 다 DB에 접근하게 해준다.
  • Writer 는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용
  • Writer가 접근 중이라면 모든 Reader 들은 접근 금지
  • Writer가 DB 에서 빠져나가야만 Reader 진입 가능

image

image

  • reader가 1명 처음으로 왔다면 writer 못 들어오게 하기 위해 P(db)를 처리함
  • 내가 마지막으로 읽고 나가는 reader 라면 V(db)로 처리
  • 기아 문제가 발생할 수 있음
    • reader 가 무한히 계속해서 읽고 있는데 안 끝난다면 writer는 영원히 DB에 접근이 안됨

⇒ 일정 시간동안만 접근하는 리더들만 허용했다가 writer 로 변환해주면 해결 가능!

식사하는 철학자 Problem

image

  • 철학자들의 배고파지는 시간이 각기 다르다.
  • 젓가락은 5짝만 존재하고 철학자는 굶어 죽으면 안된다! ⇒ 데드락

image

💡 우리가 차용할 솔루션은 2번 째, 모두 집을 수 있을 때만 집게 하자라는 것이다.

image

  • mutex : state를 건들기 위해서는 락을 걸어야됨
  • test에서 V(self[i]) 를 통해 젓가락을 집을 권리가 생김

Monitor

세마포어의 문제점

  • 코딩하기 힘들다
  • 정확성의 입증이 어렵다
  • 자발적 협력이 필요
  • 한번의 실수가 모든 시스템에 치명적 영향 (가장 큰 이슈)

⛸️ 동시 수행 중인 프로세스 사이에서 abstract data type 의 안전한

공유를 보장하기 위한 high-level synchronization 구조

image

세마포어와 다르게 오직 모니터 함수 내에서만 처리할 수 있음

image

  • 함수 내에서 아예 진입자체를 막는다.

  • 개발자에게 편한 함수형 프로그래밍

  • 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
  • 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음
  • 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition 변수 (큐 역할)를 사용
  • 컨디션 변수는 wait과 signal 연산에 의해서만 접근 가능
    • x.wait()
      • x.wait()을 invoke 한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend
      • 한마디로 큐에 넣어주는 메서드
    • x.signal()
      • x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume(깨우는 역할)
      • suspend 된 프로세스가 없으면 아무 일도 일어나지 않는다.