CPU Scheduling

정의

- 컴퓨터 시스템의 성능을 높이기 위해 자원을 어떤 프로세스에 얼마나 할당할 것인지 정책을 만드는 것이다.

목적

• 처리율 증가
• CPU 이용률 증가
• overhead 최소화
• 응답, 반환 시간 최소화
• 대기 시간 최소화
• 균형 있는 자원의 사용

문맥 교환(Context Switching)

• 정의
  - 하나의 프로세스에서 다른 프로세스로 CPU가 할당되는 과정에서 발생
  - 새로운 프로세스에게 CPU를 할당하기 위해 현재 CPU가 할당된 프로세스의 상태 정보를 저장하고, 새로운 프로세스의 상태 정보를 설정한 후 CPU를 할당하여 실행되도록 하는 작업
  - OS에서 overhead의 발생 요인 중 하나

비선점 스케줄링(Non Preemptive)

• 프로세스에게 이미 할당된 CPU를 강제로 뺏을 수 없고, 사용이 끝날 때까지 기다려야 하는 방법
• 실시간 처리가 안되므로 중요한 작업의 대기시간이 길어지는 경우가 발생
• 모든 프로세스들에 대한 요구를 공정히 처리
• 응답 시간의 예측이 용이
• FIFO(FCFS), SJF, HRN, Priority, Deadline

선점 스케줄링(Preemptive)

• 우선 순위가 높은 프로세스가 이미 할당된 CPU를 강제로 뺏을 수 있는 방법
• 실시간 처리, 대화식 시분할 처리
• 많은 오버헤드를 초래할 수 있음
• RR, SRT, MQ, MFQ

---

FIFO(First-In First-Out / FCFS)

• 준비상태에서 도착한 순서에 따라 CPU 할당
  장 : 공정함
  단 : 우선순위가 높은 프로세스가 오래 대기할 수 있다는 점

SJF(Shortest Job First)

• 실행시간이 가장 짧은 작업을 먼저 수행
  장 : 가장 적은 평균 대기 시간
  단 : 기아현상 발생 (작업 시간이 큰 경우 오랫동안 기다리거나 CPU를 할당 받지 못함)

기아현상 해결 방법
Aging 기법 : 강제로 우선순위를 부여하여 CPU를 할당

• 예시

C가 실행시간이 가장 짧으니 먼저 수행되고, 그 다음은 B, A 순서

0초에는 작업이 A밖에 없으니 A를 수행하고, 그 다음은 B와 C가 있는 C가 실행시간이 더 짧으니 먼저 수행 된다.

HRN(Highest Response Ratio Next)

• SJF의 단점인 긴 작업과 짧은 작업간의 불평등을 보완하는 기법이다.
• 대기 시간과 서비스 시간을 고려하여서 우선순위를 계산 ( (대기 시간 + 서비스 시간) / 서비스 시간 )
  장 : SJF의 단점(긴 작업과 짧은 작업간의 불평등)을 보완
  
  
• 예시

A는 10/5
B는 16/10
C는 22/15
D는 28/8 로 D의 우선순위가 가장 높다.

Priority

• 대기 큐에서 기다리는 각 프로세스마다 우선 순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

Deadline (기한부)

• 일정 시간내에 프로세스를 완료하는 기법
• 제한된 시간안에 프로세스들이 동시에 실행되면 스케줄링이 복잡해지며
  실행 시 집중적으로 요구되는 자원관리에 오버헤드 발생
  
  
  

---

RR(Round Robin)

• FIFO 방식처럼 순서대로 CPU를 할당하지만, 각 프로세스마다 일정한 할당시간 만큼만 서비스
  단 : 만약 할당되는 시간이 작을 경우 문맥교환 및 오버헤드가 자주 발생
  
  
• 만약 할당되는 시간이 클 경우 FIFO 방식과 같아진다.
• 대화식 시분할 시스템을 위해 고안된 방식
  
  
• 예시

A를 5초동안 서비스 해주고 B를 5초동안 C를 5초동안 해주면

A는 3초, B는 2초, C는 1초가 남는다.

다시 A,B,C 각각 5초동안 서비스 해준다.

SRT(Shortest Remaining Time)

• 실행중인 프로세스의 남은 시간과 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법
• SJF 방식이지만 선점형
  
  
• 예시

0초에는 A밖에 없으니 작업 수행

1초에 B가 도착했는데 A보다 실행시간이 짧다. 따라서 B수행
2초에 C가 도착했는데 B보다 실행시간이 짧다. 따라서 C수행

C를 다 수행하고 B와 A중 실행시간이 더 짧은 B 수행

MQ(Multi level Queue)

• 프로세스들을 우선 순위에 따라 시스템, 대화형, 일괄처리 등으로 상위, 중위, 하위 단계의 단계별 준비 큐를 배치하는 방식
• 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용

MFQ(Multi level Feedback Queue)

• 여러 개의 큐를 두어 낮은 단계로 내려갈수록 프로세스의 시간 할당량을 크게 하는 방식
• 적응 기법(시스템이 유동적인 상태 변화에 적절히 반응)의 개념을 적용
• 특정 그룹의 준비상태 큐간 이동할 수 있도록 개선한 기법