운영체제 ch5.

Chapter 5: CPU Scheduling

• CPU scheduling

– CPU : 가장 중요한 컴퓨터 리소스

à CPU scheduling: OS 설계의 핵심

– CPU 활용도 극대화 및 프로세스를 위한 공정한 CPU 사용

• 멀티 프로그래밍으로 시작하여 CPU 활용도 극대화

• CPU – I/O burst 주기

– 프로세스 실행은 CPU 실행과 I / O 대기 주기로 구성됩니다.

• CPU burst 배포가 주요 관심사입니다.

process thread를 cpu에 할당할 것인가?

cpu burst à cpu에서 데이터 계산 및 처리

I/O burst à 입출력 장치를 이용해서 프로그램이 입출력을 수행하는 시간

cpu를 사용하지 않을 때 대기로 보낸다.

 

여러 개의 프로그램을 하나의 cpu에서 실행시키기 위해서는 하나의 프로세스가 컴퓨터 점유해서 cpu 및 I/O실행 종료후 다음 process

cpu와 I/O장치 낭비, multi programing 등장à 메모리에 동작할 program을 다 올린후 cpu사용하다 i/o사용하기 위해 대기상태로 진입하면 다른 process B를 cpu에 할당해서 사용한다.

è 목적 max사용률

Histogram of CPU-burst Times

• 많은 수의 짧은 burst

• 적은 수의 긴 burst

 

 

다양한 형태의 process가 있고 다양한 burst time을 가지고 짧은쪽에 몰려 있다.

상태를 알고 알고리즘을 만들어야 효율적

 

CPU Scheduler

• ready-queue에있는 process 중에서 process를 선택하고 해당 process에 CPU core를 할당합니다.

– ready-queue은 다양한 방식으로 주문할 수 있습니다. # 만들기에 따라 달라진다 FIFO 등

• CPU 스케줄링 결정은 다음과 같은 경우에 발생할 수 있습니다.

– 1. running에서 waiting 상태로 전환 # cpu를 사용하다가 다른 event를 하기 위해 잠시 멈춘다

– 2. running에서 ready 상태로 전환 # time sharing으로 time quentum을 초과할 때 --|

– 3. waiting에서 ready로 전환 # waiting 상태에 있다가 원하던 event 발생 또는 입출력이 끝났을 때(알고리즘 및 우선수위에 따라)

– 4. 종료 # 더 이상 할일이 없을 때 cpu를 두고 나간다.

# | --한번 점유했을 때 사용할 수 있는 시간이 있다 내부적으로 timer가 system interrupt를 발생시키고 scheduler동작시킨다. 시간 측정후 time quetum을 초과하면 ready-queue로 이동하고 다른 process cpu에 할당

 

• 위의 1번과 4번 상황은 nonpreemptive(비선점형)입니다. # 점유를 포기했을 때만 사용가능

– 프로세스가 종료되거나 WAIT 상태가 될 때까지 CPU를 차지합니다.

• 다른 모든 일정은 preemptive입니다. # cpu를 점유를 뺏어서 전달

– 공유 데이터에 대한 접근 고려 à Race condition

– kernel 모드에서 preemption 고려

• nonpreemptive 또는 preemptive kernel

– 중요한 OS 활동 중에 발생하는 interrupt 고려

• 인터럽트 활성화 / 비활성화

 

Dispatcher

• Dispatcher 모듈은 CPU 스케줄러가 선택한 프로세스에 CPU 제어를 제공합니다. 여기에는 다음이 포함됩니다.

– switching context

– user 모드로 전환

– 해당 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 점프

• Dispatch latency

– 한 process를 중지하고 다른 process를 시작하는 시간

• switching context 수

– cat / proc / 2166 / status # 2166 PID

voluntary_ctxt_switches              150   # 스스로 한 경우

nonvoluntary_ctxt_switches          8         # timer, scheduler에 의해

• 자발적 컨텍스트 전환

– IO 차단으로 인해

• 비 자발적 컨텍스트 전환

– 타임 슬라이스 만료 또는 선점

# timer interrrupt발생 interrupt 서비스로 넘어옴 -- > kernel 모드로 진입된 상태

 

 

 

 

 

 

Scheduling Criteria

• CPU 사용률 ß 최대

– CPU를 가능한 한 바쁘게 유지

• Throughput처리량 ß 최대

– 시간 단위당 실행을 완료 한 프로세스 수

• Turnaround처리 시간 ß 최소

– 특정 프로세스를 실행하는 데 걸리는 시간 #끝내고돌아오는 시간

• Waiting대기 시간 ß 최소

– 프로세스가 준비 대기열에서 대기한 시간

• Response응답 시간 ß 최소

– 요청이 제출된 후 첫 번째 응답이 생성될 때까지 걸리는 시간 (time-sharing 환경의 경우)

• 최적화

– 평균

– 표준편차

– 최대 또는 최소

 

 

Scheduling Criteria

• 모든 시스템

– starvation기아 없음

– 공정성: 모든 프로세스가 CPU를 공정하게 공유합니다.

– 균형 및 효율성 : 시스템의 모든 부분을 바쁘게 만듭니다.

• Batch process system 일괄 처리 시스템 # 연달아 입력된 일을 처리하는 경우

– 처리량

- 처리 시간

– CPU 사용률

• Interactive system 대화형 시스템

- 응답 시간

• Real-time system 실시간 시스템

- 마감 시간

– 예측 가능성

 

Scheduling Algorithm

• nonpreemptive비선점 스케줄링 알고리즘

– FCFS (First-Come-First-Served선착순) (FIFO)

• time-slice는 없지만 I/O 차단이 있습니다.

– SJF (Shortest Job First가장 짧은 작업 우선)

• 일괄 처리 시스템에서 평균 대기 시간 최소화

• Priority선점 스케줄링 알고리즘

– RR (Round-robin) 스케줄링

– 우선 순위 스케줄링

• 다단계 대기열 예약, 다단계 피드백 대기열 예약

• Linux의 Preemptive스케줄링 알고리즘

– 정규 업무를위한 CFS (Completely Fair Scheduling)

–RR, FIFO, 실시간 작업을 위한 EDF (Earliest deadline First가장 빠른 기한 우선)

• 실시간 스케줄링 알고리즘

– RM (Rate-Monotonic) 스케줄링

– EDF (가장 빠른 마감일 우선)

– LLF (Least Laxity First)

 

First- Come, First-Served (FCFS) Scheduling

• ready-queue의 도착 순서에 따라 CPU 할당

– real-life : 마트 카운터, 은행 번호표, 패스트 푸드

– Non-preemptive, No starvation

 

# 입출력인 경우에는 해결

 

 

가장 먼저 온 것을 해결하고 끝나고 다음 task해결

 

 

# 문제

• Convoy호송 효과 : 긴 과정 뒤에 짧은 과정

– 긴 평균 대기 시간

– I / O 시간에 CPU가 idle 상태 일 수 있음

– CPU 시간이 지나면 I / O가 idle 상태 일 수 있음

 

 

Shortest-Job-First (SJF) Scheduling # 기다리는 시간을 줄인다

• 다음 CPU burst의 길이를 각 process와 연결

– 이 길이를 사용하여 가장 짧은 시간으로 process를 예약합니다.

– 실제로, Shortest-next-CPU-burst, non-preemptive비선점 # cpu 할당받은 후 다 끝날 때까지 반환 x, multi-programing환경에서 입출력 동안 cpu 반환할 수 있다.

– 느슨한 convoy호송 효과

• SJF가 최적

– 주어진 프로세스 세트에 대해 최소 평균 waiting대기 시간을 제공합니다.

– 어려움은 다음 CPU 요청의 길이를 아는 것입니다.

– long run-tim 일일 때 기아 # 우선 순위가 떨어져 계속 밀린다. (작은일부터하다가 큰일 못함)

 

Example of SJF

Determining Length of Next CPU Burst

• 길이 추정 만 가능

– 이전 것과 유사해야합니다.

– 그런 다음 예측된 다음 CPU 버스트가 가장 짧은 프로세스를 선택합니다.

• 지수 평균을 사용하여 이전 CPU 버스트의 길이를 사용하여 수행할 수 있습니다.

1. t­n = nth CPU burst의 실제 길이

2. τ n+1 = 다음 CPU burst에 대한 예측값

3. α ,  0 ≤ α≤1

4. τ n+1 = α tn + (1- α)τ n

• 일반적으로 α는 ½로 설정됩니다.

• 호출된 선점형 버전

shortest-remaining-time-first

 

Examples of Exponential Averaging

. τ n+1 = α tn + (1- α)τ n

α=0 : 최근 기록은 중요하지 않습니다 # 이전 예측값만

. τ n+1 = τ n

α=1 : 실제 마지막 CPU burst만 계산

. τ n+1 = tn

같은 일일 때 패턴을 가지고 실행되다가 특이사항이 생길 때 처리할 수 있도록

• 공식을 확장하면 다음을 얻을 수 있습니다.

• α  및 (1- α )이 모두 1보다 작거나 같으므로 각 연속 항은 이전 항보다 가중치가 적습니다

# 더 과거의 값들은 점점 영향력 감소

 

 

Example of Shortest-remaining-time-first

이제 varying arrival times 및 preemption 개념을 분석에 추가합니다.

 

Round Robin (RR) # preemption

• 각 process는 작은 단위의 CPU 시간 (time quantum q)을 얻습니다.

–이 시간이 경과하면 프로세스가 preemption되고 ready-queue 끝에 추가됩니다.

• n개 process가 q와 함께 ready-queue에있는 경우

– 그러면 각 process는 한 번에 최대 q 시간 단위의 chunk로 CPU 시간의 1/n을 얻습니다. 어떤 프로세스도 (n-1) q 시간 단위 이상 대기하지 않습니다.

• Timer는 모든 quantum을 중단하여 다음 프로세스를 예약합니다. #dispatcher이용

 

• 모든 프로세스는 동일한 우선 순위를 갖습니다.

• Performance

– q large à FIFO # 모든 process가 q이하이다

– q small à q는 context switch대해 커야합니다.

그렇지 않으면 overhead가 너무 높습니다

– 일반적으로 q = 10ms ~ 100ms, context switch <10us

• time quantum 및 context switch시간

 

 

Example of RR with Time Quantum = 4

 

Turnaround Time Varies With The Time Quantum

 

 

Priority Scheduling

• 우선 순위 번호 (정수)는 각 프로세스와 연관됩니다.

• CPU는 우선 순위가 가장 높은 process에 할당됩니다.

(가장 작은 정수 = 가장 높은 우선 순위)

– preemptive

– nonpreemptive

• SJF는 우선 순위가 예측된 다음 CPU burst 시간의 역인 우선 순위 스케줄링입니다.

• 동일한 우선 순위 내에서 Round Robin 또는 FIFO 가능

• 기아 문제 (= 무기한 차단)

– 우선 순위가 낮은 프로세스는 실행되지 않을 수 있습니다.

• Solution: 노화

– 대기 시간이 진행됨에 따라 process의 우선 순위가 높아집니다.

– 긴 CPU 점유 process의 우선 순위를 낮춥니다.

 

Example of Priority Scheduling

 

 

 

 Priority Scheduling w/ Round-Robin

 

Multilevel Queue

• priority scheduling을 사용하면 각 priority에 대해 별도의 queues이 있습니다.

• priority가 가장 높은 queue에서 process를 scheduel해라!

– 각 queue에는 자체 scheduling 알고리즘이 있습니다.

– priority scheduling + RR scheduling 이 효과적

 

• 예) Foreground (Interactive) process 및 Background (batch) process

– 다양한 response time 요구사항

– Foreground > Background

• Foreground: RR # 응답이 빨라야한다

• Background: FCFS # 비교적 느려도됨

– 가능한 variant변형: CPU 시간을 각 queue로 나눕니다.

• Foreground: 80 %, Background: 20 %

 

 

• 예) process 유형에 따른 Prioritization 지정

Multilevel Feedback Queue (MLFQ)

• process가 다양한 queues간에 이동할 수 있도록 허용

– 동적 우선순위 체계

– 이러한 방식으로 aging를 구현할 수 있습니다.

– 프로세스는 CPU burst의 특성에 따라 분류됩니다.

• 많은 CPU 시간을 소비하고 우선순위가 낮은 queue로 이동

• I/O 중심의 interactive process à 우선순위가 높은 queue로 이동

• 세 개의 queues 예

– 새 작업이 Q0에 진입하고 FCFS를 제공했습니다.

• CPU를 확보하면 작업이 8mS 수신

• 8mS 내에 완료되지 않음, 1 분기로 이동

– 1 분기에 작업이 다시 FCFS에 제공됩니다.

• 16mS에서 완료되지 않음, 선점 및 2 분기

– 2 분기의 process가 오랫동안 제공되지 않았습니다.

à 상위 queue로 이동할 수 있음

– 최우선순위 : CPU burst가 8mS 미만인 process

– 다음 우선순위 : 8mS < CPU 버burst <= 24mS

– 마지막으로 2 분기에 종료

• 다음 매개 변수로 정의되는 MLFQ scheduler:

– 각 queue에 대한 queue 수 및 scheduling 알고리즘

– scheduling 를 upgrade/demote 할 시기를 결정하는 데 사용되는 방법

– process가 서비스를 필요로 할 때 process가 들어갈 queue를 결정하는 데 사용되는 방법

• Notes

– kernel process는 user process queue에 들어 가지 않습니다.

– 우선순위에 따라 다른 time slices

• 낮은 우선순위를 위한 큰 time slices à 낮은 CPU 확보 가능성

• 마지막 queue: FCFS (infinite time slice)

 

 

Thread Scheduling

• user-level와 kernel-level threads의 구별 # os에서는 kernel-level thread를 동작시킨다

– 최신 OS는 process가 아닌 thread를 예약합니다.

• Many-to-one과 many-to-many, thread 라이브러리는 LWP(Light Weight Process)에서 실행되도록 user-level thread를 예약합니다.

# 현대에는 one-to-one을 많이 쓴다, thread를 관리하는 process는

– 일정 경쟁이 process 내에 있기 때문에 PCS (process-contention scope 프로세스 경쟁 범위)라고합니다.

– 일반적으로 프로그래머가 설정한 우선순위를 통해 수행

• 사용 가능한 CPU에 예약된 kernel thread는 process-contention scope (PCS) – 시스템의 모든 스레드 간의 경쟁

– Linux, Windows 케이스

• Pthread 스케줄링 예

– API는 thread 생성 중에 PCS 또는 SCS를 지정할 수 있습니다.

• PTHREAD_SCOPE_PROCESS는 PCS 스케줄링을 사용하여 thread를 스케줄링합니다.

• PTHREAD_SCOPE_SYSTEM은 SCS 스케줄링을 사용하여 thread를 스케줄링합니다.

– OS에 따라 제한 가능 – Linux 및 macOS에서만 허용

PTHREAD_SCOPE_SYSTEM

 

Multiprocessor Scheduling

• Multiple CPU 사용 가능

– thread의 병렬 실행을 통한 load 공유 # load를 분담한다.

– 더 복잡한 CPU 스케줄링

• Multiprocessor 아키텍처 :

– Homogeneous 아키텍처 # process들이 다 똑같은 상태

• Multicore CPUs

• Multithreaded cores

• NUMA(Not Uniform Memory Access) systems # access 속도가 다르다

– Heterogeneous 다중 처리 # 다른 process, 일반 ex) cpu core | digital signal processor | AI porcessor | graphic

• Scheduling 전략

– Asymmetric multiprocessing

• Master server: processor가 스케줄링 및 IO를 제공합니다.

• 남은 processor : 계산 전용

– Symmetric Multiprocessing(SMP) # shared memeory process에서도 쓰는 용어

• 각 processor 자체 스케줄링 가능

Multiprocessor Scheduling

• Symmetric multiprocessing (SMP)

-common ready queue # 간단, load balancing해결

• Shared queue access는 botteneck이 될 수 있습니다. #계속 참조해서 사용해야한다

- core 당 run queues

• SMP의 일반적인 방법 # botteneck은 해결

 

• Load balancing 문제

Multithreaded Multicore System

• 동일한 물리적 칩에 있는 Multiple processor cores

-더 빠르고 적은 전력 소모

• core 당 여러 thread 속도 증가

-memory 검색이 발생하는 동안 다른 thread에서 진행하기 위해 memory stall을 활용합니다.

 

-각 core에는 1 개 이상의 하드웨어 thread가 있습니다.

-한 thread에 memory stall이 발생하면 다른 thread로 전환하십시오!

 

• Chip-multithreading (CMT)

– 각 core에 여러 하드웨어 threads를 할당합니다.

(Intel에서는 이것을 hyper-threading이라고합니다.)

– core 당 2 개의 하드웨어 thread가있는 quad-core system에서 OS는 8 개의 논리 processors를 인식합니다.

• Multithreading구현

– 대략적인 Multithreading

• memory stalls사이

• thread 전환에 대한 높은 비용

– 세분화된 multithreading

• instructions 사이

• thread switching을 위한 회로 à 저렴한 비용

 

 

 

 

 

Multithreaded Multicore System

• cache 및 pipeline과 같은 물리적 core resources는 하드웨어 thread에서 공유해야합니다.

• 두 가지 level의 스케줄링

– 1. 논리 CPU에서 실행할 소프트웨어 thread를 결정하는 OS

• 일반적인 스케줄링 알고리즘 사용

– 2. 각 core가 물리적 core에서 실행할 하드웨어 thread를 결정하는 방법.

• RR

• 특정 회로 # 두개 처럼 간단할 수 있다.

– 두 level이 정보를 공유 할 수 있다면

•보다 효율적인 스케줄링

• 예) core 당 2 개의 core 및 2 개의 하드 thread

– resource 충돌을 피하기 위해 2 개의 소프트웨어 core를 다른 core에 할당 할 수 있습니다.

 

 

 

Multiprocessor Scheduling

• Load Balancing

– SMP 인 경우 효율성을 위해 모든 CPU를 load 상태로 유지해야합니다.

– 워크로드를 균등하게 분산하기 위한 load Balancing시도

– Push migration- 주기적인 작업은 각 processor의 load를 확인하고 발견되면 작업을 overloaded과부하된 CPU에서 다른 CPU로 push합니다.

– Pull migration– idle processor가 사용중인 processor에서 대기중인 작업을 가져옵니다.

– Linux CFS, FreeBSD ULE : push and pull migration 구현

• processor Affinity선호도 # cache관련

– 한 processor에있는 thread, processor의 cache는 해당 thread의 memory access를 저장합니다. à warm cache

• thread에 "processor Affinity"가 있습니다.

- load balancing으로 인한 thread migration은 processor affinity의 영향을 미칠 수 있습니다.

à 해당 thread가 원본 processor의 cache 내용을 잃게됩니다.

– Soft affinity– 동일한 processor에서 실행을 시도하지만 보장할 수 없음

– Hard affinity– process가 실행할 processor set를 지정할 수 있습니다.

 

NUMA and CPU Scheduling

• 메인 메모리 아키텍처가 processor affinity에 영향을 미침

• OS가 NUMA를 인식하는 경우 thread가 실행중인 CPU에 memory closes t 를 할당합니다.

 

Real-Time CPU Scheduling
 # 개념 정도만

• Real-time system

– Soft real-time systems # deadline이 있지만 할 수 없지 .. ex) streaming

• 중요한 real-time tasks은 우선순위가 가장 높지만 작업 schedule시기에 대해서는 보장하지 않습니다.

– Hard real-time systems # 대재앙 발생 ex) 미사일

• task는 deadline까지 서비스를 받아야합니다.

• real-time system의 이벤트 특성

– 시스템이 이벤트를 기다립니다.

• 소프트웨어의 타이머 만료 또는 하드웨어의 외부 센서

– 시스템은 최대한 빨리 event에 대한 대응 조치를 수행해야합니다.

• Event latency: event에서 event service까지

– Latency 요구 사항은 event마다 다릅니다.

• 두 가지 유형의 latencies가 성능에 영향을 미침

– Interrupt latency : interrupt에서 interrupt service routine까지

– Dispatch latency: 현재 process를 CPU에서 제거하고 다른 process로 전환하는 데 걸리는 시간

 

• 충돌 단계 : 1. kernel 모드에서 실행중인 모든 process의 Preemption선점, 2. 우선순위가 높은 process를 위한 낮은 우선순위 process의 리소스 해제

Priority-based Scheduling

• real-time 스케줄링: 스케줄러는 우선 순위 기반의 preemptive 스케줄링을 지원해야합니다.

– 그러나 soft real-time만 보장

• hard real-time의 경우 deadlines을 맞추는 기능도 제공해야합니다.

• process에는 새로운 특성이 있습니다. 주기적인 process에는 일정한 간격intervals으로 CPU가 필요합니다.

– processing timet, deadlined, period p 있음

– 0 ≤ t ≤ d ≤ p

– 정기 작업 비율은 1 / p입니다.