Korea Tech Conference 2005 년 5 월 14 일, 서울 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 1
리눅스에서의실시간지원 정영준 / 임용관 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 2
1. 개요 2. 스케줄러 목차 I. 고정스케줄링시간지원 3. 커널구조 I. 선점형커널지원 II. 자발적선점패치 III. 스핀락패치 IV. 인터럽트패치 4. 성능분석 5. 결론 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 3
개요 Throughput vs Realtime 실시간관련커널패치 interrupt interrupt preemptible preemptible kernel kernel thread thread O(1) O(1) Scheduler Scheduler patch patch 2.6 vanilla kernel 2.6.4 2.4 vanilla kernel lockbreak, lockbreak, preemptible preemptible kernel, kernel, O(1) O(1) Scheduler Scheduler patches patches 2.6.7 2.6.9 voluntary voluntary spinlock spinlock preemption preemption patch patch patch patch 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 4
2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 5
스케줄러 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 6
2.4 커널의스케줄러 Throughput 기반의단일 runqueue 지원 실시간태스크지원미흡 실시간태스크와일반태스크가 runqueue에혼재 Non-deterministic mechanism 태스크들의수에따라서고정된시간내에스케줄링이일어날수없음 실시간성능이요구되는시스템에는적합하지않음 실시간태스크들에한해서는제한된시간내의스케줄링지연시간지원이요구됨 O(1) 스케줄링 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 7
2.6 커널의스케줄러 우선순위기반두개의 runqueue 실시간성지원 runqueue에우선순위별로태스크들이연결됨 비트맵에서처음으로 1인비트를찾는연산만으로다음에실행될태스크를선택할수있음 - bsfl deterministic mechanism 태스크들의수가아무리많다하여도고정된시간내에스케줄링이일어남 실시간성능이요구되는시스템에적합 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 8
커널구조 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 9
선점형커널지원 커널모드선점비교 ( 차이점 ) < 비선점형커널 > < 선점형커널 > 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 10
선점형커널지원 개요 커널 2.4.x 에서부터오픈커뮤니티에서시작 커널 2.5.4 에서공식채택 커널 2.6.x 에서컴파일시에옵션으로제공 Concurrency & Reentrancy 지원 SMP locking mechanism 수정지원 이유와고려사항 선점형커널을위한새로운락메커니즘지원필요 선점형커널의 concurrency 와 reentrancy 문제는 SMP 에서의그것과같음 기존락메커니즘 Semantic 을유지하면서 SMP locking mechanism 을수정 장점 최소한의커널수정으로 preemptible kernel 구현 결과 Preemptible kernel 지원 시스템 responsibility 증가, 시스템 throughput 감소 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 11
선점형커널구현 새로운 Preemption lock 필요 선점형커널 : Kernel 은 preemption locked region 을제외하고 preemptible 하다 효과적인락메커니즘수정 SMP spinlock /*preemption enable region */ preempt_lock(); new_spin_lock(); original_spin_lock(); /* preemption locked region */ original_spin_unlock(); preempt_unlock(); new_spin_unlock(); /*preemption enable region */ 락메커니즘의 Semantic은유지 락메커니즘자체만을수정하여대부분의커널코드가선점가능함 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 12
선점형커널구현 Preemption lock 의추가적인사용 SMP-safe vs. Preempt-safe SMP Spinlock 이커버되지않는부분은 Preemption lock을사용해야함 Preempt-safe 로보호해야하는곳 Per-CPU data structures CPU state : this is very architecture dependent 예제코드 cpucache_t *cc; /* this is per-cpu */ preempt_disable(); cc = cc_data(searchp); if (cc && cc->avail) { free_block(searchp, cc_entry(cc), cc->avail); cc->avail = 0; } preempt_enable(); return 0; 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 13
관련자료구조 <Agenda> 상세구현들여다보기 TIF_NEED_RESCHED, preempt_count Preemption lock #define preempt_disable() do { inc_preempt_count(); barrier(); } while (0) #define preempt_enable() do { barrier(); dec_preempt_count(); preempt_check_resched(); } while (0) Spinlock #define spin_lock(lock) do { preempt_disable(); _raw_spin_lock(lock); } while(0) #define spin_trylock(lock) ({preempt_disable(); _raw_spin_trylock(lock)? 1 : ({preempt_enable(); 0;});}) #define spin_unlock(lock) do { _raw_spin_unlock(lock); preempt_enable(); } while (0) Interrupt #define spin_lock_irq() do { local_irq_disable(); preempt_disable(); _raw_spin_lock_flags(); } while (0) #define spin_unlock_irq() do { _raw_spin_unlock(); local_irq_enable(); preempt_enable(); } while (0) #define spin_lock_bh() do { local_bh_disable(); preempt_disable(); _raw_spin_lock(); } while (0) #define spin_unlock_bh() do { _raw_spin_unlock(); preempt_enable(); _local_bh_enable(); } while (0) 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 14
어떻게적용되어돌아갈까? 인터럽트에서복귀시에조건을만족하면 preempt_schedule 을호출하여재스케줄링 lower priority task Run ISR wakeup other task Interrupt occur Set need_resched to 1 if it is needed jmp ret_from_intr higher priority task same as vanilla linux If user mode running jmp ret_from_sys_call 1. check user mode doesn t meet the condition schedule, context switch exit 1. check preempt_count 2. check need_resched irq and bh nested If preempt_count = 0, need_resched = 1 preempt_schedule check irq or bh nesting irq and bh not nested 2005년 5월 14일 CE Linux Forum Korea Tech Conference 15
자발적선점패치 개요 높은스케줄링레이턴시 reported by JACKit (up to 50ms!) 소스코드에새로운스케줄링포인트를추가 might_sleep() lock 을갖지않았으므로 sleep 될수있음을나타내는코드 noop 이나디버깅옵션을넣으면 lock 을가지고휴면하게되는경우인지를체크할수있음 1ms 이상의레이턴시를가지는구간을탐색및테스트 선점포인트를삽입 선점타이밍을앞당김으로우선순위가높은태스크가실행될수있는시간을앞당김 정규커널트리에는미포함 실시간패치에통합되어배포 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 16
새로운스케줄링포인트 # define might_sleep() do { voluntary_resched(); } while (0) int sched voluntary_resched(void) { #ifdef CONFIG_DEBUG_SPINLOCK_SLEEP might_sleep( FILE, LINE ); #endif if (!voluntary_preemption) return 0; if (need_resched() && system_state >= SYSTEM_BOOTING_SCHEDULER_OK) { set_current_state(task_running); schedule(); return 1; } return 0; } 1tick =1jiffie =1ms TA TB TA with need_resched=1 might_sleep() TB 가미리실행가능함 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 17
스핀락패치 선점의관점에서본스핀락 스핀락구간은 preemption disable 구간임 lock을사용하지도않는태스크가실행될기회를빼앗기게됨 어떤 lock이잡혀있다면그 lock을사용할태스크만실행되지못하게만드는것이필요 새로운 lock 매커니즘 90여개의 spin_lock은오리지널코드를유지 나머지코드는 mutex_lock으로대체 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 18
TA spin_lock(x) 선점불가능구간 : 모든다른태스크가실행될기회를빼앗기게됨 스핀락패치 spin_lock(x) <Agenda> TA 선점가능! 하지만, 이구간을실행할태스크가선점을하여실행된다면 spin_lock(x) 에서 TA 가 lock 을놓을때까지기다리게됨 locked region x spin_unlock(x) TB 와 TC 는실행될기회를전혀갖지못하게됨, locked region 을사용하지도않을텐데.. locked region for the tasks which uses this area spin_unlock(x) TB 가선점! TB TB 는 x region 을수행하지않으므로계속실행가능! TB TC TC 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 19
스핀락패치 TA spin_lock(x) Tc 는 TA 가 hold 하고있는 x region 을 access 하려했으므로 spin_lock(x) 구문에서 block 됨 TC TC 가선점! locked region for the tasks which uses this area spin_unlock(x) 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 20
개요 인터럽트패치 2.6.4용인터럽트쓰래드패치첫등장 타이머인터럽트를제외한모든인터럽트를쓰레드화 serialize 된인터럽트처리를우선순위화 각인터럽트쓰레드에게실시간우선순위와 SCHED_FIFO 스케줄링 policy를할당 스케줄링을통한예측가능성 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 21
인터럽트패치 <Agenda> Task 인터럽트가발생하면즉시그 ISR 를처리한다! 스케줄러는관여할수없다. Task intr find ISR intr wakeup interrupt thread ISR 의처리시점이 scheduler 에의해서결정된다. ISR ret scheduler ISRT Task < 기존의인터럽트처리과정 > < 인터럽트쓰레드화 > 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 22
성능분석 인터럽트관련시스템성능 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 23
인터럽트지연시간측정 성능분석 < 2.6.9-vanilla > < 2.6.9-인터럽트패치 > interrupt disable time cli~sti 인터럽트지연시간을가늠 intlatency-2.6.patch적용 perfview 로값을저장함 < 2.6.9- 인터럽트패치 + 자발적선점패치 > 2005년 5월 14일 CE Linux Forum Korea Tech Conference 24
선점지연시간측정 성능분석 < 2.6.9-vanilla > < 2.6.9- 인터럽트패치 > < 2.6.9- 인터럽트패치 + 자발적선점패치 > 2005년 5월 14일 CE Linux Forum Korea Tech Conference 25
결론 다각적인방법을통한리눅스에서의실시간성지원노력 이시간에도다양한패치들개발됨 오픈커뮤니티에서의노력 100us 정도의선점지연시간을보장하는리눅스커널 리눅스의장점을살리면서도실시간성능이크게향상된커널사용가능 Throughput과의 tradeoff 불안정한측면 -> 꾸준한안정화 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 26
Reference http://www.celinuxforum.org Understanding the Linux Kernel Linux Kernel Development Building Embedded Linux Systems Linux Kernel Internals http://redhat.com/~mingo/realtimepreempt/ 2005 년 5 월 14 일 CE Linux Forum Korea Tech Conference 27