История операционных систем

История операционных систем

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

Онтогенез повторяет филогенез

После опубликования книги Чарльза Дарвина «Происхождение видов» немецкий зоолог Эрнст Хэккель (Ernst Haeckel) сформулировал правило: «Онтогенез… Нечто подобное произошло в компьютерной промышленности. Каждый новый вид… А теперь взглянем на операционные системы. Первые мэйнфреймы изначально не имели защитного оборудования и поддержки…

Основные функции операционных систем

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

Классификация ОС

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

□ General Purpose Operating Systems (ОС общего назначения)

□ Real -Time Systems (ОС реального времени)

□ Hybrid or/and "in-between" systems (Системы промежуточных типов)

ДОС (Дисковые Операционные Системы)

Характерный пример — различные загрузочные мониторы для машин клас­са Spectrum. Как правило, такие системы работают одновременно только с одной… Дисковая операционная система MS DOS для IBM PC-совместимых машин является… Существование систем этого класса обусловлено их простотой и тем, что они потребляют мало ресурсов. Для машин класса…

ОС общего назначения

Здесь под ОС мы будем подразумевать системы "общего назначения", т. е. рассчитанные на интерактивную работу одного или нескольких…

Системы виртуальных машин

Виртуальные машины являются ценным средством при разработке и тести­ровании кросс-платформенных приложений. Реже они используются для отладки… Такие системы отличаются высокими накладными расходами и сравнитель­но низкой… Часто СВМ являются подсистемой ОС общего назначения: MS DOS и MS Windows-эмуляторы для UNIX и OS/2, подсистема WoW в…

Системы реального времени

Способность гарантировать время реакции является отличительным призна­ком систем РВ. Важно учитывать различие между гарантированностью и просто… По другим признакам эти системы могут относиться как к классу ДОС (RT-11), так… Любопытно, что новомодное течение в компьютерной технике — multimedia — при качественной реализации предъявляет к…

Средства кросс-разработки

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

Системы промежуточных типов

Некоторые системы реального времени, например QNX, могут использо­ваться как в качестве самостоятельной ОС, загружаемой с жесткого диска в… Таких примеров "гибридизации" можно привести множество, поэтому к…

Семейства операционных систем

На основании такой преемственности можно выстроить "генеалогические деревья" операционных систем и — с той или иной обоснованностью —… Тем не менее, мы с достаточно большой уверенностью можем выделить ми­нимум три… □ Системы для больших компьютеров фирмы IBM — OS/390, z/OS и IBM VM.

Выбор операционной системы

Наконец, некоторые задачи, такие как автоматизация конторской работы в небольших организациях, не предъявляют высоких требований к на­дежности,… Нужно отметить, впрочем, что современные версии Windows, несмотря на низкую…

Проблема

Основная проблема MS Windows состоит вовсе не в том, что это не "насто­ящая" операционная система — "велосипед", в терминах…

Открытые системы

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

Представление данных в вычислительных системах

В силу аппаратных ограничений процессор оперирует числами фиксирован­ной разрядности. Количество двоичных разрядов основного арифметико-логического… В прошлом встречались и процессоры, разрядность которых не являлась степенью…

Введение в двоичную арифметику

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

Из табл. 1.1 видно, что результат сложения двух одноразрядных чисел явля­ется двухразрядным (двузначным) числом, а результат сложения двух N-разрядных — N+1 -разрядным. Образующийся дополнительный бит называ­ется бытом переноса (carry bit).

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

Представление текстовых данных

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

Представление изображений

В векторном формате изображение разделяется на примитивы — прямые линии, многоугольники, окружности и сегменты окружностей, параметри­ческие кривые,…   Каждый примитив описывается своими геометрическими координатами. Точность описания в разных форматах различна, нередко…

Представление звуков

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

Упаковка данных

Научной основой всех методов упаковки является теория информации: дан­ные, в которых имеются статистические автокорреляции, называются избы­точными… Один из первых методов упаковки был предложен задолго до разработки… В конце сороковых годов XX века основателем современной теории инфор­мации Шенноном, и независимо от него, Фано был…

Сигнал при этом, конечно, искажается, но сильнее всего при этом страдает равномерно распределенный по спектру шум, что и требуется (рис. 1.8).

Алгоритмы JFIF (лежащий в основе распространенного формата хранения растровых изображений JPG), MPEG, MP3 тоже начинаются с выполнения над входным потоком преобразования Фурье. Но, в отличие от шумодава, JFIF удаляет из полученного спектра не частоты, которые ни­же заданного порога, а фиксированное количество частот — конечно же, стараясь отобрать самые слабые. Количество частот, которые надо выки­нуть, определяется параметром настройки упаковщика. У JFIF этот пара­метр так и называется — коэффициентом упаковки, у МРЗ — битрейтом.

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

При разумно выбранном уровне упаковки результат — фотореалистичное изображение или музыкальное произведение — на взгляд (или, соответст­венно, на слух) практически неотличим от оригинала. Различие может пока­зать только спектральный анализ данных. Но если распаковать сжатое с по­терями изображение, подвергнуть его редактированию (например, отмасштабировать или пририсовать какой-нибудь логотип), а потом упако­вать снова, результат будет удручающим: редактирование привнесет в изо­бражение новые частоты, поэтому велика опасность, что повторная упаков­ка даже с более низким коэффициентом сжатия откусит какие-то из "полезных" частот изображения. После нескольких таких перепаковок от изображения остается только сюжет, а от музыки — только основной ритм. Экспериментальные варианты приблизительных алгоритмов вместо класси­ческого разложения по взвешенной сумме синусов и косинусов используют разложение по специальным функциям, так называемым вэйвлетам (wavelet). Утверждается, что вэйвлетная фильтрация при том же уровне сжа­тия (понятно, что сравнивать по уровню сжатия алгоритмы, которые сжи­мают что угодно в заданное число раз, совершенно бессмысленно) дает меньший уровень субъективно обнаружимых искажений. Но субъективное восприятие, как известно, сильно подвержено эффекту плацебо (человек склонен видеть улучшение или вообще изменение там, где его нет, если имеет основания предполагать, что изменение должно произойти) зато вэйвлетные алгоритмы сильно уступают обычным вариациям JFIF по про­изводительности, поэтому до сих пор они не вышли из экспериментального состояния.

Контрольные суммы

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

Введение в криптографию

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

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

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

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

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

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

Устойчивость шифра к поиску автокорреляций в сообщении называется криптостойкостью алгоритма. Даже при использовании удачных в этом смысле алгоритмов, если взломщик знает, что исходные (нешифрованные) данные удовлетворяют тому или иному требованию, например, содержат определенное слово или снабжены избыточным кодом, он может произве­сти полный перебор пространства ключей: перебирать все значения ключа, допускаемые алгоритмом, пока не будет получено удовлетворяющее требо­ванию сообщение. При использовании ключей достаточно большой разряд­ности такая атака оказывается чрезмерно дорогой, однако прогресс вычис­лительной техники постоянно сдвигает границу "достаточности" все дальше и дальше. Так, сеть распределенных вычислений Bovine в 1998 году взлома­ла сообщение, зашифрованное алгоритмом DES с 56-разрядным ключом за 56 часов работы [www.distributed.net]!

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

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

Низкая криптостойкость может быть обусловлена не только алгоритмом шифрования, но и процедурой выбора ключа: если ключ может принимать любые двоичные значения заданной разрядности, но реально для его выбора используется страдающий неоднородностью генератор псевдослучайных чи­сел, мы можем значительно сократить объем пространства, которое реально должен будет перебрать взломщик наших сообщений (вопросы генерации равномерно распределенных псевдослучайных чисел обсуждаются во втором томе классической книги [Кнут 2000]). Еще хуже ситуация, когда в качестве ключа используются "легко запоминаемые" слова естественного языка: в этом случае реальный объем пространства ключей даже довольно большой разрядности может измеряться всего лишь несколькими тысячами различ­ных значений.

Современные алгоритмы шифрования делятся на два основных класса: с секретным и с публичным ключом (кажущееся противоречие между тер­мином "публичный ключ" и приведенными выше рассуждениями будет разъяснено далее).

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

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

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

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

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

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

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

Например, широко применяемый блочный алгоритм DES шифрует 64-битные блоки данных 56-битным ключом. Полное описание алгоритма при­водится в документе [NBS FIPS PUB 46, 1977]. Русский перевод этого документа может быть найден в приложениях к книге [Дейтел 1987]. Для современной вычислительной техники полный перебор 56-битного про­странства — "семечки", поэтому сейчас все большее распространение полу­чают алгоритмы с большей разрядностью ключа — Blowfish, IDEAL и др. [Анин 2000].

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

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

Двухключевые схемы шифрования намного сложнее в разработке, чем схе­мы с секретным ключом: требуется найти преобразование, не поддающееся обращению при помощи применявшегося в нем публичного ключа, *но та­кое, чтобы с применением приватного ключа его все-таки можно было об­ратить. Известные криптоустойчивые схемы основаны на произведениях простых чисел большой разрядности, дискретных логарифмах и эллиптиче­ских кривых. Наиболее широкое применение получил разработанный в 1977 г. алгоритм RSA [www.rsa.com FAQ].

Известные двухключевые алгоритмы требуют соответствия ключей весьма специфическим требованиям, поэтому для достижения криптостойкости, сопоставимой с блочными алгоритмами, необходимо использовать ключи намного большей разрядности. Так, снятые в 2000 году ограничения Мини­стерства торговли США устанавливали ограничения разрядности ключа, ко­торый мог использоваться в экспортируемом за пределы США профаммном обеспечении: для схем с секретным ключом устанавливался предел, равный 48 битам, а для схем с открытым — 480.

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

Такая схема делает практичной частую смену секретных ключей: так, в про­токоле SSH ключ генерируется на каждую сессию [www.cs.hut.fi SSH]; в про­токоле виртуальных приватных сетей IPSEC время жизни ключа ограничено восемью часами [redbooks.ibm.com sg245234.pdf].

Еще более широкое применение двухключевые схемы нашли в области ау­тентификации и электронной подписи. Электронная подпись представляет собой контрольную сумму сообщения, зашифрованную приватным ключом отправителя. Каждый обладатель соответствующего публичного ключа мо­жет проверить аутентичность подписи и целостность сообщения. Это может использоваться для проверки аутентичности как сообщения, так и самого отправителя. Использование в качестве контрольной суммы обычного CRC невозможно, потому что генерация сообщения с заданным CRC не представляет вычислительной сложности. Для применения в электронной подписи были разработаны специальные алгоритмы вычисле­ния контрольных сумм, затрудняющие подбор сообщения с требуемой сум­мой [RFC 1320, RFC 1321].

 

Загрузка программ

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

Создание процессов в Unix

При этом каждый из процессов имеет свою копию всех локальных и статиче­ских переменных. На процессорах со страничным диспетчером памяти физиче­ского… Если мы хотим запустить другую программу, то мы должны исполнить систем­ный… Несколько неожиданное, но тем не менее верное описание действия exec — это замена образа процесса в рамках того же…

Абсолютная загрузка

□ Система может предоставить каждому процессу свое адресное пространство. Это возможно только на процессорах, осуществляющих трансляцию… □ Система может исполнять в каждый момент только один процесс. Так ведет…  

Формат загрузочного модуля a.out

• "магическое число" — признак того, что это именно загружаемый модуль, а не что-то другое; • число text_size —длину области кода программы (text); • data_size — длину области инициализованных данных программы (data); !

Разделы памяти

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

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

Относительная загрузка

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

Базовая адресация

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

Именно так происходит загрузка com-файлов в системе MS DOS.

Позиционно-независимый код

Относительная адресация, когда ад­рес получается сложением адресного поля команды и адреса самой этой ко­манды — значения счетчика команд. Код, в котором используется только такая адресация, можно загружать с любого адреса без всякой перенастрой­ки. Такой код называется позиционно-независимым (position-independent).

Позиционно-независимый код в современных Unix-системах

Компиляторы современных систем семейства UNIX — GNU С или стандартный С-компилятор UNIX SVR4 имеют ключ -f pic(Position-Independent Code).

Оверлеи (перекрытия)

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

Сборка программ

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

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

□Таблицу ссылок на внешние объекты. Иногда это называется таблицей или списком импорта. □Таблицу объектов, определенных в этом модуле, на которые можно… □ Различную служебную информацию, такую, как имя модуля, программу, которая его создала и отладочную…

Объектные библиотеки

Библиотека, как правило, представляет собой последовательный файл, со­стоящий из заголовка, за которым последовательно располагаются объект­ные… □ Список всех объектных модулей, со смещением каждого модуля от нача­ла… □ Список всех глобальных символов, определенных в каждом из модулей, с указанием, в каком именно мо­дуле он был…

Сборка в момент загрузки

Главное преимущество состоит в том, что, если мы загружаем несколько программ, использующих одну и ту же библиотеку, мы можем настроить их на работу… Примером такой сборки является широко используемая в Windows всех вер­сий и…

Программные модули в N9000

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

Динамические библиотеки

DLL представляют собой библиотеки в том смысле, что обычно они соби­раются из нескольких объектных модулей. Но, в отличие от архивных биб­лиотек, из… Главное достоинство DLL состоит в том, что модуль (как основной, так и… Особенно удобна возможность вызывать любую функцию по имени при обращении к внешним модулям из интерпретируемых…

Разделяемый код в системах семейства Windows

Катастрофические масштабы эта проблема принимает в системах семей­ства Windows, где принято помещать в дистрибутивы прикладных программ все потенциально разделяемые модули, которые этой программе могут по­требоваться — среда исполнения компилятора и т. д. При этом каждое приложение считает своим долгом поместить свои разделяемые модули в C:WINDOWSSYSTEM32 (в Windows NT/2000/XP это заодно приводит к тому, что установка самой безобидной утилиты требует администраторских привиле­гий). Средств же проследить за тем, кто, какую версию, чего, куда и зачем по­ложил, практически не предоставляется.

В лучшем случае установочная программа спрашивает: "Тут вот у вас что-то уже лежит, перезаписать?". Стандартный деинсталлятор содержит список DLL, которые принадлежат данному приложению, и осознает тот факт, что эти же DLL используются кем-то еще, но не предоставляет (и, по-видимому, не пыта­ется собрать) информации о том, кем именно они используются. Наличие рее­стра объектов СОМ не решает проблемы, потому что большая часть приноси­мого каждым приложением "разделяемого" кода (кавычки стоят потому, что значительная часть этого кода никому другому, кроме принесшего его прило­жения, не нужна) не является сервером СОМ.

В результате, когда, например, после установки MS Project 2000 перестает ра­ботать MS Office 2000, это никого не удивляет, а конфликты между приложениями различных разработчиков или разных "поколений" счи­таются неизбежными. Установить же в одной системе и использовать хотя бы попеременно две различные версии одного продукта просто невозможно — од­нако, когда каждая версия продукта использует собственный формат данных, а конверсия между ними неидеальна, это часто оказывается желательно. Разработчики же и тестеры, которым надо обеспечить совместимость с различными версиями существующих приложений, при этом просто оказываются в безвыходной ситуации. Неслучайно поставщики VmWare (системы виртуальных машин для х86) как одно из главных достоинств своей системы рекламируют возможность держать несколько копий Windows одновременно загруженными на одной машине.

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

Загрузка самой ОС

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

Загрузка Sun Solaris

Если загрузка происходит с жесткого диска, BIOS загружает в память и запус­кает нулевой сектор нулевой дорожки диска. Этот сектор обычно содержит не… MBR перехватывает прерывание int 13h и транслирует обращения к дисковой… Так или иначе, но загрузочный сектор — по совместительству, первичный за­грузчик Solaris оказывается в памяти и…

Управление оперативной памятью

Открытая память

В этом случае управление памятью со стороны системы состоит в том, что загрузчик проверяет, поместится ли загружаемый модуль в пространство от… Однако программа может использовать динамическое управление памятью, например… Функция malloc поддерживает некоторую структуру данных, следя­щую за тем, какие блоки памяти из уже выделенных были…

Алгоритмы динамического управления памятью

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

Сборка мусора

Некоторые системы программирования используют специальный метод ос­вобождения динамической памяти, называемый сборкой мусора (garbage collection).… Самый простой метод отличать используемые блоки от ненужных — счи­тать, что… Впрочем, при наивной реализации такого подхода возникает специфическая проблема. Если у нас есть циклический список,…

Открытая память (продолжение)

Управление памятью в OS/360 В этой связи нельзя не упомянуть о поучительной истории, связанной с… Однако после загрузки программу уже нельзя было перемещать по памяти: пример, при вызове подпрограммы адрес возврата…

Управление памятью в MS DOS

Каждой программе в MS DOS отводится блок памяти. С каждым таким блоком ассоциирован дескриптор, называемый МСВ— Memory Control Block (рис. 4.14).… После запуска corn-файл получает сегмент размером 64Кбайт, а ехе — всю… Естественно, что наращивать сегмент можно только за счет следующего за ним в цепочке МСВ, и MS DOS разрешит делать это…

Управление памятью в MacOS и Win16

"Ручки" представляют собой попытку создать программный аналог аппарат­ных диспетчеров памяти. Они позволяют решить проблему фрагментации и… Использование "ручек" сильно усложняет программирование вообще и в…  

Системы с базовой виртуальной адресацией

Вы можете заметить, что термин базовая адресация уже занят — мы называ­ли таким образом адресацию по схеме reg[offset]. Метод, о котором сейчас идет… Как правило, машины, использующие базовую адресацию, имеют два регистра. Один… При помощи этих двух регистров мы сразу решаем две важные проблемы.

Компьютер и внешние события

Примечание

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

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

Следовательно

ОПРОС

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

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

Канальные процессоры и прямой доступ к памяти

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

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

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

Для реализации этого алгоритма достаточно трех регистров (указателя в па­мяти, значения текущего слова и счетчика переданных слов). Реализующее этот алгоритм устройство называют контроллером прямого доступа к памяти (Direct Memory Access controller, DMA controller) (рис. 6.1). Такие контроллеры часто рассчитаны на одновременную работу с несколькими устройствами — имеют несколько каналов — и, соответственно, больше регистров.

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

Различают два типа реализаций ПДП:

1. Мастер шины (bus master), когда устройство имеет свой собственный контроллер ПДП,

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

Типичный современный дисковый контроллер имеет и средства ПДП и внутренний буфер. У кэширующих (имеющих кэш-память) и RAID-контроллеров объем буфера… Периферийные процессоры находят широкое применение в современных… В отличие от перечисленных устройств, классический полностью програм­мируемый канальный процессор подключен…

Прерывания

Процессор имеет один или несколько входов, называемых сигналами или линиями запроса прерывания. При появлении сигнала на одном из входов, процессор…

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

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

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

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

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

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

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

ИСКЛЮЧЕНИЯ

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

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

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

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

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

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

Многопроцессорные архитектуры

Одним из доводов является повышение надежности вычислительной системы посредством многократного резервирования. Если один из процессоров…

Примечание

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

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

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

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

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

Некоторые многопроцессорные системы поддерживают исполнение на разных процессорах различных ОС — так, на IBM z90 часть процессоров может исполнять Linux, а остальные — z/OS. В такой конфигурации, работающий под управлением Linux Web-сервер может взаимодействовать с работающие под z/OS сервером транзакций через общую физическую память. Многопроцессорные серверы Sun Fire могут исполнять несколько копий Solaris.

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

Современные суперкомпьютеры этого типа (IBM SP6000, Cray Origin) состоят из десятков, сотен, а иногда и тысяч отдельных процессорных модулей (каждый модуль представляет собой относительно самостоятельную вычислительную систему, обычно многопроцессорную, с собственной памятью и нередко, с собственной дисковой подсистемой), соединенных между собой высокоскоростными каналами. Именно к этому типу относился шахматный суперкомпьютер Deep Blue, выигравший в 1997 году матч у чемпиона мир по шахматам Гарри Каспарова.

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

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

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

Одно из основных решений, позволяющих согласовать скорости ЦПУ и ОЗУ, — это снабжение процессоров высокоскоростными кэшами команд и данных. Такие кэши нередко делают не только для центральных процессо­ров, но и для адаптеров шин внешних устройств. Это значительно уменьша­ет количество обращений к ОЗУ, однако мешает решению задачи, ради ко­торой мы и объединяли процессоры в единую систему: обмена данными между потоками, исполняющимися на разных процессорах (рис. 6.2 Некогерентный кэш).

Большинство контроллеров кэшей современных процессоров предоставляют средства обеспечения когерентности кэша — синхронизацию содержимого кэш-памятей нескольких процессоров без обязательной записи данных в основное ОЗУ.

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

Порядок доступа к памяти в SPARC

Частично упорядоченный доступ (PSO, Partial Store Order), когда процессор по-прежнему использует и кэширование, и переупорядочивание, но в потоке… Полностью упорядоченный доступ (TSO, Total Store Order), когда процессор… Каждый следующий режим повышает уверенность программиста в том, что его программа прочитает из памяти именно то, что…

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

1. СОМА (Cache Only Memory Architecture) – архитектура памяти, при которой работа с ней происходит как с кэшем. Система переносит страницы памяти, с которой данный процессорный модуль работает чаще других, в его локальную память.

2. CC-NUMA (Cache-Coherent Non-Uniform Memory Access), неоднородный дос­туп к памяти с обеспечением когерентности кэшей). В этой архитектуре адаптеры межмодульных соединений снабжаются собственной кэш­памятью, которая используется при обращениях к ОЗУ других модулей. Основная деятельность центрального коммутатора и каналов связи со­стоит в поддержании когерентности этих кэшей.

Понятно, что обе эти архитектуры не решают в корне проблемы неоднород­ности доступа: для обеих можно построить такую последовательность меж­процессорных взаимодействий, которая промоет (Промывание кэша — довольно распространенный термин. Это последовательность обращений, которая намного больше объема кэша и в которой нет ни одного повторного обращения к одной и той же странице, или очень мало таких обращений.) все кэши и перегрузит межмодульные связи, а в случае СОМА приведет к постоянной перекачке страниц памяти между модулями. То же самое, впрочем, справедливо и для симметричных многопроцессорных систем с общей шиной. В качестве резюме можно лишь подчеркнуть, что масштабируемость (отношение производительности системы к количеству процессоров) мно­гопроцессорных систем определяется в первую очередь природой задачи и уровнем параллелизма, заложенным в использованный для решения этой задачи алгоритм. Разные типы многопроцессорных систем и разные топо­логии межпроцессорных соединений пригодны и оптимальны для различ­ных задач.