СПО экзамен. СПО. Тупиковые ситуации. Методы борьбы с тупиками игнорирование тупиков
 Скачать 69.23 Kb.
|
|
Тупиковые ситуации. Методы борьбы с тупиками: игнорирование тупиков Методы борьбы с тупиками: предотвращение тупиков Методы борьбы с тупиками: алгоритм банкира Методы борьбы с тупиками: нарушение условий возникновения тупиков Методы борьбы с тупиками: обнаружение тупиков Методы борьбы с тупиками: восстановление после тупиков Физические принципы организации ввода-вывода. Классификация устройств ввода-вывода. Контроллеры устройств ввода-вывода. Прямой доступ к памяти (DMA) Логические принципы ввода-вывода. Структура системы ввода-вывода. Драйверы устройств ввода-вывода. Структура системы ввода-вывода. Функции базовой подсистемы ввода-вывода. Файлы. Имена и атрибуты файлов. Варианты организации файлов. Директории. Структура файловой системы. Методы выделения дискового пространства: выделение непрерывной последовательностью блоков Методы выделения дискового пространства: связный список Методы выделения дискового пространства: таблица отображения файлов Методы выделения дискового пространства: индексные узлы. Учет свободного места. Монтирование файловых систем. Многопроцессорные системы. Суперкомпьютеры. Способы организации ОС мультипроцессоров. Сетевые и распределенные ОС. 1. Тупиковые ситуации. Тупик – это ситуация, при которой два или более процессов находятся в состоянии блокировки в ожидании событий, которых никогда не произойдет. При взаимоблокировке каждый из процессов обладает одним или несколькими ресурсами необходимыми другим процессам. Условия возникновения тупиков: Условие взаимоисключения. Тупики могут возникнуть, если используются выделенные ресурсы (т.е. неразделяемые), т.е. ресурсы к которым не может иметь доступа более 1 процесса. Условие ожидания ресурсов. Процессы должны ожидать ресурсы, которые им необходимы, но заняты. Условие неперераспределяемости ресурсов. Ресурсы не могут быть забраны у процессов для выделения их другим процессам принудительно. Ресурсы могут освобождаться только самими процессами. Условие кругового ожидания. Существует кольцевая цепь процессов в которой каждый процесс ждет доступа к ресурсу удерживаемому другим процессов цепи. Необходимо и достаточно для возникновения тупиков выполнение всех четырех условий. 2. Методы борьбы с тупиками: игнорирование тупиков В системах общего назначения тупики могут возникать редко, в маловероятных ситуациях. Значительно дороже, чем ущерб от тупика, реализовывать сложные алгоритмы предотвращения тупиков, накладывать ограничения на работу процессов и пользователей, снижая производительность системы в целом. Поэтому возможные маловероятные тупики игнорируются. 3. Методы борьбы с тупиками: предотвращение тупиков Подсистема распределения ресурсов, предотвращающая тупик, должна гарантировать, что ни одного из четырех условий, необходимых для его наступления, не возникнет. Условие взаимоисключения. Тупики могут возникнуть, если используются выделенные ресурсы (т.е. неразделяемые), т.е. ресурсы к которым не может иметь доступа более 1 процесса. Условие ожидания ресурсов. Процессы должны ожидать ресурсы, которые им необходимы, но заняты. Условие неперераспределяемости ресурсов. Ресурсы не могут быть забраны у процессов для выделения их другим процессам принудительно. Ресурсы могут освобождаться только самими процессами. Условие кругового ожидания. Существует кольцевая цепь процессов в которой каждый процесс ждет доступа к ресурсу удерживаемому другим процессов цепи. 4. Методы борьбы с тупиками: алгоритм банкира Состояние системы можно считать надежным, если система способна удовлетворить все запросы процессов в течение конечного времени. Процесс запрашивает ресурсы у системы. Система оценивает наличие запрошенных ресурсов и сколько ресурсов останется после удовлетворения запросов. Процесс гарантирует, что в случае выделения ему запрошенных ресурсов они будут возвращены системе в конечное время. Система выделяет процессу ресурсы, если останется после этого в надежном состоянии. Недостатки алгоритма: 1) алгоритм может быть реализован только, если в системе фиксированное количество процессов, ресурсов и пользователей. 2) На систему накладываются ограничения не совместимые с обычной работой системы. 5. Методы борьбы с тупиками: нарушение условий возникновения тупиков Нарушение условия взаимоисключения. Выделенные ресурсы необходимо преобразовать в разделяемые, например, используя спулинг. Недостаток: не все ресурсы могут быть разделяемые. Нарушение условия ожидания ресурсов. Процессы не должны иметь возможности запрашивать новые ресурсы удерживая предыдущие, если какие-то из запрошенных ресурсов для них недоступны. Двухфазный захват ресурсов: Процесс запрашивает все необходимые ресурсы Если хоть 1 из ресурсов недоступен, то все выделенные процессу ресурсы освобождаются и возврат к фазе 1. Недостаток: не всегда известно наперед какие ресурсы процессу потребуются. Нарушение условия неперераспределенности. ОС должна иметь возможность принудительно передать ресурс от одного процесса к другому. Недостатки: не существует четких методов определения, что процесс сделал с ресурсом, как с ним продолжать взаимодействовать, поэтому принудительные действия системы по отбору ресурса чреваты потерей данных и работоспособности процесса. Нарушение условия кругового ожидания. Для нарушения условия необходимо обеспечить очередность запросов к ресурсам, например, в порядке возрастания номеров ресурсов. В таком случае кольцевой цепи не возникает. Недостаток: после запроса к ресурсам с более высокими номерами нельзя обратиться к ресурсам с меньшим номером. 6. Методы борьбы с тупиками: обнаружение тупиков В системе могут быть реализованы алгоритмы поиска колец на направленных графов процессов-ресурсов. Недостаток: сложность реализации и снижение производительности. 7. Методы борьбы с тупиками: восстановление после тупиков Если тупик обнаружен, то кольцевая цепь процессов должна быть разорвана. Для этого необходимо завершение одного или нескольких процессов или перераспределение ресурсов. Недостаток: невозможно корректно перезапустить любой выбранный процесс продолжив его с той же команды. 8. Физические принципы организации ввода-вывода. Устройства вычислительной системы связаны электрическими соединениями, называемые линиями. Линии, предназначенные для выполнения одинаковых действий объединяются в шины. Шины формируют локальную магистраль. Шина адреса предназначена для указания номера ячейки памяти или порта I/O. Шина данных предназначена для передачи данных между устройствами. Шина управления предназначена для передачи управляющих воздействий от ЦП к устройству. Разрядность шины – количество линий входящих в нее. 9. Классификация устройств ввода-вывода. 1) Устройства ввода. 2) Устройства вывода. 3) Устройства ввода-вывода. 4) Устройства символьные – осуществляют последовательный побайтовый ввод-вывод (модем). 5) Устройства блочные – осуществляют I/O блоками байт. 6) Устройства монопольные – могут одновременно использоваться только одним процессом. 7) Устройства разделяемые - могут одновременно использоваться несколькими процессами. 8) Сетевые устройства. 9) Локальные устройства. 10. Контроллеры устройств ввода-вывода. Контроллер – это устройство взаимодействующее с вычислительной системой по стандартным интерфейсам и управляющее устройствами ввода-вывода. 11. Прямой доступ к памяти (DMA) DMA – механизм, позволяющий передавать данные между памятью и устройствами I/O напрямую без участия ЦП. Алгоритм передачи данных из устройств I/O в ОЗУ: Устройства I/O подключаются к DMA линиями, называемыми каналы DMA. DMA устанавливает на шину данных значение, которое необходимо записать. На шину адреса устанавливается номер порта ОЗУ. На шину управления устанавливается значение запись в ОЗУ. Контроллер ОЗУ, порт которого установлен на шине адреса, читает значение с шины данных и инициирует его запись в ОЗУ. Контроллер – это устройство, взаимодействующее с вычислительной системой по стандартным интерфейсам, и управляющее устройствами I/O. 12. Логические принципы ввода-вывода.  13. Структура системы ввода-вывода. Драйверы устройств ввода-вывода. Драйвер – программная часть ОС разработанная производителем устройства, предназначенная для логического сопряжения устройства с программными интерфейсами ОС. Драйвер программно управляет контроллером устройства. 14. Структура системы ввода-вывода. Функции базовой подсистемы ввода-вывода. BIOS – подсистема ОС отвечающая за взаимодействие с драйверами, обработку ошибок I/O; организацию spooling’a (формирование очередей I/O); буферизацию и кэширование. 15. Файлы. Имена и атрибуты файлов. Файл - блок информации на внешнем запоминающем устройстве имеющий определённое логическое представление, соответствующие ему операции чтения-записи и фиксированное имя, позволяющее получить доступ к этому файлу. В большинстве файловых систем имя файла используется для указания, к какому именно файлу производится обращение. В различных файловых системах ограничения на имя файла сильно различаются: в FAT16 и FAT12 размер имени файла ограничен 8.3 знаками (8 на имя и 3 на расширение); в других системах имя файла ограничено обычно в 255 байт; в NTFS имя ограничено в некоторых ОС 255 символами юникод. В некоторых файловых системах, таких как NTFS, предусмотрены атрибуты (обычно это бинарное значение «да»/«нет», кодируемое одним битом). Примеры атрибутов: только для чтения, системный, скрыты, архивный. 16. Варианты организации файлов. 1) Неструктурированная последовательность блоков и в общем случае байт. файлы последовательного доступа файлы прямого доступа 2) Последовательность записей фиксированного размера. 3) Записи переменного размера. Поскольку записи различного размера, то невозможно рассчитать адрес начала определенной записи и для доступа к ней необходимо прочитать все предыдущие записи, поэтому файл записи переменного размера в чистом виде не является файлом прямого доступа. 4) Индексно-последовательные файлы – файл с записями переменного размера, каждая из которых сопровождается ключевым полем по которому можно однозначно идентифицировать запись. При необходимости получить прямой доступ к конкретным записям, файл сопровождается дополнительной управляющей структурой – индексом, который отсортирован по ключевым полям и содержит указатели на записи. Типы файлов: регулярные файлы директории или каталоги 17. Директории. Директория – это особый тип файлов, содержащий список других файлов. В зависимости от ФС в директории по каждому файлу могут храниться: имя, атрибуты, права доступа, номер первого блока или номер индексного узла, размер файла и прочая информация. 18. Структура файловой системы. 1) Суперблок – это первый блок ФС, содержащий тип ФС, размер блока данных, количество блоков данных, размер массива индексных узлов. 2) Структуры, описывающие свободное место. 3) Массив индексных узлов. 19. Методы выделения дискового пространства: выделение непрерывной последовательностью блоков Метод используется в стационарных ФС, где файлы не изменяются. Каждому файлу выделяется последовательный набор блоков. Достоинства: поскольку файл находится в одном месте, то для доступа к нему необходимо минимум передвижений по диску. Недостатки: 1) После удаления файлов возникает фрагментация. 2) Файл ограничен в размере с соседними файлами, а поскольку заранее размер файла известен не всегда, то это накладывает большие ограничения на алгоритмы работы с файлами. 3) Необходим выбор стратегии размещения файлов. 20. Методы выделения дискового пространства: связный список В директории хранится номер первого блока файла. Каждый блок на ряду с данными содержит указатель на следующий блок этого файла. Последний блок файла вместо указателя содержит символ конца файла. Достоинства: файл не ограничен по размеру другими файлами, поскольку его блоки могут располагаться в любых местах диска и в любом порядке. Недостатки: 1) В каждом блоке необходимо выделить несколько байт для указателя на следующий блок, что создает неудобство обработки данных блока. При сбое в одном блоке теряется вся следующая за них цепочка блоков файлов. 2) Файл является файлом последовательного доступа, поскольку для доступа к конкретному блоку необходимо прочитать все предыдущие блоки файлов. 21. Методы выделения дискового пространства: таблица отображения файлов FAT – File Allocation Table. Список блоков каждого файла выносится в отдельную управляющую структуру FAT. Она представляет собой массив, каждая ячейка которого соответствует одному блоку диска. В директории записан номер первого блока файла, ссылки на последующие блоки читаются из таблицы размещения файлов. Каждая ячейка FAT содержит указатель на следующий блок файлов. Ячейка FAT соответствующая последнему блоку файла содержит символ конца файла. Достоинства: 1) Файл организованный связным списком блоков, является файлом прямого доступа к конкретному блоку, нужно только прочитать FAT и по значениям его ячейки определить нужный номер блока. 2) Указатели не занимают место в блоках данных, а вынесены в отдельную структуру. 3) При сбое одного блока теряется только его содержимое. 4) В FAT можно отметить плохие и свободные блоки, по ней можно восстановить цепочки файлов даже при отсутствии записей в директориях. Недостатки: 1) FAT является узким местом в системе, поскольку при уничтожении таблицы, будут потеряны данные всех файлов, поскольку FAT всегда дублируется. 2) FAT имеет фиксированный максимальный размер, следовательно может описать фиксированное максимальное количество блоков. Из-за этого необходимо добавлять дополнительные FAT в пространстве блоков данных. По FAT можно определить блоки выделенные файлу, но с точностью до байта размер файла определяется только записью в директорию. В FAT32 выделено 32 бита, следовательно размер файла не более 232 байт. 22. Методы выделения дискового пространства: индексные узлы. Индексный узел – это управляющая структура ФС описывающая 1 файл. Адресуется номером в массиве индексных узлов. Каждый индексный узел содержит права доступа и атрибуты файла, время создания и модифицирования и прочую информацию о файле, а также список блоков данных файла. Если файл большой, то список блоков может разделяться на несколько частей. В таком случае первые блоки данных файла перечисляются в самом индексном узле, после чего в индексном узле находятся номера блоков косвенной адресации, т.е. блоков данных файла. В блоках второго уровня могут быть ссылки на блоки третьего уровня, и т.д. Достоинства: 1) Нет ограничений на размер файла. 2) Простота организации ссылок на файлы. 3) Для доступа ко всем блокам данных файла достаточно прочитать его индексный узел. 4) Сбой в блоке с индексным узлом приведет к потере максимум 1 файла. 23. Учет свободного места. Свободное место может описываться следующим образом: 1) Битовый вектор: каждому блоку данных соответствует 1 бит, который установлен или не установлен в зависимости от того, занят или свободен этот блок. Современные архитектуры содержат команды битовой арифметики, благодаря чему подсчет свободного места по битовому вектору является тривиальной задачей. Недостаток: несмотря на то, что каждому блоку соответствует всего 1 бит, размер битового вектора очень велик. 2) Связный список. Каждый свободный блок содержит указатель на следующий свободный блок. Поскольку в блоках нет данных, то хранение указателя никак не мешает данным. Достоинства: чаще всего необходим только первый блок. Указатель на него и на следующий за ним доступны. Недостаток: для получения общего количества свободных блоков необходимо пройти по всему списку. При сбое одного из свободных блоков теряется все оставшееся за ним свободное место. Модификация списка позволяет ссылаться на каждый свободный блок, а не на первый из группы свободных блоков следующих последовательно. Благодаря этому получить общее число свободных блоков можно быстрее. 3) Таблица отображения файлов. Незанятая ячейка таблицы означает свободный блок данных. 4) Учет свободного места одним индексным узлом. Все свободные блоки данных объединены в 1 файл с индексным узлом, который учитывает свой размер стандартными средствами. ФС может содержать очень большое количество файлов, из-за чего массив индексных узлов может продолжаться в нескольких местах в разделах блоков данных. Блоки косвенной адресации также размещаются в разделе блоков данных. 24. Монтирование файловых систем. Монтирование – это процесс соотнесения корневого или любого другого каталога устройства хранения данных со своей ФС и каталога другой ФС. Благодаря монтированию в единую файловую иерархию могут объединятся файловые иерархии из различных ФС и с различных устройств хранения данных, локальных и удаленных вычислительных систем. При обходе директории при чтении точки монтирования, т.е. директории в которой смонтирована другая ФС, система читает суперблок другой ФС, определяет ее тип, и в зависимости от него продолжает обход директорий специфическими для нее операциями. ФС может быть размонтирована, т.е. соответствие ее и каталога другой ФС удалено. Монтирование может производиться вручную или автоматически, может описываться в специальных конфигурационных файлах. 25. Многопроцессорные системы. Классы: 1) Мультипроцессоры (суперкомпьютеры) Включают в себя большое количество ЦП, общую память и общую периферию. Располагаются локализовано, администрируется и управляется централизованно. 2) Мультикомпьютеры (кластеры) Представляют собой совокупность систем, каждая из которых включает в себя один или несколько ЦП, память, и, возможно некоторую периферию. Располагается, администрируется и управляется централизованно. 3)Распределенные системы. Представляют собой совокупность полностью независимых вычислительных систем с полным набором оборудования не локализованных географически, администрируются и управляются децентрализованно, объединяются глобальной или локальной сетью. ОС в мультироцессорах и мультикомпьютерах одна общая в рамках системы. В распределенных каждый работает со своей ОС. 26. Суперкомпьютеры. Суперкомпьютер – это вычислительная система стоимостью не ниже 1 миллиона долларов. Суперкомпьютер – это вычислительная система, производительность которой лишь на порядок ниже, чем необходимо для решения современных передовых задач. 27. Способы организации ОС мультипроцессоров. 1) Каждому ЦП своя ОС. Каждый процессор выполняет свой экземпляр ядра ОС. Код ОС записан в памяти и не дублируется. Память разбита на участки для каждого процесса. Каждый процессор выполняет пользовательские процессы и обслуживает их системные вызовы. +: простота организации. _: невозможность балансировки нагрузки между ЦП; невозможно распределение страниц памяти между различными процессорами, из-за чего один может быть перегружен, а другой простаивать, 1 участок памяти в постоянном свопинге, другой пустовать. Мультипроцессорная архитектура превращается в мультикомпьютерную теряя свои свойства. 2) Хозяин-подчиненный. Ядро ОС выполняется на одном процессоре (хозяине), остальные выполняют прикладные процессы. Хозяин может по своему усмотрению распределять прикладные процессы любым образом, управлять работой других ЦП. На хозяине выполняются все системные вызовы всех процессоров. -: при большом потоке системных вызовов хозяин является узким местом системы, т.к. при задержке обработки системных вызовов начинают простаивать прикладные процессы. 3) SMP (симметричные мультипроцессоры) Все ЦП играют единую роль – выполняют прикладные процессы, и при системных вызовах код ядра. +: как угодно балансируется нагрузка между процессорами. -: один и тот же код ядра может одновременно выполняться на нескольких процессорах, что может привести к порче данных и нарушению работоспособности всей системы. Решение: код ядра объявляется критической секцией, ей ставится в соответствие MUTEX, организовывая взаимоисключение. В результате только один процесс в конкретный момент времени может выполнять код ядра. -: снижение производительности, т.к. функционально не связанные системные вызовы не могут одновременно обрабатываться на различных ЦП. Решение: код ядра должен быть разбит на функционально независимые части, каждая из которых объявляется в критической секции и получает MUTEX. +: одновременно на нескольких процессорах могут обрабатываться системные вызовы из различных функциональных частей ядра. -: сложность разбиения кода ядра на критические секции, но для мультипроцессоров это необходимо. 28. Сетевые и распределенные ОС. Сетевые ОС это: ОС предназначенные для работы в составе сети. Совокупность ОС компьютеров сети. Сетевые ОС делятся на категории: Одноранговые – системы не играющие определенной клиентской или серверной роли, используют клиентские ОС. Клиент или сервер. Серверная ОС отличается от клиентской: Наличие комплекса административных средств. Отсутствие продвинутых мультимедиа возможностей. Возможность поддержки большого количества одновременных соединений. Распределенные ОС – это сетевые ОС, которые объединяют несколько вычислительных систем, формируют виртуальную машину, в которой данные и процессы пользователя могут располагаться и выполняться на любой системе прозрачной для пользователя. Основные команды Создание и удаление каталогов: mkdir и rmdir $ mkdir /home/chris/letters $ rmdir /home/chris/letters Просмотр содержимого каталогов: ls $ ls /home/chris/reports Переход в другой каталог: команда cd $ cd имя_каталога Для определения рабочего каталога: команда pwd Диалоговое руководство: man (позволяет пользователю получить информацию о любой команде и программе в ОС Linux) $ man ls Команда whatis обеспечивают поиск в базе данных заголовков man-страниц и выдают все найденные заголовки с кратким описанием каждого. Например, если вы хотите увидеть все пункты руководства, в которых есть отдельно стоящая буква х, необходимо дать следующую команду: $ whatis х Команда apropos выполняет ту же задачу, что и команда whatis но поиск выполняется по образцу, а не по целым словам. Скажем, команда apropos x выдаст несколько страниц с данными, в которых будут перечислены все пункты руководства, начинающиеся с буквы x $ apropos ls Отображение файлов: cat и more Команда cat выводит на экран сразу весь текст файла. More позволяет выводить текст на экран порциями. $ cat mydata $ more mydata Печать файлов: команды lpr, lpq и lprm $ lpr mydata печатать несколько файлов: $ lpr mydata preface Поиск в каталогах: команда find $ find список каталогов -опция критерии Копирование файлов $ ср исходный файл выходной файл $ ср -i newprop proposal (-i спросит о перезаписи если файл с таким именем уже существует) Копирование файлов в каталоги $ ср имена_файлов имя_каталога $ ср *. с sourcebks (копирование всех файлов с расширением *.c) $ ср props/*.* oldprop (копирование всех файлов из каталога props в каталог oldprop) $ ср имя_файла имя_каталога/новое_имя файла (при копировании дать копии имя, отличное от имени оригинала) Перемещение и переименование файлов $ mv имя_файла имя_каталога $ mv reports/*.* repbks (переместить все файлы из данного каталога в другой каталог) $ mv текущее имя_файла новое_имя_файла Перемещение и копирование каталогов $ ср -r letters/thankyou oldletters (каталог thankyou копируется в каталог oldletters) $ ср letters/* oldletters (все файлы из каталога letters копируются в каталог oldletters) Удаление файла: команда rm $ rm proposal version1 version2 (-i чтобы спрашивалось разрешение на удаление) Получить подробную информацию о файле: команда ls –l $ ls -l today Посмотреть права каталога: ls –ld Присваиваение файлу дополнительных имен: команда ln (жесткая ссылка) $ ln исходное_имя_файла дополнительное_имя_файла Создать символическую ссылку: $ ln –s $ ln -s /home/george/veglist lunch |