Ch. 4 - Synchronization Flashcards
Hardware Parallelism
CPU computing, one or more I/O devices are running at the same time.
Pseudo Parallelism
Rapid switching back and forth of the CPU among processes, pretending that those processes run concurrently.
What are the properties of cooperating processes?
Processes share a common object
Non-deterministic results
May be irreproducible
Subject to race conditions
Why is cooperation between processes desirable?
Allows for resource sharing
Faster execution time
Allows for systems to be constructed in a modular fashion
Why do cooperating processes run faster than competing processes?
Jobs can be divided into smaller pieces and executed concurrently (since the processes will synchronize)
Race Condition
Situation where two or more processes access shared data concurrently and correctness is not guaranteed due to different results from different orderings of operations.
Mutual Exclusion
Ensures that only one process can modify shared data at a time. Other processes cannot modify shared data until the current process finishes
Critical Section (CS)
A section of code where only one process may be executing at a given time. This code is executed sequentially.
True or False: It does not hurt to have a long critical section as long as the critical section is guaranteed to finish.
False. A critical section should be as short as possible to minimize runtime of the program. Reaching the end of a critical section cannot be guaranteed due to interrupts.
What fundamental requirements must be met by concurrent processes in order to cooperate correctly and efficiently?
Mutual Exclusion
Progress
Fault Tolerance
No assumptions made about speed or number of processors
Efficiency (short CS, no blocking)
Progress (Fundamental Requirement)
A process wishing to enter its CS will eventually do so in finite time.
Fault Tolerance (Fundamental Requirement)
Processes failing outside their CS should not interfere with others accessing their own CS
Semaphore
Synchronization variable that takes on a non-negative integer with only two atomic operations: P(semaphore), V(semaphore)
Why is disabling interrupts a bad solution to preventing a process being interrupted in its critical section?
Users cannot disable interrupts (privileged instruction) and the CPU cannot service mission critical tasks if interrupts are disabled. This leads to a system that is unreliable and lower system performance.
Why is a test and set (TAS) instruction desirable to use to achieve mutual exclusion? Are there any drawback(s)?
Since TAS can read, write, and store a word atomically, it is not interruptible.
Only 1 guard variable is needed per critical section
Works for n processes
Yes, a drawback is that there is busy waiting
P(semaphore)
while (semaphore) == 0); //wait until semaphore incremented
decrement semaphore
V(semaphore)
Increment semaphore
What are 3 possible uses for semaphores?
- Mutual Exclusion (initialize semaphore to 1)
- Signalling (initialize semaphore to 0)
- Counting (initialize semaphore to n >= 2)
Log-based Recovery
Record transaction to service in log file before the transaction actually happens. Not practical for large databases (huge log file would be the result).
Checkpoints
Save the state before the transaction. In the case of a crash, restore the state before the transaction. However, this adds extra overhead if transaction is complex.
What are some properties that make semaphores an attractive implementation of synchronization?
Single Resource Serialization
Can have many different CS’s with different semaphores
Can permit multiple processes into 1 CS if desirable (counting semaphores)
What is a drawback of using semaphores?
They are unstructured (i.e. the programmer is responsible for using P and V correctly)
Monitor
High-level abstraction that combines and hides:
shared data
operations on the data
synchronization with condition variables
Serializability
The outcome of the concurrent execution of atomic transactions is equivalent to the sequential execution of the same transactions in any arbitrary order.
Monitor Equivalent to V() (for condition variable x)
x.signal()
Monitor Equivalent to P() (for condition variable x)
x.wait()
If a transaction is aborted (terminated unsuccessfully), what must occur?
The transaction must be rolled back to its state before the transaction started.
