wwwxxx国产_337p日本欧洲亚洲大胆张筱雨_免费在线看成人av_日本黄色不卡视频_国产精品成熟老女人_99视频一区_亚洲精品97久久中文字幕_免费精品视频在线_亚洲色图欧美视频_欧美一区二三区

標(biāo)題: 環(huán)形隊列 [打印本頁]

作者: 51黑tt 時間: 2016-3-5 17:41
標(biāo)題: 環(huán)形隊列
環(huán)形隊列有一個head指針，有一個tail指針，假設(shè)我們用一個環(huán)形隊列來表示一組資源，
有一個線程產(chǎn)生資源并往隊列里發(fā)送，另外一個線程從隊列里取資源，一般的情況下實現(xiàn)
這樣一個功能需要用到OS的互斥/事件/信號量API，在兩個線程運行都很快時這些OS的API會帶來
比較大的系統(tǒng)開銷，怎么樣盡可能的減少OS的API調(diào)用呢，下面是一個簡單的實現(xiàn)方法(假設(shè)只有兩個
線程，一個往隊列里寫數(shù)據(jù)，一個從隊列里讀數(shù)據(jù)）：volatile u32 head = tail = 0;
os_semophore sem;
bool init()
{
sem.max_val = 1;
sem.init_val = 0;
return true;
}
void put()
{
bool need_wait = need_wake_putter = false;
while (1) {
try_put:
      need_wait = need_wake_putter = false;
      if (tail == ((head + 1) % len)  //full
         need_wait = true;
      else if (tail == head) //empty
         need_wake_getter = true;

      if (need_wait) {
         wait_semophore(sem);
         goto try_put;
      } else {
         put_element;
         head = (head + 1) % len;
         if (need_wake_getter)
            increase_semophore(sem);
      }
}
}
void get()
{
bool need_wait = need_wake_putter = false;
while (1) {
try_get:
      need_wait = need_wake_putter = false;
      if (head == tail) //empty
         need_wait = true;
      else if (tail == ((head + 1) % len)  //full
         need_wake_putter =true;

      if (need_wait) {
         wait_semophore(sem);
         goto try_get;
      } else {
         get_element;
         tail = (tail + 1) % len;
         if (need_wake_putter)
            increase_semophore(sem);
      }
}
}
head 與 tail 指針的修改不需要保護(hù)，應(yīng)為分別只有一個線程會修改他們，
put線程會讀取tail，修改head, get線程會讀取head, 修改tail。
代碼中最關(guān)鍵的是goto語句，防止出現(xiàn)誤等的情況，比如剛開始時，隊列為空，
put線程先運行，該線程會調(diào)用increase_semophore語句，然后get線程開始運行，
get線程第一次會取走一個element, 然后get線程繼續(xù)運行，當(dāng)它試圖取第二個element時，
發(fā)現(xiàn)隊列為空，于是等待，這時wait_semophore是會成功的，因為put線程之前調(diào)用了
increase_semophore，雖然這時get線程會錯誤的等到資源信號量，但它會跳到try_get標(biāo)簽
處重新檢查隊列是否為空，這樣就避免了出現(xiàn)錯誤的結(jié)果。同時經(jīng)過仔細(xì)分析，兩個線程不會死鎖。
這個隊列實現(xiàn)機制的優(yōu)點是最大的避免了調(diào)用OS的互斥/事件/信號量API，僅在必須的時候調(diào)用
wait_semophore/increase_semophore API，提高了運行效率。

歡迎光臨 (http://m.izizhuan.cn/bbs/)