УСТРОЙСТВО ОБРАБОТКИ ИНФОРМАЦИИ, СПОСОБ УПРАВЛЕНИЯ ОБЛАСТЬЮ ПАМЯТИ И КОМПЬЮТЕРНАЯ ПРОГРАММА
DEVICE FOR INFORMATION PROCESSING, METHOD FOR STORAGE AREA CONTROL

Область техники, к которой относится изобретение
Настоящее изобретение относится к устройству обработки информации, способу управления областью памяти и компьютерной программе. Более конкретно, настоящее изобретение относится к устройству обработки информации, способу управления областью памяти и компьютерной программе, предназначенным для выделения соответствующей области памяти и выполнения процесса управления памятью при выделении, в случае когда множество потоков параллельно обращаются к области памяти и выполняют ее обновление.
Уровень техники
В случае когда множество программ обработки данных выполняют в одной операционной системе (ОС, OS) или во множестве операционных систем, общие для системы аппаратные средства, а именно ЦПУ или запоминающее устройство, последовательно переключают во времени.
Распределение (планирование) процессов (задач) множества операционных систем выполняют с помощью, например, программных средств управления разделением. Если ОС(α) и ОС(β) одновременно существуют в одной системе, причем процесс ОС(α) представляет собой процесс разделения А и процесс ОС(β) представляет собой процесс разделения В, программное средство управления разделением определяет распределение процесса А и процесса В и выполняет процессы операционных систем с выделением ресурсов аппаратных средств на основе определенного планирования.
В патентном документе 1 раскрыта методика управления задачами систем с множеством ОС. В соответствии с этим раскрытием задачи, предназначенные для выполнения множеством ОС, распределяют в соответствии с приоритетом, установленным для процесса, имеющего срочность.
Когда множество программ выполняют, по меньшей мере, в одной операционной системе (ОС), присутствует множество потоков, каждый из которых определен в модуле выполнения программы, и каждый поток использует память как общий ресурс. Если делается попытка высвобождения для другого потока определенной области памяти, на которую в данное время ссылается данный поток, может возникнуть ошибка доступа. В известном уровне техники возникновение ошибки предотвращают путем установки длительности блокировки прерываний. Установка длительности блокировки прерываний приводит к другой проблеме, такой как задержка процесса.
[Патентный документ 1] Публикация №2003-345612 находящейся на экспертизе японской заявки на патент.
Сущность изобретения
Проблемы, решаемые изобретением
Настоящее изобретение было разработано с учетом указанной выше проблемы, и целью настоящего изобретения является разработка устройства обработки информации, способа управления областью памяти и компьютерной программы для выделения соответствующей области памяти и выполнения процесса управления памятью таким образом, чтобы не возникала ошибка доступа, в компоновке, в которой множество потоков параллельно обращаются к области памяти и обновляют ее.
Средство решения проблем
В соответствии с первым аспектом настоящего изобретения устройство обработки информации включает в себя менеджер потока, предназначенный для управления информацией потока на основе модулей обработки данных, и менеджер области памяти, предназначенный для управления областью памяти. Менеджер потока сохраняет в качестве информации управления потоком список потоков, содержащий информацию времени входа, которая записана для каждого потока как функция времени вызова операционной системы из программы обработки данных. Менеджер области памяти сохраняет как информацию управления областью памяти очередь высвобождения, содержащую время запроса на высвобождение, которое записано для каждой области памяти в отношении области памяти, для которой поступил запрос на высвобождение, но которая еще не была высвобождена, сравнивает время запроса на высвобождение, установленное в каждом компоненте очереди, содержащемся в очереди высвобождения, с самым старшим временем входа каждого компонента очереди в списке потоков во время процесса выделения области памяти и выделяет область памяти, соответствующую компоненту очереди, имеющему время запроса на высвобождение, установленное раньше, чем самое старшее время входа.
В устройстве обработки информации в соответствии с одним вариантом выполнения настоящего изобретения менеджер потока генерирует список потоков, соответствующий каждому из множества процессоров, записывает самое старшее время входа, содержащееся в информации времени входа, установленной в информации потока, содержащейся в списке потоков, в заголовок каждого списка потоков и управляет записанным набором информации, установленным, как на него ссылается другой процессор.
В устройстве обработки информации в соответствии с одним вариантом выполнения настоящего изобретения менеджер области памяти обращается ко всей информации самого старшего времени входа, установленной в заголовке списка потоков, соответствующего процессору, управляемому менеджером потока, выбирает самое старшее из самых старших времен входа из информации самого старшего времени входа, установленной в заголовках списка потоков, соответствующего всем процессорам, сравнивает выбранное самое старшее время входа со временем запроса на высвобождение, установленным в каждом компоненте очереди, содержащемся в очереди высвобождения, и выделяет область памяти, соответствующую компоненту очереди, имеющему время запроса на высвобождение, установленное до выбранного самого старшего времени входа.
В устройстве обработки информации в соответствии с одним вариантом выполнения настоящего изобретения менеджер потока записывает в заголовке списка потоков и в компоненте списка информацию идентификации другого компонента списка, организует список потоков как список, который позволяет последовательно получать каждый компонент из заголовка, и обновляет информацию идентификации, установленную в одном из заголовка и компонента списка, во время одного из входа потока и ликвидации потока.
В устройстве обработки информации в соответствии с одним вариантом выполнения настоящего изобретения менеджер области памяти записывает в заголовке очереди высвобождения и в компоненте очереди информацию идентификации другого компонента очереди, организует очередь высвобождения как список, который позволяет последовательно получать каждый компонент очереди из заголовка, и обновляет информацию идентификации, установленную в одном из заголовка и компонента очереди, во время одного из установки новой очереди и удаления очереди.
В устройстве обработки информации в соответствии с одним вариантом выполнения настоящего изобретения менеджер области памяти выполняет процесс управления областью памяти на основе каждого модуля кучи, причем модуль кучи установлен как область памяти, имеющая конечный размер, установленная в соответствии с каждым процессором, сохраняет как информацию управления областью памяти очередь высвобождения, содержащую время запроса на высвобождение, которое записано на основе модуля кучи в отношении кучи, для которой поступил запрос на высвобождение, но которая еще не была высвобождена, и выделяет во время процесса выделения области памяти область памяти, которая записана для каждого модуля кучи в компоненте очереди, содержащемся в очереди высвобождения.
В устройстве обработки информации в соответствии с одним вариантом выполнения настоящего изобретения менеджер области памяти проверяет цепь слабого указателя, состоящую из слабого указателя, который обращается к области памяти, соответствующей компоненту очереди, содержащемуся в очереди высвобождения, и, если слабый указатель отсутствует в цепи слабого указателя, сбрасывает компонент очереди из очереди высвобождения и высвобождает область памяти, соответствующую этому компоненту очереди.
В устройстве обработки информации в соответствии с одним вариантом выполнения настоящего изобретения менеджер области памяти проверяет флаг ликвидации области памяти, содержащийся в цепи слабого указателя, состоящей из слабого указателя, обращающегося к области памяти, соответствующей компоненту очереди, содержащемуся в очереди высвобождения, и области памяти, содержащей область обращения слабого указателя, и, если флаг ликвидации указывает состояние ликвидации, сбрасывает компонент очереди из очереди высвобождения и высвобождает область памяти, соответствующую этому компоненту очереди.
В соответствии со вторым аспектом настоящего изобретения способ управления областью памяти включает в себя этап управления потоком, состоящий в генерировании и обновлении списка потоков, состоящего из информации потоков, содержащей информацию времени входа, которая записана на основе потока как время вызова функции операционной системы из программы обработки данных, этап управления областью памяти, состоящий в генерировании и обновлении в качестве информации управления областью памяти очереди высвобождения, содержащей время запроса на высвобождение, которое записано на основе области в отношении области памяти, содержащей область памяти, для которой поступил запрос на высвобождение, но которая еще не была высвобождена, и этап выделения области памяти, состоящий в выделении области памяти, соответствующей компоненту очереди, имеющему время запроса входа, установленное ранее самого старшего времени входа, путем сравнения времени запроса на высвобождение, установленного в каждом компоненте очереди, содержащемся в очереди высвобождения, с самым старшим временем входа каждого компонента очереди в списке потоков во время процесса выделения области памяти.
В способе управления областью памяти в соответствии с одним вариантом выполнения настоящего изобретения этап управления потоком включает в себя генерирование списка потоков, соответствующего каждому из множества процессоров, запись самого старшего времени входа, содержащегося в информации времени входа, установленной в информации потока, содержащейся в списке потоков, в заголовке каждого списка потоков и управление записанной информацией, установленной так, как на нее ссылается другой процессор.
В способе управления областью памяти в одном варианте выполнения настоящего изобретения этап выделения области памяти включает в себя обращение ко всей информации о самом старшем времени входа, установленной в заголовке списка потоков, соответствующего процессору, выбор самого старшего из самых старших времен входа из информации самого старшего времени входа, установленной в заголовках списка потоков, соответствующего всем процессорам, сравнение выбранного самого старшего времени входа со временем запроса на высвобождение, установленным в каждом компоненте очереди, содержащемся в запросе на высвобождение, установленном в каждом компоненте очереди, содержащемся в очереди высвобождения, и выделение области памяти, соответствующей компоненту очереди, имеющему время запроса на высвобождение, установленное ранее выбранного самого старшего времени входа.
В способе управления областью памяти в соответствии с одним вариантом выполнения настоящего изобретения этап управления потоком включает в себя запись в заголовке списка потоков и компоненте списка информации идентификации другого компонента списка, организацию списка потоков в виде списка, который позволяет последовательно получать каждый компонент из заголовка, и обновление информации идентификации, установленной в одном из заголовка и компонента списка, во время одного из входа в поток и ликвидации потока.
В способе управления областью памяти в соответствии с одним вариантом выполнения настоящего изобретения этап управления областью памяти включает в себя запись в заголовок очереди высвобождения и в компонент очереди информации идентификации другого компонента очереди, организующего очередь высвобождения как список, который позволяет последовательно получать каждый компонент очереди из заголовка, и обновление информации идентификации, установленной в одном из заголовка и компонента очереди во время одного из установки новой очереди и удаления очереди.
В способе управления областью памяти в одном варианте выполнения настоящего изобретения этап управления областью памяти включает в себя выполнение процесса управления областью памяти на основе модуля кучи, причем модуль кучи как область памяти имеет конечный размер, установлен в соответствии с каждым процессором, и сохранение в качестве информации управления областью памяти очереди высвобождения, содержащей время запроса на высвобождение, которое записано на основе каждого модуля кучи, в отношении кучи, для которой поступил запрос на высвобождение, но которая еще не была высвобождена, и этап выделения области памяти включает в себя выделение области памяти, которая записана на основе модуля кучи в компонент очереди, содержащийся в очереди высвобождения.
В способе управления областью памяти в соответствии с одним вариантом выполнения настоящего изобретения этап управления областью памяти включает в себя проверку цепи слабого указателя, состоящей из слабого указателя, ссылающегося на область памяти, соответствующую компоненту очереди, содержащемуся в очереди высвобождения, и, если слабый указатель отсутствует в цепи слабого указателя, сброс компонента очереди из очереди высвобождения и высвобождение области памяти, соответствующей этому компоненту очереди.
В способе управления областью памяти в соответствии с одним вариантом выполнения настоящего изобретения этап управления областью памяти включает в себя анализ флага ликвидации области памяти, содержащегося в цепи слабого указателя, состоящей из слабого указателя, обращающегося к области памяти, соответствующей компоненту очереди, содержащемуся в очереди высвобождения, и области памяти, содержащей область обращения слабого указателя, и, если флаг ликвидации обозначает состояние ликвидации, сброс компонента очереди из очереди высвобождения и высвобождение области памяти, соответствующей этому компоненту очереди.
В соответствии с третьим аспектом настоящего изобретения компьютерная программа, предназначенная для выполнения процесса управления областью памяти, включает в себя этап управления потоком, состоящий в генерировании и обновлении списка потоков, состоящего из информации потока, содержащей информацию времени входа, которая записана на основе потока как время вызова функции операционной системы из программы обработки данных, этап управления областью памяти, состоящий в генерировании и обновлении в качестве информации управления областью памяти очереди высвобождения, содержащей время запроса на высвобождение, которое записано на основе области в отношении области памяти, для которой поступил запрос на высвобождение, но которая еще не была высвобождена, и этап выделения области памяти, состоящий в выделении области памяти, соответствующей компоненту очереди, имеющему время запроса на вход, установленное ранее самого старшего времени входа, путем сравнения времени запроса на высвобождение, установленного в каждом компоненте очереди, содержащемся в очереди высвобождения, с самым старшим временем входа каждого компонента очереди в списке потоков во время процесса выделения области памяти.
Компьютерная программа в соответствии с настоящим изобретением предусмотрена для компьютерной системы общего назначения, выполняющей множество программных кодов, на носителе данных, считываемом компьютером, таком как CD, FD или МО, или через среду передачи данных, такую как сеть. Благодаря предоставлению компьютерной программы в виде, который может быть считан компьютером, компьютерная система выполняет процесс в соответствии с компьютерной программой.
Эти и другие свойства и преимущества настоящего изобретения будут очевидны из следующего описания настоящего изобретения и прилагаемых чертежей. В контексте описания настоящего изобретения система ссылается на логический набор множества устройств и не ограничивается устройством, в котором элементы находятся в пределах одного корпуса.
Преимущества
В соответствии с вариантами выполнения настоящего изобретения список потоков информации потока, содержащей информацию времени входа, которая записана на основе потока, причем поток, представляющий собой модуль обработки данных, сохранен как информация управления потоком, и очередь высвобождения, содержащая время запроса на высвобождение, которое записано на основе модуля области, в отношении области памяти, для которой поступил запрос на высвобождение, но которая еще не была высвобождена, сохранена как информация управления областью памяти. Время запроса на высвобождение, установленное в каждом компоненте очереди, содержащемся в очереди на высвобождение, сравнивают с самым старшим временем входа каждого компонента очереди в списке потоков во время процесса выделения области памяти. Процесс выделения памяти выполняют только для области памяти, соответствующей компоненту очереди, время запроса на высвобождение которого установлено ранее самого старшего времени входа. Только область памяти, которая не является целью доступа во всех потоках, надежно выбирают и подвергают процессу выделения. Процесс выделения области памяти безопасно выделяют таким образом, что в нем не происходит генерирование ошибки доступа в каждом потоке.
Краткое описание чертежей
На фиг.1 показана блок-схема устройства обработки информации в соответствии с настоящим изобретением.
На фиг.2 представлен модуль процессора.
На фиг.3 представлена иллюстрация структуры программных средств устройства обработки информации в соответствии с настоящим изобретением.
На фиг.4 представлена иллюстрация процесса доступа к типичной области памяти.
На фиг.5 представлена иллюстрация процесса доступа к типичной области памяти.
На фиг.6 представлена иллюстрация информации, управляемой менеджером потока в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.7 подробно представлена информация, управляемая менеджером потока в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.8 представлена иллюстрация информации, управляемой менеджером области памяти в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.9 показана блок-схема последовательности выполнения операций, иллюстрирующая последовательность процесса входа информации потока, выполняемого менеджером потока в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.10 подробно представлен процесс входа информации потока, выполняемого менеджером потока в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.11 показана блок-схема последовательности выполнения операций, иллюстрирующая последовательность процесса ликвидации информации потока, выполняемого менеджером потока в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.12 подробно представлена последовательность процесса ликвидации информации потока, выполняемого менеджером потока в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.13 показана блок-схема последовательности выполнения операций, иллюстрирующая последовательность процесса регистрации запроса на высвобождение области памяти, выполняемого менеджером области памяти в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.14 показана блок-схема последовательности выполнения операций, подробно иллюстрирующая процесс выделения области памяти, выполняемый менеджером области памяти в устройстве обработки информации в соответствии с настоящим изобретением.
На фиг.15 представлена иллюстрация структуры слабого указателя и цепи слабого указателя.
На фиг.16 показана блок-схема последовательности выполнения операций, иллюстрирующая процесс получения величины указателя, состоящий в получении величины слабого указателя.
На фиг.17 показана блок-схема последовательности выполнения операций, иллюстрирующая процесс последовательности очереди высвобождения (процесс очистки) в структуре, содержащей слабый указатель.
Подробное описание изобретения
Устройство обработки информации, способ управления областью памяти и компьютерная программа в соответствии с настоящим изобретением описаны ниже со ссылкой на чертежи.
Структура аппаратных средств устройства обработки информации в соответствии с настоящим изобретением описана ниже со ссылкой на фиг.1. Модуль 101 процессора включает в себя множество процессоров (модулей обработки) и обрабатывает данные в соответствии с различными программами, сохраненными в ПЗУ (постоянное запоминающее устройство) 104 и на НЖМД (HDD) 123, включая операционные системы (ОС) и прикладные программы, работающие под управлением ОС. Модуль 101 процессора будет описан ниже со ссылкой на фиг.2.
В ответ на команды, поступающие через модуль 101 процессора, графический процессор 102 генерирует данные, предназначенные для отображения на экране дисплея, которые формирует выходной модуль 122, например выполняет процесс изображения трехмерной графики. В главном запоминающем устройстве (динамическом ОЗУ, DRAM) 103 содержится программа, выполняемая модулем 101 процессора, и параметры, которые изменяются в ходе выполнения программы. Эти элементы взаимно соединены через главную шину 111, включающую в себя шину ЦПУ.
Главная шина 111 соединена с внешней шиной 112, такой как шина PCI (ВПК, взаимное соединение периферийных компонентов), через мост 105. Мост 105 управляет вводом и выводом данных между главной шиной 111, внешней шиной 112, контроллером 106, картой 107 памяти и другими устройствами.
Входной блок 121 вводит информацию во входное устройство, такое как клавиатура и устройство-указатель, оперируемые пользователем. Выходной блок 122 включает в себя блок вывода изображения, такой как один из жидкокристаллического дисплея и ЭЛТ (CRT, электронно-лучевая трубка), и устройство вывода звука, такое как громкоговоритель.
НЖМД (привод жесткого диска) 123 управляет жестким диском, загруженным в него, записывая, таким образом, или воспроизводя программу для выполнения модулем 101 процессора и информацию.
Привод 124 считывает данные программы, сохраненные на загружаемом съемном носителе 127 записи, таком как магнитный диск, оптический диск, магнитооптический диск, полупроводниковое запоминающее устройство или тому подобное, и передает данные и программы в главное запоминающее устройство (динамическое ОЗУ) 103 через интерфейс 113, внешнюю шину 112, мост 105 и главный мост 111.
Соединительный порт 125 соединяется с внешним устройством 128 и может включать в себя шину УПШ (USB, универсальная последовательная шина), шину IEEE 1394 или тому подобное. Соединительный порт 125 соединен с модулем 101 процессора через интерфейс 113, внешнюю шину 112, мост 105 и главную шину 111. Блок 126 передачи данных, соединенный с сетью, передает данные, подаваемые из НЖМД 123 или тому подобного, и принимает данные, поступающие извне.
Структура модуля процессора описана ниже со ссылкой на фиг.2. Как показано на чертеже, модуль 200 процессора включает в себя группу 201 основного процессора, включающую в себя множество модулей основных процессоров, и множество групп 202-20n подпроцессоров, каждый из которых включает в себя множество модулей подпроцессоров. Каждая группа дополнительно включает в себя контроллер запоминающего устройства и вторичный кэш. Группы 201-20n процессоров, каждая из которых включает в себя восемь модулей процессоров, например, соединены с использованием одной из архитектуры поперечной линии и сети обмена пакетами. В ответ на команду основного процессора группы 201 основного процессора, по меньшей мере, один подпроцессор из множества групп 202-20n подпроцессоров выбирают для выполнения заданной программы.
Контроллер потока памяти в каждой группе процессора управляет вводом данных в главное запоминающее устройство 103 по фиг.1 и выводом данных из него. Вторичный кэш используют как область памяти для обработки данных в каждой группе процессоров.
Как было описано выше, когда множество программ работает в одной или множестве операционных систем (ОС), присутствует множество потоков, определенных модулем выполнения программ, и при этом память, например основное запоминающее устройство (динамическое ОЗУ) по фиг.1, используется как ресурс, общий для потоков. Если один поток пытается выполнить процесс высвобождения для области памяти, в то время как к этой области памяти осуществляет доступ другой поток, возникает ошибка доступа. В известном уровне техники возникновение ошибки доступа предотвращают путем установки периода блокировки прерываний, но установка периода блокировки прерываний приводит к другой проблеме, такой как задержка процесса.
В соответствии с настоящим изобретением выполняют эффективную обработку данных путем выполнения соответствующего управления памятью в соответствии с потоком. Процесс выделения и высвобождения памяти соответствующего потока подробно описан ниже со ссылкой на фиг.3.
На фиг.3 представлен программный стек в устройстве обработки информации в соответствии с настоящим изобретением. Программный стек состоит из операционной системы (ОС) 310 и прикладной программы 320, выполняемой в операционной системе (ОС) 310. Операционная система (ОС) 310 включает в себя ядро 311, предназначенное для выполнения многоцелевого управления, управления системой файлов, управления памятью и процессами ввода и вывода.
Ядро 311 включает в себя менеджер 312 потока (диспетчер системного вызова), менеджер 313 области памяти (модуль управления кучей), предназначенный для выполнения управлением области памяти, и другой модуль 314 ядра.
В процессе объектно-ориентированного управления памятью ресурс обрабатывают как объект и управление памятью выполняют на основе области памяти, имеющей конечный размер, называемой кучей. Менеджер 313 области памяти (модуль управления кучей) управляет выделением объекта для кучи. Менеджер 313 области памяти (модуль управления кучей) высвобождает конечную кучу, эффективно выделяя область памяти (кучу) для каждого потока, запрашивающего кучу.
Типичный процесс выделения памяти для выделения области памяти потоку описан ниже со ссылкой на фиг.4 и 5. Как показано на фиг.4, доступ к области х 351 памяти, области у 352 памяти и области z 353 памяти, установленным как объекты по фиг.4, осуществляется через таблицу 350 идентификации (ИД, ID), установленную как информация-указатель на объекты программой выполнения потока.
Ядро ОС блокирует таблицу 350 ИД для предотвращения доступа второго потока к области памяти, доступ к которой в настоящее время осуществляется первым потоком, для исключения доступа из второго потока. Таким образом, второй поток не может выполнять доступ к памяти до тех пор, пока таблица 350 ИД не будет разблокирована, и требуется ожидание обработки.
На фиг.5 представлена таблица ИД, имеющая двухслойную структуру. Таблица 371 ИД используется для доступа к области х 361 памяти и области z 362 памяти и т.д. как к объектам. Область z 362 памяти, в свою очередь, содержит вторую таблицу b 372 ИД и разрешает доступ к области а 363 памяти и к области b 364 памяти с использованием второй таблицы b 372 ИД. Таким образом, ядро ОС блокирует таблицу ИД для предотвращения доступа другого потока к области памяти. Другой поток, таким образом, не может выполнить доступ к памяти до тех пор, пока не будет высвобождено блокирование, и обработка, таким образом, выполняется с задержкой.
Даже если отдельная область, такая как одна из области а 363 памяти и области b 364 памяти по фиг.5, не используется, ядро блокирует таблицу а 371 ИД в процессе управления памятью во время использования области х 361 памяти. В результате нельзя эффективно использовать доступную область памяти.
Настоящее изобретение преодолевает такое неэффективное использование памяти, обеспечивая, таким образом, возможность эффективного выделения памяти для каждого потока. Такой процесс выполняют с помощью менеджера 312 потока (диспетчера системного вызова) и менеджера 313 области памяти (модуля управления кучей) в ядре 311, как показано на фиг.3. Этот процесс подробно описан ниже.
Процесс, выполняемый менеджером 312 потока (диспетчером системного вызова), описан ниже со ссылкой на фиг.6 и 7.
Менеджер 312 потока (диспетчер системного вызова) выполняет потоки для каждого из процессоров, предусмотренных в устройстве обработки информации, для выполнения потока. Менеджер 312 потока (диспетчер системного вызова) содержит информацию управления потоком для каждого процессора отдельно.
Информация менеджера потока описана ниже со ссылкой на фиг.6 и фиг.7. На фиг.6 представлен список потоков, формирующий информацию управления потоком для каждого процессора. На чертеже показаны только списки потоков, соответствующие процессору 1 и процессору 2. Менеджер 312 потоков (диспетчер системного вызова) генерирует и содержит список потоков как информацию управления, соответствующую процессору, выполняющему обработку потока.
На фиг.6 (а) представлен список потоков как информация управления потоком процессора 1. Список потоков состоит из данных конкатенации информации времени входа отдельных потоков, работающих в гипервизоре в процессоре 1, и информации самого старшего времени входа. На фиг.6 (b) представлен список потоков как информация управления потоками процессора 2. Список потоков состоит из данных конкатенации информации времени входа отдельных потоков, работающих в гипервизоре в процессоре 2, и информации самого старшего времени входа. Информация времени входа потока относится к времени вызова функции операционной системы из прикладной программы, которая представляет собой различные программы обработки данных. В любом из списков другой процессор может обратиться к информации о самом старшем времени входа. Как описано выше, поток представляет собой модуль выполнения обработки данных, соответствующий логическому разделу. Для выполнения потока резервируют различные ресурсы, такие как процессоры и области памяти.
Когда процессор, предназначенный для выполнения потока, определен, для потока процессора выделяют доступную область памяти. Менеджер 312 потока (диспетчер системного вызова) распределяет потоки между процессорами, генерирует список потоков как информацию потока, относящуюся к выделению области памяти, и управляет потоками.
Гипервизор представляет собой привилегированный уровень, расположенный между логическими разделами и аппаратными средствами, и управляет логическим разделом. Поток представляет собой процесс, выполняемый логическим разделом. Описываемый поток, который выполняется модулем процессора со ссылкой на фиг.1 и 2, выполняется логическим разделом. Аппаратные ресурсы (ресурсы: вычислительные ресурсы, главный процессор, подпроцессор, запоминающее устройство, устройства и т.д.) выделяют для каждого логического раздела, и логический раздел выполняет процессы с использованием выделенных для него ресурсов.
Менеджер 312 потока (диспетчер системного вызова) записывает и содержит информацию времени входа, относящуюся к потоку, идентифицируемому гипервизором, который скомпонован как привилегированный уровень между логическим разделом и аппаратными средствами.
Информация списка потоков, содержащаяся менеджером 312 потока (диспетчером системного вызова), подробно описана со ссылкой на фиг.7. Как описано со ссылкой на фиг.6, список потоков, как информация управления потоками для каждого процессора, включает в себя данные конкатенации информации времени входа каждого потока и информации самого старшего времени входа. Информация управления включает в себя переменную 400, установленную для каждого процессора, и переменную 410, установленную для каждого потока, как показано на фиг.7. Как описано выше, информация времени входа потока соответствует времени вызова функции операционной системы из прикладной программы, выполняющей функцию различных программ обработки данных.
Переменная 400, установленная для каждого процессора, включают в себя заголовок (head) 401 и время 402 самого старшего входа (oldest_time). Заголовок (head) 401 содержит информацию указателя на передний элемент списка. Время 402 самого старшего входа (oldest_time) содержит самую старшую из информации времени входа в элементах, установленных в списке. Список соответствующим образом обновляют в соответствии с входом потока и ликвидацией потока. Если самое старшее время входа среди элементов, формирующих список, будет обновлено в процессе обновления, время 402 самого старшего входа (oldest_time) также обновляется вместе с ним. С учетом эффективности процесса доступа заголовок (head) 401 и время 402 самого старшего входа (oldest_time) содержат в различных линиях кэш. Линия кэш, в которой содержится заголовок (head) 401, содержит только переменные, для которых не требуется ссылка из другого процессора. Другой процессор может обращаться к линии кэш, содержащей время 402 самого старшего входа (oldest_time).
Переменная 410, установленная для каждого потока, включают в себя информацию 411 идентификации потока предшественника (predecessor) и информацию 412 времени входа (time). Информация 411 идентификации потока предшественника (predecessor) представляет собой идентификатор (например, указатель) информации предыдущего потока. Как показано на чертеже, список содержит информацию потока в порядке от потока, имеющего самое последнее время входа, до потока, имеющего самое старшее время входа. Каждую из информации потока идентифицируют по информации 411 идентификации потока предшественника (predecessor) и затем получают. Информация потока в передней части списка идентифицирована по заголовку 401 (head) самой старшей информации входа. Поскольку информация конечного потока не имеет предыдущего потока, [установлена информация идентификации потока предшественника (predecessor)=NULL]. Время 412 входа (time) обозначает время входа каждого потока.
Ниже со ссылкой на фиг.8 описана информация, управляемая менеджером 313 области памяти (модуль управления кучей). Как описано выше, в объектно-ориентированном процессе управления памятью ресурс обрабатывают как объект и управление памятью выполняют на основе области памяти, имеющей конечный размер, называемой кучей. Элемент, управляющий выделением объекта для кучи, представляет собой менеджер 313 области памяти (модуль управления кучей). Менеджер 313 области памяти (модуль управления кучей) высвобождает конечную кучу, эффективно выделяя область памяти (кучу) для каждого потока, запрашивающего кучу.
Менеджер 313 области памяти (модуль управления кучей), содержит информацию управления кучей, установленную для каждого процессора. Другими словами, количество модулей информации управления кучей равно количеству процессоров. Информация управления кучей содержит очередь высвобождения, как показано на фиг.8. Очередь высвобождения представляет собой информацию об области памяти (куче), для которой поступил запрос на высвобождение, но которая еще не была высвобождена.
Структура очереди высвобождения, содержащаяся менеджером 313 области памяти (модуль управления кучей), будет описана со ссылкой на фиг.8. Очередь высвобождения, показанная на фиг.8, установлена как информация управления кучей, установленная для каждого процессора. Очереди высвобождения, показанные на фиг.8, размещены индивидуально для соответствующих процессоров.
Очередь высвобождения установлена как список конкатенации информации 451 заголовка (release_queue_head) и компонента 460 очереди. Компонент 460 очереди содержит идентификатор 461 кучи (heap_ID), время 462 запроса на высвобождение (release_time), информацию 463 очереди преемника (successor) и информацию 464 области памяти.
Идентификатор 461 кучи (heap_ID) представляет собой информацию идентификации кучи, установленную как область памяти для каждого процессора. Время 462 запроса на высвобождение обозначает время запроса кучи, а именно время, в которое поток вырабатывает запрос на использование кучи. Информация 463 очереди преемника (successor) представляет собой указатель на последующую очередь в очереди высвобождения. Информация 464 области памяти представляет собой информацию доступа к области памяти, доступной для процессора, соответствующего идентификатору 461 кучи (heap_ID).
Информация 451 заголовка (release_queue_head) содержит идентификатор кучи (heap_ID) и установлена как информация, содержащая информацию указателя передней части очереди. Как показано на чертеже, все компоненты очереди получают путем отслеживания информации 463 очереди преемника (successor) каждого компонента очереди из информации 451 заголовка (release_queue_head).
Доступные процессоры выделены для каждого потока в процессе выделения ресурсов, при этом идентифицирована область кучи, соответствующая каждому процессору, и поток готов для выполнения. В этот момент времени компонент очереди установлен в очереди высвобождения, соответствующей выделенному процессору.
В соответствии с настоящим изобретением эффективное выделение памяти для потока выполняют под управлением менеджера 312 потока (диспетчера системного вызова) и менеджера 313 области памяти (модуль управления кучей) в ядре 311. Процесс менеджера 312 потока (диспетчер системного вызова) и менеджера 313 области памяти (модуль управления кучей) описан в ядре 311 со ссылкой на фиг.9.
Процесс менеджера 312 потока (диспетчер системного вызова) будет описан ниже со ссылкой на фиг.9-12. Менеджер 312 потока (диспетчер системного вызова) выполняет процесс входа информации потока в список потоков и процесс ликвидации информации из списка потоков, описанные со ссылкой на фиг.6 и 7.
Процесс входа информации потока выполняется сразу же после того, как прикладная программа вызывает функцию ОС. Более конкретно, поток для обработки данных с использованием процессора генерируют, когда прикладная программа вызывает функцию ОС. Поток устанавливают в состояние ожидания, в котором он ожидает высвобождения области памяти. Информацию потока, соответствующую потоку, вновь устанавливают как информацию управления с помощью менеджера 312 потока (диспетчера системного вызова).
Процесс ликвидации информации потока выполняют непосредственно перед тем, как управление будет передано в прикладную программу, с завершением процесса системного вызова ОС. Более конкретно, процесс выделения памяти выполняют с помощью ОС и управление передают в прикладную программу. Поток может быть выполнен с использованием процессора и области памяти, выделенной ОС. Когда управление возвращают прикладной программе с завершением системного вызова ОС, для потока выделяют область памяти (кучу). Менеджер 312 потока (диспетчер системного вызова), управляющий информацией потока в области памяти (куче), находящийся в состоянии ожидания, удаляет информацию потока из списка потоков. Этот процесс называется процессом ликвидации.
Последовательность процесса входа потока описана ниже со ссылкой на блок-схему последовательности выполнения операций, представленную на фиг.9, и схему, показанную на фиг.10. Процесс входа потока выполняют для добавления новой информации 510 потока в список потоков, как показано на фиг.10. Место добавления новой информации 510 потока по фиг.10 (а) обозначено информацией 501 заголовка, содержащейся в данных 500, относящихся к процессору. В этом процессе добавления создают список потоков по фиг.10 (b). Когда добавляют новую информацию 510 потока, необходимо обновить различную информацию в существующем списке потоков. На фиг.9 показана блок-схема последовательности выполнения операций процесса обновления.
Каждый этап блок-схемы последовательности выполнения операций по фиг.9 будет описан ниже. Последовательность этапов, показанная на фиг.9, выполняется в состоянии блокировки прерываний. На этапе S101 переменную [р] устанавливают как идентификатор процессора, выполняющего процесс входа. Как описано выше, менеджер 312 потока (диспетчер системного вызова) управляет списком потоков для каждого процессора. Для идентификации списка потоков при выполнении процесса входа потока переменную [р] устанавливают как идентификатор процессора, выполняющего процесс входа. На этапе S102 переменную [поток] устанавливают как идентификатор процессора, выполняющего процесс ликвидации. Более конкретно, переменный поток устанавливают как идентификатор потока 510 по фиг.10.
На этапе S103 устанавливают переменную [old_head] = информация идентификации потока предшественника (predecessor_thread_ID [thread] = head [p]).
Этот этап процесса означает, что величина [head [p]], установленная для заголовка 501 по фиг.10 (а), установлена для информации 511 потока - предшественника информации 510 нового потока и что величина [head [p]] установлена для переменной [old_head].
На этапе S104 устанавливают переменную [head [p]] = поток. Этот этап процесса означает, что величина, установленная для заголовка 501 по фиг.10 (а), установлена как идентификатор информации 510 нового потока для входящего потока.
На этапе S105 устанавливают текущее время для переменного времени [thread]. Этот этап процесса означает, что текущее время устанавливают в качестве информации 512 времени входа для информации 510 потока входа по фиг.10 (а).
_
На этапе S106 определяют, равна ли переменная [oldhead], установленная на этапе S103, значению NULL. Переменная [old_head], установленная на этапе S103, представляет собой информацию, которая установлена для заголовка 501 по фиг.10 (а), перед процессом входа. Если для заголовка 501 по фиг.10 (а) перед процессом входа установлено значение [NULL], в списке потоков отсутствует информация потока, и информация 510 нового потока по фиг.10 представляет собой единственную информацию потока, установленную для списка потоков. Самое старшее время 502 входа, установленное в данных 500, относящихся к процессору по фиг.10 (а), установлено для информации, установленной для информации 512 времени входа на этапе S105, а именно для времени [thread].
Если переменная [old_head] не равна NULL, информация потока, имеющая более старшее время входа, чем информация 510 нового потока, присутствует в списке потоков. Обработка, таким образом, заканчивается без обновления самого старшего времени 502 входа, содержащегося в данных 500, относящихся к процессору, показанному на фиг.10 (а).
Такой процесс входа приводит к тому, что в списке потоков информация 510 нового потока по фиг.10 (b) установлена в местоположении, доступном для заголовка 501 данных 500, относящихся к процессору.
Процесс ликвидации потока, выполняемый менеджером 312 потока (диспетчером системного вызова) будет подробно описан со ссылкой на фиг.11 и 12. Процесс ликвидации потока выполняют непосредственно перед тем, как управление будет возвращено в прикладную программу, после завершения процесса системного вызова, выполняемого ОС. Когда управление возвращают прикладной программе после завершения процесса выделения памяти, выполняемого с помощью ОС, поток может быть выполнен с использованием процессора и области памяти, выделенной с помощью ОС. Когда управление возвращают прикладной программе после завершения процесса выделения памяти, выполняемого с помощью ОС, для потока выделяют область памяти (кучу). Менеджер 312 потока (диспетчер системного вызова), находящийся в режиме ожидания, управляющем информацией потока, удаляет информацию потока из списка потоков. Выше был описан процесс ликвидации потока.
Последовательность обработки процесса ликвидации описана ниже со ссылкой на фиг.11. Последовательность этапов, показанных на фиг.11, выполняют в состоянии блокировки прерываний. Этапы S201 и 202 по фиг.11 выполняют для определения процессора и потока, выполняющего процесс ликвидации. На этапе S201 переменную [р] устанавливают для идентификатора, выполняющего процесс ликвидации. На этапе S202 переменную [поток] устанавливают для идентификатора текущего потока, выполняющего процесс ликвидации.
На этапе S203 определяют местоположение потока, предназначенного для обработки в процессе ликвидации. Более конкретно, определяют, следует ли выполнять этапы S211-S213 или этапы S221-S224, в зависимости от местоположения информации потока, для процесса ликвидации в списке потоков. Другими словами, процесс становится разным в зависимости от того, расположена ли информация потока, предназначенная для удаления, как показано на фиг.12 (а) или фиг.12 (b).
Как показано на фиг.12 (а), информация 550 потока, предназначенная для обработки в процессе ликвидации, расположена в передней части списка потоков, а именно в местоположении, определенном заголовком 541 данных 540, относящихся к процессору. Информация заголовка [head [p]] заголовка 541 данных 540, относящихся к процессору, установлена как информация идентификации [thread] для информации 550 потока, предназначенного для удаления. Ответ на определение, выполняемое на этапе S203, представляет собой "да", и, таким образом, выполняются этапы S211-S213.
Как показано на фиг.12 (b), информация 550 потока, предназначенная для обработки в процессе ликвидации, находится в местоположении, отличном от передней части списка потоков. В этом случае информация заголовка [head [р]] для заголовка 541 данных 540, относящихся к процессору, не установлена как информация идентификации [thread] для информации 550 потока, предназначенного для обработки в процессе ликвидации. Ответ на определение, выполняемое на этапе S203, будет "нет". Обработка переходит на этапы S221-S224.
Как показано на фиг.12 (а), информация 550 потока теперь находится в передней части списка потоков. На этапе S211 информация заголовка [head [р]] для заголовка 541 данных 540, относящихся к процессору, установлена для информации 551 идентификации потока предшественника [predecessor[thread]], установленной для информации 550 потока, предназначенной для обработки в процессе ликвидации. Как показано на фиг.12 (а), этот этап обработки соответствует установке информации, определяющей информацию 560 потока, в заголовке 541 данных 540, относящихся к процессору. Если предыдущий поток отсутствует в информации 550 потока, предназначенной для обработки в процессе ликвидации, информация 551 идентификации потока предшественника [predecessor[thread]] устанавливается равной [NULL]. Аналогично, значение [NULL] устанавливают для информации заголовка [head [p]] для заголовка 541.
На этапе S212 определяют, установлено ли значение NULL для информации заголовка [head [p]] для заголовка 541 данных 540, относящихся к процессору. Если будет определено, что значение NULL установлено, тогда в списке потоков с удаленной информацией 550 заголовка отсутствует информация потока. В этом случае для самого старшего времени входа [oldest_time] в данных 540, относящихся к процессору, устанавливают значение 0.
Если на этапе S212 будет определено, что значение NULL не установлено для информации заголовка [head [p]] заголовка 541 данных 540, относящихся к процессору, информация потока будет присутствовать в информации потока даже после удаления информации 550 потока. В этом случае обработка заканчивается без перезаписи самого старшего времени входа [oldest_time] данных 540, относящихся к процессору.
Как показано на фиг.12 (b), информация 550 потока, предназначенная для обработки в процессе ликвидации, находится в местоположении, которое не является передней частью списка потоков. На этапе S221 предполагают, что переменная [succ] представляет собой поток, находящийся в самой передней части потока ликвидации в списке потоков. При этом предполагается, что передняя часть списка представляет собой его передний конец. Другими словами, самый первый поток соответствует информации 570 потока по фиг.12 (b).
На этапе S222 информацию идентификации потока предшественника [predecessor [succ]] для потока, непосредственно предшествующего потоку ликвидации, обновляют как информацию идентификации потока предшественника [predecessor [thread]] для потока ликвидации. Этот этап обработки соответствует установке информации, определяющей информацию 580 потока для информации идентификации потока предшественника информации 570 потока, как показано на фиг.12 (b). Если в процессе ликвидации отсутствует поток предшественник для информации 550 потока, предназначенного для обработки, для информации 551 идентификации потока предшественника [predecessor [thread]] устанавливают значение [NULL] и, таким образом, значение [NULL] устанавливают для информации идентификации потока предшественника информации 570 потока.
На этапе S223 определяют, установлено ли значение NULL для информации идентификации потока предшественника [[predecessor [thread]] для потока ликвидации. Если будет определено, что значение NULL установлено, ликвидация информации 550 потока означает ликвидацию потока, имеющего самое старшее время входа. В этом случае время [succ] устанавливают для самого старшего времени входа [oldest_time] данных 540, относящихся к процессору, и обработка заканчивается. Другими словами, этот процесс выполняют, когда информация 580 потока по фиг.12 (b) отсутствует. Время 572 входа информации 570 потока устанавливают как самое старшее время входа [oldest_time] для данных 540, относящихся к процессору.
Если на этапе S223 будет определено, что значение NULL не было установлено для информации идентификации потока предшественника [[predecessor [thread]] для потока ликвидации, присутствует поток, имеющий более старшее время входа, чем информация 550 потока, предназначенная для обработки в процессе ликвидации, а именно информация 580 потока по фиг.12 (b). Обработка заканчивается без перезаписи самого старшего времени входа [oldest_time] данных 540, относящихся к процессору.
Процесс, выполняемый менеджером 313 области памяти (модуль управления кучей) будет описан ниже со ссылкой на фиг.13. Менеджер 313 области памяти (модуль управления кучей) содержит очередь высвобождения по фиг.8 как информацию управления кучей, установленную для каждого процессора. Очередь высвобождения представляет собой информацию об области памяти (куче), которая еще не была высвобождена, хотя уже поступил запрос на ее высвобождение.
Менеджер 313 области памяти (модуль управления кучей) выполняет процесс регистрации запроса на высвобождение и процесс выделения области памяти для области памяти (кучи). Процесс регистрации запроса на высвобождение области памяти (кучи) выполняют для добавления новой очереди к очереди высвобождения, описанной со ссылкой на фиг.8. Процесс выделения области памяти выполняют для выделения области памяти (кучи) для потока и очередь удаляют из очереди высвобождения в соответствии с необходимостью.
Процесс регистрации запроса на высвобождение области памяти описан ниже со ссылкой на блок-схему последовательности выполнения операций по фиг.13. На этапе S301 ИД кучи [hID] компонента очереди, установленной как новая очередь высвобождения, устанавливают как идентификатор кучи области памяти, запрашиваемой на высвобождение. Как было описано выше, очередь высвобождения как информацию управления области памяти устанавливают для каждой кучи, соответствующей процессору. Менеджер 313 области памяти (модуль управления кучей) высвобождает и выделяет область памяти для каждой кучи. Менеджер 313 области памяти (модуль управления кучей) устанавливает ИД кучи, для которой было запрошено высвобождение как ИД кучи очереди, которой должен быть добавлен к очереди высвобождения.
На этапе S302 заголовок очереди высвобождения (release_queue_head [hID]) устанавливают для последующей информации очереди (преемника) нового компонента очереди. Если на этапе S303 будет определено, что величина заголовка очереди высвобождения (release_queue_head [hID]) установлена равной последующей информации очереди (преемнику) области высвобождения, информацию указателя нового компонента очереди вводят в заголовок очереди высвобождения (release_queue_head [hID]) и разную информацию, такую как информация области памяти, устанавливают в очереди. Обработка, таким образом, заканчивается.
Если на этапе S303 будет определено, что величина заголовка очереди высвобождения (release_queue_head [hID]) не равна последующей информации очереди (преемнику) области высвобождения, обработка возвращается на этап S302 для повторения этапов S302 и S303. После проверки, что величина заголовка очереди высвобождения (release_queue_head [hID]) равна последующей информации очереди (преемнику) области высвобождения, различную информацию, такую как информация области памяти, устанавливают для очереди. Обработка, таким образом, заканчивается.
Определение на этапе S303, что величина заголовка очереди высвобождения (release_queue_head [hID]) не равна последующей информации очереди (преемнику) для области высвобождения, получают, когда другой процесс установки очереди одновременно выполняют с помощью другого процессора, с последующей информацией очереди (преемником) перезаписанной области высвобождения.
Новую очередь устанавливают в очереди на высвобождение в ответ на определение на этапе S303, что величина заголовка очереди высвобождения (release_queue_head [hID]) равна последующей информации очереди (преемнику) области высвобождения. Область памяти, соответствующую этому процессу, надежно резервируют (гарантируют).
Процесс выделения последовательности области памяти (кучи), выполняемый менеджером 313 области памяти (модуль управления кучей), описан ниже со ссылкой на фиг.14. На этапе S401 переменную [hID] устанавливают равной идентификатору процессора, выполняющего выделение области памяти. Процесс выделения области памяти выполняют для каждого процессора. Вначале идентифицируют процессор, для которого должна быть выделена область памяти.
На этапе S402 определяют, присутствует ли в памяти область неиспользованной памяти, равная размеру запрашиваемой для выделения области памяти. Более конкретно, менеджер 313 области памяти (модуль управления кучей) проверяет, присутствует ли в памяти неиспользуемая область, имеющая такой же размер, как и размер области памяти, требуемой потоком. Если будет определено, что область памяти доступна, обработка переходит на этап S405. Менеджер 313 области памяти (модуль управления кучей) выделяет область памяти, такую как область памяти обработки данных, для потока, соответствующего процессору, имеющему идентификатор, установленный на этапе S401.
Если на этапе S402 будет определено, что неиспользуемая память, имеющая такой же размер, что и размер памяти, запрашиваемой для выделения, не доступна в памяти, обработка переходит на этап S403. Менеджер 313 области памяти (модуль управления кучей) определяет на этапе S403, не меньше ли размер памяти, запрашиваемой для выделения, чем заданное пороговое значение. Если будет определено, что размер памяти, запрашиваемой для выделения, меньше, чем заданное пороговое значение, обработка переходит на этап S404. Менеджер 313 области памяти (модуль управления кучей) определяет на этапе S404, присутствует ли в области кучи неиспользуемая область памяти, удовлетворяющая размеру области памяти, запрашиваемой для выделения. Если будет определено, что неиспользуемая область памяти, удовлетворяющая размеру области памяти, запрашиваемой для выделения, присутствует в области кучи, менеджер 313 области памяти (модуль управления кучей) выполняет процесс выделения области памяти, установленной как неиспользуемая область кучи на этапе S405. Этот этап обработки выполняют, если запрашиваемый размер памяти меньше, чем заданное пороговое значение, и удовлетворяется условие выделения только неиспользуемой области кучи.
Если на этапе S403 будет определено, что запрашиваемый для выделения размер области памяти не меньше, чем заданное пороговое значение, или если на этапе S404 будет определено, что неиспользуемая область, удовлетворяющая размеру запрашиваемой для выделения области памяти, отсутствует в области кучи, после определения на этапе S403, что размер запрашиваемой для выделения области памяти меньше, чем заданное пороговое значение, для выделения области памяти выполняют этап S406 и последующие этапы. Этап обработки на этапе S406 выполняют путем ссылки на очередь высвобождения и список потоков.
На этапе S406 устанавливают переменную [head] как заголовок очереди высвобождения (release_queue_head [hID]) и значение 0 устанавливают для заголовка очереди высвобождения (release_queue_head [hID]).
На этапе S407 переменную [time] устанавливают равной минимальному из самых старших времен входа, а именно самым старшим временам входа, установленным в списке потоков, соответствующих всем процессорам.
На этапе S408 менеджер 313 области памяти (модуль управления кучей) сравнивает время запроса на высвобождение (release_time), установленное в каждом компоненте, отслеживаемом от каждого заголовка, с минимальным из самых старших времен входа, установленных в списке потоков, соответствующих всем процессорам, имеющим время [time], установленное на этапе S407, и выбирает только запрашиваемое время высвобождения (release_time), которое меньше, чем величина [time]. Менеджер 313 области памяти (модуль управления кучей) удаляет выбранное запрашиваемое время высвобождения [release_time] из очереди высвобождения, высвобождает области памяти, соответствующие этим очередям, и выделяет высвобожденные области памяти для потока, запрашивающего память.
При этом гарантируется, что высвобождение области памяти, запрашиваемой перед минимальным из самых старших времен входа всех процессоров, не является целью доступа для всех потоков. Путем выбора, высвобождения и последующего выделения области памяти процесс выделения области памяти выполняется безопасно.
На этапе S409 устанавливают информацию последующей очереди (преемника) для конечной части остальных очередей, которые не являются очередями, удаленными из очередей высвобождения на этапе S408, для заголовка очереди высвобождения (release_ queue_head [hID]). Если на этапе S410 будет определено, что величина заголовка очереди высвобождения (release_queue_head |hID]) установлена равной последующей информации очереди (преемника) конечной части очереди, указатель на переднюю часть очереди из остальных очередей, кроме очередей, удаленных из очередей высвобождения, устанавливают для заголовка очереди высвобождения (release_queue_head [hID]) на этапе S408.
Если на этапе S410 будет определено, что величина заголовка очереди высвобождения (release_queue_head [hID]) не установлена равной последующей информации очереди (преемника) конечной части очереди, обработка возвращается к этапу S409 для повторения этапов S409 и S410. После проверки того, что величина заголовка очереди высвобождения (release_queue_head [hID]) установлена равной последующей информации очереди (преемнику) конечной части очереди, менеджер 313 области памяти (модуль управления кучей) устанавливает разную информацию, такую как информация области памяти, для этой очереди. Обработка, таким образом, заканчивается.
Определение на этапе S410, что величина заголовка очереди высвобождения (release_queue_head [hID]) не установлена равной последующей информации очереди (преемнику) оконченной очереди, может привести к тому, что, когда другой процесс установки и удаления очереди выполняется другим процессором, последующая информация очереди (преемник) будет перезаписана.
Менеджер 313 области памяти (модуль управления кучей) выбирает только очередь, имеющую запрашиваемое время высвобождения (release_time), установленное в очереди высвобождения, меньшее, чем минимальное из самых старших времен входа, установленных в списке потоков, соответствующих всем процессорам. Менеджер 313 области памяти (модуль управления кучей) удаляет выбранные очереди из очередей высвобождения, высвобождает области памяти, соответствующие очередям, и выделяет области памяти для потока, запрашивающего память. Только область памяти, которая не установлена как цель доступа для всех потоков, будет надежно выбрана в процессе выделения памяти. Процесс выделения области памяти, выполняется, таким образом, для каждого потока так, что при этом отсутствуют ошибки доступа.
Процесс управления памятью, предназначенный для поддержки прикладной программы со слабым указателем, будет описан ниже. Структура очереди высвобождения, содержащейся менеджером 313 области памяти (модуль управления кучей), была описана со ссылкой на фиг.8. Очередь высвобождения устанавливают как список конкатенации информации 451 заголовка (release_queue_head) и компонента 460 очереди. Компонент 460 очереди содержит идентификатор 461 кучи (head_ID), время 462 запроса на высвобождение (release_time), информацию 463 последующей очереди (преемник) и информацию 464 области памяти.
Идентификатор 461 кучи (heap_ID) представляет собой информацию идентификации кучи в области памяти, установленную в соответствии с каждым процессором. Время 462 запроса на высвобождение (release_time) обозначает время, в которое вырабатывают запрос кучи, а именно время, в которое поток вырабатывает запрос на использование кучи. Информация 463 последующей очереди (преемника) представляет собой указатель на последующую очередь в очереди высвобождения. Информация 464 области памяти представляет собой информацию доступа к области памяти, доступной для процессора, соответствующего идентификатору 461 кучи (heap_ID).
Информация 451 заголовка (release_queue_head) содержит идентификатор кучи (heap_ID) и установлена как информация, содержащая информацию указателя передней части очереди. Как показано, все компоненты очереди приобретают путем отслеживания информации 463 последующей очереди (преемника) каждого компонента очереди от информации 451 заголовка (release_queue_head).
Доступные процессоры выделяют каждому из потоков в процессе выделения ресурсов, идентифицируют область кучи, соответствующую каждому процессору, и поток устанавливают в режим ожидания выполнения. В этот момент времени компонент очереди устанавливают в очередь высвобождения, соответствующую выделенному процессору.
Очередь высвобождения, описанную со ссылкой на фиг.8, сохраняют как информацию управления областью памяти. Для выделения области памяти время запроса на высвобождение, установленное для каждого компонента очереди в очереди высвобождения, сравнивают с самым старшим временем входа в списке потоков. Процесс выделения области памяти выполняют для компонента очереди со временем запроса на высвобождение, установленным перед самым старшим временем входа, и, таким образом, надежно выполняют для области памяти, которая не установлена как цель доступа во всех потоках. Процесс выделения области памяти, таким образом, выполняют для каждого потока так, что при этом отсутствует ошибка доступа.
Значение счетчика обращения (rf) можно использовать для определения, доступна ли область памяти. Счетчик обращения устанавливают для каждой кучи (области памяти). Если величина подсчета счетчика обращения равна 1 или больше, к куче (области памяти) можно обращаться. Другими словами, присутствует поток, ссылающийся на кучу.
Для обращения к куче (области памяти) получают адрес памяти из объекта указателя, который содержит информацию адреса кучи (области памяти). Полученный адрес памяти затем устанавливают в регистре. После этого выполняют доступ, в соответствии с адресом, установленным в регистре. Если другой поток пытается обратиться к памяти в середине этого процесса, информация памяти в месте назначения доступа может быть изменена по сравнению с планируемой. Однако надежное обращение к памяти выполняют путем сравнения времени высвобождения запроса, установленного в очереди высвобождения, описанной со ссылкой на фиг.8, с самым старшим временем входа в списке потоков.
Слабый указатель представляет собой один из типов объектов указателя. Слабый указатель представляет собой специальный указатель, который не увеличивает величину подсчета указанного выше счетчика обращения (rf), установленного в соответствии с кучей (областью памяти). Хотя слабый указатель обращается к куче (области памяти) так же, как это делают стандартные указатели, слабый указатель отличается от стандартных указателей тем, что число в величине подсчета счетчика обращения (rf), соответствующей куче (области памяти), не учитывают обращение слабого указателя. При этом может быть невозможно определить, следует ли обращаться к счетчику обращения (rf) или нет, на основе величины счетчика обращения. Если обращение к куче слабого указателя будет освобождено, информация адреса, соответствующая куче, содержащаяся слабым указателем, будет обновлена с установкой в 0 (NULL). Более конкретно, слабый указатель обновляет свою собственную информацию указателя в 0 (NULL), без влияния на счетчик обращения кучи.
Если информация указателя, содержащаяся слабым указателем, будет получена и сохранена в регистре во время обращения к памяти, информация, содержащаяся слабым указателем, будет немедленно заменена 0 (NULL). Последующее обращение к памяти с использованием такой информации указателя для слабого указателя больше не может выполняться, и информация указателя для слабого указателя будет потеряна. Модификация очереди высвобождения по фиг.8, описанная выше, не может быть выполнена без стыков. Эта проблема преодолевается так, как описано ниже.
Надежное обращение к памяти и обновление очереди высвобождения памяти с использованием слабого указателя описано ниже со ссылкой на фиг.15. На фиг.15 представлены слабый указатель и куча (область памяти) 600, имеющая область памяти обращения, к которой обращается слабый указатель. Информация 464 области памяти компонента 460 очереди в очереди высвобождения по фиг.8 имеет структуру кучи (области памяти) 600 по фиг.15.
Слабые указатели а-n обращаются к одной и той же области памяти обращения. Как показано, каждый из слабых указателей а-n содержит заголовок указателя, включающий в себя ИД указателя и переменные члена, такие как представлены ниже:
(a) преемник,
(b) предшественник,
(c) указатель объекта.
Указатель объекта представляет собой переменную члена объекта как информацию области памяти, к которой следует обратиться. Последовательность слабых указателей а-n обращается к одной и той же области памяти обращения и имеет один и тот же указатель объекта.
Преемник и предшественник представляют собой переменные указателя, которые соединяют в цепь слабые указатели, имеющие одну и ту же область памяти обращения к куче (области памяти), имеющей область памяти обращения, к которой обращается слабый указатель. Преемник представляет собой информацию идентификации одного из слабых указателей и кучи в качестве последующего объекта. Предшественник представляет собой информацию идентификации одного из слабых указателей и кучи в качестве предшествующего объекта.
Преемник и предшественник устанавливают в слабом указателе, который имеет ту же область памяти обращения и кучу (область памяти), имеющую область памяти обращения, к которой обращается слабый указатель. Двухстороннюю связь, а именно цепь, строят так, чтобы последовательность слабых указателей и куч соединялась в цепь. Такая цепь называется цепью слабых указателей.
Информация, относящаяся к флагу ликвидации и счетчику ликвидации, установлена в куче. Как описано выше, счетчик обращения имеет величину, соответствующую среде обращения в области памяти. Счетчик обращения не учитывает как обращение информацию, относящуюся к слабому указателю, но учитывает обращение других указателей, кроме слабого указателя. Флаг ликвидации используют для определения, не обращаются ли к счетчику обращения указатели, включающие в себя слабый указатель, другими словами, ликвидируют ли поток. Флаг ликвидации устанавливают в [1], если поток ликвидируют, и устанавливают в [0], если поток не ликвидируют. В процессе инициализации выделения новой памяти флаг ликвидации устанавливают в [0].
Таким образом, строят цепь слабых указателей. Величину указателя получают из слабого указателя. Более конкретно, получают указатель объекта, такого как переменная памяти объекта соответствующего адреса, требуемого для обращения к области памяти обращения. Процесс получения описан ниже со ссылкой на блок-схему последовательности выполнения операций, показанную на фиг.16.
На этапе S501, в процессе получения величины указателя из слабого указателя, определяют, удовлетворяются ли следующие условия (1) и (2). Условие (1) состоит в том, что указатель объекта для слабого указателя, а именно переменная члена объекта, не равен нулю. Условие (2) состоит в том, что величина счетчика обращения (rf), установленная в куче, связанная с цепью слабых указателей, равна или больше 1.
Если будет определено, что эти два условия удовлетворяются, обработка переходит на этап S502. Затем возвращают указатель объекта как переменную члена объекта, соответствующую адресу, требуемому для обращения к области памяти обращения, установленной в слабом указателе. Если будет определено, что эти два условия не удовлетворяются, обработка переходит на этап S503 для возврата [0].
Если будет определено, что указатель объекта, такой как слабый указатель, а именно переменная члена объекта, равен нулю или если будет определено, что величина подсчета счетчика обращения (rf), установленного в куче, связанного цепью слабых указателей, равна 0, на этапе S503 возвращают 0. Если величина подсчета счетчика обращений (rf) равна нулю, обращение с другими указателями, кроме слабого указателя, не выполняют. Однако при этом нельзя определить, выполняется ли обращение с помощью слабого указателя. Если величину указателя получают из слабого указателя, указатель объекта, представляющий собой слабый указатель, устанавливают равным нулю. Обращение к памяти с использованием информации указателя, который представляет собой слабый указатель, при этом больше нельзя выполнять. В случае когда информация указателя, такого как слабый указатель, отсутствует, обновление очереди высвобождения невозможно выполнить без стыков. Для исключения такой проблемы величину указателя при таком условии не получают.
Процесс очистки очереди высвобождения описан ниже со ссылкой на фиг.17. Очередь высвобождения была описана со ссылкой на фиг.8, и ею управляют с помощью менеджера 313 области памяти (модуля управления кучей). Как описано выше, в процессе объектно-ориентированного управления памятью источник обрабатывают как объект и управление памятью выполняют на основе области памяти, имеющей конечный размер, называемый кучей. Элемент, управляющий выделением объекта для кучи, представляет собой менеджер 313 области памяти (модуль управления кучей). Менеджер 313 области памяти (модуль управления кучей) соответствующим образом высвобождает конечную кучу, эффективно выделяя при этом область памяти (кучу) для каждого потока, запрашивающего кучу.
Менеджер 313 области памяти (модуль управления кучей) содержит информацию управления кучей, установленную для каждого процессора. Другими словами, количество модулей информации управления кучей равно количеству процессоров. Информация управления кучей содержит очередь высвобождения, показанную на фиг.8. Очередь высвобождения представляет собой информацию области памяти (кучи), для которой поступил запрос на высвобождение, но которая еще не была высвобождена.
При очистке очереди высвобождения выполняют специальный процесс, а именно процесс обновления в компоновке, содержащей слабый указатель. Процесс очистки очереди высвобождения описан ниже со ссылкой на блок-схему последовательности выполнения операций, показанную на фиг.17. Процесс, показанный на фиг.17, последовательно выполняют для всех объектов (компонентов очереди высвобождения), содержащихся в очереди высвобождения.
На этапе S601 очередь высвобождения опорожняют. Более конкретно, опорожняют переднюю часть очереди информации 451 заголовка (release_queue_head) по фиг.8 и эту очередь отсоединяют.
На этапе S602 время высвобождения объекта (компонент очереди высвобождения) устанавливают в очереди высвобождения, предназначенной для обработки, а именно запрашиваемое время высвобождения (release_time) сравнивают с самым старшим временем входа, установленным в списке потоков, соответствующих процессору. Если будет определено, что запрашиваемое время высвобождения (release_time) меньше, чем самое старшее время входа, обработка переходит на этап S603.
На этапе S603 определяют, удовлетворяется ли одно из следующих условий (а) и (b).
Условие (а) состоит в том, что флаг ликвидации, установленный в куче (области памяти), идентифицированный в ИД кучи объекта (компонента очереди высвобождения), предназначенного для обработки, установлен в состояние ликвидации.
Условие (b) состоит в том, что в цепи слабых указателей, соответствующей куче (области памяти), отсутствуют слабые указатели, другими словами, цепь слабых указателей является пустой.
Если одно из указанных выше условий (а) и (b) удовлетворяется, обработка переходит на этап S604. Процесс сбрасывают. Другими словами, область памяти, соответствующая объекту, установленному в очереди высвобождения, высвобождают и объект (компонент очереди высвобождения) удаляют из очереди высвобождения.
Если на этапе S603 будет определено, что ни одно из условий (а) и (b) не удовлетворяется, обработка переходит на этап S621. Величину указателя объекта, такую как переменная члена объекта слабого указателя, содержащегося в цепи слабых указателей, установленной в соответствии с кучей, устанавливают равной [0]. На этапе S622 флаг ликвидации устанавливают равным [1]. На этапе S623 текущее время вводят в качестве времени высвобождения объекта (компонент очереди высвобождения), установленного в очереди высвобождения, а именно запрашиваемое время высвобождения (release_time). На этапе S624 объект (компонент очереди высвобождения) снова устанавливают в очередь высвобождения.
Если на этапе S602 будет определено, что время высвобождения объекта (компонент очереди высвобождения), установленное в очереди высвобождения для обработки, а именно время высвобождения запроса (release_time), не меньше, чем самое старшее время входа, установленное в списке потоков, соответствующем процессору, обработка переходит на этап S611. На этапе S611 определяют, равен ли нулю счетчик обращения (rf), установленный в куче (области памяти) идентифицированной ИД кучи объекта. Если будет определено, что счетчик обращения равен нулю, обработка переходит на этап S624. Объект (компонент очереди высвобождения) снова устанавливают в очередь высвобождения.
Процесс по фиг.17 выполняют с помощью менеджера 313 области памяти (модуль управления кучей) в операционной системе 310 по фиг.3. В компоновке со слабым указателем, который содержат как указатель, обращающийся к области памяти, менеджер 313 области памяти (модуль управления кучей) анализирует слабый указатель, обращающийся к области памяти, соответствующей компоненту очереди, содержащемуся в очереди высвобождения, и цепь слабых указателей, состоящих из области памяти, содержащей область обращения слабого указателя. Если менеджер 313 области памяти (модуль управления кучей) определяет, что в цепи слабых указателей отсутствует слабый указатель или что флаг ликвидации области памяти, содержащейся в цепи слабых указателей, установлен в состояние ликвидации, компонент очереди сбрасывают из очереди высвобождения и высвобождают область памяти, соответствующую этому компоненту очереди.
Процесс по фиг.17 также выполняют для объекта (компонент очереди высвобождения), установленного в очереди высвобождения. При выполнении этого процесса очистки, выполняемого в компоновке, содержащей слабый указатель, очередь высвобождения надежно обновляют, запрашиваемое время высвобождения, установленное в очереди высвобождения, надежно сравнивают с самым старшим временем входа списка потоков и выполняют обращение к памяти таким образом, что не возникают ошибки.
Настоящее изобретение было описано со ссылкой на конкретные варианты выполнения. Очевидно, что специалист в данной области техники сможет выполнить изменения и модификации вариантов выполнения настоящего изобретения без отхода от объема настоящего изобретения. Варианты выполнения настоящего изобретения были описаны только с целью примеров, и их не следует рассматривать как ограничение объема настоящего изобретения. Для того чтобы понять объем настоящего изобретения, следует обратиться к формуле изобретения.
Описанная выше последовательность этапов может быть выполнена в виде программных средств, аппаратных средств или их комбинаций. Если последовательность этапов будет выполнена с использованием программных средств, программа, формирующая программное средство, может быть установлена с носителя записи или через сеть в компьютере, выполненном в виде аппаратной структуры, или, например, в компьютере общего назначения.
Программа может быть заранее записана на один из жесткого диска и ПЗУ (постоянное запоминающее устройство), используемое как носитель записи. Программа также может быть временно или постоянно записана на съемные носители записи. Носители записи включают в себя гибкий диск, CD-ROM (память на компактном диске, предназначенном только для чтения), диск МО (магнитооптический диск), DVD (цифровой универсальный диск), магнитный диск, полупроводниковое ЗУ и т.д. Такой съемный носитель может поставляться в виде так называемого упакованного программного обеспечения.
Программа может быть установлена со съемного носителя записи на компьютер, как указано выше. Кроме того, программа может быть передана по беспроводному каналу в компьютер с сайта загрузки. Программа также может быть передана по кабелю через сеть, такую как сеть ЛВС (локальная вычислительная сеть) и сеть Интернет. Программу затем принимают с помощью компьютера и устанавливают на носитель записи, такой как жесткий диск, в компьютере.
Этапы процесса, представленные в этом описании, выполняют последовательно в порядке временной последовательности, указанной выше. В качестве альтернативы этапы могут быть выполнены параллельно или отдельно. В этом описании система относится к логической системе, состоящей из множества устройств, и элементы каждого устройства не обязательно содержатся в одном корпусе.
Промышленная применимость
Как описано выше, в соответствии с компоновкой настоящего изобретения список потоков информации потока, содержащей информацию времени входа, которая записана для каждого потока, причем поток представляет собой модуль обработки данных, сохранен как информация управления потоком, и очередь высвобождения, содержащую время запроса на высвобождение, которое записано для каждой области памяти в отношении области памяти, для которой поступил запрос на высвобождение, но которая еще не была высвобождена, сохраняют как информацию управления областью памяти. Время запроса на высвобождение, установленное в каждом компоненте очереди, содержащемся в очереди высвобождения, сравнивают с самым старшим временем входа каждого компонента очереди в списке потоков во время процесса выделения области памяти. Процесс выделения памяти выполняют только для области памяти, соответствующей компоненту очереди, со временем запроса на высвобождение, установленным перед самым старшим временем входа. Только область памяти, которая не является целью обращения всех потоков, надежно выбирают и подвергают процессу выделения. Процесс выделения области памяти безопасно выполняют таким образом, что ошибки доступа не возникают в каждом из потоков.