Пользовательская реализация malloc в Stack Overflow
Я наткнулся на вопрос интервью, где они попросили реализовать malloc () и свободную функцию в C ++.
В самом начале объявляется массив символов размером 50000 (50000 байт). Предполагая, что это куча памяти, напишите malloc и free функции для выделения блоков памяти и освобождения памяти.
Кто-нибудь может предоставить мне рабочий / псевдокод C ++ или просто объяснить механизм? (очевидно, код сделает его намного проще для понимания).
Спасибо,
Рохит
Решение
В то время как написание производственного динамического распределителя памяти является очень сложной задачей, написание игрушечного — просто. Этот вопрос, очевидно, предназначен для проверки ваших навыков, но все же справедливо искать вдохновение в работах других.
«Язык программирования C» Кернигана & Ritchie содержит простую реализацию из malloc, Изучите его и рассмотрите последствия его разработки и реализации. Подумайте, как бы вы улучшили его, чтобы он работал лучше, меньше фрагментировался или обрабатывал несколько потоков. После этого больше не должно быть труда написать собственный распределитель игрушек и ответить на любые возникающие вопросы.
Другие решения
Есть несколько разных алгоритмов, которые можно использовать. Для такого
небольшая память, я бы просто префикс каждого блока с указателем на следующий
блок и флаг, указывающий, выделен ли он или освобожден.
распределение состоит из нахождения достаточно большого свободного блока, разделения его
при необходимости и маркировка возвращаемого блока как выделенного. Бесплатный
состоит из маркировки блока как свободного. В какой-то момент вы также должны
объединить блоки: если два свободных блока следуют друг за другом, они объединяются
в одну. (Я сделал это во время размещения в моей реализации.)
Вышеприведенный алгоритм не очень сложен сам по себе. Настоящий трюк
получать все разные слепки и тому подобное. Это хорошее упражнение
в программировании очень низкого уровня.
Я не проверял это раньше, но я думаю, что это можно сделать, используя новое ключевое слово и шаблоны для поддержки общего состояния для создания массива желаемых типов,
но я буду следовать этому вопросу, чтобы узнать реакцию героев C ++.