доктор технических наук
doctor of technical sciences
доктор технических наук, профессор
doctor of technical sciences
доктор педагогических наук
Tula State Lev Tolstoy Pedagogical University
В работе рассмотрена проблема оптимизации расписания функционирования многопроцессорных систем. Решение данной проблемы предполагает формирование жесткогографика работы, который определяет ритм процессов, но на практике на функционирование систем оказывает влияние множество побочных факторов, которые делают интервалывремени выполнения работ случайными. В работе построена полумарковская модель формирования стохастического расписания в условиях парного соревнования. Показано, чтоесли при функционировании системы возможно исполнение пунктов расписания в произвольном порядке, то эволюция полумарковского процесса проходит по гамильтонову пути.Доказано, что все возможные реализации гамильтоновых путей образуют полную группу несовместных событий. Отмечается, что вследствие наложения ограничений по характеру эволюции, процесс эволюции не является строго полумарковским, и поэтому предложен метод формирования из первичной модели, строго полумарковского процесса с древовидной структурой. Получены зависимости для расчета плотностей распределения и вероятностей переключения из состояний полумарковского процесса в сопряженные состояния, а также времени блуждания от стартового до поглощающих состояний. С использованиемпонятия парного дискретного соревнования и распределенного штрафа оценивается эффективность выбора гамильтонова пути одним из субъектов с учетом того, что алгоритм поведения его оппонента известен с точностью до построения полумарковской модели.
The paper considers the problem of optimizing the operation schedule for multiprocessor systems. The solution to this problem involves the formation of a rigid work schedule, whichdetermines the rhythm of the processes, but in practice the functioning of systems is influenced by many side factors that make the intervals of work execution random. In the work, a semi-Markov model of the formation of a stochastic schedule in conditions of pair competition is constructed. It is shown that if during the functioning of the system it is possible to execute theitems of the schedule in an arbitrary order, then the evolution of the semi-Markov process follows the Hamiltonian path. It is proved that all possible realizations of Hamiltonian paths form acomplete group of incompatible events. It is noted that, due to the imposition of restrictions on the nature of evolution, the evolution process is not strictly semi-Markov, and thereforea method of forming a strictly semi-Markov process with a tree structure from the primary model is proposed. Dependences are obtained for calculating the distribution densities and theprobabilities of switching from states of a semi-Markov process to conjugate states, as well as the time of walking from the starting to absorbing states. Using the concept of paired discretecompetition and a distributed penalty, the effectiveness of the choice of a Hamiltonian path by one of the subjects is estimated, taking into account the fact that the algorithm of his opponent’sbehavior is known up to the construction of a semi-Markov model.
The authors declare that there are no conflicts of interest present.