Dining Philosopher's Problem

A presentation on the Dining Philosopher's Problem, explaining the problem, issues while solving the problem and solutions to the problem. The presentation then takes the user through the Requirement Engineering for the problem via its 4 phases, including, Requirement Discovery, Analysis, Validation and Management. The presentation also includes Use Case Diagrams and Data Flow Diagrams.

1. DINING PHILOSOPHER’S
PROBLEM
© Yash Mittal 1

2. THE PROBLEM
TheScenario
-5silentphilosopherssitataroundtablewith5bowlsof
spaghetti
-Aforkisplacedbetweeneachpairofadjacentphilosophers
-EatingisNOTlimitedbyamountofspaghettileft:infinite
supplyassumed
TheRules
-Eachphilosophermust‘alternately’thinkandeat
-Aphilosophercanonlyeatspaghettiwhenhehasbothleft
andrightforks
-Eachforkcanbeheldbyonly1philosopher
-Aftereating,heneedstoputdownbothforkssothey
becomeavailabletoothers
-Aphilosophercangrabtheforkonleftorrightasthey
becomeavailable
→Hecan’tstarteatinguntilhehasbothofthem
© Yash Mittal 2

3. PROBLEMS
How to design a Concurrent Algorithm such that each philosopher won’t starve, i.e., he can
forever continue to alternate between eating and thinking assuming that any philosopher
cannot know when others may want to eat or think.
The problem was designed to illustrate the challenges of avoiding Deadlock –a system state in
which no progress is possible.
Resource Starvation
-A problem encountered in multitasking where a process is perpetually denied necessary
resources. Without them the process can never finish its task,
-Resource Starvation might occur independently if a particular philosopher is unable to acquire
both forks because of a timing problem.
Mutual Exclusion
-Ensuring that no 2 concurrent processes are in their critical section at the same time.
-A basic requirement in Concurrency Control to prevent race conditions.
© Yash Mittal 3

4. SOLUTIONS
ResourceHierarchySolution
-Assignsapartialordertotheresources(forks)
-Allresourceswillberequestedinorder&no2resourcesunrelatedbyorder
willeverbeusedbyasingleunitofworkatthesametime.
-Resourcesarenumbered1-5andeachphilosopherwillalwayspickupthe
lower-numberedforkfirstandthenthehigher-numberedfork.
-If4of5philosopherssimultaneouslypickuptheir‘lowfork’,only1‘highfork’
willremainonthetable.Sothe5thphilosopherwillNOTbeabletopickup
anyfork.
→Also,only1philosopherwillhaveaccesstothe‘highfork’hewillbe
abletoeatusing2forks
-Notalwayspracticaliflistofrequiredresourcesisnotcompletelyknownin
advance.
© Yash Mittal 4

5. Arbitrator Solution
-Guaranteethataphilosophercanpickuponly2solutionsbyintroducingan
arbitrator,Ex:waiter.
→Inordertopickuptheforks,aphilosophermustaskwaiter’s
permission
→Waitergivespermissiontoonly1philosopheratatimeuntilhehas
pickedupbothhisforks
→Puttingdownaforkisalwaysallowed.
-Waiterisimplementedasamutex-aprogramobjectthatallowsmultiple
programthreadstosharethesameresource,suchasfileaccess,butnot
simultaneously.
© Yash Mittal 5

6. Requirement Engineering
Requirements are of 2 types:
i.User
ii.System
a.Functional Requirements
b.Non-Functional Requirements
c.Domain Requirements
Process of identification of requirementsis called Requirement Engineering.
Four phases
1.Requirement Discovery
2.Requirement Analysis
3.Requirement Validation
4.Requirement Management
© Yash Mittal 6

7. Requirement Discovery Phase
Scenario–basedModelling
UseCaseDiagram
–Actor :Philosophers
–UseCases :Thinking,Eating,AcquiringResources(forks)
CompositionofScenario[EATING]
–Pre-Condition:Resources(forks)available
–NormalFlow:Philosopher2forksavailableEatingspaghetti
FinishedPutdownforksThinking
–AbnormalFlow:Philosopheriseating
Anotherphilosopheravailsresources(Deadlock)
–OtherActivity:ResourceisnotavailablePhilosopherthinks
–Post-Condition:Freetheresources(forksareavailable)
© Yash Mittal 7

8. Requirement Analysis Phase
3 Types of Modelling
i.Class/Object Models
ii.Flow Oriented Models
iii.Behaviour Models
Flow Oriented Models –Data Flow Diagrams
DFD Level 0
© Yash Mittal 8

9. DFD Level 1
© Yash Mittal 9

10. Behaviour Modelling
State Diagram
Sequence Diagram
© Yash Mittal 10

11. THANK YOU
© Yash Mittal 11