Для выполнения на компьютере какой-либо программы необходимо, чтобы она имела доступ к ресурсам компьютера
| Вид материала | Документы |
СодержаниеВнутренняя память. Внешняя память. |
- Операционная система компьютера (назначение, состав, загрузка) Назначение, 99.73kb.
- Невырожденные матрицы обратная матрица, 27.2kb.
- Пример настоящей программы для компьютера на языке Лого 16 > Последовательность работы, 4798.61kb.
- Автор программы И. В. Баркова Ф. И. О., Педагога дополнительного образования; квалификационная, 224.25kb.
- Назначение и состав операционной системы компьютера. Загрузка компьютера, 95.4kb.
- Все программы и данные хранятся в долговременной (внешней) памяти компьютера в виде, 91.55kb.
- 1. Введение Ни одна страна, какой бы крупной и самообеспеченной важнейшими ресурсами, 1012.34kb.
- Белая Холуница Кировская область Описание проекта Название проекта Алгоритмы и основы, 179.54kb.
- Реферат «Защита информации» Ученица 9 класса Гагарина Надежда Руководитель элек- тивного, 55.96kb.
- Языки программирования, 27.65kb.
while (some condition) {
while(Test_and_Set(&lock));
critical section
lock = 0;
remainder section
}
К сожалению, даже в таком виде полученный алгоритм не удовлетворяет условию ограниченного ожидания для алгоритмов. Подумайте, как его следует изменить для соблюдения всех условий.
Команда Swap (обменять значения)
Выполнение команды Swap, обменивающей два значения, находящихся в памяти, можно проиллюстрировать следующей функцией:
void Swap (int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
Применяя атомарную команду Swap, мы можем реализовать предыдущий алгоритм, введя дополнительную логическую переменную key, локальную для каждого процесса:
shared int lock = 0;
int key;
while (some condition) {
key = 1;
do Swap(&lock,&key);
while (key);
critical section
lock = 0;
remainder section
}
Отключение прерываний
Когда в машине имеется лишь один процессор, параллельные процессы не могут перекрываться, а способны только чередоваться. Кроме того, процесс будет продолжаться до тех пор, пока не будет вызван сервис операционной системы или пока процесс не будет прерван. Следовательно, для того чтобы гарантировать взаимное исключение, достаточно защитить процесс от прерывания. Эта возможность может быть обеспечена в форме примитивов, определенных системным ядром для запрета и разрешения прерываний. Процесс в таком случае может обеспечить взаимоисключение следующим образом:
while (true){
/* Запрет прерываний */;
/* Критический раздел */;
/* Разрешение прерываний */;
/* Остальной код */;
}
Поскольку критический раздел не может быть прерван, выполнение взаимоисключения гарантируется. Однако цена такого подхода высока. Эффективность работы может заметно снизиться, поскольку при этом ограничена возможность процессора по чередованию программ. Другая проблема заключается в том, что такой подход не будет работать в многопроцессорной архитектуре. Если вычислительная система включает несколько процессоров, то вполне возможно (и обычно так и бывает), что одновременно выполняются несколько процессов. В этом случае запрет прерываний не гарантирует выполнения взаимоисключений.
17.
Инверсия приоритета
Изменение приоритета потоков обычно является поиском неприятностей. Инверсия приоритета может произойти, когда многие потоки с различным приоритетом имеют общий доступ к одним и тем же блокировкам и ресурсам, и поток с низким приоритетом практически до бесконечности задерживает работу потока с более высоким приоритетом. Мораль этой истории – просто избегайте изменений приоритетов потоков насколько это возможно.
Вот крайний пример инверсии приоритета. Представьте себе, что поток ThreadA с низким приоритетом получает блокировку L. Затем появляется поток ThreadB, имеющий высокий приоритет. Он пытается получить L, но не может, поскольку ее удерживает ThreadA. Это и есть «инверсия»: дело обстоит так, как если бы потоку ThreadA был искусственно и временно дан больший приоритет, чем у потока ThreadB, просто потому, что он удерживает блокировку, необходимую потоку ThreadB.
Эта ситуация со временем разрешится сама собой, когда поток ThreadA освободит блокировку. Увы, это еще не все – представьте, что произойдет, когда на сцене появится поток ThreadC со средним приоритетом. Хотя поток ThreadC не нуждается в блокировке L, его простое присутствие может полностью исключить выполнение потока ThreadA, что непрямым образом предотвратит выполнение высокоприоритетного потока ThreadB.
Рано или поздно эта ситуация будет замечена потоком диспетчера установки баланса Windows Balance Set Manager. Даже если поток ThreadC останется работоспособным навсегда, поток ThreadA со временем (через четыре секунды) получит временное повышение приоритета от ОС. Остается надеяться, что этого достаточно, чтобы он довел работу до завершения и освободил блокировку. Но задержка здесь огромна (четыре секунды), и если с этим связан какой-либо интерфейс пользователя, пользователь приложения наверняка заметит проблему.
18.
Семафоры - средство управления процессами
Семафоры традиционно использовались для синхронизации процессов, обращающихся к разделяемым данным. Каждый процесс должен исключать для всех других процессов возможность одновременно с ним обращаться к этим данным (взаимоисключение). Когда процесс обращается к разделяемым данным, говорят, что он находится в своем критическом участке.
Для решения задачи синхронизации необходимо, в случае если один процесс находится в критическом участке, исключить возможность вхождения для других процессов в их критические участки. Хотя бы для тех, которые обращаются к тем же самым разделяемым данным. Когда процесс выходит из своего критического участка, то одному из остальных процессов, ожидающих входа в свои критические участки, должно быть разрешено продолжить работу.
Процессы должны как можно быстрее проходить свои критические участки и не должны в этот период блокироваться. Если процесс, находящийся в своем критическом участке, завершается (возможно, аварийно), то необходимо, чтобы некоторый другой процесс мог отменить режим взаимоисключения, предоставляя другим процессам возможность продолжить выполнение и войти в свои критические участки.
Семафор - это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций wait и signal и операции инициализации init. Двоичные семафоры могут принимать только значения 0 и 1. Семафоры со счетчиками могут принимать неотрицательные целые значения.
Операция wait(s) над семафором s состоит в следующем:
если s > 0 то s:=s-1 иначе (ожидать на s)
а операция signal(s) заключается в том, что:
если (имеются процессы, которые ожидают на s)
то (разрешить одному из них продолжить работу)
иначе s:=s+1
Операции являются неделимыми. Критические участки процессов обрамляются операциями wait(s) и signal(s). Если одновременно несколько процессов попытаются выполнить операцию wait(s), то это будет разрешено только одному из них, а остальным придется ждать.
Семафоры со счетчиками используются, если некоторые ресурс выделяется из множества идентичных ресурсов. При инициализации такого семафора в его счетчике указывается число элементов множества. Каждая операция wait(s) уменьшает значения счетчика семафора s на 1, показывая, что некоторому процессу выделен один ресурс из множества. Каждая операция signal(s) увеличивает значение счетчика на 1, показывая, что процесс возвратил ресурс во множество. Если операция wait(s) выполняется, когда в счетчике содержится нуль (больше нет ресурсов), то соответствующий процесс ожидает, пока во множество не будет возвращен освободившийся ресурс, то есть пока не будет выполнена операция signal.
Монитор — это подход к синхронизации двух или более компьютерных задач, использующих общий ресурс, обычно аппаратуру или набор переменных. При многозадачности, основанной на мониторах, компилятор или интерпретатор прозрачно для программиста вставляет код блокировки-разблокировки в соответствующим образом оформленные процедуры, избавляя программиста от явного обращения к примитивам синхронизации.
Изобретён Пером Бринчем Хансеном, впервые воплощён в языке Concurrent Pascal и использован для структурирования межпроцессного взаимодействия в операционной системе Solo.
Взаимоисключительность
Монитор состоит из:
набора процедур, взаимодействующих с общим ресурсом
мьютекса
переменных, связанных с этим ресурсом
инварианта, который определяет условия, позволяющие избежать состояние гонки
Процедура монитора захватывает мьютекс перед началом работы и держит его или до выхода из процедуры, или до момента ожидания условия (см. ниже). Если каждая процедура гарантирует, что перед освобождением мьютекса инвариант истиннен, то никакая задача не может получить ресурс в состоянии, ведущем к гонке.
Простой пример. Рассмотрим монитор, выполняющий транзакции банковского счёта.
monitor account {
int balance := 0
function withdraw(int amount) {
if amount < 0 then error "Счёт не может быть отрицательным"
else if balance < amount then error "Недостаток средств"
else balance := balance - amount
}
function deposit(int amount) {
if amount < 0 then error "Счёт не может быть отрицательным"
else balance := balance + amount
}
}
Инвариант здесь просто утверждает, что баланс должен отразить все прошедшие операции до того, как начнётся новая операция. Обычно это не выражено в коде, но подразумевается и может быть упомянуто в комментариях. Однако, есть языки программирования, такие как Эйфель, которые могут проверять инварианты. Блокировка добавлена компилятором. Это делает мониторы безопаснее и удобнее, чем другие подходы, требующие от программиста вручную добавлять операции блокировки-разблокировки, - поскольку программист может забыть добавить их.
19.
Определение семафора
Семафор — это объект, с которым можно выполнить три операции.
init(n):
счётчик := n
enter():
ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.
leave():
увеличить счётчик на единицу.
Предположим, что есть такой участок кода:
semaphore.init(5);
.....
.....
semaphore.enter();
DoSomething();
semaphore.leave();
Тогда не более пяти потоков могут одновременно выполнять функцию DoSomething().
В более сложных семафорах может использоваться очередь; при этом потоки, ожидающие освобождения семафора, будут проходить через семафор именно в том порядке, в котором они вызывали enter().
Мьютексы (mutex) — это один из вариантов семафорных механизмов для организации взаимного исключения. Они реализованы во многих ОС, их основное назначение — организация взаимного исключения для потоков из одного и того же или из разных процессов.
Мьютексы — это простейшие двоичные семафоры, которые могут находиться в одном из двух состояний — отмеченном или неотмеченном (открыт и закрыт соответственно). Когда какой-либо поток, принадлежащий любому процессу, становится владельцем объекта mutex, последний переводится в неотмеченное состояние. Если задача освобождает мьютекс, его состояние становится отмеченным.
Организация последовательного доступа к ресурсам с использованием мьютексов становится несложной, поскольку в каждый конкретный момент только один поток может владеть этим объектом. Для того, чтобы объект mutex стал доступен потокам, принадлежащим разным процессам, при создании ему необходимо присвоить имя. Потом это имя нужно передать «по наследству» задачам, которые должны его использовать для взаимодействия. Для этого вводятся специальные системные вызовы (CreateMutex), в которых указывается начальное значение мьютекса и его имя.
20
Мониторы.
Семафоры предоставляют мощный и гибкий механизм реализации безопасного межпроцессного взаимодействия. Однако гибкость всегда имеет обратную сторону – программы, создаваемые с использованием таких средств, подвержены ошибкам, причиной которых является их неизбежно повышенный уровень сложности. В качестве иллюстрации можно опять обратиться к программе из листинга 16. Вы уже видели, что случайное изменение порядка вызовов примитивов синхронизации способно сделать программунеработоспособной, притом это не слишком очевидно. А ведь это всего лишь коротенький учебный пример. Ошибки, связанные с неправильным использованием семафоров, могут приводить к непредсказуемым и невоспроизводимым критическим состояниям вычислительной системы.Отсюда очевидна необходимость, в первую очередь для целей прикладного программирования, иметь средство синхронизации болеевысокого уровня, которое могло бы обеспечить повышение надежности параллельных программ. Таким средством стали мониторы, предложенные Хоаром (Hoare) и Бринч Хансеном (Brinch Hansen) в 1974 г. Основная идея состоит в том, чтобы «спрятать» защищаемый ресурс внутрь объекта, обеспечивающего взаимоисключения.
Мониторы с сигналами. Монитор (версия Хоара - Хансена) представляет собой программный модуль, состоящий из инициализирующей последовательности, одной или,нескольких процедур и локальных данных. Основные характеристики: 1. Локальные переменные монитора доступны только его процедурам; внешние процедуры доступа к локальным данным монитора не имеют. 2. Процесс входит в монитор путем вызова одной из его процедур. 3. В мониторе в определенный момент времени может выполняться только один процесс; любой другой процесс, вызвавший монитор, будет приостановлен в ожидании доступности монитора. Очевидно (требования 1,2), объектно ориентированные ОС или языки программирования могут легко реализовать монитор как объект со специальными характеристиками. Соблюдение требования 3 позволяет монитору обеспечить взаимоисключения. Если данные в мониторе представляют некий ресурс, то монитор обеспечивает взаимоисключение при обращении к ресурсу. Для применения в параллельных вычислениях мониторы должны обеспечивать синхронизацию. Пусть находясь в мониторе должен быть приостановлен до выполнения некоторого условия. При этом требуется механизм, который не только приостанавливает П, но и освобождает монитор, позволяя войти в него другому П. Позже, по выполнению условия, и когда монитор станет доступным, приостановленный П сможет продолжить свою работу . Монитор поддерживает синхронизацию при помощи переменных условия, располагающихся и доступных только в мониторе. Работать с этими переменными могут две ф-ции.
cwait(c): приостанавливает выполнение вызывающего П по условию c. Монитор при этом доступен для использования другим П.
• csignal(c): возобновляет выполнение некоторого П, приостановленного вызовом cwait с тем же условием. Если имеется несколько таких П, выбирается один из них; если таких П нет, ф-ция не делает ничего. Как видим, операции cwait/csignal монитора отличаются от соотв. операций семафора. Если П в мониторе передает сигнал, но при этом нет ни одного ожидающего его П, то сигнал просто теряется. Это значит, что переменные условия, в отличие от семафоров, не являются счетчиками. В качестве иллюстрации использования монитора повторим решение задачи производитель/потребитель с ограниченным буфером:
Мониторы с оповещением и широковещанием.
Хоаровское определение мониторов требует, чтобы в случае, если очередь ожидания выполнения условия не пуста, при выполнении каким- либо П операции csignal для этого условия был немедленно запущен из указанной очереди. Т.о., выполнивший csignal П должен либо немедленно выйти из монитора, либо быть приостановленным. У такого подхода 2 недостатка:
1. Если выполнивший csignal П не завершил свое пребывание в мониторе, то требуется 2 дополнительных переключения П: для приостановки данного П и для возобновления его, когда монитор станет доступен.
2. Планировщик П, связанный с сигналом, должен быть идеально надежен. При выполнении csignal П из соответствующей очереди должен быть немедленно активизирован до того, как в монитор войдет другой П и условие активации при этом может измениться. В результате возможна взаимная блокировка всех П, связанных с данным условием.
Lampson и Redell разработали другое определение монитора для языка Mesa (такая же структура монитора использована и в языке Modula-3). Примитив csignal заменен примитивом cnotify(x), который интерпретируется след. образом. Если П, выполняющийся в мониторе, вызывает cnotify(x), об этом оповещается очередь условия х, но выполнение П продолжается. Результат оповещения состоит в том, что П в
начале очереди условия возобновит свою работу в ближайшем будущем, когда монитор окажется свободным. Однако, поскольку нет гарантии, что другой П не войдет в монитор раньше, при возобновлении работы должен проверить, выполнено ли условие. Инструкции if заменены циклами while; таким образом, будет выполняться как минимум одно лишнее вычисление переменной условия. Однако в этом случае отсутствуют лишние переключения П и не имеется ограничений на момент запуска ожидающего П. Важно, что для монитора Лемпсона-Ределла можно ввести предельное время ожидания, связанное с примитивом cnotify. П, который прождал уведомления в течении предельного времени, помещается в очередь активных, независимо от того, было ли уведомление о выполнении условия. При активации П проверяет выполнение условия и либо продолжает работу, либо опять блокируется. Это предотвращает голодание в случае, если другие П сбоят перед уведомлением о выполнении условия.
Также в систему команд можно включить примитив cbroadcast (широковещательное сообщение), который вызывает активизацию всех ожидающих П. Это удобно, когда уведомляющий П не знает о количестве ожидающих П или не в состоянии определить, который П надо вызвать. Дополнительным преимуществом монитора Лемпсона-Ределла перед монитором Хоара, является меньшая подверженность ошибкам. Если пришло ложное оповещение, П все равно проверит выполнение условия. Мониторы являются структурным компонентом языка программирования и ответственность на организации взаимного исключения лежит на компиляторе. Последний обычно использует мьютексы и переменные условий. Часто ОС предоставляют поддержку реализации мониторов именно через эти средства. Типовым представителем языков программирования, в котором мониторы являются основным средством синхронизации потоков, является
Java. Добавление в описание метода ключевого слова synchronized гарантирует, что если один поток начал выполнение этого метода, ни один другой поток не сможет выполнять другой синхронизированный метод из этого класса. Т. е., в языке Java у каждого объекта, имеющего синхронизованные методы, есть связанный с ним монитор. Общим недостатком семафоров и мониторов является то, что они расчитаны на работу в одно- или многопроцессорной вычислительной системе с общей памятью. Если система состоит из нескольких процессоров, каждый из которых имеет свою собственную память, а связь между ними осуществляется через каналы ввода/вывода, ни один из рассмотренных выше механизмов реализации взимоисключений не работоспособен. В этом случае возможно только сотрудничество П с использованием связи.
21
Передача сообщений
В роли чего-то другого выступает передача сообщений. Этот метод межпроцессного взаимодействия использует два примитива: send и receive, которые скорее являются системными вызовами, чем структурными компонентами языка (что отличает их от мониторов и делает похожим на семафоры). Поэтому их легко можно поместить в библиотечные процедуры, например send(destination, Smessage); receive(source. Smessage);
Первый запрос посылает сообщение заданному адресату, а второй получает сообщение от указанного источника (или от любого источника, если это не имеет значения). Если сообщения нет, второй запрос блокируется до поступления сообщения либо немедленно возвращает код ошибки. Разработка систем передачи сообщений. С системами передачи сообщений связано большое количество сложных проблем и конструктивных вопросов, которых не возникает в случае семафоров и мониторов. Особенно много сложностей появляется в случае взаимодействия процессов, происходящих на различных компьютерах, соединенных сетью. Так, сообщение может потеряться в сети. Чтобы избежать потери сообщений, отправитель и полу- получатель договариваются, что при получении сообщения получатель посылает обратно подтверждение приема сообщения. Если отправитель не получает подтверждения через некоторое время, он отсылает сообщение еще раз. Теперь представим, что сообщение получено, но подтверждение до отправите- отправителя не дошло. Отправитель пошлет сообщение еще раз, и до получателя оно дойдет дважды. Крайне важно, чтобы получатель мог отличить копию предыдущего со- сообщения от нового. Обычно проблема решается с помощью помещения порядкового номера сообщения в тело самого сообщения. Если к получателю приходит письмо с номером, совпадающим с номером предыдущего письма, письмо классифицируется как копия и игнорируется. Решение проблемы успешного обмена информации в условиях ненадежной передачи сообщений составляет основу изучения компьютерных сетей. Для систем обмена сообщениями также важен вопрос названий процессов. Не- Необходимо однозначно определять процесс, указанный в запросе send или receive. Кроме того, встает вопрос аутентификации: каким образом клиент может определить, что он взаимодействует с настоящим файловым сервером, а не с само- самозванцем? Помимо этого, существуют конструктивные проблемы, существенные при рас- расположении отправителя и получателя на одном компьютере. Одной из таких про- проблем является производительность. Копирование сообщений из одного процесса в другой происходит гораздо медленнее, чем операция на семафоре или вход в мо- монитор. Было проведено множество исследований с целью увеличения эффективности передачи сообщений. Решение проблемы производителя и потребителя с передачей сообщений
Теперь рассмотрим решение проблемы производителя и потребителя с передачей сообщений и без использования разделенной памяти. Мы предполагаем, что все сообщения имеют одинаковый размер и сообщения, которые посланы, но еще не получены, автоматически помещаются операционной системой в буфер. В этом решении используются N сообщений, по аналогии с N сегментами в буфере. Потребитель начинает с того, что посылает про- производителю N пустых сообщений. Как только у производителя оказывается эле- элемент данных, который он может предоставить потребителю, он берет пустое сообщение и отсылает назад полное. Таким образом, общее число сообщений в системе постоянно и их можно хранить в заранее заданном участке памяти. Если производитель работает быстрее, чем потребитель, все сообщения будут ожидать потребителя в заполненном виде. При этом производитель блокируется в ожидании пустого сообщения. Если потребитель работает быстрее, ситуация инвертируется: все сообщения будут пустыми, а потребитель будет блокирован в ожидании полного сообщения. Передача сообщений может быть реализована по-разному. Рассмотрим способ адресации сообщений. Можно присвоить каждому из процессов уникальный адрес и адресовать сообщение непосредственно процессам. Другой подход состо- состоит в использовании новой структуры данных, называемой почтовым ящиком. По- Почтовый ящик — это буфер для определенного количества сообщений, тип которых задается при создании ящика. При использовании почтовых ящиков в качестве параметров адреса send и receive задаются почтовые ящики, а не процессы. Если процесс пытается послать сообщение в полный почтовый ящик, ему приходится подождать, пока хотя бы одно сообщение не будет удалено из ящика. В задаче производителя и потребителя оба они создадут почтовые ящики, достаточно большие, чтобы хранить TV сообщений. Производитель будет посылать со- сообщения с данными в почтовый ящик потребителя, а потребитель будет посылать пустые сообщения в почтовый ящик производителя. С использованием почтовых ящиков метод буферизации очевиден: в почтовом ящике получателя хранятся со- сообщения, которые были посланы процессу-получателю, но еще не получены. Другим предельным случаем использования почтовых ящиков является принципиальное отсутствие буферизации. При таком подходе, если send выполняется раньше, чем receive, посылающий процесс блокируется до выполнения receive, когда сообщение может быть напрямую скопировано от отправителя к получателю без промежуточной буферизации. Если receive выполняется раньше, чем send, получающий процесс блокируется до выполнения send. Этот метод часто называется рандеву, он легче реализуется, чем схема буферизации сообщений, но менее гибок, поскольку отправитель и получатель должны работать в режиме жесткой синхронизации. Передача сообщений часто используется в системах с параллельным программированием. Характерным примером системы передачи сообщений является MPI
(Message-Passing Interface — интерфейс передачи сообщений).
22
.При любом виде взаимодействия процессам необходима взаимная синхронизация. Существуют два основных вида синхронизации — взаимное исключение и условная синхронизация. Взаимное исключение обеспечивает, чтобы критические секции операторов не выполнялись одновременно. Условная синхронизация задерживает процесс до тех пор, пока не выполнится определенное условие. Например, взаимодействие процессов производителя и потребителя часто обеспечивается с помощью буфера с разделяемой памяти. Производитель записывает в буфер, потребитель читает из него. Чтобы предотвратить одновременное использование буфера и производителем, и потребителем (тогда может быть считано не полностью записанное сообщение), используется взаимное исключение. Условная синхронизация используется для проверки, было ли считано потребителем последнее записанное в буфер сообщение.
23Решение проблемы producer-consumer с помощью семафоров
Одной из типовых задач, требующих организации взаимодействия процессов, является задача producer-consumer (производитель-потребитель). Пусть два процесса обмениваются информацией через буфер ограниченного размера. Производитель закладывает информацию в буфер, а потребитель извлекает ее оттуда. Грубо говоря, на этом уровне деятельность потребителя и производителя можно описать следующим образом.
Producer: while(1) {
produce_item;
put_item;
}
Consumer:
while(1) {
get_item;
consume_item;
}
Если буфер забит, то производитель должен ждать, пока в нем появится место, чтобы положить туда новую порцию информации. Если буфер пуст, то потребитель должен дожидаться нового сообщения. Как можно реализовать эти условия с помощью семафоров? Возьмем три семафора empty, full и mutex. Семафор full будем использовать для гарантии того, что потребитель будет ждать, пока в буфере появится информация. Семафор empty будем использовать для организации ожидания производителя при заполненном буфере, а семафор mutex - для организации взаимоисключения на критических участках, которыми являются действия put_item и get_item (операции положить информацию и взять информацию не могут пересекаться, так как тогда возникнет опасность искажения информации). Тогда решение задачи выглядит так:
Semaphore mutex = 1;
Semaphore empty = N, где N – емкость буфера;
Semaphore full = 0;
Producer:
while(1) {
produce_item;
P(empty);
P(mutex);
put_item;
V(mutex);
V(full);
}
Consumer:
while(1) {
P(full);
P(mutex);
put_item;
V(mutex);
V(empty);
consume_item;
}
Легко убедиться, что это действительно корректное решение поставленной задачи. Попутно заметим, что семафоры использовались здесь для достижения двух целей: организации взаимоисключения на критическом участке и синхронизации скорости работы процессов.
24. Задача "читатели — писатели". Имеется разделяемый ресурс — область памяти, к которой требуется доступ процессам двух типов:
Процессы первого типа — "ЧИТАТЕЛИ" — могут получать доступ к разделяемому ресурсу одновременно. Они считывают информацию.
Процессы второго типа — "ПИСАТЕЛИ" — взаимно исключают и друг друга, и "читателей". Они записывают в разделяемую область памяти данные.
Задача известна в двух вариантах:
"Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее; это — первая задача ЧП.
2. "Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее, если отсутствуют запросы от "писателей". "Писатель", требующий доступ к ресурсу, должен получить его как можно быстрее, но после обслуживания "читателей", подошедших к ресурсу до первого "писателя". Это — вторая задача ЧП.
Приведем возможное решение задач с помощью комбинированного семафора.
Считаем, что процедура ОТКРЫТЬ ПО СЧИТЫВАНИЮ выполняется подобно процедуре ПРОПУСТИТЬ, изменяя только значение семафора-счетчика. Процедура ОТКРЫТЬ ПО ЗАПИСИ выполняется подобно процедуре ОТКРЫТЬ, "открывая" семафор и обеспечивая запуск "задержанных" процессов с процедур ЗАКРЫТЬ ПО ЗАПИСИ или ЖДАТЬ ПО ЗАПИСИ, при выполнении которых произошло прерывание.
Тогда критические интервалы для каждой задачи могут быть выполнены по следующим схемам.
25 Семафоры
Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году.
Концепция семафоров
Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: P (от датского слова proberen — проверять) и V (от verhogen — увеличивать). Классическое определение этих операций выглядит следующим образом:
P(S): | пока S == 0 процесс блокируется; |
V(S): | S = S + 1; |
Эта запись означает следующее: при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1. Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. При выполнении операции V над семафором S к его значению просто прибавляется 1.
П
одобные переменные-семафоры могут быть с успехом применены для решения различных задач организации взаимодействия процессов. В ряде языков программирования они были непосредственно введены в синтаксис языка (например, в ALGOL-68), в других случаях применяются через использование системных вызовов. Соответствующая целая переменная располагается внутри адресного пространства ядра операционной системы. Операционная система обеспечивает атомарность операций P и V, используя, например, метод запрета прерываний на время выполнения соответствующих системных вызовов. Если при выполнении операции P заблокированными оказались несколько процессов, то порядок их разблокирования может быть произвольным, например, FIFO.
Мониторы
Хотя решение задачи producer-consumer с помощью семафоров выглядит достаточно элегантно, программирование с их использованием требует повышенной осторожности и внимания, чем, отчасти, напоминает программирование на языке ассемблера. Допустим, что в рассмотренном примере мы случайно поменяли местами операции P, сначала выполняя ее для семафора mutex, а уже затем для семафоров full и empty. Допустим теперь, что потребитель, войдя в свой критический участок (mutex сброшен), обнаруживает, что буфер пуст. Он блокируется и начинает ждать появления сообщений. Но производитель не может войти в критический участок, для передачи информации, так как тот заблокирован потребителем. Получаем тупиковую ситуацию.
В сложных программах произвести анализ правильности использования семафоров с карандашом в руках становится очень непростым занятием. В то же время обычные способы отладки программ зачастую не дают результата, поскольку возникновение ошибок зависит от interleaving’а атомарных операций, и ошибки могут быть трудно воспроизводимы. Для того чтобы облегчить труд программистов, в 1974 году Хором (Hoare) был предложен механизм еще более высокого уровня, чем семафоры, получивший название мониторов. Мы с вами рассмотрим конструкцию, несколько отличающуюся от оригинальной.
Мониторы представляют собой тип данных, который может быть с успехом внедрен в объектно-ориентированные языки программирования. Монитор обладает своими собственными переменными, определяющими его состояние. Значения этих переменных извне монитора могут быть изменены только с помощью вызова функций-методов, принадлежащих монитору. В свою очередь, эти функции-методы могут использовать в своей работе только данные, находящиеся внутри монитора и свои параметры. На абстрактном уровне можно описать структуру монитора следующим образом:
monitor monitor_name {
описание переменных ;
void m1(...){...
}
void m2(...){...
}
...
void mn(...){...
}
{
блок инициализации внутрениих переменных ;
}
}
Здесь функции m1,..., mn представляют собой функции-методы монитора, а блок инициализации внутренних переменных содержит операции, которые выполняются только один раз: при создании монитора или при самом первом вызове какой-либо функции-метода до ее исполнения.
Важной особенностью мониторов является то, что в любой момент времени только один процесс может быть активен, т. е. находиться в состоянии готовность или исполнение, внутри данного монитора. Поскольку мониторы представляют собой особые конструкции языка программирования, то компилятор может отличить вызов функции, принадлежащей монитору, от вызовов других функций и обработать его специальным образом, добавив к нему пролог и эпилог, реализующий взаимоисключение. Так как обязанность конструирования механизма взаимоисключений возложена на компилятор, а не на программиста, работа программиста при использовании мониторов существенно упрощается, а вероятность появления ошибок становится меньше.
Однако одних только взаимоисключений не достаточно для того, чтобы в полном объеме реализовать решение задач, возникающих при взаимодействии процессов. Нам нужны еще и средства организации очередности процессов, подобно семафорам full и empty в предыдущем примере. Для этого в мониторах было введено понятие условных переменных (condition variables), над которыми можно совершать две операции wait и signal, до некоторой степени похожие на операции P и V над семафорами.
Если функция монитора не может выполняться дальше, пока не наступит некоторое событие, она выполняет операцию wait над какой-либо условной переменной. При этом процесс, выполнивший операцию wait, блокируется, становится неактивным, и другой процесс получает возможность войти в монитор.
Когда ожидаемое событие происходит, другой процесс внутри функции-метода совершает операцию signal над той же самой условной переменной. Это приводит к пробуждению ранее заблокированного процесса, и он становится активным. Если несколько процессов дожидались операции signal для этой переменной, то активным становится только один из них. Что нам нужно предпринять для того, чтобы у нас не оказалось двух процессов, разбудившего и пробужденного, одновременно активных внутри монитора? Хор предложил, чтобы пробужденный процесс подавлял исполнение разбудившего процесса, пока он сам не покинет монитор. Несколько позже Хансен (Hansen) предложил другой механизм: разбудивший процесс покидает монитор немедленно после исполнения операции signal. Мы будем придерживаться подхода Хансена.
Давайте применим концепцию мониторов к решению задачи производитель-потребитель .
monitor ProducerConsumer {
condition full, empty;
int count;
void put() {
if(count == N) full.wait;
put_item;
count += 1;
if(count == 1) empty.signal;
}
void get() {
if (count == 0) empty.wait;
get_item();
count -= 1;
if(count == N-1) full.signal;
}
{
count = 0;
}
}
Producer:
while(1) {
produce_item;
ProducerConsumer.put();
}
Consumer:
while(1) {
ProducerConsumer.get();
consume_item;
}
Легко убедиться, что приведенный пример действительно решает поставленную задачу. Реализация мониторов требует разработки специальных языков программирования и компиляторов для них. Мониторы встречаются в таких языках как параллельный Евклид, параллельный Паскаль, Java и т.д. Эмуляция мониторов с помощью системных вызовов для обычных широко используемых языков программирования не так проста, как эмуляция семафоров. Поэтому можно пользоваться еще одним механизмом со скрытыми взаимоисключеньями, механизмом, о котором мы уже упоминали, — передачей сообщений.
26.
Механизмы параллельной обработки в ОС семейства Windows
В ОС Windows предоставлено семейство следующих объектов синхронизации:
Процесс
Поток
Файл
Консольный ввод
Уведомление об изменении файлов
Мьютекс
Семафор
Событие
Таймер ожидания
Экземпляр каждого из перечисленных объектов может находится в одном из двух состояний сигнальном(signaled) и несигнальном(unsignaled). Поток освобождается при входе объекта в сигнальное состояние. Механизм достаточно прост: поток выполняет запрос на ожидание к исполнительной системе с использованием дескриптора объекта синхронизации. Когда объект входит в сигнальное состояние, исполнительная система освобождает все потоки находящиеся в состоянии ожидания этого объекта.
Мьютексы. Мьютексы используются для взаимоисключительного доступа к ресурсам, благодаря им обеспечивается получение доступа к ресурсу одновременно только одним объектом.
Таймер ожидания. Объект ядра который подаёт сигнал в определённый момент времени и/или через заданные промежутки времени.
27. Механизмы параллельной обработки в ОС семейства UNIX
Важнейшие механизмы параллельной обработки, это:
Каналы
Сообщения
Разделяемая память
Семафоры
Сигналы
Каналы. Они представляют собой циклические буфера которые позволяют процессам связываться друг с другом в соответствии с моделью производитель/потребитель. Поэтому канал это очередь работающая по принципу «первым вошёл – первым вышел», запись в которую осуществляется одним процессом, а чтение другим. Существует 2 типа каналов: именованные и неименованные. Совместно использовать неименованные каналы, могут только связанные между собой процессы, а несвязанные могут совместно использовать лишь неименованные каналы.
Сообщения. Сообщение представляет собой блок текста определённого типа. С каждым процессом связана очередь сообщений, функционирующая подобно почтовому ящику. Указанный отправителем тип сообщений, может быть использован получателем как критерий отбора сообщений. Он может получать сообщения либо в соответствии с принципом «первым вошёл – первым вышел», либо в соответствии с их типом.
Разделяемая память. Это общий блок виртуальной памяти, совместно используемой многими процессами
Семафоры. Семафор — объект, позволяющий войти в заданный участок кода не более чем n потокам. С семафором можно выполнить 3 операции:
Семафор может быть инициализирован неотрицательным значением
Можно уменьшить значение семафора командой wait()
Можно увеличить значение семафора командой signal()
Сигналы. Сигнал представляет собой программный механизм информирующий процесс о наступлении асинхронного события. Сигнал подобен аппаратному прерыванию, но не использует систему приоритетов. Процессы могут посылать сигналы друг другу, в обмене сигналами может принимать участие и ядро. Сигнал обрабатывается сразу же после активизации процесса, или возврата его из системного вызова.
28. Принципы взаимоблокировок. Предотвращение взаимоблокировок
Взаимоблокировка – это ситуация при которой группа процессов находится в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из той же группы. Т.к. все процессы находятся в состоянии ожидания, ни один из них не будет причиной события способного активировать другой процесс в группе, поэтому ситуация остаётся тупиковой до бесконечности. В основном событие которого ждёт каждый процесс возвращает какой-либо ресурс, занятый в данный момент другим участником группы.
4 ОБЯЗАТЕЛЬНЫХ условия взаимоблокировок:
Условие взаимного исключения. Каждый ресурс в данный момент или отдан ровно одному процессу, или недоступен.
Условие удержания и ожидания. Процессы в данный момент удерживающие ресурс, могут запрашивать новый ресурс.
Условие отсутствия принудительной выгрузки ресурса. У процесса нельзя принудительным образом забрать ранее полученный ресурс, процесс владеющий им должен сам освободить ресурс.
Условие циклического ожидания. Должна существовать круговая последовательность из двух и более процессов, каждый из которых ждёт доступа к ресурсу, удерживаемому следующим членом последовательности.
Взаимоблокировки можно избежать, отслеживая которое состояние является безопасным а которое нет. Безопасное состояние – это то в котором существует последовательность действий, гарантирующая что все процессы смогут окончить свою работу. Алгоритм банкира избегает тупиков, не выполняя запрос, если тот приводит систему в небезопасное состояние. Также взаимоблокировки можно предотвратить структурно, построив систему так, что тупиковая ситуация никогда не возникнет по построению. Например позволить использовать процессу только 1 ресурс в любой момент времени. Взаимоблокировки ещё можно предотвратить, пронумеровав все ресурсы и требовать от процессов создания процессов в строго возрастающем порядке.
29 П А М Я Т Ь
----------------------------------------------------------------- Память-это совокупность микpосхем, пpедназначенных для хpанения инфоpмации (данных, пpогpамм, команд).
-----------------------------------------------------------------
Основной характеристикой памяти является емкость.
Емкость памяти - это максимальный объем хpанимой инфоpмации, измеpяемой в байтах.
Память ЭВМ постpоена из двоичных запоминающих элементов - битов (от binary digit - двоичная цифpа), объединенных в гpуппы по 8 битов, котоpые называются байтами. Все байты пронумерованы. Hомеp байта называется адpесом. Каждый байт информации доступен по указанию его адреса. Адресная шина процессора находит требуемую ячейку памяти по указанному процессором адресу. Т.о. адресация памяти процессором ограничена разрядностью адресной шины и равна двум в степени разрядности адресной шины: для 8080 - 220=1 Мегабайт
80286 - 224=16 Мегабайт
80386 и т.д. - 232= 4 Гигабайт
Единицы измеpения инфоpмации:
1 байт - 8 бит
1 Килобайт - 1024 байта
1 Мегабайт - 1024 Кбайта
1 Гигабайт - 1024 Мбайта
1 Теpабайт - 1024 Гбайта
В ПК существует два вида памяти: внутpенняя и внешняя.
ВНУТРЕННЯЯ ПАМЯТЬ.
Внутренняя память - это память, к которой процессор может обратиться непосредственно в процессе работы и немедленно использовать ее.
К внутpенней памяти относятся:
1. Постоянная память (ПЗУ или ROM - Read Only Memory) - используется для хpанения данных, котоpые никогда не тpебуют изменения.
Содеpжимое памяти заносится на заводе-изготовителе.
В ПЗУ записывают пpогpамму упpавления pаботой пpоцессоpа, пpогpамму упpавления монитоpом, клавиатуpой, пpинтеpом, внешней памятью, пpогpаммы запуска и остановки ПК, тестиpования устpойств.
Инфоpмация, занесенная в ПЗУ пpедназначена только для чтения (read only). Вся информация, хранимая в ПЗУ энергонезависима, т.е. при выключении ПК она сохраняется. Объем ПЗУ невелик - измеряется в килобайтах. Микросхемы ПЗУ устанавливаются на "материнской" плате, расположенной в системном блоке.
2. Опеpативная память (ОЗУ или RAM -Random Acscess Memory) - этот вид памяти пpедназначен для временного хpанения информации и содержит обрабатываемые процессором в данный момент программы и данные. Распределение этой памяти осуществляется автоматически в процессе исполнения программ, которые перед началом работы загружаются в ОЗУ с жесткого диска или дискеты.
Это энеpгозависимый вид памяти - пpи выключении ПК содеpжимое памяти стиpается. Объем опеpативной памяти - от 8 до 64 Mb. Модули ОЗУ находятся на "материнской" плате.
3. КЭШ-память (cache) - это свеpхопеpативная память, пpедназначенная для обмена данными между пpоцессоpом и ОЗУ, т.е. является буфеpом между ними. Используется для вpеменного хpанения пpомежуточных данных.
МП <--> КЭШ <--> ОЗУ
Hаличие КЭШ-памяти увеличивает пpоизводительность ПК. Объем КЭШ-памяти зависит от объема опеpативной памяти. КЭШ-память может иметь объем: 64, 128, 256, 512 Kb. Для ОЗУ в 8 Mb достаточно КЭШ pазмеpом 256 Kb, для ОЗУ в 16 Mb - 512 Kb.
ВНЕШНЯЯ ПАМЯТЬ.
Внешняя память (ВЗУ) - это вид памяти, пpедназначенный для долговpеменого хpанения инфоpмации. Этот вид памяти обладает большим объемом и маленьким быстpодействием.
К внешней памяти относятся:
- накопители на гибких магнитных дисках 5.25" и 3.5"
( FDD - Floppy Disk Drive);
- накопители на жестких магнитных дисках типа "винчестеp"
( HDD - Hard Disc Drive);
- накопители типа CD-ROM.
-
П А М Я Т Ь
