Способность операционной системы поддерживать в рамках одного процесса выполнение нескольких потоков.
n MS-DOS – один процесс с одним потоком
n UNIX – много процессов с одним потоком в каждом процессе
n Windows, Solaris, Linux, Mach, OS/2 – множество процессов со множеством потоков в каждом процессе.
Характеристики процесса
n Виртуальное адресное пространство, в котором содержится образ процесса
n Защищённый доступ к процессорам, другим процессам для обмена информацией, файлам и ресурсам ввода-вывода.
Характеристики потока
n Состояние выполнения потока
n Контекст потока
n Стек выполнения:
q Стек пользовательского режима
q Стек режима ядра
n Статическая память для локальных переменных (TLS в семействе Win32)
n Доступ к памяти и ресурсам процесса, которому он принадлежит. Ресурсы процесса разделяются между всеми его потоками.
Преимущества использования потоков
n Создание потока занимает меньше времени, чем создание процесса.
n Поток можно завершить быстрее, чем процесс.
n Переключение между потоками процесса происходит намного быстрее.
n Потоки одного процесса разделяют его ресурсы, что позволяет потокам взаимодействовать без привлечения ядра ОС.
Потоки на однопроцессорной системе
n Работа в приоритетном (foreground) и фоновых режимах (background).
q Электронные таблицы
n Асинхронная обработка
q Работа с низкопроизводительными устройствами
n Повышение скорости выполнения
q Одновременные операции по загрузке и обработке данных
n Модульная структура программы
q Осуществление разнообразных действий и/или выполняющие множество операций ввода-вывода из и на различные источники.
Потоки
n Приостановка (Suspending) процесса приводит к простановке всех его потоков
n Завершение процесса приводит к завершению всех его потоков.
Состояния потока
n События, изменяющие состояние потока
q Порождение (Spawn)
n Первичный поток процесса порождается ОС. Другие потоки процесса порождаются потоками (начиная с первичного).
n Новый поток создаётся со своим контекстом и стеками и помещается в очередь готовых к выполнению.
q Блокирование
n Ожидание некоторого события с сохранением контекста
n Процессор переходит к выполнению другого потока.
q Разблокирование
n Наступление события и перевод потока в готовое состояние
q Завершение
n Разрушение контекста и стеков потока.
Состояние потока в Windows NT/2000/XP
Структура потоков в Windows NT
Удалённый вызов процедур с использованием потоков. Однопоточный клиент.
Удалённый вызов процедур с использованием потоков. Многопоточный клиент.
Однопоточный сервер
Многопоточный сервер с одним процессором
Поток сервера принимает запросы пользователей и порождает дочерние потоки для их обслуживания. Завершив обработку запроса серверные потоки передают результаты пользователю.
Недостатки многопоточного сервера
n Тратится время на создание нового потока и его последующее завершение.
n Потоки потребляют ресурсы системы
q Бесконтрольное порождение потоков может привести к исчерпанию ресурсов системы и è уязвимость к DoS атакам.
q Тратится время на переключение контекста между потоками.
q В системе может существовать много «лишних» потоков, находящихся в состоянии ожидания.
Многопоточный сервер на базе пула потоков.
n Идея
q Число одновременно работающих потоков надо ограничивать è на одном процессоре эффективно выполняется только один поток.
q Существует ограниченный пул потоков готовых к обслуживанию заявок. (Pool – набор однотипных объектов).
q Система контролирует число активных потоков.
q Система отслеживает изменение состояния потоков
n Активен à Блокирован. Активизирует поток из пула, если число активных потоков меньше порогового значения.
n Блокирован àГотов. Активизирует поток, если число активных потоков меньше порогового значения.
n Следствие
q Эффективная загрузка процессоров в системе è запросы успевают выполняться быстрее.
q Меньше вероятность успешных DoS атак.
Реализация потоков в ОС
n Потоки на уровне пользователя (User-level threads)
n Потоки на уровне ядра (Kernel-level threads)
Потоки на уровне пользователя
n Управление потоками выполняется на уровне приложения
n Ядро операционной системы не располагает информацией о существовании потоков.
Потоки на уровне пользователя
Потоки уровня ядра
n Ядро операционной системы владеет информацией о процессах и потоках
n Диспетчерезируемой единицей в системе является поток.
q Пример: OS/2, Windows
Комбинированный подход
n Потоки создаются на пользовательском уровне
n Диспетчеризация и синхронизация потоков выполняется на пользовательском уровне
n Потоки пользовательского режима проецируются на потоки уровня ядра.
q Пример: Solaris, Windows
Потоки в Windows API
#include <iostream>
#include <windows.h>
// Функция, исполняемая потоками.
// Выводит заданный параметром p символ
DWORD __stdcall CharsThread(LPVOID p)
{
// LPVOID p есть указатель на символ
TCHAR c = *(TCHAR*)(p);
// Бесконечно выводим на экран символ
while(1)
{
std::cout << c;
}
return 0;
}
int _tmain(int argc, _TCHAR* argv[]) {
// Описатели потоков
HANDLE hThreads[2];
TCHAR asterisk = '*';
TCHAR exclam = '!';
// Поток, печатающий '*'
hThreads[0] = CreateThread(NULL, 0, CharsThread, &asterisk, 0, NULL);
// Поток, печатающий '!'
hThreads[1] = CreateThread(NULL, 0, CharsThread, &exclam, 0, NULL);
// Время ожидания завершения потоков
#define TIMEOUT 2000
// Ждём завершения двух потоков TIMEOUT миллисекунд
WaitForMultipleObjects(2, hThreads, TRUE, TIMEOUT);
/* Закрываем описатели потоков. Сами потоки продолжают работать до
завершения процесса */
CloseHandle(hThreads[0]);
CloseHandle(hThreads[1]);
return 0;
}
Потоки в POSIX 1003.1
#include <pthread.h>
#include <stdio.h>
void *Thread(void *string)
{
int i;
for (i=0; i<10; i++)
printf("%s\n", (char *)string);
pthread_exit(NULL);
}
int main()
{
char *e_str = "Hello!";
char *f_str = "Bonjour !";
pthread_t e_th;
pthread_t f_th;
int rc;
rc = pthread_create(&e_th, NULL, Thread, (void *)e_str);
if(rc) exit(-1);
rc = pthread_create(&f_th, NULL, Thread, (void *)f_str);
if(rc) exit(-1);
pthread_exit(NULL);
}
Пулы потоков в Windows 2000
n Асинхронный вызов функций
q BOOL QueueUserWorkItem( PTHREAD_START_ROUTINE pfnCallback, PVOID pvContext, ULONG dwFlags);
n Очередь таймеров
q HANDLE CreateTimerQueue();
q BOOL CreateTimerQueueTimer( PHANDLE phNewTimer, HANDLE hTimerQueue, WAITORTIMERCALLBACK pfnCallback, PVOID pvContext, DWORD dwDueTime, DWORD dwPeriod, ULONG dwFlags);
q BOOL DeleteTimerQueueTimer( HANDLE hTimerQueue, HANDLE hTimer, HANDLE hCompletionEvent);
n Очередь ожидания на объектах ядра
q BOOL RegisterWaitForSingleObject( PHANDLE phNewWaitObject, HANDLE hObject, WAITORTIMERCALLBACK pfnCallback, PVOID pvContext, ULONG dwMilliseconds, ULONG dwFlags);
q BOOL UnregisterWaitEx( HANDLE hWaitHandle, HANDLE hCompletionEvent);
Волокна (Fibers) в Windows NT
Конвертирование потока в волокно
• PVOID ConvertThreadToFiber(PVOID pvParam);
Создание новго волокна в потоке
• PVOID CreateFiber( DWORD dwStackSize, PFIBER_START_ROUTINE pfnStartAddress, PVOID pvParam);
Переключение конткста на заданное волокно
• VOID SwitchToFiber(PVOID pvFiberExecutionContext);
Удаление волокна
• VOID DeleteFiber(PVOID pvFiberExecutionContext);
Классификация систем Флинна
n SISD
q Один процессор исполняет единственный поток команд; данные хранятся в единой области памяти.
n SIMD
q Каждая инструкция выполняется над различными наборами данных разных процессов (Векторные и матричные процессоры).
n MISD
q Единая последовательность данных передаётся различным процессорам для обработки
n MIMD
q Несколько процессоров одновременно выполняют команды над различными наборами данных.
Параллельные архитектуры
SMP и AMP (ASMP) системы
n SMP (Symmetric Multi Processing)
q Все процессоры в системе равноправны и потоки системы и пользователя могут быть запущены на любом из них.
q Как правило каждый процессор планирует свою работу, извлекая из очереди имеющийся процесс или поток.
n AMP (Asymmetric Multi Processing)
q Один процессор объявляется ведущим (master) на котором выполняются потоки ядра ОС.
q Ведущий процессор отвечает за диспетчеризацию
q Ведомые (slave) процессоры исполняют потоки пользователей.
SMP versus AMP. Масштабируемость.
Соглашения относительно многопроцессорных ОС
n Конкурирующие потоки или процессы.
q Реентерабельный код системы
n Диспетчеризация
q Планирование выполняется на любом из процессором.
n Синхронизация
q Обеспечить синхронизацию при доступе к разделяемым ресурсам.
n Управление памятью
q Обеспечить возможность разделения страниц памяти между несколькими процессорами
n Надёжность и отказоустойчивость
q Отказ одного из процессоров не должен остановить работу всей системы.
Диспетчеризация потоков на SMP
n Поток находится в состоянии «готов»:
q Подключать поток к любому простаивающему (Standby processor) процессору
q Подключать поток к любому из родственных процессоров (Affinity processor)
q Подключать поток к идеальному (Ideal processor ) процессору
q Подключать поток к последнему (Last processor ) процессору.
q Комбинированный подход (NT-системы)
Диспетчеризация потоков в многопроцессорной сиcтеме с Windows 2000
Архитектура операционных систем
n Монолитные системы
q Классические ядра UNIX, Linux
n Многоуровневые (слоёные) системы
q THE, MULTICS, Windows NT
n Виртуальные машины
q IBM VM/370, JVM
n Экзоядерные системы
q Исследования в MIT
n Микроядерные системы (модель клиент-сервер)
q QNX, MINIX
Монолитные системы
Многоуровневые (слоёные, Layered) системы
Свойства слоёв абстракции Г.Майерс
1. На каждом слое ничего не известно о свойствах (и даже существовании) более высоких слоёв
2. На каждом слое ничего не известно о строении других слоёв. Связь между слоями осуществляется только через жестко заданные интерфейсы.
3. Каждый слой представляет собой группу компонентов, некоторые из которых являются внутренними. Имена других компонентов известны на следующем, более высоком слое и представляют собой интерфейс с этим слоем.
4. Каждый слой располагает определёнными ресурсами и либо скрывает от других слоёв, либо представляет другим слоям некоторые их абстракции (виртуальные ресурсы
5. Каждый слой может обеспечивать некоторую абстракцию данных в системе.
6. Предположения, которые на каждом слое делаются относительно других слоёв должны быть минимальны.
7. Связь между слоями ограничена явными аргументами. Недопустимо совместное использование слоями глобальных данных.
8. Каждый слой должен иметь высокое зацепление и низкую связанность.
Виртуальные машины
n Виртуализация всех видов ресурсов вычислительной системы называется виртуальной машиной (Virtual Machine, VM)
Микроядра
(MINIX, QNX, Fluke, Paramecium, SPIN, Vino)
n Компактное ядро ОС – микроядро, наноядро.
n Ядро содержит только минимально необходимую функциональность.
n Многие сервисы ОС, традиционно включаемые в состав ядра, выполняются в защищённых подсистемах:
q Драйверы устройств
q Файловая система
q Менеджер виртуальной памяти
q Оконная подсистема
q Сервисы защиты.
Преимущества микроядерной архитектуры
n Единообразные интерфейсы
q Отсутствуют различия между службами ядра и службами режима пользователя.
q Доступ к службам осуществляется через механизм сообщений
n Расширяемость
q Лёгкость включения новых служб
n Гибкость
q Добавления новых свойств
q Исключение свойств из системы
n Переносимость
q Для переноса на другую платформу требуются изменения только в микроядре. Другие службы остаются неизменными.
n Надёжность
q Модульная архитектура
q Возможность тщательного тестирования маленького ядра.
n Поддержка распределённых систем
q Подсистемы посылают сообщения не зная какая именно машина в сети будет его обрабатывать
n Объектно-ориентированный подход
q Компоненты системы являются объектами со строго опредёлёнными интерфейсами.
Архитектура микроядра
Микроядро в распределённой системе
Архитектура микроядра
n Взаимодействие между процессами (IPC – Inter Process Communications)
n Управление вводом-выводом
n Управление прерываниями
Недостатки микроядерной архитектуры
Чистое микроядро непрактично с точки зрения производительности
Смешанные архитектуры
n Большинство современных коммерческих операционных систем нельзя отнести сугубо к монолитной либо микроядерной архитектуре:
q Достаточно большое ядро с загружаемыми драйверами устройств и некоторыми важными подсистемами, т.к.: менеджер памяти, файловая система и т.п.
q Ряд подсистем (серверы) функционируют в режиме пользователя и используют передачу сообщений через ядро для коммуникации с другими подсистемами.
Надёжность операционных систем
n Огромные размеры современных ОС
n Ядро Linux ~2 500 000 строк кода.
n Ядро Windows XP ~6 000 000 строк кода.
q Число ошибок составляет (по различным исследованиям) от 6 до 16 на 1000 строк кода
q ~70% кода ядра составляют драйверы устройств с ещё более низкой надёжностью.
q Разработчики не владеют полной информацией о системе
n Трудность изоляции ошибок в компонентах
Повышение надёжности ОС. Защита на базе языка.
n ОС Singularity (Microsoft Research)
q Sing#
n Безопасность типов
n Система передачи сообщений
n Сборка мусора
q Процессы могут разделять одно адресное пространство
n У каждого процесса свой домен (Domain)
q Микроядро
n Контроль доступа к аппаратуре
n Распределение памяти
n Синхронизация
n Передача сообщений
q Драйверы устройств
n Работа в отдельных процессах
Процессы и синхронизация
n Состояние
q Значение переменных программы в некоторый момент времени
n Действие
q Неделимое действие: изменяет состояние неделимым образом
n История
q Конкретное выполнение программы
Независимость параллельных процессов
n R = {r} – множество переменных, которые процесс читает
n W={w} – множество переменных, которые процесс пишет.
n Процессы независимы, если выполняется условие:
Разделяемый и критический ресурс
Разделяемый ресурс Критический ресурс
Синхронизация
n Цель синхронизации – предотвратить нежелательные истории.
q Взаимное исключение – объединение мелкомодульных неделимых операторов в крупномодульные
q Условная синхронизация – задержка выполнения процесса до достижения программой состояния, удовлетворяющего некоторому предикату.
Мелкомодульная неделимость
n Действие, реализуемое непосредственно аппаратным обеспечением.
n Характеристики машины
q Значения базовых типов хранятся в элементах памяти, которые считываются и записываются неделимыми действиями
q Значения обрабатываются так: их помещают в регистры, там применяют операции и затем записывают результаты в память
q Каждый процесс (поток) обладает своим контекстом (своим набором регистров)
q Любые промежуточные результаты вычислений сохраняются в памяти принадлежащей процессу (потоку), например, в стеке.
Условие «не больше одного»
Оператор присваивания x=e удовлетворяет условию «не больше одного», если либо выражение е содержит не больше одного критического ресурса, а переменная х не является разделяемой, либо выражение е не содержит критических переменных, а другие процессы могут считывать переменную х
Задача критической секции
n Взаимное исключение
q В любой момент только один процесс выполняет КС
n Отсутствие взаимной блокировки
q Если несколько процессов пытаются войти в КС, хотя бы один это осуществит
n Отсутствие излишних задержек
q Решение о вхождении в КС принимается за конечное время
n Возможность входа
q Процесс, который пытается войти в КС, когда-нибудь это сделает
Реализация взаимоисключения: аппаратная поддержка
n Отключение прерываний
q Легко реализовать
q Система теряет контроль над исполнением
q Не работает на многопроцессорных системах
n Повышение уровня IRQL
q Легко реализовать
q Важные прерывания маскируются
q Не работает на многопроцессорных системах
n Специальные инструкции микропроцессора
q Легко реализовать
q Применим в многопроцессорных системах
Спин-блокировки в Windows
Используются только в режиме ядра. Обеспечивают взаимное исключение на многопроцессорных системах.
n KeAcuireSpinLock(PKSPIN_LOCK pSpinLock, PKIRQL pOldIrql);
n KeReleaseSpinLock(PKSPIN_LOCK pSpinLock, PKIRQL pNewIrql);
Критические секции: решение со справедливой стратегией
n Алгоритм разрыва узла (Питерсона)
q Дополнительная переменная (last) с номером процесса, последнего запросившего вход в КС. Процесс входит в КС, если его номер не совпадает с last.
n Алгоритм билета
q При запросе входа в КС процесс получает свой номер, заведомо больший любого из ранее выданных другим процессам. Процессы обслуживаются в порядке увеличения номера.
n Алгоритм поликлиники
q Реализация алгоритма билета без использования специальных инструкций микропроцессора.
Семафоры
Дейкстра
n Семафор - вспомогательная критическая целочисленная переменная, для которой определены три операции:
1. Инициализация неотрицательным значением
2. Операция wait уменьшает значение семафора. Если значение становится отрицательным, процесс, выполняющий операцию wait блокируется
3. Операция signal увеличивает значение семафора. Если это значение положительно, то заблокированный операцией wait процесс деблокируется
Семафорные примитивы в Win32
n Критическая секция
q VOID InitializeCriticalSection(LPCRITICAL_SECTION lpcs)
q VOID EnterCriticalSection(LPCRITICAL_SECTION lpcs)
q VOID LeaveCriticalSection(LPCRITICAL_SECTION lpcs)
n Мьютекс
q HANDLE CreateMutex(LPSECURITY_ATTRIBUTE lpsa, BOOL bOwner, LPCTSTR szName)
q Wait-функции
q BOOL RelaseMutex(HANDLE hMutex)
n Семафор
q HANDLE CreateSemaphore (LPSECURITY_ATTRIBUTE lpsa, LONG cSemInitial, LONG cSemMax, LPSTR lpszSemName)
q Wait-функции
q BOOL ReleaseSemaphore(HANDLE hSem, LONG cRelease, LPLONG lpPrev);
n События
q HANDLE CreateEvent(LPSECURITY_ATTRIBUTE lpsa, BOOL fManual, BOOL fState, LPSTR szName)
q Wait-функции
q BOOL SetEvent(HANDLE hEvent)
q BOOL ResetEvent(HANDLE hEvent)
Задача производитель/потребитель
n Один или несколько процессов-производителей помещают данные в общий буфер.
n Процесс-потребитель извлекает данные из буфера
n Должна выполнятся задача критической секции при доступе к буферу со стороны производителей и потребителей
Задача «читатели/писатели»
n Несколько процессов могут одновременно читать данные из общей области памяти.
n Только один процесс в каждый момент времени может писать в общую область памяти.
n Процессы-читатели не могут читать данные, если происходит запись в общую область памяти.
Управление памятью
n Эффективное распределение памяти для размещения нескольких процессов
n Эффективное распределение памяти для обеспечения эффективного исполнения готовых процессов.
Требования к управлению памятью
n Перемещение
n Защита
n Совместное использование
n Логическая организация
n Физическая организация
Перемещение
n Программист не знает куда будет загружена программа при выполнении
n Во время выполнения программа может быть выгружена на диск и в дальнейшем загружена в память по другим адресам (перемещена)
n Ссылки на память должны быть переведены процессором и системой в реальные физические адреса.
Защита
n Процессы не должны без разрешения иметь возможности к обращениям к памяти других процессов
n Невозможно вычислить и проверить абсолютные адреса памяти при компиляции
n Защита памяти обеспечивается аппаратным обеспечением системы.
q Операционная система не в состоянии предвидеть все обращения к памяти.
q Использование механизма исключений (exception) для отслеживания нарушений доступа к памяти (0xEh в системах Intel)
Разделение
n Возможность нескольким процессам разделять общие адреса памяти
q Эффективнее разделять общие блоки памяти несколькими процессами, чем создавать закрытые копии.
Логическая организация
n Программы имеют модульную структуру
n Модули могут создаваться и компилироваться независимо
n Можно установить различную степень защиты для модулей (только для чтения, только для выполнения и т.д.)
n Можно разделять модули между процессами
Физическая организация
n Двухуровневая архитектура памяти
q Основная
q Вторичная
n Основной задачей является эффективная организация потоков информации между основной и вторичной памятью
Распределение памяти
n Фиксированное распределение
n Динамическое распределение
n Система двойников
n Простая страничная организация
n Простая сегментная организация
n Страничная организация ВП
n Сегментная организация ВП
Фиксированное распределение
n Любой процесс, чей размер меньше или равен размеру раздела может быть загружен в свободный раздел
n Если все разделы заняты, то система может выгрузить простаивающий процесс во вторичную память
n Программы, которые не помещаются в раздел могут быть созданы с использованием оверлеев (overlays).
Алгоритм размещения при фиксированном распределении
n Разделы одинакового размера
q Не имеет значения какой свободный раздел выбрать для использования.
n Разделы разного размера
q Использовать наименьший раздел, способный вместить процесс
q Очередь процессов для каждого раздела
Динамическое распределение
n Разделы имеют переменную длину
n Процесс распределяет памяти ровно столько, сколько требуется
n Возможно появления «дыр» в памяти – внешняя фрагментация памяти.
n Для преодоления фрагментации используется метод уплотнения для перемещения процессов в смежные области памяти; свободная память собирается в один блок.
Динамическое распределение. Алгоритм размещения.
n Первый подходящий блок памяти
n Наилучший подходящий
Динамическое распределение. Система двойников.
n Всё доступное пространство считается единым блоком размером 2U
n При запросе размером s, таким, что 2U-1 < s <= 2U, выделяется весь блок
n В противном случае блок разделяется на два эквивалентных двойника размерами 2U-1
n Если 2U-2 < s <= 2U-1, то по запросу выделяется один из двойников.
Перемещение. Типы адресов.
n Логический адрес (Logical). Ссылка на ячейку памяти, не зависящая от текущего расположения данных в памяти
n Относительный адрес (Relative). Частный случай логического адреса, когда адрес рассчитывается относительно известной точки в программе.
n Физический адрес (абсолютный, physical). Действительное расположение ячейки в основной памяти.
Перемещение.
n Абсолютные (физические) адреса памяти известны только при загрузке программы в память.
n Процесс может перемещаться между различными разделами в результате операций свопинга
n Уплотнение также вызывает перемещение процесса в основной памяти.
Страничная организация
n Разделение физической памяти на блоки равной длины и разделение процесса на блоки этой же длины
n Блоки процесса называются страницы (pages). Блоки основной памяти – фреймы (frames).
n Операционная система поддерживает таблицу страниц для каждого процесса
q Содержит расположение кадра для каждой страницы процесса
q Адрес памяти представлен адресом страницы и смещением внутри страницы.
Сегментация
n Сегменты программы могут иметь разный размер
n Существует максимальный размер сегмента
n Адрес состоит из двух частей: номера сегмента и смещения внутри сегмента
n Так как сегменты имеют переменный размер, сегментация похожа на динамическое распределение.
Виртуальная память.
Основные идеи
n Обращения логическим адресам памяти динамически транслируются в физические адреса во время исполнения
q Процесс может быть выгружен на диск и вновь загружен в основную память таким образом он может находится в разных местах основной памяти
n Процесс может быть разбит на несколько блоков (страниц/сегментов), которые не обязательно занимают смежные адреса в основной памяти
n Нет необходимости загружать в основную память сразу все блоки.
Выполнение программы
1. Операционная система помещает в основную память несколько блоков (страниц/сегментов) программы
Множество блоков, загруженных в основную память называется резидентным множеством
1. При обращении процесса к логическому адресу, отсутствующего в оперативной памяти блока, генерируется прерывание.
2. Операционная система переводит процесс в состояние блокировки.
3. Блок процесса, которому принадлежит логический адрес помещается (погружается) в основную память
1. Операционная система инициирует операцию ввода-вывода с диска
2. К процессору подключается другой процесс (поток) из очереди готовых.
3. После завершения операции ввода-вывода генерируется прерывание.
4. Система переводит блокированные процесс в состояние готовности.
Преимущества технологии виртуальной памяти
n Больше процессов может одновременно находится в основной памяти
q Загружены только некоторые блоки процессов
q При большом количестве процессов в основной памяти высока вероятность существования готовых к выполнению процессов в любой момент времени.
n Процесс может быть больше, чем вся основная память.
Типы памяти
n Основная память
q Оперативная (реальная) память, где может выполняться процесс.
n Виртуальная память
q Дисковая память
q Обеспечивает эффективную многозадачность, снимая ограничения на объём основной памяти.
n Виртуальное адресное пространство (ВАП).
q Диапазон ячеек памяти, доступных процессу
q Не все адреса ВАП должны быть спроецированы на основную память при исполнении процесса.
Пробуксовка (Thrashing)
n Выгрузка из основной памяти активных блоков – блоки, которые требуются процессу для выполнения
n Система тратит больше времени на перемещение блоков между основной и вторичной памятью, чем на исполнение программ.
Принцип локализации
1. Обращения к коду и данным в операционной системе имеют тенденцию к кластеризации.
2. Только несколько блоков процесса требуются для исполнения в короткие промежутки времени.
3. Есть возможность делать реальные оценки необходимых в ближайшем будущем процессу блоков.
Принцип локализации даёт надежду на
эффективность работы виртуальной памяти.
Поддержка функционирования ВП
n Аппаратное обеспечение должно поддерживать сегментную, страничную или сегментно-страничную организацию
n Операционная система должна иметь возможность для переноса страниц и /или сегментов между основной и вторичной памятью.
Страничная организация
n Каждый процесс имеет собственную таблицу страниц (page table).
n Каждая запись таблицы страниц (page table entry - PTE) содержит соответствующий странице номер кадра в основной памяти.
n Должен существовать бит присутствия, определяющий находится ли страница в основной памяти или нет.
n При обращении к отсутствующей в основной памяти странице генерируется прерывание отказ страницы (Page Fault)
Бит модификации в таблице страниц
n Бит модификации, определяющий были ли модифицированы данные странице, с момента её загрузки в основную память.
n Если изменений не было, то страницу перед освобождением не требуется перемещать во вторичную память.
Таблицы страниц при многоуровневой организации
n Таблицы страниц могут занимать слишком много места в оперативной памяти
n Таблицы страниц также располагаются в виртуальной памяти.
n Только часть таблицы страниц может располагаться в основной памяти при выполнении процесса.
Ассоциативный буфер трансляции (TLB – Translation Lookaside Buffer)
n Каждое обращение к виртуальному адресу может вызывать два обращения к физическому адресу
q Для считывания таблицы страниц
q Для чтения данных с кадра основной памяти
n Для решения этой проблемы существует высокоскоростной кэш для часто используемых PTE, который называется TLB.
Функционирование TLB
n При обращении к виртуальному адресу, процессор сначала обращается к TLB
n Если PTE присутствует в TLB (попадание в TLB), номер кадра извлекается из TLB и формируется адрес в основной памяти
n При промахе в TLB процессор использует номер страницы для обращения к PTE.
n При обращении к виртуальному адресу проверяется наличие страницы в основной памяти
n При отсутствии генерируется исключение
n Производится обновление TLB для включения нового PTE.
Размер страницы
n Меньше размер страницы – меньше внутренняя фрагментация
n Меньше размер страницы – больше страниц требуется процессу
n Больше страниц процесса – больше памяти отводится под таблицы страниц
n Вторичная память эффективнее работает с большими блоками данных – эффективней использовать большие страницы.
n Малый размер страницы – большее количество страниц можно держать в оперативной памяти
n После некоторого времени исполнения процесса, страницы памяти будут содержать все необходимые процессу данные (принцип локализации). Частота страничных отказов будет низкой.
n Увеличение размера страницы приводит к тому, что страницы содержат данные, которые располагаются вдалеке от последних обращений к памяти. Частота страничных отказов возрастает.
Сегментация
n Сегменты могут иметь разные, динамически изменяемые размеры
n Упрощается обработка структур данных изменяемого размера
n Упрощается совместное использование кода и данных разными процессами
n Улучшается защита.
Таблицы сегментов
n Располагается в основной памяти
n Содержит начальный адрес сегмента и его длину
n Существует бит присутствия сегмента в основной памяти
n Дополнительные биты: модификации, доступа.
Сегментно-страничная организация
n Страничная организация
q Прозрачна для программиста
q Устраняет внешнюю фрагментацию
n Сегментная организация
q Непрозрачна для программиста
q Модульность
q Возможность обработки структур данных переменной длины
q Защита
q Совместное использование памяти
Задачи управления виртуальной памятью
Задача:
n Выборки
n Размещения
n Замещения
n Проецирования
Стратегия выборки (Fetch Policy)
n Определяет момент времени, когда страница должна быть помещена в основную память
q По требованию
q Предварительная выборка
n Кластеризация (Windows 2000)
n Интеллектуальная выборка (Windows XP)
Стратегия размещения
n Определяет место в основной памяти, где должен быть расположен блок
n Не имеет значения для страничной или сегментно-страничной организации.
n Приобретает первостепенную важность при построении систем с неоднородной памятью (например, на базе NUMA)
Стратегия замещения
n Определяет какую страницу основной памяти требуется заместить.
n Вероятность обращения к замещаемой странице в ближайшем будущем должна быть минимальной.
n Все стратегии замещения основаны на предсказании будущего использования страницы, основываясь на данных из прошлого.
Алгоритмы замещения
n Оптимальный
n Дольше всех не используемая (Least Recently Used – LRU)
n FIFO
n Часовой алгоритм (Clock Policy)
Оптимальный алгоритм
n Выбирает на замещение страницу к которой дольше всего не будет обращений.
n Реализовать не возможно, т.к. нельзя знать все будущие события в системе.
LRU
n Выбирает на замещение страницу которая дольше всех не использовалась
n В соответствие с принципом локализации считается, что в ближайшем будущем к этой странице не будет обращений.
n С каждой страницей должна быть сопоставлена информация о времени последнего использования.
FIFO
n Рассматривает все страницы в памяти как круговой буфер.
n Страницы удаляются из буфера по принципу карусели (Round-robin).
n Самый простой алгоритм в реализации.
n Удаляется страница памяти, которая находится там дольше всего.
n Эта страница может снова понадобится в ближайшем будущем.
Clock Policy (версия 1)
n Все загруженные страницы организованы в виде кругового буфера
n Существует бит использования (Use bit)
n При загрузке страницы в основную память бит устанавливается в 1
n При обращении к странице бит устанавливается в 1
n Замещению подвергается первая встреченная страница со сброшенным битом.
n При операции замещения все встреченные установленные биты сбрасываются.
Clock Policy. (версия 2)
n Кадры страниц разделены на категории
q Не использован, не модифицирован (u=0, m=0)
q Использован, не модифицирован (u=1, m=0)
q Не использован, модифицирован (u=0, m=1)
q Использован, модифицирован (u=1, m=
n Сканируем буфер кадров, начиная с текущего положения. Бит u не изменяем. Первый же кадр (u=0, m=0) замещается.
n Если шаг №1 не дал результатов, то ищем кадр с (u=0, m=1), во время сканирования сбрасываем биты использования. Перед замещением содержимое кадра сбрасывается на диск.
n Если шаг №2 не дал результатов, то переходим к шагу №1.
Буферизация страниц
n Система выбирает страницу на замещение по принципу FIFO
n Замещаемые страницы не удаляются из основной памяти, а попадают один из списков:
q Список модифицированных страниц
q Список свободных станиц
Использование буферизации страниц в Windows 2000
n Состояния фреймов страниц
q Активная (Active/ Valid)
q Переходная (Transition)
q Простаивающая (Standby)
q Модифицированная (Modified)
q Модифицированная, но не записываемая (Modified no-write)
q Свободная (Free)
q Обнулённая (Zeroed)
q Аварийная (Bad)
Управление резидентным множеством
Основной вопрос:сколько основной памяти требуется выделить процессу?
n Чем меньше памяти выделяется процессу, тем большее количество процессов может находится в основной памяти и тем выше вероятность существования готовых к исполнению процессов.
n При небольшом количестве страниц процесса в основной памяти частота страничных отказов достаточно высока.
n После определённого предела дополнительное выделение основной памяти процессу в соответствии с принципом локализации не будет приводить к значительному снижению частоты страничных отказов.
Размер резидентного множества
n Фиксированное распределение
q Процессу выделяется фиксированное число страниц основной памяти для исполнения
q При обработке страничного отказа система замещает страницы процесса
n Переменное распределение
q Число страниц основной памяти, выделяемых процессу изменяется в течение жизни процесса.
Фиксированное распределение, локальное замещение.
n Необходимо заранее решить вопрос о количестве кадров, выделяемых процессу
n При выделении слишком малого количества памяти получаем высокую частоту страничных отказов
n При слишком большом количестве кадров получаем малое количество процессов в основной памяти.
n При исчерпании резерва резидентного множества страница замещается другой страницей того же процесса.
Переменное распределение, глобальная область видимости
n Операционная система держит список свободных страниц.
n При наступлении страничного отказа, операционная система включает страницу в резидентное множество процесса.
n При нехватке свободных страниц система производит операцию замещения страницы.
Переменное распределение, локальная область видимости
n При загрузке процесса ему в качестве резидентного множества выделяется некоторое количество страниц, исходя из типа приложения, запроса программы или других критериев. Для заполнения рабочего множества используется стратегия выборки по требованию или предварительная выборка.
n При возникновении страничного отказа и заполнении резидентного множества страница для замещения выбирается среди резидентного множества процесса, сгенерировавшего отказ.
n Система периодически проводит переоценку распределения памяти процессам.
Стратегия рабочего множества (working set strategy)
Управление рабочими множествами (наборами) в Windows 2000
Диспетчер рабочих наборов
Диспетчер настройки баланса
n Все процессы начинают жизненный цикл с одинаковыми максимальными и минимальными размерами рабочего набора (345 и 50 страниц соответственно для систем с большим объёмом памяти)
n При возникновении страничного отказа система, система проверяет лимиты рабочего набора процесса и объём свободной памяти.
n Если условия позволяют диспетчер памяти разрешает процессу увеличить размер рабочего множества до максимума и даже превысить его, если достаточно свободных страниц.
n При нехватке памяти система заменяет страницы в рабочем наборе.
Управление рабочими наборами в Windows 2000
n При слишком частой генерации модифицированных страниц вызывается диспетчер рабочих наборов, который инициирует автоматическое усечение рабочего набора для увеличения объёма свободной памяти.
q Подсчитывает, сколько страниц при необходимости можно изъять из рабочего набора процессов, если их рабочий набор превышает минимальный.
q Оптимально упорядочивает список процессов – кандидатов на усечение рабочего набора
q Если с момента усечения рабочего набора процесс вызовет определённое количество страничных отказов, он исключается из числа кандидатов на усечение до следующего цикла усечения (через 6 секунд)
q Для усечения рабочего набора используется часовой алгоритм для определения исключаемых страниц (начиная с Windows XP/2003 используется единый алгоритм для много и однопроцессорных систем)
Управление вводом-выводом
Структурная организация компьютерных систем Дж. фон Неймана
n Устройство оперативной памяти для хранения данных и программ
n Центральное процессорное управление (ЦПУ)
q Арифметическое и логическое устройство
q Устройство управления выполнением программы
n Оборудование ввода-вывода
n Связи между компонентами – магистраль (шина)
Магистраль
n Средство соединения двух и более устройств в компьютерной системе
n Обычно имеется общая магистраль для всех устройств в компьютере
n Структура магистрали
q Линии адреса
q Линии данных
q Линии управления
Линии адреса
n Определяют адреса источника и приёмника данных
n Ширина адресной магистрали определяет максимальный объём адресуемой памяти.
q Типичные разрядности (битов): 16 (Intel 8080), 20 (Intel 8086), 32 (Intel 80386), 36 (Intel Pentium), 64 (Intel Itanium /Itanium 2)
Линии данных
n Передаёт данные (на уровни магистрали не делается различий между «данными» и «инструкциями»)
n Ширина магистрали данных определяет производительность системы
q Типичные разрядности (битов): 8 (Intel 8080), 16 (Intel 8086), 32 (Intel 80386), 64 (Intel Pentium)
Линии управления
n Передаёт управляющие и синхронизирующие сигналы
q Сигналы на чтение/запись памяти
q Запросы на прерывание
q Тактовые импульсы (синхронизирующие сигналы)
Сложность систем ввода-вывода
n Широкий набор различных типов периферийных устройств
q Передача данных различного объёма
q На разных скоростях
q В различных форматах
n Устройства обладают меньшей производительностью, чем память или ЦПУ
n Требуют специальных модулей (контроллеров) ввода-вывода
Модуль (контроллер) ввода-вывода
n Имеет интерфейс для подключения к ЦПУ и памяти, т.е. к системной магистрали.
n Имеет интерфейс подключения к одному или нескольким периферийным устройствам
Функции модуля ввода-вывода
n Управление и синхронизация
n Взаимодействие с ЦПУ
n Взаимодействие с устройством
n Буферизация данных
n Обнаружение ошибок
Алгоритм работы с модулем ввода-вывода
1. ЦПУ запрашивает статус устройства у модуля ввода-вывода.
2. Модуль ввода-вывода возвращает статус.
3. Если готово, ЦПУ запрашивает передачу данных.
4. Модуль ввода-вывода получает данные с устройства.
5. Модуль передаёт данные ЦПУ
6. Для операций передачи данных существует несколько решений.
Решения для организации ввода-вывода
n Программируемый (PIO)
n Управляемый прерываниями
n Прямой доступ к памяти (DMA)
Ввод-вывод в операционных системах
n Эффективность
q Большинство устройств ввода-вывода намного медленнее основной памяти.
n Использование мультипрограммирования позволяет некоторым процессам ждать завершения операций ввода-вывода, выполняя в это время другие процессы
n Операции подкачки в основную память являются операциями ввода-вывода.
q Даже при наличии большого объёма основной памяти операции ввода-вывода будут отставать от процессора
n Универсальность
q Желательна единая модель управления различными устройствами
q Требуется скрыть детали управления устройствами в низкоуровневых модулях (драйверах устройств).
q Предоставить процессам работу с устройствами посредством высокоуровневых вызовов:
n Открытие/закрытие, чтение/запись, блокирование/разблокирование и т.п.
Подсистема ввода-вывода в ОС (1)
n Организация параллельной работы устройств ввода-вывода и процессора
n Согласование скоростей обмена и кэширование данных
n Безопасное и защищённое разделение устройств и данных между процессами
n Обеспечение удобного логического интерфейса между устройствами и остальной частью системы
n Поддержка широкого спектра драйверов с возможностью простого включения в систему нового драйвера
n Динамическая загрузка и выгрузка драйверов по указанию пользователя или за счёт автоматического реконфигурирования (PnP)
n Поддержка нескольких файловых систем
n Поддержка синхронных и асинхронных операций ввода-вывода
n Поддержка перехода системы и отдельных устройств в состояния с низким энергопотреблением
Организация параллельной работы устройств ввода-вывода и процессора
n Каждое устройство снабжено модулем (контроллером) ввода-вывода
n Модуль ввода-вывода взаимодействует с драйвером
n Под управлением модуля ввода-вывода устройство может некоторое время функционировать независимо от процессора
n От подсистемы ввода-вывода требуется спланировать в реальном времени запуск и приостановку большого количества драйверов и минимизировать загрузку процессора задачами ввода-вывода
n Распределение всех драйверов по уровням приоритета обслуживания прерываний
Согласование скоростей обмена и кэширование данных
n Все устройства имеют различные скоростные характеристики.
q Например пересылка файла через модемное соединение (операция ввода-вывода с жёсткого диска на коммуникационный порт)
n Буферизация в операциях ввода-вывода
q Без буферизации (прямой ввод-вывод, direct I/O)
q Буферизированный ввод-вывод (buffered I/O)
n С одним буфером
n С двумя буферами
n С круговым буфером
Буферизация в операциях ввода-вывода
n Двойная буферизация
q Используются два системных буфера
q Процесс может записывать или считывать из одного буфера, пока система заполняет или освобождает другой
n Круговой буфер
q Используется больше двух буферов
q Буферы организуются в круговой
q Используется при интенсивных операциях ввода-вывода процессом
Кэширование данных
n Буферизация в основной памяти данных для всех драйверов файловых систем
q Кэширование на основе логических блоков (смещение внутри дисковых разделов)
q Кэширование на основе виртуальных блоков (смещение внутри файлов)
n Опережающее кэширование
Обеспечение удобного логического интерфейса между устройствами и остальной частью системы
n Поддержка файловой модели представления периферийных (базисная модель)
q Любое устройство выглядит для прикладного программиста как последовательность байтов
n Подобная модель для некоторых устройств выглядит слишком бедной и на её основе строятся модели управления для конкретных устройств
q Графический адаптер
q Принтер
q Сетевой обмен
q и т.д.
Поддержка широкого спектра драйверов
n Необходимо наличие чёткого и открытого интерфейса между драйверами и другими компонентами ОС
n Драйвер взаимодействует с модулями ядра ОС и с модулем ввода-вывода
q Два типа интерфейсов для драйвера
n «Драйвер-ядро» (Driver Kernel Interface, DKI)
n «Драйвер-устройство» (Driver Device Interface, DDI)
q ОС может поддерживать несколько типов DKI/DDI для устройств различных классов
q Для разработки драйверов разработчики ОС предоставляют Driver Development Kit (DDK)
n Типы драйверов
q Драйверы файловой системы
q Драйверы Windows 2000
q Унаследованные (Legacy) драйверы Windows NT
q Драйверы видеоадаптеров
q WDM (Windows Driver Model)
n Драйверы магистралей (шин)
n Функциональные драйверы
n Драйверы фильтров
Обработка прерывания драйвером Windows 2000
1. Фаза 1
1. Процессор функционирует на некотором уровне IRQL.
2. Устройство генерирует прерывание. Прерывание ловится (traps) ISR диспетчера прерываний ОС
3. Диспетчер прерываний вызывает ISR драйвера с которым сопоставлено прерывание
4. ISR производит минимальную обработку и оставляет менее приоритетные операции DPC, ставя её в очередь на обслуживание
2. Фаза 2
1. IRQL процессора «падает» до DPC/Dispatch
2. Происходит опустошение очереди отложенных процедур.
Поддержка асинхронного и синхронного ввода-вывода
n Синхронные операции блокируют инициировавший операцию ввода-вывода процесс до окончания операции
n Асинхронные операции позволяют процессу продолжить своё выполнение параллельно с операцией ввода-вывода.
q Сложно проектировать программы с использованием асинхронных операций
q Требуется сложная синхронизация
n Диспетчер ввода-вывода ОС обычно использует асинхронные операции ввода-вывода. Синхронные операции предоставляются пользователю в виде системных вызовов.
Асинхронный ввод-вывод в Windows 2000
n Синхронизация на объекте ядра «файл»
q Нет способа определить какая операция завершилась при множественных запросах на ввод-вывод.
n Синхронизация на объекте ядра «событие», сопоставленное с операцией ввода-вывода
q Выдать запрос и обработать результат могут различные потоки.
q WaitForMultipleObjects может ожидать максимум на 64 объектах.
q Множественные запросы могут вызвать множественные переключения контекста
n Постановка результатов ввода-вывода в очередь APC (Asynchronous Procedure Call)
q Выдать запрос ввода-вывода и обработать результаты должен один и тот же поток.
n Использование порта завершения ввода-вывода (Input-Output Completion Port)
q Выдать запрос и обработать результат могут различные потоки.
q Существует ограниченный пул готовых к обслуживанию результатов запросов потоков.
q Система управляет активацией поток для предотвращения лишних переключений контекста.
q Необходимо тщательно выбирать алгоритм управления размером пула.
q Могут существовать временные перегрузки системы.
Многослойные модели операционных систем
Завершение операции ввода-вывода в Windows 2000
1. Фаза 1
1. DCP-процедура вызывает диспетчер ввода-вывода для обработки исходного запроса на ввод-вывод
2. Диспетчер ввода-вывода ставить APC в очередь для завершения обработки запроса ввода-вывода в контексте вызывающего потока
2. Фаза 2
1. При следующем переключении на вызывающий поток генерируется прерывание APC.
2. Диспетчер прерываний передаёт управление APC-процедуре диспетчера ввода-вывода
3. APC-процедура ядра записывает данные в адресное пространство потока и переводит описатель файла в свободное состояние.