1CSC 4103 - Operating SystemsSpring 2007Tevfik KoşarLouisiana State UniversityApril 24th, 2007Lecture - XXIIDistributed SystemsMotivation• Distributed system is collection of loosely coupled processors that– do not share memory– interconnected by a communications network• Reasons for distributed systems– Resource sharing• sharing and printing files at remote sites• processing information in a distributed database• using remote specialized hardware devices– Computation speedup – load sharing– Reliability – detect and recover from site failure, function transfer,reintegrate failed site– Communication – message passingA Distributed SystemDistributed-Operating Systems• Users not aware of multiplicity of machines– Access to remote resources similar to access to localresources• Data Migration – transfer data by transferringentire file, or transferring only those portions ofthe file necessary for the immediate task• Computation Migration – transfer thecomputation, rather than the data, across thesystemDistributed-Operating Systems (Cont.)• Process Migration – execute an entire process, or partsof it, at different sites– Load balancing – distribute processes across network to eventhe workload– Computation speedup – subprocesses can run concurrently ondifferent sites– Hardware preference – process execution may requirespecialized processor– Software preference – required software may be available atonly a particular site– Data access – run process remotely, rather than transfer alldata locallyNetwork TopologyRobustness in Distributed Systems• Failure detection• ReconfigurationFailure Detection• Detecting hardware failure is difficult• To detect a link failure, a handshaking protocol can beused• Assume Site A and Site B have established a link– At fixed intervals, each site will exchange an I-am-upmessage indicating that they are up and running• If Site A does not receive a message within the fixedinterval, it assumes either (a) the other site is not up or (b)the message was lost• Site A can now send an Are-you-up? message to Site B• If Site A does not receive a reply, it can repeat themessage or try an alternate route to Site BFailure Detection (cont)• If Site A does not ultimately receive a reply from Site B,it concludes some type of failure has occurred• Types of failures:- Site B is down- The direct link between A and B is down- The alternate link from A to B is down- The message has been lost• However, Site A cannot determine exactly why thefailure has occurredReconfiguration• When Site A determines a failure has occurred, it mustreconfigure the system:1. If the link from A to B has failed, this must bebroadcast to every site in the system2. If a site has failed, every other site must also benotified indicating that the services offered by thefailed site are no longer available• When the link or the site becomes available again, thisinformation must again be broadcast to all other sitesDistributed File Systems• Distributed file system (DFS) – a distributedimplementation of the classical time-sharing model of afile system, where multiple users share files and storageresources• A DFS manages set of dispersed storage devices• Overall storage space managed by a DFS is composed ofdifferent, remotely located, smaller storage spaces• There is usually a correspondence between constituentstorage spaces and sets of filesDFS Structure• Service – software entity running on one or more machinesand providing a particular type of function to a prioriunknown clients• Server – service software running on a single machine• Client – process that can invoke a service using a set ofoperations that forms its client interface• A client interface for a file service is formed by a set ofprimitive file operations (create, delete, read, write)• Client interface of a DFS should be transparent, i.e., notdistinguish between local and remote filesNaming and Transparency• Naming – mapping between logical and physical objects• Multilevel mapping – abstraction of a file that hides thedetails of how and where on the disk the file is actuallystored• A transparent DFS hides the location where in the networkthe file is stored• For a file being replicated in several sites, the mappingreturns a set of the locations of this file’s replicas; boththe existence of multiple copies and their location arehiddenNaming Structures• Location transparency – file name does not reveal thefile’s physical storage location– File name still denotes a specific, although hidden, set ofphysical disk blocks– Convenient way to share data– Can expose correspondence between component units andmachines• Location independence – file name does not need to bechanged when the file’s physical storage location changes– Better file abstraction– Promotes sharing the storage space itself– Separates the naming hierarchy form the storage-deviceshierarchyNaming Schemes — Three Main Approaches• Files named by combination of their host name and localname; guarantees a unique systemwide name– Eg. host:local-name– Not location transparent, nor location independent• Attach remote directories to local directories, giving theappearance of a coherent directory tree; only previouslymounted remote directories can be accessed transparently– Eg. NFS• Total integration of the component file systems– A single global name structure spans all the files in the system– If a server is unavailable, some arbitrary set of directories ondifferent machines also becomes unavailableRemote File Access• Remove-service mechanism is one transfer approach• Reduce network traffic by retaining recently accessed diskblocks in a cache, so that repeated accesses to the sameinformation can be handled locally– If needed data not already cached, a copy of data is broughtfrom the server to the user– Accesses are performed on the cached copy– Files identified with one master copy residing at the servermachine, but copies of (parts of) the file are scattered indifferent caches– Cache-consistency problem – keeping the cached copiesconsistent with the master file• Could be called network virtual memoryCache Location – Disk vs. Main Memory• Advantages of disk caches– More reliable– Cached data kept on disk are still there during recoveryand don’t need to be fetched again• Advantages of main-memory