erlangschedulingpreemptivegreen-threads

How does erlang implements preemptive scheduling with one OS thread?


I want to know how erlang's VM preempts the running code and contexts the stack. How it can be done in a language such as c?


Solution

  • The trick is that the Erlang runtime has control over the VM, so it can - entirely in userspace - keep track of how many VM instructions it's already executed (or, better yet, an estimate or representation of the actual physical computation required for those instructions - a.k.a. "reductions" in Erlang VM parlance) and - if that number exceeds some threshold - immediately swap around process pointers/structs/whatever and resume the execution loop.

    Think of it something like this (in kind of a pseudo-C that may or may not actually be C, but I wouldn't know because I ain't a C programmer, but you asked how you'd go about it in C so I'll try my darndest):

    void proc_execute(Proc* proc)
    {
        /* I don't recall if Erlang's VM supports different
           reduction limits for different processes, but if it
           did, it'd be a rather intuitive way to define process
           priorities, i.e. making sure higher-priority processes
           get more reductions to spend */
        int rds = proc->max_reductions;
    
        for (; rds > 0; rds--) {
            /* Different virtual instructions might execute different numbers of
               physical instructions, so vm_execute_next_instruction will return
               however many reductions are left after executing that virtual
               instruction. */
            rds = vm_execute_next_instruction(proc, rds);
            if (proc->exited) break;
        }
    }
    
    void vm_loop(Scheduler* sched)
    {
        Proc *proc;
    
        for (;;) {
            proc = sched_next_in_queue(sched);
            /* we'll assume that the proc will be null if the
               scheduler doesn't have any processes left in its
               list */
            if (!proc) break;
            proc_execute(proc);
        }
    }
    
    Proc* sched_next_in_queue(Scheduler* sched)
    {
        if (!sched->current_proc->exited) {
            /* If the process hasn't exited yet, readd it to the
               end of the queue so we can resume running it
               later */
            shift(sched->queue, sched->current_proc);
        }
        sched->current_proc = pop(sched->queue);
        return sched->current_proc;
    }
    

    This is obviously quite simplified (notably excluding/eliding a lot of important stuff like how VM instructions are implemented and how messages get passed), but hopefully it illustrates how (if I'm understanding right, at least) Erlang's preemptive scheduler and process model works on a basic level.