Distributed Shared Memory
BE Project
Kamlesh Laddhad Dhruv Mehta Makarand Sonare Sameer Masram Vijay Iyer Instructors: Prof V. J. Abhyankar and Prof. C. S. Moghe
What is DSM?
Abstraction that supports the notion of shared memory in a physically non shared (distributed) architecture. Local as well as remote memories can be accessed in a uniform manner, with the location of the shared region transparent to the application program. Our implementation:
under paged virtual memory environment.
Issues Involved in DSM
NETWORK
COMMUNICATION
Since the individual computers have to communicate with each other over the network, network delays cannot be ignored.
CONSISTENCY DATA
GRANULARITY
The requirement to integrate VM management and DSM often forces the granularity of the shared region to be an integral number of the fundamental unit of memory management, which is a page.
COHERENCE
Consistency Models
Strict consistency in shared memory systems.
Sequential consistency in shared memory systems Our focus.
Other consistency protocols
Casual consistency protocol. W eak and release co nsistency pro to co l
Coherence Model
WRITE-INVALIDATE PROTOCOL
A write caused invalidation of all other copies. Disad: Invalidations sent to all nodes that have copies. Efficient: Where several updates occur between reads. Inefficient: Where many nodes frequently access an object.
WRITE-UPDATE PROTOCOL
A write causes all copies to be updated. More difficult to implement as a new value has to be sent instead of invalidation messages. Generate considerable network traffic.
P ro to co l used by us : w rite- invalid ate.
Architecture
DSM
Subsystem DSM Server KEY Server
DSM Subsystem
Routines to handle page faults relating to virtual addresses corresponding to a DSM region. Code to service system calls which allow a user process to get, attach and detach a DSM region. Code to handle system calls from the DSM server.
DSM Server
In-server
Receives messages from remote DSM servers and takes appropriate action. (E.g. Invalidate its copy of a page)
Out-server
Receives requests from the DSM subsystem and communicates with its peer DSM servers at remote nodes. Note that the DSM subsystem itself does not directly communicate over the network with other hosts. Communication with key Server.
Key Sever
Each region must be uniquely identifiable across the entire LAN. When a process executes shmget system call with a key and is the first process at that host to do so, the key server is consulted. K ey server internal table is s looked-up for the key, if not found then it stores the specified key in the table as a new entry.
Communication Issues
Communication between
User level process and DSM subsystem.(Explained next)
DSM subsystem and DSM server. Amongst DSM servers. DSM server and key server.
Uses message queues. We modified the system V message queues for this purpose
Used UDP and broadcast messaging for this purpose for reasons of efficiency
User Level Process : DSM Subsystem Communication
We distinguish between two types of user level processes
A user process that makes use of DSM facility.
The user process uses a set of system calls such as shmget( ), shmat( ), shmdt( ) to communicate with the kernel.
The DSM server process, which is a privileged process. The DSM server process makes use of the following system calls. dsmcreat(), dsmgot(), dsmget(), dsmattch(), dsmattched(), dsmwpage(), dsmrpage() . dsminv().
DSM Protocol
Membership
The membership protocol is used to keep trak of those hosts that are currently interested in accessing a DSM region Consistency protocol comes into play when hosts wish to read or write from or to pages in a DSM region.
protocol
Consistency
protocol
The
correctness of the consistency protocol depends on the accuracy-of information maintained by the membership protocol.
TERMINOLOGY
Manager :
Owner :
The host where a DSM region is first created is the manager of that DSM region. Grants membership for the dsm region it owns. Any change in the membership set is communicated to all other members. The host that currently has the write permission for a DSM page Different pages of a DSM region can have different owners Ownership of a particular page may change during the lifetime of the region. Manager of the DSM region. Key of the DSM region. Current membership set for the DSM region. No. of local clients (processes on that host which executed shmat( )). Number of global clients.
Information maintained by each host for each DSM region
TERMINOLOGY
So m
e m o re info rm atio n Owner hint:
The owner hint indicates who the current owner of the page
Copies
Version
hint :
hint :
Copies hint is an estimate of the number of copies of a DSM page.
Version hint indicates the current version of the DSM page. The version
hint is used for maintaining sequence of the pages in case of loss of messages or out of order delivery.
D A T A S T R U C T
Memory management info for a particular process
Task array maintained by OS
PCB
Defines properties of region
Page directory and page table Permissible Operations
Data structures for DSM
Additions in System V to support DSM
Array of page table entries Describes a SM region
Processes attached to this region
Refetences
M ichael B eck et al,Linux K ernel Internals,A dd iso n -Wesley. A ndrew Tanenbaum ,D istributed O perating System s.Prentice H all o f India. M aurice B ach,D esign and Im plem entatio n o f U nix O perating System , Prentice Hall of India. W .R ichards Stevens,U nix N etw o rk Pro gram m ing,Prentice H all o f India. Pedro So uto and Eugene W .Stark,A D istributed Shared M em o ry Facility fo r FreeB SD ,Pro ceedings o f the U SEN IX 1997 Technical C o nference, Anaheim, California, January 6-10, 1997. Kai Li and Paul Hudak, M em o ry C o herence in Shared V irtual M em o ry System s,A C M Transactions on Computer Systems, 7(4):321 359, November 1989. M ukesh Singhal and N iranjn G .Shivaratri,A dvanced C o ncepts in O perating System s McGraw Hill
Extra Slides
Our Addition to System V for DSM
dsm_nattch: No. of hosts using this DSM region. manager_d: Details of manager such as ip
address of the host and also the index into shm_segs of the manager. member: Info about members in membership set. copy_set: Info about on which some process has attached this DSM region. dsm_wait: Queue for hosts who has requested to attach to this DSM region and are waiting. dsm_pages: Info(owner hint, version hint, copies, page wait) about the pages belonging to this DSM region.
