kernel scheduler분석중에 의문이 생겨서요....

munhoney의 이미지

요즘 kldp 도움을 자주 받고 있네요 ^^' (감솨~~ 합네다)

스케쥴러 분석 중 의문이 몇개 생겨서 자문을 구합니다.

1. kernel/schedule.c 의 schedule 함수가 어떻게 불리나요?
책에서는 direct invocation / lazy invocation 어쩌구 저쩌구 하는데, 일단 do_exit하고 나서 scheduler가 불리는 것은 OK.
그렇다면 scheduler를 주기적으로 수행하는 다른 것은 없나요? (주기적으로 수행해야 정확한 schedule이 될 것같은데.)
제 생각에는 schduler는 주기적으로 모니터링하면서 검사를 해야할 것 같은데요..
kswap 데몬이 있던데 혹시 이것이 주기적으로 schduler를 불러주는 것인가요? 하지만, kswap은 priority가 낮아서 cpu idle
상태에서만 호출이 되는 걸로 알고 있습니다. 그러면 scheduler가 제때에 불릴 수가 없을 것 같은데요?

2. 분석하다보니 likely(...) 와 unlikely(...) 가 사용이 되던데요.. 이 모두 compiler에게 hint를 알려주는 거라고 나와있습니다.
hint라는 게 구체적으로 어떤 일을 하는거지요?
대략 unlikely 같은 경우는 잘 사용되지 않으니 compiler가 알아서 잘 컴파일 하라라는 것 같은데 어떻게 잘 알아서
컴파일을 하라는 건지...

부탁드립니다용..

camera7의 이미지

1. kernel/sched.c 의 schedule() 함수는
- 타이머 인터럽트가 뜰 때 현재 task timeslice의 만료여부를 체크하여 NEED_RESCHED 필드 설정
- 모든 interrupt handler 수행 후 복귀 시 NEED_RESCHED 필드 체크하여 schedule() 호출
- 커널 코드내에서 명시적으로 schedule() 호출
e.g. pthread_mutex_lock 호출 시 커널 단에서 현재 task를 wait queue에 넣고 schedule() 호출
- 시간이 오래 소요되는 system call의 경우 명시적으로 schedule() 호출

주로 첫번째 (타이머 인터럽트)의 경우가 많을 것으로 생각되네요.

2. 뭐, 굳이 예를 들자면

if(likely (x == 0))
A
else
B

이런 코드라면 pipeline을 훼손 시키지 않기 위해
컴파일러가 assem으로 변환시에 branch 문 바로 밑에 A 라는 코드를 둔다거나 뭐 이런식이 아닐지~

munhoney의 이미지

네 감사합니다. ^^

명확한 답변에 많은 부분이 이해가 되었네요..

하지만, 좀더 알고 싶은 부분은..

1.
결국 timer interrupt에 의해서 주기적으로 불리게 되겠네요. 어짜피 timer interrupt는 time slice에 맞게 띌것이니깐요.
그런데 timer interrupt 코드를 볼려면 어디서 보아야 하지요? 코드 위치가...

2.
pipeline 을 깨지 않기 위해 branch 문 바로 옆에 둔다는것은 조금 이해가 안되네요. 보다 구체적인 설명을 더 들을 수 있을까요? :-)

P.S.
우분투에서 파이어폭스를 사용하고 있는데 답변에 +를 하고 싶은데 안되는군요.. 역시 XP에 적합하게 되었는가봐요..
혹, 가능한 방법이 있나요?

---------------------------------
http://blog.naver.com/munhoney
---------------------------------

bushi의 이미지

http://lxr.linux.no/linux+v2.6.30.5/+ident=16056915
. 앞으로 가면 schedule_tick(), 뒤로 가면 timer_tick()
. task_tick() 들을 보시려면 kernel/ 의 sched_fair.c, sched_rt.c, sched_idletask.c 들을 보시면 됩니다.

http://kerneltrap.org/node/4705
. 수동 branch prediction.

OTL

munhoney의 이미지

..

---------------------------------
http://blog.naver.com/munhoney
---------------------------------

camera7의 이미지

참고로 우선순위를 기준으로 고정된 timeslice를 갖는 것은 O(1) 스케쥴러에 대한 내용입니다. ~2.6.22

CFS 같은 경우는 대략 아래 공식으로 timeslice가 변하게 되지요.. (뭐 혹자는 timeslice가 없는 스케쥴러라는 이야기를 ...ㅡㅡ)

       sched_slice = __sched_period X (현 task의 weight / 전체 task의 weight)

그리고 O(1)처럼 각 task마다 timeslice 필드를 갖는게 아니라
scheduler_tick 함수내에서 sched_slice를 계산해서 스케쥴링 여부를 판단하게 됩니다.

powerson의 이미지

1. do_IRQs 함수를 보시면 각 handler들에 대해서 함수콜을 하게 되어 있는데, 이건 interrupt vector table에 등록되어 있는 handler들을 호출하게 됩니다. 지금 코드를 확인해볼 시간이 없어서 이 정도밖에 답변을 못 드리겠네요^^

2. if 등은 branch instrution들을 사용하며, pipelining이 깨질수도 있다는 것은 아실겁니다. 코드를 짜시면서, if의 condition에 대해서 대부분은 참이다? 혹은 대부분은 거짓이다? 등을 판단하실 수 있을때 compiler에게 이것은 대부분 참이다라는 것을 알려줘서 pipelining이 깨지지 않도록 보호해준다고 생각하시면 될 거 같습니다.
실제로 코드를 짜서 확인해보시면 가장 좋은데, likely or unlikely는 __builtin_expect define 되어 있으니, 이 부분을 가지고 compile 하신 후 objdump로 assembly를 직접 확인해보시면 될 거 같네요.

------------------------------------------------------
아직은 젊다. 모든 것을 할 수 있는 나이란 말이지.

------------------------------------------------------
아직은 젊다. 모든 것을 할 수 있는 나이란 말이지.

tj의 이미지

likely/unlikely는 두가지 효과가 있는데요.

1. (최초) branch prediction이 맞을 가능성 높히기. 프로세서 구현마다 다른데 어떤 프로세서에선 직접 힌팅이 들어가기도 하고 어떤 애들은 종류나 조건의 형태에 따라 하기도 합니다. 요즘엔 이전 브랜칭 결과들에 따라서 프로세서가 알아서 잘 해서 정말 hot path들에 대해선 그렇게 영향이 크지 않을 수도 있습니다.

2. 더 중요한 부분은 cache locality인데 likely/unlikely로 구분해주면 hot path들을 붙여서 배치하고 cold path들은 뒤쪽에 모읍니다. 이렇게 하면 실제 실행되는 코드의 cache footprint가 작아지고 전체적으로 하위 캐시나 메모리로의 엑세스를 줄일 수 있기 때문에 성능 향상에 도움이 됩니다.

코드나 프로세서따라 다르지만 메모리 엑세스가 캐시에 비해 워낙 느리니까 cache footprint 줄이는 게 도움이 많이 된다고 알고는 있는데 실제로 측정해본 적은 별로 없네요. -_-;;

tj의 이미지

참고로 이런 부분에 관심이 있으면 intel optimization reference manual 읽어보면 도움이 많이 됩니다. SIMD 부분 제외하면 양도 그렇게 많지 않구요. http://www.intel.com/Assets/PDF/manual/248966.pdf

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.