03-CPU 스케줄링

1. CPU 스케줄링 개요

MySelf-Architec-Oper_11_1

모든 프로세스는 CPU를 필요로 하고 모든 프로세스는 먼저 CPU를 사용하고 싶어 합니다.

이러한 프로세스들에게 공정하고 합리적으로 CPU 자원을 할당하기 위해,
운영체제는 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 기다리게 할지를 결정합니다.
이렇게 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을
- CPU 스케줄링(CPU scheduling)이라고 합니다.
CPU 스케줄링은 컴퓨터 성능과도 직결되는 대단히 중요한 문제입니다.
- 프로세스들에게 현명하게 CPU를 배분하지 못하면,
- 반드시 실행되어야 할 프로세스들이 실행되지 못하거나,
- 당장 급하지 않은 프로세스들만 주로 실행되는 등 무질서한 상태가 발생할 수도 있기 때문입니다.

1.1 프로세스 우선순위

MySelf-Architec-Oper_11_2

프로세스들에게 공정하게 CPU를 배분하려면 어떻게 해야 할까요? 다시 말해, 가장 공정한 CPU 스케줄링이란 무엇일까요?

단순하게 CPU를 사용하고 싶어 하는 프로세스들이 차례로 돌아가며 CPU를 이용하게 하는 방법
- 즉, 먼저 말한 프로세스 순서대로 CPU를 이용하게 하는 방법
- 언뜻 들으면 합리적인 방식인 것 같지만, 사실 좋은 방법이 아닙니다.
- 그 이유는 프로세스마다 우선순위가 다르기 때문입니다.
우선순위가 높은 프로세스란 빨리 처리해야 하는 프로세스들을 의미합니다.
- 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 많은 프로세스가 있습니다.
입출력 작업이 많은 프로세스를 먼저 실행하는 것이 왜 더 효율적일까요? 위 그림을 보면,
- 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는
- CPU 작업이 많은 프로세스(=CPU 집중 프로세스)의 우선순위보다 높다.

이를 이해하려면 일반적인 프로세스가 어떤 과정을 거치며 실행되는지를 생각해 봐야 합니다.

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행됩니다.
달리 말하면, 프로세스는 실행 상태와 대기 상태를 반복하며 실행됩니다.
e.g. 워드 프로세서는 CPU를 사용하여 명령어를 실행하고,
- 사용자로부터 입력받은 내용을 보조기억장치에 저장하고,
- CPU를 사용하여 명령어를 실행하고,
- 사용자가 입력한 내용을 화면에 출력하는 과정을 반복하며 실행됩니다.

그런데 프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 있습니다.

비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스도 있고,
- 입출력 집중 프로세스(I/O bound process)라고 합니다.
- 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 됩니다.
복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스도 있습니다.
- CPU 집중 프로세스(CPU bound process)라고 합니다.
- 대기 상태보다는 실행 상태에 더 많이 머무르게 됩니다.

💡 CPU 버스트와 입출력 버스트

CPU 버스트(CPU burst) : CPU를 이용하는 작업

입출력 버스트(I/O burst) : 입출력장치를 기다리는 작업

프로세스는 일반적으로 CPU 버스트와 입출력 버스트를 반복하며 실행된다고 볼 수 있습니다.

그래서

입출력 집중 프로세스는 입출력 버스트가 많은 프로세스,

CPU 집중 프로세스는 CPU 버스트가 많은 프로세스라고 정의할 수 있습니다.

MySelf-Architec-Oper_11_4

CPU 집중 프로세스는 CPU를 많이 사용해야 하는 프로세스이고, 입출력 집중 프로세스는 그렇지 않은 프로세스인데, CPU 집중 프로세스와 입출력 집중 프로세스가 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적입니다.

e.g. CPU 집중 프로세스와 입출력 집중 프로세스가 동시에 CPU 자원을 요구했다고 가정해 봅시다.

이러한 경우 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고,
그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적입니다.
입출력장치가 입출력 작업을 완료하기 전까지는,
- 입출력 집중 프로세스는 어차피 대기 상태가 될 예정이기 때문에,
- 입출력 집중 프로세스를 얼른 먼저 처리해버리면,
- 다른 프로세스가 CPU를 사용할 수 있기 때문입니다.

MySelf-Architec-Oper_11_5

이렇듯 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다
- 각각의 상황에 맞게 CPU를 배 분하는 것이 더 효율적입니다.
상황에 맞게, 그리고 프로세스의 중요도에 맞게 프로세스가 CPU를 이용할 수 있도록 하기 위해,
- 운영체제는 프로세스마다 우선순위(priority)를 부여합니다.
운영체제는 각 프로세스의 PCB에 우선순위를 명시하고,
- PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정합니다.
그렇게 자연스레 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행됩니다.

💡 프로세스 우선순위 직접 확인하기

우선순위가 높은 대표적인 프로세스는 입출력 작업이 많은 프로세스이지만,

이외에도 우선순위가 높은 프로세스로는 실시간 프로세스, 일부 백그라운드 프로세스 등 다양합니다.

어떤 프로세스의 우선순위가 높고, 어떤 프로세스의 우선순위가 낮은지 직접 확인해보세요.

유닉스, 리눅스, macOS 등의 유닉스 체계 운영체제에서는 ps -el 명령을 통해 확인이 가능합니다.

nice 명령을 통해 일부 프로세스의 우선순위를 변경할 수도 있지요.
1minchul@minchul:~$ ps -el
2F S UID PID PPID  C  PRI NI ADDR SZ  WCHAN  TTY  TIME CMD
34 S   0   1    0  4  80   0 - 41422  -       ?   00:00:03 systemd
41 S   0   2    0  0  80   0 -     0  -       ?   00:00:00 kthreadd
51 I   0   3    2  0  60 -20 -     0  -       ?   00:00:00 rcu_gp
61 I   0   4    2  0  60 -20 -     0  -       ?   00:00:00 rcu_par_gp
71 I   0   5    2  0  80   0 -     0  -       ?   00:00:00 kworker/0:0-events
81 I   0   6    2  0  60 -20 -     0  -       ?   00:00:00 kworker/0:0H-mmc_complete
윈도우에서는 Process Explorer라는 소프트웨어를 통해 우선순위 확인과 변경이 가능합니다.

1.2 스케줄링 큐

MySelf-Architec-Oper_11_7

PCB에 우선순위가 적혀 있다고는 하지만,
- CPU를 사용할 다음 프로세스를 찾기 위해
- 운영체제가 일일이 모든 프로세스의 PCB를 뒤적거리는 것은 비효율적입니다.
- CPU를 원하는 프로세스들은 한 두 개가 아니고,
- CPU를 요구하는 새로운 프로세스는 언제든 생길 수 있으니까요.
이는 비단 CPU 자원에만 국한된 상황이 아닙니다.
- 메모리에 적재되고 싶어 하는 프로세스도 얼마든지 있을 수 있고,
- 특정 입출력장치와 보조기억장치를 사용하길 원하는 프로세스도 여러 개가 있을 수 있습니다.
운영체제가 매번 일일이 모든 PCB를 검사하여,
- 먼저 자원을 이용할 프로세스를 결정하는 일은 매우 번거로울뿐더러 오랜 시간이 걸리는 일입니다.

MySelf-Architec-Oper_11_8

그래서 운영체제는 프로세스들에 **‘줄을 서서 기다릴 것’**을 요구합니다.

CPU를 사용하고 싶은 프로세스들,
메모리에 적재되고 싶은 프로세스들,
특정 입출력장치를 사용하고 싶은 프로세스들을 모두 줄 세우는 것이죠.
그리고 운영체제는 이 줄을 스케줄링 큐(scheduling queue)로 구현하고 관리합니다.
운영체제는 메모리로 적재되고 싶은(새로 생성되는) 프로세스들을
- 큐에 삽입하여 줄을 세우고,
- CPU를 이용하고 싶은 프로세스들 또한 큐에 삽입하여 줄을 세우고,
- 특정 입출력장치를 이용하고 싶은 프로세스들 역시 큐에 삽입하여 줄을 세웁니다.

1.2.1 준비 큐와 대기 큐

MySelf-Architec-Oper_11_9

운영체제가 관리하는 대부분의 자원은 이렇듯 큐로 관리됩니다.
그래서 운영체제가 관리하는 줄, 즉 큐에는 다양한 종류가 있습니다.
대표적인 큐로 준비 큐와 대기 큐가 있습니다.
- 준비 큐(ready queue) : CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미
- 대기 큐(waiting queue) : 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미
cf. 큐는 자료 구조 관점에서 보았을 때는
- 먼저 삽입된 데이터가 먼저 나가는 선입선출(First In First Out) 자료 구조이지만,
- 스케줄링에서 이야기하는 큐는 반드시 선입선출 방식일 필요는 없습니다.

1.2.2 우선순위(priority)

MySelf-Architec-Oper_11_10

준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입되어 CPU를 사용할 차례를 기다립니다.

운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되,
- 그 중 우선순위가 높은 프로세스를 먼저 실행합니다.
우선순위가 낮은 프로세스들이 먼저 큐에 삽입되어 줄을 섰다고 할지라도,
- 우선순위가 높은 프로세스는 그들보다 먼저 처리될 수 있습니다.
이런 점에서 봤을 때, 높은 우선순위를 가진 프로세스는 마치 VIP와도 같습니다.
- 이처럼 프로세스들로 하여금 줄을 세우면서,
- 동시에 높은 우선순위부터 실행하는 구체적인 방식은 다음 절에서 다루겠습니다.

MySelf-Architec-Oper_11_11

대기 상태에 있는 프로세스도 마찬가지입니다.

같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다립니다.
e.g. 하드 디스크 사용을 요구한 프로세스는
- 하드 디스크 대기 큐에서 입출력 작업이 완료되기를 기다리고,
e.g. 프린터 사용을 요구한 프로세스는
- 프린터 대기 큐에서 입출력 작업이 완료되기를 기다리는 것이지요.
입출력이 완료되어, 완료 인터럽트가 발생하면,
- 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고,
- 이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거합니다.
- 당연히 해당 PCB는 준비 큐로 이동합니다.

MySelf-Architec-Oper_11_12

10장에서 배운 프로세스 상태 다이어그램을 기억하나요? 운영체제가 유지하는 여러 큐에 대해 알았다면, 프로세스 상태 다이어그램을 위 그림과 같이 조금 더 세밀하게 완성할 수 있습니다

1.3 선점형과 비선점형 스케줄링

MySelf-Architec-Oper_11_13

다시 여러분이 운영체제라고 가정해 봅시다. 여러분이 프로세스에 CPU를 사용하도록 허락하여, 해당 프로세스는 CPU를 잘 사용하고 있다고 해 보죠. 그런데 갑자기 다른 급한 프로세스가 CPU를 지금 당장 사용하길 요청한다면, 여러분은 어떻게 할건가요?

이런 상황에서 여러분이 택할 수 있는 방법은 2가지입니다.

선전혐 스케줄링(preemptive scheduling)
- 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아, 다른 프로세스에 할당
비선점형 스케줄링(non-preemptive scheduling)
- 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 기다리기

1.3.1 선점형 스케줄링

MySelf-Architec-Oper_11_14

cf. 선점(preemptive) : **‘남보다 앞서서 차지함’**을 의미
현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아, 다른 프로세스에 할당하는 스케줄링 방식
장점 : 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다.
단점 : 그만큼 문맥 교환과정에서 오버헤드가 발생할 수 있다.
지금까지 설명한 스케줄링 방식이 선점형 스케줄링의 일종입니다.
- 프로세스마다 정해진 시간만큼 CPU를 사용하고,
- 정해진 시간을 모두 소비하여, 타이머 인터럽트가 발생하면,
- 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에 할당하는 방식

1.3.2 비선점형 스케줄링

MySelf-Architec-Oper_11_15

cf. 비선점(non-preemptive) : 선점의 반대 개념, 앞서서 차지하지 않음
현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 기다리기
다시 말해, 하나의 프로세스가 자원을 사용하고 있다면,
- 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진
- 다른 프로세스가 끼어들 수 없는 스케줄링 방식
비선점형 스케줄링의 장단점은 선점형 스케줄링의 장단점을 뒤집은거라고 보면 됩니다.
장점 : 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다
단점 : 모든 프로세스가 골고루 자원을 이용하기 어렵다.

2. CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘의 종류는 매우 다양하고 운영체제 저마다 서로 다른 스케줄링 알고리즘을 사용하고 있습니다.

이 책에서 다루지 못한 스케줄링 알고리즘도 있지요.
중요한 것은 각 스케줄링 알고리즘에서 사용된 ‘아이디어’이지, ‘용어’가 아닙니다.
그래서 각 스케줄링 방법을 달달 외울 필요는 없습니다.
그러므로 각 스케줄링 알고리즘들의 작동 방식과 장단점을 이해하는데에만 집중하여 학습하길 바랍니다.

2.1 선입 선처리 스케줄링 (FCFS)

MySelf-Architec-Oper_11_16

FCFS 스케줄링(First Come First Served Scheduling) === 선입 선처리 스케줄링
단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링
먼저 CPU를 요청한 프로세스부터 CPU 할당
단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용
- 이런 현상을 호위 효과(convoy effect)라고 합니다.
e.g. CPU를 오래 사용하는 프로세스가 먼저 도착하면,
- 다른 프로세스는 그 프로세스가 CPU를 사용하는 동안 무작정 기다리는 수밖에 없음
e.g.
- 17ms 동안 CPU를 이용하는 프로세스 A,
- 5ms 동안 CPU를 이용하는 프로세스 B,
- 2ms 동안 CPU를 이용하는 프로세스 C가 차례로 준비 큐에 삽입된다면,
- 프로세스 C는 고작 2ms를 실행하기 위해 22ms (17ms+5ms)라는 긴 시간을 기다려야만 합니다.

2.2 최단 작업 우선 스케줄링 (SJF)

호위 효과를 방지하려면 어떻게 해야 할까요? 단순하게 생각해보면,

CPU 사용 시간이 긴 프로세스는 나중에 실행하고,
CPU 사용 시간이 짧은 간단한 프로세스를 먼저 실행하면 되겠죠?

MySelf-Architec-Oper_11_17

SJF 스케줄링(Shortest Job First Scheduling) === 최단 작업 우선 스케줄링
호위 효과를 방지하려면?
CPU 사용 시간이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
e.g. FCFS 그림의 프로세스 A의 CPU 사용 시간이 매우 길기 때문에 B와 C는 무작정 오래 기다림
- 위 SJF 그림처럼 CPU 사용 시간이 짧은 C와 B부터 실행한다면,
- C는 더 이상 기다릴 필요가 없고, B는 2ms, A는 7ms만 기다리면 됩니다.
cf. SJF 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만,
- 선점형으로 구현될 수도 있습니다.
- 선점형 SJF 스케줄링이 뒤에 언급할 최소 잔여 시간 우선 스케줄링입니다.

2.3 라운드 로빈 스케줄링 (RR)

MySelf-Architec-Oper_11_18

RR 스케줄링 (round robin scheduling) === 라운드 로빈 스케줄링
RR 스케줄링 = 선입 선처리 스케줄링(FCFS) + 타임 슬라이스(time slice)
타임 슬라이스(time slice) : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 큐에 삽입된 프로세스들은 순서대로 CPUI를 이용하되 정해진 시간만큼만 이용
- 정해진 시간을 모두 사용했음에,도 아직 프로세스가 완료되지 않았다면, 다시 큐의 맨 뒤에 삽입
  - 즉, 문맥 교환(context switch)이 발생
RR 스케줄링에서 타임 슬라이스 크기가 매우 중요합니다.
- 타임 슬라이스가 너무 크면, 사실상 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 생기고,
- 타임 슬라이스가 너무 작으면, 문맥 교환에 발생하는 비용이 커져서,
  - CPU는 프로세스를 처리하는 일보다
  - 프로세스를 전환하는 데에 온 힘을 다 쓸 여지가 있기 때문입니다.
  - 즉, 문맥교환에 발생하는 오버헤드가 때문에 CPU 부담이 너무 커짐
e.g. CPU 사용 시간이 11ms, 3ms, 7ms인 프로세스 A, B, C를
- 타임 슬라이스가 4ms인 라운드 로빈 스케줄링을 한다면, 위 그림처럼 수행됩니다.

2.4 최소 잔여 시간 우선 스케줄링 (SRT)

SRT (Shortest Remaining Time) 스케줄링 === 최소 잔여 시간 우선 스케줄링
SRT 스케줄링 = 최단 작업 우선 스케줄링(FCFS) + 라운드 로빈(RR) 스케줄링
- FCFS 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- RR 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사욯하는 스케줄링 알고리즘
정해진 시간만큼 CPU를 이용하되, (RR)
- 다음으로 CPU를 선택할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택 (FCFS)

2.5 우선순위 스케줄링 (priority)

우선순위 스케줄링(priority scheduling)
프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행
우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
cf, SJF 스케줄링, SRT 스케줄링 알고리즘은 넓은 의미에서 우선순위 스케줄링의 일종으로 볼 수 있습니다.
- SJF 스케줄링 : 작업(Job) 시간이 짧은 프로세스에 높은 우선순위를 부여하는 방식
- SRT 스케줄링 : 남은(Remaining) 시간이 짧은 프로세스에 높은 우선순위를 부여하는 방식

2.5.1 문제점 : 기아현상

MySelf-Architec-Oper_11_19

다만, 우선순위 스케줄링은 근본적인 문제를 내포하고 있습니다.

우선순위 스케줄링의 근본적인 문제점, 기아(starvation) 현상
우선순위 높은 프로세스만 주구장창 실행
우선순위 낮은 프로세스 (쭌비 큐에 먼저 삽입되었음에도 불구하고) 실행 연기

2.5.2 기아현상 해결법 : 에이징

MySelf-Architec-Oper_11_20

이를 방지하기 위한 기법 : 에이징(aging)
오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
마치 대기 중인 프로세스의 우선순위를 마치 나이먹듯 점차 증가시키는 방법
- 우선순위가 낮아도 언젠가는 우선순위가 높아진다.

2.6 다단계 큐 스케줄링

MySelf-Architec-Oper_11_21

multilevel queue 스케줄링 === 다단계 큐 스케줄링
우선순위 스케줄링의 발전된 형태
우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리
- 우선순위가 가장 높은 큐가 비어 있으면, 그 다음 우선순위 큐에 있는 프로세스 처리
e.g. 위 그림을 보면,
- 우선순위 0에 삽입된 프로세스들, 우선순위 1에 삽입된 프로세스들, 우선순위 2에 삽입된 프로세스들
- 순서대로 CPU를 할당받아 실행됩니다.
큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해집니다.
- 어떤 큐에는 우선순위가 비교적 높아야 하는 CPU 집중 프로세스가 삽입될 수 있고,
- 어떤 큐에는 우선순위가 비교적 낮아도 상관없는 입출력 집중 프로세스가 삽입될 수 있습니다.
또한 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있습니다.
- e.g. 어떤 큐에서의 타임 슬라이스는 크게,
- 어떤 큐에서의 타임 슬라이스는 작게 사용하고,
- 어떤 큐에서는 선입 선처리 스케줄링을 사용하고,
- 어떤 큐에서는 라운드 로빈 스케줄링을 사용할 수 있습니다.

2.6.1 문제점 : 기아현상

그러나 Multilevel queue 스케줄링에도 문제점이 있습니다.

기본적으로 프로세스들이 큐 사이를 이동할 수 없습니다.
다시 말해, 우선순위가 낮은 프로세스는 계속 우선순위가 낮은 큐에 머무를 수 밖에 없습니다. (계속 연기)
즉, 다시 한번 기아 현상이 발생할 수 있습니다.
이걸 해결하기 위해 등장한 것이 다단계 피드백 큐 스케줄링입니다.

2.7 다단계 피드백 큐 스케줄링

MySelf-Architec-Oper_11_22

multilevel feedback queue 스케줄링 === 다단계 피드백 큐 스케줄링
다단계 큐 스케줄링의 발전된 형태
큐 간의 이동이 가능한 다단계 큐 스케줄링
- 새로 준비 상태가 된 프로세스가 있다면,
- 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스) 동안 실행
다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동 불가
- 우선순위가 낮은 프로세스는 계속해서 실행 연기 우려
- 기아 현상 발생 가능

MySelf-Architec-Oper_11_23

다단계 피드백 큐 스케줄링 하에서는 새롭게 준비 상태가 된 프로세스가 있으면,

그 프로세스를 가장 우선순위가 높은 큐에 삽입하고,
타임 슬라이스만큼 CPU를 할당받아서 사용하게 하고,
이떄 실행이 안 끝났다면, (CPU가 더 필요하다면)
우선순위가 다음으로 높은 큐에다가 삽입합니다.
- 우선순위 1 큐에서 또 처리가 되고, 쭉 실행합니다.
- 여기서도 실행이 안 끝났으면
- 또 우선순위가 다음으로 높은 큐에다가 삽입합니다.
즉, CPU를 많이 이용해야 하는 프로세스일 수록, 우선순위가 자연스럽게 낮아집니다.
자연스럽게
- CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고,
- 입출력 집중 프로세스의 우선순위는 상대적으로 높아짐

2.7.1. 에이징 기법 적용

MySelf-Architec-Oper_11_24

다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있는 방식이기 때문에
낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면,
점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있습니다.

MySelf-Architec-Oper_11_25

어떤 프로세스의 CPU 이용 시간이 길면, 낮은 우선순위 큐로 이동시키고,
어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면, 높은 우선순위 큐로 이동시키는 방식
cf. 다단계 피드백 큐 스케줄링은 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘입니다.

02-프로세스-스레드 04-프로세스 동기화