The section below is extracted from http://www.cs.ncl.ac.uk/modules/1999-2000/csc810/memory.html

Memory Management (4)

The following short extract is taken from the paper:

EMAS - The Edinburgh Multi-Access System, by H.Whitfield and A.S.Wight, The Computer Journal,vol.16,no.4,November 1973.

The Paging System

Files reside permanently on the disc-file and pages of files are moved between the disc-file, core and drum during the execution of user processes.

User processes do not make file-access requests but instead refer to virtual memory addresses onto which files have been mapped. The paging software moves the relevant pages around the storage hierarchy as required.

The director connects files to virtual memory by writing information on the master page. Small files are laid out on the disc-file in contiguous pages but a file of more than 16 pages in length is broken into 16 page blocks plus a shorter block of pages for any remainder. One 16 page block is not necessarily next to its successor block. On the master- page there is a table which relates segment numbers in virtual memory to physical disc-file addresses.

For each segment there is specified:

   ACCESS MODE:     no access, read/read-write, shareable/non-shareable.
   LENGTH:          length of block, i.e. number of valid pages in this segment.
   DISC ADDRESS:    disc address of first page of the block.
   AMX:             index into the active memory table.

The paging routines operate from this table (the claimed block table - CBT) and have no knowledge of files as such or to whom they belong. Because this table and other necessary tables (see diagram) are quite large (about 3,000 bytes), the master page is paged with the process. However, it must always be in core while the process is receiving service from the CPU.

When a process which has its pages entirely resident on the disc- file becomes active, it must first wait until it can be allocated an initial amount of drum space. Its master page is then copied to the drum and the process waits for an allocation of core. When it is allocated core its master page is moved to core and execution begins. This causes page demands and further pages are brought in. As pages come in entries are added to the core memory (CMT), core map (CMAP) and core position (CPT) tables. Every so often the read-write markers on the core pages belonging to a process are examined and cleared and entries made in the USAGE field of the core map. If it appears that pages are no longer being used they are removed from core to the drum. In this way the size of the core working set is reduced. If a process goes to sleep (e.g. waits for console input) or is removed from core for other reasons, the core working set can, if appropriate, be retained and the pages in it preloaded the next time.

The segment and page tables which drive the hardware have to be set up for processes in core from the other tables. It is worth noting that the core map and the core position tables contain all the information needed to do this. In fact alternative paging hardware operating directly from these tables is easy to envisage. An associative memory large enough to contain extracts from the core map and core position tables of the current process would be needed. At present we restrict these tables to 63 entries.

To enable the paging routines to perform preloading operations where appropriate, extracts of the claimed block table are kept permanently in core. This table (the active memory table - AMT) has space for extracts concerning 32 blocks but is not always full. The entry specifies the block disc address and has a 16 bit mask to specify which pages of the block are in the working set and therefore eligible for space on the drum. When the pages of the working set are actually allocated space on the drum the disc address is changed to a pointer to a block page table (BPT) which has further pointers to the active store table (AST). Here there is one entry for each drum page. In this entry there is a core address if the page is allocated core. There are also flags which specify whether the page is in core or on the drum, and whether a page on the drum has been changed since it was last on disc-file.

In the case of files connected in a shareable mode there is an extra level of indirection from the active memory table of each process through a common shared active memory table (SAM) and then to the block page table entry. In this way all references to a shared file use the same disc, drum or core page as appropriate. There is also a table (the page in transit table - PIT) which has chains of processes awaiting the arrival of a shared page.

When a page fault interrupt occurs, i.e. reference is made to a virtual address where the corresponding page is not in core or the page table is not up to date, the supervisor accesses the claimed block table to check that access is valid. If the AMX field is non-zero there is an extract in the active memory table and supervisor works down the chain to discover where the latest version of the page is situated. It will then demand page it from the disc or drum, or, if it is in core already, complete the page table. If the page is not in core but already on its way (for some other process) an entry is made in the page in transit table.

The paging is handled by a number of servicing routines.

    
   ACTIVEGIVE   which moves the master page from disc to drum,
   COREGIVE     which preloads the current core working set from drum to core,
   PAGETURN     which services demand page requests,
   CORETAKE     which removes unused pages or complete working
                sets, and recomputes the working set, and
   ACTIVETAKE   which moves pages from drum to disc.

In general pages leaving core go to the drum. However a process which is designated for removal to disc can have its unshared pages moved directly to disc.


harry.whitfield@ncl.ac.uk               27 november 1997 ...