Читайте также:
|
Методы распределения памяти:
1. Без использования дискового пространства:
1.1. Фиксированные разделы – самый простой способ; так как в каждом разделе может выполняться только одна программа, то уровень мультипрограммирования заранее ограничен числом разделов, независимо от того, какой размер имеют программ – даже если программа имеет маленький объем, она будет занимать весь раздел, что приводит к неэффективному использованию памяти.
1.2. Динамические разделы – разделы не делятся заранее, сначала вся память свободна, каждой вновь поступающей задаче выделяется необходимая память, если недостаточно, то задача остается в очереди. После завершения память освобождается и на ее место может быть загружена другая задача. Т.о. в произвольный момент времени ОП представляет собой случайную последовательность блоков произвольного размера. По сравнению с методом 1.1., данный метод обладает большей гибкостью, но ему присуща фрагментация (наличие большого числа несмежных участков памяти очень маленького размера).
1.3. Перемещаемые разделы. Один из методов борьбы с фрагментацией – перемещение фрагментов в сторону старших или младших адресов, так чтобы образовывалась единая свободная область. Это называется сжатие, может выполняться при каждом завершении задачи (требуется меньше вычислительной работы) или только тогда, когда для вновь поступившей задачи нет свободного раздела достаточного размера (реже выполняется). Хотя сжатие приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто перевешивает преимущества данного метода.
2. С использованием дискового пространства:
2.1. Страничное распределение;
2.2. Сегментное;
2.3. Сегментно-страничное.
Лекция 8 (01.11.2012)
Файловая система – часть ОС, назначение которой в том, чтобы обеспечивать удобный интерфейс при работе с данными, хранящимися на диске и обеспечить совместное использование файлов несколькими пользователями и процессами. В широком смысле понятие ФС включает:
1. Совокупность всех фалов на диске;
2. Наборы структур данных, используемых для управления файлами;
3. Комплекс системных программных средств, реализующих управление файлами.
Файлы идентифицируются именами, длина которых зависит от типа ФС.
Файлы бывают 3х типов: обычные, специальные, каталоги.
Обычные делятся на текстовые и двоичные. Специальные файлы – файлы, ассоциированные с устройствами ввода-вывода, которые позволяют пользователю выполнять операции ввода-вывода, использую обычные команды записи в файл и чтения из файла. Эти команды обрабатываются в начале программами ФС, а затем преобразуются ОС в команды управления соответствующими устройствами.
Специальные команды, также как устройства ввода-вывода, делятся на байт-ориентированные и блок-ориентированные.
Каталог – это с одной стороны группа файлов, объединенных пользователем по какому-то признаку, а с другой стороны это файл, содержащий системную информацию о группе файлов, его содержащую.
Логическая организация ФС бывает одноуровневая, иерархическая (дерево) и иерархическая (сеть).
Физическая организация и анализ файла. Физическая организация файла описывает правила расположения файла на устройстве внешней памяти, в частности на диске. Файл состоит из физических записей – блоков. Блок – наименьшая единица данных, которой внешнее устройство обменивается с ОП.
Непрерывное размещение – простейший вариант физической организации, при котором файлу предоставляется последовательность блоков диска, образующих единый сплошной участок памяти. Для задания адреса файла в этом случае достаточно указать номер блока. Достоинство: простота. Недостатки: неизвестно, сколько резервировать под файл, неизбежно возникает фрагментация и пространство используется не эффективно.
Связанный список блоков. При таком способе в начале каждого блока содержится указатель на следующий блок. Адрес также задается номером первого блока. В отличи от предыдущего способа, каждый блок может быть присоединен в цепочку какого-либо файла, следовательно, фрагментация отсутствует. Файл может изменяться во время своего существования, наращивая число блоков. Недостаток – сложность реализации доступа к произвольно заданному места в файле. Для того, чтобы прочитать пятый по порядку блок файла, необходимо последовательно прочитать первые четыре, прослеживая цепочку номеров блоков. Кроме того, при таком способе количество данных файла, содержащихся в одном блоке, не равно степени двойки, а многие программы читают данные блоками, размер которых кратен степени двойки.
Связанный список индексов используется, в основном в FAT. С каждым блоком связывается некий элемент «индекс». При такой физической организации сохраняются все достоинства предыдущего способа и снимаются оба недостатка.
Простое перечисление номеров блоков, занимаемых файлом. Рассмотрим юникс, для хранения файла выделено 13 полей, если размер файла меньше или равен 10 блокам, то номера этих блоках непосредственно перечислены в первых десяти полях адреса. Если размер файла больше 10 блоков, то следующее 11 поле содержит номер блока, в котором может быть расположено еще 128 номеров блоков. Если размер еще больше, то используется 12 поле, в котором находится номер блока, содержащего 128 номеров блоков, которые содержат по 128 номеров блоков данного файла.
Права доступа к файлу. Определить права доступа, значит определить для каждого пользователя набор операций, которые он может применить к данному файлу. В разных ОС может быть свой список дифференцируемых операций доступа. В самом общем случае права доступа могут быть описаны матрицей прав доступа, в которой столбцы соответствуют всем файлам системы, а строки всем пользователям и на пересечении всех строк и столбцов указываются разрешенные операции. В некоторых системах пользователи могут быть разделены на отдельные категории. Для всех пользователей одной категории определяются единые права доступа. В юникс владелец, группа и все остальные. Различают 2 основных подхода к определению прав доступа:
1. Избирательный доступ, когда для каждого файла и каждого пользователя сам владелец может определить допустимые операции;
2. Мандатный подход, когда система наделяет пользователя определенными правами по отношению к каждому разделяемому ресурсу, в зависимости от того, к какой группе пользователей отнесен.
Программные алгоритмы организации взаимодействия процессов
Требования к алгоритмам:
1. Задача должна быть решена чисто программным способом на обычной машине, не имеющей специальных команд взаимоисключения. При этом предполагается, что основные инструкции языка программирования являются атомарными.
2. Не должно существовать никаких предположений в относительных скоростях выполняющихся процессов или числе процессоров, на которых они выполняются.
3. Если процесс Pi исполняется в своем критическом участке, то не существует никаких других процессов, исполняющихся в соответствующих критических секциях.
4. Процессы, которые находятся вне своих критических секций и не собираются входить в них, не могут препятствовать другим процессам входить в их собственные критические участки.
5. Не должно возникать неограниченно долгого ожидания для входа одного из процессов в свой критический участок.
Методы решения:
1. Запрет прерываний:
While (some condition) {
Запрет прерыв
Critical section
Разреш прерыв
Remainder section
}
Поскольку выход процесса из состояния исполнения без его завершения исполняется по прерыванию, внутри критической секции никто не может вмешаться в его работу. Однако, такое решение может иметь далеко идущие последствия, поскольку позволяет процессу пользователя разрешать и запрещать прерывания во всей ВС.
Допустим, что пользователь случайно запретил прерывания и завис: без перезагрузки системы в такой ситуации не обойтись. Тем не менее запрет и разрешения прерываний часто применяются как пролог и эпилог критических секций внутри самой ОС.
2. Переменная-замок:
Возьмем переменную, доступную всем процессам, с начальным значением 0. Процесс может войти в критическую секцию только тогда, когда значение этой переменной равно 0, одновременно изменяя ее значение на 1, тем самым закрывая замок. При выходе из критической секции процесс сбрасывает переменную в 0.
Shared int lock = 0;
While (some condition) {
While (lock); lock=1;
Critical section
Lock=0;
Remainder section
}
Допустим процесс П0 протестировал значение lock и принял решение двигаться дальше. В этот момент, еще до присвоения lock=1, планировщик передал управление П1. Он тоже проверил содержимое переменной lock, увидел, что она равна 0 и тоже принял решение войти в критическую секцию. Получено одновременно 2 процесса, выполняющие свои критические секции.
3. Строгое чередование:
Также будет общая переменная, только она будет играть не роль замка, а явно указывать, кто может следующим войти в него. Для i-го процесса алгоритм выглядит так:
Shared int turn = 0;
While (some condition) {
While (turn!=0);
Critical section
Turn = 1-0;
Remainder section
}
Очевидно, что взаимоисключение гарантируется, процессы входят в секцию строго по очереди, но наш алгоритм не удовлетворяет условию прогресса. Например, если значение переменной равно 1 и процесс П0 готов войти в крит участок, он не сможет сделать этого, даже если процесс П1 находится в remainder section.
4. Флаги готовности:
Недостатком пред алгоритма является то, что процессы ничего не знают о состоянии друг друга в текущий момент времени.
Shared int ready[2]={0,0};
While (sm cond) {
Ready[i]=1;
While (ready[1-i]);
Cs
Ready[i]=0;
Rs
}
Когда итый процесс готов войти в критическую секцию, он присваивает элементам массива куди итому значение 1-и; после выхода из крит секции он сбрасывает его в 0. Процесс не входит в критическую секцию, если другой процесс уже готов ко входу в крит секцию или уже в ней. Полученный алгоритм обеспечивает взаимоисключение, позволяет процессу, готовому ко входу в критический участок, войти в него сразу после эпилога в другом процессе, но все-равно нарушает условие прогресса.
Пусть процессы практически одновременно подошли к выполнению пролога. После выполнения присваивания реди 0 = 1, планировщик передал процессор от процесса 0 процессу 1, который также выполнил присваивания реди1 = 1. После этого оба процесса бесконечно ждут друг друга на входе в критическую секцию, возникает тупик.
5. Алгоритм Петерсона:
Пусть оба процесса имеют доступ к массиву флагов процессора и к переменной очередности.
Shared int ready[2]={0,0};
Shared in turn;
While (some condition) {
Ready[i]=1;
Turn = 1-I;
While (ready[1-i] && turn = 1-i)
Cs
Read[i]=0;
Rs
}
При исполнении пролога критической секции процесс Пи заявляет о готовности вступить в крит участок и одновременно предлагает другому процессу приступить к его выполнению. Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу. При этом одно из предложений всегда следует после другого. Тем самым работу в крит участке продолжит процесс, которому было сделано последнее предложение. Данный алгоритм удовлетворяет всем требованиям.
Дата добавления: 2014-12-19; просмотров: 91 | Поможем написать вашу работу | Нарушение авторских прав |