<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이라고 볼 수 있음
  • priority == predicted next CPU burst time
• 문제점
  • Starvation(기아 현상): low priority processes may never execute.
• 해결 방법
  • Aging(노화): as time progresses increase the priority of the process.
    • 오래 기다리면 우선 순위를 높여주자

5. RR (Round Robin)

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

• 각 프로세스는 동일한 크기의 **할당 시간(time quantum)**을 가짐 (일반적으로 10~100 milliseconds)

  • 응답시간이 빠르다는 것이 장점 (누구든지 짧은 시간만 기다리면 CPU를 가질 수 있음)

• 할당 시간이 지나면 프로세스는 선점당하고 Ready queue의 제일 뒤에 가서 다시 줄을 섬

• n개의 프로세스가 Ready queue에 있고 할당 시간이 q time unit 인 경우, 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻음

  → 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다!

  • 실행 시간이 긴 프로세스일 수록 대기 시간이 길어지고, 실행 시간이 짧은 프로세스일 수록 대기 시간 또한 짧아짐 (실행 시간이 대기 시간에 비례)

• Performance

  • q large → FCFS와 다를 바 없음
  • q small → context switch에 대한 오버헤드가 커진다

• 일반적으로 SJF보다 average turnaround time이 길지만, response time은 더 짧다.

6. Multilevel Queue

• Ready queue를 여러 개로 분할
  • foreground(interactive)
  • background(batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling
  • Time slice
• 각 큐의 레벨 (큐 간의 이동은 X, 처음부터 결정됨)

7. Multilevel Feedback Queue

• Multilevel Queue 와 달리 프로세스가 다른 큐로 이동 가능 (Starvation 발생 가능성 낮춤)
• aging을 이와 같은 방식으로 구현할 수도 있음
• Multilevel-feedback-queue scheduler를 정의하는 파라미터들 (기준)
• 프로세스의 처리 시간을 고려할 필요가 없음 (+ 처리 시간이 짧을 수록 우대받음)

특이한 케이스의 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