Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

335

ошибкой, т. к. оно навязывает задание потока, для которого итерации выпол-

няются последовательно, а не совместно. Иными словами, в таких случаях

более естественным является цикл

for

традиционных языков. Впрочем, и в

этих случаях задание цикла для всех можно было бы трактовать как явное

указание на то, что вся зависимость итераций друг от друга фактически сво-

дится лишь к перевычислению параметра цикла. Но и тогда лучше было бы

воспользоваться описанным в § 7.3.1 понятием списка параметров цикла.

Таким образом, мы видим здесь еще одно концептуальное противоречие:

в одном и том же фрагменте программы нужно использовать либо только

потоки, либо только совместные циклы. Оно пока что остается потенциаль-

ным, поскольку совместные циклы в обиход еще не вошли (хотя, видимо, на

следующем витке развития к ним вернутся как к мощному средству прото-

типирования и распараллеливания).

Если говорить о логической аналогии, то совместные циклы соответству-

ют скорее ограниченным кванторам всеобщности, чем какому-то другому ло-

гическому понятию. Таким образом, принятое в

СЕТЛе

обозначение соответ-

ствует сути совместных циклов.

7.3.4. Входные и выходные потоки. Сопрограммы

До сих пор потоки рассматривались исключительно с одной позиции: с

точки зрения их генерации для конкретной обработки. То, что они могут ис-

пользоваться как цель обработки, разумеется, не исключалось. Более того,

при обсуждении программ о простых числах об этом говорилось прямо. Дру-

гой наглядный пример:использование потока псевдослучайных чисел. Пусть

имеется следующая программа:

Программа 7.3.1

Псевдослучайные числа

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

void main()

{

int i;

srand( (unsigned)time( NULL ) );

for( i = 0; i < 10; i++ )

// Напечатать 10 чисел

336

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

printf( "%6d\n", rand() );

}

Эта программа подпадает под схему 1 с инициализацией, не включающей ге-

нерацию. Но что можно сказать о функциях

srand

rand

, если рассматривать

их независимо от использующей программы? Первая из них инициализиру-

ет поток, а вторая генерирует его элементы независимо от того, как будут

они применяться.Иными словами, здесь поток — цель некоторой (оставшей-

ся вне рассмотрения) обработки, или, по-другому, выходной поток, который

является входным потоком для программы 7.3.1.

С другой стороны, каждая итерация цикла программы 7.3.1 поставляет

число, которое требуется напечатать, функции

printf

. Вполне правдоподобно

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

печатывает последовательность выводимых элементов, передаваемых через

параметры

printf

(эта программа производит еще другую дополнительную

работу, обеспечивающую корректность вывода: оперирование с позициями

курсора на экране, форматирование и др.). Иными словами, имеет место вы-

ходной поток элементов, генерируемый программой 7.3.1. Таким образом,

программа 7.3.1 потребляет один поток и в ходе его обработки порождает

другой поток.

Вполне допустимы и практически применяются схемы организации ра-

боты с потоками, когда выходной поток формируется несколькими програм-

мами (фрагментами программ) или когда поток потребляется несколькими

программами (фрагментами программ). В общем случае возможно несколь-

ко (m) производителей и несколько (n) потребителей потоковых данных. Их

взаимодействие корректно, если

Не может случиться так, что потребители запрашивают

больше данных, чем произведено производителями.

(7.2)

Если взаимодействия реализуются при последовательной дисциплине вычи-

слений, то других ограничений не предполагается. Возможности согласова-

ния порождения и потребления потока в этом случае сводятся к одной из

следующих схем:

1. Разделение: генерация хранимого потока производителями с последу-

ющим извлечением данных потребителями. По существу здесь нет вза-

имодействия. Работа производителей и потребителей не влияет друг на

друга.

7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

337

2. Запрашивание: по мере надобности очередного элемента потока для

потребления (обработки)вызывается подпрограмма производителя (од-

ного из них, нужного для конкретной работы). Таким образом, выделя-

ется управляющая программа (потребитель), которая указывает, когда

и какого из производителей нужно активизировать.

3. Предъявление: по мере порождения очередного элемента потока произ-

водителем вызывается необходимый для обработки потребитель, кото-

рому предъявляется этот элемент. Таким образом, управление осуще-

ствляется программой производителя, которая указывает, когда и како-

го из потребителей нужно активизировать.

4. Общее управление: строится специальная управляющая программа, ко-

торая поочередно вызывает производителей и потребителей, тем са-

мым организуя выходной/входной поток.

Последние три схемы описывают механизмы сопрограммного взаимодей-

ствия группы подпрограмм,называемых сопрограммами (процедур,модулей

и др.,) в случае дисциплины последовательных синхронных вычислений.

Суть механизма сопрограммного взаимодействия в общем случае, т. е.

без привязки к потоковой обработке, состоит в следующем. В ходе выполне-

ния какой-либо подпрограммы группы происходит приостановка ее работы

с тем, чтобы вызвать для выполнения другую подпрограмму группы (способ

приостановки не фиксируется). В какой-то момент приостановленная под-

программа возобновляет свою работу в том состоянии, в котором она была

приостановлена (важный частный, но не единственно возможный случай —

запоминание точки приостановки с тем, чтобы возобновление продолжилось

с этой точки программы).

Сопрограммное взаимодействие естественно обобщается на процессы,

которые возникают при выполнении программ. Программа — это статиче-

ское понятие (текст, код), процесс — понятие динамическое, определяемое

как выполнение некоторой программы. Одна программа может породить мно-

го процессов (пример — рекурсия), но любой процесс связан с вполне опре-

деленной программой процесса. Так что словосочетание ‘приостановка ра-

боты программы’ понимается как приостановка выполнения процесса, ею

порожденного (одного из них), а ‘возобновление работы программы’ есть не

что иное, как возобновление выполнения процесса, ею порожденного и ранее

приостановленного (каким-либо способом).

338

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

Понятие сопрограммных взаимодействий можно продуктивно использо-

вать не только в случаях последовательных синхронных вычислений.По срав-

нению с последовательным случаем расширяются лишь способы приоста-

новки и возобновления процессов. Допускается внешняя приостановка, ко-

торая никак не связана с логикой работы программы процесса. Возобновле-

ние процесса не обязательно происходит принудительно по явной коман-

де, допускается асинхронное продолжение выполнения процесса с точки его

приостановки, когда открывается возможность для этого (например, когда

освободился один из процессоров).

Как видно из определения сопрограммного взаимодействия, оно никак

не связано с потоковой обработкой. Сопрограммность может базироваться

на совместном использовании несколькими процессами любого общего ре-

сурса (см. рис. 7.1, часть а). Поток следует рассматривать лишь как один из

Поток

Приостановленны

й процесс

Потенциально

активный процесс

Обработанные элементы

Порождение

(генерация)

Порождение

(генерация)

Приостановленные

процессы

Активный

процесс

П11 П12

Программа 1

Программа 2

П21

Общий ресурс

трех процессов

Потенциально

активный

процесс

П11

Программа 1

Программа 2

П21

Необработанные элементы

Потребление

(обработка)

Потребление

(обработка)

а) буферизация отсутствует б) потоковая бу феризация

П12

Рис. 7.1. Взаимодействие процессов с разделяемыми ресурсами

видов такого ресурса, который характеризуется определенными правилами

доступа. Это динамически пополняемая последовательность со слабой зави-

симостью пополнения и извлечения элементов: для корректности обработки

необходимо выполнение условия (7.2).

7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

339

Потоки — это один из наиболее важных видов ресурсов, совместно ис-

пользуемых сопрограммами.С их помощью реализуется часто применяемый

на практике механизм буферизации. Идея механизма буферизации в том, что

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

(очередь, поток, иную структуру данных), пополняемый процессами-произ-

водителями, и опустошаемый процессами-потребителями (см. рис. 7.1, часть

б). В этом случае производители могут генерировать элементы, не дожидаясь

запросов потребителей.

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

средство и только во вторую очередь как средство распараллеливания работ.

Причем последнее вовсе не обязательно!

Буфер может иметь фиксированные размеры, и тогда его заполненность

приводит к невозможности (к блокировке) работы производителей до тех

пор, пока потребители не очистят его. В вырожденном случае, когда длина

буфера не может превышать единицы, буферизация фактически отсутству-

ет, и применимы схемы согласования 2–4. Для асинхронного случая к ним

добавляются схемы использования средств управления параллельными вы-

числениями: операторы синхронизации, ожидания и т. п. В случае неогра-

ниченного буфера становится возможной и схема 1, но, как уже отмечалось,

фактически это отсутствие взаимодействия.

Имеются виды буферизации, которая базируется не на потоковом извле-

чении данных. Заполнение буфера — генерация потока, но извлечение дан-

ных может быть организовано не только как очередь, но и как стек, и как

множество (когда порядок извлечения непринципиален). Выбор типа буфера

обусловливается особенностями решаемой задачи.

Рекомендуем посмотреть пример в § 8.6.3, в котором активно использу-

ется буферизация в виде линии задержки.

Все рассмотренные выше виды буферизации представляют собой пассив-

ную буферизацию,т. е. такую,которая не участвует в выполнении существен-

ных функций производителей и потребителей данных, а используется лишь

для хранения. Наряду с ней употребительна и активная буферизация, когда

с хранением совмещается ряд других функций. К примеру, если для обработ-

ки требуется только часть данных некоторого потока, то можно организовать

фильтр для отбора нужных данных перед помещением их в буфер либо перед

извлечением их. Этот прием можно усмотреть в решении задачи о простых

числах, если считать хранилище уже найденных чисел буфером. Легко заме-

тить, что фильтрация перед сохранением данных в таком случае зависит от

свойств уже накопленного материала (числа, кратные уже запомненным про-

340

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

стым числам, не сохраняются). Это довольно типичная ситуация, равно как и

та, в которой условие выходного фильтра формулируется с использованием

свойств хранимых данных. Собственно говоря, подобные зависимости мож-

но рассматривать как признак того, что следует организовывать активную

буферизацию.

Не следует думать, что в буфере всегда хранятся именно те значения, ко-

торые генерируются поставщиками данных и извлекаются для потребления.

Так, часто активная буферизация применяется, когда требуется, к примеру,

хранить уплотненные данные или размещать в буфере значения, по которым

требуемые данные определяются путем вычислений. Таков, в частности, тот

пример задачи о простых числах, когда оказалось выгоднее сохранять их раз-

ности, а не сами значения.

Из всего предыдущего рассмотрения видно,что буферизация сначала долж-

на рассматриваться как общий прием декомпозиции программ, а когда реше-

ние о буферизации принято,можно говорить о языковом оформлении и далее

о реализации.

До сих пор учет параллельного выполнения процессов в качестве задачи

рассматривался лишь в принципе — схемы 1–4 задают строго определенный

порядок, условие (7.2) вообще не связано с последовательностью или парал-

лельностью вычислений. При асинхронной параллельной работе процессов

производителей и потребителей для обеспечения корректности разделения

общего ресурса нужно решать задачу блокировки чтения/записи данных. Ис-

ходные условия для нее сводятся к двум положениям:

1. Разрешаются ситуации, когда:

любое число потребителей одновременно читают ранее

записанные данные общего ресурса;

(7.3)

2. Недопустимы ситуации, когда:

два или более производителей пытаются записать данные

в общий ресурс одновременно;

(7.4)

один или более потребителей пытаются прочитать данные

общего ресурса, когда некоторый (любой) производитель

записывает данные.

(7.5)

7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

341

Это классическая задача синхронизации взаимодействия писателей (произ-

водителей)и читателей (потребителей), работающих с общим ресурсом.Если

взаимодействие буферизируется с помощью потока,то условие (7.5)ослабля-

ется. Вместо него требуется выполнение условия (7.2).

До сих пор обработка потоков связывалась с внешними управляющими

действиями. Возможен и другой взгляд на поток, при котором считается, что

программные единицы управляются входными потоками данных, именуе-

мых обычно сообщениями. Элементы потока сообщений могут восприни-

маться программной единицей и, тем самым, либо возбуждать соответству-

ющую реакцию, либо игнорироваться, в случае, когда данное сообщение не

предназначено для этой программной единицы.

Здесь, как и ранее, более точно надо говорить о процессах, а не о про-

граммных единицах, так что слова «управление программной единицы вход-

ным потоком событий» следует трактовать исключительно как управление

процессом,который порожден данной программной единицей (одним из них).

Стоит отметить, что современная трактовка такого управления чаще всего

связывается с объектами, получающими сообщения и возбуждающими ре-

акцию на них посредством вызова соответствующих методов.

Самое примечательное в потоках-сообщениях то, что их использование

позволяет в максимальной степени стандартизовать управление, а именно:

составляется единый цикл генерации сообщений и их рассылки процессам,

и те из процессов-получателей, которые предусматривают реакцию на дан-

ное сообщение, осуществляют нужную обработку в пределах собственной

компетенции.

Современные системы программирования включают в себя средства ор-

ганизации потоков-сообщений для управления процессами и обеспечивают

возможности реализации стандартного потокового управления. В подавля-

ющем большинстве случаев это связывается с объектной ориентированно-

стью. Примеры:

Visual Basic

Delphi

Visual C++

и др.

В отличие от программ, которые рассматривались до сих пор и которые

можно назвать программами “одного измерения” (некая последовательность

описаний и действий, понятная сама по себе, если знаешь язык), стандарти-

зация потокового управления позволяет перейти к качественно иному стилю

программирования. В рамках этого стиля, получившего название событий-

но-ориентированного (см. § 3.5), программист готовит (под-) программы, ре-

агирующие на события, происходящие в системе. При этом стандартизован

способ передачи такой программе сведений о том, что настало ее время (на-

ступило событие).

342

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

Важное уточнение! Реагируют такие программы не сами по себе, а че-

рез объекты, которые их содержат в качестве методов. Такое опосредованное

действие удобно во всех отношениях:

• Объект содержит все, что нужно для задания реакции на события. В

частности, он знает, на какие события предусмотрена его реакция.

• Можно создавать копии объектов (методы не дублируются).

• Контекст методов — это атрибуты объекта, другие его методы и, ра-

зумеется, описания, в которые погружено описание объектов данного

класса.

Активизация реакции объекта на событие задается следующей схемой:

если у объекта есть метод для данного события,

то этот метод вызывается для исполнения

иначе этот объект ничего не делает;

Это одна из мотиваций объектного подхода

). При рассмотрении программ,

построенных для отработки реакций на события, самое важное то, что все

такие программы могут быть стандартизованы. Обсуждение такой схемы см.

в § 3.5.

В случае событийно-ориентированного программирования схема програм-

мы, называемой обычно проектом, строится следующим образом:

инициировать первичный набор объектов

//(в дальнейшем он может

меняться, менять свои свойства и др.);

цикл

// бесконечный цикл опроса-ожидания событий

если есть событие

то

цикл для всех объектов из набора

// опрос текущего набора объектов

если у объекта есть метод для данного события

то вызывать этот метод для исполнения

конец цикла

Не самая главная, не самая важная, но существенная и вдобавок такая, с которой програм-

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

системах, например, на

Visual C++

или

Delphi

7.3. ЛОГИЧЕСКАЯ СТРУКТУРА ЦИКЛА

343

7.3.5. Понятие обстановки вычислений.

Действия, меняющие обстановку

Любой вид потоковой обработки — это схематическое описание процес-

са, управляемого последовательностью, получение которой элемент за эле-

ментом задано генерацией потока. С формальной точки зрения итерации лю-

бого цикла можно рассматривать как обработку некоторого ‘умозрительно-

го’ потока, состоящего из сложных (структурированных) элементов: каждый

такой элемент — вся совокупность данных, используемых в итерации (см.

п. 7.3.1). Но этот взгляд непродуктивен: схемы обработки составляются для

того, чтобы удобнее записывать, обсуждать, сравнивать алгоритмы и спосо-

бы их представления в языковых формах. Таким образом, нужно рассматри-

вать обработку как потоковую, когда это удобно, и говорить о других схемах,

когда потоковое представление не помогает восприятию.

При принудительном завершении конструкции действия становятся не-

локальными, и уже поэтому не могут адекватно описываться потоковыми

схемами. Наглядный пример обработки, которая не вписывается в эти схе-

мы, — бинарный поиск (заодно здесь иллюстрируется нелокальность завер-

шителя):

Программа 7.3.2

Binary Search

#include <stdio.h>

#include <math.h>

#deﬁne SZA 10 //

Размер массива поиска

int a[SZA]; //

Массив поиска

void init ()

// Функция задания начальных значений a

{

...

}

int main()

{

char c;

// Переменная для организации потока ввода

init ();

do {

int x;

// Переменная для искомого значения

344

ГЛАВА 7. ЦИКЛИЧЕСКИЕ ВЫЧИСЛЕНИЯ

int imi = 0;

// Нижний индекс поиска

int ima = SZA;

// Верхний индекс поиска

int h;

// Служебная переменная:

//полуразность

imi

ima

int response;

// Ответ

printf ("Input: ");

scanf ("%i", &x);

response=-1;

// Заранее предполагаем неудачу

while (imi <= ima)

{

h = (imi+ima)/2;

if (x == a[h]) {response=h;

break

;}

if (x > a[h]) imi = h+1;

else ima = h-1;

}

printf ("Output: %i\n", response);

scanf ("%c", &c);

}

while ( c != ’n’);

return 0;

}

Заметим, что переменная

response

совмещает в себе две функции: индекса

нужного элемента, если он найден, и сообщения о неудаче, если такого эле-

мента нет. Такое совмещение часто целесообразно: особые значения резуль-

тата служат естественным сигналом об исключительной ситуации.

break;

выводит нас за пределы двух операторов сразу, поскольку исполняется вну-

три условного оператора, а заканчивает минимальный объемлющий цикл.

Далее, поскольку мы ищем хотя бы одно решение, у нас в программе прак-

тически вычисляется квантор существования, т. е. дизъюнкция целого мно-

жества элементов. Поэтому в качестве начального значения ответа берется

−1, логически соответстующая единице дизъюнкции: лжи, отсутствию ре-

шения.

Это общее правило: если вычисляется выражение вида

i∈I

, то в качестве начально-

го значения берется единичный элемент операции ⊗. Поэтому, например, при вычислении

суммы начальным значением обычно принимается 0.