Семафор (Операционные Системы)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 11:30, 8 октября 2016.

Семафоры — одно из старейших средств разделения доступа к критическим ресурсам параллельно работающих процессов. Семафоры были введены в эксплуатацию Эдсгером Дейкстра еще в 1965 году. Алгоритм использования семафоров выглядит так:

подпись

Эдсгер Вибе Дейкстра определил две операции над семафорами: P и V. Операция P блокирует семафор, операция V — деблокирует семафор. Более точно, операции P и V определены следующим образом: Операция P проверяет, что семафор открыт. Если семафор открыт, операция закрывает семафор и завершается. Операция проверки и открытия является атомарной, то есть ни один другой процесс не может наблюдать ситуации, когда семафор проверен, но ещё не закрыт. Если на момент проверки семафор уже закрыт, операция P приостановит процесс до тех пор, пока некоторый другой процесс не откроет семафор. После того, как некоторый процесс открыл семафор, система выбирает из множества процессов, ожидающих открытия семафора, какой-то один и разблокирует его. Операция V разблокирует семафор. Эта операция никогда не приостанавливает выполнение процесса. [1].

Семафор - средство управления процессами

Семафор - это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций wait и signal и операции инициализации init. Двоичные семафоры могут принимать только значения 0 и 1. Семафоры со счетчиками могут принимать неотрицательные целые значения.

Операция wait(s) над семафором s состоит в следующем:

если s > 0 то s:=s-1 иначе (ожидать на s)
а операция signal(s) заключается в том, что:
если (имеются процессы, которые ожидают на s)
то (разрешить одному из них продолжить работу)
иначе s:=s+1

Операции являются неделимыми. Критические участки процессов обрамляются операциями wait(s) и signal(s). Если одновременно несколько процессов попытаются выполнить операцию wait(s), то это будет разрешено только одному из них, а остальным придется ждать.

Семафоры со счетчиками используются, если некоторые ресурс выделяется из множества идентичных ресурсов. При инициализации такого семафора в его счетчике указывается число элементов множества. Каждая операция wait(s) уменьшает значения счетчика семафора s на 1, показывая, что некоторому процессу выделен один ресурс из множества. Каждая операция signal(s) увеличивает значение счетчика на 1, показывая, что процесс возвратил ресурс во множество. Если операция wait(s) выполняется, когда в счетчике содержится нуль (больше нет ресурсов), то соответствующий процесс ожидает, пока во множество не будет возвращен освободившийся ресурс, то есть пока не будет выполнена операция signal. [2].

Пример

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

 
using System;
using System.Threading;
 
namespace SemaphoreApp
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 1; i < 6; i++)
            {
                Reader reader = new Reader(i);
            }

            Console.ReadLine();
        }
    }

    class Reader
    {
        // создаем семафор
        static Semaphore sem = new Semaphore(3, 3);
        Thread myThread;
        int count = 3;// счетчик чтения
         
        public Reader(int i)
        {
            myThread = new Thread(Read);
            myThread.Name = "Читатель " + i.ToString();
            myThread.Start();
        }
 
        public void Read()
        {
            while (count > 0)
            {
                sem.WaitOne();
 
                Console.WriteLine("{0} входит в библиотеку", Thread.CurrentThread.Name);
 
                Console.WriteLine("{0} читает", Thread.CurrentThread.Name);
                Thread.Sleep(1000);
 
                Console.WriteLine("{0} покидает библиотеку", Thread.CurrentThread.Name);
 
                sem.Release();
 
                count--;
                Thread.Sleep(1000);
            }
        }
    }
}

В данной программе читатель представлен классом Reader. Он инкапсулирует всю функциональность, связанную с потоками, через переменную Thread myThread.

Для создания семафора используется класс Semaphore: static Semaphore sem = new Semaphore(3, 3);. Его конструктор принимает два параметра: первый указывает, какому числу объектов изначально будет доступен семафор, а второй параметр указывает, какой максимальное число объектов будет использовать данный семафор. В данном случае у нас только три читателя могут одновременно находиться в библиотеке, поэтому максимальное число равно 3.

Основной функционал сосредоточен в методе Read, который и выполняется в потоке. В начале для ожидания получения семафора используется метод sem.WaitOne(). После того, как в семафоре освободится место, данный поток заполняет свободное место и начинает выполнять все дальнейшие действия. После окончания чтения мы высвобождаем семафор с помощью метода sem.Release(). После этого в семафоре освобождается одно место, которое заполняет другой поток.

А в методе Main остается только создать читателей, которые запускают соответствующие потоки.

Также, достаточно интересно представлен принцип работы семафора в публикации с сайта "ITnan" . [3].

Системные вызовы Unix/Linux

В ОС Unix/Linux механизм семафоров обслуживается тремя системными вызовами: semget, semctl и semop.

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

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

Системный вызов semop выполняет прикладные семафорные операции: аналоги P- и V-операций, а также проверки состояния семафора.

Семафоры в Unix/Linux не имеют внешних имен. При получении идентификатора семафора процесс пользуется числовым ключом. Разработчики несвязанных процессов могут договориться об общем значении ключа, который они будут использовать, но у них нет гарантии в том, что это же значение ключа не будет использовано кем-то еще. Гарантированно уникальный массив семафоров можно создать с использованием ключа IPC_PRIVATE, но такой ключ не может быть внешним. Поэтому семафоры используются, как правило, родственными процессами, которые имеют возможность передавать друг другу идентификаторы семафоров, например, через наследуемые ресурсы или через параметры вызова дочерней программы. [4].

Алгоритмы

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

Выделение буфера

Обратимся к алгоритму getblk. Алгоритм работает с тремя структурами данных: заголовком буфера, хеш-очередью буферов и списком свободных буферов. Ядро связывает семафор со всеми экземплярами каждой структуры. Другими словами, если у ядра имеются в распоряжении 200 буферов, заголовок каждого из них включает в себя семафор, используемый для захвата буфера; когда процесс выполняет над семафором операцию P, другие процессы, тоже пожелавшие захватить буфер, приостанавливаются до тех пор, пока первый процесс не исполнит операцию V. У каждой хеш-очереди буферов также имеется семафор, блокирующий доступ к очереди. В однопроцессорной системе блокировка хеш-очереди не нужна, ибо процесс никогда не переходит в состояние приостановки, оставляя очередь в несогласованном (неупорядоченном) виде. В многопроцессорной системе, тем не менее, возможны ситуации, когда с одной и той же хеш-очередью работают два процесса; в каждый момент времени семафор открывает доступ к очереди только для одного процесса. По тем же причинам и список свободных буферов нуждается в семафоре для защиты содержащейся в нем информации от искажения.

  
 алгоритм getblk           /* многопроцессорная версия */   
     входная информация:  номер файловой системы,
          номер блока                           
     выходная информация: захваченный буфер, предназначенный для обработки содержимого блока           
     {                                                          
        выполнять (пока буфер не будет обнаружен)               
        {                                                       
           P(семафор хеш-очереди);                              

           если (блок находится в хеш-очереди)                  
           {                                                    
              если (операция CP(семафор буфера) завершается неудачно)       /* буфер занят */                  
              {                                                 
                 V(семафор хеш-очереди);                        

                 P(семафор буфера);      /* приостановка до момента освобождения */                    
                 если (операция CP(семафор хеш-очереди) завершается неудачно)                                
                 {                                              
                    V(семафор буфера);                          

                    продолжить;     /* выход в цикл "выполнять" */                         
                 }                                              
                 в противном случае если (номер устройства или номер блока изменились)                       
                 {                                              
                    V(семафор буфера);                          

                    V(семафор хеш-очереди);                     
                 }                                              
              }                                                 
              выполнять (пока операция CP(семафор списка свободных буферов) не завершится успешно) ;    /* "кольцевой цикл" */                    

              пометить буфер занятым;                           

              убрать буфер из списка свободных буферов;         

              V(семафор списка свободных буферов);              

              V(семафор хеш-очереди);                           

              вернуть буфер;                                    
           }                                                    
           в противном случае   /* буфер отсутствует в хеш-очереди */                             
           /* здесь начинается выполнение оставшейся части алгоритма */                                                  
        }                                                       
     }

Здесь показана первая часть алгоритма getblk, реализованная в многопроцессорной системе с использованием семафоров. Просматривая буферный кеш в поисках указанного блока, ядро с помощью операции P захватывает семафор, принадлежащий хеш-очереди. Если над семафором уже кем-то произведена операция данного типа, текущий процесс приостанавливается до тех пор, пока процесс, захвативший семафор, не освободит его, выполнив операцию V. Когда текущий процесс получает право исключительного контроля над хеш-очередью, он приступает к поиску подходящего буфера. Предположим, что буфер находится в хеш-очереди. Ядро (процесс A) пытается захватить буфер, но если оно использует операцию P и если буфер уже захвачен, ядру придется приостановить свою работу, оставив хеш-очередь заблокированной и не допуская таким образом обращений к ней со стороны других процессов, даже если последние ведут поиск незахваченных буферов. Пусть вместо этого процесс A захватывает буфер, используя операцию CP; если операция завершается успешно, буфер становится открытым для процесса. Процесс A захватывает семафор, принадлежащий списку свободных буферов, выполняя операцию CP, поскольку семафор захватывается на непродолжительное время и, следовательно, приостанавливать свою работу, выполняя операцию P, процесс просто не имеет возможности. Ядро убирает буфер из списка свободных буферов, снимает блокировку со списка и с хеш-очереди и возвращает захваченный буфер. Предположим, что операция CP над буфером завершилась неудачно из-за того, что семафор, принадлежащий буферу, оказался захваченным. Процесс A освобождает семафор, связанный с хеш-очередью, и приостанавливается, пытаясь выполнить операцию P над семафором буфера. Операция P над семафором будет выполняться, несмотря на то, что операция CP уже потерпела неудачу. По завершении выполнения операции процесс A получает власть над буфером. Так как в оставшейся части алгоритма предполагается, что буфер и хеш-очередь захвачены, процесс A теперь пытается захватить хеш-очередь. Поскольку очередность захвата здесь (сначала семафор буфера, потом семафор очереди) обратна вышеуказанной очередности, над семафором выполняется операция CP. Если попытка захвата заканчивается неудачей, имеет место обычная обработка, требующаяся по ходу задачи. Но если захват удается, ядро не может быть уверено в том, что захвачен корректный буфер, поскольку содержимое буфера могло быть ранее изменено другим процессом, обнаружившим буфер в списке свободных буферов и захватившим на время его семафор. Процесс A, ожидая освобождения семафора, не имеет ни малейшего представления о том, является ли интересующий его буфер тем буфером, который ему нужен, и поэтому прежде всего он должен убедиться в правильности содержимого буфера; если проверка дает отрицательный результат, алгоритм запускается сначала. Если содержимое буфера корректно, процесс A завершает выполнение алгоритма.

Wait

Во время выполнения системной функции wait процесс приостанавливает свою работу до момента завершения выполнения своего потомка. В многопроцессорной системе перед процессом встает задача не упустить при выполнении алгоритма wait потомка, прекратившего существование с помощью функции exit; если, например, в то время, пока на одном процессоре процесс-родитель запускает функцию wait, на другом процессоре его потомок завершил свою работу, родителю нет необходимости приостанавливать свое выполнение в ожидании завершения второго потомка. В каждой записи таблицы процессов имеется семафор, именуемый zombie_semaphore и имеющий в начале нулевое значение. Этот семафор используется при организации взаимодействия wait/exit (Рисунок 12.15).

 
     многопроцессорная версия алгоритма wait                    
     {                                                          
        /* цикл */                              
         {                                                      
             перебор всех процессов-потомков:                   

             если (потомок находится в состоянии "прекращения существования")                                   

                  вернуть управление;                           

             P(zombie_semaphore);   /* начальное значение - 0 */
         }                                                      
     }

Когда потомок завершает работу, он выполняет над семафором своего родителя операцию V, выводя родителя из состояния приостановки, если тот перешел в него во время исполнения функции wait. Если потомок завершился раньше, чем родитель запустил функцию wait, этот факт будет обнаружен родителем, который тут же выйдет из состояния ожидания. Если оба процесса исполняют функции exit и wait параллельно, но потомок исполняет функцию exit уже после того, как родитель проверил его статус, операция V, выполненная потомком, воспрепятствует переходу родителя в состояние приостановки. В худшем случае процесс-родитель просто повторяет цикл лишний раз.

Драйверы

В многопроцессорной реализации вычислительной системы на базе компьютеров AT&T 3B20 семафоры в структуру загрузочного кода драйверов не включаются, а операции типа P и V выполняются в точках входа в каждый драйвер. Интерфейс, реализуемый драйверами устройств, характеризуется очень небольшим числом точек входа (на практике их около 20). Защита драйверов осуществляется на уровне точек входа в них:

   P(семафор драйвера);

    открыть (драйвер);

    V(семафор драйвера);

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

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

Фиктивные процессы

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

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

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

Проблемы семафоров

Во-первых, можно написать программу с «утечкой семафора», вызвав enter() и забыв вызвать leave(). Реже встречаются ошибки, когда дважды вызывается leave().

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

// Поток 1:
semaphore1.enter();
semaphore2.enter();
// ...
semaphore2.leave();
semaphore1.leave();

// Поток 2:
semaphore2.enter();
semaphore1.enter();
// ...
semaphore1.leave();
semaphore2.leave();

Примечания

  1. Семафор [Электронный ресурс] : Материал из https://ejudge.ru/: — Режим доступа: https://webcache.googleusercontent.com/search?q=cache:4Q8sJgYL_ugJ:https://ejudge.ru/study/3sem/sem14.pdf+&cd=8&hl=ru&ct=clnk&gl=ru
  2. Семафор [Электронный ресурс] : Материал из http://www.ccas.ru/: — Режим доступа: http://www.ccas.ru/paral/prog/semaphore.html
  3. Семафор [Электронный ресурс] : Материал из https://itnan.ru/: — Режим доступа: https://itnan.ru/post.php?c=1&p=261273
  4. Семафор [Электронный ресурс] : Материал из http://life-prog.ru/: — Режим доступа: http://life-prog.ru/view_linux.php?id=23
  5. Семафор [Электронный ресурс] : Материал из http://citforum.ru/: — Режим доступа: http://citforum.ru/operating_systems/bach/glava_106.shtml
  6. Семафор [Электронный ресурс] : Материал из Википедии — свободной энциклопедии: — Режим доступа: https://ru.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D0%B8%D0%BC%D0%BD%D0%B0%D1%8F_%D0%B1%D0%BB%D0%BE%D0%BA%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0