+
Memory Management
+ ◼ The main working principle of digital computer is Von-
Neumann stored program principle. First of all we have to keep
all the information in some storage, mainly known as main
memory, and CPU interacts with the main memory only.
Therefore, memory management is an important issue while
designing a computer system.
◼ On the other hand, everything cannot be implemented in
hardware, otherwise the cost of system will be very high.
Therefore some of the tasks are performed by software
program. Collection of such software programs are basically
known as operating systems. So operating system is viewed
as extended machine. Many more functions or instructions
are implemented through software routine. The operating
system is mainly memory resistant, i.e., the operating system
is loaded into main memory.
+◼ Due to that, the main memory of a computer is divided into two
parts. One part is reserved for operating system. The other part is
for user program. The program currently being executed by the
CPU is loaded into the user part of the memory.
◼ In a uni-programming system, the program currently being
executed is loaded into the user part of the memory.
◼ In a multiprogramming system, the user part of memory is
subdivided to accommodate multiple process. The task of
subdivision is carried out dynamically by operating system and is
known as memory management.
+
Figure : Five State process model
+
To utilize the idle time of CPU, we are shifting the paradigm from uni-
program environment to multi-program environment.
Since the size of main memory is fixed, it is possible to accommodate only
few process in the main memory. If all are waiting for I/O operation, then
again CPU remains idle.
To utilize the idle time of CPU, some of the process must be off loaded from
the memory and new process must be brought to this memory place. This is
known swapping.
+
What is swapping :
[Link] process waiting for some I/O to complete, must stored
back in disk.
2. New ready process is swapped into main memory as space
becomes available.
3. As process completes, it is moved out of main memory.
4. If none of the processes in memory are ready,
➢ Swapped out a block process to intermediate queue of
blocked process.
➢ Swapped in a ready process from the ready queue.
Partitioning
+ ◼ Splitting of memory into sections to allocate processes including operating system.
There are two scheme for partitioning :
◼ Fixed size partitions
◼ Variable size partitions
◼ The unused portion of memory in each partition is termed as hole.
◼ There are two simple ways to slightly remove the problem of memory wastage:
◼ Coalesce : Join the adjacent holes into one large hole , so that some process
can be accommodated into the hole.
◼ Compaction : From time to time go through memory and move all hole into one
free block of memory.
Effect of Dynamic Partitioning
Logical address
- expressed as a location relative to the
beginning of the program
Physical address
- an actual location in main memory
Base address
- current starting location of the process
+
◼ A process in memory consists of instruction plus data. The instruction
will contain address for memory locations of two types:
◼ Address of data item
◼ Address of instructions used for branching instructions
◼ These addresses will change each time a process is swapped in. To
solve this problem, a distinction is made between logical address and
physical address.
◼ Logical address is expressed as a location relative to the beginning of
the program. Instructions in the program contains only logical address.
▪ Physical address is an actual location in main memory.
◼ When the processor executes a process, it automatically converts from
logical to physical address by adding the current starting location of the
process, called it's base address to each logical address.
◼ Every time the process is swapped in to main memory, the base address
may be different depending on the allocation of memory to the process.
+ Paging
◼ Both unequal fixed size and variable size partitions are inefficient in the
use of memory. It has been observed that both schemes lead to memory
wastage. Therefore we are not using the memory efficiently.
◼ There is another scheme for use of memory which is known as paging.
◼ In this scheme,
◼ The memory is partitioned into equal fixed size chunks that are relatively
small. This chunk of memory is known as frames or page frames.
◼ Each process is also divided into small fixed chunks of same size. The
chunks of a program is known as pages.
◼ A page of a program could be assigned to available free frame.
◼ In this scheme, the wastage space in memory for a process is a fraction of a
page frame which corresponds to the last page of the program.
◼ At a given point of time some of the frames in memory are in use and some
are free. The list of free frame is maintained by the operating system.
+
Memory
Management
Paging
+
Logical and
Physical
Addresses
Paging
+
Paging Revisitted
◼ If a page is not in physical memory
◼ find the page on disk
◼ find a free frame
◼ bring the page into memory
◼ What if there is no free frame in memory?
+
Page Replacement
◼ Basic idea
◼ if there is a free page in memory, use it
◼ if not, select a victim frame
◼ write the victim out to disk
◼ read the desired page into the now free frame
◼ update page tables
◼ restart the process
+ Page Replacement
◼ Main objective of a good replacement algorithm is to achieve a
low page fault rate
◼ insure that heavily used pages stay in memory
◼ the replaced page should not be needed for some time
◼ Secondary objective is to reduce latency of a page fault
◼ efficient code
◼ replace pages that do not need to be written out
+
Reference String
◼ Reference string is the sequence of pages being referenced
◼ If user has the following sequence of addresses
◼ 123, 215, 600, 1234, 76
◼ If the page size is 100, then the reference string is
◼ 1, 2, 6, 12, 0
+
First-In, First-Out (FIFO)
◼ The oldest page in physical memory is the one selected for
replacement
◼ Very simple to implement
◼ keep a list
◼ victims are chosen from the tail
◼ new pages in are placed at the head
+
FIFO
•Consider the following reference string: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1
x x x x x x x x x
Compulsory Misses
0 4 4 4 4 2
2 4 2 0 0 3 0 1 0 2 0
1 1 1 3 3 3
6 6 6 6 1 1
•Fault Rate = 9 / 12 = 0.75
+
FIFO Issues
◼ Poor replacement policy
◼ Evicts the oldest page in the system
◼ usually a heavily used variable should be around for a long time
◼ FIFO replaces the oldest page - perhaps the one with the heavily
used variable
◼ FIFO does not consider page usage
+ Optimal Page Replacement
◼ Often called Balady’s Min
◼ Basic idea
◼ replace the page that will not be referenced for the longest time
◼ This gives the lowest possible fault rate
◼ Impossible to implement
◼ Does provide a good measure for other techniques
+
Optimal Page Replacement
•Consider the following reference string: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1
x x x x x x
Compulsory Misses
0 0 3
2 4 2 3 2
1 1 1
6 4 4
•Fault Rate = 6 / 12 = 0.50
•With the above reference string, this is the best we can hope to do
+
Least Recently Used (LRU)
◼ Basic idea
◼ replace the page in memory that has not been accessed for the
longest time
◼ Optimal policy looking back in time
◼ as opposed to forward in time
◼ fortunately, programs tend to follow similar behavior
+
LRU
•Consider the following reference string: 0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1
x x x x x x x x
Compulsory Misses
0 4 4 4 2
2 4 2 0 0 3 0 2 0
1 1 1 1 1
6 6 6 3 3
•Fault Rate = 8 / 12 = 0.67
+ LRU Issues
◼ How to keep track of last page access?
◼ requires special hardware support
◼ 2 major solutions
◼ counters
◼ hardware clock “ticks” on every memory reference
◼ the page referenced is marked with this “time”
◼ the page with the smallest “time” value is replaced
◼ stack
◼ keep a stack of references
◼ on every reference to a page, move it to top of stack
◼ page at bottom of stack is next one to be replaced
+
LRU Issues
◼ Both techniques just listed require additional hardware
◼ remember, memory reference are very common
◼ impractical to invoke software on every memory reference
◼ LRU is not used very often
◼ Instead, we will try to approximate LRU
+
Virtual Memory
◼ Demand Paging : Each page of a process is brought in only when it is
needed
◼ Principle of locality
◼ When working with a large process execution may be confined to a small section
of a program (subroutine)
◼ It is better use of memory to load in just a few pages
◼ If the program references data or branches to an instruction on a page not in
main memory, a page fault is triggered which tells the OS to bring in the desired
page
◼ Advantages:
◼ More processes can be maintained in memory
◼ Time is saved because unused pages are not swapped in and out of memory
◼ Disadvantages:
◼ When one page is brought in, another page must be thrown out (page
replacement)
◼ If a page is thrown out just before it is about to be used the OS will have to go get
the page again
◼ Thrashing
◼ When the processor spends most of its time swapping pages rather than
executing instructions
+
Inverted Page
Table Structure
Inverted Page
Table Structure
+
Operation of Paging
and Translation
Lookaside Buffer
(TLB)
+
Segmentation
◼ Usually visible to the
◼ Advantages:
programmer
◼ Simplifies the handling of
◼ Provided as a convenience for
growing data structures
organizing programs and data
and as a means for associating ◼ Allows programs to be
privilege and protection altered and recompiled
attributes with instructions and independently without
data requiring that an entire set
of programs be re-linked
◼ Allows the programmer to and re-loaded
view memory as consisting of ◼ Lends itself to sharing
multiple address spaces or among processes
segments
◼ Lends itself to protection