Requirements: Safety, Fairness, Liveness (Freedom from Starvation & Deadlock)
Performance Matrices: Synchronization Delay, System Throughput, Message Complexity, Response Time
Types
Centralized
Process requests the Coordinator and then Coordinator decides whether to allow to deny the access to CR
FIFO is used for process request
Uses 3 messages: Reply, Release, Request
Advantages
No starvation
Achieves mutual exclusion
Easy implementation
Disadvantages
Single point of faliure
Can't distinguish between ead coordinator and denied permission
Distributed
Non Token Based
Lamport
Algorithm
Pi sends request to all Pj
Pi makes entry in its own queue
Pj receives request message and makes entry in its own queue and sends reply to Pi
To access CS
Pi receives reply from all Pj
Its request is topmost in the queue
Pi exists the CS and removes itself from queue
Pi broadcast release message and then all Pj removes Pi entry
Performance Parameter: 3(n-1) messages per CS invocation
(n-1) Reply, Request, Release
Ricart
Algorithm
When a site Si wants to enter CS, it sends a timestamped request message to all the sites in its request set
When site Sj receives a Request message from site Si, it sends a Reply message to site Si if the two condition is fulfilled, the request is deferred otherwise
Site Sj is neither requesting nor executing the CS
Site Sj is requesting and Si requests timestamp is smaller than Sj own request timestamp
Site Si enters the CS after it has received Reply messages from all the sites in its request set
When site Si exits the CS, it sends Reply message to all the deferred requests
Performance Parameter: 2(n-1) messages per CS invocation
(n-1) Reply, Request
Maekawa
Rules for making Group
Intersection of two Groups should not be NULL
A process should be part of its own group
Group should contain more than one process
Algorithm
Process sends Request to all the processes in its group
Process should get Reply from all process in its group to access CS
If vote is "false", means no process in its group is accessing CS, permission is granted (Reply given), Vote is turned to "true"
If vote is "true", no reply is given and its value is stored in its queue for later consideration
After leaving CS, process sends Release message to all processes in its group, all these process turns vote to "false" and sends reply to process in their queue
Performance Matrix
Synchronization Delay: 2t
Messages: 3*√n
Advantage
No single point of faliure
Deadlock can be avoided by using timestamps
Token Based
Suzuki
Singhal's
RayMonds
Resource Management
Assigning process to the nodes
Techniques
Task Assignment Approach
Each process submitted by the user for processing is viewed as a collection of related tasks
This task is scheduled to a suitable resource in order to improve the performance
Requirements
Execution time of task
Amount of computation required by each task
Speed of CPU
Cost of processing each task on every node
Time of communication between one task and other task
Number of tasks we have
Goals
Minimization of IPC costs
Quick turnaround time for the complete process
A high degree of parallelism
Efficient utilization of resources
Load Balancing Approach
All processes submitted by the user are distributed among the resources by system
Equalize the workload among the resources and remove unbalanced load on the resources
Goals
Optimal resource utilization
Maximize throughput
Minimize response time
Avoid overloading
Avoid crashing
Types
Static
Deterministic (Works on average values of system, ignores current state)
It uses the information about the properties of the nodes and the characteristics of the process to be scheduled
Difficult to optimize
Probabilistic
Uses information of static attributes (number of nodes, processing capabilities, topology, ...) of the system to formulate simple process placement rules
Poor performance
Dynamic (Works on current state of system)
Centralized
Collects information to server nodes and makes assignment decision
Makes efficient decision and have lower Fault tolerance
Distributed
Contains entities to make decisions on predefined set of nodes
Avoid the bottleneck of collecting state information and react faster
Types
Cooperative
Distributed entities cooperate with each other
More complex and involve larger overhead
Stability better
Non-Cooperative
Entities act as autonomous one and make scheduling decisions independently from other entities
Issues in Designing
Load estimation policy
Determines how to estimate the workload of a node
Measurable Parameters can be
Total number of processes on the node
Resource demand of these processes
Instruction mis of these processes
Architecture and Speed of node's processor
Process transfer policy
Determines weather to execute the process locally or remote
Uses threshold policy to decide weather the node is heavily-loaded or lightly-leaded
Process is accepted if node is below threshold to execute
Process is transferred from heavily-loaded node to lightly-loaded node if above threshold value
Threshold value determined by
Static policy
Predefined value decided for each node depending on processing capabilities
Dynamic policy
Value calculated from average workload and predefined constant
State information exchange policy
Determines how to exchange load information among nodes
Types
Periodic Broadcast
Broadcast when state changes
On-demand exchange
Exchange by polling
Location transfer policy
Determines to which nodes the transferable policy should be sent
Threshold method
Random node is selected
Checks if that node is able to receive the process, then process is transferred
If node rejects, another node is selected randomly
This continues till probe limit is reached
Shortest method
L distinct nodes are chosen at random and polled to determine its load
Process is transferred to node having minimum value unless its workload value prohibits
Simple improvement is to discontinue probing when a node with 0 value is encountered
Bidding method
Nodes contains managers (sends processes) and contractors (receives processes)
Manager broadcast a request for bid and contractor responds with bids (based on capacity of contractor nodes) and manager selects the best offer
Manager is then notified and asked whether it accepts the process for execution or not
Full autonomy for the nodes regarding scheduling
Big communication overhead
Difficult to decide a good pricing policy
Pairing
Reduces the variance of load only between pairs
Each nodes ask some randomly chosen nodes to form a pair with it
A node only tries to find a process if it has at least two pairs
If it receives rejection then it randomly selects another node to make pair
Two nodes that differ greatly in load and temporarily paired and migration starts
The pair is broken as soon as the migration is over
Priority assignment policy
Determines the priority of execution of local and remote processes
Rules
Selfish
Local processes is given higher priority than remote processes
Worst response time among three
Altruistic
Remote processes is given higher
Best response time among three
Intermediate
When number of local processes is greater than or equal to remote processes then local processes is given higher priority otherwise remote processes is given higher priority
Migration limiting policy
Determines the total number of times a process can migrate
Types
Uncontrolled
Remote process arriving at a node is treated just as process originating at node, so process may be migrated any number of times
Controlled
Uses a migration count parameter to fix limit on the number of times a process can migrate
Irrevocable migration policy
Migration count is fixed to 1
Load Sharing Approach
Conserve the ability of the system to perform the work
Assuring none of the node are idle and none of the processes are queued
Ideas
Load estimation policy
Checks if node is idle or not
Counts total number of processes
Measures CPU utilization to count load
Process transfer policy
Algorithm normally uses all-or-nothing strategy
Node becomes receiver node if it has 0 process else becomes sender
Threshold value of all nodes is fixed to 2 instead of 1 to avoid having node with no processes
State information exchange policy
Broadcast when state changes to overloaded or underloaded
Broadcast-when-idle policy when receiver initiated policy is used with fixed value of 1
Poll when state changes, randomly asks nodes for state information until finds an appropriate one or probe limit is reached
Poll-when-idle policy when receiver initiated policy is used with fixed value of 1
Location transfer policy
Sender initiated location policy
Sender node decides where to send the process
Heavily loaded nodes search for lightly loaded nodes
Receiver initiated location policy
Receiver node decides where to send the process
Lightly loaded nodes search for receiver loaded nodes
Priority assignment policy
Same as load balancing
Migration limiting policy
Same as load balancing
Algorithms
Global Scheduling Algorithm
No prior knowledge about the process
Dynamic in nature
Quick decision making capability
Scalability
Fault tolerance
Process Management
Process Allocation
Which process should be assigned to which process
Process Migration
Relocation of process from source node to destination node
Types
Non-Preemptive
Migration before process starts executing in current node
Preemptive
Migration during process is executing in current node
Costlier
Mechanism
Freezing process in source node and restarting process in destination node
Transferring process address space form source node to destination node
Process state
Process address space
Forwarding all message for process on its destination node
Messages received after execution stooped at source node and before restarting process in destination node
Messages received after restarting process in destination node
Messages expected by already migrated process after restarting process in destination node
Mechanism for handling coprocesses
Threads
Part of a process
Each thread belongs to only one process
Threads can share common data so they do not need to use inter-process communication
Threads also have states like processes, Priority can be assigned
