Взаимоблокировка

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

Условия необходимые для взаимоблокировки:

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

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

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

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

Четыре стратегии избегания взаимоблокировок:

1. Пренебрежением проблемой в целом (вдруг пронесет).

2. Обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется).

3. Динамическое избежание тупиков.

4. Предотвращение четырех условий, необходимых для взаимоблокировок.

Моделирование тупиков с помощью графов.

Условные обозначения

На такой модели очень хорошо проверить возникает ли взаимоблокировка. Если есть цикл, значит, есть и взаимоблокировка.

Выход из взаимоблокировки

Восстановление при помощи принудительной выгрузки ресурса

Как правило, требует ручного вмешательства (например: принтер).

Восстановление через откат

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

С принтером опять будут проблемы.

Восстановление путем уничтожения процесса

Самый простой способ.

Но с принтером опять будут проблемы.

В реальных системах они не годятся.

Предотвращение четырех условий, необходимых для взаимоблокировок

Предотвращение условия взаимного исключения

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

Например, с помощью спулинга для принтера, когда только демон принтера работает с принтером.

Предотвращение условия удержания и ожидания

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

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

Можно выгружать ресурсы, но могут быть проблемы с принтером.

Предотвращение условия циклического ожидания

Способы предотвращения:

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

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

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

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

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

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

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

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

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

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

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

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

3. Высвобождение ресурса.

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

16. Файловые системы (FAT-16, FAT-32)

Название FAT происходит от названия метода организации файлов - Таблица размещения файлов (File Allocation Table)

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

Число 16 означает, что данная файловая система 16-разрядная - для адресации кластеров используется 16 разрядов. Поэтому максимальное количество кластеров составляет 65525, а максимальный размер кластера 128 секторов. максимальный размер раздела FAT16 2 гигабайта. Обычно чем больше размер кластера, тем больше становятся потери дискового пространства.Если на больших дисках записывается большое количество маленьких файлов, то потери дискового пространства будут значительны

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

Из всего выше сказанного следует, что основными недостатками файловой системы FAT16 являются:

• Невозможность поддержки разделов диска размером больше 2 Гб;
• Невозможность работы с файлами размером более 2 Гб;
• Невозможность работы с жесткими дисками емкостью более 8 Гб;
• Ограниченный размер корневой папки, которая может содержать не более 512 элементов.

Файловая система FAT32 представляет собой усовершенствованную версию FAT16, предназначенную для использования на разделах емкостью до 2 Терабайт

Главными отличиями FAT32 от FAT16 являются 28-разрядные номера кластеров, меньший, по сравнению с FAT 16, размер кластера и более гибкая организация корневого каталога, который не ограничен в размере. Однако при небольших размерах кластера, но больших размерах раздела увеличивается размер таблицы расположения файлов, что может замедлить загрузку операционной системы и файловые операции.

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

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

NTFS, как FAT16 и FAT32, использует кластеры для записи файлов на диск. Размер кластера в NTFS по умолчанию зависит от размера диска. поэтому NTFS использует дисковое пространство наиболее эффективно по сравнению с FAT16 и FAT32.

18. Работа с несколькими файловыми системами

Разработчики ОС стремятся обеспечить пользователя возможностью работать сразу с несколькими файловыми системами.

Новая ФС имеет многоуровневую структуру:

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

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

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

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

19. Основное управление памятью (многозадачность, моделирование многозадачности)