Concept
모든 작업이 CPU를 꽉 사용하는 상태는 아니다. CPU burst, I/O burst 등...
CPU가 계산하는 시간, Input/Outpt 대기 등 시간, 메모리에 data 가져오는 시간 등은 모두 속도, 걸리는 시간이 다르다.
그리고 대부분 CPU 사용하는 시간이 짧다. -> CPU가 쉬는 시간에 다른 일을 시키자.
CPU Scheduler
○ CPU scheduler는 ready queue(readu 상태인 프로세스 모여있는 공간)에서 골라서 cpu에 배정한다.
○ CPU 스케줄링은 다음과 같은 상황에 일어난다.
1. running -> waiting state
2. running -> ready state
3. waiting -> ready state
4. Terminates
○ Nonpreemptive VS Preemptive
Nonpreemptive(비선제) : 종료나 waiting 상태가 되는게 아니면 CPU를 놓치 않는다. 양보하지 않는다.
Preemptive(선제) : Nonpreemptive를 제외한 모든 것. CPU를 한정된 시간 동안만 할당한다.
consider accesss to shared data -> race condition(경쟁상태. 각 프로세스가 cpu 선점을 위해 경쟁) 발생 가능
consider preemption while in kernel mode
conside interrupts occurring during crucial OS activites : 불가피할 경우 인터럽트를 disable하고 끝나면 다시 enable 가능. 잘 사용되지는 않는다.
○ Dispatcher
스케줄러 내 Task의 실행 순서를 제어하는 역할 : context switch, switching to user mode, 이전 프로그램으로 돌아가기 등
Dispatch latnecy(지연) - dispatcher가 한 프로세스를 멈추고 다른 프로세스를 시작하는데 걸리는 지연 시간.(save PCB0 -> restore PCB1 ..)
○ Scheduling Criteria : 스케줄링 기준
CPU utilization : 이용률
Throughput : 처리량
Turnaround time :반환시간 (프로세스 시작 ~ 끝날 때까지 걸린 시간)
Waiting time : 프로세스가 ready queue에 머무는 시간 (cpu time, I/O time등은 스케줄러가 줄일 수 없기 때문에)
Response time : 응답시간. 반환시간이 같아도 응답시간이 짧으면 결과를 미리 볼 수 있는 효과가 있다.
응답시간의 평균을 줄이는 것보다 편차를 줄이는 것이 일반적으로 더 중요하다
Scheduling Algorithm
○ FCFS ( First Come First Served)
Nonpreemptive algorithm이다.
먼저 온 프로세스 순서대로 먼저 진행하고, 프로세스가 다 끝나면 그 다음으로 온 프로세스를 사용한다.
*Convoy effect : 긴 CPU-bound job 때문에 짧은 job이 계속 CPU를 기다리는 현상
○ SJF (Shortest-Job-First)
Nonpreemptive algorithm.
가장 짧은 프로세스를 선택하는 알고리즘. 평균 대기 시간을 기준으로 optimal(최적의)하다.
○ SRTF (Shortest Remaining Time First)
SJF의 Preemptive 버전
○ RR(Round Robin)
FCFS의 Preemptive 버전.
매우 popular한 알고리즘.
각 프로세스는 짧은 CPU time(time quantum - q)를 가지고, Time interrupts가 q가 끝나고 일어나 다음 프로세스로 옮긴다.
q는 메모리 버스 이동 시간에 1000~1만배 정도의 시간을 가져야 의미가 있다. q가 너무 크면 FCFS랑 동일하고, q가 너무 작으면 cpu 일은 못하고 대부분 context switch 시간만 차지한다.
○ 우선순위 스케줄링
우선순위 따라 스케줄링. CPU가 정말 많이 쓰이는건 오히려 우선순위가 작다. 어차피 너무 오래 걸리니 기대를 안한다.
우선순위가 높은 것은 유저한테 가까운 경우 높다. 유저가 큰 영향을 받는 부분.
문제점 : Starvation(기아) : 낮은 우선순위는 평생 실행되지 못할 수 있다.
해결법 : Aging : 시간이 지날 수록 우선순위를 올려준다.
* MIT에서 1973년에 IBM7094를 종료했더니 1967년에 제출된 우선순위가 아주 낮은 프로세스가 아직 끝나지 않았다는 루머가 있다...
- Multi level Queue : 각 우선순위를 레벨별로 큐로 나누고, 우선순위 별로 실행. 동일 우선순위면 보통 Round-Robin
높은 우선순위는 무조건 먼저 실행될 수도 있고, 큐에 따라 time-slice를 배정할 수도 있다.
-Multi level feedback Queue : 큐를 이동할 수 있는 방식으로 CPU를 많이 사용했으면 밑으로 내리고, 너무 오래 기다렸으면 위로 올리기도 한다.
가장 일반적인 CPU 스케줄링 알고리즘이지만 가장 복잡한 CPU 스케줄링 알고리즘이기도 하다.
* Real-Time 스케줄링은 무조건 우선순위다. 일정 bound 내에 완료를 보장. 그렇게 하고 같은 우선순위 내에서는 round-robin, FCFS을 사용. Real-Time을 제외한 작업에 스케줄링은 여기 소개하는 것들을 알아서 잘 사용.
Multiple-Processor Scheduling
○ Multiprocess는 다음 중 하나는 따르는 아키텍쳐이다.
1.Multicore CPUs
2. Multithreaded cores(하나의 코어가 다중 하드웨어 스레드 지원)
3. NUMA systems (Non Uniform Memory Access)
4. Heterogeneous multiprocessing : 모바일 시스템에서 동일한 기능을 하지만 전원 절약을 위해 성능이 떨어지는 코어 같이 가지고 있는 형태
○ Symmetric(대칭) Multiprocessing
-Asymmetric Multiprocessing : 한 프로세서가 스케줄링을 담당한다.
-Symmetric Multiprocessing : 프로세서가 self scheduling
1. common ready queue : Ready queue를 공유해서 race condition이 발생 가능하고, Locking이 필요해서 성능 저하, high contention 유발
2. per-core run queues : 각 코어가 본인의 ready queue를 가지고 있는것 같은 형태. 가장 일반적인 형태로 캐시의 성능이 좋은 반면 workload balancing 알고리즘이 필요하다.
○ Multiple threads per core
한 코어에는 여러 스레드가 존재한다. memory stall을 토대로 여러 논리 프로세서 소유
memory stall 상황을 이용해 CPU가 쉬는 동안 다른일을 시켜 병행을 시킨다.
-Memory stall : CPU가 메모리에서 데이터를 가져오거나 내보낼 때 아무것도 안하는 현상
-Hardware Thread : 코어 속에 스레드 흐름. 코어는 1개더라도 CPU 쉬는 시간 등을 이용해 여러 스레드 흐름 만들 수 있다.
OS view에서는 이게 각각의 CPU로 잡힌다.
○ Load Balancing : workload가 계속 분산되고 적절하게 만드는 작업, 코어가 개별적인 큐를 가지고 있어야만 의미가 있다.
push migration : 특정 task가 주기적으로 검사하는 방식
pull migration : idle processor가 자발적으로 짐을 덜어주는 방식
○ Processor Affinity : 프로세서 선호도(캐시 선호도)
프로세스/스레드가 지정된 CPU에서만 실행되도록 조작.
soft affinity : 노력하지만 no guarantees. Hard affinity : 무조건한다. guarantees.
○ NUMA-aware (Not Uniformed Memory Access 불균일 기억 장치 접근)
컴퓨터 메모리 설계 방법 중의 하나로, 프로세서가 로컬 메모리, 가까운 메모리에 적재하여 속도를 올린다
○ Event latency - 이벤트가 발생해서 그것을 인지하고 서비스를 시작할 때까지 지연되는 시간
2가지 종류의 지연이 real-time systems performance에 영향을 끼친다.
1. Interrupt Latency : Interrupt 도착 하고 ISR(Interrupt Service Routine) 시작 까지 가는데 걸리는 시간
2. Dispatch Latency : Context Switching 딜레이 : Conflicts + dispatch 시간
Priority - based Scheduling
○ real-time scheduling은 스케줄러가 preemptive, priority-based 스케줄링을 지원해 줘야 한다.프로세스는 주기적인(Periodic) 체크가 있다.
*Admission - control algorithm : 프로세스가 스케줄러에게 deadline을 요총했을 때
1. 받아들여서 주어진 시간 내에 종료를 보장
2. 불가능하기 때문에 거부
를 결정하는 알고리즘
○ Rate Monotonic Scheduling
Periodic(주기) 프로세스를 스케줄링. static priority policy + preemption하다.
무조건 짧은 주기 = 높은 우선순위를 가지는 정적인 우선순위 정책을 가지고, 정적인 우선순위 사용 알고리즘 가운데 optimal(최적의) 알고리즘이다.
우선순위가 높으면(deadline이 더 가까우면) preemptive하게 바로 전환한다.
위 사진에서 스케줄링이 불가능한(deadline 초과)이유는 Rate-monotonic scheduling 알고리즘은 N개의 프로세스를 스케줄링할 때, CPU Utilization이 N(2^(1/N) -1)을 넘을 수 없다.
CPU Utilization for Pi = ti / pi
○ EDF (Earliest Deadline First Scheduling)
Deadline을 우선순위 기준으로 잡은 알고리즘으로, process가 주기적일 필요가 없으며, CPU burst가 일정할 필요도 없다.
오직 스케줄러에게 deadline을 미리 알려줄 수만 있으면 된다.
EDF는 이론적으로 최적의 알고리즘으로 CPU Utilization을 100%로 올릴 수 있으나, 현실에서는 Context switching 등 추가 비용으로 인해 100% 성취를 하지 못한다.
○리눅스 스케줄링 (Ver2.5, 과거) - O(1) Scheduler
○ 리눅스 스케줄링(Ver2.6.23+, 현재) - CFS (Complete Fair Scheduler)
CFS는 우선순위를 직접 할당하지 않고 virtual run time에 따라 동적으로 조정한다. CFS는 runnable task 중 vruntime이 가장 작은 것을 먼저 한다.(time quantum 동안은 보장)
Quantum은 nice value(-20~+19)를 베이스로 계산된다. > 고정이 아니다
같은 CPU 시간을 사용해도 우선순위가 낮은 프로세스의 가상 런타임은 높은 프로세스의 가상 런타임보다 크게 계산된다. 가상 런타임이 작으면 우선순위가 높다.
새로 들어온 task 들은 vruntime이 0.
○ Real time tasks have static priorities
0~99까지는 real-time 쪽이고, 100~139를 Normal tasks 들이 우선순위로 쓰는데, CFS에서 nice value가 100이 -20, 139가 +19이다.
○Windows Scheduling
Dispatcher가 Scheduler다.
32 level의 우선순위 scheme이 있다.
Variable Class는 1-15, real-time class 는 16-31이며 variable class는 우선순위를 변경할 수 있다.
우선순위 클래스는 REALTIME_PRIOIRTY_CLASS,HIGH_PRIORITY_CLASS ... 등등이 있고,
클래스 내에도 상대적인 우선순위 TIME_CRITICAL, HIGHEST, .. 등이 있다.
Variable priority 스레드가 I/O 대기가 완료되면 dispatcher는 우선순위를 향상시킨다. = I/O bound thread가 CPU-bound 스레드보다 우선한다는 의미
키보드 I/O > 디스크 I/O
*우선순위가 낮은 클래스도 내부 Realative prioirty에 따라 우선순위가 조금 높은 클래스보다 더 우선될 수 있다. 즉 클래스가 절대적인 차이는 아니다.
'강의 > OS' 카테고리의 다른 글
OS - Thread (0) | 2023.06.29 |
---|---|
OS - Processes (0) | 2023.06.27 |
OS - Structure (0) | 2023.06.26 |
스레드 (4장)-시험 요약 (1) | 2023.04.20 |
프로세스(3장)시험 요약 (1) | 2023.04.20 |