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

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

Голосов: 2

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
                                              Выполненные процессы
               Процессор




             Очередь новых задач
     Рисунок 12 – Схема обслуживания задач согласно дисциплине FCFS
     Такой алгоритм выбора процесса осуществляет невытесняющее
планирование. Процесс, получивший в свое распоряжение процессор,
занимает его до истечения текущего времени выполнения. После этого
для выполнения выбирается новый процесс из начала очереди. Преиму-
ществом алгоритма FCFS является легкость его реализации, недостат-
ками – среднее время ожидания и среднее полное время выполнения для
этого алгоритма существенно зависят от порядка расположения процес-
сов в очереди. Для подтверждения этого тезиса рассмотрим следующий
пример.
     Пусть в состоянии готовность находятся три процесса p0, p1 и p2,
время выполнения которых в условных единицах, соответственно, со-
ставляет t1вып = 13, t2вып = 4 и t3вып = 1 (рис. 13). Для простоты будем по-
лагать, что в выполнение процессов не вмешиваются операции типа
ввода-вывода, а временем переключения контекста можно пренебречь.
                   исполнение
   p0
                    готовность                     исполнение
   p1

                                готовность                       исполнение
   p2

    0                                         13            17       18   t
Рисунок 13 – Временная диаграмма выполнения процессов в порядке p0, p1 и p2

     Среднее время ожидания в данном случае можно рассчитать как
(0 + 13 + 17)/3 = 10 усл. ед. времени, среднее полное время выполнения
составит в этом случае (13 + 17 + 18)/3 = 16 усл. ед. времени.
     В то же время, если очередность этих процессов изменить на об-
ратную – p2, p1, p0, то временная диаграмма выполнения будет выглядеть
так, как представлено на рис. 14.



                                     61


 p0             готовность                  исполнение
                исполнение
 p1
          готовность
 p2
             исполнение
      0       1           5                                         18   t
Рисунок 14 – Временная диаграмма выполнения процессов в порядке p2, p1 и p0

В этом случае среднее время ожидания будет (5 + 1 + 0)/3 = 2 усл. ед.
времени, а среднее полное время выполнения будет (18 + 5 + 1)/3 = 8
усл. ед. времени.
     Все это означает, что при изменении очередности выполнения од-
них и тех же процессов среднее время ожидания уменьшилось в 5 раз, а
полное время выполнения – уменьшилось в 2 раза, что подтверждает
большую чувствительность алгоритма FCFS к изменению порядка оче-
редности выполнения процессов.
     Round Robin. Модификацией алгоритма FCFS является алгоритм,
получивший название Round Robin (детская карусель) или сокращенно
RR. Схематично обслуживание задач согласно алгоритму RR представ-
лено на рис. 15. По сути, это алгоритм FCFS, только реализованный в
режиме вытесняющего планирования (очередной процесс передается на
исполнение по таймеру по истечении определенного кванта времени).
                                       Выполненные задачи
                  Процессор




                    Очередь задач, готовых к         Новые задачи
                         исполнению
          Рисунок 15 – Схема обслуживания задач согласно дисциплине RR
    Можно представить себе все множество готовых процессов органи-
зованным циклически – процессы «сидят на карусели». Карусель враща-
                                       62


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



    готовность                готовность        готовность                готовность
    Процесс4                  Процесс 2         Процесс 3                 Процесс 1



                 исполнение                                  исполнение
                 Процесс 3                                   Процесс 2



                 Процессор                                   Процессор

                       а)                                      б)

                      Рисунок 16 – Процессы «на карусели»:
                  а – момент времени t1, б – момент времени t2
     На производительность алгоритма RR существенно влияет величи-
на кванта времени – при очень больших величинах кванта алгоритм RR
вырождается в алгоритм FCFS, при очень малых – создается иллюзия
того, что каждый из n процессов работает на собственном виртуальном
процессоре с производительностью ~ 1/n от производительности реаль-
ного процессора (конечно, если не принимать во внимание время пере-
ключения контекста).
     Shortest Job First. Если выбирать процесс не по порядку (как в
FCFS и RR), а основываясь на его минимальном времени непрерывного
использования процессора, то это позволит повысить производитель-
ность алгоритма планирования использования процессора. Описанный
алгоритм получил название «кратчайшая работа первой» (англ. Shortest
Job First, SJF).
     Основную сложность при реализации алгоритма SJF представляет
невозможность точно знать в каждом случае время исполнения очеред-
ного процесса.




                                           63


    3.3   Взаимодействие и синхронизация процессов и по-
          токов
    3.3.1 Независимые и взаимодействующие вычислительные про-
    цессы
    Основной особенностью мультипрограммных OC является то, что в
их среде параллельно развивается несколько (последовательных) вы-
числительных процессов. С точки зрения внешнего наблюдателя эти по-
следовательные вычислительные процессы выполняются одновременно
(«параллельно»). При этом под параллельными понимаются не только
процессы, одновременно развивающиеся на различных процессорах, ка-
налах и устройствах ввода-вывода, но и те последовательные процессы,
которые разделяют центральный процессор и в своем выполнении хотя
бы частично перекрываются во времени. Любая мультипрограммная ОС
вместе с параллельно выполняющимися процессами может быть логи-
чески представлена как совокупность последовательных вычислений,
которые, с одной стороны, состязаются за ресурсы, переходя из одного
состояния в другое, а с другой – действуют почти независимо один от
другого, но при этом образуя единую систему посредством установле-
ния разного рода связей между собой (путем пересылки сообщений и
синхронизирующих сигналов).
    Итак, параллельными называют такие последовательные вычисли-
тельные процессы, которые одновременно находятся в каком-нибудь ак-
тивном состоянии. Два параллельных процесса могут быть независимы-
ми (англ. independent processes) либо взаимодействующими (англ.
cooperating processes).
    Независимыми являются процессы, множества переменных кото-
рых не пересекаются. Под переменными в этом случае понимают файлы
данных, а также области оперативной памяти, сопоставленные проме-
жуточным и определенным в программе переменным. Независимые
процессы не влияют на результаты работы друг друга, так как не могут
изменять значения переменных друг у друга. Они могут только явиться
причиной в задержках исполнения друг друга, так как вынуждены раз-
делять ресурсы системы.
    Взаимодействующие процессы используют совместно некоторые
(общие) переменные, и выполнение одного процесса может повлиять на
выполнение другого. Следует отметить, что при рассмотрении вопросов
синхронизации вычислительных процессов (п. 3.3.2), из числа разделяе-
мых ими ресурсов исключаются центральный процессор и программы,
реализующие эти процессы, то есть с логической точки зрения каждому
процессу соответствуют свои процессор и программа, хотя в реальных
                                 64


системах обычно несколько процессов разделяют один процессор и од-
ну или несколько программ. Многие ресурсы вычислительной системы
могут совместно использоваться несколькими процессами, но в каждый
момент времени к разделяемому ресурсу может иметь доступ только
один процесс. Ресурсы, которые не допускают одновременного исполь-
зования несколькими процессами, называются критическими.
      3.3.2    Цели и средства синхронизации
     Синхронизация процессов – приведение двух или более процессов к
такому их протеканию, когда определенные стадии разных процессов
совершаются в определенном порядке, либо одновременно. Потребность
в синхронизации возникает только в мультипрограммной ОС и связана с
совместным использованием аппаратных и информационных ресурсов
вычислительной системы. Синхронизация 8 необходима в любых случа-
ях, когда параллельно протекающим процессам (потокам) необходимо
взаимодействовать – для исключения гонок и тупиков при обмене дан-
ными между потоками, разделении данных, при доступе к устройствам
ввода-вывода. Для ее организации используются средства межпроцесс-
ного взаимодействия (Inter Process Communications, IPC), что отражает
историческую первичность понятия «процесс» по отношению к поня-
тию «поток». Среди наиболее часто используемых средств синхрониза-
ции – сигналы, сообщения, семафоры и мьютексы.
     Выполнение процесса (потока) в мультипрограммной среде всегда
имеет асинхронный характер. Очень сложно с полной определенностью
сказать, на каком этапе выполнения будет находиться процесс в опреде-
ленный момент времени. Даже в однопрограммном режиме не всегда
можно точно оценить время выполнения задачи. Это время во многих
случаях существенно зависит от значения исходных данных, которые
влияют на количество циклов, направления разветвления программы,
время выполнения операций ввода-вывода и т.п. В связи с тем, что ис-
ходные данные в разные моменты запуска задачи могут быть разными,
то и время выполнения отдельных этапов и задачи в целом является
весьма неопределенной величиной.
     Еще более неопределенным является время выполнения программы
в мультипрограммной системе. Моменты прерывания потоков, время
нахождения их в очередях к разделяемым ресурсам, порядок выбора по-
токов для выполнения – все эти события являются результатом стечения
многих обстоятельств и могут быть интерпретированы как случайные. В
лучшем случае можно оценить вероятностные характеристики вычисли-


8 Все сказанное справедливо для синхронизации потоков, а если ОС не поддерживает потоки – то для
синхронизации процессов.
                                              65


тельного процесса, например, вероятность его завершения за данный
период времени.
     Учитывая вышеизложенное, можно сделать вывод, что потоки в
общем случае (когда программист не предпринял специальных мер по
их синхронизации) протекают независимо, асинхронно друг другу. Это
справедливо как по отношению к потокам одного процесса, выполняю-
щим общий программный код, так и по отношению к потокам разных
процессов, каждый из которых выполняет собственную программу.
     Для синхронизации потоков прикладных программ программист
может использовать как собственные средства и приемы синхрониза-
ции, так и средства ОС. Например, два потока одного прикладного про-
цесса могут координировать свою работу с помощью доступной для них
обоих глобальной логической переменной, которая устанавливается в
единицу при осуществлении некоторого события, например выработки
одним потоком данных, нужных для продолжения работы другого. Од-
нако во многих случаях более эффективными или даже единственно
возможными являются средства синхронизации, предоставляемые ОС в
форме системных вызовов. Так, потоки, принадлежащие разным про-
цессам, не имеют возможности вмешиваться каким-либо образом в ра-
боту друг друга. Без посредничества ОС они не могут приостановить
друг друга или оповестить о произошедшем событии.
     Средства синхронизации используются ОС не только для синхро-
низации прикладных процессов, но и для ее внутренних нужд. Обычно
разработчики ОС предоставляют в распоряжение прикладных и систем-
ных программистов широкий спектр средств синхронизации. Эти сред-
ства могут образовывать иерархию, когда на основе более простых
средств строятся более сложные, а также могут быть функционально
специализированными. Например, средства для синхронизации потоков
одного процесса, средства для синхронизации потоков разных процес-
сов при обмене данными и т.д.
    3.3.3   Пример необходимости синхронизации
    Пренебрежение вопросами синхронизации процессов, выполняю-
щихся в режиме мультипрограммирования, может привести к их непра-
вильной работе или даже к краху системы.
    Рассмотрим пример, демонстрирующий необходимость синхрони-
зации двух процессов, каждый из которых работает с некоторым общим
ресурсом – программой печати файлов (принт-сервером, рис. 17).
    Эта программа печатает по очереди содержимое файлов, имена ко-
торых последовательно в порядке поступления записывают в специаль-
ный общедоступный файл «заказов». Специальная переменная NEXT,
доступная всем процессам-клиентам, содержит номер первой свободной
                                 66


позиции для записи имени файла в файле «заказов». Процессы-клиенты
считывают значение этой переменной, определяя тем самым очередную
свободную позицию для записи имени файла, после чего значение пере-
меной NEXT увеличивается на единицу.
                                                                           Принт-сервер
               Процесс-клиент R
                                          Общие данные                      Печать файлов
              Прочитать NEXT                                                  из списка
        R1

        R2   Поместить имя файла
                   RFILE

        R3     Нарастить NEXT                            1   ALPHA
                      .                                  2  BETA
                      .
                      .                    NEXT          3 GAMMA


               Процесс-клиент S                          .
                                                         .
               Прочитать NEXT
        S1
                                                         .
        S2   Поместить имя файла
                   SFILE
                                   Разделяемый ресурс
        S3     Нарастить NEXT
                      .
                                                                  «Эффект гонок»
                      .
                      .                                      R1               R2    R3
                                              R                    прерывание

                                                                   S1 S2   S3
                                              S



 Рисунок 17 – Пример необходимости синхронизации при доступе к одному
                             файлу заказов
     Предположим, что в некоторый момент времени процесс R решил
распечатать свой файл, для чего считал текущее значение переменной
NEXT (пусть NEXT = k). Затем, например, вследствие исчерпания кванта
времени, выделенного процессу, выполнение процесса было прервано.
     Очередной процесс S, желающий также распечатать файл, считал
значение k переменной NEXT, поместил в позицию k имя своего файла и
нарастил значение переменной NEXT на единицу.
     Когда в очередной раз управление будет передано процессу R, то
он, продолжая свое выполнение, в полном соответствии со считанным
ранее значением текущей свободной позиции, запишет имя файла для
печати в файл «заказов» также в позицию k (поверх имени файла про-
цесса S). Поэтому, файл процесса S не будет напечатан.
     Очевидно, что решение проблемы синхронизации в данном случае
зависит от взаимных скоростей процессов и моментов их прерывания,
то есть при других названных параметрах потери файлов при печати


                                              67


могло и не быть. Это подтверждает нерегулярность рассинхронизации
процессов и наличие сложностей в обеспечении их синхронизации.
     Ситуации подобные этой, когда два или более процессов обрабаты-
вают разделяемые данные, и конечный результат зависит от соотноше-
ния скоростей процессов, называются гонками.
     Важным понятием, используемым при синхронизации потоков, яв-
ляется понятие «критической секции» программы. Критическая секция
– это часть программы, результат выполнения которой может непред-
сказуемо меняться, если переменные, относящиеся к этой части про-
граммы, изменяются другими потоками в то время, когда выполнение
этой части еще не завершено. Критическая секция всегда определяется
по отношению к определенным критическим данным, при несогласо-
ванном изменении которых могут возникнуть нежелательные эффекты.
В примере, представленном на рис. 17, такой критической секцией явля-
ется файл «заказов», являющийся разделяемым ресурсом для процессов
R и S.
    3.3.4   Механизмы синхронизации
     Как было отмечено выше в п. 3.3.2, ОС поддерживает целый ряд
различных средств синхронизации процессов, позволяющих избежать
проблем, подобной той, что описана выше и представлена на рис. 17.
Рассмотрим каждое из этих средств синхронизации процессов более по-
дробно.
     Блокирующие переменные. Для синхронизации потоков одного
процесса прикладной программист может использовать глобальные бло-
кирующие переменные. С этими переменными, к которым все потоки
процесса имеют прямой доступ, программист работает, не обращаясь к
системным вызовам ОС. Каждому набору критических данных ставится
в соответствие двоичная переменная, которой поток присваивает значе-
ние 0, когда он входит в критическую секцию, и значение 1, когда он ее
покидает.
     На рис. 18 показан фрагмент алгоритма потока, использующего для
реализации взаимного исключения доступа к критическим данным D
блокирующую переменную F(D). Перед входом в критическую секцию
поток проверяет, не работает ли уже какой-нибудь другой поток с дан-
ными D. Если переменная F(D) установлена в 0, то данные заняты и
проверка циклически повторяется. Если же данные свободны (F(D) = 1),
то значение переменной F(D) устанавливается в 0 и поток входит в кри-
тическую секцию. После того, как поток выполнит все действия с дан-
ными D, значение переменной F(D) снова устанавливается равным 1.


                                  68


                                             Попытка доступа к
                                             разделяемому ресурсу D




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


                                               Да, свободен

                                     Занять ресурс
                                        F(D):=0



                                 Критическая секция
                                 (работа с ресурсом D)



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


                               Продолжение вычислений
 Рисунок 18 – Работа в критической секции с использованием блокирующих
                              переменных
     Блокирующие переменные могут использоваться не только при до-
ступе к разделяемым данным, но и при доступе к разделяемым ресурсам
любого вида. Если все потоки разработаны с учетом вышеописанных
соглашений, то взаимное исключение гарантируется. При этом потоки
могут быть прерваны ОС в любой момент и в любом месте, в том числе
в критической секции. Однако следует заметить, что одно ограничение
на прерывания все же имеется – нельзя прерывать поток между выпол-
нением операций проверки и установки блокирующей переменной, т.к.
это нарушит принцип взаимного исключения.
     Действительно, пусть в результате проверки переменной поток
определил, что ресурс свободен, но сразу после этого, не успев устано-
вить переменную в 0, был прерван. За время его приостановки другой
поток занял ресурс, вошел в свою критическую секцию, но также был
прерван, не завершив работы с разделяемым ресурсом. Когда управле-
ние было возвращено первому потоку, он, считая ресурс свободным,
установил признак занятости и начал выполнять операции в критиче-
ской секции. Таким образом, в одной критической секции производят
работу два различных потока, а это потенциально может привести к не-
желательным последствиям.
                                   69


     Во избежание подобных ситуаций в системе команд многих ком-
пьютеров предусмотрена единая, неделимая команда анализа и присвое-
ния значения логической переменной (например, команды ВТС, BTR и
ВТ5 процессора Pentium). При отсутствии такой команды в процессоре
соответствующие действия должны реализовываться специальными си-
стемными примитивами – базовыми функциями ОС, которые бы запре-
щали прерывания на протяжении всей операции проверки и установки.
     Реализация взаимного исключения с использованием глобальных
блокирующих переменных имеет существенный недостаток: в течение
времени, когда один поток находится в критической секции, другой по-
ток, которому требуется тот же ресурс, получив доступ к процессору,
будет непрерывно опрашивать блокирующую переменную, бесполезно
растрачивая выделяемое ему процессорное время, которое могло бы
быть использовано для выполнения какого-нибудь другого потока. Для
устранения этого недостатка во многих ОС предусматриваются специ-
альные системные вызовы (аппарат событий) для работы с критически-
ми секциями.
     Семафоры. В разных ОС аппарат событий реализуется по своему,
но в любом случае используются системные функции аналогичного
назначения, которые условно именуют WAIT(x) и POST(x), где x – иден-
тификатор некоторого события. На рис. 19 показан фрагмент алгоритма
процесса, использующего эти функции.
     Если ресурс занят, то процесс не выполняет циклический опрос, а
вызывает системную функцию WAIT(D), здесь D обозначает событие,
заключающееся в освобождении ресурса D. Функция WAIT(D) перево-
дит активный процесс в состояние ожидание и делает отметку в его де-
скрипторе о том, что процесс ожидает события D. Процесс, который в
это время использует ресурс D, после выхода из критической секции
выполняет системную функцию POST(D), ОС просматривает очередь
ожидающих процессов и переводит процесс, ожидающий события D, в
состояние готовность.
     Обобщающее средство синхронизации процессов с использованием
изложенных выше принципов, названное семафор, предложил
Э.В. Дейкстра (Edsger Wybe Dijkstra) – выдающийся нидерландский
учѐный, идеи которого оказали огромное влияние на развитие компью-
терной индустрии. Семафор – объект, позволяющий войти в заданный
участок кода не более чем n потокам. Осуществляется это путем исполь-
зования специальной защищенной переменной S, значения которой
можно опрашивать и менять только при помощи специальных операций
P(S) и V(S) и операции инициализации. Семафор может принимать це-
лое неотрицательное значение. При выполнении потоком операции P
над семафором S значение семафора уменьшается на 1 при S > 0, или
                                 70



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