17. Рекурсивные подпрог.

Рекурсия – вызов функцией самой себя. Большое количество алгорит­мов наиболее естественным образом представляется с использованием рекурсии. Во многих языках, где первичной доступной структурой данных являются списковые структуры, рекурсия является первичным механизмом управления для повторя­ющихся последовательностей операторов, заменяя циклы, характерные для боль­шинства других языков.

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

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

Единственное различие между рекурсив­ным вызовом и обычным вызовом заключается в том, что рекурсивный вызов создает вторую активацию этой же подпрограммы во время жизни ее первой активации.

18. Планируемые подпрог.

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

Существуют следующие способы планирования подпрограмм:

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

2. Планировать выполнение программ в зависимости от истинности какого-либо логического выражения. Такое планирование является одним из видов обобщенной обработки ис­ключений; подпрограмма В вызывается всякий раз, когда значения перемен­ных Z и X изменяются и удовлетворяют заданным условиям.

3. Планировать подпрограммы на основе моделирования временной шкалы.

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

4. Планировать подпрограммы в соответствии с назначенным приоритетом

19. Параллельные подпрог.

Конструкции параллельного программирования усложняют разработку, поскольку одновременно несколько процессоров могут иметь доступ к одному и то­му же объекту данных. Чтобы рассматривать параллелизм, следует обратиться к следующим пяти понятиям.

1. Определение переменных. Переменные могут быть изменяемыми или неиз­меняемыми. Изменяемые переменные — это обычные переменные, объяв­ляемые в большинстве последовательных языков программирования. Неизменяемой переменной значение можно присвоить только один раз. Смысл существования таких переменных за­ключается в том, чтобы избежать проблемы синхронизации. Когда такой пе­ременной присвоено некоторое значение, любая задача может обратиться к этой переменной и получить правильное значение.

2. Параллельная композиция. Выполнение движется от одного оператора к сле­дующему.

3. Структура программы. Параллельные программы в основном следуют од­ной из следующих двух моделей выполнения.

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

б) Они могут быть реагирующими, когда программа реагирует на некото­рые внешние «раздражители», называемые событиями. Примерами реа­гирующих систем являются системы реального времени и оперативные системы управления. Операционная система и система обработки тран­закций, например система регистрации предварительных заказов, также являются типичными примерами таких реагирующих систем. В целом их можно охарактеризовать как обладающие недетерминированным по­ведением, так как никогда не известно точно, когда произойдет какое-то событие.

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

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

20. Синхронизация параллельных подпрог. Концепция монитора

Синхронизация процессов — приведение двух или нескольких процессов к такому их протеканию, когда определённые стадии разных процессов совершаются в определённом порядке, либо одновременно.

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

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

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

Монитор состоит из:

1)набора процедур, взаимодействующих с общим ресурсом

2)мьютекса

3)переменных, связанных с этим ресурсом

Процедура монитора захватывает мьютекс перед началом работы и держит его или до выхода из процедуры, или до момента ожидания условия. Чтобы избегать состояния активного ожидания, процессы должны сигнализировать друг другу об ожидаемых событиях. Мониторы обеспечивают эту возможность с помощью условных переменных. Когда процедура монитора требует для дальнейшей работы выполнения определённого условия, она ждёт связанную с ним условную переменную. Во время ожидания она временно отпускает мьютекс и выбывает из списка исполняющихся процессов.

Монитор имеет следующие свойства:

Связывается с объектом по требованию.

Невозможно создать экземпляр класса Монитор.