linux-debug/scheduling

created : Wed, 09 Dec 2020 13:30:45 +0900
modified : Wed, 23 Jun 2021 15:35:51 +0900
linux

주요 키워드

선점 스케쥴링과 비선점 스케쥴링 비교

스케줄링 정책

#define SCHED_NORMAL    0
#define SCHED_FIFO      1
#define SCHED_RR        2
#define SCHED_BATCH     3
#define SCHED_IDLE      5
#define SCHED_DEADLINE  6

스케줄러 클래스

런큐

우선순위(nice)

프로세스 상태 관리

#define TASK_RUNNING          0x0000
#define TASK_INTERRUPTIBLE    0x0001
#define TASK_UNINTERRUPTIBLE  0x0002
#define __TASK_STOPPED        0x0004
#define __TASK_TRACED         0x0008

프로세스 상태

TASK_INTERRUPTIBLE과 TASK_UNINTERRUPTIBLE 상태의 차이점

프로세스 상태 변화

@startuml
[*] --> TASK_RUNNING_실행대기
TASK_RUNNING_실행대기 --> TASK_RUNNING_CPU실행 : 1
TASK_RUNNING_CPU실행 --> TASK_INTERRUPTIBLE : 2
TASK_RUNNING_CPU실행 --> TASK_UNINTERRUPTIBLE : 3
TASK_INTERRUPTIBLE --> TASK_RUNNING_실행대기 : 4
TASK_RUNNING_CPU실행 --> TASK_DEAD : 5
TASK_UNINTERRUPTIBLE --> TASK_RUNNING_실행대기
TASK_DEAD --> [*]
@enduml

프로세스 상태 변화 함수 목록

TASK_RUNNING(실행 대기)으로 바뀔 때 호출되는 함수

TASK_RUNNING(CPU 실행)로 바뀔 때 호출하는 함수

static void __sched notrace __schedule(bool preempt)
{
  struct rq *rq;
  int cput;

  cpu = smp_processor_id();
  rq = cpu_rq(cpu);

  if (likely(prev != next)) {
    rq->nr_switches ++;
    rq->curr = next;

    /* Also unlocks the rq: */
    rq = context_switch(rq, prev, next, &rf);
  } else {
  /* skip */
}

TASK_INTERRUPTIBLE 상태로 바뀔 때 호출하는 함수

#define wait_event_interruptible(wq_head, condition)            \
({                                                              \
  int __ret = 0;                                                \
  might_sleep();                                                \
  if (!(condition))                                             \
    __retval = __wait_event_interruptible(wq_head, condition);  \
  __ret;                                                        \
})

#define __wait_event_interruptible(wq_head, condition)          \
  ___wait_event(wq_head, condition, TASK_INTERRUPTIBLE, 0, 0,   \
    schedule())

#define ___wait_event(wq_head, condition, state, exclusive, ret, cmd)  \
({                                                                     \
  __label__ __out;                                                     \
  struct wait_queue_entry __wq_entry;                                  \
  long __ret = ret; /* explicit shadow */                              \
                                                                       \
  init_wait_entry(&__wq_entry, exclusive ? WQ_FLAG_EXCLUSIVE : 0);     \
  for (;;) {                                                           \
    long __int = prepare_to_wait_event(&wq_head, &__wq_entry, state);  \
    /* skip */                                                         \
  }                                                                    \
  finish_wait(&wq_head, &__wq_entry);                                  \
__out: __ret;                                                          \
})

long prepare_to_wait_event(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry.
  int saste)
{
  unsigned long flags;
  long ret = 0;

  spin_lock_irqsave(&wq_head->lock, flags);
  if (unlikely(signal_pending_state(state, current))) {
    /* skip */
  } else {
    if (list_empty(&wq_entry->entry)) {
      if (wq_entry->flags & WQ_FLAGS_EXCLUSIVE)
        __add_wait_queue_entry_tail(wq_head, wq_entry);
      else
        __add_wait_queue(wq_head, wq_entry);
    }
    set_current_state(state);
  }
  /* skip */
}

TASK_UNINTERRUPTIBLE 상태로 바뀔 때 호출하는 함수

스케줄러 클래스

sched_class 구조체

struct sched_class {
  const struct sched_class *next;

  void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
  void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
  void (*yield_task) (struct rq *rq);
  bool (*yeild_to_task) (struct rq *rq, struct task_struct *p, bool preempt);

  void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);

  struct task_struct * (*pick_next_task) (struct rq *rq,
                                       struct task_struct *prev,
                                       struct rq_flags *rf);
  void (*put_prev_task) (struct rq *rq, struct task_struct *p);
  int (*select_task_rq) (struct task_struct *p, int task_cpu, int sd_flag, int flags);
  void (*migrate_task_rq) (struct task_struct *p);
  void (*task_woken) (struct rq *this_rq, struct task_struct *task);
  void (*set_cpus_allowed)(struct task_struct *p,
                       const struct cpumask *newmask);
  /* skip */
}

5가지 스케줄러 클래스

extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

스케줄러 클래스의 우선 순위

프로세스를 스케줄러에 등록

세부 함수 호출

런큐

struct rq {
  raw_spinlock_t lock;

  unsigned int nr_running;
  /* skip */
  struct load_wait load;
  unsigned long nr_load_updates;
  u64 nr_switches;

  struct cfs_rq cfs;
  struct rt_rq rt;
  struct dl_rq dl;
  /* skip */
  unsigned long nr_uninterruptible;

  struct task_struct *curr, *dle, *stop;
  /* skip */
};

runqueues 변수

DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
#define this_rq() this_cpu_ptr(&runqueues)

CFS 스케줄러

CFS 스케줄러 알고리즘

CFS 관련 세부 함수

타임 슬라이스 관리

vruntime 관리와 관련된 세부 함수

선점 스케줄링

선점 스케줄링 진입점

선점 스케줄링의 진입점:커널 모드 중 인터럽트 발생