[OS] CPU Scheduling

CPU Scheduling

• 어떻게 Process에게 CPU의 사용을 할당할 것인가
  • Multiprogramming에 기반함 - Memory 내의 실행 준비된(Ready State)의 Process들(in Ready Queue) 가운데 하나에게 CPU를 할당
    • Multiprogramming: 컴퓨터가 여러 프로그램을 동시에 실행하는 것처럼 보이게 하는 기술
• 목표: CPU 사용률과 처리량(Throughput)의 최대화

 

CPU, I/O Burst Cycle

• CPU Burst: CPU로 연산을 수행하는 시간
• I/O Burst: I/O 처리를 위해 기다리는 시간
• 일반적인 프로세스는 두 Burst를 번갈아 가며 수행함
• Process 분류에 따른 CPU Burst의 특징
  • CPU-Bound(Intensive: 집중적인) Process: 짧은 주기로 길게 이어지는 CPU Burst
  • I/O-Bound(Intensive: 집중적인) Process: 긴 주기로 짧게 이어지는 CPU Burst
  • 어떤 종류의 Process가 많은지에 따라 스케줄링 기법의 효율성이 달라짐

프로세스별 burst duration (서로 다른 Process, System에도 불구하고 대체적으로 다음과 같은 경향을 보임)

 

Scheduling의 종류

• CPU Scheduling의 결정은 다음 시점에 따라 이루어짐 (어느 시점에 Process를 Context Switch 할 것인지)
  1. "Running" → "Waiting" 상태: I/O에 접근 후 대기할 때
  2. "Running" → "Ready" 상태: 다른 Process에게 CPU를 선점당할 때
  3. 수행 종료: 수행이 종료됐을 때
  4. "Ready" → "Running" 상태: 비선점형 스케줄링

• 비선점형 스케줄링 (Non-preemptive Scheduling)
  • 1, 4의 상황에서만 수행되는 스케줄링 기법
  • I/O를 수행하는 단계가 속해있어야 함
  • Multiprogramming의 기본 스케줄링 - OS가 강제로 CPU 사용을 해제하지 못함
  • 현재는 잘 사용되지 않음
• 선점형 스케줄링 (Preemptive Scheduling)
  • 그 외의 다른 Scheduling 기법
  • 대부분의 OS가 하고있는 CPU Scheduling 기법
  • OS가 현재 CPU를 사용하고 있는 Process의 수행을 정지할 수 있음 (2의 상태 변이 발생)

 

Scheduling Criteria(스케줄링 기준)

• CPU 사용률(CPU Utilization): 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
• 처리량(Throughput): CPU가 단위 시간당 처리하는 프로세스의 기준
• 응답 시간(Response Time): Interactive System에서 요청 후 첫 응답이 올 때까지의 시간
• 대기 시간(Waiting Time): Process가 Ready Queue 내에서 대기하는 시간의 총합(Waiting Queue가 아님)
• Turnaround Time: Process가 시작해서 끝날 때까지 걸리는 시간
• 이상적인 Scheduling Criteria
  • 최대의 CPU 사용률
  • 최대의 처리량
  • 최소의 응답 시간
  • 최소의 대기 시간
  • 모든 조건을 만족시키는 Scheduler를 만드는 것은 현실적으로 불가능
• 시스템의 용도에 따른 요구사항이 달라짐
  • 슈퍼 컴퓨터: CPU 사용률
  • 개인용 컴퓨터: 응답 시간
  • 워크 스테이션: 처리량

 

Scheduling Algorithms

• First-Come, First-Served (FCFS) Scheduling: 단체 주문 도중 작은 주문이 와도 단체 주문 이후에 처리함
• Shortest-Job-First (SJF) Scheduling: 단체 주문 도중 작은 주문이 들어오면 먼저 처리해 줌
• Priority Scheduling: 우선순위가 높은 프로세스부터 실행
  • ex) 시스템에 전원이 나갔을 때, 재빨리 가장 높은 Priority인 백업 프로세스가 실행됨, 자율 주행 자동차에서 안전이 최우선시됨
• 범용 시스템에서 사용
  • Round-Robin (RR) Scheduling: 10ms만 프로세스를 사용하고 프로세스 교체 (공평하게 시간 분배)
  • Multilevel Queue Scheduling: 세분화하여 긴 작업은 더 많은 CPU 자원을 동적으로 할당
  • Multilevel Feedback Queue Scheduling : 세분화하여 긴 작업은 더 많은 CPU 자원을 동적으로 할당

 

1. FCFS Scheduling

• 먼저 CPU 할당을 요청한 Process에 CPU를 먼저 할당
  • FIFO Queue를 사용하여 간단하게 구현 가능
  • 비선점형 스케줄링

평균 대기 시간이 (0+24+27)/3=17로 아주 김

• 범용 시스템에서 잘 사용되지 않음
  • Multilevel Queue에서 사용될 수 있지만 FCFS로만 스케줄링하지 않음

 

2. Shortest Job First Scheduling

• CPU Burst Time이 가장 짧은 Process에 CPU를 먼저 할당
  • 최소의 평균 대기 시간을 제공
• 비선점형 방식: 한 번 CPU를 할당받으면 자신의 CPU Burst Time이 끝나기 전에는 놓지 않음
• 선점형 방식: Shortest Remaining Time First Scheduling(SRTF)
  • CPU를 할당받아 수행 중이더라도 CPU Burst Time이 자신의 현재 남은 시간보다 짧은 시간을 가진 프로세스가 새로 생성되면 CPU를 양보함

 

3. Priority Scheduling

• 미리 주어진 Priority에 따라 CPU를 할당
• 비선점형 방식
  • 한 번 CPU를 할당받으면 자신의 CPU Burst Time이 끝나기 전에는 놓지 않음
• 선점형 방식
  • 새로 생성된 Process가 현재 실행되는 Process보다 높은 Priority를 가지고 있을 경우, CPU를 양보
• 문제점
  • 기아 상태(Starvation): 낮은 Priority를 가진 Process는 전혀 수행되지 않을 수 있음
• 해결 방법
  • Aging 기법: 할당을 기다리는 시간에 따라 Priority를 증가시켜 주는 방법
• 시스템 별로 Priority가 필요한 경우(생명, 안전과 집결된 시스템)에서 적용됨

 

4. Round Robin Scheduling

• CPU를 시간 단위(Time Quantum)로 할당
  • 선점형 Scheduling 방식
  • 보통 Time Quantum은 10-100 milliseconds
  • Time Quantum만큼 수행한 Process는 Ready Queue의 끝으로 들어가 다시 할당을 기다림

Example of Round Robin Scheduling

• Ready Queue 내의 Process: n개
• Time Quantum: q시간
• 각각의 Process가 할당받는 시간: 1/n 만큼의 CPU 시간을 q로 쪼개어 할당받음
• 각 Process의 다음 Time Quantime이 돌아오기까지의 대기 시간: 최대 $(n-1)*x$
• 성능
  • q가 클 경우: FCFS (Starvation 발생)
  • q가 작을 경우: 문맥 전환(Context Switching)에 필요한 시간보다 낮다면 효율이 매우 떨어짐(Overhead 증가)
  • 일반적으로 10ms 미만의 Burst를 가진 process들이 많기 때문에 q를 10ms로 잡음

 

5. Multilevel Queue Scheduling

• Ready Queue를 여러 개의 Queue로 분리하여, 각각에 대해 다른 Scheduling Algorithm을 사용하는 기법
• Foreground Queue
  • Interactive 한 동작이 필요한 Process를 위한 Queue
    • ex) User Process(게임, 웹서핑 등)
  • Round Robin 기법 사용
• Background Queue
  • CPU 연산 작업(짧은 연산)을 주로 수행하는 Process를 위한 Queue
  • FCFS 기법 사용: Context Switch Overhead를 줄이기 위해 짧은 CPU 연산을 FCFS로 처리
• 각 Queue에 CPU를 어떻게 할당할 것인지를 결정해야 함
  • Queue에 대한 Priority 또는 Time Slice를 사용할 수 있음

 

6. Multilevel Feedback Queue Scheduling

• Multilevel Queue에서 Process들이 서로 다른 Queue로 이동할 수 있도록 한 Scheduling 기법
  • Aging의 한 방법으로 사용될 수 있음
• 필요한 요소들
  • Queue의 개수
  • 각 Queue마다의 Scheduling 기법
  • 언제 Process를 한 단계 높은 Queue로 옮길 것인가
  • 언제 Process를 한 단계 낮은 Queue로 옮길 것인가
  • 어떤 Process가 특정한 Service를 필요로 할 때 그것을 제공하는 Queue로 옮겨줄 방법

ex) Q0에서 안 끝나면 Q1으로 이동, Q1에서 안 끝나면 Q2로 이동하여 끝날때 까지 수행

• 즉, 생성된 후로 Q0, Q1에서 8+16ms 동안 종료되지 않는 Process는 많은 작업을 필요로 하는 Process로 간주하여 FCFS 기법을 이용해 충분한 CPU Time을 할당해 주는 Scheduling 방법

 

4 Multiple Processor Scheduling의 기본

• more CPU, more Complex for Scheduling: CPU 여러 개를 사용하는 System의 경우, CPU Scheduling이 더욱 복잡해짐
  • 각각의 CPU에 서로 다른 I/O 장치가 연결되어 있다면?
  • 각각의 CPU가 서로 다르다면? (명령어 셋, 처리 속도)
• 1. 비대칭 멀티프로세싱 (Asymmetric Multiprocessing)
  • 하나의 CPU가 시스템 자료 구조(Scheduling, I/O 작업 등) 관리
    • 나머지 CPU에게 프로세스 할당해줌
  • 모든 CPU가 접근할 경우보다 데이터 공유가 간단히 이루어짐
    • Kernel Multithread 지원이 안 되는 경우
  • ex) Master CPU가 나머지 Slave CPU를 관리
• 2. 대칭 멀티프로세싱(Symmetric Multiprocessing)
  • CPU가 쭉 펼쳐져 Process가 실행되면 특성에 따라 아무 CPU를 할당받음

• 3. 프로세서 친화성(Processor Affinity)
  • 과거에 수행하던 CPU(성능을 알고있는)에 Process를 배정하는 방법
  • ex) ARM CPU에서 성능(P > B > L), 저전력(P < B < L)을 참고하여 배정
• 4. Load Balancing
  • CPU가 동일할 경우, 동일한 Process들을 수행할 수 있음
  • CPU 마다 각각의 Ready Queue를 둘 경우
    • 일부 CPU에 Process가 집중될 수 있음
  • CPU 모두에(전체 CPU에) 하나의 Ready Queue만을 둘 경우
    • 사용 가능한 CPU에 차례대로 Process를 배정

by GPT

• in Linux
  • 방식: Completely Fair Scheduling (CFS)
    • 각 프로세스가 CPU를 사용할 수 있는 시간을 균등하게 보장
  • 작동 방식: CFS는 특정 프로세스에게 고정된 시간 슬라이스(Time Slice)를 할당하기보다는, 각 프로세스가 CPU를 얼마나 사용했는지 가상 런타임 (Virtual Runtime, vruntime)을 추적
  • 범용적으로 쓸 수 있는 OS로 역할을 수행하기  위해 사용
    • 리눅스는 데스크톱, 서버, 임베디드 등 다양한 환경에서 사용되므로, 모든 상황에서 적절한 성능과 응답성을 제공하기 위해 CFS와 같은 공정하고 유연한 스케줄링 기법을 사용