15110 Fall 2012 [Touretzky/Kaynar]

Problem Set 10 - due Friday, November 9 in class

Reading Assignment

Read Chapter 4 of Blown to Bits.

Instructions

• Type or neatly write the answers to the following problems.
• Please STAPLE your homework before you hand it in.
• On the first page of your homework, include your name, andrew ID, lab section (A-N), and the assignment number.
• You must hand in your homework at the start of class on the given due date.

1. (6 pts) Suppose you are hired to automate the Student Council election at a local college. Students will swipe their ID cards to identify themselves as eligible voters and then choose from one of several candidates for Student Council President. Consider the following algorithm:

   while true do

   1. Read the student's ID when they swipe their card.
      
   2. Check the student database to verify that the student hasn't already voted. If they have voted, go back to step A.
      
   3. Wait for the student to press a touch screen to vote for their candidate.
      
   4. Retrieve the current vote count for the candidate they selected from the candidate database, and store it in the variable V.
      
   5. Set V = V + 1.
      
   6. Write the new vote count V for that candidate back to the candidate database.
      
   7. Mark in the student database that this student has voted, so they can't vote again, and set V to nil.

   end

   1. Suppose the polling place has multiple voting machines right next to each other. Describe how a student could exploit a weakness in the above algorithm to vote twice.

   2. Let's assume that there are two candidates. Suppose Tom is the first voter of the day. He goes to the first voting machine and votes for candidate #1. After he leaves, Mary goes to the second voting machine and votes for candidate #2. Using the process/state notation you saw in lecture, we can represent the initial state of the system as 0/0/nil/nil/AA, meaning that each candidate starts out with zero votes, each voting machine has nil as its value of V, and both machines are at step A of the algorithm. Write down the sequence of states the system would go through as Tom votes using the first machine and then Mary votes using the second machine. Note: you do not need to create a complete state table describing every possible path through the state space. Just write a down a legal sequence of states that starts with 0/0/nil/nil/AA and ends with 1/1/nil/nil/AG.

   3. Suppose Bob and Carol simultaneously arrive at the polling place and attempt to vote in lock step. When Bob and Carol show up, one candidate has accumulated 5 votes and the other has 6. Using the process/state notation you saw in lecture, when Bob and Carol go to swipe their ID cards the system would be in state 5/6/nil/nil/AA. Both Bob and Carol intend to vote for candidate #1. Describe a sequence of state transitions, beginning with the state 5/6/nil/nil/AA, that would result in only one of their votes being counted, i.e., the final state would be 6/6/nil/nil/GG instead of the correct 7/6/nil/nil/GG.

   4. Introducing a critical section in the algorithm can make it better behaved. What is a critical section? And what is the smallest set of steps in the above algorithm that should be included in the critical section to prevent votes from being lost?

   5. To be as careful as possible, you decide your algorithm should lock both the candidate database and the student database, to prevent both double voting and under counting. Here is the revised algorithm:

      while true do

      1. Read the student's ID when they swipe their card.
         
      2. Lock the student database, waiting if necessary.
         
      3. Check the student database to verify that the student hasn't already voted. If they have voted, unlock the database and go to step A.
         
      4. Wait for the student to press a touch screen to vote for their candidate.
         
      5. Lock the candidate database, waiting if necessary.
         
      6. Unlock the student database.
         
      7. Retrieve the current vote count for the candidate they selected from the candidate database, and store it in the variable V.
         
      8. Set V = V + 1.
         
      9. Write the new vote count V for that candidate back to the candidate database.
         
      10. Lock the student database, waiting if necessary.
          
      11. Mark in the student database that this student has voted, so they can't vote again, and set V to nil.
      12. Unlock the student database.
          
      13. Unlock the candidate database.

      end

      Because steps G-I are performed with the cndidate database locked, voting machines cannot interfere with each other in a way that causes votes to be under counted. But what about deadlock? Describe a sequence of states beginning with 5/6/nil/nil/AA that will result in deadlock.

   6. Reorder the steps of the above algorithm so that deadlock cannot occur.

   7. Using your modified algorithm from the previous step, suppose a student swipes their card, is presented with a list of candidates to choose from, and then walks away without voting. What will happen when students arrive at other voting machines and try to vote?

   8. Give a revised algorithm that will not hang up other voting machines if a student swipes their card but does not vote.

2. (3 pts) At Moe's Sub Shop, it takes 30 seconds to put a sandwich together, 2 minutes to run it through the (hand-cranked) oven, 1 minute to apply the toppings, and 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 five 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. Her shop has just one sandwich station, one oven, one cash register, and one worker. How long does it take her to serve five 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. Now when five customers arrive at her shop, they can get faster service, although not as fast as at Moe's. How long does it take all five to be served? Show your calculation.

   4. Suppose there were 30 customers needing service. Compare the time to completion for Moe, serial Marge, and pipelined Marge in this situation. Show your calculation.

3. (1 pt) 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.