24308 CSC 080A - 0 - Operating Systems Spring 2003 Monday, 5:30 pm - 8:15 pm , Kramer Science Center 102A Herbert J. Bernstein (yaya@dowling.edu) Concurrency

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC080/CSC080_Concurrency.html
Copyright © 2002 Herbert J. Bernstein and other parties. All rights reserved.

Topics

• Concurrency: The idea of concurrent execution; states and state diagrams; deadlock prevention; dispatching and context switching; interrupt handling in a concurrent environment.
• Distributed systems: Data communications concepts; network issues; the distinction between concurrency and autonomy; trust and management of errors; synchronization.
• Scheduling: Preemptive and nonpreemptive scheduling; scheduling policies; processes and threads; real-time issues.

 

 

Basic issues of concurrency

• Computational processes change states
• Information is equivalent to alternatives in the states of systems
• 0 or 1 in a bit of a word
• some information is of direct interest

input data for a culculation, results of a calculation
• some information is meta-information, information about the status of information
• the program is ready and waiting for input data
• the program is running
• the program has output data ready and is waiting to provide it
• We may view a computation in terms of all the states in the systems

e.g.treat all the bits in all the words in memory as bits in one big word
or aggregate all the status information
• We may view a computation in terms of organized subsets of information

e.g.all the data related to a particular sub-calculation with
all the meta-information about the status of that calculation
• Finite state machines (see http://www.nist.gov/dads/HTML/finiteStateMachine.html).
• Assign numbers to states, possibly with time
• List transitions among states on input or external events
• Complex systems may be modelled as multiple finite state machines
• Often implemented as simple tables of state transitions
• Often drawn as graphs with states as nodes and transitions as edges
• Degree of autonomy
• Single process
• Master-slave, delegation
• Multiple autonomous processes
• Deadlocks
• Process 1 waiting for resource held by process 2 which is waiting for resource held by process 1
• Especially serious when there is only one CPU being shared
• Always request multiple resources in the same order
• Provide a mechanism to ensure release of resources held by blocked processes
• See http://java.sun.com/docs/books/tutorial/essential/threads/deadlock.html
• Sharing a CPU
• Common memory provides inter-process communication
• Context switching -- saving/restoring registers, memory maps, etc.
• Process -- full context saved
• Thread -- only partial context saved (usually share memory maps)
• Processes may have system-level protections and resource access (kernel processes)
• Processes may have user-level protections and resource access (user processes)
• Processes may be created synchronously (traps, forks) or asynchronously (interrupts)
• Sharing a CPU costs time for context switches
• Sharing a CPU creates simple locking and coordination mechanisms
• Interprocess Communication (IPC)
• Shared memory
• Message passing
• Atomic operations, critical sections
• Locks and spin locks
• Software locks (Peterson's solution) depend on atomicity of memory references
• Hardware locks (NYU Ultracomputer Fetch and Add, TSL)
• Semaphores (see http://cne.gmu.edu/modules/ipc/pink/swsem.html)
• Two atomic operations
• simple case, semaphore s starts at 1
• down(s) (originally called p(s))
• if ( s == 0 ) { sleep(); } else { s--;}
• up(s) (originally called v(s))
• if ( s > 0 ) { wakeup_waiting_process(); } else {s++;}
• Mutex (mutual exclusion lock)
• simple two state sempahore
• usually inverted
• Monitor
• language managed critical section
• Barriers
• Wait for all processes to arrive at an agreed location

Distributed Systems

• Lack of shared memory
• No simple hardware for atomic operations
• Multiple replicas of data needed
• Message passing and remote procedure calls
• Three-way handshakes
• Significant latency in communications
• High overhead to all attempts at process coordination
• Long pipelines of data
• Time synchronization difficult
• Significant possibility of lost, duplicated or corrupted data
• Errors managed with redundant data (checksums)
• Layering used to create reliable virtual connections
• data stream broken into numbered packets
• data retained and retransmitted if not acknowledged
• matching circular buffers maintained on both sides
• extra pointers used to manage multiple un-acknowledged packets
• Significant possibility of intentionally incorrect data
• Identities of senders need to be authenticated
• Data needs to be checked
• DoS attacks need to be managed
• Encryption desirable (SSH, SSL, etc.)

Scheduling

• Processes and threads
• A process consists of the actual resources and actions of a computation
• A thread is a light-weight process
• Choosing among multiple processes that are ready to run
• Optimize for intended system use
• Serve processes in order set by psystem policies
• Try to optimize use of resources
• Many scheduling policies
• FIFO
• First job in is first job out
• Wastes resources on I/O bound jobs
• no may to get an urgent short job out
• Shortest job first, shortest remaining time first
• Estimate the CPU time to completion
• Run the job with shortest estimated time to completion first
• Correct time estimates based on measured CPU time vs. I/O wait time
• Reschedule as new jobs arrive
• Round robin scheduling
• Preempt running jobs on clock ticks.
• QOS (Quality of Service Scheduling)
• Rank jobs with priorities, serve "highest" priority jobs first
• Batch systems
• No users waiting for immediate response
• Subject to external priorities, run shortest remaining time job first
• Modify scheduling to allow for I/O
• I/O drivers interrupt compute-bound threads
• Mainly non-preemptive (wait for jobs to block on I/O)
• Coarse time grain on preemptive scheduling
• I/O in long streams if possible
• Time sharing systems and interactive systems
• Users waiting for immediate response
• Preemptive scheduling necessary
• Time scales below 1/2 second li>QOS flags make fair scheduling difficult -- some classes of service may starve
• I/O scheduling is a primary limitation in system response
• Buffers must be accessible early in transfer processes
• Drivers must keep the CPU for short periods of time
• Multiple I/O transactions must be supported "simultaneously"
• Threads may be scheduled separately as full processes or as sub processes by the parent. Typically all threads within a parent process on a mono-processor system are viewed as the presponsibility of the parent process. Efficient multiprocessor used requires more intimate interaction with the scheduler.
• Real-time systems
• Similar to interactive systems, but with hard constraints
• May avoid interrupts to ensure deterministic behavior
• Polling loops