Arrangement for monitoring the state of memory segments

Claim 1

In a system for monitoring the working memory of a computer equipped with a processing unit in order to locate, upon request by a program being carried out in the computer and under control of respective algorithms, a group of L contiguous unoccupied memory locations, mark such locations as occupied and make them available for use by such requesting program, and in order to release a previously occupied group of memory locations no longer needed by such program and mark such locations as unoccupied, and in order to specially treat those working memory locations which contain base addresses, constituting pointers to other groups of working memory locations, the improvement comprising: means including a 1-bit direct access memory state register and a 1-bit direct access base address status register, each register containing an address decoder and having a plurality of single bit stages, with each stage corresponding to a respective location of the working memory, means for connecting said memory state register to the working memory for setting each stage of said memory state register to one binary state when its corresponding working memory location is occupied and to the opposite binary state when its corresponding working memory location is unoccupied, and means for connecting said base address status register to the working memory for setting each stage of said base address status register to the one binary state when its corresponding working memory location is occupied by a base address and to the opposite binary state when its corresponding working memory location is not occupied by a base address; a first group of status flip-flops arranged to provide signals indicating the algorithm to be executed by said system and arranged to be set by, and interrogated by, the computer processing unit; a second group of status flip-flops connected to control inputs of said state register and said status register and providing signals indicating which of said state register and status register is to be subjected to an operation; arithmetic-logic function unit means including an adder circuit and an indicator circuit connected to said state register and said status register, said indicator circuit including a forward-backward shift register, a memory address register having inputs connected to said adder circuit and to the output of said shift register, an addressing logic having pairs of outputs connected to the address decoders of said memory state register and said base address status register for transmitting address signals thereto, each pair of outputs being associated with a respective address bit position; means connecting the outputs of said shift register and said memory address register to an input of said addressing logic, and a don't care logic having an input connected to the output of said shift register and an output connected to an input of said addressing logic and arranged to produce don't care address bits for addressing blocks of stages in said memory state register and said base address status register; said indicator circuit including means for producing, at each pair of outputs of said addressing logic: a binary 1 value on a first line of the pair and a binary 0 value on a second line of the pair when the corresponding address bit has a binary 1 value; a binary 0 value on the first line of the pair and a binary 1 value on the second line of the pair when the corresponding address bit has a binary 0 value; and a binary 1 value on both lines of the pair when a don't care address bit is being produced by said don't care logic at the respective address bit position, in order to subdivide a group of contiguous working memory locations into simultaneously addressable blocks and to scan the locations of each block sequentially, from the location having the highest address, in the direction of descending addresses; and a control mechanism connected to said first and second groups of status flip-flops and to said function unit means for setting said status flip-flops, under control of signals from said function unit means and the computer processing unit, in a manner to selectively perform any selected one of: a first operating sequence in response to a corresponding instruction from the computer processing unit, for searching, starting from an arbitrarily selected memory location, both of said state register and status register simultaneously to locate in each of said state register and said status register a group of L contiguous register stages which are all in the opposite binary state, a second operating sequence, in response to a corresponding instruction from the computer processing unit, for setting, to the one binary state, each stage of said base address status register which corresponds to a working memory location containing a base address, a third operating sequence, in response to a corresponding instruction and signals indicating a particular base address and a given group length, for setting to the opposite binary state a number of stages of said memory state register corresponding to such length and starting from the stage corresponding to such base address, and a fourth operation sequence, in response to an instruction generated in said system, for searching both of said state register and said status register for the occurrence of the opposite binary state in a stage of said state register and the occurrence of the one binary state in the corresponding stage of said status register, indicating that the corresponding working memory location contains a base address, and, subsequent to locating such occurrence, setting such status register stage to the opposite binary state.