h****n
发帖数: 1093 | 1 queue和这个问题不太一样，hash里面的slot是independent所以才能这么做，queue要
对整个queue加锁的，所能优化的地方有两点，第一个是尽量降低临界区也就是锁的时
间，第二个就是要采用semaphore同步机制来避免queue为空的时候pop操作busy loop，
queue满的时候push操作busy loop。具体可参考semaphore如何解决经典的生产者消费
者问题 |
|
o********n
发帖数: 193 | 2 来自主题: JobHunting版 - 新鲜电面经 从这里学到不少，回报大家。
G家。上来聊项目，10分钟。
然后来三个题。
第一题，给两段code，分别运行在不同的thread，汇编写的，两快code在register和两
快共享memory上相互读写，中间还穿插各种loop和branch,要求求出一指定register的
value。一眼看上去我就晕了，冷静后我挑出重点code，说是个consumer/producer low
level execution sequence problem in assembly。这两块code都没加锁，所以执行
的顺序排列组合下有四种可能，我搞出了一种可能，挺琐碎，又紧张，花了不少时间，
第二个可能正要搞他说算了。
第二题算法，字符串操作，我用两指针，几下就搞完了，边搞边讲，他说correct。面
完后我自己测了下，编译没过，原因是官给的input string是const，我定义的临时指
针没有const，编译报错，算是bug了，用const char*强制转换一下就过，测试都对。
第三题，实现多个producer和多个consumer，没有别的提示。这个我熟，说整个mutex
保护写，整个s... 阅读全帖 |
|
|
c********t
发帖数: 5706 | 4 en, 这个好，用semaphore，一个线程专门负责检测semaphore来create h2o, 是不是像
observer？ |
|
c********t
发帖数: 5706 | 5 en, 这个好，用semaphore，一个线程专门负责检测semaphore来create h2o, 是不是像
observer？ |
|
l*******b
发帖数: 2586 | 6 may be need several mutex to lock them... if the counter is a semaphore,
then it will pick one to wake up.
wiki: To avoid starvation, a semaphore has an associated queue of processes
(usually a first-in, first out) |
|
w*****a
发帖数: 166 | 7 多谢大牛分享！
看了下大牛们的分析，超级菜鸟说下自己的理解，整理下思路
首先，给出的程序就是busy checking,因为是while，不停的check,从os的角度，这个
thread是running/ready状态。
就算你用volatile,当一个thread在处理时，os仍然给另一个thread时间片来busy
checking if(volatile),所以他说你这个有busy waiting。
那么这样，我们必须想办法让一个thread处理时，另个个必须sleep(from os: blocked
),那就用lolhaha大牛的semaphore了。
当permit=0时，java并不care permit is >0, or <0,只要有人release, permit +1,
所以才可以synced output.
http://www.coderanch.com/t/504827/threads/java/Semaphores |
|
b*s
发帖数: 82482 | 8 对，semaphore，早期的信号系统……
semaphore?
…… |
|
|
b*s
发帖数: 82482 | 10 就是flag semaphore系统：
http://en.wikipedia.org/wiki/Flag_semaphore
问题是，谁在中国看到的？那个看到中国小旗的人是否是flag semaphore的发明人？那
个人什么时候去中国的？
不是inspired by中国花瓶，是inspired by中国game，而且是在中国看到的。那保安看
到那瓷器就讲了这个事情。
plus you sure you studied semiphore in the context of naval flag signalling,
not computer science? haha
…… |
|
b*s
发帖数: 82482 | 11 而且，中国的这个game是什么？具体是为了信号传输还是别的？中国自己的典章记载是
什么？
就是flag semaphore系统：
http://en.wikipedia.org/wiki/Flag_semaphore
问题是，谁在中国看到的？那个看到中国小旗的人是否是flag semaphore的发明人？那
个人什么时候去中国的？
不是inspired by中国花瓶，是inspired by中国game，而且是在中国看到的。那保安看
到那瓷器就讲了这个事情。
plus you sure you studied semiphore in the context of naval flag signalling,
not computer science? haha
…… |
|
c*****t
发帖数: 1879 | 12 Java's monitor mechanism can be easily implemented on any platforms.
If you read up things on Monitor <-> Semaphore, Java's monitor
implementation is quite trivial using semaphores. |
|
c*****t
发帖数: 1879 | 13 Java's monitor mechanism can be easily implemented on any platforms.
If you read up things on Monitor <-> Semaphore, Java's monitor
implementation is quite trivial using semaphores. |
|
b***i
发帖数: 3043 | 14 真是一语道破梦中人。
我的目的，就是实现dos这样的文本窗口，同时有一些按钮等。这样，我的主程序等待
semaphore，然后按下按钮，或者回车就release semaphore。
看来，应该做一个actionprocess函数，然后根本没有主程序的等待，直接在按下回车
或者按钮的时候在keypressed或者菜单action里面call actionprocess，尽快完成任务
，比如打开文件，命令处理等，反正源头都是GUI的活动。 |
|
b***i
发帖数: 3043 | 15 System.exit(0); 在main里面呼叫还是在UI线程里面呼叫？
现在程序开始后，我是应该用一个semaphore锁定main，不继续执行，等待用户进行UI
操作，直到用户决定退出，点击退出按钮，我这个时候释放semaphore，回到main执行
System.exit(0)呢？还是main里面直接结束， 没有System.exit(0)，但是在UI线程里
面呼叫 System.exit(0)好呢？ |
|
c*****t
发帖数: 1879 | 16 建议你买本
"Foundations of Multithreaded, Paralle, and Distributed Programming"
基本上这辈子不用再为这类问题发愁。基本所有的常见问题都有 C/java/pseudo
code 。抄一下就是了。
对于 reader / writer 的问题，最佳解法的 pseudo code 是
int nr = 0; // number of readers
semaphore rw = 1;
semaphore mutexR = 1;
reader ()
{
P (mutexR);
++nr;
if (nr == 1)
P (rw);
V (mutexR);
... critical section code
P (mutexR);
--nr;
if (nr == 0)
V (rw);
V (mutexR);
}
writer ()
{
P (rw);
... critical section code
V (rw);
}
如果没有 sema |
|
r******m
发帖数: 6 | 17 谢谢各位。
看来我对mutex的理解不对，我想说的应该是semaphore。
老大能不能顺便讲讲mutex跟semaphore的区别？
（google了一下，不是太明白） |
|
g*****g
发帖数: 34805 | 18 mutex is a binary semaphore, or a special case of semaphore |
|
D*******a
发帖数: 3688 | 19 mutex can only be unlocked by the thread which locks it
semaphore can be released by any thread
therefore you cannot use mutex as a binary semaphore under some cases |
|
b***i
发帖数: 3043 | 20 那就是说你同步部分写错了。很大的可能是你的那个semaphore根本就是生成了两个不
同的变量。
你要详细说一下，你是怎么同步的。你是把semaphore的指针传递给dll吗？ |
|
t****t
发帖数: 6806 | 21 mutex, condition variable, and atomic are already there. no semaphore,
although semaphore can be easily implemented with condition variable. |
|
x**n
发帖数: 461 | 22 第一，这不是TeacherWei原来的方案，原来的方案是一台单机打天下。后来大家不停地
打补丁才成这样。
第二，就是这个核心的单机节点。用Interlocked。当然，你可以欺负一帮Java
developer 不知道 interlocked。但是至少你得说是semaphore吧，或者是自己实现的
semaphore. |
|
x**n
发帖数: 461 | 23 你這個系統裡 semaphore 是必需的，不管你直接用 .net class 還是自己用
interlocked 實現，本質都是 semaphore。另外其實 goodbug 已經給你提示了，你還
需要 acid，這些加起來，就不是光 interlocked 那麼簡單了 |
|
d*******n
发帖数: 109 | 24 为啥是学linux给戴歪的？
mutex和semaphore锁 线程 进程都可以 semaphore 你自己写一个都可以 不用用任何
library |
|
f******n
发帖数: 90 | 25 已经fail好几次onsite了, 这里跟大家讨论一个tricky的面试问题。
我碰到过两次在讨论相关technical问题的时候，面试者犯技术上的错误，这种时候应
该怎么办？
第一次，我比较紧张，前面几个简单的问题答得都磕磕绊绊的，给对方的印象不是特别
好。 然后在回答另一个C++问题的时候，我为了impress him就特意提到了某些比较
obscure的tenichal details。 结果面试者说不可能，他从来没听说过。FT，我当时也
不知道说啥了。 我回来又查了资料，我确实是对的。
第二次， 他让我实现一个thread synchronization的问题，他实际上想让我用
condition variable实现，可我用的是semaphore,也可以实现。 他说semaphore 的V()
不会wake up sleeping threads waiting at P()。 He said he will be seriously
surprised if it does。 我又无语了。
可能我fail不全是因为这些，当时这个肯定起了不少负面的作用。 大家觉得应该当时
就 |
|
发帖数: 1 | 26 我面学生 一般就问你自己觉得哪门课学得最好啊
很多cs的老美来我这变态假物理专业
操作系统
好 那你给我实现一个semaphore
网络
好 你给我说说我在浏览器敲入google.com发生什么
数据结构
好 给我说说b数和binary search tree的本质区别
体系结构
好 给我说说code cache 和data cache的区别
把一群水货 立刻题走
现在招马工 就找一堆拼死刷题的生物钱老 |
|
f**********8
发帖数: 6 | 27 Please send your resume to a***[email protected] if interested.
Position: Software Engineer, Platform
Cyphort develops appliance and cloud based solutions that protect cloud
infrastructure against targeted attacks, corporate espionage and IP theft.
Our innovative approach detects armored malware, performs behavioral
clustering, and correlation algorithms for contextual threat prevention. We
are looking for smart people who collaborate, innovate and make great
security products. Whatever your role, y... 阅读全帖 |
|
d******y
发帖数: 1039 | 28 今天得到了第一个正式的offer,为了不淡忘找工的艰辛，以及往后得到更好的offe
r, 写写这个过程吧。
Fresh Ph.D. CS. 没有工作经验。去年12月毕业，博士论文关于无线通讯。我12月
开始找工，全国各地撒网，目标锁定比较大的公司。
准备过程:
1.联系熟人，朋友，以及朋友的朋友。从内部投了10家大公司。rp不错，大概50%有
回复。
2.自己在网上瞎投，投了5家公司，没有任何回复。
3.参加了各大公司在学校搞的information session, 没用。
4.找了两本教科书复习C++和数据结构：accelerated C++ 和introduction to alg
orithms
面试过程:
12月的时候刚搞完论文通过答辩，生物钟还没有调整过来，很多公司又喜欢早上面
试，所以错过了几个机会。比如大名鼎鼎的某金融shark,打电话过来的时候我还在
做梦，自然回答的一团糟。印象深刻的几个问题是：mutex和semaphore的区别；什
么是named pipes和pipes的区别；singleton的两种实现方法等等。12月23号在CC买
东西的时候又有一个公司突然 |
|
y***n
发帖数: 1594 | 29 今天和Bloomberg聊了一个小时，对方应该也是个中国人，问题都还可以，但是都很刨
根究底， 看你到底懂不懂。 没有算法的问题， 但是很多Multi-threading..
1> Reference Type/ Value type, can value type be on heap?
2> Static class.
3> Delegate/Event.
4> which thread does the delegate run on?
5> Can a strut has a default constructor?
6> Difference between mutex/monitor/semaphore.
7> When do you use the ThreadPool?
8> a lot, lot threading questions.....
下边这本书一定要读透， 所有的朋友都觉得这是 .Net bible.
http://www.amazon.com/CLR-via-Second-Pro-Developer/dp/0735621632 |
|
b****a
发帖数: 4465 | 30 I really don't know the answer.
I used mutex in multi-threads and semaphore in multi-processes |
|
k***e
发帖数: 556 | 31 面试这事 随机性很大 你还是稍微看点
至少process thread semaphore mutex ipc要知道吧
我的背景是物理，C++和Data structure还知道些少许，至于os就是一窍不通。。。所
以有些困惑。 |
|
b**********7
发帖数: 103 | 32 [更新Google Intern Interview 过程解释]
感谢很多朋友来信。鉴于大家都很关心Google Intern的过程，我来详细的说说吧。Google intern interview的过程好像和以前不太一样了，目前在发正式offer前，需要经历2轮电话interview，然后会进入一个candidate pool，由manager来挑选，这个过程叫host bidding.
1. 电话interview: 都是google的开发人员来面的，所以比MS的HR难。当然从另一个方面来说，因为开发人员更容易理解你的code，你更容易和他们沟通。每个人大约2道题。其中一个人两个都是算法。另一个就会问一道概念题（当然，是很多小概念），一道算法。面完后，他们把feedback发给HR，如果两个人对你的评价都是positive，那么恭喜，你进入candidate pool 了。一般这个要等待1天到几周不等。
2.我电面是用google doc, 每次写一点儿要保存，有些麻烦。尤其是你要加个外层循环，需要把每一行都缩进，很麻烦。我个人不建议先在IDE里写，因为这是个interactive... 阅读全帖 |
|
p******1
发帖数: 366 | 33 First, ask about my projects in resume. TinyOS scheduler stuff...
Second, virtual function problem
Third, reverse a string. Signature is Char* reverse(char *)
Fouth, what's deadlock? what's semaphore and mutex?
Fifth, use stacks to achieve queue functions.
Sixth, talk about himself. lol....
回答的都没问题，就是有点儿困。。。中午吃了烤牛肉，嘻嘻。不知道能不能到下一轮
。不过看板内大牛们都到了onsite了还是被拒，我觉得没什么希望了。
干脆发过来攒人品，希望大家虎年吉祥。 |
|
d******a
发帖数: 238 | 34 线程通信，其实叫线程同步更准确，主要有mutex, conditional variable,semaphore.
管道,socket什么的应该归到进程间通信里。
静态type指的是用模板实现，动态指用虚拟函数实现。
我觉得还是让设计股票那个server端和客户端的题最狠了，这题明明是招架构师到经理
职位的。。。 |
|
f****4
发帖数: 1359 | 35 静态type 动态type
class Base;
class Derived:Base;
这只是show一下继承结构
Base *p = new Derived;
Base * 是所谓的静态type
Derived是动态type
（这个在more effective c++/effective c++里面有提到过）
你说的那个非别叫做静态polymorphism和动态polymorphism
semaphore. |
|
|
s*****r
发帖数: 773 | 37 1 如何detect dead lock, avoid dead lock 和break dead lock
how to make sure there is no dead lock?
2 mutex 和 binary semaphore有什么区别
3 线程之间如何通讯?
谢谢了 |
|
|
c****a
发帖数: 11 | 39 你的i/o example里面 为什么不能用mutex?
mutex |
|
l*******y
发帖数: 1498 | 40 thread1 waits for the I/O to complete, thread2 is responsible for completing
the I/O operation. thread1 get the semaphonre first, thread2 realse it then
. Then thread1 find the I/O operation completes and can do the following
things. This is a kind of communication.
If use mutex, if thread1 get the mutex, only thread1 can release the mutex. |
|
x***y
发帖数: 633 | 41 For concurrency programming, beside mutex, you can also use semaphore,
critical sectoin, cv or block/write locks as synchronization primitives... |
|
o**********t
发帖数: 406 | 42 1,2 可以用 main thread，但是似乎不好，因为 main thread 一般不应该参与这种事
情。也不可一概而论。
可以开始就针对每个 object 启动一个 thread，全部一起开始。
也可以只有一个 worker thread ，让 worker thread 检查是否还有剩余的 object
3, C#: lock, Mutex, Semaphore, Memory Barrier, Monitor ....etc
1.假定现在data sampling, data collection, data analysis loop只对一种object
循环, 循环结束, work thread也就结束, 那么怎么让data sampling, data
collection, data analysis loop对一种object 循环结束后, 继续对其他objects 循
环, 等对所有objects循环后, work thread 再退出?
2. 如何实现? 需要main thread参与控制吗? 还是只在workthread就可以? 各有啥优
势? 劣势?
3 |
|
r****o
发帖数: 1950 | 43 多谢。楼主看来是对network和OS很有经验的吧。
像spanning tree in layer 2和recursive semaphore的这两题目我感觉没经验的很难
答好啊。
com" |
|
I**********s
发帖数: 441 | 44 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
r****o
发帖数: 1950 | 45 spin lock和mutex的主要区别是不是就是spin lock是busy waiting， mutex是sleep
waiting?
这是不是也是spin lock和semaphore的区别?
logN |
|
Z*****Z
发帖数: 723 | 46 扔块板儿砖：thread之间是共享内存的，所以通信可以用shared memory，semaphore。
process有独立的内存空间，所以上述方法不适用，取而代之的是信号、文件读写、soc
ket
有什么不同? |
|
c*****h
发帖数: 166 | 47 大概50分钟的样子 最后5分钟问他问题
我online test选的java, 不过电面上来也就是c/c++的东西
1. 自我介绍
2. static什么意思 怎么用
3. synchronize怎么用
4. Singleton, 什么时候用 什么是double checking(ft这里，我自己说出来了被他追
着打)
5. HashMap和TreeMap,search，insert, delete的复杂度, 有HashMap了为啥还要
TreeMap
6. Sql里面有哪些Join, inner join 和left join的区别 举实际例子
7. 给个dead lock的场景 怎么解决 semaphore和mutex lock区别
完全没有behavioral question, brain tease和project介绍
各位好运~ |
|
|
|
d********n
发帖数: 54 | 50 本人PhD，3年半工作经验。2个月前收到Google recruiter电话，开始面试，一个月前
拿到offer，然后开始了漫长的谈判，昨天终于签字。上来share一下面经。
2年前面过google，职位不喜欢，把它拒了。因为他们有记录，所以这次只安排了4人面
试。
第一个是老美，先问了一些简单问题，比如怎么判断一个32 bit是big endian 还是
small endian等等。最后出了一道算法题，也很容易，给定K个sorted array，要求输
出一个大的sorted array。简单的merge sort就解决了。不过merge sort 要求每次K个
array中，最小的element。简单的当然是scan这K个array。我提出可以把K个array的当
前element放入Heap structure，这样每次搜索就从O(K)降低到O(logK)。最后写了个程
序。
第二个是老中。也是先问了一些简单问题，然后让我设计一个分布式文件系统，给定
path name，可以读写文件。具体的system design这里就不提了。其中一个细节是，给
定path name，怎么知... 阅读全帖 |
|
