Dynamic off-screen display memory manager

• US 5,742,797 A
• Filed: 08/11/1995
• Issued: 04/21/1998
• Est. Priority Date: 08/11/1995
• Status: Expired due to Fees

• Current Assignee: Lenovo Singapore Pte Limited (Lenovo Group Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Celi, Joseph Jr., Wagner, Jonathan Mark, Louie, Roger
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US08/513,710
• Time in Patent Office: 984 Days
• Field of Search: 345/185, 345/189, 345/200, 345/201, 345/203, 395/507, 395/497.01, 395/497.02, 395/509, 395/520, 395/492, 395/497.04, 395/497.03
• US Class Current: 345/548
• CPC Class Codes: G06T 1/60 Memory management

Abstract

A display memory manager allocates and deallocates off-screen video memory by dividing the memory space into a plurality of lapping and non-overlapping regions each capable of storing a different amount of digitized display data, and creating a linked list data structure indicative of the allocated and unallocated regions and various combinations of the unallocated regions. Upon receiving a request for off-screen display memory the display memory manager traverses the linked list data structure searching for a region, or combination of regions, large enough to store the requested amount of digitized display data. Once a region or combination of regions has been found and allocated, the linked list data structure is updated to indicate that the new regions are now allocated and hence unavailable to a subsequent requested allocation unless deallocated.

Claims

1. A method of allocating and deallocating off-screen display memory in a computer system, comprising the steps of:

A. receiving a request for a region of off-screen display memory to store a digitized image data;

B. traversing a linked list data structure of off-screen display memory regions organized from a smallest-sized region to a largest-sized region to select a region of unallocated off-screen display memory large enough to store the digitized image data;

C. storing the digitized image data in the selected region;

D. updating the linked list data structure to indicate that the selected region of off-screen display memory is now allocated; and

E. recomputing the various combinations for the remaining unallocated regions of the off-screen display memory and storing the new combinations in the linked list data structure and reorganizing the linked list data structure from a smallest-sized region to a largest-sized region.

2. The method of claim 1, further comprising the steps of:

F. receiving a request to deallocate a region of the off-screen display memory;

G. traversing the linked list data structure to select the element in the linked list indicative of the region in the off-screen display memory to be deallocated; and

H. updating the selected linked list element indicative of the off-screen display memory region to be deallocated to indicate that the region is no longer allocated.

3. The method of claim 2 wherein step D further comprises the steps of:

D2. storing the starling address of the allocated off-screen display memory region in an address field on the linked list element; and

D3. storing the size of the allocated region in a size field of the linked list element.

4. The method of claim 1, wherein step D, comprises the step of:

D1. storing the starting address of the allocated region in a field in the linked list data structure element.

5. The method of claim 1 wherein the steps of the present invention are performed by an operating system of a multi-media multi-tasking computer system.

6. The method of claim 1, wherein the linked list data structure comprise a plurality of linked elements each associated with at least one unallocated region and step B comprises B1 selecting the element associated with the largest sized combination of unallocated regions B2 progressing from element to element in the order of descending sized regions, and B3 selecting the selected region is the smallest region large enough to store the digitized video image.

7. A computer system off-screen display memory manager which allocates regions of unallocated off-screen display memory in response to a request for off-screen display memory storage, comprising:

A. a memory device containing off-screen video memory for storing digitized data;

B. apparatus which maintains a linked list data structure containing elements indicative of the current state of said memory device wherein each element includes a field indicative of the size of the allocated and unallocated memory regions within said memory device and the starting address of each region along with a status flag indicative of whether the region is allocated or unallocated, said linked list data structure organized from a smallest-sized memory region to a largest-sized memory region; and

C. means for searching the linked list data structure in order to select the smallest unallocated region of said memory device larger than the size of the request for off-screen display memory storage and storing the image into the selected unallocated region of said memory device and updating the linked list data structure to indicate that the selected region is now allocated and reorganizing the linked list data structure from a smallest-sized memory region to a largest-sized memory region.

8. The off-screen display memory manager of claim 7 wherein said electronic memory device is VRAM.

9. The off-screen display memory manager of claim 8 further comprising:

a deallocating means for deleting an dement in said linked list data structure in response to a deallocation request of a memory region within said memory device, and for reforming said linked list data structure to ensure that said linked list is indicative of the current state of said memory device.

10. The off-screen display memory manager of claim 9 wherein said memory device is DRAM.

11. A method of allocating and deallocating off-screen display regions in a memory device which stores digitized information in a multi-tasking computer system, comprising the steps of:

A. receiving an allocation request for a region of the electronic memory device;

B. providing a linked list data structure comprises elements each corresponding to a region of the memory device, and wherein each element includes information fields indicative of starling location of the region, size of the region and whether the region is allocated or unallocated;

C. arranging the elements in the linked list data structure from smallest region to largest region;

D. traversing the elements of the linked list data structure to locate the smallest unallocated region in the memory device whose size is larger than the size of the allocation request;

E. storing the digitized data in the located region;

F. updating the linked list data structure to indicate that the selected region of the memory device is now allocated; and

G. resorting the elements in the linked list data structure to ensure that the element associated with the smallest region in the memory device is the first element in the linked list and remaining elements are arranged on the basis of their size in ascending order.

12. The method of claim 11, further comprising the steps:

H. changing the status of a region in the memory device from allocated to unallocated in response to a deallocation command;

I. reforming the linked list by merging any adjacent unallocated regions; and

J. rearranging the elements of the linked list to ensure that the elements are arranged from smallest to largest region.

13. A computer program product comprising:

a computer usable medium having computer readable code means embodied thereon for allocating and deallocating off-screen display memory in a computer system, said program code means comprising;

program code means for receiving a request for a region of off-screen display memory to store a digitized image data;

program code means for traversing a linked list data structure of off-screen display memory regions organized from a smallest-sized region to a largest-sized region to select a region of unallocated off-screen display memory large enough to store the digitized image data;

program code means for storing the digitized image data in the selected region;

program code means for updating the linked list data structure to indicate that the selected region of off-screen display memory is now allocated; and

program code means for recomputing the various combinations for the remaining unallocated regions of the off-screen display memory and storing the new combinations in the linked list data structure and for reorganizing the linked list data structure from a smallest-sized region to a largest-sized region.

14. The computer program product of claim 13, further comprising:

program code means for receiving a request to deallocate a region of the off-screen display memory;

program code means for traversing the linked list data structure to select the element in the linked list indicative of the region in the off-screen display memory to be deallocated; and

program code means for updating the selected linked list element indicative of the off-screen display memory region to be deallocated to indicate that the region is no longer allocated.

15. The computer program product of claim 14 wherein said program code means for updating the linked list data structure further comprises:

program code means for storing the starting address of the allocated off-screen display memory region in an address field on the linked list element; and

program code means for storing the size of the allocated region in a size field of the linked list element.

16. The computer program product of claim 13 wherein said program code means for updating the linked list data structure further comprises:

program code means for storing the starting address of the allocated region in a field in the linked list data structure element.

17. The computer program product of claim 13 in combination with documentation.

18. A computer program product for use in a computer system having off-screen display memory, the computer program product comprising:

a computer usable medium having computer readable program code means for allocating and deallocating the off-screen display memory, the program code means comprising;

first program code means for receiving a request for a region of off-screen display memory to store a digitized image data;

second program code means for traversing a linked list data structure of off-screen display memory regions organized from a smallest-sized region to a largest-sized region to select a region of unallocated off-screen display memory large enough to store the digitized image data;

third program code means for storing the digitized image data in the selected region;

fourth program code means for updating the linked list data structure to indicate that the selected region of off-screen display memory is now allocated; and

fifth program code means for recomputing the various combinations for the remaining unallocated regions of the off-screen display memory and storing the new combinations in the linked list data structure and for reorganizing the linked list data structure from a smallest-sized region to a largest-sized region.

19. The computer program product of claim 18, wherein the computer readable program code means further comprises:

sixth program code means for receiving a request to deallocate a region of the off-screen display memory;

seventh program code means for traversing the linked list data structure to select the element in the linked list indicative of the region in the off-screen display memory to be allocated; and

eighth program code means for updating the selected linked list element indicative of the off-screen display memory region to be deallocated to indicate that the region is no longer allocated.

20. The computer program product of claim 19 wherein the fourth program code means further comprises

program code means for storing a starting address of the allocated off-screen display memory region in an address field on the linked list;

and

program code means for storing the size of the allocated region in a size field of the linked list.

21. The computer program product of claim 18, wherein the fourth program code means comprises program code means for storing a starting address of the allocated region in a field in the linked list data structure.