Искусственный интеллект

9.4. Мультипрограммное выполнение параллельных процессов На уровне модели параллельных процессов предполагается, что процессы выполняются параллельно. Физически это обусловливает наличие для каждого процесса своего индивидуального процессора. В реальной жизни количество процессоров компьютера ограничено и вместо дисциплины параллельного выполнения процессов используются дисциплины квазипараллельного, в частности на одном процессоре. В этом случае для эквивалентности результатов необходимо учитывать дополнительные ограничения на выполнение процессов и использовать специальные средства синхронизации. В настоящей главе рассмотрен однопроцессорный вариант выполнения параллельных процессов, называемый мультипрограммным, причем все процессы предполагаются детерминированными. Его главное свойство состоит в чередовании выполнения переходов различных процессов на одном процессоре как последовательности дискретных шагов. На каждом шаге (такте) выбирается один процесс, выполнение которого допустимо, и выполняется его допустимый переход. (Заметим, что этот переход в каждом процессе единственный вследствие детерминированности процессов.) Выбором процесса ведает специальный планировщик или диспетчер. Диспетчер может осуществлять холостые такты, в которых ни один процесс не выполняется, и значения всех переменных, включая переменные места, остаются неизменными. В случае, когда ни один из допустимых процессов не может быть выполнен и холостой такт является единственно возможным выбором, будем говорить, что модель параллельных процессов находится в дедлоке. Специальный случай такой ситуации проявляется, когда все процессы остановились (находятся в терминальных местах). Следует также отметить, что каждый переход выполняется без какого-либо вмешательства со стороны других процессов, в связи с чем все операции, относящиеся к переходу, называются неделимыми или атомарными.