• CPU 스케쥴링은 다중 프로그래밍(MultiProgramming)의 기본이다. 스케쥴링을 통해 CPU에서 연산되는 프로세스, 스레드를 교환하면서 컴퓨터를 보다 효율적으로 사용할 수 있다.
• 스레드를 지원하는 운영체제에서 실질적으로 운영체제는 프로세스가 아니라, 커널 수준 스레드를 스케쥴한다.

1. Basic Concept

• 다중 프로그래밍(Multi-programming)은 CPU 이용률을 최대화 하기 위해 다수의 프로세스를 메모리에 유지하며, CPU의 대기 시간을 최대한 없게 한다.
• 다수의 프로세스는 CPU 스케쥴링에 의해 실행된다.

A. CPU-I/O의 Burst Cycle

• 프로세스의 실행은 CPU Burst와 I/O Burst의 사이클로 이루어 지는데 CPU 스케쥴링의 성공은 프로세스들의 위와 같은 성질에 의해 좌우된다.

• 위 그래프는 CPU-Burst의 지속시간과 빈도 수를 나타낸 그래프이다. 짧게 지속되는 Cpu-burst의 빈도가 오래 지속되는 Cpu-Burst 빈도보다 많다.

B. CPU Scheduler와 preemitive Scheduling

• CPU 스케쥴러는 ready queue에 있는 프로세스중에 하나를 선택하여 CPU를 할당한다.
• 선택 절차는 CPU 스케쥴러에 의해 일어나며 큐에 있는 레코드 들은 일반적으로 프로세스들의 PCB이다.

• I/O or event wait을 하거나 exit하여 프로세스의 상태가 변할 경우 프로세스는 CPU를 자발적으로 내놓는다. (non - preemitive)
• 그러나, 이 이외의 경우 프로세스 실행 중 CPU 자원을 뺐어온다. (preemitive)

C. Dispatcher

• 스케쥴러의 기능에 포함된 요소로, 디스패처는 CPU의 제어를 스케쥴러가 선택한 프로세스에게 주는 모듈이다.
• 한 프로세스가 끝나고 다음 프로세스가 실행되기 전까지 걸리는 시간을 Dispatch latency라고 한다.
• 프로세스 실행은 user mode에서 일어나고 스케쥴러에 의한 다음 실행될 프로세스의 선택과 문맥교환 과정을 kernel mode에서 일어난다.

디스패처가 하는 일

1. 문맥 교환; 실행중이던 프로세스를 PCB에 저장후 실행할 프로세스의 PCB를 메모리에서 불러온다.
2. 문맥교환 후 다시 user mode로 전환

2. Scheduling Criteria

• CPU 이용률
• 처리량: 단위 시간당 완료된 프로세스의 개수
• 총 처리 시간: 프로세스의 제출 시간과 완료 시간의 간격
• 대기 시간: 프로세스가 준비완료 큐에서 대기하면서 보낸 시간의 합
• 응답 시간: 사용자와의 대화식 시스템에서 총 처리 시간으로 스케쥴링 하는 것은 최선이 아니다. 사용자는 프로세스와 계속 반응해야하므로 짧게 짧게 반응하는 것이 좋다.

3. Scheduling Algorithm

A. First Time First Go ; 선착순 실행

• CPU를 먼저 요청하는 프로세스가 할당받는 방식
• non-preemitive 방식(인터럽트가 일어나지 않음)
• CPU-burst가 긴 프로세스가 먼저 실행 시 다른 프로세스가 waiting하는 시간이 매우 길어진다.(PROBLEM)

B. Shortest Job First Scheduling; 작업시간 낮은 순으로 실행

• CPU burst시간이 짧은 프로세스대로 실행하는 방식
• SJF는 non-preemitive방식과 preemitive방식으로 나눌 수 있다.
• non - preemitive방식: 한 번 프로세스가 CPU에서 실행되면 끝날때까지 인터럽트 발생하지 않는다.
• preemitive 방식: 어떤 프로세스가 실행중에 새로운 프로세스가 도착했을 경우 실행중이던 프로세스가 종료될때까지 남은 시간보다 새로운 프로세스의 CPU burst의 시간이 짧을 경우 인터럽트가 일어나 문맥교환이 일어난다.
• SJF방식의 한계점은 CPU burst시간의 예측이 어렵다는 것에 있다.

CPU Burst시간의 예측방법

정적인 방법

• 일반적으로 CPU Burst시간은 다음과 같은 프로세스 타입에 따라 예측할 수 있다.
• 커널영역의 OS 프로세스<usermode(interactive<foreground<backgraound)

동적인 방법

• 다음 CPU Burst의 길이가 이전 CPU Burst의 값과 비슷하다고 기대하고 근사값을 계산하여 구하는 것이다.
• “Exponential averaging” 이라고 한다.
  

C. Priority Scheduling; 우선순위

• 우선순위 스케쥴링은 각 프로세스에 우선순위를 연관하여 우선순위가 높은 순서대로 프로세스를 실행하는 알고리즘이다.
• 우선순위는 내부적인 기준과 외부적인 기준으로 정해진다. (내부적 기준: 시간 제한, 메모리 요구, 평균 입출력 버스트 등등)
• 우선순위 스케쥴링은 preemitive하거나 non-preemitive한 경우로 나눌 수 있다. preemitive한 경우 준비완료 큐에 도착한 프로세스의 우선순위가 현재 실행중인 프로세스의 우선순위보다 높을 경우 context - change 가 일어난다.
• 우선순위 스케쥴링 알고리즘에서 우선순위가 낮은 프로세스의 경우 계속해서 실행되지 못하는 starvation의 문제가 일어날 수 있다. 이 경우 시간이 지남에 따라 우선순위를 높이는 aging 기법을 사용하면 해결할 수 있다.

D. Round Robin Scheduling; 제한시간

• 선착순으로 실행(FCFG)하는 방식과 비슷하지만, Time Quantum(시간 할당량)이 지난 후 다음 프로세스로 문맥교환이 일어나는 방식이다.
• 이 방식이 일어날 경우 두가지 상황이 발생할 것이다.
  1. CPU Burst가 단위시간보다 짧은 경우: 이 경우 프로세스는 자발적으로 CPU를 반납 할 것이다.
  2. CPU Burst가 단위시간보다 짧은 경우: 이 경우 프로세스는 인터럽트가 발생해 CPU에서 다른 프로세스로 문맥교환이 일어나고, 실행하던 프로세스는 준비완료 큐의 꼬리에 넣어진다.
• RR방식은 time Quantum의 크기에 매우 영향을 받는다. 시간 할당량이 크다면, FCFG방식과 차이가 없고, 시간 할당량이 작다면 잦은 문맥교환으로 많은 오버헤드가 발생하여 성능 저하가 일어난다.

E. Multilevel Queue Scheduling(다단계 큐 스케쥴링)

• 프로세스별로 특징(ex. foreground, background)에 따라 다른 그룹으로 분류할 수 있는 경우, 이 프로세스 그룹들은 응답시간에 대한 요구사항이 각자 다르기 때문에 서로 다른 스케쥴링 알고리즘을 요구 할 것이다.
• 그래서 준비완료 큐를 하나가 아닌 여러 큐를 만들어서 각 큐마다 우선순위를 만들 어 프로세스의 우선순위 혹은 프로세스 유형과 같은 프로세스의 특성에 따라 한개의 큐에 영구적으로 할당한다.( 1. 시스템 프로세스 → 2. 대화형 프로세스 → 3. 대화형 편집 프로세스 → 4. 일괄처리 프로세스 → 5. 학생 프로세스 순으로 우선순위를 매길 수 있다.)
• 위에서 만들어진 서로다른 큐와 큐를 스케쥴링하는 큐또한 있어야한다. 일반적으로 고정 우선순위의 선점형 스케쥴링으로 구현되어 각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다.

F. Multileve Feedback Queue Scheduling(다단계 피드백 큐 스케쥴링)

• 다단계 큐 스케쥴링 알고리즘에서 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당되어 이동하지 않는다.
• 그러나 다단계 피드백 큐 스케쥴링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.
• 낮은 우선순위 큐에서 오래 대기하는 프로세스는 특정한 시간이 지난 후 높은 우선순위의 큐로 올려준다.
• 낮은 순위의 큐는 높은 순위의 큐가 비어 있을 때만 실행 가능하다.(preemitive)
• 먼저 CPU burst시간에 따라 프로세스를 구분하고 그 프로세스를 Cpu burst 시간을 기준으로 한 준비완료 큐에 넣는다. CPU burst 시간이 짧은 큐에 있는 프로세스가 실행되고 만약 주어진 시간 할당량 안에 프로세스가 끝나지 않는다면, 그 프로세스는 현재 있던 스케쥴링 큐보다 우선순위가 한단계 낮은 스케쥴링 큐의 꼬리로 이동된다.

• 다단계 피드백 큐 스케쥴러는 다음의 매개변수에 의해 정의된다.
  • 큐의 개수
  • 각 큐를 위한 스케쥴링 알고리즘
  • 한 프로세스를 높은 우선순위 큐로 올리는 시간 결정
  • 한 프로세스를 낮은 우선순위 큐로 내리는 시간 할당량 결정
  • 프로세스가 서비스(CPU, 자원..)를 필요로 할때 프로세스가 들어갈 큐를 결정하는 방법

4. Thread Scheduling

• 스레드는 사용자 수준과 커널 수준의 스레드로 구별 할 수 있다.
• 사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고, 커널은 이를 알지 못한다.
• 하지만 결국 CPU상에서 사용자 수준 스레드가 실행되기 위해서는 커널 수준 스레드에 mapping 되어야 한다.
• 이 둘을 지원하는 운영체제에서는 스케쥴되는 대상은 프로세스가 아니라 커널 수준스레드이다.

A. User - level Thread Scheduling

• 사용자 수준 스레드의 스케쥴링은 스레드 라이브러리에 의해 이루어지고 이 과정은 커널이 모른다.
• 다대다 모델, 다대일 모델에서 스레드 라이브러리는 사용자 수준의 스레드를 가용한 LWP(PCB에 의해 컨트롤 되는 하나의 프로세스)상에서 스케쥴링한다. 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁 범위(PCS)로 알려져 있다. 그리고 이 경우 사용자 수준 스레드가 실제 CPU상에서 실행되는 것은 아니다.
• 실제

B. Kernel - level Thread Scheduling

• 사용가능한 CPU로 어떤 커널 스레드를 스케쥴 할 것인지 결정하기 위해서 커널은 시스템 경쟁 범위(SCS)를 사용한다.
• SCS스케쥴링에서의 CPU에 대한 경쟁은 시스템 상의 모든 스레드 상에서 일어난다.