운영체제 2: 프로세스 스케줄링 시스템의 종류와 알고리즘

스케줄링 시스템

 운영체제는 CPU를 효율적으로 사용하기 위해 프로세스 스케줄링을 수행하며, 스케줄링 시스템은 여러가지가 있는데 배치(batch) 처리 시스템, 시분할 시스템, 멀티 태스킹, 멀티 프로세싱, 멀티 프로그래밍으로 나눌 수 있다. 사실 실제로는 시분할 시스템, 멀티 프로그래밍, 멀티 태스킹은 유사한 의미로 통용된다. 중요한 점은 이 세 가지 시스템 모두 CPU 활용도를 높여서 여러 프로그램이 짧은 시간안에 처리될 수 있도록 하기 위해 사용한다는 것이다.

 

배치 처리 시스템

 자료 구조 중 큐(Queue)와 같은 방법으로(선입선출 = FIFO) 첫 번째 응용 프로그램의 작업이 끝나면 바로 이어서 다음 응용 프로그램이 자동으로 실행 될 수 있도록 하는 방법이다.

 배치 처리 시스템은 여러 한계가 있고, 이를 극복하기 위해 멀티 프로그래밍과 시분할 시스템이 등장했다.

• 각 응용프로그램당 실행시간을 정확히 계산할 수 없기 때문에, 먼저 실행된 프로그램이시간이 오래 걸릴 경우 이 후 프로그램이 실행되기까지의 대기시간이 과도하게 늘어난다
• 한 번에 하나의 작업만 처리하기 때문에 멀티 태스킹이 불가능하다 (예를 들어 음악을 재생하면서 문서를 작성할 수 없다)
• 하나의 작업이 일단 실행된 경우, 중간에 입력된 작업은 해당 작업이 끝나야만 실행될 수 있다 (어떤 프로세스가 작업하는 도중에는 키보드를 눌러도 입력에 대한 결과는 작업중이던 프로세스가 끝나야 받을 수 있다)

시분할 시스템

 다중 사용자 지원을 위해 응용 프로그램이 CPU를 점유하는 시간을 잘게 쪼개어 실행될 수 있도록 하는 시스템이다. 시분할 시스템의 목표는 프로세스 응답 시간을 가능한 짧게 가져가는 것이다.

 

멀티 태스킹 시스템

 시분할 시스템을 기반으로 한다. 굉장히 짧은 시간 차이는 사람이 인지하지 못하는 점을 활용해 작업을 굉장히 짧은 시간 단위로 쪼갬으로써 단일 CPU에서 여러 응용 프로그램이 동시에 실행되는 것처럼 보이게 하는 시스템이다.

 

멀티 프로세싱 시스템

 멀티 태스킹은 CPU 코어를 하나만 사용하지만 멀티 프로세싱은 여러 CPU 코어를 사용한다. 즉, 멀티 프로세싱은 최대한 CPU를 많이 활용하면서, 시간 대비 CPU의 활용도를 높이는 것을 통해 짧은 시간 안에 응용 프로그램 실행을 완료하는 것이다. 여러 CPU에 하나의 프로그램을 병렬로 실행해서 속도를 극대화하는 시스템이다.

멀티 프로그래밍 시스템

 응용프로그램이 하는 모든 작업이 CPU를 이용하는 것은 아니다. 예를 들어 프로세스 중간에 파일을 읽는 작업이 필요할 때 CPU가 아닌 메모리나 저장매체에 접근한다. 이럴 때 파일을 읽어오는 동안 해당 CPU는 아무 작업도 하지 않는 상태가 된다 (=CPU & 시간의 낭비). 멀티 프로세싱은 그 시간 동안 실행하던 프로그램을 blocking해 두고 DMA가 데이터를 가져오는 작업을 하는 동안 다른 응용프로그램의 작업을 하는 것으로 채우는 것이다.  따라서 멀티 프로그래밍 시스템의 목표는 CPU 활용도(CPU가 작업을 한 시간/프로세스 실행에 걸린 시간)를 최대한 높이는 것이다.

 

스케줄링 알고리즘 (스케줄러 정책/ Policy)

 컴퓨터 구조에서 모든 프로그램은 메모리에 올려진 후, CPU에 하나씩 넣어지면서 실행된다. 프로세스란 메모리에 올려져서 실행 중인 프로그램을 일컫고, 응용 프로그램은 여러 개의 프로세스로 이루어질 수 있다 (IPC 기법). 프로세스의 실행을 관리하는 것이 스케줄러이다. 스케줄러는 특정 알고리즘에 따라 프로세스를 실행, 교체시킨다.

 

FIFO 스케줄러

 가장 간단한 스케줄러로 들어온 순서대로 프로세스를 실행하는 스케줄러이다. 배치 처리 시스템에서 사용된다.

 

최단 작업 우선 스케줄러 (SJF)

 가장 프로세스 실행 시간이 짧은 작업부터(Short job first) 실행 시킨다. 작업을 시작하기 전에 모든 프로세스의 각 작업에 걸리는 시간을 계산해야하며, 경우에 따라 FIFO와 최종 실행시간이 같을 수 있다.

 

우선 순위 기반 스케줄러

 프로세스에 정적(실행 전에 각 프로세스의 우선순위를 미리 지정) 또는 동적(상황에 따라 스케줄러가 우선순위를 변경)방법으로 우선순위를 매겨(Prority-based) 실행 시킨다.

 사람이 직접 모든 프로세스에 대한 우선순위를 매기는 것은 불가능하기 때문에 스케줄러가 프로세스에 우선순위를 매기는 동적 우선순위가 많이 사용된다.

 

Round robin 스케줄러

 특정 기간 동안 프로세스의 실행이 완료되지 않으면 남은 실행 과정을 대기열의 맨 뒤로 배치하는 것 (시분할 시스템을 기반으로 한다)

예를 들어, 처음 들어온 프로세스의 총 실행 시간은 3초인데, 1초 단위로 프로세스를 자른다고 하면 실행 시작되고 1초 후 나머지 과정은 대기하고 있는 프로세스의 뒷 순서로 넘겨준다.

 

  

 

 

프로세스 상태와 알고리즘

 스케줄러가 작업 계획을 세울 때 가장 중요한 것은 프로세스의 상태이다. 프로세스가 바로 CPU에 넣어서 실행이 가능한 상태인지, 다른 곳에서 작업이 필요해서 대기(wait)해야하는 상태인지에 대한 정보가 필요하다. 프로세스의 상태는 다음과 같이 다섯 가지로 구분된다.

• new: 프로세스가 생성 중인 상태
• ready state: 프로세스가 CPU에서 실행 가능인 상태 (=실행 대기 상태)
• running state: 프로세스가 현재 CPU에서 실행 중인 상태
• blocked state: 프로세스가 대기 중인 상태 (특정 이벤트 발생 대기 상태 - 저장매체 또는 출력장치 등에 접근 중이며 해당 작업이 끝나면 프로세스에 특정 이벤트를 발생 시키며, 이 이벤트의 의미는 이제 CPU에서 작업이 가능하다는 것)
• exit: 프로세스를 종료하기 위해 프로세스를 위해 분배되었던 시스템 리소스를 풀어주는 과정

프로세스 상태가 변하는 경우

• running -> block: Process blocks for input(여기서 Input은 특정 이벤트)
• block -> ready: Process becomes available (CPU가 이제 작업할 수 있는 상태가 됨)
• ready -> running: Scheduler picks this process (스케줄러에 의해 CPU에 넣어짐)
• running -> ready : Scheduler picks another process (CPU에서 실행중이다가 대기 중으로 바뀜)

선점형 스케줄러 vs 비선점형 스케줄러

• 선점형 스케줄러 (Preemptive Scheduling): 하나의 프로세스가 다른 프로세스 대신에 프로세서(CPU)를 차지할 수 있음 (running -> ready가 가능) : 시분할 시스템 (Round robin scheduler)
• 비선점형 스케줄러 (Non-preemptive Scheduling): 하나의 프로세스가 끝날 때 까지 다른 프로세스가 CPU를 사용할 수 없음. 프로세스가 자발적으로 blocking 상태로 들어가거나, 실행이 끝났을 때만 다른 프로세스로 교체가 가능하다.

 처음 스케줄러가 나왔던 시대에는 선점형의 구현이 어려워서 비선점형 스케줄러를 사용했지만, 현재는 대부분의 OS에서 선점형 스케줄러를 사용하고 있다. 비선점형의 경우, 먼저 실행되는 프로세스의 응답시간이 길 경우 다른 프로세스의 응답이 과도하게 지연된다는 단점이 있다. 선점형의 장점을 극대화하면서 다른 알고리즘의 장점도 함께 가져가고자, 현대의 스케줄러는 여러 알고리즘을 섞어서 사용하는 경우가 일반적이다.