Assign each data structure to at least one scenario: Explain: 1. why you chose t

Question

Assign each data structure to at least one scenario:

Explain: 1. why you chose the data structure.

2. whether you would use java's implementation of the data structure.

3. describe why the data structure is the best for efficiency.

Scenario 7: A printer queue prioritizes all print jobs in the following way. Three data structures are used to prioritize the jobs. All short jobs of 1 page are put on a data structure that has the first in first out property; all jobs that are 2 to 4 pages are put on a data structure with a last in first out property; all jobs >4 pages are put on a priority queue, prioritized by shortest page length. The printer queue removes items from each of the data structures in a round-robin order: short, middle, long, short, middle, long,... A student in a rush to print her homework submitted her 3 page paper to the printer queue right before a rush of students printed their 4 page papers. An hour later, her paper still hadn't printed. She asks tech support what happened to her paper, and they suggest that she resubmit her paper to the queue. Will this strategy help? What is the name of each data structure that is used for the short, medium, and long jobs? How would you fix the printer queue so that no jobs will be put on the printer queue indefinitely? What are the arguments for including job size as a reason for prioritization?

Explanation / Answer

Q. What is the name of each data structure that is used for the short, medium, and long jobs?

As per the given passage, the names of the data structures are as follows

i. The data structure used for short jobs will be a Queue, because of it's First-In-First-Out behaviour.

ii. The data structure used for implementing the medium jobs will be a Stack, because of it's LIFO property.

iii. The data structure for implementing the long jobs will be a Priority Queue, prioritized by shortest page length.

Q. whether you would use java's implementation of the data structure?

I would surely use java's implementation of the data structure because it has built in implemetation for the above data sturctures and also we can easily model the jobs in terms of objects. To be honest, what language you do the implementation doesn't actually matters as long as you can implement it in some language.

Q. “... She asks tech support what happened to her paper, and they suggest that she resubmit her paper to the queue. Will this strategy help?...”

The disadvantage with the stack implementation is that the jobs that arrived earlier may get postponed indefinitely. The above mentioned strategy may help only if there are no other rush of students submitting the paper after her. To put simply, it just doesn't gurantee to solve the problem.

Even in case of priority queues used for the long jobs, we may encounter the problem of indefinte waiting as the lower priority jobs may never get the change to run.

Q. How will you fix this?

For the medium jobs we can simply use FIFO queue instead of stack because as they are smaller in size, the waiting time will never be much. However, additionally, we can also use the following fix of the long jobs, for the medium jobs too.

For the long jobs, a simple priority queue implementation will never work. We need to use the “Aging” mechanism to ensure that jobs with lower priority will eventually complete their execution. This method can be used to reduce indefinte waiting of the tasks with lesser priority. It works on the principle that the priority of a process should increase as it waits in the ready queue. The increase in priority may be equal to the waiting time and it's page-length. We can also use the same techinique for the medium jobs. For the short jobs, the implementation of FIFO works efficiently.

What are the arguments for including job size as a reason for prioritization?

The reason for including the job size as the prioritization factor is because, the average waiting time will be reduced compared to FIFO queues. But since, it still leads to indefinite waiting problem, we should also add the "waiting time" along with "job size" as the factos for prioritization.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.