This is going to be extremely light on details with respect to the current state of
the Parrot interpreter.
It is also going to be expressed in terms of Win32 APIs.
For both of these I apologise in advance. Time, and the "or forever hold your peace"
imperative has overridden my desire to do
otherwise.
My attempts to get up speed enough on the sources to work out how to apply the ideas I
am going to express, and to become
conversant with the *nix pthreads implementation and terminology, have moved too
slowly to afford me the opportunity to do more.
Hoping this stimulates ideas rather than a flame war.
Regards, Nigel Sandever.
------------------------
THE BASIS OF THE IDEA
Modern OSs succeed in having multiple threads of execution share a single copy of
process memory without the operations of one
thread being able to interfere with the state of another. The state of the code
running in those threads may be corrupted through
mismanagement. But the state of the threads themselves, their program counters,
registers and stacks cannot. The mechanisms for
this incorruptibility are:
Each operation (opcode) performed by the thread is atomic. The scheduler can
never interrupt a thread whilst an operation
is in progress. Only between operations.
Before the start of an operation, and after the end of one, the state of the
thread is entirely encapsulated within the
registers and stack. By swapping the entire state of the CPU register set, when
switching from one thread to another, the state of
each thread is preserved and reconstituted. No other mechanisms or interlocks are
required.
By analogy, a virtual machine that wishes to have multiple threads of execution must
achieve the same level of atomicity for each
operation it performs.
VIRTUAL MACHINE INTERPRETER
At any given point in the running of the interpreter, the VM register set, program
counter and stack must represent the entire
state for that thread. Once an opcode has started execution on a given thread, no
other thread of execution within that interpreter
much be allowed to start an operation until the first thread completes its opcode.
NON-VMI THREADS
ASYNCHRONOUS IO
Note that this does not mean that no other thread in the process can take a timeslice,
only that any thread that is allowed to run
should not be able to affect the state of the VM in question. A thread charged with
performing asynchronous reads on behalf of the
user program running within the VM interpreter can go ahead so long as it doesn't
directly modify the VMI state.
EVENT MANAGER THREAD
Equally, an event thread can also be run concurrently in the background to receive
asynchronous notifications (signals, messages,
asynchronous read completions etc.). It can then queue these events and set a flag
that the VMI can inspect between each iteration
of the "opcode execution loop" and action appropriately. This gives the benefit of
"safe signals" along with safe and timely
processing of other, similarly asynchronous events.
GARBAGE COLLECTION
The garbage collector would need to run *synchronously* with the interpreter opcode
loop. Effectively, it would be another (possibly
long running) opcode. An analogy of this are all the long running syscalls that
operate within a multi-tasking OS. Eg. synchronous IO,
virtual memory allocation, swapping etc. Just as virtual memory operations suspend the
affected processes until the operations are
complete, so garbage collection can be see as a virtual memory operation for the
virtual machine that requires the VMI to be
suspended until the operation is complete.
PREREQUISITES
The key is for the VM to be reentrant, and the use of (in win32 terms) a "critical
section".
REENTRANCY
Not only must the VMI be coded in a reentrant fashion, with all state addressed
through pointers (references) loaded into it's
Virtual register set. All the code underlying it, including syscalls and CRT must
equally be reentrant. Many APIs within many CRTs
*are not reentrant* (eg. strtok()). All state must be on a per-thread not a
per-process basis.
To this end, I would propose that no CRT APIs are used directly from the main code!
Instead, a full set of CRT-like macros would be inherited from a header file, where
either the real CRT API would be called, or an
alternative implementation. This header file would be conditionally included on the
basic of the target platform. This concentrates
the bulk, if not all, platform specific code into a single file (or set of files).
EXPANDING THE VIRTUAL MACHINE
What I am suggesting here is that the virtual machine analogy be extended to encompass
not just the VHLL-user-program view of
the registers and stack, but also it's view of the entire machine and underlying OS.
By so doing, not only does it allow those working on the core of the VMI to be
isolated from the underlying machine and OS
architecture. It allows them to extend the VMI's view of the world, beyond the
concepts of any single architecture. It also serves
the very practical purpose of avoiding the morass of platform-conditional compilation
directives in the bulk of the code, by
concentrating them in single (groups of) files, by platform.
ATOMICITY AND CRITICAL SECTIONS
Atomicity of the VMI opcodes can be achieved by having the core loop of the
interpreter enter and exit a critical section each time
it processes an opcode. For those not familiar with critical sections, they are a
(Win32) OS construct that prevents any
cooperating thread within a process, from having timeslice until the thread that
entered the critical section has exited.
Unlike semaphores and events, critsecs only operate within a single process. They are
relatively lightweight as there is no need to
enter kernel mode for their operation. They are, in effect a CPU specific "test and
set" operation applied to a piece of user mode
memory. Their lightweight nature means that they are faster than inter-process
semaphore mechanisms. When used in a process that
currently has only a single thread in operation, they have almost negligible
performance effect upon that thread. They also operate
correctly on SMP machines.
PROCESS GLOBAL STATE
Unavoidably process global state, such as filehandles etc., should only be usable
(from the user program being run by the VMI)
through the use of opcodes. Done this way, the serialisation of the opcodes at the VMI
level protects the global state.
THIS IS ONLY PART OF THE SOLUTION
None of the above addresses the problems of synchronising user program state. This
will still need to be addressed. This could either
be done by the user code through the use of something like the P5 :shared and lock()
mechanisms. Or preferably, transparently by the
VMI itself. Possibly, by having each PMC contain an 'in-use' flag that would be set
each time an opcode (method) was dispatched on a
PMC (object) and cleared when the operation completes.
If two threads attempt concurrent operations on the same PMC, the first thread
accessing the PMC sets the flag. When a second
thread attempt to access it, it finds the flag set and blocks (relinquishing it's
timeslice) until the first thread has completed and
cleared the flag. This doesn't solve the potential for deadlock problems arising from
the user-level code, though it may be possible
for the VMI to detect and diagnose these at runtime in a similar way that
deep-recursion detection is done in P5.
The cost to the single-threaded user application is for a test&set operation (a few
cycles), per object-method, plus the flag, which
need only be one bit, but maybe more efficiently coded as a 32-bit entity.
CONCLUSION (TENTATIVE, NO PROOF)
As all VHLL entities are PMCs at the VMI level, the sharing of data between threads at
the VHLL level is done entirely through
those PMCs. If no single PMC can be the subject of an opcode on two threads
concurrently, there /should/ be no opportunity for
conflict.
As all VMI internal state are encapsulated within the VMI register set, and each
thread has it's own set of registers, the internal
state of the VMI(s) should be equally secure.
Other internal housekeeping operations, memory allocation, garbage collection etc. are
performed as "sysopcodes", performed by the
VMI within the auspices of the critical section, and thus secured.
All asynchronous operations are performed by one or more non-VMI threads and do not
adjust the state of the VMI directly.
Instead, they queue notifications of events, and results to the VMI, and these are
detected by the VMI within the body of the main
loop. Once detected, an appropriate sysopcode is dispatched within the critical
section in the normal way.
SOME ADDITIONAL IDEAS
MEMORY MANAGEMENT
I've been looking at (glancing through) the memory management used by Parrot. The
basic concept of memory pools, if I have
understood them correctly, is to allocate similarly size object from the same pool.
The idea behind this is that it will be easier to
find a suitable size piece of memory available for reallocation having been GC'd, from
a pool dedicated to allocation of a similar size
to that needed. This should reduce the fragmentation of originally large allocations
into lots of small allocations, thereby reducing
the need for coalescence, and overall memory allocation.
The thought struck me that with the exception of strings and (other) compound data
types, all the instances of any given class are
always the same size. Where an existing class is dynamically extended in some way, the
result is the creation of a new (anonymous)
class as pre-existing instances of the original class would not be modified. As such,
the class would seem to be the ideal point at
which to pool the allocation and deallocation of memory.
If each class is given it's own memory pool that is a multiple of its instance size.
That pool effectively becomes an (C-style) array
of instances. As each element is exactly the right size, the only time the pool would
need to grow, is when all the existing elements
are in-use and another is required. Once an instance has been freed, it's slot in the
array would be available and exactly the right
size for the next instantiation. There would never be a requirement to coalesce
allocations. Whether the free slots are found
through a free space chain, or even a linear search, the GC would only need to process
this pool when a new instance of this class is
being allocated. It would then only need to scan a single pool of (same-sized)
reference objects to GC the existing instances.
If all references to this type where allocated from another pool dedicated to
references-to-this-class, that also hung off the
parent class, then the volume of references to be scanned would also be minimised.
If the larger segments of memory allocated for each pool, were allocated as virtual
memory segments, rather than as arbitrary
chunks of heap memory, the size of each individual pool can be grown in-place, at
runtime, without the need to copy then existing
space to the new larger allocation. And without the need to shuffle any other memory
pools around to accommodate the increase in
size. The OS's Virtual Memory Management takes care of the whole process. It also
becomes possible to reserve a sizeable pre-
allocation for important pools and those known to be likely to grow quickly, without
actually consuming the entire reservation from
the physical memory pool before it is actually needed. The OS will then take care of
notification of an individual pool's need to grow
through page faults and the growth becomes a process of simply committing another
(few) pages from the pre-allocation.
The memory requirements of variable size objects can be managed through Global Heap
and sub-allocation APIs as now.
Thread specific local storage required for the VMI's register stacks etc. can be
handled using Thread Local Storage APIs.
COOPERATIVE MULTIPROCESSING AND CO_ROUTINES.
Some applications benefit from the programmer being able to have much tighter control
over the scheduling of threads of execution
within the process. The extreme example of this are co-routines where control is
passed back and forth between two (or more) pieces
of code as the demands of the algorithm and data dictate rather than on the basis of
arbitrary time-slicing. Win32 has a concept of
Fibres. The are manually dispatched threads. A given thread (fibre) receives it's
timeslice in the normal way. However, it can
transfer the rest of it's current timeslice to another fibre on demand. The first
fibre remains suspended until the second fibre
transfers control back. The state of the first fibre is retained just as it would be
if the thread had been swapped by the scheduler.
In this way two (or more) fibres can cooperatively share their timeslices whilst other
threads (and processes) continue to receive
their timeslices in the normal way. This, I think, is the essence of co-routines?
I have no understanding (yet) of how the co-routines that Parrot is promising are
implemented on *nix systems. But unless the
concept of co-routines is encapsulated at the higher level with the implementation
being pushed down to platform specific code,
unless *nix also supports a concept very similar to Win32 fibres, it will be
impossible to utilise this "tailor made" OS facility. Thus,
the implementation of co-routines designed to operate well on *nix platforms is likely
to need to be emulated on Win32 with high
level requirements that won't fit well with the underlying OS. This could result in a
similarly sub-optimal emulation of a *nix
concept on Win32 as currently exists for the fork emulation. Other non-*nix platforms
would likely also suffer from this force fit
as well.
