[운영체제(OS)] 6-1. CPU 스케줄링 (CPU scheduling)

Short-Term schduling이라고 불리는 CPU scheduling은 현재 CPU 자원을 어떤 process에게 할당할 것인가를 결정하는 것이다. 

 

Process는 CPU사용시간에 따라 두가지 종류로 나뉠수 있다.

• I/O bound job : CPU를 사용하는 빈도는 많지만(CPU를 process가 잡는 빈도) 실제 사용하는 시간은 적은 process를 가르킨다.
• CPU bound job : CPU를 사용하는 빈도는 적지만 실제 사용하는 시간은 긴 process를 가르킨다. 계산 위주의 일을 많이하며 사용자랑 상호작용을 많이한다.

CPU scheduling은 이 두가지를 고려해서 만들어야 한다.

사용자가 실행시키는 프로그램의 반응이 느리면 사용자는 답답해 할 것이다. 그러므로 CPU bound job에 먼저 cpu를 할당해주어야 한다.

 

다음은 프로세스들이 각각의 Queue에 들어가 CPU를 할당받기를 기다리고 있는 그림을 보여준다. 

• Long-term scheduling은 이제 막 생성된 새로운 프로세스를 Ready Queue로 이동시킨다. 자주 발생하지 않고 가끔 발생하기 때문에 Long-term 이라고 이름이 붙어졌다.
• Ready Queue에 존재하는 프로세스는 CPU를 할당만 받으면 바로 수행할 수 있는 프로세스들이다. short-term scheduling을 통해 다음 프로세스를 선택한다.
• Blocked Queue에 존재하는 프로세스는 I/O가 발생한 프로세스들로 I/O가 끝나기를 기다리고 있다. 여기서 프로세스에 I/O 종료Interrupt가 오면 바로 Ready Queue로 들어간다.
• Blocked, Suspend Queue는 interrupt가 발생하지 않았고 일시중지(예를 들면 Ctrl+Z)된 프로세스들이 존재하는 Queue이다.
• Ready, Suspend Queue는 interrupt가 왔지만 일시중지된 프로세스들이 존재하는 Queue이다.

추가적으로 Medium-term scheduling은 일시중지(suspend)관련 scheduling이며 메모리에서 제거해주는 역할을 한다.(메모리에 올라간 프로세스들만 cpu가 실행시킬 수 있는데 안쓰는 프로세스는 메모리에서 내리는 것이 효율적이기 때문에)

---

CPU Scheduler

Multiprogramming 환경에서 CPU 스케줄링이 꼭 필요하다. 

CPU 스케줄러(scheduler)는 메모리에 올라와 실행할 준비가 된 프로세스(Ready Queue에 있는 프로세스)를 선택하고 그 중 하나에 CPU를 할당한다.

CPU 스케줄링은 프로세스가 다음과 같은 상황일 경우에 발생한다.

1. 프로세스가 running 상태에서 waiting 상태로 전환될때 (예: I/O 요청), 어떤 프로세스가 CPU를 가질지 스케줄링 발생
2. running 상태에서 ready 상태로 전환될때 (예: timeout), 어떤 프로세스가 CPU를 가질지 스케줄링 발생
3. waiting 상태에서 ready상태로 전환될때 (예: I/O 종료 인터럽트), 어떤 프로세스가 CPU를 가질지 스케줄링 발생
4. 한 프로세스가 종료되면, 어떤 프로세스가 CPU를 가질지 스케줄링 발생 

1번과 4번은 CPU 스케줄링이 자연스럽게(nonpreemptive) 발생하며 2번과 3번은 프로세스가 계속 CPU를 쓸 수 있지만 강제적으로(preemptive) 스케줄링이 발생한다.

---

Dispatcher

디스패치(Dispatch)는 short-term scheduler가 선택한 프로세스에 CPU를 제공하는 것이며 디스패처 모듈(Dispatcher module)은 디스패치의 과정을 담당한다. 디스패처 모듈은 다음을 포함하는 일을 한다.

• 컨텍스트 전환하기(Switching context)
• 사용자 모드로 전환하기(Switching to user mode) 
• user program의 적절한 위치로 점프하여 해당 프로그램을 다시 시작하기

Dispatch latency(디스패치 지연)

디스패처가 한 프로세스를 중지하고 다른 프로세스를 시작하는 데 걸리는 시간이다. (대부분 컨텍스트 전환 오버헤드가 크다)

---

Scheduling Criteria(스케줄링하는 기준)

 

CPU utilization(CPU 사용률)

• CPU가 놀지 않도록 해야한다. 최대한 CPU를 최대한 바쁘게 유지

Throughput(처리량)

• 단위 시간당 실행을 끝내는 프로세스 수

Turnaround time(처리 시간)

• 특정 프로세스를 완료하는 데 걸리는 시간. 즉 시작부터 끝나는 시간

Waiting time(대기 시간)

• Ready Queue에서 기다리는 시간의 총합.( I/O발생하고 다시 Ready Queue에 들어가도 시간을 합쳐야 한다. Ready Queue에 존재하는 시간)

Response time(응답 시간)

• (Time-sharing 환경에서) 사용자의 요청이 발생한 후 첫 번째 응답이 생성될 때까지 소요된 시간, 출력이 아님. 예를 들면 사용자가 마우스를 움직여서 커서가 움직일때까지 걸리는 시간

따라서 CPU 스케줄링을 할때의 알고리즘은 CPU utilization(CPU 사용률) 최대, Throughput(처리량) 최대, Turnaround time(처리 시간) 최소, Waiting time(대기 시간) 최소, Response time(응답 시간) 최소로 걸리도록 해야한다.

 

---

Scheduling Algortihm

 

총 일곱 가지가 있으며 차례대로 살펴보도록 하겠다.

• FCFS (First-Come First-Served) : 먼저 들어온 process 부터 CPU를 사용한다.
• SJF (Shortest-Job-First) : 현재 Queue에 존재하는 process 중 사용시간이 가장 짧은 process 부터 CPU를 사용한다.
• SRTF (Shortest-Remaining-Time-First) : Queue 에 남아있는 process 중 사용시간이 가장 짧은 process 부터 CPU를 사용한다.(새로 들어온 process도 scheduling에 고려해주어야 한다)
• Priority Scheduling : 우선순위를 두고 scheduling할 process를 선택한다.
• RR (Round Robin) : 일정 시간(time quantum) 동안 process를 사용하고 시간이 끝나면 다시 scheduling을 한다.
• Multilevel Queue : process를 Queue에 넣을때 Queue를 여러개 두어 scheduling 한다.
• Multilevel Feedback Queue : Queue를 여러개 두고 Queue간에 이동이 가능하게 하여 scheduling 한다.

---

FCFS (First-Come First-Served) Scheduling

 

프로세스는 P1, P2, P3가 존재하고 이 순서대로  Ready Queue에 들어와있다. CPU 실행시간(burst time)은 순서대로 24, 3, 3 이다.

 

다음은 간트 차트(Gantt Chart)이며 FCFS는 CPU를 강제적으로 뺏지 않는다.

출처 : http://ftp.gunadarma.ac.id/linux/docs/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-1/ch14s02.html

Queue에서 프로세스가 기다리는 시간(Waiting time)은 P1: 0, P2 : 24, P3 : 27이고 평균적으로 기다리는 시간은 (0+ 24 + 27) / 3 = 17이다.

 

만약 Queue에 들어온 순서가 P2, P3, P1로 들어왔다면 다음과 같은 간트 차트가 그려진다.

출처 : http://ftp.gunadarma.ac.id/linux/docs/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-1/ch14s02.html

Queue에서 프로세스가 기다리는 시간(Waiting time)은 P1 : 6, P2  : 0, P3 : 3이고 평균적으로 기다리는 시간은 (6 + 0 + 3)/3 = 3이다. 처음의 경우보다 기다리는시간이 훨씬 적다. 

 

따라서 FCFS scheduling이 가지는 문제는 Convoy effect(호위병 효과)이다. 내 앞에 CPU 사용시간이 긴 process가 있으면 짧은 process는 오래 기다릴 수 밖에 없다.

---

Shortest Job First(SJF) Scheduling

CPU는 각 프로세스가 다음 사용하는 CPU 시간의 길이를 알고 가장 짧은 시간을 사용하는 프로세스에게 먼저 할당한다.

SJF 스케줄링은 CPU를 강제로 뺏는지에 대한 기준을 통해 두가지로 나뉠 수 있다.

비강제성(Nonpreemptive)

• CPU가 프로세스에 할당되면 CPU 사용시간이 완료될 때까지 CPU를 뺏을 수 없다.

강제성(Preemptive)

• 현재 프로세스의 CPU 사용시간이 남은 것보다 새 프로세스가 CPU를 사용하는 시간이 더 짧다면 강제로 뺏어 가장 짧은 사용시간 프로세스에게 할당한다. 즉 가장 짧게 남은 프로세스에게 CPU를 할당해준다. 이 방식을 SRTF(Shortest-Remaining-Time-First)라고 한다다.

SJF 알고리즘은 프로세스들이 ready queue에서 대기하는 시간들의 평균, 다시말해 최소 평균 대기 시간(Average waiting time)이 최적이다.(평균 대기시간이 작다)

Non-Preemptive SJF의 예제

출처 : https://www.studytonight.com/operating-system/cpu-scheduling

process들이 ready queue에 2, 3, 0, 1에 들어올 때(0은 이미 존재한다는 의미), SJF 알고리즘이 수행되면 위의 Gantt chart처럼 process들이 실행된다.

시간이 0일 때, P2가 ready queue에 있고 가장 짧은 시간동안 cpu를 사용할 것 이기 때문에 P2를 먼저 cpu에게 할당한다. 

P2가 9의 시간까지 쓰면서 P0, P1, P3가 모두 Ready queue에 들어와있고 여기서 가장 짧은 순서대로 cpu를 할당하게 된다. 

 

Average waiting time은 (0 + 8 + 11 + 18) / 4 = 9.25 이다. (도착한 시간에서 실행되는 시간을 빼주는 것 ex : P1은 21 - 3 = 18)

 

Preemptive SJF의 예제

출처 : https://www.studytonight.com/operating-system/cpu-scheduling

Preemptive SJF는 SRTF(Shortest Remaining Time First) 알고리즘이라고도 불린다. Ready queue에 있는 process들을 계속 체크하면서 CPU burst time이 가장 작은 것 부터 시작한다. CPU를 잡고 process를 수행중이더라도 더 짧은 Burst time이 있으면 CPU를 뺏어 그 process에게 할당한다. 

 

P2가 처음에 CPU를 할당받고 P2의 burst time은 줄어들고 있는 상황이다. 2ms일때(P2의 burst time은 4) P0가 들어오는 데 이 프로세스의 cpu burst time은 3으로 현재 실행중이 process보다 작다. 따라서 cpu를 뺏어 P0에게 할당한다. 

 

이런방식으로 프로세스의 일을 수행한다. 

 

그렇다면 Preemptive, Nonpreemptive SJF 알고리즘을 수행하려면 process가 사용하는 cpu 사용시간을 알아야한다. 하지만 이는 미래의 일을 알고 하는 것이기 때문에 불가능한 알고리즘이다. 따라서 cpu 사용시간을 예측하는 법을 사람들이 제안하였는데 이 부분을 다음 글에서 작성하도록 하겠다.