[OS] CPU 스케줄링 알고리즘 (CPU Scheduling Algorithm)

선점형 스케줄링

Round Robin (RR) 스케줄링

• 설계 방침 : 모든 프로세스에게 공편한 실행 기회를 주기 위해 일정 시간 간격으로 프로세스들을 번갈아 실행시킨다.
• 알고리즘 : 큐에 대기중인 프로세스들을 타임 슬라이스 주기로 돌아가면서 선택하는 방법이다. 도착하는 프로세스들은 큐의 끝에 삽입되며, RR은 준비 리스트의 맨 앞에 있는 프로세스를 선택한다.
• 성능과 문제점 : RR은 공정하고, 기아 현상이 없으며, 구현이 쉽다는 장점이 있다. 하지만 잦은 스케줄링으로 인해 스케줄링 때마다 소요되는 컨텍스트 스위칭 오버헤드가 크다는 단점이 있다.

 

프로세스도착 시간실행 시간(예상 값)

P1	0	4
P2	1	3
P3	2	1
P4	5	3

 

 

SRTF (Shortest Remaining Time First)

• 설계 방침 : 새로운 프로세스가 큐에 도착하는 시점에서, 현재 실행 중인 프로세스의 남은 실행 시간보다 도착한 프로세스의 예상 실행 시간이 더 짧은 경우, 현재 프로세스를 중단시키고 새로 도착한 프로세스를 실행시키자는 의도이다.
• 알고리즘 : 큐에서 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행시킨다. 실행 중인 프로세스의 남은 실행 시간보다 더 짧은 프로세스가 큐에 도착하면 실행을 중단하고 도착한 프로세스를 실행시킨다.
• 성능과 문제점 : 가장 짧은 프로세스를 먼저 실행하므로, 프로세스들의 평균 대기 시간은 최소화된다. 하지만 현실에서는 프로세스의 실행 시간을 예상 할 수 없기 때문에 거의 사용되지 않는다.

 

프로세스도착 시간실행 시간(예상 값)

P1	0	4
P2	1	3
P3	2	1
P4	5	3

 

 

Priority Scheduling (Fixed Priority Preemptive Scheduling)

• 설계 방침 : 프로세스에 우선 순위를 두는 컴퓨터 시스템에서 철저히 우선 순위에 따라 프로세스를 실행시킨다.
• 알고리즘: 큐에서 가장 높은 우선 순위의 프로세스를 먼저 스케줄링한다. 실행 중인 프로세스가 종료하거나 더 높은 순위의 프로세스가 도착할 때, 스케줄링을 다시 시행한다. 프로세스마다 우선 순위가 할당되며 종료할 때까지 바뀌지 않는다.
• 성능과 특징 : 순위가 높은 프로세스일수록 대기 시간이나 응답 시간이 짧다.

 

비선점 스케줄링

FCFS (First Come First Served)

• 설계 방침 : 큐에 도착한 순서대로 프로세스를 실행시켜, 매우 단순하고 구현하기 쉽도록 하는데 착안되었다.
• 알고리즘 : 큐에 먼저 도착한 프로세스를 먼저 스케줄링한다.
• 성능과 문제점 : 기아는 발생하지 않지만 일반적으로 처리율이 낮다.

 

프로세스도착 시간실행 시간

P1	0	4
P2	1	3
P3	2	1
P4	5	3

 

 

SJF (Shortest Job First)

• 설계 방침 : 실행시간이 가장 짧은 프로세스를 먼저 실행시켜 프로세스들이 평균 대기 시간을 최소화 하는데 목표가 있다.
• 알고리즘 : 큐에서 실행 시간이 가장 짧은 프로세스를 선택한다.
• 성능과 문제점 : 긴 프로세스보다 짧은 프로세스를 먼저 실행하면 그 뒤에 대기 중인 모든 프로세스의 대기 시간이 짧아진다. SJF는 가장 짧은 프로세스를 먼저 실행하므로, 평균 대기 시간은 최소화 된다. 하지만 SJF는 현실에서 사용할 수 없다. 실제 프로세스의 실행 시간을 예상할 수 없기 때문이다.

 

프로세스도착 시간실행 시간(예상 값)

P1	0	4
P2	1	3
P3	2	1
P4	5	3

 

 

선점 / 비선점 스케줄링

MLQ (Multi-level Queue)

• 설계 방침 : 프로세스들을 n개의 우선 선위 레벨로 구분하여 레벨이 높은 프로세스들을 우선적으로 처리하고자 하는 목적으로 설계되었다.
• 알고리즘 : 컴퓨터 시스템에 n개의 우선 순위를 두고 우선 순위별로 하나씩 큐를 두며, 프로세스 역시 우선 순위를 가진다. 프로세스가 도착하면 우선 순위에 따라 큐에 삽입된다. 스케줄러는 가장 높은 순위의 큐에서 맨 앞에 있는 프로세스를 선택한다. 가장 높은 순위의 큐가 비어 있으면, 그 다음 순위의 큐에서 프로세스를 선택한다.
• 선점 / 비선점
  • 선점 : 프로세스의 실행 중에 더 높은 순위의 큐에 프로세스가 도착하면 실행을 중단하고 새로 도착한 프로세스를 스케줄 하면 선점 스케줄링이 된다.
  • 비선점: 실행중인 프로세스가 실행을 끝냈을 때 스케줄링 하도록 구현하면 비전섬 스케줄링이 된다.
• 성능과 특징 : 높은 순위를 가진 프로세스들의 대기 시간이나 응답 시간이 짧은 장점이 잇다. 하지만 낮은 레벨의 큐에 잇는 프로세스가 높은 레벨의 큐로 이동할 수 없어 지속적으로 높은 레벨의 프로세스가 도착하면 기아가 발생한다.

 

 

MLFQ (Multi-level Feedback Queue)

• 설계 방침 : 여러 레벨의 큐 사이에 프로세스들이 이동할 수 있게 함으로써, 짧은 프로세스나 CPU 사용량이 비교적 적고 I/O가 많은 프로세스를 먼저 실행시켜 프로세스의 평균 대기 시간을 줄인다.
• 알고리즘 : 프로세스에게 주어지는 우선 순위는 없고, 우선 순위는 큐에만 주어진다.
  • 새로 생성된 프로세스는 가장 높은 레벨의 큐에 삽입된다.
  • MLFQ 스케줄러는 가장 높은 레벨의 큐에서 맨 앞에 잇는 프로세스를 선택하여 CPU를 할당한다.
  • 프로세스가 CPU를 사용한 총 시간이 큐 시간 할당량을 넘어서게 되면 아래 레벨의 큐에 삽입된다. CPU 총 사용 시간이 큐 시간 할당량을 넘어서면 아래 레벨의 큐에 삽입된다.
  • 프로세스가 I/O로 실행이 중단된 이후 I/O가 끝나 실행이 준비되면 하나 높은 레벨의 큐에 삽입된다.
  • 큐에서 대기하는 시간이 오래되면 프로세스의 기아를 막기 위해 위 레벨의 큐에 삽입한다.
  • 프로세스가 최하위 레벨의 큐에 들어가면 프로세스가 완료될 때까지 RR 알고리즘을 이용하여 돌아가면서 스케줄링된다.
• 선점 / 비선점
  • 선점 : 더 높은 레벨의 큐에 프로세스가 도착할 때 실행을 중단하고 새 프로세스를 스케줄링하면 선점 스케줄링이 된다.
  • 비선점: 현재 프로세스가 실행을 끝낼 때 비로소 스케줄링을 하도록 구현하면 비선점 스케줄링이 된다.
• 성능과 특징: 서로 다른 레벨의 큐를 두어 프로세스들이 큐 사이로 이동할 수 있게 하여 CPU의 사용 시간이 짧은 프로세스나 I/O-bound 프로세스들이 높은 레벨의 큐에 오래 머무르도록 하고, 낮은 레벨의 큐에 오래 머무른 프로세스를 높은 레벨의 큐로 이동시켜 기아가 발생하지 않도록 한다.

 

 

 

참고

운영체제(Operating system), 황기태 지음