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)