Memory allocator for multithread environment

• US 6,539,464 B1
• Filed: 03/23/2001
• Issued: 03/25/2003
• Est. Priority Date: 04/08/2000
• Status: Expired due to Fees

• Current Assignee: Radoslav Nenkov Getov
• Original Assignee: Radoslav Nenkov Getov
• Inventors: Getov, Radoslav Nenkov
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): Encarnacion, Yamir
• Application Number:
  US09/816,280
• Time in Patent Office: 732 Days
• Field of Search: 711/147, 711/152, 711/171, 711/170, 709/102
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Memory allocator combines private (per thread) sets of fixed-size free blocks lists, a global, common for all threads, set of fixed-sized free block lists, and a general-purpose external coalescing allocator. Blocks of size bigger than the maximal fixed size are managed directly by the external allocator. The lengths of fixed-size lists are changed dynamically in accordance with the allocation and disallocation workload. A service thread performs updates of all the lists and collects memory associated with terminated user threads. A mutex-free serialization method, utilizing thread suspension, is used in the process.

Claims

1. A method for managing of allocation of memory blocks in a computer system, said computer system:

(a) defining one or more threads, said one or more threads being the execution of sequence of programing instructions;

(b) running at least one of said threads in parallel;

(c) defining a fixed size, said fixed size being a positive integer number;

(d) providing a fixed size set, said fixed size set comprising at least one of said fixed size;

said fixed size set being farther characterized by a maximal fixed size and a fixed sizes count;

(e) comprising a memory;

(f) providing an external allocation, said external allocation;

i) by a request, the request including a block size, the block size being one of the members of said fixed size set, the request also including a blocks count,

ii) performing allocation of memory blocks or blocks of that blocks count from said memory of said computer system, each block of that block size;

(g) providing an external disallocation, said external disallocation;

i) by a request, the request including at least one block, previously been allocated by using of said external allocation,

ii) performing disallocation of these blocks and returning them to said memory of said computer system;

said method for managing of allocation of memory blocks comprising the steps of;

(h) defining a class, said class;

i) being capable of storing substantially arbitrary amount of blocks at a time;

ii) providing means for adding to it and taking from it of an arbitrary amount of blocks at a time;

iii) providing means for querying the length thereof, length being the count of the blocks therein;

iv) comprising a preferred length, said preferred length being a variable, capable of storing a non-negative numeric value;

(i) defining a class set, said class set containing said classes of amount being equal to said fixed sizes count;

(j) establishing a correspondence between said fixed sizes from said fixed size set and said classes from said class set;

the correspondence being such that each member of said fixed size set corresponds to exactly one member of said class set and vice versa;

the correspondence being sufficient to identify the class in given instance of said class set, given said fixed size;

(k) defining a slot, said slot comprising an instance of said class set;

(l) providing an associating means;

said associating means performing association between an instance of said slot with exactly one of said threads, the association being mutual, one to one;

said associating means being sufficient to identify said slot instance, associated with particular of said threads;

(m) establishing a separate instance of said slot for each of said threads, running on said computer system, thereby associating said slot instance with the particular said threads and vice versa, using said associating means;

(n) providing a means for decaying of preferred lengths, said means for decaying of preferred lengths performing decaying of the current values of said preferred length of all said classes in existence;

the decaying being non-negatively correlated with the passing of time, the time being an adequate measure for the temporal relationships on said computer system;

(o) providing a means for preferred length incrementing;

said means for preferred length incrementing referring to a particular instance of said class;

said means for preferred length incrementing performing modifying of the current value of said preferred length of the particular instance of said class;

said means for preferred length incrementing comprising a sequence of operations, selected from the group consisting of;

(1) doing nothing;

(2) if the current value is less than one, setting it to a predetermined positive number;

otherwise firstly incrementing it by a predetermined non-negative number and then multiplying it by a predetermined positive number;

(3) if the current value is less than one, setting it to a predetermined positive number;

otherwise firstly multiplying it by a predetermined positive number and then incrementing it by a predetermined non-negative number;

(4) if the current value is less than one, setting it to approximately one;

otherwise multiplying it by approximately two;

(5) incrementing of the current value in any other way;

any of (1), (2), (3), (4), or (5) above, and then limiting the current value so that it does not exceed the greater of;

a) a predefined first positive number, and b) a predefined second positive number divided by the fixed size corresponding to the particular class instance;

(p) establishing a global class set;

said global class set being an instance of said class set;

(q) receiving a global allocation request of a global allocation size and a global allocation count, said global allocation size being one of the members of said fixed size set;

said global allocation size and said global allocation count being part of said global allocation request;

(r) in response to said global allocation request, performing a global block allocation, said global block allocation comprising the steps of;

i) identifying a global class, said global class being the member of said global class set, corresponding to said global allocation size according to said correspondence;

ii) if said global class contains less blocks than said global allocation count, performing the steps of;

incrementing of said preferred length of said global class by using said means for preferred length incrementing;

estimating a count of blocks to request as a number equal to the greater of said preferred length and said global allocation count, the greater decremented by the current length of said global class;

using a request to said external allocation, requesting and receiving memory blocks of amount equal to said count of blocks to request, and with size, equal to said global allocation size;

placing received blocks into said global class;

iii) taking from said global class blocks of count, equal to said global allocation count, and

iv) returning to the requesting party these blocks, thus fulfilling said global allocation request;

(s) receiving an allocation request of an allocation size by an allocating thread, said allocation size being one of the members of said fixed size set;

said allocating thread being one of said threads;

said allocation size and said allocating thread being part of said allocation request;

(t) in response to said allocation request performing a block allocation;

said block allocation comprising the steps of;

i) identifying said slot associated with said requesting thread;

ii) identifying a slot class, said slot class being said class from said class set from said slot, corresponding to said allocation size;

iii) if the identified slot class is empty, performing the steps of;

incrementing of said preferred length of said slot class, using said means for preferred length incrementing;

using a request to said global block allocation, requesting and receiving memory blocks of a size equal to said allocation size, and of a count substantially equal to the current value of said preferred length of said slot class, but not less than one;

placing received blocks into said slot class;

iv) taking one block from said slot class, and

v) returning the block to the requesting party, thus fulfilling said allocation request;

(u) providing a means for class updating, said means for class updating referring to a class being updated;

said class being updated being one of said classes in existence;

said means for class updating comprising the steps of;

i) performing a check if said class being updated is too full;

the decision about this using a method selected from the group consisting of;

said class being updated is never too full;

said class being updated is too full if its length is greater than the value of said preferred length thereof multiplied by a predetermined positive number;

said class being updated is too full if its length is greater than the value of said preferred length multiplied by approximately two;

said class being updated is too full if its length is greater than the smaller of;

a) said preferred length thereof multiplied by a first predetermined positive number, and b) a second predetermined positive number;

ii) if said class being updated was found to be too full, performing the steps of;

determining a count of blocks to take, said count of blocks to take being a positive integer number, the value thereof selected from the group consisting of;

a predetermined positive integer number;

approximately the current length of said class being updated multiplied by a predetermined positive number;

approximately the half of the current length of said class being updated;

approximately the current length of said class being updated minus current value of said preferred length of said class being updated;

approximately the current length of said class being updated;

taking from said class being updated blocks of count equal to said count of blocks to take;

if said class being updated belongs to said global class set, disallocating the blocks been taken, using a request to said external disallocation with size corresponding to said fixed size corresponding to said class being updated;

else

performing a global disallocation, said global disallocation comprising a step of adding the blocks been taken to this member of said global class that corresponds to the size from said fixed size set corresponding to said class being updated according to said correspondence;

(v) establishing a means for regular updating;

said means for regular updating carrying out repeatedly, at appropriate intervals, said means for class updating for substantially all said classes in said class set in all said slots, as well as for all said classes in said global class set;

the updates being done frequently enough, so that all said classes for most of the time will not contain any blocks which would be taken from them by said means for class updating;

whereby the blocks, stored in any of said classes will be unavailable for any other purpose;

whereby the blocks, returned to said memory of said computer system, will be available for some other purpose, including for using them by said external allocation as blocks of the any of said fixed size, after appropriate splitting or coalescing;

whereby each of said slots, respectively said classes therein, will be accessed exclusively by the thread, associated with the slot;

whereby said classes from said global class set will be accessed concurrently in a serialized manner by various threads;

whereby the step of taking blocks from said class, belonging to said global class set, on average, is substantially faster than said external allocation;

whereby the step of taking blocks from said class, belonging to said class set in said slot, on average, is substantially faster than said global block allocation;

whereby plurality of said allocation requests for blocks of various of said fixed sizes will be issued by various of said threads;

whereby the actual length of said class, associated with particular fixed size and thread, will tend to grow during periods of more frequent allocations of blocks of this particular size that are requested by this particular thread, thus making possible performing the allocations and disallocations faster, due to less frequent requests to said global block allocation, said external allocation, and said external disallocation;

whereby the actual length of said class from said global class set, associated with particular fixed size, will tend to grow during periods of more frequent allocations of blocks of this particular size, requested by any thread, thus making possible performing allocations and disallocations faster, due to less frequent requests to said external allocation and said external disallocation;

whereby the actual length of said class, associated with particular fixed size and thread, will tend to decrease during periods of less frequent allocations of blocks of this particular size that are requested by this particular thread, thus releasing blocks from said class to said global class set, respectively to said computer system;

whereby the actual length of said class from said global class, associated with particular fixed size, will tend to decrease during periods of less frequent allocations of blocks of this particular size that are requested by any thread, thus releasing blocks from said class to said computer system.

2. The method for managing the allocation of memory blocks of claim 1, further comprising the steps of:

(a) receiving a disallocation request by a disallocating thread;

said disallocation request being to disallocate a memory block, formerly been allocated by said block allocation;

said disallocating thread being one of said threads;

the size of the block being one of said fixed size set;

the block, the size of the block, and said disallocating thread being part of said disallocation request;

(b) in response to said disallocation request performing a block disallocation;

said block disallocation comprising the steps of;

i) identifying said slot associated with said disallocating thread;

ii) identifying a disallocation slot class, said disallocation slot class being said class in said class set in the identified slot, corresponding to the size of the block being disallocated according to said correspondence;

iii) if said disallocation slot class is empty, incrementing of said preferred length thereof, using said means for preferred length incrementing;

iv) placing the block being disallocated into said identified disallocation slot class;

whereby adding a block to said class, respectively said block disallocation, will be substantially faster than said external disallocation;

whereby plurality of said disallocation requests for blocks of various of said fixed sizes will be issued by various of said threads;

whereby some blocks might be allocated by one thread and disallocated by another thread;

whereby the preferred and actual lengths of said class, associated with particular fixed size and thread, will tend to grow during periods of more frequent disallocations of blocks of this particular size that are requested by this particular thread, thus making possible performing the allocations and disallocations faster;

whereby the actual length of said class, associated with particular fixed size and thread, will tend to decrease during periods of less frequent disallocations of blocks of this particular size that are requested by this particular thread, thus releasing blocks from said class to said memory of said computer system;

whereby the actual length of said class from said global class set, associated with particular fixed size, will tend to grow during periods of more frequent disallocations of blocks of this particular size, requested by any thread, thus causing performing both allocations and disallocations faster due to less frequent requests to said external allocation and said external disallocation.

3. The method for managing of allocation of memory blocks of claim 1, wherein said means for regular updating comprises the steps of:

(a) providing a service thread;

said service thread being a separate stream of execution of programming instructions, running in parallel with said threads on said computer system;

said service thread periodically carrying out said means for class updating for part of the instances of said classes in existence;

(b) establishing at least of one of so defined said service threads and running them in parallel with the rest of said threads on said computer system, wherein said service threads in combination carry out said means for class updating for substantially all the instances of said classes in existence;

whereby said means for class updating will be done in regular and timely manner.

4. The method for managing of allocation of memory blocks of claim 3, wherein said service thread farther performs a step, comprising collecting and returning to said computer system any resources that might be part of the implementation of said slot and of said associating means;

the collecting being done for said slots, associated with said threads that no longer exist,

whereby these resources will be released and made available for later reuse by said computer system in timely manner.

5. The method for managing of allocation of memory blocks of claim 3, wherein said computer system farther comprises a plurality of processors or CPUs;

wherein said means for regular updating farther comprises the steps of;

(a) establishing a separate of said service threads for each of CPUs, and forcing it to run on essentially separate CPU;

(b) arranging each of said service threads being established to preferably carry out said means for class updating of said classes residing in said slots that are associated with said threads, running on the same CPU, as does said service thread itself;

whereby running the service thread on the same CPU as the client threads will improve the performance due to the decreased need for synchronization between the CPUs.

6. A method for managing of allocation of memory blocks in a computer system, said computer system:

(a) defining one or more threads, said one or more threads being the execution of sequence of programming instructions;

(b) running at least one of said threads in parallel;

(c) defining a fixed size, said fixed size being a positive integer number;

(d) providing a fixed size set, said fixed size set comprising at least one of said fixed size;

said fixed size set being farther characterized by a maximal fixed size and a fixed sizes count;

(e) comprising a memory;

(f) providing an external allocation, said external allocation;

i) by a request, the request including a block size, the block size being one of the members of said fixed size set, the request also including a blocks count,

ii) performing allocation of memory blocks or blocks of that blocks count from said memory of said computer system, each block of that block size;

(g) providing an external disallocation, said external disallocation;

i) by a request, the request including at least one block, previously been allocated by using of said external allocation,

ii) performing disallocation of these blocks and returning them to said memory of said computer system;

said method for managing of allocation of memory blocks comprising the steps of;

(h) defining a class, said class;

i) being capable of storing substantially arbitrary amount of blocks at a time;

ii) providing means for adding to it and taking from it of an arbitrary amount of blocks at a time;

iii) providing means for querying the length thereof, length being the count of the blocks currently therein;

iv) comprising a preferred length, said preferred length being a variable, capable of storing a non-negative numeric value;

(i) defining a class set, said class set containing said classes of amount equal to said fixed sizes count;

(j) establishing a correspondence between said fixed sizes from said fixed size set and said classes from said class set;

the correspondence being such that each member of said fixed size set corresponds to exactly one member of class set;

the correspondence being sufficient to identify said class in particular fixed size set, given particular fixed size;

(k) defining a slot, said slot comprising an instance of said class set;

(l) providing an associating means;

said associating means performing association between an instance of said slot with exactly one of said threads;

the association being mutual, one to one;

said associating means being sufficient to identify the slot, associated with particular thread;

(m) establishing a separate instance of said slot for each of said threads, thereby associating said slot instance with the particular of said threads, using said associating means;

(n) providing a means for decaying of preferred lengths;

said means for decaying of preferred lengths performing decaying of the current values of said preferred length of all said classes in existence;

the decaying being non-negatively correlated with the passing of time, the time being an adequate measure for the temporal relationships on said computer system;

(o) providing a means for preferred length incrementing;

said means for preferred length incrementing referring to particular instance of said class;

said means for preferred length incrementing performing modifying the current value of said preferred length of the particular instance of said class;

said means for preferred length incrementing comprising a sequence of operations, selected from the group consisting of;

(1) doing nothing;

(2) if the current value is less than one, setting it to a predetermined positive number;

otherwise firstly incrementing it by a predetermined non-negative number and then multiplying it by a predetermined positive number;

(3) if the current value is less than one, setting it to a predetermined positive number;

otherwise firstly multiplying it by a predetermined positive number and then incrementing it by a predetermined non-negative number;

(4) if the current value is less than one, setting it to approximately one;

otherwise multiplying it by approximately two;

(5) incrementing of the current value in any other way;

any of (1), (2), (3), (4), or (5) above, and then limiting the current value so that it does not exceed the greater of a predefined first positive number and a predefined second positive number divided by said fixed size corresponding to the particular instance of said class;

(p) receiving an allocation request for allocating blocks of an allocation count and of an allocation size by an allocating thread;

said allocation size being one of the members of said fixed size set;

said allocating thread being one of said threads;

said allocation size, said allocation count, and said allocating thread being part of said allocation request;

(q) in response to said allocation request, performing a block allocation, said block allocation comprising the steps of;

i) identifying said slot associated with said allocating thread;

ii) identifying a slot class, said slot class being the member from said class set from identified slot, corresponding to said allocation size;

iii) if said slot class contains less blocks than said allocation count, performing the steps of;

incrementing of said preferred length of said slot class, using said means for preferred length incrementing;

using a request to said external allocation, requesting and receiving memory blocks of a size equal to said allocation size and a count substantially equal to the current value of said preferred length of said slot class, but not less than said allocation count minus the current length of said slot class;

placing received blocks into said slot class;

iv) taking from said slot class blocks of the amount equal to said allocation count, and

v) returning to the requesting party these blocks, thus fulfilling said allocation request;

(r) providing a means for class updating;

said means for class updating referring to a class being updated;

said class being updated being an instance of said class;

said means for class updating comprising the steps of;

i) performing a check if said class being updated is too full;

the decision about this using a method from the group consisting of;

said class being updated is never too full;

said class being updated is too full if its length is greater than the value of said preferred length thereof multiplied by a predetermined positive number;

said class being updated is too full if its length is greater than the value of said preferred length thereof multiplied by approximately two;

said class being updated is too full if its length is greater than the smaller of;

a) said preferred length thereof multiplied by a first predetermined positive number, and b) a second predetermined positive number;

ii) if said class being updated was found to be too full, performing the steps of;

determining a count of blocks to take;

said count of blocks to take being a positive integer number, the value thereof chosen from the group consisting of;

a predetermined positive integer number;

approximately the current length of said class being updated multiplied by a predetermined positive number;

approximately the current length of said class being updated;

approximately the half of the current length of said class being updated;

approximately the current length of said class being updated minus the current value of said preferred length thereof;

taking from said class being updated blocks of count equal to said count of blocks to take;

disallocating the blocks been taken by using a request to said external disallocation;

(s) establishing a means for regular updating;

said means for regular updating carrying out repeatedly, at appropriate intervals, said means for class updating for substantially all said classes in said class set in substantially all said slots;

the updates being done frequently enough, so that said classes for most of the time will not contain any blocks which would be taken from them by said means for class updating;

whereby the blocks, stored in said class will be unavailable for other purpose;

whereby the blocks, returned to said computer system, will be available for some other purpose, including for using them, after appropriate splitting and coalescing by said external allocation as blocks of potentially another fixed sizes;

whereby each of said slots, respectively said block lists therein, will be accessed exclusively by the thread, associated with the slot;

whereby taking a block from said class, respectively said block allocation, will be substantially faster than said external allocation;

whereby a plurality of said allocation requests for blocks of various of said fixed sizes will be issued by various of said threads;

whereby the actual length of said class, associated with particular fixed size and thread, will tend to grow during periods of more frequent allocations of blocks of this particular size that are requested by this particular thread, thus causing performing the allocations faster;

whereby the actual length of said class, associated with particular fixed size and thread, will tend to decrease during periods of less frequent allocations, of blocks of this particular size that are requested by this particular thread, thus releasing blocks from said class to said computer system.

7. The method for managing the allocation of memory blocks of claim 6, further comprising the steps of:

(a) receiving a disallocation request by a disallocating thread;

said disallocation request being to disallocate a memory block, formerly been allocated by said block allocation;

said disallocating thread being one of said threads;

the block being disallocated, the size of this block, and said disallocating thread being part of said disallocation request;

(b) in response to said disallocation request, performing a block disallocation, which comprises the steps of;

i) identifying said slot associated with said disallocating thread;

ii) identifying a disallocation class, said disallocation class being the member of said class set in identified slot, corresponding to the size of the block being disallocated according to said correspondence;

iii) if said disallocation class is empty, incrementing of said preferred length thereof by using said means for preferred length incrementing;

iv) placing the block being disallocated into said identified disallocation class;

whereby adding a block to said class, respectively said block disallocation, will be substantially faster than said external disallocation;

whereby each of said slots, respectively said classes therein, will be accessed exclusively by the thread, associated with the slot;

whereby plurality of said disallocation requests for blocks of various of said fixed sizes will be issued by various of said threads;

whereby some blocks might be allocated by one thread and disallocated by another thread;

whereby the preferred and actual lengths of said class, associated with particular fixed size and thread, will tend to grow during periods of more frequent disallocations of blocks of this particular size that are requested by this particular thread, thus causing performing allocations and disallocations faster, due to less frequent requests to said external allocation and said external disallocation;

whereby the actual length of said class, associated with particular fixed size and thread, will tend to decrease during periods of less frequent disallocations of blocks of this particular size, requested by this particular thread, thus releasing blocks from said class to said computer system.

8. The method for managing of allocation of memory blocks of claim 6, wherein said means for regular updating comprises the steps of:

(a) providing a service thread;

said service thread being a separate stream of execution of programming instructions;

said service thread periodically carrying out said means for class updating for part of the instances of said classes in existence;

(b) establishing at least of one of so defined said service thread and running them in parallel with the rest of said threads on said computer system, wherein said service threads in combination carry out said means for class updating for substantially all the instances of said classes in existence;

whereby said means for class updating will be performed in a regular and timely manner.

9. The method for managing of allocation of memory blocks of claim 8, wherein said service thread farther performs a step, comprising periodical collecting and returning to said computer system of any resources that are part of the implementation of said slot and of said associating means;

the collecting being done for said slots associated with said threads that no longer exist,

whereby these resources will be released and made available for reusing by said computer system in timely manner.

10. The method for managing of allocation of memory blocks of claim 8, wherein said computer system farther comprises a plurality of processors or CPUs;

wherein said means for regular updating farther comprises the steps of;

(a) establishing a separate of said service threads for each of CPUs, and forcing it to run on a separate CPU;

(b) arranging each of said service threads being established to preferably carry out said means for class updating of said classes residing in said slots that are associated with said threads, running on the same CPU, as does said service thread itself;

whereby running the service thread on the same CPU as the client threads will improve performance due to the decreased need for synchronization between CPUs.

11. A method for managing of allocation of memory blocks in a computer system, said computer system:

(a) defining a fixed size, said fixed size being a positive integer number;

(b) providing a fixed size set, said fixed size set comprising a plurality of said fixed sizes;

said fixed size set being farther characterized by a maximal fixed size and a fixed sizes count;

(c) providing an external allocation, said external allocation performing allocation of a memory block or block of size, being one of said fixed sizes in said fixed size set;

the size being part of the request for said external allocation;

said method for managing of allocation of memory blocks comprising the steps of;

(d) considering said fixed sizes in said fixed size set being ordered incrementally by their values, establishing a correspondence between the zero-based indexes in this ordering and said fixed sizes in said fixed size set;

said correspondence being one to one;

(e) determining a common divisor, said common divisor being such a positive integer number that divides each of said fixed sizes from said fixed size set without residue;

(f) establishing an index array, each entry in said index array being capable of storing a number between zero and said fixed sizes count;

said index array being of size equal to said maximal fixed size divided by said common divisor;

(g) initializing of said index array in such a way that at each position it contains;

the index, according to said correspondence, of the minimal member of said fixed size set such that said fixed size, corresponding to that index according to said correspondence, is not less than the position multiplied by said common divisor;

(h) receiving an allocation request of a request size;

said allocation request being a request to allocate memory block of the request size;

said request size being a positive integer number not greater than said maximal fixed size;

said request size being part of said allocation request;

(i) in response to said allocation request, performing a block allocation, said block allocation comprising the steps of;

i) estimating a position, the position being an integer number, by the formula;

the integer part of;

said request size plus said common divisor minus one divided by said common divisor;

ii) taking the value placed at so estimated position in said index array;

iii) using this value as index according to said correspondence, identifying corresponding to it said fixed size,

whereby the identified fixed size will be the smallest in said fixed size set that is not less than said request size;

iv) using said external allocation, allocating a block of identified fixed size;

v) returning the allocated block to the requesting party and thus fulfilling said allocation request;

whereby finding of the smallest member of said fixed size set that is not less than said request size will require only a lookup in said index array and a few arithmetic calculations;

whereby the size of said index array will be smaller than said maximal fixed size by a factor of said common divisor.

12. The method for managing of allocation of memory blocks of claim 11, wherein said computer system further comprises:

(a) providing an external disallocation, said external disallocation performing disallocation of a block, previously been allocated by said external allocation;

a block and the corresponding to it said fixed size being part of each request for said external disallocation;

said method for managing of allocation of memory blocks farther comprising;

(b) receiving a disallocation request;

said disallocation request being a request to disallocate a block, formerly been allocated by said block disallocation;

the block and its actual size being part of said disallocation request;

(c) in response to said disallocation request, performing a block disallocation;

said block disallocation comprising the steps of;

i) estimating a position, the position being an integer number, by the formula;

the integer part of;

the actual block'"'"'s size divided by said common divisor plus one;

ii) taking the value placed at the estimated position in said index array;

iii) decrementing it by one;

iv) using this value as index according to said correspondence, identifying said fixed size, corresponding to it;

whereby identified fixed size is the greatest in said fixed size set that is not greater than the actual size of the block;

v) using said external disallocation, disallocating the block of said identified fixed size;

whereby finding of the greatest member of said fixed size set that is not greater than the block size will require only a lookup in said index array and a few arithmetic calculations;

whereby said index array will be used in both said block allocation and said block disallocation.

13. A method for serialization in a parallel computing environment, said parallel computing environment comprising:

(a) a shared object;

(b) an owning thread;

said owning thread being an execution of stream of programming instructions;

(c) an alien thread;

said alien thread being an execution of stream of programming instructions;

(d) wherein said alien thread and said owning thread run in parallel in said computing environment;

(e) wherein said alien thread and said owning thread try to access said shared object in a substantially asynchronous and parallel manner;

(f) whereby the actual access to said shared object needs to be serialized so that at most one of said owning thread and said alien thread actually accesses said shared object at the same time;

said method for serialization in a parallel computing environment comprising the steps of;

(g) providing means for suspending of said owning thread;

suspending being defined as temporary stopping the process of execution of programming instructions;

said means for suspending being able to be initiated by a programming instruction executed by said alien thread;

(h) providing means for resuming of said owning thread;

resuming being defined as resuming the process of execution of programming instructions by said owning thread, been previously suspended;

said means for resuming being able to be initiated by a programing instruction executed by said alien thread;

(i) establishing and associating of a boolean flag with said shared object, said boolean flag;

i) being capable of keeping one of the two distinctive values true and false at a time;

ii) being initially set to value false;

iii) being accessible by said owning thread for writing, that is for changing its value;

the writing being done in an atomic programming instruction;

the atomic programming instruction being defined as one that once started, cannot be interrupted before entirely finished;

iv) being accessible by said alien thread for reading by an atomic programming instruction;

v) values being written to it by said owning thread being substantially instantly visible, if read by said alien thread;

(j) providing an owning thread access, said owning thread access being a serialized access by said owning thread to said shared object;

said owning thread access performing the steps of;

i) writing by said owning thread value true to said boolean flag;

ii) performing the actual access by said owning thread to said shared object;

iii) writing by said owning thread a value false to said boolean flag;

(k) providing an alien thread access attempt, said alien thread access attempt being an attempt for serialized access by said alien thread to said shared object;

said alien thread access attempt comprising the successive steps of;

i) suspending of said owning thread, using said means for suspending, initiated by said alien thread;

ii) checking by said alien thread of the current value of said boolean flag;

iii) if said boolean flag contains value true, resuming of said owning thread using said means for resuming, and terminating said alien thread access attempt as unsuccessful;

otherwise

iv) performing the actual access by said alien thread to said shared object;

v) resuming of said owning thread using said means for resuming, initiated by said alien thread;

vi) finishing said alien thread access attempt as successful;

whereby a plurality of said owning thread accesses and said alien thread access attempts will be performed by said owning thread and said alien thread, respectively, in substantially asynchronous and parallel manner;

whereby said boolean flag will contain value true during periods in which said shared object is being actually accessed by said owning thread;

whereby said owning thread will be suspended during periods in which said shared object is being actually accessed by said alien thread;

whereby all of said owning thread accesses will succeed;

whereby some of said alien thread access attempts might fail, in case of contention between said owning thread and said alien thread for said shared object;

whereby the actual accesses of said alien thread and said owning thread to said shared object are serialized;

whereby, provided that said alien thread accesses said shared object much less frequently than does said owning thread, there will be negligible performance degradation caused by the serialization;

whereby there are no mutexes involved.