Editing Virtual memory (section)

==Segmented virtual memory==
Some systems, such as the [[Burroughs Corporation|Burroughs]] B5500,<ref>{{cite book|author=Burroughs|id=1021326|title=Burroughs B5500 Information Processing System Reference Manual|url=http://bitsavers.org/pdf/burroughs/B5000_5500_5700/1021326_B5500_RefMan_May67.pdf|year=1964|publisher=[[Burroughs Corporation]]|access-date=28 November 2013}}</ref> and the current Unisys MCP systems<ref name="“MCP-VM">{{cite web |title=Unisys MCP Virtual Memory |url= https://public.support.unisys.com/aseries/docs/ClearPath-MCP-20.0/86000387-514/section-000023206.html |website=Unisys}}</ref> use segmentation instead of paging, dividing virtual address spaces into variable-length segments. Using segmentation matches the allocated memory blocks to the logical needs and requests of the programs, rather than the physical view of a computer, although pages themselves are an artificial division in memory. The designers of the B5000 would have found the artificial size of pages to be [[Procrustes|Procrustean]] in nature, a story they would later use for the exact data sizes in the [[Burroughs B1700|B1000]].<ref name="“B1000-Procrustes">{{cite book |chapter=Design of the Burroughs B1700 |chapter-url= https://dl.acm.org/doi/10.1145/1479992.1480060 |website=ACM|date= 1972 |doi= 10.1145/1479992.1480060 |last1= Wilner |first1= W. T. |title= Proceedings of the December 5–7, 1972, fall joint computer conference, Part I on – AFIPS '72 (Fall, part I) |pages= 489–497 |isbn= 978-1-4503-7912-0 }}</ref>

In the Burroughs and Unisys systems, each memory segment is described by a master [[Data descriptor|descriptor]] which is a single absolute descriptor which may be referenced by other relative (copy) descriptors, effecting sharing either within a process or between processes. Descriptors are central to the working of virtual memory in MCP systems. Descriptors contain not only the address of a segment, but the segment length and status in virtual memory indicated by the 'p-bit' or 'presence bit' which indicates if the address is to a segment in main memory or to a secondary-storage block. When a non-resident segment (p-bit is off) is accessed, an interrupt occurs to load the segment from secondary storage at the given address, or if the address itself is 0 then allocate a new block. In the latter case, the length field in the descriptor is used to allocate a segment of that length.

A further problem to thrashing in using a segmented scheme is checkerboarding,<ref name="Checkerboarding">{{cite web |title=Checkerboarding |url= https://public.support.unisys.com/aseries/docs/ClearPath-MCP-20.0/86000387-514/section-000023184.html |website=Unisys}}</ref> where all free segments become too small to satisfy requests for new segments. The solution is to perform memory compaction to pack all used segments together and create a large free block from which further segments may be allocated. Since there is a single master descriptor for each segment the new block address only needs to be updated in a single descriptor, since all copies refer to the master descriptor.

Paging is not free from fragmentation – the fragmentation is internal to pages ([[internal fragmentation]]). If a requested block is smaller than a page, then some space in the page will be wasted. If a block requires larger than a page, a small area in another page is required resulting in large wasted space. The fragmentation thus becomes a problem passed to programmers who may well distort their program to match certain page sizes. With segmentation, the fragmentation is external to segments ([[external fragmentation]]) and thus a system problem, which was the aim of virtual memory in the first place, to relieve programmers of such memory considerations. In multi-processing systems, optimal operation of the system depends on the mix of independent processes at any time. Hybrid schemes of segmentation and paging may be used.

The [[Intel 80286]] supports a similar segmentation scheme as an option, but it is rarely used.

Segmentation and paging can be used together by dividing each segment into pages; systems with this memory structure, such as [[Multics]] and [[IBM System/38]], are usually paging-predominant, segmentation providing memory protection.<ref>{{Cite book|url = http://www.bitsavers.org/pdf/ge/GE-645/LSB0468_GE-645_System_Manual_Jan1968.pdf|title = GE-645 System Manual|pages = 21–30|date = January 1968|access-date = 25 February 2022}}</ref><ref>{{cite web|last1=Corbató |first1=F. J.|author-link=Fernando J. Corbató|last2=Vyssotsky |first2=V. A.|author2-link=Victor A. Vyssotsky|title=Introduction and Overview of the Multics System |url=http://www.multicians.org/fjcc1.html |access-date=13 November 2007 }}</ref><ref>{{cite web|last1=Glaser |first1=Edward L. |last2=Couleur |first2=John F. |last3=Oliver |first3=G. A. |name-list-style=amp |title=System Design of a Computer for Time Sharing Applications |url=http://www.multicians.org/fjcc2.html }}</ref>

In the [[Intel 80386]] and later [[IA-32]] processors, the segments reside in a [[32-bit]] linear, paged address space. Segments can be moved in and out of that space; pages there can "page" in and out of main memory, providing two levels of virtual memory; few if any operating systems do so, instead using only paging. Early non-hardware-assisted [[x86 virtualization]] solutions combined paging and segmentation because x86 paging offers only two protection domains whereas a VMM, guest OS or guest application stack needs three.<ref>{{Cite web|url=https://old.hotchips.org/wp-content/uploads/hc_archives/hc17/1_Sun/HC17.T1P2.pdf|first1=J. E. |last1=Smith |first2=R. |last2=Uhlig |date=14 August 2005 |title=''Virtual Machines: Architectures, Implementations and Applications'', HOTCHIPS 17, Tutorial 1, part 2}}</ref>{{rp|22}} The difference between paging and segmentation systems is not only about memory division; segmentation is visible to user processes, as part of memory model semantics. Hence, instead of memory that looks like a single large space, it is structured into multiple spaces.

This difference has important consequences; a segment is not a page with variable length or a simple way to lengthen the address space. Segmentation that can provide a single-level memory model in which there is no differentiation between process memory and file system consists of only a list of segments (files) mapped into the process's potential address space.<ref>{{Cite journal|last1=Bensoussan
|first1=André|last2=Clingen|first2=Charles T.|last3=Daley|first3=Robert C.|date=May 1972|title=The Multics Virtual Memory: Concepts and Design|journal=Communications of the ACM|volume=15|issue=5|pages=308–318|url=http://www.multicians.org/multics-vm.html|doi=10.1145/355602.361306|citeseerx=10.1.1.10.6731|s2cid=6434322}}</ref>

This is not the same as the mechanisms provided by calls such as [[mmap]] and [[Win32]]'s MapViewOfFile, because inter-file pointers do not work when mapping files into semi-arbitrary places. In Multics, a file (or a segment from a multi-segment file) is mapped into a segment in the address space, so files are always mapped at a segment boundary. A file's linkage section can contain pointers for which an attempt to load the pointer into a register or make an indirect reference through it causes a trap. The unresolved pointer contains an indication of the name of the segment to which the pointer refers and an offset within the segment; the handler for the trap maps the segment into the address space, puts the segment number into the pointer, changes the tag field in the pointer so that it no longer causes a trap, and returns to the code where the trap occurred, re-executing the instruction that caused the trap.<ref>{{cite web |title=Multics Execution Environment |url=http://www.multicians.org/exec-env.html |website=Multicians.org |access-date=9 October 2016}}</ref> This eliminates the need for a [[Linker (computing)|linker]] completely<ref name="denning" /> and works when different processes map the same file into different places in their private address spaces.<ref>{{Cite book|first=Elliott I.|last=Organick|title=The Multics System: An Examination of Its Structure|publisher=MIT Press|year=1972|isbn=978-0-262-15012-5|url-access=registration|url=https://archive.org/details/multicssystemex00orga}}</ref>