Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Семафоры

Читайте также:
  1. Семафоры
  2. Семафоры – механизм синхронизации процессов

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

Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом.

V(S): переменная S увеличивается на 1. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа другим потокам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S = 0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию P(S), ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также являются неделимой операцией.

Никакие прерывания во время выполнения примитивов V и Р недопустимы.

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

Введем два семафора: е — число пустых буферов, и f — число заполненных буферов, причем в исходном состоянии е = N, a f = 0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис. 4.14.).

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

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

Тупики

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

Итак, пусть поток-писатель начинает свою работу с проверки доступности критической секции — операции Р(b), и пусть он первым войдет в критическую секцию. Выполняя операцию Р(е), он может обнаружить отсутствие свободных буферов и перейти в состояние ожидания. Как уже было показано, из этого состояния его может вывести только поток-читатель, который возьмет очередную запись из буфера. Но поток-читатель не сможет этого сделать, так как для этого ему потребуется войти в критическую секцию, вход в которую заблокирован потоком-писателем. Таким образом, ни один из этих потоков не может завершить начатую работу и возникнет тупиковая ситуация, которая не может разрешиться без внешнего воздействия.

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

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

Выводы

· Мультипрограммирование, или многозадачность (multitasking), — это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются сразу несколько программ.

· Мультипрограммирование применяется для повышения эффективности вычислительной системы, которая может пониматься как:

o общая пропускная способность вычислительной системы;

o удобство работы пользователей, например возможность интерактивной работы для нескольких пользователей или возможность одновременной работы одного пользователя с несколькими приложениями на одной машине;

o реактивность системы — то есть способность системы выдерживать заранее заданные (возможно, очень короткие) интервалы времени между запуском программы и получением результата.

· В зависимости от выбранного критерия эффективности ОС делятся на системы пакетной обработки, системы разделения времени и системы реального времени.

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

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

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

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

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

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

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

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

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

· В зависимости от источника прерывания делятся на три больших класса:

o внешние прерывания, связанные с сигналами от внешних устройств;

o внутренние прерывания, возникающие в результате ошибок вычислений;

o программные прерывания, представляющие собой удобный способ вызова процедур операционной системы.

· Механизм прерываний поддерживается аппаратными средствами компьютера и программными средствами операционной системы.

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

· Для упорядочивания процессов обработки прерываний все источники прерываний распределяются по нескольким приоритетным уровням, а роль арбитра выполняет диспетчер прерываний ОС.

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

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

Вопросы для самоконтроля

1. Поясните употребление терминов «программа», «процесс», «задача», «поток», «нить».

2. В чем состоит принципиальное отличие состояний «ожидания» и «готовности» потока, ведь и в том и в другом он ожидает некоторого события?

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

4. В какой очереди (ожидающих или готовых) скапливается большее число процессов:

A) в интерактивных системах разделения времени;

B) в системах пакетной обработки, решающих «счетные» задачи.

5. Известно, что программа А выполняется в монопольном режиме за 10 минут, а программа В — за 20 минут, то есть при последовательном выполнении они требуют 30 минут. Если Т — время выполнения обеих этих задач в режиме мультипрограммирования, то какое из неравенств, приведенных ниже, спра ведливо?

А) Т<10;

В) 10<Т<20;

С) 20<Т<30;

D) Т>30.

6. Может ли процесс в мультипрограммном режиме выполняться быстрее, чем в монопольном?

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

8. При невытесняющем планировании необходимо, чтобы во всех выполняющихся программах были предусмотрены кодовые последовательности, которые передают управление ОС. Эти точки возврата управления прикладной программист должен определить заранее еще до выполнения программы. Можно ли сказать, что в этом случае мы имеем дело со статическим планированием?

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

10.Для тех вариантов, которые вы считаете возможными, опишите более подробно алгоритм планирования.

11.Являются ли синонимами термины «планирование процессов» и «диспетчеризация процессов»?

12.Можно ли задачу планирования процессов целиком возложить на приложения?

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

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

15.Представьте себе ОС, разработанную для компьютера, в котором отсутствует система прерываний. Какой алгоритм планирования процессов может быть реализован в такой ОС?

16.Какие события вызывают перепланирование процессов (потоков)?

17.Поясните разницу между программными и аппаратными прерываниями.

18.Что такое вектор прерываний?

19.Какой тип системы прерываний — векторный или опрашиваемый — реализован в процессоре Pentium?

20.Всегда ли прерывание вызывает перепланировку процессов?

21.Какими средствами синхронизации процессов располагает современная ОС?

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




Дата добавления: 2015-01-30; просмотров: 90 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав