这两个线程唯一可能冲突的时候是它们同时想要访问同一行/列。因此,我决定为每行/列使用一个简单的互斥锁即可。
这是我第一次在C/C++中使用线程,我想按照规范来做。我有两个问题:
1. 如何生成这些线程?这更多是一个语言问题。 2. 如何尽可能高效地实现锁定?如果存在冲突,则请求线程将排队等待资源被释放。但是,如何实现唤醒呢?我可以使用循环轮询内存位置,但那不够优雅。理想情况下,我认为基于中断的方法最好。
C++本身不提供任何线程支持。在Windows上,您可以使用CreateThread
。在UNIX上,您可以使用POSIX线程(pthreads)。
通常情况下不需要实现自己的并发原语。例如,在Windows上,您可以使用CreateMutex
创建互斥对象,并使用WaitForSingleObject
等待直到它被释放。
我可以相对简单地回答第一部分 - 这取决于您的平台。如果您正在使用Win32 API,请查看http://msdn.microsoft.com/en-us/library/ms682453%28VS.85%29.aspx "CreateThread"函数并阅读示例。我在Windows上多线程阅读的书是这本:http://www.amazon.co.uk/Windows-PRO-Developer-Jeffrey-Wintellect-Christophe/dp/0735624240,它不仅涵盖了使用CreateThread和其他选项BeginThread进行线程处理,还包括锁定和信号量等。
如果您正在使用Linux,则需要通过pthread函数使用POSIX线程,请参见http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html作为示例。
一个关于pthreads的代码示例看起来像这样 - 注意,我留下了从同一函数创建多个线程的功能,即callocing pthread_t变量数组。你可能不需要这个。
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <malloc.h>
void *thread_function(void *arg)
{
/* DO SOME STUFF */
/* Exit Thread */
pthread_exit();
}
int main(int argc, char** argv)
{
/* variables */
int retval = 0;
/* array of thread handles */
pthread_t* thread_handle = (pthread_t*) calloc(1, sizeof(pthread_t));;
/* create function - fork() for threads */
retval = pthread_create(&thread_handle[0], NULL, thread_function, NULL);
/* DO SOME STUFF */
/* join - wait for thread to finish */
pthread_join(thread_handle[0], NULL);
return EXIT_SUCCESS;
}
使用gcc 文件名 -o 可执行文件名 -lpthread
进行编译
你确定你需要一个矩阵吗?根据你所描述的情况,似乎是队列。队列的锁定相对简单:当任何人读取或写入时,它们会通过pthread_mutex获取排他锁。(除非你真的知道你有性能问题,否则不要使用读写锁等)
当然,不需要任何中断。
从boost threads.开始。
至于您的设计,似乎您已经决定允许任何线程对整个矩阵进行随机访问。
如果可能的话,最好想出如何将矩阵的部分责任划分给特定的线程。每次访问单元格都需要锁定会成为瓶颈。
Thomas讲解了线程库。如果你有操作系统,唯一需要处理中断处理程序的原因是没有操作系统提供的线程控制。
关于锁定的事情,我要警告你小心不要死锁。您需要按行和列进行锁定,因此每行和每列都需要自己的互斥锁。(实际上,读者/写者锁对性能来说更好,但您必须更加小心死锁和竞态条件。)
确保您始终以一致的顺序获取和释放锁定;您不希望一个线程锁定第N行,然后阻止锁定第K列,然后已经锁定第K列的线程决定锁定第N行并被阻止,从而给您两个阻塞的线程和什么也没有发生(请播放John Woo手枪对峙场景)。
这需要一些花式操作,但总体上锁定资源的数量非常低。还有其他人能做得更好吗(或者找到我的方案的反例)?
另请注意,将矩阵分成行和列有些随意。如果在此方案下发生了太多争用,您应该将行细分为两半(例如)。
trylock
互斥锁。如果失败,释放写锁,(阻塞)获取并释放互斥锁(以确保其他线程获得读锁),回到获取写锁。这会影响性能:v(。感觉像是需要为每列都添加一个信号的适当实现。 - Potatoswatter如果为每行/列设置一个互斥锁,当行写线程和列读线程访问行/列交叉点处的元素时,会出现竞争条件。如果矩阵很大,你将需要许多互斥锁。我不确定每个操作系统都能提供成千上万的互斥锁。
听起来一个线程安全的生产者-消费者队列会是你问题的更好解决方案。看看Intel的Thread Building Blocks(TBB)库。我发现,当你使用数据流范例对程序进行建模时,多线程变得更加容易。
如果你想要减少大型稀疏矩阵的内存占用,请查看Boost.uBlas。它有一个sparce_matrix
模板类,使用Map按索引关联存储元素。