cs

OS - 스케줄링 알고리즘

joepasss 2022. 5. 14. 20:42

스케줄링 알고리즘

1. 기한부 스케줄링(deadline scheduling)

비선점

  • 작업들을 마감시간까지 완성하도록 계획한 스케줄링
  • 마감시간 이후 처리된 작업은 쓸모가 없다

2. 우선순위 스케줄링 알고리즘

비선점

  • 프로세스 실행 중 실행순서가 우선순위에 따라 정해지는 것
  • 우선순위가 높은 프로세스들이 계속 들어오면 우선순위가 낮은 프로세스들은 무한정 기다려야 한다
  • 정적 우선순위
    • 우선순위가 변하지 않는 방법
    • 상대적으로 오버헤드가 작고 구현이 용이하다
  • 동적 우선순위
    • 우선순위를 상황에 맞게 계속 조정하여 사용한다
    • 상대적으로 오버헤드가 크고 구현이 어렵다

3. FCFS 스케줄링 (FIFO)

비선점

  • 준비 큐에 도착한 순서에 따라 디스패치되는 것 (First In First Out)
  • 예측이 쉽다는 장점이 있으나 대화식 시스템에는 적합하지 않다

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

비선점

  • 작업이 끝나기까지의 실행시간의 추정치가 가장 작은 작업을 먼저 실행하는 방법
  • 단 도착시간이 주어진 경우 첫 번째로 들어온 작업에 대해서는 FCFS(FIFO) 기법을 적용한다
  • 대기 중인 작업의 수를 감소시키게 되고, 긴 작업 뒤에 대기 중인 작업들의 수도 감소시킬 수 있다
  • 작업들이 시스템을 통과할 때 평균 대기시간을 최소화 할 수 있다

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

선점

  • SJF를 선점형태로 변형시킨 방법
  • 작업이 끝나기까지 남아 있는 실행시간의 예상치가 가장 작은 프로세스를 먼저 실행시킨다.
  • 새로 입력된 작업도 포함해서 계산하므로 긴 작업들은 SJF에서보다 평균 대기시간이 길어진다
  • 시분할 시스템에 유용
  • SJF 스케줄링 기법보다 오버헤드가 크다

6. 라운드 로빈 스케줄링

선점

  • FIFO 처럼 도착순으로 디스패치 되지만 CPU에서 제어하는 타임 슬라이스(시간할당량)의 제한을 받는다
  • CPU 시간이 만료될 때 까지 처리되지 못하면 대기 중인 다음 프로세스로 넘어가며 실행 중이던 프로세스는 준비완료 리스트의 가장 뒤로 보내진다

7. HRN 스케줄링

비선점

  • SJF 스케줄링 기법의 약점인 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법
  • 각 작업의 우선순위는 그 작업이 서비스를 받을 시간 뿐 아니라 그 작업이 서비스를 기다린 대기시간 두 가지의 함수를 이용해서 값이 큰 것을 우선순위로 선택한다
    • 우선순위 값 = (대기시간 + 서비스를 받을 시간) / 서비스를 받을 시간
    • 값이 클수록 우선순위가 높다

스케줄링 방법 정리

종류 선점여부 방법
기한부 스케줄링 비선점 프로세스별 마감시간을 정해서 마감시간 안에 프로세스가 끝날 수 있도록 프로세스의 순서를 조정
우선순위 스케줄링 비선점 우선순위를 정해서 실행
정적 우선순위 / 동적 우선순위
FCFS (FIFO) 스케줄링 비선점 준비 큐에 도착한 순서대로 실행
SJF 스케줄링 비선점 작업의 실행시간이 가장 작은 작업 먼저 수행
SRT 스케줄링 선점 남아 있는 실행시간이 가장 작은 작업 먼저 수행
라운드 로빈 스케줄링 선점  FIFO 스케줄링으로 디스패치, 시간 할당량 이내에 작업을 완료하지 못 했다면 리스트의 가장 끝으로 보낸다
HRN 스케줄링 비선점 우선순위 값 = (대기시간 + 서비스를 받을 시간) / 서비스를 받을 시간
값이 높은 순서로 디스패치

 

8. FSS 스케줄링 (다단계 큐 스케줄링)

  • FSS (Fair Share Scheduling) 혹은 다단계 큐(MQ: Multi-level Queue)
  • 프로세스들의 집합 간 스케줄링 지원
  • UNIX 환경에서 서로 관계있는 사용자들에게 한정된 비용으로 시스템 자원을 사용할 수 있게 하기 위해 개발됨
  • 자원은 여러 공평한 공유 그룹에 배분
  • 특정 그룹으로 프로세스들을 분류할 수 있는 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법
  • 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스 등으로 나누어 준비상태 큐를 상위, 중위 하위단계로 배치
  • 각 준비상태 큐는 독자적인 스케줄링을 가지고 있으므로 각 그룹의 특성에 따라 서로 다른 스케줄링 가능

 

FSS (MQ)

 

9. 다단계 피드백 큐 스케줄링 (MFQ)

  • 신규 프로세스가 큐잉 네트워크에 들어오면 CPU를 차지할 때 까지 각 단계의 큐 내에서 FIFO 형태로 이동하며, 새로운 프로그램이 들어오면 높은 우선순위를 할당해 준다
  • 마지막 단계에서는 그 작업이 완료될 때 까지 라운드 로빈으로 순환
  • 프로세스가 낮은 단계로 내려갈수록 프로세스의 시간 할당량이 커진다
  • 입출력 위주의 프로세스들은 선점 스케줄링 기법으로, 연산 위주의 프로세스들은 비선점 기법으로 처리
  • 짧은 작업과 입출력장치를 효과적으로 활용하기 위해 입출력 위주의 작업들에게 우선순위를 주기 위함
  • 각 작업의 성격을 파악하여 빠르게 각 작업에 맞는 처리전략을 세울 수 있다

 

MFQ