DOC PREVIEW
FSU COP 5611 - COP 5611 Lecture Notes

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Outline Announcement Distributed scheduling continued Quiz at the end of today s class Announcement Schedule for the rest of the semester 4 10 Recovery 4 15 Fault tolerance 4 17 Class evaluation Protection and security 4 22 Protection and security continued Quiz 3 4 24 Existing distributed systems and review Final exam 5 30 7 30PM April 29 2003 Cumulative January 14 2019 COP 5611 Operating Systems 2 Motivations January 14 2019 COP 5611 Operating Systems 3 Motivations cont January 14 2019 COP 5611 Operating Systems 4 Distributed Scheduling A distributed scheduler is a resource management component of a distributed operating system that focuses on judiciously and transparently redistributing the load of the system among the computers to maximize the overall performance January 14 2019 COP 5611 Operating Systems 5 Components of a Load Distributing Algorithm Four components Transfer policy Determines when a node needs to send tasks to other nodes or can receive tasks from other nodes Selection policy Determines which task s to transfer Location policy Find suitable nodes for load sharing Information policy January 14 2019 COP 5611 Operating Systems 6 Stability The queuing theoretic perspective The CPU queues grow without bound if arrival rate is greater than the rate at which the system can perform work A load distributing algorithm is effective under a given set of conditions if it improves the performance relative to that of a system not using load distribution Algorithmic stability An algorithm is unstable if it can perform fruitless actions indefinitely with finite probability Processor thrashing January 14 2019 COP 5611 Operating Systems 7 Sender Initiated Algorithms January 14 2019 COP 5611 Operating Systems 8 Receiver Initiated Algorithms January 14 2019 COP 5611 Operating Systems 9 Empirical Comparison of Sender Initiated and Receiver Initiated Algorithms January 14 2019 COP 5611 Operating Systems 10 Symmetrically Initiated Algorithms Sender initiated component A sender broadcasts a TooHigh message sets a TooHigh timeout alarm and listens for an Accept A receiver that receives a TooHigh message cancels its TooLow timeout sends an Accept message to the sender and increases its load value On receiving an Accept message if the site is still a sender choose the best task to transfer and transfer it If no Accept has been received before the timeout it broadcasts a ChangeAverage message to increase the average load estimates at the other nodes January 14 2019 COP 5611 Operating Systems 11 Symmetrically Initiated Algorithms cont Receiver initiated component It broadcasts a TooLow message set a TooLow timeout alarm and starts listening for a TooHigh message If TooHigh message is received it cancels its TooLow timeout sends an Accept message to the sender and increases its load value If no TooHigh message is received before the timeout the receiver broadcasts a ChangeAverage message to decrease the average at other nodes January 14 2019 COP 5611 Operating Systems 12 Comparison January 14 2019 COP 5611 Operating Systems 13 Adaptive Algorithms A stable symmetrically initiated algorithm Each node keeps of a senders list a receivers list and an OK list By classifying the nodes in the system as Sender overloaded Receiver underloaded or OK using the information gathered through polling January 14 2019 COP 5611 Operating Systems 14 A Stable Symmetrically Initiated Algorithm cont Sender initiated component The sender polls the node at the head of the receiver The polled node moves the sender to the head of its sender list and sends a message indicating it is a receiver sender or OK node The sender updates the polled node based on the reply If the polled node is a receiver it transfers a task The polling process stops if its receiver s list becomes empty or the number of polls reaches a PollLimit January 14 2019 COP 5611 Operating Systems 15 A Stable Symmetrically Initiated Algorithm cont Receiver initiated component The nodes polled in the following order Head to tail of its senders list Tail to head in the OK list Tail to head in the receivers list January 14 2019 COP 5611 Operating Systems 16 A Stable Sender Initiated Algorithm This algorithm uses the sender initiated algorithm of the stable symmetrically initiated algorithm Each node is augmented by an array called the statevector It keeps track of its status at all the other nodes in the system It is updated based on the information at the polling stage The receiver initiated component is replaced by the following protocol When a node becomes a receiver it informs all the nodes that are misinformed January 14 2019 COP 5611 Operating Systems 17 Comparison January 14 2019 COP 5611 Operating Systems 18 Performance Under Heterogeneous Workloads January 14 2019 COP 5611 Operating Systems 19 Selecting a Suitable Load Sharing Algorithm The best algorithm depends on the system under consideration For example if the system never attains high loads sender initiated algorithms will give an improved algorithm Stable scheduling algorithms should be used for systems that can reach high loads For systems with heterogeneous work loads adaptive stable algorithms are preferable January 14 2019 COP 5611 Operating Systems 20 Other Requirements of Load Distributing Scalability The algorithm should work well in large distributed systems Location transparency Determinism Preemption Heterogeneity January 14 2019 COP 5611 Operating Systems 21 Case Studies The V System The Sprite system Condor system The Stealth distributed scheduler January 14 2019 COP 5611 Operating Systems 22 Task Placement vs Task Migration Task placement vs task migration Task placement refers to the transfer of a task that is yet to begin execution to a new location and starts its execution there Task migration refers to the transfer of task that has already begun execution to a new location and continuing its execution there January 14 2019 COP 5611 Operating Systems 23 Task Migration State transfer The task s state includes the content of registers the task stack the task s status virtual memory address space file descriptors any temporary files and buffered messages In addition current working directory signal masks and handlers resource usage statistics and references to children and parent processes Unfreeze The task is installed at the new machine and is put in the ready queue January 14 2019 COP 5611 Operating Systems 24 Issues in Task Migration State transfer The cost to support


View Full Document

FSU COP 5611 - COP 5611 Lecture Notes

Documents in this Course
Load more
Download COP 5611 Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view COP 5611 Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view COP 5611 Lecture Notes and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?