프로세스 스케줄링 (Process Scheduling)

1. 프로세스 스케줄링 (Process Scheduling)

Process scheduler가 실행 가능한 여러 프로세스 중에서 하나의 process를 선택한다.

(1) 프로세스 스케줄링의 목적

• 단일 프로세서 시스템에서는 한 번에 한 프로세스만 실행될 수 있다.
• 하지만 I/O 장치에서 응답을 기다리는 경우 CPU는 일을 하지 않고 기다리게 된다.
• 한 프로세스를 실행 가능한 시점까지 실행하고, I/O 등 CPU를 사용하지 않은 작업을 할 때는 다른 프로세스를 실행한다면 CPU 사용 효율을 높일 수 있다. 
• CPU 활용을 최대화 하기 위해서, OS는 빠르게 CPU로부터 Process를 교환한다.'

(2) 프로세스 스케줄링 과정

• 새로운 프로세스는 초기에 ready queue에 놓인다. 실행을 위해 선택(dispatch) 될 때까지 ready queue에서 기다린다.
• 일단 프로세스에게 CPU가 할당되면, 아래 이벤트(event) 발생할 때까지 해당 프로세스가 CPU에서 실행된다.
  • 프로세스가 입출력 요청을 하여 입출력 큐에 넣어진다.
  • 프로세스가 새로운 자식 프로세스를 생성하고 자식 프로세스의 종료를 기다리는 동안 대기 큐에 놓일 수 있다.
  • 프로세스가 인터럽트(timer event) 발생을 기다린다.
  • 인터럽트 또는 할당된 시간 간격이 만료되어 프로세스가 코어에서 강제로 제거되어 준비 큐에 돌아갈 수 있다.

 

2. 스케줄러 (Schedulers)

(1) Long-term scheduler (작업 스케줄러, job scheduler)

디스크에 있는 프로그램들을 선택해서 실행을 위해 메모리로 적재(load) 한다. 
Ready Queue에 놓인다.

• 디스크에 있는 프로그램을 어떤 순서로 가져와서 처리될 것인가를 결정한다.
• CPU-bound와 I/O bound 작업을 잘 혼합하여 선택한다.

(2) Short-term scheduler (CPU scheduler)

Ready Queue에서 실행을 기다리고 있는 process들 중 한 개를 선택해서 CPU를 할당한다.

• 더 long-term scheduler 보다 빈번하게 프로세스를 선택한다.
  • CPU를 쉬지 않게 하기 위해서 process 교체가 빈번하다.

(3) Medium-term scheduler 

메모리에 올라와 있는 process들 중 선택해서 스와핑(swapping)을 통해서 disk로 process를 보낸다.

• 메모리에 너무 많은 process가 올라와 있을 수 있다. 이 경우 여유 공간을 마련하기 위해서 process를 선택해서 제거해야 한다.
• 스와핑(Swapping) :
  • Swap out : 메모리에서 프로세스를 제거하고 디스크에 저장한다.
  • Swap in : 이후 실행을 다시하기 위해 디스크에서 메모리로 프로세스를 다시 가져온다.

 

3. 스케줄링 큐 (Scheduling Queue)

(1) Ready Queue (준비 큐)

• program이 메모리에 적재되면 Ready Queue에 들어가서 준비 상태가 되어 CPU 코어에서 실행되기를 기다린다.
• Ready Queue는 일반적으로 연결 리스트로 저장된다.
• 헤더에는 리스트의 첫 번째 PCB에 대한 포인터가 저장되고 각 PCB에는 준비 큐의 다음 PCB를 가리키는 포인터 필드가 포함된다. 

(2) Wait Queue (대기 큐)

• I/O 완료와 같이 특정 이벤트가 발생하기를 기다리는 프로세스는 대기 큐에 삽입되어서 waiting 한다.

 

4. Context Switching (문맥 교환)

CPU 코어를 다른 프로세스로 교환하기 위해 이전의 프로세스의 상태를 보관하고 새로운 프로세스의 보관된 상태를 복구하는 작업

(1) Context Switching 과정

• 1. 요청 발생 : interrupt 또는 System Call
• 2. 커널은 과거 프로세스(P0)의 context를 PCB에 저장한다.
• 3. 실행이 스케줄 된 새로운 프로세스(P1)의 context가 저장된 PCB를 이용하여 복구한다.

(2) Context Switching Time

• context switching이 진행될 동안 시스템이 아무런 유용한 일을 못 하기 때문에 순수한 overhead가 발생한다.
• context switching time은 하드웨어의 지원에 크게 좌우된다.