Operating Systems

Computer Science Department

UU
July 2019
Chapter Six

Memory Management

2
Chapter Objectives
◼To provide a detailed description of various ways of
organizing memory hardware.
◼To discuss various memory-management techniques,
including paging and segmentation.

3
Topics Included
◼ Introduction
◼ Basic Memory Management
◼ Multiprogramming with variable partitions – swapping
◼ Virtual Memory
◼ Paging
◼ Page Replacement Algorithms
◼ Segmentation

4
Introduction
◼ Memory is one of the most important resources of the computer system
that is used to store data and programs temporarily.
◼ Program must be brought into memory and placed within a process for it to
be run.
◼ Ideally programmers want memory that is:
◼ large
◼ fast
◼ non volatile

◼ Memory hierarchy:
◼ small amount of fast, expensive memory – cache.
◼ some medium-speed, medium price main memory.
◼ gigabytes of slow, cheap disk storage.
◼ Operating system coordinate how these memories are used.

5
Introduction(cont’d)
◼Part of the operating system that manages memory is called
the memory manager (MM).
◼The main functions of the MM are the following:
◼ Keeping track of which part of memory are in use and which parts are
free.
◼ Allocating and de-allocating memory to processes.
◼ Managing swapping between memory and disk when memory is not big
enough to hold all the processes.

◼A good memory manager has the following attributes.

◼ It allows all processes to run.
◼ Its memory (space used for the management activity) overhead must be
reasonable.
◼ Its time overhead (time required for the management activity) is
reasonable.

6
Basic Memory Management
◼Memory management systems can be divided into two basic
classes:
◼ those that move processes back and forth between main memory and
disk during execution (swapping and paging),
◼ and those that do not:

◼Mono-programming – Only one process will be in the memory

in addition to the operating system.
◼Multiprogramming - It allows multiple programs to run in
parallel. Divides the memory among concurrently running
processes and the operating system.

7
Monoprogramming without Swapping or Paging

Three simple ways of organizing memory

(a) formerly used on mainframes and minicomputers but is rarely used any
more.
(b) used on embedded systems.
(c) used by early personal computers.
8
Memory Partitioning
◼In order to run multiple programs in parallel a memory should
be partitioned.
◼There are two partitioning options – fixed partitioning and
dynamic partitioning.
◼ Fixed partitioning – partitioning is done before the processes comes to
memory.
◼ Dynamic partitioning – partitioning is done when processes request
memory space.

1. Fixed partitioning
◼ It is the simplest and oldest partitioning technique.
◼ Variations of fixed partitioning.
◼ Equal sized fixed partitions
◼ Unequal sized fixed partitions
9
Equal sized fixed partitions
◼ The memory is partitioned into equal-sized partitions.
◼ Any process whose size is less than or equal to the partition size can be
loaded into any available partition.
◼ If all partitions are occupied with processes that are not ready to run, then
one of these processes is swapped-out and a new process is loaded or a
suspended process is swapped in and loaded.
◼ Advantage: It is simple to implement and requires minimal management
overhead.
◼ Problems:
◼ A program may be too big to fit into a partition.
◼ Inefficient use of memory due to internal fragmentation.
◼ Can happen if there is hole of size 15,000 bytes and a process needs 14,900 bytes;
Keeping a hole of size 100 bytes is not worth the effort so the process is allocated
15,000 bytes.
◼ The size difference of 100 bytes is memory internal to a partition, but not being used.
10
Example of Fixed Partitioning

11
Unequal sized fixed partitioning
◼ Memory is partitioned into unequal-sized fixed partitions.
◼ In this case there are two memory allocation schemes:
◼ Using multiple queues.
◼ Using a single queue.
◼ Using multiple queues
◼ Each partition has its own queue.
◼ A process is assigned to the smallest partition within which it will fit and it can
only be loaded into the partition it belongs.
◼ Advantage: Minimize internal fragmentation.
◼ Disadvantage processes are waiting in some other queues: Some partitions
may remain unused.

12
Unequal sized fixed partitioning(cont’d)

◼ separate input queues for each partition

(a) Multiple input queue

(b) Single input queue

13
Unequal sized fixed partitioning(cont’d)
◼ Using single queue
◼ The smallest available partition that can hold the process is selected.
◼ Whenever a partition becomes free, the process closest to the front of the
queue that fits in it could be loaded into the empty partition.
◼ Advantage: Partitions are used all the time.
◼ Disadvantage: When best fit is searched, it will not give small jobs best
service, as they are interactive. A possible remedy for this problem is
not to allow small processes not to be skipped more than k – times.
◼ Summary
◼ Advantage of fixed partitioning.
◼ It is simple to implement and requires minimal management overhead.
◼ Disadvantages of fixed partitioning.
◼ Inefficient use of memory due to internal fragmentation.
◼ Limits number of active processes.
◼ A program may be too big to fit in any of the partitions.

14
2. Dynamic partitioning
◼Partitions are created dynamically during the allocation of
memory.
◼The size and number of partitions vary throughout of the
operation of the system.
◼Processes will be allocated exactly as much memory they
require.

◼If there is not enough main memory to hold all the currently
active processes, so excess processes must be kept on disk
and brought in to run dynamically.

15
Dynamic partitioning(cont’d)
◼Dynamic partitioning leads to a situation in which there are a
lot of small useless holes in memory. This phenomenon is
called external fragmentation.
◼Solution to external fragmentation is compaction – combining
the multiple useless holes in to one big hole.
◼ Problem: it requires a lot of CPU time. For instance, on a 1-GB machine
that can copy at a rate of 2 GB/sec (0.5 nsec/byte) it takes about 0.5 sec
to compact all of memory.

16
Dynamic partitioning(cont’d)

The Effect of Dynamic Partitioning

17
Dynamic partitioning(cont’d)

The Effect of Dynamic Partitioning

18
Dynamic Memory Summary
◼Advantage
◼ Dynamic memory allocation provides a better memory utilization.

◼Disadvantage
◼ Management is more complex.
◼ Includes memory compaction overhead.

19
Relocation and Protection
◼Multiprogramming introduces two essential problems that
must be solved – protection and relocation.
◼Protection
◼ Programs in other processes should not be able to reference memory
locations in a process for reading or writing purposes without
permission.
◼ A user program shouldn’t be able to address a memory area which is
not in its partition.
◼ A user process must not access any portion of the OS.
◼ Usually a program in one process can not branch to an instruction in another
process.
◼ Without permission, a program in one process cannot access the data area
of another process.

20
Relocation and Protection(cont’d)
◼Relocation
◼ Location of a program in main memory is unpredictable due to loading,
swapping and compaction.
◼ To solve this problem, a distinction is made among several types of
addresses.
◼ There are two types of addresses:
◼ Logical address
◼ It is a reference to a memory location independent of the current assignment of data
to memory.
◼ Physical/absolute address
◼ An actual locator in the main memory.

◼The user program deals with logical addresses; it never sees

the real physical addresses.
◼The memory-mapping hardware converts logical addresses
into physical addresses. 21
Logical vs. Physical Address Space
◼ The concept of a logical address space that is bound to a separate physical address
space is central to proper memory management.
◼ Logical address – generated by the CPU.
◼ Physical address – address seen by the memory unit.
◼ Logical and physical addresses are:
◼ The same in compile-time and load-time address-binding schemes;
◼ They differ in execution-time address-binding scheme. In that case the logical address is
referred to as virtual address.
We use Logical address and virtual address interchangeably.
◼ Logical address space is the set of all logical addresses generated by a program.
◼ Physical address space is the set of all physical addresses corresponding to a given logical
address space.

22
Memory-Management Unit (MMU)
◼Hardware device that at run time maps virtual addresses to
physical address.

23
Relocation techniques
◼There are two possible solutions for relocation problems –
static relocation and dynamic relocation.
◼Static Relocation
◼ When a process is first loaded, all relative memory references are
replace by an absolute addresses based on the base address of the
loaded process.
◼ It can be applied for processes which are always assigned to the same
partition, for instance in the case of unequal size fixed partitions scheme
with multiple process queue.
◼ It doesn’t solve the protection problem. A malicious program can always
construct a new instruction and jump to it.

24
Relocation techniques(cont’d)
◼Dynamic Relocation
◼ When a process is assigned for running, a special processor register
(base register) is loaded with the starting address of the program and a
limit register is loaded with ending address of the partition.
◼ Limit and base registers are protected by the hardware not to be
modified by user programs.
◼ Hardware mechanisms are used for translating relative addresses to
physical addresses at the time of execution of the instructions that
contains the reference.

25
Relocation techniques(cont’d)

◼ The value in the base register is added to the relative address to

produce an absolute address.
◼ The absolute address is compared to the valued in the limit/bound
register.
◼ If the address is within bounds, the instruction execution can proceed,
otherwise an interrupt is generated to the OS.
◼ Dynamic relocation provides solution to both relocation and protection
problems.

26
Swapping
◼ A process can be swapped temporarily out of memory to a backing store
and then brought back into memory for continued execution.
◼ Total physical memory space of all processes can exceed the real physical
memory of the system.
◼ Two general approaches to memory management can be used.
◼ Swapping: bringing in each process in its entirety, running it for a while, then
putting it back on the disk.
◼ virtual memory allows programs to run even when they are only partially in main
memory.

◼ Memory allocation changes as:

◼ processes come into memory.
◼ leave memory.
◼ Shaded regions are unused memory.
27
Swapping(cont’d)
◼ A process has three major sections - stack, data and code
◼ With fixed partitions, the space given to process is usually larger
than it asked for and hence the process can expand if it needs.
◼ With dynamic partitions since a process is allocated exactly as
much memory it requires, it creates an overhead of moving and
swapping processes whenever the process grows dynamically.
◼ It is expected that most processes will grow as they run, so it is
a good idea to allocate a little extra memory whenever a
process is loaded into the memory.
◼ As shown in the following diagram the extra space is located
between the stack and data segments because the code
segment doesn’t grow.

28
Swapping(cont’d)

◼If a process runs out of the extra space allocated to it, either
◼ It will have to be moved to a hole with enough space or
◼ Swapped out of memory until a large enough hole can be created or
◼ Kill the process.

29
Schematic View of Swapping

30
Memory Usage Management
◼When memory is assigned dynamically, the operating system
must manage it.
◼There are two ways to keep track of memory usage – bitmap
and linked list.
◼Bitmaps
◼ The memory is divided into fixed size allocation units.
◼ Each allocation unit is represented with a bit in the bit map. If the bit is
0, it means the allocation unit is free and if it is 1, it means it is
occupied.
◼ Example: Look at the following portion of a memory. Let the size of the
allocation units is 5k as shown in the diagram.

31
Memory Management with Bitmaps

◼The corresponding bitmap for the above memory can be as

follows:

32
Memory Management with Bitmaps(cont’d)
◼The size of the allocation unit is an important design issue.
◼The smaller the allocation unit, the larger the bitmap size,
which will result to memory and CPU overheads. Searching
will take time.
◼E.g. Assume an allocation unit of 4bytes and assume the
computer has 800KB of memory.
◼ Number of bits required = 800KB/4B = 200Kbits
◼ Size of bitmap = 200Kbits/8 = 25KB
◼ Percentage of the memory used for the bitmap = (25/800)*100% 
3%.

◼What if the allocation unit is large?

◼ The larger the allocation unit, the larger the internal fragmentation.

33
Memory Management with Linked Lists
◼ Maintain a linked list of allocated and free memory segments.
◼ Each segment is either a process(P) or a hole(H) between two processes
and contains a number of allocation units.
◼ Each entry in the list consists of
◼ Segment type: P/H (1bit).
◼ The address at which it starts.
◼ The length of the segment.
◼ A pointer to the next entry.
◼ Example 1: The memory in the bitmap example can be represented using
linked list as follows:

34
Example 2: bitmap and linked list

◼(a) Part of memory with 5 processes, 3 holes

◼ tick marks show allocation units
◼ shaded regions are free
◼(b) Corresponding bit map
◼(c) Same information as a list

35
Memory Management with Linked Lists(cont’d)
◼The list is kept sorted by address. Sorting this way has the
advantage of easily updating when processes terminates or
is swapped out.
◼A terminating process normally has two neighbors, except
when it is at the very beginning or end of the list.
◼The neighbors can be either process or holes, leading to four
combinations as shown on the next slide:

36
Memory Management with Linked Lists(cont’d)

◼When a process and holes are kept on a list sorted by

address, several algorithms can be used to allocate
memory for a newly created process.

37
Memory Allocation Algorithms
◼Memory Allocation algorithms (Placement algorithms)
◼When a new process is created or swapped in, the OS must
decide which free block to allocate.
◼The following are some of the placement algorithms.
◼First-Fit
◼ It scans the memory from the beginning and chooses the first available
block that is large enough.
◼ It is the simplest and fastest algorithm.
◼ Disadvantage: Searching from the beginning always may result in slow
performance.

38
Memory Allocation Algorithms(cont’d)
◼Next Fit
◼ It starts scanning the memory from the location of the last placement
and chooses the next available block that is large enough.
◼ Disadvantage: It may cause the last section of memory to be quickly
fragmented.

◼Best Fit
◼ It searches the entire list of available holes and chooses the lock that is
closest in size to the request.
◼ Disadvantage: External fragmentation and slower because it scans the
whole list. .

◼Example: Memory Configuration before and after Allocation

of 16-Mbyte Block.

39
40
Memory Allocation Algorithms(cont’d)
◼Worst Fit
◼ It searches for the largest available hole, so that the hole broken off will
be big enough to be useful.
◼ Disadvantage: It is as slow as best fit.

◼Quick Fit
◼ It maintains separate list for some of the more common size requests.
◼ Advantage: Finding a hole of the required size is extremely fast.
◼ Disadvantage: When a process terminates or is swapped out, finding
its neighbors to see if a merge is possible is expensive.

41
Virtual Memory
◼A process may be larger than the available main memory.
◼In the early days overlays were used to solve this problem.
◼ The programmer will divide the program into modules and the main
program is responsible for switching the modules in and out of memory
as needed.
◼ Although the actual work of swapping overlays in and out was done by
the system, the decision of how to split the program into pieces had to
be done by the programmer.
◼ Drawback: The programmer must know how much memory is available
and it wastes the programmer time.

◼In virtual memory the OS keeps those parts of the program

currently in use in main memory and the rest on the disk.

42
Virtual Memory(cont’d)
◼Piece of programs are swapped between disk and memory as
needed.
◼Example, a 512-MB program can run on a 256-MB machine
by carefully choosing which 256 MB to keep in memory at
each instant, with pieces of the program being swapped
between disk and memory as needed.
◼Program generated addresses are called virtual addresses
and the set of such addresses form the virtual address
space.
◼The virtual address will go to the Memory Management Unit
(MMU) that maps the virtual addresses into physical
addresses.
43
Paging
◼There are two virtual memory implementation techniques
◼ Paging
◼ Segmentation

◼Paging
◼ The virtual address space is divided into units called pages. The
corresponding units in the physical memory are called page frames.
◼ Size of a frame is power of 2 between 512 bytes and 16 Mbytes.
◼ Pages and page frames should have the same size.
◼ Transfer between memory and disks are always in units of pages.
◼ The operation of dividing a process into pages is done by the compiler or
MM.
◼ Example: Assume a 64KB virtual address and each process is divided
into 4K pages and the physical memory size is 32KB.

44
Virtual Memory…

The relation between

virtual addresses
and physical
memory addresses
given by
page table

45
Paging(cont’d)
◼Examples:
1. When the program tries to access address 0 using the
instruction - MOVE REG, 0
◼ The MMU sees that this virtual address falls in page 0 (0-4095), which
according to its mapping is page frame 2 (8192 to 12287). It thus
transforms the address to 8192 and outputs address 8192 onto the
bus.

2. MOVE REG, 8196 is effectively transformed in to MOVE

REG, 24580
3. MOVE REG, 4250, ?
In to: 4250
4. Move REG, 20580, ?
46
In to: 12388
Cont’d
◼Address
0. 0-4095 8. 32767-36863
1. 4096- 8191 9. 36864- 40959
2. 8192 – 12287 10. 40960– 45055
3. 12288 – 16383 11. 45056– 49151
4. 16384 – 20479 12. 49152– 53247
5. 20480 – 24575 13. 53248– 57343
6. 24576 – 28671 14. 57344– 61439
7. 28672 - 32767 15. 61440- 65535
47
Paging(cont’d)
◼Example: Address Bits = 16, Page
size = 4K, Logical address = 8196.
The following figure shows the
internal operation of the MMU with 16
4K pages. split into a 4-bit page
number and a 12-bit offset.

Internal operation of MMU with 16 4 KB pages

48
Paging(cont’d)
◼Page Tables
◼ The OS maintains page table for mapping virtual addresses to physical
addresses.
◼ Page tables are stored in memory.
◼ The OS also maintains all free-frames, list of all frames in main memory
that are currently unoccupied.
◼ Each page table entry contains: present-bit, modified-bit, and frame
number.
◼ Present-bit: Whether the page is present in main memory or not.
◼ Modified-bit: whether the contents of the corresponding page have been
altered since the page was last loaded into main memory. If it is not altered,
then it is not necessary to write the page out when it is to replace the page in
the frame it occupies.
◼ Frame number: Indicates the corresponding page frame number in memory.

49
Paging(cont’d)
◼Page Size
◼There are two issues:
◼ The smaller the page size, the less number of internal fragmentation
which optimizes the use of main memory.
◼ The smaller the page size, the greater the number of pages and thus
the larger the page table.

50
Paging(cont’d)
◼If an instruction in a process tries to access an address in
unmapped page.
◼ The MMU causes the CPU to generate an interrupt, called page fault.
◼ The OS puts the interrupted process in a blocking state and takes
control.
◼ The OS chooses a page(page frame) to remove from memory and
updates its contents back to the disk if it is modified since its last load.
he OS issues a disk I/O read request to fetch the page just referenced into
the page frame just freed and the OS can dispatch another process to
run while the disk I/O is performed.

51
Page Replacement Algorithms
◼Page Replacement Algorithms (PRA)
◼ When a page fault occurs, the OS has to choose a page to remove from
memory to make room for the page that has to be brought in.

◼Optimal PRA
◼ It says replace the page that will not be referenced soon.
◼ Drawback – impossible to know whether the page will be referenced or
not in the future (its unrealizable).

◼First In First Out PRA

◼ Remove the oldest page.
◼ The FIFO page-replacement algorithm is easy to understand and
program.
◼ However, its performance is not always good.
◼ page in memory the longest may be often used.

52
Page Replacement Algorithms(cont’d)
◼FIFO algorithm uses the time when a page was brought into
memory, whereas the OPT algorithm uses the time when a
page is to be used.
◼Least Recently Used (LRU) PRA
◼ Remove pages that have less used in the past.
◼ We can think of this strategy as the optimal page-replacement algorithm
looking backward in time, rather than forward.

53
Page Replacement Algorithms(cont’d)
◼Second Chance PRA

◼ Operation of a second chance

◼ Pages sorted in FIFO order. Inspect reference bit. If the value is 0, replace this
page; but if the reference bit is set to 1, give the page a second chance and
move on to select the next FIFO page.
◼ Page list if fault occurs at time 20, A has R bit set.
54
Page Replacement Algorithms(cont’d)
◼Clock PRA
◼ It differs from second chance only in the implementation.

55
Segmentation
◼ Memory-management scheme that supports user’s view of memory.
◼ A program is a collection of segments -- a logical unit such as:
main program
procedure
function
method
object
local variables, global variables
common block
stack
symbol table
arrays
◼ Each segment can to reside in different parts of memory. Way to
circumvent the contiguous allocation requirement.
◼ In a one-dimensional memory, these segments would have to be allocated
contiguous chunks of virtual address space.
56
Segmentation(cont’d)

◼One-dimensional address space with growing tables

◼One table may bump into another
57
Segmentation(cont’d)
◼The virtual space is divided into units called segments.
◼Segments can have unequal and dynamic size.
◼Each segment has its own virtual address space.
◼Each segment consists of a linear sequence of addresses,
from 0 to some maximum.
◼The OS maintains a segment table for each process and also
a free-segment list.
◼It simplifies the handling of growing data structures.
◼When segmentation is used there is no internal fragmentation.

58
Example of Segmentation

59
Paging Vs Segmentation

Comparison of paging and segmentation

60
Reading Assignment
◼ Other PRA Algorithms not included in the lecture.
◼ More on Segmentation.
◼ Paging with segmentation combined (Hybrid).
◼ Thrashing (causes, effects of thrashing, how to avoid it).

61