Системное программное обеспечение

Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом.

V(S): переменная S увеличивается на 1 единым действием. Выборка, наращивание  и запоминание не могут быть  прерваны. К переменной S нет доступа  другим потокам во время выполнения  этой операции.

PCS): уменьшение S на 1, если это возможно. Если 5*0 и невозможно уменьшить  S, оставаясь в области целых  неотрицательных значений, то в  этом случае поток, вызывающий  операцию Р, ждет, пока это уменьшение  станет возможным. Успешная проверка  и уменьшение также являются  неделимой операцией

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

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

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

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

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

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

14. Тупики. Условия возникновения тупиков. Задачи ОС, связанные с решением проблемы тупиков.

Тупики

Приведенный выше пример позволяет  также проиллюстрировать еще  одну проблему синхронизации — взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch), или тупиками. Покажем, что если переставить местами операции Р(е) и Р(b) в потоке-писателе, то при некотором стечении обстоятельств эти два потока могут взаимно блокировать друг друга, Итак, пусть поток-писатель начинает свою работу с проверки доступности критической секции — операции  Р(b), и пусть он первым войдет в критическую секцию. Выполняя операцию  Р(е), он может обнаружить отсутствие свободных буферов и перейти в состояние ожидания. Как уже было показано, из этого состояния его может вывести только поток-читатель, который возьмет очередную запись из буфера. Но поток-читатель не сможет этого сделать, так как для этого ему потребуется войти в критическую секцию, вход в которую заблокирован потоком-писателем. Таким образом, ни один из этих потоков не может завершить начатую работу и возникнет тупиковая ситуация, которая не может разрешиться без внешнего воздействия.

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

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

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

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

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

Тупики могут быть предотвращены  на стадии написания программ, то есть программы должны быть написаны таким  образом, чтобы тупик не мог возникнуть при любом соотношении взаимных скоростей потоков. Так, если бы в  примере, поток А и поток В  запрашивали ресурсы в одинаковой последовательности, то тупик был  бы>в принципе невозможен. Другой, более гибкий подход к предотвращению тупиков заключается в том, что  ОС каждый раз при запуске задач  анализирует их потребности в  ресурсах и определяет, может ли в данной мультипрограммной смеси  возникнуть тупик. Если да, то запуск новой  задачи временно откладывается. ОС может  также использовать определенные правила  при назначении ресурсов потокам, например, ресурсы могут выделяться операционной системой в определенной последовательности, общей для всех потоков. В тех  же случаях, когда тупиковую ситуацию не удалось предотвратить, важно  быстро и точно ее распознать, поскольку  блокированные потоки не выполняют  никакой полезной работы. Если тупиковая  ситуация образована множеством потоков, занимающих массу ресурсов, распознавание  тупика является нетривиальной задачей. Существуют формальные, программнореализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки. Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные потоки/Можно снять только часть из них, освободив ресурсы, ожидаемые остальными потоками, можно вернуть некоторые потоки в область подкачки, можно совершить -«откат» некоторых потоков до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в тех местах, после которых возможно возникновение тупика.

15. Функции ОС по управлению памятью. Типы адресов. Способы преобразования адресов.

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

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

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

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

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

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

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

Типы адресов

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

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

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

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

Совокупность виртуальных адресов  процесса называется виртуальным адресным пространством. Диапазон возможных  адресов виртуального пространства у всех процессов является одним  и тем же. Например, при использовании 32-разрядных виртуальных адресов  этот диапазон задается границами 0000000016и FFFFFFFF16. Тем не менее каждый процесс  имеет собственное виртуальное  адресное пространство — транслятор присваивает виртуальные адреса переменным и кодам каждой программе  независимо.

16. Алгоритмы распределения памяти без использования дискового пространства.

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

Распределение памяти фиксированными разделами

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

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

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

Распределение памяти разделами  переменной величины

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

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

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

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