스케줄링 알고리즘

스케줄링 성능 평가 기준

평균 대기 시간

• 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합 평균값

평균 반환 시간

• 각 프로세스가 생성된 시점부터 수행이 완료된 시점까지의 소요시간 평균값

다양한 스케줄링 알고리즘

FCFS 스케줄링

First-Come First-Served. Queue와 같은 구조다.

• 비선점 스케줄링 알고리즘
  • 비선점: 중간에 누가 CPU를 뺏어갈 수 없는 방식
• 준비 큐에 도착한 순서에 따라 디스패치

장점

• 가장 간단한 스케줄링 기법

단점

• 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수 있음.
• 프로세스들의 도착 순서에 따라 평균 반환시간이 크게 변한다.

이런 식으로 값이 주어진다면 가정하고 평균 대기 시간과 평균 반환 시간을 구해본다.

평균 대기 시간은 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합 평균값이다.

• A가 준비 큐에 있는 시간 0초
  • A는 첫 번째로 등록된 프로세스이므로 준비 큐에 대기 없이 바로 실행 됨
• B가 준비 큐에 있는 시간 6초
  • A가 실행되는 6초만큼 준비 큐에 있음
• C가 준비 큐에 있는 시간 9초
  • A가 실행되는 시간 6초, B가 실행되는 시간 3초만큼 준비 큐에 있음
• D가 준비 큐에 있는 시간 10초
  • A=6초 + B=3초 + C=1초 = 10초 준비 큐에 있음

평균 반환 시간은 생성된 시점부터 수행이 완료된 시점까지 소요시간 평균 값이다.

• A는 6초만에 반환
• B는 9초만에 반환
• C는 10초만에 반환
• D는 14초만에 반환

FCFS 스케줄링 알고리즘 성능 측정 결과

평균 대기 시간: (0+6+9+10)/4 = 6.25초

평균 반환 시간: (6+9+10+14)/4 = 9.75초

하지만 이걸 C, B, D, A 순으로 돌린다면 평균 대기시간을 3.25초, 평균 반환시간을 6.75초로 확 줄일 수도 있음. 즉, 똑같은 작업을 하더라도 어떤 순서로 실행되느냐에 따라 결과가 다르기 때문에 예측하기 어려움

SJF 스케줄링

Shortest Job First. 가장 짧은 작업을 가장 빨리 실행하는 알고리즘이다.

• 비선점 알고리즘
• 준비 큐에 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 디스패치

비선점 방식이기 때문에 0초에 6초짜리 작업이 들어오고, 1초에 2초짜리 작업이 들어온다면, 6초 작업을 마치고 2초 작업을 처리함.

즉, STF 방식은 한 번 준비 큐에서 프로세스가 되면 다시는 준비 큐로 돌아오지 않음.

장점

• 일괄처리 환경에서 구현하기 쉬움

단점

• 실행 예정 시간 길이를 사용자의 추정치에 의존하기 때문에 실제로는 먼저 처리할 작업의 CPU 시간을 예상할 수 없음

SRT 스케줄링

Shortest Remaining Time.

• 선점 스케줄링 알고리즘
• 실행이 끝날 때까지 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치

SJF 알고리즘과 다르게 선점 방식이기 때문에 A라는 작업이 실행되다가도 그보다 더 작은 B라는 작업이 들어오면 A를 중지시키고 B를 실행시킨다.

장점

• SJF보다 평균 대기시간이나 평균 반환시간에서 효율적
• 대화형 운영체제에 유용

단점

• 각 프로세스의 실행시간 추적. 선점을 위한 문맥 교환(context switching) 등
• SJF보다 오버헤드가 큼.

RR(Round Robin) 스케줄링

• 선점 스케줄링 알고리즘
• 준비 큐에 도착한 순서에 따라 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한
• 시간 할당량 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치
• 예) 시간 할당량 = 3이라면, A라는 작업이 시간 6이라고 해도 3만큼만 작업하고 CPU를 반납해야 함.
• 기본적으로 FCFS 알고리즘을 사용함. 단지 할당량 만큼만 사용하고 CPU를 반납한다는 것만 다름.

장점

• CPU를 독점하지 않고 공평하기 이용
• 대화형 운영체제에 유용

단점

• 시간 할당량이 너무 크면 FCFS 스케줄링과 다를 게 없음
• 시간 할당량이 너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가함.시간할당량이 6일 때와 1일 때 성능 비교

시간할당량이 6일 때와 1일 때 성능 비교

HRN 스케줄링

Highest Resposne Ratio Next.

• 비선점 스케줄링 알고리즘
• 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 디스패치
  • 예상 실행시간이 짧을수록, 대기시간이 길수록 응답 비율이 커진다.
• 응답 비율: (대기 시간 + 예상실행시간)/예상실행시간 = 대기시간/예상대기시간 + 1

장점

• SJF 단점 보완
  • 자기보다 짧은 게 들어와도 작업을 못하고 기다려야 하는데, HRN은 기다리면 기다릴수록 응답 비율이 커지기 때문에 우선순위가 높아지는 효과가 있어서, 하염없이 기다리지 않고 선택될 수 있는 확률이 생김.

다단계 피드백 큐 스케줄링

• 선점 스케줄링 알고리즘(RR 알고리즘 활용함)
• I/O 중심 프로세스와 CPU 중심 프로세스의 특성에 따라 서로 다른 시간 할당량 부여
• n개의 단계(단계 1 ~ 단계 n)
• 각 단계마다 하나씩 큐 존재
• 단계가 커질수록 시간 할당량도 거짐

스케줄링 방법

• 신규 프로세스는 단계 1의 큐에서 FIFO 순서에 따라 CPU 점유
• 입출력 같은 이벤트가 발생하면 CPU를 양보하고 대기 상태로 갔다가 다시 준비상태가 될 때에는 현재와 동일한 단계의 큐에 배치
• 시간 할당량을 다 썼지만 프로세스가 종료되지 못했다면 다음 단계 큐로 이동 배치
• 마지막 단계 n에서는 RR 스케줄링 방식으로 동작
• 단계 k의 큐에 있는 프로세스가 CPU를 할당 받으려면 단계1부터 단계 k-1까지 모든 큐가 비어있어야만 함.

장점

• I/O위주 프로세스(대화형)는 높은 우선권 유지
• 연산 위주 CPU 중심 프로세스는 낮은 우선권이지만 긴 시간 할당량 가짐

적응적 다단계 피드백 큐 스케줄링

• 시간 할당량을 다 쓰기 전에 CPU를 반납하는 경우 하나 작은 단계의 큐로 이동 배치
• 연산 위주 프로세스가 I/O 위주로 바뀐다면 점점 작은 단계로 배치 가능

정리

• 비선점
  • FCFS(First Come First Served)
    • 준비 큐에 들어온 순서대로 디스패치(FIFO)
  • SJF(Shortest Job First)
    • 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧은 것부터 디스패치
  • HRN(Highest Response ratio Next)
    • 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것부터 디스패치
• 선점
  • RR(Round Robin)
  • 다단계 피드백
  • SRT(Shortest Remaining Time)
    • 실행시간이 끝날 때까지 남은 시간 추정치가 가장 짧은 프로세스를 디스패치

각각의 방식은 연관관계가 있다.

FCFS를 사용하다가 시간 할당량이라는 것을 제공한 것이 Round Robin 방식이다. 라운드 로빈을 쓰다가 단계를 나눠준 것이 다단계 피드백 큐 알고리즘이다.

SJF 같은 경우는 전체 시간 할당량이 짧은 것을 먼저 실행시키겠다는 알고리즘이다.

전체 대신에 ‘남은 시간'이 짧은 것이 좋겠다고 하여 개선한 것이 SRT다.

혹은 똑같은 비선점 SJF 방식이지만, 기다리는 시간이 많은 프로세스를 먼저 실행시키겠다는 것이 HRN 알고리즘이다.