5. 프로세스 스케줄링 (2)

강의 출처 : https://www.youtube.com/watch?v=r1JVA7yOPAM&t=1102s

Basic Scheduling algorithms

1. FCFS (First-Come-First-Service)
2. RR (Round-Robin)
3. SPN (Shortest-Process-Next)
4. SRTN (Shortest Remaining Time Next)
5. HRRN (High-Response-Ratio-Next)
6. MLQ (Multi-level Queue)
7. MFQ (Multi-level Feedback Queue)

이 중 현재 게시물에서는 1, 2를 다루겠습니당

1. FCFS

First-Come-First-Service

• 선착순 알고리즘 (먼저 오는 프로세스한테 프로세서 할당)
• Non-preemptive scheduling
• 스케줄링 기준 (Criteria)
  • 도착 시간 (ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리
• 자원을 효율적으로 사용가능
  • High resource utilization
    • 이유
      1. 선착순으로 그냥 할당하니까 불필요한 스케줄링 오버헤드가 없음
      2. CPU가 계속 일할 수 있음 (비선점스케줄링이라서)
• Batch system에 적합
  • 일괄 처리 시스템은 시스템지향적이기 때문임.
  • 시스템 기준으로 보면 오는 순서대로 빠르게 작업을 처리 할 수 있기 때문
• interactive system에 부적합
  • 입력을 넣었을 때 빠른 반응을 요하는 대화형 시스템에는 부적합
• 단점
  • Convoy effect
    • 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상 (대기시간 >> 실행시간)
  • 긴 평균 응답시간(response time)
    • 먼저 ready queue에 도착한 프로세스가 끝날 때까지 기다려야하므로, 언제 끝날지 예측도 안되고 계속 기다려야하므로 평균 응답시간이 길어지게 됨

FCFS

P2때문에 P3, P4, P5의 NTT가 커짐 == convoy effect

• Normalized TT (NTT)
  • 기준이 서로 다를 때 기준을 하나로 맞춰주는 방법 (정규화)
  • 최적의 경우 NTT의 값은 1이 된다.
    • 왜냐하면, 도착~실행시작 = 0이어야 BT == TT 이기 때문

2. RR

Round-Robin

• 돌아가면서 프로세서를 쓰자
• Preemptive scheduling
• 스케줄링 기준(Criteria)
  • 도착 시간(ready queue 기준)
  • 먼저 도착한 프로세스를 먼저 처리
• 자원 사용 제한 시간(time quantum)이 있음 (FCFA와의 차별점)
  • system parameter
  • 프로세스는 할당된 시간이 지나면 자원 반납
    • Timer-runout
  • 특정 프로세스의 자원 독점(monopoly) 방지
  • Context switch overhead가 큼
    • 왜냐하면, 프로세스가 계속 바뀌므로
• 대화형 시스템(interactive system), 시분할 시스템(time-sharing system)에 적합
  • 응답이 중요한 시스템들에 적합하다
• Time quantum이 시스템 성능을 결정하는 핵심 요소
  • 만약, time quantum이 매우 크다면(무한대에 가깝다면)
    • FCFS와 동일하게 됨
      • 왜냐하면, 제한시간이 무한대로 길다면 해당 프로세스가 끝날 때까지 그 다음 프로세스는 기다려야하기 때문
  • 만약, time quantum이 매우 작다면(0에 수렴한다면)
    • 프로세서를 동시에 쓰는 기분이 들 것이다 (processor sharing)
    • 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낄 것
      • 체감 프로세서 속도 = 실제 프로세서 성능의 1/n
        • 왜냐하면 프로세서 1개를 n개의 프로세스가 나누어쓰는 느낌이기 때문
    • High context switch overhead
      • 오버헤드가 매우 클 것임
        • 왜냐하면 time quantum이 매우 작을 경우, 프로세스가 계속 바뀌니까 overhead가 큰 것

timer-runout이 되었을 때 할당되었던 P1은 ready queue의 맨 뒤로 가게된다 (P4뒤)

• 만약 P1이 프로세서를 할당 받았다가 time quantum을 넘길 경우(timer-runout), 현재 ready queue의 맨 뒤로 가게 됨 (P4 뒤)

time quantum이 2인 경우

• time quantum이 2인 경우 위와 같다.
• 참고로 현재 아웃풋이 중간에 없기 때문에 TT값은 response time과 동일하다.
• FCFS에 비해 응답 시간이 비슷한 것을 확인할 수 있다.

time quantum이 3인 경우

• time quantum에 따라 average response time(TT)가 바뀌는 것을 확인할 수 있다.