 by barrios 카테고리
이전블로그
최근 등록된 덧글
저도 링크 얻어갑니다~
by mooni at 06/26 안녕하십니까 까마굽니다.. by 까마구 at 06/24 ㅋㅋㅋ 정환 아우라우~~ .. by Junghwan at 01/29 웹서비스까지는 아니지만.. by barrios at 01/25 메모장
 |
http://lwn.net/Articles/295854/ Arjan van de Van이 새로운 timeout method를 제안했다. schedule_hrtimeout이다. API가 나타내는 그대로 timeout을 위해 hrt를 사용하는 것이다. 이러한 기술이 나온 이유는 기존의 timeout관련 system call들이(select, pselect, poll, ppoll, epoll_wait)등이 내부적으로는 jiffies를 사용하여 nanosecond의 인수를 받는다고 할지라도 내부적으로 1~10 msec까지의 latency를 가질수 밖에 없었기 때문이다. 하지만 HRT를 사용하여 timeout을 처리하다보면 동시에 일어날 수 있는 timeout event가 줄어들 것이며 결국 잦은 wakeup과 많은 power consumption을 유발하게 될 것이다. 이 문제를 해결하기 위해 1초 이하의 timeout은 HRT를 사용하며 그 이상의 값은 이전과 같이 jiffies를 사용하는 것이다. 하지만 Linus는 그러한 solution을 좋아하지 않았다. 대신에 그는 모든 timeout 값에 대해서 적절한 resolution을 제공하기를 원했다. 예를 들어 timeout 값이 작으면 latency또한 작아지고 크면 latency 값또한 커질 수 있는 그러한 형태 말이다. 그래서 Arjan은 새로운 제안을 하였다. hrtimer를 soft와 hard의 두가지 timeout값을 가지게 하고 커널은 최대한 soft 값에 맞추어서 timeout event를 발생시킬 수 있도록 노력하되 최대 hart 값을 넘어가지 않게 하는 범위내에서 자유롭게 할 수 있는 것이다. 이 feature는 좋긴 하지만 몇몇 주요 API들을 변경해야 하는 문제가 있다. 또한 가장 중요한 문제는 그 range를 과연 어떻게 정할 것이냐 이다. Arjan은 두가지를 가지고 그 값을 조절한다. 먼저 task struct에 timer_slcak_ns라는 새로운 필드를 넣어 nanosecond단위로 timer accuracy를 명시하게 하였다 이 값은 prctl system call에 의해 조절될 수 있으며 default value는 50umsec이다. 그러므로 현재 커널 보다는 훨씬 정확하다. 둘째로, 명시된 timeout값에 따라 accuracy value를 제공하는 heuristic한 함수를 제공하였다. 긴 timeout 예를 들어 10sec보다 큰 경우에는 accuracy는 100ms이다. timeout값이 짧으면 짧을수록 10ns까지 accrucy error값은 작아진다. poll관련 함수들은 이 heuristic이 return한 값을 사용하게 될 것이며 timer_slack_ns값을 초과할 수는 없다. 페이지 회수를 시작하여 high order의 페이지를 할당하려 할때 racing allocator들로 인하여 low order들의 페이지들이 high order의 페이지로 coalescing 되기전에 다시 fragmentation되는 현상을 막기위한 패치이다. 이 패치는 allocation들이 자주 racing되는 경우 효과를 발휘할 것으로 보인다. 하지만 이 패치는 OOM등에 문제를 발생시킬 소지가 있을 것으로 보인다. CFS(Complete Fair Scheduling)은 linux 2.6.23에 들어간 이미 오래된 기능이다. 리눅스 커널 2.6의 가장 큰 변화 중 하나가 O(1) Scheduler라고 그렇게 외쳐됐던 것이 엇그제 일인데 벌써 다른 스케줄러로 교체되어 버렸다. 요즘 너무 메모리쪽으로만 집중을 하다보니 스케줄러 쪽으로 많이 소원해진 것이 사실이다. 아무리 그래도 기본적인 Design Concept정도는 알고 있어야 할 듯 해서 이 페이지를 정리해 본다. 이글은 아래의 페이지를 내 마음대로 해석하여 정리한 글임을 밝혀둔다. http://gustavus.edu/+max/os-book/updates/CFS.html 2008/08/15 11:40:46 - barrios - 크게 봐서는 CFS는 이전의 스케줄러와 같은 원리로 동작한다. CFS도 이전의 스케줄러와 마찬가지로 niceness가 각 쓰레드가 할당받는 CPU time을 제어하기 위한 주요 수단이다. O(1) 스케줄러는 동적으로 priority를 조절하여 waking thread가 조만간 얼마나 빨리 수행될지를 조절하였지 runnable한 쓰레드들 사이에서의 CPU sharing을 조절하진 않았다. CFS에서는 runtime을 측정하는 방법과 waking thread가 빨리 수행될 수 있기를 보장하기 위한 방법이 새롭게 사용되었다. CFS로 들어가기에 앞서 이전 O(1) 스케줄러의 문제점을 몇가지 살펴보자.
CFS는 각 niceness level을 timeslice로 할당하기 보다는 weight로 할당하고 runnable한 쓰레드들의total weight에 기반하여 timeslice를 계산한다. 그로므로 각 쓰레드들은 total weight에 기반하여비례적으로 timslice를 받게 된다. CFS는 runabble한 쓰레드들이 한 바퀴 round-robin을 하는 시간을정하여 그 시간을 기준으로 CPU를 분배한다. 그 target time이 100ms라고 가정하면, 두개의 같은priority의 쓰레드들은 같은 weight을 가지게 됨으로 각 쓰레드는 50ms를 얻게 된다. 이는 두 쓰레드가 nice값0을 갖던, 19를 갖던 상관없이 50ms씩을 얻게 된다. 만일 4개의 쓰레드가 같은 nice값을 갖는다면 25ms씩 갖게된다. 스위칭 rate는 이전의 스케줄러와는 달리 nice 값의 level과는 무관하게 된 것이다. 재미있는 것은 스위칭 rate가 전체 시스템 부하와 관련있어 졌다는 것이다. 즉 시스템에 부하가 많아지면 응답성을 보장하기 위해서throughput을 약간 희생하게 될 것이다. 응답성의 level은 target time에 따라 조절되어 진다. 이 값은시스템 어드민에 의해 조절될 수 있다. 100ms의 값은 서버와 같이 throughput이 주요하고 응답성은 단지graphical한 interaction이 아니라 web page reload의 scalability를 중요시 여기는 시스템에서적절하다. CFS의 default target time은 20ms이다. 이것은 응답성이 중요한 desktopmachine에 적절하다. 하지만 시스템 부하가 정말 높아지게 되면 CFS는 응답성을 위하여 throughput을계속해서 희생하지 않는다. 왜냐하면 각 쓰레드가 얼마나 적은 timeslice를 받게 되느냐에 하한선이 있기 때문이다. 그지점에 도달하게 되었을 경우 새로운 쓰레드가 시스템에 들어가게 되면 per-thread time을 감소시키기보다는 쓰레드들을순환하기 위한 전체 시간을 증가시킬 것이다. niceness0과 niceness5을 가지는 두개의쓰레드가 CPU를 공유하는 경우를 가정해보자. CFS는 이 쓰레듣르에게 1024와 335의 weight을 주게 된다. 그러므로쓰레드가 얻는 시간은 1024/(1024+355), 335/(1024+335)가 된다. 1024는 대략 335의 3배이기 때문에niceness0을 가진 쓰레드는 대략 100ms중에 75ms, niceness5를 가진 쓰레드는 100ms중에 15ms를 갖게될 것을 예측할 수 있다. niceness 5, 10 또는 niceness 0, 5를 갖던 상관 없이 같은 결과를 얻게 될것이다. 왜냐하면 어떻게 하여도 weight의 비율이 3:1이 될 것이기 때문이다. 즉, CPU proportion은niceness의 상대적 차이로 얻게 되는 것이지 이전과 같이 절대 차이로 인하여 얻게 되는 것이 아니다. CFS의 big idea는 각 쓰레드들이 얼마나 많은 시간동안 실행을 했는지를 쓰레드의 weight으로 scale하여 유지하는것이다. 즉, niceness0 쓰레드는 수행시간을 1ns단위로 scale한다. 반면, niceness5 를 가진 쓰레드는실행시간을 대략 3ns단위로 scale하게 된다. 이렇게 weigh을 이용하여 scale하는 이유는 어떤 쓰레드가가장 뒤쳐져 있는지를 판별하기 위해서이다. 가장 뒤쳐져 있다는 것은 자신에게 주어진 timeslice를 가장 채우지 못한쓰레드라는 것이다. CFS가 timeslice를 채우지 못한 쓰레드들에게 계속해서 제어권을 넘겨 균형을 유지하려고 한다면끊임없이 가장 뒤쳐져 있는 쓰레드들로 스위칭을 해야하며 이는 매우 비효율적일 것이다. 얘기가 어려워진다. 쉽게 예를 들어설명하여 보자. 두 쓰레드가 같은 niceness를 가지고 있다면 스케줄러는 두 쓰레드가 항상같은 timeslice을 수행하고 있음을 보장하려고 애쓸 것이다. 즉, X ns 후에 살펴보니 정확하게 두 쓰레드가 X/2ns씩 수행을 해야 할 것이다. 이것을 만족시키기 위해서는 스케줄러는 끊임없이 쓰레드들 사이를 스위칭 해야 할 것이며 그것은너무 비효율적일 것이다. 그래서 스케줄러는 그렇게 자주 스위칭을 하는 것보다는 한 쓰레드를 그 쓰레드의 timeslice동안지켜보게 된다.(스케줄러는 쓰레드들을 20ms 주기로 스위칭을 한다고 가정하자) 그 결과, 60msec 후에 두 쓰레드가30ms씩 수행된 것이 아니라 40ms, 20ms 씩 수행된 것을 볼수도 있게 될 것이다. 하지만 스케줄러가 다음 실행할쓰레드를 결정할 때 20ms를 수행한 쓰레드 B를 선택하여 쓰레드 A를 빨리 따라잡게 만들 것이다. 이런 방법으로 쓰레드들이서로 제어권을 주고 받으며 수행하게 되면 어느 시점에서도 두 쓰레드들 사이의 차이가 그렇게 크게 되지 않게 만들 것이다.(이예제에서는 20ms 이내가 될 것이다.) 두 쓰레드가 다른 niceness를 가지고 있을 경우를고려해보자. 예를 들어 쓰레드 A는 niceness0을 가지고 있고 쓰레드 B는 niceness5를 가지고 있다고 가정하자.쉽게하기 위해 1024/335는 3이라고 하자. 즉 쓰레드 A는 쓰레드 B보다 3배 더 크다. 60ms이후에 이상적인 경우쓰레드 A는 45ms, 쓰레드 B는 15ms가 되야 한다. 하지만 스케줄러가 20ms마다 쓰레드들을 스위칭한다면 그 이상적인상황은 발생하지 않을 것이다. 쓰레드 A는 40ms, 쓰레드 B는 20ms가 수행된 것을 알 수 있다. 이 시점에서 다음 어떤쓰레드를 스케줄해야 할까? B는 이미 자신의 할당받은 timeslice(15ms)를 넘어선 것을 알 수 있다.스케줄러가 이러한 상황을 판단하기 위해서는 각 쓰레드의 time을 scale fator를 가지고 곱하는 것이다. 예를 들어쓰레드 A는 scale factor가 1이다. 반면 쓰레드 B는 3이다. 그러므로 실제 run time이 40ms, 20ms인경우, virtual run time은 40ms, 60ms가 되는 것이다. 이제 명확해졌다. 쓰레드 A는 더 뒤쳐져 있다.그러므로 스케줄러는 쓰레드 A를 실행해야 할 것을 알게 된다. 위의 설명은 모든 쓰레드들이system이 처음 bootup됐을 때부터 시작되었고 계속해서 runnable하게 존재한다면 잘 동작할 것이다. 하지만 실제시스템은 그렇지않기 때문에 새로 만들어지는 쓰레드들과 잠에서 깨어나느 쓰레드들에 대한 고려가 반드시 필요하다. 이런 고려가 되지않을 경우, 새로 만들어지는 쓰레드나 잠들었다 깨어난 쓰레드들은 이미 존재하고 있던 쓰레드들을 따라잡을 때가지 수행되게 될것이다. 이는 바람직하지 못하다. 그러므로 하나의 쓰레드가 runqueue에 들어가게 될 경우 그 쓰레드의 virtualruntime은 존재하는 runnable한 쓰레드들의 가장 작은 virtual runtime으로 지정되고 약간 조절되게 된다.(새롭게 만들어지는 쓰레드 or 깨어나는 쓰레드냐에 따라). 이러한 방법으로 우선적으로 실행될 수 있는 구너한을 부여받고비정상적으로 오랫동안 수행되지 않을 것이다. run queueu는 runnable thread들의virtual runtime으로 정렬한 red-black tree로 유지된다. CFS가 쓰레듣르을 스위칭하려고 할 때 가장왼쪽에 놓여 있는 쓰레드들 선택하게 된다. 즉 가장 작은 virtual runtime을 가진 쓰레드이다. 스케줄러는 2가지 상황에서 이러한 쓰레드들을 스위칭 한다. 첫째는 timeslice를 다 소진했을 경우이다. 다른 상황은 현재쓰레드가 수행된지 어느 정도 시간이 됐는데(이 값은 configurable하다.) 새로운 쓰레드가 runqueue에 들어오게되는 경우이다. runnable 한 쓰레드들을 virtual runtime의 timeline에위치시키는 장점중 하나는 waking thread들이 다른 쓰레드들을 굶주리게 하는 경우를 막을 수 있다는 것이다.(이미 언급한바와 같이 이전 O(1) 스케줄러의 큰 문제점이기도 했다.) 시간이 가면서 깨어나는 쓰레드들은 virtual runtime의 timeline에 점점 더 뒤쪽으로 위치하게 된다. 즉, 현재 time을 기준으로 상대적으로 더 뒤쪽으로 위치하게 된다. 반면인내심을 가지고 CPU를 기다려온 쓰레드들은 고정된 virtual runtime을 갖게 된다. 즉, 이들은 이미 오래전 fix한 virtual runtime을 가지고 있다. 그러므로 마침내 가장 작은 virtual runtime을 갖게 될 것이며 실행되게될 것이다. sleeping과 wakeup을 가진 어떤 음모도 이제 통하지 않게 된다. 가장 이상적인 CFS slice는 다음과 같이 계산된다. slice = (se->load.weight / cfs_rq->load.weight) * period period는 스케줄러가 모든 task들을 수행하는데 걸리는 시간이다. default로 20ms로 되어 있으나 이 값은 고정은 아니다. 시스템에 runnable한 task들의 수가 sched_nr_latency보다 커질 수록 이 값은 증가하게 된다. 그렇지 않게 되면 각 task들에게 분배되는 slice가 너무 작아 context switching 오버헤드가 너무 커져 시스템이 비효율적일 수 있기 때문이다. se는 sched_entity를 의미하는 것이다. 따로 설명은 안했지만 CFS에서의 sched_entity는 단지 task만 될 수 있는 것이 아니라, user, container등 보다 다양한 hierachy를 제공한다. 여기서는 se가 task로 봐도 무방하다. 즉, slice는 한 period 중 태스크의 weight이 cfs_rq의 전체 weight중에 차지하는 비율이다. 또한 실행중 특정 task의 vruntime은 다음과 같이 계산된다. vruntime += (NICE_0_LOAD / se->load.weight) * delta_exec 여기서 delta_exec는 그 cpu를 할당받아 수행된 시간이다. NICE_0_LOAD는 상수값 1024이다. 즉 vruntime은 위에서 이미 설명한 것과 같이 task의 weight으로 수행시간을 scale한 결과이다. 위의 식 이전의 식과 결합하면 다음과 같이 될 수 있다. vruntime += (period/cfs_rq->load.weight) * NICE_0_LOAD 위의 식이 증명하는 것과 같이 period와 cfs_rq->load.weight은 모든 task들에게서 같은 값을 가지기 때문에 모든 task들의 vruntime은 같은 값 갖게 된는 것이다. 아주 이상적인 경우에 말이다. 그러므로 vruntime 값이 적다는 것은 그 task가 자신의 slice를 충분히 사용하지 못했다는 것이고 그 task가 rbtree의 leftmost에 있게 되며 가장 긴급히 수행시켜줘야 할 task가 되는 것이다. Process Scheduling and Time
UNIX scheduling round robin with multilevel feedback user priority kernel priority 부록 : 시그널 핸들링 Kernel 이 하는 역할 1. The kernel access the user saved register context. PC, SP 2. clear the signal handler fiedl in the u area, setting it to the default state 3. The kernel creates a new stack frame on the user stack, writing in the values of the program counter and stack pointer it had retrieved from the user saved register context and allocating new space, if necessar. The user stack looks as if the process had called a user-level function(the signal catcher) at the point where it had maded the system call or where the kernel had interrupted it(before recognitio of the signal) 4. The kernel changed the user saved register context: It resets the value for the program counter to the address of the signal catcher function and sets the value for the stack pointer to account for the growth of the user stack After returning from the kernel to user mode, the process will thus execute the signal handling function; when it returns from the signal handling function, it returns to the place in the user code where the system call or interrupt originally occurred, mimicking a return from system call or interrupt. 블로그는 정말 오랜만이군요. 이제는 별볼일 없는 페이지가 된지라.. 혹시라도 방문하시는 분들에게 커널에 관한 많은 좋은 정보를 남겨드릴 수 있었으면 좋았을 텐데.. 개인적으로 해야할 일들을 하느라 상당 부분 시간을 뺐겼습니다. 앞으로도 장담하진 못하고 있지만.. 마음이 맞는 분들과 새로운 OS제작을 시작하였습니다. OS구현이 목적이라기 보다는 많은 이론적인 것들을 공부를 하며 구현에 적용해 보고자 하는 것이었고 가끔 그런 취지를 망각하고 구현에 힘을 쏟으려 애를 쓰는 경우도 생기곤 하지만 그것보다는 이론적인 접근과 저와 같은 초보 분들에 쉬운 접근(많은 재밌는 알고리즘들과 커널의 동작원리)에 대해 고민하고 있습니다. 이제는 만들고 있는 지 얼마 안되었고, 아직은 같이 공부하고 있는 분들과 공유하고 있는 사이트를 공개할 만하지 못하지만 나중에 언제가 좋은 자료가 모이게 되면 다른 분들의 동의를 얻어 공개하고자 합니다. 그 때는 많은 분들에게 좋은 자료 드릴 수 있었으면 합니다. 간만에 몇자 끄적이고 갑니다.
|
