SU1327113A2 - Apparatus for controlling virtual memory - Google Patents

Abstract

The invention relates to computing, can be used in computers with virtual memory, and allows for an optimal distribution of pages of RAM between active tasks. For this purpose, the virtual control device is included. by memory ev By 955076, a paging exchange control unit was introduced, which, based on the results of the analysis of the number of page failures and the number of successful accesses to the RAM, allows the hardware to redistribute the pages of the RAM between active tasks. 21 il.

Description

 1132

The invention relates to computing and can be used in virtual memory computers.

The purpose of the invention is to expand the functionality by providing a dynamic optimal redistribution of EP pages between active tasks.

Fig. I shows a functional diagram of a device for managing virtual memory; in fig. 2 - block scheme of input registers; on fit, 3 block diagram of the output registers of FIG. 4, the circuit of drivers in fig. 5 is a diagram of comparison blocks; in fig. 6 is a comparator circuit; Fig. 7 is a diagram of a local control unit; in fig. 8 is a page memory block diagram; Fig. 9 is a diagram of the memory element; FIG. 10 is a schematic of the arrangement generator; Fig 1 1 is a diagram of a replacement control block; FIG. 12 is a diagram of a priority node; in fig. 13 is a block diagram of the correction; FIG. 14 is a diagram of a paging control unit; Fig. 15 is a block diagram of determining the number of page faults; in fig. 16 - layout of block arrangements; in fig. 17 is a diagram of the first comparison unit; FIG. 18 is a diagram of the second comparator unit; FIG. 19 is a diagram of the forwarder of the page exchange address; in fig. 20 is a timing diagram of clock pulses.

owls; in fig. 21 - the space of the active task state in the RAM.

The device for managing the virtual memory (FIG. 1) contains a block of I input registers, a block 2 of output registers, a control register 3, a general purpose register 4, blocks 5 of comparison, a block of 6 local controls, blocks of 7 page memories, a spread generator 8 , substitution control unit 9, correction unit 10, paging exchange control unit 11, main memory input 12, mode setting input 3, synchronization input 4, device operation code setting input 15, device 16 inputs of 24-24 local control unit, control input 25 interrupt block 6 local control detecting the outputs 26 - 3 local control unit 6, an additional output 32 of the local control unit 6, input device 33, output 34 An information input unit 1 registers,

Q

5 0 5 o

five

0

five

0

five

32

output 35 of the interrupt signal, informational output 36 of the device.

The page exchange control unit 11 (FIG. 1D) contains the page fault number determination units 37, the first 38 and second 39 placement blocks, the first 40 and second 41 comparison blocks, the first to fourth decoders 42 to 45, the first 46 and second 47 adders, the first to fourth groups of 48 to 51 memory elements, the first to the fourth of groups 52 to 55 of the calculation blocks, the calculation block 56, the group of 57 drivers, the AND-OR 58 element,

The block 37 for determining the number of page faults (FIG. 15) contains the first 59 and second 60 AND elements, the first - third counters 61 - 63, OR element 64,

The first block of comparison 40 (FIG. 17) contains the first 65 and second 66 registers, block 67 of bitwise comparison, switch 68, trigger group 69, delay element 70, AND group 71, And 72 element.

The first 38 and second 39 placement blocks have the same construction (Fig. 16) and contain a group of 73 registers, a group of 74 comparison blocks, a group of 75 And elements, a group of 76 OR elements, a group of 77 rewriting registers, a decipher 78, a switch 79 , a group of 80 memory registers.

The second comparison unit 41 (FIG. 18) contains a memory block 81, a group of 82 memory registers, a group of comparison blocks 83, a group 84 of elements, a group of elements 85 I.

The group shaper 57 (FIG. 19) contains the first 86 and second 87 input registers, bit unit 88: a comparison, the first 89 and the second 90 And elements, the output registers 91 and 92, and OR element 93,

Block I of the input registers (FIG. 2) contains the logical address register 94, the subtractor 95, the group of 96 elements And, the outputs 97-99 of the register 94 of the logical address, the outputs 100-104 of the control register 3,

Page memory unit 7 (FIG. 8) contains groups 105-115 of memory elements, registers 116 and 117, a decoder 118, elements 119 and 134, elements J1I 135-138.

313

Comparison unit 5 (Fig. 5) contains comparator 139, register 1ДО, elements AND А1 and 142.

The generator 8 arrangement (Fig. 0) contains a group of 143 elements EXCLUSIVE OR, the switch 144 and the decoder 145.

Replacement control unit 9 (FIG. P) contains OR elements 146, a decoder 147, switches 148, and a priority node 149.

Correction block 10 (Fig. 13) contains a decoder 1 50, elements AND 151 - 154 and elements OR 155.

Block 2 of the output registers (Fig. 3) contains the register 156 of the physical address, the register 157 of the replaced page, the register of flags 158, switches 159. and 160, drivers 161 and 162, and OR element 163,

The memory element of the groups 105-115 of the page memory unit 7 (FIG. 9) contains the address decoder 164, the information register 165, the AND group 166, and the switch 167.

The comparator 139 (FIG. 6) contains an element WL-NOT 168 and in each bit an element EXCLUSIVE OR 169.

The priority node 149 (FIG. 12) of the replacement control block 9 contains AND elements 170 and OR elements 171.

The formers 161 and 162 (FIG. 4) contain the elements OR 172 (it is assumed that the device contains two memory blocks of pages),

The local control unit 6 (Fig. 7) contains the second - the seventh 173 - 178, the thirteenth - the fifteenth 179 - 181, the eighth - the twelfth 182 - 186 and the first 187 elements And the sixth 188, the fifth 189, the first - the fourth 190 - 193 OR elements and triggers 194 and 195.

The device for managing the virtual memory works as follows.

The modes of operation of the device are determined by the control device of the processor driving the corresponding input of the local control unit 6.

During the operation associated with addressing the AS, the processor control unit excites input 17 of block 6. If the word bit of the program's interface, which determines the address translation mode, is not set, then, during the pulse CO, the element 81, signal with

13

the output of which through the OR element 189 writes to the register 156 of the physical address, which enters the input of the register I56 through the switch 159 of the block 2 output registers. If the processor is operating in the address translation mode, the corresponding bit of the program status word is set and the specified information is loaded into the control register 3, the information about the number of pages minimum required for the execution of each active task, as well as the information about the task length is transferred to pages, determined by the value of the REGION parameter of the EXEC operator. During the operation associated with accessing the main memory, the control device initiates the input 17 of the local control unit 6 and Then, during the operation of the pulse CO, the element 185 is opened, according to the signal from output 27. which logical address is recorded in the register 94 of the logical address of block 1 of the input registers. In block 1, the virtual page address is formed in the same way as in the prototype device. The bits of the virtual page address, except for the offset, are fed to the inputs of a group of 143 elements EXCLUSIVE OR generator 8 of the arrangement, the result of which through the commutator 144 enters the address inputs of groups 105-115 memory elements of each of the 7 page memory blocks. The information i read from the selected cell of groups 105-107, 113 and 1I5 of the memory elements is fed to the corresponding comparison unit 5. At the same time, information from the selected cell of groups 105–107 of memory elements of each of blocks 7 is fed to the corresponding inputs of block 40 comparing the input addresses of block 11 of the page exchange control. In block 40, the number of pages of RAM is determined from information from group 105–107 of memory elements ti

related to each active task. The conditions for deleting pages from RAM, formed by elements AND 121 -125 of block 7, and the corresponding information from groups 108, 110 - 113 of memory elements are written to registers 116 and 117, respectively, by a signal from the output 30 of local control 6, coming through 5

cut open element And 179 during the action of the pulse C1. Block 5 compares the addresses of virtual pages coming from blocks 1 of the input registers and blocks 7 of the page memories.

If a comparison has occurred | The selected row of groups 105-115 of the memory elements is loaded and this page is not used in I / O operations, this indicates that the required virtual page is in the main memory and is accessible. This situation is stored in the registers 140 of each of the blocks 5 according to the signals received from the output 29 of the open element AND 179 during the action of the pulse C1, and characterizes the successful access to the main memory page. This information from the output of the switch 76 of block 5 is fed to the first input of the corresponding block 37 for determining the number of page faults. The signals from the outputs of the AND elements 141 arrive at block 2 at the element OR 163j by means of which it is determined whether the required page is found in the operational memory and whether it is allowed to be accessed. This situation is remembered in trigger 194 during the action of pulse C1 on a signal received at the trigger input of trigger 194 through an open element 79.

If a comparison has occurred, selected on the row of groups 05-115 memory elements loaded, but this page is used in I / O operations, this indicates that the required virtual page is in RAM, but is not available for access side of the processor. This situation is remembered in trigger 195 (single state) during the action of pulse C1 by a signal received at the trigger input of trigger 195 through an open element AND 79. This condition is formed by elements AND blocks 5 and element and 190 block 6.

If using the OR element 63 it is established that access to the virtual page is possible (single state of flip-flop 194, then its generated physical address is recorded in physical address register 156 by the output from the 28 output of local control 6, which is fed to the control input of physical register 156 -6

Whose address through the element of the NII 184 and the open element And 180 during the pulse C1, the Physical address is fed to the input of the register 155 through the switch 159. The physical address is formed as a combination of the number of the unit 5 of the comparison, where the virtual address has been recognized, the code coming from the output of the com1 The luminator 144 of the generator 8 arrangement, and the offset coming from the output 99 of the register 94 of the logical address. Binary code of block number 5. The comparison is formed by the shaper 161. After that, the paging table is corrected, which involves setting the reference bits and change bits, if the RAM was accessed to record information. For this, during the operation of the pulse C2, the element AND 178 is opened, the signal from the output 30 of which goes to the element 132 of each of the blocks of the 7 page memories. The contents of the registers 140 of the comparison units 5 are fed to the second inputs of the And elements i 32 of the respective blocks of the 7 page memories, since the recognition of the virtual address is possible only in one of the 5 blocks of the comparison, And the elements 119, 120, 132 and 134 of the corresponding block of the memory 7 are opened pages. Elements 119 and 120 determine the installation of information at the inputs of groups 108 and 109 of memory elements of the corresponding page memory block 7, and open element 132 allows the recording signal to pass to the control inputs of groups 100 and 109 of memory elements. Writing to the memory elements group 109 is performed only when the trigger code sets the operation defining the recording of information E to the operational memory. In this case, the AND 134 element is open.

After forming the conditions for determining a free or possibly replaced page, they are analyzed by the substitution control unit 9. The formed address of the possibly replaced page and the method of its replacement are placed into the register 157 of the replaced page and into the register of 158 flags, respectively, according to the signals from the output 28 of the And 182 element during the action of the C2 impulse

If the triggers 194 and 195 are S state zeroes, then it determines that the desired virtual page

713

not in RAM, which corresponds to a page fault. This information, through element 186, goes to the second input of the corresponding block 37 for determining the number of page faults. If, although Sy in two blocks 37, the number of successful accesses to RAM or the number of page faults D reach their critical values K or, which are selected taking into account the specific characteristics of the flow of problems solved in this computing system, or can be obtained as a result of simulation modeling computational process, then the information about this from the first outputs of the corresponding blocks 37 through the element H-OR 58 goes to the additional input 25 of block 6 and opens the element And 187, the signal from the output 26 of block 6 calls There is an interruption, which determines that it is necessary to redistribute pages of RAM between active tasks. After processing these interruptions, the operating system transmits to the paging exchange control unit-che; the input registers for each task involved in the paging exchange are minimal; the allowable number of pages of RAM required to solve each task, and the length of the problem in the pages of RAM. In block 1, pairs of tasks that are simultaneously in the RAM, for example the task with the largest excess number of pages, are put in Compliance is the task that requires the most pages of RAM to complete successfully. In block P, the number of pages that will participate in the exchange is determined, and the addresses of the exchange are formed in the group of blocks 57, which from the output of block 11 arrive at the input of the decoder 150 of the correction block 10, which analyzes the addresses of the tasks participating in the exchange and the conditions of the exchange . As a result of such an analysis, the signal of the decoder 150 is used to change the number of the task in the group of 106 memory elements of blocks 7 by transferring to the group 106 of blocks 7 of the memory pages of the giving tasks, the numbers of the taking tasks. Under the action of the pulse C1, the element And 173 6 is unlocked, the signal from the output 30 of which and the signal from the output

ten

15

20

25

thirty

35

40

45

50

55

men- |, -e OR 188 open: element1; nt AND 126 of that block 7, which is selected by generator 8 decoder 145. The signal from the output of the open element AND 126 enters the control inputs of the group of 106 memory elements, allowing the recording The new number of the active task, which participates in page exchange, from the output of the decoder 150 of the correction block 10. After completing the cycle of paging between tasks that are simultaneously in RAM, the device continues to work in the mode of dynamic address translation until the values or D "p at least for two active tasks are reached again. When accessing the external memory, the correction unit 10 analyzes the condition formed by the decoder 147, which determines whether it is possible to replace or input the required page. If possible, an I / O wait bit is set in the corresponding row of the page table. For this, the signal from the output of the open element AND 154 of the correction unit 10 is supplied to the elements 130 of each of the blocks of the 7 page memories. In the page memory unit 7 selected by the priority node 149, the AND 130 element is opened in the presence of CHI from the output 30 of the AND 177 block of the local control unit-6, and during the action of the C2 pulse, the memory elements are written to the group 113. Information at the input of a group of I13 memory elements of each of the page memory units 7 is established from the output of the OR element 155 of the correction unit 10.

If, when analyzing the conditions by the correction block 10, it is determined that it is not possible to enter the desired page, then the input-output wait bit indicator of the page table is not marked,

If the required virtual page is not in the RAM, then during the action of the pulse C2, the element AND 183 ,, opens a signal from the output 26 of which causes an interruption, indicating that the required virtual page is not in the RAM.

If trigger 194 is in the zero state, and trigger 195 is in the single state, this means that the required virtual page is in the RAM, but uses .9132

with I / O system. Therefore, no row of the page table is marked, since the signal from the output of the trigger 195 closes the element AND 177 and at the time of the action of the impulse C2 opens the element AND 184, which causes an interrupt, indicating that the processor is allowed to access the page used by the system I / O,

When executing I / O operations, it is necessary to set the I / O wait bit in the page table for real physical pages of the operative p; 1 m tee, to which the Topbfri is accessed during these operations. Upon completion of the I / O operation, the I / O wait bit is reset.

To perform such actions, the processor lowers the register 4 of general purpose1 and sets the address of the real physical page, the corresponding most significant bit — the code defining the setting or clearing of the I / O wait bit, and the processor control device excites input 18 of block 6 local government Thus, the younger part of the physical address of the page from the output of general register 4 through the switch 144 of the generator 8 of the arrangement arrives at the address input of groups 105-115 of memory elements of each of the blocks of page memory 7. The older part of the physical address of the page is decrypted by the decoder 145 of the generator 8 arrangement, which allows you to select one of the blocks of 7 page memories, i.e. the corresponding part of the page table. The set or reset code for the I / O wait bit is input to a group of 113 memory elements of each of the 7 page memory blocks via the OR 155 and I 151 elements. At the time of the C1 pulse, the AND element opens, the output signal of which opens 30 the AND 129 element of that block of page memory 7, which is selected by the decoder 145 of the generator 8 arrangement. The signal from the output of an open element AND 129 through the element OR 36 is fed to the control input of a group of 113 memory elements, causing a recording, of information arriving at the input of the elec

0

11310

cops 115 of memory, with gpkhodl Sh1I 155 element of the correction unit 10.

When initially loading a physical page with a memory memory, onepaTj BHon memory must be set or reset (forbidden pointer) 1n to delete pages and the row pointer of the page table. To accomplish such actions, the processor sets in the lower bits of general register 4 the address of the real physical page, in the corresponding higher bits - the bits that determine the validity of the row of the page table, and the code that determines the prohibition of deleting pages from RAM. and the processor control unit drives the input 19 of the local control unit 6.

Thus, the younger part of the physical address of the page from the output of general register 4 through the commutator 144 of the generator 8 of the arrangement goes to the address inputs of groups 105-115 memory elements of each of the blocks 7 of the page memories. The older part of the physical address is decrypted by the descriptor 145 of the arrangement 8 generator, which allows you to select one of the blocks 7 of these pages, i.e. The corresponding part of the page table. The installation codes of the pointer bits to prohibit deletion and the validity of the row of the page table are fed to the inputs of the groups 114 and the memory elements of each of the page memory blocks 7 through the And elements 152 and 153 of the correction block 10. At the moment of action of the pulse C1, the element 175 opens and, through the element S1I 188, the signal from the output 28 of the element OR 188 opens the element 28 of that block 7 of the page memory, which is selected by the decoder 145 of the generator 8. The signal from the output of the open element AND 128, which arrives at the control inputs of the groups 114 and 115 of the memory elements, causes the recording of information arriving at the inputs of the groups 114 and 15 of the memory elements from the output of the elements 152 and 153 of the correction unit Yu.

5 When the virtual page is initially loaded, the information about this page is written into the corresponding row of the page table. With this, mouth5

0

five

0

1113

The processor control function excites input 20 of block 6. Since the page is inserted into the RAM, only if it is accessed, the physical address of the RAM, where the virtual page will be loaded, is in the register 157 of the page being replaced. The processor places the address of the physical page from the corresponding bits of the register 157 of the replaced page into the lower bits of general register 4, in the corresponding high bits of which the information about the prohibition of deleting the page from the main memory and the validity of the page table row is placed. The virtual page address is located in the register 94 of the logical address of the block 1 of the input registers, where it is recorded from the signals from the output 27 of the block 6 of the local control through the open element 185.

Thus, the younger part of the physical address from the outputs of general register 4 through the switch 144 of the generator 8 of the arrangement arrives at the address input of the groups 105 115 of the memory elements of each of the blocks of the 7 page memories. The older part of the physical address is decrypted by the decoder generator 145 of the 8 arrangement, which allows you to choose one of

blocks of 7 pages of memory, i.e. soot

the corresponding part of the page table. At the time of the pulse C1, the element AND 173 of block 6 opens, the signal from output 30 of which and the signal from the output of element OR 188 open the elements AND 126 - 128, 128 and 131 of that block 7 of page memory, which is selected by the decoder 145 generator 8 arrangement. The signals from the outputs of open elements I 126 - 128, 131 and 133 are fed to the control inputs of groups 105 - 112, 114 and 115 of memory elements, causing the recording of information entering the inputs of groups 105 P 2, P4 and 115 elements. The number of the virtual page from the output of the block 1 of the input registers is set at the inputs of groups 105-107 memory elements. A logical zero is set at the inputs of the groups 108 and 109 of the memory elements, since the elements of the groups 119 and 120 are closed. At the inputs of the group of 110 memory elements, the decoder 11 8 is set to the value

g

5 o

five

Q g

3 2

the logical unit is 51, and the inputs of the groups 111 and 112 of the memory elements are the logical zero value (the loading page is included in many of the most frequently used pages. The information on the inputs of the groups 114 and 11 5 memory elements is determined by the contents of the corresponding high-order bits 4 of the general purpose This information through the elements 152 and I53 of the correction unit 10 is fed to the inputs of the groups 114 and 115 of the memory elements.

The mathematical justification for the optimal page exchange in the OP between the active tasks is as follows.

The space of the task state (Fig. 21) in the RAM can be characterized by the following parameters:

L- is the number of pages required to solve the i-th problem, the length of the problem in pages (determined by the REGION parameter in the EXEC statement);

D is the number of current failures;

N and - the number of different pages of the i-th task, which was addressed during the accumulation of D failures;

X; - the number of OP pages allocated for the i-th task at the time D of failures;

.L. - the minimum required number of pages for solving the i-th task;

Cd - the number of successful hits to the pages of the i-th task.

. The algorithm of optimal control of page exchange in the OP between active tasks.

When the i-th problem D is reached during the process of solving, the failures or successful calls to the PD (and are constant coefficients for all active tasks), the coefficients for this task are calculated:

(one)

l Njrs

BUT . ----- X,

, n dt d. -f-,

Li

and

"BUT

(2)

1Л1

 WG-th /

where N is the total number of active tasks. Then the total number of active tasks in the OP is divided into two subsets: a subset of tasks with an excess of OP pages — giving I. and a subset of tasks with a lack of OP pages — taking 1 by checking the conditions:

15- (3)

ij. {i / r. l, pV

(four)

 1313

The giving subset according to A. is ordered by arranging the elements I ,. from D. to A;

about . m "x ("

For the elements of the taker subset Ij, the coefficients Aj are determined. , and elements 1 are arranged

from J to / 1G. Next, produce

 sss I min;

redistribution of OD pages between

active tasks, taking into account the fact that the task with min A j can give the maximum number of pages, and the task with check L; can receive the maximum number of pages OP:

K-min L.-X. , X.-Ljj, i € ly, jelj. (five)

In this case, the exchange between the i-th and j-th tasks is performed in such a way as to fully satisfy the i-th task, if

L. -X, Xj -L °.

(6)

or completely free the jth task from the redundant pages of the OP, if

L. - X. 7 / X. - L ° .. (7)

At the same time, for A j, it is impossible to satisfy problems from set 1 by means of tasks from set 1n. This condition can also serve as a basis for choosing the values of K p and D p.

The paging control unit 11 (FIG. 2-) operates as follows.

When the virtual memory page is initially loaded, information about this page is recorded in the corresponding row of the page table in groups 105 - P5 of the memory elements of block 7. At the same time, from groups 105 - 107 information elements: virtual machine number and virtual memory number (group of elements 105 ); task number (element group 106); the segment number and the page number (group of elements 107) are fed to block 40 comparing the input page addresses. In block 40, the addresses recorded in groups of 105-107 elements are compared, and it is determined how many pages of RAM - X | refers to every task that has been submitted. This information from block 40 enters the first or nth memory block, and the first block of each group receives information about the first task, the second about the second, and so on. Number of blocks na

Q

20

35

25

zo

Q g j-n 3U

The mi corresponds to the number of pages of RAM. To the other input of the memory blocks of group 48 through the decoder 42 comes from a group of 109 elements of block 7 the number of references to the pages of this task is N, the first output of each BL: the memory of group 48 is connected to the input of the adder 46, in which the total number of tasks is calculated at the same time in memory, according to the number of memory blocks of group 48, which received information. The second and third outputs of the said memory blocks 48 are connected to the inputs of the computing blocks y1j of the group 52, the outputs of which are connected to the inputs of the spreading unit 38 and to the inputs of the adder 47, in which the calculation of Z A - is performed.

1-1

In block 38 of the installation, the maximum coefficient is determined and the subsequent L TO (";" at the same time, the A input

| T1C (X

, and on the last - A; , from the outputs of adders 46 and 47, information is fed to the inputs of block 56, in which the average value of D is calculated by the formula N

l:. l :.

55

D:

f N The output of block 56 is connected to the first input of block 41 of comparison with ip., the remaining inputs of which receive the values of the coefficients from D to

that

D. From the OUTPUTS of the arrangement block 38, in this case, it enters the second input of the block 41, the third, etc., the last input of the block 41 enters 1, from the last

R | eleven

output of block 38. In block 41, the comparison with set i is divided into two subsets: a subset of tasks with an excess of pages of RAM (1a 1 f a subset of tasks that lack pages, RAM (I, CD). The numbers of tasks from the set la The first group of inputs of the decoder 44 is received, the second group of inputs is received from block 1 of the input registers of LJ values for all active tasks, the third group of inputs of the decoder 44 receives the values of X from blocks 48 of the group memory, while the output of the decoder 44 passes t zn tim X, and L, corresponding to so ,, that the first pair of

1513

the inputs of the decoder are X, and L, corresponding to / 1 of the many H «1

The first pair of outputs of the decoder 44 is connected to the inputs of the first memory block 50 of the group, into which the values of X are written. And L corresponding to task c, d, out of 1, and the last group of outputs of the decoder 44 to the last memory block of group 50, in which the values X, L °, corresponding to A, are recorded. of 1 „, VYSH1 O3

the moves of the memory blocks of the group 50 are connected to the inputs of the blocks of the calculation 54 of the group, in which for each task from set 1 the calculation of the expression X -Lj, j I a is performed, and this result with the number of the task to which it belongs is transmitted from the output of the corresponding memory block: group 54 to the first input of the corresponding shaper of the page exchange address of group 57. Task numbers from the set Ij are sent to the first group of inputs of the decoder 43, to the second group of inputs which of block 1 receives the values L., to the third group - signals from the output s Bloch Cove 37 for determining the current number of operational failures of pages of memory. The decoder 43 skips the values of d. , Lj for each task from the set Ig to the inputs of the corresponding memory blocks of group 49, the outputs of which are connected to the inputs of the corresponding blocks of group 53, in which the calculation is performed using the formula D

 ---- for each task from the set

va If. Values of A, from the outputs, respectively

block 53 of the group arrive at the inputs of the block 39 of the arrangement, which functions the same as. block 38 arrangement. At the first output of block 39, a task number is formed, for which, the last is a task number for which min. The given numbers go to the first group of inputs of the decoder 43, the second group of inputs of which receive the values L. from block 1, the third - the values X. from memory blocks of group 48. The first pair of outputs of the decoder 45 receives the values X., L ,, corresponding to the task from the set Ig, for which

the last pair of decoder 45 passes3

sixteen

There are values X, L of the task from the set T, for which D J. The first pair of outputs of the decoder 45 is connected to the input of the first memory block of group 51, into which the values X., L. are received for task X e 1, which has no (f etc., the last pair of outputs is connected to the inputs of the last memory block groups 51, in which X, L values are written, for task I-, in which. The memory blocks of group 51 are connected to the inputs of the corresponding calculation blocks of group 55, in which the K values for each task from the set Ig are calculated, the results of calculations from the outputs of the blocks of group 55 are fed to the second inputs of the forms The address exchange groups of the page exchange group 57 whose outputs are connected to the first group of inputs of the decoder 150 of the correction block 10. At the input of each shaper of the group 57 address, a page exchange address is formed that includes the number of the task, the giving page Njj, the number of the task taking the page Nj and the number of pages participating in the exchange. Kg or Co. The formed addresses are sent to the first group of inputs of the decoder 150 of block 10, the second group of inputs of which from block 116 receives the addresses of the pages that are least used and ezhaschih tasks between which paging is performed. The page exchange between active tasks actually consists in replacing in block group 106 of memory block 7 the number of the task giving pages to the number of the task taking the page, and the number of pages in which the numbers of the tasks will be changed is determined in the corresponding driver 57 group address from expression

.-X-, X.-Lj, iel5, jel.

A task from the set Ig, in which mof takes the maximum number of pages, a task from the set In, in which. , gives the maximum number of pages. For such pairs of tasks, the quantities that characterize them are X, L. (icij), X, L (jelj) are passed through the corresponding calculation blocks of group 54, in which the values of K X -, - L J are determined, to the inputs of one

i7

grouper 57, and it is precisely between such tasks that the page exchange is performed in such a way that for the giving task is completely freed from redundant pages, or taking the task fully satisfies the missing pages the page exchange control unit 11 begins to function if even for two tasks are achieved values or K, which are forkyrugots about information received at the inputs of blocks 37 determining the number of page faults from the output of comparator 139 5 of block 5 and the output of trigger i 94 of block 6. Reach signals The Kp or p from the second inputs of block 37 is placed at the inputs of the AND-OR element 58, from the output of which a signal is fed to the 2o additional input 25 of block 6, an interrupt is generated, which arrives at the output 26 of block 6 and is processed in the operating system. During the processing of this interrupt 25, according to the signals from the operating system, block 11. Realizes the redistribution of pages of the main memory between active tasks. The block 37 for determining the number of pages Q q of faults (FIG 15) includes an element AND 59, an element 60 AND with a first inverse input, the inputs of which receive signals from the outputs of comparator 139 of block 5 and trigger 194 of block 6. If the page being accessed is in the RAM, then both signals are present at the input of the And 59 element, which indicates successful access to the RAM. The impulse from the output of the element 59 is fed to the input of the counter 61 successful calls K, whose other input is previously fed the code number K | , which is initially installed in the counter 61, If the signal from the trigger output 194 is not received, this indicates the absence of the required page in the RAM and a page failure occurs - access to the external memory. In this case, the signal does not arrive at the first inverse input of the AND element 60, and the second input receives a signal from the output of the comparator 39 of block 5, the impulse from the output of the elements I 60, indicating a page fault, is fed to the input of the counter 62, in which

40

50

. „55

Chd 5 2 25 Q 35

40

50

1318

The code of the number is set, and simultaneously at input 63, in which the current number of page faults Dy is calculated. At overflow (dostizhenki D or K., p) of one of the counters 6i or 62, the overflow pulse from the output of the OR 64 element is fed to the additional input 25 of block 6 and simultaneously with this pulse the counter 63 reads to the second group inputs of the decoder 43, as well as resetting the counters 61 and 62.

The input address comparison unit 40 (fkg. 17) operates as follows.

Memory register 65 receives information from the first page from the memory elements of groups 105-107 of block 7 and is stored in it. The information from the subsequent pages comes through element 71 And, the inverse input of which is connected to the zero output of the first trigger of group 69, all other page addresses are received through the corresponding elements AND of group 71 in block 67, which compares the contents of the memory elements of groups 105 -107 ka; kda of the next page with information stored in register 65. The output of block 67 of one-by-one comparison is connected to the input of register 66 of memory of the number of pages relating to the i-th task, in this case to that number Ora at this moment is stored in register 65. After the comparison with the last page code in register 65 by the signal received on the first input of the last element of group 71 and 70 through the delay line the number of pages read is performed operational memory; related to this task., which goes to the input of the switch 68 and the latter sends the number of pages of the first taskJ obtained as a result of comparing the first page address with all addresses to the input of the first memory block of group 48, the result of each comparison is the case of address matching gives a pulse the output of block 67 which sug is modeled in block

and also serves for

CH 5 2 25 Q 55

setting the triggered trigger of group 69 from one state to zero and thus locking the corresponding AND element of group 71, which makes it possible to exclude the compared page address from the general 19, 327113 20

of the number of pages arriving for elements D. until all

comparisons with other addresses on entry will not be recorded descending in

block 40 comparison. The procedure for executing the output registers of the group 80. until it is pro- , Block 41 Comparison with A (Fig. 1 8)

All addresses are compared. works as follows.

Blocks 38 and 39 of the arrangement (Fig. 16) The first input register 81 will be operated as follows. Blocked calculated A values from the output in calculating block 56 are calculated, output values from input groups 52 or 53 are received from the input-rap group 82 registers of group 73 with their no-L „to L ,. according to the outputs of the tasks. In the first part of the yearly block 38 of the arrangement, the output of the register stores the value D, and in the register 81 L .r enters the first second — the number of the corresponding task-input of all units of a bit comparison. The value of D., recorded in the first section of group 83, on the second inputs to the input to the register of group 73, the incoming values are from D D to the first input of the first block of / (T1l outputs of the registers of group 82, bit comparison group 74, for the first time the outputs of the blocks of the second second input of which are supplied And j compared to the group 83 are connected to the output of the second register of the group 73; the corresponding elements And if the first value is greater than the second, group 84, the second inputs of which then the pulse appears on the first you are connected the second outputs are corresponding during the comparison block of group 74, into the second register of group 82, which is otherwise on the second. The first is the task number corresponding to the output of the first comparison block grouped. The second output of the block 74 is connected to the first input of the group 83 is connected to the input of the element I of group 75, and the second, the corresponding element AND of the group, the input of the second, element I of group 75, py 85, to the second input of which also the second and third inputs of the first evil element are given the task number, which ment and group 75 are connected to the second Q corresponds to / 1; compared to the block and third outputs of the first register. Comparison of group 83 with Asr "All non-groups 73 from which they receive the store of tasks for which / l. ° The values of D and numbers in it are from the outputs of the corresponding task. Similar information of the post 85 of the group 85 to the first group goes to the inputs of the second element AND inputs of the decryptor 43, and all the numbers 75 from the outputs of the second registrar task for which Dc / through group 73. After comparison, the large corresponding elements And group 84 have the value A. with its number through the input to the first group of inputs, the corresponding element AND of the group 75 of the encoder 44. Thus, the first register of group 77, the contents of the whole set of active tasks, is divided into block OR element 76 of the group 76. and which compares the same set-giving and I with berupschh with AD value stored in the tre-1 task.

The input register of group 7i. Ta-Formers of the address of the exchange of rapid comparison are made before the group 57 (Fig. 19) work blind, until it finds the maximum-blowing way.

element f, which is from the output In the first input register 86 of the last register of the group 77, the number of pages K «given by

the corresponding elements of the groups of the 75i-th task and calculated in the corresponding 76 are fed to the input of the switch 79, the unit of the group 54 according to the formula

which sends the first A j ,, to the per-K Xj-LJ, j e Ij, and the number of the task

The left output memory register of the group of the 80.browser page. In the second entrance

The number of found maximum register 87 comes the number of pages

The copier enters ad-Kg decryptor 78, received by the jth task and computed, the signal from the output of which zeroed out in the corresponding block calculates the corresponding input register of group 55 using the formula Kg L. of group 73, in which initially sJElg, and the number tasks.

entered, then the procedure on-C outputs of registers 86 and 87 values

for the remaining Kg and K are received on the first and second

21132711

the moves of block 88 are comparable. If K, j Kg, then a signal appears at the first output of the block 88, if g K ,, then the signal appears at the second output of the comparator block 88, the first output of which is connected to the input of the element And 89, to the other inputs of which

The number of the task is given, the page is given, Nj is the number of the task that takes the page, N, r and the value K, the second output of the comparison block 88 is connected to the first input of the element I 90, to the others

the inputs of which are supplied from the outputs of registers 86 and 87 Nj, N 36 and Kg, the outputs g of elements AND 89 and 90 are connected respectively to the inputs of memory registers 91 and 92, the outputs of which are connected to the corresponding inputs of the element OR 93, the output of which is connected to one of the inputs of the first group of inputs of the DESIGNER 150 of the block 10,., If Ka is greater than Kg, then the exchange is carried out in such a way that the task, taking the page, is completely 25 satisfied. In this case, a pulse appears at the first output of the comparator 88, which registers the exchange address in the register 9i through the element 89 and the form, K, If kf KQ, THEN the high potential appears at the second output of the comparator 88, and register 92 through the element And 90 writes the address of the page exchange in the form of N. NjjK-, real-. a variant, when a task giving pages is completely free from them,

Block 1 of the input registers (Fig. 2) is designed to form a complete virtual address, works in the same way as the similar block in the prototype device, and additionally outputs 103 and 04 of the control register 3 for the switchboard from the operating room are entered into it. a system of L. values (the length of the i-th task in the pages of the RAM), and L, (the minimum number of pages for the i-th task).

Blocks 7 of page memories (Fig. 8) are designed to store a page table and provide the possibility of its modification, each of blocks 7 contains part of this table. All memory blocks contain a full page table, the number of lines of which is equal to the number of pages that can be arranged in RAM. The row of the page table describes the single

40

45

50

55

five

about

five

0

five

0

five

322

memory page. Blocks 7 operate in the same way as the corresponding blocks in the prototype device. In the row of the page table, a group of 106 memory elements is additionally introduced, in which task numbers are stored that determine the perfomance of this memory page for a specific active task.

Element 106 (FIG. 9) contains descis1) rytor 164, information register 165, group 166 of memory elements, switch 167 and works in the same way as groups of memory elements of the row of the page table in the device-prototype. In block 7 is entered an auxiliary input, which is the information input of the memory element of group 106, connected to one of the outputs of the first group of outputs (a decoder) and S 50 of the correction unit 10, for overwriting the numbers of active tasks. In addition, additional outputs have been introduced from the memory elements of the 105-107 groups connected to the third input of the page exchange control unit P, which are used to transmit the address of the virtual machine and the virtual unit. The data from element 105, the address of the active task number to which the operational memory page belongs, from elements of group 106, addresses of segment number and page number of elements of group 107, all the listed information is fed to the input of unit 40 for comparing input addresses.

Comparison unit 5 (FIG. 5) is designed to compare virtual addresses of pages post-entry from block 1 of input registers with virtual page numbers stored in the corresponding blocks of page memory 7, and works in the same way as the corresponding block in device prototype, it additionally has a compiler 139 input connected to the first input of block 11,

Correction block 10 (FIG. 13) is intended for storing information in the memory elements of groups 106, 113-115 of each block 7 and works in the same way as the corresponding block in device-prototype j, the address decoder 150 is additionally inserted, the first group of inputs of which connected to the second output of block 11, and the second group of inputs receives information about page removal conditions and frequency

using them from register 116, the outputs of the decoder 150 are connected to the corresponding inputs of elements of the group 106 of the numbers of tasks.

The local control unit 6 (FIG. 7 is designed to generate control signals and operates in the same way as the corresponding block in the prototype device; the element 187 is additionally inserted in it, the first direct input of which is the additional input 25 of block 6 The second input of which is input 17 of block 6, the third input of which is input 22 of block 6, and the element 186 to the first input of which the output of the trigger 195 is connected, and the second of the output of the trigger 194, the output of the element 186 is additional output 32 of block 6.

The arrangement generator 8 (FIG. 10), the replacement control block 9 (FIG. 11), the output registers block 2 (FIG. 3), the drivers 161 and 162 (FIG. 4) are made in the same way as the corresponding blocks in the prototype device , and perform the same functions

Thus, when inserting a page into RAM, the device for managing virtual memory implements the following algorithm: with the I / O wait bit set, the address of the required page is entered, the required virtual page is entered, and then the I / O wait bit is cleared

When replacing the RAM page, the proposed device implements the following algorithm: when the I / O wait bit is set, the virtual page is removed from the required physical page of the RAM, the address of the input virtual page is set, and then the I / O bit is reset.

After a certain period of time under the control of the operating system, the bits of the page frequency are adjusted. During one cycle of the procedure, the frequency of use of pages is corrected simultaneously in the corresponding rows of each part of the page table in each block of 7 page memories.

Upon reaching a critical number of failures or successful access to the RAM, control unit 1I

-SQ g o

25

gQ

. ,,

about gg

35

45

324

page exchange via block 6, the local control generates an interrupt that is processed in the operating system, while in block 11 addresses of the tasks involved in the exchange of pages are formed. The generated addresses from the outputs of the corresponding shapers of the address of the group 57 are sent to the first group of inputs of the decipher 150 of the block 10, to another group of inputs of which information about the page removal conditions and their frequency of use from the register 116 comes. the memory elements of group 106 of block 7, change in them the numbers of the tasks to which the respective pages belong, simultaneously the counter 61 of page faults and the counter 62 of successive recourses to the main memory are reset. After the end of one cycle of optimal redistribution of pages of RAM between active tasks, the device continues to work in the mode of dynamic translation and address translation until the critical values of the number of page faults or successful access to the RAM memory are reached again.

Thus, the proposed device for managing virtual memory implements the process of address conversion using hardware, as well as a constant record of the number of successful hits and the number of page failures when accessing the memory pages belonging to each active task, and for this purpose information optimally redistributes memory pages between active tasks, which makes it possible in general to reduce the number of country exchanges with external memory and significantly improve the performance of to computational systems.

Claims (1)

Invention Formula A device for managing virtual memory by author. St. No. 955076, characterized in that, with the aim of expanding the functionality due to the optimal redistribution of the pages of RAM between active tasks, a paging control unit is introduced into it, with the information output .25132 the input registers block is connected to the input of the number of pages; y1 solving the active task of the page exchange control block, whose information output is connected to the input of the page exchange addresses of the correction block, the equality signs of the comparison block are connected to the fault exchange control block , fifth manager The latest output of the local control unit is connected to the polling input of the presence of failures of the page exchange control unitJThe output sign of the presence of faults is connected to the interrupt control input of the local control unit, the second information outputs of the page storage units are connected tr FIG. 2 From t K2 Omiz OmIZ Om13 From 28 oI f -.R AJ5 From 12 0m27 OTYUZ OYU7 about about Y uY. OTB 1o / G60 f57 From lit tpU6,3 and 2ji | K | ., X, h    f f LLL r ySyww Л 1 1 л1л1г  I G SH 1 r 172 I Iyy I FVUF 0tfe. four " ZTSh Wholesale Omts 2S fi.9 From t fib.p Fie.n Otsh 151 8gsg about G53 fpus. f3 ut. OS / 7/77 W From t 53 BO Fib, 15 From wit Sj sit (25 S3 From W5-W7 o Fig.17 /, PP - p , one (/ ". / I  j HSSS S3 Kfff fie. nineteen f (/ y. 20 0ui.ir Editor L. Veselovska Compiled by A.Mishin Tehred I.Popovich Order 3391/46 Circulation 672Signature VNIIPI USSR State Committee for inventions and discoveries I13035, Moscow, Zh-35, Raushsk nab., 4/5 Production and printing company, Uzhgorod, st. Project, 4 Proofreader L. Pilipenko