프로세스[2] - 프로세스 스케줄링(Process Scheduling)

프로세스 스케줄링(Process Scheduling)

스케줄링 큐(Queues)

프로세스가 시스템에 들어오면, 이들은 잡 큐에 놓여진다. 이 큐는 시스템 안의 모든 프로세스로 구성된다. 주 메모리에 존재하며 준비 완료 상태에서 실행을 대기하는 프로세스들은 준비완료 큐(ready queue)라 불리는 리스트 상에 유지된다.  이 큐는 일반적으로 연결 리스트로 저장된다. 준비 완료 큐의 헤더는 리스트의 첫번쨰와 마지막 PCB를 가리키는 포인터를 포함한다. 각 PCB는 준비 완료 큐에 있는 다음 프로세스를 가리키는 포인터 필드를 가진다. 시스템에는 또한 다른 큐 들도 있다. 프로세스가 CPU를 할당 받으면, 어느 정도 실행을 하고 결국에는 그만두거나,  인터럽트 되거나, 입/출력 요청이 완료되는 것같은 특별한 사건의 발생을 기다리게 된다. 시스템에는 많은 프로세스들이 있기 때문에, 디스크가 다른 프로세스들의 입/출력 오청으로 바쁠 수 있다.  그러므로 프로세스는 디스크를 대기해야 할 수도 있다. 특정 입/출력 장치를 대기하는 프로세스들의 리스트를 장치 큐(device queue)라고 한다. 각 장치는 그 자신의 장치 큐를 가진다. 새로운 프로세스는 처음에 준비 완료 큐에 놓인다. 프로세스는 실행을 위하여 선택될 때 즉, CPU를 할당 받을 때 까지 준비 완료 큐에서 대기한다. 일단 프로세스에 CPU가 할당되어 실행되면, 여러가지 사건들 중의하나가 발생 할 수 있다.

   

   - 프로세스가 입/출력 요청을 하여 입/출력 큐에 넣어질 수 있다.

   - 프로세스가 새로운 서브프로세스를 생성하고 그 프로세스의 종료를 기다릴 수 있다.

   - 프로세스가 인터럽트의 결과에 의해 강제로 CPU로부터 제거되고, 준비 완료 큐에 다시 놓일 수 있다.

처음의 두 경우에서, 프로세스는 결국 대기 상태에서 준비 완료 상태로 전환되고, 다시 준비 완료 큐에 넣어지게 된다. 프로세스는 종료될 때까지 이 주기를 계속하며, 종료되면 모든 큐에서 삭제되고 그 자신의 PCB와 자원을 반납(deallocate)한다.

스케줄러(Schedulers)

일괄 처리 시스템에서는 즉시 실행될 수 있는 것보다 더 많은 프로세스들이 종종 제출된다. 이들 프로세스들은 대용량 메모리에 저장되어 나중에 실행될 때까지 그곳에 유지된다. 장기 스케줄러는 이 풀에서 프로세스들을 선택하여 실행하기 위해 메모리로 적재한다. 단기 스케줄러는 실행 준비과 완료되어 있는 프로세스들 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.

이들 두 스케줄러 사이의 주요한 차이점은 이들의 실행 빈도에 있다. 단기 스케줄러는 CPU를 위해 반드시 자주 새로운 프로세스를 선택해야 한다. 프로세스는 입/출력 요청을 위해 대기하기 전까지 겨우 수 밀리초 동안 실행될 수 있다. 종종 단기 스케줄러는 매번 백 밀리초마다 한번씩 실행된다. 실행 간격이 짧기 때문에, 단기 스케줄러는 반드시 매우 빨라야 한다.

반면에 장기 스케줄러는 실행 빈도수가 훨씬 적다. 시스템에서 새로운 프로세스를 생성하는 간격은 수 분이 될 수 있다. 장기 스케줄러는 다중 프로그램의 정도( 메모리에 있는 프로세스들의 수)를 제어한다. 다중 프로그래밍의 정도가 안정적이면, 평균 프로세스 생성률이 시스템을 떠나는 평균 프로세스 이탈률(average departure rate)과 반드시 동일해야 한다. 그러므로 장기 스케줄러는 프로세스가 시스템을 떠날 때만 호출될 필요가 있을 수도 있다. 실행 간격이 비교적 크기 때문에, 장기 스케줄러는 실행할 프로세스를 선택하는 데 시간을 더 사용해도 된다.

일반적으로, 대부분의 프로세스들은 입/출력 중심 또는 CPU 중심으로 묘사된다. 입/출력 중심 프로세스는 연산보다 입/출력 수행에 더 많은 시간을 소요하는 프로세스이다. 반면에 CPU 중심 프로세스는 입/출력 중심 프로세스보다 연산에 시간을 더 소요하여, 입/출력 요청을 드물게 발생시키는 프로세스이다. 

만일 모든 프로세스들이 입/출력 중심이라면, 준비 완료 큐는 항상 비게 되고, 단기 스케줄러는 할일이 없게 된다. 모든 프로세스들이 CPU 중심이라면 입/출력 대기 큐는 항상 비어있는 상태가 되고, 장치들이 사용되지 않을 것이고, 재차 시스템이 균형을 잃게 된다. 최선의 성능을 가진 시스템은 CPU 중심과 입/출력 중심 프로세스들을 적절히 혼합한다.

문맥 교환

CPU를 다른 프로세스로 교환하려면 이전의 프로세스의 상태를 보관하고 새로운 프로세스의 보관된 상태를 적재하는 작업이 필요하다. 이 작업은 문맥 교환 ( Context Switch ) 이라고 알려져 있다.

문맥은 CPU레지스터의 값, 프로세스 상태, 메모리 관리 정보를 포함한다. 문맥교환이 일어나면, 커널은 과거 프로세스의 CPB내에 있는 문맥을 저장하고 수행이 스케줄된 새로운 프로세스의 저장된 문맥을 적재한다.