算法高手请进.队列链表问题.(100分)

J

jingtao

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-02

• #1

建立一个链表,摄像头不断主动产生数据,我们开一个线程,把数据添加到链表.然后另外一个线程不断从链表里面取出数据压缩传输.现在是使用了临界区,意思是添加数据的时候,处理线程阻塞.反之亦然.但是,这样会发生问题:
1:读数据的时候,会导致写数据线程阻塞,从而发生掉包.
2:写数据的时候,会导致读数据线程阻塞,从而导致画面发生停顿.
由于数据产生方是主动产生,所以无法适用生产消费者算法.问有没有现成的解决算法?

 

O

OopsWare

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-02

• #2

如果硬件设备根本跟不上实时捕捉和压缩，那不管是循环还是线程，都不可能实现你上面的要求。如果硬件能充分满足你上面要求，那就基本不会出现你上面所说的情况...

因为上面所说的是时间主要消耗在捕捉时的传输，和图像的压缩。真正接触的临界区的只有链表节点增删的微不足道的一瞬。

视频的压缩不可能是一帧帧去压的，通常一个换成区会是几秒种，也就是近百帧的图像数据，在这个压缩过程中，如果都是线程的 while(true) do ... 去做，这之间不可能留出足够的CPU的IDLE去执行捕捉的数据传输，如果你能在压缩过程的循环中，没几十毫秒Sleep一下，你说的情况应该也不会出现了。

 

J

jingtao

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-02

• #3

杜兄,情况不是的.硬件产生的缓冲肯定是足够速度的.可能我表达不清楚(实际上是一个程序同时处理几个摄像头)
是这样的:我的链表元素是结构,结构里面又包括联合.添加数据的时候,我需要遍历所有元素,找到相同的组(例如P帧,时间凿之类),然后添加.否则则新建一结构再添加.所以遍历的时候会消耗时间.而处理数据的时候,我是取出来处理后释放该内存.因为处理也需要时间,所以卡住.
我的想法是,是否有一种算法,类似有个中间缓冲区.得到数据后先丢到这里.而处理线程则从中间取?

 

金

金卡绣球jk8.com

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-03

• #4

循环队列

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-03

• #5

关于队列数据的读写，我以前写过一点思路，请看：
socket通讯的问题 http://www.delphibbs.com/delphibbs/dispq.asp?lid=554437

看了您的说明，我认为“新建结构”以及“释放内存”似乎是频繁发生的，而内存的分配
以及回收的代价是比较高的，相比较而言，遍历所有链表元素只是读了几十次内存而已，时
间开销不会大。
建议这样做：读写缓冲是肯定要的，另外，为了不因为频繁的申请、释放内存而产生大量
的时间资源浪费，应该开辟一个专门的处理缓冲，结构可以参考读写缓冲。

 

A

Another_eYes

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-04

• #6

如果你想解决互斥操作的时间太长， 那么这里提供一点思路：
将你的互斥锁从锁队列改成锁帧数据，即在每帧数据结构中添加一个独立的互斥锁和一个删除标记，在删除队列前锁住该帧与前后帧，然后修改链表指向并置位删除标记就可以解锁了（注意需要保留本帧数据中的原始链表指向），同时被删除帧数据并不马上释放而是放入一个延时队列中隔一段时间后再释放。
遍历时只需要依次加锁当前帧即可（如果当前帧有删除标记只要无条件移动到下一帧即可，由于有延时释放的机制，所以不会出现访问已删除的帧数据而产生内存异常）,这样可以将冲突的可能性降至最低。 不会出现你现在模型中由于要播放第一帧锁住队列而造成插入第100帧的操作陷入等待。
当然缺点也很明显，就是资源占用大幅度上升， 不过这些都在可以忍受的范围内（至少windows系统下同时申请超过10000个互斥量不会有任何问题。 而你的内存占用也不过比正常情况下多占了1-2秒运行所产生的内存）

 

J

jingtao

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-05

• #7

准备使用类似
http://www.codeproject.com/csharp/circularbuffer.asp
的环形缓冲

 

A

Another_eYes

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-05

• #8

环形队列只适用于先入先出或先入后出有最大数量限制的队列，不适用于存在随机插入或随机删除的队列

 

Q

QQ在线

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-06

• #9

分配/回收内存，在多线程下，系统默认都是需要锁定一个CS，再加上自定义的临界锁，速度更慢，而且我用CS，好像是经常出问题，特别在读写频敏的时候。所以，我是尽量减少自定的锁/互斥资料的使用。
一个共用的队列，需要给两个线程使用，不知下面的方法可否使用了：
Read线程:
有数据时，不断取出一块内存，然后使用PostThreadMessage或其它通知性手段通知Write线程，并加入本身的一个LIST中，标志该数据包为READ出状态
Write线程：
得到通知后，通知PeekMessage其它手段，得到该数据包（Pointer(Msg.LParam)），然后进行处理，处理完后，置标志为处理状态，并再次通知READ线程，该包我已做完处理，可以丢弃。

这样，READ/WRITE处理的数据包单独工作，而且没有所谓的共用队列，队列只在READ线程中需要，用来保存内存的地址，防止READ线程有数据，但没有给WRITE线程处理进行的一些保护措施。

嘿，只是猜猜。未经试验。

 

K

kaoleoloi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-08

• #10

帮顶！

╭=========================================╮

80G海量源代码,控件，书籍全免费狂下不停！

http://www.source520.com

╰=========================================╯

 

J

jingtao

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-02-26

• #11

多人接受答案了。