QMCS 360 Class Notes # 9	Dr. Rick Smith Quantitative Methods and Computer Science
Dr. Smith Home | Research | Classes | Blackboard | Cryptosmith | QMCS Home | UST A-Z | UST Home last update: Tuesday, October 11, 2005

Collect Homework

Next Homework: Oops, I'm asking for the Review Questions, not the Problems

A comment on "operating environment"

It's a way of thinking about what your program can and cannot od

In the OS world, it includes the notion of kernel vs user mode

In the device driver world, it includes the notion of interrupt status and any related process restrictions - does an interrupt run as a process or in some weird world containing nothing but CPU registers, the I/O registers, and maybe some RAM? - can they read files, for instance?

Concurrency also affects your operating environment

What variables are safe to touch? 

What do you have locked, and what is accessible by other processes?

Are you the only process guaranteed to run this chunk of code?

What other procedures, methods, etc., can you safely run?

A comment on Sections 5.2 thru 5.4

They are illustrating the evolution of concurrency control from a cumbersome mess to a fairly clear and efficient mechanism.

Historical progression

Getting it to work at all - figuring out how to lock variables

Realizing the integral role of process scheduling

The WAIT instruction on the PDP-11 - never worked!

Dijkstra's semaphores integrated concurrency checking with scheduling

BUT they were hard to integrate into programs

Tony Hoare's monitor concept - better, but ...

Redefined Wait and Signal, and stuck them in a safer, cleaner operating environment

caused unnecessary process switching if the signalling process is still doing stuff in the monitor environment

Also required special-case scheduling of the signalled process, or there was a risk of concurrency errors

Lampson and Redell

Monitor with Wait and Notify (replaced Signal)

Monitors

Example from Java (Adam?) - type of "module" (object, collection of procedures, ...) that processes must execute one at a time.

There's an entry queue

If a process is executing any of the module's procedures or methods, then all other processes are queued to await its completion

Once one process exits, the waiting ones can get their chance.

Wait semantics

Argument: a "Condition:

Like a binary semaphore: a Boolean and a queue

Always CLEARS the Boolean, then queues to wait for it to be SET

Notify semantics

Argument: a "Condition" like in Wait

Simply SETS the Boolean and signals the scheduler that the next process on the queue may run.

The notifying process does NOT itself get de-scheduled, since we want it to exit the monitor BEFORE rescheduling occurs.

Not enough for efficiency - you end up with busy/waits

Do a version of 5.16 without wait/signal - busy-wait the process in the outer loop

Next, do a version using 5.17

Message Passing and IPC

Synchronization

Blocking Send, Blocking Receive

Also called "rendezvous" - used in Ada

If only 2 processes involved, we don't have much of a queueing or storage management issue

We can get around busy-wait problems with kernel threads

Nonblocking Send, Blocking Receive

Supports user level threads

Lets sender generate a bunch of output without suspending

Problem - flow control

Sender needs a "protocol" to know when its output has been processed - a possible synchronization problem

"Natural" for receiving process if it's essentially a service provider

Nonblocking Send, Nonblocking Receive

Supports user level thread environment

Addressing

Direct addressing

Sender and receiver are always explicitly identified

Indirect addressing

Use a separate queue or "mailbox" 

Mailbox may be handled different ways 1-1, 1-many, many-many

Queueing Policy

FIFO

Priority