Bit map search by competitive processors

• US 4,992,935 A
• Filed: 07/12/1988
• Issued: 02/12/1991
• Est. Priority Date: 07/12/1988
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Goldstein, Barry C., Comerford, Liam D.
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): CHUN, DEBRA
• Application Number:
  US07/218,174
• Time in Patent Office: 945 Days
• Field of Search: 364/200, 364/900
• 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

Abstract

A method and apparatus for performing a bit map search of the allocation state of memory pages in a computing system. A competitive search is accomplished by a pair of dedicated microprocessors, each of which implements a differently optimized search procedure, to find a bit indicating an un-allocated page in the memory. The first processor to find such a bit interrupts the other processor. The first processor then calculates the free page location and informs the computing system of the location. The other processor is responsible for updating the bit map and summary buffers.

Claims

1. In a computer system, apparatus for determining the allocation of memory pages, comprising:

a central processor;

a memory, including n, where is an integer, memory pages, with said memory connected to said central processor;

a bit map which includes n bits, each of said n bits being indicative of the allocation state of an associated page in said memory;

a pair of processors, each of which is connected to said central processor and said bit map, and each of which implements a different competitive search procedure of said bit map, to determine an un-allocated page in said memory; and

means for the first processor of said pair of processors to determine an un-allocated page in said memory as the result of said search procedure, to communicate the location of the un-allocated page in said main memory to said central processor.

2. In a computer system, apparatus for determining the allocation of memory pages, comprising:

a central processor;

a memory, having n×

m memory pages, where n and m are integer, with said memory connected to said central processor;

a bit map which includes n×

m bits, with the state of each bit being indicative of whether or not an associated page in said memory is allocated or un-allocated, with a given bit being in a first state when its associated page is un-allocated, and being in a second state when its associated page is allocated;

a first processor connected to said central processor and said bit map, and which performs a first search procedure, optimized for a bit map densely populated with bits in said first state, of said bit map in response to a search request from said central processor to determine an un-allocated page in said memory;

a second processor connected to said central processor, said first processor and said bit map, and which performs a second search procedure, optimized for a bit map sparsely populated with bits in said first state, of said bit map in response to said search request from said central processor to determine an un-allocated page in said memory; and

means for the first one of said first and second processors to determine an un-allocated page in said memory as the result of the search procedure to communicate the location of the un-allocated page in said main memory to said central processor, and to interrupt the search procedure of the other one of said first and second processors.

3. In a computer system, the combination comprising:

a central processor;

a system memory comprised of n pages, where n is an integer, said memory being connected to said central processor;

a subsystem connected to said central processor for determining the allocation state of said n pages in said system memory, said subsystem including;

a bit map having n bits, with each of said n bits being indicative of the allocation state of an associated page in said system memory;

a pair of processors, each of which is connected to said central processor and said bit map, and each of which performs a different bit map search procedure to find an un-allocated page in said system memory, in response to a search request from said central processor; and

means for the first processor of said pair of processors to find an un-allocated page indication in said bit map to communicate the location of the associated page in said system memory to said central processor.

4. The combination claimed in claim 3, including:

means for the first processor of said pair of processors to interrupt the bit map search procedure of the second processor of said pair of processors in response to said first processor of said pair of processors finding an un-allocated page in said system memory.

5. The combination claimed in claim 4, including:

means for the second processor of said pair of processors to update the allocation state of the found un-allocated page of said bit map from un-allocated to allocated following the interrupt from said first processor of said pair of processors.

6. In a computer system, the combination comprising:

a global bus;

a central processor connected to said global bus;

a system memory connected to said central processor via said global bus, a system memory having n×

m pages, where n and m are integers;

a local bus connected to said central processor;

a subsystem connected to said central processor via said local bus, for determining the allocation state of pages in said main memory in response to search requests by said central processor, said subsystem including;

a bit map having n×

m bits, with each bit being indicative of the allocation state of an associated page in said system memory;

a first processor connected to said central processor via said local bus and connected to said bit map, which performs a first search procedure of said bit map to find an un-allocated page in said system memory in response to a search request from said central processor;

a second processor connected to said central processor via said local bus and connected to said bit map, which performs a second search procedure, different than said first search procedure, to find an un-allocated page in said system memory in response to said search request from said central processor; and

means for the first one of said first processor and said second processor to find an un-allocated page in said bit map to communicate the location of the associated page in said system memory to said central processor.

7. In a computer system, apparatus for determining the allocation of memory pages, comprising:

a central processor;

a memory connected to said central processor, and having n rows by m columns of memory pages, where m and n are integers;

a bit map which includes n rows by m columns of bits, with the state of each bit being indicative of whether or not an associated page in said memory is allocated or un-allocated, with a first bit state being indicative of an un-allocated page and a second bit state being indicative of an allocate page;

a first register of n bits which holds a summary of the bit map state of each of said n rows, with the i'"'"'th bit of said first register being in said first bit state if at least one at the bits in the i'"'"'th row of said bit map are in a said first bit state, and being in said second state;

a second register of m bits which holds a summary of the bit map state of each of said m columns, with the j'"'"'th bit of said second register being in said first bit state if at least one of the bits in the j'"'"'th column of said bit map are in said first bit state, and being in said second bit state if all the bits in the j'"'"'th row are in said second state;

a first processor connected to said central processor, said bit map and said first and second registers, and which performs a first search procedure of said bit map in response to a search request from said central processor to determine an un-allocated page in said memory with said first search procedure being optimized for said bit map being densely populated with bits in said first bit state;

a second processor connected to said central processor, said bit map and said first and second registers, and which performs a second search procedure of said bit map by searching said first and second registers in response to said search request from said central processor to determine an un-allocated page in said memory, with said second search procedure being optimized for said bit map being sparsely populated with bits in said first bit state; and

means for the first one of said first and second processors to find an un-allocated page in said memory as a result of said first and second search procedures, to communicate the location of the un-allocated page to said central processor.

8. The combination claimed in claim 7, including;

means for interrupting the search procedure of the one of said first and second processors that did not find an un-allocated page; and

means for said one of said first and second processors to update the allocation state of said bit map, to reflect that said un-allocated page found in the search procedure has been allocated to said central processor.

9. A method of determining the allocation state of n, where n is an integer, pages in a memory, said method comprising the steps of:

changing the state of each of n bits in a bit map to reflect the allocation state of an associated page in said memory with a given bit being in a first state when allocated and a second state when un-allocated;

performing a first search procedure of said bit map by a first processor to determine an un-allocated page in said memory;

performing a second search procedure, different than said first search procedure, of said bit map by a second processor to determine an un-allocated page in said memory; and

providing the location of an un-allocated page in said memory by the first one of said first and second processors finding a bit in said bit map being in said second state, which reflects its associated page in said memory being un-allocated.

10. A method of determining the allocation state of pages in a n×

m, where n and m arE integers, page memory operative with a central processor, with a bit map which includes n×

m bits, with the state of each bit being indicative of whether or not an associated page in said memory is allocated or un-allocated, with a given bit being in a first state when its associated page in said memory is un-allocated, and being in a second state when its associated page in said memory is allocated, said method comprising the steps of;

performing by a first processor, a first search procedure for bits in said first state, optimized for a bit map densely populated with bits in said first state, of said bit map in response to a search request from said central processor to determine an un-allocated page

performing by a second processor, a second bit map search procedure for bits in said first state, optimized for a bit map sparsely populated with bits in said first state, of said bit map in response to said search request from said central processor to determine an un-allocated page in said memory; and

informing said central processor of the location of an un-allocated page in said memory by the first one of said first and second processors finding a bit in said bit map in said first state.

11. The method of claim 10, including the step of:

interrupting the search procedure of the one of said first and second processors that failed to find an un-allocated page in said memory, in response to said first one of said first and second processors finding a bit in said bit map in said first state; and

updating the allocation state of said bit map by the one of said first and second processors that failed to find an un-allocated page in said memory, to reflect that the un-allocated page found in the search proceeding has been allocated to said central processor.