Method of service differently prioritised customer computer system and the device for its realization

 

(57) Abstract:

The invention relates to the field of computer engineering and can be applied in communication systems. The technical result is timely service nizkoplotnykh requests. The device contains N subscriber units, where N 2, counter, clock, divider, N-shadowy the item OR NOT, a multiplexer, an inverter element And the selector-multiplexer, encoder priorities, N-shadowy element AND-NOT, the decoder low-level blocks To fetch and commit, where the K - bit code the remaining waiting time. The method describes the operation of this device. 2 c. and 2 C. p. F.-ly, 13 ill.

The proposed technical solutions combined to form a single inventive concept relate to the field of computer engineering and can be applied in communication systems.

Known methods of service requests of the computing system implemented, for example, in the device A. C. the USSR 1441398 "Multi-device dynamic priority", IPC G 06 F 9/46, publ. 30.11.88, B 44, where the higher priority request is linearly over a certain interval of time; and. C. the USSR 1562912 Multichannel ostreoida after each service request on other priority areas. (Under the terms of the service request, the priority means the following. Service - the set of actions of a computing system that includes a sample request from the queue, the resource allocation, as well as carrying out the finishing operations. The request is to send the signal that triggers the response. Input message containing a request to the system for resource allocation. The priority number, the prescribed task, process, or operation that determines the order of their execution or maintenance. The smaller the number, the higher the priority level).

However, the known methods analogs do not take into account the valid time of the request in the queue, resulting in a high probability of loss of low-priority requests as a result of their untimely service.

The known device service requests - see , for example, and. C. the USSR 1441398 "Multi-device dynamic priority", IPC G 06 F 9/46, publ. 30.11.88, BI 44; and. C. the USSR 1562912 "Multichannel device with dynamic change priority", IPC G 06 F 9/46, publ. 07.05.90, BI 17.

Known analogues are increasing priority and units of analysis priorities. The General lack of analogues is a low probability when usnote to the claimed method of service requests is the way, implemented in the device for service requests and see. C. RF 2140666 "Method for serving user requests the computing system and device for its realization", IPC G 06 F 9/46, publ. 27.10.99, B 30.

Prototype method is that form codes maximum waiting time service request Tthe coolant.iwhere i= 1,2, . . . N - the corresponding priority number of the i-th subscriber, and N is the total number of subscribers, and memorize them. Then form the pings and organize from the pings of all second order in accordance with priorities subscribers. Requests from the queue of the second order, which reached a maximum wait time, transfer to the queue of the first order at the position corresponding to the numbers of their priorities. Consistently serve the requests from the queue of the first order in accordance with the increase in numbers of priorities, and in the absence of requests in the queue of the first order, serve the requests from the queue of the second order.

Prototype method takes into account the maximum time spent by the requests in the queue of the second order, and the priority of the requests when transferring them to the queue of the first order, which ensures a high probability of timely about what uzywane low-priority requests. This is because the prototype method does not take into account the timing of requests (VISA) from the queue of the second order when the priority service. For this reason, queries with small VISAS expect service as much, and requests of the same priority with large VISAS. (Under VISA refers to the time required to service the request).

Known the closest analogue (prototype) for their technical nature of the claimed device is a device (the first option) and see. C. RF 2140666 "Method for serving user requests the computing system and device for its realization", IPC G 06 F 9/46, publ. 27.10.99, B 30.

The device service requests of subscribers of a computer system containing N subscriber units, where N2, count, item, clock, divider, N-shadowy the element OR NOT, the multiplexer, the first inverter. While the counting input of the counter is connected to the output element And the second input element And is connected to the generator output clock pulses and the input of the divider. The output of the divider is connected to clock inputs of the N subscriber units. Query inputs and K-bit inputs, where K2 - bit code maximum wait time service for the mi and K-bit input Code, the maximum time-out" device, N inputs N-Vodolaga item OR IS NOT connected to the outputs of the "Excess" of the corresponding N subscriber units, and the output of the N-Vodolaga item OR IS NOT connected to the inputs of the "Ban" N subscriber units. N information inputs of the multiplexer are connected with the first signal outputs corresponding to N subscriber units. J, where J = ]log2N[, outputs a Code subscriber" counter connected to the corresponding J to the address inputs of the multiplexer and at the same time are respectively J outputs the Code of the subscriber devices. The output of the multiplexer is connected to the input of the first inverter and at the same time is permissive output device. The output of the first inverter connected to the first input element And the reset input of the counter is polled input device. Inputs "Zeroing" N subscriber units are relevant inputs to "zero" the device.

Each subscriber unit comprises a counter element And Tregubova element And inverter, OR. Inverted enable input of the account counter is a challenge entry subscriber unit and connected to the first input element And. To information inputs of the counter are the corresponding K-bit input Code maximum time coolant is stroke counter connected to the first input Tregubova element And the input of the inverter. The inverter output is connected to the second input of the OR element and is the output of "Excess" subscriber unit. The second input Tregubova element And connected to the first input element And. Second input element And an entry "Ban" subscriber unit. The third entrance Tregubova element is a clock input of the subscriber unit. Output Tregubova element And connected to the counting input of the counter. The output element And is connected to the first input of the OR element. The output element OR is the first signal output, the subscriber unit.

This scheme allows for comparison with devices with peers to enhance the likelihood of timely service of low priority requests.

However, the device prototype has a drawback: low probability of timely maintenance of low-priority requests. This is due to the fact that the device is a prototype does not account for VISA requests from the queue of the second order when the priority service. For this reason, queries with small VISAS expect service as much, and requests of the same priority with large VISAS.

The purpose of the claimed technical solution is to develop a method and device service requests, Aulnay time losses for requests with a higher priority level by reducing the time spent in the queue of the second order queries with small VISAS.

In the proposed method the goal is achieved by the fact that in the known method of servicing requests of a computer system, namely, that form codes maximum waiting time service request Tthe coolant.iwhere i= l, 2, . . . N - the corresponding priority number of the i-th subscriber, and N is the total number of subscribers, memorize them, form the pings, organize signal requests the turn of the second order in accordance with the non-priority callers from the queue of the second order are transferred to the queue of the first order requests that have reached the maximum waiting time at the position corresponding to the numbers of their priorities, consistently serve the requests from the queue of the first order in accordance with the increase in numbers of priorities, and in the absence of requests in the queue of the first order, serve the requests from the queue of the second order, simultaneously with the formation of codes a maximum wait time of service requests additional form M, where M2, codes, maximum, differing in the duration of time intervals Taboutenough to service requests. When servicing requests from the queue of the second pre-order the minimum number of priority with the maximum time intervals Taboutother requests from the queue of the second order. If there are requests, Taboutless than Tthe coolant.minserve from among the request with the lowest priority number, and if no service request from the queue of the second order with minimum priority number, and compare Tthe coolant.minand Taboutand serve the requests from the queue of the second order as long as there are no requests in the queue of the first order.

A new set of essential features allows you to achieve the technical result due to the formation of M, where M2, codes, maximum, differing in the duration of time intervals Taboutenough to service requests, and service requests from the queue of the second order pre-compare the time interval Tthe coolant.minremaining to timeout service the request with the minimum priority number, with the maximum time intervals Taboutother requests from the queue of the second order and if there are requests, Taboutless than Tthe coolant.minserve from their number a query that has the smallest nomeata, and compare Tthe coolant.minand Taboutand serve the requests from the queue of the second order as long as there are no requests in the queue of the first order.

The goal in the claimed device service differently prioritised customer computing system is achieved by the fact that in the known device service requests of subscribers of a computer system containing N subscriber units, where N2, the counter, the counting input of the counter is connected to the output element And the second input element And is connected to the generator output clock pulses and the input of the divider, the output of the divider is connected to clock inputs of the N subscriber units, a request inputs and K-bit input Code maximum wait time" N subscriber units are appropriate request inputs and K-bit input Code, the maximum time-out" device, N-Vodolaga of the element OR NOT, the N inputs of which are connected to the outputs of the "Excess" of the corresponding N subscriber units, and the output of the N-Vodolaga item OR IS NOT connected to the inputs of the "Ban" N subscriber units, multiplexer, N information input of which is connected with the first signal outputs corresponding to N subscriber units, and its J, where the litter is connected to the input of the first inverter, the output of the first inverter connected to the first input element And the reset input of the counter is polled input device, and inputs "Zeroing" N subscriber units are relevant inputs to "zero" the device, inputs of the selector is a multiplexer, a second inverter, the N-shadowy element AND-NOT, the priority encoder, the decoder low level, block sampling and fixation. J information inputs of the first group selector-multiplexer connected to the corresponding J outputs a Code subscriber" of the counter J of the outputs of the selector-multiplexer are respectively J outputs the Code subject to the service subscriber devices. The input of the second inverter connected to the input of the first inverter and the output of the second inverter is connected to allows the input of the selector is a multiplexer and is at the same time permitting the output device, the n-th, where n= 1,2, . . . N, an inverse input of the priority encoder is connected to the second signal output (N+l)-n-th subscriber unit. J the inverse outputs of the priority encoder connected to the J inputs of the second group of inputs of the selector is a multiplexer. N inputs N-Vodolaga item AND IS NOT connected to the corresponding N inverse inputs of the priority encoder, the RA of the low level is connected to the corresponding J outputs a Code subscriber" counter, and N inverted outputs of the decoder low level is connected to the inputs allowing a comparison of the respective N subscriber units. J inputs "Code subscriber" of each of the blocks To sampling and fixation connected to the corresponding outputs of the "Code of the subscriber in the meter. m-th, where m= 1,2, . . . To, the discharge of the output Code of the remaining time-out" of the n-th subscriber unit connected to the n-th digit of the N-bit sign-Digit code the remaining waiting time of the m-th block sampling and fixation. The control input of each of the blocks To sampling and fixation connected to the output of the first inverter. Outputs the Discharge of the selected code the remaining time-out" To block sampling and fixation connected to the corresponding bits of the K-bit inputs the Selected code, the remaining time-out" each of the N subscriber units. Each subscriber unit is provided in addition to the K-bit input Code maximum service time", which are both K-bit input Code maximum service time" of the device.

The subscriber unit comprises a counter element And Tregubova element And inverter element OR Tregubova element AND-NOT, of the comparator. Inverted enable input of the account of the counter auletta are respectively K-bit input Code maximum wait time" subscriber unit, and the reset input of the counter is input to "zero" the subscriber unit, and the inverted output of the counter is connected to the first input Tregubova element And the input of the inverter. The inverter output is connected to the second input of the OR element and is the output of "Excess" subscriber unit. The second input Tregubova element And connected to the first input element And. Second input element And an entry "Ban" subscriber unit. The third entrance Tregubova element is a clock input of the subscriber unit, and the output Tregubova element And connected to the counting input of the counter. The output element And is connected to the first input of the OR element and the first input Tregubova element. The output element OR is the first signal output, the subscriber unit. The second input Tregubova item AND IS NOT connected to the comparator output, the first and second groups of inputs To inputs of each of which are respectively K-bit input "Selected code, the remaining time-out" and the K-bit input Code, the maximum time of service of the subscriber unit. The third entrance Tregubova element AND IS NOT an entry Permit comparison of the subscriber unit. Output Tregubova element AND NOT the C the om Code the remaining time-out" subscriber unit.

Block sampling and fixation consists of a multiplexer and a D-flip-flop. N information inputs of the multiplexer are respectively N-bit input Bits code the remaining time-out" block sampling and fixation, a J address inputs of the multiplexer are respectively the J inputs "Code subscriber unit sampling and fixation. Information input D flip-flop connected to the output of the multiplexer, a control input of D-flip-flop is a control input unit of sampling and fixation. The output of D-flip-flop is the output of "Discharge of a selected code the remaining time-out" block fetch and commit.

Conducted by the applicant's analysis of the level of technology has allowed to establish that the analogs are characterized by the sets of characteristics is identical for all signs, the inventive method and device maintenance differently prioritised customer computing system, no. Therefore, each of the claimed invention meets the condition of patentability "Novelty."

Search results known solutions in this and related areas of technology, with the purpose of revealing of signs consistent with the distinctive features of the prototype characteristics of each of the claimed invention showed mo the integrity of influence provided the essential features of each of the claimed inventions to the achievement of the technical result. Therefore, each of the claimed invention meets the condition of patentability "Inventive step".

The stated objects of the invention are illustrated by the drawings, there is shown

in Fig. 1 - structure of the computing system;

in Fig. 2 - placing requests in the queue of the second order;

in Fig. 3 - procedure for transfer requests from the queue of the second order in the queue of the first order;

in Fig. 4 - Fig. 7 is a timing diagram of operation of the device service differently prioritised customer computer system;

in Fig. 8 - average time spent in the computer system and the likelihood of timely service requests with different priorities and different VISAS;

in Fig. 9 - the average time spent in the queue of requests with different priorities and different VISAS;

in Fig. 10 - the average time spent in the computer system queries all with different priorities VISAS;

in Fig. 11 - device service differently prioritised customer computer system;

in Fig. 12 - subscriber unit;

in Fig. 13 is a block fetch and commit.

The implementation of the inventive method consists in the following. For each request (GRU> The formation of the above code is from the following considerations. The residence time of the request of the i-th subscriber computing system is known and set normative documents. It is determined by the value of Tadditional i. The amount of VISAS i-th subscriber Tabout.icharacterizes the time spent computing system for maintenance (resource allocation). The value of Tabout.ifor each request is determined experimentally in the initial period of operation or on the basis of statistical data of the operation of similar systems. Moreover, in the General case, it is possible to combine queries the i-th subscriber, with close-largest VISAS in M, where M2, groups, and assign each group requests the value of Tabout.jiwhere j is the sequence number of the query group, sufficient for maintenance (resource allocation) request with the maximum VISAS from this group. The maximum waiting time service request Tthe coolant.idetermines the maximum time that a request in the queue, after which the request will be allocated a resource of the computing system and may be defined by the following ratio:

Tthe coolant.i= Tadditional i-Tabout.ji-Tfor the de i= l, 2, . . . N;

Tadditional i- allowable time request the i-th subscriber computing system, after which the request expires, or the subscriber has certain losses;

Tabout.ji- VISAS i-th subscriber, where j= 1,2, . . . M - the number of the group of queries;

TZap.i- some slack time is defined cost of service.

Generated for each subscriber computing system codes a maximum wait time of service and codes of VISAS remembered (stored). Then the system is ready for operation and receives signals queries generated by subscribers of a computer system (see Fig. 1). They arrive at the device service requests, where is the queue of the second order according to the initial priorities (the first subscriber has the highest priority and N-th subscriber - lowest) (see Fig. 2). Immediately thereafter begins counting the time spent by the requests in this queue.

After receiving from the computing system signal about the release of the resource device query determines in the queue of the second order request with a minimum number of z priority, compares the time TMI intervals Tabout.ji(i= z+1, z+2, . . . N) other requests in a given time in the queue of the second order. Upon detection of the request, VISAS, which does not exceed the time remaining until the expiration of the waiting time service request with the lowest priority number, that is, satisfying the inequality

Tabout.ji< Tthe coolant.z, (2)

where Tabout.ji- VISAS i-th subscriber, where i= z+1, z+2, . . . , N; j= 1,2, . . . M - the number of the group of queries;

Tthe coolant.z- the time interval remaining until the expiration of the maximum waiting time service request in the queue of the second order,

the maintenance unit generates computing system code AB, in which is found the query, then the system allocates the requested resource. If multiple requests that satisfy the inequality (2), computing resource will be allocated for the request with the lowest priority number.

In the case when one or more of the requests reach the maximum wait time in queue of the second order, in the device service requests organized the first order of the requests that exceed the maximum waiting time of service) (see Fig. 3). Moreover, requests from the very. Fig. 3). This priority of service have requests from the queue of the first order. From the queue of the first order queries are retrieved in accordance with the priorities.

For example, at the initial moment of time t1(see Fig. 4A) in the system are 4 request and received signal computing system about the release of the resource. The highest priority has the query 1 (minimum priority). In addition, in the device are query 3, whose demand computing resource can be met over the period of time remaining to request 1 before the expiration of the maximum time-out (Tabout.j3< Tthe coolant.1and the query 1 will not be considered late. The resource will be allocated for the request 3. After the resource release request 3, at time t2a(see Fig. 5A), the resource will be allocated for the request 1, as it has the lowest priority number in the device there is no query that satisfy the condition (2). After the liberation of the resource request 1 at time t3A(see Fig. 6A), the resource will be allocated for the request 4, as by this point in time, the maximum waiting time service request 4 in the queue of the second order exceeded the value of Tthe coolant.4and the request is transferred to an account selected request 2.

The sequence of service requests when using the prototype method is as follows. At the initial moment of time t1the resource will be allocated for the request 1 (see Fig. 4B). At time t2Bthe resource will be allocated for the request 2 (see Fig. 5B). Next, at time t3band t4Bthe resource will be allocated to requests 4 and 3, respectively, because each of them to the corresponding moments of time has elapsed waiting time. As a result, queries 4 and 3 resource will be allocated with a considerable delay.

The claimed method of service differently prioritised requests provides a high probability of low-priority service requests by taking into account a maximum wait time of service requests in the queue of the second order, as well as reducing the time spent in the request queue with small VISAS (compared with the method of the prototype) through use of an allowance of time remaining before the expiration of the maximum time-out service priority requests.

The validity of theoretical assumptions were tested using a simulation model of the computing system, when the exponential distribution law of receipt of service requests. The result is smoreno three priority);

VIZ - time interval;

Tcf.- the average time spent by a request in the computing system (average service time);

- standard deviation;

P(TTsupplementary) is the probability of timely maintenance requests computing system;

Tcf.inaboutcharedi- average waiting time of a request for a resource of the computing system.

From the presented data it follows that the claimed method allows to increase the probability of timely services to low-priority requests to 3% by reducing the time spent in the request queue with small VISAS in 1.1-1.3 times in comparison with the method of the prototype, which indicates the possibility of achieving this technical result.

The device (Fig. 11) consists of a generator of clock pulses 2 and divider 3, N-Vodolaga of the element OR NOT 4, count 5, item And 6, the first inverter 7, a multiplexer 8, the decoder low level 11, the priority encoder 12, N-Vodolaga element AND-NOT 13, the second inverter 14, the selector-multiplexer 15, N subscriber units (AB) l1-lN(the diagram AB is shown in Fig. 12), block sampling and fixation (BWF) 91-9k(scheme is atora clock 2 is connected to the input of the divider 3 and the second input element And 6. The output of the divider 3 is connected to the clock inputs 20 AB. The first signal outputs 251-25NAB respectively connected to information inputs A1-ANmultiplexer 8, the output Y which is connected to the input of the first inverter 7 and to the input of the second inverter 14. The output of the first inverter 7 is connected to the first input element And 6 and to the control input 29 of each TO BWF. The output element And 6 connected to the counting input of the counter 5. The reset input R of the counter 5 is polling the input device 31. J information outputs Q1-QJcounter 5 is connected to the corresponding J inputs "Code subscriber" 27 BUF, corresponding to J control inputs V multiplexer 8 to the J inputs and1-ajthe first group of information inputs of the selector-multiplexer 15, and J information inputs X1-XJdecoder low level 11. The output of the second inverter 14 is connected to allows the input E of the selector-multiplexer 15 and is directly addressable by the output device 32. Query inputs 16 AB are the corresponding request from the input device. K-bit inputs 17 "Code maximum timeout" AB are the corresponding K-bit inputs 17 "Code maximum time-out" device.kalinago time care AB are the corresponding K-bit inputs 19 "Code maximum service time" of the device. Inverted inputs 28 of the priority encoder 12 is connected to the second signal output 28 AB 11-1Nwhen this connection is made as follows: 1-th inverted input of the priority encoder 12 is connected to the second signal output of the N-th AB, 2-th inverted input of the priority encoder 12 is connected to the second signal output N-1 AB, the n-th inverse input of the priority encoder 12 is connected to the second signal output (N+1)-n AB, and N-th inverse input of the priority encoder 12 is connected to the second signal output 1 AB. In addition, N inverted inputs 28 of the priority encoder 12 is connected to the respective N inputs N-Vodolaga element AND-NOT 13. Inverted outputs of the priority encoder 12 is connected to the corresponding J inputs of the second group of information inputs B1-BJselector-multiplexer 15. The output of element AND-NOT 13 connected to selectively input a V selector-multiplexer 15.

Outputs Y1-Yjselector-multiplexer 15 J are the corresponding outputs 33 "Code subject to the service subscriber devices. The outputs of the "Excess" 241-24NAB 11-1Nconnected to the corresponding inputs of the N-Vodolaga element AND-NOT 4. Output N-Vodolaga element AND N respectively to the inputs 221-22N"Comparison of AB. K-bit outputs 231-23NCode the remaining time-out" each of N AB is connected to N-bit inputs 301-30N"Bits of code remaining time-out" TO BWF, when this connection is made as follows: 1st grades K-bit outputs 231-23NCode the remaining time-out" each of N AB connected to the corresponding bits of the N-bit input 301"Bits of code remaining wait time" 1 BWF, 2nd grades K-bit outputs 231-23NCode the remaining time-out" each N AB connected to the corresponding bits of the N-bit input 302"Bits of code remaining time-out" 2nd BUF, m-th bits of the K-bit outputs 231-23NCode the remaining time-out" each of N AB connected to the corresponding bits of the N-bit input 30m"Bits of code remaining waiting time of the m-th BWF, the K-th bits of the K-bit outputs 231-23NCode the remaining time-out" each of N AB connected to the corresponding bits of the N-bit input 30K"Bits of code remaining waiting time of K-th BWF. Outputs 101-10K"The category is selected codh inputs 26 "the Selected code, the remaining time-out" each of N AB.

Clock 2 is designed to generate a synchronizing pulse and can be built by any known scheme. Cm. for example, C. L. Shyla. Popular TTL chips. - M. : ARGUS, 1993, S. 18.

The divider 3 is designed to increase the repetition period arriving at its input sequence of pulses. The specific value of the required division depends on the selected clock frequency clock pulse devices, as well as from a specified range of time lagsthe coolant.i. Implementation scheme of such a divider is known. In particular, the divider can be constructed on the counter. Cm. for example, p. P. Maltsev, N. C. Dolidze and other Digital integrated circuits. The Handbook. - M. : Radio and communication, 1994, S. 62-74. When the input divider is the counting input of the counter, and the output of the divider is one of the outputs of the counter.

The counter 5 is designed to account arriving at its counting input pulses and output the number in binary code. Cm. for example, p. P. Maltsev, N. C. Dolidze and other Digital integrated circuits. The Handbook. - M. : Radio and communication, 1994, S. 62-74.

The multiplexer 8 is used to alternately switching signal outputs 14 subscriber STW information and measuring equipment. The tutorial. -L. : LPI them. Kalinina, 1980, S. 70-72.

The decoder low level 11 is designed to convert arriving at its input binary code into a low-level signal on one of its outputs. Implementation scheme of the decoder low level is known. Cm. for example, p. P. Maltsev, N. C. Dolidze and other Digital integrated circuits. The Handbook. - M. : Radio and communication, 1994, S. 42-43.

The priority encoder 12 is designed to convert low-level signal on one of its inputs in binary code at its output, and the conversion is carried out taking into account the priorities of the signals corresponding to the numbers of inputs. The implementation of the priority encoder is known. Cm. for example, p. P. Maltsev, N. C. Dolidze and other Digital integrated circuits. The Handbook. - M. : Radio and communication, 1994, S. 40.

The selector is a multiplexer 15 is designed for switching one of the two J-bit groups of input to output. Implementation scheme of such a selector-multiplexer known. Cm. for example, p. P. Maltsev, N. C. Dolidze and other Digital integrated circuits. The Handbook. - M. : Radio and communication, 1994, S. 36.

Subscriber units 11-1Ndesigned for the admission control signals queries on the data requests, generate control signals to an extraordinary service requests based on the comparison result, and control signals on the priority boost after the set timeout for each request.

The subscriber unit may be implemented in various ways. In particular, his scheme shown in Fig. 12, contains the element And 1.1, item, OR 1.2, the inverter 1.3, counter 1.4, trekhgolovy element And 1.5, the comparator 1.6, trekhgolovy element AND NOT 1.7.

The first input element And 1.1 (see Fig. 12) connected to the inverted enable input of the account counter 1.4, with a second input Tregubova element And 1.5 and is a challenge entry 16 AB. K information inputs1-DKcounter 1,4 are K-bit input 17 "Code maximum timeout" AB. Input reset R counter 1.4 is the entrance 18 "Zeroing" AB. The counting input of the counter 1.4 is connected to the output Tregubova element And 1.5, the inverted output of counter overflow 1.4 connected to the first input Tregubova element And 1.5 and to the inverter input 1.3. The third entrance Tregubova element And 1.5 is a clock input 20 AB. The inverter output 1.3 is connected to the second input element OR 1.2 and is output 24 "Excess" is a OR 1.2 and to the first input of Tregubova item AND NOT 1.7. The output element OR 1.2 is the first signal output 25 AB. Information outputs Q1-OKcounter 1.4 are K-bit output 23 of the Code of the remaining time-out" AB. To inputs B1INKthe second group of information inputs of the comparator 1.6 are K-bit input 19 "Code maximum time care AB. To inputs AND1-AKthe first group of information inputs of the comparator 1.6 are K-bit input 26 "the Selected code, the remaining time-out" AB. Output "<" comparator 1.6 connected to the second input Tregubova item AND NOT 1.7. The third entrance Tregubova item AND NOT 1.7 is the entrance 22 "Resolution comparison of AB. Output Tregubova item AND NOT 1.7 is the second signal output 28 AB.

Counter 1.4 is designed to account arriving at its input pulses (the pulses), the formation of the result of counting in binary code, the generation of the control signal defined by the code of the initial fill to the inputs D and the repetition period of the clock pulses, there is a configurable timer. Job description and diagram of this counter is known and described, for example, in the book: p. P. Maltsev, N. C. Dolidze and other Digital integrated Mich codes two groups of K-bit inputs and generate comparison results. Job description and diagram of the comparator is shown, for example, in the book: C. L. Shyla Popular TTL chips. - M. : ARGUS, 1993, S. 183-184.

Blocks sampling and fixation 91-9Kdesigned to highlight bits of code remaining time-out for the selected query and their fixation for subsequent comparison in AB.

BWF can be implemented in various ways. In particular, his scheme shown in Fig. 13, contains a multiplexer 9.1 and D-trigger 9.2.

N information inputs a1-anmultiplexer 9.1 (see Fig. 13) are the N-bit input 30 "Digits code the remaining time-out" BWF. J address inputs V multiplexer 9.1 J are the corresponding inputs 27 "Code caller BWF. The output Y of the multiplexer 9.1 is connected with the information input D of D-flip-flop 9.2. The control input of D-flip-flop 9.2 is a control input 29 BWF. The output of D-flip-flop 9.2 is the output 10 "Discharge of the selected code the remaining time-out" BFF.

The multiplexer 9.1 is intended for switching of one of the N inputs to its output. The implementation of such a multiplexer is known. Cm. for example, in the book: p. P. Maltsev, N. C. Dolidze and other Digital integrated circuits. The Handbook. - M. : Radio St entrance. Cm. for example, in the book: p. P. Maltsev, N. C. Dolidze and other Digital integrated circuits. The Handbook. - M. : Radio and communication, 1994, S. 50-51.

The device operates as follows. In the initial period of operation, when the service request is not received, request inputs 161-16NAB 11-1N(see Fig. 11) are set to low logic levels. The pulses received from the clock pulses 2 through the opened item And 6 at the counting input of the counter 5, the outputs of which edge of each clock pulse sequentially shift code combinations that are non-AB binary J-bit code (2J= N). Code combination from the output of the counter 5 are received at the address input of the fifth multiplexer 8, alternately commuting on the output Y of the multiplexer 8, the signals from the first signal outputs 251-25NAB 11-lNin the sequence determined by their priorities (i.e. top-down). To permit the output device 32 is set to high logic level.

When a request for a group of inputs 171-17NCode maximum wait time" for informational inputs D1-DKcounter 1.4 AB receives K-bit code maximally code which is in addition to the maximum number representable in K-bit code. The group of inputs 19 "Maximum service time" for informational inputs b1-bkcomparator 1.6 corresponding AB receives K-bit code VISA. Lowest VISAS meets most code that is in addition to the maximum number representable in K-bit code. Then query the input 16 of the corresponding AB established a high level. While at the signal output 25 AB will be high level (through the open item 1.1 and item OR 1.2). At the counting input of the counter 1.4 corresponding AB receives pulses from the clock 2 chain: the divider 3, the clock input 20 AB, outdoor trekhgolovy element And 1.5 AB. Counter 1.4 AB acts as a timer which is triggered after a certain time interval (upon reaching the overflow).

On the K-bit outputs 231-23NCode the remaining time-out" AB receives the current values of the counters 1.41-1.4Nwith outputs Q1-QK. The discharge current counter values received on N-bit inputs 301-30K"Bits of code remaining time-out" BWF, however understand there are m-th bit of the K-bit output 23 of the Code of the remaining time-out" (where m = 1,2, . . . To) the n-th AB is supplied to the n-th bit (where n= 1, 2, . . . N) N-bit sign-30 "Discharge code the remaining waiting time of the m-th block fetch and commit.

With the release of the resource of the computing system generates a pulse of high level is supplied to poll the input device 31, when this occurs, the counter 5. Next, upon receipt of clock pulses from clock 2 at the counting input of the counter 5 is scanned by the multiplexer 8 signal outputs 251-25NAB in priority order (top to bottom), as well as alternate switching of the discharge current values code the remaining waiting time of query inputs 301-30NBWF to outputs 101-10KBWF chain: informational inputs A1-ANmultiplexers 9.11-9.1Kinformation outputs Y multiplexers 9.11-9.1Kinformation input D of the D flipflops 9.21-9.2Kinformation outputs of the D flipflops 9.21-9.2K.

Upon detection of the first counter a high level on the signal outputs 25 AB he switched to the output Y of the multiplexer 8. At the output of the inverter 7 is set to a low level backsyria at the output of the counter 5 code selected AB? and establishes a low level at the control input 29 BWF 91-9Kby translating thus D-flip-9.21-9.2KBWF 91-9Kin the mode information storage. At the outputs 101-10KBWF 91-9Kfixed current code value of the remaining waiting time of the request, contained in a selected AB, which receives the K-bit inputs 26 "the Selected code, the remaining time-out" AB 11-1Non the K-bit input group a Comparators 1.61-1.6Neach of the AB. In the Comparators 1.61-1.6Nall AB compares the current value of the remaining waiting time of the request, contained in a selected AB IDs VISA requests in other AB with lower priorities to identify one or more AB queries VISA which does not exceed the remaining query timeout in the selected AB. In that case, if AB is a request VISAS is less than the time remaining until the expiration of the maximum waiting time service request to the selected AB (i.e. "<", as compared codes, which is in addition to the maximum value representable in K-bit code), the output "<" comparator 1.6 formed a high signal, which when trekhgolovy e the outputs 28, only AB, in which there is no request signal to request the input 16 (trekhgolovy element AND NOT 1.7 closed low on the first entry), as well as in selected AB, because the third entrance Tregubova item AND NOT 1.7 selected AB filed low level signal from the corresponding output of the decoder low level 11. The decoder low level 11 allows to exclude from further consideration the result of comparing the remaining time-out request in the selected AB with his VISA. With the second signal outputs 28 AB signals to inverted inputs of the priority encoder 12, and the second signal output of the n-th AB is connected to the (N+1)-n-th inverted input of the priority encoder 12. The specified connection method of the second signal outputs 281-28NAB to the inputs of the priority encoder 12 is due to the fact that the outputs of the priority encoder 12 inverse, that is, to obtain at its output code AB with the lowest priority number should be cross-connected to its inputs in reverse order. The priority encoder 12 generates at its outputs code AB with the lowest priority number from the number of AB having a low level on the second signal output 28 (that is, from among the Bank, participating in the review). With inverted outputs of Chipata-multiplexer 15. At the same time to the J inputs A1-AJthe second group of information inputs of the selector-multiplexer 15 receives the code for the selected AB. In that case, if there is at least one of AB, which is a request signal, VISAS, which is less than the current timeout value of the query in the selected AB, input V selector-multiplexer 15 N-shadowy element AND-NOT 13 will be set to a high signal. When this selector is a multiplexer 15 switches on the outputs 33 of the Code subject to the service subscriber devices code AB installed on a group of inputs b1INJ. Otherwise, the selector-multiplexer 15 switches on the outputs 33 of the Code subject to the service subscriber devices code AB installed on a group of inputs A1-AJ. Signal permitting the operation of the selector-multiplexer 15 is a low level signal to an enabling input E input through the second inverter 14 from the output Y of the multiplexer 8. Simultaneously, the low level signal from the output of the second inverter 14 is permissive signal computing system for reading code AB subject to maintenance. The second inverter 14 is selected so that the delay time of the signal it was not less than the time the pic is a new item AND NOT 1.7 AB, the priority encoder 12.

If one or more queries in the current queue has reached the maximum waiting time is their priority service. When the maximum waiting time at the inverse output of the counter overflow 1.4 set low level, which locks trekhgolovy element And 1.5, preventing the flow of clock pulses to the counting input of the counter 1.4. Switches the inverter 1.3 and its output level is set to high. The high level with the release of "Excess" 24 this AB switches N-shadowy the element OR NOT 4 and inlets 21 "Ban" all AB is set to the low level signal. As a result, the output of the element And 1.1 all AB is set to the low level signal which locks trehochkovye elements AND NOT 1.7. The high level on the first signal outputs 25 AB will only requests that have reached the maximum wait time, and the second signal outputs 28 all AB will be set at a high level. As a result, the selective input a V selector-multiplexer 15 N-shadowy element AND-NOT 13 will be set to the low level, the switching at the outputs 33 of the Code subject to the service subscriber" s outputs 25 AB counter 5 will be selected AB, with the highest priority from among the AB with the requests that have reached the maximum wait time. After executing a query with an expired timeout is reset 1.4 AB input "Reset" 18 that will establish a high level at the output of the counter 1.4, thereby establishing the output "Excess" 24 low level that will allow the device after execution of all requests that have timed out go to service newly received or waiting requests in the order determined by the logic device.

1. The method of servicing the customer computing system, namely, that form codes maximum waiting time service request Tthe coolant.iwhere i = 1,2, . . . N - the corresponding priority number of the i-th subscriber, and N is the total number of subscribers, memorize them, form the pings, organize signal requests the turn of the second order in accordance with the non-priority callers from the queue of the second order are transferred to the queue of the first order requests that have reached the maximum waiting time at the position corresponding to the numbers of their priorities, consistently serve the requests from the queue first is of the order service request from the queue of the second order, characterized in that simultaneously with the formation of codes a maximum wait time of service requests additional form M, where M 2, codes maximum, differing in the duration of time intervals Taboutenough to service requests, and service requests from the queue of the second order pre-compare the time interval Texp.minremaining to timeout service the request with the minimum priority number, with the maximum time intervals Taboutother requests from the queue of the second order and if there are requests, Taboutless than Texp.minserve from among the request with the lowest priority number, and if no service request from the queue of the second order with minimum priority number, and compare Texp.minand Taboutand serve the requests from the queue of the second order as long as there are no requests in the queue of the first order.

2. The device service requests of subscribers of a computer system containing N subscriber units, where N 2, counter counter counter input coupled to the output element And Veen clock inputs of the N subscriber units, query inputs and K-bit input Code, the maximum time-out", where the 2 - bit code maximum waiting time service request N subscriber units are appropriate request inputs and K-bit input Code, the maximum time-out" device, N-shadowy the element OR NOT, the N inputs of which are connected to the outputs of the "Excess" of the corresponding N subscriber units, and the output of the N-Vodolaga item OR IS NOT connected to the inputs of the "Ban" N subscriber units, multiplexer, N information input of which is connected with the first signal outputs corresponding to N subscriber units, and its J, where J = ]log2N[, address input connected to the corresponding J outputs a Code subscriber" counter, the output of the multiplexer is connected to the input of the first inverter, the output of the first inverter connected to the first input element And the reset input of the counter is polled input device, and inputs "Zeroing" N subscriber units are relevant inputs to "zero" the device, characterized in that additionally introduced selector-multiplexer, J information inputs of the first group which are connected to the corresponding J outputs a Code subscriber" counter, J outputs CE is a, a second inverter, whose input is connected to the input of the first inverter, and the output - allows the input of the selector is a multiplexer and is at the same time permitting the output device, the priority encoder, the n-th inverse input of which, where n = 1,2. . . , N, is connected to the second signal output (N+1) is the n-th subscriber unit, J inverse outputs of the priority encoder connected to the J inputs of the second group of inputs of the selector-multiplexer, N-shadowy element AND-NOT, N input of which is connected to the corresponding N inverse inputs of the priority encoder, and the output of the N-Vodolaga item AND IS NOT connected to the control input of the selector-multiplexer, decoder low level, the J input of which is connected to the corresponding J outputs a Code subscriber" counter, N inverse outputs of the decoder low level is connected to the inputs allowing a comparison of the respective N subscriber units, To units of sampling and fixation, where the K - bit code the remaining waiting time of the J inputs of the "Code of the subscriber" each of which is connected to the corresponding outputs of the "Code of the subscriber" counter, m-th bit, where m = 1,2. . . , K, K-bit output Code the remaining time-out" of the n-th subscriber unit connected to the n-th digit of the N-RA the CSOs from To units sampling and fixation connected to the output of the first inverter, outputs the Discharge of the selected code the remaining time-out" To block sampling and fixation connected to the corresponding bits of the K-bit inputs the Selected code, the remaining time-out" each of the N subscriber units, each subscriber unit is provided in addition To the-bit input Code maximum service time", which is also the K-bit input Code maximum service time" of the device.

3. The device according to p. 2, wherein the subscriber unit comprises a counter, inverted entry permit account which is desirable entrance subscriber unit and connected to the first input element And To the information inputs of the counter are K-bit input Code maximum wait time" subscriber unit, and the reset input of the counter is input to "zero" the subscriber unit, the inverted output of the counter is connected to the first input Tregubova element And the input of the inverter, the inverter output is connected to the second input of the OR element, and is the output of "Excess" subscriber unit, the second input Tregubova element And connected to the first input element And the second input element And an entry "Ban" subscriber unit is connected to the counting input of the counter, the output element And is connected to the first input of the OR element and the first input Tregubova element AND-NOT, and the output element OR is the first signal output, the subscriber unit, the second input Tregubova item AND IS NOT connected to the comparator output, the first and second groups of inputs To inputs of each of which are respectively K-bit input "Selected code, the remaining time-out" and the K-bit input Code, the maximum time of service of the subscriber unit, and a third input Tregubova element AND IS NOT an entry Permit comparison of the subscriber unit, output Tregubova item AND NOT a second signal output, the subscriber unit To the outputs of the counter are respectively the K-bit output Code the remaining time-out" subscriber unit.

4. The device under item 2 or 3, characterized in that the unit of sampling and fixation consists of multiplexer, N information inputs which are N-bit input Bits code the remaining time-out" block sampling and fixation, and J address inputs of the multiplexer are the J inputs "Code subscriber unit sampling and fixation, D-trigger information whose input is connected to the output of multiplexes out the Discharge of the selected code the remaining time-out" block sampling and fixation.

 

Same patents:

The invention relates to computer technology and can be used for priority service requests

The invention relates to computer technology and can be used in devices for servicing customer requests with different priorities, with the distribution of the flow of information through communication lines

The invention relates to computing and can be used in devices of series-parallel service requests of subscribers with a variable distribution of the flow of information through communication lines

The invention relates to computer technology and may find application in fault-tolerant multiprocessor systems for load balancing between processors during faults

The invention relates to a corresponding system, that is able to work in real time and is tolerant to errors system for signal processing, with many blocks of data that are connected to each other through the blocks of data

The invention relates to the field of computer engineering and can be applied in communication systems

The invention relates to a method of congestion control messages elementary program in the electronic switching system

The invention relates to computer technology and is intended for use in a local area network with bus topology to control the transmission of data packets through a common channel

The invention relates to computing and can be used to provide machine-to-machine exchange in distributed computer systems and computer networks

FIELD: computer science.

SUBSTANCE: device has n-byte query register, query limits location systems, each of which consists of counting timer and OR element, OR element, AND element, keys cascade.

EFFECT: higher reliability and speed of operation.

1 dwg

FIELD: method and device for processing data for preserving recurrent status in data processing device.

SUBSTANCE: device has data processing block, having multiple functioning modes, for each of which special memory stack is present. Method describes operation of this device. Data carrier contains program, configuring data processing device for performing stages of method.

EFFECT: decreased size of code and decreased interruption processing delay.

3 cl, 16 dwg

FIELD: engineering of information processing systems.

SUBSTANCE: system contains master-system for processing information, interface, central communication device, client system for processing information, object model. In accordance to method each master system sends to central communication device elements of its data array determined in appropriate master-representation, while in master-representation of connected master system elements of data array are contained, for which system has data priority.

EFFECT: simplified specification and development of interfaces between technical applications.

2 cl, 6 dwg

FIELD: engineering of interrupt processing mechanisms in computer systems.

SUBSTANCE: system contains processor with multiple contexts for execution of commands stored in memory. In response to common interrupt logical processors of processor with multiple contexts compete for receiving access to jointly utilized register. First logical processor gaining access to aforementioned jointly utilized register processes common interrupt. Remaining logical processors return from interrupt.

EFFECT: increased productiveness of system.

4 cl, 5 dwg

FIELD: computer engineering, possible use in data exchange systems and local computing networks.

SUBSTANCE: device contains N≥2 client blocks, clock impulse generator, N client time controllers, OR element, AND-NOT element, selector-multiplexer, two N-input AND-NOT elements, two priority encoders, main wait time controller.

EFFECT: increased probability of timely servicing of clients under conditions of real functioning process of data exchange systems, with continuous dynamics of change of modes of different priority requests from clients.

4 cl, 7 dwg

FIELD: engineering of computers for controlling memory, in particular, external memory controllers.

SUBSTANCE: memory control device for operation in memory controller network contains memory controller being an owner unit, capable of controlling the blocking of certain data area during execution of input-output outputs, and component for exchanging messages, providing for transmission of at least one message with blocking request, permission of blocking, blocking removal request and blocking removal signal, and also input-output component, while any image of aforementioned data area, received by instant copying thereof, is maintained as coherent relatively to data area itself, and input-output component may position previous direct confirmation, that this data area remains coherent to any such image, to cash-memory, and may perform input-output operations on basis of aforementioned previous direct confirmation. Method describes operation of aforementioned device. Software product for computer is realized on machine-readable carrier and contains a program recorded thereon, realizing operations of aforementioned method.

EFFECT: expanded functional capabilities.

3 cl, 3 dwg

FIELD: engineering of means for pausing execution of a stream until certain memory access occurs.

SUBSTANCE: in one variant of realization, processor contains a set of executive devices, capable of executing a set of streams. First stream includes a command, which determines the address being tracked. Logical pausing means pause execution of first stream, and monitor causes renewal of first flow as reaction to access of given address being tracked.

EFFECT: increased processor productiveness.

5 cl, 14 dwg

FIELD: methods for automatic execution of a program, connected to data file, when data file and program being executed are positioned on different computer units.

SUBSTANCE: in methods, program being executed is accessed through graphic image of data file type, realized in the network, which includes client system and a set of server systems. Client system receives the scheme, which determines connection between the set of programs being executed and corresponding set of data file types. Graphic image of data files is displayed, information about selection of graphic image of data file is received from server system, on basis of it program to be executed is selected and executed.

EFFECT: increased productivity of system due to distributed execution of programs.

9 cl, 19 dwg, 3 tbl

FIELD: method and system for providing user interface information to client.

SUBSTANCE: in accordance to the invention, access system contains registration mechanism. Client environment for automatic processing of user interface receives registration information from the client and transmits user interface information after receipt. Server for automatic processing of user interface receives registration information from client environment for automatic processing of user interface and notifies processor of user interface about registration, and also receives user interface information from user interface processor. The server contains filtration device for filtering out information of no interest to client, and notification device for notifying the client about information which is of interest to the client.

EFFECT: ensured capacity for filtration and coordination of excessive and disorienting notifications.

2 cl, 11 dwg

FIELD: telecommunications.

SUBSTANCE: device contains a set of central processor units, which are assigned a common external up address in telecommunication network which allows packet data. IP messages, addressed to a network element, are received, and received IP messages which contain first messages are identified. First value is identified in first message and first message is transmitted to central processor unit on basis of identified first value, if identified first value is not equal to zero.

EFFECT: ensured load balancing for central processor when using several types of traffic.

3 cl, 3 dwg

FIELD: technology for distribution of limited resource between multiple users.

SUBSTANCE: in system including shared resource, coefficients of load on resource by users are controlled with consideration of stability vectors, characterizing probability of resource use by one or another user. Aforementioned control allows to prevent resource overloading situations. Also described are system and method, wherein load coefficients are selected from multiple accessible coefficients in accordance to multiple user stability vectors of shared resource.

EFFECT: division of assumed resource capacity on a row of parcels with fixed coefficient to provide for optimal use of shared resource.

5 cl, 9 dwg

Up!