Сетевые операционные системы

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

При вытесняющей мультизадачности каждый процесс получает фиксированный квант времени процессора. По истечении одного кванта ОС вновь получает управление, чтобы переключить другой процесс. Передача управления операционной системе происходит и при обращении активного процесса к ОС или при возникновении системного события, даже если квант времени процесса не закончился. (Примеры реализации вытесняющей многозадачности - Windows NT). В Windows 95 для 32-разрядных приложений и приложений MS-DOS реализована вытесняющая мультизадачность, для 16-разрядных приложений - кооперативная мультизадачность.

Системы с вытесняющей многозадачностью являются более надежными и стабильными, так как при невытесняющей многозадачности ошибка в одной прикладной программе может «подвесить» всю систему. Примером системы с невытесняющей многозадачностью является Windows 3.11.

17. Понятия процесса и потока. Состояние процессов. Управление процессами

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

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

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

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

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

Процесс в системах разделения времени может находится в одном из следующих состояний:

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

· Готовности к выполнению - пассивное состояние, ресурсы могут быть предоставлены, тогда процесс перейдет в состояние выполнения;

· Блокирования или ожидания - пассивное состояние. Процесс заблокирован по своим внутренним причинам (ожидает некоторого события, завершение ввода/вывода, получение сообщения от другого потока или освобождение ресурса).

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

Управление процессами включает в себя решение следующих задач:

· определение момента времени для смены выполняемого процесса;

· выбор процесса на выполнение из очереди готовых процессов;

· переключение контекстов "старого" и "нового" процессов.

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

Планирование:

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

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

2. У не вытесняющих более высокие требования к разработчикам приложений

· Вытесняющее - решение о переключении процессора с одного потока на другой принимает ОС.

1. Простота разработки приложений,

В большинстве современных ОС используется вытесняющее планирование.

18. Дескрипторы и контексты процессов

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

· Идентификатор процесса;

· Тип (или класс) процесса, который определяет для супервизора некоторые правила предоставления ресурсов;

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

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

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

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

· Место или адрес для организации обмена информацией с другими процессами;

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

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

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

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

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

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

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

· включить дескриптор нового процесса в очередь готовых процессов;

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

19. Проблемы синхронизации процессов. Способы синхронизации

Синхронизация процессов и потоков.

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

IPC (Inter Process Communication)

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

Необходимость синхронизации и гонки.

Рассмотрим пример:

2-а процесса борются за один ресурс.



Клиент N

Описание ситуации:

1. Поток А обновляет поле «Заказ» записи о клиенте N. Он выполняет шаг А1. шаг А2 изменяет значение поля «Заказ». Выполнение прерывается из-за завершения кванта.

2. Поток В выполняет операцию внесения данных об оплате клиентом N. Он успевает выполнить шаг В1 и В2 до своего прерывания.

3. Управление передается потоку А, выполняется шаг А3 и запись переносится в файл.

4. Когда управление передается потоку В, он выполняет шаг В3. Данные о «Заказе» потока А заменяются на устаревшие.

Может возникнуть и обратная ситуация, может быть потеряна информация поля «Оплата».

Ситуация, когда два или более процесса обрабатывают разделяемые данные и неконечный результат зависит от соотношения скоростей потоков, называется «Гонкой».

Критическая секция:

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

Чтобы исключить эффект «Гонок» по отношению к критическим данным, необходимо чтобы в каждый момент времени в критической секции, связанной с этими данными находился только 1 поток, это метод Взаимного Исключения.

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

Блокирующие переменные.

Глобальные переменные - это переменные, к которым все потоки имеют доступ.

Алгоритм использования блокирующих переменных:

Продолжить выполнение

Каждому набору критических данных ставится соответствующая двоичная переменная, которая =0 при нахождении в критической ситуации, и =1, если ресурс свободен.

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

Недостаток: неэффективность использования процессов времени в цикле проверки значения переменной. Для решения этой проблемы в ОС применяются специальные системные вызовы для работы с критическими секциями.

Семафоры.

Дийкстра (Dykstra) - это переменные, которые могут принимать целые неотрицательные значения. Для работы с семафорами используются 2 примитива, обозначаемые P и V. Сама переменная семафор - S.

С ней выполняются следующие действия:

1. V(S): S: =S+1

Единым неделимым действиям.

2. P(S): S: = S-1

Если это возможно. Если S: =0, то поток ждет пока это уменьшение станет возможным. Операция неделимая.

Пример:

Работа семафора на примере двух потоков при помощи буфера.

потоки-писатели потоки-читатели

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

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

Буфер состоит из буферов N.

Введем семафоры e и f.

e - свободные;

f - занятые.

В начальный момент времени e = N, f = 0: потоки-писатели выполняют операцию P(e).

Такая схема позволяет эффективно и с минимальными затратами решить сложную задачу.

В частном случае, если переменная S принимает значение 0 и 1: S = {0,1}, то семафор вырождается в блокирующую переменную (двоичный семафор).

20. Тупики, способы борьбы с ними

При реализации синхронизации доступа процессов к ресурсам может возникнуть проблема тупика. Тупиком называется ситуация, когда 2 процесса нуждаются в 2 ресурсах одновременно, при этом 1 процесс захватывает 1 ресурс, а 2 процесс захватывает 2 ресурс и ни один не может продолжать исполнение. Процессы ждут друг друга неопределённо долгое время. Такая ситуация также носит названия “клинч” (clinch), взаимная блокировка, дедлок (deadlocks).

Проблема тупиков включает в себя следующие задачи:

· предотвращение тупиков,

· распознавание тупиков,

· восстановление системы после тупиков.

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

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

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

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

21. Управление процессами и потоками в многозадачных ОС

Алгоритм планирования, основанный на квантовании.

Квантование - каждому потоку поочередно для выполнения предоставляется ограниченно непрерывный период процессорного времени, который называется квантом. Смена активного потока происходит, если:

1. поток завершился;

2. произошла ошибка;

3. состояние ожидания;

4. исчерпан квант времени, отведенный данному потоку.

Размер кванта времени принимается небольшим (десятки миллисекунд). Чем больше квант, тем выше вероятность завершения потока в результате первого же цикла. Квант может быть фиксированным, либо изменяться различными способами.

1) Если величина каждого последующего кванта уменьшается до некоторого заданного минимума. В этом случае преимущество получают короткие задачи, а длительные вычисления будут проводиться в фоновом режиме.

2) Каждый следующий квант больше предыдущего. Снижаются накладные расходы на переключения задач, выгодно в случае нескольких потоков, выполняемых длительное время.

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



Алгоритм планирования, основанный на приоритетах.

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

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

Особенности приоритетов в WinNT.



1) По прошествию времени приоритеты потоков могут выходить за пределы диапазона. Если поток не полностью использовал свой квант, приоритет повышается, иначе - понижается.

2) Дифференцированное изменение приоритетов. Потоки, ожидающие ввода с клавиатуры, имеют более быстро возрастающий приоритет. Например, дисковые операции менее быстрые.

2 способа приоритетного планирования:

1. с относительными приоритетами;

2. с абсолютными приоритетами;

Общее между ними - на выполнение из очереди выбирается поток с наивысшим приоритетом.

Отличие - в моменте выбора смены потока.

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

“+” - минимизируется время переключения процесса.

“-” - процесс может занять процессор на долгое время.

В основном, применяется в системах пакетной обработки.

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

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

Современные ОС основываются на смешанном алгоритме планирования с использованием квантования и приоритетов.

Мультипрограммирование на основе прерываний

Назначение и типы прерываний

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

Прерывание процедура

Виды прерываний:

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

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

3) Программные не является «истинными», возникает при выполнении специальной команды процессора, имитирующей прерывание INT.

Прерывание характеризуется приоритетами (степень важности).

Механизм прерываний:

Необходима аппаратная и программная поддержка.

Существует 2 способа выполнения прерываний шины:

1) Векторные (vectored);

2) Опрашиваемый (polled).

В обоих способах процессор получает информацию об уровне приоритета прерывания на шине подключения внешних устройств (PCI).

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

По номеру вызываются соответствующие обработчики.

Вектор бывает:

1) Фиксированным (не изменяемым);

2) Конфигурирующим (аппаратные конфигурации (джамперы, переключатели и т.д.));

3) Программируемыми.

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

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

Подтверждается следующими шинами: ISA, EISA, MCA, PCI.

Платформа Intel реализует смешанный механизм прерывания: до процессора обработка идет по механизму опрашивания прерываний, внутри процессора векторный.

Механизм прерываний реализует приоритезацию и маскирования прерываний. Приоритеты могут обслуживаться как Относительные и Абсолютные.

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

Абсолютные - при поступлении прерываний с более высоким приоритетом, процессор переходит к его обработке.

Маскирование - это сокрытие прерывания более низкого уровня по с равнению с обрабатываемым.

Последовательность действий аппаратных и программных средств по обработке прерываний:

0) Сигнал прерывании;

1) Аппаратное распознавание типа прерывания. Если прерывание данного типа в текущий момент запрещены, то продолжается выполнении текущего потока. Иначе вызывается процедура обработки прерываний, адрес которой находится в специальной таблице Операционные Системы;

2) Автоматическое сохранение некоторой части контекста прерванного потока;

3) Загрузка адреса процедур обработки прерываний в счетчик команд + автоматическая загрузка нового значения слова о состоянии машины (для привилегированного режима);

4) Временный запрет прерывания данного типа, чтобы не организовывать вложенный цикл прерываний;

5) После обработки восстановления прерываний, контекст и работа потока возобновляется (при этом частично контекст восстанавливается аппаратно по команде возврата из прерываний, а часть программы извлечением данных из стека).

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

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

Две задачи:

· определение момента времени смены текущего потока.

· выбор для выполнения из очереди готовых потоков.

Примеры реализации планирования:

· ни один поток не занимает процессор больше определенного времени

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

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

Планирование может осуществляться:

· статически

· динамически

Динамическое планирование - решение принимается во время работы системы на основе анализа текущей ситуации.

Статическое планирование выполняется когда набор всех выполняемых задач известен заранее. (системы реального времени). Планировщик принимает решение не во время работы системы, а заранее.

Диспетчеризация - это реализация найденного в результате планирования решения, то есть непосредственное переключение процессора с одного потока на другой.

Состоит из 3 этапов:

· сохранение контекста текущего потока.

· загрузка контекста нового потока в результате планирования

· запуск потока на выполнение

Выполняется диспетчеризация аппаратно-программным способом.

23. Управление памятью и виртуализация адресного пространства в многозадачных ОС

Функции ОС по управлению памятью:

· отслеживание свободной, занятой памяти.

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

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

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

Дополнительные фунуции:

· дефрагментация памяти

· обслуживание запросов ядра и служб ОС

· защита памяти.

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

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

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

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

Виртуальное адресное пространство

Совокупность виртуальных адресов (ВА) процесса называется виртуальным адресным пространством (ВАП).

Способы организации ВАП:

· плоское (линейная последовательность адресов). Адрес = смещение от начала.

· деление на части (сегменты, страницы). Адрес = n+m, где n - номер сегмента, m - смещение в сегменте. (n, l, m - сегмент, страница, смещение).

Способы преобразования ВА в физические:

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

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

Второй способ более гибкий, позволяет перемещать программу в памяти.

Современные вычислительные системы обладают особенностью: максимальный размер виртуального адресного пространства часто больше физической памяти, установленной в системе. Для решения такой проблемы применяется механизм виртуальной памяти, то есть использование более медленных ЗУ большего объема (жесткий диск) для временного хранения данных из оперативной памяти.

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

24. Память и отображения, виртуальное адресное пространство

Способы отображения основной памяти на кэш

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

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

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

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

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

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

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

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

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

Виртуальное адресное пространство

Совокупность виртуальных адресов (ВА) процесса называется виртуальным адресным пространством (ВАП).

Способы организации ВАП:

· плоское (линейная последовательность адресов). Адрес = смещение от начала.

· деление на части (сегменты, страницы). Адрес = n+m, где n - номер сегмента, m - смещение в сегменте. (n, l, m - сегмент, страница, смещение).

Способы преобразования ВА в физические:

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

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

Второй способ более гибкий, позволяет перемещать программу в памяти.

Современные вычислительные системы обладают особенностью: максимальный размер виртуального адресного пространства часто больше физической памяти, установленной в системе. Для решения такой проблемы применяется механизм виртуальной памяти, то есть использование более медленных ЗУ большего объема (жесткий диск) для временного хранения данных из оперативной памяти.

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

25. Распределение статическими и динамическими разделами

Распределение статическими, динамическими и перемещаемыми разделами - это распределение без использования внешней памяти.

Фиксированный раздел.

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

Задачи управления памятью:

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

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

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

· простота реализации

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

Недостатки:

· жесткость.

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

Динамический раздел.

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

Задачи ОС по управлению памятью:

· ведение таблиц свободных и занятых областей (начальный адрес и размер).

· при создании нового процесса анализ требований, сравнение с таблицей и выбор раздела.

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

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

Преимущества:

· гибкость.

Недостатки:

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

· сложность.

Перемещаемый раздел.

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

Преимущество:

· нет фрагментации

· гибкость.

Недостаток:

· приходиться применять динамическое преобразование адресов

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

26. Сегментная, страничная и сегментно-страничная организация памяти

Сегментное, страничное и сегментно-страничное распределение - это распределение с использованием внешней памяти.

Страничное распределение

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

Вся оперативная память машины также делится на части такого же размера, называемые физическими страницами (или блоками).

Размер страницы обычно выбирается равным степени двойки: 512, 1024 и т.д., это позволяет упростить механизм преобразования адресов.

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

Рис. Страничное распределение памяти

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

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

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

- дольше всего не использовавшаяся страница,

- первая попавшаяся страница,

- страница, к которой в последнее время было меньше всего обращений.

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

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

Рассмотрим механизм преобразования виртуального адреса в физический при страничной организации памяти (рисунок 2.13).

Виртуальный адрес при страничном распределении записывается в виде пары чисел (P, Sv) (P - порядковый номер виртуальной страницы, начиная с 0, Sv - смещение в пределах виртуальной страницы).

Физический адрес записывается в виде пары чисел (n, Sf) (n - порядковый номер физической страницы, начиная с 0, Sv - смещение в пределах физической страницы).

Для преобразования адресов исполбзуются особые свойства стпаничной организации:

1) Размер страницы равен 2k, а значит смещение S можно получить простым отделением разрядов в двоичной записе, а оставшиеся старшие разряды - это двоичная запись номаре страницы.

10 0110011001 210-размер страницы

P Sv

2) В пределах страницы последовательность виртуальный адресов однозначно отображается с последовательностью физических адресов

Sv=Sf

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

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

1) Из специального регистра процессора извлекается адрес AT - таблицы страниц процессов. На основании начального адреса таблицы страниц, номера виртуальной страницы P (старшие разряды) и длины одной записи в таблице страниц (l) определяется адрес нужного дескриптора в таблице

a=AT+P*l

2) Из дескриптора извлекается номер соответствующей физической страницы n.

3) К номеру физической страницы при соединяется смещение S (младшие разряды).

Преимущества:

1) Простота пересчета адресов

2) Небольшой объем страниц

3) Относительная простота метода

Недостатки:

1) Не учет содержимого разбиваемых данных

Сегментное распределение

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

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

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



Рис. Распределение памяти сегментами

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

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

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

Странично-сегментное распределение

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

Рис. Схема преобразования виртуального адреса в физический для сегментно-страничной организации памяти

27. Свопинг, виртуальная память

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

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

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

Таким образом, виртуальная память - это совокупность программно-аппаратных средств, позволяющих пользователям писать программы, размер которых превосходит имеющуюся оперативную память; для этого виртуальная память решает следующие задачи:

1) Размещение данных в ЗУ разного типа

2) Выбор образов процессов или их частей для перемещения из памяти на диск и обратно

3) Перемещение, при необходимости, данных между памятью и диском

4) Преобразование виртуальных адресов в физические

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

Виртуальная память выполняется на основе 2 подходов:

1) Свопинг - образы процессов выгружаются на диск и загружаются в память целиком.

Недостатки:

a. Неэффективность

b. Если адресное пространство больше свободной памяти, то свопинг не работает

2) Виртуальная память - между памятью и диском перемещаются какие-то части образов процессов.

ВП реализуется 3 способами:

1) Страничная ВП - данные между диском и памятью перемещаются страницами - частями фиксированного размера.

2) Сегментная ВП - перемещение данных осуществляется сегментами т.е. частями произвольного размера с учетом смыслового значения данных

3) Сегментно-страничная ВП - комбинированный двухуровневый способ: виртуальное адресное пространство делится на сегменты, а сегменты на страницы, единица перемещения страница.

Для хранения сегментов и страниц на диске используется специальный файл - файл подкачки, swap, страничный файл (paging file).

28. Кэш-память

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

Неотъемлемым свойством кэш-памяти является ее прозрачность для программ и пользователей. Система не требует никакой внешней информации об интенсивности использования данных; ни пользователи, ни программы не принимают никакого участия в перемещении данных из ЗУ одного типа в ЗУ другого типа, все это делается автоматически системными средствами.

Кэш-памятью, или кэшем, часто называют не только способ организации работы двух типов запоминающих устройств, но и одно из устройств -- «быстрое» ЗУ.

Оно стоит дороже и, как правило, имеет сравнительно небольшой объем. «Медленное» ЗУ далее будем называть основной памятью, противопоставляя ее вспомогательной кэш-памяти.

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

Принцип действия кэш-памяти

Рассмотрим одну из возможных схем кэширования (рис. 5.25). Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных из основной памяти. Каждая запись об элементе данных включает в себя:

· значение элемента данных;

· адрес, который этот элемент данных имеет в основной памяти;

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

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

· если данные обнаруживаются в кэш-памяти, то есть произошло кэш-попадание (cache-hit), они считываются из нее и результат передается источнику запроса;

· если нужные данные отсутствуют в кэш-памяти, то есть произошел кэш-промах (cache-miss), они считываются из основной памяти, передаются источнику запроса и одновременно с этим копируются в кэш-память.

Интуитивно понятно, что эффективность кэширования зависит от вероятности попадания в кэш. Использование кэш-памяти имеет смысл только при высокой вероятности кэш-попадания.

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

· Временная локальность. Если произошло обращение по некоторому адресу, то следующее обращение по тому же адресу с большой вероятностью произойдет в ближайшее время.

...