置顶随笔
找工，其实早在11年十一月份就结束了，今天来补个总结。
11年九月下旬赶回去参加趋势科技在南京的笔试，并成功地在十一之前拿到offer，记得从南京坐高铁回家，怀里揣着趋势的offer很是心安，也给了自己很大的信心（因为，一直觉得自己从广州跑回南京上海找工会处于劣势），至今对于趋势科技面试的轻松氛围，包括最后的群面都印象深刻，是一家很nice的公司。
休完十一假期就赶去上海，在上海复旦呆了个把月，感谢舍友彭博帮我在复旦找到落脚地。
在上海，前前后后参加了很多的笔试面试，最终拿到了满意的offer，去了EMC，尽量得花5000大洋的毁约费。
推荐公司：EMC，TrendMicro，Marvell
“经验”：
自信&微笑，熟练掌握一门语言(如C)，数据结构与算法(推荐《算法导论》)，操作系统(推荐《深入理解计算机系统》)，有个别“拿得出手”的小项目，英语
----------------------------------------------------------------------------------------------------------------
所有投递简历公司那长长的列表(排名按投递简历的时间顺序)：
1. 爱立信 上海
SH01 Software Design Engineer (上海)
[已笔试, 通过群面, 放弃]
2. 趋势科技 Trend Micro (上海)
软件工程师
https://campus.trendmicro.com.cn
[已笔试, 已面试, OFFER]
3. Marvell (上海)
[已笔试，已面试，OFFER]
4. 百度 (上海)
[时间冲突，放弃]
5. 华为
软件研发工程师 性能/算法工程师
[放弃]
6. 飞利浦 苏州 (上海)
嵌入式软件开发工程师 软件应用开发工程师
[放弃]
7. Google (上海)
[放弃]
8. nVidia 英伟达 (上海)
GPU Architect
[放弃]
9. EMC (上海)
Software Development Engineer 上海
[已笔试, 已面试, OFFER]
10. AMD (上海)
System Software Engineer
[木有笔试机会]
11. 腾讯 (上海)
后台开发 上海
[已笔试, 已面试, OFFER]
12. 微软 (上海)
软件开发工程师 上海
[时间冲突，放弃]
13 Samsung (南京)
手机开发 南京
[放弃]
14 IBM CSTL (上海)
storage software engineer
[没消息]
15. Intel (上海)
zhaopin.com
[木有笔试机会]
16. Cisco (上海)
embedded software development engineer
[放弃]
17. 大众点评网 (上海)
技术培训生 - 开发
[放弃]
18. 阿尔卡特朗讯 (上海)
[放弃]
19. 支付宝 (上海)
[放弃]
20. 中航无线电 (上海)
[放弃]
21. Oracle (上海)
[已面试，算是给了OFFER]
22. 江苏移动
[放弃]
下半年就要正式找工了，淘宝的实习因为爷爷去世提前告一段落。
书籍
编程语言： 《C和指针》，《C专家编程》，《C++ Primer》，《Effective C++》
数据结构与算法： 《算法导论》，《编程珠玑》，《编程之美》
操作系统: 《操作系统》，《深入理解计算机系统》，《Linux内核设计与实现》
计算机网络: 《TCP/IP详解 卷一》
编程实践
常用数据结构，排序，搜索，图算法，动态规划，字符串等
参考： PKU已做题目，何海涛的面试100题，IT面试题
2012年2月27日
找工，其实早在11年十一月份就结束了，今天来补个总结。
11年九月下旬赶回去参加趋势科技在南京的笔试，并成功地在十一之前拿到offer，记得从南京坐高铁回家，怀里揣着趋势的offer很是心安，也给了自己很大的信心（因为，一直觉得自己从广州跑回南京上海找工会处于劣势），至今对于趋势科技面试的轻松氛围，包括最后的群面都印象深刻，是一家很nice的公司。
休完十一假期就赶去上海，在上海复旦呆了个把月，感谢舍友彭博帮我在复旦找到落脚地。
在上海，前前后后参加了很多的笔试面试，最终拿到了满意的offer，去了EMC，尽量得花5000大洋的毁约费。
推荐公司：EMC，TrendMicro，Marvell
“经验”：
自信&微笑，熟练掌握一门语言(如C)，数据结构与算法(推荐《算法导论》)，操作系统(推荐《深入理解计算机系统》)，有个别“拿得出手”的小项目，英语
----------------------------------------------------------------------------------------------------------------
所有投递简历公司那长长的列表(排名按投递简历的时间顺序)：
1. 爱立信 上海
SH01 Software Design Engineer (上海)
[已笔试, 通过群面, 放弃]
2. 趋势科技 Trend Micro (上海)
软件工程师
https://campus.trendmicro.com.cn
[已笔试, 已面试, OFFER]
3. Marvell (上海)
[已笔试，已面试，OFFER]
4. 百度 (上海)
[时间冲突，放弃]
5. 华为
软件研发工程师 性能/算法工程师
[放弃]
6. 飞利浦 苏州 (上海)
嵌入式软件开发工程师 软件应用开发工程师
[放弃]
7. Google (上海)
[放弃]
8. nVidia 英伟达 (上海)
GPU Architect
[放弃]
9. EMC (上海)
Software Development Engineer 上海
[已笔试, 已面试, OFFER]
10. AMD (上海)
System Software Engineer
[木有笔试机会]
11. 腾讯 (上海)
后台开发 上海
[已笔试, 已面试, OFFER]
12. 微软 (上海)
软件开发工程师 上海
[时间冲突，放弃]
13 Samsung (南京)
手机开发 南京
[放弃]
14 IBM CSTL (上海)
storage software engineer
[没消息]
15. Intel (上海)
zhaopin.com
[木有笔试机会]
16. Cisco (上海)
embedded software development engineer
[放弃]
17. 大众点评网 (上海)
技术培训生 - 开发
[放弃]
18. 阿尔卡特朗讯 (上海)
[放弃]
19. 支付宝 (上海)
[放弃]
20. 中航无线电 (上海)
[放弃]
21. Oracle (上海)
[已面试，算是给了OFFER]
22. 江苏移动
[放弃]
2011年10月20日
示例代码:
/* how to simulate C++'s polymorphism with C */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/* declaration of virtual method */
typedef void (*Func1)(void);
typedef void (*Func2)(int);
typedef void (*Func3)(char *);
/* ------------------- Base Class begin ------------------*/
void func1_base(void)
{
printf("func1_base(void) called\n");
}
void func2_base(int item)
{
printf("func2_base(%d) called\n", item);
}
struct Vtbl_Base {
Func1 f1;
Func2 f2;
};
struct Vtbl_Base bvtbl = {&func1_base, &func2_base};
struct Base {
void *vptr; /* pointer to VTABLE */
int field_base;
};
void Base_Init(struct Base *base, int value)
{
base->vptr = &bvtbl;
base->field_base = value;
}
/* ------------------- Base Class end ------------------*/
/* ------------------- Derived Class begin ------------------*/
void func1_derived(void)
{
printf("func1_derived(void) called\n");
}
void func3_derived(char *item)
{
printf("func3_derived(%s) called\n", item);
}
struct Vtbl_Derived {
struct Vtbl_Base vtbl_base;
Func3 f3;
};
struct Vtbl_Derived dvtbl = {{&func1_derived, &func2_base}, &func3_derived};
struct Derived {
struct Base base;
int field_derived;
};
void Derived_Init(struct Derived *derived, int b, int d)
{
Base_Init((struct Base *)derived, b);
derived->base.vptr = &dvtbl;
derived->field_derived = d;
}
/* ------------------- Derived Class end ------------------*/
void
test_polymorphism(struct Base *obj)
{
((struct Vtbl_Base *)(obj->vptr))->f1();
((struct Vtbl_Base *)(obj->vptr))->f2(obj->field_base);
}
int
main(int argc, char **argv)
{
struct Base base;
Base_Init(&base, 128);
test_polymorphism(&base);
struct Derived derived;
Derived_Init(&derived, 128, 256);
test_polymorphism((struct Base *)&derived);
((struct Vtbl_Derived *)(*(int *)&derived))->f3("polymorphism");
}
2011年10月16日
转:
一个 m*n 的 Young 氏矩阵(Young tableau) 是一个 m*n 的矩阵,其中每一行的数据都从左到右排序,每一列的数据都从上到下排序.Young 氏矩阵中可能会有一些 ∞ 数据项,表示不存在的元素.所以,Young 氏矩阵可以用来存放 r<= mn 个有限的元素.
a).画一个包含{9,16,3,2,4,8,5,14,12} 的4*4 的 Young 氏矩阵.b).给出一个在非空 m*n 的 Young 氏矩阵上实现 EXTRACT-MIN 算法,使其运行时间为O(m+n).
c).说明如何在O(m+n)时间内,将一个新元素手入到一个未满的 m*n Young 氏矩阵中.
d).给出一个时间复杂度为 O(n^3) 的对 n*n Young 氏矩阵排序的算法.
e).给出一个运行时间为O(m+n) 的算法,来决定一个给定的数是否存在于一个给定的 m*n 的 Young 氏矩阵当中.
答
a). 2 3 4 5
8 9 12 14
16 ∞ ∞ ∞
∞ ∞ ∞ ∞
PS.该矩阵并不是唯一的.
b). (1)用递归的思想.在 Young 氏矩阵中，通过递归的解决(m-1)*n,或m*(n-1) 的子问题来求解.则有 T(m,n)=T(m-1,n) or T(m,n-1)+ O(1),显然,T=O(m+n).伪代码如下:
EXTRACT_MIN(Young[1...m] [1...n])
EXTRACT_MIN=Young[1][1]; //类似FORTRAN的写法.函数名即是返回值.
Young[1][1]= INFINITY;
ADJUST_TO_YOUNG(Young[1...m] [1...n]);
END
ADJUST_TO_YOUNG(Young[x...m] [y...n])
if(Young[x][y]==∞)
return;
if(Young[x+1][y]>Young[x][y+1])
swap(Young[x][y], Young[x][y+1]);
ADJUST_TO_YOUNG(Young[x...m][y+1...n]);
else
swap(Young[x][y], Young[x+1][y]);
ADJUST_TO_YOUNG(Young[x+1...m][y...n]);
END
(2)类似堆的删除：将Young[1][1]与最右下角元素交换, 然后移动Young[1][1]处的元素至合适位置，即把它与右方或下方元素的比较,并与其中较小的一个交换.反复进行直到它不大于它右方和下方的元素为止.
c). 类似堆的插入：先将待插入的元素 K 放在 Young[m][n], 然后比较 K 与它左方或上方元素的大小,并与其中较大的一个交换.反复进行直到 K 不小于它左方和上方的元素为止. 在这里,同样有,T(m,n)=T(m-1,n) or T(m,n-1)+ O(1),T=O(m+n).伪代码如下:
INSERT(k,Young[m][n])
if(Young[m][n] < INFINITY) alert: 矩阵已满,无法插入!!
while(k<Young[m-1][n] or k<Young[m][n-1])
if(Young[m-1][n] >Young[m][n-1])
swap(k,Young[m-1][n]);
m=m-1;
else
swap(k,Young[m][n-1]);
n=n-1;
END
d). 调用 n*n 次 EXTRACT_MIN 过程即可.
e). 总是于最右上角的元素X比较；
1）如果==X,结束；
2）如果比X小，那么元素只可能在前N-1列中；
3）如果比X大，那么元素只可能在后M-1行中；
Young 氏矩阵去掉一行或一列还是 Young 氏矩阵；
所以每次比较最少去掉一行或一列，这样复杂度就是 O(m+n);
问题:
有两个已排好序的数组A和B，长度均为n，找出这两个数组的中间元素。要求时间代价为O(logn)
思路:
a. 比较自然的思路是归并算法，不过时间复杂度是O(n)，无法满足题目要求
b.
( http://www.binghe.org/2011/05/find-median/ )
Say the two arrays are sorted and increasing, namely A and B.
It is easy to find the median of each array in O(1) time.
Assume the median of array A is m and the median of array B is n.
Then,
1′ If m=n, then clearly the median after merging is also m, the algorithm holds.
2′ If m<n, then reserve the half of sequence A in which all numbers are greater than
m, also reserve the half of sequence B in which all numbers are smaller than n.
Run the algorithm on the two new arrays.
3′ If m>n, then reserve the half of sequence A in which all numbers are smaller than
m, also reserve the half of sequence B in which all numbers are larger than n.
Run the algorithm on the two new arrays.
Time complexity: O(logn)
2011年10月11日
昨天去面试，结果中间还插了一个小时的上机(给个laptop，Windows+VC环境，用惯Vim结果好不习惯^_^)，其中一题如下：
有N个人按照1到N编号围成一个圈做游戏
从第一个人开始从1报数,数到M的人退出游戏,他后面的人接着重新从1开始报数，一直持续到所有人都退出．
要求输出退出游戏的人的顺序.
这题以前看过，记得貌似有些数学规律的，忘了，所以只能当场用模拟的方法来做。
当时用的是循环数组来模拟，结果花了半个小时才编译、测试搞定，面试我的人(挺Nice的)看了之后说，答案输出是对的，其实更自然的模拟是用链表。
刚才用链表试了下，果然简单好多，大概五分钟就可以搞定。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
int n, m;
struct Item {
int number;
struct Item *next;
};
void
solve(int n, int m)
{
int i, j;
assert(n>0 && m<=n);
struct Item *items = (struct Item *)malloc(sizeof(struct Item) * n);
assert(items != NULL);
/* init */
for(i=0; i<n-1; ++i) {
items[i].number = i+1;
items[i].next = items+i+1;
}
items[n-1].number = n;
items[n-1].next = items;
/* simulate */
struct Item *cur, *prev = NULL;
cur = items;
while(n--) {
j = m;
while(--j) {
prev = cur;
cur = cur->next;
}
printf("%d\n", cur->number);
prev->next = cur->next;
cur = cur->next;
}
free(items);
}
int
main(int argc, char **argv)
{
while(scanf("%d %d", &n, &m) != EOF) {
printf("Result of (N=%d, M=%d)\n", n, m);
solve(n, m);
}
return 0;
}
2011年10月8日
文件描述符----文件表----v节点结构三者的联系
既然文件描述符标识特定进程正在访问的文件，那进程跟文件是怎么联系起来的呢？
首先我们得知道每运行一个进程，shell就会默认为其打开三个文件描述符(0,1,2)，分别与标准输入(stdin)，标准输出(stdout)和标准错误(stderr)对应。
接下来讲下内核所使用的三种数据结构，正是这三种数据结构才使进程最终跟文件联系起来。建议边看图一边看下面的文字描述
a. 每个进程在进程表中都有一个记录项，每个记录项中有一张打开文件描述符表，可将其视为一个矢量，每个描述符占用一项。
与每个文件描述符相关联的是：(a) 文件描述符。(b) 指向一个文件表项的指针
b. 内核为所有打开文件维持一张文件表。每个文件表项包含：(a) 文件状态标志。(b) 当前文件位移量。(c) 指向该文件v节点表项的指针。
c. 每个打开文件（或设备）都有一个v节点结构。是文件的重要信息部分。
下图表示以上三个数据结构的关系：
fd1 = open(pathname, oflags);
fd2 = dup(fd1);
fd3 = open(pathname, oflags);
图一
dup/dup2
相信大部分在Unix/Linux下编程的程序员手头上都有《Unix环境高级编程》(APUE)这本超级经典巨著。作者在该书中讲解dup/dup2之前曾经讲过“文件共享”，这对理解dup/dup2还是很有帮助的。这里做简单摘录以备在后面的分析中使用：
Stevens said:
(1) 每个进程在进程表中都有一个记录项，每个记录项中有一张打开文件描述符表，可将视为一个矢量，每个描述符占用一项。与每个文件描述符相关联的是：
(a) 文件描述符标志。
(b) 指向一个文件表项的指针。
(2) 内核为所有打开文件维持一张文件表。每个文件表项包含：
(a) 文件状态标志(读、写、增写、同步、非阻塞等)。
(b) 当前文件位移量。
(c) 指向该文件v节点表项的指针。
图示：
文件描述符表
------------
fd0 0 | p0 -------------> 文件表0 ---------> vnode0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------
fd2 2 | p2
------------
fd3 3 | p3
------------
... ...
... ...
------------
一、单个进程内的dup和dup2
假设进程A拥有一个已打开的文件描述符fd3，它的状态如下：
进程A的文件描述符表(before dup2)
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------
fd2 2 | p2
------------
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------
... ...
... ...
------------
经下面调用：
n_fd = dup2(fd3, STDOUT_FILENO);后进程状态如下：
进程A的文件描述符表(after dup2)
------------
fd0 0 | p0
------------
n_fd 1 | p1 ------------
------------ \
fd2 2 | p2 \
------------ _\|
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------
... ...
... ...
------------
解释如下：
n_fd = dup2(fd3, STDOUT_FILENO)表示n_fd与fd3共享一个文件表项(它们的文件表指针指向同一个文件表项)，n_fd在文件描述符表中的位置为 STDOUT_FILENO的位置，而原先的STDOUT_FILENO所指向的文件表项被关闭，我觉得上图应该很清晰的反映出这点。按照上面的解释我们 就可以解释CU中提出的一些问题：
(1) "dup2的第一个参数是不是必须为已打开的合法filedes？" -- 答案：必须。
(2) "dup2的第二个参数可以是任意合法范围的filedes值么？" -- 答案：可以，在Unix其取值区间为[0,255]。
另外感觉理解dup2的一个好方法就是把fd看成一个结构体类型，就如上面图形中画的那样，我们不妨把之定义为：
struct fd_t {
int index;
filelistitem *ptr;
};
然后dup2匹配index，修改ptr，完成dup2操作。
在学习dup2时总是碰到“重定向”一词，上图完成的就是一个“从标准输出到文件的重定向”，经过dup2后进程A的任何目标为STDOUT_FILENO的I/O操作如printf等，其数据都将流入fd3所对应的文件中。下面是一个例子程序：
#define TESTSTR "Hello dup2\n"
int main() {
int fd3;
fd3 = open("testdup2.dat", 0666);
if (fd < 0) {
printf("open error\n");
exit(-1);
}
if (dup2(fd3, STDOUT_FILENO) < 0) {
printf("err in dup2\n");
}
printf(TESTSTR);
return 0;
}
其结果就是你在testdup2.dat中看到"Hello dup2"。
二、重定向后恢复
CU上有这样一个帖子，就是如何在重定向后再恢复原来的状态？首先大家都能想到要保存重定向前的文件描述符。那么如何来保存呢，象下面这样行么？
int s_fd = STDOUT_FILENO;
int n_fd = dup2(fd3, STDOUT_FILENO);
还是这样可以呢？
int s_fd = dup(STDOUT_FILENO);
int n_fd = dup2(fd3, STDOUT_FILENO);
这两种方法的区别到底在哪呢？答案是第二种方案才是正确的，分析如下：按照第一种方法，我们仅仅在"表面上"保存了相当于fd_t（按照我前面说的理解方 法）中的index，而在调用dup2之后，ptr所指向的文件表项由于计数值已为零而被关闭了，我们如果再调用dup2(s_fd, fd3)就会出错(出错原因上面有解释)。而第二种方法我们首先做一下复制，复制后的状态如下图所示:
进程A的文件描述符表(after dup)
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------ /|
fd2 2 | p2 /
------------ /
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------ /
s_fd 4 | p4 ------/
------------
... ...
... ...
------------
调用dup2后状态为：
进程A的文件描述符表(after dup2)
------------
fd0 0 | p0
------------
n_fd 1 | p1 ------------
------------ \
fd2 2 | p2 \
------------ _\|
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------
s_fd 4 | p4 ------------->文件表1 ---------> vnode1
------------
... ...
... ...
------------
dup(fd)的语意是返回的新的文件描述符与fd共享一个文件表项。就如after dup图中的s_fd和fd1共享文件表1一样。
确定第二个方案后重定向后的恢复就很容易了，只需调用dup2(s_fd, n_fd);即可。下面是一个完整的例子程序：
#define TESTSTR "Hello dup2\n"
#define SIZEOFTESTSTR 11
int main() {
int fd3;
int s_fd;
int n_fd;
fd3 = open("testdup2.dat", 0666);
if (fd3 < 0) {
printf("open error\n");
exit(-1);
}
/* 复制标准输出描述符 */
s_fd = dup(STDOUT_FILENO);
if (s_fd < 0) {
printf("err in dup\n");
}
/* 重定向标准输出到文件 */
n_fd = dup2(fd3, STDOUT_FILENO);
if (n_fd < 0) {
printf("err in dup2\n");
}
write(STDOUT_FILENO, TESTSTR, SIZEOFTESTSTR); /* 写入testdup2.dat中 */
/* 重定向恢复标准输出 */
if (dup2(s_fd, n_fd) < 0) {
printf("err in dup2\n");
}
write(STDOUT_FILENO, TESTSTR, SIZEOFTESTSTR); /* 输出到屏幕上 */
return 0;
}
注意这里我在输出数据的时候我是用了不带缓冲的write库函数，如果使用带缓冲区的printf，则最终结果为屏幕上输出两行"Hello dup2"，而文件testdup2.dat中为空，原因就是缓冲区作怪，由于最终的目标是屏幕，所以程序最后将缓冲区的内容都输出到屏幕。
三、父子进程间的dup/dup2
由fork调用得到的子进程和父进程的相同文件描述符共享同一文件表项，如下图所示：
父进程A的文件描述符表
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------ /|\
fd2 2 | p2 |
------------ |
|
子进程B的文件描述符表 |
------------ |
fd0 0 | p0 |
------------ |
fd1 1 | p1 ---------------------|
------------
fd2 2 | p2
------------
所以恰当的利用dup2和dup可以在父子进程之间建立一条“沟通的桥梁”。这里不详述。
四、小结
灵活的利用dup/dup2可以给你带来很多强大的功能，花了一些时间总结出上面那么多，不知道自己理解的是否透彻，只能在以后的实践中慢慢探索了。
转载:
http://blog.21ic.com/user1/6406/archives/2011/81684.html
2011年10月7日
override: 覆盖、重写
overload: 重载
虚函数总是在派生类中被改写，这种改写被称为“override”。我经常混淆“overload”和“override”这两个单词。澄清一下：
override是指派生类重写基类的虚函数，就象我们前面B类中重写了A类中的foo()函数。重写的函数必须有一致的参数表和返回值（C++标准允许返回值不同的情况，这个我会在“语法”部分简单介绍，但是很少编译器支持这个feature）。这个单词好象一直没有什么合适的中文词汇来对应，有人译为“覆盖”，还贴切一些。
overload约定成俗的被翻译为“重载”。是指编写一个与已有函数同名但是参数表不同的函数。例如一个函数即可以接受整型数作为参数，也可以接受浮点数作为参数。
答案是：不可以
原因：
概念上，
虚函数的意图是动态绑定，程序会根据对象的动态类型来选择要调用的方法。然而在构造函数运行的时候，这个对象的动态类型还不完整(可以是基类，也可以是子类)，没有办法确定它到底是什么类型，故构造函数不能动态绑定。
实现上，vptr是构造函数设置的。通过vptr才能找到虚函数。
如果构造函数为虚函数，通过构造函数设置的vptr才能找到构造函数，然后调用它设置vptr，这是不可能实现的。
参考:
2011年9月25日
前两天Marvell面试，被问到优先级反转是什么东东，无奈只能表示不会，还好面试官非常地NICE，很耐心地告诉我这是什么，还聊起NASA的火星探测器就因为优先级反转的原因出现过BUG， 我就一直点头，还说回来会GOOGLE学习下
Priority Inversion 优先级反转是嵌入式实时系统里面的一个经典的问题。简单描述一下这个问题：有三个优先级不同的task,A,B,C; A的优先级最高，B次之，C最低。其中A和C有共享的临界区。如果C已进入临界区，那么A在进入进入临界区之前，就会被阻塞。task B有可能打断C而进入运行状态，这样C什么时候从临界区退出，就是一个未知的时间。A只有C从临界区退出后才能被调度，A被阻塞的时间也是未知的。这样，低优先级的B先于高优先级的A被调度，优先级发生了逆转。
这个问题在一般的操作系统里面不是一个严重的问题，最多A被多阻塞了一段时间。但是，在实时系统里面，如果一个任务在规定的时间里面没有被调度运行，系统就相当于失败了，可能引发系统崩溃。
解决这个问题有两种手段：
1：Priority inheritance(优先级继承)，如果一个高优先级的task被阻塞，与它共享临界区的低优先级的task在进入临界区后，优先级就会继承高优先级task的优先级，保证它不会被其他优先级次高的任务打断。从临界区退出后，C的优先级恢复正常。
2：A priority ceiling（最高优先级），给临界区分配最高优先级，如果一个task进入临界区，就把临界区的优先级赋给它，已保证它不会被打断。从临界区退出后，task的优先级恢复正常。
实时操作系统的一个特点就是，一个实时任务，会在规定的时间内得到响应，并且在规定的时间内完成任务。所以，一切不可预知的动作都是有害的。
有兴趣可以看看下面两个链接：
http://en.wikipedia.org/wiki/Priority_inversion
http://www.embedded.com/story/OEG20020321S0023
来源:
http://www.kernelchina.org/node/210
继续我们的推理问题之旅，今天我们要对付的是一个Google的面试题：Two Egg Problem.
我们开始吧！
No.2 Google Interview Puzzle : 2 Egg Problem
* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process
分析与解答：
题目要求试的最大次数最小。首先，讨论两个比较trivial的方案。
方案1：从第一层开始扔鸡蛋，如果鸡蛋不碎，则上一层再扔。这样，如果鸡蛋在某一层碎的话，该层就是临界的层。这种方案的优点在于省鸡蛋，只会摔破一个鸡蛋。还有一个鸡蛋可以带回家，做个鸡蛋羹，补充营养个! :) 缺点就是，如果鸡蛋在100层才碎的话，那就要试100次啦。那你等电梯要等死啦，而且还要接受别人的打量的目光，心说这怪咖为什么每次都只坐一层楼啊…
方案2： 想必很多人都会想到这个方案。我只能说，这是中国计算机教育的成功啊。这就是“二分查找法”。首先在第50层楼扔鸡蛋，如果鸡蛋不碎的话，就去75楼。如果碎了的话，那么对不起，同志。由于你只剩一个鸡蛋了，所以你得小心地从第一层开始，这样才能保证你在鸡蛋碎完的时候能找到临界楼层。这种方法的优势在于，如果你知道你的鸡蛋比较硬的话，你就采用这个方法吧。临界楼层越高，这个方法尝试的次数越小。但这种优势是用临界楼层比较小时比较大的尝试次数为代价获得的。我们看到，如果临界层数在49层的话，我们要尝试50次，而临界层数为100层的时候，尝试次数只有7次。但是，现在的问题是，全部情况下的最大尝试次数最小。这样，虽然在某些情况下，这种方法的性能很好。但是就最差情况而言，还是要尝试50次，好像还是有点大。这边，我们想起来，“二分查找法”的目标是平均性能最佳，并不是最差性能最佳。我们似乎走错了路！！！不过，方案二相比方案一来讲还是有进步的。
方案2似乎陷入了“短板效应”的泥沼，由于最坏情况下的坏性能制约了总体性能的提高。解决这个问题的总的原则应是：“一碗水端平”，尽量做到各种情况下的尝试次数尽量差不多。这正应合GOOGLE的信条Don't be evil，不以别的情况为代价换取另一些情况的指标的提高。做到“不伤害”.(呵呵，这是我瞎联想的)。那么，就照着这条路走吧，我假设每种情况下最大的尝试次数为x.
则第一次扔蛋的楼层应为x;
第二次扔蛋的楼层应为 x+(x-1);
…
依次类推。
从上面看到，每次我们增加的楼层都是前一次减1.我们所要保证的就是应该在增加的层数变成0之前到顶楼，所以有：
x+(x-1)+…+1≥100
这是一个等差数列，整理后有：
x2+x-200≥0
发现x≥14。
我们总结一下：
第一次在14楼扔，如果碎了的话从一楼再开始扔；
否则在14+13=27层扔，如果碎了的话从15层开始扔；
否则在27+12=39层扔，如果碎了的话从28层开始扔；
……
这样，最大尝试次数为14次就行了。不信你试试。
最后，为了体现严谨性，给出本题的模型：
转移方程：
minNum[n ] = min(1 + max(i – 1, minNum[n-i])) ，for 1≤i ≤n
边界条件:
minNum[0] = 0; minNum[1] = 1
这里，n为楼层数，i为起始楼层数。
据说这是一个动态规划问题，我还没来得及仔细研究。其实，我的感觉是，很多理论最初的来源都是很朴素的真理，只是我们没学懂，所以把它们想复杂了。所以，很好的理论就这样不被大多数人所理解了。
参考文献：
1. http://blog.csdn.net/TravelInHistory/archive/2006/12/07/1434098.aspx
2. http://classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html