Автоматический поиск состояний гонок в ядре OC Linux (1187393)
Текст из файла
Министерство образования и науки Российской ФедерацииМосковский физико-технический институт (государственный университет)Факультет управления и прикладной математикиКафедра информатикиКоновалов Андрей ДмитриевичАвтоматический поиск состояний гонокв ядре ОС Linux03.04.01 — Прикладные математика и физикаВыпускная квалификационная работа магистраНаучный руководитель:к.ф.-м.н. Хорошилов Алексей ВладимировичДолгопрудный2016 г.Содержание1 Введение32 Состояния гонок52.1Неопределенное поведение .
. . . . . . . . . . . . . . . . . . . . . . . . .62.2Поиск состояний гонок . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.2.1Алгоритм Lockset . . . . . . . . . . . . . . . . . . . . . . . . . . .92.2.2Алгоритм Happens-before . . . . . . . . . . . . . . . . . . . . . . . 113 Обзор динамических детекторов143.1Применение детекторов . . . .
. . . . . . . . . . . . . . . . . . . . . . . . 143.2Внутреннее устройство детекторов . . . . . . . . . . . . . . . . . . . . . 153.33.2.1Теневая память . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2.2Инструментация . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 163.2.3Библиотека времени исполнения . . . . . . . . . . . . . . . . . . . 17Существующие детекторы в пространстве ядра . . . . . . . . . . . . . . 174 Детектор KernelThreadSanitizer4.119Устройство детектора KernelThreadSanitizer . . . . . . . . . . . . . . . .
194.1.1Теневая память . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.1.2Инструментация . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.1.3Аннотации примитивов синхронизации . . . . . . . . . . . . . . . 214.1.4Обработка обращения к памяти . . .
. . . . . . . . . . . . . . . . 254.1.5Поиск ошибок в планировщике . . . . . . . . . . . . . . . . . . . 274.1.6Отчеты об ошибках . . . . . . . . . . . . . . . . . . . . . . . . . . 284.2Производительность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3Найденные ошибки . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 315 Заключение3221ВведениеПри написании программ разработчики часто допускают различные ошибки.Такие ошибки могут приводить к неправильному или непредсказуемому поведениюпрограмм: замедлению скорости работы, аварийному завершению исполнения, порчеданных и т.п..
Результатом подобного поведения могут быть большие экономическиепотери и даже гибель людей [1].Даже при отсутствии ошибок в написанной разработчиком программе во времяее выполнения все равно могут произойти ошибки. Виной этому могут быть ошибкив каком-либо из компонентов операционной системы, в том числе в ее ядре. Ядрооперационной системы Linux является одним из самых больших и сложных проектовс открытым исходным кодом на текущий момент.
Поиск и исправление ошибок в ядреявляется актуальной задачей, поскольку в настоящее время система Linux лидируетна рынках смартфонов, интернет-серверов и суперкомпьютеров [2].Ошибки могут быть разных типов: ошибки в логике работы программы, ошибки синхронизации потоков, ошибки работы с памятью и т.п. Поиск ошибок вручнуюне всегда бывает эффективен. Например, ошибки могут наблюдаться очень редкоили не проявляться какое-то время после того, как они произошли. Для решенияэтой проблемы процесс поиска ошибок можно автоматизировать. В данной работерассматривается автоматический поиск состояний гонок в ядре Linux. Согласно исследованию ИСП РАН [3], среди типовых ошибок в ядре наиболее часто встречаютсяименно состояния гонок.Для автоматического поиска ошибок в существующих программах, используются специальные приложения, которые называются детекторами (англ.
detectors).Детекторы ошибок в основном разделяются на статические и динамические [4]. Статические детекторы анализируют исходный код программы, не осуществляя ее запуск. Иногда простые статические детекторы встроены прямо в компилятор, которыйвыдает предупреждения во время компиляции программы. Напротив, динамическиедетекторы анализируют поведение программы по мере ее исполнения и обнаруживают ошибку, только если она в действительности произошла.Недостатками статического анализа является большая вычислительная сложность и низкая точность. Часто поиск нетривиальных ошибок статическим анализомс достаточной точностью возможен только для отдельных изолированных модулей3программы и требует особой организации ее исходного кода [5]. К недостаткам динамического анализа относится необходимость наличия тестов, возникающая вследствие того, что обнаружение ошибки происходит только во время исполнения кода,который ее содержит.В рамках данной работы был выбран динамический анализ, поскольку существенное редактирование и реорганизация исходного кода ядра Linux (более 15 млн.строк кода на языке C) за разумное время представлялись невозможными.
Однакопоскольку при работе ядра исполняется лишь ограниченный набор драйверов (исполняются только драйвера, отвечающие за работу присоединенных к тестирующемукомпьютеру устройств), обнаружение ошибок с помощью динамических детекторовв драйверах является затруднительным.В большинстве современных операционных систем ядро операционной системыи программы пользователя имеют разные привилегии, т.е.
обладают разными правами на исполнение инструкций, чтение памяти и т.п. В операционной системе Linuxразличают два режима выполнения пользовательского процесса: режим ядра (англ.kernel mode) и режим пользователя (англ. user mode). Процесс начинает выполнениев режиме пользователя. Когда процесс производит обращение к операционной системе, режим выполнения процесса переключается с режима пользователя на режимядра: операционная система пытается обслужить запрос пользователя, возвращаякод ошибки в случае неудачного завершения операции.В дальнейшем детекторы, которые ищут ошибки в приложениях пользователя,будем называть детекторами ошибок для приложений пользователя или детекторами ошибок в пространстве пользователя, а детекторы, которые ищут ошибки вядре и его компонентах, – детекторами ошибок для ядра или детекторами ошибокв пространстве ядра.Сейчас существует несколько довольно эффективных и точных детекторов состояний гонок в пространстве пользователя [6, 7].
Однако существующие детекторысостояний гонок в пространстве ядра обладают рядом ограничений. Они могут тестировать лишь отдельные компоненты ядра, а также обладают большим количествомложных срабатываний и неудобны в использовании. Цель данной работы: разработка нового метода поиска состояний гонок для ядра Linux, применимого для всегокода ядра.42Состояния гонокОдними из самых распространенных, опасных и трудноуловимых ошибок в мно-гопоточных программах являются состояния гонок.Определение. Состоянием гонки (англ. data race) называется ситуация, когда два или более потока исполнения программы могут одновременно осуществитьдоступ к одной области памяти (например, переменной) и как минимум один изэтих доступов является записью.Считается, что любые два доступа к памяти из двух потоков могут произойтиодновременно, если обратное не гарантируется применяемой в программе дисциплиной синхронизации.Следует отметить, что в англоязычной литературе существует два различныхпонятия, которые на русский язык переводятся как состояние гонки [5].
Одно изних, называемое “race condition”, относится к недетерминированности исполненияпараллельных процессов. Другое, более узкое, называемое “data race”, относится кчастному случаю недетерминизма, возникающему в многопоточных программах принеправильной работе потоков с разделяемой памятью (англ. shared memory) и соответствует определению выше.Состояние гонки является серьезной ошибкой программирования – такие ошибки могут приводить к нарушению целостности данных и аварийному завершениюпрограммы. Подобные ошибки бывает очень трудно найти, так как они происходятлишь при определенных условиях, которые зачастую сложно воспроизвести специально, даже если знать эти условия – например, особая последовательность переключений исполнения двух потоков.Состояния гонок приводят к негативным последствиям вследствие двух причин.Во-первых, результат исполнения программы с состояниями гонок может зависетьот того, в каком порядке инструкции программы исполняются различными потоками.
Такую ситуацию бывает чрезвычайно трудно воспроизвести при использованииобычных способов отладки. Во-вторых, компилятор при оптимизации кода программы с состоянием гонки может преобразовать его таким образом, что он становитсяочевидно ошибочным [8].Существует понятие так называемых безобидных состояний гонок (англ. benign5data race).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
