process scheduling

Process scheduling

    linux에 관한 내용

    지금까지는함수 명은 linux에 dependent하지만, 내용은 일반적인 내용 이었는데,

    본 내용은 linux dependent한 내용이다.

   

Linux의 scheduler

    -Non-Retal-Time scheduler

    -Real-Time Scheduler

   

    real time으로비춰지지는 않는다.

 

Linux scheduling

    1. Time sharing (SCHED_NORMAL; SCHED_OTHER)<- defaultscheduler

           RR (Round-Robin) 유사한 것 사용

           time slice를 할당해서 process가 processor resource 사용

           timer interrupt에 의해서 동작하게 된다.

           

            button-up에서context switching을 유발 시키는 형식

           

            최근의 Linux kernel에는 scheduler가 변경 되었다.

            à 최신의 Linux는 timeslice를 사용하고 time interrupt에 의존적이지 않게 되었다.

               CFS(Completely Fair Scheduler)

              

            Linux는priority를 지닌다. (real-time이던non-real-time이던 지님)

           Linux는 priority를non-real-time으로 변경 시켜 준다.

           

           Start --> ready ---> run---> Exit

                           <---                          

                           wait

 

           ready와 run 모두 taskrunning으로 (같은 상태여도 ready queue에있으면 ready 상태이고,

즉, 이 둘은 따로 state를 나눌 필요가 없을 수 있기에)

           linux도 둘을 running으로 본다.

 

TASK_RUNNING     TASK_INTERRUPTIBLE     TASK_UNINTERRUPTIBLE     __TASK_TRACED     __TASK_STOPPED         기존 task가 fork로 process 생성 ----------> TASK_RUNNING --------------> TASK_RUNNING ------> TASK 종료                task 생성      ^ ^        schedule()           | |       do_exit                                                          | |        context_switch()    | |                               | |                               | |                               | +--------------------------+ |                 특정 조건으로 |         선점됨                     | 대기열로 이동                 깨어나 실행   |                                    | (휴면 상태)                 대기열로 이동 +---- TASK_INTERRUPTIBLE <-----+                                     or                                      TASK_UNINTERRU

 

        TASK_INTERRUPTIBLE

               Interrupt를 받을 수 있고 signal에 의해 깨어나 running 상태로 진입 가능한 wait 상태

 

        TASK_UNINTERRUPTIBLE

               Event에 의해서만 깨어날 수 있는 wait 상태 (interrupt를 받지 못함/signal에 의해 깨지 못함)

           

        TASK_STOPPED

               process가 ctrl+z를 누르면 멈춰 있는 이런 상태 (SIGSTOP - 상태)

                

        TASK_TRACED

               break point해서 process를 어느 순간까지 진행하다가 멈추는 기능을수행하고자 할 때

               ptrace()를 사용해서 제어를 하는데, 이 제어를 받는 것은 TASK_TRACED 상태로 관리

              

        EXIT_ZOMBIE

               process가 종료 되었지만,

               자원을 아직 반환 하지 못했을 때의 상태

                자신이 fork한 process를 부모가 더 관심을 가질 수 있다는 개념에서 만들어진 생태

               (윈도우는 일단, process를 생성하고 관심을 안 갖는 구조)

               à Linux는 zombie로 인해서 à

PID 및 task structure를 유지 하기 때문에 garbage가 많아져서 성능 저하가 발생 à

해서 공격을 받았었으나 현재는많이 fix되어서 문제가 더 이상 report되지 않는다.

          

       EXIT_DEAD

               자원까지 반환한 상태

 

           

            어느한 쪽에서 이미 dead 상태에서 wait을 호출하지 않기위해서 2개로 나누었다.

 

Classes of processes

    process들이 priority를 지니는데, 이priority를 동적으로 바꿔줄 수 있음

   

1.     interactive process

        뭔가반응을 기다리는 process

        Linux가상대적으로 높은 prio.를 준다.

2.     Batch process

        계산만하는 process

        Linux가상대적으로 낮은 prio.를 준다.

3.     Real-Time process

       interactive하던, batch하던 관계 없이 높은 priority를 얻음

       priority를 초기의 값을 유지 시킨다.

 

interactive와 batch의구분

wait에서 오래 있으면 à interactive로 판단

    run에오래 있으면 à batch로 판단

   

    Network라면, wait 하다가 많은 처리를 한번에 하면

    Linux는 batch하다고 판단. (실제로는interactive하지만)

 

Process Preemption

    Priority

       TASK_RUNNING state (READY state로 새롭게 진입 시 run queue에있는 것보다 prio.가 높으면)

        현재 run이던 것이 preemption된다.

       

       2.6.23이 CFS를사용하기 시작 (no dynamic priority)

   

    Time quantum

        priority이외에 time quantum을 다 사용하면preempted

       

Linux 2.6 Kernel is preemptive

        timer외에다른 interrupt의 실행 시, 혹은 system call 등의 발생 시 scheduler를 돌려야 하는지 check

        이때어느 조건을 만족하면 preemption된다.

        실제로 user 영역이던 kernel 영역이던 preemption 될 수 있는 region이 상당히 많아졌다.

        이것을많이 하면 할 수록 hard real-time을 계산하기 어려워진다.(preemption point가 많아지니깐)

 

        정확한hard-real-time의 만족 여부는 instruction 별로 preemption이 되는지 안 되는지 판단해야 하는데,

이것이 복잡하기 때문에 현실적으로는 hard-real-time의 판단이 어렵다.

       

Quantum duration

    process를실행할 때, 얼마만큼의 quantum time용 time slice를 할당해야 하는가?

   

    작은 값이면

        잦은 scheduling에 의한 overhead 발생

    큰 값이면

        반응속도가문제

   

    Real-time쪽이라고 한다면,

        Linux는아직 real-time 용으로 적합하지 않다고 할 수 있다.

 

    timequantum이 크면 dead-line을 check하는 resolution이 커지게 되기 때문에

    어떤반응 시간 내에 가용한 resource가 제한될 수 있다.

 

Linux Non-Real-Time Scheduler

    SCHED_OTHER가 원래 이름 이었는데, SCHED_NORMAL로 바뀌었고.. 다시CFS로변경 되었음.

 

SCHED_NORMAL

1.    Time-shard process scheduler

        O(1)scheduler       

        2.6에서자신 있게 내 놓은 scheduler (이전에는 O(n))       

           Ingo Molor

               Linux의 patch를 많이 만든 사람인데,Linux scheduler에 대한 patch를 수행

               많은 preemption point를 제거 하였다.   

2.    2개의priority를 관리 (priority와 nice 값)

3.    Static Priority (0~99, 100~139)

       100~139 (큰 값이 낮은 priority) -- SCHED_NORMAL

       

        100 이전은 real-time scheduler가 사용

   

       setpriority() <-- priority 변경

       nice()      <--

       

 

                                staticprio.    nice val.       Quantum

           highest priority    100             -20             800ms

           default ..          120             0               100ms

           lowest..            139             +19             50ms

           

           formula

               heuristic formula               

               (140-static priority ) * 20, if static priority < 120

               ..                     * 5 ,                    >= 120

 

ex. 800ms 의 quantum이어도, 대부분의 process는 IO 처리를위해서 wait으로 가게 되기에,

800ms 동안 쭉 다 쓸 수 있는 경우가 없다.

            혹은 preemption 된 다른 process에 의해서 preempted될 수 있다.

            ready로 들어온 process가현재 도는 process 보다 더 높은 priority        

  

           time quantum은 static prio.로 판단하고,

            실제로동작하는 process의 prio.는 dynamic prio.로 관리

 

Dynamic priority

    staticpriority만 가지고 돌리게 되면, 반응 속도가 느려 질 수 있으며, 여러 문제 가능 하므로,

    kernel은내부에서 dynamic priority를 관리한다. (userlevel에서 볼 수 있는 priority가 아니다.)

   

    bonus를가지고 결정

        0 ~10       

        5는가장 낮은 priority의 penalty를 의미.       

       

    TASK_INTERRUPTIBLE (wait 상태의 상태 값) -- 에 자주 들어가면, 전체priority가 작아지게 된다.

        그럼, bonus 값이 작으니, 자꾸 들어오면 bonus 값을 올려준다.

        (I/Owait 상태의 것은 priority를 높여줘서 run이더 빨리 될 수 있도록 하고)

       

        혹은계속 돌던 것은 낮은 bonus를 줘서 상대적으로 바로 다른 것이 돌 수 있도록 관리를 해 준다.

 

Interactive and batch processes

    Interactive

        어떤 것은 상당히 nice해서 time quantum이 작은데, interactive하기 까지 하면

           -> resource를 너무 못 가져가게 되니,

           interactive하면, time quantum을 다 소모해도, 다시 좀 더 돌 수 있도록 처리해 주는 것이다.

           (IO intensive한 process를 더 챙겨 주는 방식)

           

            Dynamicpriority <= 3 * static priority / 4 +28

            Bonus- 5 >= static priority / 4 - 28

           

            위수식을 만족하는 process는 interactive하다고판단.           

           interactive와 batch를 번갈아 가게 될 수 있다. (wait time에 의해서)

 

Active and Expired Processes

Active Processes

        아직 time quantum이 남은 processes

   

    Expired processes

        timequantum을 다 써서 다음 time quantum을 기다리는 processes

   

    Scheduler

        batch인지아닌지를 판단하여, interactive면,

        다시 active 상태로 넣어 주기 위한 time quantum 계산 및time quantum을 증가 시키는 작업 수행

           expired process 중 긴 시간 동안 기다리는 것이 있으면 쫓아낸다.

       

       expire된 것 중 static prio.가 높은 것이 있으면 따로 빼준다.

   

    그림, CPU-X Expired run queue와 CPU-X Active runqueue (dynamic priority)

    위 두개 queue는 Active가 비면,expired runquque와 Active runqueue를 포인팅만 변경해서

O(1)의 scheduling이 가능하게 되었다.

      à priority 별로 queue를 따로 두었기에 찾는데, 시간 감소

 

 

CFS (Completely Fair Scheduler)

   Real-time-scheduler가 아닌 이상 궁극적인 목표는 fairness이다.

     - fair의기준은 CPU의 사용 시간

   

    앞 보다개념이 간단.   

    IO intensive (많이 wait한것)에 더 많은 기회를 주겠다는 것

   

    No timeslice

   

    자신보다 virtual run time이 작은 것이 생기지 않을 때까지 계속 run

    (부작용: 작은 것 둘이 있을 때, 두 개가 서로 작아지면서 서로 계속 context switching 가능

è  그래서 이것에대한 처리가 문제가 되었음)

   

    이에대한 granularity를 /proc/sys/kernel/sched_granularity_ns에서설정 가능

 

    Red-Blacktree를 사용   

    binarytree의 문제 (balanced가 아닐 수 있음 -linked list의 n time 소모 가능)

   

    balanced로만들려면, 새로운 것을 insert 시 마다 overhead가 발생하는데,

(이를 가장 잘 해주는 binary tree는 AVL-tree)

    이 AVL-tree는 너무 balance를 너무 잘 맞춰 주려고 하기때문에 O(n)이 너무 자주 생긴다.

   

    AVL-tree만큼은아니지만, 이와 유사하게 동작하는..

    balanced의mismatching을 x2 rbtree로 해 주는 것이 red-black tree이다.

   

   sched_normal에 비해서 복잡도의 증가가 심각하지 않다고 판단되어 사용 되고 있음

   

    R-B-tree의 node에서의 시간은 virtual runtime이며,

이 값이 run 한 시간이다. 오른쪽으로 가면 많이 run된 것 왼쪽은 적개 run 된 것들   

    left-most를꺼내서 run 시키는 구조이다.

   

    virtualtime 뿐만 아니라, static priority 역시 존재한다.

    staticpriority는 감쇄 factor로서 사용한다. (높은 priority의 process는 상대적으로 덜 감쇄)

    낮은priority는 상대적으로 더 감쇄 시킨다.

   

    linkedlist 보다 RBT의 조작이 어려워서 그렇지만, 더동작이 simple하고 fair한 scheduling이 가능하다.

    더 reasonable한 policy를 사용하고 있음

   

    Vanillakernel ver. 를 사용하면 CFS를 사용하고 있다.   

 

Linux Real-Timer Scheduler

    linux가제공해 주는 real-time scheduler   

    priority만고려해서 결정한다.   

    높은 prio.먼저 수행하는 simple

   

Real-time priority

    from 1 ~99

   

    높은 prioroty 동작, 낮으면wait

    같은 prio.는 RR등으로

   

   sched_setparam()

   sched_setscheduler()        <-pri. 및 scheduler 의 종류까지 선택

   

    위 2개 함수를 사용해서 prio.를 결정 해 줄 수 있다.

   

Sched 종류

    SCHED_FIFO

        timesharing을 위한 것 이었는데, prio. 개념을 추가

        같은 prio에 대해서 FIFO로 할 것이냐 RR로 할 것이냐를 결정한다.

       

        ex.       

       prio.  process.

       1      A

       2      B, C

       3      D       

       

        A ---B --- C --- D (B가 C보다 먼저 실행 -FIFO니깐) 물론 높은 prio.의 proce.에 의해서 preempted

 

 SCHED_RR

       sched_RR은

       

        A ---B --- C --- B --- C --- B --- C --- D <-- 동일 prio.에 대해서FIFO냐, RR이냐의 차이

        

    SCHED_DEADLINE

        진정으로 real-time scheduler라고 부를 수 있는 scheduler       

        주기적인 task인데, dead-line을 놓치지 않고 실행 될 수 있는 scheduler

       

        EDF라는알고리즘을 구현 (Earliest Deadline First)       

        새작업이 preemption에 대해서 자신의 deadline을만족 시킬 수 있는지 여부를 수식으로 결정

       

        WCET(Worst-Case Execution Time)

            어떤 task의 동작에있어서 최악으로 오래 걸리는 시간이 무엇인지           

            자신이필요한 period, 시간 time           

           period에 대해서 time만 받으면 되는데, 이것이 지켜 질지는 모른다.

           

           IO 시간이 포함되면, 이것을 파악 하기가 어렵다.

            이것이정확하지 않으면 시스템이 꼬이게 되어 있음

            

            아직 kernel ver.에 들어가 있지 않다.

           http://www.gitorious.org/sched_deadline/pages/Home

            가서 patch를 해야 사용 가능

 

Context Switch

 

Context switch 발생 경우

1.    높은 priority의 process가 들어올 시

2.    I/O wait

3.    stop 경우

4.    yield 경우: sched_yield( )

        자신과동일 priority에 넘겨준다. (동일 priority가 없으면 - 실제론no yield임)

5.    SCHED_RR 자신의 time slice를 모두 사용한 경우

 

SYSTEM CALLS

nice() getpriority()       <-- SCHED_NORMAL 사용 하는 쪽에서 사용 setpriority()        <-- SCHED_NORMAL 사용 하는 쪽에서 사용

 

  Realtimescheduler APIs

sched_getscehduler() sched_setscheduler( )           <- scheduler 정책 결정 가능 (FIFO, RR, DEAD_LINE) sched_getparam( ) sched_setparam( ) sched_yield( )                  Relinquish the processor voluntarily without blocking sched_get_ priority_max( )      Get the minimum real-time priority value for a policy sched_get_ priority_min( )      Get the maximum real-time priority value for a policy sched_rr_get_interval( )        Get the time quantum value for the Round Robin policy sched_rr_get_interval()

 

sched_setaffinity( )       : multi-core용 - process가 어느 processor 상에서만 동작 할 수 있도록 지정 가능 sched_getaffinity( )

 

FIFO example

   

intset_pro_priority(intpri) {        structsched_paramparam;        inttemp;        temp = sched_getscheduler(0);          if (pri == 0) {              param.sched_priority = sched_get_priority_max(SCHED_FIFO);        } else if(pri== 1) {              param.sched_priority = sched_get_priority_min(SCHED_FIFO);        } else {              param.sched_priority = pri;        }          if (sched_setscheduler(0,SCHED_FIFO,&param) !=0) {         return -1;        }          if (sched_setparam(0,&param) != 0) {              return -1;        }        return temp; }