Final Results and Answers

I will put your final exam grade in the final-grade/final-grade.txt file in your handin directory.

Grade Distribution

  50 -  54:   53 54
  55 -  59:   57
  60 -  64:   62 
  65 -  69:   65 69
  70 -  74:   70 71 74
  75 -  79:   76 76 77 78 78
  80 -  84:   81 83 83 
  85 -  89:   88 88 88 89 89 89
  90 -  94:   90 90 91 92 93
  95 - 100:   97 98 100

Final Answers

Part I: True or False

1. False. sem_wait does not always block; it depends on the semaphore value.

2. False. Semaphore is sufficient (for mutex and scheduling)

3. False. An execution can be preempted anytime.

4. True.

5. False. NFS is a stateless server.

6. False. Google can build reliability around cheap machines.

7. False. Computation is partitioned across server machines.

8. False. RAID-0 does not provide any data protection.

9. True.

10. True.

Part II: Synchronization Problems and Threads

1. To ensure only one processor can proceed. (Note: TAS was specifically introduced to handle multi-processors. Without TAS, the code above still works on a uni-processor. Thus in your answer, you need to explicitly mention about processor. Otherwise you do not get a full credit.)

   If while(TAS) is missing, then multiple threads running on multiple processors can proceed, leading to a race condition.

2. To ensure that while a processor is executing inside the lock function, it is not interrupted.

   If it is missing, a deadlock can occur. For more see: [Lec 17, Slide 11].

3. Because it just spin-waits for a while (the thread who is executing inside the lock function on another processor will definitely finish soon -- it just executes less than 10 instructions).

4. full and empty semaphores are scheduling semaphores. We need a semaphore to provide mutual exclusion since the producers and consumers are sharing the buffer.

   If no mutex, then there will be race condition.

5. mutex = 1, full = 0, empty = N [Lec 18, Slide 14].

6. Deadlock. Ex: A consumer comes in, and it will be blocked on the "full" semaphore, but it is holding the "mutex" semaphore.

7. Swap p1 with p2.
   Swap c1 with c2.
   Swap p5 with p6.
   Swap c5 with c6.
   

8. Flexible scheduling, portability, low overhead.

9. Leverage multiprocessors, and inter-leaving execution (especially if there are I/O-bound threads)

10. A thread/context is given an exclusive stack.

    It is important because each thread must have its own stack for its own execution.

    Part III: Distributed Systems and RAID

11. Memory pressure and network load.

12. NFS wins: if read the first byte (or small number of bytes) of large files.
    In this case, AFS will transfer the whole file from server to client, but NFS only transfer one block at a time.
    (I also accept: write few-bytes of large-files, because AFS always synchronize the whole file to the server, while NFS only sends the updated block back to the server).

    AFS wins: for any writes. Because in NFS writes always go to the server periodically (e.g. every 1-3 seconds). But in AFS, writes are kept locally until the file is closed.

13. open() interface must be changed. With call-backs, open() does not need to check if the files in the local memory/disk are valid or not; the client does not need to talk to the server. If the local cache is invalid, the call-backs should notify the client.

    Without call-backs, there is no way to check if the files in the client cache are still consistent with those in the server. Thus, on open(file), the client must talk to the server first in order to check the consistency of the file.

    Some of you answers that read()/write() must be changed. It is already explicitly stated that since the first version of AFS, read() and write() never contact the server. Thus, the answer is either open() or close(). The latter does not need to be changed. So the answer is open().

14. You should use NFS.

    If you use AFS, data is fetched from the server only on opens, and the whole file is stored on the local disk, and the file server cannot be utilized as a file cache. Since the client memory is small, everything will be read from the slow local disk.

    With NFS, if the file is not in local cache, read can go to the server. And since the server's memory is huge, the clients' files might be in the server memory.

    In conclusion, in this scenario, transferring data from the server's memory to the client is much faster than reading the data from the client's disk. (Note: it is a common practice that whenever you have a high-end server, you want to utilize the server's memory to cache client's data).

15. 2T:
    T1: read B3, B4, P1, and P2 in parallel
    (then perform parity computation in memory -- should be very fast)
    T2: write B3', B4', P1', and P2' in parallel
    

16. 4T:
    T1: read B3, B4, and P1 in parallel (can't read P2 because of contention)
    T2: read P2
    (compute new parity for P1' and P2')
    T3: write P1' and B3' in parallel
    T4: write P2' and B4' in parallel