COURSE NAME : OPERATING SYSTEM

COURSE CODE : 381CCS-3

CHAPTER 6 : PRINCIPAL (MAIN) MEMORY MANAGEMENT

SUBJECT COORDINATOR: DR. ANAND DEVADURAI

SUBJECT TEACHER: MRS. MARIYAM AYSHA BIVI
DEPARTMENT OF COMPUTER SCIENCE
KING KHALID UNIVERSITY
ABHA, KSA.

Course
Specification Text Book Page
Chapter No TOPICS CHAPTERS / SECTION Number Book Reference
Principal Memory Management “Operating
CHAPTER 9 349-378 System
Background 9.1(9.1.3) 353-354 Concepts”, 10th
Edition,
Contiguous Memory Allocation 9.2(9.2.1,9.2.2,9.2.3) 356-360 Abraham Silber
6
Swapping 9.5(9.5.1,9.5.2,9.5.3) 376-378 Schatz ,
Paging 9.3(9.3.1) 360-365 Peter Baer Galvin,
Greg Gagne
Structure of the Page Table , Wiley, 2018
9.4(9.4.1,9.4.2,9.4.3) 371-375
CHAPTER 6 : MAIN (PRINCIPAL) MEMORY MANAGEMENT

 Background
 Contiguous Memory Allocation
 Memory Protection
 Memory Allocation - Variable Partition (Multiple-partition) allocation
 Fragmentation
 Paging
 Structure of the Page Table
 Swapping
 Standard Swapping
 Swapping with Paging
 Swapping on Mobile Systems

2
 6.1 BACKGROUND
 Program must be brought (from disk) into memory and placed within a
process for it to be run
 Main memory and registers are only storage CPU can access directly Register
access in one CPU clock (or less)
 Main memory can take many cycles
 Cache sits between main memory and CPU registers Protection of memory
required to ensure correct operation

LOGICAL VS PHYSICAL ADDRESS SPACE

 Logical address (Virtual Address) – generated by the CPU
 Physical address – address seen by the memory unit
 Logical and physical addresses are
 Same in compile-time and load-time address-binding schemes;
 Differ in execution-time address-binding scheme
 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 these Logical addresses. 3
6.2 CONTIGUOUS MEMORY ALLOCATION
 Main memory must support both OS and user processes.
 Limited resource, must allocate efficiently, Contiguous allocation is one method
 Main memory usually into two partitions:
• Resident operating system, usually held in low memory User processes then
held in high memory
• Each process contained in single contiguous section of memory

6.2.1 MEMORY PROTECTION

 Relocation registers(Base Register) used
to protect user processes from each other,
and from changing operating-system code
and data
 Relocation register: contains value of
smallest physical address
 Limit register: contains range of logical
addresses, each logical address must be
less than the limit register
4
 MMU maps logical address dynamically Figure 6.1 Hardware support for
relocation and limit registers
6.2 CONTIGUOUS MEMORY ALLOCATION(CONT…)
6.2.2 MEMORY ALLOCATION - Variable Partition (Multiple-partition) allocation
 Hole: Block of available memory of various size are scattered throughout memory.
 When a process arrives, it is allocated memory from a hole large enough to
accommodate it
 Process exiting frees its partition, adjacent free partitions combined
 Operating system maintains information about:
a) allocated partitions b) free partitions (hole)

Figure 6.2 Variable Partition

How to satisfy a request of size n from a list of free holes?

 First-fit: Allocate the first hole that is big enough
 Best-fit: Allocate the smallest hole that is big enough; must search entire list,
unless ordered by size
- Produces the smallest leftover hole
 Worst-fit: Allocate the largest hole; must also search entire list
- Produces the largest leftover hole 5
 First-fit and best-fit better than worst-fit in terms of speed and storage utilization
6.2 CONTIGUOUS MEMORY ALLOCATION(CONT…)
6.2.3 FRAGMENTATION
 External Fragmentation – total memory space exists to satisfy a request, but it is
not contiguous
 Internal Fragmentation – allocated memory may be slightly larger than
requested memory; this size difference is memory internal to a partition, but not
being used
 First fit analysis reveals that given N blocks allocated, 0.5 N blocks lost to
fragmentation

 Reduce external fragmentation by

 Compaction:
• Shuffle memory contents to place all free memory together in one large
block
• Compaction is possible only if relocation is dynamic, done at execution time
• The simplest compaction algorithm is to move all processes toward one end of
memory; all holes move in the other direction, producing one large hole of
available memory. This scheme can be expensive
 Paging
• Permit the logical address space of processes to be noncontiguous,
thus allowing a process to be allocated physical memory wherever 6
such memory is available.
6.3 PAGING
 Divide physical memory into fixed-sized blocks called frames
- Size is power of 2, between 512 bytes and 16 Mbytes
 Divide logical memory into blocks of same size called pages
 Keep track of all free frames
 To run a program of size N pages, need to find N free frames and load program
 Set up a page table to translate logical to physical addresses

Figure 6.4 Paging Example

Logical address: n = 2 and m = 4.
Figure 6.3 Paging model of Using a page size of 4 bytes and a 7
logical and physical memory physical memory of 32 bytes (8 pages)
6.3 PAGING(CONT..)
 Address Translation Scheme
• Page number (p) – used as an index into a page table which contains base address of
each page in physical memory
• Page offset (d) – combined with base address to define the physical memory address
that is sent to the memory unit
page number page offset
p d
m -n n
 For given logical address space 2m and page size 2n

Figure 6.5 Paging Hardware

6.4 STRUCTURE OF THE PAGE TABLE
6.4.1 HIERARCHICAL PAGE TABLE
 Break up the logical address space into multiple page tables
 We then page the page table

A) Two-Level Paging
Example
 A logical address is divided into:
• a page number consisting of 20 bits
• a page offset consisting of 12 bits
 Since the page table is paged, the page
number is further divided into:
• a 10-bit page number
• a 10-bit page offset Figure 6.6 A Two level Page- table Scheme
 Thus, a logical address is as follows:

 p1 is an index into the outer page table,

p2 is the displacement within the page of
the inner page table 9

 Known as forward-mapped page table Figure 6.7 Address Translation Scheme

6.4 STRUCTURE OF THE PAGE TABLE
6.4.1 HIERARCHICAL PAGE TABLE
B) Three Level Paging

Figure 6.8 Three level Paging Scheme

10
6.4 STRUCTURE OF THE PAGE TABLE
6.4.2 HASHED PAGE TABLE
 Common in address spaces > 32 bits
 The virtual page number is hashed into a page table
• This page table contains a chain of elements hashing to the same location
 Each element contains (1) the virtual page number (2) the value of the mapped
page frame (3) a pointer to the next element
 Virtual page numbers are compared in this chain searching for a match
• If a match is found, the corresponding physical frame is extracted

Figure 6.9 Hashed Page Table 11

6.4 STRUCTURE OF THE PAGE TABLE
6.4.3 INVERTED PAGE TABLE
 Rather than each process having a page table and keeping track of all possible
logical pages, track all physical pages,
 One entry for each real page of memory
 Entry consists of the virtual address of the page stored in that real memory
location, with information about the process that owns that page
 Decreases memory needed to store each page table, but increases time
needed to search the table when a page reference occurs

12

Figure 6.10 Inverted Page Table

6.5 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 processes can exceed physical memory
6.5.1 STANDARD SWAPPING
 Backing store – fast disk large enough to accommodate copies of all memory images for
all users; must provide direct access to these memory images
 Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-
priority process is swapped out so higher-priority process can be loaded and executed
 Major part of swap time is transfer time; total transfer time is directly proportional to the
amount of memory swapped
 System maintains a ready queue of ready-to-run processes which have memory images
on disk

13

Figure 6.11 Standard swapping of two

processes using a disk as a backing store
6.5 SWAPPING
6.5.2 SWAPPING WITH PAGING
 Linux and Windows use a variation of swapping in which pages of a process—
rather than an entire process—can be swapped.
 The term swapping refers to standard swapping.
 Paging refers to swapping with paging.
 A page out operation moves a page from memory to the backing store; the
reverse process is known as a page in

14

Figure 6.12 Swapping with Paging

6.5 SWAPPING
6.5.2 SWAPPING ON MOBILE SYSTEMS
 Not typically supported
• Flash memory based
 Small amount of space
 Limited number of write cycles
 Poor throughput between flash memory and CPU on mobile
platform
 Instead of Swapping it use other methods to free memory if low
• iOS asks apps to voluntarily relinquish allocated memory
 Read-only data thrown out and reloaded from flash if needed
 Failure to free can result in termination
• Android terminates apps if low free memory, but first writes
application state to flash for fast restart
15