определения О.С., структура О.С., основные функции О.С., основные задачи синхронизации параллельных процессов (обозначить и раскрыть), реализация взаимоисключения: семафоры и мониторы
Теоретическое задание по курсу "Операционные Системы"
Задание: дать определения О.С., структура О.С., основные функции О.С., основные задачи синхронизации параллельных процессов (обозначить и раскрыть), реализация взаимоисключения: семафоры и мониторы.
Теория: Операционная система (ОС) - комплекс системных и управляющих программ, предназначенных для наиболее эффективного использования всех ресурсов вычислительной системы (ВС) (Вычислительная система - взаимосвязанная совокупность аппаратных средств вычислительной техники и программного обеспечения, предназначенная для обработки информации) и удобства работы с ней.
Назначение ОС - организация вычислительного процесса в вычислительной системе, рациональное распределение вычислительных ресурсов между отдельными решаемыми задачами; предоставление пользователям многочисленных сервисных средств, облегчающих процесс программирования и отладки задач.
Структура ОС носит модульный характер.
Программный модуль - программа, рассматриваемая как целое в контекстах хранения в наборе данных, трансляции, объединения с другими программными модулями, загрузки в оперативную память для выполнения или разработки в составе программного комплекса.
При разработке программного обеспечения его разделение на модули происходит по функциональному признаку, что способствует минимизации числа межмодульных связей и, следовательно, уменьшению сложности разрабатываемого программного комплекса.
Размеры модулей при этом обычно составляют несколько десятков, реже несколько сотен операторов алгоритмического языка. При исполнении программ различают исходный модуль - программу, выраженную на принятом при разработке комплекса языке программирования, объектный модуль - программу, полученную в результате трансляции на машинный язык, и загрузочный модуль - программу, прошедшую редактирование и готовую к помещению в оперативную память и после настройки адресных констант по месту загрузки - к исполнению. Загрузочный модуль может включать в себя несколько объектных и ранее отредактированных загрузочных модулей.
Основные функции ОС:
Загрузка приложений в оперативную память и их выполнение;
Стандартизованный доступ к периферийным устройствам (устройства ввода-вывода);
Управление оперативной памятью (распределение между процессами, (виртуальная память);
Управление доступом к данным на энергонезависимых носителях (таких как Жёсткий диск, Компакт-диск и т. д.), как правило, с помощью файловой системы;
Пользовательский интерфейс;
Сетевые операции, поддержка стека протоколов.
Дополнительные функции:
Параллельное или псевдопараллельное выполнение задач (многозадачность);
Взаимодействие между процессами: обмен данными, взаимная синхронизация;
Защита самой системы, а также пользовательских данных и программ от действий пользователей (злонамеренных или по незнанию) или приложений;
Разграничение прав доступа и многопользовательский режим работы (аутентификация, авторизация).
Параллельными называются процессы, у которых «интервалы времени выполнения перекрываются за счет использования разных ресурсов одной и той же вычислительной системы или за счет перераспределения одного и того же набора ресурсов». При рассмотрении параллельности мы несколько расширим понятие процесса: будем понимать под процессом любую последовательность действий. Процесс у нас имеет строго последовательную структуру, он выполняется операция за операцией, команда за командой. Но в один и тот же момент времени в системе могут выполняться несколько таких последовательностей. Такое расширение понимания процесса позволит нам включить в рассмотрение и такие последовательности действий, которые формально процессами не являются: отдельные нити одного процесса, модули ядра ОС, обработчики прерываний, процессы на внешних устройствах и т.д. С концептуальной точки зрения не имеет значения, является ли одновременность выполнения реальной (достигаемой за счет аппаратного распараллеливания) или виртуальной (достигаемой за счет разделения времени), хотя это различие, как мы увидим ниже, может сказываться на механизмах реализации.
Процессы, которые мы рассматриваем, являются слабо связанными. Это означает, что за исключением достаточно редких моментов явной связи процессы выполняются независимо друг от друга. Взаимная независимость процессов запрещает нам при решении задач управления параллельным выполнением делать какие-либо предположения о соотношении скоростей выполнения процессов. За счет перераспределения ресурсов эти скорости вообще не могут считаться постоянными. Единственным оправданным предположением в этом отношении может быть предположение о наихудшем (наименее удобном для нас) соотношении скоростей.
Поскольку параллельные процессы разделяют ресурсы вычислительной системы, задачи управления параллельным выполнением есть задачи управления ресурсами. Как и в случае монопольно используемых ресурсов, методы решения этих задач составляют широкий спектр от самых консервативных (требующих значительного снижения уровня мультипрограммирования) до самых либеральных (допускающих параллельное выполнение большого числа процессов).
Основной задачей управления параллельным выполнением является задача взаимного исключения (mutualexclusion, сокращенно - mutex): два процесса не могут выполнять одновременный доступ к разделяемым ресурсам. Обратим внимание на то обстоятельство, что взаимное исключение обеспечивается уже на аппаратном уровне. Если процессор одновременно получает два запроса, то он выполняет их последовательно по тем или иным правилам арбитража. Каждая процессорная команда обладает свойством атомарности: она или выполняется полностью, или вообще не выполняется. Так же атомарно каждое обращение к памяти. Арбитражные свойства аппаратуры являются основой для построения более сложных механизмов взаимного исключения.
Последовательность операций в процессе, которая выполняет такую единицу работы (транзакцию) с разделяемым ресурсом, во время которой никакой другой процесс не должен иметь доступа к этому ресурсу, составляет критическую секцию. Чтобы процесс мог обеспечить безопасность выполнения своей критической секции, в его распоряжении должны быть средства - "скобки критической секции" - которыми он эту критическую секцию обозначит и защитит. Назовем эти скобки csBegin и csEnd и посвятим дальнейшее рассмотрение взаимного исключения механизмам реализации этих скобок. Для доказательства правильности каждой реализации для нее необходимо показать следующее:
1 в любой момент времени не более, чем один процесс может находиться в своей критической секции;
2 решение о том, какому процессу первому надлежит войти в критическую секцию, не может откладываться до бесконечности;
3 остановка процесса вне своей критической секции не влияет на другие процессы.
В некоторых случаях возникает необходимость в приостановке выполнения процесса до наступления некоторого внешнего по отношению к нему события - такая задача называется задачей синхронизации. Если рассматривать события как ресурсы (потребляемые), то задача синхронизации является частным случаем задачи взаимного исключения. Как частный случай, она допускает частные решения.
Типичным примером задачи синхронизации является обеспечение выполнения "графа синхронизации", подобного тому, который представлен на рисунке 4.1. Граф синхронизации задает порядок выполнения действий. В программной реализации мы можем представлять действия A, B, ..., I как отдельные процессы и выполнять явную синхронизацию или, использовать неявную синхронизацию, представляя в виде процессов тройки ABC, DEF, GIH или ADG, BEH, CFI, и вводить явные точки синхронизации внутри процессов.
Рисунок 4.1. Пример графа синхронизации
Взаимное исключение запретом прерываний.
Большинство компьютерных архитектур предусматривает в составе своей системы команд команды запрета прерываний (иногда - селективного запрета). В микропроцессорах Intel-Pentium, например, такими командами являются CLI (запретить прерывания) и STI (разрешить прерывания). Такие команды и могут составить "скобки критической секции": запрет прерываний при входе в критическую секцию и разрешение - при выходе из нее. Поскольку вытеснение процесса возможно только по прерыванию, процесс, находящийся в критической секции, не может быть прерван. Этот метод, однако, обладает большим числом недостатков:
1. пока процесс находится в критической секции, не могут быть обработаны никакие внешние события, в том числе, и события, требующие обработки в реальном времени;
2. исключаются не только конфликтующие критические секции, которые могут обращаться к разделяемым данным, но и все другие процессы вообще, дисциплина, таким образом, является весьма консервативной;
3. процесс, находящийся внутри критической секции, не может перейти в ожидание (кроме занятого ожидания), так как механизм ожидания обеспечивается прерываниями;
4. программист должен быть весьма внимателен к тому, чтобы все возможные варианты выхода из критической секции обеспечивались разрешением прерываний;
5. вложение критических секций невозможно;
6. обеспечение критической секции запретом прерываний базируется на аппаратной атомарности команд, оно неприменимо в мультипроцессорных системах с реальной параллельностью, так как программа, выполняющаяся на одном процессоре не может запретить прерывания другого процессора.
Семафоры
В теории операционных систем семафор представляет собой неотрицательную целую переменную, над которой возможны два вида операций: P и V.P-операция над семафором представляет собой попытку уменьшения значения семафора на 1. Если перед выполнением P-операции значение семафора было больше 0, P-операция выполняется без задержек. Если перед выполнением P-операции значение семафора было 0, процесс, выполняющий P-операцию, переводится в состояние ожидания до тех пор, пока значение семафора не станет большим 0.V-операция над семафором представляет собой увеличение значения семафора на 1. Если при этом имеются процессы, задержанные на выполнении P-операции на данном семафоре, один из этих процессов выходит из состояния ожидания и может выполнить свою P-операцию.Семафоры являются гибким и удобным средством для синхронизации и взаимного исключения процессов, учета ресурсов, скрытые семафоры также используются в операционных системах как основа для других средств взаимодействия процессов.
Монитор
Монитор представляет собой набор информационных структур и процедур, которые используются в режиме разделения. Некоторые из этих процедур являются внешними и доступны процессам пользователей, их имена представляют входные точки монитора. Пользователь не имеет доступа к информационным структурам монитора и может воздействовать на них, только обращаясь ко входным точкам. Монитор, таким образом, воплощает принцип инкапсуляции данных. В терминах объектно-ориентированного программирования ресурс, обслуживаемый монитором, представляет собой объект, а входные точки - методы работы с этим объектом. Особенностью монитора, однако, является то, что в его состав входят, так называемые, "процедуры с охраной", которые не могут выполняться двумя процессами одновременно.Не являясь средством более мощным или гибким, мониторы, однако, представляют значительно более удобный инструмент для программиста, избавляя его от необходимости формировать критические секции, обеспечивая более высокий уровень интеграции данных и предупреждая возможные ошибки во взаимном исключении.Монитор - это механизм организации параллелизма высокого уровня, который содержит множество переменных состояний, очередей и множество процедур, необходимых для реализации динамического распределения и доступа к общим ресурсам.
Достоинства монитора:
Логические возможности не меньше, чем у семафоров.
Упрощение написания параллельных программ. Достаточно знать процедуры организации параллельных вычислений.
Повышение надежности параллельных систем, так как полностью защищает управление ресурсом.
Обеспечение гарантированного получения ресурса.
Задание: дать определения О.С., структура О.С., основные функции О.С., основные задачи синхронизации параллельных процессов (обозначить и раскрыть), реализация взаимоисключения: семафоры и мониторы.
Теория: Операционная система (ОС) - комплекс системных и управляющих программ, предназначенных для наиболее эффективного использования всех ресурсов вычислительной системы (ВС) (Вычислительная система - взаимосвязанная совокупность аппаратных средств вычислительной техники и программного обеспечения, предназначенная для обработки информации) и удобства работы с ней.
Назначение ОС - организация вычислительного процесса в вычислительной системе, рациональное распределение вычислительных ресурсов между отдельными решаемыми задачами; предоставление пользователям многочисленных сервисных средств, облегчающих процесс программирования и отладки задач.
Структура ОС носит модульный характер.
Программный модуль - программа, рассматриваемая как целое в контекстах хранения в наборе данных, трансляции, объединения с другими программными модулями, загрузки в оперативную память для выполнения или разработки в составе программного комплекса.
При разработке программного обеспечения его разделение на модули происходит по функциональному признаку, что способствует минимизации числа межмодульных связей и, следовательно, уменьшению сложности разрабатываемого программного комплекса.
Размеры модулей при этом обычно составляют несколько десятков, реже несколько сотен операторов алгоритмического языка. При исполнении программ различают исходный модуль - программу, выраженную на принятом при разработке комплекса языке программирования, объектный модуль - программу, полученную в результате трансляции на машинный язык, и загрузочный модуль - программу, прошедшую редактирование и готовую к помещению в оперативную память и после настройки адресных констант по месту загрузки - к исполнению. Загрузочный модуль может включать в себя несколько объектных и ранее отредактированных загрузочных модулей.
Основные функции ОС:
Загрузка приложений в оперативную память и их выполнение;
Стандартизованный доступ к периферийным устройствам (устройства ввода-вывода);
Управление оперативной памятью (распределение между процессами, (виртуальная память);
Управление доступом к данным на энергонезависимых носителях (таких как Жёсткий диск, Компакт-диск и т. д.), как правило, с помощью файловой системы;
Пользовательский интерфейс;
Сетевые операции, поддержка стека протоколов.
Дополнительные функции:
Параллельное или псевдопараллельное выполнение задач (многозадачность);
Взаимодействие между процессами: обмен данными, взаимная синхронизация;
Защита самой системы, а также пользовательских данных и программ от действий пользователей (злонамеренных или по незнанию) или приложений;
Разграничение прав доступа и многопользовательский режим работы (аутентификация, авторизация).
Параллельными называются процессы, у которых «интервалы времени выполнения перекрываются за счет использования разных ресурсов одной и той же вычислительной системы или за счет перераспределения одного и того же набора ресурсов». При рассмотрении параллельности мы несколько расширим понятие процесса: будем понимать под процессом любую последовательность действий. Процесс у нас имеет строго последовательную структуру, он выполняется операция за операцией, команда за командой. Но в один и тот же момент времени в системе могут выполняться несколько таких последовательностей. Такое расширение понимания процесса позволит нам включить в рассмотрение и такие последовательности действий, которые формально процессами не являются: отдельные нити одного процесса, модули ядра ОС, обработчики прерываний, процессы на внешних устройствах и т.д. С концептуальной точки зрения не имеет значения, является ли одновременность выполнения реальной (достигаемой за счет аппаратного распараллеливания) или виртуальной (достигаемой за счет разделения времени), хотя это различие, как мы увидим ниже, может сказываться на механизмах реализации.
Процессы, которые мы рассматриваем, являются слабо связанными. Это означает, что за исключением достаточно редких моментов явной связи процессы выполняются независимо друг от друга. Взаимная независимость процессов запрещает нам при решении задач управления параллельным выполнением делать какие-либо предположения о соотношении скоростей выполнения процессов. За счет перераспределения ресурсов эти скорости вообще не могут считаться постоянными. Единственным оправданным предположением в этом отношении может быть предположение о наихудшем (наименее удобном для нас) соотношении скоростей.
Поскольку параллельные процессы разделяют ресурсы вычислительной системы, задачи управления параллельным выполнением есть задачи управления ресурсами. Как и в случае монопольно используемых ресурсов, методы решения этих задач составляют широкий спектр от самых консервативных (требующих значительного снижения уровня мультипрограммирования) до самых либеральных (допускающих параллельное выполнение большого числа процессов).
Основной задачей управления параллельным выполнением является задача взаимного исключения (mutualexclusion, сокращенно - mutex): два процесса не могут выполнять одновременный доступ к разделяемым ресурсам. Обратим внимание на то обстоятельство, что взаимное исключение обеспечивается уже на аппаратном уровне. Если процессор одновременно получает два запроса, то он выполняет их последовательно по тем или иным правилам арбитража. Каждая процессорная команда обладает свойством атомарности: она или выполняется полностью, или вообще не выполняется. Так же атомарно каждое обращение к памяти. Арбитражные свойства аппаратуры являются основой для построения более сложных механизмов взаимного исключения.
Последовательность операций в процессе, которая выполняет такую единицу работы (транзакцию) с разделяемым ресурсом, во время которой никакой другой процесс не должен иметь доступа к этому ресурсу, составляет критическую секцию. Чтобы процесс мог обеспечить безопасность выполнения своей критической секции, в его распоряжении должны быть средства - "скобки критической секции" - которыми он эту критическую секцию обозначит и защитит. Назовем эти скобки csBegin и csEnd и посвятим дальнейшее рассмотрение взаимного исключения механизмам реализации этих скобок. Для доказательства правильности каждой реализации для нее необходимо показать следующее:
1 в любой момент времени не более, чем один процесс может находиться в своей критической секции;
2 решение о том, какому процессу первому надлежит войти в критическую секцию, не может откладываться до бесконечности;
3 остановка процесса вне своей критической секции не влияет на другие процессы.
В некоторых случаях возникает необходимость в приостановке выполнения процесса до наступления некоторого внешнего по отношению к нему события - такая задача называется задачей синхронизации. Если рассматривать события как ресурсы (потребляемые), то задача синхронизации является частным случаем задачи взаимного исключения. Как частный случай, она допускает частные решения.
Типичным примером задачи синхронизации является обеспечение выполнения "графа синхронизации", подобного тому, который представлен на рисунке 4.1. Граф синхронизации задает порядок выполнения действий. В программной реализации мы можем представлять действия A, B, ..., I как отдельные процессы и выполнять явную синхронизацию или, использовать неявную синхронизацию, представляя в виде процессов тройки ABC, DEF, GIH или ADG, BEH, CFI, и вводить явные точки синхронизации внутри процессов.
Рисунок 4.1. Пример графа синхронизации
Взаимное исключение запретом прерываний.
Большинство компьютерных архитектур предусматривает в составе своей системы команд команды запрета прерываний (иногда - селективного запрета). В микропроцессорах Intel-Pentium, например, такими командами являются CLI (запретить прерывания) и STI (разрешить прерывания). Такие команды и могут составить "скобки критической секции": запрет прерываний при входе в критическую секцию и разрешение - при выходе из нее. Поскольку вытеснение процесса возможно только по прерыванию, процесс, находящийся в критической секции, не может быть прерван. Этот метод, однако, обладает большим числом недостатков:
1. пока процесс находится в критической секции, не могут быть обработаны никакие внешние события, в том числе, и события, требующие обработки в реальном времени;
2. исключаются не только конфликтующие критические секции, которые могут обращаться к разделяемым данным, но и все другие процессы вообще, дисциплина, таким образом, является весьма консервативной;
3. процесс, находящийся внутри критической секции, не может перейти в ожидание (кроме занятого ожидания), так как механизм ожидания обеспечивается прерываниями;
4. программист должен быть весьма внимателен к тому, чтобы все возможные варианты выхода из критической секции обеспечивались разрешением прерываний;
5. вложение критических секций невозможно;
6. обеспечение критической секции запретом прерываний базируется на аппаратной атомарности команд, оно неприменимо в мультипроцессорных системах с реальной параллельностью, так как программа, выполняющаяся на одном процессоре не может запретить прерывания другого процессора.
Семафоры
В теории операционных систем семафор представляет собой неотрицательную целую переменную, над которой возможны два вида операций: P и V.P-операция над семафором представляет собой попытку уменьшения значения семафора на 1. Если перед выполнением P-операции значение семафора было больше 0, P-операция выполняется без задержек. Если перед выполнением P-операции значение семафора было 0, процесс, выполняющий P-операцию, переводится в состояние ожидания до тех пор, пока значение семафора не станет большим 0.V-операция над семафором представляет собой увеличение значения семафора на 1. Если при этом имеются процессы, задержанные на выполнении P-операции на данном семафоре, один из этих процессов выходит из состояния ожидания и может выполнить свою P-операцию.Семафоры являются гибким и удобным средством для синхронизации и взаимного исключения процессов, учета ресурсов, скрытые семафоры также используются в операционных системах как основа для других средств взаимодействия процессов.
Монитор
Монитор представляет собой набор информационных структур и процедур, которые используются в режиме разделения. Некоторые из этих процедур являются внешними и доступны процессам пользователей, их имена представляют входные точки монитора. Пользователь не имеет доступа к информационным структурам монитора и может воздействовать на них, только обращаясь ко входным точкам. Монитор, таким образом, воплощает принцип инкапсуляции данных. В терминах объектно-ориентированного программирования ресурс, обслуживаемый монитором, представляет собой объект, а входные точки - методы работы с этим объектом. Особенностью монитора, однако, является то, что в его состав входят, так называемые, "процедуры с охраной", которые не могут выполняться двумя процессами одновременно.Не являясь средством более мощным или гибким, мониторы, однако, представляют значительно более удобный инструмент для программиста, избавляя его от необходимости формировать критические секции, обеспечивая более высокий уровень интеграции данных и предупреждая возможные ошибки во взаимном исключении.Монитор - это механизм организации параллелизма высокого уровня, который содержит множество переменных состояний, очередей и множество процедур, необходимых для реализации динамического распределения и доступа к общим ресурсам.
Достоинства монитора:
Логические возможности не меньше, чем у семафоров.
Упрощение написания параллельных программ. Достаточно знать процедуры организации параллельных вычислений.
Повышение надежности параллельных систем, так как полностью защищает управление ресурсом.
Обеспечение гарантированного получения ресурса.