CPU 스케줄링

• 워크로드(workload) : 프로세스가 동작하는 일련의 행위

• 스케줄링 평가 항목

  • 반환 시간(성능 측면에서의 평가 기준)
  • 공정성

스케줄링에서 성능과 공정성은 상충된다. (전체 시스템의 성능 극대화를 위해 몇몇 프로세스에게 실행 기회를 주지 않을 수 있고 공정성이 악화된다.)

• 응답 시간 : 프로세스가 생성된 시점부터 처음으로 스케줄 될 때까지의 시간

---

1. CPU 스케줄링
   • 운영체제가 CPU 자원을 여러 프로세스(작업)에게 어떻게 할당할지 결정하는 방법
   • 하나의 프로세스는 하나의 CPU(싱글 코어)가 필요하기 때문에, 프로세스 수만큼 CPU가 존재하는 것이 가장 이상적. 하지만, 현실적으로 불가능하기 때문에 실행 중인 모든 프로세스들에게 골고루 CPU를 할당하는 일이 필요
2. CPU 스케줄링의 목표
   1. CPU 이용률 최대화 : CPU가 쉬지 않도록 항상 바쁘게 만드는 것
   2. 처리량 최대화 : 단위 시간당 완료되는 작업의 수를 늘리는 것
   3. 대기 시간 최소화 : 프로세스가 실행되기 위해 기다리는 시간을 줄이는 것
   4. 응답 시간 최소화 : 대화형(interactive) 작업의 경우 요청에 대한 응답을 빠르게 제공하는 것

---

1. 선점형(Preemptive) vs 비선점형(Non-preemptive)
   • 선점형 : 한 프로세스가 CPU를 사용하고 있을 때, 우선순위가 높은 다른 프로세스가 나타나면 CPU를 강제로 빼앗아 올 수 있는 방식.
   • 비선점형 : 한 프로세스가 CPU를 할당받으면 스스로 종료되거나 대기 상태로 전환될 때까지 CPU를 빼앗기지 않는 방식. 현재 프로세스가 명시적으로 CPU를 양보하거나 I/O 작업 등으로 블로킹 상태에 놓일 때까지 기다려야 함.
     

대부분 현대 운영체제는 유연성이 뛰어난 선점형 방식 사용

1. CPU 스케줄링 알고리즘 분류
   • 비선점형
     1. FCFS(First-Come, First-Served) : 먼저 온 프로세스가 먼저 처리되는 방식
     2. SJF(Shortest-Job-First) : 실행 시간이 가장 짧은 프로세스부터 먼저 처리하는 방식
   • 선점형
     1. SRTF(Shortest-Remaining-Time-First) : SJF의 선점형 버전. 남은 시간이 가장 짧은 프로세스 먼저 실행
     2. 라운드 로빈(Round-Robin) : 각 프로세스에게 동일한 시간(타임 슬라이스)을 할당하고, 시간이 지나면 다음 프로세스로 넘어가는 방식
     3. 다단계 큐(Multilevel Queue) : 프로세스를 여러 큐로 나누어 각 큐마다 다른 스케줄링 알고리즘을 적용하는 방식

우선순위 스케줄링 : 우선순위가 가장 높은 프로세스부터 처리하는 방식 (낮은 숫자가 높은 우선순위일 수 있음)

구현 방식에 따라 비선점, 선점으로 구현될 수 있음.

---

1. FCFS(선 도착, 선 처리, First-Come, First-Served) or FIFO(선입선출, First In First Out)
   • 단순하고 구현하기 쉬우며 먼저 도착한 프로세스부터 처리하므로 프로세스들의 반환 시간이 일정한 경우 좋은 성능을 보인다.
   • 하지만, 프로세스들의 반환 시간이 일정하지 않기 때문에 만일 먼저 도착한 프로세스의 반환 시간이 다른 프로세스들의 반환 시간보다 긴 경우, 끝나기를 기다려야 해 좋지 않은 성능을 보인다.
   • Convey effect : 반환 시간이 짧은 프로세스들이 반환 시간이 긴 프로세스가 끝나기를 기다려야 하는 현상
2. SJF(최단 작업 우선, Shortest Job First)
   • 가장 짧은 실행 시간을 가진 프로세스부터 처리한다.
   • 모든 프로세스들이 거의 동일한 시간에 도착한다면 FCFS의 Convey effect를 발생시키지 않는 등 최적의 스케줄링 알고리즘이지만 프로세스들의 도착 시간은 모두 다르다.
   • 반환 시간이 긴 프로세스 A를 실행 중에 비교적 짧은 프로세스 B, C가 도착했다면 프로세스 A가 끝날 때까지 기다려야 하는 Convey effect가 동일하게 발생한다.
3. SRTF(최단 잔여시간 우선, Shortest-Remaining-Time-First) = STCF(Shortest Time-to-Completion First)
   • SJF에 선점 기능을 추가한 스케줄링 알고리즘
   • 새로운 프로세스 생성 시, 현재 실행 중인 프로세스의 남은 반환 시간과 새로운 프로세스의 반환 시간을 비교해 가장 짧은 프로세스를 실행시킨다. 만일 기존 프로세스가 더 길었다면 프로세스를 중지(Blocked) 상태로 만들고 이후에 다시 실행시킨다.
   • 프로세스의 반환 시간을 미리 알고 있고, I/O 작업 등의 작업이 없이 오직 CPU만 사용하며, 반환 시간만 생각한다면 높은 성능을 보장하는 알고리즘
   • 그러나 응답 시간과 프로그래머와 상호작용 측면에서는 매우 낮은 성능을 보인다.

---

• 기아(Starvation) 상태 : 특정 프로세스가 필요한 자원을 영원히 할당받지 못하고 무기한으로 대기하는 상황

• 우선순위 스케줄링 : 각각의 프로세스마다 우선순위를 부여해 우선순위가 높은 프로세스 먼저 실행시키는 방식

  우선순위가 높은 프로세스의 작업이 마쳐져야 그 다음 우선순위의 프로세스가 실행되기 때문에 상황에 따라 낮은 우선순위 프로세스가 기아상태에 빠질 수도 있다.

  다만, 높은 우선순위 프로세스가 I/O 관련 작업 등과 같은 일이 발생하면 낮은 우선순위 프로세스가 실행 기회를 얻을 수도 있다. 따라서, 낮은 우선순위 프로세스가 기아 상태에 빠지는 일은 드물다.
  

• 라운드 로빈(Round-Robin) : 우선순위가 같은 프로세스들간의 형평성을 위해 정해진 시간 간격만큼만 실행하고 다른 프로세스에게 CPU의 할당을 넘기는 방식

  • 퀀텀(Quantum) or 타임 슬라이스(Time Slice) : 실행의 최소 단위 시간 간격. 타이머 인터럽트 주기의 배수로 설정해야 한다.

    타임 슬라이스를 길게 하면 마우스로 드래그앤 드롭을 할 때 반응이 늦게 나타나는 일 등이 발생한다.

    타임 슬라이스를 짧게 하면 컨텍스트 스위칭이 자주 발생해 성능 저하를 일으킨다.

    반환 시간은 작업 완료 시간만 고려하기 때문에 반환 시간 측면에서 최악의 알고리즘

---

1. 스케줄링 알고리즘에 의해 스케줄링이 진행되는 시점
   • 라운드 로빈 알고리즘 적용 시, 정해진 시간이 지나면 다음 프로세스에게 실행 순서를 넘겨야 한다. 이를 위해 스케줄러가 동작해야 하므로 프로세스의 실행시간 간격에 해당하는 매 타임 슬라이스마다 스케줄링이 진행되어야 한다.
   • 우선순위 스케줄링 알고리즘 적용 시, 우선순위가 높은 프로세스는 무조건 먼저 실행되어야 하기 때문에 새로운 프로세스가 생성될 때 스케줄링이 진행되어야 한다. 반대로 현재 실행 중인 프로세스가 종료될 때, 다른 프로세스를 실행시켜야 하기 때문에 스케줄링이 진행되어야 한다.
   • 현재 실행 중인 프로세스가 블로킹 상태가 되면 다른 프로세스가 대신 실행되어야 하고 실행될 다른 프로세스를 선정하기 위해 스케줄링이 진행되어야 한다.

요약

1. 매 타임 슬라이스마다 스케줄링
2. 프로세스 생성 및 소멸될 때마다 스케줄링
3. 현재 실행 중인 프로세스가 블로킹 상태에 놓일 때마다 스케줄링

---

1. 우선순위 역전(Priority Inversion) : 프로세스의 우선순위가 뒤바뀌는 현상

예를 들어, 다음과 같은 우선순위를 가진 프로세스들이 있다면

프로세스 A > 프로세스 B > 프로세스 C

우선순위 스케줄링에 의해 프로세스 A가 실행되다가 IPC로 연결되어 있는 프로세스 C의 결과 값이 필요해졌다.

프로세스 A는 프로세스 C가 실행될 수 있도록 Blocked 상태에 들어간다.

프로세스 B는 우선순위가 높은 프로세스 A가 블로킹 상태가 되자 다음으로 높기 때문에 CPU를 할당받는다.

프로세스 A는 프로세스 B보다 우선순위가 높음에도 불구하고 프로세스 B보다 우선순위가 낮은 것처럼 동작한다.

예는 IPC로 들었지만, IPC 때문에 발생하는 것이 아닌 공유 자원 때문에 발생한다.

우선순위가 낮은 프로세스가 공유 자원을 점거한 상태에서 우선순위가 높은 프로세스가 동일한 자원을 요청할 때 우선순위 역전이 발생한다.

위 문제의 해결 방법으로는 프로세스 A가 블로킹 상태가 될 때, 프로세스 C에게 자신의 우선순위를 잠시 위임하면 프로세스 B는 자신보다 우선순위가 높아진 프로세스 C에게 밀려 CPU를 할당받지 못하게 된다.

운영체제별로 다양한 우선순위 역전 케이스들이 존재하고 해결하는 방법도 다양하다. 직접 해결해주거나 시스템 함수를 제공해 해결될 수 있도록 한다. 아무런 지원을 해주지 않는 운영체제도 존재한다.

우선순위 역전의 문제는 프로세스 간에만 일어나는 것이 아니라 쓰레드 간에서도 발생할 수 있다.