[운영체제] 7. Synchronization Examples(1)

오영선·2022년 7월 13일

7. 동기화 예제

ch.6에서는 Critical section과, 경쟁 조건에 중점을 두었다면 ch.7에서는 6장에서 제시된 도구를 고전적인동기화 문제에 적용하는 것에 중점을 둔다.

7.1 고전적인 동기화 문제들

이 문제들은 새롭운 동기화 방법이 제시되었을 때 그 방법을 검증하는데 이용된다. 해결안에서는 semaphore가 사용되지만 실제 구현에서는 mutex가 사용될 수 있다.

semaphore : critical section을 지나가도 될지/안될지를 표현하는 깃발.
lock의 경우는 0,1로 표현하는데 
세마포어는 shared data의 개수를 의미한다. 
lock과 반대로 최대로 사용될때(더이상 이용X) 0, 이용가능 할때 1>= 이다. (최대 몇명까지 공유가 되는지) 
(단, 0과 1만 가질때 binary semaphore라고 한다. 그 외에는 counting semaphore)
세마포어는 wait(), signal()로 자원을 사용하고 반납한다. wait() : -1, signal() : +1로 이해하자.

7.1.1 유한 버퍼 문제

초기화 설정
	int n; //pool의 수
    semaphore mutex = 1;
    semaphore empty = n; //처음에는 모두 쓸 수 있다.
    semaphore full = 0;

초기화 설정
	while (true) {
      wait(full);
      wait(mutex);
      ...
      /* remove an item from buffer to next consumed */'
      while(count==0);
      next_consumed = buffer[out];//빈 버퍼를 넣는다.
      ...
      signal(mutex);
      signal(empty);
      ...
      /* consume the item in next consumed */
      ...
}

소비자 : 생산자를 위해 빈 버퍼를 생산한다.

while (true) {
...
/* produce an item in next produced */
...
wait(empty); //empty-1
wait(mutex);
...
/* add next produced to the buffer */
while(count == bufferSize);
buffer[in] = next_produced; //채워넣는다.
...
signal(mutex);
signal(full); //full+1
}

생산자 : 소비자를 위해 꽉찬 버퍼를 생산

에효.,.에요.,. 에효,.,.

7.1.2 Readers-Writers 문제

DB에 접근하는 readers와 writers가 있을 때, 하나의 writer가 데이터를 조작 중 다른 스레드가 동시에 접근할 때의 문제
-> writer에게 배타적 접근권한을 줌으로 써 해결.

변형 문제)
1. writer가 아직 접근하지 않았을 때 (미허가) reader가 기다려서는 안된다. -> writer가 기아상태
2. writer가 준비되면 가능한 빨리 수행되어야 한다. (writer를 끝내고 새로운 reader를 수행하기 위해) -> reader 가 기아상태

1의 문제 해결하기 :

초기화 설정
	semaphore rw_mutex = 1; //rw모두 접근
    semaphore mutex = 1; //readCnt 접근떄 사용
    int read_count = 0; //현재 접근중인 reader수

rw_mutex는 writer의 상호 배제권한을 주기 위해 사용되고, 첫번쨰와 마지막reder에 의해서도 사용된다.

writer 

while (true) {
  wait(rw mutex); //rw-1
  ...
  /* writing is performed */
  ...
  signal(rw mutex); //rw+1
}

reader 

while (true) {
  wait(mutex);
  read count++; 
  if (read count == 1) //마지막
  wait(rw mutex);
  signal(mutex);
  ... //n-1개 수행중
  /* reading is performed */
  ...
  wait(mutex);
  read count--;
  if (read count == 0) //첫번째
  signal(rw mutex);
  signal(mutex);
}

7.1.3 식사하는 철학자들

교착상태, 기아상태를 발생시키지 않고 여러 스레드에게 여러 자원을 할당 하기.

1) 세마포 해결안.
각 젓가락을 하나의 세마포로 표현한다. wait()은 젓가락을 집고, signal()로 내려놓는다.

semaphore chopstick[5];

while (true) {
  wait(chopstick[i]);
  wait(chopstick[(i+1) % 5]); //두개씩 집는다.
  ...
  /* eat for a while */
  ... 
  -> 교착상태 발생. wait[i]가 동시에 5개 발생할때?
  -> wait(i+1)을 수행하지 못해 계속 기다리게 됨.
  signal(chopstick[i]);
  signal(chopstick[(i+1) % 5]);
  ...
  /* think for awhile */
  ...
}

2) 모니터 해결안 : 교착 X
양쪽 젓가락을 모두 얻을 수있을 때 젓가락을 집는다.

enum {THINKING, HUNGRY, EATING} state[5];
양쪽 두 이웃이 eating이 아닐때
(state[(i+4) % 5] != EATING) and (state[(i+1) %
5] != EATING).
식사 가능
e state[i] = EATING 

condition self[5]; : 젓가락 집기를 할 수 없을때 보류

DiningPhilosophers.pickup(i);
...
eat
...
DiningPhilosophers.putdown(i);
를 통해 젓가락을 사용

monitor DiningPhilosophers
{
  enum {THINKING, HUNGRY, EATING} state[5];
  condition self[5];
  
  void pickup(int i) {
    state[i] = HUNGRY;
    test(i);
    if (state[i] != EATING)
    self[i].wait();
  }
  void putdown(int i) {
    state[i] = THINKING;
    test((i + 4) % 5);
    test((i + 1) % 5);
  }
  void test(int i) {
  if ((state[(i + 4) % 5] != EATING) &&
  (state[i] == HUNGRY) &&
  (state[(i + 1) % 5] != EATING)) {
  state[i] = EATING;
  self[i].signal();
  }
  }
  initialization code() {
  for (int i = 0; i < 5; i++)
  state[i] = THINKING;
  }
}

이 문제는 교착상태를 해결하지만 아직 기아상태를 해결하지는 못한다.

7.2 커널 안에서의 동기화

윈도우 동기화 : 다중 스레드 커널

윈도우는 다중 처리기 시스템에서 스핀락을 써서 전역정보 액세스를 통제한다.(단, 짧은 코드에 대해서)

커널 외부에는 스레드를 동기화하기 위해 dispatcher객체가 제공된다. 스레드는 이 객체를 사용해 mutex 락, 세마포어, event(조건부), 타이머.등의 방법으로 동기화 한다.

dispatcher객체는 signaled 또는 nonsignaled 상태이다.
signaled : 사용가능, 스레드 봉쇄 안됨.
non signaled : 사용 불가능, 스레드 봉쇄됨.

디스패처 객체때문에 스레드가 봉쇄되면 스레드는 대기상태가 되고, 객체의 대기 큐에 들어간다. 다시 signaled상태가 되면 큐를 검사하고 해당 스레드를 준비 상태로 바꾸어 실행가능하게 한다.

그림은 뮤텍스 락인데, 오직 하나의 스레드만 소유할 수 있으므로 대기큐에서는 하나의 스레드만 선택된다.

Critical-section 객체는 커널의 개입이 없는 사용자모드 mutex이다. 락을 획득하려는 프로세스는 커널mutex를 할당하고 CPU를 양도한다. 커널 mutex가 객체에 대한 경쟁이 발생할때만 할당되어 효율적이다.
참고

리눅스의 동기화
무슨말인지몰갯어여
--이걸 알아야대

7.3 POSIX 세마포

세마포를 두 유형으로 나눈다. named와 unnamed.
약간 전역세마포랑 지역세마포 공유범위로 나눈듯?
몬소리여

7.4 Java에서 동기화

머 이런게 있대 ~~
java 의 모든 객체는 하나의 락 과 연결되어 있다. 메소드가 synchronized로 선언되었을떄, 메솓를 호출하기 위해서는 해당 락을 획득해야 한다. (synchronized method)
만약 한 스레드가 그 메소드를 호출했는데 이미 다른 스레드가 락을 가졌다면 해당 스레드는 봉쇄되고, 객체의 락에 설정된 entry Set에 추가된다. (락이 얻어질때까지 기다렸다가 들어간다)
또한 대기 집합이라는 것이 있는데, 스레드가 락을얻고 실행될떄 해당 스레드가 조건이 안돼 조건이 만족될때까지 기다려야 할떄 들어갔다가 조건이 충족되고 나면 다시 entrySet으로 들어간다.

그외에 세마포도 있고... 조건변수도 있고. .하기싫다 . .

7.5 대체 방안들

스레드-안전 병행 응용 설계- 에 도움을 주는 프로그래밍 언어와 하드웨어들 :
1) 트랜젝션 메모리 :
메모리 트랜젝션 :
commit, roll-back()으로 원자성을 보장한다.
구현은 STM,HTM으로 가능하다(sw, hw 트랜젝션 메모리)
2) OpenMP :
스레드의 생성과 관리가 openMp라이브러리에 의해 처리되어 응용 개발자들은 신경쓰지 않아도 된다.
3) 함수형 프로그래밍 언어
C, C++, java, C# : 명령형 언어, 상태 기반
함수형 언어 : 명령형과는 많이 다르며 상태를 유지하지 않는다. 7장에서 논의된 문제들이 함수형 언어에서는 존재하지 않는다.

7.6 요약

프로세스 동기화의 고전적인 문제에는 유한버퍼, 읽는자-쓰는자, 식사하는 철학자 문제가 있다. 이러한 문제는 mutex lock, 세마포어, 모니터 및 조건 변수 등등 도구로 개발할 수 있다.
윈도우는 dispatcher 객체와 event로 프로세스 동기화를 구현한다.
linux는 원자적 변수, 스핀 락, mutex 락을 포함한 경쟁조건을 방지하기 위해 다양한 접근 방식을 쓴다.
POSIX api는 mutex락, 세마포, 조건 변수를 제공하고, 세마포는 기명, 무명 두가지를 제공한다. 기명 : 관련없는 프로세스들이 이름을 참조해 세마포에 액세스
무명 : 쉽게 공유할수 없고 공유 메모리 영역에
세마포를 배치해 해당하는 프로세스만 접근가능하다.
Java는 동기화를 위한 여러 라이프러리와 api가 있다. 모니터, 재진입 락, 세마포어, 조건 변수 가 있다.
임계구역 문제를 해결하려면 트랜젝션 메모리, OpenMP, 함수형 언어등이 있다. 함수형 언어는 상태를 유지하지 않으므로 일반적으로 경쟁조건, 임계구역의 영향을 받지 않는다.

참고
운영체제 서적
[세마포어] https://jhnyang.tistory.com/101