Notes on Chapter 5

Notes on Chapter 5

_1. Review 3 difficulties - p. 199

_2. Discuss “Simple Example”

Uniprocessor - p. 200

Multiprocessor - p. 201

Solution - p. 202 {control access to shared resources}

_3. Concurrency concerns - p. 202

Principle: Results need to be independent of speeds of processes

_4. Process interaction

Unaware - poss. competition

Main discussion - pp. 204-5

Indirectly aware - cooperate & share

Disc. - pp. 205-6

Problems:

2 modes of access {R,W}; only W needs M.E.

New requirement - data coherence {see p. 206}

Directly aware - cooperate & share & communicate

Disc. - pp. 206-7

Problems:

Deadlock & starvation (see p. 207), not M.E.

_5. Poss. problems

Violation of mutual exclusion

Deadlock

Starvation

Loss of data coherence

_6. Summary - Table 5.1, p. 203

_7. Mutual exclusion {2 levels}

Simple - obviously 2 processes cannot both use some resources

simultaneously, e.g., processor

More subtle

Critical resource

Critical section of code - the portion of code in which a process

accesses a critical resource

Rule: Only one process at a time should be allowed into its critical

section

Enforcement of M.E. can lead to:

Deadlock

Starvation

O.S. involved bec. it allocates resources

Process must have method of signaling need for M.E.

Abstract example - p. 205

Requirements: See p. 207

_8. Critical Section

Can be used to solve competition - p. 205

Can be used to solve cooperation - p. 206

_9. Software solutions to ME

1st Attempt -

Guarantees ME

Busy waiting (BW)

Lock step synchronization (LSS)

If process fails, other process is locked out

2nd Attempt

Does not guarantee ME

bec. not independent of relative speeds

No LSS

**If process fails outside CS - OK

inside CS - other process is locked out

** Note: In this and all other solutions, this is not precisely,

literally true. If it fails immediately before resetting

the flag, technically it is outside its CS, but still blocks

the other process.

3rd Attempt

No LSS

If process fails outside CS - OK

inside CS - other process is locked out

Deadlock (due to mutual rudeness)

4th Attempt

Busy work waiting (BWW)

No LSS

If process fails outside CS - OK

inside CS - other process is locked out

Livelock (due to excessive mutual courtesy)

Dekker’s Algorithm

No LSS

No DL or LL

If process fails outside CS - OK

inside CS - other process is locked out

Proof of Correctness:

ME -

There are 3 cases to consider:

(1) P0 “wants to” and attempts to enter before P1.

(2) P1 “wants to” and attempts to enter before P0.

(3) In some sense, both P0 and P1 “want to” and attempts to enter at the same time.

Case 1:

P0 sets flag(0) to T. Continues. Finds flag(1) = F, exits while loop and immediately enters CS.

P1, when it tries to enter, finds flag(0) = T and is stuck in the outer while loop until P0 leaves CS.

Therefore, ME is preserved.

Case 2:

Exactly the same as Case 1 with roles of P0 & P1 reversed.

Case 3:

Both P0 and P1 set their respective flags. This forces both of them into their outer while loop. Both execute their IF statement.

At this point turn must be either 0 or 1. Spo turn = 0. P1 sets flag(1) to F and then is forced into its inner while loop.

This allows P0 to enter CS. But P1 must remain in the inner while loop until P0 exits CS and then sets turn = 1, releasing P1 from the inner while loop.

Therefore, ME is preserved.

If turn = 1, then we have a similar situation with the roles of P0 and P1 reversed.

No DL -

For deadlock to occur, both P0 & P1 must be “caught” somewhere in their code. The only places this can happen are the outer and the inner while loops.

Therfore, there are 4 cases to consider:

(1) outer - outer {I.e., both P0 & P1 are caught in their outer while loops}

(2) outer - inner

(3) inner - outer

(4) inner - inner

Case 1: {outer - outer}

The outer loop consists of a single If statement. To remain in the outer portion of the loop the IF condition must be false for both P0 & P1. But this implies that turn <> 0 & turn <> 1. But that is impossible. So, Case 1 cannot occur.

Case 2: {outer - inner}

Before P1 enters the inner loop, it sets flag(1) to F, releasing P0 from the outer loop. So, Case 2 cannot occur.

Case 3: {inner - outer}

The same as Case2 with the roles of P0 and P1 reversed.

Case 4: {inner - inner}

For P0 to enter its inner loop turn must be 1. For P1 to enter its inner loop turn must be 0. But turn cannot be both 0 and 1. So, Case 4 cannot occur.

No Starvation -

For P0 to be starved P1 must enter CS at least twice while P0 is attempting to enter.

Spo P1 enters CS once while P0 is attempting to enter. As P1 leaves CS it sets turn to 0.

At this point, since P0 is attempting to enter, either {1} flag(0) is T or else {2} P0 reset flag(0) to F and is in its inner loop. If {2} is the case, then P0 found turn to be 0 and reset flag(0) to T. So, in either case, flag(0) is T.

As P1 attempts to enter, it finds flag(0) = T and is caught by the condition of its outer loop. Since turn is now 0, the IF condition succeeds, it resets flag(1) to F and is forced into its inner loop. This allows P0 to proceed.

So, P0 cannot be starved. And by reversing the roles of P0 and P1 in the above, we find that P1 also cannot be starved.

Peterson’s Algorithm

No LSS

No DL or LL

If process fails outside CS - OK

inside CS - other process is locked out

Proof of Correctness:

See p. 212

Exercise:

Describe how a process failing inside its CS can lock out another process from its CS.

Answer: When P0 enters CS, flag(0) = T. If it fails inside CS, flag(0) remains T.

P1 comes along, sets turn to 0. Now the compound condition of the While loop is met: flag(0) = T && turn = 0. P1 is caught in its loop.

_10. Hardware approaches to ME

Disable Interrupts:

For uniprocessor, ME is guaranteed, but at a high price.

For multiprocessor, ME is not guaranteed.

Special Machine Instructions:

Test & Set

Exchange

Instructions are atomic, i.e., cannot be interrupted

See pp. 214-216

Dis/Advantages - p. 216

_11. OS & programming language approaches:

semaphores

monitors

message passing

_12. Semaphores

3 semaphore operations:

initialize

wait(s) {P = proberen}

signal(s) {V = verhogen}

Result of search for "verhogen":

verhogen

1. increase, raise

a. wait & signal are atomic

b. counting vs. binary semaphores

c. strong vs. weak semaphores

d. Example - pp. 218-219

e. Mutual exclusion via semaphores - pp. 220-221

f. s.count >= 0

s.count < 0

g. Disadvantage: may be difficult to produce a correct program; not easy to

see overall effect.

_13. Producer/Consumer Problem

a. Description (why only one consumer? See p. 248 top)

b. Infinite buffer example - p. 222

c. Incorrect solution - p. 223 {example p. 224}

d. Correct solution - p. 225

e. Counting semaphore solution - p.226

f. Effect of programming errors - bottom p. 225 {deadlock}

g. Finite buffer problem (pp. 226-7) & solution (p. 228)

_14. Implementation of Semaphores

a. Test & Set

b. Disabling interrupts

_15. Monitors

a. Programming language construct

b. Equivalent functionality of semaphores; easier to control

c. Software module: 1 or more procedures; init sequence; local data

d. Chief characteristics

- local data accessible only via monitor’s procedures

- process enters monitor only by invoking one of its procs.

- only 1 process may execute in monitor at a time

This allows ME of data & resources via data (p. 235)

e. Can be implemented as object with special characteristics

f. Supports synchronization by way of condition vbls.

Operations:

cwait( c ) - suspend execution on condition c

can be used by process to temporarily suspend itself (p. 237)

csignal( c ) - resume execution

can be used by process to alert others of changed condition

g. Bounded buffer example - p. 238

h. Difference betw. Semaphore & monitor

- semaphore: both ME & synch. are programmer’s responsibility

- monitor: provides ME; synch. is programmer’s responsibility

i. Suspend or not after csignal? - p. 237

j. Errors possible;

e.g., omit csignal in bounded buffer => waiting processes hung up.

k. Hoare requires that if there is a process in the condition queue

when signal occurs, process issuing csignal must exit or be suspended

_15. Monitors w/ Notify & Broadcast

a. Two drawbacks to Hoare’s requirement

- if process is not finished its work - 2 additional process

switches are required

- process scheduling must be absolutely reliable (p. 239)

b. Lampson & Redell

- csignal replaced by cnotify (& process may continue executing)

- waiting process must recheck condition

- in code if statements are replaced by while stmts.

See solution, p. 240

c. Possible to associate watchdog timer with each condition

- prevents starvation in case other process fails before notifying

d. Possible now to add a cbroadcast primitive; useful in these cases:

- producers & consumers work with variable length items

- process not sure who should be reactivated (p. 240)

e. Advantages

- not as prone to error; e.g., incorrect notify or broadcast does

not cause error

- more modular; small change in one process does not require

corresponding changes to many other processes

_17. Message Passing

a. For processes to interact, need:

synchronization

communication

b. Message passing does both AND works in a distributed envmt.

c. Primitives:

send (destination, message)

receive(source, message)

d. Synchronization

Blocking send, blocking receive

rendezvous

allows for tight synchronization

Nonblocking send, blocking receive

receiver is blocked until requested message arrives

probably the most useful combination

Disadv:

if error, process could repeatedly generate messages

places burden on programmer to determine if message was

received

Nonblocking send, nonblocking receive

neither party is required to wait

Blocking receive can lead to process being blocked indefinitely

if message is lost or sender fails.

e. Addressing

Direct

Send specifies receiver

Receive explicitly or implicitly designates sender

Indirect

Message sent to shared data structure - mailbox

Adv. - greater flexibility

Relationships can be 1-1, many-1, 1-many, many-many

Association of process to mailbox:

Static

Dynamic

Ownership of mailbox

sender or creating process or O.S.

f. Mutual Exclusion

Assume nonblocking send, blocking receive

Mailbox mutex, initialized with null content message

Message functions as token passed from process to process

Fig. 5.26, p. 246

To enter CS - receive(mutex,message)

When leaving CS - send(mutex, message)

See assumptions, p. 247

Fig. 5.27, p. 247

Q: Why mailboxes?

A: To control producing & consuming

Q: Why for loop sending to mayproduce mailbox?

A: To set max items produced to size of bounded buffer.

Q: For how many producers & consumers will it work?

A: Any number.

_18. Readers/Writers

a. Q: What are the 3 conditions that must be satisfied in classic

readers/writers problem? {A: p. 248}

b. Q: Why does general solution to ME w/ CS not work for R/W?

A: p. 248

c. Q: Is P/C simply special case of R/W? Why or why not?

A: p. 249

d. Semaphore solution, Readers priority - p. 249

Q: What prevents reader from reading while writer is writing?

A: Reader enters immediately if other readers are reading;

Otherwise, reader waits on wsem. If writer is writing

wsem is “unavailable”.

Q: What prevents writer from writing while another writer is

writing?

A: Writer immediately waits on wsem.

Q: What prevents writer from writing while reader is reading?

A: First reader waits on wsem, last reader to leave signals wsem.

Therefore, if wsem is “available”, then no reader is reading.

Q: What is the purpose of the semaphore x? What could happen if

it were omitted from the code?

A: To ensure proper updating of readcount. Without it, 2

readers may try to update it at the same time, giving it an

erroneous value.

Q: If 5 readers are waiting while writer is writing, “where” are

they waiting?

A: 1 is waiting on wsem; the others are waiting on x.

Otherwise, reader waits on wsem. If writer is writing

wsem is unavailable.

Q: What obvious problem does this solution create?

A: Data can become “out of date”, as writers are starved.

e. Semaphore solution, writers priority - p. 251

Q: Produce a scenario which illustrates the need for sem. z.

A: Writer arrives =>

y -> 0; wc -> 1; rsem -> 0; y -> 1; wsem -> 0

writes

Readers arrive =>

rsem -> 0; x -> 0; rc -> 1; wait(wsem)

5 readers arrive =>

wait on rsem

Writer arrives =>

waits on rsem

Queue of rsem is now: W-R-R-R-R-R

Now, strong semaphore discipline stipulates that processes

are unblocked in FIFO order. But, for writers to have

priority, waiting writers must be unblocked before

waiting readers.

Q: What O.S. service would eliminate the need for sem. z?

A: Prioritized semaphore queues.

Q: For which would you rather write a proof of

correctness: Fig. 5.29 or Fig. 5.30?

A: A rhetorical question.

Q: What is the initial value of count?

A: 100

Q: When is the value of count 100?

A: Initially, and as long as there are no requests to read or write.

Q: How can we tell how many readers are reading?

A: If count > 0, then the number of readers is 100 - count.

If count = 0, then there are no readers and there is at least

one write request.

If count < 0, then there are readers and there is at least one

write request. The number of readers is -count.

Q: How can we tell how many write requests there are?

A: We can’t. We can only tell whether or not there are ANY

write requests.

Q: How can we tell if there is an outstanding write request?

A: If count is either 0 or < 0.

Q: In the controller’s code at the point “if (!empty (finished)), from whom are the “finished” messages received?

A: From readers only. The finished message is received from

the one and only one writer at the point where count = 0.

Q: Which synchronization discipline is used in this solution?

A: Nonblocking send, blocking receive.

Both readers and writers send requests, but are not yet blocked. But, as they follow up the request with a receive, if no message is sent back, they are blocked.

If it were a nonblocking receive, for example, then the controller would reset count to 100 before receiving a finished request from the writer. Then it would go on and start sending “OK” messages to waiting readers.