[쉽게 배우는 운영체제] Chapter 04. CPU 스케줄링

01 스케줄링 단계

▶ 고수준 스케줄링

시스템 내의 전체 작업 수를 조절하는 것으로 시스템 내에서 동시에 실행 가능한 프로세스의 총 개수를 결정한다.

 

▶ 중간 수준 스케줄링

고수준 스케줄링에 의해 실행이 결정된 프로세스의 수를 조절하여 시스템의 과부하를 막는다.

 

▶ 저수준 스케줄링

활성화된 프로세스들의 실제 진행을 담당한다.

 

02 프로세스의 우선순위

우선순위가 높은 프로세스는 커널 프로세스, 전면 프로세스, 대화형 프로세스, 입출력 집중 프로세스이며, 우선순위가 낮은 프로세스는 사용자 프로세스, 후면 프로세스, 일괄 작업 프로세스, CPU 집중 프로세스다. 느린 입출력 프로세스에 CPU의 작업을 양보함으로써 시스템의 효율성이 향상되는데 이를 '사이클 훔치기'라고 한다.

 

03 비선점형 스케줄링

어떤 프로세스가 CPU를 점유하면 작업을 완료할 때까지 다른 프로세스가 CPU를 뺏을 수 없는 스케줄링 방식으로, 과거의 일괄 작업 시스템에서 사용했다.

 

04 선점형 스케줄링

어떤 프로세스가 CPU를 할당받아 실행 중이더라도 스케줄러가 CPU를 강제로 뺏을 수 있는 스케줄링 방식이다. 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생긴다는 단점이 있으나 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.

 

05 스케줄링 알고리즘

▶ 선입선출(FCFS)

먼저 들어온 작업에 먼저 CPU를 할당한다. 가장 단순한 선점형 알고리즘이다.

 

▶ 최단 작업 우선(SJF)

실행 시간이 짧은 작업부터 CPU를 할당한다. 이 방식의 경우 작업 시간이 긴 프로세스가 긴 프로세스가 계속 뒤로 밀리면서 아사 현상이 발생한다. 아사 현상은 나이 먹기로 완화할 수 있으나 여전히 공평성을 위배한다.

 

▶ 최고 응답률 우선(HRN)

알고리즘 작업 시간과 기다린 시간을 혼합하여 CPU를 할당한다. 아사 현상을 해결하기 위해 만든 비선점형 알고리즘이다.

 

▶ 라운드 로빈(RR)

선점형 알고리즘 중 우선순위가 적용되지 않는 가장 단순하고 대표적인 알고리즘이다.

 

▶ 최소 잔류 시간 우선(SRT)

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

 

▶ 우선순위

우선순위가 높은 프로세스부터 CPU를 할당한다. 선점형과 비선점형 방식에 모두 적용할 수 있는 알고리즘이다.

 

▶ 다단계 큐(MLQ)

우선순위에 따라 여러 개의 큐를 사용하는 알고리즘 중 고정 우선순위 방식이다.

 

▶ 다단계 피드백 큐(MLFQ)

우선순위에 따라 여러 개의 큐를 사용하고 한 번 CPU를 잡은 프로세스의 우선순위를 떨어뜨린다. 각 큐의 타임 슬라이스 크기가 다른 변동 우선순위 알고리즘이다.

 

 

---

 

 

연습문제 01. 시스템 내에서 동시에 실행 가능한 프로세스의 총 개수를 결정하는 단계는?

① 단기 스케줄링

② 중간 수준 스케줄링

③ 고수준 스케줄링

④ 저수준 스케줄링

 

연습문제 02. 저수준 스케줄링이 원만하게 이루어지도록 완충 역할을 하는 단계는?

① 장기 스케줄링

② 중간 수준 스케줄링

③ 고수준 스케줄링

④ 작업 스케줄링?

 

연습문제 03. 활성화된 프로세스의 실제 진행을 담당하는 단계는?

① 작업 스케줄링

② 중간 수준 스케줄링

③ 고수준 스케줄링

④ 저수준 스케줄링

 

연습문제 04. 비선점형 스케줄링과 비교하여 선점형 스케줄링에 대한 설명으로 옳지 않은 것은?

① 비선점형에 비하여 우선순위가 낮다.

② 실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행할 수 있다.

③ 문맥 교환의 오버헤드가 많다.

④ 시분할 방식 스케줄러에 사용된다.

 

연습문제 05. 나머지 3개와 비교하여 우선순위가 높은 프로세스는?

① 일괄 처리 프로세스

② 사용자 프로세스

③ 커널 프로세스

④ CPU 집중 프로세스

 

연습문제 06. 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식의 스케줄링 알고리즘은?

① 최고 응답률 우선(HRN)

② 최단 작업 우선(SJF)

③ 최소 잔류 시간 우선(SRT)

④ 선입선출(FCFS)

 

연습문제 07. 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식의 스케줄링 알고리즘은?

① 최고 응답률 우선(HRN)

② 최단 작업 우선(SJF)

③ 최소 잔류 시간 우선(SRT)

④ 선입선출(FCFS)

 

연습문제 08. 아사 현상이 발생할 수 있는 비선점형 방식의 스케줄링 알고리즘은?

① 최고 응답률 우선(HRN)

② 최단 작업 우선(SJF)

③ 최소 잔류 시간 우선(SRT)

④ 선입선출(FCFS)

 

연습문제 09. 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링하는 비선점형 알고리즘은?

① 최고 응답률 우선(HRN)

② 최단 작업 우선(SJF)

③ 최소 잔류 시간 우선(SRT)

④ 선입선출(FCFS)

 

연습문제 10. 선점형 알고리즘이 아닌 것은?

① 다단계 큐(MLQ)

② 다단계 피드백 큐(MLFQ)

③ 라운드 로빈(RR)

④ 최단 작업 우선(SJF)

 

연습문제 11. 아사 현상을 완화하는 방법은?

① 사이클 훔치기

② 에이징

③ 작업 훔치기

④ 우선순위

 

연습문제 12. 선입선출(FCFS) 스케줄링과 유사하지만, 각 프로세스마다 CPU를 사용할 수 있는 타임 슬라이스가 있으며 우선순위가 없는 알고리즘은?

① 다단계 큐(MLQ)

② 다단계 피드백 큐(MLFQ)

③ 라운드 로빈(RR)

④ 최단 작업 우선(SJF)

 

연습문제 13. 문맥 교환 시간을 소비하는 알고리즘은?

① 최고 응답률 우선(HRN)

② 최단 작업 우선(SJF)

③ 다단계 큐(MLQ)

④ 선입선출(FCFS)

 

연습문제 14. 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남은 작업 시간이 가장 적은 프로세스를 선택하는 알고리즘은?

① 최고 응답률 우선(HRN)

② 다단계 피드백 큐(MLFQ)

③ 최소 잔류 시간 우선(SRT)

④ 선입선출(FCFS)

 

연습문제 15. 현대의 운영체제에서 사용하기 힘든 알고리즘은?

① 우선순위

② 다단계 피드백 큐(MLFQ)

③ 최소 잔류 시간 우선(SRT)

④ 라운드 로빈(RR)

 

연습문제 16. 우선순위에 따라 여러 개의 큐를 사용하는 알고리즘 중 고정 우선순위 방식은?

① 선입선출(FCFS)

② 다단계 피드백 큐(MLFQ)

③ 다단계 큐(MLQ)

④ 최고 응답률 우선(HRN)

 

연습문제 17. 우선순위에 따라 여러 개의 큐를 사용하는 알고리즘 중 변동 우선순위 방식은?

① 선입선출(FCFS)

② 다단계 피드백 큐(MLFQ)

③ 다단계 큐(MLQ)

④ 최고 응답률 우선(HRN)

 

연습문제 18. 우선순위에 따라 여러 개의 큐를 사용하고 각 큐의 타임 슬라이스 크기가 다른 변동 우선순위 알고리즘은?

① 선입선출(FCFS)

② 다단계 피드백 큐(MLFQ)

③ 다단계 큐(MLQ)

④ 최고 응답률 우선(HRN)

 

연습문제 19. 다단계 피드백 큐(MLFQ)에서 우선순위가 가장 낮은 큐는 어떤 알고리즘처럼 작동하는가?

① 최고 응답률 우선(HRN)

② 최단 작업 우선(SJF)

③ 최소 잔류 시간 우선(SRT)

④ 선입선출(FCFS)

 

연습문제 20. (고수준) 스케줄링은 스케줄링 3단계 중 시스템 내에서 동시에 실행 가능한 프로세스의 총 개수를 결정하는 단계다.

 

연습문제 21. (중간 수준) 스케줄링은 스케줄링 3단계 중 저수준 스케줄링이 원만하게 이루어지도록 완충 역할을 하는 단계다.

 

연습문제 22. (저수준) 스케줄링은 스케줄링 3단계 중 아주 짧은 시간에 일어나는 스케줄링 단계다.

 

연습문제 23. 비선점형과 선점형 스케줄링 중 일괄 작업 방식 스케줄링에 사용되는 것은 (비선점형 스케줄링)이다.

 

연습문제 24. 비선점형과 선점형 스케줄링 중 실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행할 수 있는 것은 (선점형 스케줄링)이다.

 

연습문제 25. 비선점형과 선점형 스케줄링 중 실행 상태에 있는 작업이 완료될 때까지 다른 작업이 불가능한 것은 (비선점형 스케줄링)이다.

 

연습문제 26. 입출력 집중 프로세스보다 CPU 집중 프로세스의 우선순위가 (낮다).

 

연습문제 27. 커널 프로세스의 우선순위가 사용자 프로세스보다 (높다).

 

연습문제 28. 후면 프로세스보다 전면 프로세스의 우선순위가 (높다).

 

연습문제 29. 일괄 처리 프로세스보다 대화형 프로세스의 우선순위가 (높다).

 

연습문제 30. CPU 집중 프로세스보다 입출력 집중 프로세스에 먼저 CPU를 할당하면 효율이 올라가는데 이를 (사이클 훔치기)라고 한다.

 

연습문제 31. (변동 우선순위 알고리즘) 방식에서는 낮은 우선순위를 높은 우선순위로 바꾸어 시스템 효율을 향상한다.

 

연습문제 32. (FCFS) 스케줄링은 콘보이 효과가 발생하는 스케줄링 알고리즘이다.

 

연습문제 33. (SJF) 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식의 스케줄링 알고리즘이다.

 

연습문제 34. (아사 현상)은 최단 작업 우선(SJF)과 같은 알고리즘에서 긴 작업이 계속 뒤로 밀리는 것을 말한다.

 

연습문제 35. (HRN) 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링하는 비선점형 알고리즘이다.

 

연습문제 36. (라운드 로빈) 스케줄링은 선점형 알고리즘 중 우선순위가 적용되지 않는 가장 단순하고 대표적인 방식의 알고리즘이다.

 

연습문제 37. (에이징)은 아사 현상을 완화하는 방법이다.

 

연습문제 38. (다단계 큐) 스케줄링은 선입선출(FCFS) 스케줄링과 유사하지만, 각 프로세스마다 CPU를 사용할 수 있는 타임 슬라이스가 있으며 우선순위가 없는 알고리즘이다.

 

연습문제 39. (SRT) 스케줄링은 최단 작업 우선(SJF)과 라운드 로빈(RR) 스케줄링을 혼합한 선점형 알고리즘이다.

 

연습문제 40. (다단계 큐) 스케줄링은 우선순위에 따라 여러 개의 큐를 사용하는 알고리즘 중 고정 우선순위 방식의 알고리즘이다.

 

연습문제 41. (SRT) 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남은 작업 시간이 가장 적은 프로세스를 선택하는 알고리즘이다.

 

연습문제 42. (다단계 피드백 큐) 스케줄링은 우선순위에 따라 여러 개의 큐를 사용하고 각 큐의 타임 슬라이스 크기가 다른 변동 우선순위 알고리즘이다.

 

연습문제 43. 다단계 피드백 큐(MLFQ) 스케줄링에서 우선순위가 가장 낮은 큐는 (FCFS) 스케줄링 방식으로 작동한다.

 

연습문제 44. CPU 스케줄링 3단계를 설명하시오.

CPU 스케줄링 3단계는 고수준 스케줄링, 저수준 스케줄링, 중간 수준 스케줄링입니다.

고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것으로, 장기 스케줄링 혹은 작업 스케줄링이라고도 불립니다.

저수준 스케줄링은 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일을 합니다.

중간 수준 스케줄링은 고수준 스케줄링과 저수준 스케줄링 사이에 일어나는 스케줄링으로 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막아줍니다.

 

연습문제 45. 선점형 스케줄링과 비선점형 스케줄링을 설명하시오.

선점형 스케줄링은 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이고, 비선점형 스케줄링은 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식입니다.

 

연습문제 46. 사이클 훔치기에 대하여 설명하시오.

입출력 집중 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우를 의미합니다.

 

연습문제 47. 고정 우선순위와 변동 우선순위에 대하여 설명하시오.

고정 우선순위 알고리즘은 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정되는 것이며, 단순하게 구현할 수 있지만 시시각각 변하는 시스템 상황을 반영하지 못해 효율성이 떨어집니다.

변동 우선순위 알고리즘은 일정 시간마다 변하는 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템 상황을 반영하여 효율적인 운영이 가능합니다.

 

연습문제 48. 최단 작업 우선(SJF) 스케줄링과 에이징에 대하여 설명하시오.

SJF 스케줄링은 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고 합니다. 이 스케줄링 방식의 경우, 작은 작업이 계속 준비 큐에 들어오게 되면 큰 작업은 계속 연기되는데 이를 아사 현상이라고 하며, 이러한 문제는 에이징으로 완화할 수 있습니다.

 

연습문제 49. 다단계 피드백 큐 스케줄링에 대하여 설명하시오.

다단계 피드백 큐 스케줄링은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식입니다. CPU를 사용한 후 프로세스의 우선순위가 낮아지고, CPU를 사용한 후의 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어갑니다.