a*****8
发帖数: 10 | 1 一个小时的phone interview
让实现一个支持多线程的hashmap （就是支持分布式系统的）
完全没有想法 挂了
给大家讨论一下 |
j*****y
发帖数: 1071 | 2 bless.
感觉就是对于 insert, find, delete 这些操作需要 lock吧？
【在 a*****8 的大作中提到】
: 一个小时的phone interview
: 让实现一个支持多线程的hashmap （就是支持分布式系统的）
: 完全没有想法 挂了
: 给大家讨论一下
|
M********5
发帖数: 715 | 3 这道题就是考你在实现push和pop的时候要用个thread_lock吧，应该，好像不需要很多多
线程的概念。。。不知道还有没有人有其他意见。。。 |
h****n
发帖数: 1093 | 4 其实就是对query，insert，delete操作加锁即可
注意不要对整个hashtable加锁，这样子并行化性能低下
要对每一次被indexed的slot加锁
【在 a*****8 的大作中提到】
: 一个小时的phone interview
: 让实现一个支持多线程的hashmap （就是支持分布式系统的）
: 完全没有想法 挂了
: 给大家讨论一下
|
w****x
发帖数: 2483 | 5 该不是要实现lock free的hash map吧 |
c*****a
发帖数: 808 | 6 是不是类似这样，不太懂系统
private Lock lock = new Lock();
public int delete(int x){
lock.lock();
int val = super.delete(x);
lock.unlock();
return val;
}
The lock() method locks the Lock instance so that all threads calling lock()
are blocked until unlock() is executed. |
M********5
发帖数: 715 | 7 这个怎么实现，加thread_lock的时候不就是
void insert(int num){
thread_lock();
map.insert(num);
thread_unlock();
}
没有注意语法的正确与否，只表达了idea。。。加锁的时候不是整个container的数据
都lock起来了吗？
【在 h****n 的大作中提到】
: 其实就是对query，insert，delete操作加锁即可
: 注意不要对整个hashtable加锁，这样子并行化性能低下
: 要对每一次被indexed的slot加锁
|
j*****y
发帖数: 1071 | 8 对 slot 加锁怎么做阿？ 我下面的code 感觉是对整个 hash table加锁了。
请指点，多谢 :)
class hashmap
{
int m;
pair table[m];
pthread_mutex_t lock;
int hashfunc(string);
public:
void insert(pair v)
{
pthread_mutex_lock(&lock);
int slot = hashfunc(v.first);
table[slot] = v;
pthread_mutex_unlock(&lock);
}
};
【在 h****n 的大作中提到】
: 其实就是对query，insert，delete操作加锁即可
: 注意不要对整个hashtable加锁，这样子并行化性能低下
: 要对每一次被indexed的slot加锁
|
h****n
发帖数: 1093 | 9 题目应该是要你自己设计一个hashmap而不使用stl里的hashmap
如果可以自己设计hashmap，简单的做法是申请一个mutex数组，数组的大小和
hashtable slot数目一致，一一对应
如果对并行性能要求不高那就另当别论了
【在 j*****y 的大作中提到】
: 对 slot 加锁怎么做阿？ 我下面的code 感觉是对整个 hash table加锁了。
: 请指点，多谢 :)
: class hashmap
: {
: int m;
: pair table[m];
: pthread_mutex_t lock;
: int hashfunc(string);
: public:
: void insert(pair v)
|
j*****y
发帖数: 1071 | 10 明白意思了, 需要一对一的 mutex来锁定相应的 slot. 如果只有一个 mutex 的话，
就只能锁定整个 table了吧？ 多谢 :)
【在 h****n 的大作中提到】
: 题目应该是要你自己设计一个hashmap而不使用stl里的hashmap
: 如果可以自己设计hashmap，简单的做法是申请一个mutex数组，数组的大小和
: hashtable slot数目一致，一一对应
: 如果对并行性能要求不高那就另当别论了
|
|
|
M********5
发帖数: 715 | 11 多谢指点，明白了。。。
【在 h****n 的大作中提到】
: 题目应该是要你自己设计一个hashmap而不使用stl里的hashmap
: 如果可以自己设计hashmap，简单的做法是申请一个mutex数组，数组的大小和
: hashtable slot数目一致，一一对应
: 如果对并行性能要求不高那就另当别论了
|
j*****y
发帖数: 1071 | 12 还有一个问题， 对于 queue 里面的操作， 能做到对于 slot 来锁定吗？ 感觉
要复杂些， 因为 dequeue 和 enqueue 有依赖关系.
【在 h****n 的大作中提到】
: 题目应该是要你自己设计一个hashmap而不使用stl里的hashmap
: 如果可以自己设计hashmap，简单的做法是申请一个mutex数组，数组的大小和
: hashtable slot数目一致，一一对应
: 如果对并行性能要求不高那就另当别论了
|
h****n
发帖数: 1093 | 13 queue和这个问题不太一样，hash里面的slot是independent所以才能这么做，queue要
对整个queue加锁的，所能优化的地方有两点，第一个是尽量降低临界区也就是锁的时
间，第二个就是要采用semaphore同步机制来避免queue为空的时候pop操作busy loop，
queue满的时候push操作busy loop。具体可参考semaphore如何解决经典的生产者消费
者问题
【在 j*****y 的大作中提到】
: 还有一个问题， 对于 queue 里面的操作， 能做到对于 slot 来锁定吗？ 感觉
: 要复杂些， 因为 dequeue 和 enqueue 有依赖关系.
|
y*******g
发帖数: 6599 | 14 多线程hashmap 和支持分布式系统的DHT区别很大吧？
多线程concurrenthashmap就可以了。 主要idea就是分bucket来lock
【在 a*****8 的大作中提到】
: 一个小时的phone interview
: 让实现一个支持多线程的hashmap （就是支持分布式系统的）
: 完全没有想法 挂了
: 给大家讨论一下
|
h****n
发帖数: 1093 | 15 agree，这两个问题是有区别，分布式的话hash table要分配到各个机器上，而不是整
个存在一个机器里面，之间需要协议来保证coherency 不过感觉电面的话分布式应该不
会让你设计，这可不是十几二十分钟能搞定的，顶多说说idea
【在 y*******g 的大作中提到】
: 多线程hashmap 和支持分布式系统的DHT区别很大吧？
: 多线程concurrenthashmap就可以了。 主要idea就是分bucket来lock
|
c********t
发帖数: 5706 | 16 难道不是简单的synchronized就行吗？如下：
public class NewHashMap extends HashMap {
public synchronized void put(K a, V b){
super.put(a,b);
}
public synchronized V get(K a){
return super.get(a);
}
}
【在 a*****8 的大作中提到】
: 一个小时的phone interview
: 让实现一个支持多线程的hashmap （就是支持分布式系统的）
: 完全没有想法 挂了
: 给大家讨论一下
|
c********t
发帖数: 5706 | 17 哦，我也后知后觉了。多谢！
【在 h****n 的大作中提到】
: 题目应该是要你自己设计一个hashmap而不使用stl里的hashmap
: 如果可以自己设计hashmap，简单的做法是申请一个mutex数组，数组的大小和
: hashtable slot数目一致，一一对应
: 如果对并行性能要求不高那就另当别论了
|
j*****y
发帖数: 1071 | 18 谢谢。 刚才看了 那个 consumer/producer 的 wiki, 对于 queue而已就是要对于
queue的size用 semaphore, 是吧?
【在 h****n 的大作中提到】
: queue和这个问题不太一样，hash里面的slot是independent所以才能这么做，queue要
: 对整个queue加锁的，所能优化的地方有两点，第一个是尽量降低临界区也就是锁的时
: 间，第二个就是要采用semaphore同步机制来避免queue为空的时候pop操作busy loop，
: queue满的时候push操作busy loop。具体可参考semaphore如何解决经典的生产者消费
: 者问题
|
h****n
发帖数: 1093 | 19 其实两个binary semaphore就足够了，一个sem_full另外一个是sem_empty 初值都为0
pop操作只有在检测到queue为空的时候才去wait(sem_full)，当push一个新元素的时候
都会去notify一个等待的线程
push操作检测queue为满的时候做类似操作
如果光用mutex的话，当queue为空的话，做pop操作的线程即使拿到mutex每次都检测到
queue为空，这样子就做了很多无谓的工作，还占用了时间片
而用同步机制的话，这种情况下会被scheduler直接放进pending list里面直到被
notify避免了cpu的浪费
【在 j*****y 的大作中提到】
: 谢谢。 刚才看了 那个 consumer/producer 的 wiki, 对于 queue而已就是要对于
: queue的size用 semaphore, 是吧?
|
