Разработка инструментария для повышения эффективности использования кэш-памяти процессора

Размещено на http://www.allbest.ru/

Введение

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

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

Память в современных процессорах имеет иерархическую структуру. Кэш-память реализована на кристалле процессора, с целью улучшить время обращения к памяти. Однако может возникнуть проблема, заключающаяся в том, что локальные кэши процессоров содержат данные не согласованные с данными хранящимися в оперативной памяти. Для решения этой проблемы был разработан алгоритм когерентности, который называется MESI. Работа алгоритма когерентности влияет на производительность всей системы. В многопоточных приложениях может возникнуть ситуация, когда разные объекты делят одну и ту же кэш-линию процессора. Такую проблему называют ложным разделением данных или false sharing. Если происходит false sharing, то система должна согласовать данные в кэшах каждого процессора. Чтобы оптимизировать программу и более эффективно использовать кэш процессора, необходимо улучшить пространственную и временную локальность, а также необходимо заранее выравнивать код и данные. Часто разработчики не задумываются об этих особенностях, что является причиной медленного выполнения разработанного программного обеспечения. Возможно, применяется неэффективный алгоритм или разработчики нерезультативно работают с массивами или со структурами данных в многопоточной среде.

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

1. Постановка задачи

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

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

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

1. Описание предметной области

1.1 Многопроцессорные системы

У всех мультипроцессоров каждый центральный процессор может адресоваться ко всей памяти. Однако по характеру доступа к памяти эти машины делятся на два класса. Мультипроцессоры, у которых каждое слово данных может быть считано с одинаковой скоростью, называются UMA-мультипроцессорами (Uniform Memory Access -- однородный доступ к памяти). В противоположность им мультипроцессоры NUMA (NonUniform Memory Access -- неоднородный доступ к памяти) этим свойством не обладают. [1]

1.1.1 Архитектура многопроцессорных систем с общей шиной

В основе простейшей архитектуры мультипроцессоров лежит идея общей шины (см. рисунок 1).

Рисунок 1- Многопроцессорная система с обшей памятью

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

Чтобы решить эту проблему необходимо добавить каждому центральному процессору кэш. Кэш может располагаться на кристалле центрального процессора. Так как большее количество обращений к памяти будет удовлетворенно кэшем, возможно будет использовать большее число процессоров. Как правило, кэширование выполняется не для отдельных слов, а для блока данных по 32 или по 64 байта. При обращении к слову весь блок считывается в кэш центрального процессора, обратившегося к слову. [1]

1.1.2 Архитектура многопроцессорных систем с неоднородным доступом к памяти

В вычислительных системах с неоднородным доступом к памяти реализована технология NUMA (Non-Uniform Memory Access). Технология неоднородного доступа к памяти позволяет создавать крупномасштабные вычислительные системы. В архитектуре NUMA память физически распределена между процессорами, но логически общедоступна. Это позволяет сохранить преимущества архитектуры с единым адресным пространством, а также ощутимо расширить возможности масштабирования ВС. Архитектура NUMA систем показана на рисунке 2.



Рисунок 2 - Архитектура мультипроцессоров NUMA

У машин NUMA есть ключевые характеристики, которые отличают их от других мультипроцессоров.

· Имеются два или более узлов, каждый из которых может быть представлен процессорным элементом с кэш-памятью.

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

· Узлы соединены посредством высокоскоростной сети.

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

· Когерентность кэшей обычно поддерживается аппаратными средствами (ccNUMA), но возможен вариант без таких средств (nccNUMA).

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

1.2 Многоядерные процессоры

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

Рисунок 3 - Структура многоядерного процессора

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

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

В многоядерных процессорах каждое ядро может поддерживать технологию SMT (Simultaneous multithreading), позволяющую выполнять несколько потоков вычислений на каждом ядра. На процессорах, выпускаемых компаний Intel, данная технология называется Hyper-threading. В процессорах с поддержкой Hyper-Threading, набор регистров имеется у каждого логического процессора, но не поддерживается одновременное выполнение инструкций выборки/декодирования в двух потоках. Такие инструкции будут выполняться поочередно.

Рассмотрим пример, когда применение технологии Hyper-Threading оправдано. Предположим, что процессор выполняет поток инструкций первого логического процессора. Выполнение потока может приостановиться по одной из причин:

· произошёл промах при обращении к кэшу;

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

· ожидается результат предыдущей инструкции.

Центральный процессор при включенной поддержке Hyper-Threading не будет простаивать, а передаст управление второму логическому процессору. Следовательно, пока один логический процессор ожидает, вычислительные ресурсы процессора будут использованы другим логическим процессором.

1.3 Кэш память

На ранних компьютерах иерархия памяти была представлена три уровнями: регистры процессора, оперативная память и память на внешних носителях. Чтобы уменьшить разницу в скорости работы центрального процессора и оперативной памяти, системные инженеры приняли решение разместить на кристалле процессора маленькую SRAM память, которую они назвали кэш-памятью. Скорость обращения к кэшу первого уровня равнялся 4 тактам процессора. В дополнении к кэшу первого уровня было принято решении создать кэш второго уровня большего размера. Скорость обращения за данными хранящимися в кэше L2 равняется 10 тактам процессора. Современные процессоры включают еще больший кэш, называемый L3 кэш, находящийся между кэшем L2 и основной памятью и доступ к которому равен 50 тактам процессора. Основная структура одинакова для кэша любого уровня. [2]

1.3.1 Структура кэша

Рассмотрим компьютерную систему, где адрес памяти равен m бит и имеется M=2^m уникальных адресов. Кэш организован как массив, состоящий из S=2^s множеств. На рисунке 3.4 показан пример множественно-ассоциативного кэша.

Каждое множество состоит из кэш-линий. Каждая линия содержит блок данных размеров B=2^b байт, бит корректности, который показывает, что в кэш-линии хранится значимая информация и таг поле равное t = m - (b + s) бит. Таг поле уникально идентифицирует кэш-линию в конкретном множестве. [2]

Обычно, структуру кэша можно представить в виде кортежа (S, E, B, m). Емкость кэша вычисляется, как С = S * E * B без учета битов поля таг и бита корректности. Когда центральному процессору поступает инструкция чтения данных из памяти по адресу A, он посылает адрес A в кэш. Если в кэше хранится копия данных по адресу A, то блок данных немедленно отправляется CPU. Кэш может найти запрашиваемые данные, просто извлекая биты из адреса, подобно хэш-таблицы с чрезвычайно простой хэш-функцией. Логическое разделение адреса на составные части показана на рисунке 4.

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



Рисунок 4 - Структура множественно-ассоциативного кэша

Будем предполагать, что у нас имеется система с CPU, регистрами, кэшем первого уровня и оперативной памятью. Когда CPU выполняет инструкцию чтения данных, он запрашивает их из кэша L1. Если в кэше имеется копия запрашиваемых данных, то это cache hit и данные будут незамедлительно возвращены центральному процессору. Однако, если происходит cache miss, т.е. запрашиваемые данные отсутствуют, кэш L1 запросит копию данных из оперативной памяти. Пример промаха по кэшу показан на рисунке 3.5. Прежде чем извлечь блок данных необходимо выполнить три шага: выбрать множество, определить кэш-линию, извлечь данные.

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

Рисунок 5 - Пример возникновения промаха по кэшу

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

Множественно-ассоциативный кэш подобен кэшу прямого отображения за исключением того, что множество содержит более одной кэш-линии. Если данные имеются в кэше, то происходит cache hit, иначе cache miss. Если во множестве есть свободная линия, то данные запрошенные из оперативной памяти будут скопированы в неё. Иначе будет применен алгоритм замещения, который выберет линию, которая будет замещена. Например, политика least frequently used (LRU) замещает линию, которая наименее часто использовалась. Политика least recently used (LRU) вытесняет линию, которая не использовалась дольше всех. Алгоритм Белади, считается наиболее эффективным алгоритмом замещения, замещает ту кэш-линию, данные в которой не потребуется в течение длительного времени, как правило, на практике этот алгоритм не реализуется. Политика Random Replacement (RR) случайным образом выбирает кандидата на замещение и отбрасывает его при необходимости освободить место в кэше. Этот алгоритм не требует хранить историю обращений к кэш-линии. Из-за своей простоты использовался в процессорах ARM.

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

1.3.2 Ложное разделение данных

В симметричных мультипроцессорных системах, каждый процессора имеет локальный кэш. Система должна гарантировать согласованность данных в кэшах процессоров. Ложное разделение данных (False sharing) происходит, когда потоки, выполняющиеся на разных процессорах, изменяют переменные, которые находятся в одной и той же строке кэша. Это делает строку кэша недействительной, заставляя систему задействовать механизм когерентности кэша, что вредит производительности всей системы. [7]

Ложное разделение данных - это хорошо известная проблема, влияющая на производительность в многопроцессорных системах. На рисунке 3.7, показан пример возникновения ложного разделения данных.

Для лучшего понимания ситуации приводящей к False sharing необходимо рассмотреть реальный пример кода (см. листинг 3.1).

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

Рисунок 6 - Ситуация приводящая к False sharing

На рисунке 6, потоки 0 и 1, обращаются к переменным, которые хранятся в смежных адресах памяти и делят одну и ту же кэш-линию. Хотя потоки изменяют разные переменные, кэш-линия становится недействительной, заставляю систему обновить память для поддержки когерентности кэша. Для обеспечения согласованности данных в нескольких кэшах процессоры компании Intel реализуют алгоритм MESI. При первой загрузке строки кэша, процессора маркирует её, как строку с эксклюзивным доступом. Пока кэш-линия помечена как эксклюзивная, последующие операции с данной кэш-линией могут свободно использовать хранящиеся в ней данные. Если процессор замечает, что другим процессором используется та же кэш-линия, он помечает ее, как кэш-линию с общим доступом. Если в одном из процессоров кэш-линия помечается, как модифицированная, то для всех других процессоров она становится недействительной. Ложное разделение данных может заметно ухудшить производительность приложения. Компиляторы могут оптимизировать код, устраняя ситуацию ложного разделения данных. Но для этого необходимо скомпилировать программу с оптимизацией, иначе проблема ложного разделения данных не будет рассматриваться компилятором.

Листинг 1 - Пример кода, в котором не учитывается проблема False sharing

2. Основная часть

2.1 Взаимодействие user space с kernel space

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

Таблица 1 - Самые распространенные специальные файловые системы

Название	Точка монтирования	Описание
bdev	Нет	Блочные устройства
binfnt_misc	Любая	Различные исполняемые форматы
eventpollfs	Нет	Используется механизмом эффективного опроса событий
pipefs	Нет	Каналы
ргос	/proc	Общая точка доступа к структурам данных ядра
rootfs	Нет	Предоставляет пустой корневой каталог на этапе загрузки
shim	Нет	Области памяти, совместно используемые при межпроцессорном взаимодействии
mqueue	Любая	Используется для реализации очередей сообщений POSIX
sockfs	Нет	Сокеты
sysfs	/sys	Общая точка доступа к системным данным
tmpfs	Любая	Временные файлы (хранятся в оперативной памяти, если не выполняется подкачка)
usbfs	/proc/bus/usb	USB-устройства
devfs	/dev	Динамическая файловая система, предназначенная для управления файлами устройств

Специальные файловые системы не привязаны к физическим блочным устройствам. Однако ядро присваивает каждой смонтированной специальной файловой системе фиктивное блочное устройство, у которого старший номер равен нулю, а в качестве младшего номера берется произвольное значение (индивидуальное у каждой файловой системы). [3]

Файловая система devfs монтируется в каталог /dev. В этом каталоге размещены описание устройств системы. В ОС Linux всё рассматривается, как файл, даже такие устройства, как порты, жёсткие диски и т.д. Для всех таких устройств существует запись в каталоге /dev.

Ядро Linux предоставляет механизмы создания записей в специальных файловых системах, т.е. для взаимодействия с модулем, в момент его инициализации необходимо вызвать специальные функции, которые позволят управлять в дальнейшем модулем. Каждая файловая система /proc, /dev или /sys, предоставляет набор функций и структур данных, которые используется, для взаимодействия между пространством пользователя и пространством ядра. В рамках дипломной работы при реализации модуля, использовались возможности файловой системы devfs и procfs.

В системе Linux каждому устройству соответствует запись в каталоге /dev. Все устройства характеризуется двумя номерами: старшим номером, определяющим класс устройства, и младшим номером, указывающим внутри своего класса на конкретный экземпляр устройства.

Старший и младший номер уникально характеризуют устройства в системе. Модуль соединяется с устройством не по имени его в системе, а по старшему и младшему номеру устройства. Не запрещается использовать при регистрации устройства, заранее зарезервированные номера из файла Documentation/devices.txt, но при этом возможен конфликт с уже используемым оборудованием.

В каталоге /dev все устройства делятся на блочные и символьные. Старшие номера для блочных и символьных устройств составляют разные пространства номеров и используются независимо друг от друга.

Символьное устройство в ядре описывается структурой типа struct cdev. Данная структура объявлена в файле /linux/cdev.h. Объявление структуры struct cdev показано в листинге 1.

Листинг 1 - Объявление структуры struct cdev

Тип dev_t - используется, чтобы хранить старший/младший номер устройства.

Структура file_operations - является одной из самой значимой структуры данных. Это структура является базовой для реализации операций ввода/вывода: open(), read(), write(), close(), ioctl() и т.д.

Основной структурой данных в модели драйвера устройства является структура, называемая kobject. Объявление структуры показано в листинге 2. Объекты kobject вложены в более крупные объекты, которые называют контейнерами, они описывают компоненты модели драйвера устройства. Дескрипторы шин, устройств и драйверов являются типичными контейнерами. [3]

В каждой структуре kobject имеется поле k_name, которое не может быть пустым. Если имя объекта не больше 20 символов, то оно хранится во внутреннем массиве name. Структура kobject может быть членом множества, которая описывается структурой kset. Поле entry, является либо пустым, либо представляет двусвязный список, содержащий члены множества kset. Обе структуры kobject и kset имеют поле struct kobj_type. Данная структура представляет тип объекта и содержит методы используемые, для управления данным объектом. [3]

Листинг 2 - Объявление структуры struct kobject

Как уже говорилось, ядро использует структуры типа cdev для объявления символьных устройств. До того, как будут вызваны операции данного устройства, мы должны выделить и зарегистрировать хотя бы одну структуру данных типа cdev. Для инициализации структуры необходимо вызвать функцию cdev_init(). При вызове функции необходимо передать структуру file_operations, в которой перечислены функции ввода/вывода.

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

Чтобы удалить символьное устройство из системы, необходимо вызвать функцию cdev_del().

Обращаться к структуре cdev после передачи её в cdev_del() нельзя. В старых версия ядра Linux, например 2.6, можно увидеть, что почти все символьные устройства не пользуются интерфейсом cdev, они используют два устаревших вызова для регистрации устройства в системе, которые показаны в листинге 3.

Листинг 3 - Объявление устаревших функций регистрации устройств

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

Каталог /proc напрямую контролируется ядром Linux. Из-за того, что он предоставляет информацию, получаемую из ядра, то каждый файл в каталоге имеет нулевую длину. Если выполнить операцию чтения для какого-нибудь файла, то в терминале отобразится соответствующая информация. Это объясняется тем, что виртуальные файловые системы, регистрируются на уровне VFS (Виртуальная Файловая Система), и нет существенной разницы в работе с виртуальным файлом или обычным.

Основная структура, которая полностью описывает механизмы работы с каталогом proc, является struct proc_dir_entry, объявление структуры показано в листинге 4.

Листинг 4 - Объявление структуры

Чтобы создать запись в каталоге proc необходимо вызвать функцию proc_create(), реализация которой показана в листинге 5.

Листинг 5 - Реализация функции



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

Чтобы удалить запись из каталога proc необходимо воспользоваться функцией proc_remove().

Если возникает при реализации модуля ядра необходимость в иерархической структуре файлов и каталогов, то для этих целей в файле linux/proc_fs.h объявлены несколько функций, который показаны в листинге 6.

Листинг 6 - Объявление необходимых функций при создании каталогов



2.2 Средства синхронизации ядра Linux

Можно считать ядро неким сервером, отвечающим на запросы. Эти запросы поступают либо от процесса, выполняемого процессором, либо от внешнего устройства, генерирующего запрос на прерывание. Фрагменты кода ядра выполняются не последовательно, а вперемешку. В результате между ними может возникнуть конкуренция за ресурсы, и эту ситуацию следует контролировать с помощью соответствующих приемов синхронизации. [3]

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

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

· Атомарные переменные

· Спин-блокировки

· Последовательные блокировки

· Семафоры

· Семафоры чтения/записи

· Мьютексы реального времени

· Механизмы ожидания завершения

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

2.2.1 Реализация семафоров в Linux

Чтобы использовать семафоры код ядра должен подключить <asm/semaphore.h>. Семафоры могут быть объявлены и проинициализированы разными способами. Первый способ, создание семафора и инициализация его затем с помощью sema_init(struct semaphore *sem, int val), где аргумент val - является начальным значением семафора.

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

Листинг 7 - Объявление макросов создания мьютекса

DECLARE_MUTEX(name);

DECLARE_MUTEX_LOCKED(name);

После вызова макросов мьютекс будет объявлен с именем name и инициализирован в 1 (DECLARE_MUTEX) или в 0 (DECLARE_MUTEX_LOCKED). Мьютекс имеет заблокированное состояние, если он был инициализирован значением 0. Поэтому он должен быть явным образом разблокирован до того, как потоку будет разрешён доступ.

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

Листинг 8 - Объявление функций захвата семафора

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

Функция down_interruptible() требует дополнительные проверки при ее использовании, т.е. если операция была прервана, функция возвратит значение не равное нулю, которое нужно корректным образом обработать.

Функции down_trylock() не переходит в режим ожидания, если семафор был захвачен другим потоком и возвратит значение не равное нулю в данном случае. Если функция down() выполняется успешно в каком-либо потоке, то считается, что этот поток владеет семафором. Захват семафора, означает право на доступ к критической секции. После того, как все операции в критической секции будут выполнены, семафор должен быть разблокирован вызовом функции up().

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

2.2.2 Реализация спин-блокировок

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

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

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

Для использования спин-блокировок необходимо подключить файл <linux/spinlock.h>. Спин-блокировка описывается типом spinlock_t.

Как и все другие примитивы, спин-блокировка должна быть проинициализирована. Существует несколько вариантов инициализации, можно использовать макрос SPIN_LOCK_UNLOCKED или вызвать явно функцию spin_lock_init.

Перед тем как войти в критическую секцию поток должен захватить блокировку вызовом void spin_lock(spinlock_t *lock).

Для освобождения полученной блокировки необходимо вызвать функцию void spin_unlock(spinlock_t *lock).

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

Листинг 9 - Пример использования механизма запрета прерывания

spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;unsigned long flags;spin_lock_irqsave(&mr_lock, flags);/* критический участок кода... */spin_unlock_irqrestore(&mr_lock, flags);

Вызов spin_lock_irqsave() сохранит текущее состояние системы прерываний, запретит прерывания и попытается захватить блокировку. Функция spin_unlock_irqrestore(), наоборот освобождит блокировку и восстанавливит предыдущее состояние.

2.2.3 Реализация атомарных операций

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

Ядро предоставляет два набора интерфейсов для выполнения атомарных операций: один -- для работы с целыми числами, а другой -- для работы с отдельными битами. Эти интерфейсы реализованы для всех аппаратных платформ, которые поддерживаются операционной системой Linux. Большинство аппаратных платформ поддерживают атомарные операции или непосредственно, или путем блокировки шины доступа к памяти при выполнении одной операции (что в свою очередь гарантирует, что другая операция не может выполниться параллельно). Это как-то позволяет справиться с проблемой в случае аппаратных платформ, таких как SPARC, которые не поддерживают базовых машинных инструкций для выполнения атомарных операций. [4]

Средства выполнения атомарных операций с целыми числами работают с типом данных atomic_t. Вместо того, чтобы использовать функции, которые работают непосредственно с типом данных int языка Си, по ряду причин используется специальный тип данных. Во-первых, функции, которые выполняют атомарные операции, принимают только аргументы типа atomic_t, это гарантирует, что атомарные операции выполняются только с данными этого специального типа. В то же время это также гарантирует, что данные этого типа не смогут передаваться в другие функции, которые не выполняют атомарных операций. [4]

Объявления всех атомарных операций, находятся в заголовочном файле <asm/atomic.h>. Для некоторых аппаратных платформ существуют дополнительные возможности, которые характерны только для конкретной платформы. Основные методы и макросы для работы с атомарными операциями перечислены в таблице 2. Атомарные операции реализуются, как встроенные функции с ассемблерными вставками.

Таблица 2 - Полный список целочисленных атомарных операций

Атомарная операция	Описание
ATOMIC_INIT(int i)	Инициализировать атомарную переменную значением i
int atomic_read(atomic_t *v)	Считать значение атомарной переменной
void atomic_set(atomic_t *v, int i)	Присвоить атомарной переменной значение i
void atomic_add(int i, atomic_t *v)	Увеличить значение атомарной переменной на i
void atomic_sub(int i, atomic_t *v)	Уменьшить значение атомарной переменной на i
void atomic_inc(atomic_t *v)	Инкрементировать значение на 1
void atomic_dec(atomic_t *v)	Декрементировать значение на 1
int atomic_sub_and_test(int i, atomic_t *v)	Вычесть значение i с v и проверить, не равно ли значение атомарной переменной нулю
int atomic_add_negative(int i, atomic_t *v)	Сложить значение i с v и проверить, не является ли значение отрицательным
int atomic_dec_and_test(atomic_t *v)	Декрементировать значение на 1 и проверить, не равно ли значение атомарной переменной нулю
int atomic_inc_and_test(atomic_t *v)	Инкрементировать значение на 1 и проверить, не равно ли значение атомарной переменной нулю

2.3 Очереди ожиданий Linux

При реализации модуля ядра возникла необходимость в использовании блокируемого ввода/вывода. Если мы считываем информацию из модуля ядра, то может возникнуть ситуация, приводящая к ожиданию запрашиваемых данных. Такую ситуацию нужно корректно обработать, либо вернуть признак ошибки, либо ожидать пока данные не станут доступны. В Linux есть множество вариантов реализации ожидании какого-либо события, например, примитив синхронизации называемый “механизм ожидания завершения”. В рамках дипломной работы, используются возможности очередей ожидания реализованных в ядре Linux. Данный механизм существует ещё с версии ядра 2.4 и при переносе на более старые платформы требует меньше исправлений в исходном коде.

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

Рисунок 7 - Очередь ожиданий в ядре версии 2.4

Объявление и инициализация очереди показана в листинге 10.

Листинг 10 - Пример объявления и инициализации очереди

Очередь можно инициализировать во время компиляции используя специальный макрос DECLARE_WAIT_QUEUE_HEAD (my_queue). Как только очередь ожидания объявлена и проинициализирована процесс может использовать ее, чтобы ожидать конкретного события. Процесс может заснуть, вызвав один из вариантов sleep_on(), в зависимости от того, как долго процесс будет ожидать и может ли он быть прерван при появлении прерывания.

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

Прерываемый вариант interruptible_sleep_on() работает так же, как sleep_on(), за исключением того, что процесс может быть прерван сигналом. Данная функция, использовалась разработчиками ядра, прежде чем появился вызов wait_event_interruptible().

Листинг 11 - Объявление функций переводящих процесс в состояние ожидания

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

2.4 Связанные списки ядра Linux

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

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

Списки должны быть проинициализированы перед использованием с помощью макроса INIT_LIST_HEAD или с помощью LIST_HEAD. Большинство функций для работы со списками определены в заголовочном файле <linux/list.h>.

Листинг 12 - Объявление структур используемых при реализации потокобезопасной очереди



Рисунок 8 - Структура данных list_head

Макрос list_add(struct list_head *new, struct list_head *head) добавляет новую запись сразу же после головы списка, т.е. в начало списка. Таким образом, она может быть использована для создания стеков.

Макрос list_add_tail(struct list_head *new, struct list_head *head) добавляет элемент new перед головой списка, т.е. в конец списка. Данная функция может быть использована для создания очередей.

Макросы list_del(), list_del_init() удаляют запись из списка. Если потребуется, чтобы запись была вставлена в другой список, необходимо использовать list_del_init(), которая инициализирует заново указатели связного списка. Макросы list_move() и list_move_init() удаляют запись из своего текущего списка и добавляют ее в начало головы.

Пример реализации макроса list_entry() в ядре linux, показан в листинге 13.

Листинг 13 - Реализация макроса list_entry

Макрос list_entry() развернется в следующую запись, как показано в листинге 14, если использовать его для структуры queue_t.

Листинг 14 - Пример вызова макросы для структуры queue_t

Прием из листинга 4.14 широко известен. Используя указатель на поле типа struct list_head, макрос list_entry() вычисляет начальный адрес самой структуры. Чтобы выполнить такой расчёт, необходимо рассчитать смещение struct list_head от начало структуры. Потом вычисляется смещение члена типа struct list_head по отношению к переданному указателю.

Реализация потокобезопасной очереди на основе применения структуры list_head

Очередь создается посредством вызова функции queue_create(), которая в первую очередь выделяет память для «головы» очереди типа queue_t, а затем инициализирует спин-блокировку, вызывая функцию spin_lock_init().

Чтобы поместить в очередь элемент необходимо вызвать функцию queue_enqueue() передав в качестве первого аргумента указатель на очередь, а вторым аргументом сам элемент. Элемент помещается в конец очереди при помощи вызова list_add_tail(). Перед тем, как добавить элемент в очередь, захватывается блокировка. Реализация данной функции показана в листинге 15.

Листинг 15 - Реализация функции

Чтобы извлечь из очереди элемент необходимо вызвать функцию queue_dequeue(). Перед тем как извлечь элемент, нужно получить указатель на структуру типа queue_item_t при помощи макроса list_first_entry(), данный макрос вычисляет смещение структуры типа struct list_head в структуре queue_item_t и возвращает указатель на начало структуры queue_item_t.

queue_enqueue()

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

Листинг.16 - Реализация функции

queue_dequeue()

void* queue_dequeue(queue_t *q)

{

queue_item_t *queue_item;

void *item;

if (queue_is_empty(q))

return NULL;

queue_lock(q);

queue_item =

list_first_entry(&(q->list), queue_item_t, list);

item = queue_item->item;

list_del(&(queue_item->list));

kfree(queue_item);

queue_unlock(q);

return item;

}

Для захвата блокировки вызывается функция queue_lock(), а для освобождения queue_unlock(). Реализация функций показана в листинге 17.

Листинг 17 - Пример реализации функции queue_lock() и queue_unlock()

2.5 Реализация модуля ядра в Linux

Перед тем как будут вызваны операции чтения/записи модуля ядра, необходимо с начало открыть файл в каталоге dev. При загрузке модуля вызывается функция инициализации mcva_init(), в которой осуществляется инициализация ресурсов и создается запись в каталоге /dev. В нашем случае модуль зарегистрирован под именем mcva. Во время системного вызова open() в модуле ядра происходит инициализация всех дополнительных структур данных, которые будут использоваться в дальнейшем. Например, инициализация потокобезопасной очереди происходит именно при открытии файла. Реализация функции open() в модуле ядра, показана в листинге 18.

Листинг 18 - Пример реализации функции open()

int mcva_open(struct inode *inode, struct file *file)

{

icva_t *__module;

__module = kmalloc(sizeof(icva_t), GFP_KERNEL);

if (__module == NULL)

return -ENOMEM;

if ((__module->data_queue = queue_create()) == NULL)

return -ENOMEM;

initialization_icva(__module);

file->private_data = __module;

return 0;

}

Для взаимодействия пользовательского пространства и пространства ядра были реализованы две основные функции - это чтение и запись данных из модуля. Чтобы увеличить производительность и сократить время выполнения операции записи, было принято решения использовать в ядре потокобезопасную очередь. Выше было сказано, про то, что операции ввода/вывода должны быть блокирующими. Данную возможность можно реализовать, воспользовавшись очередями ожиданий. Если пользовательский процесс вызывает операцию чтения и очередь пуста, то процесс ожидает до тех пор, пока не выполнится операция записи. Как только выполняется операция записи, атомарно устанавливается флаг, сигнализирующий о том, что данные доступны. Возможна ситуация, когда одновременно будут выполняться две операции чтения из файла /dev/mcva. Чтобы избежать гонки за данными в начале вызова операций ввода/вывода осуществляется захват семафора посредством вызова down_interruptible(), а в конце его освобождение с помощью вызова функции up().Реализация операции записи, показана в листинге 19.

Листинг 19 - Пример реализации операции записи

static ssize_t mcva_bwrite(struct file *file,

const char __user *buf, size_t count, loff_t *f_pos)

{

int ret;

in_data_t *input_data;

icva_t *__module = file->private_data;

if (down_interruptible(&__module->semwrite))

return -ERESTARTSYS;

if ((input_data =

kmalloc(sizeof(in_data_t), GFP_KERNEL)) == NULL) {

printk(KERN_DEBUG

"<%s> kmalloc failed\n", __func__);

up(&__module->semwrite);

return -ENOMEM;

}

if (copy_from_user(input_data, buf, count)) {

up(&__module->semwrite);

return -EFAULT;

}

if ((ret =

queue_enqueue(__module->data_queue,

(void *)input_data)) < 0) {

printk(KERN_DEBUG

"<%s> queue_enqueue failed\n", __func__);

up(&__module->semwrite);

return ret;

}

if (atomic_read(&__module->readiness_read) == 0) {

atomic_set(&__module->readiness_read, 1);

wake_up_interruptible(&__module->readq);

}

up(&__module->semwrite);

return count;

}

Ядро операционной системы располагается в своем собственном адресном пространстве, как и все пользовательские процессы в системе. При копировании данных из пространства пользователя в пространство ядра необходимо использовать специальные функции copy_to_user(), copy_from_user().

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

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

При закрытии файла в каталоге /dev в модуле ядра вызывается функция mcva_release(), которая освобождает все ресурсы, которые был выделены во время вызовы функции open. Реализация функции release() показана в листинге 20.

Листинг 20 - Пример реализации функции release()

2.5 Обход каталогов страниц

Каждый выполняющийся процесс в ядре представлен структурой task_struct. Данную структуру называют дескриптором процесса. Структура, описывающая процесс имеет большие размеры и хранит всю необходимую информацию, а именно указатель на список используемых виртуальных страниц, текущее состояние процесса, число открытых файлов, указатель на процесс родитель при вызове функции fork и т.д. Виртуальное пространство процесса описывается структурой типа mm_struct. Чтобы отслеживать области памяти каждого процесса, в ядре реализована структура vm_area_struct, которая хранит их в виде двусвязного списка областей, причем две области никогда не пересекаются. Начало каждой области указано в переменной vm_start, а конец области в переменной vm_end. Область, выделенная для процесса, может быть доступна, как для чтения или для записи. Следует отметить тот факт, что даже если область была выделена процессу, в действительности физической страницы памяти может не существовать.

Каждый процесс в системе указывает на свой собственный каталог PGD (Page Global Directory). Каталог состоит из записей типа pgd_t. Тип является архитектурно зависимым и объявлен в файле <asm/page.h>. Для архитектуры x86, процесс копирует значение, хранящееся в переменной mm_struct->pgd в регистр cr3, что приводит к сбросу TLB буфера. Каждая активная запись в каталоге PGD указывает на страничный фрейм, который хранится в каталоге PMD (Page Middle Directory). В данном каталоге каждая запись представлена типом pmd_t, которая в свою очередь указывает на страничный фрейм, содержащийся в каталоге PTE (Page Table Entries). Все записи в данном каталоге представлены типом pte_t, где каждая запись фактически указывает на действительные пользовательские данные. В случае, если страница была выгружена на жесткий диск, запись о данной странице будет сохранена в каталоге PTE. Во время вызова функции do_swap_page() информация о выгруженной странице будет найдена в каталоге PTE. Иерархия каталогов страниц показана на рисунке 9.