发帖数: 1 | 1 我看了看RCU，哥们你真是胆子大，居然敢在面试的时候拿这个出来，
However,RCU does not have any write side primitive which looks traditional
write lock. That is, their update side primitives need other locks to keep
threads safe.
http://www.cs.nyu.edu/~lerner/spring11/proj_rcu.pdf page 6 & 7
就是说，RCU只允许一个写线程，一个一个地写。如果有多于一个的写线程，必须要使
用另外的锁进行同步。具体的source code这个slide里面都有。
所以RCU依赖于其他的resource锁定方式，根本不可能是lock free的。我一直说，有些
theoretical junk是依赖于unreal的假设，根本不实用。
"
我一直强调的是绝对不可以在hashtable的设计(尤其在面试的时候)用copy-on-write，
一定要用lock。
第一点：最基本的常识，只能有... 阅读全帖 |
|
T*****g
发帖数: 1306 | 2 哥们你做过synchronization相关的工作么？你知道你一个bucket有100个element，多
线程同时写在mutex上要等多久么？不过你提的这个throughput可能用mutex也能达到，
只能说你是没见过高性能的salable hashtable
不要误导人了，谁告诉你要copy一整条bucket来做copy on write？（有人提到RCU了，
RCU就可以做）。RCU的难点只在于resize的时候不好处理，不过已经有人把这个问题解
决了。
如， |
|
m****e
发帖数: 255 | 3 Do they offer stock options, RCU etc? I say if in downtown Mahattan, you should have at least 80k for base, then + RCU + benefits. If the RCU and benefits are limited, consider 90k at least. |
|
发帖数: 1 | 4 我一直强调的是绝对不可以在hashtable的设计(尤其在面试的时候)用copy-on-write，
一定要用lock。
第一点：最基本的常识，只能有一个thread来写，比如hashtable的值用作counter。用
copy-on-write，立马废掉。
第二点: 更进一步的synchronization，是要保证global ordering。比如狗家股票real
time streaming, 绝对不可以11:11:11.002的报价先写入，然后11:11:11.000的报价
后写入。这就有不少的实现方法。这个已经超出了hashtable面试的范围，但是如果你
想exceed expectation，mention this.
很多刚毕业的菜鸟喜欢在面试的时候胡吹一些"advanced technology"以达到shock-and
-owe的效果，use it wisely。比如下面这个就非常的un-wise：
“你知道你一个bucket有100个element，多线程同时写在mutex上要等多久么？不过你
提的这个throughput可能用mutex也能达到”
听着都能让... 阅读全帖 |
|
发帖数: 1 | 5 在这里争哪种实现效率更好没有意义，不如约战github，想用rcu的用rcu，用CoW的用
CoW，用锁的用锁，各自实现几个，然后跑个分，talk is cheap, show LZ the code |
|
T*****g
发帖数: 1306 | 6 利用RCU的idea可以做很多拓展，你要想multi-writer是可以自己做的，不要被最基本
的RCU的定义给限制了
放狗搜一下，你就明白了 |
|
n******t
发帖数: 4406 | 7 pid是放在全局的pid_hash 这个数据结构里面的，这个东西用rcu机制来做同步，find_
vpid,作为rcu的reader,肯定需要用rcu_read_lock 和rcu_read_unlock了，从调用方式
上来说和 mark临界区没什么区别了。 |
|
s*******f
发帖数: 148 | 8 Thanks a lot for the information. i'm fresh master and i don't think they'd offer stock or options.
It's in midtown, not in financial district hehe:) The company is pretty
small, will it be too much to ask for 80k?
should have at least 80k for base, then + RCU + benefits. If the RCU and
benefits are limited, consider 90k at least. |
|
b********8
发帖数: 40 | 9 NYC-based quant trading hedge fund is looking for a GUI developer to join
our infrastructure team. They’ll work on overhauling the RCU, developing UI
applications from scratch including visualization/analytical/monitoring
tools, among other tasks. Candidates will need desktop GUI skills as opposed
to web dev skills. Ideally they’ll have intermediate to advanced C / C++ (
preferred), but we’re also willing to consider C#, or Java/Swing for this
role. CS background and computer vision experience h... 阅读全帖 |
|
y******n
发帖数: 47 | 10 周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.
* given a function on sorted dictionary to retrieve word by index,
string getWord(int i), how to i... 阅读全帖 |
|
S**I
发帖数: 15689 | 11 ☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 00:18:17 2011, 美东) 提到:
周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.... 阅读全帖 |
|
a****Q
发帖数: 83 | 12 不觉得lock需要基于某种语言来看,基本的思路都是一样的,当然，配合上语言,实现起
来会有不区别:
简单讲就lock和lock free
lock 具体实现:
Java: concurrency package
C/C++; pthread, C11
Linux kernel: spinlock_t, semaphore/mutex, rwlock_t.
Kernel的实现相对复杂一点,因为要区分当前的context,spinlock_t/rwlock_t会屏蔽中
断，所以不能block当前进程，比如不能分配内存,不能有磁盘或是网络读写．其他的和
user space的实现没有概念上的区别.
lock free 的实现实质上就是把lock从一段代码进一步精确到一条或是几条代码，所以
需要硬件上的配合.最实质的就是如何运用memory fence(也就是memory barrier)和CAS
(compare and swap)指令.
具体的实现：
Java: final/volatile/atomic variables;
ass/C/C++: 在C11出来之前很多都是直接内嵌汇编指令... 阅读全帖 |
|
|
w***x
发帖数: 105 | 14 lock free有很多种实现，glowinglake说的类似kernel里用的rcu，不过面试与其说考
lockfree，还不如考考简单的multi-threading的常识问题，lockfree的水很深，有些
问题可以复杂到深不见底的程度，所以真遇到个明白人，这种面试官其实是自取其辱。 |
|
l********e
发帖数: 103 | 15 多谢各位指点
我面试的时候 面试官 说写是用mutex, read不用lock...
不过 大家讨论后 我觉得这肯定不对
看了好几处CAS的介绍 都是说要update的时候 先和原来的值比较 如果相同则update
不过 没有说会不会影响 只读的线程
我想确认一下 CAS , RCU这种atomic的命令都是 在all pre-existing read-side
critical sections complete后 锁住bus,然后才update的吧？
不然读的线程 就都读出乱码了
我的理解对吗？
谢谢 |
|
T*****g
发帖数: 1306 | 16 这俩不是一个层面的吧
CAS是CPU instruction不存在read side critical section吧，你之前拿到了旧的
pointer那就是可以reference旧的object，具体到硬件
实现上有不同的办法，但是语义是一样的
RCU会有一个quiescent period来确保所有的read side critical section都结束，在
user space的implementation里好像是靠拿到每个worker的mutex来实现
★ 发自iPhone App: ChineseWeb 16 |
|
T*****g
发帖数: 1306 | 17 这个问题...怎么说呢...synchronization primitive是一层一层往上build的。。。
最底层的就是一些CPU atomic instruction，atomic load / store, CAS, TAS, 基于
这些CPU instruction可以build出各种锁（spin mutex, rwlock, MCS lock）,还有RCU
（本质是用atomic operation来做atomic publish）以及其他的一些primitive
楼下有人建议你看看那本书，我没读过，不过感觉应该对你理解这些有帮助 |
|
T*****g
发帖数: 1306 | 18 为什么不能？
我拿到了list里一个node的reference，只要这个node不被free我的access就不会有
segfault，同时我读到的数据是point-in-time consistent的（是在我拿到reference
的时候的snapshot）
change value可以copy-on-write, add / change node我用atomic pointer可以很容易
实现，然后等所有拿到这个node 的reference的reader都退出的时候就可以free掉了。
free这部分要避免segfault可以用最简单的ref count pointer来实现，当然RCU更好，
因为更scalable。 |
|
w***x
发帖数: 105 | 19 rcu设计本来就是一个w，多个r，这种情况下确实是lockfree，无论w还是r。
不过我一直不清楚user mode下怎么实现。 |
|
T*****g
发帖数: 1306 | 20 RCU的user space 实现比kernel space实现overhead要高，但是还是非常scalable，比
rwlock之类的强多了啊
其实主要的优势在于不modify的时候不往shared memory写数据，避免cache line
bouncing
当然这些偏底层了，不做这个的人估计理解起来有点困难 |
|
b********8
发帖数: 40 | 21 NYC-based quant trading hedge fund is looking for a GUI developer to join
our infrastructure team. They’ll work on overhauling the RCU, developing UI
applications from scratch including visualization/analytical/monitoring
tools, among other tasks. Candidates will need desktop GUI skills as opposed
to web dev skills. Ideally they’ll have intermediate to advanced C / C++ (
preferred), but we’re also willing to consider C#, or Java/Swing for this
role. CS background and computer vision experience h... 阅读全帖 |
|
i***e
发帖数: 9429 | 22 这个挺好的，3Ton的coil 配对2吨半的空调。CX35-36A
没有38A的，只有36A。CX35 是最新新款铝质coil.
系统效率同样达到16 SEER
(这套组合你很有可能还有tax credit 和当地电力公司或天然气公司的rebate.)
Active Systems ELITE XC14 SERIES LENNOX INDUSTRIES, INC. XC14-030-230A**
CX35-36A+TDR 1005 SL280UH070XV36A* 28000 13.00 16.00 1 RCU-A-CB
212 Yes |
|
A*********e
发帖数: 4361 | 23 RCU那个头不认得。FASHION太恐怖的版，不去掺和 |
|
w****g
发帖数: 597 | 24 Linux Kernel 2.6.29 Released
Posted by kdawson on Monday March 23, @10:07PM
"Linus Torvalds has released Linux 2.6.29. The new features include the
inclusion of kernel graphic modesetting, WiMAX, access point Wi-Fi support,
inclusion of squashfs and a preliminary version of btrfs, a more scalable
version of RCU, eCryptfs filename encryption, ext4 no journal mode, OCFS2
metadata checksums, improvements to the memory controller, support for
filesystem freeze, and other features. Here is the full l |
|
