동기화(Synchronization)

협력적 프로세스(Cooperating Process)

협력적 프로세스란?

• 동시에 실행되며 서로 영향을 끼치는 프로세스들
• 데이터를 공유하는 프로세스들

동시 처리 (concurrent processing)

• 협력적 프로세스들이 동시에 공유 데이터에 접근해서 연산작업을 수행하는 것
• 하나의 프로세스에 의해 데이터 접근 및 조작을 동일한 데이터에 접근한 기존 프로세스의 연산 작업에 영향을 끼침

데이터 불일치(data inconsistency)

• 협력적 프로세스들이 서로 다른 공유 데이터 값을 가지고 연산 작업을 처리
• 통제되지 않은 협력적 프로세스 실행 순서에 의해 발생

은행 공유 계좌 문제

입금 및 인출을 위한 협력적 프로세스 처리

• 두 개의 협력적 프로세스 A와 B가 은행 공유 계좌에 접근
• 프로세스 A는 계좌에 돈을 입금(deposit)
• 프로세스 B는 계좌로부터 돈을 인출(withdraw)

deposit() 함수

int deposit(account,money)
{
	balance = get_balance(account);
	balacne = balance + money;
	put_palance(account, balance);
	return balance;
}

withdraw() 함수

생산자와 소비자 문제

int withdraw(account, money)
{
	balance = get_balance(account);
	balance = balance - money;
	put_balance(account, balance);
	return balance;
}생산자와 소비자 문제

협력적 생산자(producer) 및 소비자(consumer) 프로세스

• 생산자 프로세스는 버퍼에 데이터를 삽입(produce)
• 소비자 프로세스는 버퍼로부터 데이터를 사용(consume)

무한 버퍼(unbounded-buffer)

• 버퍼의 저장 크기에 한계가 없음
• 생산자는 대기를 할 필요가 없음
• 버퍼가 비어있는 경우 소비자는 대기해야 함

유한 버퍼(bounded-buffer)

• 버퍼의 저장 크기에 한계가 존재
• 버퍼가 가득 차 있는 경우 생산자는 대기해야 함
• 버퍼가 비어있는 경우 소비자는 대기해야 함

유한 버퍼 구현

• 두 개의 논리 포인터 in, out을 가지는 원형 배열로서 구현
• 변수 in : 버퍼 내에서 다음으로 비어 있는 index를 가리킴
• 변수 out : 버퍼 내에서 첫 번째로 차 있는 index를 가리킴
• in > out : 버퍼에 데이터가 존재함
• in == out : 버퍼가 비어있음(empty)
• (in + 1)%BUFFER_SIZE == out : 버퍼가 가득 차 있음(full)

생산자 및 소비자 프로세스 구현을 위한 첫 번째 코드

• 생산자 프로세스
  • 새로운 아이템(=next_produced) 생성
  • 버퍼에 저장

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

• 소비자 프로세스
  • 버퍼로부터 아이템(=next_consumed) 꺼냄
  • 아이템 소비

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

생산자 및 소비자 프로세스 구현을 위한 두 번째 코드

• 버퍼의 모든 여유 공간을 전부 활용
• 새로운 정수형 변수 count를 정의해서 버퍼 상태를 인지
• 먼저 count를 0으로 초기화
• 생산자 프로세스가 아이템을 버퍼에 넣으면 count를 1 증가
• 소비자 프로세스가 버퍼에서 아이템을 꺼내면 count를 1 감소
• count == BUFFER_SIZE : 버퍼가 가득 참(full)
• count == 0 : 버퍼가 비어있음(empty)

while(true){
	/* produce an item in next_produced */

	while(count == BUFFER_SIZE)
		; /* do nothing */
	
	buffer[in] = next_produced;
	in = (in + 1) % BUFFER_SIZE:
	count++;
}

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

경쟁 상황(Race Condition)

경쟁 상황

• 여러 개의 프로세스가 동일한 자료에 접근 및 조작
• 이때, 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황

생산자 프로세스

• count++ 구현 코드
• register1 = count register1 = register1 + 1 count = register1

소비자 프로세스

• count-- 구현 코드
• register2 = count register2 = register2 - 1 count = register2

경쟁 상황 발생 예시

• count = 5인 상황에서의 경쟁 상황 발생 과정

• 생산자-소비자 프로세스 구현을 위한 첫 번째 코드와 달리, 두 번째 코드에서 경쟁 상황 문제가 발생한 이유는?
  • 첫번째 코드에서는 생산자, 소비자가 동시에 접근하는 공유 변수가 없었지만 두번째 코드에서는 공유 변수(count)가 있기 때문

임계영역(Critical Section)

임계 영역(critical section)

• 공유 데이터가 존재하는 프로세스 코드 영역
• 동시에 두 개 이상의 프로세스가 진입할 수 없음

Entry section

• 임계 영역에 들어가도 되는지 여부를 체크하고 입장 요청하는 코드 영역

Exit section

• 임계 영역에서 빠져나왔음을 통지하는 코드 영역

Remainder section

• critical section, entry section, exit section을 제외한 나머지 코드 영역

솔루션 조건

상호 배제(Mutual exclusion)

• 임계 영역에는 두 개 이상의 프로세스가 동시에 진입할 수 없음

진행(Progress)

• 현재 임계 영역에 진입한 프로세스가 없고
• 몇몇 프로세스들이 임계 영역에 진입하고 싶어 한다면
• 이미 임계 영역에서의 작업을 막 끝낸 프로세스들은 제외하고 (ex : remainder section에서 실행 중인 프로세스들)
• 나머지 중 임의의 프로세스가 선택되어 임계 영역에 진입해야 함
• 선택이 무한정 연기될 수 없음

한정된 대기(Bounded waiting)

• 임계 영역에 진입 요청을 한 프로세스가 실제 임계 영역에 진입할 때까지의 대기 시간이 무한정 길어질 수 없음

인터럽트 기반 솔루션

인터럽트 비활성화(Disabling interrupts)

• Entry section → critical section : 인터럽트 비활성화
• Critical section → entry section : 인터럽트 활성화

단점

• 임계 영역에서의 프로세스 작업량이 엄청 많다면?
  • 컴퓨터 시스템에서 프로세스가 임계영역에 상주하는 동안 모든 인터럽트 발생이 차단되어 비효율적인 성능 저하가 일어날 수 있다.
• 특정 (우선순위가 높은) 프로세스가 임계 영역을 계속 독점하게 된다면?
• 멀티 CPU 코어 환경이라면?
  • 임의의 프로세스가 엔트리 섹션에 진입하고 인터럽트 비활성화가 수행되는데 OS는 임계 영역에 진입한 프로세스가 할당되는 프로세스 이외에 다른 모든 프로세스에게도 인터럽트 비활성화 메시지를 날려야 하므로 모든 프로세스가 인터럽트 비활성화 요청을 처리하기 위해 상당한 오버헤드를 감수해야 한다. 비활성화 처리 자체를 위해서 프로세스가 임계영역에 진입해야 되는 시간이 길어질 수 있다. 그리고 프로세스 하나를 위해서 다른 관련 없는 모든 프로세스의 동작도 멈춰야 하여 시스템 효율성이 떨어진다.

하드웨어 기반 동기화 지원

하드웨어 기반 동기화(H/W support synchronization)

• Test-and-Set 인스트럭션
• Compare-and-Swap 인스트럭션

Test-and-Set 인스트럭션 기반 스핀락(spin-lock)

• 원자적(atomic) 연산을 수행
• lock 파라미터를 체크
• lock 파라미터 값 그대로 리턴
• 원래 lock 변수 값에는 새로운 값 설정

Compare-and -Swap 인스트럭션 기반 스핀락(spin-lock)

• 원자적(atomic) 연산을 수행
• lock파라미터를 체크
• lock파라미터 값 그대로 리턴
• lock 파라미터와 expected파라미터를 비교한 다음, new_value 파라미터 값 대입 수행

한정된 대기 문제를 해결하는 Compare-and-Swap 인스트럭션 기반 스핀락(spin lock)

• 각 프로세스 상태를 나타내는 공유 배열 변수 waiting[n] 정의
• 임계 영역에 진입할 다음 프로세스를 명시적으로 결정
• 임의의 프로세스는 최악의 경우 n-1회의 양보로 임계 영역 진입(n : 전체 프로세스 개수)

뮤텍스 락(Mutex Locks)

뮤텍스 락

• Mutual exclusion → Mutex
• 임계 영역을 보호하고 프로세스 간 경쟁 상황을 방지
• acquire() : 임계 영역 진입 전 lock을 획득
• release() : exit section으로 진입하며 lock을 반환

세마포어(Semaphore)

세마포어 S

• 뮤텍스 락의 공유 변수 lock의 일반화된 형태
• Integer변수로서 정의
• 원자적 인스트럭션으로서 접근
• wait() = P()
  • 세마포 변수 S 감소
  • 공유 자원을 사용하기 위해 호출
• signal() = V()
  • 세마포 변수 S증가
  • 공유 자원을 반환하기 위해 호출

이진 세마포어(Binary semaphore)

• 세마포 변수 S는 integer형 변수
• 값은 0과 1만을 가질 수 있음
• 뮤텍스 락에서의 공유 변수 lock과 동일한 역할 수행

계수형 세마포어(Counting semaphore)

• 세마포 변수 S는 integer형 변수
• 값은 0,1,2,3,...을 가질 수 있음 (상한 값이 없음)
• 두 개 이상의 공유 자원을 관리할 수 있음

바쁜 대기 문제 (Busy Waiting Problem)

바쁜 대기 문제

• 프로세스가 임계 영역에 진입하기 위해 while문을 통해 lock무한 체크를 하는 것
• while문의 실행을 위해 CPU자원을 불필요하게 할당

해결법

• lock을 무한 체크하기 위한 while문을 제거
• 프로세스에게 자기 차례가 왔음을 알려주는 순번표 할당
• 실행 순서 저장 및 통지를 위한 리스트 변수 정의

리스트가 있는 세마포어

리스트가 있는 세마포어

• Integer 변수 value와 리스트 변수를 포함

 

• wait() 함수
  • value 감소
  • 가용 공유 자원이 있는 경우 프로세스는 lock 획득
  • 가용 공유 자원이 없는 경우 프로세스는 sleep큐에 합류
  • 자신의 순번이 올 때까지 CPU자원은 다른 프로세스에게 양보

• signal() 함수
  • value 증가
  • 대기 중인 프로세스가 있다면 sleep큐로부터 방출
  • 해당 프로세스에 공유 자원 할당

스레드(Thread)

스레드(Thread)란

• 프로세스의 주소 공간을 공유하는 독립적인 실행 코드 집합
• 프로세스 실행 구조와 유사
• 문맥 교환을 위해 스레드 제어 블록(Thread control block, TCB) 사용
• 스레드 간의 문맥 교환 시 사용하는 주소 공간은 그대로 유지

멀티 스레드 프로세스

• 각 스레드가 독립적으로 실행
• 프로세스 주소 공간에 하나의 스택이 아니라 스레드마다 스택이 할당
• 싱글 스레드 프로세스에 비해 메모리 관리가 복잡해짐

pthread

• POSIX Thread
• 유닉스/리눅스 계열 POSIX시스템에서 제공하는 스레드 구현 API

Pthread API

pthread_create() : 스레드 생성

#include <pthread.h>
int pthread_create(pthread_t *thread,const pthread_attr_t *attr,void*(*start_routine) (void*), void *art);

• thread
  • pthread_t타입 구조체를 가리키는 포인터
  • 스레드 identifier로서 사용
• attr
  • 스레드의 속성을 지정하는 데 사용
  • 스택의 크기와 스레드의 스케쥴링 우선순위 지정
• (void *)
  • 스레드가 실행할 함수의 포인터, void* 타입 파라미터 및 리턴값 사용
• arg
  • 스레드가 실행할 함수에게 전달할 파라미터

pthread_join() : 분기 스레드 완료 대기

#include <pthread.h>
int pthread_join(pthread_t thread,void ** value_ptr);

• thread
  • 어떤 스레드가 실행 완료되길 기다리는지 명시
• 리턴 값에 대한 포인터
  • 스레드 실행 루틴이 임의의 데이터 타입을 리턴할 수 있기 때문에 void 포인터로 정의