OPERATING SYSTEMS

ETCS 304

UNIT 1

Department of CSE, Operating Systems BVCOE NEW DELHI

 Chapter 1: Introduction

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 1: Objectives
 To describe the basic organization of computer systems
 To provide a grand tour of the major components of
operating systems
 To give an overview of the many types of computing
environments

BVCOE NEW DELHI

Department of CSE, Operating Systems BVCOE NEW DELHI
What is an Operating System?
 A program that acts as an intermediary between a user of a
computer and the computer hardware
 Operating system goals:
 Execute user programs and make solving user problems easier
 Make the computer system convenient to use
 Use the computer hardware in an efficient manner

BVCOE NEW DELHI

Department of CSE, Operating Systems BVCOE NEW DELHI
Computer System Structure
 Computer system can be divided into four components:
 Hardware – provides basic computing resources
 CPU, memory, I/O devices
 Operating system
 Controls and coordinates use of hardware among various applications and
users
 Application programs – define the ways in which the system
resources are used to solve the computing problems of the users
 Word processors, compilers, web browsers, database systems, video
games
 Users
 People, machines, other computers

BVCOE NEW DELHI

Department of CSE, Operating Systems BVCOE NEW DELHI
Four Components of a Computer System

Department of CSE, Operating Systems BVCOE NEW DELHI

What Operating Systems Do
 Depends on the point of view
 Users want convenience, ease of use and good
performance
 Don’t care about resource utilization
 But shared computer such as mainframe or
minicomputer must keep all users happy

Department of CSE, Operating Systems BVCOE NEW DELHI

 Operating System Definition
 OS is a resource allocator
 Manages all resources
 Decides between conflicting requests for efficient and
fair resource use
 OS is a control program
 Controls execution of programs to prevent errors
and improper use of the computer

Department of CSE, Operating Systems BVCOE NEW DELHI

 Operating System Definition (Cont.)
 No universally accepted definition
 “Everything a vendor ships when you order an
operating system” is a good approximation
 But varies wildly
 “The
The one program running at all times on the
computer” is the kernel.
 Everything else is either
 a system program (ships with the operating system) ,
or
 an application program.

Department of CSE, Operating Systems BVCOE NEW DELHI

Computer Startup

 bootstrap program is loaded at power-up or

reboot
 Typically stored in ROM or EPROM, generally
known as firmware
 Initializes all aspects of system
 Loads operating system kernel and starts
execution

Department of CSE, Operating Systems BVCOE NEW DELHI

 Interrupt Handling
 The operating system preserves the state of the
CPU by storing registers and the program counter
 Occurrence of a new event is signaled by an
interrupt from either h/w or s/w.
 Determines which type of interrupt has occurred:
 polling
 vectored interrupt system
 Separate segments of code determine what action
should be taken for each type of interrupt

Department of CSE, Operating Systems BVCOE NEW DELHI

Storage Structure
 Main memory – only large storage media that the CPU can
access directly
 Random access
 Typically volatile

 Secondary storage – extension of main memory that

provides large nonvolatile storage capacity
 Hard disks – rigid metal or glass platters covered with
magnetic recording material
 Disk surface is logically divided into tracks, which are subdivided into sectors
 The disk controller determines the logical interaction between the device and the
computer

Department of CSE, Operating Systems BVCOE NEW DELHI

Caching

 Important principle, performed at many levels in a

computer (in hardware, operating system, software)
 Information in use copied from slower to faster
storage temporarily
 Faster storage (cache) checked first to determine if
information is there
 If it is, information used directly from the cache (fast)
 If not, data copied to cache and used there
 Cache smaller than storage being cached
 Cache management important design problem
 Cache size and replacement policy

Department of CSE, Operating Systems BVCOE NEW DELHI

 Operating System Structure
 Multiprogramming needed for efficiency
 Single user cannot keep CPU and I/O devices busy at all times
 Multiprogramming organizes jobs (code and data) so CPU always has one to execute
 A subset of total jobs in system is kept in memory

 One job selected and run via job scheduling

 When it has to wait (for I/O for example), OS switches to another job

 Timesharing (multitasking) is logical extension in which CPU switches jobs

so frequently that users can interact with each job while it is running, creating interactive
computing
 Response time should be < 1 second
process
 Each user has at least one program executing in memory 

 If several jobs ready to run at the same time  CPU scheduling

 If processes don’t fit in memory, swapping moves them in and out to run

 Virtual memory allows execution of processes not completely in memory

Department of CSE, Operating Systems BVCOE NEW DELHI

 Computer-System Architecture
• Batch processing systems
• Multiprogramming systems
• Time sharing/Multitasking
systems
 Most systems use a single general-purpose processor
 Most systems have special-purpose processors as well
 Multiprocessors systems growing in use and importance
 Also known as parallel systems, tightly-coupled systems
 Advantages include:
1. Increased throughput
2. Economy of scale
3. Increased reliability – graceful degradation or fault tolerance
 Two types:
1. Asymmetric Multiprocessing – each processor is assigned a specie task.
2. Symmetric Multiprocessing – each processor performs all tasks

Department of CSE, Operating Systems BVCOE NEW DELHI

Symmetric Multiprocessing Architecture

Department of CSE, Operating Systems BVCOE NEW DELHI

 LECTURE 2

Department of CSE, Operating Systems BVCOE NEW DELHI

 Computing Environments – Distributed
 Distributed computiing
 Collection of separate, possibly heterogeneous, systems
networked together
 Network is a communications path, TCP/IP most common
 Local Area Network (LAN)
 Wide Area Network (WAN)
 Metropolitan Area Network (MAN)
 Personal Area Network (PAN)
 Network Operating System provides features between
systems across network
 Communication scheme allows systems to exchange messages
 Illusion of a single system

Department of CSE, Operating Systems BVCOE NEW DELHI

 Computing Environments – Client-Server
 Client-Server Computing
 Dumb terminals supplanted by smart PCs
 Many systems now servers, responding to requests generated
by clients
 Compute-server system provides an interface to client to
request services (i.e., database)
 File-server system provides interface for clients to store
and retrieve files

Department of CSE, Operating Systems BVCOE NEW DELHI

 Computing Environments - Peer-to-Peer
 Another model of distributed system
 P2P does not distinguish clients and
servers
 Instead all nodes are considered peers
 May each act as client, server or both
 Node must join P2P network
 Registers its service with central lookup
service on network, or
 Broadcast request for service and respond to
requests for service via discovery protocol
 Examples include Napster and Gnutella,
Voice over IP (VoIP) such as Skype

Department of CSE, Operating Systems BVCOE NEW DELHI

 Computing Environments – Real-Time Embedded Systems

 Real-time embedded systems most prevalent form of

computers
 Vary considerable, special purpose, limited purpose OS,
real-time OS
 Use expanding
 Many other special computing environments as well
 Some have OSes, some perform tasks without an OS
 Real-time OS has well-defined fixed time constraints
 Processing must be done within constraint
 Correct operation only if constraints met

Department of CSE, Operating Systems BVCOE NEW DELHI

ONLINE RESOURCES:
https://www.youtube.com/watch?v=a2B69vCtjOU&list=PL3-
wYxbt4yCjpcfUDz-TgD_ainZ2K3MUZ&index=2
GATE QUESTIONS
1. Which of the following requires a device driver?
 a) Register
 b) Cache
 c) Main memory
 d) Disk
 Answer: (d)
2. Which of the following does not interrupt a running process?
 (a) A device
 (b) Timer
 (c) Scheduler process
 (d) Power failure

Department of CSE, Operating Systems BVCOE NEW DELHI

GATE QUESTIONS
3. Increasing the RAM of a computer typically improves performance because:
 a. Virtual memory increases
 b. Larger RAMs are faster
 c. Fewer page faults occur
 d. Fewer segmentation faults occur

Department of CSE, Operating Systems BVCOE NEW DELHI

 Chapter 8: Main Memory

Department of CSE, Operating Systems BVCOE NEW DELHI

 LECTURE 3: Memory Management
 Background
 Swapping
 Contiguous Memory Allocation
 Segmentation
 Paging
 Structure of the Page Table
 Example: The Intel 32 and 64-bit Architectures
 Example: ARM Architecture

Department of CSE, Operating Systems BVCOE NEW DELHI

Objectives

 To provide a detailed description of various ways of

organizing memory hardware
 To discuss various memory-management
techniques, including paging and segmentation.

Department of CSE, Operating Systems BVCOE NEW DELHI

 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
 Memory unit only sees a stream of addresses + read
requests, or address + data and write requests
 Register access in one CPU clock (or less)
 Cache sits between main memory and CPU registers
 Protection of memory required to ensure correct
operation

Department of CSE, Operating Systems BVCOE NEW DELHI

Base and Limit Registers
 A pair of base and limit registers define the logical
address space
 CPU must check every memory access generated in user
mode to be sure it is between base and limit for that user

Department of CSE, Operating Systems BVCOE NEW DELHI

Hardware Address Protection

Department of CSE, Operating Systems BVCOE NEW DELHI

Binding of Instructions and Data to Memory

 Address binding of instructions and data to memory

addresses can happen at three different stages
 Compile time: If memory location known a priori,
absolute code can be generated; must recompile code
if starting location changes
 Load time: Must generate relocatable code if
memory location is not known at compile time
 Execution time: Binding delayed until run time if the
process can be moved during its execution from one
memory segment to another

Department of CSE, Operating Systems BVCOE NEW DELHI

Multistep Processing of a User Program

Department of CSE, Operating Systems BVCOE NEW DELHI

Logical vs. Physical Address Space
 The concept of a logical address space that is bound to a
separate physical address space is central to proper
memory management
 Logical address – generated by the CPU; also referred to as
virtual address
 Physical address – address seen by the 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
 Logical address space is the set of all logical addresses
generated by a program
 Physical address space is the set of all physical addresses
generated by a program

Department of CSE, Operating Systems BVCOE NEW DELHI

Memory-Management Unit (MMU)
 Hardware device that at run time maps virtual to physical
address
 To start, consider simple scheme where the value in the
relocation register is added to every address generated by a
user process at the time it is sent to memory
 Base register now called relocation register
 MS-DOS on Intel 80x86 used 4 relocation registers
 The user program deals with logical addresses; it never sees
the real physical addresses
 Execution-time binding occurs when reference is made to
location in memory
 Logical address bound to physical addresses

Department of CSE, Operating Systems BVCOE NEW DELHI

Dynamic relocation using a relocation register
 Routine is not loaded until it is
called
 Better memory-space utilization;
unused routine is never loaded
 All routines kept on disk in
relocatable load format
 Useful when large amounts of
code are needed to handle
infrequently occurring cases

Department of CSE, Operating Systems BVCOE NEW DELHI

Dynamic Linking
 Static linking – system libraries and program code
combined by the loader into the binary program image
 Dynamic linking –linking postponed until execution
time
 Small piece of code, stub, used to locate the
appropriate memory-resident library routine
 Stub replaces itself with the address of the routine, and
executes the routine
 Operating system checks if routine is in processes’
memory address
 If not in address space, add to address space

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 4

Department of CSE, Operating Systems BVCOE NEW DELHI

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
 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

Department of CSE, Operating Systems BVCOE NEW DELHI

Schematic View of Swapping

Department of CSE, Operating Systems BVCOE NEW DELHI

Contiguous Allocation
 Main memory must support both OS and user
processes
 Limited resource, must allocate efficiently
 Contiguous allocation is one early method
 Main memory usually into two partitions:
 Resident operating system, usually held in low memory
with interrupt vector
 User processes then held in high memory
 Each process contained in single contiguous section of
memory

Department of CSE, Operating Systems BVCOE NEW DELHI

Contiguous Allocation (Cont.)
 Relocation registers used to protect user processes from
each other, and from changing operating-system code
and data
 Base register contains value of smallest physical address
 Limit register contains range of logical addresses – each
logical address must be less than the limit register
 MMU maps logical address dynamically
 Can then allow actions such as kernel code being
transient and kernel changing size

Department of CSE, Operating Systems BVCOE NEW DELHI

Hardware Support for Relocation and Limit Registers

Department of CSE, Operating Systems BVCOE NEW DELHI

 Multiple-partition allocation
 Degree of multiprogramming limited by number of partitions
 Variable-partition sizes for efficiency (sized to a given process’ needs)
 Hole – block of available memory; holes 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)

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 5

Department of CSE, Operating Systems BVCOE NEW DELHI

 Dynamic Storage-Allocation Problem
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

First-fit and best-fit better than worst-fit in terms of speed and storage
utilization

Department of CSE, Operating Systems BVCOE NEW DELHI

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
 1/3 may be unusable -> 50-percent rule

Department of CSE, Operating Systems BVCOE NEW DELHI

Fragmentation (Cont.)
 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, and
is done at execution time

Department of CSE, Operating Systems BVCOE NEW DELHI

Segmentation
 Memory-management scheme that supports user view of memory
 A program is a collection of segments
 A segment is a logical unit such as:
main program
procedure
function
method
object
local variables, global variables
common block
stack
symbol table
arrays

Department of CSE, Operating Systems BVCOE NEW DELHI

User’s View of a Program

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 6

Department of CSE, Operating Systems BVCOE NEW DELHI

Logical View of Segmentation
1

4
1

3 2
4

user space physical memory space

Department of CSE, Operating Systems BVCOE NEW DELHI

Segmentation Architecture
 Logical address consists of a two tuple:
<segment-number, offset>,

 Segment table – maps two-dimensional physical addresses; each table entry has:
 base – contains the starting physical address where the segments reside in
memory
 limit – specifies the length of the segment

 Segment-table base register (STBR) points to the segment table’s location in

memory

 Segment-table length register (STLR) indicates number of segments used by a

program;

Department of CSE, Operating Systems BVCOE NEW DELHI

Segmentation Architecture (Cont.)
 Protection
 With each entry in segment table associate:
 validation bit = 0  illegal segment
 read/write/execute privileges

 Protection bits associated with segments; code

sharing occurs at segment level
 Since segments vary in length, memory allocation is
a dynamic storage-allocation problem
 A segmentation example is shown in the following
diagram

Department of CSE, Operating Systems BVCOE NEW DELHI

Segmentation Hardware

Department of CSE, Operating Systems BVCOE NEW DELHI

Paging
 Physical address space of a process can be noncontiguous; process is
allocated physical memory whenever the latter is available
 Avoids external fragmentation
 Avoids problem of varying sized memory chunks
 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

Department of CSE, Operating Systems BVCOE NEW DELHI

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

Department of CSE, Operating Systems BVCOE NEW DELHI

Paging Hardware

Department of CSE, Operating Systems BVCOE NEW DELHI

Paging Model of Logical and Physical Memory

Department of CSE, Operating Systems BVCOE NEW DELHI

Paging Example

n=2 and m=4 32-byte memory and 4-byte pages

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 7

Department of CSE, Operating Systems BVCOE NEW DELHI

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 (PTLR) 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)

Department of CSE, Operating Systems BVCOE NEW DELHI

Implementation of Page Table (Cont.)
 Some TLBs store address-space identifiers
(ASIDs) in each TLB entry – uniquely identifies each
process to provide address-space protection for that
process
 Otherwise need to flush at every context switch
 TLBs typically small (64 to 1,024 entries)
 On a TLB miss, value is loaded into the TLB for faster
access next time
 Replacement policies must be considered
 Some entries can be wired down for permanent fast
access

Department of CSE, Operating Systems BVCOE NEW DELHI

Associative Memory
 Associative memory – parallel search
Page # Frame #

 Address translation (p, d)

 If p is in associative register, get frame # out
 Otherwise get frame # from page table in memory

Department of CSE, Operating Systems BVCOE NEW DELHI

Paging Hardware With TLB

Department of CSE, Operating Systems BVCOE NEW DELHI

Effective Access Time
 Associative Lookup =  time unit
 Can be < 10% of memory access time
 Hit ratio = 
 Hit ratio – percentage of times that a page number is found in the associative
registers; ratio related to number of associative registers
 Consider  = 80%,  = 20ns for TLB search, 100ns for memory access
 Effective Access Time (EAT)
EAT = (1 + )  + (2 + )(1 – )
=2+–
 Consider  = 80%,  = 20ns for TLB search, 100ns for memory access
 EAT = 0.80 x 100 + 0.20 x 200 = 120ns
 Consider more realistic hit ratio ->  = 99%,  = 20ns for TLB search, 100ns for
memory access
 EAT = 0.99 x 100 + 0.01 x 200 = 101ns

Department of CSE, Operating Systems BVCOE NEW DELHI

Memory Protection
 Memory protection implemented by associating
protection bit with each frame to indicate if read-only
or read-write access is allowed
 Can also add more bits to indicate page execute-only,
and so on
 Valid-invalid bit attached to each entry in the page
table:
 “valid” indicates that the associated page is in the
process’ logical address space, and is thus a legal page
 “invalid” indicates that the page is not in the process’
logical address space
 Or use page-table length register (PTLR)
 Any violations result in a trap to the kernel
Department of CSE, Operating Systems BVCOE NEW DELHI
 Valid (v) or Invalid (i) Bit In A Page Table

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 8

Department of CSE, Operating Systems BVCOE NEW DELHI

Structure of the Page Table
 Memory structures for paging can get huge using
straight-forward methods
 Consider a 32-bit logical address space as on modern
computers
 Page size of 4 KB (212)
 Page table would have 1 million entries (232 / 212)
 If each entry is 4 bytes -> 4 MB of physical address space
/ memory for page table alone
 That amount of memory used to cost a lot
 Don’t want to allocate that contiguously in main memory

 Hierarchical Paging
 Hashed Page Tables
 Inverted Page Tables
Department of CSE, Operating Systems BVCOE NEW DELHI
Hierarchical Page Tables

 Break up the logical address space into

multiple page tables
 A simple technique is a two-level page table
 We then page the page table

Department of CSE, Operating Systems BVCOE NEW DELHI

Two-Level Page-Table Scheme

Department of CSE, Operating Systems BVCOE NEW DELHI

Two-Level Paging Example
 A logical address (on 32-bit machine with 1K page size) is
divided into:
 a page number consisting of 22 bits
 a page offset consisting of 10 bits

 Since the page table is paged, the page number is further

divided into:
 a 12-bit page number
 a 10-bit page offset

 Thus, a logical address is as follows:

where p1ofisCSE,
Department an index into
Operating the outer
Systems BVCOEpage table, and p2 is the
NEW DELHI
displacement within the page of the inner page table
Address-Translation Scheme

Department of CSE, Operating Systems BVCOE NEW DELHI

 Hashed Page Tables
 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
 Variation for 64-bit addresses is clustered page tables
 Similar to hashed but each entry refers to several pages (such as 16) rather than 1
 Especially useful for sparse address spaces (where memory references are non-
contiguous and scattered)

Department of CSE, Operating Systems BVCOE NEW DELHI

Hashed Page Table

Department of CSE, Operating Systems BVCOE NEW DELHI

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
 Use hash table to limit the search to one — or at most a few — page-table
entries
 TLB can accelerate access
 But how to implement shared memory?
 One mapping of a virtual address to the shared physical address

Department of CSE, Operating Systems BVCOE NEW DELHI

Inverted Page Table Architecture

Department of CSE, Operating Systems BVCOE NEW DELHI

ONLINE RESOURCES
 https://www.youtube.com/watch?v=2OobPx246zg&list=P
L3-wYxbt4yCjpcfUDz-TgD_ainZ2K3MUZ&index=10

Department of CSE, Operating Systems BVCOE NEW DELHI

 GATE QUESTIONS
 1. Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4KB, what is the approximate size of the
page table? (GATE 2001)
 (a) 16 MB
 (b) 8 MB
 (c) 2 MB
 (d) 24 MB
 Answer: (c)
 2. Suppose the time to service a page fault is on the average 10 milliseconds, while a memory access takes 1 microsecond. Then a 99.99% hit ratio
results in average memory access time of (GATE CS 2000)
 (a) 1.9999 milliseconds
 (b) 1 millisecond
 (c) 9.999 microseconds
 (d) 1.9999 microseconds
 Answer: (d)
 3. Consider a 2-way set associative cache memory with 4 sets and total 8 cache blocks (0-7) and a main memory with 128 blocks (0-127). What
memory blocks will be present in the cache after the following sequence of memory block references if LRU policy is used for cache block
replacement. Assuming that initially the cache did not have any memory block from the current job?
0 5 3 9 7 0 16 55

(A) 0 3 5 7 16 55
(B) 0 3 5 7 9 16 55
(C) 0 5 7 9 16 55
(D) 3 5 7 9 16 55

Department of CSE, Operating Systems BVCOE NEW DELHI

GATE QUESTIONS
 4. A 32 – bit wide main memory unit with a capacity of 1 GB is built using 256M X 4-bit
DRAM chips. The number of rows of memory cells in the DRAM chip is 214. The time
taken to perform one refresh operation is 50 nanoseconds. The refresh period is 2
milliseconds. The percentage (rounded to the closet integer) of the time available for
performing the memory read/write operations in the main memory unit is _______ .
(A) 59
(B) 40
(C) 99
(D) None of these

Department of CSE, Operating Systems BVCOE NEW DELHI

 Chapter 9: Virtual Memory

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 1: Virtual Memory
 Background
 Demand Paging
 Copy-on-Write
 Page Replacement
 Allocation of Frames
 Thrashing
 Memory-Mapped Files
 Allocating Kernel Memory
 Other Considerations
 Operating-System Examples

Department of CSE, Operating Systems BVCOE NEW DELHI

Objectives
 To describe the benefits of a virtual memory system
 To explain the concepts of demand paging, page-
replacement algorithms, and allocation of page frames
 To discuss the principle of the working-set model
 To examine the relationship between shared memory and
memory-mapped files
 To explore how kernel memory is managed

Department of CSE, Operating Systems BVCOE NEW DELHI

Background
 Code needs to be in memory to execute, but entire program
rarely used
 Error code, unusual routines, large data structures
 Entire program code not needed at same time
 Consider ability to execute partially-loaded program
 Program no longer constrained by limits of physical memory
 Each program takes less memory while running -> more
programs run at the same time
 Increased CPU utilization and throughput with no increase in response
time or turnaround time
 Less I/O needed to load or swap programs into memory ->
each user program runs faster

Department of CSE, Operating Systems BVCOE NEW DELHI

Background (Cont.)
 Virtual memory – separation of user logical memory
from physical memory
 Only part of the program needs to be in memory for execution
 Logical address space can therefore be much larger than physical address space
 Allows address spaces to be shared by several processes
 Allows for more efficient process creation
 More programs running concurrently
 Less I/O needed to load or swap processes

Department of CSE, Operating Systems BVCOE NEW DELHI

Background (Cont.)
 Virtual address space – logical view of how
process is stored in memory
 Usually start at address 0, contiguous addresses until end of space
 Meanwhile, physical memory organized in page frames
 MMU must map logical to physical

 Virtual memory can be implemented via:

 Demand paging
 Demand segmentation

Department of CSE, Operating Systems BVCOE NEW DELHI

Virtual Memory That is Larger Than Physical Memory

Department of CSE, Operating Systems BVCOE NEW DELHI

 Shared Library Using Virtual Memory

Department of CSE, Operating Systems BVCOE NEW DELHI

Demand Paging
 Could bring entire process into memory at load
time
 Or bring a page into memory only when it is
needed
 Less I/O needed, no unnecessary I/O
 Less memory needed
 Faster response
 More users
 Similar to paging system with swapping (diagram
on right)
 Page is needed  reference to it
 invalid reference  abort
 not-in-memory  bring to memory
 Lazy swapper – never swaps a page into
memory unless page will be needed
 Swapper that deals with pages is a pager

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 2

Department of CSE, Operating Systems BVCOE NEW DELHI

Basic Concepts

 With swapping, pager guesses which pages will be used before swapping out
again
 Instead, pager brings in only those pages into memory
 How to determine that set of pages?
 Need new MMU functionality to implement demand paging
 If pages needed are already memory resident
 No difference from non demand-paging
 If page needed and not memory resident
 Need to detect and load the page into memory from storage
 Without changing program behavior
 Without programmer needing to change code

Department of CSE, Operating Systems BVCOE NEW DELHI

Valid-Invalid Bit
 With each page table entry a valid–invalid bit is associated
(v  in-memory – memory resident, i  not-in-
memory)
 Initially valid–invalid bit is set to i on all entries
 Example of a page table snapshot:

 During MMU address translation, if valid–invalid bit in page

table entry is i  page fault

Department of CSE, Operating Systems BVCOE NEW DELHI

Page Table When Some Pages Are Not in Main Memory

Department of CSE, Operating Systems BVCOE NEW DELHI

Page Fault

 If there is a reference to a page, first reference to that page

will trap to operating system:
page fault
1. Operating system looks at another table to decide:
 Invalid reference  abort
 Just not in memory
2. Find free frame
3. Swap page into frame via scheduled disk operation
4. Reset tables to indicate page now in memory
Set validation bit = v
5. Restart the instruction that caused the page fault

Department of CSE, Operating Systems BVCOE NEW DELHI

Steps in Handling a Page Fault

Department of CSE, Operating Systems BVCOE NEW DELHI

Aspects of Demand Paging
 Extreme case – start process with no pages in memory
 OS sets instruction pointer to first instruction of process, non-
memory-resident -> page fault
 And for every other process pages on first access
 Pure demand paging
 Actually, a given instruction could access multiple pages ->
multiple page faults
 Consider fetch and decode of instruction which adds 2 numbers from
memory and stores result back to memory
 Pain decreased because of locality of reference
 Hardware support needed for demand paging
 Page table with valid / invalid bit
 Secondary memory (swap device with swap space)
 Instruction restart

Department of CSE, Operating Systems BVCOE NEW DELHI

Performance of Demand Paging
 Stages in Demand Paging (worse case)
1. Trap to the operating system
2. Save the user registers and process state
3. Determine that the interrupt was a page fault
4. Check that the page reference was legal and determine the location of the page on the disk
5. Issue a read from the disk to a free frame:
1. Wait in a queue for this device until the read request is serviced
2. Wait for the device seek and/or latency time
3. Begin the transfer of the page to a free frame
6. While waiting, allocate the CPU to some other user
7. Receive an interrupt from the disk I/O subsystem (I/O completed)
8. Save the registers and process state for the other user
9. Determine that the interrupt was from the disk
10. Correct the page table and other tables to show page is now in memory
11. Wait for the CPU to be allocated to this process again
12. Restore the user registers, process state, and new page table, and then resume the interrupted instruction

Department of CSE, Operating Systems BVCOE NEW DELHI

 Performance of Demand Paging (Cont.)
 Three major activities
 Service the interrupt – careful coding means just several hundred instructions
needed
 Read the page – lots of time
 Restart the process – again just a small amount of time
 Page Fault Rate 0  p  1
 if p = 0 no page faults
 if p = 1, every reference is a fault
 Effective Access Time (EAT)
EAT = (1 – p) x memory access
+ p (page fault overhead
+ swap page out
+ swap page in )

Department of CSE, Operating Systems BVCOE NEW DELHI

Demand Paging Example
 Memory access time = 200 nanoseconds
 Average page-fault service time = 8 milliseconds
 EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p x 200 + p x 8,000,000
= 200 + p x 7,999,800
 If one access out of 1,000 causes a page fault, then
EAT = 8.2 microseconds.
This is a slowdown by a factor of 40!!
 If want performance degradation < 10 percent
 220 > 200 + 7,999,800 x p
20 > 7,999,800 x p
 p < .0000025
 < one page fault in every 400,000 memory accesses

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 3

Department of CSE, Operating Systems BVCOE NEW DELHI

Page Replacement

 Prevent over-allocation of memory by

modifying page-fault service routine to include
page replacement
 Use modify (dirty) bit to reduce overhead of
page transfers – only modified pages are written
to disk
 Page replacement completes separation between
logical memory and physical memory – large
virtual memory can be provided on a smaller
physical memory

Department of CSE, Operating Systems BVCOE NEW DELHI

Need For Page Replacement

Department of CSE, Operating Systems BVCOE NEW DELHI

 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
- Write victim frame to disk if dirty

3. Bring the desired page into the (newly) free frame; update the page
and frame tables

4. Continue the process by restarting the instruction that caused the trap

Note now potentially 2 page transfers for page fault – increasing EAT

Department of CSE, Operating Systems BVCOE NEW DELHI

Page Replacement

Department of CSE, Operating Systems BVCOE NEW DELHI

 Page and Frame Replacement Algorithms

 Frame-allocation algorithm determines

 How many frames to give each process
 Which frames to replace
 Page-replacement algorithm
 Want lowest page-fault rate on both first access and re-access
 Evaluate algorithm by running it on a particular string of
memory references (reference string) and computing the
number of page faults on that string
 String is just page numbers, not full addresses
 Repeated access to the same page does not cause a page fault
 Results depend on number of frames available
 In all our examples, the reference string of referenced page
numbers is
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

Department of CSE, Operating Systems BVCOE NEW DELHI

Graph of Page Faults Versus The Number of Frames

Department of CSE, Operating Systems BVCOE NEW DELHI

First-In-First-Out (FIFO) Algorithm
 Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
 3 frames (3 pages can be in memory at a time per process)

15 page faults

 Can vary by reference string: consider

1,2,3,4,1,2,5,1,2,3,4,5
 Adding more frames can cause more page faults!
 Belady’s Anomaly

 How to track ages of pages?

 Just useofa CSE,
Department FIFOOperating
queue Systems BVCOE NEW DELHI
 FIFO Illustrating Belady’s Anomaly

Department of CSE, Operating Systems BVCOE NEW DELHI

LECTURE 4

Department of CSE, Operating Systems BVCOE NEW DELHI

Optimal Algorithm

 Replace page that will not be used for longest period of time
 9 is optimal for the example
 How do you know this?
 Can’t read the future
 Used for measuring how well your algorithm performs

Department of CSE, Operating Systems BVCOE NEW DELHI

 Least Recently Used (LRU) Algorithm
 Use past knowledge rather than future
 Replace page that has not been used in the most amount of time
 Associate time of last use with each page

 12 faults – better than FIFO but worse than OPT

 Generally good algorithm and frequently used
 But how to implement?

Department of CSE, Operating Systems BVCOE NEW DELHI

LRU Algorithm (Cont.)
 Counter implementation
 Every page entry has a counter; every time page is referenced
through this entry, copy the clock into the counter
 When a page needs to be changed, look at the counters to find
smallest value
 Search through table needed
 Stack implementation
 Keep a stack of page numbers in a double link form:
 Page referenced:
 move it to the top
 requires 6 pointers to be changed
 But each update more expensive
 No search for replacement
 LRU and OPT are cases of stack algorithms that don’t have
Belady’s Anomaly
Department of CSE, Operating Systems BVCOE NEW DELHI
 Use Of A Stack to Record Most Recent Page References

Department of CSE, Operating Systems BVCOE NEW DELHI

LRU Approximation Algorithms
 LRU needs special hardware and still slow
 Reference bit
 With each page associate a bit, initially = 0
 When page is referenced bit set to 1
 Replace any with reference bit = 0 (if one exists)
 We do not know the order, however
 Second-chance algorithm
 Generally FIFO, plus hardware-provided reference bit
 Clock replacement
 If page to be replaced has
 Reference bit = 0 -> replace it
 reference bit = 1 then:
 set reference bit 0, leave page in memory
 replace next page, subject to same rules

Department of CSE, Operating Systems BVCOE NEW DELHI

Second-Chance (clock) Page-Replacement Algorithm

Department of CSE, Operating Systems BVCOE NEW DELHI

 Enhanced Second-Chance Algorithm

 Improve algorithm by using reference bit and modify bit (if

available) in concert
 Take ordered pair (reference, modify)
1. (0, 0) neither recently used not modified – best page to
replace
2. (0, 1) not recently used but modified – not quite as good,
must write out before replacement
3. (1, 0) recently used but clean – probably will be used again
soon
4. (1, 1) recently used and modified – probably will be used
again soon and need to write out before replacement
 When page replacement called for, use the clock scheme
but use the four classes replace page in lowest non-empty
class
 Might need to search circular queue several times

Department of CSE, Operating Systems BVCOE NEW DELHI

Thrashing
 If a process does not have “enough” pages, the page-fault
rate is very high
 Page fault to get page
 Replace existing frame
 But quickly need replaced frame back
 This leads to:
 Low CPU utilization
 Operating system thinking that it needs to increase the degree of
multiprogramming
 Another process added to the system

 Thrashing  a process is busy swapping pages in and out

Department of CSE, Operating Systems BVCOE NEW DELHI

Thrashing (Cont.)

Department of CSE, Operating Systems BVCOE NEW DELHI

 Demand Paging and Thrashing
 Why does demand paging work?
Locality model
 Process migrates from one locality to another
 Localities may overlap

 Why does thrashing occur?

 size of locality > total memory size
 Limit effects by using local or priority page replacement

Department of CSE, Operating Systems BVCOE NEW DELHI

Page-Fault Frequency
 More direct approach than WSS
 Establish “acceptable” page-fault frequency (PFF) rate
and use local replacement policy
 If actual rate too low, process loses frame
 If actual rate too high, process gains frame

Department of CSE, Operating Systems BVCOE NEW DELHI

ONLINE RESOURCES:
https://www.youtube.com/watch?v=kQKpJ4bD8TA&list=PL3-
wYxbt4yCjpcfUDz-TgD_ainZ2K3MUZ&index=7
GATE QUESTIONS
 1. Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern,
increasing the number of page frames in main memory will
 a) Always decrease the number of page faults
 b) Always increase the number of page faults
 c) Some times increase the number of page faults
 d) Never affect the number of page faults
 Answer: (c)
 Which of the following statements is false?
 a) Virtual memory implements the translation of a program’s address space into physical memory address space
 b) Virtual memory allows each program to exceed the size of the primary memory
 c) Virtual memory increases the degree of multiprogramming
 d) Virtual memory reduces the context switching overhead
 Answer: (d)

Department of CSE, Operating Systems BVCOE NEW DELHI

GATE QUESTIONS
 3. Thrashing occurs when
(a)When a page fault occurs
(b) Processes on system frequently access pages not memory
(c) Processes on system are in running state
(d) Processes on system are in waiting state
Answer: (b)
 4. A computer system supports 32-bit virtual addresses as well as 32-bit physical addresses. Since
the virtual address space is of the same size as the physical address space, the operating system
designers decide to get rid of the virtual memory entirely. Which one of the following is true?
(a) Efficient implementation of multi-user support is no longer possible
(b) The processor cache organization can be made more efficient now
(c) Hardware support for memory management is no longer needed
(d) CPU scheduling can be made more efficient now

Answer: (c)

Department of CSE, Operating Systems BVCOE NEW DELHI