[운영체제] CPU 스케줄링

CPU 스케줄링

1. 운영체제가 CPU의 자원을 어떤 프로세스에게 할당해 줄 지 그 일정을 짜는 것
2. 일정을 어떻게 짰는지에 따라 CPU의 자원을 얼마나 효율적으로 사용하게 되는지가 결정
3. CPU 스케줄러는 다음 네 가지 상황에서 동작
   • 한 프로세스가 실행상태에서 대기 상태로 전환될 때 ex) I/O 요청에 의한 대기
   • 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 ex) 할당된 시간이 다 끝났을 때 (타이머 인터럽트가 발생했을 때)
   • 프로세스가 대기 상태에서 준비완료 상태로 전환될 때 ex) I/O 종료 시
   • 프로세스가 종료될 때

 

스케줄링 알고리즘

비선점 스케줄링

어떤 프로세스가 CPU를 점유하고 있다면 해당 프로세스의 작업이 완료될 때까지 다른 프로세스는 CPU를 사용할 수 없음.

1. 장점 : 프로세스 일괄 처리에 적합하고 Context Switching을 최소화할 수 있다
2. 단점 : 긴급히 처리되어야 할 프로세스가 처리되지 못할 수 있다
3. 종류
   • FCFS (First Come First Service) : Ready Queue에 도착한 순서대로 CPU에 할당하는 방식. 다른프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 convoy effect (호위 효과) 발생
   • SJF (Shortest Job First) : CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식. 평균 대기시간 가장 짦음. CPU 처리시간이 긴 프로세스는 무한정 기다려야 하는 기아상태 (Starvation) 발생
   • HRN (Highest Reponse Ratio Next) : SJF 에서 기아상태를 해결하기 위해, CPU 처리시간과 대기 시간을 모두 고려하여 결정 ((대기시간 + CPU 처리시간) / CPU 처리시간). 대기시간에 비례하여 우선순위를 높이는 것을 에이징 (Aging) 기법
   • Priority (우선순위) : 운영체제 또는 사용자에 의해 프로세스에 우선순위를 부여. 선점형이거나 비선점형 모두 가능. 기아상태 (Starvation) 발생가능하므로 이를 위해 Aging 기법으로 오래 대기한 프로세스에는 우선순위를 점진적으로 증가시킬 수 있음.

 

선점 스케줄링

어떤 프로세스가 CPU를 점유하고 있을 때 우선순위가 높은 다른 프로세스가 점유를 빼앗아 CPU를 점유할 수 있음.

1. 장점 : 긴급히 처리되어야 할 프로세스를 처리할 수 있다
2. 단점 : Context Switching이 자주 일어날 수 있다
3. 종류
   • SRT (Shortest Remaning Time) : SJF 와 유사하지만 선점 스케줄링 방식으로, 점유 중인 프로세스보다 남은 CPU 처리시간이 짧은 프로세스가 Ready Queue에 들어올 경우 점유할 수 있음
   • RR (Round Robin) : FCFS 와 유사하지만 시간 할당량 (Time Quantum) 개념을 추가. 어떤 프로세스가 CPU를 사용한 시간이 Time Quantum만큼 지나면 이 프로세스로부터 CPU 자원을 회수하고, 이 프로세스를 Ready Queue의 가장 뒤로 보내는 것. Time Quantum 이 너무 크면 FCFS 와 동일하고, 너무 작으면 Context Switching 이 너무 자주 발생함.
   • 다단계 큐 (Multi-Level Queue) : 여러개의 준비 큐를 가지는 스케줄링 방법. 각 큐는 자기만의 스케줄링 알고리즘을 가질 수 있고, 큐와 큐 사이의 스케줄링도 존재. 우선순위 낮은 Queue 의 프로세스는 무한 대기 기아 (Stravation) 상태 가능
   • 다단계 피드백 큐 (Multi-Level Feedback Queue) : 다단계 큐 스케줄링 방식에 에이징 기법을 적용. 우선순위가 낮은 큐에서 너무 오래 기다린 프로세스의 우선순위를 점점 올려서 우선순위가 높은 큐로 옮겨주는 방식

 

 

참고

• https://velog.io/@raejoonee/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%9D%98-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81
• https://velog.io/@mu1616/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81