Emulating the printer job queue process
There are also numerous examples of queues in computer science. For example, computer labs have10computers, which are all connected to the same printer. When students need to print, theirprint jobwill enter aformation. The first task in this queue is the print job that is about to be executed. If a task is at the end of the queue, it must wait until all previous tasks have been executed.
Students send print requests to shared printers, and these print jobs are stored in anformationand in accordance with thefirst come first servedThe order in which they are executed. Such a setup can lead to many problems. One of the most important is whether the printer can handle a certain amount of work. If it can't, students may miss the lesson they are to attend due to waiting too long.
Consider this scenario in a computer lab: in any given hour, the lab is full of10Students. They can print up to2times, and the number of pages to print ranges fromRanging from 1 to 20 pages. The lab's printers are rather old andeach minuteCan only print at low quality10Page. It is also possible to turn up the print quality, but doing so causes the printer toeach minutePrint only5Page. Reducing the print speed may cause students to wait too long. So, how should you set the print speed?
The problem can be solved by constructing a model. We need to build a model for theschoolchildren、print jobcap (a poem)printerBuilding Objects. When a student submitsprint jobWhen we do, we need to add them to the printer'stask queuein the queue. When the printer finishes executing a task, it checks that queue to see if there are any more tasks in it that need to be processed. We are interested in how long the average student has to wait to get a printed article. This time is equal to the average wait time for print jobs in the queue.
Some knowledge of probability needs to be applied in the simulation. For example, a student may print an article with 1 to 20 pages. If the pages occur with equal probability, then the printing task of theActual lengthIt can be calculated by simulating a random number of article pages from 1 to 20.
If the lab has10students, and in thean hourInside everyone printsa fewtimes, thenhourlyThat's an average of20A print job.What is the probability of creating a print request in any given second? Answering this question requires consideration of the ratio of tasks to time. Twenty tasks per hour is equivalent to one task every 180 seconds.
The probability of a print request being created in each second can be modeled by a random number from 1 to 180 (1/180 probability). If the random number is exactly 180, then a print request is considered to have been created.Note that it may happen that multiple requests are created one after the other, or there may be no requests for a long time. This isThe Nature of Analog. We want to simulate as accurately as possible when common parameters are known.
Main simulation steps:
1. Create aPrint job queue. Each missionarrivalWhen there is atimestamp. At first, the queue is empty.
2. For each second (currentSecond), perform the following operations.
- Is there a newly created print job? If so, start the print job with thecurrentSecond as its timestamp and add the task to the queue.
- If the printer is idle and there are tasks waiting to be executed, do the following:
- through (a gap)formationThe first job is taken out of the printer and submitted to the printer;
- expense or outlaycurrentSecond minus the timestamp of the taskThis is the basis for calculating theirwaiting time；
- Place the task'swaiting timeStored in alistings, which is used as the data for calculating the average waiting time;
- According to the mandate of thepagination, calculate the execution time.
- The printer performs a one-second printout while the job from theexecution timeSubtract one second from it.
- If the print job is executed, i.e., the job'sexecution timedecrease to0If the printer returns to theleisure timeStatus.
3. When the simulation is complete, calculate the average wait time based on the values in the wait time list.
Building a queue program
class Queue:
def __init__(self):
= [] # Build empty queues
def isEmpty(self):
return ==[] # Determine if it's empty
def enqueue(self,item):
(0, item) # Insert element at the end of the queue (left end of the list)
def dequeue(self):
return () # Remove elements at the head of the queue (right end of the list)
def size(self):
return len() # Length of queue (list)
Analog Printing Program
import random
# Analog printers
class Printer:
# Printer initialization
def __init__(self, ppm):
= ppm # Print speed Pages per minute
= None # Existing mandates
= 0 # of time required for the task
# Print job countdown 0 for print completion
def tick(self):
# If the printer is running a job
if != None:
# Execution time for this task = Execution time - 1 (Execution time countdown)
= - 1
if <= 0: # Execution time for this task <= 0
= None # The task is complete
# Determine if the printer is idle
def busy(self):
if != None:
return True
else:
return False
# Printer accepts new jobs
def startNext(self, newtask):
= newtask
# of new print jobs = number of pages in new job * (60 / how many pages per minute to print)
# (60 / how many pages are printed per minute speed) = number of seconds it takes to print each page
= () * (60 / )
# Simulate the properties of individual tasks
class Task:
# Task initialization
def __init__(self, time):
= time # Point in time when the task was created
= (1, 21) # of task pages Randomly generated between 1 and 20
def getStamp(self):
return # Get the point in time when the task was created
def getPages(self):
return # of pages to get the task
def waitTime(self, currenttime):
# Waiting time for task = current time - point in time when task was created
return currenttime -
# New print requests created by simulated students
def newPrintTask():
# The print request is a random event
# Simulate the probability of generating a print request per second by a random number between 1 and 180
# If the random number is exactly 180, then a print request is considered to have been created.
num = (1, 181)
if num == 180:
return True
else:
return False
# Simulate the printing process
def simulation(numSeconds, pagesPerMinute):
labprinter = Printer(pagesPerMinute)
printQueue = Queue()
waitingtimes = []
for currentSecond in range(numSeconds):
if newPrintTask():
task = Task(currentSecond)
(task)
if(not ())and(not ()):
nexttask = ()
((currentSecond))
(nexttask)
()
averageWait = sum(waitingtimes)/len(waitingtimes)
print("Average wait %6.2f seconds, %3d tasks still waiting to be processed"
% (averageWait, ()))
Simulate the printing process (with comments)
def simulation(numSeconds, pagesPerMinute):
# numSeconds-Time period
# pagesPerMinute-Print speed, pages per minute
labprinter = Printer(pagesPerMinute) # Create printers
printQueue = Queue() # Create a queue of printer jobs
waitingtimes = [] # Create a sample list of wait time data
for currentSecond in range(numSeconds): # One cycle for one second
if newPrintTask(): # If a print request is created
task = Task(currentSecond) # Create a print job and record the current point in time
(task) # The print job enters the printer job queue
# If the printer is idle and there is a job in the printer job queue
if(not ())and(not ()):
nexttask = () # Take a new task from the queue
# Calculate the wait time for a new task in the task queue based on the current point in time and record the wait time in the sample list.
((currentSecond))
(nexttask) # Start a new job Printer goes busy
() # Decrease the countdown of the current print job execution by one second for each cycle
averageWait = sum(waitingtimes)/len(waitingtimes)
print("Average wait %6.2f seconds, %3d tasks still waiting to be processed" % (averageWait, ()))
It is important to note thattimestampIt's something we've been working on for a long time based oncyclic simulationIt's out. We're set.numSeconds Time periodAfter that, each cycle is equivalent to one second of time elapsed.
Although the results may not be the same for each simulation. But for that we don't need to be concerned. This is due to the nature of random numbers. What we are interested in is whenTrends in results when parameters are changed。
Here are some results:
We have obtained reference data based on simulations on how the printer performs tasks in one hour at both speeds. It is clear to see that when the print quality is increased, the average waiting time of the students increases significantly compared to the low quality case and an increase in the number of unfinished task processing occurs, so setting the printer to the low quality mode is the most appropriate.
summarize
That's all for this post, I hope it was helpful and I hope you'll check back for more from me!