CPU 스케줄링

CPU 스케줄링을 왜 필요할까요??

멀티 프로그래밍 동시에 프로세스를 사용하기 위해서 필요합니다.

동시에 실행하려는 목적은 CPU가 속도가 굉장히 빨라서 놀고 있기에 컨텍스트 스위칭을 하여 나눠서 시분할을 하여 CPU의 이용효율성을 높이기 위해서입니다.

 

CPU 스케줄링은 메모리에 로드되어 있는 프로세스 중에서 어떤 프로세스에게 CPU을 할당해줄 것인지 결정하는 것이 CPU스케줄링입니다.

 

그럼 어떤 프로세스에게 할당할지 결정하나요??

어떤 프로세스를 선택할지는 여러 스케줄링 기법이 존재합니다.

 

Preemptive와 Non-Preemptive의 차이점을 아시나요??

Non-Preemptive은 비선점형으로 CPU를 프로세스가 선점하게되면 프로세스가 자발적으로 나오거나 프로세스가 종료되는 경우입니다.

즉, 프로세스가 자진해서 CPU를 반납하고 문맥교환이 이루어지는 것입니다.

Preemptive은 선점형으로 CPU를 프로세스가 선점하게 되면 스케줄러가 강제로 나올 수 있도록 할 수 있습니다.

즉, CPU를 빼앗기고 문맥교환이 이루어지는 것입니다.

 

프로세스가 I/O 요청으로인해 wait상태로가거나 terminate으로 인해 종료되게 되면 Non-Preemptive합니다.

프로세스가 running 상태에서 ready 상태로 가게 되는 경우와 wait 상태에서 ready 상태로 가게 되는 경우는 Non-Preemptive 혹은 Preemptive을 결정할 수 있습니다. 그 이유는 타임 아웃을 통해 ready 상태로 강제로 이동될 수도 있으며, wait에서 ready 상태로 가게 됬는데 현재 실행 중인 프로세스보다 ready 상태로 변한 프로세스의 우선순위가 더 크다면 강제로 바뀜이 일어날 수도 있기 때문입니다.

 

Dispatcher에 대해 설명해주세요

CPU 코어의 컨트롤을 넘겨주는 것입니다. running 상태의 프로세스를 ready 상태나 wait 상태로 바꾸며, 다른 프로세스가 CPU을 선점하는 것입니다. 이 것을 콘텍스트 스위칭이라고 하며, 콘텍스트 스위칭을 해주는 모듈을 Dispatcher라고 말합니다.

 

Dispatcher는 콘텍스트를 하나의 프로세스에서 다른 프로세스로 넘겨주고, 유저 모드를 바꿔주며, 새로운 프로세스의 적당한 위치로 옮기는 것입니다.

 

Dispatcher latency가 무엇인지 아시나요??

두 개의 프로세스가 컨텍스트 스위칭이 일어날 때 PCB를 저장하고 가져오는 시간을 말합니다.

이 시간을 CPU를 사용하는 시간보다 짧아지게되면, 

 

스케줄링의 목표가 무엇이라고 생각하시나요??

CPU 이용률을 최대로하는 것입니다. (CPU utilization)

단위 시간 내에 프로세스를 처리하는 하는 양이 얼마나 되는지에 대한 처리량을 높이는 것입니다. (Throughput)

프로세스를 도착하고나서부터 종료될 때까지의 시간을 최소화 시키는 것입니다. (Turnaround time)

ready queue에서 기다리는 시간을 최소화 하는 것입니다. (Waiting time)

반응 시간을 최대한 빠르게 하는 것입니다. (UI에 보여주는 것) (Response time)

 

어떤 프로세스를 할당하는 기법에 무엇들이 있나요?

FCFS 는 First Come, First-Served입니다. 먼저 온 것들을 먼저 처리해주겠다는 것입니다.

SJF는 Shortest Job First입니다. 짧은 Job을 먼저 처리해주는 것입니다.

SRTF는 Shortest Remaning Time First입니다. 남아 있는 Job이 짧은 것을 먼저 처리해주는 것입니다.

RR는 Round-Robin은 시분할을 하여 정해진 시간만큼만 인터리빙하여 사용합니다.

Priority-based는 RR을 사용하는데 우선순위를 부여하여 사용할 수 있습니다.

MLQ, MLFQ 등이 존재합니다.

 

FCFS가 뭔가요??

FCFS는 CPU를 먼저 요청한 프로세스에게 할당을 해주는 것입니다.

FIFO Queue을 활용하여 쉽게 구현이 가능합니다.

예제를 확인해보면, P1의 Burst Time 24 / P2의 Burst Time 3 / P3의 Burst Time 3 인 경우

waiting time : P1 = 0 / P2 = 24 / P3 = 27

Turnaround time : P1 = 24 / P2 = 27 / P3 = 30

여러 경우의 살펴보게 되면 CPU-burst time에 따라 waiting, turnaround time의 극단적인 차이가 나타납니다.

FCFS는 하나의 프로세스가 들어오면 다 처리하기 때문에 Non-Preemptive합니다.

Convoy Effect 때문에 FCFS는 효율적으로 쓰이지 못합니다.

Convoy Effect : short process가 long process 뒤에서 시간 손해를 보는 경우

 

SJF은 무엇인가요??

CPU burst가 가장 작은 프로세스를 할당해주는 것입니다.

예제를 확인해보면, P1 = 6 / P2 = 8 / P3 = 7 / P4 = 3

waiting time : P1 = 3 / P2 = 16 / P3 = 9 / P4 = 0

Turnaround time : P1 = 9 / P2 = 24 / P3 = 16 / P4 = 3

SJF는 Non-Preemptive와 Preemptive 방식이 존재합니다.

평균 waiting time이 최소임을 보장해줍니다.

long process 앞에 short process가 있다면 waiting time 은 감소합니다.

SJF은 next CPU burst의 길이 기준으로 삼는데 next CPU burst의 알수가 없기 때문입니다.

그래서 예측을 이용하여 활용합니다. previous CPU burst을 통해 지수적으로 평균을 내서 사용합니다.

 

SRTF는 무엇인가요??

SRTF는 SJF에서 Preemptive 방식입니다.

현재 프로세스를 실행중인데 남은 burst time보다 더 짧은 Burst time을 가지고 있으면 그자리를 차지하게 됩니다.

waiting time : P1 = (10-1) = 9 / P2 = (1-1) = 0 / P3 = (17-2) = 15 / P4 = (5-3) = 2

Turnaround time : P1 = 17 / P2 = 4 / P3 = 24 / P4 = 7

 

RR는 무엇인가요??

라운드 로빈 스케줄링이라고 부릅니다.

Preemptive FCFS with time quantum입니다. 시간 단위를 두고 시간 단위까지만 실행하고 바뀌는 형태입니다.

time quantum은 작은 시간 단위로 주어야 합니다.

time quantum보다 CPU burst가 작다면 프로세스가 자발적으로 나오게 되면서 다음 프로세스에 대해 스케줄링할 것입니다.

time quantum보다 CPU burst가 크다면 OS에게 인터럽트를 발생시켜 콘텍스트 스위칭이 일어날 것입니다.

예제를 확인해보면, P1 = 24 / P2 = 3 / P3 = 3의 burst time을 갖고 time quantum이 4milliseconds라면,

waiting time : P1 = (10-4) = 6 / P2 = 4 / P3 = 7

Turnaround time : P1 = 30 / P2 = 7 / P3 = 10

RR은 Preemptive합니다.

라운드 로빈 스케줄링은 time quantum을 얼마나 주느냐에 따라 성능이 달라집니다.

quantum을 무한대 증가시키면 FCFS가 될걸고 엄청나게 짧게 쪼갠다면 콘텍스트 스위칭만 발생하는 현상만 나타납니다.

 

Priority-base가 무엇인가요??

SJF으로만 하기엔 어려움이 존재하니 우선순위를 부여하여 활용하는 것입니다.

각 프로세스에 우선순위를 부여하는 것입니다. 우선순위가 같다면 FCFS을 이용하게 될것입니다.

우선 순위는 낮은 숫자가 높은 우선순위를 갖습니다.

Preemptive은 인터럽트 우선순위가 높은 순이되며, Non-Preemptive은 하던것을 진행을 하다하고 나옵니다.

 

Starvation problem이 무엇인지 아시나요??

우선수위가 낮은 프로세스가 계속 높은 우선순위의 프로세스의 인터럽트로 실행되지 않는 경우, 한 프로세스라도 전혀 실행되지 않는 것입니다.

이 문제는 Aging solution으로 해결이 가능합니다.

 

그럼 Aging solution이 무엇인데요??

프로세스가 낮은 우선순위가 계속해서 대기하게 되면, 천천히 우선순위를 높혀주어 언제간 수행될 것을 보장해주는 것입니다.

 

RR와 Priority 스케줄링 하시나요??

RR 방식에 높은 우선순위를 합쳐서 진행하는 것입니다.

만약 같은 우선순위를 가지고 있다면 라운드 로빈을 활용하면 됩니다.

 

Multi-Level Queue(MLQ)가 무엇인지 아시나요??

어떤 프로세스냐에 따라서 여러 종류의 그룹으로 나누고 여러 개의 큐에 다양한 알고리즘을 적용하는 스케줄링 기법입니다.

사용자와 상호작용적으로 작동하는 프로세스는 요구되는 응답시간이 백그라운드 프로세스에 비해 더 짧을 것입니다. 그래서 결과가 브라우저가 늦게 나타나면 짜증나서 사용자가 ㄷ꺼버립니다. 하지만 영화 다운로드 같은 경우는 백그라운드 작업은 실행시켜놓고 기다리기만 합니다.

뒤에서 돌아가는 프로그램보다 내가 하고 있는 작업이 반응이 느릴 때 답답하니 여러 개로 쪼개서 다른 스케줄링 기법을 적용하는 것입니다.

 

Multi-Level Feed Queue와 Multi-Level Queue차이가 무엇일까요??

MLQ은 각각 프로세스의 중요도에 따라 큐로 나누고 각 큐에서 다른 알고리즘을 적용해 효율을 높일 수 있는 장점이 있지만, 한 번 해당 큐에 들어가면 프로세스는 다른 큐로 이동되거나 변경되는 것이 거의 불가능하다는 단점이 존재합니다. 오버헤드가 낮은 대신 유연하지 못합니다.

프로세스마다 중요도를 추측해서 분류할 것입니다. 이부분에서 잘못된다고 하면 변경할 수 없는 유동적이지 못한 단점이 존재하느 ㄴ것입니다.

MLFQ은 MLQ와 다르게. 프로세스가 큐 사이 이동이 가능하며, 분류되는 방식의 차이도 존재합니다.

 

Multi-Level Feed Queue는 무엇인데요??

다단계 피드백 큐는 5가지 변수에 의해 정의됩니다. 큐의 번호, 각각의 큐의 스케줄링 알고리즘, 작업을 보다 높은 우선순위의 큐로 격상시키는 시기 결정 알고리즘, 작업을 보다 낮은 우선순위의 큐로 격하시키는 시기 결정 알고리즘, 프로세스들이 어디 큐에 들어갈 것인가를 결정하는 알고리즘으로 됩니다.

위의 동작 방식은, 어떤 프로세스가 중요한지 모르니 똑같이 시작합니다. MLQ는 우선순위에 따라 들어가는 입구가 달랐지만, MLFQ는 모든 프로세스들이 가장 위의 큐에 들어갑니다.

제일 위에 있는 큐는 RR으로 스케줄링하는데 time quantum은 8입니다. 자신의 time quantum을 다 채우지 못한 process는 그대로 두고 time quantum을 다 채운 프로세스는 그 밑의 레벨에 있는 큐로 들어갑니다.

특징은 밑에 있는 큐는 time quantum의 크기를 첫 번째 있는 큐의 2배로 합니다.

마지막 큐는 백그라운드 프로세스가 보통 그러하듯이 FCFS로 처리합니다.

 

위에서 설명한 왜 밑에 레벨 큐로 내려가고 그대로 있고 그런가요??

사용자와 상호협력적이지 않은 백 그라운드의 프로세스는 CPU burst가 매우 큰 특징을 이용한 것입니다.

만약, 게임 다운로드하는데 1시간 걸린다고 합니다. 그럼 우리는 백 그라운드로 돌려놓고 인터넷 서치를 할 것입니다.

즉 바로 처리해야할 일은 인터넷 서치입니다.

즉, 게임 다운로드처럼 CPU를 계속 써야하는 CPU burst가 큰 프로세스를 우선순위가 낮다고 판별하는 것입니다.

사용자와 상호작용할 가능성이 높은 프로세스, 입출력을 필요로 하는 것, CPU 처리가 I/O 작업이랑 번갈아가며 일어나므로 CPU Burst가 작다는 특징이 있습니다. 이를 우선순위가 높다고 합니다.

 

time quantum을 다 채웠다는 것은 CPU burst process일 가능성이 높은 것입니다. 그래서 아래 큐로 내려보내는 것입니다. time quantum을 16으로 해도 다 채웠다면 CPU bound process라고 생각하고 아예 밑으로 내려가서 사용자와 동작하는 것이 아니니깐 컨텍스트 스위칭을 안하고 그대로 수행시키는 것입니다. 그래서 FCFS을 이용합니다.

즉, 다음 단계로 넘어갈 수록 CPU burst가 크다는 것이니 우선순위가 점점 낮아지는 것입니다.