Классические задачи синхронизации

6.1 Модели параллельных вычислений

Логический и физический параллелизм

· Различают следующие способы параллельного исполнения потоков:

– физический (каждый поток исполняется своим процессором)

– логический (один процессор переключается на исполнение разных потоков)

· Потоки, исполняемые одним процессором, называются одновременными или конкурирующими

Модели параллельных вычислений

дописать лекции у наташи

void philosopher (int i)

{

while(true)

{

think();

take_forks(i);

eat();

put_forks(i);

}

void take_forks (int i)

{

mutex.wait();

state[i] = HUNGRY;

test(i); //попробовать взять две вилки

mutex.signal();

s[i].wait(); //заблокироваться, если вилки недоступны

}

void put_forks (int i)

{

mutex.wait();

state[i] = THINKING;

test(LEFT); //разрешить есть соседу слева

test(RIGHT);

mutex.signal();

}

void test (int i) //номер философа

{

if (state[i] == HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING)

{

state[i] = EATING;

s[i].signal();

}

7. Тупики (deadlocks)

7.1 Определение тупиков

· Поток находится в тупике, если он ожидает событие, которое никогда не произойдет.

· Событие не может произойти никогда по следующим причинам:

– не существует потока, который оповещает о наступлении события;

– такой поток существует, но сам находится в тупике;

· Будем считать, что процесс находится в тупике, если находится в тупике хотя бы один поток этого процесса.

7.2 Классификация системных ресурсов

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

· Классификация ресурсов по доступу:

– совместно используемые ресурсы;

– монопольные ресурсы.

· Совместно используемый ресурс может одновременно использоваться несколькими потоками, например, файл.

· Монопольный ресурс может быть представлен потоку только в монопольное использование, например, принтер.

Классификация ресурсов по способу распределения

· Классификация ресурсов по способу распределения:

– перераспределяемые ресурсы;

– не перераспределяемые ресурсы.

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

· Не перераспределяемый ресурс не может быть отобран у потока, который владеет этим ресурсом, например, принтер.

Классификация ресурсов по времени существования

· Классификация ресурсов по времени существования:

– повторно используемые ресурсы;

– потребляемые ресурсы.

· Повторно используемый ресурс может использоваться потоками многократно, например, принтер.

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

7.3 граф распределения ресурсов

· Для обнаружения тупиков определим граф распределения ресурсов процесса.

– Граф ресурсов процесса – это ориентированный граф, вершины которого обозначают потоки, а дуги интерпретируются следующим образом:

– случай повторно используемых ресурсов: поток Т1 запрашивает ресурс Р, занятый потоком Т2;

– случай потребляемых ресурсов: поток Т1 запрашивает ресурс Р, который Т2;

7.4 Обнаружение тупиков в случае повторно используемых ресурсов

· Рассмотрим процесс, в котором потоки используют только повторно используемые ресурсы.

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

· Теорема 1 (Критерий тупика в случае повторно используемых ресурсов).

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

– Граф ресурсов, не содержащий цикла

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

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

«Граф ресурсов, содержащий цикл»

Пусть граф распределения ресурсов содержит цикл: Т1, Т2, …, Тк, Т1. Поток Т1 будет заблокирован до тех пор, пока ресурс, требуемый этим потоком, не будет освобожден потоком Т2. Повторяя эти рассуждения получим, что поток Т1 будет заблокирован до тех пор, пока поток Тк не освободит ресурс, требуемый Тк-1. Но этого не произойдет никогда, т.к. поток Тк ждет ресурс, захваченный самим потоком Т1. Значит, процесс находится в тупике.

7.5 Обнаружение тупиков в случае потребляемых ресурсов

· Рассмотрим процесс, в котором потоки используют только потребляемые ресурсы.

· Пусть G – граф распределения ресурсов такого процесса.

Определение узла

· Подграф H графа G называется узлом, если:

– через все вершины графа H проходит цикл;

– для каждой дуги, связывающей подграф G\ H с подграфом H, вершина из подграфа G\H является началом этой дуги, вершина из H – концом.

«Примеры»

· Теорема 2 (Критерий тупика в случае потребляемых ресурсов)

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

Доказательство аналогично теореме 1.

7.6 Восстановление после обнаружения тупика

Три подхода к восстановлению процесса

· После обнаружения тупика должно быть выполнено восстановление процесса, которое заключается в разблокировании потоков этого процесса.

· Существуют три подхода к восстановлению процесса:

– Перераспределение ресурсов(preemption).

– Прекращение работы заблокированных потоков(termination).

– Откат на контрольную точку(rollback).

Перераспределение ресурсов

· Этот подход к восстановлению процесса – самый лучший, но редко может быть осуществим на практике по причине невозможности перераспределения ресурсов.

Прекращение работы заблокированных потоков

· Этот подход к восстановлению процесса – самый плохой, так как нарушается целостность обрабатываемой информации.

· Однако, этот подход можно применять в случае, если потерянная информация не является существенной.

Откат на контрольную точку

· Этот подход к восстановлению процесса применяется наиболее часто. Но при реализации этого подхода должны быть решены две проблемы:

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

– восстановление информации на момент, предшествующий тупику.

Контрольные точки и транзакции

· Для реализации этого подхода в программе устанавливаются такие точки, в которых запоминается состояние контекста потока.

· Эти точки называются контрольными точками потока.

· Изменение контекста потока между двумя контрольными точками называется транзакцией.

Откат

· Транзакция может быть зафиксирована или отменена.

· Отмена транзакции называется откатом на контрольную точку.

· После отката потоки разблокируются.

· Если транзакция зафиксирована, то откат на контрольную точку невозможен.

Действия, выполняемые при откате

· При откате выполняются следующие действия:

– контекст потока восстанавливается в состояние, в котором он находился в контрольной точке.

– восстанавливаются данные на момент прохождения контрольной точки.

– освобождаются заблокированные ресурсы.

7.7 Предотвращение тупиков

Стратегии распределения ресурсов

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

– захват всех ресурсов.

– откат в случае отказа.

– упорядочивание запросов.

Захват всех ресурсов

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

· Недостатки подхода:

– неэффективное использование ресурсов компьютера, т.к. они блокируются для использования другими потоками.

Откат в случае отказа

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

· Недостаток подхода:

– затраты на откат потока.

Упорядочивание запросов

· Типы (классы) ресурсов линейно упорядочиваются (нумеруются)

· В процессе своей работы поток может захватить только те ресурсы, тип которых больше типа уже используемых им ресурсов.

· Недостаток подхода:

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

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

· Алгоритм банкира – позволяет избежать тупика.

· Этот алгоритм разработал Дейкстра (1965г)

· Моделью алгоритма является работа банкира по обеспечению клиентов кредитами.

Формулировка задачи

· Задача состоит в следующем:

– банкир имеет ограниченное количество денег для выдачи кредитов.

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

– кредит может выдаваться по частям.

– каждый кредит не превышает ресурсов банкира.

– сумма кредитов может превышать ресурсы банкира.

· Аналогии в программных системах:

– банкир – сервер

– клиент – клиент

– кредит – ресурс.

Состояние системы

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

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

– иначе состояние называется небезопасным.

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

Примеры состояний системы

· Банкир имеет 10 единиц ресурса для выдачи кредита.

клиенты	Выделено ресурсов. Свободно 10	Мах потребность
A
B
C
D

· безопасное состояние

клиенты	Выделено ресурсов. Свободно 2	Мах потребность
A
B
C
D

· небезопасное состояние

клиенты	Выделено ресурсов. Свободно 1	Мах потребность
A
B
C
D

Блок схема алгоритма банкира

«блок схема»

Задача №1

· Процесс включает пять потоков Т_к, к = 1, 5, которые используют девять повторно используемых ресурсов: Р_i, i = 1, 9

· Потоки процесса выполнили следующие запросы на распределение ресурсов:

	Т₁	Т₂	T₃	T₄	T₅
Захватил	Р₁	Р₂, Р₆	Р₃	Р₇, Р₈	Р₅, Р₉
Ждет	Р₇, Р₉	Р₈		Р₅	Р₆

· Требуется определить, находится ли система в тупике.

Решение

· Определяем потоки, которые находятся в состоянии ожидания: Т₁, Т₂, Т₄, Т₅.

· Строим граф распределения ресурсов для этих потоков.

P₆

P₅

P₈

P₉

P₇

T₁

T₃

T₄

T₅

T₂

· Так как граф распределения ресурсов содержит цикл (Т₂,Т₄) (Т₄, Т₅) (Т₅, Т₂), то процесс находится в тупике.

Задача №2

· В системе работают n процессов, которые используют m ресурсов типа R. Пусть каждому процессу выделено R_k ресурсов и для каждого процесса известно М_k – максимальное количество ресурсов, которые он может использовать, к = 1, n.

· Вопрос 1. Используя алгоритм банкира, требуется определить, сколько ресурсов дополнительно можно выделить процессу j, где n = 5, m = 20, j = 3, M_k = (5, 10, 5, 10, 3) R_k = (4, 7, 1, 5, 0).

Решение. Применяем алгоритм банкира

· Определяем количество распределения и свободных ресурсов. Распределено 17, Свободно 3.

· Строим вектор количества ресурсов, которые могут запросить процессы: (1, 3, 4, 5, 3)

· Для перехода системы в безопасное состояние, требуется, чтобы оставался 1 свободный ресурс R для процесса 1.

· Следовательно, процессу 3 можно дополнительно выделить 3 – 1 = 2 единицы ресурса R.

· Вопрос 2. Процесс 3 запросил у системы 3 единицы ресурса R. Удовлетворит ли система запрос?

· Решение. Так как система может выделить процессу 3 максимум 2 единицы ресурса, то процесс 3 получит отказ в выделении ресурсов.

8. Передача данных между процессами

8.1 Каналы передачи данных

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

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

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

Обмен данными между потоками одного процесса

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

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

· Если потоки выполняются в контекстах разных процессов, то потоки не могут обращаться к общим переменным.

· В этом случае для обмена данными между процессами создается канал передачи данных, который является объектом ядра ОС и представляет собой область памяти, разделяемую несколькими процессами и используемую ими для обмена данными.

Схема канала передачи данных

T₁	B₁	K₁	M	K₂	B₂	T₂
	канал передачи данных

· Т1, Т2 – потоки пользователя. В1, В2 – буферы ввода-вывода. К1, К2 – потоки ядра ОС. М – общая память.

Порядок работы канала передачи данных

· Пересылка данных из потока Т1 в поток Т2 происходит следующим образом:

– Пользовательский поток Т1 записывает данные в буфер В1, используя специальную функцию ядра ОС.

– Поток К1 ядра ОС читает данные из буфера В1 и записывает их в общую память М.

– Поток К2 ядра ОС читает данные из общей памяти М и записывает их в буфер В2.

– Пользовательский поток Т2 читает данные из буфера В2.

Реализация канала

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

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

Способы передачи данных по каналам

· Различают два способа передачи данных по каналам:

– потоком;

– сообщениями.

· Если данные передаются непрерывной последовательностью байтов, то такая пересылка данных называется передача данных потоком.

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

8.2 Связи между процессами

· Прежде чем пересылать данные между процессами, нужно установить между этими процессами связь.

· Связь между процессами устанавливается как на физическом (аппаратном), так и логическом (программном) уровнях.

Направления передачи данных

· С точки зрения направления передачи данных различают следующие виды связей:

– полудуплексная связь – данные по этой связи могут передаваться только в одном направлении;

– дуплексная связь – данные по этой связи могут передаваться в обоих направлениях.

Топологии связей

· Теперь предполагая, что рассматриваются только полудуплексные связи, определим возможные топологии связей.

· Под топологией связи будем понимать конфигурацию связей между процессами отправителями и получателями.

Виды связей

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

– 1 - > 1 между собой связаны только два процесса.

– 1 - > N один процесс связан с N процессами.

– N - > 1 каждый из N процессов связан с одним процессом

– N - > M каждый из N процессов связан с каждым из М процессов.

Обозначения

· ○ – процесс

· □ - канал

· → - связь

Топология связей между процессами

Порты и почтовые ящики

· Канал передачи данных, реализующий топологию N - > 1 обычно называется портом.

· Канал передачи данных, реализующий топологию N - > M называется почтовым ящиком.

Порядок разработки систем обмена данными

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

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

Функции для установки связей между процессами

· Для установки связей между процессами обычно используются функции типа:

– connect – установить связь.

– disconnect – разорвать связь.

· Эти функции, а также функции для обмена данными между процессами обеспечивает система передачи данных, которая обычно является частью ядра ОС.

8.3 Передача сообщений

· Обмен сообщениями между процессами выполняется при помощи двух функций:

– send – послать сообщение;

– receive – получить сообщение.

Структура сообщений

Заголовок сообщения	Тип сообщения
Идентификатор получателя
Идентификатор отправителя
Длина сообщения
Управляющая информация
Тело сообщения	Содержание сообщения

Типы адресации процессов

· При передаче сообщения может использоваться прямая или косвенная адресация процессов.

Прямая адресация процессов

· При прямой адресации процессов в функциях send и receive явно указываются процессы отправитель и получатель.

· В этом случае функции обмена данными имеют следующий вид:

– send(P, message) – послать сообщение процессу Р;

– receive(Q, message) – получить сообщение от процесса Q.

Косвенная адресация процессов

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

· В этом случае функции обмена данными имеют следующий вид:

– send(S, message) – послать сообщение по каналу связи S;

– receive(R, message) – получить сообщение по каналу связи R.

· В последнем случае сообщение могут получать все процессы, подключенные к каналу R.

Симметричная и асимметричная адресация

· Адресация процессов может быть симметричной и асимметричной.

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

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

Адресация в системах клиент-сервер

· Асимметричная адресация процессов используется в системах клиент-сервер.

· В этом случае клиенты знают адрес сервера и посылают ему сообщения, используя функцию send(Server, message).

· А сервер «слушает» канал связи и принимает сообщения от всех клиентов, используя функцию receive(Connection, message).

· Часто эта функция так и называется listen (слушать).

Протокол

· Набор правил, по которым устанавливаются связи и передаются данные между процессами, называется протоколом.

8.4 Синхронный и асинхронный обмен данными

· При передаче данных различают синхронный и асинхронный обмен данными.

Синхронное и асинхронное отправление сообщений

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

· В противном случае отправление сообщения называется асинхронным.

Синхронное и асинхронное получение сообщения

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

· В противном случае получение сообщения называется асинхронным.

Синхронный и асинхронный обмен сообщениями

· Обмен сообщениями называется синхронным, если поток отправитель синхронно передает сообщения, а поток адресат синхронно принимает эти сообщения.

· В противном случае обмен сообщениями называется асинхронным.

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

Рандеву

· Синхронный обмен данными в случае прямой адресации процессов называется рандеву (rendezvous – франц. «встреча»).

· Такой механизм обмена сообщениями используется в языке программирования Ада.

8.5 Буферизация

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

Типы буферизации

· Существенно различаются три типа буферизации:

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

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

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

8.6 Анонимные каналы в Windows

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

· Процесс, который создает анонимный канал, называется сервером анонимного канала.

· Процессы, которые связываются с анонимным каналом, называются клиентами анонимного канала.

Свойства анонимных каналов

· не имеют имени;

· полудуплексные;

· передача данных потоком;

· синхронный обмен данными;

· возможность моделирования любой топологии связей.

Порядок работы с анонимным каналом

· создание анонимного канала сервером;

· соединение клиентов с каналом;

· обмен данными по каналу;

· закрытие канала.

Соединение клиентов с анонимным каналом

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

· Чтобы процесс-клиент наследовал дескриптор анонимного канала, этот дескриптор должен быть наследуемым.

· Явная передача наследуемого дескриптора процессу-клиенту анонимного канала может выполняться одним из следующих способов:

– через командную строку;

– через поля hStdInput, hStdOutput и hStdError структуры STARTUPINFO;

– посредством сообщения WM_COPYDATA;

– через файл.

Функции для работы с анонимным каналом

· CreatePipe – создание анонимного канала;

· WriteFile – запись данных в анонимный канал;

· ReadFile – чтение данных из анонимного канала.

8.7 Именованные каналы в Windows

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

· Процесс, который создает именованный канал, называется сервером именованного канала.

· Процессы, которые связываются с именованным каналом, называются клиентами именованного канала.

Свойства именованных каналов

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

· могут быть как полудуплексные, так и дуплексные;

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

· обмен данными может быть как синхронным, так и асинхронным;

· возможность моделирования любой топологии связей.

Порядок работы с именованными каналами

· создание именованного канала сервером;

· соединение сервера с экземпляром именованного канала;

· соединение клиента с экземпляром именованного канала;

· обмен данными по именованному каналу;

· отсоединение сервера от экземпляра именованного канала;

· закрытие именованного канала клиентом и сервером.

Функции соединения с именованным каналом

· CreateNamedPipe – создание именованного канала;

· ConnectNamedPipe – соединение сервера с клиентом именованного канала;

· DisconnectNamedPipe – отсоединение сервера от именованного канала;

· WaitNamedPipe – ожидание клиентом свободного экземпляра именованного канала;

· CreateFile – соединение клиента с именованным каналом;

Функции для передачи данных по именованному каналу

· WriteFile – запись данных в именованный канал;

· ReadFile – чтение данных из именованного канала;

· PeekNamedPipe – копирование данных из именованного канала;

· TransactNamedPipe – обмен сообщениями по именованному каналу;

Функции для работы с состоянием и свойствами именованного канала

· GetNamedPipeHandleState – определение состояния именованного канала;

· SetNamedPipeHandleState – изменение состояния именованного канала;

· GetNamedPipeInfo – получить информацию об атрибутах именованного канала;

9. Управление устройствами компьютера

9.1 Логическая структура компьютера

ЦП

ОП

Системная шина

У₁

У₂

У_n

Обозначения

· ЦП – центральный процессор (CPU – central processing unit)

· ОП- оперативная память (RAM – random access memory)

· У₁, У₂, …, У_n – устройства

· Центральным процессором называется интегральная схема (ИС), которая выполняет две основные функции

– исполняет команды программы;

– управляет работой устройств компьютера.

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

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

· Системной шиной называется набор ИС и линий передачи сигналов, которые предназначены для обмена сигналами между ЦП, ОП и устройствами.

· Системная шина обеспечивает 3 вида обмена данными:

– ЦП = ОП

– ЦП = У

– ОП = У

· Системная шина состоит из трех шин:

– шины управления, по которой передаются управляющие сигналы;

– шины данных, по которой передаются данные;

– адресной шины, по которой передаются адреса.

9.2 Типы устройств

устройства
исполнительные	интерфейсные
контроллеры	сопроцессоры	последовательные	параллельные

Исполнительные устройства

· Исполнительные устройства – это ИС, которые функционально дополняют ЦП.

· Различают два типа исполнительных устройств: контроллеры и процессоры.

Контроллеры

· Контроллеры – это ИС, которые предназначены для управления другими устройствами, освобождая от этих функций ЦП.

· Пример 1. Контроллер прерываний управляет диспетчеризацией сигналов прерываний от устройств.

· Пример 2. Контроллер прямого доступа к памяти управляет прямым доступом устройств к ОП.

Сопроцессоры

· Сопроцессоры – это процессоры специального назначения.

· Пример. Процессор цифровой обработки сигналов (DSP – digital signal processor).

Интерфейсные устройства

· Интерфейсные устройства – это ИС, которые управляют обменом данными между компьютером и внешними устройствами ввода/вывода данных.

· Часто интерфейсные устройства называются интерфейсами или устройствами ввода/вывода.

Последовательные и параллельные интерфейсы

· Последовательные интерфейсы передают данные последовательно по битам. Например, интерфейс RS 232.

· Параллельные интерфейсы передают параллельно целое слово данных (8, 16, 32 или 64 бита)

Драйверы

· В ОС для доступа к устройствам используются специальные программы, которые называются драйверами устройств.

9.3 Логическая архитектура центрального процессора

УУ

АЛУ

Память (регистры)

инструкция

управл. сигнал

операнды

результат

центральный процессор

Обозначения

· УУ – устройство управления;

· Назначение УУ:

– исполняет инструкции перехода.

· АЛУ - арифметико-логическое устройство

· Назначение АЛУ:

– исполняет арифметические команды;

– исполняет логические команды.

· Память – регистры микропроцессора, в которых хранятся:

– данные;

– команды;

– состояние процессора.

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

– PC – счетчик команд (program counter)

– IR – регистр команд (instruction register)

· Через MemPtr обозначим массив байтов основной памяти.

Цикл работы процессора

while (true)

{

IR = MemPtr[PC];//извлекаем команду

++PC; //увеличиваем счетчик

if (InstructionCode(IR) == Jump)

PC = JumpAddress(IR);

else

Execute(IR); //вызов АЛУ

}

Архитектура фон Неймана

· Такая архитектура и принципы работы процессора называются архитектурой фон Неймана.

· Принципы архитектуры фон Неймана:

– данные и инструкции хранятся в основной памяти (программа хранится в основной памяти)

– для доступа к содержимому основной памяти используется адресация (данные и инструкции в основной памяти неразличимы)

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

9.4 Прерывания

Контекст процессора. Перестановка контекста процессора

· Состояние регистров процессора при исполнении программы называется контекстом процессора.

· Контекст процессора определен только в точках между выполнением двух последовательных команд.

· В этих точках можно изменить контекст процессора, т.е. запомнить текущий контекст процессора в памяти, а затем загрузить из памяти в процессор новый контекст.

· Такая операция называется перестановкой контекста процессора.

Точка прерывания. Прерывание программы.

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

· Сам процесс перестановки контекста процессора называется прерыванием программы.

Прерывание

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

· Процессор проверяет состояние этого флага после выполнения каждой команды.

· Сигнал, устанавливающий флаг прерывания, называется прерыванием.

Классификация прерываний по отношению к исполняемой программе

Прерывание
Внешние (асинхронные)	Внутренние
Аппаратные (асинхронные)	Программные (синхронные)
Ошибки в программе (исключения)	Захват ресурса

Внешние прерывания

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

Внутренние прерывания

· Внутренние прерывания инициализируются самой исполняемой программой:

– явно в случае программных прерываний;

– неявно в случае аппаратных прерываний;

Внутренние аппаратные прерывания

· Внутренние аппаратные прерывания являются асинхронными и могут происходить по следующим причинам:

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

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

Внутренние программные прерывания

· Внутренние программные прерывания являются синхронными и явно инициируются программой посредством исполнения команды (функции), которая обращается к ядру ОС.

NMI

9.5 Обработка прерываний

ЦП

КП

адресная шина

INTA

INTR

IR0

IR1

IR7

· Обозначения устройств

– ЦП – центральный процессор;

– КП – контроллер прерываний;

· Обозначения сигналов

– IR0, …, IR7 – сигналы прерывания от устройств

– INTR – сигнал запроса на прерывание от КП

– INTA – сигнал подтверждения прерывания от ЦП

– NMI – сигнал немаскируемого прерывания

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

· ЦП может блокировать обработку сигнала по линии INTR.

· КП может блокировать обработку сигнала по линиям IR0, …, IR7.

· В этом случае говорят, что соответствующие прерывания маскируются.

· Прерывания по линии NMI не маскируются. Эта линия служит для передачи сигнала прерывания в случае аварии оборудования, например, падение напряжения в сети.

Диспетчеризация прерываний

· КП выполняет диспетчеризацию сигналов прерывания от устройств, которые поступают на входы IR0, …, IR7.

· Для этого КП программируется таким образом, что каждому из входов IR0, …, IR7 ставится в соответствие свой приоритет.

· Если на входы КП поступает несколько сигналов прерывания, то обрабатывается сигнал с наибольшим приоритетом, а остальные маскируются.

Дисциплина обслуживания прерываний

· Такая дисциплина обслуживания прерываний называется одноуровневой с приоритетами.

· Контроллеры прерываний могут подключаться каскадом, т.е. INTR одного КП подключается к одному из входов IR0, …, IR7 другого КП.

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

Алгоритм обработки сигналов прерываний от устройств

· Сигналы прерывания поступают на входы IR0, …, IR7 контроллера прерываний.

· КП обрабатывает сигналы и выдает запрос ЦП на вход INTR.

· Если вход INTR не маскирован, то ЦП передает КП подтверждение о получении сигнала прерывания по линии INTA.

· По второму сигналу от ЦП по линии INTA контроллер прерываний устанавливает на адресную шину адрес программы обработки прерывания.

· ЦП передает управление программе обработки прерывания.

Передача управления программе обработки прерывания

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

· Если процессор сохраняет только свое текущее слово состояния (PSW – processor state word), то программа обработки прерывания должна иметь следующую структуру.

Структура программы обработки прерывания

вход: //сохранение PSW

сохранение содержимого регистров;

обработка прерывания;

восстановление содержимого регистров;

выход: //восстановление PSW

10. Виртуальная память

10.1 Концепция виртуальной памяти

· Интегральные схемы, предназначенные для хранения программ и данных, называются физической памятью.

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

· Каждый байт физической памяти имеет свой номер или индекс, который называется физическим адресом.

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

Логическая память процесса

· Под логической памятью процесса понимается массив байтов, к которым может обратиться процесс.

· Индекс каждого элемента этого массива называются логическим адресом.

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

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

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

· Обычно, прямое отображение невозможно, по той простой причине, что объем логической памяти процесса превышает объем физической памяти компьютера.

Виртуальная память

· Для решения этой задачи физическую память компьютера дополняют памятью на дисках.

· Полученную расширенную память называют виртуальной памятью, а адрес элемента этой памяти называется виртуальным адресом.

Схема преобразования адресов при работе процесса

Линейный адрес

↓

Виртуальный адрес

↓

Физическией адрес

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

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

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

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

10.2 Организация виртуальной памяти

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

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

– при обращении процесса по виртуальному адресу процессор проверяет, находится ли виртуальная страница с этим адресом в реальной памяти;

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

· Такая организация виртуальной памяти называется страничной.

· Файлы, в которых хранятся страницы виртуальной памяти, называются файлами страниц или файлами подкачки (swap files).

Отображение виртуальных страниц

x

x

x

x

x

Витруальная память Реальная память

Форматы адресов

а) формат реального адреса: r d

r – номер реальной страницы

d – смещение

б) формат виртуального адреса v d

v – номер виртуальной страницы

d – смещение

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

Преобразование виртуальных адресов в реальные адреса

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

Формат строки таблицы страниц процесса

f a r

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

a – адрес виртуальной страницы во внешней памяти.

r – адрес реальной страницы в физической памяти.

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

Алгоритм отображения виртуальной памяти в реальную память (выполняется аппаратно – микропроцессором)

· Найти в таблице страниц строку, соответствующую номеру виртуальной страницы. Индекс этой строки равен b + v.

· Если f = 1, то виртуальная страница находится в реальной памяти.

· Если f = 0, то виртуальная страница находится на диске. В этом случае выполнить следующие действия:

– загрузить виртуальную страницу в реальную память.

– установить в столбце r адрес виртуальной страницы в реальной памяти.

– установить в столбце f значение 1.

· Вычислить реальный адрес, который формируется из адреса реальной страницы, который задан значением r, и смещением в виртуальной странице, которое задано значением d.

10.3 Алгоритмы замещения страниц

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

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

Проблема замещения страницы виртуальной памяти

· В этом случае возникает следующая проблема: какую виртуальную страницу вытолкнуть из физической памяти на диск.

· Для определения такой страницы чаще всего используются следующие алгоритмы.

1. Алгоритм FIFO

· На диск выталкивается первая из загруженных в реальную память виртуальных страниц.

2. Алгоритм LRU (least recently used)

· На диск выталкивается виртуальная страница, которая дольше всего не использовалась.

3. Алгоритм NRU (not recently used)

· На диск выталкивается страница, которая не использовалась в заданный интервал времени.

· Если таких страниц несколько, выбирается случайная.

4. Алгоритм LFU (least frequently used)

· На диск выталкивается виртуальная страница, которая меньше всего использовалась

Пробуксовка страниц

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

· То есть при каждом новом обращении к памяти будет необходима подкачка новой виртуальной страницы в реальную память.

Проблема оптимизации замещения страниц

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

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

Затирание виртуальных страниц

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

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

10.4 Рабочее множество процесса

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

· Эмпирически было определено, что при работе многих программ наблюдается свойство локальности.

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

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

Рабочее множество страниц процесса

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

· Это множество виртуальных страниц называются рабочим множеством процесса.

· Естественно, что рабочее множество страниц процесса изменяется со временем, какие-то страницы начинают использоваться реже, а какие-то чаще.

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

10.5 Организация виртуальной памяти в Windows

· В ОС Windows используется страничная организация виртуальной памяти.

· При этом линейный адрес процесса совпадает с его виртуальным адресом, который имеет следующий формат:

Формат виртуального адреса в Windows

31 22 21 12 11 0

p v d

p – смещение в каталоге страниц

v – номер виртуальной страницы

d – смещение внутри страницы

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

большая диаграмма

Каталог таблиц страниц

· В Windows адрес таблицы страниц процесса хранится в специальной таблице, которая называется каталогом таблиц страниц.

· Каждая строка каталога таблиц страниц содержит адрес уникальной таблицы страниц.

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

· Поэтому каждый процесс использует единственную таблицу страниц.

· Отсюда следует, что адресные пространства разных процессов изолированы друг от друга.

Формат строки таблицы страниц

31 27 26 7 6 3 2 0

p a f s

s – состояние страницы

f – номер файла подкачки страницы

a – физический адрес страницы

p – атрибуты доступа к странице

Состояния виртуальной страницы

· Поле s описывает состояние виртуальной страницы, которое определяется комбинацией трех бит.

· Различные комбинации этих бит определяют следующие состояния виртуальной страницы:

– страницы нет в реальной памяти (invalid page)

– страница находится в реальной памяти (valid page)

– страница находится в реальной памяти и модифицирована (valid dirty page)

– страница загружается в реальную память (invalid page in transition)

– страница сохраняется на диск ((invalid dirty page in transition)

Файлы подкачки

· Поле f задает номер файла подкачки на диске.

· Учитывая длину этого поля, можно определить до 16 файлов подкачки виртуальных страниц.

Физический адрес страницы

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

· Учитывая длину этого поля, можно определить, что виртуальная память процесса может содержать 2²⁰ виртуальных страниц.

· Отсюда следует. что так как длина виртуальной страницы равна 4кб, то вся виртуальная память процесса составляет 2²⁰*4кб = 4Гб виртуальной памяти.

Атрибуты доступа к странице

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

– PAGE_NOACCESS – доступ к странице запрещен;

– PAGE_READONLY – доступно только чтение страницы;

– PAGE_READWRITE – доступны чтение и запись страницы.

10.6 Менеджер виртуальной памяти в Windows

· В Windows управлением виртуальной памяти занимается специальный процесс, который называется менеджером виртуальной памяти (Virtual Memory Manager – VMM)

· Менеджер виртуальной памяти поддерживает свое внутреннее описание состояния каждой страницы в реальной памяти.

Состояние страниц реальной памяти

· В соответствии с этим описанием каждая страница реальной памяти может находиться в одном из следующих состояний:

– страница в рабочем состоянии и используется процессом (valid);

– страница записывается на диск (modified);

– страница удаляется из рабочего множества страниц процесса (standby);

– страница освобождена процессом, но не заполнена нулями (free);

– страница заполнена нулями и может использоваться любым процессом (zeroed);

– страница в нерабочем состоянии (bad).

Управление рабочим множеством страниц процесса и алгоритм прокачки страниц

· Для каждого процесса операционная система Windows определяется рабочее множество страниц этого процесса.

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

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

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

·