СИСТЕМА И СПОСОБ РАСПРЕДЕЛЕНИЯ ПАМЯТИ ВО ВСТРОЕННЫХ СИСТЕМАХ ИЛИ СИСТЕМАХ БЕСПРОВОДНОЙ СВЯЗИ
SYSTEM AND METHOD OF ALLOCATING MEMORY IN EMBEDDED SYSTEMS OR WIRELESS COMMUNICATION SYSTEMS

По настоящей заявке испрашивается приоритет предварительной патентной заявки США № 61/041878, поданной 2 апреля 2008 г.
Область техники
Настоящее изобретение, в целом, относится к области распределения памяти и, более конкретно, к распределению памяти во встроенных системах или системах беспроводной связи.
Предшествующий уровень техники
Служба распределения памяти использует пулы элементов памяти. В некоторых случаях элементы памяти сортируются по различным пулам, основываясь на размере элемента памяти. Например, один пул может состоять из множества малых элементов памяти, тогда как другой пул может состоять из относительно небольшого количества больших элементов памяти. В ответ на запросы распределения памяти соответствующий элемент данных может быть выбран из конкретного пула и возвращен запрашивающему объекту. Эта система приводит к существенной пустой трате ресурсов памяти и процессора. Например, при малых элементах памяти отношение заголовка к полезной нагрузке является высоким, что приводит в результате к неэффективному использованию памяти. Дополнительно, когда элементы всей памяти распределены, значительные фрагменты данных любого конкретного элемента данных могут оставаться неиспользованными. Кроме того, в этих службах распределения недоступно никакое статистическое мультиплексирование. Ресурсы процессора также расходуются из-за формирования цепочек из многочисленных малых элементов памяти.
В системах беспроводной связи пакеты часто сегментируются на малые, с фиксированным размером, пакеты "радиолинии", например, 40 байтов, для обеспечения надежной радиопередачи. Для эффективного использования памяти один из подходов состоит в том, чтобы создать большой пул из относительно малых элементов памяти, каждый из которых хранит 40-байтовый блок, которые, в конечном счете, могут образовывать цепочку на более высоких уровнях для формирования больших блоков данных (например, 1500-байтовые IP-пакеты). Один из недостатков такой службы состоит в том, что некоторое пространство может быть потрачено впустую, потому что элементам памяти придется выравниваться по строкам кэша (32 или 64 байта), которые могут не соответствовать малому размеру пакета радиолинии. Кроме того, различные технологии могут совместно использовать один и тот же пул элементов памяти, чтобы уменьшить общий объем памяти, и в этом случае размер полезной нагрузки элемента памяти должен быть выбран так, чтобы соответствовать наибольшему размеру пакета радиолинии, что может дополнительно увеличивать потери производительности.
КРАТКОЕ ИЗЛОЖЕНИЕ СУЩЕСТВА ИЗОБРЕТЕНИЯ
В одном из вариантов осуществления представлена система, обеспечивающая управление памятью. Система содержит процессор и службу управления памятью, которая выполняется на процессоре. Служба управления памятью сконфигурирована с возможностью создания первых элементов памяти, причем каждый из первых элементов памяти содержит заголовок и полезную нагрузку, причем полезная нагрузка сконфигурирована с возможностью сохранения множества независимо распределенных участков памяти, а заголовок первых элементов памяти ссылается на распределяемое пространство в полезной нагрузке, создания вторых элементов памяти, причем каждый из вторых элементов памяти содержит заголовок, ссылающийся на один или более участков памяти в полезной нагрузке первых элементов памяти, и возвращения ссылки из любого заголовка первого или второго элемента памяти, чувствительного к запросу распределения памяти.
В другом варианте осуществления представлен способ управления памятью. Способ содержит этапы, на которых распределяют первые элементы памяти, причем каждый из первых элементов памяти содержит первый заголовок и полезную нагрузку, причем полезная нагрузка содержит участки независимо распределяемой памяти, а первый заголовок содержит ссылку на нераспределенную память в полезной нагрузке, распределяют вторые элементы памяти, причем каждый из вторых элементов памяти содержит второй заголовок, причем второй заголовок содержит ссылку на распределенный участок памяти в полезной нагрузке первого элемента памяти, принимают запросы для распределения памяти и отвечают на запросы для распределения памяти посредством возвращения ссылки из заголовка первого или второго элемента памяти.
В другом варианте осуществления представлена система управления памятью. Система содержит средство распределения первых элементов памяти, причем каждый из первых элементов памяти содержит первый заголовок и полезную нагрузку, причем полезная нагрузка содержит участки независимо распределяемой памяти, а первый заголовок содержит ссылку на нераспределенную память в полезной нагрузке, средство распределения вторых элементов памяти, причем каждый второй элемент памяти содержит второй заголовок, причем второй заголовок содержит ссылку на распределенный участок памяти в полезной нагрузке первого элемента памяти, средство приема запросов для распределения памяти и средство ответа на запросы для распределения памяти посредством возвращения ссылки из заголовка первого или второго элемента памяти.
В другом варианте осуществления предложен машиночитаемый носитель, закодированный компьютерными командами. Команда, при ее выполнении, обеспечивает осуществление процессором этапов, на которых распределяют первые элементы памяти, причем каждый из первых элементов памяти содержит первый заголовок и полезную нагрузку, причем полезная нагрузка содержит участки независимо распределяемой памяти, а первый заголовок содержит ссылку на нераспределенную память в полезной нагрузке, распределяют вторые элементы памяти, причем каждый второй элемент памяти содержит второй заголовок, причем второй заголовок содержит ссылку на распределенный участок памяти в полезной нагрузке первого элемента памяти, принимают запросы для распределения памяти и отвечают на запросы для распределения памяти посредством возвращения ссылки из заголовка первого или второго элемента памяти.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
В дальнейшем изобретение поясняется описанием предпочтительных вариантов воплощения со ссылками на сопроводительные чертежи, на которых:
фиг.1 изображает структурную схему примера мобильного устройства;
фиг.2 изображает структурную схему примера элементов памяти;
фиг.3 изображает структурную схему другого примера элементов памяти;
фиг.4A и 4B изображают блок-схему примера способа распределения памяти;
фиг.5 изображает блок-схему последовательности операций различных примеров выполнения службы распределения памяти;
фиг.6 изображает блок-схему последовательности операций другого примера способа распределения памяти.
ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ
Последующее подробное описание направлено на конкретные варианты осуществления изобретения. Изобретение, однако, может быть осуществлено множеством различных путей. Должно быть очевидным, что приведенные здесь аспекты могут осуществляться в широком разнообразии форм, и что любая конкретная структура, функция или и то, и другое, раскрытые здесь, являются просто примерами воплощения. На основе представленных здесь результатов специалист в данной области техники должен понимать, что любой раскрытый здесь аспект может быть осуществлен независимо от любых других аспектов, и что два или более этих аспектов могут объединяться различными способами. Например, устройство может быть осуществлено или способ может быть реализован, используя любое количество аспектов, изложенных здесь. Кроме того, такое устройство может быть осуществлено или такой способ может быть реализован, используя другую структуру, функциональные возможности, или структуру и функциональные возможности в дополнение к одному или более чем к одному аспектам, изложенным здесь.
Мобильные устройства для работы обычно используют службы распределения памяти. Здесь описываются способы и устройства для уменьшения общего объема памяти, требующегося различным подсистемам в мобильном устройстве, и уменьшения ресурсов для обработки, расходуемых мобильным устройством. Ниже представлены некоторые архитектуры, которые могут использоваться вместе с описанными способами и устройствами.
На фиг.1 представлена структурная схема примера мобильного устройства 102. Устройство 102 содержит процессор 202, осуществляющий связь с запоминающим устройством 204, и сетевой интерфейс 206 для связи через беспроводную линию 106. Как вариант, устройство 102 может также включать в себя одно или более устройств 210 отображения, устройство 212 ввода пользователя, такое как клавиатура, сенсорный экран или другое подходящее тактильное устройство ввода данных, громкоговоритель 214, содержащий преобразователь, выполненный с возможностью обеспечения акустического выхода, основываясь на сигнале, принятом по беспроводной линии 106, и/или микрофон 216, содержащий преобразователь, выполненный с возможностью обеспечения ввода акустического сигнала, который может быть передан по беспроводной линии 106. Например, телефон может включать в себя устройство 210 отображения, выполненное с возможностью обеспечения визуального выхода графического интерфейса пользователя (GUI).
Сетевой интерфейс 206 может включать в себя любую подходящую антенну (не показана), приемник 220 и передатчик 222 так, чтобы устройство 102, как пример, могло связываться с одним или более устройствами по беспроводной линии 106. Как вариант, сетевой интерфейс 206 может также иметь возможности обработки для снижения требований к обработке для процессора 202.
Как вариант, устройство 102 может включать в себя второй сетевой интерфейс 208, который осуществляет связь по сети 110 через линию 108. Например, устройство 102 может обеспечивать возможность связи с другой сетью 110 (например, глобальной сетью, такой как Интернет) через проводную или беспроводную линию связи. Соответственно, устройство 102 может дать возможность другим устройствам 102 (например, станции Wi-Fi) получать доступ к другой сети 110. Кроме того, следует понимать, что одно или более устройств 102 может быть портативным или, в некоторых случаях, относительно непортативным. Второй сетевой интерфейс 208 может передавать и принимать радиочастотные сигналы в соответствии со стандартом IEEE 802.11, включающим в себя IEEE 802.11(a), (b) или (g), стандартом BLUETOOTH и/или CDMA, GSM, AMPS, или другие известные сигналы, которые используются для связи внутри беспроводной сотовой телефонной сети. Кроме того, второй сетевой интерфейс 208 может содержать любой подходящий проводной сетевой интерфейс, такой как Ethernet (IEEE 802.3), USB или MDDI.
Устройство 102 может включать в себя батарею 231 для обеспечения электропитания одного или более компонентов устройства 102. Устройство 102 может содержать, по меньшей мере, одно из телефона, смартфона, персонального цифрового помощника (PDA), ультрамобильного персонального компьютера (UMPC), мобильного Интернет-устройства (MID) или любого другого мобильного устройства. В частности, содержащиеся здесь результаты могут быть использованы (например, осуществлены в рамках или выполнены) во множестве устройств 102.
Описанные здесь компоненты могут осуществляться различными способами. Со ссылкой на фиг.1, устройство или оборудование 102 представляется как последовательность взаимодействующих функциональных блоков, которые могут представлять функции, осуществляемые, например, процессором 202, программным обеспечением, некоторой их комбинацией или некоторым другим способом, как описано здесь. Например, процессор 202 может облегчить пользователю ввод через устройства 212 ввода данных. Дополнительно, передатчик 222 может содержать процессор для передачи, обеспечивающий различные функциональные возможности, относящиеся к передаче информации на другое устройство 102. Приемник 220 может содержать процессор для приема, который обеспечивает различные функциональные возможности, относящиеся к приему информации от другого устройства 102, как описано здесь.
Процессор 202 также осуществляет связь со службой 203 распределения памяти. В одном варианте осуществления служба 203 распределения памяти работает на процессоре 202. Служба 203 распределения памяти отвечает на запросы памяти от одной или более подсистем, работающих в устройстве 102. Способ и порядок работы службы 203 распределения памяти будут описаны более подробно здесь ниже.
Как отмечено выше, на фиг.1 показано, что в некоторых аспектах эти компоненты могут быть осуществлены через соответствующие компоненты процессора. Эти компоненты процессора могут быть осуществлены в некоторых аспектах, используя, по меньшей мере, частично, описанную здесь структуру. В некоторых аспектах процессор может быть выполнен с возможностью осуществления части или всех функциональных возможностей одного или более этих компонентов. В некоторых аспектах один или более компонентов, представленных пунктирными прямоугольниками, являются необязательными.
В одном или более примерах вариантов осуществления описанные функции могут быть осуществлены аппаратным обеспечением, программным обеспечением, встроенным программным обеспечением или любой их комбинацией. При осуществлении с помощью программного обеспечения функции могут быть сохранены или передаваться посредством одной или более команд или кода на машиночитаемом носителе данных. Машиночитаемый носитель включает в себя как компьютерный носитель данных, так и среду передачи, включающую в себя любую среду передачи, облегчающую передачу компьютерной программы из одного места в другое. Носители данных могут быть любыми доступными носителями, к которым может получать доступ универсальный или специализированный компьютер. Для примера, но не для ограничения, такие машиночитаемые носители могут содержать оперативное запоминающее устройство (RAM), постоянное запоминающее устройство (ROM), электрически стираемое программируемое постоянное запоминающее устройство (EEPROM), компакт-диск CD-ROM или другой оптический дисковый накопитель, магнитный дисковый накопитель или другие магнитные запоминающие устройства или любой другой носитель, который может использоваться для переноса или хранения желаемого средства управляющих программ в форме команд или структур данных, и к которым может быть получен доступ посредством универсального или специализированного компьютера или универсального или специализированного процессора. Кроме того, любое соединение должным образом упоминается как машиночитаемая среда. Например, если программное обеспечение передается с веб-сайта, сервера или другого удаленного источника, использующего коаксиальный кабель, оптоволоконный кабель, витую пару, цифровую абонентскую линию (DSL) или беспроводные технологии, такие как инфракрасное излучение, радиоволны и микроволновое излучение, то коаксиальный кабель, оптоволоконный кабель, витая пара, DSL или беспроводные технологии, такие как инфракрасное излучение, радиоволны и микроволновое излучение, содержатся в определении среды. Магнитные и немагнитные диски, используемые здесь, включают в себя компакт-диск (CD), лазерный диск, оптический диск, цифровой универсальный диск (DVD), дискету и диск по технологии Blu-ray, где магнитные диски обычно воспроизводят данные магнитным способом, тогда как немагнитные диски воспроизводят данные оптически с помощью лазеров. Комбинации вышеуказанных дисков также должны входить в число машиночитаемых носителей.
В соответствии с одним аспектом службы распределения памяти, малые блоки памяти упакованы в большие блоки фиксированного размера (называемые "элементы DSM"). Для каждого из малых блоков поддерживается слежение за использованием элементов "DUP" (дубликат), которое показывает полезную нагрузку внутри DSM. Поскольку элементы DSM имеют ограниченный размер и все блоки внутри DSM, как можно предположить, имеют примерно одинаковый ограниченный срок службы, нет необходимости проводить фрагментацию свободной памяти внутри каждого DSM. Преимущество этого заключается в том, что использование памяти может быть значительно уменьшено, так как только небольшая часть памяти внутри DSM тратится впустую, но при некоторой доле сложности других способов распределения памяти с высокой эффективностью упаковки. Другой способ представления состоит в том, что это гибрид служб распределения с фиксированным размером и гибким размером, где общая память распределяется по блокам фиксированного размера, но в пределах блоков допускаются распределения с гибкими размерами, потому что гибкие распределения, как ожидается, будут иметь короткий срок службы.
В одном аспекте основной блок памяти называют элементом DSM. В нем содержится раздел заголовка и раздел полезной нагрузки. Когда блок данных должен быть сохранен в памяти, выделяется новый элемент DSM, и данные копируются в раздел полезной нагрузки DSM. Дополнительно, заголовки обновляются, чтобы отразить начало и длину данных. Если длина данных превышает размер раздела полезной нагрузки, многочисленные элементы DSM могут соединяться вместе в цепочку в связанный список.
Дополнительно определяется специальный тип элемента DSM, обозначенный как DUP ("дубликат"). DUP использует ту же самую структуру заголовка, что и обычный DSM, но он не имеет собственного раздела полезной нагрузки. Вместо этого он может указать на раздел данных в другом месте, например, внутри обычного DSM. Чтобы проследить, сколько DUP указывают на данные в одном и том же элементе DSM, существует поле заголовка, обозначенное "ref_count", которое отсчитывает количество ссылок на этот элемент DSM, и в котором устанавливается единица, когда первоначальный DSM распределяется впервые. Каждый раз, когда создается новый DUP, это указывается внутри элемента DSM и значение "ref_count" увеличивается. Аналогично, когда DUP освобождается, значение "ref count" первоначального элемента DSM уменьшается. Таким способом алгоритм распределения может знать, когда элемент DSM может быть фактически свободен, что происходит только тогда, когда никакие другие DUP не указывают на раздел полезной нагрузки этого пакета, что происходит, когда значение "ref_count" возвращается обратно на ноль.
DUP могут использоваться для разбивки пакетов, реорганизации данных, удаления заголовков и т.д., без необходимости затрагивания первоначальных данных. Все это может быть достигнуто просто манипуляцией заголовками DSM и DUP.
В соответствии с другим аспектом способы, позволяющие упаковывать данные в один и тот же элемент DSM для улучшения эффективности памяти, могут быть направлены на некоторые из недостатков, отмеченных ранее. В соответствии с этим аспектом определяется пул больших элементов DSM. Большой размер DSM должен позволить соединить в один и тот же элемент DSM данные множества пакетов радиолинии.
На фиг.2 представлена структурная схема, показывающая элементы памяти службы распределения памяти. Служба распределения памяти может включать в себя и программный интерфейс приложения ("API"). Этот API может быть доступным для доступа подсистемам, таким как подсистемы, присутствующие в устройстве 102 API. Эта служба распределения памяти может выполняться полностью или частично процессором 202 или другим подобным устройством обработки. Дополнительно, API может формировать часть операционной системы для мобильного или беспроводного устройства, такого как устройство 102. Альтернативно, API может формировать часть программной библиотеки. На фиг.2 показан первый тип элемента 610 памяти. Этот первый тип элемента 610 памяти может упоминаться как элемент управления передачей данных ("DSM"). Альтернативно, он может упоминаться как контейнерный элемент. Эти элементы 610 памяти контейнерного типа организуются как пул 605 элементов памяти. Хотя на фигуре показан единый пул 605, следует понимать, что могут также использоваться многочисленные пулы элементов DSM. Каждый пул может характеризоваться одной или более общей характеристикой, такой как размер элемента или подсистема, обслуживаемая пулом.
На фиг.2 также представлен увеличенный вид элемента 610 памяти. Как видно на увеличенном виде, эти элементы 610 контейнерного типа содержат многочисленные разделы. Первый раздел элемента памяти может упоминаться как заголовок 615. Заголовок 615 может содержать информацию, относящуюся к остальным частям элемента 610 памяти, а также другую информацию. Второй раздел элемента 610 памяти может упоминаться как полезная нагрузка. Сама полезная нагрузка может иметь несколько распределенных частей или блоков памяти 620. Кроме того, полезная нагрузка может иметь нераспределенное или неиспользуемое пространство 625. В одном варианте осуществления полезная нагрузка содержит приблизительно 1500 байтов, размер, приблизительно необходимый для сохранения IP-пакета.
Заголовок 615 элемента 610 памяти может содержать такую информацию, как ссылка на нераспределенное пространство 625 в элементе 610 памяти. В одном примере эта ссылка принимает форму указателя, указывающего начальный адрес нераспределенного пространства 625 в элементе 610 памяти. Эта ссылка на нераспределенную память 625 в элементе 610 данных может также упоминаться как "data_ptr". Заголовок может также содержать поле, указывающее размер распределенной памяти 620. Это количество распределенного пространства может упоминаться как "используемое" пространство в полезной нагрузке. Заголовок может также содержать поле, указывающее идентификатор, который идентифицирует пул 605 памяти, связанный с элементом 610 памяти. Этот идентификатор может упоминаться как "pool_id". Заголовок может также содержать поле, указывающее количество ссылок на элемент 610 памяти. Например, как описано ниже, на элемент 610 памяти могут ссылаться другие элементы памяти. Например, на каждый из распределенных участков 610 памяти полезной нагрузки ссылается разный элемент памяти. Дополнительно, заголовок 615 элемента 610 памяти ссылается на нераспределенную часть 625 полезной нагрузки. Счет этих ссылок может использоваться, помимо прочего, для цели определения, когда элемент 610 памяти может быть освобожден и возвращен пулу 605, чтобы впоследствии быть перераспределенным. Этот счет ссылок может упоминаться как "ссылки". Заголовок 615 может также содержать одну или более ссылок на другие элементы памяти. Например, если запрашиваемый участок памяти является слишком большим, чтобы соответствовать одиночному элементу 610 памяти, ссылки в заголовке могут использоваться, чтобы указать один или более дополнительных элементов памяти, которые могут соединяться вместе цепочкой, чтобы удовлетворить запрос. В зависимости от типа элементов памяти, на которые делается ссылка, эти ссылки могут упоминаться как "pkt_ptr" или "dup_ptr". Например, pkt_ptr может сослаться на ноль или больше элементов DSM или контейнерных элементов, в то время как dup_ptr может ссылаться на ноль или больше элементов DUP. В дополнение к идентифицированным полям заголовок 615 может содержать дополнительные поля, такие как поле, определяемое пользователем, или поля, используемые для целей тестирования. Кроме того, заголовок 615 может пропускать одно или более идентифицированных полей.
На фиг.2 также показан второй тип элемента 630 памяти. Этот второй тип элемента памяти может упоминаться как дубликат или элемент памяти "DUP". Эти элементы 630 DUP содержат заголовок, подобный заголовку 615 элементов 610 контейнерной памяти. Например, элементы DUP могут иметь те же самые поля, что и заголовок элемента 615 DSM. Альтернативно, элементы DUP могут иметь больше или меньше полей. Однако эти элементы DUP не имеют своей собственной полезной нагрузки. Скорее, заголовки 630 элементов DUP содержат ссылки на контейнерные элементы памяти. В одном конкретном примере элемент 630 DUP содержит указатель, указывающий первый блок распределения памяти в распределенной части 620 элемента 610 памяти. Эти элементы 630 DUP могут также быть выполнены в одном или более пулов 640. Подобно пулам 605 контейнерных элементов могут использоваться многочисленные пулы элемента DUP. Например, на фиг.2 показаны два пула 640 и 650 элементов DUP. В одном примере каждая подсистема во встроенном устройстве или в устройстве беспроводной связи имеет свой собственный пул элементов DUP. В этом варианте осуществления пул 640 может соответствовать одной конкретной подсистеме, тогда как пул 650 может соответствовать другой подсистеме. Как видно на фиг.2, один вариант осуществления обеспечивает, что элементы DUP от отдельных пулов могут ссылаться на блоки 620 памяти в едином элементе 610 DSM.
На фиг.3 показан альтернативный вариант осуществления элементов памяти, показанных на фиг.2. Как прежде может использоваться единый пул элементов 715 DSM. Однако, на этот раз, каждый пул элементов 730 и 735 DUP, соответственно, ссылается на распределенные части разных элементов 725 и 720 DSM. Как описано выше, элементы DSM могут возвращаться в пул 715 DSM для перераспределения, как только все ссылки в полезной нагрузке будут освобождены. Однако когда многочисленным подсистемам разрешается иметь ссылки DUP в одном и том же элементе DSM, может происходить фрагментация. Например, вся память, распределенная первой подсистеме в конкретном DSM, уже могла быть освобождена. Однако если на малый блок все еще делается ссылка посредством DUP от другой подсистемы, остающаяся память в полезной нагрузке может ожидать освобождения до тех пор, пока вторая подсистема не освободит свой малый блок памяти. Чтобы минимизировать эту проблему, каждая подсистема может иметь свои собственные ссылки DUP в своем собственном DMS. Таким путем, сроки службы распределенных частей памяти в конкретном DSM, вероятнее всего, будут одинаковыми. Схожесть сроков службы будет приводить к уменьшению фрагментации.
На фиг.4A и 4B показан вариант осуществления способа 780 распределения памяти. Этот способ 780 может выполняться как служба, работающая на процессоре, таком как процессор 202. Способ 780 облегчает прием запросов распределения памяти и возвращение ссылок на распределенную память. Как описано ниже, конкретная назначенная ссылка может быть функцией текущей ситуации распределения памяти для запроса подсистемы и размера запрашиваемого блока памяти. Дополнительно следует заметить, что некоторые из этапов могут быть опущены, чтобы удовлетворить требования или специальные требования конкретного приложения. Дополнительно следует отметить, что некоторые из описанных здесь этапов являются оптимизациями и, таким образом, могут выборочно использоваться или быть опущены по усмотрению разработчика системы.
Способ 780 начинается, когда служба распределения памяти на этапе 785 получает запрос памяти. Как часть запроса памяти запрашивающая подсистема может указать запрашиваемый размер памяти. Запрашивающая подсистема может также предоставить идентификатор подсистемы так, чтобы служба распределения памяти могла выбрать соответствующий элемент DSM для этой подсистемы. После приема запроса памяти служба распределения памяти определяет, является ли запрашиваемый размер меньше размера нераспределенной памяти в текущем контейнерном элементе DSM, как показано на этапе 790 принятия решения. Как обсуждалось со ссылкой на фиг.2 и 3, элементы DSM могут иметь нераспределенное пространство в разделе полезной нагрузки. Этап 790 принятия решения может быть выполнен посредством сравнения размера нераспределенной части с запрашиваемым размером. Альтернативно, так как общий размер полезной нагрузки известен, запрашиваемый объем может сравниваться с размером распределенной части полезной нагрузки. В другом варианте осуществления, вместо использования для сравнения запрашиваемого размера памяти, система распределения памяти может увеличить размер запроса так, чтобы увеличенный запрос был выровнен с границами кэша. Например, фактический запрос может быть увеличен так, чтобы получающийся в результате запрос был кратным конкретному размеру строки кэша, такому как 16, 32, 64 или 128 байт. Независимо от этого, если запрашиваемый размер памяти или ее увеличенная выровненная версия вписывается в нераспределенную часть, способ переходит к этапу 800.
На этапе 800 принятия решения система распределения памяти определяет, превышает ли запрашиваемый размер плюс размер ранее распределенной части текущего элемента DSM первый порог. Например, если полезная нагрузка DSM составляет приблизительно 1500 байтов длины, порог может составить 1200 байтов. Соответственно, система распределения памяти должна определить, превышает ли размер уже распределенной памяти плюс размер запрашиваемой памяти 1200-байтовый предел. В одном варианте осуществления порог может быть выбран как определенный процент от размера полезной нагрузки элемента DSM. Например, порог может составить приблизительно 70%-80% размера полезной нагрузки. В другом варианте осуществления размер порога может быть выбран, чтобы отразить характеристики размера общего запроса, такие как запросы памяти для хранения IP-пакетов. В другом варианте осуществления вместо того, чтобы сравнивать размер распределенной памяти с порогом, с порогом может сравниваться размер остающейся нераспределенной памяти. В этом варианте осуществления служба должна вычислить часть полезной нагрузки, которая может оставаться нераспределенной, если был распределен запрашиваемый или отрегулированный размер памяти. Сравнение остающейся нераспределенной памяти с этим порогом может затем использоваться способом, подобным ранее обсуждавшемуся сравнению распределенной памяти с порогом.
Выполняя этап 800 принятия решения, если идентифицированная сумма больше, чем порог, способ переходит к этапу 805. При переходе к этапу 805 система распределения памяти возвращает ссылку запрашивающей подсистеме. В одном варианте осуществления возвращенной ссылкой является data_ptr из заголовка текущего элемента DSM. Предпочтительно, возвращая ссылку из заголовка элемента DSM, система распределения памяти сохраняет служебные данные и ресурсы, вовлеченные в создание элемента DUP и возвращение ссылки из заголовка DUP. Дополнительно, распределение остатка полезной нагрузки DSM, а не только запрашиваемого размера, позволяет службе распределения памяти избегать малых блоков данных в конце полезных нагрузок, которые, в противном случае, могут, если используются, привести к организации цепочки.
Возвращаясь к этапу 800 принятия решения, если запрашиваемый размер памяти плюс уже распределенный размер памяти не больше порога, способ переходит к этапу 810. На этапе 810 служба распределения памяти создает элемент DUP, распределяет запрашиваемую память и возвращает ссылку в DUP к запрашивающей подсистеме. Предпочтительно, посредством многочисленных итераций этот способ позволяет службе распределения памяти упаковывать многочисленные распределения в единый элемент DSM. Эта упаковка позволяет эффективно использовать ресурсы памяти и обеспечивает выигрыш как в использовании памяти, так и в использовании обработки.
Возвращаясь к этапу 790, если запрашиваемый размер памяти больше, чем нераспределенное пространство в текущем элементе DSM, способ переходит к этапу 845 принятия решения на фиг.4B. На этапе 845 принятия решения служба распределения памяти определяет, превышает ли запрашиваемый размер второй порог. Этот второй порог, как и первый, может быть установлен как фиксированное количество байтов. Например, если размер полезной нагрузки элемента DSM составляет 1600 байтов, второй порог может составлять 1200 байтов. Альтернативно, второй порог может быть также определен как процент от размера полезной нагрузки. Например, второй порог может составлять 65%-75% от размера полезной нагрузки. В другом варианте осуществления порог может определяться динамически. Например, порог может быть установлен равным общему объему распределенной памяти в элементе DSM. В этом варианте осуществления запрашиваемый размер может превысить порог, когда запрашиваемый размер превышает распределенное пространство в DSM. Независимо от того, как определен порог, если запрашиваемый размер больше, чем этот порог, служба распределения памяти распределяет новый элемент DSM и возвращает data_ptr из нового заголовка элемента DSM в запрашивающую подсистему, как показано на этапе 850. Подобно этапу 805 этот процесс возвращения ссылки из заголовка нового элемента DSM сохраняет служебные данные для создания нового элемента DUP. Запрашивающей подсистеме дается больше, чем она попросила, целиком элемент DSM, и это распределение позволяет удовлетворять последующие запросы распределения с помощью нераспределенной памяти, остающейся в текущем элементе DSM.
Возвращаясь к этапу 845, если запрашиваемый размер меньше этого второго порога, способ переходит к этапу 855. На этапе 855 удаляется ссылка заголовка элемента DSM на нераспределенную часть полезной нагрузки DSM. В действительности это освобождает остаток элемента DSM. Кроме того, создается новый элемент DSM. Блок памяти распределяется в новом элементе DSM, и создается соответствующий DUP. Ссылка в новом DUP на новый элемент DSM затем возвращается в запрашивающую подсистему.
Для цели объяснения на фиг.5 показаны примеры приведенного выше способа. В случае 1 показан текущий элемент 910 DSM. Текущий DSM имеет как распределенную часть 915, так и нераспределенную часть 920. Запрашиваемый размер 925 пакета показан как первый порог 930. Как видно на фигуре, размер распределенной части 915 плюс размер запрашиваемой части 925 меньше первого порога 930. Соответственно, как показано, участок элемента 935 DSM распределен и создан новый элемент DUP, и его ссылка возвращается запрашивающей подсистеме. Новый элемент DUP включает в себя ссылку на DSM 935, которая указывает начало вновь распределенных данных.
В случае 2 текущий DSM 955 показан совместно с другим запрашиваемым пакетом 960. Как показано на фигуре, размер распределенной части DSM 955 плюс размер запрашиваемого пакета превышает первый порог, однако сумма не превышает общую длину полезной нагрузки. Соответственно, ссылка на нераспределенную часть элемента 965 DSM возвращается запрашивающей подсистеме. Результат состоит в том, что в дополнение к получению запрашиваемого размера памяти или даже немного большего отрегулированного распределения строк запрашивающая подсистема получит все остающееся нераспределенное пространство 980 в DSM 965. Опять же, возвращение ссылки из заголовка элемента DSM сохраняет служебную команду на создание DUP и исключает образование цепочек, потенциально образуемых заглушкой 980, которая, в противном случае, могла бы быть оставлена.
В случае 3 текущий DSM 985 показан с другим запрашиваемым блоком 990 памяти. Как показано на фигуре, запрашиваемый пакет является слишком большим, чтобы разместиться в нераспределенной части текущего DSM. Кроме того, запрашиваемый размер меньше, чем второй порог 995. Соответственно, ссылка в заголовке текущего DSM 1000 на нераспределенные части полезной нагрузки удаляется. Создается новый DSM 1005. Блок памяти из этого DSM распределяется, и создается новый элемент DUP, ссылающийся на распределенный блок в новом DSM. Ссылка из этого нового элемента DUP затем возвращается запрашивающей подсистеме. Опять же, следует понимать, что хотя второй порог 995 показан как статический, порог может быть определен динамически, например, устанавливая его равным размеру распределенной памяти в оригинале.
В случае 4 DSM 1010 показан вместе с запрашиваемым блоком 1015 памяти. Как и в случае 3, запрашиваемый размер слишком большой, чтобы поместиться в нераспределенной части элемента 1010 DSM. Кроме того, запрашиваемый размер 1015 блока больше второго порога 995. В результате, текущий DSM 1020 сохраняется в своем текущем состоянии. Между тем, создается новый DSM 1025, и ссылка на нераспределенную часть полезной нагрузки в новом заголовке DSM возвращается.
Способ, показанный на фиг.6, подобен способу, показанному на фиг.4A и 4B. Однако на фиг.6 предлагаются изменения в отношении определенных параметров, используемых в варианте осуществления услуги для распределения памяти. Способ 1080, показанный на фиг.6, обеспечивает API для запросов распределения памяти. В одном конкретном варианте осуществления способ 1080 обеспечивает запрос функции для подсистем, которая может использоваться для запроса распределения памяти. Как показано на фигуре, функция может принимать в качестве параметра запрашиваемый размер распределения памяти. Кроме того, функция может принимать другие параметры, такие как идентификатор подсистемы, который идентифицирует запрашивающую подсистему. Служба, представленная в соответствии с фиг.6, может быть сконфигурирована с возможностью ее выполнения на процессоре, таком как процессор 202 устройства 102. В ответ на запросы распределения служба, как обсуждается ниже, готовит указатель на распределенный блок памяти с размером, большим или равным запрашиваемому размеру. Соответственно, подсистемы, которые используют служебный API, возвращают указатель в распределенную память. В одном конкретном варианте осуществления способ, показанный на фиг.6, во время своей работы использует некоторые или все следующие значения:
current_dsm_item_ptr []: это набор указателей на текущий элемент DSM для каждой подсистемы.
aligned_pkt_size: это размер запрашиваемого блока памяти, отрегулированный, чтобы быть выровненным со строками кэша таких размеров, как 16, 32, 64 или 128.
pkt_ptr: указатель на распределенную память, которую собираются возвратить.
DSMI_MEM_THRESHOLD_TO_FREE_DSM: первый порог для того, чтобы определить, должна ли быть возвращена ссылка DUP или DSM. Если после распределения блока памяти остающаяся нераспределенная память должна быть меньше этого порога, ссылка DSM возвращается, эффективно распределяя всю остающуюся нераспределенную память в элементе DSM.
DSMI_THRESHOLD_FOR_COMPLETE_ITEM_ALLOCATION: второй порог для определения, должны ли ссылки DUP или DSM быть возвращены. Если запрашиваемый размер пакета больше этого порога, создается новый элемент DSM, и возвращается ссылка из заголовка нового DSM. Текущий DSM сохраняется.
Способ, показанный на фиг.6, начинается с запроса функции, показанного на этапе 1085. В качестве параметра запроса служба распределения принимает запрашиваемый размер пакета "pkt_size". Кроме того, в некоторых вариантах осуществления в запросе функции также должен передаваться другой параметр, идентификатор подсистемы. Переходя к этапу 1100, способ блокирует конкретный пул элементов DSM, чтобы избежать проблем одновременного доступа. После блокировки пула способ переходит к этапу 1105 принятия решения. На этапе 1105 принятия решения служба определяет, является ли pkt_ptr нулевым. Если по запросу никакая память не была распределена, указатель может быть нулевым. Однако если указатель имеет ненулевое значение, служба переходит к разблокированию пула на этапе 1140 и возвращает указатель на этап 1145. Однако если указатель нулевой, служба переходит к этапу 1110 принятия решения.
Продолжая на этапе 1110 принятия решения, служба определяет, является ли current_dsm_item_ptr нулевым. Если предыдущие итерации не привели в результате ни к какому текущему существующему элементу DSM, на этапе 1115 служба переходит к его созданию и прекращает его создание, если оно терпит неудачу на этапах 1120, 1140, 1145. Как только для действительного текущего DSM подтверждается существование или создание, способ переходит к этапу 1125 принятия решения. На этапе 1125 принятия решения служба определяет, меньше ли выровненный запрашиваемый размер, чем размер нераспределенного пространства в текущем DSM. Если это так, на этапе 1130 служба затем определяет, меньше ли нераспределенное пространство, которое должно остаться после распределения запрашиваемой памяти в DSM, чем первый порог. Если это так, служба на этапе 1135 создает DUP и распределяет выровненную запрашиваемую память в текущем DSM, разблокирует пул на этапе 1140 и возвращает указатель DUP на этапе 1145. В противном случае служба на этапе 1150 создает полностью новый DSM, на этапе 1140 разблокирует пул и на этапе 1145 возвращает указатель из заголовка нового DSM.
Возвращаясь к этапу 1125, если запрашиваемый размер больше, чем остающееся нераспределенное пространство, способ переходит к этапу 1155 принятия решения. На этапе 1155 служба определяет, больше ли запрашиваемый размер второго порога или равен ему. Если это так, служба создает полностью новый DSM 1165, разблокирует пул 1140 и возвращает указатель из заголовка нового DSM 1145. В противном случае служба освобождает остающуюся память в текущем DSM и снова переходит к запуску способа на этапе 1105. Результат состоит в том, что создан новый DSM и создан DUP, ссылающийся на тело нового DSM, и указатель DUP возвращен запрашивающей подсистеме.
Здесь также представлены дополнительные признаки и варианты осуществления настоящей службы распределения памяти.
Многочисленные указатели DSM для различных пользователей
Для использования в случаях, в которых срок службы блоков, как ожидается, будет существенно различен для различных пользователей, алгоритм может поддерживать многочисленные указатели DSM и упаковать в одном и том же DSM только блоки данных со схожими сроками жизни. Например, конкретный идентификатор пользователя может быть передан вместе с запросом распределения, так что только данные от этого пользователя будут упаковываться в одном и том же элементе DSM. Запросы других пользователей должны упаковываться в другие DSM. Здесь "пользователем" может быть набор задач или подзадач, или уровней, или функций, или любая другая их комбинация, чтобы отличать один набор профиля пользователя от другого.
Поддержка добавления данных спереди (или сзади) DSM
Для эффективного добавления данных спереди существующего элемента DSM или DUP (то есть добавление заголовков протокола), без распределения нового элемента DSM и выполнения соединения цепочек, предложено обеспечивать распределение DSM со свободным пространством спереди. За свободным пространством поддерживается слежение с помощью заголовка "offset". Таким способом DUP или DSM могут распределяться с заданным смещением и позже, если перед DSM необходимо вставить больше данных, это может быть сделано без нового распределения DSM, сопровождаемого образованием цепочек. Подобная служба может обеспечиваться для добавления данных и в конце DSM.
Многочисленные пулы
Служба позволяет многочисленным пулам DSM обеспечивать резервирование заданного числа элементов определенному пользователю. Это путь, при котором пользователь не должен будет волноваться, что внезапно больше не окажется никаких свободных элементов DSM, потому что всех их распределил другой пользователь. Кроме того, это обеспечивает лучшую способность отладки при проблемах переполнения памяти (когда один пользователь не принимает во внимание границы распределения), потому что проблема ограничивается только объемом кодового алфавита этого пользователя.
Служба квоты как альтернатива многочисленным пулам
Другой способ достигнуть того же самого состоит в том, чтобы иметь один пул, но каждый пользователь имеет максимальную квоту элементов DSM (байты), которые он может распределить. Как только он достиг своей квоты, он должен освободить некоторые элементы, чтобы распределить новые элементы во избежание недостатка памяти у других пользователей. Одно из преимуществ, которое этот подход имеет перед подходом с многочисленными пулами, заключается в том, что может быть достигнуто совместное использование. Например, если существуют 4 пользователя с их собственным пулом из X элементов, это должно потребовать 4X элементов памяти. Однако так как очень маловероятно, что все 4 пользователя будут распределять все элементы в одно и то же время, служба квот может позволить уменьшить общую память, скажем, до 3X, предполагая, что если один пользователь берет всю свою память, равную X, 3 остальных пользователя смогут иметь возможность совместно использовать остающуюся память, равную 2X.
Многочисленные указатели DSM для различных размеров
В этом аспекте распределение DSM может быть разделено, основываясь на запрашиваемом пространстве памяти (в отличие от использования описанного выше идентификатора подсистемы). Вместо использования традиционного пути пулов многочисленных размеров, совместно используемых через многочисленные уровни/подсистемы, чтобы удовлетворить потребности всех задач/профилей, с помощью этого предложения возможно обеспечить поддержку многочисленных указателей DSM, из которых только блоки определенного размера могут быть распределены для каждого указателя DSM. Например, мы можем иметь указатель DSM для размеров блоков 128, 256, 512, 768, 1024, 1536 байтов и так далее.
Всякий раз при любых запросах уровня/модулей для определенного размера памяти алгоритм может определить наиболее подходящий указатель DSM и обеспечить дубликат, если запрашиваемый размер доступен. Если запрашиваемый размер недоступен, тогда освобождают указатель DSM (если он не нулевой) для этого размера и распределяют большой элемент из глобального пула больших элементов (например, элементов, больших, чем заданное количество байтов, в одном примере, элементы, большие или равные 768 байтам), и затем DUP наилучшим образом подгоняет размер блока и возвращает DUP вызывающему абоненту.
Настоящее распределение обладает также несколькими отличительными преимуществами по сравнению с предшествующим уровнем техники. Варианты осуществления настоящей службы уменьшают занимаемую площадь памяти. Использование меньшего количества пулов обеспечивает лучшее статистическое мультиплексирование. Служба обеспечивает лучшую эффективность упаковки. Для элементов DSM требуется меньше служебных команд, даже при добавлении служебных команд для DUP. Центральный процессор, обрабатывающий служебные команды (MIPS), уменьшается из-за меньшего количества цепочек. Служба разрешает использование больших элементов DSM, избегая длинных цепочек в пакете (особенно при больших размерах пакета), таким образом уменьшая количество операций распределения/освобождения DSM. Варианты осуществления упрощают техническое обслуживание, связанное с более традиционным подходом, вовлекающим многочисленные пулы памяти. Служба может осуществляться как имеющая центральный API для обработки, и это помогает избежать необходимости осуществлять такие функциональные возможности в каждой подсистеме, тем самым дублируя код. Необходимость в отдельных размерах пулов и размерах элементов для каждого целевого значения исключается. Без описанных здесь способов необходимо было бы осуществлять код отдельно во многих местах (например, различные или многочисленные уровни в стеке, такие как модуль пакетных служб (PS), высокоскоростной модуль USB (HS-USB) и т.д.), которые более склонны к ошибкам, и т.д. Возможно определить пул DUP в высокоскоростной памяти для дополнительного улучшения показателей (например, преимущества кэша), например определяя пул DUP в памяти с малой задержкой (например, внутренняя оперативная память (IRAM)). Уменьшенные проверки в DSM могут быть получены, если используется только один пул с этим программным интерфейсом приложения (API). В настоящее время DSM выполняет некоторые проверки, основанные на идентификаторе пула (идентификация), который передается в качестве параметра.