CPU 스케줄링

스케줄링의 단계

• 고수준 스케줄링 (=장기 스케줄링, 작업 스케줄링)
  시스템 내의 전체 작업 수를 조절한다. 작업 요청이 오면 시스템의 상황을 고려하여 작업을 승인할지 거부할지를 결정한다. 메인프레임과 같은 큰 시스템에서 사용된다.
• 중간 수준 스케줄링 (=중기 스케줄링)
  프로세스가 활성화된 후에도 시스템의 부하를 조절하기 위해 프로세스 중 일부를 보류 상태로 보내기도 하고, 다시 활성화시키기도 한다.
• 저수준 스케줄링 (=단기 스케줄링)
  준비 상태에 있는 프로세스를 실행 상태 또는 대기 상태로 보내기도 하며, 타임아웃으로 준비 상태로 돌려보내기도 한다. 

스케줄링의 목적

• 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 한다.
• 효율성: 시스템 자원이 유휴 시간 없이 사용되어야 한다.
• 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정해야 한다.
• 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다.
• 반응 시간 보장: 시스템은 적절한 시간 안에 프로세스의 요구에 반영해야 한다.
• 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.

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

• 선점형 스케줄링
  어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식, 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생길 수 있다. 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.
• 비선점형 스케줄링
  어떤 프로세스가 CPU를 점유하면 다른 프로세스가 강제로 빼앗을 수 없는 스케줄링 방식, CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어진다. 과거의 일괄 작업 시스템에서 사용하던 방식이다.

스케줄링 평가 기준

• CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간
• 처리량: 단위 시간당 작업을 마친 프로세스의 수
• 대기 시간: 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간
• 응답 시간: 프로세스 시작 후, 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간
• 반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간 (대기 시간 + 실행 시간)

1. FCFS 스케줄링 (First Come First Served)

• 비선점형 방식
• 선입선출 스케줄링
• 준비 큐에 도착한 순서대로 CPU를 할당하는 방식
• 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다. -> 다른 프로세스들의 대기 시간이 길어져 시스템의 효율성이 떨어지는 콘보이 효과(Convoy Effect)가 발생한다.
• 모든 프로세스는 우선순위가 동일하다.

2. SJF 스케줄링 (Shortest Job First)

• 비선점형 방식
• 최단 작업 우선 스케줄링
• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 방식
• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다는 문제점이 있다.
• 실행 시간이 긴 프로세스는 계속 순위가 밀려 연기되는 아사 현상 (또는 무한 봉쇄 현상)이 발생할 수 있다. -> 공평성이 떨어진다.

3. HRN 스케줄링 (Highest Response Ratio Next)

• 비선점형 방식
• 최고 응답률 우선 스케줄링
• 서비스를 받기 위해 기다린 시간과 CPU 사용시간을 고려하여 스케줄링하는 방식
• 우선순위 = (대기시간+CPU사용시간) / CPU사용시간
• SJF 스케줄링에서 발생할 수 있는 아사 현상을 완화한다.
• 그러나 여전히 공평성이 위배된다.

4. 라운드 로빈 스케줄링 (Round Robin, RR)

• 선점형 방식
• 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 차례를 기다리는 방식
• 타임 슬라이스의 크기는 프로세스의 반응 시간과 시스템 전체의 성능에 영향을 미치므로, 적당한 크기로 정하는 것이 중요하다.

5. SRT 우선 스케줄링 (Shortest Remaining Time)

• 선점형 방식
• 최소 잔류 시간 우선 스케줄링
• 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업시간이 가장 적은 프로세스를 선택한다.

6. 우선순위 스케줄링

• 우선순위를 반영한 스케줄링
• 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현할 수 있다.
• 비선점형 방식과 선점형 방식에 모두 적용할 수 있다.

7. 다단계 큐 스케줄링

• 선점형 방식
• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
• 각 큐는 라운드 로빈 방식으로 운영되며, 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

8. 다단계 피드백 큐 스케줄링

• 선점형 방식
• 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식
• 다단계 큐 스케줄링과 달리, CPU를 사용하고 난 프로세스의 우선순위가 낮아진다.
• CPU를 사용하고 난 프로세스는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.