[공룡책🦖] CPU Scheduling

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

---

CPU Scheduling Basic Concepts

• 멀티 프로그래밍을 채택한 O/S에서는 기본적으로 사용
• 멀티 프로그래밍의 기본적인 목표
  • CPU 사용률을 최대화하기 위해 프로세스들을 concurrent하게 항상 실행
  • 한 프로세스가 wait할 경우 OS CPU를 뺏은 뒤 다른 프로세스에 할당

⇒ 프로세스는 I/O 요청을 위해 CPU 스케줄링이 필요

 

 

CPU I/O Burst 사이클 

번갈아가며 실행

프로세스 실행은 CPU execution과 I/O wait의 사이클로 구성된다.

프로세스 실행은 CPU 버스트(burst)로 시작되고 뒤이어 I/O 버스트가 발생한다.

마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르는 대신 실행을 종료하기 위한 요청과 함께 끝난다.

 

 

Durations of CPU bursts

• I/O-bound program : many short CPU bursts, 입출력 짧게 자주
• CPU-bound program : few long CPU bursts

 

CPU Scheduler

• CPU 스케줄러(CPU Scheduler) : 메모리 안의 실행 준비를 마친 프로세스 중 하나를 선택하여 CPU로 할당하는 역할을 수행
• ready 상태에 있는 프로세스들 중 CPU를 할당해줄 수 있는 프로세스를 선택하는 방법으로 무엇을 채택해야 할까?
  
  • Linked List / Binary Tree
  • FIFO Queue 
  • Priority Queue
  • → 큐 내 레코드들은 일반적으로 프로세스의 PCB

 

 

Preemptive (선점) and Nonpreemptive (비선점) Scheduling

• 선점형은 스케줄러에 의해 프로세스가 실행 도중에 CPU에서 빠져나올 수 있음을 의미
• 비선점형은 프로세스가 CPU에서 실행을 마치고 종료할 때까지 나머지 프로세스가 대기함을 의미
  즉, 프로세스가 terminaiting 상태나 waiting 상태로 변할 때까지 대기

 

Decision Making for CPU-scheduling

1. 프로세스가 running → waiting 상태로 스위칭
2. 프로세스가 running → ready 상태로 스위칭
3. 프로세스가 waiting → ready 상태로 스위칭
4. 프로세스가 terminates 상태가 될 때

 

1번과 4번은 프로세스가 자발적으로 CPU에서 빠져나오는, 즉 비선점 유형이다. 스케줄링 면에서는 선택의 여지가 없어서 실행에 의해 새로운 프로세스가 반드시 선택되어야 한다.

2번과 3번은 스케줄러에 의해 실행 중 CPU에서 빠져나올 수 있어 비선점 유형일수도, 선점 유형일수도 있다.

 

 

 

Dispatcher

디스패처는 CPU 스케줄러에 의해 선택된 프로세스에게 실질적으로 CPU의 제어권을 주는 역할을 수행한다.

스케줄러는 무엇을 변경할지 선택하는 것이고, 디스패처는 변경을 실제로 수행하는 것이다.

• CPU 스케줄러 내부에 포함
• 프로세스의 레지스터를 적재하고(Context Switching) 커널 모드에서 사용자 모드로 전환
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)

Context Switching을 하는데 소요되는 시간을 dispactcher latency 라고 칭하고, 이 소요 시간을 줄이기 위해 디스패처는 최대한 빨라야 한다.

Dispatcher Latency는 CPU 사용 시간보다 가급적 짧아야 한다.

 

 

 

Scheduling Criteria

CPU 스케줄링 알고리즘별 특성이 다르기에, 상황에 따라 선택해야 한다.

비교하는 데 사용되는 특성에 따라서 알고리즘을 결정하는 데 큰 차이가 발생한다. 

Scheduling criteria는 스케줄링 알고리즘 비교를 위한 기준으로, 최선의 알고리즘을 선택하는데 기준점이 된다.

 

 

1. CPU 이용률 ( CPU utilization )
   • CPU는 바쁜 상태를 유지해야함 → 사용률을 늘려야함
   • 실제 시스템에서는 40%에서 90%까지의 범위를 가져야함
2. 처리량 ( Throughput )
   • 특정 시간 내 많은 양의 프로세스 처리
   • 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수
3. 총 처리 시간 ( Turnaround time)
   • 프로세스 실행 후 종료까지의 시간을 최소화
   • 대기 시간 = 준비 큐에서 대기하면서 보낸 시간의 합
4. 응답 시간 ( Response time )
   • 첫 응답이 시작되는 데까지 걸리는 시간
   • 중간에 결과가 나온다면 그것이 기준이 됨
   • 응답 시작까지의 걸리는 시간이지 최종 응답 출력까지의 시간이 아님
5. 대기 시간 ( Waiting Time) 
   
   • 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지 걸리는 시간
   • 프로세스가 Ready 큐에 상주하는 시간을 최소화
   •  Waiting time을 개선하면 시스템의 효율을 크게 증대

 

CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

평균보다는 최대/최소값을 최적화시킨다.

 

 

Scheduling Algorithms

Ready queue 내의 어떤 프로세스에게 CPU core를 할당할 것인가의 문제를 해결한다.

 

 

FCFS(First-Come, First-Served) Scheduling

• 먼저 온 프로세스를 먼저 실행하는 방법
• 비선점 스케줄링 유형
• FIFO 큐를 참고하여 만들어진 방법으로 구현이 가장 쉽고 간단
• CPU 버스트 타임이 긴 프로세스가 먼저 실행되는 경우 waiting time이 크게 늘어나 효율성이 하락

FCFS 알고리즘

 

 

SJF(Shortest Job First) Scheduling

• 도착 순서와 무관하게 짧은 작업을 먼저 수행
• 크기가 동일할 경우 먼저 도착한 프로세스 실행
• 선점 유형 or 비선점 유형
  • 다음 프로세스에게 대기 명령을 내리면 비선점 유형
  • 현 프로세스를 중단하고 다음 프로세스를 실행시키면 선점 유형
• 평균 waiting time 을 최대한 줄일 수 있는 최적의 옵션

• 다음 프로세스의 CPU burst 시간을 확실히 알 수 없기 때문에 현실적으로 구현하기 어려움
  • 이에 대한 방안으로 다음 프로세스의 CPU burst 시간을 예측하여 비슷하게라도 구현
  • 실행할 프로세스가 과거에 얼마나 CPU burst 시간을 소요했는지 저장하여 현재 소요할 시간을 예측
  • 그러나 시간을 얼마나 쓰는지 기록하는 것 역시 CPU에 저장되는 것이기 때문에 부담 O

 

SJF 스케줄링

 

 

SRTF(Shortest-Remaining-Time-First) Scheduling

• 현재 실행중인 프로세스보다 다음 프로세스의 실행 시간이 짧다면 바로 다음 프로세스를 실행하는 방법
• SJF, SRTF 스케줄링의 경우 계속해서 짧은 실행 시간을 가진 프로세스가 도착하면, 긴 실행 시간을 가진 프로세스는 영영 실행하지 못할 가능성이 있음

SRTF 알고리즘

 

RR(Round-Robin) Scheduling

• 먼저 들어온 프로세스를 실행하지만, 시간 단위(time quantum)에 따라 끊임없이 스위칭하는 선점형 스케줄링 방법
• 원형 큐(순환 큐)로 처리
• 평균 waiting 시간을 줄일 수 있으나, 평균 response 시간이 크게 늘어날 수 있음

 

• 프로세스의 CPU 버스트 시간이 설정한 시간 단위보다 적다면?
  → 프로세스가 CPU에서 자발적으로 탈출하고 스케줄러는 ready 큐에 있는 다음 프로세스를 실행한다.
• 프로세스의 CPU 버스트 시간이 설정한 시간 단위보다 길면?
  → O/S에 의해 인터럽트와 함께 컨텍스트 스위칭이 발생한 후 다음 프로세스를 바로 실행한다. 그리고 현재 프로세스는 ready 큐의 끝으로 가 대기한다.

 

 

Priority-base Scheduling

• 각 프로세스에게 우선 순위를 할당하고, 우선 순위 순으로 프로세스를 CPU에 할당하는 방법
• 같은 우선 순위를 가지고 있다면, 먼저 온 프로세스를 실행
• CPU burst 시간이 클 때 우선 순위를 낮게 설정할 경우 SJF 스케줄링과 비슷한 결과가 나올 수 있다.
• 선점 유형 or 비선점 유형
• 가장 경계해야 할 문제는 기아(starvation) 현상
  • 우선 순위가 낮은 프로세스의 경우 무한정 대기 가능성 존재
  • 이에 대한 방안으로 오랜 기간 대기한 프로세스는 점진적으로 우선 순위를 높이는 방법

Priority-base Scheduling

 

 

Multi-Level Queue(MLQ) Scheduling

• 우선 순위별로 큐를 지정하고, 큐에 따라 각각 다른 스케줄링을 적용하는 방법
• 새로운 프로세스가 들어왔을 때 어느 큐로 분류해야 하는지 애매

 

Multi-Level Queue(MLQ) Scheduling

• MLQ 스케줄링를 보완한 방법
• 우선 순위별로 큐를 지정하는 것까진 똑같으나, 최하단 우선 순위의 큐를 제외하고는 모두 RR 스케줄링을 적용한 방법
  • 처음 실행한 큐는 최상단 우선 순위의 큐로 들어감
  • 최상단 우선 순위의 큐에 시간 단위를 가장 낮게 설정하고, 시간 단위 안에 실행한 경우 프로세스는 해당 큐에 유지됨
  • 시간 단위안에 프로세스 실행을 마치지 못한 경우 해당 프로세스의 우선 순위를 한 단계 낮춤
  • 계속해서 시간 단위 내에 실행하지 못한다면 최하단 우선 순위로 내려가 순서대로 실행
• 실행 시간이 길어 우선 순위가 낮아진 프로세스의 경우 기아 현상이 발생할수도 있음

 

 

Thread Scheduling

• 실제로 OS에 의해서 process가 아닌 kernel-level thread가 스케줄링
• user level thread는 thread library에 의해 관리되고 커널은 존재를 모름

→ CPU에서 실행되려면 연관된 kernel level thread에 mapping되어야 한다.

 

 

경쟁 범위 Contention Scopre

다대일과 다대다 모델을 구현하는 시스템에서는 thread library는 사용자 수준 스레드를 가용한 LWP 상에서 스케줄한다. 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스 경쟁 범위(process-contention scope, PCS)로 알려져 있다.

CPU상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템 경쟁 범위(system-contention scope, SCS)를 사용한다.

 

 

1. Process Contention Scope (PCS)

• User level thread를 스케줄
• 프로세스 내 스레드 간 CPU core 경쟁
• 높은 우선 순위를 가진 스레드 선택
• 실행 중인 스레드 선점

 

2. System Contention Scope (SCS)

• Kernel level thread를 스케줄
• 시스템 전체 스레드 간 CPU core 경쟁
• 스레드 라이브러리가 가용 LWP에 스케줄 → OS가 LWP의 kernel thread를 물리적 CPU core에 스케줄

 

 

Pthread Scheduling

Pthreads는 다음과 같은 범위의 값을 구분한다.

• PTHREAD SCOPE PROCESS : PCS 스케줄링을 사용하여 스레드 스케줄

    → user level 스레드를 가용한 LWP에 스케줄함

• PTHREAD SCOPE SYSTEM : SCS 스케줄링을 사용하여 스레드 스케줄

    → 각 user level 스레드에 대한 LWP를 생성하고 연결함 (core에 일대일 매핑)

 

 

 

Multi-Processor Scheduling

Multi-Processor는 여러 개의 물리적 프로세서를 제공하는 시스템을 말하며, 각 프로세서에는 하나의 단일 코어 CPU가 포함되어 있다. Processor당 한 core에 여러 CPU가 가용한다면 부하 공유가 가능하다.

다중 처리기는 다음 시스템 아키텍처들에 사용할 수 있다.

• Multicore CPU (homogenous)
• Multithreaded cores (homogeneous)
• NUMA systems (homogeneous)
• Heterogeneous multiprocessing

 

 

Approaches to Multiple-Processor Scheduling

1. 비대칭 다중 처리기 AMP (asymmetric multiprocessing )

• 비대칭 (기능적으로 다름) : Master / others
• Master server가 모두 처리하며 나머지는 user code만 실행
• 오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단함
• Master server가 전체 시스템 성능을 저하할 수 있는 병목이 될 수 있음

 

2. 대칭 다중 처리 SMP (symmetric multi-processing)

• 독립적으로 작업 가능
• CPU마다 똑같은 일 처리 가능
• 다중 처리기를 지원하기 위한 표준 접근 방식
• 각 프로세서는 스스로 스케줄링 가능하며 스케줄러가 ready queue를 확인하고 실행할 스레드를 선택함

 

 

Multicore Processors

현대 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착하여 다중 코어 프로세서 (multicore processor)가 된다.

 

프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 소비하는 메모리 스톨(memory stall)이라고 하는 이 상황은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 주로 발생한다.

현대 프로세스는 메모리보다 속도가 훨씬 빨라서 cache miss가 발생하게 된다.

 

이러한 상황을 해결하기 위해 

• 둘 이상의 hardware thread를 한 core에 할당
• 한 hardware thread가 메모리를 기다리며 중단되면 core가 다른 thread로 전환
• 각 hardware thread는 각 arhictectural state를 유지
• OS 입장에서는 hardware thread를 software thread를 실행하는 논리적인 CPU로 보고 스케줄링 진행 (chip multithreading; CMT)

 

 

Load Balancing (부하 균등)

SMP

운영체제와 메모리를 공유하는 여러 프로세서가 프로그램을 수행하는 것

• 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 시도
• 멀티프로세서의 이점을 최대한 활용하기 위해서인데, 그렇지 않으면 하나의 프로세서가 idle 상태일 때 다른 프로세서들은 부하가 클 수 있음 → ready queue에서 CPU를 기다리는 상황

 

Load Balancing

• SMP에서 모든 프로세서들의 부하를 동일하게 유지하는 것
• 각 프로세서별로 자신의 ready queue를 갖는 시스템에서는 필요함
• common run queue를 사용하는 system에서는 필요없음

 

 

Processor Affinity

스레드에 의해 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채우게 된다. 그 결과 스레드에 의한 잇따른 메모리 접근은 캐시 메모리에서 만족한다.

그렇다면 스레드가 특정 processor에서 실행될 때 캐시 메모리는?

 

Warm Cache

• 스레드가 최근 접근한 데이터가 프로세서의 캐시를 채움
• 스레드에서의 연속적인 메모리 접근은 캐시 메모리에서 처리됨 → warm cache

 

캐시 무효화 및 다시 채우는 비용이 많이 들기 때문에 SMP를 지원하는 대부분의 운영체제는 스레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 같은 프로세서에서 계속 실행시키면서 warm cache 를 사용한다. 

 

 

Process Affinity 형태

1. Soft Affinity

• OS는 process가 동일 processor에서 실행되도록 노력함, 보장은 안됨
• 노력은 하지만 load balancing으로 이주 가능

2. Hard Affinity

• system call로 프로세스가 실행될 수 있는 프로세서의 집합을 지정
• 특정 프로세서에서 실행되도록 보장

메인 메모리 구조가 process affinity에도 영향을 준다.

• 특정 CPU에 스케줄된 스레드로부터 가까운 메모리를 할당한다.
• NUMA-aware인 경우 가까운 메모리에 할당한다.

 

 

Heterogeneous Multiprocessing (HMP)

• 모든 프로세서가 기능 면에서 동이하기에 스레드는 임의 core에서 실행 가능하다.
• load balancing, processor affinity, NUMA 등에 따라 메모리 접근 시간이 다르다.
  • core들이 기능적으로 다를 수 있음
  • 스레드가 특정 목적으로 특정 core에서 실행될 수 있음
  • task의 특정 요구에 기반해 특정 core에 할당함으로써 전력 소비를 더 잘 관리

 

 

Real-Time CPU Scheduling

Real-Time O/S에서의 스케줄링은 Soft Realtime 혹은 Hard Realtime 으로 구성된다.

• Soft real-time 시스템 : 반드시 정해진 시간 내에 실행하는 것은 아니며, 중요 태스크가 먼저 실행된다는 것만 보장
• Hard real-time 시스템 : 요구 사항이 매우 엄격하여 태스크는 반드시 시간 내에 실행되어야 함