<aside> 📌 CPU-burst Time의 분포, Schedulling Algorithms, Round Robin(RR), Multilevel Queue, Multilevel Feedback Queue, Multi-Processor Scheduling, Real-time Scheduling, Example of Non-Preemptive SJF, Thread Scheduling, Algorithm Evaluation

</aside>

Scheduling Algorithms

1. FCFS (First-Come First-Served)

• time-sharing 시스템에서 Interactive job 의 응답 시간이 굉장히 길어짐 → 썩 좋은 스케줄링 방법은 아님

  • 앞에 어떤 프로세스가 버티고 있느냐에 따라 처리 시간이 굉장히 달라짐
  • Convoy effect(호위 효과): 짧은 프로세스가 긴 프로세스 뒤에 있는 현상, 오래 기다려야 함

• Example

  Process	Burst Time
  P1	24
  P2	3
  P3	3

  • 프로세스의 도착 순서: P1, P2, P3

    Process	Waiting Time	Response Time	Turnaround Time
    P1	0	0	24
    P2	24	24	27
    P3	27	27	30

    • 처리 순서: P1(24) → P2(3) → P3(3)
    • Average waiting time: (0 + 24 + 27) / 3 = 17

  • 프로세스의 도착 순서: P2, P3, P1

    Process	Waiting Time	Response Time	Turnaround Time
    P1	6	6	30
    P2	0	0	3
    P3	3	3	6

    • 처리 순서: P2(3) → P3(3) → P1(24)
    • Average waiting time: (6 + 0 + 3) / 3 = 3

2. SJF (Shortest-Job-First)

• 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄

• Two schemes:

  • Nonpreemptive (비선점)
    • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
  • Preemptive (선점)
    • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
    • 이 방법을 Shortest-Remaining-Time-First(SRTF)라고도 부름

• SJF is optimal → Preemtive 버전에 대해 얘기하는 것

  • 주어진 프로세스들에 대해 minimum average waiting time을 보장
  • 전체가 기다리는 시간이 평균적으로 짧아짐

• 문제점

  • Starvation이 발생할 수 있음
  • CPU 사용 시간을 미리 알 수 없음 (실제로는 SJF를 완벽하게 사용하기 어려움, 과거 정보를 토대로 추정만 가능)

• Example

  Process	Arrival Time	Burst Time
  P1	0	7
  P2	2	4
  P3	4	1
  P4	5	4

  • Nonpreemptive

    Process	Waiting Time	Response Time	Turnaround Time
    P1	0	0	7
    P2	6	6	12
    P3	3	3	8
    P4	7	7	16

    • 처리 순서: P1(7) → P3(1) → P2(4) → P4(4)
    • Average waiting time: (0 + 6 + 3 + 7) / 4 = 4

  • Preemptive

    Process	Waiting Time	Response Time	Turnaround Time
    P1	9	0	16
    P2	1	0	9
    P3	0	0	1
    P4	2	2	2

    • 처리 순서: P1(2) → P2(2) → P3(1) → P2(2) → P4(4) → P1(5)
    • Average waiting time: (9 + 1 + 0 + 2) / 4 = 3 (optimal 알고리즘이기 때문에 이보다 짧을 순 없음)

3. SRTF (Shortest-Remaining-Time-First)

• SJF의 Preemptive한 방법

4. Priority Scheduling

• A priority number(integer) is associated with each process
  • 다양한 기준의 priority 가 있을 수 있음
• highest priority를 가진 프로세스에게 CPU 할당 (smallest integer == highest integer)
  • Preemptive
  • Nonpreemptive
• SJF는 일종의 priority scheduling이라고 볼 수 있음
• 문제점
• 해결 방법

5. RR (Round Robin)

• 컴퓨터 시스템에서 사용하는 스케줄링은 여기에 기반하고 있음

특이한 케이스의 CPU Scheduling

Multiple-Processor Scheduling

• CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
• Homogeneous processor인 경우
• Load sharing
• Symmetric multiprocessing (SMP) - symmetric: 모든 CPU들이 대등한 것
• Asymmetric multiprocessing

Real-Time Scheduling

• Hard real-time systems
• Soft real-time computing

Thread Scheduling