CHuDya все записи автора 28. Основной особенностью мультипрограммных операционных систем является то, что в их среде параллельно развивается несколько (последовательных) вычислительных процессов. С точки зрения внешнего наблюдателя эти последовательные вычислительные процессы выполняются одновременно, мы же будем говорить «параллельно». При этом под параллельными понимаются не только процессы, одновременно развивающиеся на различных процессорах, каналах и устройствах ввода-вывода, но и те последовательные процессы, которые разделяют централь- ный процессор и в своем выполнении хотя бы частично перекрываются во време- ни. параллельными мы будем называть такие последовательные вычислитель- ные процессы, которые одновременно находятся в каком-нибудь активном состо- янии. Два параллельных процесса могут быть независимыми (independed processes) либо взаимодействующими (cooperating processes). Независимыми являются процессы, множества переменных которых не пересека- ются. Под переменными в этом случае понимают файлы данных, а также области оперативной памяти, сопоставленные промежуточным и определенным в програм- ме переменным. Независимые процессы не влияют на результаты работы друг дру- га, так как не могут изменять значения переменных друг у друга. Они могут только явиться причиной в задержках исполнения друг друга, так как вынуждены разде- лять ресурсы системы. Взаимодействующие процессы совместно используют некоторые (общие) перемен- ные, и выполнение одного процесса может повлиять на выполнение другого. Как мы уже говорили, при выполнении вычислительные процессы разделяют ресурсы сис- темы. Подчеркнем, что при рассмотрении вопросов синхронизации вычислитель- ных процессов из числа разделяемых ими ресурсов исключаются центральный про- цессор и программы, реализующие эти процессы, то есть с логической точки зрения каждому процессу соответствуют свои процессор и программа, хотя в реальных си- стемах обычно несколько процессов разделяют один процессор и одну или несколь- ко программ. Многие ресурсы вычислительной системы могут совместно использо- ваться несколькими процессами, но в каждый момент времени к разделяемому ресурсу может иметь доступ только один процесс. Ресурсы, которые не допускают одновременного использования несколькими процессами, называются критическими. Если несколько вычислительных процессов хотят пользоваться критическим ре- сурсом в режиме разделения, им следует синхронизировать свои действия таким образом, чтобы ресурс всегда находился в распоряжении не более чем одного из них. Если один процесс пользуется в данный момент критическим ресурсом, то все остальные процессы, которым нужен этот ресурс, должны ждать, пока он не освободится. Если в операционной системе не предусмотрена защита от одновре- менного доступа процессов к критическим ресурсам, в ней могут возникать ошиб- ки, которые трудно обнаружить и исправить. Конкурирующие процессы действуют относительно независимо друг от друга, однако они имеют доступ к некоторым общим переменным. Их независимость заключается в том, что они могут работать друг без друга, поодиночке. Но при своем выполнении они могут работать и параллельно, и тогда они иногда начинают конкурировать при обращении к этим общим переменным. Таким образом, их независимость относительна. Чтобы предотвратить некорректное исполнение конкурирующих процессов вследствие нерегламентированного доступа к разделяемым переменным, необходимо ввести понятие взаимного исключения, согласно которому два процесса не должны одновременно обращаться к разделяемым переменным. При организации различного рода взаимодействующих процессов приходится организовывать взаимное исключение и решать проблему корректного доступа к общим переменным (критическим ресурсам). Те места в программах, в которых происходит обращение к критическим ресурсам, называются критическими секциями (Critical Section, CS). Средства синхронизациии связи Все известные средства решения проблемы взаимного исключения основаны на использовании специально введенных аппаратных возможностей. К этим аппарат- ным возможностям относятся: блокировка памяти, специальные команды типа «проверка и установка» и механизмы управления системой прерываний, которые позволяют организовать такие средства, как семафорные операции, мониторы, по- чтовые ящики и др. С помощью перечисленных средств можно разрабатывать вза- имодействующие процессы, при исполнении которых будут корректно решаться все задачи, связанные с проблемой критических секций. Блокировка памяти Все вычислительные машины и системы (в том числе и с многопортовыми блока- ми оперативной памяти) имеют средство для организации взаимного исключения, называемое блокировкой памяти. Блокировка памяти запрещает одновременное исполнение двух (и более) команд, которые обращаются к одной и той же ячейке памяти. Блокировка памяти имеет место всегда, то есть это обязательное условие функционирования компьютера. Соответственно, поскольку в некоторой ячейке памяти хранится значение разделяемой переменной, то получить доступ к ней может только один процесс, несмотря на возможное совмещение выполнения ко- манд во времени на различных процессорах (или на одном процессоре, но с кон- вейерной организацией параллельного выполнения команд). Механизм блокировки памяти предотвращает одновременный доступ к разделяе- мой переменной, но не предотвращает чередование доступа. Алгоритм Деккера Алгоритм Деккера основан на использовании трех переменных (листинг 7. 4): пе- рекл1, перекл2 и ОЧЕРЕДЬ. Пусть по-прежнему переменная перекл1 устанавливает- ся в true тогда, когда процесс ПР1 хочет войти в свою критическую секцию (для ПР2 аналогично), а значение переменной ОЧЕРЕДЬ указывает, чье сейчас право сде- лать попытку входа при условии, что оба процесса хотят выполнить свои крити- ческие секции. Листинг 7. 4. Алгоритм Деккера label 1, 2. var перекл1, перекл2 boolean, ОЧЕРЕДЬ integer. Begin перекл1 = false, перекл2 =false ОЧЕРЕДЬ =1. parbegin while true do begin перекл1 =true. продолжение & 220 Глава 7. Организация параллельных взаимодействующих вычислений Листинг 7. 4 (продолжение) 1 if перекл2 =true then if ОЧЕРЕДЬ=1 then go to 1 else begin перекл1 =false while ОЧЕРЕДЬ=2 do begin end end else begin CS1 { критическая секция ПР1 } ОЧЕРЕДЬ =2 перекл1 =false end end and while true do begin перекл2 =1 2 if перекл1 =true then if ОЧЕРЕДЬ=2 then go to 2 else begin перекл2 =false while ОЧЕРЕДЬ=1 do begin end end else begin CS2 { критическая секция ПР2 } ОЧЕРЕДЬ =1 перекл2 =false end end parend end Если перекл2 = true и перекл1 = false, то выполняется критическая секция процес- са ПР2 независимо от значения переменной ОЧЕРЕДЬ. Аналогично для случая пе- рекл2 = false и перекл1 =true. Если же оба процесса хотят выполнить свои критические секции, то есть перекл2 = = true и перекл1 = true, то выполняется критическая секция того процесса, на кото- рый указывает значение переменной ОЧЕРЕДЬ, независимо от скоростей развития обоих процессов. Использование переменной ОЧЕРЕДЬ совместно с переменными перекл1 и перекл2 в алгоритме Деккера позволяет гарантированно решать пробле- му критических секций. То есть переменные перекл1 и перекл2 гарантируют, что взаимное выполнение не может иметь места; переменная ОЧЕРЕДЬ гарантирует, что не может быть взаимной блокировки, так как переменная ОЧЕРЕДЬ не меняет свое- го значения во время выполнения программы принятия решения о том, кому же сейчас проходить свою критическую секцию. Тем не менее реализаций критических секций на основе описанного алгоритма практически не встречается из-за их чрезмерной сложности, особенно тогда, когда требуется обобщить алгоритм Деккера с двух до N процессов. проверка и установка Операция проверки и установки является, так же как и блокировка памяти, одним из аппаратных средств, которые могут быть использованы для решения задачи вза- имного исключения при выполнении критической секции. Данная операция реа- лизована во многих компьютерах. Так, в знаменитой машине IBM 360 (370) эта команда называлась TS (Test and Set — проверка и установка). Команда TS являет- ся двухадресной (двухоперандной). Ее действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Команда TS является неделимой опера- цией, то есть между ее началом и концом не могут выполняться никакие другие команды. Листинг 7. 5. Взаимное исключение с помощью операции проверки и установки var common, local1, local2 integer begin common =0. parbegin ПР1 while true do begin local1 =1. while local1=1 do TS(local1, common), CS1. { критическая секция процесса ПР1 } common =0 PR1. { ПР1 после критической секции } end and ПР2 while true do begin Iocal2 =1. while local2=1 do TS( local2, common) CS2, { критическая секция процесса ПР2 } common =0 PR2 { ПР2 после критической секции } end parend end Предположим, что первым хочет войти в свою критическую секцию процесс ПР1 В этом случае значение local1 сначала установится в единицу, а после цикла про- верки с помощью команды TS(local1, common) — в нуль. При этом значение common станет равным единице. Процесс ПР1 войдет в свою критическую секцию. После выполнения критической секции переменная common примет значение, равное нулю, что даст возможность второму процессу ПР2 войти в свою критическую сек- цию. Безусловно, мы предполагаем, что в компьютере реализована блокировка памяти, то есть операция common: = 0 неделима. Команда проверки и установки значитель- но упрощает решение проблемы критических секций. Главная черта этой коман- ды — ее неделимость. 29. Семафорные примитивы Дейкстры Понятие семафорных механизмов было введено Дейкстрой [10]. Семафор (semaphore) — это переменная специального типа, которая доступна параллельным процес- сам только для двух операций — закрытия и открытия, названных соответственно операциями Р и V1. Эти операции являются примитивами относительно семафора, который указывается в качестве параметра операций. Здесь семафор играет роль вспомогательного критического ресурса, так как операции Р и V неделимы при сво- ем выполнении и взаимно исключают друг друга. Одним из вариантов реализации семафорных механизмов для организации вза- имного исключения является так называемый мъютекс (mutex). Термин «mutex» произошел от словосочетания «mutual exclusion semaphore», что дословно перево- дится с английского как «семафор взаимного исключения». Мьютексы реализова- ны во многих операционных системах, их основное назначение — организация вза- имного исключения для задач (потоков выполнения) одного или нескольких процессов. Мьютексы — это простейшие двоичные семафоры, которые могут на- ходиться в одном из двух состояний — отмеченном и неотмеченном (открыт и за- крыт соответственно). Семафорные примитивы чрезвычайно широко используются при проектиро- вании разнообразных вычислительных процессов. При этом некоторые задачи являются настолько «типичными», что их детальное рассмотрение уже стало классическим в соответствующих учебных пособиях. Не будем делать исклю- чений и мы. Необходимо иметь очевидные решения, которые позволят прикладным програм- мистам без лишних усилий, связанных с доказательством правильности алгорит- мов и отслеживанием большого числа взаимосвязанных объектов, создавать па- раллельные взаимодействующие программы. К таким решениям можно отнести так называемые мониторы, предложенные Хоаром [52]. В параллельном программировании монитор — это пассивный набор разделяемых переменных и повторно входимых процедур доступа к ним, которым процессы пользуются в режиме разделения, причем в каждый момент им может пользовать- ся только один процесс. Рассмотрим, например, некоторый ресурс, который разделяется между процесса- ми каким-либо планировщиком [17]. Каждый раз, когда процесс желает получить в свое распоряжение какие-то ресурсы, он должен обратиться к программе-плани- ровщику. Этот планировщик должен иметь переменные, с помощью которых можно отслеживать, занят ресурс или свободен. Процедуру планировщика разделяют все процессы, и каждый процесс может в любой момент захотеть обратиться к плани- ровщику. Но планировщик не в состоянии обслуживать более одного процесса одновременно. Такая процедура-планировщик и представляет собой пример мо- нитора. Таким образом, монитор — это механизм организации параллелизма, который со- держит как данные, так и процедуры, необходимые для динамического распреде- ления конкретного общего ресурса или группы общих ресурсов. Процесс, желаю- щий получить доступ к разделяемым переменным, должен обратиться к монитору, который либо предоставит доступ, либо откажет в нем. почтовый ящик — это информационная структура, поддерживаемая опера- ционной системой. Она состоит из головного элемента, в котором находится ин- формация о данном почтовом ящике, и нескольких буферов (гнезд), в которые помещают сообщения. Размер каждого буфера и их количество обычно задаются при образовании почтового ящика. Основные достоинства почтовых ящиков: * процессу не нужно знать о существовании других процессов до тех пор, пока он не получит сообщения от них; * два процесса могут обменяться более чем одним сообщением за один раз; * операционная система может гарантировать, что никакой иной процесс не вме- шается во взаимодействие процессов, ведущих между собой «переписку»; * очереди буферов позволяют процессу-отправителю продолжать работу, не об- ращая внимания на получателя. Основным недостатком буферизации сообщений является появление еще одного ресурса, которым нужно управлять. Этим ресурсом являются сами почтовые ящики. Конвейеры Программный канал связи (pipe), или, как его иногда называют, конвейер, транс- портер, является средством, с помощью которого можно обмениваться данными между процессами. Принцип работы конвейера основан на механизме ввода-вы- вода файлов в UNIX, то есть задача, передающая информацию, действует так, как будто она записывает данные в файл, в то время как задача, для которой предна- значается эта информация, читает ее из этого файла. Операции записи и чтения осуществляются не записями, как это делается в обычных файлах, а потоком бай- тов, как это принято в UNIX-системах. Таким образом, функции, с помощью кото- рых выполняется запись в канал и чтение из него, являются теми же самыми, что и при работе с файлами. Очереди сообщений Очереди (queues) сообщений предлагают более удобный метод связи между взаи- модействующими процессами по сравнению с каналами, но в своей реализации они сложнее. С помощью очередей также можно из одной или нескольких задач независимым образом посылать сообщения некоторой задаче-приемнику. При этом только процесс-приемник может читать и удалять сообщения из очереди, а про- цессы-клиенты имеют право лишь помещать в очередь свои сообщения. Таким образом, очередь работает только в одном направлении. Если же необходима двухсторонняя связь, то можно создать две очереди. 32 В микроядерных операционных системах мы можем выделить центральный ком- пактный модуль, относящийся к супервизорной части системы. Этот модуль име- ет очень небольшие размеры и выполняет относительно небольшое количество управляющих функций, но позволяет передать управление на другие управляю- щие модули, которые и выполнят затребованную функцию. Микроядро — это ми- нимальная главная (стержневая) часть операционной системы, служащая осно- вой модульных и переносимых расширений. Основная идея, заложенная в технологию микроядра заключается в том, чтобы создать необходимую среду верхнего уровня иерархии, из которой можно легко получить доступ ко всем функциональным возможностям уровня аппаратного обеспечения. При этом микроядро является стартовой точкой для создания всех остальных модулей системы. Все эти остальные модули, реализующие необхо- димые системе функции, вызываются из микроядра и выполняют сервисную роль. Наиболее ярким представителем микроядерных операционных систем является операционная система реального времени QNX. Микроядро QNX поддерживает только планирование и диспетчеризацию процессов, взаимодействие процессов, обработку прерываний и сетевые службы нижнего уровня. Функции микроядерных * управление виртуальной памятью; * поддержка заданий и потоков; * взаимодействие между процессами (Inter-Process Communication, IPC); * управление поддержкой ввода-вывода и прерываниями; * сервисы хоста (host)1 и процессора. В макроядерных, или монолитных, операционных системах ядро, состоящее из мно- жества управляющих модулей и структур данных, не разделено на центральную часть и периферийные (по отношению к этой центральной части) модули. Ядро получается монолитным, неделимым. В этом смысле макроядерные операцион- ные системы являются прямой противоположностью микроядерным. В монолитной операционной системе, несмотря на ее возможную сильную структуризацию, очень трудно удалить один из уровней многоуровневой модульной структуры. Добавление новых функций и изменение существующих для монолитных операционных систем требует очень хорошего знания всей архи- тектуры операционной системы и чрезвычайно больших усилий. В качестве подтверждения этому можно привести пример с операционными системами класса Windows NT, которые построены на идеологии клиент-сервер, но которые тем не менее трудно назвать микроядерными. Пример windows NT 33.Требования к операционным системам реального времени Система реального времени (СРВ) должна давать отклик на любые непредсказуемые внешние воздействия в течение предсказуемого интервала времени. Для этого должны выполняться следующие требования. * Ограничение времени отклика. После наступления события реакция на него гарантированно должна последовать до предустановленного крайнего срока. Отсутствие такого ограничения рассматривается как серьезный недостаток программного обеспечения. * Одновременность обработки. Даже если наступает более одного события одновременно, все временные ограничения для всех событий должны быть выдержаны. Это означает, что системе реального времени должен быть присущ параллелизм, что достигается использованием нескольких процессоров и/или многозадачного подхода. Примерами систем реального времени являются системы управления атомными электростанциями или какими-нибудь технологическими процессами, системы медицинского мониторинга, системы управления вооружением, системы космической навигации, системы разведки, системы управления лабораторными экспериментами, системы управления автомобильными двигателями, робототехника, телеметрические системы управления, системы антиблокировки тормозов, системы сигнализации. Операционная система должна быть мультипрограммной и мультизадачной (многопоточной — multi-threaded), а также активно использовать прерывания для диспетчеризации. То есть планировщик должен иметь возможность прервать любой поток выполнения и предоставить ресурс тому потоку, которому он более необходим. Операционная система (и аппаратура) должна также обеспечивать прерывания на уровне обработки прерываний. Должно существовать понятие приоритета потока (задачи). В идеальной ситуации ОСРВ отдает ресурс потоку или драйверу с ближайшим крайним сроком, что называется управлением временным ограничением (DeadLine DrivenOS). Чтобы реализовать это временное ограничение, операционная система должна знать, сколько времени требуется каждому из выполняющихся потоков для завершения. Операционных систем, построенных по этому принципу, практически нет, так как он слишком сложен для реализации. Поэтому разработчики операционных систем принимают иную точку зрения: вводится понятие уровня приоритета для задачи, и временные ограничения сводятся к приоритетам. Должна существовать система наследования приоритетов. Когда поток низшего приоритета захватил ресурс, разделяемый с потоком высшего приоритета, и начал выполняться поток среднего приоритета, выполнение потока высшего приоритета будет приостановлено, пока не освободится ресурс и не отработает поток среднего приоритета. В этой ситуации время, необходимое для завершения потока высшего приоритета, зависит от нижних уровней приоритетов — это и есть инверсия приоритетов. Чтобы устранить такие инверсии, ОСРВ должна допускать наследование приоритета, то есть повышение уровня приоритета потока до уровня потока, который его вызывает. Наследование означает, что блокирующий ресурс поток наследует приоритет потока, который он блокирует (разумеется, это справедливо лишь в том случае, если блокируемый поток имеет более высокий приоритет). Операционная система должна обеспечивать мощные, надежные и удобные механизмы синхронизации задач. Так как задачи разделяют данные (ресурсы) и должны сообщаться друг с другом, представляется логичным существование механизмов блокирования и коммуникации. То есть необходимы механизмы, гарантированно предоставляющие возможность оперативно обменяться сообщениями и синхросигналами между параллельно выполняющимися задачами и процессами. Поведение операционной системы должно быть известно и достаточно точно прогнозируемо. Времена выполнения системных вызовов и временные характеристики поведения системы в различных обстоятельствах должны быть известны разработчику. Поэтому создатель ОСРВ должен приводить следующие характеристики: * латентную задержку прерывания, то есть время от момента прерывания до момента запуска задачи: она должна быть предсказуема и согласована с требованиями приложения (эта величина зависит от числа одновременно висящихｻ прерываний); * максимальное время выполнения каждого системного вызова (оно должно быть предсказуемо и не должно зависеть от числа объектов в системе); * максимальное время маскирования прерываний драйверами и супервизорными модулями операционной системы. Интерфейсы операционных систем Под интерфейсами операционных систем следует понимать специальные интерфейсы системного и прикладного программирования (API), предназначенные для выполнения следующих задач: 1.Управление процессами, которое включает в себя следующий набор основных функций: • запуск, приостанов и снятие задачи с выполнения; • задание или изменение приоритета задачи; • взаимодействие задач между собой (механизмы сигналов, семафорные примитивы, очереди, конвейеры, почтовые ящики); • вызов удаленных процедур (Remote Procedure Call, RPC). 2.Управление памятью: • запрос на выделение блока памяти; • освобождение памяти; • изменение параметров блока памяти (например, память может быть заблокирована процессом либо предоставлена в общий доступ); • отображение файлов на память (имеется не во всех системах). 3.Управление вводом-выводом: • запрос на управление виртуальными устройствами (напомним, что управление вводом-выводом является привилегированной функцией самой операционной системы, и никакая из пользовательских задач не должна иметь возможности непосредственно управлять устройствами); • файловые операции (запросы к системе управления файлами на создание, изменение и удаление данных, организованных в файлы). API (интерфейс прикладного программирования) — это набор функций, предоставляемых системой программирования разработчику прикладной программы и ориентированных на организацию взаимодействия результирующей прикладной программы с целевой вычислительной системой. Целевая вычислительная система представляет собой совокупность программных и аппаратных средств, в окружении которых выполняется результирующая программа. Сама результирующая программа порождается системой программирования на основании кода исходной программы, созданного разработчиком, а также объектных модулей и библиотек, входящих в состав системы программирования. Существует несколько вариантов реализации API: 1.реализация на уровне модулей операционной системы; При реализации функций API на уровне модулей операционной системы операционная система ответственна за выполнение функций API. Объектный код, выполняющий функции, либо непосредственно входит в состав операционной системы (или даже ядра операционной системы), либо находится в составе динамически загружаемых библиотек, поставляемых вместе с системой. В таком варианте результирующая программа обращается непосредственно к операционной системе. Поэтому достигается наибольшая эффективность выполнения функций API по сравнению со всеми другими вариантами реализации API. Недостатком организации API по такой схеме является практически полное отсутствие переносимости не только кода результирующей программы, но и кода исходной программы. 2. реализация на уровне системы программирования; При реализации функций API на уровне системы программирования эти функции предоставляются пользователю в виде библиотеки функций соответствующего языка программирования. Обычно речь идет о библиотеке времени выполнения (RTL). Система программирования предоставляет пользователю библиотек функций и обеспечивает подключение к результирующей программе объектного кода, ответственного за выполнение этих функций Очевидно, что эффективность вызова функций API в таком варианте будет несколько ниже, чем при непосредственном обращении к функциям операционной системы. Однако переносимость исходного кода программы в таком варианте оказывается самой высокой, поскольку синтаксис и семантика всех функций строго регламентированы в стандарте соответствующего языка программирования. реализация на уровне внешней библиотеки процедур и функций. При реализации функций API с помощью внешних библиотек эти функции предоставляются пользователю в виде библиотеки процедур и функций, созданной сторонним разработчиком. С точки зрения эффективности выполнения этот метод реализации API имеет самые низкие результаты, поскольку внешняя библиотека обращается как к функциям операционной системы, так и к функциям RTL языка программирования. Если говорить о переносимости исходного кода, то здесь требование только одно - используемая внешняя библиотека должна быть доступна в любой из архитектур вычислительных систем, на которые ориентирована прикладная программа. Интерфейс POSIX POSIX (Portable Operating System Interface for Computer Environments — незави- симый от платформы системный интерфейс для компьютерного окружения) — это стандарт IEEE (Institute of Electrical and Electronics Engineers — институт инже- неров по электротехнике и радиоэлектронике), описывающий системные интер- фейсы для открытых операционных систем, в том числе оболочки, утилиты и ин- струментарии. Помимо этого, согласно POSIX, стандартизированными являются задачи обеспечения безопасности, задачи реального времени, процессы админист- рирования, сетевые функции и обработка транзакций. #include #include #include // Название processFile // Описание исполняемый код потока // Входные параметры IpFileName - имя файла для обработки // Выходные параметры нет DWORD processFile(LPVOID IpFileName ) { HANDLE handle, // описатель файла DWORD numRead, total = 0, char buf, // запрос к ОС на открытие файла (только для чтения) handle = CreateFile( (LPCTSTR)lpFileName GENERIC_READ. FILE_SHARE_READ, NULL, OPEN_EXISTING FILE_ATTRIBUTE_NORMAL, NULL); // цикл чтения до конца файла