MONADS

MONADS address resolution occurs as depicted:
monads_as.png

Attempting to translate a virtual address not in main memory causes a page fault interrupt.

Page fault resolution involves determining the disk location of the virtual page; as MONADS VM encompasses all disk and main memory, a virtual address can refer to any byte on any disk attached to a MONADS computer.

The partitions into which a MONADS disk are divided are known as volumes. When a volume is created it is allocated a unique volume number. The volume number forms the high-order bits of all addresses stored on the volume. The kernel contains a local mount table of all currently mounted volumes.


Address spaces

Volumes

Volumes are further divided into areas corresponding to logical entities such as processes, files and programs. The areas are called address spaces and are identified by address space numbers.
MONADS addresses are structured to describe the volume, address space, and page containing the address.

Volume number (6 bits) Within volume address space number (26 bits) Within AS page (16 bits) Offset (12 bits)

Each address space has its own page table which maps from virtual addresses to disk addresses for that address space. This page table is stored within the address space which it describe:

page_table.png

Address space 0 of a volume is used to store volume specific information such as the free space map and a directory of the address spaces stored on the volume.
The structure of address space zero is identical to all other address spaces in that it contains primary and secondary page tables. The location of its first page must be predefined.

  • Since the VM is very large, VM addresses need-not be reused
  • All processes & data co-exist in the same VM space (sharing data is thus easy)
  • Preventing unwanted access to data is a problem

Segmented Memory

MONADS uses a high-level protection scheme which divides the VM space into logical segments. Access to segments is controlled by capabilities.

Segments can be any arbitrary size. Segment and page boundaries are orthogonal, and all segments have the same basic format (so access to them is uniform).
Segments may contain data and capabilities for other segments. Processes use offsets relative to a segment (never generate virtual addresses).
Segments are addressed using segment capabilities with the format:

Start address Length Type & access

The ‘type’ field defines the type of data contained in the segment and the ‘access’ field defines the allowable operations.

To enable access to the data stored in a segment, a segment capability must be loaded into a capability register. Machine instructions access the data using addresses of the form:

Capability register# Offset within segment

Segments are grouped together into information-hiding modules, each module presenting a procedural interface.

  • Access to modules is controlled by module capabilities
    • …in the form:
    • || Name || Access list || Status ||
  • The ‘access list’ defines the interface procedures useable by the owner of the capability.
  • The ‘status’ field defines the operations that can be performed on the capability.

Module capabilities

Module capabilities can only be stored in the data area of segments of type “module capability”. These have the type and access fields set to prevent illegal modifications of the stored “modcaps”.

The first time a process accesses a module it must open it. This operation causes the creation of a special ‘module call segment’ (MCS), which contains segment capabilities for each of the interface procedures available and is used for subsequent calls on the module until it is closed.
To create a MCS the calling process must access the module’s "red tape information", which is contained in the root page of each module.

Each module resides in a separate and unique address space. These spaces are never reused, even if the module is deleted. The module name in a module capability is the address space occupied by the module.

The two distinct types of address spaces contain modules or stacks. The major difference is that a stack address space may contain pointers into other address spaces, so all stack address spaces are long.
A module address space does not contain pointers, so all pointers are only to segments within the module. Thus pointers are simple offsets within the address space relative to the module (cant be short).

caps.png

Node address resolution

The unique node number for a MONADs node is defined in hardware when it is manufactured. These node numbers create a virtual network similar to the way IP numbers form an internet. Translations between node numbers and network addresses are contained in the network addresses table maintained by the kernel (maintains the mapping Logical node numberPhysical network address.

When a node boots, it initializes its local network addresses table (NAT) with its own node number mapping and the broadcast node mapping. The node then broadcasts a ‘here_i_am’ message containing its own logical node number and physical network address. On receipt of this message the other nodes update their NATs and reply with a ‘here_i_am_too’ message. When a node shuts down it broadcasts a ‘node_going_down’ message, resulting in the removal of this mapping.


Data coherency

At any time there may be copies of a particular page in the memories of multiple nodes. For the views of the data to remain coherent each node must see the same version of each such page.
Maintenance of coherent views is no problem if nodes only read a shared page. If one writes to it, then the other nodes no longer have the same view. The solution is to use a multiple reader / single writer policy (this requires hardware support in the ATU).
The kernel at each node maintains an exported pages table (XPT) which contains an entry for every owned page for which a copy exists in the main memory of another node. This contains:

Page number Reading nodes Disk page Current version node
  • The ‘reading nodes’ field is similar to the ‘copy set’ used in IVY.
  • The ‘disk page’ field is used to create the MMT entry for a modified exported page when it is returned to the owner.
  • The ‘current version’ field contains the node number of the node with a read/write copy of the page, or if there are read-only copies it defines which node has the most recent copy.
    • If a copy of the page is in the main memory of the owner node as well as remote nodes, the current version field contains the node number of the owner node.
    • If the owner node has an up-to-date copy of the page but not in main memory (and an XPT entry exists) the current version field is set to null.
  • The XPT for a diskless node is always empty.

Nodes also maintain the ‘imported pages table’ (IPT) listing imported pages currently in their main memory;

Virtual page number Server node Main memory page frame number

Pages loaded from local disk for local use default to read/write access. Imported pages default to read-only.
At any time there are:

  • Zero or more read-only copies of the page OR…
  • Zero or one read/write copy of the page.

Owner nodes are responsible for implementing the page coherence protocol for their pages. When a page fault for a remote page occurs at a node, the local kernel determines the page owner from the page address.

Obtaining a read-only copy of a page

  • A ‘request_page’ message is transmitted to the owner node
  • On receipt of this message by the owner node:
    • No copy exists in main memory network-wide. A ‘supply_page’ message is used to transmit a copy of the page after it is retrieved from secondary storage.
    • One or more read-only copies exist in main memory network-wide but not in the owner node’s main memory. A ‘send_page’ message is transmitted to one of the nodes with a copy.
    • One or more read-only copies exist in main memory network-wide, including a copy in the owner node-s main memory. A ‘supply_message’ message is used to transmit a copy of the page to the requesting node.
    • A read/write copy exists in the main memory of a node. If the r/w copy is in the owner node’s main memory it is marked as read-only and a ‘suppy_page’ message is used. If the r/w copy is at a remote node, a ‘send_page’ message is used.
    • It has no knowledge. An ‘invalid_address_space’ message is used to inform the requesting node.

In all cases (except ‘no knowledge’) the page is mapped in as r-o into the ATU at the requesting node. In the ‘no knowledge’ case, an exception condition exists at the requesting node.

  • If a page fault occurs at the owner node, the XPT is used to determine the page status. It is usually quicker to retrieve a copy of the page from another node than to load it from local disk.

Obtaining a Read/write copy of a page

  • R/w access is achieved by increasing the access rights of a r-o page.
  • This is achieved by transmitting a ‘request_changed_access_rights’ message to the page owner. Either:
    • An r-o copy exists only in the memory of the requesting node. The owner transmits a ‘access_rights_changed’ message to the requesting node.
    • More than one copy of the page exists in main memory system-side, including in the memory of the requesting node. An ‘invalidate_page’ message is sent to all nodes with a copy. When all ‘page_invalidated’ messages have been received, an ‘access_rights_changed’ message is transmitted.

Page discard

If the page to be discarded is not local (has an IPT entry), than either:

  • The page is unmodified r-o or unmodified r/w. ‘Page_invalidated’ message informs the owner node.
  • The page is modified r/w, or modified r-o. The access is reduced to r-o (if necessary) and a copy is returned to the owner using the ‘return_page’ message.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License