JPH02133840A - Apparatus for discovering non-allotted memory page - Google Patents

Abstract

PURPOSE: To easily search the unassigned pages within a memory by taking searching procedures of different optimizing systems by each of a pair of exclusive microprocessors. CONSTITUTION: Each bit of a bit map memory 44 shows the page assigning state of a system memory, each of processors 28 and 30 executes the programs stored in memories 62 and 64 and searches the unassigned pages of the system memory. At this time, the processor 28 executes the program which is optimum for the searching of a bit map with high occupancy ratio by searching the bit map 44, the processor 30 executes the program optimum for the searching of the bit map with low occupancy ratio by searching each of an X register and a Y register and by inspecting the contents of the bit location of the bit map 44. Thus, unassigned pages in the memory can be easily discovered.

Description

DETAILED DESCRIPTION OF THE INVENTION A. Field of Industrial Application The present invention relates to the field of data processing, and in particular to operations for determining how memory pages are allocated in a computer system. 6B. Prior Art and Its Related Art Problem Bit maps are a compact way to store data representing the allocation status of memory pages in a computing system. The position of an unallocated page can be determined by an algorithm from the position of a bit in a predetermined state. Can you give me the distribution?

There are several ways to search a bit map, but their characteristics can be broadly divided into two. One is efficient when the bit map occupies few unallocated pages, and the other is efficient when the bit map occupies high.

There are many articles and patents describing memory search capabilities, each with their own advantages and disadvantages.

IBM TDB November 1979 issue, vOl, 2
2, No, 6. pp. 2489-90, “Translation for Parallel Tables”
e Directed Translation describes a method for performing vector operations such as search processes. This method uses multiple processors simultaneously and is solely based on comparing search arguments in SIMD (Single Instruction 111 Data Stream) parallel processors. In methods that can use parallel computing, multiple search arguments of the same or different types are searched in the same table to obtain multiple results.

This method is particularly useful for parallelism (p
) is a simultaneous translation of the search arguments, and the vector forms a search tree with pre-ordered binary values on parallel (p) processors.
Therefore, each processor must independently compare the search argument with the result of recursively scanning copies of the search tree in a fixed order. A match indicates a match between the search argument and the translated value; otherwise, either the left or right side of the search tree is searched to see if the search argument is greater or less than the node value, respectively.

U.S. Pat. No. 4,482,956 addresses the ability of a single chained queue to operate in parallel with multiple element insertion routines and one deletion routine. The routine is m
can be executed asynchronously and simultaneously on u's processors, deleting an element on the one hand and inserting one or more anchor-directed elements on the other hand. This is done by a dequeue lock, which is examined only by program routines that delete elements and insert anchor-directed elements into the queue (via System/370 compare/swap instructions). Not examined by program routines.

U.S. Pat. No. 4,639,856 discloses a dual stream system for use in a multiprocessor computer system.
I'm talking about processors. This multiprocessor computer system has two mechanisms for both processors, which are used when one of the processors becomes inoperable. A second mechanism is located within the disabled processor and maintains its functional operation.A second mechanism is also located within the disabled processor and sends a shortage signal to the other processor that is capable of functional operation.The other processor receives the shortage signal. If the other processor cannot locate the data in its own cache, it will be unable to locate the required data in the cache of the inoperable processor.

Means for Solving the C1 Problem An object of the present invention is to provide a means for determining how memory pages in a computer system are allocated.

An object of the present invention is to provide means for determining memory page allocation in a computer system by searching for contention between a pair of processors.

It is an object of the present invention to provide a mechanism for searching a bit map indicating memory page allocation status in a computing system. Therefore, a competition search is performed between the pair of processors. Each processor searches for an unallocated page in memory using a search procedure using a different optimization method. The lagging processor updates its bit map and registers.

In other words, the bit map search function according to the present invention is as follows:
Bit maps are searched in parallel using search methods with different optimization methods so that the search is optimal for various conditions. In the bit map search described here, each of a pair of dedicated microprocessors uses a search procedure with a different optimization method, and competes to see which one will first find a bit indicating an unallocated page. The first processor to locate such a bit will interrupt the losing processor. The losing processor takes the bit position and updates the bit map and summary buffer, while the winning processor calculates the free page position and notifies it to the larger system.

D. Embodiment A bit map is a compact means of storing data indicating the allocation status of storage pages in a computer system.The location of an unallocated page can be determined by an algorithm from the position of a bit in a given state. can. The state of the bit map is represented by the occupancy and distribution of bits in states indicating the presence of unallocated pages.

There are several ways to search a bit map, but their characteristics can be broadly divided into two. One is efficient when there are few unallocated pages occupying the bit map, and the other is efficient when there are few unallocated pages occupying the bit map. is efficient when is high.

In a bit map, if the occupancy rate of bits indicating unallocated pages is high, it is easy to quickly find bits in the desired state by sequentially searching. If the occupancy of such bits is low in the bit map, sequential searching typically takes a significant amount of time. Compressing bit map data results in loss of information, but it can be converted into a condensed form.

Such summary data can be represented by a pair of registers. Each register has a number of bits, the number of bits corresponds to the number of rows or columns in the bit map.6 The bits in the register indicate an available page if at least one bit is in the column or row of the bit map. Set. A search procedure can be established that examines the summary register to find the row or column of the bit map that contains the bit to be searched. All this method requires is to examine the bits in one of the summary registers, followed by one bit in the bit map.
All it does is examine the contents of the rows (sequentially). If the number of bits is sparse and it is unlikely that useful bits will be found even after searching two rows, this method is faster than the sequential search through the bit map.The second search procedure using summary registers is , all of the pit locations indicated by the row and column bits in the summary register are to be searched sequentially. The space explored in this way is only as large as the product of the number of bits in the summary register. This is a method comparable to

It is customary for storage management systems to be implemented as a single integrated circuit whenever possible. However, the illustrated embodiment assumes that each of the logical elements of the system is incorporated as part of a large scale integrated circuit. Of course, the logic elements can be implemented as individual devices or in combination with integrated circuit devices.

The central processing unit (CPU), which operates as the serviced processor or context processor, accesses system memory (storage) via the global bus.
connected to. It is also connected to subsystems via local buses. The subsystem is responsible for determining the allocation status of pages within system memory. The subsystem includes two microprocessors.

Local memory for each microprocessor, 2 ports of bit map memory, status reporting logic,
There are a register and a Y register.

A bit map memory of size X bits by X bits (where the product of The microprocessor is connected to the internal bus of the CPU in which the subsystem is embedded.

The CPU attempts to read the page number of a free page in memory from this internal bus. The local bus can also be used to provide data to the system, such as page numbers of deallocated memory pages. local·
In addition to the data report line of the bus (the line through which page counts are committed), lines are used that convey system status to the CPU and that also receive commands from the CPU. The cpu commands include reset,
The initialize, start bitmap search, and update bitmap memory commands can be used to mark a page as empty. In a typical embodiment of the system, status reporting is performed on at least three lines to convey the following states of the subsystem: dormant, searching, data available, system failure, and no free pages. These lines are typically driven by logic circuits that receive status information from both processors and the service request line, from which the service request line derives the exact status of the status report line.

Both embedded microprocessors have length X
and Y can be accessed. The contents of the register are hardware support functions intended for the search algorithm executed by the processor. Therefore, this processor can preferentially access each register. However, the register here indicates the algorithm.
This is an example. Specific support hardware and other support hardware may also be selected to speed up execution of other search algorithms without departing from the spirit of the invention.

Each microprocessor is capable of executing programs stored in memory that is low power to it.

Means for modifying this program is also provided. Modifications can be made by overwriting local memory or by causing the processor to execute programs located in other accessible memory. Each processor can interrupt the execution of the other processor by providing an interrupt contact.

The subsystem's processors begin execution at power-up by setting bit map memory and bits in the x-y registers to indicate that the page is available. In this example, this state is set to "ON" or "1", and the processor then enters a state in which it waits for a command from the context processor, for example to find the address of a free page in the map.

To understand the operation of the system, it is necessary to know the search algorithm of the processor. The search algorithm chosen for the processor is optimized to perform the search as quickly as possible as the state of the bit map changes. Memory states indicating free pages generally occupy either a high or a low percentage of the bit map. In this example, the first
Assume that the processor's search algorithm is a simple sequential search, in which the state of each successive bit of memory is examined. Meanwhile, the second processor uses X and Y registers to maintain a summary data of the bit map state, in which if any bit in the i-th row of the bit map indicates an available page; The i-th bit of the Y register indicates page availability; similarly, if any bit in the j-th column is set to ``ON'', the
The jth bit of the register is -ON'', the second processor thus performs the search with the help of hardware, the Y register is examined first and the line to be searched is found. The X register is then examined to determine which of the individual bits to search, where:
These algorithms were chosen for reference; there is a clear difference in efficiency between high-occupancy bitmaps and low-occupancy bitmaps7.
Other algorithms may also be selected without departing from the spirit of the invention.

When the state of the command line changes, indicating the start of a search, both processors begin executing their respective stored programs representing their respective search algorithms. This command line and processor state change is encoded by the status reporting logic to indicate continuation of the search. The first processor, in step with its program, goes directly to the bit map, finds the bit indicating the address of a free page (because the bit map is occupied by l), and interrupts the second processor. Converts the found bit position to a page number and sets the page number on the data line to signal the status control logic that the search is complete. The status line control logic then changes the status line to indicate that data is available.

The second processor was searching the summary register when the first processor completed its search, so it did not find any free pages.After receiving an interrupt from the first processor, the second processor reads the data line that was created and changes the contents of both the bit map and the summary register to reflect the allocation state (unavailability) of the page found.

The process of allocating and deallocating pages continues until the two processors' search algorithms have approximately the same probability of completing the search, and which processor searches first depends on the state of the bit map memory and It depends on whether the In some cases, a request is made for a number of free pages, which both processors race to find. In this case, the data in the summary register processed by the second processor points to a bit in the bit map that is effectively free, and the second processor determines the state of the bit before the first processor locates the bit indicating a free page. When verifying the page number, the second processor interrupts the first processor and decodes and asserts the retrieved page number.Meanwhile, the first processor in parallel Updates the summary register, where the processor updates the state of the bit map entry, since the summary register only indicates that each bit is likely to be 1, not that it is actually 1. must be verified.

While events are proceeding normally, pages are deallocated by the operating system of the context processor.1 Deallocation means that if (for example) the first processor first updates its memory map and then its summary register, Continued by that processor.

If there are no pages available, register this condition with “
It is the second processor that first determines from the absence of the ON" bit. After this determination, the second processor notifies the status line control logic, which encodes that state of the status line. The first processor may be halted by this operation.The context processor's operating system then deallocates the required number of pages if only one register indicates that it does not have an "ON" bit. , which indicates a system failure.

Any part of a computer system can fail. 1[
A failure of a system processor is signaled by status line logic which is activated by the failure of that processor and begins processing in response to commands. This failure can then be reported via the status line. However, this system is fail-soft to certain processor failures. This allows continuous operation, although it may slow down the operation.

When a "reset" command is issued, both processors are halted and returned to a command ready state. "
When the ``Initialize'' command is issued, both processors each execute a power-up (sequence) command, which causes the bit map to have all bits set to ``ON''.

The present invention will be explained in detail below. FIG. 1 is a general block diagram of the system. CPU 2 is a global
It is connected to system memory 4 via bus 6 . D.A.
Other devices such as SD 8 and terminal IO can also be connected to bus 6 via channels (CH) 12 and 14, respectively. The system memory can be any size that is easy to handle, but in this explanation it is assumed to be 32 x 32 pages. Each page is 4096
bytes (4 kilobytes).

The allocation status of pages of system memory 4 is connected to CPU 2 via local bus 18 . stored in subsystem 16; CPU 2 and subsystem 16 may be formed on a single integrated circuit chip 20, or may be formed as separate devices or in a combination of integrated circuits and devices.

FIG. 2 is a detailed block diagram of subsystem 16 of FIG. Local bus 18 is connected to command bus 22. It consists of a data bus 24 and a status bus 26. Command bus 22 connects to microprocessor 2 via lines 32.34.
8.30 and via line 35 to status report logic 33. Data bus 24 is line 3
6 and 38 to the processor 28.30.

Status bus 26 connects to status report logic via line 40. Processors 28 and 30 connect to interrupt line 4.
2, each processor is connected via line 46.48
to a two-vote bit map memory 44. Processor 28 connects X register 50 and Y register 52 via lines 54.56, and processor 30 connects X register 50 and Y register 52 via line 58.60.
Leads to. Processor 28 is connected to local memory 62, and processor 30 is connected to local memory 64. The activity code and code strobe are output from processor 28.30 to logic circuit 33 via lines 37 and 39, respectively.

The bit map memory 44 is 32 bits x 3 in size.
2 bits, each bit in system memory 4 (Figure 1)
For convenience of explanation, the allocation status of a given page in
The present invention adopts the following arrangement. That is, the memory 44
If the predetermined bit of the memory 44 is "l", the associated page of the system memory 4 is not allocated; conversely, if the predetermined bit of the memory 44 is "0", the associated page of the system memory 4 is allocated.

X register 50 and Y register 52 are each 32 bits long. See Figure 1O for a description of the function of registers 50,52.

The bit map 44° is 4 bits x 4 for easy understanding.
Similarly, the registers 50° and 52° are each 4 bits long, and the row “0” of the 6-bit map 44 is
If at least one bit of " is 1, the Y register 52
The bit at position 10” is also l. Conversely, the bits in row “o” of bit map 44° are all 0 as shown in the figure.
If so, the bit at the "0"' position of the Y register 52' is also 0 as shown. Row position 1 of Y register 52
．． 2.3, each bit is l. This corresponds to at least one bit position in row 1.2.3 of bit map 44° being 0. In the X register 50', bit position 0 is 0. This is column 0 of bitmap 44°
This is because the bit positions are each 0. X
The bit at column position ff1l, 2.3 of register 50' is l. This corresponds to having a 1 in at least one bit position in column 1, 2.3 of bit map 44°.

Each processor 28.30 executes a program stored in a memory 62.64 and a system memory 4 (
Search for unopened pages in Figure 1). The processor 28 is
The details will be explained in conjunction with Figure 8, but bit map 4
By searching for bitmaps with a high occupancy rate, the optimal program is executed. processor 30
As will be described in detail in conjunction with FIG. 9, searching the X register and Y register respectively, and
By inspecting the contents of the bit positions in map 44, a program is executed that is optimal for searching for bit maps with low occupancy. The details of these programs are summarized below.

When a free page is needed, CPU 2 (Figure 1)
begins examining the allocation status of pages in system memory as indicated by bit map memory 44 by setting the command line to the appropriate code.

Each processor's response to this command is encoded by status report logic 33. This allows C
The PU 2 may determine the responsiveness of the subsystem based on the activity of the processor 28.30 as indicated by the status reporting logic 33. Commands coming from CPU 2 via command bus 22 on line 62 are held in latch buffer 65, and at the same time commands are
A command strobe is applied on line 66 from bus 22. This indicates that the status of the command line is valid.The properties of these commands are summarized below.

The activity code and code strobe are provided on line 37 from processor 28, and similar connections are provided on line 39 from processor 30. Commands and activities that are held (latched)
The code is connected to the address via lines 68 and 70, respectively.
is applied to decoder 72 , and accordingly decoder 72
sends the status code selection address on line 74 to memory matrix 76. The matrix receives the applied address signal and outputs a status code on line 76 to an output buffer 88. Buffer 88 provides a subsystem status report signal on line 90 and a status strobe on line 90 to indicate that the status report is valid, on status bus 26 and to CPU 2.

The table of FIG. 4 shows typical (but not all) commands provided from the CPU 2 to the status report logic 33 via the command bus 35. Such commands include "No Activity J (000)". , Initialization (100), [Deallocation J (010), [
Search J (001) four items are shown. As explained later, a reset command can be indicated by any command that sets "l" on two or more command lines (as simplified as in this example). Can be done.

FIG. 5 is a flow diagram of the program executed by both processors of the subsystem to determine which command is required.
, ie, indicates a 1-no-activity command. If the answer is YES then 1
Branching back to input 100, another command is searched.

If the answer is NO, the process moves to decision block 102 where a determination is made whether a "Start Search" command has been received. . If the answer is YES, a search is initiated by processor 28.30 as shown at 104.

The details will be described in conjunction with FIGS. 8 and 9.

If the answer is no, the process moves to decision block 106 where a determination is made whether the command is "Start Deallocation." If the answer is YES, page deallocation is initiated as shown at 108. This will be explained in detail in conjunction with FIG. If the answer is no, the process moves to decision block 110 where a determination is made as to whether the command is "initialize". If the answer is YES, the initialization process begins as shown at 112. Details of this are shown in Figure 6. If the answer is no, then
The IJ top set command is processed.

Processor initialization is initiated for processors 28 and 30 in response to an "Initialize" command. A flow diagram of the initialization process 112 (FIG. 5) is shown in FIG.

Here, the activity code is set and "initialization" is instructed.The current address is x=0.0 as shown at 120. y=0 is set, after which bit (x,y) of the bit map is set to 1 as shown at 122. At step 122, the X register 50 and Y register 52 in FIG. 2 are also set to zero, and the value of X is increased by one as shown at 124. At 126, it is determined whether x=X. where X is the number of columns in the bit map. If the answer is no, the process branches back to 122 and returns to 1
122.124.12 until the answer at 26 is YES
6 is repeated. The process then proceeds to 128 where X is reset to 0 and y is incremented by one value. The process then proceeds to decision block 130, where it is determined whether y=Y. where Y is the number of rows in the bit map. If the answer is no, the process branches back to 122, 124, 126 and 1 until the answer to decision block 130 is YES.
28 is repeated. If YES, all bit positions are initialized. The activity code is then set to "initialization complete" as shown at 132.

Details of deallocation process 108 (FIG. 5) are shown in FIG. 7 for processor 28.30.

Here, it is assumed that the status bit of the page is at position (x, y) of the bit map, and the page is to be deallocated. The deallocation process for processor 28 begins at 134 . Activity at 136
The flag is set to ``page deallocation''.
At 38 bit map bit (X%y) is set to l.

The process completes at 140 and the activity flag is set to "Pl Complete."

The deallocation process for processor 30 is 142
start from. At 144, the activity flag is set to "Fpage Deallocation". Then at 146, the bit (X) of the X register is set to l. At 148, bit (y) of the Y register is set to l. The process completes at 150 and the activity flag is set to ``rP2 Completed''.

The "start search element" command 104 (FIG. 5) causes the processors 28, 30 to simultaneously begin a search procedure to search for an unopened page in the system memory 4 (FIG. 1). The search procedure is optimized to allow quick searches even as the state of bit map 44 (FIG. 2) changes. The occupancy of the bit map 44 is determined by the memory state indicating free pages in the system memory 4;
High, low, or somewhere in between.

By way of example, the search processor of the first processor 28 is optimized to search for highly occupied bit maps by a simple sequential search. In this sequential search, bits
The state of each successive bit of map memory 44 is examined. FIG. 8 shows details of the search process of processor 28.

As an example, the search process of the second processor 30 may include x,
Y registers 50 and 52 (Figure 2) are optimized to search for low-occupancy bit maps. , if any bit in the i-th row of bit map 44 indicates that the page is available, then the i-th bit of Y register 52 indicates that the page is available; If any bit in the column is 1, the j-th bit of the X register 50 is l. Therefore, the second processor 30 executes the search with the support of the hardware, and the X register 50
are examined to determine which columns of the bit map are each available, and Y register 52 is examined to determine which locations of these columns are available. The search process of processor 30 is shown in detail in FIG.

The search process described below was chosen as an example because there are distinct differences in search probabilities when searching bit maps with either high or low occupancy. Other search procedures may also be implemented without departing from the spirit of the invention.

As mentioned above, the first processor 28 (FIG. 2) takes a search procedure that is optimal for highly occupied bit maps. A typical example of such a search procedure will be described in conjunction with FIG. 8 regarding sequential search of a bit map. If you refer to FIGS. 10 and 11 at the same time, it will be easier to understand the flowchart in FIG. 8.

FIG. 1O is a map of 4 degrees of system memory corresponding to 16 pages, and shows the correspondence between pages and bits of a 4.times.4 bit map 44 degrees. A 4-bit X register at 50° and a 4-bit Y register at 52° are also shown.

While the size was set to 32 in the explanation of Figures 1 and 2, the size is set to 4 bits here to make it easier to explain the search procedure for the bit map corresponding to Figures 8 and 9. It's for a reason. Bit map 44'' indicates an unopened page with a binary value of -1''. Bit map position (2,
1), (1,2), (2,2), (3,2) (3,3)
are the binary values “l” and are pages 9, 6, 10, and 14 of unopened system memory shown at 4 degrees, respectively.
．． Corresponds to 15. Position 0 of the X register 50° is '''0
”, indicating that the bit positions in column 0 of bit map 44° are all “0”, positions l, 2.3 of X register 50° are each “1”, and bit map 44° For example, the position (l, 2) in column l is "l", the position (2, l
) and (2,2) are "1" 1 row 3 position (3,2) and (3
, 3) is "l-," and position 0 of the Y register 52 is "
0", indicating that all bit positions in column 0 of bit map 44° are "0".

Positions Ml, 2, 3 of Y register 52' are each "l" indicating that at least one position in column 1.2.3 of bit map 44° is "1", e.g., row l The position (2, l) is “l-1 row 2 position (l, 2),
(2, 2) (3, 21 is “l”, row 3 digit g1 (3, 3
) is ``l''.

FIG. 8 shows a sequential search of the bit map by the processor 28 (FIG. 2), which is optimal for bit maps with high occupancy. set to ``Medium'' (154)
, 156, X and y are each set to O, which corresponds to position (0,0) of bit map 44'. 1
At 58, a test is made to determine whether bit (0,0) of bit map 44' is equal to "l". Since the position (0,0) of the bit map is "0", the answer is NO. This is the 0th order 160, which corresponds to step A in Figure 11, and X increases by 1 to x+1, so x=1
becomes. It is determined whether x=X. x=4,
The bit map is of size X of 44 degrees. Since x=1, X is not equal to X, and the step returns to 158. Here, bit (x, y) becomes bit (I, 0).

This is as shown in step B of FIG. Bit (1
, 0) is “0” as seen from bit map 44
′. Therefore, the search proceeds to 160 and X increases by 1 to 2. In 162, X (=2) is X (=4)
Since the bits (x,
y) becomes bit (2,0), and step C in Figure 11
As shown. Bit (2,0) is 10'' as seen from the bit map 44°, so the search proceeds to 160 and the value of X increases by 1 to 3, 162
Since x (=3) is not equal to X (=4), 158
11, where bits (x, y) become bits (3, 0), as in step D of FIG. bit·
As you can see from the map, it is "0". Therefore, the search proceeds to 160 and X increases by 1 to 4. 162, X (=4) is X as shown in step E of FIG.
(=4), now the search proceeds to 164, and X is 0
The value of y is increased by one and becomes y=1. As the search progresses, it is determined whether y=y. Here Y=4
That is, the Y size of the bit map is 44 degrees. In this example, y (=1) is not equal to Y (=4), so the search proceeds to 158, where bit (x, y) is equal to bit (0, 1) as shown in step F of Figure 11. , bit (0,l) is “0” as shown in bit map 44°
Therefore, the search proceeds to 160, where X increases by one value and becomes x=1. In 162, x (=1) is
4), so it returns to 158 and bits (x, y
) is the bit (1, 1
), the bit (1°1) is "〇-" as shown in the bit map 44°, so it returns to 160, and X increases by one and becomes 2. At 162, x (=2) becomes X (=4 )
is not equal to , so we go back to 158 and bit (x, y) becomes bit (2°l) as shown in step H of Figure 11, bit (2,1) becomes “ P2, processor 30 (FIG. 2), is interrupted as shown at 168 and is informed that it has lost the search race. At 170, the data line is set to xY+y and the system
The number of available pages in memory is indicated. In this example, the result is (2).(4)+(1)=9. The nine pages indicated by system memory map 4° correspond to location (2,l) in bit map 44°. An activity code is set at 172 to indicate that the number of available page (9) in system memory is on the data line. If each position of bit map 44° is "0", this indicates that there are no pages available, and the search will eventually proceed to 166,
At this time, y (-4) = Y (=4). After this, as shown at 174, the activity code is [
Set to ``No Pages Available''.

FIG. 9 shows the best fit for low-occupancy bitmaps with hardware support (by processor 30).
Hardware support, illustrating bit map searches, is implemented in the X register 50' and Y register 52' as shown in FIG. 1O. In FIG. 9, the search begins at 176 and the activity code is set to "Searching" as shown at 178. Bits X and y are each set to "0" at 180. This corresponds to step A in FIG. At 182, the bit (0) of the X register is found to be “0”, so the search proceeds to 184 and the X
The value of increases by one and becomes x=1. At 186, x (=1) is not equal to X (=4), so we return to 182 and find that bit (1) of the X register is not equal to '0' because its position l is 'l'. .This indicates that at least one is “1” in column l of bit map 44°.In 188, bit (0) of Y register is ``“0”
It is determined whether it is equal to or not.

This means that all bit positions in column 0 are "0". This also corresponds to step B in FIG. The search proceeds to 190, where y increases by one value and becomes y=l. 1
At 92 it is found that y (=l) is not equal to Y (=4) and the search returns to 188.

Bit (1) of the Y register is “0” because position l is “l”.
This indicates that at least one position in column l is “1”, the search is then 19
4, it is determined whether bit (1,1) of bit map 44° is '1''. This corresponds to step C in FIG. 12. Bit map position ft(1,1) is “0”, so the answer λ is NO. Next, return to 190 and y
increases by one and becomes 2 7 At 192, yC=2) is Y(=
4), the search returns to 188 to determine if bit (2) of the Y register is equal to "0". Since bit 2 is -1'', the answer is NO and the search proceeds to 194 to determine whether bit (1,2) is equal to 'l''. This corresponds to step D in FIG. Bit (l,2) of bit map 44° is "1", indicating that there is an unallocated page in system memory map 4°, as shown at 196, in the PI or processor 28 of FIG. It is informed that the PI was unable to search due to an interruption. In 198, data
The line is set to xY+y, (1) ・ (4)
+(2)=6. This indicates that page 6 of system memory map 4° is unallocated. Page 6 of system memory map 4° corresponds to position (1, 2) of bit map 44°. I understand. At 200, the activity code is set;
Indicates that the number of available pages is set in the data line. If each bit position in the X register 50° is '0', indicating that there is no page available, the search proceeds from 186 to 202 and the activity code is set to 'no page available'.

If the X register is found to be "1" and the Y register is not "l", an error is indicated by a return to 192 or 6204, and the activity code is set to indicate the error.

It will be apparent to those skilled in the art that the resources of this subsystem may be utilized by other search algorithms, including those with hardware support similar to those shown in FIG. In one example algorithm, each processor uses one or the other register for preliminary searches. Similarly, the sequential search of FIG. 8 can be improved by setting (x,y) in step 156 equal to the next page number of the page allocated after m. Examples or variations thereof involving such hardware support do not depart from the spirit of the present invention.

E. Effect According to the present invention, for example, one processor performs a bit map search suitable for when there are many unallocated pages, and the other processor performs a bit map search suitable for when there are few unallocated pages. - It becomes possible to perform map searches, thereby improving the performance of the computer system.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of the computer system and subsystems. FIG. 2 is a detailed block diagram of the subsystem outlined in FIG. 1. FIG. 3 is a detailed block diagram of the status report logic circuitry outlined in FIG. 2. FIG. 4 is an explanatory diagram briefly showing commands used when implementing the present invention. FIG. 5 is a flow diagram showing how the commands of FIG. 4 are differentiated by subsystem. FIG. 6 is a flow chart showing how to initialize the processor. FIG. 7 is a flow diagram illustrating how pages are deallocated. FIG. 8 is a flowchart illustrating details of the sequential search of a bit map in accordance with the present invention. FIG. 9 is a flow diagram of a hardware supported bit map search in accordance with the present invention. Figure 10 depicts the system memory, bit map, and X and Y registers to help you understand the bit map conflict search flowchart shown in Figures 8 and 9. It is. FIG. 11 is an explanatory diagram showing the steps of the search procedure shown in FIG. 8. FIG. 12 is an explanatory diagram showing the steps of the search procedure shown in FIG. 9. 2...CPU, 4...System memory, 6...
...Global bus, 16...Subsystem,
18...Local bus, 20...Integrated circuit chip, 28.30...Processor, 33...Status report logic circuit, 44...2 port bit...
Memory 50...X register, 62.64...Local memory, 108...Deallocation process, l12...Initialization process Applicant: International Business Machines
corporation

Claims (1)

Claims: An apparatus for finding unallocated memory pages in a computer system, comprising: a central processing unit; a memory comprising n memory pages (where n is an integer); comprising n bits; bit map memories, each holding a bit map indicating the allocation status of an associated page in said memory; examining n bits of said bit map to discover unallocated pages in said memory; a pair of processors competing in a separate manner, and after one of the pair of processors discovers an unallocated page in the memory, the location of the discovered unallocated page in the memory is determined by the central processor; A device for finding unallocated memory pages, comprising means for communicating to the device.