Chapter 3

Question 1

In OO programming what is an object

Answer 1

container for Data

Question 2

What is an example of a state (set of fields)

Answer 2

a sequence of items in a Queue

Question 3

What is an example of methods

Answer 3

enq + deq

Question 4

What is the safety + liveness properties of an object

Answer 4

Safety: nothing bad happens (correctness). Liveness: something good eventually happens (progress)

Question 5

How to determine if an object’s are behaving correctly?

Answer 5

Pre/post conditions

Question 6

Can concurrent methods overlap?

Answer 6

Yes

Question 7

Should you characterize all possible interactions with concurrent calls?

Answer 7

Yes

Question 8

Principle 3.3.1

Answer 8

Method calls should appear to happen in a one-at-a-time sequential order

Question 9

When is a object quiescenct

Answer 9

when it has no method calls (inactive)

Question 10

Principle 3.3.2

Answer 10

Methods calls separated by a period of quiescence should appear to take effect in real-time order(if methods call is separated by gap of inactivity…)

Question 11

What does 3.3.1 and 3.3.2 form

Answer 11

Quiescent consistency

Question 12

When is a object quiescent consistent

Answer 12

If method calls appear to be in sequential order, method calls take place in real-time order if separated by period of inactivity

Question 13

Is Quiescent consistency compositional?

Answer 13

Yes. If Each object in the system the whole system will be quiescent consistent

Question 14

Principle 3.4.1

Answer 14

Method calls should take effect in program order(order in which a single thread issues method calls)

Question 15

Is method calls by different calls unrelated by program order?

Answer 15

Yes

Question 16

What does 3.3.1 and 3.4.1 form

Answer 16

Sequential consistency

Question 17

When is a object in sequential order?

Answer 17

method calls are in sequential + program order

Question 18

A.enq(x) concurrent with B.enq(Y), then A.deq(y) concurrent with B.deq(x). Construct 2 possible sequential orders

Answer 18

A.enq(x)->B.enq(y)->B.deq(x)->A.deq(y)

B.enq(y)->A.enq(x)->A.deq(y)->B.deq(x) (both are in program order)

Question 19

Is quiescent and sequential consistancy comparable?

Answer 19

no. 1 does not mean the other exists

Question 20

Principle 3.5.1(Linearizability

Answer 20

Each method call should appear to take effect instantly at some moment between invocation and response

Question 21

What is the linearization point?

Answer 21

CS/ single step where the effects of the method call become visible to other methods

Question 22

3 correctness conditions

Answer 22

Quiescent consistency
Sequential consistency
Linearizability

Question 23

When is a method lock free

Answer 23

if some method calls finishes in a finite number of steps

Question 24

When is a method wait free

Answer 24

if it guarantees that every call finishes its execution in a finite number of steps

Question 25

Progress Conditions

Answer 25

Deadlock-free: some thread trying to acquire the lock eventually succeeds.
Starvation-free: every thread trying to acquire the lock eventually succeeds.
Lock-free: some thread calling a method eventually returns (succeeds)
Wait-free: every thread calling a method eventually returns (succeeds)

Question 26

does synchronization usually imply mutual exclusion?

Answer 26

yes

Question 27

Are synchronization events linearizable?

Answer 27

yes. ordered + all threads agree on ordering

Question 28

What are sync events

Answer 28

Locks + sync blocks
Volatile fields
Final fields