Ch. 4 - Synchronization

Question 1

Hardware Parallelism

Answer 1

CPU computing, one or more I/O devices are running at the same time.

Question 2

Pseudo Parallelism

Answer 2

Rapid switching back and forth of the CPU among processes, pretending that those processes run concurrently.

Question 3

What are the properties of cooperating processes?

Answer 3

Processes share a common object
Non-deterministic results
May be irreproducible
Subject to race conditions

Question 4

Why is cooperation between processes desirable?

Answer 4

Allows for resource sharing
Faster execution time
Allows for systems to be constructed in a modular fashion

Question 5

Why do cooperating processes run faster than competing processes?

Answer 5

Jobs can be divided into smaller pieces and executed concurrently (since the processes will synchronize)

Question 6

Race Condition

Answer 6

Situation where two or more processes access shared data concurrently and correctness is not guaranteed due to different results from different orderings of operations.

Question 7

Mutual Exclusion

Answer 7

Ensures that only one process can modify shared data at a time. Other processes cannot modify shared data until the current process finishes

Question 8

Critical Section (CS)

Answer 8

A section of code where only one process may be executing at a given time. This code is executed sequentially.

Question 9

True or False: It does not hurt to have a long critical section as long as the critical section is guaranteed to finish.

Answer 9

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.

Question 10

What fundamental requirements must be met by concurrent processes in order to cooperate correctly and efficiently?

Answer 10

Mutual Exclusion
Progress
Fault Tolerance
No assumptions made about speed or number of processors
Efficiency (short CS, no blocking)

Question 11

Progress (Fundamental Requirement)

Answer 11

A process wishing to enter its CS will eventually do so in finite time.

Question 12

Fault Tolerance (Fundamental Requirement)

Answer 12

Processes failing outside their CS should not interfere with others accessing their own CS

Question 13

Semaphore

Answer 13

Synchronization variable that takes on a non-negative integer with only two atomic operations: P(semaphore), V(semaphore)

Question 14

Why is disabling interrupts a bad solution to preventing a process being interrupted in its critical section?

Answer 14

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.

Question 15

Why is a test and set (TAS) instruction desirable to use to achieve mutual exclusion? Are there any drawback(s)?

Answer 15

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

Question 16

P(semaphore)

Answer 16

while (semaphore) == 0); //wait until semaphore incremented
decrement semaphore

Question 17

V(semaphore)

Answer 17

Increment semaphore

Question 18

What are 3 possible uses for semaphores?

Answer 18

1. Mutual Exclusion (initialize semaphore to 1)
2. Signalling (initialize semaphore to 0)
3. Counting (initialize semaphore to n >= 2)

Question 19

Log-based Recovery

Answer 19

Record transaction to service in log file before the transaction actually happens. Not practical for large databases (huge log file would be the result).

Question 20

Checkpoints

Answer 20

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.

Question 21

What are some properties that make semaphores an attractive implementation of synchronization?

Answer 21

Single Resource Serialization
Can have many different CS’s with different semaphores
Can permit multiple processes into 1 CS if desirable (counting semaphores)

Question 22

What is a drawback of using semaphores?

Answer 22

They are unstructured (i.e. the programmer is responsible for using P and V correctly)

Question 23

Monitor

Answer 23

High-level abstraction that combines and hides:
shared data
operations on the data
synchronization with condition variables

Question 24

Serializability

Answer 24

The outcome of the concurrent execution of atomic transactions is equivalent to the sequential execution of the same transactions in any arbitrary order.

Question 25

Monitor Equivalent to V() (for condition variable x)

Answer 25

x.signal()

Question 26

Monitor Equivalent to P() (for condition variable x)

Answer 26

x.wait()

Question 27

If a transaction is aborted (terminated unsuccessfully), what must occur?

Answer 27

The transaction must be rolled back to its state before the transaction started.