\include{setup}

\begin{document}
\pagestyle{headings}

\vfill
\thispagestyle{empty}

\vbox{}
\vfill

{\Huge
\begin{center}
\begin{tabular}{c}
Virtual Memory Management \\
in Mach
\end{tabular}
\end{center}
}
\vfill
\vfill
\begin{center}
The following slides are borrowed from \\
\vspace*{.25in}
{\Large  A Mach Tutorial}\\
\vspace*{.25in}
Copyright \copyright 1990 by David L. Black, \\
Avadis Tevanian, Jr., and Michael Wayne Young \\
All Rights Reserved.\\
\end{center}
\vfill

\newpage
\slidehead{Mach VM: Key Features}
\begin{itemize}
\item {\it Architecture independence}: easily portable to paged architectures
\item {\it Multiprocessor/distributed system support}: supports current and
future architectures
\item {\it Advanced functionality}: shared memory, mapped files, etc.
\item {\it High performance}: outperforms several machine dependent designs
\end{itemize}

\newpage
\slidehead{Mach VM Support}

Interface
\begin{itemize}
\item portable -- simple paged address space model
\item flexible -- sparse, virtual address spaces
\item sharing -- within a task, and between related tasks
\item extensible -- user-defined memory objects
\end{itemize}

Implementation
\begin{itemize}
\item lazy evaluation
\item copy-on-write virtual copy operations
\item architecture-independent data structures
\item easily portable - minimal hardware support required
\end{itemize}

\newpage
\slidehead{Basic VM Design}

Needs to be portable to wide variety of hardware

Logical (machine-independent) representation
\begin{itemize}
\item Task virtual memory {\it address maps}

\item Virtual memory {\it objects}

\item Resident {\it pages} -- not necessarily hardware page size
\end{itemize}

Architecture-dependent subsystem
\begin{itemize}
\item Keep the interface simple

\item Merely make the MMU work

\item May have incomplete information
\end{itemize}

\newpage
\slidehead{Entry Lookup}

{\it vm_map_lookup_entry}: lookup an address in a map, returning a pointer
to an entry.

Algorithm:

\begin{itemize}
\item Start at saved hint.
\item Follow linked list until region found.
\end{itemize}

\newpage
\slidehead{Map space allocation}

{\it vm_map_find}: finds free address space

Algorithm:

\begin{itemize}
\item Use free space hint when possible.

\item Start at specified address (using lookup).

\item Follow list until finding an open slot.

\item If slot found, insert new entry into list (extending previous entry if
possible).

\end{itemize}

\newpage
\slidehead{Other Map Manipulations}

{\it vm_map_remove}

{\it vm_map_copy}

{\it vm_map_protect}

{\it vm_map_inherit}

All operate on a range of addresses.

First lookup start address.

Scan each region in the list (until end) performing necessary operation.

Split (and merge) entries whenever necessary.

\newpage
\slidehead{VM Objects}

Each VM object represents a single source of virtual memory.

Resident pages cache that memory in physical memory.

Remainder is always available from object's {\it memory manager}.

No memory manager is recorded for zero-filled memory initially.
Default memory manager will provide backing storage when
pageout becomes necessary.

All zero-filled memory is created equal...
sequentially allocated memory extends objects (instead of creating new ones).

\newpage
\slidehead{Efficient Virtual Memory Copy}

Copied data is often only read, not written

Share physical memory read-only until written, then make copy

Copy-on-write algorithm:
\begin{itemize}
\item Copy object reference to new map

\item Mark both map entry references {\it copy-on-write}

\item Reprotect pages in hardware to prevent writing
\end{itemize}

When write fault occurs:
\begin{itemize}
\item Make new object to hold changed pages

\item Keep old object reference for unchanged pages
\end{itemize}

\newpage
\slidehead{Resident Pages}

Physical memory is just a cache of virtual memory

Page belongs to just one object

Associative store: hash to resident page by object, offset
(called the {\it virtual-to-physical table})

Also need to maintain:
\begin{itemize}
\item All pages within one object (to ease deallocation, virtual copy)

\item Pageout information
\begin{itemize}
\item Modified and referenced bits

\item Free queue, or LRU pageout queue
\end{itemize}
\end{itemize}

Page structure is a multi-threaded list

Wire operation faults in page; removes from queues.

\newpage{}
\slidehead{Page Fault Algorithm}

Look up fault address in map to find object.
Create shadow object if necessary.

Get the specified page in resident memory (next slide)

Make copy if copy object doesn't have one and page is being written.

Verify that we still want this page; if not, start all over

Enter page into physical map and return

\newpage{}
\slidehead{Page Fault -- How to Find a Page}

Have an object/offset description.

Until we find the page:

\begin{itemize}

\item Look for a resident page in this object

\item If we can't find one:

	\begin{itemize}

	\item Allocate new page with appropriate object/offset; mark it busy

	\item Ask the memory manager for this object to retrieve the data

		\begin{itemize}

		\item If we still don't find it, try loop again
		with shadow object

		\item If there is no shadow object, zero-fill the page

		\end{itemize}

	\end{itemize}

\end{itemize}

\newpage{}
\slidehead{Pageout Algorithm}

Three queues:

\begin{itemize}

\item Active list -- pages that have been mapped, in LRU-like order

\item Inactive list -- pages with reference bit cleared, staged for pageout.

\item Free list -- pages with no mappings; available for use

\end{itemize}

Free clean pages from the {\it inactive} list

Start cleaning dirty pages from the {\it inactive} list

Replenish the {\it inactive} list by drawing from {\it active} list

Reference bit need not be implemented as such in pmap module

\newpage{}
\slidehead{Virtual Memory Cache}

All pages in memory represent a VM cache of secondary storage.

Objects may be specified as {\it persistent}:

\begin{itemize}

\item When an object is no longer referenced, its pages are not freed.

\item Pages are placed on inactive queue (remembered in hash table).

\item Kernel maintains a LRU list of unreferenced objects still cached

\end{itemize}

Major use - objects representing virtual memory obtained from files

\newpage
\slidehead{Locks}

The following locks are used:

\begin{itemize}

\item {\it map locks}: protects address maps

\item {\it object locks}: protects each object

\item {\it hash table bucket locks}: locks object/page hash table

\item {\it busy pages}: long term per-page locks

\end{itemize}

Notes:

\begin{itemize}

\item Address maps have subsidiary locks for reference count and hints.

\item Currently only a single hash table bucket lock - may change in future.

\end{itemize}

\newpage
\thispagestyle{empty}

\vbox{}
\vfill

{\Huge
\begin{center}
\begin{tabular}{c}
External Memory Management \\
in Mach
\end{tabular}
\end{center}
}

\vfill

\newpage
\slidehead{Exporting Memory Management}

Map objects into user address spaces

User-level server manages backing storage

Kernel manages main memory as cache of user data

\newpage
\slidehead{Benefits}

Flexibility in managing data

Improved performance from better sharing and caching

Better structuring of kernel and applications

Allows virtual memory to be implemented on a communication
base -- appropriate to some multiprocessors

\newpage
\slidehead{Applications}

Typical Operating System Facilities
\begin{itemize}
\item {Mapped files}
\item {Shared state mapped as objects}
\item {Network paging}
\item {Network shared memory}
\end{itemize}

Database Management
\begin{itemize}
\item {Special backing storage management}
\item {External consistency constraints}
\end{itemize}

Process Migration
\begin{itemize}
\item {Copy-on-reference}
\item {Provide-in-advance}
\end{itemize}

Relaxed Consistency on Shared Data

\newpage
\slidehead{Interface Organization}

Memory objects
\begin{itemize}
\item {Mapped into user address space(s)}
\item {Represented by a port if user-managed}
\item {Port used by kernel to access and store object data}
\end{itemize}

Interfaces
\begin{itemize}
\item {Memory Manager to Kernel}
\item {Kernel to Memory Manager}
\end{itemize}

Asynchronous
\begin{itemize}
\item {Provide data in advance}
\item {Delay transfer to backing storage}
\item {Allow flexibility and concurrency}
\end{itemize}

Multiple kernels may use same object

\newpage
\slidehead{Interface Description}

Client - Map memory object

Kernel to Memory Manager
\begin{itemize}
\item {Initialize memory object}
\item {Request page of data}
\item {Write back changed data page}
\item {Terminate}
\end{itemize}

Memory Manager to Kernel
\begin{itemize}
\item {Provide data page}
\item {Restrict access to cached data}
\item {Clean and/or flush cached data}
\item {Allow data to be cached when not mapped}
\item {Indicate that data is not available}
\end{itemize}

\newpage
\slidehead{Example: Initialization}

\begin{center}

\Large
\setlength{\unitlength}{1.0in}

\begin{picture}(7,4)

\thicklines

\put(0.25,3.25){\framebox(1.5,0.75){Client A}}
\put(0.25,0){\framebox(1.5,0.75){\shortstack{Mach\\[3pt]Kernel A}}}
\put(2.75,1.5){\framebox(1.5,1.0){\shortstack{Shared\\[3pt]Memory\\Server}}}

\put(0.5,3.25){\vector(0,-1){2.49}}
\put(0.3,2.0){2}

\put(0.625,0.76){\vector(0,1){2.49}}
\put(0.65,2.0){4}

\put(1.38,0.76){\vector(1,1){1.36}}
\put(1.75,1.375){3}

\put(1.75,3.75){\vector(1,-1){1.245}}
\put(2.35,3.25){1}

\put(2.82,2.505){\vector(-1,1){1.065}}

\end{picture}
\end{center}

\begin{enumerate}
\item {Request memory object from manager}
\item {Map object into address space}
\item {Kernel initializes memory object}
\item {Client resumed}
\end{enumerate}

\newpage
\slidehead{Example: Simple Fault}

\begin{center}

\Large
\setlength{\unitlength}{1.0in}

\begin{picture}(7,4)

\thicklines

\put(0.25,3.25){\framebox(1.5,0.75){Client A}}
\put(0.25,0){\framebox(1.5,0.75){\shortstack{Mach\\[3pt]Kernel A}}}
\put(2.75,1.5){\framebox(1.5,1.0){\shortstack{Shared\\[3pt]Memory\\Server}}}

\put(0.5,3.25){\vector(0,-1){2.49}}
\put(0.3,2.0){1}

\put(0.625,0.76){\vector(0,1){2.49}}
\put(0.65,2.0){4}

\put(1.38,0.76){\vector(1,1){1.36}}
\put(1.75,1.375){2}

\put(2.74,1.945){\vector(-1,-1){1.185}}
\put(2.0,1.0){3}

\end{picture}
\end{center}

\begin{enumerate}
\item {Client program page faults}
\item {Kernel requests data}
\item {Memory manager provides data}
\item {Kernel enters page mapping, resumes client}
\end {enumerate}

\newpage
\slidehead{Example: Shared Access}

\begin{center}

\Large
\setlength{\unitlength}{1.0in}

\begin{picture}(7,4)

\thicklines

\put(0.25,3.25){\framebox(1.5,0.75){Client A}}
\put(5.25,3.25){\framebox(1.5,0.75){Client B}}
\put(0.25,0){\framebox(1.5,0.75){\shortstack{Mach\\[3pt]Kernel A}}}
\put(5.25,0){\framebox(1.5,0.75){\shortstack{Mach\\[3pt]Kernel B}}}
\put(2.75,1.5){\framebox(1.5,1.0){\shortstack{Shared\\[3pt]Memory\\Server}}}

\put(1.38,0.76){\vector(1,1){1.36}}

\put(2.74,1.945){\vector(-1,-1){1.185}}
\put(2.0,1.0){3}

\put(5.62,0.76){\vector(-1,1){1.36}}
\put(5.1,1.375){2}

\put(4.26,1.945){\vector(1,-1){1.185}}
\put(4.85,1.0){4}

\put(6.5,3.25){\vector(0,-1){2.49}}
\put(6.3,2.0){1}

\put(6.625,0.76){\vector(0,1){2.49}}

\end{picture}
\end{center}

\begin{enumerate}
\item {Another client read faults on same page}
\item {Its kernel requests data}
\item {Memory manager locks data to prevent modification}
\item {Memory manager provides data, read-only}
\end{enumerate}

\newpage
\slidehead{Example: Revoking Access}

\begin{center}

\Large
\setlength{\unitlength}{1.0in}

\begin{picture}(7,4)

\thicklines

\put(0.25,3.25){\framebox(1.5,0.75){Client A}}
\put(5.25,3.25){\framebox(1.5,0.75){Client B}}
\put(0.25,0){\framebox(1.5,0.75){\shortstack{Mach\\[3pt]Kernel A}}}
\put(5.25,0){\framebox(1.5,0.75){\shortstack{Mach\\[3pt]Kernel B}}}
\put(2.75,1.5){\framebox(1.5,1.0){\shortstack{Shared\\[3pt]Memory\\Server}}}

\put(0.5,3.25){\vector(0,-1){2.49}}
\put(0.3,2.0){1}

\put(0.625,0.76){\vector(0,1){2.49}}

\put(1.38,0.76){\vector(1,1){1.36}}
\put(1.75,1.375){2}

\put(2.74,1.945){\vector(-1,-1){1.185}}
\put(2.0,1.0){4}

\put(5.62,0.76){\vector(-1,1){1.36}}

\put(4.26,1.945){\vector(1,-1){1.185}}
\put(4.85,1.0){3}

\end{picture}
\end{center}

\begin{enumerate}
\item {Client write faults on read-only page}
\item {Kernel requests write access to page}
\item {Memory manager requests flush}
\item {Write access granted after flush}
\end{enumerate}

\newpage
\slidehead{Potential Pitfalls}

Memory managers cannot be completely trusted
\begin{itemize}
\item {Failure to provide data}
\item {Failure to free flushed data}
\item {Spurious changes to data}
\end{itemize}

Memory managers may use their own data

\newpage
\slidehead{Protecting User Programs}

Obtain information about contents of memory

Multiple threads of control
\begin{itemize}
\item {One thread handles page fault for another}
\item {Access data of questionable origin in expendable thread}
\end{itemize}

Analogy to communication failure
\begin{itemize}
\item {Time out}
\item {Notification}
\end{itemize}

\newpage
\slidehead{Protecting the Kernel}

Default Memory Manager
\begin{itemize}
\item {Trusted provider of backing storage}
\item {Used for pageout of zero-filled memory}
\item {Backs data flushed to other managers}
\end{itemize}

Copy-on-write
\begin{itemize}
\item {Default memory manager backs original data if changed by manager}
\item {Preserves original data}
\end{itemize}

Wired-down memory -- data will not disappear

Reserved memory pool for allocation of data structures needed to flush data

\end{document}
