Virtual Memory

Management and File

Management
2
Contents

● Basics of Virtual Memory

● Demand Paging
● Page Replacement Policies
● Access methods - files
● Directory structure
● File system
● Allocation strategies
● Free space management
● Efficiency and Performance

3
What is Virtual Memory?

● It gives illusion to programmer that a process whose size

is greater than RAM can also be executed!
● That means a process whose size is greater than size of
RAM can also be executed.
● Size of main memory is fixed and limited whereas size of
process can be anything.
● Ideally we want to place more number of processes in the
main memory; multiprogramming

4
What is Virtual Memory?

● Till now we tried to place entire process into main

memory using different strategies like - MFT, MVT,
Paging, Segmentation etc.
● CPU executes one instruction at a time or in other words
CPU refers one page or segment at a time.
● So why to load entire process into main memory?
● Why not only required part like pages/segments loaded
into memory?
● This is the basic idea behind virtual memory concept.

5
Virtual Memory

● In fact, an examination of real programs shows us that, in

many cases, the entire program is not needed.

● For instance, consider the following:

● Programs often have code to handle unusual error conditions.
Since these errors seldom, if ever, occur in practice, this
code is almost never executed.
● Arrays, lists, and tables are often allocated more memory
than they actually need. An array may be declared 100 by 100
elements, even though it is seldom larger than 10 by 10
elements.

6
Virtual Memory

● Virtual memory makes the task of programming much easier,

because the programmer no longer needs to worry about the
amount of physical memory available;

● Programmer can concentrate instead on programming the

problem that is to be solved.

● This technique frees programmers from the concerns of

memory-storage limitations.
● Virtual memory is not easy to implement, however, and may
substantially decrease performance if it is used carelessly.

7
 Virtual Memory Block Diagram
Frame Number Valid / Invalid
Process 1 Process 3
OS p0 p0
0 p1 p1 p1
1 p0 Swap-out p2 p2
2 p1 p3 p3
3 p2 p4 p4
CPU
4 p4 p5
Process 2
Page Table 5 p2 Swap-in p6
p0
6 p1
p1 Process 4
● There are 4 processes present on HDD 7 p5
● All processes divided into pages p2 p0
8 p0
● Page size = frame size p3 p1
9
● Note that only some (required pages) p2
are fetched into main memory 10
● Pages may not stored in contiguous RAM
fashion Hard Disk
8
 Virtual Memory Block Diagram
Frame Number Valid / Invalid
Process 1 Process 3
Page no.
OS p0 p0
Number 0 — 0 0 p1 p1 p1
1 0 1 1 p0 Swap-out p2 p2
P2 2 3 1 2 p1 p3 p3
3 — 0 3 p2 p4 p4
CPU
4 p4 p5
Page Table Process 2
of P2 5 p2 Swap-in p6
p0
6 p1
● Let's assume Process P2 is getting p1 Process 4
7 p5
executed p2 p0
8 p0
● Pages P1 and P2 are already present 9
p3 p1
in main memory - observe page table p2
● Page 0 and page 3 of process P2 are 10
not present in RAM so their valid RAM
Hard Disk
bit is set to 0
9
 Virtual Memory Block Diagram- Demand Paging
Frame Number Valid / Invalid
Process 1 Process 3
OS p0 p0
0 — 0 0 p1 p1 p1
1 0 1 1 p0 Swap-out p2 p2
P2 2 3 1 2 p1 p3 p3
3 — 0 3 p2 p4 p4
CPU
4 p4 p5
Page Table Process 2
of P2 5 p2 Swap-in p6
p0
6 p1
● Let's say CPU requests page 3 of p1 Process 4
7 p5
Process 2 which is not present in mm p2 p0
8 p0
● CPU checks entry in page table of P2 p3 p1
● As there is no entry of page 2 a 9
TRAP signal gets generated p2
10
● Now a user process changes mode to
RAM
kernel mode Hard Disk
10
 Virtual Memory Block Diagram
Frame Number Valid / Invalid
Process 1 Process 3
OS p0 p0
0 — 0 0 p1 p1 p1
1 0 1 1 p0 Swap-out p2 p2
P2 2 3 1 2 p1 p3 p3
3 9 1 3 p2 p4 p4
CPU
4 p4 p5
Page Table Process 2
of P2 5 p2 Swap-in p6
p0
6 p1
● In kernel mode, OS brings page 3 of p1 Process 4
7 p5
process 2 into RAM let say at free p2 p0
8 p0
frame number 9 p3 p1
● Corresponding page table entry also 9 P3
gets updated p2
10
● Now process changes its mode back to
RAM
user mode Hard Disk
● CPU access page 3 by referring page 11
table entry
Virtual Memory - Page fault

● When requested page not found in the main memory, Page fault
occurs.
● When Page fault occurs, process switches from user mode to
kernel mode.
● In kernel mode operating system fetches required page from
secondary storage.
● If there is free frame in main memory, the required page
will be placed in that frame
● If there is no free space then existing page gets replaced
with new page using page replacement policies.
● Existing page will be placed in the HDD.
12
13
Virtual Memory - Page Replacement Algorithms

● Whenever page fault occurs, OS needs to bring required page into

main memory. If there is no free frame in main memory then an
existing page in main memory needs to be replaced with new page. For
page replacement following algorithms are used
1. First in First Out
2. Optimal Page Replacement
3. Least Recently Used
The ultimate aim of page replacement policies is to reduce number of
page faults.

The string of memory references is called reference string.

14
Virtual Memory - Page Replacement Algorithms
1. First In First Out
Reference
7 0 1 2 0 3 0 4 2 3 0 3 1 2 0
String

F1 1 1 1 1 0 0 0 3 3 3 3 2 2
CPU
F2 0 0 0 0 3 3 3 2 2 2 2 1 1 1
Frames
F3 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0

F F F F+R H F+R F+R F+R F+R F+R F+R H F+R F+R H

1. If there is a free frame and Page fault -> store new page with no
replacement
2. If no free frame and If page fault -> Replace new page with page arrived
15
first
Virtual Memory - Page Replacement Algorithms
1. First In First Out
Reference
7 0 1 2 0 3 0 4 2 3 0 3 1 2 0
String

F1 1 1 1 1 0 0 0 3 3 3 3 2 2
CPU
F2 0 0 0 0 3 3 3 2 2 2 2 1 1 1
Frames
F3 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0

F F F F+R H F+R F+R F+R F+R F+R F+R H F+R F+R H

● Page Hit ratio = # Page hits/# pages = 3/15

● Page Miss Ratio = # Page Miss/# pages = 12/15
● No of Page faults= 12
16
 Virtual Memory - Page Replacement Algorithms
What is the effect of number of frames available in RAM on
page fault ration?
Reference
1 2 3 4 1 2 5 1 2 3 4 5
String

F1 3 3 3 2 2 2 2 2 4 4
CPU
F2 2 2 2 1 1 1 1 1 3 3 3
Frames
F3 1 1 1 4 4 4 5 5 5 5 5 5

F F F F+R F+R F+R F+R H H F+R F+R H

Page Hit Ratio =
3/12
No of Page FIFO with 3 frames
faults= 9 17
 Virtual Memory - Page Replacement Algorithms
What is the effect of number of frames available in RAM on
page fault ration? - Belady’s Anomaly
Reference
1 2 3 4 1 2 5 1 2 3 4 5
String

F1 4 4 4 4 4 4 3 3 3
CPU
F2 3 3 3 3 3 3 2 2 2 2
Frames
F3 2 2 2 2 2 2 1 1 1 1 5
F4 1 1 1 1 1 1 5 5 5 5 4 4
Page Hit Ratio =
2/12 F F F F H H F+R F+R F+R F+R F+R F+R
No of Page
faults= 10 FIFO with 4 frames 18
Virtual Memory - Page Replacement Algorithms
What is the effect of number of frames available in RAM on
page fault ration? - Belady’s Anomaly

The increase in the number of frames considerably decreases

the number of page faults. However, sometimes reverse action
occurs when the increased number of frames results in
increased page faults. This exception is known as the
Belady’s Anomaly.

19
 Virtual Memory - Page Replacement Algorithms
2. Optimal Page Replacement - Replace the page that will
not be used for the longest period of time.
Reference
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2
String

F1 2 2 2 2 2 2 2 2 2 2 2 2
CPU F2 1 1 1 1 1 4 4 4 4 4 4 1 1
Frames
F3 0 0 0 0 0 0 0 0 0 0 0 0 0 0
F4 7 7 7 7 7 3 3 3 3 3 3 3 3 3 3

Page Hit Ratio =

F F F F H F+R H F+R H H H H H F+R H
8/15
20
 Virtual Memory - Page Replacement Algorithms
3. Least Recently Used - Replace the least recently used
page in past or page has not been used for longest period
of time
Reference
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2
String

F1 2 2 2 2 2 2 2 2 2 2 2 2
CPU F2 1 1 1 1 1 4 4 4 4 4 4 1 1
Frames
F3 0 0 0 0 0 0 0 0 0 0 0 0 0 0
F4 7 7 7 7 7 3 3 3 3 3 3 3 3 3 3

Page Hit Ratio =

F F F F H F+R H F+R H H H H H F+R H
8/15
21
LRU

● It works on the idea that the more recently used blocks are more likely to be
referenced again.

22
Thrashing

24
25
Thrashing

26
● File Handling in Operating System

27
File System

● A file is a collection of related information defined by

its creator.

● Files are mapped by the operating system onto physical

mass-storage devices.

● A file system describes how files are mapped onto physical

devices, as well as how they are accessed and manipulated
by both users and programs.

28
File System

● Accessing physical storage can often be slow, so file

systems must be designed for efficient access.

● Other requirements may be important as well, including

providing support for file sharing and remote access to
files.

29
File Concept

● Contiguous logical address space

● Types:
○ Data
■ numeric
■ character
■ binary
○ Program
● Contents defined by file’s creator
○ Many types
■ Consider text file, source file,
executable file
File Attributes
● Name – only information kept in human-readable form
● Identifier – unique tag (number) identifies file
within file system
● Type – needed for systems that support different
types
● Location – pointer to file location on device
● Size – current file size
● Protection – controls who can do reading, writing,
executing
● Time, date, and user identification – data for
protection, security, and usage monitoring
● Information about files are kept in the directory
structure, which is maintained on the disk
● Many variations, including extended file attributes
such as file checksum
● Information kept in the directory structure
File Handling in Operating System

● File system - A software program in OS that manages files

and folders.
● It manages how data will be stored and fetched.
● Files and folders are stored on non volatile memories
like HDD, SSD or Pendrive.

File System

Data Storage and

User File Folder
fetch
32
File Attributes and Operations

● File Attributes: Name, extension, identifier, location,

size, created date, modified date, permissions etc.
● File Operations: Create, read, write, delete, truncate
etc.

33
File Allocation Methods

● Two types of file allocation methods, contiguous and non

contiguous allocation
● A file is divided into number of logical units and stored
into sectors on the disk.

Mapping

Original File divided into Disk with Sectors 35

File logical blocks
File Allocation Methods

● Contiguous allocation File A

File Start Length File B

0 1 2 3 4
A 0 3
5 6 7 8 9
B 6 5
10 11 12 13 14
C 14 4 File C
15 16 17 18 19

Disk with Sectors 36

File Allocation Methods

● Contiguous allocation - Advantages and disadvantages

1. Easy to Implement
2. Excellent read performance
3. Disk may get fragmented
4. Difficult to grow file

37
File Allocation Methods

● Non Contiguous allocation -

1. Linked list allocation
2. Indexed File Allocation

38
File Allocation Methods
1. Linked list allocation:-
File A
File Start Length

A 0 3
File B
0 1 2 3 4 B 3 5

C 2 4
5 6 7 8 9

0 7 7 16 16 -1
10 11 12 13 14 File C

15 16 17 18 19 2 5 5 10 10 15 15 -1

3 13 13 6 6 18 18 11 11 -1
Disk with Sectors 39
File Allocation Methods

● Linked List allocation - Advantages and disadvantages

1. File size can be expanded or shrunk
2. Large seek time
3. Random or direct access is difficult
4. Overhead of pointers

40
File Allocation Methods
2. Indexed allocation:-
File A

File Start
Sector 0
A 0 A0 6
File B
A1 9
0 1 2 3 4 B 3 A2 10

5 6 7 8 9 C 12

10 11 12 13 14 File A :- Sector 0 contains mapping of File C

blocks to sectors in index format
15 16 17 18 19 File B :- Sector 3 contains mapping of
blocks to sectors in index format
File C :- Sector 12 contains mapping of
Disk with Sectors blocks to sectors in index format 41
2. Indexed allocation

42
Free Space Management

A file system is responsible to allocate the free blocks

to the file therefore it has to keep track of all the free
blocks present in the disk. There are mainly three
approaches by using which, the free blocks in the disk are
managed.

1. Bit vector or Bit map

2. Linked List
3. Grouping

43
Free Space Management

1. Bit vector or Bit map:-

● In this approach, the free space list is implemented as a
bit map vector.
● It contains the number of bits where each bit represents
each block.
● If the block is empty then the bit is 1 otherwise it is 0.
● Initially all the blocks are empty therefore each bit in
the bit map vector contains 1.

1 0 1 1 0 1 1 1 1 0 0 1 Free

Occupied

44
Free Space Management
2. Linked List:-
● In this approach, the free disk blocks are linked together
i.e. a free block contains a pointer to the next free
block.
● The block number of the very first disk block is stored at
a separate location on disk and is also cached in memory.

Head of the first free sector is

0 1 2 3 4 stored

5 6 7 8 9

10 11 12 13 14 45
 Linked list (free list)
 Cannot get contiguous space
easily
 No waste of space
 No need to traverse the entire
list (if # free blocks recorded)

46
Free Space Management
3. Grouping:-
● This approach stores the address of the free blocks in the first
free block.
● The first free block stores the address of some, say n free blocks.
Out of these n blocks, the first n-1 blocks are actually free and
the last block contains the address of next free n blocks.
● An advantage of this approach is that the addresses of a group of
free disk blocks can be found easily.

47
File Directory Structure
● Directory can be defined as the listing of the related
files on the disk. The directory may store some or the
entire file attributes.

● To get the benefit of different file systems on the

different operating systems, A hard disk can be divided
into the number of partitions of different sizes.

● The partitions are also called volumes or mini disks.

48
File Directory Structure

49
Directory Implementation

● There is the number of algorithms by using which, the directories

can be implemented.
● However, the selection of an appropriate directory implementation
algorithm may significantly affect the performance of the system.

● The directory implementation algorithms are classified according

to the data structure they are using.
● Linear List
● Hash Table

50
Directory Implementation

● Linear List:-
○ All the files in a directory are maintained as linked list.
○ Each file contains the pointers to the data blocks which are
assigned to it and the next file in the directory.
○ When a new file is created, then the entire list is checked
whether the new file name is matching to a existing file name
or not.
○ In case, it doesn't exist, the file can be created at the
beginning or at the end.
○ Therefore, searching for a unique name is a big concern
because traversing the whole list takes time because of
linear search.
51
Directory Implementation

● Linear List:-
○ Therefore, searching for a unique name is a big concern
because traversing the whole list takes time.
○ The list needs to be traversed in case of every operation
(creation, deletion, updating, etc) on the files therefore
the systems become inefficient.

52
Directory Implementation
● Hash Table:-
○ To overcome the drawbacks of linked list implementation of
directories, there is an alternative approach that is hash
table.
○ This approach suggests to use hash table along with the
linked lists.

File Name Pointer to

data block

File Name File A

Hash
Function File B Linked
List
File C
53
Efficiency and Performance

● Disk tend to represent a major drawback in system performance

● Disk is the slowest component of the system
● Whenever a file is read/written corresponding directory entry
needs to be maintained like date of access.
● This may affect overall efficiency of the disk
● A frequently accessed file for read operation also requires to
perform read/write operation on attributes
● Apart from different memory allocation strategies one can
improve the performance of the system by other ways such as
maintaining caches to store complete track of the disk

54