--
Atomic operation

    執行過程中不會被別的程式中斷的操作

 ex:
    atomic_t v;                     //define v
    atomic_t u = ATOMIC_INIT(0);    //define u and initialize it to zero

    atomic_set(&v,4);               // v = 4 (atomically)
    atomic_add(2,&v);               // v = v + 2 (atomically)
    atomic_inc(&v);                 // v = v + 1 (atomically)










--
Ordering & Barrier
 (問題)    (解法)

    某些程式語意上沒問題，不過平行處理會有問題

    Barrier

    A
    B     ┐
  ───  ├ 插入barrier讓上下不能對調
    C     ┘
    D
    E








--
Spin Lock

   對critical section進行互斥存取的手段

   當資源已經被占用，另一個process會重複"test and set"，直到資源被釋放掉為止

   定義:   spinlock_t lock;

   初始化: spin_lock_init(lock);  //把spin lock設為1(unlock)

   獲得:   spin_lock(lock);       //重複判斷直到spin lock變成1(unlock)
                                  //然後再把spin lock設成0(lock)
                                  //程式碼是先做減法再做判斷

           spin_trylock(lock);

   釋放:   spin_unlick(lock);     //把spin lock設成1(unlock)




--
   注意：

          spin lock = busy waiting lock

          spin lock 有可能導致 dead lock

            ‧遞迴使用spin lock的時候，會抓不到spin_unlock，導致deadlock
            ‧當一個process獲得spin lock後suspend(ex: kmalloc)













--
Read/Write Spin lock

    writer的prioiity較reader低

    write的時候，別人都不能read；read的時候可以很多人一起read

    實作方法：使用一個32bit的變數

              0~30個bit是reader的counter，第31個是給writer使用

              當第31個bit等於1，表示目前rwlock被writer鎖住，

              這時前31個bit都應該是0，代表沒有任何的reader








--
Sequential lock (seqlock)

   writer的priority較reader高

   reader/writer可以各自讀寫，但是reader要重複讀到writer離開為止

   同時只能有一個writer在寫

   使用在很常讀很少寫的狀況












--
   實作方式：

             (1)writer:

                進去的時候，把sequence++，sequence會變成奇數，代表我正在寫

                出去的時候，再把sequence++，sequence變成偶數，代表我寫完了

             (2)reader:

                reader在進去之前要先檢查sequence是否為奇數

                如果是奇數，代表有writer正在寫入，redo直到sequence為偶數再進去

                reader在離開的時候，會檢查當前的sequence值是否有改變

                如果有，就代表writer有進來過，就重讀直到兩次sequence值相同為止




--
RCU (read copy update)

   kernal同步機制之一，避免writer寫到一半就有人跑來讀

   要寫入資料的時候：

        (1) 先配置和data一樣大的空間data_new

        (2) 把data複製過去data_new

        (3) 開始把寫入data_new，目前除了writer以外沒有人可以使用data_new

        (4) 把指向data的pointer指向data_new，以後reader讀到的都是data_new

        (5) 等待所有持有舊資料的reader都離開RCU read side，writer free舊資料






--
   和seqlock的差別：

        seqlock當reader遇到writer寫入資料時，會強迫reader重讀一次，而RCU不會


   優點：當有writer正在寫入的時候，reader和writer可以平行計算，平行度提高

   缺點：cpoy會消耗CPU time，overhead提高

   注意：RCU在read的時候不會發生context switch，why?  這不是缺點 why?











--
Semaphore

   和spin lock很像，當資源被占用時，semaphore會讓process進入睡眠

   和spin lock的差別：
        (1) spin lock一定不會CTX_SW，semaphore一定會CTX_SW

        (2) 單一process持有鎖時間短的就用spin lock，持有鎖時間長的用semaphore

        (3) spin lock會讓process進入busy wait的狀態，semaphore則是sleep的狀態

        (4) critical section中有會引起suspend的程式碼的話就用semaphore
            想在中斷的情況下使用共享資源就用spin lock

   注意：因為是要用sleep的方式進行，使用busy loop的方式實作是錯誤的

         所以sleep的動作就不能寫在critical section裡面，必須先做釋放的動作

         在呼叫waiting queue的API做釋放的動作，所以必須把semaphore variable

         放在私有空間裡，於是可能會有race condition的問題
--

Counting semaphore

   鎖有N個，就是一次有N個process可以使用該資源

   如果鎖只有一個就叫做binary semaphore


r/w semaphore

   類似FIFO

   先送出semaphore要求的process可以先拿到semaphore

   但是當有一連串的reader就可以同時拿到semaphore

   不過同時間還是只可以有一個writer拿到


可以使用r/w spin lock或是r/w semaphore增加同步效能

--

稍微整理一下自己念到的東西，如果有錯誤的地方請指正<(_ _)>

還有有人知道為什麼RCU read的時候不會發生context switch不是缺點嗎

這邊我沒聽得很清楚








--
                        你們都是我的翅膀！         －Unlight－
 [Modified by swallow] From: 140.123.101.139 (2012/06/19 Tue 20:04:35)
＊iliketoeatdr 推薦：推薦這篇文章                             *|06/19 20:40 arnr
＊co 推薦：推薦這篇文章                                       *|06/21 02:42 arnr
＊h3615840 推薦：推薦這篇文章                                 *|06/21 07:43 vgQf
＊awa 推薦：推薦這篇文章                                      *|06/21 15:13 arnr
＊vfs80223 推薦：推薦這篇文章                                 *|06/21 23:07 omwl
＊yo6317 推薦：推薦這篇文章                                   *|06/21 23:19 ggza
＊yo6317 轉錄：本文已轉錄到某秘密看板                         *|06/21 23:20 ggza
＊lahaha 推薦：推薦這篇文章                                   *|06/22 06:29 ggzd
＊p1234567890 推薦：推薦這篇文章                              *|06/22 15:26 omkC

--