OS_Unit-4 Operating system class notes for the reference of the semister exams.pdf

Operating system

1. MEMORY MANAGEMENT
AND
VIRTUAL MEMORY
MANAGEMENT
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of Information
Technology

2. Memory Management






Introduction
Swapping
Contiguous Memory allocation
Paging
Structure of the page table
Segmentation

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

3. Introduction





Basic Hardware
Address Binding
Logical vs Physical Address Space
Dynamic Loading
Dynamic Linking & Shared Libraries

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

4. Basic Hardware






Main memory and registers are only storage that
CPU can access directly.
Program must be brought (from disk) into
memory and placed within a process for it to be
run.
Register access in one CPU clock (or less).
Main memory can take many cycles.
Cache sits between main memory and CPU registers.
Protection of memory required to ensure correct
operation.

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

5. Base and Limit Registers
◦A pair of base and limit registers define the logical address space

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

6. Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

7. Address Binding









Symbolic names  Logical names  Physical names
Symbolic Names: known in a context or path
file names, program names, printer/device names, user
names
Logical Names: used to label a specific entity
job number, major/minor device numbers, process id
(pid), uid, gid..
Physical Names: address of entity
address on disk or memory
entry point or variable address
PCB address

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

8. Address Binding




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. Need hardware support
for address maps (e.g., base and limit registers)
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

9. Multi Step Processing of a User Program
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

10. Binding Time Tradeoffs












Early binding
compiler - produces efficient code
allows checking to be done early
allows estimates of running time and space
Delayed binding
Linker, loader
produces efficient code, allows separate compilation
portability and sharing of object code
Late binding
VM, dynamic linking/loading, overlaying, interpreting
code less efficient, checks done at runtime
flexible, allows dynamic reconfiguration

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

11. Logical vs. Physical Address Space




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
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

12. Memory Management Unit (MMU)



Hardware device that maps virtual to physical address

In MMU scheme, 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

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

13. Dynamic Relocation Using a Relocation
Register
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

14. Dynamic Loading





Routine is not loaded until it is called

Better memory-space utilization; unused routine is never loaded

Useful when large amounts of code are needed to handle infrequently
occurring cases

No special support from the operating system is required implemented
through program design
https://www.youtube.com/watch?v=lWVQsld8hMI

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

15. 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 needed to check if routine is in processes’ memory
address

Dynamic linking is particularly useful for libraries

System also known as shared libraries
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

16. Swapping
A process must be in memory to be executed.
A process can be swapped temporarily out of memory to a backing store.
For example, assume a multiprogramming environment with a round-robin
CPU-scheduling algorithm.
A variant of this swapping policy is used for priority based scheduling
algorithms.
This variant of swapping is sometimes called roll out, roll in.

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

17. Swapping Cont..
Swapping requires a backing store.
Whenever the CPU scheduler decides to execute a process, it calls the
dispatcher.
The dispatcher checks to see whether the next process in the queue is in
memory.
If it is not the dispatcher swaps out a process currently in memory and
swaps in the desired process.
It then reload registers and transfers control to the selected process.

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

18. Swapping Cont..
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

19. Contiguous Memory Allocation
Introduction
Memory Mapping and Protection
Memory Allocation
Fragmentation
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

20. Contiguous Memory Allocation
Contiguous: sharing a common border or together in sequence.
The memory is usually divided into two partitions: one for the resident
operating system and one for the user processes.
We can place the operating system in either low memory or high memory.

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

21. Memory Mapping and Protection
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

22. Memory Mapping and Protection
When the CPU scheduler selects a process for execution, the dispatcher
loads the relocation and limit registers with the correct values
Because every address generated by the CPU is checked against these
registers, we can protect both the operating system and the other users'
programs and data.

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

23. Memory Allocation
Variable Partition Scheme(Dynamic Partitioning):
Partitions are of variable length and number
Each process is allocated exactly as much memory as it
requires
Hole – block of available memory; holes of various size
are scattered throughout memory
Eventually holes are formed in main memory. This is
called external fragmentation
Operating system maintains information about:
a) allocated partitions b) free partitions (hole)

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

24. Memory Allocation Cont..
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

25. Memory Allocation Cont..
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

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

26. Memory Allocation Cont..
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

27. Fragmentation
◦As processes are loaded and removed from memory, the free memory
space is broken into little pieces. It happens after sometimes that
processes cannot be allocated to memory blocks considering their small size
and memory blocks remains unused. This problem is known as
Fragmentation.
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

28. 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.
Reduce external fragmentation by compaction
Shuffle memory contents to place all free memory together in one large
block

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

29. Paging
Introduction
Hardware Support
Protection
Shared Pages

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

30. Introduction
Paging is a memory-management scheme
that permits the physical address space of
a process to be noncontiguous.
The basic method for paging involves
breaking physical memory into fixed-sized
blocks called frames and breaking logical
memory into blocks of the same size called
pages.

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

31. Cont…
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

32. Cont…
Every address generated by the CPU is divided
into two parts: a page number (p) and a page
offset (d).
The page number is used as an index into a page
table.
The page table contains the base address of each
page in physical memory.
This base address is combined with the page
offset to define the physical memory address

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

33. Cont…
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

34. Free Frames
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

35. Hardware Support





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)

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

36. Hardware Support Cont…
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

37. Hardware Support Cont…
The percentage of times that a particular page number is found in the
TLB is called the hit ratio.
An 80-percent hit ratio means that we find the desired page number in
the TLB 80 percent of the time.
If it takes 20 nanoseconds to search the TLB and 100 nanoseconds to
access memory, then a mapped-memory access takes 120 nanoseconds
when the page number is in the TLB.

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

38. Hardware Support Cont…
If we fail to find the page number in the TLB (20 nanoseconds), then we
must first access memory for the page table and frame number (100
nanoseconds) and then access the desired byte in memory (100
nanoseconds), for a total of 220 nanoseconds.
To find the effective memory-access time, we weight each case by its
probability:

effective access time = 0.80 x 120 + 0.20 x 220
= 140 nanoseconds.

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

39. Protection
Memory protection implemented by associating
protection bit with each frame

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

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

40. Protection Cont...
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

41. Shared Pages
Shared code
One copy of read-only (reentrant) code shared among processes (i.e., text
editors, compilers, window systems).

Private code and data
Each process keeps a separate copy of the code and data

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

42. Shared Pages Cont…
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

43. Structure of the Page Table
◦
◦
◦
Hierarchical Paging
Hashed Page Tables
Inverted Page Tables
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

44. Hierarchical Paging



Break up the logical address space into multiple page tables

A simple technique is a two-level page table

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

45. Two-Level Page Table Scheme
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

46. 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 pii is an index into the outer page table, and p2 is the
displacement within the page of the outer page table

page number page offset
p
i
p
2 d
12 10 10
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

47. Address Translation Scheme
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

48. Three-Level Paging Scheme
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

49. 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

Virtual page numbers are compared in this chain
searching for a match
If a match is found, the corresponding physical
frame is extracted

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

50. Hashed Page Tables Cont…
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

51. Inverted Page Tables




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

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

52. Inverted Page Table Architecture
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

53. 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
--method
--object
--local variables, global
variables
--common block
--stack
--symbol table
--arrays
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

54. User’s View of a Program
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

55. Logical View of Segmentation
1
3
2
4
1
4
2
3
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

56. 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;
segment number s is legal if s < STLR
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

57. Segmentation Architecture







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

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

58. Segmentation Hardware
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

59. Example of Segmentation
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

60. Virtual Memory Management





Virtual Memory
Demand Paging
Page Replacement Algorithms
Allocation of Frames
Thrashing

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

61. Virtual Memory







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

Virtual memory can be implemented via:
Demand paging
Demand segmentation
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

62. Virtual Memory
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

63. Virtual Memory
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

64. Virtual Memory
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

65. Demand Paging


Basic Concepts
Performance of Demand Paging
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

66. Basic Concepts







Bring a page into memory only when it is needed
Less I/O needed
Less memory needed
Faster response
More users

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

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

67. Demand Paging
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

68. Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

69. Performance of Demand Paging







If there is a reference to a page, first reference to that page will trap to
operating system:
page fault

Operating system looks at another table to decide:
Invalid reference  abort
Get empty frame
Swap page into frame
Reset tables
Set validation bit = v
Restart the instruction that caused the page fault

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

70. Performance of Demand Paging
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

71. Performance of Demand Paging
Page Fault Rate 0  p  1.0
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
+ restart overhead)

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

72. Allocation of Frames
◦
◦
◦
Introduction
Equal vs. Proportional Allocation
Global vs. Local Replacement
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

73. Introduction










Each process needs minimum number of frames
Example: IBM 370 – 6 pages to handle SS MOVE
instruction:
instruction is 6 bytes, might span 2
pages
2 pages to handle from
2 pages to handle to
Maximum of course is total frames in the system
Two major allocation schemes
Fixed allocation
Proportional allocation

Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

74. Equal vs. Proportional Allocation



Equal Allocation – For example, if there are 100
frames (after allocating frames for the OS) and 5
processes, give each process 20 frames

Proportional Allocation – Allocate according to the
size of process


Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

75. Global vs. Local Replacement





Global replacement – process selects a replacement frame from the set of
all frames; one process can take a frame from another
But then process execution time can vary greatly
But greater throughput so more common

Local replacement – each process selects from only its own set of allocated
frames
More consistent per-process performance
But possibly underutilized memory
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

76. Thrashing






A process is thrashing if it is spending more time paging than executing
If the process does not have the minimum number of frames it will quickly
page-fault.
At this point, it must replace some page.
However, since all its pages are in active use, it must replace a page that will
be needed again right away.
Consequently, it quickly faults again, and again, and again, replacing pages
that it must bring back in immediately.
This high paging activity is called thrashing.


Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

77. Thrashing
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

78. Page Fault Frequency







Thrashing has a high page-fault rate.
When the page fault rate is too high, we know that the process needs
more frames.
Conversely, if the page-fault rate is too low, then the process may have
too many frames.
We can establish upper and lower bounds on the desired page-fault rate.
If the actual page-fault rate exceeds the upper limit, we allocate the
process another frame;
if the page-fault rate falls below the lower limit, we remove a frame
from the process.
Thus, we can directly measure and control the page-fault rate to prevent
thrashing
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology

79. Cont..
Mrs Venkata Naga Rani Bandaru, Assistant Professor, Department of
Information Technology