제 6 장 프로세스 간 동기화 및 통신
6.1 개요
병행 프로세스들은 서로 독립적으로 수행될 수도 있으며 , 때로는 다른 프로 세스들과의 협력을 통해서 기능을 수행하는 비동기적 (asynchronous) 수행 이 될 수도 있다 .
6.2 병행 처리의 문제점
병행 처리 문제점
공유 자원의 상호 배타적인 사용 (mutual exclusion)
하나의 기능을 공동으로 사용하여 수행하는 두 프로세스 간의 동기화 문제 (synchronization)
자료 교환을 위한 메시지 전달 방식과 같은 통신 문제 (communication)
두 개 이상 프로세스의 실행 순서와는 무관하게 항상 같은 결과를 얻을 수 있어 야 하는 문제 (determinancy)
교착상태 문제 (deadlock)
프로그래밍 언어를 통한 병행 처리 문제 (concurrent programming) 올바른 실행을 검증하는 문제 (verification)
6.2.1 임계구역
• 프로세스가 공유자료를 변경하는 코드 영역
• 하나의 프로세스만 공유 데이터에 대해 배타적으로 접근하고 나머지 프로세스들은 공 유 데이터의 접근할 필요가 있더라도 기다려야 한다 .
• 임계구역은 가능한 한 빨리 수행되어야만 하며 , 프로세스가 임계구역에 들어간 후 프 로세스가 블럭 상태로 되어서는 안 된다 .
6.2.2 상호배제
• 한 프로세스만 임계구역에 진입
• 다수의 프로세스들이 하나의 공유 자원을 상호 배타적으로 사용할 수 있게 하면서 동 시에는 수행할 수 없도록 한다 .
• 예 )
shared double account;
트랜잭션 1 트랜잭션 2
1-1 read account;
1-2 subtract 10,000 won from account;
1-3 store account;
2-1 read account;
2-2 add 10,000 won to account;
2-3 store account;
• 트랙잭션 실행 순서에 따라 account 값은 10,000, 20,000, 0 원일 수 있다 .
• 공유 변수를 접근하고 있는 하나의 프로세스 이외에는 다른 모든 프로세스들이 공유 변수를 접근하지 못하게 제어하는 기법을 상호 배제라 한다 .
• 합리적인 카운팅을 위한 상호 배제 프리미티브
mutual_exclusion() { int account;
p1() {
while(true) { get_account();
enter_mutex();
account = account + 10000;
exit_mutex();
} } p2() {
while(true) { get_account();
enter_mutex();
account = account - 10000;
exit_mutex();
}
} account = 10000;
parbegin p0();
p1() parend }
6.3 상호배제 프리미티브
• 임계구역 해결을 위한 3 가지 요구 조건
상호배제 (mutual exclusion): 한 프로세스만 임계구역에 진입 .
진행 (progress): 임계구역에 진입할 프로세스 선택이 영원이 지연되지 않음 .
한계 대기 (bounded waiting): 한 프로세스가 임계구역 진입 요청 후 기다리는 데 한계가 있음 .
6.3.1 1 단계 프리미티브
• 1 단계 상호 배제 프리미티브
program mutex1() { boolean turn;
p0() {
while(true) {
while (turn == 1) ; critical_section;
turn = 1;
} }
p1() {
while(true) {
while (turn == 0) ; critical_section;
turn = 0;
} }
turn=0;
parbegin p0();
p1();
parend }
6.3.2 2 단계 프리미티브
• 2 단계 상호 배제 프리미티브
program mutex2() {
boolean p0_using, p1_using;
p0() {
while (true) {
while (p1_using == TRUE) ; p0using = TRUE;
critical section
p0_using = FALSE;
remainder section }
}
p1();
{ while (true) {
while (p0_using == TRUE) ; p1using = TRUE;
critical section p1_using = FALSE;
remainder section }
}
p0_using=false;
p1_using=false;
parbegin p0();
p1();
parend }
상호 배제가 보장되지 않는다 .
6.3.3 3 단계 프리미티브
• 3 단계 상호 배제 프리미티브
program mutex3() {
boolean p0_using, p1_using;
p0() {
while (true) {
p0_using = TRUE;
while (p1_using);
critical section
p0_using = FALSE;
remainder section } }
p1() {
while (true) {
p1_using = TRUE;
while (p0_using) ; critical section
p1_using = FALSE;
remainder section }
}
p0_using=false;
p1_using=false;
parbegin p0();
p1();
parend }
교착상태 발생
6.3.4 4 단계 프리미티브
• 4 단계 상호 배제 프리미티브
program mutex4() {
boolean p0_using, p1_using;
p0() {
while (true) { p0_using = true;
while (p1_using) { p0_using := false;
/* give p1 a chance */
p0_using := true } critical section
p0_using := false;
remainder section }
p1() {
while (true) { p1_using = true;
while (p0_using) { p1_using := false;
/* give p0 a chance */
p1_using := true }
critical section p1_using := false;
remainder section }
p0_using=false;
p1_using=false;
parbegin p0();
p1();
parend }
진행 조건 불만족
6.3.5 Dekker 의 알고리즘
• Dekker's 알고리즘
Dekker() {
int favored_process;
boolean p1using, p2using;
favored_process=0;
p0() {
while (true) { p0_using = true;
while (p1_using) {
if (favored_process == 1) then {
p0_using = false;
while (favored_process == 1);
p0_using = true;
} }
critical section
favored_process = 1;
p0_using = false;
remainder section }
}
p1() {
while (true) { p1_using = true;
while (p0_using) {
if (favored_process == 0) then {
p1_using = false;
while (favored_process == 0);
p1_using = true }
}
critical section
favored_process = 0;
p1_using = false;
remainder section } }
p0_using = false;
p1_using = false;
favoredprocess = 0;
parbegin p0();
p1();
parend }
참고 1: Lamport 의 Bakery 알고리즘
6.4 하드웨어에 의한 동기화
• 더 이상의 분할이 불가능한 명령문 test_and_set(target) 는 논리 변수 target 의 값을 temp 에 복사 한 후 target 을 true 로 설정하고 temp 값을 반환한다 .
• test_and_set 명령을 이용한 상호 배제
boolean test_and_set(boolean &target) { boolean temp = target;
target = true;
return temp;
}
testandsetexample() { boolean active;
p0() {
while (1) {
while (test_and_set(active));
critical section;
active = false;
remainder section }
}
p1() {
while (1) {
while (test_and_set(active));
critical section;
active = false;
remainder section }
}
active = false;
parbegin p0();
p1() parend }
6.5 세마포어
6.5.1 정의
• 세마포어는 P 와 V 그리고 semaphore_initialize( 세마포어의 초기값 설정 ) 라는 세 가지 오퍼레이션 (operation) 에 의해서만 접근될 수 있는 통제된 변수 (protected variable) 이다 .
• 세마포어 변수 S 는 2 진 세마포어 (binary semaphore) 의 경우 그 값이 0 또는 1 이 될 수 있고 , 산술 세마포어 (counting semaphore) 는 0 과 양의 정수를 그 값으 로 가질 수 있다 .
• P 와 V 는 test_and_set 처럼 분리될 수 없는 원자적 연산이다
6.5.2 프로세스 간 동기화
• 세마포어에 대한 block/wakeup 프로세스간 동기화
semaphore event_of_interest=0;
process_one() {
preliminary_stuff_one;
P(event_of_interest);
other_stuff_one }
process_two() {
preliminary_stuff_two;
V(event_of_interest);
other_stuff_two }
6.5.3 프로세스 간 통신
• 세마포어에 의한 프로세스 간 통신 : 생산자 소비자 문제
semaphore exclusive_access=1, number_deposited=0;
int number_buffer;
producer_process() { int next_result;
while (1) {
calculate_next_result();
P(exclusive_access);
number_buffer = next_result;
V(exclusive_access);
V(number_deposited) }}
consumer_process() { int next_result;
while (1) {
P(number_deposited);
P(exclusive_access);
next_result = number_buffer;
V(exclusive_access);
write(next_result);
}}
참고 2: 식사하는 철학자 문제
• 공유 데이터 : Semaphore chopStick[] = new Semaphore[5];
6.6 모니터
6.6.1 개요
• 모니터란 특정 공유 자원이나 한 그룹의 공유 자원을 할당하는 데 필요한 데이터 및 프 로 시저 를 포함하 는 병 행 성 구 조 (concurrency construct) 로 자 료 추상화 (data abstraction) 의 개념을 기초로 하고 있다 .
• 모니터의 선언 형식의 구조
monitorname : monitor;
{
declarations of private data; /* local monitor variables */
void pub_name(formal parameters) { /* public procedures */
procedure_body;
}
void priv_name() { /* private procedures */
initialization of monitor data;
};}
• 조건 변수 (condition variable)
wait( 조건 변수 이름 )
signal( 조건 변수 이름 )
6.6.2 사용 예
• 식사하는 철학자 문제
monitor DP {
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
void pickup (int i) { state[i] = HUNGRY;
test(i);
if (state[i] != EATING) self [i].wait;
}
void putdown (int i) { state[i] = THINKING;
// test left and right neighbors test((i + 4) % 5);
test((i + 1) % 5);
}
void test (int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) { state[i] = EATING ;
self[i].signal () ; }
}
initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING;
} }
• 철학자 작업
DP.pickup(i) eat
DP.putdown(i)
• 환형 버퍼를 사용한 생산자 / 소비자 문제
monitor ring_buffer_monitor;
char ring_buffer[N];
int next_slot_to_fill, next_slot_to_empty;
int slot_in_use;
condition ring_buffer_has_data, ring_buffer_has_space;
void fill_a_slot(char x) {
if (slot_in_use == N) wait(ring_buffer_has_space);
ring_buffer[next_slot_to_fill] = x;
slot_in_use = slot_in_use + 1;
next_slot_to_fill = (next_slot_to_fill + 1) mod N;
signal(ring_buffer_has_data);
}
void empty_a_slot(char x) {
if (slot_in_use == 0) wait(ring_buffer_has_data);
x = ring_buffer[next_slot_to_empty];
slot_in_use = slot_in_use -1;
next_slot_to_empty = (next_slot_to_empty - 1) mod N;
signal(ring_buffer_has_space);
} {
slot_in_use = 0;
next_slot_to_fill = 0;
next_slot_to_empty = 0;
• 읽기 - 쓰기 문제
monitor readers_and_writers;
int readers;
boolean someone_is_writing;
condition reading_allowed, writing_allowed;
void begin_reading() {
if (someone_is_writing || queue(writing_allowed)) wait(reading_allowed);
readers = readers + 1;
signal(reading_allowed);
}
void finished_reading() { readers = readers - 1;
if (readers == 0) signal(writing_allowed);
}
viod begin_writing() {
if (readers > 0 || someone_is_writing) wait(writing_allowed);
someone_is_writing = true;
}
viod finished_writing() { someone_is_writing = false;
if (queue(reading_allowed)) signal(reading_allowed);
else signal(writing_allowed);
} {
readers = 0;
someone_is_wrting = false;
}
6.7 메시지
• 많은 운영체제들이 몇 가지 종류의 프로세스 간 통신을 지원하기 위하여 메시 지 메커니즘을 채택하고 있다 .
• 컴퓨터 네트워크에서 노드 간의 통신은 주로 메시지를 주고받음으로써 이루 어지고 , 이는 프로세스 간 통신 및 동기화를 자연스럽게 지원한다 .
• 메시지 시스템 구현
How are links established?
Can a link be associated with more than two processes?
How many links can there be between every pair of communicating processes?
What is the capacity of a link?
Is the size of a message that the link can accommodate fixed or variable?
Is a link unidirectional or bi-directional?
