RU2415465C2 - Multichannel priority device - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: device has M channels, each containing a decoder, a group of AND elements, first and second OR elements, and the K-th channel (K=1,…M-1) additionally contains an AND element with non-inverting and inverting inputs, where each channel includes a delay element, where in each channel the request input is connected to the input of the delay element, the output of which is connected to the second inputs of all AND elements of the group of AND elements in its channel.

EFFECT: broader functionalities owing to introduction of request service procedures with absolute priorities.

1 dwg

Description

The invention relates to the field of computer technology and can be used in information processing systems to organize the access of subscribers to a public device.

A multi-channel priority device is known / USSR Author's Certificate No. 970372, G06F 9/46 /, containing channels, each of which contains an OR-NOT element, an NOT element, an OR element, and an I. element.

The disadvantage of this device is the severity of priorities determined by the subscriber’s connection location, i.e. channel number.

A multi-channel priority device is known / USSR Author's Certificate No. 1633403, G06F 9/46 /, containing a group of code inputs, a register, a decoder, a polling input, M channels, each of which contains AND elements, OR elements, an NOT element, a device request input and an output devices.

The disadvantages of the device are the dependence of the priorities of subscribers on the connection point of the most important subscriber and the inability to interrupt service of a lower priority subscriber when there is a request from a higher priority subscriber, i.e. the inability to service subscribers in accordance with the discipline of service with absolute priorities.

The closest in technical essence to the claimed device is a multi-channel priority device selected as a prototype / USSR Author's Certificate No. 1809441, G06F 9/46 /, containing an OR-NOT element, an AND element, an OR element, a pulse shaper, a delay element, a group of OR elements , a high-order selection block containing AND elements with direct and inverse inputs, H channels, each of which contains a trigger, an OR element, a second and first group of AND elements, a register, a decoder, a channel response output, a channel reset input, g the group of code inputs of the device, the channel request input, and the single trigger output of each channel is the channel response output and is connected to the corresponding input of the OR-NOT element, the output of which is connected to the first input of the AND element, the second input of which is connected to the output of the OR element, the inputs of which are request inputs of the corresponding channels, the output of the AND element is connected to the input of the pulse shaper, the group of code inputs of the device is connected to the group of inputs of the first group of elements AND of the corresponding channel, the output of the The pulse generator is connected to the input of the delay element and to the second inputs of the first group of elements AND of all channels, the group of outputs of the first group of elements AND of each channel is connected to the group of information inputs of the register of its channel, the group of outputs of which is connected to the group of the channel decoder, K-th (K = 1, ..., H) whose output is connected to the first input of the Kth element AND of the second group of elements AND of its channel and to the channel of the same name with the input of the Kth element OR of a group of elements OR, the output of the Kth element AND of the second group of elements AND is connected to K th in the house of the OR element of its channel, the output of which is connected to the single input of the trigger of its channel, the zero input of the channel trigger is the channel reset input and connected to the input of resetting the channel register, the output of the delay element is connected to the second inputs of the elements And the second groups of elements And of all channels, output Н -th element OR group of elements OR is the N-th input and output of the high-order selection block (BSSR) and is connected to the third inputs of the H-elements And the second groups of elements AND of all channels and the first inverse inputs of all ele nths And with direct and inverse inputs of the BVSR, the output of the Mth [M = 1, ..., (H-1)] element And with direct and inverse inputs of the BVSR is the Mth output of the BVSR and is connected to the third inputs of the M-elements of And of the second group of AND elements of all channels, the output of the first OR element of the OR group of elements is connected to the direct input of the first AND element with direct and inverse inputs of the BSSR, the output of the Ith [I = 2, ..., (H-1)] OR element of the group is connected to direct input of the I-th element And with direct and inverse inputs of the BSSR and with the corresponding inverse inputs of each of the elements And with direct and inverse the inputs of the BVSR, the numbers of which are less than I.

The device operates as follows.

In the initial state, the registers and triggers of all channels are in the zero state, therefore, using the OR element is NOT opened the element I. At random times from the subscribers (not shown) the request signals in the form of a logical unit are received at the request inputs of the corresponding channels. At the same time, from the subscribers to the corresponding group of code inputs of the device their priority codes are received (priority is higher, the higher the code). The device uses a binary priority code. Subscribers do not have the same codes. If the request is not received from the subscriber, then, accordingly, the code does not arrive at the group of code inputs of the device, because the code will be zero. The request signal, passing through the OR element and the open AND element, generates an impulse along the rising edge with the help of a pulse shaper, according to which priority codes are entered into the channel registers through the first group of AND elements. In accordance with the received code at the corresponding K-m (K = 1, ..., N) output of the decoder, a signal of a logical unit appears. This signal opens at the first input the Kth element AND of the second group of AND elements of its channel and, passing through the Kth element OR of the group of OR elements, enters the high-order selection block. At the output of this block, which corresponds to the largest priority code from the received, a single signal occurs.

Assume that the senior bit corresponds to the K-th signal of the channel decoder. Then, from the Kth output of the BSSR, the signal of the logical unit goes to all Kth elements AND of the second group of elements AND of all channels. Then, after a delay time equal to the operation of the register, decoder, group of elements OR and BSSR, the pulse previously generated on the former will appear from the output of the device delay element. This pulse gates all the elements AND of the second group of elements AND of all channels. As a result, at the output of the Kth element of the second group of elements of the AND channel corresponding to the Kth (oldest available) priority code, a single signal is formed, which, passing through the OR element of its channel, sets the trigger to a single state. Thus, at the output of the channel response corresponding to the highest priority code, a single signal is generated, indicating the resolution of capture of the common device. As this signal is generated using the OR-NOT element of the device, the AND element of the device is closed. After the subscriber’s service is completed by the public device, a single signal is received at the channel reset input. This signal resets the trigger and the channel register. As a result, the And element opens again and the channel is further selected with the highest priority code from the channels that submitted service requests. In the future, the operation of the device is repeated. The choice of senior level is as follows. When signals are received at the inputs of the BSSR, the signal corresponding to the highest bit (the bit is the older, the higher the sequence number of the input of the BSSR), closes all the elements And the BSSR, the sequence number of which is less than the number of this signal. After that, this signal corresponding to the high order is fed to the corresponding output of the BSSR.

Thus, if during the servicing of this subscriber a request is received from a higher priority subscriber, this request will be serviced only after the service of this subscriber is completed.

However, it is known / 1 / that in real-time computing systems, a delay in the queue for processing more important requests leads to greater losses in system efficiency than a delay in less important requests. To increase the efficiency of a computing system, it is first necessary to provide a public device (OOP) to service a request that has the highest priority (importance). Such a discipline (discipline with absolute priorities) of using OOP (request servicing) is equivalent to increasing the productivity of the entire system / 1 /.

Thus, this device does not provide priority servicing of a more important request if it appeared during servicing of less important requests, which is its drawback.

The aim of the invention is to expand the scope of the device by introducing the discipline of servicing requests with absolute priorities.

This goal is achieved by the fact that in a multi-channel priority device containing M channels, each of which contains a decoder, a group of AND elements, a first and second OR element, a group of code inputs, a request input, a response output, and a K-th channel (K = 1 , ..., M-1) additionally contains an And element with direct and inverse inputs, and in each channel the group of code inputs is connected to the group of inputs of the decoder, the N-th output of which (H = 1, ..., M) is connected to the first input H- of the element And the group of elements And its channel, the I-th input (I = 1, ..., M) of the second element OR of the Nth channel (H = 1, ..., M) is connected to the Nth output of the decoder of the 1st channel, the output of the second element OR of the Kth channel (K = 1, ..., M-1) is connected to the direct input of the element And with direct and inverse inputs of its channel, the outputs of which are connected to the third inputs of K-elements AND groups of elements AND of all channels, the output of the second OR element of each channel, except the first, is connected to the corresponding inverse input of the AND element with direct and inverse inputs of each other channel whose number is less than this, the output of the second element OR of the Mth channel is connected to the inputs of the Mx elements AND the group of elements AND of all channels in each channel the outputs of the elements AND the group of elements AND are connected to the corresponding inputs of the first OR element, the output of which is the output of the channel response, a delay element is introduced into each channel, and in each channel the request input connected to the input of the delay element, the output of which is connected to the second inputs of all elements AND the group of elements AND its channel.

Comparative analysis with the prototype shows that the inventive device is characterized by the presence of new elements - delay elements in each channel and the connections of each of them with other elements of the device.

Thus, the claimed device meets the criteria of the invention of "novelty."

An analysis of the similar technical solutions known to the author in the given technical field did not reveal the features distinguishing the claimed solution from the prototype, which allows us to conclude that the claimed solution meets the criterion of "significant differences".

The drawing shows a structural diagram of a device.

The device contains M channels 1, which include a decoder 2, a group of elements AND 3, the first and second elements OR 4, 5, an element 6 with direct and inverse inputs, a delay element 7, a group of code inputs 8, request input 9, output 10 answers.

The elements of the device shown in the drawing are connected as follows.

In each channel 1, the group of code inputs 8 is connected to the group of inputs of the decoder 2, the Nth output of which (H = 1, ..., M) is connected to the first input of the Nth element And the group of elements AND 3 of its channel 1, Ith input (I = 1, ..., M) of the second element OR 5 of the N-th channel (Н = 1, ..., M) is connected to the N-th output of the decoder 2 of the I-th channel 1, the output of the second element OR 5 of the K-th channel ( K = 1, ..., M-1) is connected to the direct input of the And 6 element with direct and inverse inputs of its channel 1, the outputs of which are connected to the third inputs of the K-x elements And the group of And 3 elements of all channels 1, the output of the second IL element And 5 of each channel 1, except the first, is connected to the corresponding inverse input of the And 6 element with direct and inverse inputs of each other channel 1, the number of which is less than this, the output of the second element OR 5 of the Mth channel 1 is connected to the third inputs of the M-x elements And the group of elements And 3 of all channels 1, in each channel 1 the outputs of the elements And the group of elements And 3 are connected to the corresponding inputs of the first element OR 4, the output of which is the output of the response 10 of channel 1, in each channel the input of the request 9 is connected to the input of the delay element 7 which output oh connected to the second inputs of all elements AND groups of elements AND 3 of its channel 1.

The device operates as follows.

In the initial state, at the inputs 9 of the request for channels 1 and groups of code inputs 8, zero signals are present. At random times from subscribers (subscribers are not shown in the drawing), request signals in the form of a logical unit are received at the request inputs 9 of the corresponding channels 1. At the same time, from the subscribers to the corresponding group of code inputs 8 their priority codes are received (priority is higher, the older the code). The device uses a binary priority code, and subscribers cannot have the same codes, but they can be changed quickly when reconfiguring the computing system. Further, when describing the operation of the device, when prompted by a subscriber, we mean the simultaneous receipt of a single signal at input 9 and a priority code for a group of code inputs 8 of the corresponding channel 1. If there is no request from the subscriber, the code will be equal to the corresponding group of code inputs 8 zero, therefore, the zero outputs of the decoders 2 are not used in the device (only the outputs from the 1st to the Mth are used, where M is the number of channels).

Consider the situation when a request is received from the first subscriber, i.e. channel 11, and then, during its servicing, a request was received from the second subscriber (i.e., channel 12), the priority of which is higher than that of the first subscriber (suppose that the priority code received in the corresponding channel is equal to the channel number )

Thus, in the first channel 11 at the first output of the decoder 2, a single signal will be established, which will open the first element And 31 of the group of And elements on the first input and passing through the second element OR 5 and entering the direct input of the And element with direct and inverse inputs 6, will ensure the appearance of a single signal at its output (since zero signals are present at its inverse inputs at that time), which will open the first element And 31 of the group of elements I at the third input. By this moment, in the first channel 11, the output of delay element 7 will appear single the first signal, which, having passed through the first element AND 31 of the group of AND elements and through the first element OR 4, will go to the output of answer 10. A single signal from the output of answer 10 will give permission to the first subscriber to access the public device (if this signal is absent, then subscriber’s access to the public device will be denied). From this moment, the first subscriber is serviced by a public device and, if before the end of his service, a request signal is received from the second subscriber (whose priority is higher than that of the first subscriber, since he is equal to two in the situation under consideration and equal to two at the first subscriber unit), then in the second channel 12 at the second output of the decoder 2, a single signal will be established, which will open the second element And 32 of the group of And elements on the first input and, passing through the second element OR 5, will go: firstly, to the first channel 11 according to the inverse input of the And element with direct and inverse inputs 6, setting a zero signal at its output, which in the first channel 11, passing through the And element 31 of the group of And elements and the OR element 4, will ensure that the output of the answer 10 is a zero signal, which will lead to interruption of service of the first subscriber, and, secondly, in the second channel, to the direct input of the And element with direct and inverse inputs 6, causing the appearance of a single signal at its output (since there are zero signals on its inverse inputs), which will go to the third input of the second element And 32 of the group of And elements, and since this element will be open by the second input as a single signal from the output of the delay element 7 (since it delays the request signal from input 9 for the time of operation of the decoder 2, the second element OR 5 and the element AND with direct and inverse outputs 6), then the output of element And 32 of the group of elements And there will be a single signal, which through the element OR 4 will go to the output of the response 10 and will allow the second ab nents access to common device.

After the second subscriber finishes servicing, at the group of code inputs 8 and request input 9 of the second channel 12, this subscriber sets zero signals, which will lead to (after the delay element 7, element And 32, and element OR 4 are triggered in channel 12), the second answer 10 appears on the output channel 12 of the zero signal, and at the output of the response 10 of the first channel 11, a single signal will appear (after operation in the second channel 12 of the decoder 2 of the OR element 5 and in the first channel 11 of the And element with direct and inverse inputs 6, the And element 31 and the OR element 4) , and, traces tion, will continue servicing the first subscriber. Since the delay element 7 delays the signal for the response time of the decoder 2, the OR element 5 and the And element with direct and inverse inputs 6, the appearance of a zero signal at the output 10 of the second channel 12 and a single signal at the output 10 of the first channel 12 will occur simultaneously.

If, before the end of the second subscriber’s service, a request from a higher priority subscriber appears, then the second subscriber’s service will be interrupted similarly to the one described above, and when the highest priority subscriber (of those that issued service requests) is serviced, then service of lower priority will continue subscribers in the order of their priorities.

Since the inputs of the second OR element 5 of the last 1 m channel can receive only signals corresponding to the highest priority of the subscriber (which other subscribers cannot interrupt), this channel does not have an And element with direct and inverse inputs 6.

Thus, the proposed device provides absolute priority to subscribers in accordance with their priorities, which can be changed quickly when reconfiguring the computing system.

Due to the fact that the proposed device does not create savings, but gives a different positive effect, it takes into account the importance of queries, which makes it possible to increase the equivalent performance of a computing system, we will carry out a comparative analysis of the proposed and basic device, which is chosen as the prototype, since it most effectively implements the functions organization of access to the shared resource.

The basic device implements the discipline of servicing requests with relative priorities. The proposed device allows discipline with absolute priorities and, due to this, receive wins in equivalent performance. The methodology for assessing the effectiveness of the discipline with absolute priorities compared to relative priorities is given in / 1 /, where it is shown that it was not possible to obtain simple analytical expressions to determine the gain in equivalent performance, and to determine the values of the effectiveness of the disciplines, calculations have to be carried out sequentially using formulas that allow you to first determine the duration of waiting for requests in the queue, then the total length of stay in the system and the total penalty for this. The results of the performance assessment, presented in / 1 / in graphical form, for two request flows show that when the device is loaded equal to 0.9, with the ratio of processing time of lower priority requests to the processing time of higher priority requests equal to 30, and the same penalty ratio unit of waiting time for higher priority penalties per unit of waiting time for lower priority requests, gain in equivalent performance from the use of the proposed device compared to the basic device with makes about 40%.

Information sources

1. Lipaev V.V., Yashkov S.F. The effectiveness of the methods of organizing the computing process in ACS. - M .: Statistics, 1975, p. 39, p. 127-129.

Claims (1)

A multi-channel priority device containing M channels, each of which contains a decoder, a group of AND elements, the first and second OR elements, and the K-th channel (K = 1, ..., M-1) additionally contains an And element with direct and inverse inputs, moreover, in each channel, the group of code inputs is connected to the group of inputs of the decoder, the Nth output of which (H = 1, ..., M) is connected to the first input of the Nth element And the group of elements And its channel, the 1st input (I = 1 , ..., M) of the second OR element of the Nth channel is connected to the Nth output of the decoder of the 1st channel, the output of the second OR element -th channel is connected to the direct input of the AND element, with direct and inverse inputs of its channel, the outputs of which are connected to the third inputs of the K-x elements AND the group of elements AND of all channels, the output of the second OR element of each channel, except the first, is connected to the corresponding inverse input And element, with direct and inverse inputs of each other channel whose number is less than this, the output of the second OR element of the Mth channel is connected to the third inputs of the Mx elements AND of the group of elements AND of all channels, in each channel the outputs of the elements AND of the ele The AND elements are connected to the corresponding inputs of the first OR element, the output of which is the channel response output, characterized in that a delay element is introduced into each channel, and in each channel, the request input is connected to the input of the delay element, the output of which is connected to the second inputs of all AND elements elements And your channel.