• P(S) – декремент значения семафора и проверка нового значения, если оно не меньше нуля, то выполняется критическая секция процесса, иначе процесс переводится в состояние ожидания;

• V(S) – увеличение значения семафора на единицу и перевод в состояние готовности процессов, ожидающих критический ресурс.

Существует множество «семафорных» алгоритмов, создающих значения семафора с разными областями возможных целочисленных значений. Семафоры, имеющие бинарное значение называются МЬЮТЕКСАМИ. Мьютексы имеют два состояния «Отмечен» (открыт) и «Не отмечен» (закрыт).

Недостатком механизма семафоров является примитивность семафоров: они не содержат ни непосредственного указания на синхронизирующий механизм, ни непосредственного указания на ресурс, который они контролируют.

36. Поясните принцип действия мониторов.

Монитором в параллельном программировании называют пассивный набор разделяемых переменных и повторно входимых процедур (см. раздел 1.6). Повторно входимые процедуры обеспечивают доступ к разделяемым переменным. В каждый момент времени монитором может пользоваться только один процесс. Процедуры монитора исполняются только по требованию процессов.

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

37. Поясните принцип действия почтовых ящиков.

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

38. Поясните работу конвейеров и очередей сообщений.

Конвейеры, иначе транспортёры или каналы связи, представляют собой потоки байтов, передающихся между двумя и более процессами. Физически конвейеры реализуются как буферная память, работающая по принципу FIFO, но они не являются очередями. Как информационная структура конвейеры описываются идентификатором, размером (не более 64К), указателем начала данных и указателем конца данных, которые определяют адреса начала и конца данных. Конвейер представляет собой закольцованную очередь (рис. 3.8).

В исходном состоянии оба указателя равны нулю. При добавлении в конвейер данных оба указателя увеличиваются на единицу. Дальнейшее добавление данных увеличивает значение указателя на конец данных (рис. 3.8,а). Чтение и удаление данных происходит всегда с начала. Поэтому при чтении и удалении данных приходится изменять значения указателей. В итоге указатели движутся от начала конвейера к её концу. Серым цветом на рис. 3.8 показаны записанные данные. Свободная область в начале конвейера образовалась в результате удаления и чтения данных.

Очереди позволяют одному или нескольким процессам посылать сообщения одному процессу-приёмнику. Читать и удалять сообщения из очереди может только процесс приёмник. Процессы-источники могут только посылать сообщения в очередь. Пересылка сообщений возможна только от процессов источников к процессу-приёмнику, т.е. связь процессов односторонняя. Для получения двусторонней связи необходимо организовывать две очереди сообщений.

Очереди сообщений являются более удобным средством обмена сообщениями, чем конвейеры, но имеют более сложную реализацию. Они предоставляют возможность использовать несколько дисциплин работы с сообщениями: FIFO, LIFO, приоритетный доступ и произвольный доступ.

Второй особенностью очереди сообщений является сохранение в ней прочитанных записей, в то время как из конвейера они удаляются. Третьей особенностью очереди является присутствие в очереди не сообщений, а их адреса в памяти и размер. Эти данные хранятся в области памяти, которая является общей для процессов, обменивающихся сообщениями. Каждый процесс, пользующийся очередью должен получить доступ к общему разделу памяти через системные запросы API, т.к. очередь – это системный механизм.

43. Поясните как возникновение тупика при кольцевом обмене процессов сообщениями через почтовые ящики.

При обмене процессами сообщениями через почтовые ящики по кольцевой схеме (рис. 4.2) возможно возникновение тупика. Процессы ПР1, Пр2, Пр3 создают сообщения М1, М2 и М3 соответственно. Посылка сообщения является запросом разделяемого ресурса типа CR, приём сообщения – освобождением запрошенного ресурса. Следует помнить, что процесс может послать сообщение только в почтовый ящик при наличии свободного гнезда. Взаимодействие процессов осуществляется посредством получения сообщений от предшествующего процесса и посылкой сообщения последующему.

Если поменять местами операторы посылки сообщения и ожидания сообщения, то получится тупик, т.к. ни один процесс не сможет послать сообщение до тех пор, пока не получит сообщение от предшествующего процесса, а тот, в свою очередь, заблокирован.

Таким образом, при кольцевом обмене процессов сообщениями причиной тупика является неправильная последовательность операторов посылки и ожидания сообщения.

44. Приведите пример возникновения тупика в системе с семафорами.

45. Приведите пример возникновения тупика в системе с мониторами.

46. Что такое сеть Петри? Из каких элементов она состоит?

Сети Петри могут быть представлены в аналитической и в графической форме. В первом случае становится возможной автоматизация процесса анализа, во втором – наглядное изображение параллельного процесса.

Элементы сети Петри:

• вершины-переходы, соответствующие событиям, происходящим в системе;

• вершины-позиции, соответствуют условиям возникновения событий;

• направленные дуги (стрелки);

• фишки (точки в вершинах-позициях) – средства активизации переходов.

Переход активен, если в каждой позиции, соединённой с ним входящей дугой, имеется фишка. Движение фишки возможно только через активный переход. Расположение фишек называется разметкой сети.

47. Как нейтрализовать условие взаимного исключения для предотвращения тупика?

Условие взаимного исключения можно нейтрализовать разрешением неограниченного разделения ресурсов. Это приемлемо для повторно входимых программ и ряда драйверов, но неприемлемо для общих переменных, используемых в критических секциях процессов.

48. Как ослабить условие ожидания для предотвращения тупика?

Действие условия ожидания можно ослабить предварительным выделением процессу разделяемых ресурсов и блокированием процессов, не получивших предварительно все необходимые ресурсы. Однако такой подход снижает эффективность операционной системы, и не всегда реализуем, т.к. далеко не все процессы "знают" перед началом выполнения список необходимых им ресурсов.

49. Как подавить условие отсутствия перераспределения ресурса у блокированного процесса для предотвращения тупика?

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

50. Как исключить условие кругового ожидания для предотвращения тупика?

Условие кругового ожидания можно исключить введением иерархии разделяемых ресурсов и введения дисциплины их выделения и освобождения. Захват процессом ресурсов происходит в направлении повышения иерархического уровня захватываемых ресурсов, а освобождение – в направлении понижения уровня освобождаемых ресурсов. Поэтому захват процессом ресурса некоторого уровня заблокирует захват им ресурсов того же или более низкого уровня, но не запретит захват ресурсов более высокого уровня. Освобождение ресурсов происходит в обратном порядке: сначала освобождаются ресурсы верхних уровней иерархии, а затем – нижних.

Магнитные и оптические диски. Файловые системы

1. Определите понятия: дорожка, цилиндр, сектор, кластер.

• Дорожка – намагниченный участок рабочей поверхности носителя информации, имеющий форму окружности с центром на оси шпинделя

• Сектор – фрагмент дорожки, отделенный от других секторов магнитными метками

• Цилиндр – совокупность дорожек одинакового радиуса всех рабочих поверхностей носителей информации

• Кластер – несколько секторов на дорожке идущих подряд.

2. Поясните способы CHS и LBA адресации секторов на магнитном диске.

Для обращения к кластерам, секторам и блокам данных имеется две системы физических адресов элементов дискового пространства: CHS и LBA. В системе CHS координатами сектора являются: номер цилиндра (Cylinder), номер рабочей поверхности носителей (Нead), он же номер дорожки в цилиндре, номер сектора на дорожке (Sector).

В системе LBA (Logical Block Addressing) используется линейная адресацию секторов, начиная с сектора 1, головки 0, цилиндра 0 и заканчивая последним физическим сектором диска. Адрес начального сектора диска обозначается как LBA 0. Номер сектора в системе LBA определяется выражением:

LBA = (СхHmax + H)xSmax + S – 1

где С, H, S – координаты сектора в системе CHS,

Hmax – общее количество рабочих поверхностей дисков,

Smax – число секторов на дорожке.

3. Поясните логическую структуру диска.

Дисковое пространство с помощью специальной программы (например, F Disk) делится на разделы. Каждому разделу присваивается буквенное имя (т.н. имя логического диска). Один раздел называется первичным, на нем по умолчанию образуется диск «С:» и помещается главный загрузчик операционной системы (Master Boot Record). Загрузочный сектор имеет главную таблицу разделов (т.е. таблица с адресом первичного раздела, адресом расширенного раздела, внесистемный загрузчик и системный загрузчик). В расширенном разделе можно создать несколько логических дисков, каждый из них имеет свой загрузочный сектор и загрузчик (Secondary Master Boot Record). Часть памяти может быть не распределена.

4. Каково содержимое Master Boot Record'а?

Главная загрузочная запись (англ. master boot record, MBR) — код и данные, необходимые для последующей загрузки операционной системы и расположенные в первых физических секторах (чаще всего в самом первом) на жёстком диске или другом устройстве хранения информации.

MBR содержит небольшой фрагмент исполняемого кода, таблицу разделов (partition table) и специальную сигнатуру.

Функция MBR — «переход» в тот раздел жёсткого диска, с которого следует исполнять «дальнейший код» (обычно — загружать ОС). На «стадии MBR» происходит выбор раздела диска, загрузка кода ОС происходит на более поздних этапах алгоритма.

В процессе запуска компьютера, после окончания начального теста (Power-on self-test — POST), Базовая система ввода-вывода (BIOS) загружает «код MBR» в оперативную память (в IBM PC обычно с адреса 0000:7c00) и передаёт управление находящемуся в MBR загрузочному коду.

5. Каково содержимое Secondary Master Boot Record'а?

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

6. В чём проблема четырёх первичных разделов? Почему её желательно решить? Каковы способы решения этой проблемы?

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

39. Что такое тупик? Приведите примеры.

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

Процессы Р1 и Р2 вошли в критические секции и захватили ресурсы R1 и R2 соответственно. Впоследствии P1 затребовал R2, а P2 – ресурс R1. Но ресурсы уже заняты. Критические секции процессов не завершены, процессы в режиме ожидания.

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

40. Каковы условия возникновения тупика?

Для появления тупиков должны одновременно выполняться четыре условия:

• взаимное исключение не запрещает монопольный доступ к разделяемым ресурсам (условие взаимного исключения);

• удержание процессом захваченного ресурса на время ожидания доступа к недостающим для продолжения его работы разделяемым ресурсам (условие ожидания);

• невозможность перераспределения ресурсов, захваченных процессами, находящимися в режиме ожидания (условие отсутствия перераспределения);

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

41. Какова классификация разделяемых ресурсов в модели Холта?

42. В чем разница между системными ресурсами и расходуемыми ресурсами?

Системные ресурсы SR представляют собой множество идентичных единиц некоторого вида ресурсов. Это множество единиц конечно и неизменно в операционной системе. Каждая единица ресурса либо доступна, либо выделена какому-либо процессу. Никакой процесс не может влиять на ресурс (или на его единицу), который ему не принадлежит. К системным ресурсам относятся основная и внешняя память, периферийные устройства, иногда процессоры, программное обеспечение, файлы данных, таблицы и разрешение войти в критическую секцию.

Расходуемые ресурсы CR также представляют собой конечное множество идентичных единиц ресурсов одного вида. Однако процессы могут порождать единицы и освобождать порождённые единицы ресурса, поэтому число единиц расходуемых ресурсов переменно. Процесс потребитель ресурса уменьшает число единиц, потребляет их и не возвращает ресурсу. К ресурсам CR относятся, в частности, прерывания от таймера и устройств ввода-вывода, сигналы синхронизации процессов, сообщения, содержащие различные запросы на обслуживание и данные, и соответствующие им ответы.

Решение проблемы: применение нестандартного загрузчика.

7. Что такое внесистемный и системный загрузчики? Каковы их функции?

На первом секторе логического диска С: располагается также специальная программа, которая называется внесистемным загрузчиком Non-System Bootstrap (NSB).

Процедура начальной загрузки (bootstrap loader) вызывается как программное прерывание (BIOS INT 19h). Эта процедура определяет первое готовое устройство из списка разрешенных и доступных (гибкий или жесткий диск, а в современных компьютерах это могут быть еще и компакт-диск, привод ZIP-drive компании Iomega, сетевой адаптер или еще какое-нибудь устройство) и пытается загрузить с него в оперативную память короткую главную программу-загрузчик. Для накопителей на жестких магнитных дисках — это уже известный нам главный, или внесистемный, загрузчик (NSB) из MBR, и ему передается управление. Главный загрузчик определяет на диске активный раздел, загружает его собственный системный загрузчик и передает управление ему. И наконец, этот загрузчик находит и загружает необходимые файлы операционной системы и передает ей управление. Далее операционная система выполняет инициализацию подведомственных ей программных и аппаратных средств. Она добавляет новые сервисы, вызываемые, как правило, тоже через механизм программных прерываний, и расширяет (или заменяет) некоторые сервисы BIOS. Необходимо отметить, что в современных мультипрограммных операционных системах большинство сервисов BIOS, изначально расположенных в ПЗУ, как правило, заменяются собственными драйверами ОС, поскольку они должны работать в режиме прерываний, а не в режиме сканирования готовности.