멀티프로그래밍은 CPU 활용도를 극대화 하는 스케쥴링 알고리즘이다. 아래 그림과 같이 각 프로세스들이 존재할 때 Wait 파트를 파일 읽기를 하는 시간으로 가정한다면 CPU에서 진행되는 순서는 Combinded 처럼 될 것이다.
프로세스 상태는 크게 3가지로 분류가 된다. 초기에 프로세스 생성이 될 때와 종료될 때는 논외로 할 때 Running, Ready, Block 상태가 있다.
프로세스 상태 간 관계는 다음과 같다. Ready 상태에서 Running이 될 수 있고 Running 후 Block 또는 Ready 상태로 간다. Block 상태가 끝나면 Ready로 돌아간다.
위와 같은 프로세스 상태를 기반으로 하는 기초적인 알고리즘은 다음과 같다. 프로세스 3개의 상태가 다음과 같다고 가정할 때 각 상태별 큐가 존재한다.
그리고 다음과 같이 각 상태에 맞게 큐에 삽입한다. 최초 시점에서는 모두 실행이 가능한 Ready이기에 모두 Ready큐에 들어간다.
이후 ReadyQueue.pop()을 통해 해당 큐로부터 프로세스를 가져와 처리한다. 이 때 실행 중이기 때문에 Running 큐에 삽입된다.
일정 시간 진행 후에는 종료 후 상태를 판단하여 해당 상태에 맞는 큐에 삽입된다. 프로세스 1의 경우 여전히 진행가능하기 때문에 Ready 큐로 돌아간다.
다음에는 Ready 큐의 가장 앞에 있는 프로세스 2를 가져와 CPU에서 처리를 하고 종료가 된 뒤 상태는 Block이 된다. 따라서 다음과 같이 Block 큐로 들어간다.
이렇게 큐 3개에 동일하게 작동을 하며 프로세스 처리가 되면 최종적인 CPU 프로세스 처리 순서는 다음과 같다. 중간에 존재하는 idle은 Ready 큐에 실행가능한 프로세스가 없어 대기 상태일 때를 의미한다.