[OS] 5. Process Scheduling 2

기본적인 스케줄링 알고리즘 중에서 FCFS와 RR에 대해서 먼저 알아볼 것이다.

FCFS (First-Come-First-Service)

말 그대로 "선착순" 알고리즘이라고 볼 수 있다. 먼저 들어오는 프로세스에 먼저 프로세서를 할당해주겠다는 것이다.

• Non-preemptive scheduling 
• 스케줄링 기준
  • 도착 시간을 기준으로 스케줄링한다
  • ready-queue에 먼저 도착한 프로세스를 먼저 처리
• 자원을 효율적으로 사용 가능 
  • 스케줄링 overhead가 적다. 
  • 프로세서(cpu)가 계속 일할 수 있다. 
• Batch System에 적합, interactive system에 부적합 
• 단점 
  • Convoy effect
    • 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상 (대기 시간 > 실행 시간)
  • 긴 평균 응답시간

FCFS (First-Come-First-Service)

normalized TT(NTT)라고 해서, Turnaround Time(TT: 도착부터 실행완료까지 시간)을 Burst Time(BT: 실행시간)으로 나눈 값이 있다. 이는 실제 도착시간을 기준으로 상대적으로 어느정도 기다렸는지를 나타내며, 통상 1이 넘으면 오래 기다린 것이라고 판단한다. 그리고 프로세스의 NTT 값들을 비교하여 공평하게 작업이 수행되고 있는지 또한 확인해볼 수 있다.

RR (Round-Robin)

프로세서를 일정 시간 동안만 사용하고 돌려가며 사용하자는 개념이다.

• preemptive scheduling
• 스케줄링 기준
  • 도착 시간
  • 먼저 도착한 프로세스를 먼저 처리 
• 자원 사용 제한 시간(time quantum)이 있다.
  • system parameter (time quantum)
  • 프로세스는 할당된 시간이 지나면 자원을 반납한다
    • Timer-runout (할당된 시간이 지나면 ready-queue의 맨 뒤에 다시 줄을 선다)
  • 특정 프로세스의 자원 독점을 방지한다 
  • Context switch overhead가 크다 
• 대화형(interactive), 시분할 시스템에 적합하다. 

RR (Round-Robin)

Time quantum이 시스템 성능을 결정하는 핵심 요소이다. 여기서 time quantum이 무한이 된다면 결국 FCFS와 같아진다. 왜냐하면 선착순으로 프로세스를 처리하는 방식은 같으나, 프로세서를 시간을 두고 돌려쓴다는데 차이가 있던 것인데, 시간 제약이 무한이 되면 이 것이 무효화되어 FCFS와 같아지는 것이다.
반대로 time quantum이 작아진다면 프로세서를 공유(processor sharing)하고 있는 듯한 느낌을 받게된다. 즉 모든 프로세스가 각각의 프로세서 위에서 실행되는 것 처럼 느끼는 것이다. 대신 그 만큼 context switch overhead가 높다.

간단하게 FCFS와 RR에 대해 먼저 알아보았다.

Ref: https://www.youtube.com/watch?v=r1JVA7yOPAM&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=9