-
Notifications
You must be signed in to change notification settings - Fork 1
/
mlfq.py
87 lines (72 loc) · 2.89 KB
/
mlfq.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Process:
def __init__(self, name, arrival_time, burst_time):
self.name = name
self.arrival_time = arrival_time
self.burst_time = burst_time
self.started = False
def log_queue(queue, current_time):
print(f"[current time: {current_time}]")
for i, q in enumerate(queue):
print(f"Queue {i}: ", end="")
for p in q:
print(f"[name: {p.name}, burst_time: {p.burst_time}] ", end="")
print()
print()
def mlfq_schedule(queue, completed_processes, current_time):
# Select a process from the queue to execute
for i in range(len(queue)):
if queue[i]:
process = queue[i].pop(0)
if process.burst_time <= 1:
# Process completed
current_time += process.burst_time
process.burst_time = 0
completed_processes.append(process)
else:
# Process executes for a certain time and then returns to the next level queue
current_time += 1
process.burst_time -= 1
if i+1 == len(queue):
queue[i].append(process) # Return to the original queue
else:
queue[i+1].append(process)
# Check if it's time to reinsert all processes to the highest priority queue
if current_time % REINSERT_INTERVAL == 0:
for q in queue[1:]:
for p in q:
queue[0].append(p)
q.clear()
print(f"Reinserted all processes to the highest priority queue at time {current_time}\n")
# Only execute one process per call to the schedule function
break
return current_time
def run(processes, queue_num=4, reinsert_interval=5):
global REINSERT_INTERVAL
REINSERT_INTERVAL = reinsert_interval
# Create multi-level feedback queue
queue = [[] for _ in range(queue_num)]
current_time = 0
completed_processes = []
while True:
for process in processes:
if not process.started and process.arrival_time <= current_time:
# Add the process to the first queue, which is the highest priority queue
queue[0].append(process)
process.started = True
log_queue(queue, current_time)
current_time = mlfq_schedule(queue, completed_processes, current_time)
# Check if all processes have completed
if all(process.burst_time == 0 for process in processes):
break
return completed_processes
if __name__ == "__main__":
# Test case
processes = [
Process("P1", 0, 6),
Process("P2", 2, 5),
Process("P3", 4, 8),
Process("P4", 6, 2)
]
completed_processes = run(processes)
for process in completed_processes:
print(f"Process {process.name} completed")