Задачи синхронизации

Основные понятия

Объектами распараллеливания являются неделимые процессы — работы, на которые разбивается исходный алгоритм или разрабатываемая программная система.

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

Ресурсы, используемые несколькими процессами, называются разделяемыми.

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

Участки программы (процесса), где процессы обращаются к разделяемому ресурсу, называются критическими интервалами (блоками, секциями).

Процессы называются взаимосвязанными, если они используют общие критические ресурсы.

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

Например, процессу A необходимы внешние устройства X, Y. С устройством Y пока работает процесс B. Тогда процесс A "захватывает" пока устройство X и ждет освобождения Y. Но устройство X потребовалось и процессу B, который также "зависает" в ожидании его освобождения.

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

Выше был приведен пример:

"Закрыть адрес по считыванию" a

"Считать по адресу" а

Здесь возможен локальный тупик — бесконечное выполнение команды (2), если другой процесс (на другом процессоре) или ОС не "откроет" адрес а.

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

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

Требования к решению этой задачи:

· задержка любого процесса вне его критического интервала не должна влиять на развитие других процессов;

· решение должно быть симметрично относительно процессов;

· решение не должно допускать тупиков.

Решение с помощью механизма семафоров:

2. Задача "поставщики — потребители". Имеется ограниченный буфер на несколько порций информации. Он является критическим ресурсом для процессов двух типов:

· процессы "поставщики", получая доступ к ресурсу, помещают на свободное место в буфере несколько или одну порцию информации;

· процессы "потребители", получая доступ к ресурсу, считывают из него порции информации.

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

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

Возможная схема решения задачи с помощью семафоров:

3. Задача "читатели — писатели".

Имеется разделяемый ресурс — область памяти, к которой требуется доступ процессам двух типов:

Процессы первого типа — "ЧИТАТЕЛИ" — могут получать доступ к разделяемому ресурсу одновременно. Они считывают информацию.

Процессы второго типа — "ПИСАТЕЛИ" — взаимно исключают и друг друга, и "читателей". Они записывают в разделяемую область памяти данные.

Задача известна в двух вариантах:

1. "Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее; это — первая задача ЧП.

2. "Читатели", изъявившие желание получить доступ к ресурсу, должны получить его как можно быстрее, если отсутствуют запросы от "писателей". "Писатель", требующий доступ к ресурсу, должен получить его как можно быстрее, но после обслуживания "читателей", подошедших к ресурсу до первого "писателя". Это — вторая задача ЧП.

Приведем возможное решение задач с помощью комбинированного семафора.

Считаем, что процедура ОТКРЫТЬ ПО СЧИТЫВАНИЮ выполняется подобно процедуре ПРОПУСТИТЬ, изменяя только значение семафора-счетчика. Процедура ОТКРЫТЬ ПО ЗАПИСИ выполняется подобно процедуре ОТКРЫТЬ, "открывая" семафор и обеспечивая запуск "задержанных" процессов с процедур ЗАКРЫТЬ ПО ЗАПИСИ или ЖДАТЬ ПО ЗАПИСИ, при выполнении которых произошло прерывание.

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

4. Задача "обедающие философы". За круглым столом сидят k философов, которые проводят время, чередуя философские размышления с потреблением пищи. Перед каждым — тарелка спагетти, между тарелками — по одной вилке. Для еды каждому философу требуются две вилки. Использовать можно только вилки, лежащие рядом с тарелками. Так как переходы от размышления к принятию пищи производятся в непредсказуемые моменты времени, то возможны конфликты и требуется синхронизация процессов.

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

Рис. 1. Связь по схеме "обедающие философы"

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

Пусть с i-м процессором для передачи влево связан "левый" семафор C_i, для передачи вправо — "правый" семафор C_i+1 (или наоборот). Пусть каждый процессор, нуждающийся в передаче двум соседям, пытается сначала закрыть свой "правый" (аналогично, "левый") семафор. Затем, если это не успел сделать левый сосед, он попытается закрыть "левый" семафор и произвести передачу. Тогда возможен общий тупик, если все процессоры одновременно закроют все семафоры. (При одновременном пересчете значений функции в узлах сетки вероятность такой ситуации высока.)

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

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

Вместо признака может быть использован семафор. Ожидание может быть организовано процедурами ЖДАТЬ или ЖУЖ.

Системные часы и таймеры

Часами называется программный или аппаратный объект, предназначенный для измерения видимого или истинного хода времени.

Показания часов можно опросить и установить (в допустимых для часов пределах).

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

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

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

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

Реальным (или астрономическим) называется время, измеренное по системным часам безотносительно к тому, какой процесс (поток управления) выполняется.

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

Время выполнения конкретного процесса или потока управления измеряется часами процессорного времени.

Под мониторингом времени выполнения понимается оперативное отслеживание процессорного времени, затрачиваемого процессом (потоком управления).

Виртуальное время процесса - время, измеряемое системными часами, пока процесс выполняется.

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

Таймером процессорного времени называется таймер, ассоциированный с часами процессорного времени.

Взвести (зарядить) - значит запустить таймер, измеряющий ход времени и позволяющий уведомить процесс о наступлении заданного момента.

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

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

Одноразовые таймеры снимаются со взвода после первого (и единственного) срабатывания.

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

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

Операционные системы

Назначение и функции ОС

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

Основные функции, которые выполняют ОС:

· прием от пользователя заданий или команд и их обработка;

· прием и исполнение программных запросов на запуск, приостановку и остановку других программ;

· загрузка в оперативную память подлежащих исполнению программ;

· инициация программы (передача ей управления, в результате чего процессор исполняет программу);

· обеспечение работы систем управления файлами (СУФ) и СУБД;

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

· обеспечение функций по организации и управлению всеми операциями ввода\вывода;

· распределение памяти и организация виртуальной памяти;

· планирование о диспетчеризации задач;

· организация механизмов обмена сообщениями и данными между выполняющимися программами;

· обеспечение сохранности данных;

· обеспечение работы систем программирования.

Обзор операционных систем

MS DOS 6

Системные требования: очень маленькие.

Одна из первых "массовых" ОС, широко распространенная во времена компьютеров на процессорах 286-486. Управление осуществлялось набором команд с клавиатуры, что было крайне медленно и неудобно. Эта ситуация привела к возникновению оболочек-консолей, самой популярной из которых оказался Norton Commander. На сегодняшний день операционная система DOS является устаревшей и практически не используется. Ее можно встретить на совсем древних машинах, которые владельцы не спешат выбрасывать в мусор.

Windows 3 (1990 год)

Системные требования: 386-25, 4 Мb RAM

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

Windows 95 (1995 год)

Минимальные системные требования: 486DX-25, 8Mb RAM
Рекомендуемые системные требования: Pentium-100, 32Mb RAM

Появление новых окон произвело фурор в компьютерном мире. Это уже не очередная надстройка над DOS, а самостоятельная ОС. Был в корне переработан интерфейс, улучшилась многозадачность, дистрибутив пополнился служебными программами и дополнительными утилитами. Также система могла похвастаться большим количеством встроенных драйверов для многих устройств, что делало процесс инсталляции гораздо проще. Через год Microsoft выпустила версию OSR2 (OEM Service Release), которая поддерживала новую файловую систему FAT32, что позволяло работать с жесткими дисками большого объема. Появился встроенный интернет-браузер и приложение DirectX для работы с трехмерной графикой и медиа-потоками.

Стабильность работы и защищенность в Windows 95 оставляло желать лучшего. Рекомендуется периодически переустанавливать ОС, особенно если часто инсталлировать разного рода программы. В нынешнее время Windows 95 считается устаревшей, хотя для машин класса Пентиум-100, которые еще живут в домах и даже организациях, это наиболее подходящая операционная система.

Windows NT 4 (1995 год)

Минимальные системные требования: Pentium-66, 16Mb RAM
Рекомендуемые системные требования: Pentium-166, 64Mb RAM

Windows NT представляет собой совершенно иную систему, предназначенную для серьезной работы и больших сетей. Например, большинство пакетов для трехмерного моделирования и анимации работали только под NT. Несмотря на внешнее сходство с Windows 95, эта ОС имеет другое ядро и использует иные механизмы работы. Она отличается большой устойчивостью, безопасностью и стабильностью, однако у этого есть обратная сторона. Драйвера устройств должны быть специально написаны под Windows NT, операционка использует собственную файловую систему NTFS, которую не понимают Windows 95-98. Конфигурировать NT гораздо сложнее, это должен делать квалифицированный пользователь. Система предназначена для серьезной работы, так что про всякие игрушки лучше забыть. Windows NT 4 существует в двух вариантах: Workstation и Server. Первый предназначен для персональных рабочих мест, а второй должен работать в качестве сервера.

Благодаря своей надежности и относительно низким системным требованиям Windows NT 4 стала очень популярной. Однако эта система тоже не идеальна, и Microsoft регулярно выпускала пакеты обновлений, называемые сервис-паками. Необходимым минимумом стал сервис-пак 4. Если он не установлен, то некоторые программы просто откажутся запускаться.

Сейчас Windows NT 4 считается устаревшей системой, хотя многие пользователи не спешат устанавливать себе нечто новое.

Windows 98 (1998 год)

Минимальные системные требования: Pentium-66, 24Mb RAM
Рекомендуемые системные требования: Pentium-150, 64Mb RAM

Ядро и основные механизмы остались прежними. Появилась поддержка новых на тот день интерфейсов и протоколов, пополнилась коллекция драйверов. Наиболее очевидное новшество - интеграция с Интернет. Рабочий стол можно сделать настоящей веб-страницой. Обновленный Internet Explorer стал довольно простым и в тоже время функциональным, что сделало его лидером на рынке браузеров.

Повторилась история со вторым релизом - через некоторое время появилась Windows 98 SE, что значит Second Edition (вторая редакция). Предпочтительнее использовать именно ее, по причине меньшего количества ошибок и большей устойчивости. Также рекомендуется периодически удалять Windows 98 и устанавливать заново для большей стабильности работы.

На сегодня эта операционная система хоть и является морально устаревшей, но еще широко распространена.

Windows Me (2000 год)

Минимальные системные требования: Pentium-150, 32Mb RAM
Рекомендуемые системные требования: Pentium-300, 64Mb RAM

По сути дела мы имеем очередное обновление системы на ядре Windows 95-98. Много косметических изменений, обновлен и расширен набор драйверов. Из полезностей появилась система восстановления операционки, которая периодически запоминает состояния регистра и дает возможность возврата. Этим разработчики попытались скомпенсировать общую неустойчивость ядра Windows 95-98-Ме. Вместе с тем они стали потихоньку избавляться от тормозящего наследия DOS.

Итог: самая последняя ОС линейки Windows 95-98. Дальнейшее развитие этого направления разработчики посчитали неперспективным.

Windows 2000 Professional

Минимальные системные требования: Pentium-133, 64Mb RAM
Рекомендуемые системные требования: Pentium II-300, 128Mb RAM

Структура управления мало чем отличается от Windows NT 4. Система действительно работает гораздо стабильнее, чем Windows 95-98-Ме, однако конфигурировать ее сложнее. Операционка теперь понимает файловые системы FAT32 и NTFS. При инсталляции пользователь должен выбрать нужную.
Еще можно отметить новый режим "засыпания" компьютера. Можно нажать на кнопочку "заснуть", содержимое оперативной памяти запишется на винчестер, затем компьютер выключится. Когда вы включите питание, неважно, когда это произойдет, через час, день или месяц, то все будет абсолютно в таком состоянии, как перед "засыпанием".

Подводя итог, можно сказать, что Windows 2000 стала продолжением линейки NT, недаром в названии употребляется слово Professional. Ее можно использовать как для серьезной работы, так и для развлечений, благо с играми все обстоит хорошо.

Windows XP (2001 год)

Минимальные системные требования: Pentium II-233, 64Mb RAM
Рекомендуемые системные требования: Pentium III-500, 128Mb RAM

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

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

Улучшено время загрузки, примерно столько же, сколько нужно Windows 98. Это достижение, потому что Windows 2000 грузится гораздо дольше.
Существует три версии системы - Professional, Home и 64-Bit Edition. Как ясно из названий, Professional предназначена для профессионального использования, Home - для дома, а 64-Bit Edition должна устанавливаться на компьютеры с процессором Intel Itanium для узкоспециализированных областей применения.

Имеется функция отката драйверов. То есть при установке нового система не удаляет старый, а хранит его на всякий случай.

На сегодняшний день ХР является самой свежей операционкой от Microsoft. Это действительно стабильная и красиво выглядящая система, которую не стыдно и не страшно установить на свой компьютер и спокойно работать-играть, не боясь внезапного обвала. Хотя она тоже не идеальна, в свет вышел первый пакет исправлений.

Linux

Вообще-то операционных систем много. И делает их не только Microsoft. Просто в определенный момент времени эта фирма сумела хорошо раскрутить свою продукцию и теперь держит весь мир в кулаке монополии.

Несмотря на владычество Microsoft, некоторая альтернатива на рынке операционных систем все-таки имеется. Это Linux, второе по распространенности семейство операционок после Windows.

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

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

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

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

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

Red Hat Linux

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

Mandrake Linux

Считается самым завершенным дистрибутивом Linux на нынешний момент. Он снабжен большим количеством встроенных приложений и утилит. А так же может похвастаться отличной русификацией.

ASP Linux

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

Slackware Linux

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

S.u.S.E. Linux

Знаменит тем, что в его пользу правительство Германии даже отказалось от продукции Microsoft. По большому счету является потомком Slackware, хотя имеет своеобразные отличия. Очень большое внимание уделено вопросу безопасности. Специфичный дистрибутив, рекомендуется для опытных пользователей.

Архитектура операционной системы

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

Дата добавления: 2014-01-07