In Progress
Unit 1, Lesson 21
In Progress

Full Utilization

Video transcript & code

Full Utilization

It's been a long day of playing in the forest, and now we're all gathered around the fire circle ready to sing some campfire songs and munch on tasty snacks. That's right: it's time to break out the graham crackers, chocolate bars, and marshmallows and make some s'mores!

The question is, how quickly can we provide s'mores for our whole troop?

In order to track our efficiency, let's create a Smore class.

It has fields for when the treat was started and when it was finished, as well as for which camper it is intended for.

It also has a method to report how long they had to wait for their snack.


class Smore
  attr_accessor :started_at, :finished_at
  attr_reader   :camper

  def initialize(camper)
    @camper      = camper
    @started_at  = started_at
    @finished_at = finished_at
  end

  def wait
    finished_at - started_at
  end
end

For the sake of quick and easy testing, instead of using real time and real sleeps in this code, we're going to simulate time as a series of 1-second ticks starting from zero.


$tick = 0

We'll simulate work by advancing the clock a given number of seconds.


def work(seconds)
  $tick += seconds
end

Let's also define a little helper method for logging events with a timestamp.

We use a string format to right-justify the timestamp numbers.


def log(message)
  puts "%3d: %s" % [$tick, message]
end

Let's try this out:


log "Gathering around the campfire"
# >>   0: Gathering around the campfire

Our camping group has lots of hungry hikers, but for the purposes of today's episode we'll focus on just three of them.


smore_orders = ["Kashti", "Ebba", "Ylva"]

We'll map this list to a list of s'more orders in progress.


smores       = smore_orders.map{|camper| Smore.new(camper)}

Now, last year's s'more-making free-for-all was a messy disaster, so we've determined that this year we're going to do things a little differently. This time around, we're going to assign campers to specific roles in the s'more-creation process.

Unfortunately the bags of marshmallows sat in the hot sun a little too long, so the first role is someone to carefully extract one intact candy from the sticky mass of marshmallows.

We'll call them the MarshmallowWrangler.

They have one job: get a marshmallow.

This method will record when the s'more was started...

Simulate 20 seconds of work...

And then log the fact that a marshmallow is ready.


class MarshmallowWrangler
  def get_marshmallow(smore)
    smore.started_at = $tick
    work(20)
    log("A marshmallow is ready for #{smore.camper}")
  end
end

Our next job description is for someone to skewer the marshmallow on a sharpened stick and toast it over the fire.


class Toaster
  def toast_marshmallow(smore)
    work(60)
    log("A marshmallow is toasty warm for #{smore.camper}")
  end
end

Finally, we need a camper to take the hot toasted marshmallow, sandwich it with some chocolate between two graham crackers, and then wait until it melts the chocolate to the perfect state of gooey scrumptiousness.


class Assembler
  def assemble_smore(smore)
    work(30)
    smore.finished_at = $tick
    log("Your s'more is ready, #{smore.camper}!")
  end
end

Let's get our s'more-prep staff ready!


wrangler     = MarshmallowWrangler.new
toaster      = Toaster.new
assembler    = Assembler.new

Now, it's simply a matter of getting a marshmallow for each s'more...


smores.each do |smore|
  wrangler.get_marshmallow(smore)
end

...then toasting those marshmallows...


smores.each do |smore|
  toaster.toast_marshmallow(smore)
end

...and then assembling the finished treats.


smores.each do |smore|
  assembler.assemble_smore(smore)
end

OK, let's see how our work assignment turned out. We'll calculate the shortest and longest s'more-making times.


shortest_prep = smores.min_by(&:wait)
longest_prep = smores.max_by(&:wait)

Then we'll wrap up with some reporting.


log "Everyone has a s'more!"
log "Shortest prep: #{shortest_prep.camper} at #{shortest_prep.wait} seconds"
log "Longest prep: #{longest_prep.camper} at #{longest_prep.wait} seconds"

Let's run this and see what we get.


# >>   0: Gathering around the campfire
# >>  20: A marshmallow is ready for Kashti
# >>  40: A marshmallow is ready for Ebba
# >>  60: A marshmallow is ready for Ylva
# >> 120: A marshmallow is toasty warm for Kashti
# >> 180: A marshmallow is toasty warm for Ebba
# >> 240: A marshmallow is toasty warm for Ylva
# >> 270: Your s'more is ready, Kashti!
# >> 300: Your s'more is ready, Ebba!
# >> 330: Your s'more is ready, Ylva!
# >> 330: Everyone has a s'more!
# >> 330: Shortest prep: Kashti at 270 seconds
# >> 330: Longest prep: Ylva at 290 seconds

Well the good news is that everyone has a s'more. But unfortunately, there are some complaints.

We used a "batching" model for our s'more preparation. First we fetched all our marshmallows, then we toasted them in sequence, then we assembled each s'more. As a result, even though a s'more could theoretically be made in as little as 110 seconds,

the shortest wait was actually 270 seconds,

and the longest was 290!

We could try a serial approach instead of a batch model. In this approach we make one s'more from start to finish, before starting on the next one.


smores.each do |smore|
  wrangler.get_marshmallow(smore)
  toaster.toast_marshmallow(smore)
  assembler.assemble_smore(smore)
end

Let's try this variation.


# >>   0: Gathering around the campfire
# >>  20: A marshmallow is ready for Kashti
# >>  80: A marshmallow is toasty warm for Kashti
# >> 110: Your s'more is ready, Kashti!
# >> 130: A marshmallow is ready for Ebba
# >> 190: A marshmallow is toasty warm for Ebba
# >> 220: Your s'more is ready, Ebba!
# >> 240: A marshmallow is ready for Ylva
# >> 300: A marshmallow is toasty warm for Ylva
# >> 330: Your s'more is ready, Ylva!
# >> 330: Everyone has a s'more!
# >> 330: Shortest prep: Kashti at 110 seconds
# >> 330: Longest prep: Kashti at 110 seconds

The good news here is that all of the s'mores take the minimum possible time to make, 110 seconds. But the bad news is that some campers have to wait much longer than others!

While Kashti has a s'more in his hands quickly,

Ylva had to wait five and a half minuts for hers!

There's a pretty obvious problem with our s'more-making workflow. Even though we have separate campers assigned to each role, only one of them is working at a time! Our workers are under-utilized. But there's no reason for the marshmallow wrangler and the toaster to sit idle while the assembler puts together a finished sandwich. In order to achieve maximum utilization, we need to find a way interleave their work, while still keeping the whole process coordinated.

Just to get an idea of what it means for the work to be interleaved, let's start by coordinating it manually.

In order to do this, we're going to split each prepper's task into a start and a finish method.

For the MarshmallowWrangler, the start method begins with a guard clause. It uses an instance variable called @ready_at to check to see if the object is done with its last task yet. If not, it raises an exception.

This clause is just there to keep us honest. It ensures we won't accidentally try to tell the wrangler to get a second marshmallow when the last one isn't ready yet.

Next up this method sets the @ready_at variable to 20 seconds in the future, and then marks the smore as having been started.

The finish method simply reports the fact that a marshmallow is now ready for the next phase.

The other two prepper classes have their methods split in much the same way.


class MarshmallowWrangler
  def start(smore)
    fail "I'm busy!" unless @ready_at.to_i <= $tick
    @ready_at = $tick + 20
    smore.started_at = $tick
  end

  def finish(smore)
    log("A marshmallow is ready for #{smore.camper}") 
  end
end

class Toaster
  def start(smore)
    fail "I'm busy!" unless @ready_at.to_i <= $tick
    @ready_at = $tick + 60
  end

  def finish(smore)
    log("A marshmallow is toasty warm for #{smore}")
  end
end

class Assembler
  def start(smore)
    fail "I'm busy!" unless @ready_at.to_i <= $tick
    @ready_at = $tick + 30
  end

  def finish(smore)
    smore.finished_at = $tick
    log("Your s'more is ready, #{smore}!")
  end
end

Now for the fun part: manually scheduling the work so that no one's time is wasted and smores are prepared as quickly as possible with only three workers.

First, we tell the wrangler to start un-sticking the first marshmallow.

Then we give it 20 seconds to work.

Then we finish that task and start on the next marshmallow.

We also let the toaster know to start toasting the first marshmallow.

Next we let another 20 seconds pass.

Then we finish up fetching the second marshmallow and begin the third.

Then another 20 seconds to finish getting the last marshmallow out of the bag.

After another 20 seconds the toaster should be done toasting the first marshmallow.

...and so one, and so on, and so on.

We manually schedule the start and end of each task, ensuring that just enough time passes for a worker to be done, and making sure that all workers are occupied at all times.


wrangler.start(smores[0])
work(20)
wrangler.finish(smores[0])
wrangler.start(smores[1])
toaster.start(smores[0])
work(20)
wrangler.finish(smores[1])
wrangler.start(smores[2])
work(20)
wrangler.finish(smores[2])
work(20) # 80
toaster.finish(smores[0])
toaster.start(smores[1])
assembler.start(smores[0])
work(30) # 110
assembler.finish(smores[0])
work(30) # 140
toaster.finish(smores[1])
toaster.start(smores[2])
assembler.start(smores[1])
work(30) # 170 
assembler.finish(smores[1])
work(30) # 200
toaster.finish(smores[2])
assembler.start(smores[2])
work(30) # 230
assembler.finish(smores[2])

This is obviously not a practical or sustainable way to program. But it gives us a very clear visual representation of exactly the kind of coordination that needs to occur for these three tasks to be managed efficiently.

When we run this, we get results that are a little different from our previous two attempts.


# >>   0: Gathering around the campfire
# >>  20: A marshmallow is ready for Kashti
# >>  40: A marshmallow is ready for Ebba
# >>  60: A marshmallow is ready for Ylva
# >>  80: A marshmallow is toasty warm for Kashti
# >> 110: Your s'more is ready, Kashti!
# >> 140: A marshmallow is toasty warm for Ebba
# >> 170: Your s'more is ready, Ebba!
# >> 200: A marshmallow is toasty warm for Ylva
# >> 230: Your s'more is ready, Ylva!
# >> 230: Everyone has a s'more!
# >> 230: Shortest prep: Kashti at 110 seconds
# >> 230: Longest prep: Ylva at 190 seconds

It finishes a hundred seconds sooner than our other tries. That's because we've arranged for full or at least nearly full utilization of our workers.

But at what cost? First off we had to drastically restructure our food prepper classes in order to separate the start and finish of each task.


class MarshmallowWrangler
  def start(smore)
    fail "I'm busy!" unless @ready_at.to_i <= $tick
    @ready_at = $tick + 20
    smore.started_at = $tick
  end

  def finish(smore)
    log("A marshmallow is ready for #{smore.camper}") 
  end
end

And the lengths we went to to manually coordinate the tasks are simply impractical and unsustainable in a real-world codebase.


wrangler.start(smores[0])
work(20)
wrangler.finish(smores[0])
wrangler.start(smores[1])
toaster.start(smores[0])
work(20)

If only there were some way of automatically coordinating the work for full utilization. That's a problem we'll tackle in an upcoming episode. Until then, happy hacking!

Responses