5/29 複習Lab3 與預習Lab4背景知識

82 views
Skip to first unread message

Ben

unread,
May 22, 2012, 11:46:15 AM5/22/12
to julu...@googlegroups.com

主題內容:   MIT OSE 讀書會:  (共90分鐘)

  • 複習 Lab 3: Part A/B 及問題討論
  • 預習 Lab 4: Preemptive Multitasking 背景知識

時間: 2012/05/29 19:30 ~ 21:00 (聚會在Mix Coffee &Tea

報名網址:http://registrano.com/events/345d7c
網路筆記網址:http://sync.in/juluosdev


分享者:  Ben及與會者


複習上次實題及討論: (40分)

Lab 3 - Part A/B: Page Faults, Breakpoints Exceptions, and System Calls

LEC 5: Process Creation System call, Interrupt, and Exception Handling (handouts:IDT)
預習實題: (30分) Next Topic (6/12)  Lab 4: Preemptive Multitasking 背景知識


LEC 6: Virtual Memory Multiprocessors and locking


LEC 7: Process scheduling

  • Preparation: Read "Scheduling" up to "Sleep and wakeup" with proc.c, setjmp.S, and sys_fork (in sysproc.c); do Homework 6

LEC 8: Processes and coordination
  • Preparation: Read remainder of "Scheduling"; read remainder of proc.c and sys_wait, sys_exit, sys_kill; do Homework 7


社群運作的下一步 (20分鐘)

  • 議程討論 COSCUP Workshop


    (本次活動會需要使用電腦實際上機練習, 請不要把notebook忘在家裡。)


    此次活動已加入TOSSUG行程(請參閱http://www.tossug.org/2012)

    (註1:活動時間 7:30pm 開始,6:30pm 開始入場。)

    (註2:如包場,參加者需在店消費約200元以下,折抵場地費。)

    (註3:活動採分享心得或研究實作展示。)

    (註4:活動場地有提供無線網路。)

    Ben

    unread,
    May 29, 2012, 11:06:38 AM5/29/12
    to julu...@googlegroups.com

    way

    unread,
    May 30, 2012, 4:55:36 AM5/30/12
    to julu...@googlegroups.com
    hi 感謝分享,問一下昨天丹尼斯說wiki的spin lock有問題是哪裡有問題呢??
    昨天沒聽仔細 .....SORRY.

    spinlock的文章,內容有提到cmpxchg ,xchg比較,可以測試一下.....


    Ben <ben...@gmail.com> 於 2012年5月29日下午11:06 寫道:
    今日讀書會紀錄2012-05-29

    way

    unread,
    May 30, 2012, 5:55:57 AM5/30/12
    to julu...@googlegroups.com
    這篇不錯,基本觀念都講了 Spinlock
    http://wiki.osdev.org/Spinlock 

    Ben

    unread,
    May 31, 2012, 9:06:22 AM5/31/12
    to julu...@googlegroups.com
    問題應該出在沒檢查目前的lock是不是已鎖定(lock=true) 再設定 lock,  
    因需同時比較lock值且設定它. 
    (比較與資料交換若非保證在同一指令, 還是會有race condition 發生的可能)

    這裡看到一個實作方式使用 gcc builtins 的函式
    Note that GCC has atomic builtins, so you don't actually need to use inline asm to accomplish this:

    void spin_lock(int *p)
    {
        while(!__sync_bool_compare_and_swap(p, 0, 1));
    }

    void spin_unlock(int volatile *p)
    {
        asm volatile (""); // acts as a memory barrier.
        *p = 0;
    }

    Jim Huang

    unread,
    May 31, 2012, 9:13:59 AM5/31/12
    to julu...@googlegroups.com
    2012/5/31 Ben <ben...@gmail.com>:

    > 問題應該出在沒檢查目前的lock是不是已鎖定(lock=true) 再設定 lock,
    > 因需同時比較lock值且設定它.
    > (比較與資料交換若非保證在同一指令, 還是會有race condition 發生的可能)

    Gotcha!

    > 這裡看到一個實作方式使用 gcc builtins 的函式
    > http://stackoverflow.com/questions/6935442/x86-spinlock-using-cmpxchg
    > Note that GCC has atomic builtins, so you don't actually need to use inline
    > asm to accomplish this:

    在 gcc-4.5 之後,對於 atomic builtins 有了較多的硬體架構支援,如 ARMv6+
    (ldrex/strex),Android library 原本有若干 atomics macro,在新版 (應該在下個 AOSP 版本)
    也改用 gcc builtins

    > void spin_lock(int *p)
    > {
    > while(!__sync_bool_compare_and_swap(p, 0, 1));
    > }
    >
    > void spin_unlock(int volatile *p)
    > {
    > asm volatile (""); // acts as a memory barrier.
    > *p = 0;
    > }

    memory barrier 還得考慮到 SMP,有對應的硬體指令。

    Thanks,
    -jserv

    way

    unread,
    May 31, 2012, 9:29:18 PM5/31/12
    to julu...@googlegroups.com
    我覺得應該沒問題吧~至少我看過的很多kernl都是這樣寫的 

    直接來看WIKI 的code吧

    lock:                        ; The lock variable. 1 = locked, 0 = unlocked.
         dd      0
     
    spin_lock:
         mov     eax, 1         
         xchg    eax, [lock]   ; Atomically swap EAX register with lock variable.
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    這沒問題,一定是 atomic 
         test      eax, eax    
    ^^^^^^^^^^^^^^^^^^^^^^^^^^
    你指的問題,是說如果在執行這指令時被context switch,然後被修改嗎?
    可是context switch會保證你的register前後的內容一致阿,所以應該不會有問題才對.
         jnz       spin_lock  
         ret


    2012/5/31 Ben <ben...@gmail.com>
    這裡使用 memory barrier,是為了效率,跟LOCK行為沒有直接關係吧
        *p = 0;
    }

    sung descent

    unread,
    May 31, 2012, 11:57:01 PM5/31/12
    to julu...@googlegroups.com
    請問這行為什麼有 memory barrier 的效果?
    x86 不需要 memory barrier 指令嗎?

    > *p = 0;
    > }

    way

    unread,
    Jun 1, 2012, 12:14:04 AM6/1/12
    to julu...@googlegroups.com
    asm volatile("": : : "memory");

    應該是這樣吧,這兩個效果一不一樣我就不知道了


    http://nano-chicken.blogspot.tw/2009/09/linux-memory-barrier.html 


    2012/6/1 sung descent <desc...@gmail.com>

    Ben

    unread,
    Jun 1, 2012, 10:19:46 AM6/1/12
    to julu...@googlegroups.com


    wayling於 2012年6月1日星期五UTC+8上午9時29分18秒寫道:
    我覺得應該沒問題吧~至少我看過的很多kernl都是這樣寫的 

    直接來看WIKI 的code吧

    lock:                        ; The lock variable. 1 = locked, 0 = unlocked.
         dd      0
    Ben:  我定義lock 為全域變數.  
     

     
    spin_lock:
         mov     eax, 1         
         xchg    eax, [lock]   ; Atomically swap EAX register with lock variable.
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    這沒問題,一定是 atomic
    >> yes 
     
         test      eax, eax    
    ^^^^^^^^^^^^^^^^^^^^^^^^^^
    你指的問題,是說如果在執行這指令時被context switch,然後被修改嗎?
    可是context switch會保證你的register前後的內容一致阿,所以應該不會有問題才對.
     
     我們先不談content switch情況,

      timing 1. 當有兩顆以上CPU 共用這個lock全域變數時, 其中第一、二顆CPU 同時執行到 xchg  及 test eax, eax 中間(因為這段程式沒有比較 eax 是否為 1, 
                      , 這時有第三顆cpu即將呼叫 spinunlock,
      timing 2. 第三顆 cpu 呼叫spinunlock, eax 設為0, 則第一、二顆CPU 同時拿到鎖, 進入 critical section. 
      timing 3, 第一、二顆CPU 同時存取需獨佔的資料如(硬碟同時只能有一個寫入的動作等)

    如何避免這種況, 我看到兩種解法
    1. 使用cmpxchg,   保證不會有上列情況, 因為 (xchg+test 同時執行為atomic的) 
    2.  保證同時最多只有1顆CPU 使用lock 全域變數執行上述spinlock&spinunlock程式。


         jnz       spin_lock 
     
         ret

    Gavin Guo

    unread,
    Jun 2, 2012, 7:30:57 AM6/2/12
    to julu...@googlegroups.com

    x86 應該可以用 lock bus 來解決 multi-core 的問題。我記得 arm 的 ldrex/strex 也可以解決 multi-core 共競現象。有錯請指教。

    Gavin

    way

    unread,
    Jun 3, 2012, 11:48:11 PM6/3/12
    to julu...@googlegroups.com
    Ben <ben...@gmail.com> 於 2012年6月1日下午10:19 寫道:


    wayling於 2012年6月1日星期五UTC+8上午9時29分18秒寫道:
    我覺得應該沒問題吧~至少我看過的很多kernl都是這樣寫的 

    直接來看WIKI 的code吧

    lock:                        ; The lock variable. 1 = locked, 0 = unlocked.
         dd      0
    Ben:  我定義lock 為全域變數.  
     

     
    spin_lock:
         mov     eax, 1         
         xchg    eax, [lock]   ; Atomically swap EAX register with lock variable.
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    這沒問題,一定是 atomic
    >> yes 
     
         test      eax, eax    
    ^^^^^^^^^^^^^^^^^^^^^^^^^^
    你指的問題,是說如果在執行這指令時被context switch,然後被修改嗎?
    可是context switch會保證你的register前後的內容一致阿,所以應該不會有問題才對.
     
     我們先不談content switch情況,

      timing 1. 當有兩顆以上CPU 共用這個lock全域變數時, 其中第一、二顆CPU 同時執行到 xchg  及 test eax, eax 中間(因為這段程式沒有比較 eax 是否為 1, 這時有第三顆cpu即將呼叫 spinunlock,
     
      timing 2. 第三顆 cpu 呼叫spinunlock, eax 設為0, 則第一、二顆CPU 同時拿到鎖, 進入 critical section. 

    hi ben

    你這裡講的有點問題,兩顆cpu (CPU 1& 2)同時執行到xchg,沒問題,但卻只有一顆可以把eax設為0,並把lock設為1,接者通過接下來的test進入critical section.
    因為CPU會鎖memory,所以只有一個CPU可以取得spin_unlock時設的0.

    所以我還是覺得這段code在smp上也沒問題.

    有錯請指正 

    way

    unread,
    Jun 4, 2012, 12:05:47 AM6/4/12
    to julu...@googlegroups.com

    Ben

    unread,
    Jun 4, 2012, 12:18:47 AM6/4/12
    to julu...@googlegroups.com

    ARM與Cortex筆記-ARM MPCore (Multi-Processor Core) 多核心架構解析.

    感謝分享,這篇文章寫得不錯,值得一讀。

    Gavin Guo

    unread,
    Jun 4, 2012, 2:27:58 AM6/4/12
    to julu...@googlegroups.com
    x86 可以參考 understandling linux kernel version 3 (裡面有對 lock 指令進一步的解釋):
    http://www.civilnet.cn/book/kernel/Understanding.the.Linux.Kernel(3rd%20Edition)/understandlk-CHP-5-SECT-2.html

    Read-modify-write assembly language instructions (such as inc or dec)
    that read data from memory, update it, and write the updated value
    back to memory are atomic if no other processor has taken the memory
    bus after the read and before the write. Memory bus stealing never
    happens in a uniprocessor system.

    Read-modify-write assembly language instructions whose opcode is
    prefixed by the lock byte (0xf0) are atomic even on a multiprocessor
    system. When the control unit detects the prefix, it "locks" the
    memory bus until the instruction is finished. Therefore, other
    processors cannot access the memory location while the locked
    instruction is being executed.

    ---------------------------------
    1: lock; decb slp->slock
    jns 3f
    2: pause
    cmpb $0,slp->slock
    jle 2b
    jmp 1b
    3:

    The decb assembly language instruction decreases the spin lock value;
    the instruction is atomic because it is prefixed by the lock byte. A
    test is then performed on the sign flag. If it is clear, it means that
    the spin lock was set to 1 (unlocked), so normal execution continues
    at label 3 (the f suffix denotes the fact that the label is a
    "forward" one; it appears in a later line of the program). Otherwise,
    the tight loop at label 2 (the b suffix denotes a "backward" label) is
    executed until the spin lock assumes a positive value. Then execution
    restarts from label 1, since it is unsafe to proceed without checking
    whether another processor has grabbed the lock.

    Regards,
    Gavin
    Reply all
    Reply to author
    Forward
    0 new messages