CS 스터디 4회차 -(3)

CS 스터디 4회차 마지막 챕터

<3> 동기화와 교착 상태에 대해 알아보도록 하겠다.

프로세스와 스레드는 동시다발적으로 수행된다고 말했었다.

이렇게 동시다발적으로 수행되는 프로세스와 스레드들은 서로 협력하면서 영향을 주고 받는다.

그리고 이 과정에서 자원의 일관성을 보장해야 한다.

동기화는 프로세스만을 동기화 시키는게 아니라 스레드도 동기화의 대상이긴 하지만 편의성 프로세스의 동기화라고만 하겠다.


📘 동기화의 의미

$\rarr$ 공동의 목적을 위해 동시에 수행되는 프로세스. 프로세스들의 수행 시기를 맞추는 것.

예를 들어, 워드 프로세서 프로그램이라고 한다면.

맞춤법 검사 프로세스, 입력 내용을 화면에 출력하는 프로세스 등 여러가지 많은 프로세스가 있다.

이 프로세스들은 아무렇게나 동시에 실행되어서는 안 된다.

자원의 일관성을 보장해야 되기 때문이다.

그걸 위해서 동기화를 해줘야 한다.

📌 실행 순서 제어

$\rarr$ 프로세스를 올바른 순서대로 실행하기

📌 상호 배제

$\rarr$ 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기

이렇게 두가지의 동기화가 있다.

실행 순서 제어를 위한 동기화(:reader writer problem)

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

이 writer 프로세스와 reader 프로세스가 동시에 실행된다고 가정을 해보자.

아무렇게나 동시에 실행해도 괜찮을까?

아니다.

실행순서가 있기 때문이다.

reader 프로세스는 Book.txt 안에 값이 존재한다라는 특정 조건이 만족되어야 실행된다.

그렇기에 reader 프로세스는 writer 프로세스가 실행이 끝난 다음에야 실행이 가능한 것이다.

이게 실행 순서 제어를 위한 동기화라고 보면 된다.

그럼 이제 상호 배제에 대한 동기화에 대해 알아보자.

상호 배제는 공유 불가능한 자원이 동시에 사용되는 것을 피하기 위한 동기화다.

반드시 한 번에 하나씩만 사용해야 하는 프로세스가 있을 수 있으니까.

예를 들어, 프린트 같은 경우에 말이다.

이렇게 한 번에 하나의 프로세스만 접근해야 되는 자원에 동시 접근을 피하기 위한 동기화가 상호 배제를 위한 동기화라고 기억하자.

상호 배제를 위한 동기화엔 Bank account problem 이라는 고전적인 문제가 있다.

예를 들어서, 현재 계좌에 잔액이라는 데이터가 있다고 가정을 해보자.

그 잔액에는 10만원이 있다.

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

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

이 상황에서 프로세스 A, B 가 동기화 없이 동시에 실행된다면?

동기화 없이 실행되도 계좌에는 17만원이 남아 있을거라고 생각할 수 있지만 전혀 아니다.

문맥 교환까지 추가해서 살펴보자.

프로세스 A, B는 잔액이라는 데이터를 동시에 사용하는데

프로세스의 A의 실행이 전부 다 끝나버리기도 전에 프로세스 B가 이 잔액이라고 하는 데이터에 접근했기 때문에 이런 결과가 나오게 된다.

올바르게 실행되기 위해서는 잔액이라는 데이터에 접근할 땐 한 번에 하나만 접근해야 한다.

문맥교환이 되더라도 이 정보를 잃지 말고 기다려야 한다.

다른 예시를 살펴 보자.

Producer & Consumer problem

생산자 - 소비자 문제라고도 부른다.

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

이 두개의 프로세스 혹은 스레드는 총합이라 하는 변수를 공유하고 있었다고 가정해보자.

생산자는

생산자 () {
		버퍼에 데이터 삽입
        '총 합' 변수 1 증가
}

이렇게 가정을 하고.

소비자는

소비자 () {
		버퍼에서 데이터 빼내기
        '총 합' 변수 1 감소
}

이렇게 가정을 해보자.

그리고 총합이라는 변수는 생산자 프로세스 그리고 소비자 프로세스가 모두 공유할 수 있어야 하기 때문에 전역변수였다고 가정을 하겠다.

총합 = 10

생산자 () {
		버퍼에 데이터 삽입
        '총 합' 변수 1 증가
}
소비자 () {
		버퍼에서 데이터 빼내기
        '총 합' 변수 1 감소
}

이 상태에서 생산자를 10만번, 소비자를 10만번 동시에 실행하면 어떻게 될까?

0이 될까?

아니다. 코드를 돌리면 0이 될 때도 있고, 전혀 다른 숫자가 될 때도 있고, 오류를 일으킬 때도 있다.

동시에 접근해서는 안 되는 총합이라는 자원에 동시에 접근했기 때문에 발생하는 문제다.

접근해서는 안 되는 자원에 대해 알기 위해서는 공유자원과 임계구역에 대해 먼저 살펴봐야 한다.

📘 공유 자원(shared resource)
$\rarr$ 여러 프로세스 혹은 스레드가 공유하는 자원.

앞서 예시에서 총합이라고 하는 변수는 생산자, 소비자 이 두개가 총합이라고 하는 전역변수를 공유하고 있었다.

그렇기 때문에 전역변수도 공유자원이라고 할 수 있다.

파일, 각종 입출력장치, 보조기억장치들도 모두 공유 자원이라고 할 수 있다.

그리고 이런 공유 자원들 중에서는 두 개 이상의 프로세스를 동시에 실행하면 문제가 발생하는 자원이 있다.

뱅크 계좌 문제에서 계좌 잔액 변수라던지, 총합 변수가 이런 자원에 속한다.

📘 임계 구역(critical section)
$\rarr$ 동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역

예시에서 총합 변수를 읽어들인다던가, 1을 더한다거나, 잔액 변수에 접근한다거나 하는 코드를 모두 임계 구역이라고 한다.

당연하게도 2개 이상의 프로세스 혹은 스레드가 실행되면 임계 구역에도 문제가 생긴다.

그래서 임계 구역에 진입하고자 한다면 이 임계 구역은 한 번에 하나의 프로세스만 실행되야 하기 때문에 다른 프로세스들은 대기를 시킨다.

프로세스 A가 먼저 임계 구역에 들어갔다. 프로세스 B는 임계 구역에 들어가고 싶어도 대기 해야 된다. 언제까지? 프로세스 A가 임계 구역에서 빠져나올 때까지.

📘 레이스 컨디션(race condition)
$\rarr$ 프로세스나 스레드가 임계 구역에 동시에 접근해 자원의 일관성이 깨지는 것.

앞선 예시들 모두 레이스 컨디션이라고 볼 수 있다.

모두 동시에 자원에 접근해 오류를 일으키는 문제기 때문에.

📌 임계 구역 문제, 어떤 자원의 일관성을 지켜주기 위해서 운영체제는 어떤 일을 해야 될까?
다시 말해서, 상호 배제를 위한 동기화를 어떻게 이룰 수 있을까?

$\rarr$ 세 가지 원칙을 지켜 주면 된다.
1. 상호 배제(mutual exclusion)
2. 진행(progress)
3. 유한 대기(bounded waiting)

상호 배제는 한 프로세스가 임계구역에 진입했다면 다른 프로세스는 들어올 수 없다는 것.

진행은 임계구역에 아무도 진입하지 않았다면 진입하고자 하는 프로세스는 들어갈 수 있어야 된다라고 하는 것.

유한 대기는 한 프로세스가 임계구역에 진입하고 싶다면 언젠가는 들어갈 수 있어야 한다는 것.
(임계구역에 들어가기 위해 무한정 대기해서는 안 된다.)

이제 동기화 기법에 대해 알아보도록 하자.

📘 뮤텍스 락, 세마포, 모니터

동기화 기법엔 다양한 기법들이 있지만 제일 대중적인 세 가지를 알아보자.

📌 뮤텍스 락(mutex lock)

$\rarr$ 상호 배제를 위한 동기화 도구, 자물쇠 역할을 한다.

예를 들어 옷 가게에 가서 옷을 입어 보기 위해 탈의실에 들어간다고 하자. 그럴 때 탈의실에 들어가서 다른 사람이 들어올 수 없게 자물쇠로 문을 잠그는 것.

임계구역에 이미 들어간 프로세스가 있을 때 다음 프로세스가 들어갈 수 없게 하는 것. 이것을 뮤텍스 락이라고 한다.

뮤텍스 락을 코드로 구현한다면 전역변수 하나, 함수 두개로 만들 수 있다.

1. 자물쇠 역할을 하는, 프로세스들이 공유하는 전역변수 - lock
2. 임계 구역을 잠그는 역할 - acquire 함수
3. 임계 구역의 잠금을 해제하는 역할 - release 함수

acquire(){
	while (lock == true)	/*만약 임계 구역이 잠겨 있다면*/
    	;					/*임계 구역이 잠겨 있는지를 반복적으로 확인*/
    lock = true;			/*만약 임계구역이 잠겨 있지 않다면 임계구역 잠금*/
}

release(){
	lock = false;			/*임계 구역 작업이 끝났으니 잠금 해제*/
}

임계구역이 잠겨 있는지 아닌지를 반복적으로 확인하는 것을

바쁜 대기(busy waiting)이라고 부른다.

📌 세마포(semaphore)
$\rarr$ 좀 더 일반화된 방식의 동기화 도구. 공유자원이 여러 개 있는 상황에서도 동기화가 가능.

좀 전의 뮤텍스 락은 탈의실이 하나 있는 경우였다면, 세마포는 탈의실이 여러 개 있는 경우다.

공유자원이 여러 개 있는 경우도 있으니까.

세마포는 이진 세마포, 카운팅 세마포가 있는데 이진 세마포는 뮤텍스 락과 유사한 방식이라 카운팅 세마포에 대해서만 다뤄보겠다.

세마포는 그림에서처럼 열차가 지나가도 되는지 멈춰야 하는지를 나타내는 신호기를 일컫는 말이다.

임계 구역 앞에서 멈춤 신호를 받으면 잠시 대기.
가도 좋다는 신호를 받으면 임계 구역 진입.

이렇게 말이다.

세마포도 간단히 코드로 구현할 수 있는데, 생략하도록 하겠다.

📌 모니터(monitor)
$\rarr$ 상호 배제를 위한 동기화와, 실행 순서제어를 위한 동기화 방식을 모두 제공해주는 동기화 도구.

세마포는 대중적이긴 하지만 사용시 불편한 감이 있다.

임계 구역 앞 뒤로 항상 wait 신호와 signal 신호를 보내줘야 하기 때문이다.

세마포를 누락할 수도 있고, 신호의 순서를 헷갈리거나, 중복해서 사용한 경우가 있을 수 있다.

이 경우 디버깅이 힘들어 지기 때문에 사용자 입장에서는 사용이 불편하다고 할 수 밖에 없다.

그래서 등장한 동기화 도구가 모니터다.

다르게 말하면 사용자가 다루기 편한 동기화 도구란 소리기도 하다.

이 그림은 상호 배제를 위한 동기화를 보여준다.

• 인터페이스를 위한 큐
• 공유자원에 접근하고자 하는 프로세스를(인터페이스를 위한) 큐에 삽입
• 큐에 삽입된 순서대로 (한 번에 하나의 프로세스만) 공유 자원 이용

실행 순서를 위한 동기화다.

• 조건 변수를 이용한다.
• 조건 변수 .wait() : 대기 상태로 변경, 조건 변수에 대한 큐에 삽입
• 조건 변수 .signal() : wait()으로 대기 상태로 접어든 조건 변수를 실행 상태로 변경

📌 조건 변수란, 프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 변수

여기서 참고할 점은, 상호 배제를 위한 동기화에서 '큐'와 실행 순서를 위한 동기화에서 '조건 변수 큐'는 다르다는 것.

마지막으로 정리하자면,

모니터 안에는 하나의 프로세스만 있을 수 있고
두 가지 방법이 존재한다.

1. wait()을 호출했던 프로세스는 signal()을 호출한 프로세스가 모니터를 떠난 뒤에 수행을 재개
2. signal()을 호출한 프로세스의 실행을 일시 중단하고 자신이 실행된 뒤 다시 signal()을 호출한 프로세스의 수행을 재개

다시 말해서 모니터는 상호 배제를 위한 동기화 뿐만 아니라 실행 순서를 위한 동기화도 제공을 하는데

특정 프로세스가 실행될 조건이 아직 안 됐을 때는 조건변수 wait를 통해 실행을 중단하고, 실행해도 괜찮을 땐 signal을 호출해 실행하게 만들어준다.

📘 이제 드디어 교착 상태다

📌 교착 상태(deadlock)
$\rarr$ 프로세스가 제대로 실행되려면 자원이 필요한데, 두 개 이상의 프로세스가 각자 갖고 있는 자원들을 그저 기다리기만 하면 그 어떤 프로세스도 실행되지 못하고 마치 교통이 마비되어 꽉 막힌 도로의 차처럼, 막혀버린 현상을 교착 상태라고 한다.

교착 상태를 해결하는 것 또한 운영체제에서 해야하는 아주 중요한 업무라고 할 수 있다.

교착 상태가 발생하는 조건을 알아보자.
1. 상호 배제
2. 점유와 대기
3. 비선점
4. 원형 대기

네 가지 조건들이 있다.

상호 배제는 동기화에서 이미 말을 했다. 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 것. 상호 배제 조건이 없다면 교착 상태는 일어나지 않는다.

점유와 대기는 자원을 할당 받은 상태에서 다른 자원을 기다리고 있는 상태이다.

비선점은 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태를 말한다.

원형 대기는 프로세스들이 원의 형태로 자원을 대기하는 상태를 말한다.

물론 자원 할당 그래프에서 원의 형태를 띄고 있다고 해서 무조건 교착 상태인 것은 아니지만, 교착 상태가 발생했다면 자원 할당 그래프에서 원의 형태를 띄고 있다고 보면 된다.

그렇다면 교착 상태의 해결 방법에 대해 알아보자.

방법엔 세 가지가 있다.

예방하는 방법, 회피하는 방법, 해결하는 방법이다.

📌 예방하는 방법

예방하는 방법부터 알아보자.

바로 위에서 교착 상태의 발생 조건이 네 가지 있었다.
그 중 하나라도 충족하지 않으면 교착 상태가 발생하지 않기 때문에 발생 조건 중 하나를 없애 버리는 방법이다.

이 방법은 이론적으로는 가능하지만, 현실적인 방법은 아니다.

없애는 발생조건마다 부작용이 발생하기 때문이다.

📌 회피하는 방법

다음은 회피하는 방법이다.

회피하는 방법에서는 교착 상태를 자원은 한정되어 있는데, 이 한정되어 있는 자원을 무분별하게 할당해서 발생했다라고 간주한다.

배분할 수 있는 자원의 양을 교착상태가 발생하지 않을 정도로만 배분한다고 보면 된다.

• 안전 순서열
• 안전 상태
• 불안전 상태

안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서이고,
안전 상태는 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태,
마지막으로 불안전 상태는 교착 상태가 발생할 수도 있는 상태이다.

교착 상태 회피는 항상 안전상태만을 유지하게끔 자원을 할당하는 방식으로 볼 수도 있다.

교착 상태 회피를 위한 알고리즘으로 은행원 알고리즘이라는 게 있으니 나중에 검색해 보도록 하자.

📌 해결 하는 방법
$\rarr$ 해결하는 방법엔 교착 상태 검출 후 회복이 있다.

교착 상태가 발생했다는 것을 인정하고 사후에 조치 하는 방식이라고 말할 수 있다.

교착 상태가 발생하든 말든 일단 프로세스가 자원을 요구하면 자원을 할당해주고 교착상태가 발생했다면 그 때 회복을 한다.

이 방법엔 두가지가 있는데,

자원 선점을 통해 회복 시키거나, 강제 종료함으로써 회복 하는 방법이 있다.

자원 선점을 통해 회복 시키는 것은
교착 상태가 회복 될 때까지 한 프로세스에 자원을 몰아주는 방식이고,

강제 종료함으로써 회복은
말 그대로 강제 종료를 하는 것이다.

여기까지 동기화와 교착 상태에 대해 알아보았다.