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

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

다중 프로그래밍의 목적은 CPU 이용을 최대화하기 위하여 항상 하나의 프로세스라도 실행되도록 하는데 있다. 시분할의 목적은 각 프로그램이 실행되는 동안 사용자가 상호작용할 수 있도록 프로세스들 사이에서 CPU를 빈번하게 교체하는 것이다. 이 목적을 달성하기 위해 프로세스 스케줄러는 CPU에서 실행 가능한 여러 프로세스들 중에서 하나의 프로세스를 선택한다. 단일처리기 시스템에서는 실행 중인 프로세스가 한 개 이상 있을 수 없다. 만일 프로세스들이 여러 개가 있다면, 나머지 프로세스들은 CPU가 자유로워져 다시 스케줄링이 이루어질 때까지 기다려야 한다.

1. 스케줄링 큐 (Scheduling Queue)

프로세스가 시스템에 들어오면, 이들은 작업 큐에 놓여진다. 이 큐는 시스템 안의 모든 프로세스를 포함한다. 주 메모리에 적재되어 있으면 준비완료 상태에서 실행되기를 기다리는 프로세스들은 준비완료 큐(ready queue)라고 불리는 리스트에 저장된다. 준비 완료 큐의 헤더(첫 번째 노드)는 리스트의 첫 번째와 마지막 PCB를 가리키는 포인터를 저장하고 있다. 또한, 각 PCB는 준비완료 큐에 있는 다음 프로세스를 가리키는 포인터 필드를 가진다.

시스템에는 다른 큐들도 있다. 프로세스가 CPU를 할당받으면, 어느 정도 실행한 후에 궁극적으로 종료되거나 인터럽트에 의해 작업을 중지하거나, 혹은 I/O 요청 완료와 같은 특정 사건의 발생을 기다리게 된다. 프로세스가 디스크 같은 공유장치에 입출력 요청을 했다고 가정하자. 시스템에는 많은 프로세스들이 있기 때문에 디스크가 다른 프로세스들의 입출력 요청으로 바쁠 수 있다. 그러므로 프로세스는 디스크를 사용하기 위하여 기다려야 할 수도 있다. 특정 입출력장치를 대기하는 프로세스들의 리스트를 장치 큐(device queue)라고 한다. 각 장치는 자신만의 장치 쥬를 가진다.

프로세스 스케줄링을 논의하는데 사용되는 공통적인 표현 방식은 아래의 이미지와 같은 큐잉 도표(queueing diagram)이다. 각 사각형은 하나의 큐를 나타낸다. 두 가지 유형의 큐(준비완료 큐와 장치 큐들의 집합)가 존재한다. 원은 큐를 서비스하는 자원이며, 화살표는 시스템에서 프로세스들의 흐름을 표현한다.

새로운 프로세스는 처음에 준비완료 큐에 놓인다. 프로세스는 실행될 프로세스로 선택될 때, 즉 CPU를 할당 받을(dispatch) 때까지 준비완료 큐에서 대기한다. 일단 프로세스에게 CPU가 할당되어 실행되면, 다음 여러 가지 이벤트들 중 하나가 발생할 수 있다.

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

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

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

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

1 - a. Linux의 프로세스 표현

Linux 운영체제의 프로세스 제어 블록은 C 언어의 struct task_struct로 표현된다. 이 구조체는 프로세스의 상태, 스케줄링과 메모리 관리 정보, 오픈된 파일 및 부모 프로세스와 자식 프로세스를 가리키는 포인터 등을 포함한 프로세스를 표현하기 위한 모든 필요한 정보를 가지고 있다(프로세스의 부모 프로세스는 그 프로세스를 생성한 프로세스이고, 자식 프로세스는 그 프로세스가 생성한 모든 프로세스를 의미한다).

2. 스케줄러 (Scheduler)

프로세스는 일생 동안에 다양한 스케줄링 큐 사이를 이주한다. 운영체제는 스케줄링 목적을 위해 어떤 방식으로든지 프로세스들을 이들 큐에서 반드시 선택해야 한다. 그리고 이 선택 절차는 적절한 스케줄러에 의하여 실행된다.

종종 일괄처리 시스템에서는 당장 실행될 수 있는 것보다 더 많은 프로세스들이 제출된다. 이들 프로세스들은 대용량 메모리(전형적으로 디스크)에 저장되어 나중에 실행될 때까지 그곳에 유지된다. 장기 스케줄러(long-term scheduler)라고도 불리는 작업 스케줄러(job scheduler)는 이 풀에서 프로세스들을 실행하기 위해 선택하여 메모리로 적재한다. 단기 스케줄러(short-term scheduler)라고도 불리는 CPU 스케줄러(CPU scheduler)는 실행 준비가 완료되어 있는 프로세스 중에서 하나를 성택하여 그 프로세스에게 CPU를 할당한다.

이들 두 스케줄러 사이의 주요한 차이점은 스케줄러의 실행 빈도에 있다. 단기 스케줄러는 CPU를 위해 자주 새로운 프로세스를 선택해야만 한다. 프로세스는 입출력 요청을 위해 대기하기 전까지 겨우 수 밀리초 동안 실행될 수 있다. 종종 단기 스케줄러는 매번 백 밀리초마다 최소 한 번씩 실행된다. 실행 각격이 짧기 때문에 단기 스케줄러는 매우 빨라야 한다. 만일 한 프로세스를 100 밀리초 동안 실행하기 위하여 10 밀리초를 소모한다면, 10 / (100 + 10) = 약 9%의 CPU를 단순히 작업을 스케줄링하기 위하여 사용하게 된다.

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

장기 스케줄러는 신중한 선택을 해야 한다. 일반적으로, 프로세스들은 입출력 중심 또는 CPU 중심으로 기술될 수 있다. 입출력 중심 프로세스는 연산보다 입출력 작업 실행에 더 많은 시간을 소요하는 프로세스이다. 반면, CPU 중심 프로세스들은 입출력 작업보다 연산에 더 많은 시간을 소모하는 프로세스이다.

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

일부 운영체제는 장기 스케줄러가 없거나, 최소한의 기능만 사용한다. 예를 들어 시분할 기법을 사용하는 운영체제의 경우, 장기 스케줄러가 없다. 이 경우, 모든 새로운 프로세스가 단기 스케줄러에 의해 선택되도록 단순히 메모리에 넣는다.

추가로, 이러한 시분할 시스템과 같은 일부 OS들은 중간 수준의 스케줄링을 도입한다. 이와 같은 중기 스케줄러(medium-term scheduler)의 핵심 아이디어는 메모리에서 프로세스들을 제거하는 것이다. 즉, CPU 사용을 위한 경쟁을 완화시키는 것이다. 프로세스를 잠시 메모리에서 스왑아웃 시켰다가, 적당한 시기에 스왑인 시키는 스와핑 방식을 통해서 CPU 사용 경쟁을 완화시키는 것이다. 스와핑은 프로세스 혼합상태를 개선하기 위하여 필요하거나, 또는 메모리 요구량이 변하며 가용 메모리로 해결이 불가능할 때 메모리를 자유화시키기 위해 필요하다.

스와핑에 관한 내용은 다음 링크를 통해서 자세히 알아볼 수 있다. (http://neos518.tistory.com/121?category=806096)

3. 문맥 교환 (Context Switch)

인터럽트는 운영체제가 CPU를 현재 작업으로부터 빼앗아 커널 루틴을 실행할 수 있게 처리한다. 이러한 연산은 범용 시스템에서 자주 발생한다. 인터럽트가 발생하면, 시스템은 인터럽트 처리가 끝난 후에 문맥을 복구할 수 있도록 실행 중이던 프로세스의 문맥을 저장할 필요가 있다. 이는 결국 프로세스를 중단했다가 재개하게 된다. 문맥은 프로세스의 PCB에 저장된다. 문맥은 CPU 레지스터의 값, 프로세스의 상태, 메모리 관리 정보 등을 포함한다.

일반적으로 CPU가 커널 모드이건 사용자 모드이건 CPU의 현재 작업 상태를 저장하는 작업을 수행하고(state save), 나중에 연산을 재개하기 위하여 상태 복구작업을 수행한다(state restore).

CPU를 다른 프로세스에게 할당하려면 현재 프로세스의 상태를 저장하고, 다른 프로세스의 저장된 상태를 복구하는 작업이 필요하다. 이 작업을 문맥 교환(context switch)이라고 한다. 문맥 교환이 일어나면 커널은 과거 프로세스의 문맥을 PCB에 저장하고, 새로운 프로세스의 저장된 문맥을 복구한다. 문맥 교환이 진행될 동안 시스템이 아무런 유용한 일을 못하기 때문에 문맥 교환 시간은 순수한 오버헤드이다. 그 속도는 메모리의 속도, 반드시 복사되어야 하는 레지스터의 수, 특수 명령어(모든 레지스터들을 하나의 명령어로 보관하고 적재하는 것과 같은)의 존재에 좌우되기 때문에 기계마다 다르다. 전현적인 속도는 수 밀리초 정도이다.