Process Scheduling

SPN, SRTN, HRRN

SPN (Shortest-Process-Next)

• Non-preemptive scheduling
• 스케줄링 기준 (Criteria)
  • 실행시간 (burst time 기준)
  • Burst time이 가장 작은 프로세스를 먼저 처리
    • SJF(Shortest Job First) scheduling
• 장점
  • 평균 대기시간(Waiting Time, WT) 최소화
  • 시스템 내 프로세스 수 최소화
    • 스케줄링 부하 감소, 메모리 절약 -> 시스템 효율 향상
  • 많은 프로세스들에게 빠른 응답 시간 제공
• 단점
  • Starvation (기아현상, 무한대기) 현상 발생
    • BT(Burst Time)가 긴 프로세스는 자원을 할당 받지 못 할 수 있음
      • Aging 등으로 해결 (e.g HRRN)
    • 정확한 실행시간을 알 수 없음
      • 실행시간 예측 기법이 필요
  사진 출처 - https://youtu.be/keY9Wi7scEs
• 도착한 프로세스들 중 Burst Time이 짧은 프로세스 부터 실행된다.
• 프로세스 2는 BT이 길어 WT이 다른 프로세스에 비해 길어진다.

SRTN (Shortest Remaining Time Next)

• SPN의 변형
• Preemptive scheduling
  • 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨
• 장점
  • SPN의 장점 극대화
• 단점
  • 프로세스 생성시, 총 실행 시간 예측이 필요함
  • 잔여 실행을 계속 추적해야 함 = overhead
  • Context switching overhead

-> 구현 및 사용이 비현실적

HRRN (High-Response-Ratio-Next)

• SPN의 변형
  • SPN의 단점인 Starvation 보완
  • SPN + Aging concepts, None-preemptive scheduling
• Aging concepts
  • 비유적인 표현
    노약자 배려
  • 프로세스의 대기 시간(WT)을 고려하여 기회를 제공
• 스케줄링 기준 (Criteria)
  • Response ratio가 높은 프로세스 우선
• Response ratio = WT+BT / BT (응답률)
  • SPN의 장점 + Starvation 방지
  • 실행 시간 예측 기법 필요 (overhead)

Basic Scheduling algorithms

• Fairness (공평성)
  • FCFS (First-Come-First-Service)
  • RR (Round-Roin)
• Efficiency/Performance (효율성, 성능)
  • SPN (Shortest-Proess-Next)
  • SRTN (Shortest Remaining Time Next)
  • HRRN (High-Response-Ratio-Next)

  문제점

  • 실행시간 예측 부하

  문제점을 해결한 algorithms

• Efficiency/Performance (효율성, 성능)
  • MLQ (Multi-level Queue)
  • MFQ (Multi-level Feedback Queue)

MLQ, MFQ

MLQ (Multi-level Queue)

• 작업 (or 우선순위)별 별도의 ready queue를 가짐
  • 여러개의 ready queue를 가짐
  • 최초 배정 된 queue를 벗어나지 못함
  • 각각의 queue는 자신만의 스케줄링 기법 사용
• Queue 사이에는 우선순위 기반의 스케줄링 사용
  • E.g., fixed-priority preemptive scheduling
• 장점
  • 빠른 응답시간
• 단점
  • 여러 개의 Queue 관리 등 스케줄링 overhead
  • 우선순위가 낮은 queue는 starvation 현상 발생 가능

사진 출처 - https://youtu.be/actKUqea6Xc

• Queue가 여러 개이며 위로 올라갈수록 우선순위가 높아진다.

MFQ (Multi-level Feedback Queue)

• 프로세스의 Queue간 이동이 허용된 MLQ
• Feedback을 통해 우선 순위 조정
  • 현재까지의 프로세서 사용 정보(패턴) 활용
• 특성
  • 동적 우선순위 (Dynamic priority)
  • 선점 스케줄링 (Preemptive scheduling)
  • Favor short burst-time processes
  • Favor I/O bounded processes
  • Improve adaptability
• 프로세스에 대한 사전 정보 없이 SRN, SRTN, HRRN 기법의 효과를 볼 수 있음

사진 출처 - https://youtu.be/actKUqea6Xc

• 큐가 여러개 존재하며 큐들 간에 이동이 가능하다.
• 단점
  • 설계 및 구현이 복잡, 스케줄링 overhead가 큼
  • Starvation 문제 등
• 변형
  • 각 준비 큐마다 시간 할당량을 다르게 배정
    • 프로세스의 특성에 맞는 형태로 시스템 운영 가능
  • 입출력 위주 프로세스(I/O bounded process)들을 상위 단계의 큐로 이동, 우선 순위 높임
    • 프로세스가 block될 때 상위의 준비 큐로 진입하게 함
    • 시스템 전체의 평균 응답 시간 줄임, 입출력 작업 분산 시킴
  • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
    • 에이징 (aging) 기법
• Parameters for MFQ scheduling
  • Queue의 수
  • Queue별 스케줄링 알고리즘
  • 우선 순위 조정 기준
  • 최초 Queue 배정 방법

<참고>

• HPC Lab. KOREATECH - [OS]Lecture 5. Process Scheduling (3/4) - SPN, SRTN, HRRN / 운영체제 강의
• HPC Lab. KOREATECH - [OS]Lecture 5. Process Scheduling (3/4) - MLQ, MFQ / 운영체제 강의