|
UNIT – 4 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Unit-04/Lecture-01 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Distributed Scheduling -Issues
in Load Distributing 1.Load (i)
Resource and CPU queue
lengths are good indicators of load. (ii)
Artificially increment
CPU queue length for transferred jobs on their way. (iii)
Set timeouts for such
jobs to safeguard against transfer failures. (iv)
Little correlation
between queue length and CPU utilization for interactive jobs: use
utilization instead. (v)
Monitoring CPU
utilization is expensive (vi)
Modeling -- Poisson
Process, Markov process, M/M/1 queue, M/M/N 2.Classification of Algorithms (i)
Static -- decisions
hard-wired into algorithm using prior knowledge of system (ii)
Dynamic -- use state
information to make decisions. (iii)
Adaptive -- special case
of dynamic algorithms; dynamically change parameters of the algorithm 3.Load Sharing vs. Load Balancing (i)
Load Sharing -- reduce
the likelihood of unshared state by transferring tasks to lightly loaded
nodes (ii)
Load Balancing -- try to
make each load have approximately same load 4.Preemptive vs. Nonpreemptive (i)
Preemptive transfers --
transfer of a task that is partially executed, expensive due to collection of
task's state (ii)
Non preemptive transfers
-- only transfer tasks that have not begun execution. 5.Components of Load Distribution (i)
Transfer policy --
threshold based, determine if a process should be executed remotely or
locally (ii)
Selection policy --
which task should be picked, overhead in transfer of selected task should be
offset by reduction in its response time (iii)
Location policy -- which
node to be sent, possibly use polling to find suitable node (iv)
Information policy --
when should the information of other nodes should be collected;
demand-driven, or periodic, or state-change-driven Demand-driven: nodes gather information about
other nodes (i) sender initiated (ii) receiver initiated (iii)
symmetrically initiated Periodic : nodes exchange information
periodically State-change-driven
: nodes disseminate
information when their state changes (v) Stability -- queuing-theoretic, or
algorithmic perspective . ……………Reference { Singhal &
Shivratari, Advance Concept in Operating System, 262 } Components for Load Distributing Algorithms 1.
Transfer Policy: This
policy determines whether the node is in a suitable state to share the load.
Most of the transfer policies are threshold based policies, If a load at a
node exceeds a threshold value T, then the node is overloaded and act as a
sender. If the load at the node falls below a threshold T, then the load is
under loaded and acts as a receiver. 2.
Selection Policy: This
policy selects a task for transfer. Simplest approach is to select the newly
originated task at the node which has made this node as the sender for task
transfer, it will also be a cheap operation as it will be a non preemptive
task transfer. The basic criterion which is to be satisfied during selection
of a task is that the overhead incurred in task transfer must be less than
the reduction in response time of the task and long-lived task satisfies this
condition. Another factor which is to be considered during selection of
tasks is that the task must have fewer location dependent system calls since
such calls are to be executed on the same machine where the task has been
originated. 3.
Location Policy: This
policy selects the node where the selected task is to be transferred.
Simplest approach to find such node is Polling. In polling, one node calls another node
to determine whether it is in a state of load sharing. Nodes can be called
serially or parallaly. A node can be selected for polling randomly or on
nearest neighbor basis. An alternative to polling is to distribute a query to
all nodes to find the available nodes. 4.
Information Policy: This
policy is responsible for determining when the system state is to be corrected,
from where it is to be corrected and what information is to be corrected. It
is of three types: Demand Driven: In
this policy, the node starts correcting the state of other nodes when it
becomes a sender or receiver. This policy is basically a dynamic policy. This
policy can be sender initiated, receiver initiated or symmetrically
initiated. In sender initiated, a sender looks for receiver to give their
load, In receiver initiated, receiver searches for sender, take their load,
and symmetrically initiated is the combination of both where the collection
of the system state is started whenever there is need of extra processing
power. Periodic: In
this policy, the nodes exchange their system information periodically and on
the basis of this information, task transfer is made. This policy does not
adapt its activities according to system state change for example if the
system is already overloaded then exchanging the system state information
periodically will further worsen the situation. State Change Driven Policy: In
this policy, a node disseminates its state information to other nodes
whenever its state changes by certain degree. This policy differs from demand
driven policy as in this case, the nodes disseminate their state information
rather than collecting the state information of other nodes. Under
centralized approach, a node disseminates its information t centralized
collection point whereas in case of decentralized approach, a node
disseminate to peers. ……………Reference { Singhal &
Shivratari, Advance Concept in Operating System,264 }
Unit-04/Lecture-03 Different
Types of Load Distributing Algorithms Dynamic,
static, and adaptive algorithms: ·
Load-distributing
algorithms can be broadly characterized as dynamic, static, or adaptive.
Dynamic load distributing algorithms use system-state information (the loads
at nodes), at least in part, to make load-distributing decisions, while
static algorithms make no use of such information. Decisions are hard wired
in static load distributing algorithms using a priori knowledge of the
system. ·
For
example, under a simple “cyclic splitting” algorithm, each node assigns the
ith task it initiates to node i mod N, where N is the number of nodes in the
system. Alternatively, a probabilistic algorithm assigns a task to node i
with probability p,, where the probabilities are determined statically
according to factors such as the average task-initiation rate and execution
rate for each node. ·
Each
of these algorithms can potentially make poor assignment decisions. Because
they do not consider node states when making such decisions, they can
transfer a task initiated at an otherwise idle node to a node having a
serious backlog of tasks. Dynamic algorithms have the potential to outperform
static algorithms by using system-state information to improve the quality of
their decisions. For example, a simple dynamic algorithm might be identical
to a static algorithm, except that it would not transfer an arriving task if
the node where it arrived was idle. ·
A
more sophisticated dynamic algorithm might also take the state of the
receiving node into account, possibly transferring a task to a node only if
the receiving node was idle. A still more sophisticated dynamic algorithm
might transfer an executing task if it was sharing a node with another task
and some other node became idle. ·
Essentially, dynamic algorithms improve
performance by exploiting short-term fluctuations in the system state.
Because they must collect, store, and analyze state information, dynamic
algorithms incur more overhead than their static counterparts, but this
overhead is often well spent. Most recent load-distributing research has
concentrated on dynamic algorithms, and they will be our focus for the
remainder of this article. ·
Adaptive
load-distributing algorithms are a special class of dynamic algorithms. They
adapt their activities by dynamically changing their parameters, or even
their policies, to suit the changing system state. For example, if some load
distributing policy performs better than others under certain conditions,
while another policy performs better under other conditions, a simple
adaptive algorithm might choose between these policies based on observations
of the system state. ·
Even when the system is uniformly so heavily
loaded that no performance advantage can be gained by transferring tasks, a
non adaptive dynamic algorithm might continue operating (and incurring
overhead). To avoid overloading such a system, an adaptive algorithm might
instead curtail its load distributing activity when it observes this
condition. Load. ·
A
key issue in the design of dynamic load-distributing algorithms is
identifying a suitable load index. A load index predicts the performance of a
task if it is executed at some particular node. To be effective, load index
readings taken when tasks initiate should correlate well with task-response
times. ·
Load indexes that have been studied and used
include the length of the CPU queue, the average CPU queue length over some
period, the amount of available memory, the context-switch rate, the system
call rate, and CPU utilization. ·
Researchers
have consistently found significant differences in the effectiveness of such
load indexes - and that simple load indexes are particularly effective. For
example, Kunz’ found that the choice of a load index has considerable effect
on performance, and that the most effective of the indexes we have mentioned
is the CPU queue length. ·
Furthermore, Kunz found no performance
improvement over this simple measure when combinations of these load indexes
were used. It is crucial that the mechanism used to measure load be efficient
and impose minimal overhead. Preemptive
versus non preemptive transfers ·
Preemptive
task transfers involve transferring a partially executed task. This operation
is generally expensive, since collecting a task’s state (which can be quite
large or complex) is often difficult. Typically, a task state consists of a
virtual memory image, a process control block, unread I/O buffers and
messages, file pointers, timers that have been set, and so on. ·
Non
preemptive task transfers, on the other hand, involve only tasks that have
not begun execution and hence do not require transferring the task’s state.
In both types of transfers, information about the environment in which the
task will execute must be transferred to the remote node. This information
may include the user’s current working directory and the privileges inherited
by the task. Non preemptive task transfers are also called task placements. Centralization. ·
Dynamic
load-distributing algorithms differ in their degree of centralization.
Algorithms can be centralized, hierarchical, fully decentralized or some
combination of these. ·
Algorithms
with some centralized components are potentially less reliable than fully
decentralized algorithms, since the failure of a central component may cause
the entire system to fail. ·
A
solution to this problem is to maintain redundant components, which can
become active when the previously active component fails. A second weakness
of centralized algorithms is not so easily remedied: A central component is
potentially a bottleneck, limiting load distribution. While hierarchical
algorithms can alleviate both problems, the complete solution lies in fully
decentralized algorithms. ……………Reference { Singhal &
Shivratari, Advance Concept in Operating System,266 }
Unit-04/Lecture-04 TASK MIGRATION Introduction
(i)
Task
placement: non-preemptive transfer of process that has never run (ii)
Task
migration: preemptive transfer of process that has been executed (iii)
Home
node: site where the process originates (iv)
Foreign
process: process executing on a node other than its home node (v)
Freezing:
when a process is migrated, its execution is interrupted (frozen) for the
time it takes to move the process to another site.
(i)
load
distribution, to equalize workload due to (a)
transient
periods of high load at some network nodes (transfer processes from
temporarily overloaded node to another node) (b)
or
in a system where process origination is always unbalanced (a few
workstations consistently generate many processes ) (ii)
to
return a workstation to its owner. (migrate a foreign process back to its
home node when owner returns) (iii)
to
improve communication (processes that communicate frequently can be moved to
the same node; processes that access resources at a remote site may be moved
to that site)
(i)
State
transfer: collect all information crucial to process execution and
transfer to another machine (a)
Process
control block contains register contents, memory map information, etc. (b)
Process
address space includes stack, heap, plus virtual pages Currently in memory At
some point during state collection, the process must be frozen (ii)
Unfreeze:
after installing the process state at the new site, the process is put in the
Ready queue to be scheduled Unit-04/Lecture-05
Issues in Task Migration (i)
State Transfer: Issues to consider here include (a)
Cost
in processor time, network bandwidth, etc.: When a process is moved to
another node, it is frozen until the transfer is complete. There is the cost
of a complete context switch, plus transfer, plus possible affect on other
processes that might be affected. (Processes that interact with the migrating
process may timeout during the interval when it is frozen, and thus could be
aborted) (b)
Residual
dependencies: These are resources that the original host node must maintain
on behalf of the migrated process. For example, a process may transfer pages
in virtual memory only as they are referenced; the original host may have to
forward messages directed to the process at its original site. (ii)
Location
Transparency: Users aren't required to know where a task is executed; there
should be no affect on the process. Process names, file names, etc., must be
independent of the host machine. A uniform name space is important to allow
the process to maintain access to system resources, to continue to be able to
communicate with other processes, etc. (iii)
Structure
of the Migration Mechanism: It emphasizes the separation of policy from
mechanism. Policy decides
when/where/why transfer to be done (see discussion of policies earlier) while
mechanism is the act of
collecting state, sending it elsewhere, etc. As always, there are benefits to
separating the two: for example, policies can be changed without affecting
mechanisms. (iv)
Performance:
This is the major drawback to any kind of dynamic task migration facility. Process Migration Mechanisms The following issues in
designing a process migration facility: (i)
Who
initiates the migration? (ii)
What
part of the process is migrated? (iii)
What
happens to messages and signals? Migration Initiation (i)
Migration
can be initiated either by a module in the operating system, or by the
process itself. (ii)
OS
module is the most common when load sharing is the primary objective of the
migration (iii)
If
the goal is to move closer to resources or other processes, then the
migration could be initiated by the process itself. What is Migrated (i)
The
process control block (PCB) is required, but is relatively easy to transfer
from one machine to another (especially if the machines are heterogeneous) (ii)
Process
address space is more difficult. The process will have a number of
virtual pages in memory, and the question is whether to some or all, whether
to pre copy (move pages to new host while execution continues on old host),
etc. Some possibilities include: (a)
Immediately
move all of them (eager
transfer) (b)
Move
all pages that are dirty, but transfer others on demand only (c)
Move
no pages at all until they are referenced (d)
Flush
pages to disk, page back in when they are referenced on the remote site Messages and Signals (i)
Any
messages or signals intended for a frozen process are stored at the host
until the process transfer is complete (ii)
Other
messages and signals must be routed from the home site to the new host. Heterogeneity Many distributed systems consist
of a variety of different platforms, running several different operating
systems. This brings up a number of problems; e.g., (i)
Object
code for one machine won’t execute on a machine with a different instruction
set. (ii)
Data
representations may differ from one platform to another (iii)
Register
structure will be different; information in PCB may not be directly
transferable to a different computer. Solutions
are based on ideas such as (i)
Maintaining
a migration stack that has platform-independent representations of
platform-specific data (ii)
Use
of some sort of virtual machine approach, such as a common intermediate code
that can be recompiled quickly for different platforms (similar to Java’s
virtual machine concept) Instances of Load Distribution
and Process Migration (i)
Clusters
dedicated to the execution of parallel programs often use static load
distribution; less often would use dynamic load distribution, seldom use
process migration (ii)
Many
research-based distributed systems, including Sprite, Charlotte, V-System,
implemented process migration in the context of a network of
workstations. (iii)
Current
research in areas such as grid computing visualizes using remote resources on
a wide-area network. Mobile agent research focuses on
independently initiated movement of processes around a network to do various
tasks: searches in a distributed data base, comparison shopping, etc. ……………Reference { Singhal &
Shivratari, Advance Concept in Operating System,283 }
Unit-04/Lecture-06 Deadlock-Issues in deadlock detection
& Resolutions (dec2011) Deadlock can occur whenever two
or more processes are competing for limited resources and the processes are
allowed to acquire and hold a resource (obtain a lock) thus preventing others
from using the resource while the process waits for other resources. Two common places where
deadlocks may occur are with processes in an operating system (distributed or
centralized) and with transactions in a database. The concepts discussed here are applicable
to any system that allocates resources to processes. Locking protocols such as the
popular Two Phase Locking (see concurrency control) give rise to deadlock as
follows: process A gets a lock on data item X while process B gets a lock on
data item Y. Process A then tries to
get a lock on Y. As Y is already
locked, process A enters a blocked state.
Process B now decides to get a lock on X, but is blocked. Both processes are now blocked, and, by the
rules of Two Phase Locking, neither will relinquish their locks. This is a deadlock: process A is
waiting for a resource held by process B and process B is waiting for a
resource held by process A. No
progress will take place without outside intervention. Several processes can be involved in a
deadlock when there exists a cycle of processes waiting for each other.
Process A waits for B which waits for C which waits for A. Four conditions must hold for
deadlock to occur: 1. Exclusive use – when a process
accesses a resource, it is granted exclusive use of that resource. 2. Hold and wait – a process is allowed
to hold onto some resources while it is waiting for other resources. 3. No preemption – a process cannot
preempt or take away the resources held by another process. 4. Cyclical wait – there is a circular
chain of waiting processes, each waiting for a resource held by the next
process in the chain. The structure of the system may
allow additional complexities in the deadlock problem. The simplest model, single-resource,
requires that a process have no more than one unfulfilled request. Thus a blocked process is waiting for only
one other process and can be involved in at most one deadlock cycle. In
the AND model (also called the multiple-resource model), a process is allowed
to make several resource requests, and it is blocked until all of the
requests are granted. Processes in
this model can be involved in several deadlock cycles at once. In the OR
model (also called the communication model), a process makes several requests
and is blocked until any one of them is granted. The AND-OR model allows a combination of
request types, such as a request for resource X and either Y or Z. The problem of deadlocks can be
handled in several ways: Prevention, Avoidance, and Detection. In prevention, some requirement of the
system makes deadlocks impossible so that no runtime support is
required. Avoidance schemes require
decisions by the system while it is running to insure that deadlocks will not
occur. Detection requires the most
sophisticated runtime support: the system must find deadlocks and break them
by choosing a suitable victim that is terminated or aborted and restarted if
appropriate. ……………Reference { Singhal &
Shivratari, Advance Concept in Operating System,154 } Distributed Deadlock Handling
Strategies(Dec2013) 1.Deadlock prevention (i)
All
resource at once. (ii)
Preventing
a process from holding while waiting (iii)
Inefficient,
can become deadlocked at resource acquiring phase, resource requirements are
unpredictable -- not an efficient, universal solution. 2.Deadlock avoidance (i)
A resource is granted to
a process if the resulting state is safe (ii)
Every site has to
maintain the global state (iii)
The checking for a safe
state must be done with mutual exclusion (iv)
The number of processes
and resources in a distributed system is large (v)
Not a practical solution 3.Deadlock detection (i) Once deadlock, always deadlock --
detection won't be outdated (ii)
deadlock detection can be proceed concurrently with normal activities Deadlock handling Most
current operating systems cannot prevent a deadlock from occurring.When a
deadlock occurs, different operating systems respond to them in different
non-standard manners. Most approaches work by preventing one of the four
Coffman conditions from occurring, especially the fourth one. Major approaches
are as follows. Ignoring deadlock:In this approach, it is
assumed that a deadlock will never occur. This is also an application of the Ostrich algorithm. This
approach was initially used by MINIX and UNIX. This
is used when the time intervals between occurrences of deadlocks are large
and the data loss incurred each time is tolerable. Detection Under
deadlock detection, deadlocks are allowed to occur. Then the state of the
system is examined to detect that a deadlock has occurred and subsequently it
is corrected. An algorithm is employed that tracks resource allocation and
process states, it rolls back and restarts one or more of the processes in
order to remove the detected deadlock. Detecting a deadlock that has already
occurred is easily possible since the resources that each process has locked
and/or currently requested are known to the resource scheduler of the
operating system. Deadlock
detection techniques include, but are not limited to, model checking. This approach constructs
a finite state-model on which it
performs a progress analysis and finds all possible terminal sets in the
model. These then each represent a deadlock. After
a deadlock is detected, it can be corrected by using one of the following
methods:
Unit-04/Lecture-07 Distributed
Deadlock Algorithms A. Centralized Approach - deadlock-detection coordinator constructs global wait-for graph, detects
deadlock, and selects victim process to rollback. Options for keeping global wait-for graph up to date: 1) coordinator sent a message
whenever an edge is added or deleted in a local wait-for graph 2) periodically each machine sends a
list of collection of changes that have been made to the local wait-for graph 3) coordinator requests local
wait-for graphs from each site when it wants to invoke the deadlock detection
algorithm Due to incomplete or delayed information, the coordinator's
constructed global-wait-for graph may not exactly match the real
situation. False
cycles/deadlocks might be incorrectly detected with unnecessary
processes being rolled back. Distributed Deadlock-Detection Algorithm (based on
option 3 and timestamps) Operation of "Requesting-Sending Site": When a process Pi at site A requests a resource
from Pj at site B, a request message with timestamp TS is
sent (here the relative size of the timestamps are not important just that
they are unique identifiers), and the edge Pi Operation of "Request-Receiving Site": When the request message with timestamp TS from process Pi at
site A is received at site B for a resource held by Pj at
site B, an edge Pi Coordinator's Deadlock Detection Algorithm 1) Periodically, the coordinator sends an initiate message to
each site which causes each site to send their current local wait-for graph. 2) When the coordinator has received all of the local wait-for
graphs, it constructs a global wait-for graph as follows: a) A vertex for every process in the
system. b) An edge Pi i) there is an edge Pi local resources held by local
processes), or ii) an edge Pi graph
The above algorithm does not
detect false cycles, but does detect all actual cycles/deadlocks. B. Fully Distributed Approach to Deadlock Detection A controller at each site shares an equal role in deadlock
detection. The controller at each site maintains a local wait-for graph
containing local processes and an additional "process" Pex (ex
for external). A local process will have an edge to Pex if it
requests a nonlocal resource held by another process. Edges from Pex to
a local process will exist if a nonlocal process requests a resource held by
the local process. Suppose that site A had some local processes that were involved
in a deadlock cycle with some nonlocal processes. What would site A's local
wait-for graph look like?
Answer: It would contain a cycle involving the local processes
involved in the deadlock cycle and Pex. Is a cycle involving some
local processes and Pex sufficient to indicate a deadlock?
When a controller detects a cycle in the local wait-for graph
containing only local processes (excluding Pex), then it has detected deadlock. When a
controller detects a cycle in the local wait-for graph containing Pex,
then it must invoke a distributed cycle-detection algorithm. ` Unit-04/Lecture-08 Distributed cycle-detection idea The controller detecting a cycle
containing Pex of Pex
Distributed Deadlock Prevention - design system so
deadlock is structurally impossible by denying one of the four necessary
conditions. Distributed Algorithm using
unique process-priority numbers, global time stamping and resource
pre-emption. (Here we assume only one resource of each type. Processes get a timestamp when
they are created (If they get rolled back/killed, they are given the same
timestamp). Timestamps are used to prevent a cycle necessary for deadlock. Wait-die Algorithm - roll back/die younger
process if it requests a resource held by an older process.
How does this prevent
deadlock??? Answer: To get a cycle in a
wait-for graph, a younger process would need to wait for an older process.
Since this is not allowed, deadlock is prevented. Wound-Wait Algorithm - allow older process to
pre-empt resource held by younger process (killing or wounding it).
Prevention (Dec 2013) Deadlock prevention algorithms Deadlock
prevention works by preventing one of the four Coffman conditions from
occurring. (i) Removing
the mutual exclusion condition means that no process will have exclusive
access to a resource. This proves impossible for resources that cannot be spooled. But
even with spooled resources, deadlock could still occur. Algorithms that
avoid mutual exclusion are called non-blocking synchronization
algorithms. (ii) The
hold and wait or resource holding conditions may be removed by requiring
processes to request all the resources they will need before starting up (or
before embarking upon a particular set of operations). This advance knowledge
is frequently difficult to satisfy and, in any case, is an inefficient use of
resources. Another way is to require processes to request resources only when
it has none. Thus, first they must release all their currently held resources
before requesting all the resources they will need from scratch. This too is
often impractical. It is so because resources may be allocated and remain
unused for long periods. Also, a process requiring a popular resource may
have to wait indefinitely, as such a resource may always be allocated to some
process, resulting in resource starvation.(These
algorithms, such as serializing tokens, are
known as the all-or-none algorithms.) (iii) The no
pre-emption condition may also be difficult or
impossible to avoid as a process has to be able to have a resource for a
certain amount of time, or the processing outcome may be inconsistent or thrashing may
occur. However, inability to enforce pre-emption may interfere with a priority algorithm. Pre-emption of
a "locked out" resource generally implies a rollback, and is to be avoided, since it is
very costly in overhead. Algorithms that allow pre-emption include lock-free and wait-free algorithms and optimistic concurrency control. (iv)
The final
condition is the circular wait condition. Approaches that avoid circular
waits include disabling interrupts during critical sections and using a
hierarchy to determine a partial
ordering of resources. If no obvious
hierarchy exists, even the memory address of resources has been used to
determine ordering and resources are requested in the increasing order of the
enumeration. Dijkstra's solution can also be used. Avoidance Deadlock
can be avoided if certain information about processes are available to the
operating system before allocation of resources, such as which resources a
process will consume in its lifetime. For every resource request, the system
sees whether granting the request will mean that the system will enter an unsafe state, meaning a state that
could result in deadlock. The system then only grants requests that will lead
to safe states.In order for
the system to be able to determine whether the next state will be safe or
unsafe, it must know in advance at any time: (i) resources
currently available (ii) resources
currently allocated to each process (iii) resources
that will be required and released by these processes in the future It is
possible for a process to be in an unsafe state but for this not to result in
a deadlock. The notion of safe/unsafe states only refers to the ability of the system to enter a
deadlock state or not. For example, if a process requests A which would
result in an unsafe state, but releases B which would prevent circular wait,
then the state is unsafe but the system is not in deadlock. One
known algorithm that is used for deadlock avoidance is the Banker's algorithm,
which requires resource usage limit to be known in advance. However, for many
systems it is impossible to know in advance what every process will request.
This means that deadlock avoidance is often impossible. Two
other algorithms are Wait/Die and Wound/Wait, each of which uses a
symmetry-breaking technique. In both these algorithms there exists an older
process (O) and a younger process (Y). Process age can be determined by a
timestamp at process creation time. Smaller timestamps are older processes,
while larger timestamps represent younger processes. ……………Reference {http://www.cs.uni.edu} `
Unit-04/Lecture-09 Discuss the various
concurrency control protocols Distributed concurrency control is the concurrency
control of a
system distributed over a computer
n In database systems and transaction
processing (transaction
management) distributed concurrency control refers primarily to the
concurrency control of a distributed
database. It also
refers to the concurrency control in a multidatabase (and other multi-transactional object) environment (e.g., grid computing, cloud computing environments. A major goal for distributed
concurrency control is distributed serializability (or global
serializability
for multidatabase systems). Distributed concurrency control
poses special challenges beyond centralized one, primarily due to
communication and computer latency. It often requires special
techniques, like distributed
lock manager over
fast computer networks with low latency, like switched fabric (e.g., InfiniBand). commitment
ordering (or
commit ordering) is a general serializability technique that achieves
distributed serializability (and global serializability in particular)
effectively on a large scale, without concurrency control information
distribution (e.g., local precedence relations, locks, timestamps, or
tickets), and thus without performance penalties that are typical to other
serializability techniques The most common distributed
concurrency control technique is strong strict two-phase locking (SS2PL, also named rigorousness),
which is also a common centralized concurrency control technique. SS2PL
provides both the serializability, strictness, and commitment ordering properties. Strictness, a
special case of recoverability, is utilized for effective recovery from
failure, and commitment ordering allows participating in a general solution
for global serializability. For large-scale distribution and complex
transactions, distributed locking's typical heavy performance penalty (due to
delays, latency) can be saved by using the atomic commitment protocol, which is needed in a distributed database for
(distributed) transactions' atomicity (e.g., two-phase commit, or a simpler one in a reliable system), together with some local
commitment ordering variant (e.g., local SS2PL) instead of distributed locking,
to achieve global serializability in the entire system. All the commitment
ordering theoretical results are applicable whenever atomic commitment is
utilized over partitioned, distributed recoverable (transactional) data,
including automatic distributed deadlock resolution. Such technique can be utilized also
for a large-scale parallel
database, where a
single large database, residing on many nodes and using a distributed lock
manager, is replaced with a (homogeneous) multidatabase, comprising many
relatively small databases (loosely defined; any process that supports
transactions over partitioned data and participates in atomic commitment
complies), fitting each into a single node, and using commitment ordering
(e.g., SS2PL, strict CO) together with some appropriate atomic commitment
protocol (without using a distributed lock manager). ……………Reference {https://en.wikipedia.org}
. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
