Smo with failures and mutual assistance between channels. Classification of queuing systems
Computer science, cybernetics and programming
A queuing system with n queuing channels receives a Poisson flow of requests with intensity λ. The intensity of the application service by each channel. After the end of the service, all channels are released. The behavior of such a queuing system can be described by a Markov random process t, which is the number of customers in the system.
2. QS with failures and full mutual assistance for mass flows. Graph, system of equations, calculated ratios.
Formulation of the problem.A queuing system with n queuing channels receives a Poisson flow of requests with intensity λ. The intensity of servicing the request by each channel is µ. The request is served by all channels simultaneously. After the end of the service, all channels are released. If a newly arrived request finds a request, it is also accepted for service. Some channels continue to serve the first request, while the rest - a new one. If the system is already serving n requests, then the newly arrived request is rejected. The behavior of such a queuing system can be described by a Markov random process ξ(t), which is the number of customers in the system.
Possible states of this process are E = (0, 1, . . . , n). Let us find the characteristics of the considered QS in the stationary mode.
The graph corresponding to the process under consideration is shown in Figure 1.
Rice. 1. QS with failures and complete mutual assistance for Poisson flows
We compose a system of algebraic equations:
The solution of this system has the form:
Here χ =λ/nµ is the average number of requests entering the system during the average service time of one request by all channels.
Characteristics of a multi-channel queuing system with failures and full mutual assistance between channels.
1. Probability of denial of service (probability that all channels are busy):
2. Probability of servicing an application (relative throughput of the system):
As well as other works that may interest you |
|||
| 32353. | Methods of legal regulation (authoritarian and autonomous) methods of legal influence. Modern trends in the development of ways and methods of legal regulation in Russian law | 37KB | |
| Methods of legal regulation authoritarian and autonomous methods of legal influence. Modern trends in the development of ways and methods of legal regulation in Russian law. Legal science distinguishes between the concepts of legal influence and legal regulation. Nevertheless, it is necessary to distinguish between strictly defined means of legal influence on social relations, specially designed for their direct regulation. | |||
| 32354. | The concept of legal consciousness. The structure of legal consciousness | 30KB | |
| Legal consciousness is a set of ideas and feelings expressing the attitude of people of social communities of classes of nations of the people to the current and desired law. Being a subjective reaction of a person to legal reality, legal consciousness, on the one hand, represents a form of social consciousness along with moral, political, religious, aesthetic, etc. Law and legal consciousness are inextricably linked. Alekseev legal consciousness is an inevitable companion of law. | |||
| 32355. | Pedagogical activity, its structure and specificity. Teacher personality requirements | 16.92KB | |
| Requirements for the personality of the teacher. The content is determined by social factors, the place and function of the teacher in society, society's requirements for the teacher and socio-psychological factors, the expectations of those around them, public expectations and attitudes. Communicative establishment and maintenance of relations with students, parents, administration, teachers. The teacher must know and take into account the characteristics of the student that hinder or help him, and accordingly respond to them, the slowness of the student associated with his temperament requires patience and tact ... | |||
| 32356. | Psychological foundations of learning. Teaching as a process and activity. Basic learning models | 17.22KB | |
| Basic learning models. Teaching as an organized process is a side of learning and is a product of learning activity. Learning components: Target goals and objectives Content of the curriculum Activity activities of the teacher and students Effective assessment of self-assessment Learning functions: Educational assimilation of ZUNs Educational value attitude to the world Developing the establishment of the relationship between phenomena and factors Learning purposeful cognitive activity of students aimed at mastering them ... | |||
| 32357. | General concept of temperament. Properties and types of temperament, their manifestation in activity and behavior | 16.91KB | |
| Temperament is the innate individual characteristics of a person that determine the dynamic characteristics of the intensity and speed of response, the degree of emotional excitability and balance, the features of adaptation to the environment. They determine the dynamics of various human activities, play, educational, labor, recreational: Reactivity is the degree of involuntary reactions of a person to external or internal influences of the same strength. Plasticity, ease, flexibility and speed of adaptation of a person to changing external ... | |||
| 32358. | Self-consciousness of the individual. The structure of self-consciousness. The development of self-consciousness in ontogenesis | 18.56KB | |
| Thus, self-consciousness includes: Self-knowledge intellectual aspects of self-knowledge Self-attitude emotional attitude towards oneself In general, three layers of human consciousness can be distinguished: Attitude towards oneself Expectation of other people's attitude towards oneself attribute projection Attitude towards other people: egocentric level of relations if they help me then they are good people group-centric level if he belongs to my group then he is a good pro-social level do to others as you would like to be done to you... | |||
| 32359. | General concepts of character. Character structure. Character typology | 13.96KB | |
| Character structure. Typology of character. In the structure of the personality of character, it occupies a central place, combining all other properties and behavioral features: Influences cognitive processes On emotional life On motivation and will Determines the individuality and originality of the personality The character of a person is an alloy of innate properties of higher nervous activity with individual traits acquired throughout life. Character structure: Traits expressing the orientation of the personality, stable needs of installation, interests, inclinations, ideals, goals ... | |||
| 32360. | Group and joint activities. Factors of effectiveness of group and joint activities | 15.38KB | |
| Factors of effectiveness of group and joint activities. Compatibility The ability of group members to work together. Types of compatibility: Psychophysiological certain similarity of characteristics of people and, on this basis, the consistency of their emotional and behavioral reactions, synchronization of the pace of joint activities. Evaluation criteria: Performance results. | |||
| 32361. | Psychological readiness of the child for school. Methods for diagnosing psychological readiness for schooling | 13.85KB | |
| The psychological readiness of the child for schooling is the necessary and sufficient level of mental development of the child for mastering the school curriculum in the conditions of learning in a group of peers. The structure of the component: Psychomatory readiness balance of the processes of excitation and inhibition, which allows the child to focus his attention for a longer time, contributes to the formation of arbitrary forms of behavior and cognitive processes; the development of small muscles of the hand and hand-eye coordination, which creates ... | |||
| Classification features | Varieties of queuing systems | |||||||||||
| Incoming demand flow | Limited requirements | Closed | open | |||||||||
| distribution law | Systems with a specific law of distribution of the incoming flow: exponential, Erlang k order, palm, normal, etc. | |||||||||||
| Turn | Queue discipline | With ordered queue | With an unordered queue | Service Priority | ||||||||
| Waiting Service Limits | With rejections | With unlimited waiting | Restricted (mixed) | |||||||||
| By queue length | Waiting time in queue | By time of stay in SMO | Combined | |||||||||
| Service discipline | Service stages | single phase | Polyphase | |||||||||
| Number of service channels | single channel | Multichannel | ||||||||||
| With equal channels | With unequal channels | |||||||||||
| Reliability of service channels | With absolutely reliable channels | With unreliable channels | ||||||||||
| No recovery | With recovery | |||||||||||
| Mutual Aid Channels | without mutual aid | With mutual help | ||||||||||
| Service reliability | With mistakes | Without mistakes | ||||||||||
| Service Time Distribution | Systems with a specific service time distribution law: deterministic, exponential, normal, etc. | |||||||||||
If the service is performed in stages by some sequence of channels, then such a QS is called multiphase.
AT CMO with "mutual assistance" between channels, the same request can be served simultaneously by two or more channels. For example, the same failed machine can serve two workers at once. Such "mutual assistance" between channels can take place both in open and closed QS.
AT CMO with errors an application accepted for service in the system is serviced not with full probability, but with some probability ; in other words, service errors may occur, the result of which is that some applications that went to the QS and supposedly “served” actually remain unserved due to “marriage” in the work of the QS.
Examples of such systems are: information desks, sometimes giving incorrect information and instructions; a corrector that can miss an error or correct it incorrectly; telephone exchange, sometimes connecting the subscriber to the wrong number; trading and intermediary firms that do not always fulfill their obligations with high quality and on time, etc.
To analyze the process occurring in a QS, it is essential to know basic system parameters: the number of channels , the intensity of the flow of applications , the performance of each channel (the average number of applications served per unit time by the channel), the conditions for the formation of the queue, the intensity of the departure of applications from the queue or system.
The relation is called system load factor. Often only such systems are considered in which .
Service time in QS can be both random and non-random. In practice, this time is most often taken as distributed according to the exponential law, .
The main characteristics of the QS depend relatively little on the type of service time distribution law, but mainly depend on the average value . Therefore, it is often assumed that the service time is distributed according to an exponential law.
The assumptions about the Poisson nature of the flow of requests and the exponential distribution of service time (which we will assume from now on) are valuable because they allow us to apply the apparatus of so-called Markov random processes in the theory of queuing.
The effectiveness of service systems, depending on the conditions of the tasks and objectives of the study, can be characterized by a large number of different quantitative indicators.
The most commonly used are the following indicators:
1. The probability that the channels are busy with the service is .
A special case is the probability that all channels are free.
2. The probability of refusal of the application in service.
3. The average number of busy channels characterizes the degree of system load.
4. Average number of channels free of service:
5. Coefficient (probability) of idle channels.
6. Equipment load factor (probability of busy channels)
7. Relative throughput - the average share of incoming requests served by the system, i.e. the ratio of the average number of requests serviced by the system per unit of time to the average number of requests received during this time.
8. Absolute throughput, i.e. the number of applications (requirements) that the system can serve per unit of time:
9. Average channel idle time
For systems with expectation additional features are used:
10. Average waiting time for requests in the queue.
11. Average residence time of an application in the CMO.
12. Average queue length.
13. Average number of applications in the service sector (in CMOs)
14. Probability that the time the application stays in the queue will not last more than a certain time.
15. The probability that the number of requests in the queue waiting to start service is greater than some number.
In addition to the listed criteria, when evaluating the effectiveness of systems, cost indicators:
– the cost of servicing each requirement in the system;
– the cost of losses associated with waiting per unit of time;
– the cost of losses associated with the departure of requirements from the system;
is the cost of operating the system channel per unit of time;
is the cost per unit of downtime for the channel.
When choosing the optimal system parameters for economic indicators, you can use the following loss cost function:
a) for systems with unlimited waiting
Where is the time interval;
b) for systems with failures ;
c) for mixed systems.
Options that provide for the construction (commissioning) of new elements of the system (for example, service channels) are usually compared at reduced costs.
The reduced costs for each option are the sum of current costs (cost) and capital investments, reduced to the same dimension in accordance with the efficiency standard, for example:
(given costs per year);
(given costs for the payback period),
where - current costs (cost) for each option, p.;
- industry normative coefficient of economic efficiency of capital investments (usually = 0.15 - 0.25);
– capital investments for each option, p.;
is the standard payback period for capital investments, years.
The expression is the sum of current and capital costs for a certain period. They are called given, since they refer to a fixed period of time (in this case, to the standard payback period).
Indicators and can be used both in the form of the sum of capital investments and the cost of finished products, and in the form specific capital investments per unit of production and unit cost of production.
To describe a random process occurring in a system with discrete states , state probabilities are often used, where is the probability that at the moment the system will be in the state .
It's obvious that .
If a process occurring in a system with discrete states and continuous time is Markovian, then for the probabilities of states it is possible to compose a system of linear Kolmogorov differential equations.
If there is a labeled graph of states (Fig. 4.3) (here, above each arrow leading from state to state, the intensity of the flow of events is indicated, transferring the system from state to state along this arrow), then the system of differential equations for probabilities can be immediately written using the following simple rule.
On the left side of each equation there is a derivative, and on the right side there are as many members as the arrows are directly related to this state; if the arrow points in
If all flows of events that transfer the system from state to state are stationary, the total number of states is finite and there are no states without exit, then the limit mode exists and is characterized by marginal probabilities .
Formulation of the problem. At the entrance n-channel QS receives the simplest flow of requests with density λ. The density of the simplest service flow of each channel is equal to μ. If a request received for service finds all channels free, then it is accepted for service and serviced simultaneously l channels ( l < n). In this case, the service flow of one request will have an intensity l.
If a request received for servicing finds one request in the system, then n ≥ 2l newly arrived application will be accepted for service and will be serviced simultaneously l channels.
If an application received for servicing finds in the system i applications ( i= 0,1, ...), while ( i+ 1)l≤ n, then the received request will be serviced l channels with a total capacity l. If a newly received application finds in the system j requests, and two inequalities are simultaneously satisfied: ( j + 1)l > n and j < n, then the application will be accepted for service. In this case, some applications can be served l channels, the other part smaller than l, number of channels, but all n channels that are randomly distributed among the applications. If a newly received application is found in the system n applications, it is rejected and will not be served. An application that has been serviced is serviced to the end (applications are "patient").
The state graph of such a system is shown in Fig. 3.8.
Rice. 3.8. QS state graph with failures and partial
mutual assistance between channels
Note that the state graph of the system up to the state x h coincides with the state graph of the classical queuing system with failures, shown in Fig. 2, up to the notation of the flow parameters. 3.6.
Consequently,
(i
= 0, 1, ..., h).
Graph of system states, starting from the state x h and ending with the state x n, coincides up to notation with the state graph of QS with full mutual assistance, shown in Fig. 3.7. In this way,
.
We introduce the notation λ / lμ = ρ l ; λ / nμ = χ, then
Taking into account the normalized condition, we obtain
To shorten further notation, we introduce the notation
Find the characteristics of the system.
Application Service Probability
The average number of applications in the system,
Average Busy Channels
.
Probability that a particular channel will be busy
.
The probability of occupancy of all channels of the system
3.4.4. Queuing systems with failures and inhomogeneous flows
Formulation of the problem. At the entrance n-channel QS receives an inhomogeneous elementary flow with a total intensity λ Σ , and
λ Σ
=
,
where λ i- the intensity of applications in i-m source.
Since the flow of requests is considered as a superposition of requirements from various sources, the combined flow with sufficient accuracy for practice can be considered Poisson for N = 5...20 and λ i ≈ λ i +1 (i1,N). The service intensity of one device is distributed according to the exponential law and is equal to μ = 1/ t. Servicing devices for servicing an application are connected in series, which is equivalent to increasing the service time by as many times as many devices are combined for servicing:
t obs = kt, μ obs = 1 / kt = μ/ k,
where t obs – request service time; k- the number of service devices; μ obs - the intensity of the application service.
Within the framework of the assumptions made in Chapter 2, we represent the QS state as a vector , where k m is the number of requests in the system, each of which is serviced m appliances; L = q max- q min +1 is the number of input streams.
Then the number of occupied and free devices ( n zan ( 
),n sv ( 
)) able 
is defined as follows:
Out of state 
the system can go to any other state 
. Since the system has L input streams, then from each state it is potentially possible L direct transitions. However, due to the limited resources of the system, not all of these transitions are feasible. Let the QS be in the state 
and an application arrives requiring m appliances. If a m≤ n sv ( 
), then the request is accepted for service and the system goes into a state with intensity λ m. If the application requires more devices than there are free ones, then it will receive a denial of service, and the QS will remain in the state 
. If able 
there are applications requiring m devices, then each of them is serviced with intensity m, and the total intensity of servicing such requests (μ m) is defined as μ m
= k m μ
/ m. When the service of one of the requests is completed, the system will go into a state in which the corresponding coordinate has a value one less than in the state 
,
=, i.e. reverse transition will occur. On fig. 3.9 shows an example of a QS vector model for n
= 3, L
= 3, q min = 1, q max=3, P(m) = 1/3, λ Σ = λ, the intensity of instrument maintenance is μ.
Rice. 3.9. An example of a QS vector model graph with denial of service
So every state 
characterized by the number of serviced requests of a certain type. For example, in a state 
one claim is serviced by one device and one claim by two devices. In this state, all devices are busy, therefore, only reverse transitions are possible (the arrival of any customer in this state leads to a denial of service). If the service of the request of the first type ended earlier, the system will switch to the state 
(0,1,0) with intensity μ, but if the service of the second type of request ended earlier, then the system will go into the state 
(0,1,0) with intensity μ/2.
A system of linear algebraic equations is compiled from the graph of states with applied transition intensities. From the solution of these equations, the probabilities are found R(
), by which the QS characteristic is determined.
Consider finding R otk (probability of denial of service).
,
where S is the number of graph states of the QS vector model; R(
) is the probability of the system being in the state 
.
The number of states according to is defined as follows:
,
(3.22)
;
Let us determine the number of states of the QS vector model according to (3.22) for the example shown in Fig. 3.9.
.
Consequently, S = 1 + 5 + 1 = 7.
To implement real requirements for service devices, a sufficiently large number of n
(40, ..., 50), and requests for the number of service devices of the application in practice lie in the range of 8–16. With such a ratio of instruments and requests, the proposed way of finding the probabilities becomes extremely cumbersome, since QS vector model has a large number of states S(50)
= 1790, S(60)
= 4676, S(70) = 11075, and the size of the matrix of coefficients of the system of algebraic equations is proportional to the square S, which requires a large amount of computer memory and a significant amount of computer time. The desire to reduce the amount of computation stimulated the search for recurrent computational possibilities R(
) based on multiplicative forms of representation of state probabilities. The paper presents an approach to the calculation R(
):
(3.23)
The use of the criterion of equivalence of the global and detailed balances of Markov chains proposed in the paper makes it possible to reduce the dimension of the problem and perform calculations on a medium-power computer using the recurrence of calculations. In addition, there is the possibility:
– calculate for any values n;
– speed up the calculation and reduce the cost of machine time.
Other characteristics of the system can be defined similarly.
System of equations
QS with failures for a random number of serving flows is a vector model for Poisson flows. Graph, system of equations.
Let us represent QS as a vector , where k m is the number of requests in the system, each of which is serviced m appliances; L= q max- q min +1 is the number of input streams.
If the request is accepted for service and the system goes into a state with intensity λ m.
When the service of one of the requests is completed, the system will go into a state in which the corresponding coordinate has a value one less than in the state , = , i.e. reverse transition will occur.
An example of a QS vector model for n = 3, L = 3, q min = 1, q max=3, P(m) = 1/3, λ Σ = λ, the intensity of instrument maintenance is μ.
A system of linear algebraic equations is compiled from the graph of states with applied transition intensities. From the solution of these equations, the probabilities are found R(), by which the QS characteristics are determined.
QS with an infinite queue for Poisson flows. Graph, system of equations, calculated ratios.
System Graph
System of equations
Where n– number of service channels, l– number of mutually assisting channels
QS with an infinite queue and partial mutual assistance for arbitrary flows. Graph, system of equations, calculated ratios.
System Graph
System of equations
–λ R 0 + nμ R 1 =0,
.………………
–(λ + nμ) P k+ λ P k –1 + nμ P k +1 =0 (k = 1,2, ... , n–1),
……………....
-(λ+ nμ) P n+ λ P n –1 + nμ P n+1=0,
……………….
-(λ+ nμ) Pn+j+ λ Р n+j –1 + nμ Р n+j+1=0, j=(1,2,….,∞)
QS with an infinite queue and complete mutual assistance for arbitrary flows. Graph, system of equations, calculated ratios.
System Graph
|
System of equations
QS with a finite queue for Poisson flows. Graph, system of equations, calculated ratios.
System Graph
System of equations
Design ratios:
,