Operating system chapter 15

Operating system chapter 15

اسلاید 1: 1Distributed Process ManagementChapter 15

اسلاید 2: 2Process MigrationTransfer of sufficient amount of the state of a process from one computer to anotherThe process executes on the target machine

اسلاید 3: 3MotivationLoad sharingMove processes from heavily loaded to lightly load systemsCommunications performanceProcesses that interact intensively can be moved to the same node to reduce communications costMay be better to move process to where the data reside when the data is large

اسلاید 4: 4MotivationAvailabilityLong-running process may need to move because the machine it is running on will be downUtilizing special capabilitiesProcess can take advantage of unique hardware or software capabilities

اسلاید 5: 5Initiation of MigrationOperating systemWhen goal is load balancingProcessWhen goal is to reach a particular resource

اسلاید 6: 6What is Migrated?Must destroy the process on the source system and create it on the target systemProcess image and process control block and any links must be moved

اسلاید 7: 7Example of Process Migration

اسلاید 8: 8Example of Process Migration

اسلاید 9: 9What is Migrated?Eager (all):Transfer entire address spaceNo trace of process is left behindIf address space is large and if the process does not need most of it, then this approach my be unnecessarily expensive

اسلاید 10: 10What is Migrated?Precopy: Process continues to execute on the source node while the address space is copiedPages modified on the source during precopy operation have to be copied a second timeReduces the time that a process is frozen and cannot execute during migration

اسلاید 11: 11What is Migrated?Eager (dirty): Transfer only that portion of the address space that is in main memory and have been modifiedAny additional blocks of the virtual address space are transferred on demandThe source machine is involved throughout the life of the process

اسلاید 12: 12What is Migrated?Copy-on-reference: Pages are only brought over when referencedHas lowest initial cost of process migrationFlushing: Pages are cleared from main memory by flushing dirty pages to diskRelieves the source of holding any pages of the migrated process in main memory

اسلاید 13: 13Negotiation of MigrationMigration policy is responsibility of Starter utilityStarter utility is also responsible for long-term scheduling and memory allocationDecision to migrate must be reached jointly by two Starter processes (one on the source and one on the destination)

اسلاید 14: 14

اسلاید 15: 15EvictionDestination system may refuse to accept the migration of a process to itselfIf a workstation is idle, process may have been migrated to itOnce the workstation is active, it may be necessary to evict the migrated processes to provide adequate response time

اسلاید 16: 16Distributed Global StatesOperating system cannot know the current state of all process in the distributed systemA process can only know the current state of all processes on the local systemRemote processes only know state information that is received by messagesThese messages represent the state in the past

اسلاید 17: 17ExampleBank account is distributed over two branchesThe total amount in the account is the sum at each branchAt 3 PM the account balance is determinedMessages are sent to request the information

اسلاید 18: 18Example

اسلاید 19: 19ExampleIf at the time of balance determination, the balance from branch A is in transit to branch BThe result is a false reading

اسلاید 20: 20Example

اسلاید 21: 21ExampleAll messages in transit must be examined at time of observationTotal consists of balance at both branches and amount in message

اسلاید 22: 22ExampleIf clocks at the two branches are not perfectly synchronizedTransfer amount at 3:01 from branch AAmount arrives at branch B at 2:59At 3:00 the amount is counted twice

اسلاید 23: 23Example

اسلاید 24: 24Some TermsChannelExists between two processes if they exchange messagesStateSequence of messages that have been sent and received along channels incident with the process

اسلاید 25: 25Some TermsSnapshotRecords the state of a processGlobal stateThe combined state of all processesDistributed SnapshotA collection of snapshots, one for each process

اسلاید 26: 26Inconsistent Global State

اسلاید 27: 27Consistent Global State

اسلاید 28: 28Distributed Snapshot Algorithm

اسلاید 29: 29Distributed Snapshot AlgorithmProcess 1Outgoing channels2 sent1, 2, 3, 4, 5, 63 sent1, 2, 3, 4, 5, 6Incoming channelsProcess 3Outgoing channels2 sent1, 2, 3, 4, 5, 6, 7, 8Incoming channels1 received1, 2, 3 stored 4, 5, 62 received1, 2, 3 stored 44 received1, 2, 3Process 2Outgoing channels3 sent1, 2, 3, 44 sent1, 2, 3, 4Incoming channels1 received1, 2, 3, 4 stored 5, 63 received1, 2, 3, 4, 5, 6, 7, 8Process 4Outgoing channels3 sent1, 2, 3Incoming channels2 received1, 2 stored 3, 4

اسلاید 30: 30 Distributed Mutual Exclusion ConceptsMutual exclusion must be enforced: only one process at a time is allowed in its critical sectionA process that halts in its noncritical section must do so without interfering with other processesIt must not be possible for a process requiring access to a critical section to be delayed indefinitely: no deadlock or starvation

اسلاید 31: 31Distributed Mutual Exclusion ConceptsWhen no process is in a critical section, any process that requests entry to its critical section must be permitted to enter without delayNo assumptions are made about relative process speeds or number of processorsA process remains inside its critical section for a finite time only

اسلاید 32: 32

اسلاید 33: 33Centralized Algorithm for Mutual ExclusionOne node is designated as the control nodeThis node control access to all shared objectsOnly the control node makes resource-allocation decisionAll necessary information is concentrated in the control nodeIf control node fails, mutual exclusion breaks down

اسلاید 34: 34Distributed AlgorithmAll nodes have equal amount of information, on averageEach node has only a partial picture of the total system and must make decisions based on this informationAll nodes bear equal responsibility for the final decision

اسلاید 35: 35Distributed AlgorithmAll nodes expend equal effort, on average, in effecting a final decisionFailure of a node, in general, does not result in a total system collapseThere exits no systemwide common clock with which to regulate the time of events

اسلاید 36: 36Ordering of EventsEvents must be order to ensure mutual exclusion and avoid deadlockClocks are not synchronizedCommunication delays

اسلاید 37: 37Ordering of EventsNeed to consistently say that one event occurs before another eventMessages are sent when want to enter critical section and when leaving critical sectionTime-stampingOrders events on a distributed systemSystem clock is not used

اسلاید 38: 38Time-StampingEach system on the network maintains a counter which functions as a clockEach site has a numerical identifierWhen a message is received, the receiving system sets is counter to one more than the maximum of its current value and the incoming time-stamp (counter)

اسلاید 39: 39Time-StampingIf two messages have the same time-stamp, they are ordered by the number of their sitesFor this method to work, each message is sent from one process to all other processesEnsures all sites have same ordering of messagesFor mutual exclusion and deadlock all processes must be aware of the situation

اسلاید 40: 40

اسلاید 41: 41

اسلاید 42: 42

اسلاید 43: 43Token-Passing ApproachPass a token among the participating processesThe token is an entity that at any time is held by one processThe process holding the token may enter its critical section without asking permissionWhen a process leaves its critical section, it passes the token to another process

اسلاید 44: 44Deadlock in Resource AllocationMutual exclusionHold and waitNo preemptionCircular wait

اسلاید 45: 45Phantom Deadlock

اسلاید 46: 46Deadlock PreventionCircular-wait condition can be prevented by defining a linear ordering of resource typesHold-and-wait condition can be prevented by requiring that a process request all of its required resource at one time, and blocking the process until all requests can be granted simultaneously

اسلاید 47: 47Deadlock AvoidanceDistributed deadlock avoidance is impracticalEvery node must keep track of the global state of the systemThe process of checking for a safe global state must be mutually exclusiveChecking for safe states involves considerable processing overhead for a distributed system with a large number of processes and resources

اسلاید 48: 48Distributed Deadlock DetectionEach site only knows about its own resourcesDeadlock may involve distributed resourcesCentralized control – one site is responsible for deadlock detectionHierarchical control – lowest node above the nodes involved in deadlockDistributed control – all processes cooperate in the deadlock detection function

اسلاید 49: 49Deadlock in Message CommunicationMutual WaitingDeadlock occurs in message communication when each of a group of processes is waiting for a message from another member of the group and there are no messages in transit

اسلاید 50: 50

اسلاید 51: 51Deadlock in Message CommunicationUnavailability of Message BuffersWell known in packet-switching data networksExample: buffer space for A is filled with packets destined for B. The reverse is true at B.

اسلاید 52: 52Direct Store-and-Forward Deadlock

اسلاید 53: 53Deadlock in Message CommunicationUnavailability of Message BuffersFor each node, the queue to the adjacent node in one direction is full with packets destined for the next node beyond

اسلاید 54: 54

اسلاید 55: 55Structured Buffer Pool

اسلاید 56: 56Finite Channels Lead to Deadlock