CPU 스케줄링

CPU 스케줄링 핵심

운영체제의 핵심 기능인 CPU 스케줄링의 개념, 목적, 주요 고려사항 및 다양한 알고리즘을 종합적으로 분석한다. CPU 스케줄링은 다중 프로그래밍 환경에서 여러 프로세스에 CPU 자원을 효율적으로 배분하는 작업으로, 시스템의 전반적인 성능을 결정하는 중요한 요소이다.

스케줄링 방식은 크게 비선점형과 선점형으로 나뉜다. 비선점형 스케줄링은 한 프로세스가 CPU를 점유하면 작업이 끝날 때까지 다른 프로세스가 개입할 수 없는 반면, 선점형 스케줄링은 운영체제가 필요에 따라 실행 중인 프로세스를 중단시키고 다른 프로세스에 CPU를 할당할 수 있다. 대화형 및 시분할 시스템에서는 빠른 응답성을 위해 주로 선점형 방식을 사용한다.

효과적인 스케줄링을 위해서는 프로세스의 우선순위, CPU 집중 프로세스와 입출력 집중 프로세스의 구분, 전면/후면 프로세스 등의 특성을 고려해야 한다. 일반적으로 커널 프로세스, 전면 프로세스, 입출력 집중 프로세스가 더 높은 우선순위를 갖는다.

주요 스케줄링 알고리즘들은 각기 다른 장단점을 가지며, 시스템의 목표에 따라 선택된다.

• 비선점형 알고리즘: FCFS(선입선출)는 간단하지만 처리 시간이 긴 프로세스가 시스템 효율을 저하시키는 '콘보이 효과'가 발생할 수 있다. SJF(최단 작업 우선)는 평균 대기 시간을 최소화하지만, 긴 작업이 무한히 대기하는 '기아 현상'을 유발할 수 있으며, HRN은 이를 보완한다.
• 선점형 알고리즘: 라운드 로빈(RR)은 모든 프로세스에 공평한 CPU 시간을 할당하지만 문맥 교환 오버헤드가 크다. SRT는 SJF의 선점형 버전이며, 다단계 큐(MLQ)와 다단계 피드백 큐(MFQ)는 우선순위를 기반으로 큐를 여러 개 두어 복잡한 스케줄링을 수행하는 고급 기법이다.

이러한 스케줄링은 인터럽트 메커니즘을 통해 효과적으로 관리된다. 인터럽트는 입출력 완료와 같은 이벤트를 CPU에 알리는 신호로, 선점형 스케줄링과 시스템 자원 보호를 위한 이중 모드(커널/사용자) 전환의 핵심적인 역할을 담당한다.

---

1. CPU 스케줄링의 개념과 목적

스케줄링의 정의

CPU 스케줄링이란 프로세스가 생성되어 실행될 때, 운영체제가 시스템의 다양한 자원(특히 CPU)을 특정 프로세스에 할당하는 작업을 의미한다.
이는 여러 프로세스가 동시에 실행되는 다중 프로그래밍 환경에서 CPU와 시스템 자원의 배분을 결정하는 운영체제의 핵심 역할이며,
레스토랑 관리자가 예약, 좌석, 주문, 조리 순서 등을 관리하는 것과 비유할 수 있다.

CPU 스케줄링은 역할에 따라 세 가지 수준으로 나뉜다.

• 고수준 스케줄링 (장기 스케줄링): 어떤 작업을 시스템이 받아들일지 결정하여 시스템 내의 전체 작업 수를 조절한다. 작업 스케줄링이라고도 한다.
• 중간 수준 스케줄링: 시스템 과부하를 막기 위해 일부 활성화된 프로세스를 '중지(suspend)' 상태로 전환하여 전체 활성 프로세스 수를 조절한다.
• 저수준 스케줄링 (단기 스케줄링): 준비 상태에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정한다. 매우 짧은 시간에 빈번하게 발생한다.

스케줄링의 목적

효과적인 CPU 스케줄링은 다음의 목표를 달성하기 위해 설계된다.

목적	설명
공평성	모든 프로세스가 자원을 공평하게 배정받아야 하며, 특정 프로세스가 배제되어서는 안 된다.
효율성	시스템 자원이 유휴 시간 없이 사용되도록 스케줄링하고, 유휴 자원을 사용하려는 프로세스에 우선권을 준다.
안정성	우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정하고, 악의적인 프로세스로부터 시스템 자원을 보호한다.
확장성	시스템의 프로세스 수가 증가해도 안정적으로 작동하도록 조치하며, 자원 증가의 혜택이 시스템에 반영되게 한다.
반응 시간 보장	시스템은 사용자의 요구에 적절한 시간 안에 반응해야 한다.
무한 연기 방지	특정 프로세스의 작업이 무한히 연기되어서는 안 된다.

---

2. 스케줄링 방식의 분류와 주요 고려사항

선점형 스케줄링 vs. 비선점형 스케줄링

CPU 스케줄링 방식은 실행 중인 프로세스의 작업을 중단시킬 수 있는지 여부에 따라 선점형과 비선점형으로 구분된다.

구분	선점형 스케줄링 (Preemptive)	비선점형 스케줄링 (Non-preemptive)
작업 방식	실행 중인 작업을 중단시키고 새로운 작업을 실행할 수 있다.	실행 중인 작업이 완료될 때까지 다른 작업이 불가능하다.
장점	한 프로세스가 CPU를 독점할 수 없어 대화형, 시분할 시스템에 적합하다.	CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.
단점	문맥 교환에 따른 오버헤드가 많다.	CPU 사용 시간이 긴 프로세스 때문에 전체 처리율이 떨어질 수 있다.
주요 사용처	시분할 방식 스케줄링	일괄 작업 방식 스케줄링
중요도	높음	낮음

대부분의 현대 운영체제의 저수준 스케줄러는 빠른 응답 시간을 위해 선점형 방식을 사용한다.

스케줄링 시 주요 고려사항

CPU 스케줄러는 시스템의 효율을 극대화하기 위해 다음과 같은 사항들을 종합적으로 고려하여 우선순위를 결정한다.

• 프로세스 종류: 커널 프로세스는 일반 프로세스보다 높은 우선순위를 가진다.
• CPU 집중 vs. 입출력 집중 프로세스:
  • CPU 집중 프로세스 (CPU-bound): 수학 연산과 같이 CPU를 많이 사용하는 프로세스.
  • 입출력 집중 프로세스 (I/O-bound): 파일 복사와 같이 입출력을 많이 사용하는 프로세스.
  • 입출력 집중 프로세스의 우선순위를 높게 설정하면, 해당 프로세스가 입출력을 위해 대기하는 동안 CPU가 다른 작업을 처리할 수 있어 시스템 전체의 효율이 향상된다.
• 전면 vs. 후면 프로세스:
  • 전면 프로세스 (Foreground): 현재 사용자와 직접 상호작용하는 GUI 화면의 맨 앞 프로세스.
  • 후면 프로세스 (Background): 사용자 입력 없이 백그라운드에서 작동하는 프로세스.
  • 일반적으로 전면 프로세스가 후면 프로세스보다 높은 우선순위를 가진다.

우선순위 요약:

• 높은 우선순위: 커널 프로세스, 전면 프로세스, 대화형 프로세스, 입출력 집중 프로세스
• 낮은 우선순위: 일반 프로세스, 후면 프로세스, 일괄 처리 프로세스, CPU 집중 프로세스

---

3. 다중 큐를 활용한 프로세스 관리

운영체제는 효율적인 프로세스 관리를 위해 상태별로 여러 개의 큐(다중 큐)를 사용한다.

준비 상태의 다중 큐

프로세스들은 우선순위에 따라 각기 다른 준비 큐에 삽입된다. CPU 스케줄러는 가장 높은 우선순위를 가진 큐(일반적으로 0번 큐)의 맨 앞에 있는 프로세스부터 CPU를 할당한다. 우선순위 부여 방식에는 두 가지가 있다.

• 고정 우선순위 방식: 프로세스가 생성될 때 부여받은 우선순위가 끝날 때까지 바뀌지 않는다. 구현은 쉽지만 시스템 환경 변화에 대응하기 어렵다.
• 변동 우선순위 방식: 프로세스 작업 중간에 우선순위가 변경될 수 있다. 구현은 복잡하지만 시스템 효율성을 높일 수 있다.

대기 상태의 다중 큐

입출력 요청으로 대기 상태에 들어간 프로세스들은 요청한 입출력 장치별로 구분된 큐에 배치된다.
이를 통해 시스템은 동일한 장치에 대한 요청을 모아서 처리하여 효율을 높일 수 있다.
대기 큐에서는 여러 프로세스의 작업이 동시에 완료될 수 있으며, 이때 인터럽트 벡터라는 자료구조를 사용하여 여러 인터럽트를 동시에 처리한다.

---

4. 주요 CPU 스케줄링 알고리즘 분석

알고리즘 평가 기준

스케줄링 알고리즘의 성능은 다음 기준으로 평가된다.

• CPU 사용률 (CPU utilization): 전체 시간 중 CPU가 사용된 시간의 비율. 높을수록 좋다.
• 처리량 (Throughput): 단위 시간당 작업을 마친 프로세스의 수. 클수록 좋다.
• 대기 시간 (Waiting time): 프로세스가 준비 큐에서 대기한 시간의 총합. 짧을수록 좋다.
• 응답 시간 (Response time): 첫 번째 반응이 나타나기까지 걸리는 시간. 짧을수록 좋다.
• 반환 시간 (Turnaround time): 프로세스 생성부터 종료까지 걸린 시간 (대기 시간 + 실행 시간). 짧을수록 좋다.

비선점형 알고리즘

1. FCFS (First-Come, First-Served)

• 동작 방식: 준비 큐에 도착한 순서대로 CPU를 할당한다.
• 평가: 구현이 간단하지만, 처리 시간이 긴 프로세스가 먼저 도착하면 다른 모든 프로세스의 대기 시간이 길어지는 **콘보이 효과(convoy effect)**가 발생하여 시스템 효율을 저하시킬 수 있다.

2. SJF (Shortest Job First)

• 동작 방식: 준비 큐에서 실행 시간이 가장 짧은 프로세스에게 CPU를 먼저 할당한다.
• 평가: 평균 대기 시간을 최소화하는 최적의 알고리즘이다. 하지만 실행 시간이 긴 프로세스는 계속해서 순위가 밀려 무한정 대기하는 **기아 현상(starvation)**이 발생할 수 있다. 또한, 운영체제가 프로세스의 종료 시간을 정확히 예측하기 어렵다는 단점이 있다. 기아 현상을 완화하기 위해 에이징(aging) 기법을 사용하기도 한다.

3. HRN (Highest Response Ratio Next)

• 동작 방식: SJF의 기아 현상을 보완하기 위해 만들어졌으며, 우선순위를 (대기 시간 + CPU 사용 시간) / CPU 사용 시간 공식으로 계산하여 값이 가장 높은 프로세스부터 처리한다.
• 평가: 대기 시간이 길어질수록 우선순위가 높아져 기아 현상을 완화하지만, 여전히 공평성이 위배될 수 있어 널리 사용되지는 않는다.

선점형 알고리즘

1. 라운드 로빈 (Round Robin, RR)

   • 동작 방식: FCFS를 선점형으로 변형한 것으로, 각 프로세스는 할당된 시간(타임 슬라이스) 동안만 실행되고, 시간이 만료되면 준비 큐의 맨 뒤로 이동한다.
   • 평가: 시분할 시스템에 적합하며 모든 프로세스에 공평한 기회를 제공한다. 그러나 잦은 문맥 교환으로 인한 오버헤드가 발생할 수 있다.

2. SRT (Shortest Remaining Time)

   • 동작 방식: SJF의 선점형 버전으로, 현재 실행 중인 프로세스의 남은 시간보다 더 짧은 실행 시간을 가진 프로세스가 준비 큐에 도착하면 CPU를 빼앗아 할당한다.
   • 평가: 평균 대기 시간이 짧지만, 남은 시간을 계속 계산해야 하는 오버헤드가 있고 SJF와 마찬가지로 기아 현상이 발생할 수 있다.

3. 다단계 큐 (Multi-Level Queue, MLQ)

   • 동작 방식: 우선순위에 따라 여러 개의 준비 큐를 사용한다. 프로세스는 특정 큐에 영구적으로 할당되며, 각 큐는 독립적인 스케줄링 알고리즘(예: 전면 프로세스 큐는 RR, 후면 프로세스 큐는 FCFS)을 가질 수 있다. 상위 큐의 모든 작업이 끝나야 하위 큐의 작업이 시작된다.
   • 평가: 유연한 스케줄링이 가능하지만, 하위 큐의 프로세스는 기아 현상을 겪을 수 있다.

4. 다단계 피드백 큐 (Multi-Level Feedback Queue, MFQ)

   • 동작 방식: 다단계 큐를 개선한 방식으로, 프로세스가 큐 사이를 이동할 수 있다. 일반적으로 CPU를 한 번 사용한 프로세스는 더 낮은 우선순위의 큐로 이동한다. 우선순위가 낮은 큐일수록 타임 슬라이스 크기를 크게 설정하여 CPU 점유 확률이 낮은 것을 보완한다.
   • 평가: 시스템 변화에 적응력이 높고 기아 현상을 완화할 수 있는 가장 정교한 알고리즘 중 하나이다.

---

5. 인터럽트 처리와 운영체제 모드

인터럽트의 개념 및 종류

인터럽트는 입출력 장치 등의 이벤트 발생을 CPU에 알리는 메커니즘이다. 운영체제가 주기적으로 장치 상태를 확인하는 폴링(polling) 방식과 달리, 이벤트가 발생했을 때만 CPU에 신호를 보내므로 효율적이다.

• 동기적 인터럽트: 현재 실행 중인 명령어 때문에 발생한다. (예: 0으로 나누기, 잘못된 메모리 접근, 사용자의 [Ctrl]+[C] 입력)
• 비동기적 인터럽트: 실행 중인 프로세스와 무관하게 하드웨어 오류나 주변 장치(키보드, 마우스)의 조작으로 발생한다.

인터럽트 처리 과정

1. 인터럽트 발생 시, 현재 실행 중인 프로세스는 일시 정지되고 관련 정보가 저장된다.
2. 인터럽트 컨트롤러가 여러 인터럽트의 처리 순서를 결정한다.
3. 인터럽트 벡터에 등록된 해당 인터럽트 핸들러(처리 루틴)가 실행된다.
4. 인터럽트 처리가 완료되면, 일시 정지되었던 프로세스가 재개되거나 종료된다.

이중 모드 (Dual Mode)

운영체제는 시스템 자원을 보호하기 위해 이중 모드로 동작한다.

• 커널 모드 (Kernel Mode): 운영체제 커널 코드가 실행되는 상태로, 모든 시스템 자원에 접근할 수 있다.
• 사용자 모드 (User Mode): 일반 사용자 프로세스가 실행되는 상태로, 자원 접근이 제한된다.

사용자 프로세스가 입출력과 같은 보호된 자원에 접근하려면 시스템 호출(System Call) 을 통해 운영체제에 서비스를 요청해야 한다.
이 과정에서 사용자 모드에서 커널 모드로 전환이 일어나며, 작업 완료 후 다시 사용자 모드로 복귀한다.
이중 모드는 인터럽트를 기반으로 동작하며, 시스템의 안정성과 보안을 보장하는 핵심적인 메커니즘이다.