Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005373OCamlOCaml generalpublic2011-10-10 11:122013-12-12 16:02
ReporterNickChapman 
Assigned To 
PrioritynormalSeverityfeatureReproducibilitysometimes
StatusacknowledgedResolutionopen 
PlatformOSOS Version
Product Version3.12.1 
Target VersionFixed in Version 
Summary0005373: Caml thread wont yield
DescriptionI have an example of an ocaml program using threads, which shows one
thread failing to yield & causing the execution of a second thread to
be completely blocked. This happens despite the non-yielding thread
continuously allocating.

example.ml

    let pr s = Printf.eprintf "%.3f : %s\n%!" (Unix.gettimeofday()) s

    let nanosleep f = ignore (Unix.select [] [] [] f)

    let rec beater_loop () =
      pr "beat";
      nanosleep 0.1;
      beater_loop()

    let rec spin_loop p i =
      let p = (let (a,b) = p in (b,a)) in (* allocate every iteration *)
      if i = 0
      then ()
      else spin_loop p (i-1)

    let main () =
      let _t = Thread.create beater_loop () in
      nanosleep 1.0;
      pr "spin a while";
      let p = ("foo","bar") in
      spin_loop p 2_000_000_000; (* approx 5 secs *)
      pr "spin a while..done";
      nanosleep 1.0;
      exit 0

    let () = main()


build using:
    ocamlopt -thread -c example.ml
    ocamlopt.opt -thread unix.cmxa threads.cmxa example.cmx -o example.exe


The behaviour when running this program is not deterministic, but more
often that not it has output something like:


    1317804008.719 : beat
    1317804008.818 : beat
    1317804008.918 : beat
    1317804009.019 : beat
    1317804009.119 : beat
    1317804009.219 : beat
    1317804009.319 : beat
    1317804009.419 : beat
    1317804009.519 : beat
    1317804009.619 : beat
    1317804009.718 : spin a while
    1317804014.271 : spin a while..done
    1317804014.271 : beat
    1317804014.372 : beat
    1317804014.473 : beat
    1317804014.574 : beat
    1317804014.675 : beat
    1317804014.776 : beat
    1317804014.877 : beat
    1317804014.978 : beat
    1317804015.079 : beat
    1317804015.180 : beat

The point to look for is that there are no "beat" messages for the 5
seconds between "spin a while" & "...done". (Note: sometimes there are
beats while spinning, and sometimes they start and stop - but in most
runs there are none.)

It seems the spinning thread is correctly, periodically releasing &
re-aquiring the lock, every 50ms when the c-ticker thread makes
allocation fail the heap limit check, but that this in not enough to
make the thread yield. It seems that previously sched_yield() was
used, but the call is currently elided.

  ocaml/otherlibs/systhreads/st_stubs.c

    CAMLprim value caml_thread_yield(value unit) /* ML */
    {
      if (st_masterlock_waiters(&caml_master_lock) == 0) return Val_unit;
      enter_blocking_section();
      st_thread_yield();
      leave_blocking_section();
      return Val_unit;
    }

  ocaml/otherlibs/systhreads/st_posix.h

    static void INLINE st_thread_yield(void)
    {
    #ifndef __linux__
      /* sched_yield() doesn't do what we want in Linux 2.6 and up (PR#2663) */
      sched_yield();
    #endif
    }

Without sched_yield, the sequence of calls executed by the thread
owning the masterlock reduces to...

  enter_blocking_section();
  leave_blocking_section();

which reduces to...

  st_masterlock_release
  st_masterlock_acquire

which reduces to..

      pthread_mutex_unlock(&m->lock);
      pthread_cond_signal(&m->is_free);

      pthread_mutex_lock(&m->lock);


If another thread is already waiting on the condition variable & mutex
pair, we might hope that it will be next to acquire the mutex, but the
semantics of posix threads offer no such guarantees.

And in practice is appears that more often than not, the same thread
which just unlocked the mutex immediately re-locks it. And so even in
examples with just two threads contending for the mytex, one thread
can be permanently starved.


Tagspatch
Attached Files? file icon st_posix.h [^] (11,565 bytes) 2011-10-11 12:17
patch file icon ocaml-explicit-thread-yield-3.12.1.patch [^] (6,972 bytes) 2011-10-18 12:11 [Show Content]

- Relationships

-  Notes
(0006159)
lefessan (developer)
2011-10-11 12:22

I attached a new "st_posix.h" that I think fixes this problem. It introduces a queue of active threads, waiting to take the master lock. When a thread releases the lock, all threads are woken up, and only the first one on the queue can take it. So, scheduling between these threads should be mostly fair.

It is implemented using a cons put on the thread local stack, so it has no limit on the number of active threads, and the queue has two pointers, one to the head, one to the tail, so that insertion and deletions are in one step. It would probably not work if it were possible to kill threads, but killing threads is not possible with OCaml systhreads, so it is ok.
(0006166)
xleroy (administrator)
2011-10-16 18:55

Fairness in thread scheduling is a delicate issue: whole books have been written about it. Linux's (2.6 and up) scheduler is willing to sacrifice fairness entirely to wring a little more throughput out of the system (this was confirmed to me by one of the authors of said scheduler). In particular, sched_yield(), which used to implement a pretty good approximation to round-robin, was deliberately sabotaged in 2.6 (it makes the yielding thread give up its time quota entirely), rendering it unusable with Caml's system threads. (OpenOffice was similarly affected.)

In the end, I don't think we care enough about fairness in Caml to try to restore it on top of an unfair OS scheduler. "Real" threaded applications (those doing I/O and inter-thread synchronization) work just fine without fairness. I reclassify this PR as a feature wish, but doubt it will be granted.

Concerning Fabrice Le Fessant's patch: restarting all threads at every yield in order for just one to run and all other to go back to sleep is a complete no-no. Try it with 500 threads and see...
(0006167)
lefessan (developer)
2011-10-17 09:58

500 threads ? I didn't know there were such OCaml applications. Anyway, above a few tens of threads, using threads for I/O is a complete waste of resources, and the runtime should give incentives to avoid that (by using an expensive fair scheduler ;-) ).

Anyway, it is still possible to have one condition per thread (allocated once on thread creation), and to signal only the condition of the first thread on the queue when the lock is released. Then, any thread entering the queue would also make sure it signals that first thread too to avoid stalling the scheduler. I will experiment some code around this.
(0006168)
ygrek (reporter)
2011-10-17 16:07
edited on: 2011-10-17 16:17

Just for the record, I have an application with circa 1000 threads running just now :) Most of the threads - when active - are executing C++ code but are launched from ocaml. Not that it couldn't have used 10 times less threads, but it was most easy to code this way :)

(0006171)
lefessan (developer)
2011-10-18 12:14

I uploaded a new patch: this one uses one condition per waiting thread, so only the first one on top of the queue is signaled. Conditions are allocated when a thread needs to wait, if none is available. Otherwise, they are reused. Every thread that terminates tries to free one condition, so the number of allocated conditions is bound by the number of threads, never more, probably always much fewer.
(0010444)
doligez (administrator)
2013-10-09 14:36

So how are you going to document this feature? By saying that scheduling is guaranteed to be fair?
(0010445)
lefessan (developer)
2013-10-09 14:48

If I remember well, the patch ensures that scheduling is fair, only among OCaml threads.

- Issue History
Date Modified Username Field Change
2011-10-10 11:12 NickChapman New Issue
2011-10-11 12:17 lefessan File Added: st_posix.h
2011-10-11 12:22 lefessan Note Added: 0006159
2011-10-16 18:55 xleroy Note Added: 0006166
2011-10-16 18:55 xleroy Severity minor => feature
2011-10-16 18:55 xleroy Status new => acknowledged
2011-10-16 18:55 xleroy Description Updated
2011-10-17 09:58 lefessan Note Added: 0006167
2011-10-17 16:07 ygrek Note Added: 0006168
2011-10-17 16:17 ygrek Note Edited: 0006168
2011-10-17 16:17 ygrek Note Edited: 0006168
2011-10-17 16:17 ygrek Note Edited: 0006168
2011-10-18 12:11 lefessan File Added: ocaml-explicit-thread-yield-3.12.1.patch
2011-10-18 12:14 lefessan Note Added: 0006171
2013-10-09 14:36 doligez Note Added: 0010444
2013-10-09 14:36 doligez Tag Attached: patch
2013-10-09 14:48 lefessan Note Added: 0010445


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker