Алгоритмы динамического управления памятью
К основным недостаткам этого алгоритма относится невозможность оценки времени поиска подходящего блока, что делает его неприемлемым для задач реального времени. Для этих задач требуется алгоритм, который способен за фиксированное (желательно, небольшое) время либо найти подходящий блок памяти, либо дать обоснованный ответ о том, что подходящего блока не существует.
Проще всего решить эту задачу, если нам требуются блоки нескольких фиксированных размеров (рис. 4.10). Мы объединяем блоки каждого размера в свой список. Если в списке блоков требуемого размера ничего нет, мы смотрим в список блоков большего размера. Если там что-то есть, мы разрезаем этот блок на части, одну отдаем запрашивающей программе, а вторую… Правда, если размеры требуемых блоков не кратны друг другу, что мы будем делать с остатком?
Для решения этой проблемы нам необходимо ввести какое-либо ограничение на размеры выделяемых блоков. Например, можно потребовать, чтобы эти размеры равнялись числам Фибоначчи (последовательность целых чисел, в которой Fi+1 = Fi + Fi-1. В этом случае, если нам нужно Fi байт, а в наличии есть только блок размера Fi+1, мы легко можем получить два блока – один требуемого размера, а другой – Fi-1, который тоже не пропадет. Да, любое ограничение на размер приведет к внутренней фрагментации, но так ли велика эта плата за гарантированное время поиска блока?
Рис. 4.10. Выделение блоков фиксированных размеров
На практике, числа Фибоначчи не используются. Одной из причин, по-видимому, является относительная сложность вычисления такого Fi, которое не меньше требуемого размера блока. Другая причина – сложность объединения свободных блоков со смежными адресами в блок большего размера. Зато широкое применение нашел алгоритм, который ограничивает последовательные размеры блоков более простой зависимостью – степенями числа 2: 512 байт, 1 Кбайт, 2 Кбайт и т. д. Такая стратегия называется алгоритмом близнецов (рис. 4.11).
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Одно из преимуществ этого метода состоит в простоте объединения блоков при их освобождении. Адрес блока-близнеца получается простым инвертированием соответствующего бита в адресе нашего блока. Нужно только проверить, свободен ли этот близнец. Если он свободен, то мы объединяем братьев в блок вдвое большего размера, и т. д. Даже в наихудшем случае время поиска не превышает О (log(Smax)-log(Smin)), где Smax и Smin обозначают, соответственно, максимальный и минимальный размеры используемых блоков. Это делает алгоритм близнецов трудно заменимым для ситуаций, в которых необходимо гарантированное время реакции – например, для задач реального времени. Часто этот алгоритм или его варианты используются для выделения памяти внутри ядра ОС.
Рис. 4.11. Алгоритм близнецов
Существуют и более сложные варианты применения описанного выше подхода. Например, пул свободной памяти Novell Netware состоит из 4 очередей с шагом 16 байт (для блоков размерами 16, 32, 48, 64 байта), 3 очередей с шагом 64 байта (для блоков размерами 128, 192, 256 байт) и пятнадцати очередей с шагом 256 байт (от 512 байт до 4 Кбайт). При запросах большего размера выделяется целиком страница. Любопытно, что возможности работы в режиме реального времени, присущие этой изощренной стратегии, в Netware практически не используются.
Например, если драйвер сетевого интерфейса при получении очередного пакета данных обнаруживает, что у него нет свободных буферов для его приема, он не пытается выделить новый буфер стандартным алгоритмом. Вместо этого, драйвер просто игнорирует пришедшие данные, лишь увеличивая счетчик потерянных пакетов. Отдельный системный процесс следит за состоянием этого счетчика и только при превышении им некоторого порога за некоторый интервал времени выделяет драйверу новый буфер.
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.
Для новых пользователей первый месяц бесплатно. Зарегистрироваться в сервисе
Подобный подход к пользовательским данным может показаться циничным, Но надо вспомнить, что при передаче данных по сети возможны и другие Причины потери пакетов, например порча данных из-за электромагнитных Помех. Поэтому все сетевые протоколы высокого уровня предусматривают средства пересылки пакетов в случае их потери, какими бы причинами эта потеря ни была вызвана. С другой стороны, в системах реального времени игнорирование данных, которые мы все равно не в состоянии принять и обработать, – довольно часто используемая, хотя и не всегда приемлемая стратегия.