Memory segmentation

Last updated

Memory segmentation is an operating system memory management technique of dividing a computer's primary memory into segments or sections. In a computer system using segmentation, a reference to a memory location includes a value that identifies a segment and an offset (memory location) within that segment. Segments or sections are also used in object files of compiled programs when they are linked together into a program image and when the image is loaded into memory.

Contents

Segments usually correspond to natural divisions of a program such as individual routines or data tables [1] so segmentation is generally more visible to the programmer than paging alone. [2] Segments may be created for program modules, or for classes of memory usage such as code segments and data segments. [3] Certain segments may be shared between programs. [1] [2]

Segmentation was originally invented as a method by which system software could isolate software processes (tasks) and data they are using. It was intended to increase reliability of the systems running multiple processes simultaneously. [4]

Hardware implementation

In a system using segmentation, computer memory addresses consist of a segment id and an offset within the segment. [3] A hardware memory management unit (MMU) is responsible for translating the segment and offset into a physical address, and for performing checks to make sure the translation can be done and that the reference to that segment and offset is permitted.

Each segment has a length and set of permissions (for example, read, write, execute) associated with it. [3] A process is only allowed to make a reference into a segment if the type of reference is allowed by the permissions, and if the offset within the segment is within the range specified by the length of the segment. Otherwise, a hardware exception such as a segmentation fault is raised.

Segments may also be used to implement virtual memory. In this case each segment has an associated flag indicating whether it is present in main memory or not. If a segment is accessed that is not present in main memory, an exception is raised, and the operating system will read the segment into memory from secondary storage.

Segmentation is one method of implementing memory protection. [5] Paging is another, and they can be combined. The size of a memory segment is generally not fixed and may be as small as a single byte. [6]

Segmentation has been implemented several ways on various hardware, with or without paging. Intel x86 memory segmentation does not fit either model and is discussed separately below, and also in greater detail in a separate article.

Segmentation without paging

Associated with each segment is information that indicates where the segment is located in memory— the segment base. When a program references a memory location, the offset is added to the segment base to generate a physical memory address.

An implementation of virtual memory on a system using segmentation without paging requires that entire segments be swapped back and forth between main memory and secondary storage. When a segment is swapped in, the operating system has to allocate enough contiguous free memory to hold the entire segment. Often memory fragmentation results if there is not enough contiguous memory even though there may be enough in total.

Segmentation with paging

Instead of a memory location, the segment information includes the address of a page table for the segment. When a program references a memory location the offset is translated to a memory address using the page table. A segment can be extended by allocating another memory page and adding it to the segment's page table.

An implementation of virtual memory on a system using segmentation with paging usually only moves individual pages back and forth between main memory and secondary storage, similar to a paged non-segmented system. Pages of the segment can be located anywhere in main memory and need not be contiguous. This usually results in a reduced amount of input/output between primary and secondary storage and reduced memory fragmentation.

History

The Burroughs Corporation B5000 computer was one of the first to implement segmentation, and "perhaps the first commercial computer to provide virtual memory" [7] based on segmentation. The B5000 is equipped with a segment information table called the Program Reference Table (PRT) which is used to indicate whether the corresponding segment resides in the main memory, to maintain the base address and the size of the segment. [8] The later B6500 computer also implemented segmentation; a version of its architecture is still in use today on the Unisys ClearPath Libra servers.

The GE 645 computer, a modification of the GE-635 with segmentation and paging support added, was designed in 1964 to support Multics.

The Intel iAPX 432, [9] begun in 1975, attempted to implement a true segmented architecture with memory protection on a microprocessor.

The 960MX version of the Intel i960 processors supported load and store instructions with the source or destination being an "access descriptor" for an object, and an offset into the object, with the access descriptor being in a 32-bit register and with the offset computed from a base offset in the next register and from an additional offset and, optionally, an index register specified in the instruction. An access descriptor contains permission bits and a 26-bit object index; the object index is an index into a table of object descriptors, giving an object type, an object length, and a physical address for the object's data, a page table for the object, or the top-level page table for a two-level page table for the object, depending on the object type. [10]

Prime, Stratus, Apollo, IBM System/38, and IBM AS/400 (including IBM i) computers use memory segmentation.

Examples

Burroughs large system architectures

B5000

Descriptors in the B5000, B5500 and B5700 reside in either the Program Reference Table (PRT) or the stack, and contain a presence bit indicating whether the data are present in memory. There are distinct data and program descriptors.

B6500

Multics architectures

S/370 architecture

In the IBM System/370 models [lower-alpha 1] with virtual storage [11] [12] (DAT) and 24-bit addresses, control register 0 specifies a segment size of either 64 KiB or 1 MiB and a page size of either 2 KiB or 4 KiB; control register 1 contains a Segment Table Designator (STD), which specifies the length and real address of the segment table. Each segment table entry contains a page table location, a page table length and an invalid bit. IBM later expanded the address size to 31 bits and added two bits to the segment table entries:

Segment-protection bit
Segment is read-only
Common-segment bit
The segment is shared between address spaces; this bit is set to optimize TLB use

Each of IBM's DAT implementations includes a translation cache, which IBM called a Translation Lookaside Buffer (TLB). While Principles of Operation discusses the TLB in general terms, the details are not part of the architecture and vary from model to model.

Starting with the 3031, 3032, and 3033 processor complexes, IBM offered a feature called Dual-address Space [12] : 5-13–5-17, Dual-Address-Space Control : 5-17–5-20, DAS Authorization Mechanisms : 5-21–5-24, PC-Number Translation  [13] (DAS), which allows a program to switch between the translation tables for two address spaces, referred to as primary address space (CR1) and secondary address space (CR7), and to move data between the address spaces subject to protection key. DAS supports a translation table to convert a 16-bit address space number (ASN) to an STD, with privileged instructions to load the STD into CR1 (primary) or CR7 (secondary).

x86 architecture

Early x86 processors, beginning with the Intel 8086, provide crude memory segmentation and no memory protection. (Every byte of every segment is always available to any program.) The 16-bit segment registers allow for 65,536 segments; each segment begins at a fixed offset equal to 16 times the segment number; the segment starting address granularity is 16 bytes. Each segment grants read-write access to 64 KiB (65,536 bytes) of address space (this limit is set by the 16-bit PC and SP registers; the processor does no bounds checking). Offset+address exceeding 0xFFFFF wraps around to 0x00000. Each 64 KiB segment overlaps the next 4,095 segments; each physical address can be denoted by 4,096 segment–offset pairs. This scheme can address only 1 MiB (1024 KiB) of physical memory (and memory-mapped i/o). (Optional expanded memory hardware can add bank-switched memory under software control.) Intel retroactively named the sole operating mode of these x86 CPU models "real mode".

The Intel 80286 and later processors add "286 protected mode", which retains 16-bit addressing, and adds segmentation (without paging) and per-segment memory protection. For backward compatibility, all x86 CPUs start up in "real mode", with the same fixed overlapping 64 KiB segments, no memory protection, only 1 MiB physical address space, and some subtle differences (high memory area, unreal mode). In order to use its full 24-bit (16 MiB) physical address space and advanced MMU features, an 80286 or later processor must be switched into "protected mode" by software, usually the operating system or a DOS extender. If a program does not use the segment registers, or only puts values into them that it receives from the operating system, then identical code can run in real mode or protected mode, but most real-mode software computes new values for the segment registers, breaking this compatibility.

The Intel i386 and later processors add "386 protected mode", which uses 32-bit addressing, retains segmentation, and adds memory paging. In these processors, the segment table, rather than pointing to a page table for the segment, contains the segment address in linear memory. When paging is enabled, addresses in linear memory are then mapped to physical addresses using a separate page table. Most operating systems did not use the segmentation capability, despite possible advantages (4 x 4GiB logical address space instead of only 4 GiB), opting to keep the base address in all segment registers equal to 0 at all times and provide per-page memory protection and swapping using only paging. Some use the CS register to provide executable space protection on processors lacking the NX bit or use the FS or GS registers to access thread-local storage. [14] [15]

The x86-64 architecture does not support segmentation in "long mode" (64-bit mode). [16] Four of the segment registers: CS, SS, DS, and ES are forced to 0, and the limit to 264. The segment registers FS and GS can still have a nonzero base address. This allows operating systems to use these segments for special purposes such as thread-local storage. [14] [15]

See also

Notes

  1. ↑ Models 115, 125, 135, 138, 145, 148, 155 II, 158, 165 II, and 168

Related Research Articles

<span class="mw-page-title-main">Virtual memory</span> Computer memory management technique

In computing, virtual memory, or virtual storage, is a memory management technique that provides an "idealized abstraction of the storage resources that are actually available on a given machine" which "creates the illusion to users of a very large (main) memory".

x86 Family of instruction set architectures

x86 is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was introduced in 1978 as a fully 16-bit extension of Intel's 8-bit 8080 microprocessor, with memory segmentation as a solution for addressing more memory than can be covered by a plain 16-bit address. The term "x86" came into being because the names of several successors to Intel's 8086 processor end in "86", including the 80186, 80286, 80386 and 80486 processors. Colloquially, their names were "186", "286", "386" and "486".

In computer architecture, 64-bit integers, memory addresses, or other data units are those that are 64 bits wide. Also, 64-bit central processing units (CPU) and arithmetic logic units (ALU) are those that are based on processor registers, address buses, or data buses of that size. A computer that uses such a processor is a 64-bit computer.

x86 memory segmentation refers to the implementation of memory segmentation in the Intel x86 computer instruction set architecture. Segmentation was introduced on the Intel 8086 in 1978 as a way to allow programs to address more than 64 KB (65,536 bytes) of memory. The Intel 80286 introduced a second version of segmentation in 1982 that added support for virtual memory and memory protection. At this point the original mode was renamed to real mode, and the new version was named protected mode. The x86-64 architecture, introduced in 2003, has largely dropped support for segmentation in 64-bit mode.

In computing, protected mode, also called protected virtual address mode, is an operational mode of x86-compatible central processing units (CPUs). It allows system software to use features such as segmentation, virtual memory, paging and safe multi-tasking designed to increase an operating system's control over application software.

<span class="mw-page-title-main">Memory management unit</span> Hardware translating virtual addresses to physical address

A memory management unit (MMU), sometimes called paged memory management unit (PMMU), is a computer hardware unit that examines all memory references on the memory bus, translating these requests, known as virtual memory addresses, into physical addresses in main memory.

x86 assembly language is the name for the family of assembly languages which provide some level of backward compatibility with CPUs back to the Intel 8008 microprocessor, which was launched in April 1972. It is used to produce object code for the x86 class of processors.

x86-64 64-bit version of x86 architecture

x86-64 is a 64-bit version of the x86 instruction set, first announced in 1999. It introduced two new modes of operation, 64-bit mode and compatibility mode, along with a new 4-level paging mode.

The Burroughs Large Systems Group produced a family of large 48-bit mainframes using stack machine instruction sets with dense syllables. The first machine in the family was the B5000 in 1961, which was optimized for compiling ALGOL 60 programs extremely well, using single-pass compilers. The B5000 evolved into the B5500 and the B5700. Subsequent major redesigns include the B6500/B6700 line and its successors, as well as the separate B8500 line.

Flat memory model or linear memory model refers to a memory addressing paradigm in which "memory appears to the program as a single contiguous address space." The CPU can directly address all of the available memory locations without having to resort to any sort of bank switching, memory segmentation or paging schemes.

Memory protection is a way to control memory access rights on a computer, and is a part of most modern instruction set architectures and operating systems. The main purpose of memory protection is to prevent a process from accessing memory that has not been allocated to it. This prevents a bug or malware within a process from affecting other processes, or the operating system itself. Protection may encompass all accesses to a specified area of memory, write accesses, or attempts to execute the contents of the area. An attempt to access unauthorized memory results in a hardware fault, e.g., a segmentation fault, storage violation exception, generally causing abnormal termination of the offending process. Memory protection for computer security includes additional techniques such as address space layout randomization and executable space protection.

<span class="mw-page-title-main">Memory address</span> Reference to a specific memory location

In computing, a memory address is a reference to a specific memory location used at various levels by software and hardware. Memory addresses are fixed-length sequences of digits conventionally displayed and manipulated as unsigned integers. Such numerical semantic bases itself upon features of CPU, as well upon use of the memory like an array endorsed by various programming languages.

In computing, position-independent code (PIC) or position-independent executable (PIE) is a body of machine code that, being placed somewhere in the primary memory, executes properly regardless of its absolute address. PIC is commonly used for shared libraries, so that the same library code can be loaded at a location in each program's address space where it does not overlap with other memory in use by, for example, other shared libraries. PIC was also used on older computer systems that lacked an MMU, so that the operating system could keep applications away from each other even within the single address space of an MMU-less system.

<span class="mw-page-title-main">General protection fault</span>

A general protection fault (GPF) in the x86 instruction set architectures (ISAs) is a fault initiated by ISA-defined protection mechanisms in response to an access violation caused by some running code, either in the kernel or a user program. The mechanism is first described in Intel manuals and datasheets for the Intel 80286 CPU, which was introduced in 1983; it is also described in section 9.8.13 in the Intel 80386 programmer's reference manual from 1986. A general protection fault is implemented as an interrupt. Some operating systems may also classify some exceptions not related to access violations, such as illegal opcode exceptions, as general protection faults, even though they have nothing to do with memory protection. If a CPU detects a protection violation, it stops executing the code and sends a GPF interrupt. In most cases, the operating system removes the failing process from the execution queue, signals the user, and continues executing other processes. If, however, the operating system fails to catch the general protection fault, i.e. another protection violation occurs before the operating system returns from the previous GPF interrupt, the CPU signals a double fault, stopping the operating system. If yet another failure occurs, the CPU is unable to recover; since 80286, the CPU enters a special halt state called "Shutdown", which can only be exited through a hardware reset. The IBM PC AT, the first PC-compatible system to contain an 80286, has hardware that detects the Shutdown state and automatically resets the CPU when it occurs. All descendants of the PC AT do the same, so in a PC, a triple fault causes an immediate system reset.

The NX bit (no-execute) is a technology used in CPUs to segregate areas of a virtual address space to store either data or processor instructions. An operating system with support for the NX bit may mark certain areas of an address space as non-executable. The processor will then refuse to execute any code residing in these areas of the address space. The general technique, known as executable space protection, also called Write XOR Execute, is used to prevent certain types of malicious software from taking over computers by inserting their code into another program's data storage area and running their own code from within this section; one class of such attacks is known as the buffer overflow attack.

Descriptors are an architectural feature of Burroughs large systems, including the current Unisys Clearpath/MCP systems. Apart from being stack- and tag-based, a notable architectural feature of these systems is that it is descriptor-based. Descriptors are the means of having data that does not reside on the stack as for arrays and objects. Descriptors are also used for string data as in compilers and commercial applications.

In computing, the x86 memory models are a set of six different memory models of the x86 CPU operating in real mode which control how the segment registers are used and the default size of pointers.

The Global Descriptor Table (GDT) is a data structure used by Intel x86-family processors starting with the 80286 in order to define the characteristics of the various memory areas used during program execution, including the base address, the size, and access privileges like executability and writability. These memory areas are called segments in Intel terminology.

The task state segment (TSS) is a structure on x86-based computers which holds information about a task. It is used by the operating system kernel for task management. Specifically, the following information is stored in the TSS:

In operating systems, memory management is the function responsible for managing the computer's primary memory.

References

  1. 1 2 Holt, Anatol W. (1961). "Program Organization and Record Keeping for Dynamic Storage Allocation". Communications of the ACM. 4 (10): 422–431. doi: 10.1145/366786.366795 . S2CID   18973700.
  2. 1 2 Englander, Irv (2003). The architecture of computer hardware and systems software (3rd ed.). Wiley. ISBN   0-471-07325-3.
  3. 1 2 3 Glaser, Edward L.; Couleur, John F.; Oliver, G. A. (1965). System Design of a Computer for Time Sharing Applications. 1965 Fall Joint Computer Conference.
  4. ↑ "1.2 Memory Management". AMD64 Technology AMD64 Architecture Programmer's Manual Volume 2: System Programming (PDF). Vol. 2. Advanced Micro Devices. 2018. p. 5.
  5. ↑ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). "Segmentation" (PDF). Operating Systems: Three Easy Pieces. Arpaci-Dusseau Books.
  6. ↑ Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3 (3A, 3B & 3C): System Programming Guide (PDF). Intel Corporation. 2012. pp. 3–13.
  7. ↑ Mayer, Alastair J. W. "The Architecture of the Burroughs B5000 - 20 Years Later and Still Ahead of the Times?" . Retrieved 2012-03-15.
  8. ↑ Hayes, John P. (1978). Computer Architecture and Organization. p. 371. ISBN   0-07-027363-4.
  9. ↑ Introduction to the IAPX 432 Architecture (PDF). Intel Corporation. 1981. p. 78.
  10. ↑ BiiN CPU Architecture Reference Manual (PDF). BiiN. July 1998.
  11. ↑ "Dynamic Address Translation" (PDF). IBM System/370 Principles of Operation (PDF). Systems (Fourth ed.). IBM. September 1974. pp. 57–68. GA22-7000-4.
  12. 1 2 "Dynamic Address Translation". IBM System/370 Principles of Operation (Eleventh ed.). IBM. September 1987. pp. 3-20–3-38. GA22-7000-10.
  13. ↑ "Address spaces" (PDF). IBM System/370 Extended Architecture Principles of Operation (PDF) (Second ed.). IBM. January 1987. pp. 3-13–3-14. SA22-7085-1.
  14. 1 2 Matt Pietrek (May 2006). "Everything You Need To Know To Start Programming 64-Bit Windows Systems". Microsoft. Retrieved 2023-04-18.
  15. 1 2 Drepper, Ulrich (2013-08-22). "ELF Handling For Thread-Local Storage" (PDF).
  16. ↑ AMD64 Technology AMD64 Architecture Programmer's Manual Volume 2: System Programming (PDF). Vol. 2. Advanced Micro Devices. 2018.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.