[ECOS] [SMP] issues with bin_sem2 (dining philosopher test)

[sandeep <shimple0 at yahoo dot com>]

change_state :
......
   // Theoretically it is possible for all the philosophers to be
   // hungry but not waiting on semaphores.  But in practice this
   // means something is wrong.
   CHECK(false == all_hungry);

Philosopher :
......
   // Think for a bit
   self->delay((id+cycle++)%12);    // Cogito ergo sum...

   // I am now hungry, try to get the chopsticks
   change_state(id,'H');

   // Get the sticks
   first_stick->wait();


Consider two (for sake of example) threads (philosophers) in smp scenario -

The initial delay (and various interrupts happening on systems, different
interrupts handling associated with different processors) can cause a
situation (wrt code snippets mentioned above) where -

T1 finishes delay and comes back on processor P1
T1 goes to change_state on P1
T2 is waking up from it's delay on processor P2
T1 comes out of change_state and goes on to acquire first_stick on P1
T2 goes to change_state on P2 and mentioned CHECK fails.

kphilo.c also suffers from this issue.

with some (tick_timing, number of ticks per timeslice and usual factors on the
system) combination it could be possible to end up there on single processor
case also?

Some more issues with bin_sem2 test are -

* perhaps i missed something in my going through this test, as i couldn't find
  utility of "+1" in pstate size declaration.

  static char pstate[PHILOSOPHERS+1];

  in case of kphilo.c it is clear, as diag_write_string is used on pstate.

  btw, kphilo doesn't find a place in kernel/current/cdl and doesn't get built.
  a quick look at test file gives impression that it is not supposed to be in 
  public cvs repository. i wonder why it is there then? hence no more comments 
  on kphilo.


* in change_state

  "if (PHILO_LOOPS == state_changes++)"

  should be moved inside

  pstate_mutex.lock(); { ... } pstate_mutex.unlock();

  there are race conditions on updations to state_changes, so some updations
  might get lost. Hitting this on no-smp configuration should not be possible
  with standard ecos configuration. though losing of some updations can be 
  handled as harmless as in case of updations to cycle in Philosopher.

  advantage of this move is that only one thread would try to print
  FINISH message.

  btw, i am assuming decent compilers. If there are some compilers in use that
  generate code for mentioned "if .... ", at some optimisation level like --

  1. get current value of state_changes
  2. compare it with current value of PHILO_LOOPS for equality
  3. if check fails, go to step 5
  4. print FINISH message
  5. get current value of state_changes again
  6. increment it and store back

  with this kind of code generation, race conditions can yield a situation
  where state_changes can miss being equal (becomes greater) to PHILO_LOOPS
  at if check and later cause test to go on and on.

i haven't analysed the test thoroughly, but came across above issues in limited
analysis to answer an observation on SMP run of this test, where test FINISH
message was also printed and following that was the previously mentioned FAILed
check message about hunger.

sandeep



		
__________________________________ 
Do you Yahoo!? 
Yahoo! Mail - Find what you need with new enhanced search.
http://info.mail.yahoo.com/mail_250

-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss