置頂隨筆
找工，其實早在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