Process Scheduling (Context Switching)

Process Scheduling

CPU는 짧은 시간 단위로 scheduling을 해서 process들을 번갈아가면서 수행한다.

이를 multitasking이라 한다.

Multitasking을 위해서는 scheduling이 반드시 필요하다.

 

OS가 memory에 load 된 여러 process들 중 다음에 실행할 process를 선택하는 것을 scheudling이라 한다.

 

pseudo code로 나타내면 다음과 같다.

while(1) {
	프로세스 실행 : run the process for a while
	프로세스가 CPU를 yield하거나 interrupt를 발생할 때까지 기다림 : wait until an interrupt happens or the process yields CPU
	프로세스를 멈추고 state를 저장(PCB) : stop it and save its state
	다음에 실행할 프로세스 선택 : choose another process to run next
	선택된 프로세스의 state를 load : load the state of chosen process
}

 

Scheduling, Dispatching

policy(의사결정)와 mechanism(의사결정을 실행)가 분리되어있다.

• scheduling
  • OS가 memory에 load 된 여러 process들 중 다음에 실행할 process를 선택
  • 여러 policy가 존재한다.
  • chosse another process to run next
• dispatching
  • 선택된 process를 실제로 실행하는 것
  • = mechanism
  • 프로세스 실행, 프로세스를 멈추고 state를 저장, 선택된 프로세스의 state를 load
    • run the process for a while, stop it and save tis state, load the state of chosen process

 

---

Context Switching

Dispatcher가 다른 process로 전환하는 것을 말한다.

Dispatching에 속한다.

 

다른 process로 전환될 때 이전 process의 상태를 저장하고, 새로운 process의 저장되어있는 상태를 load 해야 한다.

이를 context switching이라 한다.

 

Process Context

Process context(process state)는 보통 3가지로 나눈다.

• system context
  
  • memory(kernel space)에 저장되어 있다.
  • memory management, accounting, I/O status information
• memory context
  • address space : code, data, stack, heap segment
• processor context (CPU context)
  • CPU register(PC, 범용 register)들의 현재 값들

 

Scheduling 할 때는 context가 바뀌게 된다.

 

Process control block은 메모리에 존재하기 때문에 메모리 영역에 있는 값들은 OS가 별도의 작업을 하지 않아도 된다.

따라서 system context와 memory context는 운영체제가 별도로 작업을 할 필요가 없다.

 

Processor context는 CPU에 존재하기 때문에 OS가 별도의 작업을 통해서 값을 저장해야 한다.

 

Context Switching의 이유 & 장소

Scheduling은 process의 작업이 끝난 후 발생하는 것이 아니라 예측할 수 없는 임의의 시점에 발생한다.

예를 들어 timer interrupt가 발생한다면 interrupt가 발생한 그 시점에 즉시 context switching이 일어난다.

 

따라서 다른 process로 전환된 후 다시 해당 process로 돌아왔을 때 정상적으로 수행하기 위해서 기존의 데이터들을 저장하고 복원해야 한다.

이를 위해서 memory, 특히 kernel space에 있는 PCB(process control block)에 저장한다.

 

Overhead

Context switching을 하면 overhead가 발생한다.

Context switching을 할 때는 다른 작업을 할 수 없기 때문이다.

 

Multitasking과 overhead에서의 scheduling 간격은 trade-off 관계이다.

 

Scheduling의 간격을 줄이면 context swtching을 하는 시간 대비 process가 실제 작업을 하는 시간이 늘어나기 때문에 overhead가 더 늘어나게 된다.

따라서 overhead 관점에서 scheduling이 일어나는 간격은 클 수록 좋다.

 

그러나 scheduling의 간격을 줄인다면 multi-tasking의 효과가 줄어든다.

따라서 multi-tasking 관점에서 scheduling이 일어나는 간격은 작을 수록 좋다.

 

Register Set의 수와 Overhead

Register set을 여러 개 제공하면 context switching로 인한 손실을 줄일 수 있다.

Process context를 저장하는 것 대신에 다른 register set을 사용함으로써 context switching으로 인한 손실을 줄인다.

DECSYSTEM-20이 이를 이용한 방식이다.

 

그러나 이는 CPU가 커지는 것을 야기하는데, die의 공간은 비싸고 가격 대비 성능도 좋지 않다.

 

---

Scheduling Queue

운영체제에는 scheduling과 관련한 3종류의 queue가 있다.

• job queue
  • process bookkeeping을 위한 것이다.
  • 생성된 모든 프로세스들을 담는다.
• ready queue
  • CPU scheduling(processor scheduling)을 위한 것이다.
  • CPU를 기다리는 프로세스들을 담는다.
  • running이 아닌 ready 상태인 프로세스들을 담는다.
  • scheduler가 실행할 새로운 process를 선택할 때 ready queue에 있는 프로세스들 중 선택한다.
• device queue
  • I/O scheduling을 위한 것이다.
  • I/O 작업을 요청하고 기다리는 프로세스들을 담는다.
  • waiting 상태의 process들이 담겨있다.

 

Ready queue와 device queue는 process의 상태와 맞물려서 들어있는 요소들이 바뀐다.

각 queue에는 해당하는 process들의 PCB가 linked list로 연결된 형태로 담겨져있다.

 

device queue에도 I/O scheduler의 scheduling 정책이 존재한다.

I/O device마다 I/O scheduler의 정책이 다르지만, 일반적으로 FIFO를 많이 사용한다.