데이터 접근과 동기화
데이터 접근은 운영체제에서 프로그램이나 프로세스가 파일, 데이터베이스, 메모리 등에 저장된 데이터를 읽고 쓰는 과정을 의미한다.
race condition(경쟁 조건)은 여러 프로세스/스레드가 동시에 같은 데이터를 조작할 때, 타임이이나 접근 순서에 따라 결과가 달라질 수 있는 상황을 말한다.
동기화는 여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것을 말한다.
동기화 없이 동시 접근이 이루어지면 데이터 불일치, 충돌, 경합 등이 발생할 수 있다.
| 상호배제 (Mutual Exclusion)
임계 영역(critical section) : 공유 데이터의 일관성을 보장하기 위해 하나의 프로세스/스레드만 진입해서 실행 가능한 영역을 말한다.
여기서 하나의 프로세스/스레드만 진입해서 실행 가능한 영역을 mutual exclusion이라고 한다.
임계 영역의 해결 조건
1. 상호 배제 Mutual Exclusion : 한 번에 하나의 프로세스만 임계 영역에 들어갈 수 있어야 한다.
2. 진행 Progress : 임계 영역에 들어갈 프로세스를 선택할 때 무한 대기 상태가 발생하지 않아야 한다.
3. 한정된 대기 Bounded Waiting : 임계 영역에 들어가는 것을 기다리는 프로세스는 무한정 기다리지 않아야 한다.
상호 배제는 락(lock)을 사용해서 보장한다.
do {
acquire lock // [경합] 락을 획득하여 임계 영역에 진입하기 위해 대기하거나, 락을 얻는다.
critical section //[하나만 진입] 임계 영역. 공유 자원에 접근하거나 중요한 작업을 수행한다.
release lock //[작업 후 반환] 락을 해제하여 다른 프로세스나 스레드가 임계 영역에 진입할 수 있게 한다.
remainder section // 나머지 코드. 임계 영역과 관련 없는 작업을 수행한다.
} while(TRUE) // 무한 루프. 이 구조가 계속 반복된다.
| 스핀락 : 락을 가질 수 있을 때까지 반복해서 시도
volatile int lock = 0; // 전역 변수로 선언된 락. 여러 프로세스나 스레드 간의 공유 자원 접근을 제어한다.
void critical(){
while (test_and_set(&lock) == 1); // test_and_set 함수를 사용하여 락을 획득하려 시도한다.
// 락이 이미 획득된 상태이면, 1을 반환하고, 그렇지 않으면 0을 반환하여 락을 획득한다.
// critical section 시작
// 여기에 임계 영역에 해당하는 코드가 위치한다. 공유 자원에 접근하거나 중요한 작업을 수행한다.
// critical section 종료
lock = 0; // 락을 해제하여 다른 프로세스나 스레드가 임계 영역에 진입할 수 있게 한다.
}
// 이해를 위한 TestAndSet.
// 공유되는 락에 대해서, 원래 락의 값을 가져와 값을 1로 바꾼 뒤 반환. 호출하면 무조건 락의 값이 1로 바뀜
int TestAndSet(int *lockPtr) {
int oldLock = *lockPtr; // 현재 락의 상태를 저장한다.
*lockPtr = 1; // 락을 설정하여 다른 프로세스나 스레드가 이 임계 영역에 들어오지 못하게 한다.
return oldLock; // 이전 락의 상태를 반환하여, 락이 이미 설정되어 있었는지 확인할 수 있다.
}
TestAndSet은 CPU atomic 명령어다
- 실행 중간에 간섭 받거나 중단되지 않는다.
- 같은 메모리 영역에 대해 동시에 실행되지 않는다.
동일한 파라미터에 대해 두 개 이상의 프로세스가 동시에 호출한다 하더라도, cpu 레벨에서 먼저 하나 실행시키고 끝나면 이어서 다른 하나를 실행 시킨다. 동기화시켜 실행시키지, 동시에 실행시키지 않는다.
→ 동시에 두 개의 스레드가 TestAndSet을 실행할 일은 존재하지 않는다.
동작방식
락을 얻기 위해 계속해서 반복해 상태를 확인한다(busy-waiting 바쁜 대기). 즉, 락이 해제될 때까지 cpu를 점유하면서 계속 체크한다.
while 루프를 빠져나갈 때까지 시도하고, 시도하고, 시도한다.
그 때마다 락을 확인하고, 확인하고, 확인하는.
계속해서 반복하고, 락을 취득하려고 반복하는 방식
(CPU를 계속 사용하며 대기하기 때문에 "스핀"이라는 용어가 사용된다.)
장단점
간단하고 빠른 락 매커니즘이다.
하지만 기다리는 동안 CPU를 낭비한다는 단점이 있다. (락이 있는지 확인하는 일 자체가 cpu 잡아먹는 일이다.)
락을 획득할 때까지 오래 대기해야 하는 경우 비효율적이다.
다중 코어 시스템에서 간단한 락을 구현할 때 사용된다.
예시
마치 화장실 문 앞에서 계속 문이 열리는지 확인하는 사람과 같다. 계속 확인하느라 다른 일을 할 수 없다.
이를 개선한 것이 "락이 준비되면 깨워" 뮤텍스 방식이다.
| 뮤텍스 : 락을 가질 수 있을 때 까지 휴식
// 사용 예시:
mutex->lock(); // 임계 영역에 진입하기 위해 뮤텍스를 잠금. (락 획득)
... critical section // 임계 영역. 이곳에 들어가기 위해 경합을 한다.
mutex->unlock(); // 임계 영역을 벗어나면서 뮤텍스를 해제. (락 반환)
class Mutex {
int value = 1; // 뮤텍스 상태를 나타내는 변수. 1이면 사용 가능, 0이면 사용 중.
int guard = 0; // 보호 변수. Test-and-Set을 사용하여 경쟁 상태를 방지.
// value 값을 임계영역 내에서 안전하게 바꿔주기 위한 안전 장치
Mutex::lock() {
while (test_and_set(&guard)); // guard 변수의 락을 획득할 때까지 대기.
if (value == 0) { // 만약 뮤텍스가 사용 중이면,
// 현재 스레드를 대기 큐에 넣고, => "다음에 내 차례가 되면 깨워주세요"
guard = 0; // guard를 해제하고,
go to sleep; // 스레드를 대기 상태로 전환.
} else {
value = 0; // 뮤텍스를 잠금 상태로 설정. "
guard = 0; // guard를 해제.
}
}
Mutex::unlock() {
while (test_and_set(&guard)); // guard 변수의 락을 획득할 때까지 대기.
if (큐에 하나라도 대기 중이라면) { // 만약 대기 중인 스레드가 있으면,
// 그 중에 하나를 깨운다.
} else {
value = 1; // 뮤텍스를 사용 가능 상태로 설정.
}
guard = 0; // guard를 해제.
}
};
어떤 스레드가 락을 쥐기 위해 경합을 하는데, 락은 value을 통해 컨트롤된다.
value 값을 줄 수 없으면 큐에 들어가서 대기하고 있을 테니, 줄 수 있을 때 깨워줘 = > Mutex::unlock()
→ 락을 얻지 못한 프로세스를 대기 상태로 전환시켜 CPU 자원을 낭비하지 않는다.
동작방식
락을 얻지 못한 경우 해당 스레드를 대기 상태로 전환하고, cpu 자원을 해제한다.
스레드는 락이 해제되면 다시 깨워진다.
장단점
cpu 자원을 효율적으로 사용해 긴 시간 동안 락을 기다릴 때 유리하다.
하지만 스레드를 대기 상태로 전환하고 깨우는데 컨텍스트 스위칭이 필요하며 오버헤드가 발생한다.
운영체제의 커널에서 자원 접근을 제어할 때 사용한다.
화장실 문이 잠기면 문 앞에서 기다리는 것이 아니라, 나오면 말해달라 하고, 벤치에 앉아 기다리는 것과 같다.
| 그렇다면 뮤텍스가 스핀락보다 항상 좋을까?
멀티코어 환경이고, critical section에서의 작업이 컨텍스트 스위칭보다 더 빨리 끝난다면 스핀락이 뮤텍스보다 더 이점이 있다.
뮤텍스는 락을 취득할 수 없으면 잠들어 있다가 깨워줘야한다. 잠들고 깨우는 과정에 컨텍스트 스위칭이 발생한다.
컨텍스트 스위칭은 현재 실행 중인 스레드의 상태를 저장하고 ,다른 스레드의 상태를 로드하는 과정이다. 오버헤드가 발생한다.
싱글코어에서는 스핀락 방식으로 계속 기다리고 있다 해도, 이미 락을 쥐고 있는 스레드가 락을 풀어줘야 락을 취득할 수 있다.
결국 컨텍스트 스위칭이 발생하기 때문에 싱글 코어에서는 스핀락의 이점이 전혀 없다.
하지만 멀티코어 환경에서는 여러 스레드가 동시에 실행될 수 있으므로, 한 스레드가 락을 기다리면 다른 코어에서 다른 스레드를 실행할 수 있다.
임계 영역에서 수행하는 작업이 매우 짧아 컨텍스트 스위칭보다 빨리 끝나는 경우에는 스핀락이 유리할 수 있다.
→ 스핀락은 락을 얻기 위해 계속 상태를 확인한다. 짧은 시간 내에 락을 얻을 수 있다면 컨텍스트 스위칭 없이 바로 임계 영역을 실행할 수 있다. (컨텍스트 스위칭 오버헤드 없이 바로 임계 영역을 실행할 수 있기 때문에 더 효율적이다.)
반면
→ 뮤텍스는 락을 얻지 못하면 스레드를 대기 상태로 전환한다. 락이 해제되면 다시 깨우는 과정에서 컨텍스트 스위칭 오버헤드가 발생한다.
∴
스핀락이 유리한 경우: 임계 영역의 작업이 매우 짧고, 컨텍스트 스위칭 오버헤드가 크며, 멀티코어 환경에서 실행될 때.
뮤텍스가 유리한 경우: 임계 영역의 작업이 길고, 락을 기다리는 시간이 길어질 수 있는 경우. CPU 자원을 절약할 수 있다.
| 세마포어 : signal mechanism을 가진 하나 이상의 프로세스/스레드가 critical section에 접근 가능하도록 하는 장치
// 사용 예시:
semaphore->wait(); // 자원을 사용하기 위해 세마포어를 기다림.
... critical section // 임계 영역. 중요한 작업 수행.
semaphore->signal(); // 자원 사용을 종료하고 세마포어를 신호.
class Semaphore {
int value = 1; // 세마포어의 값. 자원 사용 가능 여부를 나타냄. 1이외의 값도 가질 수 있다. 1,2, ...
int guard = 0; // 보호 변수. Test-and-Set을 사용하여 경쟁 상태를 방지.
}
Semaphore::wait() {
while (test_and_set(&guard)); // guard 변수의 락을 획득할 때까지 대기.
if (value == 0) { // 만약 자원이 사용 불가능하면,
// 현재 스레드를 대기 큐에 넣고,
guard = 0; // guard를 해제하고,
go to sleep; // 스레드를 대기 상태로 전환.
} else {
value -= 1; // 자원을 사용 중으로 표시. (뮤텍스와 다르게 차감하는 방식이다._
guard = 0; // guard를 해제.
}
}
Semaphore::signal() {
while (test_and_set(&guard)); // guard 변수의 락을 획득할 때까지 대기.
if (큐에 하나라도 대기 중이라면) { // 만약 대기 중인 스레드가 있으면,
// 그 중에 하나를 깨워서 준비 시킨다.
} else {
value += 1; // 자원을 사용 가능 상태로 설정. 하나씩 증가시켜주는 방식이다.
}
guard = 0; // guard를 해제.
}
value += 1, -= 1인 이유 : critical section에 프로세스나 스레드가 하나 이상 들어갈 수 있도록 하기 위해서
공중 화장실에 좌변기가 3개, 3개까지는 동시에 사용할 수 있을 때. 이런 상황에서 세마포어가 사용된다.
value = 1 이라면, value -= 1 결과가 0이 되므로 그 이후에 wait()를 호출하는 스레드는 (value == 0) 조건에 걸려 큐에 들어가게 된다.
→ value = 1 인 세마포어는 Binary Semapore (이진 세마포어) 라고 불린다.
→ 1보다 더 많은 크기를 value로 가지는 세마포어는 Counting Semaphore라고 불린다.
특정 자원에 접근할 수 있는 프로세스의 수를 제한한다.
동시 접근 프로세스 수를 제어하여 자원 고갈을 방지한다.
다중 프로세스 환경에서 데이터베이스 연결 수 를 제한할 때 사용된다.
주차장에 몇 대의 차량만 들어갈 수 있게 하는 것과 같다. 주차장이 꽉 차면 새 차량은 대기해야 한다.
| Mutax와 Binary Semaphore은 다르다.
뮤텍스는 락을 가진 자만 락을 해제할 수 있지만 세마포어는 그렇지 않다. 세마포어는 wait를 하는 존재와 signal을 보내는 존재가 다를 수 있다.
뮤텍스는 누가 락을 해제할지 예상할 수 있다. 락을 가진 자만이 락을 해제할 수 있다.
뮤텍스는 priority inheritance 속성을 가진다. 세마포어는 그 속성이 없다.
여러 프로세스가 동시에 실행하게 되면 cpu에서 컨텍스트 스위칭이 발생해서 누굴 먼저 실행시킬지 결정하게 되는데, 이를 스케줄링 이라고 한다.
스케줄링을 하는 방식엔 여러가지가 있는데 우선순위 방식이 있다.
같은 자원에 대해 경합해서 락을 취득하려고 하다보면,
우선순위 낮은 p2가 락을 가지고 있는 상황에서, 우선순위 높은 p1이 락을 쥐려하면.
p1은 p2에 의존성을 갖게 된다.
p1은 p2가 락을 해제하기 전까지 아무것도 할 수 없다.
뮤텍스에서는 위와 같은 상황을 p2의 우선순위를 p1만큼 올려버린다. 그래서 임계 영역을 우선적으로 벗어날 수 있게 한다.
이것을 priority inheritance라고 한다.
우선순위 역전을 방지하기 위해, 낮은 우선순위의 스레드가 높은 우선순위의 스레드가 필요로 하는 락을 가지고 있을 때, 낮은 우선순위의 스레드의 우선순위를 일시적으로 올려주는 기능
하지만 세마포어는 락을 획득한 스레드가 아닌 다른 스레드가 신호를 보내어 해제할 수 있다. 즉, wait를 호출한 스레드와 signal을 호출한 스레드가 다를 수 있따라서 우선순위 역전 문제가 발생할 수 있지만 이를 해결할 수 있는 메커니즘이 없다.
∴
상호 배제만 필요하다면 뮤텍스를,
작업 간의 실행 순서 동기화가 필요하다면 세마포어를 권장한다.
'CS' 카테고리의 다른 글
| CS_운영체제_멀티프로세스, 스레드와 멀티 스레딩 (1) | 2024.06.30 |
|---|---|
| CS_운영체제_교착상태 (0) | 2024.06.30 |
| CS_운영체제_Paging: Smaller Table (0) | 2024.06.25 |
| CS_운영체제_TLB (0) | 2024.06.25 |
| CS_운영체제_세그먼테이션, 페이징 (0) | 2024.06.23 |