[OS] 프로세스 스케줄링

프로세스 스케줄링을 위한 자료구조

• job queue : 상태에 상관없이 모든 프로세스를 저장하고, 관리하기 위한 자료구조이며, 따라서, 반드시 메모리가 할당되어 있는 프로세스만 있지 않고, 말그대로 모든 프로세스가 담겨있다.
• ready queue : 프로세스 상태에서 배웠던 ready 상태(CPU의 할당을 기다리는 상태로, 할당만되면 바로 실행할 수 있는 대기상태)에 해당하는 프로세스들을 관리하는 큐로 이러한 ready queue에 있는 프로세스들에게 CPU를 어떻게 할당할지(공평하게?)를 결정하는 스케줄링 알고리즘이 있다. 이 때, job queue와 달리 레디큐에 있는 모든 프로세스에는 메모리가 할당된 상태임.
• device Queue : 각각의 장치마다 사용되기를 기다리며 줄 서 있는 프로세스들을 관리한다. 장치 큐에 속한 프로세스는 봉쇄 상태(blocked)가 된다. 봉쇄 상태에 있다가 장치 컨트롤러가 인터럽트를 발생시키면 준비 상태로 바뀌어 준비큐로 이동한다.

위와 같이 프로세스를 큐에 넣고 빼주는 역할을 하는 스케줄러

• 장기 스케줄러(job scheduler) : 어떤 프로세스를 준비큐(ready queue)에 넣어줄 것인가(어떤 프로세스에 메모리를 할당해줄까)를 결정하는 스케줄러. 즉, 프로세스의 상태로 표현해보면, new에서 ready로 바꿔주는 역할을 해주며, 디스크와 메모리 사이의 스케줄링을 담당하는 부분이다. 결과적으로 '실행중인 프로세스 개수'를 제어하는 부분이다. 하지만, 현대의 운영체제에서는 사용하지 않는다고 함. 즉, 스케줄러의 결정없이 프로세스가 시작되면 바로 메모리를 할당해 준비큐에 넣어줌. 그 이유는 요즘은 운영체제가 가상 메모리를 지원하기 때문에 메모리 제한이 없어졌기 때문이라고 함!.
• 단기 스케줄러(CPU scheduler) : 일반적으로 스케줄러라고 하면 가리키는 것이 이 단기 스케줄러인데, 단기 스케줄러는 레디큐에 있는 프로세스 중에 어떤 프로세스에 CPU를 할당할지를 결정한다(CPU와 메모리 사이를 스케줄링). 위에서 레디큐를 설명할 때 말한 스케줄링 알고리즘을 통해 결정하는데, 따라서 매우 빈번하게 호출되므로 속도가 적당히 빨라야한다.
  위의 사진을 보면, 레디큐에 있던 프로세스가 단기 스케줄러로인해 CPU를 할당받는데, 할당 받아서 실행중에 있던 프로세스가 I/O 처리를 위해 waiting queue로 가기도 한다. 이 때, 단기 스케줄러는 CPU를 놀게해서는 안되고(CPU 낭비) 다른 프로세스에 CPU를 할당해주게 된다. 그러다가 처리를 마친 아까 있던 프로세스에 다시 CPU를 할당해서 재활성화를 하는 등의 처리를 한다. 따라서, 단기 스케줄러는 ready-> running -> waiting -> ready의 상태를 관리한다.
• 중기 스케줄러(Swapper) : 사실 이 중기 스케줄러도 요즘 운영체제에는 없는 것이지만, 설명해보면, 오히려 이 스케줄러는 프로세스를 빼는(swap out) 역할을 한다(다시 메모리에서 디스크로의 스케줄링). 만약에 프로세스가 너무 많아서 메모리 할당이 너무 많이 된 상태라면, CPU가 context-switching을 하며 동시적 연산을 할 때 감당이 안될 것이다. 그러한 상황은 CPU에 부하를 주기 때문에 몇개의 프로세스 중에 몇개를 다시 대기 상태로 내려보내야 하는데 이 때 어떤 프로세스를 내려보낼지를 결정하는 것이 중기 스케줄러이다(ready-> suspended). 즉, 메모리로부터 프로세스를 제거해서 멀티 프로그래밍을 제어하여 좀 더 CPU를 효율적으로 쓸 수 있게 한다. 하지만 위에서 말한 것처럼 요즘은 가상 메모리가 있기에 swapper가 필요하지 않게 됐다.

단기 스케줄러(CPU Scheduler)의 스케줄링 방식

• FCFS(First Come First Served) :
  => 큐처럼 먼저 들어온 프로세스에게 먼저 CPU를 할당해주는 것이다. CPU를 하나의 프로세스가 선점하면, 처리가 끝날 때까지 다음 프로세스는 CPU를 사용할 수 없다. 단점은 만약에 처음 들어온 프로세스가 시간 소요가 큰 프로세스면, 비효율적인 결과를 가져온다.
• SJF(Short - Job - First) :
  => 도착 순서와는 관계없이 CPU burst time이 짧은 프로세스에게 먼저 할당하는 방식이다. FCFS 방식에 비해서 효율적으로 CPU를 사용하는 것 같지만, 결국 burst time이 긴 프로세스는 영원히 CPU를 할당받을 수 없게될 수 있음.
• SRTF(Shortest Remaining Time First) :
  => 새로운 프로세스가 들어올 때마다 새롭게 스케줄링을 하는 것인데, SJF를 유지하다가 그보다 더 짧은 프로세스가 들어오면 중단하고 새로 들어온 더 짧은 프로세스에 CPU를 할당한다. 이에 대한 문제점은 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없게 된다.
• Priority Scheduling :
  => 우선순위 큐처럼 우선순위를 주고, 우선순위에 따라 CPU를 할당하는 방식. 우선순위가 더 높은 프로세스가 들어오면 CPU를 그쪽에 할당하도록 되어있음. 그러나 우선순위가 낮은 프로세스는 무기한 대기할 수 있다는 문제가 있음
• Round Robin(RR) : 가장 현대적인 스케줄링 방식으로, context switching이 이 방식으로 이뤄진다. 각 프로세스마다 동일한 할당시간을 분배하고, 그 할당시간이 끝나면 다시 ready queue에 끝으로 가서 대기를 해야한다. 이런식으로 하면 랜덤한 프로세스들이 공정하게(?) CPU 할당을 받고 처리될 수 있다. 그러나, 만약 할당 시간이 지나치게 커지면 FCFS와 똑같아지고, 지나치게 할당시간이 작으면 context-switching이 너무 빈번해져 overhead가 발생할 수 있다.