💾

06 : Multiprocessor Scheduling

course

last review

2023/04/15

mastery

none

progress

not started

date

2023/03/21

4 more properties

Previous chapter

05 : Multi-Level Feedback Queue

Single-Queue Scheduling

Multi-Queue Scheduling

Linux CPU Schedulers

Completely Fair Scheduler (CFS)

/proc/<pid>/sched

Control Group(cgroup)

Diving into Linux Kernel v5.11.8

Header 1

SMP는 Symmetric Multiprocessing의 약어로 대칭형 다중 처리 시스템을 의미합니다. SMP 시스템에서는 여러 개의 프로세서가 한 개의 메모리에 접근할 수 있으며, 모든 프로세서는 동일한 우선순위로 처리됩니다. 이러한 구조로 인해 SMP 시스템은 높은 처리량을 보장할 수 있습니다. 그러나 SMP 시스템에서는 캐시 일관성 문제와 같은 고려할 점이 있습니다.

NUMA는 Non-Uniform Memory Access를 나타내며, SMP와 유사하지만, 메모리가 노드로 구성되어 있는 시스템에서 사용됩니다. 각 노드는 로컬 메모리와 원격 메모리를 가지고 있으며, 로컬 메모리에 대한 접근은 빠르지만 원격 메모리에 대한 접근은 느립니다. 따라서, NUMA 시스템에서는 프로세서와 메모리 간의 거리를 고려하여 작업을 스케줄링하고 메모리 할당을 최적화합니다.

Single-Queue Scheduling

Single-Queue Multiprocessor Scheduling (SQMS)는 여러 개의 프로세서가 공유하는 하나의 큐에서 작업을 가져와 처리하는 스케줄링 알고리즘입니다. 이 알고리즘에서는 각 프로세서가 독립적으로 작업을 수행하며, 큐에 대한 접근은 원자적으로 보호됩니다. 따라서, SQMS는 SMP 시스템에서 사용하기에 적합합니다. SQMS는 각 프로세서의 공정한 분배를 보장하며, 작업을 처리하는 데 걸리는 시간이 일정하지 않은 경우에도 효율적으로 작동합니다.

Multi-Queue Scheduling

Linux CPU Schedulers

Completely Fair Scheduler (CFS)

vruntime

각 태스크는 virtual runtime에 기반한 R-B 트리에 저장된다.

Weighted runtime은 각 프로세스의 nice value(-20~19)를 기반으로 계산된다.

vruntime의 업데이트 방정식은 다음과 같다.

\text{vruntime}=\text{vruntime} +\text{DeltaExec}\times \cfrac{Weight_0}{Weight_P}

/proc/<pid>/sched

Priority

prio = nice + 120

•

CFS : 100~139

•

0~99는 real-time scheduler가 쓴다.

nice 값을 바꾸고 싶을 때는 renice 커맨드를 쓰면 된다.

•

유저는 nice를 -1~-20으로 바꿀 수 없다.

•

root 권한만 가능

Control Group(cgroup)

Diving into Linux Kernel v5.11.8

•

Scheduling classes (/kernel/sched/sched.h)

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 tast_struct *(*pick_next_task)(struct rq *rq);
		...
		int (*balance) (struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
		...
}
C
복사

Next chapter