Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

3 How HPC-GAP organizes shared memory: Regions
 3.1 Thread-local regions
 3.2 Shared regions
 3.3 Ordering of shared regions
 3.4 The public region
 3.5 The read-only region
 3.6 Migrating objects between regions
 3.7 Region names
 3.8 Controlling access to regions
 3.9 Functions relating to regions
 3.10 Atomic functions
 3.11 Write-once functionality

3 How HPC-GAP organizes shared memory: Regions

HPC-GAP allows multiple threads to access data shared between them; to avoid common concurrency errors, such as race conditions, it partitions GAP objects into regions. Access to regions is regulated so that no two threads can modify objects in the same region at the same time and so that objects that are being read by one thread cannot concurrently be modified by another.

3.1 Thread-local regions

Each thread has an associated thread-local region. When a thread implicitly or explicitly creates a new object, that object initially belongs to the thread's thread-local region.

Only the thread can read or modify objects in its thread-local region. For other threads to access an object, that object has to be migrated into a different region first.

3.2 Shared regions

Shared regions are explicitly created through the ShareObj (3.9-9) and ShareSingleObj (3.9-15) primitives (see below). Multiple threads can access them concurrently, but accessing them requires that a thread uses an atomic statement to acquire a read or write lock beforehand.

See the section on atomic statements (3.9-43) for details.

3.3 Ordering of shared regions

Shared regions are by default ordered; each shared region has an associated numeric precedence level. Regions can generally only be locked in order of descending precedence. The purpose of this mechanism is to avoid accidental deadlocks.

The ordering requirement can be overridden in two ways: regions with a negative precedence are excluded from it. This exception should be used with care, as it can lead to deadlocks.

Alternatively, two or more regions can be locked simultaneously via the atomic statement. In this case, the ordering of these regions relative to each other can be arbitrary.

3.4 The public region

A special public region contains objects that only permit atomic operations. These include, in particular, all immutable objects (immutable in the sense that their in-memory representation cannot change).

All threads can access objects in the public region at all times without needing to acquire a read- or write-lock beforehand.

3.5 The read-only region

The read-only region is another special region that contains objects that are only meant to be read; attempting to modify an object in that region will result in a runtime error. To obtain a modifiable copy of such an object, the CopyRegion (3.9-29) primitive can be used.

3.6 Migrating objects between regions

Objects can be migrated between regions using a number of functions. In order to migrate an object, the current thread must have exclusive access to that object; the object must be in its thread-local region or it must be in a shared region for which the current thread holds a write lock.

The ShareObj (3.9-9) and ShareSingleObj (3.9-15) functions create a new shared region and migrate their respective argument to that region; ShareObj will also migrate all subobjects that are within the same region, while ShareSingleObj will leave the subobjects unaffected.

The MigrateObj (3.9-21) and MigrateSingleObj (3.9-22) functions migrate objects to an existing region. The first argument of either function is the object to be migrated; the second is either a region (as returned by the RegionOf (3.9-7) function) or an object whose containing region the first argument is to be migrated to.

The current thread needs exclusive access to the target region (denoted by the second argument) for the operation to succeed. If successful, the first argument will be in the same region as the second argument afterwards. In the case of MigrateObj (3.9-21), all subobjects within the same region as the first argument will also be migrated to the target region.

Finally, AdoptObj (3.9-26) and AdoptSingleObj (3.9-27) are special cases of MigrateObj (3.9-21) and MigrateSingleObj (3.9-22), where the target region is the thread-local region of the current thread.

To migrate objects to the read-only region, one can use MakeReadOnlyObj (3.9-35) and MakeReadOnlySingleObj (3.9-36). The first migrates its argument and all its subjobjects that are within the same region to the read-only region; the second migrates only the argument itself, but not its subobjects.

It is generally not possible to migrate objects explicitly to the public region; only objects with purely atomic operations can be made public and that is done automatically when they are created.

The exception are immutable objects. When MakeImmutable (Reference: MakeImmutable) is used, its argument is automatically moved to the public region.

gap> RegionOf(MakeImmutable([1,2,3]));
<public region>

3.7 Region names

Regions can be given names, either explicitly via SetRegionName (3.9-38) or when they are created via ShareObj (3.9-9) and ShareSingleObj (3.9-15). Thread-local regions, the public, and the readonly region are given names by default.

Multiple regions can have the same name.

3.8 Controlling access to regions

If either GAP code or a kernel primitive attempts to access an object that it is not allowed to access according to these semantics, either a "write guard error" (for a failed write access) or a "read guard error" (for a failed read access) will be raised. The global variable LastInaccessible will contain the object that caused such an error.

One exception is that threads can modify objects in regions that they have only read access (but not write access) to using write-once functions - see section 3.11.

To inspect objects whose contents lie in other regions (and therefore cannot be displayed by PrintObj (Reference: PrintObj) or ViewObj (Reference: ViewObj), the functions ViewShared (3.9-41) and UNSAFE_VIEW (3.9-42) can be used.

3.9 Functions relating to regions

3.9-1 NewRegion
‣ NewRegion( [name, ]prec )( function )

The function NewRegion creates a new shared region. If the optional argument name is provided, then the name of the new region will be set to name.

gap> NewRegion("example region");
<region: example region>

NewRegion will create a region with a high precedence level. It is intended to be called by user code. The exact precedence level can be adjusted with prec, which must be an integer in the range [-1000..1000]; prec will be added to the normal precedence level.

3.9-2 NewLibraryRegion
‣ NewLibraryRegion( [name, ]prec )( function )

NewLibraryRegion functions like NewRegion (3.9-1), except that the precedence of the region it creates is below that of NewRegion (3.9-1). It is intended to be used by user libraries and GAP packages.

3.9-3 NewSystemRegion
‣ NewSystemRegion( [name, ]prec )( function )

NewSystemRegion functions like NewRegion (3.9-1), except that the precedence of the region it creates is below that of NewLibraryRegion (3.9-2). It is intended to be used by the standard GAP library.

3.9-4 NewKernelRegion
‣ NewKernelRegion( [name, ]prec )( function )

NewKernelRegion functions like NewRegion (3.9-1), except that the precedence of the region it creates is below that of NewSystemRegion (3.9-3). It is intended to be used by the GAP kernel, and GAP library code that interacts closely with the kernel.

3.9-5 NewInternalRegion
‣ NewInternalRegion( [name] )( function )

NewInternalRegion functions like NewRegion (3.9-1), except that the precedence of the region it creates is the lowest available. It is intended to be used for regions that are self-contained; i.e. no function that uses such a region may lock another region while accessing it. The precedence level of an internal region cannot be adjusted.

3.9-6 NewSpecialRegion
‣ NewSpecialRegion( [name] )( function )

NewLibraryRegion (3.9-2) functions like NewRegion (3.9-1), except that the precedence of the region it creates is negative. It is thus exempt from normal ordering and deadlock checks.

3.9-7 RegionOf
‣ RegionOf( obj )( function )
gap> RegionOf(1/2);
<public region>
gap> RegionOf([1,2,3]);
<region: thread region #0>
gap> RegionOf(ShareObj([1,2,3]));
<region 0x45deaa0>
gap> RegionOf(ShareObj([1,2,3]));
<region 0x45deaa0>
gap> RegionOf(ShareObj([1,2,3], "test region"));
<region: test region>

Note that the unique number that each region is identified with is system-specific and can change each time the code is being run. Region objects returned by RegionOf can be compared:

gap> RegionOf([1,2,3]) = RegionOf([4,5,6]);
true

The result in this example is true because both lists are in the same thread-local region.

3.9-8 RegionPrecedence
‣ RegionPrecedence( obj )( function )

RegionPrecedence will return the precedence of the region of obj.

gap> RegionPrecedence(NewRegion("Test"));
30000
gap> RegionPrecedence(NewRegion("Test2", 1));
30001
gap> RegionPrecedence(NewLibraryRegion("LibTest", -1));
19999

3.9-9 ShareObj
‣ ShareObj( obj[[, name], prec] )( function )

The ShareObj function creates a new shared region and migrates the object and all its subobjects to that region. If the optional argument name is provided, then the name of the new region is set to name.

ShareObj will create a region with a high precedence level. It is intended to be called by user code. The actual precedence level can be adjusted by the optional prec argument in the same way as for NewRegion (3.9-1).

3.9-10 ShareLibraryObj
‣ ShareLibraryObj( obj[[, name], prec] )( function )

ShareLibraryObj functions like ShareObj (3.9-9), except that the precedence of the region it creates is below that of ShareObj (3.9-9). It is intended to be used by user libraries and GAP packages.

3.9-11 ShareSystemObj
‣ ShareSystemObj( obj[[, name], prec] )( function )

ShareSystemObj functions like ShareObj (3.9-9), except that the precedence of the region it creates is below that of ShareLibraryObj (3.9-10). It is intended to be used by the standard GAP library.

3.9-12 ShareKernelObj
‣ ShareKernelObj( obj[[, name], prec] )( function )

ShareKernelObj functions like ShareObj (3.9-9), except that the precedence of the region it creates is below that of ShareSystemObj (3.9-11). It is intended to be used by the GAP kernel, and GAP library code that interacts closely with the kernel.

3.9-13 ShareInternalObj
‣ ShareInternalObj( obj[, name] )( function )

ShareInternalObj functions like ShareObj (3.9-9), except that the precedence of the region it creates is the lowest available. It is intended to be used for regions that are self-contained; i.e. no function that uses such a region may lock another region while accessing it.

3.9-14 ShareSpecialObj
‣ ShareSpecialObj( obj[, name] )( function )

ShareLibraryObj (3.9-10) functions like ShareObj (3.9-9), except that the precedence of the region it creates is negative. It is thus exempt from normal ordering and deadlock checks.

3.9-15 ShareSingleObj
‣ ShareSingleObj( obj[[, name], prec] )( function )

The ShareSingleObj function creates a new shared region and migrates the object, but not its subobjects, to that region. If the optional argument name is provided, then the name of the new region is set to name.

gap> m := [ [1, 2], [3, 4] ];;
gap> ShareSingleObj(m);;
gap> atomic readonly m do
>      Display([ IsShared(m), IsShared(m[1]), IsShared(m[2]) ]);
>    od;
[ true, false, false ]

ShareSingleObj will create a region with a high precedence level. It is intended to be called by user code. The actual precedence level can be adjusted by the optional prec argument in the same way as for NewRegion (3.9-1).

3.9-16 ShareSingleLibraryObj
‣ ShareSingleLibraryObj( obj[[, name], prec] )( function )

ShareSingleLibraryObj functions like ShareSingleObj (3.9-15), except that the precedence of the region it creates is below that of ShareSingleObj (3.9-15). It is intended to be used by user libraries and GAP packages.

3.9-17 ShareSingleSystemObj
‣ ShareSingleSystemObj( obj[[, name], prec] )( function )

ShareSingleSystemObj functions like ShareSingleObj (3.9-15), except that the precedence of the region it creates is below that of ShareSingleLibraryObj (3.9-16). It is intended to be used by the standard GAP library.

3.9-18 ShareSingleKernelObj
‣ ShareSingleKernelObj( obj[[, name], prec] )( function )

ShareSingleKernelObj functions like ShareSingleObj (3.9-15), except that the precedence of the region it creates is below that of ShareSingleSystemObj (3.9-17). It is intended to be used by the GAP kernel, and GAP library code that interacts closely with the kernel.

3.9-19 ShareSingleInternalObj
‣ ShareSingleInternalObj( obj[, name] )( function )

ShareSingleInternalObj functions like ShareSingleObj (3.9-15), except that the precedence of the region it creates is the lowest available. It is intended to be used for regions that are self-contained; i.e. no function that uses such a region may lock another region while accessing it.

3.9-20 ShareSingleSpecialObj
‣ ShareSingleSpecialObj( obj[, name] )( function )

ShareSingleLibraryObj (3.9-16) functions like ShareSingleObj (3.9-15), except that the precedence of the region it creates is negative. It is thus exempt from normal ordering and deadlock checks.

3.9-21 MigrateObj
‣ MigrateObj( obj, target )( function )

The MigrateObj function migrates obj (and all subobjects contained within the same region) to the region denoted by the target argument. Here, target can either be a region object returned by RegionOf (3.9-7) or a normal gap object. If target is a normal gap object, obj will be migrated to the region containing target.

For the operation to succeed, the current thread must have exclusive access to the target region and the object being migrated.

3.9-22 MigrateSingleObj
‣ MigrateSingleObj( obj, target )( function )

The MigrateSingleObj function works like MigrateObj (3.9-21), except that it does not migrate the subobjects of obj.

3.9-23 LockAndMigrateObj
‣ LockAndMigrateObj( obj, target )( function )

The LockAndMigrateObj function works like MigrateObj (3.9-21), except that it will automatically try to acquire a lock for the region containing target if it does not have one already.

3.9-24 IncorporateObj
‣ IncorporateObj( target, index, value )( function )

The IncorporateObj function allows convenient migration to a shared list or record. If target is a list, then IncorporateObj is equivalent to:

IncorporateObj := function(target, index, value)
  atomic value do
    target[index] := MigrateObj(value, target)
  od;
end;

If target is a record, then it is equivalent to:

IncorporateObj := function(target, index, value)
  atomic value do
    target.(index) := MigrateObj(value, target)
  od;
end;

The intended purpose is the population of a shared list or record with values after its creation. Example:

gap> list := ShareObj([]);
gap> atomic list do
>      IncorporateObj(list, 1, [1,2,3]);
>      IncorporateObj(list, 2, [4,5,6]);
>      IncorporateObj(list, 3, [7,8,9]);
>    od;
gap> ViewShared(list);
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

Using plain assignment would leave the newly created lists in the thread-local region.

3.9-25 AtomicIncorporateObj
‣ AtomicIncorporateObj( target, index, value )( function )

AtomicIncorporateObj extends IncorporateObj (3.9-24) by also locking the target. I.e., for a list, it is equivalent to:

AtomicIncorporateObj := function(target, index, value)
  atomic target, value do
    target[index] := MigrateObj(value, target)
  od;
end;

If target is a record, then it is equivalent to:

AtomicIncorporateObj := function(target, index, value)
  atomic value do
    target.(index) := MigrateObj(value, target)
  od;
end;

3.9-26 AdoptObj
‣ AdoptObj( obj )( function )

The AdoptObj function migrates obj (and all its subobjects contained within the same region) to the thread's current region. It requires exclusive access to obj.

gap> l := ShareObj([1,2,3]);;
gap> IsThreadLocal(l);
false
gap> atomic l do AdoptObj(l); od;
gap> IsThreadLocal(l);
true

3.9-27 AdoptSingleObj
‣ AdoptSingleObj( obj )( function )

The AdoptSingleObj function works like AdoptObj (3.9-26), except that it does not migrate the subobjects of obj.

3.9-28 LockAndAdoptObj
‣ LockAndAdoptObj( obj )( function )

The LockAndAdoptObj function works like AdoptObj (3.9-26), except that it will attempt acquire an exclusive lock for the region containing obj if it does not have one already.

3.9-29 CopyRegion
‣ CopyRegion( obj )( function )

The CopyRegion function performs a structural copy of obj. The resulting objects will be located in the current thread's thread-local region. The function returns the copy as its result.

gap> l := MakeReadOnlyObj([1,2,3]);
[ 1, 2, 3 ]
gap> l2 := CopyRegion(l);
[ 1, 2, 3 ]
gap> RegionOf(l) = RegionOf(l2);
false
gap> IsIdenticalObj(l, l2);
false
gap> l = l2;
true

3.9-30 IsPublic
‣ IsPublic( obj )( function )

The IsPublic function returns true if its argument is an object in the public region, false otherwise.

gap> IsPublic(1/2);
true
gap> IsPublic([1,2,3]);
false
gap> IsPublic(ShareObj([1,2,3]));
false
gap> IsPublic(MakeImmutable([1,2,3]));
true

3.9-31 IsThreadLocal
‣ IsThreadLocal( obj )( function )

The IsThreadLocal function returns true if its argument is an object in the current thread's thread-local region, false otherwise.

gap> IsThreadLocal([1,2,3]);
true
gap> IsThreadLocal(ShareObj([1,2,3]));
false
gap> IsThreadLocal(1/2);
false
gap> RegionOf(1/2);
<public region>

3.9-32 IsShared
‣ IsShared( obj )( function )

The IsShared function returns true if its argument is an object in a shared region. Note that if the current thread does not hold a lock on that shared region, another thread can migrate obj to a different region before the result is being evaluated; this can lead to race conditions. The function is intended primarily for debugging, not to build actual program logic around.

3.9-33 HaveReadAccess
‣ HaveReadAccess( obj )( function )

The HaveReadAccess function returns true if the current thread has read access to obj.

gap> HaveReadAccess([1,2,3]);
true
gap> l := ShareObj([1,2,3]);;
gap> HaveReadAccess(l);
false
gap> atomic readonly l do t := HaveReadAccess(l); od;; t;
true

3.9-34 HaveWriteAccess
‣ HaveWriteAccess( obj )( function )

The HaveWriteAccess function returns true if the current thread has write access to obj.

gap> HaveWriteAccess([1,2,3]);
true
gap> l := ShareObj([1,2,3]);;
gap> HaveWriteAccess(l);
false
gap> atomic readwrite l do t := HaveWriteAccess(l); od;; t;
true

3.9-35 MakeReadOnlyObj
‣ MakeReadOnlyObj( obj )( function )

The MakeReadOnlyObj function migrates obj and all its subobjects that are within the same region as obj to the read-only region. It returns obj.

3.9-36 MakeReadOnlySingleObj
‣ MakeReadOnlySingleObj( obj )( function )

The MakeReadOnlySingleObj function migrates obj, but not any of its subobjects, to the read-only region. It returns obj.

3.9-37 IsReadOnlyObj
‣ IsReadOnlyObj( obj )( function )

The IsReadOnlyObj function returns true if obj is in the read-only region, false otherwise.

gap> IsReadOnlyObj([1,2,3]);
false
gap> IsReadOnlyObj(MakeImmutable([1,2,3]));
false
gap> IsReadOnlyObj(MakeReadOnlyObj([1,2,3]));
true

3.9-38 SetRegionName
‣ SetRegionName( obj, name )( function )

The SetRegionName function sets the name of the region of obj to name.

3.9-39 ClearRegionName
‣ ClearRegionName( obj )( function )

The ClearRegionName function clears the name of the region of obj to name.

3.9-40 RegionName
‣ RegionName( obj )( function )

The RegionName function returns the name of the region of obj. If that region does not have a name, fail will be returned.

3.9-41 ViewShared
‣ ViewShared( obj )( function )

The ViewShared function allows the inspection of objects in shared regions. It will try to lock the region and then call ViewObj(obj). If it cannot acquire a lock for the region, it will simply display the normal description of the object.

3.9-42 UNSAFE_VIEW
‣ UNSAFE_VIEW( obj )( function )

The UNSAFE_VIEW function allows the inspection of any object in the system, regardless of whether the current thread has access to the region containing it. It should be used with care: If the object inspected is being modified by another thread concurrently, the resulting behavior is undefined.

Moreover, the function works by temporarily disabling read and write guards for regions, so other threads may corrupt memory rather than producing errors.

It is generally safe to use if all threads but the current one are paused.

3.9-43 The atomic statement.

The atomic statement ensures exclusive or read-only access to one or more shared regions for statements within its scope. It has the following syntax:

atomic ([readwrite|readonly] expr (, expr)* )* do
  statements
od;

Each expression is evaluated and the region containing the resulting object is locked with either a read-write or read-only lock, depending on the keyword preceding the expression. If neither the readwrite nor the readonly keyword was provided, read-write locks are used by default. Examples:

gap> l := ShareObj([1,2,3]);;
gap> atomic readwrite l do l[3] := 9; od;
gap> atomic l do l[2] := 4; od;
gap> atomic readonly l do Display(l); od;
[ 1, 4, 9 ]
gap> l := ShareObj([1,2,3,4,5]);;
gap> l2 := ShareObj([6,7,8]);;
gap> atomic readwrite l, readonly l2 do
>      for i in [1..3] do l[i] := l2[i]; od;
>      l3 := AdoptObj(l);
>    od;
gap> l3;
[ 6, 7, 8, 4, 5 ]

Atomic statements must observe region ordering. That means that the highest precedence level of a region locked by an atomic statement must be less than the lowest precedene level of a region that is locked by the same thread at the time the atomic statement is executed.

3.10 Atomic functions

Instead of atomic regions, entire functions can be declared to be atomic. This has the same effect as though the function's body were enclosed in an atomic statement. Function arguments can be declared either readwrite or readonly; they will be locked in the same way as for a lock statement. If a function argument is preceded by neither readwrite nor readonly, the corresponding object will not be locked. Example:

gap> AddAtomic := atomic function(readwrite list, readonly item)
>      Add(list, item);
>    end;

3.11 Write-once functionality

There is an exception to the rule that objects can only be modified if a thread has write access to a region. A limited sets of objects can be modified using the "bind once" family of functions. These allow the modifications of objects to which a thread has read access in a limited fashion.

For reasons of implementation symmetry, these functions can also be used on the atomic versions of these objects.

Implementation note: The functionality is not currently available for component objects.

3.11-1 BindOnce
‣ BindOnce( obj, index, value )( function )

BindOnce modifies obj, which can be a positional object, atomic positional object, component object, or atomic component object. It inspects obj![index] for the positional versions or obj!.(index) for the component versions. If the respective element is not yet bound, value is assigned to that element. Otherwise, no modification happens. The test and modification occur as one atomic step. The function returns the value of the element; i.e. the old value if the element was bound and value if it was unbound.

The intent of this function is to allow concurrent initialization of objects, where multiple threads may attempt to set a value concurrently. Only one will succeed; all threads can then use the return value of BindOnce as the definitive value of the element. It also allows for the lazy initialization of objects in the read-only region.

The current thread needs to have at least read access to obj, but does not require write access.

3.11-2 TestBindOnce
‣ TestBindOnce( obj, index, value )( function )

TestBindOnce works like BindOnce (3.11-1), except that it returns true if the value could be bound and false otherwise.

3.11-3 BindOnceExpr
‣ BindOnceExpr( obj, index, expr )( function )

BindOnceExpr works like BindOnce (3.11-1), except that it evaluates the parameterless function expr to determine the value. It will only evaluate expr if the element is not bound.

For positional objects, the implementation works as follows:

BindOnceExprPosObj := function(obj, index, expr)
  if not IsBound(obj![index]) then
    return BindOnce(obj, index, expr());
  else
    return obj![index]);
  fi;
end;

The implementation for component objects works analogously.

The intent is to avoid unnecessary computations if the value is already bound. Note that this cannot be avoided entirely, because obj![index] or obj!.(index) can be bound while expr is evaluated, but it can minimize such occurrences.

3.11-4 TestBindOnceExpr
‣ TestBindOnceExpr( obj, index, expr )( function )

TestBindOnceExpr works like BindOnceExpr (3.11-3), except that it returns true if the value could be bound and false otherwise.

3.11-5 StrictBindOnce
‣ StrictBindOnce( obj, index, expr )( function )

StrictBindOnce works like BindOnce (3.11-1), except that it raises an error if the element is already bound. This is intended for cases where a read-only object is initialized, but where another thread trying to initialize it concurrently would be an error.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Ind

generated by GAPDoc2HTML