Distributed and Concurrent Systems PDF

# Distributed and Concurrent Systems ## Introduction ### Fundamental of Distributed Computing A distributed system is a collection of autonomous computers linked by a computer network and equipped with distributed system software. This software enables the computers to coordinate their activities...

# Distributed and Concurrent Systems ## Introduction ### Fundamental of Distributed Computing A distributed system is a collection of autonomous computers linked by a computer network and equipped with distributed system software. This software enables the computers to coordinate their activities and share resources such as hardware, software, and data. **Working of DS** * Each computer has: - A local operating system. - A middle-ware service. - A distributed application layer. * They are connected via a network. **Characteristics of D.S** 1. **Resource sharing:** The ability to use any hardware, software, or data anywhere in the system. 2. **Openness:** Concerned with extensions and improvements of D.S. 3. **Concurrency:** 4. **Scalability:** The scalability of the system. 5. **Fault tolerance:** It increases the overall reliability of the system. 6. **Transparency:** Hides the complexity of D.s to the users and application programs. **Applications of Dis** 1. **Finance & Commerce:** - E.g. E-commerce (Amazon, eBay, online banking) 2. **The Information Society:** - Search engines. - Wikipedia. - Social networking. 3. **Creative Industries & Entertainment:** - Online gaming. - Music. - YouTube. 4. **Healthcare:** - Online patient records. - Health informatics. 5. **Education:** - E-learning. 6. **Transport & Logistics:** - GPS. - Google maps. 7. **Science** 8. **Environment Management & Sensor Tech** **Example of Distributed System** A nationalized bank with multiple branch offices, where each branch has: - A teller machine. - A local area network (LAN). - Branch data stored in a database. - Branch backup data. **Requirements of DS** 1. **Security & Reliability** 2. **Consistency of Replicate Data** 3. **Concurrent Transaction** 4. **Fault Tolerance** **Architecture for Distributed System** 1. **Shared Memory Architecture** - Tightly coupled systems. - Easier to program. 2. **Distributed Memory Architecture** - Loosely coupled systems. **Shared Memory Architecture** * Multiple processors share the same memory space. * Inter-process communication is fast and efficient. * The communication channel is a shared memory. * It is a "Tightly coupled approach". **Distributed Memory Architecture** * Each processor has its own local memory space. * Inter-process communication requires sending messages through the network. * It is a "Loosely coupled approach". **Advantages of Distributed Systems** * Inherently distributed applications. * Information sharing among geographically distributed users. * Resource sharing. * Better price-performance ratio. * Shorter response time & higher throughput. * Higher reliability and availability against component failure. * Extensibility & incremental growth. * Better flexibility. **Disadvantages of Distributed Systems** * Relevant software does not exist currently, * Security poses a problem due to easy access to data. * Network saturation may cause a hurdle in data transfer. **Issues in Designing Distributed Systems** 1. **Transparency** 2. **Flexibility** 3. **Reliability** 4. **Performance** 5. **Scalability** 6. **Security** ## Distributed Computing Models * **Fundamental Models:** Based on some fundamental properties, such as characteristics, failures, and security. - Interaction Model - Failure Model - Security Model * **Architectural Models:** Based on an architectural style. - Client-Server Model - Peer-to-Peer Model ## Architectural Model * Deals with the organization of components across the network of computers and their interrelationship. * There are two main architectural models: - Client-server Model - Peer-to-peer Model ## Client-Server Model * The most important and widely used distributed system architecture. * Client and server roles are assigned and changeable. * **How it works:** - The client sends a request to the server. - The server processes the request and sends a reply back to the client. **Client Invoke Individual Server** * The client makes a request to the main server. * The main server delegates requests to slaves according to some predefined strategy. ## Peer-to-Peer Model * Unlike the client-server model, the peer-to-peer model does not distinguish between client and server. * Each node can either be a client or a server depending on whether the node is requesting or providing the service. * Each node is considered a peer. * The pattern of communication between peers depends entirely on the application requirements. * Each object is replicated in several computers to distribute the load and provide resilience in the event of disconnection of individual computers. ## Fundamental Models **1. Interaction Model** * Computation occurs within processes. * Processes interact by passing messages, resulting in: - Communication (information flow). - Coordination (synchronization and ordering of activities) between processes. * This model reflects the fact that communication takes place with delays. <start_of_image>* **Performance of communication channel:** - Latency (message, network, system). - Bandwidth. - Jitter. * **Two variants of the interaction model:** - **Synchronous DS:** - Processes execute in a known lower/upper bounded time. - Messages are received within a known bounded time. - Known local clock's drift rate. - **Asynchronous DS:** - No bounds on: - Process execution speed. - Message transmission delay. - Clock drift rate. **2. Failure Model** * Failure model defines and classifies faults. * It is important to understand the kinds of failures that may occur in a system. * **Types of faults:** - **Fail-stop:** A process halts and remains halted. Other processes can detect that the process has failed. - **Crash:** A process halts and remains halted. other processes may not be able to detect this state. - **Omission:** A message inserted in an outgoing message buffer never arrives at the other end. Incoming messages may also be omitted. - **Arbitrary:** Process/channel exhibits arbitrary behavior. It may send/transmit arbitrary messages at arbitrary times. Commit missions, a process may stop or take an incorrect step. - **Timing Failure:** Clock drift exceeds allowable bounds. **3. Security Model** * There are several potential threats a system designer needs to be aware of: - **Threats to processes:** An attacker sends a request or response using a false identity. - **Threats to communication channels:** An attacker may intercept messages and save them. - **Denial of service:** An attacker may overload a server by making excessive requests. * **Cryptography and authentication are often used to provide security.** ## Software Concepts * **Network operating system (NOS):** Build using a distributed system from a network of workstations connected by a high-speed network. * **Distributed operating system (DOS):** Each workstation is an independent computer with its own operating system, memory, and other resources like hard disk, file system, and databases. It follows the loosely coupled architecture pattern, which allows the user to use services provided by the local machine itself. - **Examples:** - **Remote Login:** Where a user workstation is used to log in to the remote server and execute commands over the network. - **Centralized File Storage Systems:** It has scalability features where large numbers of resources and users are supported but it fails to provide a single coherent view. * **Multi-process, data sharing system, middleware OS:** Enables a distributed system to behave like a virtual uniprocessor even though the system operates on a collection of uniprocessors. - **Characteristics:** - It enables inter-process communication. - It provides uniform process management mechanisms. - It provides uniform and visible file systems. - It has identical kernel implementation. - It uses local control of the machine. - It handles scheduling issues. - It communicates with all the computers using message passing interface (MPI). - **It follows a tightly coupled architecture pattern. It uses queues to manage message loss between sender and receiver computers.** - **Example:** Automated banking system, railway reservation system, etc. - **Disadvantages:** - It has a problem of scalability as it supports only a limited number of independent computers with shared resources. - There is a need to define message passing semantics prior to the execution of messages. ## Communication in Distributed Systems * **Issues in communication:** - **Message-oriented communication** - **Remote Procedure Calls (RPC)** - **RMI (Remote Method Invocation):** RMI is essentially RPC, but specific to remote objects. - **Stream-oriented communication** ## Communication Protocol * **Rules on communication.** * Protocols could be "connection oriented" or "connectionless". ## OSI Layers * The Open Systems Interconnection (OSI) model is a conceptual framework that defines a networking communications model. * **7 Layers:** 1. **Physical Layer:** Responsible for the movement of individual bits from one node to the next. 2. **Data Link Layer:** Responsible for moving frames from one node to the next and performs error detection and correction. 3. **Network Layer:** Responsible for the delivery of individual packets from a source host to a destination host. 4. **Transport Layer:** Responsible for the delivery of messages from one process to another. - **Protocols:** - **TCP (Transmission Control Protocol):** Connections oriented. - **UDP (User Datagram Protocol):** Connectionless. 5. **Session Layer:** Responsible for dialog control and synchronization. 6. **Presentation Layer:** Responsible for translation, compression, and encryption. 7. **Application Layer:** This layer provides network services to applications. ## Remote Procedure Call (RPC) * **RPC is a protocol that one program can use to request a service from a program located in another computer on a network, without having to understand the network's details.** * A procedure call is also called as a function call or subroutine call. * **RPC uses the client-server model:** - The client requests a remote procedure to be executed. - The server executes the procedure and sends back the results to the client. * **RPC includes mainly 5 elements:** - **Client:** The client initiates an RPC call. - **Client Stub:** A piece of code which converts parameters and sends a message to the server, and vice versa. - **RPC Runtime:** Handles the transmission of messages between client and server. - **Server Stub:** Unpacks the call request and makes a normal call to invoke the appropriate procedure in the server. - **Server:** Executes the remote procedure and returns the results. * **Steps of a Remote Procedure Call:** 1. The client procedure calls the client stub in a normal way. 2. The client stub builds the message and calls the local OS. 3. The client's OS sends the message to the remote OS. 4. The remote OS gives the message to the server stub. 5. The server stub unpacks parameters and calls the server. 6. The server does the work and returns the result to the stub. 7. The server stub packs the result in a message back to the client's OS, and calls the local OS. 8. The client’s OS gives the message to the client stub. 9. The client stub unpacks the result and returns to the client. * **Example of an RPC:** Client machine: - The client process calls the procedure "add" with arguments. - The client stub builds the message and sends it to the server. Server machine: - The server receives the message. - The server stub unpacks the message. - The server process executes the procedure "add". - The server stub packs the result into a message and sends it back to the client. * **Implementation issues in Remote Procedure Call (RPC):** - **RPC Protocols:** The first issue is the choice of the RPC protocol. - **Connection-oriented protocols:** - The client is bound to the server, and a connection is established between them. - The advantage: Communication becomes much easier. - The disadvantage: Especially over a LAN, it is performance loss. - **Connectionless protocols:** - **IP (Internet Protocol) & UDP:** Easy to use and fit in well with existing Unix systems and networks, such as the internet. The downside is performance loss. - **Packet and message length:** Doing an RPC has a large, fixed overhead, independent of the amount of data sent. Thus, reading a 64k file in a single 64k RPC is vastly more efficient than reading it in 64 1k RPCs. - **It is therefore important that the protocol and network should allow large transmissions.** - **Some RPC systems are limited to small sizes.** - **In addition, many networks cannot handle large packets, so a single RPC call will have to be split over multiple packets, causing extra overhead.** * **Example:** The client wants to write a 4k block of data to a file server, but the system cannot handle packets longer than 1k. - The client sends the data in 4 packets, each with 1k of data. - The server acknowledges receipt of each packet. - The server then combines the 4 packets into a 4k block. * **Advantages of RPC:** - **Client-server model:** Simple and efficient way to build distributed systems. - **Flexibility:** RPC allows for complex communication patterns, such as asynchronous communication. - **Performance:** RPC can be optimized for performance, especially over a LAN. - **Security:** RPC can be secured using various security protocols. * **Disadvantages of RPC:** - **Complexity:** RPC can be complex to implement, especially for large-scale distributed systems. - **Performance:** RPC can be slow, especially over a WAN. - **Security:** RPC can be vulnerable to security attacks. ## RMI Remote Method Invocation * **RMI is an API that provides a mechanism to create distributed applications in Java.** * It allows an object to invoke methods on an object running in another JVM. * RMI provides remote communication between the applications using two objects: stub and skeleton. **RMI System Layers** * **Stub/Skeleton Layer:** - The stub is an object that acts as a gateway for the client side. - All outgoing requests are routed through it. * **Remote Reference Layer:** - Provides a communication channel between the client and server for invoking remote methods. * **Transport Layer:** Provides the underlying network communication mechanism for transmitting data between client and server. **Understanding Stub and Skeleton** * **Remote Object:** An object whose method can be invoked from another JVM. * **Stub:** - It is an object that acts as a gateway for the client side. - All outgoing requests are routed through it. - It resides in the client side and represents the remote object. * **Skeleton:** - It is an object that acts as a gateway for the server side of the object. - All incoming requests are routed through it. - When the skeleton receives an incoming request, it does the following tasks: - Reads the parameters from the remote object. - Invokes the method on the actual remote object. - Writes and transmits the result back to the client. * **Working of an RMI Application** 1. When the client makes a call to the remote object, it is received by the stub, which eventually passes this request to the remote reference layer (RRL). 2. When the client-side RRL receives the request, it invokes a method called "invoke()" of the object "remoteRef()". It passes the request to the RRL on the server side. 3. When the RRL on the server side passes the request to the skeleton (proxy on the server), it finally invokes the required object on the server. 4. The result is passed all the way back to the client. * **Java RMI Example** **Steps to write an RMI program:** 1. **Create the remote interface:** For creating the remote interface, extend the Remote interface and declare the remote exception with all methods of the remote interface. ```java import java.rmi.*; public interface Adder extends Remote { public int add(int int1, int int2) throws RemoteException; } ``` 2. **Provide the implementation of the remote Interface:** For providing implementation, we need to do either one of the following: - Extend the UnicastRemoteObject class. - Use the "exportObject()" method. ```java import java.rmi.*; import java.rmi.server.*; public class AdderRemote extends UnicastRemoteObject implements Adder { public AdderRemote() throws RemoteException { super(); } public int add(int int1, int int2) { return int1 + int2; } } ``` 3. **Compile the implementation class and create the stub and skeleton object using the "rmic" tool:** The "rmic" tool invokes the RMI compiler and creates the stub and skeleton object. ```bash rmic AdderRemote ``` 4. **Start the registry service by the "rmiregistry" tool:** Now start the service using "rmiregistry" tool. If you do not specify port no., it uses a default port now. ```bash rmiregistry 8000 ``` 5. **Create and run the server application:** Start the server application that implements the remote interface. 6. **Create and run the client application:** Start the client application that makes calls to the remote server. * **Goals of RMI:** - Minimize the complexity of applications. - Preserve type safety. - Distributed garbage collection. - Minimize the difference between working with local and remote objects. ## Message Passing * **The formal model of distributed message passing systems has two timing models:** - **Synchronous:** All processes execute in lockstep. - **Asynchronous:** No assumption is made about the relative speeds of processes. * **In message passing systems, processes communicate by sending or receiving messages over a communication channel.** * **The pattern of connections provided by the channels describes the topology of the system.** * **Collection of channels - network.** * **Message Passing Model Algorithm:** 1. Let us consider an algorithm consisting of n processes. 2. Bidirectional point-to-point channels. 3. Each processor labels its incident channels 1, 2, 3, ... It might not know who is at the other end. ## Parallel Virtual Machine (PVM) * **PVM is a software package that allows a heterogeneous collection of workstations (host pool) to function as a single, high-performance parallel machine (virtual).** * **PVM, through its virtual machine, provides a simple, yet useful distributed operating system.** * **It has a daemon running on all computers making up the virtual machine.** * **PVM programming Model:** - **PVM application consists of a collection of cooperating tasks, each of which is responsible for some workload of a big problem.** - **PVM is inherently dynamic in nature, and it has a rich set of resource control functions. Hosts can be added or deleted.** - **Functions:** - **Load balancing:** Distributes workload among processors. - **Task migration:** Moves tasks between processors. - **Fault tolerance:** Allows the software to continue operating even if a processor fails. - **Fault Tolerance:** PVM supports a basic fault notification scheme. It does not automatically recover an application after a crash, but it does provide notification primitives to allow fault-tolerant applications to be built. - **The virtual machine is dynamically reconfigurable.** - **A PVM can recover from the loss of any foreign PVM except the master. The master never crashes.** * **PVM & MPI:** | Feature | PVM | MPI | |---|---|---| | Virtual machine concept | Yes | No | | Message passing | Simple | Rich | | Communication topology | Unspecified | Support logical communication topology | | Interoperate across architectural boundaries | Yes | Some realizations do not | | Portability over performance | Yes | Performance over flexibility | | Resource and process control | Yes | Primarily concerned with messaging | | Fault tolerance | Robust | More susceptible to faults | * **PVM is better for:** - Heterogeneous clusters - Resource and process control - When the size of the cluster and the time for program execution are great. * **MPI is better for:** - Supercomputers (PVM is not supported) - Man performance - Applications that need rich message support. ## Processes and Threads * **Process:** A program in execution. - **Execution content:** - Program counter (PC) - Stack pointer (SP) - Data register - **An instance of a computer program that is being executed on one of the operating system’s (virtual) processors.** - A process has a virtual address space, cache, and code. - It has open handles to system objects, a security context, a unique identifier, environment variables, a priority class and at least 1 thread of execution. * **Threads:** Lightweight process. - **A thread is a path of execution within a process.** - A thread executes its own piece of code independently from other threads. - **A way of process to split itself into 2 or more threads**. - **A thread maintains only the minimum information to allow a CPU to be shared by several threads.** - **Execution content:** - Program counter (PC) - Stack pointer (SP) - Data register * **Process vs. Thread:** - **Process:** Unit of allocation. - Resources - Privileges - etc. - **Thread:** Unit of execution. - PC - SP - Registers - **Each process has one or more threads.** - **Each thread belongs to one process.** - **Processes:** - Inter-process communication is expensive. - Secure. - **Threads:** - Inter-thread communication is cheap. - Not Secure. * **Threads in Distributed Systems** - Used to express communication in the form of multiple logical connections at the same time. - An important property of threads is that they can provide a convenient means of allowing blocking system calls without blocking the entire process in which the thread is running. - A main contribution of threads in DS is that they allow clients and servers to be constructed so that communication and local processing can overlap, resulting in a high level of performance. * **Attractive to use in distributed systems:** - **Multithreaded client:** E.g., Web browser. - **Multithreaded server:** E.g., Web server. * **Can be used to hide delays/latencies in network communication by initiating communication and immediately proceeding with something else.** * **Example:** Web browser (such as IE, which is multithreaded.) - A web browser can start up several threads, like fetching the main HTML file and images on the page, animations, applets, etc. * **Multithreaded server:** Organized in a dispatcher/worker model. - **Server implementation schema:** - Single-threaded server. - Multi-threaded server. - Finite-state machine server. - Use non-blocking system calls. * **A Multithreaded server organized in a dispatcher/worker model:** - Requests coming in from the network are dispatched to a worker thread. - Each request is given to a worker thread in the operating system. * **Characteristics:** - **Threads →** Parallelism, blocking system calls. - **Single-threaded processes →** Non-parallelism, blocking system calls. - **Finite-state machine →** Parallelism, non-blocking system calls. * **Three ways to construct a server:** - **Blocking System Calls:** Make programming easier and improves performance. - **Single-threaded Server:** Retains the ease and simplicity of blocking system calls, but gives up performance. - **Finite-state machine approach:** Achieves high performance through parallelism and use of non-blocking calls. This is hard to program. # Distributed Mutual Exclusion * **What is mutual exclusion?** - When a process is accessing shared data, the process is said to be in a CS (critical section). - No two processes can be in the same CS at the same time. This is called mutual exclusion. * **Distributed mutual exclusion:** - Assumes there is an agreement on how a resource is identified (poss identifier with requests). - Create an algorithm to allow a process to obtain exclusive access to a resource. - Different algorithms based on message passing to implement mutual exclusion in distributed systems are: - Centralized Algorithm - Token Ring Algorithm - Distributed Algorithm # Deadlock * **Deadlock problem:** There are 2 processes sharing the same resource but effectively preventing each other from accessing it. - **Deadlock:** Processes are waiting for a resource held by another process, so they are not able to progress and end up in a circular wait. * **Various methods to handle deadlock:** - **Deadlock ignorance:** Ignore the possibility of deadlock. Risky. - **Deadlock prevention:** Prevent deadlock by ensuring that the conditions for deadlock are not met. - **Deadlock avoidance:** Avoid deadlock by ensuring that the system will not enter a state where deadlock is possible. - **Deadlock detection and recovery: Detect a deadlock after such an event happens and recover the system to a state where it is able to work.** #