메모리에 존재하는 P개의 프로세스와 각 프로세스가 실행을 완료하기 위해 필요한 N개의 자원이 주어졌을 때, 교착 상태(deadlock)가 절대 발생하지 않도록 하기 위해 프로세스에 할당해야 하는 최소 자원의 개수 R을 구하는 것이 이 글의 목표입니다.
교착 상태(Deadlock)란?
교착 상태란 운영체제에서 여러 프로세스가 메모리에 상주하고 있음에도 불구하고, 프로그램 실행에 필요한 자원을 다른 프로세스가 점유하고 있고 그 프로세스 역시 또 다른 자원을 기다리고 있는 상황 때문에 어느 프로세스도 실행을 진행하지 못하는 상태를 말합니다.
예를 들어 메모리에 두 개의 프로세스 P1과 P2가 있다고 가정해 보겠습니다. P1은 자원 R1을 필요로 하고, P2는 자원 R2를 필요로 합니다. 그런데 P1이 자원 R2를 점유한 채 R1을 기다리고, 반대로 P2는 자원 R1을 점유한 채 R2를 기다린다면 어떻게 될까요? 이때 교착 상태가 발생합니다.
이러한 상황은 순환 대기(circular wait)의 전형적인 예로, 교착 상태를 일으키는 대표적인 원인 중 하나입니다. 따라서 교착 상태를 예방하려면 프로세스들이 사용할 수 있는 자원의 개수를 미리 계산하여 충분히 확보해 두어야 합니다.
교착 상태가 발생하지 않는 조건
R >= P × (N − 1) + 1
- R : 필요한 자원(Resources)의 개수
- P : 프로세스(Processes)의 개수
- N : 각 프로세스가 필요로 하는 자원(Need)의 개수
이 공식의 직관적인 의미는 다음과 같습니다. 각 프로세스가 최악의 경우 (N − 1)개의 자원을 점유한 상태에서 나머지 1개를 추가로 기다릴 수 있습니다. 모든 프로세스가 이런 상태에 빠져도 자원이 하나라도 더 남아 있다면, 그 자원을 배정받은 프로세스는 실행을 마치고 자원을 반납하게 되므로 순환 대기가 깨지게 됩니다.
예제
입력: 프로세스 수 = 5, 필요 자원 = 3 출력: 필요한 최소 자원 수 = 11 입력: 프로세스 수 = 7, 필요 자원 = 2 출력: 필요한 최소 자원 수 = 8
접근 방법
- 메모리 내 프로세스의 개수와 각 프로세스가 필요로 하는 자원의 개수를 입력받습니다.
- 위에서 소개한 공식을 적용하여 필요한 자원의 개수를 계산합니다.
- 계산 결과를 화면에 출력합니다.
알고리즘
START
Step 1-> 최소 자원 수를 계산하는 함수 선언
int min_resource(int process, int need)
int calculate = 0 으로 선언
calculate = process * (need - 1) + 1 대입
calculate 반환
Step 2-> main() 함수에서
int process = 5, need = 3 선언
min_resource(process, need) 호출
STOPC++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
// 필요한 최소 자원 수를 계산하는 함수
int min_resource(int process, int need) {
int calculate = 0;
calculate = process * (need - 1) + 1;
return calculate;
}
int main() {
int process = 5, need = 3;
cout << "필요한 최소 자원 수 : " << min_resource(process, need);
return 0;
}실행 결과
필요한 최소 자원 수 : 11
위 프로그램은 프로세스가 5개이고 각 프로세스가 3개의 자원을 필요로 하는 경우, 5 × (3 − 1) + 1 = 11개의 자원만 확보하면 어떤 경우에도 교착 상태가 발생하지 않음을 보여줍니다. 시간 복잡도는 단순 곱셈과 덧셈 연산만 수행하므로 O(1)로 매우 효율적입니다.