[운영체제] 05. CPU Scheduling

 

 

 

 

CPU bursts and I/O bursts의 교대 시퀀스

 

Histogram of CPU burst times

CPU Scheduler

• 실행 준비된 프로세스 중 하나를 선택한다

CPU scheduling 결정은 다음과 같은 경우에 이루어진다

• (1) 프로세스가 실행 상태(running)에서 대기 상태(wating)로 전환될 때 (예: I/O 요청)
• (2) 프로세스가 실행 상태(running)에서 준비 상태(ready)로 전환될 때 (예: time slice expiration)
• (3) 프로세스가 대기 상태(wating)에서 준비 상태(ready)로 전환될 때 (예: I/O 완료)
• (4) 프로세스가 종료될 때(terminate)

(1)과 (4) 상황에서의 스케줄링은 비선점형(non-preemptive, 수행 중간에 중단 불가)이다.

 

(2)와 (3) 상황에서의 스케줄링은 선점형(preemptive, 수행 중간에 중단 가능)이다.

Dispatcher

• CPU 스케줄러에 의해 선택된 프로세스에 CPU 제어권을 부여

Dispatcher 기능

• switches context. (문맥 교환)
• User mode로 전환
• 선택된 프로세스를 재시작하기 위해 적절한 위치로 점프

Dispatch latency

• Dispatcher가 하나의 프로세스를 멈추고 다른 프로세스를 시작하는 데 걸리는 시간
• 스케줄링 오버헤드

Scheduling Criteria

CPU utilization

• CPU를 최대한 바쁘게 유지. (0% ~ 100%)

Throughput

• 단위 시간당 완료된 프로세스 수

Turnaround time

• 요청을 보내고 완료될 때 까지 시간(수행이 끝날 때 까지의 시간)

Waiting time

• 프로세스가 ready queue에서 대기한 시간의 합.(수행 시작할 때 까지의 시간)

Response time

• 요청을 보내고 첫 응답이 생성될 때까지의 시간

Scheduling algorithm의 목표

• Maximize the CPU utilization 
• Maximize the throughput
• Minimize the turnaround time
• Minimize the waiting time 
• Minimize the response time
  • response time의 평균보다 분산을 최소화하는 것이 더 중요할 수 있다.
  • E.g., interactive system

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
• ...

First-Come First-Served (FCFS)

process set이 다음과 같을 때

 

• P1, P2, P3 순서로 프로세스가 도착했다고 가정해보자

The Gantt Chart for the schedule

 

Wating time

• Wating time for P₁ = 0, P₂ = 24, P₃ = 27
• 평균 대기 시간: (0 + 24 + 27)/3 = 17
• FCFS는 비선점형(non-preemptive)이다.

process set이 다음과 같을 때

• P2, P3, P1 순서로 프로세스가 도착했다고 가정해보자

The Gantt Chart for the schedule

 

Waiting time

• Wating time for P₁ = 6, P₂ = 0, P₃ = 3
• 평균 대기 시간: (6 + 0 + 3)/3 = 3
• 이전 경우보다 훨씬 낫다.

Shortest-Job-First (SJF)

• CPU를, 가장 작은 CPU 버스트를 가진 프로세스에 할당.
  • 즉, 가장 짧은 것을 먼저

Two versions

• Non-preemptive (비선점형)
  • 한 번 CPU가 프로세스에 할당되면 선점될 수 없다.
• Preemptive (선점형)
  • 새로운 프로세스가 현재 실행 중인 프로세스의 남은 시간보다 짧은 CPU 버스트 길이로 도착하면 선점
  • 이를 Shortest-Remaining-Time-First (SRTF)라 한다.
    • 선점형 SJF 를 SRTF라고 부른다

SJF는 평균 대기 시간(average wating time) 측면에서 최적(optimal)이다.

 

Non-Preemptive SJF

 

Gantt Chart

 

Wating time

• Wating time for P₁ = 0, P₂ = 6, P₃ = 3, P4 = 3
• 평균 대기 시간: (0 + 6 + 3 + 7)/4 = 4

Preemptive SJF

 

Gantt Chart

Wating time

• Wating time for P₁ = 9, P₂ = 1, P₃ = 0, P4 = 2
• 평균 대기 시간: (9 + 1 + 0 + 2)/4 = 3

다음 CPU 버스트 시간 길이를 결정하는 것이 필요합니다.

이전 CPU 버스트 시간을 이용한 추정 (지수 평균)

 

 

다음 CPU 버스트 시간

다음 CPU 버스트 시간 길이 예측

Priority Scheduling (우선순위 스케줄링)

• 각 프로세스에는 우선순위 번호 (priority number, 정수)가 할당됩니다.
• CPU는 가장 높은 우선순위를 가진 프로세스에 할당됩니다.
  • 가장 작은 정수가 가장 높은 우선순위를 갖는다고 판단
• SJF는 일종의 우선순위 스케줄링입니다.
  • 다음 CPU 버스트 시간의 예측값을 짧은 것을 기준으로 우선순위로 사용한다고 볼 수 있기 때문
• 문제
  • Starvation - 낮은 우선순위 프로세스는 실행되지 않을 수 있습니다.
  • Starvation이 발생하는 이유 : 높은 우선순위를 갖는 프로세스들만이 실행되어, 낮은 우선순위 프로세스가 실행되지 않아 발생한다 (시험에 나오면 반드시 위 내용을 다 써야 한다)
• 해결책
  • Aging - 시간이 지남에 따라 프로세스의 우선순위를 증가시킵니다.

---

Round Robin (RR)

• 각 프로세스는 작은 단위의 CPU time을 얻습니다.
  • time quantum 또는 time slice (보통 10-100 밀리초)
  • 이 시간이 지나면,
    • 프로세스는 선점되고(중단된다고 보면 된다) 준비 큐의 끝에 추가됩니다.
• 준비 큐에 있는 n개의 프로세스와 time quantum이 q인 경우,
  • 각 프로세스는 한 번에 q time unit씩 총 1/n의 CPU time을 얻습니다.
  • (n-1)q time unit을 초과하여 대기하는 Process는 없다.
• 성능
  • q가 크면 FCFS와 같습니다.
  • q가 작으면 컨텍스트 스위칭 오버헤드(Context switching overhead)가 너무 높습니다.

 

Example) Time quantum이 2인 RR

Gantt Chart

Response time

• Response time for P₁ = 0, P₂ = 2, P₃ = 4, P4 = 6
• 평균 응답 시간: (0 + 2 + 4 + 6)/4 = 3

일반적으로 SJF보다 평균 turnaround time(반환 시간)은 높지만, 평균 Response time은 낮다

 

 

Time quantum and context switch time

 

Time quantum에 따른 Turnaround time의 변화

Multilevel Queue

Ready queue는 별도의 queues로 분할됩니다.

• foreground queue (상호작용 프로세스용)
• background queue (배치 프로세스용)

각 queue는 자체 scheduling algorithm을 가집니다.

• foreground queue - RR 
• background queue - FCFS 

queues 간 scheduling은 반드시 수행되어야 합니다.

• Fixed priority scheduling
  • foreground queue에서 먼저 프로세스를 서비스
  • starvation 가능성
• Time slice
  • 각 queue는 일정량의 CPU Time을 갖는다
    • foreground queue의 프로세스는 80%
    • background queue의 프로세스는 20%

Multilevel queuing 예시

 

Multilevel Feedback Queues

Process는 다양한 queues 사이에서 이동할 수 있습니다.

multilevel-feedback-queue scheduler의 매개 변수

• queues의 수
• 각 queue의 scheduling algorithms
• 프로세스를 upgrade할 때 사용하는 방법
• 프로세스를 demote할 때 사용하는 방법
• 프로세스가 서비스가 필요할 때 들어갈 queue를 결정하는 방법

---

Multi-Processor Scheduling

Multi-processor scheduling

• single processor scheduling보다 더 복잡합니다.

두 가지 유형의 scheduling

• Asymmetric multiprocessing
  • Master processor가 scheduling 결정을 수행하고, 다른 프로세서들은 사용자 코드를 실행합니다.
• Symmetric multiprocessing (SMP)
  • 각 프로세서가 자체 scheduling 결정을 수행합니다.
  • 현재 가장 일반적입니다.

Multi-processor scheduling의 새로운 문제

• Processor affinity(친밀성)
  • 동일한 프로세서에서 프로세스를 계속 실행하도록 합니다.
  • multicore 시스템에서 프로세스의 실행을 다른 프로세서로 이주하지 않고 같은 프로세서에서 실행시키는 것
• Load balancing
  • Workload(작업 부하)를 모든 프로세서에 고르게 분산하도록 시도합니다.
    • Push migration : 바쁜(overloaded) 프로세서가 안 바쁜(idle) 프로세서에게 작업을 넘김
    • Pull migration : 안 바쁜 프로세서가 바쁜 프로세로부터 작업을 가져옴

---

NUMA and CPU Scheduling

NUMA (None Uniform Memory Access)

• NUMA 구조의 예시: 각 CPU가 자체 메모리에는 빠르게 접근할 수 있지만, 다른 CPU의 메모리에 접근할 때는 느려집니다.

 

Multi-Processor Scheduling

SMP의 경우, 효율성을 위해 모든 CPU가 로드되어야 합니다.

• Load balancing
  • Workload를 고르게 분산하려고 시도합니다.
• Push migration
  • 주기적으로 각 프로세서의 부하를 확인하고, 과부하된 CPU의 작업을 다른 CPU로 push한다.
• Pull migration
  • Idle processor(유휴 프로세서)가 바쁜 프로세서에서 waiting task를 가져옵니다.

Linux Scheduling

Time-sharing with timeslice

• timeslice가 있는 프로세스만 실행할 수 있습니다.
• timer interrupt가 발생하면 timeslice가 차감됩니다.
• timeslice가 0이 되면 다른 프로세스가 선택됩니다.
• 모든 프로세스의 timeslice가 0이 되면, 재계산이 수행됩니다.

Real-time with priority

• Soft real-time
• Highest priority process가 항상 먼저 실행됩니다.

Linux는 timeslice를 사용해서 가장 높은 우선 순위 프로세스를 스케줄링합니다.

 

높은 우선 순위를 가진 프로세스는 더 긴 timeslice를 부여받습니다.

우선 순위에 따라 인덱싱된 task 목록

 

 

Algorithm Evaluation

Deterministic modeling

• 미리 정해진 특정 workload를 가져와서, 그 workload에 대한 각 algorithm의 성능을 정의합니다.
• 예: 주어진 processes 집합에 대해 Gantt Chart를 사용하는 SJF (Shortest Job First).

• 간단하고 빠름
• 알고리즘을 설명하고 예시를 제공하는 데 유용합니다.

Queueing models

• 수학적 공식을 사용합니다.
• 간단한 queueing network model

• 도착률(arrival rate)과 서비스율(service rate)이 주어지면,
  • utilization, 평균 queue 길이, 평균 waiting time을 도출할 수 있습니다.
• 일부 평가에서 제한적으로 사용됩니다.

Simulation

• 컴퓨터 시스템의 모델을 프로그램합니다.
  • Data structures는 시스템의 주요 구성 요소를 나타냅니다.
  • 예: 시계를 위한 변수
• 난수 생성기(Random numbere generator)가 필요합니다.
  • 프로세스 수, CPU 버스트 시간, 도착, 출발 등을 생성합니다.
  • Uniform, exponential, poisson 등
• 비용이 많이 들 수 있습니다.
  • 시뮬레이터의 설계, 코딩 및 디버깅은 시간이 많이 소요됩니다.
  • 대용량 저장 공간과 시간이 필요할 수 있습니다.

Simulation example

Implementation

• 알고리즘을 완전히 정확하게 평가하는 방법 --> 매우 어렵다.
  • ex) algorithm coding, operating system modification