임베디드 레시피

Egloos | Log-in




2009년 08월 17일

Scheduler의 구현

드디어 Kernel의 가장 핵심 Scheduler가 등장하는 순간입니다. 두두두두. Scheduler의 Context Switching에 대한 Policy가 바로 선점형이라든가, 비선점형이라든가를 결정하는 핵심이 되겠사옵니다. 그러면, Scheduler가 해야 할 일은 실은 꼭 찝어서 2가지 정도 된다고 봐야 하지 않을 까 해요.
 
1) 다음에 순서를 받을 Task 선정
2) Context Switching을 해야겠죠. 어떻게? 현재 Running Task의 Context 를 해당 Task의 Stack에 저장하고, 다음 번 순서의 Task의 Stack에서 Context를 CPU Register로 가져오는 일을 해서 그 일을 마무리 하는 거죠.
 
1) 다음 순서를 받을 Task를 선정하는 방법 - 가장 높은 Priority를 가진 Ready Task를 선정하는 방법. 다음에 순서를 받을 Task를 선정하는 방법에는 여러 가지 방법이 있어요. Priority base 같은 경우에는 Priority 순서대로 TCB를 Linked List로 연결해서 묶어 놓은 후에, TCB를 묶어 놓은 Head부터 점차 하나하나 Ready된 Task를 찾아가는 걸로 다음 Task를 결정할 수도 있고요.
 
 
이렇게 Ready된 Task를 찾아가는 게 시간이 걸리니까, Ready Task만 다로 Ready Task List로 따로 관리하는 방법도 있어요. 그런 경우에는 send_signal() 내부에 Ready 시킨 Task를 Ready Task List에 넣어주는 수고로움을 해줘야 한답니다.
 
여하튼 간에 그 모양새는 (Priority 높은 순서대로.)
 
뭐 이런 꼴이 되는 거지요. 전체 Task TCB도 이렇게 관리 될 수가 있고요, 그 중 Ready된 녀석들만 따로 만들어서, 그쪽에 넣어줘도 되겠죠. Linked List로 관리하면 넣고 빼고가 편리하니까, 가능한 일이죠.
 
(이런 방법은 Task가 많을 수록 Highest Priority Task를 찾는데 시간이 걸리겠죠.) 이것 때문에 여러 가지 방법들이 많이 나오는데, 요즘은 computing power가 좋아져서 이 방법도 꽤나 쓸모 있으니, 참고해 두세요.
 
그러면 실제 Context Switching은 어떻게 할 거냐. 하면! 현재 context를 해당 task의 stack에 집어 넣는 일을 해야겠죠. 그건 Assembly로 가능하니까, 그 예를 들어보도록 하겠나이다.
 
   
2) Context Switching 하는 방법은,
 
   1) CPSR을 제대로 저장할 수 있어야 한다.
   2) Context를 제대로 저장 가능 해야함.
   3) 현재 task tcb에 context를 push한 후 update된 sp를 마지막에 tcb에 저장 가능해야 한다. ■
 
    stmfd   sp!, {lr}                 ; lr을 stack에 넣자. 영차.
    sub     sp, sp, #4               ; r13 자리는 TCB에 넣을꺼니까 비워둠.
    stmfd   sp!, {r0-r12}           ; r0~r12를 stack에 넣음.
    mrs      lr, CPSR                 ; lr은 이미 stack에 넣었으니까, CPSR을 담아두는 temp 저장소로.
    stmfd   sp!, {lr}                 ; CPSR을 back up 해둔 걸 stack에 넣자.
    ldr r0,= curr_task_tcb          ; 현재 task tcb의 주소를 가져온 후,
    str     sp, [ r0, #TCB_SP_POSITION]   ; 현재 tcb의 sp넣을 위치에 sp를 넣어줌.
 
3) 그러면, 다음 New Task의 Context를 다시 CPU register에 load하는 방법은,
 
    1) CPSR을 제대로 가져올 수 있어야 한다. 어디에? SPSR에.. 그 이유는  Context Switching 당했을 때의 CPSR로 복구되기 보담은 Context가 복구 된 후 한꺼번에 하려는 게지요.
    2) Context를 모두 제대로 가져와야 한다.
    3) sp를 제대로 복구할 수 있어야 한다.
 
    ldr     r0, = highst_task_tcb              ; 다음 new task의 tcb주소를 가져와서,
    ldr     sp, [r0, #TCB_SP_POSITION]    ; tcb에 저장되어 있던 sp를 불러오자.
    ldmfd   sp!, {r0}                             ; 그전에 저장되어 있던 CPSR을 가져오자 
    msr     SPSR_f, r0                           ; SPSR의 f자리와
    msr     SPSR_c, r0                           ; c자리를 update해 주시고,
    ldmfd   sp!, {r0-r13,pc}^                 ; stack에 넣었던 것들을 불러내고, SPSR을 CPSR로 넣어주고, sp도 update
 
요렇게 하면 간단하겠죠?
 
실제로 그림이 잘 안 그려지죠.  이걸 한번 실제로 어떻게 되는지 보시죠 머. 아래는 Context Switching함수가 불리는 순간의 Context입니다.오른쪽 SP는 Stack을 따로 가르키고요, 현재 그곳의 주소는 R13의 0x1141E8C이지요. 현재 mode는 SVC이고요. IRQ와 FIQ는 Lock이 걸려 있는 상태네요.
 
        Current Context

N _  R0       01E4  R8          0  SP> 00000001
Z _  R1   01154808  R9          0  +04 01141EC0
C C  R2   600000D3  R10  011416C0  +08 010A82E0
V _  R3   01141EC0  R11         0  +0C 0005FC27
I I  R4       6007  R12  007A70A1  +10 00000000
F F  R5          0  R13  01141E8C  +14 00000000
T _  R6   00FE8038  R14      0B49  +18 00000000
J _  R7       03BB  PC   00011218  +1C 00000000
svc  SPSR 600000F3  CPSR 200000D3  +20 00000000
Q _                                +24 00000D29
     USR:           FIQ:           +28 00000000
     R8          0  R8          0  +2C 00000D21
     R9          0  R9          0  +30 00000000
     R10  011416C0  R10         0  +34 01141E4C
     R11         0  R11         0  +38 011416C0
     R12  007A70A1  R12         0  +3C 00000007
     R13  00FEE730  R13  00FEC8A0  +40 00000000
     R14         0  R14         0  +44 00006007
                    SPSR       10  +48 0000002B
                                   +4C 00000000
     SVC:           IRQ:           +50 00000000
     R13  01141E8C  R13  00FED1A0  +54 00000000
     R14      0B49  R14  00011290  +58 018A00D4
     SPSR 600000F3  SPSR 60000013  +5C 0115CF50
                                   +60 00000000
     UND:           ABT:           +64 00000000
     R13  00FEE830  R13  00FEDB30  +68 00FEBF88
     R14         0  R14         0  +6C 00000000
     SPSR       10  SPSR       10  +70 00000000


뒤따라 오는 그림은 Stack이 있는 곳에 대한 Memory 실제 모양새 이에요.일단은 어찌디었던 간에 Context Switching을 하기 위해서는, 
   1) Context를 저장하고요,
   2) 현재 task tcb에 context를 push한 후 update된 sp를 마지막에 tcb에 저장 가능해야 한다.
는 거죠.  그러면 한번 예상해 보세요. Context는 어떤 모양새로 저장이 될까요?   
   
              |
___address__|________0________4________8________C_0123456789ABCDEF
 SD:01141DE0| 0000E913 018A0154 018A00D4 018A0124 ....T.......$...
 SD:01141DF0| 00095F3F 018A00D4 00FE8038 00000027 ?_......8...'...
 SD:01141E00| 00000E15 00000000 018A00D4 018A02AC ................
 SD:01141E10| 00000800 00000027 00000027 00000000 ....'...'.......
 SD:01141E20| 007FE594 600000F3 00000E97 600000F3 .......`.......`
 SD:01141E30| 00000000 007FE594 0115F2B0 00000000 ................
 SD:01141E40| 00FE8038 00000000 00000000 600000F3 8..............`
 SD:01141E50| 011416C0 00000000 00000000 00000000 ................
 SD:01141E60| 00006007 00000000 00FE8038 00000000 .`......8.......
 SD:01141E70| 010A82E0 000003BB 000003BB 00006007 .............`..
 SD:01141E80| 00000000 000003BB 00000B45>00000001 ........E.......
 SD:01141E90| 01141EC0 010A82E0 0005FC27 00000000 ........'.......
 SD:01141EA0| 00000000 00000000 00000000 00000000 ................
 
자, 이제 Context를 저장하게 되면 Stack이 어떤 모양새인지 한 번 보실래요?
일단은
   stmfd   sp!, {lr}                 ; r14  
    sub     sp, sp, #4               ; r13 자리는 TCB에 넣을꺼니까 비워둠.
    stmfd   sp!, {r0-r12}           ; r0~r12를 stack에 넣음.
    mrs      lr, CPSR                  ; lr은 이미 stack에 넣었으니까, SPSR을 담아두는 temp 저장소로.
    stmfd   sp!, {lr}                 ; CPSR back up 해둔 걸 stack에 넣자.
    ldr r0,= curr_task_tcb          ; 현재 task tcb의 주소를 가져온 후,
    str     sp, [ r0, #TCB_SP_POSITION]   ; 현재 tcb의 sp넣을 위치에 sp를 넣어줌.
 
이렇게 했으니까, 제일 먼저 lr이 저장될꺼고, 그 다음 R13자리는 Garbage가 들어 있을 것이고,그 다음에는 R12부터 R0까지 넣어주고요, CPSR을 저장하겠지요?0xB49, Garbage, 0x007A70A1, 0, 0x11416C0, 0, 0, 0x3BB, 0xFE8038,0x0, 0x6007, 0x1141EC0, 0x600000D3, 0x1154808, 0x1E4 순으로 Stack에 집어 넣겠네요. 자, 볼까요.


___address__|________0________4________8________C_0123456789ABCDEF
 SD:01141DE0| 0000E913 018A0154 018A00D4 018A0124 ....T.......$...
 SD:01141DF0| 00095F3F 018A00D4 00FE8038 00000027 ?_......8...'...
 SD:01141E00| 00000E15 00000000 018A00D4 018A02AC ................
 SD:01141E10| 00000800 00000027 00000027 00000000 ....'...'.......
 SD:01141E20| 007FE594 600000F3 00000E97 600000F3 .......`.......`
 SD:01141E30| 00000000 007FE594 0115F2B0 00000000 ................
 SD:01141E40| 00FE8038 00000000 018A02AC>200000D3 > : Push된 다음의 SP
 SD:01141E50| 000001E4 01154808 600000D3 01141EC0 ................
 SD:01141E60| 00006007 00000000 00FE8038 000003BB .`......8.......
 SD:01141E70| 00000000 00000000 011416C0 00000000 .............`..
 SD:01141E80| 007A70A1 000003BB 00000B49>00000001 > : 원래의 SP
 SD:01141E90| 01141EC0 010A82E0 0005FC27 00000000 ........'.......
 SD:01141EA0| 00000000 00000000 00000000 00000000 ................


즉


 SD:01141DE0| 0000E913 018A0154 018A00D4 018A0124 ....T.......$...
 SD:01141DF0| 00095F3F 018A00D4 00FE8038 00000027 ?_......8...'...
 SD:01141E00| 00000E15 00000000 018A00D4 018A02AC ................
 SD:01141E10| 00000800 00000027 00000027 00000000 ....'...'.......
 SD:01141E20| 007FE594 600000F3 018A02AC 600000F3 .......`.......`
 SD:01141E30| 00000000 007FE594 0115F2B0 00000000 ................
 SD:01141E40| 00FE8038 00000000 600000F3>CPSR     8..............`
 SD:01141E50| r0       r1       r2       r3       ................
 SD:01141E60| r4       r5       r6       r7       .`......8.......
 SD:01141E70| r8       r9       r10      r11      .............`..
 SD:01141E80| r12      000003BB lr       >00000001 ........E.......
 SD:01141E90| 01141EC0 010A82E0 0005FC27 00000000 ........'.......
 SD:01141EA0| 00000000 00000000 00000000 00000000 ................



뭐 이런 식인거죠. 거꾸로 Context를 복구할 때는 SP가 가르키는 곳부터 거꾸리 순서대로 restore해주면 되겠죠. 자, 그러면 미지의 Wait state의 Task의 TCB로 부터 lr을 찾아내어, 그 Task가 어디까지 실행한 후, Context Swtiching이 되었었는지 찾아 볼까요?
 
dsp를 관장하는 dsp_task라는 게 있다고 가정하고요, 이 Task의 TCB인 dsp_tcb를 한번 뒤적거려 볼께요.


   dsp_tcb = (
    sp = 0x0113F114,
    receive_signal = 0,
    wait_signal = 24607,
    pri = 125,
    link = (next_ptr = 0x01142488, prev_ptr = 0x01140B10),
    task_name = "DSP"}


뭐 이런식으로 생겼다고 보믄요,
일단 제일 처음 찾아갈 곳은 sp겠네요. 0x113F114를 한번 볼까요.

___address__|________0________4________8________C_0123456789ABCDEF
 SD:0113F110| 00B4BB87>600000F3 00000003 00FBF600 .......`........
 SD:0113F120| 00000000 00000003 0000601F 00000000 .........`......
 SD:0113F130| 00FE8038 0113F188 00000000 00000000 8...............
 SD:0113F140| 0113ED88 00000000 00000000 0113F188 ................
 SD:0113F150| 00000B49 00000001 010E8218 00000000 I...............
 SD:0113F160| 00B4CA09 00000000 00000000 00000000 ................
 SD:0113F170| 00000000 00000000 00000D29 00000000 ........).......
 SD:0113F180| 00000D21 00000000 0113F114 0113ED88 !...............
 SD:0113F190| 00000007 00000000 0000601F 0000007D .........`..}...
 SD:0113F1A0| 00000000 00000000 00000000 01142488 .............$..

 
으흐흐 뭐 이런식으로 생겼사옵니다. 요걸 다시 해석해 보면요,
 
___address__|________0________4________8________C_0123456789ABCDEF
 SD:0113F110| 00B4BB87>CPSR     R0       R1       .......`........
 SD:0113F120| R2       R3       R4       R5       .........`......
 SD:0113F130| R6       R7       R8       R9       8...............
 SD:0113F140| R10      R11      R12      0113F188 ................
 SD:0113F150| lr       00000001 010E8218 00000000 I...............
 SD:0113F160| 00B4CA09 00000000 00000000 00000000 ................
 SD:0113F170| 00000000 00000000 00000D29 00000000 ........).......
 SD:0113F180| 00000D21 00000000 0113F114 0113ED88 !...............
 SD:0113F190| 00000007 00000000 0000601F 0000007D .........`..}...
 SD:0113F1A0| 00000000 00000000 00000000 01142488 .............$..
 
 
뭐 이런 식일 거라는 감이 이제 생기셨죠. R13자리는 여전히 Garbage가 있을 테니까, 굳이R13이라고 적지 않았어요. 그러면, lr에 어떤 값이 있었는지 볼까요? 오, 0xB49 값이 있네요?그러면, 0xB49에 뭐가 있는지 한번 찾아 보지요.
 
_addr/line__|code_____|label____|mnemonic________________|comment
            |      #endif
            |   }
        1680|   sigs = curr_task_tcb->sigs;
 ST:00000B48|6AB0                ldr     r0,[r6,#0x28]
        1681|   INTLOCK_FREE( );
 ST:00000B4A|2D00                cmp     r5,#0x0         
 ST:00000B4C|68C4                ldr     r4,[r0,#0x0C]    
 ST:00000B4E|D101                bne     0xB54
 ST:00000B50|FB96F010            bl      0x11280          
        1682|   return sigs;
 ST:00000B54|1C20                mov     r0,r4            
        1683|} /* END of wait_signal */
 ST:00000B56|BD70                pop     {r4-r6,pc}
 
오, 뭔지는 모르겠지만, 무신 signal관련한 일을 하시네요? 오호라, 뭔가 Signal 냄새가 나는데, 그럼 Stack Frame을 이용하여, 어떤 함수들이 불리워져서여기까지 오게 되었는가 확인 한번 해 보면? - Stack을 통해서 어느 함수에서 불리워 졌는지 알 수 있는 방법 이미 알고 있지요? -

-000|context_switch(asm)
    |
-001|wait_signal(
    |  ?)
    |
    |         context_switch();
 ---|end of frame
   
 
오호라, 이 dsp task는 마지막에 한 일이, wait_signal을 통해서, CPU 점유권을 스스로놓았고, 다른 signal을 기다리고 있네요. 어쩐지 TCB의 receive_signal은 아무것도 없고, wait_signal에는 값이 있더라. 뭐 대부분의 Task는 이런 상태를 갖고 있는 것 처럼 보일 거에요. 뭐 어려운 얘기는 아니지만, 이걸 아는 순간부터, 우리는 강력한 power를 가지게 된거나다름 없어요. 왜냐구요. 우리는 모든 task가 무엇을 하고 있었는지를 확연하게 조사 가능하게 된거니까요.으하하!
, , , , , , , 

by 히언 | 2009/08/17 21:18 | RTOS팩토리(커널) | 트랙백 | 핑백(1)

Linked at 친절한 임베디드 시스템 개발자.. at 2009/10/01 12:45

... ⓗ Scheduler의 구현 ... more

◀ 이전 페이지          다음 페이지 ▶