题目
原文:
Suppose we have the following code:
1
2
3
4
5
6
7
8
9
10
11
class Foo{
public:
A(.....); /*If A is called, a new thread will be created and
the corresponding function will be executed. */
B(.....); /*same as above */
C(.....); /*same as above */
};
Foo f;
f.A(.....);
f.B(.....);
f.C(.....);
i) Can you design a mechanism to make sure that B is executed after A, and C is executed after B?
ii) Suppose we have the following code to use class Foo. We do not know how the threads will be scheduled in the OS.
1
2
3
Foo f;
f.A(.....); f.B(.....); f.C(.....);
f.A(.....); f.B(.....); f.C(.....);
Can you design a mechanism to make sure that all the methods will be executed in sequence?
译文:
假设我们有以下代码:
1
2
3
4
5
6
7
8
9
10
class Foo{
public:
A(.....); /*当A被调用时,会创建一个新的线程并执行相应的函数*/
B(.....); /*同上*/
C(.....); /*同上*/
};
Foo f;
f.A(.....);
f.B(.....);
f.C(.....);
i) 你能设计一种机制确保B在A后执行,C在B后执行吗?
ii) 假设我们有以下代码,我们并不知道操作系统如何调度线程。 你能设计一种机制来确保所有的方法都按顺序执行吗?
1
2
3
Foo f;
f.A(.....); f.B(.....); f.C(.....);
f.A(.....); f.B(.....); f.C(.....);
解答
第一问,初始的两个信号量都为0,函数A执行完后,信号量s_a会加1,这时B才可执行。 B执行完后信号量s_b加1,这时C才可执行。以此保证A,B,C的执行顺序。 注意到函数A其实没有受到限制,所以A可以被多个线程多次执行。比如A执行3次, 此时s_a=3;然后执行B,s_a=2,s_b=1;然后执行C,s_a=2,s_b=0; 然后执行B,s_a=1,s_b=1。即可以出现类似这种序列:AAABCB。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Semaphore s_a(0);
Semaphore s_b(0);
A {
/***/
s_a.release(1); // 信号量s_a加1
}
B {
s_a.acquire(1); // 信号量s_a减1
/****/
s_b.release(1); // 信号量s_b加1
}
C {
s_b.acquire(1); // 信号量s_b减1
/******/
}
第二问代码如下,与第一问不同,以下代码可以确保执行顺序一定严格按照: ABCABCABC…进行。因为每一时刻都只有一个信号量不为0, 且B中要获取的信号量在A中释放,C中要获取的信号量在B中释放, A中要获取的信号量在C中释放。这个保证了执行顺序一定是ABC。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Semaphore s_a(0);
Semaphore s_b(0);
Semaphore s_c(1);
A {
s_c.acquire(1);
/***/
s_a.release(1);
}
B {
s_a.acquire(1);
/****/
s_b.release(1);
}
C {
s_b.acquire(1);
/******/
s_c.release(1);
}
全书题解目录:
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上:
https://github.com/Hawstein/cracking-the-coding-interview
声明:自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证,转载请注明作者及出处
出处:http://hawstein.com/2013/02/19/18.5/