Sri Devaraj Urs Educational Trust (R.

)
R. L. JALAPPA INSTITUTE OF TECHNOLOGY
(Approved by AICTE, New Delhi, Affiliated to VTU, Belagavi & Accredited by NAAC “A” Grade)
Kodigehalli, Doddaballapur- 561 203
Department of CS&E (Artificial Intelligence & Machine Learning)

Subject Code: BCS303

Subject Name: Operating Systems
Module Number: 04
Name of the Module: Virtual Memory Management File System,
Implementation of File System
Scheme: 2022
Prepared by
Manjunatha N
Assistant Professor
Institute Vision
To be a premier Institution by imparting quality Technical education, Professional Training
and Research.

Institute Mission
M1: To provide an outstanding Teaching, Learning and Research environment through
Innovative Practices in Quality Education.
M2: Develop Leaders with high level of Professionalism to have career in the Industry, Zeal
for Higher Education, focus on Entrepreneurial and Societal activities.

Department Vision
To empower the students with knowledge and skills to develop the competency in the field of
Artificial Intelligence and Machine Learning.

Department Mission
M1: To craft the students with Novel and Intellectual skills to capability in the field of
Artificial Intelligence and Machine Learning.
M2: To train the students to have Professional career in the field of AI and ML and zeal for
Higher Studies and Research.
 Sri Devaraj Urs Educational Trust (R.)
R. L. JALAPPA INSTITUTE OF TECHNOLOGY
(Approved by AICTE, New Delhi, Affiliated to VTU, Belagavi & Accredited by NAAC “A” Grade)
Kodigehalli, Doddaballapur- 561 203
Department of CS&E (Artificial Intelligence & Machine Learning)

PROGRAMME SPECIFIC OUTCOMES (PSOs)

PSO1: Students will have the ability to understand analyse and demonstrate the knowledge
of Human cognition, Artificial Intelligence, Machine Learning in terms of real world
problems to meet the challenges of future.

PSO2: Students will have the knowledge of software, Hardware, Algorithms, Modelling
Networking and Application Development.

PSO3: Students will have the ability to develop computational knowledge using Innovative
tools and techniques to solve problems in the areas related to Machine learning and Artificial
Intelligence.

PROGRAMME EDUCATIONAL OBJECTIVES (PEOs)

PEO1: Graduates will have Prospective careers in the field of AI and ML.

PEO2: Graduates will have good Leadership Qualities, Self Learning abilities and zeal for
higher studies and Research.

PEO3: Graduates will follow Ethical Practices and exhibit high level of professionalism by
participating and addressing Technical, Business and Environmental challenges.
 Outline
 VIRTUAL MEMORY MANAGEMENT
 Background
 Demand paging
 Copy-on-write;
 Page replacement
 Allocation of frames
 Thrashing
 FILE SYSTEM, IMPLEMENTATION OF FILE SYSTEM
 File concept, Access methods, Directory structure, File system mounting, File
sharing
 Protection
 Implementing File system
 File system structure
 File system implementation
 Directory implementation
 Allocation methods
 Free space management

Department of Computer Science, RLJIT 4

 Virtual-Memory Management
Virtual memory is a technique that allows the execution of processes that are not
completely in memory. One major advantage of this scheme is that programs can be
larger than physical memory.

In practice, most real processes do not need all their pages, or at least not all at
once, for several reasons:
1. Error handling code is not needed unless that specific error occurs, some of
which are quite rare.
2. Certain features of certain programs are rarely used.

The ability to load only the portions of processes that are actually needed has
several benefits:
 Programs could be written for a much larger address space (virtual memory
space ) than physically exists on the computer.
 Because each process is only using a fraction of their total address space, there is
more memory left for other programs, improving CPU utilization and system
throughput.
 Less I/O is needed for swapping processes
Department in and
of Computer out
Science, RLJITof RAM, speeding things
5
up.
 Virtual-Memory Management

The figure below shows the general layout of virtual memory, which can be much
larger than physical memory:

Figure: Diagram showing virtual memory that is larger than physical-memory

Department of Computer Science, RLJIT 6
 Virtual-Memory Management

Virtual-memory can be implemented by:

1) Demand paging and
2) Demand segmentation.

Department of Computer Science, RLJIT 7

 Virtual-Memory Management

Demand Paging:
The basic idea behind demand paging is that when a process is swapped in, its
pages are not swapped in all at once. Rather they are swapped in only when the
process needs them. ( on demand. ) This is termed as lazy swapper, although a
pager is a more accurate term.

Figure : Transfer of a paged memory to contiguous disk space

The basic idea behind demand paging is that when a process is swapped in, the
pager only loads into memory those pages that is needed presently.
Department of Computer Science, RLJIT 8
 Virtual-Memory Management

 Pages that are not loaded into memory are marked as invalid in the page table,
using the invalid bit. Pages loaded in memory are marked as valid.
 If the process only ever accesses pages that are loaded in memory ( memory
resident pages ), then the process runs exactly as if all the pages were loaded in
to memory.

Department of Computer Science, RLJIT 9

 Virtual-Memory Management

A page-fault occurs when the process tries to access a page that was not brought
into memory. Procedure for handling the page-fault (Figure 4.4):
1) Check an internal-table to determine
whether the reference was a valid or an
invalid memory access.
2) If the reference is invalid, we terminate
the process. If reference is valid, but
we have not yet brought in that page, we
now page it in.
3) Find a free-frame (by taking one from
the free-frame list, for example).
4) Read the desired page into the newly
allocated frame.
5) Modify the internal-table and the page-
table to indicate that the page is now in
memory.
6) Restart the instruction that was
Department of Computer Science, RLJIT
interrupted by the trap. 10
 Virtual-Memory Management

Copy-on-Write :
 Copy-on-Write (COW) allows both parent and child processes to
initially share the same pages in memory.
 Fork() system call-----parent process.
 Exec() system call----child process.
 If either process modifies a shared page, only then is the page copied.
 Copy-on-write is a common technique used by several operating
systems like windows xp, Linux and Solaris.

Department of Computer Science, RLJIT 11

 Virtual-Memory Management

Copy-on-Write :

Before Process 1 Modifies Page C

Department of Computer Science, RLJIT 12

 Virtual-Memory Management

Copy-on-Write :

After Process 1 Modifies Page C

Department of Computer Science, RLJIT 13

 Virtual-Memory Management

Page Replacement:
1) FIFO page replacement
2) Optimal page replacement
3) LRU page replacement (Least Recently Used)
4) LFU page replacement (Least Frequently Used)

Department of Computer Science, RLJIT 14

 Virtual-Memory Management

Basic Page Replacement

1. Find the location of the desired page on
disk
2. Find a free frame:
- If there is a free frame, use it
- If there is no free frame, use a page
replacement algorithm to select a victim
frame
3. Bring the desired page into the newly free
frame; update the page and frame tables
4. Restart the process
Department of Computer Science, RLJIT 15
 Virtual-Memory Management

Basic Page Replacement

Page Replacement Algorithms Want lowest page-fault rate.

Evaluate algorithm by running it on a particular string of memory
references (reference string) andDepartment
computing the Science,
of Computer number RLJITof page
16 faults on that
string
 Virtual-Memory Management

Page replacement algorithms

 FIFO (First-In-First-Out)Page Replacement
• Replace the page that occur first.
 Optimal Page Replacement
• Replace the page that will not be used for the
longest period of time.
 LRU(Least Recently Used) Page Replacement
• Replace the page that has not been used for the longest period
of time.

Department of Computer Science, RLJIT 17

 Virtual-Memory Management

LRU Approximation Algorithms

 Reference bit
 With each page associate a bit, initially = 0
 When page is referenced bit set to 1
 Replace the one which is 0 (if one exists)
 We do not know the order, however

 Second chance
 Need reference bit
 Clock replacement
 If page to be replaced (in clock order) has reference bit = 1 then:
 set reference bit 0
 leave page in memory
 replace next page (in clock order), subject to same rules

Department of Computer Science, RLJIT 18

Virtual-Memory Management

Department of Computer Science, RLJIT 19

 Virtual-Memory Management

Counting Algorithms
 Keep a counter of the number of
references that have been made to
each page
 LFU Algorithm: replaces page with
smallest count
 MFU Algorithm: Replace the page with
the highest reference count.

Department of Computer Science, RLJIT 20

 Virtual-Memory Management

Allocation of Frames
 Two major allocation schemes
 fixed allocation
 priority allocation
 Equal allocation – For example, if there are 100 frames
and 5 processes, give each process 20 frames.
 m-frames and n-processes then, m/n frames.

 Proportional allocation – Allocate available memory

according to the size of process.

Department of Computer Science, RLJIT 21

 Virtual-Memory Management

Global vs. Local Allocation

 Global replacement – process selects a
replacement frame from the set of all
frames; one process can take a frame from
another
 Local replacement – each process selects
from only its own set of allocated frames

Department of Computer Science, RLJIT 22

 Virtual-Memory Management

Thrashing
 If a process does not have “enough” pages,
the page-fault rate is very high. This leads to:
 low CPU utilization
 operating system thinks that it needs to
increase the degree of multiprogramming
 another process added to the system
 High paging activity is called Thrashing.
 a process is thrashing if it is spending more
time paging than executing.
Department of Computer Science, RLJIT 23
 Virtual-Memory Management

Thrashing

Department of Computer Science, RLJIT 24

 Virtual-Memory Management

Working-Set Model
 Working set model is based on the assumption of locality.
 This model uses a parameter,  to define the working set window.
 The idea is to examine the most recent  page references.
 If a page is in active use, it will be in the working set.
 If it is no longer being used, it will be drop from the working set.

Department of Computer Science, RLJIT 25