1. Multi-level feedback queue scheduling algorithm

Multi-level feedback queue scheduling algorithm is a kind of process scheduling algorithm, the scheduling algorithm can not know the execution time required by various processes in advance, but also can better meet the needs of various types of processes, is a better process scheduling algorithm commonly recognized at present.

Now, you might immediately ask, how does a multilevel feedback queue scheduling algorithm actually schedule? I think a lot of algorithms can be expressed in one graph + one sentence, so I’m going to try to make the algorithm look as clear as possible with images.

In a word:

Multi-stage feedback queue scheduling algorithm. “Multi-stage” refers to multiple queues with different priorities. “Feedback” refers to that if a process joins a queue with a higher priority, it immediately stops the current task and switches to the process in the queue with a higher priority.

A picture:

The figure above shows an example of A schedule, with processes A(4), B(3), C(4), D(2), E(4), and the time required to be serviced in parentheses. Let the first queue time slice q=1, because the rule of the time slice in this algorithm is: the length of the latter time slice is twice that of the previous one, so the second queue time slice Q =2, and the third queue time slice Q =4.

If not, put to the end of the next queue (orange)

At the end of the queue, the RR algorithm is executed, that is, the service is executed one time slice at a time, until the loop runs out of processes.

Python3 implementation code

First, I’ll describe the structures used in the program

1. Process/Task structure

class Process: def __init__(self,name,arrive_time,serve_time): Self. name=name # Process name self.arrive_time=arrive_time # arrive_time self.serve_time=serve_time # Service time Self.left_serve_time =serve_time # Self.finish_time =0 # Cycling_time =0 # cycle time self.w_cycling_time=0 # Turnaround time with rightsCopy the code

The attributes of a process are process name, arrival time, time needed to be serviced, remaining time needed to be serviced, completion time, turnaround time, and turnaround time with weights. The turnaround time is the interval between submission time and completion time; The authorized turnaround time is the turnaround time/actual running time.

2. The queue

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])Copy the code

To set up a queue, the initialization method needs to give priority to the queue, and the list of processes contained in the queue, and define methods to get some attributes of the queue.

3. Multi-level feedback queue scheduling algorithm (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)# process queue=len(self.process_list) # process queue length index=int(0) # index q=self.q # time slice running_time=int(0)# time that has been run # scheduler loop while(True): # current_process=self.process_list[index%len_queue] # if current_process. Left_serve_time >0: If current_process. Left_serve_time >=q: if current_process. running_time+=q #print(current_process.name,running_time,index) current_process.left_serve_time-=q else : #print('%s still need to serve time less than the current time segment '%current_process.name) running_time+=current_process.left_serve_time If current_process. Left_serve_time ==0: Finish_time =running_time Current_process.cycling_time =current_process.finish_time-current_process.arrive_time # Calculate the weighted turnover time Current_process. w_cycling_time=float(current_process.cycling_time)/current_process.serve_time # print('%s') '%current_process.name 'print(' process name: %s, completion time: %d, turnover time: %d, weighted turnover time: %d,  %.2f'%(current_process.name,current_process.finish_time,current_process.cycling_time,current_process.w_cycling_time)) Self.process_list. Remove (current_process) len_queue=len(self.process_list) If len(self.process_list)==0: len(self.process_list)==0: len(self.process_list)==0: len(self.process_list)==0: If index>=len(self.process_list): index=index%len_queueCopy the code

The multi-stage feedback queue scheduling algorithm is used to execute the process in the last queue. If it is taken out separately, it is also a complete algorithm implementation code. The following code also has the corresponding test code.

4. Multi-level feedback queue scheduling algorithm

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 # q_first=self. Q_first # for I in range(len(q_list)): q_list[i].q=q_first else : Q_list [I].q=q_list[I -1].q*2 If I ==len(q_list)-1 if I ==len(q_list)-1: Print (' * * * * * * * * * * * * * * to perform RR last queue scheduling algorithm * * * * * * * * * * * * * ') # print (q_list [I] process_list []) # last queue resetting the arrival time 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]. %d'%(I,q_list[I].q)) print(' process is not finished and needs to be added to the end of the next queue: Q_list [I +1].add(currentQueue.get(index)) index+=1 else: Print (' queue.get (index).name ',currentQueue.get(index).left_serve_time=0 currentQueue.delete(index) if index==currentQueue.size(): breakCopy the code

The above is the multi-level feedback queue scheduling algorithm. The last queue uses the RR algorithm in the third code slice, and the others are implemented according to the above algorithm details.

5. Test the program

"Test program" "if __name__=='__main__': 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) "" uses RR scheduling algorithm, Time slice is 1 "' print (' # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ') Print (" -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- rotation scheduling algorithm -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - ') print('#################################################################') rr=RR(process_list,1) rr.scheduling() "' using multi-level feedback queue scheduling algorithm 'print () print (' # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #') Print (" -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- test multi-level feedback queue scheduling algorithm -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - ') Print (' # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ') processA Process of = (' 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_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) # Queue_list.append (queue0),queue_list.append(queue1),queue_list.append(queue2) # mfq=MulitlevedFeedbackQueue(queue_list,1) mfq.scheduling()Copy the code

Results:

Download the code at github.com/LIANGQINGYU…

Welcome Star, crab crab!!