What is a formal statement of the Dining Philosopher's Problem?
0
(The dining philosopher's problem is described here.)
I'm having trouble understanding whether or not the philosopher's act simultaneously. Do they all take one action simultaneously, then take their next action simultaneously? Or do they takes turns taking one action?
Is there a formal statement of the problem somewhere or a reduction of it to something that can be stated more rigorously?
discrete-mathematics computer-science
edited Nov 28 '18 at 13:48
Christian Blatter
172k7112326
asked Nov 28 '18 at 11:50
Damian Siniakowicz
163
add a comment |
0
(The dining philosopher's problem is described here.)
I'm having trouble understanding whether or not the philosopher's act simultaneously. Do they all take one action simultaneously, then take their next action simultaneously? Or do they takes turns taking one action?
Is there a formal statement of the problem somewhere or a reduction of it to something that can be stated more rigorously?
discrete-mathematics computer-science
edited Nov 28 '18 at 13:48
Christian Blatter
172k7112326
asked Nov 28 '18 at 11:50
Damian Siniakowicz
163
1
The dining philosophers problem involves acquiring and releasing resources over time, and falls under the "concurrent/parallel programming" umbrella. The formal tools for dealing with such problems exist, but are not widely known/used because (in my opinion) they are very cumbersome. There are some nice papers by Lamport and Dijkstra about how to reason formally in these systems, if you would like to poke around.
– Joppy
Nov 28 '18 at 12:55
1
However, in most situations like this, you should assume that each philosopher acts arbitrarily - they will wait an arbitrary amount of time before doing something, and if two philosophers try to (for example) pick up a fork at once, the tie is broken arbitrarily - one wins, one loses. Another reasonable assumption would be for ties to be broken by each backing off and resetting, and trying again at some (arbitrary) time in the future.
– Joppy
Nov 28 '18 at 12:57
1
There are various possible ways to formulate the problem of the dining philosophers. They could take actions simultaneously, sequentially in turn, or in an arbitrary sequence. Depending on how you define when the actions occur, you may have to adjust what the actions are. You have seen some particular formulation, and only someone who has seen the same formulation can tell you what it says.
– David K
Nov 28 '18 at 13:14
add a comment |
0
0
0
(The dining philosopher's problem is described here.)
I'm having trouble understanding whether or not the philosopher's act simultaneously. Do they all take one action simultaneously, then take their next action simultaneously? Or do they takes turns taking one action?
Is there a formal statement of the problem somewhere or a reduction of it to something that can be stated more rigorously?
discrete-mathematics computer-science
edited Nov 28 '18 at 13:48
Christian Blatter
172k7112326
asked Nov 28 '18 at 11:50
Damian Siniakowicz
163
(The dining philosopher's problem is described here.)
I'm having trouble understanding whether or not the philosopher's act simultaneously. Do they all take one action simultaneously, then take their next action simultaneously? Or do they takes turns taking one action?
Is there a formal statement of the problem somewhere or a reduction of it to something that can be stated more rigorously?
discrete-mathematics computer-science
discrete-mathematics computer-science
edited Nov 28 '18 at 13:48
Christian Blatter
172k7112326
asked Nov 28 '18 at 11:50
Damian Siniakowicz
163
edited Nov 28 '18 at 13:48
Christian Blatter
172k7112326
asked Nov 28 '18 at 11:50
Damian Siniakowicz
163
edited Nov 28 '18 at 13:48
Christian Blatter
172k7112326
edited Nov 28 '18 at 13:48
Christian Blatter
172k7112326
edited Nov 28 '18 at 13:48
Christian Blatter
172k7112326
172k7112326
asked Nov 28 '18 at 11:50
Damian Siniakowicz
163
asked Nov 28 '18 at 11:50
Damian Siniakowicz
163
asked Nov 28 '18 at 11:50
Damian Siniakowicz
163
163
1
The dining philosophers problem involves acquiring and releasing resources over time, and falls under the "concurrent/parallel programming" umbrella. The formal tools for dealing with such problems exist, but are not widely known/used because (in my opinion) they are very cumbersome. There are some nice papers by Lamport and Dijkstra about how to reason formally in these systems, if you would like to poke around.
– Joppy
Nov 28 '18 at 12:55
1
However, in most situations like this, you should assume that each philosopher acts arbitrarily - they will wait an arbitrary amount of time before doing something, and if two philosophers try to (for example) pick up a fork at once, the tie is broken arbitrarily - one wins, one loses. Another reasonable assumption would be for ties to be broken by each backing off and resetting, and trying again at some (arbitrary) time in the future.
– Joppy
Nov 28 '18 at 12:57
1
There are various possible ways to formulate the problem of the dining philosophers. They could take actions simultaneously, sequentially in turn, or in an arbitrary sequence. Depending on how you define when the actions occur, you may have to adjust what the actions are. You have seen some particular formulation, and only someone who has seen the same formulation can tell you what it says.
– David K
Nov 28 '18 at 13:14
add a comment |
1
The dining philosophers problem involves acquiring and releasing resources over time, and falls under the "concurrent/parallel programming" umbrella. The formal tools for dealing with such problems exist, but are not widely known/used because (in my opinion) they are very cumbersome. There are some nice papers by Lamport and Dijkstra about how to reason formally in these systems, if you would like to poke around.
– Joppy
Nov 28 '18 at 12:55
1
However, in most situations like this, you should assume that each philosopher acts arbitrarily - they will wait an arbitrary amount of time before doing something, and if two philosophers try to (for example) pick up a fork at once, the tie is broken arbitrarily - one wins, one loses. Another reasonable assumption would be for ties to be broken by each backing off and resetting, and trying again at some (arbitrary) time in the future.
– Joppy
Nov 28 '18 at 12:57
1
There are various possible ways to formulate the problem of the dining philosophers. They could take actions simultaneously, sequentially in turn, or in an arbitrary sequence. Depending on how you define when the actions occur, you may have to adjust what the actions are. You have seen some particular formulation, and only someone who has seen the same formulation can tell you what it says.
– David K
Nov 28 '18 at 13:14
1
1
The dining philosophers problem involves acquiring and releasing resources over time, and falls under the "concurrent/parallel programming" umbrella. The formal tools for dealing with such problems exist, but are not widely known/used because (in my opinion) they are very cumbersome. There are some nice papers by Lamport and Dijkstra about how to reason formally in these systems, if you would like to poke around.
– Joppy
Nov 28 '18 at 12:55
The dining philosophers problem involves acquiring and releasing resources over time, and falls under the "concurrent/parallel programming" umbrella. The formal tools for dealing with such problems exist, but are not widely known/used because (in my opinion) they are very cumbersome. There are some nice papers by Lamport and Dijkstra about how to reason formally in these systems, if you would like to poke around.
– Joppy
Nov 28 '18 at 12:55
1
1
However, in most situations like this, you should assume that each philosopher acts arbitrarily - they will wait an arbitrary amount of time before doing something, and if two philosophers try to (for example) pick up a fork at once, the tie is broken arbitrarily - one wins, one loses. Another reasonable assumption would be for ties to be broken by each backing off and resetting, and trying again at some (arbitrary) time in the future.
– Joppy
Nov 28 '18 at 12:57
However, in most situations like this, you should assume that each philosopher acts arbitrarily - they will wait an arbitrary amount of time before doing something, and if two philosophers try to (for example) pick up a fork at once, the tie is broken arbitrarily - one wins, one loses. Another reasonable assumption would be for ties to be broken by each backing off and resetting, and trying again at some (arbitrary) time in the future.
– Joppy
Nov 28 '18 at 12:57
1
1
There are various possible ways to formulate the problem of the dining philosophers. They could take actions simultaneously, sequentially in turn, or in an arbitrary sequence. Depending on how you define when the actions occur, you may have to adjust what the actions are. You have seen some particular formulation, and only someone who has seen the same formulation can tell you what it says.
– David K
Nov 28 '18 at 13:14
There are various possible ways to formulate the problem of the dining philosophers. They could take actions simultaneously, sequentially in turn, or in an arbitrary sequence. Depending on how you define when the actions occur, you may have to adjust what the actions are. You have seen some particular formulation, and only someone who has seen the same formulation can tell you what it says.
– David K
Nov 28 '18 at 13:14
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3017054%2fwhat-is-a-formal-statement-of-the-dining-philosophers-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3017054%2fwhat-is-a-formal-statement-of-the-dining-philosophers-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
The dining philosophers problem involves acquiring and releasing resources over time, and falls under the "concurrent/parallel programming" umbrella. The formal tools for dealing with such problems exist, but are not widely known/used because (in my opinion) they are very cumbersome. There are some nice papers by Lamport and Dijkstra about how to reason formally in these systems, if you would like to poke around.
– Joppy
Nov 28 '18 at 12:55
1
However, in most situations like this, you should assume that each philosopher acts arbitrarily - they will wait an arbitrary amount of time before doing something, and if two philosophers try to (for example) pick up a fork at once, the tie is broken arbitrarily - one wins, one loses. Another reasonable assumption would be for ties to be broken by each backing off and resetting, and trying again at some (arbitrary) time in the future.
– Joppy
Nov 28 '18 at 12:57
1
There are various possible ways to formulate the problem of the dining philosophers. They could take actions simultaneously, sequentially in turn, or in an arbitrary sequence. Depending on how you define when the actions occur, you may have to adjust what the actions are. You have seen some particular formulation, and only someone who has seen the same formulation can tell you what it says.
– David K
Nov 28 '18 at 13:14