- •Кафедра программного обеспечения информационных технологий
- •«Операционные системы и системное программирование»
- •40 01 01
- •Содержание
- •Введение
- •Разработка программ в ос unix
- •1.1 Отличительные черты ос unix
- •1.2 Основы архитектуры операционной системы unix
- •1.3 Ядро системы
- •1.4 Пользователи системы, атрибуты пользователя
- •1.5 Системные вызовы и функции стандартных библиотек
- •1.6 Описание программы, переменные окружения
- •1.7 Аргументы и опции программы
- •1.8 Обработка ошибок
- •2 Файлы и файловая система
- •2.1 Файлы
- •2.2 Типы файлов
- •2.2.1 Обычные файлы
- •2.2.2 Каталоги
- •2.2.3 Файлы символичной связи (ссылки)
- •2.2.4 Файлы устройства
- •2.2.5 Именованные каналы
- •2.2.6 Сокеты
- •2.3 Владельцы файлов и права доступа к файлу
- •2.4 Дополнительные атрибуты файла
- •2.5 Файловый ввод/вывод
- •Открытие файла
- •2.6 Мультиплексированный ввод/вывод
- •2.7 Векторный ввод/вывод
- •2.8 Файлы, отображающиеся в памяти
- •2.9 Каталоги, работа с каталогами
- •2.9.1 Создание каталога
- •2.9.2 Удаление каталога
- •2.9.3 Чтение информации из каталога
- •2.9.4 Закрытие каталога
- •2.10 Создание жестких ссылок
- •2.11 Символическая ссылка
- •2.12 Удаление ссылки (или имени файла)
- •2.13 Переименование файла
- •2.14 Файловая система ос unix
- •2.14.1 Организация файловой системы ext2
- •2.15 Файлы устройств
- •3 Процессы
- •3.1 Виды процессов
- •3.2 Создание процесса
- •3.3 Вызовы семейства exec
- •3.4 Функции завершения процесса
- •3.5 Ошибки
- •3.6 Копирование при записи
- •3.7 Системные вызовы ожидания завершения процесса
- •3.8 Системный вызов system
- •3.9 Основные параметры, передаваемые процессу
- •3.10 Сеансы и группы процессов
- •4 Взаимодействие процессов
- •4.1 Сигналы
- •4.1.1 Отправка (генерация) сигнала
- •4.1.2 Наборы сигналов
- •4.1.3 Блокировка сигналов
- •4.2 Неименнованные каналы (трубы)
- •4.2.1 Размер канала и взоимодействие процессов при передаче данных
- •4.3 Именнованные каналы
- •4.4 Дополнительные средства межпроцессного взоимодействия
- •4.5 Механизмы межпроцессорного взаимодействия
- •4.5.1 Очереди сообщений
- •4.5.2 Семафоры Семафоры как теоретическая конструкция
- •4.5.3 Разделяемая память
- •4.5.4 Потоки
- •Int pthread_setschedparam(pthread_t tid, int policy, const struct sched_param *param);
- •Int pthread_getschedparam(pthread_t tid, int policy, struct schedparam *param);
- •5 Операционные системы
- •5.1 Понятие операционной системы
- •5.2 Характеристики современных ос
- •5.2.1 Многопоточность
- •5.2.2 Распределенные ос
- •5.2.3 Концепция ос на основе микроядра
- •5.2.4 Функции микроядра.
- •5.3 Принципы построения ос
- •5.4 Концептуальные основы ос
- •5.4.1 Процессы
- •Модель работы процесса с двумя приостановочными состояниями
- •Варианты решения:
- •Решение задачи взаимного исключения. Алгоритм Деккера.
- •Решение задачи взаимного исключения. Алгоритм Пэтерсона..
- •Синхронизирующие примитивы (семафоры).
- •Задача “производитель-потребитель” Общие семафоры
- •Задача “производитель-потребитель”, буфер неограниченного размера(Спящий парикмахер)
- •Задача “производитель-потребитель”, буфер ограниченного размера
- •5.4.2 Распределение ресурсов. Проблема тупиков
- •Алгоритм банкира
- •Применение алгоритма банкира
- •5.4.3 Монитороподобные средства синхронизации
- •Механизм типа «критическая область»
- •5.4.4 Виртуализация
- •5.4.5 Подсистема управления памятью
- •5.4.6 Виртуальная оперативная память
- •5.5 Аппаратные особенности процессоров Intel-архитектуры, направленных на поддержку многозадачности
- •5.5.1 Сегментация памяти. Ia-32
- •5.5.2 Распределение памяти в реальном режиме
- •5.5.3 Организация защиты в процессоре
- •5.5.4 Поддержка многозадачности в процессорах архитектуры ia-32
5.4.2 Распределение ресурсов. Проблема тупиков
Рассматривается логическая задача, которая возникает при взаимодействии различных процессов, когда они должны делить ресурсы.
Под процессами понимаются программы, описывающие некоторый вычислительный процесс, выполняемый ЭВМ. Выполнение такого вычислительного процесса требует времени, в течение которого в памяти ЭВМ хранится информация.
О процессах известно следующее.
1. Их требования к объему памяти не будут превышать определенного предела.
2. Каждый вычислительный процесс завершится при условии, что требуемый процессу объем памяти будет предоставлен в его распоряжение. Завершение вычислительного процесса будет означать, что его требование к памяти уменьшилось до нуля.
Имеющаяся память поделена на страницы фиксированного размера, эквивалентные с точки зрения программы.
Фактическое требование нужного процессу объема памяти является функцией времени, то есть изменяется по мере протекания процесса, но не превышает заранее заданную границу. Отдельные процессы запрашивают и выделяют память единицами в одну страницу. Однажды начатый процесс получает возможность рано или поздно завершиться, и исключается ситуация, когда процесс может быть уничтожен в ходе выполнения, напрасно истратив свои ресурсы.
Если на вычислительной машине выполняется один процесс, или они последовательно следуют один за другим, единственным условием является то, чтобы запрашиваемый процессом объём памяти не превышал доступный объём памяти вычислительной машины. Если параллельно развиваются несколько процессов, то могут возникнуть проблемы с выделением им ресурсов и надо предусмотреть выделение памяти таким образом, чтобы все начатые процессы смогли завершить свое выполнение.
Ситуация, когда какой-либо из процессов может быть завершён лишь при условии уничтожения какого-либо другого процесса, называется «смертельными объятиями» или тупиком.
Рис. 4.1. Тупиковая ситуация
Ситуация, приведенная выше, является тупиковой. Из этой ситуации невозможно выйти без уничтожения какого-либо из процессов.
Решаемая проблема состоит в том, как избежать попадания в тупик, не накладывая слишком больших ограничений.
Алгоритм банкира
Банкир обладает конечным капиталом, например, талерами. Он решает принимать клиентов, которые могут занимать у него талеры на следующих условиях:
1. Клиент делает заем для совершения сделки, которая будет завершена за определенный промежуток времени.
2. Клиент должен указать максимальное количество талеров для этой сделки.
3. Пока заем не превысит заранее установленную потребность, клиент может увеличивать или уменьшать свой заем.
4. Клиент, который просит увеличить свой текущий заем, без недовольства воспринимает ответ о том, что необходимо подождать с получением очередного талера, но через некоторое время талер будет обязательно выдан.
5. Гарантия для клиента, что такой момент наступит, основана на предусмотрительности банкира и на том факте, что остальные клиенты работают по таким же правилам.
Основными вопросами при решении такой задачи являются:
1. При каких условиях банкир может заключить контракт с новым клиентом?
2. При каких условиях банкир может выплатить (следующий) запрашиваемый талер клиенту, не опасаясь попасть в тупик?
Ответ на первый вопрос достаточно прост: банкир может принять любого клиента на обслуживание, чья максимальная потребность не превышает капитал банкира. Ответ на второй вопрос достаточно сложный. Сначала нужно формализовать задачу.
потребность[i] <= капитал, для всех i.
0 <= заем[i] <= потребность[i], для всех i.
требование[i] = потребность[i] - заем[i], для всех i.
наличные = капитал - СУММА_по_i заем[i].
0 <= наличные <= капитал.
В такой ситуации алгоритм принятия решения о том, будет ли безопасной выдача следующего талера выглядит след образом:
integer Св_Деньги; boolean Безопасно;
boolean array Завершение_под_сомнением [1..N];
Св_Деньги := наличные;
for i := 1 step 1 until N do Завершение_под_сомнением[i] := true;
L: for i :=1 step 1 until N do begin
if ( (Завершение_под_сомнением [i]) and
(Требован[i] <= Св_Деньги) ) then begin
Завершение_под_сомнением [i] := false;
Св_Деньги := Cв_Деньги + Заем[i];
goto L;
end;
end;
if (Св_Деньги = капитал) then Безопасно := true
else Безопасно := false;
Проверка возможности выплаты, то есть положение Безопасно, означает, могут ли с гарантией быть завершены все сделки. Алгоритм начинается с проверки, имеет ли, по крайней мере, один клиент требование, не превышающее наличные деньги. Если это так, то этот клиент может завершить свою сделку, и далее исследуются оставшиеся клиенты с учетом того, что первый клиент завершил свою сделку и возвратил свой заём полностью.
Безопасность положения означает, что могут быть закончены все сделки, то есть банкир видит способ получения обратно всех своих денег.
В полном варианте алгоритма банкира эта ситуация должна быть удовлетворена для всех клиентов, принятых на обслуживание и если после завершения цикла, отмеченного меткой L окажется, что капитал банкира полностью восстановлен, то ситуация считается безопасной, в противном случае она определяется как тупиковая и, следовательно, удовлетворять запрос клиента не представляется возможным.
Если более глубоко анализировать эту проблему, то можно показать, что решение о выделении следующего запрашиваемого талера клиенту будет принято тогда, когда хотя бы для одного клиента выполниться условие ((Завершение_под_сомнением[i]) and (Треб[i]<=Св_Деньги)) и это говорит о безопасности ситуации и проверку можно приостановить.