CPU 스케줄링 [운영체제]

1. 프로세스 우선순위

우선순위가 높은 프로세스는 낮은 프로세스보다 CPU를 먼저 더 오래 차지함

1.1 Kernel process 와 user process

kernel process의 우선순위는 user process의 우선순위보다 높음
kernel process들은 우선순위가 서로 다름
User process들은 우선순위가 서로 다름
User process의 우선순위는 사용자가 변경 가능
- 예 : 리눅스에서 nice 명령을 가지고 user process의 우선순위 변경 가능

1.2 CPU bound process와 I/O bound process

CPU burst
- 프로세스가 실행(running) 상태에서 CPU를 집중적으로 사용하는 시간
I/O burst
- 대기(waiting) 상태에서 I/O을 집중적으로 하는 시간

CPU bound process
- I/O burst 보다 CPU burst가 많은 프로세스
I/O bound process
- CPU burst 보다 I/O burst가 많은 프로세스
I/O bound process의 우선 순위를 CPU bound process보다 높이면 시스템의 효율성이 향상됨
- I/O bound process가 실행 상태가 되면 I/O controller에게 입출력을 요청하여 대기 상태로 옮겨져서 CPU bound process가 CPU를 바로 사용할 수 있기 때문임

[그림 2] CPU bound process가 I/O bound process보다 우선순위가 높은 경우

[그림 3] I/O bound process가 CPU bound process보다 우선순위가 높은 경우

1.3 foreground process 와 background process

foreground process
- 키보드로 표준 입력을 받아들여 실행되는 프로세스
- 사용자와의 상호작용이 가능하여 interactive process 라고도 함
> 키보드로 표준 입력을 받아들이는 프로세스는 한 순간에 하나밖에 없음
> 어느 한 터미널에서 foreground 프로세스는 다른 터미널에서 background 프로세스로 보임
ex)
> 사용자가 로그인 하자 마자 보이는 쉘 프로세스(Ubuntu의 경우 : bash 프로세스)
> 만약 사용자가 쉘을 통해 vi를 실행하면 쉘 프로세스는 background 프로세스가 되고 vi는 foreground 프로세스 가 됨
background process
- 한 프로세스가 실행되는 동안 뒤에서 실행되는 프로세스
> 리눅스는 여러 프로세스가 동시에 실행되는 multi-process를 지원하기 때문에 프로세스를 background 모드로 실행할 수 있음
- 리눅스에서 background process로 실행하기 위해 명령어 라인의 마지막에 '&'기호 사용
ex)
> 파일 찾기는 시간이 오래 걸리기 때문에 찾기 작업이 종료될 때까지 다른 작업을 할 수 없음. 이러한 경우 파일 찾 기 작업을 background 모드로 실행시키고 foreground 모드로 다른 작업을 수행
foreground process는 background process보다 우선순위가 높음
- foreground process는 사용자의 표준 입력을 바로 처리해야 하기 때문임

1.4 정리

우선순위 높음	우선순위 낮음
1. kernel process 2. foreground process 3. interactive process 4. I/O bound process	1. user process 2. background process 3. batch process 4. CPU bound process

2. 준비 상태의 다중 큐

프로세스의 우선순위는 PCB의 CPU scheduling information에 저장되어 있음

2.1 준비상태(ready state)의 준비 큐(ready queue)는 프로세스의 우선순위에 따라 다중 큐로 구성됨

프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입
준비 큐를 몇 개로 나눌지, 준비 큐에 있는 프로세스 중 어떤 프로세스에게 CPU를 할당할지는 스케줄링 알고리즘에 따라 다름

2.2 프로세스의 우선순위를 배정하는 방식

고정 우선순위 방식
- OS에 의해 정해진 프로세스의 우선순위는 프로세스가 끝날 때까지 변하지 않음
- 구현하기 쉽지만 시스템의 변화에 대응하기 힘들기 때문에 시스템의 효율성을 저하시킴
변동 우선순위 방식
- 프로세스의 우선순위는 실행 중 변함
- 구현하기 어렵지만 시스템의 변화에 대응하기 용이해 지므로 시스템의 효율성을 향상시킴

3. 대기 상태의 다중 큐

대기상태(waiting state)의 대기 큐(waiting queue)는 입출력 장치의 종류에 따라 다중 큐로 구성됨

같은 I/O를 요구하는 프로세스끼리 같은 큐에 넣음
여러 입출력 장치가 있기 때문에 I/O가 동시에 끝날 경우 여러 개의 interrupt가 동시에 처리됨

4. 다중 큐 비교

4.1 프로세스의 우선순위를 배정하는 방식

5. CPU 스케줄링

5.1 CPU 스케줄링

운영체제의 프로세스 관리를 위해 사용됨
- 준비 상태에 여러 프로세스 중 어느 프로세스에게 먼저 CPU를 할당하여 실행시킬 것인지를 결정하기 위해 사용됨

5.2 CPU 스케줄링의 목적

공평성
- 모든 프로세스가 시스템 자원을 공평하게 배분받도록 함
효율성
- 시스템 자원이 유휴 시간없이 사용되도록 함
안정성
- 우선순위가 높은 프로세스가 먼저 실행되도록 하여 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호함
확장성
- 프로세스가 증가해도 시스템이 안정적으로 작동하도록 함
반응 시간 보장
- 시스템이 적절한 시간 내에 프로세스의 요구에 반응하도록 함
무한 연기 방지
- 특정 프로세스의 작업 무한히 연기되지 않도록 함

프로세스를 처리하기 위한 단계가 필요하며 각 단계별 스케줄링은 다음과 같음

5.3 장기 스케줄링(long-term scheduling)

시스템에서 활성화되는(실행가능한) 프로세스 수 결정
활성화되는 프로세스를 결정하므로 Job 스케줄링이라고도 함

5.4 중기 스케줄링(Middle-term-scheduling)

시스템의 과부하를 막기위해 이미 활성화된 프로세스 수 조정
- 이미 활성화된 프로세스를 보류상태로 보내고 과부하가 해소되면 다시 활성화 시킴
- 운영체제는 처리가 보류된 프로세스들을 처리 재개가 가능할 때까지 주기억장치에서 하드 디스크로 옮기는데, 이 과정을 스왑 아웃(Swap out)이라고 부르고, 반대를 스왑 인(Swap In)이라고 함
[참고] Swapping
- 물리 메모리(RAM)의 용량이 부족할 때 프로세스를 메모리에서 하드 디스크로 일시적으로 이동(Swap out) 시켰다가 실행을 계속하기 위해 다시 메모리로 되돌아 오게 하는 것(Swap in)

5.5 단기 스케줄링(short-term scheduling)

준비 상태에 있는 프로세스 중 하나를 골라 실행 상태로 보냄
실행 상태에 있는 프로세스를 준비 상태로 보냄
실행 상태에 있는 프로세스를 대기 상태로 보냄
대기 상태의 프로세스를 준비 상태로 보냄
아주 짧은 시간 내에 일어나기 때문에 단기 스케줄링이라고 함
일반적으로 CPU 스케줄링은 단기 스케줄링을 말함

5.6 CPU 스케줄링은 비선점형(non-preemptive)과 선점형(preemptive)으로 나뉨

구분	비선점형 스케줄링	선점형 스케줄링
방식	1. 실행 중인 프로세스로부터 CPU를 빼앗을 수 없음 2. 실행 중인 프로세스는 완료되거나 대기 상태가 될 때까지 계속 실행됨	1. 실행중인 프로세스로부터 CPU를 빼앗아 다른 프로세스를 실행시킬 수 있음 2. 시분할 시스템을 위해 만들어짐 3. RR 스케줄링 ex) 프로세스는 CPU사용시간(time slice)동안 실행되고 난 다음 실행이 완료되지 않으면 준비 큐의 끝으로 이동하여 다음 실행될 차례를 기다리고 준비 큐의 앞에 있는 프로세스가 실행됨(다른 프로세스에게 CPU를 빼앗김)
장점	1. 드문 문맥 교환(context switch)로 인해 오버헤드 작음(실행 중인 프로세스가 완료(terminated)되거나 대기(waiting) 상태가 될 때까지 문맥 교환이 발생하지 않음)	1. 하나의 프로세스가 CPU를 독점할 수 없어서 빠른 응답 시간을 요구하는 시스템에 적합
단점	1. 실행중인 프로세스는 완료되거나 대기 상태가 될 때까지 계속 실행됨(시스템 효율성 낮음) 2. 따라서, 비선점형 스케줄링은 지금은 거의 사용되지 않음	1. Time slice가 작으면 잦은 문맥 교환(context switch) 로 인한 오버헤드가 큼 (프로세스 실행 시간보다 문맥 교환 시간이 증가할 수 있음)
사용	일괄 작업 시스템	시분할 시스템
알고리즘	FCFS, SJF, HRN	RR, SRT, MLQ, MLFQ

6. 스케줄링 알고리즘의 선택 기준

6.1 CPU 사용률(CPU utilization)

전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정
이 수치가 클수록 좋은 알고리즘임
- 이상적인 수치는 100% 이지만 실제로는 여러 가지 이유로 90%에도 못 미침

6.2 처리량(throughput)

단위 시간당 작업을 마친 프로세스 수
이 수치가 클수록 좋은 알고리즘임

6.3 대기시간(waiting time)

준비 상태의 준비 큐(ready queue)에서 프로세스가 CPU를 할당 받기위해 기다리는 대기 시간
- 대기 상태의 대기 큐(waiting queue)에서 프로세스가 I/O 처리가 완료되길 기다리는 대기 시간이 아님!(!주의!)
이 수치가 짧을수록 좋은 알고리즘임

6.4 응답 시간(response time)

첫 프로세스 시작 후 첫 번째 출력(반응)이 나오기까지의 시간
이 수치가 짧을수록 좋은 알고리즘임

6.5 반환 시간(turnaround time)

프로세스의 대기 시간과 실행 시간의 합
이 수치가 짧을수록 좋은 알고리즘임

7. 스케줄링 알고리즘의 평가 기준

스케줄링 알고리즘의 시스템 효율성을 평가하기 위해 CPU 사용율과 처리량은 계산하기 어렵기 때문에 주로 대기 시간, 응답 시간, 반환 시간을 계산함

7.1 평균 대기 시간

모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값
이 수치가 짧을수록 좋은 알고리즘임
스케줄링 알고리즘의 성능을 비교하기 위해 많이 사용됨

비선점형 스케줄링

8. FCFS(First Come First Served) Scheduling

우선순위 미 사용(큐에 있는 순서대로 프로세스 처리)

8.1 비선점형 스케줄링

실행 중인 프로세스로부터 CPU를 빼앗을 수 없음
실행 중인 프로세스가 완료되거나 대기 상태가 될 때까지 계속 실행됨

8.2 준비 큐에 들어온 프로세스 순서대로 실행(First-In First-Out, FIFO) -> 우선순위 사용 안함

8.3 단점

convoy effect 발생할 수 있음
- 실행 시간이 긴 프로세스가 먼저 실행되면 실행시간이 짧은 프로세스는 실행이 계속 지연되는 현상
- 해결방법
> 우선순위 사용 : 실행 시간이 짧은 프로세스에게 높은 우선순위 부여하여 먼저 실행시킴(SJF, HRN, SRT)
> time slice 사용(RR)

※ 아래의 표와 같은 프로세스 P1, P2, P3가 FCFS 스케줄링으로 실행될 때 평균 대기 시간 계산

프로세스	준비 큐에 도착 시간(ms)	실행 시간(ms)
P1	0	30
P2	3	18
P3	6	9

P1 은 가장 먼저 도착하여 먼저 실행 -> 그 다음 도착한 P2가 실행됨 -> 그 다음 도착한 P3가 실행됨
평균 대기 시간 = 0(P1) + 27(P2) + 42(P3) / 3 = 23ms

9. SJF(Shortest Job First) Scheduling

9.1 비선점형 스케줄링

9.2 FCFS 스케줄링의 convoy effect를 완화하기 위한 스케줄링

준비 큐에 있는 프로세스 중 실행 시간이 짧은 프로세스에게 높은 우선순위 부여하여 먼저 실행됨

9.3 단점

프로세스의 실행 시간을 정확히 계산하기 어려움
- 예 : 워드프로세서는 사용자에 의해 몇시간 동안 사용될 수 있음
starvation(아사, 기아상태) 발생할 수 있음
- 우선순위가 높은 프로세스가 계속 준비 큐에 들어와서 먼저 실행되면 우선순위가 낮은 프로세스는 실행이 계속 지연되는 문제
> 우선순위가 낮은 프로세스는 CPU를 할당 받지 못해 굶음
- 프로세스의 우선순위를 기반으로 한 스케줄링에서 주로 발생함

※아래의 표와 같은 프로세스 P1, P2, P3가 SJF 스케줄링으로 실행될 때 평균 대기 시간 계산

프로세스	준비 큐에 도착한 시간(ms)	실행 시간(ms)
P1	0	30
P2	3	18
P3	6	9

P1은 가장 먼저 도착하여 먼저 실행 -> P2와 P3 중에서 실행 시간이 짧은 P3가 높은 우선순위를 가지므로 먼저 실행됨 -> P2가 실행됨
평균 대기 시간 = 0(P1) + 24(P3) + 36(P2) / 3 = 20ms

10. HRN(Highest Response Ratio Next) Scheduling

10.1 비선점형 스케줄링

SJF스케줄링의 starvation(실행 시간이 긴 프로세스(우선 순위가 낮은 프로세스)는 실행이 계속 연기되어 대기 시간이 길어지는 문제)를 완화하기 위해 에이징(대기 시간이 긴 프로세스에게 높은 우선순위 부여) 사용

준비 큐에 있는 프로세스 중 실행 시간이 짧거나 대기 시간이 긴 프로세스에게 높은 우선순위 부여하여 먼저 실행됨

- 우선순위 = (대기시간 + 실행시간) / 실행시간 -> 대기시간 + 실행시간 이 높은 프로세스에게 우선순위 부여
- 위의 값이 클수록 우선순위 높음

10.2 단점

프로세스의 실행 시간을 정확히 계산하기 어려움
SJF 스케줄링 보다 starvation이 완화되는게 있지만 여전히 존재함

※아래의 표와 같은 프로세스 P1, P2, P3 가 HRN 스케줄링으로 실행될 때 평균 대기 시간 계산

프로세스	준비 큐에 도착 시간(ms)	실행 시간(ms)
P1	0	30
P2	3	18
P3	6	9

P1은 가장 먼저 도착하여 먼저 실행 -> P2와 P3의 우선순위 계산(P2의 우선순위 = 27 + 18 / 18 = 2.5, P3 의 우선순위 = 24 + 9 / 9 = 3.67) -> 큰 값을 가진 P3가 높은 우선순위를 가져서 먼저 실행 -> P2가 실행됨
평균 대기 시간 = 0(P1) + 24(P3) + 36(P2) / 3 = 20ms

선점형 스케줄링

11. RR(Round Robin) Scheduling

11.1 FCFS 스케줄링과 유사

준비 큐에 들어온 프로세스 순서대로 실행(우선순위 사용 안함)

11.2 시분할 시스템에서 사용됨

11.3 Time slice 사용

프로세스는 CPU 사용시간(time slice)동안 실행되고 난 다음 실행이 완료되지 않으면(timeout)준비 큐의 끝으로 이동하여 다음 실행될 차례를 기다리고 준비 큐의 앞에 있는 프로세스가 실행됨(다른 프로세스에게 CPU를 빼앗김)
-> 선점형 스케줄링
FCFS 스케줄링에서 나타나는 convoy effect(실행 시간이 긴 프로세스가 실행되고 있으면 실행 시간이 짧은 프로세스가 오랫동안 기다리는 현상)을 완화시킴
하나의 프로세스가 CPU를 독점할 수 없어서 빠른 응답 시간을 요구하는 시스템에 적합

Time slice가 큰 경우
- Time slice = 무한대 이면 RR 스케줄링은 FCFS 스케줄링이 됨
Time slice가 작은 경우
- 잦은 문맥 교환으로 인해 오버헤드가 큼(문맥 교환 시간이 프로세스 실행 시간보다 증가할 수 있음)

※ Time slice = 10ms 인 경우 아래의 표와 같은 프로세스 P1, P2, P3가 RR 스케줄링으로 실행될 때 평균 시간 계산

프로세스	준비 큐에 도착 시간(ms)	실행 시간(ms)
P1	0	30
P2	3	18
P3	6	9

P1 은 가장 먼저 도착하여 먼저 실행 -> P2가 time slice 동안 실행됨 -> P3가 9ms동안 실행되고 완료 -> P1가 time slice 동안 실행됨 -> P2가 8ms동안 실행되고 완료 -> P1가 time slice동안 실행됨
평균 대기 시간 = 0(P1) + 7(P2) + 14(P3) + 19(P1) + 19(P2) + 8(P1) / 3 = 22.33ms

12. SRT(Shortest Remaining Time) Scheduling

12.1 RR 스케줄링과 SJF 스케줄링을 혼합한 방식

기본적으로 RR 스케줄링(선점형)으로 실행되지만 준비 큐에 있는 프로세스 중 남아있는 실행시간이 짧은 프로세스에게 높은 우선순위 부여하여 먼저 실행됨

12.2 단점(SJF 스케줄링의 문제점)

프로세스의 실행 시간을 정확히 계산하기 어려움
Starvation이 발생할 수 있음

※ Time slice = 10ms 인 경우 아래의 표와 같은 프로세스 P1, P2, P3 가 SRT 스케줄링으로 실행될 때 평균 대기 시간 계산

프로세스	준비 큐에 도착 시간(ms)	실행 시간(ms)
P1	0	30
P2	3	18
P3	6	9

P1은 가장 먼저 도착하여 먼저 실행 -> 짧은 실행시간(9ms)을 가진 P3 실행
-> P1의 남아있는 실행 시간(20ms)보다 P2의 실행시간(18ms)와 P2의 실행시간(18ms)와 P2의 남아 있는 실행 시간 (8ms)이 짧기 때문에 P2를 연달아 두 번 실행 -> P1가 실행됨
평균 대기 시간 = 0(P1) + 4(P3) + 16(P2) + 27(P1) / 3 = 15.66ms

13. MLQ(Multilevel Queue) Scheduling

13.1 OS에 의해 정해진 프로세스의 우선순위에 따라 여러 준비 큐(ready queue)를 사용

프로세스의 우선순위가 높은 큐에 있는 모든 프로세스의 실행이 완료되어야 다음 큐에 있는 프로세스를 실행함
각 큐는 RR스케줄링(선점형)으로 처리됨
- 우선순위가 높은 큐일수록 작은 time slice를 사용
> 우선순위가 높은 foreground process는 사용자와 빠른 상호작용을 위해 작은 time slice를 사용
- 우선순위가 낮은 큐일수록 큰 time slice를 사용
> 우선순위가 낮은 background process는 무한대의 time slice를 사용(즉, FCFS 스케줄링으로 처리)
고정 우선순위 방식
- 프로세스의 우선순위는 변하지 않음(프로세스는 다른 큐로 이동하지 못함)
- 프로세스는 time slice동안 실행되고 난 다음 실행이 완료되지 않으면 원래의 큐의 끝으로 이동

13.2 문제점

Starvation이 발생할 수 있음

14. MLFQ(Multilevel Feedback Queue) Scheduling

14.1 OS에 의해 정해진 프로세스의 우선순위에 따라 여러 준비 큐(ready queue)를 사용

프로세스의 우선순위가 높은 큐에 있는 모든 프로세스의 실행이 완료되어야 다음 큐에 있는 프로세스를 실행함
각 큐는 RR스케줄링(선점형)을 사용
- 우선순위가 높은 큐일수록 작은 time slice를 사용
- 우선순위가 낮은 큐일수록 큰 time slice를 사용
> 우선순위가 가장 낮은 큐는 무한대의 time slice를 사용(즉, FCFS 스케줄링으로 처리)
변동 우선순위 방식
- 프로세스는 time slice동안 실행되고 난 다음 실행이 완료되지 않으면 우선순위가 낮아짐
-> 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 이동
- 그러나, 커널 프로세스가 사용자 프로세스가 있는 큐로 이동하지는 않음
- 이러한 방식으로 MLQ 스케줄링의 starvation을 완화시킴
현재 운영체제들의 일반적인 스케줄링 방식

'운영체제' 카테고리의 다른 글

프로세스 동기화 및 임계구역 [운영체제] (0)	2024.04.12
컴퓨터의 구조 [운영체제] (2)	2024.03.25
운영체제의 소개 및 구조 [운영체제] (0)	2024.03.24