Единое окно доступа к образовательным ресурсам

Операционные системы. Теория и практика: Учебное пособие

Голосов: 2

В учебном пособии изложены особенности функционирования, назначения и архитектуры современных операционных систем (ОС). В работе отражены: понятие и эволюция операционных систем, архитектурные особенности и классификация ОС по различным критериям, особенности управления процессами и памятью, основы организации файловых систем и некоторые их конкретные примеры, рассмотрены консолидированные серверные системы хранения данных большого объема RAID. Для получения практических навыков работе в операционных системах (на примере систем семейства Unix-Linux) учебное пособие освещает вопросы разработки программных проектов с использованием специализированных утилит, а также по управлению процессами и потоками и средствами их синхронизации. Предназначено для студентов, обучающихся по направлению 230100 Информатика и вычислительная техника.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    поток блокируется, «ожидая на семафоре», при S = 0. При выполнении
операции V(S) происходит пробуждение одного из потоков, ожидающих
на семафоре S, а если таковых нет, то значение семафора увеличивается
на 1 (как можно заметить, по сути – операции P и V аналогичны функ-
циям POST и WAIT). Как следует из вышесказанного, при входе в кри-
тическую секцию поток должен выполнять операцию P(S), а при выходе
из критической секции – операцию V(S).
                                           Запрос к ресурсу D




                                       Ресурс
       Неделимая операция            свободен?
       «поверка-установка»            F(D)=1?            Нет, занят


                                             Да, свободен        WAIT(D)
                                   Занять ресурс
                                      F(D):=0
                                                                 Процесс
                                                              блокируется до
                                                             освобождения D
                                Критическая секция
                               (работа с ресурсом D)



                                Освободить ресурс
                                     F(D):=1




                                     POST(D)


                             Снятие блокировки со всех
                              процессов, ожидающих
                                     ресурс D
    Рисунок 19 – Работа в критической секции с использованием системных
                      функций WAIT(D) и POST(D)
     В простом случае, когда семафор работает в режиме 2-х состояний
(S > 0 и S = 0), его алгоритм работы полностью совпадает с алгоритмом
мьютекса, а S выполняет роль блокирующей переменной.
     Рассмотрим использование семафоров на классическом примере
взаимодействия двух процессов, выполняющихся в режиме мультипро-
граммирования, один из процессов пишет данные в буферный пул, а
другой считывает их из буферного пула. Пусть буферный пул состоит из
N буферов, каждый из которых может содержать одну запись. Процесс
                                     71


«писатель» должен приостанавливаться, когда все буфера оказываются
занятыми, и активизироваться при освобождении хотя бы одного буфе-
ра. Напротив, процесс «читатель» приостанавливается, когда все буфе-
ры пусты, и активизируется при появлении хотя бы одной записи. Вве-
дем следующие семафоры:
      e – число пустых буферов («e» – empty);
      f – число заполненных буферов («f» – full);
      b – двоичный семафор, используемый для обеспечения взаимно-
     го исключения.
     Операции с буфером (запись, считывание) являются критическими
секциями. Процессы могут быть описаны следующим образом:
    // Глобальные переменные
    #define N 256
    int e = N, f = 0, b = 1;
    void Writer ()
    {
      while(1)
      {
             PrepareNextRecord(); /* подготовка новой записи */
             P(e); /* Уменьшить число свободных буферов, если они есть */
             /* в противном случае ждать, пока они освободятся */
             P(b);         /* Вход в критическую секцию */
             AddToBuffer(); /* Добавить новую запись в буфер */
             V(b);         /* Выход из критической секции */
             V(f);        /* Увеличить число занятых буферов */
      }
    }
    void Reader ()
    {
      while(1)
      {
             P(f);          /* Уменьшить число занятых буферов, если они есть */
             /* в противном случае ждать, пока они появятся */
             P(b);           /* Вход в критическую секцию        */
             GetFromBuffer(); /* Взять запись из буфера          */
             V(b);           /* Выход из критической секции      */
             V(e);           /* Увеличить число свободных буферов */
             ProcessRecord(); /* Обработать запись                */
      }
    }
    Достоинства использования операций на семафоре:
    1. Пассивное ожидание (постановка в очередь и автоматическая
выдача ресурсов).
    2. Возможность управления группой однородных ресурсов.


                                       72


     К недостаткам использования семафоров относят то, что некор-
ректное использование операций на семафоре может привести к нару-
шению работоспособности параллельных систем.
     Действительно, если в рассмотренном примере переставить места-
ми операции P(e) и P(b) в функции «писатель», то при некотором стече-
нии обстоятельств эти два процесса могут взаимно заблокировать друг
друга. Так, пусть «писатель» первым войдет в критическую секцию и
обнаружит отсутствие свободных буферов; он начнет ждать, когда «чи-
татель» возьмет очередную запись из буфера, но «читатель» не сможет
этого сделать, так как для этого необходимо войти в критическую сек-
цию, вход в которую заблокирован процессом «писатель».
     Мониторы. В связи с тем, что использование семафоров требует
особой осторожности (одна незначительная ошибка может привести к
останову системы), для облегчения корректного функционирования
программ было предложено высокоуровневое средство синхронизации,
называемое монитором. Мониторы представляют собой тип данных,
обладающий собственными переменными, определяющими его состоя-
ние. Значения этих переменных извне могут быть изменены только с
помощью вызова функций-методов монитора. Функции-методы могут
использовать в работе только данные, находящиеся внутри монитора, и
свои параметры. Важной особенностью мониторов является то, что в
любой момент времени только один процесс может быть активен, т.е.
находиться в состоянии готовность или исполнение, внутри данного
монитора. Вот пример описания монитора:
     monitor monitor_name
     {
           описание переменных;
           void m1(...){... }
           void m2(...){... }
           ...
           void mn(...){... }
           { блок инициализации внутренних   переменных;}
     }
    Однако одних только взаимоисключений недостаточно для того,
чтобы в полном объеме реализовать решение задач, возникающих при
взаимодействии процессов. Необходимы средства организации очеред-
ности процессов, подобно семафорам f(full) и e(empty) в примере.
    Для этого в мониторах было введено понятие условных перемен-
ных, над которыми можно совершать две операции wait и signal, отчасти
похожие на операции P и V над семафорами.
    monitor ProducerConsumer
     {
            condition full, empty;
            int count;
                                     73


           void put()
           {      if(count == N) full.wait;
                  put_item;
                  count += 1;
                  if(count == 1) empty.signal;
           }
           void get()
           {      if (count == 0) empty.wait;
                  get_item();
                  count -= 1;
                  if(count == N-1) full.signal;
           }
     }

     Producer: while(1)
     {     produce_item;
           ProducerConsumer.put();
     }

     Consumer: while(1)
     {     ProducerConsumer.get();
           consume_item;
     }
     Функция монитора выполняет операцию wait над какой-либо
условной переменной. При этом процесс, выполнивший операцию wait,
блокируется, становится неактивным, и другой процесс получает воз-
можность войти в монитор.
     Когда ожидаемое событие происходит, другой процесс внутри
функции совершает операцию signal над той же самой условной пере-
менной. Это приводит к пробуждению ранее заблокированного процес-
са, и он становится активным.
     Отличительной особенностью мониторов является то, что исклю-
чение входа нескольких процессов в монитор реализуется не програм-
мистом, а компилятором, что делает ошибки менее вероятными. Реали-
зация мониторов требует использования специальных языков програм-
мирования и компиляторов для них (например, «параллельный Евклид»,
«параллельный Паскаль», Java).
     Следует отметить, что эмуляция семафоров значительно проще
эмуляции мониторов – в отличие от семафоров Дейкстры, условные пе-
ременные мониторов не запоминают предысторию, поэтому операция
signal всегда должна выполняться после операции wait. Если операция
signal выполняется над условной переменной, с которой не связано ни
одного заблокированного процесса, то информация о произошедшем
событии будет утеряна, и выполнение операции wait всегда будет при-
водить к блокированию процесса.
                                        74


     Сигналы. Вообще, сигнал – это некоторое значимое событие
(например, прерывание), источником которого может быть ОС или иная
составляющая вычислительной системы. Сигналы вызывают прерыва-
ние процесса, выполнение заранее предусмотренных действий.
     Сигналы могут вырабатываться как результат работы самого про-
цесса (т.е. вырабатываться синхронно), а могут быть направлены про-
цессу другим процессом (т.е. вырабатываться асинхронно). Синхронные
сигналы чаще всего приходят от системы прерываний процессора и сви-
детельствуют о действиях процесса, блокируемых аппаратурой, напри-
мер деление на нуль, ошибка адресации, нарушение защиты памяти и
т.д. Примером асинхронного сигнала является сигнал с терминала
(например, сигнал об оперативном снятии процесса с выполнения с по-
мощью некоторой нажатой комбинации клавиш –Ctrl + C, Ctrl + Break),
в результате чего ОС вырабатывает сигнал и направляет его активному
процессу.
     Сигналы обеспечивают логическую связь между процессами, а
также между процессами и пользователями (терминалами). Поскольку
посылка сигнала предусматривает знание идентификатора процесса, то
взаимодействие посредством сигналов возможно только между род-
ственными процессами, которые могут получить данные об идентифи-
каторах друг друга.
     Следует отметить, что в распределенных системах, состоящих из
нескольких процессоров, каждый из которых имеет собственную опера-
тивную память, блокирующие переменные, семафоры, сигналы и другие
аналогичные средства, основанные на разделяемой памяти, оказываются
непригодными. В таких системах синхронизация может быть реализова-
на только посредством обмена сообщениями, рассмотренными ниже в
п. 3.3.6.
    3.3.5   Проблемы синхронизации
     В п. 3.3.4 рассмотрен ряд механизмов ОС, используемых для син-
хронизации параллельно действующих процессов. Однако, в некоторых
случаях, при конкуренции нескольких процессов за обладание конеч-
ным числом ресурсов, может возникнуть ситуация, когда запрашивае-
мый процессом ресурс недоступен, и ОС переводит данный процесс в
состояние ожидания. В то же время, если этот же ресурс удерживается
другим ожидающим процессом, то первый процесс не сможет сменить
свое состояние. Подобная ситуация называется взаимной блокировкой,
дедлоком (англ. deadlocks), клинчем (англ. clinch), или тупиком. Напри-
мер, тупик возникнет при перестановке местами операций Р(е) и Р(b) в
примере с процессами «читатель» и «писатель», рассмотренном выше. В
этом случае ни один из этих потоков не сможет завершить начатую ра-
                                  75


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


                                 76


     В качестве необходимых условий возникновения тупиков называют
следующие четыре:
     1) Условие взаимоисключения (англ. Mutual exclusion). Одновре-
менно использовать ресурс может только один процесс.
     2) Условие ожидания ресурсов (англ. Hold and wait). Процессы
удерживают ресурсы, уже выделенные им, и могут запрашивать другие
ресурсы.
     3) Условие «неперераспределяемости» (англ. No preemtion). Ресурс,
выделенный ранее, не может быть принудительно забран у процесса до
его завершения. Освобождены они могут быть только процессом, кото-
рый их удерживает.
     4) Условие кругового ожидания (англ. Circular wait). Существует
кольцевая цепь процессов, в которой каждый процесс ждет доступа к
ресурсу, удерживаемому другим процессом цепи.
     Соответственно, решить проблему возникновения тупиков можно
путем избегания описанных выше ситуаций 2-4 (ситуация взаимоис-
ключения – объективна):
      ситуацию ожидания дополнительных ресурсов можно нарушить,
если потребовать, чтобы процессы запрашивали сразу все ресурсы од-
новременно (очевидные недостатки – снижение уровня мультипрограм-
мирования и нерациональное использование ресурсов);
      ситуацию «неперераспределяемости» можно нарушить, если по-
требовать, чтобы процесс, который не получил дополнительных ресур-
сов, сам освобождал удерживаемые;
      ситуацию кругового ожидания можно предотвратить, если про-
цессы запрашивают ресурсы в заранее определенном порядке, то есть
ресурсы имеют уникальные упорядоченные номера, которые распреде-
ляются в соответствии с некоторым планом (планирование распределе-
ния ресурсов).
     Восстановление системы после тупиков. При возникновении ту-
пиковой ситуации не обязательно снимать с выполнения все заблокиро-
ванные процессы, а можно:
      снять только часть из них, при этом освобождая ресурсы, ожи-
даемые остальными процессами;
      вернуть некоторые процессы в область «свопинга»;
      совершить «откат» некоторых процессов до некоторой кон-
трольной точки (т.е. места, где возможен тупик), в которой запоминает-
ся вся информация, необходимая для восстановления выполнения про-
граммы с данного места.
     Игнорирование. Простейший подход – не замечать проблему ту-
пиков. Для того чтобы принять такое решение, необходимо оценить ве-
                                  77


роятность возникновения взаимоблокировки и сравнить ее с вероятно-
стью ущерба от других отказов аппаратного и программного обеспече-
ния. Подход большинства современных ОС (Unix, Windows и др.) состо-
ит в том, чтобы игнорировать данную проблему в предположении, что
маловероятный случайный тупик предпочтительнее, чем внедрение
сложных и дорогостоящих средств борьбы с тупиками, и жертвовать
производительностью системы или удобством пользователей (например,
ограничивать пользователей в числе процессов, открытых файлов и т.п.)
не стоит.
    3.3.6   Механизмы межпроцессного взаимодействия
     Помимо решения задачи синхронизации процессов и потоков, в ОС
требуется обеспечение и обмена данными между ними. Если речь идет о
необходимости обмена данными между потоками одного процесса, то
решение этой задачи не представляет никакой сложности, т.к. они име-
ют общее адресное пространство и файлы, и получают беспрепятствен-
ный доступ к данным друг друга. Другое дело – обмен данными пото-
ков, выполняющихся в рамках разных процессов. В этом случае обмену
препятствуют развитые средства ОС по защите процессов друг от друга,
находящихся к тому же в разных адресных пространствах.
     Операционная система имеет доступ ко всем областям памяти, по-
этому она может играть роль посредника в информационном обмене по-
токов: при возникновении необходимости в обмене данными поток об-
ращается с запросом к ОС, по которому ОС, пользуясь своими привиле-
гиями, создает различные системные средства связи, такие, например,
как каналы, очереди сообщений или разделяемую память. Эти средства
(как и рассмотренные выше средства синхронизации процессов), отно-
сят к классу средств межпроцессного взаимодействия.
     Следует помнить, что многие из средств межпроцессного обмена
данными выполняют также и функции синхронизации: в том случае, ко-
гда данные для процесса-получателя отсутствуют, последний перево-
дится в состояние ожидания средствами ОС, а при поступлении данных
от процесса-отправителя процесс-получатель активизируется.
     Каналы. Один из методов взаимодействия между процессами по-
лучил название канал связи, конвейер или транспортер (англ. pipe) –
однонаправленный механизм передачи данных (неструктурированного
потока байтов) между процессами без необходимости создания файла на
диске. Канал представляет собой буфер в оперативной памяти, поддер-
живающий очередь байт согласно FIFO. Для программиста, использу-
ющего канал, этот буфер выглядит как безымянный файл, в который
можно писать и читать, осуществляя тем самым обмен данными.

                                 78


    Механизм каналов часто используется не только программистами,
но и обычными пользователями ОС для организации конвейера команд
в случае, когда выходные данные одной команды пользователя стано-
вятся входными данными для другой команды. Так, наиболее простой
вариант канала создает оболочка Unix между программами, запускае-
мыми из командной строки, разделенными символом «|». Например, ко-
мандная строка dmesg | less создает канал от программы dmesg, выводя-
щей отладочные сообщения ядра при загрузке к программе постранич-
ного просмотра less.
    Обычный канал получил развитие, результатом которого стало по-
явление именованного канала или именованного конвейера – зареги-
стрированного в системе канала (по сути – запись в каталоге файловой
системы), который разрешено использовать различным процессам или
потокам (не обязательно родственным). Реализуется это путем создания
одним, а чтения – другим процессом (потоком) файла типа FIFO с од-
ним и тем же указанным в процессах именем.
    Также можно создать канал с помощью, например, команд mknod
или mkfifo и настроить gzip на сжатие того, что туда попадает:
     mkfifo pipe
     gzip -9 -c < pipe > out
     Параллельно, в другом процессе можно выполнить:
     cat file > pipe,
     что приведѐт к сжатию передаваемых данных gzip-ом.
     Именованный канал существует в ОС и после завершения процесса,
поэтому после окончания использования он должен быть «отсоединен»
или удален. Следует иметь в виду, что именованные каналы используют
файловую систему только для хранения имени конвейера, а данные
между процессами передаются через буфер в оперативной памяти, как и
в случае обычного канала.
     Очереди сообщений. Механизм очередей сообщений (англ. queues)
в целом схож с механизмом каналов, но позволяет процессам и потокам
обмениваться структурированными сообщениями. При этом синхрони-
зация осуществляется по сообщениям, то есть процесс, пытающийся
прочитать сообщение, переводится в состояние ожидания в том случае,
если в очереди нет ни одного полного сообщения.
     Следует отметить, что в распределенных системах, состоящих из
нескольких процессоров и неразделяемых блоков памяти, использова-
ние таких средств синхронизации как блокирующие переменные, сема-
форы, сигналы является непригодным. В таких системах синхронизацию
следует реализовывать только посредством обмена сообщениями.


                                 79


     С помощью очередей можно из одной или нескольких задач неза-
висимым образом посылать сообщения некоторой задаче-приемнику.
При этом только процесс-приемник может читать и удалять сообщения
из очереди, а процессы-клиенты имеют право лишь помещать в очередь
свои сообщения. Таким образом, очередь работает только в одном
направлении, а если необходима двухсторонняя связь, то следует со-
здать две очереди.
     Очереди сообщений являются глобальными средствами коммуни-
каций для процессов ОС, как и именованные каналы, так как каждая
очередь имеет в пределах ОС уникальное имя. В ОС Unix в качестве та-
кого имени используется числовое значение – так называемый ключ.
Ключ является числовым аналогом имени файла, при использовании
одного и того же значения ключа процессы будут работать с одной и той
же очередью сообщений.
     Работа с очередями сообщений имеет ряд отличий от работы с ка-
налами:
     1) Очереди сообщений предоставляют возможность использовать
несколько дисциплин обработки сообщений (FIFO, LIFO, приоритетный
доступ, произвольный доступ).
     2) Если при чтении сообщения оно удаляется из конвейера, то при
чтении сообщения из очереди этого не происходит, и сообщение может
быть прочитано несколько раз.
     3) В очередях присутствуют не непосредственно сами сообщения, а
их адреса в памяти и размер. Эта информация размещается системой в
сегменте памяти, доступном для всех задач, общающихся с помощью
данной очереди. Каждый процесс, использующий очередь, должен
предварительно получить разрешение на доступ в общий сегмент памя-
ти с помощью системных запросов API, ибо очередь – это системный
механизм, и для работы с ним требуются системные ресурсы и, соответ-
ственно, обращение к самой ОС.
     Для наглядности, при обзоре механизмов реализации средств меж-
процессного взаимодействия здесь и далее будем использовать конкрет-
ные системные вызовы ОС Unix.
     Так, для работы с очередью сообщений процесс должен воспользо-
ваться системным вызовом msgget, указав в качестве параметра значе-
ние ключа. Если очередь с данным ключом в настоящий момент не ис-
пользуется ни одним процессом, то для нее резервируется область памя-
ти, а затем процессу возвращается идентификатор очереди, который, как
и дескриптор файла, имеет локальное для процесса значение. Если же
очередь уже используется, то процессу просто возвращается ее иденти-
фикатор.

                                 80



    
Яндекс цитирования Яндекс.Метрика