728x90
Background
- Data consistency
- 멀티프로세싱/스레딩 시에 다수 작업이 동시에 시행
- 인터럽트 발생 시 이전에 동작하던 작업이 일시 중단되고 새로 실행
- 여러 작업이 데이터를 공유할 경우 문제 발생
- 데이터 업데이트 중 다른 프로세스가 읽어들이거나
- 여러 프로세스가 동시에 쓰는 경우
- 일정 루틴에 맞는 프로세스 실행 순서를 정의할 필요가 존재
- Producer - Consumer Problem
- 데이터 생산 프로세스(Producer)는 큐가 차있지 않은 동안 데이터를 입력
- 데이터를 쓰는 프로세스(Consumer)는 큐가 비어있지 않으면 데이터 사용
- Counter 변수를 같이 접근하는 문제 존재
- ++, --명령어 실행 시 변수값을 각 레지스터로 이동하여 처리
- race condition : 초기값이 5일 때, 동시에 접근 시 Producer는 5 > 6, Consumer는 5 > 4로 Counter 값을 바꾸므로 결과적으로 카운터값이 6>4로 변경될 가능성 존재
- fork()의 race condition
- fork 실행 시 반환값은 PID
- 두 프로세스가 동시에 fork 호출 시 같은 PID를 갖는 두 프로세스가 생성될 수 있음
/* Producer Process */
while (true) {
/* produce an item in next produced */
while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
/* Consumer Process */
while (true) {
while (counter == 0)
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
/* consume the item in next consumed */
}
Critical-Section Problem
- 다수의 프로세스/스레드 생성 시 한 번에 하나의 작업만 실행될 수 있는 구간
- 공용 데이터 접근시의 충돌 방지
do
{
/* Ask Permission to enter critical section */
/* Critical Section */
/* Exit Critical Section */
...
}while(...);
- Critical Section 문제의 해결 조건
- Mutual Exclusion : 프로세스 P가 Critical Section에 접근 시 다른 프로세스는 해당 구간을 실행하면 안됨(Critical Section의 정의)
- Progress : Critical Section에 실행 중인 프로세스가 없을 경우, 이 구간에 진입하고자 하는 프로세스를 지연 없이 진입시켜야 함
- Bounded Waiting : 프로세스 A가 Critical Section에 있을 때, 새 프로세스가 진입하고자 할 경우 A가 끝나는 것을 대기해야 하나, 무한정 대기해서는 안됨 (Critical Section 진입 시 우선순위의 조정 필요)
- OS의 Critical-Section Handling : Non-Preemptive
- 인터럽트 없이 커널 설계
- 구현이 쉽고, 오류를 신경쓸 필요성이 낮아짐
- 공유 데이터 접근 시 우선한 작업이 처리되어야 나머지 처리가 가능하므로 시스템 반응성, 성능이 떨어지게 됨
Peterson's Solution
- SW 기반으로 HW 영역의 문제를 해결하고자 하는 접근법
- 2개 프로세스/스레드를 가정
- load/store 명령어는 순서대로 실행된다고 가정(각 명령어 중에는 인터럽트가 없음)
- 두 프로세스에는 변수가 존재 : int turn ; bool flag[2]
- turn : critical section에 접근 가능한 프로세스
- flag[i]가 true면 i번째 process가 Critical section에 접근하고자 함
- Entry Section
- 자신의 flag를 true로 만듦 : critical section에 접근할 준비
- turn을 상대 프로세스 값으로 대입
- while : 상대 프로세스가 준비가 되었고(flag), 실행할 순서인 경우(turn), 완료할 때까지 무한루프로 대기
- 그렇지 않은 경우 자신의 코드 실행
- critical section 실행 후 자신의 flag를 false로 설정
- 위 예시의 검증
- Mutual Section : while문 조건에서 turn이 상대방 값으로 대입되므로 critical section에 동시 접근이 불가
- Progress : Entry section에 진입하지 않은 경우 해당 프로세스의 flag는 false이므로 다른 프로세스는 바로 critical section에 접근 가능
- Bounded Waiting : turn이 상대 값으로 대입되었기 때문에 프로세스가 while문 재진입 시 다른 프로세스에 우선권을 넘겨주므로 무한 대기 없이 두 프로세스가 순차 실행
- Peterson's Soultion의 문제 : 현대 컴퓨터에서 실행을 보증하지 않음
- 프로세서나 컴파일러가 성능을 위해 독립적으로 실행되는 명령어 순서를 변경할 수 있음
- 독립적인(서로 다른 곳에 접근하는) 명령어의 경우 순서를 바꾸어도 결과는 동일
- 멀티코어 / 멀티프로세서 구조에서 심각한 문제가 될 수 있음
- 원래의 알고리즘
- (Process i) flag i = true, turn = j
- (Process j) flag j = true, turn = i
- (Process j가 먼저 접근한 경우) j는 critical section 처리, i는 while 대기
- flag j = false : Process i가 critical section 처리
- 현대 아키텍처의 경우
- (Process i) turn = j : flag를 나중에 대입
- (Process j) turn = i, flag j = true
- turn i=false이므로 Process j가 Critical section 처리
- (Process i) flag i = true
- turn이 i이므로 Process i도 Critical Section에 접근 가능 : Mutual Section 위반
- 원래의 알고리즘
HW Support for Synchronization
- Critical Section Code를 위한 별도 명령어 제공
- Memory Barrier
- HW Instruction
- Atomic Variable
- Memory Barrier
- 명령어의 실행 순서를 명시
- Strongly Ordered : 각 프로세서가 구현 명령어대로 접근
- Weakly Ordered : 명령어 접근 순서가 바뀔 수 있음
- Memory barrier : 배리어 전후로는 명령어 순서 변경이 불가
- HW Instruction
- Test-and-Set
boolean test_and_set (boolean *target) {
boolean rv = *target;
*target = true;
return rv:
}- 다른 명령어와 독립적으로 실행(execute atomically)
- target값을 읽어들인 후, target에 새 값 대입
- 읽어들인 값 rv 반환
- Compare-and-Swap
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}- 이전값(value)가 예측값(expected)와 동일하면 새 값(new_value)로 치환
- Test-and-Set
// criticals section with test_and_set
do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
- test_and_set이 처음에는 false
- 먼저 접근한 프로세스가 lock을 true로 바꿈
- 나머지 프로세스들은 test_and_set이 true를 반환하게 되므로 mutual section이 성립
//critical section with comp_and_swap
while (true){
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
- 초기값 lock이 0이면 해당 프로세스는 Critical section 진입하면서 lock을 1로 바꿈
- 나머지 프로세스는 lock이 1이므로 while 대기
- 이때 value와 expect가 다르므로(1, 0) swap이 되지 않게 됨
while (true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key == 1)
key = compare_and_swap(&lock,0,1);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = 0;
else
waiting[j] = false;
/* remainder section */
}
- Bounded waiting and Mutual section
- i번째 프로세스가 실행된 경우
- i+1부터 순회하면서 대기중인 프로세스 탐색
- 대기중인 프로세스가 있을 경우 해당 프로세스의 waiting 상태를 풀어줌
- 특정 프로세스가 계속해서 점유하는 것을 방지
- Atomic Variable
- 변수 하나만을 보호해야 할 경우
- 동시 접근 시 데이터의 일관성 보장
Mutex Locks
- acquire/release 명령어로 atomic variable 선언
- busy wait : Critical Section에 접근하지 못한 나머지 변수들은 while loop를 돌면서 대기
- spin lock : 무한루프를 돌면서 대기하는 형태(busy wait)
Semaphores
- Mutex Lock의 경우 한 번에 하나의 프로세스만 Critical Section 진입
- Semaphore의 경우 정수 변수 S 값의 설정에 따라 진입 가능한 프로세스 수 설정 가능
- wait(S) : 대기 중인 프로세스 조정
- signal(S) : 실행이 완료된 프로세스 release
- 자원 관리에 주로 사용
- Busy wait이 없는 Semaphore
- 프로세스 sleep(), wakeup() 확인
- wait : 프로세스 실행이 불가능한 경우 프로세스를 sleep queue에 추가 후 sleep
- signal : 프로세스가 추가 실행이 불가능하면서 waiting중인 프로세스 존재 시 해당 프로세스 wakeup
- 프로세스 리스트 접근 시 mutex section 구현 필요
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
//add this process to S->list;
block();
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
//remove a process P from S->list;
wakeup(P);
}
}
Monitor
- mutex/semaphor의 고레벨 구현
- monitor 내에 선언한 함수는 컴파일 단계에서 wait-signal이 구현됨
- condition variable
- 변수에 여러 프로세스가 동시 접근 시 signal - wait 구현
Liveness
- Progress, Bounded Waiting으로 보장
- 프로세스가 일정 시간 내에 실행되는 것을 보장
- 보장되지 않을 경우 알 수 없는 이유로 시스템이 멈추는 등의 문제 발생
- Deadlock
- 둘 이상의 프로세스가 서로의 자원을 필요로 하는 상황
- 서로의 wait을 위해 서로의 자원을 필요로 하는 상황
- P0의 Q wait을 위해서는 P1이 대기하는 Q가 필요
- P1의 S wait을 위해서는 P0이 대기하는 S가 필요
- 둘 이상의 프로세스가 서로의 자원을 필요로 하는 상황
- Starvation
- 프로세스가 공유 자원(Critical Section, Semaphore, ...)을 무한히 대기하는 현상
- 선점한 프로세스가 무한히 자원을 점유하기 때문에 발생
- Priority Inversion
- P1>P2>P3의 우선순위를 갖는 프로세스(P1이 가장 우선)을 가정
- P1, P3이 공유 자원 R1을 사용하는 상황
- P3이 사용하는 자원을 release해야 P1을 실행 가능
- 이때 P2가 실행되면 P2>P3이므로 P2가 우선 실행
- P1은 R1 자원을 대기중이므로 실행되지 못함
- 이로 인해 P2가 P1보다 우선 실행되는 우선순위 역전 현상이 발생
- 해결책 : Priority Inheritance(우선순위 상속) - P3의 우선순위를 P1 수준으로 높여줌
Bounded-Buffer Problem
- n개의 버퍼마다 데이터 존재
- 버퍼에는 full, empty, mutex 변수를 갖고 있음
- full : 버퍼 내 데이터 수
- empty : 버퍼 내의 공백 수 (full + empty = 버퍼 크기)
- mutex : 프로세스의 권한 할당 여부 (1 - producer / 0 - consumer)
- Producer
- 버퍼가 비었는지 확인(wait(empty))
- lock acquire - release acquire(wait, signal(mutex))
- notify consumer(signal(full))
- Consumer
- 버퍼가 찼는지 확인(wait(full))
- lock acquire - relase acquire(wait, signal(mutex))
- notify producer(signal(empty))
Readers-Writers Preoblem
- readers : 데이터를 읽기만 하는 프로세스
- writers : 데이터의 입/출력을 모두 하는 프로세스
- readers의 경우 동시에 데이터 읽기가 가능하게 설정
- rw_mutex semaphore를 설정
728x90