스케줄링 알고리즘

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

어떤 스케줄링 알고리즘이 효율적인지 파악하기 위한 평가 기준은 다음과 같다.

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

  스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기시간을 본다.
  평균 대기시간은 모든 프로세스의 대기 시간 총합을 프로세스 수로 나눈 값이다. 주의할 점은 평균 대기시간은 작업 패턴을 바꾸면 대기 시간이 역전될 수 있다는 점이다. 따라서 절대적인 성능지표는 될 수 없다.

FCFS (First Come First Served) 스케줄링

• 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, 선입선출 스케줄링이라고도 한다.

동작방식

평가

• 단순하고 공평하지만, 콘보이 효과(호위효과)로 인한 시스템 효율성이 떨어지는 문제가 있다.
• 콘보이 효과 : 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려야하는 상황을 말한다.
• 일괄작업 시스템인 경우, 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는시간이 많아저 작업 효율이 떨어진다.

SJF (Short Process First) 스케줄링

• 최단 작업 우선 스케줄링
• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
• 오래 걸리는 작업을 뒤로 보내면서, 콘보이 효과를 완화하여 시스템 효율성을 높인다.

동작방식

평가

• 작은 작업을 먼저 실행하기 때문에 이론적으로는 시스템 효율성이 좋아진다.
• 하지만, 2가지 문제로 인해 사용하기 힘들다.
  • 운영체제가 프로세스의 종료 시간을 예측하기 어렵다.
    • 프로세스가 자신의 작업 시간을 운영체제에 알려주는 방식으로 보완
  • 작업 시간이 긴 프로세스는 계속 연기되면서 아사 현상 또는 무한 봉쇄현상이 나타날 수 있다.
    • 프로세스가 양보할 수 있는 상한선을 정하는 방식(에이징)으로 보완
• 결론적으로 프로세스의 종료시간을 파악하기 어렵고 아사현성아 일어 날 수 있기 때문에 잘 사용하지 않는다.

HRN (Highest Response Ratio Next) 스케줄링

• 최고 응답률 우선 스케줄링
• 서비스를 받기 위해 기다린 시간과 CPU 사용시간을 고려하여 스케줄링 하는 방식이다.

동작방식

• 우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간
• 우선순위를 정할때 대기시간을 고려함으로써 아사 현상을 완화한다.

평가

• 대기시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당 받을 확룔을 높인다.

라운드 로빈 스케줄링

• 순환 순서 방식 스케줄링
• 한 프로세스가 할당받은 시간동안 작업을 하다가 완료하지 못하면 준비큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.

동작방식

평가

• 문맥 교환시간이 추가되므로 문맥 교환시간을 고려하면 비효율적인 프로세스로 평가될 수 있다. (다른 스케줄링 방법과 총 대기시간이 동일한 경우)

SRT (Shortest Remaining Time) 스케줄링

• SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식
• 최소 잔류 시간 우선 스케줄링

동작방식

• CPU를 할당할 때 남은 작업 시간이 가장 적은 프로세스를 선택한다.
• 타임 슬라이스 동안 작업이 완료되지 않으면 준비큐로 가서 차례를 기다린다.

평가

• 프로세스의 남은 시간을 주기적으로 계산하고 남은 시간이 더 적은 프로세스와 문맥교환 시간이 필요하다.
• SJF 스케줄링과 마찬가지로 프로세스의 종료 시간을 예측하기 어렵고 아사현상이 일어날 수 있다는 문제가 있다.

우선순위 스케줄링

• 우선순위를 반영한 스케줄링

동작방식

• 중요도에 따라 우선순위를 가지고, 우선순위를 적용하는 방법은 다양하다.
  - SJF : 짧은 작업시간을 가진 프로세스가 높은 우선순위를 가진다.
  • HRN : 작업시간이 짧거나 대기시간이 긴 프로세스가 높은 우선순위를 가진다.
  • SRT : 남은 시간이 짧은 프로세스가 높은 우선순위를 가진다.
• 우선순위 알고리즘은 고정 우선순위 알고리즘과 변동 우선 순위 알고리즘으로 나뉜다.
  • 고정 우선순위 알고리즘 : 한번 부여받은 우선순위는 변하지 않는다. 시시각각 변하는 시스템 상황을 반영하지 못해 효율성이 떨어진다.
  • 변동 우선순위 알고리즘 : 일정 시간마다 변하는 우선순위를 새로 계산하고 반영한다. 시스템이 복잡하지만 시스템 상황을 반영하여 효율적인 운영이 가능하다.

평가

• 공평성을 위해하고 아사현상을 일으킨다는 문제가 있다.
• 변동 우선순위의 경우 프로세스의 우선순위를 매번 바꿔야학기 때문에 오버헤드가 발생하여 시스템 효율성이 떨어진다.

다단계 큐 스케줄링

• 고정형 우선순위를 사용하는 스케줄링 (선점형)
• 프로세스는 운영체제에게 부여받은 우선 순위에 따라 해당 우선순위의 큐에 삽입된다.
  
• 우선 순위가 높은 상위 큐 프로세스의 작업이 끝나기 전까지 하위 큐의 프로세스의 작업을 할 수 없다.
• 우선 순위가 낮은 프로세스의 작업이 연기되는 문제가 있다.

다단계 피드백 큐 스케줄링

• 우선순위가 낮은 프로세스에 불리한 다단계 스케줄링의 문제점을 보안한 방식
• 다단계 피드백 큐 스케줄링은 CPU를 사용한 후 프로세스의 우선순위가 낮아진다.
• 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으로써, 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
• 프로세스의 우선순위가 낮아질수록 해당 큐의 타임 슬라이스 크기가 커진다.
• 즉, 우선순위에 따라 타임 슬라이스 크기가 달라진다는 것이다.
• 우선순위가 낮은 프로세스가 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선 순위가 낮은 큐의 타임 슬라이스 크기를 크게 설정한다.