powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Посоветуйте алгоритм распределения ресурсов
18 сообщений из 18, страница 1 из 1
Посоветуйте алгоритм распределения ресурсов
    #37600545
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Задача, в общем, такова: Есть программа передающая файлы через сеть. Для каждого файла создается специальный класс, который передает данные через несколько соединений. Скорость передачи непосредственно зависит от количества соединений. Для каждого соединения создается своя нить. У класса есть функции: добавить одно соединение, и закрыть одно соединение. У каждого файла есть приоритет: высокий, средний или низкий. Общее количество соединений может быть ограничено. Подскажите алгоритм, который можно использовать для распределения соединений между файлами согласно их приоритетам.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37600584
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RedCatXДля каждого файла создается специальный класс, который передает данные через несколько соединений. Специальный класс ? Может все-же объект?

А вообще, твоя задача это классическая задача о рюкзаке: http://en.wikipedia.org/wiki/Knapsack_problem
Принципы ее решения обсуждаются тут на форуме как минимум раз в месяц.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37600681
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Но максимальное количество соединений может быть не ограничено, или ограничено, но неявно: например, пропускной способностью канала или загруженностью серверов на данный момент, а также их настройками. Задача о рюкзаке все еще подходит для решения этой проблемы?
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37601122
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Да и без этого, у меня не получается сопоставить задачу о рюкзаке с моей проблемой... Там же как я понял, есть рюкзак некоторого заданного объема, у предметов есть объем и стоимость, задача состоит в том чтобы в рюкзак набрать предметов на максимально возможную общую стоимость. Как это сопоставить с моей задачей я что-то не могу понять...
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37601233
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну а у тебя что?
Есть пропускная способность физического канала. = объем рюкзака
От нее зависит количество возможных соединений. = количество вещей
Соединения у тебя напрямую завязаны на файлы. Файлы имеют приоритет = вес вещей
Тебе нужно передать как можно больше "важных" файлов и по возможности не забывать про "неважные". Так?

Ну значит в самом начале - рюкзак пуст, набиваешь его.
Как только один файл закончился, делаешь перераспределение - добиваешь оставшимися в очереди файлами в порядке их приоритета. Если хочешь чтобы важные файлы останавливали пересылку неважных - по приходу нового важного файла в очередь делаешь принудительную очистку всего рюкзака и заново его наполняешь.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37601240
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
White OwlНу а у тебя что?
Есть пропускная способность физического канала. = объем рюкзака
От нее зависит количество возможных соединений. = количество вещей
Соединения у тебя напрямую завязаны на файлы. Файлы имеют приоритет = вес вещей
А что тогда стоимость вещей? И где решение задачи: распределение количества соединений между файлами согласно их приоритету?
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37601302
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RedCatXА что тогда стоимость вещей? И где решение задачи: распределение количества соединений между файлами согласно их приоритету?У тебя один файл посылается по нескольким соединениям одновременно или по одному? Если по нескольким - обзови количество соединений на один файл его стоимостью и все.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37601312
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
White OwlУ тебя один файл посылается по нескольким соединениям одновременно или по одному? Если по нескольким - обзови количество соединений на один файл его стоимостью и все.
Количество соединений на один файл - это та величина которую нужно найти. Нужен алгоритм, который в соответствии с приоритетами файлов устанавливает им нужные количества соединений. Это как закачки в uTorrent или DownloadMaster (там можно выставлять приоритеты закачек).
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37601785
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RedCatXКоличество соединений на один файл - это та величина которую нужно найти.Хорошо.
Файл размером один байт - сколько соединений нужно чтобы его переслать?
Файл размером сто гигабайт - сколько соединений нужно чтобы его переслать?
Два файла одинакового размера, но с разными приоритетами - насколько больше соединений будет у одного файла чем у другого?

Сколько соединений ты в принципе можешь создать? Не забывай что у тебя всего одно физическое соединение с провайдером и чем больше логических соединений ты создашь - тем медленнее они все будут работать. Обойти ограничение физического канала в принципе не возможно.

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

Ты все еще не видишь параллелей с рюкзаком? :)


RedCatXНужен алгоритм, который в соответствии с приоритетами файлов устанавливает им нужные количества соединений. Это как закачки в uTorrent или DownloadMaster (там можно выставлять приоритеты закачек). Ты уверен что действительно нужно много соединений ? Множественные параллельные соединения это очень редко дает прирост в скорости и только на больших расстояниях.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37602651
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
White OwlФайл размером один байт - сколько соединений нужно чтобы его переслать?
Файл размером сто гигабайт - сколько соединений нужно чтобы его переслать?

Файл разбивается на секции вне зависимости от его размера (но конечно файл в 1 байт разбить просто невозможно), для загрузки каждой секции открывается соединение. Во время передачи допустимо создавать новые секции или приостанавливать существующие, таким образом устанавливая количество соединений. Собственно нужно сделать чтобы файл с высоким приоритетом получал большее количество соединений чем файл с низким. Никаких ограничений нет, или они неизвестны. Как и когда перераспределять количество соединений я не знаю.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37602729
JoFan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
RedCatX,

Разве от количества соединений будет расти скорость передачи ?
Или в задаче нужно передать один файл на несколько хостов-приемников ?
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37602928
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
JoFanРазве от количества соединений будет расти скорость передачи ?
Или в задаче нужно передать один файл на несколько хостов-приемников?

Да, от количества соединений зависит скорость передачи. Попробуйте, например, скачать файл по HTTP сначала через одно соединение (встроенный в браузер менеджер загрузок), а потом скачайте его через несколько соединений (сторонний менеджер загрузок, например, ReGet). В первом случае скорость будет около 20% от пропускной способности вашего интернет-канала.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37602994
JoFan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
RedCatXJoFanРазве от количества соединений будет расти скорость передачи ?
Или в задаче нужно передать один файл на несколько хостов-приемников?

Да, от количества соединений зависит скорость передачи. Попробуйте, например, скачать файл по HTTP сначала через одно соединение (встроенный в браузер менеджер загрузок), а потом скачайте его через несколько соединений (сторонний менеджер загрузок, например, ReGet). В первом случае скорость будет около 20% от пропускной способности вашего интернет-канала.

такое поведение reget актуально было во время медленной модемной связи (уже и не помню зачем так сделано было), сейчас же для закачки больших файлов используется торрент технология
но и в один поток я качаю равно со скоростью, указанной в тарифном плане (никакой уменьшении скорости не наблюдаю)
возможно такое может быть, если на самом сайте идет ограничение на отдачу на коннект
если же говорить о локальной сети, то тут качание в несколько соединений не оправдано

предлагаю взять уже готовые средства для обмена (например http://curl.haxx.se/libcurl/), и только если вдруг (в чем я лично сомневаюсь) покажут себя плохо - изобретать свой велосипед
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37603089
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
JoFanно и в один поток я качаю равно со скоростью, указанной в тарифном плане (никакой уменьшении скорости не наблюдаю)
Вам очень повезло с вашим интернет провайдером. У меня, например, ни разу не получалось достичь скорости указанной в тарифе на одном HTTP-соединении.
JoFanпредлагаю взять уже готовые средства для обмена (например http://curl.haxx.se/libcurl/), и только если вдруг (в чем я лично сомневаюсь) покажут себя плохо - изобретать свой велосипед
Я и так использую библиотеку libcurl. Но задача состоит не в этом.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37603298
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RedCatXПодскажите алгоритм, который можно использовать для распределения соединений между файлами согласно их приоритетам.
Должна хорошо подойти идея жадного (greedy) алгоритма. Во-первых, уточняете понятие приоритета. Кроме базового (который Вы назвали) вычисляемый приоритет файла может регулироваться его размером и долей уже прокачанного содержимого. Ну а потом - файлы выстраиваются в приоритетную очередь, на нескольких первых высыпается соединений по необходимости. При освобождении соединений они добрасываются файлам, испытывающим дефицит, если таких нет - берётся очередной файл из очереди. При добавлении файла приоритетом выше минимального скачивающегося - тот возвращается в очередь либо с него срезаются соединения. Правила расчёта вычисляемого приоритета регулируют ситуации типа "этот файл низкоприоритетный, но уже почти скачан, глупо его тормозить".
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37603483
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RedCatX, думаю здесь подойдёт система приоритетов которую использует eMule или torrent клиент. Процессы изначально обладают одинаковым приоритетом. В процессе закачки они захватывают слоты закачек (абстракция) настолько, насколько позволяет канал или политика сети. Пока есть активные процессы с высоким приоритетом, процессы с средним приоритетом слоты не берут и т.д. Между равными происходит захват слотов не знаю как но возможно по RoundRobin.
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37606459
RedCatX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Большое спасибо!
...
Рейтинг: 0 / 0
Посоветуйте алгоритм распределения ресурсов
    #37647013
White OwlНу а у тебя что?
Есть пропускная способность физического канала. = объем рюкзака
От нее зависит количество возможных соединений. = количество вещей
Соединения у тебя напрямую завязаны на файлы. Файлы имеют приоритет = вес вещей стоимость вещей
Объем файла = объем вещи
Тебе нужно передать как можно больше "важных" файлов и по возможности не забывать про "неважные". Так?

Чем выше удельный приоритет (средний приоритет файлов в рюкзаке/объем файлов в рюкзаке) в рюкзаке тем лучше.
...
Рейтинг: 0 / 0
18 сообщений из 18, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Посоветуйте алгоритм распределения ресурсов
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]