Python實戰——實作程序排程算法：先來先服務（FCFS）、短作業優先（SJF）和動态最高優先數優先（HRRN）

Python實戰——實作程序排程算法：FCFS、SJF和HRRN

實驗要求

程序排程算法：采用先來先服務、短作業、動态最高優先數優先的排程算法（即把處理機配置設定給優先數最高的程序）。

每個程序有一個程序控制塊（ PCB）表示。程序控制塊可以包含如下資訊：

程序名—程序标示數 ID

優先數 PRIORITY 優先數越大優先權越高（僅HRRN）

到達時間—程序的到達時間為程序輸入的時間。、

程序還需要運作時間ALLTIME，程序運作完畢ALLTIME=0，

已用CPU時間----CPUTIME、

程序開始阻塞時間STARTBLOCK-表示當程序在運作STARTBLOCK個時間片後，程序将進入阻塞狀态

程序的阻塞時間BLOCKTIME–表示當程序阻塞BLOCKTIME個時間片後，程序将進入就緒狀态

程序狀态—STATE

因為FCFS和SJF比較簡單，是以寫這兩個算法時比較粗糙，沒有設定阻塞時間，執行時也隻是列印執行程序的資訊（這倆是白給的）~~

HRRN算法每次都計算作業的優先級，随着作業等待時間的變長，優先級不斷的提高，是以能夠得到更快的執行。一般優先級的計算方法是：優先級 = (作業已等待時間 + 作業的服務時間) / 作業的服務時間，而這裡我隻是簡單地令程序在等待或阻塞時優先數+1，效果都差不多~~

代碼如下

運作環境為python 3.7

import random
class PCB:
    def __init__(self,pid,priority,arr_time,all_time,cpu_time,start_block,block_time,state): ##初始化程序
        self.pid=pid
        self.priority=priority
        self.arr_time=arr_time
        self.all_time=all_time
        self.cpu_time=cpu_time
        self.start_block=start_block
        self.block_time=block_time
        self.state=state

    def output(self):   ##hrrn輸出
        print("程序"+str(self.pid),"優先級："+str(self.priority),"到達時間:"+str(self.arr_time),
              "還需運作時間:"+str(self.all_time),"已運作時間:"+str(self.cpu_time),
              "開始阻塞時間："+str(self.start_block),"阻塞時間："+str(self.block_time),"狀态："+self.state)
    def Output(self):   ##sjf fcfs輸出
        print("程序"+str(self.pid),"正在執行，到達時間:"+str(self.arr_time),
              "還需運作時間:"+str(self.all_time),"已運作時間:"+str(self.cpu_time))
    def toBlock(self):  ##将狀态置為Block
        self.state="Block"
    def toRun(self):    ##将狀态置為Run
        self.state="Run"
    def toFinish(self):     ##将狀态置為Finish
        self.state="Finish"
    def toReady(self):      ##将狀态置為Ready
        self.state="Ready"
    def running(self):      ##程序運作時狀态變化
        self.all_time-=1
        self.cpu_time+=1
    def toBlocking(self):   ##程序将要開始阻塞的狀态變化
        if self.start_block>0:
            self.start_block-=1
    def blocking(self):     ##程序阻塞時的狀态變化
        if self.block_time>0:
            self.block_time-=1
        self.priority+=1

def init(num):##初始化程序，生成四個程序并按到達時間将它們放入清單list1
    list1=[]
    for i in range(num):
        list1.append(PCB(str(i),random.randint(1,10),random.randint(10,15),
                         random.randint(1,10),0,random.randint(5,10),random.randint(1,10),"Ready"))
    for i in range(len(list1)-1):
        for j in range(i+1,len(list1)):
            if list1[i].arr_time>list1[j].arr_time:
                list1[i],list1[j]=list1[j],list1[i]
    return list1
        
def fcfs(list1):##先來先服務
    time=0
    while 1:
        print("time:",time)
        if time>=list1[0].arr_time:
            list1[0].running()
            list1[0].Output()
            if list1[0].all_time==0:
                print("程序"+list1[0].pid+"執行完畢,周轉時間："+str(time-list1[0].arr_time+1)+"\n")
                list1.remove(list1[0])
        time+=1
        if not list1:
            break

def sjf(list1):##搶占式短作業優先
    list2=[]   ##就緒隊列
    time=0
    while 1:
        len_list2=len(list2)
        print("time:",time)
        if list1:
            i=0
            while 1:   ##将程序放入就緒隊列，就緒隊列的第一個是正在執行的程序
                if time==list1[i].arr_time:
                    list2.append(list1[i])
                    list1.remove(list1[i])
                    pid=list2[0].pid  ##擷取就緒隊列第一個程序的程序ID
                    i-=1
                i+=1
                if i>=len(list1):
                    break                 
        if len(list2)>=2 and len(list2)!=len_list2: ##判斷就緒隊列中最短的作業
            len_list2=len(list2)
            for i in range(len(list2)-1):
                for j in range(i+1,len(list2)):
                    if list2[i].all_time>list2[j].all_time:
                        list2[i],list2[j]=list2[j],list2[i]
        if list2: ##執行過程
            if pid!=list2[0].pid: ##如果正在執行的程序改變，則發生搶占
                print("發生搶占，程序"+list2[0].pid+"開始執行")
                pid=list2[0].pid
            list2[0].running()
            list2[0].Output()
            if list2[0].all_time==0:
                print("程序"+list2[0].pid+"執行完畢,周轉時間："+str(time-list2[0].arr_time+1)+"\n")
                list2.remove(list2[0])
                if list2:
                    pid=list2[0].pid
        time+=1
        if not list2 and not list1:
            break
def hrrn(list1): ##動态最高優先數優先
    list2=[]  ##就緒隊列
    list3=[]  ##阻塞隊列
    time=0
    while 1:
        print("time:",time)
        if list1:
            i=0
            while 1: ##将程序放入就緒隊列
                if time==list1[i].arr_time:
                    list2.append(list1[i])
                    list1.remove(list1[i])
                    pid=list2[0].pid
                    i-=1
                i+=1
                if i>=len(list1):
                    break
        for i in range(len(list2)-1): ##将就緒隊列的程序按優先級大小排列
            for j in range(i+1,len(list2)):
                if list2[i].priority<list2[j].priority:
                    list2[i].toReady()
                    list2[i],list2[j]=list2[j],list2[i]
        if list2: ##執行過程
            if pid!=list2[0].pid:
                print("發生搶占，程序"+list2[0].pid+"開始執行")
                pid=list2[0].pid
            if list2[0].start_block>0 or list2[0].block_time<=0:
                list2[0].toRun()
                list2[0].running()
                list2[0].toBlocking() 
            for i in range(1,len(list2)):
                list2[i].priority+=1
                list2[i].toBlocking()
        if list3: ##阻塞隊列
            for i in list3:
                i.blocking()
                
        for i in list2:
            i.output()
        for i in list3:
            i.output()
            
        if list2:  ##當程序開始阻塞時間為0，将程序放入阻塞隊列
            i=0
            while 1:
                if list2:
                    if list2[i].start_block==0 and list2[i].block_time!=0:
                        print("程序"+list2[i].pid+"開始阻塞，進入阻塞隊列")
                        list2[i].toBlock()
                        list3.append(list2[i])
                        list2.remove(list2[i])
                        i-=1
                i+=1
                if i>=len(list2):
                    break
            
        if list3:  ##當程序阻塞時間為0，将程序放入就緒隊列
            i=0
            while 1:
                if list3[i].block_time==0:
                    print("程序"+list3[i].pid+"阻塞結束，進入就緒隊列")
                    list3[i].toReady()
                    list2.append(list3[i])
                    list3.remove(list3[i])
                    pid=list2[0].pid
                    i-=1
                i+=1
                if i>=len(list3):
                    break
                
        if list2: ##程序執行完畢則移出就緒隊列
            if list2[0].all_time<=0:
                list2[0].toFinish()
                print("程序"+list2[0].pid+"執行完畢，周轉時間："+str(time-list2[0].arr_time+1),"狀态："+list2[0].state+"\n")
                list2.remove(list2[0])
                if list2:
                    pid=list2[0].pid
        
        time+=1
        if not (list1 or list2 or list3):
            break
if __name__=="__main__":
    while 1:
        n=input("請選擇算法(1、先來先服務  2、搶占式短作業優先  3、動态最高優先數優先):")
        if n=="1":
            list1=init(4)
            for i in list1:
                i.Output()
            fcfs(list1)
        elif n=="2":
            list1=init(4)
            for i in list1:
                i.Output()
            sjf(list1)
        elif n=="3":
            list1=init(4)
            for i in list1:
                i.output()
            hrrn(list1)
        else:
            print("輸入錯誤，請重新輸入！")
           

運作結果如下

FCFS（僅截取部分）

SJF（僅截取部分）

HRRN（僅截取部分）

程序的所有資訊都是用Random庫随機生成，因為一個個輸入太麻煩~~

程式執行時隻需選擇排程算法，執行過程不需要任何操作

特别需要注意的是：在循環的每一秒中，輸出資訊和具體的操作一定要分開！一定要分開！一定要分開！ 要麼先列印後操作，要麼先操作後列印，不要邊操作邊列印，會混亂的~

親身經曆總結出的教訓~