在 Python 中模拟抢占式 M/M/1 队列时出现问题
Problem in simulating a preemptive M/M/1 queue in Python
下面显示了我的代码，它模拟了具有两种到达类型的 M/M/1 抢占式队列，其中第一种类型优先于第二种类型。但是，我不知道为什么在我的代码中抢先规则没有按应有的方式工作。
我的意思是在抢占式队列中，例如，如果类型 2 的作业正在接收服务并且类型 1 的作业到达，则服务器会中断类型 2 作业的服务并开始类型 1 作业的服务。但是，一旦完成类型 1 作业的服务，它 应该 继续 中断的类型 2 作业的服务。
在我的代码中，如果工作类型 2 正在接受服务并且工作类型 1 到达，则工作类型 2 会立即永久离开系统。我想知道您能否告诉我为什么会发生这种情况以及我该如何解决？
非常感谢您提前付出的时间和精力。
import random
import simpy
rn_seed = 10
t1_interval_arrivals = 20.0
t2_interval_arrivals = 1
t1_interval_service = 5
t2_interval_service = 20
def type_1_generator(env, interval, server):
i = 0
while True:
c = job(env, "type_1"+" #"+ str(i), "type_1", server, t1_interval_service)
env.process(c)
t = random.expovariate(1.0 / interval)
yield env.timeout(t)
i +=1
def type_2_generator(env, interval, server):
i = 0
while True:
c = job(env, "type_2"+" #"+str(i), "type_2", server, t2_interval_service)
env.process(c)
t = random.expovariate(1.0 / interval)
yield env.timeout(t)
i +=1
def job(env, name, typ , server, sr_interval):
arrive = env.now
print("Job", name, "Arrived at: ",arrive)
service_interval = random.expovariate(1.0 / sr_interval)
print("Job", name, "Service time: ",service_interval)
if typ == "type_1":
while service_interval:
with server.request(priority=1) as req:
yield req
yield env.timeout(service_interval)
service_interval = 0
print("Job", name, "Left system at: ",env.now)
elif typ == "type_2":
while service_interval:
try:
start = env.now
with server.request(priority=2) as req:
yield req
yield env.timeout(service_interval)
service_interval = 0
print("Job", name, "Left system at: ",env.now)
except simpy.Interrupt:
print("Job", name, "Is interrupted at: ",env.now)
service_interval -= env.now - start
print("Job", name, "Remaining service: ",env.now)
print("Job", name, "Left system at ",env.now)
# Setup and start the simulation
random.seed(rn_seed)
env = simpy.Environment()
# Start processes and run
server = simpy.PreemptiveResource(env, capacity=1)
env.process(type_1_generator(env, t1_interval_arrivals, server))
env.process(type_2_generator(env, t2_interval_arrivals, server))
env.run()
以下是结果示例：
Job type_2 #1 Arrived at: 0.5601717881563535
Job type_2 #1 Service time: 34.69876113045603
Job type_1 #1 Arrived at: 16.94474499667717
Job type_1 #1 Service time: 0.22635015810062187
Job type_2 #1 Is interrupted at: 16.94474499667717
Job type_2 #1 Remaining service: 18.31418792193521
Job type_2 #1 Left system at 16.94474499667717
Job type_1 #1 Left system at: 17.17109515477779
在上面的结果中，您可以看到一旦“Job type_1 #1”到达 16.94，服务器就中断了“Job type_2 #1”的服务以及该作业的剩余服务时间是 18.31。但是，一旦服务器完成“Job type_1 #1”，它就不会继续为“Job type_2 #1”提供服务。事实上，当“Job type_1 #1”到达时，“Job type_2 #1”立即离开了系统。这清楚地表明我的代码有什么问题。为什么“Job type_2 #1”立即离开系统并且服务器不再继续为该作业提供服务？
我对您的代码进行了一些更改。需要注意的是，当您重新提交对资源的请求时，它会被放在队列的末尾。所以我给了中断的第二类工作比新的第二类工作更高的优先级。第一类作业仍然具有最高优先级。我还添加了一些打印语句。
import random
import simpy
rn_seed = 10
t1_interval_arrivals = 20.0
t2_interval_arrivals = 1
t1_interval_service = 5
t2_interval_service = 20
# use for unique id across all jobs
i = 0
def type_1_generator(env, interval, server):
global i
while i < 6:
c = job(env, "type_1"+" #"+ str(i), "type_1", server, t1_interval_service)
i +=1
env.process(c)
t = random.expovariate(1.0 / interval)
yield env.timeout(t)
def type_2_generator(env, interval, server):
global i
while i < 4:
c = job(env, "type_2"+" #"+str(i), "type_2", server, t2_interval_service)
i +=1
env.process(c)
t = random.expovariate(1.0 / interval)
yield env.timeout(t)
def job(env, name, typ , server, sr_interval):
"""
use three priorites so interuped jobs can
take precendence over type 2 jobs that have
not started yet
job priorities are:
type 1: 1
type 2: 3
interupted type 2: 2
"""
arrive = env.now
print("Job", name, "Arrived at: ",arrive)
service_interval = random.expovariate(1.0 / sr_interval)
print("Job", name, "Service time: ",service_interval)
if typ == "type_1":
while service_interval:
with server.request(priority=1) as req:
yield req
print("Job", name, "seized resource at: ",env.now)
yield env.timeout(service_interval)
service_interval = 0
print("Job", name, "released resource at: ",env.now)
print("Job", name, "finished at: ",env.now)
elif typ == "type_2":
priority=3
while service_interval:
try:
with server.request(priority=priority) as req:
yield req
start = env.now
if priority == 3:
print("Job", name, "seized resource at: ",env.now)
else:
print("Job", name, "resumed with resource at: ",env.now)
yield env.timeout(service_interval)
service_interval = 0
print("Job", name, "released resource at: ",env.now)
except simpy.Interrupt:
# up priority to take precenance of not started jobs
priority=2
print("Job", name, "Is interrupted at: ",env.now)
service_interval -= env.now - start
print("Job", name, "Remaining service: ",service_interval)
print("Job", name, "finished ",env.now)
# Setup and start the simulation
random.seed(rn_seed)
env = simpy.Environment()
# Start processes and run
server = simpy.PreemptiveResource(env, capacity=1)
env.process(type_1_generator(env, t1_interval_arrivals, server))
env.process(type_2_generator(env, t2_interval_arrivals, server))
env.run()
下面显示了我的代码，它模拟了具有两种到达类型的 M/M/1 抢占式队列，其中第一种类型优先于第二种类型。但是，我不知道为什么在我的代码中抢先规则没有按应有的方式工作。 我的意思是在抢占式队列中，例如，如果类型 2 的作业正在接收服务并且类型 1 的作业到达，则服务器会中断类型 2 作业的服务并开始类型 1 作业的服务。但是，一旦完成类型 1 作业的服务，它 应该 继续 中断的类型 2 作业的服务。
在我的代码中，如果工作类型 2 正在接受服务并且工作类型 1 到达，则工作类型 2 会立即永久离开系统。我想知道您能否告诉我为什么会发生这种情况以及我该如何解决？
非常感谢您提前付出的时间和精力。
import random
import simpy
rn_seed = 10
t1_interval_arrivals = 20.0
t2_interval_arrivals = 1
t1_interval_service = 5
t2_interval_service = 20
def type_1_generator(env, interval, server):
i = 0
while True:
c = job(env, "type_1"+" #"+ str(i), "type_1", server, t1_interval_service)
env.process(c)
t = random.expovariate(1.0 / interval)
yield env.timeout(t)
i +=1
def type_2_generator(env, interval, server):
i = 0
while True:
c = job(env, "type_2"+" #"+str(i), "type_2", server, t2_interval_service)
env.process(c)
t = random.expovariate(1.0 / interval)
yield env.timeout(t)
i +=1
def job(env, name, typ , server, sr_interval):
arrive = env.now
print("Job", name, "Arrived at: ",arrive)
service_interval = random.expovariate(1.0 / sr_interval)
print("Job", name, "Service time: ",service_interval)
if typ == "type_1":
while service_interval:
with server.request(priority=1) as req:
yield req
yield env.timeout(service_interval)
service_interval = 0
print("Job", name, "Left system at: ",env.now)
elif typ == "type_2":
while service_interval:
try:
start = env.now
with server.request(priority=2) as req:
yield req
yield env.timeout(service_interval)
service_interval = 0
print("Job", name, "Left system at: ",env.now)
except simpy.Interrupt:
print("Job", name, "Is interrupted at: ",env.now)
service_interval -= env.now - start
print("Job", name, "Remaining service: ",env.now)
print("Job", name, "Left system at ",env.now)
# Setup and start the simulation
random.seed(rn_seed)
env = simpy.Environment()
# Start processes and run
server = simpy.PreemptiveResource(env, capacity=1)
env.process(type_1_generator(env, t1_interval_arrivals, server))
env.process(type_2_generator(env, t2_interval_arrivals, server))
env.run()
以下是结果示例：
Job type_2 #1 Arrived at: 0.5601717881563535
Job type_2 #1 Service time: 34.69876113045603
Job type_1 #1 Arrived at: 16.94474499667717
Job type_1 #1 Service time: 0.22635015810062187
Job type_2 #1 Is interrupted at: 16.94474499667717
Job type_2 #1 Remaining service: 18.31418792193521
Job type_2 #1 Left system at 16.94474499667717
Job type_1 #1 Left system at: 17.17109515477779
在上面的结果中，您可以看到一旦“Job type_1 #1”到达 16.94，服务器就中断了“Job type_2 #1”的服务以及该作业的剩余服务时间是 18.31。但是，一旦服务器完成“Job type_1 #1”，它就不会继续为“Job type_2 #1”提供服务。事实上，当“Job type_1 #1”到达时，“Job type_2 #1”立即离开了系统。这清楚地表明我的代码有什么问题。为什么“Job type_2 #1”立即离开系统并且服务器不再继续为该作业提供服务？
我对您的代码进行了一些更改。需要注意的是，当您重新提交对资源的请求时，它会被放在队列的末尾。所以我给了中断的第二类工作比新的第二类工作更高的优先级。第一类作业仍然具有最高优先级。我还添加了一些打印语句。
import random
import simpy
rn_seed = 10
t1_interval_arrivals = 20.0
t2_interval_arrivals = 1
t1_interval_service = 5
t2_interval_service = 20
# use for unique id across all jobs
i = 0
def type_1_generator(env, interval, server):
global i
while i < 6:
c = job(env, "type_1"+" #"+ str(i), "type_1", server, t1_interval_service)
i +=1
env.process(c)
t = random.expovariate(1.0 / interval)
yield env.timeout(t)
def type_2_generator(env, interval, server):
global i
while i < 4:
c = job(env, "type_2"+" #"+str(i), "type_2", server, t2_interval_service)
i +=1
env.process(c)
t = random.expovariate(1.0 / interval)
yield env.timeout(t)
def job(env, name, typ , server, sr_interval):
"""
use three priorites so interuped jobs can
take precendence over type 2 jobs that have
not started yet
job priorities are:
type 1: 1
type 2: 3
interupted type 2: 2
"""
arrive = env.now
print("Job", name, "Arrived at: ",arrive)
service_interval = random.expovariate(1.0 / sr_interval)
print("Job", name, "Service time: ",service_interval)
if typ == "type_1":
while service_interval:
with server.request(priority=1) as req:
yield req
print("Job", name, "seized resource at: ",env.now)
yield env.timeout(service_interval)
service_interval = 0
print("Job", name, "released resource at: ",env.now)
print("Job", name, "finished at: ",env.now)
elif typ == "type_2":
priority=3
while service_interval:
try:
with server.request(priority=priority) as req:
yield req
start = env.now
if priority == 3:
print("Job", name, "seized resource at: ",env.now)
else:
print("Job", name, "resumed with resource at: ",env.now)
yield env.timeout(service_interval)
service_interval = 0
print("Job", name, "released resource at: ",env.now)
except simpy.Interrupt:
# up priority to take precenance of not started jobs
priority=2
print("Job", name, "Is interrupted at: ",env.now)
service_interval -= env.now - start
print("Job", name, "Remaining service: ",service_interval)
print("Job", name, "finished ",env.now)
# Setup and start the simulation
random.seed(rn_seed)
env = simpy.Environment()
# Start processes and run
server = simpy.PreemptiveResource(env, capacity=1)
env.process(type_1_generator(env, t1_interval_arrivals, server))
env.process(type_2_generator(env, t2_interval_arrivals, server))
env.run()