题目
原文：
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/
