Введение в паралельные миры .NET 4.0

Перевод статьи Introduction to Parallelism in .NET 4.0 by Johnatan Cardy

В недалеком прошлом, процессоры имели как правило одно ядро, но благодаря тому что из года в год производители увеличивали его частоту, увеличивалась таким образом и общая производительность процессора. Это означало, что производительность многопоточного кода, написанного для одноядерного процессора хоть и несильно но все таки повышалась (одноядерные процессоры как правило могут только эмулировать выполнение нескольких потоков одновременно). В последние несколько лет, частота достигла своего определенного экстремума и теперь увеличение производительности процессоров осуществляется за счет увеличения количества ядер. Так, большинство процессоров сегодня обладают двумя и немного реже четырмя ядрами. Вместе с тем прослеживается тенденция, что и в будуем производительность процессоров будет прирастать в первую очередь за счет увеличения количества физических ядер.

Создание корректных паралельных программ сопряжено с определенными сложностями, возникающих в процессе разработки. К таким сложностям относятся синхронизация общих данных, поточная безопасность кода, исключение ситуаций гонок данных (race conditions) и блокировки данных (deadlocking) и многие другие вопросы. Зачастую решение данных проблем является очень затратным в как в плане времени так и в плане высокой стоимости квалифицированных сотрудников, способных решать подобные задачи. В данной статье я попробую познакомить читателей с новыми особенностями .NET 4.0, которые предназначены для помощи в написании масштабируемого кода, использующего возможности паралелизма, многопоточности и эффективного использования многоядерных процессоров.

Заметка: Термин «многоядерный» описывает процессор, содержащий большее количество ядер, чем количество выполняющихся процессов, а это может быть сотни или даже тысячи ядер. С этой точки зрения – паралелизм в программном обеспечении это ключ; нельзя сказать что система работает эффективно если количество имеющихся ядер больше количества потоков. Если вы считаете процессоры с таким количеством ядер мифическими, подумайте вот о чем – NVIDIA разрабатывает свои паралельные процессоры с учетом этих требований паралелизма. Например NVIDIA GTX280 GPU имеет 240 ядер, Tesla M20(http://www.nvidia.com/object/product_tesla_c1060_us.html) – целых 448. Intel также аннонсировала 50-ядерный процесор по кодовым названием «Knights Corner» (http://www.intel.com/pressroom/archive/releases/20100531comp.htm).

Часто, когда мы используем распаралеливание в наших приложениях, мы пишем код, который адаптирован к конкретному количеству ядер. Например, я хочу освободить мой UI поток посредством выполнения времязатратных вычислений в фоне. Таким образом, я запускаю мои операции вычисления в новом потоке, который беру из пула потоков. Но что если мой процессор имеет 4 ядра? Или 1000? Я же жестко запрограммировал использование только двух потоков. Это главный момент, который бы акцентирован в исследовательском отчете 'The Landscape of Parallel Computing Research: A View from Berkeley(http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.pdf)' университета Калифорнии Беркли в 2006 году. В частности там сказано:

«Главной целью должна быть возможность написать программу которая эффективно выполняется на высоко-распаралеленой вычислительной системе»

и -

«Для того что бы добиться успеха, программные модели не должны зависеть от количества процессоров»

Не беспокойтесь – все эти вопросы аддресуются реализации .NET 4.0, которая призвана изолировать разработчика от низкоуровневых концепций многопоточности. Сейчас мы должны сфокусироваться в первую очередь на том, что выполняется паралельно, а не как. С данным подходом, мы можем обеспечить в будущем гибкость и масшабируемость нашего программного обеспечения при использовании его на многоядерных системах. Px (Parallel Extensions) – широкий термин для для описания механизмов паралелизма в .NET 4.0. Он состоит из Task Parallel Library и PLINQ. Ниже, я вкраце опишу каждый из них, и как бонус представлю вашему вниманию Rx – Reactive Extensions – легкий фреймворк основанный на Px.

Task Parallel Library

(http://www.microsoft.com/downloads/en/details.aspx?FamilyID=86B3D32B-AD26-4BB8-A3AE-C1637026C3EE)

Данная библиотека помимо всего прочего содержит фуникции для распаралеливания циклов for и foreach, и вводит новый тип Task, который может использоватся как альтернатива ThreadPool. Данный тип используется для представления операции, которой может понадобиться некоторое время для ожидания без блокировки своего потока.

• Parallel.For и Parallel.ForEach: создает делегат Task для реализации тела цикла, которое будет вызываться паралельно.
  
• Parallel.Invoke: разрешает паралельные вызовы множества операций.
  
• Task.WaitAll: блокирует только главный поток, ожидая, пока завершатся все задачи, вместо того, что бы блокировать каждый поток в отдельности.
  
• Task.Factory.ContinueWhenAll: создает задачу (task) которая представляет выполнение определенного числа подзадач.
  

Предупреждение: Не стоит слишком переусердствовать приведением ваших паралельных алгоритмов к форме использующей паралельные конструкции если ваш код достаточно простой. Это связано с тем, что накладные расходы связанные с синхронизацией (для балансировки нагрузки потоков) и вызовы делегатов, которые осуществляются при выполнении задач, могут только все ухудшить.

PLINQ

(http://msdn.microsoft.com/en-us/library/dd997425.aspx)

PLINQ – это набор расширенных методов (extension methods) которые могут использоваться для паралельного выполнения запросов обычного LINQ. Сюда также входят дополнительные расширения которых нету в последовательном LINQ. Расширенные методы находятся в типе ParallelQuery<T>, который можно получить вызвав предварительно метод AsParallel() объекта IEnumerable. Ниже я представлю несколько расширений, для того что бы вы могли представить что входит в PLINQ:

• Select, Where, OrderBy, Aggregate, All, и.т.д.: Паралельные версии стандартных операторов.
  
• ForAll: Выполняет действие для каждого элемента коллекции ParallelQuery. Паралельно, разумеется.
  
• AsOrdered: Сигнализирует, что паралельный запрос должен вести себя как упорядоченный – таким образом, после того как все части паралельной операции завершениы, вы можете быть уверены что все элементы в коллекции результата, отсортированы в заданном порядке.
  
• AsUnordered: сигнализирует что запросу ParallelQuery не требуется получать результат в каком то определенном порядке. Эта логика используется по умолчанию.
  
• AsSequential: преобразует ParallelQuery в IEnumerable, вынуждая операцию выполнятся последовательно.
  
• WithCancellation: позволяет передавать токен отмены, делая возможным прерывание паралельной операции.
  
• WithExecutionMode: PLINQ иногда решает что выполнение операции последовательно более эффективно. Однако, если вам лучше известно как нужно осуществлять вычисление, вы можете форсировать это указав подобным образом что необходимо всегда выполнять операцию паралельно.
  

Предупреджение: Когда осуществляется замещение запросов паралельными версиями, все что вы хотите выполнить паралельно должно быть независимым друг от друга. Будте аккуратны с лямбда-выражениями, не позволяя им допускать побочные эффекты и сделайте их действительно паралельными.

Rx

(http://download.microsoft.com/download/C/5/D/C5D669F9-01DF-4FAF-BBA9-29C096C462DB/Rx%20HOL%20.NET.pdf)

Rx (Reactive Extensionы) похож на LINQ, но только работает как бы наоборот. В то время как LINQ представляет собой множество расширенных методов для IEnumerable, то Rx – это множество расширенных методов для IObservable. Главным моментом здесь является тот факт, что IObservable является математическим двойником IEnumerable – коллекция IEnumerable – это коллекция для извлечений (pull collection), а IObservable – коллекция для размещения (push collection). Эти коллекции и эквиваленты и противоположны друг другу одновременно. Вместо того, что бы запрашивать каждый элемент в отдельности из коллекции, как бы вы поступали в случае с IEnumerable, для IObservable действует другая логика – вы получаете уведомление каждый раз, когда новый элемент помещается в коллекцию и еще одно уведомление когда достигается конец коллекции.

Подождите, но каким образом это имеет отношение к паралелизму о котором мы говорим в данной статье? Что же, у Rx непосредственное отнощение к паралелизму, с его помощью становится возможным комбинировать данные из асинхронных источников в вашем приложении. Эти асинхронные источники могут быть частью различных паралельных вычислений – или если говорить об этом более простыми словами, то они, например, могут передаваться через разные UI события из различных потоков. IObservable будет осуществлять обработку всех сложных моментов, с которыми сопряжена работа с несколькими потоками, а разработчик может сфокусироваться непосредственно только на своей прикладной задачей. Стоит отметить, что Rx зависит от Px, так как глубоко в своих недрах он использует операции Px.

В следующем примере, создается IObservable который ссылается на источник. После это осуществляется вызов Subscribe для данного источника и передача некоторых действий, которые необходимо выполнить для каждого элемента, по достижению конца коллекции и в случае ошибки:

IObservable<int> source = Observable.Empty<int>();

Как только вы создали свой источник, вы должны подписаться на уведомления. Это осуществляется с помощью метода Subscribe:

IDisposable subscription = source.Subscribe(

item => {}, //что-то делаем с элементом коллекции

ex => {}, //обрабатывает исключение

() => {} //что-то делаем при завершении коллекции

);

В примере выше у нас в качестве источника используется пустая коллекция, и поэтому мы просто получим уведомление OnCompletion. Очевидно, что с пустой коллекции толку мало, ниже представлен список ситуаций, где и как можно создать IObservable:

• Можно создать коллекцию IObservable из какого-то вычисления, выполняемого длительное время, и реализовать код, который асинхронно обрабатывает результат по мере его появления.
  
• Можно накапливать данные получаемые посредством ввода пользователя в коллекции IObservable, например – события передвижения мыши можно представить как бесконечную коллекцию элементов которые представляют собой текущие координаты мыши.
  
• Любое другое событие .NET может быть использовано для создания IObservable с помощью использования метода Observable.FromEvent.
  

Доступно большое количество расширенных методов LINQ – Where, Select, Skip – они делают то же что и в случае с обычным LINQ. Ниже представлен упрощенный пример исходного кода с использованием IObservable, который был взят из документации Hands On Labs, которые я рекомендую к прочтению, если вы планируете использовать Rx в своей работе.

//прослушиваем событие TextChanged для textbox

var src = Observable.FromEvent<EventArgs>(textBox, "TextChanged").Select(evt => ((TextBox)evt.Sender).Text) //получаем текст

.Throttle(TimeSpan.FromSeconds(1)) //максимум 1 сообщение в секунду

.DistinctUntilChanged(); //Игнорируем эквивалентные дубликаты

//Вызываем ObserveOn для синхронизации с потоком UI, и записываем текст в метку.

using(src.ObserveOn(label).Subscribe(

txt =>

{

label.Text = txt;

})

{

Application.Run(frm);

}

Оригинальный пример из документации который я рассмотрел выше идет немного дальше – отсылает элементы в хранилище через веб-сервис (у Rx имеется встренная поддержка асинхронной работы с веб-сервисами), получает ответ, вызывает SelectMany для того что бы поставить полученные результаты в соответствие с инициировавшим их запросом и помещением их в ListView. И все это помещается буквально в нескольких строчках, причем никакого спагетти-кода, все чинно и интуитивно понятно.

Выводы

Целью данной статьи является поверхностное знакомство с особенностями реализации паралелизма, которые существуют в .NET 4.0 и я старался изо всех сил не вдаваться в ненужные подробности. Например, из того что я не рассмотреть, стоит обязательно отметить что существует поддержка обработки исключений, возникающих при паралельных вычислениях, определение количества задач (потоков) выполняемых в фоне и управление этими задачами – все эти вещи так и иначе будут использоваться в реальных приложениях. Помимо этого, фреймворк содержит огромное количество другой функциональности, о которой я не упомянул даже вскольз.

Я надеюсь, сейчас вы понимаете потребности и возможности поддержки паралельных вычислений, существующих в .NET. Если какая либо из описаных выше возможностей вас заинтересовала, обратитесь за дополниетльной информацией к источникам, которые представлены гиперссылками в статье. Я это крайне рекомендую, так как чувствую, что в будущем эта информация будет чрезвычайно полезной и обязательной для любого .NET разработчика.

Спасибо, Джонни

 

Пишем свое облако тегов

Для группировки элементов списка часто применяют иерархическую структуру. Примером такой структуры может быть файловая система. В ней есть директории, внутри директорий находятся файлы и другие директории. Соответственно в этих директориях свои файлы и директории. Таких нехитрым образом можно к примеру группировать какие то документы. Например в одной директории находятся документы связанные с работой, в другой – персональные документы. Дальше, например в директории с рабочими документами есть свои директории, к примеру директория с финансовыми документами, директория со справками и директория с черновиками. Казалось бы – все есстественно, и разве как-то может быть иначе? Оказывается может. Другой вариант, который я хочу рассмотреть в данной статье – использование меток (тегов) для описания принадлежности нашего документа какой то категории. Например, рабочий документ содержащий какую-то справку – можно пометить двумя метками: «работа», и «справка». В этом случае это будет равосильно тому, как если бы данный документ находился в директории "справки" который в свою очередь – в "работа".

Очевидных преимуществ подхода с метками по сравнению с иерархической моделью достаточно – к примеру для того что бы один и тот же документ «находился в разных директориях» достаточно добавить ему соответствующую метку. В случае с иерархической моделью пришлось бы копировать документ в требуемую директорию. А в случае когда потребовалась бы модификация документа – пришлось бы редактировать как оригинал так и все его копии. Подход использующий метки позволяет абстрагироваться от того, где и как хранится документ и избавляет от необходимости создавать копии для различных «директорий». Документы храниться не только непосредственно в файловой системе, а в любом удобном для этого месте: FTP, базы данных, удаленный сервер. Еще одним преимуществом использования меток явлется возможность визуального отображения статистики - каких документов больше, а каких меньше в заданной «директории». Чем больше документов – тем большим шрифтом отображается метка, и наоборот. Этот прием думаю всем знаком – облако тегов – популярный элемент в современных страницах.

Давайте посмотрим на реализацию данного подхода изнутри с технической точки зрения.

Облако тегов изнутри

Элемент управления предназаначен для отображения меток. Сам по себе он представляет собой простой слой (div), в котором находятся ссылочные метки. У каждой метки – соответсвенно свой текст и свой размер шрифта. По нажатию на метку осуществляется вызов серверного обработчика, который инициирует событие TagClicked. Событие помимо всего прочего содержит информацию о том, на какую метку кликнул пользователь.

Ниже представлена ASP разметка элемента управления.

<div style="width:100%; height:100%;">
<asp:Repeater id="cloudCtrl" runat="server">
<ItemTemplate>
<asp:LinkButton OnClick="OnClick" runat="server" Text='<%# DataBinder.Eval(Container.DataItem, "Key") %>'
Font-Size='<%# DataBinder.Eval(Container.DataItem, "Value") %>' />
</ItemTemplate>
</asp:Repeater>
</div>

Code-Behind облачного элемента управления состоит из двух частей.

К первой относятся свойство Items и метод ProcessItems. Они предназначены для инициализации облачного элемента. Для каждой метки, которая будет оборажатся задано текстовое описание и размер шрифта, который будет использоваться для данной метки.

public
Dictionary<string, int> Items
{ set { ProcessItems(value); } }

private void ProcessItems(Dictionary<string, int> list)
{
cloudCtrl.DataSource = list.ToDictionary(i => i.Key, i => new
FontUnit(i.Value));
cloudCtrl.DataBind();
}

Стоит отметить что при инициализации в элемент управления передается информация об размере шрифта. На первый взгляд может показаться что было бы неплохо, что бы вместо размера шрифта сюда передавалось число определяющее, сколько раз данная метка использовалась, а уже сам контрол на основании этой информации мог бы сам определять размер шрифта. Но в таком случае было бы невозможно адаптировать элемент к различным условиям. Например, если ожидается что число использований меток будет небольшое – то размер шрифта должен изменяться быстрее, чем в случае когда количество использований предполагается большим. В иных случаях может понадобится изменять размер шрифта не по тому сколько раз встречается та или иная метка, а по некоторой другой информации, специфичной для конкретного случая. Передавая при инициализации размер шрифта – мы тем самым предоставляем право клиентскому коду самому решать когда какой размер шрифта меток должен быть.

Вторая часть представляет собой обработчик нажатия на метку и генерацию события TagClicked, которое будет обработано клентским кодом.

public class StringEventArgs : EventArgs
{
  public string Value { get; set; }
  public StringEventArgs() { }
  public StringEventArgs(string val)
  {
  Value = val;
  }
}

public event EventHandler<StringEventArgs> TagClicked;

protected void OnClick(object sender, EventArgs args)
{
  var btn = sender as LinkButton;
  if(btn!=null)
  {
   if (TagClicked != null)
   TagClicked(this, new StringEventArgs(btn.Text));
  }
}


Клиентский код



При помещении нашего облака на страницу необходимо следующую разметку:

<%@Register TagPrefix="my" TagName="TagControl" Src="~/Controls/CloudControl.ascx" %>
...
<my:TagControl OnTagClicked="OnTagClicked" runat="server" id="tagCtrl"/>

С Code-Behind дело немного сложнее, но так же все очень просто.

Инициализация облачного элемента

protected void Page_Load(object sender, EventArgs e)
{
    // получаем все метки известные системе, и информацию о том сколько раз каждая метка используется
Dictionary<string, int> dic = DataProvider.GetTagsStatistic();
// инициализируем облачный контрол
tagCtrl.Items = dic.ToDictionary(pair => pair.Key, pair => GetFontSize(pair.Value));
...
}

Обратите внимание на метод, которые устанавливает размер шрифта метки исходя из информации о том сколько раз метка была использована

private int GetFontSize(int num)
{
/* 1 использование - 8px
* 2-3 - 11px
* 4-7 - 14px
* 8-15 - 17px
* 16-31 - 20px
* и так далее
*/

int pow = 0;
while(num > 1)
{
  pow++;
  num = num >> 1;
}
return 8 + pow*3;
}

Обработка нажатия на метку.

protected void OnTagClicked(object sender, StringEventArgs e)
{
  string label = e.Value;
  // в зависимости от выбранной метки осуществляем фильтрацию наших данных
...
}

Вот пожалуй и все, облачный элемент управления готов к использованию. Понятное дело, что это только базовая функциональность. Продвигаясь дальше – можно разрисовывать метки в различные цвета в зависимости от релевантности окружения, можно добавить кнопку Reset по нажатию на которую будет осуществляться сброс текущей фильтрации, что бы пользователь смог отобразить все элементы.

Так или иначе мне кажется что использование меток в таком ключе, намного более выгодное и гибкое решение чем использование иерархий и древовидных контролов. Да и выглядит все это более дружелюбно и интуитивно для конечного пользователя.

Git me!

Практически любой процесс разработки программного обеспечения в которой принимает участие как минимум несколько человек не обходится без использования системы контроля версий (version control system). Думаю для любого разработчика это не является открытием и всякий наверняки знаком с такими системами. До недавного времени наиболее распространенными числились Subversion (svn) и mercurial. В моих кругах имело место также использование Visual Source Safe (vss) – но я не считаю это за тренд, скорее наооборот пережиток прошлого.

С недавних же пор все чаще стали говорить и использовать «новую» систему контроля версий - Git. Создателем ее является небезызвестный Линус Торвальдс, которого не устроили существующие продукты и он опять решил перевернуть весь мир. Если посмотреть в будущее, даже самое недалекое, то мне кажется, что Git в скором времени может затмить собой и Subversion и Mercurial и все остальные системы вместе взятые.

В чем же причина? В фуникциональности и удобстве. Не буду описывать все плюшечки и бенефиты системы, наверняка вы и сами сможете с ними разобраться. Уже сегодня есть целые ресурсы, которые посвящены именно подобным вопросам. Например, вот этот http://whygitisbetterthanx.com

Разумеется, для того что бы оценить систему, нужно испробовать ее в работе.

В данной статье я хочу поделиться вариантом работы с системой который использую сам и члены команды в которой я работаю.

Я работаю под Windows и все операции провожу с использованием утилиты Git Bash. Для ее запуска необходимо выбрать в проводнике (или чем вы там еще пользуетесь) директорию с проектом и через контекстное меню запустить Git Bash.

Для начала работы необходимо получить Git репозиторий. Для этого воспользуемся коммандой git clone. Команда принимает только один параметр – URL родительноского репозитория

git clone ssh://here_is_your_url.com/project.git

После выполнения мы получим локальную копию репозитория в директории из под которой вызвали Git Bash. Команда выполняется только один раз когда у нас еще нету репозитория.

После этого можно работать с файлами проекта, редактировать, добавлять и удалять. После того как назрела необходимость зафиксировать изменения, опять запускаем Git Bash и выполняем команду git status. Команда призвана показать какие изменения были произведены. Увереные в себе люди могут этой командой не пользоватьсяJ

Далее необходимо добавить файлы которые будут закомичены. Для это я использую:

git add .

Команда подготовит все файлы, в том числе и новые, которых в репозитории нету.

Иногда возникает необходимость не добавлять какие то файлы или даже целые директории, например папки Debug, bin или файлы с расширением *.obj. Для этого целесообразно добавить нежелательные файлы в исключения, которые описываются файлом .gitignore. Просто создайте файл .gitignore в корне репозитория и добавьте содержимое, которое должно игнорироваться гитом. Например для случая, который я расмотрел выше содержимое файла будет следующим:

Debug

Bin

*.obj

После того как все файлы подготовлены делаем коммит:

git commit –m "Message of the commit"

После этой команды данные попадают не в удаленный репозиторий, а во временный, локальный. Для того что бы данные зафиксировать окончательно нужно произвести еще несколько действий.

Получаем обновления из удаленного репозитория, наверняка пока мы работали уже кто-то что-то обновил.

git fetch

Теперь начинается магия – мы склеиваем полученную удаленную версию с нашей локальной. Для этого используем rebase.

git rebase origin master

Если в процессе склеивания конфликтных ситуация не было, то работа практически сделана – все что нам нужно – это отослать изменения на сервер:

git push

Если же возникли сложности при ребейсе, я использую araxis merge для фикса конфликтов. Хотя на самом деле можно использовать любой другой инструмент – тут личное дело каждого. Настройки утилит мерджинга задаются в файле .gitconfig а сам файл находится в пользовательской папке (С:\users\me). Что бы настроить araxis или любой другой инструмент нужно в этом файле указать следующее:

[diff]

    tool = araxis

[difftool "araxis"]

    path = full_path_to_exe

[merge]

    tool = araxis

[mergetool "araxis"]

    path = full_path_to_exe

Вернемся к команде rebase которая не смогла выполнится из-за наличия конфликта. Для разрешения конфликта пользуемся командой:

git mergetool

Команда откроет araxis и там необходимо зарезолвить конфликт и сохранить все файлы которые имеют отношение к кнофликту. Необходимо отметить что araxis будет вызван ровно столько раз сколько кофликтных файлов у нас имеется.

После того как все конфликты исправлены, завершаем rebase следующей командой:

git rebase --continue

После того как rebase завершен, как и в случае когда конфликтов не было не забываем заливать все изменения на сервер командой git push.

Вот и все.

Как в хранимую процедуру передать массив

Не так давно у меня возникла необходимость передать в хранимую процедуру массив целочисленных значений. Далее в процедуре мне нужно быть что то сделать с каждым переданным числом. Занявшись поиском решения которое меня устроило бы в сложившейся ситуации я несколько увлекся, что привело к написанию данной статьи.

Итак, вариантов у меня получилось три.

Первый вариант – как говорится, вариант в лоб – передача в хранимку CSV-строки с последующей обработкой. Несмотря на то что это самый очевидный вариант, кода в данном случае придется писать больше чем в любом другом. Причиной этого является не очень гибкий набор T-SQL функций для работы со строками. Производительность такого способа будет не на высоте да и в плане наглядности кода – выгглядит он слегка загруженно. Вот как выглядит фрагмент обработки CSV-строки на языке T-SQL:

--

DECLARE @x VARCHAR(500)

SET @x = '111,222,333'



DECLARE @pos INT

DECLARE @piece VARCHAR(500)

DECLARE @table TABLE(id INT)



IF RIGHT(RTRIM(@x),1) <> ','

SET @x = @x + ','



SET @pos = PATINDEX('%,%' , @x)

WHILE @pos <> 0

BEGIN

SET @piece = left(@x, @pos - 1)



INSERT INTO @table

SELECT CAST(@piece AS INTEGER)



SET @x = STUFF(@x, 1, @pos, '')

SET @pos = PATINDEX('%,%' , @x)

END



SELECT t.id AS id FROM @table t

Другой способ передачи массива чисел, это использование конструкций OPENXML. Проблем в данном решении несколько: во-первых нужно дополнительно затрачивать усилия на генерацию соответствующего XML на вызывающей стороне, а во-вторых: не очень высокая производительность при больших объемах данных. Связано это с тем что в данном случае на сервере выделяются большие объемы памяти для работы с XML. Основным же достоинством данного подхода является относительная простота и тот факт что данные конструкции будут работать на SQL сервере версией ниже 2005.

Пример кода представлен ниже:

--

DECLARE @idoc int

DECLARE @x VARCHAR(400)

SET @x = '<Root><item num=''111''/><item num=''112''/><item num=''113''/></Root>'



EXEC sp_xml_preparedocument @iDoc OUTPUT, @x

SELECT CAST(num AS INTEGER) FROM OPENXML(@iDoc, '/Root/item')

WITH ( num varchar(5) )

EXEC sp_xml_removedocument @iDoc

Последний способ – это использование типа XML который появился в SQL Server 2005. Для данного типа предусмотрены соответствующие методы которые позволяют выполнять базовые операции с типом. Перечень всех методов я приводить не буду, ограничусь лишь примером их использования для решения моей задачи. Как видим последний способ является наиболее лакончиным и максимально эфективным.

--

DECLARE @x XML

SET @x = '<Root><num>111</num><num>112</num><num>113</num></Root>'

SELECT T.c.value('.', 'integer') AS id FROM @x.nodes('/Root/num') AS T(c)




 

Какой сервис использовать в Silverlight?

Большинство Silverlight приложений используют различного рода сервисы для связи с внешним миром. Для таких задач, как работа с базой или обращение к серверной логике для осуществления каких-то вычислений это и вовсе практически единственно возможный способ. Сама же платформа Silverlight в процессе своего взросления получает поддержку все большего количества различных типов сервисов. Для непросвещенного программиста, который только знакомится с Silverlight крайне сложно определиться, что и когда стоит использовать. Данная статья призвана вкраце описать возможные типы поддерживаемых сервисов и попытаться помочь сделать осмысленный выбор.

Сервисы WCF и ASMX

При создании сервисов в .NET большинство разработчиков выберут WCF (Windows Communication Foundation). WCF появился в .NET 3.0 и был предназначен для упрощения процесса построения сервисо-ориентированных приложений. Целью данного программного фреймворка ялвяется унификация нескольких различных API взаимодейстия, таких как Remoting, "классические" веб-сервисы (ASMX) и так далее.

WCF получил широкое распространение и поэтому неудивительно что Microsoft предоставляет его поддержку и в Silverlight. В данный момент связка Silverlight - WCF является наиболее распространенной по сравнению с другими технологиями, предназначенными для реализации коммуникации приложений Silverlight с внешним миром. Если вы являетесь начинающим программистом, выбор WCF будет вероятнее всего наиболее предпочтительным.

ASMX или классические веб-сервисы также являются широко распространнеными. Их также можно использовать вместе с Silverlight, однако у него нету всех тех преимуществ, которые предоставляет WCF.

Еще Silverlight 2 обладал поддержкой дуплексного соединения через сервисы WCF. Однако, несмотря на то, что этот режим был возможным, он был трудно реализуемым. С появлением Silverlight 3 дуплексное взаимодействие с WCF через HTTP стало намного проще. Silverlight 4 добавил поддержку протокола net.tcp. И сегодня мы можем реализовать как однонаправленный так и двухнаправленный протокол взаимодействия с намного более высокой производительностю предоставляемой привязкой net.tcp.

Говоря о производительности, в Silverlight 3 была добавлена поддержка бинарного кодирования передаваемой информации, что в итоге приводило к более быстрой передаче данных. Также, появилась поддержка обработки сбоев. До появления Silverlight 3 происходившие сбои сервиса были невидимыми для Silverlight. Это вынуждало заниматься очень тяжелой отладкой. Сейчас такие ситуации – безвозвратно ушедшее прошлое.

 

REST и WCF Data Services

В то время как ASMX и WCF это очень мощные инструменты которые способны предложить решение практически для любой ситуации, иногда их использование бывает избыточным. Бывают такие случаи, что необходимо просто передавать текстовую информацию, как правило JSON (JavaScript Object Notation) или XML, от сервера к приложению Silverlight.

Протокол используемый для таких целей называется REST (Representational State Transfer). В сравнении с веб-сервисами (WCF или ASMX) REST обладает рядом преимуществ которые могут быть существенными для Silverlight. Передаваемой информацией является текст, удобный для чтения человеком, как правило в XML формате, не перегруженный излишней разметкой. Сообщения SOAP – формат веб-сервисов – также XML, но в пакете SOAP содержится много служебного XML который сильно затрудняет прозрачное понимание текста человеком. Использование REST приведет к тому, что по сети будет передано меньше информации, что в итоге положиетльно скажется на пропускной способности и производительности приложения. Таким образом, REST более легок для понимания и к тому же платформо-независим. Его использование не требует дополнительного программного обеспечения поскольку работает поверх стандартного HTTP протокола.

Являются ли сервисы RESTful (сервисы которые следуют принципам REST часто называются RESTful) трендом? На этот вопрос можно с уверенностью ответить положительно. Сегодня много больших веб-приложений, такие как Flickr, Facebook, Twitter, YouTube предлагают свои возможности благодаря использованию API RESTful (коллекции сервисов REST). .NET обладает исчерпывающей поддержкой RESTful сервисов. Silverlight может беспрепятственно использовать такие сервисы.

 

WCF RIA

Microsoft WCF RIA Services – это фреймворк, задачей которого является упрощение разработки RIA-решений. Сервисы RIA призваны решать вопросы сложности и несогласованности, которые могут возникнуть в процессе создания N-уровневой архитектуры приложения, основанной на использовании фреймворков, элементов управления и сервисов серверной платформы ASP.NET и клиентского Silverlight приложения.

Сервисы RIA делают простым процесс передачи данных от вашего сервиса к клиенту. Это происходит благодаря тому, что при написании сервисов, которые связаны с источниками данных (базы данных, отдельные пользовательские классы, Entity Model и т.д.) на серверной стороне, позже осуществляется  генерация этих элементов на клиентской стороне. В процессе генерации также создается необходимый контекст, методы и операции, необходмые для взаимодействия с требуемым сервисом. Таки образом, по своей сути сервисы WCF RIA – это серверная технология, которая отображает серверный код на клиенте используя WCF для коммуникации. В дополнение ко всему данный фреймворк делает возможным интегрировать валидацию и аутентификацию для используемых сервисов и передаваемых объектов.

Модели памяти: Причина переосмысления параллельных языков и аппаратного обеспечения

Перевод статьи: Sarita V. Adve, Hans-J. Boehm «Memory Models: A Case for Rethinking Parallel Languages and Hardware»

Преамбула

Эра параллельных вычислений для массовго использования уже наступила, но написание корректной параллельной программы все еще остается намного более сложной задачей, чем написание последовательной программы. За исключением отдельных случаев, большинство параллельных программ использует подхода разделяемой (shared) памяти. Модель памяти, которая определяет значение разделяемых переменных, является основополагающим моментом разработки подобным способом. К сожалению, в таком случае приходится выбирать между программируемостью и производительностью, что, очевидно, является областью наиболее подверженной обсуждению как в спецификациях языков программирования, так и в архитектуре аппаратного обеспечения. Повышенное внимание к данному вопросу в конце концов привели к необходимости в подобных дебатах, в которых обсуждается использование популярных языков програмирования, таких как C++ и Java, и опубликованных спецификаций совместимой модели памяти большинства производителей аппаратного обеспечения. Несмотря на то, что подобные дебаты уже сами по себе являются неоспоримым достижением, были выявлены фундаментальные недостатки в современных языках и системах, которые ограничивают дальнейшее развитие безопасного параллельного программирования.

В данной статье обсуждается путь решения возникших сложностей, с поясняющими примерами и их реализацией. Краеугольным камнем предшествующих дебатов были заключения, сводящиеся к тому, что модель памяти должна представлять собой контракт между программистом и системой, и если программист пишет корректные программы (не подверженные гонкам данных (data-race-free)), система предоставит высокий уровень программируемости (последовательную согласованность) и производительность. В статье мы уделим внимание вопросу, почему данная точка зрения является  наилучшим решением для современных языков программирования, и почему недостаточно просто двигаться вперед. Мы рассмотрим возможные направления, призванные устранить большинство проблем связанных с моделью памяти, но требующие проведения ревизии для существующих языков программирования и аппаратного обеспечения. В частности, мы будем говорит о том, что параллельниые языки должны не только предлагать высокоуровневые модели использования, но также и принуждать их использовать. Дальше, для масштабируемости и эффективной производительности, аппаратное обеспечение должно быть спроектированно с учетом этих моделей, для того что бы в полной мере воспользоваться ими. Рассмотренные недостатки и необходимость в дальнейшем исследовании существующих вопросов, которые мы выделили, имет большое значение для практики, исследований и обучения во многих дисциплинах компьютерных наук, теорий программного и аппаратного обеспечения.

Введение

Большинство существующих параллельных программ написаны с использованием потоков и разделяемых переменных. Хотя здесь нету согласованности с моделью параллельного программирования, все же существует много причин популярности использования потоков. Сущности потоков поддерживались большинством распространенных операционных систем еще до того, как многоядерных процессоры стали  массово использоваться. Причиной этого является то, что использование потоков может быть полезным и для других задач. Непосредственная поддерждка разделяемой памяти аппаратным обеспечением потенциально предоставляет преимущество в производительности, например, предоставление возможности совместного чтения данных без дополнительных затрат. Способность передавать ссылку на память между потоками делает более простым представления сложных данных для совместного доступа. Наконец, разделяемая память делает возможным более простое распараллеливание ключевых частей программы без необходимости глобального изменения структур данных.

Модель памяти, или модель согласованности (consistency) памяти, находится в центре семантики параллелизма программ и систем с разделяемой памятью. Она определяет подмножество значений, для которых разрешено чтение в программе, определяя тем самым базовую семантку разделяемых переменных. Она отвечает на вопрос: Достаточен ли реализованный механизм синхронизации для того,  что бы требуемая операция записи достоверно осуществлялась перед операцией чтения? Могут ли два потока писать в смежные поля памяти в одно время? Должно ли конечное значение быть таким, какое оно было в момент последней записи?

Модель памяти определяет интерфейс между программой и другим аппаратным или программным обеспечением, которое может изменить эту программу (например компилятор, виртуальная машина или динамический оптимизатор). Невозможно детально рассуждать о программе (написанной на высокоуровневом байт-коде, ассемблере или машинном языке) или какой-либо части реализации языка (включая аппаратную составляющую) без точно определенной модели памяти.

Сложная модель памяти делает процесс написания параллельных программ и процесс обучения написанию таких программ более сложным. Такая вот программа, написанная не совсем корректно, может ограничить аппаратную оптимизацию и оптимизацию компилятора, значительно уменьшая производительность. С введением единого интерфейса, решение модели памяти имеет долгосрочный эффект, оказывая влияние на переносимость и легкость сопровождения программ.Таким образом архитектура аппаратного обеспечения, реализованная с учетом строгой модели памяти не может быть использована с примененим более слабой модели без нарушения бинарной совместимости, и новая версия компилятора с более слабой моделью памяти  может потребовать модификации уже существующего кода. Таким образом, модель памяти применяемая в одном компоненте должна учитывать модели памяти всех остальных компонентов системы. Производитель процессоров не может гарантировать строгую модель аппаратного обеспечения если проектировщик системной памяти предоставляет более слабую модель; строгая модель аппаратного обеспечения не очень полезна для разработчиков, использующих языки программирования и компиляторы, обеспечивающие только слабые гарантии.

Однако, главная роль модели памяти часто недооценивается. Это частично связано с тем, что формально задать модель, которая сможет управлять всеми возможными свойствами программируемости, производительности и переносимости необычайно сложно. В то же время, неформально, машинозависимые описания были наиболее прменимыми в эпоху, когда параллельное программирование было уделом экспертов и достигая максимально высокого уровня производительности приходилось жертвовать параметрами программируемости и переносимости.

В конце 80х и 90х, данная область получила внимание преимущественно в среде разработчиков аппаратного обеспечения, где многие подходы [2] исследовались в плохой согласованности. Описания коммерческой аппаратной модели памяти имели существенно отличались в точности, включая случаи полного игнорирования отдельного раздела и некоторых отраженных нежеланий изготовителя сделать требуемые пояснения для непрозрачных особенностей использования в будущем. Хотя модель памяти влияет на значение каждой загруженной инструкции в каждом многопоточном приложении, она иногда все еще относится к разделу «системноого программирования» в руководстве по архитектуре.

Еще одним из сложных моментов для архитекторов программного обеспечения было отсутствие прозрачной модели памяти на уровне языков программирования – было непонятно что разработчики программного обеспечения должны ожидать от аппаратного обеспечения с которым работают. Несмотря на это, исследователи, работающие в области аппаратных средств предложили способ избавться от данной проблемы [3], для всеобщего признания было необходимо найти консенсус со стороной разработчиков программного обеспечения. До 2000 года, существовало несколько программных окружений, которые учитывало данную публикацию с относительной степенью совместимости [37], но наиболее распространенные окружения имели невнятные спецификации, которые провоцировали возникновение многих вопросов [29, 9]. Даже если спецификации были достаточно понятны, они часто нарушались в целях повышения производительности [9], что способствовало непониманию многих моментов реализации даже экспертами, и были сложны в изучении.

С 2000 года мы приступили к попыткам четко специфицировать модель памяти на уровне языков программирования, в первую очередь для Java и C++, к попыткам адапатировать подобные модели для C и других языков. В процессе нашей работы, мы должны были решать вопросы возникающие в процессе использования различного аппаратного обеспечения, которые не способствовали созданию прозрачной программной модели. Иногда было сложно найти компромис между простой и удобной програмной моделью и адекватной производительностью на существующем аппаратном обеспечении.

Сегодня, языки программирования и большинство изготовителей аппаратного обеспечения имеют (или планируют) совместимые спецификации моделей памяти. Хотя данный момент является неоспоримым достижением на фоне драматического прошлого, он подвержен фундаментальным недостаткам в существующих параллельных языках программирования и их взаимодействии с аппаратной частью. По прошествии десятилетий потраченных на исследования, до сих пор остается чрезвычайно сложно описывать, скажем, какой уровень допустимой нагрузки можно разрешить для системы без ущерба для действующих гарантий безопасности или реализаций используемых методологий. Для нас, полученный опыт позволил понять, что решение проблем моделей памяти требует существенно новых исследований, охватывающих различные области: параллельные языки, аппаратное обеспечение и все окружение вцелом.

В данной публикации обсуждаются пути, которые привели к существующему положению вещей в теории моделей памяти, существующим фундаментальным недостаткам, и последствиям, провоцирующим дальнейшие исследования. Основополагающая роль модели памяти в параллельных вычислениях делает данную публикацию очень важной для многих дисциплин компьютерных наук, включая алгоритмы, приложения, языки, компиляторы, формальные методы, инжинерию программного обеспечения, виртуальные машины,  системые среды выполнения, и аппаратное обеспечение. Для практиков и преподавателей, публикация обеспечит краткий конспект по текущему положению вещей в этом часто игнорируемом и слабопонимаемом предмете. Для исследователей, материал представленный здесь обрисовывает в общих чертах амбициозный и кросс-дисциплинарный порядок вещей, позволяющий определить фундаментальные проблемы, которые есть сегодня – какое значение может иметь разделяемая переменная и как ее реализовать.

Последовательная согласованность

Привычный способ выполнения многопоточных программ базируется на разделяемых переменных. Каждый шаг выполнения состоит из выбора очередного потока для выполнения, и последующего  шага в данном выполнении потока  (как следует из текста исходного кода потока или последовательности программы). Этот процесс повторяется до тех пор пока вся программа не завершит свое выполнение. В действительности, процесс выполнения можно представить как определение всех шагов для каждого потока и поочередное их выполнение каким-то образом. Всегда, при получении доступа к объекту (переменной, полю или элементу массива), определяется его последноее сохраненное значение.

К примеру, на рисунке 1 отражена сущность конкуррентного алгоритма Деккера. Программа может быть выполнена путем поочередного выполнения шагов двух потоков различными способами. Формально, каждое и таких способов чередований определяет общий порядок выполнения всех шагов, которые должны выполняться всеми потоками. Этот порядок является согласованным к заданной последовательности программы для каждого потока. Любой доступ к разделяемой переменной «видит» предыдущее значение, сохраненное для переменной при  чередовании.

Первоначально X=Y=0 Красный поток Синий поток X = 1; r1 = Y; Y = 1; r2 = X;

Рисунок 1. Суть Алгоритма Деккера. Может ли r1 = r2 = 0?

Выполнение 1 X=1; r1=Y; Y=1; r2=X; // r1==0; // r2==1; Выполнение 2 Y=1; r2=X; X=1; r1=Y; //r1==1; //r2==0; Выполнение 3 X=1; Y=1; r1=Y; r2=X; //r1==1; //r2==1;

Рисунок 2. Возможные варианты выполнения к рисунку 1

На рисунке 2 представлены три возможные последовательности которые вместе иллюстрируют все возможные финальные значения неразделяемых переменных r1 и r2. Хотя так же могут быть и другие последовательности переключений между потоками, невозможно что бы r1 и r2 были равны 0 в конце выполнения; любое выполнение должно начинатся с первого выражения каждого из потоков, и установленная здесь переменная будет считываться другим потоком в дальнейшем. Следуя Лэмпорту [24], выполнение, которое может трактоваться как чередование ссылается на последовательную согласованность (sequential consistency). Последовательная согласованность дает нам самое простое понимание разделяемых переменных, но предостерегает от некоторых смежных течений.

Во-первых, последовательная согласованность может быть затратной  в реализации. Для рисунка 1, компилятор может, к примеру, изменить порядок двух независимых присваиваний для красного потока, в случае раннего планирвания загрузки для того что бы скрыть возможные задержки. В дополнение, современные процессоры почти всегда используют буфер для хранения, что бы избежать ожидания завершения сохранения, также эффективно изменяет порядок инструкций для каждого потока. Обе оптимизации и на уровне компиляторов и на уровне аппаратного обеспечения в конечном счете могут привести к случаю, когда будет r1==0 и r2==0 и как следствие могут привести к выполнению непоследовательной согласованности. Таким образом, изменение порядка любой пары доступа, чтения переменных из буффера записи, регистрации присвоения, исключение основных подвыражений, исключение избыточного чтения, и многие другие оптимизации процессоров и компиляторов, используемых в системах с одиночным процессором, потенциально могут привести к нарушению последовательной согласованности. [2]

Для того что бы определить, что подобная транформация небезопасна, анализатору компилятора необходимо выполнить небольшую работу (например [43]). Компиляторы, однако, имеют мало информации о разделяемых переменных, используемых разными потоками, делая трудозатраным выполнение подобного анализа перед применением оптимизации, которые мы обязаны выполнить везде. Так же здесь много работы на теоретическом выполнении этих оптимизаций в аппаратном обеспечении, с поддержкой откатов при выявлении актуальных нарушений последовательной согласованости (например [19, 24]). Однако эти идеи относятся к техникам специфичных реализаций (например поддержка решительного предположения (aggressive speculation support)), и изготовители как правило нерасположенны к ним в долгосрочной перспективе (в особености,применительно к компиляторам с непоследовательной согласованностью). Таким образом, большинство современных процессоров и компиляторов не предоставляют последовательной согласованности.

Во-вторых, несмотря на то, что последовательная согласованность выглядит простейшей моделью, она не достаточно проста и не так полезна как это казалось изначально. К примеру, имеет смысл рассуждать о чередовании шагов, только если нам известно об этих шагах. В этом случае, они представляют собой независимое обращение к памяти, на очень низком уровне. Попробуем представить два потока, которые в одно и то же время устанавливают значение 100.000 и 60.000 для разделяемой переменной X на 16-биной машине (за один такт доступ осуществялется только к 16 битам). Финальное значение переменной X при выполнении с «последовательной согласованностью» может быть 125.536 если присваивание значения 60.000 произошло между верхней и нижней половиной присваивания значения 100.000. На более высоком уровне это означает, что значение даже самых простейших операций библиотеки зависит от гранулярности системы, на которой данная библиотека выполняет свои операции.

В более общем случае, программисты беспокоятся о корректности параллельного кода в терминах чередования отдельных операций по доступу к памяти, и последовательная согласованность не защищает от основных источников ошибок связанных с совместным доступом,  которые возникают при одновременном доступе к одним и тем же разделяемым переменным (называется это явление состоянием гонки данных). Даже принимая во внимание последовательную согласованность, подобные операции по одновременному доступу могут оставаться опасными, и их следует избегать, или хотя бы явно выделять. Полагаясь на последовательную согласованость без выделения сложных участков кода, сильно усложняется требуемая реализация.

Данные без состояния гонок

Мы можем избежать обе рассмотренные проблемы обратив внимание на то что:

·         Проблеммное преобразование (например изменения порядка операций по доступу к несвязанным переменным на рисунке 1) никогда не влияет на результат в  однопоточных программах, но влияет на результат многопоточных (например, позволяя обоим переменным r1 и r2 рисунка 1 быть установленым в 0)

·         Эти преобразования могут быть определены только кодом, который позволяет двум потокам обратиться к одним и тем же данным одновременно таким способом, который спровоцирует конфликтную ситуацию, например, один поток пишет данные, а другой читает их.

Языки программирования как правило предоставляют механизмы синхронизации, такие как блокировки, или транзакционную память, для ограничения одновременного доступа к переменным из различных потоков. Если мы потребуем, что бы эти механизмы использовались корректно, и гарантируем выполнение последовательной согласованности только в случаях, когда нету нежелательных параллельных обращений, мы избавимся от данных моментов.

Мы может сделать это более точно следующим образм. Предположим языки позволяют отличать синхронизованные и обычные (несинхронизованные) операции (смотри ниже). Мы можем сказать, что две операции с памятью конфликтуют, если они обращаются к одному и тому же участку памяти (например переменной или элементу массива) и одна из этих операций – это запись.

Мы может сказать, что программа (со специфическими входными данными) позволяет получить состояние гонок, если у нее есть последовательное согласованное выполнение (то есть, порядок чередования выполнения шагов отдельных потоков определен в программе) при котором две простые (несинхронизированные) конфликтующие операции выполняются «одновременно». В нашем случае, две операции выполняются «одновременно» если они следуют друг за другом при чередовании шагов и относятся к различным потокам. Поскольку данные операции выполняются друг за другом при чередовании и мы знаем что они могут с так же хорошо выполнятся и в противоположном порядке; нет чередующихся операций влияющих на порядок.

Что бы убедится, что две несинхронизированные конфликтующие операции не выполнятся одновременно, они должны быть упорядочены посредством синхронизирующих операций чередования. Например, один поток должен освободить блокировку после доступа к разделяемой переменной, а другой поток должен получить блокировку перед обращением к переменной. Хотя, так же можно определить состояние гонок данных как конфликтующий доступ неупорядоченный синхронизацией, как это сделано в Java. Эти определения эквивалентны [1, 12].

Программу, которая не допускает возникновения состояний гонок памяти, называется свободной от гонок. А модель, свободная от гонок гарантирует последовательную согласованность только для программ, свободных от гонок [3, 1]. Для программ, которые допускают сотояния гонок, данная модель не предоставляет никаких гарантий.

Ограничения на состояние гонок не обременительно. В дополнение к блокировкам, которые предназначены для избежания возникновения гонок, современные языки программирования как правило обеспечивают механизм, подобный тому, который в Java носит название изменчивых переменные (volatile variables). Этот механизм объявляет, что определенные переменные или поля могут использоваться для синхронизации между потоками. Конфиктующий доступ к таким переменным может произойти одновременно – так как они явно определены как синхронизированные (в отличие от обычных, несинхронизированных), они не являются источниками гонок.

Для того что бы реализовать пример, показанный на рисунке 1 корректно без возникновения состояний гонок, нам необходимо просто идентифицировать разделяемые переменные X и Y как синхронизированные переменные. Это потребовало бы любой реализации, которая гарантировала бы последовательную согласованность, несмотря на одновременный доступ. Также потребовалась бы реализация гарантий цельного (неделимого) выполнения операций синхронизованного доступа; если 32-битное число используется для синхронизации, не должно быть доступа к нему как к двум 16-битным половинкам.

Этот решение «последовательной согласованности для програм свободных от состояний гонок» облегчает проблему обсуждаемую для случая чистой последовательной согласованости. Наиболее важные оптимизации процессора и компилятора остаются доступными для обычных операций – осторожность должна иметь место преимущественно только при явно указанном синхронизированном доступе, в результате которого оптимизация может повлиять на выполнение программы. Далее, несинхронизированные секции кода выполняются атомарно и подобные требования, призывающие явно указывать конкуррентный доступ, делает более простым понимание кода и человеком и компилятором. Этот поход описан более детально в [11].

Устойчивость от состояний гонок не предоставляет возможности для осуществления оптимизаций для однопоточных программ. Практически, оптимизации, касающиеся копирования значения разделяемой перменной в саму себя,  то есть выполнения присваивания x = x, где значение x не может быть переписано в другими способами, остаются некорректными. Это главным образом реализованно в определенных контекстах [9].

Хотя устойчивость от состояния гонок формально было предложено еще в 1990 [3], оно не находило широкого применения как формальная модель для промышленного использования до недавнего времени. Далее мы опишем эволюцию промышленных моделей, сфокусированных на решении проблем наличия состояний гонок и их влияние на будущие решения.

Промышленная практика и эволюция

Аппаратные модели памяти

Большинство аппаратного обеспечения поддерживает «смягченные» модели (relaxed models) которые являются более слабыми, чем последовательная согласованность. Эти модели используют подходы, в основе которых лежит реализация (implementation-centric view) или производительность (performance-centric view). В них желаемые процессорные оптимизации являются базой спецификации модели [2]. Типичные движущие оптимизации смягчают требования к порядку последовательной согласованности программы. Например, TSO (опция разделения времени) процессоров SPARC гарантирует, что доступы потока к памяти будут видны другим потокам в порядке заданном в программе, за исключением случаев, когда операция чтения следует за операцией записи.

Подобные модели дополнительно предоставляют ограничивающие инструкции, позволяющие программистам явно устанавливать порядок, который не может быть гарантирован иным способом; например программисты TSO могут установить ограничение между операциями записи и чтения потока для того что бы быть уверенным в том, что в процессе выполнения заданный порядок будет сохранен. Подобный стиль спецификации с заданием порядка и ограничений на уровне программы прост, но многие его нюансы могут не отвечать требованиям [1, 2]. Во-первых, этот стиль предполагает, что операция записи атомарна и неделима, и она видна всем потокам именно так. Однако, на рисунке 3 проиллюстрирован случай, когда осуществляемая процессором операция записи может быть видна разным потокам в разное время через используемые буфферы записи и разделяемый кэш. Добавление подобной оптимизации увеличивает сложность спецификации модели памяти. Таким образом, полная спецификация TSO, в которую включены самые простые атомарные оптимизации, оказывается более запутанной чем простое описание продемонстрированное выше. Модель PowerPC реализует более решительную форму оптимизации, со спецификацией, которая выглядит комплексной и сложной для интерпретации даже для экспертов. Документация x86 для Inter и AMD была неоднозначной в этом плане; однако недавние обновления добавили пояснения к имеющимся неоднозначностям, хотя эти обновления и остаются неофициальными.

Во-вторых, в хорошо написанных программах, поток обычно полагается на синхронизированное взаимодействие, определяя порядок или видимость операций доступа к памяти для других потоков. Таким образом, необходимость что бы упорядоченный доступ двух программ всегда был видим для всех потоков в том же порядке или операция записи выглядела атомарной для всех потоков несмотря на наличие синхронизации между потоками является избыточной. Вместо этого, важно сохранить порядок и атомарность только для явно синхронизированных потоков. Некоторые аппаратные реализации пытаются использовать эту данность, хотя и с помощью специальных методов, что еще больше усложняет модель памяти.

Первоначально X = Y = 0; Ядро 1 Ядро 2 Ядро 3 Ядро 4 X = 1; Y = 1; r1 = X; ограничение r2 = Y; r3 = Y; ограничение r4 = X; Может ли в результате быть r1=1; r2=0;r3=1; r4=0; нарушая атомарность операций записи?

Рисунок 3. Процессор не может выполнить атомарные и неделимые операции записи. Предположим в порядок программы добавлено ограничение. Положим кэши третьего и четвертого ядра имеют X и Y. Две операции записи инициируют сброс данных кешей. Это может привести к изменению порядка кэшей, формируя показанный результат и приходя к ситуации, когда оба обновления X происходит до и после обновления Y.

Первоначально X = Y = 0; Ядро 1 Ядро 2 r1 = X; if(r1==1) { Y = 1; } r2 = Y; if(Y==1) { X = 1; } Допустимо ли r1 = r2 = 1?

(a)

Первоначально X = Y = 0; Ядро 1 Ядро 1 r1 = X; Y = r1; r2 = Y; X = r2; Допустимо ли r1 = r2 = 42?

(b)

Рисунок 4. Тонкость с зависимостями контроллирования (a) и данных (b). Допустим, при чтении ядром 1 значения X мы получим 1 и предположим выполним операцию записи в Y. Ядро 2 также осуществляет запись в X. Обе операции чтения теперь дадут 1, создавая «самозаполняемое» предположение или «обусловленный» цикл. В случае с одним ядром, нету зависимости контроллирования, так как предположение корректно; однако, большинство программистов не будут ожидать такого результата (данный код на самом деле является свободным от состояния гонок так как здесь нету возникновений состояния гонок в процессе выполнения последовательной согласованности). Часть (b) показывает аналогичный случайный цикл с зависимостями данных. Ядро 1 может полагать что X = 42 (например, используя предположение о значении, основанное на предыдущем сохраненном значении) и (что любопытно) пишет значение 42 в Y. Ядро 2 читает это и пишет 42 в X, таким образом доказывая предположение и создавая случайный цикл который генерирует значение (42). К счастью, в наши дни нету процессоров которые ведут себя таким образом, но спецификация модели памяти должна отражать эту особенность.

В-третьих, современные процессоры выполняют различные формы предположений (например ветвление и аддрессацию), которые могут привести к незаметным и комплексным взаимодействиям с зависимостями данных и контроллирования, как это показано на рисунке 4.  Принятие во внимание эти предположения в в конкретном случае добавляет дополнительные источники сложности порядка выполнения инструкций программы + спецификации для стилей ограничения. Как мы будем обсуждать в секции 4.2.1, точная формализация зависимостей данных и контроллирования является фундаментальным препятствием для обеспечения чистой спецификации высокоуровневой модели памяти в наши дни. В общем, спецификации аппаратных моделей памяти часто остаются незавершенными, чрезмерно сложными и/или наврядли достаточными для того, что бы всегда быть правильно истолковаными даже экспертами. С тех пор как на аппаратные модели сильно повлияли аппаратные оптимизации, они часто несоответствуют требованиям программного обеспечения, приводя в резульатате к наличию некорректного кода или к необоснованным падениям производительности (Секция 4.3).

4.2 Модели памяти высокоуровневых языков

Язык Ada очевидно был первым широко распространенным высокоуровневым языком, который предоставил первый класс для поддержки параллельного программирования с использованием разделяемой памяти. Хотя подход используемый в языке для синхронизации потоков изначально был немного отличным от последующего дизайна более поздних языков, он был необыкновенно продвинутым в плане семантики памяти [37]. Он использовал стиль, похожий на стиль свободный от состояний гонок, требуя что бы корректные программы были хорошо синхронизированными; при этом не требуя полного представления о понятии «хорошо синхронизированного» и оставляя неопределенным поведение подобных программ.

Позже, пока не появилась Java, основные языки программирования не предоставляли качественной поддержки для потоков, и программирование разделяемой памяти было возможно только с использованием библиотек и API, таких как потоки POSIX и OpenMP. Наша предыдущая работа описывает почему подход применения дополнительных библиотек потоков не удовлетворителен [9]. Без реального определения языка программирования в контексте потоков, остается непонятным вопрос, какие трансформации совешаемые компилятором являются легальными, и таким образом, что программист может предполагать. Все-таки, спецификация потоков POSIX демонстрирует модель приближенную к свободной от состояния гонок, хотя здесь есть несколько несовместимых аспектов, с сильно различающимися интерпретациями даже между экспертами учавствующими в обсуждениях коммитета по стандарту. Модель OpenMP также не прозрачна, и в своем большинстве основана на инструкциях, аналогичных инструкциям ограничения в аппаратной модели, с соответствующими недостатками.

4.2.1 Модель памяти Java

Язык Java предоставляет первоклассную поддержку для потоков с разделением специально предназначенным для ее модели памяти. Пав (Pugh) показал что данная модель сложна в интерпретации и плохо разбиваемая – основные оптимизации компилятора были запрещены и во многих случаях модель демонстрировала неоднозначное или неопределенное поведение [29]. В 2000, Sun собрала экспертную группу для того что бы провести ревизию модели с помощью сообщества [30]. Усилия координировались через открытую рассылку по электронной почте куда были привлечены различные участники, представляющие вендоров аппаратного обеспечения, разработчиков программного обеспечения, исследователей и практиков.

Быстро было решено, что модель памяти Java должна предоставлять последовательную согласованность для программ свободных от состояний гонок, где переменный доступ (и блокировки с синхронизированных методов и мониторов) требовал синхронизации.

Однако, свобода от состояний гонок невозможна для Java. Поскольку Java считалась безопасным и защищенным языком, она не могла позволить произвола для состояний гонок. В особенности, Java должна поддерживать ненадежный (untrusted) код как часть надежного приложения и таким образом должна ограничивать ущерб причиненный состоянием гонок в ненадежном коде. К сожалению, идея безопасности, защищенности и «ограниченного ущерба» в многопоточном контексте не были как следует определены. Проблемой с определением модели памяти Java было формализовать эти понятия, таким образом что бы они минимально воздействовали на гибкость системы.

Рисунок 4(b) показывает эти случаи. Программа имеет состояние гонки и она некорректна. Однако, Java не может позволить операцию чтения для того что бы возвратить значение (return value out-of-thin-air) (как в случае с числом 42) поскольку должен быть найдено компромис для удовлетворения условий безопасности и защищенности. Например, было бы невозможно гарантировать что подобный ненадежный код не может вернуть пароль к которому не должно быть доступа. Подобные сценарии появляются для того, что бы нарушить любое обоснованное ожидание и ни один текущий процессор не деалет этого. Тем не менее, модель памяти должна формально запрещать подобное поведение, так что бы будущие процессоры также избегали этого.

Запрещение подобных нарушений каким то способом которые не будет способствовать одновременному запрещению других оптимизаций чрезвычайно сложная задача. Рисунок 5 демонстрирует пример в котором также возникает нарушение обусловленности (causality violation), но оно разрешено основной оптимизацией компилятора исключения избыточного чтения. После множественных предложений и пяти лет оживленных дискуссий, текущая модель была принята как наилучший компромис. Эта модель позволяет добиться результата продемонстрированного на рисунке 5, но не такого который продемонстррован на 4(b). К сожалению, эта модель очень сложна, она имеет несколько неожиданных поведений, и как было недавно показано не лишена ошибок. Мы предоставляем небольшой пример для модели представленной ниже и направляем читателей к [26] за полным описанием.

Первоначально X = Y = 0; Оригинальный код Поток 1 Поток 2 r1 = X r2 = X if (r1 == r2) { Y = 1} r3 = Y X = r3 После преобразований компилятора Поток 1 Поток 2 Y = 1 r1 = X r2 = r1 if(true); r3 = Y X = r3 Допустимо ли r1 = r2 = r3 = 1?

Рисунок 5. Исключение избыточного чтения может спровоцировать появление нарушения обусловленности, но должно быть разрешено. Для потока 1, компилятор может исключить избыточное чтение переменной X, заменив r2=X на r2=r1.Это позволит прийти к заключению, что выражение r1==r2 всегда корректно, делая запись в Y безусловной. Потом компилятор может сместить операцию записи что бы она выполнялась перед чтением X так как зависимости не нарушены. Последовательная согласованность позволяла бы обеим операциям чтения X и Y возвращать 1 в новом но не в оригинальном коде. Этот результат для оригинального кода появляется для нарушения обусловленности поскольку требуется самодоказываемая предполагаемая операция записи Y.

Общим для рисунков 4(b) и 5 является операция записи, которая выполняется раньше чем она выполнялась бы в случае наличия последовательной согласованности. Примеры отличаются тем, что для предполагаемой операции записи в конце (Y=1), есть несколько последовательных согласованных выполнений , где они выполняются (выполнение где обе операции чтения X возвращают 0). Для рисунка 4(b), не может быть последовательного согласованого выполнения для Y=42. Это мнение, с помощью которого определяется возможность предполагаемой операции записи в приемлимой форме является базисом обусловленности в модели Java и определение «хорошего поведения»   ключевой источник сложности.

Модель Java проверяет допустимость выполнения путем «совершения» одной или более операций доступа к памяти в определенное время – допустимость требует, что бы все операции доступа были совершены (в любом порядке). Осуществление операции записи раньше требуемого времени (до того как эта операция определена в порядке программы) требует, что бы она выполнялась в контексте «хорошего поведения», где (неформально) (1) выполненные операции доступа имеют похожую синхронизацию и взаимоотношения состояний гонок во всех предыдущих выполнениях и (2) операции записи которые должны выполнится не зависят от операций чтения, которые возвращают значения из состояний гонок. Эти условия убеждают, что будущие состояния гонок не будут использоваться для подтверждения предполагаемой операции записи которая вдальнейшем может подтвердить последующие состояния гонок.

Ключевой причиной сложности модели  Java является тот факт что она непрактична – доступ в будущем сможет определить является ли текущий доступ допустимым. Далее, много возможных будущих выполнений должны быть рассмотрены для определения их легальности. Этот выбор в будущем (хорошее поведение) выполнении также предоставляет некоторые неожиданные результаты. На самом деле, как обсуждалось в [26], если код одного потока совмещен («inlined») с другим потоком, то такой код может реализовывать больше поведений, чем оригинальный код. Таким образм, подобный эффект является недопустимым для модели Java (даже если не предполагается наличия синхронизации и тупиков (deadlock)). На практике, запрещенные оптимизации сложно реализовать и это не является значимым для ограничения производительности. Данное поведение, однако, не интуитивно, с другими причастностями – оно возникает изза того, что некоторые состояния гонок в оригинальном коде могут перестать быть такими состояниями в «inlined» коде. Это значит, что в момент определения совершения ранней операции записи, операция чтения при выполнение с «хорошим поведением» имеет больше выбора для возврата значений чем раньше (поскольку существует меньше состояний гонок), что выливается в новые поведения.

Как правило, увеличение синхронизации в модели Java может привести к новому поведению, даже несмотря на то что большая синхронизация условно приводит к возможным выполнениям. Недавно, было показано, что  по подобным причинам, добавление неподходящих операций чтения или удаление изыбточных операций чтения иногда также может добавить новое поведение, и данные свойства имеют более серьезные последствия чем предполагалось ранее [33]. На практике, некоторые оптимизации которые были разрешены моделью памяти Java в действительности являются запрещенными текущей спецификацией.

Непонятной является ситуация, когда существующее аппаратное обеспечение или JVM реализует подобную оптимизацию и таким образом нарушает нынешнюю модель Java. Конечно, текущая спецификация существенно улучшена. Несмотря на это, ситуация еще далека до желаемой. Во-первых, понятно, текущая спецификация не преследует целью наличия основных оптимизирующих преобразований, которые воспрепятствуют изменению логики программы. Во-вторых, она наследует сложность и новые наблюдения делают сложным процесс доказательства  корректности реальной системы. В-третьих,  методология спецификации по сути неустойчивая – небольшие изменения как правило приводят к трудно отлавливаемым непреднамеренным последствиям.

Модель Java управлялась как правило существующим набором тестовых случаев [30], основанных на неформальном преобразовании кода, которые были или наоборот не были желаемыми. Пока существует возможность изменить модель Java, остается нежелательным что наша спецификация поведения многопоточных программ опиралась бы на таком сложном и неустойчивом основании. Вместо этого, секция 6 пропагандирует фундаментальное переосмысление нашего подхода.

4.2.2 Модель памяти С++

Ситуация с C++ существенно отличается от той, что мы видим в случае с Java. Сам по себе язык не предоставляет поддержки потоков. Несмотря на это, они широко применяются, как правило посредством использования дополнительной библотеки, реализующей требуемую функциональность, как pthread [20], или соответствующие реализации Microsoft Windows. К сожалению важнейшие спецификации, например комбинации стандартов C и C++ в купе со стандартом Posix, оставляют нераскрытым вопросы правил управления разделяемыми переменными [9]. Это делает для создателей компиляторов непонятным точное определение того что им нужно реализовать, приводя в результате к очень случайным сбоям для которых сложно найти виноватого, и что наиболее важно, делает сложным процесс обучения параллельному программированию, поскольку даже эксперты не смогут согласится с некоторыми базовыми правилами, такими как может ли ситуация отображенная на рисунке 4(a) привести к состоянию гонки данных (Правильный ответ: Нет).

Мотивированные, данными наблюдениями, мы в 2005 году мы начали работу над моделью памяти для C++. Усилия в конечном счете были увеличены для включения определения атомарных операций (синхронизация аналогичная Java) и API для потоков соответственно. Это часть существующего черновика [22], для следующей ревизии С++. Следующий стандарт C предполагает содержать очень похожую модель памяти, с очень похожими атомарными операциями.

Эта разработка проводилась в то время, когда усиливались сомнения относительно того что модель памяти Java, полагаясь на последовательную согласованность для программ свободных от состояний гонок данных, была рационально реализуемой на широко используемых архитектурах, как минимум делая возможным реализацию спецификации в срок. Результатом этих дискуссий стали следующие наблюдения, оба из которых мы принимаем на веру для существующего аппаратного обесппечения.

·         Модель  языка программирования более слабая чем свбода от гонок данных вероятно не пригодна для использования большей частью сообщества программистов. Ранняя работа [10] отмечает данный момент, к примеру, даже создатели библиотеки реализующей работу с потоками часто остаются сбитыми с толку когда приходится явно иметь дело с упорядочиванием операций непосредственно в памяти. Главное усилие было помещено на попытки разработать более слабую, но сравнительно простую и пригодную для использования модель. Мы не чувствуем что добились успеха.

·         В некоторых архитектурах, в особенности на некоторых реализация PowerPC, свобода от гонок данных, является самой трудозатратной задачей. (в свете современных спецификаций (2009), подобная стоимость других, в особенности x86, более скромная, и ограничена в большинстве своем атомарными (C++) или изменчивыми (volatile)(Java) операциями хранения).

Это привело к компромисной модели памяти которая поддерживает свободу от гонок данных, для практически всего языка. Однако, атомарные типы данных, также обеспечивают низкоуровневые операции с явным принуждением порядка операций памяти, которые ужасно нарушают последовательную согласованность, даже при отсутстви гонок данных. Низкоуровневые операции просто определить и их можно без труда исключить для программистов, не являющихся экспертами (Операции требуют явного указания аргументов порядка памяти). Но они предоставляют экспертам возможность написать очень тонкий, переносимый, синхронизированный код который приближается по производительности к коду ассемблера.

Так как C++ не поддерживает выполнение кода в песочнице (sand-box), черновой стандарт C++ может и оставляет семантику программы с гонками данных абсолютно неопределенной, эффективно делая написание таких программ некорректным. Как мы отмечали в [12], это имеет некоторое количество в большинстве своем производительных, с преимуществами и большим отражением в существующих реализациях компиляторов.

В дополнение к моментам отраженных в секции 5, следует отметить что это действительно толкает моменты Java в намного меньший и темный угол спецификации; точно такие же моменты всплывают, если мы перепишем рисунок 4(b) с помощью атомарных операций C++ и использованием операций по низкоуровневому упорядочиванию порядка операций с памятью. Наше текущее решение этой проблемы проще но не такое элегантное как в Java. В отличие от Java, оно затрагивает небольшое количество скрытых вызовов библиотеки, а не доступов к памяти.

С моделью памяти Java, мы чувствуем, что хотя это решение использует компромис, это важный шаг вперед. Оно прозрачно устанавливает свободу от состояний гонок как ключевую гарантию что сможет понять любой прогрммист. Оно точно определяет, что создает гонки данных. Оно в конченом счете решает простой вопрос: Если значения x.a и x.b установлены одновременно, то будет ли это гонной данных? (Нет, пока они являются частью той же смежной последовательности биовых полей.) Поступая таким образом, просто определить недостатки существующих компиляторов которые мы сейчас сможем исправить.

4.3 Примирение  моделей языков программирования и аппаратного обеспечения

На всем протяжении этого процесса, постоянно становилось понятно, что существующие аппаратные модели и инструкции ограничения часто являются в лучшем случае минимальным аналогом моделей памяти языков программирования, особенно с учетом volatile полей Java и атомарных объектов C++. Всегда возможно реализовать подобную синхронизацию переменных, отображением каждой из них на блокировку, и выполнением и освобождением соответствующей блокировки контролирующей все операции доступа. Однако, подобный подход добавляет сотни избыточных циклов для каждой операции доступа, особенно учитывая тот факт, что доступ через блокировку может приводить к пропускам кеша (cache misses), даже если задействованы только операции чтения. 

Изменчивые (volatile) и атомарные переменные как правило используются для избежания использования блокировок для именно этих случаев. Типичное применение  заключается в использовании флага, которые идентифицирует была ли проинициализирована структура данных предназначенная только для чтения. Поскольку инициализация осуществляется только один раз, практически все операции доступа просто читают значение атомарного/изменичивого флага, тем самым избегая необходимости использования блокировки. Применение блокировки для доступа к флагу лишает преимущества данного подхода.

Однако, на аппаратном обеспечении где атомарность операций записи не такая строгая (см рисунок 3), часто становится непонятно возможны ли более эффективные (чем применение блокировок) отображения; даже полностью ограниченная реализация может не обладать последовательной согласованностью. Даже на другом аппаратном обеспечении существуют видимые несоответствия, вызвание в большинстве случаев недостатком хорошего понимания модели языка программирования когда было спроектированно аппаратное обеспечение. На x86 почти достаточно отображать синхронизации загрузок и сохранения на обычные инструкции загрузки и сохранения. Аппаратное обечпечение предоставляет твердые гарантии, того что переупорядочивание обычных операций с памятью синхронизированными операциями не видимо. Однако, нельзя предотвратить переупорядочивание синхронизированного сохранения следующее за синхронизированной загрузкой; таким образом данная реализация не предотвращает неккорректного результата для рисунка 1.

Это может привести к замене синхронизированной операции сохранения на обычныую инструкцию сохранения за которой следует существнное ограничение. Исключительной целью данного ограницения является защита от переупорядочивания синхронизированного сохранения и последующей операции синхронизированной загрузки. На практике подобные синхронизированные загрузки вряд ли будет находится настолько близко (алгоритм Деккера как правило не используется) что бы действительно ограничить аппаратное обеспечение. Но только инструкция ограничения (fence) ограничивает все случаи переупорядочивания памяти, включая случай, когда используются несинхронизированные операции доступа, добавляя таким образом излишнее ограничение. Решением получше будет вариант с привлечением механизма нахождения различий между двумя типами загрузок и сохранения (обычные и синхронизированные), как например инструкции Itanium ld.acq и st.rel [21]. Это, однако, требует изменения набора инструкций архитектуры, что в большинстве случаев является сложным предложением.

Мы подозреваем что нынешняя ситуация делает инструкции ограничения более дорогими чем необходимыми, по очереди мотивируя дополнительную сложность на уровне языков программирования как в случае с низкоуровневыми атомарными сущностями (atomic) C++ или lazySet() в Java.

Урок закончен

Свобода от состояние гонок данных обеспечивает простую и устойчивую модель для потоков и разделяемых переменных. Мы убеждены, что это наилучшая модель наших дней которая для использования при начале разработки программмного обеспечения. К сожалению, недостаток гарантий наличия состояний гонок и несоответствие с существующим «железом» предполагает три существенные слабости:

Отладка

Случайное наличие состояния гонки данных приводит не «неопределенному поведению», которое часто принимает форму неожиданных результатов позже в последующем процессе выполнения программы, намного позже чем на самом деле произошла гонка данных, повлекшая повреждение данных. Хотя обычный мгновенный результат состояния гонки данных не ожидается, и хотя происходит операция чтения незафиксированных значений или операция записи несовместимлого результата, мы отмечаем в [12], что прочие результаты, такие как непреднамеренные разветвления (wild branches) так же возможны в качестве результата оптимизаций компилятора, который ошибочно предполагает что состояния гонок данных отсутствуют. Поскольку подобные случаи сложно воспроизвести, корневую причину подобного некорректного поведения часто сложно определить, и на исправление подобных дефектов могут уйти недели. Многие программные средства призванные отлаживать подобные ситуации (например CHESS [27], RaceFuzzer[32]) также предполагают наличие последовательной согласованности, что ограничивает их полезность.

Производительность синхронизированных переменных на нынешнем аппаратном обеспечении.

Как уже обсуждалось, проверка на наличие последовательной согласованности в присутствии volatile  для Java и atomic для C++ для нынешнего аппаратного обеспечения может дорого обходится. Как результат, и С++ и в меньшей степени Java должны были обеспечить более дешевую альтернативу которая сильно усложняет модель для экспертов, пытающихся использовать ее.

Ненадежный код

В ненадежном (untrusted) коде нету способа убедится в отсутствии состояний гонок данных. Таким образом, эта модель недостаточна для таких языков как Java.

Из нашего опыта можно извлечть недвусмысленный урок – для программ с состояниями гонок данных очень тяжело определить семантику, которую просто понимать и удерживать желаемую гибкость системы. За время развития модели памяти Java, ее сложность, и последующее развитие неожиданных поведений, далеки от желаемого. К сожалению, мы знаем от том что альтернативной спецификации, которая была бы простой в использовании нету. Второе, правила для ослабления гарантий отсутствия гонок данных для лучшего соответствия нынешней аппаратной составляющей, как скажем низкоуровневые atomic из C++, так же более сложные чем этого хотелось бы.

Есть только один очевидный путь для улучшений – исключить потребность в выходе за рамки гарантий свободы от гонок данных:

•          Ликвидировать мотивацию в повышении производительности и

•          Убедиться что гонки данных никогда не произойдут во время выполнения, и таким образом избегая необходимости в спецификации их поведения и сильно упрощая или ликвидируя процесс отладки связанный с гонками памяти. К сожалению, это приводит нас в активную среду исследований, где нету готового решения. Мы обсудим возможные подходы в последующих двух секциях.

Выводы для языков программирования

Несмотря на драматическое схождение в дебатах по моделям памяти, достигнутые результаты приводят к следующему выбору: язык программирования, который позиционируется как язык обладающий сильной безопасностью и надежными параметрами, но не имеющий прозрачного определения какое значение может быть возвращено при выполнении операции чтения разделяемой памяти (случай Java). Против языка с прозрачной семантикой, но требующий избегания надежных параметров обещанных языком, таким как Java (случай C++). К сожалению современное программное обеспечение требует и параллельность и надежность, и потребность выбора между ними недопустимо.

С пессимистичной точки зрения следовало бы вовсе исключить использование разделяемой памяти. Однако, значительные преимущества глобального аддресного пространства, по крайней мере эпизодически, поддерживается широко распространенным использованием потоков, несмотря на наличие сложных моментов. Мы верим, что недостаток кроется не в парадигме глобального аддрессного пространства, а в неквалифицированном использовании «дикой распределенной памяти», допускаемой текущими системами.

Свобода от состояний гонок данных была первой попыткой формализации дисциплины разделяемой памяти через модель памяти. Она достоверно недостаточна так как ответственность за следование этой дисциплине ложилось на плечи разработчика. Далее, свободы от состояний гонок само по себе, возможно, недостаточно для того что бы писать корректные программы, обладающие простотой в отладке, и хорошо сопровождаемым кодом разделяемой памяти; например, он не исключает полностью атомарных нарущений или недетерминированных поведений.

Двигаясь дальше, мы верим, что для того что бы сделать возможным «параллелизм для масс» нужно разработать и продвигать послушную модель разделяемой памяти (disciplined shared-memory model), которая:

•          достаточно проста для того что бы быть легка в обучении для неопытных новичков, то есть, минимально обеспечивать последовательную согласованность для программ которые подчиняются требуемому порядку;

•          должна принуждать к требуемому порядку, то есть, нарушения данного порядка не должны приводить к неопределенной и чрезвычайно сложной семантке, но должны отлавливаться и возвращаться назад к разработчику как недопустимые.

•          быть достаточно универсальной для реализации важных параллельных алгоритмов и паттернов, и

•          Обладать высокой и масштабируемой производительностью.

Многие предыдущие попытки,  главной целью которых было увеличение продуктивности разработчиков находили способы реализаций уровней абстракций работы с потоками; например Cilk [18], TBB [23], OpenMP [36], недавний язык HPCS [25], другие высокоуровневые библиотеки, фреймворки, и API такие как java.util.concurrent и библиотеки boost для C++, хороши как и другие специфичные для конкретной области. Пока приведенные решения преодолевают свой длинный путь по нарправлению к упрощению трудностей для гармоничной реализации параллелизма, наши аргументы основанные на модели памяти являются более глубокими – мы приводим доводы в пользут того, что, по крайней мере сейчас и в недалеком будущем, невозможно обеспечить рациональную семантику для языка которая допускала бы наличие состояний гонок памяти и возможно более фундаментальные проблемы. В действительности, все примеры которые были нами приведены или предоставляют непрозрачную модель или страдают от подобных ограничений как в C++/Java.  Следовательно, эти подходы, не реализуют требований принуждения модели. Похожим образом, транзакционная память обеспечивает высокоуровневый механизм для атомарности, но модель памяти в настоящем не-транзакционном коде сталкивается с теми же проблемами, которые описаны здесь [35].

В сердце наших намерений относительно послушной модели лежат вопросы какая «посушность» требуется и как к ней принуждать? Краткосрочным, переходным путем является продолжение работы со свободой от гонок данных и фокусирование на иследовании вопросов принуждения. Идеальное решение для языков программирования это ликвидировать гонки данных с помощью дизайна (например [13]); однако, наши семантические сложности можно избежать даже динамическими способами (например [16] или  [17]) которые замещают все случаи гонок данных соответствующими исключеними (Есть и другие более быстрые техники динамического определения гонок данных, предназначенные в основном для отладки, но они не гарантируют совершенной точности, как здесь требуется.)

Более долгострочные решения касаются и соответствующей «послушности» и ее принуждения. Фундаментальный задачи отладки, тестирования и определении причин возниковения у многопоточных программ их недетерминированности – выполнение может показать один из многих прослоек доступа к памяти. В сопоставление с этим, многие программы, написанные в расчете на высокую производительность имеют детерминированный результат и могут быть представлены детерминированными алгоритмами. Написание подобных программ с использованием детерминированного окружения позволяет определить причину с последовательной семантикой (модель памяти намного проще чем последовательная согласованность с потоками).

Следовательно, ценной послушности является гарантия детерминированности по умолчанию; когда требуется недетерминированность, она должна запрашиваться явно и не должна персекаться с детерминированными гарантиями для остальных фрагментов программы [7]. Здесь много предшествующей работы над детерминированными параллельными данными, фуникцональными и актерскими языками. Мы сфокусированы на универсальных усилиях которые продолжают использовать широко распространенные практики программирования, и сложные структуры данных, основанные на указателях. Подходы, базирующиеся на особенностях языков программирования, с подобными целями включают Jade [31] и более новый Deterministic Parallele Java (DPJ) [8]. В часности DPJ предлагает тип основанный на регионе и эфективную систему для семантики с детерминированностью по умолчанию – название «регионы» отделяет разделы кучи и для каждого метода выполняет сбор информации какой регион использовался в операциях записи и чтения каждым методом. Вместе с упорядоченной структурой параллельного контроля, компилятор легко может использовать полученную суммарную информацию для того, что бы убедится что не произошло неупорядоченных конфликтных операций досутпа и программа детерминирована. Недавние результаты показывают, что DPJ можно применять для большого количества программ и сложных структур данных получая производительность сравнимую с кодом потоков [8].

Так же наблюдался прогресс в методах времени исполнения (runtime methods) для детерминированности [15, 28, 4, 5].

Оба подхода  имеют свои плюсы и минусы и все еще требуют дополнительных исследований перед массовым применением. Подход основанный на использовании языка программирования должен устанавливать, что он достатчно выразителен и не потребует чрезмерных усилий разработчика. Для ранних, новые техники являются обещающими, но пока не более того. Для более поздних, DPJ пытается облегчить бремя путем использования похожего базового языка (Java на данный момент) и обеспечивая полуавтоматические средства для предположений требуемых аннотаций программиста [38]. Далее, аннотации языка такие как эффективная суммарная информация операций чтения и записи DPJ являются значимой документацией – они  способствуют увелчиению жизненного цикла для модулярности, поддерживаемости, спорной компенсации за усилия разработчика. В конечном счете, выгода статических подходов выражена отсутствием оверхеда и сюрпризов во время исполнения.

В отличие от предыдущего, чистый подход времени исполнения предполагает меньшее затрат со стороны программиста, но привносит недостаток, который заключается в том что  накладные расходы в отдельных случаях могут быть чересчур высоки. Далее, по сути, подход времени выполнения не предоставляет гарантий статического подхода перед выполнением и поэтому допускающий наличие сюрпризов.

Мы настроены оптимистично и считаем, что рассмотренные подходы открыли много обещающих направлений для «послушной» разделяемой памяти, которые могут решить проблемы описанные в данной публикации. Похоже что финальное решение будет в состоянии из сбалансированной комбинации  особенностей языка программирования и среды выполнения и станет результатом богатой череды последующих исследований.

Выводы для аппаратного обеспечения

Как было рассмотрено в разделе 4, нынешние аппаратные модели памяти неполностью соответствуют даже нынешним программным (свободным от состояний гонок) моделям памяти. Изменения ISA для того что бы определять отдельные операции загрузки и сохранения как синхронизации могут решить некоторые краткосрочные проблемы. Однако установленные изменения ISA сложно изменить, особенно в случае, когда существующий код работает вцелом как нужно и недостаточно опыта для документирования преимуществ котороые могут быть получены после изменений.

Академические исследователи пошли другим путем, использующий сложные механизмы (например [6]) для того что бы предположительно удалить принуждения налагаемые операциями ограничения, отбрасывая предположения когда определено, что принуждения действительно нужны. Хотя эти медоты доказали свою эффективность, они привносят затраты реализации и не касаются непосредственно корня проблемы несоответствующих моментов параллельной аппаратно-программной семанитки.

Если взглянуть в будущее, мы верим что появится более фундаментальное решение данной проблемы с переосмысленным дизайном, где будущие исследования многоядерного аппаратного обеспечения будут эволюционировать в гармонии с исследованиями программных моделей рассмотреных в секции 6.

Текущее состояние технологий аппартаного обеспечения делает чрезвычайно подходящим нынешнее временем для подобных намерений. Мощные и сложные принуждения привели индустрию ситуацию когда понятно, что производительность будет расти за счет увеличения числа вычислительных ядер. Сегодняшние многоядерные решения использующие кеш, оптимизированы для нескольких ядер – существенное увеличение  производительности до нескольки сотен или тысяч ядер без анализа требований программного обеспечения будет сложным.

Мы видим эти сложности как возможность не только решить проблемы, обсуждаемые в данной публикации, но делая таки образом, мы ожидаем добиться более эффективных программного и аппаратного обеспечения. Во-первых, мы верим что процессоры у которых будет поддержка программных моделей будут более эффективными чем аналогичные программные решения. Это наблюдение уже лежит в основе работы по моделям смягченной аппаратной согласованности (relaxed hardware consistency model) – мы надеемся что различия нынешенего времени приведут к совместной эволюции программных и аппаратных моделей, а не к модификациям каждой из моделей в отдельности которые могут обеспечить более эффективные решения. Во-вторых, аппаратные исследования для поддержки программных моделей также будут чрезвычайно критичными. Аппаратная поддержка может использоваться для эффективного принуждения требуемого порядка тогда как статических подходов оказывается недостточно; например путем непосредственного определения нарушений порядка и/или используя эффективные стратегии песочниw (sandbox) для ненадежного кода.

Вместе с этими строками мы совместно с DPJ начинаем в Иллинойсе аппаратный проект DeNovo.  Мы используем DPJ-подобные регионы и эффектные аннотации для реализации дизайна более мощных, эффективных коммуникаций по отношению к программному обеспечению, когерентных протоколов и механизмов планирования задач.Мы также планируем обеспечить аппаратную поддержку и поддержку времени выполнения для того что бы иметь дело со случаями когда статической информации и аналитики DPJ будет недостаточно. После появления таких моделей, мы ожидаем что они лягут в основу последующих программно-аппаратных интерфейсов всключая ISA.

Выводы

Эта публикация показывает перспективу основанную на совместной работе уже более тридцати лет. Мы неоднократно были удивлены, насколько сложно формализировать кажущийся простым и фундаментальным вопрос: «какое значние должна вернуть операция чтения в многопоточной программе». Последовательная согласованность для программ свободных от состояний гонок данных является лучшим, что мы можем сделать сегодня, но недостаточным. Невозможность определить обоснованную семантику для программы с состояниями гонок данных не только теоретический недостаток, а фундаментальная дыра в основе наших языков программирования и систем. Сейчас считается нормой, что большинство распространяемого программного обеспечения имеет дефекты и похоже что большинство коммерческого многопоточного программного обеспечения обладает гонками данных. Отладочные средства и безопасные языки ограничивающие ненадежный код в «песочнице» должны уметь работать с подобными явлениями и должные предоставлять семантику которую разработчики и специалисты в состоянии понять.

Мы верим в то, что пришло время переосмысления дизайна наших языков программирования и систем. Как минимум, система, и желательно языки должна принуждать к отсутствию гонок данных. Долгосрочная и потенциально более стоящая стратегия заключается в переосмыслении высокоуровневых порядков, которые делают процесс написания параллельных программ намного проще и является результатом новых языков и систем. Мы также верим в то, что некоторый беспорядок в сегодняшних моделях памяти может быть предотвращен путем более тесного взаимодействия разработчиков программного и аппартаного обеспечения. Поскольку мы подталкиваем к более упорядоченным моделям памяти, тут есть еще одна благоприятная возможность переосмыслить и перепроектировать программно-аппаратные интерфейсы и аппаратные реализации всех параллельных механизмов. Эти взгляды вопролощают намерения богатых исследований для которых потребуется вовлечение многих поддисциплин различных околокомпьютерных сфер, включая разработку языков, компиляторов, формальных методов, разработки программного обеспечения, алгоритмов, систем времени выполнения и аппаратного обеспечения.

Благодарности

На эта публикацию сильно повлияли взаимодействия и дискуссии с коллегами на протяжении долее тридцати лет.  Нам чрезвычайно приятно поблагодарить Марка Хилла (Mark Hill) за совместную разработку подходов свободных от состояний гонок и другой фундаментальной работы, Курош Гарачерлу (Kourosh Gharachorloo) за аппаратные модели, Джереми Мэнсона (Jeremy Manson) и Билла Пага (Bill Pugh) за модель Java, Лоуренса Кроула (Lawrence Crowl), Пола МакКини (Paul McKenney), Кларка Нельсона (Clark Nelson) и Герба Саттера (Herb Sutter) за модель C++, и Викрама Адве (Vikram Adve), Роба Боччино (Rob Bocchino) и Марка Снира (Marc Snir) за последующую работу по упорядоченным программным моделям памяти и их принуждениям. Мы бы хотели поблагодарить Дуга Ли (Doug Lea) за бесчисленные дискуссии и продолжительные одобрения запечатать конверт. Напоследок, мы бы хотели поблагодарить Викрама Адве (Vikram Adve), Роба Боччино (Rob Bocchino), Лоуренса Кроула (Lawrence Crowl), Марка Хилла (Mark Hill), Дуга Ли (Doug Lea), Джереми Мэнсона (Jeremy Manson), Пола МакКини (Paul McKenney), Брэйтина Саха (Bratin Saha) и Роба Шрейбера (Rob Schreiber) за комментарии к черновику данной работы. Сарита Адве (Sarita Adve) в настоящее время финансируется корпрорациями Intel и Microsoft через Исследовательский Центр Универсальных Параллельных Вычислений  Иллинойса.

Ссылки

[1] S. V. Adve. Designing Memory Consistency Models for Shared-Memory Multiprocessors. PhD thesis, University of Wisconsin- Madison, 1993.

[2] S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer, 29(12):66–76, 1996.

[3] S. V. Adve and M. D. Hill. Weak ordering—A new definition. In Proc. 17th Intl. Symp. Computer Architecture, pages 2–14, 1990.

[4] M. D. Allen, S. Sridharan, and G. S. Sohi. Serialization sets: a dynamic dependence-based parallel execution model. In Proc. Symp. on Principles and Practice of Parallel Programming, 2009.

[5] E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: Safe Multithreaded Programming for C/C++. In OOPSLA, 2009.

[6] C. Blundell, M. M. K. Martin, and T. Wenisch. Invisifence: performance-transparent memory ordering in conventional multiprocessors.In Proc. Intl. Symp. on Computer Architecture, 2009.

[7] R. Bocchino et al. Parallel programming must be deterministic by default. In Proc. 1st Workshop on Hot Topics in Parallelism, 2009.

[8] R. Bocchino et al. A type and effect system for deterministic parallel java. In Proc. Intl. Conf. on Object-Oriented Programming, Systems,Languages, and Applications, 2009. to appear.

[9] H.-J. Boehm. Threads cannot be implemented as a library. In Proc.Conf. on Programming Language Design and Implementation, 2005.

[10] H.-J. Boehm. Reordering constraints for pthread-style locks. In Proc.12th Symp. Principles and Practice of Parallel Programming, pages173–182, 2007.

[11] H.-J. Boehm. Threads basics. http://www.hpl.hp.com/personal/Hans_Boehm/threadsintro.html, July 2009.

[12] H.-J. Boehm and S. Adve. Foundations of the C++ concurrency memory model. In Proc. Conf. on Programming Language Design and Implementation, pages 68–78, 2008.

[13] C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In Proc. Intl.Conf. on Object-Oriented Programming, Systems, Languages, and Applications, 2002.

[14] L. Ceze et al. BulkSC: Bulk Enforcement of Sequential Consistency.In Proc. Intl. Symp. on Computer Architecture, 2007.

[15] J. Devietti et al. DMP: Deterministic shared memory processing.In Proc. Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 85–96, Mar.2009.

[16] T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: a race and transaction-aware java runtime. In Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation, pages 245–255, 2007.

[17] C. Flanagan and S. Freund. FastTrack: Efficient and precise dynamic race detection. In Proc. Conf. on Programming Language Design and Implementation, 2009.

[18] M. Frigo, C. E. Leiserson, and K. H. Randall. The implementation of the Cilk-5 multithreaded language. In Conference on Programming Language Design and Implementation (PLDI), pages 212–223, 1998.

[19] K. Gharachorloo, A. Gupta, and J. Hennessy. Two Techniques to Enhance the Performance of Memory Consistency Models. In Proc.Intl. Conf. on Parallel Processing, pages I355–I364, 1991.

[20] IEEE and The Open Group. IEEE Standard 1003.1-2001. 2001.

[21] Intel. Intel Itanium Architecture: Software Developer’s Manual, jan 2006.

[22] ISO/IEC JTC1/SC22/WG21. ISO/IEC 14882, programming language - C++ (committee draft). http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2800.pdf, 2008.

[23] James Reinders. Intel(R) Threading Building Blocks: Outfitting C++ for Multi-core Parallelism. O’Reilly, 2007.

[24] L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers,

C-28(9):690–691, 1979.[25] E. Lusk and K. Yelick. Languages for high-productivity computing:The DARPA HPCS language project. Parallel Processing Letters,17(1):89–102, 2007.

[26] J. Manson, W. Pugh, and S. Adve. The Java memory model. In Proc.Symp. on Principles of Programming Languages, 2005.

[27] M. Musuvathi and S. Qadeer. Iterative context bounding for systematictesting of multithreaded programs. In Conf. on Programming Language Design and Implementation, pages 446–455, 2007.

[28] M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: Efficient deterministic multithreading in software. In Proc. Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Mar. 2009.

[29] W. Pugh. The Java memory model is fatally flawed. Concurrency -Practice and Experience, 12(6):445–455, 2000.

[30] W. Pugh and the JSR 133 Expert Group. The Java memorymodel. http://www.cs.umd.edu/~pugh/java/memoryModel/and referenced pages, July 2009.

[31] M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of jade. ACM Transactions on Programming Languages and Systems, 20(3):483–545, may 1998.

[32] K. Sen. Race directed random testing of concurrent programs. In Conf. on Programming Language Design and Implementation, 2008.

[33] J. Sevcik and D. Aspinall. On validity of program transformations in the java memory model. In ECOOP 2008, pages 27–51, 2008.

[34] D. Shasha and M. Snir. Efficient and correct execution of parallel programs that share memory. ACM Transactions on Programming Languages and Systems, 10(2):282–312, April 1998.

[35] T. Shpeisman et al. Enforcing isolation and ordering in STM. In Conference on Programming Language Design and Implementation (PLDI), 2007.

[36] The OpenMP ARB. OpenMP application programming interface: Version 3.0. http://www.openmp.org/mp-documents/spec30.pdf, May 2008.

[37] United States Department of Defense. Reference Manual for the Ada Programming Language: ANSI/MIL-STD-1815A-1983 Standard 1003.1-2001, 1983. Springer.

[38] M. Vakilian et al. Inferring method effect summaries for nested heap regions. In 24th Intl. Conf. on Automated Software Engineering, 2009. to appear.