멀티 프로그래밍과 Wait

image.png

  • 각각의 프로세스들이 처음부터 끝까지 쭉 실행을 한다고 가정할 경우, 각각의 프로세스는 어떻게 실행이 되는지를 보여주는 그림이다.

  • 예를들어, Process A의 경우 먼저 cpu에서 실행이 된다.(Run 상태) 그리고, 특정 시점이 되면 저장매체 혹은 시스템 자원을 사용하기 위해서 System Call과 같은 요청을 하면서 wait 상태가 된다. 그리고 system call이 완료되면 다시 cpu에 올라가면서 run상태가 된다.

  • 각각의 프로세스 3개를 스케쥴러에서 실행을 할때, 최적의 스케쥴러는?

    • a를 가장먼저 선택한다. b,c 프로세스는 wait 상태이기때문에 실행 불가
    • b를 선택한다. a,c프로세스는 wait 상태
    • c를 선택한다. a,b,프로세스는 wait 상태
    • 결과적으로, a,b,c 프로세스를 쉴틈없이 cpu에 올리면서 cpu활용도를 극대화 시킨다.
  • 위의 설명과 같이 cpu의 활용도를 극대화 시키기 위해서 프로세스가 어떤 시점에 실행이 되고 wait가 되는지 상태를 알고 있어야 한다.

프로세스 상태

image.png

  • running state : 현재 cpu에서 실행 상태
  • ready state : cpu에서 실행 가능한 상태(실행 대기 상태)
  • block state : 특정 이벤트 발생 대기 상태(ex : 프린팅이 다 되었다!)

process state 관계

image.png

  • 프로세스가 cpu에서 running상태에 있다가 file 입력 요청이 들어오면 block상태가 된다.

  • 스케쥴러가 다른 프로세스를 선택한다.

  • block상태에서 파일 입력이 다 되었다는 특정 이벤트를 받으면 ready state로 변경 시킨다.

  • cpu에서 현재 실행중인 프로세스작업이 끝나면 스케쥴려가 ready상태인 프로세스들을 실행 시킨다.

  • ready상태인 프로세스가 실행되면서 running상태가 된다.

  • 시분할 시스템에서는 특정 시점마다 서로 다른 프로세스를 계속 바꿔가면서 실행 시킨다. 이때, 프로세스를 running -> ready로 바꾸면서 시분할 시스템을 구현한다.(그림의 3번 상황)

image.png

image.png

image.png

cpu입장에서 process1,2,3은 모두 ready 상태가 된다. 2번을 선택하면서 process2는 running 상태가 되었다가(1번,3번은 ready상태) event처리를 위해 block 상태가 된다. ready 상태인 프로세스들을 선택하기 위해서 또다른 알고리즘이 필요하게 된다.

State Queue를 활용한 스케쥴러

image.png

위의 그림과 같이 3개의 Queue를 활용해서 ready,running,block state를 구분 하도록 하면된다.

image.png

스케쥴러가 하는 일은 ready state quque에서 프로세스 하나를 deque시킨다. 그렇다면 queue의 정책에 따라 가장 먼저 들어간 프로세스가 deque된다.
위의 그림에서는 process1이 ready state queue에 가장 앞부분에 위치 해 있다가, deque되면서 running state queue로 들어간 것 이다.

image.png

process1을 실행 시키고, 특정 시간이 지나면 ready state queue에서 process2를 deque시키면서 running state queue로 옮기고, cpu에서해당 프로세스를 실행 시킨다. 그리고 process 2는 실행 시키고 나면 wait를 해야하는 작업이 있으므로, ready state queue가 아닌 block state queue로 push 시킨다.

image.png

다음은 process3을 running 시킨다. 그리고 해야할 작업이 더 남았으므로 ready state queue로 push 시킨다.

ready state queue를 확인해보면 process 1의 작업이 남았으므로 해당 프로세스를 deque시키면서 cpu에 올려서 작업을 처리한다. 3번 process가 ready state queue에 들어 있으므로 3번을 cpu에 올리면서 running state에 push 시킨다.

image.png

2번프로세스에서 wait상태가 필요한 작업이 다 끝나면서 이벤트가 발생하고 block state에 있던 process2를 ready state queue에 push 시킨다.

image.png

3번 process에도 wait해야하는 작업이 있는것을 확인하고 block state queue로 이동 시킨다.

image.png

2번 프로세스가 최종적으로 종료되면서 queue에서 빠져나온다.
image.png

ready state에 들어있는 process가 없으므로 cpu는 대기하고 있는다.(idle상태) 그리고, process 3번의 작업이 종료하면서 이벤트를 발생시키면서 process 3을 ready state queue로 이동 시킨다.

image.png

3번을 pick해서 running state로 옮기고 cpu에 올려서 작업을 처리한다.

image.png

※ process 3의 wait time이 process 2의 wait time보다 짧은경우

CPU 스케쥴러 작동에서 만약 1,2,3 프로세스 중 2 프로세스가 2 | 2(wait)(3초) | 2 이고 3 프로세스가 3 | 3(wait)(1초) | 3 일 경우
Block State Queue에는 2프로세스가 먼저 들어가서 3초대기 하고 그다음 3프로세스가 들어가서 1초대기를 할때에 wait 이벤트가 3부터 끝나게 되면 Block State Queue에서 3을 Ready State Queue로 옮겨야 하는데 Queue특성상 FIFO로 2번이 먼저 POP이 된다.

하지만 실제 운영체제에서는 Block State Queue는 Queue라고 이름을 붙였음에도, Queue의 일반적인 정책에는 위반되죠. 실제로는 Queue라기보다 Block State에 있는 프로세스들의 리스트이다. 통상적으로 다양한 스케쥴링 방식에 따라서 Blcok State Queue의 동작이 달라질 수 있기 때문에, 각 스케쥴링 방식마다 이름을 달리 붙이기 보다는, 이렇게 Wait Queue 또는 Block State Queue라고 보통 이름을 붙인다. 특별한 정책을 가진 Queue라고 생각해주시면 좋다.

실제로는 리눅스의 예만 봐도, wait queue라고 이름을 붙이고 있는데, 내부적으로는 wait queue 에 있는 모든 프로세스를 한번에 깨우거나, 그 중 특별한 조건만을 가진 프로세스를 깨우거나, 하나만 특정해서 깨우고 있다.