Кроме malloc/free для программы нужна ОС для обеспечения чего-либо еще?
Если вы используете карту, каждый ключ должен быть уникальным. Вы не можете использовать размеры в качестве ключа, так как они не являются уникальными.
Из описания вашей проблемы:
У меня много пар обуви, и у каждой обуви есть размер, цвет и цена. Пары обуви должны быть упорядочены по по размеру.
карта не является хорошим выбором, поскольку Карты , как правило, не упорядочены (за исключением
SortedMap). Вы хотите, чтобы структура данных была упорядочена в соответствии с определенными критериями. AListкажется действительно хорошим выбором. Наиболее распространенной реализацией списка являетсяArrayList.Сначала вам нужен класс для хранения вашего объекта обуви, который должен выглядеть следующим образом:
public class Shoe{ int size; Color color; // Color is an enum, but it can be a String if you want to be less restrictive int price; public Shoe(int size, Color color, int price) { ... }Затем вы можете хранить свою обувь в своем списке таким образом:
List<Shoe> shoes = new ArrayList<>(); shoes.add(new Shoe(36, Color.BLACK, 30)); shoes.add(new Shoe(36, Color.WHITE, 35)); shoes.add(new Shoe(37, Color.BLACK, 40)); shoes.add(new Shoe(38, Color.BLACK, 40)); ...И Как только ваш список заполнен, вы можете упорядочить их по размеру:
shoes.sort(Comparator.comparing(Shoe::getSize));
Альтернатива: вы можете создать
TreeMap<Integer,List<Shoe>>(отсортированная карта, которая отображает ключи в список для разрешения столкновений ключей), используя тот же компаратор, таким образом, даже если вы вставляете новую обувь, она остается упорядоченной, но она выходит за рамки вашей проблемы.
7 ответов
malloc обычно реализуется во времени выполнения C в пространстве пользователя, полагаясь на определенные системные вызовы ОС для отображения на страницах виртуальной памяти. Задание malloc и free должен управлять теми страницами памяти, которые фиксируются в размере (обычно 4 КБ, но иногда больше), и нарезать и ставить на карту их в части, которые могут использовать приложения.
Посмотрите, например, GNU libc реализация.
Для намного более простой реализации проверьте класс операционных систем MIT с прошлого года. А именно, посмотрите заключительные раздаточные материалы лаборатории и смотрите на lib/malloc.c. Этот код использует операционную систему JOS, разработанный в классе. Путем это работает, то, что это прочитывает таблицы страниц (обеспечил только для чтения ОС), ища неотображенные диапазоны виртуальных адресов. Это затем использует sys_page_alloc и sys_page_unmap системные вызовы страниц карты и некарты в текущий процесс.
Существует несколько способов заняться проблемой.
Чаще всего C программы имеют их собственную malloc/free функциональность. Тот будет работать на маленькие объекты. Первоначально (и как только память исчерпывается) диспетчер памяти попросит у ОС большей памяти. Традиционные методы сделать это - mmap и sbrk на вариантах Unix (GlobalAlloc / LocalAlloc на Win32).
Я предлагаю, чтобы Вы смотрели на средство выделения памяти Doug Lea (Google: dlmalloc) от поставщика памяти (например, ОС) точка зрения. То средство выделения является высшим качеством в очень хорошем и имеет рычаги для всей главной операционной системы. Если Вы хотите знать то, что высокопроизводительное средство выделения ожидает от ОС, это - код, Ваш предпочтительный вариант.
Вы путаете "кучу" и стек?
Я спрашиваю, потому что Вы упоминаете "когда-либо расширяющуюся часть памяти", объем и переменные продвижения на "куче", поскольку они объявляются. То верное кажется, что Вы на самом деле говорите о стеке.
В наиболее распространенных объявлениях реализаций C автоматических переменных как
интервал i;
обычно собираются привести ко мне выделяемый на стеке. В общем malloc не примет участие, если Вы явно не вызываете его, или некоторый вызов библиотеки, который Вы выполняете, вызывает его.
Я рекомендовал бы смотреть "на Опытное Программирование C" липой Peter Van Der для фона о том, как программы C обычно работают со стеком и "кучей".
Обязательное чтение: Knuth - Искусство Программирования, Объем 1, Глава 2, Раздел 2.5. Иначе Вы могли считать Kernighan & Ritchie "Язык программирования C" для наблюдения реализации; или, Вы могли считать Plauger "Стандартная библиотека для C" для наблюдения другой реализации.
Я полагаю, что то, что необходимо сделать в ядре, будет несколько отличаться от того, что видят программы вне ядра. В частности, выделение в оперативной памяти для программ будет иметь дело с виртуальной памятью, и т.д., тогда как программы вне кода просто видят результаты того, что обеспечило ядро.
Читайте об управлении виртуальной памятью (подкачка страниц). Это является очень определенным для ЦП, и каждая ОС реализует управление VM особенно для каждого поддерживаемого ЦП. Если Вы пишете свою ОС для x86/amd64, прочитайте их соответствующие руководства.
Обычно библиотека C обрабатывает реализацию malloc, запрос памяти от ОС (любой через анонимный mmap или, в более старых системах, sbrk) по мере необходимости. Таким образом, Ваша сторона ядра вещей должна обработать выделяющие целые страницы через что-то как одно из тех средств.
Затем это составило malloc скупо выдать память способом, которая не фрагментирует свободную память слишком много. Я не слишком в курсе дел с деталями этого, хотя; однако, термин арена приходит на ум. Если я могу выследить ссылку, я обновлю это сообщение.
Опасно Опасно !! Если вы даже рассматриваете попытку разработки ядра, вы должны хорошо знать стоимость ваших ресурсов и их относительно ограниченную доступность ...
Одна вещь о рекурсии заключается в том, что она очень дорогая (по крайней мере, в мире ядра), вы не увидите много функций, написанных для того, чтобы просто продолжать работать без рассуждений, иначе ваше ядро запаникует.
Чтобы подчеркнуть мою точку зрения (на stackoverflow.com хех), прочтите этот пост из Блог отладки NT о переполнении стека ядра, в частности,
· На платформах на базе x86 стек режима ядра составляет 12 КБ .
· На платформах на базе x64 Стек режима ядра составляет 24 КБ . (на базе x64 платформы включают системы с процессоры, использующие AMD64 архитектура и процессоры, использующие Архитектура Intel EM64T).
· На платформах на базе Itanium Стек режима ядра составляет 32 КБ с 32 КБ вспомогательный магазин.
На самом деле, не много;
Обычные подозреваемые
1. Широкое использование стека.
2. Рекурсивный вызов функций.
Если вы немного прочитаете блог, вы увидите, насколько сложной может быть разработка ядра с довольно уникальным набором проблем. Вы не ошиблись на уроке теории, это было просто, просто. ;)
От теории -> разработка ядра настолько важна для переключения контекста , насколько это возможно (возможно, сохранив некоторое взаимодействие с гипервизором !!).
В любом случае, никогда не предполагайте , подтвердите и проверьте свои ожидания.