Первое слово каждого блока используется как указатель на следующий блок. В остальной части блока хранятся данные.
В отличие от систем с непрерывными файлами, такой метод позволяет использовать каждый блок диска. Нет потерь дискового пространства на фрагментацию (кроме потерь в последних блоках файла). Кроме того, в каталоге нужно хранить только адрес первого блока файла. Всю остальную информацию можно найти там. С другой стороны, хотя последовательный доступ к такому файлу несложен, произвольный доступ будет довольно медленным. Кроме того, размер блока уменьшается на несколько байтов, требуемых для хранения указателя. Если первые несколько байтов каждого блока будут заняты указателем на следующий блок, то для чтения блока полного размера придется считывать и объединять два соседних блока диска, для чего потребуется выполнение дополнительных операций
Опишите механизм кеширования для повышения производительности файловой системы.
Для минимизации количества обращений к HDD применяется блочный кэш или буферный кэш. В данном контексте кэшем называется набор блоков, логически принадлежащих диску, но хранящихся в оперативной памяти по соображениям производительности. Существуют различные алгоритмы управления кэшем. Обычная практика заключается в перехвате всех запросов чтения к диску и проверке наличия требующихся блоков в кэше. Если блок присутствует в кэше, то запрос чтения блока может быть удовлетворен без обращения к диску. В противном случае блок сначала считывается с диска в кэш, а оттуда копируется по нужному адресу памяти. Последующие обращения к тому же блоку могут удовлетворяться из кэша.
Также кэширование результатов поиска значительно ускоряет процесс поиска файлов в больших каталогах. Прежде чем начать поиск файла, проверяется, нет ли его имени в кэше. Если ФС недавно уже искала этот файл, его имя окажется в кэше и повторная операция поиска будет выполнена очень быстро. Конечно, кэширование поможет только в том случае, если ФС много раз обращается к небольшому количеству файлов.
Опишите UMA-мультипроцессоры с общей шиной, в чем состоит основная идея. Опишите UMA-мультипроцессоры: без кеша, с кешем, с кешем и локальной памятью. Какие существуют ограничения использования такой архитектуры.
В основе простейшей архитектуры мультипроцессоров лежит идея общей шины. Несколько CPU и несколько модулей памяти одновременно используют одну и ту же шину для общения друг с другом. Когда CPU хочет прочитать слово в памяти, он сначала проверяет, свободна ли шина. Если шина свободна, CPU выставляет на нее адрес нужного ему слова, подает несколько управляющих сигналов и ждет, пока память не выставит нужное слово на шину данных. Если шина занята, CPU просто ждет, пока она не освободится. При большом количестве CPU большую часть времени CPU будут простаивать.
Если добавить каждому CPU кэш, большое количество обращений к памяти теперь может быть удовлетворено прямо из кэша, обращений к шине будет существенно меньше, и система сможет поддерживать большее число CPU.
Еще один вариант архитектуры мультипроцессоров - у каждого CPU имеется не только кэш, но также и локальная собственная память, с. которой он соединен по индивидуальной шине. Для оптимального использования подобной конфигурации компилятор должен поместить текст программы, константы, стеки (то есть все неизменяемые данные), а также локальные переменные в локальные модули памяти. При этом общая память используется только для общих модифицируемых переменных.
Механизм синхронизации в мультипроцессорах посредством мьютекс-протокола. Взаимное исключение. Кэширование и проблема конкуренции за шину. Решение проблемы кэширования: итерация пробного чтения, двоичный экспоненциальный откат, опрос собственной переменной блокировки.
В мультипроцессорных системах часто требуется синхронизация CPU. Мьютекс-протокол выполняется всеми CPU, чтобы гарантировать работу взаимного исключения. Сердцем любого практического мьютекс-протокола является команда CPU, позволяющая исследовать и изменить слово в памяти за одну операцию. Эта команда считывает слово памяти в регистр CPU. Одновременно она записывает 1 (или другое ненулевое значение) в слово памяти. Конечно, для выполнения операций чтения и записи памяти требуется два цикла шины.
На мультипроцессоре команда TSL может работать неверно, если не заблокировать шину. Для разрешения этой проблемы команда TSL сначала должна блокировать шину посредством команды LOCK, не допуская обращения к ней других CPU, затем выполнить оба обращения к памяти, после чего разблокировать шину. Подобный способ реализации взаимного исключения использует спин-блокировку, что является не только тратой времени запрашивающего CPU, но также может накладывать значительную нагрузку на шину или память, существенно снижая скорость работы всех остальных CPU, пытающихся выполнять свою обычную работу. Наличие кэширования не устраняет проблему конкуренции за шину. Весь блок кэша, содержащий слово блокировки, постоянно мотается взад-вперед от CPU, удерживающего блокировку, к CPU, пытающемуся ее получить. Все это создает довольно значительный и совершенно излишний трафик шины. Решение проблемы: 1. запрашивающая сторона сначала выполняет простую итерацию чтения, чтобы убедиться, что мьютекс свободен. Только убедившись, что он свободен, CPU выполняет команду TSL, чтобы захватить его. 2. Использование алгоритма двоичного экспоненциального отката. Вместо постоянного опроса, между опросами может быть вставлен цикл задержки. Вначале задержка представляет собой одну команду. Если мьютекс занят, задержка удваивается, учетверяется и т. д. до некоторого максимального уровня. При низком уровне получим быструю реакцию при освобождении мьютекса, зато потребуется больше обращений к шине для чтения блока кэша. Высокий максимальный уровень позволит уменьшить число лишних обращений к шине за счет более медленной реакции программы на освобождение мьютекса. 3. каждый CPU, желающий заполучить мьютекс, опрашивает свою собственную переменную блокировки, которая находится в не используемом для других целей блоке кэша.
8. Опишите механизм бригадного планирования – планирование во времени и пространстве, в чем его достоинства и недостатки.
Бригадное планирование представляет собой развитие идеи совместного планирования. Состоит из трех частей:
1. Группы связанных потоков планируются как одно целое, бригада.
2. Все члены бригады запускаются одновременно, на разных CPU с разделением времени.
3. Все члены бригады начинают и завершают свои временные интервалы вместе.
Бригадное планирование работает благодаря синхронности работы всех CPU. Это значит, что время разделяется на дискретные кванты. В начале каждого нового кванта все CPU перепланируются заново, и на каждом CPU запускается новый поток. В начале следующего кванта опять принимается решение о планировании. В середине кванта планирование не выполняется. Если какой-либо поток блокируется, его CPU простаивает до конца кванта времени. Идея бригадного планирования состоит в том, чтобы все потоки процесса работали по возможности вместе, так, что если один из них посылает сообщение другому потоку, то второй поток получает сообщение практически мгновенно и может так же быстро на него ответить. Поскольку все потоки процесса работают вместе в течение одного кванта времени, они могут отправлять и принимать большое количество сообщений за один квант времени.