Chapter 7:
Terms:
Frame: a fixed-length block of main memory
Page: A fixed-length block of data that resides in secondary memory. A page of data may be
temporarily copied into a frame of main memory
Segment: A variable-length block of data that resides in secondary memory. An entire segment
may temporarily be copied into an unavailable region of main memory (segmentation) or the
segment may be divided into pages which can be individually copied into main memory (combined
segmentation and paging)
Requirements that memory management is intended to satisfy:
1. 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 able to be swapped in and out of main memory in order to
maximise processor utilization
• Specifying that a process must be placed in the same memory region when it is
swapped back in would be limiting
o May need to relocate the process to a different area of memory
2. Protection
• Processes need to acquire permission to reference memory locations for reading and
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
3. 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 shard areas of memory without
compromising protection
• Mechanisms used to support relocation support sharing capabilities
4. Logical organisation
• Memory is organised as linear
• Programs are written in modules
o Modules can be written and compiled independently
o Different degrees of protection given to modules
o Sharing on a modular level corresponds to the user’s way of viewing the problem
• Segmentation is the tool that most reading satisfies requirements
5. Physical organisation
• Cannot leave the programmer with the responsibility to manage memory
• 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 the program
• Programmer does not know how much space will be available
Memory Partitioning:
Memory management brings processes into main memory for execution by the processor
• Involves virtual memory
• Based on segmentation and paging
Partitioning
• Used in several variations in some obsolete operating systems
• Does not involve virtual memory
Fixed Partitioning:
• May use of equal-size partitions or unequal-size partitions
• If all partitions are full and no process is in the Ready or Running state, the OS can swap a
process out of any of the partitions and load in another process so there is some work for
the processor
• Disadvantages of equal-size fixed partitions:
o A program may be too big to fit in a partition => program needs to be designed with
the use of overlays
o Main memory utilisation is inefficient
▪ Any program regardless of its size occupies an entire partition
▪ Internal fragmentation: wasted space due to the block of data loaded being
smaller than the partition
• Disadvantages of fixed partitions:
o The number of partitions specified at system generation time limits the number of
active processes in a system
o Small jobs will not utilise partition space efficiently
Dynamic Partitioning:
• Partitions are of variable length and number
• Process is allocated exactly as much memory as it requires
• This technique was used by IBM’s mainframe OS (OS/MVT)
• External fragmentation:
o Memory become more and more fragmented
o Memory utilisation declines
• Compaction:
o Technique for overcoming external fragmentation
o OS shifts process so that they are contiguous
o Free memory is together in one block
o Time consuming and wastes CPU time
• Placement Algorithms:
o Best-fit: choose the block that is closet in size to the request
o First-fit: begins to scan memory from the beginning and chooses the first available
block that is large enough
o Next-fit: begins to scan memory from the location of the last placement and chooses
the next available block that is large enough
Buddy system:
• Compromised of fixed and dynamic partitioning scheme
• Space available for allocations is treated as a single block
• Memory blocks are available of size 2K words, L ≤ K ≤ U, where
o 2L = smallest size block that is allocated
o 2U = largest size block that is allocated, generally 2U is the size of the entire memory
available for allocation
• Memory s is allocated such that
o 2U-1 < s < 2U
o Otherwise 2U block split into two equal 2U-1 blocks
Addresses:
Logical address: reference to a memory location independent of the current assignment of data to
memory
Relative address: address is expressed as a location relative to some known point
Physical or Absolute Address: actual location in main memory
Paging:
Partition memory into equal fixed-size chunks that are relatively small
Process is also divided into small fixed-size chucks of the same size
• Pages: chucks of a process
• Frames: available chunks of memory
Page table:
• Maintained by OS for each process
• Contains the frame location for each page in the process
• Processor must know how to access for the current process
• Used by processor to produce a physical address
Paging address translation:
• A consequence of using a page size of 2 is that the logical addresses are transparent to the
programmer, assembler and linker (they are the same as the relative address)
• Steps for paging address translation of a logical address of n + m nits:
o Extract the page number as the leftmost n bits of the logical address
o Use the page number as an index into the process page table to find the frame
number k
o The desired physical address is the concatenation of the frame number k and the
offset m
Segmentation:
A program may be subdivided into segments:
• May vary in length
• There is a maximum length
Addressing consists of two parts:
• Segment number
• An offset
Similar to dynamic partitioning however eliminates the problem of internal fragmentation
Are usually visible and provided as a convenience for organising programs and data
Typically the programmer will assign programs and data to different segments
For purpose of modular programming the program or data may be further broken down into
multiple segments
• The principal inconvenience of this service is that the programmer must be aware of the
maximum segment size limitation
Another consequence of unequal size segments is that there are no simple relations between
logical addresses and physical address
Steps for segmentation addresses translation of logical address of n + m bits:
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 fins 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 is greater or equal to 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 m
Loading:
First step to creation of an active process
Load a program into main memory to create process image
Three approaches:
• Absolute loading
• Relocatable loading
• Dynamic run-time loading
Linking:
Produce integrated program and data load from collection of object modules
Pass load module to loader
Linkage editor (static linking)
Dynamic linker:
• Load-time dynamic linking
• Run-time dynamic linking
• DLL hell