Разделение и распределение памяти
Одной из отличительных особенностей многопроцессорной вычислительной системы является сеть обмена, с помощью которой процессоры соединяются с памятью.
Рассмотрим структурную организацию однородных одноуровневых микропроцессорных систем, архитектура которых определяется организацией связи процессоров с оперативной памятью данных и организацией межпроцессорного обмена.
По способу организации связи процессоров с оперативной памятью данных все системы относятся к одному из трех типов: с общей (равнодоступной), индивидуальной (раздельной), индивидуальной основной и общей вспомогательной оперативной памятью данных.
Многопроцессорные системы с общей модульной оперативной памятью данных эффективны при решении такого класса задач, данные в которых могут быть размещены в различных модулях общей оперативной памяти. Тогда процессоры системы смогут работать с этими модулями с малыми взаимными помехами.
Система обладает наибольшей универсальностью, если информация, хранимая в любом модуле памяти, доступна любому процессору и устройству ввода-вывода. Эта универсальность достигается за счет аппаратурных затрат на организацию коммутации между любыми модулями памяти, процессорами и устройствами ввода-вывода. Затраты на такой матричный коммутатор растут пропорционально произведению числа модулей памяти на число процессоров и устройств ввода-вывода.
Структурная схема многопроцессорной системы с общей модульной памятью и матричным коммутатором приведена на рис. 18.
Рис. 18. Многопроцессорная система с матричной архитектурой
Каждый из процессоров П1,…,Пmимеет доступ к любому модулю оперативной памяти ОЗУ1,…,ОЗУn. Последние работают параллельно и допускают n одновременных обращений со стороны процессоров или устройств ввода-вывода. При обращении нескольких процессоров или устройств ввода-вывода к одному и тому же модулю памяти возникает конфликтная ситуация и коммутатор обслуживает первым устройство с наивысшим приоритетом.
Многопроцессорные системы с индивидуальной (раздельной) памятью данных эффективны для решения класса задач, где имеются четко разделимые подмножества данных, размещаемых в соответствующих модулях памяти. Структурная схема многопроцессорной системы с индивидуальной памятью приведена на рис. 19.
Рис. 19. Многопроцессорная система с индивидуальной памятью
Каждый процессор П1,…,Пmобращается к своему модулю оперативной памяти ОЗУ1,…,ОЗУm. Однако для редкого обмена данными между процессорами предусмотрены блоки обмена БО и вспомогательная общая оперативная память ОЗУ. Операции обмена инициируются процессорами.
На рис. 20 приведена схема многопроцессорной системы с индивидуальной памятью и одномодульной общей памятью данных. Такая система особенно эффективна для многопрограммной работы с коллективным использованием большого архива базовых данных. Устройство управления памятью регулирует возможные конфликты при одновременном обращении нескольких процессоров к общей одномодульной памяти данных.
Рис. 20. Многопроцессорная система с общей памятью данных
На быстроту обмена информацией между модулями, а следовательно, и на производительность системы большое влияние оказывает способ коммутации процессоров. По способу коммутации все конкретные многопроцессорные системы относятся к одному из типов: структура с матричным коммутатором, общая магистральная структура (общая шина), матричная структура, последовательная конвейерная структура.
Многопроцессорные системы с матричным коммутатором (рис. 18) обладают наибольшей универсальностью. Широко распространены многопроцессорные системы, содержащие программируемый (универсальный) коммутатор, к которому подключаются входы и выходы всех процессоров и запоминающих устройств. В такой системе путем программирования может быть реализована практически любая из многочисленных структур многопроцессорных систем, однако она требует мощной системы коммутации, что связано со значительными аппаратными затратами.
Общая магистральная структура (рис. 21) отличается тем, что несколько процессоров подключаются к одной магистрали, которая осуществляет связь между любыми процессорами. Организация межпроцессорных связей на основе общей магистрали является одним из распространенных способов построения многопроцессорных систем. Такая система является наиболее простой, дешевой и легко наращиваемой.
Рис. 21. Магистральная многопроцессорная система
Одновременно через общую магистраль информация передается между двумя устройствами, т. е. магистраль используется подключенными к ней устройствами в режиме разделения времени. Это является причиной возникновения конфликтов, при которых несколько устройств одновременно претендуют на занятие магистрали, что вызывает простой оборудования и уменьшает производительность системы. Для повышения пропускной способности магистрали иногда создают систему с несколькими параллельными магистралями.
Многопроцессорная система с матричной структурой представлена на рис. 22. Каналы связи организованы по принципу близкодействия: жесткие связи между собой имеют только соседние процессоры, а между отдаленными процессорами каналы связи отсутствуют. Обмен информацией между ними возможен только через цепочку процессоров.
Рис. 22. Матричная многопроцессорная система
Последовательная конвейерная структура многопроцессорной системы (рис. 23) содержит цепочку последовательно соединенных процессоров, так что информация на выходе одного является входной информацией для другого. Процессоры образуют процессорный конвейер (трубопровод). На вход конвейера доставляется поток данных (операнды из памяти). Каждый процессор обрабатывает соответствующую часть задачи, передавая результаты соседнему процессору, который использует их в качестве исходных данных. Таким образом, решение задач для некоторых исходных данных развертывается последовательно в конвейерной цепочке. Это обеспечивается подведением к каждому процессору своего потока команд, т. е. имеется множественный поток команд.
Рис. 23. Конвейерная многопроцессорная система
Если трубопровод заполнен, выходной процессор (Пm) выдает результаты для последовательности входных данных через очень короткие интервалы времени, хотя действительное время прохождения задачи через конвейер может быть существенно большим.
Кроме рассмотренной классификации многопроцессорных систем, широко используется классификация по признаку одинарности или множественности потоков команд и данных. Так, в соответствии с этой классификацией рассмотренную конвейерную систему (см. рис. 23) можно отнести к системам с одинарным потоком данных и множественным потоком команд.
В матричной структуре (см. рис. 22) имеется несколько потоков данных и один общий поток команд, т. е. все процессоры выполняют одновременно одну и ту же команду, но над разными операндами, доставляемыми процессорам из памяти несколькими потоками данных (рис. 24).
Имеются структуры многопроцессорных систем, в которых существует несколько потоков данных и несколько потоков команд.
Отметим, что однопроцессорная система в соответствии с рассматриваемым признаком классификации содержит одинарный поток данных.
Рис. 24. Организация обработки данных в матричной системе
Статьи к прочтению:
Программирование микроконтроллеров: Урок 2. Организация памяти данных(регистры)
Похожие статьи:
При страничной организации виртуальное адресное пространство процесса делится на равные части механически, без учета смыслового значения данных. В одной…
На рис. 10 показана схема страничного распределения памяти. Виртуальное адресное пространство каждого процесса делится на части одинакового,…
Источник
Методы распределения внешней памяти
Основная проблема при построении файловой системы «изнутри» заключается в соотнесении имени файла физическим единицам хранения на носителе информации. В настоящее время данные на магнитных носителях хранятся в виде совокупностей по 512 байтов. (Иногда используются единицы хранения в 1024 или даже 2048 байтов, но по ряду причин они не стали пока употребительными.) Такая совокупность байтов непосредственно на внешнем носителе: дискете или жестком диске называется сектором (сектором магнитного диска). Сектор магнитного диска по смыслу использования аналогичен странице бумаги для печатного текста. Почти также, как в делопроизводстве оказывается неудобным пользоваться листами произвольного размера, в технических системах информации, несмотря на ряд теперь уже забытых попыток, оказалось удобней всего пользоваться подобными стандартными блоками для хранения данных. (Вспомните, даже маленькие стихотворения для постоянного хранения размещают по одному на целой странице бумаги, хотя большая часть такой страницы не используется при этом.)
Сектора магнитного диска в пределах логического диска (или даже всего магнитного носителя) могут быть пронумерованы последовательностью целых чисел. Эту нумерацию могут брать на себя программные компоненты системы ввода-вывода или даже аппаратура современных электронных устройств. Для наших целей пока достаточно, что для компонентов файловой системы вся совокупность секторов диска может однозначно рассматриваться как массив со сквозной нумерацией.
Основной внутренней функцией каталогов в файловых системах оказывается связывание имени файла с информацией о местонахождении файла на магнитном носителе (совершенно также, как для каталога в библиотеке на бумажных носителях). Таким образом внутреннюю структуру элемента каталога файловых систем (ФС) можно образно изобразить в виде
Имя файла -> Информация о месте хранения файла.
В этом же элементе может находиться служебная информации о файле (дата его создания, размер и т.п.), хотя такое решение совсем не обязательно.
Основной технической проблемой хранения файла в техническом носителе является характерное свойство большинства файлов менять свой размер в процессе использования. (Чаще всего файлы пополняются, но могут и уменьшаться в размерах.) Такой эффект не характерен для бумажных носителей информации. Простейшее решение, используемое человеком при хранении увеличивающейся последовательности томов (многотомного издания, печатаемого отдельными томами), заключается в образовании необходимого свободного места для хранения путем раздвижения соседних единиц хранения. Практическая реализация такого подхода для хранения файла породила в свое время метод последовательного непрерывного размещения.
В этом методе для файла выдвигается требование его размещения в непрерывной последовательности пронумерованных секторов. Этим облегчается составление информации о местонахождении файла на магнитном диске: такая информация будет всегда включать номер начального сектора в последовательности секторов хранения и число таких секторов для данного файла (теоретически можно было бы хранить и номер последнего сектора в такой последовательности). Подобное решение предельно просто и применялось в ОС «реального времени» в 80-х годах XX в., называвшейся RT-11. К очевидным недостаткам этого метода относится невозможность увеличить файл на старом месте его хранения, если за ним размещен другой файл. В таком случае содержимое файла с увеличенным размером приходилось размещать на новом месте (если оно имелось). При периодическом пополнении файла его содержимое перемещалось с места на место. Практическое использование указанного метода требовало периодической реорганизации размещения файлов, которое приводило к «выдавливанию» неиспользуемых участков размещения файлов и размещению используемых строго один за другим. Современным аналогом такого действия, решающего хотя и несколько иные задачи, является запуск служебной программы дефрагментации в файловых системах Windows 9x.
При достаточно длительной эксплуатации файловой системы в области хранения данных оказывается много незаполненных промежутков, возникающих как результат удаления файлов (аналог ситуации выбрасывания части книг из книжного шкафа). Поэтому оказывается практически целесообразным размещать данные новых файлов в таких незаполненных промежутках (также как в освободившихся местах книжного шкафа). При этом достаточно большие новые файлы могли не поместиться ни в один из незаполненных промежутков, и у разработчиков возникало естественное желание размещать новые файлы по частям в свободных промежутках. Реализация такого желания влечет отказ от непременного размещения файла в виде непрерывной последовательности секторов.
Наиболее радикальным решением при этом стало встраивание в ФС таких информационных средств, которые позволяют хранить содержимое файла в множестве секторов, произвольно разбросанных по области хранения. Встает вопрос, где же файловой системе хранить информацию о практически произвольном размещении содержимого файла по секторам области хранения? Теоретически возможны два принципиальных решения: хранить эту информацию подобно структуре связного списка в самих секторах области хранения или использовать специальные структуры данных, предназначенные исключительно для информации о размещении файлов. Первое решение называется методом последовательно-связного размещения файла. Оно имеет максимальную гибкость, восходящую к достоинствам абстрактной структуры связного списка, но, к сожалению, и обладает основным недостатком последнего: практической невозможностью произвольного доступа к промежуточным блокам (доступ к элементу связного списка возможен только по цепочке предшествующих элементов). Последнее лишает файловую систему возможности использовать прямой доступ к произвольному элементу файла и, как следствие, настолько снижает ее производительность, что делает такой метод практически нецелесообразным.
Таким образом, возникла практическая неизбежность конструктивного включения в файловую систему специализированных структур хранения информации о размещении содержимого файлов в блоках хранения (в частности, в секторах области хранения данных).
Возможны два варианта построения структур размещения файлов:
— произвольное размещение файлов, допускающее какой угодно разброс блоков файла по исходной совокупности пронумерованных блоков дисковой памяти;
— размещение файлов, использующее участки возможно максимальной длины из последовательно пронумерованных блоков.
Такие участки последовательно пронумерованных блоков дисковой памяти принято называть экстентами (от слова extent).
Произвольное размещение файлов требует наличия таблиц такого размещения. При этом, в свою очередь, возможны следующие варианты:
— единственная таблица размещения на файл;
— таблицы размещения с несколькими уровнями;
— сцепленные таблицы размещения.
Все эти варианты в непосредственном применении требуют построения таблиц, число которых зависит от текущего числа файлов в системе, и поэтому порождают существенно нерегулярные структуры.
Сцепленность таблиц размещения предполагает, что все такие таблицы помещаются одна за другой, в конце каждой таблицы специальным кодом указывается ее конец, а в записи оглавления для файла помещается указатель на начало такой таблицы, соответствующей этому файлу. Сами таблицы размещаются как связный список. Существенной вариацией идеи сцепленных таблиц являются таблицы размещения дисковой памяти, рассматриваемые далее и свободные от отмеченной выше нерегулярности.
Заметим, что все таблицы размещения файлов при работе с файловой системой должны находиться в оперативной памяти для обеспечения достаточно быстрой работы с файлами.
Прежде чем идти дальше отметим, что для нормальной работы файловой системы необходимо иметь не только структуры размещения файлов, но и информацию о свободных на текущий момент блоках возможного размещения. Действительно, информация о размещении блоков файла необходима для доступа к его содержимому, но создание и увеличение уже имеющегося файла невозможно без информации, где размещать его новые данные.
В связи с этим выделяют методы распределения файлов, под которыми понимают распределение новых блоков файлу из свободных на текущий момент. Такие распределения требуют ведения детальной информации о свободных блоках области данных файловой системы. Известны четыре метода распределения файлов, называемые по структуре детальной информации о свободных блоках:
n списком свободных блоков;
n картой свободных участков;
n битовой картой;
n таблицей распределения дисковой памяти.
Список свободных блоков использует структуру связного списка, который соединяет в одну цепочку все свободные блоки (на томе дисковой памяти или логическом диске). Недостатком этого метода являются большие затраты времени на создание и расширение файла, когда ему дополнительно выделяется не один, а достаточно много новых блоков. Удаление файлов при использовании этого метода также требует значительных затрат времени от ОС, потому что файловая система в этом случае должна все блоки удаляемого файла вставить в цепочку свободных блоков (выполняя столько операций над дисками, сколько блоков в удаляемом файле).
Наиболее изящным методом из перечисленных является метод битовой карты. Битовая карта представляет собой вспомогательную таблицу, хранимую на магнитном диске, в которой k-му биту таблицы соответствует k-й блок области данных файловой системы. Одно значение этого бита (обычно единичное) отражает занятость соответствующего блока каким-то файлом, другое значение (обычно нулевое) отражает, что соответствующий блок свободен. Если в конкретной файловой системе имеется к примеру, 4 млн. распределяемых блоков хранения по 512 байтов (секторов) с общей возможностью хранения около 2 Гбайт данных, то битовая таблица будет состоять из 4 млн. битов или, иначе говоря, из 512-килобайтной битовой карты. Такой относительно небольшой объем этой карты позволяет при работе компьютера держать ее постоянно в оперативной памяти и достаточно быстро определять занятость блока дисковой памяти с любым номером. Заметим, что битовая карта дает информацию только о свободных блоках (и как несущественное следствие, о занятых), но не несет никакой информации о размещении файлов по конкретным блокам.
Метод свободных участков предполагает для своего использования, что файлы размещаются не произвольными наборами блоков, а небольшим числом участков с непрерывной нумерацией в каждом из них. Отказ от этого требования приводит к тому, что в определенных неблагоприятных сочетаниях условий (которые могут сложиться в реальной работе операционной системы), свободные участки выродятся в отдельные блоки. Например, может получиться, что каждый нечетный блок распределен некоторому файлу, а каждый четный свободен. В таком неблагоприятном случае для хранения данных о свободных участках потребуется больше места, чем требуется для битовой карты.
Таблица распределения дисковой памяти является структурой, объединяющей в себе свойства и битовой карты и таблицы размещения отдельных файлов. Ее английское наименование File Allocation Table дало обозначение ряду файловых систем (FAT), получивших широкое распространение в разработках фирм IBM и Microsoft, которые рассмотрим далее.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Источник
