Честное планирование дискового ввода-вывода с учетом разделяемых ресурсов файлового кэша (1187435), страница 3
Текст из файла (страница 3)
В оригинальной формулировке GPS предполагает, чтораспределяемый ресурс является непрерывным. Т.к. запросы ввода-вывода к дискуявляются дискретными и имеют в общем случае произвольный размер, необходимопостроение некоторой аппроксимации GPS.В качестве примеров простейших аппроксимаций GPS можно привести алгоритмыWRR (Weighted Round Robin), DRR (Deficit Round Robin) и WFQ (Weighted Fair Queueing).Их общая идея состоит в выделении каждому процессу очереди запросов и обходе этихочередей в некотором порядке. Во время обхода планировщик исполняет некотороеколичества запросов из каждой из этих очередей в соответствии с логикой алгоритма,общей пропускной способностью и заданными весами процессов.Рассматриваемые далее честные алгоритмы планирования являются развитиемданных простых алгоритмов.3.3.2.
Алгоритм CFQ – Completely Fair QueueingПланировщик CFQ является основным планировщиком в современных версияхОС Linux и выставлен планировщиком по умолчанию во многих дистрибутивах этой ОС.Однако,впоследниегодынекоторыедистрибутивы,предназначенныедляпользовательских систем, в частности, Ubuntu, начали отказываться от него в пользу болеепростых планировщиков, таких как deadline.10Алгоритм CFQ является развитием идеи Round Robin. Процессам с дисковойактивностью выделяются некоторые кванты времени, в течение которых планировщикисполняет только запросы из очереди текущего процесса. Частота выдачи процессу квантавремени определяется его весом. В конце исполнения каждого кванта планировщикнекоторое время ожидает прихода новых синхронных запросов, что решает т.н. проблемуdeceptive idleness («обманчивое бездействие»).
Она заключается в том, что процесс ссинхронной дисковой активностью не может отправить следующий запрос ввода-вывода,пока не будет исполнен предыдущий. С точки зрения алгоритма планирования такойпроцесс может выглядеть неактивным.Благодаря предоставлению процессам эксклюзивного доступа к диску в течениекоротких промежутков времени достигается высокая степень локальности обращений кдиску, т.к. данные отдельно взятого процесса обычно располагаются на иске близко друг кдругу. В результате достигается высокая суммарная производительность диска.Один из основных и наиболее очевидных недостатков CFQ с точки зрения честностираспределения ресурсов диска является следующая его особенность. Даже при честномраспределении времени эксклюзивного доступа к диску распределение битрейтов можетоказаться нечестным, т.к.
пропускная способность диска меняется со временем припереходе планировщика от одного процесса к другому. Рассматриваемый далее алгоритмпланирования BFQ данного недостатка не имеет.3.3.3. Алгоритм BFQ – Budget Fair QueueingПринципиальным отличием данного алгоритма от ранее рассмотренного CFQявляется то, что он выделяет процессам не кванты времени, а т.н.
бюджеты. Планировщикпредоставляет текущему активному процессу эксклюзивный доступ к диску, пока процессне исчерпает выделенный ему на данном шаге бюджет. Таким образом, планировщик наоснове BFQ получает те же преимущества локальности обращений к диску, что и CFQ, нопри этом может обеспечить более честное распределение битрейтов процессов в случаеразличнойпропускнойспособностидискавовремяисполнениязапросовотразных процессов.Активный процесс выбирается на каждом шаге алгоритма на основании заданныхвесов процессов, а также уже полученного ими «сервиса» – количества байт, записанныхна диск и прочитанных с диска.
Для выбора активного процесса используетсявспомогательный алгоритм WF2Q+ (Worst-case Fair Weighted Fair Queueing). Измененияразмеровбюджетовпроизводятсяисходясоответствующих процессов.11изтекущейдисковойактивностиПриведем краткое описание вспомогательного алгоритма WF2Q+, используемого длявыбора активного приложения. Изначально данный алгоритм был разработан дляпланирования отправки пакетов в сетях передачи данных, и шаг алгоритма состоял ввыборе следующего пакета для отправки. При использовании в рамках BFQ алгоритмWF2Q+ на каждом шаге выбирает следующий активный процесс. Таким образом, рольпакета здесь играет совокупность запросов, исполняемых за период активности,суммарный размер которых равен бюджету процесса.Алгоритм использует понятие виртуального времени (virtual time), измеряемого вбайтах и соответствующего количеству полученного сервиса на данный момент реальноговремени.
Системное виртуальное время равно суммарному количеству сервиса,полученного всеми приложениями в системе. Виртуальное время процесса равноколичеству сервиса, деленному на вес приложения.Приложениям, имеющим непустую очередь запросов к диску, присваиваютсявеличины virtual start time, и virtual finish time, которые пересчитываются при вставкепроцесса в очередь ожидающих доступа к диску и при получении процессом некоторогоколичества сервиса. «Подходящими» называются процессы, для которых virtual start timeменьше системного виртуального времени. В качестве активного выбирается тот процессиз «подходящих», который имеет наименьшее значение virtual finish time.
В результате стечением времени процессы получают объемы сервиса, пропорциональные их весам.3.4. Файловый кэшВ современных операционных системах для ускорения работы с более частоиспользуемыми файлами использует файловый кэш – промежуточный буфер воперативной памяти, содержащий фрагменты файлов с диска, которые могут бытьзапрошены пользовательскими процессами с наибольшей вероятностью. Доступ к даннымв файловом кэше осуществляется на несколько порядков быстрее, чем к данным на диске,но его объем на несколько порядков меньше, причем он ограничен не только объемомоперативной памяти в системе, но и другими факторами, связанными с его реализацией вконкретных ОС. Очевидно, что наличие файлового кэша оказывает значительное влияниена производительность дисковой подсистемы, т.к.
большая часть операций с файламиосуществляется приложениями именно кэшированным образом.Наряду с кэшированием файлов в современных ОС существует механизмотображения файлов в память (memory mapped files). Процесс может работать с файлом,отобразив его в свое адресное пространство, при этом обращаясь к данным по12виртуальному адресу. При этом чтение данных из файла в память происходитпосредством страничной ошибки (page fault) при первом обращении к ним, а записьявляется отложенной.Кэширование файлов в современных ОС, в частности, в Windows и Linux, такжереализовано на основе отображения файлов в память. Приведем краткое описаниемеханизмов файлового кэша в ОС Windows. Для кэша выделены определенные диапазоныядерных адресов, отображение файлов в которые описывается т.н.
картой кэша(cache map) с гранулярностью 256 килобайт. Для каждого кэшированного фрагментафайла создается его отображение в соответствующий диапазон ядерной памяти, и чтениеэтого фрагмента с диска в кэш происходит путем вызова page fault-а. Помимо чтенияданных в кэш непосредственно по запросу от приложения реализован механизмопережающего чтения (read ahead) – система заранее считывает с диска фрагментыфайлов,которыесбольшойвероятностьюбудутзапрошеныприложениемв ближайшее время.Запись на диск измененных фрагментов кэшированных файлов происходит либоотложенным образом (write behind или write back), либо сразу после изменения(write through).
Для механизма write behind в системе выделены специальные ядерныепотоки, сканирующие файловый кэш в поисках измененных страниц и осуществляющиеих сброс на диск. При этом в случае, например, неожиданного отключения питаниявозможна потеря пользовательских данных. Механизм write through же позволяетприложениям убедиться в том, что их данные действительно записаны на диск.3.5.
Аппаратный дисковый кэшВ современных жестких дисках и SSD-дисках применяется аппаратный дисковыйкэш – промежуточный буфер между собственно жестким диском и использующей егооперационной системой, физически расположенный на самом устройстве диска. В немхранятся данные, которые были недавно считаны с диска или записаны на диск.Перечислим основные преимущества, даваемые наличием дискового кэша. Увеличение скорости чтения данных с диска за счет кэширования наиболее частоиспользуемых данных и применения механизмов опережающего чтения. Ускорение записи за счет того, что контроллер диска сообщает ОС о завершенииоперации записи сразу же после ее прихода.
Для обеспечения надежности при этомдиском предоставляется возможность принудительного сброса данных и механизмwrite through.13 Совмещение скоростей передачи данных на физическом носителе информации и наинтерфейсе ввода-вывода диска. Обеспечение возможности исполнения диском нескольких операций одновременно(с точки зрения ОС).Наличие аппаратного дискового кэша оказывает значительное влияние напроизводительность работы системы с диском. Для увеличения утилизации дисковогокэша планировщик дисковой активности должен учитывать его наличие. Иначе возможныситуации, когда планировщик задерживает запросы ввода-вывода, которые могли быпопасть в кэш и быть исполнены значительно быстрее.
Реализация такого учетаосложняется тем фактом, что дисковый кэш является «прозрачным» для операционнойсистемы – на уровне ОС нет никакой информации о том, присутствует ли конкретныйдиапазон данных в дисковом кэше. Это приводит к необходимости построениявероятностных моделей для получения такой информации на основании предыдущихопераций ввода-вывода. В рамках данной работы данная задача не решается, однако онаявляется естественным ее продолжением и остается в качестве одной из возможностейдальнейшего развития.144. Проблема учета разделяемых ресурсов файлового кэша вдисковом планировщикеВ этом разделе мы более подробно опишем проблему учета файлового кэша валгоритмах планирования доступа к диску, рассматриваемую в данной работе.Мы обсудим два отдельных фактора этой проблемы: нечестность распределения самого ресурса файлового кэша; наличие в нем разделяемых между многими процессами данных.Далее мы приведем результаты тестов, демонстрирующих проявление этихфакторов, а также некоторые примеры проявления проблемы нечестности доступа кфайловому кэшу в реальных системах.
Кроме того, проведем обзор аналогичнойпроблемы, возникающей в задачах контроля за использованием физической памятипроцессам и группами процессов в операционных системах, а также предлагаемыхпутей ее решения.4.1. Проблема нечестного распределения ресурса файлового кэшаВ современных операционных системах файловый кэш принято считать общимсистемным ресурсом. В частности, в ОС Windows, на которую в первую очередьориентирована данная работа, файловый кэш «принадлежит» ядру системы в целом, и неведется никакого учета его использования отдельными процессами. В результатевозможнаситуациянечестногораспределенияресурсафайловогокэшамеждуотдельными процессами в системе. Равноправные с точки зрения выделенных ресурсовфизической памяти и пропускной способности диска процессы (или группы процессов)могут получать разные объемы файлового кэша.Рассмотрим классическую (применяемую, в частности, в ОС Windows и ОС Linux)схему управления рабочим набором (working set) файлового кэша – набором страницфизической памяти, занимаемой кэшированными данными.
Для вытеснения странициспользуется алгоритм LRU (Last Recently Used) – ведется список страниц памяти,упорядоченный по времени последнего доступа к странице. В момент, когда нужновытеснить страницу, выбирается та, которая наиболее давно использовалась. При этомсписок является общим на всю систему, в отличие от множества различных списков длярабочих наборов отдельных процессов.15Более того, ОС Windows файловый кэш является частью общего системногорабочего набора, в который входит также вся остальная физическая память, используемаяядром системы. Таким образом, в случае, например, возникновения паузы виспользовании кэшированных файлов некоторым процессом (или группой процессов)соответствующиестраницыизрабочегонаборафайловогокэшаоказываютсявытесненными, и в результате этот процесс получает меньшую долю ресурсафайлового кэша.4.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
