프로세스 관리

프로세스 개요

정의

일반적으로 프로세서에 의해 처리되는 사용자 프로그램, 실행중인 프로그램을 의미한다.

작업(Job), 태스트(Task)라고도 한다.

PCB

Process Control Block 프로세스 제어 블록으로 운영체제가 프로세스에 대한 중요한 정보를 저장해 놓는 곳.

저장 정보

프로세스의 현재 상태 

- 준비, 대기, 실행 등의 프로세스 상태

포인터

- 부모 프로세스에 대한 포인터

- 자식 프로세스에 대한 포인터

- 프로세스가 위치한 메모리에 대한 포인터

- 할당된 자원에 대한 포인터

프로세스 고유 식별자

- 프로세스를 구분할 수 있는 고유  번호

스케줄링 및 프로세스의 우선 순위

- 스케줄링 정보 및 프로세스가 실행될 우선순위

CPU 레지스터 정보

- Accumulator, Index Register, 범용 레지스터, PC 등에 대한 정보

주기억장치 관리 정보

- Base 레지스터, Page 테이블 정보

*베이스 레지스터 - 주기억장치가 분할된 영역으로 나뉘어 관리할 때, 프로그램이 한 영역에서 다른 영역으로 

옮겨지더라도 명령의 주소 부분을 바꾸지 않고 정상적으로 수행될 수 있도록 하기 위한 레지스터

프로세스 상태 전이

제출 - 작업 처리를 위해 사용자가 작업을 시스템에 제출한 상태

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

준비

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

- 프로세스는 준비상태 큐(스케줄링 큐)에서 실행을 준비하고 있다.

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

실행

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

- 프로세스 수행이 완료되기 전에 프로세스에게 주어진 프로세서 할당 시간이 

종료(Timer Run Out)되면 프로세스는 준비 상태로 전이된다.

- 실행중인 프로세스에 입출력 처리가 필요하면 실행중인 프로세스는 대기 상태로 전이된다.

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

대기, 보류, 블록(BLOCK) 

- 프로세스에 입출력 처리가 필요하면 현재 실행중인 프로세스가 중단하고 입출력 처리가 완료되 때까지 대기하고 있는 상태

완료 - 프로세서를 할당받아 주어진 시간안에 수행을 완료한 상태

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

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

웨이크업 - 입출력 작업이 완료되어 프로세스가 대기 상태에서 준비 상태로 전이되는 과정

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

스레드

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

단일 스레드 - 하나의 프로세스에 하나의 스레드

다중 스레드 - 하나 이상의 스레드가 존재

프로세스의 일부 특성을 갖고 있기 때문에 경량 프로세스라고도 한다.

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

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

분류

사용자 수준의 스레드 - 사용자가 만든 라이브러리를 사용하여 스레드를 운용, 속도는 빠르지만 구현이 어려움.

커널 수준 스레드 - 운영체제의 커널에 의해 스레드를 운용한다. 구현이 쉽지만 속도가 느리다.

스케줄링

프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업.

장기, 중기, 단기로 나뉜다.

장기 스케줄링 

- 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업을 한다.

- 작업 스케줄러에 의해 수행된다.

중기 스케줄링 

- 어떤 프로세스들이 CPU를 할당 받을 것인지 결정하는 작업

- CPU를 할당받으려는 프로세스가 많을 경우 프로세스를 일시 보류시킨 후 활성화해서 일시적으로 부하를 조절한다.

단기 스케줄링 

- 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미한다.

- 프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수행된다.

*문맥 교환(Context Switching)

하나의 프로세스에서 다른 프로세스로 CPU가 할당되는 과정에서 발생되는 것으로 새로운 프로세스에

CPU를 할당하기 위해 현재 CPU가 할당된 프로세스의 상태 정보를 저장하고,

새로운 프로세스의 상태 정보를 설정한 후 CPU를 할당하여 실행되도록 하는 작업을 의미한다.

스케줄링의 목적

공정성 - 모든 프로세스에 공정하게 할당한다.

처리율(량) 증가 - 단위 시간당 프로세스를 처리하는 비율(양)을 증가시킨다.

CPU 이용률 증가 - 프로세스 실행 과정에서 주기억장치를 액세스한다든지, 입출력 명령 실행 등의 원인에 의해

발생할 수 있는 CPU의 낭비 시간을 줄인고, CPU가 순수하게 프로세스를 실행하는 데 사용되는 시간 비율을 증가시킨다.

우선순위 제도 - 높은 우선순위의 프로세스를 먼저 실행

오버헤드 최소화

응답 시간 최소화 - 작업을 지시하고, 반응하기 시작하는 시간을 최소화한다.

반환 시간 최소화 - 프로세스를 제출한 시간부터 실행이 완료될 때까지 걸리는 시간을 최소화한다.

대기 시간 최소화 - 준비상태 큐에서 대기하는 시간을 최소화한다.

균형있는 자원의 사용 - 메모리, 입출력 장치 등의 자원을 균형 있게 사용한다.

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

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

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

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

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

- 중요한 짧은 작업이 중요하지 않은 긴 작업을 기다릴 수 있다.(단점)

- 종류로는 FCFS, SJF, 우선순위, HRN, 기한부 등의 알고리즘이 있다.

선점(Preemptive) 스케줄링

하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 

CPU를 갖에로 빼앗아 사용할 수 있는 스케줄링 기법.

- 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용된다.

- 많은 오버헤드를 초래한다.

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

- 종류로는 라운드로빈, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등의 알고리즘이 있다.

비선점 스케줄링

FCFS, SJF, 우선순위, HRN, 기한부

FCFS = FIFO

준비상태 큐(대기 큐, 준비 완료 리스트, 작업준비 큐, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 할당하는 기법.

ex)

P1 - 20초, P2 - 4초, P3 - 6초

평균 실행 시간 : (20+4+6)/3 = 10

평균 대기 시간 : (0+20+24)/3 = 14.6

평균 반환 시간 : (20+40+30)/3 = 24.6

SJF(Shortest Job Fisrt, 단기 작업 우선)

실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법

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

단점 - 실행 시간이 긴 프로세스가 무한 대기할 수 있다.

평균 실행 시간 : (4+6+20)/3 = 10

평균 대기 시간 : (0+4+10)/3 = 4.6

평균 반환 시간 : (4+10+30)/3 = 14.6

HRN(Hightest Response-ratio Next)

대기 시간과 서비스(실행) 시간을 이용하는 기법

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

ex)

위 예제에서 대기시간 P1 - 10초, P2 - 20초, P3 - 10초

우선 순위 계산 : P1 = 1.5, P2 - 6, P3 = 2.6

우선 순위 P2->P3->P1

기한부

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

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

우선순위

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

우선순위가 동일할 경우 FCFS기법으로 CPU를 할당한다.

우선순위는 프로세스의 종류나 특성에 따라 다르게 부여된다.

가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아 상태(Starvation)가 발생할 수 있다.

*에이징 기법 - 양보한 프로세스의 경우 우선 순위 단계를 한 단계씩 높여 무한 연기나 기아를 막는 기법.

선점 스케줄링

선점 우선순위

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

비선점 우선순위 기법을 선점 형태로 변경한 것.

SRT(Shortest Remaining Time)

현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여

가장 잛은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법이다. 시분할 시스템에 유용.

RR(Round Robin)

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

FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만

프로세스는 시간 할당량(Time Slice)동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고

준비상태 큐의 가장 뒤로 배치된다.

할당되는 시간이 클 경우 FCFS 기법과 같고, 할당되는 시간이 작을 경우 문맥 교환과 오버헤드가 자주 발생된다.

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

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

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

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

특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 있는 큐.

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

병행 프로세스와 상호 배제

병행 프로세스

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

임계 구역

Critical Section은 다중 프로그래밍 운영체제에서 어느 한 시점에서는 하나의 프로세스만 자원 

또는 데이터를 사용하도록 지정한 공유 자원(영역)을 의미한다.

- 하나의 프로세스만 접근할 수 있으며, 해당 프로세스가 자원을 반납하면 다른 프로세스가 자원이나 데이터를 사용할 수 있다.

상호 배제 기법

상호 배제(Mutual Exclusion)는 특정 프로세스가 공유 자원을 사용하고 있을 경우

다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법을 의미한다.

소프트웨어적 구현방법

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

여러 개의 프로세스 기준 : 빵집 알고리즘(Lamport)

*빵집 알고리즘 : 고객이 빵집에 들어갈 때 번호를 부여하여 순서대로 빵을 제공한는 것 처럼, 

각 프로세스에게 번호를 부여하여 자원을 사용하도록 하는 방법

하드웨어적 구현 방법

Test & Set 기법과 Swap 명령어 기법이 있다.

동기화 기법

두 개 이상의 프로세스를 한 시점에 동시에 처리할 수 없으므로 각 프로스세에 대한 처리 순서를 결정하는 것.

상호 배제의 한 형태이다.

세마포어

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

P 연산 : While S <= 0 Do Skip

자원을 사용하려는 프로세스들의 진입 여부를 자원의 개수(S)를 통해 결정하는 것으로 Wait 동작이라 한다.

S = S-1 

자원 점유를 알리는 것으로 자원의 개수를 감소시킨다.

V 연산 : S = S+1

대기중인 프로세스를 깨우는 신호(Wake up)로서, Signal 동작이라 한다.

S = S+1은 자원을 반납하였으므로 자원의 개수를 증가시킨다.

모니터

특수 프로그램 기법으로 특정 공유 자원을 프로세스에게 할당하는 데 

필요한 데이터와 이 데이터를 처리하는 프로시저로 구성된다.

교착 상태

상호 배제에 의해 나타는 문제점. 둘 이상의 프로세스들이 자원을 점유한 상태에서

서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미한다.

교착 상태 발생의 필충조건

상호 배제(Mutual Exclusion) - 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있다.

점유와 대기(Hold and Wait) - 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는

자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

비선점(Non-preemption) - 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.

환형 대기(Circular Wait) - 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.

교착상태 해결 기법

예방 기법(Prevention)

교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법.

네 가지 조건 중에서 어느 하나를 제거(부정)함으로써 수행된다. 자원 낭비가 가장 심한 기법이다.

회피 기법(Avoidance)

교착상태가 발생하면 적절히 피해가는 방법. 주로 은행원 알고리즘(Banker's 알고리즘)이 사용된다.

*은행원 알고리즘

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

- 교착상태가 발생할 수 있는 상태를 불완전 상태라고 한다.

- 자원의 양과 사룔자(프로세스) 수가 일정해야 한다.

- 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장한다.

프로세스가 자원을 요구할 때 시스템은 이 자원을 할당한 후에도 시스템을 안전 상태에 머무르게 하는가를

결정해야 하며 안전 상태에 있으면 자원을 할당하고, 그렇지 않으면 필요한 자원이 반납될 때까지 기다린다.

발견 기법(Detection)

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

- 교착 상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다.

회복 기법(Recovery)

교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 

선점하여 프로세스나 자원을 회복하는 것을 의미한다.

프로세스 종료 - 교착상태에 있는 프로세스를 종료하는 것

자원 선점 - 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당한다.