14

Билет 14

1. Процессы: взаимодействие процессов в распределенных системах; централизованный и распределенный алгоритмы, синхронизация часов (алгоритм Лампорта); RPC – механизм

2. Аппаратные прерывания: типы аппаратных прерываний; особенности. Прерывания от устройств ввода-вывода: назначение и аппаратная реализация. Прерывание от системного таймера в защищенном режиме. Пример кода обработчика прерывания от системного таймера из лабораторной работы по защищенному режиму

Вопрос 1.

Процессы: взаимодействие процессов в распределенных системах

В распределенных системах, называющихся так, потому что ресурсы рассредоточены, процессы не имеют общей памяти (например, сети). Могут синхронизироваться только сообщениями. Взаимодействие по системе «клиент-сервер». Процессам часто нужно взаимодействовать друг с другом, например, 1 процесс может передавать данные другому процессу, или несколько процессов могут обрабатывать данные из общего файла. В этих случаях возникает проблема синхронизации процессов. Она связана с потерей доступа к параметрам из-за их некорректного разделения.

Критический ресурс ‐ разделенная переменная, к которой обращаются разные процессы. Критическая секция ‐ строки кода, в кот. происходит обращение к критическому ресурсу.

Необходимо обеспечить монопольный доступ процесса к критическому ресурсу, до тех пор пока процесс его не освободит. То есть чтобы не могли одновременно войти в критическую секцию.

Централизованный и распределенный алгоритмы

Централизованный алгоритм - Процесс‐координатор (м.б. выбран процесс с наиб. сетевым адресом) отвечает за возможность вхождения в критические секции. Как только процесс готов войти в критич. область, он посылает сообщение, где указывает ID крит. секции.Процесс сможет зайти в крит. секцию только после ответа координатора. Координатор проверяет, не находится ли к‐л. др. процесс в крит. области (по полученным сообщениям). Если находится, то корд. не посылает ответ, а ставит запрос в очередь. После освобождения крит. области процессу б. выслан ответ‐подтверждение. Если координатор аварийно завершился необходимо выбрать новый координатор. Если к‐ л. процесс обнаружит отсутств. корд. (время ожид ответа > кртитич. времени), то процесс инициирует выбор нового координатора. Самый эффективный алгоритм.

Распределенный алгоритм

Алгоритм формулируется следующим образом:

1. Когда процесс хочет войти в критическую секцию, он формирует сообщение.
   • В этом сообщении он указывает:
     • идентификатор нужной ему критической секции;
     • свой номер (идентификатор);
     • время формирования сообщения по своим локальным часам.
   • Предполагается, что передача сообщения надёжна: получение каждого сообщения сопровождает подтверждение.
   • Протокол - соглашение о том, какие действия выполняют процессы при передаче и получении сообщения. Надёжный протокол всегда предполагает подтверждение получения сообщения.
2. Это сообщение, сформированное процессом, процесс рассылает всем взаимодействующим процессам (то есть n - 1 сообщение)
3. Получив такое сообщение, процесс проверяет, в какой ситуации он сам находится по отношению к критической секции.
   • Возможны 3 ситуации:
     1. получивший сообщение процесс не собирается входить в данную критическую секцию (и не находится в ней). В этом случае процесс посылает сообщение-ответ с разрешением войти в критический участок;
     2. процесс, получивший сообщение, находится в данной критической секции. В этом случае никакое сообщение не посылается;
     3. Процесс, получивший сообщение, сам формировал сообщение запрос на вход в данную критическую секцию, но еще не успел это сделать.
        • (на доске: хочет войти в ту же критическую секцию). Тогда процесс проверяет временную метку создания своего сообщения, сравнивает ее с временной меткой полученного сообщения. Если его сообщение было сформировано раньше, то никакого сообщения-ответа процесс не посылает. Если в результате таких рассылок процесс получает n - 1 сообщение подтверждения входа в критический участок, то процесс может войти в критический участок. Если он не получает хотя бы одно сообщение, то в критический участок процесс войти не может.

В этом случае процесс должен послать n - 1 сообщение-запрос и в ответ получить n - 1 сообщение-разрешение на вход, иначе войти не может.

Алгоритм Лампорта

Алгоритм Лампорта применяется для синхронизации временных ответок (для соблюдения отношения "случилось до / случилось после")

• Процесс, отправивший сообщение, так же отправляет время отправки по локальным часам.
• В случае, если время процесса меньше, чем время отправления, то он сам устанавливает время отправления: пришедшее + 1.

RPC – механизм

RPC - это механизм, с помощью которого один процесс активизирует другой процесс на этой же или удаленной машине для выполнения какой-то работы (функции) от своего имени. В Unix он напоминает вызов обычной (локальной) функции. Вызываемая функция выполняется (может выполняться) на совершенно другой машине. Это взаимодействие выполняется по модели клиент-сервер. Процесс, который вызывает функцию RPC является клиентским. Процесс, который выполняет функцию на этой же или на другой машине, является серверным.

Описание работы:

Прикладная программа, выполняемая клиентским процессом, выполняет вызов удаленной процедуры. При этом для этой программы это просто вызов на локальной машине. В системе существует интерфейс, то есть вызов, выполняемый приложением, преобразуется в вызов так называемого клиентского stab'a (фиктивный модуль клиента; клиентская заглушка).

Вызов клиентского стаба, действия:

1. Подготовка буфера сообщения.
2. Упорядочивание параметров в буфере.
3. Добавление в собщение полей заголовков.
4. Системный вызов, в результате которого происходит переход в режим ядра и выполняется переключение контекста.
5. В ядре для того, чтобы обработать сообщение, оно должно быть скопировано в буфер ядра (В режиме пользователя свой буфер, в режиме ядра - свой).
6. Определение адреса назначения.
7. Адрес помещается в заголовок сообщения.
8. Инициализируется сетевой интерфейс.
9. Включается таймер.

Первые 4 действия выполняет стаб клиента.

В результате вызова начинает выполняться stab. Происходит вызов функции стандартной библиотеки. Взаимодействие выполняется через сокеты.

В результате вызова библиотечной функции, происходит обращение к местному сокету (сокету BSD).

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

Итог действий на стороне клиента - формирование сетевого пакета, который передается процессу-серверу.

На серверной стороне через сокет пакет поступает на машину, на которой выполняется процесс-сервер. Вызывается библиотека и её функции. На стороне сервера имеется серверный stab.

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

Вопрос 2.

Аппаратные прерывания: типы аппаратных прерываний, особенности

Типы аппаратных прерываний.

1. Прерывание от системного таймера - асинхронное периодическое прерывание. Оно периодически выполняется в разных системах с разной частотой.
2. Прерывание от действий оператора (например, ctrl+C - завершение процесса в Unix).
3. Асинхронные события в системе. Например, прерывания от внешних устройств. Большую часть аппаратных прерываний составляют прерывания от внешних устройств, и именно эти прерывания информируют процессор о завершении операции ввода вывод.

Прерывания от устройств ввода-вывода: назначение и аппаратная реализация

Назначение:

Назначение прерываний от устройств ввода-вывода - информирование процессора об асинхронных событиях, поступающих в систему.

Аппаратные прерывания - их задача заключается в информировании процессора о завершении ввода вывода, по большей части (Источник - https://github.com/chrislvt/OS/wiki/Лекция-02).

Аппаратная реализация (концептуальная (нефизическая) схема; PIC):

Прерывание от системного таймера в защищенном режиме

БЛИН, КАЖЕТСЯ, ЭТО НЕ ТО( РЯЗАНЬ СКАЗАЛА, ЧТО ЭТИ ОСЫ РАБОТАЮТ В long mode'e, ПОЭТОМУ ЭТО НЕМНОГО НЕ О ТОМ

UNIX

По тику:

• инкрементирует счетчик тиков аппаратного таймера;
• декременирует квант текущего потока;
• обновляет статистику использования процессора текущим процессом — инкремент поля c_cpu дескриптора текущего процесса до максимального значения 127;
• инкрементирует счетчики часов и других таймеров системы;
• декрементирует счетчик времени до отправления на выполнение отложенного вызова (если счетчик достиг нуля, то выставление флага для обработчика отложенного вызова).

По главному тику:

• регистрирует отложенные вызовы функций, относящиеся к работе планировщика, такие как пересчет приоритетов;
• пробуждает в нужные моменты системные процессы, такие как swapper и pagedaemon. Под пробуждением понимается регистрация отложенного вызова процедуры wakeup, которая перемещает дескрипторы процессов из списка "спящих" в очередь готовых к выполнению.
• декрементирует счётчик времени, оставшегося времени до посылки одного из следующих сигналов:
  • SIGALRM – сигнал, посылаемый процессу по истечении времени, предварительно заданного функцией alarm();
  • SIGPROF – сигнал, посылаемый процессу по истечении времени заданного в таймере профилирования;
  • SIGVTALRM – сигнал, посылаемый процессу по истечении времени, заданного в "виртуальном" таймере.

По кванту:

• посылает текущему процессу сигнал SIGXCPU, если тот превысил выделенную ему квоту использования процессора.

Windows

По тику:

• инкрементирует счётчик системного времени;
• декрементирует квант текущего потока на величину, равную количеству тактов процессора, произошедших за тик (если количество затраченных потоком тактов процессора достигает квантовой цели, запускается обработка истечения кванта);
• декрементирует счетчики времени отложенных задач;
• если активен механизм профилирования ядра, инициализирует отложенный вызов обработчика ловушки профилирования ядра путем постановки объекта в очередь DPC: обработчик ловушки профилирования регистрирует адрес команды, выполнявшейся на момент прерывания.

По главному тику:

• освобождает объект "событие", который ожидает диспетчер настройки баланса.

По кванту:

• инициализирует диспетчеризацию потоков путем постановки соответствующего объекта в очередь DPC.

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

new_int08 proc uses eax ebx
        mov edi, 160 + 60    ;Смещение(позиция) курсора в видеопамяти
        mov al, 21h     ;Символ "!" (байт символа)
        mov ah, 75h     ;Цвет       (байт атрибута)
        shl ah, 1
        stosw           ;al (символ) с параметром (ah) перемещается в область памяти es:di

        mov al, 20h         ;EOI ведомого контроллера
        out 20h, al

;Поскольку в защищенном режиме аппаратное прерывание смещает стек не на три слова,
;как в реальном режиме, а на 6, обработчики прерываний должны заканчиваться
;"длинной" командой iret, которая снимет со стека три двойных слова.
        iretd   ;double - 32-битный iret
    new_int08 endp