<aside> 📌 CPU and I/O Bursts in Program Execution, CPU-burst Time의 분포, CPU Scheduler & Dispatcher, Scheduling Algorithms, Scheduling Criteria, FCFS(First- Come First-Served), SJF(Shortest-Job-First), Example of Non-Preemptive SJF, Example of Preemptive SJF, 다음 CPU Burst Time의 예측, Exponential Averaging, Priority Scheduling, Round Robin(RR), Example: RR with Time Quantum = 20, Turmaround Time Varies With Time Quantum

</aside>

CPU and I/O Bursts in Program Execution

• 프로그램이 실행되면 어떤 프로그램이든 그림 왼쪽과 같은 경로(기계어)를 가지고 실행 됨

• CPU만 연속적으로 쓰는 단계(CPU-burst)와 I/O만 실행하는 단계(I/O-burst)가 반복됨

  • 누구에게 CPU를 줄지 결정하는 것 → Scheduler

  

  I/O가 잦은 개입을 하는 프로그램 (Interactive함)

CPU-burst Time의 분포

• 여러 종류의 job(== process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다

  • Interactive job에게 적절한 response 제공 요망
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

  

  프로그램의 종류에 따라 각 burst의 빈도와 길이가 다름

  • 대부분의 CPU 시간은 I/O bound job이 다 쓴다는 추론을 하면 안 됨!!

  • I/O bound job은 중간에 너무 많이 끼어들어서 빈도가 높았던 것, CPU bound job은 CPU를 오래 쓰기 때문에 빈도가 적을 수 밖에 없음

    → 실제로 CPU는 CPU bound job이 오래 쓰며, I/O bound job은 CPU를 오래 쓰지 않음

  • job의 종류가 섞여 있다는 것 또한 추론 가능

  • I/O bound job은 interactive 하기 때문에 너무 오래 기다리면 사용자가 답답할 수 있기 때문에 CPU를 우선적으로 주는 게 필요함(공평보단 효율) → CPU 스케줄링의 필요성

프로세스의 특성 분류

• 프로세스는 그 특성에 따라 다음 두 가지로 나눔
  • I/O-bound process
    • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
    • 사람하고 인터랙션하는 job
    • many + short CPU burst
  • CPU-bound process
    • 계산 위주의 job
    • few + very long CPU burst

CPU Scheduler & Dispatcher

• CPU Scheduler

  • 누구에게 CPU를 줄 지를 결정하는 커널 코드
  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고름

• Dispatcher

  • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘기는 커널 코드
  • 이 과정을 context switching(문맥 교환)이라고 함

• CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.

  1. Running → Blocked (ex_I/O 요청하는 시스템 콜)
  2. Running → Ready (ex_할당 시간 만료로 timer interrupt)
  3. Blocked → Ready (ex_I/O 완료 후 인터럽트, 우선순위 기반 스케줄링을 하고 있을 때는 → 우선순위가 높은 프로세스에게)
  4. Terminate (프로세스가 종료돼서 할 일이 없으니 새로운 프로세스에게 CPU 넘김)
  • 1, 4에서의 스케줄링은 nonpreemptive (== 강제로 빼앗지 않고 자진 반납, 가지고 있어도 할 일이 X)
  • 다른 모든 스케줄링은 preemptive (== 강제로 빼앗음, CPU 계속 쓰고 싶지만 ㅠㅠ 어쩔 수 X)

Scheduling Criteria

1. Performance Index (== Performance Measure, 성능 척도)

• 시스템 입장에서의 성능 척도
  • CPU utilization (이용률)
    • keep the CPU as busy as possible
    • 전체 시간 중에서 CPU가 놀지 않고 일한 시간의 비율
  • Throughput (처리량)
    • number of processes that complete their execution per time until
    • 주어진 시간 동안에 몇 개의 작업을 완료했는가
    • process 하나를 완료한 것 X, burst 각각의 건을 따져야 함
• 프로세스(프로그램) 입장에서의 성능 척도 (시간이 중요)
  • Turnaround Time (소요 시간, 반환 시간)
    • amount of time to execute a particular process
    • CPU를 쓰러 들어가서(Ready Queue), 다 쓰고 나가는 데 걸린 시간 (대기 시간 + 처리 시간)
    • process 하나를 완료한 것 X, burst 각각의 건을 따져야 함
  • Waiting time (대기 시간)
    • amount of time a process has been waiting in the ready queue
    • CPU를 쓰지 못 하고 Ready Queue에서 기다린 시간
    • 선점형 스케줄링에서는 CPU를 얻었다 뺐겼다 하기 때문에 각각의 기다린 시간이 모두 포함됨
  • Response time (응답 시간)
    • amout of time it takes from when a request was submitted until the first response is produced. not output (for time-sharing environment)
    • CPU를 처음으로 얻기 까지 걸린 시간
    • 선점형 스케줄링에서 CPU를 얻었다 뺐겼다 할 때도 시간이 바뀌지 않음

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을 보장
  • 전체가 기다리는 시간이 평균적으로 짧아짐
• 문제점
• Example

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

• SJF의 Preemptive한 방법

4. Priority Scheduling

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

5. RR (Round Robin)

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

다음 CPU Burst Time의 예측

• 다음번 CPU burst time을 어떻게 알 수 있는가? (input data, branch, user, …)