15110 Spring 2013 [Kaynar/Gunawardena]

Problem Set 9 - due Friday, April 5 in class

Reading Assignment

Read Chapter 4 of Blown to Bits.

Instructions

  1. (2 pts) An operating system is a program that controls the operation of a computational device (computer, cell phone, game console, etc.).

    1. An operating system contains a component called the kernel as shown below.


      (http://en.wikipedia.org/wiki/File:Kernel_Layout.svg)

      What role does the kernel play? (You may look this up online and quote any reliable source you find, citing where you got the information. But if you quote from a website, you should still summarize what you quoted in your own words. Don't just copy someone else's words without thinking about what they mean.)

    2. Briefly explain how the operating system uses the principle of multitasking to run a number of programs "concurrently" on a device with a single processor.

  2. (1 pt) Revisit slides 20-23 of the slide deck Multi-tasking and Deadlock (Week 10). Write an interleaving of the steps of the two programs that would cause both programs to enter their critical sections at the same time.

  3. (2 pts) Recall the lecture slides about the classic problem Dining Philosophers (Week 10, Review and Pipelining).
    1. Describe how a deadlock can occur.
    2. Can you make a modification to the algorithm that would remove the deadlock scenario you found?
    Be specific in your answer, by listing exactly what steps should be taken by each philosopher, in what order.

    The Dining Philosophers is a well-studied problem. You can look it up in a book or an online source, but you need to understand the solution and write it in your own words. Do not forget to cite your source if you have not come up with your solution on your own.

  4. (3 pts) At Moe's Sub Shop, it takes 4 steps to serve a customer: (1) 30 seconds to put a sandwich together, (2) 2 minutes to run it through the (hand-cranked) oven, (3) 1 minute to apply the toppings, and (4) 1 minute to deliver the sandwich and collect payment from the customer. Moe has three workers, and each has their own sandwich station, oven, topping station, and cash register so they can all work in parallel.

    1. If three customers arrive at Moe's at the same time, how long will it take for all of them to be served?

    2. Marge thinks Moe is crazy for investing so much in equipment. Marge's shop has just one sandwich station, one oven, one cash register, and one worker. How long does it take her to serve three customers?

    3. Michael tells Marge she can speed up service by hiring more workers without having to purchase more equipment, using a technique called "pipelining". Marge expands her workforce to four people such that each step is handled by a different person. Now when three customers arrive at her shop, they can get faster service, although not as fast as at Moe's. How long does it take all three to be served? Show your calculation.

  5. (2 pts) In the Blown To Bits reading, you learned how Google handles a search query for the World Wide Web. Describe one way that Google uses concurrency (parallelism) based on your reading. Be specific.