fork
是linux下的一個系統調用，它的作用是産生一個子程序，子程序是目前程序的一個副本，它跟父程序有一樣的虛存内容，但也有一些不同點，讀者可以自己參考這裡。
但是，值得注意的是，父程序調用fork()後，fork()傳回的是生成的子程序(如果能順利生成的話)的ID。子程序執行的起點也是代碼中fork的位置，不同的是子程序fork()傳回的是0。如下代碼：
int i;
i = fork();
printf("%d\n",i);
int i;
i = fork();
printf("%d\n",i);
這段代碼中，父程序列印出來的值是“子程序id”，而子程序列印出來的是0。
www.spongeliu.com
好了，廢話介紹完了，讓我們切入正題，看兩個比較有意思的C語言題目。
www.spongeliu.com
第一題，計算下面代碼理論上總共列印了多少行：(網易2011筆試題)
#include
#include
#include
int main(){
int i;
for(i = 0; i<5; i++){
fork();
printf("%d\n",getpid());
fflush(stdout);
}
}
#include
#include
#include
int main(){
int i;
for(i = 0; i<5; i++){
fork();
printf("%d\n",getpid());
fflush(stdout);
}
}
問題解答：
這道問題并不難，最快的想法就是2+4+8+16+32，因為第一層的printf會有兩個程序列印，第二層會增加到4個，以此往下，就得出62行。
www.spongeliu.com
但我這裡打算采用另外一種方法，一種更加直覺的方法，就是直接數出來，這樣會避免大腦短路，而且對下一題目有幫助。
www.spongeliu.com
要直接數出來也很簡單，隻是有些繁瑣，因為每循環一次，都會列印一行并且産生一個子程序，子程序又會繼續循環列印并産生新的程序。我們可以在草稿紙上畫一棵樹，畫出每個程序的子程序以及循環次數，如果你眼力夠好，腦子不容易亂，這種方法很快會讓你得到正确答案。但我恰好腦子不是能夠保證清醒的人，畫了三遍樹得到的都是錯誤答案。
www.spongeliu.com
随後，我在紙上用了一種更簡單的資料結構——隊列進行計算，并且順利得出了答案。我是這樣計算的：
首先，主程序會循環5次，則我們将5壓入到隊列中：
queue =" 5 ";
sum = 0; //sum是總列印次數
queue =" 5 ";
sum = 0; //sum是總列印次數
主程序會循環5次，列印5行并且産生5個子程序，這5個子程序分别會列印5，4，3，2，1行，則我們将這5個數放入隊列，并将第一個5出隊列加入到sum中：
queue = " 5 4 3 2 1 ";
sum = sum + 5;
queue = " 5 4 3 2 1 ";
sum = sum + 5;
這樣，我們再取隊列首元素，即5，他會列印5行，并且生成4個子程序，子程序的分别會列印4，3，2，1行，我們把這4個數放入到隊列中，并将第一個5出隊列加入到sum中：
queue = " 4 3 2 1 4 3 2 1";
sum = sum + 5;
queue = " 4 3 2 1 4 3 2 1";
sum = sum + 5;
我們繼續重複上面的工作，取首元素4，他會列印4行，并且會聲稱3個子程序，子程序分别列印3，2，1行，重複上面的入隊列和出隊列操作：
queue = " 3 2 1 4 3 2 1 3 2 1 ";
sum = sum + 4;
queue = " 3 2 1 4 3 2 1 3 2 1 ";
sum = sum + 4;
這樣，以此重複以上的操作，當遇到元素1的時候，隻有出隊列而沒有入隊列的操作，因為隻列印1行的子程序不會再循環産生新的子程序。最後，當隊列中不再有元素的時候，sum就是總共列印的行數。
www.spongeliu.com
這種方法的有點是你可以很輕松、很清醒的在紙上把隊列寫出來并算出答案，缺點是如果你加法不好，很容易算錯答案！
www.spongeliu.com
第二題：問下面的代碼執行後總共産生了多少程序(不包括主程序)？(2009 EMC筆試)
#include
int main(){
fork();
fork() && fork() || fork();
fork();
}
#include
int main(){
fork();
fork() && fork() || fork();
fork();
}
這個題目跟上一個對比起來就稍微有點難度了，因為你就算畫樹也有可能算錯！
www.spongeliu.com
我個人感覺這個題目考察兩方面的知識：1、開頭所講的fork()傳回值；2、&&和||的運算。
www.spongeliu.com
讓我們現讨論下&&和||的運算再來繼續讨論這個題目。&&是“邏輯與”操作，如果兩個操作數有一個為0，則整個式子為0。标準C中規定，如果&&運算符的左操作數為0，則不計算右操作數；如果左操作數為1，才計算右操作數。
與之類似，||操作符是“邏輯或”操作，标準C規定如果||運算符左操作數為1，則不計算右操作數；如果左操作數為0，則計算右操作數。
www.spongeliu.com
繼續來看我們的題目，我們把題目中的5個fork()分别标記為A,B,C,D,E。則我們可以看到，主程序一共産生4個程序，分别産生在A,B,C,E位置上(B,C兩個fork()傳回值都不是0，是以B&&C不為0，是以不計算D)。讓我們仍然采用上題的算法，使用一個隊列：
首先，将主程序産生子程序的位置放到隊列中：
queue = " A B C E ";
sum = 0;
queue = " A B C E ";
sum = 0;
我們從隊列中取首元素A，我們分析A處産生的程序，發現它會在B, C, E三處産生子程序，我們把這三個元素插入到隊列中，并将sum+1。
queue = " B C E B C E "
sum ++;
queue = " B C E B C E "
sum ++;
然後，我們從隊列中取出首元素B，B處産生的子程序稍稍不一樣，因為子程序中B所代表的fork()傳回值為0，是以C得不到執行，而D會得到執行。是以，B處産生的子程序會執行D, E，将這兩個元素送入隊列，sum++：
queue = " C E B C E D E "
sum ++;
queue = " C E B C E D E "
sum ++;
下面，我們取首元素C，分析發現，C處産生的程序會執行D, E,送入隊列并且sum++:
queue = " E B C E D E D E "
sum ++;
queue = " E B C E D E D E "
sum ++;
同上一題一樣，依次這樣執行，遇到E則沒有元素入隊列，直到最後隊列為空，sum就是總共産生的程序個數。
www.spongeliu.com
最後，總結下這兩個題目，我感覺這裡要想不搞亂，最好的方法就是這樣子把并行的問題給串行話，因為就人腦來說，并行不一定比串行快^_^
歡迎大家留言進行讨論！
anyShare分享到：