Quoting Yukihiro Matsumoto <matz / ruby-lang.org>:

> In message "Re: replacing the use of gettimeofday in the scheduler"
>     on Fri, 2 Mar 2007 08:07:20 +0900, "Avdi Grimm" <avdi / avdi.org> writes:
>
> |This might well be.  Not being a contributor to the Ruby kernel, I
> |don't know what the policy is: does Ruby only implement features which
> |can be built with pure POSIX, or can they have OS-specific
> |implementations?
>
> It can have OS-specific implementation, but I want the core behavior
> being common on most (if not all) platforms.  Besides that, I have no
> idea to fix this "bug" on _any_ platform right now.  Any idea?

So here's what I found out after a bit of research and my proposition for a
solution.

Most languages use native threads to implement multithreading so they do not
have to care about scheduling and blocking by themselves. There do not seem to
be many languages/runtimes that use green threads.

* the Gambc Scheme implementation is regarded as being very high quality
  wrt to its implementation of multithreading/green threads. Allthough it
  goes to great lengths to be portable, it seems to base its scheduling
  decisions on the "wall-clock"
  (gettimeofday and clock_gettime(CLOCK_REALTIME, ...) ), so I expect Gambc
  to suffer from the very same scheduling problems as Ruby.

* Python uses native threads but Stackless Python implements green threads
  scheduling by directly accessing the Pentium's internal clock through the
  RDTCS machine instruction. I have not checked how it implements sleep, i.e.
  whether and how hh:mm:ss.mm is calculated from it. This solution has
  evidently a very high hardcore coolness geek factor but is not very portable.

* The GNU Portable Threads Library is using gettimeofday as well thus...

So after a day or so of research I am realizing the shocking fact - what Matz
saw too - that the core of the problem is base POSIX not providing any
monotonic clock API and aparently everybody's scheduler being at the merci of
some sysadmin issuing a "date -s". If anybody knows any better, then pointers
are wellcome.

So I see three approaches for a solution:

1. eliminate the worst case:

   eval.c has a few places where the timeofday() function is used, almost
   exclusively to do something like the following:

     loop() {
         start:     start = timeofday()
                    do_something()
         meanwhile: elapsed_time = timeofday() - start
                    remaining_time = elapsed_time - interval_of_interest
                    if( remaining_time < 0 )
                        break;
                    else
                        # loop again
      }

   the code between start and meanwhile represents here a critical section
   where no one should on a system scale be allowed to mess with system time,
   which timeofday() doesn't guarantee.

   Thus what we *can* do is to at least guarantee that remaining_time
   *never ever* increases:

     if( remaining_time > previous_remaining_time )
        remaining_time = previous_remaining_time;
     # else
        previous_remaining_time = remaining_time;


2. Do it "right":

   Doing it right would require having a monotonic time source, which the
   REALTIME extension of POSIX provides through the
   clock_gettime( CLOCK_MONOTONIC, ... ) function.

   Thus Ruby could schedule correctly on systems that *do* implement the
   POSIX REALTIME extension and use the old "broken" method on the other
   systems or add system specific solutions for those at a later time/as
   needed/submitted.

   Linux and DragonFly BSD do have CLOCK_MONOTONIC but OSX does not seem
   to have it. If people want to check about whether their systems provide it,
   here's a test:

     #include <unistd.h>
     #ifdef _POSIX_MONOTONIC_CLOCK
     main() {
       printf("yes\n");
     }
     #endif


3. use Ruby's own thread_timer as a source or as a
   time_sanity_offset_correction

   However - I'm not sure whether this approach yields reliable results and
   does not additional unnecessary complexity



All solutions however have a semantic side effect: timeofday is being called
from:

   a) the scheduler
   b) from sleep()
   c) indirectly from timeout() through sleep()

guaranteeing that remaining_time never increases is good for
a) the scheduler and c) timeout(), but can break existing programs using
c) sleep(), in case someone was doing somthing along the lines of:

     # need to wake up at noon
     sleep_time = noon() - now()
     sleep( sleep_time )

With the current "broken" semantics, that would work just right, since with
the current implementation sleep() time would increase/decrease in parallel
with the "sysadmin" changing the system time with "date -s" or similar.

Thus the question here is: do we want the scheduler and timeout() to work as
naively expected even in a situation where "wall clock" suddenly changes or do
we want sleep to work correctly in the same situation. Do we want absolute "wall
clock" work right or do we want the relative "stop watch" to
work right?


I'd suggest to apply both solutions from above, that is:

a) eliminate the worst case behaveour, where "remaining_time" is growing with
   the current implementation Ruby has and

b) "do the right thing" and use clock_gettime( CLOCK_MONOTONIC, ... ) instead
   of gettimeofday where available.

Opinions? Shall I try to submit a patch?
*t

[1] http://www.opengroup.org/onlinepubs/009695399/functions/clock_settime.html

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.