📌스케줄링 알고리즘

📖FCFS(first-come-first-service)

🔍개념

• non-preemptive sheduling
• 스케줄링 기준 : 선착순으로 처리(ready queue 기준)

✏️특징

• high resource utilization(high Tr/Tc) 즉, scheduling overhead가 낮다.
• batch system에 적합 / interactive system에 부적합
• 긴 평균 응답시간
• convoy effect
  • 나는 1초면 끝나는 작업인데 내앞에 10초걸리는 작업이 진행중이라 기다림
  • 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상

📖RR(round-robin)

🔍개념

• preemptive sheduling
• 스케줄링 기준 : 선착순으로 처리(ready queue 기준)
• 단, 자원 사용제한시간(time quantum)이 존재히며 프로세스는 할당된 시간이 지나면 자원 반납

✏️특징

• 특정 프로세스의 자원 독점 방지
• context switch overhead가 크다
• 대화형(interactive), 시분할 시스템에 적합
• time quantum이 시스템 성능을 결정하는 중요한 요소
  • time quantum to infinite : 사실상 FCFS
  • time quantum to zero : processor sharing(프로세서를 동시에 쓰는 느낌)
    • 이때 체감 프로세서 속도 = 실제 프로세서 성능의 1/n
    • 그러나 high context switch overhead

📖SPN(shortest-process-Next) 또는 SJF(shortest-job-fist)

🔍개념

• non preemptive scheduling
• 스케줄링 기준 : 실행시간(burst time)이 가장 작은 프로세스를 먼저 처리

✏️특징

• 평균 대기시간(WT) 최소화
• 시스템 내 프로세스수 최소화
  • 스케줄링 부하 감소, 메모리 절약
• 많은 프로세스들에게 빠른 응답 시간 제공
• 무한대기 현상 발생 : BT(burst time)가 긴 프로세스는 자원을 할당받지 못할 수 있음
• 정확한 실행시간(BT)을 알 수 없음 : 실행시간 예측 기법이 필요하다.

📖SRTN(shortest-remaining-time-next)

🔍개념

• preemptive scheduling
• 스케줄링 기준 : 잔여 실행 시간이 더적은 프로세스가 ready되면 선점
• SPN의 변형

✏️특징

• BT예측 필요
• 잔여실행을 계속 추적함 => overhead
• context switching overhead

📖HRRN(high-response-ratio-next)

🔍개념

• non preemptive scheduling
• SPN의 변형 : SPN + aging concepts
  • aging concepts : 프로세스 대기시간(WT)를 고려하여 기회 제공
• 스케줄링 기준 : response ratio가 높은 프로세스 우선
  • response ratio
    • 응답률( WT+BT / BT )
    • 필요한 실행시간 대비 얼마나 기다렸나? 지표

✏️특징

• SPN 장점 + starvation(무한대기 현상) 방지
• 실행시간 예측 기법 필요 => overhead

📖MLQ(muilti-level-queue)

🔍개념

• 작업별 별도의 ready queue를 가진다
  • 최초 배정된 queue를 벗어나지 않는다
  • 각각의 queue는 자신만의 스케줄링 기법 사용
• queue 사이에서는 우선순위 기반의 스케줄링 사용

✏️특징

• 여러 queue관리로 overhead
• 우선순위 낮은 queue는 startvation 발생

📖MFQ(muilti-level-feedback-queue)

🔍개념

• preemptive scheduling
• 프로세스 queue간 이동이 허용된 MLQ
• feedback을 통해 우선순위 조정

✏️특징

• dynamic priority
• favor short BT processes 또는 favor I/O bounded processes
• improve adaptability : 각 큐의 시간 할당량 조절로 프로세스 특성에 맞게 시스템 운영
• BT를 예측하지 않아도 SPN, SRTN, HRRN의 효과를 볼 수 있다.
• 설계, 구현이 복잡하다
• overhead 크다, starvation 발생

✏️queue간의 우선순위 결정 방법

1. I/O bounded processes
   입출력 위주 프로세스들을 상위 단계 큐로(우선순위 높임)
   왜? => I/O는 일반적으로 cpu를 잠시만 쓰기 때문에
2. aging 기법
   대기시간이 지정된 시간을 초과한 프로세스들을 상위 단계 큐로

✏️parameters for MFQ scheduling

• Queue수
• Queue별 스케줄링 알고리즘
• 우선순위 조정 기준
• 최초의 Queue 배정 방법
  ...

📮출처 : https://www.youtube.com/watch?v=hzXVQIlSSos&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN