Как многопоточность этого сценария проблемы?

Question

Я хотел бы провести симуляцию распределенной системы, в которой я должен провести исследование для информации (поставок) распределенным (параллельным, если мог бы !!) способом, например, у меня есть следующий класс:

public class Group{
public int identifier;
public int[] members;
public String name; 
public String[] supplies;
public int[] neighbors;}

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

1- Я хочу провести исследование расходных материалов, во-первых: внутри одной группы, если я не нахожу требуемый запас, я должен выполнить поиск во всех группах, которые являются соседями этой группы,Я думаю, чтобы сделать это с помощью многопоточности, я имею в виду, если поиск не удался, я должен сделать поиск во всех других соседях одновременно, используя несколько потоков, каждый из которых учитывает одного соседа, если у меня есть 10 соседей, тоДолжно быть создано 10 потоков ....

2 - Теперь, если я хочу начать повторный поиск с первого разаe с несколькими группами, я имею в виду начать с 3 или 4 или более групп, каждая из которых ищет разную поставку, или одну и ту же .... + одна группа, которая вызывает поиск, может быть соседом для другой группы ...

Итак, мой вопрос: как добиться этого сценария с помощью потоков?

PS. У меня есть машина с одним процессором с одним ядром, и мне нет дела до времени выполнения (все, что я хочу - это смоделировать эту проблему ...

Спасибо за каждый ответ и наилучшие пожелания.

Answer 1

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

Вернемся к предложению.Я хотел бы создать класс GroupPool, который имеет пул потоков, которые могут найти информацию.Количество потоков будет настраиваться через параметр конфигурации времени выполнения.Вы можете создать фабричный класс, который читает этот параметр из файла конфигурации и создает пул запускаемых объектов.

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

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

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

Надеюсь, это поможет вам попытаться спроектировать структуру для вашей проблемы.

Answer 2

Я не вижу никакого преимущества в производительности для многопоточности на одном процессоре.Это связано с тем, что одновременно может работать только 1 поток, и между потоками будет время переключения, поэтому, возможно, на самом деле потребуется больше времени для поиска группы с нужным ресурсом.

Лично япросто перебираем соседей первой группы и проверяем их на наличие ресурсов.Затем, если ресурсы не были найдены, я бы вызвал поиск по каждой из подгрупп, передав список уже проверенных групп, чтобы он мог пропустить уже проверенные группы.Что-то вроде:

public Group searchForGroupWithResource(Resource resource){
    List<Group> groupsToCheck = new ArrayList<Group>();
    groupsToCheck.add(this);
    int currentIndex = 0;
    while(currentIndex < groupsToCheck.size()){
        Group currentGroup = groupsToCheck.get(currentIndex);
        if(currentGroup.hasResource(resource)){
            return currentGroup;
        }
        groupsToCheck.addAll(currentGroup.getNeighbors(groupsToCheck));
        currentIndex++;
    }
    return null;
}

public List<Group> getNeighbors(List<Group> excludeGroups){
    //Get non-excluded neighbors
    List<Group> returnNeighbors = new ArrayList<Group>();
    for(Group neighbor : neighbors){
        boolean includeGroup = true;
        for(Group excludeGroup : excludeGroups){
            if(excludeGroup.equals(neighbor)){
                includeGroup = false;
                break;
            }
        }
        if(includeGroup){
            returnNeighbors.add(neighbor);
        }
    }
    return returnNeighbors;
}

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

Answer 3

Так как у вас есть проблема с привязкой к процессору, оптимальным количеством потоков, вероятно, будет количество ядер, которое у вас есть.Я бы позаботился о том, чтобы у каждого потока было около 100 микросекунд работы, иначе вы могли бы обнаружить, что у вас больше работы, чем полезной работы.Например, вы можете обнаружить, что поиск 10 тыс. узлов - это работа около 100 человек.Если вы не будете осторожны, многопоточное приложение может быть во много раз медленнее однопоточного.

Так что я бы нашел способ разделить работу, чтобы у вас было от 1 до 100 КБ узлов для каждого потока.и ограничьте ваш параллелизм количеством имеющихся у вас ядер.