Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Уровень операционной системы
Операционная система — это программа, которая добавляет ряд команд и особенностей к тем, которые обеспечиваются уровнем команд. Обычно операционная система реализуется главным образом в программном обеспечении, но нет никаких веских причин, по которым ее нельзя было бы реализовать в аппаратном обеспечении.
Набор команд уровня операционной системы — это полный набор команд, доступных для прикладных программистов. Он содержит практически все команды более низкого уровня, а также новые команды, которые добавляет операционная система. Эти новые команды называются системными вызовами. Они вызывают определенную службу операционной системы, в частности одну из ее команд.
Уровень операционной системы всегда интерпретируется. Когда пользовательская программа выполняет команду операционной системы, например чтение данных из файла, операционная система выполняет эту команду шаг за шагом, точно так же, как микропрограмма выполняет команду ADD . Однако когда программа выполняет команду уровня архитектуры команд, эта команда выполняется непосредственно микроархитектурным уровнем без участия операционной системы.
Уровень операционной системы имеет несколько особенновстей. Первая из них — это виртуальная память. Виртуальная память используется многими операционными системами. Она позволяет создать впечатление, что у машины больше памяти, чем есть на самом деле. Вторая особенность — файл ввода-вывода. Это понятие более высокого уровня, чем команды ввода-вывода, которые мы рассматривали в предыдущей главе. Третья особенность — параллельная обработка (как несколько процессов могут выполняться, обмениваться информацией и синхронизироваться).
Виртуальная память
В первых компьютерах память была очень мала по объему и к тому же дорого стоила. В те времена программисты тратили очень много времени на то, чтобы впихнуть свои программы в крошечную память.
Традиционным решением этой проблемы было использование вспомогательной памяти (например, диска). Программист делил программу на несколько частей, так называемых оверлеев, каждый из которых помещался в память. Чтобы прогнать программу, сначала следовало считывать и запускать первый оверлей. Когда он завершался, нужно было считывать и запускать второй оверлей и т. д.
В 1961 году группа исследователей из Манчестера предложила метод автоматического выполнения процесса наложения, при котором программист мог вообще не знать об этом процессе [42]. Этот метод, который сейчас называется виртуальной памятью, имел очевидное преимущество, поскольку освобождал программиста от огромного количества нудной работы. Впервые этот метод был использован в ряде компьютеров, выпущенных в 60-е годы. К началу 70-х годов виртуальная память появилась в большинстве компьютеров.
Страничная организация памяти
Группа ученых из Манчестера выдвинула идею о разделении понятий адресного пространства и адресов памяти. Рассмотрим в качестве примера типичный компьютер того времени с 16-битным полем адреса в командах и 4096 словами памяти. Программа, работающая на таком компьютере, могла обращаться к 65536 словам памяти.
До изобретения виртуальной памяти приходилось проводить жесткое различие между теми адресами, которые меньше 4096, и теми, которые равны или больше 4096. Эти две части рассматривались как полезное адресное пространство и бесполезное адресное пространство соответственно. Никакого различия между адресным пространством и адресами памяти не проводилось, поскольку между ними подразумевалось взаимно-однозначное соответствие.
Идея разделения понятий адресного пространства и адресов памяти состоит в следующем. В любой момент времени можно получить прямой доступ к 4096 словам памяти, но это не значит, что они непременно должны соответствовать адресам памяти от 0 до 4095. Например, мы могли бы сообщить компьютеру, что при обращении к адресу 4096 должно использоваться слово из памяти с адресом 0, при обращении к адресу 4097 — слово из памяти с адресом 1, при обращении к адресу 8191 — слово из памяти с адресом 4095 и т. д. Другими словами, определяется отображение из адресного пространства в действительные адреса памяти.
Рис. 6.2. Виртуальные адреса памяти с 4096 по 8191 отображаются в адреса основной памяти с 0 по 4095.
Возникает интересный вопрос: а что произойдет, если программа совершит переход в один из адресов с 8192 по 12287? В машине без виртуальной памяти произойдет ошибка, на экране появится фраза «Несуществующий адрес памяти» и выполнение программы остановится. В машине с виртуальной памятью будет иметь место следующая последовательность шагов:
Такая технология автоматического наложения называется страничной организацией памяти, а куски программы, которые считываются с диска, называются страницами.
Возможен и другой, более сложный способ отображения адресов из адресного пространства в реальные адреса памяти. Адреса, к которым программа может обращаться, мы будем называть виртуальным адресным пространством, а реальные адреса памяти в аппаратном обеспечении — физическим адресным пространством. Схема распределения памяти или таблица страниц соотносит виртуальные адреса с физическими адресами. Предполагается, что на диске достаточно места для хранения полного виртуального адресного пространства.
Программы пишутся так, как будто в основной памяти хватит места для размещения всего виртуального адресного пространства, даже если это не соответствует действительности. Программы могут загружать слова из виртуального адресного пространства или записывать слова в виртуальное адресное пространство, несмотря на то, что на самом деле физической памяти для этого не хватает. Программист может писать программы, даже не осознавая, что виртуальная память существует. Просто создается такое впечатление, что объем памяти данного компьютера достаточно велик.
Реализация страничной организации памяти
Виртуальное адресное пространство разбивается на ряд страниц равного размера, обычно от 512 до 64 Кбайт. Физическое адресное пространство тоже разбивается на части равного размера таким образом, чтобы каждая такая часть основной памяти вмещала ровно одну страницу. Эти части основной памяти называются страничными кадрами.
На рисунке 6.3 (а) показан один из возможных вариантов разделения первых 64 К виртуального адресного пространства на страницы по 4 К. Адрес может быть байтом, но может быть словом в компьютере, в котором последовательно расположенные слова имеют последовательные адреса. Виртуальную память, изображенную на рис. 6.3, можно реализовать посредством таблицы страниц, в которой количество элементов равно количеству страниц в виртуальном адресном пространстве.
Рис. 6.3. Первые 64К виртулаьного адреного пространства разделены на 16 страниц по 4К каждая (а); 32К основной памяти разделены на 8 страничных кадров по 4К каждый (б).
На рис. 6.3 (б) изображена физическая память, состоящая из восьми страничных кадров по 4 К. Эту память можно ограничить до 32К, поскольку:
Каждый компьютер с виртуальной памятью содержит устройство для осуществления отображения виртуальных адресов на физические. Это устройство называется контроллером управления памятью (MMU – Memory Management Unit). Он может находиться на микросхеме процессора или на отдельной микросхеме рядом с процессором. В нашем примере контроллер управления памятью отображает 32-битный виртуальный адрес в 15-битный физический адрес, поэтому ему требуется 32-битный входной регистр и 15-битный выходной регистр.
Когда в контроллер управления памятью поступает 32-битный виртуальный адрес, он разделяет этот адрес на 20-битный номер виртуальной страницы и 12-битное смещение внутри этой страницы (поскольку страницы в нашем примере по 4 К). Номер виртуальной страницы используется в качестве индекса в таблице страниц для нахождения нужной страницы.
Сначала контроллер управления памятью проверяет, находится ли нужная страница в текущий момент в памяти. Поскольку у нас есть 220 виртуальных страниц и всего 8 страничных кадров, не все виртуальные страницы могут находиться в памяти одновременно. Контроллер управления памятью проверяет бит присутствия в данном элементе таблицы страниц. В нашем примере этот бит равен 1. Это значит, что страница в данный момент находится в памяти.
Далее из выбранного элемента таблицы нужно взять значение страничного кадра (в нашем примере — 6) и скопировать его в старшие три бита 15-битного выходного регистра. Нужно именно три бита, потому что в физической памяти находится 8 страничных кадров. Параллельно с этой операцией младшие 12 битов виртуального адреса (поле смещения страницы) копируются в младшие 12 битов выходного.
Рис. 6.4. Формирование адреса основной памяти из адреса виртуальной памяти.
Вызов страниц по требованию. Политика замещения страниц.
При обращении к адресу страницы, которой нет в основной памяти, происходит ошибка из-за отсутствия страницы. В случае такой ошибки операционная система должна считать нужную страницу с диска, ввести новый адрес физической памяти в таблицу страниц, а затем повторить команду, которая вызвала ошибку. Такой метод работы с виртуальной памятью называется вызовом страниц по требованию.
Вопрос о том, стоит ли использовать вызов страниц по требованию или нет, имеет смысл только в самом начале при запуске программы. Когда программа проработает некоторое время, нужные страницы уже будут собраны в основной памяти. Если это компьютер с разделением времени и процессы откачиваются обратно, проработав примерно 100 миллисекунд, то каждая программа будет запускаться много раз. Для каждой программы распределение памяти уникально и при переключении с одной программы на другую меняется, поэтому в системах с разделением времени такой подход не годится.
Альтернативный подход основан на наблюдении, что большинство команд обращаются к адресному пространству не равномерно. Обычно большинство обращений относятся к небольшому числу страниц. При обращении к памяти можно вызвать команду, вызвать данные или сохранить данные. В каждый момент времениt существует набор страниц, которые использовались при последних к обращениях. Этот набор страниц называется рабочим множеством.
Поскольку рабочее множество обычно меняется очень медленно, можно, опираясь на последнее перед остановкой программы рабочее множество, предсказать, какие страницы понадобятся при новом запуске программы. Эти страницы можно загрузить заранее перед очередным запуском программы.
В идеале набор страниц, которые постоянно используются программой (так называемое рабочее множество), можно хранить в памяти, чтобы сократить количество ошибок из-за отсутствия страниц. Если программа обращается к странице, которая отсутствует в основной памяти, ее нужно вызвать с диска. Однако чтобы освободить для нее место, на диск нужно отправить какую-нибудь другую страницу. Следовательно, нужен алгоритм для определения, какую именно страницу необходимо убрать из памяти. Выбирать такую страницу просто наугад нельзя. Если, например, выбрать страницу, содержащую команду, выполнение которой вызвало ошибку, то при попытке вызвать следующую команду произойдет еще одна ошибка из-за отсутствия страницы.
По одному из алгоритмов удаляется та страница, которая использовалась наиболее давно, поскольку вероятность того, что она будет в текущем рабочем множестве, очень мала. Этот алгоритм называется LRU (Least Recently Used — алгоритм удаления наиболее давно использовавшихся элементов).
Можно применять и другой алгоритм — FIFO (First-in First-out — первым поступил, первым выводится). FIFO удаляет ту страницу, которая раньше всех загружалась, независимо от того, когда в последний раз производилось обращение к этой странице. С каждым страничным кадром связан отдельный счетчик. Изначально все счетчики установлены на 0. После каждой ошибки из-за отсутствия страниц счетчик каждой страницы, находящейся в памяти, увеличивается на 1, а счетчик только что вызванной страницы принимает значение 0. Когда нужно выбрать страницу для удаления, выбирается страница с самым большим значением счетчика. Поскольку она не загружалась в память очень давно, существует большая вероятность, что она больше не понадобится.
Если размер рабочего множества больше, чем число доступных страничных кадров, ни один алгоритм не дает хороших результатов, и ошибки из-за отсутствия страниц будут происходить часто. Если программа постоянно вызывает подобные ошибки, то говорят, что наблюдается пробуксовка (thrashing). Пробуксовка очень нежелательна.
Размер страниц и фрагментация
Если пользовательская программа и данные время от времени заполняют ровно целое число страниц, то когда они находятся в памяти, свободного места там не будет. С другой стороны, если они не заполняют ровно целое число страниц, на последней странице останется неиспользованное пространство. Например, если программа и данные занимают 26 000 байтов на машине с 4096 байтами на страницу, то первые 6 страниц будут заполнены целиком, что в сумме даст 6x4096=24 576 байтов, а последняя страница будет содержать 26 000-24576=1424 байта. Поскольку в каждой странице имеется пространство для 4096 байтов, 2672 байта останутся свободными. Всякий раз, когда седьмая страница присутствует в памяти, эти байты будутзанимать место в основной памяти, но при этом не будут выполнять никакой функции. Эта проблема называется внутренней фрагментацией (поскольку неиспользованное пространство является внутренним по отношению к какой-то странице).
Если размер страницы составляет n байтов, то среднее неиспользованное пространство в последней странице программы будет n/2 байтов — ситуация подсказывает, что нужно использовать страницы небольшого размера, чтобы свести к минимуму количество неиспользованного пространства. С другой стороны, если страницы маленького размера, то потребуется много страниц и большая таблица страниц. Если таблица страниц сохраняется в аппаратном обеспечении, то для хранения большой таблицы страниц нужно много регистров, что повышает стоимость компьютера. Кроме того, при запуске и остановке программы на загрузку и сохранение этих регистров потребуется больше времени.
Однако у маленьких страниц есть свои преимущества. Если рабочее множество состоит из большого количества маленьких отделенных друг от друга областей виртуального адресного пространства, при маленьком размере страницы будет реже возникать пробуксовка (режим интенсивной подкачки), чем при большом.
Сегментация
До сих пор обсуждалась только одномерная виртуальная память, в которой виртуальные адреса идут один за другим от 0 до какого-то максимального адреса. По многим причинам гораздо удобнее использовать два или несколько отдельных виртуальных адресных пространств. Например, компилятор может иметь несколько таблиц, которые создаются в процессе компиляции:
Каждая из первых четырех таблиц постоянно растет в процессе компиляции. Последняя таблица растет и уменьшается совершенно непредсказуемо. В одномерной памяти эти пять таблиц пришлось бы разместить в виртуальном адресном пространстве в виде смежных областей, рис. 6.6.
Область адресного пространства, предназначенная для таблицы символов, может переполниться, даже если в других таблицах полно свободного места. Компилятор может забирать свободное пространство у одних таблиц и передавать его другим таблицам, но это похоже на управление оверлеями вручную — некоторое неудобство в лучшем случае и долгая скучная работа в худшем.
Рис. 6.6. Одномерная виртуальная память с «врезающимися» друг в друга таблицами.
На самом деле нужно просто освободить программиста от расширения и сокращения таблиц. Для этого нужно создать много абсолютно независимых адресных пространств, которые называются сегментами. Каждый сегмент состоит из линейной последовательности адресов от 0 до какого-либо максимума. Длина каждого сегмента может быть любой от 0 до некоторого допустимого максимального значения. Разные сегменты могут иметь разную длину (обычно так и бывает). Более того, длина сегмента может меняться во время выполнения программы. Длина стекового сегмента может увеличиваться всякий раз, когда что-либо помещается в стек, и уменьшаться, когда что-либо выталкивается из стека.
Так как каждый сегмент основывает отдельное адресное пространство, разныесегменты могут увеличиваться или уменьшаться независимо друг от друга и невлияя друг на друга. Естественно, сегмент может переполниться, но это происходит редко, поскольку сегменты очень большие. Чтобы определить адрес в двухмерной памяти, программа должна выдавать номер сегмента и адрес внутри сегмента.
Рис. 6.7. Сегментированная память.
Сегментированная память имеет и другие преимущества помимо упрощения работы со структурами данных, которые постоянно уменьшаются или увеличиваются. Если каждая процедура занимает отдельный сегмент, в котором первый адрес — это адрес 0, то связывание процедур, которые компилируются отдельно, сильно упрощается. Когда все процедуры программы скомпилированы и связаны, при вызове процедуры из сегмента n для обращения к слову 0 будет использовать- ся адрес (n, 0).
Если процедура в сегменте n впоследствии изменяется и перекомпилируется, то другие процедуры менять не нужно (поскольку ни один начальный адрес не был изменен), даже если новая версия больше по размеру, чем старая. В одномерной памяти процедуры обычно располагаются друг за другом, и между ними нет никакого адресного пространства. Следовательно, изменение размера одной процедуры может повлиять на начальный адрес других процедур. Это, в свою очередь, требует изменения всех процедур, которые вызвают любую из этих процедур, чтобы попадать в новые начальные адреса. Если в программу включено много процедур, этот процесс будет слишком накладным.
Сегментация облегчает разделение общих процедур или данных между несколькими программами. Если компьютер содержит несколько программ, работающих параллельно, и если все эти программы используют определенные процедуры, снабжать каждую программу отдельной копией расточительно для памяти. А если сделать каждую процедуру отдельным сегментом, их легко можно будет разделять между несколькими программами, что исключит необходимость создавать физические копии каждой разделяемой процедуры.
Разные сегменты могут иметь разные виды защиты. Например, сегмент с процедурой можно определить как «только для выполнения», запретив тем самым считывание из него и запись в него. Для массива с плавающей точкой разрешается только чтение и запись, но не выполнение и т. д. Такая защита часто помогает обнаружить ошибки в программе.
Реализация сегментации
Сегментацию можно реализовать одним из двух способов. Это подкачка и разбиение на страницы. При первом подходе некоторый набор сегментов находится в памяти в данный момент. Если происходит обращение к сегменту, которого нет в данный момент в памяти, этот сегмент переносится в память. Если для него нет места в памяти, один или несколько сегментов нужно сначала записать на диск.
Сегментация существенно отличается от разбиения на страницы в следующем: размер страниц фиксирован, а размер сегментов — нет. На рис. 6.8 (а) показан пример физической памяти, в которой изначально содержится 5 сегментов. Посмотрим, что происходит, если сегмент 1 удаляется, а сегмент 7, который меньше по размеру, помещается на его место. В результате получится конфигурация, изображенная на рис. 6.8 (б). Между сегментом 7 и сегментом 2 находится неиспользованная область («дырка»). Затем сегмент 4 меняется на сегмент 5 (рис. 6.8 (в)), а сегмент 3 замещается сегментом 6 (рис. 6.8 (г)). Через некоторое время память разделится на ряд областей, одни из которых будут содержать сегменты, а другие — неиспользованные области. Это называется внешней фрагментацией (поскольку неиспользованное пространство попадает не в сегменты, а в «дырки» между ними, то есть процесс происходит вне сегментов). Иногда внешнюю фрагментацию называют поклеточной разбивкой.
Если программа обратится к сегменту 3 в тот момент, когда память подвергается внешней фрагментации (рис. 6.8, г), то общее пространство «дырок» составляет 10 Кбайт, а это больше, чем нужно для сегмента 3, но так как это пространство разбито на маленькие кусочки, сегмент 3 туда загрузить нельзя. Вместо этого приходится сначала удалять другой сегмент.
Чтобы избежать такой ситуации, нужно сделать следующее. Каждый раз, когда появляется «дырка», нужно перемещать сегменты, следующие за «дыркой», ближе к адресу 0, устраняя таким образом эту «дырку» и оставляя большую «дырку» в конце.
Рис. 6.8. Динамика внешней фрагментации (а, б, в, г); удаление внешней сегментайии путем уплотнения (д).
Нужен специальный агоритм для определения, какую именно «дырку» лучше использовать для определенного сегмента. Для этого требуется список адресов и размеров всех «дырок». Популярный алгоритм оптимальной подгонки выбирает самую маленькую «дырку», в которую помещается нужный сегмент. Цель этого алгоритма — соотнести «дырки» и сегменты, чтобы избежать «отламывания» куска большой «дырки», который может понадобиться позже для большого сегмента.
Другой популярный алгоритм по кругу просматривает список «дырок» и выбирает первую «дырку», которая по размеру подходит для данного сегмента. Естественно, это занимает меньше времени, чем проверка всего списка, чтобы найти оптимальную «дырку». Последний алгоритм гораздо лучше, чем алгоритм оптимальной подгонки, с точки зрения общей производительности, поскольку оптимальная подгонка порождает очень много маленьких неиспользованных дырок
Говорилось, что реализовать сегментацию можно двумя способами: подкачкой и разбиением на страницы. До сих пор речь шла о подкачке. При таком подходе по необходимости между памятью и диском перемещаются целые сегменты.
Второй способ реализации — разделить каждый сегмент на страницы фиксированного размера и вызывать их по требованию. В этом случае одни страницы сегмента могут находиться в памяти, а другие — на диске. Чтобы разбить сегмент на страницы, для каждого сегмента нужна отдельная таблица страниц. Поскольку сегмент представляет собой линейное адресное пространство, все средства разбиения на страницы, которые мы до сих пор рассматривали, применимы к любому сегменту. Единственное различие состоит в том, что каждый сегмент получает отдельную таблицу страниц.
Виртуальная память в процессоре Pentium II
Pentium II имеет сложную систему виртуальной памяти, которая поддерживает вызов страниц по требованию, чистую сегментацию и сегментацию с разбиением на страницы. Виртуальная память состоит из двух таблиц: LDT (Local Descriptor Table — локальная таблица дескрипторов) и GDT (Global Descriptor Table —глобальная таблица дескрипторов). Каждая программа имеет свою собственную локальную таблицу дескрипторов, а единственная глобальная таблица дескрипторов разделяется всеми программами компьютера. Локальная таблица дескрипторов LDT описывает локальные сегменты каждой программы (ее код, данные, стек и т. д.), а глобальная таблица дескрипторов GDT описывает системные сегменты, в том числе саму операционную систему.
Каждая работающая программа имеет специальную таблицу страниц, которая состоит из 1024 32-битных элементов. Ее адрес указывается глобальным регистром. Каждый элемент в этой таблице указывает на таблицу страниц, которая также содержит 1024 32-битных элементов. Элементы таблицы страниц указывают на страничные кадры. Схема изображена на рис. 6.13.
Рис. 6.13. Отображение линейного адреса на физический адрес
В завершение стоит сказать несколько слов о защите, поскольку это имеет непосредственное отношение к виртуальной памяти. Pentium II поддерживает 4 уровня защиты, где уровень 0 — самый привилегированный, а уровень 3 — наименее привилегированный. Они показаны на рис. 6.14. В каждый момент работающая программа находится на определенном уровне, указывающемся 2-битным полем в PSW (Program Status Word — слово состояния программы) — регистре аппаратного обеспечения, который содержит коды условия и другие биты состояния. Более того, каждый сегмент в системе также принадлежит к определенному уровню.
Рис. 6.14. Уровни защиты процессора Pentium II.
Виртуальная память UltraSPARC II
UltraSPARC II — это 64-разрядная машина, которая поддерживает виртуальную память со страничной организацией и с 64-битными виртуальными адресами. Тем не менее по разным причинам программы не могут использовать полное 64-битное виртуальное адресное пространство. Поддерживается только 64 бита, поэтому программы не могут превышать 1,8х1013 байтов.
Допустимая виртуальная память делится на 2 зоны по 243 байтов каждая, одна из которых находится в верхней части виртуального адресного пространства, а другая — в нижней. Между ними находится «дырка», содержащая адреса, которые не используются. Попытка использовать их вызовет ошибку из-за отсутствия страницы.
Из-за огромного виртуального адресного пространства обычная таблица страниц (как в Pentium II) не будет практичной. В UltraSPARC II применяется совершенно другой подход. Устройство управления памятью содержит таблицу, так называемый TLB (Translation Lookaside Buffer — буфер быстрого преобразования адреса). Эта таблица отображает номера виртуальных страниц в номера физических страничных кадров. Для страниц размером в 8К существует 231 номеров виртуальных страниц, то есть более двух миллиардов. Естественно, не все они могут быть отображены.
Поэтому TLB содержит только номера самых последних используемых виртуальных страниц. Страницы команд и страницы данных рассматриваются отдельно. Для каждой из этих категорий в TLB включены номера 64 последних виртуальных страниц. Каждый элемент этого буфера включает номер виртуальной страницы и соответствующий номер физического страничного кадра.
Когда номер процесса вызывает его контекст, виртуальный адрес в этом контексте передается в контроллер управления памятью, то он с помощью специальной схемы сравнивает номер виртуальной страницы со всеми элементами буфера быстрого преобразования адреса TLB для данного контекста одновременно. Если обнаруживается совпадение, номер страничного кадра в этом элементе буфера соединяется со смещением, взятым из виртуального адреса, чтобы получить 41-битный физический адрес и обработать некоторые флаги.
Если совпадение не обнаружилось, происходит промах в TLB, который вызывает ловушку в операционной системе. Обрабатывать ошибку должна сама операционная система
Операционная система должна сохранять наиболее часто используемые элементы буфера TLB в таблице под названием буфер хранения преобразований (TSB — translation storage buffer). Эта таблица построена как кэш-память прямого отбражения виртуальных страниц. Каждый 16-байтный элемент данной таблицы указывает на одну виртуальную страницу и содержит бит достоверности, номер контекста, тег виртуального адреса, номер физической страницы и несколько флаговых битов.
Если нужной виртуальной страницы нет в кэш-памяти, операционная система использует другую таблицу для нахождения информации о странице, которая может находиться или не находиться в основной памяти. Таблица, которая применяется для этого поиска, называется транслирующей таблицей.
Файлы
Набор команд уровня операционной системы содержит большую часть команд из уровня архитектуры команд, а также несколько новых очень важных команд. Некоторые ненужные команды в уровень операционной системы не включаются. Ввод-вывод — это одна из областей, в которых эти два уровня различаются очень сильно.
Один из способов организации виртуального ввода-вывода — использование абстракции под названием файл. Файл состоит из последовательности байтов, записанных на устройство ввода-вывода.
Ввод-вывод файла осуществляется с помощью системных вызовов для открытия, чтения, записи и закрытия файлов. Перед тем как считывать файл, его нужно открыть. Процесс открытия файла позволяет операционной системе найти файл на диске и передать в память информацию, необходимую для доступа к этому файлу.
После открытия файла его можно считывать. Системный вызов для считывания должен иметь как минимум следующие параметры:
Данный системный вызов помещает требующиеся данные в буфер. Обычно он возвращает число считанных байтов. Это число может быть меньше того числа, которое запрашивалось изначально (например, нельзя считать 2000 байтов из файла размером 1000 байт).
С каждым открытым файлом связан указатель, который сообщает, какой байт будет считываться следующим. После команды read указатель дополняется числом считанных байтов, поэтому последовательные команды read считывают последовательные блоки данных из файла. Обычно этот указатель можно установить на особое значение, чтобы программы могли получать доступ к любой части файла. Когда программа закончила считывание файла, она может закрыть его и сообщить операционной системе, что она больше не будет использовать этот файл. Операционная система сможет освободить пространство в таблице, в которой хранилась информация об этом файле.
В операционных системах для универсальных вычислительных машин файл представляет собой более сложную структуру. Здесь файл может быть последовательностью логических записей, каждая из которых имеет строго определенную структуру.
Основная виртуальная команда ввода считывает следующую запись из нужного файла и помещает ее в основную память, начиная с определенного адреса, как показано на рис. 6.17. Чтобы выполнить эту операцию, виртуальная команда должна получить сведения о том, какой файл считывать и куда в памяти поместить запись. Часто существуют параметры для чтения некоторой записи, которые определяются или по ее месту в файле, или по ее ключу.
Рис. 6.17. Чтение файла состоящего из логических записей: до чтения записи 19 (а); после чтения записи 19 (б).
Основная виртуальная команда вывода записывает логическую запись из памяти в файл. Последовательные команды write производят последовательные логические записи в файл.
Параллельная обработка
Некоторые вычисления удобно производить с помощью двух и более параллельных процессов (то есть как будто бы на разных процессорах). Другие вычисления можно поделить на части, которые затем выполняются параллельно, что сокращает общее время вычисления.
В компьютере с несколькими процессорами каждый из нескольких взаимодействующих процессов можно приписать к одному определенному процессору, чтобы выполнять несколько действий одновременно. Если в компьютере имеется только один процессор, эффект параллельной обработки можно смоделировать. Для этого процессы будут выполняться по очереди, каждый понемножку. Иными словами, процессор будет разделяться между несколькими процессами.
Формирование процесса
Программа должна работать как часть какого-либо процесса. Этот процесс, как и все другие процессы, характеризуется состоянием и адресным пространством, через которое можно получить доступ к программам и данным. Состояние включает как минимум счетчик команд, слово состояния программы, указатель стека и регистры общего назначения.
Большинство современных операционных систем позволяют формировать и прерывать процессы динамически. Для формирования нового процесса требуется системный вызов. Этот системный вызов может просто создать клон вызывающей программы или позволить исходному процессу определить начальное состояние нового процесса, то есть его программу, данные и начальный адрес. В одних случаях исходный процесс сохраняет частичный или даже полный контроль над порожденным процессом. В других случаях исходный процесс никак не контролирует порожденный процесс: после того как новый процесс сформирован, исходный процесс не может его остановить, запустить заново, проверить или завершить. Таким образом, эти два процесса работают независимо друг от друга.
Состояние гонок
Во многих случаях параллельные процессы должны взаимодействовать, и их работу нужно синхронизировать.
Рассмотрим два независимых процесса, процесс 1 и процесс 2, которые взаимодействуют через общий буфер в основной памяти. Для простоты мы будем называть процесс 1 производителем (producer), а процесс 2 — потребителем (consumer). Производитель выдает простые числа и помещает их в буфер по одному. Потребитель удаляет их из буфера по одному и печатает. Эти два процесса работают параллельно с разной скоростью. Если производитель обнаруживает, что буфер заполнен, он переходит в режим ожидания, то есть временно приостанавливает операцию и ожидает сигнала от потребителя. Когда потребитель удаляет число из буфера, он посылает сигнал производителю, чтобы тот возобновил работу. Если потребитель обнаруживает, что буфер пуст, он при- останавливает работу. Когда производитель помещает число в пустой буфер, он посылает соответствующий сигнал потребителю.
Для моделирования параллельных процессов на языке Java в данном случае используются потоки (threads).
Каждый поток похож на процесс. Единственным различием является то, что все потоки в пределах одной программы на языке Java работают в одном адресном пространстве. Это позволяет им разделять один общий буфер. Если в компьютере имеется два и более процессоров, каждый поток может выполняться на другом процессоре, поэтому в данном случае имеет место реальный параллелизм. Если компьютер содержит только один процессор, потоки разделяются во времени на одном процессоре.
Пусть in и out указатели на буфер, resume – команда возобновляющая работу потока. Сложность состоит в том, что между моментом, когда потребитель вызывает in и out, и моментом, когда он отключается, производитель, обнаружив, что in=out+1, и предположив, что потребитель отключен (хотя на самом деле он еще продолжает функционировать), вызывает процедуру resume, чего не нужно делать, поскольку потребитель функционирует. Такая ситуация называется состоянием гонок, поскольку успех процедуры зависит от того, кто выиграет гонку по проверке in и out, после того как значение out увеличилось.
Синхронизация с использованием семафоров
Проблему состояния гонок можно разрешить по крайней мере двумя способами. Первый способ — снабдить каждый процесс специальным битом ожидания пробуждения. Если процесс, который функционирует в данный момент, получает сигнал «пробуждения», то этот бит устанавливается. Если процесс отключается в тот момент, когда этот бит установлен, он немедленно перезапускается, а бит сбрасывается. Данный бит сохраняет сигнал пробуждения для будущего использования. Этот метод решает проблему состояния гонок только в том случае, если у нас есть всего 2 процесса. В общем случае при наличии п процессов он не работает. Конечно, каждому процессу можно приписать п -1 таких битов ожидания пробуждения, но это неудобно.
Дейкстра предложил другое решение этой проблемы. Где-то в памяти находятся две переменные, которые могут содержать неотрицательные целые числа. Эти переменные называются семафорами. Операционная система предоставляет два системных вызова, up и down, которые оперируют семафорами. Up прибавляет 1 к семафору, a down отнимает 1 от семафора. Если операция down совершаетсянад семафором, значение которого больше 0, этот семафор уменьшается на 1 и процесс продолжается. Если значение семафора равно 0, то операция down не может завершиться. Тогда данный процесс отключается до тех пор, пока другой процесс не выполнит операцию up над этим семафором.
Команда up проверяет, не равен ли семафор нулю. Если он равен 0 и другой процесс находится в режиме ожидания, то семафор увеличивается на 1. После этого процесс, который «спит», может завершить операцию down, установив семафор на 0. Теперь оба процесса могут продолжать работу. Если семафор не равен 0, команда up просто увеличивает его на 1. Семафор позволяет сохранять сигналы пробуждения, так что они не пропадут зря. У семафорных команд есть одно важное свойство: если один из процессов начал выполнять команду над семафором, то другой процесс не может получить доступ к этому семафору до тех пор, пока первый не завершит выполнение команды или не будет приостановлен при попытке выполнить команду down над 0.
Примеры операционных систем