15. Условие «кругового ожидания » и его разрешение.
Нарушение условия кругового ожидания.
Третий стратегический принцип исключает круговое ожидания. По стольку всем ресурсам присваиваются индивидуальные номера, а процессы должны запрашивать ресурсы в порядке возрастания номеров, то кругового ожидания возникнуть не может. Такой принцип реализован в большинстве современных операционных систем, однако можно отметить и некоторые недостатки, одним из которых является следующий: постольку запрос ресурсов осуществляется в порядке возрастания их номеров и номера ресурсов назначаются при генерации системы и чаще всего действуют в течение длительного промежутка времени, то в случае введения в систему нового типа ресурсов может возникнуть необходимость переделки программ и систем.
Примечание (третий принцип Хавендера) : Следует ввести линейную упорядоченность по типам ресурсов для всех процессов. Если процессу выделены ресурсы данного типа, то в дальнейшем он может запрашивать только ресурсы далёких по порядку типов. Всем ресурсам в системе присваиваются уникальные номера и процессы должны запрашивать ресурсы в порядке возрастания номеров, что позволяет не возникнуть в системе ситуации «кругового ожидания».
16. Понятие критической области и её значение для функционирования системы.
Когда несколько процессов могут асинхронно изменять содержимое общей области данных, необходимо защитить данные от одновременного изменения двумя и более процессами. Рассмотрим два процесса P1 и P2 работающих на центральных процессорах C1 и C2. Эти процессы увеличивают значение переменной X, которая представляет число единиц ресурса. Если P1 выполняется на C1, а P2 выполняется на C2, то может возникнуть одна из следующих последовательностей:
P1:R1:=x; R1:=R1+1; x:=R1; ….
P2:… R2:=x; R2:=P2+1; x:=R2;
t0 → time
P1:R1=x; R1:=R1+1; x:=R1;…
P2:… R2:=x; R2:=R2+1; x:=R2;
Пусть х содержит значение V в момент времени t0. В момент tk переменная содержала бы V+1 , если бы выполнение шло на процессорах С1 и С2 выполнялось бы по 1) и переменная х содержала бы V+2 , если выполнялось по 2). Оба значение могут быть реализованы, если Р1 и Р2 разделены во времени. При этом должно учитываться каждое приращение х. Решение заключается в x:=x+1 только одному процессу. Если имеется несколько последовательных процессов, которые могут связываться друг с другом через общую память для хранения данных, то каждая программа, выполняемая процессорами, содержит критическую область, в которой организован доступ к общим данным. Проблема заключается в том, чтобы запрограммировать процессы так, чтобы в любой момент только один из процессов находился в своей критической области. Если процесс P входит в свою критическую область (CS) то никакой другой процесс не может сделать, то же самое до тех пор, пока P не покинет свою CS. Следует иметь в виду, что в любом случае должны выполняться следующие предположения:
Считывание из общей памяти и запись в неё есть неделимая операция.
Критические области не могут иметь связанных с ними приоритетов.
Программа может останавливаться и вне своей критической области.
Схема работы с критической областью может быть представлена следующим образом:
Основной целью является взаимное исключение. Одновременно должны быть устранены два возможных типа блокировки:
Процесс нормально работающий вне своей CS не может блокировать другой процесс при вхождении другого процесса в свою CS.
Два процесса, готовые войти в свои критические области не могут откладывать неопределённо долго решение о том какой из них действительно войдёт в CS первым, используя принцип «сверхвежливости».