CPU Scheduling

목적

CPU Scheduling을 이해하기
CPU Scheduling를 사용하는 이유
CPU Scheduling의 종류

CPU Scheduling

• 다중 프로세스 혹은 프로그램 환경에서 CPU를 효율적으로 사용하기 위한 방법
• 이유: CPU는 코어 당 한 가지 일만 처리할 수 있다. 여러 가지의 일을 처리해야할 때, 일을 끝내고 다음 Process를 선택하는 알고리즘을 CPU Scheduling이라 한다.
• 장점:
  • CPU 이용률 최적화 = 전반적 처리량 향상 = 처리시간 최소화
  • 응답 시간 최소화 = 반응성 향상
  • 우선순위 결정 = 시스템 성능 향상

CPU Scheduling 내 Process 상태

1. Runnig: CPU에서 실행되는 상태
2. Ready: Runnig 준비가 된 상태
3. Waiting: I/O 등 실행이 아닌 다른 이벤트를 기다리는 상태
   예) Process 중 로그인이 필요한 경우 Waiting으로 상태를 바꾼 후 다른 Process를 처리

종류

선점형(Preemptive)
일반적으로 Process를 선택할 때는 I/O가 발생하거나 intterupt가 발생할 때, 프로그램이 종료될 때이다. 그러나 섡점형 스케줄링은 위와 같은 상황이 아니어도 다른 Process에 CPU를 강제로 할당한다.

• 장점: 처리 기간이 긴 Process가 CPU를 독점적으로 사용할 때, 이를 다른 Process에 먼저 할당할 수 있다.
• 단점: switching으로 인해 Overhead가 증가할 수 있다.

비선점형(Non-preemtive)
한 Process가 CPU를 점유한 경우 이를 빼앗을 수 없는 형식이다.

• 장점: 필요한 switching만 발생하여 Overhead가 적다.
• 단점: Process 배치가 효율성의 차이를 만든다.

CPU Scheduling 평가(Criteria)

1. CPU Utilization(이용률): 시간당 CPU가 수행되는 비율 -> 높게!
2. Throughtput(처리율): 단위시간당 처리하는 작업의 수 -> 높게!
3. Turnaround Time(반환시간): Process 시작부터 종료 후 자원을 반환하는 시간 -> 짧게!
   • Ready, Runnig, Waiting, I/O 등 모든 시간을 포함
4. Waiting Time(대기시간): Ready Queue에서 CPU 할당을 기다린 시간
   • 다른 대기 시간은 제외
5. Response Time(반응시간): 대화형 시스템에서 사용자가 응답을 받는데 소요되는 시간

CPU Scehduling Algorithms

FCFS(First Come First Served)

• 선입 선출
• 비선점형
• 장점:
  • 작성이 쉽고 간단하다.
• 단점:
  • Convoy Effect가 발생한다. (CPU를 오래 할당하는 Process가 먼저 수행되면 평균 대기 시간이 길어진다)

SJF(Shortest Job First)

• 가장 짧게 수행되는 Process가 우선 수행된다.
• 비선점형 / 선점형
• 장점:
  • 평균 대기 시간이 줄어든다.
• 단점: Process의 CPU 수행 시간을 예측하기 어렵다.

Priority

• 우선 순위 기준(우선 순위는 정수값으로 표현하며 낮을수록 우선도가 높다)
• 비선점형 / 선점형
• 장점:
  • 중요한 Process를 먼저 수행할 수 있다.
• 단점:
  • Starvation이 발생한다. = 우선도가 낮은 Process는 실행되지 않는다.
    이를 보안하기 위해서 Aging을 사용한다. = ready queue에서 기다리는 시간이 길어질수록 우선 순위를 올린다.

RR(Round Robin)

• Process마다 일정 시간(Time Quantum)만 CPU를 할당한다.
• 일반적으로 많이 사용됨.
• 선점형
• 장점:
  • 반응시간이 빨라진다.
• 단점:
  • Time Quantum에 의존적이다. (일반적으로 10 ~ 100 msec)
    • Time Quantum의 크기가 크다면 FCFS와 가까움
    • Time Quantum의 크기가 작다면 Overhead가 엄청나게 증가

Multilevel Queue

• Process의 업무에 따라 Queue를 여러 그룹으로 나눈다.
• Priority처럼 Queue에 우선 순위를 할당할 수 있다. = Starvation이 발생할 수 있다.
• 장점:
  • Queue마다 각자의 알고리즘을 가지고 있다.
• 단점:
  • 각 Queue 사이는 이동할 수 없다.

MFQ(Multilevel Feedback Queue)

• Multilevel Queue를 기본으로 하되, 수행 시간이 오래걸린다면 다음 Queue로 Process를 옮긴다.
• 장점:
  • starvation의 우선순위를 높일 수 있다.