1. Виртуальная память: управление памятью страницами по запросу – три схемы. Алгоритмы вытеснения страниц: демонстрация особенностей на модели траектории страниц. Рабочее множество – определение, глобальное и локальное замещение. Флаги в дескрипторах страниц, предназначенные для реализации замещения страниц.
2. Синхронизация и взаимоисключение параллельных процессов в распределенных системах: централизованный и распределенный алгоритмы, алгоритмы Token-ring; сравнение алгоритмов. Транзакции: определение, особенности, двухфазный протокол фиксации.
Стали делить память на страницы. Можно выполнить программу, которая находится не целиком в памяти. Для этого нужно содержать части кода с которыми в текущий момент работает процессор. Это воплотилось в понятие виртуальная память.
Виртуальная память – память, размер которой превышает размер реального физического пространства.
Существует 3 схемы управления ВП (Виртуальной Памятью):
- управление памятью страницами по запросам;
- управление памятью сегментами по запросам;
- управление памятью сегментами, поделенными на страницы по запросам.
Управление памятью страницами по запросу - три схемы преобразования
Существует три схемы преобразования виртуального адреса в физический.
1. Прямое отображение.
Таблица страниц находится в оперативной памяти. Таких страниц столько - сколько процессов. В процессоре должен находится регистр начального адреса таблицы страниц.
Виртуальный адрес состоит из двух частей.
- Смещение d.
- Номер страницы p.
Номер страницы используется как смещение дескриптора страницы в таблице страниц. Если страница загружена в память, то выполняя преобразование мы можем получить линейный физический адрес. Если страница не загружена в память, то возникнет страничное исключение
2. Ассоциативное отображение.
В чистом виде не используется.
Использование ассоциативной памяти – память, которая обеспечивает выборку по ключу за 1 такт.
Выборка осуществляется за 1 такт за счет специальной схемы.
3. Ассоциативное – прямое отображение.
Комбинация первых двух методов.
Если весь физический адрес занят, то нужно выгрузить страницу.
Способы.
1. Выталкивание случайной страницы (первая попавшееся). Для замены выбирается любая случайная страница.
Недостатки:
- Может быть вытолкнута часто используемая или только что загруженная страница.
Преимущества:
- Малые накладные расходы
2. FIFO. Выталкивается та, которая дольше всего находится в памяти.
Для реализации этого способа нужно организовать очередь либо хранить время.
Аномалия FIFO: (особенность) Существуют такие траектории загрузки страниц, когда увеличение страничной памяти ведет к увеличению страничных прерываний.
"+" - страничное прерывание (загружается в результате страничного прерывания). Если нужно загрузить страницу, которая в памяти (страничная удача), то очередь не редактируется (так и остается в очереди на старом месте).
Сначала рассматриваем память размером 3 страницы
Увеличим страничную память
Этот алгоритм исключает возможность выгрузки только что загруженной страницы, но не исключает выгрузку часто используемой.
Недостаток:
- Может быть выгружена часто используемая страница.
3. LRV (Least Recently Used): замещаем наименее используемую страницу.
Для реализации этого способа нужно хранить временные метки, которые редактируются при каждом обращении, либо список, каждый раз в конец которого кладем только что используемую. В начале списка будет менее использованная страница.
Увеличим страничную память
Свойство включения: (особенность) Если какая-то страница выбрана при реализации с объемом памяти M, то этаже страница при такой же траектории будет выбрана, если память M+1 страниц (т.к. она полностью соответствует свойству локальности).
Недостатки:
- Большие накладные ресурсы.
4. LFU (Least Frequency Used): Наименее часто используемая в последнее время.
В этом способе контролируется частота обращения к странице (количество обращений).
Недостаток:
- Может быть вытеснена только что загруженная страница, не набравшая число обращений.
5. NUR (Not Used Recently): аппроксимирует LRU.
Каждому кадру физической памяти приписывается бит обращения. Работа с битом: Вытесняется страница с битом обращения равным 0. Устанавливается в 1, когда страница загружается в какой-то кадр. Обновляется каждый раз при обращении. Периодически все биты обращений сбрасываются в 0.
Показывает состояние оперативной памяти после загрузки 5й страницы в 1й кадр
Также вводится бит модификации (dirty). Он устанавливается, если в страницу была осуществлена запись.
в результате возможны следующие 4 ситуации.
| Обр. | Модиф. |
|---|---|
| 0 | 0 |
| 0 | 1 |
| 1 | 0 |
| 1 | 1 |
Лучше вытеснять немодифицированную страницу, т.к. её точная копия находится на диске.
рабочее множество
Для каждого процесса в каждый момент времени существует набор страниц которые он должен держать в памяти – рабочее множество. Если этот набор не будет загружен возникнет трешинг страниц (постоянная загрузка и выгрузка страниц).
Трешинг - процесс не может загрузить в память все рабочее множество и все время подгружаются одни и те же страницы.
Из тетради: Деннинг предложил взять число страниц к котором обращается процесс за интервал времени delta t и предложил назвать как work set (рабочее множество). Т.е. рабочее множество - это число страниц к котором обращается процесс за интервал времени delta t.
При увеличении delta t число страниц, к которым обращается процесс будет стремится к некоторому пределу. Другими словами: процесс будет выполняться без страничных преобразований, если ему удастся загрузить в память все нужные страницы (это и есть раб. мн-во). Если процессу не удается загрузить в память все, что ему нужно, то возникает thrashing (подкачка одних и тех же страниц). За свое время жизни процесс меняет рабочее множество.
Глобальное замещение - может быть вытеснена любая страница любого процесса. Локальное замещение - вытесняются страницы только данного процесса.
Если у какого-то процесса слишком много страничных преобразований, то ему выделяется дополнительное количество страниц (квота). Позже можно снизить число страниц. Т.е. можно регистрировать число выделяемых страниц.
P [Present] - Он установлен, если страница находится в памяти.
A [Accessed] - показывает, было ли произведено обращение к странице с момента загрузки ее в память.
D [Dirty] - показывает была ли произведена запись в страницу.
Синхронизация и взаимоисключение параллельных процессов в распределенных системах: централизованный и распределенный алгоритмы, алгоритмы Token-ring; сравнение алгоритмов.
Алгоритмы взаимоисключения в распределенных системах:
- централизованные;
- распределенные;
- token-ring.
Сводит решение, подобное решению на одной машине. Существует процесс-координатор, например, на машине с наибольшем значением сетевого адреса. Когда какой-то процесс хочет войти, он посылает запрос с именем участка, в который хочет зайти и ждет координатора. Координатор смотрит, не находится ли кто-то уже там или кто-то на очереди. Если да, то координатор ставит полученный запрос в очередь, иначе посылает разрешение и помечает область занятой. Необходимо иметь алгоритм выхода из ситуации отказа координатора.
Рассмотрим ситуацию, когда каждый процесс может выполнить роль координатора. В этом случае, если какой-то процесс обнаружил, что координатор отсутствует (если прошел timeout, то он может считать, что координатор отсутствует (здесь может использоваться специальный протокол)). Тогда такой процесс может инициализировать процесс выбора нового координатора. Посылается специальный запрос, в котором процесс указывает свой номер всем процессам. Если у принимающего процесса больший номер, то он инициирует такой запрос сам. В результате останется один процесс с наибольшим номером. Он становится координатором.
Второй тип алгоритма это распределенный алгоритм.
Алгоритм формулируется следующим образом:
- Когда процесс хочет войти в критическую секцию, он формирует сообщение.
- В этом сообщении он указывает:
- идентификатор нужной ему критической секции;
- свой номер (идентификатор);
- время формирования сообщения по своим локальным часам.
- Предполагается, что передача сообщения надёжна: получение каждого сообщения сопровождает подтверждение.
- Протокол - соглашение о том, какие действия выполняют процессы при передаче и получении сообщения. Надёжный протокол всегда предполагает подтверждение получения сообщения.
- В этом сообщении он указывает:
- Это сообщение, сформированное процессом, процесс рассылает всем взаимодействующим процессам (то есть n - 1 сообщение)
- Получив такое сообщение, процесс проверяет, в какой ситуации он сам находится по отношению к критической секции.
- Возможны 3 ситуации:
- получивший сообщение процесс не собирается входить в данную критическую секцию (и не находится в ней). В этом случае процесс посылает сообщение-ответ с разрешением войти в критический участок;
- процесс, получивший сообщение, находится в данной критической секции. В этом случае никакое сообщение не посылается;
- Процесс, получивший сообщение, сам формировал сообщение запрос на вход в данную критическую секцию, но еще не успел это сделать.
- (на доске: хочет войти в ту же критическую секцию). Тогда процесс проверяет временную метку создания своего сообщения, сравнивает ее с временной меткой полученного сообщения. Если его сообщение было сформировано раньше, то никакого сообщения-ответа процесс не посылает. Если в результате таких рассылок процесс получает n - 1 сообщение подтверждения входа в критический участок, то процесс может войти в критический участок. Если он не получает хотя бы одно сообщение, то в критический участок процесс войти не может.
- Возможны 3 ситуации:
В этом случае процесс должен послать n - 1 сообщение-запрос и в ответ получить n - 1 сообщение-разрешение на вход, иначе войти не может.
(еще один распределенный алгоритм)
Смысл заключается в том, что процессы создают логическое кольцо - замкнутую цепочку.
Каждый процесс в логическом кольце знает идентификатор следующего процесса в этом логическом кольце. По данному логическому кольцу передается так называемый токен. Это специальное сообщение, которое содержит идентификатор конкретной критической секции. Этот токен переходит от n-ого процесса к n + 1-ому процессу, циркулирует по логическому кольцу. Когда процесс получает токен, он анализирует, нужно ли ему войти в данную критическую секцию. Если нужно, получив токен, он входит в критическую секцию и токен удерживает. Выйдя из критической секции, процесс отправляет токен следующему в цепи процессу. Пока процесс находится в критической секции он удерживает токен. Если ни один процесс не заинтересован во вхождении в критическую секцию токена, такой токен быстро циркулирует по цепочке.
Самый надежный алгоритм: централизованный алгоритм. За счет возможности выбора нового координатора.
В случае распределенного алгоритма: Если какой-то из процессов перестал существовать, то процесс, разославший n - 1 сообщение-запрос, не сможет получить n - 1 сообщение-ответ: потеря работоспособности по конкретной критической секции.
В случае Токен Ринг: если какой-то процесс перестает существовать, то цепь разрывается. Чтобы ее восстановить, надо предпринять соответствующие действия. Если циркулирование токена по каким-то причинам прервано, то есть только одно средство определения: таймаут.
Транзакция - само по себе неделимое действие. Транзакция - высокоуровневое средство взаимодействия процессов.
Любая транзакция должна быть неделимой, это свойство транзакции.
Транзакцией называется последовательность операций над одним или несколькими объектами базы данных, такими как файлы, записи и тому подобное, которая переводит систему из одного целостного состояния в другое целостное состояние.
Один процесс объявляет, что хочет начать транзакцию с одним или более объектами. Происходит изменение объектов какое-то время. Инициатор транзакции объявляет, что он хочет завершить транзакцию. Если все процессы с ним соглашаются, то результат фиксируется. Если один/более процессов отказываются/потерпели крах, тогда все изменения возвращаются к исходному состоянию(откат).
Для того, чтобы транзакция могла выполняться, система (или ПО) должна предоставлять необходимый набор примитивов - команд управления транзакцией:
begin_transactionend_transaction-
abort_transaction(прерывание означает необходимость восстановления исходных значений) -
read_transaction,write transaction(позволяют читать или писать данные)
Примечание: begin и end определяют границы транзакции.
Свойства транзакций:
- упорядоченность: гарантирует, что если две или более транзакции выполняются в одно и то же время, то конечный результат выглядит так, как если бы транзакции выполнялись в определенном порядке.
- неделимость: если транзакция находится в процессе выполнения, то промежуточные результаты выполнения транзакции не видны никакому другому процессу.
- постоянство: означает, что после фиксации транзакции никакой сбой не может отменить результатов ее выполнения.
Существует два основных подхода к реализации механизма транзакций:
-
Для каждого процесса, участвующего в транзакции, создается индивидуальное рабочее пространство. В этом пространстве находятся копии всех файлов (объектов), которые нужны процессу для выполняния транзакции. Пока транзакция не будет зафиксирована или не прервется, все изменения выполняются только над объектами в этом индивидуальном рабочем пространстве. Если транзакция успешно завершается, то все изменения копируются в исходные объекты. Если транзакция прерывается, то копии просто удаляются (исходные файлы не были изменены). Очевидный недостаток: большие накладные расходы, так как создаются дополнительные копии файлов (объектов) в системе.
-
Список намерений. В данном подходе модифицируются сами файлы/записи/объекты, но перед любым изменением выполняется запись в специальный файл, который называется журнал регистрации. В этом журнале отмечается, какая транзакция делает изменения, какой файл/запись изменяется и в этот журнал записывается старое и новое значения изменяемого файла записи. Только после того, как транзакция успешно выполнена, указаные изменения сохраняются в исходном файле. Если транзакция фиксируется (выполняется успешно), то об этом делается запись в журнале регистрации, но записи не удаляются. Если транзакция прерывается, то журнал регистрации используется для приведения файлов (записей) в исходное состояние - такое действие называется откатом.
В распределённых системах фиксация транзакции может потребовать взаимодействия нескольких процессов, которые выполняются на разных машинах. В этом случае каждая такая отдельная машина хранит какие-то переменные/файлы базы данных. Для достижения неделимости транзакции в распределенных системах, используется специальный протокол - протокол двухфазной фиксации транзакций.
Это не единственный протокол для фиксации транзакции, но он считается наиболее надежным.
Суть протокола: для обеспечения выполнения транзакции в распределенной системе один из взаимодействующих процессов выполняет функции координатора.
координатор подчиненный процесс
------------------------------------ --------------------
| Записать "приготивиться" | | |
| Послать сообщения "приготовиться" | -> | Записать "готов" | 1 фаза
| | <- | Послать "готов" |
| Собрать сообщения-ответы | | |
------------------------------------- --------------------
| Запись в журнале | | |
| Послать сообщение "завершить" | -> | | 2 фаза
| Собрать ответы | <- | Послать ответ |
------------------------------------- --------------------
-
Первая фаза (заключается в том, что координатор собирает сообщения от других процессов - ответы)
- координатор должен записать в журнал регистрации приглашение для других процессов участвующих в транзакции: например, "приготовиться".
- после того, как эта запись сделана в журнале регистрации, выполняется рассылка сообщений процессам, участвующим в транзакции.
- подчинённый процесс, получив сообщение "приготовится", в журнал регистрации выполняет запись о готовности завершить транзакцию, например, "готов".
- после успешной записи в журнал регистрации, подчинённый процесс может послать сообщение координатору.
-
Вторая фаза (возможна, только в том случае, если координатор получил сообщения от всех процессов о готовности завершить транзакцию)
- если действие завершается с некоторой ошибкой, то в этом случае никаких действий подчиненный процесс совершать не будет и никакого сообщения "готов" не пошлет.
- если координатор собирает сообщения от всех подчинённых процессов, то координатор переходит к фиксации (завершению) транзакции.
- координатор делает запись в журнале регистрации "завершить". Только после успешной записи в журнале регистрации, корординатор посылает сообщение "завершить" подчиненным процессам.
- получив сообщение "завершить", подчиненный процесс записывает в журнал "завершить" (фиксировать).
Только после этого, посылается ответное сообщение. Процесс координатор снова должен собрать эти сообщения-ответы. если он собрал сообщения от всех участников транзакции процессов, то результат транзакции фиксируется. Вторая фаза является фазой фиксации результатов транзакции.