Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-10-04
2004-06-29
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S152000, C711S156000
Reexamination Certificate
active
06757803
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to recovery of memory in a computer system having a shared memory, the computer system being either a multiprocess or a multiprocess single processor system, and more particularly to avoiding loss of regions of memory by failure of a process to return allocated memory after finishing with it so that the region of memory can be de-allocated for re-use.
2. Background Information
Routers often have multiple processors handling incoming packets and outgoing packets. The packets are stored in buffers in common, or shared, memory. As the packet progress through steps of the routing procedure, ownership of the buffer in memory is transferred from processor to processor. Ownership of the buffer in memory is first assigned to a processor handling the incoming interface. Later, depending upon the system architecture, ownership of the buffer may be transferred to an intermediate processor. Still later, ownership may be transferred to a processor handling the outgoing interface. Upon transmission of the packet, the buffer in the common memory is released for re-use for routing another packet.
A problem in usage of buffers stored in common memory is that if an error occurs during the routing procedure, then the memory used for the buffer may not be released for re-use. Errors leading to a failure to release the memory used for buffers include: a crash of any of the processors to which ownership of the buffer may be assigned; a failure of the processor handling release of the memory for re-use; and other computer glitches, etc.
Also, a computer system having only one processor, but having an operating system which supports multiple processes using a shared memory has memory allocated to each process. When a process completes, the allocated memory is supposed to be de-allocated for re-use. However, computer glitches may cause memory to not be de-allocated. Memory which is not de-allocated is then lost and cannot be used by subsequent process. A method for de-allocating such lost memory is needed.
Memory which is not released for re-use is lost to the computer system. If enough memory is lost then the computer system will run out of memory and be unable to continue functioning. In the router example, bringing the router down and then re-booting it releases the lost memory. However bringing the router down and then re-booting it is very undesirable as it causes loss of service in the computer network served by the router. In the single processor system supporting multiple processes, the usual method of freeing the “lost” memory is to re-boot the system. Re-booting the computer system is very undesirable.
The memory management problem is discussed in the book by Andrew S. Tanenbaum and Albert S. Woodhull,
Operating Systems, Second Edition
, published by Prentice Hall, Copyright 1997, all disclosures of which are incorporated herein by reference, especially at pages 316-318.
A better way of releasing memory allocated to processors, or to multiple processes of a single processor, is needed.
SUMMARY OF THE INVENTION
A method of recovering memory blocks in a computer system having multiple processes executing therein, and the processes sharing a common memory, is described. A memory usage data structure (MUDS) is maintained for each process executing in the computer system. The MUDS has a bitmap field having a bit corresponding to each block of allocatable memory. A bit corresponding to a selected memory block is set to the value of “1” when the selected memory block is allocated to the selected process. The bit corresponding to the selected memory block is set to the value of “0” when the selected memory block is not allocated to the selected process. A master MUDS is generated by combining the MUDS maintained by each process, the master MUDS having bits set to a value of “0” for free memory blocks, and the master MUDS having bits set to a value of “1” for memory blocks allocated to any processes of the multiprocess computer system. In response to the master MUDS, all memory blocks having a corresponding bit set to a value of “0” are returned to free memory.
The processes may all execute on a single processor, or they may each execute on a single processor in a multiprocessor computer system. A master process may be used to combine all of the MUDS to form the master MUDS. The master MUDS may be formed by combining the individual process MUDS in response to expiration of a timer. Alternatively, the master MUDS may be formed by combining the individual process MUDS in response to a request by a process. When operating on a single processor, the multiple processes may execute under a timesharing operating system.
Each process may execute on a different processor in a multiprocessor computer system. The multiprocessor computer system may be a router where the individual processors are interface processors of the router.
When the multiprocessor computer system is a router the allocated memory may be buffer memory used to store data packets as they are being received and retransmitted. Allocation of the buffer memory to a receive queue is performed in order to maintain an empty receive queue ready to receive the next incoming data packet. Ownership of the buffer memory is transferred from a receiving processor to other processors as the routing process proceeds. Upon completion of routing of the data packet, the buffer memory is returned to the global free queue. The memory usage data structure is referred to, in the case of a router, as the Buffer Usage Data Structure, and is abbreviated BUDS. The master BUDS is generated, and any processor not submitting a processor BUDS does not have any bits in the master BUDS set to a value of “1”. Accordingly, any memory previously allocated to a processor which has crashed, or died, is then returned to the global free queue in response to the master BUDS.
REFERENCES:
patent: 5784699 (1998-07-01), McMahon et al.
patent: 5838994 (1998-11-01), Valizadeh
patent: 5898687 (1999-04-01), Harriman et al.
patent: 6212613 (2001-04-01), Belair
Tanenbaum, Andrew S. and Woodhull, Albert S., “Operating Systems: Design and Implementation,” 1997, pp. 316-318, Second Edition, Prentice Hall, Upper Saddle River, New Jersey.
Berl Steven Howard
Lin Minjie
Cesari and McKenna LLP
Cisco Technology Inc.
Elmore Reba I.
LandOfFree
Distributed buffer recovery does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed buffer recovery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed buffer recovery will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3356066