Transcript Lect#36

Operating Systems
•Virtual Memory
•Thrashing
•Single-User Contiguous Scheme
•Fixed Partitions
•Dynamic Partitions
Understanding Operating Systems
1
Virtual Memory
 Programs are often too large to fit into the primary memory.
 To solve this problem, computer scientist came up with the idea of
virtual memory – where part of the storage on the secondary memory
(hard disk) is considered as part of the main memory (RAM).
 The actual memory required by a program -- logical memory, is
considered to be independent of the physical memory of the computer.
 The following explains how OS implements this idea:
 Let the physical memory be of size M.
 M is partitioned into r equal parts each of size M/r.
 Each of these partitions is called a page frame.
 Let the logical Memory be L.
 L is portioned into p equal parts each of size s=M/r.
 Each of these partitions is called a page.
 Notice that page frames and pages must be of the same size.
 Parts of the pages that cannot fit into the physical memory are placed on the
virtual memory.
 As the program executes, and more page frames become available, the pages
are swapped into page frames. This process is called paging.
Understanding Operating Systems
2
Example
Suppose the physical memory of a computer is 256KB and is partitioned
into 8 page frames. If the logical memory required by a program is
5MB, what is the number of pages needed in the virtual memory.
Solution:
page size, s = M/p = 256KB/8 = 32KB
therefore, number of pages, p = L/s
= 5MB / 32KB
= 5 * 2^10KB / 2^5KB
= 5 * 2^5
= 5 * 32
= 160.
Thus, 160 pages are needed in the virtual memory
Understanding Operating Systems
3
Page Table
 When a program is using virtual memory, the system keep tracks of
which part is in memory and which part is in virtual memory through
the page table.
 The table consists of at least three columns as shown below:
frame reference page address
page frame
address
1
0
1
0 reference is a single bit flag indicating whether the page is in memory (1) on
 The frame
in virtual memory (0). The page address is the location of the page if it is on the disk
and the page frame address is the location of the page if it has been transferred to
memory.
 At least one page is loaded into a page frame before the execution begins.
 When the program demands access to the address of an instruction, the system first
checks if it is in a page frame, if it is not, an OS interrupt called page fault occurs. This
forces the OS to search for the next logical page and put it into a page frame.
Understanding Operating Systems
4
Thrashing
 Virtual memory presents the problem of thrashing – high paging
activity, which reduces the speed of a program.
 If the size of a page is small, too many page faults can result which
cause thrashing.
 On the other hand, if the size of a page is too big, it can result in waste
of memory. For example, if a page is 32KB, a 3KB program has to be
stored in 32KB, wasting 29KB. However, if the size of a page is 4KB,
then only 1KB is wasted.
 Designers of OS often have to tradeoff between these two factors.
 The greatest problem of thrashing is under-use of the CPU as it
remains idle waiting for pages to be transferred into page frames.
Understanding Operating Systems
5
Single-User Contiguous Scheme
• Each program loaded in its entirety into memory and
allocated as much contiguous memory space as needed.
• If program was too large -- it couldn’t be executed.
• Minimal amount of work done by Memory Manager.
• Hardware needed : 1) register to store base address;
2) accumulator to track size of program as it is loaded into
memory.
Understanding Operating Systems
6
Fixed (Static) Partitions
• Attempt at multiprogramming using fixed partitions
– one partition for each job
– size of partition designated by reconfiguring the system
– partitions can’t be too small or too large.
• Critical to protect job’s memory space.
• Entire program stored contiguously in memory during
entire execution.
• Internal fragmentation is a problem.
Understanding Operating Systems
7
Main memory use during fixed
partition allocation of Job 3 must
wait.
Job List :
J1
30K
J2
50K
J3
30K
J4
25K
Original State
100K
After Job Entry
Job 1 (30K)
Partition 1
Partition 1
Partition 2
25K
Partition 3
25K
50K
Partition 4
Understanding Operating Systems
Job 4 (25K)
Partition 2
Partition 3
Job 2 (50K)
Partition 4
8
Dynamic Partitions
• Available memory kept in contiguous blocks and jobs
given only as much memory as they request when loaded.
• Improves memory use over fixed partitions.
• Performance deteriorates as new jobs enter the system
– fragments of free memory are created between blocks
of allocated memory (external fragmentation).
Understanding Operating Systems
9
Dynamic Partitioning of Main Memory &
Fragmentation
Understanding Operating Systems
10
Dynamic Partition Allocation Schemes
• First-fit: Allocate the first partition that is big enough.
– Keep free/busy lists organized by memory location (loworder to high-order).
– Faster in making the allocation.
• Best-fit: Allocate the smallest partition that is big enough
– Keep free/busy lists ordered by size (smallest to largest).
– Produces the smallest leftover partition.
– Makes best use of memory.
Understanding Operating Systems
11