· 목차
- Race Condition
- Critical Region(or Critical Section)
- Critical Section Problem Requirement
- Busy Waiting
- Spin lock
- Peterson's solution
- TSL(Test and Set Lock)
- Sleep and Wakeup
- Semaphores(PV operation)
안녕하세요, 이번에는 Synchronization에 대해서 알아보도록 하겠습니다.
Synchronization이 중요한 이유를 말하자면, 프로세스나 스레드의 Race Condition을 방지하고,
데이터의 일관성을 유지하기 위해서 입니다.
그렇다면 Race Condition이 무엇이길래 방지해야 하는 것일까요?
Race Condition
Race Condition이란 여러 프로세스나 스레드가 동시에 데이터에 접근하고, 수정하려고 할 때 발생하게 됩니다.
예를 들어서, 두 스레드가 동시에 은행 계좌의 잔액을 업데이트하면 잔액이 잘못되는 문제가 생기게 됩니다.
예시
스레드 A: 잔액 읽기 → 10000원
스레드 B: 잔액 읽기 → 10000원
스레드 A: 5000원 인출 후 저장 → 5000원
스레드 B: 4000원 인출 후 저장 → 6000원
위의 예시를 보면, 스레드가 동시에 잔액에 접근하고 인출로 계좌의 잔액을 수정하게 되면 문제가 발생하게 됩니다.
위의 문제들로 인해서 데이터의 일관성이 깨지게 되고, 일관되지 않는 데이터를 가지게 됩니다.
그렇다면 어떤 것들이 공유자원이 될까요?
여기서 공유자원이라는 것은 동시에 접근 가능한 데이터를 말합니다.
공유자원에는 Global variable과 Dynamic object들이 있습니다. 여기서 local variable은 공유자원이 아닙니다.
왜 그런지는 아래의 그림을 보시면 이해가 쉽습니다.
그림을 보면, Stack 영역에서 Thread3개가 각자의 stack 영역을 가지고 있습니다. 그렇기 때문에 스레드의 local variable은
서로 공유되지 않고 각자 가지고 있기 때문에 공유자원이 아닙니다.
Global variable의 경우에는 Static data(data segment)영역에 저장되기 때문에 서로 공유가 가능하다는 것을 알 수 있습니다.
마찬가지로, Dynamic Object는 heap 메모리 영역에 저장되기 때문에 서로 공유가 가능하다는 것을 유추할 수 있습니다.
이제 그럼 서로 상호배제적으로 공유자원에 접근해야 한다는 것은 알 수 있습니다.
Critical Region(or Critical Section)
상호 배제적(mutual exclusio, mutex)으로 공유자원에 접근하기 위해 Critical Region이라는 개념이 있습니다.
위 그림은 Critical Region에 대한 그림으로, Process A가 Critical Region안에 있을 때, Process B는 기다리게 됩니다.
만약에 Process A가 Critical Region에서 일을 다 하게 된다면, 다른 Process가 Critical Region에 들어갈 수 있게 됩니다.
앞서 이미 말했듯이, 이렇게 공유자원인 Critical Region에 접근할 때, 문제가 발생하게 되는데,
해당 문제를 살펴보고 개선하기 위한 방법들에 대해서 살펴보도록 하겠습니다.
Critical Section Problem Requirement
Critical Region 문제를 해결하기 위해서는 아래와 같은 문제들이 해결되어야 합니다.
1. Mutual exclusion(mutex)
Critical region에는 하나의 프로세스 또는 스레드만 들어가야 한다.
2. Bounded waiting(no starvation)
프로세스나 스레드가 Critical Region에 계속해서 못들어가면 안되고, 무조건 들어갈 수 있어야 한다.
3. Progress
만약 스레드 A가 Critical region의 entry에서 기다리고 있는 상태에서 다른 스레드 B가 Critical region에 들어가기 위한 시도를
막아서는 안된다는 것 입니다.
즉, 시스템은 Critical Region에 스레드가 없을 때, 시스템은 멈추지 않고 다음에 들어갈 스레드를 결정해야 하며 계속해서 대기
상태에 있어서 starvation되는 일은 없도록 해야 합니다.
4. 임계구역 문제의 요구사항 중에서 CPU 속도나 CPU 개수에 대한 가정이 없어야 한다는 것으로, 시스템의 환경에 따라서
동기화가 작동하거나 안되거나 하는 상황이 발생하면 안된다는 것 입니다.
이제 해당 Critical Region의 문제를 해결하기 위해서 고안된 방법들에 대해서 살펴보도록 하겠습니다.
Busy Waiting
Mutual Exclusion은 여러 프로세스나 스레드가 동시에 Critical Region에 접근하지 못하도록
보장하는 중요한 Synchronization 매커니즘으로 lock을 기다리는 동안 CPU를 계속 사용하며 반복적으로
Lock의 상태를 확인하는 방법입니다.
그리고 Critical region에 들어가있는 프로세스나 스레드는 방해받지 않기 위해서 모든 interrupt를 비활성화합니다.
interrupt는 운영체제나 하드웨어가 수행중인 작업을 중단하고 특정 작업을 처리하도록 강제하는 신호입니다.
이런 interrupt를 일정 시간 동안 차단함으로써 Critical Region에 있는 코드나 다른 작업에 의해 방해 받지 않도록 보장합니다.
while (lock == 1);
lock = 1;
Critical_region();
lock = 0;
위의 코드는 대표적인 lock variable을 이용한 방식입니다.
Critical_region()이 실행되는 동안 lock은 1이고 실행이 완료되고 난 이후에 종료하고 lock을 해제해줌으로써
다음 스레드나 프로세스가 Critical Region에 들어갈 수 있게 됩니다.
여기서 단점은 CPU 자원 낭비, starvation문제, Deadlock의 문제가 있으며, 아래와 같습니다.
Busy Waiting은 계속해서 lock variable을 체크해줘야 하기 때문에 CPU를 계속해서 사용하게 되고, CPU자원을 낭비하게 됩니다.
우선순위가 낮은 스레드가 계속 Lock을 획득하지 못해서 무한 대기할 수 있기 때문에 Starvation문제가 발생하게 됩니다.
Busy Waiting중인 여러 스레드가 서로의 lock을 기다리는 상황에서 Deadlock에 빠질 수 있게 됩니다.
Spin lock
여기서 Busy Waiting을 이용한 것이 Spin lock을 이용해 Lock을 획득하는 방식으로 이뤄집니다.
Spinlock은 프로세스나 스레드 A,B가 동시에 실행될 수 없기 때문에 exclusive하게 실행하는게 보장됩니다.
while(TURE) {
while(turn != 0)
critical_region();
turn = 1;
noncritical_region();
}
while(TRUE) {
while(turn != 1)
critical_region();
turn = 0;
noncritical_region();
}
하지만 문제점으로는 Critical Region에 못들어가는 Progress문제가 발생하게 됩니다.
예를 들어서, 낮은 우선순위의 스레드 A가 Lock을 획득하고, 높은 우선순위 스레드 B가 Busy Waiting을 하는 상황에서
스레드 A는 운영체제가 자원을 할당하지 않아 Lock을 해제하지 못하는 문제가 발생하게 됩니다.
Peterson's solution
Peterson's Solution은 두 개의 프로세스 간의 mutex를 보장하기 위해 설계된 고전적인 알고리즘입니다.
Peterson's Solution의 알고리즘은 Race Condition과 Critical Section문제에서 Progress와 Mutex를 보장하는데 중점을 둡니다.
| 특성 | Peterson's Solution | Spinlock |
| 대기 방식 | Busy Waiting | Busy Waiting |
| 사용 가능한 프로세스 수 | 2개의 프로세스에만 사용 가능 | 여러 스레드와 프로세스에 사용 가능 |
| Progress(진행 보장) | 진행성 보장 | 우선순위 역정 등으로 진행성 문제 발생 가능 |
TSL(Test and Set Lock)
Peterson's Solution은 이론적으로 두 프로세스 간에 Mutext와 Progress는 보장하지만, 현대적인 멀티코어 시스템에서
몇 가지 문제점으로 인해 사용이 어렵습니다. 이런 문제점을 보완하기 위해서 TSL과
같은 하드웨어 기반 Synchronization이 도입되었습니다.
Peterson's solution은 두 개의 프로세스만을 위한 알고리즘이며,
단순한 변수 체크와 조건문으로 동작하기 때문에 메모리 접근 도중 Race Condition이 발생할 가능성이 있습니다.
특히 멀티프로세스 환경에서는 메모리 접근이 Atomic하지 못하기 때문에 여러 프로세스가 동시에 동일한 변수를
수정할 수 있기 때문에 Atomic Operation하지 못하다는 문제점이 있습니다.
이를 극복하기 위해서 TSL이 사용되는 것이며, Lock을 사용하는 CPU가 memory bus를 잠그는 방식으로 사용됩니다.
bool test_and_set(bool *flag) {
bool old = *flag;
*flag = True;
return old;
}
/////
lock = false
repeat
while Test_and_Set(lock) do no-op;
Critical Section
lock = false;
Remainder Section
until false
이제 TSL은 Atomic, mutex를 보장하지만, Busy waiting으로 인한 자원낭비가 심하기 때문에 이를 해결하기 위해서
운영체제는 Sleep and Wakeup 매커니즘을 도입하게 됩니다.
Sleep and Wakeup
Sleep and Wakeup은 Busy Waiting문제를 해결하기 위해서 고안된 방법입니다.
대기 중인 스레드가 필요할 때만 깨워 작업을 수행할 수 있도록 함으로써 CPU 자원의 낭비를 방지하는 방식입니다.
동작원리는 아래와 같이 간단합니다.
Sleep은 Lock을 얻지 못한 스레드는 바로 반복문으로 대기하지 않고 waiting queue에 들어가 대기 상태로 전환됩니다.
또한 대기중인 스레드는 스케줄링되지 않습니다.
Wakeup은 Lock을 해제하는 스레드가 대기중인 스레드 중에 하나를 깨워 Lock을 획득할 수 있게 합니다.
스레드가 깨어나면 Critical Region에 진입하고 작업을 수행하게 됩니다.
pthread_mutex_t lock;
pthread_cond_t cond;
int is_locked = 0; // Lock 상태 표시
void acquire_lock() {
pthread_mutex_lock(&lock); // 뮤텍스 잠금
while (is_locked) {
pthread_cond_wait(&cond, &lock); // Lock이 해제될 때까지 대기 (Sleep)
}
is_locked = 1; // Lock 설정
pthread_mutex_unlock(&lock); // 뮤텍스 해제
}
void release_lock() {
pthread_mutex_lock(&lock); // 뮤텍스 잠금
is_locked = 0; // Lock 해제
pthread_cond_signal(&cond); // 대기 중인 스레드 하나를 깨움 (Wakeup)
pthread_mutex_unlock(&lock); // 뮤텍스 해제
}
여기에 더해서 추가적으로 Producer-consumer라는 것도 존재합니다.
Producer-Consumer는 버퍼에 producer는 item을 생성해서 넣고, consumer은 잠자는 상태입니다.
버퍼가 다 차게되면, consumer를 깨워서 item을 사용하고, 버퍼에 공간이 생기면 producer을 깨우는 방식입니다.
위의 방식은 Busy waiting과 Progress를 해결할 수 있습니다. 하지만 Race Condition이라는 단점이 있을 수 있습니다.
문제는 producer가 버퍼에 데이터를 추가한 후, wakeup신호를 보내 consumer를 깨우려고 할 때,
consumer는 이미 버퍼가 비어 있다고 판단해 대기 상태로 진입하려고 할 때 wakeup 신호가 너무 일찍 발생하게 되면 문제가
발생하게 됩니다. consumer는 아직 대기 상태로 들어가기 전에 wakeup 신호가 발생하면, 신호가 손실되고 소비자는 영원히
대기 상태에서 빠져나올 수 없게 됩니다.
while (count == 0) {
pthread_cond_wait(&cond_consume, &mutex); // 소비자가 대기 상태로 진입
}
int item = buffer[--count]; // 버퍼에서 데이터 소비
pthread_cond_signal(&cond_produce); // 생산자를 깨움
예를 들어서 위의 코드에서 consumer는 count == 0을 확인합니다. 버퍼가 비어있다고 판단하고 대기 상태로 들어가려고 합니다.
그러나 consumer가 대기 상태로 진입하기 전에 생산자가 데이터를 추가하고 wakeup신호를 보내게 되고,
consumer는 신호를 받지 못하고 잠든 상태로 남게 되어 시스템이 멈출 수 있습니다.
Semaphores(PV operation)
세마포어는 Synchronization는 카운팅 매커니즘을 통해 동시 접근할 수 있는 자원의 수를 제한하여,
Deadlock과 Race Condition을 예방하는 중요한 역할을 합니다.
세마포어는 정수 변수(카운터)로 표현되며, 공유 자원에 접근할 수 있는 프로세스나 스레드의 수를 제어합니다.
P연산과 V연산은 카운터 값을 증가시키거나 감소시켜 자원 접근을 관리합니다.
P(down)연산 → 자원획득 시도 의미, 세마포어 값을 감소
V(up)연산 → 자원 해제를 의미하며, 세마포어 값을 증가
또한 세마포어의 두 operation은 atomic하게 수행됩니다.
위와 같은 장점들을 이용해 세마포어는 Producer Consumer Problem을 해결할 수 있습니다.
binary semaphore(aka mutex semaphore)는 mutex를 보장한 세마포어로
한번에 하나의 스레드나 프로세스만 들어오는 것을 허락하기 때문에 이 점을 이용해서
Producer Consumer의 문제점을 해결할 수 있습니다.
또한 poducer와 consumer가 버퍼가 full이거나 empty일 때 움직임을 각자 상황에 맞게 멈추게 됩니다.
bounded buffer using Semaphores의 경우 아래의 코드와 같습니다.
#pseudocode
var mutex: semaphore = 1 ; mutual exclusion to shared data
empty: semaphore = n ; count of empty buffers (all empty to start)
full: semaphore = 0 ; count of full buffers (none full to start)
procedure:
<produce the item>
down(empty) ; one fewer buffer, block if non available
down(mutex) ; get access to pointers
<add item to buffer>
up(mutex) ; done with pointers
up(full) ; note one more full buffer
consumer:
down(full) ; wait until there;s a full buffer
down(mutex) ; get access to pointers
<remove item from buffer>
up(mutex) ; done with pointers
up(empty) ; note there's an empty buffer
<use the main>
세마포어는 기존의 Synchronization의 문제들을 해결할 수 있지만, global variable을 공유하기 때문에
코드를 잘못 작성했을 때 어디서나 접근할 수 있다는 단점이 있습니다. 즉, 코드를 잘 작성해야 한다는 문제점이 있습니다.
그 다음으로 세마포어는 단순한 카운팅 도구일 뿐, 세마포어와 실제로 제어하려는 자원이나 데이터 간에는
명시적인 연결이 없습니다. 프로그래머는 세마포어로 보호할 데이터와 세마포어의 역할을 일관되게 관리해야 하며,
실수로 잘못된 데이터에 세마포어를 적용하거나 세마포어 없이 자원을 사용하면 문제가 발생할 수 있기 때문입니다.
그리고 프로그래머가 동일한 세마포어를 Critical region 보호와 Synchronization에 혼용하면
Dead lock이나 Starvation같은 문제가 발생할 수 있습니다.
그렇다면, 세마포어와 같은 동기화 도구를 사용해 프로세스 간에 데이터를 어떻게 공유하고,
이러한 공유가 스레드와 어떻게 다른지와 세마포어와 프로세스 간 공유 데이터의 개념은 어떻게 될까요?
첫 번째로, 세마포어와 같은 동기화 도구는 주로 커널공간에 저장됩니다.
커널에 저장된 세마포어는 System call을 통해서만 접근할 수 있습니다.
이런 이유는 프로세스 간에 직접적인 메모리 접근을 허용하면 데이터 손상이나 보안 문제가 발생할 수 있기 때문에,
커널이 자원을 관리하면 안정적이고 안전한 접근이 가능하게 됩니다.
두 번째로, 프로세스와 독립성 부분에서 각 프로세스는 자신의 메모리 공간을 독립적으로 사용하기 때문에,
커널을 통한 세마포어 관리가 필요합니다.
세 번째로, 현대 운영체제는 공유 메모리와 메모리 맵 파일을 통해 프로세스 간 통신을 지원합니다.
네 번째로, 공유 파일은 메모리 공유가 불가능한 경우에만 대안으로 사용될 수 있지만, 성능 저하가 발생할 수 있습니다.
프로세스와 스레드 간 공유 메모리 방식의 차이점을 이해하는 것은 동시성 프로그래밍과 IPC 문제 해결에 중요합니다.
지금까지 Synchronization의 일부를 살펴봤습니다. 아직 Monitor이라는 개념과 Message개념이 남아있기 때문에
다음 시간에 Monitor와 Message에 대해서 살펴보고 Scheduling에 대해서 알아보겠습니다.
감사합니다.
'전자전기공학 > 운영체제' 카테고리의 다른 글
| [Operating System/운영체제][Memory관리,Virtual memory, Paging] (0) | 2024.10.29 |
|---|---|
| [Operating System/운영체제][memory관리, Bit Map, Linked List, Fragmentation] (4) | 2024.10.28 |
| [Operating System/운영체제][Thread] (4) | 2024.10.08 |
| [Operating System/운영체제][Process] (8) | 2024.10.07 |
| [Operating System/운영체제][Trap, System Call, Fault, Interrupt] (0) | 2024.09.30 |