Process Synchronization (1)
데이터의 접근
- 데이터가 스토리지에 저장
- 연산할 데이터를 fetch
- 데이터 연산
- 연산 결과 스토리지에 저장
Race Condition
- 스토리지가 공유되어 여러 연산이 동시에 실행될 경우, Race Condition의 가능성이 있음
- CPU / Memory, Process / Address space와의 관계에서 생기는 문제
- 커널 내부 데이터를 접근하는 루틴들 간에도 문제가 있을 수 있음
- ex) 커널 모드 수행 중 인터럽트로 커널 모드 다른 루틴 수행 시
OS에서 Race Condition은 언제 발생하는가?
-
kernel mode 수행 중 interrupt 발생 시
- 커널 모드 running 중 interrupt가 발생하여 interrupt 처리 루틴이 수행
- 양 쪽 다 커널 코드이므로, kernel address space 공유
-
disable / enable interrupt로 문제 해결 가능
-
Process가 System call을 하여 kernel mode로 수행 중인데, context switch가 일어나는 경우
- 두 프로세스의 address space 간에는 data sharing이 없음
- 그러나 system call을 하는 동안에는 kernel address space의 data에 접근하게 됨
- 이 작업 중간에 CPU를 선점해가면 Race condition 발생
- 커널 모드에서 수행 중일때는 CPU를 선점하지 않고, 사용자 모드로 돌아갈 때 선점하는 것으로 해결 가능
-
멀티프로세서에서 shared memory 내의 kernel data
- 어떤 CPU가 마지막으로 count를 store 했는가에 대한 Race condition 발생
- 해결책1: 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 함(비효율)
- 해결책2: 커널 내부에 있는 각 공유 데이터에 접근할 때 마다 그 데이터에 대한 lock / unlock을 함
Process Synchronization 문제
- 공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있음
- 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요
-
Race Condition
- 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
- Race condition을 막기 위해서는 concurrent process는 동기화되어야 함
The Critical-Section Problem
- n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
- 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
- 문제: 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어가지 않아야 함
프로그램적 해결법의 충족 조건
-
Mutual Exclusion
- 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 됨
-
Progress
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 함
-
Bounded Waiting
- 프로세스가 critical section에 들어가려고 요청한 그 후부터 그 요청이 허용될 때 까지 다른 프로세스들이 critical section에 들어가는 횟수에는 한계가 있어야 함
Initial Attempts to solve problem
- 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있음 -> synchronization variable
Algorithm 1
- Synchronization variable
- int turn;
- initially turn = 0
- Pi can enter its critical section if (turn == i)
- Process Pi
- Mutual Exclusion은 만족하지만 Progress 불만족
- 반드시 한 번씩 교대로 들어가야 하기 때문에 critical section에 들어가 있는 프로세스가 turn 값을 바꾸어줘야 Progress가 생기기 때문
- P1은 critical section에 1번 들어가고, P0은 지속적으로 들어가야 하는 상황이라면 P1이 turn을 반납하지 않아 아무도 critical section을 이용하지 못하게 될 가능성 존재
Algorithm 2
- Synchronization variable
- boolean flag[2];
- initially flag[모두] = false; //no one is in critical section
- Pi ready to enter its critical section if (flag[i] == true)
- Process Pi
- Mutual Exclusion은 만족하지만 Progress 불만족
- while 문에서 서로 끊임 없이 양보하는 상황 발생 가능
Algorithm 3 (Peterson's Algorithm)
- turn과 flag[] 변수 모두 사용
- Process Pi
- 두 프로세스 모두가 Critical section에 들어가고 싶을 경우에만 turn 변수를 따지는 구조
- 세 가지 요구사항을 모두 만족하지만, Busy Waiting(=Spin Lock) 문제
- CPU와 Memory를 계속 사용하면서 대기 !
Synchronization Hardware
- Interrupt는 Instruction 단위로 발생
- Instruction 하나에 읽기와 쓰기가 가능해진다면?
- 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우, 문제의 해결 가능
- a가 0이든 1이든 a를 읽은 후, 1로 변경
- Mutual Exclution with Test & Set
Semaphores
- 이전 방식들을 추상화시킨 방법
- Semaphore S(자원의 갯수)
- integer variable
- 아래의 두 가지 atomic 연산에 의해서만 접근 가능
- P 연산은 자원을 가져가는 행위
- V 연산은 자원을 반납하는 행위
Block / Wakeup Implementation
- block과 wakeup를 다음과 같이 가정
- block: 커널은 block을 호출한 프로세스를 suspend. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
- wakeup(P): block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮김
- cf. S.value를 빼고 잠 들었기 때문에, 내가 value를 내놓았음에도 value가 0 이하라는 것은 누군가가 잠들어 있다는 의미
Busy-wait vs. Block/wakeup
- Block/wakeup overhead vs. Critical section 길이
- Critical section의 길이가 긴 경우 Block/wakeup이 적당
- Critical section의 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
- 일반적으로는 Block/wakeup 방식이 더 좋음
Two types of Semaphores
-
Counting semaphore
- 도메인이 이상인 임의의 정수값
- 주로 resource counting에 사용
-
Binary semaphore(= mutex)
- 0 또는 1 값만 가질 수 있음
- 주로 Mutual Exclusion(lock/unlock)에 사용
Deadlock and Starvation
- Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
- 자원을 요구하는 순서의 변경을 통해 해결이 가능
- Starvation: indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
