From: Tomas Pospisek Date: 2007-03-06T01:12:49+09:00 Subject: Re: replacing the use of gettimeofday in the scheduler Quoting Tomas Pospisek : > Quoting Yukihiro Matsumoto : > > > In message "Re: replacing the use of gettimeofday in the scheduler" > > on Fri, 2 Mar 2007 08:07:20 +0900, "Avdi Grimm" 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 > #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 It's funny to note, that the identical problem was recently reported against Python [1], that the discussion contains also the two proposed approaches [2] and that there's no decision yet on how to proceed and thus the bug is still open. So Ruby is not alone :-) *t [1] https://sourceforge.net/tracker/index.php?func=detail&aid=1607041&group_id=5470&atid=105470 [2] https://sourceforge.net/tracker/index.php?func=detail&aid=1607149&group_id=5470&atid=305470 ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.