Process State & Scheduling

프로세스는 어떠한 상태(state)를 가집니다.

---

Process State

멀티 태스킹 컴퓨터 시스템에서 프로세스는 다양한 상태를 차지할 수 있다.

각각의 상태는 OS 커널에서 인식되는 상태는 아닐 수 있으나, 프로세스를 이해하기 위한 추상적 개념이다.

 

 

Process & Thread (OS)

지난번 포스팅에서 단일 프로세스와 멀티 프로세스 환경에 대해 말씀드렸습니다.

그 중 프로세스 상태에 대한 이야기도 살짝 했었는데요.

이번엔 프로세스 상태와 멀티 프로세스 환경에서 각 프로세스가 어떤 순서로 동작되는지 알아보겠습니다.

지난 글의 Context switching에서 언급한 내용에 대한 추가 설명이라 생각하시면 되겠습니다.

 

프로세스 상태는 대표적으로 5가지가 있습니다.

1. New (Created): 프로세스를 생성 중인 상태 (Secondary memory에 존재)
2. Ready: 프로세스가 CPU에 할당되기 위한 준비가 완료된 상태
3. Running: 프로세스가 CPU에 할당되어 실행 중인 상태
4. Wait (asleep): block 되어 I/O나 event를 기다리는 상태
5. Terminate: 프로세스가 종료된 상태 (해당 프로세스의 PCB도 제거됨)

각 상태는 간단히 말하면 단어 그대로의 의미를 갖습니다.

생성, 실행전 준비, 실행, 대기, 종료

 

그리고 Ready 상태에서 Running으로 넘어가는 시점에 어떤 프로세스를 먼저 CPU에 할당할 건지 결정합니다.

앞선 포스트에서 말씀드렸지만, 자원은 한 번에 하나의 프로세스만 점유 가능하기 때문에 할당할 프로세스를 결정해야 합니다.

즉, 이때 Scheduling이 작동합니다.

 

각 상태와 어떻게 전이되는지 자세히 알아보기 그림을 통해 보겠습니다.

그림 1. 프로세스 상태

화살표가 의미하는 것은 프로세스의 상태가 전이될 수 있는 흐름입니다.

Terminated 상태는.. 어디에 속하는 게 맞을지 ㅠ, 또한 New는 지연상태에 포함되는 것은 아닙니다.

이 상태 전이도 6가지로 표현할 수 있습니다.

 

Dispatch (Schedule)

Scheduling을 통해 Ready queue의 맨 앞에 있던 프로세스가 CPU를 점유하는 상태

New에서 생성된 프로세스는 Ready queue에 저장되어 실행 대기합니다.

Dispatch: Ready -> Running

 

Timeout (Preemption)

OS에서 지정한 시간이 지난 경우 발생

OS는 하나의 프로세스가 자원을 독점하는 것을 방지하기 위해 각 프로세스별 실행 시간을 정합니다.

이를 Clock interrput를 설정한다 표현합니다.

Timeout: Running -> Ready

 

Block (Sleep)

실행 상태의 프로세스가 Timeout 발생 전 입출력 event가 발생한 경우

즉, Timeout과의 차이점을 제대로 이해하셔야 합니다.

이후 I/O가 종료되면 Wake up을 통해 Running이 아닌 Ready 상태로 다시 돌아갑니다.

Block: Running -> Wait

 

이때, 프로세스가 CPU를 점유하는 것은 Running 상태입니다.

즉, Running 상태인 프로세스는 단 하나만 존재하는데요. 하지만, Ready 또는 Wait 상태의 프로세스는 많겠죠.

이 상태에선 아래와 같은 프로세스들이 존재할 수 있습니다.

• Ready 상태에서 우선순위가 계속 밀려 Running을 하지 못하는 프로세스
• I/O 작업을 진행 중인 다수의 프로세스

전자의 경우 실행되지도 못한 채 Ready 상태에서 대기 중입니다.

후자의 경우 I/O  작업을 진행 중이나,제대로 진행되지 않는 경우입니다.

처리할 작업이 너무 많거나 프로세스 내부적으로 어떤 문제가 발생했기 때문에 진행되지 못하는 게 아닐까 싶네요.

자세한 내용은 아래에 다시 기술하겠습니다.

중요한 것은 두 경우 모두 의미 없이 메모리를 차지하고 있다는 점이죠.

이 문제점을 해결하기 위해 Vitrual memory를 지원하는 시스템에선 스와핑을 통해 프로세스를 외부 스토리지에 배치합니다.

이러한 상태는 Suspended로 불립니다.

 

 

Swap - out/Swap - in

메모리 효율을 높이기 위한 비효율적인 프로세스를 외부 저장소로 Swapping 하는 경우

다시 메모리로 적재하는 경우는 Swap in

Wait 상태에서 발생하는 경우 Suspended Wait, Ready 상태에서 발생하는 경우 Suspended Ready입니다.

Swap - out: Ready -> Suspended Ready, Wait -> Suspended Wait

Swap - in: Suspended Ready -> Ready, Suspended Wait -> Wait

 

Wake up

입출력 작업 종료 등 기다리던 event가 완료됐을 때

또는, Suspended Wait 상태에서 I/O가 완료된 경우 Suspended Ready로 이동할 때

Wake up: Wait -> Ready, Suspended Wait -> Suspended Ready

 

마지막으로 New -> Suspended Ready 형태의 상태 전이도 발생합니다.

이 또한 다양한 문제가 있겠으나 Ready queue가 넘치는(?) 등의 메모리 부족 현상에 의해 발생할 수 있겠죠.

 

스케줄링으로 넘어가기 전에Suspended 상태가 왜 발생하는지 정리하고 넘어가겠습니다.

측면	원인	설명
시스템 성능	CPU 스케줄링	스케줄링에 따른 타 프로세스 할당
	성능 회복 목적	큰 작업이나 작업량이 많은 경우
시스템 용량	자원 절감	시스템 부하 시 리소스 절감
	메모리 확보	커널에 의한 메모리 회수
	대기 지연	I/O, 인터럽트 발생 후 대기 시간 증가
시스템 안정성	프로세스 의심	프로세스의 특정 부분 모니터링을 위해
	시스템 장애	시스템 장애 발생 시 처리

 

 

---

Scheduling

스케줄러는 시스템에 허용할 다음 작업과 실행할 다음 프로세스를 선택하는 운영 체제 모듈입니다.

그중 프로세스 스케줄러는 특정 시점에 실행되는 프로세스(CPU를 점유할 프로세스)를 결정합니다.

이렇게 프로세스를 선택하는 행위를 프로세스 스케줄링이라 부릅니다.

 

Scheduling 성능 평가 요소

• CPU 이용률
• 처리율
• 반환 시간
• 대기 시간
• 반응 시간 (응답 시간)

 

Process Scheduler는 특징에 따라 3가지 종류가 존재합니다.

Long-term Scheduler (Job scheduler)

디스크에서 어떤 프로그램을 가져와 커널에 등록할지(Ready queue에 담을지) 즉, 프로세스로 만들지 결정하는 스케줄러입니다.

메모리에 동시에 올라가 있는 프로세스의 수를 조절하는 역할 또한 합니다.

즉, New -> Ready 상태로 전이되는 과정에서 작동합니다.

 

Short-term Scheduler (CPU scheduler)

일반적으로 스케줄러는 단기 스케줄러를 의미하며, 준비 상태의 프로세스 중 어떤 프로세스를 다음에 실행할지 결정합니다.

스케줄링 알고리즘에 따라 다음 프로세스를 결정합니다.

즉, Dispatch 상태 전이 과정에서 작동합니다.

 

Dispatcher

단기 스케줄러가 선택한 프로세스에 CPU를 할당받고 작업을 수행할 수 있도록 환경을 설정하는 커널 모듈입니다.

한 프로세스를 중지하고 다른 프로세스를 시작하는 데 걸리는 시간: Dispatch 지연 시간.

 

Dispatcher의 역할은 다음과 같습니다.

• Context Switching (문맥 교환)
• 사용자 모드로 전환
• New 상태로 표시된 사용자 프로그램의 적절한 위치로 이동해 재시작

또한, 아래의 조건을 만족해야 합니다.

• 모든 프로세스 스위치에서 호출되므로 가능한 한 빨라야 함.
• 문맥 교환 중에는 CPU가 거의 유휴 상태로 유지되므로 불필요한 문맥 교환은 지양.

 

medium-term Scheduler (Job scheduler)

너무 많은 프로세스에 메모리를 할당해 시스템의 성능이 저하되는 경우, 프로세스의 수를 조절하기 위한 스케줄러입니다.

메모리 부족으로 성능 저하가 발생할 경우 강제로 프로세스로부터 메모리를 빼앗는 역할을 합니다.

이러한 행위를 위에서 봤던 Swap이라 부르죠.

타깃은당장 CPU 획득 가능성이 낮은 Wait 상태의 프로세스부터 Swap을 통해 디스크 영역에 저장합니다.

즉, Swap-in/out 상태 전이에서 작동합니다.

 

 

마지막으로 스케줄링 알고리즘에 대해 살펴보겠습니다.

 

 

---

Scheduling Algorithm

단기 스케줄러에서 사용되는 알고리즘으로 선점형과 비선점형으로 나뉩니다.

Ready -> Running (Dispatch)

 

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

• 어떤 프로세스가 CPU를 할당받으면자발적으로 중지(Terminate or I/O 요청)될 때까지 실행되는 것을 보장.
• 순서대로 처리
• 다음에 처리해야 할 프로세스와 관계없이 응답 시간 예상 가능.
• 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드가 적음.
• 일괄 처리 시스템에 적합.
• CPU 사용 시간이 긴 하나의 프로세스가 짧은 여러 프로세스를 오랫동안 대기시킬 수 있음, 처리율 나쁨.

 

선점형 스케줄링(Preemptive Scheduling)

• 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 기존 프로세스를 멈추고 CPU를 강제로 점유.
• 모든 프로세스에 CPU 사용 시간을 동일하게 부여 가능.
• 빠른 응답 시간을 요하는 대화식 시분할 시스템에 적합.
• 긴급한 프로세서를 제어 가능.
• 운영 체제가 프로세서 자원을 선점하고 있다가 각 프로세스의 요청이 있을 때 우선순위에 따라 자원을 배분.

 

이제부터 선점/비선점 스케줄링 알고리즘의 종류별 특징과 동작 방식을 알아보겠습니다.

아래는 대기 시간과 프로세스가 도착 및 실행 후 반환 시간 공식을 나타냅니다.

그림 2. 대기시간 계산식

그림 3. 반환시간 계산식

 

 

비선점형

 

FCFS (First Come First Served)

Ready Queue에 들어온 순서대로 작업 처리

 

장점

• 구현이 쉬움
• Starvation 없음
• 프로세서가 지속적으로 프로세스를 처리하므로 처리율이 높음

단점

• 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 수행될 수 있음
• 프로세스들의 도착 순서에 따라 평균 반환시간이 크게 변함

 

프로세스	도착 시간	실행 시간	처리 순서	대기 시간	반환 시간
p1	0	10	1	0	10
p2	1	15	2	10 - 1 = 9	24
p3	2	42	3	(10 + 15) - 2 = 23	65
p4	3	8	4	(10 + 15 + 42) - 3 = 64	72
p5	4	14	5	(10 + 15 + 42 + 8) - 4 = 71	85

평균 대기 시간 = (0 + 9 + 23 + 64 + 71) / 5 = 167 / 5 = 33.4

평균 반환 시간 = (10 + 24 + 65 + 72 + 85) / 5 = 256 / 5 = 51.2

 

SJF (Shortest Job First)

Ready Queue에 존재하는 프로세스 중 실행시간이 가장 짧은 프로세스부터 자원을 할당

 

장점

• 항상 실행 시간이 가장 짧은 작업부터 처리, 평균 대기시간이 가장 짧음

단점

• Starvation 발생, 실행시간의 크기가 내림차순으로 들어오는 경우
• 실행 시간 예측 어려움

 

프로세스	도착 시간	실행 시간	처리 순서	대기 시간	반환 시간
p1	0	10	1	0	10
p2	1	15	4	32 - 1 = 31	46
p3	2	42	5	47 - 2 = 45	87
p4	3	8	2	10 - 3 = 7	15
p5	4	14	3	18 - 4 = 14	28

평균 대기 시간 = (0 + 31 + 45 + 7 + 14) / 5 = 97 / 5 = 19.4

평균 반환 시간 = (10 + 46 + 87 + 15 + 28) / 5 = 186 / 5 = 37.2

 

HRN (Highest Response-Ratio Next)

Ready Queue에 존재하는 프로세스 중 응답 비율이 가장 큰 프로세스부터 자원을 할당

 

응답 비율 = (대기시간 + 실행시간) / 실행시간

실행시간이 낮을수록 높은 우선순위 부여

 

장점

• SJF의 단점을 보완, 효율적인 자원 사용
• Starvation 없음, aging을 통한 해결

단점

• 잦은 Context Switching으로 인한 overhead
• 위의 비선점과 마찬가지로 공정한 배분을 하는 알고리즘은 아님

 

시간대 별 ratio

프로세스	1차	2차	3차	4차	5차
p1	완료	완료	완료	완료	완료
p2	X	(9 + 15) / 15 = 1.6	(17 + 15) / 15 = 2.1333	완료	완료
p3	X	(8 + 42) / 42 = 1.1904	(16 + 42) / 42 = 1.3809	(31 + 42) / 42 = 1.738	(45 + 42) / 42 = 2.3095
p4	X	(7 + 8) / 8 = 1.875	완료	완료	완료
p5	X	(6 + 14 ) / 14 = 1.4285	(14 + 14) / 14 = 2	(29 + 14) / 14 = 3.0714	완료
CPU 점유	p1	p4	p2	p5	p3

p1이 도착한 경우 다른 프로세스가 없어 바로 진행되지만, p1 완료 후엔 모든 프로세스가 도착한 이후입니다.

 

프로세스	도착 시간	실행 시간	처리 순서	대기 시간	반환 시간
p1	0	10	1	0	10
p2	1	15	3	18 - 1 = 17	32
p3	2	42	5	47 - 2 = 45	87
p4	3	8	2	10 - 3 = 7	15
p5	4	14	4	33 - 4 = 29	43

평균 대기 시간 = (0 + 17 + 45 + 7 + 29) / 5 = 98 / 5 = 19.6

평균 반환 시간 = (10 + 32 + 87 + 15 + 43) / 5 = 187 / 5 = 37.4

 

 

선점형

 

RR (Round-Robin)

프로세스가 CPU에서 동작할 수 있는 시간을 할당 (time slicing)

원형 큐 구조, 프로세스가 할당 시간을 다 소모한 경우 가장 뒤로 배치 (OS에 의한 interrupt)

FCFS에 선점을 적용, Gantt 차트로 표현.

 

장점

• Starvation 없음, CPU 독점 없이 공평한 시간 이용
• 프로세스 최악 응답 시간을 알기 수월
• 대화형 시스템에 유용

단점

• 시간 할당 단위가 너무 큰 경우 FCFS와 동일하게 동작
• 시간 할당 단위가 너무 작은 경우 잦은 Context Switching으로 인한 overhead

 

Time slice 단위: 5

각 Context Switching은 preemption을 통해 이루어집니다.

그림 4. R - R Gantt chart

프로세스	도착 시간	실행 시간	처리 순서	대기 시간	반환 시간
p1	0	10	1	20	30
p2	1	15	3	38 - 1 = 37	53
p3	2	42	5	47 - 2 = 45	89
p4	3	8	2	35 - 3 = 32	48
p5	4	14	4	47 - 4 = 43	62

평균 대기 시간 = (20 + 37 + 45 + 32 + 43) / 5 = 177 / 5 = 35.4

평균 반환 시간 = (30 + 53 + 89 + 48 + 62) / 5 = 282 / 5 = 56.4

 

SRTF (Shortest Remaining-Time First)

Ready Queue에 존재하는 프로세스 중 실행시간이 가장 짧은 프로세스부터 자원을 할당

현재 실행 시간이 가장 짧은 프로세스에 선점을 통해 자원을 할당

SJF는 진행 중인 프로세스를 완료 후 다음 프로세스를 결정한다면, SRTF는 더 짧은 작업이 들어오는 즉시 switching

즉, SJF 방식에서 선점 정책을 도입

 

장점

• 최적의 평균 대기시간

단점

• Starvation 발생
• 잦은 Context Switching으로 인한 overhead

 

이해를 돕기 위해 p2와 p4의 실행시간을 바꿔 진행합니다.

초기 p1 -> p2에서 preemption 정책이 적용됐습니다.

그림 5. SRTF Gantt chart

프로세스	도착 시간	실행 시간	처리 순서	대기 시간	반환 시간
p1	0	10	2	8	18
p2	1	8	1	1 - 1 = 0	8
p3	2	42	5	47 - 2 = 45	87
p4	3	15	4	32 - 3 = 29	44
p5	4	14	3	18 - 4 = 14	28

평균 대기 시간 = (8 + 0 + 45 + 29 + 14) / 5 = 96 / 5 = 19.2

평균 반환 시간 = (18 + 8 + 87 + 44 + 28) / 5 = 185 / 5 = 37

 

다단계 큐 (Multilevel Queue)

프로세스의 우선순위에 따라 Ready Queue를 다르게 배정

서로 다른 우선순위를 가지는 프로세스들을 구분 및 관리, 각 Queue 사이에도 우선순위가 존재

상위 단계 Queue에 프로세스가 도착하면, 실행 여부를 떠나 하위 단계는 CPU를 뺏김. preemptive

 

장점

• 각 Queue 마다 서로 다른 알고리즘 적용 가능, 스케줄링 overhead 낮음

단점

• 우선순위가 고정적임, 유연적이지 못함 -> 정적(절대적) 우선순위
• 프로세스는 Queue 간 이동 불가
• Starvation 발생

 

그림 6. Multilevel Queue 예시

 

다단계 피드백 큐 (Multilevel Feedback Queue)

동적 우선순위를 기반으로 하는 선점 방식으로 운영

여러 단계의 Queue 존재

프로세스가 많은 CPU 시간을 사용하는 경우 우선순위가 낮은 Queue로 이동

낮은 우선순위 대기열에서 오래 대기하는 프로세스는 높은 우선순위 Queue로 이동

각 Queue 마다 서로 다른 CPU 시간 할당량(Time quantum)을 가짐

우선순위가 낮은 Queue일수록 더 큰 Time quantum.

 

장점

• Aging을 통한 Starvation 해결
• 동적 우선순위

단점

• 스케줄링 overhead가 높음

 

우선순위 하향: CPU를 점유했으나 해당 Queue의 시간 할당량 내에 완료되지 못한 프로세스

우선순위 상향: CPU를 특정 시간 S 동안 점유하지 못한 프로세스

그림 7. Multilevel Feedback Queue

t2의 할당량을 가진 Queue가 진행 중 t1 Queue로 프로세스가 들어온 경우

-> t2를 멈추고 t1부터 실행 preemptive

 

RM (Rate Monotonic)

작업의 크기와 개수가 알려진 프로세스들이 주기적으로 실행되는 환경에서 사용

수행 주기가 가장 짧은 프로세스에 가장 높은 우선순위 부여

우선순위 변동이 없는 정적 스케줄링

 

EDF (Earliest Deadline First)

스케줄링 이벤트가 일어날 때마다, 큐에서 마감시간이 가장 가까운 프로세스를 탐색하여 다음에 수행

주기적인 작업, 단일 처리기 환경에서 선점형 프로세스 스케줄링 가능

작업(task) N개: O(N^2), 수학적으로 최적

 

 

 

여기까지 프로세스의 상태와 스케줄링 알고리즘에 대해 알아봤습니다.

Time slice/Time quantum은 스케줄링 알고리즘에서 같은 의미로 쓰이니 혼란 없으시길 바랍니다.

다른 것들처럼 표를 그리며 예시를 들진 않았으나 MQ, MFQ의 동작 방식 또한 잘 알고 가셔야 합니다.

표를 통해 표현하기엔 너무 길어질 것 같아 skip 했습니다

또한, RM, EDF는 주기적인 프로세스를 예시로 들어야 하는 경우라 아래 링크 남겨두었으니 참고하시기 바랍니다.

 

난이도 자체가 매우 높은 내용들은 아니니 차분하게 읽어보시면 금방 이해하리라 생각합니다.

질문이나 빠진/잘못된 내용에 대한 문의하시면, 늦지 않게 피드백하겠습니다. 감사합니다.

 

 

 

 

참고 자료

Wikipedia - MFQ

Wikipedia - Scheduling

Wikipedia - Process(Korean)

GeeksforGeeks - State of Process in OS

서울과학기술대학교 조병호 교수님 운영체제 강의자료

Wikipedia - RM(Korean)

Wikipedia - EDF(Korean)