RU2186420C1 - Device for servicing equal-priority requests of computing system subscribers - Google Patents

Abstract

FIELD: computer engineering; data exchange systems. SUBSTANCE: device has N subscriber s blocks, clock generator, two N-input NOR gates, two priority coders, OR gate, NAND gate, and selector-multiplexer. EFFECT: enhanced speed and reliability of device. 2 cl, 5 dwg

Description

 The claimed technical solution relates to the field of computer technology and can be applied in data exchange systems.

 Known service request devices. Maintenance - a set of actions of a computing system, including fetching a request from the queue, allocating a resource to it, as well as conducting final operations. Request - sending a signal initiating a response. An input message containing a system requirement for a resource allocation. - see, for example, ed. USSR 1441398 "Multichannel device of dynamic priority" IPC G 06 F 9/46, published 11/30/88, Bull. 44; author St. USSR 1562912 "Multichannel device with dynamic priority change" IPC G 06 F 9/46, published 07.05.90, Bull. 17, Aut. USSR 1522206 "Dynamic priority device", G 06 F 9/46, published 11/15/89, Bull. 42.

 Known counterparts contain priority analysis blocks. Priority - a number assigned to a task, process, or operation that determines the order in which they are performed or serviced. The smaller the number, the higher the priority level, and priority building blocks. A common disadvantage of analogues is the low probability of timely service of requests of lower priority.

 Of the known closest analogue (prototype) in its technical essence of the claimed device is a device (first option), see author. St. RF 2140666 "A method for servicing user requests of a computing system and a device implementing it" IPC G 06 F 9/46, published October 27, 1999, Bull. thirty.

The prototype device includes N subscriber units, where N≥2, counter, AND element, clock, divider, N-input OR-NOT element, multiplexer, inverter. In this case, the counting input of the counter is connected to the output of the And element, and the second input of the And element is connected to the output of the clock generator and the input of the divider. The output of the divider is connected to the clock inputs of N subscriber units. Query inputs and K-bit inputs, where K≥2 is the capacity of the code for the maximum waiting time for service requests, the “Maximum waiting time code” N subscriber units are the corresponding request inputs and the K-bit inputs “Maximum waiting time code” for the device, N inputs N the input element OR is NOT connected to the “Exceed” outputs of the corresponding N subscriber units, and the output of the N-input element is NOT connected to the “Prohibition” inputs of N subscriber units. N information inputs of the multiplexer are connected to the first signal outputs of the corresponding N subscriber units. J, where J =] log ₂ N [, the subscriber code outputs of the counter are connected to the corresponding J address inputs of the multiplexer and at the same time are respectively the J outputs of the subscriber code of the device. The multiplexer output is connected to the inverter input and at the same time is the enable output of the device. The inverter output is connected to the first input of the AND element, and the counter reset input is a polling input of the device. Inputs "Zeroing" N subscriber units are the corresponding inputs "Zeroing" of the device.

 Moreover, each subscriber unit consists of a counter, an AND element, a three-input AND element, an inverter, an OR element. The inverse input of the counter account resolution is the request input of the subscriber unit and is connected to the first input of the element I. The information inputs of the counter are the corresponding K-bit input "Maximum waiting time code" of the subscriber unit. The counter reset input is the “Zeroing” input of the subscriber unit. The inverse output of the counter is connected to the first input of the three-input element And and the input of the inverter. The inverter output is connected to the second input of the OR element and is the “Exceed” output of the subscriber unit. The second input of the three-input element And is connected to the first input of the element I. The second input of the element And is the input "Prohibition" of the subscriber unit. The third input of the three-input element And is the clock input of the subscriber unit. The output of the three-input element AND is connected to the counting input of the counter. The output of the AND element is connected to the first input of the OR element. The output of the OR element is the first signal output of the subscriber unit.

 Such a scheme allows, in comparison with analog devices, to increase the likelihood of timely service of low-priority requests due to the extraordinary service of requests with an expired wait time taking into account their priorities.

 However, the prototype device has disadvantages: relatively low reliability and relatively low speed, which are due to the large number of components of the prototype device.

 The purpose of the claimed technical solution is to develop a request servicing device that provides improved performance and reliability by reducing the number of elements included in its composition.

The goal in the inventive device for servicing multi-priority requests of subscribers of a computer system is achieved by the fact that in a known device for servicing requests for subscribers of a computer system containing N subscriber units, where N≥2, a clock generator, request inputs and K-bit inputs "Code maximum waiting time ", where K≥1 is the capacity of the code for the maximum waiting time for the service request, N subscriber units are the corresponding request inputs and K-bit inputs" Code max the device’s minimum latency, the Nulling inputs N subscriber units are the corresponding Nulling device inputs, the first and second N-input NAND elements, the first and second priority encoders, the OR element, the NAND element and the selector are additionally entered multiplexer. The N inputs of the first and second N-input elements are NOT connected to the corresponding N inverse inputs of the first and second priority encoders, respectively. The outputs of the first and second N-input elements AND are NOT connected respectively to the second and first inputs of the OR element, the n-th inverse inputs of the first and second priority encoders, where n = l, 2, ... N, are connected respectively to the first and second signal outputs of the (N + 1) -n-th subscriber unit. The output of the OR element is connected to the second input of the AND-NOT element. The first input of the AND-NOT element is a polling input of the device, and the output of the AND-NOT element is connected to the inverse enable input of the selector-multiplexer and is the enable output of the device. The control input of the selector-multiplexer is connected to the second input of the OR element. J inverse outputs of the first and second priority encoders, where J =] log ₂ N [, are connected to the corresponding J inputs of the second and first groups of inputs of the selector-multiplexer, respectively. The output of the clock generator is connected to the clock inputs of all subscriber units, and the J outputs of the selector-multiplexer are, respectively, the J outputs of the device Subscriber Code to be serviced.

 The subscriber unit consists of a counter, an inverter, a three-input element I. The inverse input of the resolution of the counter account is the request input of the subscriber unit and is connected to the second input of the three-input element And and the input of the inverter. The information inputs of the counter are the K-bit input "Code maximum latency" of the subscriber unit, and the reset input of the counter is the input "Zeroing" of the subscriber unit. The inverse output of the counter is connected to the first input of the three-input element And is the first signal output of the subscriber unit. The third input of the three-input element And is the clock input of the subscriber unit, and the output of the three-input element And is connected to the counting input of the counter. The inverter output is the second signal output of the subscriber unit.

 Higher, in comparison with the prototype device, the performance of the claimed device is achieved due to the fact that the delay time of the appearance of the result of the work after setting the signal at the polling input of the device is determined only by the combined delay time of the operation of the NAND element and the selector-multiplexer switching to the output of the claimed device code of the service request. At the same time, in the prototype device, after setting the signal at the polling input, a sequential polling of all batteries is initiated in order to control the presence of request signals in them. Further, in the prototype device, the request to be serviced is determined and then the code of the request to be serviced is output to its output.

 The analysis of the prior art by the applicant made it possible to establish that there are no analogues that are characterized by sets of features that are identical to all the features of the claimed device for servicing diverse priorities of subscribers of a computing system. Therefore, the claimed invention meets the condition of patentability "Novelty."

 The search results for known solutions in this and related fields of technology, in order to identify features that match the distinctive features of the prototype of the claimed invention showed that they do not follow explicitly from the prior art. From the prior art determined by the applicant, the influence of the provided by the essential features of the claimed invention on the achievement of the specified technical result is not known. Therefore, the claimed invention meets the condition of patentability "Inventive step".

The claimed objects of the invention are illustrated by drawings, in which:
figure 1 - service device of different priority requests of subscribers of a computing system;
figure 2 - subscriber unit;
figure 3 - the structure of the computing system;
figure 4 - placement of request signals in the queue of the second order;
figure 5 - the order of transfer of requests from the second order queue to the first order queue.

The device (see figure 1) consists of a clock 2, the first and second N-input elements NAND 7, 10, the first and second priority encoders 8, 9, OR 4, NAND 5, selector- the multiplexer 6, N subscriber units (AB) 1 ₁ -1 _N (AB scheme is shown in figure 2).

 The elements are interconnected as follows (see figure 1). The output of the clock generator 2 is connected to the clock inputs 14 of each of the N subscriber units. Request inputs 11 and K-bit inputs 12 "Maximum latency code" N subscriber units are the corresponding request inputs and K-bit inputs "Maximum latency code" of the device. Zeroing inputs 13 N subscriber units are the corresponding Zeroing inputs of the device. N inputs of the first and second N-input elements AND-NOT 7, 10 are connected to the corresponding N inverse inputs of the first and second encoders of priorities 8, 9. The outputs of the first and second N-input elements AND-NOT 7, 10 are connected respectively to the second and the first inputs of the OR element 4. n-th inverse inputs of the first and second priority encoders 8, 9, where n = 1,2, ... N, are connected respectively to the first 15 and second 16 signal outputs (N + 1) -n- Go subscriber unit. The output of the OR element 4 is connected to the second input of the AND-NOT element 5. The first input of the AND-NOT 5 element is the interrogation input 17 of the device, and the output of the AND-NOT 5 element is connected to the inverse enable input of the selector-multiplexer 6 and is the enable output 18 of the device. The control input of the selector-multiplexer 6 is connected to the second input of the OR element 4. J inverse outputs of the first and second priority encoders 8, 9 are connected to the corresponding J inputs of the second and first groups of inputs of the selector-multiplexer 6, respectively, and J outputs of the selector-multiplexer 6 are respectively J outputs 19 "Subscriber Subscriber Service Code" of the device.

 The clock generator 2 is designed to generate a synchronizing sequence of pulses and can be built according to any known scheme. See, for example, V.L. Shilo "Popular digital circuits", M .: "Radio and communications", 1987, p. 50-53.

 Priority encoders 8 and 9 are designed to convert a low-level signal at one of their inputs into a binary code at the output, and the conversion is carried out taking into account the priorities of the signals corresponding to the input numbers. Priority scrambler implementation scheme is known. See, for example, in the book: V.L. Shilo "Popular digital circuits", M .: "Radio and communications", 1987, p. 147-148.

 The selector-multiplexer 6 is designed for switching one of two J-bit groups of inputs to output. Implementation schemes for such a selector-multiplexer are known. See, for example, in the book: V.L. Shilo "Popular digital circuits", M .: "Radio and communications", 1987, p. 139-140.

Subscriber units 1 ₁ -1 _N are designed to control the receipt of request signals, control the remaining waiting time, as well as generate control signals after a specified waiting time for each request.

 The subscriber unit can be implemented in various ways. In particular, its circuit shown in figure 2, contains a counter 1.1, an inverter 1.2 and a three-input element And 1.3.

 The inverse input of the resolution of the counter counter 1.1 is the request input 11 of the subscriber unit and is connected to the second input of the three-input element And 1.3 and the input of the inverter 1.2. To the information inputs of counter 1.1 are the K-bit input "Code maximum latency" 12 of the subscriber unit, and the reset input of the counter 1.1 is the input "Zero" 13 of the subscriber unit. The inverse output of the counter 1.1 is connected to the first input of the three-input element And 1.3 and is the second signal output 16 of the subscriber unit. The third input of the three-input element And 1.3 is the clock input 14 of the subscriber unit, and the output of the three-input element And 1.3 is connected to the counting input of the counter 1.1. The output of the inverter 1.2 is the second signal output 16 of the subscriber unit.

 Counter 1.1 is intended for counting the pulses (counting pulses) received at its input, for generating a control signal determined by the initial filling code for inputs D and the period of the clock pulses, that is, it is a configurable timer. The description of the operation and the circuit of such a counter are known and are given, for example, in the book: P.P. Maltsev, N.S. Dolidze et al., "Digital Integrated Circuits: A Guide", -M.: Radio and Communication, 1994, p. 64-65.

The device operates as follows. Before the device starts working on the group of K-bit inputs "Code maximum latency" 12 ₁ -12 _N to the information inputs of the counters 1.1 ₁ -1.1 _N subscriber units receive codes that specify the maximum waiting time for servicing requests, ensuring the initialization of the counters. The shortest latency corresponds to the largest code, which complements the maximum number represented in the K-bit code.

по цепи элемент ИЛИ 4, элемент И-НЕ 5 установлен высокий логический уровень. Система готова к работе и ожидает сигналы запросов, вырабатываемые абонентами вычислительной системы (см. фиг.3).In the initial period, when there are no service requests, low logic levels are set at all request inputs of 11 subscriber units. The three-input element AND 1.3 of all batteries is closed, clock pulses from the clock generator 2 to the counting inputs From the counters 1.1 batteries do not arrive. From the side of the computing resource, there is no signal about the release of the resource (low level is set at the polling input 17). At the second and first signal outputs AB 1 ₁ -1 _N set high logic levels. Accordingly, the outputs of the first and second N-input elements AND NOT 7, 10 set low logic levels. The outputs of the selector-multiplexer 6 are open, since at the inverse enable input

the circuit element OR 4, element AND NOT 5 set a high logical level. The system is ready for operation and awaits request signals generated by subscribers of the computing system (see figure 3).

через установленный интервал времени, определяемый кодами начального заполнения счетчиков и частотой тактовых импульсов.When a need arises for a computing resource, subscribers of the computing system generate request signals that are sent to the request service device and placed in a second-order queue. The request signal from the subscriber is considered a high level signal installed on the request input 11 of the corresponding battery. At the same time, at the second signal outputs 16 of these batteries through inverters 1.2, low level signals will be established. The set of low-level signals at the second signal outputs 16 AB forms a second-order queue. The position of the request signal in the second order queue is determined by its initial priority: the request signal received from the subscriber with the lowest number has the highest priority (see Fig. 4). The counting inputs from the 1.1 AB counters containing the request signals receive pulses from the clock pulse generator 2 in the circuit: the clock inputs are 14 AB, the open three-input elements AND 1.3 AB. Counters 1.1 perform the function of timers, which control the expiration of the allowable time for requests to be in the second order queue by summing the clock pulses received at their counting input and generate an overflow signal at the outputs

after a set time interval determined by the codes for the initial filling of the counters and the frequency of the clock pulses.

The signals from the second signal outputs 16 ₁ -16N AB 1 ₁ -1 _N are supplied to the inverse inputs of the second priority encoder 9, which converts the request signals into a J-bit code corresponding to the AB number taking into account its priority. In this case, the signal from the second signal output of the first AB goes to the Nth inverse input of the second priority encoder 9, the signal from the second signal output of the second AB goes to the (N-1) inverse input of the second priority encoder 9, the signal from the second signal output of the n-th battery goes to the (N + 1) -n-th inverse input of the second priority encoder 9, the signal from the second signal output of the N-th battery goes to the first inverse input of the second priority encoder 9. The specified method of connecting the second signal outputs 16 ₁ - 16 _N AB due to the fact that the moves of the second priority encoder are 9 inverse, that is, in order to obtain at its output a code corresponding to the battery with the lowest number from those batteries whose second signal outputs 16 have low logic levels (request signals), the second battery signal outputs should be connected to the inputs of the second Priority encoder 9 in reverse order. If there is at least one request signal in the second-order queue, a high level will be established at the output of the second N-input AND-NOT 10 element.

As the computing resource becomes free, a high-level signal is generated, which is fed to the interrogation input of the device 17 and then to the first input of the NAND 5 element. If there is at least one request in the second-order queue, a low level signal will be established at the output of the NAND 5 element. , which will allow data transmission to the selector-multiplexer 6. At the selective input S of the selector-multiplexer 6, a low level is set (at the first signal outputs of all batteries there is a high level), therefore, to the outputs "Code to be serviced bonenta "19-selector multiplexer 6 will be switched code received at input A ₁ -A _J of the first group selector-multiplexer inputs 6 and corresponding to the smallest number AB containing a request signal from the second-order queue.

 After satisfying the subscriber’s demand for computing resources, the subscriber removes the request signal from the request input 11 of the corresponding battery, and resets the counter 1.1 of the corresponding battery at the input “Zero” 13. At the same time, the first and second signal outputs 15 and 16 of the corresponding batteries will be high.

а следовательно, и на первых сигнальных выходах 15 сигналов низкого уровня, что соответствует переносу запросов в очередь первого порядка на места, соответствующие их приоритетам (см. фиг.5). в целях их дальнейшего внеочередного, по отношению к очереди второго порядка, обслуживания. При этом запираются трехвходовые элементы И 1.3, запрещая поступление тактовых импульсов на счетные входы С счетчика 1.1. Совокупность сигналов низкого уровня на первых сигнальных выходах 15 АБ образует очередь первого порядка. Обслуживание запросов из очереди первого порядка осуществляется с учетом их начальных приоритетов. При этом формирование кода, соответствующего наименьшему номеру АБ, содержащему сигнал запроса из очереди первого порядка, осуществляется первым шифратором приоритетов 8 тем же способом, что и из очереди второго порядка. При наличии запроса в очереди первого порядка их внеочередное, по отношению к запросам из очереди второго порядка, обслуживание обеспечивается сигналом высокого уровня на выходе первого N-входового элемента И-НЕ 7, который, поступая на селективный вход S селектора-мультиплексора 6, коммутирует на выходы "Код подлежащего обслуживанию абонента" 19 сигналы по группе входов B₁-B_J. Сигнал высокого уровня на выходе первого N-входового элемента И-НЕ 7 будет до тех пор, пока в очереди первого порядка есть хотя бы один запрос.In the event that one or several requests as a result of the created queue have reached the maximum waiting time, overflows of the counters 1.1 of the corresponding batteries, overflows on their inverse outputs

and therefore, at the first signal outputs 15 low-level signals, which corresponds to the transfer of requests in the first order queue to the places corresponding to their priorities (see figure 5). with a view to their further extraordinary, in relation to the second-order queue, service. At the same time, the three-input elements AND 1.3 are locked, prohibiting the arrival of clock pulses to the counting inputs C of the counter 1.1. The set of low-level signals at the first signal outputs of 15 AB forms a first-order queue. Requests from the first order queue are serviced taking into account their initial priorities. In this case, the formation of the code corresponding to the lowest AB number containing the request signal from the first order queue is performed by the first priority encoder 8 in the same manner as from the second order queue. If there is a request in the first-order queue, their extraordinary, in relation to requests from the second-order queue, service is provided by a high-level signal at the output of the first N-input element AND-NOT 7, which, entering the selective input S of the selector-multiplexer 6, commutes to outputs "Subscriber code to be serviced" 19 signals according to input group B ₁ -B _J. The high-level signal at the output of the first N-input element AND-NOT 7 will be until there is at least one request in the first-order queue.

счетчика 1.1, устанавливая тем самым на первом и втором сигнальных выходах 15 и 16 этого АБ высокие уровни, что позволит устройству после выполнения всех запросов с истекшим временем ожидания перейти к обслуживанию вновь поступивших, либо ждущих своей очереди запросов в порядке, определенном логикой работы устройства.After releasing the resource allocated in the interests of the next request of the subscriber from the first-order queue (with the elapsed waiting time), the subscriber removes the request signal from the request input 11 of the corresponding battery and resets the counter 1.1 of the corresponding battery at the input "Reset" 13, which will set a high level at the output

counter 1.1, thereby setting high levels on the first and second signal outputs 15 and 16 of this battery, which will allow the device, after all requests with an expired waiting time, to proceed to service newly arrived or waiting for its turn requests in the order determined by the logic of the device.

Claims (2)

1. A device for servicing multi-priority subscriber requests of a computing system, containing N subscriber units, where N≥2, a clock generator, request inputs and K-bit inputs "Code for maximum waiting time", where K≥2 is the capacity of the code for maximum waiting time for request service , N subscriber units are the corresponding request inputs and K-bit inputs of the "Maximum latency code" of the device, inputs "Zero" N subscriber units are the corresponding inputs "Zero" device characterized in that the first and second N-input NAND inputs are additionally introduced, N inputs of which are connected to the corresponding N inverse inputs of the first and second priority encoders, respectively, and the outputs of the first and second N input NAND inputs are connected respectively to the second and first inputs of the OR element, the nth inverse inputs of the first and second priority encoders, where n = 1,2,. . . , N, are connected respectively to the first and second signal outputs (N + 1) of the nth subscriber unit, the output of the OR element is connected to the second input of the AND-NOT element, the first input of which is the polling input of the device, the output of the AND-NOT element is connected to the inverse the enable input of the selector-multiplexer and is the enable output of the device, the control input of the selector-multiplexer is connected to the second input of the OR element, J inverse outputs of the first and second priority encoders, where J =] log ₂ N [, are connected to the corresponding J inputs with respectively, the second and first groups of inputs of the selector-multiplexer, the output of the clock generator is connected to the clock inputs of all subscriber units, J outputs of the selector-multiplexer are the corresponding J outputs "Device Subscriber Code" of the device.  2. The device according to p. 1, characterized in that the subscriber unit consists of a counter, the inverse of the account resolution of which is the request input of the subscriber unit and connected to the second input of the three-input element And and the input of the inverter, K information inputs of the counter are K-bit input " The code is the maximum waiting time "of the subscriber unit, and the counter reset input is the input" Zeroing "of the subscriber unit, the inverse output of the counter is connected to the first input of the three-input element And is the first signal output subscriber unit, the third input of the three-input element And is the clock input of the subscriber unit, and the output of the three-input element And is connected to the counting input of the counter, the inverter output is the second signal output of the subscriber unit.

Images