COMPUTER OPERATING SYSTEMS
COMPUTER OPERATING SYSTEMS CS 2510
Popular in Course
Popular in ComputerScienence
This 11 page Class Notes was uploaded by Jonas Bartell on Monday October 26, 2015. The Class Notes belongs to CS 2510 at University of Pittsburgh taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/229375/cs-2510-university-of-pittsburgh in ComputerScienence at University of Pittsburgh.
Reviews for COMPUTER OPERATING SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/26/15
Replica Placement Model We consider objects and don t worry whether they contain just data or code or both Distinguish different processes A process is capable of hosting a replica of an object or data Permanent replicas Processmachine always having a replica Serverinitiated replica Process that can dynamically host a replica on request of another server in the data store Clientinitiated replica Process that can dynamically host a replica on request of a client client cache Replica Placement 1 x 9 Serverinitiated replication VA xx 7quot Clientinitiated replication Permanent Serverinitiated replicas The logical organization of different kinds of copies of a data store into three concentric rings Examples web servers file servers multicast trees ServerInitiated Replicas CZ Server without 9 copy of file F Server with P K copy of F Client c1 Q File F Server Q counts access from C1 and 02 as if they would come from Keep track of access counts per le aggregated by considering server closest to requesting clients Number of accesses drops below threshold D gtdrop le Number of accesses exceeds threshold R gtreplicate le Number of access between D and R gtmigrate le ClientInitiated Replicas More like a client cache 7 Keep it on disk 7 Keep it in memory 7 How much space to use 7 How long to keep copyreplica 7 How to detect data is stale Readonly les work best Sharing data among client processes may be good Sharing space is essential Update Propagation 13 Fmpagate umy nuh muunmwhdauun urupdate utten used fur mehes Transfer data r m Dpy m anumerdstnbuted databases FmpagzteLheupdateoptzvmtontu uthereupresa1su Elledacnv repllmuun ohsmm39nn Nu angle appmachls the best but depends hghly un amiable bandwidth and radrlurwnle mum at rephms Update Propagation 23 Fush ng updates sa39Va39rmmate d appruaeh m whmh update 15 pmpagated regardless whether target asked fur rt Puurng updates euen Hmuated appruaeh m wmeh euent requests tu be updated Nan se 1 Re pansetme anteater Update Propagation 33 Observation We can dynamically switch between pulling and pushing using leases A contract in which the server promises to push updates to the client until the lease expires Issue Make lease expiration time dependent on system s behavior adaptive leases Agebased leases An object that hasn t changed for a long time will not change in the near future so provide a longlasting lease Renewalfrequency based leases The more often a client requests a speci c object the longer the expiration time for that client for that object will be Statebased leases The more loaded a server is the shorter the expiration times become Question Why are we doing all this Epidemic Algorithms Basic idea Assume there are no writeiwrite con icts Update operations are initially performed at one or only a few replicas A replica passes its updated state to a limited number of neighbors Update propagation is lazy ie not immediate Eventually each update should reach every replica Anti entropy Each replica regularly chooses another replica at random and exchanges state differences leading to identical states at both afterwards Gossiping A replica which has just been updated ie has been contaminated tells a number of other replicas about its update contaminating them as well System Model We consider a collection servers each storing a number of objects Each object O has a primary server at which updates for O are always initiated avoiding writewrite con icts An update of object O at server S is always timestamped the value of O at S is denoted VALOS TOS denotes the timestamp of the value of object O at server S AntiEntropy Basic issue When a server S contacts another server S to exchange state information three different strategies can be followed Push S only forwards all its updates to S if TOS lt TOS then VALOS lt VALOS Pull S only fetched updates from S if TOS gt TOS then VALOS lt VALOS Push Pull S and S exchange their updates by pushing and pulling values Observation if each server periodically randomly chooses another server for exchanging updates an update is propagated in Olog 7 time units Question why is pushing alone not ef cient when many servers have already been updated G0331p1ng Basie model A server 5 havrng an update to report conLac other servers If a server rs contacted to whlch the update has already propagated 5 stops eontaetrng other server w th probabrlrty lk Ila rs the Eraetron of rgnorant servers r e whlch are unaware olthe update rt can be shown that vvrth rnany servers 5 gtwltle observatron Ifwe really have to ensure that all servers are eventually updated gosslplng alone rs not enougn Deleting Values em We aannatrernave an ald value fmm a 5m expert the renaval ta prap due trrne usrng eprdenra al e and agate lnstead rnere renaval wlll be undane rn g nthrns Solution Remaval has ta be regtsteed as a speclal update by rnsetrng a death cem mle Nextproblern When ta rernave a death aetr aate rtrs nat allawed ta stay fareve Run a glahal alganthrnta detect whether the rernaval rs kmwn eveyvvhee andthen aallett the death aertr aates laaks llke garbage sallettran Assume death cetr cates prap agate rn t rnrte trrne and ass crate a rnarnrnurnlrfeurne faraaetrt39raateaanhe dane atnsk afnatreaahrng all smels Nam rt rs neaessarythat a renaval attually reaches all servers Question What s the saalahrlrty pmblem heren Consistency Protocols Consistency protocol describes the implementation of a speci c consistency model We will concentrate only on sequential consistency Primarybased protocols Replicatedwrite protocols Cachecoherence protocols PrimaryBased Protocols 14 All read and write operations go to server Example used in traditional clientserver systems that do not support replication Client Client Single server for 39tem X Backup server W1 W4 R1 R4 Vl W2 d R2 L Ejantj lt7 W3 R3 Data store W1 Write request R1 Read request W2 Forward request to server for x R2 Forward request to server for x W3 Acknowledge write completed R3 Return response W4 Acknowledge write completed R4 Return response PrimaryBased Protocols 24 Primarybackup protocol writes are typically forwarded to server Client Client Primary server for item X Backup sener W1 Write request R1 Read request W2 Forward request to primary R2 Response to read W3 Tell backups to update W4 Acknowledge update W5 Acknowledge write completed Example Traditionally applied in distributed databases and le systems that require a high degree of fault tolerance Replicas are often placed on same LAN PrimaryBased Protocols 34 Primarybased localwrite protocol migrate the data do not replace it Client Current server New server for item x for item x B Eaj i 8 Data store 1 Read or write request 2 Forward request to current server for x 3 Move item x to client39s server 4 Return result of operation on client39s server Example Establishes only a fully distributed nonreplicated data store Useful when writes are expected to come in series from the same client eg mobile computing without replication PrimaryBased Protocols 44 Primarybackup protocol with local writes replicate data only for reading Client Client Old primary New primary for item x for item x Backup server R1 R2 W1 W3 A L lk W5 W5 W Al W4 Data store W5 W2 W4 W1 Write request R1 Read request W2 Move item x to new primary R2 Response to read W3 Acknowledge write completed W4 Tell backups to update W5 Acknowledge update Example Distributed shared memory systems but also mobile computing in disconnected mode ship all relevant les to user before disconnecting and update later on ReplicatedWrite Protocolsl2 0 Active replication Updates are forwarded to multiple replicas where they are carried out 0 One problem to deal with replicated invocations Client replicates 39 invocation request Object receives the same invocation three times 1 All replicas see the same invocation Replicated object ReplicatedWrite Protocols 22 Replicated invocations Centralized Solution Assign a coordinator on each side client and server which ensures that only one invocation a and one reply is send b Coordinator Coordinator of object B of object C Client replicates invocation request 1 Triple Modular Redundancy Simple to implement Vote on all three results Majority 50 1 wins Request is replicated to all servers Request Al A2 A3 QuorumBased Protocols Quorumbased protocols Ensure that each operation is carried out in such a way that a majority vote is established distinguish read quorum and write quorum Read quorum Example Lazy Replication Basic model number of replica servers jointly implement a causalconsistent data store 0 Clients normally talk to front ends which maintain data to ensure causal consistency Clients F W up Write queue Read queue iquot 3 EU UH Pending 1 D D D uij 1 Local serve request 1 E353 i k H 1 r l j I l l i i I Distributed data store