메모리 주소공간(S-box), CPU 프로세서(E-box) → Multiprocessor system
공유메모리를 사용하는 프로세스들
커널 내부 데이터를 접근하는 루틴들 간(예: 커널모드 수행 중 인터럽트로 커널모드의 다른 루틴 수행 시)
Race condition 1 - OS에서 Interrupt handler vs kernel
kernel 명령 수행 중, interrupt 차단
커널모드 running 중 interrupt가 발생하여 인터럽트 처리 루틴이 수행
양쪽 다 커널 코드이므로, kernel address space 공유
Race condition 2 - 프로세스가 시스템 콜을 하여 커널 모드로 수행 중인데, context switch가 일어나는 경우
u : user mode / k : kernel mode
해결책 : 커널 모드에서 수행 중일 때는 CPU를 선점(preempt)하지 않고, 사용자 모드로 돌아갈 때 선점
Race condition 3 - Multiprocessor에서 shared memory 내의 kernel data
방법 1) 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법 (커널 전체에 대해 lock / unlock) → 비효율
방법 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해 lock / unlock을 하는 방법
Process Synchronizatino 문제
공유 데이터의 동시 접근(Concurrent access)은 데이터의 불일치 문제(Inconsistency) 발생 가능성
일관성(Consistency) 유지를 위해 협력 프로세스 간 실행 순서 정해주는 메커니즘 필요
Race condition
여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
Race condition을 막기 위해 → Concurrent process는 동기화(Synchronize)되어야 한다.
The Critical-Section Problem
Critical-Section : 공유 데이터를 접근하는 코드
n개의 프로세스가 공유 데이터를 동시에 사용하기 원하는 경우
각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical-section이 존재
Problem : 하나의 프로세스가 critical section에 있을 때, 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다
Critical-Section 문제를 해결하기 위한 초기의 시도
아래는 프로세스들의 일반적인 구조
do {
entry section
critical section
exit section
remainder section
} while (1);
프로세스들은 Synchronize를 위해 몇몇 변수를 공유할 수 있다 → Synchronization variable
아래에서 문제 해결을 알아보자
프로그램적 해결법의 충족 조건
Mutual Exclusion (상호 배제)
한 프로세스가 Critical-section 부분을 수행 주이면, 다른 모든 프로세스들은 각자의 Critical-section에 들어가면 안 된다.
Progress
아무도 Critical-section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있다면 들어가게 해주어야 한다.
Bounded Waiting (유한 대기)
프로세스가 critical section에 들어가려고 요청한 후부터 허용될 때까지, 다른 프로세스들이 critical section에 들어가는 횟수에는 한계가 있어야 한다.
** 두 개의 프로세스 P1, P2가 있다고 가정
Algorithm 1
Synchronization variable : turn 사용
P0 프로세스의 코드
int turn = 0; // => Pi는 turn == i일 때 critical section에 들어갈 수 있음
do {
while (turn != 0); // 자기 차례가 아니면 while문에서 대기
critical section
turn = 1;
remainder section
} while (1);
→ Bounded waiting을 지키지 못함
Algorithm 2
Synchronization variables
boolean flag[2];
initially flag[all] = false;
flag[i] == trun → Pi가 CS에 들어갈 준비가 되었다.
Process Pi
do {
flag[i] = true;
while (flag[j]) ; // Pj가 CS에 있으면 while문에서 대기;
critical section
flag[i] = false // CS에서 나갈 때 flag를 false로
remainder section
} while (1);
Mutual Exclusion을 만족하지만, Progress를 만족하지 않음
두 프로세스가 모두 2행까지 수행 후, 끊임 없이 양보하는 상황이 발생할 수 있음
Algorithm 3 (Peterson’s Algorithm)
Algorithm 1, 2의 synchronization variables를 합친 알고리즘
Process Pi
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j); // 상대가 CS에 들어가려하고, 상대 턴이면 대기
critical section // 상대가 CS에 들어갈 의사가 없거나, 의사는 있지만 상대 차례가 아니면 진입
flag[i] = false;
remainder section
} while (1);
3가지 충족 조건을 모두 만족; 2개의 프로세스에 대한 Critical-Section 문제를 해결
Problem : Busy Waiting!(=Spin lock) (계속 CPU와 Memory를 쓰면서 wait)
while문을 계속 돌면서 lock을 건다.
Synchronization Hardware
하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원한다면, 앞의 문제는 간단히 해결
읽기와 쓰기가 하나의 Instruction으로 실행 → 도중에 CPU를 뺏기지 않음
a가 0이면 → 0을 읽어오고 1로 수정
a가 1이면 → 1을 읽어오고 1로 수정
Mutual Exclusion with Test & Set
// Synchronization variable:
boolean lock = false;
// Process Pi
do {
while (test_and_set(lock));
// lock이 0이면 -> 아무도 CS에 있지 않음 -> while문을 통과하고 1로 수정
// lock이 1이면 -> while문에서 대기
critical section
lock = false;
remainder section
} while (1);
여전히 Busy waiting 문제 발생
Semaphores
앞의 방식들을 추상화시킴
추상 자료형을 사용 → 컴퓨터 내부에 구현된 실제 자료구조와 별개로, Object와 연산을 가지고 있는 자료형
Semaphore S
Integer variable
아래의 두 가지 atomic 연산에 의해서만 접근 가능
P(S) → 공유 데이터를 획득하는 과정
while(S≤0) do no-op; → wait / 여전히 busy waiting
S—;
V(S) → 사용 후 반납하는 과정
S++;
Critical Section of n Processes
// Synchronization variable;
Semaphore mutex; // initially 1: 1개가 CS에 들어갈 수 있다
// Process Pi
do {
P(mutex); // 양수면 감소시키고 CS 진입, 아니면 wait
critical section
V(mutex); // Semaphore 증가
remainder section
} while (1);
Block / Wakeup Implementation
CS 진입 차례가 아닌 프로세스를 block해 Busy waiting 문제 해결
Semaphore를 아래와 같이 정의
typedef struct
{
int value; // semaphore
struct process *L; // process wait queue
} semaphore;
block : 호출한 프로세스를 suspend 시키고, 해당 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
wakeup(P) : 블록된 프로세스 P를 wakeup / 해당 프로세스의 PCB를 Ready queue로 옮김
P(S)
S.value--; // prepare to enter
if (S.value < 0) // 음수면 block
{
add this process to S.L //
block();
}
V(S)
S.value++;
if (S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}
추상 자료형에서 S는 자원의 개수를 나타냈지만, 지금 S.value는 기다리는 프로세스의 개수를 나타내는 값(음수로)
Busy-wait vs Block/Wakeup
Critical section의 길이가 긴 경우 Block/Wakeup이 적당
Critical section의 길이가 매우 짧은 경우 → Block/Wakeup 오버헤드가 Busy-wait 오버헤드보다 더 커질 수 있음
일반적으로는 Block/Wakeup 방식이 더 좋음
Semaphore의 종류
Counting Semaphore
도메인이 0 이상인 임의의 정수값
주로 자원이 여러 개일 때, Resource counting에 사용
Binary Semaphore (=mutex)
0 또는 1 → 자원이 1개
주로 Mutual exclusion(lock/unlock)에 사용
Deadlock and Starvation
Deadlock(교착 상태) : 둘 이상의 프로세스가, 서로 상대방의 의해 충족될 수 있는 event를 무한히 기다리는 현상
S, Q가 1로 초기화된 Semaphore라 하자
Starvation
프로세스가 suspend된 이유에 해당하는 Semaphore 큐에서 빠져나갈 수 없는 현상
Bounded-Buffer Problem
mutex, empty, full 은 각각의 Semaphore
mutex는 전체 lock/unlock을 관장
Readers-Writers Problem
한 프로세스가 DB에 write 중일 때, 다른 프로세스가 접근하면 안됨
Read는 여럿이 동시에 해도 됨
readcount(Shared data) : 현재 DB에 접근 중인 Reader의 수
mutex(Synchronization variable) : readcount 접근(critical section)의 mutual exclusion 보장을 위해 사용
db : Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
처음 읽을 때 db에 P, 다 읽고 나갈 때 더이상 Reader가 없다면 V(db)
Reader가 다 빠져나가야만 Writer가 DB에 접근 가능
→ Starvation 발생 가능!
Dining-Philosophers Problem
Philosopher의 행동
밥 먹기 (양쪽 젓가락을 잡고)
생각하기 (양쪽 젓가락을 놓고)
위의 Solution의 문제점 : Deadlock의 가능성이 있음
모두가 왼쪽 젓가락을 잡게 되면 → 오른쪽 젓가락을 잡는 코드를 모두가 기다리게 됨
해결 방안
n-1명의 철학자만 테이블에 동시에 앉을 수 있도록 한다.
젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집게 한다.
비대칭 : 짝수 철학자는 왼쪽, 홀수 철학자는 오른쪽 젓가락부터 집도록
2번 해결 방안에 대한 코드
Semaphore의 문제점
코딩하기 힘들다
정확성의 입증이 어렵다
자발적 협력이 필요하다
한 번의 실수가 모든 시스템에 치명적 영향
→ Monitor 도입
Monitor
프로그래밍 언어 레벨에서 제공하는 High-level synchronization construct
동시 수행 중인 프로세스 사이에서 Abstract data type의 안전한 공유를 보장
내부의 프로시저를 통해서만 공유 데이터에 접근할 수 있게 만듦
Monitor는 그 자체가 하나의 프로세스만 접근할 수 있음 (lock을 따로 걸 필요가 없다)
