운영체제 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. tn = 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입니다.