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) <- default scheduler

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

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

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

           

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

           

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

            à 최신의 Linux는 time slice를 사용하고 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 모두 task running으로 (같은 상태여도 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 용으로 적합하지 않다고 할 수 있다.

 

    time quantum이 크면 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()      <--

       

 

                                static prio.    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

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

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

   

    bonus를 가지고 결정

        0 ~ 10       

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

       

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

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

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

       

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

 

Interactive and batch processes

    Interactive

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

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

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

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

           

            Dynamic priority <= 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

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

   

    Scheduler

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

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

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

       

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

   

    그림, CPU-X Expired run queue와 CPU-X Active run queue (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 time slice

   

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

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

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

   

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

 

    Red-Black tree를 사용   

    binary tree의 문제 (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 시키는 구조이다.

   

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

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

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

   

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

    더 reasonable한 policy를 사용하고 있음

   

    Vanilla kernel 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

        time sharing을 위한 것 이었는데, 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 사용 하는 쪽에서 사용

 

  Realtime scheduler 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; }