Matlab【多台多处理器机器上等长作业繁忙时间调度】

多台多处理器上的等长作业调度类似于多台机器上的等长作业调度，可以将m台机器上的m*g个处理器独立看做是m*g台机器，生成一个可行的调度。

注意到，两者之间的不同之处在于同一台机器上的g个处理器共享该机器的繁忙时间，即只要有一个处理器上运行作业，其他的处理器不管是否有作业运行，该处理器都必须开机。大部分情况下，为了节约能耗，需要充分利用每台机器上的各个处理器，这样可以保证节省服务器的开机时间，即繁忙时间，达到节省能耗的目的。

该问题的大概处理思路如下：

%% 多台多处理器上的作业繁忙时间调度问题
%每台机器上的处理器个数
g = 2;
%作业处理时间
p = 3;
%作业的释放时间
r = [1 2 2 3 4 5 3 4 6 7 4 5 9 7 3 4];
%作业的最迟开始时间
u = [9 4 7 5 6 8 10 15 12 10 9 7 10 9 5 6];
%二分查找确定使用最少的机器个数
m=getm(g,r,u,p);
%生成一个可行调度
[~,starttimes] = shedule(m * g,r,u,p)
%优化调度
newstarttimes = optimalshedule(starttimes,m,g,r,u,p)

shedule方法即之前多台机器上的等长作业调度问题求解思路，详情参见

function [ starttimes ] = shedule( m,r,u,p )
%% 多台处理器作业调度优化
% starttimes：可行的调度
% r：作业的释放时间
% u：作业的最迟开始时间
% m：机器的台数
% p：作业的处理时间，所有的作业处理时间相同

    %bellman算法对最晚开始时间的理解不同
    %例如算法理解的r=[1 4 4 4];u=[4 4 10 4];m=4;p=3;
    %我们理解的r=[1 4 4 4];u=[5 5 11 5];m=4;p=3;
    %因此，为了便于理解，这里对u统一做了加1处理。
    u=u+1;
    %作业总时间
    B=sort([r u]);
    rmin = min(B);
    umax = max(B);
    %以时间为顶点
    T = rmin:umax;
    %图G中边的权重
    G=ones(length(T))*inf;
    %标识图G中的边
    M=zeros(length(T));
    M = existsedge( M,rmin,umax,r,u,p)';
    for i=1:length(T)
        for j=1:length(T)
            %判断是否存在边，若存在，则计算边的权重
            if M(i,j) == 1
                if i < j
                    G(i,j)=m;
                else
                    count = 0;
                    for k = 1:length(r)
                        if r(k) >= j && u(k) <= i
                            count = count + 1;
                        end
                    end
                    G(i,j)=-count;
                end
            end
        end
    end

    %绘出调度图
    graph(G);
    %求解问题
    [~,dis] = bellmanford(G,umax);
    %确定各个作业的开始时间
    [~,ind]=sort(u);
    starttimes = zeros(1,length(u));
    k=1;
    for i=1:length(T)-1
        if dis(i) ~= dis(i+1)
            %当前时刻i开始的作业个数
            tmp = dis(i+1) - dis(i);
            while(tmp > 0)
                starttimes(ind(k)) = i;
                k = k+1;
                tmp = tmp - 1;
            end
        end
    end
end

function [ m ] = getm( g,r,u,p )
%% 二分查找确定使用最少的机器个数
    m1=1;
    m2=length(r);
    flag=1;
    while flag
        n=fix((m1+m2)/2);
        [flag,~]=shedule(n * g,r,u,p);
        if flag
            m=n;
        end
        m2=n;
    end
end

optimalshedule方法：

function [ newstarttimes ] = optimalshedule( starttimes,m,g,r,u,p )
%% 多台多处理器作业调度优化
% starttimes：可行的调度
% r：作业的释放时间
% u：作业的最迟开始时间
% m：机器的台数
% g：每台机器上处理器的个数
% p：作业的处理时间，所有的作业处理时间相同
    
    rmin = min(r);
    umax = max(u);
    %未调度的作业
    U=1:length(r);
    %优化后的调度时间
    newstarttimes = zeros(1,length(r));
    K=[];
    P=[];
    t=rmin;
    while t <= umax && ~isempty(U)
        %待调度的作业，记录其下标
        Stmp = [];
        s = max(t,starttimes);
        %遍历未调度作业的集合，统计在t和t+p之间开始的作业的个数
        count = 0;
        for i=1:length(U)
            %注意到，时间线推进过程中，可能开始时间位于t和t+2p之间的作业个数不大于2mg
            if s(U(i)) >= t && s(U(i)) < t + 2*p
                count = count + 1;
                Stmp = [Stmp i];
                newstarttimes(U(i)) = s(U(i));
            end
        end
        %批调度
        if count >= m*g
            %删除已经调度的作业
            U(Stmp) = [];
            %更新时间
            for i=t:t+3*p
                if ~ismember(i,K)
                    K=[K i];
                end
            end
            t = t + 2*p;
        else
            %检查是否有急需要运行的作业
            flag = 0;
            for i=1:length(U)
                if u(U(i)) == t
                    flag = 1;
                    break;
                end
            end
            %若存在急需要运行的作业
            if flag
                worktodo = [];
                %检查所有未调度作业的开始时间是否在t和t+p之间，若是，则运行
                for i=1:length(U)
                    if s(U(i)) >= t && s(U(i)) < t + p
                        worktodo = [worktodo i];
                        newstarttimes(U(i)) = s(U(i));
                        P = [P U(i)];
                    end
                end
                %删除已经调度的作业
                U(worktodo) = [];
                %更新时间
                 t = t + p;
            else
                %不存在急需运行的作业时，需要将时间轴向前推进
                t = t + 1;
            end
        end
    end
end

function graph(cm)
%% 绘图

    %% 去除图中的权重为inf的边
    for i=1:size(cm,1)
        for j=1:size(cm,2)
            if cm(i,j) == inf
                cm(i,j) = 0;
            end
        end
    end
    
    %% 设置图显示权重并可视化
     bg=biograph(cm);
     bg.showWeights='on';
     view(bg);
end

生成的结果对比：

starttimes =

     4     1     3     2     3     4     6     9     7     6     5     4     7     5     2     3


newstarttimes =

     4     1     3     2     3     4     6    10    10     6     5     4    10     5     2     3

由结果可知，优化后的算法可以推迟部分作业的开始时间，使得机器尽可能减少开机时间。

代码和参考资料：github地址    csdn地址

最后

以上就是忧伤星星为你收集整理的Matlab【多台多处理器机器上等长作业繁忙时间调度】的全部内容，希望文章能够帮你解决Matlab【多台多处理器机器上等长作业繁忙时间调度】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。