Да, лекции в нашем университете – на английском языке.

Наши роботы считают, что вас заинтересует это:

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

Все советы автономны и их порядок не имеет значения.

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

Познакомьтесь с UNIX. Установка Убунту и компиляция ядра – это не знакомство с UNIX. Почитайте о том инженерном и научном фундаменте который лежит в основе философии UNIX. Не обязательно становится крутым сисадмином и поднимать десяток серверов, лучше просто привыкните к принципам работы и UNIX way.

Математика – это главное. Не смотря на сугубую потребительскую направленность многих софтверных компаний, фундаментальные науки остаются фундаментом всего.

Задавайте вопросы. Естественно, если не нашели ответ в гугле. Соответственно, не задавайте вопросы, на которые может ответить гугл. Сайт StackOverflow – ваш лучший друг. Задавайте вопросы в интернете, среди друзей, учителей, коллег. Глупый вопрос лучше незнания.

Познакомьтесь с системами контроля версий.  Хотя бы с основными – SVN, Git, Mercurial. Откройте репозитарий на своей машине и используйте его для домашних заданий и собственных проектов.

Знай свой инструмент

Познакомьтесь с современными инструментами разработки. Зачастую в университетах не уделяют внимания средам разработки и другим программам и утилитам, необходимым для полноценной работы. Многие IDE бесплатны, попробуйте Eclipse, NetBeans, Emacs, XCode, привыкните к принципам работы, найдите удобный для вас инструмент.

Научитесь пользоваться отладчиком. Это настолько критично, что совершенно непонятно, почему университеты уделяют этому так мало внимания.

Познакомьтесь с методологиями разработки.  Сложно им придумать применение в университетской жизни, но все же возможно. Как минимум, вы можете попробовать использовать какую-нибудь методологию в своем с другом проекте.

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

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

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

Изучите новый для себя язык программирования. Иногда слышу нечто вроде «нас учат чему-то, я не знаю, где это будет применяться в жизни». Такие люди зачастую настолько уверены в бесполезности некоторых этих знаний, что после окончания университета работают по какой-то другой специальности потому, что их не научили программировать на популярном сегодня языке программирования. Забудьте фразу «мне это не понадобиться в будущем». Когда в детском саду учат читать, то никто не готовит профессиональных чтецов. Детей просто учат пользоваться инструментом для получения информации.

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

У нас на работе всегда есть пиво :-)

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

Не забывайте о принципе Парето. 20 процентов усилий дают 80 процентов результата. Это, естественно, не правило, но вполне очевидная тенденция.

И самое главное: если вам не нравится программирование, то не становитесь программистом. Очень просто :-) Ничем хорошим работа без удовольствия закончиться не может.

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

Наши роботы искали похожие записи, но не нашли :(

• Сигма – сумма того, что получится в красных фигурных скобках
• Шеврон внизу и зеленая двойка – битовый сдвиг два раза (или просто деление на 4)
• Первая картинка – первый логотип компании, которая в последствии превратилась в IBM, а аббривеатура M. F. T. S. – The IBM Mathematical Formula Translating System – язык программирования Fortran. Четыре запятые в конце превращают это в «for».
• Пирог (pie, читается так же, как π)  – просто переменная
• Знак равенства это знак равенства
• На фотографии в компании пингвина Тукса изображен Эндрю Танненбаум, известный в том числе спором с создателем Линукса Линусом Торвальдсом, который произошел в 1992 году. Две запятые в начале превращают это в 92.
• 2 читается как «to»
• printf («goodbye, dad\n»); – смерть Денниса Ритчи, 2011 год. Можно по той же логике превратить это в 11, но это не так важно
• Принтер – оператор PRINT
• Девочка брызгает (squirt)  воду. Из букв 1, 2, 5, 6 получится SQRT – квадратный корень. (Другие ассоциации со словом «squirt»? Бывает)
• Снова π

Что получается?

sum {
   for π = 92 to 2011
     print sqrt π
} / 4

Сам численный результат, конечно, не важен.

Второй ребус:

1. Домашний борщ

2. Майкл… ?

3. Ваш ответ? (для третьего ребуса требуется разгадать первые два)

Решение:

Домашний борщ

• В первой таблице всякие выражения, написанный шрифтом webdings. Некоторые – правда, другие – ложь.
• Если считать слева направо сверху вниз и соотнести номера ячеек с «правдой» с цифрами после таблицы, то получим другие индексы. Стэнли Ипкисс – это чувак из фильма «Маска». Таблица правды/лжи будет использована как маска:
• Выберем из таблицы куски QR-кода по полученным индексам, соберем воедино. QR-код ведет на http://freetonik.com/text/budni/
• Из подчеркнутых букв получим «пять»

Майкл ... ?

• Чертик – символ FreeBSD. 6 запятых превращает это в F
• Инфракрасное изображение кота – infrared = IR
• Логоитип сайта StackOverflow, первые две буквы – ST
• Ссылка дана с ошибкой, но она не очень важна. Должна вести сюда – звук дозвона диал-ап модема
• Много скобок – это LISP. Запятая в начале превращает его в ISP
• Получается «FIRST dial-up ISP» – первый интернет провайдер с диал-апом, компания The World.
• Иконка домашней странички означает домашнюю страницу этого провайдера
• В исходном HTML-тексте этой страницы на строке 585 в момент публикации ребуса был штат Оклахома
• Высшая точка в этом штате – гора Black Mesa, название, известное по игре Half Life
• С дипломатом в этой игре постоянно передвигался G-Man
• Микрофон – озвучка. Этого персонажа в игре озвучивал Майкл Шапиро

Ваш ответ?

• На последней картинке изображен Barney Google
• Забиваем в гугл «пять» и «шапиро» (или эти два ответа в любой другой форме)
• Ищем на странице выдачи элемент с ID «resultStats» (это количество найденных страниц) – это и есть ответ

Как и в случае с первым ребусом, сам численный ответ не важен.

Наши роботы искали похожие записи, но не нашли :(

Уже почти год все эти блоги являются разделами единого сайта freetonik.com. Я приглашаю вас подписаться на RSS-поток всего сайта: здесь публикуется намного больше постов, включая заметки о Вселенной «APOD по-русски» и статьи по информатике и ИТ. Адрес фида – http://feeds.feedburner.com/freetonik

Старые фиды никуда не денутся, пока там есть хотя бы один подписчик.

Спасибо!

Наши роботы считают, что вас заинтересует это:

• Astronomy Picture of the Day по-русски Всем известная научная организация NASA довольно активна в интернете, на...
• Непредубежденность На youtube есть канал молодого британца по имени Doug 'QualiaSoup'....
• Тау Тельца и туманность Хинда Желтоватая звезда ближе к центру снимка это Тау Тельца, которая дала...

Microsoft Silverlight — это программная платформа, включающая в себя плагин для браузера, который позволяет запускать приложения, содержащие анимацию, векторную графику и аудио-видео ролики, что характерно для RIA (Rich Internet application). (Википедия)

Для сегодняшнего вводного урока нам понадобится среда для разработки. Можно воспользоваться бесплатной Microsoft Visual Web Developer 2010 Express или приобрести Microsoft Visual Studio 2010. Также вам понадобится Silverlight 4 Tools for Visual Studio 2010. Можно также попробовать визуальный редактор Microsoft Expression Blend, который позволяет создавать красивые интерфейсы без написания кода. Сегодня он нам не понадобится, я буду использовать MSVS 2010.

Запустите Visual Studio, выберите File -> New -> Project, и выберите Silverlight Application и Visual C#. В следующем окне выберите ASP.NET Web Application Project, Silverlight 4 и нажмите OK. Вы увидите окно, разделенное на две части: сверху визуальное представление главной страницы сайта, а внизу XAML-код, который и описывает эту страницу. XAML (читается «замл») это основанный на XML язык разметки, с помощью которого очень удобно создавать интерфейсы и графику. Если вы работали с HTML, то принцип XAML вам покажется знакомым.

Если файл MainPage.xaml у вас еще не открыт, то кликните дважды по нему в Solution Explorer'е, и вы увидите автоматически сгенерированный XAML-код:

<UserControl x:Class="SilverlightApplication8.MainPage"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
    xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
    mc:Ignorable="d"
    d:DesignHeight="300" d:DesignWidth="400">
    <Grid x:Name="LayoutRoot" Background="White">
    </Grid>
</UserControl>

Давайте добавим текст и кнопку. Текстовый блок описывается тегом TextBlock:

<TextBlock Text="Hello, World!" HorizontalAlignment="Center" />

А кнопка тегом Button:

<Button Name="myButton" Width="100" Content="Click" Click="myButtonClick" />

Но если вставить эти два элемента в сгенерированную для нас сетку , то кнопка «налезет» на надпись. Чтобы не вникать в детали, давайте изменим «подложку» — вместо элемента Grid будем использовать StackPanel: в этом случае каждый новый добавленный элемент будет отображаться после последнего. Вот что у меня получилось:

<UserControl x:Class="SilverlightApplication8.MainPage"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
    xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
    mc:Ignorable="d"
    d:DesignHeight="300" d:DesignWidth="400">
    <StackPanel x:Name="LayoutRoot" Background="White">
        <TextBlock Text="Hello, World!" HorizontalAlignment="Center" />
        <Button Name="myButton" Width="100" Content="Click" Click="myButtonClick" />
    </StackPanel>
</UserControl>

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

Кликните по треугольнику рядом с MainPage.xaml в Solution Explorer'е и откройте появившийся там файл MainPage.xaml.cs (в случае, если вы, как и я, выбрали C# в качестве основного языка при первом запуске Visual Studio). В этом файле находится частичный класс MainPage с конструктором с одной единственной функцией InitializeComponent (). Мы хотим добавить функцию, которая будет выполняться при нажатии на кнопку. Добавим в класс следующий код:

private void myButtonClick(object sender, RoutedEventArgs e)
{
   myButton.Content = "Goodbye, World!";
}

Для сравнения и полноты примера, вот идентичный код на Visual Basic:

Private Sub myButtonClick(ByVal sender As Object, ByVal e As RoutedEventArgs)
    myButton.Content = "Goodbye, World!"
End Sub

Возможно, ваша версия Visual Studio автоматически создала пустой метод в тот момент, когда вы указали его название при описании кнопки в XAML, но моя MSVS2010 не пошла мне на встречу.

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

Заключение

Честно говоря, впечатления от .NET и Windows Presentation Framework двоякие: с одной стороны, это по-настоящему мощная система, позволяющая создавать практически любые приложения для платформы windows (включая windows 7 phone) и интернета. Не нужно больше работать напрямую с Win32 API или с ужасным COM. Команда программистов могут работать над одним проектом, каждый со своим любимым языком, не заботясь о совместимости и передаче данных. С другой стороны, как и другие технологии Майкрософт, все это выглядит чудовищно неэлегантно: куча составных частей, множество «слоев», множество переизобретенных велосипедов.

Месяца через два у меня будет чуточку опыта реальной разработки c Silverlight, посмотрим, что из этого выйдет.

Продукты Майкрософт

• Microsoft Visual Studio все, что нужно, для разработки .net и WPF, включает визуальный редактор
• Microsoft Visual Studio Express «легкая» версия, включает редактор WPF
• Microsoft Expression Blend мощный инструмент для визуального дизайна XAML
• Microsoft Expression Design позволяет экспортировать векторные и растровые изображения в XAML
• XAMLPad простой удобный редактор XAML

Продукты других компаний

• WPF Graphics Tools
• XamlPadX v4 blog.
• SharpDevelop
• Danet Studio
• Kaxaml
• Ultimate XAML for Softimage
• ZAM 3D
• 3DPaintBrush
• PowerBuilder .NET
• Snoop

Наши роботы считают, что вас заинтересует это:

• Heal this world - Мое рабочее место- Fastfood?- Скринкаст- Кризисная распродажа- Доставка цветов-...
• MFcast #15. Все новинки Nokia World (X3 и X6, N97 Mini, Booklet 3G и N900), а также анонсы от SE Минувшая неделя ознаменовалась мероприятием Nokia World, на котором было представлено...

Как это работает?

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

Проблема современных систем голосования (как классических, так и компьютеризованных): человек не может удостовериться в том, что его голос учтен. Объясняется это, обычно, принципом анонимности голосования, но это сугубо техническая причина. Если хорошенько подумать, то можно найти способ проверки собственного голоса без нарушения принятых норм. Хорошее сравнение — банкоматы. Мы все ими пользуемся и доверяем, при этом наши деньги остаются в сохранности, и, что самое главное, мы всегда можем проверить каждую операцию (на сайте или в банке). Хорошая система электронных выборов должна быть проверяема на всех стадиях.

Для такой системы были определены следующие требования:

• система публичных/частных ключей: голосующие зашифровывают голос, кандидаты — расшифровывают
• легко-генерируемые случайные ключи: для каждого голосующего генерируется случайный ключ, так что голоса за одного кандидата от разных людей не являются идентичными в зашифрованном виде
• гомоморфизм

Про последний пункт мы поговорим чуть позже.

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

1. Каждый кандидат генерирует и публикует следующую информацию:
   • Большое простое число p
   • Число a_b (по модулю p)
   • Публичный ключ y_b (y_b = a^x_b mod p)
     • Частный ключ x_b (случайное число от 1 до p-1; не публикуется!)
2. Голосующий должен зашифровать свой голос — некое сообщение m (-1<m<p). Каждый голосующий имеет свои публичный и частный ключи — y_a и x_a, соответственно.
   • Формируется общий ключ SK (shared key): SK = (y_b)^x_a = (y_a)^x_b
   • Голос это пара (c1, c2) = (ya, m*SK) mod p
3. Только тот кандидат, за которого был отдан голос, сможет его расшифровать:
   • (m * SK * SK^-1) mod p = (m * a^x_ax_b * a^-x_ax_b) mod p = m

Вот простой пример:

1. p = 13, a = 2, y_b = 7, x_b = 11 (7 = 2¹¹ mod p).
2. m = 7, (c1, c2) = (2⁶, 7*(2¹¹)⁶) mod 13 = (12, 6)
3. (7*2⁶⁶ * 2^-66) mod 13 = 7 = m.

Теперь немного о последнем пункте списка требований: гомоморфизм (в нашем случае — гомоморфизм групп). Если вы знакомы с теорией групп из математики, то должны вспомнить это свойство. Если коротко: группа это математический объект, «замкнутый» относительно некоторой операции. Например, целые числа относительно сложения — группа, так как взяв два любые элемента из этой группы (два целых числа) и применив операцию сложения (сложив эти числа) мы получим другое целое число — другой элемент той же группы. Это и есть «замкнутость». Такую группу обозначили бы как (Z, +).

Пусть у нас есть две такие группы: (G, *) и (H, ·). Гомоморфизмом будет являться функция h: G → H, если h (u*v) = h (u) · h (v). В нашем случае функцией является зашифровка:

enc (u·v) = enc (u) ·enc (v).

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

enc (m1) · enc (m2) = (y_x1, m1 · SK1) · (y_x2, m · SK2) mod p = (y_x1, · (m1 · m2)(SK1 · SK2)) mod p = enc (m1 · m2).

Как происходит голосование?

1. Избиратель проверяет бюллетень. Используется принцип доказательства с нулевым разглашением. Голосующий выбирает два любых бюллетеня, соскребает случайные числа (публичный ключ) с одного из них (как в лотерее) и сканирует двумерный штрих-код чтобы удостовериться, что указанный там порядок кандидатов соответствует зашифрованной информации. Этот бюллетень перестает быть действительным, а избиратель использует второй.
2. Избиратель делает выбор.
3. Отрывает левую часть.
4. Уничтожает публичный ключ.
5. Сканирует бюллетень, уходит домой.

Отсканированные бюллетени публикуются на вебсайте. Проголосовавший может проверить, был ли его голос учтен, и если был — все ли прошло без ошибок.

Испытания

Данная система была опробована на выборах в локальные органы самоуправления в университетах MIT, Harvard, Unversite Catholique de Louvain (25000 избирателей), University of Ottawa. 3 ноября 2009 года эта система применялась на выборах в Takoma Park, Maryland, USA.

К прочтению

[1] Ben Adida. Advances in Cryptographic Voting Systems. MIT. (2006).
[2] Avi Rubin. An Election Day clouded by doubt, October 2004.
[3] Blakley, G. R. Safeguarding cryptographic keys. Proceedings of the National Computer Conference 48: 313-317, (1979).
[4] Josh D. Cohen and Michael J. Fischer. A robust and verifiable cryptographically secure election scheme. In FOCS, pages 372–382. IEEE Computer Society, 1985.
[5] S. Poblig and M. Hellman, An improved algorithm for computing logarithms over GF (p) and its cryptographic significance, IEEE, Transaction on Information Theory It-24:106-110, (1978).
[6] T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31, pg. 469-472. (1985)
[7] Презентация Jimin Park, Applied Cryptography class, Carleton University, Feb. 2011

Наши роботы искали похожие записи, но не нашли :(

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

4.1 Количество сетевой деятельности

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

Другое важное значение это нагрузка на узел L_node = M / |V|, или количество сообщений на каждый узел, и нагрузка на соединение L_link = M / |E|, или количество сообщений на каждое соединение (ребро графа).

Сообщение это набор битов; некоторые протоколы используют очень короткие сообщения (например, сигнальные биты), некоторые – очень длинные (например, графические файлы). Значит, для более точного подсчета эффективности системы нужно брать в расчет количество битов. Это значение назыавют битовой сложностью (bit complexity) протокола.

4.2 Время

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

Однако, мы можем найти значение времени, если сделаем еще несколько предположений. Время, найденное таким способом, называют идеальным или идеальной временной сложностью T. При “еденичных коммуникационных задержках” и “синхронизированных часах” любое сообщение передается и обрабатывается за один промежуток времени. В таком случае, общее время можно подсчитать зная битовую сложность.

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

Пример: вещание

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

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

Пусть E будет набор сущностей, а G коммуникационной топологией системы. Для упрощения, примем несколько дополнительных допущений:

1. Двусторонние соединения. (используем ненаправленный граф; см. рис. 3.2.1).
2. Полная надежность

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

3. Соединение (connectivity). Коммуникационная топология G является соединенной.

Из определения самой задачи вещания следует, что только один узел обладает информацией в начале, значит:

4. Уникальный инициатор

Простая стратегия, которой мы будем следовать, звучит следующим образом:

“если сущность обладает информацией, то она делится ею с соседями”

Чтобы создать набор правил, реализующий эту стратегию, необходимо определить набор статусных значений S. Из определения понятно, что нужно отличать узел-инициатор от всех остальных узлов. Поэтому, {initiator, idle} ⊆ S. Процесс может быть начат только инициатором (узлом, статус которого является “initiator”). Обозначим информацию, которую нужно передать, за I. Так выглядит набор правил B (x) (однинаков для всех сущностей):

1. initiator × ι → {send(I) to N (x)}
2. idle × Receiving (I) → {Process(I); send(I) to N (x)}
3. initiator × Receiving (I) → nil
4. idle × ι → nil

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

активность, сгенерированная протоколом, никогда не закончится

Представьте себе простую систему, состояющую из трех узлов, соединенных между собой (см. рис. 4.2.1). Пусть x будет инициатором, y и z будут idle, и все сообщения передаются с одинаковой скоростью; тогда y и z будут посылать сообщения друг другу до бесконечности.

Рис 4.2.1.

Для обхода этой проблемы каждая сущность должна отправлять сообщение соседям только один раз: когда она сама получает информацию. Этого можно добиться добавлением нового статуса “done”, который будет означать, что узел выполнил свою работу. Тогда S={initiator, idle, done}.

1. initiator × ι → {send(I)  to N (x); become done}
2. idle × Receiving (I) → {Process(I); become done; send(I) to N (x)}
3. initiator × Receiving (I) → nil
4. idle × ι →nil
5. done × Receiving (I) → nil
6. done × ι→nil

В этом случае сетевая деятельность протокола прекращается после конечного промежутка времени, или, другими словами, за конечное время каждый узел получает статус “done”.

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

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

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

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

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

Protocol Flooding
1. initiator × ι → {send(I) to N (x); become done}
2. idle × Receiving (I) → {Process(I); become done; send(I) to N (x) -sender}
3. initiator × Receiving (I) → nil
4. idle × ι → nil
5. done × Receiving (I) → nil
6. done × ι → nil

Этот алгоритм называется Flooding (затопление), потому что система “затапливается” сообщениями в процессе. Это базовый алгоритмический инструмент для распределенных вычислений.

Теперь мы знаем, что количество сообщений меньше 2m:

M[flooding] = 2m — n + 1.

Теперь посмотрим на затраты времени. Пусть d (x,y) будет обозначать дистанцию (длину кратчайшего пути) между узлами x и y в графе G. Естественно, что сообщение, переданное инициатором, должно достичь всех узлов, включая самый отдаленный. Итак, если x это инициатор, то идеальное время будет r (x) = Max {d (x, y): y ∈ E}; это значение также называют радиусом узла x. Другими словами, общее время зависит от топологии сети и его невозможно определить заранее. Однако, мы можем определить идеальное время в худшем из возможных случаев.

Так как любая сущность может быть инициатором, идеальное время выполнения в худшем случае будет d (G) = Max (r (x): x ∈ E}, что является диаметром графа G. Получается, идеальное время выполнения будет как максимум диаметром G:

T[flooding] ≤ d (G).

Наши роботы считают, что вас заинтересует это:

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

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

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

Сегодня мы познакомимся с общими определениями и понятиями распределенных сетей.

Это выдержки из моих конспектов, основанные на курсе Distributed Computing профессора Никола Санторо, а также его книги Design and Analysis of Distributed Algorithms.

Глава 1. Вселенная.

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

1.1 Сущности (узлы)

Сущностью может выступать любой процесс, процессор, компьютер, сетевой свитч, агент какого-либо рода и т.д. Каждая сущность (узел) обладает собственной локальной памятью, всключающий набор регистров, значения которых устанавливаются заранее. Примером регистра может быть status (x) — текущий статус узла x. Следующий набор стандартных допущений применим к любой сущности x ∈ E:

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

1.2 Внешние события

Поведение узла x ∈ E зависит от внешних событий или просто событий (event). При отсутствии события сущность ничего не делает. Возможны три типа внешних событий:

прибытие сообщения
срабатывание “будильника” локальных часов
спонтанный импульс

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

1.3 Действия

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

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

1.4 Поведение

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

Status × Event → Action

и называется правилом. Правило описывает какое действие должен произвести узел при событии в зависимости от текущего состояния. В примере с банкоматом можно придумать правило: если текущий статус счета является “заморожен”, то при событии “снять денег” нужно уведомить клиента о статусе и не выдать никаких денег.

Поведение сущности x выражается набором правил B (x). Этот набор должен быть полным и однозначным, то есть для каждого возможного события e и статуса s должно существовать одно и только одно правило в B (x) для (s, e). Этот набор правил также называют протоколом или распределенным алгоритмом сущности x.

Поведение всей среды определяется поведением каждого узла и называется коллективным поведением B (E) набора сущностей E.

B (E) = {B (x): x ∈ E}.

1.5 Однородное поведение

Коллективное поведение является однородным (гомогенным), если каждая сущность обладает одним и тем же поведением. То есть, ∀x, y ∈ E, B (x) = B (y). Интересный и очень важный факт:

Свойство 1.5.1 Каждое коллективное поведение можно превратить в однородное.

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

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

s × e → { if my role = workstation then Aworkstation else Aserver endif }.

Глава 2. Связь

В распределенной среде сущности общаются между собой отправкой и принятием сообщений. Сообщением называют любой конечный набор битов. Обмен сообщениями не обязательно проходит напрямую; возможно, сообщение проходит через другие сущности. Обозначим набор сущностей, которым узел x может отправить сообщение напрямую, как Nout (x) ⊆ E, а называть их будем для простоты “исходящими соседями”. Также, обозначим Nin (x) ⊆ E как набор всех узлов, которые могут отправить сообщение узлу x напрямую, и назовем их “входящими соседями”.

Соседство описывается графом G=(V, E), где V это набор узлов, а E ⊆ V × V это набор рёбер. Направленный граф G описывает коммуникационную топологию среды. Мы будем обозначать количество узлов, рёбер и диаметр графа n (G), m (G) и d (G), соответственно. При отсутствии неоднозначности, мы будем использовать только символы n, m и d.

Глава 3. Аксиомы и ограничения

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

3.1 Аксиомы

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

Аксиома 3.1.1 При отсутствии повреждений и ошибок, задержки коммуникации конечны.

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

Вторая аксиома гласит, что каждый узел имеет возможность различать своих соседей.

Аксиома 3.1.2. Каждая сущность может различать своих входящих соседей. Каждая сущность может различать своих исходящих соседей.

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

Нужно помнить, что это знание локально для узла.

3.2 Ограничения

3.2.1 Коммуникационные ограничения

Очередь (queuing). Соединение (x, y) может быть представлено как канал связи между узлами x и y. Различные ограничение описывают механизм работы такого канала, например, очереди FIFO (first-in-first-out) описываются следующим ограничением:

Последовательность сообщений (message ordering): при отсутствии повреждений и ошибок, сообщения, посланные одному и тому же исходящему соседу будут доставлены в таком же порядке, в котором они были посланы.

Двухсторонняя коммуникация. ∀x ∈ E, Nin (x) = Nout (x). Иными словами, если (x, y) ∈ E, то (y, x) ∈ E.

Нужно помнить, что (x, y) не обязательно то же самое соединение, что (y, x). Если мы имеем дело с двусторонними соединениями (рёбрами), то (x, y)=(y, x).

Рис. 3.2.1. В случае двусторонних соединений используется ненаправленный граф.

Ошибки. Несколько ограничений касаются ошибок или повреждений системы. Вот некоторые примеры:

Гарантированная доставка (guaranteed delivery). Любое сообщение, будучи отправленным, будет доставлено без повреждений.

С таким ограничением нам не нужно принимать во внимание возможные ошибки при передаче.

Частичная надежность (partial reliability). В будущем никаких ошибок не случится.

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

Полная надежность (total reliability). Ошибок не было и не будет.

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

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

Соединение (connectivity). Коммуникационная топология G является соединенной.

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

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

Единичные коммуникационные задержки. При отсутствии ошибок или повреждений задержка в передаче сообщения на любом соединении равняется одной еденице времени.

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

Наши роботы считают, что вас заинтересует это:

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

Это набор конспектов по курсу Software Engineering, основанный на книге Software Engineering, 8th edition, Ian Sommerville, Pearson Education, 2006.

Chapter 1

What is software? Computer program with a set of documentation (system design and structure and user documentation), configuration data and all additional sources of information directly related to the program

There are 2 types of software product:

1. Generic product. Stand-alone systems, sold on open market to everyone. Examples – desktop operating system, office packs or graphical editors.
2. Customized (bespoke) products. Developed for particular customers with special features. Examples – special systems for traffic control or airbus flight operations.

From developers’ stand of view, one of the main differences of those types is that for customized case the specifications for a software product is done mostly by the organization which buying it. For generic product development, specifications are created by the same development organization.

Nowadays, there is no straight line between those types as there was several years ago.

Software engineers, as any other engineers, make things work by applying theories, methods and tools (created, mostly, by computer scientists, but when it comes to practical problems, there’s often need to change the solution and develop your own way, still, based on some theory). Software engineering is not all about coding programs, there are much more problems to solve during the work on project, for example project management, scheduling of work, testing and choosing the right way to go.

Software engineering is concerned with all aspects of the development and evolution of complex systems. System engineering is concerned with hardware development, policy and process design.

Software process consists of four fundamental activities:

1.      Software specification where engineers or/and customers define what the product should do and how should it operate.

2.      Software development is designing and actual coding.

3.      Software validation is generally testing. It is important to check if the system is designed and implemented correctly.

4.      Software evolution is modifying the system according to new needs of customer (s).

Different types of software need different development process.

Software process model is a simplified description of a software process that presents one view of a process. And again, choice of a view depends on the system developing, sometimes it is useful to apply a workflow model, sometimes, for example – a role/action model.

Most software process models are based on one of three general models or paradigms of software development.

1.      The waterfall approach. In this case the development process and all activities are divided into phases such as requirement specification, software design, implementation, testing etc. Development goes phase-by-phase.

2.      Iterative development. An initial system is rapidly developed from very abstract specifications. Of course, it can be reimplemented according to new, probably more detailed specifications.

3.      Component-based software engineering (CBSE). The development process is done assuming some parts of the system is already exist, so the process focuses on integrating parts together rather than developing everything from scratch.

A software engineering method is a structured approach to software development whose aim is to facilitate the production of high-quality software in a cost-effective way. If not talking about history, today most common method is based on UML (Unified Modeling Language), which was created from different approaches from the past.

As any other thing related to software engineering, methods may vary depending on different situations.

For a software engineer it is always important to make sure the product is good, and there are different tools to analyze that. Overall, good piece of software should meet these attributes:

1.      Maintainability. Software should be developed in such way that it can be changed according to new specifications and needs of customers. This aspect is directly related to software evolution.

2.      Dependability. It includes reliability, security and safety. Good dependable system should make minimum (or no) economic damage in case of failure.

3.      Efficiency. Software should be efficient and should not waste system resources.

4.      Usability. With all hidden for an end-user requirements, first thing customer think of when they start using the program is how easy to do it and how good the documentation is. Software should be usable without too much effort from user. Therefore, developers should always keep in mind the type of an user system building for.

My thoughts

First chapter is introduction and most of things look familiar for me, especially after attending COMP3104 lectures. I think about software development as very complex process, which technically never ends because always has something to make better or add more features. While facing big problems and developing large systems, the necessity of every point of development become stronger. As such, I understand why maintainability is so important for both developers and customers.

Software engineering is a lot of responsibility: to other engineers, to customers and society around the product. It is a big challenge – applying theoretical methods on practice.

Chapter 2

The word ‘system’ is widely used, but the useful working definition of a system when we talk about particular parts and particular goals sounds like:

A system is a purposeful collection of interrelated components that work together to achieve some objective.

No matter how complicated and large any system might be, we can still apply this definition. Now if we talk about software systems, there are two categories:

1. Technical computer-based. This type of system includes hardware and software but not procedures and processes. Most of simple desktop software, OS etc. are examples of technical computer-based systems. Main point is: using this software has a purpose, but software itself does not know it, knowledge of this purpose is not part of a system.

2. Socio-technical systems includes hardware or/and software (actually, we can say it includes technical systems), but most important part it includes knowledge of how the system should be used and operated in order to achieve final objective. This kind of system includes predefined operational processes, people (to operate a system). Carleton University is a socio-technical system, because all of resources (library, buildings, computer labs, all physical things as well as general “knowledge”) are operated and used by certain people (profs, staff and students).

Socio-technical system is different from technical not only because of people. The book outlines three main distinctions:

— Parts of socio-technical system have properties that are properties of the system as a whole rather than associated with those parts particularly.

— Such system may be nondeterministic, which means that the same input don’t always produce the same output. System works and operated by human, who doesn’t always react the same way as some software.

— The way system works and achieves its objectives does not just depend on the system itself. It also depends on the stability of these objectives.

We should always keep in mind that the main principle of system is one of the main problems – system cannot be fully functional if even one part of it does not work. Interdependency causes this statement. This statement must be applied not only when we look at system and its parts, but also when we look broader – at different systems within another system. For example, we have a software program which is a system itself and consists of different components. They all work properly and system designed correctly, but if we actually plug this program into operating system (which is another system), and that OS operates all the hardware (which is also a system), we cannot be sure that the program will work as it suppose to. As a software engineer, person should always think wide.

One another source of possible problems is the ability of the system to involve and to be changed to accommodate modified system engineering requirements. It is very common when during such change software failure happens, even though software was working properly before an attempt to change it. Therefore, this kind of software failure is actually not software failure, but rather some mistake or series of mistakes during designing the system, so that modifying gone wrong.

There is a complex relationship between system components and this very fact says that the system is more than just a box with some functional stuff in it. Parts and relationships have different emergent properties and those properties are properties of the whole system. Often those properties can only be derived from sub-system interrelationships and are “invisible” when we look at particular system component. There are two types of emergent properties:

1. Functional. Everything related to how the system works. For example, functional requirement of a phone is to be able to make and receive calls.

2. Non-functional. Everything related to behaviour and operating environment. For that same phone non-functional emergent requirement may be “to be easy to use”.

Emergent properties are often very complex and it is hard to describe them. It is even harder to analyze some properties. For example, reliability. First of all, we should know that reliability is such a property which cannot be seen and analyzed without detailed analyze of every part of a system. Even if 99 of 100 parts of a system are super reliable and solid-stone-never-fail-parts, one little piece may cause failure of a whole system.

There are three related influences on the overall reliability of a system:

1. Hardware reliability

2. Software reliability

3. Operator reliability

This is very obvious, because any problem may come from one of three main parts of a socio-technical system.

System engineers are not just concerned with software but also with hardware and human interaction. They must think of services that system provides and how useful and easy to use different parts may be.

System requirements specify what the system must do and its properties. An important part of the requirements definition is to establish a set of overall objectives that the system should meet. A fundamental difficulty in establishing system requirements is that the problems are so complex, that there are so many related entities and there is no definitive problem specification. The true nature of a problem emerges only when a solution is created.

System design is concerned with how the system functionality is to be provided by the components of the system. Process of designing a system is fairy complicated and consists of different steps or phases. It starts with organizing requirements into related groups, then – identifying sub-systems that can (alone or interacting with each other) meet those requirements and cover all the groups of them. Then developers should actually assign requirements to sub-systems. Then, every sub-system’s functionality should be specified. It is also useful to specify relationships between sub-systems. When this step is done and all sub-systems are at least in some close to working state, software engineer should define sub-system interfaces. When this is done, it is possible to continue to develop these sub-systems in parallel.

Designing is one of the first and most important steps of product development. For almost all systems, there are many possible design decisions that meet the requirements. In perfect situation, developers choose design as they thing is the best for given requirements, but pretty often another facts affect this choice – customer’s desire, federal laws etc.

Next big step in developing is system modelling. Model of a system is an abstract representation of all parts and mechanisms of system. Usually model of a system is developed and shown as graphical image. There might be different scales of a model so it is possible to look at the system from different points of view and different scale.

Sub-system development is basically process of creating building blocks for a project. In fact, those sub-systems are not always developed from scratch for purposes of this particular project. Quite often developers can use sub-systems of different projects or even integrate some side-developed components. Sub-systems are usually developed in parallel. If the system developing process goes step-by-step, one component after another, it becomes very hard and expensive to make modifications. And there is (almost) always modifications to be done during development.

Systems integration is a process of putting all independently developed sub-systems into one. Integrating all the components at a time sounds like good way, but on practice it is not always possible, because development of different sub-systems takes different time. Also, adding sub-systems one-by-one or at least by blocks or sections reduces number of errors.

At finally, software evolution. This process is more abstract and doesn’t not directly related to first development, but still is very important. While developing software systems, changes can come even during designing and implementation, and of course more changes will come after some period of use. There may be just bug-fixing changes or adding new requirements. Changes should not be just technically motivated, different points of view should be taken to analyze process, such as business and technical prospective.

System decommissioning means taking the system out of service after the end of its useful operation lifetime. Hardware can be recycled, software can be reused for some different purposes or just be ‘forgotten’. Anyway, for a software, decommissioning is not such a big problem.

Software development might be such a complex process, so it is impossible to create a product alone or create it within small group of developers. In a complex projects organisational processes are important.

My thoughts:

After this chapter I can see the difference between two general types of systems when it comes to software or hardware, also now I understand why different objectives demand different sort of system. Any technical operation (mostly cyclic, or with no need to analyze situation in real-time, especially when it comes to something moral-related) can be done easily by technical systems, but there’s no such machine that can do anything without human. Socio-technical systems come along when there’s an objective and work on something to achieve that objective needs several decisions to make, and quite often those decisions can be made only by human.

Socio-technical systems seems more flexible and useful in many cases, still, there are a lot of disadvantages of this system. Human resource is not the best when it comes to errors (mistakes) and supporting socio-technical system in general is much more expensive.

Steps of developing model are familiar to me in general, but there are some new details we didn’t face while developing model for our Monopoly game, because even though we work almost as people work during large project, we didn’t face the same problems as, for example, Mac OS developers do. That’s why I found this chapter useful.

Chapter 3

Errors, mistakes and fails in software are common, usually a fail cause inconvenience but no serious long-term damages or something as serious as huge money loss or even health damage. However, in some systems failure can have very big and serious consequences. This type of system is called critical system. There are three main types of critical systems:

1. Safety-critical systems. Fails in this system may result in injury, death or environmental damage. For example, space shuttle with astronauts on board. If something goes wrong with navigation system, people may die.
2. Mission-critical systems. Fails in this system may result in failure of some goal-directed activity and main objective of the system may not be reached. The same space-shuttle is an example of mission-critical system, because even without astronauts taken in count, the whole mission might be failed.
3. Business-critical systems. Fails may cause loss of money for customers using this system. Bank money management system is an example.

The most important emergent property of a critical system is dependability. Systems that are unreliable and unsafe are often rejected by users. Possible failure cost may be so big users refuse to use the system. A system that may easily loose the information is very unsafe too, because data is often the most expensive part of organization.

As a summary of all seriousness of critical systems and software fails we can say that only trusted methods and techniques must be used for development.

Dependability of a system is the main component in “calculating” trustworthiness. Trustworthiness is a degree of user confidence that the system will operate exactly as it suppose to. Of course, calculating is not the right word, because such a value cannot be expressed numerically, but some abstract terms like “not dependable”, “very dependable” are used.

Trustworthiness and usefulness are not the same and not even directly related. Program may be very useful and easy to work with in many areas, but it may crash every time user hits more than three buttons at a time. Or vice versa, system may work as a solid stone, but all it does is printing random numbers.

Four principal dimensions to system dependability are: Availability, Reliability, Safety and Security.

All of these may be decomposed into another, for example security includes integrity (ensuring that data is not damaged) and confidentiality. Reliability includes correctness, precision and timeliness. All of them are interrelated.

Some other system properties may be considered under the heading of dependability:

1.      Repairability. How easy and fast system can be restored after fail. Unfortunately, most of today’s software systems use a lot of third-party components and therefore system’s repairabilty does not depend on system only

2.      Maintainability. How east and fast system can be changed to adopt new requirements and rules.

3.      Survivability. Ability of a system to continue work and deliver services after fail or attack.

4.      Error tolerance. Ability of a system to avoid input errors

System availability and reliability are closely related to each other. Both of them can be expressed as numerical probabilities – availability is the probability that system will be up and running to deliver services; reliability is the probability that the system will work correctly.

More precise definitions are:

—           Reliability – the probability of failure-free operation over a specified time in a given environment for a specific purpose.

—           Availability – the probability that a system, at a point in time, will be operational and able to deliver the requested services.

By definition, the environment for a system is quite important and has to be taken into account. Measuring the system in one environment doesn’t mean it will work with same results in different environment.

Three complementary approaches that are used to improve the reliability of a system are:

1.      Fault avoidance. Development techniques used to minimise the possibility of mistakes before they result in system faults.

2.      Fault detection and removal. Identifying and solving system problems before the system is used.

3.      Fault tolerance. Techniques used to ensure that some system errors doesn’t not result in failure.

Safety-critical systems are systems where it is essential that system operation is always safe. The system should never damage people or system’s environment even in case of failure. There are two classes of safety-critical systems:

1. Primary safety-critical software. This is software which is used as a controller in a system.
2. Secondary safety-critical software. This is software that can be indirectly result in injury.

There is no 100% safe and reliable system, so various methods are used to assure safety. What we can do is to ensure that accidents do not occur or the consequences of an accident are minimal. Three complementary ways of doing that are:

1. Hazard avoidance. System is designed in such way so that hazards are avoided, for example cutting machine can be ran only by pressing two buttons at the same time, so operator’s both hands are busy (still, he has plenty of other stuff that can be cut )))
2. Hazard detection and removal. System should have some components responsible for analyzing possible hazards and removing them, for example speed limiter for cars.
3. Damage limitation. If damage happened, system should make the result minimum. Cars always have airbags.

Security is a system attribute that reflects the ability of the system to protect itself from external attacks that may be accidental or deliberate. Nowadays, security is very serious issue, especially for Internet or network-related systems. Mistakes in designing security system can cause system faults because of possible attacks. Three types of damage that may be caused through external attack are:

1.      Denial of service. The system may be forced into a state when it doesn’t deliver services anymore and (from user’s point of view) doesn’t work at all.

2.      Corruption of programs or data. The system itself may be corrupted under attack, but also the data system operates and has access to.

3.      Disclosure of confidential information. The information system operates and has access to may be exposed to unauthorised people.

My thoughts:

We all got used to software failures and it became so common for us that programs are unstable and you can never be sure. I think this is bad thing, really bad, that’s why working on this chapter I was thinking of some “perfect future” where all software-based systems somehow managed to work perfectly fine, but actually, I don’t think this will ever happen. As you were saying on one lecture about mission-critical systems, the same software bug as there was 20 years ago came out and caused big damage. Even though computers are machines, they do mistakes, because they were created by human, and human indeed do mistakes.

Chapter 4

Software process is a set of activities that leads to the production of a software product. There’s no, of course, ideal software process and every project needs different. Software processes are complex and, like all other intellectual and creative processes, rely on people making decisions and judgements.

Still, there are some common parts for almost any software process:

1. Software specification. Defining the functionality of the software and constraints on its operation.
2. Software design and implementation.
3. Software validation. Testing the product to ensure it meets all requirements.
4. Software evolution.

Software processes can be improved by process standardisation where diversity in software processes across an organisation is reduced.

Three process models covered in this chapter are:

1.      Waterfall model. Dividing fundamental processes (specification, implementation etc) into phases.

2.      Evolutionary development. An initial system is rapidly developed from abstract specifications.

3.      Component-based software engineering. Development process is focused on integrating reusable components into a system rather than developing them from scratch.

In practice, of course, it is often impossible to work all the way trough within only one model. For example, sub-systems may be developed using different model than main system. Often, models are combined.

Principal stages of the waterfall model are:

1.      Requirements analysis and definition.

2.      System and software design

3.      Implementation and unit testing

4.      Integration and system testing

5.      Operation and maintenance.

The main principle is that the next phase cannot begin before previous is done. In practice, these stages may overlap and feed information to each other. During design, problems with requirements are identified. During coding design problems are found and so on.

During the final life cycle phase (operation and maintenance) the software put into use. Errors and omissions in the original software requirements are discovered. The system must evolve to be useful.

The advantages of waterfall model are that documentation is produced at each phase and that it fits with other engineering process models. Its major problem is its flexible partitioning of the project into distinct stages. Commitments must be made at early stage in the process, which makes it difficult to respond to changing customer requirements.

There are two fundamental types of evolutionary development:

1. Exploratory development where the objective of the process is to work with the customer to explore their requirements and deliver a final system. The development starts with the parts of the system that are understood. The system evolves by adding new features proposed by the customer.
2. Throwaway prototyping where the objective of the evolutionary development process is to understand the customer’s requirements and hence develop a better requirements definition for the system.

This approach is often more effective than the waterfall approach in producing systems that meet the immediate needs of customers. However, there are two major problems with this model:

• The process is not visible. Managers need regular deliverables to measure progress. If systems are developed quickly, it is not cost-effective to produce documents that reflect every version of the system.
• Systems are often poorly structured.

These problems are acute when the project is large, for the small systems (up to 500,000 lines of code) the author of the book thinks that the evolutionary process it the best choice.

In the majority of systems there is some software reuse. Pretty often this happens informally, when people working on the project know of designs or code which is similar to that required. The look at these, modify them and reuse in current project. It is often essential for rapid system development.

Stages for software process using component-based model are:

1. Component analysis
2. Requirements modification
3. System design with reuse
4. Development and integration.

Change is inevitable in all large software projects. The system requirements change as the business procuring the system responds to external pressures. Management priorities change; new technologies become available, design and implementation change. This means that the software process is not a one-off process; rather, the process activities are regularly repeated as the system is reworked in response to change requests. There are two process models that have been designed to support process iteration:

1.      Incremental delivery. The whole process of software development are broken down into a series of increments that are each developed in a turn. This process is something between the waterfall model and evolutionary model. Customers identify the services to be provided by the system. They also identify which of the services are most important for them and which are less. After basic development, customers take early delivery of part of the system and then they can experiment with the system. This helps them clarify their requirements for later increments. New increments are developed and combined with the existing parts, so the system is getting better and more functional after each increment.

2.      Spiral development. The development of the system spirals outwards from an initial outline through to the final developed system. This process may be represented as a spiral. Each loop represents a phase of the software process. Thus, the innermost loop might be concerned with system feasibility. Next loop – with requirement definition, etc.

My thoughts:

I really think mixing different software process models can give better results than using just one model. Even for such a small project as our Monopoly game, we started as a waterfall model: defining requirements and use-cases first, then – designing the system, components and signals. When coding takes place, I think it might be better to switch the process to something between waterfall model and evolutionary development. This sounds like incremental delivery, where customers are us, developers JWe develop some part of a system, make it executable and testable and test this part as if we were end-customers. This kind of work will reduce some errors, which can be seen only while executing and testing.

Chapter 5

Software project management is an essential part of software engineering. Good management cannot guarantee project success, however, bad management usually result in project failure. Software managers do the same kind of job as other engineering project managers. However, software engineering is different from other types of engineering. Some differences are:

1. The product is intangible. The software cannot be seen or touched; it is not physical at all.
2. There are no standard software processes. There is no specified process for particular task and quite often it is hard and takes time to manage which software development process is more suitable for the project.
3. Large software projects are often “one-off” projects. Large software projects are often very different in some ways from previous project. Therefore, even managers with large experience may find it difficult to anticipate problems.

Main activities of a software manager are:

• Proposal writing
• Project planning and scheduling
• Project cost
• Project monitoring and reviews
• Personnel selection and evaluation
• Report writing and presentations

Writing proposal to win a contract to carry out the work is important possible stage. It usually includes cost and schedule estimates and justifies why the project contract should be awarded to a particular organisation or team.

Project planning is concerned with identifying the activities, milestones and deliverables produced by a project.

The manager should keep track of the progress of the project and compare actual and planned progress and costs. Informal monitoring can often predict potential problems by revealing difficulties as they occur.

During a project, it is normal to have several reviews.

Project managers usually have to select people to work on their project. Ideally, skilled staff with appropriate experience will be available to work on the project, by in reality managers (in most cases) have to settle for a less-than-ideal project team. The reasons for this are:

1. The project budget may not cover the use of highly paid staff.
2. Staff with the appropriate experience may not be available either within an organisation or externally.
3. The organisation may wish to develop the skills of its employees, so inexperienced staff may be assigned to the project to learn and to gain experience.

Chapter 6

Requirements for the system are the descriptions of the services provided by the system and its operational constraints. The process of analyzing, documenting and checking services needed is called Requirements Engineering.

Requirement is quite important and widely used word in software engineering, but still it not used in industry in consistent way. In some cases requirement is some high-level, abstract statement of a service that system must provide. In some other cases – it is detailed definition of a system function.

There exist two general types of requirements while developing a system:

1.      User requirements are statements in natural language, of what services the system is expected to provide and the constraints under which it must operate. They should be concerned on functional and non-functional requirements from user’s point of view, describing in detail aspect of a system that are important for customer. While working on user requirements, it’s important to avoid everything related to system design.

2.      System requirements is a set of system functions descriptions in detail. Also, requirement document should be precise and define exactly what it is to be implemented. System requirements for software engineers are starting point for developing system, because they describe the way system should be designed and implemented. How user requirements should be provided.

Software system requirements are often classified as functional, non-functional or domain requirements.

Functional requirements describe what system should do, how it should react to different inputs and systems behavior at different situations. Statements of functional requirement should tell exactly what should happen in which cases, still, these requirements keep pretty abstract.

Non-functional requirements are constraints on the services of functions offered by the system. They include such aspects of development as timing, development process and standards. Non-functional requirements can be related to emergent properties such as reliability, response time etc. They are rarely associated with particular system features and more often used to describe more general aspects of a system, for example “user friendly graphical user interface”.

Domain requirements come from the application domain of the system and that reflect characteristics of that domain. They come more from the system itself rather than from specific need of system users. Domain requirements are important because they often reflect fundamentals of the application domain.

Chapter 7

The goal of the requirement engineering is to create and maintain a system requirement document. The overall process includes four high-level sub-processes. These are concerned with assessing whether the system is useful to the business (feasibility study); discovering requirements (elicitation and analysis); converting these requirements into some standard form (specification); and checking that the requirements actually define the system that the customer wants (validation).

Feasibility study produces feasibility report and leads to next process – requirements elicitation and analysis. Then, system models and requirements specification produced, next – user and system requirements and requirements validation processes come, and as result of all these sub-processes (they also rely on each other during requirement engineering process) the requirement document developed.

Feasibility studies answers number of questions:

1.      Does the system contribute to the overall objectives of the organisation?

2.      Can the system be implemented using current technology and within given cost and schedule constraints?

3.      Can the system be integrated with other systems which are already in place?

In a feasibility study in it often that you consult information sources such as the managers of the departments where the system will be used, software engineers who are familiar with the type of system that is proposed, technology experts and end-users of the system.

In the next stage, the requirements elicitation and analysis, software engineers work with customers and end-users of a system to find out about application domain, what services the system should provide, the general performance of the system. When these general requirements are ready, developers should check if the requirements actually define the system that the customer wants. These checks include:

• Validity checks. Further thought and analysis may identify additional or different functions that are required.
• Consistency checks. Requirements should not conflict.
• Completeness checks. Requirement document should include requirements, which define al functions and constraints intended by the system user.
• Realism checks. Using knowledge of existing technology, the requirements should be checked to ensure that they could actually be implemented.
• Verifiability. To reduce the potential for dispute between customer and contractor, system requirements should always be written so that they are verifiable.

The requirements for large project are always changing. Often, because the problem cannot be fully defined, the software requirements are bound to be incomplete. Requirement management is the process of understanding and controlling changes to system requirements. This includes keeping track of individual requirements and maintaining links between dependent requirements, establishing a formal process for making change proposals and linking these to system requirements.

My thoughts:

Requirements are, I believe, the most known part of this book to me. We discussed requirements quite a lot, and I see why they are important. During requirement engineering process (if I can call it that fancy way :) ) for our Monopoly game, we faced problems, discussed in this chapter. For example, some sort of consistency checks were done after Iteration 1 and we found some requirements conflicts and overlap one another. Completeness check showed that we still missing two requirements, not really important and basic ones, but still, if we were starting implementation, at some point we would come back and think again.

We didn’t do any feasibility studies, except for maybe one question – “Can the system be implemented using current technology and within given cost and schedule constraints?”. Given cost is a term mark and schedule was set, so we didn’t really deep thinking and analysing. For large and real project, this is much more serious questions.

Chapter 8

User requirement should be written in natural language to be understandable by non-technical people, but during developing process requirements may be expressed in more technical way. One widely used technique is to document the system specification as a set of system models. Models are graphical representation of what system should do and how it should operate, that’s why models are often more easy to understand than even detailed natural language description. Models are also an important bridge between the analysis and design process.

At an early stage of requirement engineering developers should define the boundaries of the system. This involves working with system stakeholders to distinguish what is the system and what is the system’s environment. These decisions should be made early to limit the cost of developing and time for analysis.

Once some decisions on the boundaries of the system have been made, part of the analysis activity is the definition of that context and the dependencies that a system has on its environment. Producing a simple architectural model is the first step in this activity.

Architectural models describe the environment of a system. However, they don’t show the relationship between the other systems in the environment and the system that is being specified. Therefore, simple architectural models are normally supplemented by other models, such as process models, that show the process activities supported by the system.

Behavioural models are used to describe the overall behaviour of the system. Two types of behavioural models exist:

• Data-flow models, which model the data processing in the system. It is an intuitive way of showing how data is processed by a system. Data-flow models are valuable because tracking and documenting how the data associated with a particular process moves through the system helps analysts understand what is going on. This type of models show a functional perspective where each transformation represents a single function or process. They show the entire sequence of action that take place from an input being processed to the corresponding output that is the system’s response.
• State machine models, which model how the system reacts to events. It showssystem states and events that cause transition from one state to another. It does not show the flow of data within the system. A state machine model of a system assumes that, at any time, the system is in one of a number of possible states. When a signal is received, trigger may switch a transition to a different state.

These types of models can be combined.

Most large software systems make use of a large database of information. In some cases, this database is independent of the software system. In others, it is created for the system being developed. An important part of systems modelling is defining the logical form of the data processed by the system.

The most widely used data modelling technique is Entity-Relation-Attribute modelling (ERA modelling), which shows the data entities, their associated attributes and the relations between these entities. These models have been widely used in database design.

Like all graphical models, data models lack detail, and you should maintain more detailed descriptions of the entities, relationships and attributes that are included in the model. More detailed descriptions are often stored in a repository or data dictionary. A data dictionary is an alphabetic list of the names included in the system models. As well as the name, the dictionary should include an associated description of the named entity and, if the name represents a composite object, a description of the composition.

An object-oriented approach to the whole software development process is now commonly used. This means expressing the system requirements using an object model, designing using objects and developing the system in an object-oriented programming language.

Developing object models during requirements analysis usually simplifies the transition to object-oriented design and programming. However, as author notices, end-users often find object models unnatural and difficult to understand.

Object-oriented modelling involves identifying the classes of object that are important in the domain being studied. These are often organised into taxonomy. A taxonomy is a classification scheme that shows how an object class is related to other classes through common attributes and services. To display this taxonomy, the classes are organised into an inheritance hierarchy with the most general object classes at the top.

The design of class hierarchies is not easy, so the analyst need to understand, in detail, the domain in which the system is to be installed.

As well as acquiring attributes and services through an inheritance relationship with other objects, some objects are groupings of other objects. The classes representing these objects may be modelled using an object aggregation model.

A structured method is a systematic way of producing models of an existing system or a system that is to be built. Structured methods provide a framework for detailed system modelling as part of requirements elicitation and analysis.

My thoughts:

As everything big and important today, such process as software engineering is based on some abstract things. System models are abstract and detailed at the same time. Different types are used, but again, as I said before, my opinion is “mixing is better”, or in this case using different types of models to describe different sides of development have to be done.

Modelling the system is important, because this is the base, most fundamental part of actual work after requirements are defined, or at least part of them. Even for such a small project as our Monopoly game, I cannot imagine starting coding from scratch with no requirements defined and model developed, especially when there are four people in the team. Models are also useful to divide work between developers I guess: when signals are defined and model is created, different components may be implemented by different people, sometimes – in the different parts of Earth (like most of Open Source developers work).

Chapter 9

Specification for critical systems is important. Because of the high potential costs of system failure, it is important to ensure that the specification for critical systems accurately reflects the real needs of users of the system.

System functional requirements may be generated to define error checking and recovery facilities and features that provide protection against system failures. Non-functional requirements may be generated to define the required reliability and availability of the system.

Critical systems specifications’ objective is to understand the risks faced by the system and generate dependability requirements to cope with them. The process of risk analysis consists of four steps:

1.      Risk identification. Potential risks that might arise are identified. These are dependent on the environment in which the system is to be used. In safety-critical systems, the principal risks are hazards that can lead to an accident. Experienced engineers, working with domain experts and professional safety advisors, should identify system risks. Group working techniques such as brainstorming may be used to identify risks.

2.      Risk analysis and classification. The risks are considered separately. Those that are potentially serious and not implausible are selected for further analysis. Risks can be categorised in three ways:

a.       Intolerable. The system must be designed in such a way so that either the risk cannot arise or, if it does arise, it will not result in an accident. Intolerable risks are those that threaten human life or the financial stability of a business and which have a significant probability of occurrence.

b.      As low as reasonably practical (ALARP). The system must be designed so that the probability of an accident arising because of the hazard is minimised, subject to other considerations such as cost and delivery. ALARP risks are those which have less serious consequences or which have a low probability of occurrence.

c.       Acceptable. While the system designers should take all possible steps to reduce the probability of an ‘acceptable’ hazard arising, these should not increase costs, delivery time or other non-functional system attributes.

3.      Risk decomposition. Each risk is analysed individually to discover potential root causes of that risk. Different techniques for risk decomposition exist. The one discussed in the book is Fault-tree analysis, where analyst puts hazard at the top and place different states which can lead to that hazard above. States can be linked with ‘or’ and ‘and’ symbols. Risks that require a combination of root causes are usually less probable than risks that can result from a single root cause.

4.      Risk reduction assessment. Proposals for ways in which the identified risks may be reduced or eliminated are made. Three possible strategies of risk deduction that can be used are:

a.       Risk avoidance. Designing the system in such a way that risk or hazard cannot arise.

b.      Risk detection and removal. Designing the system in such a way that risks are detected and neutralised before they result in an accident.

c.       Damage limitation. Designing the system in such a way that the consequences of an accident are minimised.

In the 1980s and 1990s, as computer control become widespread, the safety engineering community developed standards for safety critical systems specification and development. The process of safety specification and assurance is part of an overall safety life cycle that is defined in an international standard for safety management IEC 61508 (IEC, 1998).

Security and safety requirements have something in common; however, there are some differences between these types of requirements.

The conventional (non-computerised) approach to securityanalysis is based around the assets to be protected and their value to an organisation. The stages in this process are:

1.      Asset identification and evaluation

2.      Threat analysis and risk assessment

3.      Threat assignment

4.      Technology analysis

5.      Security requirements specification

Reliability is a complex concept that should always be considered at the system rather than the individual component level. Component in the system are interdependent, so a failure in one component can be propagated through the system and affect the operation of other components. Three types of reliability should be taken in consideration – hardware reliability, software reliability and operator reliability.

My thoughts:

I think almost every system can be dangerous somehow, it’s a nature of things that if something does something, this something can be done in other, more insecure or unsafe way. Especially, in such a complex structures as software systems. Engineers do their best to develop better, more secure and safe systems, but while increasing the size of system all the problems and risks increase, so all techniques of risk avoidance or reduction are in this infinite race between system size and safety. Previous chapters were all about important thing about functional part of a system, how system should be developed etc. This chapter is also about developing and designing the system, but it shows the importance of other side.

Chapter 10

The term formal methods is used to refer to any activities that rely on mathematical representations of software including formal system specification, specification analysis and proof, transformational development, and program verification. In the 1980s many software engineering researchers proposed that using formal development methods was the best way to improve software quality. They also predicted that by 21^st century a large proportion of software would be developed using formal methods. However, this prediction has not come true.

Critical systems development usually involves a plan-based software process that is based on the waterfall model of development. Both the system requirements and the system design are expressed in detail and carefully analysed and checked before implementation begins. The involvement of the client decreases and the involvement of the contractor increases as more detail is added to the system specification. In the early stages of the process the specification should be ‘customer-oriented’. Stages of software specification and its interface with the design process are (in order):

User Requirements Definitions -> System requirements specification -> Architectural design -> Formal specification -> High-level design.

Depending on the process used, specification problems discovered during formal analysis might influence changes to the requirements specification if this has not already been agreed.

Two fundamental approaches to formal specification have been used to write detailed specifications for industrial software systems:

1. An algebraic approach where the system is described in terms of operations and their relationships.
2. A model-based approach where a model of the system is built using mathematical constructs such as sets and sequences, and the system operations are defined by how they modify the system state.

Large systems are usually decomposed into sub-systems that are developed independently. Sub-systems make use of other sub-systems, so an essential part of the specification process is to define sub-system interfaces.

The algebraic approach was originally designed for the definition of abstract data type interfaces. In an abstract data type, the type is defined by specifying the type operations rather than the type representation, so it is similar to an object class.

The process of developing a formal specification of a sub-system interface includes the following activities:

1. Specification structuring. Organise the informal interface specification into a set of abstract data types or object classes.
2. Specification naming. Establish a name for each abstract type specification.
3. Operation selection. Choose a set of operations for each specification based on the identified interface functionality.
4. Informal operation specification. Write an informal specification of each operation.
5. Syntax definition. Define the syntax of the operations and the parameters to each.
6. Axiom definition. Define the semantics of the operations by describing what conditions are always true for different operation combinations.

The simple algebraic techniques can be used to describe interfaces where the object operations are independent of the object state. Therefore, the result of applying an operation should not depend on the results of previous operations. As structure increases in size, algebraic descriptions become increasingly difficult to understand.

Model-based specification is an approach to formal specification where the system specification is expressed as a system state model. System operations are defined by how they affect the state of the system model.

While developing a model-based specification, state variables and predicates should be defined.

My thoughts:

Maybe I just don’t have any good experience, but for me a model-based approach seems like too complicated case, and algebraic approach sound more natural.

Chapter 11

Architectural design is the initial design process of identifying sub-systems and establishing a framework for sub-system control and communication. Using large-grain components improves performance, and using fine-grain components improves maintainability, so if both of these are important system requirements developers should find some compromise solution. There is an overlap between the process of requirements engineering and architectural design.

Sub-system design is an abstract decomposition of a system into large-grain components, each of which may be a substantial system in its own right. Block diagrams are often used to describe sub-system designs where each box in the diagram represents sub-system. Sub-systems can have their own sub-systems, in that case boxes are placed into boxes. Arrows mean that data and or control signals are passed from sub-system to sub-system in the direction of the arrows.

Architectural design is a creative process so many decisions are being made depending on requirements, specific rules for particular project and experience of an architect. Architectural models that may be developed may include:

• A static structural model that shows the sub-systems or components that are to be developed as separate units.
• A dynamic process model that shows how the system is organised into processes at run-time.
• An interface model that defines the services offered by each sub-system through its public interface.
• Relationship model that shows relationships, such as data flow, between the sub-systems.
• A distributed model that shows how sub-systems may be distributed across computers.

Different models may be used. Sub-systems making up a system exchange information so that they can work together effectively. There are two fundamental ways in which this can be done.

1. All shared data is held in a central database that can be accessed by all sub-systems. A system model based on a shared database is sometimes called a repository model.
2. Each sub-system maintains its own database. Data is interchanged with other sub-systems by passing messages to them.

The majority of systems that use large amount of data are organised around a shared database or repository. This model is suited to applications where data is generated by one sub-system and used by another.

The client-server architectural model is a system model where the system is organised as a set of services and associated servers and clients that access and use the services. Clients may have to know the names of the available servers and the services that they provide.

The layered model of an architecture (sometimes called an abstract machine model) organises a system into layers, each of which provide a set of services. Each layer can be thought of as an abstract machine whose machine language is defined by the services provided by the layer. This ‘language’ is used to implement the next level. This approach supports the incremental development of systems.

After an overall system organisation has been chosen, different approaches may be used to decompose sub-systems into modules. Two main strategies of doing this are:

1. Object-oriented decomposition where a system is decomposed into a set of communicating objects. Object call on the services offered by other objects. The object-oriented approach is well-known and convenient, but still has some disadvantages, for example, to use services, objects must explicitly reference the name and the interface of other objects. If an interface change is required to satisfy proposed system changes, the effect of that change on all users of the changed object must be evaluated.
2. Function-oriented pipelining where the system is decomposed into functional modules that accept input data and transformed into output data. Each processing step is implemented as a transform.

The models for structuring a system are concerned with how a system is decomposed into sub-systems. To work as a system, sub-systems must be controlled so that their services are delivered to the right place at the right time. There are two generic control styles that are used in software systems:

• Centralised control. One sub-system has overall responsibility for control and starts and stops other sub-systems. It may also devolve control to another sub-system bit will expect to have this control responsibly returned to it.
• Even-based control. Rather than control information being embedded in a sub-system, each sub-system can respond to externally generated events. These events might come from other sub-systems or from the environment of the system.

Chapter 12

A distributed system is a system where the information processing is distributed over several computers rather than confined to a single machine. Advantages of distributed system are coming from several important characteristics of distributed systems. These advantages are:

1. Resource sharing
2. Openness
3. Concurrency
4. Scalability
5. Fault tolerance

However, there are (as usual) some disadvantages:

1. Complexity
2. Security
3. Manageability
4. Unpredictability

The design challenge is to create the software and hardware to provide desirable distributed system characteristics and, at the same time, minimise the problems that are inherent in these systems.

Two generic types of distributed systems are:

• Client-server architectures. The system may be thought of as a set of services that are provided to clients that make use of these services. Servers and clients are treated differently. The simplest client-server architecture is called a two-tier client-server architecture, where an application is organised as a server (or multiple servers) and a set of clients. The client might be thin (when all of the application processing and data management is carried out on the server, and the client is just presenting data) or fat (where client implements the application logic and interactions with user, and server is responsible for data management)
• Distributed object architectures. There is no distinction between servers and clients, and the system may be thought of as a set of interacting objects whose location is irrelevant. There is no distinction between a service provider and a user of these services. A more general approach to distributed system design is to remove the distinction between client and server and to design the system architecture as a distributed object architecture. Objects may be distributed across a number of computers on a network and communicate through middleware. This middleware is called an object request broker.

The simplest model of a distributed system is a multiprocessor system where the software system consists of a number of processes that may (but need not) execute on separate processors. This approach is widely used in large real-time systems.

Peer-to-peer (p2p) systems are decentralised systems where computations may be carried out by any node on the network and, in principle at least, no distinctions are made between clients and servers. The overall system is designed to take advantages of the computational power and storage available across a potentially big network of computers.

My thoughts:

Our Monopoly game is an example of client-server architecture with a thin client. We have one server which is responsible for all computations and data management, and client is only a GUI. This is the easiest way for us, because technically one program will do everything and another will only show that. It is also better in terms of security:

Chapter 13

There are many types of application system and, on the surface, they may seem to be very different. However, after examining the architectural organisation of applications many of these superficially dissimilar applications have much in common. There are four broad types of architectures discussed in the book:

1. Data-processing applications. These are data-driven applications, they process data in batches without explicit user interventions during the processing. The specific action taken by the application depend on the data that it is processing. Applications of this type are commonly used in business, where similar operations are carried out on a large amount of data. The nature of data-processing systems where records or transactions are processed serially with no need to maintain state across transactions means that these systems are naturally function-oriented. Functions are components that do not maintain internal state information from one invocation to another.
2. Transaction-processing applications. These are database-centred applications that process user requests for information and that update the information in database. These are most common type of interactive business systems. They are organised in such a way that user actions can’t interfere with each other and the integrity of the database is maintained. To simplify the management of different terminal communication protocols, large-scale transaction-processing systems may include middleware that communicates with all types of terminal, organises and serialises the data from terminals, and sends that data for processing. Implementations of information and resource management systems based on Internet protocols are now the norm.
3. Event-processing systems. This is a very large class of application where the actions of the system depend on interpreting events in the system’s environment. These events might be the input of a command by a system user or a change in variables that are monitored by the system. Real-time systems also fall into this category. However, for real-time systems, events are not usually user interface events but events associated with sensors or actuators in the system.
4. Language-processing systems. These are systems where the user’s intensions are expressed in a formal language (such as Java). The language-processing system processes this language into some internal format and then interprets this internal representation. The best known language-processing systems are compilers, which translate high-level language programs to machine code. In the very abstract way the language-processing system’s process can be described as: instructions go to the translator, which checks syntax and semantics and then generate some abstract instructions for interpreter. Interpreter takes those instructions along with data, executes the program and gives the output. Other components  might also be included that transform the syntax tree to improve efficiency and remove redundancy from the generated machine code.

Chapter 14

An object-oriented system is made up of interacting objects that maintain their own local state and provide operations on that state. The representation of the state is private and cannot be accessed directly from outside the object. Object-oriented design processes involve designing object classes and the relationships between them.

Object-oriented design is one phase of the development process:

• Object-oriented analysis is concerned with developing an object-oriented model of the application domain. The objects in that model reflect the entities and operations associated with the problem to be solved.
• Object-oriented design with developing an object-oriented model of a software system to implement the identified requirements.
• Object-oriented programming is concerned with realising a software design using an object-oriented programming language, such as Java.

An object is an entry that has a state and a defined set of operations that operate on that state. The state is represented as a set of object attributes. Objects created according to an object class definition.

In such a language as Java it is easy to take an object-oriented design and produce an implementation where the objects are concurrent processes. There are two kinds of concurrent object implementation:

1. Servers where the object is realised as a parallel process with methods corresponding to the defined object operations.
2. Active objects where the state of the object may be changed by internal operations executing within the object itself.

The general process that is described in the book has a number of stages:

1. Understand and define the context and the modes of use of the system.
2. Design the system architecture
3. Identify the principal objects in the system.
4. Develop design models
5. Specify object interfaces.

My thoughts:

The concept of object-oriented design seemed really unnatural for me five or six years ago when I used to code with Visual Basic and Delphi. I’ve seen no sense in making things so complicated and abstract rather than just write the program you need using procedures, jumps etc. Today it’s the other way around – I don’t see any other way of programming something bigger that bash script.

Chapter 15

Computers are used to control a wide range of systems from simple domestic machines to entire manufacturing plants. These computers interact directly with hardware devices. The software in these systems is embedded real-time software that must react to events generated by the hardware and issue control signals in response to these events. A good definition from author of the book is the following:

A real time system is a software system where the correct functioning of the system depends on the results produced by the system and the time at which these results are produced. A soft real-time system is a system whose operation is degraded is results are not produced according to the specific timing requirements. A hard real-time system is a system whose operation is incorrect if results are not produced according to the timing specification.

One way of looking at a real-time system is as a input/response system. For a specific input system responds in a particular way. These inputs (or stimuli) fall into two classes:

1. Periodic stimuli. These occur at predictable time intervals.
2. Aperiodic stimuli. These occur irregularly.

Because real-time systems must meet their timing constraints, sometimes it is impossible to use object-oriented development for hard real-time systems. Object-oriented development involves hiding data and accessing attributes values through operations defined with the object, which means there is a significant performance overhead in object-oriented systems because extra code is required to mediate access to attributes and handle calls to operations.

A state model of a system assumes that, at any time, the system is in one of a number of possible states. When a stimulus is received, this may cause a transition to a different state.

A real-time operating system manages processes and resource allocation in a real-time. There are many RTOS products available, from very small, simple systems for consumer devices to complex systems for cell phones and mobile devices and operating systems specially designed for process control and telecommunications. RTOS usually inclides:

• A real-time clock. Provides information to schedule processes periodically.
• An interrupt handler. Manages aperiodic requests for service.
• A scheduler. Responsible for examining the processes that can be executed and choosing one of these for execution.
• A resource manager. Allocates appropriate memory and processor resources for ascheduled process.
• A despatcher. This component is responsible for starting the execution of a process.

Real time operating system’s actions required to start a process looks like this: Scheduler chooses process for execution based on process priority, the expected execution time and the deadlines of the ready processes; resource manager allocates memory and processor; despatcher starts execution on available processor.

Chapter 16

User interface of a software product is the “face” of it. Many “user errors” are caused by the fact that user interfaces do not consider the capabilities of real users and their working environment. A poorly designed interface means that users will probably be unable to access some of the system features, will make mistakes and will fell that the system hinders rather than helps them in achieving whatever they are using system for.

While designing user interface, some physical and mental capabilities of the people who will use the software should be taken into account. Some of them are:

1. People have a limited short-term memory.
2. We all make mistakes, especially when we have to handle too much information or are under stress. Too much system warnings, alarms etc. can annoy stressed people thus increase the chances that they will make more operational mistakes.
3. We have a diverse range of physical capabilities. Some people see and hear better than other, some people are color-blind, etc.
4. We have different interaction preferences. Some people like to work with pictures, others with text.

These human factors are the basic for the design principles.

The principle of user familiarity suggests that users should not be forced to adapt to an interface because it is convenient to implement.

The principle of user interface consistency means that system commands and menus should have the same format, parameters should be passed to all commands in the same way, and command punctuation should be the similar. However, full consistency is neither possible nor desirable.

The principle of minimal surpriseis appropriate because people get very irritated when a system behaves in an unexpected way.

The principle of recoverability is important because users inevitably make mistakes when using a system. The interface design can minimise these mistakes, but mistakes can never be completely eliminated. Consequently, system should include some tools allowing users recover from their mistakes. These can be of three kinds:

• Confirmation of destructive actions. To avoid accidental destructions or to explain consequences for user.
• The provision of an undo facility. Undo restores the system to a state before the action occurred. Multiple levels of undo are useful because users don’t always recognise that a mistake has been made. (Why mspaint has only three levels of undo, or do they think that people who use mspaint are only pros and don’t do too much mistakes??!)
• Checkpointing. It involves saving the state of a system at periodic intervals and allowing the system to restart from the last checkpoint. Similar to simple backup system for data.

A related principle is the principle of user assistance. Interfaces should have built-in user assistance or help facilities.

The overall user interface design process in general concerned with two main questions: how should the user interact with the system and how should information from the system be presented to the user?

User can interact with computer system in a number of ways, most common of them are:

1.      Direct manipulation. The user interacts directly with objects on the screen. It usually involves a pointing device, e.g. a mouse or a finger on a touch screen (like on your white 16 gig iPhone).

2.      Menu selection. The user selects a command from a list of possibilities (a menu).

3.      Form fill-in. The user fills in the fields of a form. Some fields may have associated menus, and the form may have action to be initiated.

4.      Command language. User enters a special command and associated parameters to instruct the system what to do (bash!)

5.      Natural language. The user issues a command in natural language. This is usually a front-end to a command language. (I also think that this includes voice commands)

Presentation of information by a computer system depends on user of the system. Also, the issue of colour in presentation is important. The most important key guidelines for the effective use of colour are:

1. Limit the number of colours employed and be conservative how these are used.
2. Use colour change to show a change in system status.
3. Use colour coding to support the task users are trying to perform.
4. Use colour coding in a thoughtful and consistent way.
5. Be careful about color pairings.

The user interface design process includes sub-processes concerned with user analysis, interface prototyping and interface evaluation. The aim of user analysis is to sensitise designers to the ways in which users actually work. Different techniques (task analysis, interviewing, observation) are used during user analysis.

User interface prototype development should be a staged process with early prototypes based on paper versions of the interface that, after initial evaluation and feedback, are used as a basis for automated prototypes. The goals of user interface evaluation are to obtain feedback on how a UI design can be improved to assess whether an interface meets its usability requirements.

My thoughts:

As I was reading this chapter, I was thinking about how serious and professional Apple’s user interface designers are. Every point of the stuff discussed in this chapter was a serious for them. Like the principle of user consistency: in Mac OS user can always be sure, that the program he never used before will have a menu line at the top of the screen. ALWAYS!

Actually, the iPhone is one of the few products where I don’t even want to customize user interface, because it feels like someone did think.

In general, I think of user interface as a very important and really interesting field in software engineering. Right now I’m working on GUI for our project, so this chapter was pretty useful for me.

Chapter 17

Rapid software development processes are designed to produce useful software quickly. Generally, they are iterative processes where specification, design, development and testing are interleaved. The software is not developed and deployed in its entirety, but in a series of increments, with each increment including new system functionality. The two main advantages to adopting an incremental approach to software development are:

1.      Accelerated delivery of customer services. Early increments of the system can deliver high-priority functionality.

2.      User engagement with the system. Users of the system have to be involved in the incremental development process because they have to provide feedback to the development team on delivery increments.

However, as usual, there are some major difficulties with iterative development and incremental delivery are:

1.      Management problems. Incrementally developed systems change so quickly that it is not cost-effective to produce lots of system documentation.

2.      Contractual problems. When there is no system specification, it may be difficult to design a contract for the system development.

3.      Validation problems. In a specification-based process, verification and validation are geared towards demonstrating that the system meets its specifications.

4.      Maintenance problems. Continual change tends to corrupt the structure of any software system. This means that anyone apart from the original developers may find the software difficult to understand.

Agile methods are iterative development methods that focus on incremental specification, design and system implementation. They involve the customer directly in the development process. Reducing development overhead can make faster software development possible. Extreme programming (XP) is a well-known agile method that integrates a range of good programming practices such as systematic testing, continuous software improvement and customer participation in the development team.

In an XP process, customers are intimately involved in specifying and prioritizing system requirements. The requirements are not specified as lists of required system functions. Rather, the system customer is part of the development team and discusses scenarios with other team members.

Rapid application development involves using development environments that include powerful tools to support system production. These includes database programming languages, form and report generators, and links to office applications.

Throw away prototyping is an iterative development process where a prototype system is used to explore the requirements and design options. This prototype is not intended for deployment by the system customer.

My thoughts:

Rapid software development seems interesting for me, because it somehow related to our project. Even though we had quite a lot of time and a case study (which almost means we had a set of requirements ready to be organized and used), extreme programming sounds like a good description of last two weeks before iteration 2 J

Anyway, this type of software development is interesting, but I’d prefer a regular, no-rush and planned process, it is much less stress and more creativity (at least for the type of person I am).

Chapter 18

Reuse-based software engineering is an approach to development that tries to maximize the reuse of existing software. The software units that are reused may be of radically different sizes. There may be an application system reuse, different particular component reuse or object and function reuse. A complementary form of reuse is concept reuse, where rather than reuse a component, the reused entity is more abstract and is designed to be configured and adapted for a range of situations.

An obvious advantage of software reuse is that overall development costs should be reduced. Fewer software components need be specified, designed, implemented and validated. However, there are also costs and problems associated with software reuse. There is a significant cost associated with understanding whether a component is suitable for reuse in a particular situation and in testing that component to ensure compatibility.

Design patterns are high-level abstractions that document successful design solutions. They are fundamental to design reuse in object-oriented development. A pattern description should include a pattern name, a problem and solution description, and a statement of the results and trade-offs of using the pattern. A huge number of published patterns are now available covering a range of application domains and languages. The use of patterns is an effective form of reuse.

Program generators are an alternative approach to concept reuse where the reusable concepts are embedded in a generator system. The designer specifies the abstractions required using a domain-specific language, and an executable program is generated.

Application frameworks are collections of concrete and abstract objects that are designed to be reused through specialization and addition of new objects. Three classes of framework are:

• System infrastructure frameworks. These frameworks support the development of system infrastructures such as communications, user interfaces and compilers.
• Middleware integration frameworks. These consist of a set of standards and associated object classes that support component communication and information exchange.
• Enterprise application frameworks. These are concerned with specific application domains such as telecommunications or financial systems.

A commercial-off-the-shelf product is a software system that can be used without change by its buyer. COTS product reuse is concerned with the reuse of large-scale systems. These provide a lot of functionality, and their reuse can radically reduce costs and development time. Potential problem with COTS-based reuse include lack of control over functionality and performance, lack of control over system evolution, the need for support from external vendors and difficulties in ensuring that systems can interoperate.

One of the most effective approaches to reuse is creating software product lines or application families. A product line is a set of applications with a common application-specific architecture. Various types of specialization of a software product line may be developed:

1.      Platform specialization.

2.      Environment specialization

3.      Functional specialization

4.      Process specialization

My thoughts:

While working on our project we touched only one aspect of software reuse – program generators. Rose Real Time is a good example of program generator.

When we just started I was thinking about Rose RT as a weird way to develop a system, it was hard to understand how learning a new environment and using it may be useful or may lead to faster development, but today I see all advantages of this approach. We don’t have to think about building a server, about network routines, about designing a system in a good way with straight C and Java, we don’t even have to think about choosing the way of connecting java and c code.

So now I think of software reuse as actually useful thing that helps us reduce the development time.

Chapter 19

Reuse-based software engineering is becoming the main development approach for business and commercial systems. Component-based software engineering (CBSE) emerged in the late 1990s as a reuse-based approach to software systems development. Single object classes were too detailed and specific, and often had to be bound with an application at compile-time. CBSE is the process of defining, implementing and integrating or composing loosely coupled independent components into systems. The essentials of component-based software engineering are:

1. Independent components that are completely specified by their interfaces. There should be a clear separation between the component interface and its implementation so that one implementation of a component can be replaced by another without changing the system.
2. Component standards that facilitate the integration of components. These standards are embodied in a component model and define, at very minimum, how component interfaces should be specific and how components communicate.
3. Middleware that provides software support for component integration. Middleware such as CORBA handles low-level issues efficiently and allows developers to focus on application-related problems.
4. A development process that is geared to component-based software engineering.

As always, some problems with using this approach remain:

1. Component trustworthiness. Components are black-box program units, and the source code of the component may not be available to component users.
2. Component certification. This issue is closely related to trustworthiness, it is the issue of certification.
3. Emergent property prediction. Because components are opaque, predicting their emergent properties is particularly difficult.
4. Requirements trade-offs. Developers usually have to make trade-offs between ideal requirements and available components in the system specification and design process.

A component model defines a set of standards for components, including interface standards, usage standards and deployment standards. The implementation of the component model provides a set of horizontal services that may be used by all components.

Component composition is the process of writing components together to create a system.

Наши роботы искали похожие записи, но не нашли :(

Логично подумать, что если один процессор выполняет работу на n секунд, то четыре процессора потратят n/4 секунд. Понятие “фактор ускорения” (“speedup factor”) это отношение времени, которое тратит на выполнение работы один процессор к времени, которое тратит на эту же работу многопроцессорная система.

S (p) = T_s / T_p

Для расчета важно использовать самый оптимальный T_s, то есть лучший из возможных не-параллельных алгоритмов.
Теперь плохие новости: у этого ускорения есть лимит. Называется он Amdahl’s Law (Закон Амдала) и вот его суть: так выглядит какая-либо задача на обычной однопроцессорной системе:

Все время выполнения — знакомое уже нам T_s, состоит из той части, которую можно распределить на несколько процессоров (распараллелить) — (1-f) T_s, и той части, что распараллелить нельзя (серийная) — fT_s.

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

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

Фактор ускорения расчитывается по формуле:

То есть все зависит от того, какой кусок программы мы сможем распараллелить (f в процентах означает количество серийного кода). Если f=0%, то есть абсолютно весь код распараллелен (чего практически не может быть), то чем больше процессоров мы задействуем, тем быстрее будет выполнена задача, и соотношение будет линейное: хотим в 10 раз быстрее — используем десять процессоров, хотим в миллион раз быстрее — закупаем миллион процессоров. Но вот стоит оставить 5% серийного кода, а 95% распараллелить, то фактор ускорения будет равен 20 и выше никак не прыгнуть. Даже если закупим к тому миллиону еще миллион процессоров, то программа все равно будет выполняться в 20 раз быстрее. Вот как этот грустный факт выглядит на графике с примерами разных процентов f:

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

Чтобы написать хороший параллельный алгоритм, нужно вникнуть в суть проблемы и подумать, как его можно разделить на отдельные независимые (в идеале) части, чтобы все они выполнялись параллельно на разных процессорах. Посмотрим на примере довольно ёмкой задачи умножения матрицы А на вектор b. Результат будет записан в вектор y, который по размеру идентичен вектору b. Чтобы получить первое значение вектора y, нужно умножить первую строку матрицы на вектор b, чтобы получить второе значение y — вторую строку на b, и так далее. Получается, каждый элемент вектора y можно считать независимо от других, то есть параллельно.

Размер каждой такой задачи один и тот же — все строки A имеют одинаковый размер (пока не касаемся таких деталей, как плотность матрицы — возможно, в ней много нулей, но предположим, что это не сильно влияет на время выполнения). Нет никаких зависимостей между задачами, и все задачи используют один и тот же b.

Вот другой пример — запрос в базу данных:

MODEL = “CIVIC” AND YEAR=2001 AND (COLOR=”GREEN” OR COLOR=”WHITE”);

Запрос пытается получить все зеленые или белые Цивики 2001 года из такой базы:

Такую задачу можно разложить на три части: один процессор будет формировать таблицу все Цивиков 2001 года, другой процессор будет формировать таблицу всех белых и зеленых машин (эти два запроса могут идти параллельно), после чего результат join’а этих двух таблиц и будет ответом.

Можно изменить структуру запроса, что может повлиять на параллелизацию

Разделение задачи на части для последующего распределения этих частей на разные процессоры называется декомпозицией. Умножение матрицы на вектор это пример декомпозиции результата задачи: результат (вектор y) был разделен на несколько независимых частей и каждая расчитывалась отдельно от другой. То же самое можно сделать и с перемножением матриц:

Наша первая параллельная программа

Для написания нашей первой параллельной программы мы будем использовать Cilk. Это язык программирования, который по сути является С с удобными инструментами для параллелизации и синхронизации задач. Cilk был разработан в MIT в 1994 году, был бесплатным и свободным, но к 2006 году стал коммерциализироваться, стал поддерживать С++, а год назад был куплен с потрохами компанией Intel, которой, конечно же, выгодно иметь хороший язык программирования для многоядерных систем: они ведь саим такие системы и производят. Я не уверен, как можно получить компилятор бесплатно, в нашем университете есть академическая версия для студентов (разработчик Cilk хороший друг профессора), поэтому прошу меня извинить, если вы не сможете найти его. Но поискать, я считаю, стоит, потому что Cilk жутко прост и удобен! Не сравнить с Pthreads. Все, что нам нужно знать, чтобы начать программировать, это три ключевых слова: cilk,spawn и sync.

Лучше всего начать с примера, поэтому вот вам любимая всеми рекурсивная задача — числа Фибоначи — на Си:

int fib (int n){
if (n<2) return n;
	else {
		int x, y;
		x = fib (n-1);
		y = fib (n-2);
		return (x+y);
}
}

А вот та же программа на Cilk:

cilk int fib (int n){
if (n<2) return n;
	else {
		int x, y;
		x = spawn fib (n-1);
		y = spawn fib (n-2);
		sync;
		return (x+y);
}
}

Заметили разницу? ,)
Ключевое слово cilk используется для указания функции. Самыми главными являются слова spawn и sync. Spawn ставится перед вызовом функции, которую мы хотим запустить на другом ядре, а sync ждет окончания выполнения всех вызванных ранее spawn’ами функций. То есть строчка

x=spawn fib (n-1);

запускается на другом ядре, и сразу выполняется строчка y=spawn fib (n-2). Перед тем, как вернуть результат (return (x+y)) нужно дождаться окончания выполнения, иначе в переменных x и y не будет правильных значений. Это делает команда sync — как и понятно из названия.

Правда, легко?

Такая программа хоршенько загрузит множество ядер! Вот как выглядит схема работы этого алгоритма для n=4:

Цвета подсветки кода соответствуют цветам узлов графа. Каждый уровень графа выполняется одновременно, то есть первый вызов для n=4 вызывает две функции — для 3 и 2, они в свою очередь — для 2 и 1 и для 1 и 0 соответственно.

Вот исходный код этой программы:

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

Наши роботы искали похожие записи, но не нашли :(