[ OS ] Multiprocessor Scheduling

1. Multiprocessor Scheduling

 

이 챕터에서는 코어가 여러개일 때 스케줄링하는 방법에 대한 이야기이다. 

 

 

1.1 Multiprocessor Architecture

 

 

코어는 각각 캐시를 가지고 있으며 공통된 캐시를 가지고 있다. 대부분의 노트북과 컴퓨터는 위와같은 구조를 보인다. 각 CPU는 멀리있는 Memory도 사용 가능하다.

 

1.2. Single-queue multiprocessor scheduling (SQMS)

 

이 방법은 CPU가 여러개더라도 하나의 Queue로 운영하는 방법이다. 큐에서 job을 꺼낼때는 코어의 개수만큼 한번에 꺼내서 쓸 수 있다.  A를 계속 실행하는데 CPU 를 옮겨다니므로 처리해야할 부분이 늘어난다. 그렇게 되면 동기화 오버해드가 일어날 수도 있다.

 

 

1.3. Multi-queue multiprocessor scheduling (MQMS)

 

이 방법은 CPU당 하나의 큐로 운영하는 방법이다. 각자 자기 CPU의 큐를 이용하므로 동기화 오버해드는 일어나지 않을 것이다.

 

1.4. Problem of Multi-queue multiprocessor scheduling (MQMS)

 

1) 한 CPU에 하나의 프로세스만 존재하고 다른 CPU에는 여러 프로세스가 있다면 혼자있는 프로세스가 독점

2) 한 CPU에 일이 없고 다른 프로세스에 일이 있어도 하나는 놀고 하나는 일해야함

 

1.5. Solution of Multi-queue multiprocessor scheduling (MQMS) Problem

 

위 문제를 해결하는 방법은 CPU에 일이 하나도 없을 때 다른 CPU의 job을 훔쳐오는 방법이다. 이는 Work stealing라 부른다 . 어떤 프로세스를 가져오는가에 대한 내용은 다 다르겠지만 보통은 mrmory bound가 적은 프로세스를 데려온다. 

 

1. Completely Fair Scheduler (CFS)

리눅스의 CPU 스케줄러는 여러가지가 있다. 스케줄러를 바꾸기 위해서는 root 권한이 필요하다. 

 

1) Completely Fair Scheduler (CFS)

2) Real-Time Schedulers

3) Deadline Scheduler - 데드라인이 급한 애들부터 실행

 

1.1 Completely Fair Scheduler (CFS)

리눅스 CPU 스케줄러중에 가장 기본적인 알고리즘.  점유하고 있는 시간을 나타내고 왼쪽 아래로 갈수록 가장 적은 값이 있다. 

 

여기서 vruntime은 기존 런타임에 프로세스마다 가중을 준 가상 런타임이다. 아래 식으로 정해진다. 

여기서 nice는 얼마나 양보했는가를 말한다.  -20~ 19 사이의 값을 가지고 높을수록 양보를 잘 하는 job이다. 

기본 값은 0 이다. 

 

양보해야하는 job이 필요할 때는 Nice 값을 높여주면 가중치도 높아지고 실제 vruntime이 높아진다. 그럼 os가 양보하게 한다. 그 반대도 성립한다. 

 

1.2 Priority

 

pio = nice + 120  

 

nice 는 -20 부터 19이므로 pio은 100~139 가 된다. 하지만 우선순위보다는 vruntime이 더 중요하게 사용된다. 그럼 prio는 어디다가 쓸까? CFS 보다 더 우선순위가 높은 스케줄러 SCHED_FIFO, SCHED_RR, SCHED_DEADLINE 에서 엄격하고 중요하게 쓰인다. 

 

1.3 Multiprocessor Scheduling in CFS

 

멀티 코어에서 CFS는 어떻게 쓰일까?

 

먼저 큐의 길이는 각 스레드가 얼마큼 CPU를 사용하고 있는가 (CPU사용시간/ 단위시간) 의 평균으로 계산한다. 스레드의 prio가 높으면 CPU를 많이 썼다고 판단한다 그러면 load가 높다고 생각하고 다른 스레드를 넣지 않는다 이 스래드의 평균이 큐의 길이이다.

 

1.4 Scheduling classes

 

1) 스케줄러 클래스

struct sched_class {

	void (*enqueue_task) (struct rq *rq, 
							struct task_struct *p, 
							int flags);
	void (*dequeue_task) (struct rq *rq, 
							struct task_struct *p, 
							int flags);
	...
	struct task_struct *(*pick_next_task)(struct rq *rq);  //스케줄러 알고리즘
	...
	int (*balance)(struct rq *rq, struct task_struct *prev,
					struct rq_flags *rf);
                    // taxk Queue 의 밸런스를 맞춰줌
...
}

 

2) 각 스케줄러 구조체 정의

extern const struct sched_class dl_sched_class;  // dead line
extern const struct sched_class rt_sched_class;  // fifo 와 RR
extern const struct sched_class fair_sched_class;  //CFS 
extern const struct sched_class idle_sched_class; 
//위의 스케줄링 애들이 실행시킬게 없을 때 실행할 것들을 관리

 

3) CFS 스케줄링 클래스

DEFINE_SCHED_CLASS(fair) = {
	.enqueue_task = enqueue_task_fair,
	.dequeue_task = dequeue_task_fair,
	...
	.pick_next_task = __pick_next_task_fair,  
    // ready Queue 에서 누구를 데려올까 결정하는 함수, vruntime이 가장 작은 애를 데려올 것이라고 예상
	...
	.balance = balance_fair,
	...
}

4) 각 코어마다 있는 CPU runqueue 

struct rq { //run Queue , 레디큐를 모아놓은 것
	raw_spinlock_t lock; // 동기화를 위함
	...
	struct cfs_rq cfs;
	struct rt_rq rt;
	struct dl_rq dl;
	...
    //Process Control Block
	struct task_struct *curr;
	struct task_struct *idle;
}

5) 운영체제는 초기화할 때 timer 값을 지정

static void __sched notrace __schedule(bool preempt)
{
	...
	prev = rq->curr;  // 현재 실행중인 프로세스의 PCB 저장
	...
	next = pick_next_task(rq, prev, &rf); // 다음 실행시킬 프로세스의 PCB 저장
	...
	rq = context_switch(rq, prev, next, &rf);  // pre 재우고 next 깨우고
	...
}

6) 다음 실행 시킬 프로세스를 찾는 함수

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, 
struct rq_flags *rf)
{
	...
	put_prev_task_balance(rq, prev, rf);
    
	for_each_class(class) {  // 스케줄러 클래스를 우선순위대로 돌며 vruntime 이 작은 애들 찾는다
		p = class->pick_next_task(rq);
		if (p)
			return p;
	}
	...
}