Linux Scheduling

EEEFFEE·2023년 11월 29일

Armv8 Architecture

목록 보기
8/15

23.11.28 최초 작성

1. 프로세스 상태

  • TASK_RUNNING(실행 대기) : ready 상태
  • TASK_RUNNING(실행) : running 상태
  • TASK_INTERRUPTIBLE : sleep 상태
  • TASK_UNINTERRUPTIBLE :
  • TASK_DEAD : terminate 상태
// /source/include/linux/sched.h

#define TASK_RUNNING			0x0000				//실행 대기 상태
#define TASK_INTERRUPTIBLE		0x0001				//sleep 상태
#define TASK_UNINTERRUPTIBLE		0x0002			//sleep 상태
#define __TASK_STOPPED			0x0004
#define __TASK_TRACED			0x0008
/* Used in tsk->exit_state: */
#define EXIT_DEAD			0x0010
#define EXIT_ZOMBIE			0x0020
#define EXIT_TRACE			(EXIT_ZOMBIE | EXIT_DEAD)
...

//https://elixir.bootlin.com/linux/v5.15.30/source/include/linux/sched.h

struct task_struct {
#ifdef CONFIG_THREAD_INFO_IN_TASK
	/*
	 * For reasons of header soup (see current_thread_info()), this
	 * must be the first element of task_struct.
	 */
	struct thread_info		thread_info;
#endif
	unsigned int			__state;			//프로세스 상태 저장
    ...
}
...

2. 상태 변경 API

  • /source/kernel/sched/core.c

    • wake_up_new_task() : TASK_RUNNING(실행 대기)상태로 변경

    • yield() : TASK_RUNNING(실행 대기)상태로 변경

    • __schedule() : current process()상태로 변경

      • current process : cpu를 점유하면서 실행되는 프로세스(런큐 구조체의 curr필드에 저장된 태스크 디스크럽터)
  • /source/include/linux/wait.h
    • wait_event_interruptible() : TASK_INTERRUPTIBLE 상태로 변화
  • /source/kernel/signal.c
    • __arm64_sys_pause() : TASK_INTERRUPTIBLE 상태로 변화
  • /source/kernel/signal.c
    • do_sigtimedwait() : TASK_INTERRUPTIBLE 상태로 변화

3. Preemptive scheduling

  • 특정 상황에 따라 프로세스의 스케줄링 순서를 변경할 수 있는 스케줄링 기법
  • Race condition의 주요 원인 중 하나
  • CONFIG_PREEMPTION

3.1 Preemption 체크

  • 인터럽트 핸들러를 처리하고 다시 원래 실행하던 프로세스로 돌아가기 전에 체크
  • 인터럽트 서비스 루틴 실행 마무리하고 인터럽트가 유발된 유저 공간으로 복귀하기 직전에 체크
  • 시스템 콜 핸들러 함수 실행을 마무리 한 후 유저 공간으로 복귀하기 직전에 체크

3.2 코드 실행 중 익셉션 유발 시 흐름

3.2.1 커널 코드 실행 중 커널 코드

  1. el1h_64_irq()을 통해 인터럽트 핸들러 실행

  2. 인터럽트 핸들러 완료하고 thread_info의 preempt_count값을 검사한 뒤

    2.1 0이면 3 으로 Preemptive Scheduling 진행
    2.2 0이 아니면 exit_el1_irq()호출 해 익셉션이 발생한 위치로 복귀

  3. arm64_preempt_schedule_irq() 실행

  4. preempt_schedule_irq() 실행

  5. schedule(SM_PREEMPT) 실행

  • preempt_schedule_irq() : __schedule()호출해 
//	/source/kernel/sched/core.c

asmlinkage __visible void __sched preempt_schedule_irq(void)
{
	enum ctx_state prev_state;

	/* Catch callers which need to be fixed */
	BUG_ON(preempt_count() || !irqs_disabled());

	prev_state = exception_enter();

	do {
		preempt_disable();
		local_irq_enable();
		__schedule(SM_PREEMPT);
		local_irq_disable();
		sched_preempt_enable_no_resched();
	} while (need_resched());

	exception_exit(prev_state);
}

3.2.2 유저 애플리케이션 실행 중 커널 코드

  1. el0t_64_irq()을 통해 인터럽트 핸들러 실행

  2. 인터럽트 핸들러 완료한 후 exit_to_user_mode()를 호출

  3. flags값을 _TIF_NEED_RESCHED와 & 연산을 한 뒤

    3.1 true면 4 로 Preemptive Scheduling 진행
    3.2 false면 __exit_to_user_mode()호출 해 유저모드 복귀

  4. prepare_exit_to_user_mode() 실행

  5. do_notify_resume() 실행

  6. schedule() 실행

3.2.3 유저 애플리케이션 실행 중 시스템 콜

  1. el0_sync(), el0_sync_handler()을 통해 인터럽트 핸들러 실행

  2. 인터럽트 핸들러 완료한 후 exit_to_user_mode()를 호출

  3. flags값을 _TIF_NEED_RESCHED와 & 연산을 한 뒤

    3.1 true면 4 로 Preemptive Scheduling 진행
    3.2 false면 __exit_to_user_mode()호출 해 유저모드 복귀

  4. do_notify_resume() 실행

  5. schedule() 실행

4. Non_Preemptive scheduling

  • 특정 상황에 따라 프로세스의 스케줄링 순서를 변경할 수 있는 스케줄링 기법
  • 프로세스가 schedule()함수를 호출해 자발적으로 스케줄링 요청

4.1 preemption 비활성화

  • preempt_disable(), preempt_enable() : thead_info의 preempt_count값을 조작해 (+1/-1) preemption을 비활성화/활성화 하는 함수

  • preempt_disable()필요한 경우

    • 특정 루틴에서 Preemption이 유발되고 오동작 할 때
    • 하드웨ㅓ어 디바이스에 정확한 딜레이 인가
    • 코드 구간의 실행 시간 정확히 지켜야 할 떄

  • preempt_disable()피해야 하는 경우

    • schedule()이전 preempt_disable()함수 호출(에러 발생)
    • 스핀락 이후 preempt_disable()함수 호출(spinlock에서 호출)

5. Context Switching

5.1 관련 자료구조

  • Armv8 : cpu_context(링크)

  • Armv7 : cpu_context_save(링크)

5.2 실행 흐름

  1. 프로세스의 우선순위를 vruntime기준으로 관리하는 레드 블랙 트리에서 vruntime이 가장 작은 프로세스를 next 프로세스로 설정
  2. 현재 실행 중인 프로세스(prev 프로세스)를 cpu에서 비우고 next 프로세스의 정보를 그 자리에 설정함
  • source/kernel/sched/core.c
    • __schedule() : context_switch()호출
    • context_switch() : switch_to() 호출
  • /source/include/asm-generic/switch_to.h
    • switch_to() : __switch_to() 호출
  • /source/arch/arm64/kernel/process.c
    • __switch_to() : cpu_switch_to() 호출
  • /source/arch/arm64/kernel/entry.S
    • cpu_switch_to() : 실제 cpu에서 prev 프로세스와 next 프로세스를 교체

6. Runqueue

  • 실행 대기 중인 프로세스(TASK_RUNNING)와 cpu에서 실행중인 current 프로세스를 관리하는 자료구조
  • 해당 자료구조의 프로세스를 vruntime에 따른 우선순위로 관리

6.1 커널에서 Runqueue

  • percpu타입의 변수 (runqueues 링크)
  • RT, CFS, Deadline 서브 Runqueue 관리
//	/source/kernel/sched/sched.h

struct rq {
	/* runqueue lock: */
	raw_spinlock_t		__lock;

	/*
	 * nr_running and cpu_load should be in the same cacheline because
	 * remote CPUs use both these fields when doing load calculation.
	 */
     
     ...
	unsigned int		nr_running;			//런큐에 존재하는 프로세스 갯수

	...
    
	u64			nr_switches;				//컨텍스트 스위칭 횟수

	...

	struct cfs_rq		cfs;				//CFS 런큐
	struct rt_rq		rt;					//rt 런큐
	struct dl_rq		dl;					//deadline 런큐

	...
    
	unsigned int		nr_uninterruptible;	//TASK_UNINTERRUPTABLE 프로세스 갯수
	
    ...
    
	struct task_struct __rcu	*curr;		//해당 런큐에서 현재 cpu에서 실행중인 프로세스
    
	...	
};

6.2 런큐 함수

  • /source/kernel/sched/sched.h
    • cpu_rq() : runqueues변수에서 cpu 오프셋을 적용한 주소에 접근
    • this_rq() : runqueues변수에서 cpu 오프셋을 적용해 주소를 얻어 옴

6.3 CFS (Completely Fair Scheduler)

  • Runqueue에서 실행 대기 상태인 프로세스를 공정하게 실행하도록 하는 스케줄러
  • 공정한 실행을 위해 타임 슬라이스 단위로 관리 함
    • 타임 슬라이스 : 스케줄러가 프로세스에게 부여한 실행 시간
    • 프로세스가 타임 슬라이스 모두 소진 시 컨텍스트 스위칭
    • 프로세스의 우선순위가 높을 수록 더 많은 타임 슬라이스를 부여
  • vruntime
    • 프로세스가 그동한 실행한 시간을 정규화한 시간 정보
    • CFS 스케줄러가 프로세스를 선택할 수 있는 기준 제공
    • CFS 스케줄러는 가장 작은 프로세스를 next 프로세스로 선정

6.3.1 ftrace message 분석

  • 관련 이벤트
    - `sched_switch` : 프로세스가 스케줄링
- `sched_wakeup` : 프로세스를 깨움
- `sched_stat_runtime` : 프로세스의 실행 시각, `vruntime`출력
    Non-Preemptive Scheduling 
vchiq-slot/0-74 [001] ..... 2375.466107: schedule+0x4/0x100 <-slot_handler_func+0xe9c/0x1730
// 프로세스가 schedule()을 통해 스케줄링 요청

vchiq-slot/0-74 [001] ..... 2375.466108: <stack trace>
=> schedule+0x8/0x100
=> slot_handler_func+0xe9c/0x1730
=> kthread+0xfc/0x110
=> ret_from_fork+0x10/0x20


vchiq-slot/0-74 [001] d..2. 2375.466111: sched_stat_runtime: comm=vchiq-slot/0 pid=74 runtime=13519 [ns]
vruntime=1265661013373 [ns]
// runtime : runtime=13519 ns
// vruntime=1265661013373 ns

vchiq-slot/0-74 [001] d..2. 2375.466112: sched_switch: prev_comm=vchiq-slot/0 prev_pid=74 prev_prio=101
prev_state=S ==> next_comm=kworker/1:1 next_pid=2525 next_prio=120

Preemptive Scheduling 

Xorg-594 [001] dNh.. 2375.426845: irq_handler_exit: irq=2 ret=handled
// 인터럽트 서비스 루틴 종료 후 커널 코드로 복귀 중 Preemption 발생

	Xorg-594 [001] dN... 2375.426846: preempt_schedule_irq+0x4/0xb8 <-el1_interrupt+0x50/0x70
	Xorg-594 [001] dN... 2375.426848: <stack trace>
=> preempt_schedule_irq+0x8/0xb8
=> el1_interrupt+0x50/0x70
=> el1h_64_irq_handler+0x18/0x28
=> el1h_64_irq+0x64/0x68
// el1h_64_irq()을 통해 인터럽트 핸들러 실행

=> kfree+0x0/0x148
=> do_writev+0x114/0x130
=> __arm64_sys_writev+0x28/0x38
=> invoke_syscall+0x4c/0x110
=> el0_svc_common.constprop.3+0x98/0x120
=> do_el0_svc+0x34/0xd0
=> el0_svc+0x30/0x88
=> el0t_64_sync_handler+0x98/0xc0
=> el0t_64_sync+0x18c/0x190
Xorg-594 [001] dN.2. 2375.426850: sched_stat_runtime: comm=Xorg pid=594 runtime=103611 [ns]
vruntime=20138844005 [ns]
Xorg-594 [001] d..2. 2375.426853: sched_switch: prev_comm=Xorg prev_pid=594 prev_prio=120 prev_state=R+
==> next_comm=v3d_render next_pid=300 next_prio=98
profile
EEEFFEE
네
이전 포스트

커널 타이머

다음 포스트

Armv8 Synchronization

0개의 댓글