BGS COLLEGE OF ENGINEERING AND TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

Mahalakshmi Layout, Bengaluru-560086

OPERATING SYSTEM [BCS303]

MODULE-04

MEMORY MANAGEMENT
QUESTION BANK
SOLUTIONS

1
 SOLUTIONS

1) With a neat diagram describe the steps in handling the page fault.
ANS:
A page fault occurs when a process tries to access a page that is not present in
main memory (RAM) but exists in secondary storage (disk). The OS must
bring the required page from the disk into memory to continue execution.

Steps in Handling a Page Fault

1. The memory address requested is first checked, to make sure it was a valid
memory request.
2. If the reference is to an invalid page, the process is terminated. Otherwise,
if the page is not present in memory, it must be paged in.
3. A free frame is located, possibly from a free-frame list.
4. A disk operation is scheduled to bring in the necessary page from disk.
5. After the page is loaded to memory, the process's page table is updated with
the new frame number, and the invalid bit is changed to indicate that this is
now a valid page reference.
6. The instruction that caused the page fault must now be restarted from the
beginning

Fig: steps in handling page fault

2
2) What is TLB? Explain TLB in detail with a paging system with a
neat diagram

ANS:

A Translation Lookaside Buffer (TLB) is a special, small, and high-speed

associative memory (hardware cache) used in paging systems to improve
address translation speed. It stores a limited number of recently accessed page
table entries (Page Number → Frame Number mappings), reducing the need
to access the page table in main memory frequently.

WORKING:

When a logical-address is generated by the CPU, its page-number is

presented to the TLB.

If the page-number is found (TLB hit), its frame-number is immediately

available and used to access memory

If page-number is not in TLB (TLB miss), a memory-reference to page

table must be made. The obtained frame-number can be used to access
memory

In addition, we add the page-number and frame-number to the TLB, so

that they will be found quickly on the next reference

If the TLB is already full of entries, the OS must select one for
replacement.

Percentage of times that a particular page-number is found in the TLB is

called hit ratio.

3
 Figure 1: Paging hardware with TLB

3) With the help of a neat diagram, explain the various steps of

address binding

ANS:

Figure: Multistep processing of a user program

4
Address Binding:
Address binding of instructions to memory-addresses can happen at 3 different
stages.

i) Compile Time - If it is known at compile time where a program will reside

in physical memory, then absolute code can be generated by the compiler,
containing actual physical addresses. However, if the load address changes at
some later time, then the program will have to be recompiled.

ii) Load Time - If the location at which a program will be loaded is not known
at compile time, then the compiler must generate relocatable code, which
references addresses relative to the start of the program. If that starting address
changes, then the program must be reloaded but not recompiled.

iii) Execution Time - If a program can be moved around in memory during the
course of its execution, then binding must be delayed until execution time.

4) What is demand paging? Explain the steps in handling page faults

using the appropriate diagram.

ANS:

DEMAND PAGING:
A demand paging is similar to paging system with swapping when we want to
execute a process we swap the process the in to memory otherwise it will not
be loaded in to memory.

Steps in Handling a Page Fault

1. The memory address requested is first checked, to make sure it was a valid
memory request.
2. If the reference is to an invalid page, the process is terminated. Otherwise,
if the page is not present in memory, it must be paged in.
3. A free frame is located, possibly from a free-frame list.

5
4. A disk operation is scheduled to bring in the necessary page from disk.
5. After the page is loaded to memory, the process's page table is updated with
the new frame number, and the invalid bit is changed to indicate that this is
now a valid page reference.
6. The instruction that caused the page fault must now be restarted from the
beginning

Fig: steps in handling page fault

5) What is segmentation? Explain the basic method of segmentation

with an example.

ANS:

Segmentation is a memory management technique in which the logical

memory of a process is divided into variable-sized segments based on the
logical structure of the program, such as code, data, stack, heap, functions, or
modules. Each segment has a segment number and a segment length, and the
OS maintains a segment table to map logical segments to physical memory
locations

6
Basic Method of Segmentation
This is a memory-management scheme that supports user-view of memory
(Figure 1).
A logical-address space is a collection of segments.
Each segment has a name and a length.
The addresses specify both segment-name and offset within the segment.
Normally, the user-program is compiled, and the compiler automatically
constructs segments reflecting the input program.
For ex: The code, Global variables, The heap, from which memory is
allocated, The stacks used by each thread, The standard C library

Figure: Programmer’s view of a program

6) Discuss the structure of the page table with a suitable diagram.

ANS:

Structure of the Page Table

The most common techniques for structuring the page table:

1. Hierarchical Paging
2. Hashed Page-tables
3. Inverted Page-tables

7
1. Hierarchical Paging
Problem: Most computers support a large logical-address space (232 to
264). In these systems, the page-table itself becomes excessively large.
Solution: Divide the page-table into smaller pieces.

Two Level Paging Algorithm:

The page-table itself is also paged.
This is also known as a forward-mapped page-table because address
translation works from the outer page-table inwards.

Figure: A two-level page-table scheme

2. Hashed Page Tables

This approach is used for handling address spaces larger than 32 bits.
The hash-value is the virtual page-number.
Each entry in the hash-table contains a linked-list of elements that hash to
the same location (to handle collisions).
Each element consists of 3 fields:
1. Virtual page-number
2. Value of the mapped page-frame and
3. Pointer to the next element in the linked-list.

8
 Figure: Hashed page-table

3. Inverted Page Tables

Has one entry for each real page of memory.
Each entry consists of virtual-address of the page stored in that real
memory-location and information about the process that owns the page.
Each virtual-address consists of a triplet <process-id, page-number,
offset>.
Each inverted page-table entry is a pair <process-id, page-number>

Figure: Inverted page-table

9
7) What are the commonly used strategies to select a free hole from
the available holes?
ANS:
Commonly Used Strategies to Select a Free Hole

[Link] Fit: Allocate the first hole that is big enough. Searching can start
either at the beginning of the set of holes or at the location where the
previous first-fit search ended.

2. Best Fit: Allocate the smallest hole that is big enough. We must search
the entire list, unless the list is ordered by size. This strategy produces the
smallest leftover hole.

3. Worst Fit: Allocate the largest hole. Again, we must search the entire
list, unless it is sorted by size. This strategy produces the largest leftover
hole.

First-fit and best fit are better than worst fit in terms of decreasing time
and storage utilization.

8) Explain fragmentation in detail.

ANS:

Fragmentation is a condition in memory management where the available

memory is broken into small pieces and becomes difficult to allocate to
processes even though the total free space is enough.

Fragmentation occurs mainly due to dynamic allocation and

loading/unloading of processes in memory.

Two types of memory fragmentation:

1. Internal fragmentation
2. External fragmentation
10
1)Internal Fragmentation

The general approach is to break the physical-memory into fixed-sized

blocks and allocate memory in units based on block size.
The allocated-memory to a process may be slightly larger than the
requested-memory.
The difference between requested-memory and allocated-memory is
called internal fragmentation i.e. Unused memory that is internal to a
partition.

2) External Fragmentation
External fragmentation occurs when there is enough total memory-space
to satisfy a request but the available-spaces are not contiguous. (i.e.
storage is fragmented into a large number of small holes).
Both the first-fit and best-fit strategies for memory-allocation suffer from
external fragmentation.
Statistical analysis of first-fit reveals that given N allocated blocks,
another 0.5 N blocks will be lost to fragmentation. This property is
known as the 50-percent rule.

Two solutions to external fragmentation:

Compaction: The goal is to shuffle the memory-contents to place all free

memory together in one large hole. Compaction is possible only if
relocation is dynamic and done at execution-time
Permit the logical-address space of the processes to be non-contiguous.
This allows a process to be allocated physical-memory wherever such
memory is available. Two techniques achieve this solution: 1) Paging and
2) Segmentation

11