31Load ControlFundamental tradeoffHigh multiprogramming levelIssues! What criterion should be used to determine when to increase ordecrease the MPL?! Which task should be swapped out if the MPL must be reduced?Low paging overhead!MPLmin = 1 processminimum number of frames required for a process to executenumber of page frames!MPLmax =32Load ControlHow not to do it: Base load control on CPU utilization! Assume memory is nearly full! A chain of page faults occur! A queue of processes forms atthe paging device! CPU utilization fallsOperating system increases MPL! New processes fault, taking memory away from existing processesCPU utilization goes to 0, the OS increases the MPL further...System is thrashing — spending all of its time pagingI/ODeviceI/ODevice...PagingDevicePagingDeviceCPUCPU33Better criteria for load control: Adjust MPL so that:! mean time between page faults (MTBF) = page fault service time(PFST)! ! WSi = size of memory1.0CPUUtilizationMultiprogramming LevelThrashing can be ameliorated by local page replacementLoad ControlThrashingNmaxNI/O-BALANCEMTBFPFST1.034Load ControlThrashingWhen the multiprogramming level should bedecreased, which process should be swappedout?SuspendedSuspendedsuspendedqueuereadyqueuesemaphore/condition queuesWaitingWaitingRunningRunningReadyReady?Paging DiskPhysicalMemory! Lowest priority process?! Smallest process?! Largest process?! Oldest process?! Faulting process?Saving the worldbefore bedtimeTwo Generals’ ProblemS.P.Q.RS.P.Q.R• Romans win if attack simultaneously• Otherwise, Barbarians win• Romans must coordinate attackTwo Generals’ ProblemS.P.Q.RS.P.Q.R• only communication is by messenger• messengers must sneak through the valleyProblem:Design a protocol to save Western Civilization(i.e. one that ensures that Romans always attack simultaneously)• they don’t always make itClaim There is no non-trivial protocol that guarantees that the Romans will always attack simultaneously Two Generals’ ProblemProof: Let P be shortest such protocol• consider last message mlast• P must work if mlast never arrives• so don’t send it• but now we have a new protocol shorter than P !Fundamental Limitation: Solution needs• unbounded number of messages or• guaranteed message deliveryOtherwise, attack may never take place!Atomic CommitThe objectivePreserve data consistency for distributed transactions in the presence of failures ModelFor each distributed transaction T:one coordinatora set of participantsCoordinator knows participants; participants don’t necessarily know each otherEach process has access to a Distributed Transaction Log (DT Log) on stable storageThe setupEach process pi has an input value votei:votei {Yes, No}Each process pi has output value decisioni:decisioni {Commit,
View Full Document
Unlocking...