ready queue에 있는 프로세스들 중, 어느 것을 cpu에 올릴 것인지 결정하는 것.
CPU 스케쥴링의 목적은, 멀티 프로그래밍. (한 프로세서 안에서 여러 프로세스를 동시에 돌리는 것.)
즉, CPU가 쉬지 않고 열심히 돌아갈 수 있도록 관리하는 것이다. (CPU 효율 극대화)
정확히 말하면, 커널 스레드가 OS에 의해 스케쥴링 된다.
(그러나 프로세스 스케쥴링 이라는 말도 스레드 스케쥴링과 혼용한다.)
◆ 프로세스 실행 - CPU burst , I/O burst
프로세스 실행되면 CPU를 쓰는 시간(CPU burst) 및 I/O를 대기하는 시간(I/O burst)이 번갈아가면서 일어난다.
CPU burst: CPU만 연속적으로 쓰면서 instruction을 실행하는 일련의 단계
I/O burst: I/O를 기다리는 단계
모든 프로그램은 CPU burst, I/O burst의 연속이지만, 프로그램의 종류에 따라서 각 burst의 빈도나 길이가 다르다.
I/O bound job: CPU를 짧게 쓰고 중간에 I/O가 끼어드는 job = CPU burst가 짧은 경우 (manyshort CPU bursts)
이러한 경우가 많음
= 중간에 I/O burst가 끼어드는 경우가 많음
CPU bound job: CPU만 오랫동안 쓰는 job = CPU burst가 긴 경우 (few very long CPU bursts)
이러한 경우의 빈도가 매우 낮음
ex) 계산 위주의 job
※ 대부분의 CPU 시간은 I/O bound job이 다 쓴다? ㄴㄴ I/O bound job은 너무 짧게 짧게 난도질을 당해서 빈도가 높을 수밖에 없는 특성을 가짐. 반대로 CPU bound job은 당연히 빈도가 낮을 수밖에 없음(길게 한번에 가니까) 실제로 CPU는 CPU bound job이 많이 쓰고, I/O bound job은 CPU를 짧게, 잦게 쓴다 고 해석하는 것이 타당함
컴퓨터 안에는 I/O bound job, CPU bound job이 섞여 있으므로 적절한 CPU scheduling이 필요함
I/O bound job이 문제가 됨!!
interactive한 job임
CPU bound job이 CPU를 잡고 놓지 않으면 I/O bound job이 너무 오래 대기하게 됨 → 사용자가 답답해짐
가능하면사람과 interact하는 I/O bound job에 CPU를 우선적으로 주는 것이 필요함
◆ CPU Scheduler
CPU 스케쥴러는 특정 알고리즘을 사용해 ready queue에서 프로세스를 선택하고, CPU 코어를 할당한다.
스케쥴링 옵션으로 두 가지 종류가 있다.
Preemptive scheduling (강제 회수) 내 CPU burst가 끝나지 않았더라도 다른 애들이 뺏을 수 있도록 함
Nonpreemptive scheduling (자진 반납) 프로세스가 실행중일 때, 다른 애들에 의해서 CPU를 빼앗기지 않도록 함
대부분의 최신 OS는 Preemptive 방식을 사용한다. (Windows, MacOS, Linux, UNIX)
4가지의 경우 프로세스를 새로 선택해야 한다.(scheduling decision)
running → wating state(I/O를 받으려고 기다림)
running → ready state(interrupt가 발생했을 경우)
wating → ready state
terminate
1번과 4번 case에서는 nonpreemptive하다. 즉, 중간에 끊기지 않은 경우
2번과 3번 case에서는 preemptive하거나 nonpreemptive 하다.
◆ Dispatcher
Dispatch : 스케쥴러가 선택한 프로세스의 context 레지스터 값을 cpu 레지스터로 로드하여 실행시킬 준비를 하는 과정.
Dispatch latency : 이전 프로세스의 runnning 상태가 끝나는 시점부터 다음 프로세스가 running이 시작되는 그 시점까지의 지연 시간. 즉 context switch 하는 시간 동안의 순수 오버헤드를 의미한다.
Scheduler : Ready queue의 프로세스 중에서 다음에 실행할 프로세스를 결정함 Dispatcher : 스케쥴러가 선택한 프로세스에다 실제로 cpu를 할당함
◆ Scheduling Criteria
스케쥴링 알고리즘 평가 기준
그러면, 어떤 스케쥴링 알고리즘이 좋은 알고리즘일까?
다음의 비교 기준들을 통해 최적의 알고리즘을 선정할 수 있다.
<높으면 좋음>
CPU Utilization : CPU 사용률. CPU가 놀지 않고 프로세스들을 돌리는 비율. (0~100%)
Throughput: 단위시간 당 처리량 (실행한 Instruction의 수)
<낮으면 좋음> - 시간에 관한 것들
Turnaround Time : 특정 프로세스가 메모리에 로드가 되고 종료될 때까지의 총 소요 시간 (ready queue에서 대기하고, CPU를 사용하고, I/O를 기다리는 모든 시간을 포함한다.)
순서에 따라 waiting time이 바뀐다. 2번과 같이 가장 긴 P1을 가장 마지막에 실행하면 앞 애들의 waiting time이 줄어듦
Convoy effect
※ Convoy effect: 굉장히 짧은 프로세스들이 긴 프로세스들 뒤에 있으면 쌉손해 🚚🚗🚗🚗 => 평균 대기시간이 길어지게 됨
◆ Shortest-Job-First (SJF)
burst time이 짧은 작업들을 먼저 스케쥴링하는 방식
유저와 상호소통을 하는 interactive한 시스템의 경우 waiting time이 짧아야 response time이 줄어든다.
우선적으로 response time이 줄이려면 수행시간이 적은 것을 먼저 실행시켜야 한다.
nonpreemptive 한 방식
각각의 프로세스가 CPU를 얼마나 사용할 지 예측한 후, 예측한 CPU burst time이 가장 짧은 작업을 먼저 스케쥴링 해주는 방식. (예측 방식: 그 작업의 이전 CPU burst 길이를 기반으로 예측한다.)
평균 waiting time 측면에서 봤을 때, optimal한 알고리즘이다. (최적; 유일하지는 않지만, 더 나은 것은 없다)
ex)
⚠️문제점:
정확한 시간 예측 불가
CPU burst time이 긴 작업들의 Starvation 발생 가능성
■ Shortest-Remaining-Time-First(SRTF)
남아있는 burst time이 제일 짧은 작업을 먼저 스케쥴링 하는 방식
SJF의 preemptive한 버전이다.
주의) 이전에 실행 끝난 시간이나, arrival time을 고려해서 waiting time을 계산하기!!
◆ Round Robin (RR)
한번에 CPU를 사용할 수 있는 최대 시간(time quantum)을 정해놓고, 프로세스들이 돌아가면서 일정 시간동안 CPU를 사용하는 방식
preemptive
time quantum이 끝나면 다시 ready queue로 돌아감.
공평한 방법이므로 response가 더 좋음
ㆍtime quantum : 프로세스가 한 번 스케쥴링 되었을 때 CPU를 쓸 수 있는 최대 시간.
보통 10~100 ms 정도이다. → 최대 시간이므로, 타임 퀀텀보다 더 적게 쓸 수도 있음!!
최대시간만큼 쓸 수 없는 상황: I/o요청이나 타이머 인터럽트를 제외한 다른 인터럽트가 걸렸을 때
※ 타이머 인터럽트에 설정된 시간이 타임 퀀텀이다.
ex)
※ 타임 퀀텀을 얼마로 잡을 것인가?
타임 퀀텀을 너무 길게 한다면? : 들어온 순서대로 FCFS와 똑같다.(타임 퀀텀 안에 다 처리함)→ 페어하지만 구림.
타임 퀀텀을 0에 수렴하게 짧게 한다면? : 프로세스가 동작하는 시간보다 더 많은 시간을 스케쥴링, context switching 하는데 사용해야한다. 이에 따라 오버헤드가 엄청 커짐 → cpu utilization 감소
⇒ 따라서 타임 퀀텀을 적절하게 설정하는 것이 중요하다!! 일반적으로 타임 퀀텀은 CPU burst time의 평균 정도로 둔다. (보통 10~100ms정도)
⚠️문제점:
적절한 타임 퀀텀을 어떻게 설정하느냐에 따라 스케쥴링의 성능이 완전히 달라짐
불필요한 오버헤드가 생길 수 있다. ex) 수행되어야 하는 프로세스가 A하나만 남아있고 A의 burst time이 20이다. 그런데 Time Quantum이 4라면 timer interrupt, context switching이 계속 일어나야 함으로 오버헤드가 커진다
📌 엄지손가락의 법칙 (rule of thumb) : 타임 퀀텀에 CPU burst 의 80%를 포함할 수 있도록 설정해야 한다!
◆ Priority Scheduling
Process마다 Priority가 부여되어, 이를 기준으로 스케쥴링하는 방식. (높은 우선순위부터)
preemptive, non-preemptive
스케쥴 대상인 프로세스들 한테 우선순위를 부여하며, 우선순위 높은 녀석이 먼저 스케쥴링 되도록 함. 우선순위 기준을 어떻게 주냐에 따라 성능, 적합한 시스템이 달라짐
flexible : 시스템이 어떤 목적으로 설계하는냐에 따라 상황에 맞게끔 유연하게 조정이 가능
※ 스케쥴링 우선순위 예시
arrival time이 빠른 녀석일수록 무조건 우선 순위를 빨리 준다. → FCFS CPU burst time이 제일 짧은 녀석을 먼저 해주자 → SJF 남아있는 burst time이 제일 빠른 녀석을 먼저 해주자 → SRTF
⚠️문제점:
starvation이 발생 가능하다. 공평하지 못하다! : 우선순위가 낮은 프로세스가 존재할텐데, 계속에서 높은 우선순위를 가진 프로세스만이 ready queue에 도달하면 낮은 우선순위를 가지는 프로세스가 계속 실행을 못하게 될 수도 있다. ⇒ 해결 방안 :Aging → 우선순위가 낮은 프로세스의waiting time이 커질수록우선 순위를 올려준다.
※ Priority Scheduling with Round-Robin
우선순위를 기준으로 실행하되, 동일한 우선순위의 프로세스는 라운드 로빈으로 실행하는 방식.
◆Multilevel Queue
특성이 비슷한 프로세스들끼리 같은 큐에 분류하고, 큐별로 적절한 스케쥴링 알고리즘을 선택하는 방식.
꽤 좋아보인다.
그러나 고려할 것들이 꽤 있다.
고려할 것들:
큐 개수 : 몇 개의 큐를 정의할 것인가?
큐 별 스케쥴링 알고리즘 : 각 큐에 어떤 알고리즘을 선택할 것인가?
프로세스 분류 방법 : 어떤 프로세스를 어떤 큐에 넣을 것인가? ex) 예를 들어 IDE는 Editing을 할 때는 interactive process에 적합하고, Compile 할 때는 batch process에 적합하다. 이 프로세스가 어떤 큐에 들어갈지는 알고리즘을 제작한 사람이 임의로 설정을 하게 된다. 그럼 과연 이것이 신뢰가능한가?
큐 간의 스케쥴링 알고리즘 : 큐들 사이의 스케쥴링 방식은?
ex) Multilevel Queue with Priority Scheduling
Time Slice:단위 시간을 두고 앞의 80%는foreground뒤에 20%는Background로 둔다.
foreground - interactive(I/O bound) response time이 중요하기 때문에 RR 사용
background - CPU bound 경우. FCFS로 쭉 수행할 수 있도록
⇒ 두 큐 사이는 Priority Scheduling (각각 priority 별로 queue를 두고, 높은 priority 골라서실행하는것)
◆Multilevel Feedback Queue (MLFQ)
Multilevel Queue 와는 달리 Queue의 목적성이 없다. 실제 Process를 큐에 넣어보고 I/O, CPU Bound 중 어디에 더 가까운지 판단하여 그에 맞는 큐에 넣는다.
멀티 레벨 큐에서 조금 더 발전된 방식으로, 대부분 덩치 있는 OS들에서 채택하고 있는 방법이다.
각작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의특성에 따라 동적으로 우선순위를 부여한다. => 기존 Multilevele queue에서의 문제점 - IDE 같은 경우의 문제점을 해결 가능.
고려할 것들:
큐 개수 :몇 개의 큐를 정의할 것인가?
큐 별 스케쥴링 알고리즘 :각 큐에 어떤 알고리즘을 선택할 것인가?
프로세스 분류 방법 :어떤 프로세스를 어떤 큐에 넣을 것인가?
프로세스 승급 기준 :다음 큐로 넘어가는 기준
프로세스 강등 기준 :이전 큐로 돌아가는 기준
ex)
그림과 같이, 세 큐 Q0, Q1, Q2가 있다고 하자. 세 큐는 각각 다음 방식으로 스케쥴링한다.
Q0 : RR스케쥴링(타임퀀텀=8)
Q1 : RR 스케쥴링(타임퀀텀=16)
Q2 : FCFS 스케쥴링
이때 프로세스가 스케쥴링되는 과정은 다음과 같다.
새로운 프로세스는 먼저 Q0 대기열로 들어감.
CPU를 얻으면 프로세스는 8밀리초 동안 작동함.
8밀리초 안에 완료되지 않으면 Q1 대기열로 이동함.
CPU를 얻으면 16밀리초동안 작동함.
그래도 완료되지 않으면 Q2 대기열로 이동해 작동함
절반정도 왔으니 잠시 쉬어가는 타임~
◆Multiple-Processor Scheduling
앞서 나온 방법들은 CPU 프로세서가 하나인 경우의 스케쥴링 방식이었다.
이번에는 프로세서가 여러개인 경우의 스케쥴링 방식이다.
■Symmetricmultiprocessing(SMP)
멀티 프로세서를 지원하기 위한 표준 접근 방식이며, 각 프로세서는 스스로 스케줄링할 수 있다
여러 코어를 사용하는 방식에는 두 방식이 있다.
(a) 모든 Task가 공통 큐에 들어있어서, 코어들이 하나씩 꺼내 씀
(b) 각 코어가 고유의 큐를 가지도록 하는 방식
여러 개의 프로세서 코어를 동일한 물리적 칩에 배치하는 것이 최근 추세. → 더 빠르고 더 적은 전력을 소비함.
코어당 여러개의 하드웨어 스레드를 쓰는 방식도 증가하고 있음. → 메모리 검색이 수행되는 동안에도 다른 스레드에서 계산을 진행할 수 있다.
※ Memory stall : 메모리에서 데이터를 가져오는 동안 코어가 잠시 동작을 멈추는 것을 의미함.
■ Chip-multithreading (CMT)
각 코어에 여러 개의 하드웨어 스레드를 할당하는 방식
인텔에서는 CMT를 hyperthreading이라고 부름.
각 코어에 여러 개의 하드웨어 스레드가 돌아가는 것처럼 보이지만, 사실은 Parallel하게 실행되는게아니라,Hardware가contextSwtching처럼thread를 빠르게전환하는것.
코어당 하드웨어 스레드가 2개인 쿼드 코어 시스템이라면, OS 입장에서 8개의 논리 프로세서가 있는 것.
작업관리자 들어가면 있는 이런 정보 보임
※ 멀티스레디드 멀티코어 시스템에서 스케쥴링 방식 (2단계) 1. 운영 체제 - 논리적 프로세서에서 실행할 소프트웨어 스레드를 결정함. (sw 스레드) 2. 각 코어 - 물리적 코어에서 실행할 하드웨어 스레드를 결정함 (hw 스레드)
◆Multiple-Processor Scheduling - 고려할 사항들
멀티 프로세서 스케쥴링을 할 때 고려할 사항들이 있다.
그중 다음 두 가지를 볼 것이다.
Load Balancing
Processor Affinity
◆Multiple-Processor Scheduling - Load Balancing
멀티 프로세서 스케쥴링에서, 특정 프로세서가 너무 많은 프로세스를 돌린다 싶으면, 스케쥴러가 적절히 균등하도록 분배해주는 행위
프로세스는 현재 돌고있는 프로세서 위에서 address space등의 메모리를 차지할 것이다.
이 때, 다른 프로세서의 메모리에 있는 데이터를 참조해한다면, 시간이 오래 걸릴 것이다.
따라서자신이 현재 돌고있는 프로세서의 메모리와,자신이 접근하려는 데이터가 있는 메모리를 같도록 만들어줄 때 Processor Affinity를 활용하기도 한다. 또는 프로세스 프로파일링 할 때 사용함.
다음 두 종류의 프로세서를 지정 방식이 있다.
Soft affinity : 권고사항. "최대한 코어1에 배치해줬으면 좋겠는데, 꼭 여기서만 해야 하는 건 아니야~" priority를 높여주는 등의 노력은 하지만, 해당 프로세서에서의 실행을 보장할 수는 없음.
Hard affinity : 특정 프로세서에서만 돌도록 완전히 보장해줌. "무조건 이 프로세스는 코어1에서 실행돼야 해!!!! "
◆ Real-Time CPU Scheduling
실시간으로 CPU를 스케쥴링하는 방법이다.
실시간 스케쥴링 시스템은 크게 두가지로 나뉜다.
Soft real-time system : 어떤 Task를 데드라인 안에 끝내고자 하는 게 목표임. 데드라인이 끝나더라도 결과값이 어느정도 가치를 가짐.
Hard real-time system :어떤 Task를무조건 데드라인 안에 끝내야 함. 못 맞출 바엔 차라리 스케쥴링을 안하는 게 나을 정도로 데드라인이 치명적인 시스템. ex) 자율주행 자동차
real-time 스케쥴링을 하려면, 스케쥴러는 다음 스케쥴링 방식을 지원해야 한다.
preemptive. 강제 회수가 가능해야 하고
priority-based scheduling. 우선순위 기반 스케쥴링을 해줘야 한다.
Real-time 스케쥴링에서, 한가지 특성이 더 등장한다.
Aperiodic : 언제든 task가 발생할 수 있음.
Periodic : task가 주기적으로 발생함.
■ Periodic
Real-time system에서 특정 프로세스가 periodic하게(주기를 가지고 반복적으로) 들어온다고 생각해보자.
이때 주기를 p, deadline을 d, 프로세싱되는 시간을 t라고 하면, 다음이 성립해야 한다.
0 ≤ t≤ d ≤ p
이 때, periodic process의 rate는 1/P이다.
◆ Real-Time CPU Scheduling - Periodic Task Scheduling
periodic task들을 위한, 다음 두가지 스케쥴링 알고리즘을 살펴볼 것이다.
둘다 preemptive한 방식이다.
Rate Monotonic Scheduling (RM)
Earliest Deadline First Scheduling (EDF)
◆ Rate Monotonic Scheduling (RM)
Rate가 높은 프로세스 우선 스케쥴링 (== 주기가 짧은 프로세스 우선 스케쥴링)
Period의 길이에 따라 priority가 부여됨. (rate = 1/P)
주기가 짧으면 priority가 높음
주기가 길면 priority가 낮음
Static priority : 이 방법은 프로세스가 들어온 순간마다 priority를 판단하는 것이 아니라, 처음부터 rate를 사용하여 priority를 정해주고, 그 priority그대로 쭉 스케줄링 해주는 것이다.
ex) 스케쥴링 성공
데드라인이 주기와 같은 P1, P2가 있다.
P1은 주기가 50초이고, 20초 동안 processing한다.
P2는 주기가 100초이고, 35초 동안 processing한다.
0에서 P1과 P2이 들어왔다고 하자.이 경우, RMS를 적용하면 결과는 아래와 같다.
처음 P1과 P2가 들어왔을 때, P1이 주기가 짧으므로(=rate가 높으므로) P1을 먼저 스케줄링해준다. 20초간의 스케줄링이 끝나면 P2가 스케줄링된다. P2가 스케줄링 되는 도중 50초에 P1이 들어오게 되고, P1이 더 rate가 높으므로 P1이 preemption해서 스케줄링된다. P1이 끝난 70초에 P2가 마저 스케줄링 된다.
ex) 스케쥴링 실패
데드라인이 주기와 같은 P1, P2가 있다.
P1은 주기가 50초이고, 25초 동안 processing 한다.
P2는 주기가 80초이고, 35초 동안 processing 한다.
0에서 P1과 P2이 들어왔다고 하자. 이 경우, RMS를 적용하면 결과는 아래와 같다.
처음 P1과 P2가 들어왔을 때, P1이 P2보다 rate가 높으므로 priority가 높은 것을 확인할수 있다. 그래서 P1 먼저 실행되고, P2가 실행되다가 50초에 다시 P1이 스케줄링된다. 75초에 다시 남은 P2가 스케줄링 되고있는데, 80초에 주기가 돌아와서 첫번째 P2 실행이 끝나기 전에 다음 P2가 스케줄링된다. 이 경우, deadline을 맞추는데 실패한 것이다.
◆ Earliest Deadline First Scheduling (EDF)
데드라인 임박한 프로세스 우선 스케쥴링
deadline에 따라 priority가 부여됨.
deadline이 임박하면 priority가 높음
deadline이 느긋하면 priority가 낮음
Dynamic priority :이 방법은 RMS처럼 static하게 priority를 주는 것이 아니라, task들이 들어올때마다 deadline을 비교해보고 priority를 정하는 방식이다
ex)
데드라인이 주기와 같은 P1, P2가 있다.
P1은 주기가 50초이고, 25초 동안 processing 한다.
P2는 주기가 80초이고, 35초 동안 processing 한다.
0에서 P1과 P2이 들어왔다고 하자.이 경우, EDF를 적용하면 결과는 아래와 같다.
처음에는 데드라인이 더 짧은 P1부터 실행한다. 25초 이후 P2를 실행한다.
50초에 P1의 주기가 돌아서 다시 들어오고자 했다. 그러나 이때 P1의 데드라인은 50초 남았고, P2의 데드라인은 30초 남은 상황이므로, 그대로 P2부터 계속 실행한다.
RM 보다 유휴시간이 적지만, ready queue에 process가 들어올 때마다 deadline을 확인해야 해서 overhead가 크다.
