标题: 环形队列 [打印本页]

作者: 51黑tt    时间: 2016-3-5 17:41
标题: 环形队列
环形队列有一个head指针,有一个tail指针,假设我们用一个环形队列来表示一组资源,
有一个线程产生资源并往队列里发送,另外一个线程从队列里取资源,一般的情况下实现
这样一个功能需要用到OS的互斥/事件/信号量API,在两个线程运行都很快时这些OS的API会带来
比较大的系统开销,怎么样尽可能的减少OS的API调用呢,下面是一个简单的实现方法(假设只有两个
线程,一个往队列里写数据,一个从队列里读数据):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 指针的修改不需要保护,应为分别只有一个线程会修改他们,
put线程会读取tail,修改head, get线程会读取head, 修改tail。
代码中最关键的是goto语句,防止出现误等的情况,比如刚开始时,队列为空,
put线程先运行,该线程会调用increase_semophore语句,然后get线程开始运行,
get线程第一次会取走一个element, 然后get线程继续运行,当它试图取第二个element时,
发现队列为空,于是等待,这时wait_semophore是会成功的,因为put线程之前调用了
increase_semophore,虽然这时get线程会错误的等到资源信号量,但它会跳到try_get标签
处重新检查队列是否为空,这样就避免了出现错误的结果。同时经过仔细分析,两个线程不会死锁。
这个队列实现机制的优点是最大的避免了调用OS的互斥/事件/信号量API,仅在必须的时候调用
wait_semophore/increase_semophore API,提高了运行效率。






欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1