CPU Scheduling

이 글은 KOCW 강좌 중 경성대학교 양희재 교수님의 '운영체제' 강의를 정리한 글입니다.

 

CPU Scheduling

CPU Scheduling

Main Memory에 여러 가지 Process가 Load 돼서 CPU는 다수의 Process를 처리해야 한다.

효율적인 처리를 위해 어떤 Process를 먼저 처리할지 계획하는 것을 CPU Scheduling이라 한다.

Scheduling 방식을 크게 2가지로 나눌 수 있다.

• Preemptive
  • Process가 CPU를 사용하고 있는 중에도 다른 Process가 강제로 점유할 수 있는 상태
• Non-Preemptive
  • I/O나 Interrupt를 제외하고 Process가 CPU를 사용하고 있으면 끝날 때까지 다른 Process가 점유할 수 없는 상태

CPU Scheduling 얼마나 효율적인지 기준은 아래와 같다.

• CPU Utilization(CPU 이용률) -> CPU 사용 가동률
• Throughput(처리율) -> 단위 시간당 처리하는 Job 수(Process)
• Turnaround Time(반환시간) -> Ready Queue에 들어오고 모든 작업 끝내고 Process가 종료하는 데 걸린 시간
• Waiting Time(대기시간) -> Ready Queue에서 대기하는 시간
• Response Time(응답 시간) -> Interactive System에서 Input에 대한 반응 걸리는 시간

FCFS

First-Come, First-Served

FCFS는 가장 먼저 온 Process를 처리하는 방식이다.

매우 간단하고 공정한 방식이다.

Non-Preemptive Scheduling으로 순서대로 처리하면서 Process가 끝나고 다음 Process를 처리된다.

큰 Process가 CPU를 오래 사용하는 동안 나머지 Process가 기다리는 것을 Convoy Effort라고 한다.

FCFS는 Convoy Effort가 발생한다.

SJF

Shortest-Job-First

SJF는 가장 짧게 수행되는 Process를 먼저 처리하는 방식이다.

가장 효율적인 방식이지만 매우 비현실적인 방식이다.

실질적으로 Process의 CPU 점유시간이 얼마나 될지 알 수가 없다.

알려면 실제로 수행하여 측정해야 한다.

측정한 시간으로 예측할 수 있지만 Overhead가 부담이 커서 하지는 않는다.

Preemptive, Non-Preemptive Scheduling 모두 가능하다.

Priority

Priority Scheduling은 우선순위가 높은 Process를 먼저 처리하는 방식이다.

운영체제에서 보통 Integer Number로 우선순위를 정하며 낮은 숫자가 우선순위가 높다.

Preemptive, Non-Preemptive Scheduling 모두 가능하다.

우선순위를 정하는 요인은 아래와 같다.

• Internal
  • time limit, memory requirement, i/o to CPU burst,...
• External
  • amount of funds being paid, political factors,...

Priority Scheduling은 starvation 문제가 생길 수 있다.

starvation은 우선순위가 높은 Process가 계속 들어오면 순위가 낮은 Process가 CPU 점유를 못하는 것을 말한다.

해결하기 위한 방법으로 Ready Queue에 오래 머문 Process일수록 우선순위를 높이는 againg이 있다.

Round-Robin

Round Robin Scheduling은 일정 시간 동안 다수의 Process를 번갈아가며 처리하는 방식이다.

Time-sharing System에서 진행하는 Scheduling 방식이다.

위에서 말한 일정 시간을 Time quantum이나 Time slice라고 한다.

Preemptive 방식이다.

Time quantum이 굉장히 중요한 Scheduling 방식이다.

만약 Time quantum이 무제한으로 하면 FCFS 방식,

Time quatum이 0이면 Context Switching이 빈번하게 발생해 Overhead가 발생할 수 있다.

Multilevel Queue Scheduling

Process Group에 따라 Queue를 사용해 Scheduling을 하는 방식이다.

각각의 Queue마다 절대적 우선순위가 존재한다.

각 Queue는 독립적인 Schedulig 정책을 가지고 있다.

Process Group은 아래와 같이 나눌 수 있다.

• System Processes
• Interactive Processes
• Interactive editing Processes
• Batch Processes
• Student Processes

Multilevel Feedback Queue Scheduling

Multileve Queue처럼 복수 개의 Queue를 가지고 있다.

대신 Process가 1개의 Queue에서만 있는 것이 아니라 Queue를 움직인다.

CPU 사용을 너무 오래 하면 다른 Queue로 이동한다.

starvation 우려 시 우선순위가 높은 Queue로 이동한다.