11CSE 380Computer Operating SystemsInstructor: Insup LeeUniversity of PennsylvaniaFall 2003Lecture Note: Distributed Systems2Introduction to Distributed Systems Why do we develop distributed systems? availability of powerful yet cheap microprocessors (PCs,workstations), continuing advances in communication technology, What is a distributed system? A distributed system is a collection of independent computers thatappear to the users of the system as a single system. Examples: Network of workstations Distributed manufacturing system (e.g., automated assembly line) Network of branch office computers3Distributed SystemsComparison of three kinds of multiple CPU systems4Advantages of Distributed Systemsover Centralized Systems• Economics: a collection of microprocessors offer a betterprice/performance than mainframes. Low price/performance ratio: costeffective way to increase computing power.• Speed: a distributed system may have more total computing powerthan a mainframe. Ex. 10,000 CPU chips, each running at 50 MIPS.Not possible to build 500,000 MIPS single processor since it wouldrequire 0.002 nsec instruction cycle. Enhanced performance throughload distributing.• Inherent distribution: Some applications are inherently distributed. Ex.a supermarket chain.• Reliability: If one machine crashes, the system as a whole can stillsurvive. Higher availability and improved reliability.• Incremental growth: Computing power can be added in smallincrements. Modular expandability• Another deriving force: the existence of large number of personalcomputers, the need for people to collaborate and share information.25Advantages of Distributed Systemsover Independent PCs Data sharing: allow many users to access to acommon data base Resource Sharing: expensive peripherals likecolor printers Communication: enhance human-to-humancommunication, e.g., email, chat Flexibility: spread the workload over theavailable machines6Disadvantages of Distributed Systems Software: difficult to develop software fordistributed systems Network: saturation, lossy transmissions Security: easy access also applies to secretedata7Software Concepts• Software more important for users• Two types:1. Network Operating Systems2. (True) Distributed Systems8Network Operating Systems• loosely-coupled software on loosely-coupled hardware• A network of workstations connected by LAN• each machine has a high degree of autonomyo rlogin machineo rcp machine1:file1 machine2:file2• Files servers: client and server model• Clients mount directories on file servers• Best known network OS:o Sun’s NFS (network file servers) for shared file systems (Fig.9-11)• a few system-wide requirements: format and meaningof all the messages exchanged39NFS (Network File System) NFS Architecture Server exports directories Clients mount exported directories NSF Protocols For handling mounting For read/write: no open/close, stateless NSF Implementation10(True) Distributed Systems tightly-coupled software on loosely-coupled hardware provide a single-system image or a virtual uniprocessor a single, global interprocess communication mechanism,process management, file system; the same system callinterface everywhere Ideal definition:“ A distributed system runs on a collection of computers that donot have shared memory, yet looks like a single computer to itsusers.”11Design Issues of Distributed Systems• Transparency• Flexibility• Reliability• Performance• Scalability121. Transparency• How to achieve the single-system image, i.e., how tomake a collection of computers appear as a singlecomputer.• Hiding all the distribution from the users as well asthe application programs can be achieved at twolevels:1) hide the distribution from users2) at a lower level, make the system look transparent toprograms.1) and 2) requires uniform interfaces such as access tofiles, communication.4132. Flexibility• Make it easier to change• Monolithic Kernel: systems calls are trapped andexecuted by the kernel. All system calls are servedby the kernel, e.g., UNIX.• Microkernel: provides minimal services.• IPC• some memory management• some low-level process management and scheduling• low-level i/o (E.g., Mach can support multiple filesystems, multiple system interfaces.)143. Reliability• Distributed system should be more reliable thansingle system. Example: 3 machines with .95probability of being up. 1-.05**3 probability of beingup.– Availability: fraction of time the system is usable.Redundancy improves it.– Need to maintain consistency– Need to be secure– Fault tolerance: need to mask failures, recover fromerrors.154. Performance• Without gain on this, why bother with distributedsystems.• Performance loss due to communication delays:– fine-grain parallelism: high degree of interaction– coarse-grain parallelism• Performance loss due to making the system faulttolerant.165. Scalability• Systems grow with time or become obsolete.• Techniques that require resources linearly in terms ofthe size of the system are not scalable. (e.g.,broadcast based query won't work for largedistributed systems.)• Examples of bottleneckso Centralized components: a single mail servero Centralized tables: a single URL address booko Centralized algorithms: routing based on complete information517Distributed Coordination Communication between processes in a distributed system can haveunpredictable delays, processes can fail, messages may be lost Synchronization in distributed systems is harder than in centralizedsystems because the need for distributed algorithms. Properties of distributed algorithms:1 The relevant information is scattered among multiple machines.2 Processes make decisions based only on locally available information.3 A single point of failure in the system should be avoided.4 No common clock or other precise global time source exists. Challenge: How to design schemes so that multiple systems cancoordinate/synchronize to solve problems efficiently?18Why need to synchronize clocks?214421452142 2143214421452146 2147foo.o createdfoo.c modifiedComputer forcompilingComputer foreditingLocal clock timeLocal clock time19Logical and physical clocks How a computer timer works? A counter register and a holding register. The counter is decremented by a quartz crystals oscillator.When it reaches zero, an interrupted is