CH5. Process Synchronization

#배경

*프로세스는 병행 OR 병렬도 실행

데이터의 비일관성

: 언제든지 실행 중 인터럽트 당할 수 있고 부분적으로 완료될 수 있다

*문제 상황

협력적인 순차적 프로세스 OR 스레드로 구성된 시스템

비동기적으로 수행하면서 데이터 공유

ㄴ생산자-소비자 문제: 메모리 공유(=유한 버퍼)

*Problem: Producer/ Consumer

문제: 동기화를 위해 (BUFFER_SIZE – 1)개 까지만 버퍼 사용

-Producer

while (true) {
	/* produce an item in next produced */
	while (((in+1) % BUFFER SIZE) == out);
		/* do nothing */
	buffer[in] = next_produced;
	int = (in + 1) % BUFFER_SIZE;
}

-Consumer

while (true) {
	while (in == out);
		/* do nothing */
	next_consumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	/* consume the item in next consumed */
}

*Solution: Producer/ Consumer

-Producer

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

while (true) {
	while (counter == 0)
		; /* do nothing */
	next_consumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	counter--;
	/* consume the item in next consumed */
}

*경쟁 상황(Rare Condition)

-counter++ 구현 

register1 = counter
register1 = register + 1
counter = register1

 

-counter— 구현 

register2 = counter
register2 = register2 – 1
counter = register2

 

ex. count = 5일 때 다음과 같은 실행 된다면,

S0: producer execute register1 = counter {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 – 1 {register2 = 4}
S4: producer execute counter = register1 {counter = 6 }
S5: consumer execute counter = register2 {counter = 4}

 

#임계 구역(The Critical-Section)

: 공유 변수 조작, 테이블 갱신, 파일 쓰기 등과 같은 작업 수행

/ 동기화 문제를 일으킬 수 있는 영역

*Pi 프로세스의 일반적인 구조

do {
	entry section
		critical section
	exit section
		remainder section
} while (true);

*임계 구역 문제

n 개의 프로세스 {p0, p1, … pn-1}로 구성된 시스템을 고려하자

각 프로세스는 코드 중에 임계 구역 세그먼트를 가짐

ㄴ임계 구역에 하나 프로세스 존재 -> 다른 프로세스 임계 구역에 절대 진입 X

진입 구역(entry section): 임계 구역에 진입하기 위해서는 허가 요청

/퇴출 구역(exit section) / 나머지 구역(remainder section)

*임계 구역 문제의 해결책의 요구조건

-상호 배제(mutual exclusion)

: 프로세스 Pi가 자기의 임계구역에서 실행

-> 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 X

 

-진행(progress) : 자기의 임계구역에서 실행되는 프로세스 X

+ 그들 자신의 임계구역으로 진입하려는 프로세스 O

-> 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 임계구역에 진입할 프로세스를 결정하는 데 참여할 수 O, 이 선택은 무한정 연기될 수 X

 

-한정된 대기(bounded waiting)

: 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 자신들의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다

 

#Peterson’s Solution

: 고전적인 소프트웨어 기반 해결책

두 프로세스 경우 해결책: Pi, Pj (i = 0, j = 1)_두 변수를 공유

int turn; // 어느 프로세스가 임계 구역에 진입할 차례인지 나타냄

Boolean flag[2]

// 프로세스가 임계 구역으로 진입할 준비가 되었다는 것을 나타냄

*Process Pi의 알고리즘

do {
	// 진입구역(critical section)
	flag[i] = true;
	turn = j;
	while (flag[j] && turn == j);
	// 퇴출구역(remainder section)
	flag[i] = flase;
} while (true);

 

상호 배제가 제대로 지켜진다는 사실

Pi eners CS only if:
	either flag[j] = false or turn = i;

진행 요구조건을 만족한다는 사실

대기 시간이 한없이 길어지지 않는다는 사실

 

#동기화 하드웨어(Synchronization Hardware)

: 이후 설명하는 모든 해결책은 락킹(locking)이라는 아이디어에 기반

*단일처리기 환경

-공유변수가 변경되는 동안 인터럽트 발생 허용X

-비선점형 커널

-다중처리기 시스템에서 적용X

현대 기기는 특별한 원자적 하드웨어 명령 제공

ㄴ원자적(atomic) = 인터럽트 될 수 없는

*락을 사용한 임계 구역 문제의 해결책

do {
	acquire lock
		critical section
	release lock
		remainder section
} while (true);

*test_and_set 명령어

정의:

boolean test_and_set (boolean *target) {
	boolean rv = *target;
	*target = TRUE:
	return rv;
}

원자적으로 실행

전달된 매개변수의 현재 값을 반환

변환된 매개변수의 새 값을 “TRUE”로 세팅

 

-구현_Boolean형 공유 변수 lock, FALSE로 초기화

do {
	while (test_and_set (&lock))
		; /* do nothing */
	/* critical section */
	lock = false;
	/* remainder section */
} while (true);

*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”의 현재 값을 반환

“*value == expected”일 경우에만 변수 “value”의 값을 전달된 매개변수인 “new_value”로 세팅한다. 이 조건이 만족될 때만 교환이 일어난다

 

-구현_정수형(integer) 공유 변수 “lock”(0으로 초기화)

do {
	while (compare_and_swap (&lock, 0, 1) != 0)
		; /* do nothing */
	/* critical section */
	lock = 0;
	/* remainder section */
} while (true);

*한정대기를 만족시키는 구현(with test_and_set)

do {
	waitin[i] = true;
	key = true;
	while (waiting[i] && key)
		key = test_and_set(&lock);
	waiting[i] = false;
	/* critical section */
	j = (i + 1) % n;
	while ((j != i) && !waiting[j])
		j = (j + 1) % n;
	if (j == I)
		lock = false;
	else
		waiting[j] = flase;
	/* remainder section */
} while (true);

 

#Mutex Locks

이전 해결책은 복잡하고, 응용프로그래머는 접근할 수 X

OS 설계자들은 임계 구역 문제 해결 위한 소프트웨어 툴 설계

ㄴmutex 락(mutex = mutual exclusion)

락을 얻기(acquire()) -> 임계구역 -> 락 해제(release()) => 임계구역 보호

ㄴboolean available: 락의 가용여부를 가지는 변수

acquire() 및 releas() 호출은 원자적_보통 하드웨어 원자적 명령 ~> 구현

문제점: 바쁜 대기(busy waiting) / 스핀락(spinlock)

/ 동기화 하드웨어도 동일한 문제/ CPU 낭비

*acquire() and relase()

acquire() {
	while (!available)
		; /* busy wait */
	available = false;
}
relase() {
	available = true;
}

 

do {
	acquire lock
		crititical section
	relase lock
	remainder section
} while (true);

 

#세마포(Semaphores)

: Mutex 락보다 더 정교한 방식을 제공하는 동기화 도구

세마포 S-integer형 변수

*2가지 원자적 연산 ~> 접근 가능O

wait() and signal()_Originally called P() and Y()

-wait() operation의 정의

wait (S) {
	wait (S <= 0)
	; // busy wait
	S--;
}

 

-signal() operation의 정의

siganl (S) {
	S++;
}

 

*세마포 사용법

-이진 세마포(Binary semaphore)

: 0과 1값만을 가질 수 있는 integer 변수

/ mutex lock과 같음

 

-카운팅 세마포(Counting semaphore)

: 제한 없는 영역에 정의되는 integer 변수

다양한 동기화 문제를 해결할 수 있음

S1이 S2보다 먼저 실행되어야하는 요구 조건을 가지는 P1과 P2

P1:
	S1;
	signal (synch);

P2:
	wait (synch);
	S2;

*바쁜 대기 없는 세마포 구현

-바쁜 대기 대신에 프로세스 자신을 봉쇄

각 세마포에 대한 대기 큐 존재

프로세스를 대기 큐에 넣고, 상태 -> 대기상태

다른 프로세스가 signal()연산 -> wakeup()연산 ~> 다시 시작

ㄴ대기 상태 -> 준비완료 상태

 

-대기 큐의 각 항목 두 데이터 저장

ㄴ값(integer 형)/ 리스트의 다음 레코드를 가리키는 포인터

 

-2가지 연산

block() - 연산을 호출한 프로세스를 적절한 대기 큐에 넣는다

wakeup() - 대기 큐의 프로세스 중 하나를 제거하여 준비 큐에 넣는다

 

-세마포 정의

typedef struct {
	int value;
	struct process *list;
} semaphore;
wait (semaphore *S) {
	S->value--;
	if (S->value < 0) {
		add this process to S->list;
		block ();	
	}
}

signal (sempahore *S) {
	S->value++;
	if (S->vlaue <= 0) {
		remove a process P from S->list;
		wakeup(P);
	}
}

*세마포 구현

세마포 대기큐 <- FIFO 큐로 구현

두 프로세스가 같은 세마포에 대해 동시에 wait()와 signal()을 호출X

ㄴ구현 시 wait와 signal 코드를 임계 구역에 두어야함

(단일 처리기 환경_비선점 방법/ 다중 처리기 환경_동기화 하드웨어 기법 적용)

*교착상태(Deadlock)와 기아(Starvation)

-교착상태(Deadlock)

: 둘 이상의 프로세스가 대기 중이고 이 중 하나만이 발생시킬 수 있는 이벤트를 영원히 기다리는 상태

S와 Q를 1로 초기화된 두 세마포라고 하자

P0 P1

wait (S); wait (Q);

wait (Q); wait (S);

... ...

signal (S); signal (Q);

signal (Q); signal (S);

 

-무한 봉쇄(indefinite blocking) OR 기아(Starvation): 결과

교착생태 -> 기아상태 but, 기아상태 원인은 교착상태만 있는 것 X

 

#Classic Problem of Synchronization

: 새로 제안된 동기화 기법을 검증하기 위해 사용되는 고전적인 문제

*한정-버퍼 문제(Bounded-Buffer Problem)

sige = n인 버퍼

공유하는 자료구조(초기화)

semaphore mutex = 1;
sempahore empty = n;
semaphore full = 0;

-해결방법

생산자 프로세스

do {
	...
	/* produce an item in next_produced */
	...
	wait(empty);
	wait(mutex);
	...
	/* add next produced to the buffer */
	...
	signal(mutex);
	signal(full);
} while (true);

 

소비자 프로세스 구조

do {
	wait(full);
	wait(mutex);
	...
	/* remove an item from buffer to next_consumed */
	...
	signal(mutex);
	signal(empty);
	...
	/*consume the item in next consumed */
	...
} while (true);

*Readers-Writers Problem

다수의 병행 프로세스가 하나의 데이터베이스 공유

readers: only read, not write/ writers: read as well as write

문제: 동시에 여러 reader가 읽을 수O

/ writer는 한 순간에 오직 하나만 공유 데이를 접근

reader와 writer의 구성을 어떻게 하느냐에 따라 여러 변형 가능

ㄴ모두 우선순위를 부여하는 형태

 

-해결방법

문제: wirter가 공유 자원을 사용할 수 있는 허가 얻지X

-> 어느 reader도 기다리게 할 수X

즉, writer에게 접근 권한X -> 다른 reader들은 자원에 접근O

writer의 기아(starvation) 발생 가능

 

공유 데이터_데이터베이스

semaphore rw_mutex = 1; // writer들을 위한 상호배제 위해 사용
smeaphore mutex = 1; // read_count 갱신 시, 상호배제 위해 사용
int read_count = 0; // 현재 몇 개의 프로세스들이 객체를 읽고 있는가

 

reader 프로세스 구조

do {
	wait(mutex);
	read_count++;
	if(read_count ==1)
		wait(rw_mutex);
	signal(mutex);
	...
	/* reading is performed */
	...
	wait(mutex);
	read count--;
	if(read_count == 0)
		signal(rw_mutex);
	signal(mutex);
} while (true);

 

writer 프로세스 구조

do {
	wait(rw_mutex);
	...
	/* writing is performed */
	...
	signal(rw_mutex);
} while (true);

 

*식사하는 철학자(Dinning-Philosophers) Problem

-문제

철학자는 사색-식사 번갈아 하는 일생

이웃 철학자와 대화X/ 배고플 경우 양쪽 2개의 젓가락을 동시에 집어 음식 먹음

/ 식사 후 2개 동시에 내려 놓음

5명의 철학자가 있는 경우

공유데이터

: 음식이 들어 있는 그릇(데이터)/ 젓가락(semaphore chopstick [5] = {1};

 

-해결방법

철학자 I의 구조

do {
	wait(chopstick[i];
	wait(chopstick[(i + 1) % 5]);
		// eating
	signal(chopstick[i]);
	signal(chopstick[(i + 1) % 5]);
		// thinking
} while (TRUE);

만약, 5명의 철학자가 동시에 오른쪽 OR 왼쪽 젓가락 들 경우

-> 교착상태(deallock) OR 기아(starvation)

 

-교착상태 해결방법(교착상태 해결 = 기아 해결X)

동시에 최대 4명의 철학자만 테이블에 앉을 수 있도록 허용/ 철학자는 양 젓가락이 모두 가용할 때만 젓가락 집도록 허용(집기는 임계구역에서만)

비대칭 해결책

ㄴ홀수 번호 철학자_왼편 젓가락 -> 오른편 젓가락

/ 짝수 번호 철학자_오른편 젓가락 -> 왼편 젓가락

 

#Monitors

*등장 배경

: 세마포 연산의 잘못된 사용에 의한 세마포 문제

-상호 배제 조건 위반: signal(mutex) ... wait(mutex)

 

-교착상태 발생: wait(mutex) ... wait(mutex)

 

-상호 배제 조건 위반 및 교착 상태: wait(mutex) or siganl(mutex) (or both)

순수한 프로그래밍의 오류 OR 비협조적인 개발자에 의해 발생

*모니터(Monitors) = 공유자원 + 공유자원 접근 함수, 2개 큐

: 프로세스 동기화를 위한 편리하고 효과적인 기법을 제공하는 고수준 동기화

-상호배제 큐

: 공유자원에 하나의 프로세스만 진입하기 위한 큐

 

-조건동기 큐

: 이미 공유자원을 사용하고 있는 프로세스가 진입할 수 있는 큐

ㄴwait(), notify(), notifyall()

 

*자바 모니터: 모니터를 제공하는 대표적 언어

ex.

class test{
	private int value // 공유 변수
	synchronized void test1() {
		...//
	}
	synchronized void test2() {
		...//
	}
	void test3() {
	...//
	}
}

*다리 건너기 예제

통행은 한 방향으로만 가능/ 다리의 각 섹션은 지원

 

-해결책

: 교착상태 일어나면 한 자동차가 후진하여 문제를 해결 가능(자원 선점과 롤백)

/ 교착상태 일어나면 여러 자동차가 후진해야 할 수도 있음

/ 대부분의 운영체제는 교착g상태를 예방하거나 처리X

기아도 발생 가능O

 

#교착 상태

*문제

각자 자원을 가지고 있으며 자신이 속한 집합의 다른 프로세스가 가지고 있는 자원의 획득을 기다리는 프로세스들의 집합

-자원 사용 순서: 요청 /사용/ 방출

 

-자원 요청과 방출_시스템콜

장치: request(), release()

파일: open(), close()

메모리: allocate(), free()

 

*특성

: 4가지 조건 동시에 만족시 발생

-상호 배제(Mutual exclusion)

: 한 순간에 오직 하나의 프로세스만이 자원을 사용O

 

-점유하며 대기(Hold and wait)

: 적어도 하나 이상의 자원을 가진 프로세스가 다른 프로세스가 가진

추가의 자원을 획득하기 위해 대기

 

-비선점(No preemption)

: 프로세스가 가진 자원은 오로지 사용이 끝난 후, 자발적으로만 방출

 

-순환 대기(Circular wait)

: 프로세스 집합 {P0, P1, ..., Pn}이 존재할 때, P0은 P1이 가지고 있는 자원을 기다리고, Pn-1은 Pn이 가지고 있는 자원을 기다리고, 마지막으로 Pn은 P0이 가지고 있는 자원을 기다리고 있는 상황

*교착상태를 핸들링하는 방법

-교착상태 예방(Deadlock prevention)

 

-교착상태 허용 후, 발생하면 정상 상태로 복구

 

-교착상태 회피(Deadlock avoidance)

ㄴ문제 무시 + 교착상태가 발생하지 않은 것처럼 행동

(UNIX 포함 대부분 운영체제 이 방법 사용)

 

#자원 할당 그래프(Resource-Allocation Graph)

노드와 집합 V와 간선의 집합 E

*V: 2가지 유형으로 구분

-P = {P0, P1, ..., Pn}, 시스템의 모든 프로세스로 구성된 집합

-R = {R0, R1, ..., Rm}, 시스템의 모든 자원으로 구성된 집합

*E: 2가지 유형으로 구분

-요청간선(request edge): directed edge Pi -> Rj

-할당간선(assignment edge): directed edge Rj -> Pi