On June 1, 1998, European Patent #817044 on ``Memory allocation in a multithreaded environment'' was granted to Sun Microsystems Inc. (US) with Nakhimovsky Gregory listed as inventor. The abstract reads:
A method of allocating memory in a multithreaded (parallel) computing environment in which threads running in parallel within a process are associated with one of a number of memory pools of a system of memory. The method includes the steps of establishing memory pools in the system memory, mapping each thread to one of the memory pools; and for each thread, dynamically allocating user memory blocks from the associated memory pool. The method allows any existing memory management malloc (memory allocation) package to be converted to a multithreaded version so that multithreaded processes are run with greater efficiency.
The 8 page application consists of 21 claims followed by a description of the invention and preferred embodiments. The first 6 claims read as follows:
Claims of EP0817044
1. A method of allocating memory in a multithreaded computing environment in which a plurality of threads run in parallel within a process, each thread having access to a system memory, the method comprising: establishing a plurality of memory pools in the system memory; mapping each thread to one said plurality of memory pools; and for each thread, dynamically allocating user memory blocks from the associated memory pool.
2. The method of claim 1 wherein the step of dynamically allocating memory blocks includes designating the number of bytes in the block desired to allocate.
3. The method of claim 1 further comprising the step of preventing simultaneous access to a memory pool by different threads.
4. The method of claim 1 further comprising the step of establishing a memory pool for each thread comprises allocating a memory buffer of a preselected size.
5. The method of claim 4 further comprising the step of dynamically increasing the size of the memory pool by allocating additional memory from the system memory in increments equal to the preselected size of the buffer memory.
6. The method of claim 4 wherein the preselected size of the buffer is 64 Kbytes.
The remaining 15 claims go into more details about the specific data structure to represent the memory pool and the memory blocks, and about the deallocation of blocks as well as their merger after deallocation.
Although the subject matter of this patent is not as astonishingly simple as that of the IsNot example, any computer scientist will see what this is about: memory allocation as it occurs in operating system kernels and concurrent applications. A simple way to implement this is to have a single pool of memory blocks that can be claimed by one of the parallel processes (threads). However, to avoid corruption of the administration of the memory pool, access to the memory pool has to be strictly sequential. This is achieved by locking and unlocking the memory pool during each request. Since this locking introduces a time penalty, the idea formulated in this patent is to use a separate memory pool per process (thread).
In our opinion the idea to avoid the use of shared variables is trivial. We conjecture that this idea is not new and we think that there is a proof obligation on the part of the applicants to show how this patent improves upon earlier work (see Section 8.9).
This patent can have a major impact on the implementation of most, if not all, operating system kernels and its mere existence poses a threat to further development.