Optimal process planning
An algorithm aimed at optimal processes planning is presented to your attention. Formally, we describe the problem.
Let there be files that need to be processed by preloading into
memory. For memory, the limit is put forward in the form of a total, simultaneously used memory equal to
. Then, at a time, there may be files in memory, the total volume
which does not exceed
. I.e.
where is the maximum amount of memory that will be used for processing
-th file.
In addition, at the same time there can be no more memory in files, i.e.
.
Our task is to minimize the total execution time, given that the set of files is updated after complete the processing of one of the previous files. The algorithm for selecting the following file is as follows:
- Select all possible files in decreasing order of processing time
- If the next file does not fit into memory, then the file of the maximum size from the possible
- If no files can be added, it is proposed to process the files
Оптимальное планирование процессов
Вашему вниманию представляется алгоритм, нацелнный на оптимальное планирование процессов. Формально опишем задачу.
Пусть есть файлов, которые требуется обработать, предварительно загрузив в
память. Для памяти выдвигается ограничение в виде суммарно, одновременно используемой памяти, равной
. Тогда, единовременно, в памяти могут находиться файлы, суммарный объём
которых не превышает
. Т.е.
где - максимальный объём памяти, который будет использоваться для обработки
-го файла.
Кроме того, одновременно в памяти не может находиться более файлов, т.е.
.
В нашей задаче требуется минимизировать суммарное время выполнения, учитывая, что набор файлов обновляется после завершения обработки одного из предыдущих файлов. Алгоритм выбора следующего файла состоит в следующем:
- Выбрать все возможные файлы в порядке убывания времени их обработки
- Если следующий файл не умещается в память, то выбирается файл максимального объёма из возможных
- Если ни одни файл добавить не удаётся, то предлагается обработать файлы
Examples
Let's show example of usage:
type Processor struct {
}
func (p *Processor) AppendFiles(filesForProcess scheduler_pkg.FileSlice) {
}
func (p *Processor) Process() int {
// Processing filesForProcess ...
return 0
}
func main() {
files := scheduler_pkg.FileSlice{
scheduler_pkg.File{0, 1, 2},
scheduler_pkg.File{1, 1, 2},
scheduler_pkg.File{2, 1, 2},
scheduler_pkg.File{2, 18, 5},
}
scheduler, err := scheduler_pkg.NewScheduler(files, 5, 3)
if err != nil {
panic(err)
}
processor := Processor{}
filesForProcess := scheduler.GetCurrentFiles()
// New files will appended for processing
processor.AppendFiles(filesForProcess)
for {
// Processing filesForProcess ...
finishedFileId := processor.Process()
// Processing one file was finished
scheduler.Finished(finishedFileId)
newFiles, err := scheduler.Next()
if err != nil {
panic(err)
}
if err == io.EOF {
break
}
// New files will appended for processing
processor.AppendFiles(newFiles)
}
}