Ядро 3ОС. Модель памяти и потоков

Что в данном документе

В данном документе собраны мнения, высказанные подгруппой разработки ядра в конференции. Информация взята из архива переписки за 2003 г.

Процессы и потоки

Необходимо научиться грамотно использовать страничное преобразование и постараться отказаться от использования модели процессов по образу и подобию Win32 и Linux - один процесс - все адресное пространство. Перейдя к схеме "максимальное кол-во потоков в одном адресном пространстве", перестаем каждый раз свопить потоки на диск при минимуме ОЗУ, перестаем инвалидировать TLB при каждом переключении.

Тут все просто, если в системе присутствуют потоки a, b, c, то по схеме один поток - одно адресное пространство, при переключении задачи происходит инвалидация в буфере трансляции тех линий которые не фиксированы. Всего 32 страницы по 4К каждая - итого 128К.

При применении указанной выше схемы во всем адресном пространстве не получится держать более чем одного потока, так задача позиционной независимости кода одними страницами не решается. А значит, подобная модель навязывает нам непланируемые расходы памяти на избыточные страницы (наборы страниц) под каждый поток. Это усугбляется в Win32 DLL, которые болтаются всегда с определенного глобального адреса и должны быть в каждом потоке непременно. При такой системе любое переключение задачи - частиная инвалидация TLB. Часть TLB на ядро и DLL остается фиксированным. При таком режиме работы TLB вообще не нужен, он не успевает набрать в себя и 30% адресов за квант работы потока, а если и набирает то использует их от силы дважды - один раз во время набора, второй при повторе адреса! А дальше - шлеп ему в CR3, и он все это богатство - на ветер.

Если мы видим, что TLB при фиксации покрывает планер потоков (часть ядра) + совокупный размер всех активно работающих потоков (код), зачем дергать TLB? Фиксируем весь TLB, заранее собирая страницами все потоки в одно линейное пространство (можно и не собирать) и сегментами разруливаем позиционную независимость кода в каждом потоке. Постепенно вытесняем менее активные потоки в часть не фиксированную в TLB.

Соответственно, получаем кэш-промахи на этих участка - ну так и потоки менее активны. Зато то, что работает на максимале, действительно как сыр в масле. При размере потока в 10К и ядра 28К (хрен с ним, закроем все ядро), получаем 128 - 28 = 100К / 10 = 10. Десять потоков с максимальной отдачей по самым извращенным подсчетам. На дрова видео и звука хватит, на что еще? Ты в Винде более чем 8 реально работающих с максимальной отдачей потоков видел?

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

Это от огромной лени - набрать каждый поток по 4 Гб страницами и толкать при каждом переключении задачи в CR3 новый каталог. Чего проще-то может быть? Или тут тоже применим принцип максимально быстрой разработки кода? Так у нас вроде академическая разработка и торопиться нам на "Комтек" не нужно.

Есть поток, инкапсулирующий в себя пространство(а) кода и пространство(а) данных. И данные, и код такого потока подлинковываются к нему по мере необходимости в LDT. Если такой подход кого-то конкретно не устраивает (обращение к таким подлинкованным пространствам без потери DS -> COMMON DATA возможен только через пересохранение последнего, либо сменой префикса доступа к сегменту данных), то он может выбрать связку Expand и Include в одно пространство. Далее называем совокупность локальных пространств данных и кода - потоком. Защита потока максимальная, четырехуровневая, на платформе 0x86 - это предел по аппаратной защите потока

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

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

В случае реализации схемы потоков Win32 получается так, что множество потоков должны быть размещены с одного и того же линейного адреса (так как сегментов для привязки кода к локальному 0 нет), наборы страниц таких потоков вынуждены использовать страницы разных физических адресов для создания заданной геометрии потока + DLL. Мы же даже в одну страницу сможем уложить, например, 4 потока по 1024 байта каждый. В TLB это даст всего одну линию фиксации, а позицию кода в таких потоках разрулит сегментная модель - дав каждому свой 0.

Учитывая вышеприведенное, можно назвать такую схему размещения потоков (по существу, все потоки в одном каталоге страниц) "множество потоков - одно глобальное линейное адресное пространство". В случае же схемы Win32 (думаю, что и Linux) получается столько каталогов страниц, сколько потоков в системе, и фиксацией тут ничего не выиграть. Необходимо использовать как можно меньше фиксаций линий в TLB, так как потоки в такой системе растут как на дрожжах (не меньше страницы, а все, что меньше, с подачи MS называемое потоком, я бы побоялся использовать - защиты ноль, переключение контекста усилием программисткой воли всего штата MS).

Таким образом, поток процесса- это совокупность адресных пространств и системных объектов, связанных единым планируемым, неделимым исполнением. В случае псевдопараллельности системы, в которой работают потоки, исполнение производится порционально (квантованно).

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

Распределение памяти

Организация списка и метаданные

Сегменты - списки. Каталоги страниц - списки. Просто блоки - списки. ММ абсолютно все равно, управляет ли она "аппаратно" защищенными сегментами или просто блоками. Это всего лишь просто "регионы", а задача ММ эффективно управлять регионами: сегментами, страницами, блоками. Их размер и правила выравнивания - частная задача.

Например, нужно выделить область равную странице - 4096 ни больше, ни меньше, а куда девать 12 байт метаданных, относящихся к выделяемому блоку? Добавить в начало блока? Тогда для использования останется 4084 байт, к тому же данные для использования никогда не будут выровнены. Добавить в конец - тоже не лучше. Если вынести метаданные в другое место, вопрос с выравниванием решается довольно просто и повышается "быстродействие" класса.

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

Выделить, когда класс THeap не вступил в работу можно, только напрямую указав адрес последней глобальной переменной плюс ее размер (LastVariable - последняя глобальная переменная):

pc_Heap = &LastVariable + sizeof(LastVariable);

Хотя может быть так:

   // Список переменных модуля start32
   c_Kernel pc_Krnl3OS;
   THeap pc_Heap;
   char bLastVariable; // последняя неинициализированная переменная

Далее во всех модулях без исключения запрещены объявления статических и глобальных переменных (только локальных - стековых).

..........(){
   .........
   // Инициализация THeap
   pc_Heap = &bLastVariable;
   .........
   }

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

Релокация

В Linux есть полезная команда ps. Если система загружена "достаточно" "для любителя", в системе существует порядка 80 потоков. Но! 95% из них "спят". Таким образом, в списке потоков "на планирование" есть 4-5 элементов. Если система обслуживает большее количество потоков, например, Apache, то что же делать, нужно - значит нужно. Во всяком случае, список - самая быстрая реализация.

Другое мнение:

  ....{
  void *next, *pred;
  };

Теперь что нужно сделать, чтобы добраться до класса, на который указывает next или pred:

  mov r0, mem:[next] // получим значение указателя
  mov r1, mem:[r0+offset(next)] // получим значение поля следующего класса
  mov r1, mem:[r1+offset(next)] // получим значение поля следующего класса
  .... обработка ....

Таким образом, для получения доступа к 10-му элементу списка необходимо десять раз читать из памяти, причем адреса классов могут различаться весьма сильно (зависит от времени их создания) в итоге давая неэффективную работу кэша данных - т. е. вариант, когда класс будет находится за пределами кэша вполне вероятен.

• Вариант А

  Реализация монолитным списком, когда в памяти данные класса следуют непосредственно за данными класса, очень сложна, но весьма быстра:
  

    mov r0, mem:[start_list_addr + sizeof(class_element)*N_class]

• Вариант Б

  Есть еще один метод, когда существует монолитный список указателей на классы по порядку:

    *class1, *class2, *class3 ..... *classN

  Доступ к N классу также быстр:

    mov r0, mem:[start_list_ptr + sizeof(ptr)*N] // получим значение указателя N
    mov r1, mem:[r0] // получим класс N

Релокация для раздвижки сдвижки таких монолитных списков будет достаточна трудоемка, но при наличии пейджинга (MM) можно решить проблему выделением связки страниц физически закрытой RAM + сторожевой (т. е. не закрытой RAM). В итоге по исключению ловить выход за предел при размещении нового элемента списка и подставлять еще одну физически закрытую страницу.

Прелесть варианта А в том, что до выполнения релокации работа с таким списком будет на порядок быстрее - так как он весь попадет в кеш процессора. На релокацию будет затрачено время (выделение страницы или перемещения всего списка в непрерывный участок памяти с новым адресом), но потом, до следующей релокации - опять быстрая работа с классами. 

Выделение памяти можно свести к двум естественным необходимостям потоков и ядра в памяти.

• выделение памяти
• изменение характеристик уже выделенной памяти

Потоки выступают в этом случае как объекты ядра.

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

Момент состоит в следующем - очевидно, что увеличение до определенного предела буфера TLB (буфера трансляции адреса) будет приводить к тому что скорость работы потоков в системе с трансляцией адреса возрастет, но увеличивать его до бесконечности бессмысленно, да и дорого. Бессмысленно, потому что в системе с многозадачной направленностью работы код потока не может занимать более 30-40% его общей величины ОЗУ, а абсолютный размер потоков относительно реального объема ОЗУ и того меньше - 10%-20%. Естественно, что в этом случае TLB приблизительно такой участок трансляции адреса и покрывает.

При использовании в системе страничного преобразования необходимо как можно реже инвалидировать переменную часть TLB, фиксированную же часть линий TLB нужно отдать ядру и интенсивно используемым библиотекам уровня ядра. Останется очень мало линий, и если при этом начать все время "ломать" адресное пространство (инвалидируя TLB), простой на ожидание преобразования адреса будет неприемлем для embedded в основном из за того, что будет практически непрогнозируем, да и для настольных систем тоже. Именно поэтому я призываю все сообщество 3ОС рассматривать пейджинг только как часть возможностей по управлению памятью (никак не потоками!!!!), а именно ее релокацией и изменением размера.

Значит, пейджинг в 3ОС будет в основном загружен следующими задачами:

1. Релокация участков адресных пространств для уменьшения или увеличения размеров в памяти
2. Организация виртуальной памяти, т. е. подмена содержимого участков адресных пространств
3. Организация релокаций в целях IPC или УД

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

Адресные пространство (класс пространств) рассматривать необходимо только в ключе первичного выделения памяти в куче ядра и его уничтожения. Адресные пространства достаточно примитивны и необходимы потокам как средство хранения в них данных или кода, причем для потока адресное пространство обеспечивает исключительно локальную точку отсчета адреса или как раньше говорили свой сегмент кода. Локальность точки отсчета приводит к таким возможностям как:

1. Исключения позиционной независимости кода из требований к коду потока.
2. Возможность запуска потоков, представляющих собой потоки чужих ОС в родном адресном пространстве. Конечно, возможность эта становится достаточно эфемерной с удалением рабочей границы кода от нулевого адреса. Пример потоки работающие под Win32 в адресах 0x40000000 могут быть запущены в 3ОС при длине их кода менее 0xFFFFFFFF-0x40000000. Но такая возможность существует без преобразования адреса при реверс инж. и эвристическом анализе кода.
3. Возможность размещения в адресном пространстве процессора максимально возможного кол-ва потоков без изменения геометрии адресного пространства при переключении задачи.
4. Канал (pipe) - очередь команд процессора. Выполнение каждой команды разбивается на несколько фаз(по количеству исполнительных модулей процессора - N): дешифрирование команды, загрузка операндов, выполнение команды, сохранение результатов. Таким образом, команда выполняется за N-циклов процессора. Размер канала равен N.
5. Конвейер - набор исполнительных модулей процессора работающих параллельно и объединенных в виде шины. Дешифрование команды, загрузка операндов и выполнение команды происходит в начале цикла процессора, а сохранение результатов в конце. Если не удается сохранить изменения во внешней памяти в течение 1 цикла, модуль формирования адреса делает это в последующих циклах.

RR очереди потоков

Реализация на базе двунаправленного списка должна быть не хуже (по производительности) чем циклический двунаправленный список (ЦДС), это минимум.

Аргументы:

• Объект потока нужно быстро "изымать" из работы планировщика, когда его нужно "усыпить". Ставить флажок, что поток спит не эффективно. Например, в системе работают 500 потоков (это вполне реальная вещь) и если для усыпления используется флажок, планировщику придется пробегать по всем спящим потокам. ЦДС с этим справляется достаточно эффективно
• Когда придет время пробудить поток (это может сделать соответствующий драйвер или подсистема ядра), его нужно быстро "поставить на планирование". ЦДС это также достаточно эффективно решает
• Изъятые из планирования потоки могут включаться в локальные ЦДС - не нужно плодить лишних структур - плюс единообразная система работы с объектами ядра

IPC

Поток в ядре 3ОС может иметь несколько сегментов данных, возьмем за правило предоставлять дескриптор LDT для потока №2 как пространство данных IPC.

Изначально дескриптор указывает на область данных величиной 1 байт (хотя под данное пространство стандартно и его размер больше), при записи в данную область методом потока SendIPC, произойдет выход за границу, который будет отработан исключением #GP. Соответственно, пространство IPC будет расширено, и поток, которому посылался IPC будет уведомлен о том, что его ожидает сообщение IPC по второму дескриптору LDT. Второй дескриптор LDT потока приемника будет перестроен на эту область памяти. После подтверждения потоком приемника его дескриптор IPC будет снова указывать на 1 байт. Поток-получатель будет приведен к 1 байту в зависимости от асинхронности или синхронности сообщения. При наличии асинхронного IPC и последующего обращения в дескриптор IPC будет произведено выделение памяти под новый IPC.

Отправитель сообщения определяется:

Исходя из структуры самого сообщения, если s_Message

 struct s_Message{
  s_MID s_MsgID; // уникальный ID, который должен генерироваться централизованно.
  s_UID s_ResiverID;
  s_UID s_SenderID;
  dword sizeBody;
  char Body[k_PageSize - sizeof(s_UID)*2 - 4];
  };

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

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