Python模拟作业调度

__author__ = 'SHUHUA'

#-*- coding: UTF-8 -*-

import random

titlebar='id'.ljust(5)+'优先数'.ljust(15)+'到达时间'.ljust(15)+'服务时间'.ljust(15)+'开始时间'.ljust(15)+'结束时间'.ljust(15)+'周转时间'.ljust(15)+'带权周转时间'.ljust(15)+'\n'

list=[]#作业队列

lastid = -1#上次调度之后的最后一个元素的id

ggstep = 1#高响应比优先调度步骤

now=0#高响应比优先调度专用当前时间记录

ID=0

SUPER=1   #优先数

ARRIVE=2  #到达时间

SERVER=3  #服务时间

START=4   #开始时间

End=5     #结束时间

ZZ=6      #周转时间

AVGZZ=7   #平均周转时间

def show_process():#打印

     global flist,titlebar

     strs=''

     if r.get()=='3':

        for i in range(len(list)):

            strs += str(list[i][ID]).ljust(5)+str(list[i][SUPER]).ljust(15)+str(list[i][ARRIVE]).ljust(15)+str(list[i][SERVER]).ljust(15)+ str(list[i][START]).ljust(15)+ str(list[i][End]).ljust(15)+str(list[i][ZZ]).ljust(15) +str(list[i][AVGZZ]).ljust(15)+'\n'

     else:

         for i in range(len(list)):

            strs += str(list[i][ID]).ljust(5)+''.ljust(15)+str(list[i][ARRIVE]).ljust(15)+str(list[i][SERVER]).ljust(15)+ str(list[i][START]).ljust(15)+ str(list[i][End]).ljust(15)+str(list[i][ZZ]).ljust(15) +str(list[i][AVGZZ]).ljust(15)+'\n'

     v1.set(titlebar + strs)

def random_process():#随机生成作业队列

    global list,lastid,ggstep

    ggstep=1#高响应比步骤置1

    lastid=-1#每次刷新都要使最后一个已调度的作业索引为-1

    del list[:] # 每次都清空列表

    for i in range(10):

        id=i

        #super=random.randint(0,15)#静态优先权才有

        super=0#动态优先权，开始都是0

        arrive=i#不要改为随机数

        server=random.randint(1,101)

        new=[id,super,arrive,server,'','','','']

        list.insert(i,new)

    show_process()

import tkMessageBox

def add_process():#添加作业

    global list,lastid

    k = True

    if eat.get()=='' or est.get()==''or eat.get().isdigit()==False or est.get().isdigit()==False:

        tkMessageBox.showerror( message="请正确输入内容")

        k=False

    if ok:

        if len(list)>0 and list[lastid][START] !='':#说明前面已经进行过调度

            if int(eat.get()) < list[lastid][ARRIVE]:

                k=False

                tkMessageBox.showerror(  message="当前已经过调度", detail=u"请输入不小于 "+str(list[lastid][ARRIVE])+u' 的到达时间' )

    if ok:

        id = len(list)

        arrive=int(eat.get())

        server=int(est.get())

        if r.get()=='3':#高响应比优先时

            if esuper.get()==''or (esuper.get().isdigit()==False):

                tkMessageBox.showerror(  message="请正确输入", detail=u"优先数大小(默认为1)" )

            else:

                super=int(esuper.get())

                new=[id,super,arrive,server,'','','','']

                list.insert(id,new)

                show_process()

        else:#先来先服务 or 短作业优先时

            new=[id,'',arrive,server,'','','','']

            list.insert(id,new)

            show_process()

def fcfs():#先来先服务调度所有作业

    global list,lastid

    list = sorted(list,cmp=lambda x,y:cmp(x[ARRIVE],y[ARRIVE]))#按到达时间对就绪队列进行排序

    for i in range(len(list)):

        if list[i][START] =='':#尚未调度

           if list[i][ID]==0:

                list[i][START]=list[i][ARRIVE]

           else:

               list[i][START] =list[i-1][End]

           assert isinstance(list, object)

           list[i][End] = list[i][START] + list[i][SERVER]

           list[i][ZZ] = list[i][End] - list[i][ARRIVE]

           avg = float(list[i][ZZ])/list[i][SERVER]

           list[i][AVGZZ] = ("%.2f" % avg)

    if len(list):

        lastid = len(list)-1

    show_process()

def spf():#短作业优先--所有作业

    global list,lastid#lastid在这里作为每次已调度的做而已中最后一个的id

    lastid =-1

    short_early_list=sorted(list,key=lambda x:(x[SERVER],x[ARRIVE]))

    early_short_list=sorted(list,key=lambda x:(x[ARRIVE],x[SERVER]))

    firstnot=[]#存放下一个要调度的作业

    if len(list)==0:

        tkMessageBox.showerror(  message="当前没有作业，不能调度"  )

    else:

        i=0

        times =len(list)

        del list[:]#list只存放已经调度的，要清空

        while(i<times):#一共有times个作业需要调度，要找times次

            for p in range(times):#找出下一个要调度的作业赋给firstnot

                if len(list)==0:#如果当前时间是0，取时间最早那个--并且在这个时间点上最短的

                    firstnot = early_short_list[0]#取早且短那个

                    #清除两个未调度队列中的firstnot：

                    utid = early_short_list[0][ID]

                    for j in range(len(short_early_list)):#从未调度队列short_early_list中删除

                        if short_early_list[j][ID]==outid:

                            del short_early_list[j]

                            break

                        if j == times-i-2:#防止index溢出

                            break

                    del early_short_list[0]#从未调度队列early_short_list中删除

                    break#一旦找到就跳出for循环

                elif short_early_list[p][ARRIVE]<=list[lastid][End]:#如果前已有调度，且未调度中最短的那个作业已经到达

                    firstnot =short_early_list[p]#就去当前 短且早的这个

                    #清除两个未调度队列中的firstnot：

                    id=short_early_list[p][ID]

                    lenss=len(short_early_list)

                    j=0

                    for k in range(lenss):

                        if short_early_list[k][ID]==id:

                            del short_early_list[k]

                            j +=1

                        if early_short_list[k][ID]==id:

                            del early_short_list[k]

                            j+=1

                        if j == 2 or k >= times-i-2:#防止index溢出

                            break

                    break#一旦找到就跳出for循环

            if firstnot==[]:#如果循环完了都没找到已经到达的作业，那就取接下来最早且短那个

                firstnot = early_short_list[0]#取早且短那个

                #清除两个未调度队列中的firstnot：

                utid = early_short_list[0][ID]

                for x in range(len(short_early_list)):#从未调度队列short_early_list中删除

                    if short_early_list[x][ID]==outid:

                        del short_early_list[x]

                del early_short_list[0]#从未调度队列early_short_list中删除

            #处理firstnot：

            id = len(list)

            arrive = firstnot[ARRIVE]

            server = firstnot[SERVER]

            if lastid ==-1:

                start=firstnot[ARRIVE]

                en= firstnot[ARRIVE] + firstnot[SERVER]

            else:

                start = list[lastid][End]

                en = start+server

            zz = en - arrive

            av = float(zz)/server

            avg = ("%.2f" % av)

            new=[id,'',arrive,server,start,en,zz,avg]

            list.append(new)#在已调度队列list中插入

            lastid = len(list)-1

            i +=1#回到while找下一调度作业

        #调度完成

        show_process()

def gg():#高响应比优先--对一个作业（并且是单道系统）

    global list,ggstep,now

    if ggstep==1: #第一次点击“开始调度”，因为所有作业优先数都是0，所以调度最早那个。

        list = sorted(list,cmp=lambda x,y:cmp(x[ARRIVE],y[ARRIVE]))#按到达时间对就绪队列进行排序

        now = list[0][ARRIVE]#最初当前时间为最早到达时间

    if list[0][SUPER]>=0 :#还有得调度

         list[0][SUPER]= -ggstep#优先数改为  -第几次调度

         list[0][START]= now

         list[0][End]= list[0][START] + list[0][SERVER]

         list[0][ZZ]= list[0][End] - list[0][ARRIVE]

         avg= float(list[0][ZZ])/list[0][SERVER]

         list[0][AVGZZ]= ("%.2f" % avg)

         now += list[0][SERVER]

         ggstep +=1

        #重计剩余已经到来的作业的优先数

         for k in range(len(list)):

             if list[k][SUPER] >= 0 and list[k][ARRIVE] <=now:#尚未调度

                 waittime= now - list[k][ARRIVE]

                 super = 1+float(waittime)/list[k][SERVER]

                 list[k][SUPER]=("%.2f" % super)

        #让优先权越高的、越早的在前面

         list = sorted(list,cmp=lambda x,y:cmp(x[ARRIVE],y[ARRIVE]))

         list.reverse()

         list=  sorted(list,cmp=lambda x,y:cmp(x[SUPER],y[SUPER]))

         list.reverse()

    show_process()

def algorithm():#采用何种算法

    global message_change,now,ggstep

    if r.get() == '1':

        fcfs()

    elif r.get() == '2':

        spf()

    else :

        gg()

from Tkinter import *

top = Tk() #根窗口

top.title=('作业调度')

top.resizable(False, False)

top.geometry('479x500')

c1=Label(top,text='操作')

b1=Button(top,text = "随机初始作业",bg = "SkyBlue",width=15,command = random_process)

c2=Label(top,text='添加作业')

c22=Label(top,text='优先数：')

c23=Label(top,text='到达时间：')

c24=Label(top,text='服务时间：')

c26=Label(top,text='*')

c27=Label(top,text='*')

esuper=Entry(width=5)

esuper.insert(1,'1')

eat=Entry(width=5)

est=Entry(width=5)

b2=Button(top,text = "确定添加",bg = "SkyBlue",width=15,command = add_process)

c1.place(x=5,y=5)

b1.place(x=5,y=30)

c2.place(x=5,y=60)

c22.place(x=10,y=80)

c23.place(x=10,y=100)

c24.place(x=10,y=120)

esuper.place(x=80,y=80)

eat.place(x=80,y=100)

est.place(x=80,y=120)

c26.place(x=120,y=100)

c27.place(x=120,y=120)

b2.place(x=5,y=145)

c3=Label(top,text='选择算法')

c3.place(x=200,y=5)

r = StringVar()                 #使用StringVar生成字符串变量用于单选框组件

r.set('1')                      #初始化变量值

radio = Radiobutton(top,       #生成单选框组件

                            variable = r, #设置单选框关联的变量

                            value = '1',   #设置选中单选框时其所关联的变量的值

                            indicatoron = 0,

                             bg = "SkyBlue",

                            text = '先来先服务'.center(25)) #设置单选框显示的文本

radio.place(x=200,y=30)

radio = Radiobutton(top,

                            variable = r,

                            value = '2',      #当选中单选框时，r的值为2

                            indicatoron = 0,

                            bg = "SkyBlue",

                            text = '短作业优先'.center(25))

radio.place(x=200,y=70)

radio = Radiobutton(top,

                            variable = r,

                            value = '3',

                            indicatoron = 0,

                             bg = "SkyBlue",

                            text = '高响应比优先'.center(25))

radio.place(x=200,y=110)

b3=Button(top,text = "开始调度",bg = "LightSalmon",width=15,command = algorithm)

b3.place(x=200,y=145)

v1 = StringVar()

v1.set(titlebar)

Message(top,width = 580,textvariable = v1,bg = "Tan" ).place(x=5,y=185)

auth=Label(top,text='作业调度实验\n 11级计科3班\n3211005813\n 青春痘\n  2013年12月30日',bg="LightGrey")

auth.place(x=368,y=0)

mainloop()