스케줄러(Scheduler)

Summary

스케줄러에 대해 알아본다.

스케줄러 (Scheduler)

어떤 프로세스에 자원을 할당할지를 결정하는 운영체제 커널의 모듈 및 시스템 소프트웨어
한정적인 메모리를 여러 프로세스가 효율적으로 사용할 수 있도록 실행할 프로세스를 선택한다

스케줄링 큐(Scheduling Queue)

프로세스는 수행하면서 상태가 여러 번 변한다. 프로세스 상태에 따라 서비스를 받아야 하는 곳이 다르다. 일반적으로 프로세스는 여러 개가 한 번에 수행 되므로 이에 따른 순서가 필요하다. 이러한 순서를 대기하는 곳을 큐라고 한다. 프로세스를 스케줄링 관리하는 큐에는 프로세스 상태에 따라 3가지 종류가 존재한다.¹

²

1. Job Queue
   • 현재 시스템 안의 모든 프로세스의 집합³
   • 하드디스크에 있는 프로그램이 실행되기 위해 메인 메모리의 할당 순서를 기다리는 큐⁴
2. Ready Queue
   • CPU 점유 순서를 기다리는 큐
   • ready 상태의 메인메모리 안에 상주하며 CPU를 잡아서 실행되기를 기다리는 모든 프로세스의 집합
   • 새로운 프로세스는 이 큐에 담긴다.
3. Device Queue
   • Device I/O 작업을 대기하는 프로세스들의 집합
   • I/O를 하기 위한 여러 장치가 있는데, 각 장치를 기다리는 큐가 각각 존재한다.
   • I/O장치가 현재 사용 불가해서(unavailable) blocked 된 프로세스들을 들고 있다.

⁴

큐 내부에는 각 프로세스의 PCB가 저장되어 있다.
프로세스의 상태가 바뀌면, 해당 프로세스 PCB가 기존 큐에서 unlink되고 새로운 상태에 따른 큐로 옮겨진다.⁵

큐는 프로세스 순서를 기다리는 공간이며, 이 순서를 정해주는 알고리즘을 스케줄링이라 한다.

스케줄러 종류

각각의 큐에 프로세스들을 넣고 빼주는 스케줄러에는 3가지 종류가 존재한다.

⁶

• Job Queue - Job Scheduler(Long-term scheduler)
• Ready Queue - CPU Scheduler(Short-term scheduler)
• Device Queue - Device Scheduler

장기 스케줄러(Long-term scheduler/Job scheduler)

Job Queue의 순서를 정해준다.
한정된 메모리에 많은 프로세스가 한꺼번에 메모리에 올라올 때, 대용량 메모리(디스크)에 임시로 저장된다. 이 큐에 저장된 프로세스 중 어떤 프로세스를 메모리에 할당하여 ready queue로 보낼지 결정한다.

• 메모리와 디스크 사이의 스케줄링 담당
• 프로세스에 메모리 및 각종 리소스를 할당(admit)
• degree of multiprogramming 제어: 실행 중인 프로세스의 수 제어
  • degree of multiprogramming이 안정적이다면, 프로세스 생성 평균속도와 시스템을 나가는 프로세스 평균속도가 같다.²
• 프로세스 상태변화
  • new -> ready(in memory)
• 스케줄링이 발생하는 시간(초~분)이 비교적 오래 걸리기 때문에 long-term(장기) 스케줄러라고도 한다.
• 모든 시스템이 지원하지 않는다.
  • Time-sharing os는 장기 스케줄러가 없다. 바로 메모리에 올라가 ready 상태가 된다.

단기 스케줄러(Short-term scheduler / CPU scheduler)

• CPU와 메모리 사이의 스케줄링을 담당
• 어떤 프로세스를 다음으로 실행할지(running) 결정한다.
• ready 한 프로세스들 중 하나를 골라 실행시키고 CPU를 할당한다 (scheduler dispatch).
• 장기 스케줄러보다 적은 degree of Multiprogramming 제어 제공
• 장기 스케줄러보다 빠르다. 스케줄링이 발생하는 시간이 매우 짧아서 short-term 스케줄러라고도 한다.
• 일반적으로 부르는 스케줄러는 단기 스케줄러를 뜻한다.
• 프로세스 상태변화
  • ready -> running (-> waiting -> ready)

중기 스케줄러(Medium-term scheduler / Swapper)

• 여유 공간을 마련하기 위해 프로세스를 스와핑(swapping)한다.
  • 실행하는(running) 프로세스는 I/O 요청을 받으면 정지될 수 있다. 정지된 프로세스(suspended process)는 더는 일을 완료할 수 없다. 이 정지된 프로세스를 메모리에서 지우고 다른 프로세스를 들일 공간을 만들기 위해서, 정지된 프로세스는 보조기억장치(secondary storage)로 옮겨진다. 이 과정을 스와핑(swapping)이라고 한다.
  • 프로세스가 “swapped out” 또는 “rolled out” 되었다고 한다.

• 다시 프로세스를 메모리에 데려와 실행을 계속한다.

• degree of Multiprogramming을 줄인다.
• 속도는 단기와 장기 스케줄러의 중간이다.
• 프로세스 상태변화
  • ready -> suspended
  • suspended process state: 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태. 프로세스 전부 디스크로 swap out 된다. blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready state로 돌아갈 수 있지만, 이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없다.
• Time sharing system에 들어있다.

⁷

References

1. 깃헙 인터뷰 문제 ↩

2. tutorialspoint ↩ ↩²

3. 테리의 일상 블로그 ↩

4. codemcd님 velog ↩ ↩²

5. tutorialspoint ↩

6. geeksforgeeks ↩

7. kosaf04phy님 블로그 ↩