Дедупликация страницы исполняемого кода драйверов OC Windows (1187398), страница 9
Текст из файла (страница 9)
Покажем это на примере. Пусть вдрайвере есть функция, которая выполняет последовательно операции записи на дверазличные страницы его кода. Тогда, с точки зрения моего драйвера, этот драйвер привызове этой функции будет посылать запрос на запись в эти две страницы почтиодновременно. И если в какой-то момент времени будет приходить запрос на запись впервую из этих страниц, то с довольно большой вероятностью (зависящей от того, изкаких еще мест этого драйвера будут выполняться операции записи в эти страницы) ковторой странице тоже будет приходить запрос на запись в этот же момент времени. Такимобразом эти две страницы драйвера не могут считаться независимыми. Поскольку,изначально о драйвере нет никакой информации, то нельзя считать его страницынезависимыми.
Однако, можно считать и независимыми в совокупности.Утверждение, что страницы не независимы, привело бы к тому, что Пуассоновскийпроцесс в данной модели необходимо было бы заменить на процесс восстановления. Чтосделало бы вычисления слишком громоздкими.Однако, если предположить, что вызовы функций драйвера системой можнорассматривать как независимые, то можно пересчитать математическую модель для кол48ва различных вызовов, и умножать получившееся кол-во страниц на выборочное среднеекол-ва страниц, в который драйвер делает запись при одном вызове.492.3.3.3. Время до первой записи как случайная величинаРассмотрим случай, когда у каждого из N одинаковых независимых драйвероввсего одна станица: L=1.Изначально (в момент времени) в памяти находится одна общая для всехстраница, копируемая при записи.
Когда от i-го драйвера к ней приходит запрос на запись(write(i)), странички разделяются и в памяти появляется новая страница, доступная длязаписи, но видимая только i-му драйверу. Теперь он будет обращаться к ней напрямую.Процесс заканчивается, когда все N драйверов будут иметь свои копии этой страницы.Событием будем считать поступление первого запроса на запись от i-го драйвера,всего за все время работы произойдет N событий. Кол-во событий произошедших за времяt обозначим K(t).Обозначим- время, в которое пришел запрос на запись от i-го драйвера, то естьмомент наступления события.
Для каждого драйвераожиданиеи функцию распределения- случайная величина, мат, которой можно приближенно найти изстатистических данных, собранных за время нескольких запусков системы.Получается, что есть N случайных величин , независимых, одинаковораспределенных, с функцией распределения.Нужно найти:1. Сколько событий произойдут к определенному моменту времени? Это нужно длятого, чтобы принять решение о целесообразности объединения страниц вслучае Pageable Writable.Ищем мат ожидание кол-ва событий.2. Найти вероятность того, что несколько событий произойдут почтиодновременно. То есть интервалы между ними будут настолько малы, чторезервный буфер не будет успевать заполняться. Это нужно для случаяNonPageable, Writable для корректировки размеров буфера.Ищем вероятность того, что более чем k событий произойдут на интервалеменьшем ε, где ε определяется исходя из времени, которое нужно системе,чтобы заполнить резервный буфер..501) Вероятность того, что ровно k из N событий произойдут за время t, обозначимP(K=k,t).Таким образом, где- числосочетаний из n по k.Мат ожидание.2) Вероятность того, что ровно k из N событий произойдет на временном отрезкеобозначим P(K=k,,).Следовательно,Обозначим.
При n>100 и nA(1-A)>20 можно воспользоватьсятеоремой Муавра-Лапласа.3) Вероятность того, что больше или ровно k из N событий произойдет навременном отрезке, обозначим P(K≥k,).4) Коллизией из k событий назовем момент, когда k событий попали на временнойотрезок длиной < ε.51P(∃ хоть одна коллизия из k событий) ≅5) P(∃ коллизия из 2-х событий, когда N=2) =. Здесь учтено, что случайнаявеличина непрерывна (т.к. это временя), и формула полной вероятности.
(Длядискретной случайной величины эта формула выглядела бы так:). Можно обобщить на случай коллизии k из N событий. Опуская длинные выкладки,приходим к формуле:522.3.3.4. Пуассоновский процессФункцию распределения F( ) можно получать либо чисто из экспериментальныхданных (статистическая функция распределения), либо можно получить ее вид изтеоретических соображений с точностью до неизвестных параметров.
Этот параграфпосвящен именно этому.Как и в предыдущем случае, рассматривается 1 драйвер обращающийся к своейединственной странице. Но в отличие от предыдущего случая, не будем ограничиватьсятолько его первым обращением. Рассмотрим его обращения как случайный процесс. Тоесть событие - это запись в станицу. События происходят через случайные промежуткивремени, и они независимы.Как видим, обращения драйвера к своей странице это Пуассоновский процесс, оесть процесс с независимыми приращениями. В данном случае интенсивностьПуассоновского процесса λ не известна, и берется из экспериментальных данных. Онаокажется разной для разных драйверов, и вообще говоря, может зависеть от времени.1) Пуассоновский процессλ - интенсивность - мат ожидание числа событий в единицу времени.MK(t)=λt.2) Распределение интервала времени T между событиями.
Для Пуассоновскогопроцесса оно имеет показательный закон распределения:где Т - время между двумя событиями.Функция плотности распределения имеет вид:.MT=1/λ, DT=Таким образом, выражениеможно использовать в качестве теоретической функции распределения времени допервого вызова.53542.3.3.5. Модификация Пуассоновского процесса.Пуассоновский процесс довольно неплохо описывает механизм обращениядрайвера к своим страницам, но в данном случае важно только первое обращение.Другими словами, на самом деле, до первого события общий процесс представляет собойсумму N пуассоновских процессов с одинаковыми интенсивностями (если по 1 страницена драйвер), после наступления первого события, тот простейший процесс в котором онопроизошло исключается из рассмотрения, так как больше не сможет сгенерироватьсобытие, то есть это уже будет сумма N-1 процессов и т.д. пока все страницы неразъединятся.Пусть одновременно и независимо происходят N простейших потоков.
Тогда общая сумма числа событий в этих потокахcявляется Po(λt) cПуассоновский процесс с переменной интенсивностью. В общем случае этопроцесс с заданной (неслучайной) λ(t). Здесь же рассмотрим только случай с кусочнопостоянной λ. Пусть N простейших пуассоновских процессов независимы и происходятпоследовательно на непересекающихся отрезках.
Тогда суммарное число событий, гдеД-во:Таким образом, реальный процесс в системе может быть представлен по аналогии спуассоновским процессом с переменной интенсивностью с кусочно постоянными λ. Но онне будет уже являться пуассоновским процессом, так какзависит не от времени, а откол-ва наступивших событий.Такое представление оно дает возможность посчитать вероятность коллизий.Например, коллизии из двух элементов на k-м шаге. Итак, считаем, что у каждого изпростейших процессов, составляющих общий процесс, интенсивность =начале она =, потомТогда,.55, в самом2.3.3.6. Итоги.В рамках математической модели "разделения" страниц при записи были полученыследующие формулы.Математическоеожиданиеколичествасобытий,которыепроизойдуткопределенному моменту времени:гдефункцияраспределениясчитаетсяпоформулеОно необходимо для того, чтобы в случае Pageable страниц принять решение об их"объединении", а так же для для того, чтобы правильно расчитывать размер резервногобуфера страниц.При реализации учитывалось, что формула для распределения получена исходя изпредставления данного процесса Пуасоновским, то есть имеет приближенный вид.
Былсозданметод,прикотором,еслиразмербуфераприближаетсякзначению,предсказанному в рамках математической модели, например, становится разным 75%, тонеобходимо увеличить буфер в 2 раза.Вероятность того, что несколько событий произойдут почти одновременно. То естьинтервалы между ними будут настолько малы, что резервный буфер не будет успеватьзаполняться. То есть вероятность того, что более чем k событий произойдут на интервалеменьшем ε, где ε определяется исходя из времени, которое нужно системе, чтобызаполнитьрезервныйбуфер..56Этот результат необходим для случая NonPageable, Writable для корректировкиразмеров буфера и частоты работы подкачивающей нити, добавляющей в него страницы.В реализации опять же учтен приближенный характер выражений.
Если эта вероятностьстановится больше определенного значения, то увеличивается размер буфера, и нитьначинает чаще проверять, не нужно ли добавить страниц.Следует отдельно отметить, что несмотря на то, что для приближенныхвычисленийиспользуетсяформулаполученная в рамках приближения реального процесса Пуассоновским, сами формулыдля математического ожидания и вероятности коллизии были выведены без привязки копределенному типу распределения случайной величины - времени до первого обращенияк странице.
Следовательно, в качестве F(t) можно подставить статистическую формулураспределения, полученную в ходе большого количество экспериментов.Однако, поскольку математическая модель используется лишь для приближеннойоценки, а получение статистических функций для каждой страницы каждого драйверавесьма затруднительно, было решено ограничиться приближением с Пуассоновскимпроцессом.572.4.
Тестирование и сравнение результатов с математической моделью2.4.1. Сбор статистикиВо-первых, проанализируем, как распределяются страницы по типам. Это даетвозможность судить об итоговых выигрышах, а так же еще раз доказывает актуальностьисследования.Были проанализированы ~300 драйверов, установленных на моем рабочемкомпьютере. На диаграмме – усредненные данные.Были получены следующие результаты:Всего драйверов = 320, всего их страниц = 22480, то есть 87Мб памяти, из них:Code = 13220, Data = 9260, что равняется примерно 59% и 41% соответственно.Распределение страниц по типам:ТипcnprcnpwcprcpwdnprdnpwdprdpwСтрани 9567цы453320020517038831493843%2%14%0%23%17%1%0%где c - код, d - данные, p - pageable, np - nonpageable, w - writable, r - nonwritable.58Максимальное число доступных для записи NonPageable страниц было = 7, аименно, в драйверах http.sys и ntfs.sys.