LINUX.ORG.RU

Алгоритм пере-нумерации заданий


0

0

Хотелось бы, чтобы уважаемая публика проверила правильность моих рассуждений. Если кто найдёт ошибку в алгоритме ? буду очень признателен.

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 номеров.


>Хотелось бы, чтобы уважаемая публика проверила правильность моих рассуждений

>Доказательство:

Формальный маразм. Подожди немного и это пройдет.

anonymous
()
Ответ на: комментарий от ukez

Уж пробовал (на другом форуме). Тогда посыпались жалобы, что сформулировано недостаточно подробно :-)

Glen
() автор топика
Ответ на: комментарий от ukez

если проще: нашему модулю нужно как-то нумеровать taskIDs для создаваемых им под-заданий. Простой метод комбинирования taskID родительского задания с порядковым номером под-задания не пойдёт: taskID родительских заданий занимают столько же бит, сколько и taskID дочерних под-заданий.

Glen
() автор топика
Ответ на: комментарий от Die-Hard

Вдогонку:

Ты, кстати, так и делаешь, только полагаясь на "авось", что хвост голову не догонит. Так нельзя: если распределение числа одновременно обрабатываемых заданий нормальное (а оно у тебя будет нормальное (:-)), то довольно скоро твой алгоритм сглючит. Тебе придется контролировать не только голову (gen_taskID) но и хвост (наименьший taskID modulo MAX_ID). И непонятно, что делать, когда голова догонит хвост.

Лучше так:

Храни использованные чиселки в хэше, а размер хэша положи равным "мат. ожидание числа одновременно обрабатываемых заданий + дисперсия". Просто "на глаз"; если будут коллизии, нужно размер понемногу увеличить. Если хэш будет достаточным, то при использовании простейшей хэш-функции gen_taskID % (размер хэша) коллизий почти не будет.

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

>Ты, кстати, так и делаешь, только полагаясь на "авось", что хвост >голову не догонит.

Никоим образом - бОльшая часть из моего длиннющего сообщения и посвящена доказательсву того, что НЕ догонит при следующих ограничениях:

(1) за время существования любого задания в нашем модуле в него (модуль) может поступить не более чем (MaxTasks-1) новых заданий. В свою очередь, каждое задание может быть разбито на не более чем MaxSubs под-заданий.

(2) (2*MaxTasks-1)*MaxSubs < MAX_ID

И эти ограничения тоже упомянуты.

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

Glen
() автор топика
Ответ на: комментарий от Glen

2Glen

> Никоим образом - бОльшая часть из моего длиннющего сообщения и посвящена доказательсву того, что НЕ догонит при следующих ограничениях:

Я и говорю: на "авось" ;)

Где Вы в своем алгоритме что-либо проверяете? А, между тем,

1. А что делать, если ограничения будут нарушены? Все равно надо наложенные ограничения проверять на каждом шаге!

2. Ограничения совершенно искуственные и ненужные. Очевидно, из них следует

(MaxTasks-1)*MaxSubs < MAX_ID -MaxTasks*MaxSubs < MAX_ID

То есть, достаточно принять менее ограничивающее условие:

(MaxTasks-1)*MaxSubs < MAX_ID

и просто раздавать номера от 0 до MAX_ID -1. Как только gen_taskID ==MAX_ID, значит, ограничения оказались нарушены.

> Но меня интересовало именно такое решение, когда НЕ надо осуществлять проход по поисковым структурам (и следовательно, терять на это время). А та же хэш-таблица требует времени на поиск в ней.

Наверное, я не совсем точно выразился. Еще раз:

На "прохождение" хэша в данной конкретной проблеме время тратится только на разрешение коллизий, посколку вычисление хэш-функции сводится к операции взятия остатка. А другая специфика данной задачи состоит в том, что коллизии будут _крайне_ редки.

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

Вдогонку:

Чувствую, надо подробнее :-)

(MaxTasks-1)*MaxSubs -- _максимальное_ количество ID, которое может быть распределено за все время жизни системы. Поэтому условия (MaxTasks-1)*MaxSubs < MAX_ID _заведомо_ достаточно для того, чтобы не переполнить пул. Если ++gen_task вдруг оказалось равно IDMAX_ID, то значит, исходные ограничения не выполняются.

Die-Hard ★★★★★
()

Честно говоря, мутное условие и мутный алгоритм.

1. Имеется ли контроль над алгоритмом выделения taskID'ов "вышестояшим уровнем"?

2. Необходимо ли нулевое пересечение множеств taskID и subtaskID или достаточно уникальности taskID'ов и subtaskID'ов отдельно?

3. Могут ли под-задания "нижележащему уровню" выдаваться кем-то, кроме рассматриваемого экземпляра "модуля"?

В простейшем случае, можно было бы просто брать subtaskID'ы из ряда неотрицательных целых.

watashiwa_daredeska ★★★★
()
Ответ на: комментарий от watashiwa_daredeska

watashiwa_daredeska:

> Честно говоря, мутное условие и мутный алгоритм.

Да нет. Мутное доказательство и формулировка. Алгоритм тривиальный.

Die-Hard ★★★★★
()
Ответ на: комментарий от Glen

Glen :

> Ну и на том спасибо :-)

Да пожалуйста :-)

Только больше я Вам не помощник. Надо ж математику знать хотя бы на уровне 4 класса!

Die-Hard ★★★★★
()
Ответ на: комментарий от watashiwa_daredeska

"1. Имеется ли контроль над алгоритмом выделения taskID'ов "вышестояшим уровнем"? " - НЕТ

"2. Необходимо ли нулевое пересечение множеств taskID и subtaskID или достаточно уникальности taskID'ов и subtaskID'ов отдельно? " - достаточно уникальности subtaskID. А taskID всё равно генерирует Не наш модуль.

"3. Могут ли под-задания "нижележащему уровню" выдаваться кем-то, кроме рассматриваемого экземпляра "модуля"? " - НЕТ.

"В простейшем случае, можно было бы просто брать subtaskID'ы из ряда неотрицательных целых." - опять же: что делать когда достигнем максимально возможного значения MAX_VAL ? На ноль переходить? Так это и есть тот алгоритм, что я описал в самом начале. Моя просьба состояла в том, чтобы проверить правльность его доказательства (утрверждения типа "это и так ясно" мне недостаточно).

Thanx, Glen

Glen
() автор топика
Ответ на: комментарий от Die-Hard

"может быть распределено за все время жизни системы" совершенно неверно. Время жизни системы неограниченно. Может быть Вы хотели сказать - "за время присуствия некоего задания (или под-задания)" в нашем модуле?

Thanx, Glen

Glen
() автор топика
Ответ на: комментарий от Glen

Ага теперь чуть-чуть понятнее :) Т.е. это просто доказательство некоторого условия, для простейшего алгоритма, при соблюдении которого голова никогда не догонит хвост.

Ну, тогда, вроде более менее сходится :)

watashiwa_daredeska ★★★★
()
Ответ на: комментарий от Glen

2Glen :

Извиняюсь, неверно понял проблему.

Выкладки верные, но, все равно, в реальности задача контроля принятых ограничений будет более сложной и долгой нежели простые отметки в хэше.

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

>при использовании простейшей хэш-функции gen_taskID % (размер хэша) >коллизий почти не будет

Да, это я не учёл. Дейтсвиттельно, функция <gen_taskID % (размер хэша)> при ПОСЛЕДОВАТЕЛЬНОМ наращивании gen_taskID обещает дать мало коллизий.

Что ж, тогда, пожалуй,и использование хэш-таблицы тоже не сильно затормозит программу.

Glen
() автор топика
Ответ на: комментарий от Glen

Glen:

> ...пожалуй,и использование хэш-таблицы тоже не сильно затормозит программу.

Да не затормозит, а ускорит!

Еще раз:

1. При гауссовом распределении (а что еще можно ожидать?) придется так или иначе контролировать переполнение gen_taskID % MAX_ID, поскольку с ненулевой вероятностью может встретиться что угодно.

2. Контроль типа if(хэш[gen_taskID % (размер хэша)] свободен) + if( хэш[id].next == NULL ){освобождаем хэш[id]} при завершении подзадания минимален, поскольку он O(1), а не O(n), как в случае "помодульного" контроля (n -- число активных модулей).

3. Если размер хэша укладывается в "матожидание + сигма", то вероятность коллизий мала и оверхедом на их обработку можно пренебречь.

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

>При гауссовом распределении

Ясейчас вряд ли вспомню, что такое "гауссово распределение"; но очевидно, это - равномерное распределение, так?

Ну, как раз в нашем случае занятые номера под-заданий будут распределены по всему простарнству номеров [0, MAX_ID] НЕ равномерно - они будут следовать один за другим; понятно, с некоторым количеством дырок между занятыми номерами. Ведь мы же намерены поиск нового номера начинать ВВЕРХ от сохранённого предыдущего gen_taskID - и скорее всего, уже (gen_taskID + 1) будет НЕ занят.

Glen
() автор топика
Ответ на: комментарий от Glen

Glen (Score: 54 MaxScore: 54) (*) (05.07.2005 18:49:14):

> Ясейчас вряд ли вспомню, что такое "гауссово распределение"; но очевидно, это - равномерное распределение, так?

Нет, конечно!

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

Гауссово (т.н. "нормальное") распределение обычно всегда имеет место быть (с небольшими поправками на конечность времени ожидания и несимметрией в силу принципиальной положительности n). Главная особенность, что с ненулевой (но малой) вероятностью мы имеем сколь угодно большие отклонения от n.

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

А, понятно. Спасибо за объяснение.

>при размере хэша несколько большем, чем n+сигма, коллизии будут редки.

Верно, но ? только когда на ДАННОМ наборе входной информации ДАННАЯ хэш-функция обеспечивает более-менее равномерное распределение входных значений по хэш-таблице. В описанном выше нашем случае это, очевидно, так. Но вообще говоря ? НЕ обязательно; может случиться такая неприятная ситуация, когда, скажем, 80% от входных значений попали в небольшой ? скажем, 20% от общего числа ? диапазон элементов хэш-таблицы. Вот огда коллизий будет много.

Glen
() автор топика
Ответ на: комментарий от Glen

2Glen (06.07.2005 15:46:32):

> ...только когда на ДАННОМ наборе входной информации ДАННАЯ хэш-функция обеспечивает более-менее равномерное распределение входных значений по хэш-таблице.

Нет, в данной ситуации равномерного распределения как раз не нужно.

gen_task % hash_size будет "головой", которая будет догонять "хвост". Коллизии будут возникать только в том случае, если "голова" догонит "хвост", т.е. редко.

В случае коллизии появится своеобразная "дырка": после освобождения вызвавшего коллизию ID этот ID не может быть сразу повторно использован. Дырка исчезнет при следующем цикле, когда gen_task, перевалив через MAX_ID, вновь станет равным этому ID.

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

>Нет, в данной ситуации равномерного распределения как раз не >нужно.

>gen_task % hash_size будет "головой", которая будет догонять "хвост". >Коллизии будут возникать только в том случае, если "голова" догонит >"хвост", т.е. редко.

Да, согласен. Действительно, "отсутствие коллизий" не обязательно привязано к "равномерному распределению"; это я не подумавши сказал.

Glen
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.