Принятие решений в условиях неопределенности: Методические указания к лабораторным занятиям, страница 5

Формализация задачи и построение математической модели

Рассматриваемая ситуация относится к динамическим задачам управления ресурсами оперативной памяти в многозадачном режиме работы операционных систем. Программный комплекс представляет собой динамическую систему, состояние которой изменяется с течением времени по закону, зависящему от выбранной стратегии управления. Переход системы из одного состояния в другое осуществляется мгновенно и в любой момент времени система может находиться только в одном из своих состояний.

Для построения математической модели процесса управления данной системой прежде всего необходимо выяснить, какие параметры характеризуют ее состояние в каждый момент времени. Состояние комплекса в момент времени t определяется набором состояний {S₁, …, S_n} программ Р₁,…,Р_n, входящих в него. В свою очередь состояние S_k программы P_k в момент t можно охарактеризовать номером этапа N_k, выполняемого программой, и временем q_k(t), оставшимся до завершения работы программы (без учета времени ожидания). Таким образом, состояние комплекса в момент времени t однозначно описывается набором параметров

{(N₁, q₁(t)), (N₂, q₂(t)), …, (N_n, q_n(t))}.

Управление системой заключается в распределении ресурсов оперативной памяти между программами в каждый момент времени и может быть представлено в виде вектора функций

U(t) = {u₁(t), u₂(t), …, u_n(t)}.

Если в момент времени t программе P_i выделен ресурс памяти a_ij, необходимый для выполнения j-го этапа, то u_i(t) = 1. Если программе в данный момент не выделено памяти вообще, т. е. она находится в режиме ожидания, то u_j(t) = 0. Будем считать, что в момент  завершения последнего этапа программа P_i переходит в состояние «хранения на диске», не требующее оперативной памяти, и  u_j(t) = 0 при . Выбранное управление должно отвечать условиям

                                (2.1)

                           (2.2)

Значение функции a_i(t) при каждом t равно объему оперативной памяти, предоставленной программе P_i в момент времени t.

Параметры q_i(t), i = 1, …, n, связаны с u_i(t) соотношениями

или с учетом (2.2)

                                       (2.3)

Время выполнения всего комплекса программ выражается функционалом

                                  (2.4)

Формулы (2.1)-(2.4) описывают математическую модель рассматриваемого процесса. В рамках этой модели задача построения оптимальной стратегии управления программным комплексом заключается в отыскании вектора U(t), который удовлетворяет условиям (2.1), (2.2) и доставляет минимум фукционалу J(U).

Управление U(t) является ступенчатой векторной функцией и терпит скачок всякий раз, когда завершается выполнение очередного этапа хотя бы одной из программ P_i, i=1, …, n. Именно в такие моменты времени изменяются номера этапов N_i и происходит переход системы из одного состояния в другое в зависимости от значения управления U(t). Это обстоятельство позволяет рассматривать задачу оптимального управления программным комплексом как процесс с дискретными состояниями.

Дискретная модель для двухпрограммного комплекса

Комплекс из двух программ P₁ и P₂ можно рассматривать как систему, в которой протекает процесс с конечным числом дискретных состояний, каждое из которых описывается парой состояний входящих в комплекс программ: (S₁₁, S₂₁), (S₁₂, S₂₂), …, (S_1k,  S_2k).

Рассмотрим множество этих состояний с точки зрения возможности системы переходить из состояния (S_1i, S_2i) в состояние (S_1j, S_2j) непосредственно или через другие состояния. Для этого удобно пользоваться так называемым графом состояний. Вершины графа соответствуют состояниям системы (S_1i, S_2i). Каждую вершину графа будем изображать прямоугольником, разделенным на четыре равные части (рис. 2.1), в которые вписаны значения четырех параметров, определяющих состояние системы: N_1i и N_2i - номера этапов программ P₁ и P₂ соответственно, q_1i и q_2i - рабочее время, оставшееся до завершения программ P₁ и P₂, без учета времени ожидания.