[Process] Process Scheduling

지난 포스트에서 이야기 했던 것처럼 Process에는 각각의 상태를 나타내는 state가 존재하고 이를 OS level에서 처리하기 위해 필요한 정보를 모아놓은 Process Control Block을 운용한다고 했다. 그 때 얼핏 나왔던 이야기가 Process는 여러개 존재하지만 CPU는 한번에 한 instruction만 수행할 수 있다고 했었다. 이 말을 다르게 표현하면 각 Process마다 정해진 규칙에 따라서 수행되어야만 system Resource를 효율적으로 처리할 수 있다는 것이다. 

 결국 Process state에 따라서 어떤 scheduling 방식을 취하냐는 CPU의 Utilization에도 영향을 미친다는 말이 된다. 당연히 우리가 할려는 효율적인 Multi Programming을 위해서는 Process Scheduler가 있어야 될 거 같다. 그래서 그 부분에 대한 이야기를 잠깐 해보려고 한다. 

 일단 첫번째로 생각해볼 수 있는 방법이 Queue라는 것이다. 자료구조론을 들은 사람이라면 원리를 잘 알겠지만 전형적인 First In First Out(FIFO) 구조를 가지고 있다. 즉 먼저 들어온 Process가 System내에서 가장 먼저 처리되게끔 구현하자는 것이다. 그러면 Process가 생성되는대로 이 Queue내에서 대기하고 있다가 받은 순서대로 차례대로 수행되는 것이 된다. 물론 이 Process가 생성되는 과정은 여러가지가 있을 것이다.

그림에서 나온 것처럼 interrupt가 발생했을 때, 또는 나중에 설명하겠지만 Fork() 를 통한 생성, 혹은 주기적인 Process 일 경우에는 정해진 time slice가 끝날때 마다 Process가 생성될 것이다. 앞에서 언급한 Queue에 특성상 먼저 들어온 순서대로 Ready Queue에 삽입되고 CPU를 통해서 처리될 것이다. 그런데 사실 지금까지 말한 방법 자체는 하나의 Scheduling Policy중 하나일 뿐이다. 말그대로 먼저 들어오는 것을 먼저 처리하겠다는 규칙을 정한 것일뿐 사용자에 따라서는 다른 Policy를 취할 수도 있을 것이다. 이같은 내용은 Linux kernel 소스에서도 찾아볼 수 있다.

/*
 * Scheduling policies
 */
#define SCHED_NORMAL		0
#define SCHED_FIFO		1
#define SCHED_RR		2
#define SCHED_BATCH		3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE		5
/* Can be ORed in to make sure the process is reverted back to SCHED_NORMAL on fork */
#define SCHED_RESET_ON_FORK     0x40000000

Linux Kernel Source 중에 usr/include/linux로 들어가면 sched.h 라는 헤더파일이 있는데 이게 바로 Process Scheduling에 대한 기본적인 struct 정의가 담겨있는 파일이다. 여기서 보면 위와 같이 Scheduling Policy에 대한 설정을 할 수 있게끔 전역변수로 지정되어 있다. 말그대로 Round Robin 이나 Batch 형식으로 바꾸고 싶다면 Task Struct 내에 있는 policy의 값을 위 중 하나로 변경하면 된다. 

struct task_struct {
	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
	void *stack;
	atomic_t usage;
	unsigned int flags;	/* per process flags, defined below */
	unsigned int ptrace;

#ifdef CONFIG_SMP
	struct llist_node wake_entry;
	int on_cpu;
#endif
	int on_rq;

	int prio, static_prio, normal_prio;
	unsigned int rt_priority;

           ...............

	unsigned char fpu_counter;
#ifdef CONFIG_BLK_DEV_IO_TRACE
	unsigned int btrace_seq;
#endif

	unsigned int policy;
	cpumask_t cpus_allowed;

#ifdef CONFIG_PREEMPT_RCU
	int rcu_read_lock_nesting;
	char rcu_read_unlock_special;
	struct list_head rcu_node_entry;

...................

참고로 위와 같이 Task ( 저번에 Process와 동일한 개념이라고 했었다) 에 대한 모든 정보를 가지고 있는 Struct 구조를 Task Descriptor 또는 Process Descriptor라고 하고 보통 Linked list 형태로 구현되어 있다. 

자 그럼 이제 Process에 대한 것을 봤으니 다시 위의 Process Scheduling 그림을 보자. 

여기서 Scheduler의 역할을 수행하는 것이 뭘까? Scheduler란 말 그대로 job을 처리할 순서를 정해주는 부분이다. 그러면 그림에서는 ready Queue와 CPU가 일종의 Scheduler라고 볼 수 있겠다. 그런데 어떤 사람은 CPU는 Process를 처리하는 최종단계인데 이게 Process가 처리되는 순서를 결정지어주냐 의문을 가질 수 있다. 사실 위에서 보여진 CPU 블럭은 CPU와 CPU Scheduler가 함께 표현된 형태이다. 그대신 이 Scheduler에서 처리된 내용은 바로 cpu를 통해서 수행되므로 그만큼 Process간의 term이 매우 짧을 것이다. 그래서 이런 경우를 보통 short term Scheduler라고 한다. 반대로 앞에 있는 Ready Queue는 Process가 생성 된 것을 한꺼번에 담고 있으므로 그만큼 각각을 처리하는 term이 길 것이다. 그래서 이런 것을 long term scheduler라고 말한다.

  그런데 이 말은 Process가 생성될 때 모두 동일한 형태, 또는 동일한 우선 순위를 가지고 있다는 가정하에 성립하는 것이다. 사실 Process를 보면 시스템 동작에 필수적이고 빠르게 수행되어야 할 Process가 있을 것이고, 또는 앞의 Process에 비해서 오래 걸리면서 별로 중요하지 않는 Process가 있을 것이다. 보통 I/O와 관련된 process 가 그렇다. 여담으로 아는 사람은 알겠지만 PC 구성요소 중에서 I/O와 관련된 장치들의 처리속도가 가장 느리고, 발전 속도도 가장 느리다. 그래서 PC의 체감 성능이 낮게 느껴지는 이유가 여기에 있다. 

 아무튼 이런 I/O와 관련한 Process가 처리되고 있는 순간에 중요한 Process가 개입했다면 당연히 중요한 Process를 먼저 처리하고 그다음으로 이어서 처리되게끔 할 것이다. 이때 등장하는 mechanism이 swapping이다. 그래서 위와 같은 상황이 발생하는 경우에는 CPU 내에서 Process Swap이 이뤄지게끔 구현되어 있다. 실제로 앞에서 소개한 Task Struct에서도 Swap이 가능한 Task에 대해서는 따로 Process flag를 설정할 수 있게끔 정의되어 있다. 이렇게 process swapping 도 일종의 scheduler라고 볼 수 있으며, 이걸 mid-term scheduler라고 한다. 그래서 그걸 그림으로 표현한게 다음과 같다.

정리해보자면 Short Term Scheduler는 보통 ms 단위로 처리되고, 자주 발생된다. 당연히 상대적으로 long term 방식에 비해서 처리속도가 빨라야만 한다. 그러면 전체 task 처리에 있어서 큰 영향을 주는 것은 빠르게 처리되는 Short term scheduler를 더 빠르게 개선하는 것이 아니라, 원래 느렸던 long term scheduler를 빠르게 만드는 것이 되겠다. 보통 process를 한번에 여러개 처리하는 방식으로 개선해나가고 있으며, 그런 걸 multiprogramming이라고 한다. 즉 앞에서도 나왔지만 효율적인 Multi Programming을 위해서는 이 long term Scheduler가 한번에 Process를 얼마나 처리할 수 있느냐가 관건이 되겠다.

 유념을 해야 될게 있다면, 지금 Process가 나열되어 있는 상태인데 지난 포스트에서도 소개했던 것처럼 Process가 저장된 Memory Address도 다르고 이에 따른 CPU Register도 각 Process마다 다르다. 그렇기 때문에 어떤 연유로 인해서 Process가 바뀔 때에는 이전 Process의 information을 저장하고 새 Process의 information을 불러오는 과정을 거친다. 이런 과정을 Context Switching이라고 하는데 이 과정에서 Memory에 저장하고 불러오는 것에 대한 Overhead가 매우 크다. 그래서 이를 가능한 한 최소화 하는 것이 이슈가 된다. 이 부분에 대해서 Linux kernel 이 어떻게 처리하는지가 궁금하면 역시 source를 살펴보면 된다. /usr/src/kernel/sched.c 에서 볼수 있으며, source에는 다음과 같이 명시되어 있다.

/*
 * context_switch - switch to the new MM and the new
 * thread's register state.
 */
static inline void
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next)
{
	struct mm_struct *mm, *oldmm;

	prepare_task_switch(rq, prev, next);

	mm = next->mm;
	oldmm = prev->active_mm;
	/*
	 * For paravirt, this is coupled with an exit in switch_to to
	 * combine the page table reload and the switch backend into
	 * one hypercall.
	 */
	arch_start_context_switch(prev);

	if (!mm) {
		next->active_mm = oldmm;
		atomic_inc(&oldmm->mm_count);
		enter_lazy_tlb(oldmm, next);
	} else
		switch_mm(oldmm, mm, next);

	if (!prev->mm) {
		prev->active_mm = NULL;
		rq->prev_mm = oldmm;
	}
	/*
	 * Since the runqueue lock will be released by the next
	 * task (which is an invalid locking op but in the case
	 * of the scheduler it's an obvious special-case), so we
	 * do an early lockdep release here:
	 */
#ifndef __ARCH_WANT_UNLOCKED_CTXSW
	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
#endif

	/* Here we just switch the register state and the stack. */
	switch_to(prev, next, prev);

	barrier();
	/*
	 * this_rq must be evaluated again because prev may have moved
	 * CPUs since it called schedule(), thus the 'rq' on its stack
	 * frame will be invalid.
	 */
	finish_task_switch(this_rq(), prev);
}