<form id="8u6mm"><address id="8u6mm"></address></form>

_{<tbody id="8u6mm"><rt id="8u6mm"></rt></tbody>}

<ol id="8u6mm"><li id="8u6mm"></li></ol>

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

---

作者: 51黑tt    時(shí)間: 2016-3-5 17:41
標(biāo)題: 環(huán)形隊(duì)列
環(huán)形隊(duì)列有一個(gè)head指針，有一個(gè)tail指針，假設(shè)我們用一個(gè)環(huán)形隊(duì)列來表示一組資源，
有一個(gè)線程產(chǎn)生資源并往隊(duì)列里發(fā)送，另外一個(gè)線程從隊(duì)列里取資源，一般的情況下實(shí)現(xiàn)
這樣一個(gè)功能需要用到OS的互斥/事件/信號量API，在兩個(gè)線程運(yùn)行都很快時(shí)這些OS的API會帶來
比較大的系統(tǒng)開銷，怎么樣盡可能的減少OS的API調(diào)用呢，下面是一個(gè)簡單的實(shí)現(xiàn)方法(假設(shè)只有兩個(gè)
線程，一個(gè)往隊(duì)列里寫數(shù)據(jù)，一個(gè)從隊(duì)列里讀數(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)為分別只有一個(gè)線程會修改他們，
put線程會讀取tail，修改head, get線程會讀取head, 修改tail。
代碼中最關(guān)鍵的是goto語句，防止出現(xiàn)誤等的情況，比如剛開始時(shí)，隊(duì)列為空，
put線程先運(yùn)行，該線程會調(diào)用increase_semophore語句，然后get線程開始運(yùn)行，
get線程第一次會取走一個(gè)element, 然后get線程繼續(xù)運(yùn)行，當(dāng)它試圖取第二個(gè)element時(shí)，
發(fā)現(xiàn)隊(duì)列為空，于是等待，這時(shí)wait_semophore是會成功的，因?yàn)閜ut線程之前調(diào)用了
increase_semophore，雖然這時(shí)get線程會錯(cuò)誤的等到資源信號量，但它會跳到try_get標(biāo)簽
處重新檢查隊(duì)列是否為空，這樣就避免了出現(xiàn)錯(cuò)誤的結(jié)果。同時(shí)經(jīng)過仔細(xì)分析，兩個(gè)線程不會死鎖。
這個(gè)隊(duì)列實(shí)現(xiàn)機(jī)制的優(yōu)點(diǎn)是最大的避免了調(diào)用OS的互斥/事件/信號量API，僅在必須的時(shí)候調(diào)用
wait_semophore/increase_semophore API，提高了運(yùn)行效率。

---

歡迎光臨 (http://www.torrancerestoration.com/bbs/)

Powered by Discuz! X3.1

_{<tbody id="byswz"></tbody>}