13

次のすべてが満たされるかどうかが保証される場合は、食事する哲学者の問題を解決するアルゴリズムを確認する必要があります。

  • デッドロックの可能性はありません。
  • 飢餓の可能性はありません。

問題を解決するために箸のセマフォを使用しています。

これが私のコード（アルゴリズム）です：

while(true)
{
    // He is Hungry
    pickup_chopsticks(i);

    // He is Eating...
    drop_chopsticks(i);

    // He is thinking
}

// ...

void pickup_chopsticks(int i)
{
    if(i % 2 == 0) /* Even number: Left, then right */
    {
        semaphore_wait(chopstick[(i+1) % NUM_PHILOSOPHERS]);
        semaphore_wait(chopstick[i]);
    }
    else /* Odd number: Right, then left */
    {
        semaphore_wait(chopstick[i]);
        semaphore_wait(chopstick[(i+1) % NUM_PHILOSOPHERS]);
    }
}

void drop_chopsticks(int i)
{
    semaphore_signal(chopstick[i]);
    semaphore_signal(chopstick[(i+1) % NUM_PHILOSOPHERS]);
}

ここでデッドロックの可能性はないと確信していますが、ここで飢餓の問題が発生する可能性はありますか？はいの場合、どうすれば解決できますか？

4

2 に答える 2

17

定義。哲学者は、使用できないセマフォを待機していない場合に有効になります。実行は、有効な哲学者によって実行されるステップの無限のシーケンスです。無限に有効にされたすべての哲学者がしばしば無限に多くのステップを踏むならば、処刑は非常に公平です。食事する哲学者の解決策は、すべての非常に公正な処刑において、すべての哲学者が無限に頻繁に食事をする場合に限り、飢餓のないものです。

定理。非食事する哲学者がセマフォを保持しない、ループやデッドロックのない食事する哲学者のソリューションはすべて、飢餓のないものです。

証拠。矛盾を得るために、ある哲学者（彼をフィルと呼ぶ）が有限の頻度でしか食事をしないという非常に公正な処刑が存在すると仮定します。この実行が実際に行き詰まっていることを示します。

ループがないのでpickup_chopsticks、drop_chopsticksPhilは有限の数のステップしか実行しません。最後のステップは、semaphore_wait箸iで言うことです。実行は非常に公平であるため、箸iは、ある有限の時間以降、必然的に継続的に使用できなくなります。クエンティンを箸iの最後の持ち主にしましょう。クエンティンが無限に多くのステップを踏んだ場合、彼はsemaphore_signaliを箸にかけるので、クエンティンも無限に多くのステップを踏みます。次に、クエンティンは箸jを待っています。これは、同じ議論により、時間の終わりまで継続的に利用できず、（たとえば）ロバートによって保持されています。semaphore_wait限りなく多くの哲学者の間でsの連鎖をたどることによって、私たちは必然的にデッドロックであるサイクルに到達します。

QED

于 2011-11-25T23:03:09.687 に答える
5

私はこれを何年も使用していませんが、アルゴリズムを検証するために使用できるツールがあります。Promelaでアルゴリズムを作成する必要があります。

http://spinroot.com/spin/whatispin.html

http://en.wikipedia.org/wiki/Promela

于 2011-11-25T21:43:37.433 に答える