====== Questions ======

These relatively simple questions -- mostly true/false or multiple-choice -- are meant to help you prepare for the final.  Unless otherwise stated, the questions concern typical operating systems for PC- and server-class hardware, like the ones we've focused on in class.  Multiple-choice questions are "circle all that apply".

These preparation questions do not cover all topics that will be on the final.  We hope to update them as time goes on.

[[answers|Answers]] to these questions

===== Group A =====

[[answers#Group A|Answers for this group]]

**A1.** T/F: "Propagation of effects" refers to the property that it's easy to
change one part of a system without changing any of the other parts.

**A2.** Which of these is not one of the characteristics that complicate the
construction of large systems?  A. Emergent properties; B. Trade-offs;
C. Modularity; D. Incommensurate scaling; E. Propagation of effects.

**A3.** T/F: "Modules" and "subsystems" are near synonyms.

**A4.** Of the three advantages below, which is the most common advantage of good system modularity?
A. Better performance; B. Fewer deadlocks; C. Stable interfaces control
propagation of effects.

**A5.** Which of these does //not// refer to crossing the boundary between application and kernel?  A. Protected control transfer; B. Inter-procedure call; C. System call; D. Remote procedure call.

**A6.** T/F: Function calls are an example of modularity.

**A7.** T/F: Function calls are an example of soft modularity, where the modularity is by contract but the contract is not enforced.

**A8.** T/F: Function calls are an example of hard modularity.

**A9.** Which of these possible function behaviors (i.e., things that a function might do) help demonstrate whether function call modularity is soft or hard?  A. Infinite loop; B. Return to caller; C. Change global variables as allowed by function specification; D. Buffer overflow.

**A10-A16.** You are given an application whose main loop reads N characters from a file, one character at a time, by calling a function called ''readc'' N times.  This application is then changed to use buffered I/O for reads (it didn't before).  The application's main loop is //not// changed, however.

//A10.// T/F: The buffered I/O version will make fewer system calls than the other. \\
//A11.// T/F: The buffered I/O version will make fewer function calls than the other. \\
//A12.// T/F: The buffered I/O version improves read performance via speculation. \\
//A13.// T/F: The buffered I/O version improves read performance via prefetching. \\
//A14.// T/F: The buffered I/O version improves read performance via batching. \\
//A15.// T/F: The buffered I/O version improves read performance via dallying. \\
//A16.// T/F: The buffered I/O version reduces the number of times the data must be copied between the disk and the application's main loop.

**A17-A23.** Now, you are given an application whose main loop **writes** N characters from a file, one character at a time, by calling a function called ''writec'' N times.  This application is changed to use buffered I/O for **writes** (it didn't before).  The application's main loop is again not changed.

//A17.// T/F: The buffered I/O version will make fewer system calls than the other. \\
//A18.// T/F: The buffered I/O version will make fewer function calls than the other. \\
//A19.// T/F: The buffered I/O version improves write performance via speculation. \\
//A20.// T/F: The buffered I/O version improves write performance via prefetching. \\
//A21.// T/F: The buffered I/O version improves write performance via batching. \\
//A22.// T/F: The buffered I/O version improves write performance via dallying. \\
//A23.// T/F: The buffered I/O version reduces the number of times the data must be copied between the application's main loop and the disk.

**A24.** Which of the following are not fundamental parts of the Von Neumann computer model? A. Transition function; B. Function calls; C. Arithmetic-logical unit (ALU); D. Primary memory.

**A25.** T/F: Processes run inside the kernel.

**A26.** T/F: Any process can access any other process's memory by default.

**A27.** T/F: System calls are more expensive than regular function calls.

**A28.** T/F: When an application wants to contact the kernel, it executes a normal instruction like ''jmp'' that jumps directly to the relevant code in the kernel.  The kernel returns to the application just as a function normally returns to its caller.

**A29.** T/F: The heap is an example of an I/O device abstraction.

**A30.** Which of the following instructions should be //protected//, i.e., can execute only when the processor is running in its most privileged mode (CPL 0)?  A. HSC; B. INT (software interrupt); C. ADD; D. JMP; E. INB (contact I/O device).

**A31.** T/F: The kernel communicates with applications by making system calls.

**A32.** Which are the typical processor privilege levels when user applications and the kernel are running?  A. Kernel CPL 0, application CPL 0; B. kernel CPL 3, application CPL 0; C. kernel CPL 0, application CPL 3; D. kernel CPL 3, application CPL 3.

===== Group B =====

[[answers#group b|Answers for this group]]

Match each word with its definition.

| A. Batching  | 1. A performance optimization strategy that delays processing the current request in case there's a later opportunity to handle several requests simultaneously.  |
| B. Caching  | 2. A performance optimization strategy that handles several requests at once in order to reduce the total amount of overhead.  |
| C. Context switch  | 3. A performance optimization strategy that keeps the data needed for a request in a faster memory in case it is needed later.  |
| D. Current protection level (CPL)  | 4. A performance optimization strategy that loads data (for example, from disk) that hasn't yet been requested.  |
| E. Dallying  | 5. A performance optimization strategy that operates in advance of the current request, in the hope that some of that work will be useful.  |
| F. Isolation  | 6. A processor hardware setting that determines the privileges available to the currently running code -- for example, whether that code can run special privileged instructions.  |
| G. Modularity  | 7. A property of subsystems that neither subsystem can affect the other, except perhaps at explicitly specified interaction points.  |
| H. Prefetching  | 8. A virtual computer abstraction provided by the operating system for running application code.  |
| I. Process  | 9. The degree to which and manner in which a system is broken into pieces.  |
| J. Speculation  | 10. The kernel-mediated operation of switching a processor from running one process's code to running another process's code.  |
| K. Virtualization  | 11. A design where one object simulates another object's interface, providing roughly the same behavior.  |

===== Group C =====

[[answers#group c|Answers for this group]]

**C1.** Match the system call to its function, expressed in terms of fundamental system abstractions.

| A. ''execvp''  | 1. New bounded buffer  |
| B. ''fork''    | 2. New code for interpreter  |
| C. ''open''    | 3. New I/O device      |
| D. ''pipe''    | 4. New virtual computer  |

**C2.** T/F: Reading from or writing to a pipe can sometimes block.

**C3.** T/F: The ''dup2'' system call only works for pipes.

**C4.** T/F: If there were enough file descriptors, then all programs would run exactly the same even if they never called ''close''.  That is, ''close'' is useful only for garbage collection.

**C5.** Which are elements of a typical process descriptor?  A. Process state (blocked/runnable); B. Address space; C. Disk driver; D. File descriptor table.

**C6.** T/F: The kernel always runs all existing processes in round-robin order.

**C7.** Which system calls can directly affect another running process (i.e., not through virtual I/O devices)?  A. ''open''; B. ''read''; C. ''pipe''; D. ''write''; E. ''kill''; F. ''signal''; G. ''waitpid''.

**C8.** T/F: Disk files provide applications with a stream abstraction.

**C9.** T/F: Zombie processes are called "zombies" because they live forever and cannot be killed.

**C10.** T/F: If processes had no exit status, and process IDs were never reused, then there would be no need for zombie processes.

**C11.** Which system calls are required to set up a pipe, like in the shell?  A. ''open''; B. ''close''; C. ''dup2''; D. ''pipe''.

**C12.** Which system calls are required to set up input redirection, like in the shell?  A. ''open''; B. ''close''; C. ''dup2''; D. ''pipe''.

**C13.** T/F: The kernel attempts to make most system calls appear to happen indivisibly/atomically.

**C14.** T/F: Buffered I/O functions like ''printf'' make as many system calls as there are calls to the functions.

**C15.** T/F: The bounded buffer is an example solution to a producer/consumer synchronization problem.

**C16.** T/F: Timer interrupts are generally required for a kernel to correctly isolate processes.

===== Group D =====

[[answers#group d|Answers for this group]]

**D1.** Match the operation name with the corresponding synchronization object.

| A. ''acquire''        | 1. condition variable   |
| B. ''acquire_read''   | 2. read/write lock      |
| C. ''cond_wait''      | 3. semaphore            |
| D. ''verhogen''/''V'' | 4. spinlock             |

**D2.** Which synchronization object is implemented with a polling strategy, as opposed to a blocking strategy?  A. Semaphore; B. Spinlock; C. Condition variable.

**D3.** Arrange these lines of code in order to build a correct implementation of the ''compare_and_swap'' atomic operation.

<code>
          int compare_and_swap(uint32_t *addr, uint32_t oldval, uint32_t newval) {
Line A:       *addr = newval;
Line B:       } else {
Line C:       if (*addr == oldval) {
Line D:       return 0;
Line E:       return 1;
Line F:       }
          }
</code>

**D4.** Which are required conditions for deadlock? A. Mutual exclusion; B. Circular wait; C. Hold and wait; D. Race condition; E. No preemption.

**D5.** T/F: Lock contention is most common when a system has many more locks than processes.

**D6.** T/F: The key to finding a critical section is to find writes to shared state.

**D7.** Match the waits-for graph with the property it most strongly implies.

| A. {{waitsfor-y.png|waitsfor-y.png}}  | 1. Lock contention  |
| B. {{waitsfor-x.png|waitsfor-x.png}}  | 2. Deadlock   |
| C. {{waitsfor-z.png|waitsfor-z.png}}  | 3. None of the above  |

===== Group E =====

**E1.** T/F: Access control lists are more useful for authentication than for authorization.

**E2.** T/F: Encryption is more useful for authentication than for authorization.

**E3.** T/F: Cryptographic hash functions are more useful for authentication than for authorization.

**E4.** T/F: Cryptographic signatures are more useful for authentication than for authorization.

**E5.** T/F: In public key cryptosystems, K = K<sup>-1</sup>.

**E6.** T/F: Public key cryptosystems are intended to be arranged so that anyone can compute E(M, K) once they know M.

**E7.** T/F: Secret key cryptosystems are intended to be arranged so that anyone can compute E(M, K) once they know M.

**E8.** T/F: Say that M = M1||M2, where the || operation denotes concatenation.  Then given a cryptographic hash function H, M1, and H(M1||M2), it is easy to find M2.

**E9.** T/F: If a system authorizes any action made by anyone, then authentication is not really relevant in that system.

**E10.** T/F: Nonces help ensure freshness in cryptographic protocols, where freshness is the property of being replay-free.

**E11.** A Unix user ID is an instance of what category?  A. Access control list, B. Principal, C. Private key, D. Authorization function.