Operating Systems:

Internals and Design Principles.

CCS3203/
Operating Systems

Memory Management

Dr. Reem Ibrahim

Introduction
 Memory management requirements
 Paging
 Memory partitioning
 Segmentation

2 Operating System Dr. Reem Ibrahim

Memory Management Requirements
 Memory management is intended to satisfy the
following requirements:
 Relocation
 Protection
 Sharing
 Logical organization
 Physical organization

3 Operating System Dr. Reem Ibrahim

 Relocation
 Programmers typically do not know
in advance which other programs will
be resident in main memory at the Process control
information Process Control Block
Entry point
time of execution of their program. to program
Branch
 Active processes need to be able to Program instruction

be swapped in and out of main Increasing

memory in order to maximize address

values

processor utilization. Reference

to data

 Specifying that a process must be Data

placed in the same memory region

when it is swapped back in would be Current top
of stack
limiting Stack

 may need to relocate the process

to a different area
of memory Addressing requirement for a process

4 Figure 7.1 Addressing

Operating System Requirements
Dr. Reem Ibrahimfor a Process
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.

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

5 Operating System Dr. Reem Ibrahim

Logical Organization
 Memory is organized as linear.
 Programs are written in modules
 Modules can be written and compiled independently
 Different degrees of protection given to modules (read-only, execute-only)
 Sharing on a module level corresponds to the user’s way of viewing the
problem
 Segmentation is the tool that most readily satisfies
requirements

6 Operating System Dr. Reem Ibrahim

Physical Organization

Cannot leave the

Memory available for a Programmer does not
programmer with the
program plus its data know how much space
responsibility to
may be insufficient will be available
manage memory

overlaying allows various

modules to be assigned
the same region of
memory but is time
consuming to program

7 Operating System Dr. Reem Ibrahim

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 now-obsolete operating
systems
 Does not involve virtual memory

8 Operating System Dr. Reem Ibrahim

Fixed Partitioning
Operating System Operating System

 PARTITION SIZES 8M 8M

Two alternatives
2M
 8M 4M

 Equal-size partitions. In 6M
this case, any process whose 8M
size is less than or equal to 8M
the partition size can be
loaded into any available
8M

partition. 8M

If all partitions are full and

8M

no process is in the Ready 12M
or Running state, the 8M

operating system can swap a

process out of any of the 8M

partitions and load in 16M

another process, so that 8M
there is some work for the
processor.
(a) Equal-size partitions (b) Unequal-size partitions

Figure 7.2 Example of Fixed Partitioning of a 64-Mbyte Memory

9 Operating System Dr. Reem Ibrahim
 A program may be too big to fit in a partition
 program needs to be designed with the use of overlays.
 Main memory utilization is inefficient
 any program, regardless of size, occupies an entire
partition
 internal fragmentation
 wasted space due to the block of data loaded being
smaller than the partition

10 Operating System Dr. Reem Ibrahim

 The simplest way is to assign each process
to the smallest partition within which it
will fit. In this case, a scheduling queue is
needed for each partition, to hold
swapped-out processes destined for that
partition .The advantage of this approach is Operating
System
Operating
System
that processes are always assigned in such
a way as to minimize wasted memory
within a partition (internal fragmentation).
 Consider a case in which there are no New New

processes with a size between 12 and 16M Processes Processes

at a certain point in time. In that case, the

16M partition will remain unused, even
though some smaller process could have
been assigned to it. Thus, a preferable
approach would be to employ a single
queue for all processes When it is time to (a) One process queue per partition (b) Single queue
load a process into main memory, the
smallest available partition that will hold Memory Assignment for Fixed
Figure 7.3 Memory Assignment for Fixed Partitioning
the process is selected. Partitioning

11 Operating System Dr. Reem Ibrahim

 The number of partitions specified at system
generation time limits the number of active processes
in the system.
 Small jobs will not utilize partition space efficiently.

12 Operating System Dr. Reem Ibrahim

 Operating Operating Operating Operating
8M

Partitions are of
System System System System

Process 1 Process 1 Process 1
variable length and
20M 20M 20M

number 56M Process 2 14M Process 2 14M

Process is allocated
36M
 22M
Process 3 18M

exactly as much 4M

(a) (b) (c) (d)

memory as it requires
 This technique was Operating
System
Operating
System
Operating
System
Operating
System

used by IBM’s Process 1 20M Process 1 20M 20M

Process 2 14M

mainframe operating 6M
Process 4 Process 4 Process 4

system, OS/MVT
8M 8M 8M
14M
6M 6M 6M

Process 3 18M Process 3 18M Process 3 18M Process 3 18M

4M 4M 4M 4M

(e) (f) (g) (h)

13 Operating System Dr. Reem Ibrahim

Figure 7.4 The Effect of Dynamic Partitioning
Dynamic Partitioning

External Fragmentation
• memory becomes more and more fragmented
• memory utilization declines

Compaction
• technique for overcoming external fragmentation
• OS shifts processes so that they are contiguous
• free memory is together in one block
• time consuming and wastes CPU time

14 Operating System Dr. Reem Ibrahim

Placement Algorithms 8M 8M

 Best-fit 12M
First Fit
12M

chooses the block that is closest 22M

6M
Best Fit
in size to the request. Last 18M
allocated 2M
 First-fit
block (14M)

begins to scan memory from the 8M 8M

beginning and chooses the first 6M

Allocated block
6M

available block that is large enough. Free block

 Next-fit
14M Possible new allocation 14M

Next Fit
begins to scan memory from the
location of the last placement and 36M
20 M

chooses the next available block (a) Before (b) After

that is large enough Example Memory Configuration

before and after allocation of
16- M-byte Block
Figure 7.5 Example Memory Configuration befor e
15 Operating System and afterDr.
Allocation of 16-Mbyte Block
Reem Ibrahim
Buddy System
1 Mbyte block 1M
 Comprised of fixed and
dynamic partitioning Request 100 K A = 128K 128K 256K 512K
schemes.
Request 240 K A = 128K 128K B = 256K 512K
 Space available for allocation
is treated as a single block Request 64 K A = 128K C = 64K 64K B = 256K 512K

 Memory blocks are available Request 256 K A = 128K C = 64K 64K B = 256K D = 256K 256K
of size 2K words, L ≤ K ≤ U,
Release B A = 128K C = 64K 64K 256K D = 256K 256K
where
 2L = smallest size block Release A 128K C = 64K 64K 256K D = 256K 256K
that is allocated
Request 75 K E = 128K C = 64K 64K 256K D = 256K 256K
 2U = largest size block
that is allocated; Release C E = 128K 128K 256K D = 256K 256K

generally 2U is the size Release E 512K D = 256K 256K

of the entire memory
available for allocation Release D 1M

16 Operating System Dr. Reem Ibrahim

Addresses
 Logical
Relative address
 Reference to a memory
location independent of the Base Register
Process Control Block

current assignment of data

to memory. Adder Program

Absolute

Relative
address
 Bounds Register Comparator

 Address is expressed as a
location relative to some
Data
Interrupt to
operating system

known point.
Stack

 Physical or Absolute Process image in

main memory
 Actual location in main
memory. Hardware support for relocation
Figure 7.8 Hardware Support for Relocation

17 Operating System Dr. Reem Ibrahim

 Frame Main memory Main memory Main memory
number
0 0 A.0 0 A.0
1 1 A.1 1 A.1
2 2 A.2 2 A.2
3 3 A.3 3 A.3

 Partition memory into 4

5
6
4
5
6
4
5
6
B.0
B.1
B.2

equal fixed-size chunks that 7

8
7
8
7
8

are relatively small

9 9 9
10 10 10
11 11 11
12 12 12

 Process is also divided into 13

14
13
14
13
14

small fixed-size chunks of (a) Fifteen Available Frames (b) Load Process A (c) Load Process B

the same size. 0

Main memory
A.0 0
Main memory
A.0 0
Main memory
A.0

Pages : chucks of a process.

1 A.1 1 A.1 1 A.1
 2
3
A.2
A.3
2
3
A.2
A.3
2
3
A.2
A.3
4 B.0 4 4 D.0

 Frames: Available chunks of 5

6
B.1
B.2
5
6
5
6
D.1
D.2

memory
7 C.0 7 C.0 7 C.0
8 C.1 8 C.1 8 C.1
9 C.2 9 C.2 9 C.2
10 C.3 10 C.3 10 C.3
11 11 11 D.3
12 12 12 D.4
13 13 13
14 14 14

(d) Load Process C (e) Swap out B (f) Load Process D

Assignment of Process
Figure 7.9 Assignment to Free
of Process Pages to FreeFrames
Frames
18 Operating System Dr. Reem Ibrahim
Page Table
 Maintained by operating system 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.

0 0 0 — 0 7 0 4 13
1 1 1 — 1 8 1 5 14
2 2 2 — 2 9 2 6 Free frame
3 3 Process B 3 10 3 11 list
Process A page table Process C 4 12
page table page table Process D
page table

19 Operating System Dr. Reem Ibrahim

 Logical address = Logical address =
Relative address = 1502 Page# = 1, Offset = 478 Segment# = 1, Offset = 752
0000010111011110 0000010111011110 0001001011110000

Segment 0
750 bytes
Page 0
User process
(2700 bytes)

752
478
Page 1

1950 bytes
Segment 1
Page 2

fragmentation
Internal
(a) Partitioning (c) Segmentation

(b) Paging
(page size = 1K)

Logical
Figure Addresses
7.11 Logical Addresses

20 Operating System Dr. Reem Ibrahim

 16-bit logical address
6-bit page # 10-bit offset

0 0 000 1011 1011 110

0 000101
1 000110
2 011001
Process
page table

000 1100 1110 11 110

16-bit physical address
(a) Paging

16-bit logical
Examples ofaddress
Logical-to-Physical Address Translation
4-bit segment # 12-bit offset Operating System
21 Dr. Reem Ibrahim
Segmentation
 A program can 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
 Eliminates internal fragmentation
 Usually visible
 Provided as a convenience for organizing programs and data
 Typically the programmer will assign programs and data to different
segments.
 For purposes 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.
22 Operating System Dr. Reem Ibrahim
 Address Translation
 Another consequence of unequal size segments is that there
is no simple relationship between logical addresses and
physical addresses
 The following steps are needed for address translation:

Compare the offset,

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

23 Operating System Dr. Reem Ibrahim

 16-bit physical address
(a) Paging

16-bit logical address

4-bit segment # 12-bit offset

0 0 010 0101 1110 000

Length Base
0 001011101110 0000010000000000
1 011110011110 0010000000100000 +
Process segment table

001 0001 1000 10 000

16-bit physical address
(b) Segmentation

Examples of Logical-to-Physical Address Translation

Figure 7.12 Examples of Logical-to-Physical Address Translation
24 Operating System Dr. Reem Ibrahim
Memory Management Techniques
Technique Description Strengths Weaknesses

Main memory is divided into a Inefficient use of

memory due to internal
number of static partitions at Simple to implement;
fragmentation;
Fixed Partitioning system generation time. A process little operating system
maximum number of
may be loaded into a partition of overhead.
active processes is
equal or greater size.
fixed.

Inefficient use of
Partitions are created dynamically, No internal
so that each process is loaded into a fragmentation; more processor due to the
Dynamic Partitioning need for compaction to
partition of exactly the same size as efficient use of main
counter external
that process. memory.
fragmentation.

Main memory is divided into a

number of equal-size frames. Each
process is divided into a number of
equal-size pages of the same length No external A small amount of
Simple Paging
as frames. A process is loaded by fragmentation. internal fragmentation.
loading all of its pages into
available, not necessarily
contiguous, frames.

No internal
Each process is divided into a
fragmentation; improved
number of segments. A process is
memory utilization and
Simple Segmentation loaded by loading all of its External fragmentation.
reduced overhead
segments into dynamic partitions
that need not be contiguous. compared to dynamic
partitioning.

As with simple paging, except that No external

25 Operating
it is not necessary to load all of the System
fragmentation; higher Dr. Reem Ibrahim
Virtual Memory degree of Overhead of complex
pages of a process. Nonresident