Перераспределение сегментов памяти для решения проблемы фрагментации

Перераспределение сегментов памяти для решения проблемы фрагментации

Иллюстрации

Показать все

Реферат

УРОВЕНЬ ТЕХНИКИ

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

Память может изнашиваться тогда, когда система записывает в память, так как запись может изменять физическую конфигурацию материала в памяти или ухудшать его некоторым другим образом. Устройства памяти, восприимчивые к этой проблеме, упоминаются как изнашиваемые устройства памяти. Из-за постепенного ухудшения параметров изнашиваемые устройства памяти подвергаются отказам памяти, которые могут воспрепятствовать надежному хранению в памяти данных для системы после большого количества операций записи, производимых системой. Например, ячейка РСМ может, как правило, выдерживать порядка 10⁸ операций записи перед изнашиванием (то есть перед отказом), тогда как ячейка DRAM может, как правило, выдерживать порядка 10¹⁵ операций записи перед отказом.

Память для системы можно разбить на множество областей, причем каждая область имеет многочисленные сегменты. Система может использовать области памяти в качестве блока для выделения памяти (например, во время исполнения) и/или переноса данных между основной памятью и вспомогательной памятью, такой как жесткий диск. Так как отдельные сегменты областей памяти начинают выходить из строя из-за большого количества записей, происходит фрагментация памяти. Фрагментация памяти возникает в тех случаях, когда область памяти разделена на меньшие участки используемой памяти (например, один или более соседних "рабочих" сегментов), которые разделятся вышедшим из строя или изношенным сегментом, который нельзя больше использовать. Хотя малые участки используемой памяти между вышедшими из строя сегментами являются по-прежнему надежными для выделения памяти, они не используются эффективным образом в системе, так как малые участки по отдельности являются слишком малыми для хранения более крупных объектов, например, данных, чье хранение требует непрерывной памяти (например, многочисленные смежные сегменты). Другими словами, система не может поместить более крупные объекты между двумя вышедшими из строя сегментами памяти из-за фрагментации.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

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

Это краткое изложение сущности изобретения предоставлено, чтобы ввести подборку концепций в упрощенной форме, которые дополнительно описаны ниже в подробном описании. Данное краткое изложение сущности изобретения не предназначено ни для идентификации ключевых или существенных признаков заявляемого изобретения, ни для использования в качестве помощи при определении объема заявляемого изобретения. Например, термин "технологии" может относиться к системе(ам), аппаратным средствам, способу(ам), машиночитаемым инструкциям, модулю(ям) и/или алгоритмам, как это разрешено вышеупомянутым контекстом и на всем протяжении документа.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Подробное описание представлено со ссылкой на сопроводительные фигуры. На фигурах левая крайняя цифра(ы) ссылочной позиции идентифицирует фигуру, на которой ссылочная позиция появляется первой. Одинаковые ссылочные позиции на различных фигурах используются для обозначения аналогичных или идентичных элементов.

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

Фиг. 2 иллюстрирует примерную область памяти на различных этапах в случае, когда примерная архитектура системы реализует технологию кластеризации и перераспределения в соответствии с различными вариантами осуществления, раскрытыми в данном документе.

Фиг. 3 иллюстрирует две последовательных примерных области памяти в соответствии с различными вариантами осуществления, описанными в данном документе.

Фиг. 4 иллюстрирует примерный процесс выделения памяти, который создает и/или обновляет метаданные перераспределения в соответствии с различными вариантами осуществления, описанными в данном документе.

Фиг. 5 иллюстрирует примерный процесс выделения памяти, который использует метаданные перераспределения, чтобы считывать данные из области памяти в соответствии с различными вариантами осуществления, описанными в данном документе.

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Обзор

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

Как описано выше, изнашиваемые устройства памяти подвержены отказам памяти, которые могут воспрепятствовать надежному хранению в памяти данных после большого количества записей. Отказы памяти могут представлять собой изначально присутствующие отказы или статические отказы, либо отказы памяти могут представлять собой динамические отказы. В различных вариантах осуществления память представляет собой основную память, которая может включать в себя большой участок изнашиваемой памяти (которая, как правило, предполагается более плотной и более эффективной в плане затрат памятью) и меньший участок DRAM, который хранит данные и операции, которые не могут допускать отказа (например, операции, которые могут быть существенными для операционной системы). Изнашиваемые устройства памяти могут обеспечивать стабильные сегменты хранения, которые выходят из строя с меньшей степенью детализации по сравнению с более крупными областями основной памяти. В контексте данного документа более крупные области памяти описаны в качестве страниц памяти, и сегменты страниц памяти упоминаются как строки. Однако, в контексте данного документа понятно, что области памяти могут представлять собой любой модуль или блок памяти, используемый для выделения памяти в изнашиваемой памяти или устройствах памяти, выполненных по другой технологии. Более того, области памяти и строки могут изменяться по размеру или объему для хранения объектов (например, области и/или строки могут быть более детализированными или менее детализированными).

Когда в системе, которая использует DRAM в качестве основной памяти, происходит отказ памяти, отключается вся область памяти (например, страница). Однако продолжительный отказ памяти, где используется DRAM, является очень редким. Напротив, в изнашиваемых устройствах памяти продолжительные отказы памяти происходят чаще. Если бы одинаковое или аналогичное выведение из строя всей области памяти проявлялось бы для изнашиваемых устройств памяти, то объем памяти быстро бы израсходовался даже в том случае, если бы каждая область памяти по-прежнему имела бы все, а не один функциональный сегмент. По этой причине, вместо отключения памяти с детализацией на уровне области, системы, использующие изнашиваемые устройства памяти, могут отключать память с меньшей степенью детализации на уровне сегмента (например, с детализацией на уровне строки). Однако, так как трансляцию памяти из виртуальных адресов в физические адреса можно все еще выполнить с детализацией на уровне области в системах с изнашиваемой памятью (и это обычно выполняется при детализациях на уровне областей по причинам непроизводительных затрат), это может привести к виртуальному адресному пространству, которое нельзя сделать полностью непрерывным, и, следовательно, к фрагментации.

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

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

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

Иллюстративная архитектура

На Фиг. 1 изображена примерная системная архитектура 100 для реализации технологий, которые обсуждаются в данном документе. Системная архитектура 100 может быть сконфигурирована в виде любого подходящего вычислительного устройства, которая использует технологии памяти, которые допускают фрагментацию. В качестве примера, а не ограничения, системная архитектура 100 может включать в себя персональные вычислительные устройства, портативные вычислительные устройства, смартфоны, серверные вычислительные устройства, группы серверов, центры обработки данных или любые другие устройства, которые используют и/или выделяют память. Соответственно, системная архитектура 100 может включать в себя системное программное обеспечение 102, контроллер 104 памяти и модуль 106 памяти. Системное программное обеспечение 102, контроллер 104 памяти и/или модуль 106 памяти могут быть соединены и могут осуществлять связь в виде множества различных конфигураций (например, системная шина, сеть и т.д.).

В различных вариантах осуществления системное программное обеспечение 102 может включать в себя операционную систему, такую как операционная система Microsoft Windows®, операционная система смартфона, операционная система, работающая в режиме реального времени, или любой другой тип операционной системы, соединенный с модулем 106 памяти. Более того, системное программное обеспечение 102 может включать в себя любой тип динамических исполняемых сред (например, виртуальные машины, управляемый код и т.д.). По меньшей мере в одном варианте осуществления операционная система может сообщать об отказах памяти в динамические исполняемые среды, с тем чтобы динамически исполняемые среды могли выделять память в окрестности вышедших из строя частей памяти.

В различных вариантах осуществления системное программное обеспечение 102 и/или контроллер 104 памяти выполнены с возможностью управления потоком данных в и из модуля 106 памяти (например, физической памяти). Модуль 106 памяти может представлять собой аппаратный модуль памяти, который включает в себя множество страниц 108(1)…108(N), где каждая страница 108(1)…108(N) может представлять собой более крупную область памяти, обсужденную выше. В связи с этим системное программное обеспечение 102 и/или контроллер 104 памяти можно выполнить с возможностью выделения пространства памяти на страницах 108(1)…108(N) для объектов, ассоциированных с программами или приложениями, исполняемыми на одном или более процессорных ядрах 110(1)…110(М), управление которыми осуществляется с помощью системного программного обеспечения 102. Следовательно, системное программное обеспечение 102 можно выполнить с возможностью предоставления сервисов одному или более процессорным ядрам 110(1)…110(М), и каждое процессорное ядро 110(1)…110(М) может иметь кэш 112(1)…112(L), в который кэшируются одна или более страниц 108(1)…108(N), которые в текущий момент времени доступны системному программному обеспечению 102 и/или контроллеру 104 памяти. Более того, в кэшах 112(1)…112(L) может также кэшироваться информация об отказах памяти или ошибках, которая сообщается с помощью системного программного обеспечения 102. По меньшей мере в одном варианте осуществления кэши 112(1)…112(L) могут представлять собой статическое оперативное запоминающее устройство (SRAM).

В различных вариантах осуществления модуль 106 памяти представляет собой основную память для системной архитектуры 100 системного программного обеспечения 102. Системное программное обеспечение 102 можно хранить в модуле 106 памяти или можно хранить в отдельной памяти в пределах системной архитектуры 100, которая отличается от модуля 106 памяти. Контроллер 104 памяти может представлять собой часть аппаратных средств компьютера, которые расположены на печатной плате с модулем 106 памяти, контроллер 104 памяти может быть расположен на той же самой подложке, что и модуль 106 памяти, или контроллер 104 памяти может быть расположен на подложке микросхемы с процессорными ядрами 110(1)…110(М). По меньшей мере в одном варианте осуществления контроллер 104 памяти встроен в программно-аппаратные средства (firmware) или в программируемую пользователем вентильную матрицу (FPGA). В другом варианте осуществления контроллер может представлять собой специализированную интегральную схему (ASIC), ассоциированную с модулем 106 памяти, или драйвер устройства, ассоциированный с модулем 106 памяти. Таким образом, контроллер 104 памяти может располагаться на стороне обработки системной архитектуры 100, или контроллер 104 памяти может локально располагаться на модуле 106 памяти.

Как описано выше, каждая из страниц 108(1)…108(N) включает в себя многочисленные строки, которые системное программное обеспечение 102 и/или контроллер 104 памяти могут использовать для выделения памяти. Размер страницы памяти и число страниц памяти в модуле памяти может изменяться в зависимости от системной архитектуры. Например, размер страницы памяти может находиться в диапазоне от приблизительно одного килобайта до двух мегабайтов. Более того, по меньшей мере в одном примере, каждая строка на странице памяти может иметь размер 512 битов, однако в других примерах страницы и строки могут быть меньше или больше.

В различных вариантах осуществления каждое из процессорных ядер 110(1)…110(М) может включать в себя один или более процессоров. Процессоры могут представлять собой одиночное процессорное устройство или ряд из двух или более устройств, любые или все из которых могут включать в себя многочисленные вычислительные устройства. Процессоры можно реализовать в виде одного или более микропроцессоров, микрокомпьютеров, микроконтроллеров, процессоров для цифровой обработки сигналов, центральных процессорных устройств, конечных автоматов, логических схем, процессоров с общей памятью и/или любых устройств, которые манипулируют сигналами на основании рабочих инструкций. Среди других возможностей, процессоры можно выполнить с возможностью извлечения и исполнения машиночитаемых инструкций, которые хранятся в системном программном обеспечении 102, контроллере 104 памяти или любом другом приложении или программе, доступной системной архитектуре 100.

Как дополнительно обсуждено здесь, страницы памяти 108(1)…108(N) в модуле 106 памяти могут представлять собой страницы изнашиваемой памяти, такой как PCM. Однако технология, описанная в данном документе, широко применима к системам, использующим другие типы технологий памяти аппаратных средств, включая, но не ограничиваясь, флэш-память, подсистемы RAM, магниторезистивное оперативное запоминающее устройство с переносом спинового момента (STT-MRAM), ферроэлектрическое оперативное запоминающее устройство (FRAM), резистивное оперативное запоминающее устройство (RRAM) или любые другие магниторезистивные устройства памяти. Более того, технологии, обсужденные в данном документе, могут быть также применимы к устройству памяти на основе заряда, таким как DRAM.

В различных вариантах осуществления системное программное обеспечение 102 может включать в себя модуль 114 выделения памяти, и контроллер 104 памяти может включать в себя модуль 116 обнаружения отказов, модуль 118 кластеризации и кэш 120 информации об отказах. Модуль 114 выделения памяти можно выполнить с возможностью управления потоком данных (например, объектов), поступающих на и из страниц 108(1)…108(N) в модуле 106 памяти. Модуль 116 обнаружения отказов можно выполнить с возможностью обнаружения вышедших из строя строк в пределах каждой из страниц 108(1)…108(N). Например, модуль 116 обнаружения отказов обнаруживает и подтверждает, что строка вышла из строя и не является больше надежной в случае, когда контроллер 104 памяти записывает данные в строку в странице 108(N), к которой в текущий момент времени осуществляется доступ, при одновременном временном сохранении другой версии этих данных в буфере. Затем контроллер 104 памяти считывает данные обратно (например, непосредственно считывает данные обратно) со страницы 108(N), к которой в текущий момент времени осуществляется доступ, и модуль 116 обнаружения отказов сравнивает считанные данные с другой версией данных, которые временно хранятся в буфере. Если данные, считанные обратно из страницы 108(N), к которой в текущий момент времени осуществляется доступ, не являются такими же, как данные, временно хранящиеся в буфере, то модуль 116 обнаружения отказов идентифицирует строку в пределах страницы 108(N), к которой в текущий момент времени осуществляется доступ, в качестве вышедшей из строя строки.

В различных вариантах осуществления модуль 116 обнаружения отказов можно выполнить с возможностью сохранения информации об отказах области в кэше 120 информации об отказах. Информация об отказах областей включает в себя то, имеет или не имеет каждая из отдельных страниц 108(1)…108(N) постоянный отказ строки. Если страница 108(N) имеет постоянный отказ строки, контроллер 104 памяти может кэшировать метаданные 122 перераспределения для страницы 108(N) в кэше 120 информации об отказах, а также адрес для страницы 108(N). Соответственно, модуль 114 выделения памяти может использовать метаданные 122 перераспределения, которые хранятся в кэше 120 информации об отказах, для управления запросами на считывание и/или запись в отношении страниц 108(1)…108(N), которые имеют по меньшей мере один постоянных отказ строки.

Как дополнительно обсуждено ниже, в различных вариантах осуществления модуль 118 кластеризации выполнен с возможностью создания метаданных 122 перераспределения, которые переназначают вышедшие из строя строки краям каждой из отдельных страниц 108(1)…108(N) (например, верхней части страницы или нижней части страницы) или краям страницы 108(1)…108(N), которая находится в конце более крупной области перераспределения памяти (например, четыре страницы или восемь страниц). В некоторых вариантах осуществления модуль 118 кластеризации может создавать метаданные 122 перераспределения для отдельной страницы 108(N) или более крупную область перераспределения памяти, когда модуль 116 обнаружения отказов первым идентифицирует постоянный отказ строки (то есть вышедшую из строя строку) в пределах отдельной страницы 108(N).

В различных вариантах осуществления, когда страница 108(N) используется в текущий момент времени, предполагается к использованию или недавно использовалась системным программным обеспечением 102 совместно с одним или более процессорными ядрами 110(1)…110(М), модуль 114 выделения памяти может временно хранить метаданные 122 перераспределения для текущей страницы 108(N) в кэш 120 информации об отказах, как будет дополнительно обсуждено здесь. В альтернативных вариантах осуществления, метаданные 122 перераспределения будут также храниться в одном или более кэшах 112(1)…112(L).

Хотя модуль 116 обнаружения отказов и модуль 118 кластеризации изображены в контроллере 104 памяти, в контексте данного документа понятно, что некоторые или все функциональные возможности, выполняемые этими отдельными модулями, можно дополнительно или альтернативно сохранить где-нибудь еще или расположить на или распространить через системное программное обеспечение 112 (например, некоторые функциональные возможности можно выполнить с помощью операционной системы). Более того, в различных вариантах осуществления системное программное обеспечение 102 может также поддерживать отдельный кэш соотнесения отказов, в котором хранится информация об отказах памяти и который передает эту информацию в динамические исполняемые среды в точках выделения памяти, с тем чтобы можно было избежать отказа памяти. В результате, по меньшей мере в некоторых вариантах осуществления системное программное обеспечение 102 и контроллер 104 памяти могут осуществлять связь друг с другом и обмениваться информацией для выполнения технологий, обсуждаемых в данном документе.

Фиг. 2 иллюстрирует различные стадии для отдельной страницы 108(N) памяти, когда страница памяти изнашивается, и операционная система 102 и контроллер 104 памяти реализуют примерный процесс перераспределения во времени. Как обсуждено выше, отдельная страница 108(N) памяти может включать в себя многочисленные различные строки. Объем памяти каждой строки и число строк на каждой странице может зависеть от типа используемой памяти. По меньшей мере в одном варианте осуществления размер строки может составлять 512 битов, и страница 108(N) может представлять собой страницу размером четыре килобайта.

Однако, как показано на Фиг. 2, страница 108(N) включает в себя восемь строк, индексированных 0, 1, 2, 3, 4, 5, 6 и 7 в иллюстративных целях и для облегчения понимания. Хотя строки на Фиг. 2 проиндексированы последовательно с использованием числовых значений от 0 до 7, в контексте документа понятно, что можно использовать любую схему адресации сегментов или строк для более крупных областей памяти. Более того, как показано на Фиг. 2, каждую строку можно разбить на участок хранения данных и участок исправления ошибок. Участок хранения данных хранит объекты или части объектов, выделенных модулю 106 памяти, и участок исправления ошибок зарезервирован для возможного исправления ошибок для каждой отдельной строки. Когда исправление ошибок полностью исчерпано (например, участок исправления ошибок полностью заполнен на Фиг. 2), модуль 116 обнаружения идентифицирует строку как вышедшую из строя строку, как обсуждено выше. В альтернативных вариантах осуществления отдельные строки могут не включать в себя участок исправления ошибок.

Как показано на этапе 200(А), страница 108(N) является идеальной страницей, так как она еще не включает в себя каких-либо вышедших из строя строк, и каждая строка имеет полный набор доступных ресурсов исправления ошибок. Однако, так как системное программное обеспечение 102 и/или контроллер 104 памяти начинают выполнять запись 108(N) во время процессов выделения памяти, проводимых с течением времени, и из-за изменения в пределах отдельных ячеек, которые образует изнашиваемая память, отдельные строки в пределах страницы 108(N) могут иметь различный уровень износа.

Как показано на этапе 200(В), строка 1 и строка 3, помеченные "отказ 1" и "отказ 2", соответственно, исчерпали все доступные ресурсы исправления ошибок. Таким образом, модуль 116 обнаружения отказов может обнаружить, что эти строки вышли из строя, и в целях этого обсуждения предполагается, что строка 1 вышла из строя первой, а строка 3 вышла из строя второй после выхода из строя строки 1.

В различных вариантах осуществления, когда модуль 116 обнаружения отказов обнаруживает, что первая строка (например, строка 1) в пределах отдельной страницы 108(N) вышла из строя, модуль 118 кластеризации на этапе 200(С) создает метаданные 122 перераспределения и выделяет строку памяти (например, строку 7) в пределах страницы 108(N) для метаданных 122 перераспределения. Таким образом, когда первая строка 108(N) выходит из строя в результате износа (например, строка 1) модуль 118 кластеризации может также создать в то же самое время второй "ложный" отказ. Вторая строка с ложным отказом, которая хранит метаданные 122 перераспределения, может быть расположена на участке за пределами страницы 108(N) (например, строка 7). Модуль 118 кластеризации устанавливает метаданные 122 перераспределения на верхней части или на нижней части страницы 108(N), с тем чтобы не прерывалось непрерывное пространство для хранения данных.

В различных вариантах осуществления метаданные 122 перераспределения включают в себя ряд информационных записей, которые отражают число строк на странице 108(N). Например, метаданные 122 перераспределения имеют информационную запись 0, соответствующую строке 0, информационную запись 1, соответствующую строке 1, информационную запись 2, соответствующую строке 2 и т.д. Метаданные 122 перераспределения сконфигурированы для логической реорганизации строк в пределах страницы 108(N) путем переключения или смещения информационных записей таким образом, чтобы надежные или рабочие строки создавали логическое непрерывное пространство в пределах страницы 108(N), и ненадежные или вышедшие из строя строки логически перенаправлялись на участок, расположенный за пределом страницы 108(N), где были также установлены метаданные 122 перераспределения. Величина пространства для хранения данных, которое требуется для каждой информационной записи в метаданных 122 перераспределения, может быть равна числу битов, основывающемуся на логарифме от числа строк на странице 108(N). Так как метаданные 122 перераспределения управляют и перенаправляют пространство хранения данных для страницы 108(N), метаданные 122 перераспределения можно сохранять с избыточностью в случае, когда некоторые из битов, где были сохранены метаданные 122 перераспределения, отказали или повреждены. Более того, модуль 118 кластеризации можно выполнить с возможностью восстановления метаданных 122 перераспределения, если метаданные 122 перераспределения повреждены в результате тестирования аппаратных средств с помощью операций записи.

Как показано на этапе 200(D), модуль 118 кластеризации переключает информационную запись для строки 1 (например, фактический отказ на стадии 200(С)) на информационную запись для строки 6 в нижней части страницы. Таким образом, согласно метаданным 122 перераспределения с переключенными информационными записями, строка 6 становится логической вышедшей из строя строкой, и строка 1 становится логической рабочей строкой. Контроллер 104 памяти сохраняет данные в фактической строке 6, которая была логически переключена на строку 1, с тем чтобы создать непрерывное пространство для хранения данных.

Далее, при выходе из строя фактической строки 3, модуль 118 кластеризации переключает информационную запись для вышедшей из строя строки 3 на информационную запись для рабочей строки 5, которая представляет собой следующую рабочую строку, доступную для переключения на нее во время процесса перераспределения. Опять же, путем переключения информационных записей модуль 118 кластеризации создает логический участок непрерывного пространства памяти, который не является вызванным или разделенным вышедшими из строя строками памяти.

В различных вариантах осуществления каждую информационную запись в метаданных 122 перераспределения можно индексировать для отражения сдвига физического адреса (например, физическое местоположение первоначальной строки, связанной с информационной записью) и логического сдвига строки (например, физическое местоположение перераспределенной строки в случае, когда первоначальная строка вышла из строя). Таким образом, в различных вариантах осуществления метаданные 122 перераспределения обеспечивают преобразование адреса или местоположения путем указания того, что вышедшая из строя строка 1 была логически переключена на рабочую строку 6, и вышедшая из строя строка 3 была логически переключена на рабочую строку 5, как показано в виде реорганизации (например, переупорядочивания) информационных записей метаданных 122 перераспределения на стадии 200(D). Так как метаданные 122 перераспределения были созданы для и установлены на строке 7, информационная запись для строки 7 может быть пустой (например, "*") и не включать в себя какой-либо перенаправляющей информационной записи. В различных вариантах осуществления информационная запись для строки 7 может хранить избыточные метаданные перераспределения, как упомянуто выше.

Таким образом, исходные информационные записи в метаданных 122 перераспределения, соответствующие рабочим строкам на странице 108(N), на которые не были логически переключены вышедшие из строя строки, остаются такими же. Например, на стадии 200(D) информационные записи для строк 0, 2 и 4 в метаданных 122 перераспределения не были модифицированы или изменены, потому что они не поменялись местами с информационными записями для вышедшей из строя строки.

В различных вариантах осуществления метаданные 122 перераспределения используют указатель 202 границы, с тем чтобы модуль 118 кластеризации мог идентифицировать следующую доступную рабочую строку, чтобы логически поменять ее местами с вышедшей из строя строкой. Поскольку модуль 118 кластеризации логически объединяет вместе вышедшие из строя строки на участке, расположенном за пределами страницы 108(N), указатель 202 границы указывает на следующую рабочую строку, которая отделяет логическое непрерывное пространство от логического вышедшего из строя пространства. Например, на стадии 200(D) указатель 202 границы указывает на фактическую строку 4 как на следующую рабочую строку, которая ограничивает и отделяет логические отказы (например, строки 5, 6 и 7), объединенные в нижней части страницы 108(N). Соответственно, когда модуль 116 обнаружения отказов обнаруживает другой отказ строки, модуль 118 кластеризации реорганизует страницу 108(N) памяти путем логического перенаправления, в метаданных 122 перераспределения, адреса или индекса вышедшей из строя строки на строку, идентифицируемую указателем 202 границы. Модуль 118 кластеризации может затем продвигать указатель 202 границы на следующую рабочую строку и обновлять метаданные 122 перераспределения.

В различных вариантах осуществления каждая строка на странице 108(N) выполнена с индикатором, который дает возможность модулю 114 выделения памяти, во время начального доступа, идентифицировать, была ли логически перераспределена эта строка в процессе кластеризации. Например, индикатор может представлять собой один бит, зарезервированный на участке исправления ошибок, показывающий "да" в том случае, когда строка вышла из строя и была перераспределена, или "нет", когда строка не вышла из строя и данные, к которым осуществляется доступ, хранятся в строке. Когда строка вышла из строя, модуль 118 кластеризации может установить этот индикатор для указания того, что строка была перенаправлена или перераспределена. По меньшей мере в одном варианте осуществления модуль 114 выделения памяти и/или контроллер 104 памяти может определить местоположение метаданных 122 распределения, так как модуль 114 выделения памяти и/или контроллер 104 памяти знают, что метаданные 122 перераспределения можно расположить на первой строке в верхней части страницы 108(N) или на последней строке в нижней части страницы 108(N). В других вариантах осуществления индикатор для каждой строки можно дополнительно выполнить таким образом, чтобы он имел дополнительную возможность указывать метаданные 122 перераспределения в пределах страницы 108(N).

Исходя из различий между стадией 200(В) и стадией 200(D) видно, что процессы кластеризации и перераспределения, обсужденные в данном документе, логически создают большее количество непрерывного пространства для более крупного выделения объектам. Например, если бы модуль 114 выделения памяти должен был выделить память в окрестности вышедших из строя строк 1 и 3 на стадии 200(В), модуль 114 выделения памяти мог бы сохранить данные в 1) строке 0, 2) строке 2 или 3) строках 4-7 (например, четыре непрерывных строки). После выполнения процессов кластеризации и перераспределения модуль 114 выделения памяти может сохранить данные в логически рабочих строках 0-4 (например, пять непрерывных строк). Как упомянуто выше, страница 108(N) на Фиг. 2 включает в себя восемь строк в иллюстративных целях и для облегчения понимания. Соответственно, выгода и преимущества процессов кластеризации и перераспределения могут быть более очевидными за счет использования примеров, где имеется больше строк (например, 64 строки на странице), больше вышедших из строя строк, рассредоточенных в пределах страницы, и т.д.

Фиг. 3 иллюстрирует две соседние страницы 2N и 2N+1 300, которые хранятся в модуле 106 памяти. Для дальнейшей максимизации величины непрерывного пространства памяти, модуль 118 кластеризации можно выполнить с возможностью кластеризации вышедших из строя строк и метаданных 122 перераспределения на верхней части четных страниц (например, страниц 2N) в модуле 106 памяти и в нижней части нечетных страниц (например, страниц 2N+1) в модуле 106 памяти или наоборот. Таким образом, количество непрерывного пространства памяти может охватывать две