|
|
环形队列有一个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，提高了运行效率。
|
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
