제 6장 프로세스 간 동기화 및 통신 6.1 개요 6.2 병행 처리의 문제점 병행 프로세스들은 서로 독립적으로 수행될 수도 있으며, 때로는 다른 프로세스들과의 협력을 통해서 기능을 수행하는 비동기적(asynchronous) 수행이 될 수도 있다. 6.2 병행 처리의 문제점 병행 처리 문제점 공유 자원의 상호 배타적인 사용(mutual exclusion) 하나의 기능을 공동으로 사용하여 수행하는 두 프로세스 간의 동기화 문제(synchronization) 자료 교환을 위한 메시지 전달 방식과 같은 통신 문제(communication) 두 개 이상 프로세스의 실행 순서와는 무관하게 항상 같은 결과를 얻을 수 있어야 하는 문제(determinancy) 교착상태 문제(deadlock) 프로그래밍 언어를 통한 병행 처리 문제(concurrent programming) 올바른 실행을 검증하는 문제(verification) Slide 1 (of 22)

6.2.1 임계구역 프로세스가 공유자료를 변경하는 코드 영역 하나의 프로세스만 공유 데이터에 대해 배타적으로 접근하고 나머지 프로세스들은 공유 데이터의 접근할 필요가 있더라도 기다려야 한다. 임계구역은 가능한 한 빨리 수행되어야만 하며, 프로세스가 임계구역에 들어간 후 프로세스가 블럭 상태로 되어서는 안 된다. Slide 2 (of 22)

shared double account; 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 원일 수 있다. 공유 변수를 접근하고 있는 하나의 프로세스 이외에는 다른 모든 프로세스들이 공유 변수를 접근하지 못하게 제어하는 기법을 상호 배제라 한다. Slide 3 (of 22)

합리적인 카운팅을 위한 상호 배제 프리미티브 mutual_exclusion() { int account; p1() { while(true) { get_account(); enter_mutex(); account = account + 10000; exit_mutex(); } p2() { account = account - 10000; account = 10000; parbegin p0(); p1() parend Slide 4 (of 22)

6.3 상호배제 프리미티브 임계구역 해결을 위한 3가지 요구 조건 6.3.1 1단계 프리미티브 상호배제(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 (turn == 0) ; turn = 0; turn=0; parbegin p0(); p1(); parend Slide 5 (of 22)

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 (p0_using == TRUE) ; p1using = TRUE; p1_using = FALSE; p0_using=false; p1_using=false; parbegin p0(); parend 상호 배제가 보장되지 않는다. Slide 6 (of 22)

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() { p1_using = TRUE; while (p0_using) ; p1_using = FALSE; p0_using=false; p1_using=false; parbegin p0(); p1(); parend 교착상태 발생 Slide 7 (of 22)

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 remainder section p1() { p1_using = true; while (p0_using) { p1_using := false; /* give p0 a chance */ p1_using := true p0_using=false; p1_using=false; parbegin p0(); p1(); parend 진행 조건 불만족 Slide 8 (of 22)

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); } critical section favored_process = 1; remainder section p1() { p1_using = true; while (p0_using) { if (favored_process == 0) p1_using = false; while (favored_process == 0); p1_using = true favored_process = 0; favoredprocess = 0; parbegin p0(); p1(); parend Slide 9 (of 22)

Slide 10 (of 22)

참고1: Lamport의 Bakery 알고리즘 Slide 11 (of 22)

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() { parbegin p0(); p1() parend Slide 12 (of 22)

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처럼 분리될 수 없는 원자적 연산이다 Slide 13 (of 22)

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 Slide 14 (of 22)

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() { P(number_deposited); next_result = number_buffer; write(next_result); Slide 15 (of 22)

참고2: 식사하는 철학자 문제 공유 데이터: Semaphore chopStick[] = new Semaphore[5]; Slide 16 (of 22)

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(조건 변수 이름) Slide 17 (of 22)

6.6.2 사용 예 식사하는 철학자 문제 철학자 작업 DP.pickup(i) eat DP.putdown(i) 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++) 철학자 작업 DP.pickup(i) eat DP.putdown(i) Slide 18 (of 22)

환형 버퍼를 사용한 생산자/소비자 문제 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; Slide 19 (of 22)

읽기-쓰기 문제 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; Slide 20 (of 22)

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? Slide 21 (of 22)

참고 3: 메시지를 사용한 유한 버퍼 생산자/소비자 문제의 해 Slide 22 (of 22)