Main Memory

Dr. Noman Islam

http://sites.google.com/a/nu.edu.pk/noman-islam

​

• We must keep several processes in memory—that is, we must share memory.
• Separate per-process memory space protects the processes from each other and is fundamental to having multiple processes loaded in memory for concurrent execution
• We can provide this protection by using two registers, usually a base and a limit, as illustrated in Figure 8.1.
• The base register holds the smallest legal physical memory address; the limit register specifies the size of the range
• For example, if the base register holds 300040 and the limit register is 120900, then the program can legally access all addresses from 300040 through 420939 (inclusive).

• Any attempt by a program executing in user mode to access operating-system memory or other users’ memory results in a trap to the operating system, which treats the attempt as a fatal error
• The base and limit registers can be loaded only by the operating system, which uses a special privileged instruction

Binding

• Compile time: If you know at compile time where the process will reside in memory, then absolute code can be generated
• Load time. If it is not known at compile time where the process will reside in memory, then the compiler must generate relocatable code. In this case, final binding is delayed until load time.
• Execution time. If the process can be moved during its execution from one memory segment to another, then binding must be delayed until run time. Most general-purpose operating systems use this method.

Logical versus physical address

• An address generated by the CPU is commonly referred to as a logical address, whereas an address seen by the memory unit—that is, the one loaded into the memory-address register of the memory—is commonly referred to as a physical address.
• The set of all logical addresses generated by a program is a logical address space.
• The set of all physical addresses corresponding to these logical addresses is a physical address space.
• Thus, in the execution-time address-binding scheme, the logical and physical address spaces differ.

​

• The run-time mapping from virtual to physical addresses is done by a hardware device called the memory-management unit (MMU).
• The base register is now called a relocation register.
• The value in the relocation register is added to every address generated by a user process at the time the address is sent to memory
• For example, if the base is at 14000, then an attempt by the user to address location 0 is dynamically relocated to location 14000; an access to location 346 is mapped to location 14346.

• We now have two different types of addresses: logical addresses (in the range 0 to max) and physical addresses (in the range R + 0 to R + max for a base value R).
• The user program generates only logical addresses and thinks that the process runs in locations 0 to max.
• However, these logical addresses must be mapped to physical addresses before they are used.

Dynamic loading

• To obtain better memory-space utilization, we can use dynamic loading.
• With dynamic loading, a routine is not loaded until it is called.

Dynamic Linking and Shared Libraries

• Dynamically linked libraries are system libraries that are linked to user programs when the programs are run
• Dynamic linking, in contrast, is similar to dynamic loading.
• Here, though, linking, rather than loading, is postponed until execution time.
• This feature is usually used with system libraries, such as language subroutine libraries.

Swapping

• A process must be in memory to be executed. A process, however, can be swapped temporarily out of memory to a backing store and then brought back into memory for continued execution
• Mobile devices generally use flash memory rather than more spacious hard disks as their persistent storage.
• The resulting space constraint is one reason why mobile operating-system designers avoid swapping

• Apple’s iOS asks applications to voluntarily relinquish allocated memory. Read-only data (such as code) are removed from the system and later reloaded from flash memory if necessary.
• Android does not support swapping and adopts a strategy similar to that used by iOS.
• It may terminate a process if insufficient free memory is available.
• However, before terminating a process, Android writes its application state to flash memory so that it can be quickly restarted.

Contiguous Memory allocation

• One of the simplest methods for allocating memory is to divide memory into several fixed-sized partitions.
• Each partition may contain exactly one process.
• Thus, the degree of multiprogramming is bound by the number of partitions.
• In the variable-partition scheme, the operating system keeps a table indicating which parts of memory are available and which are occupied.
• Initially, all memory is available for user processes and is considered one large block of available memory, a hole.
• Eventually, as you will see, memory contains a set of holes of various sizes.

• First fit. Allocate the first hole that is big enough. Searching can start either at the beginning of the set of holes or at the location where the previous first-fit search ended. We can stop searching as soon as we find a free hole that is large enough.
• Best fit. Allocate the smallest hole that is big enough. Wemust search the entire list, unless the list is ordered by size. This strategy produces the smallest leftover hole.
• Worst fit. Allocate the largest hole. Again, we must search the entire list, unless it is sorted by size. This strategy produces the largest leftover hole, which may be more useful than the smaller leftover hole from a best-fit approach.

Fragmentation

• Both the first-fit and best-fit strategies for memory allocation suffer from external fragmentation
• Memory fragmentation can be internal as well as external. Consider a multiple-partition allocation scheme with a hole of 18,464 bytes. Suppose that the next process requests 18,462 bytes. If we allocate exactly the requested block, we are left with a hole of 2 bytes. The overhead to keep track of this hole will be substantially larger than the hole itself. The general approach to avoiding this problem is to break the physical memory into fixed-sized blocks and allocate memory in units based on block size. With this approach, the memory allocated to a process may be slightly larger than the requested memory. The difference between these two numbers is internal fragmentation—unused memory that is internal to a partition.

• One solution to the problem of external fragmentation is compaction. The goal is to shuffle the memory contents so as to place all free memory together in one large block.
• Another possible solution to the external-fragmentation problem is to permit the logical address space of the processes to be noncontiguous, thus allowing a process to be allocated physical memory wherever such memory is available.

Segmentation

• mapped the programmer’s view to the actual physical memory
• Each segment has a name and a length. The addresses specify both the segment name and the offset within the segment. The programmer therefore specifies each address by two quantities: a segment name and an offset.
• A C compiler might create separate segments for the following:
• The code
• Global variables
• The heap, from which memory is allocated
• The stacks used by each thread
• The standard C library

• Each entry in the segment table has a segment base and a segment limit.
• The segment base contains the starting physical address where the segment resides in memory, and the segment limit specifies the length of the segment.
• Segmentation permits the physical address space of a process to be noncontiguous

​

Paging

• The basic method for implementing paging involves breaking physical memory into fixed-sized blocks called frames and breaking logical memory into blocks of the same size called pages
• When a process is to be executed, its pages are loaded into any available memory frames from their source (a file system or the backing store). The backing store is divided into fixed-sized blocks that are the same size as the memory frames or clusters of multiple frames.

• The hardware support for paging is illustrated in Figure 8.10. Every address generated by the CPU is divided into two parts: a page number (p) and a page offset (d).
• The page number is used as an index in to a page table.
• The page table contains the base address of each page in physical memory.
• This base address is combined with the page offset to define the physical memory address that is sent to the memory unit

• The selection of a power of 2 as a page size makes the translation of a logical address into a page number and page offset particularly easy.
• If the size of the logical address space is 2m, and a page size is 2n bytes, then the high-order m− n bits of a logical address designate the page number, and the n low-order bits designate the page offset