Материал: Ответы к экзамену (Операционные системы)
Динамическая память, алгоритмы управления.
распределение памяти динамическими разделами. Каждая программа занимает столько места, сколько она требует. Если программе не хватило памяти, то оставшаяся её часть хранится на диске. Эта часть вызывается по мере необходимости. Для организации динамического распределение используют процедуру свопинга (подкачка или откачка программ). Откачка используется в тех случаях, когда выпавшая из обработки часть программы перемещается на диск. При таком способе организации памяти так же возможна фрагментация памяти.
Распределение динамической памяти - память выделяется во время выполнения в куче. Это используется, когда количество (размер) памяти является переменной и известно только во время выполнения. Динамическое распределение достигается с помощью определенных функций, таких как malloc(), calloc(), realloc()mв C и "new", "delete" в С++.
Виртуальная память, файл подкачки.
Виртуальная память — метод управления памятью компьютера, позволяющий выполнять программы, требующие больше оперативной памяти, чем имеется в компьютере, путём автоматического перемещения частей программы между основной памятью и вторичным хранилищем (например, жёстким диском). Для реализации необходима аппаратная поддержка и возможности ОС.
В системе виртуальные адреса с помощью блока управления памятью транслируются в физические адреса в памяти компьютера. Управление виртуальными адресными пространствами, соотнесение физической и виртуальной памяти, а также перемещение фрагментов памяти между основным и вторичным хранилищами выполняет операционная система.
В настоящее время виртуальная память аппаратно поддерживается в большинстве современных процессоров.
С помощью виртуальной памяти можно:
освободить программиста от необходимости вручную управлять загрузкой частей программы в память и согласовывать использование памяти с другими программами;
предоставлять программам больше памяти, чем физически установлено в системе;
в многозадачных системах изолировать выполняющиеся программы друг от друга путём назначения им непересекающихся адресных пространств.
Страничная организация виртуальной памяти
В большинстве современных ОС виртуальная память организуется с помощью страничной адресации.
Оперативная память делится на страницы: области памяти фиксированной длины, которые являются минимальной единицей выделяемой памяти (то есть даже запрос на 1 байт от приложения приведёт к выделению ему страницы памяти).
Исполняемый процессором пользовательский поток обращается к памяти с помощью адреса виртуальной памяти, который делится на номер страницы и смещение внутри страницы.
Процессор преобразует номер виртуальной страницы в адрес соответствующей ей физической страницы при помощи буфера ассоциативной трансляции (TLB). Если ему не удалось это сделать, то требуется дозаполнение буфера путём обращения к таблице страниц (так называемый Page Walk), что может сделать либо сам процессор, либо ОС.
Если страница была выгружена из оперативной памяти, то ОС подкачивает страницу с жёсткого диска в ходе обработки события Page fault. При запросе на выделение памяти ОС может «сбросить» на жёсткий диск страницы, к которым давно не было обращений.
Критические данные (например, код запущенных и работающих программ, код и память ядра системы) обычно находятся в оперативной памяти.
Сегментная организация виртуальной памяти
Виртуальное пространство делится на части произвольного размера — сегменты.
Для каждого сегмента могут быть назначены права доступа к нему пользователя и его процессов.
При загрузке процесса часть сегментов помещается в оперативную память (при этом для каждого из этих сегментов ОС подыскивает подходящий участок свободной памяти), а часть сегментов размещается в дисковой памяти.
Сегменты одной программы могут занимать в оперативной памяти несмежные участки.
Во время загрузки система создает таблицу сегментов процесса, в которой для каждого сегмента указывается начальный физический адрес сегмента в оперативной памяти, размер сегмента, правила доступа, признак модификации, признак обращения к данному сегменту за последний интервал времени и некоторая другая информация.
Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов делаются ссылки на один и тот же участок оперативной памяти, в который данный сегмент загружается в единственном экземпляре.
Система с сегментной организацией функционирует аналогично системе со страничной организацией: время от времени происходят прерывания, связанные с отсутствием нужных сегментов в памяти, при необходимости освобождения памяти некоторые сегменты выгружаются, при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Кроме того, при обращении к памяти проверяется, разрешен ли доступ требуемого типа к данному сегменту.
Виртуальный адрес при сегментной организации памяти может быть представлен парой (g, s), где g — номер сегмента, а s — смещение в сегменте.
Физический адрес получается путём сложения начального физического адреса сегмента, найденного в таблице сегментов по номеру g, и смещения s.
Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное по сравнению со страничной организацией преобразование адреса.
Подкачка страниц
Один из механизмов виртуальной памяти, при котором отдельные фрагменты памяти перемещаются из ОЗУ во вторичное хранилище (жёсткий диск, флеш-память), освобождая ОЗУ для загрузки других активных фрагментов памяти. Такими фрагментами в современных ЭВМ являются страницы памяти.
Временно выгруженные из памяти страницы могут сохраняться на внешних запоминающих устройствах как в файле, так и в специальном разделе на жёстком диске.
Многопоточные программы, стандарт posix.
Многопоточность — свойство платформы (например, операционной системы, виртуальной машины и т. д.) или приложения, состоящее в том, что процесс, порождённый в операционной системе, может состоять из нескольких потоков, выполняющихся «параллельно», то есть без предписанного порядка во времени. При выполнении некоторых задач такое разделение может достичь более эффективного использования ресурсов вычислительной машины.
Определение
POSIX – стандарт системы UNIX, который определяет минимальный интерфейс системных вызовов, который должны поддерживать совместимые с ним системы UNIX (и не только).
Задачи POSIX:
Содействовать облегчению переноса кода прикладных программ на иные платформы.
Способствовать определению и унификации интерфейсов заранее при проектировании, а не в процессе их реализации.
Сохранять по возможности и учитывать все главные, созданные ранее и используемые прикладные программы.
Определять необходимый минимум интерфейсов прикладных программ для ускорения создания, одобрения и утверждения документов.
Развивать стандарты в направлении обеспечения коммуникационных сетей, распределенной обработки данных и защиты информации.
Рекомендовать ограничение использования бинарного (объектного) кода для приложений в простых системах.
Состав
Основные определения (англ. Base definitions) — список основных определений и соглашений, используемых в спецификациях, и список заголовочных файлов языка Си, которые должны быть предоставлены соответствующей стандарту системой.
Оболочка и утилиты (англ. Shell and utilities) — описание утилит и командной оболочки sh, стандарты регулярных выражений.
Системные интерфейсы (англ. System interfaces) — список системных вызовов языка Си.
Обоснование (англ. Rationale) — объяснение принципов, используемых в стандарте.
Синхронизация потоков.
Для синхронизации потоков применяются семафоры, мьютексы и критические секции.
Семафор
Семафор – это объект, ограничивающий количество потоков, которые могут войти в заданный участок кода. Семафоры используются для синхронизации и защиты передачи данных через разделяемую память, а также для синхронизации работы процессов и потоков.
Мьютекс
Мьютекс - аналог одноместного семафора, служащий в программировании для синхронизации одновременно выполняющихся потоков.
Мьютекс отличается от семафора тем, что только владеющий им поток может его освободить, т.е. перевести в отмеченное состояние. Мьютексы — это один из вариантов семафорных механизмов для организации взаимного исключения. Они реализованы во многих ОС, их основное назначение — организация взаимного исключения для потоков из одного и того же или из разных процессов.
Критическая секция
Критическая секция — объект синхронизации потоков, позволяющий предотвратить одновременное выполнение некоторого набора операций несколькими потоками. Критическая секция выполняет те же задачи, что и мьютекс.
Семафоры, алгоритм Дейкстры.
Определение
Семафор — объект, ограничивающий количество потоков, которые могут войти в заданный участок кода. Определение введено Эдсгером Дейкстрой в 1962 или 1963 году. Семафоры используются для синхронизации и защиты передачи данных через разделяемую память, а также для синхронизации работы процессов и потоков.
Это объект, над которым можно выполнять действия:
Инициализация семафора (задать начальное значение счётчика);
Захват семафора (ждать, пока счётчик станет больше 0, после этого уменьшить счётчик на единицу);
Освобождение семафора (увеличить счётчик на единицу).
Применение семафоров:
запрет одновременного выполнения заданных участков кода (критические секции);
поочерёдный доступ к критическому ресурсу (важному ресурсу, для которого невозможен (или нежелателен) одновременный доступ);
синхронизация процессов и потоков (например, можно инициировать обработку события отпусканием семафора).
Проблемы семафоров:
можно написать программу с «утечкой семафора», вызвав enter() и забыв вызвать leave(). Реже встречаются ошибки, когда дважды вызывается leave();
семафоры чреваты взаимной блокировкой потоков.
Алгоритм Дейкстры
Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.
Формальное определение
Дан
взвешенный ориентированный граф
без дуг отрицательного веса. Найти
кратчайшие пути от некоторой вершины
графа
до всех остальных вершин этого графа.
Взаимодействие между потоками.
В многопоточной среде часто возникают задачи, требующие приостановки и возобновления работы одних потоков в зависимости от работы других. В частности, это задачи, связанные с предотвращенем конфликтов доступа при использовании одних и тех же данных или устройств из параллельно исполняемых потоков. Для решения таких задач используются специальные объекты для взаимодействия потоков, такие как взаимоисключения (мьютексы), семафоры, критические секции, события и т.п. Многие из этих объектов являются объектами ядра и могут применяться не только между потоками одного процесса, но и для взаимодействия между потоками разных процессов.
Взаимоисключения (mutex, мьютекс) — это объект синхронизации, который устанавливается в особое сигнальное состояние, когда не занят каким-либо потоком. Только один поток владеет этим объектом в любой момент времени. После всех необходимых действий мьютекс освобождается, предоставляя другим потокам доступ к общему ресурсу. Объект может поддерживать рекурсивный захват второй раз тем же потоком, увеличивая счётчик, не блокируя поток, и требуя потом многократного освобождения.
Критические секции обеспечивают синхронизацию подобно мьютексам, за исключением того, что объекты, представляющие критические секции, доступны лишь в пределах одного процесса.
Семафоры представляют собой доступные ресурсы, которые могут быть приобретены несколькими потоками в одно и то же время, пока пул ресурсов не опустеет. Тогда дополнительные потоки должны ждать, пока требуемое количество ресурсов не будет снова доступно.
События. Объект, хранящий в себе 1 бит информации «просигнализирован или нет», над которым определены операции «просигнализировать», «сбросить в непросигнализированное состояние» и «ожидать». Ожидание на просигнализированном событии есть отсутствие операции с немедленным продолжением исполнения потока. Ожидание на непросигнализированном событии приводит к приостановке исполнения потока до тех пор, пока другой поток (или же вторая фаза обработчика прерывания в ядре ОС) не просигнализирует событие. Возможно ожидание нескольких событий в режимах «любого» или «всех». Возможно также создание события, автоматически сбрасываемого в непросигнализированное состояние после пробуждения первого же — и единственного — ожидающего потока (такой объект используется как основа для реализации объекта «критическая секция»).
Условные переменные (condvars). Сходны с событиями, но не являются объектами, занимающими память — используется только адрес переменной, понятие «содержимое переменной» не существует, в качестве условной переменной может использоваться адрес произвольного объекта. В отличие от событий, установка условной переменной в просигнализированное состояние не влечёт за собой никаких последствий в случае, если на данный момент нет потоков, ожидающих на переменной. Установка события в аналогичном случае влечёт за собой запоминание состояния «просигнализировано» внутри самого события, после чего следующие потоки, желающие ожидать события, продолжают исполнение немедленно без остановки. Активно используются в UNIX-подобных ОС.
Порт завершения ввода-вывода. Реализованный в ядре ОС и доступный через системные вызовы объект «очередь» с операциями «поместить структуру в хвост очереди» и «взять следующую структуру с головы очереди» — последний вызов приостанавливает исполнение потока в случае, если очередь пуста, и до тех пор, пока другой поток не осуществит вызов «поместить». Самой важной особенностью IOCP является то, что структуры в него могут помещаться не только явным системным вызовом из режима пользователя, но и неявно внутри ядра ОС как результат завершения асинхронной операции ввода-вывода на одном из дескрипторов файлов.
ERESOURCE. Мьютекс, поддерживающий рекурсивный захват, с семантикой разделяемого или эксклюзивного захвата. Семантика: объект может быть либо свободен, либо захвачен произвольным числом потоков разделяемым образом, либо захвачен всего одним потоком эксклюзивным образом.
Rundown protection. Полудокументированный (вызовы присутствуют в файлах-заголовках, но отсутствуют в документации) объект в ядре Windows. Счётчик с операциями «увеличить», «уменьшить» и «ждать». Ожидание блокирует поток до тех пор, пока операции уменьшения не уменьшат счётчик до нуля.