Защита от инверсий приоритетов

⇐ ПредыдущаяСтр 4 из 4

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

Какие же механизмы защиты от этой проблемы используют разработчики ОСРВ? Наиболее широко распространенный и проверенный механизм – это наследование приоритетов.

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

Другой, несколько менее распространенный метод, называется Протокол Предельного Приоритета (Priority Ceiling Protocol) [6]. Метод этот заключается в добавлении к стандартным свойствам объектов синхронизации параметра, определяемого максимальным приоритетом потока, которые к этому объекту обращаются. Если этот параметр установлен, то приоритет любого потока, обращающегося к этому объекту синхронизации, будет увеличен до указанного уровня, и, таким образом, не сможет быть вытеснен никаким потоком, который может нуждаться в заблокированном им ресурсе. После разблокирования ресурса, приоритет потока понижается до начального уровня. Таким образом, получается нечто вроде предварительного наследования приоритетов. Однако этот метод имеет ряд серьезных недостатков. В первую очередь, на разработчика ложиться работа по «обучению» объектов синхронизации их уровню приоритетов. Во вторых, возможны задержки в запуске высокоприоритетных потоков на время отработки низкоприоритетных потоков. В целом максимально эффективно этот механизм может быть использован в случае, когда имеется один поток жесткого реального времени и несколько менее приоритетных потоков, разделяющих с ним ресурсы.

11. Межпроцессное взаимодействие (англ. Inter-Process Communication, IPC) — набор способов обмена данными между множеством потоков в одном или более процессах. Процессы могут быть запущены на одном или более компьютерах, связанных между собой сетью. IPC-способы делятся на методы обмена сообщениями, синхронизации, разделяемой памяти и удаленных вызовов (RPC). Методы IPC зависят от пропускной способности и задержки взаимодействия между потоками и типа передаваемых данных.

IPC наряду с концепцией адресного пространства является основой для разграничения адресного пространства.

Метод	Реализуется (операционной системой или другим окружением)
Файл	Все операционные системы.
Сигнал	Большинство операционных систем; некоторые системы, как например, Windows, только реализуют сигналы в библиотеке запуска Си, но не обеспечивают их полноценной поддержки для использования методов IPC.
Сокет	Большинство операционных систем.
Канал	Все системы, соответствующие POSIX.
Именованный канал	Все системы, соответствующие POSIX.
Семафор	Все системы, соответствующие POSIX.
Разделяемая память	Все системы, соответствующие POSIX.
Обмен сообщениями (без разделения)	Используется в парадигме MPI, Java RMI, CORBA и других.
Проецируемый в память файл	Все системы, соответствующие POSIX; несет риск появления состояния гонки в случае использования временного файла. Windows также поддерживает эту технологию, но использует API отличный от POSIX.
Очередь сообщений	Большинство операционных систем.
Почтовый ящик	Некоторые операционные системы.

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

Проблема обедающих философов

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

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

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

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

Проблема читателей и писателей

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

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

Проблема спящего брадобрея

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

В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается — он уже не ждет); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.

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

Выгружаемые ресурсы-безболезненно забрать у владеющего им процесса.

Невыгружаемый ресурс-не может быть безболезненно отобран у процесса.

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

1. Запрос ресурсов

2. Использование ресурсов

3. Возврат ресурсов

Пр А	Пр Б
Запрос р-са 1	Запрос р-са 2
Запрос р-са 2	Запрос р-са 1
Использование р-ов	Использование р-ов
Возврат р-са 2	Возврат р-са 1
Возврат р-са 1	Возврат р-са 2

Условие взаимоблокировок:

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

2. Условие удержания и ожидания. Процессы в данный момент удерживающие полученные раннее ресурсы могут запрашивать новые ресурсы.

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

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

Обнаружение и устранение взаимоблокировок:

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

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

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

Избежание взаимоблокировок:

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

Предотвращение взаимоблокировок:

1. Атака условия взаимного исключения

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

2. Атака условия удержания и ожидания

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

Недостатки данного способа решения:

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

· Ресурсы не будут использоваться оптимально

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

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

4. Атака условия циклического ожидания

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

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

5. Алгоритм банкира

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

Суть алгоритма:

· Предположим, что у системы есть «х» устройств.

· Операционная система принимает запрос от пользовательского процесса, если его макс потребность не превышает «х».

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

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

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

Выводы: Имеются различные способы выхода из взаимоблокировок.

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

· Перезагрузка системы

· Рестарт системы с контрольной точки

Контрольная точка - полное состояние ПК сохраненное на внешнем носителе.

14. Выгружаемые ресурсы

См.13й (в интернетах нет нихчего, инфа 146%).

15. Невыгружаемые ресурсы

См.13й.

16. FAT (англ. File Allocation Table — «таблица размещения файлов») — классическая архитектура файловой системы, которая из-за своей простоты всё ещё широко используется для флеш-дисков и карт памяти. В недавнем прошлом использовалась в дискетах, на жёстких дисках и других носителях информации.

Разработана Биллом Гейтсом и Марком МакДональдом (англ.) в 1976—1977 годах. Использовалась в качестве основной файловой системы в операционных системах семейств DOS и Windows (до версии Windows 2000).

Структура FAT следует стандарту ECMA-107 и подробно определяется официальной спецификацией от Microsoft, известной под названием FATGEN.

FAT16	FAT32
Реализована и используется большинством операционных систем (MS-DOS, Windows 95/98/ Me, Windows 2000 и Windows XP, OS/2, UNIX).	На данный момент поддерживается только в Windows 95/98/ Me, Windows 2000 и Windows XP (бородатая статья, даже Висты нет, будьте оптимистами – врите, что все всё реализовали)
Очень эффективна для логических дисков размером менее 256 Мбайт.	Не работает с дисками объемом менее 512 Мбайт.
Поддерживает сжатие дисков, например по алгоритму DriveSpace.	Не поддерживает сжатие дисков.
Обрабатывает максимум 65 525 кластеров, размер которых зависит от объема логического диска. Так как максимальный размер кластеров равен 32 Кбайт, FAT16 может работать с логическими дисками объемом не более 2 Гбайт.	Способна работать с логическими дисками объемом до 2 047 Гбайт при максимальном размере кластеров в 32 Кбайт.
Чем больше размер логического диска, тем меньше эффективность хранения файлов в FAT'16-системе, так как увеличивается и размер кластеров. Пространство для файлов выделяется кластерами, и поэтому при максимальном объеме логического диска файл размером 10 Кбайт потребует 32 Кбайт, а 22 Кбайт дискового пространства пропадет впустую.	На логических дисках объемом менее 8 Гбайт размер кластеров составляет 4 Кбайт.

Максимально возможная длина файла в FAT32 равна 4 Гбайт за вычетом 2 байтов. Win32-приложения могут открывать файлы такой длины без специальной обработки. Остальные приложения должны использовать прерывание Int 21h, функцию 716С (FAT32) с флагом открытия, равным EXTEND-SIZE (1000h).

В файловой системе FAT32 на каждый кластер в таблице размещения файлов отводится по 4 байта, тогда как в FAT16 - по 2, а в FАТ12 - по 1, 5.

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

Файловые системы (NTFS)

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

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

NTFS (аббревиатура New Technology File System — Файловая Система Новой Технологии) — стандартная файловая система для семейства операционных систем Microsoft Windows NT.

Представлена 27 июля 1993 вместе с Windows NT 3.1. NTFS разработана на основе файловой системы HPFS (аббревиатура High Performance File System — Высокопроизводительная Файловая Система), создававшейся Microsoft совместно с IBM для операционной системы OS/2.

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

Спецификации файловой системы являются закрытыми. Обычно размер кластера равен 4Кб. На практике не рекомендуют создавать тома более 2ТБ. Жесткие диски только достигли таких размеров, возможно в будущем нас ждет новая файловая система.

Во время установки ОС Windows ХР предлагается отформатировать диск в системе FAT или NTFS. При этом имеется в виду FAT32.

Все файловые системы построены на принципе: один кластер – один файл. Т.е. один кластер хранит данные только одного файла.

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

Рассмотрим на примере одного тома на диске объемом 120Гб и файла размером 10Кб.

Для FAT32 размер кластера будет 32Кб, а для NTFS – 4Кб.

В FAT32 такой файлзаймет 1 кластер, при этом останется 32-10=22Кб незанятого места.

В NTFS такой файлзаймет 3 кластера, при этом останется 12-10=2Кб незанятого места.

Таким образом, переход от FAT32 к NTFS позволяет более оптимально использовать жесткий диск при наличии большого количества мелких файлов в системе.

⇐ Предыдущая 1 2 34