QMCS 360 Class Notes # 8	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

Diagrams of processes/threads in Windows and Unixes

Concurrency

Interrupts, multiprogramming, multiple processors yield the "concurrency problem"

Example from the book: p. 204-205

The basic problem is the RACE CONDITION

The results of the program are DIFFERENT depending on what happens during execution.

This is bad - a computer should always yield the same results when given the same input.

Arises in several places

Multiple applications sharing resources

Single application with multiple threads

Operating System itself

Processor scheduling - the queues and control blocks

Memory - the queues and control blocks

Files - buffered copies and on-disk copies

I/O devices - queues and control blocks

How do we solve it? One answer: MUTUAL EXCLUSION

Need a mechanism so that only one process/processor at a time accesses a shared resource, usually an area of RAM

Organize software so that accesses to shared resources occur in specific areas called CRITICAL SECTIONs

Enforce mutual exclusion while in the critical section

Problems

Deadlock - two processes are waiting - each for a resource owned by the other ("deadly embrace")

Starvation - a process waits for a resource that it never gets

Requirements for mutual exclusion to "work"

Must always be enforced - no critical section should execute without it

A process that halts inside a critical section must do so without interfereing with other processes (ie never if it has a shared resource)

A process that needs a critical section should never be stuck forever - no deadlock or starvation

If no process is in a critical section, a process entering one should be able to enter it without delay

No assumptions are made about speed of processes or processors or number of available processors

A process remains inside a critical section for only a finite amount of time

Implementing critical sections

Disable interrupts

Advantages

Simple and obvious

Disadvantages

Slows down the whole system - delays responses to interrupts

Test and Set instruction

Tests and changes a value in RAM in one, uninterruptable instruction, and sets the condition code according to the initial value

Advantages

Fast execution, simple

Somewhat practical in multiprocessor environments

Disadvantages

Process that awaits a change in the variable will "spin wait" which hogs the processor and doesn't let the other (critical section) process finish up

Deadlock and starvation are possible (p. 215)

Semaphore - an OS-level control that uses the scheduler

2 operations: Wait (or "test" or "P") and Signal (or "increment" or "V")

Works on a variable with a queue of processes

Binary example:

Wait function - used at the start of a critical section (more or less)

disable interrupts

if value = 1, then change to 0 and proceed

else, queue this process to on this semaphore's queue to wait for rescheduling

enable interrupts

Signal function - used at the end of the critical section

disable interrupts

if queue of processes is empty, set value to 1

else, take a process from the semaphore queue and make it ready to run

enable interrupts

The "classic" implementation keeps a numeric variable with the (negative) number of processes waiting on the queue for the semaphore.

Producer/Consumer Problem

Basic problem: share a buffer while one process sticks stuff in and another pulls it out

Theoretical case: infinite buffer (no wrap around needed)

Practical case: bounded buffer (wrap around)