8. 프로세스 상태와 스케줄링 알고리즘

1. 멀티프로그래밍과 wait

• 멀티 프로그래밍: CPU 활용도를 최대화 하기위한 스케줄링 알고리즘
• Wait: 간단히 저장매체로부터 파일 읽기를 기다리는 시간으로 가정 

 

 

a) 개요

• 위와 같이 프로그램 A, B, C가 있으며 각 프로그램은 위의 그림처럼 CPU를 할당받아 사용한다.
• 각 프로그램은 wait 상태에 있는 동안 CPU를 사용하지 않는다.
• CPU 활용도를 최대화하는 방법은, 각 프로그램의 wait 시점에서 CPU 사용을 필요로 하는 다른 프로그램을 실행시키는 것이다.
• 결과적으로, 그림의 combined 처럼 스케줄링을 구현하여 CPU 활용도를 100%로 유지할 수 있다. 
• 어떻게 해야 이러한 스케줄링 알고리즘을 만들 수 있는지 알아보자. 

 

 

b) 프로세스 상태 

- 프로그램의 CPU 사용여부를 판단하려면 프로세스 상태를 확인하면 된다. 프로세스의 상태는 다음과 같은 단계로 구분된다.  

- 프로세스는 총 5가지의 상태로 구분된다. 그 중 3가지를 이용하여 스케줄러가 CPU의 사용여부를 판단하게 된다. 

• ready state: CPU에서 실행 가능한 상태 / 실행 대기중인 상태
• running state: 현재 CPU에서 실행중인 프로세스 
• block state: 특정 이벤트를 대기하고 있는 상태 (= wait 상태)

 

 

c) 문제점과 한계점

- 프로세스가 running 상태에서 block(= wait) 상태로 전환하게 되면, ready 상태에 있는 프로세스 중 하나를 선택하여 CPU에 할당하게 된다. 그러나 ready 상태에 있는 프로세스가 여러개가 존재한다면, 무엇을 기준으로 다음에 실행할 프로세스를 선택할까?  

 

- 이를 해결하기 위한 새로운 알고리즘에 대해 알아보자. 

 

---

2. 프로세스 상태 Queue

• Queue는 순서대로 데이터를 쌓는 자료구조이다.(FIFO) 
• Queue를 이용하여 프로세스 상태 변동에 순서를 부여하는 것이다. 
• Ready State Queue, Running State Queue, Block State Queue를 이용하여 실행 준비된 프로세스, 실행중인 프로세스, 대기중인 프로세스에 순서를 부여하여 CPU를 할당 받을 순서를 만들어준다. 

- Queue를 이용하여 프로세스 순서를 부여하는 방법 뿐만 아니라, 앞선 포스팅에서 배웠던 우선순위 또는 최단 작업 알고리즘 등 다양한 알고리즘을 활용하여 프로세스에 순서를 부여하는 작업을 할 수 있다.