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

[Ben]

主題內容:   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及與會者

• 報名前，請先參閱2012讀書會相關活動方式
• 以MIT OSE 2011  課程教材為輔及實際以Labs練習為主，來一同交流學習OS開發。
• Google網上論壇: 主題討論

複習上次實題及討論: (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)

• "Traps, interrupts, and drivers" and the related xv6 source files; doHomework 4
  

預習實題: (30分） Next Topic (6/12)  Lab 4: Preemptive Multitasking 背景知識

LEC 6: Virtual Memory Multiprocessors and locking

• Preparation: Read "Locking" with spinlock.c and skim mp.c; do Homework 5
  

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]

今日讀書會紀錄2012-05-29

[way]

hi 感謝分享,問一下昨天丹尼斯說wiki的spin lock有問題是哪裡有問題呢??

昨天沒聽仔細 .....SORRY.

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

http://chenyufei.info/blog/2012-01-28/spinlock-implementation-comparision/

Ben <ben...@gmail.com> 於 2012年5月29日下午11:06 寫道：

今日讀書會紀錄2012-05-29

[way]

這篇不錯,基本觀念都講了 Spinlock

http://wiki.osdev.org/Spinlock 

[Ben]

問題應該出在沒檢查目前的lock是不是已鎖定(lock=true) 再設定 lock,  

因需同時比較lock值且設定它. 

(比較與資料交換若非保證在同一指令, 還是會有race condition 發生的可能)

這裡看到一個實作方式使用 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:

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]

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]

我覺得應該沒問題吧~至少我看過的很多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]

請問這行為什麼有 memory barrier 的效果？
x86 不需要 memory barrier 指令嗎？

> *p = 0;
> }

[way]

asm volatile("": : : "memory");

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


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

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

[Ben]

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.  保證同時最多只有１顆CPU 使用lock 全域變數執行上述spinlock&spinunlock程式。

     jnz       spin_lock 

 

     ret

[Gavin Guo]

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

Gavin

[way]

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]

hi  Gavin 

剛好看到 http://loda.hala01.com/2011/06/arm%E8%88%87cortex%E7%AD%86%E8%A8%98-arm-mpcore-multi-processor-core-%E6%9E%B6%E6%A7%8B%E8%A7%A3%E6%9E%90/ 

就當reference吧,因為我看不是很懂 XD

[Ben]

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

http://loda.hala01.com/2011/06/arm%E8%88%87cortex%E7%AD%86%E8%A8%98-arm-mpcore-multi-processor-core-%E6%9E%B6%E6%A7%8B%E8%A7%A3%E6%9E%90/ 

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

[Gavin Guo]

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