Python模拟进程调度

__author__ = 'SHUHUA'

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

import random

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

list=[]#进程PCB队列

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

timestep = 1#时间片大小，默认是1

ID=0

LE=1   #时间片轮转法中，剩余服务时间的记录

ARRIVE=2  #到达时间

SERVER=3  #服务时间

START=4   #开始时间

End=5     #结束时间

ZZ=6      #周转时间

AVGZZ=7   #平均周转时间

def show_process():#打印

     global flist,titlebar

     strs=''

     for i in range(len(list)):

        strs += str(list[i][ID]).ljust(5)+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

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

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

    for i in range(10):

        id=i

        arrive=i#不要改为随机数

        server=random.randint(1,101)

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

        list.insert(i,new)

    show_process()

import tkMessageBox

def add_process():#添加进程

    global list,lastid,timestep

    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 etime.get()==''or (etime.get().isdigit()==False):

                tkMessageBox.showerror(  message="请正确输入", detail=u"时间片大小(默认为1)" )

            else:

                timestep=int(etime.get())

                new=[id,'',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 rr():#时间片轮转法

    global list,lastid,timestep

    lt = sorted(list,cmp=lambda x,y:cmp(x[ARRIVE],y[ARRIVE]))#按到达时间对队列进行排序，lt指没调度过的进程队列--新来的队列

    del list[:]#完成后的进程才能放进list--完成队列

    worklist=[]#有序存放可调度进程的队列--工作队列

    now = lt[0][ARRIVE] #当前时刻

    alltime=0#要运行的总时

    for i in range(len(lt)):

        lt[i][LE]=lt[i][SERVER]#用LE索引处作为剩余服务时间的记录

        alltime += lt[i][SERVER]

    if now !=0:

        tkMessageBox.showerror(  message="手动输入请从让开始时间为0"  )

    #三步:

    lt[0][START]=lt[0][ARRIVE]

    worklist.append(lt[0])

    del lt[0]

    k=0#用来防止lt越界访问

    lk =len(lt)#用来防止lt越界访问

    while(now < alltime):#没运行完都要继续

        #1、调度worklist队首一个。

        if worklist[0][LE] >= timestep:#如果剩余时间 >= timestep

            worklist[0][LE] -= timestep

            now += timestep

        elif 0 < worklist[0][LE] < timestep:#如果剩余时间不足 timestep

            now += worklist[0][LE]

            worklist[0][LE] = 0

        #2、（如果lt！=[]）看lt里哪些进程准备好了，就从lt删除并插进 worklist 里。

        for j in range(len(lt)):

            if lt[j][ARRIVE] <= now:

                lt[j][START] = now

                worklist.append(lt[j])

                del lt[j]

                k += 1

            if j >= lk - k - 1:#防止越界访问

                break

        #3、 把当前调度的从worklist队首删除，如果还没完成就插到 worklist 队尾，如果完成了就插到list队列队尾。

        if worklist[0][LE]==0:

            #先结算

            worklist[0][End] = now

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

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

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

            #再删插

            list.append(worklist[0])

            del worklist[0]

        elif worklist[0][LE]>0:

            worklist.append(worklist[0])

            del worklist[0]

    list = sorted(list,cmp=lambda x,y:cmp(x[ARRIVE],y[ARRIVE]))#按到达时间对队列进行排序，lt指没调度过的进程队列--新来的队列

    show_process()

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

    global message_change

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

        fcfs()

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

        spf()

    else :

        rr()

from Tkinter import *

top = Tk() #根窗口

top.title=('进程调度')

top.resizable(False, False)

top.geometry('450x500')

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='*')

etime=Entry(width=5)

etime.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)

etime.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月28日',bg="LightGrey")

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

mainloop()