不用锁实现队列读写？

yuhang001

今日去面试，面试官说不用锁实现一个队列，这个队列只有一个进程读和一个进程写，应该怎样实现呢？

zliming

CPU在操作同一个内存地址时会锁住总线，这时不会中断，也就不会线程切换。

这样实现的

flyingtime

用signal符合要求不：
1、进程1写队列，直到队列满开始发送一个信号给进程2，此时进程1开始等待队列不为满的信号；
2、进程2开始时等待一个读的信号，当进程1发给它一个信号时它将读取队列并删除已读的节点，同时发送信号给进程1；
3、返回第一步

dreamice

原帖由 yuhang001 于 2009-5-5 23:32 发表
今日去面试，面试官说不用锁实现一个队列，这个队列只有一个进程读和一个进程写，应该怎样实现呢？

只有一个进程读，一个进程写，那就意味着不会出现并发的读，和并发的写。于是，写的往队列尾部写，读的从队列头部度；写的时候，先判断队列是否满了，如果没满，则写，写完了增加队列计数；读的时候，判断队列是否非空，非空的话，则读出来后，再减少队列元素计数。

daybreakcx

如果兼顾并行和防止队空的操作的话设置一个对首指针和一个队尾指针，为了防止并行使得数据错乱，我想使用链表结构
入队的时候申请空间，然后写入数据，再把对尾指针延后
出队的时候如果非空，先把队尾指针后移，这样操作类似于出队应该不会出现并行问题
同时对于同一个队列空间是互斥操作，因为空间都是链表独立的，一旦出队就访问不到了，而且入队的时候先申请空间填好然后才入队，也避免了两个写进程往队列同一块空间写，个人认为应该可以的
不对的请指正

[ 本帖最后由 daybreakcx 于 2009-5-6 10:15 编辑 ]

cookis

IPC 呀，用消息队列不行吗？

zliming

http://b.cnc.qzone.qq.com/cgi-bi ... imestamp=1241579164

我试写了一个，不知道会不会出错，10000的数字排的正确

daybreakcx

楼上效率不低啊，这么快就发日志了

虎皮尖椒

除非说的是可以使用隐含的锁或者自己实现锁，不然楼上几位的做法都不能解决并发冲突。

zliming

了解的比较模糊：
多CPU多核操作总线，在北桥芯片里面就已经固化了一个锁了。
对同一内存地址操作(读后写)已经是有lock free