Лекция 09 - chrislvt/OS GitHub Wiki

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

Лексикографический порядок

Вот такая запись называется лексикографическим порядком:
(a, b) < (c, d) - истина, если a < c || (a == c && b < d).
На языке это записывается в сложное выражение, но НЮ предлагает вспомнить наставление Тассова, который убеждал нас не использовать длинные логические выражения. Потому что сложно и нечитаемо. То есть это надо делать продуманно и изящно вот.

Применительно к bakery-алгоритму Лампорта (см пред лекцию). Когда процесс p_i хочет войти в свой критический участок, p_i ждёт пока у него не будет самый маленький номер среди всех процессов, которые желают войти в свой критический участок. Если два процесса имеют одинаковые номера, то есть "одновременно вошли в дверь", то в критический участок войдёт процесс с наименьшим собственным номером. Строки 9-13 в псевдокоде. (здесь будет ссылка на пред лекцию). То есть, если вернуться к аналогии с булочной, то первым из двух одновременно пришедших покупателей будет покупатель с меньшим номером паспорта.

Аппаратные способы реализации взаимоисключений

Test-and-set

Команда test-and-set. Записывается по-разному, но неважно. Эта команда появилась в ....(неслышно (4:30)). Это неделимая команда, которая выполняет проверку, а затем установку содержимого ячейки памяти, которая называется байт блокировки. Существует ряд команд подобных test-and-set. Это очень важные команды в ОС.
test-and-set читает значение логической переменной B, копирует его в A, а затем для B устанавливает значение истина. НЕДЕЛИМАЯ!
Пишем код:

flag, c1, c2: logical;

// p1
while (1) {    
    c1 = 1;
    while (c1 == 1) {
       test-and-set(c1, flag);
    }
    CR1;
    flag = 0;
    PR1; 
}  

// p2   
while (1) {    
    c2 = 1;
    while (c2 == 1) {
       test_and_set(c2, flag);
    }
    CR2;
    flag = 0;
    PR2; 
}  

// начальная установка
flag = 0;
parbegin
   p1; p2;
parend

flag = true, если любой из процессов находится в своём критическом участке и false в противном случае. Рассмотрим случай, когда p1 хочет зайти в свой КУ, а процесс p2 уже находится в КУ. p1 устанавливает c1 = 1, а затем входит в цикл проверки переменной flag командой test-and-set. Поскольку p2 находится в своём КУ, то flag = 1. Команда test-and-set обнаруживает этот факт и устанавливает c1 = 1. Таким образом p1 находится в своём цикле активного ожидания до тех пор, пока p2 не выйдет из КУ. Этот способ реализации не исключает бесконечного откладывания, но его вероятность считается очень небольшой. Когда процесс выходит из КУ и устанавливает flag = 0, то, скорее всего, другой процесс сможет перехватить инициативу и установить flag = 1.

Самое важное про test-and-set - она широко используются в ядре. Чаще всего в цикле (как в примере выше). Поэтому очень часто ...что-то невнятное (18:10)... называется циклической блокировкой (spin-lock, simple-lock, simple mutex). Это очень важные команды, в основе которых лежит test-and-set. Чаще всего test-abd-set возвращает предыдущее значение переменной. Пишем spinlock:

// c - conditional (переменная типа "условие")
void spin_lock(spin_lock_t *c)
{
    while (test-and-set(*c) != 0) {
        // ресурс занят
    }
}

Понятно, что для того чтобы сделать команду test-and-set неделимой необходимо заблокировать шину данных. Это крайне негативное действие в системе, которое значительно снижает отзывчивость системы. То есть если будет использоваться длительный цикл активного ожидания, это может привести к занятию шины одной единственной нитью (нитью??? 22:10) или потоком. Это снизит производительность системы. Эта проблема решается следующим образом:

void spin_lock(spin_lock_t *c)
{
    while (test-and-set(*c) != 0) {
        while (*c != 0); // проверка без захвата шины памяти
    }
}

Если ресурс занят, если выполнена проверка командой test-and-set, то затем в цикле выполняется просто проверка c без захвата шины памяти. Ну и spin_unlock:

void spin_unlock(spin_lock_t *c)
{
    *c = 0;
}

Это парные команды. Ядрёные команды. То есть они очень часто используются в ядре операционных систем. Почему? Очень часто (Нихуя не слышно, хули там скребёт 25:10) ... но оказывается.... Вопрос взаимоисключений в ядре является очень важным, но за неимением учебного процесса не удаётся затронуть эту волнующую тему. Переходим на важнейшую тему - семафоры.

Семафоры

Были предложены Дейкстрой. В 1965 была опубликована первая статья, где он выдвигал идею семафоров. Что подвигло его на это? Стремление избежать активного ожидания. Активное ожидание приводит к непроизводительным тратам процессорного времени. Процесс циклится проверяя какую-то переменную, тратит на это выделенное ему процессорное время, фактически квант, соответственно пока другой процесс не выйдет из своего критического участка. Крайне неэффективное использование процессорного времени. И тогда Дейкстра предложил новое решение, которое и назвал семафором. В общем-то семафор не очень похож на этот семафор (который красный-жёлтый-зелёный). Скорее он похож на турникет, который толкает тот, кто выходит. То есть войти можно только если кто-то выходит. Мы будем использовать обозначения, которые предложил Дейкстра. Семафор - это неотрицательная, защищённая переменная, на которой определены две неделимые операции: P(s) - пропустить ("p" - первая буква аналогичного слова в датском) и V(s) - освободить (аналогично, первая буква). Если семафор может принимать два значения 0 или 1, то такой семафор называется бинарным.

P(s) - декрементирует s:
s = s - 1, если s > 0
если s = 0, то декремент невозможен и процесс блокируется на s до тех пор, пока декремент не станет возможен.

V(s) - инкрементирует s:
s = s + 1
То есть освобождение заблокированного процесса, поскольку s становится > 0.

Заблокировать процесс и разблокировать процесс можно только на уровне ядра. То есть P(s) и V(s) - системные вызовы, которые переводят систему в режим ядра. В режиме ядра процесс будет заблокирован и когда это станет возможно V(s) переведёт систему в режим ядра и выполняя эту команду, система разблокирует первый процесс из очереди семафора. Сразу же здесь нужно сказать, что любой переход в режим ядра это дополнительные расходы, это переключение контекста. Мы избавились от активного ожидания, но заплатили за это переходом в режим ядра. У всех альтернативных решений в программировании всегда есть своя цена. Понятно, что P(s) и V(s) это макро-команды, это большие действия системы, в основе которых лежит test-and-set. Пишем простейшее взаимоисключение с помощью семафоров:

s: semaphore
  
// p1
while (1) {    
    ...
    P(s);
    CR1:
    V(S)
    PR1;
    ...
}  

// p2
while (1) {    
    ...
    P(s);
    CR2:
    V(S)
    PR2;
    ...
}

// начальные установки
s = 1;
parbegin
   p1; p2;
parend

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

Задача Дейкстры "Производство-потребление"

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

se - семафор, который показывает, что буфер пуст (empty)      
sf - семафор, который показывает, что буфер полон (fool)        
sb - бинарный семафор.
  
// consumer
while (1) {    
    P(sf);
    P(sb);
    N = N - 1; // взять из буфера
    V(sb);
    V(sf);
    // вывести значение
    ...
}  

// produser
while (1) {    
    P(se);
    P(sb);
    N = N + 1; // добавить в буфер
    V(sb);
    V(sf);
    ...
}

// начальные установки
se = N; // кол-во пустых ячеек = равно размеру буфера
sf = 0; // кол-во заполненных
sb = 1; // позволяет выполнять действия не блокируя... **(Не слышно 56:10)**

Produser может положить в буфер единицу информации, если есть свободная ячейка. Если свободных нет, то producer будет блокирован на семафоре empty до тех пор пока consumer не освободит хотя бы одну ячейку. P(se) - consumer (producer же должен быть 57:20) может декрементировать семафор, если он не равен 0, то есть если если есть пустые ячейки. Иначе он будет блокирован. Соответственно бинарный семафор защищает разделяемую переменную N. После того как produser смог положить в буфер единицу информации он инкрементирует семафор full.
Consumer может взять единицу информации из буфера, если семафор full не равен 0, то есть если есть заполненные ячейки. Бинарный семафор защищает переменную. Освободив ячейку буфера, потребитель инкрементирует семафор empty, то есть увеличивает кол-во пустых ячеек, тем самым он может ... (Не слышно 59:05). Это очень важное решение и на третьей ЛР по юникс будем его писать.

Множественные семафоры

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

Обедающие философы

За круглым столом сидят 5 философов. Перед каждым из них тарелка, а справа и слева по одному прибору (для приёма пищи необходимо два прибора) (надо вставить картинку). Жизнь философа проста: он какое-то время размышляет, потом пытается поесть. Понятно, что приборы являются ресурсами. На самом деле существует три способа действия философа:

  1. Каждый пытается одновременно взять обе вилки. Если удаётся взять приборы, философ некоторое время ест, а потом одновременно кладёт оба прибора.
  2. Философ берёт правый прибор и удерживая его пытается взять левый.
  3. Философ берёт правый, пытается взять левый. Если не удаётся - кладёт правый.

Это модель трёх негативных ситуаций в системе:

  1. Модель бесконечного откладывания. Сколько философов умрёт от голода? Рязанова заявляет, что один и приводит простой пример - у одному из философов постоянно не достаётся, то правого, то левого.
  2. Тупиковая ситуация. Если все философы взяли по правому прибору.
  3. Захват и освобождение одних и тех же ресурсов.

Пишем код, который как раз демонстрирует св-во множественных семафоров:

forks: array[1..5] of semaphore;
left, right: 1...5;

//p1 - первый философ
left = (i + 1) mod 5;
right = i mod 5;
while(1) {
    /*размышляет*/
    p(forks[left], forks[right]); // неделимой операцией изменяется несколько семафоров
    /*ест*/
    v(forks[left], forks[right]);
}
...

//p5 - пятый
left = 4;
right = 5;
while (1) {
    /*размышляет*/
    p(forks[left], forks[right]);
    /*ест*/
    v(forks[left], forks[right]);
}
...

Понятно, что код у каждого философа аналогичный. Это первый случай - берут сразу по два прибора. Можно с mod, можно без mod.

Mutex

Семафоры привели к идее множественным семафором. Но использование семафоров всё равно черевато появлением сложно отлавливаемых тупиков.
Mutex (mutual exclusion) - это так же средство предоставляемое системой - системный вызов. О сравнении семафоров и мьютексов можно много говорить, есть такой материал "семафоры против мьютексов". Фактически мьютекс представляет из себя (ближе всего) бинарный семафор, но есть важнейшие отличия:

  1. У мьютекса есть понятие владельца. Владельцем является процесс, захвативший мьютекс. И только владелец может освободить мьютекс. У семафора же нет владельца. Для семафора возможна следующая запись: (у меня её нет). Захватывает семафор один процесс, а освобождает совсем другой. Это самая главное различие.
  2. Мьютексы предоставляют так называемую инверсию приоритетов безопасности. Мьютекс знает своего владельца и если на мьютексе блокируется другой более приоритетный процесс, то на самом деле приоритет процесса, захватившего мьютекс, повышается. То есть невозможно перехватить мьютекс.
  3. Процесс, захвативший мьютекс не может быть случайно удалён, завершён. А захвативший семафор может.

На самом деле все примитивы (в разных системах это могут быть разные название) можно назвать двумя словами: lock и unlock. Но это не касается семафоров!!! Семафоры это особенный договор. Всё касается средств близких к мьютексам. Это самое общее название. В зависимости от системы могут быть другие термины (wait-post, wait-signal).

Мониторы

Мониторы являются более высокоуровневыми средствами чем раннее перечисленные примитивы.