Scheduler?
그 전에, Queue
수많은 Process/Thread 가 있고, 이를 수행할 CPU core/thread는 한정되어 있기 때문에, 우리는 Process/Thread를 어떻게 처리를 할지 Scheduling을 해야한다.
이러한 프로세스는 여러 State의 상태에 들어가게 될테고, 이에따라 다르게 Scheduling을 해야한다. 이를 위해 3가지 종류의 Queue가 존재한다.
- Job Queue
Secondary storage에 있는 process가 memory로 load될 때 secondary storage에 형성되어있는 Queue - Ready Queue
Memory에 load되어있고, 실행되기를 기다리는 Ready state의 process들로 형성되어 있는 Queue - Device Queue
Device I/O을 대기하고 있는 Process들로 형성되어 있는 Queue. I/O Device에 있는 buffer에 형성되어있다.
그러고보니 State를 다룬적이 없다.
Process의 State는 위의 그림으로 정리가 된다.
- Disk -> Main memory 로 이동하는 과정은 Created state 에서 ready state로 바뀌는 과정이고, 이는
Long-term Scheduler(= job Scheduler)가 담당한다. - Main memory -> CPU로 이동하는 과정은 ready state에서 running state로 바뀌는 과정이고, 이는
short-term Scheduler(= CPU scheduler)가 담당한다. - running state에서 preempt 됐거나, I/O device의 응답을 기다리는 경우, asleep 상태가 된다. 또한, ready 상태에서 starvation이 발생하게 된다면, 오랫동안 memory위에 적재되어 있어, 자원만 잡아먹는 상태가 된다. 이들을 suspended 상태로 바꾸어 memory에서 secondary storage로 쫓아내는 scheduler가
medium-term scheduler이다.
그럼 하나씩 자세히 보자
1. Long-term Scheduler
long-term scheduler의 역할
created -> ready
memory는 한정되어있기에, 수많은 process가 한번에 적재될 수 없다. secondary storage의 pool에 저장되어 있는 process 중 어떤 process를 memory에 적재할지 결정하는 역할을 한다.
- degree of multiprogramming(메모리에 적재되어 있는 process의 개수)을 제어한다. 이 degree가 너무 커도, 너무 작아도 좋지 않기에, 적당한 수를 유지해야한다.
- Virtual Memory 기술의 발달로 요즘 널리 사용되는 time-sharing system에는 long-term Scheduler가 없다.
2. Short-term Scheduler
short-term scheduler의 역할
ready -> running
clock interrupt, I/O interrupt, operating system call 등의 signal을 받게 된다면 Short-term scheduler가 memory에서 대기중인 ready-queue에 있는 process들 중에서 CPU의 자원을 사용할 process를 고른다.
참고로 process에 CPU의 자원을 할당해 주는 것은 dispatcher 가 한다.
Dispatcher
running -> ready : Dispatch
Short-term scheduler가 고른 process에게 CPU을 할당한다. interrupt나 syscall을 받아 kernel mode의 control을 받아 다음과 같은 역할을 한다.
- Switching to user mode
- Context Switch
Unnecessasry context switch가 발생하지 말아야 하므로, context Switch가 필요 없는 시간동안은 virtually idle 상태에 있어야 한다.
Dispatcher의 latency는 context switching overhead에 직결되므로, 최대한 빨라야한다.
3. Medium-term Scheduler(== Swapper)
suspended ready,block <=> ready, asleep
Memory가 부족할 경우, 여유 공간 마련을 위해 process를 Secondary Storage로 옮긴다. 이를 통해 부족한 memory를 충당하고, degree of multiprogramming을 제어한다. suspended 된 process는 자력으로 ready, asleep 상태로 돌아올 수 없다.
