CPU 스케줄링 — 여러 프로세스에게 CPU를 어떻게 나눠줄까?

About this offer

앞에서 프로세스와 스레드가 무엇인지 알아봤다. 프로그램이 실행되면 프로세스가 되고, 여러 프로세스가 동시에 실행될 수 있다. 그렇다면 한 가지 문제가 생긴다. CPU는 한정되어 있는데, 실행해야 할 프로세스는 여러 개라면 CPU를 누구에게 먼저 줘야 할까? 운영체제는 이 문제를 해결하기 위해 CPU 스케줄링 을 사용한다. CPU 스케줄링은 여러 프로세스 중에서 CPU를 사용할 프로세스를 선택하고, CPU 사용 순서를 결정하는 것 이다. 1. 프로세스마다 우선순위가 다르다 모든 프로세스가 똑같은 중요도를 가지는 것은 아니다. 운영체제는 프로세스의 우선순위 를 고려하여 CPU를 할당한다. 예를 들어 어떤 프로세스는 CPU를 오래 사용해야 하고, 어떤 프로세스는 잠깐 CPU를 사용한 뒤 입출력을 기다려야 할 수도 있다. 프로세스의 특성을 이해하기 위해 크게 두 종류로 나눌 수 있다. CPU 바운드 프로세스 CPU를 많이 사용하는 프로세스다. 예를 들어 복잡한 계산처럼 CPU에서 처리해야 하는 작업이 많은 경우가 이에 해당한다. I/O 바운드 프로세스 입출력 작업을 많이 사용하는 프로세스다. CPU를 사용하다가도 파일 읽기나 입력 등의 입출력 작업을 기다리는 상태가 될 수 있다. 즉, CPU 바운드 → CPU를 사용하는 시간이 상대적으로 김 I/O 바운드 → CPU 사용 후 입출력을 기다리는 경우가 많음 운영체제는 이러한 프로세스들의 특성과 우선순위를 고려하면서 CPU를 배분한다. 2. 프로세스는 어디에서 기다릴까? 실행할 프로세스가 많다고 해서 모든 프로세스가 CPU를 바로 사용할 수 있는 것은 아니다. 프로세스들은 자신의 상태에 따라 여러 큐에서 기다리게 된다. 대표적으로 준비 큐(Ready Queue) 와 대기 큐(Waiting Queue) 가 있다. 준비 큐 CPU를 사용할 준비가 되어 있는 프로세스들이 기다리는 곳이다. 프로세스 A ─┐ 프로세스 B ─┼→ 준비 큐 → CPU 프로세스 C ─┘ CPU 스케줄러는 준비 큐에 있는 프로세스 중 하나를 선택해 CPU를 할당한다. 대기 큐 입출력 작업 등을 기다리는 프로세스가 머무르는 곳이다. CPU ↓ 입출력 요청 ↓ 대기 큐 ↓ 입출력 완료 ↓ 준비 큐 따라서 프로세스는 실행되는 동안 준비 큐와 대기 큐 등을 오가게 된다. 3. 선점형과 비선점형 CPU 스케줄링 방법을 이해할 때 중요한 기준 중 하나가 선점 여부 다. 비선점형 스케줄링 한 프로세스가 CPU를 사용하기 시작하면, 스스로 CPU를 반납할 때까지 다른 프로세스가 강제로 CPU를 빼앗을 수 없는 방식 이다. 프로세스 A ████████████ ↓ CPU 반납 ↓ 프로세스 B ████████ 프로세스가 실행을 끝내거나 대기 상태로 들어가야 다음 프로세스가 CPU를 사용할 수 있다. 선점형 스케줄링 현재 실행 중인 프로세스의 CPU를 다른 프로세스가 강제로 빼앗을 수 있는 방식 이다. 프로세스 A ██████ ↓ 선점 프로세스 B ███████ 예를 들어 더 높은 우선순위의 프로세스가 준비되었다면 현재 실행 중인 프로세스를 멈추고 새로운 프로세스에게 CPU를 할당할 수 있다. 둘의 차이를 정리하면 다음과 같다. 구분 선점형 비선점형 CPU 강제 회수 가능 불가능 프로세스 전환 필요에 따라 가능 CPU 반납 후 전환 응답성 상대적으로 높일 수 있음 상대적으로 낮을 수 있음 특징 여러 프로세스를 빠르게 번갈아 실행 가능 구조가 비교적 단순 4. CPU 스케줄링 알고리즘 CPU를 어떤 순서로 할당할지는 여러 가지 방법으로 결정할 수 있다. 대표적인 CPU 스케줄링 알고리즘에는 다음과 같은 것들이 있다. FCFS SJF Round Robin SRT Priority Scheduling Multilevel Queue Multilevel Feedback Queue 각 알고리즘마다 프로세스를 선택하는 기준이 다르다. 4-1. FCFS — First Come First Served 먼저 온 프로세스부터 처리하는 방식 이다. 말 그대로 먼저 준비 큐에 들어온 프로세스가 먼저 CPU를 사용한다. 준비 큐 A → B → C ↓ A → B → C 은행에서 줄을 선 순서대로 처리하는 것과 비슷하게 생각할 수 있다. 구조가 단순하다는 특징이 있지만, 먼저 실행된 프로세스의 작업이 너무 오래 걸리면 뒤의 프로세스들이 오랫동안 기다릴 수 있다. 4-2. SJF — Shortest Job First 실행 시간이 짧은 프로세스를 먼저 실행하는 방식 이다. A : ██████████ B : ███ C : █████ → B → C → A CPU를 짧게 사용하는 프로세스를 먼저 처리하면 전체적으로 프로세스가 기다리는 시간을 줄이는 데 도움이 될 수 있다. 4-3. Round Robin Round Robin은 일정한 시간만큼씩 CPU를 돌아가면서 사용하는 방식 이다. 이때 각 프로세스에게 할당되는 일정한 시간을 타임 슬라이스(Time Slice) 라고 한다. 예를 들어 타임 슬라이스가 2라면, A → B → C → A → B → C ... 각 프로세스가 CPU를 조금씩 나누어 사용한다. 한 프로세스가 CPU를 계속 독점하지 않도록 하기 때문에 여러 프로세스가 번갈아 실행되는 환경에서 사용할 수 있다. 4-4. SRT — Shortest Remaining Time SRT는 남은 실행 시간이 짧은 프로세스를 우선하는 방식 이다. SJF와 비슷하지만, 현재 실행 중인 프로세스보다 남은 실행 시간이 더 짧은 프로세스가 등장하면 CPU를 넘겨줄 수 있다. 노트에서는 SRT를 SJF와 Round Robin의 특징이 결합된 형태로 정리하고 있다. 4-5. Priority Scheduling 말 그대로 우선순위가 높은 프로세스부터 실행하는 방식 이다. 프로세스 A → 우선순위 3 프로세스 B → 우선순위 1 프로세스 C → 우선순위 2 ↓ B → C → A 우선순위의 기준은 시스템의 목적이나 프로세스의 특성에 따라 정해질 수 있다. 다만 우선순위가 낮은 프로세스가 계속해서 실행되지 못하는 문제가 발생할 수 있다. 5. 여러 개의 큐를 사용하는 방법 프로세스를 하나의 큐에서만 관리하는 것이 아니라 여러 개의 큐로 나누어 관리하는 방법 도 있다. Multilevel Queue 프로세스의 특성이나 우선순위 등에 따라 여러 개의 큐를 만들어 관리하는 방식이다. 예를 들어, 높은 우선순위 ┌──────────────┐ │ 큐 1 │ └──────────────┘ ┌──────────────┐ │ 큐 2 │ └──────────────┘ ┌──────────────┐ │ 큐 3 │ └──────────────┘ 낮은 우선순위 각 큐마다 서로 다른 스케줄링 방식을 사용할 수도 있다. Multilevel Feedback Queue Multilevel Feedback Queue는 여러 개의 큐를 사용하면서 프로세스의 실행 특성에 따라 큐를 이동시킬 수 있는 방식 이다. 프로세스가 CPU를 사용하는 방식에 따라 다른 큐로 이동할 수 있기 때문에 하나의 기준만 사용하는 것보다 유연하게 프로세스를 관리할 수 있다. 노트에서는 Multilevel Feedback Queue를 다양한 스케줄링 상황에 적용할 수 있는 일반적인 형태로 정리하고 있다. 6. CPU 스케줄링을 왜 알아야 할까? 지금까지 살펴본 내용을 하나로 연결해보자. 컴퓨터에서는 여러 프로세스가 동시에 실행되고 있다. 하지만 CPU는 한정된 자원이기 때문에 운영체제가 모든 프로세스에게 CPU를 무작정 나눠줄 수는 없다. 그래서 운영체제는 여러 프로세스 ↓ 준비 큐 ↓ CPU 스케줄러 ↓ 실행할 프로세스 선택 ↓ CPU 할당 과 같은 과정을 통해 CPU를 관리한다. 그리고 어떤 프로세스를 먼저 실행할 것인지 결정하는 방법에 따라 FCFS, SJF, Round Robin, SRT, Priority Scheduling, Multilevel Queue, Multilevel Feedback Queue 등의 알고리즘을 사용할 수 있다. 결국 CPU 스케줄링의 핵심은 한정된 CPU 자원을 여러 프로세스에게 어떻게 배분할 것인가 라고 볼 수 있다. 마무리 이번 글에서는 운영체제가 여러 프로세스에게 CPU를 할당하는 CPU 스케줄링 에 대해 알아봤다. 핵심 내용을 정리하면 다음과 같다. CPU 스케줄링 │ ├─ 프로세스의 우선순위 고려 │ ├─ 준비 큐 / 대기 큐 │ ├─ 선점형 / 비선점형 │ └─ 스케줄링 알고리즘 ├─ FCFS ├─ SJF ├─ Round Robin ├─ SRT ├─ Priority ├─ Multilevel Queue └─ Multilevel Feedback Queue 그런데 여기서 또 하나의 문제가 생긴다. 여러 프로세스가 같은 자원을 사용한다면 어떻게 해야 할까? 여러 프로세스가 동시에 하나의 자원에 접근하면 실행 순서에 따라 결과가 달라지는 문제가 발생할 수 있다. 다음 글에서는 이러한 문제를 해결하기 위한 프로세스 동기화 와 함께 임계 구역, 경쟁 조건, 뮤텍스, 세마포어, 모니터 를 살펴본다.