[Part2-공룡책] 3. CPU 스케줄링(1/2) - Operating System(OS)

Operating System(OS)에 이어서 Part2에는  다음과 같은 순서*로 알아보겠습니다.

*공룡책을 기반

  
[프로세스 관리]
1. 프로세스
2. 스레드와 병행성
3. CPU 스케줄링
[프로세스 동기화]
4. 프로세스동기화
5. 동기화 예제
6. 교착상태
[메모리 관리]
7. 메인 메모리
8. 가상 메모리
[저장장치 관리]
9. 대용량 저장장치 구조
10. 입출력 시스템
[파일시스템]
11. 파일시스템 
12. 파일시스템 구현

 

삼성전자 갤럭시북4 프로 NT960XGQ-A51A 인텔 울트라5 색상선택 16인치 고해상도 AI 노트북 사무용 대

* 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받을 수 있습니다.

 

Operating System(OS) Part2 - 3.CPU 스케줄링(1/2)

1. 기본개념

운영체제가 프로세스를 프로세서에 할당하는 것을 디스패치(Dispatch)라고 한다. 

(이때 프로세스 상태가 ready에서 running으로 바뀐다.) 

그리고 운영체제가 레디 큐(Ready queue)에 있는 프로세스들 중에서 어떤 프로세스를 

디스패치할 것인가 정하는 것이 프로세스 스케줄링(Process scheduling)이다.

스케줄링 알고리즘에는 대표적으로 FCFS, SJF, SRF, RR 네 가지 방식이 있고, 

알고리즘을 평가할 때는 수행 시간(Burst time)과 CPU 사용량(CPU utilization), 

단위 시간 당 끝마친 프로세스의 수(Throughput), 하나의 프로세스가 레디 큐에서 대기한 시간부터 

작업을 마칠 때까지 걸리는 시간(Turnaround time), 프로세스가 레디 큐에서 대기한 시간(Wating time), 

프로세스가 처음으로 CPU를 할당받기까지 걸린 시간(Response time)을 기준으로 한다.

선점(Preemptive) 방식과 비선점(Non-Preemptive) 방식으로 나뉜다. 

선점 스케줄링은 운영체제가 강제로 프로세스의 사용권을 통제하는 방식이고, 

비선점 스케줄링은 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식이다. 

즉, 선점 스케줄링 방식에서는 CPU에 프로세스가 할당되어 있을 때도 

운영체제가 개입해 다른 프로세스에게 CPU를 할당할 수 있다.

 

2. 스케줄링 기준

1) CPU 이용률(utilization)
앞서 계속 언급했듯, CPU를 최대한 바쁘게 유지시키는 것은 중요한 기준이 된다.
2) 처리량(throughput)
CPU 작업량 측정의 한 방법으로, 단위 시간당 완료된 프로세스의 개수를 의미한다.
3) 총 처리 시간(turnaround time)
프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라고 한다.
총처리 시간은 (1) 준비 큐에서 대기한 시간, (2) CPU에서 실행하는 시간, (3) I/O 시간을 합한 시간이다.
4) 대기 시간(waiting time)
대기 시간은 준비 큐에서 대기하면서 보낸 시간의 합이다.
5) 응답 시간(response time)
응답이 시작되는 데까지 걸리는 시간이다. 즉, 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간을 말한다.

 

3. 스케줄링 알고리즘

1) 선입 선처리 스케줄링 (First-Come First-Served, FCFS)

     - 먼저 들어온 프로세스를 먼저 프로세서에 할당하는 방식이다.

     -  Queue의 FIFO(First-In First-Out)와 동일하다.

     -  구현이 쉬워서 간단한 시스템에 자주 사용된다.

     -   프로세스 처리 순서에 따라 성능이 크게 달라질 수 있다.

     -  수행 시간이 큰 프로세스가 먼저 들어오면 그 뒤에 들어온 프로세스들이 불필요하게

         오랜 시간을 기다리게 되는 콘보이 효과(Convoy effect)가 발생한다.

     - 먼저 온 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

         

Process	Burst time	Response time	Turnaround time	Waiting time
P1	9	0	9	0
P2	1	9	10	9
P3	1	10	11	10

 

+----+----+----+----+----+----+----+----+----+----+----+
|                     P1                     | P2 | P3 |
+----+----+----+----+----+----+----+----+----+----+----+
0                                            9    10   11

Average wating time= (0+9+10)/3=6.33

P1, P2, P3 프로세스가 들어온 순서대로 할당됐다. P2, P3는 수행 시간이 짧음에도 P1이 끝날 때까지 기다리게 되어 평균 대기 시간이 늘어났다.

 

 

2) SJF (Shortest Job First)

     -  프로세스의 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.

     -  FCFS에서 발생하는 콘보이 효과를 해결할 수 있다.

     -  최적 알고리즘이지만 수행 시간을 정확히 알 수 없다. (앞서 처리한 프로세스들의 기록을 보고 추측한다.)

     -  버스트 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.

     -  버스트 시간이 짧은 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

Process	Burst time	Response time	Turnaround time	Waiting time
P1	6	3	9	3
P2	8	16	24	16
P3	7	9	16	9
P4	3	0	3	0

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|      P4      |              P1             |                P3                |                   P2                  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0              3                             9                                  16                                      24

Average wating time=(3+16+9+0)/4=7

 

프로세스의 수행 시간을 정확히 예측했다는 가정하에, 수행 시간이 짧은 순서대로 프로세서에 할당됐다.

 

3) SRF (Shortest Remaining Time First)

     -  프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.

     -  SJF에서 발생하는 기아 문제를 해결할 수 있다.

     -  수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리를 바꾸는 선점 스케줄링 방식이다.

Process	Arrival time	Burst time	Response time	Turnaround time	Waiting time
P1	0	8	0	17	9
P2	1	4	1	5	0
P3	2	9	17	24	15
P4	3	5	5	7	2

 

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| P1 |         P2        |           P4           |                P1                |                     P3                     |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0    1                   5                        10                                 17                                           26

Average wating time=(9+0+15+2)/4=26

 

P1이 수행되던 중, 1ms에 P2가 들어왔다. 이때 P1의 남은 수행 시간은 7ms이고, P2의 남은 수행 시간은 4ms이기 때문에 운영체제가 개입해 P1의 수행을 중단하고 P2를 프로세서에 할당한다. P2가 프로세서에 할당된 사이, 2ms에 P3가 들어왔으나 P2의 남은 수행 시간은 3ms이고, P3의 남은 수행 시간은 9ms이기 때문에 프로세서는 P2를 계속 수행한다. 이어서 3ms일 때 P4가 들어왔지만 P2의 남은 수행 시간은 2ms이고, P4의 남은 수행 시간은 5ms이기 때문에 여전히 P2가 수행된다. 이후에도 같은 방식으로 프로세스의 작업이 끝나거나 새로운 프로세스가 들어올 때마다 남은 수행 시간을 비교해 자리를 바꿔준다.

 

 

4) 라운드로빈 (Round Robin)

     -  일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.

     -  시스템의 time-sharing과 같은 방식이다.

     -  반응성이 좋다.

     -  주로 우선순위 스케줄링(Priority scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용한다.

     -  시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

 

Process	Burst time	Response time	Turnaround time	Waiting time
P1	15	0	19	4
P2	2	3	5	3
P3	2	5	7	5

Time quantum = 3ms

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|      P1      |    P2   |    P3   |      P1      |      P1      |      P1      |      P1      |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0              3         5         7              10             13             16             19

Average wating time=(4+3+5)/3=4

모든 프로세스들이 동일하게 3ms씩 프로세스에 할당된다. P2와 P3의 경우 수행 시간이 2ms이기 때문에 할당된 3ms를 모두 사용하지 않았다.

 

5)Priority Scheduling

     -  특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다.

     -  프로세스를 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식으로 사용된다.

     -  SRF의 경우 남은 수행 시간을 기준으로 우선순위를 부여한다고 할 수 있다.

     -  다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점 모두 가능하다.

 

Process	Priority	Burst time	Response time	Turnaround time	Waiting time
P1	3	5	4	9	4
P2	1	1	0	1	0
P3	4	2	9	11	9
P4	5	1	11	12	11
P5	2	3	1	4	1

+----+----+----+----+----+----+----+----+----+----+----+----+
| P2 |      P5      |           P1           |    P3   | P4 |
+----+----+----+----+----+----+----+----+----+----+----+----+
0    1              4                        9         11   12

Average wating time=(4+0+9+11+1)/5=5

 

우선순위에 따라 프로세스가 할당되었다. 사용자가 자주 사용하는 프로세스의 우선순위를 높게 부여하는 식으로 기준을 만들 수 있다. 다만 특정 프로세스의 우선 순위가 계속 밀려 기아가 발생할 수 있으므로, 시간이 지날 때마다 프로세스의 나이를 증가시켜 오래 대기한 프로세스의 우선순위를 높여주는 조치가 필요하다.

 

 

6)다단계 큐 스케줄링

다단계 큐 스케줄링 알고리즘은 우선순위마다 별도의 큐를 두는 것이다.

 

                                                                       우선순위마다 별도의 큐

각 큐들은 자신의 스케줄링 알고리즘을 가질 수 있는데, 예를 들어 백그라운드 큐는 선입선출, 포그라운드는 라운드 로빈 알고리즘을 사용하는 경우이다.

또한, 큐와 큐 사이에도 스케줄링이 반드시 있어야 하는데, 보통의 우선순위는 실시간 -> 시스템 -> 대화형 -> 배치 순서이다.

 

                                                                                         다단계 큐 스케줄링

 

7) 다단계 피드백 큐 스케줄링

     -  다단계 피드백 큐 스케줄링 알고리즘은 프로세스가 큐들 사이를 이동하는 것을 허용한다.

     -  만약 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동하는 식이다.

     -  마찬가지로 너무 오래 기다린 프로세스들은 높은 우선순위의 큐로 이동할 수도 있다.