Классические задачи синхронизации процессов

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

Обедающие философы (Рис. 86.). Пускай существует круглый стол, за которым сидит группа философов: они пришли пообщаться и покушать. Кушают они спагетти, которое находится в общей миске, стоящей в центре стола. Для приема пищи они пользуются двумя вилками: одна в левой руке, другая — в правой. Вилки располагаются по одной между каждыми двумя философами. Любой философ может взять обе вилки, покушать, затем положить вилки на стол, после этого вилки может взять его сосед и повторить эти действия. Если мы организуем работу таким образом, что любой философ, желающий поесть, берет сначала левую вилку, затем правую, после чего начинает кушать, то в какой-то момент может возникнуть ситуация тупика (когда каждый возьмет по одной левой вилке, а правая будет захвачена соседом).

86. Содержание

    • Содержание
    • 1 Введение 5
    • 2 Управление процессами 87
    • 3 Реализация межпроцессного взаимодействия в ос Unix 114
    • 4 Файловые системы 152
    • 4.1 Основные концепции 152
    • 5 Управление оперативной памятью 181
    • 6 Управление внешними устройствами 196
    • Введение
    • Пакетная обработка заданий.
    • Развитие языков и систем программирования.
    • Этапы эволюции.
    • Основы архитектуры вычислительной системы
    • Структура вс
    • Структура вычислительной системы.
    • Аппаратный уровень вс
    • Управление физическими ресурсами вс
    • Пример зависимости от драйвера.
    • Управление логическими/виртуальными ресурсами
    • Системы программирования
    • Этапы проектирования.
    • Кодирование.
    • Тестирование.
    • Каскадная модель.
    • Каскадная итерационная модель.
    • Спиральная модель.
    • Прикладные системы
    • Первый этап развития прикладных систем.
    • Второй этап развития прикладных систем.
    • Третий этап развития прикладных систем.
    • Пакет программ Microsoft Office.
    • Пакет MathCad.
    • Система BaaN.
    • Выводы, литература
    • Структура организации вычислительной системы.
    • Основы компьютерной архитектуры
    • Структура, основные компоненты
    • Структура компьютера фон Неймана.
    • Базовая архитектура современных компьютеров.
    • Оперативное запоминающее устройство
    • Ячейка памяти.
    • Контроль четности.
    • Озу без расслоения памяти — один контроллер на все банки.
    • Озу с расслоением памяти — каждый банк обслуживает отдельный контроллер.
    • Центральный процессор
    • Структура организации центрального процессора.
    • Регистровая память
    • Устройство управления. Арифметико-логическое устройство
    • Общая схема работы кэШа.
    • Аппарат прерываний
    • Использование иерархической модели регистров прерывания.
    • Использование вектора прерываний.
    • Этап программной обработки прерываний.
    • Внешние устройства
    • Внешние устройства.
    • Внешние запоминающие устройства
    • Магнитная лента.
    • Принцип устройства магнитного диска.
    • Принцип устройства магнитного барабана.
    • Принцип устройства памяти на магнитных доменах.
    • Модели синхронизации при обмене с внешними устройствами
    • Синхронная и асинхронная работа с ву.
    • Потоки данных. Организация управления внешними устройствами
    • Непосредственное управление центральным процессором внешнего устройства.
    • Синхронное/асинхронное управление внешними устройствами с использованием контроллеров внешних устройств.
    • Использование контроллера прямого доступа к памяти (dma) или процессора (канала) ввода-вывода при обмене.
    • Иерархия памяти
    • Иерархия памяти.
    • Аппаратная поддержка операционной системы и систем программирования
    • Требования к аппаратуре для поддержки мультипрограммного режима
    • Мультипрограммный режим.
    • Проблемы, возникающие при исполнении программ
    • Вложенные обращения к подпрограммам.
    • Перемещаемость программы по озу.
    • Фрагментация памяти.
    • Регистровые окна
    • Регистровые окна.
    • Регистровые окна. Вход и выход из подпрограммы.
    • Системный стек
    • Системный стек.
    • Виртуальная память
    • Страничная организация памяти.
    • Страничная организация памяти. Преобразование виртуального адреса в физический.
    • Страничная организация памяти. Схема преобразования адресов.
    • Многомашинные, многопроцессорные ассоциации
    • Классификация мкмд.
    • Numa-система.
    • Терминальные комплексы (тк)
    • Терминальные комплексы.
    • Компьютерные сети
    • Компьютерные сети.
    • Организация сетевого взаимодействия. Эталонная модель iso/osi
    • Модель организации взаимодействия в сети iso/osi.
    • Логическое взаимодействие сетевых устройств по I-ому протоколу.
    • Семейство протоколов tcp/ip. Соответствие модели iso/osi
    • Семейство протоколов tcp/ip.
    • Взаимодействие между уровнями протоколов tcp/ip.
    • Система адресации протокола ip.
    • Маршрутизация дейтаграмм.
    • Основы архитектуры операционных систем
    • Структура ос
    • Структурная организация ос.
    • Структура ос с монолитным ядром.
    • Структура ос с микроядерной архитектурой.
    • Логические функции ос
    • Типы операционных систем
    • Структура сетевой ос.
    • Структура распределенной ос.
    • Управление процессами
    • Основные концепции
    • Модели операционных систем
    • Типы процессов
    • Типы процессов: однонитевая (а) и многонитевая (б) организации.
    • Контекст процесса
    • Реализация процессов в ос Unix
    • Процесс ос Unix
    • Разделение сегмента кода.
    • Базовые средства управления процессами в ос Unix
    • Пример использования системного вызова fork().
    • Пример использования системного вызова execl().
    • Пример использования схемы fork-exec.
    • Жизненный цикл процесса. Состояния процесса
    • Жизненный цикл процессов.
    • Формирование процессов 0 и 1
    • Формирование нулевого и первого процессов.
    • Инициализация системы.
    • Планирование
    • Взаимодействие процессов
    • Разделяемые ресурсы и синхронизация доступа к ним
    • Гонка процессов.
    • Пример тупиковой ситуации (deadlock).
    • Способы организации взаимного исключения
    • Пример двоичного семафора.
    • Классические задачи синхронизации процессов
    • Обещающие философы.
    • Реализация межпроцессного взаимодействия в ос Unix
    • Базовые средства реализации взаимодействия процессов в ос Unix
    • Способы организации взаимодействия процессов.
    • Сигналы
    • Неименованные каналы
    • Именованные каналы
    • Модель межпроцессного взаимодействия «главный–подчиненный»
    • Общая схема трассировки процессов.
    • Система межпроцессного взаимодействия ipc (Inter-Process Communication)
    • Очередь сообщений ipc
    • Очередь сообщений ipc.
    • 0666 Определяет права доступа */
    • Разделяемая память ipc
    • Массив семафоров ipc
    • Int val; /* значение одного семафора */
    • Сокеты — унифицированный интерфейс программирования распределенных систем
    • Файловые системы
    • Основные концепции
    • Структурная организация файлов
    • Атрибуты файлов
    • Основные правила работы с файлами. Типовые программные интерфейсы
    • Модель одноуровневой файловой системы.
    • Модель двухуровневой файловой системы.
    • Модель иерархической файловой системы.
    • Подходы в практической реализации файловой системы
    • Структура «системного» диска.
    • Модели реализации файлов
    • Модель непрерывных файлов.
    • Модель файлов, имеющих организацию связанного списка.
    • Модели реализации каталогов
    • Модели организации каталогов.
    • Соответствие имени файла и его содержимого
    • Пример жесткой связи.
    • Пример символической связи.
    • Координация использования пространства внешней памяти
    • Квотирование пространства файловой системы
    • Квотирование пространства файловой системы.
    • Надежность файловой системы
    • Проверка целостности файловой системы
    • Проверка целостности файловой системы. Непротиворечивость файловой системы соблюдена.
    • Проверка целостности файловой системы. Зафиксирована пропажа блока.
    • Проверка целостности файловой системы. Зафиксировано дублирование свободного блока.
    • Проверка целостности файловой системы. Зафиксировано дублирование занятого блока.
    • Проверка целостности файловой системы. Контроль жестких связей.
    • Примеры реализаций файловых систем
    • Организация файловой системы ос Unix. Виды файлов. Права доступа
    • Логическая структура каталогов
    • Логическая структура каталогов.
    • Внутренняя организация файловой системы: модель версии System V
    • Структура файловой системы версии System V.
    • Работа с массивами номеров свободных блоков
    • Работа с массивами номеров свободных блоков.
    • Работа с массивом свободных индексных дескрипторов
    • Индексные дескрипторы. Адресация блоков файла
    • Индексные дескрипторы.
    • Адресация блоков файла.
    • Файл-каталог
    • Файл-каталог.
    • Установление связей.
    • Достоинства и недостатки файловой системы модели System V
    • Внутренняя организация файловой системы: модель версии Fast File System (ffs) bsd
    • Структура файловой системы версии ffs bsd.
    • Стратегии размещения
    • Стратегия размещения последовательных блоков файлов.
    • Внутренняя организация блоков
    • Внутренняя организация блоков (блоки выровнены по кратности).
    • Выделение пространства для файла
    • Выделение пространства для файла.
    • Структура каталога ffs
    • Структура каталога ffs bsd.
    • Блокировка доступа к содержимому файла
    • Управление оперативной памятью
    • Одиночное непрерывное распределение
    • Одиночное непрерывное распределение.
    • Распределение неперемещаемыми разделами
    • Распределение неперемещаемыми разделами.
    • Распределение перемещаемыми разделами
    • Распределение перемещаемыми разделами.
    • Страничное распределение
    • Страничное распределение.
    • Иерархическая организация таблицы страниц.
    • Использование хеш-таблиц.
    • Инвертированные таблицы страниц.
    • Замещение страниц. Алгоритм «Часы».
    • Сегментное распределение
    • Сегментное распределение.
    • Сегментно-страничное распределение
    • Сегментно-страничное распределение. Упрощенная модель Intel.
    • Управление внешними устройствами
    • Общие концепции
    • Архитектура организации управления внешними устройствами
    • Модели управления внешними устройствами: непосредственное (а), синхронное/асинхронное (б), с использованием контроллера прямого доступа или процессора (канала) ввода-вывода.
    • Программное управление внешними устройствами
    • Иерархия архитектуры программного управления внешними устройствами.
    • Планирование дисковых обменов
    • Планирование дисковых обменов. Модель fifo.
    • Планирование дисковых обменов. Модель lifo.
    • Планирование дисковых обменов. Модель sstf.
    • Raid 2. Избыточность с кодами Хэмминга (Hamming, исправляет одинарные и выявляет двойные ошибки).
    • Raid 3. Четность с чередующимися битами.
    • Raid 5. Распределенная четность (циклическое распределение четности).
    • Работа с внешними устройствами в ос Unix
    • Файлы устройств, драйверы
    • Системные таблицы драйверов устройств
    • Ситуации, вызывающие обращение к функциям драйвера
    • Включение, удаление драйверов из системы
    • Организация обмена данными с файлами
    • Организация обмена данными с файлами.
    • Буферизация при блок-ориентированном обмене
    • Борьба со сбоями