CFS의 vruntime과 time slice

choboja의 이미지

안녕하세요? CFS 분석중인 학생입니다. 관련 자료가 많지 않아서 여러모로 힘드네요. ㅠㅠ

대략적으로 task에 할당된 vruntime과 time slice가 어떻게 계산되는지 알게 되었는데요,
time slice는 task의 weight와 cfs_rq의 비에 의해 구해지는데,

vruntime은 기준 weight(1024)를 task의 weight 비와 task의 실행시간으로 구해지는데,

time slice의 경우 직관적으로 이해되는것이 우선순위의 비에 따라 task의 실행시간이 증가되는걸로 이해가 되는데,

vruntime의 경우 task의 우선순위와 기준 weight에 의해 결정이 나는군요.

근데 궁금한건 꼭 vruntime을 사용해야되는것인지네요. 즉, time slice가 긴경우 vruntime은 짧아지는데, time slice를 tree의 key로
만들어도 되지 않을까요? ㅡㅡ;

왜 vruntime을 사용하게 되지 궁금합니다.

그리고 왜 CFS가 completely fair scheduler이죠?? fair하다는것이 vruntime을 기준으로 말하는것 같은데, 우선순위가 다른경우에도 비슷한 vruntime 을 가지는것으로
알고있습니다. 문서를 보면
80% of CFS's design can be summed up in a single sentence : CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.
ideal multi-tasking이라는것이 동일한 시간을 실행한다. 즉 2개의 task가 실행되면 cpu시간의 1/2씩 사용한다는 것같고, 이런걸 이루기 위해 vruntime을 도입한것 같는데 맞는지요?

또한 만약 vruntime이 작은 값이 스케쥴링되고 time slice가 완료되어 다시 cfs_rq에 enqueue될때 이전에 실행되지 않은 task보다 vruntime이 작아서 먼저 실행될수도 있나요?
이런일은 없을듯한데, ( task들을 모두 실행할 수 있는 time period를 계산하는 부분때문 ) 그런데 어떻게 그게 보장이 되는지 궁금하네요.

마지막으로

update_min_vruntime(cfs_rq)
{
       cfs_rq_min_vruntime = max_vruntime( cfs_rq->min_vruntime, vruntime);
}

왜 max값을 선택해서 cfs_rq_min_vruntime에 넣는지 알고싶습니다. 더 작은 값을 넣어주지 않고, 큰 값을 선택하는 이유가 궁금하네요.
혹 entity_key라는 부분이 se->vruntime - cfs_rq->min_vruntime 이 부분때문인지.. 새로운 task가 queue될때 tree의 오른쪽으로 보낼려고 하는것인지..
확신이 안서네요.

아직 새로운 task가 만들어질때의 vruntime값과 time_slice가 어떻게 계산되는지를 확인하지 못해서 부분, 부분이 명확하지 않습니다.

답변 부탁드리겠습니다.
감사합니다.

pastime의 이미지

CFS가 fair하다는 것은 말씀하신 것처럼 vruntime을 기준으로 합니다.
즉 (우선순위에 따라) 태스크가 실제로는 서로 다른 time slice 동안 실행되더라도
최소한 vruntime 상으로는 (거의) 동일한 시간 만큼 실행되었다고 인식하기 때문에
(우선순위에 상관없이) 모든 태스크를 공평하게 실행했다고 할 수 있는 것입니다.

그렇게 때문에 cfs_rq (tree)를 관리할 때 vruntime을 기준으로 해야
다음으로 실행할 태스크를 공평하게 선택할 수 있을 것입니다.

정상적인 (이상적인?) 경우라면 한 번의 period 동안 태스크가 한 번씩 실행되므로
cfs_rq 내의 모든 태스크의 vruntime은 한 단위 시간 정도의 차이 밖에 나지 않을 것이고
따라서 한 번 수행된 태스크의 vruntime은 다른 태스크의 vruntime 값 보다 항상 클 것 같습니다.

마지막으로 cfs_rq->min_vruntime을 업데이트하는 부분은
cfs_rq 내의 모든 태스크들의 vruntime 값이 커짐에 따라 cfs_rq 자체의 vrumtime 값도 증가시키기 위함입니다.
만약 max 대신 min을 쓴다면 절대로 증가하지 않겠지요..

choboja의 이미지

답변 감사합니다.

"모든 task의 vruntime은 한단위 밖에 차이가 나지 않을것"
음.. 중요한 것 같네요.
그렇다면 한번 실행된 task는 실행되지 않은 task보다 오른쪽에 위치할 것 같네요. (한번 테스트를 해봐야겠네요.)

한번 실행된 task들의 tree에서의 위치가 거의 바뀌지 않을 것 같네요.
왜냐하면 task의 vruntime이 갱신되는 경우가 sched_tick()이 발생하였을 때 업데이트되는데(context switch아닌 경우),
모든 타스크가 동일한 시간의 time_tick(4ms정도)이 발생하기 때문에 task의 load(task의 nice값에 의해 정해지므로) 가 변하지 않는 이상 위치가 변하지 않는걸로 생각됩니다.

"마지막으로 cfs_rq->min_vruntime을 업데이트하는 부분은
cfs_rq 내의 모든 태스크들의 vruntime 값이 커짐에 따라 cfs_rq 자체의 vrumtime 값도 증가시키기 위함입니다.
만약 max 대신 min을 쓴다면 절대로 증가하지 않겠지요."

그렇네요. 코드중 leftmost task의 vruntime과 현재 vruntime을 비교하고 작은 녀석과 cfs_rq->vruntime을 비교해서 큰 녀석을 setting해주네요.
이 부분을 놓치고 있었네요.

답변 감사드립니다.^^

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.