-
Three central themes of OS design
- Multiprogramming
- Multiprocessing
- Distributed processing
-
Three contexts in which concurrency arises
- Multiple applications
- Structured applications
- Operating system structure
-
Atomic operation
- A function, or sequence of instructions that is indivisible
- Must execute entirely, or not at all
-
Critical section
- Section of code requiring access to shared resources
- Must not be executed while another process is inside it
-
Deadlock
When two or more processes are unable to complete, because they are waiting for the other to finish
-
Livelock
- When two or more processes continually change states in response to the other
- No useful work is done
-
Mutual exclusion
Requirement that when a process is in a critical section, no other processes are in the critical section
-
Race condition
- Multiple threads reading/writing to a shared resource
- Final outcome depends on the relative timing of execution (of the processes)
-
Starvation
When a runnable (ready) process is continually overlooked by the scheduler
-
Software approaches to mutual exclusion (algorithm names)
- Dekker's algorithm
- Petersons's algorithm
-
Three difficulties with concurrency/shared resources
- Race conditions can arise
- Hard to prevent deadlock
- Programming errors are hard to locate
-
Four OS design and management issues caused by concurrency
- Difficulties tracking progress
- Difficulties handling allocation and deallocation of resources
- Difficulties dealing with data and physical resource protection
- Race conditions occur if process function and result must be independent of relative speeds
-
Resources that might be accessed by multiple processes
- Processor time
- Memory
- Files
- I/O Devices
-
Three types of process interaction
- Processes are unaware of eachother
- Processes are indirectly aware of eachother (via a shared resource)
- Processes are directly aware of eachother
-
How processes that are unaware of eachother interact
Competition for shared resources
-
How processes that are indirectly aware of eachother interact
Cooperation, via shared resources
-
How processes that are directly aware of eachother interact
Direct communication
-
Influence processes that are unaware of eachother can have on eachother
- Results of one process independent of the action of the others
- Timing of the process may be affected
-
Influence processes that are aware of eachother (directly or indirectly) can have on eachother
- Results of one process may depend on informaiton obtained from the other(s)
- Timing of the process may be affected
-
Control problems associated with processes that are unaware of eachother
- Mutual exclusion
- Deadlock (renewable resource)
- Starvation
-
Control problems associated with processes are indirectly aware of eachother
- Mutual exclusion
- Deadlock (renewable resource)
- Starvation
-
Control problems associated with processes that are directly aware of eachother
- Deadlock (consumable resource)
- Starvation
-
Three types of process interactions
- Competition
- Cooperation
- Direct communication
-
Six requirements for mutual exclusion
- Mutual exclusion must be enforced
- Halts in non-critical sections mustn't affect other processes
- No possibility of deadlock or starvation
- If a critical section is free, a process trying to use it should be allowed to without delay
- No assumptions made about process speeds or # of processors
- Finite time limit for processes to be in critical sections
-
Hardware approaches to mutual exclusion
- Interrupt disabling
- Special machine instructions
-
Three levels mutual exclusion can be implemented
- Program level
- OS level
- Hardware level
-
Two machine instructions for supporting mutual exclusion
- Compare and swap instruction
- Exchange instruction
-
Pros of machine instructions for supporting mutual exclusion
- Applicable to any number of processes
- Simple and easy to verify
- Can support multiple critical sections
-
Cons of machine instructions for supporting mutual exclusion
- Uses busy (or spin) waiting
- Starvation can occur
- Deadlock can occur
-
Semaphore
Integer used for signaling purposes
-
Mutex
A sempahore, but must be unlocked by the process that locked it
-
Binary semaphore
A sempahore that can only haves the values 0 or 1
-
Condition variable
Data type that is used to block a process or thread until a particular condition is true
-
Operations that are defined for a semaphore
- Initialization
- semWait
- semSignal
|
|
