Queue Applications: Scheduling, Buffering, Traversal

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 10.5 Free with a free account

Queue Applications: Scheduling, Buffering, Traversal

Data Structures and Algorithms · Chapter 10: Stacks, Queues, and DequesSection 10.5 · lesson 43 of 8710 min · free with a free account

← Stack Applications: Expressions, Undo and Call TrackingNext lesson: Collections That Grow as Elements Are Added →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Queues for print jobs, bounded buffers, round-robin, and breadth-first search.

  • Explain the fairness and the weakness of a first-come, first-served queue
  • Compare blocking and non-blocking operations on a bounded buffer
  • Trace round-robin scheduling and explain how the slice size changes it
  • Use a queue to find a shortest route with breadth-first search

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,552 words). Read along, or search it.

Opening Question

Which Waiting Item Goes Next

When several things are waiting, which should go next? That question turns up all over computing. If the answer is the one that has waited longest, you need a queue: add at the rear, and remove from the front. Here are four places it does that job: a print queue, a buffer between a producer and a consumer, a round-robin scheduler, and a search for the shortest way through a maze.

Application

A First-Come, First-Served Print Queue

A computer usually has more work than workers. Several documents go to one printer, so something must decide the order. The simplest fair rule is first come, first served, and that's exactly a queue. New jobs join at the rear with offer, and the printer polls the job at the front. So the memo, thesis, label and invoice print in exactly that order. It's fair, since no job is ever passed over, and simple, since the only decision is to take the front. Its weakness shows when job lengths differ. Say the four jobs take two, eight, one and three minutes, all sent together. The memo starts at once, and the thesis waits two minutes. The one-minute label waits ten, stuck behind the thesis, and the invoice waits eleven. The average wait is five point seven five minutes. A long job delays everything behind it, however short the later jobs are.

Application

Bounded Buffers Between Producer and Consumer

Often one part of a program produces items, and another consumes them, at different speeds. A keyboard types in bursts, while a program reads steadily. A network delivers packets unevenly, while a video player shows them at a fixed rate. A buffer is a queue placed between the two. The producer adds at the rear, the consumer removes from the front, and the order is kept. Real buffers are bounded, with a fixed capacity. That's the circular array from earlier in this chapter. A bounded buffer has two edge cases: full and empty. Java's blocking queue handles each in two ways. A blocking method makes the caller wait. Put on a full buffer waits until there's room, and take on an empty one waits until an item arrives. A non-blocking method answers at once. Offer on a full buffer returns false, and the item is not added. Poll on an empty buffer returns null. In one program, a producer and a consumer share a buffer of three, on separate threads. The consumer prints one to ten in order, though neither knows the other's speed. Sharing a queue safely between threads is delicate. That's why ready-made blocking queues are preferred to hand-built ones. Simulate a fast producer and a slow consumer, and the buffer climbs to its capacity. Then the producer has to wait, until the consumer catches up. Two lessons follow. A buffer absorbs bursts: items that arrive faster than they can be used are stored, not lost. But a buffer can't fix a long-run mismatch. If the producer is faster on average, a bigger buffer only delays the moment it fills.

Quick Check

Offer on a Full Buffer

Quick check. A bounded buffer of capacity two holds three and five, so it's full. The producer calls offer with seven, and ignores the result. Then the consumer takes one item, and the producer offers eight. What does the buffer hold now, front first? Pause, and decide. A: it holds five and eight. Offer on the full buffer returned false at once, so seven was never added. Ignoring the result lost it. The take removed three, the front item, and that made room for eight. Five, seven is what put would give, because put waits for room instead of giving up. And seven, eight forgets that three and five were already in line.

Application

Round-Robin Scheduling Rules

Arrival order lets one long task hold up all the others. Round-robin scheduling fixes the worst of that, by giving every task a short, equal turn, called a time slice. Take the task at the front, and let it run for one slice, or until it finishes, if that's sooner. If it's finished, it leaves. If not, it goes to the rear of the queue. Repeat until the queue is empty.

Trace

Three Tasks with a Slice of Three

Take three tasks: A needs five time units, B three, and C eight. With a slice of three, A runs from zero to three, and goes to the back with two left. B runs from three to six, and finishes. C runs from six to nine, and goes back with five left. A finishes at eleven. Then C runs twice more, and finishes at sixteen. In arrival order, the same tasks would simply run back to back: A, then B, then C.

Comparison

Responsiveness Versus Finishing Time

Round robin doesn't finish the work sooner: the last task ends at sixteen either way. What changes is how soon each task starts. Short task B now finishes at six instead of eight, and every task starts within six units. The price is that A, first in line, finishes at eleven instead of five, so the average finishing time gets slightly worse. Round robin trades a little efficiency for responsiveness and fairness.

Key Idea

Choosing the Slice Size

The size of the slice matters. A slice of one takes sixteen turns, and in a real system, every switch between tasks costs time. A slice of three takes six turns, as you just saw. A slice of eight, as long as the longest task, never interrupts anything. So round robin turns back into arrival order.

Quick Check

Finishing Order with a Slice of Two

Quick check. Three tasks wait in the order A, B, C. A needs two units, B needs six, and C needs three. The slice is two. In what order do they finish? Pause, and decide. A, then C, then B. A's two units fit in its first slice, so it finishes at two. B runs from two to four, and goes back with four left. C runs from four to six, and goes back with one left. B runs again, then C finishes at nine, and B finally finishes at eleven. A, B, C would be arrival order, which round robin breaks up. And C can't finish first: it doesn't even start until four.

Application

Fewest Moves Through a Maze

The fourth application is a puzzle: find the fewest moves from the start of a maze to the goal. You move one cell at a time, and never into a wall. The idea is to explore in rings. First every cell one move from S, then every cell two moves away, then three, and so on. The first time the search reaches G, it has used as few moves as possible. A queue makes this automatic.

Algorithm

The Queue Holds the Frontier

The queue holds the frontier: cells that have been found, but not yet examined. Give the start distance zero, and enqueue it. Remove the front cell. If it's the goal, its distance is the answer. Otherwise, look at its four neighbors. Each open neighbor with no distance yet gets one more than the current cell, and joins the rear of the queue. Repeat. If the queue empties without reaching the goal, there's no route.

Trace

Distances Spread in Rings

Run it. S gets zero. Its only open neighbor gets one, and the corridor continues: two, three, and four in the middle row. From four, the search spreads both ways: five on each side, then six at both ends of the row. Then seven, up, down, and on the left, and eight beyond them. When G is removed, at step fourteen, its distance is eight. Read the distances in removal order: zero, one, two, three, four, five, five, six, six. They never decrease.

Worked Example

Walking Back from the Goal

The route itself comes from walking back from G. At each step, move to a neighbor whose distance is exactly one smaller. From eight, that's seven, six, five, four, three, two, one, and back to S: a shortest route. Two cells in the bottom row were never even reached. The search stopped as soon as G was removed.

Key Idea

Why a Queue Finds the Shortest Route

Why does it work? The queue holds cells of at most two distances, d and d plus one, with all the d cells in front. Each removed cell adds cells at d plus one, and they join at the rear, behind everything already waiting. So a ring always finishes before the next one begins. Three details matter. Mark a cell when it's enqueued, not when it's removed. Otherwise a cell next to several frontier cells is enqueued again and again. A stack would give a different search. It follows one corridor to its end before backing up, so the first route it finds to G could be longer than necessary. And the cost is proportional to the maze. Each open cell is enqueued at most once, so time and space are both order of the number of cells.

Key Takeaways

Queue Application Essentials

To sum up. A queue fits whenever the order of arrival should decide the order of service. A print queue is fair and simple, but a long job delays everything behind it. A bounded buffer absorbs bursts: put waits when it's full, and take waits when it's empty. Round robin runs the front task for one slice, then sends it to the rear. And breadth-first search, driven by a queue, reaches the goal by a shortest route.

Think About It

Where a New Task Joins

Something to think about. In round robin, a new task arrives while task A is running its slice. Where should the new task join the ready queue? And what would go wrong for the tasks already waiting, if it could join at the front?

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Queue Applications: Scheduling, Buffering, Traversal

What is the difference between put and offer on a Java BlockingQueue?
On a full bounded queue, put waits until there is room, while offer returns false at once and the item is not added. Likewise, on an empty queue, take waits until an item arrives, while poll returns null right away. If code calls offer on a full buffer and ignores the false result, that item is silently lost, so check the return value or use put.
Why does breadth-first search find the shortest path?
Breadth-first search finds a shortest path in an unweighted maze or graph because its queue explores cells in rings of increasing distance. The queue only ever holds cells at distance d and d + 1, with all the d cells in front, so every cell at distance d is removed before any cell at d + 1. The first time the goal is removed, its distance is the fewest possible moves.
How does the time slice size affect round-robin scheduling?
A smaller time slice makes round robin more responsive but causes more switches between tasks, and in a real system every switch costs time. A slice as long as the longest task never interrupts anything, so round robin turns back into arrival order. For tasks needing 5, 3, and 8 units, a slice of 1 takes 16 turns, a slice of 3 takes 6, and a slice of 8 takes 3.
Why should breadth-first search mark a cell when it is enqueued?
Marking a cell as found when it is enqueued, not when it is removed, ensures each cell joins the queue at most once. If marking waits until removal, a cell next to several frontier cells can be enqueued again and again, wasting time and memory. With early marking, each open cell is enqueued at most once, so the search runs in time and space proportional to the number of cells.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →