Managing Your Memory

Another key role of the Operating System is to manage memory resources, there are two separate conceptual levels of memory. Firstly, physical memory – this is what the operating system sees, and it relates directly to your actual physical hardware. Secondly, there is virtual memory, which is what a programmer will see when developing an application to run within an operating system. Virtual memory is viewed as limitless, and is not dependent on the physical memory available – so applications can be programmed to run on systems with different physical memory capabilities.

Binding and Linking

Binding is the process in compilation of binding symbolic addresses (such as variable names), to relocatable addresses (such as n bytes from the start of this module). The linkage editor or loader will later bind these relocatable addresses to absolute memory addresses (such as 74014)

Binding may happen in three places:

• Compile Time: This generates abosolute code that references absolute memory addresses. Example is MS-DOS .COM files
• Load Time: Binding takes place when file is loaded,
• Execution Time: Binding takes place only when code is run, allows programs to move memory space even during execution. This requires the hardware to have a memory management unit (MMU)

Linking may also be delayed until run time, this allows multiple programs to share the same library routines, with the libraries only having to be loaded once into memory

Programs execute “stubs”, which see if a library is loaded in memory, if it is they link to it’s location, if its not they load it then replace themselves with a link to its location.

Memory Allocation

Where possible memory should be allocated contiguously, meaning that “free” memory is kept together.

There are three main systems for allocating memory:

◊ Best Fit

◊ Worst Fit

◊ First Fit

Fragmentation

Fragmentation can be internal or external, and relates to wasted memory space:

External Fragmentation: There is enough total memory to fulfil a process’s requirements, however there is not enough contiguous memory to allocate the process to one block of memory.

Internal Fragmentation: Generally, holes are broken into fixed sizes, or blocks. A process may leave wasted space in its block however, which is wasting memory and can lead to cavity viruses.

Paging

Paging is a scheme which prevents memory allocation needing to be contiguous. This makes memory use more efficient.

• Physical memory is broken into fixed blocks, called frames.
• Logical memory is broken into fixed blocks (of the same size), called pages.
• A page table contains the base address of each page in physical memory

When a process executes, its pages are loaded into any available frames. Addresses are considored as page numbers (p) and page offsets (d). The page number can be used to lookup the memory address in the page table, and the offset relates to the exact address within the frame.

The page table is kept in main memory, and is governed by the page-table base register (a pointer to the page table_ and the page-table length register (which indicates the size of the page table).

Memory protection can be implemented by associating a protection bit with each frame, additionally a valid-invalid bit can be attached to each entry (again in the page table) where valid indicates the the associated page is in the process’ logical address space and is thus legal, and invalid indicates the page is not in the processes’ logical address space.

Segmentation

Segmentation is a memory management scheme which supports a user view of memory, it views programs as a collection of segments, where each segment is a logical unit such as a main program, procedure, function or stack.

Virtual Memory

Virtual memory is the capability of the operating system that enables programs to address more memory locations than are actually provided in main memory. Virtual memory systems help remove much of the burden of memory management from the programmers, freeing them to concentrate on application development.

[Deitel et. al., 2004]

With virtual memory, the logical address space is much larger than the physical address space, and pages are swapped (paged) in and out of main memory. The operating system maintains a list of the free frames in the physical address space, and brings pages into memory when they are required. Each process visualises the address space as a contiguous block of memory, although only part of a process need be loaded into memory for it to execute.

When a process addresses a page, it is looked up in the page table, the valid-invalid bit is checked, if it is valid then the page is already in memory, if it is invalid then the page is brought to memory (after checking the request is valid, and the process should have access to the frame – known as handling a page fault trap). If there are no free frames in memory, then an algorithm will look for a page which is loaded but no longer in use and replace it. Thrashing is the term for a process which spends more time paging than doing actual work.

There are a number of different algorithms for finding pages which can be replaced:

• Evaluate Algorithm. This runs each algorithm on a particular string of memory references, computes the number of page faults per algorithm and then chooses the one with the lowest possible number of page faults.
• FIFO Algorithm. Every page is associated with the time it was brought into memory, the oldest page is replaced first.
• Optimal Algorithm. The page which will not be needed for the longest period of time is switched out, this will always return the fewest page faults.
• Least Recently Used (LRU). Every page is associated with the time it was last used, the page which has not been used in the longest time is replaced first.

Belady’s Anomaly notes that with some algorithms, the number of page faults may increase as the number of allocated frames increases. Initially, this may seem counter-intuitive, but some combinations of page demands will have fewer page faults with a smaller number of available frames. The LRU algorithm is an example of a “counter algorithm”, and is one which will never exhibit this anomaly,

Working Set Model

The working set model states that a process can be in RAM if and only if all of the pages that it is currently using (the most recently used pages) can be in RAM. The model is an all or nothing model, meaning if the pages it needs to use increases, and there is no room in RAM, the process is kicked from memory to free the memory for other processes to use.

[Wikipedia – http://en.wikipedia.org/wiki/Working_set ]

The working set model is a system for trying to reduce the amount of trashing processes (processes which spend more time paging than doing actual work). This occurs when the total size of a locality (part of a process) is greater than the size of the total memory.

We define a working set window, $$ \Delta $$ of a fixed number of page references, for example 10,000 instructions.

$$!
\mbox{If } \Delta \mbox{ is too small it will not encompass a whole locality}\\
\mbox{If } \Delta \mbox{ is large it can encompass several localities} \\
\mbox{If } \Delta \to \infty \mbox { then it can encompass the entire program } $$

Next, we define $$ D $$ as the sum of all the pages referenced by all the processes in our $$ \Delta $$ (or the number of frames demanded in the period), and $$ m $$ as the total number of available frames.

$$!
\mbox{If } D > m \Rightarrow \mbox{ Thrashing is occuring }
$$

The policy of the working set model is then to suspend one of the processes when thrashing occurs, to reduce the demand and create more free frames. In practice, this is often done with an interval timer and reference bit, when a page is referenced its reference bit is set to 1 – making it part of the working set, each time the timed interval occurs all reference bits are reset to 0.

References:

• Janet Lavery – Durham University Computer Systems, Operating Systems Lecture 6, 2007
• Janet Lavery – Durham University Computer Systems, Operating Systems Lecture 7, 2007