[운영체제 공룡책] 7. Synchronization Examples

동시성 제어의 고전적 문제들

7.1 Classic Problmes of Synchronization

• 대표적인 동시성 제어의 문제들
  • The Bouned-Buffer Problem : 생산자 소비자 문제를 유한 버퍼로 해결할 때의 문제
  • The Readers-Writers Problme
  • The Dining-Phiosophers Problem : 철학자들의 저녁

The Bouned-Buffer Problem (한정 버퍼 문제, 생산자-소비자 문제)

• Shared Data Structures
  • int n = 버퍼 공간
  • semaphore mutext = 1 , 바이너리 뮤텍스 세마포어! 여러 개가 동시에 버퍼 풀에 접근하지 못하도록 상호배제 하려고 사용함!
  • semaphore emtpy = n empty buffer 수를 카운팅하기 위해
  • semaphore full = 0 full buffer 수를 카운팅하기 위해
• 좌측 생산자
  • 소비자가 버퍼를 다 비울때 까지 기다림
  • 뮤텍스에게 허락을 받을때까지 기다림
  • 그후 동기 작업 진행 (싱크로나이즈드 키워드가 붙겠징)
  • 그 후 뮤텍스 반납
  • 그 후 버퍼 다 쓰면 full 해서 소비자에게 가져가라고 알려줌
  • 위 작업을 n번 반복해서 버퍼가 꽉 차면 소비자가 시작된당
• 우측 소비자
  • 생략
• 주거니 받거니 하는건가?
  교수님께서는 생산자 N개가 버퍼를 모두 꽉 채웠을 때 시그널이 발생해서 소비자로 넘어가는 거 처럼 말씀하셨는데, 로직은 생산자가 버퍼 한 번 쓰고 나서 signal 보내니까 바로 소비자에게 시그널가는 거 같음
• 여튼 복잡해서 잘 안쓴다고 하심
• 자바 코드로 구현된 샘플 있음!!
  • C언어 pthread와 semapohre로 생산자 1개, 소비자 1개 버퍼 5개짜리로 테스트했을 때 동기화가 잘 되지 않았던 이유는 세마포어 한계 때문이었나? 자바 모니터로 구현했을떄느 ㄴ괜찮은걸 볼 수 있음.. (버퍼사이즈 1개로 줘도 동일하게 생산자, 소비자가 티카타카안하고 갑자기 두 번씩 실행되는거 보임)
  • 자바에서 semapohre 모니터락 지원해줘서(wait(), notify()) Bounded-Buffer 문제 해결하는 코드 있음 (p16)
  • 근데 생상자5, 소비자5, 버퍼5로 두면 자바도 동일하게 문제 발생함

The Readers-Writers Problme

• 만약 concurrently하게 실행되는 프로세스들이 공유 자원에 읽기만 하거나, 읽고 쓰는 애들이 정해져있다면 어떨까? database처럼! 만약 두 개 이상의 reader들이 공유자원에 동시에 접근했을때 문제가 생길까? 전혀 영향 없음. writer들만 조심시키면 된다.
• Priority
  • first readers-writers : reader들은 다른 reader들이 작업이 끝내기를 기다릴 필요 없다. 단순히 writer들이 작업을 끝내길 기다리면 된다. 이 때 모든 프로세스들은 우선순위가 공평하기 때문에 writer가 대기하고 있다고 해서 특별히 가중치를 주지 않는다. (이러면 발생하는 문제가 있음. 보통 CUD 작업의 우선순위가 더 높음. 그래서 두번째 조건을 충족시켜야함. 여기서는 복잡해서 다루지 않는다고 함)
  • second readers-writers 문제 : writer가 access를 하기 위해 기다린다면 이들에게 우선순위를 줘서, 새로운 readesr들은 진입하지 않고 기다리게 함
  • starvation 문제는 위 두 케이스에서 발생할 수 있음
• The Readers-Writers Problem에서 first readers-writers 상황에 대해 코드로 알아보자
  • reader process 데이터 구조
  • semaphore rw_mutex = 1; // reader와 writer가 공유해서 쓰는 뮤텍스 semaphore mutex = 1; // 상호배제를 위해 사용 int read_count = 0; // 얼마나 많은 프로세스가 해당 자원에 접근하고 있는지 보여줌. 리더의 개수가 0이 되면 라이터 진입 가능.
  • 코드
    • 여기서는 라이터의 우선순위가 엄청낮다..! 읽고 있는 프로세스가 0개 일때만 라이터에게 자원을 점유할 수 있도록 해주네..! 근데 라이터에게 가는 게 확실한것도아님. rw_mutex를 기다리고 있던 프로세스는 리더들도 있움..!
    • 만약 1개의 라이터가 CS에 진입하면, N개의 리더들은 대기 상태임
      • 이 때, 1개의 리더는 rw_mutex 큐에 들어가있고
      • 나머지 n-1개의 리더들은 mutex 큐에 들어가있는 상태가 됨
      • rw_mutex : 리더와 라이터 프로세스들 간 상호배제를 위해 사용하는 뮤텍스
      • mutex : 리더 count의 수 증가/차감 시 상호배제를 위해 사용하는 뮤텍스
    • 라이터의 우선순위가 굉장히 낮음
      • 리더 프로세스들이 자원 접근을 하지 않은 상태가 되었을 때 (read_count == 0), 시그널을 보냄 (signal(rw_mutex))
      • 이때 라이터가 시그널을 받고 CS에 진입할 수 있음
      • 하지만 대기 큐에 라이터만 있는게 아니라 리더들도 있기 때문에 우선순위는 공평하게 스케쥴러에 의해 돌아감
  • Reader-Writer Locks을 통해 리더-라이터 문제를 쉽게 해결 가능 (개념만 간단히 짚고 넘어가겠음)
    • read mode의 여러 개의 프로세스가 reader-writer lock에 요청한다면 접근을 허락해줌
    • write mode의 프로세스는 단 한개만 허락해줌

철학자들은 왜 굶어 죽었을까?

Dining-Philosophers Problme

여러 개의 프로세스가 여러 개의 자원을 사용하고자 하는 상황

국수를 아주 좋아하는 철학자 5명이 모였습니다.
그들은 원형 테이블에 둘러 앉아 "삶이란 무엇인가?"라는 질문에 대한 해답을 고민하기 시작했습니다.
원형 테이블의 중앙에는 국수가 놓여 있었고, 테이블에는 모두 다섯 개의 젓가락이 낱개로 놓여 있었습니다.
즉, 철학자들 한 명의 왼쪽과 오른쪽에 각각 한 개의 젓가락이 놓여 있다는 뜻입니다.
따라서 철학자들은 왼쪽과 오른쪽 양쪽의 젓가락을 이용하여 국수를 먹을 수 있습니다.
국수는 무한리필되기 때문에 5명의 철학자들은 해답을 찾을 때까지 생각을 하기로 했습니다.
하지만 어느날 그들은 모두 굶어 죽었습니다. 왜 그랬을까요?

• 젓가락에 상호배제 되도록 mutex! 혹은 semaphore를 걸면 되지!
• 근데 데드락과 기아 문제는 여전히 존재하지!
  • 5명이 철학자가 동시에 배가 고프면?
  • 모두 동시에 오른쪽 젓가락을 잡는다면?
• 해결방법 (이 방법들은 데드락까지 해결가능한데, 기아 상태를 해결할 수는 없다)
  • 철학자들의 숫자를 4명으로 제한함
  • 양쪽 젓가락이 모두 사용 가능할 때만 젓가락을 잡도록 함
  • asymmetric. 홀수번호를 부여받은 철학자는 왼쪽 젓가락을 집고 오른쪽을 집고, 짝수는 오른쪽 먼저 그후 왼쪽 젓가락 집기
  • 데드락 문제 여담 : 방지하는 비용보다 오류발생 비용이 저렴해서, 발생 빈도수가 적으니 그냥 냅두고 빨리 캐치해서 수정하는 방향으로 푸는 걸 많이 선택하나봄
• 지금까지 배운 동기화 도구들로 문제를 해결해볼거야! 문제해결이 중요한건 아니고, 이런 도구들을 다뤄서 동기화를 해결해보는 게 중요한거임! 뮤텍스와 세마포어를 통해 상호배제를 구현하는 것은 어려웠으니까, Monitor lock으로 2번째(양쪽 젓가락 모두 가용할때만 잡도록함)을 구현해보겠음
• Monitor Solution 요구사항
  • 제한 : 양쪽 젓가락이 가용할 때만 젓가락을 집도록 함
  • 세 가지 상태 : 생각 상태와 배고픔 상태 그리고 식사 상태
  • 철학자들은 양쪽의 철학자가 식사중이 아닐때, 젓가락이 모두 가용할 때만 배고픔 상태에서 식사 상태로 변경할 수 있음
  • 참고로 이렇게 구현해도 상호배제와 데드락 방지는 되는데, 기아는 못막음
• Monitor Solution 구현
  • DiningPhilosopher 클래스 : 젓가락 배분 책임을 가짐
    • Monitor로 구현
    • pickip() : 젓가락 집기
    • putdown() : 젓가락 내려놓기
• Monitor Solution 구현 코드 자바 코드로 구현된 샘플 있음!! TODO 실습해보기~

7.5 Alternative Approaches

• Thread-Safe Concurrent Applications:
  • 멀티코어 시스템에서 Concurrent applcations(뮤텍스락, 세마포어, 모니터 등)은 퍼포먼스가 굉장히 좋은 반면에 race conditions과 liveness hazard(deadlock) 와 같은 문제가 발생함
  • 여러 가지 대안들이 나옴! concurrent하게 돌려도 되는 것을 thread-safe 하다고 표현함!
    • 뮤텍스락, 세마포어, 모니터도 포함하여 여러 가지 대안이 나옴
    1. Transactional Memory : atomic한 operation. 원자적 실행 단위. 메모리 자체를 트랜잭셔널하게 만듬
    2. OpenMP : #pragma, omp parerall~
    3. Functional Programming Language