在javascript中执行最短作业优先算法

Question

我试图使用javascript模拟os的最短作业优先技术，给定作业/流程、到达时间和突发时间：

签出以下链接：最短工作优先-概念。现在我有了一个数组：

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
    }
];

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

e.g

[
   {"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"}
]

所以我试着去做，但是我被困住了，而且离我想要达到的目标还很远。

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实例

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);
        }
    }    
}

Answer 2

如果你只想按bt排序，最短到最长，那么这个就行了.

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": 3,
        "bt": 3
    }
];

arr.sort(function(a, b) {
    return a.bt > b.bt;
});