교착 상태

교착 상태

• Deadlock
• 다중 프로그래밍 시스템에서 프로세스가 결코 일어나지 않을 사건을 기다리는 상태
• 프로세스가 교착 상태에 빠지면 작업이 정지되어 명령 진행 불가
• 운영체제가 교착 상태를 해결하지 못하면, 시스템 운영자·사용자는 작업 교체 및 종료하는 외부 간섭으로 해결해야 함
• 하나 이상의 작업에 영향을 주어 무한 대기
• 두 프로세스가 사용하는 자원(비공유)이 서로 기다리고 있을 때 발생
• 자원 해제 요청을 받아들일 때까지 프로세스들은 작업 진행 불가
• 자원 해제 수신 때까지 현재 보유 자원도 해제 불가

프로세스의 자원 사용 순서

1. 자원 요청
   • 프로세스가 필요한 자원 요청
   • 해당 자원을 다른 프로세스가 사용 중이면 요청을 수락할 때까지 대기
2. 자원 사용
   • 프로세스가 요청한 자원을 획득하여 사용
3. 자원 해제
   • 프로세스가 자원 사용을 마친 후 해당 자원을 되돌려줌

교착 상태 발생 예시

• 스풀링 시스템
  • 쉽게 교착 상태에 빠짐
  • 디스크에 할당된 스풀 공간의 출력을 완료하지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지하면 발생
  • 스풀링 처리부에 공간이 넉넉하면 교착 상태 발생률 감소
  • 스풀링 파일의 일정 포화 임계치(Saturation Threshold)를 설정하여 교착 상태 예방 가능
• 디스크 공유
  • 디스크 사용에 제어가 없으면 프로세스들이 서로 충돌하는 명령 시 교착 상태 발생
• 네트워크
  • 네트워크가 붐비거나 입출력 버퍼 공간이 부족한 네트워크 시스템에 메시지 흐름을 제어하는 적절한 프로토콜이 없으면 교착 상태가 발생

교착 상태 발생 조건

1. 상호 배제
   • 자원을 최소 하나 이상 비공유, 한 번에 프로세스 하나만 해당 자원을 사용할 수 있어야 함
   • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 대기
2. 점유와 대기
   • 자원을 최소한 하나 정도 보유
   • 다른 프로세스에 할당된 자원 얻으려고 대기하는 프로세스가 있어야 함
3. 비선점
   • 자원 선점 불가, 자원은 강제로 빼앗을 수 없고 자원을 점유하고 있는 프로세스가 끝나야 해제
4. 순환(환형) 대기

• 상호 배제, 점유와 대기, 비선점만 만족해도 교착 상태 발생 가능 (발생하지 않을 수도 있음)
• 순환 대기는 1~3번의 조건을 만족할 때 발생할 수 있는 결과
• 순환 대기가 점유와 대기 조건을 포함하므로 네 가지 조건이 모두 독립적인 것은 아님

교착 상태의 표현

• 시스템 자원 할당 그래프인 방향 그래프로 표현
• 자원 할당 그래프
  • G = (V, E)로 구성
  • 정점 집합 V는 프로세스 집합 P = {P1, P2, ... , Pn}과 자원 집합 R = {R1, R2, ... , Rn}으로 나뉨
  • 간선 집합 E는 원소를 (Pi, Rj)나 (Rj, Pi)와 같은 순서쌍으로 나타냄

---

교착 상태의 해결 방법

1. 예방(prevention)
2. 회피(avoidance)
3. 탐지(detection) 및 회복

Havender의 교착 상태 예방 방법

• 상호 배제 예방: 각 프로세스는 필요한 자원을 한 번에 모두 요청해야 함
• 점유와 대기 예방: 요청한 자원을 모두 제공받기 전까지는 작업 진행 불가
• 비선점 예방: 어떤 자원을 점유하고 있는 프로세스의 요청을 더 이상 허용하지 않으면 점유한 자원을 모두 반납하고, 필요할 때 다시 자원 요청
• 순환 대기 예방: 모든 프로세스에 자원을 순서대로 할당

자원의 상호 배제 조건 방지

• 상호 배제는 '자원의 비공유'가 전제되어야 함
• 일반적으로 상호 배제 조건을 만족하지 않으면 교착 상태 예방 불가능

점유와 대기 조건 방지

• 점유와 대기 조건이 발생하지 않으려면 프로세스가 작업 수행 전에 필요한 자원을 모두 요청하고 획득해야 함
• 대기 상태에서는 프로세스가 자원 점유 불가능하므로 대기 조건 성립되지 않음 (최대 자원 할당)
• 자원 할당 시 시스템 호출된 프로세스 하나를 실행하는 데 필요한 모든 자원을 먼저 할당하고 실행 후 다른 시스템 호출에 자원 할당
• 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 것
• 프로세스가 자원을 더 요청하려면 자신에게 할당된 자원을 모두 해제해야 함
• 단점: 자원 효율성 너무 낮음, 기아 상태 발생 가능 (대화식 시스템에서 사용 불가)

비선점 조건 방지

• 이미 할당된 자원에 선점권이 없어야 한다는 전제 조건 필요
• 어떤 자원을 가진 프로세스가 다른 자원을 요청할 때 요청한 자원을 즉시 할당받을 수 없어 대기해야 한다면, 프로세스는 현재 가진 자원을 모두 해제
• 프로세스가 작업을 시작할 때는 요청한 새로운 자원과 해제한 자원을 모두 확보해야 함
• 이러한 방법은 비선점 조건을 효과적으로 무효화시키지만 이미 실행한 작업의 상태를 잃을 수도 있음
• 작업 상태를 쉽게 저장·복구할 수 있을 때나 빈번하게 발생하지 않을 때만 좋은 방법
• 전용 입출력장치 등을 빼앗아 다른 프로세스에 할당 후 복구하는 과정이 간단하지 않음
• 대안 1: 프로세스가 어떤 자원을 요청할 때 요청한 자원이 사용 가능한 지 검사 후 사용 가능할 경우 자원 할당
  • 사용 불가능할 경우 대기 프로세스가 요청한 자원을 점유하고 있는지 검사
  • 요청한 자원을 대기 프로세스가 점유하고 있다면, 자원을 해제하고 요청 프로세스에 할당
  • 요청한 자원을 사용할 수 없거나 실행 중인 프로세스가 점유하고 있다면 요청 프로세스는 대기
  • 프로세스가 대기하는 동안 다른 프로세스가 점유한 자원을 요청하면 자원을 해제할 수 있음
• 대안 2: 두 프로세스에 우선순위를 부여하고 높은 우선순위의 프로세스가 그보다 낮은 우선순위의 프로세스가 점유한 자원을 선점하여 해결
  • 프로세서 레지스터나 기억장치 레지스터와 같이 쉽게 저장되고 이후에 다시 복원하기 쉬운 자원에 사용
  • 프린터·카드판독기·테이프 드라이버 같은 자원에는 적용되지 않음

순환 대기 조건 방지

• 모든 자원에 일련의 순서 부여, 각 프로세스가 오름차순으로만 자원을 요청할 수 있게 함
• 이는 계층적 요청 방법으로 순환 대기의 가능성을 제거하여 교착 상태를 예방
• 예상된 순서와 다르게 자원을 요청하는 작업은 실제로 자원을 사용하기 전부터 오랫동안 자원을 할당받은 상태로 있어야 하므로, 상당한 자원 낭비를 초래
• 자원 집합을 R = {R1, R2, ... , Rn}이라고 가정
• 각 자원에 고유 숫자 부여 (어느 자원의 순서가 빠른지 알 수 있게 함)
• 이것은 1:1 함수 F:R → N으로 정의 (N은 자연수 집합)
• 자원 R의 집합에 CD 드라이브·디스크 드라이브·프린터가 포함된다면 함수 F는 아래와 같이 정의
  • F(CD 드라이브) = 2
  • F(디스크 드라이브) = 4
  • F(프린터) = 7

교착 상태 예방 시 고려할 규칙

• 각 프로세스는 오름차순으로만 자원 요청 가능
• 즉, 프로세스는 임의의 자원 Ri를 요청할 수 있지만 그 다음부터는 F(Rj) > F(Ri)일 때만 자원 Rj 요청 가능
• 데이터 형태 자원이 여러 개 필요하다면, 우선 요청할 형태 자원을 하나 정해야 함
• 앞서 정의한 함수를 이용하면 CD 드라이브와 프린터를 동시에 사용해야 하는 프로세스는 CD 드라이브 먼저 요청 후 프린터 요청

교착 상태 회피

• 목적: 덜 엄격한 조건을 요구하여 효율적인 자원 사용
• 교착 상태의 모든 발생 가능성을 미리 제거하는 것이 아님
• 교착 상태 발생 가능성을 인정하고(세 가지 필요조건 허용), 교착 상태가 발생하려고 할 때 적절히 회피하는 것
• 예방보다는 회피가 더 병행성을 허용
• 방법 1: 프로세스의 시작 중단
  • 프로세스의 요구가 교착 상태를 발생시킬 수 있다면, 프로세스 시작 중단
• 방법 2: 자원 할당 거부 (은행원 알고리즘)
  • 프로세스가 요청한 자원을 할당했을 때 교착 상태가 발생할 수 있다면, 요청한 자원을 할당하지 않음

프로세스의 시작 중단

• 교착 상태 회피를 위해 자원을 언제 요청하는지 추가 정보 필요
• 각 프로세스마다 요청과 해제에서 정확한 순서를 파악하고 있다면, 요청에 따른 프로세스 대기 여부 결정 용이
• 프로세스의 요청 수락 여부는 현재 사용 가능한 자원, 프로세스에 할당된 자원 등 각 프로세스에 대한 자원의 요청과 해제를 미리 알고 있어야 결정 가능
• 다양한 교착 상태 회피 알고리즘 중에서 가장 단순하고 유용한 알고리즘은 각 프로세스가 필요한 자원의 최대치(할당 가능한 자원 수)를 선언하는 것
• 프로세스가 요청할 자원별로 최대치 정보를 미리 파악할 수 있으면 시스템이 교착 상태가 되지 않을 확실한 알고리즘을 만들 수 있음
• 교착 상태 회피 알고리즘은 시스템이 순환 대기 조건이 발생하지 않도록 함
  • 자원 할당 상태 검사 (자원 할당 상태는 사용 가능한 자원 수)
  • 할당된 자원 수
  • 프로세스들 최대 요청 수로 정의
  • 각 프로세스에 자원을 할당할 수 있음
• 교착 상태를 예방할 수 있으면 안정된 상태가 됨
• 시스템에 안정 순서가 있으면 그 시스템은 안정 (순서가 없으면 불안정)
  • 안정 상태와 불안정 상태로 구분, 교착 상태는 불안정 상태에서 발생
  • 모든 사용자가 일정 기간 안에 작업을 끝낼 수 있도록 운영체제가 할 수 있으면 현재 시스템의 상태가 안정
  • 교착 상태는 불안정 상태이나 모든 불안정 상태가 교착 상태인 것은 아님
  • 상태가 안정하다면 운영체제는 불안정 상태와 교착 상태를 예방 가능
  • 불안정 상태의 운영체제는 교착 상태를 발생시키는 프로세스의 자원 요청 방지 불가

자원 할당 거부: 다익스트라의 은행원 알고리즘

• 자원의 할당 여부 결정 전에 미리 결정된 모든 자원의 최대 가능한 할당량을 시뮬레이션하여 한전 여부 검사
• 이후, 다음 대기 중인 다른 모든 활동의 교착 상태 가능성을 조사하여 안전 상태 여부 검사·확인
• 프로세스가 자원을 요청할 때마다 운영체제로 실행
• 자원 요청 승낙이 불안전한 상태에서 시스템을 배치할 수 있다고 판단하면 이 요청을 연기·거부하여 교착 상태 예방
• 따라서 각 프로세스에 자원을 어떻게 할당(자원 할당 순서 조정)할 것인지 정보가 필요하므로 각 프로세스가 요청하는 자원 종류의 최대 수를 알아야 함 (이를 통해 교착 상태 회피 알고리즘 정의 가능)
• 은행원 알고리즘의 단점
  • 할당할 수 있는 자원의 일정량 요청: 자원은 수시로 유지 보수가 필요하고 고정이나 예방 때문에 일정하게 남아 있는 자원 수 파악 골란
  • 사용자 수가 일정해야 하지만 다중 프로그래밍 시스템에서는 사용자 수가 항상 변함
  • 교착 상태 회피 알고리즘을 실행하면 시스템 과부하 증가
  • 프로세스는 자원을 보유한 상태로 끝낼 수 없음 (시스템에서는 이보다 더 강력한 보장 필요)
  • 사용자가 최대 필요량을 미리 알려주도록 요청하지만, 자원 할당 방법이 점점 동적으로 변하면서 사용자의 최대 필요량 파악 곤란
  • 항상 불안정 상태를 방지해야 하므로 자원 이용도가 낮음

교착 상태 회복

1. 시스템 상태를 검사하는 교착 상태 탐지 알고리즘
2. 교착 상태에서 회복시키는 회복 알고리즘

• 교착 상태 파악을 위해 교착 상태 탐지 알고리즘을 언제 수행해야 하는지 결정하기 어려움
• 교착 상태 탐지 알고리즘을 자주 실행하면 시스템의 성능 낮아짐
• 교착 상태에 빠진 프로세스를 빨리 발견하여 자원의 유휴 상태 방지 가능, 자주 실행하지 않으면 반대 상황 발생
• 탐지와 회복 방법은 필요한 정보를 유지하고 탐지 알고리즘을 실행시키는 비용뿐 아니라 교착 상태 회복에 필요한 부담까지 요청

탐지 알고리즘 호출

• 교착 상태 발생 빈도수와 교착 상태가 발생했을 때 영향을 받는 프로세스 수에 따라 결정
• 교착 상태가 자주 발생하면 탐지 알고리즘도 더 자주 호출
• 일단 교착 상태가 발생하면 해결할 때까지 프로세스에 할당된 자원들은 유휴 상태 및 교착 상태의 프로세스 수는 점점 증가
• 어떤 프로세스라도 허용할 수 없는 요청을 하면 즉시 교착 상태
• 요청할 때마다 교착 상태 탐지 알고리즘 호출하면 교착 상태 회피 가능하지만 연산 시간 부담
• 좀 더 경제적인 방법은 호출 빈도를 줄임
• 시간마다 또는 CPU 이용률이 일정 이하로 떨어질 때마다 호출하는 것

교착 상태 회복 방법: 프로세스 중단

1. 교착 상태 프로세스 모두 중단
   • 교착 상태의 순환 대기를 확실히 해결하지만, 자원 사용과 시간면에서 비용 많이 들어감
   • 오래 연산했을 가능성이 있는 프로세스의 부분 결과를 폐기하여 다시 연산해야 함
2. 한 프로세스씩 중단
   • 한 프로세스 중단할 때마다 교착 상태 탐지 알고리즘을 호출하여 프로세스가 교착 상태에 있는지 확인
   • 교착 상태 탐지 알고리즘을 호출하는 부담이 상당히 크다는 것이 단점
3. 프로세스 중단이 쉽지 않을 수도 있음
   • 프로세스가 파일을 업데이트하다가 중단된다면 해당 파일은 부정확한 상태
   • 마찬가지로 프로세스가 데이터를 프린터에 인쇄하고 있을 때 중단하면 다음 인쇄를 진행하기 전에 프린터의 상태를 정상 상태로 되돌려야 함
4. 최소 비용으로 프로세스들을 중단하는 우선순위 선정
   • 프로세스가 수행된 시간과 앞으로 종료하는 데 필요한 시간
   • 프로세스가 사용한 자원 형태와 수
   • 프로세스를 종료하는 데 필요한 자원 수와 프로세스 수
   • 프로세스가 대화식 혹은 일괄식인지에 대한 여부

교착 상태 회복 방법: 자원 선점

• 선점 자원 선택
  • 프로세스를 종료할 대 비용을 최소화하려면 적절한 선점 순서 결정
  • 비용 요인에는 교착 상태 프로세스가 점유한 자원 수, 교착 상태 프로세스가 지금까지 실행하는데 소요한 시간 등 매개변수
• 복귀
  • 필요한 자원을 잃은 프로세스는 정상적으로 실행 불가
  • 프로세스를 안정 상태로 복귀
  • 프로세스를 교착 상태에서 벗어날 정도로만 복귀시키는 것이 더 효과적
  • 단, 시스템이 실행하는 모든 프로세스의 상태 정보가 유지된다는 것이 부담
• 기아
  • 동일한 프로세스가 자원들을 항상 선점하지 않도록 보장할 때, 동일한 프로세스를 희생자로 선택할 경우 프로세스가 짧은 시간 동안만 희생자로 지정되도록 보장해야 함

철학자 문제

• 철학자는 프로세스, 젓가락은 자원을 의미
• 교착 상태의 4가지 필요 조건

구분	예
상호 배제	젓가락은 한 번에 한 철학자만 사용
점유 및 대기	잡은 젓가락은 계속 잡은 채로 반대쪽 젓가락을 기다림
비선점	타인의 젓가락을 강제로 뺏을 수 없음
순환 대기	모든 철학자들은 오른쪽에 앉은 철학자가 젓가락을 놓기를 기다림

• 철학자는 스레드, 젓가락은 세마포어로 표현
• 상호 배제(mutex): 젓가락은 한 번에 한 철학자만 들 수 있다는 의미 → 초기화 값 1
• 프로그램 1은 교착 상태의 4가지 필요조건을 만족
• 실행 시 무한루프를 돌며 eating과 thinking을 출력
• 어느 순간 데드락 발생 / 출력 정지

교착 상태 해결

import java.util.concurrent.Semaphore;
class Philosopher extends Thread {
    int id; // 철학자 id
    Semaphore left, right; // 왼쪽, 오른쪽 젓가락
    Philosopher(int id, Semaphore left, Semaphore right){
        this.id = id;
        this.left = left;
        this.right = right;
    }

public void run() {
    try {
        while(true) {
            left.acquire();
            right.acquire();
            eating();
            right.release();
            left.release();
            thinking();
        }
    } catch (InterruptedException e) {}
}

void eating() {
    System.out.printIn("[" + id + "] eating..");
}
void thinking() {
    System.out.printIn("[" + id + "] thinking..");
}

교착 상태 해결: 개선한 소스

public void run() {
    try {
        while(true) {
            if(id%2==0){
                left.acquire();
                right.acquire();
            } else {
                right.acquire();
                left.acquire();
            }
            eating(); right.release(); left.release();
            thinking();
        }
    } catch (InterruptedException e) {}
}

모니터 이용

• 구성: 공유 자원, 접근 함수들, 큐 2개
• 2개의 큐는 각각 배타동기, 조건동기를 위한 것
• 배타동기 큐로 인해 공유 자원에는 항상 최대 1개의 스레드만 접근 가능 (mutex 보장)

해결 방안

• 하나의 스레드가 조건동기로 인해 block 되어 조건동기 큐에 들어가면(=wait) 새로운 스레드가 공유 자원에 접근 가능
• 새 스레드는 작업 종료 후 조건동기 큐에 갇힌 스레드를 깨울 수 있음(=notify)
• 깨어난 스레드는 현재 공유 자원에 접근 중인 다른 스레드가 없을 때 다시 임계구역에 진입할 수 있음
• 배타동기: synchronized 키워드 사용, 임계 구역에 synchronized 키워드만 붙이면 상호배제 보장됨

class SharedData {
    int balance; // 공유 자원 변수
    synchronized void add() {balance++;}
    synchronized void sub() {balance--;}
    int getBalance() {return balance;}
}

철학자 문제 적용

1. 젓가락을 세마포어 변수대신 클래스로 정의, 젓가락을 사용 중이라면 다른 스레드의 acquire 호출하여도 wait
2. 젓가락을 내려놓을 경우 wait의 기준은 inUse 플래그 조작
3. inUse 플래그 false로 초기화
4. 다른 스레드를 notify로 깨움

class Chopstick {
    private boolean inUse = false; // 플래그
    synchronized void acquire() throws InterruptedException {
        while (inUse)
            wait();
        inUse = true;
    }
    synchronized void release() {
        inUse = false;
        notify();
    }
}

다익스트라의 알고리즘

• 교착상태 회피를 위한 간단한 이론적 기법
• 시스템 내에 자원형이 한 가지만 존재하는 경우 시스템의 상태를 항상 안전상태로만 진행시킴

Habermann's 알고리즘

• 다익스트라 알고리즘의 확장 기법
• 여러 종류의 자원형이 존재함을 고려
• 시스템의 상태를 항상 안전 상태로만 진행시킴

교착 상태 검출 기법

• 시스템 운영 중 주기적으로 또는 필요한 경우에 교착 상태 확인
• 현재 시스템이 교착 상태인지의 여부
• 현재 시스템이 교착 상태라면 교착 상태의 프로세스 검출
• 자원 할당 그래프 사용

자원 할당 그래프

• Resource Allocation Graph
• 교착 상태 검출을 위해 사용
• 방향성 이분 그래프(Directed Bipartite Graph) 사용
• 속성: 방향성 그래프, G = (N, E)로 표현

N = {Nₚ, Nᵣ} where
    Nₚ is the set of processes = {P1, P2, ... , Pn} and
    Nᵣ is the set of resources = {R1, R2, ... , Rm}

• 모든 엣지들은 Nₚ와 Nᵣ 간에만 존재
  • 요구 엣지(request edge): Pi → Rj
  • 할당 엣지(allocation edge): Rj → Pi

Each edge e ∈ E is between Pi ∈ Nₚ
and Rj ∈ Nᵣ
    e = (Pi, Rj) : request edge
    e = (Rj, Pi) : allocation edge

• 자원 노드: 해당 자원의 type을 의미, Tₖ는 자원형 Rk에 대한 단위 자원의 수
• |(a, b)| : 임의의 노드 a로부터 다른 노드 b를 향한 엣지의 개수

그래프 단순화 기법

• Graph Reduction
• 주어진 그래프에 대해 엣지들을 제거함
• 완전 단순화 (Completely Reduced)
  • 주어진 그래프의 모든 엣지들이 제거되는 경우
  • 현재 교착 상태가 존재하지 않는다고 판단
• 단순화 불가능 (Irreducible)
  • 주어진 그래프의 모든 엣지들이 제거되지 않는 경우
  • 교착 상태가 존재하는 것으로 판단
• unblocked 프로세스
  • 현재 상태에서 요구한 자원들을 모두 할당받을 수 있는 프로세스
  • 시스템 내에 존재하는 unblocked 프로세스를 찾아 이에 인접한 엣지들을 제거

순서	특징
1	임의의 unblocked 프로세스 노드를 찾아 인접한 모든 엣지 제거
2	더 이상의 unblocked 프로세스들이 존재하지 않을 때까지 1의 과정을 반복
3	최종 형태에서 모든 엣지들이 제거되면 completely reduced
	남아 있는 엣지가 있다면 irreducible

교착 상태 검출 기법과 회피 기법의 차이

• 교착 상태 회피 기법: 최악의 경우를 고려함
• 교착 상태 검출 기법: 최선의 경우를 고려함
  • 현재 상태에 교착 상태에 놓인 프로세스가 있는지 검사
  • 미래 상태에는 관심/대응 없음

교착 상태 복구 기법

• 교착 상태 검출 기법에 의해 교착 상태의 프로세스를 검출한 후에 사용
• 시스템 내에 존재하는 교착 상태를 제거

프로세스 종료 기법

• Process Termination
• 교착 상태에 놓은 프로세스들 중 일부를 강제로 종료시킴
• 강제 종료된 프로세스들은 이후 재시작됨

자원 선점 기법

• Resource Preemption
• 교착 상태를 제거하기 위해 선점되어야 할 자원들을 결정
• 선점된 자원들을 할당받고 있는 프로세스들로부터 선점

---

기아 상태

• 작업이 결코 사용할 수 없는 자원을 계속 기다리는 결과(교착 상태)를 예방하려고 자원을 할당할 때 발생(기다림)

기아 상태의 원인

• 우선순위 기반 스케줄링: 높은 우선순위의 프로세스가 지속적으로 자원을 선점할 경우, 낮은 우선순위의 프로세스는 자원을 얻지 못하고 대기 상태에 빠질 수 있음
• 자원 할당 정책: 특정 자원 할당 정책이 일부 프로세스에 불리하게 작용하여 자원을 지속적으로 얻지 못하게 할 수 있음
• 새로운 프로세스의 연속적인 도착: 새로운 프로세스가 계속해서 도착하여 기존의 낮은 우선순위 프로세스가 실행될 기회를 얻지 못할 수 있음

기아 상태 해결 방안

• 철학자는 포크에 해당하는 세마포어에 대한 P(wait) 연산을 수행하고 나서 포크를 집음
• 즉, 포크는 해당 세마포어에 대한 V(signal) 연산을 수행하여 내려놓음