Transcript Module 7: Process Synchronization

Operating Systems
Lecture 36
Virtual Memory
Read Ch. 10.1 - 10.2
Operating System Concepts
7.1
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Segmentation vs. Paging
 Paging and Segmentation each have different
advantages and disadvantages.
 What are advantages and disadvantages of paging?
 No external fragmentation (advantage)
 There is internal fragmentation (disadvantage)
 Units of code and data are broken up into separate pages
(disadvantage)
 What are advantages and disadvantages of
segmentation?
 No internal fragmentation (advantage)
 There is external fragmentation (disadvantage)
 Keeps blocks of code or data as single units (advantage.
 Can get advantages of both systems by combining them.
Operating System Concepts
7.2
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Segmentation with Paging – MULTICS
 The MULTICS system solved problems of external
fragmentation and lengthy search times by paging the
segments.
 Solution differs from pure segmentation in that the
segment-table entry contains not the base address of the
segment, but rather the base address of a page table for
this segment.
 The offset for the segment is translated to a page number
and an offset for that page.
Operating System Concepts
7.3
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
MULTICS Address Translation Scheme
We will draw this diagram in class.
Operating System Concepts
7.4
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
MULTICS Address Translation Scheme
Operating System Concepts
7.5
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Limitations of Standard Memory
Management
 One goal of memory management is to keep as many
processes in memory as possible for multiprogramming.
 The previous examples require that the entire process be in
memory for execution.
 Therefore, the size of the program cannot exceed the size of
physical memory.
 In many cases, you don't need to have the entire program in
memory:
 Code to handle error conditions that rarely occur doesn't need to
be in main memory.
 Arrays, lists and tables are often allocated more memory than
needed.
 Virtual memory is a technique that allows the execution of
processes that are only partially in memory.
Operating System Concepts
7.6
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Benefits of 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.
 More programs can run at the same time (because each takes
up less space). This increases CPU utilization and throughput.
 Because you don't have to load the entire program into memory,
there is less I/O time needed for loading and swapping.
 Allows address spaces to be shared by several processes.
 Virtual memory can be implemented via:
 Demand paging
 Demand segmentation
Operating System Concepts
7.7
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Demand Paging
 Virtual memory is implemented by demand paging.
(Also can be implemented by demand segmentation,
which is slightly more complex).
 In demand paging, processes reside on secondary
storage (usually a hard disk).
 When a page is needed, a pager swaps it into
memory.
 The pager guesses which pages will be needed and
only swaps those in.
Operating System Concepts
7.8
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Transfer of a Paged Memory to Contiguous Disk Space
Operating System Concepts
7.9
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Valid-Invalid Bit
 We need to distinguish between pages in memory and pages on disk.
 With each page table entry a valid–invalid bit is associated
(1  in-memory, 0  not-in-memory)
Frame #
valid-invalid bit
1
1
1
1
0

0
0
page table
 During address translation, if valid–invalid bit in page table entry is 0, it
generates a page fault.
Operating System Concepts
7.10
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Page Table When Some Pages Are Not in Main Memory
Operating System Concepts
7.11
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Page Fault
 What happens when there is a page fault?
 An interrupt occurs (page fault). Control goes to the O.S.
 OS looks at another table (usually in the PCB) to determine




whether the memory access is valid.
 if the reference is invalid  abort.
 If the reference is valid, the page is not in memory.
Get empty frame (e.g. from free-frame list).
Swap page into frame.
Reset tables, validation bit = 1.
Restart instruction that was interrupted.
Operating System Concepts
7.12
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Steps in Handling a Page Fault
We will diagram this in class.
Operating System Concepts
7.13
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Steps in Handling a Page Fault
Operating System Concepts
7.14
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Potential Problem
 A page fault generates a lot of system activity and a read from
disk.
 If there are many page faults, efficiency decreases.
 Page faults are limited because programs tend to have locality of
reference.
 References are clustered together.
 Temporal Locality: recent references are likely to be referenced in
the near future. (e.g. loops, common procedures).
 Spatial locality: Nearby memory locations likely to be referenced.
(e.g. arrays, sequential code execution).
 Past study: 98% of process time spent in localities. 50% of page
faults occur during 2% of process time when changing localities.
 However, newer programming techniques decrease locality within
a process. E.g. multithreaded processes have abrupt changes in
page being referenced.
Operating System Concepts
7.15
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
What happens if there is no free frame?
 Page replacement – find some page in memory, but not
really in use, swap it out.
 performance – want an algorithm which will result in
minimum number of page faults.
 Same page may be brought into memory several times.
Operating System Concepts
7.16
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
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 x (page fault time)
page fault time = (page fault overhead
+ [swap page out ]
+ swap page in
+ restart overhead)
Operating System Concepts
7.17
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005
Demand Paging Example
 Memory access time = 1 nanosecond
 Swap Page Time = 25 msec
 If p = 0.001, what is the slow down in performance?
 What p would lead to a 10% slowdown in performance?
Operating System Concepts
7.18
Silberschatz, Galvin and Gagne 2002
Modified for CSCI 399, Royden, 2005