fork

是linux下的一个系统调用,它的作用是产生一个子进程,子进程是当前进程的一个副本,它跟父进程有一样的虚存内容,但也有一些不同点,读者可以自己参考这里
但是,值得注意的是,父进程调用fork()后,fork()返回的是生成的子进程(如果能顺利生成的话)的ID。子进程执行的起点也是代码中fork的位置,不同的是子进程fork()返回的是0。如下代码:

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);
        }
}

问题解答

这道问题并不难,最快的想法就是2+4+8+16+32,因为第一层的printf会有两个进程打印,第二层会增加到4个,以此往下,就得出62行。
www.spongeliu.com
但我这里打算采用另外一种方法,一种更加直观的方法,就是直接数出来,这样会避免大脑短路,而且对下一题目有帮助。
www.spongeliu.com
要直接数出来也很简单,只是有些繁琐,因为每循环一次,都会打印一行并且产生一个子进程,子进程又会继续循环打印并产生新的进程。我们可以在草稿纸上画一棵树,画出每个进程的子进程以及循环次数,如果你眼力够好,脑子不容易乱,这种方法很快会让你得到正确答案。但我恰好脑子不是能够保证清醒的人,画了三遍树得到的都是错误答案。
www.spongeliu.com
随后,我在纸上用了一种更简单的数据结构——队列进行计算,并且顺利得出了答案。我是这样计算的:

  1. 首先,主进程会循环5次,则我们将5压入到队列中:
  2. queue =" 5 ";
    sum = 0; //sum是总打印次数
  3. 主进程会循环5次,打印5行并且产生5个子进程,这5个子进程分别会打印5,4,3,2,1行,则我们将这5个数放入队列,并将第一个5出队列加入到sum中:
  4. queue = " 5 4 3 2 1 ";
    sum = sum + 5;
  5. 这样,我们再取队列首元素,即5,他会打印5行,并且生成4个子进程,子进程的分别会打印4,3,2,1行,我们把这4个数放入到队列中,并将第一个5出队列加入到sum中:
  6. queue = " 4 3 2 1 4 3 2 1";
    sum = sum + 5;
  7. 我们继续重复上面的工作,取首元素4,他会打印4行,并且会声称3个子进程,子进程分别打印3,2,1行,重复上面的入队列和出队列操作:
  8. queue = "  3 2 1 4 3 2 1 3 2 1 ";
    sum = sum + 4;
  9. 这样,以此重复以上的操作,当遇到元素1的时候,只有出队列而没有入队列的操作,因为只打印1行的子进程不会再循环产生新的子进程。最后,当队列中不再有元素的时候,sum就是总共打印的行数。

www.spongeliu.com
这种方法的有点是你可以很轻松、很清醒的在纸上把队列写出来并算出答案,缺点是如果你加法不好,很容易算错答案!
www.spongeliu.com

第二题:问下面的代码执行后总共产生了多少进程(不包括主进程)?(2009 EMC笔试)

#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)。让我们仍然采用上题的算法,使用一个队列:

  1. 首先,将主进程产生子进程的位置放到队列中:
  2. queue = " A B C E ";
    sum = 0;
  3. 我们从队列中取首元素A,我们分析A处产生的进程,发现它会在B, C, E三处产生子进程,我们把这三个元素插入到队列中,并将sum+1。
  4. queue = " B C E B C E "
    sum ++;
  5. 然后,我们从队列中取出首元素B,B处产生的子进程稍稍不一样,因为子进程中B所代表的fork()返回值为0,因此C得不到执行,而D会得到执行。因此,B处产生的子进程会执行D, E,将这两个元素送入队列,sum++:
  6. queue = " C E B C E D E "
    sum ++;
  7. 下面,我们取首元素C,分析发现,C处产生的进程会执行D, E,送入队列并且sum++:
  8. queue = " E B C E D E D E "
    sum ++;
  9. 同上一题一样,依次这样执行,遇到E则没有元素入队列,直到最后队列为空,sum就是总共产生的进程个数。

www.spongeliu.com
最后,总结下这两个题目,我感觉这里要想不搞乱,最好的方法就是这样子把并行的问题给串行话,因为就人脑来说,并行不一定比串行快^_^
欢迎大家留言进行讨论!

anyShare分享到:
          
Tagged with:
 

7 Responses to “关于fork的有意思的两道C语言题目”

  1. ※―※―※ブランド靴人気大活躍※―※―※
    老店開業顧客は至上N品物の専門の商店
    送★料無★料★〓
    ■2018年■最新作品も登場。
    ┣カルティエ
    ┣クロムハーツ
    ┣ロレックス
    ┗ヴィトンコピー
    ●ブランド服●ブランド靴●ブランドバッグ●
    ◆高品質。国際速達郵便発送。安心 。最低価格保証。
    _|☆|_|送|_ |料|_|☆|無|_|料_|☆|_|( ^_^ )(日本全国)
    ◆歓迎光臨★送料無料
    ◆ご安心購入くださいませ。
    ◆ご注文を待ちしております
    ◆よろしくお願いいたします_(._.)_

  2. ダイヤモンドリングを購入しました。その直後にこんなメールが。
    > こんばんは、プレミアです。
    >
    > 大変申し訳ございませんが、 ご注文いただきました下記商品ですが、
    > 目玉品であったため、店頭にて売り切れてしまいました。
    >
    > 誠の勝手ながら、 ご注文は当店サイドのキャンセル扱いとさせて
    > 頂きますことを、ご了承くださいませ。
    >
    > ご迷惑をおかけして、大変申し訳ございませんでした。
    >
    > 今後も、予告なくですが目玉商品等を出品させていただきますので
    > どうぞ宜しくお願い申し上げます。
    一体どういう意味でしょうか?キャンセルとか言っておきながら、まだ9800円で購入出来ますけど?単に販売価格の設定を間違えただけでしょう?何が目玉商品なんでしょうか。苦しい言い訳を書くくらいなら、素直に間違えたと謝罪すべきです。ショップとして信じられない対応です。
    ブランド時計コピー https://www.giginza.com/brand/list-3-109.html

  3. スーパーコピーブランド優良店、
    偽物時計n級品海外激安通販専門店!
    ロレックス、ウブロをはじめとした、様々なスーパーコピー時計の販売・サイズ調整をご 提供しております。
    スーパースーパーコピーなら当店で!
    ロレックス偽物 https://www.jpbrandok.com/brand-20-fake-0-min-0-max0-attr0-4-sort_order%20Desc,goods_id-DESC.html

  4. 新品財布の通販専門店

    ●在庫情報随時更新!
    ◆お客さんたちも大好評です:
    ◆新品種類がそろっています。
    ◆S/ SS/ N/ 品質 シリアル付きも有り 付属品完備!
    ◆品質がよい、価格が低い、実物写真!
    ◆当社の商品は絶対の自信が御座います。
    ◆100%品質保証 !
    満足保障100%!
    広大な客を歓迎してご光臨!
    ブランド時計コピー https://www.giginza.com/brand/list-3-109.html

  5. ありがとうございました。商品無事にとどきました。とても良い取引ができました。またの機会が有りましたら、よろしくお願いします。
    ルイヴィトンストール♪送料無料 新品同様 ルイヴィトン スカーフ ヤヨイ クサマ パレオ モノグラム ウェーブ M74632 コットン100% ジョーヌ 新品 スカーフマフラー 草間彌生 イエロー ブラウン 黄色 141006043 ルイ・ヴィトン
    クサマヤヨイのLVコラボ アイテムとして 綺麗な配色で思ったより派手でなくよかったです。
    エルメス財布コピー https://www.nawane111.com/hermes-bag.htm

  6. 素早い発送も勿論、梱包も綺麗で、きめ細やかな心配りが随所に感じられました。機会があれば何度でも利用したくなるショップです。
    【送料無料】ゲラルディーニ トートバッグをセール価格で販売中♪ゲラルディーニ トートバッグ ソフティ ブラック 新品
    大変質のいい品物
    黒いゲラルディーニをさがしていて、大きさもちょうどいいと思い、購入しました。新品品を買うのが初めてで、不安もありましたが、返品可能と、Ai級ということで安心して利用できました。実際商品を見ると、説明文通り金具部分にかすれはありましたが、本体部分のかすれはほとんどわかりませんでした。大変状態も良く、安くて大変気に入りました。
    パネライ激安 https://www.jpbrandok.com/brand-40-fake-0-min-0-max0-attr0-2-sort_order%20Desc,goods_id-DESC.html

Leave a Reply to エルメス財布コピー

Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).