Мне интересно, какие структуры данных/алгоритмы могут помочь облегчить обработку следующей ситуации; Я не уверен, нужен ли мне один FIFO, приоритетная очередь или несколько FIFO.
У меня есть N объектов, которые должны пройти через предопределенный рабочий процесс. Каждый объект должен выполнить шаг 1, затем шаг 2, затем шаг 3, затем шаг 4 и т. д. Каждый шаг либо выполняется быстро, либо включает «ожидание», которое зависит от чего-то внешнего для завершения (например, завершения операции с файлом или чего-то еще). ). Каждый объект поддерживает свое собственное состояние. Если бы мне пришлось определить интерфейс для этих объектов, это было бы примерно так (написано ниже на псевдо-Java, но этот вопрос не зависит от языка):
public interface TaskObject
{
public enum State { READY, WAITING, DONE };
// READY = ready to execute next step
// WAITING = awaiting some external condition
// DONE = finished all steps
public int getCurrentStep();
// returns # of current step
public int getEndStep();
// returns # of step which is the DONE case.
public State getState();
// checks state and returns it.
// multiple calls will always be identical,
// except WAITING which can transition to READY or DONE.
public State executeStep();
// if READY, executes next step and returns getState().
// otherwise, returns getState().
}
Мне нужно написать однопоточный планировщик, который вызывает executeStep() для «следующего» объекта. Моя проблема в том, что я точно не знаю, какую технику мне следует использовать, чтобы определить, что такое «следующий» объект. Я хочу, чтобы это было справедливо (первым пришел, первым обслужен для объектов, не находящихся в состоянии ОЖИДАНИЕ).
Моя интуиция состоит в том, чтобы иметь 3 FIFO: ГОТОВО, ЖДЕТ и ГОТОВО. Вначале все объекты помещаются в очередь READY, и планировщик повторяет цикл, в котором он берет первый объект из очереди READY, вызывает executeStep() и помещает его в очередь, соответствующую результату executeStep(). За исключением того, что элементы в очереди ОЖИДАНИЯ должны быть помещены в очередь ГОТОВО или ГОТОВО при изменении их состояния.... ааа!
Любой совет?