프로세스 상태전이, 스케줄링 알고리즘 #3

프로세스/ 프로그램/ 프로세서 차이 

프로세스: 실행중인 프로그램

 

프로그램: 하드디스크 등에 저장되어 있는 실행 파일

 

프로세서: 일반적으로  CPU를 뜻함.

---

 

 

프로세스 상태 전이도

 

프로세스의 상태는 생성 / 준비 / 실행 / 대기 / 완료 5개의 단계로 이루어져 있다.

 

 

프로세스 상태	설명
Create	- 프로세스가 생성되는 단계 - 주기억장치에 적재되지않고 보조기억장치에 저장
Ready	- CPU를 사용하여 실행 준비 된 상태 - 우선순위가 높은 프로세스가 CPU를 할당받는다.
Running	- 프로세스가 CPU를 차지하여 실행중인 상태
Waiting	- 기다림(wating) 또는 블록(block) 상태 - I/O 동작의 완료 등 사건 발생을 기다리는 상태
Terminated	- 프로세스의 실행이 종료

 

프로세스 상태 전이	전이 과정	설명
Dispatch	준비 -> 실행	- 준비 리스트의 맨 앞에 있던 프로세스가 CPU를 점유하게 되는것
Timeout	실행 -> 준비	- 운영체제는 프로세스가 프로세서를 계속 독점해서 사용하지 못하게 하기 위해 clock interrupt를 두어서 프로세스가 일정 시간동안만 프로세서를 점유 할 수 있다.
Block	실행 -> 대기	- I/O 등의 자원 요청후 즉시 할당 받을 수 없어, 할당 받을때까지 기다리고 있는 상태로 전이 - I/O 처리는 CPU가 아닌 I/O 프로세스가 담당하기 때문에 발생
Wake up	실행 -> 준비	- 필요한 자원이 할당되면 프로세스는 준비 상태로 전이
Swap-out	준비 -> 지연 대기 -> 지연	-프로세스가 주기억장치에서 해제 되는 상태
Swap-in	지연 -> 준비 지연 -> 대기	-프로세스가 주기억장치에 적재 되는 상태

 

---

 

스케줄러

 

시스템이 실행하고자 할 때 프로세서(CPU)를 프로그램들에게 할당하는 과정이 스케줄링이다.

 

프로세스(Process)는 자신의 임무를 모두 수행하고 사라질 때까지 많은 큐를 돌아다닌다.

이때 프로그램들은 제한된 프로세서(CPU)를 서로 사용하려고 한다.

OS는 이러한 프로세스 중 하나를 택하는데, 바로 스케줄러가 이러한 역할을 담당한다.

 

가장 자주 사용되는 스케줄러는 장기 스케줄러와 단기 스케줄러이다.

 

장기 스케줄러(Long Term Scheduler)

 

• 메모리와 디스크 사이의 스케줄링을 담당
• 하드디스크에 있는  프로그램을 Job Queue에서 꺼내 Ready Queue를 통해서 메모리로 적재한다.
• 프로세스의 상태는 new -> ready 상태로 전이
• 디스크 내의 작업을 어떤 순서로 메모리에 가져올 지 결정한다.

 

단기 스케줄러(Short Term Scheduler)

 

• CPU와 메모리 사이의 스케줄링을 담당
• 메모리에 있는 프로세스 중 하나를 선택해서 프로세서(CPU)를 할당한다.
• Ready Queue에 있는 프로그램 중 먼저 도착한 프로세스에게 CPU 할당(Dispatch)
• 프로세스의 상태는 ready -> running 상태로 전이

 

중기 스케줄러(Medium Term Scheduler)

 

• 프로세스들이 서로 CPU를 차지하려고 경쟁이 심해지면, swapping 기법을 활용해 메모리를 관리함
• 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping 기법) 
• 현 시스템에서 너무 많은 프로그램들이 동시에 올라가는 것을 조절하는 스케줄러
• 프로세스의 상태는 ready -> suspended

---

 

CPU 스케줄링 알고리즘

 

CPU 스케줄링의 결정 시점

1. Running -> Waiting ( I/O 작업 요청 발생)

2. Running -> Ready ( Time out)

3. Wait -> Ready ( I/O 작업 종료)

4. Running -> Terminated ( 프로세스 종료)

 

비선점형 스케줄링

어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장한다. 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답 시간을 예상할 수 있으며 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥교환에 의한 오버헤드가 적다. 일괄 처리 시스템에 적합하며, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점이 있다.

 

선점형 스케줄링

어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다. 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어 할 수 있다. '운영 체제가 프로세서 자원을 선점' 하고 있다가 각 프로세스의 요청이 있을 때 특정 요건들을 기준으로 자원을 배분하는 방식이다.

 

---

 

스케줄링 알고리즘

1. FCFS 스케줄링(First Come First Served Scheduling)

• 먼저 자원 사용을 요청한 프로세스에게 자원을 할당해 주는 방식의 스케줄링 알고리즘
• Ready Queue에 도착한 순서에따라 Dispatch
• 비선점형 스케줄링

FCFS 스케줄링 예

장점: 가장 간단한 스케줄링 기법

단점: 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 수행될 수 있음

 

2. SJF 스케줄링(Shortest Job First)

• 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식
• 요구 시간이 긴 프로세스가 요구 시간이 짧은 프로세스에게 항상 양보되어 기아 상태 발생 가능
• 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상된 것을 먼저 Dispatch
• 비선점형 스케줄링

Process	도착시간	Burst Time
p1	0	4
p2	1	1
p3	2	3
p4	3	2

맨 처음 CPU에 할당된 프로세스가 없기 때문에 가장 먼저 들어온 p1을 4초간 실행한다. 그 사이에 p2, p3, p4가 도착하게되어 준비큐에 p2, p4, p3 순서로 쌓인다.(Burst Time이 짧은 순서)

따라서 CPU에 할당받는 순서는

p1 -> p2 -> p4 -> p3 이다.

 

대기시간

p1 = 0  (대기시간이 없다)

p2 = 4 (p1 작업 실행 시간 대기)

p4 = 5 (p1 + p2 작업 실행 시간)

p3 = 7 (p1 + p2 + p4 작업 실행 시간)

 

평균대기시간

(0+ 4 + 5 + 7) / 4 = 4초

3. SRT 스케줄링(Shorest Remaining Time)

• CPU 작업시간이 가장 짧은 프로세스 순으로  Dispatch
• Burst Time이 가장 작은 프로세스가 자원을 할당 받았지만, 작업중에 준비큐에 들어온 프로세스가 남은 Burst Time보다 더 작은 Burst Time를 가진다면 자원을 빼앗아 그 짧은 작업부터 처리하는 방식
• 기아상태에 빠질 수 있다.
• 선점형 스케줄링

Process	도착시간	Burst Time
p1	0	4
p2	1	1
p3	2	3
p4	3	2

맨처음 CPU에 할당된 프로세스가 없기 때문에 p1 실행한다. 1초때 Burst Time이 가장 짧은 p2가 들어온다. 그리고 2초때 작업이 끝나고 그 다음 Burst Time이 짧은 p4는 도착 시간이 3이므로 2초때 p1을 다시 실행한다. 그럼 3초때는 p1이 결국 2초가 남게 되는데 p4도 2초의 실행시간이 걸리므로 결국 (2 = 2)똑같으므로(작지 않으면 선택되지 않음) 3초때는 그대로 p1을 실행한다. 그리고 p4가 실행되고 마지막으로 p3이 실행된다.

p1 -> p2 -> p1 -> p4 -> p3

 

이해가기쉽게 표로 정리해 보겠다.

0초	1초	2초	5초	7초	10초
p1	p2	p1	p4	p3	end

 

대기시간

p1 = 1초  (도착시간 0초 + p2 실행시간 1초)

p2 = 0초  ((p1 실행시간 1초) - 도착시간 1초)

p3 = 5초  (7초 - 도착시간 2초)

p4 = 2초  (5초 - 도착시간 3초)

 

총 대기시간

(1 + 0 + 5 + 2) / 4 = 2초

 

SJF 평균 대기시간보다 줄어들었다. 

 

4. 우선 순위 스케줄링 (Prior Scheduling)

• 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링
• 우선순위가 같은 경우 FCFS 스케줄링으로 할당함.
• 대체로 숫자가 작은경우 우선순위가 높음
• 우선 순위가 너무 낮아 CPU 할당을 못 받게되어 기아 상태에 빠질 수 있음
• 실행 준비는 되었지만 CPU를 사용못하는 프로세스를 CPU가 무기한 대기하는 상태 (무기한 봉쇄상태)에 빠질 수 있음
• 비선점형 스케줄링, 선점형 스케줄링 모두 가능

Process	Burst Time	우선순위
p1	1	3
p2	2	2
p3	3	4
p4	4	1

 

우선 순위가 가장 높은 p4부터 CPU를 점유한다. 그리고 p2, p1, p3 순으로 실행된다.

따라서 CPU에 할당 받는 순서는

P4 -> P2 -> P1 -> P4 이다.

 

무기한 봉쇄 상태에 빠지는 경우 해결책으로 Aging 기법을 이용한다. 이 기법은 대기하는 우선순위가 낮은 프로세스를 우선순위를 점진적 증가시킨다. 

 

5. 라운드 로빈 스케줄링(Round Robin Scheduling)

• 각 프로세스는 동일한 할당 시간을 갖게 되고 할당 시간이 끝나면 선점 당하고 준비큐에 제일 뒤에가서 다시 대기한다.
• 시분할 시스템을 위해 설계된 선점형 스케줄링
• 프로세스들 사이에 우선순위를 두지않고, 순서대로 시간단위(Time Quantum)fh CPU를 할당하는 방식

Process	Burst Time
p1	3
p2	4
p3	1
p4	2

Time Quantum = 2초

 

맨 처음 들어온 p1은 2초간 작업을 실행하고 (1초 남음) 준비 큐 맨 뒤로 간다.

2초 뒤에 p2가 실행하고 (2초 남음) 준비 큐 맨 뒤로 간다.

2초 뒤에 p3가 실행하고 (1초 동안 실행) 2초 뒤에 p4가 실행하고 p1이 남은 1초간 실행하고 p2가 남은 2초간 실행하고 끝난다.

 

p1 -> p2 -> p3 -> p4 -> p1 -> p2

 

이 알고리즘은 Time Quantum이 너무 크면 FCFS 스케줄링 알고리즘과 다를바가 없고

Time QuanTum이 너무 작으면 문맥교환이 많이 일어남으로써 오버헤드가 발생 할 수 있기 때문에 적절한 시간을 설정하는 것이 중요하다.