[ 운영체제 ] CPU 스케줄링

[ 출처 ]

혼자 공부하는 컴퓨터 구조 + 운영체제 11강

https://www.youtube.com/watch?v=isj4sZhoxjk

[ CPU 스케줄링 개요 ]

CPU 스케줄링

= 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

 

스케줄링 큐

= 반드시 선입선출 방식을 필요는 없음

 

1. 준비 큐

= CPU를 이용하기 위해 기다리는 큐

= 프로세스가 준비 상태

2. 대기 큐

= 입출력장치를 이용하기 위해 기다리는 큐

= 프로세스가 대기 상태

= 같은 장치를 요구한 프로세스들은 같은 큐에서 대기

 

선점형과 비선점형 스케줄링

1. 선점형 스케줄링

= 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당

= 어느 한 프로세스의 자원 독점을 막고 프로세스들에게 골고루 자원을 배분할 수 있음

= 그만큼 문맥 교환 과정에서 오버헤드 발생

2. 비선점형 스케줄링

= 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스 기다리기

= 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드 적음

= 모든 프로세스가 골고루 자원을 이용하기 어려움

[ CPU 스케줄링 알고리즘 ]

선입 선처리 스케줄링

= FCFS (First Come First Served) 스케줄링

= 단순히 준비 큐에서 삽입된 순서대로 처리하는 비선점 스케줄링

= 프로세스들이 기다리는 시간이 매우 길어질 수 있음 (호위효과)

 

최단 작업 우선 스케줄링

= SJF (Shortest Job First) 스케줄링

= CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링

= 호위효과 방지

 

라운드 로빈 스케줄링

= RR (Round Robin) 스케줄링

= 선입 선처리 스케줄링 + 타임 슬라이스 (time slice, 각 프로세스가 CPU를 사용할 수 있는 정해진 시간)

= 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링

   = 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼 이용

   = 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 (문맥 교환)

 

최소 잔여 시간 우선 스케줄링

= SRT (Shortest Remaining Time) 스케줄링

= 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링

= 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택

 

우선순위 스케줄링

= 프로세스들에게 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행

= 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링

= 우선순위가 높은 프로세스만 주구장창 실행되고 우선순위가 낮은 프로세스는 실행 연기 우려 (기아 현상)

   = 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식으로 방지 (에이징)

 

다단계 큐 스케줄링

= Multilevel queue 스케줄링

= 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

   = 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리

   = 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리

   = 큐 별로 다양한 스케줄링 적용 가능

= 큐 간의 이동 불가

   = 우선순위가 낮은 프로세스는 계속해서 실행 연기 우려 (기아 현상)

 

다단계 피드백 큐 스케줄링

= Multilevel feedback queue 스케줄링

= 큐 간의 이동이 가능한 다단계 큐 스케줄링

= 타임 슬라이스만큼 실행하고 완료하지 못하면 우선순위가 낮은 큐로 이동

   = CPU 집중 프로세스의 우선순위는 상대적으로 낮아짐

   = 입출력 집중 프로세스의 우선순위는 상대적으로 높아짐

= 에이징 기법 적용 가능

 

즉, 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아짐 +

어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식