[OS] 3-2. 프로세스 스케쥴링

다중 프로그래밍의 목적은 CPU 이용을 최대화하기 위해 항상 어떤 프로세스를 실행되도록 하는데 있다.
시분할(time sharing)의 목적은 각 프로그램이 실행되는 동안 사용자가 상호작용할 수 있도록 프로세스들 사이에서 CPU 코어를 빈번하게 교체하는 것이다.
때문에, 어떤 프로세스를 선택해야 하는지 결정해주는 프로세스 스케쥴러가 필요하다.

각 CPU 코어는 한 번에 하나의 프로세스를 실행할 수 있다.

• 단일 CPU 코어 ⇒ 한 번에 하나의 프로세스를 실행할 수 있다.
• 다중 CPU 코어 ⇒ 한 번에 여러 개의 프로세스를 실행할 수 있다. 코어보다 많은 프로세스가 있다면 남아있는 프로세스는 코어를 사용할 수 있는 상태에서 다시 스케쥴 될 때 까지 대기해야 한다. 이때, 현재 메모리에 있는 프로세스의 개수를 다중 프로그래밍 정도(degree)라고 한다.

다중 프로그래밍과 시분할(time sharing)의 목표를 균형있게 유지하려면 프로세스의 일반적인 동작을 고려해야 한다.

• I/O 바운드 프로세스 : CPU 연산 시간 < I/O 처리 시간 인 프로세스
• CPU 바운드 프로세스 : CPU 연산 시간 > I/O 처리 시간 인 프로세스

1. 스케쥴링 큐

준비 큐 (ready queue)

프로세스가 시스템에 들어가면 준비 큐(ready queue)에 들어가 ready 상태가 되고 CPU 코어에서 실행되기를 기다린다.
준비 큐는 일반적으로 연결 리스트로 저장된다.
준비 큐의 헤더에는 리스트의 첫 번째 PCB에 대한 포인터가 저장되어 있고
각 PCB에는 준비 큐에서 해당 PCB 다음에 있는 PCB를 가리키는 포인트 필드가 포함된다. (연결 리스트를 이용한 큐 구현을 생각하면 된다)

대기 큐 (Waiting queue)

프로세스에 CPU 코어가 할당되면 프로세스는 잠시 동안 실행되다가...

• 종료
• 인터럽트
• I/O 요청의 완료와 같은 특정 이벤트가 발생할 때 까지 대기

ex) 프로세스가 I/O 요청을 한다고 가정하자.

processor의 속도가 device(I/O 장치) 보다 빠르기 때문에 process는 I/O할 수 있을 때 까지 대기해야 한다.
이때, I/O 완료와 같은 특정 이벤트가 발생하기를 기다리는 프로세스들은 대기 큐(waiting queue)에 삽입된다.

• ready queue / waiting queue
  

  

프로세스 스케쥴링은 아래 그림과 같은 큐잉 다이어그램으로 표현할 수 있다. ready queue, waiting queue라는 2가지 유형의 큐가 제시되어 있다. 동그라미는 큐에 서비스를 제공하는 자원을 나타내고 화살표는 시스템의 프로세스 흐름을 나타낸다.

1) 새로운 프로세스는 처음에 ready queue에 놓인다. 프로세스는 실행되기 위해 선택되거나 dispatch 될 때 까지 기다린다.
2) 프로세스에 CPU 코어가 할당되고 실행 상태(running)가 되면 여러 이벤트 중 하나가 발생할 수 있다.
- 프로세스가 I/O 요청을 하고 나서 I/O 대기 큐에 놓일 수 있다.
- 프로세스가 새로운 자식 프로세스(child process)를 만든 다음 자식 프로세스가 종료할 때 까지 대기 큐에 놓일 수 있다
- 인터럽트 또는 시간이 만료되어 프로세스가 코어에서 강제로 제거되어서 준비 큐로 돌아갈 수 있다.

2. CPU 스케쥴링

CPU 스케쥴러의 역할은 준비 큐(ready queue)에 있는 프로세스 중에서 선택된 하나의 프로세스에 CPU 코어를 할당하는 것이다.

하나의 프로세스에게 CPU 코어를 길게 할당하기 보다는
기존 프로세스의 CPU 코어 할당을 해제하고 다른 프로세스가 스케쥴 되도록 설계할 가능성이 높다.
때문에 CPU 스케쥴러는 적어도 100밀리초마다 한 번씩 실행된다.

일부 OS는 swapping형태의 스케쥴링을 갖고 있는데
핵심 아이디어는 가끔식 메모리에서 프로세스를 제거해서 다중 프로그래밍의 정도(degree)를 감소시키는 것이 유리할 수 있다는 것이다. 관련 내용은 9장에서 설명한다.

3. 문맥 교환 (Context Switching)

인터럽트(interrupt)는 OS가 CPU 코어를 현재 작업에서 kernel 루틴으로 변경할 수 있도록 한다.

때문에 인터럽트가 발생하면 시스템은 인터럽트의 처리가 끝난 이후 문맥(context)을 복구할 수 있도록 현재 실행 중인 프로세스의 context를 저장할 필요가 있다. 이는 프로세스를 중단했다가 재개하는 작업이다.

context는 프로세스의 PCB에 표현된다. context는 CPU 레지스터 값, 프로세스 상태(state), 메모리 관리 정보 등등 을 갖고 있다.

사용자 모드, 커널 모드 상관없이 CPU의 현재 상태을 저장하는 작업을 수행하고 연산을 다시 시작하기 위해 복구 작업을 수행한다.

• 프로세스에서 프로세스로 context switching을 보여주는 다이어그램

context switching(문맥 교환)이란 CPU 코어를 다른 프로세스로 교환할 때 이전 프로세스의 상태를 저장 & 새로운 프로세스의 저장된 상태를 복구하는 작업을 말한다.

context switching이 발생하면

1) 커널은 이전 프로세스의 context를 PCB에 저장하고
2) 실행될 새로운 프로세스의 context 새로운 프로세스의 PCB로 부터 복구한다.

이때, context switching 이 실행되는 동안의 시간은 overhead가 된다. context switching이 실행되는 시간에는
메모리 속도, 복사해야 하는 레지스터의 개수, 특수 명령어, HW 자체에 따라 달라진다.

OS가 복잡해질 수록 context switching 시 해야 할 작업의 양이 더 많아진다. 관련된 내용은 9장에서 좀 더 자세히 살펴본다.