Transcript Operating Systems

Operating Systems:
Internals and Design Principles, 6/E
William Stallings
Multiple Processor Systems
Bits of Chapters 4, 10, 16
Parallel Processor Architectures
Multiprocessor Systems
• Continuous need for faster computers
– shared memory model
– message passing multiprocessor
– wide area distributed system
Multiprocessors
Definition:
A computer system in which two or
more CPUs share full access to a
common RAM
Multiprocessor Hardware
Bus-based multiprocessors
Non-blocking network
UMA Multiprocessor using a crossbar switch
Blocking network
Omega Switching Network
Master-Slave multiprocessors
Bus
Symmetric Multiprocessors
Bus
Symmetric Multiprocessor Organization
Multiprocessor Operating
Systems Design Considerations
• Simultaneous concurrent processes or
threads: reentrant routines, IPC
• Scheduling: on which processor a process
should run
• Synchronization: locks
• Memory management: e.g. shared pages
• Reliability and fault tolerance: graceful
degradation
Multiprocessor Synchronization
TSL fails if bus is not locked
Spinning versus Switching
• In some cases CPU must wait
– waits to acquire ready list
• In other cases a choice exists
– spinning wastes CPU cycles
– switching uses up CPU cycles also
– possible to make separate decision each
time locked mutex encountered (e.g. using
history)
Scheduling Design Issues
• Assignment of processes to processors
• Use of multiprogramming on individual
processors
• Actual dispatching of a process
Assignment of Processes to Processors
• Treat processors as a pooled resource
and assign process to processors on
demand
• Static assignment: Permanently assign
process to a processor
– Dedicate short-term queue for each processor
– Less overhead
– Processor could be idle while another
processor has a backlog
Assignment of Processes to Processors (2)
• Dynamic assignment: Global queue
– Schedule to any available processor
– Process migration, cf. local cache
Master/slave architecture
– Key kernel functions always run on a
particular processor
– Master is responsible for scheduling
– Slave sends service request to the master
– Disadvantages
• Failure of master brings down whole system
• Master can become a performance bottleneck
Peer architecture
– Kernel can execute on any processor
– Each processor does self-scheduling
– Complicates the operating system
• Make sure two processors do not choose the same
process
Traditional Process Scheduling
• Single queue for all processes
• Multiple queues are used for priorities
• All queues feed to the common pool of
processors
Thread Scheduling
• An application can be a set of threads that
cooperate and execute concurrently in the
same address space
• True parallelism
Comparison One and Two Processors
Comparison One and Two Processors (2)
Multiprocessor Thread Scheduling
• Load sharing
– Threads are not assigned to a particular
processor
• Gang scheduling
– A set of related threads is scheduled to run on
a set of processors at the same time
• Dedicated processor assignment
– Threads are assigned to a specific processor
Load Sharing
• Load is distributed evenly across the
processors
• No centralized scheduler required
• Use global queues
Disadvantages of Load Sharing
• Central queue needs mutual exclusion
• Preemptive threads are unlikely to resume
execution on the same processor
• If all threads are in the global queue, not
all threads of a program will gain access to
the processors at the same time
Multiprocessor Scheduling (3)
• Problem with communication between two
threads
– both belong to process A
– both running out of phase
Gang Scheduling
• Simultaneous scheduling of threads that
make up a single process
• Useful for applications where performance
severely degrades when any part of the
application is not running
• Threads often need to synchronize with
each other
Dedicated Processor
Assignment
• When application is scheduled, its threads
are assigned to a processor
• Some processors may be idle
• No multiprogramming of processors
Application Speedup
Client/Server Computing
• Client machines are generally single-user
PCs or workstations that provide a highly
user-friendly interface to the end user
• Each server provides a set of shared
services to the clients
• The server enables many clients to share
access to the same database and enables
the use of a high-performance computer
system to manage the database
Generic Client/Server
Environment
Client/Server Applications
• Basic software is an operating system
running on the hardware platform
• Platforms and the operating systems of
client and server may differ
• These lower-level differences are
irrelevant as long as a client and server
share the same communications protocols
and support the same applications
Generic Client/Server
Architecture
Middleware
• Set of tools that provide a uniform means
and style of access to system resources
across all platforms
• Enable programmers to build applications
that look and feel the same
• Enable programmers to use the same
method to access data
Role of Middleware in
Client/Server Architecture
Distributed Message Passing
Basic Message-Passing
Primitives
Reliability versus Unreliability
• Reliable message-passing guarantees
delivery if possible
– Not necessary to let the sending process
know that the message was delivered
• Send the message out into the
communication network without reporting
success or failure
– Reduces complexity and overhead
Blocking versus Nonblocking
• Nonblocking
– Process is not suspended as a result of
issuing a Send or Receive
– Efficient and flexible
– Difficult to debug
Blocking versus Nonblocking
• Blocking
– Send does not return control to the sending
process until the message has been
transmitted
– OR does not return control until an
acknowledgment is received
– Receive does not return until a message has
been placed in the allocated buffer
Remote Procedure Calls
• Allow programs on different machines to
interact using simple procedure call/return
semantics
• Widely accepted
• Standardized
– Client and server modules can be moved
among computers and operating systems
easily
Remote Procedure Call
Remote Procedure Call
Mechanism
Client/Server Binding
• Binding specifies the relationship between
remote procedure and calling program
• Nonpersistent binding
– Logical connection established during remote
procedure call
• Persistent binding
– Connection is sustained after the procedure
returns
Synchronous versus
Asynchronous
• Synchronous RPC
– Behaves much like a subroutine call
• Asynchronous RPC
– Does not block the caller
– Enable a client execution to proceed locally in
parallel with server invocation
Clusters
• Alternative to symmetric multiprocessing
(SMP)
• Group of interconnected, whole computers
(nodes) working together as a unified
computing resource
– Illusion is one machine
No Shared Disks
Shared Disk
Clustering Methods: Benefits
and Limitations
Clustering Methods: Benefits
and Limitations
Operating System Design
Issues
• Failure management
– Highly available cluster offers a high
probability that all resources will be in service
• No guarantee about the state of partially executed
transactions if failure occurs
– Fault-tolerant cluster ensures that all
resources are always available
Operating System Design
Issues (2)
• Load balancing
– When new computer added to the cluster, the
load-balancing facility should automatically
include this computer in scheduling
applications
Multicomputer Scheduling - Load Balancing (1)
Process
• Graph-theoretic deterministic algorithm
Load Balancing (2)
• Sender-initiated distributed heuristic
algorithm
– overloaded sender
Load Balancing (3)
• Receiver-initiated distributed heuristic
algorithm
– under loaded receiver
Operating System Design
Issues (3)
• Parallelizing Computation
– Parallelizing compiler: determines at compile
time which parts can be executed parallel
– Parallelized application: by programmer,
message passing for moving data
– Parametric computing: several runs with
different settings – simulation model
Clusters Compared to SMP
• SMP is easier to manage and configure
• SMP takes up less space and draws less
power
• SMP products are well established and
stable
Clusters Compared to SMP
• Clusters are better for incremental and
absolute scalability
• Clusters are superior in terms of
availability