Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1998-09-28
2001-07-17
Thai, Tuan V. (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S100000, C711S147000, C711S150000
Reexamination Certificate
active
06263414
ABSTRACT:
FIELD OF THE INVENTION
The present invention is in the general field of Distributed Virtual Shared Memory.
BACKGROUND OF THE INVENTION
There follows a glossary of terms, some of which are conventional and others have been coined. A page is the continuous block of data handled by the operating system and the underlying machine architecture. A page constitutes a page of memory (e.g. residing in primary or secondary memory of a computer), however this is not obligatory and accordingly by way of non-limiting example a page may constitute e.g. a portion of a file. A virtual page is a page of virtual memory.
A DSM is a software layer which provides the illusion of shared memory on a distributed environment of hosts (computers, machines, PCs, workstations etc.), this concept is further described below. An application is the program which is using the DSM. A data item is a basic memory element that is used by the application. Typical, yet not exclusive examples of data item are a variable which is declared by the application, a set of variables (e.g., a structure or a few fields inside a structure) etc. The term data item encompasses data of any type and of any given size usable by an application.
A memory object is a continuous block of data that is capable of being mapped to virtual memory. Typical yet not exclusive examples of continuous memory being one or more pages of memory; or one or more file pages (the latter being section of file in the size of page or pages). The size of memory object equals normally k times (k integer) the size of a page. Until a memory object is mapped to virtual memory, it is not accessible to the application, namely, data cannot be read from or written to the memory object.
After the memory object is mapped to the virtual memory, data can be read from or written to the memory object by accessing the virtual memory provided, of course, that there is sufficient access permission.
There follows a description of virtual memory concept and mapping virtual addresses to a memory object.
The traditional notion of virtual memory allows the operating system in a host to (re)map virtual pages to physical pages. In this way, the memory can accommodate parts of the much larger virtual memory (address space), while these parts dynamically change according to the needs of the program, using the underlying hardware and operating system services. The basic mechanism ensures that different addresses in the virtual address space, are mapped to different physical addresses.
Distributed environments are composed of many hosts and an interconnection network. A Distributed Shared Memory (DSM) system provides a single address space shared by a number of processes which may reside on a number of hosts in a distributed environment. Any process can directly access any memory location in the address space. The DSM implements the mapping between each local memory and the shared virtual memory address space.
A shared virtual memory address space is partitioned into pages. According to one out of many possible pre-defined memory behaviors, a page has an exclusive copy, or has copies residing in the local memories of several hosts at the same time. These copies are marked with access permission rights, which typically include ReadOnly, ReadWrite, or NoAccess.
A memory reference (access) causes an access exception, also called a page fault, when the page containing the referenced memory address is marked as unavailable (via NoAccess), or when it does not have sufficient permissions for the type of access requested or access is prohibited (for instance: when there is an attempt to write a page which has ReadOnly permissions). When the exception is caught by the operating system, it invokes an exception handler which is implemented as part of the DSM system. When the memory location resides in a remote host, the handler retrieves the page containing this location (or its copy) from a remote host. The DSM (via the handler) communicates with the remote hosts, and when the page finally arrives it is copied to the memory page where the exception occurred. Access permissions are then changed and execution can resume.
By the above mechanism, access exceptions on pages that do not have a local copy usually cause the entire page to move between hosts. Even if the page contains several data items, only one of which is actually referenced, the whole page will be brought in. The reason for this is that the operating system and the underlying computer architecture provide protection (access permissions) in granularity of pages, which implies that if part of the page has certain access permissions, the remaining part must be open (or, blocked) for access with exactly the same permissions (restrictions).
There are two main problems with DSMs that work in granularity of full pages, as described above. First, the network traffic is a lot higher than actually required, due to redundant transfer of memory (which increases the message size). Second, when a memory page switches locations, it moves data items that are irrelevant to the serviced access exception, but may be required at the host where the page is originally found. This reduces the amount of parallelism in the system and decreases performance. The page is said to be falsely shared by the two hosts: each of them uses a different part of it, and yet they use the page exclusively (i.e., when one of them has the page and is accessing a certain data item, the other one cannot access the page and has to wait, although it only needs to access a different data item).
Known solutions have used compilers for lowering the granularity of DSMs, making it possible for them to work with smaller pages. The compiler essentially adds to each memory reference in the code additional instructions which check the availability of the accessed data on the local machine, thus avoiding using the page-based protection mechanism. However, execution of these additional instructions typically results in high overhead.
Modern operating systems provide mechanisms for binding virtual address space to a memory object. There follows a non-binding exemplary code for accomplishing the specified mapping utilizing a so-called section object primitive.
HANDLE os_create_object_sec(unsigned long obj_size)
{
HANDLE hObj = CreateFileMapping(
(HANDLE)-1, NULL,
PAGE_READWRITE | SEC_RESERVE, 0, obj_size, NULL);
return hObj;
}
void *os_map_mem_object(HANDLE hObj, void *reqaddr)
{
return MapViewOfFileEx(hObj,
FILE_MAP_ALL_ACCESS, 0, 0, 0, reqaddr);
}
void init( )
{
HANDLE hSecObj;
void *view1, *view2;
/*
create section object of size 3*4096 bytes (i.e 3 pages on Intel x86)
*/
hSecObj = os_create_object_sec(3*4096);
/*
map the section object to address 0x20000000 - 0x20002FFF
*/
view1 = os_map_mem_object(hSecObj, 0x20000000)
}
As shown, there are provided two functions. The first os_create_object_sec declares a section object (returning handler). A parameter for the specified function is the desired size. The second function os_map_mem_object accomplishes the actual mapping from virtual memory to memory object, utilizing the specified section object.
After duly declaring the function, their follows a short code illustrating mapping a memory object (by this particular embodiment being 3 pages size memory) to virtual address ranging across 0×2000000-0×20002FFF in the virtual address space.
The mechanism for mapping regions in the virtual address space to memory objects was originally provided in order to enable processes which reside at the same host to share data. The original idea is as follows. Let one process map a memory object to its virtual address space (using for example the specified section object). Another process can map a different virtual address space to the same memory object. As a result, both processes share the memory object via their respective virtual address spaces. Any modification of the object by one of them via its mapped region can be read immediately by the other one through its own mapped region
Itzkovitz Ayal
Schuster Assaf
Knobbe Martens Olson & Bear LLP
Technion Research and Development Foundation Ltd.
Thai Tuan V.
LandOfFree
Memory for accomplishing lowered granularity of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory for accomplishing lowered granularity of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory for accomplishing lowered granularity of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2525388