Файл: Вопросы для подготовки к экзамену по дисциплине " Операционные системы ".docx

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

44. 
    Приведите пример возникновения тупика в системе с семафорами.
    
45. 
    Приведите пример возникновения тупика в системе с мониторами.
    
46. 
    Что такое сеть Петри? Из каких элементов она состоит?
    

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

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

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

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

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

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

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

---

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

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

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

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

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

---