혼자 공부하는 컴퓨터 구조 + 운영체제 5주차
혼공컴운 5주차입니다
가장 기대하고 있던 프로세스 동기화와 교착상태 파트입니다!
프로세스 동기화: 동기화란?
여러 프로세스들은 공동의 목적을 수행하기 위해
서로 협력하며 소통하기도 합니다.
서로 협력하는 프로세스들은 실행 순서와 자원의 일관성을 보장받아야 하기에
동기화(Synchronization)가 필수입니다.
.
동기화. 낮설면서도 익숙한 단어입니다
가장 쉽게 접할 수 있는 상황은 아마 달력/일정 애플리케이션의 동기화 기능일텐데요.
윈도우 11에서는 구글 캘린더와 연동하여
구글 계정 내 구글 캘린더에 등록한 일정을 윈도우 11 일정 앱에서 볼 수 있는 기능이 있습니다.
일정 주기마다 구글 캘린더로부터 데이터를 가져오나,
주기가 돌아오기 전에 구글 캘린더의 일정을 가져오고 싶다면
'동기화' 기능을 통해 수동으로 구글 캘린더의 데이터를 가져올 수 있습니다.
즉, 동기화란 시점, 상태 등을 같게 만들어준다는 의미로 볼 수 있습니다.
그 중에서도 프로세스 동기화는 프로그램 사이의 수행 시기를 맞추는 것을 의미합니다.
수행 시기를 맞춘다. 라는 것은
1. 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기
2. 상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기
두 가지를 의미합니다.
(프로세스 뿐 아니라 스레드를 포함한 실행의 흐름을 갖는 모든 것은 동기화의 대상이 될 수 있습니다.
이하 내용에서는 코드로 구현이 비교적 간단한 스레드를 사용해 코드를 작성하나,
스레드 대신 프로세스라 생각해도 무방합니다.)
실행 순서 제어와 동기화
Book.txt 파일을 읽는 Reader 프로세스, 파일을 작성하는 Writer 프로세스가 있을 때,
두 프로세스가 하나의 파일에 동시접근하면 어떻게 될까요?
자바의 파일 입출력을 배울 때 Writer를 안닫고 Reader를 쓸 때 파일이 깨지거나,
오류가 나거나, 잠금상태가 됬던게 기억나네요.
Reader 프로세스는 Writer 프로세스가 끝난 후에야 비로소 실행이 가능하며,
Writer 프로세스가 끝나기 전 Reader 프로세스가 작동하는 건 그닥 바람직한 흐름은 아닙니다.
때문에 동시에 실행되는 프로세스간에 올바른 순서대로 실행하는 것이 첫 번째 프로세스 동기화입니다.
상호 배제를 위한 동기화
상호 배제(Mutual Exclusion)는 공유가 불가능한 자원을
동시에 사용하는 것을 피하기 위해 사용되는 알고리즘입니다.
이 부분을 가장 잘 설명할 수 있는 예시는 계좌 프로그램이라 할 수 있습니다.
데이터베이스를 공부하셨던 분들이라면, DB의 원자성을 배울 때 많이 들어봤던 예시죠?
계좌에 2만원을 저축하는 프로세스 A,
계좌에 5만원을 저축하는 프로세스 B.
잔고가 10만원인 계좌에 두 가지 프로세스가 동시에 실행한다고 생각해봅시다.
10 + 2(A) + 5(B) = 17만원으로 기대했으나,
15만원이 결과로 나와버렸습니다...!
프로세스 A, B는 잔액 데이터를 사용하는데
A가 끝나기도 전에 B가 잔액을 읽어버리고
A가 끝난 후 더한 값을 저장했으나,
B는 그저 자신이 처음에 읽은(A가 끝나기 전에 읽은) 10만원에
5만원을 더해 그대로 저장해버렸거든요!!!!
때문에 서로 공유하는 자원인 '계좌의 잔액'에 대해서는
한 번에 단 한 프로세스씩만 접근할 수 있어야 합니다!
A가 계좌의 잔액에 접근하고 있을 때에는
B는 계좌의 잔액을 읽지 말고 기다린 후,
A가 끝난 후에야 잔액을 읽고 작업을 수행합니다.
이러한 내용이 바로 동시에 접근해서는 안되는 자원에
동시에 접근하지 못하게 하는 상호 배제를 위한 동기화입니다.
생산자와 소비자 문제
상호 배제를 위한 동기화에는 아주 고전적이고 유명한 문제로,
생산자와 소비자 문제가 존재합니다.
물건을 계속 생성하는 생성자 프로세스와
물건을 계속 소비하는 소비자 프로세스가 있다고 가정해봅시다.
(스레드로 가정해도 무방합니다)
생산자와 소비자는 총합이라는 데이터를 공유하고 있고,
생산자는 버퍼에 물건을 넣고, 총합 변수를 1만큼 증가시킵니다.
소비자는 버퍼에 물건을 빼고, 총합 변수를 1만큼 감소시킵니다.
이제 총합을 10으로 두고, 생산자를 100,000번, 소비자를 100,000번 실행해보기로 합시다.
그냥 단순히 생각했을 때, 100,000개를 생산하고 100,000개를 소비했으니,
총합은 변하지 않을 것 같네요.
public class Main {
// static Queue<Integer> q = new LinkedList<>();
static int sum = 10;
public static void main(String[] args) {
System.out.println("초기 합계: " + sum);
Thread producer = new Thread(Main::produce);
Thread consumer = new Thread(Main::consume);
producer.start();
consumer.start();
try {
producer.join();
consumer.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("producer, consumer 스레드 실행 이후 합계: " + sum);
}
public static void produce() {
for (int i = 0; i < 100000; i++) {
// q.offer(1);
sum++;
}
}
public static void consume() {
for (int i = 0; i < 100000; i++) {
// q.poll();
sum--;
}
}
}
도서의 참고 자료로는 C++ 코드가 첨부되어 있지만,
저는 자바가 더 편하기에 해당 내용을 자바로 짜봤습니다.
자 이제 코드를 실행해볼까요?
? 뭐지.
다시 실행해봤습니다.
이번에도 예상한 값(10)과 다른 값이 출력됩니다.
이는 생산자 / 소비자 프로세스(스레드)가 제대로 동기화되지 않았기 때문에 발생한 문제입니다.
생산자와 소비자 프로세스(스레드)는 총합(sum) 데이터를 사용하는데,
소비자가 생산자의 작업이 끝나기도 전에 총합(sum)을 수정해버렸고,
생산자도 소비자의 작업이 끝나기도 전에 총합(sum)을 수정해버린 것입니다.
위에서 언급한 계좌 잔액 문제와 같이
동시에 접근하면 안되는 자원에 동시에 접근해버린 것이죠.
공유 자원과 임계 구역
계좌의 잔액, 위 예제의 총합은 여러 프로세스/스레드가 동시에 사용하는 '공유 자원(shared resource)' 입니다.
공유 자원은 전역변수 혹은 파일 혹은 입출력장치, 보조기억장치 등이 될 수 있죠.
그리고 이런 공유 자원은 모든 자원이 그런 것은 아니지만,
잔액, 총합과 같이 복수의 프로세스가 접근해서는 안되는 자원도 있습니다.
동시에 접근해서는 안되는 이러한 코드 영역을 임계 구역(critical section)이라 합니다.
복수개의 프로세스가 임계 구역에 진입하려면
자원을 사용하고 있는 프로세스를 제외한 다른 프로세스는 대기해야 합니다.
자원의 사용이 끝나면 그 때 다음 프로세스가 임계 구역에 접근해야 합니다.
계좌 잔액이나 생산자와 소비자 문제처럼
여러 프로세스가 동시에 임계 구역에 접근하여 발생하는 문제를 레이스 컨디션(race condition)이라 하는데,
당연하게도 데이터의 일관성이 깨질 가능성이 있습니다.
상호 배제를 위한 동기화는 이와 같은 일이 발생하지 않도록
복수개의 프로세스가 임계 구역에 동시에 접근하지 못하도록 관리하는 것을 말하며
운영체제는 임계 구역 문제를 아래 3개 원칙하에 해결합니다.
상호 배제(mutual exclusion) : 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없다.
진행(progress) : 임계 구역에 어떤 프로세스도 진입하지 않았다면, 임계 구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다.
유한 대기(bounded waiting) : 한 프로세스가 임계 구역에 진입하고 싶다면 그 프로세스는 언젠가는 임계 구역에 들어올 수 있어야 한다. (임계 구역에 들어오기 위해 무한정 대기해서는 안 됨)
하나 하나 봤을 때, 당연한 원칙들이죠?
동기화 기법
뮤텍스 락
앗! 갑자기 배가 아파 화장실에 가려고 합니다.
다행이도, 화장실을 찾았습니다.
칸에 들어갈려고 했더니 잠겨있습니다.
손잡이 쪽을 보니 '사용중' 표시가 보입니다.
당연한 이야기지만 화장실 칸 안에는 한 번에 한 명만 들어갈 수 있기에
조금 기다려보기로 합니다.
자, 이제 이 이야기에서
'배가 아파 화장실을 가려는 사람'을 '프로세스'로,
'화장실'을 '임계 구역'으로
'자물쇠/사용중 표기 손잡이'를 '뮤텍스 락'으로 용어를 조금만 바꿔볼까요?
자물쇠와 사용중 표기 손잡이 역할을 하는 것을 코드로 구현한 것이 바로
뮤텍스 락(mutex lock: MUTual Exclusion lock)인데요.
동시에 접근해서는 안 되는 자원에
동시에 접근하지 않도록 만드는 도구입니다.
상호 배제를 위한 동기화 도구인셈이죠.
먼저 화장실에 들어간 사람은
내가 화장실(임계 구역)에 있음을 알리기 위해 뮤텍스 락(자물쇠)를 걸어잠급니다.
다음에 화장실을 들어온 사람은
자물쇠가 잠겨있거나 '사용중' 표시가 떠 있을 때 기다리고,
'열림' 표시 혹은 자물쇠가 안잠겨있다면 사용하면 됩니다.
뮤텍스 락의 매우 간단한 형태는 전역 변수 1개와 함수 2개로 구현할 수 있습니다.
자물쇠 : 프로세스들이 공유하는 전역 변수 lock
임계 구역 잠그는 역할 : acquire 함수
임계 구역을 잠금을 해제 : release 함수
하나씩 보겠습니다.
acquire 함수
프로세스가 임계 구역에 진입하기 전에 호츨하여
만약 임계 구역이 잠겨있다면 임계 구역이 열릴 때 까지 (lock == false가 될 때 까지)
임계 구역을 반복적으로 확인하고,
임계 구역이 열려 있다면 임계 구역을 잠그는(lock = true) 함수입니다.
release 함수
임계구역에서 작업이 끝난 뒤 호출하는 함수로,
잠긴 임계 구역을 여는(lock=true) 함수입니다.
앞선 생산자와 소비자 문제를
위와 같이 임계 구역 전후로 호출함으로써 하나의 프로세스만 임계 구역에 진입할 수 있습니다.
락을 흭득할 수 없다면 무작정 기다리고,
락을 흭득할 수 있다면 임계 구역을 잠근 뒤 볼일을 보고
임계 구역에서 나올 때는 잠금을 해제하여 임계 구역을 보호할 수 있습니다.
여기서 while문으로 lock이 잠겨있는지 계속 확인하는데,
이런 대기 방식을 바쁜 대기(busy wait)이라 합니다.
(실제 프로그래밍 언어에서 제공하는 뮤텍스 락은
이 예제보다 훨씬 정교하게 설계 및 작동합니다)
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class Main {
static final int NUM_THREADS = 4;
static int sharedSum = 0;
static Lock mutex = new ReentrantLock();
public static void main(String[] args) {
Thread[] threads = new Thread[NUM_THREADS];
for (int i = 0; i < NUM_THREADS; ++i) {
threads[i] = new Thread(Main::stockSharedSum);
threads[i].start();
}
for (int i = 0; i < NUM_THREADS; ++i) {
try {
threads[i].join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("final result is " + sharedSum);
}
public static void stockSharedSum() {
mutex.lock(); // 뮤텍스 락 -> 다른 프로세스 못들어와!
try {
for (int i = 0; i < 10000; ++i) {
sharedSum += 1;
}
} finally {
mutex.unlock(); // 언락 -> 다음 프로세스 들어오세요!
}
}
}
참고 코드 깃허브를 들어가봤더니 C++로 작성되어있길래,
저에게 익숙한 자바와 뮤텍스 락과 비슷한 역할을 하는 ReentrantLock을 사용하여 구현해봤습니다.
stockSharedSum() 메서드의 바디 부분에서
mutex를 걸어 잠그고,
볼 일이 끝났다면 mutex를 언락하여 상호 배제를 위한 프로세스 동기화를 진행합니다.
세마포
세마포(semaphore)는 뮤텍스 락과 비슷하나, 조금 더 일반화된 동기화 도구입니다.
뮤텍스 락은 하나의 공유 자원에 접근하는 프로세스를 상정했지만,
공유 자원이 여러 개 있을 경우, 여러 개 프로세스가 각각 공유 자원에 접근이 가능해야 합니다.
뮤텍스 락은 화장실에 칸이 하나만 있을 때를 상정한 경우,
세마포는 화장실에 칸이 여러 개 있을 경우로 생각할 수 있을 것 같네요.
화장실에 칸이 세 개면 세 명이 동시에 볼 일을 볼 수 있습니다.
옷가게에 탈의실이 세 개면 세 명이 동시에 탈의실을 이용할 수 있죠.
세마포는 수기 신호를 의미합니다.
근대부터는 여러 대 기차가 한 철로를 사용할 때,
한 번에 한 대씩만 지나가도록 깃발 표시를 하던 장치를 가리키던 용어로 쓰였습니다.
프로그래밍 언어에서 세마포는 위에서 언급한 철도 신호기로부터 유래한 단어로,
신호기가 내려가있을 땐 멈추고, 신호기가 올라와 있을 땐 가도 좋다는 의미로 받아들여 움직입니다.
세마포 역시 멈춤 / 가도 됨, 두 가지 신호로 임계 구역을 관리합니다.
뮤텍스 락과 비슷하게, 단순한 형태의 세마포는 1개의 변수와 2개의 함수로 구현가능합니다.
- 임계 구역에 진입할 수 있는 프로세스 개수(사용 가능한 공유 자원 개수)를 나타내는 전역변수 S
- 임계 구역에 들어가도 되는지 or 기다리는지 알려주는 wait 함수
- 임계 구역 앞에서 기다리는 프로세스에 '이제 가도 된다'라고 신호를 줄 signal 함수
뮤텍스 락과 비슷하게, 임계 구역 전후로 wait()과 signal()을 호출합니다.
wait 함수
변수 S는 임계 구역에 진입할 수 있는 프로세스 개수 / 사용 가능한 공유 자원 개수입니다.
따라서 임계 구역에 진입할 수 있는 프로세스 개수(S)가 0 이하라면 반복적으로 확인하고,
임계 구역에 진입할 수 있는 프로세스 개수가 하나 이상이면
S를 1만큼 감소시키고 임계 구역에 진입합니다.
signal 함수
wait에서 S를 1만큼 줄였듯이,
signal에서는 S를 1만큼 증가시키면 되겠죠?
좋아보이지만 여기서 한 가지 문제가 있습니다.
뮤텍스 락에게도 해당되는 문제인데,
사용할 수 있는 공유 자원이 없다면 while 문으로 계속 확인하고 있다는 점입니다.
안그래도 바쁜 CPU가 자기 할 일을 하다가 중간에 계속 화장실 문이 잠겼는지 확인하는 것이죠.
때문에 세마포는 wait 함수에서 사용할 수 있는 자원이 없다면
해당 프로세스를 대기 상태로 만들고,
프로세스의 PCB를 세마포를 위한 대기 큐에 넣고,
다른 프로세스가 signal을 호출하며 임계 구역에서 나오면
대기 큐에 넣은 (가장 위에있는) 프로세스가 임계 구역에 들어갑니다.
import java.util.concurrent.Semaphore;
public class Main {
static int num = 0;
static Semaphore semaphore = new Semaphore(1);
public static void main(String[] args) {
Thread t1 = new Thread(Main::stockNum);
Thread t2 = new Thread(Main::stockNum);
t1.start();
t2.start();
try {
t1.join();
t2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(num);
}
public static void stockNum() {
for (int i = 0; i < 100000; i++) {
try {
semaphore.acquire();
num++;
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
semaphore.release();
}
}
}
}
깃허브 참고 코드를 보니 파이썬으로 적혀있더군요.
역시나 자바로 컨버팅해 작성해봤습니다.
자바의 Semaphore 클래스를 사용했는데요.
인스턴스화 할 때 생성자로 공유 자원의 개수를 넣어줄 수 있습니다. 저는 1로 설정했습ㄴ디ㅏ.
stockNum 메서드의 바디 안에서
semaphore의 acquire 메서드를 호출합니다.
저희가 배운 내용으로 생각하자면 공유 자원의 숫자가 1만큼 감소할 것 같은데요. 진짜일까요?
Semaphore 클래스 안으로 여행을 떠나봅시다.
acquire 메서드를 호출하면 내부적으로 acquireSharedInterruptibly(1)을 호출합니다.
주석을 보니 세마포에서 허가 흭득을 요청하고, 허가를 받을 때 까지 or 스레드가 인터럽트될 때 까지 대기하고,
접근 허가가 내려지면 사용 하능한 허가(공유 자원 개수)가 하나 줄어들고,
허가가 없다면 스레드 스케줄링을 위해
다른 스레드가 이 세마포의 release 메서드를 호출하여 (공유 자원 개수가 1만큼 늘어나면)
진입 가능해질 때 까지 비활성화 된다네요.
이 참에 release도 봅시다.
세마포에서 허가를 반환하여, 세마포의 사용 가능한 허가 수가 1개 증가합니다.
만약 어떤 스레드가 허가를 흭득하려고 한다면, 그 중 하나사 선택되어 방금 반환환 허가를 가져갑니다.
그 스레드는 (다시) 활성화되며 허가를 반환하는 스레드가
반드시 acquire를 호출하여 해당 허가를 흭득해야 하는 것은 아니며,
세마포의 올바른 사용은 애플리케이션 프로그래밍 규칙에 의해 결정된다네요.
번역기 돌렸습니다.
저희가 배운 acquire, release와 크게 다르지 않는 듯 보입니다.
모니터
세마포는 꽤 좋아보이지만, 매번 임계 구역에 일일히 앞뒤로 wait과 signal 함수를 붙이기가 귀찮습니다.
wait <-> signal 위치를 서로 바꿔 적거나, wait을 두 번 적을 수도 있죠.
개인적으로 비슷한 경험을 몇 번 해봤던 것 같네요 ㅎㅎ..;
때문에 이를 해결하고자 모니터(monitor)가 등장했습니다.
공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리하여
프로세스는 반드시 인터페이스를 통해 공유 자원에 접근합니다.
모니터를 통해 공유 자원에 접근하려는 프로세스를 큐에 삽입 후
큐에 있는 순서대로 공유 자원을 이용하죠.
모니터는 공유 자원을 다루는 인터페이스에 접근하기 위한 큐(모니터에 진입하기 위한 큐)를 만들고,
모니터 안에 항상 하나의 프로세스만 들어오도록 하여
상호 배제를 위한 동기화를 제공합니다.
모니터는 특정 조건을 바탕으로 프로세스를 실행 및 일시 중단하기 위해
조건 변수(condition variable)을 사용합니다.
프로세스나 스레드의 실행 순서를 제어하기 위해 사용하는 특별한 역할을 하는 변수지요.
조건 변수로서는 wait과 signal 연산을 수행할 수 있는데,
wait은 호출한 프로세스의 상태를 대기 상태로 전환 + 일시적으로 조건 변수에 대한 대기 큐에 삽입합니다.
이 때 모니터에 진입하기 위해 삽입되는 큐(상호 배제를 위한 큐)와
wait가 호출되 실행 중단된 프로세스들이 삽입되는 조건 변수에 대한 큐는 다릅니다.
전자는 모니터에 한 번에 하나의 프로세스만 진입하기 위해,
후자는 모니터에 이미 진입한 프로세스의 실행 조건이 만족될 때 까지
잠시 실행이 중단되 만족될 때까지 잠시 실행 중단되어 기다리기 위해 만들어진 큐입니다.
조건 변수 x에 대해,
한 프로세스가 x.wait()을 했다고 해보죠.
이 프로세스는 조건 변수 x에 대한 큐에 삽입되므로
모니터는 다시 비게되어 다른 퓨ㅡ로세스가 모니터 안에 들어올 수 있게 됩니다!
wait 연산으로 중지된 프로세스는 다른 프로세스의 signal 연산으로 실행이 재개될 수 있는대,
signal은 wait을 호출해 큐에 삽입된 프로세스의 실행을 재개하는 것으로 볼 수 있습니다.
모니터는 조건 변수를 사용해 아래와 같은 프로세스 실행 순서 제어를 위한 동기화를 제공합니다.
이제 모니터를 사용하여 코드도 짜봅시다.
앞선 예제들이 C++ - 파이썬 이였으니 이번에는 자바인가? 싶었는데 아니나 다를까 자바였습니다.
때문에 별 고민하지 않고 붙여넣었는데... 컴파일 오류가 발생했습니다
자세히보니 synchronized가 아니라 syncronized 더군요.
오타인 것 같아 깃헙에 이슈를 남겼는데 1시간도 안되서 답변 및 예제 코드 수정까지 하셨습니다..!
어마어마하게 빠른 피드백에 감동했어요..!
public class Test<E> {
private static final int BUFFER_SIZE = 5;
private E[] buffer;
private int count;
private int in;
private int out;
public Test() {
count = 0;
in = 0;
out = 0;
buffer = (E[]) new Object[BUFFER_SIZE];
}
/* 생산자가 호출하는 코드 */
public synchronized void insert(E item) {
while (count == BUFFER_SIZE) {
try {
wait();
} catch (InterruptedException ie) {
}
}
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
count++;
notify();
}
/* 소비자가 호출하는 코드 */
public synchronized E remove() {
E item;
while (count == 0) {
try {
wait();
} catch (InterruptedException ie) {
}
}
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
notify();
return item;
}
}
class Test<E> {
private val buffer: Array<E?>
private var count = 0
private var `in` = 0
private var out = 0
init {
buffer = arrayOfNulls<Any>(BUFFER_SIZE) as Array<E?>
}
/* 생산자가 호출하는 코드 */
@Synchronized
fun insert(item: E) {
while (count == BUFFER_SIZE) {
try {
(this as Object).wait()
} catch (ie: InterruptedException) {
}
}
buffer[`in`] = item
`in` = (`in` + 1) % BUFFER_SIZE
count++
(this as Object).notify()
}
/* 소비자가 호출하는 코드 */
@Synchronized
fun remove(): E? {
while (count == 0) {
try {
(this as Object).wait()
} catch (ie: InterruptedException) {
}
}
val item = buffer[out]
out = (out + 1) % BUFFER_SIZE
count--
(this as Object).notify()
return item
}
companion object {
private const val BUFFER_SIZE = 5
}
}
자바만 하기엔 심심하니 코틀린으로도 변환해봤습니다.
자바에서는 synchronized 키워드를, 코틀린에서는 @Synchronized 어노테이션을 붙임으로써
모니터를 사용할 수 있습니다.
(코틀린에서는 in이 예약어이기 때문에 `in`와 같이 백틱으로 감싸줬습니다)
synchronized 키워드 혹은 @Synchronized 어노테이션이 붙은 메서드를 호출하기 위해서는
락을 먼저 흭득해야 하며, 락을 흭득할 수 없다면 스레드는 그대로 대기 상태로 전환됩니다.
synchronized 메서드를 실행하는 스레드가 메서드 실행을 종료하면 락이 해제되고
대기 상태에 있던 스레드가 깨어나 재실행됩니다.
교착상태
도심 속 교차로에서 차가 꽉 막혀 움직이지 못하는 상태가 더러 있습니다.
정체 현상이 없을 거라 생각했던 회전 교차로 역시 정체 현상이 생길 수 있죠.
프로세스 역시 위와 마찬가지로
두 개 이상의 프로세서가 서로가 가진 자원을 무작정 기다린다면
무한정 대기하게 되는 교착 상태가 발생할 수 있습니다.
식사하는 철학자 문제
식사하는 철학자 문제(dining philosophers problem)은 교착상태를 설명하기에 아주 고전적이고 좋은 예제입니다.
동그란 원탁에 다섯 명의 철학자들이 앉아있습니다.
각 철학자 앞에 식자와 포크가 있죠.
그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있습니다.
철학자들은 아래와 같은 순서로 식사를 합니다.
음, 딱 봤을 때 별 다른 문제점은 없는 것 같군요.
하지만 모든 철학자가 동시에 식사를 시작하면 어떤 철학자도 식사를 할 수 없습니다.
모든 철학자가 왼쪽 포크를 집어든다면, 모든 철학자에게 오른쪽 포크가 없으니까요.
모든 철학자는 다른 철학자들이 포크를 내려놓기만을 기다릴 뿐이죠.
이와 같이 일어나지 않을 상황을 무작정 기다리는 것을 교착 상태(deadlock)이라 합니다.
이제 철학자를 프로세스 혹은 스레드,
포크를 자원,
생각하는 행위를 자원에 접근하기 위해 대기하는 것으로 글자를 바꿔볼께요.
뮤텍스 락을 예시로 들어보겠습니다.
프로세스 A는 임계 구역 진입 전에 lock1을 잠궜습니다.
프로세스 B는 임계 구역 진입 전에 lock2를 잠궜고요.
프로세스 A는 lock2가 false가 되길 기다리고, B는 lock1이 false가 되길 기다린다면 어떨까요?
두 프로세스가 서로가 끝나기를 기대하며 무작정 대기하는 상태가 됩니다!!! ㅇㅁㅇ!!!
자원 할당 그래프
교착 상태는 자원 할당 그래프(resoure-allocation graph)를 통해 단순하게 표현할 수 있습니다.
원 : 프로세스
자원 : 사각형
사용할 수 있는 자원의 개수 : 사각형 내 점
프로세스가 자원을 할당받아 사용 중 : 자원 -> 프로세스 화살표
프로세스가 어떤 자원을 기다리고 있음 : 프로세스 -> 자원 화살표
이제 철학자 문제와 교착상태에 빠진 프로세스들을 자원 할당 그래프로 나타내봅시다.
교착상태의 특징이 보이시나요? 자원 할당 그래프가 원의 형태를 띄고 있습니다.
교착상태 발생 조건
상호 배제
교착상태의 발생의 근본적인 이유입니다. 자원을 한 번에 하나의 프로세스만 사용 하능하다는 점이죠.
점유와 대기
'왼쪽 포크'를 들고 다른 철학자의 포크를 기다렸습니다. 자원을 가진 채 다른 자원을 가진 것이죠.
'자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태'를 점유와 대기라 말합니다.
비선점
철학자들이 다른 사람의 포크를 뺏어 먹는다면 교착상태는 발생하지 않습니다.
프로세스가 다른 프로세스의 자원을 뺏는다면 교착상태 역시 발생하지 않지요.
원형 대기
프로세스가 요청 및 할당받은 자원이 원의 형태를 이룹니다.
자원 할당 그래프가 원형 상태면 이를 원형 대기라 표현합니다.
(원형 대기일 경우 교착 상태가 발생할 가능성이 있다는 것이지,
무조건 교착상태가 발생되는 것은 아닙니다)
교착 상태 해결 방법
교착 상태를 해결하는 데에는 예방 및 회피, 검출 후 회복 등이 있습니다.
교착 상태 예방
불이 나기 위한 3요소. 기억나시나요?
열, 산소, 가연물 입니다. 이 셋 중 하나라도 없다면 연가 되지 않습니다.
셋 중 하나라도 없으면 불이 나지 않는다.
반대로 말하면 셋 중 한 요소라도 제거하면 불을 소화할 수 있다.
때문에 맞불을 질러 불을 막기 위해 불을 제압하는 방법도 있습니다.
이와 마찬가지로, 교착상태의 발생 조건을 충족하게 못하게 하여
교착 상태를 예방하는 방법이 있습니다.
자원의 상호 배제를 없애자.
자원의 상호 배제를 없없앤다는 것은 모든 자원을 공유 가능하게 한다는 말고 같습니다.
이론적으로는 교착 상태를 막을 수는 있으나... 현실적으로 무리가 좀 있습니다.
점유와 대기를 없애자.
포크 하나를 쥔 채로 다른 포크를 기다리지 못하게 합니다.
두 개를 한 꺼번에 들 수 있을 때에만 들게 하는것이죠.
이 역시 이론적으로 교착 상태를 막을 수는 있으나... 자원의 활용률이 낮아질 수 있습니다.
적은 자원을 사용하는 프로세스 부터 자원을 빠르게 쇽쇽 채가니
많은 자원을 사용하는 프로세스는 무한정 기다리는 기아 현상이 발생할 수 있습니다.
비선점 조건을 없애자.
다른 철학자의 포크를 뺏어오는 방법입니다.
CPU와 같이 선점 가능한 자원에는 효과적입니다.
하지만 프린터와 같이 선점이 불가능한 자원에 대해서는 빼앗아 사용하기가 어려워 범용성은 조금 떨어집니다.
원형 대기 조건을 없애자.
포크에 번호를 붙이고, 번호가 낮은 순 -> 높은 순으로 포크를 들게 합시다.
5번 포크를 집어든채로 1번 포크를 집어들 수 없기 때문에 원형 대기는 발생하지 않습니다.
원형 식탁을 일자 테이블 식탁으로 바꾼 것과 비슷하죠.
앞선 세 방법에 비해 실용적이나, 수많은 자원에 번호를 붙이는 건 그리 간단하지 않기도 하고,
자원에 번호를 붙이는 순서에 따라 효율성이 달라질 수 있습니다.
교착 상태 회피
이는 교착 상태가 발생하지 않을 정도로만 자원을 쪼금씩 할당하는 방식입니다.
포크가 1000개가 있고, 철학자들이 1~2개 포크만 요구핟나면 교착 상태는 일어나지 않겠죠?
안전 순서열
안전 순서열은 교착 상태 없이 안전하게 프로세스에 자원을 할당하는 순서입니다.
안전 상태
안전 순서열대로 프로세스에 자원을 할당해 교착상태가 발생하지 않는 상태를 의미합니다
불안전 상태
안전 순서열이 없어 교착상태가 발생할 수 있는 상태입니다.
운영체제가 교착 상태를 회피하기 위해서는 시스탬 상태가 안전 상태 -> 안전 상태로 가는 경우에만
자원을 할당하면 됩니다.
교착 상태 검출 후 회복
예방 + 회피가 교착상태 발생을 막기 위함이였다면,
검출 후 회복은 발생을 인정 및 사후조치입니다.
선점을 통한 회복
교착 상태가 해결될 때 까지 한 프로세스에 자원을 몰아주는 방식입니다.
프로세스 강제 종료를 통한 회복
심플 이즈 베스트일까요? 교착 상태가 없어질 때 까지 하나씩 종료하거나, 전체 종료하거나.
확실하면서 간단합니다.
다만 작업 내용을 잃을 수 있습니다.
무시하기
교착 상태를 아예 무시하는 방법도 있습니다. 타조 알고리즘이라고 하는데요.
어... 머리는 제일 편한 방법인 것 같습니다.
숙제
p. 363의 확인 문제 1번
4 -> 반드시 바쁜 대기를 해야 하는 것은 아님.
대기 상태로 진입 -> 자원 이용 가능 시 재개하는 버전도 있음
Ch. 12(12-1) 임계 구역, 상호 배제 개념 정리
본문 내용으로 대체
마치며
12~13 챕터는 유독 길었던 느낌이 납니다.
쓰고나니 힘드네요.
오늘 배웠던 내용을 되새겨,
불의 연소조건을 없애 불을 없애고,
교착상태의 발생 조건을 없애 교착상태를 해결하듯이
피로와 고통의 발생 요소를 제거해 고통을 없..애는 건 안됩니다.
'CS 지식 > 운영체제 | 컴퓨터구조' 카테고리의 다른 글
| [혼공스터디 11기] 컴퓨터구조+운영체제 회고 (0) | 2024.02.17 |
|---|---|
| [혼공컴운] 6주차_가상 메모리와 파일 시스템 (0) | 2024.02.08 |
| [혼공컴운] 4주차_운영체제, 프로세스, 스레드 (2) | 2024.01.26 |
| [혼공컴운] 3주차_메모리, 캐시, 보조기억장치, 입출력장치 (0) | 2024.01.19 |
| [혼공컴운] 2주차_CPU의 작동원리 (3) | 2024.01.13 |
