Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 69
Текст из файла (страница 69)
Один из возникающих вопросов состоит в том, чтопроисходит, когда два процесса пытаются получить один и тот же ресурс в точности одновременно при помощи такой команды. Тут требуется какой-то механизм, принимающий решение, который из процессов получаетуправление. Такой механизм называется арбитром (arbiter). Обычно арбитры представляют собой аппаратныеустройства. К сожалению, можно доказать, что нельзя построить справедливого арбитра, работающего в 100%случаев, если не позволять арбитру принимать решение неопределенно долгое время.
Сущность этого явлениябыла открыта французским философом XIV века Жаном Буриданом в комментарии к De caelo Аристотеля.Буридан указал, что идеально разумная собака, помещенная между двумя одинаково привлекательными кусками еды, должна умереть от голода, поскольку она не сможет решить, к какому куску идти в первую очередь.3.4.
Параллелизм: время имеет значение297же время пытается обменять a2 и a1. Допустим, что процесс Петра доходит до некоторой точки внутри сериализованной процедуры, защищающей a1, и сразу вслед за этимпроцесс Павла входит в сериализованную процедуру, защищающую a2. Теперь Петр неможет двигаться дальше (ему надо войти в сериализованную процедуру для a2), покаПавел не выйдет из сериализованной процедуры для a2. Точно так же Павел не можетдвигаться дальше, пока Петр не выйдет из сериализованной процедуры для a1.
Обапроцесса замирают навеки в ожидании друг друга. Такая ситуация называется тупик(deadlock). В любой системе, которая предоставляет доступ к множественным разделяемым ресурсам, существует опасность тупика.В этой ситуации можно избежать тупика, если присвоить каждому счету уникальныйидентификационный номер, и переписать serialized-exchange так, чтобы процессвсегда пытался сначала войти в процедуру, которая защищает счет с наименьшим номером.
Хотя для задачи обмена это решение работает хорошо, бывают и другие ситуации,в которых требуются более развитые методы избежания тупиков, или где тупика нельзяизбежать в принципе. (См. упражнения 3.48 и 3.49.)48Упражнение 3.48.Подробно объясните, почему метод избежания тупиков, описанный выше (т. е.
счета нумеруются,и каждый процесс сначала пытается захватить счет с меньшим номером), в самом деле позволяетизбежать тупика в задаче обмена балансов. Перепишите serialized-exchange с использованием этой идеи. (Придется также изменить make-account, так, чтобы каждый счет создавалсявместе с номером, и чтобы этот номер можно было считать, послав соответствующее сообщение.)Упражнение 3.49.Опишите сценарий, в котором вышеописанный механизм избежания тупиков не работает. (Подсказка: в задаче обмена счетов каждый процесс заранее знает, к каким счетам ему нужен будетдоступ. Рассмотрите ситуацию, в которой процессу нужно сначала получить доступ к каким-торазделяемым ресурсам, прежде чем он сможет определить, какие ресурсы ему потребуются дополнительно.)Параллелизм, время и взаимодействиеМы видели, что для программирования параллельных систем, когда различные процессы имеют доступ к разделяемому состоянию, необходимо управление порядком событий, и мы видели, как можно добиться нужного порядка с помощью надлежащего использования сериализаторов.
Однако проблемы параллелизма лежат глубже, поскольку,с фундаментальной точки зрения, не всегда ясно, что имеется в виду под «разделяемымсостоянием».Механизмы вроде test-and-set! требуют, чтобы процессы в произвольные моменты времени имели доступ к глобальному разделяемому флагу. На современных высокоскоростных процессорах это реализуется сложно и неэффективно, поскольку, благодарясредствам оптимизации вроде конвейеров и кэширования памяти, содержимое памяти не48 Общий метод избежания тупиков путем нумерации разделяемых ресурсов и захвата их по порядку придумал Хейвендер (Havender 1968). В ситуациях, где тупика нельзя избежать, нужны меры по выходу из тупика(deadlock recovery), когда от процессов требуется «откатиться» из тупикового состояния и повторить попытку.Механизмы выхода из тупика широко используются в системах управления базами данных.
Эта тема детальнорассматривается у Грея и Рейтера (Gray and Reuter 1993).298Глава 3. Модульность, объекты и состояниеобязательно должно в каждый момент находиться в непротиворечивом состоянии. Изза этого в современных многопроцессорных системах идея сериализаторов вытесняетсяновыми подходами к управлению параллелизмом49.Кроме того, проблемы с разделяемым состоянием возникают в больших распределенных системах.
Например, рассмотрим распределенную банковскую систему, в которойотдельные местные банки поддерживают собственные значения баланса счетов и времяот времени сравнивают их со значениями, хранимыми в других местах. В такой системезначение «баланс счета» не будет определенным ни в какой момент, кроме как сразу после синхронизации. Если Петр вносит деньги на счет, который он делит с Павлом, когдамы должны считать, что баланс изменился, — когда меняется баланс в местном банкеили только после синхронизации? А если Павел обращается к счету через другую ветвьсистемы, какие ограничения нужно наложить на банковскую систему, чтобы ее поведение считалось «правильным»? Единственное, что может иметь значение для определения«правильности», — это поведение, которое Павел и Петр наблюдают по отдельности, исостояние счета сразу после синхронизации.
Вопросы о «настоящем» значении баланса или порядке событий между синхронизациями могут не иметь значения или дажесмысла50 .Общее в этих проблемах то, что синхронизация различных процессов, установлениеобщего состояния и управление порядком событий требуют взаимодействия процессов. Всущности, любое понятие времени при управлении параллельными процессами должнобыть прочно привязано к взаимодействию процессов51 . Любопытно, что похожая связьмежду временем и обменом информацией возникает в теории относительности, гдескорость света (самого быстрого сигнала, который можно использовать для синхронизации событий) служит универсальной константой, связывающей пространство ивремя. Сложности, с которыми мы сталкиваемся при работе с временем и состоянием ввычислительных моделях, могут на самом деле отражать фундаментальную сложностьфизического мира.3.5. ПотокиТеперь у нас есть ясное понимание того, как присваивание может служить инструментом моделирования, а также понятие о сложности проблем, связанных с ним.
Поразадать вопрос, нельзя ли организовать работу иначе и избежать части этих проблем.49 Один из подходов, альтернативных сериализации, называется барьерная синхронизация (barriersynchronization). Программист позволяет параллельным процессам выполняться как угодно, но устанавливаетопределенные точки синхронизации («барьеры»), так что ни один процесс не может продолжаться, пока все онине достигли барьера. Современные процессоры обладают машинными командами, которые позволяют программистам устанавливать точки синхронизации там, где требуется иметь непротиворечивое состояние. Например,в Power PCTM имеются две предназначенные для этого команды: SYNC и EIEIO (Enforced In-Order Executionof Input-Output, Гарантированно Последовательное Исполнение Ввода-Вывода).50 Такая точка зрения может казаться странной, но при этом существуют системы, которые именно так иработают. Изменения на счетах, связанных с кредитными картами, например, обычно поддерживаются отдельнов каждой стране, а изменения в различных странах согласовываются время от времени.
Таким образом, балансна счете может быть различным в различных странах.51 Для распределенных систем эта точка зрения исследовалась Лэмпортом (Lamport 1978). Он показал, какпри помощи взаимодействия установить «глобальные часы», через которые можно управлять порядком событийв распределенных системах.3.5. Потоки299В этом разделе мы исследуем альтернативный подход к моделированию состояния, основанный на структурах данных, называемых потоками (streams). Как нам предстоитубедиться, потоки могут смягчить некоторые трудности в моделировании состояния.Давайте сделаем шаг назад и рассмотрим еще раз, откуда происходят эти сложности.
Пытаясь моделировать явления реального мира, мы приняли несколько, казалосьбы, разумных решений: мы моделировали объекты внешнего мира, обладающие состоянием, при помощи вычислительных объектов с внутренними переменными. Мы отождествили течение времени в мире с течением времени в компьютере. Мы имитировалина компьютере изменение состояния моделируемых объектов при помощи присваиваниявнутренним переменным объектов-моделей.Возможен ли другой подход? Можно ли избежать отождествления времени в компьютере с временем в моделируемом мире? Должны ли мы заставить модель изменяться вовремени, чтобы смоделировать явления изменяющегося мира? Давайте подумаем об этомв терминах математических функций.
Можно описать изменение во времени величины xс помощью функции x(t), где время выступает как аргумент. Если мы сосредотачиваемвнимание на x момент за моментом, мы думаем об изменяющейся величине. Однако еслимы обращаем внимание на всю хронологию значений, мы не подчеркиваем изменение —функция сама по себе не изменяется52.Если время измеряется дискретными интервалами, мы можем смоделировать функцию времени как последовательность (возможно, бесконечную). В этом разделе мы увидим, как моделировать изменение в виде последовательностей, которые представляюткартины изменения во времени систем, подвергаемых моделированию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
