UNIT – 2

Unit-02/Lecture-01

Distributed Share Memory (DSM)

A distributed shared memory is a mechanism allowing end-users' processes to access shared data without using inter-process communications. In other words, the goal of a DSM system is to make inter-process communications transparent to end-users. Both hardware and software implementations have been proposed in the literature. From a programming point of view, two approaches have been studied:

Shared virtual memory: This notion is very similar to the well-known concept of paged virtual memory implemented in mono-processor systems. The basic idea is to group all distributed memories together into a single wide address space. Drawbacks: such systems do not allow to take into account the semantics of shared data: the data granularity is arbitrarily fixed to some page size whatever the type and the actual size of the shared data might be. The programmer has no means to provide information about these data.

Object DSM: in that class of approaches, shared data are objects i.e. variables with access functions. In his applications, the user has only to define which data (objects) are shared. The whole management of the shared objects (creation, access, modification) is handled by the DSM system. In opposite of SVM systems which work at operating system layer, objects DSM systems actually propose a programming model alternative to the classical message-passing.

In any case, implementing a DSM system implies to address problems of data location, data access, sharing and locking of data, data coherence. Such problems are not specific to parallelism but have connections with distributed or replicated databases management systems (transactional model), networks (data migrations), uniprocessor operating systems (concurrent programming), distributed systems.

DSM Architecture

· Each node of the system consist of one or more CPUs and memory unit

· Nodes are connected by high speed communication network

· Simple message passing system for nodes to exchange information

· Main memory of individual nodes is used to cache pieces of shared memory space

· Memory mapping manager routine maps local memory to shared virtual memory

· Shared memory space is partitioned into blocks

· Shared memory of DSM exist only virtually

· Data caching is used in DSM system to reduce network latency

· The basic unit of caching is a memory block

· The missing block is migrate from the remote node to the client process’s node and operating system maps into the application’s address space

· Data block keep migrating from one node to another on demand but no communication is visible to the user processes

· If data is not available in local memory network block fault is generated.

……….…Reference P.K.SINHA,Distributed Operating System,233}

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	Explain the different architecture of distributed share memory?	Dec2011	7
Q.2	What is Distributed Shared Memory (DSM)? Describe its architecture.	Dec2014	7

Unit-02/Lecture-02

Design & Implementations issues In DSM System

1. Granularity: Granularity refers to the block size of DSM. The unit of sharing and the unit of data transfer across the network when a network block fault occurs. Possible unit are a few word , a page or a few pages

2. Structure of Shared memory: Structure refers to the layout of the shared data in memory Dependent on the type of applications that the DSM system is intended to support

3. Memory coherence and access synchronization: In a DSM system that allows replication of shared data item, copies of shared data item may simultaneously be available in the main memories of a number of nodes. To solve the memory coherence problem that deal with the consistency of a piece of shared data lying in the main memories of two or more nodes

4. Data location and access: To share data in a DSM, should be possible to locate and retrieve the data accessed by a user process.

5. Replacement strategy: If the local memory of a node is full, a cache miss at that node implies not only a fetch of accessed data block from a remote node but also a replacement Data block must be replaced by the new data block

6. Thrashing: Data block migrate between nodes on demand. Therefore if two nodes compete for write access to a single data item the corresponding data block may be transferred back.

7. Heterogeneity: The DSM system built for homogeneous system need not address the heterogeneity issue

Structure of Share Memory Space

1. No structuring

The shared memory space is simply a linear array of words:

Advantage:

· Choose any suitable page size as the unit of sharing and a fixed grain size may and be used for all application

· Simple and easy to design such a DSM system

2. Structuring by data type

· The shared memory space is structured either as a collection of objects or collection of variables in the source language.

· The granularity in such DSM system is an object or a variable

· DSM system use variable grain size to match the size of the object/variable being accessed by the application

3. Structuring as a database

· Structure the shared memory like a database

· Shared memory space is ordered as an associative memory called tuple space

· To perform update old data item in the DSM are replaced by new data item

· Processes select tuples by specifying the number of their fields and their values or type

· Access to shared data is nontransparent. Most system they are transparent

………….…Reference P.K.SINHA,Distributed Operating System,237}

Unit-02/Lecture-03

Consistency Model

A consistency model basically refers to the degree of consistency that has to be maintained for the shared memory data

Consistency ModelsTypes:

· Strict Consistency model

· Sequential Consistency model

· Causal consistency model

· Pipelined Random Access Memory consistency model(PRAM)

· Processor Consistency model

· Weak consistency model

· Release consistency model

1. Strict Consistency model:

§ This is the strongest form of memory coherence having the most stringent consistency requirement

§ Value returned by a read operation on a memory address is always same as the value written by the most recent write operation to that address

§ All writes instantaneously become visible to all processes

2. Sequential Consistency model:

§ A shared memory system is said to support the sequential consistency model if all processes see the same order

§ If the three operations read(r1), write(w1), read(r2) are performed on a memory location in that order

§ Any of the orderings (r1, w1, r2), (r1, r2, w1), (w1, r1, r2), (w1, r2, r1), (r2, r1, w1), (r2, w1, r1) is acceptable provided all processes see the same ordering

3. Causal consistency model:

§ All processes see only those memory reference operations in the correct order that are potentially causally related

§ Memory reference operations not related may be seen by different processes in different order

§ Memory reference operation is said to be related to another memory reference operation if one might have been influenced by the other

§ Maintaining dependency graphs for memory access operations

4. Pipelined Random Access Memory consistency model(PRAM):

§ Provides a weaker consistency semantics than the above described consistency model

§ Ensures that all write operations performed by a single process are seen by all other processes in the order in which they were performed

§ All write operations performed by a single process are in a pipeline

§ Write operations performed by different processes can be seen by different processes in different order

5. Processor Consistency model:

§ Very similar to PRAM model with additional restriction of memory coherence

§ Memory coherence means that for any memory location all processes agree on the same order of all write operations performed on the same memory location (no matter by which process they are performed) are seen by all processes in the same order.

§ If w12 and w22 are write operations for writing the same memory location x, all processes must see them in the same order- w12 before w22 or w22 before w12

§ Processes P3 and P4 must see in the same order, which may be either [(w11,w12), (w21,w22)] or [(w21,w22), (w11,w12)]

6. Weak consistency model:

§ Common characteristics to many application:

a) It is not necessary to show the change in memory done by every write operation to other processes eg. when a process executes in a critical section

b) Isolated accesses to shared variable are rare

§ Better performance can be achieved if consistency is enforced on a group of memory reference operations rather than on individual memory reference operations

§ DSM system that support the weak consistency model uses a special variable called a synchronization variable

7. Release consistency model:

§ Enhancement of weak consistency model

§ Use of two synchronization variables-

a) Acquire (used to tell the system it is entering CR)

b) Release (used to tell the system it has just exited CR)

§ Acquire results in propagating changes made by other nodes to processs node

§ Release results in propagating changes made by the process to other node

§ Barrier defines the end of a phase of execution of a group of concurrently executing processes

§ Barrier can be implemented by using a centralized barrier server

………….…Reference P.K.SINHA,Distributed Operating System,238}

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	Explain various consistency models in detail?	Dec.2012	10

Unit-02/Lecture-04

Thrashing

Thrashing is said to occur when the system spends a large amount of time transferring shared data blocks from one node to another, compared to the time spent doing the useful work of executing application processes. It is a serious performance problem with DSM systems that allow data blocks to migrate from one node to another.

Thrashing may occur in the followingsituations :

1. When interleaved data accesses made by processes on two or more nodes causes a data block to move back and forth from one node to another in quick succession (a ping–pong effect)
2. When blocks with read only permissions are repeatedly invalidated soon after they are replicated. Such situations indicate poor (node) locality in references. If not properly handled, thrashing degrades system performance considerably. Therefore, steps must be taken to solve this problem.

The following methods may be used to solve the thrashing problem in DSM systems :

(i) Providing application–controlled locks: Locking data to prevent other nodes from accessing that for a short period of time can reduce thrashing. An application controlled lock can be associated with each data block to implement this method.

(ii) Nailing a block to a node for a minimum amount of time : Another method to reduce thrashing is to disallow a block to be taken away from a node until a minimum amount of time elapses after its allocation to that node. The time t can either be fixed statically or be turned dynamically on the basis of access patterns. For example, Mirage employs this method to reduce thrashing and dynamically determines the minimum amount of time for which a block will be available at a node on the basis of access patterns.

The main drawback of this scheme is that it is very difficult to choose the appropriate value for the time.

If the value is fixed statically, it is liable to be inappropriate in many cases. For example, if a process accesses a block for writing to it only once, other processes will be prevented from accessing the block until time t elapses. On the other hand, it a process accesses a block for performing several write operations on it, time t may elapse before the process has finished using the block and the system may grant permission to another process for accessing the block.

Therefore, tuning the value of t dynamically is the preferred approach in this case , the value of t for a block can be decided based on past access patterns of the block. The MMU’s reference bits may be used for this purpose. Another factor that may be used for deciding the value of t for a block is the length of a the queue of processes waiting for their turn to access the block.

(iii) Smallest page size algorithm: In this method, the DSM block size is taken as the smallest VM page size of all machines. If a page fault occurs on a node with a large page size, multiple blocks (whose total size is equal to the page size of the faulting node) are moved to satisfy the page fault. Although this algorithm reduces data contention, it suffers from the increased communication and block table management overheads associated with small sized blocks.

(iv) Intermediate page size algorithm : To balance between the problems of large and small sized blocks, a heterogeneous DSM system may select to choose a block size somewhere in between the largest VM page size and the smallest VM page size of all machines

3. Tailoring the coherence algorithm to the shared data usage pattern .Thrashing can also minimized by using different coherence protocols for shared data having different characteristics. For example, the coherence protocol used in Minim for write shared variables avoids the false sharing problem, which ultimately results in the avoidance of thrashing. Notice from the description above that complete transparency of distributed shared memory is compromised somewhat while trying to minimize thrashing. This is used most of the approaches described above require the programmer’s assistance.

For example, in the method of application controlled locks, the use of locks needs to be directed towards a particular shared memory algorithm and hence the shared memory abstraction can no longer be transparent. Moreover, the application must be aware of the shared data it is accessing and its shared access patterns. Similarly, Munin requires programmers to annotate shared variables with standard annotation types, which makes the shared memory abstraction nontransparent.

Distributed File Systems:(Dec-2013)

· A Distributed File System ( DFS ) is simply a classical model of a file system distributed across multiple machines. The purpose is to promote sharing of dispersed files. A file system provides a service for clients. The server interface is the normal set of file operations: create, read, etc. on files

Two main purposes of using files:

1.     Permanent storage of information on a secondary storage media.

2.     Sharing of information between applications

A file system is a subsystem of the operating system that performs file management activities such as organization, storing, retrieval, naming, sharing, and protection of files.

A file system frees the programmer from concerns about the details of space allocation and layout of the secondary storage device.

· In addition to the functions of the file system of a single-processor system, the distributed file system supports the following:

1. Remote information sharing:Thus any node, irrespective of the physical location of the file, can access the file.

2. User mobility: User should be permitted to work on different nodes.

3. Availability: For better fault-tolerance, files should be available for use even in the event of temporary failure of one or more nodes of the system. Thus the system should maintain multiple copies of the files, the existence of which should be transparent to the user.

4. Diskless workstations: A distributed file system, with its transparent remote-file accessing capability, allows the use of diskless workstations in a system.

· A distributed file system provides the following types of services:

Storage service: Allocation and management of space on a secondary storage device thus providing a logical view of the storage system.

True file service: Includes file-sharing semantics, file-caching mechanism, file replication mechanism, concurrency control, multiple copy update protocol etc.

Name/Directory service: Responsible for directory related activities such as creation and deletion of directories, adding a new file to a directory, deleting a file from a directory, changing the name of a file, moving a file from one directory to another etc.

DFS provides three types of services:

· Storage service- allocation and management of storage

· True file service – operations on individual file, includes read / write

· Name service – mapping between names and references

………….…Reference P.K.SINHA, Distributed Operating System,421}

Unit-02/Lecture-05

Desirable features of good Distributed File System

41.Transparency

-Structure transparency: Clients should not know the number or locations of file servers and the storage devices. Note: multiple file servers provided for performance, scalability, and reliability.

-  Access transparency: Both local and remote files should be accessible in the same way. The file system should automatically locate an accessed file and transport it to the client�s site.

- Naming transparency: The name of the file should give no hint as to the location of the file. The name of the file must not be changed when moving from one node to another.

-Replication transparency: If a file is replicated on multiple nodes, both the existence of multiple copies and their locations should be hidden from the clients.

2.     2. User mobility : Automatically bring the user environment (e.g. user home directory) to the node where the user logs in.

3. Performance: Performance is measured as the average amount of time needed to satisfy client requests. This time includes CPU time + time for accessing secondary storage + network access time. It is desirable that the performance of a distributed file system be comparable to that of a centralized file system.

4. Simplicity and ease of use: User interface to the file system be simple and number of commands should be as small as possible.

5. Scalability :Growth of nodes and users should not seriously disrupt service.

6. High availability : A distributed file system should continue to function in the face of partial failures such as a link failure, a node failure, or a storage device crash. A highly reliable and scalable distributed file system should have multiple and independent file servers controlling multiple and independent storage devices.

7. High reliability :Probability of loss of stored data should be minimized. System should automatically generate backup copies of critical files.

8.Data integrity: Concurrent access requests from multiple users who are competing to access the file must be properly synchronized by the use of some form of concurrency control mechanism. Atomic transactions can also be provided.

 9. Security:Users should be confident of the privacy of their data.

 10.Heterogeneity: There should be easy access to shared data on diverse platforms (e.g. Unix workstation, Wintel platform etc).

File Models

1.Unstructured and Structured files

In the unstructured model, a file is an unstructured sequence of bytes. The interpretation of the meaning and structure of the data stored in the files is up to the application (e.g. UNIX and MS-DOS). Most modern operating systems use the unstructured file model.

In structured files (rarely used now) a file appears to the file server as an ordered sequence of records. Records of different files of the same file system can be of different sizes.

2.Mutable and immutable files

Based on the modifiability criteria, files are of two types, mutable and immutable. Most existing operating systems use the mutable file model. An update performed on a file overwrites its old contents to produce the new contents.

In the immutable model, rather than updating the same file, a new version of the file is created each time a change is made to the file contents and the old version is retained unchanged. The problems in this model are increased use of disk space and increased disk activity.

………….…Reference {P.K.SINHA, Distributed Operating System,422}

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	What are the various trends in distributed file system? Explain them in detail?	Dec2013	7

Unit-02/Lecture-06

File Service Architecture

· An architecture that offers a clear separation of the main concerns in providing access to files is obtained by structuring the file service as three components:

o A flat file service

o A directory service

o A client module.

· The relevant modules and their relationship is shown in Figure

Figure : File service architecture

· The Client module implements exported interfaces by flat file and directory services on server side.

· Responsibilities of various modules can be defined as follows:

(1) Flat file service: Concerned with the implementation of operations on the contentsof file. Unique File Identifiers (UFIDs) are used to refer to files in all requests for flat file service operations. UFIDs are long sequences of bits chosen so that each file has a unique among all of the files in a distributed system.

(2) Directory service: Provides mapping between text names for the files and their UFIDs. Clients may obtain the UFID of a file by quoting its text name to directory service. Directory service supports functions needed generate directories, to add new files to directories.

(3) Client module:

v It runs on each computer and provides integrated service (flat file and directory) as a single API to application programs. For example, in UNIX hosts, a client module emulates the full set of Unix file operations.

v It holds information about the network locations of flat-file and directory server processes; and achieve better performance through implementation of a cache of recently used file blocks at the client.

(4) Flat file service interface:

v Above Figure contains a definition of the interface to a flat file service.

(5) Access control

v In distributed implementations, access rights checks have to be performed at the server because the server RPC interface is an otherwise unprotected point of access to files.

(6) Directory service interface

v Above Figure contains a definition of the RPC interface to a directory service.

(7) Hierarchic file system

i. A hierarchic file system such as the one that UNIX provides consists of a number of directories arranged in a tree structure.

(8) File Group

ii. A file group is a collection of files that can be located on any server or moved between servers while maintaining the same names.

1. A similar construct is used in a UNIX file system.

2. It helps with distributing the load of file serving between several servers.

3. File groups have identifiers which are unique throughout the system (and hence for an open system, they must be globally unique).

………….…Reference{www.slideshare.net}

Unit-02/Lecture-07

File Accessing Models

This depends on the method used for accessing remote files and the unit of data access.

1. Accessing remote files:

A distributed file system may use one of the following models to service a client file access request when the accessed file is remote:

 a. Remote service model :Processing of a client request is performed at the servernode. Thus, the client request for file access is delivered across the network as a message to the server, the server machine performs the access request, and the result is sent to the client. Need to minimize the number of messages sent and the overhead per message.

 b. Data-caching model: This model attempts to reduce the network traffic of the previous model by caching the data obtained from the server node. This takes advantage of the locality feature of the found in file accesses. A replacement policy such as LRU is used to keep the cache size bounded.

 While this model reduces network traffic it has to deal with the cache coherency problem during writes, because the local cached copy of the data needs to be updated, the original file at the server node needs to be updated and copies in any other caches need to be updated.

· Advantage of Data-caching model over the Remote service model:The data-caching model offers the possibility of increased performance and greater system scalability because it reduces network traffic, contention for the network, and contention for the file servers.

Hence almost all distributed file systems implement some form of caching. Example, NFS uses the remote service model but adds caching for better performance.

 2. Unit of Data Transfer:

In file systems that use the data-caching model, an important design issue is to decide the unit of data transfer. This refers to the fraction of a file that is transferred to and form clients as a result of single read or write operation.

a. File-level transfer model: In this model when file data is to be transferred, the entire file is moved.

· Advantages: file needs to be transferred only once in response to client request and hence is more efficient than transferring page by page which requires more network protocol overhead. Reduces server load and network traffic since it accesses the server only once. This has better scalability. Once the entire file is cached at the client site, it is immune to server and network failures.

· Disadvantage: requires sufficient storage space on the client machine. This approach fails for very large files, especially when the client runs on a diskless workstation. If only a small fraction of a file is needed, moving the entire file is wasteful.

b. Block-level transfer model: File transfer takes place in file blocks. A file block is a contiguous portion of a file and is of fixed length (can also be a equal to a virtual memory page size).

· Advantages: Does not require client nodes to have large storage space. It eliminates the need to copy an entire file when only a small portion of the data is needed.

· Disadvantages: When an entire file is to be accessed, multiple server requests are needed, resulting in more network traffic and more network protocol overhead. NFS uses block-level transfer model.

c.Byte-level transfer model: Unit of transfer is a byte. Model provides maximum flexibility because it allows storage and retrieval of an arbitrary amount of a file, specified by an offset within a file and length.

Drawback is that cache management is harder due to the variable-length data for different access requests.

d. Record-level transfer model:This model is used with structured files and the unit of transfer is the record.

………….…Reference {P.K.SINHA, Distributed Operating System,427}

File Sharing Semantics(Dec-2011)

· When two or more users share the same file, it is necessary to define the semantics of reading and writing precisely to avoid problems. In single-processor systems that permit processes to share files, such as UNIX, the semantics normally state that when a READ operation follows a WRITE operation, the READ returns the value just written, as shown in Fig. .

· Similarly, when two writes happen in quick succession, followed by a READ, the value read is the value stored by the last write. In effect, the system enforces an absolute time ordering on all operations and always returns the most recent value. We will refer to this model as UNIX semantics. This model is easy to understand and straightforward to implement.

(a) On a single processor, when a READ follows a WRITE, the value returned by the read is the value just written. (b) In a distributed system with caching, obsolete values may be returned.

· In a distributed system, UNIX semantics can be achieved easily as long as there is only one file server and clients do not cache files. All reads and WRITES go directly to the file server, which processes them strictly sequentially. This approach gives UNIX semantics (except for the minor problem that network delays may cause a READ that occurred a microsecond after a write to arrive at the server first and thus get the old value).

Unit-02/Lecture-08

· In practice, however, the performance of a distributed system in which all file requests must go to a single server is frequently poor. This problem is often solved by allowing clients to maintain local copies of heavily used files in their private caches. Although we will discuss the details of file caching below, for the moment it is sufficient to point out that if a client locally modifies a cached file and shortly thereafter another client reads the file from the server, the second client will get an obsolete file, as illustrated in Fig.

· One way out of this difficulty is to propagate all changes to cached files back to the server immediately. Although conceptually simple, this approach is inefficient. An alternative solution is to relax the semantics of file sharing. Instead of requiring a READ to see the effects of all previous WRITEs, one can have a new rule that says: "Changes to an open file are initially visible only to the process (or possibly machine) that modified the file.

· Only when the file is closed are the changes made visible to other processes (or machines)." The adoption of such a rule does not change what happens in Fig. 2.1(b), but it does redefine the actual behavior (B getting the original value of the file) as being the correct one. When A closes the file, it sends a copy to the server, so that subsequent READs get the new value, as required. This rule is widely implemented and is known as session semantics.

· Using session semantics raises the question of what happens if two or more clients are simultaneously caching and modifying the same file. One solution is to say that as each file is closed in turn, its value is sent back to the server, so the final result depends on who closes last. A less pleasant, but slightly easier to implement alternative is to say that the final result is one of the candidates, but leave the choice of which one unspecified.

· One final difficulty with using caching and session semantics is that it violates another aspect of the UNIX semantics in addition to not having all reads return the value most recently written. In UNIX, associated with each open file is a pointer that indicates the current position in the file. READs take data starting at this position and writes deposit data there. This pointer is shared between the process that opened the file and all its children. With session semantics, when the children run on different machines, this sharing cannot be achieved.

· To see what the consequences of having to abandon shared file pointers are, consider a command like

run >out

whererun is a shell script that executes two programs, a and b, one after another. If both programs produce output, it is expected that the output produced by b will directly follow the output from a within out. The way this is achieved is that when b starts up, it inherits the file pointer from a, which is shared by the shell and both processes. In this way, the first byte that b writes directly follows the last byte written by a. With session semantics and no shared file pointers, a completely different mechanism is needed to make shell scripts and similar constructions that use shared file pointers work. Since no general-purpose solution to this problem is known, each system must deal with it in an ad hoc way.

· A completely different approach to the semantics of file sharing in a distributed system is to make all files immutable. There is thus no way to open a file for writing. In effect, the only operations on files are CREATE and READ.

· What is possible is to create an entirely new file and enter it into the directory system under the name of a previous existing file, which now becomes inaccessible (at least under that name). Thus although it becomes impossible to modify the file x, it remains possible to replace x by a new file atomically. In other words, although files cannot be updated, directories can be. Once we have decided that files cannot be changed at all, the problem of how to deal with two processes, one of which is writing on a file and the other of which is reading it, simply disappears.

· What does remain is the problem of what happens when two processes try to replace the same file at the same time. As with session semantics, the best solution here seems to be to allow one of the new files to replace the old one, either the last one or non deterministically.

· A somewhat stickier problem is what to do if a file is replaced while another process is busy reading it. One solution is to somehow arrange for the reader to continue using the old file, even if it is no longer in any directory, analogous to the way UNIX allows a process that has a file open to continue using it, even after it has been deleted from all directories. Another solution is to detect that the file has changed and make subsequent attempts to read from it fail.

· A fourth way to deal with shared files in a distributed system is to use atomic transactions, , to access a file or a group of files, a process first executes some type of BEGIN TRANSACTION primitive to signal that what follows must be executed indivisibly. Then come system calls to read and write one or more files. When the work has been completed, an END TRANSACTION primitive is executed.

· The key property of this method is that the system guarantees that all the calls contained within the transaction will be carried out in order, without any interference from other, concurrent transactions. If two or more transactions start up at the same time, the system ensures that the final result is the same as if they were all run in some (undefined) sequential order.

· The classical example of where transactions make programming much easier is in a banking system. Imagine that a certain bank account contains 100 dollars, and that two processes are each trying to add 50 dollars to it. In an unconstrained system, each process might simultaneously read the file containing the current balance (100), individually compute the new balance (150), and successively overwrite the file with this new value. The final result could either be 150 or 200, depending on the precise timing of the reading and writing. By grouping all the operations into a transaction, interleaving cannot occur and the final result will always be 200. In Fig. we summarize the four approaches we have discussed for dealing with shared files in a distributed system.

Method	Comment
UNIX semantics	Every operation on a file is instantly visible to all processes
Session semantics	No changes are visible to other processes until the file is closed
Immutable files	No updates are possible; simplifies sharing and replication
Transactions	All changes have the all-or-nothing property

Table 2.1: Four ways of dealing with the shared files in a distributed system.

………….…Reference {P.K.SINHA, Distributed Operating System,430Tanenbaum&Steen, DISTRIBUTED SYSTEMS,253}

,

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	What are the semantic of file sharing? Explain it with the help of UNIX semantics?	Dec2011	10

File Caching Scheme

Caching:-Reduce network traffic by retaining recently accessed disk blocks in a cache, so that repeated accesses to the same information can be handled locally.

(i) If needed data not already cached, a copy of data is brought from the server to the user.

(ii) Accesses are performed on the cached copy.

(iii) Files identified with one master copy residing at the server machine, but copies of the file (or parts of the file) are scattered in different caches.

(iv) Cache-consistency problem – keeping the cached copies consistent with the master file.

Client Caching

Comparing Caching and Remote Service

(i) In caching, many remote accesses handled efficiently by the local cache; most remote accesses will be served as fast as local ones.

(ii) Servers are contracted only occasionally in caching (rather than for each access).

a. Reduces server load and network traffic.

b. Enhances potential for scalability.

(i) Remote server method handles every remote access across the network; penalty in network traffic, server load, and performance.

(ii) Total network overhead in transmitting big chunks of data (caching) is lower than a series of responses to specific requests (remote-service).

Unit-02/Lecture-09

Fault Tolerance in Distributed File Systems (Dec-2013)

Fault Tolerance: Fault tolerance is an important issue in the design of a distributed file system. Various types of faults could harm the integrity of the data stored by such a system. For instance, a processor loses the coments of its main memory in the event of a crash.

· Such a failure could result in logically complete but physically incomplete file operations, making the data that are stored by the file system inconsistent. Similarly, during a request processing, the server or client machine may crash, resulting in the loss of state information of the file being accessed. This may have an uncertain effect on the integrity of file data.

· Also, other adverse environmental phenomena such as transient faults (caused by Electromagnetic fluctuations) or decay of disk storage devices may result in the loss or corruption of data stored by a file system. A portion of a disk storage device is said to be ‘decay’. The data on that portion of the device are irretrievable.

The primary file properties that directly influence ability of a distributed file system to tolerate faults are as follows.

1. Availability: Availability of a file refers to the fraction of time for which the file is available for use. Note that the availability 100 property depends on the location of the file and the locations of its clients (users). For example, if a network is partitioned due to a communication link failure, a file may be available to the clients of some nodes, but at the same time, it may not be available to the clients of other nodes. Replication is a primary mechanism for improving the availability of a file.

2.Robustness: Robustness of a file refers to its power to survive crashes of the storage device and decays of the storage medium on which it is stored. Storage devices that are implemented by using redundancy techniques, such as stable storage device, are often used to store robust files. Note that a robust file may not be available until the faulty component has been recovered. Furthermore, unlike availability, robustness is independent of either the location of the file or the location of its clients.

· On the other hand, if a failure occurs that causes a subtransaction to abort before its completion, all of its tentative updates are undone, and its parent is notified. The parent may then choose to continue processing and try to complete its task using an alternative method or it may abort itself.

· Therefore, the abort of a sub transaction may not necessarily cause its ancestors to abort. However, if a failure causes an ancestor transaction to abort, the updates of all its descendant transactions (That have already committed) have to be undone. Thus no updates performed within an entire transaction family are made permanent until the top level transaction commits. Only after the top level transaction commits is success reported to the client.

Advantages of Nested Transactions :

Nested transactions facility is considered to be an important extension to the traditional transaction facility (especially in distributed system) due to its following main advantages:

(1) It allows concurrency within a transaction. That is a transaction may generate several subtransactions that run in parallel on different processors. Notice that all children of a parent transaction are synchronized so that the parent transaction still exhibits serializability.

(2) It provides greater protection against failures, in that it allows checkpoints to be established within a transaction. This is because the sub transactions of a parent transaction fail independently of the parent transaction and of one teacher. Therefore, when a subtransaction aborts, its parent can still continue and may fork alternative subtransaction in place of the failed subtransaction in order to complete its task

………….…Reference {P.K.SINHA, Distributed Operating System,447}

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	Define fault tolerant .Describe in brief,the methods to guard the system against different kinds of fault?	Dec2013	7
Q.2	Explain fault tolerant services in distributed system?	Dec2013	7
Q.3	Differentiate between caching and replication	Dec2014	7
Q.4	Explain significance of a fault tolerant service with fragmented and replicated data system? 7	Dec2014	7

Unit-02/Lecture-10

Naming(Dec-2012)

The naming facility of a distributed operating systemenables users and programs to assign character-string names to objects and subsequently use these names to refer to those objects.

• The locating facility,which is an integral part of the naming facility, maps an object's name to the object's location in a distributed system

• The naming and locating facilities jointly form a naming system that provides the users with an abstraction of an object that hides the details of how and where an object is actually located in the network.

• It provides a further level of abstraction when dealing with object replicas.Given an object name, it returns a set of the locations of the object's replicas.

• The naming system plays a very important role in achieving the goal of

§ location transparency,

§ facilitating transparent migration and replication

of objects,

§ object sharing

DESIRABLE FEATURESOF A GOOD NAMING SYSTEM

1.Location transparency: Location transparency meansthat the name of an object should not reveal any hint asto the physical location of the object. That is, anobject's name should be independent of the physicalconnectivity or topology of the system, or the currentlocation of the object

2.Location independency:For performance, reliability,availability, and security reasons, distributed systemsprovide the facility of object migrationthat allows themovement and relocation of objects dynamicallyamong the various nodes of a system.Locationindependency means that the name of an object neednot be changed when the object's location changes

Furthermore, a user should be able to access an objectby its same name irrespective of the node from wherehe or she accesses it (user migration)

Therefore, the requirement of location independencycalls for a

global naming facility with the following twofeatures:

§ An object at any node can be accessed without the knowledge of its physical location (location independency of request-receiving objects).

§ An object at any node can issue an access request without the knowledge of its own physical location(location independency of request-issuing objects).This property is also known as user mobility

3.Scalability: Distributed systems vary in size rangingfrom one with a few nodes to one with many nodes.Moreover, distributed systems are normally opensystems, and their size changes dynamically.

4. Uniform naming convention :In many existingsystems, different ways of naming objects,callednaming conventions, are used for naming differenttypes of objects. For example, file namestypicallydiffer from user namesand process names

5.Multiple user-defined names for the same object:Fora shared object, it is desirable that different users of theobject can use their own convenient names foraccessing it.

6.Group naming:A naming system should allow many different objects to be identified by the same name.Such a facility is useful to support broadcast facility or to group objects for conferencing or other applications

7. Meaningful names: A name can be simply any character string identifying some object. However, for users, meaningful names are preferred to lower level identifiers such as memory pointers, disk block numbers, or network addresses.

8.Performance:The most important performance measurement of a naming system is the amount of time needed to map an object's name to its attributes, such as its location.

9. Fault tolerance: A naming system should be capable of tolerating, to some extent, faults that occur due to the failure of a node or a communication link in a distributed svstem network.

10. Replication transparency:In a distributed system,replicas of an object are generally created to improve performance and reliability.

11.Locating the nearest replica:When a namingsystem supports the use of multiple copies of the same object, it is important that the object-locating mechanism of the naming system should always supplythe location of the nearest replica of the desired object.

Human-Oriented and System-Oriented Names

Names are used to designate or refer to objects at all levels of system architecture. They have various purposes, forms, and properties depending on the levels at which they are defined. However, an informal distinction can be made between two basic classes of names widely used in operating systems human-oriented names and system-oriented names. A human-oriented name is generally a character-string that is meaningful to its users.

· For example,/user/sinha/project-file-1 is a human-oriented name. Human-oriented names are defined by their users. For a shared object, different users of the object must have the flexibility to define their own human-oriented names for the object for accessing it.

· Flexibility must also be provided so that a user can change or delete his or her own name for the object without affecting those of other users. For transparency, human-oriented names should be independent of the physical location or the structure of objects they designate.

· Human-oriented names are also known as high-level names because they can be easily remembered by their users Human-oriented names are not unique for an object and are normally variable in length not only for different objects but also for different names for the same object. Hence, they cannot be easily manipulated, stored, and used by the machines for identification purpose. Moreover, it must be possible at some level to uniquely identify every object in the entire system.

· Therefore, in addition to human-oriented names, which are useful for users, system-oriented names are needed to be used efficiently by the system. These names generally are bit patterns of fixed size that can be easily manipulated and stored by machines. They are automatically generated by the system.

· They should be generated in a distributed manner to avoid the problems of efficiency and reliability of a centralized unique identifier generator. They are basically meant for use by the system but may also be used by the users. They are also known as unique identifiers and low-level names.

A simple naming model based on the use of human-oriented and system-oriented names in a distributed system

Figure above shows a simple naming model based on these two types of names. In this naming model, a human-oriented name is first mapped (translated) to a system-oriented name that is then mapped to the physical locations of the corresponding object's replicas

………….…Reference {P.K.SINHA, Distributed Operating System,496}

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	Explain desirable feature of good naming system?	Dec 2012	10

References
S no.	BOOK	Author	Priority
1	Distributed Operating System Concept & Design, PHI	P.K.Sinha	1