운영체제 5 CPU Scheduling

CPU Scheduler & Dispatcher

CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

Dispatcher
- CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다.
- 이 과정을 context switch(문맥 교환)라고 한다.

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.
1. Running -> Blocked (예: I/O 요청하는 시스템 콜)
2. Running -> Ready (예: 할당시간 만료로 timer interrupt)
3. Blocked -> Ready (예: I/O 완료후 인터럽트)
4. Terminate

• 1, 4에서의 스케줄링은 nonpreemptive(=강제로 빼앗지 않고 자진 반납)
• All other scheduling is preemptive(=강제로 빼앗음)

CPU스케줄링은 현재 ready queue에 들어와있는 CPU를 얻고자 하는 프로세스 중에서 어떤 프로세스에게 CPU를 줄거냐는 메커님즘을 말한다.

CPU Scheduler & Dispatcher

CPU Scheduler

• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

Dispatcher

• CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다.
• 이 과정을 Context Switch(문맥교환)라고 한다.

CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.
1. Running -> Blocked(I/O 요청하는 시스템 콜)
2. Running -> Ready(할당시간 만료로 time interrupt)
3. Blocked -> Ready(I/O완료후 인터럽트)
4. Terminate

비선점형 nonpreemptive(강제로 빼앗지 않음)
선점형 preemptive(강제로 빼앗을 수 있는 경우)

Scheduling Criteria

Performance Index ( = Performance Measure, 성능 척도)

1. CPU utilization(이용률)

• keep the CPU as busy as possible

2. Thoughtput(처리량)

• of processes that complete their execution per time unit

3. Turnaround time(소요시간, 반환시간)

• amount of time to execute a particular process
  CPU를 다쓰고 나갈 때 까지 걸린 시간
  CPU를 기다린 시간 + CPU를 사용한 시간

4. Waiting time(대기 시간)

• amount of time a process has been waiting in the ready queue
  CPU를 기다린 시간

5. Response time(응답 시간)

• amount of time it takes from when a request was submitted until the first response is produced. not output (for time-sharing environment)
  레디큐에 들어와서 처음으로 CPU를 얻기 까지 걸린 시간
  선점형의 경우 얻었다고 끝까지 쓰는게 아님. 쓰다가 뺏기고 쓰다가 뺏김

CPU Scheduling Algorithm

FCFS (First-Come First-Served)

먼저온 순서대로 처리함.

Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting tiem : (0 + 24 + 27)/3 = 17

convoy effect : 큐에서 오래 기다리는 현상

SJF (Shortest-Job-First)

• 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• Two schemes:

Nonpreemptive:

• 일단 CPU를 잡으면 이번 CPU burst가 완료될 때 까지 CPU를 선점(Preemption) 당하지 않음

Preemptive

• 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺴앗김
• 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고 부른다.

• SJF is optimal
  주어진 프로세스들에 대해 minimum average waiting time을 보장

Priority Scheduling

• A priority number(integer) is associated with each process

• highest priority를 가진 프로세스에게 CPU할당 (Smallest integer - highest priority)
  preemptive
  nonpreemptive

• SJF는 일종의 priority scheduling이다.
  *priority = predicted next CPU burst time

• Problem
  Starvation(기이 현상) : low priority process may never execute
  CPU사용시간을 미리 알 수 없다.

• Solution
  *Aging: as time progress increase the priority of the process
  (노화 : 아무리 우선 순위가 낮은 프로세스라도 오래 기다렸으면 우선 순위를 조금씩 높여주자.)

Round Robin (RR)

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
  *일반적으로(10-100 milliseconds)

• 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.

• n 개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
  => 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.

• Performance
  q large => FIFO
  q small => context switch 오버헤드가 커진다.

• 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.

2번째 강의 Multilevel Queue

• Ready queue를 여러 개로 분할
  foreground(interactive)
  background(batch-no human interaction)

• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  foreground-RR
  background-FCFS

• 큐에 대한 스케줄링이 필요
  Fixed priority scheduling
  - serve all from foreground then from background
  - Possibility of starvation
  Time slice
  - 각 큐에 CPU time을 적절한 비율로 할당
  - Eg., 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능
• 에이징(aging)을 이와 같은 방식으로 구현할 수 있다.
• Multilevel-feedback-queue scheduler를 정의하는 파라미터들
  1. Queue의 수
  2. 각 큐의 scheduling algorithm
  3. Process를 상위 큐로 보내는 기준
  4. Process를 하위 큐로 내쫓는 기준
  5. 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

Multiple-Processor Scheduling

• CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
• Homogeneous processor 인 경우
  - Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  - 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
• Loading sharing
  - 일부 프로세서에 job이 올리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  - 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
• Symmetric Multiprocessing(SMP)
  - 각 프로세서가 각자 알아서 스케줄링 결정
  *모든 CPU들이 대등한 관계(각 CPU가 알아서 스케줄링을한다.)
• Asymmetric multiprocessing
  - 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
  *CPU가 여러 개 있는데 그중에 하나의 CPU가 전체적인 컨트롤을 담당함

Real-Time Scheduling

• Hard real-time systems
  - Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야함
• Soft real-time computing
  -Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

Thread Scheduling

• Local Scheduling
  - User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
• Global Scheduling
  - Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation

• Queueing models
  - 확률 분포로 주어지는 arrive rate와 service rate등을 통해 각종 performance index값을 계산
• Implementaion(구현) & Measurement(성능 측정)
  - 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
• Simulation(모의 실험)
  - 알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교