Алгоритм пере-нумерации заданий
Хотелось бы, чтобы уважаемая публика проверила правильность моих рассуждений. Если кто найдёт ошибку в алгоритме ? буду очень признателен.
Thanx, Glen
Постановка задачи
Есть некий модуль, куда поступают с вышестоящего уровня ЗАДАНИЯ. Наш модуль выполняет их и сообщает вышестоящему уровню об их завершении. Понятно, новые задания вышестоящий уровень может присылать и не дожидаясь завершения предыдущих; таким образом, в нашем модуле может скапливаться несколько выполняемых заданий. Для их хранения мы организуем некую очередь. Что это за задания ? неважно; важно, что у каждого задания есть идентификатор ? назовём его taskID. Идентификаторы представляют из себя целые числа: от 0 до MAX_ID (напр., 2^32-1). Вышестоящий уровень обеспечивает уникальность taskID ? то есть, пока задание присутствует в нашем модуле, мы не получим новое с таким же taskID. Наш модуль сообщает вышележащему уровню о завершении заданий НЕ обязательно в том же порядке, в котором они к нам поступали.
В свою очередь, наш модуль разбивает каждое из заданий на несколько более мелких и отправляет их на выполнение в некий нижележащий уровень. Дисциплина общения с ним такая же ? мы выдаём задание в нижележащий уровень, потом через какое-то время он нам сообщит о его выполнении. В промежутке между этими событиями мы можем выдать ещё задания в нижележащий уровень. Нижележащий уровень сообщает о выполнении под-заданий НЕ обязательно в том же порядке, в котором мы их ему посылаем. Кроме того, разбиение задания на под-задания происходит НЕ СРАЗУ ЖЕ после его поступления в наш модуль ? это разбиение может происходить произвольно: всё время пока задание находится в нашем модуле. Скажем, в данный момент было создано одно под-задание; потом (когда в модуль поступят ещё несколько заданий) ? ещё одно и т.д. Как только все под-задания некоего задания завершены, наш модуль считает завершённым и это задание и сообщает ою этом в вышележащий уровень.
У заданий нижележащего уровня тоже есть taskID и они тоже должны быть уникальными ? пока нижележащий уровень не сообщил о завершении некоего задания, мы не имеем права дать новому поступающему в него заданию такое же значение taskID. Эти taskIDs под-заданий имеют значения в таком же диапазоне [0, MAX_ID], что и taskIDs заданий; на их хранение выделяется столько же бит (например, 32 бита).
Поэтому нашему модулю нужно как-то нумеровать taskIDs для создаваемых им заданий. Задача: как это сделать?
Мы не можем применить элементарное решение типа ?taskID под-задания составляется из <taskID родительского задания> плюс <порядковый номер под-задания в пределах родительского задания>? - как сказано выше, на хранение taskID под-заданий отведено РОВНО столько же бит, сколько и на хранение taskID родительских заданий. Это ? условие задачи и потому обсуждению не подлежит.
Алгоритм:
Дополнительное ограничение: для применения этого алгоритма мы считаем, что за время существования любого задания в нашем модуле в него (модуль) может поступить не более чем (MaxTasks-1) новых заданий. В свою очередь, каждое задание может быть разбито на не более чем MaxSubs под-заданий.
Если также считать, что (2*MaxTasks-1)*MaxSubs < MAX_ID, то можно применить следующий простой алгоритм:
(1) У нас есть некая переменная gen_taskID с начальным значением 0.
(2)При создании нового под-задания : -даём ему taskID со значением gen_taskID;
-если gen_taskID достиг значения MAX_ID, присваиваем ему 0; иначе делаем ++gen_taskID.
Докажем, что при этом не произойдёт пересечения нового присваиваемого идентификатора с каким-то из существующих в данный момент taskID.
Доказательство:
Пусть в некий момент времени taskID самого старого из обрабатываемых под-заданий имеет значение n_Start; taskID самого последнего из обрабатываемых под-заданий имеет значение nEnd. Номера между n_Start и nEnd образуют ПОЛОСУ НОМЕРОВ. Причём возможна как ситуация, когда n_Start >= nEnd, так b ситуация, когда n_Start < nEnd. Внутри полосы могут присуствовать как занятые номера, так и дырки. Дырки возникают потому, что номера могут освобождаться не в том порядке, в котором они выделялись.
Пример: пусть MaxTasks равно 2 и MaxSubs равно 2. Сначала в модуль поступило задание T1, разбитое на подзадания S1_1 и S1_2. Потом ? задание T2, разбитое на S2_1 и S2_2. Потом T2 завершилось, а T1 ? ещё нет. Номера, соответствующие S2_1 и S2_2 освободились, но более ранние S1_1 и S1_2 ? нет. Потом в модуль поступает задание T3, разбиваемое на S3_1 и S3_2. Ширина полосы номеров стала 6: сначала идут номера, соответствующие S1_1 и S1_2, потом ? два уже неиспользуемых номера; потом - номера, соответствующие S3_1 и S3_2.
Обозначим через T_Start задание, под-заданию которого принадлежит номер n_Start (отметим, что T_Start ? не обязательно самое раннее из находящихся в модуле заданий). Все остальные ? помимо n_Start ? номера из полосы (как занятые, так и дырки) относятся, очевидно, к 3-м категориям:
1)Порождённые заданием T_Start. 2)Порождённые заданиями, поступившими после T_Start. Какие-то из этих заданий могли уже закончиться, а какие-то ? ещё нет. 3)Порождённые заданиями, поступившими до T_Start. Какие-то из этих заданий могли уже закончиться, а какие-то ? ещё нет.
Номеров, относящихся к 1-й категории, может быть не более (MaxSubs-1).
Номеров, относящихся ко 2-й категории, может быть не более (MaxTasks-1)*MaxSubs. В самом деле ? раз T_Start ещё находится в модуле, после него поступить на данный момент могло не более чем (MaxTasks-1) заданий, которые все, вместе взятые, могли породить не более чем (MaxTasks-1)*MaxSubs под-заданий и, соотв., занять не более чем (MaxTasks-1)* MaxSubs номеров и/или дырок в полосе.
Номеров, относящихся к 3-й категории, может быть не более (MaxTasks-1)*MaxSubs. В самом деле, только (MaxTasks-1) заданий, поступивших непосредственно перед T_Start, могли оставить след в данной полосе. Все более ранние задания завершились ещё до поступления в модуль задания T_Start и, таким образом, их номера (или порождённые их номерами дырки) никак не могут присутствовать на данный момент в полосе. Эти (MaxTasks-1) заданий, поступивших непосредственно перед T_Start, могли породить максимум (MaxTasks-1)*MaxSubs под-заданий и, соотв., занять не более (MaxTasks-1)*MaxSubs номеров в полосе.
Итого, сложив все три категории, получаем, что максимально возможная на данный момент ширина полосы составит (2*MaxTasks-1)*MaxSubs номеров.