프로세스의 상태 그리고 알고리즘

앞의 포스팅에서 멀티 프로그래밍은 CPU 활용도를 극대화 하는 스케줄링 알고리즘이라고 했습니다.

각 박스는 CPU를 사용 중 이라는 뜻이며 공백은 CPU를 사용하지 않는 상태입니다.

그렇다면 위의 그림에서 최상의 스케줄러를 만든다면 어떻게 만들 수 있을까요? 다른 말로 CPU의 활용도를 극대화하는 스케줄러는 어떤 모습일까요?

위의 그림을 보면 프로세스 1을 제외한 나머지 프로세스들은 사전에 CPU를 사용하지 않는 모습입니다. 그렇기 때문에 가장 처음부터 CPU를 사용하기 위해 프로세스 1번이 오는것이 좋으며 마찬가지의 이유로 위와 같은 모습이 가장 좋은 선택일겁니다.

프로세스의 상태

위와 같은 상황을 만들기 위해서는 프로세스의 상태를 알고 있어야 합니다.

다시말해 스케줄러는 어떤 프로세스가 CPU 실행이 가능한 상태인지 아닌지, 어느 시점에 어떤 프로세스를 CPU에 넣어야 하는지 프로세스의 상태 정보를 알고 있어야 한다는겁니다.

출처 : IT위키

• New : 프로세스가 생성중인 상태로 Ready 상태로 가지 못한 상태입니다.
• *Ready : 프로세스가 CPU에 실행되기 위해 대기하는 상태입니다.
  • 바로 CPU 실행이 가능한 상태로 실행 대기 상태입니다.
• *Running : 프로세스에 포함된 명령어가 실행되고 있는 상태입니다. 즉, CPU에서 실행을 하고 있는 상태입니다.
• *Waiting : 프로세스가 특정 자원이나 이벤트를 기다리는 상태
  • 보조기억장치등 파일읽기를 기다리는 상태라고 생각하면 됩니다. 파일을 다 읽을때까지는 계속 Block 상태이며 파일읽기가 끝나면 운영체제에서 특정 이벤트를 해당 프로세스에 발생시키고 프로세스는 해당 상태를 Ready 상태로 변경합니다. 즉, 특정 이벤트가 발생하기 전까지는 Block 상태입니다.
  • Blocked, Blocking, Block 상태라고도 합니다.
• Exit : 종료시에는 프로세스가 바로 끝나느것이 아니라 해당 프로세스가 가지고 있는 시스템 자원들을 풀어주기위한 일정시간이 필요한 상태입니다.

상태 정보가 같다면??

하지만 문제는 또 있습니다. 위와 같은 경우인데 프로세스들의 상태가 중복이 된다면? 스케줄러는 어떤 방식으로 어떤 프로세스를 골라야할까요?

스케줄러도 어처피 하나의 프로그램입니다. 다시 말해 알고리즘으로 어떤 규칙으로 골라야할지 만들 수 있다는 의미입니다.

많은 방법중에 한가지 방법은 각 상태별로 자료구조 큐를 적용하는것 입니다. 먼저 큐는 선입선출의 기능을 하는 자료구조입니다. 그에 맞게 Ready State Queue에 들어올 수 있는 1, 2, 3번 프로세서를 순서로 큐에 담습니다.

그러면 위와 같은 그림이 그려집니다. 그러면 스케줄러는 단지 Ready Q에 담겨져있는 프로세서들을 pop()을 이용해서 꺼내오기만 하면 됩니다. 그리고 꺼내진 프로세서들은 Running Q에 옮겨지겠죠.

그러면 위와 같이 처음 들어온 프로세서1이 Running으로 옮겨질것이고 프로세서를 실행하게 됩니다. 그리고 일정 CPU를 사용하고나면 프로세서1의 첫 번째 프로세서는 Exit 상태가 되고 나머지 하나는 아래 그림과 같이 다시 Ready Q에 옮겨지게 됩니다.

그리고 다시 Ready Q에 있는 프로세스를 꺼내오고 Running Q에 들어가게 될꺼고 다음 프로세스가 Wait이라면 Block Q에 들어가게 될것입니다. 그리고 Wait Q에 있는 프로세스 대신 다음 프로세스가 들어가겠죠.

그리고 해당 작업을 반복하면 최종적으로 아래와 같은 모습이 됩니다.

CPU를 사용하지 않는 상태를 idle 상태라고 이야기하며 이전 포스팅에서 자주 언급이 되었언 유후 상태가 바로 해당 idle 상태입니다.

프로세서의 상태가 아닌 CPU의 상태를 이야기합니다.

이처럼 자료구조 큐를 사용하여서, 다시 말해 프로그래밍으로 만들 수 있는 규칙들로 이러한 결과를 만들 수 있었습니다. 물론 다른 방법으로 혹은 다른 규칙으로 스케줄링 알고리즘을 사용했다면 결과는 달라질 수 있지만 가장 기본적인 방법은 이런것이 있다 라고 알고있으면 좋을것 같습니다.