Transcript Workshop 3 Slides - dhdurso.org index to available resources

Workshop 3: Agenda
•
•
•
•
•
•
•
•
Homework review
Study group presentations
Lecture – memory concepts
Group activity – memory concepts (45 m)
Lecture – virtual memory
Group activity – memory management algorithms
Midterm review
Summary and next week preview
Operating System Concepts
8.1
Silberschatz and Galvin1999
Workshop 3: Homework
•
•
Chapter 8
– 8.1
– 8.2
Chapter 9
– 9.1.
– 9.7
Operating System Concepts
8.2
Silberschatz and Galvin1999
Workshop 3: Study Group Project
How O/S
manages main &
secondary
memory
Algorithm
data structure
etc.
3 - 5 page paper
Presentation
Operating System Concepts
5 - 10 minutes
1 person can
represent group
8.3
Silberschatz and Galvin1999
Module 8: Memory Management
•
•
•
•
•
•
•
Background
Logical versus Physical Address Space
Swapping
Contiguous Allocation
Paging
(Segmentation)
(Segmentation with Paging)
Operating System Concepts
8.4
Silberschatz and Galvin1999
Background
•
•
•
Program must be brought into memory and placed within a
process for it to be executed.
Input queue – collection of processes on the disk that are waiting
to be brought into memory for execution.
User programs go through several steps before being executed.
Operating System Concepts
8.5
Silberschatz and Galvin1999
Instructions and Data Memory Addresses
Can be set up at three different points.
•
•
•
•
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).
See page 241 in textbook
Operating System Concepts
8.6
Silberschatz and Galvin1999
Address Binding
•
•
•
Dynamic loading
Dynamic linking (ex: DLL)
Overlays (rarely used today)
Operating System Concepts
8.7
Silberschatz and Galvin1999
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.
Operating System Concepts
8.8
Silberschatz and Galvin1999
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.
Operating System Concepts
8.9
Silberschatz and Galvin1999
Swapping
•
A process can be swapped temporarily out of memory to a
backing store, and then brought back into memory for continued
execution.
•
Backing store – fast disk large enough to accommodate copies of
all memory images for all users; must provide direct access to
these memory images.
•
Roll out, roll in – used for priority-based scheduling algorithms;
lower-priority process is swapped out so higher-priority process
can be loaded and executed.
•
•
Major part of swap time is transfer time; total transfer time is
directly proportional to the amount of memory swapped.
Modified versions of swapping are found on many systems, i.e.,
UNIX and Microsoft Windows.
Operating System Concepts
8.10
Silberschatz and Galvin1999
Schematic View of Swapping
Operating System Concepts
8.11
Silberschatz and Galvin1999
Contiguous Memory Allocation
•
Multiple-partition allocation
– Hole – block of available memory; holes of various size are
scattered throughout memory.
– When a process arrives, it is allocated memory from a hole
large enough to accommodate it.
– Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
OS
OS
OS
OS
process 5
process 5
process 5
process 5
process 9
process 9
process 8
process 2
Operating System Concepts
process 10
process 2
process 2
8.12
process 2
Silberschatz and Galvin1999
Dynamic Storage-Allocation Problem
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.
Operating System Concepts
8.13
Silberschatz and Galvin1999
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.
Operating System Concepts
8.14
Silberschatz and Galvin1999
Paging
•
•
•
•
•
•
•
Logical address space of a process can be noncontiguous;
process is allocated physical memory whenever the latter is
available.
Divide physical memory into fixed-sized blocks called frames (size
is power of 2, between 512 bytes and 8192 bytes).
Divide logical memory into blocks of same size called pages.
Keep track of all free frames.
To run a program of size n pages, need to find n free frames and
load program.
Set up a page table to translate logical to physical addresses.
Internal fragmentation.
Operating System Concepts
8.15
Silberschatz and Galvin1999
Address Translation Scheme
•
Address generated by CPU is divided into:
– Page number (p) – used as an index into a page table which
contains base address of each page in physical memory.
– Page offset (d) – combined with base address to define the
physical memory address that is sent to the memory unit.
Operating System Concepts
8.16
Silberschatz and Galvin1999
Address Translation Architecture
Operating System Concepts
8.17
Silberschatz and Galvin1999
Paging Example
Operating System Concepts
8.18
Silberschatz and Galvin1999
Implementation of Page Table
•
•
•
•
•
•
Page table is kept in main memory.
Page-table base register (PTBR) points to the page table.
Page-table length register (PRLR) 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 registers or
translation look-aside buffers (TLBs)
Effective access time depends on hit ratio
Operating System Concepts
8.19
Silberschatz and Galvin1999
Memory 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.
Operating System Concepts
8.20
Silberschatz and Galvin1999
Shared Pages
•
•
Shared code
– One copy of read-only (reentrant) code shared among
processes (i.e., text editors, compilers, window systems).
– Shared code must appear in same location in the logical
address space of all processes.
Private code and data
– Each process keeps a separate copy of the code and data.
– The pages for the private code and data can appear
anywhere in the logical address space.
Operating System Concepts
8.21
Silberschatz and Galvin1999
Segmentation
1
4
1
2
3
2
4
3
user space
Operating System Concepts
physical memory space
8.22
Silberschatz and Galvin1999
Segmentation Architecture
•
Logical address consists of a two part:
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;
Operating System Concepts
8.23
Silberschatz and Galvin1999
Segmentation Architecture (Cont.)
•
•
•
Relocation.
– dynamic
– by segment table
Sharing.
– shared segments
– same segment number
Allocation.
– first fit/best fit
– external fragmentation
Operating System Concepts
8.24
Silberschatz and Galvin1999
Segmentation Architecture (Cont.)
•
•
•
•
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.
Segments can vary in length
A segmentation example is shown in the following diagram
Operating System Concepts
8.25
Silberschatz and Galvin1999
Sharing of segments
Operating System Concepts
8.26
Silberschatz and Galvin1999
Segmentation with Paging – Intel 386
•
As shown in the following diagram, the Intel 386 uses
segmentation with paging for memory management with a twolevel paging scheme.
Operating System Concepts
8.27
Silberschatz and Galvin1999
Intel 30386 address translation
Operating System Concepts
8.28
Silberschatz and Galvin1999
Comparing Memory-Management Strategies
•
•
•
•
•
•
•
Hardware support
Performance
Fragmentation
Relocation
Swapping
Sharing
Protection
Operating System Concepts
8.29
Silberschatz and Galvin1999
Memory Concepts: Group Activity
Assign memory
management
technique(s)
Present results
Operating System Concepts
Address binding
Dynamic linking
Overlays
Swapping
Contiguous
Partition
Paging
5 - 10 minutes
1 presenter is fine
8.30
Silberschatz and Galvin1999
Module 9: Virtual Memory
•
•
•
•
•
•
•
•
•
Background
Demand Paging
Performance of Demand Paging
Page Replacement
Page-Replacement Algorithms
Allocation of Frames
Thrashing
Other Considerations
Demand Segmenation
Operating System Concepts
8.31
Silberschatz and Galvin1999
Background
•
•
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.
– Need to allow pages to be swapped in and out.
Virtual memory can be implemented via:
– Demand paging
– Demand segmentation
Operating System Concepts
8.32
Silberschatz and Galvin1999
Demand Paging
•
•
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
Operating System Concepts
8.33
Silberschatz and Galvin1999
Valid-Invalid Bit
•
•
•
With each page table entry a valid–invalid bit is associated
(1  in-memory, 0  not-in-memory)
Initially valid–invalid but is set to 0 on all entries.
Example of a page table snapshot.
Frame #
valid-invalid bit
1
1
1
1
0

•
During address translation, if valid–invalid bit in page table entry is 0 
0
page fault.
0
page table
Operating System Concepts
8.34
Silberschatz and Galvin1999
Page Fault
•
•
•
•
•
•
If there is ever a reference to a page, first reference will trap to
OS  page fault
OS looks at another table to decide:
– Invalid reference  abort.
– Just not in memory.
Get empty frame.
Swap page into frame.
Reset tables, validation bit = 1.
Restart instruction
Operating System Concepts
8.35
Silberschatz and Galvin1999
What happens if there is no free frame?
•
Page replacement – find some page in memory, but not really in
use, swap it out.
– algorithm
– performance – want an method which will result in minimum
number of page faults.
Operating System Concepts
8.36
Silberschatz and Galvin1999
Page Replacement
•
•
•
Prevent over-allocation of memory by modifying page-fault service
routine to include page replacement.
Use modify (dirty) bit to reduce overhead of page transfers – only
modified pages are written to disk.
Page replacement completes separation between logical memory
and physical memory – large virtual memory can be provided on a
smaller physical memory.
Operating System Concepts
8.37
Silberschatz and Galvin1999
Page-Replacement Algorithms
•
•
•
Want lowest page-fault rate.
Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page
faults on that string.
In all our examples, the reference string is
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
Operating System Concepts
8.38
Silberschatz and Galvin1999
First-In-First-Out (FIFO) Algorithm
•
•
•
•
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
3 frames (3 pages can be in memory at a time per process)
Use queue or timestamp
1
1
4
5
2
2
1
3
3
3
2
4
1
1
5
4
2
2
1
5
3
3
2
4
4
3
9 page faults
4 frames
Operating System Concepts
8.39
10 page faults
Silberschatz and Galvin1999
Optimal Algorithm
•
•
Replace page that will not be used for longest period of time.
4 frames example
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
4
2
6 page faults
3
4
•
•
5
How do you know this?
Used for measuring how well your algorithm performs.
Operating System Concepts
8.40
Silberschatz and Galvin1999
Least Recently Used (LRU) Algorithm
•
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
5
2
•
•
Queue, timestamp
3
5
4
3
4
Counter implementation
– Every page entry has a counter; every time page is
referenced through this entry, copy the clock into the counter.
– When a page needs to be changed, look at the counters to
determine which are to change.
Operating System Concepts
8.41
Silberschatz and Galvin1999
LRU Algorithm (Cont.)
•
Stack implementation – keep a stack of page numbers in a double
link form:
– Page referenced:
 move it to the top
 requires 6 pointers to be changed
– No search for replacement
Operating System Concepts
8.42
Silberschatz and Galvin1999
Counting Algorithms
•
•
•
Keep a counter of the number of references that have been made
to each page.
LFU Algorithm: replaces page with smallest count.
MFU Algorithm: based on the argument that the page with the
smallest count was probably just brought in and has yet to be
used.
Operating System Concepts
8.43
Silberschatz and Galvin1999
Allocation of Frames
•
•
Each process needs minimum number of pages.
Two major allocation schemes.
– fixed allocation
 Equal allocation – e.g., if 100 frames and 5 processes,
give each 20 pages.
 Proportional allocation – Allocate according to the size of
process.
– priority allocation: If process Pi generates a page fault:
 select for replacement a frame from a process with lower
priority number.
 select for replacement one of its frames.
Operating System Concepts
8.44
Silberschatz and Galvin1999
Global vs. Local Allocation
•
Global replacement – process selects a replacement frame from
the set of all frames; one process can take a frame from another.
•
Local replacement – each process selects from only its own set of
allocated frames.
Operating System Concepts
8.45
Silberschatz and Galvin1999
Thrashing
•
If a process does not have “enough” pages, the page-fault rate is
very high. This leads to:
– low CPU utilization.
– operating system thinks that it needs to increase the degree
of multiprogramming.
– another process added to the system.
•
Thrashing  a process is busy swapping pages in and out.
Operating System Concepts
8.46
Silberschatz and Galvin1999
Thrashing Diagram
•
•
Why does paging work?
Locality model
– Process migrates from one locality to another.
– Localities may overlap.
Why does thrashing occur?
 size of locality > total memory size
Operating System Concepts
8.47
Silberschatz and Galvin1999
Working Set Page Faulting
•
Establish “acceptable” page-fault rate.
– If actual rate too low, process loses frame.
– If actual rate too high, process gains frame.
Operating System Concepts
8.48
Silberschatz and Galvin1999
Demand Segmentation
•
•
•
Used when insufficient hardware to implement demand paging.
OS/2 allocates memory in segments, which it keeps track of
through segment descriptors
Segment descriptor contains a valid bit to indicate whether the
segment is currently in memory.
– If segment is in main memory, access continues,
– If not in memory, segment fault.
Operating System Concepts
8.49
Silberschatz and Galvin1999
Virtual Memory: Group Activity (30m)
Assign an area
Present results
Operating System Concepts
Thrashing
Pre-paging
Inverted page table
Interlocking
Segmentation
Characteristics
Why it exists
How affects rest of
system
5- 10 minutes, 1 person
fine
8.50
Silberschatz and Galvin1999
Next Week: WS4 Preview
•
•
•
•
•
•
•
•
Homework review
Collect study group papers
Logical and physical file concepts
Group activity on above
File management
Group activity on file system performance
Summary and preview
Mid term exam! (1 hr) – see Website for sample questions
Operating System Concepts
8.51
Silberschatz and Galvin1999
Study group milestone: WS4
Identify file
structures and
access methods
Acces methods
Directory structures
Data protection
File consistency
3 - 5 page paper
Operating System Concepts
8.52
Silberschatz and Galvin1999