オペレーティング・システム

マルチレベルフィードバックキュースケジューリングアルゴリズム（Python3実装コードを使用）



Multi Level Feedback Queue Scheduling Algorithm



まず、プログラムで使用される構造を紹介します

1.「プロセス/タスク」構造



class Process: def __init__(self,name,arrive_time,serve_time): self.name=name #Process name self.arrive_time=arrive_time #Time of arrival self.serve_time=serve_time #Require service time self.left_serve_time=serve_time #Remaining time for service self.finish_time=0 #Complete time self.cycling_time=0 #Turnaround time self.w_cycling_time=0 #With right turnaround time

プロセス属性には、プロセス名、到着時間、サービスに必要な時間、サービスに必要な残り時間、完了時間、ターンアラウンドタイム、および加重ターンアラウンドタイムが含まれます。ターンアラウンドタイムは、送信時間と完了時間の間の間隔であり、加重ターンアラウンドタイムはターンアラウンドタイム/実際の実行時間です。

2.キュー



class Queue: def __init__(self,level,process_list): self.level=level self.process_list=process_list self.q=0 def size(self): return len(self.process_list) def get(self,index): return self.process_list[index] def add(self,process): self.process_list.append(process) def delete(self,index): self.process_list.remove(self.process_list[index])

キューを設定するには、初期化メソッドはキューとキューに含まれるプロセスのリストを優先する必要があります。ちなみに、キューのいくつかの属性を取得するメソッドを定義します。

次に、使用される特定のアルゴリズムプログラムがあります。
3.ラウンドロビンスケジューリングアルゴリズム（RR）

class RR: def __init__(self,process_list,q): self.process_list=process_list self.q=q def scheduling(self): process_list.sort(key=lambda x:x.arrive_time)#Sort by .arrive_time len_queue=len(self.process_list) #The length of the process queue index=int(0) #index q=self.q # running_time=int(0)#Already running time #Scheduled loop while(True): #Current Process current_process=self.process_list[index%len_queue] #Judge whether the current process has been completed if current_process.left_serve_time>0: #Calculate completion time #The service time is greater than or equal to the time slice, then the completion time + time slice time This process has not ended #If the service time is less than the time slice, the completion time will be added to the original time to continue the service if current_process.left_serve_time>=q: running_time+=q #print(current_process.name,running_time,index) current_process.left_serve_time-=q else : #print('%s still needs service time less than the current time slice'%current_process.name) running_time+=current_process.left_serve_time current_process.left_serve_time=0 #completed if current_process.left_serve_time==0: #Calculate completion time current_process.finish_time=running_time #Calculate turnaround time current_process.cycling_time=current_process.finish_time-current_process.arrive_time #Calculate weighted turnaround time current_process.w_cycling_time=float(current_process.cycling_time)/current_process.serve_time #print print('%s process has completed the process, the details are as follows:'%current_process.name) print('Process name: %s, completion time: %d, turnaround time: %d, weighted turnaround time: %.2f'%(current_process.name,current_process.finish_time,current_process.cycling_time,current_process.w_cycling_time)) #pop up self.process_list.remove(current_process) len_queue=len(self.process_list) #After a process completes the task, the index is first rolled back and then added to keep pointing to the next process that needs to be scheduled index-=1 #indexRegular increase index+=1 #If there is no process in the queue, the execution is complete if len(self.process_list)==0: break #Change index, to avoid errors when taking modulo because index is greater than len if index>=len(self.process_list): index=index%len_queue

マルチレベルフィードバックキュースケジューリングアルゴリズムは、最後のキューでプロセスを実行するために使用されます。個別に取得した場合、これは完全なアルゴリズム実装コードでもあります。次のコードにも、対応するテストコードがあります。



4.マルチレベルフィードバックキュースケジューリングアルゴリズム

class MulitlevedFeedbackQueue(): def __init__(self,queue_list,q_first): self.queue_list=queue_list self.q_first=q_first def scheduling(self): q_list=self.queue_list #Current queue collection q_first=self.q_first #The time slice of the first queue for i in range(len(q_list)): #Determine the time slice of each queue if i==0: q_list[i].q=q_first else : q_list[i].q=q_list[i-1].q*2 #Execute the time slice from the first queue #First determine whether it is the last queue, the last queue directly executes the RR scheduling algorithm #If it is not the last queue, it will judge whether it is necessary to join the end of the next queue after executing the current queue time slice if i==len(q_list)-1: print('**************Execute RR scheduling algorithm for the last queue *************') #print(q_list[i].process_list[]) #Reset the arrival time of the last queue for t in range(len(q_list[i].process_list)): q_list[i].process_list[t].arrive_time=t rr_last_queue=RR(q_list[i].process_list,q_list[i].q) rr_last_queue.scheduling() else: currentQueue=q_list[i] index=int(0) while(True): if currentQueue.get(index).left_serve_time>q_list[i].q: currentQueue.get(index).left_serve_time-=q_list[i].q print('Number %d queue time slice: %d'%(i,q_list[i].q)) print('The process has not been executed, it needs to be added to the end of the next queue: process name: %s'%(currentQueue.get(index).name)) #Throw the current process to the end of the next queue q_list[i+1].add(currentQueue.get(index)) index+=1 else: print('Service complete and pop up:',currentQueue.get(index).name) currentQueue.get(index).left_serve_time=0 currentQueue.delete(index) if index==currentQueue.size(): break

上記は、マルチレベルのフィードバックキュースケジューリングアルゴリズムです。最後のキューは3番目のコードスライスでRRアルゴリズムを使用し、その他は上記のアルゴリズムの詳細に従って実装されます。

5.テスト手順

''' test program ''' if __name__=='__main__': '''Generate process''' process_list=[] processA=Process('A',0,4) processB=Process('B',1,3) processC=Process('C',2,4) processD=Process('D',3,2) processE=Process('E',4,4) process_list.append(processA),process_list.append(processB),process_list.append(processC) process_list.append(processD),process_list.append(processE) '''Use RR scheduling algorithm, time slice is 1''' print('#################################################################') print('---------------------------Round scheduling algorithm------------------- -------') print('#################################################################') rr=RR(process_list,1) rr.scheduling() '''Use multi-level feedback queue scheduling algorithm''' print() print('#################################################################') print('-----------------------Test the multi-level feedback queue scheduling algorithm------------------- ---') print('#################################################################') processA=Process('A',0,4) processB=Process('B',1,3) processC=Process('C',2,4) processD=Process('D',3,2) processE=Process('E',4,4) process_list0,process_list1,process_list2=[],[],[] process_list0.append(processA),process_list0.append(processB) process_list1.append(processC),process_list1.append(processD) process_list2.append(processE) #queue queue_list=[] queue0=Queue(0,process_list0) queue1=Queue(1,process_list1) queue2=Queue(2,process_list2) queue_list.append(queue0),queue_list.append(queue1),queue_list.append(queue2) #Using multi-level feedback queue scheduling algorithm, the first queue time slice is 1 mfq=MulitlevedFeedbackQueue(queue_list,1) mfq.scheduling()

結果を達成する：
画像

最後に、マルチレベルフィードバックキュースケジューリングアルゴリズムの利点を要約します。

  • さまざまなプロセスに必要な実行時間を事前に知らなくても、さまざまなタイプのプロセスのニーズをより適切に満たすことができます。

  • 優先度の高いジョブと短いジョブ（プロセス）の両方に迅速に対応できます。 （FCFSと高優先度応答比スケジューリングアルゴリズムの欠点を比較してください）。

  • 長時間動作と短時間動作の両方を考慮し、良好な応答時間と強力な実現可能性を備えており、さまざまな動作環境に適しています。

コードのダウンロードアドレスを突いてください
https://github.com/LIANGQINGYUAN/OperatingSystens/blob/master/Multilleved_Feedback_Queue.py

ウェルカムスター、カニ！ ！ ！