5. 프로세스 동기화(1/2)
이 글은 다음의 강의를 수강하여 정리 및 복습하는 글임을 밝힙니다.
http://kocw.or.kr/home/cview.do?mty=p&kemId=1223639&ar=relateCourse
시스템 프로그래밍 기초
이 교과목은 컴퓨터 하드웨어 시스템과 운영체제 기반에서 프로그래밍 언어를 어떻게 사용하는지에 관한 기초에 대해서 학습한다.
www.kocw.net
멀티 프로세스가 돌아가는 경우에
다음처럼 두 개의 스레드가 있다고 합시다. 두 개의 스레드는 서로 영향을 주지 않습니다. 이를 no dependency (의존성이 없다) 라고 부릅니다. 그래서 스레드가 돌면서 context switching 이 발생해도 서로 문제가 발생하지 않습니다.
그러나 다음의 경우를 보시겠습니다.
y의 초기값은 8인 경우에 두 프로세스가 동작한다고 가정해봅시다.
그러면 스레드 A는 x = 1 로 초기화를 진행하고 x = y(=8) + 1 연산을 진행하고 x = 9의 값을 가집니다. 그 후 context switching 이 일어나 스레드 B가 실행되고, y = 3으로 초기화한 후 연산을 진행하여 y = 5 라는 값을 가지게 됩니다.
여기까지는 문제가 없습니다. 근데, 다음의 경우는 어떻게 될까요?.
y = 1 이 실행되고 난 후 context switching 이 발생하는 경우입니다.. 그림을 다시 그리면 이렇게 될 겁니다.
그러면 우리가 y의 초기값을 8로 지정했다 하더라고 y = 3이 되고, x의 값은 4가 됩니다. 즉 context switching이 언제 발생하는가? 이에 따라서 x와 y의 결과가 달라집니다.
Concurrency Problem
위에서 확인한 문제를 해결하기 위해서는 3가지의 용어를 알아야합니다.
1. Synchronization (동기화) : 우리가 원할 때 원하는 결과를 낼 수 있도록 해야합니다.
2. Critical section : 중간에 context switching이 발생하면 안되는 부분으로 critical section은 동작의 시작부터 완료까지 중간에 끊기지 않도록 보장되어야합니다.
3. Mutual exclusion (상호배제) : 기계적으로 Critical section을 만들어주는 것을 말하며, Mutex(뮤텍스)라고 줄여서 부릅니다.
Atomic Operations
더이상 쪼갤 수 없는 부분이라고 생각하면됩니다. Atomic operations 은 중간에 멈출 수 없으며, 중간에 상태가 바뀔 수 없습니다. chatgpt의 추가적인 설명에 의하면
atomic operation은 데이터의 원자적인 읽기와 쓰기에 사용되며,
critical section은 여러 스레드 또는 프로세스 간에 공유 데이터에 대한 안전한 접근을 보장하기 위한 코드 영역입니다.
Atomic operation은 하드웨어에서 지원되는 원자적인 연산이며,
critical section은 소프트웨어 수준에서 동기화를 필요로 합니다.
Too much milk problem
동기화가 제대로 이루어지지 않을 경우에 발생하는 문제를 설명하는 가장 유명한 예시입니다.
Too much milk problem - 나무위키 (namu.wiki)
Too much milk problem - 나무위키
Too much milk problem 운영체제가 오랫동안 작업할 경우 발생할 수 있는 문제. 다중CPU 관련. 동시에 발생한 작업 사이에 동기화가 제대로 안 됐을 경우 어떤 문제가 발생하는지 보여준다. 1. 철수가 냉
namu.wiki
1. 철수가 냉장고를 열어보니 우유가 없다. 철수가 우유를 사러 간다.
2. 영희가 냉장고를 열어보니 우유가 없다. 영희가 우유를 사러 간다.
3. 철수가 우유를 사온다.
4. 영희가 우유를 사온다.
5. 이제 우유가 너무 많다.이를 어떻게 해결해야할까요?
solution 1, Too much milk problem
노트를 사용하는 방법이 있을 것입니다. Thread A는 우유를 사러나간다면 냉장고에 노트를 붙여 Thread B가 우유를 사러가지않게 하는 것입니다.
if (milk == 0)
{
if (note == 0)
{
note = 1;
buyMilk();
note = 0;
}
}노트가 붙어있지 않다면, 노트를 붙이고 (1로 만들고) 우유를 사러갑니다. 해당 방법은 효율적인 방법이라 생각되지만 실제로는 문제를 해결하지 못합니다. 예시를 보시겠습니다.
두 개의 스레드가 위와 같은 코드를 사용합니다.
context swtiching이 코드 중간에 일어난다고 생각을 해봅시다.
우유가 없네? 라고 생각한 순간 context switching이 일어나 Thread B도 우유가 없다고 판단해버립니다. 그러면 여전히 두 스레드는 우유를 사러갑니다.
solution 2, Too much milk problem
서로 다른 노트를 사용하게 하자.
이는 완벽한 해법일까? 아니다.. 다음의 예시를 보자.
ThreadA가 노트를 냉장고에 붙이자 마자, context swtiching이 발생했다. 그러면 ThreadB도 노트를 냉장고에 붙이고 Thread B는 우유를 사지 않는다. context swtiching이 발생하여 Thread A가 이제 시작하려고 보니까 Thread B가 노트를 붙여놓은 것을 보고 우유를 사지 않는다. 결과적으로 아무도 우유를 사러가지 않을 수 있다.
solution 3, Too much milk problem
노트를 각자 붙이는대신, Thread A가 노트를 붙였다면 Thread B는 A가 노트를 땔때까지 기다리게하자.
이는 문제를 확실하게 해결할까? -> 답은 그렇다. 그러나 이 또한 문제가 있다.
Thread A와 Thread B는 서로 같은 일을 하는 코드다.. 그런데, 두 코드는 서로 다르다.. 이를 Asymmetric code (비대칭)코드라고 부른다. 또한 Thread B는 CPU가 찾아와도 무작정 기다리기만한다. 이를 Busy-waiting 이라고 한다. 하나만 기억하자면 CPU는 절대 놀면안된다.
solution 4, Too much milk problem
Lock (좌물쇠)로 잠궈버리는 방법이 있다.
그래서 좌물쇠로 잠그는 역할은 Acquire(), 푸는 역할은 Release() 로 Thread A가 좌물쇠를 잠그면 Thread B가 좌물쇠로 잠그려고 할 때, 좌물쇠를 획득?하지 못하므로 잠글 수 없고 waiting 하게된다. 그래서 결론적으로
표시한 부분은 Critical Section으로 보호받을 수 있다. 여기서 한 가지만 더 들어가보자면, Acquire()와 Release()가 호출되고 돌아가는 동안에는 context switching이 발생하면 안된다. 이의 동작을 보장하기 위해 atomic operations로 구현되어야한다.
Locking Mechanism
Lock (좌물쇠)는 공유하는 데이터에 접근하거나, critical section으로 들어가기 전에 Lock을 합니다. 그리고 모든 작업 종료되었을 때, Unlock을 합니다. waiting과 synchrnization이 주요 키워드입니다.
그래서 Locks에는 두 가지 Atomic fuction을 가집니다. acquire()와 release() atomic function이기 때문에 context switching이 발생해서는 안됩니다.
Implementation of Locks
Lock을 구현하기 위해서 가장 먼저 생각해볼 수 있는 것은 interrupt를 비활성화하여, context switching을 비활성화시키는것입니다.
코드를 먼저 확인해봅시다.
Acquire()
{
disable interrupts;
}
Release()
{
enable interrupts;
}
Acquire()
if (milk == 0){
buyMilk();
}
Release();
일단 여러 생각을 잠시 뒤로 미루고, 조금 더 깊게 들어가보겠습니다.
boolean Lstate = FREE; //FREE = 0
Acquire()
{
disable interrupts;
if (Lstate == LOCKED)
{
put thread on wait queue;
go to sleep();
}
else
{
Lstate = LOCKED; //LOCKED = 1
}
enable interrupts;
}먼저 Acquire 함수에 대한 내용입니다.
우선 코드를 해석하면서 가봅시다.
1. 스레드가 좌물쇠를 요청(Acquire)합니다.
2. interrupt를 비활성화합니다.
3. 만약 Lstate(Lock state)가 잠겨 있는 경우 (다른 스레드가 좌물쇠를 획득한 경우) wait queue(대기열)에 들어갑니다.
4. 그리고 sleep합니다.
5. 만약 잠겨있지 않는 경우에 Lstate를 LOCKED로 변경한 이후에 인터럽트를 활성화합니다.
(잠시만 다시... 우리는 지금 Acquire 부분을 하고 있으며, 이는 Atomic function임으로 Acquire를 통해 Lock을 얻는 동안은 인터럽트를 비활성화시키자는 부분을 하고 있다)
Release()
{
disable interrupts;
if (anyone on wait queue)
{
take thread off wait queue;
put thread on ready queue;
}
else
{
Lstate = FREE;
}
enable interrupts;
}Release의 경우에
1. 인터럽트를 비활성화합니다.
2. 만약 wait queue에서 기다리는 스레드가 있다면 wait queue에서 기다리고 있는 스레드를
3. Ready queue로 넣어줍니다.
4. 그리고 Lstate를 FREE로 바꿔주고
5. 인터럽트를 활성화합니다.
이와 같은 동작을 하게 할 것입니다. 그래서 다시 코드를 살펴보면
빨간색으로 표시된 부분이 Critical Section입니다. 가능하면 이 부분이 굉장히 짧아야할 것입니다.
잠시 하나만 생각을 해봅시다. Acquire에서
boolean Lstate = FREE; //FREE = 0
Acquire()
{
disable interrupts;
if (Lstate == LOCKED)
{
put thread on wait queue;
go to sleep();
}
else
{
Lstate = LOCKED; //LOCKED = 1
}
enable interrupts;
}interrupt를 비활성화하고나서 sleep에 들어갑니다. 근데, 비활성화가 되었으니까, interrupt를 다시 활성화를 해줘야합니다. 이 경우 어떻게 interrupt를 활성화할 수 있을까요
그래서 다음처럼 활용됩니다.
Thread A가 비활성화하고 잠에 들면, context switching으로 잠에서 깨어난 Thread B가 interrupt를 활성화합니다. 이런식으로 서로 티키타카를 하면서 주고받게됩니다.
이처럼 인터럽트를 통해 구현하는 과정에는 문제가 있습니다. 멀티 프로세스 환경에서 이와같은 방법은 좋지 않습니다.
memory read-write instructions를 기초로 하는 좌물쇠의 예시들입니다.
1. 공유하는 메모리를 Read하고 Write하는 과정
2. Test_and_set instruction
3. Compare_and_swap instruction
Test and Set Instruction
boolean test_and_set (boolean *target)
{
boolean val = *target;
*target = TRUE;
return val;
}간단한 동작입니다. target의 값을 val의 값에 저장해서 target을 TRUE로 바꿔주고 val을 출력합니다.
그래서 두 가지 경우가 있습니다.
1. target의 값이 0인 경우
- val = 0
- target = 1
- return 0;
1. target의 값이 1인 경우
- val = 1
- target = 1
- return 1;
위의 방법을 활용한 예시를 살펴보자면
boolean Lstate = FREE; //FREE = 0
do
{
while (test_and_set(&Lstate));
Lstate = FREE;
} while(LOCKED); // LOCKED = 1우선 LOCK이 busy하다면 대기를 합니다. return이 1이므로 while문에 빠지게됩니다.
그러다가 LOCK이 FREE가 되면 0을 return 받으므로 Lstate를 FREE로 바꾸고 FREE이므로 while(LOCKED) 를 탈출할 수 있게됩니다. LOCK를 획득하고
그래서 이를 활용해서 Acquire와 Release를 구현하면 이렇게됩니다.
boolean guard = FALSE;
boolean Lstate = FREE;
Acquire()
{
while (test_and_set(&guard));
if (Lstate = LOCKED)
{
put thread on wait queue;
go to sleep();
}
else
{
Lstate = LOCKED;
}
guard = FALSE:
}guard가 앞에서 보았던 target입니다. guard라고 이름 붙인 이유는 critical section을 보호하기 위함입니다.
1. gruad가 0이면 while을 빠져나갑니다.
2. Lstate가 LOCKED이면 (1이라면) wait queue로 가서 sleep합니다.
3. 만약 FREE라면 Lstate를 LOCKED 합니다 (1로 바꿉니다)
4. guard를 FALSE로 바꿉니다 (0으로 바꿉니다.)
Release()
{
while (test_and_set (&guard));
if (anyone on wait queue)
{
take thread off wait queue;
put thread on ready queue;
}
else
{
Lstate = FREE;
}
guard = FALSE;
}앞의 interrupt와 동일한 코드입니다. test_and_set에서 guard가 FALSE 되어야만 while을 빠져나옵니다.
test_and_set으로 변경시에 interrupt를 사용하지 않는다는 장점이 생기지만 아직 while에서 스레드가 기다리는 (busy waiting)은 해결하지 못했습니다.
interrupt를 사용할 때는 Acquire() 과정에서 interrupt를 막아 content switching을 불가능하게 만들어 CPU를 독점합니다. 그래서 multi processor에서 사용이 어렵다는 단점이 있었습니다.
그러나 test_and_set은 interrupt를 사용하지 않게 구현하는 것이 가능했지만, busy waiting을 막아내지는 못했습니다.
compare and set instruction
이는 두 값을 비교하는 방식이라고 하며, 짧게 언급이되어 있어 일단 넘어가겠습니다.