교착상태, 교착상태 특성, 교착상태 예방, 상호배제, 점유대기, 비선점, 환형대기

 

1. 교착상태의 개요 

 

요구-> 사용 -> 해제

요구과정에서 가용한 자원이 없으면 자원을 획득할 때까지 대기 

 

 

교착상태: 여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느 쪽도 영원히 진행하지 못하는 상태

기아상태: 프로세스 또는 스레드가 자원에 접근하고자 하지만 해당 자원을 사용할 수 없는 상태를 의미

 

교착 상태는 작업들이 서로 무한히 기다리는 상태를 나타내는 반면, 기아 상태는 자원에 대한 접근이 계속해서 차단되는 상태를 나타낸다.

 

 

 

2. 교착상태의 특성

 

교착상태의 필요조건:

- 상호배제

- 점유대기

- 비선점

- 환형대기 

-> 4가지 조건이 동시에 만족될 때 교착상태 발생가능

(가능성이 생겼다는 의미이다.) 

 

 

상호배제(mutual exclusion) 조건

- 프로세스가 자원에 대한 베타적인 통제권을 요구

- 적어도 하나 이상의 자원은 여러 프로세스에 의해 동시에 사용될 수 없음

- 다른 프로세스가 점유한 자원이 필요하면 반드시 대기 

 

 

 

점유대기 (hold and wait) 조건

- 프로세스가 이미 한 자원을 할당 받아 점유하고 있는 상황에서 다른 프로세스가 점유하고 있는 또 다른 자원을 요구하여 해제되기를 기다리는 상황 

 

 

비선점(no preemption) 조건

- 프로세스에 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에는 해제되지 않음

- 할당된 자원은 타의에 의해서는 해제되지 않음 

 

 

환형대기(cicular wait) 조건 

- 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기하는 상황

 

 

 

 

자원할당 그래프 G = (V, E) 

- V: 정점의 집합으로 P와 U의 합집합 

  - P = {p1, p2, ... pn } = n 개의 프로세스 

  - R = {r1, r2, ... rn } = r개의 자원 

- E: 방향 있는 간선의 집합 E = Q와 S의 합집합 

  -  Q = {(pi, rj): pi ∈ P, rj ∈ R} : 프로세스 pi가 자원 rj를 요구 

  => 요구간선 

- S: {(rj, pi): rj  ∈ R, pi  ∈ P} : 자원 rj가 프로세스 pi에 할당 

  => 할당간선 

 

자원할당 그래프의 예 

- 정점의 집합 V = P와 R의 합집합 

  -> 프로세스 집합 P = {p1, p2, p3} 

  -> 자원 집합 R = {r1, r2, r3} 

- 방향 있는 간선의 집합 E = Q와 U의 합집합 

 

요구간선 Q{(p1, r2)} 

할당간선 S {(r1, p1), (r2, p2)} 

 

 

 

 

p2가 r3을 요구하는 경우

- 요구간선 (p2, r3) 추가 

- 가용한 단위 자원이 존재하면 할당 간선  (r3, p2)로 바꿈 

 

 

 

 

교착상태의 필요조건 표현

- 상호배제: 하나의 할당간선 

- 점유대기: 한 프로세스에 할당간선과 요구간선을 연결 

- 비선점: 요구간선

- 환형대기: 사이클 

 

 

사이클 없음 -> 교착상태 없음

사이클 있음 -> 교착상태 발생 가능 

 

교착상태 예 

 

교착상태가 아닌 예 

 

 

r1 -> p4가 해제될 수도 있으므로 

 

 

 

 

교착상태 처리 기법 

- 교착상태 예방: 교착상태의 네 가지 필요조건이 동시에 만족되는 것을 피하여 교착상태가 발생하지 않도록 하는 방법

- 교착상태 회피: 프로세스에 필요한 자원의 최대량에 대한 정보를 이용하여 교착상태가 발생하지 않도록 하는 방법

- 교착상태 탐지 및 복구: 교착상태의 발생 여부를 조사하여 발생한 경우에는 적절한 조치를 취해 정상상태로 복구하는 방법 

 

 

 

 

자원할당 그래프 자바 코드 구현 

 

package os.resourceallocation;

public class Resource {
    private String name;
    private int availableUnits;
    private Process allocatedProcess;

    public Resource(String name, int availableUnits, Process allocatedProcess) {
        this.name = name;
        this.availableUnits = availableUnits;
        this.allocatedProcess = allocatedProcess;
    }

    public String getName() {
        return name;
    }

    public int getAvailableUnits() {
        return availableUnits;
    }

    public void setAvailableUnits(int availableUnits) {
        this.availableUnits = availableUnits;
    }

    public Process getAllocatedProcess() {
        return allocatedProcess;
    }

    public void setAllocatedProcess(Process allocatedProcess) {
        this.allocatedProcess = allocatedProcess;
    }
}

 

 

package os.resourceallocation;
import java.util.HashMap;
import java.util.Map;

public class Process {

    private String name;
    private Map<Resource, Integer> maxDemand;
    private Map<Resource, Integer> allocatedResources;
    private Map<Resource, Integer> remainingDemand;

    public Process(String name) {
        this.name = name;
        this.maxDemand = new HashMap<>();
        this.allocatedResources = new HashMap<>();
        this.remainingDemand = new HashMap<>();
    }

    // 최대 요구량 설정
    public void setMaxDemand(Resource resource, int maxUnits) {
        maxDemand.put(resource, maxUnits);
    }

    // 현재 할당 자원 설정
    public void allocateResource(Resource resource, int units) {
        int currentAllocation = allocatedResources.getOrDefault(resource, 0);
        allocatedResources.put(resource, currentAllocation + units);
    }

    // 할당 해제
    public void deallocateResource(Resource resource, int units) {
        int currentAllocation = allocatedResources.getOrDefault(resource, 0);
        int newAllocation = Math.max(currentAllocation - units, 0);
        if (newAllocation == 0) {
            allocatedResources.remove(resource);
        } else {
            allocatedResources.put(resource, newAllocation);
        }
    }

    public void setRemainingDemand(Resource resource, int remainingUnits) {
        remainingDemand.put(resource, remainingUnits);
    }

    public String getName() {
        return name;
    }

    public int getMaxDemand(Resource resource) {
        return maxDemand.getOrDefault(resource, 0);
    }

    public int getAllocatedResource(Resource resource) {
        return allocatedResources.getOrDefault(resource, 0);
    }

    public int getRemainingDemand(Resource resource) {
        return remainingDemand.getOrDefault(resource, 0);
    }

    @Override
    public String toString() {
        return name;
    }
}

 

 

package os.resourceallocation;

public class Pair<T, U> {
   private final T first;
   private final U second;

   public Pair(T first, U second) {
      this.first = first;
      this.second = second;
   }

   public T getFirst() {
      return first;
   }

   public U getSecond() {
      return second;
   }
}

package os.resourceallocation;

import java.util.*;

public class ResourceAllocationGraph {
    public static void main(String[] args) {
        // 프로세스 집합 P
        Process p1 = new Process("p1");
        Process p2 = new Process("p2");
        Process p3 = new Process("p3");

        // 자원 집합 R
        Resource r1 = new Resource("r1", 1, p1 );
        Resource r2 = new Resource("r2", 1, p2);
        Resource r3 = new Resource("r3", 2, p3);

        // 요구 간선 집합 Q
        Set<Pair<Process, Resource>> Q = new HashSet<>();
        Q.add(new Pair<>(p1, r2));

        // 할당 간선 집합 S
        Set<Pair<Resource, Process>> S = new HashSet<>();
        S.add(new Pair<>(r1, p1));
        S.add(new Pair<>(r2, p2));
        S.add(new Pair<>(r3, p3));

        // 자원 할당 그래프 출력
        System.out.println("프로세스 집합 P:");
        System.out.println(p1.getName());
        System.out.println(p2.getName());
        System.out.println(p3.getName());
        System.out.println();

        System.out.println("자원 집합 R:");
        System.out.println(r1.getName() + " (할당 중: " + r1.getAllocatedProcess().getName() + ")");
        System.out.println(r2.getName() + " (할당 중: " + r2.getAllocatedProcess().getName() + ")");
        System.out.println(r3.getName() + " (할당 중: " + r3.getAllocatedProcess().getName() + ")");
        System.out.println();

        System.out.println("요구 간선 집합 Q:");
        for (Pair<Process, Resource> edge : Q) {
            System.out.println(edge.getFirst().getName() + " -> " + edge.getSecond().getName());
        }
        System.out.println();

        System.out.println("할당 간선 집합 S:");
        for (Pair<Resource, Process> edge : S) {
            System.out.println(edge.getFirst().getName() + " -> " + edge.getSecond().getName());
        }
    }


}

 

 

 

3. 교착상태 예방

 

상호배제 조건 제거

- 공유할 수 있는 자원: 상호배제 필요 없음(예: 읽기 전용 파일) 

- 공유할 수 없는 자원: 반드시 상호배제 필요 (예: 프린터)

-> 상호배제 조건 제거로 교착 상태 예방은 불가능

-> 즉 이런 자원의 상호배제는 무조건 필요하기 때문 

 

 

점유 대기 조건 제거 : 점유를 없애거나 대기를 없애거나 

- 자원을 점유했을 때 대기하지 않아야 함 

  -> 프로세스가 앞으로 필요하 모든 자원을 처음에 한꺼번에 요구하여 할당받음 -> 자원 이용률 낮아짐, 기아 상태 가능 

- 대기할 때 자원을 점유하고 있지 않아야 함 

  -> 새로운 자원을 요구할 때 할당받았던 자원을 모두 해제 -> 점유 도중 해제 할 수 없는 (프린터 같은) 자원에는 적용 불가 

 

 

비선점 조건 제거 

- 선점이 가능하도록 함 (특성에 따라 불가능한 경우도 존재: 프린터) 

- 다른 프로세스가 대기할 가능성 줄이기: 점유 대기 상황이 발생하면 할당받았던 자원을 모두 해제 (프린터 같은 경우 적용 불가) 

 

 

환형대기 조건 제거

- 모든 자원에 일련번호를 지정 

- 함수 f: R -> N 

- 방법 1: 프로세스가 자원을 요구할 때 일련번호 기준으로 항상 오름차순이 되도록 요구, 가장 최근에 할당 받은 자원이 ri이면 다음에 요구할 자원 rj는 f(ri) < f(rj)를 만족 

=> 즉 기존의 것보다 크게 일련번호를 요구하면 사이클이 생기지 않는다. 

- 방법 2: 프로세스가 자원을 요구할 때 일련번호가 작은 자원만 점유하도록 함 = 자원 rj요구하려면 점유 중인 자원 중 f(rj) <= f(ri)인 자원 ri는 모두 해제 

 

=> 결과적으로 방법 1이나 2나 점유하고 있는 거보다 요구하는 게 크도록 하는 방법이다. 

 

=> 점유대기 중인 프로세스는 점유중인 자원의 일련번호보다 대기 중인 자원의 일련번호가 큼 

 

- 이와 같은 방식은 프로세스마다 요구순서가 다를 수 있어 자원의 일련번호 설정이 어려움 

- 요구순서가 일련번호 오름차순을 못 지키면 점유자원 해제 필요하나 적용 불가한 자원도 존재 

 

 

---

참고자료: 운영체제(김진욱, 이인복 공저, KNOU press 출판)