운영체제 3주차 과제

CPU 스케줄링에 대해 설명해주세요.

운영체제가 프로세스들에게 효율적으로 CPU 자원을 배분하는 것을 말합니다.

 

 

스케줄러의 종류는 무엇이 있나요?

스케줄러의 종류는 단기, 중기, 장기 스케줄러가 있습니다.

 

단기 스케줄러

어떤 프로세스를 다음번에 실행시킬 지 결정하는 스케줄러 입니다. 어떤 프로세스에 CPU를 할당해줄 지 결정하고, 이 과정은 millisecond 단위로 매우 빠릅니다.

• 프로세스의 상태: Ready -> Running -> Waiting -> Ready

장기 스케줄러

시작(new) 프로세스 중 어떤 것들을 ready queue로 보낼지 결정하는 스케줄러 입니다. 어떤 프로세스에 메모리를 할당해 줄 지 결정합니다. 위 그림에서 admitted가 되고 나서야, ready queue로 프로세스가 이동합니다.

 

• 프로세스의 상태: New -> Ready 

중기 스케줄러

장기 스케줄러와 다르게 모든 프로세스가 ready 상태가 됩니다. 하지만, 메모리에 모든 프로세스가 올라가 있다면 문제가 되기 때문에 중기 스케줄러, 혹은 Swapper를 통해서 일부 프로세스의 메모리를 뺴앗아 성능을 향상시킵니다. 

• 프로세스의 상태: Ready -> Suspended

현대 시분할 시스템에선, 장기 스케줄러가 쓰이지 않고 중기 스케줄러가 사용되는 이유가 있나요?

이유는 과거보다 메모리 양이 크기 때문에 스케줄링을 거치지 않고 빈 메모리에 곧바로 할당할 수 있기 때문이라 합니다. ready queue로 프로세스들을 보낼지 결정하는 것이 자원이나 시간 측면에서 불필요하다고 생각합니다.

 

프로세스의 스케줄링 상태에 대해 설명해주세요

Running

CPU를 잡고 Instruction을 수행중인 상태

 

Ready

CPU를 기다리는 상태(메모리를 할당 받음)

 

Blocked(Wait)

오랜 작업을 하고 있는 상태, ex) I/O등의 이벤트를 기다리는 상태

자신이 요청한 상태가 만족되면, Ready 상태로 됩니다.

Suspended(stopped)

중기 스케줄러 때문에 도입된 스케줄링 상태입니다.

외부(중기 스케줄러, 혹은 사람)에서 프로세스의 실행을 강제로 정지시킨 상태입니다. 프로세스가 디스크에 swap out이 되며, 외부에서 resume을 해줘야 Ready 상태로 됩니다.

ex) 메모리에 너무 많은 프로세스가 있을 때, 사용자가 프로그램을 일시 정지 시킨 경우

 

preemptive/non-preemptive 에서 존재할 수 없는 상태가 있을까요?

사용자가 강제로 프로세스의 실행시킨 상태..??

 

 

선점형 스케줄링과 비전형 스케줄링의 차이가 무엇인가요?

선점형 스케줄링 (preemptive scheduling)

프로세스가 CPU를 할당받아서 실행중이여도, 운영체제가 이를 빼앗고 다른 프로세스에 CPU를 할당할 수 있는 방식입니다. 

비선점형 스케줄링 (non-preemptive scheduling)

선점형과는 다르게, 프로세스가 실행중인 경우에 운영체제가 빼앗지 못하고 프로세스의 사용이 끝날 때 까지 기다려야 합니다. 

선입선출 스케줄링(FCFS)에 대해 설명해주세요.

First-Come-First-Served

단순하게 ready queue에 삽입된 순서대로 프로세스를 처리하는 방식이며, 비선점형 스케줄링 방식으로 동작합니다.

위 방식은 효율적이지 않은데, 그 이유는 Queue의 앞에 CPU 사용시간이 긴 프로세스가 있다면 다른 프로세스는 계속 대기해야 합니다.

 

위 그림에서 볼 수 있듯이, Burst Time이 긴 P1이 먼저 CPU를 사용한다면, P2와 P3가 그만큼 대기를 해야하기 때문에 평균 대기 시간은 17초가 나왔습니다. 반면에, P1이 가장 나중에 실행된다면, 평균 대기 시간이 3초로 매우 짧아집니다.

 

수행 시간이 긴 프로세스 뒤에 수행 시간이 짧은 프로세스가 있는 경우를 후위 효과(convoy effect)라고 합니다.

 

최단 작업 우선 스케줄링(SJF)에 대해 설명해주세요.

Shortest-Job-First

CPU 사용 시간이 짧은 프로세스에게 먼저 CPU를 할당해주는 방식입니다. 계속 사용 시간이 짧은 프로세스들에게 CPU 할당을 해주기 때문에, minimum average waiting time을 보장합니다. (선점형 방식에 대해서만)

SJF엔 두가지 방식이 존재하는데,

• 선점형: 현재 수행중인 프로세스보다 더 짧은 burst time을 가진 프로세스가 도착한다면, CPU를 빼앗깁니다. 이 방식은 SRTF라고도 부릅니다.
• 비선점형: 현재 수행중인 프로세스의 cpu burst가 종료되어야, 다음 프로세스가 수행되는 방식입니다.

 

최소 잔류 시간 우선 스케줄링(SRTF) 방식에 대해 설명해주세요.

SJF의 선점형 방식으로 동작하는 스케줄링 기법입니다.

 

기아 상태가 무엇인가요?

CPU 사용시간이 긴 프로세스가 영원히 CPU를 할당받지 못하는 문제를 이야기 합니다. 선점형 방식으로 동작하기 때문에 수행중인 프로세스가 끝나고 CPU 사용시간이 긴 프로세스가 실행되어야 하는데 만약 이 때 사용시간이 더 짧은 프로세스가 들어온다면 먼저 CPU를 할당받게 됩니다.

 

기아 상태를 어떻게 해결할 수 있나요?

Aging

우선순위가 낮은 프로세스여도, 시간이 증가함에 따라 우선순위를 높여줘 기아 상태를 해결할 수 있습니다.

우선순위 스케줄링에 대해 설명해주세요.

I/O 작업은 실행 상태보다 입출력을 위한 대기 상태에 더 오래 머무르기 때문에 CPU를 오래 점유하지 않습니다. 반면에, CPU작업은 대기 상태보다 실행 상태에 오래 머무르기 때문에 한번 CPU가 할당되면 오래 점유합니다. 그렇기 때문에 운영체제는 프로세스마다 우선순위를 PCB에 명시하고, 해당 값을 통해서 어떤 프로세스를 먼저 처리할지 결정합니다. 이렇게 자원을 효율적으로 분배하여 우선순위가 높은 프로세스를 먼저 처리하는 것을 우선순위 스케줄링이라고 합니다.

 

라운드 로빈 스케줄링에대해 설명해주세요.

타임 슬라이스란, 각 프로세스가 CPU를 사용할 수 있는 할당 시간을 가지는 것을 의미합니다.

 

라운드 로빈 스케쥴링은 정해진 타임 슬라이스의 시간만큼 돌아가며 CPU를 사용하기 떄문에 모든 프로세스가 한번씩 CPU를 할당받을 수 있는 선점형 스케줄링 입니다. 가장 큰 장점은, Response Time(응답 시간)이 빨라진다는 점 입니다.

 

RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.

프로세스들의 CPU 이용 시간보다 크게 Time Slice 값을 정한다면, 이는 결국 큐에 먼저 삽입된 순서대로 프로세스를 처리하는 FCFS 스케줄링이랑 비슷하게 동작할 것 입니다. 이는 선점형 방식인 라운드 로빈의 특성에 위배된다고 얘기할수 있습니다.

 

하지만, Time Slice 값을 너무 작게 설정한다면, 계속 CPU의 전환이 일어나기 때문에 문맥 교환이 빈번히 발생해 이에 대한 오버헤드가 커질 수 있습니다. 

멀티 레벨 큐 스케줄링에 대해 설명해주세요.

Ready queue를 여러개를 만들어서 우선순위별로 프로세스들을 저장하는 스케줄링 방식을 말합니다. 

 

foreground

• 사용자와 interaction이 많은 프로세스들을 보관합니다.
• 사용자와 interaction이 있기 때문에 응답 시간을 짧게하는 라운드 로빈 방식을 사용합니다.

background

• CPU만 오래 사용하고, 사용자와 교류가 없습니다.
• 응답 시간이 짧아야 할 이유가 없기 때문에, 오버헤드 비용을 줄이기 위해 FCFS 방식을 사용합니다.

단점

우선순위가 낮은 프로세스들이 하위 큐에 저장되기 때문에 영원히 CPU를 할당받지 못하는 기아 문제가 발생할 수도 있습니다.

 

해결방법으로는, 각 queue에 CPU 시간을 적절히 분배해서 우선순위가 낮은 프로세스들이 기아 문제가 발생하지 않도록 합니다. (aging과 유사)

 

하지만, 우선 순위가 낮은 프로세스들이 큐 간에 이동을 하지 못하는 문제 떄문에, 멀티 레벨 피드백 큐가 등장했습니다. 

 

멀티 레벨 피드백 큐 스케줄링에 대해 설명해주세요.

처음에 들어오는 프로세스는 가장 상위 큐에 저장이되고, 해당 시간 내에 처리가 가능하면 그대로 큐에서 빠져나가고, 처리가 안된다면 낮은 큐로 내려갑니다.

 

예를 들어서, Q1, Q2, Q3가 있다고 가정할 때 Q1, Q2는 라운드 로빈 방식으로 동작하고, Q3는 FCFS로 동작합니다. Q1,Q2의 차이는 아래로 내려갈수록 타임 슬라이스 값을 크게 해줘서 해당 시간 내에 프로세스가 처리되지 못하는 경우 아래 큐로 내려갑니다.

 

라운드 로빈 만으로도, CPU burst time이 낮은 프로세스에게 우선순위를 주는 것이 완벽하지 않기 때문에 멀티 레벨 피드백 큐가 나왔습니다.

• CPU burst time이 긴지 짧은지 예측이 필요없는데, 그 이유는 처음에 프로세스가 들어올 때는 상위 큐에 저장이 되기 때문입니다.

---

 

참고자료

http://www.kocw.net/home/search/kemView.do?kemId=1046323

운영체제

https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Operating%20System/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%9F%AC%EC%9D%98%20%EC%A2%85%EB%A5%98.md

Ready-For-Tech-Interview/Operating System/스케줄러의 종류.md at master · WooVictory/Ready-For-Tech-Interview