硬算法实现

Question

我无法实现SJF(最短作业优先)算法。

SJF是这样工作的

如果进程到达0，它将工作到下一个进程到达，该算法必须检查到达1的到达(进程/进程)是否比当前剩余时间短。

例如: P0执行1，仍然2完成，现在我们有P0，P1，P2，P3，P4在1算法将执行最短的一个P3，然后P0然后P4然后P1等等。问题是，我必须保存到所有进程的开始和结束时间执行，以及等待时间。

这是我最新的算法。(发生了一些错误的情况)

输入数据：

Process Arrival Burest 
P0      0       3
P1      0       4
P2      0       5
P3      1       1
p4      1       3

for (i = 0; i < proc.Count; i++)
{
    minProcIndex = i;
    for (x = i; x < proc.Count; x++)
    {
        for (int y = 0 ; y < proc.Count; y++)
        {
            if (y == minProcIndex)
                continue;

            if (tempBrust[minProcIndex] - tempArrival[y] > tempBrust[y] 
                && tempBrust[y] != 0)
            {
                tempBrust[minProcIndex] -= tempArrival[y];
               // tempArrival[minProcIndex] += tempArrival[y];
                clock += tempArrival[y];
                //proc[y].start = clock;
                minProcIndex = y;
            }
            else if (y != proc.Count -1)
                continue;
            else
            {
                if (y == 0)
                {
                    proc[minProcIndex].start = 0;
                }
                else if (proc[y].start > 0)
                {
                    proc[y].start = clock;
                }
                else
                proc[minProcIndex].start = clock;

                proc[minProcIndex].end = proc[minProcIndex].brust + clock;
                tempBrust[minProcIndex] = 0;
                clock += proc[minProcIndex].brust;
                if (minProcIndex == proc.Count - 1)
                    minProcIndex = 0;
                else
                minProcIndex++;
                for (int c = 0; c < proc.Count; c++)
                {
                    if (tempArrival[c] < clock)
                        tempArrival[c] = clock - 1;
                }
            }
        }
    }
}

Answer 1

我认为如果您创建一个类来保存流程信息，这会更容易一些。

public class ProcessInformation
{
    public string Name { get; private set; }
    public int Duration { get; private set; }
    public int ArrivalTime { get; private set; }

    public int TimeLeft { get; set; }
    public int? StartTime { get; set; }
    public int? EndTime { get; set; }
    public List<int> InterruptTimes { get; private set; }

    public ProcessInformation(string name, int arrivalTime, int duration)
    {
        Name = name;
        ArrivalTime = arrivalTime;
        Duration = duration;
        TimeLeft = duration;
        InterruptTimes = new List<int>();
    }
}

然后只需运行以下代码

var processes = new List<ProcessInformation>
                {
                    new ProcessInformation("P0", 0, 3),
                    new ProcessInformation("P1", 0, 4),
                    new ProcessInformation("P2", 0, 5),
                    new ProcessInformation("P3", 1, 1),
                    new ProcessInformation("P4", 1, 3)
                };

int currentTime = 0;
ProcessInformation currentProcess = null;
while (processes.Any(p => p.TimeLeft > 0))
{
    var shortest =
        processes.Where(p => p.ArrivalTime <= currentTime && p.TimeLeft > 0)
            .OrderBy(p => p.TimeLeft)
            .FirstOrDefault();

    if (currentProcess != null && currentProcess.TimeLeft > 0 && shortest != currentProcess)
    {
        currentProcess.InterruptTimes.Add(currentTime);
    }

    if (shortest != null)
    {
        if (shortest.StartTime == null) shortest.StartTime = currentTime;
        shortest.TimeLeft--;
        if (shortest.TimeLeft == 0) shortest.EndTime = currentTime + 1;
    }

    currentProcess = shortest;
    currentTime++;
}

foreach (var p in processes)
{
    Console.WriteLine(
        "Process {0} arrived {1} started {2} ended {3} duration {4} wait {5} interrupt times {6}", 
        p.Name, 
        p.ArrivalTime, 
        p.StartTime, 
        p.EndTime, 
        p.Duration, 
        p.EndTime - p.ArrivalTime - p.Duration,
        p.InteruptTimes.Any() ? string.Join(", ", p.InteruptTimes) : "None");
}

，它输出以下内容

进程P0到达0开始0结束4持续时间3等待1中断次数1 进程P1到达0开始7结束11持续时间4等待7次中断次数无 进程P2到达0启动11结束16持续时间5等待11中断次数无 进程P3到达1开始1结束2持续时间1等待0中断次数无 进程P4到达1开始4结束7持续时间3等待3中断次数无