Файловые системы fat16, fat32, NTFS, NFS и другие

Нити

Тупики

Приведенный выше пример поможет нам проиллюстрировать еще одну проблему синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками. Если переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Действительно, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писателем".

Рассмотрим еще один пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, принтер и диск. На рисунке 5 показаны фрагменты соответствующих программ. И пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.

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

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

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

Проблема тупиков подразумевает решение следующих задач: предотвращение тупиков, распознавание тупиков, восстановление системы после тупиков.

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

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

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

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

Таблица распределения ресурсов (какой процесс, какие ресурсы занимает)		Таблица запросов к ресурсам (какой процесс, какой ресурс ожидает)
MS WORD Outlook Express MS EXEL Explorer Win Commander	файл А сетевая карта файл В Принтер дисковод а:	Access MS WORD MS EXEL Explorer	сетевая карта файл В Принтер файл А

1. Берем первый процесс из таблицы ожидания. Access ожидает освобождения сетевой карты. Теперь по таблице распределения ресурсов отыскиваем процесс, который занимает сетевую карту. Это - Outlook Express. Теперь проверяем, какой ресурс ожидает Outlook Express. Поскольку его нет в таблице ожидания, делаем вывод о том, что он просто ожидает своей очереди, чтобы занять процессор (то есть он находится в очереди готовых), выполнить некоторые действия, после которых он освободит сетевую карту. Следовательно, тупика здесь нет. Кстати, если бы в таблице распределения не нашелся процесс, занимающий сетевую карту, то это говорило бы об ошибке в ОС. По-видимому, в таком случае ОС может распределить Access сетевую карту и перевести его в очередь готовых.

2. Теперь точно так же рассуждаем для следующего процесса из очереди ожидания - MS WORD. MS WORD ожидает файл В. В таблице распределения отыскиваем процесс, занимающий файл В. Это - MS EXEL. Теперь ищем MS EXEL в таблице запросов. Оказывается, он ждет принтер. Далее ищем в таблице распределения, кто занимает принтер. Это – Explorer. Снова по таблице ожидания ищем, что ожидает Explorer. Он ждет файл А. Наконец, по таблице распределения смотрим, какой процесс занимает файл А и обнаруживаем, что это - MS WORD. Так как вернулись к исходному процессу, делаем вывод о наличии тупика.

Приведенные рассуждения нетрудно записать в виде алгоритма. Это – не самый хороший алгоритм. Попробуйте придумать лучше.

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

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

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

Итак, методы решения проблемы синхронизации:

1. запрет прерываний процесса во время работы с ресурсом;

2. блокирующие переменные;

3. функции WAIT(ресурс) POST(ресурс);

4. семафоры;

5. мониторы.

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

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

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

Для этих целей современные ОС предлагают использовать механизм многонитевой обработки (multithreading). При этом вводится новое понятие "нить" (thread), а понятие "процесс" в значительной степени меняет смысл.

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

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

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

Нити иногда называют облегченными процессами или мини-процессами или потоками. Действительно, нити во многих отношениях подобны процессам. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находиться в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования.

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

Итак, нити имеют собственные:

программный счетчик, стек, регистры, нити-потомки, состояние.

Нити разделяют (то есть имеют в общем пользовании):

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

Многонитевая обработка повышает эффективность работы системы по сравнению с многозадачной обработкой.

Широкое применение находит многонитевая обработка в распределенных системах. Об этом будет сказано позже.

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

Другой пример использования нитей - это управление сигналами, такими как прерывание с клавиатуры (del или break). Вместо обработки сигнала прерывания, одна нить назначается для постоянного ожидания поступления сигналов. Таким образом, использование нитей может сократить необходимость в прерываниях пользовательского уровня. В этих примерах не столь важно параллельное выполнение, сколь важна ясность программы.

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

Вопросы и задачи:

· Назовите возможные состояния процесса, какие очереди организует ОС?

· Что такое контекст и дескриптор? Когда появляются контекст и дескриптор процесса?

· Преимущества и недостатки вытесняющей и не вытесняющей многозадачности.

· Причины, по которым процесс покидает процессор в случае вытесняющей многозадачности и не вытесняющей?

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

· Что такое критическая секция, приведите пример некоторой программы, укажите к ней критическую секцию.

· Сколько критических секций одновременно может поддерживать одна ОС.

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

· Чем плох метод блокирующих переменных, на что предлагается его заменить?

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

· Чем отличается метод семафоров в общем случае от метода блокирующих переменных. Приведите примеры.

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

· Приведите пример возможного тупика.

· Что такое монитор, его отличие от семафоров.

· Методы борьбы с тупиками.

· Составьте алгоритм распознавания тупика.

· Что такое нити. В какой ситуации применение нитей приводит к повышению производительности, а в какой – к понижению.

· Какова, по-вашему, причина того, что применение нитей не является широко распространенным?

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

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

Дата добавления: 2014-12-07