Unity University

Faculty of Engineering , Technology and Computational Sciences

Department of Computer Science

Course Title: Operating System (COSC 3052)

Topic: Memory Management (noncontiguous memory Mgmt.)

Objectives
After completing this topic, you will be able to:
 Requirements for Memory Management,
 Explain Memory protection(in contiguous memory allocation),
 Explain core concepts of Non-Contiguous memory allocation(paging, segmentation).

 Requirements for Memory Management

• Five Requirements for Memory Management to satisfy:
 Relocation
• Users generally don’t know where they will be placed in main memory
• May want to swap in at a different place
– Must deal with user pointers
• Generally handled by hardware
 Protection
• Prevent processes from interfering with the O.S. or other processes
• Often integrated with relocation
 Sharing
• Allow processes to share data/programs
 Logical Organization
• Support modules, shared subroutines
 Physical Organization

• Manage memory  disk transfers

Source: Feleke Merin (Dr. ̶ Engr.) Page 1

 Unity University

 Relocation

• Not a major problem with fixed-sized partitions

 Easy to load process back into the same partition
• Otherwise need to deal with a process loaded into a new location
• Memory addresses may change
 When loaded into a new partition
 If compaction is used
• Addresses
 Logical Addresses
 generated by the CPU; also referred to as virtual address
 As seen by the program
 Often set as relative to the program start
 Physical Addresses
 As seen by memory unit

Logical and physical addresses are the same in compile-time and load-time address-
binding schemes; logical (virtual) and physical addresses differ in execution-time
address-binding scheme

• Hardware does address conversion

 Memory protection(in contiguous memory allocation),

Referring to fig. x, The limit register is initialized to the size M of the currently executing
program and relocation register is initialized to the base address of the executing program.
When the program generates a logical address, the address is compared with the contents of the
limit register (M).
If the logical address is  M, then it is a valid address, else it is an “invalid address error”. If the
logical address is valid, then the corresponding physical address is computed by adding the
contents of relocation register (R) to the logical address. In case of “invalid address error”, the
process is terminated.

Source: Feleke Merin (Dr. ̶ Engr.) Page 2

 Unity University

Figure X: Hardware address protection

 Main purpose memory protection: to prevent one process corrupting the memory of any
other process including the operating system.
 Memory protection usually relies on a combination of hardware and software to allocate
memory to processes and handle exceptions. Using base register and limit register, it is
possible to provide the protection of memory.

 Relocation-register scheme 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

 Base and limit registers can be loaded only by the operating system. Operating system
prevents the user programs from changing the contents of the registers.
 An example of the hardware support that can be provided for memory protection is that
of the IBM system /370 family of machines, on which VMS runs. Microsoft Windows also
offers memory protection.
 In Unix, almost impossible to corrupt another process memory.

Source: Feleke Merin (Dr. ̶ Engr.) Page 3

 Unity University

Memory-Management Unit (MMU)

 Hardware device that maps virtual to physical address
 In MMU scheme( see figure below), the value in the relocation register is added to every
address generated by a user process at the time it is sent to memory
 The user program deals with logical addresses; it never sees the real physical addresses

Dynamic relocation using a relocation register

Source: Feleke Merin (Dr. ̶ Engr.) Page 4

 Unity University

 Non-Contiguous memory allocation

 Advantages
Non-Contiguous memory allocation offers the following advantages over, contiguous memory
allocation:
a) It Permits sharing of code and data amongst processes,
b) There is no external fragmentation of physical memory, and
c) It supports virtual memory concept.

 Limitations(disadvantages)
However, non-contiguous memory allocation involves a complex implementation and involves
additional costs in terms of memory and processing.

 Implementations Non-Contiguous memory allocation

Non-contiguous memory allocation can be implemented by the concept of the following:

a) Paging
b) Segmentation
c) Segmentation with paging.

 Basic concepts of paging

 Physical address space of a process can be noncontiguous; process is allocated in physical

memory whenever the latter is available
- Avoids external fragmentation
- Avoids problem of varying sized memory chunks
 Permits a process's memory to be noncontiguous (see figure Y below)
 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
 Backing store likewise split into pages
 Still have Internal fragmentation

Source: Feleke Merin (Dr. ̶ Engr.) Page 5

 Unity University

Fig. Y: Example of paging

Implementation of paging

 When a process is to be executed, its pages are moved from hard-disk to free frames in
physical memory.
 The information about frame number, in which a page is stored, is entered in the page
table.
 The page table is indexed by the page number.
 During program execution, CPU generates a logical address (also called virtual address).
 Logical address comprises page number (P), and offset within the page (d).
 The page number is used to index into the page table and fetch the corresponding frame
number(f).
 The physical address is obtained by combining the frame number (f) with the offset(d).

Source: Feleke Merin (Dr. ̶ Engr.) Page 6

 Unity University

 Address Translation Scheme

 Address generated by CPU is divided into:

 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

Paging Hardware

Source: Feleke Merin (Dr. ̶ Engr.) Page 7

 Unity University

Paging Model of Logical and Physical Memory

Paging model of memory is shown above. The page table stores the number of the page allocated
for each process. The page number is used as an index into the page table.

Free Frames

Before allocation After allocation

Source: Feleke Merin (Dr. ̶ Engr.) Page 8

 Unity University

Implementation of Page Table

 Page table is kept in main memory

 Page-table base register (PTBR) points to the page table
 Page-table length register (PRLR) indicates size of the page table
 In this scheme every data/instruction access requires two memory accesses. One for the
page table and one for the data/instruction.
 The two memory access problem can be solved by the use of a special fast-lookup
hardware cache called associative memory or translation look-aside buffers (TLBs)

 How to reduce the memory-overhead of a paged system?

 By increase the page size. This will correspondingly reduce the max number of pages in
the logical address space, thus reducing the size of the page table. But, increasing the page
size would increase the loss of memory, due to internal fragmentation.
 By creating a page table for the exact program size and using a page table length
register(PTLR).
 Bu using of inverted page table.

Logical memory vs Physical memory

 Logical memory
- Provides user's view of the memory
- Memory treated as one contiguous space, containing only one program
 Physical memory
- User program scattered throughout the memory
- Also holds other programs
 Mapping from logical addresses to physical addresses hidden from the user
 System could use more memory than any individual user
 Allocation of frames kept in frame table

Source: Feleke Merin (Dr. ̶ Engr.) Page 9

 Unity University

 Memory protection in paging systems

 Memory protection implemented by associating protection bit with each frame

 Protection bits kept in page table (named valid or invalid bit)
 Valid-invalid bit attached to each entry in the page table:
- “valid bit” indicates that the associated page is in the process’ logical address
space, and is thus a legal page
- “invalid bit ” indicates that the page is not in the process’ logical address space
 Define the page to be read only or read and write
 Protection checked at the time of page table reference to find the physical page number
 Hardware trap or memory protection violation
 Page table length register
- Indicates the size of the page table
- Value checked against every logical address to validate the address
- Failure results in trap to the OS

Valid (v) or Invalid (i) Bit In A Page Table

Source: Feleke Merin (Dr. ̶ Engr.) Page 10

 Unity University

Advantages of paging

 Paging eliminates external fragmentation.

 Supports high degree of multiprogramming
 Increases memory and processor utilization.

Limitations of paging scheme vs contiguous memeory allocation

 Page address mapping hardware usually increases the cost of the comuter
 Increased memory access time
 The page table occupies a significant amount of memory (memory-overhead for page table)
 Since the page table is per process, the page table would also need to be switched during
context switching

Review questions
Part I: Multiple choice questions
1. ……. Involves treating main memory as a resource to be allocated to and shared among a
number of active processes.
a) Partition management
b) Memory management
c) Disk management
d) All of the above

2. In memory management, a technique called as paging, the physical memory is broken into
fixed sized blocks called .........
a) pages b) frames c) blocks d) segments

3. Which of the following memory allocation scheme suffers from External fragmentation?
a) Segmentation b) Swapping c) Paging

4. A process that execute only in main memory is referred to as ……………… and that
allocated in disk is referred to a …………….
a) virtual memory, true memory
b) virtual memory, real memory
c) real memory, virtual memory d) imaginary memory, real memory

Source: Feleke Merin (Dr. ̶ Engr.) Page 11

 Unity University

5. The mechanism that brings a page into memory only when it is needed is called .....
a) segmentation
b) fragmentation
c) demand paging
d) page replacement

6. Paging .........
a) solves the memory fragmentation problem
b) allows modular programming
c) allows structured programming
d) avoids deadlock

7. ........is a memory management scheme that permits the physical address space of a process to
be noncontiguous.
a) Paging
b) Segmentation
c) Virtual memory
d) main memory

Part II: Descriptive questions

1. List the difference between logical address and physical address.

2. List the advantages and disadvantages of non-contiguous memory allocation.
3. Define paging.
4. What hardware is required for paging?
5. Explain the purpose of page table in paged address translation.
6. List the advantage s and disadvantages of paging.
7. Discuss memory protection scheme in paged memory system..
8. Compare and contrast paging and segmentation.
9. List the advantages and disadvantages of segmentation.
10. Why paging and segmentation is combined?

----------------------------------------- The End! ------------------------------------

Source: Feleke Merin (Dr. ̶ Engr.) Page 12