[혼공컴운] 11장. CPU 스케줄링

https://www.almabetter.com/bytes/articles/cpu-scheduling-in-os

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

---

11.3 추가 숙제

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