гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
Нити Многозадачность является важнейшим свойством ОС. Для поддержки этого свойства ОС определяет и оформляет для себя те внутренние единицы работы, между которыми и будет разделяться процессор и другие ресурсы компьютера. Эти внутренние единицы работы в разных ОС носят разные названия - задача, задание, процесс, нить. В некоторых случаях сущности, обозначаемые этими понятиями, принципиально отличаются друг от друга. Говоря о процессах, мы отмечали, что операционная система поддерживает их обособленность: у каждого процесса имеется свое виртуальное адресное пространство, каждому процессу назначаются свои ресурсы - файлы, окна, семафоры и т.д. Такая обособленность нужна для того, чтобы защитить один про- цесс от другого, поскольку они, совместно используя все ресурсы машины, конкурируют с друг другом. В общем случае процессы принадлежат разным пользователям, разделяющим один компьютер, и ОС берет на себя роль арбитра в спорах процессов за ресурсы. При мультипрограммировании повышается пропускная способность системы, но отдельный процесс никогда не может быть выполнен быстрее, чем если бы он выполнялся в однопрограммном режиме (всякое разделение ресурсов замедляет работу одного из участников за счет дополнительных затрат времени на ожидание освобождения ресурса). Однако задача, решаемая в рамках одного процесса, может обладать внутренним параллелизмом, который в принципе позволяет ускорить ее решение. Например, в ходе выпол- нения задачи происходит обращение к внешнему устройству, и на время этой операции можно не блокиро- вать полностью выполнение процесса, а продолжить вычисления по другой "ветви" процесса. Для этих целей современные ОС предлагают использовать сравнительно новый механизм многони- тевой обработки (multithreading). При этом вводится новое понятие "нить" (thread), а понятие "процесс" в значительной степени меняет смысл. Мультипрограммирование теперь реализуется на уровне нитей, и задача, оформленная в виде не- скольких нитей в рамках одного процесса, может быть выполнена быстрее за счет псевдопараллельного (или параллельного в мультипроцессорной системе) выполнения ее отдельных частей. Например, если элек- тронная таблица была разработана с учетом возможностей многонитевой обработки, то пользователь может запросить пересчет своего рабочего листа и одновременно продолжать заполнять таблицу. Особенно эффек- тивно можно использовать многонитевость для выполнения распределенных приложений, например, мно- гонитевый сервер может параллельно выполнять запросы сразу нескольких клиентов. Нити, относящиеся к одному процессу, не настолько изолированы друг от друга, как процессы в тра- диционной многозадачной системе, между ними легко организовать тесное взаимодействие. Действительно, в отличие от процессов, которые принадлежат разным, вообще говоря, конкурирующим приложениям, все нити одного процесса всегда принадлежат одному приложению, поэтому программист, пишущий это при- ложение, может заранее продумать работу множества нитей процесса таким образом, чтобы они могли взаимодействовать, а не бороться за ресурсы. В традиционных ОС понятие "нить" тождественно понятию "процесс". В действительности часто бывает желательно иметь несколько нитей, разделяющих единое адресное пространство, но выполняющих- ся квазипараллельно, благодаря чему нити становятся подобными процессам (за исключением разделяемого адресного пространства). Нити иногда называют облегченными процессами или мини-процессами. Действительно, нити во многих отношениях подобны процессам. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити- потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процес- сам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выпол- няться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования. Однако различные нити в рамках одного процесса не настолько независимы, как отдельные процес- сы. Все такие нити имеют одно и то же адресное пространство. Это означает, что они разделяют одни и те же глобальные переменные. Поскольку каждая нить может иметь доступ к каждому виртуальному адресу, одна нить может использовать стек другой нити. Между нитями нет полной защиты, потому что, во-первых, это невозможно, а во-вторых, не нужно. Все нити одного процесса всегда решают общую задачу одного 44 пользователя, и аппарат нитей используется здесь для более быстрого решения задачи путем ее распаралле- ливания. При этом программисту очень важно получить в свое распоряжения удобные средства организа- ции взаимодействия частей одной задачи. Кроме разделения адресного пространства, все нити разделяют также набор открытых файлов, таймеров, сигналов и т.п. Итак, нити имеют собственные: • программный счетчик, • стек, • регистры, • нити-потомки, • состояние. Нити разделяют: • адресное пространство, • глобальные переменные, • открытые файлы, • таймеры, • семафоры, • статистическую информацию. Многонитевая обработка повышает эффективность работы системы по сравнению с многозадачной обработкой. Например, в многозадачной среде Windows можно одновременно работать с электронной таб- лицей и текстовым редактором. Однако, если пользователь запрашивает пересчет своего рабочего листа, электронная таблица блокируется до тех пор, пока эта операция не завершится, что может потребовать зна- чительного времени. В многонитевой среде в случае, если электронная таблица была разработана с учетом возможностей многонитевой обработки, предоставляемых программисту, этой проблемы не возникает, и пользователь всегда имеет доступ к электронной таблице. Широкое применение находит многонитевая обработка в распределенных системах. Смотрите об этом в разделе "Процессы и нити в распределенных системах". Некоторые прикладные задачи легче программировать, используя параллелизм, например задачи ти- па "писатель-читатель", в которых одна нить выполняет запись в буфер, а другая считывает записи из него. Поскольку они разделяют общий буфер, не стоит их делать отдельными процессами. Другой пример ис- пользования нитей - это управление сигналами, такими как прерывание с клавиатуры (del или break). Вместо обработки сигнала прерывания, одна нить назначается для постоянного ожидания поступления сигналов. Таким образом, использование нитей может сократить необходимость в прерываниях пользовательского уровня. В этих примерах не столь важно параллельное выполнение, сколь важна ясность программы. Наконец, в мультипроцессорных системах для нитей из одного адресного пространства имеется воз- можность выполняться параллельно на разных процессорах. Это действительно один из главных путей реа- лизации разделения ресурсов в таких системах. С другой стороны, правильно сконструированные програм- мы, которые используют нити, должны работать одинаково хорошо как на однопроцессорной машине в ре- жиме разделения времени между нитями, так и на настоящем мультипроцессоре. 4. Синхронизация в распределенных системах К вопросам связи процессов, реализуемой путем передачи сообщений или вызовов RPC, тесно при- мыкают и вопросы синхронизации процессов. Синхронизация необходима процессам для организации со- вместного использования ресурсов, таких как файлы или устройства, а также для обмена данными. В однопроцессорных системах решение задач взаимного исключения, критических областей и дру- гих проблем синхронизации осуществлялось с использованием общих методов, таких как семафоры и мони- торы. Однако эти методы не совсем подходят для распределенных систем, так как все они базируются на использовании разделяемой оперативной памяти. Например, два процесса, которые взаимодействуют, используя семафор, должны иметь доступ к нему. Если оба процесса выполняются на одной и той же машине, они могут иметь совместный доступ к семафору, хранящемуся, например, в ядре, делая системные вызовы. Однако, если процессы выполняются на разных машинах, то этот метод не применим, для распределенных систем нужны новые подходы. Алгоритм синхронизации логических часов В централизованной однопроцессорной системе, как правило, важно только относительное время и не важна точность часов. В распределенной системе, где каждый процессор имеет собственные часы со сво- ей точностью хода, ситуация резко меняется: программы, использующие время (например, программы, по- добные команде make в UNIX, которые используют время создания файлов, или программы, для которых важно время прибытия сообщений и т.п.) становятся зависимыми от того, часами какого компьютера они пользуются. В распределенных системах синхронизация физических часов (показывающих реальное время) является сложной проблемой, но с другой стороны очень часто в этом нет никакой необходимости: то есть процессам не нужно, чтобы во всех машинах было правильное время, для них важно, чтобы оно было везде одинаковое, более того, для некоторых процессов важен только правильный порядок событий. В этом слу- чае мы имеем дело с логическими часами. Введем для двух произвольных событий отношение "случилось до". Выражение a ® b читается "a случилось до b" и означает, что все процессы в системе считают, что сначала произошло событие a, а потом - событие b. Отношение "случилось до" обладает свойством транзитивности: если выражения a ® b и b ® c истинны, то справедливо и выражение a ® c. Для двух событий одного и того же процесса всегда можно ус- тановить отношение "случилось до", аналогично может быть установлено это отношение и для событий пе- редачи сообщения одним процессом и приемом его другим, так как прием не может произойти раньше от- правки. Однако, если два произвольных события случились в разных процессах на разных машинах, и эти процессы не имеют между собой никакой связи (даже косвенной через третьи процессы), то нельзя сказать с полной определенностью, какое из событий произошло раньше, а какое позже. Ставится задача создания такого механизма ведения времени, который бы для каждого события а мог указать значение времени Т(а), с которым бы были согласны все процессы в системе. При этом должно вы- полняться условие: если а ® b , то Т(а) < Т(b). Кроме того, время может только увеличиваться и, следова- тельно, любые корректировки времени могут выполняться только путем добавления положительных значе- ний, и никогда - путем вычитания. Рассмотрим алгоритм решения этой задачи, который предложил Lamport. Для отметок времени в нем используются события. На рисунке 3.6 показаны три процесса, выполняющихся на разных машинах, каждая из которых имеет свои часы, идущие со своей скоростью. Как видно из рисунка, когда часы процесса 0 по- казали время 6, в процессе 1 часы показывали 8, а в процессе 2 - 10. Предполагается, что все эти часы идут с постоянной для себя скоростью. В момент времени 6 процесс 0 посылает сообщение А процессу 1. Это сообщение приходит к про- цессу 1 в момент времени 16 по его часам. В логическом смысле это вполне возможно, так как 6<16. Анало- гично, сообщение В, посланное процессом 1 процессу 2 пришло к последнему в момент времени 40, то есть его передача заняла 16 единиц времени, что также является правдоподобным. Рис. 3.6. Синхронизация логических часов а - три процесса, каждый со своими собственными часами; б - алгоритм синхронизации логических часов Ну а далее начинаются весьма странные вещи. Сообщение С от процесса 2 к процессу 1 было от- правлено в момент времени 64, а поступило в место назначения в момент времени 54. Очевидно, что это не- возможно. Такие ситуации необходимо предотвращать. Решение Lamport'а вытекает непосредственно из от- ношений "случилось до". Так как С было отправлено в момент 60, то оно должно дойти в момент 61 или позже. Следовательно, каждое сообщение должно нести с собой время своего отправления по часам маши- ны-отправителя. Если в машине, получившей сообщение, часы показывают время, которое меньше времени отправления, то эти часы переводятся вперед, так, чтобы они показали время, большее времени отправления сообщения. На рисунке 3.6,б видно, что С поступило в момент 61, а сообщение D - в 70. Этот алгоритм удовлетворяет сформулированным выше требованиям. 45 46 Алгоритмы взаимного исключения Системы, состоящие из нескольких процессов, часто легче программировать, используя так назы- ваемые критические секции. Когда процессу нужно читать или модифицировать некоторые разделяемые структуры данных, он прежде всего входит в критическую секцию для того, чтобы обеспечить себе исклю- чительное право использования этих данных, при этом он уверен, что никакой процесс не будет иметь дос- тупа к этому ресурсу одновременно с ним. Это называется взаимным исключением. В однопроцессорных системах критические секции защищаются семафорами, мониторами и другими аналогичными конструк- циями. Рассмотрим, какие алгоритмы могут быть использованы в распределенных системах. Централизованный алгоритм Наиболее очевидный и простой путь реализации взаимного исключения в распределенных системах - это применение тех же методов, которые используются в однопроцессорных системах. Один из процессов выбирается в качестве координатора (например, процесс, выполняющийся на машине, имеющей наиболь- шее значение сетевого адреса). Когда какой-либо процесс хочет войти в критическую секцию, он посылает сообщение с запросом к координатору, оповещая его о том, в какую критическую секцию он хочет войти, и ждет от координатора разрешение. Если в этот момент ни один из процессов не находится в критической секции, то координатор посылает ответ с разрешением. Если же некоторый процесс уже выполняет крити- ческую секцию, связанную с данным ресурсом, то никакой ответ не посылается; запрашивавший процесс ставится в очередь, и после освобождения критической секции ему отправляется ответ-разрешение. Этот алгоритм гарантирует взаимное исключение, но вследствие своей централизованной природы обладает низ- кой отказоустойчивостью. Распределенный алгоритм Когда процесс хочет войти в критическую секцию, он формирует сообщение, содержащее имя нуж- ной ему критической секции, номер процесса и текущее значение времени. Затем он посылает это сообще- ние всем другим процессам. Предполагается, что передача сообщения надежна, то есть получение каждого сообщения сопровождается подтверждением. Когда процесс получает сообщение такого рода, его действия зависят от того, в каком состоянии по отношению к указанной в сообщении критической секции он нахо- дится. Имеют место три ситуации: 1. Если получатель не находится и не собирается входить в критическую секцию в данный мо- мент, то он отсылает назад процессу-отправителю сообщение с разрешением. 2. Если получатель уже находится в критической секции, то он не отправляет никакого ответа, а ставит запрос в очередь. 3. Если получатель хочет войти в критическую секцию, но еще не сделал этого, то он сравнива- ет временную отметку поступившего сообщения со значением времени, которое содержится в его собствен- ном сообщении, разосланном всем другим процессам. Если время в поступившем к нему сообщении мень- ше, то есть его собственный запрос возник позже, то он посылает сообщение-разрешение, в обратном случае он не посылает ничего и ставит поступившее сообщение-запрос в очередь. Процесс может войти в критическую секцию только в том случае, если он получил ответные сооб- щения-разрешения от всех остальных процессов. Когда процесс покидает критическую секцию, он посылает разрешение всем процессам из своей очереди и исключает их из очереди. Алгоритм Token Ring Совершенно другой подход к достижению взаимного исключения в распределенных системах иллю- стрируется рисунком 3.7. Все процессы системы образуют логическое кольцо, т.е. каждый процесс знает номер своей позиции в кольце, а также номер ближайшего к нему следующего процесса. Когда кольцо ини- циализируется, процессу 0 передается так называемый токен. Токен циркулирует по кольцу. Он переходит от процесса n к процессу n+1 путем передачи сообщения по типу "точка-точка". Когда процесс получает то- кен от своего соседа, он анализирует, не требуется ли ему самому войти в критическую секцию. Если да, то процесс входит в критическую секцию. После того, как процесс выйдет из критической секции, он передает токен дальше по кольцу. Если же процесс, принявший токен от своего соседа, не заинтересован во вхожде- нии в критическую секцию, то он сразу отправляет токен в кольцо. Следовательно, если ни один из процес- сов не желает входить в критическую секцию, то в этом случае токен просто циркулирует по кольцу с высо- кой скоростью. Сравним эти три алгоритма взаимного исключения. Централизованный алгоритм является наиболее простым и наиболее эффективным. При его использовании требуется только три сообщения для того, чтобы процесс вошел и покинул критическую секцию: запрос и сообщение-разрешение для входа и сообщение об освобождении ресурса при выходе. При использовании распределенного алгоритма для одного использова- ния критической секции требуется послать (n-1) сообщений-запросов (где n - число процессов) - по одному на каждый процесс и получить (n-1) сообщений-разрешений, то есть всего необходимо 2(n-1) сообщений. В алгоритме Token Ring число сообщений переменно: от 1 в случае, если каждый процесс входил в критиче- скую секцию, до бесконечно большого числа, при циркуляции токена по кольцу, в котором ни один процесс не входил в критическую секцию. К сожалению все эти три алгоритма плохо защищены от отказов. В первом случае к краху приводит отказ координатора, во втором - отказ любого процесса (парадоксально, но распределенный алгоритм ока- зывается менее отказоустойчивым, чем централизованный), а в третьем - потеря токена или отказ процесса. Рис. 3.7. Средства взаимного исключения в распределенных системах а - неупорядоченная группа процессов в сети; б - логическое кольцо, образованное программным обеспечением Неделимые транзакции Все средства синхронизации, которые были рассмотрены ранее, относятся к нижнему уровню, на- пример, семафоры. Они требуют от программиста детального знания алгоритмов взаимного исключения, управления критическими секциями, умения предотвращать клинчи (взаимные блокировки), а также владе- ния средствами восстановления после краха. Однако существуют средства синхронизации более высокого уровня, которые освобождают программиста от необходимости вникать во все эти подробности и позволя- ют ему сконцентрировать свое внимание на логике алгоритмов и организации параллельных вычислений. Таким средством является неделимая транзакция. Модель неделимой транзакции пришла из бизнеса. Представьте себе переговорный процесс двух фирм о продаже-покупке некоторого товара. В процессе переговоров условия договора могут многократно меняться, уточняться. Пока договор еще не подписан обеими сторонами, каждая из них может от него отка- заться. Но после подписания контракта сделка (transaction) должна быть выполнена. 47 48 Компьютерная транзакция полностью аналогична. Один процесс объявляет, что он хочет начать транзакцию с одним или более процессами. Они могут некоторое время создавать и уничтожать разные объ- екты, выполнять какие-либо операции. Затем инициатор объявляет, что он хочет завершить транзакцию. Ес- ли все с ним соглашаются, то результат фиксируется. Если один или более процессов отказываются (или они потерпели крах еще до выработки согласия), тогда измененные объекты возвращается точно к тому со- стоянию, в котором они находились до начала выполнения транзакции. Такое свойство "все-или-ничего" облегчает работу программиста. Для программирования с использованием транзакций требуется некоторый набор примитивов, кото- рые должны быть предоставлены программисту либо операционной системой, либо языком программиро- вания. Примеры примитивов такого рода: BEGIN_TRANSACTION команды, которые следуют за этим примитивом, формируют транзакцию. END_TRANSACTION завершает транзакцию и пытается зафиксировать ее. ABORT_TRANSACTION прерывает транзакцию, восстанавливает предыдущие значения. READ читает данные из файла (или другого объекта) WRITE пишет данные в файл (или другой объект). Первые два примитива используются для определения границ транзакции. Операции между ними представляют собой тело транзакции. Либо все они должны быть выполнены, либо ни одна из них. Это мо- жет быть системный вызов, библиотечная процедура или группа операторов языка программирования, за- ключенная в скобки. Транзакции обладают следующими свойствами: упорядочиваемостью, неделимостью, постоянством. Упорядочиваемость гарантирует, что если две или более транзакции выполняются в одно и то же время, то конечный результат выглядит так, как если бы все транзакции выполнялись последовательно в не- котором (в зависимости от системы) порядке. Неделимость означает, что когда транзакция находится в процессе выполнения, то никакой другой процесс не видит ее промежуточные результаты. Постоянство означает, что после фиксации транзакции никакой сбой не может отменить результа- тов ее выполнения. Если программное обеспечение гарантирует вышеперечисленные свойства, то это означает, что в системе поддерживается механизм транзакций. Рассмотрим некоторые подходы к реализации механизма транзакций. В соответствии с первым подходом, когда процесс начинает транзакцию, то он работает в индивиду- альном рабочем пространстве, содержащем все файлы и другие объекты, к которым он имеет доступ. Пока транзакция не зафиксируется или не прервется, все изменения данных происходят в этом рабочем простран- стве, а не в "реальном", под которым мы понимаем обычную файловую систему. Главная проблема этого подхода состоит в больших накладных расходах по копированию большого объема данных в индивидуаль- ное рабочее пространство, хотя и имеются несколько приемов уменьшения этих расходов. Второй общий подход к реализации механизма транзакций называется списком намерений. Этот ме- тод заключается в том, что модифицируются сами файлы, а не их копии, но перед изменением любого блока производится запись в специальный файл - журнал регистрации, где отмечается, какая транзакция делает изменения, какой файл и блок изменяется и каковы старое и новое значения изменяемого блока. Только по- сле успешной записи в журнал регистрации делаются изменения в исходном файле. Если транзакция фикси- руется, то и об этом делается запись в журнал регистрации, но старые значения измененных данных сохра- няются. Если транзакция прерывается, то информация журнала регистрации используется для приведения файла в исходное состояние, и это действие называется откатом. В распределенных системах фиксация транзакций может потребовать взаимодействия нескольких процессов на разных машинах, каждая из которых хранит некоторые переменные, файлы, базы данных. Для достижения свойства неделимости транзакций в распределенных системах используется специальный про- токол, называемый протоколом двухфазной фиксации транзакций. Хотя он и не является единственным про- токолом такого рода, но он наиболее широко используется. Суть этого протокола состоит в следующем. Один из процессов выполняет функции координатора (рисунок 3.8). Координатор начинает транзакцию, делая запись об этом в своем журнале регистрации, затем он посылает всем подчиненным процессам, также выполняющим эту транзакцию, сообщение "подготовить- ся к фиксации". Когда подчиненные процессы получают это сообщение, то они проверяют, готовы ли они к фиксации, делают запись в своем журнале и посылают координатору сообщение-ответ "готов к фиксации". После этого подчиненные процессы остаются в состоянии готовности и ждут от координатора команду фик- сации. Если хотя бы один из подчиненных процессов не откликнулся, то координатор откатывает подчи- ненные транзакции, включая и те, которые подготовились к фиксации. Выполнение второй фазы заключается в том, что координатор посылает команду "фиксировать" (commit) всем подчиненным процессам. Выполняя эту команду, последние фиксируют изменения и завер- шают подчиненные транзакции. В результате гарантируется одновременное синхронное завершение (удач- ное или неудачное) распределенной транзакции. Рис. 3.8. Двухфазный протокол фиксации транзакции 5. Процессы и нити в распределенных системах |