[OS] CPU 스케줄링

스케줄링?

하나의 관리자로 프로세스들의 여러 상황을 고려하여 cpu와 시스템 자원을 어떻게 배정할 지 결정하는 역할을 함

 

- 고수준 스케줄링 (가장 큰 틀에서 이루어지는 스케줄링)

어떤 작업요청이 오면 스케줄러가 시스템의 상황을 고려하여 작업을 승인할지, 거부할지 결정함(승인 스케줄링 이라고도 함)

 

- 중간수준 스케줄링

전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막음

 

- 저수준 스케줄링

어떤 프로세스에 CPU를 할당하고 어떤 프로세스를 대기 상태로 보낼지 등을 결정함

아주 짧은 시간에 일어나기 때문에 단기 스케줄링이라고도 함

 

스케줄링의 목적

근본적으로 이런 스케줄링을 왜 할까?

모든 프로세스가 공평하게 작업하도록 하기 위해서이다.

엄청나게 오래 걸리는 프로세스만을 처리하기 위해 상대적으로 짧은 시간이 소요되는 프로세스를 처리하는것이 밀리는 경우, 하지만 이런 짧은 프로세스를 무한히 처리하여 오래 걸리는 프로세스라는 이유로 끊임없이 밀리는 현상, 이런 상태에 반응 시간이 느려져 응답이 없어지는 현상 등을 방지하고자 스케줄링을 사용한다.

 

1) 공평성 - 모든 프로세스가 자원을 공평하게 배정받아야 함

2) 효율성 - 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링 하고, 유휴 자원을 사용하려는 프로세스에 우선권을 줘야함

3) 안전성 - 우선순위를 설정하여 시스템 자원을 점유, 파괴하려는 프로세스로부터 자원을 보호해야함

4) 확장성 - 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야함

5) 반응 시간 보장 - 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 함

6) 무한 연기 방지 - 특정 프로세스의 작업이 무한히 연기되어서는 안됨

 

선점과 비선점

선점형 스케줄링 (뺏김)

- 하나의 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식

- 라운드 로빈, SRT, 다단계 큐, 다단계 피드백 큐

 

비선점형 스케줄링 (안뺏김)

- 하나의 프로세스가 CPU 할당을 받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스가 CPU를 점유할 수 없음

- 우선순위, 기한부, FCFS, SJF, HRN

 

스케줄링 알고리즘

선점

1) FCFS

들어온 순서대로 CPU에 할당(FIFO와 동일)

 

2) SJF

프로세스 도착 시점에 따라 스 당시 가장 짧은 소요 시간을 갖는 프로세스가 종료시까지 CPU 점유

가장 먼저 도착한거 먼저 처리하고 다 끝나면 도착해 있는 프로세스 중 제일 짧은거 쭉 처리함

 

비선점

1) 라운드로빈

CPU 점유 시간을 정해 정한 시간 만큼 프로세스를 처리하고 만약 시간 내 처리하지 못하면 제일 뒤로 밀림

 

2) SRT

프로세스 처리 중 가장 짧은 시간이 걸리는 프로세스를 먼저 수행

처음에는 가장 먼저 도착한거 먼저 처리하다가 큐에 프로세스가 들어왔을 때 들어온 프로세스가 현재 처리중인 프로세스보다 처리 시간이 더 짧으면 짧은거 먼저 처리함

 

3) HRN

최고 응답률 우선 스케줄링이라고도 함

SJF의 아사현상을 해결하기 위함

공식 => 우선순위 - (대기시간 + CPU사용시간) / CPU 사용시간 을 계산하여 우선순위가 높을 수록 먼저 실행한다.

 

 

문제 정리

1. 시스템 내 전체 프로세스의 수를 조절하는 것으로, 장기 스케줄링 또는 작업 스케줄링이라 불리는 스케줄링 수준은 무엇인가?

고수준 스케줄링 (가장 큰 틀에서 이루어지는 스케줄링)

 

 

2. 어떤 프로세스에 CPU를 할당하고 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 스케줄링 수준은 무엇인가?

저수준 스케줄링 (가장 작은 단위의 스케줄링)

 

 

3. 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링은 무엇인가?

선점형 스케줄링

 

 

4. 현재 입출력을 진행하는 프로세스로, 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 불리는 것은 무엇인가?

전면 프로세스

 

 

5. 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 스케줄링 알고리즘은 무엇인가?

FCFS(First-Come-First-Served) 스케줄링

(=FIFO)

 

 

6. 준비 큐에 있는 프로세스 중 실행시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 스케줄링 알고리즘은 무엇인가?

SJF(Shortest Job First) 스케줄링

 

 

7. SJF 스케줄링 알고리즘의 단점으로 크기가 큰 작업이 계속 뒤로 밀리는 현상을 무엇이라 하는가?

아사현상(starvation) (계속 밀려서 굶어 죽는 듯), 무한 봉쇄 현상

 

 

8. 아사 현상을 해결하는 방법을 설명하시오.

에이징(오랫동안 기다린 프로세스에게 우선순위를 높여줌)

 

 

9. 서비스를 받기 위해 대기한 시간과 CPU 사용시간을 고려하여 우선순위를 정하는 스케줄링 알고리즘은 무엇인가?

HRN 스케줄링

SJF 스케줄링 기법의 약점인 긴 작업과 짧은 작업 사이의 불평등을 보완

우선순위: (대기시간 + 서비스(실행)시간) / 서비스(실행)시간 = 시스템 응답시간

시스템 응답시간이 커질수록 우선순위가 높아짐

 

 

10. 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 다음 자기 차례가 올 때까지 기다리는 선점형 스케줄링 알고리즘 중 가장 단순한 것은 무엇인가?

라운드 로빈(Round Robin) 스케줄링

 

 

11. 타임 슬라이스의 크기와 문맥 교환의 관계를 설명하시오.

타임 슬라이스가 작으면 문맥 교환이 많아진다.
타임 슬라이스가 크면 문맥 교환이 적어진다.
=> 타임 슬라이스의 크기와 문맥 교환은 반비례 관례

 

12. 기본적으로 라운드 로빈 방식을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 것을 선택하는 스케줄링 알고리즘은 무엇인가?

SRT 스케줄링

 

 

13. 우선순위에 따라 준비 큐를 여러 개 사용하며 고정형 우선순위를 적용하는 스케줄링 알고리즘은 무엇인가?

다단계 큐 스케줄링

 

 

14. 우선순위에 따라 준비 큐를 여러 개 사용하며 프로세스가 CPU를 사용한 후 우선순위가 낮아지는 특성을 가진 스케줄링 알고리즘은 무엇인가?

다단계 피드백 큐 스케줄링

 

 

15. 다단계 피드백 큐 스케줄링에서 마지막 큐에 있는 프로세스(우선순위가 가장 낮은 프로세스)의 타임 슬라이스 크기는 얼마인가?

무한대

 

 

16. 다단계 피드백 큐 스케줄링에서 우선순위가 낮아질수록 타임 슬라이스의 크기는 어떻게 변하는가?

커진다

 

 

17. 다단계 피드백 큐 스케줄링에서 마지막 큐(우선순위가 가장 낮은 큐)는 어떤 스케줄링 알고리즘처럼 동작하는가?

FCFS 스케줄링