CPU 스케줄링 개요

---

CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 하며,
CPU 스케줄링(CPU scheduling) 은 CPU 스케줄러가 하는 모든 작업을 가리킨다.

운영체제는 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하기 위해
CPU 스케줄링(CPU scheduling)을 수행한다.

입출력 집중 프로세스 vs CPU 집중 프로세스

• 입출력 집중 프로세스 (I/O bound process)
  - 입출력 작업이 많은 프로세스
  - 대표적으로 비디오 재생이나 디스크 백업 작업 등을 담당하는 프로세스

• CPU 집중 프로세스 (CPU bound process)
  - CPU 작업이 많은 프로세스
  - 대표적으로 복잡한 수학연산, 컴파일, 그래픽 처리 작업 등을 담당하는 프로세스

  ✔️ 입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU 자원을 요구할 경우 ?

  입출력 집중 프로세스를 먼저 실행하여 입출력 장치를 끊임없이 작동시키고
  해당 프로세스가 입출력 작업을 하며 대기 상태로 존재하는 동안
  CPU 집중 프로세스에 CPU를 집중적으로 할당하는 것이 효율적이다.

  → 일반적으로 입출력 집중 프로세스의 우선순위가 더 높다.

스케줄러의 종류

• 장기 스케줄러(Long-term scheduler) : 어떤 프로세스를 준비 큐에 넣을 것인지 결정

• 중기 스케줄러(Medium-term scheduler, Swapper) : 메모리에 적재된 프로세스 수 관리하여 과부하 예방

• 단기 스케줄러(Short-term scheduler, CPU scheduler) : 메모리 내의 준비 상태에 있는 작업 중 실행할 프로세스를 선택하여 CPU를 할당, 타임 슬라이스 등을 지정하는 가장 핵심적인 역할을 기능을 담당

스케줄링의 목적

• 공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되면 안된다.

• 효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.

• 안정성 : 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.

• 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 해야 한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.

• 반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.

• 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

스케줄링 알고리즘 선택 기준

• CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법

• 처리량 : 단위 시간당 작업을 마친 프로세스의 수

• 대기 시간 : 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간

• 응답 시간 : 프로세스 시작 후 첫번째 출력 또는 반응이 나올 때까지 걸리는 시간

• 반환 시간 : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간

선점형 스케줄링 & 비선점형 스케줄링

---

선점형 스케줄링

프로세스가 CPU를 할당받아 실행 중이더라도
운영체제가 CPU를 강제로 빼앗아 다른 프로세스에게 할당할 수 있는 스케줄링 방식

타이머 인터럽트에 따라 CPU 자원을 뻇어 다음 프로세스에게 전달하는 것도 여기에 포함되며
대부분의 운영체제에서 차용하고 있는 방식이다.

• 장점
  - 프로세스들에게 골고루 자원을 배분할 수 있음
  - 프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합

• 단점
  - 문맥 교환 과정에서 오버헤드 발생

ex) 라운드 로빈(RR), 최소 잔류 시간 우선 스케줄링(SRT), 다단계 큐 ..

비선점형 스케줄링

하나의 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식

• 장점
  - CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적음

• 단점
  - 프로세스가 자원을 골고루 사용 불가
  - 기다리는 프로세스가 많아 처리율이 떨어짐

ex) 선입 선처리 스케줄링(FCFS), 최단 작업 우선 스케줄링(SJF), 우선순위 스케줄링, HRN ..

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

스케줄링 알고리즘

---

선입 선처리 알고리즘 (First Come First Serve, FCFS)

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식

• 모든 프로세스의 우선순위가 동일
• 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 증가

💡 콘보이 효과
처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리게 된다.

최단 작업 우선 스케줄링 (Shortest Job First, SJF)

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식

• 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 그 순서를 바꾸어 실행해서
  FCFS의 콘보이 효과를 완화할 수 있음
• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움

최소 잔류 시간 우선 스케줄링 (Shortest Remaining Time, SRT)

CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 짧은 프로세스부터 우선적으로 선택하는 선점형 방식

• 평균 대기 시간과 평균 응답 시간을 최소화할 수 있어, 시스템의 처리량을 높이고 사용자의 만족도를 향상시킬 수 있음
• 실행 시간이 긴 프로세스는 우선순위에서 계속해서 밀려 무한 대기하는 기아 현상이 발생할 수 있음

→ SJF(최단 작업 우선 스케줄링) + RR(라운드 로빈 스케줄링)

우선순위 스케줄링 (Priority)

프로세스들에게 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행하는 선점/비선점 방식

• 우선순위가 같은 프로세스들은 FCFS 방식 적용
• 우선순위가 낮은 프로세스의 실행이 계속 연기되어 기아 현상 발생 가능

💡 기아 현상 (starvation)
실행시간이 짧은 프로세스가 계속 들어오면 실행시간이 긴 프로세스는 계속 뒤로 밀려
실행 시간이 긴 프로세스의 작업이 무한 연기되는 현상

💡 에이징 (aging)
어떤 자원을 오래 대기할수록 해당 프로세스의 우선순위를 높여주는 방법

라운드 로빈 스케줄링 (Round Robin, RR)

여러 프로세스들을 할당된 시간 (타임 슬라이스) 만큼 돌아가면서 실행하는 선점형 방식

• 선점형 알고리즘 중 가장 단순하고 대표적인 방식
• 작업을 완료하지 못할 경우 준비 큐의 맨 뒤로 가서 자기 차례를 기다림
• 타임슬라이스가 큰 경우 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보임
• 타임 슬라이스가 작은 경우 문맥 교환이 빈번하게 일어나 오버헤드 발생

다단계 큐 스케줄링 (Multilevel Queue Scheduling)

우선순위에 따라 준비 큐를 여러개 사용하는 비선점형 방식

• 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입되어 실행
• 우선 순위가 낮은 프로세스의 작업이 연기되는 문제가 발생

다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

변동 우선순위 알고리즘의 전형적인 예로 CPU를 사용하고 난 프로세스가 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어가는 방식

• 오늘 날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식
• 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화
• 우선순위에 따라 타임 슬라이스의 크기가 다른데, 낮을수록 점점 커지고 마지막 큐는 무한대의 타임 슬라이스를 가짐 (* FCFS 방식)