11. CPU 스케줄링

화장실 줄을 생각해보자.
배운 사람이라면 아무리 급해도 온 순서대로 들어가야 한다.
그런데 정말 급한 사람이 왔다! 곧 나올 것 같다! 더 이상 버틸 수가 없다!
"아 뭐 누군 안 급한줄 아나!"라고 싸움이 나면 그야말로 똥판... 아니 개판이 될 것이다.
그래서 관리자가 필요하다. 관리자의 역할은 누구를 먼저 들여보낼지 정하는 것이다.

프로세스는 CPU를 만나야 본인의 소임을 다할 수 있다.
그런데 대기 줄이 너무 길다!
언제 누구를 먼저 들여보낼지 OS가 결정을 해야 한다.
개중에는 더 급한 프로세스가 있을지도 모른다. 따라서 운영의 묘가 필요하다.
이것을 CPU 스케줄링이라고 부른다.

11.1 CPU 스케줄링 개요

간단하게, 먼저 들어온 것을 먼저 실행시키면 안될까?
그렇게 간단한 문제였으면 책의 한 챕터가 되지도 않았을 것이다.
재밌는 점: 입출력 작업이 많은 프로세스를 먼저 실행하는 것이 효율적이다.
입출력장치는 느린데, 왜 먼저 실행해야 할까?

11.1.1 프로세스 우선순위

잊지 말아야 할 것이 있는데, 키보드와 모니터도 입출력장치이다.
지금 내가 이 글을 쓰고 있는 웹 브라우저를 생각해보자. (코랩에서 쓰고 있다.)
키보드를 두들기면, 입력장치인 키보드의 장치 컨트롤러가 인터럽트를 보낸다.
인터럽트를 (아마도) DMA가 받아서 CPU로 보낸다.
CPU는 명령어를 받아서 웹 브라우저 프로세스에 정보를 보낸다.
웹 브라우저 프로세스는 정보를 받아서 화면에 출력시킨다.
- 마크다운으로 쓰고 있으므로 미리보기도 처리해서 화면에 출력시킨다.
그리고 다시 키보드 입력을 기다린다.
혹시 잘못된 부분이 있다면 친절한 댓글을...
이렇게 입출력장치와 상호작용을 많이 한다.

물론 반대로 CPU를 많이 사용하는 프로세스도 있다.
나의 모국어(...)인 매트랩의 경우, 일단 코드가 돌기 시작하면 그때부터는 CPU를 주로 사용한다.
입출력 작업이 많은 프로세스를 입출력 집중 프로세스(I/O bound process)라고 부른다.
CPU 작업이 많은 프로세스를 CPU 집중 프로세스(CPU bound process)라고 부른다.

입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 대기줄에 들어왔다면?
얼른 입출력 집중 프로세스를 처리해서 던져(?)버리고 CPU 집중 프로세스에 집중해야 한다.
- 1-3장에서 컴퓨터를 사무실에 비유한 적이 있는데, 그 비유에서 입력은 사장 지시, 출력은 사장 보고였다.
- 직원이 아무리 바빠도 사장과의 소통이 최우선이 되어야 한다.
- 사장 지시가 왔다면 얼른 처리해서 던져(??)버려야 한다.
- 사장은 인내심이 없기 때문이다.
입출력 집중 프로세스는 다시 입출력을 대기할 것이기 때문이다.
- 사장의 지시사항을 기다리는 것처럼...
따라서 프로세스마다 우선순위(priority)를 주어야 한다.
우선순위는 PCB에 저장된다.

11.1.2 스케줄링 큐

그런데 OS가 매번 PCB를 뒤져가며 우선순위가 높은 것을 찾을 수는 없다.
그래서 미리 프로세스들의 줄을 세워둔다.
이것을 스케줄링 큐(scheduling queue)라고 부른다.
스케줄링 큐에는 여러 가지가 있는데, 대표적으로 준비 큐(ready queue)와 대기 큐(waiting queue)가 있다.
준비 큐는 CPU를 기다리는 큐이고, 대기 큐는 입출력장치를 기다리는 큐이다.

출처: https://byjus.com/gate/process-scheduling-in-operating-system-notes/

OS는 준비 큐의 프로세스들을 하나씩 꺼내서 실행하는데, 우선순위가 높은 것을 먼저 꺼낸다.
그래서 3장에서 봤던 선입선출의 큐와는 조금 다르다.

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

다시 화장실 줄을 생각해보자.
다들 적당히(?) 급한 상황에서 줄을 서서 기다리는데, 정말 당장 터질 것 같은 사람이 왔다.
지금 진행(...) 중인 사람을 꺼낼까? 그래도 한 자리 날 때까지는 기다릴까?

현재 실행 중인 프로세스를 뺏어서 새로 들어온 프로세스를 집어넣는 것을 선점형 스케줄링(preemtive scheduling)이라고 부른다.
반대로 현재 실행 중인 프로세스가 끝나야 새로 들어온 프로세스를 집어넣는 것을 비선점형(non-preemtive scheduling)이라고 부른다.
선점형 스케줄링
- 장점: 자원을 골고루 배분할 수 있다.
- 단점: 문맥 스위칭 과정에서 오버헤드 발생!
비선점형 스케줄링
- 장점: 문맥 스위칭 오버헤드가 적다.
- 단점: 아 급하다고! 나온다고!

11.2 CPU 스케줄링 알고리즘

CPU의 스케줄링도 알고리즘이 있다.
다음과 같은 상황을 생각해보자.
화장실은 좀 더러우니까, 공중전화를 대기 줄을 생각해보자. (옛날엔 그런게 있었단다.)

출처: https://www.hankyung.com/article/202210277471i

10명이 공중전화에 도착했다. 각자 통화할 시간을 대충 미리 알고 있다.
다음 중 어떤 방법이 가장 공정한가?
- 방법 1: 도착한 순서대로 들어간다.
- 방법 2: 통화 시간이 짧은 사람부터 들어간다. (아들이 아빠에게 거는 전화일 것이다.)
- 방법 3: 사람마다 1회 최대 30초를 준다. 30초를 넘어가면 줄 맨 뒤로 돌아간다. (전화 요금은 걱정 ㄴㄴ.)
- 방법 4: 방법 3으로 하되, 남은 통화 시간이 가장 짧은 사람부터 들어간다.
- 방법 5: 중요한 통화인 사람부터 들어간다.
- 방법 6: 10명을 통화 중요도 기준으로 세 그룹으로 나눈다. 중요도가 높은 그룹부터 들어간다. 그룹마다 위에서 나온 방식들을 다르게 적용할 수 있다.
- 방법 7: 10명을 통화 중요도 기준으로 나누되, 통화가 예상보다 길어지면 낮은 중요도 그룹으로 옮긴다. 너무 오래 기다린다 싶으면 다시 높은 중요도 그룹으로 옮긴다.
정답은 없다. 각 경우의 맥락과 장단점이 있을 뿐이다.

이제 실제 CPU의 스케줄링 알고리즘을 하나하나 간단히 설명해보자.
1. 선입 선처리 스케줄링 (FCFS; First Come First Served)
- 먼저 도착한 프로세스부터 실행한다.
- 금방 끝나는 프로세스가 앞에 오래 걸리는 프로세스가 있다면 비효율적이다.
1. 최단 작업 우선 스케줄링 (SJF; Shortest Job First)
- 준비 큐에 있는 것들 중 실행시간이 짧은 것부터 실행한다.
1. 라운드 로빈 스케줄링 (Round Robin Scheduling)
- 각 프로세스가 정해진 시간만큼만 실행되고, 그 안에 안 끝나면 맨 뒤로 다시 들어간다.
- 이 정해진 시간을 타임 슬라이스라고 부른다.
- 적절한 타임 슬라이스의 설정이 중요하다
1. 최소 잔여 시간 우선 스케줄링 (SRT; Shortest Remaining Time)
- 라운드 로빈처럼 타임 슬라이스 기준으로 각 프로세스를 실행한다.
- 그렇다면 매번 최소 잔여시간 프로세스가 다를 수 있다.
- 최소 잔여시간 프로세스를 먼저 실행하는 것이 이 방법이다.
1. 우선순위 스케줄링
- 프로세스의 우선순위 기준으로 먼저 실행시킨다.
- 다만 준비 큐에 늘 새로운 프로세스가 들어올 수 있으므로, 우선순위가 낮은 프로세스는 무한정 기다리게 될 수도 있다. 이것을 기아(starvation) 현상이라고 부른다.
- 그 경우 우선순위를 조금씩 높이는 방식을 적용해볼 수 있다.
1. 다단계 큐 스케줄링 (multilevel queue)
- 우선순위별로 준비 큐를 여러 개 만들어서 프로세스를 분류한다.
- 우선순위가 높은 준비 큐부터 순서대로 실행한다.
- 준비 큐마다 타임 슬라이스도 다르게 할 수 있고, 어디는 선입 선처리, 어디는 라운드 로빈으로 할 수도 있다.
1. 다단계 피드백 큐 스케줄링 (multilevel feedback queue)
- 다단계 큐처럼 준비 큐를 여러 만들고 프로세스를 분류하는 것까지는 똑같다.
- 다만 각 프로세스는 타임 슬라이스만큼 실행되고, 그 안에 안 끝나면 낮은 우선순위 큐로 들어간다.
- 너무 오래 기다린다 싶으면 우선순위를 올린다.

11.3 추가 숙제

준비 큐에 프로세스 A, B, C, D 순으로 삽입되었다.
선입 선처리 스케줄링을 적용하면 어떤 순서대로 실행되는가?
답: First Come이 First Served이므로 A -> B -> C -> D 순으로 실행된다.

저작자표시 비영리 변경금지