들어가기에 앞서 - race condition
컴퓨터의 데이터 접근 방식
컴퓨터가 진행하는 작업 중 디스크의 데이터를 이용하는 경우, 디스크에 저장되어 있는 값을 읽어와 연산을 하고 다시 저장하는 작업을 거친다.
읽기 작업은 데이터의 정합성이 깨질 염려가 없지만, 문제는 쓰기 작업이다. 다음 경우를 보자.
두 개의 연산 장치에서 동일한 디스크에서 데이터를 읽어 온 후, 각자 되쓰는 작업을 거쳤다고 해보자. 1번 연산 장치에는 데이터에 +1, 2번 연산 장치는 데이터에 -1을 한다고 했을 때, 결국 저장된 데이터는 +1 혹은 -1 일 것이다. (나중에 써진 것이겠지) 둘 중 하나는 원하는 결과를 얻지 못한다.
위처럼 공유 자원에 대한 접근에서 생기는 문제 상황을 Race condition이라고 한다.
OS에서의 race condition
interrupt handler VS kernel
커널모드 running 중 인터럽트가 발생하여 인터럽트 처리 루틴이 수행되는 것
예시
위와 같은 상황이 있다고 했을 때, 1. load 단계에서 읽어들인 데이터가 인터럽트 처리루틴 결과와는 상관없이 3. store 되어 증가연산만 된 경우이다.
발생할 수 있는 상황
1.
커널 수행 중 인터럽트 발생시
2.
프로세스가 시스템 콜을 하여 커널모드로 수행 중인데 문맥 교환이 일어난 경우
3.
멀티 프로세서에서 공유 메모리 안의 커널 데이터
해결 방안
해당 위험이 있는 종류의 작업인 경우 인터럽트 루틴이 끼어들 수 없도록 처리한다.
프로세스가 시스템 콜 중에 선점된 경우
프로세스는 아래처럼 유저모드와 커널모드를 전환하며 실행된다.
시스템 콜로 인해 호출되는 커널모드
만약 두 개의 프로세스가 실행중인데 시스템 콜을 통해 IO를 하고 있는 도중(커널모드) 선점 당하여 다른 프로세스가 실행되고, 해당 프로세스도 IO를 위해 커널모드를 사용하면, 커널 내에서 활용하고 있는 데이터에 대한 race condition이 발생할 수 있다.
커널모드 중 선점으로 인해 발생할 수 있는 race condition
해결방안
시스템 콜로 인해 커널모드에 진입해 있을 때는 CPU를 선점하지 않는 방식으로 해결할 수 있다. (현대의 리눅스 커널은 완전 선점 가능하다. 대신 다른 동기화 기법을 활용한다)
멀티 프로세서 인 경우
CPU가 여러개인 상황에서 메모리 접근을 할 경우, 동일 메모리 주소에 접근해 race condition이 발생할 수 있다. 각 프로세서는 각각 별도의 작업큐와 인터럽트 요청 라인을 가지기 때문에, 인터럽트 disable로 해결할 수 없는 문제이다.
해결방안
1.
커널에 접근할 수 있는 CPU를 1개로 제한한다. (비효율적)
2.
데이터에 lock을 건다.
Process Synchronization
basic concept
공유 데이터(shared data)의 동시 접근으로 인한 race condition. 막기 위해선 병행 진행 되고 있는 프로세스 간에 공유 메모리 접근에 대한 순서를 정해 주어야 한다.
보통 프로세스는 고유한 주소 공간과 데이터를 활용하기 때문에, 여러 프로세스가 진행되고 있다고 해서 반드시 생기는 문제가 아니다. 여러 프로세스가 공유하고 있는 메모리가 있을 때 대응할 필요가 있고, 그것이 프로세스 동기화(Process Synchronization)이다.
임계구역 문제 Critical Section Problem
여러 프로세스가 함께 사용하는 공유메모리가 있을 때, 해당 메모리에 접근하는 코드 블록을 임계구역(critical section)이라고 부른다.
프로그램적 해결
코드를 작성하는 개발자가 직접 임계 구역(critical section)을 관리하는 방법이다. 3가지 조건을 만족해야 한다.
1.
Mutual Exclusion 상호 배제
a.
프로세스 P1이 임계 구역을 수행 중이면 다른 모든 프로세스들은 critical section에 들어가면 안 된다.
2.
Progress
a.
아무도 임계 구역에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있다면 들어가게 해주어야 한다.
3.
Bounded Waiting 한정된 대기
a.
프로세스가 임계 구역에 들어가려고 요청한 후부터 그 요청이 허용될 때 까지 다른 프로세스들이 임계 구역에 들어가는 횟수에 한계가 있어야 한다. (두드리다보면 열려야 한다)
가정
•
모든 프로세스의 수행 속도는 0보다 크다. (임계 구역을 수행하던 프로세스가 멈춰 있으면 임계 구역 내부에서 영원히 빠져나오지 않고, 다른 프로세스들도 접근할 수 없게 될 것이니까)
•
프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
프로그램적 해결 알고리즘 1
•
turn 이라는 공유 변수 사용
프로세스가 들어가면 turn 이라는 공유변수를 변경시켜서 접근하는 방식.
•
한계점
◦
P0은 빈번하게 critical section에 접근하고, P1는 1번만 접근한다고 가정하면, P0는 여러번 반복해 critical section에 접근하고 싶어도 P1이 접근해주지 않으면 접근할 수 없다. 즉, 프로그램적 해결 만족 조건 중 progress를 만족시키지 못하므로 좋은 알고리즘은 아니다.
프로그램적 해결 알고리즘 2
•
flag를 설정하고, 나의 플래그와 여타 프로세스의 플래그를 검사해 critical section에 접근하는 방식.
•
한계점
◦
두 개의 프로세스가 동시에 2행 까지 접근하면(p0이 2행까지만 cpu를 쓰고 CPU를 넘김 → 그 사이에 p1이 2행까지 진행함) 영원히 critical seciton에 접근할 수 없다. progress 미충족!
프로그램적 해결 알고리즘 3
•
고안한 사람의 이름을 따 피터슨(Peterson)의 해결책이라 불린다.
•
•
한계점
◦
busy waiting(= spin lock) 문제 : 통과할 수 없는 while문을 돌면서 CPU를 점유하는 문제. lock이 잡혀 있으면 해당 critical section을 수행중인 프로세스로 CPU를 넘겨주어 해결하는 것이 최선이지만, 프로그램적 해결법으론 쉽지 않다.
◦
또한 최신 컴퓨터 아키텍처에선 작동한다고 보장되지 않는다. 시스템 성능의 향상을 위해 프로세스 또는 컴파일러가 종속성이 없는 읽기 및 쓰기 작업을 재정렬할 수 있기 때문이다. 1번 라인과 2번 라인만 뒤바뀌어도 피터슨의 해결책은 제대로 상호배제를 시켜줄 수 없다. 제대로 된 상호 배제를 시켜주기 위해선, 적절한 동기화 도구를 사용해야 한다. 하드웨어의 지원과 고수준 소프트웨어 API에 대해 알아보자.
하드웨어적 해결방법
Tree and Set
프로그램적 해결방법 2번 방식이 잘 동작하지 않는 이유는, 읽고 쓰는 작업이 서로 다른 인스트럭션으로 이루어져 있기 때문이다. 인스트럭션이 수행되는 도중에는 인터럽트가 올 수 없기 때문에, 만약 읽기와 쓰기가 하나의 인스트럭션에서 이루어진다면 프로그램적으로 훨씬 간단하게 코드를 짤 수 있다.
읽음과 동시에 1(true)를 세팅하는 인스트럭션을 지원하는 경우
하드웨어가 읽기와 쓰기를 하나의 인스트럭션에서 진행할 수 있도록 지원한다면(위이미지의 Test_and_set() 처럼), 프로그램이 훨씬 간결하게 작성될 수 있다.
Compare And Swap, CAS
compare_and_swap() 명령어는, test_and_set() 명령어와 마찬가지로 두 개의 워드에 대해 원자적인 연산을 하지만 두 워드의 내용 교환에 기반을 둔 기법이다.
test_and_set()과는 달리 3개의 파라미터를 대상으로 연산을 한다.
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
C
복사
어떠한 경우에든 CAS 명령어는 언제나 value의 원래 값을 반환한다. CAS를 활용하여 상호배제는 다음과 같이 구현한다.
1.
전역변수 lock이 선언되고 0으로 초기화 된다.
2.
CAS()를 호출한 첫 번째 프로세스는 lock을 1로 지정한다.
3.
lock의 원래 값이 expected 값과 같으므로 프로세스는 임계구역으로 들어간다.
4.
이후의 CAS() 호출은 현재 lock의 값이 기대값 0과 같지 않기 때문에 성공할 수 없다.
5.
2번에서 처음으로 CAS()를 호출한 프로세스가 임계구역을 빠져나올 때 lock을 0으로 변경한다.
6.
다른 프로세스가 임계구역을 들어갈 수 있게 된다.
위 과정을 코드로 표현하면 다음과 같다.
while(true){
while(comapre_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
C
복사
아쉽게도 위 코드는 상호배제는 성공하지만, 한정된 대기는 만족시키지 못한다. 해당 내용까지 만족 시키는 코드는 다음과 같다.
/* 전역변수 */
boolean waiting[n];
int lock;
/* 코드 */
while(true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key ==1)
key = compare_and_swap(&lock, 0, 1);
waiting[i] = false;
/* 임계 영역 */
j = (i + 1 ) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j==1)
lock = 0;
else
waiting[j] = false;
/* remainder section */
}
C
복사
일반적으로 상호배제를 구축하기 위해 compare_and_swap() 명령어를 직접 사용하진 않는다. 대신 원자적 변수(atomic variable)를 활용한다. 원자적 변수는 정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산을 제공하는데, CAS는 이런 원자적 연산을 구현할 때 내부적으로 활용된다.
고수준 소프트웨어 해결방법
뮤텍스 락 (Mutex Locks)
뮤텍스 라는 용어는 mutual exclusion, 상호 배제라는 말에서 왔다. 임계구역을 보호하고 경쟁 조건을 방지하기 위해 개발된 고수준 소프트웨어 도구이다.
기본 컨셉은 임계 구역에 들어가기전 반드시 락을 획득해야 하고 임계 구역을 빠져나올 때 락을 반환하는 것이다.
락을 얻을 수 있는지 반환하는 부울 변수 available, 락을 얻는 acquire(), 락을 반환하는 release() 함수로 이루어져 있다.
acquire() {
while !(!available)
; /* busy wait */
available = false;
}
C
복사
acquire 함수
release() {
available = true;
}
C
복사
release() 함수
뮤텍스 락을 활용한 임계구역 문제 해결은 다음과 같이 이루어진다.
while (true) {
acquire lock
/* critical section */
release lock
/* remainder section */
}
C
복사
뮤텍스 락의 단점
바쁜 대기(busy waiting)를 해야 한다는 것이 단점으로 꼽힌다. 한 프로세스가 임계 영역에 있는 동안 다른 프로세스들은 acquire()를 호출하는 반복문을 계속 실행해야 한다.
mutex락은 다른말로 스핀락(spin lock)이라고도 한다. 락을 사용할 수 있을 때 까지 프로세스가 회전하기 때문이다.
하지만! 문맥교환을 위한 비용이 클 경우, 차라리 스핀락으로 기다리는 것이 나을 때가 있다. 최신 다중 코어 시스템의 특정 상황에서는 실제로 락이 필요할 때 스핀락이 선호된다.
세마포 (Semaphore)
위의 방식을 추상화하기 위해서, 세마포라는 객체를 만들었다. 세마포는 정수 변수를 품은 객체라고 보면 이해가 쉽다. 그리고 API를 제한적으로 열어주어(wait(), signal()), 프로세스 간 동기화를 구현할 때 원자적(atomic)인 동작을 보장해 쉽게 프로세스를 구성할 수 있게 해주는 것이다.
세마포의 구성
초기화를 제외하고는 wait() 와 signal() 로만 접근할 수 있다. 세마포는 본디 Edsger Dijkstra라는 네덜란드 과학자에 의해 만들어졌고, wait() 함수는 “검사하다"를 의미하는 네덜란드어 proberen 에서 P, signal() 함수는 “증가하다"를 의미하는 verhogen()에서 V라고 지어졌다.
wait()와 signal()의 정의는 다음과 같다.
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
C
복사
wait(), while문의 검사와 세마포 감소 사이에 인터럽트 되지 않아야 한다.
signal(S) {
S++;
}
C
복사
signal()
wait와 signal() 연산 중 세마포의 정수 값을 변경하는 연산은 반드시 원자적으로 수행되어야 한다. (== 한 스레드가 세마포 값을 변경하면 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없다.)
실제 linux에서 semaphore.h 코드
세마포의 두 가지 사용법
운영체제는 종종 카운팅(counting) 세마포와 이진(binary) 세마포를 구분한다.
•
카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용된다. 세마포는 가용한 자원의 개수로 초기화된다.
각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하며, 이때 세마포의 값은 감소한다.
프로세스가 자원을 방출 할 때는 signal() 연산을 수행하며, 이 때 세마포의 값은 증가한다.
•
세마포 구현법
wait()를 실행하고 세마포 값이 양수가 아닌 것을 발견(== 사용 가능한 자원이 없다면)하면 프로세스는 대기해야 한다. 이 때 busy waiting 대신 프로세스는 자신을 일시 중지 시킬 수 있다. 일시 중지 연산은 프로세스를 세마포에 연관된 대기 큐에 넣고, 프로세스의 상태를 대기 상태로 전환한다. 그 후 제어가 CPU 스케줄러로 넘어가고, 스케줄러는 다른 프로세스를 실행한다.
그러면 대기 상태에 빠진 프로세스는 어떻게 되는가? 다른 프로세스가 signal() 연산을 실행하면 재시작 되어야 한다. 프로세스는 wakeup() 연산(대기상태 → 완료상태)에 의하여 재시작되는데, 재시작 되면 준비 큐에 넣어진다. (이것이 바로 수행되는지 여부는 CPU 스케줄링 알고리즘에 따라 달라진다.)
이러한 정의를 따르기 위해, 세마포를 다음과 같이 정의한다.
typedef struct {
int count;
struct process *list;
} semaphore;
C
복사
각 세마포는 한 개의 정수 value와 프로세스 리스트 list를 가진다
프로세스가 세마포를 기다려야 한다면, 이 프로세스를 세마포의 프로세스 리스트에 추가한다. signal() 연산은 프로세스 리스트에서 한 프로세스를 꺼내서 그 프로세스를 깨워준다.
wait()와 signal()은 이제 이렇게 정의된다.
wait(semaphore *S){
S -> count--;
if(S -> count < 0){
add this process to S -> list;
sleep();
}
}
C
복사
sleep가 추가된 wait()
signal(semaphore *S){
S -> count++;
if (S -> count <= 0){
remove a process P from S -> list;
wakeup(P);
}
}
C
복사
wakeup이 추가된 signal()
대기하는 프로세스의 리스트는 PCB에 있는 연결 필드에 의해 쉽게 구현할 수 있다. 각 세마포는 정수 값과 프로세스 제어 블록의 리스트에 대한 주소값을 가지고 있게 된다.
모니터
세마포가 프로세스 동기화를 위해 쓰일 수 있지만, 잘 못 사용하면 발견하기 어려운(간헐적으로 발생하는) 타이밍 오류를 만들게 된다. 프로그래밍 오류 또는 프로그래머에 의해 발생할 수 있는데, signal()을 호출해야 하는 코드에 실수로 wait()를 호출하는 식이다.
이러한 오류를 처리하기 위해 간단한 동기화 도구들을 통합한 고급 언어 구조물에 대한 필요성이 대두되는데, 그것이 모니터(monitors) 타입이다.
모니터 사용법
추상화된 데이터 형(abstract data type, ADT)는 공유 데이터와 공유 데이터를 조작하는 함수를 하나의 단위로 묶어 보호한다. (자바의 캡슐화된 객체와 유사하다.) 모니터는 상호배제를 보장해줄 수 있는 연산자 집합 (메서드)를 제공해주는 ADT이다. (자바 개발자인 나의 이해를 돕기위해, 이하 ADT를 객체라는 표현으로 치환하겠다.)
모니터가 동기화를 위해 작동하려면 condition 타입의 데이터 객체가 필요하다. condition 타입 변수는 wait()와 singal()만 호출할 수 있다.
condition x, y;
// 만약 x.wait()가 호출된다면
x.wait();
// 다른 프로세스가 x.signal()을 호출할 때 까지 일시중지 되어야 한다.
x.signal();
C
복사
x.signal() 연산은 정확히 하나의 일시중지 프로세스를 재개한다. 만약 일시 중지된 프로세스가 없으면, signal() 연산은 무시된다. 무조건 내부 변수(count++)에 영향을 주던 세마포의 signal()과 대조적이다.
x.signal() 연산을 호출하는 프로세스 P가 있고, x와 연관되고 일시중지(suspend)된 프로세스 Q가 있다고 하자. Q가 재개되면 P는 반드시 대기(wait)해야 된다. 그렇지 않으면 둘 다 활성화되기 때문이다. 그러나 두 프로세스 모두 실행이 계속될 수 있는데, 두 가지 가능성이 있다.
1.
signal and wait : P는 Q가 모니터를 떠날 때 까지 기다리거나 또는 다른 조건을 기다린다. → Q가 나갈 때 까지 suspend됨
2.
signal and continue : Q는 P가 모니터를 떠날 때 까지 기다리거나 또는 다른 조건을 기다린다 → signal을 호출하고도 P가 계속 실행됨
절충안도 존재한다. P가 signal을 호출하면, 즉시 모니터를 떠나고 Q가 재개되는 방식이다.
모니터 내에서의 프로세스 수행 재개
만약 x.signal() 이 호출되었을 때, 일시중지 되어있던 프로세스가 여러개라면 어떤 것이 재개되어야 할까?
간단하게는 가장 오래 기다린 프로세스가 가장 먼저 깨어나는 FCFS로 해도 되겠지만, 많은 경우 이걸로 충분하지 않다. 그럴 땐 wait에 우선 순위 파라미터를 넘기는 conditional-wait 객체를 활용할 수 있다.
// c는 정수 표현이다.
x.wait(c);
C
복사
c의 값은 우선순위 번호이며 일시 중지되는 프로세스의 이름과 함께 저장된다. x.signal()이 수행되면, 가장 작은 우선순위 번호를 가진 프로세스가 재개된다.
고전적인 동기화 문제
Readers-Writers 문제
하나의 DB가 다수의 병행 프로세스에 공유된다고 가정하자. 이들 중 일부는 읽기만, 일부는 쓰기만 하기를 원할 수 있다. 전자를 readers, 후자를 writers라고 부르자.
여러 reader가 공유 데이터에 접근해도 불행한 결과가 생기진 않는다. 그러나 하나 이상의 writer와 다른 프로세스가 동시에 DB에 접근하면, 혼란이 야기될 수 있다.
이러한 문제점을 막기 위해 writer가 쓰기 작업동안 공유 데이터베이스에 배타적 접근 권한을 가지게 해야할 필요가 있다. 이 문제를 readers-writers 문제라고 한다.
현재 readers-writers 문제는 일반화 되어 몇몇 시스템에선 쓰기모드와 읽기모드가 분리된 reader-writer 락을 제공한다. reader-writer 락을 획득할 때에는 읽기 모드 인지, 쓰기 모드인지 지정해야한다. (mysql에선 읽기 락은 s락, 쓰기락은 x락이라고 부른다.)
식사하는 철학자들 문제
The Dining-Philosophers Problem
번외편 - java에서의 동기화
자바는 언어의 기원부터 스레드 동기화에 대한 풍부한 지원을 제공하였다. 자바의 모니터 도구인 synchronized에 대해 알아보자.
Monitor
자바는 스레드 동기화를 위해 모니터와 같은 방식의 도구를 제공하고 있고, synchronized 키워드로 활용할 수 있다.
java의 모든 인스턴스는 각각 하나의 락과 연결되어 있다. 메소드가 synchronized로 선언될 경우, 메소드를 호출하려면 그 객체와 연결된 락을 획득해야 한다. 해당 키워드는 메서드 단위, 혹은 블럭 단위로 붙일 수 있다.
public class BoundedBuffer<T> {
private T[] buffer;
// synchornized 메서드 예시
public synchornized void insert(T item) {
/* insert logic */
}
// synchornized block 예시
public T remove() {
synchornized {
/* remove logic */
}
/* after remove */
}
}
Java
복사
만약 다른 스레드가 이미 락을 획득하고 있다면, synchronized 메서드를 호출한 스레드는 봉쇄되어 객체의 락에 설정된 진입 집합(entry set)에 추가된다. → 진입 집합은 락이 가용해지기를 기다리는 스레드의 집합을 나타낸다.
락을 획득하고 있던 스레드가 종료되면, 락이 해제(release)된다.
락이 해제될 때 진입 집합에 하나 이상의 스레드가 있다면, JVM은 다음에 synchronized영역에 들어갈 스레드를 임의로(임의는 랜덤이 아니라 Java 명세에 명시되어 있지 않다는 의미이다. 운영체제마다 다를테니까. 대부분은 FIFO로 되어있다고 한다.) 지정한다.
락 말고도 모든 객체는 스레드의 자료구조인 대기 집합과도 연결되어 있다. 대기 집합은 처음엔 비어있는데, 객체가 wait()를 호출하면 대기 집합에 할당된다. 이 대기집합은 lock을 획득한 스레드가 실행되었는데 어떠한 이유로 현재는 조건에 충족하지 못하여 공유자원에 접근할 수 없는 상황인 경우, 일시적으로 suspend되기를 선택한 객체들이 모인 공간이다.
예컨데 위의 BoundedBuffer에서 buffer가 꽉 차서 insert를 못하는 경우, 해당 인스턴스는 insert를 호출한 스레드를 wait하기를 선택 할 수 있다. 향후 remove가 실행 되어 buffer에 여유 공간이 생기면 다시 실행할 수 있도록!
notify()를 하면 대기집합의 스레드 중 하나가 락을 획득할 수 있는 진입 집합으로 다시 들어간다.
이 동작 과정에 대한 예시는 아래 링크에 작성했다.
