Transcript CS345 02 - Computer Systems

Unit 5-6
Virtual Memory
Dr Damitha Kar unar atna
Univer sity of Colombo school of computing
Operating Systems
1
Virtual memory
• Is it necessary to load an entire program to the
memory for execution?
• If the size of the program is larger than the
available memory how can it be execute?
Operating Systems
2
Virtual Memory - Goals
• Allow applications larger than physical memory to execute.
• Run partially loaded programs – Entire program need not to be
in memory all the time.
• Multiprogramming: Many programs simultaneously reside in
memory.
• Allow re-locatable programs – anywhere, anytime
• Application Portability:
• Applications should not have to manage memory resources
• Write machine independent code – program should not depend on
memory architecture.
• Permit sharing of memory segments or regions.
• For example, read-only code segments should be shared between
program instances.
Operating Systems
3
Virtual Memory
Operating Systems
4
Virtual memory
Virtual memory is partitioned in to equal size pages.
Main memory is also partitions into equal size page frames.
Size of a page = size of a page frame
Programs are also partitioned into pages at the time of
loading.
Operating Systems
5
Logical View
Operating Systems
6
Virtual Memory
• Process runs on a virtual machine as defined by
the underlying hardware.
• Focus is on Hardware support for a virtual address
space
• virtual addresses independent of physical
memory
• Key hardware component is the Memory
Management Unit (MMU)
• address translation: virtual to physical memory
• ensures virtual address space protection
Operating Systems
7
Virtual Memory
Page table
Keep track of
whether a
page is in a
physical page
frame or not.
Page table may maintain a bit in each entry to indicate whether the
page is in the memory or not.
Operating Systems
8
Handling missing pages
When a page fault occurs, the Operating System:
• moves the current process to the blocked/waiting state
(since it must wait for a page to be made resident).
• finds an empty frame or, if necessary, makes a frame empty
in main memory by swapping out a page in the main
memory.
• determines the location of the requested page on the
paging device.
• schedules a disk read operation to load the page into the
selected main memory frame (via a “pagein”)
• later handles page fetch completion (which is recognized
via an I/O completion interrupt) and then moves the
blocked process back to the ready state.
Operating Systems
9
Using Virtual Memory
http://www.tutorialspoint.com/operating_system/os_virtual_memory.htm
Operating Systems
10
Virtual Addresses
Operating Systems
11
Virtual address to Real Address
Operating Systems
12
Paging Example
Virtual Memory
Page 0
A
B
C
d
Physical
Memory
Page table
row 0
1
2
3
Page frame 0
1
A
B
C
D
0
C
C
E
f
C
C
E
f
row n
Page frame 3
4
Page n
2
CPU
Operating Systems
4
MMU
0
4
13
Using Virtual Memory
• Check an internal table for this process, to determine whether the
reference was a valid or it was an invalid memory access.
• If the reference was invalid, terminate the process. If it was valid, but
page have not yet brought in, page in the latter.
• Find a free frame.
• Schedule a disk operation to read the desired page into the newly
allocated frame.
• When the disk read is complete, modify the internal table kept with
the process and the page table to indicate that the page is now in
memory.
• Restart the instruction that was interrupted by the illegal address
trap. The process can now access the page as though it had always
been in memory. Therefore, the operating system reads the desired
page into memory and restarts the process as though the page had
always been in memory.
Operating Systems
14
Virtual Memory - Disadvantages
Space: Translation tables and other data used by VM system
reduce available memory to programs
Time: Address translation time is added to the cost
(execution time) of each instruction.
Overhead: Memory management operations have been
measured to consume up to 10% of the CPU time on a busy
system.
Efficiency: Allocating memory in pages may result in
fragmentation
Operating Systems
15
Virtual Memory
Allows programmers to address memory from a logical point of view
◦ Another layer of indirection
Allow the illusion of operating with a larger memory space than what is
available in reality
◦ By storing some of the information on the file system
Operating Systems
16
Device Drivers
Device driver is a software.
The computer communicates with
peripheral devices through device
drivers.
A driver provides a software
interface to hardware devices,
enabling operating systems and
other computer programs to access
hardware functions without
knowing the precise hardware
details.
Operating Systems
Device drivers depends on
both the hardware and the
operating system loaded in to
the computer
17
Secondary Storage Management
Secondary storage is the non-volatile repository for both user and
system data and programs.
Secondary storage is typically used to store
◦
◦
◦
◦
Source program
Executable programs
Data for the program
Temporaty data
Operating Systems
18
Files
A file is a named collection of related information, usually a sequence of
bytes
A file can be viewed in two different ways.
• Logical (programmer’s) view: how the users see the file.
◦ Liners collection of records.
◦ Image File – rows of intensity values
◦ Linear sequence of bytes.
• Physical (operating system) view: how the file is stored on secondary
storage.
◦ Many possibilities, not necessarily contiguous
Operating Systems
19
File Attributes
Each file has an associated collection of
information(attributes)
•
•
•
•
•
•
file name
Owner
type (e.g., source, data, executable)
location(s) on the secondary storage.
organization (e.g. sequential, indexed, random)
access permissions – who is permitted to
read/write/delete data in the file.
• time and date of creation, modification, last access
• file size
Operating Systems
20
File Types
File can be classified into various types based on the
content.
•
•
•
•
•
•
•
Executable
Text
Source
Library
Compressed
Word Processor
Spread sheet.
One of the possible implementation technique of file
type is to include the type as an extension to the file
name.
Operating Systems
21
File Access Methods
File access methods describe how the data stored in a file can be
accessed
• Sequential: access in order, one record after another.
• Direct (random): access in any order, skipping over uninteresting records
• Indexed : access in any order, but based on key value(s)
Operating Systems
22
Directories
Directories are used to organize file to logical
categories.
A directory is a file that can be searched for
information about other files.
◦ Entries in the directory file are created, deleted and
modified when the files they describe are create, deleted
and modified.
Operating Systems
23
Unix Directory structure
Operating Systems
24
File allocation
Common file allocation techniques
◦ Contiguous
◦ Linked
◦ Indexed
Typically the allocation techniques allocate storage space on
the basis of fixed size addressable units.
Operating Systems
25
File allocation - Contiguous
Allocate disk space as a collection
of adjacent/contiguous blocks.
This technique needs to keep
track of unused disk space.
Directory
File Name
Start Block No No of Blocks
file1
00
03
file2
12
06
file3
20
11
Operating Systems
26
File allocation - Contiguous
Advantages:
• Simple easy access.
• Easy Access.
Disadvantage
• File size is not known at the time
of creation.
• Extending file size is difficult
• External fragmentation
Operating Systems
27
File allocation - Linked
Inside each block a link is
maintained to point to the
next block of the file
Directory
File Name
Start Block No No of Blocks
file1
00
Operating Systems
03
28
File allocation - Linked
Advantages:
• No external fragmentation.
• Files can grow easily.
Disadvantage
• Many seek are required to access
file data
Example :
MSDOS FAT file system
Operating Systems
29
File allocation - Indexed
Creates a table of
pointers(index) at the time of
the file creation. This table is
modified as new blocks are
allocated for the file or
removed from the file.
The index table is also saved
in a block/s.
Example : UNIX file system
Operating Systems
30
Formatting a storage device
Hard disks, need to be formatted before using.
Formatting a disk configures the disk with a file
system so that OS can store information on the
disk.
Operating Systems
31
File Allocation Table(FAT)
 FAT is the file systems used by Windows NT operating
system.
 FAT uses a file allocation table (FAT) to keep track of files in
the storage devices
 FAT and the root directory reside at a fixed location of the
volume so that the system's boot files can be correctly
located.
 To protect a volume, two copies of the FAT are kept.
Operating Systems
32
New Technology File System
NTFS (New Technology File System) is a proprietary file system
developed by Microsoft. This is improvement of FAT. This improvements
includes
 The capability to recover from some disk-related errors
automatically, which FAT cannot.
 Improved support for larger hard disks.
 Better security because you can use permissions and encryption to
restrict access to specific files to approved users.
NTFS is a recoverable file system which keeps track of transactions
against the file system in a log.
http://windows.microsoft.com/en-us/windows-vista/comparing-ntfs-and-fat-file-systems
Operating Systems
33
Memory Fragmentation
Fragmentation is the unintentional division of
memory into many small free areas that cannot
be used effectively.
• 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 in memory internal to a
partition, hence cannot be used for any other
process.
Operating Systems
34
Memory Fragmentation ….
Compaction is a technique that can be used
to deal with (external) fragmentation by moving
partitions to bring many small free areas
together to form a single large free area.
Operating Systems
35
References
Operating System Concepts by Avi Silberschat, Peter Baer Galvin and
Greg Gagne
◦ http://codex.cs.yale.edu/avi/os-book/OS8/os8c/slide-dir/
Operating Systems
36