2장 프로세스 관리

정보처리기사 필기 - 3과목 운영체제

2장 프로세스 관리

084 프로세스의 개요

① 프로세스의 정의

· 프로세스(Process)는 일반적으로 프로세서(처리기, CPU)에 의해 처리되는 사용자 프로그램, 시스템 프로그램, 즉 실행중인 프로그램을 의미하며, 작업(Job), 테스크(Task)라고도 함

· 프로세스는 다음과 같이 여러 형태로 정의 가능

- PCB를 가진 프로그램

- 실기억장치에 저장된 프로그램

- 프로세서가 할당되는 실체로서, 디스패치가 가능한 단위

- 프로시저가 활동중인 것

- 비동기적 행위를 일으키는 주체

- 지정된 결과를 얻기 위한 일련의 계통적 동작

- 목적 또는 결과에 따라 발생되는 사건들의 과정

- 운영체제가 관리하는 실행 단위

② PCB

· PCB(Process Control Block, 프로세스 제어 블록)는 운영체제가 프로세스에 대한 중요한 정보를 저장해 놓는 곳으로, Task Control Block 또는 Job Control Block이라고도 함

· 각 프로세스가 생성될 때마다 고유의 PCB가 생성되고, 프로세스가 완료되면 PCB는 제거됨

· PCB에 저장되어 있는 정보

저장 정보	설명
프로세스의 현재 상태	준비, 대기, 실행 등의 프로세스 상태
포인터	· 부모 프로세스에 대한 포인터 : 부모 프로세스의 주소 기억  · 자식 프로세스에 대한 포인터 : 자식 프로세스의 주소 기억  · 프로세스가 위치한 메모리에 대한 포인터 : 현재 프로세스가 위치한 주소 기억  · 할당된 자원에 대한 포인터 : 프로세스에 할당된 각 자원에 대한 주소 기억
프로세스 고유 식별자	프로세스를 구분할 수 있는 고유 번호
스케줄링 및 프로세스의 우선순위	스케줄링 정보 및 프로세스가 실행될 우선순위
CPU 레지스터 정보	Accumulator, Index Register, 범용 레지스터, PC 등에 대한 정보
주기억장치 관리 정보	Base Register, Page Table에 대한 정보
입·출력 상태 정보	입·출력장치, 개방된 파일 목록
계정 정보	CPU 사용 시간, 실제 사용 시간, 한정된 시간

③ 프로세스 상태 전이

프로세스 상태 전이는 프로세스가 시스템 내에 존재하는 동안 프로세스의 상태가 변화는 것을 의미하며, 프로세스의 상태를 다음과 같이 상태 전이도로 표시

[그림 1] 상태 전이도

프로세스 상태

프로세스 상태는 제출, 접수, 준비, 실행, 대기(보류) 상태로 나눌 수 있으며, 이 중 주요 세 가지 상태는 준비, 실행, 대기 상태

· 제출(Submit) : 작업을 처리학 위해 사용자가 작업을 시스템에 제출한 상태

· 접수(Hold) : 제출된 작업이 스풀 공간인 디스크의 할당 위치에 저장된 상태

· 준비(Ready)

- 프로세스가 프로세서를 할당받기 위해 기다리고 있는 상태

- 프로세스는 준비상태 큐(스케줄링 큐)에서 실행 준비중(준비상태 큐 : 여러 프로세스가 프로세서를 할당받기 위해 기다리는 장소)

- 접수 상태에서 준비 상태로의 전이는 Job 스케줄러에 의해 수행됨

· 실행(Run)

- 준비상태 큐에 있는 프로세스가 프로세서를 할당 받아 실해오디는 상태

- 프로세스 수행이 완료되기 전에 프로세스에게 주어진 프로세서 할당 시간이 종료(Time Run Out)되면 프로세스는 준비 상태로 전이됨

- 실행중인 프로세스에 입·출력(I/O) 처리가 필요하면 실행중인 프로세스는 대기 상태로 전이됨

- 준비 상태에서 실행 상태로의 전이는 CPU(프로세서) 스케줄러에 의해 수행됨

· 대기(Wait), 보류, 블록(Block) : 프로세스에 입·출력 처리가 필요하면 현재 실행중인 프로세스가 중단되고, 입·출력 처리가 완료될 때까지 대기하고 있는 상태

· 종료(Terminated, Exit) : 프로세스의 실행이 끝나고 프로세스 할당이 해제된 상태

※ 실행 중지(Suspend)

· 하나의 프로세스가 입·출력 이외의 다른 이유에 의해 실행되지 못하는 상태

· 실행 중지된 프로세스는 다른 프로세스로 다시 시작하기 전까지는 실행될 수 없음

· 프로세스의 실행 중지 요인

- 시스템에 이상이 있거나 부하가 많을 경우 운영체제의 필요에 의해 중지시킴

- 프로세스의 이상 유무를 확인하기 위해 해당 프로세스를 완전히 종료시키지 않고 중지시킴

프로세스 상태 전이 관련 용어

· Dispatch : 준비 상태에서 대기하고 있는 프로세스 중 하나가 프로세서를 할당받아 실행 상태로 전이되는 과정

· Wake Up : 입·출력 작업이 완료되어 프로세스가 대기 상태에서 준비 상태로 전이되는 과정

· 교통량 제어기(Traffic Controller) : 프로세스의 상태에 대한 조사와 통보 담당

④ 스레드

스레드(Thread)는 프로세스 내에서의 작업 단위로서 시스템의 여러 자원을 할당받아 실행하는 프로그램의 단위

· 하나의 프로세스에 하나의 스레드가 존재하는 경우에는 단일 스레드, 하나 이상의 스레드가 존재하는 경우에는 다중 스레드라고 함

· 프로세스의 일부 특성을 갖고 있기 때문에 경량(Light Weight) 프로세스라고도 함

· 스레드 기반 시스템에서 스레드는 독립적인 스케줄링의 최소 단위로서 프로세스의 역할 담당

· 동일 프로세스 환경에서 서로 독립적인 다중 수행이 가능함

· 스레드의 분류

사용자 수준의 스레드	· 사용자가 만든 라이브러리를 사용하여 스레드 운용  · 속도는 빠르지만 구현 어려움
커널 수준의 스레드	· 운영체제의 커널에 의해 스레드 운용  · 구현이 쉽지만 속도 느림

· 스레드 사용의 장점

- 하나의 프로세스를 여러 개의 스레드로 생성하여 병행성을 증진시킬 수 있음

- 하드웨어, 운영체제의 성능과 응용 프로그램의 처리율 향상 가능

- 응용 프로그램의 응답 시간 단축 가능

- 실행 환경을 공유시켜 기억 장소의 낭비 줄어듦

- 프로세스들 간의 통신 향상

- 스레드는 공통적으로 접근 가능한 기억장치를 통해 효율적으로 통신함

085 스케줄링

① 스케줄링의 개요

· 스케줄링(Scheduling)은 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업

· 프로세스가 생성되어 완료될 때까지 프로셋는 여러 종류의 스케줄링 과정을 거치게 됨

· 스케줄링 종류

장기 스케줄링	· 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업  · 작업 스케줄링(Job Scheduling), 상위 스케줄링이라고도 하며, 작업 스케줄러에 의해 수행됨
중기 스케줄링	· 어떤 프로세스들이 CPU를 할당받을 것인지를 결정하는 작업을 의미함  · CPU를 할당받으려는 프로세스가 많을 경우 프로세스를 일시 보류시킨 후 활성화해서 일시적으로 부하를 조절함
단기 스케줄링	· 프로세스가 실행되기 위해 CPU를 할당받응 시기와 특정 프로세스를 지정하는 작업  · 프로세서 스케줄링(Processor Scheduling), 하위 스케줄링이락도 함  · 프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수행됨

※ 문맥 교환(Context Switching)

· 하나의 프로세스에서 다른 프로세스로 CPU가 할당되는 과정에서 발생되는 것으로 새로운 프로세스에 CPU를 할당하기 위해 현재 CPU가 할당된 프로세스의 상태 정보를 저장하고, 새로운 프로세스의 상태 정보를 설정한 후 CPU를 할당하여 실행되도록 하는 작업

② 스케줄링의 목적

스케줄링은 CPU나 자원을 효율적으로 사용하기 위한 정책

· 공정성 : 모든 프로세스에 공정하게 할당

· 처리율(량) 증가 : 단위 시간당 프로세스를 처리하는 비율(양)을 증가시킴

· CPU 이용률 증가 : 프로세스 실행 과정에서 주기억장치를 액세스한다든지, 입·출력 명령 실행 등의 원인에 의해 발생할 수 있는 CPU의 낭비 시간을 줄이고, CPU가 순수하게 프로세스를 실행하는데 사용되는 시간 비율을 증가시킴

· 우선순위 제도 : 우선순위가 높은 프로세스 먼저 실행

· 오버헤드 최소화 : 오버헤드 최소화

· 응답시간(Response Time, 반응 시간) 최소화 : 작업을 지시하고, 반응하기 시작하는 시간을 최소화

· 반환시간(Turn Around Time) 최소화 : 프로세스를 제출한 시간부터 실행이 완료될 때까지 걸리는 시간을 최소화

· 대기 시간 최소화 : 프로세스가 준비상태 큐에서 대기하는 시간을 최소화

· 균형 있는 자원의 사용 : 메모리, 입·출력장치 등의 자원을 균형 있게 사용

· 무한 연기 회피 : 자원을 사용하기 위해 무한정 연기되는 상태를 회피

③ 프로세서 스케줄링(프로세스 스케줄링) 기법

비선점(Non-Preemptive) 스케줄링

· 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법

· 프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용함

· 모든 프로세스에 대한 요구를 공정하게 처리 가능

· 프로세스 응답 시간의 예측이 용이하며, 일괄 처리 방식에 적합

· 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우가 발생할 수 있음

· 비선점 스케줄링의 종류에는 FCFS, SJF, 우선순위, HRN, 기한부 등의 알고리즘

선점(Preemptive) 스케줄링

· 하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

· 우선순위가 높은 프로세스를 빠르게 처리 가능

· 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용됨

· 많은 오버헤드(Overhead) 초래함

· 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록(Clock)이 필요

· 선점 스케줄링의 종류에는 Round Robin, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등의 알고리즘

비선점 스케줄링	FCFS	SJF	우선순위	HRN	기한부
선점 스케줄링	RR	SRT	선점 우선순위	다단계 큐	다단계 피드백 큐

086 비선점 스케줄링

① 비선점 스케줄링의 개요

· FCFS, SJF, HRN, 우선순위, 기반후 알고리즘· 

② FCFS(First Come First Service, 선입 선출) = FIFO(First In First Out)

· FCFS는 준비상태 큐(대기 큐, 준비 완료 리스트, 작업준비 큐, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 할당하는 기법으로, 가장 간단한 알고리즘

· 먼저 도착한 것이 먼저 처리되어 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 됨

③ SJF(Shorted Job First, 단기 작업 우선)

· SJF는 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법

· 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘

· 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 무한 연기 상태가 발생될 수 있음

④ HRN(Highest Response-ratio Next)

· 실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행) 시간을 이용하는 기법

· 우선순위 계산 공식을 이용하여 서비스(실행) 시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선순위를 주어 CPU를 할당함

· 서비스 실행 시간이 짧거나 대기 시간이긴 프로세스 일 경우 우선순위가 높아짐

· 우선순위를 계산하여 그 숫자가 가장 높은 것부터 낮은 순으로 우선순위 부여됨

· 우선순위 계산식 = (대기 시간+서비스(실행) 시간) / 서비스(실행) 시간

⑤ 기한부(Deadline)

· 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법

· 프로세스가 제한된 시간 안에 완료되지 않을 경우 제거되거나 처음부터 다시 실행해야 함

· 시스템을 프로세스에게 할당할 정확한 시간을 추정해야 하며, 이를 위해서 사용자는 시스템이 요구한 프로세스에 대해 정확한 정보를 제공해야 함

· 여러 프로세스들이 동시에 실행되면 스케줄링이 복잡해지며, 프로세스 실행 시 집중적으로 요구되는 자원 관리에 오버헤드 발생

⑥ 우선순위(Priority)

· 준비 상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

· 우선순위가 동일할 경우 FCFS 기법으로 CPU 할당

· 우선순위는 프로세스의 종류나 특성에 따라 다르게 부여될 수 있음

· 가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아 상태(프로세스를 완료하지 못하는 상태)가 발생할 수 있음

※ 에이징(Aging) 기법

· 시스템에서 특정 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우, 한 번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당받도록 하는 기법

· SJF나 우선순위 기법에서 발생할 수 있는 무한 연기 상태, 기아 상태 예방 가능

087 선점 스케줄링

선점 스케줄링 : 선점 우선순위, SRT, RR, 다단계 큐, 다단계 피드백 큐 알고리즘

① 선점 우선순위

· 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU 할당하는 기법

· 비선점 우선순위 기법을 선점 형태로 변경한 것으로, 준비상태 큐에 새로 들어온 프로세스의 순위가 높을 경우 현재의 프로세스를 보류하고 새로운 프로세스 실행

② SRT(Shortest Remaining Time)

· 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법으로, 선점 SJF 기법이라고도 함

· 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법으로, 시분할 시스템에 유용

· 준비상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드 증가

③ RR(Round Robin)

· 시분할 시스템(Time Sharing System)을 위해 고안된 방식으로, FCFS(FIFO)알고리즘을 선점 형태로 변형한 기법

· FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 시간 할당량(Time Slice, Quantum) 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비 상태 큐의 가장 뒤로 배치됨

· 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생되더 요청된 작업을 신속히 처리할 수 없음

· 할당되는 시간의 크기가 작으면 작은 프로세스들에게 유리함

④ 다단계 큐(MQ; Multi-level Queue)

· 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법

· 일반적으로 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로세스 등으로 나누어 준비상태 큐를 상위, 중위, 하위 단계로 배치

· 각 준비상태 큐는 독자적인 스케줄링을 가지고 있으므로 각 그룹의 특성에 따라 서로 다른 스케줄링 기법 사용 가능

· 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비 상태 큐로 이동 가능

· 하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당해야 함

⑤ 다단계 피드백 큐(MFQ; Multi-level Feedback Queue)

· 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법 

· 적응 기법(Adaptive Mechanism, 시스템이 유동적인 상태 변화에 적절히 반응하도록 하는 기법)의 개념 적용

· 각 준비상태 큐마다 시간 할당량을 부여하여 그 시간동안 완료하지 못한 프로세스는 다음 단계의 준비상태 큐로 이동됨

· 상위 단계 준비상태 큐일수록 우선순위가 높고, 시간 할당량이 적음

· 요구하는 시간이 적은 프로세스, 입·출력 중심의 프로세스, 낮은 우선순위에서 너무 오래 기다린 프로세스를 기준으로 높은 우선순위를 할당함

· 하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비 상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당하며, 마지막 단계 큐에서는 작업이 완료될 때까지 RR 스케줄링 기법을 사용함

088 병행 프로세스와 상호 배제

① 병행 프로세스

병행 프로세스(Concurrent Process)는 두 개 이상의 프로세스들이 동시에 존재하며 실행 상태에 있는 것을 의미

· 여러 프로세스들이 독립적으로 실행되는 것을 독립적 병행 프로세스, 서로 협력하며 동시에 실행되는 것을 협동적 병행 프로세스라고 함

· 병행 프로세스는 다중 처리 시스템이나 분산 처리 시스템에서 중요한 개념으로 사용됨

② 임계 구역

임계 구역(Critical Section)은 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서는 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유 자원(영역)을 의미

· 임계 구역에는 하나의 프로세스만 접근 가능하며, 해당 프로세스가 자원을 반납한 후에만 다른 프로세스가 자원이나 데이터 사용 가능

· 임계 구역은 특정 프로세스가 독점할 수 없으며, 임계 영역에서 수행 중인 프로세스는 인터럽트 불가능

· 임계 구역의 자원이나 데이터는 여러 프로세스가 사용해야 하므로 임계 구역 내에서의 작업은 신속하게 이루어져야 함

· 프로세스가 임계 구역에 대한 진입을 요청하면 일정 시간 내에 진입을 허락해야 함

· 현재 임계 구역에서 실행되는 프로세스가 없다면 임계 구역 사용을 기다리고 있는 잔류 영역에 있는 프로세스의 사용을 허락해야 하며, 그 이외에 있는 프로세스는 임계 구역에 진입 불가능

③ 상호 배제 기법

상호 배제(Mutual Exclusion)는 특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법

· 여러 프로세스가 동시에 공우 자원을 사용할 때 각 프로세스가 번갈아가며 공유 자원를 사용하는 것으로, 임계 구역을 유지하는 기법

· 상호 배제 기법을 구현하기 위한 방법에는 소프트웨어적 구현과 하드웨어적 구현이 있음

소프트웨어적 구현 방법

· 두 개의 프로세스 기준 : 데커(Dekker) 알고리즘, 피터슨(Peterson) 알고리즘

· 여러 개의 프로세스 기준 : Lamport의 빵집 알고리즘(고객이 빵집에 들어갈 때 번호를 부여하여 순서대로 빵을 제공하는 것 처럼, 각 프로세스에게 번호를 부여하고 자원을 사용하도록 하는 방법)

하드웨어적 구현 방법

· Test & Set 기법과 Swap 명령어 기법

④ 동기화 기법의 개요

동기화 기법(Synchronization)은 두 개의 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 각 프로세스에 대한 처리 순서를 결정하는 것으로, 상호 배제의 한 형태

· 동기화르 구현할 수 있는 방법에는 세마포어와 모니터가 있음

⑤ 세마포어(Semaphore)

· 세마포어는 '신호기', '깃발'을 뜻하며, 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 기법

· 세마포어는 다익스트라가 제안했으며, P와 V라는 두 개의 연산에 의해서 동기화를 유지시키고 상호 배제의 원리를 보장함

· S는 P와 V연산으로만 접근 가능한 세마포어 변수로, 공유 자원의 개수를 나타내며 0과 1 혹은 0과 양의 값을 가질 수 있음

[그림 2] 세마포어

① 프로세스가 자원을 사용하려고 할 경우 먼저 세마포어 변수(S)를 통해 다른 프로세스가 자원을 점유하고 있는지 조사 → 자원을 사용할 수 있으면 해당 자원을 점유한 후 자원이 점유되었다는 것을 알리고, 다른 프로세스가 이미 자원을 점유한 상태라면 자원을 사용할 수 있을 때까지 기다림

· P연산 : 자원을 사용하려는 프로세스들의 진입 여부를 자원의 개수(S)를 통해 결정하는 것으로, Wait 동작이라 함

· S = S - 1 : 자원 점유를 알리는 것으로, 자원의 개수를 감소시킴

② 프로세스가 자원 사용을 마치면 자원을 반납하므로 자원의 사용을 위해 기다리는 프로세스에게 이 사실을 알림

· V연산 : 대기중인 프로세스를 깨우는 신호(Wake Up)로서, Signal 동작이라 함

· S = S + 1 : 자원을 반납하였으므로 자원의 개수 증가시킴

- 하나의 프로세스가 S값을 변경하면 동시에 다른 프로세스가 S값을 변경할 수 없음

- 세마포어에 대한 연산은 처리중에 인터럽트되어서는 안 됨

⑥ 모니터(Monitor)

· 모니터는 동기화를 구현하기 위한 특수 프로그램 기법으로 특정 공유 자원을 프로세스에게 할당하는 데 필요한 데이터와 이 데이터를 처리하는 프로시저로 구성됨

· 자료 추상화와 정보 은폐 개념을 기초로 하여 공유 자원을 할당하기 위한 병행성 구조로 이루어져 있음

· 모니터 내의 공유 자원을 사용하려면 프로세스는 반드시 모니터의 진입부를 호출해야 함

· 외부의 프로시저는 직접 액세스할 수 없음

· 모니터의 경계에서 상호 배제가 시행됨

· 모니터에는 한 순간에 하나의 프로세스만 진입하여 자원 사용 가능

· 모니터에는 Wait와 Signal 연산이 사용됨

089 교착상태

① 교착상태의 개요

· 교착상태(Dead Lock)는 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

② 교착상태 발생의 필요 충분 조건

교착상태가 발생하려면 네 가지 조건이 충족되어야함. 단 하나라도 충족하지 않으면 교착상태 발생하지 않음

상호 배제(Mutual Exclusion)	한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 함
점유와 대기(Hold and Wait)	최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함
비선점(Non-preemption)	다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 함
환형 대기(Circular Wait)	공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 함

③ 예방 기법(Prevention)

교착상태 예방 기법은 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로, 교착상태 발생의 네 가지 조건 중에서 어느 하나를 제거(부정)함으로써 수행됨. 자원의 낭비가 가장 심한 기법

· 상호 배제(Mutual Exclusion) 부정 : 한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 함

· 점유및 대기(Hold and Wait) 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 함

· 비선점(Non-preemption) 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사요하기 위해 기다리게 함

· 환형 대기(Circular Wait) 부정 : 자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 하는 것

④ 회피 기법(Avoidance)

교착상태 회피 기법은 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법으로, 주로 은행원 알고리즘이 사용됨

은행원 알고리즘(Banker's Algorithm)

· 은행원 알고리즘은 E. J. Dijikstra가 제안한 것으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법

· 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전 상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 함

· 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(소프트웨어) 수가 일정해야 함

· 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장함

※ 은행원 알고리즘 순서와 예시

① 새로운 프로세스가 시스템에 들어가면 프로세스가 필요로 하는 자원의 최대 수를 정의. 이때 프로세스가 필요로 하는 자원의 수는 시스템에 존재하는 최대 자원 수를 초과할 수 없음

② 프로세스가 자원을 요구할 때 시스템은 이 자원을 할당한 후에도 시스템을 안전 상태에 머무르게 하는가를 결정해야 하며 안전 상태에 있으면 자원을 할당하고, 그렇지 않으면 필요한 자원이 반납될 때가지 기다림

⑤ 발견 기법(Detection)

교착상태 발견 기법은 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미

· 교착상태 발견 알고리즘과 자원 할당 그래프 등 사용 

⑥ 회복 기법(Recovery)

교착상태 회복 기법은 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것

프로세스 종료	교착상태에 있는 프로세스를 종료하는 것으로, 교착상태에 있는 모든 프로세스를 종료하는 방법과 교착상태에 있는 프로세스들을 하나씩 종료해 가며 교착상태를 해결하는 방법이 있음
자원 선점	· 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지 시키는 방법  · 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점함

출처 : 2017 시나공 정보처리기사 필기