동기화의 의미

• 동시다발적으로 실행되는 프로세스들은 서로 협력하며 영향을 주고 받는다. 이 과정에서 자원의 일관성을 보장해야 한다.
• 여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것

실행 순서 제어를 위한 동기화

reader writer problem

Writer: Book.txt 파일에 값을 저장하는 프로세스

Reader: Book.txt 파일에 저장된 값을 읽어들이는 프로세스

Reader와 Writer 프로세스는 무작정 아무렇게나 실행되어선 안된다.

실행의 순서가 있기 때문

Reader 프로세스는 ‘Book.txt 안에 값이 존재한다’는 특정 조건이 만족되어야만 실행 가능

상호 배제(mutual exclusion)를 위한 동기화

bank account problem

공유가 불가능한 자원의 동시 사용을 피하기 위한 동기화

현재 계좌 잔액: 10만원

프로세스 A는 현재 잔액에 2만원을 추가하는 프로세스

프로세스 B는 현재 잔액에 5만원을 추가하는 프로세스

A와 B를 동시에 실행하면 두 프로세스가 잔액 데이터에 동시에 접근하여 잘못된 잔액 결과를 낳을 수도 있다.

생산자와 소비자 문제

producer & consumer problem

물건을 계속해서 생산하는 생산자(producer, 프로세스 혹은 스레드)

물건을 계속해서 소비하는 소비자(consumer, 프로세스 혹은 스레드)

‘총합’ 변수 공유

초기 총합이 0일때, 생산자, 소비자를 각각 1만번씩 실행하면 총합이 0이 아닐수도 있다.

공유 자원과 임계 구역

공유 자원

• 여러 프로세스 혹은 스레드가 공유하는 자원
• 전역 변수, 파일, 입출력 장치, 보조기억장치

임계 구역

• 공유 자원 중 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
• 앞선 예시의 총합이나 잔액과 같은 변수
• 이러한 자원은 데이터 일관성을 보장하기 위해 하나의 프로세스/스레드만 진입해서 실행 가능하게 한다.

임계 구역에 진입하고자 하면 진입한 프로세스 이외에는 대기해야 한다.

임계 구역에 동시에 접근하면 자원의 일관성이 깨질 수 있다.

이러한 상황을 레이스 컨디션(race condition)이라고 한다.

💡 레이스 컨디션이 발생하는 이유: 고급 언어로 한줄의 코드가 저급언어로 변환되면 한줄이 아닐 수 있게 된다.

임계 구역 문제 해결의 원칙

• 상호 배제: 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
• 진행: 임계 구역에 어떤 프로세스도 진입하지 않았다면 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
• 유한 대기: 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언제가는 임계 구역에 들어올 수 있어야 한다. (무한정 대기해서는 안된다.)

동기화 기법

Lock을 사용한다!!

스핀 락(Spin Lock)

val int lock = 0 // 0이면 사용 가능

fun critical() {
		while(testAndSet(lock) == 1){
		// 누군가 critical section에 진입해 있으면 갇히게 됨
		}
		... critical section
		lock = 0
}

// 조건문 검사, 현재 락이 0이면 1로 만들고 0을 반환하여 critical section에 진입 가능
fun testAndSet(): Int {
		int oldLock = lock
		lock = 1
		return oldLock
}

• testAndSet()이 동시에 실행되는 경우?
  • CPU의 도움을 통해 동시에 실행되지 않도록 한다.
  • TestAndSet은 CPU의 atomic 명령어로 실행 중간에 간섭받거나 중단되지 않는다. 또한 같은 메모리 영역에 대해 동시에 실행되지 않는다.

💡 바쁜 대기(CPU 사이클 낭비)로 인해 CPU 사이클 낭비 해결 방안

• 사용할 수 있는 자원이 없는 경우 대기 상태로 만듦 (해당 프로세스의 PCB를 대기 큐에 삽입)
• 사용할 수 있는 자원이 생겼을 경우 대기 큐의 프로세스를 준비 상태로 만듦(해당 프로세스의 PCB를 대기 큐에서 꺼내 준비 큐에 삽입)

뮤텍스 락(Mutex Lock)

상호 배제를 위한 동기화 도구(자물쇠 역할), 뮤텍스 락

자물쇠 역할: 프로세스들이 공유하는 전역 변수 lock

임계 구역을 잠그는 역할: acquire 함수

임계 구역의 잠금을 해제하는 역할: release 함수

자물쇠를 지속적으로 확인하는 대기 방식을 바쁜 대기라고 한다.

val lock = 1// 락을 얻어야 임계 구역에서 작업이 가능하다.
val guard = true;

// 프로세스가 임계 구역에 진입하기 전에 호출
fun acquire() {
		while(guard == false){} // 가드를 먼저 얻는다.
		if(lock <= 0){
				// 잠겨 있으면 현재 스레드를 큐에 넣는다.
				guard = true & 자러 간다.
		}else {
				// 락을 획득
				// 열리면 임계 구역 잠근 후 임계 구역에서 작업 진행
				lock = true // 락을 잠근다.
		}
}

// 임계 구역에서 작업 끝난 후 호출
fun release() {
		if(큐에 하나라도 대기중이라면) {
				그 중에 하나를 깨운다
		}else {
				lock = false // 잠금 해제
		}
		guard= true
}

세마포(Semaphore)

뮤텍스 락에 비해 좀 더 일반화된 방식의 동기화 도구

공유 자원이 여러 개 있는 경우에도 적용 가능

전역 변수 하나와 함수 2개가 필요

임계 구역에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수 S

임계 구역에 들어가도 좋은지, 기다려야 할지 알려주는 wait 함수

임계 구역 앞에서 기다리는 프로세스에 ‘이제 가도 좋다’고 신호를 주는 signal 함수

val S = 3 // 진입할 수 있는 프로세스의 수

fun wait(){
		// 현재 진입할 수 있는 프로세스의 수가 0이하면 대기
		while( S <= 0 ) {
		// 대기
		}
		S-- // 대기가 끝나면 진입할 수 있는 프로세스 수 하나 감소시키고 임계 구역 진입
}

 // 임계 구역에서 작업 끝난 후 호출
fun signal() {
		S++ // 진입 가능한 프로세스 수 ++
}

세마포를 활용한 실행 순서 동기화

• 세마포의 변수 S를 0으로 두고
• 먼저 실행할 프로세스 뒤에 signal 함수
• 다음에 실행할 프로세스 앞에 wait 함수를 붙이면 된다.

모니터

1. 세마포를 누락한 경우
2. wait과 signal 순서를 헷갈린 경우
3. wait과 signal을 중복해서 사용한 경우

위와 같은 휴먼에러를 방지하기 위해 등장

• 상호 배제를 위한 동기화
  • 인터페이스를 위한 큐
  • 공유자원에 접근하고자 하는 프로세스를 큐에 삽입
  • 큐에 삽입된 순서대로 공유자원 이용
• 실행 순서 제어를 위한 동기화
  • 조건 변수 이용
    프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수

참고자료