40гг первые цифровые компьютеры программирование путем коммутации проводов

Вид материала

Содержание

Critical_section cs
Декларативная программа
Императивная программа
Функциональное программирование
Логическое программирование

Подобный материал:

1 ... 4 5 6 7 8 9 10 11 12

with R do

S

end do;

R – общая переменная;

S – последовательность операторов критического интервала.

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

Использование конструкции позволяет отказаться от явных действий с семафорами: открытие и закрытие их производится автоматически в соответствии с командами, сгенерированными транслятором.
Отпадает необходимость в проверке правильности расстановки операций над семафорами.
Транслятор может проверить, что общая переменная используется только внутри критических интервалов, так как мы явно указываем их в программе, следовательно, повышается надежность программ.
Однако, все остальные недостатки семафоров присущи и простому критическому интервалу.

Мониторы

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

Преимущества мониторов

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

Аппаратная поддержка критических интервалов

Запрещение прерываний
Неделимые операции

Запрещение прерываний

Достоинство

Простота и эффективность реализации

Недостаток

Запрещение прерываний может негативно отразиться на работе системы в целом
Не имеет смысла в многопроцессорных системах

Неделимые операции

В систему команд современных процессоров входит неделимая команда «проверить и установить»
За одну неделимую операцию происходит проверка переменной на равенство нулю и ее установка в единицу.
Если переменная была равна нулю, то результат операции – единица, иначе 0.

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

Средства обеспечения работы процессов (описание, создание, завершение, обработка исключений)
Механизмы, реализующие взаимное исключения и синхронизацию для процессов с общей памятью
Механизмы передачи сообщений

Механизмы передачи сообщений

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

Сопрограммы – возможность приостанавливать и продолжать выполнение одного процесса из другого.
Рандеву – возможность передачи данных между процессами без дополнительного буфера (сначала ожидается готовность процессов к передачи и приему, после этого осуществляется синхронный обмен)

Специализированные

Почтовые ящики – передача сообщений между процессами через посредника.
Порты – возможность менять посредника
Транспортеры – перенаправление ввода/вывода.

Основные понятия для ОС Windows

Процесс – экземпляр выполняемой программы, состоит из адресного пространства, в котором располагается код программы и данные.
Процессы инертны. Чтобы процесс что-либо выполнил в нем нужно создать поток (thread). Именно потоки отвечают за выполнение кода программы.
Процесс содержит как минимум один поток, который создается автоматически при запуске программы и осуществляет ее выполнение.
Программа может создавать дополнительные потоки по мере необходимости.
Потоки одного процесса работают в едином адресном пространстве.
На однопроцессорных компьютерах операционная система предоставляет последовательно каждому потоку квант времени, на многопроцессорных компьютерах одновременно может выполняться столько потоков, сколько есть процессоров.

Средства синхронизации процессов в С/С++ отсутствуют

Объекты API (используются функции С)

Взаимоисключения (mutex)
События (event)
Семафоры (semaphore)
Критические интервалы (critical section)
Защищенный доступ к переменным

Классы VCL Borland C++ Builder

TMultiReadExclusiveWriteSynchronizer
TCriticalSection
TEvent

Общие особенности

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

Возможные состояния потоков

Активен – идет выполнение потока на процессоре.
Готов – поток готов к выполнению, ждет предоставления процессорного времени.
Заблокирован – потоку не выделяется процессорное время, он не планируется на выполнение.

Управление потоками в Borland C++ Builder

Для упрощения работы с потоками в Borland C++ Builder предусмотрен специальный класс TThread.

Взаимоисключения

Объекты-взаимоисключения (мьютексы, mutex - от MUTual EXclusion) позволяют координировать взаимное исключение доступа к разделяемому ресурсу.
Сигнальное состояние объекта (т.е. состояние "установлен") соответствует моменту времени, когда объект не принадлежит ни одному потоку и его можно "захватить".
Состояние "сброшен" (не сигнальное) соответствует моменту, когда какой-либо поток уже владеет этим объектом.
Доступ к объекту разрешается, когда поток, владеющий объектом, освободит его.
Для того, чтобы объявить взаимоисключение принадлежащим текущему потоку, надо вызвать одну из ожидающих функций.
Поток, которому принадлежит объект, может его "захватывать" повторно сколько угодно раз (это не приведет к самоблокировке), но столько же раз он должен будет его освобождать.

Пример использования Mutex

#include

#include

void main() {

DWORD res;

// создаем объект-взаимоисключение

HANDLE mutex = CreateMutex(NULL, FALSE, "APPNAME-MTX01");

// если он уже существует, CreateMutex вернет дескриптор существующего

// объекта, а GetLastError вернет ERROR_ALREADY_EXISTS

// в течение 20 секунд пытаемся захватить объект

cout<<"Trying to get mutex...\n";

cout.flush();

res = WaitForSingleObject(mutex,20000);

if (res == WAIT_OBJECT_0) // если захват удался

{ // ждем 10 секунд

cout<<"Got it! Waiting for 10 secs...\n"; cout.flush();

Sleep(10000);

// освобождаем объект

cout<<"Now releasing the object.\n"; cout.flush(); ReleaseMutex(mutex);

}

// закрываем дескриптор

CloseHandle(mutex);

}

События (Event)

Объекты-события используются для уведомления ожидающих потоков о наступлении какого-либо события.
Различают два вида событий - с ручным и автоматическим сбросом.
Ручной сброс осуществляется функцией ResetEvent. События с ручным сбросом используются для уведомления сразу нескольких потоков.
При использовании события с автосбросом уведомление получит и продолжит свое выполнение только один ожидающий поток, остальные будут ожидать дальше.
Функция CreateEvent создает объект-событие.
SetEvent - устанавливает событие в сигнальное состояние.
ResetEvent-сбрасывает событие.
Функция PulseEvent устанавливает событие, а после возобновления ожидающих это событие потоков (всех при ручном сбросе и только одного при автоматическом), сбрасывает его.
Если ожидающих потоков нет, PulseEvent просто сбрасывает событие.

Семафоры

Объект-семафор - это фактически объект-взаимоисключение со счетчиком.
Семафор позволяет "захватить" себя определенному количеству потоков.
После этого "захват" будет невозможен, пока один из ранее "захвативших" семафор потоков не освободит его.
Семафоры применяются для ограничения количества потоков, одновременно работающих с ресурсом.
Объекту при инициализации передается максимальное число потоков, после каждого "захвата" счетчик семафора уменьшается.
Сигнальному состоянию соответствует значение счетчика больше нуля.
Когда счетчик равен нулю, семафор считается не установленным (сброшенным).

Критические интервалы

Объект - критический интервал помогает программисту выделить участок кода, где поток получает доступ к общему ресурсу, и предотвратить одновременное использование ресурса.
Перед использованием ресурса поток входит в критический интервал (вызывает функцию EnterCriticalSection).
Если после этого какой-либо другой поток попытается войти в тот же самый критический интервал, его выполнение приостановится, пока первый поток не покинет интервал с помощью вызова LeaveCriticalSection.
Похоже на взаимоисключение, но используется только для потоков одного процесса.
Существует также функция TryEnterCriticalSection, которая проверяет, занят ли критический интервал в данный момент.
С ее помощью поток в процессе ожидания доступа к ресурсу может не блокироваться, а выполнять какие-то полезные действия.

Критические интервалы

//Для использования критического интервала, нужно объявить переменную типа CRITICAL_SECTION
      CRITICAL_SECTION CS;

// Потом эту переменную CS нужно инициализировать (создать критический интервал)
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
     InitializeCriticalSection(&CS);
}
// используем критический интервал в потоке, когда нужно блокировать доступ к данным
void __fastcall TMyThread::Execute()
{
   FreeOnTerminate = true; // освободить занятую потоком память по окончании его работы
   for(int i=0; i<10000; i++)
   {
     // -- какие-то сложные вычисления в цикле
     if(Terminated) break; // прекратить извне поток
     // блокировать доступ к данным (войти в критический интервал)

EnterCriticalSection(&Form1->CS);


...  доступ к глобальным данным

     // закрыть критический интервал (покинуть критический интервал)

LeaveCriticalSection(&Form1->CS);
   }
}
// Когда критический интервал становиться не нужен, удаляем его
void __fastcall TForm1::FormClose(TObject *Sender, TCloseAction &Action)
{
     DeleteCriticalSection(&CS); // удалить критический интервал
}

Защищенный доступ к переменным

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

InterlockedIncrement
InterlockedDecrement,
InterlockedExchange,
InterlockedExchangeAdd
InterlockedCompareExchange

Например, функция InterlockedIncrement увеличивает значение 32-битной переменной на единицу - удобно использовать для различных счетчиков.

TMultiReadExclusiveWriteSynchronizer

Методы

void BeginRead();

void EndRead();

bool BeginWrite();

void EndWrite();

TMultiReadExclusiveWriteSynchronizer

Нить 1

while(!Sync->BeginWrite()){

Sleep(1000);

Sync->EndWrite();

}

…

// обработка общего ресурса

…

Sync->EndWrite();

Нить 2

Sync->BeginRead();

…

// обработка общего ресурса

…

Sync->EndRead();

TCriticalSection

Методы

void Enter();

void Acquire();

void Leave();

void Release();

TCriticalSection

Нить 1

sect->Enter();

…

// обработка общего ресурса

…

sect->Leave();

TEvent

Методы

void ResetEvent()

void SetEvent()

TWaitResult WaitFor(int Timeout)

enum TWaitResult {

wrSignaled,

wrTimeout,

wrAbandoned,

wrError

};

TEvent

Нить 1

TWaitResult w;

w = Event->WaitFor(1000);

if(w == wrSignaled)

// дождались сигнала

else

// не дождались

Вопросы к экзамену

Параллельная обработка. Основные понятия. Средства обеспечения работы процессов.
Параллельная обработка. Средства реализации взаимных исключений и синхронизации нитей процессов.

Программное решение проблемы взаимного исключения
Двоичные семафоры
Простые критические интервалы
Мониторы

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

Объекты API
Классы VCL Borland C++ Builder

Декларативное программирование

История развития языков программирования

40гг. – первые цифровые компьютеры – программирование путем коммутации проводов.
программирование на машинном языке
появление ассемблеров – машинные команды получают мнемонические имена (LOAD, STORE, ADD, …)
конец 50х – создание первого компилятора для языка FORTRAN (FORmula TRANslator – транслятор формул)

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

История развития языков программирования

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

Парадигма языка программирования

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

Наклонения предложений в грамматике

изъявительное (повествовательные)
вопросительное
повелительное (императивное)

Изученные языки С/C++ относятся к императивным языкам.
Другие названия – директивные, процедурные.

Программирование в повествовательном наклонении

Стиль программирования, в котором программа представляется в как совокупность утверждений получил название декларативный.
Программа на императивном языке программирования предписывает, как достичь требуемую цель; декларативная программа заявляет (декларирует), что должно быть достигнуто в качестве цели.
Наиболее важные разновидности

функциональное программирование
логическое (реляционное) программирование

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

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

Не используют понятия состояния и не содержат переменных, отсюда:

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

Предположим, требуется пройти в городе из пункта А в пункт Б.

Декларативная программа - это план города, в котором указаны оба пункта, плюс правила уличного движения. Руководствуясь этими правилами и планом города, курьер сам найдет путь от пункта А к пункту Б.
Императивная программа - это список команд примерно такого рода: от пункта А по ул. Садовой на север до площади Славы, оттуда по ул. Пушкина два квартала, потом повернуть направо и идти до Театрального переулка, по этому переулку налево по правой стороне до дома 20, который и есть пункт Б.

Виды декларативного программирования

Функциональное программирование основывается на математическом понятии функции, которая не изменяет свое окружение (в отличии от функций в процедурных языках, допускающих побочные эффекты)
Логическое программирование - программы выражены в виде формул математической логики и компьютер для решения задачи пытается вывести логические следствия из них.

Достоинства декларативных языков

В основе декларативных языков лежит не какая-то машинная модель, а логика и математика.

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

Необходимость иметь дело только (или главным образом) с логическим компонентом значительно упрощает программирование.
Декларативные языки хорошо подходят для программирования параллельных компьютеров.
Пригодность для формальных рассуждений.

Недостатки декларативных языков

Существующие формы декларативного программирования плохо справляются с временными аспектами многих задач.
Отсутствует возможность адекватно выразить в программе естественный параллелизм задачи.
Низкая эффективность.

Логическое программирование

Основано на логике предикатов.
Основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру, что ему следует делать.
Наиболее известный язык логического программирования PROLOG (от французского PROgrammation LOGique)
Пролог часто называют языком искусственного интеллекта - с его помощью решаются задачи создания экспертных систем и систем обработки естественных языков.

Пролог

Как и для других декларативных языков, при работе с Прологом мы описываем ситуацию (правила и факты) и формулируем цель (запрос), позволяя интерпретатору Пролога найти решение задачи за нас.
Под интерпретатором Пролога мы будем понимать механизм решения задачи при помощи языка Пролог. Другими словами, интерпретатор языка Пролог - это исполнитель Пролог-программ, т. е. та "активная сила", которая выполняет программы, написанные на Прологе.

Круг задач Пролог

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

Программа на языке Пролог

Blog

40гг первые цифровые компьютеры программирование путем коммутации проводов

Содержание