[OS] CPU Scheduling(단일 프로세서)

CPU 스케줄링 알고리즘은 선점형(Preemptive)/비선점형(Non-Preemptive)으로 나눌 수 있다.

비선점형 스케줄링은 CPU를 강제로 빼앗지 않는 방식이고
선점형 스케줄링은 CPU를 강제로 빼앗을 수 있는 방식이다.

CPU Scheduling 성능 측정 방법 (Scheduling Criteria, Performance Index(=Performance Measure, 성능척도))

• CPU utilization(이용률)
  keep the CPU as busy as possible
• Throughput(처리량, 산출량)
  # of processes that complete their execution per time unit
  -> CPU 입장에서의 성능척도

---

• Turnaround time(소요시간, 반환시간)
  amount of time to execute a particular process
• Waiting time(대기 시간)
  amount of time a process has been waiting in the ready queue
• Response time(응답 시간)
  amount of time it takes from when a request was submitted until the first response is produced, not output
  -> 프로그램(프로세스) 입장에서의 성능척도(작업 처리 시간에 대한 것)

Waiting time은 CPU를 얻기 위해 기다리는 시간을 모두 합친 것이고
Response time은 처음 대기 줄에 서서 CPU를 얻기 까지 기다린 시간이다.

그리고 기다리는 시간과 작업 시간 모두 합친 것이 Turnaroundtime이다.

Scheduling Algorithms

• FCFS(First-Come First-Served)
• SJF(Shortest-Job-First)
• SRTF(Shortest-Remaining-Time-First)
• Priority Scheduling
• RR(Round Robin)
• Multilevel Queue
• Multilevel Feedback Queue

FCFS(First-Come First-Served)

비선점형 스케쥴링(Non-Preemtive)
도착한 순서대로 CPU를 준다.
Convoy effect(호위 효과) 발생할 수 있음

SJF(Shortest-Job-First)

평균 대기시간이 가장 짧다

• 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• Two Schemes
  • 비선점형(Nonpreemptive)
    일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPUfmf 선점(Preemption) 당하지 않음
  • 선점형(Preemptive)
    • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를빼앗김
      • 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부른다.
      • 기아현상(Starvation)이 발생할 수 있음
• SJF is optimal
  • 주어진 프로세스들에 대해 minimum average waiting time을 보장
• 이론적으로 waiting time이 짧은 프로세스한테 CPU를 주는 것인데 사실 정확한 waiting time을 알 수 없기 때문에 실제로 잘 활용하지 않는다. (실제 정확한 CPU사용 시간을 알 수는 없지만 과거의 경험을 통해 예측해서 사용)

Priority Scheduling(우선순의 스케쥴링)

• A priority number(integer) is associated with each process
• highest priority를 가진 프로세스에게 CPU 할당(smallest integer = highest priority)
• SJF는 일종의 priority scheduling이다.(작업시간이 짧은 것에 우선순위를 부여하기 때문)
• Problem
  - Starvation(기아 현상) : low priority processes may never execute.
• Solution
  - Aging(노화) : as time progresses increase the priority of the process.

Round Robin(RR)

• 할당 시간이 지나면 CPU를 뺏기 때문에 Preemptive Scheduling이다.
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (timer에서 설정 후 넘김, 일반적으로 설정 시간은 10-100 milliseconds)
• 할당 시간이 지나면 프로세스는 선점(Preempted)당하고 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 오버헤드가 커진다.
  

Multilevel Queue

• Ready Queue를 여러 개로 분할

  • foreground(interactive)
  • background(batch - no human interaction)

• 각 큐는 독립적인 스케쥴링 알고리즘을 가짐

  • foreground - Round Robin(RR)
  • background - FCFS(First-Come First-Served)

• 큐에 대한 스케줄링이 필요

  • Fixed priority scheduling
    • serve all from foreground then from background.
    • Possibility of starvation.
  • Time Slice
    • 각 큐에 CPU time을 적절한 비율로 할당
    • Eg. 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

멀티레벨 큐는 레디큐의 단계를 이동할 수가 없음. 이것을 보완한 것이 멀티레벨 피드백 큐.
멀티레벨 피드백 큐에서는 레디큐의 단계... 간단히 신분이라고 표현했을 때 신분에 변화가 있을 수 있음.

• 프로세스가 다른 큐로 이동가능
• Aging을 이와 같은 방식으로 구현할 수 있다.
• Multilevel-Feedback-Queue Scheduler를 정의하는 파라미터들
  • Queue의 수
  • 각 큐의 Scheduling Algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 내쫓는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

처음 들어오는 프로세스는 우선순위가 가장 높은 큐에 배치
그 처음 들어 온 프로세스는 할당 시간은 짧게 준다.(RR에서 타임퀀텀을 짧게 준다는 말)
그리고 아래 큐로 갈수록 RR 할당시간을 길게 줌
가장 마지막 큐에서는 FCFS 방식으로 처리
상위 큐가 비어 있으면 그보다 낮은 큐에 있는 프로세스를 실행
-> CPU 사용시간이 짧은 프로세스한테 CPU를 많이 주는 스케줄링방식임