CN101887384A - A method for determining the length of process time slice based on Markov model - Google Patents

Abstract

The embodiment of the invention discloses a Markov model-based process timeslice length determining method, which comprises the following steps of: mapping out parameters of a Markov model; applying the Markov model to the determination of a timeslice; and making corresponding parameter adjustment according to sleep time. By implementing the method, a system presets the parameters of the Markov model in a process, the current process timeslice is calculated according to the Markov model, and the parameters of the Markov model are adjusted according to the sleep time of the process, so the timeslice length can be timely adjusted and the process performance and the system overall optimization are improved.

Description

A method for determining the length of process time slice based on Markov model

technical field

The invention relates to the field of information technology, in particular to a method for determining the length of a process time slice based on a Markov model.

Background technique

The scheduler is an important part of the operating system kernel. It is responsible for selecting and distributing the processes that need to be run. It can be regarded as a kernel subsystem that allocates limited processor time resources among runnable processes. The scheduler is a system between Linux and Windows. The basis of a class of multitasking operating systems. Only through the reasonable scheduling of the scheduler can the system resources play their role to the maximum and achieve the unity of system throughput and response time.

In process scheduling, the length of the process time slice is an important component. A process time slice is a segment of processor time allocated to each current process. Processes can be divided into I/O-consuming and processor-consuming processes, wherein: I/O-consuming processes refer to processes that spend most of their time submitting I/O requests or waiting for I/O requests. This type of process is usually in a runnable state, but the running time is short, and it will always block while waiting for more I/O requests. A processor-intensive process is one that spends most of its time executing code and typically runs continuously unless preempted. The determination of the process type is mainly based on the length of the sleep time. A process is I/O hungry if it spends most of its time sleeping. A process is processor-hungry if it takes longer to execute than sleep. Most interactive processes are I/O-consuming, and increasing the running frequency of such processes can improve the response speed of the system. Some shorter time slices should be allocated to I/O-consuming processes to increase the frequency of operation. Processor-consuming processes spend a lot of time running code without too many I/O requests. For processor-consuming processes, a longer time slice should be allocated to reduce the operating frequency.

The calculation of the time slice is mainly based on the priority of the process. The priority is mainly adjusted according to the sleep time, and the historical time slice of the process is not considered. Therefore, the length of the time slice may change suddenly, resulting in an imbalance of the time slice of each process. Degraded performance of individual processes and poor performance of the system as a whole.

Contents of the invention

Embodiments of the present invention provide a method for determining the length of a process time slice based on a Markov model, which can improve the effectiveness of determining the length of a time slice, thereby improving process efficiency and overall performance of the system.

Embodiments of the present invention provide a method for determining the length of a process time slice based on a Markov model, including:

Formulate the parameters of the Markov model;

Use the Markov model to determine the length of the process time slice;

Adjust the parameters of the Markov model according to the process sleep time.

The parameters of the proposed Markov model include:

Determine the state transition probability matrix of the Markov model to determine the impact of historical time slices on the length of the current time slice.

The determination of the Markov model to be applied to the time slice includes:

Use the state transition matrix in the Markov model to determine the length of the current time slice.

The corresponding parameter adjustment according to the sleep time includes:

Readjust the state transition matrix according to the process sleep time.

In the embodiment of the present invention, the system first presets the parameters of the process Markov model, calculates the current process time slice according to the Markov model, and adjusts the parameters of the Markov model according to the process sleep time. According to the sleep time adjustment, the embodiments of the present invention can adjust the time slice length in time by considering the historical time slice of the process, thereby improving the process performance and overall system optimization.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. For those skilled in the art, other drawings can also be obtained according to these drawings without any creative effort.

FIG. 1 is a flow chart of determining the length of a process time slice based on a Markov model in an embodiment of the present invention.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

FIG. 1 shows a flow chart of determining the length of a process time slice based on a Markov model.

① Initialize the historical time slice array. Its form is as follows T={t ₀ , t ₁ , t ₂ , t ₃ . . . }. The historical time slice array is added in the process maintenance table of the system, and the array has a maximum length, which is set to 6. The purpose of setting the maximum length is to dynamically consider the length of the historical time slice, instead of considering all of them, so as to provide a certain degree of flexibility. The generally used historical time slice length is 3 or 4. An appropriate length can improve the effectiveness of the determined current process time slice length on the one hand, and reduce the calculation amount of the process time slice length on the other hand to improve efficiency. At the same time, the value of the historical time slice array is set to the time slice length allocated when the process is initialized. If it is set to 0, it is calculated by the state transition matrix. Considering the historical time slice, the calculation of the length of the next time slice will be too short.

② Draw up the parameters of the Markov model. An important component in the Markov model is the transition probability matrix, which is also an important part in the calculation of time slices. Each item in the matrix represents the influence of the corresponding historical time slice on the current time slice, which is set in the form of an array such as M={a ₀ , a ₁ , a ₂ , a ₃ ...}, where M represents transfer The matrix is a one-dimensional row vector. The maximum length is the same as the length of the historical time slice array, which is set to 6. During the calculation process, its dynamic length is the same as that of the historical time slice array, generally 3 or 4. In M, a0 corresponds to the first item of the historical time slice array, indicating the probability influence of the historical time slice on the calculation of the current time slice, and so on. In this way, M contains the influence of elements of the historical time slice array on the calculation of the current time slice, and the elements in M should satisfy the constraint condition: a ₀ +a ₁ +a ₂ +a ₃ +a ₄ +a ₅ =1. A value of 1 indicates that the current time slice array is only determined by historical time slices. When the dynamic length of M is 4 instead of the total length 6, the values of a ₄ and a ₅ should be set to 0, indicating that the corresponding historical time slice is not taken into consideration. And so on when the dynamic length is 3 or other values.

③ Calculation of the current time slice. After the model of M is determined, the current time slice can be calculated. The calculation of the current time slice should not be too complicated, otherwise it will take up too much CPU time, which will lead to a decrease in system performance, which is counterproductive. Therefore, it is necessary to design a calculation method of O(1). The calculation method is

$\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; l</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}$

where t represents the current historical time slice. This calculation method takes into account the influence of the historical time slice on the current time slice.

④Update the current historical time slice array. The operation method is to shift the elements of the historical time slice array to the right one by one, replace the first item in the array with the calculated current time slice, and set the out-of-range elements to 0 according to the current dynamic array length. For example, the historical time slice array is T={t ₀ , t ₁ , t ₂ , 0, 0, 0}, it can be known that its dynamic length is 3, after updating it is T={t, t ₀ , t 1 , ₀ , 0 ,0}.

⑤ The process appears dormant, and the Markov model parameters are updated. The dormancy of the process indicates that the process type changes, for example, the longer the dormancy time, it indicates that the process is biased towards I/O type. The sleep time of a process directly affects the priority of the process. The parameters of the Markov model should also be consistent with the change of the priority of the process. Therefore, when the priority increases, under the constraint conditions, it is necessary to increase the probability influence of the latest historical time slice on the current time slice; the priority decreases When , under the constraint conditions, it is necessary to reduce the probability influence of the recent historical time slice on the current time slice accordingly. For example, when the process priority increases, M={a ₀ , a ₁ , a ₂ , a ₃ ...}, the values of a ₀ and a ₁ in M need to be increased accordingly, and the values of a ₂ and a ₃ in M It needs to be reduced accordingly, and the constraints need to be met. In this way, it can be considered that when the process type changes, the length of the process time slice will not change significantly, and the overall performance of the system can be maintained while maintaining the process performance.

Those of ordinary skill in the art can understand that all or part of the steps in the various methods of the above embodiments can be completed by instructing related hardware through a program, and the program can be stored in a computer-readable storage medium, and the storage medium can include: only Read memory (ROM, Read Only Memory), random access memory (RAM, Random Access Memory), disk or CD, etc.

The above is only a preferred embodiment provided by the embodiment of the present invention, which has been introduced in detail. In this paper, specific examples are used to illustrate the principle and implementation of the present invention. The description of the above embodiment is only used to help understand the present invention. The method of the invention and its core idea; at the same time, for those of ordinary skill in the art, according to the idea of the present invention, there will be changes in the specific implementation and scope of application. In summary, the content of this specification should not be understood To limit the present invention.

Claims (4)

1. the process timeslice length based on Markov model is determined method, it is characterized in that, comprising:

Draft the parameter of Markov model;

Markov model is applied to determining of timeslice;

Do corresponding parameter adjustment according to dormancy time.

2. method according to claim 1 is characterized in that, the described parameter of drafting Markov model comprises:

Determine the state transition probability matrix of Markov model, to determine of the influence of historical time sheet to the current time leaf length.

3. method according to claim 1 is characterized in that, with Markov model be applied to timeslice determine comprise:

State-transition matrix in the utilization Markov model is determined the current time leaf length.

4. method according to claim 1 is characterized in that, describedly does corresponding parameter adjustment according to dormancy time and comprises:

Readjust state-transition matrix according to the process dormancy time.

Images