</>PatchNote
목록으로

2023-04-25

운영체제 #5 — 프로세스 동기화

Operating SystemOS 2023SynchronizationSemaphore

동기화는 여러 프로세스 또는 스레드가 동시에 동작할 때, 그들이 공유하는 데이터에 안전하게 접근하는 방법을 다루는 것이다.

Race condition

여러 프로세스나 스레드가 공유하는 데이터에 동시에 접근해서 값을 읽고 바꾸는 경우, 의도치 않게 최종 값이 잘못 결정되는 일이 생긴다. 어떤 프로세스가 값을 읽고 바꾼 뒤에 다른 프로세스가 읽으면 문제가 없다. 문제는 겹칠 때다.

여러 프로세스가 공유된 데이터에 동시에 접근해서 값을 바꾸려는 상황이 race condition이다. 이때 어느 프로세스가 마지막에 끝났느냐에 따라 잘못된 결과가 나타날 가능성이 있다. 이걸 막으려고 쓰는 게 synchronization이다. 나와 아무 상관 없는 일은 동기화할 필요가 없다. race condition이 안 생기니까.

한 번 증가하고 한 번 감소했으면 원래 값이 유지되어야 하는데, 각각이 따로 진행되면 증가만 반영되거나 감소만 반영될 수 있다. 원인은 interleaved execution이다. 실제로는 하나의 CPU가 여러 작업을 번갈아 실행해서 동시에 실행되는 것처럼 보이게 하는 기법이고, serializable execution의 반대말이다. 멀티태스킹이나 멀티스레딩에서 많이 쓰인다.

Critical section problem

문제를 정형화하면 이렇게 된다. n개의 프로세스가 데이터를 공유하고 있고, 각 프로세스는 그 데이터에 접근하는 code segment를 가지고 있다. 이걸 critical section이라고 한다. 어떤 프로세스가 critical section을 수행 중일 때 다른 프로세스는 자기 critical section을 수행하지 못하게 만들어야 한다. 어떻게 막느냐가 해결책이다.

해결책이 되려면 세 조건을 모두 만족해야 한다.

  • Mutual Exclusion — 프로세스 Pi가 자신의 critical section을 실행 중일 때 다른 프로세스들은 자기 critical section을 실행할 수 없다.
  • Progress — critical section에서 수행되고 있는 프로세스가 없고 들어가고 싶어 하는 프로세스가 있다면, 그 프로세스는 무작정 기다리지 않아야 한다. 아무도 안 들어가는데 나도 못 들어가는 상황이 생기면 안 된다.
  • Bounded Waiting — 어떤 프로세스 하나만 계속 기다리지 않도록 해야 한다. 기다리는 시간에 bound를 둔다.

첫 번째만 지키면 되는 게 아니냐 싶지만, 과도하게 막으면 처리량이 떨어진다. 아래 두 조건은 막긴 막되 성능이 저하되지 않게 하려고 추가된 것이다.

critical section을 가진 프로세스는 반드시 entry section(들어가도 되는지 확인)과 exit section(끝났다고 알림)을 가져야 한다. 이 두 섹션에는 프로세스 간에 서로의 상태를 공유하는 변수가 들어 있다.

소프트웨어 해법들

Algorithm 1 — turn만 쓰기

turn이라는 공유 변수를 둔다. turn = 0이면 P0의 차례, turn = 1이면 P1의 차례다.

mutual exclusion은 만족한다. turn은 한순간에 하나의 값만 가질 수 있기 때문이다. 그런데 progress를 불만족한다. P1이 끝나서 while(turn != 0)에서 대기 중일 때 P0가 remainder section을 수행하고 있으면, critical section에 있는 프로세스가 없는데도 아무도 못 들어간다. 두 프로세스가 반드시 한 번씩 번갈아야 하는(swap turn) 문제다.

Algorithm 2 — flag만 쓰기

들어갈 의지를 flag로 표현한다. true면 의지가 있다는 뜻이고, 상대방이 들어갈 마음이 없으면 들어간다. swap turn은 발생하지 않고 mutual exclusion도 만족한다.

그런데 여전히 progress를 불만족한다. 둘 다 flag = true인 상황에서 서로 양보해버려서 아무도 못 들어간다.

피터슨 알고리즘 — 둘을 합치기

1번은 들어갈 마음이 없는 프로세스에게 들어가라고 해서 생긴 문제였다(flag가 없어서). 2번은 둘 다 들어갈 마음이 있을 때 생긴 문제였다(누가 들어가라고 정해줄 turn이 없어서). 그래서 둘을 합친다.

entry section에서 들어가려는 의지를 표현하고(flag = true), turn을 상대에게 양보한다. 그리고 상대가 들어가려는 의지가 있고 동시에 상대의 차례일 때 무한 루프에서 대기한다. 즉 상대의 의지가 없거나, turn이 내 차례이기만 해도 빠져나올 수 있다. (조건이 and지 or가 아니라는 점을 조심해야 한다.)

swap turn도 발생하지 않는다. remainder section에 있는 프로세스는 flag = false라 의지가 없으므로 다른 프로세스가 들어갈 수 있다.

critical section의 해결책은 맞다. 그런데 더 나은 방법이 있다. 두 가지가 아쉽다.

  • Busy waiting — while문을 돌면서 기다린다. CPU를 쓰면서 기다린다는 뜻이다.
  • entry section이 너무 길다. 공유 데이터를 쓰는 모든 프로세스에 이 코드가 들어가야 해서 코드가 복잡해진다.

lock

더 나은 해결책은 lock(열쇠)이라는 개념을 쓰는 것이다. lock을 얻은 프로세스는 critical section을 수행할 수 있고 다른 프로세스는 대기한다. 반납하면 대기하던 프로세스가 받을 수 있다. lock을 얻고 반납하는 단순한 함수만 쓰면 되니 개발자 입장에서 편하다.

locking system이 제대로 동작하려면 세 가지 전제가 필요하다.

  1. 한 번에 하나의 프로세스만 lock을 가질 수 있다.
  2. 다른 프로세스가 lock을 가지려 하면 기다려야 한다.
  3. lock을 가진 프로세스만이 그 lock을 반납할 수 있다.

인터럽트를 끄는 방법

lock을 하나의 프로세스만 얻게 하는 방법이 뭘까. 만약 P0가 쭉 수행하고 P1이 쭉 수행한다면 아무 문제가 없다. critical section이 동시에 실행되는 일이 없기 때문이다. 그렇게 되지 않는 이유는 코어가 하나일 때 CPU 스케줄링에 의해 interleaved execution이 발생하기 때문이다.

그러면 코어가 하나인 경우 CPU 스케줄링만 막으면 된다. critical section에 진입하면 마칠 때까지 스케줄링이 일어나지 않게 하는 것이다. 스케줄링이 일어나는 경우는 time quantum이 다 되어 CPU를 넘겨줘야 하는 경우고(critical section에서는 I/O를 발생시키지 않는다고 봤다), timer는 I/O 디바이스로서 quantum이 끝나면 인터럽트를 보낸다. 그러니 timer interrupt를 disable시키면 된다. critical section 앞에서 끄면, 실행 중에 다른 프로세스가 critical section을 수행하는 일이 일어나지 않는다.

문제는 uniprocessor가 아닌 멀티코어에서는 쓸 수 없다는 것이다.

Atomic hardware — TAS와 Swap

general한 해법은 atomic hardware를 제공받는 것이다. 중간에 끊기지 않는 것을 보장하는 회로다. 함수를 실행하면 한 번에 끝까지 실행된다. 이걸 쓰는 명령어가 Test-and-Set과 Swap이다.

Test and Set(TAS) 은 target의 원래 값을 return하되 target을 true로 바꾼다. atomic하므로 이 함수를 실행하는 도중 다른 프로세스가 끼어들 수 없다.

// 개념적으로
boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

// 사용
while (TestAndSet(&lock)) ;   // entry section
//   critical section
lock = false;                 // exit section

lock은 처음에 false다. 첫 프로세스가 TAS를 부르면 lock은 true로 바뀌지만 return 값은 false라 while을 통과한다. critical section을 실행하는 동안 lock은 true다. 다른 프로세스가 TAS를 부르면 return 값이 true라 while을 돈다. exit section에서 lock을 false로 풀어주면 그때 빠져나온다.

TAS가 atomic하지 않다면 rv = false인 순간 둘 이상의 프로세스가 동시에 호출해서 모두 false를 return받을 수 있고, mutual exclusion이 깨진다.

Swap은 key라는 local 변수를 쓴다. lock은 똑같이 공유하고, key는 "나 들어가고 싶어"를 의미한다. Swap은 lock과 key 값을 바꾼다. 먼저 들어간 놈은 lock이 false, key가 true라서 통과하고, 중간에 들어온 놈은 lock과 key가 모두 true라 while에 머문다.

세마포어

하드웨어 없이 소프트웨어만으로 해결하려면 semaphore를 쓴다. 마찬가지로 entry/exit section에 쓸 primitive를 제공하려는 것이다. 정수형 semaphore 변수 하나와 거기 접근하는 두 함수를 쓴다.

  • P(S) (wait) — S가 0 이하면 대기한다. S가 0보다 커지면 1을 빼고 빠져나온다.
  • V(S) (signal) — S를 1 더하고 빠져나온다.

atomic hardware의 도움 없이 되는 이유는 P와 V가 atomic 함수이기 때문이다. 그러면 하드웨어 회로 없이 소프트웨어만으로 어떻게 atomic을 만드나. 코어가 하나면 P와 V의 위아래에서 각각 interrupt를 disable/enable해주면 된다. 코어가 여럿이면 피터슨 알고리즘을 쓴다. semaphore 변수 자체도 공유 변수이니, P와 V 함수 내부에 피터슨 알고리즘을 적용한다. 한 번만 만들어두면 나중에 쓸 때 계속 만들지 않아도 된다.

만약 P와 V가 atomic이 아니라면 두 개 이상의 프로세스가 P의 while문에 동시에 진입해서 동시에 통과할 수 있다.

block/wakeup 세마포어

세마포어 자체에도 busy waiting이 남아 있다. P 안의 while문에서 도는 대신 프로세스를 sleep시키자.

semaphore 변수를 int가 아니라 struct으로 만든다. 원래의 정수값은 int value에 넣고, struct proc을 가리키는 포인터를 추가한다. linked list가 된다.

  • P 함수 안에서 조건이 충족되지 않으면 block(sleep)하고 linked list에 추가한다.
  • critical section에서 나올 때 한 놈을 wakeup으로 깨운다.

S.value는 1로 초기화되어 있다. 첫 프로세스는 값이 0이 되므로 그냥 통과한다. 음수가 되면 linked list에 추가하고 block한다. |S.value|가 곧 큐의 길이다. 첫 프로세스가 critical section을 통과하고 V를 호출하면 value를 1 증가시키는데, 1이 아니라면 기다리는 놈이 있다는 뜻이므로 wakeup을 호출해 큐의 첫 프로세스를 깨운다. 1이면 기다리는 놈이 없다.

기다리는 프로세스의 수를 나타내면 integer semaphore, 그냥 기다리는 프로세스가 있다/없다 정도면 binary semaphore라고 한다.

while loop가 없으니 불필요하게 CPU를 쓰는 일이 없다. 그런데 단점이 없는 건 아니다. 프로세스를 block하고, linked list에 추가하고, wakeup하는 것 전부가 오버헤드다. critical section이 짧다면 오히려 while loop를 도는 게 더 빠를 수도 있다. 그래서 짧다는 보장이 있으면 일반 세마포어를, 아니면 block/wakeup 세마포어를 개발자가 선택해서 쓴다. 동시에 많은 프로세스가 돌고 있다면 전부 while loop를 도는 것보다 block/wakeup이 효과적이다.

성능만 보면 세마포어보다 atomic hardware가 낫다. 하드웨어가 atomic instruction을 제공한다면 locking system을 쓰는 게 좋고, 제공하지 않으면 세마포어를 쓴다.

lock과 semaphore의 차이

실습에서 — race condition이 무엇이고 lock과 semaphore가 왜 필요한지, 그리고 둘의 차이가 무엇인지 답하는 문제가 있었다.

race condition은 같은 공유자원에 접근하는 프로세스나 스레드가 여러 개 돌 때 interleaved하게 동작해서 serial하게 동작했을 때와 다른 결과가 나올 수 있는 경우다. lock과 semaphore는 critical section에서 발생하는 이 race condition을 막으려고 필요하다.

차이는 이렇다. lock은 하나의 프로세스만 공유자원에 접근하게 하고, semaphore는 숫자를 조절해서 여러 개가 접근하도록 할 수 있다. lock은 하나에게 주면 돌려받기 전까지 다른 프로세스가 접근할 수 없지만, integer semaphore의 값을 2로 조절하면 최대 2개가 접근할 수 있다.

당시에 정리한 비유가 롤러코스터였다. 한 자리에는 한 명만 앉을 수 있지만 여러 명이 한 롤러코스터에 탈 수 있다. 자리가 lock이고 롤러코스터가 semaphore다.

producer-consumer

소스코드를 주고 critical section을 찾아 이유를 설명하고 제거 방법을 제안하라는 문제도 나왔다. producer-consumer 코드였다.

num_items가 0일 때 consumer가 if문을 통과해버리면 인덱스만 하나 증가하고 버퍼 안의 값은 줄지 않는다. 반대로 num_items가 버퍼 크기와 같아지면 producer가 if문을 통과해서 인덱스만 증가하니, 의도한 50000개보다 적은 데이터가 생산되고 소비된다.

해결은 조건 변수를 쓰는 것이다. consumer 쪽에서는 버퍼가 비었으면 기다리다가 producer가 생산하면 깨어나고, producer 쪽에서는 버퍼가 꽉 찼으면 기다리다가 consumer가 소비하면 깨어나게 한다.

// consumer
while (num_items == 0)
    pthread_cond_wait(&not_empty, &mutex);

// producer
while (num_items == BUFFER_SIZE)
    pthread_cond_wait(&not_full, &mutex);

이 문제에서 배운 것 하나. race condition은 코드가 아닌 곳에서도 나올 수 있다.

OS 안에서 벌어지는 critical section 문제

커널 코드 자체가 공유 데이터를 만진다. 세 가지 경우가 있다.

(1) interrupt handling 코드를 수행할 때

커널 코드가 count++을 한다. 읽고, 증가시키고, 저장하는 과정이다. 증가시키기 전에 인터럽트가 오면 handling 코드로 점프하는데, 그 handler도 커널 코드라 커널 변수인 count에 접근할 수 있다. handler에서 감소시키고 끝난 뒤 돌아와서 증가를 마치면, 의도한 결과가 나오지 않는다. 양쪽에 interrupt disable/enable을 추가해서 해결한다.

(2) 프로세스 간 스케줄링에 의해서

시스템 콜을 수행하는 도중 스케줄링이 일어나면 다른 프로세스의 커널 코드가 같은 변수를 만질 수 있다. UNIX의 방식은 system call 수행 중에는 CPU 스케줄링이 일어나지 않도록 하는 것이다.

(3) CPU가 여러 개일 때

멀티프로세서에서는 interrupt disable/enable이 효과가 없다. CPU 하나의 인터럽트를 막는 것이지 다른 CPU에는 영향을 못 미치기 때문이다.

한 가지 방법은 OS 커널 자체를 하나의 거대한 critical section으로 취급하는 것이다. 한 CPU에서 커널 모드로 실행 중이면 다른 CPU에서는 커널 모드로 실행하지 못하게 한다. 시스템 콜을 한 번에 하나씩만 하는 식이다. 그러면 그동안 다른 CPU에서 돌던 프로세스가 시스템 콜을 호출해도 실행할 수 없다. 성능상 큰 문제고, CPU를 늘려도 과도한 block 때문에 그만큼의 효과를 못 본다.

다른 방법은 커널 변수 하나하나에 synchronization tool을 적용하는 것이다. 복잡하지만 성능은 더 낫다. 뭘 선택할지는 OS vendor가 결정한다.

xv6의 sleep과 spinlock, 그리고 데드락

실습에서 — xv6의 sleep이 왜 spinlock 구조체를 필요로 하는지를 묻는 문제가 있었다.

sleep 함수에서 lock을 얻지 않고 상태를 sleep으로 바꾼다면, sleep하는 도중에 ptable에서 선택되어 프로세스가 진행될 수도 있다. 그래서 lock이 필요하다.

acquiresleep, releasesleep이 필요한 이유는, sleep하는 도중에 이 프로세스가 쓰는 공유자원을 다른 프로세스가 건드리는 것을 막기 위해서다. 공유자원 A를 쓰는 프로세스 i가 sleep 상태가 되었는데 이를 공유하는 프로세스 j가 값을 바꾸면, i가 쓰던 값과 달라진다.

데드락

같은 실습에서 데드락이 있는 코드를 주고 어떻게 제거했는지, 그리고 데드락의 조건에 비추어 이유를 설명하라는 문제가 나왔다.

send와 recv가 mutex라는 자원을 공유하는데, 강제로 뺏을 수 없고(no preemption), 하나가 가지고 있으면 놓지 않고(hold and wait), 둘 중 하나만 쓸 수 있으니(mutual exclusion) 원형 대기가 일어난다. 해결은 hold and wait를 하지 않는 것이다. 쓸 수 없다면 놓아주는 식으로 만들면 된다.