개발 공부

손승열(Son Seungyeol)

[운영체제][OSTEP] 병행성과 쓰레드

병행성과 쓰레드에 대해 공부해봅니다.

손승열(Son Seungyeol)
[운영체제][OSTEP] 병행성과 쓰레드

🚪 들어가며

쓰레드(thread): 어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위
➡️ 프로그램 카운터(PC)와 연산을 위한 레지스터들을 가짐.

멀티 쓰레드 프로그램
➡️ 하나 이상의 실행 지점(여러 개의 PC 값)을 가짐.
➡️ 각 쓰레드는 프로세스와 매우 유사하지만, 쓰레드들은 주소 공간을 공유하므로 동일한 값에 접근 가능
➡️ 쓰레드마다 스택이 할당되어 있음.(아래의 예시 그림을 참고하자.)

Single-Threaded Address Space    Multi-Threaded Address Space
 
 0 KB ┌──────────────┐             0 KB ┌──────────────┐
      │ Program Code │                  │ Program Code │
 1 KB ├──────────────┤             1 KB ├──────────────┤
      │     Heap     │                  │     Heap     │
 2 KB ├──────────────┤             2 KB ├──────────────┤
      │       │      │                  │              │
      │       │      │                  │    (free)    │
      │       ↓      │                  │              │              
      │    (free)    │                  ├──────────────┤
      │       ↑      │                  │   Stack (2)  │
      │       │      │                  ├──────────────┤
      │       │      │                  │    (free)    │
15 KB ├──────────────┤            15 KB ├──────────────┤
      │     Stack    │                  │   Stack (1)  │
16 KB └──────────────┘            16 KB └──────────────┘

💾 스택에서 할당되는 변수들이나 매개변수, 리턴 값, 그리고 그 외에 스택에 넣는 것들은 해당 쓰레드의 스택인 쓰레드-로컬 저장소(thread-local storage)에 저장된다.

⚠️ 쓰레드-로컬 저장소로 인해 주소 공간의 배치가 무너짐.
➡️ 스택의 크기가 아주 크지 않아도 되므로 대부분의 경우에는 문제가 되지 않음.
➡️ 그러나 재귀 호출을 아주 많이 한다면...🌀

💡 두 개의 쓰레드가 하나의 프로세서에서 실행 중인 경우
➡️ 실행하고자 하는 쓰레드는 반드시 문맥 교환(context switch)을 통해서 실행 중인 쓰레드와 교체되어야 함.

쓰레드 제어 블럭(thread control block, TCB): 쓰레드들의 상태를 저장
➡️ 프로세스 제어 블럭(PCB)와 유사
➡️ 프로세스 문맥 교환과 달리 쓰레드 간의 문맥 교환 시 주소 공간을 그대로 사용(사용하고 있던 페이지 테이블을 그대로 사용)

1️⃣ 예제: 쓰레드 생성

쓰레드1은 "A"를 출력하고, 쓰레드2는 "B"를 출력하는 독립적인 두 개의 쓰레드를 생성하는 프로그램을 실행시키는 상황을 가정해보자.

코드는 다음과 같다.

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

void *mythread(void *arg) {
  printf("%s\n", (char *) arg);
  return NULL;
}

int main(int argc, char *argv[]) 
{
  pthread_t p1, p2;
  int rc;
  printf("main: begin\n ");
  rc = pthread_create(&p1, NULL, mythread, "A");
  assert(rc &=& 0);
  rc = pthread_create(&p2, NULL, mythread, "B");
  assert(rc &=& 0);
  // 종료 할 수 있도록 대기 중인 쓰레드 병합하기
  rc = pthread_join(p1, NULL); assert(rc &=& 0);
  rc = pthread_join(p2, NULL); assert(rc &=& 0);
  printf("main: end\n");
  return 0;
}

동작은 다음 순서와 같다.

  1. main()은 mythread()를 실행할 두 개의 쓰레드를 생성

  2. 각 mythread()는 서로 다른 인자를 전달 받음.

    1. 스케줄러의 동작에 따라 쓰레드는 생성 후 즉시 실행되거나, 준비(Ready) 상태에서 실행은 되지 않을 수 있음.

  3. 두 개의 쓰레드 생성 후 메인 쓰레드는 pthread_join()을 호출하여 특정 쓰레드의 동작 종료를 대기

위 프로그램의 가능한 실행 순서는 다음과 같을 수 있다.

  • main() ➡️ 쓰레드1 생성 ➡️ 쓰레드2 생성 ➡️ 쓰레드1 실행 ➡️ 쓰레드 2실행 ➡️ 종료

  • main() ➡️ 쓰레드1 생성 ➡️ 쓰레드1 실행 ➡️ 쓰레드2 생성 ➡️ 쓰레드 2실행 ➡️ 종료

  • ...

이외에도 쓰레드 1과 쓰레드 2가 순서대로 생성 되었더라도 스케줄러가 쓰레드2를 먼저 실행하면 "B", "A" 순서로 출력되는 경우가 있을 수 있다.

쓰레드 생성 vs. 함수 호출

함수를 호출하는 경우, 함수 실행 후 호출자(caller)에게 리턴

쓰레드를 생성하는 경우, 실행할 명령어들을 갖고 있는 새로운 쓰레드가 생성되고, 생성된 쓰레드는 호출자와 별개로 실행

어떤 쓰레드가 언제 실행되는지 알기 어려움.

2️⃣ 훨씬 더 어려운 이유: 데이터의 공유

전역 공유 변수를 갱신하는 두 개의 쓰레드에 대한 예시를 살펴보자.

코드는 다음과 같다.

c
#include <stdio.h>
#include <pthread.h>
#include "mythreads.h"

static volatile int counter = 0;

// mythread()
// 반복문을 사용하여 단순히 1씩 더하기
// 10,000,000을 변수 counter에 더하는 방법이 아니다.
// 하지만, 문제가 무엇인지 명확하게 해준다.
void *mythread(void *arg) {
  printf("%s: begin\n", (char *) arg);
  int i;
  for (i = 0; i < 1e7; i++) {
    counter = counter + 1;
  }
  printf("%s: done\n", (char *) arg);
  return NULL;
}

// main()
// 두 개의 쓰레드를 실행하고 (pthread_create)
// 대기한다 (pthread_join)
int main(int argc, char *argv[])
{
  pthread_t p1, p2;
  printf("main: begin (counter = %d)\n", counter);
  Pthread_create(&p1, NULL, mythread, "A");
  Pthread_create(&p2, NULL, mythread, "B");
  
  // 쓰레드가 종료할 수 있도록 대기 중인 쓰레드를 병합한다
  Pthread_join(p1, NULL);
  Pthread_join(p2, NULL);
  printf("main: done with both (counter = %d)\n", counter);
  return 0;
}

위의 코드에서 Pthread_create()는 단순히 pthread_create()를 호출하고 리턴 값이 0인지 확인한다. 0이 아닌 경우 에러 메시지를 출력하고 종료한다.(Pthread_join()도 마찬가지이다.)

각 작업자 쓰레드는 반목문 안에서 공유 변수인 counter에 수를 천만 번(1e7)더한다.
➡️ 최종적으로 얻으려는 값은 20,000,000이다.

우리가 기대한 실행 결과는 다음과 같다.

prompt> gcc −o main main.c −Wall −pthread
prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 20000000)

하지만 단일 프로세서라 하더라도 때로는 아래와 같은 결과를 얻는다.

prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 19345221)

🤔 도대체 무슨 일이 벌어진 건지 알아보자.

3️⃣ 제어 없는 스케줄링

왜 위와 같은 현상이 발생하는지 이해하려면 counter 갱신을 위해서 컴파일러가 생성한 코드의 실행 순서를 이해해야 한다.

x86에서 counter를 증가하는 코드의 순서는 다음과 같다.

mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c

이 예제에서 사용하는 counter 변수의 위치의 주소는 0x8049a1c라고 가정한다.

💡 이제 어떻게 문제가 발생하는지 살펴보자.

  1. 쓰레드1이 counter를 증가시키는 코드 영역에 진입한다.

  2. counter의 값이 50이었다고 가정하면, 50을 eax레지스터에 넣는다.

    1. 쓰레드1에 있어서 eax=50이 된다.

  3. 레지스터의 값에 1을 더하여 eax=51이 된다.

  4. 타이머 인터럽트가 발생하여 운영체제가 실행 중이 쓰레드의 현재 상태를 쓰레드의 TCB에 저장한다.

  5. 쓰레드2가 선택되어 counter를 증가시키는 똑같은 코드 영역에 진입한다.

  6. counter의 값은 아직 50이므로 첫 번째 명령어 실행 결과 쓰레드2의 eax 값은 50이다.

  7. eax 값을 1 증가시키고 다시 counter(주소 0x8049a1c)에 저장한다.

  8. 다시 문맥 교환이 발생하여 쓰레드1이 리턴하여 실행된다.

  9. 쓰레드1의 eax 값은 51이므로 레지스터의 값을 counter에 저장하면 값은 51이 된다.

즉, counter의 값을 증가시키는 코드가 두 번 수행이 되었지만 counter의 값은 1 증가했다.

💡 이 예시에서처럼 명령어의 실행 순서에 따라 결과가 달라지는 상황을 경쟁 조건(race condition)이라고 부른다.

💡 컴퓨터의 작동에서 일반적으로 발생하는 결정적 결과와 달리 결과가 어떠할지 알지 못하거나 실행할 때마다 결과가 다른 경우를 비결정적(indeterminate)인 결과라고 부른다.

💡 멀티 쓰레드가 같은 코드를 실행할 때 경쟁 조건이 발생하기 때문에 이러한 코드 부분을 임계 영역(critical section)이라고 부른다.
= 공유 자원을 접근하고 하나 이상의 쓰레드에서 동시에 실행되면 안되는 코드
➡️ 이러한 코드에서 필요한 것은 상호 배제(mutual exclusion): 하나의 쓰레드가 임계 영역 내의 코드를 실행 중일 때 다른 쓰레드가 실행할 수 없도록 보장

4️⃣ 원자성에 대한 바람

임계 영역 문제에 대한 해결책 1: 강력한 명령어 한 개로 인터럽트 발생 가능성을 원천적으로 차단

예를 들어 메모리 상의 위치에 어떤 값을 더해주는 다음과 같은 명령어가 있다고 해보자.

memory−add 0x8049a1c, $0x1

하드웨어는 위 명령어가 원자적(하나의 단위)으로 실행(전부 실행되거나 말거나)되는 것을 보장한다고 할 때, 인터럽트가 발생했다는 것은 명령어가 실행되지 않았거나 실행이 종료된 후라는 것을 의미한다.

위의 예시에서 우리는 아래의 코드가 원자적으로 실행되기를 원했다.

mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c

위의 명령어들을 하나의 명령어(위의 예시인 memory-add처럼)로 대신할 수 있다면 해결할 수 있지만, 일반적인 상황에서는 그러한 명령어가 없다고 봐야한다.
➡️ 병행성을 원하고 있는데 원자적으로 실행??? 😅

하드웨어적으로는 동기화 함수(synchronization primitives) 구현에 필요한 기본적인 어셈블리 명령어 몇 개만 필요하다.
➡️ 하드웨어 동기화 명령어와 운영체제의 지원을 통해 한 번에 하나의 쓰레드만 임계 영역에서 실행하도록 구성된 멀티 쓰레드 프로그램 작성 가능

5️⃣ 또 다른 문제: 상대 기다리기

병행성 문제 = 공유 변수 접근에 관련된 쓰레드 간의 상호 작용 문제

실제로는 하나의 쓰레드가, 다른 쓰레드가 어떤 동작으로 끝낼 때까지 대기해야 하는 상황도 빈번하게 발생
➡️ 프로세스가 디스크 I/O를 요청하고 응답이 올 때까지 잠든 경우 등

6️⃣ 정리: 왜 운영체제에서?

왜 이런 것들을 운영체제에서 다뤄야 할까?

운영체제는 최초의 병행 프로그램 & 그러한 운영체제 내에서 사용하기 위한 다양한 기법들이 개발

예를 들어 임의의 파일에 write()를 수행하여 데이터를 파일에 덧붙이려고 하는 두 개의 프로세스가 실행 중인 경우를 생각해 보자.

인터럽트가 언제든지 발생할 수 있으므로 공유 자료 구조(할당을 위한 비트맵 또는 파일의 inode)를 갱신하는 코드는 임계 영역이 된다.
➡️ 인터럽트가 처음 소개되었을 때부터 운영체제 설계자들은 운영체제가 어떻게 내부 구조를 갱신할 것인가에 대해 고민해 옴.

페이지 테이블, 프로세스 리스트, 파일 시스템 구조, 대부분의 커널 자료 구조들이 올바르게 동작하기 위해서는 적절한 동기화 함수들을 사용하여 조심스럽게 다루어져야 함.

📚 참고 문헌

Operating Systems: Three Easy Pieces ― 26: Concurrency: An Introduction

운영체제 아주 쉬운 세 가지 이야기 ― 29: 병행성: 개요

Made with React, Gatsby and DatoCMS by @smastrom

Contribute or star on GitHub

© 2022-2023 손승열 for 🅒🅞🅝🅣🅔🅝🅣🅢

모두 좋은 하루 보내세요! 😊