The dining philosophers problem illustrates non-composability of low-level synchronization primitives like semaphores. It is a modification of a problem posed by Edsger Dijkstra.

Five philosophers, Aristotle, Kant, Spinoza, Marx, and Russell (the tasks) spend their time thinking and eating spaghetti. They eat at a round table with five individual seats. For eating each philosopher needs two forks (the resources). There are five forks on the table, one left and one right of each seat. When a philosopher cannot grab both forks it sits and waits. Eating takes random time, then the philosopher puts the forks down and leaves the dining room. After spending some random time thinking about the nature of the universe, he again becomes hungry, and the circle repeats itself.

It can be observed that a straightforward solution, when forks are implemented by semaphores, is exposed to deadlock. There exist two deadlock states when all five philosophers are sitting at the table holding one fork each. One deadlock state is when each philosopher has grabbed the fork left of him, and another is when each has the fork on his right.

There are many solutions of the problem, program at least one, and explain how the deadlock is prevented.

 
'=========================
class RoundTableWith5Seats
'=========================
 
  % hungry    0
  % beingUsed 1
  % putDown   0
  % empty     0
 
  sys fork[5], plate[5],chair[5],philosopher[5]
  sys first
 
  method AddPasta() as sys
    function rand() as sys
      static seed=0x12345678
      mov eax,seed
      rol eax,7
      mul seed
      xor eax,0x5335ABD9
      mov seed,eax
      return seed
    end function
    return 4+(rand() and 15)
  end method
 
  method dine()
  first++ 'PRIORITY DINER
  if first>5 then first-=5
  for i=1 to 5
    kl=first+i-1
    kr=first+i
    if kl>5 then kl-=5
    if kr>5 then kr-=5
    if philosopher(kl) = hungry then
      if not fork(kl) or fork(kr) = beingUsed then
        plate(kl) = AddPasta()
        fork(kl)=beingUsed
        fork(kr)=beingUsed
      end if
    end if
    '
  next
  '
  for kl=1 to 5
    kr=kl+1 : if kr>5 then kr-=5
    if plate(kl)
      philosopher(kl)+=1 'PHILOSOPHER DINING
      --plate(kl)
      if plate(kl)=empty
        fork(kl)=PutDown
        fork(kr)=PutDown
      end if
    else
      if philosopher(kl)>0
        --philosopher(kl) 'PHILOSOPHER THINKING
      end if
    end if
  next
  '
  end method
 
  method show() as string
  cr=chr(13)+chr(10) : tab=chr(9)
  pr="philos" tab "activity" tab "plate" tab "fork L" tab "fork R" cr cr
  for i=1 to 5
  j=i+1 : if j>5 then j-=5
  if plate(i)=0 then
    if philosopher(i)=0 then
      act="waiting"
    else
      act="thinks"
    end if
  else
    act="dining"
  end if
  '
  pr+=i tab act tab plate(i) tab fork(i) tab fork(j) cr
  next
  return pr
  end method
 
end class
 
'TEST
'====
 
RoundTableWith5Seats Sopho
for i=1 to 100
  Sopho.dine
next
 
print Sopho.show
'putfile "s.txt",Sopho.show
 
'philos	action	plate	fork L	fork R
'
'1	waiting	0	0	1
'2	dining	8	1	1
'3	thinks	0	1	1
'4	dining	8	1	1
'5	thinks	0	1	0
 