스케쥴러(Scheduler)

목차

스케쥴러란?

한정적인 메모리에 여러 프로세스가 효율적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스 중에 하나를 선택하는 역할이다. 

 

프로세스는 일생 동안 다양한 스케줄링 큐 사이를 이동하는데, 프로세스를 스케줄링하기 위한 Queue에는 세 가지 종류가 존재한다.

 

1. 작업 큐(Job Queue) : 시스템 안의 모든 프로세스들로 구성

2. 준비 큐(ready queue) : 메인 메모리에 존재하며, 준비 완료 상태에서 실행을 대기하는 프로세스들로 구성

3. 장치 대기 큐(device queue) : 특정 입/출력장치를 대기하는 프로세스들의 리스트들로 구성

 

 

스케쥴러의 종류

1. 단기 스케줄러(CPU Scheduler) : CPU와 메모리 사이를 담당하는 스케줄러
   • 실행 준비가 완료되어 준비 큐에 있는(메모리에 존재하는) 프로세스들 중에서 선택하여 CPU를 할당
   • 단기 스케줄러는 자주 수행되므로 빨라야 함
2. 중기 스케줄러(Swapper) : 메모리에서 CPU를 점유하기 위해 경쟁하는 프로세스를 디스크로 보내는 스케줄러
   • 시분할 시스템(Time-shared)과 같은일부 운영체제에서 도입
   • 다중 프로그래밍의 정도를 완화
   • 차후 다시 프로세스를 메모리로 불러와서 중단되었던 지점에서 실행을 재개하는 스와핑(swapping) 기능을 함
3. 장기 스케줄러(Job Scheduler) : 메모리와 디스크 사이를 담당하는 스케줄러
   • 디스크 상의 프로세스를 선택하여 준비 큐로 저장(메모리로 적재)
   • 다중 프로그래밍의 정도(메모리에 있는 프로세스의 수) 제어
   • 수십 초 내지 수 분 단위로 호출되기 때문에, 속도가 느릴 수 있음

스케쥴링

스케줄러가 메모리 내의 프로세스에게 CPU를 할당하는 것을 의미한다.

스케쥴링의 목적

자원 활용 최적화

• 스케줄링은 CPU, 메모리, 입출력 장치 등과 같은 시스템 자원의 사용을 최적화
• 여러 프로세스가 동시에 실행될 때, 스케줄러는 어떤 프로세스가 CPU를 사용하고, 어떤 것이 대기해야 하는지를 결정하여 CPU의 활용도를 높임

응답 시간 최소화

• 스케줄링은 프로세스들이 빠른 응답 시간을 가지도록 조절
• 사용자가 프로그램을 실행했을 때, 해당 프로그램이 빠르게 시작되어 응답하는 것이 중요 스케줄러는 이를 위해 효율적인 작업 배치를 계획

공정한 자원 할당

• 시스템 내의 여러 프로세스가 공평하게 자원을 나누어 사용할 수 있도록 스케줄링이 필요
• 우선순위를 지정하거나 순환할당 등의 기법을 사용하여 각 프로세스가 공정하게 CPU 시간을 할당받을 수 있도록 함

작업 처리량 최대화

• 스케줄러는 시스템이 많은 수의 작업을 효율적으로 처리할 수 있도록 도와줌
• 다양한 스케줄링 알고리즘을 사용하여 작업들을 효율적으로 배치하여 전체 시스템의 처리량을 최대화

자원 간의 균형 유지

• 여러 자원 간의 균형을 유지하고 효율적인 작업 분배를 지원
• CPU, 메모리, 입출력 장치 등 각각의 자원이 적절하게 활용되도록 스케줄러는 프로세스를 관리

스케쥴링 종류

선점형 스케줄링

• 남보다 앞서서 차지한다는 의미로, 어떤 프로세스가 CPU를 할당받아 차지하고 있더라도, 더 급한 프로세스가 얼마든지 CPU의 자원을 빼앗아서 쓸 수 있는 스케줄링을 의미한다.

장점

• 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다.

단점

• 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.
• 스케줄러 호출 빈도가 높다.

비선점형 스케줄링

• 어떤 프로세스가 CPU를 할당받고 있다면, 그 프로세스가 종료되거나 대기 상태가 되기 전까지 CPU를 사용할 수 없다.

장점

• 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다.
• 일괄 처리 시스템에 적합하다. 

단점

• 모든 프로세스가 골고루 자원을 이용하기 어려워 기아 현상이 발생한다. 

스케쥴링 알고리즘

자세한 내용은 해당 블로그에 들어가면 확인할 수 있다. 

중요한 몇가지만 살펴보고자 한다. 

 

⭐️ RR(Round Robin)

• 각각의 프로세스에 동일한 CPU 할당시간을 부여하는 것으로, 컴퓨팅 자원을 사용할 수 있는 기회를 프로그램 프로세스들에게 공정하게 부여하기 위한 방법이다. 
• 시분할 시스템을 위해 설계되었으며, 시간단위로 CPU를 할당하는 방식의 알고리즘이다. 
• 프로세스들은 시간 할당량 동안 중앙처리 장치를 할당받아 실행되는데, 이 시간 동안 실행을 종료하지 못하면 운영체제에 의해 준비 상태로 쫓겨나고, 준비 큐의 다음 프로세스가 중앙처리장치를 할당받아 실행된다.

⭐️ Real-time scheduling (선점형)

실시간 스케쥴링으로 사전에 정의된 기한 내에 특정 업무를 완수해야만 하는 시스템에 사용되는 스케쥴링 방식이다.

 

Real time scheduling에도 두 가지 개념이 존재한다. 

- Hard Real Time System (Hard RT) : task는 반드시 정해진 기한 안에 끝나야 한다.

- Soft Real Time System (Soft RT) : 정해진 기한이 존재하지만, 보장되지 않아도 큰 문제는 없다. 

 

Real-time scheduling의 두 가지 종류

1. RMS (Rate Monotonic Scheduling)
   - 주기를 기반으로 우선순위를 할당(주기가 짧을수록 더 높은 우선순위를 가진다.
   - 들어온 순간마다 Priority를 판단하는 것이 아니라 처음부터 rate 를 사용해서 priority를 정해주고 그 prioriy 그대로 스케줄링 해준다.
2. EDF (Earliest Deadline First)
   - deadline이 가까워져 올 때, 가장 급한 것부터 먼저 스케줄링 해주는 기법이다. 
   - task들이 들어올때마다 ㅇeadline을 비교해보고, prioritiy를 정하는 방식이다. 

 

---

면접예상질문

스케쥴링은 무엇인가요?

여러 프로세스가 있고, 이 프로세스들이 자원(CPU 등)을 동시에 요구하는데 자원은 제한되어 있습니다. 그럴 때 제한된 자원들을 어떻게(순서를 할당하는 등) 나눠줄 것인지에 대한 정책을 말합니다. 

CPU 스케쥴링은 언제 발생하나요?

• 실행상태에서 대기상태로 전환될 때 (예, 입출력 요청) - Non preemptive(비선점)
• 실행상태에서 준비상태로 전환될 때 (예, 인터럽트 발생) - preemptive(선점)
• 대기상태에서 준비상태로 전환될 때(예, 입출력이 종료될 때)
• 종료될 때(Terminated)

참고 자료 

https://terms.naver.com/entry.naver?docId=2270386&cid=51173&categoryId=51173

https://ddongwon.tistory.com/35

https://velog.io/@kyeun95/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%8A%A4%EC%BC%80%EC%A5%B4%EB%9F%ACScheduler

[운영체제] 스케쥴러(Scheduler)

15. 프로세스 스케줄링_4 (Real-time System)

라운드 로빈 스케줄링