6

Erlang is a well-known programming language that is famous (among other things) for it's lightweight threading. Erlang is usually implemented with the BEAM machine. The description (H'97) of the Erlang BEAM machine says

To guarantee a fair scheduling a process is suspended after a fixed number of reductions and then the first process from the queue is resumed.

I'm interested in this notion of reduction. According to (H'97) only the following BEAM commands count as a reduction:

  • C/CO/ResC: calls local/resident Erlang function
  • CL: Discard the current stack frame. Call a local Erlang function.
  • CEx/TrCEx: Call an external Erlang function (traced or otherwise).
  • CExL/TrCExL: Discard the current stack frame and call an external Erlang fuction (traced or otherwise).
  • M_C_r: Load the argument register x(0). Call a resident Erlang function.
  • M_CL_r: Load the argument register x(0). Discard the current stack frame. Call a local Erlang function.

All of those involve a function call. In contrast, calls to C-functions (e.g. TrC/TrCO) and calls to built-in functions (e.g. called by Bif_0_) don't count as reductions.

Questions. After this preamble, here is what I would like to know.

  1. Why are reductions used for scheduling between threads, and not time-slices?
  2. Why do only the above commands advance the reduction counter?
  3. The description in (H'97) is a bit dated, how does contemporary Erlang handle scheduling?

(H'97) B. Hausman, The Erlang BEAM Virtual Machine Specification.

Seki
  • 11,135
  • 7
  • 46
  • 70
Martin Berger
  • 1,120
  • 9
  • 19

2 Answers2

6

I'll try to answer you questions.

1) The main reason for not using time slices is performance and portability. It is quite expensive to read a monotonic time value from the operating system, and if we have to do it for every function call, the overhead becomes quite large. The cost also varies quite a lot on different OS's. The reduction counting mechanic however only requires the machine to be good at decrementing integers, which most machines are.

2) They don't. That list, as you say, is very outdated. Much of the way the VM works has been rewritten since. As a general rule of thumb; a function call (not the return) or anything that may take an unknown amount of time counts reductions. This includes bifs, nifs, gc, sending/receiving messages and probably more that I cannot think of right now.

3) Scheduling and pre-emption are very different things. You may want to see my webinar I did a couple a years ago about how scheduling is done: https://www.youtube.com/watch?v=tBAM_N9qPno

Lukas
  • 5,182
  • 26
  • 17
  • @Lucas, thanks. That's very informative. I wonder if there is a way to write (long, straight line) Erlang programs that hog the CPU because they don't involve code that decreases the reduction counter. – Martin Berger Aug 04 '15 at 16:34
  • Yes, but as there are no loop constructs in Erlang besides function calls, that is only a theoretical problem. – Lukas Aug 04 '15 at 21:06
  • @Lucas True, but even if you unroll a function a bit, say 4 recursive unwindings, you should get roughly 4 times more time on the CPU in comparison with the original function. Not saying it's a problem in practise. – Martin Berger Aug 05 '15 at 07:42
4

I only know the answer to the first question:

  1. Time slices are not necessarily accurate on all platforms and operating systems; using reductions ensures a uniform behaviour in all environments
I GIVE TERRIBLE ADVICE
  • 9,578
  • 2
  • 32
  • 40