FCFS, RR

기본 스케줄링 알고리즘들

Basic Scheduling algorithms

• FCFS (First-Come-First-Service)
• RR (Round-Robin)
• SPN (Shortest-Process-Next)
• SRTN (Shortest Remaining Time Next)
• HRRN (High-Response-Ratio-Next)
• MLQ (Multi-level Queue)
• MFQ (Multi-level Feedback Queue

FCFS (First-Come-First-Service)

선착순 알고리즘

• Non-preemptive scheduling
• 스케줄링 기준 (Criteria)
  • 도착 시간 (ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리
• 자원을 효율적으로 사용 가능
  • High resource utilization / why?
• Batch system에 적합, interactive system에 부적합
• 단점
  • Convoy effect
    • 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상 (대기시간 >> 실행시간)
  • 긴 평균 응답시간 (response time)

RR (Round-Robin)

• Preemptive scheduling
• 스케줄링 기준 (Criteria)
  • 도착 시간 (ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리
• 자원 사용 제한 시간(time quantum)이 있음
  • System parameter
  • 프로세스는 할당된 시간이 지나면 자원 반납
    • Timer-run out
  • 특정 프로세스의 자원 독점(monopoly) 방지
  • Context switch overhead가 큼
• 대화형, 시분할 시스템에 적합
• Time quantum이 시스템 성능을 결정하는 핵심 요소
  • Very large (infinite) -> FCFS
  • Very small time quantum -> processor sharing
    • 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낌
      • 체감 프로세서 속도 = 실제 프로세서 성능의 1/n
    • High context switch overhead

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

• Time-runout이 추가되었다.
• 제한시간이 끝나면 나와서 다시 맨 뒤에 가서 줄을 선다 (ready Q)
  사진 출처 - https://youtu.be/r1JVA7yOPAM
• 타임퀀텀(시간 제한) 2초
• 프로세스 1번 도착시, 아무도 없어서 바로 들어간다. 3초가 필요한데, 타임퀀텀이 2초기 때문에 2초동안 일을 하고 나온다.
• 실행이 끝난 프로세스 1번은 다시 ready Q 맨 뒤에 줄을 선다.
• 프로세스 2번도 2초동안 일을 하고 나온다. 5초의 시간이 남는다. 작업이 끝난 2번은 맨 뒤에 줄을 선다.
• 이렇게 돌아가면서 타임퀀텀에 따라 프로세스들이 실행된다.

<참고>

• HPC Lab. KOREATECH - [OS] Lecture 5. Process Scheduling (2/4) - FCFS, RR / 운영체제 강의