pintOS › pintOS 쓰레드 이론 정리(Week8_Day2)

드디어 pintOS 주간의 시작이다! 오늘은 사전 학습 자료를 정리하기로 했다.

Threads(쓰레드)

동기화

쓰레드 간의 자원 공유는 통제하지 않으면 모든걸 망가뜨릴 수도 있다!
pintOS에서 제공하는 몇 가지 동기화 요소들에 대해 정리해 보자.

공통 사전 지식

pintOS는 선점형 커널이다. 이를 이해하기 위해서는 두 가지 개념을 이해해야한다.

• 선점형 스케쥴링(Preemptive Scheduling)
  어떤 쓰레드가 CPU를 사용하고 있는 동안 다른 쓰레드에 의해 선점(뺏는다는거야)당할 수 있는 스케쥴링 방식이다.
• 비선점형 스케쥴링(Non-Preemtive Scheduling)
  어떤 쓰레드가 CPU의 사용권을 주어야 다른 쓰레드가 사용할 수 있는 방식이다(독점이 가능하다).

스케쥴링(Scheduling)
운영체제의 일부인 스케쥴러가 어떤 쓰레드가 프로세스가 CPU를 사용할 지 결정하는 행위로 여러 쓰레드 간의 CPU 시간을 분배한다.

선점(Preemption)
현재 실행 중인 쓰레드에게서 CPU를 뻇어서 다른 쓰레드에게 할당하는 행위이다.

그렇다면 자동으로 선점형 커널과 비선점형 커널은 각각의 스케쥴링 방식을 지원하는 커널을 의미한다는 것을 알 수 있다.

결론적으로 우리의 주안점인 pintOS는 선점형 커널이기 때문에 명시적인 스케쥴러의 호출 없이도 언제든지 커널 쓰레드에게서 CPU를 뺏을 수 있다.
반면 비선점형 커널의 경우 명시적인 스케쥴러의 호출이 있을 때에만 선점이 가능하다. 물론 유저 스레드는 언제나 선점이 가능하다.

이걸 기억하고 넘어가자!

Disabling Interrupts

동기화를 위한 가장 단순 무식한 방법은 interrupt를 비활성화 시켜버리는 것이다.
즉 저기요 잠깐만요! 를 못하게 응 싫어 하는 것이다. 이는 CPU가 interrupt에 반응하는것을 일시적으로 막아 다른 쓰레드가 CPU를 선점하는 것을 막는 것이다(preemption은 timer interrupt에 의해 작동함).

보통은 프로그래머가 직접 인터럽트의 상태를 설정 할 필요는 없고 이후 등장할 뮤텍스, 세마포어 등을 사용하여 쓰레드 간의 동기화를 처리 하게 된다.
그러나 이렇게 interrupt를 비활성화 하는 이유는 커널 쓰레드와 외부 인터럽트 핸들러 사이의 동기화(둘이 동시에 자원에 접근하지 못하도록)를 위해서 이다.

외부 인터럽트 핸들러(External interrupt handler)
하드웨어 인터럽트가 발생했을 경우로, 타이머, 키보드(키보드 입력), 네트워크 카드(새로운 패킷 도착), 디스크(데이터가 준비됬어요!) 등이 해당 신호를 CPU로 보낸다.
외부 인터럽트는 비동기적으로 발생하기 때문에, 언제든지 발생 할 수가 있다.
핸들러는 실행 중 대기하거나 차단되지 않기 때문에 빠르게 처리하고 커널에 제어권을 돌려주는 것이 중요한데, 외부 인터럽트의 처리 중 CPU의 다른 작업이 중단되기 때문에 커널 스레드와 동시에 자원에 접근하지 않도록 동기화 처리가 중요하다.

하지만 외부 인터럽트 중에서는 비활성화 하는 것으로 막을 수 없는 것들이 존재한다.
이들은 non-maskable interrupts(NMIs)라고 부르는데, 진짜 비상시에만 사용하는 interrupts다(컴퓨터에 불이 났어요 : 이건 중요하긴 해).
하지만 pintOS에서는 이런 interrupt들은 다루지 않는다.

다음은 interrupt를 무시하는데 사용하는 일련의 함수이다.

• INTR_OFF, INTR_ON 으로 interrupt의 활성, 비활성을 나타내는 열거형 타입니다.

  enum intr_level {
      INTR_OFF, // 기본 값은 0
      INTR_ON   // 기본 값은 1
  };
  

  enum 열거형 : 상수에 상직적인 이름을 붙혀 코드의 가독성을 높히는 집합을 의미한다.

• 현재의 interrupt 상태를 반환하는 함수이다.

  enum intr_level intr_get_level(void)
  

  현재의 interrupt 상태가 활성인지 비활성인지 알기위해 사용할 수 있다.

• 주어진 level 에 따라 인터럽트의 상태를 설정하며, 이전의 인터럽트 상태를 반환한다.

  enum intr_level intr_set_level(enum intr_level level)
  

  사용자는 선택에 따라 반환 된 인터럽트 상태를 통해 복원하는데 사용할 수 있다.

• interrupt를 활성화 하는 함수이다.

  enum intr_level intr_enable(void)
  

• interrupt를 비활성화 하는 함수이다.

  enum intr_level intr_disable(void)
  

세마포어(Semaphores)

세마포어는 교착상태(DeadLock)을 해결하기 위해 제안된 것으로, 두 개의 원자적 함수로 제어되는 정수 변수를 통해 멀티프로그래밍 환경에서 공유자원에 대한 접근을 제어한다.

교착상태 : 두 개 이상의 프로세스나 쓰레드가 서로 같은 자원을 가지려고 해서 무한하게 다음 자원을 기다리게 되는 상태이다.

원자성(Atomicity) : 여러 개의 쓰레드가 존재할 때, 특정 시점에서 어떤 메소드를 2개 이상의 쓰레드가 동시에 호출하지 못하게 하는것을 의미한다.
즉 연산이 중단되지 않고 완전히 실행될 수 있도록 다른 쓰레드가 개입하거나, 연산이 중단되는 일이 없는 상태를 의미한다.

공유자원 : 여러 쓰레드에서 동시에 접근이 가능한 자원, 때문에 오염될 위험이 높다.

위에서 말한 정수 변수는 비음수 정수이며, Down (P) 연산과 Up (V) 연산을 통해 해당 변수를 제어한다.

• Down(P) : 세마포어의 값이 양수가 될 때까지 기다린 후 값을 1만큼 감소시킨다(공유자원에 접근을 제한 하는 함수로 생각하면 된다).
• Up(V) : 세마포어의 값을 1만큼 증가시키고, 대기 중인 쓰레드가 있다면 하나를 깨운다(공유자원에 접근이 가능하도록 제한을 푸는 함수로 생각하면 된다).

예를 들면, 쓰레드 A, B가 실행이 되는데 A는 B가 완료 될때까지 대기했다가 실행을 하고 싶다.
그럼 세마포어가 0으로 초기화 되었다면 쓰레드 A가 Down을 실행하며 어 0이네? 하고 대기상태가 되고, B는 본인의 작업 완료 후 Up을 실행하며 1을 만들고 대기중이던 A를 깨운다.

물론 0 외에 다른값으로도 초기화가 가능하다.

1로 초기화 된 세마포어는 보통 자원에 대한 접근을 제어하기 위해 사용된다.
공유자원에 접근하기 전, 0으로 바꾸면서 다른 쓰레드의 접근을 막고, 나가면서 1로 증가시켜 접근 가능하도록 한다. 이 경우는 아래에서 lock으로 설명하고 있다.

1보다 더 큰 값으로도 초기화가 가능하지만, 이 경우는 매우 드물다.

다음은 pintOS에서 사용하는 세마포어의 구현이다.

• 세마포어를 표현하는 구조체로, 세마포어 값과 대기중인 쓰레드 목록을 포함한다.

  struct semaphore
  

• 주어진 초기값으로 세마포어를 생성 및 초기화 한다.

  void sema_init(struct semaphore *sema, unsigned value)
  

• Down(P) 연산을 수행한다.

  void sema_down(struct semaphore *sema)
  

• Down(P) 연산을 시도한다. 위 함수와 다른 점은 0일 경우 대기하지 않고 false를 반환하고 가능하면 true를 반환한다. 이 함수는 CPU시간을 낭비하니 비추.

  void sema_try_down(struct semaphore *sema)
  

• Up(V) 연산을 시도한다.

  void sema_up(struct semaphore *sema)
  

  기억할 점은 외부 interrupt handler에서도 해당 함수를 사용할 수 있다는 점이다.

Locks

위에서 말했듯이 Lock은 초기값이 1인 세마포어이며, Lock에서의 Up 연산은 release이고, Lock에서의 Down 연산은 acquire이다.
세마포어와 비교해서 규칙이 하나 추가되는데, lock을 aquire한 쓰레드만이 release할 권한이 있다는 것이다.
핀토스에서 사용하는 lock은 lock을 획득한 쓰레드가 다시 lock을 획득하려고 하면 오류가 발생하여 재귀를 방지한다.

다음은 pintOS에서 lock을 구현한 방법이다.

• lock을 생성하고 초기화 하며, 초기에는 어떤 쓰레드에게도 소유되지 않는다.

  void lock_init(struct lock *lock)
  

• 현재 쓰레드가 락을 획득하도록 한다. 만약 다른 쓰레드가 소유중이라면 해제될 때까지 기다린다.

  void lock_acquire(struct lock *lock)
  

• 현재 쓰레드가 락을 획득하게 하려는건 같지만, 이미 소유되어있을 경우 기다리지 않고, false를 반환한다. 가능하다면 true를 반환한다. 마찬가지로 CPU시간을 낭비하니 비추.

  bool lock_try_acquire(struct lock *lock)
  

• 현재 쓰레드가 소유중인 락을 해제한다. 만약 소유하지 않은 쓰레드라면 오류가 발생한다.

  void lock_release(struct lock *lock)
  

• 현재 쓰레드가 지정된 락을 소유하고 있는지 확인한다. 현재 쓰레드의 소유 여부만 검사가능하며, 특정 쓰레드가 락을 소유하고 있는지 확인은 불가능 하다.

  bool lock_held_by_current_thread(const struct lock *lock)
  

Monitors

모니터는 lock과 조건 변수를 함께 묶어서 사용하여 더 높은 수준의 동기화를 제공하는 도구이다.
전반적인 과정은 비슷하다. 한 쓰레드가 공유자원에 접근하기 위해 락을 획득하고, 그 획득한 쓰레드는 모니터의 안에 있다. 라고 표현하며 데이터를 다 사용해서 나올 때 모니터 락을 해제하며 다른 쓰레드가 사용을 할 수 있게 해준다.
이제 다른 점은 조건변수가 함께 사용되기 때문에, A 쓰레드가 작업을 하다가 특정 조건이 만족되지 않음을 깨닫고 wait에 들어가게 되면, 락은 해제되며 B쓰레드가 작업을 할 수 있게 된다. 그러다 A의 조건이 만족되었음을 알게 되면 signal(하나), broadcast(대기중인 모든 쓰레드)를 통해 다시 A가 락을 획득하고 모니터에 들어가게 되는 일련의 과정을 거친다.

다음은 monitors을 구현한 함수이다.

• 조건 변수를 나타내는 구조체 이다.

  struct condition
  

• 주어진 cond를 새로운 조건 변수로 초기화 한다.

  void cont_init (struct condition *cond)
  

• 조건 변수 cond를 기다리는 함수로 먼저 주어진 lockd을 자동으로 해제하고, cond가 신호를 받을 때 까지 기다린다. 신호를 받게 되면 다시 lockd을 획득하고, 함수가 리턴된다.
  함수가 리턴 된 이후에도 대기중이던 조건이 만족되지 않을 가능성이 있기 때문에, 조건을 다시 확인하고 필요하면 다시 대기할 필요가 있다.

  void cond_wait (struct condition *cond, struct lock *lock)
  

• cond 조건 변수에서 대기중인 스레드 하나를 깨우는 함수로 대기중인 스레드가 없다면 아무일도 일어나지 않는다. 또한 lock을 획득한 상태에서만 함수를 호출해야한다.

  void cond_signal(struct condition *cond, struc lock *lock)
  

• cond 조건 변수에서 대기중인 모든 쓰레드를 깨운다. 마찬가지로 lock을 획득한 상태에서 호출해야 한다.

  void cond_broadcast(struct condition *cond, struct lock *lock)
  

Optimization Barrirers

최적화 장벽이란 컴파일러가 코드를 해석할 때 특정 구역의 메모리 상태를 가정하지 못하도록 하는 특수한 명령어이다.
컴파일러는 보통 코드의 실행순서를 바꾸거나 최적화를 하려 하지만, 장벽이 있는 경우 이를 넘어서 최적화를 할 수 없다.

최적화 장벽을 쓰는 이유는 다른 쓰레드나, interrupt 핸들러에 의해 데이터가 비동기적으로 변경 될 수도 있기 때문이다.
예를 들어

int64_t start = ticks;
while(ticks == start)
    barrier();

만약 최적화 장벽이 없다면 컴파일러는 처음 start와 ticks가 같고 while문은 이를 변화시키지 않기 때문에 loop가 절대 종료되지 않을거라 결론짓고, 최적화를 통해 해당 함수를 무한 루프로 만들어버릴 수도 있다.

또한 유효한 결과를 내지 않는 함수를 임의로 삭제해버리지 않도록 막기 위해서도 사용되며, 메모리의 읽기 쓰기 순서를 보장하기 위해서도 사용한다.

컴파일러는 외부에서 정의된 함수를 호출할 때는 이를 일종의 최적화 장벽으로 간주하기 때문에 명시적으로 barrier()을 사용하지 않고, 외부 함수 호출을 통해 필요한 최적화 제한을 사용하기도 한다.

참고 : pintos-kaist