동시성 제어 예제(Bounded-Buffer, Readers-Writers

운영체제 관련 글 순서

- 프로세스란
- 쓰레드
- CPU 스케줄링
- 동기화 툴
- 동시성 제어 예제
- 데드락
- 주 메모리
- 페이징과 스와핑
- 가상 메모리와 디맨드 페이징
- 페이지 교체 알고리즘(FIFO, OPT, LRU), 쓰레싱, working set

 

 

Bounded-Buffer

• Producer-Consumer 문제라고도 부름
• n개의 버퍼가 있을때, 각각의 버퍼는 한개의 아이템을 가질 수 있음.
• 프로듀서는 버퍼에 채우는 역할, 컨슈머는 버퍼의 내용을 읽는게 역할.
• 데이터구조
  •  
  • int n; semaphore mutex = 1; // 동시 접근 막기 세마포어 semaphore empty = n; // 버퍼의 크기 semaphore full = 0;
• Producer&Consumer 코드
  •  

    

• 프로듀서 작업(empty -1, full +1). 컨슈머 작업(empty +1, full -1).
• 컨슈머 입장에선 버퍼에 작업한 것이 있어야 자원을 받아 작업이 가능하고, (버퍼에 빈공간 증가)
• 프로듀서 입장에선 버퍼에 공간이 있어야 자원을 받아 작업이 가능해진다.(버퍼 공간 차지)

 

Readers-Writers

• Readers는 읽기만, Writers는 읽기도하고 쓰기도 함.
• 읽기만 하는 Readers는 공유 데이터에 동시에 접근해서 읽어도 데이터에 영향이 없음.
• writer가 끼어 있는 경우 문제가 생김.
• 해결방법
  1. 독자 우선형(readers-preference)
  2. 저자 우선형(writers-preference)
  3. 균등형(fairness for readers and writers)
• 문제점
  • 1,2번 둘다 기아현상(startvation)이 발생할 수 있음.
• 1번 해결방법 코드

  • 

  • 

  • 변수설명
    • rw_mutex : 다른 프로세스들 간의 임계영역을 보호하기 위한 뮤텍스
    • mutex: 프로세스 reader안에서 임계영역을 보호하기 위한 뮤텍스
    • read_count: reader의 개수 ( 0이라면 writer 접근 가능)
  • 코드설명
    • reader가 처음 들어왔을때, rw_mutex로 cs에 진입하여 데이터베이스 읽음.
    • 다른 reader 프로세스(쓰레드)가 들어오면, 같이 읽을 수 있음.
    • 모든 reader가 다 읽었을때, rw_mutex를 signal하여 다른 기다리고 있는 writer cs진입 가능.
• 2~3번 해결방법은 아래 링크 참조
  • https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem

 

Dining-Philospphers

• 식사하는 철학자

• 

• 철학자들이 밥을 먹을때, 양쪽의 젓가락을 써야지만 밥을 먹을 수 있다.
• 사람은 5명이지만, 젓가락도 5개라서 최대 2명만 동시에 먹을 수 있다.
• 해결방법
  1. 각 젓가락마다 세마포어를 설정한다.
     • 상호배제는 가능하나, 데드락과 기아현상 발생할 수 있음.
     • 인접해있는 두사람이 서로 다른 젓가락을 가지고, 다른 자원을 요구할 경우 데드락 또는 기아현상이 발생할 수 있다.
  2. 철학자들의 번호에 따른 제한.
     • 홀수번호의 철학자는 왼쪽을 집은 후에 오른쪽을 집게 설정.
     • 짝수번호의 철학자는 오른쪽 집은 후 왼쪽.
     • 데드락은 해결해지나, 기아현상은 발생할 수 있음.
  3. 양쪽의 젓가락을 사용가능할때로만 제한.
     • Monitor를 사용.
     • 철학자의 상태를 3가지로 나누기(생각하기, 배고픈 상태, 밥먹는 상태)
     • 철학자가 밥을 먹을땐, 양쪽의 철학자가 밥먹고 있지않을때 먹게하면 됨.
     • 마찬가지로, 기아현상이 발생할 수 있음.
• 코드 구현
  • 3번 Monitor

  • 

    • 변수설명
      • state: 철학자의 수
      • condition: 철학자의 상태
    • 코드설명
      • test를 통해 양쪽이 밥먹는지 확인.
      • pickup을 통해 배고픈상태로 변경. test 식사단계로 돌입
      • putdown을 통해 식사 끝남.

 

Thread-safe Concurrent Applications

• 뮤텍스락,세마포어,모니터의 경우 멀티코어 환경에서 경쟁상황 또는 데드락에 빠져들 수 있다.
• 그래서 Thread-safe 한 대안이 별도로 있다.
  • Transactional Memory
    • 데이터의 불러오기와 저장하기 등의 명령의 집합을 원자적을 실행하는 방법.
    • 모든 명령이 정상적으로 수행했을때만 성공적으로 수행.
  • OpenMP(Open Multi-Processing)
    • API
    • 코드 블록을 병렬 영역으로 지정하여 사용
  • Functional Programming Language(함수형 프로그래밍)
    • 부수효과들을 제거한 순수함수를 조합하고, 공유 상태나 변경가능한 데이터 등의 부작용을 피하는 기본 원칙에 의해 소프트웨어를 구성
    • 부수효과: 변화가 발생하는 작업
      • 변수 값 변경
      • 객체 필드값 설정
      • 예외 오류 발생
      • I/O 발생
      • ...

 

참조

주니온님의 인프런 운영체제강의(공룡책)