philosophers(2), thread

업데이트: May 17, 2022

태그: thread

카테고리: os

프로세스 동기화

Background

Cooperating processes
- 서로 영향을 주고받는다.
- 논리적 주소 공간을 공유(thread)하거나 데이터를 공유(message passing)한다.
- 하지만, shared data에 concurrent access하는 것은
  - 데이터 비일관성을 초래할수도 있다.
- 그러므로,
  - 논리적 주소공간을 공유하는 cooperating 프로세스의
  - 순차적 실행은 데이터 일관성을 유지할 수 있다.
프로세스(쓰레드)가 공유하는 데이터 무결성
- Concurrent 실행 중에
  - 프로세스는 instruction 스트림 속에서 언제라도 interrupted당할 수 있다.
  - 이에따라, 처리코어는 다른 프로세스의 명령어를 실행하도록 할당할 수 있다.
- Parallel 실행 중에
  - 2개 이상의 명령 흐름이(다른 프로세스에서)
  - 동시에 다른 처리코어에서 실행될 수 있다.
데이터 비일관성
- 생산자-소비자 문제로 예시
  - shared data(buffer)를 사용하고, 비동기적으로 처리한다고 생각해보자.
  - Parallel 처리 할때는 생산자와 소비자가 동시에 버퍼에 쓰고 읽으니 문제가 발생할 것이라는게 자명하다.
  - 하지만 Concurrent할때는?
  - 두 프로세스가 Concurrent하게 하나의 변수에 접근하려할 때, 문제가 발생한다.
  - 이렇게 접근이 발생한 특정 순서에 의존하는 상황을
  - 경쟁 상황이라고 한다.
Race Condition(경쟁상황)
- 프로세스나 쓰레드가
- shared data에 concurrently하게 접근하고 조작한다면
- 결과는 접근하는 부분적인 순서에 의존된다.
Race Condition Solution
- 특정 시간에 1개의 프로세스만 shared data에 접근할 수 있다.
- 이를 프로세스 동기화라고 부른다.

Critical Section Problem(임계영역 문제)

임계영역 문제
- 시스템이 N개의 프로세스로 이뤄져있다고 가정
  - 각 프로세스가 다른 프로세스와 공유되어
  - 데이터를 접근, 수정하는 코드 영역인
  - 임계영역을 가지고 있다고 가정
  - 한 프로세스가 임계영역을 실행하고 있다면 다른 프로세스가 해당 임계영역을 실행할 수 없게 만들자.
- 두개의 프로세스가 동시에 임계영역을 실행할 수 없게 하는 것.
- 자연스럽게 동기화가 일어나고, 데이터를 cooperatively하게 공유한다.

코드 섹션
1. entry-section
  - 임계영역에 진입하기위한 허가 요청
2. critical-section
3. exit-section
  - 임계영역에서 나온다.
4. remainder-section
  - 임계영역 외의 코드 영역

문제 해결을 위한 3가지 요건
1. Mutual Exclusion (상호배제)
  - 만약 프로세스가 임계영역을 실행한다면
  - 다른 프로세스는 임계영역을 실행할 수 없다.
2. Progress(데드락 방지)
  - 만약 아무런 프로세스가 임계영역을 실행하고 있지 않고,
  - 어떤 프로세스가 임계영역을 실행하고 싶은데
  - 임계영역 진입이 무한대로 연기되는 상황
3. Bounded Waiting(starvation 방지)
  - 프로세스가 임계영역에 진입요청을 한 후에
  - 그 요청이 허용될때까지
  - 다른 프로세스들이 임계영역에 진입하도록 허용되는 횟수 제한

단일 코어 환경에서 단순한 해결책
- shared variable이 수정되는 동안에는 interrupt를 막는다.
- 현재 실행중인 명령어를 preemption없이 순서대로 실행하는게 보장된다.
- 단, 멀티프로세서 환경에서는 시스템 효율성이 낮아지는 문제가 있다.

2가지 접근법
- 비선점형 커널(non-preemptive kernel)
  - 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고,
  - 커널 모드에서 실행중인 프로세스가 커널을 빠져나가거나, block되거나, 자발적으로
  - CPU 제어를 양보할때까지 수행.
  - 성능이 느리므로, 잘 쓰이진 않음.
- 선점형 커널(preemptive kernel)
  - 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용
  - 설계하기에 어려움.
  - 하지만 응답이 더 빠름.

Peterson의 해결안

임계영역에 대한 Software Solution
- Dekker’s Algorithm
  - 2개의 프로세스를 위한 알고리즘
- Eisenberg and McGuire’s Algorithm
  - n개의 프로세스에 대해 n - 1의 하한선을 가진 경우
- Peterson’s Algorithm
  - 임계영역 문제에 대한 전통적인 소프트웨어 해결책
  - 해결될 것이라는 보장이 없음.
  - 왜냐하면 현재 컴퓨터는 load - store로 수행하기 때문.
  - 하지만,
    - 임계영역 문제의 좋은 알고리즘적 묘사이며.
    - CSP 문제 해결을 위한 3가지 요건을 잘 나타낸다.

peterson 알고리즘 코드

  #include <stdio.h>
  #include <pthread.h>

  # define true 1
  # define false 0

  int sum;
  int turn;
  int flag[2];

  void	*producer()
  {
      int	i;

      i = 0;
      while (i < 100000)
      {
          flag[0] = true; //내 차례임!
          turn = 1;//다음은 쟤 차례임!
          while (flag[1] && turn == 1)
              ;//consumer가 실행중이고, consumer의 차례일때 대기
          sum++;
          flag[0] = false; //내 차례 끝남!
          i++;
      }
      pthread_exit(0);
  }

  void	*consumer()
  {
      int	i;

      i = 0;
      while (i < 100000)
      {
          flag[1] = true;//내 차레임!
          turn = 0;//다음은 쟤 차례임!
          while (flag[0] && turn == 0)
              ;//producer가 실행중이고, producer차례인동안 대기
          sum++;
          flag[1] = false;
          i++;
      }
      pthread_exit(0);
  }

  int main()
  {
      pthread_t	t1;
      pthread_t	t2;

      pthread_create(&t1, 0, producer, 0);
      pthread_create(&t2, 0, consumer, 0);
      pthread_join(t1, 0);
      pthread_join(t2, 0);
      printf("sum : %d\n", sum);
  }

Hardware-based Solutions
하드웨어 명령이
- CSP문제 해결을 지원하도록 하자.
- 동기화 도구로 바로 사용될 수 있게하고
- 추상적인 방법의 도구로써 사용되게하자.
3가지 명령
- memory barrier / fences
- hardware instructions
- atomic variables
Atomicity(원자성)
- 원자성이 있는 동작이란 interrupt를 걸 수 없는 동작의 단위이다.
- 현대 컴퓨터는 특별한 하드웨어 명령을 제공한다.
  - test and modify
  - test and swap
  - 이건 회로를 통해 구성해야한다.
- atomic instructions의 2가지 유형
  1. test_and_set()
  2. compare_and_swap()
- atomic variable
  - 위의 atomic instruction들ㅇ느 atomic variable 구축에 사용된다.
  - atomic variable은
    - 정수나 불린형과 같은 기본 자료형에 atomic operation을 하는 것.
    - 한 변수에 대한 경쟁상황에서
    - 상호 배제성을 만족할 수 있다.

Mutex Locks

CSP를 풀기위한 고수준 도구
- Mutex Locks
  - 동기화를 위한 간단한 도구
  - 임계구역 들어가기전에 락을 획득, 임계구역 빠져나올때 락을 반납함.
  - 2개의 프로세스에 대한 것
- Semaphore
  - n개의 프로세스에 대한 제어
  - 간단하고 효과적이고 더 편리함.
- Monitor
  - mutex와 semaphore의 단점을 극복.
- Liveness
  - 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기위한 일련의 속성

Mutex Locks

mutex : mutual exclusion의 약자
임계영역을 보호하고, 경쟁상황을 막는다.
프로세스는 critical section 진입 전, lock을 acquire

critical section나갈 때 lock을 release

  while (true)
  {
      acquire()
          //critical section
      release()
          //remainder section
  }
  acquire()
  {
      while (!available)
          ; //busy_wait
      available = false;
  }
  release()
  {
      available = true;
  }

acquire, release라는 함수가 필요하다.
- 이 함수들은 각각 atomically하게 수행되어야한다.(도중에 context switch가 일어나면 안됨)
lock이 현재 사용할 수 있는지 없는지에 대한 변수 하나 필요

Busy waiting 문제
- 임계영역에 들어가는 프로세스는 acquire에서 무한루프를 돌게된다.
- 멀티프로그래밍 환경에서는 이게 단점이 되는데,
  - 단일 코어가 많은 프로세스에 의해 공유되는 환경에서
  - 다른 프로세스가 효율적으로 사용할 수 있는 CPU 싸이클을 낭비하게된다!
Spinlock
- 락을 획득할때까지 프로세스가 spin하는 mutex lock 유형
  - 장점
    - context switch가 오랜 시간 걸릴때, context switch를 할 필요가 없음
    - 멀티코어 시스템의 특정 상황 속에서
      - 쓰레드가 다른 쓰레드가 임계영역에 접근해있으면
      - spin만 하면 되기 때문에 더 선호된다.
        
        spinlock을 하지 않는다면
        
        프로세스가 wait queue에 들어가야하므로,
        
        ready queue로가서 다시 CPU를 할당받기까지 시간이 걸림.

mutex 사용 예제

  #include <stdio.h>
  #include <pthread.h>

  int sum = 0;

  pthread_mutex_t mutex;

  void	*counter(void *param)
  {
      int k;

      k = 0;
      while (k < 10000000)
      {
          //entry section
          pthread_mutex_lock(&mutex);
          //critical section
          sum++;
          //exit section
          pthread_mutex_unlock(&mutex);
          //remainder section
          k++;
      }
      pthread_exit(0);
  }

  int main()
  {
      pthread_t	t1;
      pthread_t	t2;
      pthread_mutex_init(&mutex, NULL);
      pthread_create(&t1, 0, counter, 0);
      pthread_create(&t2, 0, counter, 0);
      pthread_join(t1, 0);
      pthread_join(t2, 0);
      printf("%d\n", sum);
      return 0;
  }	

Semaphore

semaphore
- 신호장치, 신호기를 의미
- 정의
  - semaphore S는 초기화하는 때 말고는 wait(), signal()로만 접근할 수 있다.
  - wait()는 P()
  - signal()은 V()로 사용하기도 한다.
  - 각 함수는 atomic하게 구현.
  - 함수
    wait(S) { while (S <= 0) ;//busy wait S--; } signal(S) { S++; }
  - S는 자원이라고 생각하면 된다.
    - wait는 이 자원을 사용하는 것을 의미.
    - signal은 사용하던 자원을 반납한다.
    - S가 0개가 되면 signal로 자원을 반납할때까지 busy wait을 하게된다.

Semaphore 종류
- Binary Semaphore
  - S가 이진수, 즉 0과 1인 경우를 의미한다.
  - 이 경우에는 mutex lock과 동일하게 동작한다.
- Counting Semaphore
  - S의 범위는 제한이 없다.
  - 단, S가 정해지면 그 숫자만큼의 유한한 인스턴스를 의미하므로
    - 한정된 갯수의 인스턴스에 접근하는데에 사용될 수 있다.

Counting Semaphore 사용법
1. 유한한 사용가능 자원의 갯수로 semaphore(S)를 초기화한다.
2. 프로세스가 자원을 사용하면
  - wait()로 S를 감소한다.
3. 프로세스가 자원을 반납하면
  - signal()로 S을 증가시킨다.
4. S가 0이되면 모든 자원이 사용되고 있으므로,
  - 자원을 사용하고 싶어하는 프로세스는 S가 0보다 커지기 전까지 block된다.

동기화문제를 세마포어로 풀기
- P1 P2가 concurrently 하게 실행중.
- P1은 S1이라는 문장, P2는 S2라는 문장을 가짐
- S2가 S1이 끝나야만 실행될 수 있다면,
  1. P1과 P2가 Semaphore를 공유하게끔하고, 0으로 초기화한다.
  2. P1에서 S1을 실행하고 signal로 자원을 반납하고,
    S1; signal(synch);
  3. P2에서 wait로 자원을 사용하고 S2를 실행한다.
    wait(synch) S2;

Semaphore 구현

Semaphore는 또한 busy waiting 문제가 발생할 수 있다.
이 문제를 해결하려면 P(), V()를 수정해야한다.
프로세스가 wait()을 실행하면
- 만약 semaphore가 음수라면 wait해야한다.
- busy waining(무한루프) 대신에, 멈추고 waiting queue로 넘어가야한다.
다른 프로세스가 signal()을 실행하면
- 프로세스를 재시작하고, ready queue에 놓는다.

구현

  typedef struct
  {
      int value;
      struct process *list;
  } semaphore;
		
  wait(semaphore *S)
  {
      S->value--;
      if (S->value < 0)
      {
          //add this process to S->list
          sleep();
      }
  }

  signal(semaphore *S)
  {
      S->value++;
      if (S->value <= 0)
      {
          //remove process P from S->list;
          wakeup(P)
      }
  }

Monitors

mutex와 semaphore는 편리하고 효과적이지만
timing error가 일어날 수 있다.
- 이런 타이밍 오류는 특정 실행 순서로 진행했을때만 발생하고, 항상 일어나는건 아니다.
- 발견하기 어려움

엘비

philosophers(2), thread

프로세스 동기화

Background

Critical Section Problem(임계영역 문제)

Peterson의 해결안

Mutex Locks

Semaphore

Monitors

댓글남기기

참고

Deep learning 한계

[CA] Processor Datapath

신경망: Deep learning 응용