Архитектура вычислительных систем Константин Ловецкий Декабрь 2012 Кафедра систем телекоммуникаций 1 Интернет.рф: история Рунета от модемов до кириллицы Лекция подготовлена с использованием материалов сайта Евгений Бабушкин

Тихий шорох dial-up-модема, синие ссылки на черном фоне, скорость 16 кб/c. Так было совсем недавно. И вот кириллические домены, миллионы сайтов и интернет из воздуха. Стремительность развития интернета впечатляет. «Сноб» подготовил цифры и факты перед вами краткая история Рунета от основания и до наших дней dial-up модемы

3 В Москве при институте имени Курчатова образован кооператив «Интерфейс». Его сотрудники первыми в СССР попытались соединить компьютеры при помощи модемов. 1989

Родился 26 ноября 1960 года в Москве. Учился в знаменитой школе 7. Закончил факультет ВМиК в 1983 году, кафедру алгоритмических языков. В 1986 году закончил аспирантуру, защитил диссертацию, тема: "Объектно- ориентированные операционные система", руководитель Брябрин. До 1988 года работал в Вычислительном центре Академии Наук АН СССР. В 1987 году - кооператив "Техника" (созданный Артемом Тарасовым) С 1989 по 1997 года компания " ParaGraph " (соучредитель и руководитель направления, затем московского офиса.) С ноября 1997 по май 1998 года создание и работа в своей собственной фирме " CapitalSoft ". До августа 1998 года компания IBS (руководитель проекта по созданию интернет- портала, директор по технологиям ) ThinkWave Parallel Graphics, Вице-президент по технологиям и внедрениям С ParaScript Первым в 1982 году заставил заокеанские компьютеры понимать кириллицу. Написал первый антивирус. Последние 15 лет занимается оффшорным программированием, в основном новыми технологиями и продуктами. Работал с технологиями, которые еще недавно казались фантастикой - распознавание рукописного текста и 3-мерная виртуальная документация для самолетов (Боинг) и космоса. Чижов Антон

Первым в 1982 году заставил заокеанские компьютеры понимать кириллицу. Написал первый антивирус. Последние 15 лет занимается оффшорным программированием, в основном новыми технологиями и продуктами. Работал с технологиями, которые еще недавно казались фантастикой - распознавание рукописного текста и 3-мерная виртуальная документация для самолетов (Боинг) и космоса. Чижов Антон

(род. 2 февраля [1] 1935 года в Москве) советский и российский учёный, физик-теоретик,академик и член Президиума Российской академии наук, доктор физико-математических наук, Герой Социалистического Труда (1985). Президент Национального исследовательского центра «Курчатовский институт» [2]. Председатель СоветаИТЭР.2 февраля [1]1935 годаМосквероссийскийакадемикРоссийской академии наукдоктор физико-математических наукГерой Социалистического Труда1985Курчатовский институт [2]ИТЭР Евге́ний Па́влович Ве́лихов ITER (ИТЭР) проект международного экспериментального термоядерного реакторатермоядерного реактора

Очевидным способом избежания ситуации гонок является такое построение работы, при котором процессы, работающие с разделяемыми данными, не могут работать одновременно: например, пока работает один процесс, обращающийся к базе данных, другой процесс, которому также нужна эта база данных, блокируется при запуске до тех пор, пока первый не завершится. Такое решение представляется неудачным, поскольку внесение изменений в базу данных может быть не единственной задачей процесса. Вполне возможно, что процесс бОльшую часть времени занимается работой, никак с разделяемыми данными не связанной, причем время жизни процесса может оказаться слишком большим, чтобы на все это время запрещать доступ к данным кому бы то ни было еще. Например, вполне можно представить себе постоянно работающий сервер, с помощью которого клиенты банка могут узнавать остатки на своих счетах. Непосредственно он достаточно редко обращается к базе данных, но при этом работать может месяцами без перерыва. Ясно, что блокировать на все это время доступ к базе данных других процессов нельзя, ведь это парализовало бы работу банка %D0%BD%D0%B5%D1%82

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

Такая организация работы процессов, при которой два (и более) процесса не могут одновременно находиться в критических секциях по одним и тем же данным, называется взаимным исключением (англ. mutual exception). Следует отметить, что взаимные исключения могут породить дополнительные проблемы, так что при выборе метода их реализации следует соблюдать осторожность. Сформулируем требования, налагаемые на механизм взаимного исключения: Взаимоисключения. Критические секции

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

1.Блокировочная переменная Пусть имеются некоторые данные, доступ к которым осуществляют несколько процессов. Заведем в разделяемой памяти целочисленную переменную (будем называть ее s) и примем соглашение, что значение переменной 1 означает, что с разделяемыми данными никто не работает, а значение 0 – что один из процессов в настоящее время работает с разделяемыми данными и необходимо подождать, пока он не закончит работу. При запуске системы присвоим переменной s значение 1. Доступ к данным будем осуществлять следующим образом: while(s == 0) {} /* пустой цикл, пока нельзя входить в критическую секцию */ s = 0; /* запретили доступ другим процессам */ section(); /*... работа с разделяемыми данными... */ s = 1; /* разрешили доступ */ Устаревшие подходы к организации взаимного исключения

2. Запрет внешних прерываний Логично приходит в голову идея о запрете внешних (аппаратных) прерываний на время выполнения критической секции. К сожалению, этот вариант неприемлем по целому ряду причин. Рассмотрим эти причины. Во-первых, запрет прерываний годится лишь для кратковременных критических секций: длительное запрещение прерываний нарушит работу аппаратуры (например, перестанут приниматься и передаваться данные по сети). Во-вторых, запрет прерываний пригоден только для работы с данными, находящимися в оперативной памяти, поскольку для любого обмена с внешними устройствами (в том числе для чтения и записи файлов) аппарат прерываний должен работать. В-третьих, запрет прерываний обычно касается только одного процессора. В системе с несколькими процессорами это эффекта не даст Устаревшие подходы к организации взаимного исключения

Чередование Следующий способ взаимоисключения заключается в том, что процессы по очереди передают друг другу право работы с разделяемыми данными на манер эстафетной палочки Устаревшие подходы к организации взаимного исключения for(;;) { while(turn != 0) {} section(); turn = 1; noncritical_job(); } for(;;) { while(turn != 1) {} section(); turn = 0; noncritical_job(); } Здесь показаны два процесса, осуществляющие доступ к разделяемым данным (функция section()) в соответствии с маркером чередования, хранящимся в переменной turn. Значение 0 означает, что право на доступ к разделяемым данным имеет первый процесс, значение 1 соответствует праву второго процесса. Завершив работу в критической секции, процесс передает «ход» другому процессу и приступает к выполнению действий, не требующих доступа к разделяемым данным (функция noncritical_job()).

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

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

Блокировать процесс может только операционная система. Если бы процессу было точно известно, через какой промежуток времени нужный ему ресурс окажется освобожден, он мог бы выполнить системный вызов, подобный функции sleep(), чтобы отказаться от выполнения на заданный период. Однако момент освобождения нужного ресурса процессу не известен, т.к. зависит от функционирования других процессов. Получается, что управление пометками занятости/освобождения ресурсов следует возложить на операционную систему, создав еще один способ взаимодействия процессов. Следует отметить, что такой подход, кроме избавления от активного ожидания, имеет и другое важное преимущество. Операционная система, в отличие от процесса, имеет возможность при необходимости запрещать прерывания на время исполнения определенных действий внутри ядра, обеспечивая, таким образом, атомарность сколь угодно сложных операций Мьютексы и семафоры

Под мьютексом в общем случае понимается объект, имеющий два состояния (открыт/заперт) и, соответственно, две операции: lock() (запереть) и unlock() (открыть). Операция unlock() проходит успешно (и немедленно возвращает управление) в любом случае, переводя объект в состояние «открыт». Для операции lock() может быть два варианта: 1. Операция может быть реализована как булевская функция. При применении ее к открытому мьютексу она закрывает его и возвращает значение «истина» (успех). При применении к закрытому мьютексу функция возвращает значение «ложь» (неудача). Такой вариант реализации называется неблокирующим. 2. Операцию можно реализовать и как процедуру, не возвращающую никакого значения. В этом случае при применении ее к открытому мьютексу она закрывает его и возвращает управление; при применении ее к закрытому мьютексу она блокирует вызвавший процесс до тех пор, пока мьютекс не окажется открыт, после чего закрывает его и возвращает управление Мьютексы

Важнейшим свойством операций lock() и unlock() является их атомарность. Это означает, что обе операции выполняются как единое целое и не могут быть прерваны. В частности, операция lock() не может быть прервана между проверкой текущего значения мьютекса и изменением этого значения на «закрыто». Рассмотрим для начала неблокирующую реализацию lock(): while(!lock(s)) {} /* ждем, пока не удастся закрыть мьютекс */ section(); /*... работа с разделяемыми данными... */ unlock(s); /* разрешаем другим процессам доступ */ В отличие от варианта с использованием блокирующей переменной, данный вариант является корректным. Поскольку операция lock() атомарна, выход из цикла (по истинному значению функции lock()) означает, что в некий момент мьютекс оказался открыт (то есть никто в это время не работал с разделяемыми данными), и нашему процессу удалось его закрыть, причем никто другой вклиниться между проверкой и закрытием не мог. Мьютексы и семафоры

Если применить второй тип реализации операции lock() (при котором она блокируется до тех пор, пока не удастся закрыть открытый мьютекс), наш код станет еще проще, и из него исчезнет цикл активного ожидания: lock(s); /* ждем, пока не удастся закрыть мьютекс */ section(); /*... работа с разделяемыми данными... */ unlock(s); /* разрешаем другим процессам доступ */ Ясно, что такой мьютекс может быть реализован только при содействии ядра операционной системы: либо целиком как объект ядра, либо как набор операций, осуществляемых ядром над переменной, расположенной в пользовательском процессе. Отметим с другой стороны, что введение такого сравнительно простого сервиса в ядре ОС позволяет избавиться разом от всех недостатков рассмотренных выше подходов к взаимному исключению Мьютексы и семафоры

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

Как и в случае с мьютексом, операции над семафором обязательно должны быть реализованы атомарно: необходимо полностью исключить ситуации, когда результат нескольких независимых операций над семафором может зависеть от времени вызова операций процессами (как это происходило в примере, приведенном в начале лекции). Семафор, как и мьютекс, может быть реализован целиком как объект ядра, либо как набор операций ядра над переменной из памяти пользовательского процесса. Ясно, что с помощью семафора можно имитировать функционирование мьютекса, если считать значение 0 состоянием «закрыт», значение 1 состоянием «открыт», а операции lock() и unlock() заменить на down() и up(). Необходимо только следить, чтобы операция up() никогда не применялась к положительному семафору, а этого можно достичь, если применять операцию up() только в начале программы (один раз), а также после того, как прошла операция down(), и никогда иначе. Однако семафор можно использовать в более сложной роли, а именно, как счетчик доступных ресурсов Мьютексы и семафоры

Мьютексы и семафоры