[OS] 스케줄링 알고리즘

종류

비선점형 알고리즘

• FCFS 스케줄링
• SJF 스케줄링
• HRN 스케줄링

선점형 알고리즘

• 라운드 로빈 스케줄링
• SRT 스케줄링
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링

혼합

• 우선순위 스케줄링

선택 기준

CPU 사용률

• 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법

• 100%가 가장 이상적이지만 실제로는 90%에도 못미친다.

처리량

• 단위 시간당 작업을 마친 프로세스의 수

대기 시간

• 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간

응답 시간

• 프로세스 시작 후 첫 번재 출력 또는 반응이 나올 때까지 걸리는 시간

반환 시간

• 프로세스의 생성부터 종료(사용하던 자원 모두 반환)까지 걸리는 시간

• 대기시간 + 실행 시간 = 반환 시간

비선점형 알고리즘

프로세스가 CPU를 할당 받아 작업하는 동안 다른 프로세스가 뺏을 수 없다.

FCFS 스케줄링

준비 큐에 도착한 순서대로 CPU를 할당하는 방식이다. 선입선출로 이루어진다.

장점

• 알고리즘이 단순하고 공평하다.

단점

• 실행시간이 짧은 프로세스가 실행시간이 긴 프로세스를 계속 기다려야하는 문제점이 있다.

  • 콘 보이 효과 또는 호위 효과

• 보통 일괄 처리 방식에서 사용한다.

성능

• (모든 프로세스의 대기시간 + 작업시간) / 프로세스의 수

SJF 스케줄링

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당한다.

장점

• 시간이 짧은 작업부터 진행함으로써 콘 보이 효과를 완화할 수 있다.

단점

• 공평하지 못하다. 시간이 긴 작업은 계속 밀리는 상황이 발생할 수 있다.
  • 아사 현상
    • 해결 방법으로는 에이징이 있다. 나이 제한을 둠으로써 일정 횟수 이상 밀리면 더 이상 양보하지않고 작업하는 것이다.
• 운영체제가 프로세스의 종료 시간을 정확하게 예측할 수 없다.
  • 현대의 프로세스는 사용자와의 상호작용이 빈번하기 때문에 종료 시간을 예측할 수 없다. 따라서 SJF 스케줄링을 사용하기 힘들다.
  • 프로세스가 자신의 작업 시간을 운영체제에 알려주어 해결할 수 있다. 하지만 이를 정확히 알기가 어렵다.

결론

종료 시간 예측의 어려움과 아사 현상 때문에 잘 사용하지 않는다.

HRN 스케줄링

SJF 스케줄링의 아사 현상을 해결하기 위해 만들어졌다. 최고 응답률 우선 스케줄링이라고도 한다. 실행시간뿐만 아니라 대기시간까지 추가하여 판단하기 때문에 오래 기다렸다면 실행시간이 길더라도 우선순위가 높을 확률이 있다.

• 우선 순위 = {(대기 시간) + CPU 사용 시간} / CPU 사용 시간

장점

• 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상을 완화한다.

단점

• 아사 현상을 완화하긴 하지만 여전히 공평성에 위배되어 사용하지 않는다.

선점형 알고리즘

CPU를 점유하고 있는 프로세스가 있어도 타임 슬라이스나 인터럽트 요청 등에 의해 CPU를 빼앗을 수 있다.

라운드 로빈 스케줄링

프로세스가 CPU를 할당받고 작업하는 동안 할당받은 시간(타임 슬라이스)이 지나면 준비 큐의 맨 뒤로 보내는 방식이다. 선점형 알고리즘 방식 중 가장 단순하고 대표적인 방식으로 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행된다. FCFS 스케줄링에서 타임 슬라이스를 추가한 것이다. 우선 순위는 없다.

타임 슬라이스의 크기를 어떻게 설정하냐에 따라 시스템의 성능이 좌우된다.

• 타임 슬라이스가 큰 경우

  컨텍스트 스위칭 횟수가 적다. 하지만 너무 커질 경우 한 작업이 완료될 때까지 기다려야 하는 것처럼 보인다. 만약 크기가 무한대라면 FCFS와 비슷하다.

• 타임 슬라이스가 작은 경우

  컨텍스트 스위칭 횟수가 많다. 이로 인해 실제 작업 시간보다 더 많아진다.

따라서 타임 슬라이스는 되도록 작게 설정하되 컨텍스트 스위칭에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요하다.

SRT 우선 스케줄링

SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식이다. 최소 잔류 시간 우선 스케줄링이라고도 한다. 준비 큐에 남아 있는 작업시간이 가장 적은 프로세스를 선택한다. 그리고 타임슬라이스를 부여하여 작업 시간 제한을 둔다.

장점

• SJF 스케줄링과 평균 대기 시간을 비교했을 때 SRT 스케줄링의 평균 대기 시간이 더 짧다.

단점

• 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 컨텍스트 스위칭을 해야한다. SJF 스케줄링에는 없던 작업이 추가된 것이다.
• 운영체제가 프로세서의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않는다.

다단계 큐 스케줄링

우선 순위별로 준비 큐를 나누어 사용하는 방식이다. 운영방식은 라운드 로빈 방식과 동일하다. 대신 시간이 만료될 경우 같은 우선순위에 해당하는 준비 큐의 맨 뒤로 보내진다.

단점

우선 순위가 낮은 준비 큐에 있는 프로세스들이 계속 기다려야하는 현상이 발생한다.

다단계 피드백 큐 스케줄링

다단계 큐 방식과 동일하다. 대신 시간이 만료됐을 때 같은 우선순위에 해당하는 준비큐로 가는 것이 아니라 한 단계 낮은 우선순위의 준비 큐로 보내진다.

장점

• 다단계 큐에서 우선 순위가 낮은 프로세스들이 계속 기다리는 문제를 해결할 수 있다.

  이 방법으로 완전히 해결할 순 없다. 그래서 우선 순위가 낮은 준비 큐는 타임 슬라이스 시간을 크게 설정한다. 이를 통해 어렵게 잡은 CPU를 오랫동안 사용하도록 한다.

혼합

우선순위 스케줄링

프로세스의 우선순위를 반영한 스케줄링이다. 비선점형 방식과 선점형 방식에 모두 우선 순위를 적용할 수 있다.

• (비선점형) SJF 스케줄링

  작업시간이 짧은 프로세스에 높은 우선순위 부여

• (비선점형) HRN 스케줄링

  작업시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위 부여

• (선점형) SRT 스케줄링

  남은 시간이 짧은 프로세스에 높은 우선순위 부여

우선순위 알고리즘은 고정 우선순위 알고리즘과 변동 우선순위 알고리즘으로 나뉜다.

장점

• 커널 프로세스가 일반 프로세스 뒤에 실행될 수 있는 문제를 막을 수 있다.

단점

• 공평성 위배 및 아사 현상 유발

  • 프로세스 순서 무시하고 우선순위가 높은 프로세스에 먼저 CPU를 할당하기 때문이다.

• 순서 무시하고 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성을 떨어뜨린다.

  시스템의 효율성이 아니라 프로세스의 중요도를 기준으로 결정된다.