[OS] 스케줄링 알고리즘

◎ 평가 기준

• CPU 사용률

  • 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
  • 가장 이상적인 수치는 100%이지만 실제로는 여러 이유로 90%에도 못미침

• 처리량

  • 단위 시간당 작업을 마친 프로세스의 수
  • 해당 수치가 클수록 좋음

• 평균 대기 시간

  • 모든 프로세스의 대기 시간을 합한 뒤, 프로세스 수로 나눈 값
  • 해당 값이 낮을수록 좋음

◎ 프로세스 시간간의 관계

◎ 비선점형 알고리즘 vs 선점형 알고리즘

구분	선점형	비선점형
작업 방식	실행 상태에 있는 작업을 준단시키고 새로운 작업을 실행할 수 있다.	실행 상태에 있는 작업이 완료될 때까지 다른 작업 실행이 불가능하다.
장점	프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합	CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.
단점	문맥 교환의 오버헤드가 많다.	기다리는 프로세스가 많아 처리율이 떨어진다.
사용	시분할 방식의 스케줄러에 사용	일괄 작업 방식 스케줄러에 사용
중요도	높다	낮다

◎ 비선점형 알고리즘

◎ FCFS 알고리즘 (First Come First Served)

• 특징

  • 준비 큐에 도착한 순서대로 CPU를 하랑하는 비선점형 방식
  • 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있음
  • 큐가 하나라 모든 프로세스의 우선 순위는 동일

• 평가

  • 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다림
    → 시스템의 효율성이 떨어짐
  • 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아짐
    → 작업 효율이 떨어짐

• 콘보이 효과 : 매우 올래 걸리는 프로세스기 할당될 경우, 다른 스레드들이 이러한 프로세스에 영향을 받아서 전체적인 시스템 효율이 떨어지는 현상

◎ SJF 스케줄링 (Shortest Job First)

• = 최단 작업 우선 스케줄링

• 특징

  • 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
  • 콘보이 효과를 완화함

• 평가

  • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
  • starvation(아사) : 작업 시간이 길다는 이유로 계속 뒤로 밀려 공평성이 현저히 떨어짐

• 개선 방안

  • aging (나이 먹기) : 아사 현상의 완화 방법으로 프로세스가 자신의 순서를 양보할 때마다 나이를 한살 씩 먹어 최대 몇살까지 양보하도록 규정하는 것

◎ HRN 스케줄링 (Highest Response ratio Next)

• = 최고 응답률 우선 스케줄링

• 특징

  • SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
  • 

• 평가

  • 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 아사 현상 완화
  • 여전히 공평성이 위배되어 많이 사용하지 않음

◎ 선점형 알고리즘

◎ 라운드 로빈 스케줄링 (Round-Robin)

• 특징

  • 한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
  • 가장 단순하고 대표적인 방식
  • 작업을 완료할 때까지 계속 순환하면서 실행

• 타임 슬라이스와 문맥 교환

  • 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함
  • 타임 슬라이스가 큰 경우 : FCFS 스케줄링과 다를게 없어짐
  • 타임 슬라이스가 작을 경우 : 문맥 교환에 상대적으로 많은 시간능 낭비하여 실제 작업을 못하는 문제가 생김

◎ SRT 스케줄링 (Shortest Remaining Time)

• 동작 방식

  • 기본적으로는 라운드 로빈 스케줄링 방식을 사용
  • CPU를 할당받을 프로세스 선택할 때 남아있는 작업 시간이 가장 적은 프로세스를 선택

• 평가

  • 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF 스케줄링에는 없는 작업이 추가죔
  • 프로세스 종료 시간을 예측하기 어렵고 아사현상이 일어나기 때문에 잘 사용하지 않음

◎ 다단계 큐 스케줄링

• 동작 방식
  • 우선 순위에 따라 준비 큐를 여러개 사용하는 방식, 우선순위에 따라 해당 큐에 삽입
  • 고정형 우선순위 사용
  • 상단 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐에 작업이 시작됨

◎ 다단계 피드백 큐 스케줄맇

• 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤
  -> 다단계 큐에서 우선순위가 낮은 프로세스의 실행되는 연기 문제 완화

  • 단 커널 프로세스가 일반 프로세스 큐에 삽입되지 않음

• 우선 순위에 따라 타임 슬라이스의 크기가 다름

  • 한번 CPU를 잡을 때 많이 작업하라고 낮은 우선순위의 타임 슬라이스를 크게함
  • 마지막 큐에 있는 프로세스는 무한대의 타임 슬라이스를 가짐
  • 마지막 큐는 FCFS 스케줄링 방식으로 동작

◎ 기타 스케줄링 방법

◎ 우선순위 스케줄링

• 특징

  • 프로세스 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘
  • 우선순위는 비선점형 방식과 선점형 방식 모두 적용할 수 있음
    • SJF : 작업 시간이 짧은
    • HRN : 작업 시간이 짧거나 대기 시간이 긴
    • SRT : 남은 시간이 짧은

• 고정 우선순위

  • 한번 우선순위를 부여 받으면 종료될 때까지 우선순위가 고정
  • 단순하지만 시시각각 변하는 시스템의 상황을 반영하지 못함

• 변동 우선순위

  • 일정 시감나다 우선순위가 변하여 새오 계산하고 이를 반영함
  • 복잡하지만 시스템의 상황을 반영하여 효율적인 운영 가능

◎ 다중 Queue

• 준비 상태의 다중 큐

  • 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입
  • 고정 우선순위 방식, 변동 우선순위 방식이 있으며 각각 구현, 시스템의 효율성에 장점이 있음
  • 한 번에 하나의 프로세스를 꺼네에 CPU에 할당

• 대기 상태의 다중 큐 : 같은 입출력을 요구한 프로세스끼리 모아 놓음

  • 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태에 할당
  • 대기 큐에서 끝나는 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벹터라는 자료 구조 사용