CPU Scheduling이란?
멀티프로그래밍(여러개의 프로세스가 동시에 메모리에 로드 되어 있고 cpu를 선점해 concurrent하게 실행되는 것)을 사용하는 os에서는 필수이며, concurrent하게 실행되도록 하려면 시분할을 해서 cpu 자원을 끼워 넣어 cpu 사용률을 높일 수 있다.
프로세스는 아래의 두 가지 상태가 존재할 수 있다.
- CPU burst(running 상태)
- I/O burst(waiting -> ready 상태)
그런데 cpu burst 시간이 많은 경우는 별로 존재하지 않으며, I/O-bound 상태가 CPU-bound 상태보다 많이 등장하게 된다.
CPU Scheduler
- 메모리에 로드된 프로세스 중에 어떤 프로세스에 cpu를 할당할 것인 지를 결정한다.
👉 ready 상태에 있는 프로세스 중에서 CPU를 할당해줄 수 있는 프로세스를 선택해야 한다.
어떻게 다음 프로세스를 결정할까?
대기하고 있는 것 중 가장 바쁜 것을 먼저 할당해 주어야 하기 때문에 "우선순위 큐"를 이용해야 한다.
선점형(preemptive) vs 비선점형(non-preemptive)
- 선점형: 강제로 cpu에서 나오게 한다.
- 비선점형: 자발적으로 cpu에서 나오게 한다.
Non-preemptive
- 자발적으로 끝나기 전까지는 cpu를 해당 프로세스가 쓰도록 한다.
Preemptive
- 스케줄러가 cpu를 선점하고 있는 프로세스를 쫓아낼 수 있다.
CPU-scheduling시의 Decision Making
- running -> waiting 상태로 가는 경우
- running -> ready 상태로 가는 경우
- waiting -> ready 상태로 가는 경우
- 프로세스가 termination 하는 경우
👉 1 & 4: non-preemptive
👉 2 & 3: preemptive or non-preemptive(현대적인 스케줄링은 preemptive를 사용해서 선택권을 높인다.)
dispatcher
dispatcher의 실행 과정
1. context를 다른 프로세스로 넘겨주고
2. 다른 프로세스를 user mode로 바꿔준 후
3. user program을 재개 하기 위해서 적당한 위치로 ready 상태였던 프로세스를 점프시킨다.
- CPU core의 컨트롤을 넘겨주는 것을 말한다.
- 현재 프로세스를 running -> ready로 바꾼 후 다른 프로세스를 ready -> running이 되는 context-switching을 해주는 모듈을 말한다.
- 크게 보면 scheduler 안에 포함되어 있다.
- dispatcher는 context switch가 일어날 때마다 필요하기 때문에 매우 빨라야 한다.
👉 dispatch latency(지연시간) 는 한 프로세스를 멈추고 다른 프로세스를 running 상태로 만드는 데 걸리는 시간인데, 이 시간이 짧아야 한다.
CPU Scheduling을 어떻게 할까?
Scheduling시의 목표
- CUP utilization: CPU를 가장 많이 사용할 수 있도록 한다.
- Throughput(단위 시간 내 프로세스의 완결 수)을 높인다.
- Turnaround time(프로세스의 실행에서 종료될 때까지의 시간) 최소화
- Waiting time(어떤 프로세스가 ready queue에서 대기하는 시간) 최소화
- Response time 최소화(UI에서 사용자가 기다려야 하는 시간 최소화)
문제점: 레디 큐에 있는 프로세스 중 어느 프로세스에 CPU를 할당할 것인가?
- FCFS(First-come, First-served): 먼저 온 프로세스를 가장 먼저 할당해 준다.
👉 현재는 사용하는 방법이 아니다. - SJF(Shortest Job First): 남은 시간이 가장 짧은 작업에 먼저 cpu를 할당한다.
👉 위의 두 방법은 프로세스를 cpu에 전부 할당하는 것이다. - RR(Round-Robin): 시분할과 관련되어 있는 방법이다.
- 정해진 시간 만큼만 cpu를 할당한다.
- Priority-based: Round-Robin을 쓰면서 우선순위를 부여해 선점한다.
- MLQ(Multi-Level Queue): 어떤 경우에는 이렇게, 또 어떤 경우에는 저렇게 실행하도록 한다.
- MLFQ(Multi-Level Feedback Queue): cpu 선점하다가 프로세스 실행에 문제가 생기면 대기 상태로 전환
FCFS scheduling
- CPU를 먼저 요청한 프로세스에 무조건 먼저 CPU를 배정한다.
- FIFO queue를 이용하면 된다.
- 가장 간단한 CPU scheduling 알고리즘
- FCFS를 이용하면 평균 대기 시간이 최소가 아니며 CPU-burst time이 얼만 지에 따라서 달라지게 된다.(가장 먼저 들어온 프로세스의 실행 시간이 매우 길면 뒤의 것들이 시간이 매우 짧더라도 일단 기다려야 하기 때문이다.)
👉 이를 Convoy Effect(똥차 효과!)라 한다.
SJF scheduling
- shortest-next-CPU-burst-first scheduling
- 각 프로세스의 다음 CPU burst가 가장 작은 것에 먼저 CPU를 할당한다.
- 하지만, next CPU burst를 미리 알 수 있는 방법이 없다.
👉 따라서, 예측을 통해 근사적으로 구해볼 수 있는데 과거의 CPU busrt 길이에 대한 지수적 평균값을 이용한다.
👉 '이론적으로만' 최적의 알고리즘이다. - SJF는 preemptive할 수도, non-preemptive 할 수도 있다.
👉 레디 큐에 들어온 프로세스의 길이가 짧으면 현재 cpu를 점유한 프로세스 대신 들어온 프로세스가 cpu를 선점하도록 할 수 있다. - 선점형 SJF는 SRTF scheduling이라고도 볼 수 있다. 즉, 남아 있는 시간이 짧을수록 더 먼저 cpu를 점유하는 것과 같기 때문이다.
RR scheduling
- 시분할 해서 time quantum(time slice)만큼을 할당해서 time quantum만큼 실행하면 무조건 cpu에서 나가도록 함
👉 time quantum은 보통 10ms 정도이다. - preemptive FCFS이다.
- ready queue는 circular queue로 구현한다.
👉 scheduler가 ready queue를 빙글빙글 돌면서 CPU를 다음 프로세스에게 넘겨주게 된다. - 만약 프로세스의 CPU burst가 one time quantum보다 짧을 수 있다.
👉 그러면 프로세스는 자발적으로 빠져나오게 된다. - 또한, 만약 프로세스가 one time quantum보다 더 큰 CPU burst를 가지면 timer가 interrupt를 걸어 context switch가 일어나며 다시 ready queue의 tail에 들어가 해당 프로세스는 대기하게 된다.
- RR을 이용하면 평균 대기 시간이 길어질 수도 있는데, RR은 SJF와 혼합해서 사용하기 때문에 RR은 스케줄링 알고리즘에 반드시 사용 된다.
- RR 알고리즘은 time quantum 사이즈에 따라 성능이 많이 달라지게 된다.
👉 context switch가 일어날 때 dispatch latency가 존재하기 때문에 time quantum이 너무 작으면 또한 문제가 될 수 있다(context switch가 많이 일어나기 때문). 이 때문에 os의 스케줄링을 최적화 하기 위한 time quantum을 찾아야 한다. - time quantum이 무한대면 FCFS가 된다.
Priority-base scheduling
- 우선순위가 모두 같으면 FCFS가 된다.
- SJF는 priority-based scheduling이라 볼 수 있다.
👉 즉, next CPU burst가 클수록 priority를 낮게 주면 되기 때문이다. - starvation(indefinite blocking) 문제가 생길 수 있다.
👉 blocked process: 레디 큐에 있는 프로세스 중 우선 순위가 낮은 프로세스는 무한정 기다려야 할 수도 있게 된다. 따라서, 시간이 지날수록 우선 순위를 높여주는 것으로(aging) 해결할 수 있다. - preemptive 또는 non-preemptive가 가능하다.
- 만약 우선순위가 같으면 round-robin으로 스케줄링 하는 것이 좋다.
Multi-Level Queue(MLQ) scheduling
- n개의 priority를 배정해서 각 priority에 ready queue를 따로 주는 방법이다.
- 실시간 처리를 해줘야 하는 프로세스들에 높은 우선순위를 주고 batch process와 같은 일반 프로세스에 낮은 우선순위를 주어 우선순위 높은 큐가 비면 그 다음 순위의 큐를 실행한다.
- 하지만, 이 방법 역시 indefinite blocking 문제가 생길 수 있다. 따라서, 우선순위가 높은 큐는 짧은 time quantum을 주어서 빨리 실행이 끝나게 하고 다 실행이 안되면 waiting queue에 들어가게 하며, 그 다음 큐는 조금 더 긴 time quantum을 주고, 마지막 남은 것은 FCFS 알고리즘으로 실행되도록 한다.(나중에 실행될수록 더 긴 time quantum을 준다.)
👉 실제에 가까운 CPU scheduling 알고리즘이 이에 해당한다.
실제로는 스레드를 이용해 scheduling을 한다!
👉 스레드에는 user threads와 kernel threads가 있는데 os는 이 중에서도 kernel threads만 스케줄링 하면 된다. 왜냐하면 user threads는 thread library가 관리하기 때문이다.
👉 many to many 모델로 커널 스레드를 유저 스레드에 매핑 시켜서 유저 스레드에 서비스 해주기만 하면 된다.
👉 즉, 위에 공부한 알고리즘들은 모두 kernel threads에 적용된다고 보면 된다!
Real-time operating system
- window, linux는 실시간 os가 아니다.
- 실시간은 주어진 시간 내에 어떤 task를 완료할 수 있어야 한다.
- soft realtime과 hard realtime으로 나뉜다.
Soft real-time
- critical한 real-time 프로세스가 반드시 주어진 시간 안에 끝나지는 않지만 non-critical한 프로세스보다는 더 빨리 실행되도록 보장한다.
Hard real-time
- task가 반드시 주어진 시간 안에 끝나는 것을 보장한다.
