프로세스 스케줄링

1. 다중 프로그래밍 개요

다중 프로그래밍의 목적은 CPU 이용을 최대화하기 위하여 어떤 프로세스가 항상 실행 중이도록 하는 데 있다. 시분할의 목적은 각 프로그램이 실행되는 동안 사용자가 상호작용 할 수 있도록 프로세스들 사이에서 CPU를 빈번하게 교체하는 것이다.(아주 빨리 교체해서 CPU코어가 모자름에도 병렬로 실행되는 것처럼 보인다.)

2. Scheduling Queues

프로세스가 시스템에 들어오면 job queue에 놓여진다. 이 큐는 시스템 안의 모든 프로세스들로 구성된다. 주 메모리에 존재하며 process state가 ready인 프로세스들은 ready queue라 불리는 리스트 상에 유지된다. 이 큐는 보통 연결 리스트로 저장된다. ready queue의 헤더는 리스트의 첫 번째와 마지막 PCB를 가리키는 포인터를 포함한다. 각 PCB는 ready queue에 있는 다음 프로세스를 가리키는 포인터 필드를 가진다.

job queue와 ready queue말고도 여러가지 큐가 시스템에 존재한다. 프로세스가 디스크 같은 입출력 장치에 요청을 했다고 가정하자. 만약 이 디스크가 다른 프로세스들의 요청으로 바쁘다면, 프로세스는 디스크를 기다려야 할 수도 있다. 특정 입출력 장치를 대기하는 프로세스들의 리스트를 device queue라고 한다. 각 장치는 아래 그림 1처럼 자신의 device queue를 가진다.

[그림 1] ready queue와 다양한 device queue들

프로세스 스케줄링의 공통적인 표현 방식은 아래 그림 2와 같은 queueing diagram이다. 각 사각형은 하나의 queue를 나타낸다. 두 가지 타입의 큐(ready queue, device queues)가 존재한다. 원은 queue를 서비스하는 자원이며, 화살표는 시스템에서 프로세스들의 흐름을 표현한다.

[그림 2] 프로세스 스케줄링을 표현하는 queueing diagram

새로운 프로세스는 처음에 ready queue에 놓인다. 프로세스는 CPU를 할당받을 때(dispatch)까지 ready queue에서 대기한다. 프로세스에 CPU가 할당되어 실행되면 아래 사건들 중 하나가 발생할 수 있다.

• 프로세스가 I/O(입출력)을 요청하여 I/O queue에 넣어질 수 있다.
  
  
• 프로세스가 child process를 생성하고 그 프로세스의 종료를 기다릴 수 있다.
  
  
• 프로세스가 interrupt의 결과에 따라 강제로 CPU로부터 제거되어 ready queue에 다시 놓일 수 있다.

프로세스는 결국 waiting state에서 ready state로 전환되고 다시 ready queue에 넣어진다. 프로세스는 종료될 때까지 이 주기를 계속하며, 종료되면 모든 queue에서 삭제되고 프로세스의 PCB와 자원을 반납(deallocate)한다.

3. Schedulers

프로세스는 다양한 schedule queue들 사이를 이주한다. 프로세스를 스케줄링하기 위해서 운영체제는 이 queue들에서 프로세스들을 선택해야한다. 선택 절차는 적절한 스케줄러에 의해 실행된다.

Long-term scheduler(Job secheduler)는 하드 디스크에서 메모리로 프로세스를 load하는 역할을 한다. 즉 Secondary storage에 저장되어 있는 프로세스가 사용자에 의해 메모리에 적재되고 ready 상태로 되는 것이다.

Short-term scheduler(CPU scheduler)는 ready queue에 존재하는 프로세스들 중에서 어떤 프로세스를 running state로 둘 지 선택한다.

이 두 scheduler 사이의 주요한 차이점은 실행 빈도다. short-term scheduler는 CPU의 최대 효율을 위해 빈번하게(frequently) 프로세스를 선택해야만 한다. 프로세스는 I/O request까지 겨우 수 밀리초 동안만 실행될 수도 있다. 이렇게 실행 간격이 짧기 때문에 short-term scheduler는 반드시 매우 빨라야 한다. 빈번하게 실행되는데 느리다면 scheduling 하는데 너무 많은 CPU를 낭비하게 된다.

반면에 long-term scheduler는 훨씬 덜 빈번하게(infrequently) 실행된다. long-term scheduler는 다중 프로그래밍의 수준(메모리에 있는 프로세스의 수)을 제어한다. 다중 프로그래밍의 수준이 안정적이면 프로세스 생성률이 이탈률과 반드시 같아야한다. 실행 간격이 기므로 short-term scheduler보다는 많은 시간을 소비해도 된다.

long-term scheduler는 신중한 선택을 하는 것이 중요하다. 대부분의 프로세스들은 I/O bound 또는 CPU bound로 묘사된다.

I/O bound process는 연산보다 입출력 실행에 더 많은 시간을 소요하는 프로세스이다. 반면에 CPU bound process는 I/O bound process보다 연산에 시간을 더 소요하여 입출력 요청을 드물게 발생시키는 프로세스이다.

long-term scheduler는 I/O bound process와 CPU bound process들이 적절히 혼합되도록 선택하는 것이 중요하다. 만일 모든 프로세스들이 I/O bound라면 ready queue는 항상 비게 되고, short-term scheduler는 할 일이 없게 된다. 모든 프로세스들이 CPU bound라면 I/O queue는 항상 비게 되고, 장치들이 사용되지 않을 것이고, 시스템은 균형을 잃게 된다. 최선의 성능을 가진 시스템은 CPU bound와 I/O bound 프로세스들을 적절히 혼합한다.

어떤 시스템에서는 long-term scheduler가 없거나 최소한의 기능만 한다. 예를 들어, UNIX와 Microsoft Windows 같은 시분할 시스템들은 long-term scheduler가 없으며 모든 새로운 프로세스들은 short-term scheduler를 위해 단순히 메모리에 넣어진다. 

시분할 시스템과 같은 일부 운영체제들은 medium-term scheduler를 도입했다. medium-term scheduler의 핵심 아이디어는 메모리에서 프로세스들을 제거하여, 즉 CPU를 위한 경쟁에서 제거하여, 다중 프로그래밍의 정도를 완화하는 것이다. 차후에 다시 프로세스를 메모리로 불러와서 중단되었던 지점에서부터 실행을 재개한다. 이러한 기법을 swapping이라고 한다. swapping은 프로세스 혼합 상태를 개선하기 위하여 혹은 메모리가 가용 메모리를 초과하여 메모리를 비우기 위해 필요하다. swapping에 대한 자세한 것은 후에 공부하자.