4) CPU 스케줄링

1. CPU 스케줄링

CPU 스케줄러는 프로세스가 생선된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 하며, CPU 스케줄링은 CPU 스케줄러가 하는 모든 작업을 말합니다.

CPU 스케줄러는 프로세서 스케줄러 라고도 합니다.

 

2. 스케줄링의 단계

• 고수준 스케줄링 : 시스템 내의 전체 프로세스 수를 조절하는것입니다. (장기 스케줄링, 작업 스케줄링 이라고도 합니다.)
  전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정합니다. 이 결정에 따라 결정되는 시스템의 전체 프로세스 수를
  멀티프로그래밍 정도 라고 합니다.
• 중간 수준 스케줄링 : 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는 것입니다. 시스템의 부하를 조절하려면 고수준 스케줄링 대신 중간 수준 스케줄링을 고려해야합니다.
  시스템에 과부하가 걸려서 전체 프로세스 수를 저절해야 한다면 이미 활성화된 프로세스 중 일부를 보류 상태로 보낸다. 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화 됩니다.
• 저수준 스케줄링 : 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 것입니다. 
  오늘날의 CPU 스케줄러는 대부분 중간 수준 스케줄링과 저수준 스케줄링으로 구성되어 있습니다.
  타임 아웃으로 준비 상태로 돌려 보내기도 하며
  준비 상태에 있는 프로세스 중 어떤 프로세스를 선택할지, 
  어떤 기준에 따라 타임 슬라이스를 정할지 등 시스템의 성능에 많은 영향을 미칩니다.

3. 스케줄링의 목적

• 공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안됩니다.
• 효율성 : 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주저야 합니다.
• 안정성 : 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 합니다.
• 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 합니다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 합니다.
• 반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 합니다.
• 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안됩니다.
  (아사 현상 starvation 또는 무한 봉쇄 현상 infinite blocking)

4. 스케줄링 시 고려 사항

우선순위가 높은 프로세스에 CPU를 먼저 할당합니다.

• 우선순위가 높은 프로세스 : 커널 프로세스, 전면 프로세스, 대화형 프로세스, 입출력 집중 프로세스
• 우선순위가 낮은 프로세스 : 일반 프로세스, 후면 프로세스, 일괄 작업 프로세스, CPU 집중 프로세스 

5. 다중 큐

프로세스를 효율적으로 관리하기 위해 큐를 여러 개 두어 관리하는 것을 말합니다. 준비 상태에서는 우선순위에 따라 다중 큐를 운영하고, 대기 상태에서는 같은 입츌력을 요구한 프로세스들을 모아 다중 큐를 운영합니다.

 

6. 스케줄링 알고리즘

스케줄링 알고리즘은 크게 비선점형 알고리즘(non-preemptive algorism)과 선점형 알고리즘(preemptive algorism) 으로 나뉩니다.

 

비선점형 알고리즘은 프로세스가 CPU를 할당받으면 작업이 끝날 때 까지 CPU를 놓지 않지 때문에 효율이 떨어져서 지금은 거의 사용되지 않습니다.선점형 알고리즘은 시분할 시스템을 고려하여 만들어진 알고리즘으로, 어떤 프로세스가 CPU를 할당 받아 실행 중이라도 운영체제가 CPU를 강제로 빼앗을 수 있습니다.

 

구분	종류
비선점형 알고리즘	FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링
선점형 알고리즘	라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링
둘 다 가능	우선순위 스케줄링

 

- 스케줄링 알고리즘의 선택 기준

어떤 스케줄링 알고리즘이 효율적인지 파악하려면 평가 기준이 있어야합니다. 가장 많이 사용되는 평가 기준은 다음과 같습니다.

• CPU 사용률
• 처리량
• 대기 시간
• 응답 시간
• 반환 시간

 

스케줄링 알고리즘의 종류 

• FCFS 스케줄링 : 준비 규에 도착한 순서대로 CPU를 할당하는 비선점형 스케줄링 방식 (선입선출)
• SJF 스케줄링 : 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
• HRN 스케줄링 : CPU를 할당받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 비선점형 방식
• 라운드 로빈 스케줄링 : 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 선점형 방식입니다.
• SRT 스케줄링 : 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택하는 선점형 방식입니다. 
• 우선순위 스케줄링 : 프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영하여 CPU를 할당하는 방식입니다.
  선점형 혹은 비선점형 방식으로 구현이 가능합니다.
• 다단계 큐 스케줄링 : 우선순위에 따라 준비 큐를 여러 개 사용하는 비선점형 방식입니다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입되어 실행됩니다.
• 다단계 피드백 큐 스케줄링 : 다단계 큐 스케줄링과 기본적인 형태가 같지만, CPU를 사용하고 난 프로세스가 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어갑니다. 우선순위가 낮은 큐일 수록 타임 슬라이스가 커집니다.
  우선순위가 낮은 프로세스가 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정합니다. 마지막 큐에 있는 프로세스는 무한대의 타임슬라이스를 얻습니다. 무한대의 타임슬라이스는 FCFS 스케줄링 방식을 의미합니다.