Memory Management Requirement

Memory management is intended to satisfy the following requirements:

• Relocation
• Protection
• Sharing
• Logical Organization
• Physical Organization

Relocation

Programmers typically do not know in advance which other programs will be resident in main memory at the time of execution of their program

Active processes need to be able to be swapped in and out of main memory in order to maximize processor utilization

Specifying that a process must be placed in the same memory region when it is swapped back in would be limiting

• may need to relocate the process to a different area of memory

These facts raise some technical concerns related to addressing, as illustrated in Figure 7.1. The figure depicts a process image.

The OS will need to know the location of:

• process control information
• the execution stack
• the entry point to begin the execution of the program for the process.

Because the operating system is managing memory and is responsible for bringing this process into main memory, these addresses are easy to come by.

However, the processor need to deal with memory references within the program.

• Branch instruction contain - an address to reference the instruction to be executed next.
• Data reference instruction - contain the address of the byte or word of data referenced.

So the processor and OS must be able to translate the memory references found in the code of the program into actual physical memory address

• reflecting the current location of the program in memory.

Protection

Processes need to acquire permission to reference memory locations for reading or writing purposes

Location of a program in main memory is unpredictable

Memory references generated by a process must be checked at run time

Mechanisms that support relocation also support protection

Memory protection must be satisfied by the processor rather than OS. why?

• OS cannot anticipate all the memory references that a program will make
• Time consuming to screen each program in advance for possible memory referenced violation.
• It is only possible to assess the permissibility of a memory reference at the time of execution of the instruction making reference.

Sharing

Advantageous to allow each process access to the same copy of the program rather than have their own separate copy

Memory management must allow controlled access to shared areas of memory without compromising protection

Mechanisms used to support relocation support sharing capabilities

Logical Organization

Almost invariably, main memory in a computer system is organized as a linear or one-dimensional address space, consisting of a sequence of bytes or words. Secondary memory, at its physical level, is similarly organized. While this organization closely mirrors the actual machine hardware, it does not correspond to the way in which program are typically constructed.

Most programs are organized into modules, some of which are unmodifiable (read only, execute only) and some of which contain data that may be modified. If the operating system and computer hardware can effectively deal with user programs and data in the form of modules of some sort, then a number of advantages can be realized:

• Modules can be written and compiled independently, with all references from one module to another resolved by the system at run time.
• With modest additional overhead, different degrees of protection (read only, execute only) can be given to different modules.
• It is possible to introduce mechanisms by which modules can be shared among processes. The advantage of providing sharing on a module level is that this corresponds to the user’s way of viewing the problem, hence it is easy for the user to specify the sharing that is desired.

Segmentation is the tool that most readily satisfies these requirements.

Physical Organization

Computer memory is organized into at least two levels: Main memory | Secondary memory —|— Fast access at high cost | Slower and cheaper Volatile | Not volatile Small capacity holds programs and data currently in use | Large capacity for long term storage of programs and data

The organization of the flow of information between main and secondary memory is a major system concern.

Cannot leave the programmer with the responsibility to manage memory, because

• Memory available for a program plus its data may be insufficient
  • overlaying allows various modules to be assigned the same region of memory but is time consuming to program
• Programmer does not know how much space will be available

Memory Management

Principal operation of memory management is to bring programs into memory for execution by the processor.

In most modern multiprogramming system it invokes virtual memory that use both segmentation and paging techniques.

Simpler technique that do not use virtual memory:

• Partitioning
  • Fixed Partitioning
    • Equal size
    • Non-equal size
  • Dynamic Partitioning
  • Buddy System
• Simple Paging
• Simple Segmentation

Partitioning

The simplest scheme for managing the available memory is to partition it into regions with fixed boundaries.

• Divide the memory to small size partition.

Two types of partitioning:

• Fixed Partitioning
• Dynamic Partitionings

Fixed Partitioning

Equal Size Partition

Divide the memory into same size partition

Any process whose size is less than or equal to the partition size can be loaded into an available partition

The operating system can swap out a process if all partitions are full and no process in the Ready or Running state

1. A program may not fit in a partition.
   • The programmer must design the program with “overlays”
     • Program and data are organized in such away that various modules can be assigned the same region of memory with a main program responsible for switching in and out as needed
2. Memory use is inefficient.
   • Any program, no matter how small, occupies an entire partition. This is called internal fragmentation. (If the memory allocated to the process is slightly larger than the memory demanded, then the difference between allocated and demanded memory is known as internal fragmentation.)
     • E.g. Program length 2MB, it occupies an 8MB partition. So 6MB is internal fragmentation.

Unequal Size Partition

Divide the memory into different partition size.

Using unequal size partitions helps lessen the problems

• A program as large as 16MB can be accommodate without need to overlays it.
• Partition smaller than 8MB allow smaller program to be accommodate with less internal fragmentation.

Placement Algorithm

Where to put / load process in memory.

Equal-size partitions:

• If there is an available partition, a process can be loaded into that partition because all partitions are of equal size, it does not matter which partition is used
• If all partitions are occupied by blocked processes, choose one process to swap out to make room for the new process

Unequal-size partitions:

• Multiple queues
• Single queues

Use of multiple queues

• Assign each process to the smallest partition within which it will fit
• A queue for each partition size
• Tries to minimize internal fragmentation
• Problem: some queues will be empty if no processes within a size range is present

Use of single queue

• When a process is loaded into memory, the smallest available partition that will hold the process is selected
• If all partitions are occupied:
  • Preference to swapping out the smallest partition that will hold the incoming process.
  • Also have to consider other factors such as priority and blocked vs. ready process.
• Increases the level of multiprogramming at the expense of internal fragmentation

Advantages and Disadvantages

Advantages	Disadvantages
Simple and require minimal OS software and processing overhead	The number of partitions specified at system generation time limits the number of active (not suspended) processes in the system.
Unequal-size partition provides a degree of flexibility to fixed partitioning	Because partition sizes are preset at system generation time, small jobs will not utilize partition space efficiently.

The used of fixed partitioning is almost unknown today.

Example of OS that use this technique was an early IBM mainframe OS, OS/MFT (Multiprogramming with a Fixed Number of Tasks).

Dynamic Partitioning

Partitions are of variable length and number

Each process is allocated exactly as much memory as it requires.

Used in IBM’s OS/MVT (Multiprogramming with a Variable number of Tasks)

An example using 64 MB of memory is shown in Figure 7.4.

Eventually holes are formed in the memory.

Memory will become more and more fragmented, and memory utilization declines.

This hole is called external fragmentation.

• Referring to fact that the memory is external to all partitions becomes increasingly fragmented.

Technique to overcome external fragmentation is called compaction.

• Time to time OS shifts the processes so that they are contiguous and so that all of free memory is together in one block.
• Disadvantages: time consuming and waste CPU time

From figure 7.4h, compaction will result in a block of free memory of length 16M, and this maybe sufficient to load an additional process.

Placement Algorithm

Where to put / load process in memory.

Best-fit	First-fit	Next-fit
Choose the block that is closest in size to the request	Begins to scan memory from the beginning and chooses the first available block that is large enough	Begins to scan memory from the location of the last placement and chooses the next available block that is large enough
Choose smallest hole	Choose first hole from beginning	Choose first hole from last placement

Buddy System

Both fixed and dynamic partitioning schemes have drawbacks.

An interesting compromise is the buddy system.

Space available for allocation is treated as a single block

Memory blocks are available of size 2^K words, L ≤ K ≤ U, where: 2^L = smallest size block that is allocated 2^U = larger size block that is allocated; generally 2^u is the size of the entire memory available for allocation.

Example shows in Figure 7.6 using 1MB initial block.

The first request, A, is for 100kb is needed.

• The initial block is divided into two 512k buddies.
  • The first of these is divided into two 256K buddies, and the first these is divided into two 128K buddies, one of which is allocated to A.

The next request B, requires 256K block. Such block is already available and is allocated.

The process continues with splitting and combine back into 256K, which immediately combine back with its buddy.

Figure 7.7 shows a binary tree representation of the buddy allocation immediately after the release B request.

The leaf nodes represent the current partitioning of the memory.

If two buddies are leaf nodes, then at least one must be allocated, otherwise they would be combine into a larger block.

Relocation

When program loaded into memory the actual (physical / absolute address ) memory locations are determined

A process may occupy different partitions which means different physical memory locations during execution

Compaction will also cause a program to occupy a different partition which means different physical memory locations

Thus the locations of instruction and data referenced by a process are not fixed.

Types of addresses

• Logical or Virtual
  • reference to a memory location independent of the current assignment of data to memory
• Relative
  • address is expressed as a location relative to some known point
• Physical or Absolute
  • actual location in main memory

Programs that employ relative addresses in memory used dynamic run-time loading.

It means all of the memory references in the loaded process are relative to the origin of the program.

Hardware mechanism is needed for translating relative addressed to physical memory addresses at the time of execution of the instruction that contain the reference.

Figure 7.8 shows the way in which this address translation is dynamically accomplished.

When a process is assigned to the Running state:

• Base register - loaded with the starting address in memory of the process.
• Bounds register - loaded with the address of the ending location of the process

These values must be set when the program is loaded into memory or when the process image is swapped in.

During execution of the process, relative address are encountered.

• These include the contents of the instruction register, instruction addresses that occur in branch and call instruction, and addresses that occur in load and store instruction.

Each relative address goes through two steps of manipulation by the processor:

1. The value in the base register is added to the relative address to produce an absolute address.
   • Address translation
2. The resulting address is compared to the value in the bound register
   • Check either address valid or not
   • If the address within bounds, then the instruction execution may proceed, otherwise an interrupt is generated to the OS which must respond to the error.

The scheme in Figure 7.8 allows programs to be swapped in and out of memory during execution.

It also provide a measure of protection:

• Each process image is isolated by the contents of the base and bounds registers and safe from unwanted accesses by other processes.

Paging

Partition memory into equal fixed-size

Process is also divided into equal fixedsize chunks of the same size as memory

• Pages - chunks of a process
• Frames - available chunks of memory

OS maintains a page table for each process.

• The page table shows the frames location of each page of the process.
  • Used by processor to produce a physical address
• OS also maintains a single free frame list of all frames in memory that are currently occupied and available pages

Simple paging similar to fixed partitioning but the different are:

• In paging the partitions are rather small
• Program may occupy more than one partitions and no need to be contiguous.

Within the program, each logical address consists of a page number and an offset within the page.

Logical to physical address translation is done by processor and the processor must know how to access the page table of current process.

Presented with a logical address (page #, offset), the processor uses the page table to produce a physical address (frame #, offset).

Address Translation

The following steps are needed for address translation:

1. Extract the page number as the leftmost n bits of the logical address.
2. Use the page number as an index into the process page table to find the frame number k.
3. The starting physical address of the frame is k X 2m, and the physical address of the referenced byte is that number plus the offset. This physical address need not be calculated; it is easily constructed by appending the frame number to the offset.

Consider 16bit addresses are used, and the page size is 1Kb

• Logical Address = 0000010111011110
• Page Number used 6 bits and Offset used 10 bits
  • 000001 0111011110
  • Page number = 1 Offset = 478

This page 1 is residing in memory frame 6 = binary 000110.

• Physical address = 0001100111011110
  • 000110 0111011110
  • Frame Number = 6 Offset = 478

Summary

Memory is divided into small equal-size frames.

Each process is divided into frame-size pages

Smaller processes require fewer pages, larger processes require more.

When a process is brought in, all of its pages are loaded into available frames, and a page table is set up.

This approach solves many problems inherent in partitioning.

Segmentation

A program can be subdivided into segments

Segments vary in length

Have the maximum segment

Addresses consists of:

• Segment#

  Offset

Similar to dynamic partitioning the different is that with segmentation a program may occupy more than one partition and these partitions does not need to be contiguous.

Eliminates internal fragmentation but external fragmentation still exist

• However because a process is broken up into a number of smaller pieces, the external fragmentation should be less.

Paging is invisible for the programmer but segmentation is visible and is provided as a convenience for organizing programs and data.

• Programmer or compiler will assign programs and data to different segments
• For modular programming, the program or data may be further broken down into multiple segments
• The principal inconvenience is that the programmer must be aware of the maximum segment size limittion.

Address Translation

No simple relationship between logical addresses and physical addresses (like paging).

Every process will have a segment table

Analogous form paging, a simple segmentation scheme would make use of segment table for each process and a list of free blocks of memory.

Each segment table entry would have to give the starting address in memory of the corresponding segment.

The entry should also provide the length of the segment, to assure that invalid addresses are not used.

When process enters the Running state, the address of its segment table is loaded into a special register used by the memory management hardware.

Every process will have a segment table that consists of:

• Segment Number

  Length

  Base

  • Segment Number: the segment numbr of a process
  • Length: length of the segment
  • Base: starting address of the segment in memory

Length will be used to assure that invalid addresses are not used.

Consider 16bit addresses, maximum number of segments is 16.

Logical Address = 0001001011110000

Segment Number used 4 bits and Offset used 12 bits

• 0001 100111011110
• Segment Number = 1 Offset = 752

The following steps are needed for address translation:

1. Extract the segment number as the leftmost n bits of the logical address.
2. Use the segment number as an index into the process segment table to find the starting physical address of the segment.
3. Compare the offset, expressed in the rightmost m bits, to the length of the segment. If the offset greater than the length, the address is invalid.
4. The desired physical address is the sum of the starting physical address of the segment plus the offset.

Summary

A process is divided into a number of segments which need not be equal size.

When a process brought in, all of its segments are loaded into available regions of memory, and a segment table is setup.