javascript - 在javascript中做最短工作优先算法

Question

我正在尝试使用 javascript 模拟操作系统的最短作业优先技术，给定作业/进程、到达时间和突发时间:

检查此链接:Shortest Job First - Concept .现在我有一个数组:

var arr = [
    {
        "job": "j4",
        "at": 0,
        "bt": 8
    },
    {
        "job": "j2",
        "at": 2,
        "bt": 4
    },
    {
        "job": "j3",
        "at": 2,
        "bt": 5
    },
    {
        "job": "j5",
        "at": 6,
        "bt": 4
    },
    {
        "job": "j1",
        "at": 8,
        "bt": 3
    }
];

我想创建一个包含进程对象的新数组。 .

例如

[
   {"job": "j4", "range" : "0-2"},
   {"job": "j2", "range" : "2-6"},
   {"job": "j5", "range" : "6-10"},
   {"job": "j1", "range" : "10-13"},
   {"job": "j3", "range" : "13-18"},
   {"job": "j4", "range" : "18-24"}
]

所以我尝试这样做，但我 super 卡住了，离我想要实现的目标还差得很远。

for(i = 0; i < arr.length; i++) {
   var temp = [];
    for(j = arr[i].at; j < arr[i].bt; j++) {
        var clone = arr.slice(0);
        var arrived = clone.splice(0, i).filter(function( obj ) {
            return obj.at == j;
        });
        var shorter = arr[i];
        for(k = 0; k < arrived.length; k++) {
            if(arrived[k].bt < arr[i].bt) {
                shorter = arrived[k];
                arr[i].bt - (j - arr[i].at);
            }
        }
        if(shorter != arr[i]) {
            j = arr[i].bt;
        }
    }
}

编辑 如果解决了，用实际值替换新的数组值

Time Process
 0     j4(8)
 1 
 2     j4(6), j2`(4), j3(5)
 ...
 6     j4(6), j3(5), j5(4)         ::: j2 done
 7
 8     j5`(2), j4(6), j3(5), j1(3)
 9
 10                                ::: j5 done
 ...
 13                                ::: j1 done
 ...
 18                                ::: j3 done
 ...
 24                                ::: j4 done


so the new array will be

[
   {"job": "j4", "range" : "0-2"},
   {"job": "j2", "range" : "2-6"},
   {"job": "j5", "range" : "6-10"},
   {"job": "j1", "range" : "10-13"},
   {"job": "j3", "range" : "13-18"},
   {"job": "j4", "range" : "18-24"}
]

Answer 1

这是我用 JS 编写的一个有效的 SJF 示例。正如标签中提到的那样，我使用 jQuery 从主数组获取数据。将事件对象与队列进行比较，根据需要将元素移入和移出队列，并将运行时间添加到最终数组。希望这个示例可以帮助您使代码正常工作。

JSFiddle Example

var active = undefined,
    queue = [],
    final = [],
    totalBurst = 0;

// Get the total burst time
$.map(arr, function(job, index) {
    // Add a run time variable to 
    job.runTime = job.bt;
    totalBurst += job.bt + job.at;
});

// This loop simulates time
for (var i = 0; i < totalBurst; i+=1) {
    if (typeof active === 'object') {
        active.runTime -= 1;

        if (active.runTime < 1) {
            final.push({ job : active.job, start : active.start, end : i});
            active = undefined;
        }
    }

    // Get array of jobs recieved at this time signature
    var toProcess,
        jobs = $.grep(arr, function(job, index) {
            return job.at === i;
        });

    // Merge new jobs into queue
    queue = queue.concat(jobs);    
    // Sort the queue
    queue.sort(function(a,b) {
        return a.bt < b.bt ? -1 : 1;
    });

    // Get the job to process next
    toProcess = queue.splice(0,1)[0];

    if (typeof toProcess !== 'undefined') {
        // Process active job
        if (typeof active === 'undefined' && typeof toProcess !== 'undefined') {
            // Automatically start the first job in the queue
            toProcess.start = i;
            active = toProcess;
        } else if( typeof toProcess !== 'undefined' && active.bt > toProcess.bt ) {
            // Push active time to final array
            final.push({ job : active.job, start : active.start, end : i});
            // If active still has time to run add it to queue
            if (active.runTime > 0) {
                queue.push(active);
            }

            // Create new active process
            toProcess.start = i;
            active = toProcess;
        } else if( typeof toProcess !== 'undefined') {
            // Otherwise we still have an active process
            // Push the toProcess back on the queue
            queue.push(toProcess);
        }
    }    
}