一个关于加锁的策略问题，求较好的思路
现在有这样一种应用情况:有一个container(比如是std::map)，用来保存多个元素。由于这个container会被多个线程访问，因此需要进行加锁。
现在的问题是:多个线程的访问分为两种类型--一种是对container的访问如增、删元素；另外一种是对元素的访问，会修改元素的属性。
目前的实现方法是：对整个container加锁。即不管是要增删元素还是获取元素去修改元素的属 性。
这种方式的缺陷是极大地降低了并发性。因为大部分的访问实际上是获取元素去修改元素的属性。
但若对每个元素都包含一个锁，有可能存在的潜在的问题是：在windows平台上相当于要创建元素个数个Mutex，而元素个数会非常多，这有可能特别浪费资源；
且container层面上的锁仍然也是需要的。这种方式会导致为了访问元素且改写元素的属性，首先要获得container层面上的锁，接着再获得元素的锁方可。
看看大家有没有什么好的思路？谢谢！
问题点数：0、回复次数：32Top
1 楼somedummy（某人马甲）回复于 2005-01-01 14:30:41 得分 0
继承map，然后重写map的行为，加上锁的功能
要么再创建一个map，里面保存那些被锁住的元素的indexTop
2 楼beyondtkl（大龙驹<*好久没来了,兄弟们好吧。*>）回复于 2005-01-01 16:27:16 得分 0
是的 看你要求的精确度了
比如
map里面
1 2 3 4 5
某个线程只操作1 而另一个线程操作5(当然 这里的操作暂不涉及到删除) 那么 你这样的策略就是以下标为单位了
而如果一个线程修改1的某一个属性A 另一个线程读取<修改>1的另一个属性B 那么从理论上来说 是应该允许的 不过这样 你的策略 模型 就要复杂很多了...Top
3 楼xorong（勤劳与智慧）回复于 2005-01-01 17:47:52 得分 0
hoho，和数据库的表级锁与行级锁是一个道理嘛Top
4 楼xorong（勤劳与智慧）回复于 2005-01-01 17:48:52 得分 0
我觉得应该在元素里加一个属性标志是否本元素已经上锁了Top
5 楼westernsoft（）回复于 2005-01-02 23:01:45 得分 0
顶一下，继续寻求答案。。。。Top
6 楼somedummy（某人马甲）回复于 2005-01-02 23:13:15 得分 0
回复人： xorong(普渡众生) ( ) 信誉：97 2005-01-01 17:48:00 得分: 0
我觉得应该在元素里加一个属性标志是否本元素已经上锁了
=========================================
楼主说了：
但若对每个元素都包含一个锁，有可能存在的潜在的问题是：在windows平台上相当于要创建元素个数个Mutex，而元素个数会非常多，这有可能特别浪费资源；
Top
7 楼gameboy007（WoHaHa-WaHaHaHaHa）回复于 2005-01-03 02:00:22 得分 0
I am MacOSX programmer, on the Mac is:
example
The element class is
class element : public locker { ... };
struct locker {
locker():pointer_to_process_(0){}
bool isReady( void* process ) const
{
if (pointer_to_process_ && pointer_to_process_ != process)
return false;
return static_cast<bool>(pointer_to_process_ = process);
// always return true, if process is valid.
}
mutable void* pointer_to_process_;
};
running ...
void* current_process = getCurrentProcessHandler();
std::map<int, element>::iterator begin(container.begin());
std::map<int, element>::iterator end(container.end());
while (begin != end) {
if (begin->isReady(current_process)) {
// Do someting
} else {
// Element locked
}
++begin;
}
Simple case, don't need mutex.
Top
8 楼gameboy007（WoHaHa-WaHaHaHaHa）回复于 2005-01-03 02:03:11 得分 0
struct locker {
locker():pointer_to_process_(0){}
bool isReady( void* process ) const
{ ... }
void unlock() { pointer_to_process_ = 0; }
}
Top
9 楼Mephisto_76（(望美人如梦)）回复于 2005-01-04 08:43:51 得分 0
做一个代理Proxy，重载operator=()，对其实际指向的元素进行操作，按照写时拷贝的策略实现写时加锁，不知可不可以。Top
10 楼caslwzgks（梦想家）回复于 2005-01-04 08:48:55 得分 0
1、对容器的操作是非常快的，一般不会成为系统瓶颈。
2、要想使容器是多线程安全的，最安全的做法就是对删除、添加及修改元素都进行加锁。
3、对于容器，如果不同线程在“同一时刻”不可能操作同一个元素（修改元素属性），那么对于元素可以不加锁保护，只需要在取出元素时进行同步即可。这样就可以保证效率和线程安全。其实大多数在多线程环境下的容器都是这程使用模式。
Top
11 楼caslwzgks（梦想家）回复于 2005-01-04 09:01:17 得分 0
典型的任务队列实现：
g_Q是某一全局任务队列。
产生任务线程:
#define MAX_SIZE 1000
template<class T,class M,class C>
class TaskQueue{
public:
typedef typename T value_type;
typedef typename M MUTEX_TYPE;
typedef typename C CONDITION_TYPE;
typedef typename std::quque<T> QUEUE_TYPE;
private:
QUEUE_TYPE m_datas;
MUTEX_TYPE m_mutex;
CONDITION_TY m_con;
public:
void push(value_type ele){
MUTEX_TYPE::scoped_lock guard(m_mutex);
if( m_datas.size() >= MAX_SIZE )
m_con.wait( m_mutex );
m_datas.push( ele );
m_con.notify_all();
}
value_type & pop(){
MUTEX_TYPE::scoped_lock guard(m_mutex);
if( m_datas.empty() )
m_con.wait( m_mutex );
value_type & ret = m_datas.front();
m_datas.pop_front();
m_con.notify_all();
return ret;
}
};
Top
12 楼BluntBlade（信仰迷离·重构之道，在于Redo/Undo之间）回复于 2005-01-04 09:05:11 得分 0
实现两种不同的锁，然后只读的共享同一个锁，修改的线程各自独占一个锁。Top
13 楼babysloth（小懒虫虫）回复于 2005-01-04 17:43:39 得分 0
个人觉得首先看看应用背景是什么，读取多还是修改多。一般来说，我觉得加个读写锁可能比较合适。Top
14 楼laomai（老迈）回复于 2005-01-04 17:44:34 得分 0
接着喊人来讨论，呵呵Top
15 楼nicknide（封月翔天）回复于 2005-01-04 17:46:26 得分 0
补充，如果不需要进程间共享，那么可以用CRITICAL_SECTION来做，不占用系统核心对象，快
只有4个函数：
InitalizeCriticalSection
EnterCriticalSection
LeaveCriticalSection
DeleteCriticalSectionTop
16 楼wingfiring（非典型秃子）回复于 2005-01-04 17:52:34 得分 0
空间（资源）和时间效率之间基本上一对矛盾，恐怕难有万金油式的解决方案，如果真的有高要求，最终可能要回到比较高层的问题域，寻找新的思路。
我想到的一个办法是：
1。对容器的操作通过代理来完成
2。如果是读操作，代理会检查要访问的元素，并设置读锁。
3。如果是写操作，代理会检查要访问的元素，并设置排他锁Top
17 楼nicknide（封月翔天）回复于 2005-01-04 17:58:54 得分 0
恩，关于读锁和写锁，已经有很多成熟的策略呢，这个也是间接性代理的一种重要的使用方法，呵呵（感觉说了等于没说）Top
18 楼ihsgnep（石头－>信心最重要 努力是王道）回复于 2005-01-04 19:22:01 得分 0
学习Top
19 楼westernsoft（）回复于 2005-01-06 12:26:25 得分 0
continue.....Top
20 楼somexing（somexing）回复于 2005-02-16 20:11:02 得分 0
每个元素都包含一个锁，有可能存在的潜在的问题是：在windows平台上相当于要创建元素个数个Mutex，而元素个数会非常多;
而且有可能发生死锁
如果在container层面上的锁,每个线程都要排队才能读取一个数据,效率会比较低'
可以读时候防止写,写的时候防止读,典型的reader / writer问题Top
21 楼sandrowjw（我的小猫照片给弄坏了，心都碎了）回复于 2005-02-17 17:35:12 得分 0
容器锁级别应该高一些，元素的锁可以一组元素共享一个锁（用spin-lock效率会高一些）。
据说用“比较-交换”的硬件原语的话，元素级的锁可以不要，这样可以大大提高效率，不过我没有用过xhgcmp，里面有什么门道不太了解。
Top
22 楼sandrowjw（我的小猫照片给弄坏了，心都碎了）回复于 2005-02-17 17:36:24 得分 0
可以看看
http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/
我还没来得及看Top
23 楼andy_show（）回复于 2005-02-17 18:36:05 得分 0
可以在系统提供的同步对象的基础上实现一个多个读者多个写者的锁，采用如下策略
1。写的时候不允许读，读的时候不允许写
2。同时只允许一个线程写，同时允许多个线程读
3。注意读写的优先级，避免读者或写者饥饿的情况
在linux/unix系统上,因为有condition对象，实现这样的功能会更简单，在windows上会稍微复杂一点。
不过可以参考一下ACE,我记得里边好像有这样的实现。
Top
24 楼bill_li（班加罗尔）回复于 2005-02-21 03:17:34 得分 0
顶一下Top
25 楼squin（*squin*）回复于 2005-03-12 16:45:23 得分 0
建议看看《面向模式的软件体系结构》卷2，具体问题具体分析，寻找一个平衡点。
Top
26 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-03-12 17:04:21 得分 0
upTop
27 楼mengxiangfengwz（小江）回复于 2005-03-12 17:17:18 得分 0
andy_show() ( ) 信誉：100 :
写的不错,不过我认为最好再加上一点是:
一个读者,两个写者的锁，采用如下策略
1.写的时候不允许读，读的时候不允许写
2.同时只允许一个线程写，同时允许多个线程读
3.注意读写的优先级，避免读者或写者饥饿的情况
*4.对container设一读锁一写锁,另外对container的所有元素只设一个循环锁,对一个元素加完锁解锁,再对下一个元素进行加锁解锁,直至所有元素.。Top
28 楼ThinkX（秋天的树）回复于 2005-03-17 13:24:23 得分 0
看看Read/Write Lock的思路，N个线程可以并发Read，而只有一个线程可以Write。Top
29 楼fengfeng2003（）回复于 2005-03-17 19:04:59 得分 0
应该是两个锁
类似数据库中的s锁和x锁Top
30 楼Hewwatt（Hewwatt）回复于 2005-04-17 20:29:54 得分 0
另一种思路：
只在container上加一个增删锁。将读及修改元素的过程拆解为:
1. delete from container.
2. read/modify element.
3. add to container.
好处是：只要container的实现对于增删操作是O(1)复杂度的，就基本没有多少负载
坏处是：不支持多个并发的读写操作
大言不惭一句： 我看不到有什么非实时的应用系统，必须支持多个并发的读写操作。只要设计合理，完全可以将并发的读写操作经序列化以后异步执行。
Top
31 楼bing_huo（我是一个演员！）回复于 2005-04-18 22:00:34 得分 0
继承一下 重新包装标准容器中需要用到的操作 并把操作分类 按你的规则 把需要锁的锁上Top
32 楼mythlee（mythlee）回复于 2005-04-30 18:59:42 得分 0
首先要搞清楚影响并发度的瓶颈在哪里？向容器中加入或删除元素应该是很快的，应该不会成为系统的瓶颈，然后是设置属性，如果只是即时设置，应该也没问题；最麻烦的是先要加锁，再把该元素的属性取出来，禁止其他线程的访问，然后通过数据库、网络等可能会阻塞的操作使用属性或更新属性，最后返还属性，解锁。
我觉得，理论上锁的个数同并发的线程个数一样多(或者同并发访问的元素个数一样多)就可以实现上述功能了。首先设置一个全局互斥锁，线程要访问容器必须获得该锁，然后给每个元素都设置标记，标明其是否在使用，若元素未使用标记为0，则进行删除或使标记加1访问属性，然后解锁；若该元素正在使用则线程将自己的句柄或标示连同一个初始值为0的信号量塞到一个全局队列里，然后解全局锁，等待信号量。每个线程在使用完属性后，重新获得全局锁，使相应元素标记减1，若标记不为0，则去队列找到等待访问该元素的线程，唤醒，然后解锁退出。
Top
